플로이드-스타인버그 디더링

파일:Michelangelo's David - Floyd-Steinberg.png

플로이드-스타인버그 디더링이 적용된 사진

아무런 디더링을 하지 않은 사진

플로이드-스타인버그 디더링은 1976년 로버트 플로이드와 루이스 스타인버그가 고안한 영상 디더링 알고리듬이다. 이는 영상 편집 소프트웨어에서 널리 쓰이는데, 예를 들어 최대 256색만을 지원하는 GIF 형식으로 영상을 저장하기 위해 변환할 때 쓰일 수 있다.

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

$\frac{1}{16} [\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 7 \\ 3 & 5 & 1 \end{matrix}]$

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

로 계산될 수 있다.

참고 문헌

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–77 (1976).