Algoritmul Floyd-Steinberg


Exemplu de imagine RGB pe 24 de biți (stânga) convertită în RGB pe 3 biți (dreapta) utilizând algoritmul de dithering Floyd-Steinberg

Algoritmul Floyd-Steinberg este un algoritm de dithering publicat în 1976 de Robert W. Floyd și Louis Steinberg . Este utilizat în programele de manipulare a imaginilor grafice, de exemplu la conversia unei imagini în format GIF , care este limitat la 256 de nuanțe de culoare.

Descriere

Acest algoritm efectuează dithering prin răspândirea erorii de cuantificare a unui pixel la pixelii vecini. Mai precis, în algoritmul pe care îl propun, eroarea unui pixel este răspândită la pixelii din jur în aceste proporții: $7/16$ ${\ displaystyle 7/16}$ ${\ displaystyle 7/16}$ din eroare se adaugă pixelului din dreapta, $3/16$ ${\ displaystyle 3/16}$ ${\ displaystyle 3/16}$ la pixelul din stânga jos, $5/16$ ${\ displaystyle 5/16}$ ${\ displaystyle 5/16}$ la pixelul de bază, e $1/16$ ${\ displaystyle 1/16}$ ${\ displaystyle 1/16}$ la pixelul din dreapta jos.

${\begin{bmatrix}0&0&0\\0&0&{7 \over 16}\\{3 \over 16}&{5 \over 16}&{1 \over 16}\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0 & 0 & 0 \\ 0 & 0 & {7 \ over 16} \\ {3 \ over 16} & {5 \ over 16} & {1 \ over 16} \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} 0 & 0 & 0 \\ 0 & 0 & {7 \ over 16} \\ {3 \ over 16} & {5 \ over 16} & {1 \ over 16} \ end {bmatrix}}}$

De exemplu, să luăm în considerare o matrice cu următoarele valori ale pixelilor:

${\begin{bmatrix}0.00&0.00&0.00\\0.00&1.00&0.00\\0.00&0.00&0.00\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0.00 & 0.00 & 0.00 \\ 0.00 & 1.00 & 0.00 \\ 0.00 & 0.00 & 0.00 \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} 0.00 & 0.00 & 0.00 \\ 0.00 & 1.00 & 0.00 \\ 0.00 & 0.00 & 0.00 \ end {bmatrix}}}$

Dacă valoarea centrală este cuantificată la zero și eroarea este răspândită conform algoritmului Floyd-Steinberg, acesta va fi rezultatul:

${\begin{bmatrix}0.00&0.00&0.00\\0.00&0&0.44\\0.19&0.31&0.06\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0.00 & 0.00 & 0.00 \\ 0.00 & 0 & 0.44 \\ 0.19 & 0.31 & 0.06 \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} 0.00 & 0.00 & 0.00 \\ 0.00 & 0 & 0.44 \\ 0.19 & 0.31 & 0.06 \ end {bmatrix}}}$


Un alt exemplu de dithering Floyd-Steinberg efectuat pe o imagine alb-negru a unui detaliu al lui David lui Michelangelo

Algoritmul examinează imaginea de la stânga la dreapta și de sus în jos, cuantificând valorile pixelilor unul câte unul, transferând eroarea de cuantificare a fiecărui pixel către cei adiacenți, fără a implica totuși pe cei deja cuantizați. Deci, dacă un anumit număr de pixeli a fost deja rotunjit în jos, se poate aștepta ca următorul pixel să fie rotunjit în sus, astfel încât media cuantificării erorii este aproape de zero.

În unele implementări, direcția orizontală a analizei alternează între linii (o linie la dreapta, apoi una la stânga și așa mai departe): acest mod este cunoscut sub numele de "scanare serpentină" sau "dithering bustrofedic ".

Coeficienții de difuzie au proprietatea că, dacă valorile culorilor inițiale ale nuanței pixelilor sunt exact aceleași, rezultatul ditheringului va fi un model de tablă de șah. De exemplu, 50% gri poate genera un model de șah alb și negru.

Rețineți că întregul algoritm poate fi rulat „în loc”, mai degrabă decât acumularea erorii într-un tampon separat.

Eșantion de cod

Următorul este un exemplu pseudocodat al algoritmului:

 pentru fiecare y de sus în jos
   pentru fiecare x de la stânga la dreapta
      vechi_pixel: = pixel [x] [y]
      pixeli_nou: = găsiți_culoarea_de_tabelul_aproape (pixel_vechi)
      pixel [x] [y]: = pixel nou
      error_quant: = pixel_vechi - pixel_nou
      pixel [x + 1] [y]: = pixel [x + 1] [y] + 7/16 * amount_error
      pixel [x-1] [y + 1]: = pixel [x-1] [y + 1] + 3/16 * cantitate de eroare
      pixel [x] [y + 1]: = pixel [x] [y + 1] + 5/16 * amount_error
      pixel [x + 1] [y + 1]: = pixel [x + 1] [y + 1] + 1/16 * suma erorii

Pentru a obține un rezultat bun, cuantificarea erorilor ar trebui să fie suficient de precisă pentru a preveni orice erori de rotunjire care ar putea afecta imaginea finală. De exemplu, pentru a converti o imagine pe 16 biți într-o imagine pe 8 biți, funcția trova_il_colore_della_tavolozza_più_vicino() ar putea efectua o operație simplă:

 find_color_of_clearest_table (vechi_pixel) = (vechi_pixel + 128) / 256

linkuri externe

( RO ) Cuantizarea imaginii, semitonarea și deconectarea - Lecție pas cu pas pentru învățarea cuantizării, semitonarea și deconectarea
( EN ) Floyd-Steinberg Dithering - Descriere și imagini ilustrative

Portal IT : accesați intrările Wikipedia care se ocupă cu IT