Algoritme Floyd–Steinberg itu apa sih?

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.

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).

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 .

untuk tiap y dari atas sampai bawah,

untuk tiap x dari kiri sampai kanan,