[DIP] Dithering

다음은 wikipedia의 정의임.

Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and video data.

즉, 의도적으로 삽입된 noise인데 이를 사람이 보거나 들을 때, quantizaiton error를 randomize하여 최소화된 qunantization error를 느끼게 하는 것이다.

실제로 256 단계의 gray-scale이미지를 0,1의 binary image (or monochrome image)로 변환하면 quantization error로 인해 매우 image가 부자연스러워보인다. Dithering은 ideal 하게 quantization하면 bit-depth의 부족으로 인한 quantizaiton error가 심할 경우, 주변 pixel들의 값을 고려하여 의도적으로 noise를 삽입함으로서 사람이 느끼기에 0,1로만 구성된 pixel임에도 해당 pixel들의 밀도에 의해 명암을 느끼게 해주는 방법이다.

유명한 Rena 이미지로 효과를 보자.

가장 유명한 dithering 방법은 Floyd-Steinberg dithering으로 quantization error를 밑의 3개의 pixel과 오른쪽은 1개의 pixel에 전달하고나서 thrsholding하면 된다. 오류 전파 정도는 아래 그림(from : https://wh00300.tistory.com/223)을 참고하라.

PIL에서는 이미 제공하고 있으며 사용법은 다음과 같다 (convert 메소드에서 1만 넘겨주면 된다).

import PIL
import requests
import cv2
import numpy as np
import matplotlib.pyplot as plt

url  = 'https://raw.githubusercontent.com/dsaint31x/OpenCV_Python_Tutorial/master/images/lena.png'
image_ndarray = np.asarray(bytearray(requests.get(url).content), dtype=np.uint8)
img = cv2.imdecode(image_ndarray, cv2.IMREAD_COLOR)

img_go = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

img_g = img_go.copy()
BW= PIL.Image.fromarray(img).convert('1')
plt.imshow(BW, cmap='gray')
print(np.unique(BW))

• opencv를 선호하는 관계로, 우선 opencv로 읽어들인 후 PIL로 바꿈.
• PIL로 로딩해도 되며, 이 경우 위의 예제는 더 간단해진다.

opencv에선 제공되는 것을 못 찾았고 Bohumír Zámečník가 제공해준 구현물이 제일 빠른 터라 여기 첨부한다.
original gist

import cv2
import numpy as np
from numba import jit
import matplotlib.pyplot as plt

@jit(nopython=True)
def floyd_steinberg(image):
    # image: np.array of shape (height, width), dtype=float, 0.0-1.0
    # works in-place!
    h, w = image.shape
    for y in range(h):
        for x in range(w):
            old = image[y, x]
            new = np.round(old)
            image[y, x] = new
            error = old - new
            # precomputing the constants helps
            if x + 1 < w:
                image[y, x + 1] += error * 0.4375 # right, 7 / 16
            if (y + 1 < h) and (x + 1 < w):
                image[y + 1, x + 1] += error * 0.0625 # right, down, 1 / 16
            if y + 1 < h:
                image[y + 1, x] += error * 0.3125 # down, 5 / 16
            if (x - 1 >= 0) and (y + 1 < h): 
                image[y + 1, x - 1] += error * 0.1875 # left, down, 3 / 16
    return image

def dithering(img_gray):
    img = np.array(img_gray, dtype=float)/np.max(img_gray)
    _, BW = cv2.threshold(floyd_steinberg(img),0,1, cv2.THRESH_BINARY)
    return BW

BW= dithering(img_g)
plt.imshow(BW,cmap='gray')
print(np.unique(BW))

• 속도 향상의 핵심은 numa의 사용 덕이다.
• decorator를 주석처리하면, 당연히 느려진다. = =;;

color image에서도 적용가능한 방식이다. 위의 구현물들을 조금 손을 봐야하지만..

https://gist.github.com/dsaint31x/c70896b2c20e411f437d220badccdfcb

DIP_Floyd_Steinberg_dithering.ipynb

References

• R. W. Floyd and L. Steinberg, “An Adaptive Algorithm for Spatial Grayscale,” Proceedings of the Society of Information Display, Vol. 17, No. 2, 1976, pp. 75-77.
• Wikipedia

R. W. Floyd and L. Steinberg, “An Adaptive Algorithm for Spatial Grayscale,” Proceedings of the Society of Information Displ

Floyd–Steinberg dithering - Wikipedia