플로이드-스타인버그 디더링 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Michelangelo's David - Floyd-Steinberg.png|섬네일|플로이드-스타인버그 디더링이 적용된 사진]]
[[파일:Michelangelo's David - drempel.png|섬네일|아무런 디더링을 하지 않은 사진]]
'''플로이드-스타인버그 디더링'''은 1976년 [[로버트 플로이드]]와 [[루이스 스타인버그]]가 고안한 영상 [[디더링]] 알고리듬이다. 이는 영상 편집 소프트웨어에서 널리 쓰이는데, 예를 들어 최대 256색만을 지원하는 [[GIF]] 형식으로 영상을 저장하기 위해 변환할 때 쓰일 수 있다.

이 알고리듬은 [[픽셀]]의 [[양자화 오류]]를 주위의 픽셀로 분산시킴으로써 디더링을 수행하며, 그 분포는 다음과 같다.

<math>
\frac{\displaystyle 1}{\displaystyle 16}
\begin{bmatrix}
0 & 0 & 0 \\
0 & 0 & 7 \\
3 & 5 & 1 \\
\end{bmatrix}
</math>

알고리듬은 영상을 왼쪽에서 오른쪽, 위에서 아래로 따라가면서 각각의 픽셀을 양자화한다. 양자화 오류는 주위의 픽셀로 이전되지만, 이미 양자화된 픽셀은 영향을 받지 않는다. 또한, 픽셀의 값이 반올림 결과 내림이 된 픽셀이 많을수록 다음 픽셀은 올림이 될 가능성이 커지며, 이로써 평균적인 양자화 오류는 0에 가까워진다.

구현 중에는 홀수번째 줄과 짝수번째 줄의 디더링이 별도로 이루어지기도 하는데, 이를 가리켜 "serpentine scanning"이라 한다.

알고리듬을 [[의사 코드]]로 표현하면 다음과 같다.
 '''for each''' y
    '''for each''' x
       oldpixel := pixel[x][y]
       newpixel := find_closest_palette_color(oldpixel)
       pixel[x][y] := newpixel
       quant_error := oldpixel - newpixel
       pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
       pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
       pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
       pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

양자화 계수에는 만약 원래의 픽셀 값이 이용 가능한 가장 가까운 값들의 정확히 중앙값일 경우 디더링한 결과는 체스판과 같은 패턴을 이루는 성질이 있다. 예를 들어 50% 회색 데이터를 흑백으로 변환할 경우 흑백 체스판처럼 디더링될 수 있다. 최적화된 디더링을 위해서는 양자화 오류의 계산이 반올림 오류가 결과에 영향을 주지 않을만큼 정확해야 한다.

예를 들어, 16비트를 8비트로 변환할 경우 find_closest_palette_color()는 간단히
 find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256
로 계산될 수 있다.

== 참고 문헌 ==
* [http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html Floyd-Steinberg Dithering] (Graphics course project, Visgraf lab, Brazil)
*R.W. Floyd, L. Steinberg, ''An adaptive algorithm for spatial grey scale''. Proceedings of the Society of Information Display '''17''', 75&ndash;77 (1976).

[[분류:컴퓨터 그래픽스 알고리즘]]