[cite]10.1109/78.107417[/cite]

1. Introduction

보통 화면에 뿌려지는 이미지는 red, green, blue의 3가지 컬러에 각각 8비트씩을 할당하여, 한 픽셀에 24비트의 데이터량을 가집니다. 따라서 높은 해상도에서 모든 색상을 표현하기 위해서는 빠른 속도의 메모리가 필요할 수밖에 없습니다. 이러한 환경 아래에서 생겨난 방법이 바로 컬러 룩업 테이블을 이용하는 것입니다. 화면에 출력하기 위한 색상 값이 들어있는 테이틀을 미리 가지고 있고, 이미지는 컬러 값이 아닌 테이블의 항목 위치만 전송하여 데이터를 줄여보겠다는 생각입니다. 이 테이블을 팔레트라고 합니다. 이 팔레트의 크기가 본래 컬러 공간보다 작아야지만 속도 면에서 이득이 있을 것인데, 그렇게 되면 일부 표현하지 못하는 색상이 생길 수 밖에 없습니다.

따라서 우리는 적은 색상을 사용하면서도, 원래 이미지를 어떻게하면 잘 표현할지를 고민하게 됩니다. 바로 Color Quantization 방법입니다.

저자는 이 color quantization을 크게 두가지 종류로 나누어, 1. 팔레트의 색상을 어떻게 구성할 것인지와, 2. 이미지의 픽셀을 어떤 팔레트의 색으로 대체할 것인지에 대한 방법들을 소개합니다.

팔레트 색상 구성을 위해 이진 트리를 사용하여 빠른 속도를 꾀하면서 최대한 본래 이미지와의 에러가 적도록 팔레트를 만들 것입니다. 또한 color quantization의 단점인 false contouring를 방지하기 위하여 디더링 방법을 사용합니다.

이미지는 이미 gamma corrected 되어있다고 가정합니다.

2. Color Palette Design

A. Binary Tree Palette Design

팔레트의 색을 결정하는 일은 원래의 색공간 S를 미리 정해진 M개 영역으로 할당하는 일과 같습니다.

이제 이진트리를 이용하여 S를 표현할 것입니다. S는 루트 노드로 삼고 그 하위 노드들은 서로 겹치지 않는 S의 부분 집합입니다. 따라서 M개의 터미널을 가지는 트리를 구성하게 되면 전체 S는 M의 부분 집합을 나뉘게 되고 각 부분 집합은 하나의 색으로 할당되어 팔레트가 구성될 것입니다. 트리의 노드 n에 해당하는 색상 집합을 $ C_n $이라고 한다면, 그 하위 노드들은 각각 $ C_{2n}, C_{2n+1} $ 이 될 것입니다.

지금부터 이진 트리를 구성하기 위해 최상위 노드 S부터 하나씩 쪼개어 하위 노드를 생성해봅시다. 각 노드를 나누는 법은 공통된 기준에 의해서 이루어지는데 논문에서는 그 기준으로 total squared error (TSE) 를 제시하고 이를 최소로 하는 트리를 생성하고자 합니다.

$$TSE = \sum_{\text{all leaves } n} \sum_{s \in C_n} || x_s - q_n||^2$$

여기서 $s$는 $C_n$에 포함되는 픽셀값을 갖는 픽셀들을 가리키고, $x_s$는 픽셀의 값으로 RGB 색공간에 의해 3차원 벡터 값입니다. $ q_n $은 나눠진 노드 $ C_n $의 quantization된 값을 말합니다. 계산을 쉽게 하기 위하여 추가적으로 통계적 계산을 미리 해봅시다.

$$R_n = \sum_{s \in C_n} x_s x_s^T$$

$$m_n = \sum_{s \in C_n} x_s$$

$$N_n = | C_n |$$

따라서 $ R_n $은 3 * 3 크기의 행렬이 될 것이고, $ N_n $ 은 노드 n에 속하는 색상을 가지는 픽셀들의 수를 뜻합니다.

이제 노드 n에 속하는 색상이 quantization된 후의 색을 다음과 같이 평균값으로 정의하도록 합니다.

$$q_n = \frac{m_n}{N_n}$$

또한 노드 n에 해당하는 픽셀들의 색상 분포에 대한 covariance 는,

$$\tilde{R} = R_n - \frac{1}{N_n} m_n m_n^T$$

한 컬러 값 $ q_n $을 갖는 노드를 값 $q_{2n}, q_{2n + 1} $을 갖는 노드 둘로 나누기 위해서는, 먼저 앞의 TSE가 적어지는 컬러 값을 선택하여 나누어야 합니다. 노드 n의 색상 분포에서 생각해본다면, 분포의 평균 색상 지점을 중심으로, 가장 넓게 분포되는 방향의 수직 방향으로 나눈다면 분포를 최대한 넓게 잘 분리할 수 있다고 생각할 수 있습니다.

이를 수식으로 나타내면, 앞의 covariance 행렬 $ \tilde{R} $의 가장 큰 eigenvalue $ \lambda_n $에 해당하는 eigenvector $ e_n $ 를 구한 뒤,

$$C_{2n} = {s \in C_n : e^T_nx_s \leq e^T_n q_n }$$

$$C_{2n+1} = {s \in C_n : e^T_nx_s \gt e^T_n q_n }$$

를 계산하면 둘을 분리할 수 있습니다.

그리고 다음과 같은 과정으로 분리된 후의 각 노드가 가지는 통계적 값을 일부 간단하게 갱신할 수 있습니다.

$$R_{2n + 1} = R_n - R_{2n}$$

$$m_{2n + 1} = m_n - m_{2n}$$

$$N_{2n + 1} = N_n - N_{2n}$$

위의 과정을 M개의 터미널을 가질 때까지 반복하면 컬러 팔레트를 생성할 수 있습니다. 그 과정을 정리하면 아래와 같습니다.

논문에는 계산 복잡도에 대한 분석 부분이 있으나 생략하도록 하겠습니다.

B. Subjectively Weighted TSE Criteria

앞에서 설명한 TSE를 이용한 방법에 가중치를 적용하면 확장이 가능합니다.

$$WTSE = \sum_{\text{all leaves } n} \sum_{s \in C_n} W_s(x) || x_s - q_n||^2$$

식에서 $ W_s $가 가중치에 관한 함수로, 각 픽셀 위치 s의 주변에 의해 결정되는 값입니다. 따라서 지역적 특성을 반영되기 때문에 이미지에 따라 최대한의 품질을 내도록 유도할 수 있습니다. 가중치를 적용하였을 때 계산식은 아래와 같이 수정됩니다.

$$R_n = \sum_{s \in C_n} W_s x_s x_s^T$$

$$m_n = \sum_{s \in C_n} W_s x_s$$

$$N_n = \sum_{s \in C_n} W_s$$

$$\tilde{R}_n = R_n - \frac{1}{N_n} m_n m_n^T$$

$$q_n = \frac{m_n}{N_n}$$

가중치를 결정하는 방법에는 여러가지가 있겠지만 한가지 방법을 예로 들어보겠습니다. 팔레트의 수가 적을 수록 나타나는 큰 문제는 false contouring 입니다. 이것은 본래 비슷한 색들이 하나의 같은 색으로 quantization 되는 특성 때문에 이미지에서 색깔이 부드럽게 변화하는 부분이 모두 같은 색을 띄게 되는 문제점입니다. 따라서 이러한 부분에서는 가중치를 많이 주어 좀 더 세밀하게 quantization을 하도록 유도할 수 있습니다.

$$W_s = (\frac{1}{h * (min(||\nabla y ||, 16) + 2)})^2$$

정의된 식에서 $ h $는 노이즈의 영향을 적게 받기 위한 convolution kernel이고, $ \nabla y $는 RGB로부터 변환된 밝기 값의 그래디언트입니다. 따라서 16이 넘는 그래디언트는 에지로 생각하고 가중치를 최대한 적은 가중치가 계산될 것이고, 그래디언트 값이 작을 수록 가중치가 높아질 것입니다. 실험에서는 $ h $를 5 * 5 크기의 모든 성분이 1인 행렬을 사용하였습니다.

C. Erosion-Based Weighting

false contouring을 해결하는 방법으로 가중치를 주는 것과 비슷한 방법을 한가지 더 제안하고 있습니다. 만약 quantization 작업을 수행하고 나서 한가지 색으로 묶이는 영역이 넓다면 그 부분에서 false contouring이 나타날 부분이라고 예상할 수 있습니다. 따라서 그러한 부분을 계산에 반영하는 방법을 생각해볼 수 있습니다.

트리를 구성하는 중 노드를 나누는 과정에서, 한 노드 $ C_n $에 해당하는 픽셀들을 생각할 수 있습니다. 다음 그 픽셀들을 모폴로지(morphology) 연산을 이용하여 8 이웃 방식의 erosion을 하면 실질적인 영역의 크기 $ w_n $을 계산해낼 수 있습니다. 앞에서는 quantization을 위하여 2개로 분리할 다음 노드를 선택하는 과정에서 가장 큰 $ \lambda_n $를 선택하였지만, 이에 가중치를 적용하여 $ w_n \lambda_n $ 이 가장 높은 노드를 선택한다면, 영역이 넓은 노드를 우선적으로 나눌 수 있게 될 것입니다.

D. The LBG Algorithm

LBG 알고리즘은 반복적인 계산을 통하여 주어진 팔레트를 개선하는 방법입니다. 방법은 간단합니다.

먼저 M개의 팔레트가 정해지고 나면, 픽셀을 자신의 색과 가장 가까운 팔레트에 속하도록 수정합니다.

$$C_m = \{x_n : ||x-n - q_m \leq || x_n - q_k ||, 1 \leq k \leq M \}$$

다음 수정된 픽셀들을 반영하여 팔레트 색을 갱신합니다.

$$q_m = 1 / |c_m| \sum_{s \in C_m} x_s$$

이러한 과정을 모든 터미널 노드들에 대하여 더 이상 변화가 없거나 TSE 값이 적절한 값 이하고 적어질 때 까지 반복합니다.

이 방법은 expectation and maximization (EM) 과 같은 방식으로 TSE가 최적 해는 아니더라도 계속적으로 줄어들어 minimum 지점으로 수렴하는 것을 보장합니다.

3. Pixel Mapping

팔레트를 결정하였으면 이제 각 픽셀을 팔레트의 색으로 변환할 차례입니다. 여기서 높은 TSE를 허용하더라도 본래 이미지의 지역적 평균 색상이 quantization 이후의 값과 비슷하도록 하는 것이 목적입니다. 논문에서는 두가지 방법을 제시하고 있습니다.

A. Ordered Dither

이 방법은 가짜 랜덤 노이즈 패턴을 생성하여 quantization 직전에 이미지에 노이즈를 임의로 추가하는 방법입니다.

n * n 크기의 노이즈 패턴 행렬을 만들고 각 픽셀에 이를 토대로 노이즈를 추가합니다.

$$\tilde{x}_{(k, l)} = d_{(i \mod n\text{, } j \mod n)} + x_{(i, j)}$$

노이즈 패턴은 그 평균 값이 0이고 저주파 성분이 적도록 구성하여야 합니다. 노이즈 패턴은 인접하는 픽셀의 컬러들이 같지 않도록 하여 false contouring이 되는 것을 방지하도록 각 성분이 충분한 크기를 가져야합니다. 하지만, 이미지에 따라 팔레트가 다르게 생성될 경우 노이즈의 수준이 얼마나 되어야할지 미리 알 수가 없다는 다점이 있습니다.

이를 해결하는 방법 중 하나는 각 픽셀의 색상과 가장 가까운 2개의 팔레트 색을 선택하여, 둘간의 차의 배수로 노이즈를 추가하는 방법을 생각할 수 있습니다.

$$\tilde{x}_{(i, j)} = (q_2 - q_1) d_{(i \mod n\text{, } j \mod n)} + x_{(i, j)}$$

이 때에는 노이즈 패턴의 크기를 $ [ -1/2, 1/2] $ 로 하여야 합니다.

B. Error Diffusion

이 방법은 quantization 이전과 이후의 이미지가 평균 값을 갖도록 하는 방법입니다. 본래 픽셀과 quantization 이후의 픽셀 값의 차를 인접 픽셀로 확산시켜, 다음 픽셀은 오차를 포함하여 quantization 하도록 유도하는 방법입니다. 이 방법은 기존의 잘 알려진 Floyd, Steinberg 의 방법과 완전히 동일합니다.

Quantization 이후의 픽셀 색상을 선택하는 방법은 보통 픽셀의 색상과 가장 거리가 가까운 팔레트 색을 고르는 방법이 사용됩니다. 이 부분에서도 기존 만들어진 이진 트리를 통하여 속도 향상을 얻을 수 있습니다.

또한 이미지에 따라 다르게 팔레트를 생성하는 방법이기 대문에 특정한 공간에 색상이 몰려 있을 경우에도 이 부분에 충분히 많은 색상을 할당하여 quantization의 부작용을 방지할 수 있다는 장점을 가집니다.

4. Results

기존의 비트를 잘라내는 방식 (8, 8, 4), 히스토그램 기반 방식 (HIST), 제안하는 TSE (labled BS), WTSE (WBS), erosion-based (EBBS) 방식에 대하여 변환 후의 품질과 계산 속도 면에서 비교하였습니다. 품질은 RMSE, WRMSE, ACIS 를 기준으로 판단하였습니다.

---