색 양자화

컴퓨터 그래픽스에서 **색 양자화**(color quantization) 또는 **색 이미지 양자화**(color image quantization)는 색 공간에 적용되는 양자화이다. 이는 영상에 사용되는 서로 다른 색의 수를 줄이는 과정으로, 보통 새 이미지가 원래 이미지와 시각적으로 최대한 유사하게 보이도록 하는 것을 목적으로 한다. 비트맵에 대해 색 양자화를 수행하는 컴퓨터 알고리즘은 1970년대부터 연구되어 왔다. 색 양자화는 주로 메모리 제한으로 인해 제한된 수의 색상만 표시할 수 있는 장치에서 많은 색상을 가진 이미지를 표시하는 데 필수적이며, 특정 유형의 이미지를 효율적으로 압축할 수 있게 해준다.

"색 양자화"라는 명칭은 주로 컴퓨터 그래픽스 연구 문헌에서 사용된다. 응용 분야에서는 최적화된 팔레트 생성(optimized palette generation), 최적 팔레트 생성(optimal palette generation), 또는 색상 수 감소(decreasing color depth)와 같은 용어가 사용된다. 표준 알고리즘에 의해 생성된 팔레트가 반드시 가능한 최선의 결과는 아니기 때문에, 이러한 용어 중 일부는 오해의 소지가 있다.

## 알고리즘

대부분의 표준 기술은 색 양자화를 3차원 공간에서의 점 클러스터링 문제로 다룬다. 여기서 점은 원본 이미지에서 발견되는 색상을 나타내고 세 개의 축은 세 개의 색상 채널을 나타낸다. 거의 모든 3차원 클러스터링 알고리즘을 색 양자화에 적용할 수 있으며 그 반대도 마찬가지다. 클러스터가 위치한 후에는 일반적으로 각 클러스터의 점들을 평균하여 해당 클러스터의 모든 색상이 매핑되는 대표 색상을 얻는다. 세 가지 색상 채널은 보통 빨강, 초록, 파랑이지만, 유클리드 거리가 지각적 차이와 더 일치하는 Lab 색 공간도 많이 선택된다.

1979년 폴 헤크버트(Paul Heckbert)가 발명한 중앙값 절단(median cut) 알고리즘은 현재까지 색 양자화에서 가장 널리 쓰이는 알고리즘이다. 이 방식의 다양한 변형이 사용되고 있다. 이 이전에는 대부분의 색 양자화가 파퓰레이션(population) 알고리즘 또는 파퓰레이션 방법을 사용하여 수행되었는데, 이는 본질적으로 동일한 크기 범위의 히스토그램을 구성하고 점이 가장 많은 범위에 색상을 할당하는 방식이다. 더 현대적이고 인기 있는 방법은 게르바우츠(Gervautz)와 푸르가토퍼(Purgathofer)가 처음 고안하고 Xerox PARC 연구원인 댄 블룸버그(Dan Bloomberg)가 개선한 팔진트리를 이용한 클러스터링이다.

운영 체제에서 사용되는 것과 같은 실시간 색 양자화 시스템에서 흔히 볼 수 있듯이 팔레트가 고정된 경우, 색 양자화는 보통 "직선 거리" 또는 "최근접 색상" 알고리즘을 사용하여 수행된다. 이 알고리즘은 단순히 원본 이미지의 각 색상을 가져와 가장 가까운 팔레트 항목을 찾는다. 여기서 거리는 3차원 공간의 두 대응점 사이의 거리에 의해 결정된다. 즉, 색상이 (r_1, g_1, b_1) 및 (r_2, g_2, b_2)인 경우, 다음과 같은 유클리드 거리를 최소화하고자 한다.

:\sqrt{(r_1-r_2)^2 + (g_1-g_2)^2 + (b_1-b_2)^2}.

이는 효과적으로 색 육면체를 보로노이 다이어그램으로 분해한다. 여기서 팔레트 항목은 점이 되고 하나의 셀은 단일 팔레트 항목으로 매핑되는 모든 색상을 포함한다. 보로노이 다이어그램을 계산하고 주어진 점이 어느 영역에 속하는지 결정하기 위한 계산기하학의 효율적인 알고리즘이 존재한다. 실제로는 인덱스 팔레트가 매우 작아서 이러한 알고리즘까지는 필요하지 않은 경우가 많다.

프레임|공간 색 양자화를 사용하여 4색으로 축소된 다채로운 이미지.
색 양자화는 디더링과 자주 결합된다. 디더링은 매끄러운 그라데이션을 양자화할 때 나타나는 밴딩 현상과 같은 불쾌한 아티팩트를 제거하고 더 많은 색상이 있는 것처럼 보이게 할 수 있다. 색 양자화를 위한 일부 현대적인 방식은 팔레트 선택과 디더링을 독립적으로 수행하는 대신 한 단계에서 결합하려고 시도한다.

완전히 다른 접근 방식을 사용하는 덜 빈번하게 사용되는 방법들도 여럿 발명되었다. 1995년 올레그 베레브카(Oleg Verevka)가 고안한 로컬 K-평균(Local K-means) 알고리즘은 시스템에서 사용하기 위해 "예약된 색상"의 핵심 세트가 고정되어 있고 서로 다른 색상 구성표를 가진 많은 이미지가 동시에 표시될 수 있는 윈도잉 시스템에서 사용하도록 설계되었다. 이는 팔레트에 대한 초기 추측을 한 다음 이를 반복적으로 정제하는 포스트 클러스터링 방식이다.

색 양자화 초기에는 높은 계산 요구 사항과 초기화에 대한 민감도 때문에 K-평균 알고리즘이 부적합하다고 여겨졌다. 2011년, M. 에므레 첼레비(M. Emre Celebi)는 색 양자화기로서의 K-평균의 성능을 다시 조사했다. 그는 K-평균의 효율적인 구현이 수많은 색 양자화 방법보다 우수한 성능을 보임을 입증했다.


파일:Ada lovelace.png|원본
파일:Ada lovelace 02k 31i.png|2색
파일:Ada lovelace 05k 24i.png|5색
파일:Ada lovelace 10k 31i.png|10색
파일:Ada k15 i48.png|15색
파일:Ada lovelace k100 i295.png|100색


고품질이지만 속도가 느린 NeuQuant 알고리즘은 코호넨 신경망을 훈련시켜 이미지를 256색으로 축소한다. 이 네트워크는 "입력 이미지의 색상 분포에 맞추기 위해 학습을 통해 스스로를 조직화한다. 각 뉴런의 RGB 공간에서의 위치를 취하면 인접한 색상이 유사한 고품질 색상 지도를 얻을 수 있다." 이는 그라데이션이 있는 이미지에 특히 유리하다.

마지막으로, 최신 방법 중 하나는 본 대학교의 푸지카(Puzicha), 헬트(Held), 케테러(Ketterer), 부만(Buhmann), 펠너(Fellner)가 고안한 공간 색 양자화(spatial color quantization)이다. 이는 디더링과 팔레트 생성을 인간의 지각 단순 모델과 결합하여 매우 적은 수의 색상에서도 시각적으로 인상적인 결과를 만들어낸다. 이는 팔레트 선택을 엄격하게 클러스터링 문제로만 다루지 않는데, 원본 이미지에서 주변 픽셀의 색상이 해당 픽셀의 색상에도 영향을 미치기 때문이다. 샘플 이미지를 참조하라.

## 역사 및 응용

PC 초기에는 비디오 메모리 제한으로 인해 비디오 어댑터가 2, 4, 16 또는 (결국) 256색만 지원하는 것이 일반적이었다. 당시에는 더 많은 색상보다는 더 많은 픽셀(고해상도)을 갖는 데 비디오 메모리를 할당하는 것을 선호했다. 색 양자화는 시각적 저하를 제한하면서 16색 및 256색 모드에서 많은 하이 컬러 이미지를 표시할 수 있게 함으로써 이러한 절충안을 정당화하는 데 도움이 되었다. 256색 모드로 제한된 비디오 장치가 주류였을 때, 많은 운영 체제는 하이 컬러 이미지를 볼 때 자동으로 양자화 및 디더링을 수행했다. 현대의 컴퓨터는 이제 인간의 눈으로 구별할 수 있는 것보다 훨씬 더 많은 수백만 가지의 색상을 동시에 표시할 수 있으므로, 이 응용 분야는 주로 모바일 장치 및 구형 하드웨어로 제한된다.

오늘날 색 양자화는 주로 GIF 및 Portable Network Graphics 이미지에서 사용된다. 오랫동안 월드 와이드 웹에서 가장 인기 있는 무손실 및 애니메이션 비트맵 형식이었던 GIF는 최대 256색까지만 지원하므로 많은 이미지에 양자화가 필수적이다. 일부 초기 웹 브라우저는 이미지를 웹 색상으로 알려진 특정 팔레트를 사용하도록 제한하여 최적화된 팔레트에 비해 품질이 심각하게 저하되기도 했다. PNG 이미지는 24비트 색상을 지원하지만, 팔레트화된 이미지에 대해 픽셀당 더 적은 비트를 사용하므로 색 양자화를 적용하면 시각적 저하 없이 파일 크기를 훨씬 더 작게 만들 수 있는 경우가 많다.

카메라 렌즈를 통해 얻을 수 있는 무한한 수의 색상을 컴퓨터 화면에 표시하는 것은 불가능하다. 따라서 사진을 디지털 표현으로 변환하는 작업에는 필연적으로 어느 정도의 양자화가 포함된다. 실질적으로 24비트 색상은 사용 가능한 색 공간 내에서 (충실하게 표현된다면) 시각적으로 동일할 정도로 충분히 작은 오차로 인간이 인지할 수 있는 거의 모든 색상을 표현하기에 충분히 풍부하다. 그러나 카메라 감지기나 화면에서 색상을 디지털화하면 필연적으로 사용 가능한 색 공간이 제한된다. 결과적으로 색상을 표현하는 데 몇 비트를 사용하는지에 관계없이 재현이 불가능한 색상이 많이 존재한다. 예를 들어, (컴퓨터 모니터에서 흔히 사용하는) 일반적인 RGB 색 공간에서는 인간의 눈이 인지할 수 있는 모든 범위의 초록색을 재현하는 것이 불가능하다.

초기 컴퓨터에서 사용할 수 있는 색상이 적었을 때, 서로 다른 양자화 알고리즘은 매우 다른 모습의 출력 이미지를 생성했다. 그 결과, 더 실물처럼 보이게 하기 위해 정교한 알고리즘을 작성하는 데 많은 시간이 소요되었다.

### 이미지 압축을 위한 양자화

많은 이미지 파일 형식은 인덱스 컬러를 지원한다.

전체 이미지 팔레트는 일반적으로 GIF 및 PNG 파일 형식에서와 같이 각 픽셀이 팔레트의 색상 중 하나를 참조하는 이미지 전체에 대한 256개의 "대표" 색상을 선택한다.

블록 팔레트는 일반적으로 4x4 픽셀의 각 블록에 대해 2개 또는 4개의 색상을 선택하며, BTC, CCC, S2TC 및 S3TC에서 사용된다.

### 편집기 지원

많은 비트맵 그래픽 편집기는 색 양자화에 대한 내장 지원 기능을 포함하고 있으며, 많은 색상을 가진 이미지를 적은 색상의 이미지 형식으로 변환할 때 자동으로 이를 수행한다. 이러한 구현의 대부분은 사용자가 원하는 색상 수를 정확하게 설정할 수 있도록 한다. 이러한 지원의 예는 다음과 같다.

* 포토샵의 모드(Mode)→인덱스 색상(Indexed Color) 기능은 고정된 윈도우 시스템 및 웹 팔레트부터 특정 이미지 또는 이미지들에 적합한 팔레트를 생성하기 위한 독자적인 로컬 및 글로벌 알고리즘에 이르기까지 다양한 양자화 알고리즘을 제공한다.
* 페인트샵 프로(Paint Shop Pro)는 색상(Colors)→색상 수 감소(Decrease Color Depth) 대화 상자에서 중앙값 절단, 팔진트리 및 고정된 표준 "웹 안전" 팔레트의 세 가지 표준 색 양자화 알고리즘을 제공한다.
* GIMP 2.8에서 이미지를 인덱스 색상으로 변환 옵션(이미지→모드→인덱스..)은 2색에서 256색까지 색상 수를 선택하여 최적의 팔레트를 생성할 수 있게 해주며, 웹 최적화 팔레트 사용, 흑백 팔레트(1비트) 사용 또는 사용자 정의 팔레트 사용 옵션을 제공한다. 사용하지 않는 색상을 팔레트에서 제거할 수 있으며 없음, 플로이드-스테인버그(보통), 플로이드-스테인버그(색 번짐 감소) 및 위치 지정(Positioned)과 같은 다양한 디더링 옵션과 투명도 디더링 활성화 기능을 제공한다.

색 양자화는 포스터리제이션 효과를 만드는 데도 사용되지만, 포스터리제이션은 동일한 색 공간 내에서 사용되는 색상 수를 최소화하려는 약간 다른 목표를 가지고 있으며 대개 고정된 팔레트를 사용한다.

일부 벡터 드로잉 프로그램도 색 양자화를 활용하는데, 특히 윤곽선 검출의 도움으로 비트맵 이미지의 트레이싱을 생성하는 래스터-벡터 변환 기술에서 사용된다.

* 잉크스케이프(Inkscape)의 경로(Path)→비트맵 트레이스(Trace Bitmap): 다중 스캔(Multiple Scans): 색상(Color) 기능은 팔진트리 양자화를 사용하여 색상 트레이스를 생성한다.

## 같이 보기

* 인덱스 컬러
* 팔레트 (컴퓨팅)
* 소프트웨어 팔레트 목록 — 적응형 팔레트 섹션.
* 디더링
* 양자화 (영상 처리)
* 영상 분할

## 각주

## 더 읽어보기

* Paul S. Heckbert. Color Image Quantization for Frame Buffer Display. ACM SIGGRAPH '82 Proceedings. 중앙값 절단 알고리즘의 첫 번째 출판물.
* Dan Bloomberg. Color quantization using octrees. Leptonica.
* Oleg Verevka. Color Image Quantization in Windows Systems with Local K-means Algorithm. Proceedings of the Western Computer Graphics Symposium '95.
* J. Puzicha, M. Held, J. Ketterer, J. M. Buhmann, and D. Fellner. On Spatial Quantization of Color Images. (전체 텍스트 .ps.gz) Technical Report IAI-TR-98-1, University of Bonn. 1998.

분류:영상 처리