Error Diffusion이란?

• Dithering

 

Dithering이란 Bit Depth가 높은 영상데이터를 Bit Depth가 낮은 영상데이터로 바꿀 때 적용하는 알고리즘 중 하나이다. 예를 들어, 12 Bit 영상데이터는 RGB 각각 0 ~ 4095까지 총 4096단계의 밝기 Value를 가지고, 10 Bit 영상데이터는 0 ~ 1023까지 총 1024단계의 밝기 Value를 가진다. 4096단계를 1024단계로 전환할 때, 단계가 1024/4096 = 1/4로 줄어드면서 실제보다 데이터가 3/4 손실하게 된다. 이 손실되는 데이터를 어떻게 보완하고 보정할 지에 대한 방법론 중 하나가 Dithering이다.

 

Dithering은 Temporal Dithering(시간적 디더링)과 Spatial Dithering(공간적 디더링)으로 나뉜다. FRC가 시간적 디더링의 한 종류였다면, Error Diffusion은 공간적 디더링의 한 종류이다.

 

시간적 디더링을 알고싶다면? 아래 링크로

FRC(Frame Rate Control)란?

 

 

 

• Error Diffusion

Error Diffusion은 말 그대로 Error를 확산하는 것이다. 특정 픽셀이 양자화되면서 발생하는 오차를 주변 픽셀에 뿌리는 것이다. 다양한 알고리즘이 있지만, 가장 대표적으로 유명한 알고리즘이 Floyd Steinburg Dithering이다.

Dithering을 적용하지 않는 사진(좌), Floyd Steingburg Dithering을 적용한 사진(우)

왼쪽과 오른쪽 둘 다 Bit Depth가 1이지만 오른쪽 사진이 더 섬세하게 표현됨을 볼 수 있다.

 

 

 

 

• 작동 방법

 

Weight of Floyd Steinburg Dithering

 

 

 

현재 픽셀에서 발생하는 에러(오차)를 오른쪽으로 7/16, 왼쪽 아래로 3/16, 아래쪽으로 5/16, 오른쪽 아래로 1/16를 곱하여 전달한다. 이때 곱해지는 Weight의 합이 1이되는 것이 중요하다. 1보다 작다면 데이터의 손실을 의미하고, 많다면 의미없는 값이 추가되어 영상 데이터가 더 밝아지게 되는것을 의미한다.

 

 

 

 

• Pseudo Code of Floyd Steinburg Dithering

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

 

find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256

 

Floyd Steinburg Dithering의 Pesudo Code는 위와 같다.

 

oldpixel : 디더링 전 픽셀, 원래의 픽셀
newpixel : 양자화된 픽셀
quant_error : 양자화 오차

 

*find_closest_palette_color() : 양자화할 때, Truncation 또는 Round를 할 수 있다. Truncation을 하면 에러가 양수만 나오고 Round를 하면 Error가 양수와 음수가 모두 나온다. 위의 함수는 Round이다.

 

보통 SW로 설계를 할 때는 Round로 하는 것이 일반적이지만, HDL로 설계할 때는 음수 처리의 불편함과 Gate 사용의 최소화를 위해 Truncation으로 처리하는 경우가 많다.

 

 

 

• 그 외의 Error Diffusion

 

Error가 확산되는 방법은 모두 같으며, 다른 점은 Weight와 인접 확산 픽셀의 개수이다.

 

Error diffusion scheme for different dithering algorithms: Floyd-Steinberg (a); Jarvis, Judice and Ninke (b); Stucki (c); Sierra (d). The flux of the whole image remains the same.

 

곱해지는 pixel을 모두 더하면 1이된다. 하지만 1이 되지 않는 알고리즘도 있다. 바로 Atkinson Dithering이다.

 

Atkinson Dithering

 

 

Atkinson Dithering은 Apple 출신 개발자 Atkinson이 개발한 디더링이다. 모든 weight를 더하면 6/8이고 1이 되지않아서 데이터의 손실이 발생한다. 위의 그림에서 원숭이의 코 부분(빨간색 원)에 Data가 씻겨져나간 것을 볼 수 있다. 하지만, 장점도 있다. 밝은 곳과 어두운 곳의 더 뚜렷한 대비를 얻을 수 있다. 또 weight가 모두 1/8이기때문에 HDL로 설계 시 적은 Gate를 사용하여 설계할 수 있다.

 

 

 

 

• 적용

개인적으로 생각하기에 Error Diffusion을 사용하기 좋은 상황은 크게 두 가지가 있다고 생각한다. 첫 번째는, Conversiion시에 Bit Depth의 차이가 큰 경우이다. 예를 들어, Image의 Bit Depth를 8bit에서 1bit로 낮출 때 Error Diffusion을 좋은 결과를 보인다.

 

 

다른 디더링과 비교해봐도 Error Diffusion의 성능이 좋다.

 

 

No Dithering(1bit) / Floyd Steinburg Dithering(1bit)

 

 

두 번째는, 밝은 이미지와 어두운 이미지가 섞인 경우이다. 예를 들어, 흰 바탕에 검은 글씨가 있는 경우가 있다. Error Diffusion을 적용하지 않으면 흰 바탕과 글씨의 층이 뚜렷하게 보이지만, Error Diffusion을 사용하는 경우 Error를 주변 픽셀로 뿌리기때문에 조금더 자연스럽게 보일 수 있다. 위의 그림을 보면 왼쪽 그림은 밝은 쪽과 어두운 쪽 경계에 층이 생기지만, 오른쪽 그림은 더 자연스럽게 보인다.

 

 

 

 

• 참고

https://en.wikipedia.org/wiki/Error_diffusion

Error diffusion - Wikipedia

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%8A%A4%ED%83%80%EC%9D%B8%EB%B2%84%EA%B7%B8_%EB%94%94%EB%8D%94%EB%A7%81

플로이드-스타인버그 디더링 - 위키백과, 우리 모두의 백과사전

https://imagej.net/plugins/dithering

Dithering

https://scipython.com/blog/floyd-steinberg-dithering/

Floyd-Steinberg Dithering