Algoritme Floyd–Steinberg

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

gambar asli

tanpa pembauran galat

hasil Floyd–Steinberg

Algoritme 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. Algoritme 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 algoritme 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 $[0, 1]$ .

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

Floyd, R. W.; Steinberg, L. (1976). "An adaptive algorithm for spatial grey scale". Proceedings of the Society of Information Display. 17: 75–77.