Algoritme Floyd–Steinberg

**Algoritma Floyd–Steinberg** adalah algoritma pembauran galat citra yang diperkenalkan pada tahun 1976 oleh Robert W. Floyd dan Louis Steinberg. Algoritma ini sering dipakai oleh perangkat lunak penyunting gambar untuk, misalnya, menyimpan gambar dalam format GIF yang terbatas 256 warna.

Algoritma ini menggunakan pembauran galat yang memindahkan sisa galat kuantisasi tiap piksel ke piksel-piksel tetangganya untuk diurus nantinya. Persebaran galatnya dilakukan menurut aturan berikut (ditampilkan dalam peta piksel).

: \begin{bmatrix}
         &                            & *                          & \displaystyle \frac{7}{16} & \ldots \\
  \ldots & \displaystyle \frac{3}{16} & \displaystyle \frac{5}{16} & \displaystyle \frac{1}{16} & \ldots \\
\end{bmatrix}

Piksel yang ditandai dengan tanda bintang (*) adalah piksel yang sedang diolah dan bagian kosong adalah piksel-piksel yang telah diolah. Algoritma ini berjalan dari kiri ke kanan, lalu dari atas ke bawah, dan melakukan kuantisasi piksel demi piksel. Galat kuantisasi disebarkan ke piksel-piksel tetangganya tanpa mengubah nilai piksel yang sudah diolah sebelumnya. Jadi, bila beberapa piksel telah dibulatkan ke bawah, semakin tinggi peluang bahwa piksel selanjutnya akan dibulatkan ke atas sehingga rata-rata galat kuantisasinya adalah nol.

Koefisien pembauran tersebut memiliki sifat bahwa, bila piksel asalnya berada di tengah-tengah dua nilai terdekat, hasil pembaurannya adalah pola papan catur. Misalnya, nilai abu-abu 50% dapat dibaurkan menjadi pola papan catur hitam dan putih. Untuk pembauran yang optimal, perhitungan galat kuantisasi harus memiliki akurasi yang cukup agar tidak ada galat pembulatan yang dapat memengaruhi citra.

Berikut adalah kode semu algoritma Floyd–Steinberg seperti yang telah dijelaskan sebelumnya. Kode berikut dapat berjalan untuk pengodean linear nilai piksel, seperti bilangan bulat 8 bit dan 16 bit atau bilangan riil dalam rentang .

 **untuk tiap** *y* **dari** atas **sampai** bawah,
   **untuk tiap** *x* **dari** kiri **sampai** kanan,
     piksel_lama ← piksel[*x*][*y*]
     piksel_baru ← cari_warna_palet_terdekat(piksel_lama)
     piksel[*x*][*y*] ← piksel_baru
     galat ← piksel_lama - piksel_baru
     piksel[*x* + 1][*y*    ] ← piksel[*x* + 1][*y*    ] + galat * 7 / 16
     piksel[*x* - 1][*y* + 1] ← piksel[*x* - 1][*y* + 1] + galat * 3 / 16
     piksel[*x*    ][*y* + 1] ← piksel[*x*    ][*y* + 1] + galat * 5 / 16
     piksel[*x* + 1][*y* + 1] ← piksel[*x* + 1][*y* + 1] + galat * 1 / 16

Ketika mengubah warna dari kedalaman 16 bit ke kedalaman 8 bit, fungsi `cari_warna_palet_terdekat` cukup membagi dan membulatkan saja, misalnya:
 cari_warna_palet_terdekat(piksel_lama) = bulatkan(piksel_lama / 256)

Kode semu di atas dapat menghasilkan piksel di luar rentang yang sah. Nilai tersebut sebaiknya dipangkas dalam fungsi `cari_warna_palet_terdekat` daripada memangkas nilai di tengah perhitungan karena bisa saja nilainya akan kembali dalam rentang. Namun, dalam bilangan bulat berlebar tetap, nilai yang di luar rentang dapat diartikan sebagai lawannya yang menyebabkan warna putih menjadi hitam sehingga harus dihindari.

## Daftar pustaka
*