Color quantization using modified median cut / modified median cut quantization (MMCQ)

color-thief.js 라는 이미지 내 대표 색상 추출 라이브러리에서 사용된 알고리즘

https://github.com/lokesh/color-thief/blob/master/src/color-thief.js

Color quantization using modified median cut / modified median cut quantization (MMCQ) 에 대한 내용이다.

아래와 같이 동작하는 것으로 추정

- median-cut 컬러 양자화로 rgb 3차원 값으로 유사한 색상들을 군집해서 대표 색상들을 만들어냄

- 그 담에 군집량이 많은 것을 1순위 추천으로 보여줌

median-cut 컬러 양자화

컬러영상을 처리할떄 가장 흔히 사용하는 컬러표현은 RGB 컬러이다. 이것은 R,G,B에 각각 8-비트를 할당하여 256-단계를 표현할수 있게하여, 전체적으로 256x256x256=16777216가지의 컬러를 표현할 수 있게하는 것이다. 그러나 인간의 눈은 이렇게 많은 컬러를 다 구별할 수 없으므로 24-비트 RGB컬러를 사용하는 경우는 대부분의 경우에 메모리의 낭비와 연산에 오버헤드를 가져오는 경우가 많이 생긴다. RGB컬러영상을 R,G,B를 각각 한축으로 하는 3차원의 컬러공간에서의 벡터(점)으로 표현이 가능하다. 컬러영상의 픽셀들이 RGB삼차원의 공간에 골고루 펴져 있는 경우는 매우 드물고, 많은 경우에는 이 컬러공간에서 군집(groups)을 이루면서 분포하게 된다. 하나의 군(group)은 유사한 RGB값을 갖는 픽셀들로 구성이 되므로, 이 군에 포함이되는 픽셀들에게 (군의 중앙에 해당하는)대표적인 컬러값을 대체하면 그 군에 포함이 된 픽셀은 이젠 RGB공간에서 한 점으로 표현이 되고, RGB공간상에는 픽셀 수만큼의 점이 있는것이 아니라, 대표RGB값에 해당하는 점만이 존해하게 된다. 따라서 적당한 Lookup테이블(colormap)을 이용하면, 적은 메모리 공간만을 가지고도원본의 컬러와 유사한 컬러를 구현할 수 있다.

이제 문제는 원래의 컬러공간을 어떻게 군집화하는가에 대한 것으로 바뀌었다. 간단한 방법으로는 원래의 컬러영상이 차지는하는 RGB공간에서의 영역을 감싸는 최소의 박스를 찾고, 이것을 원하는 최종적으로 원하는 컬러수만큼의 박스로 분할을 하는 것이다. 그러나 박스를 어떨게 분할을 해야만 제대로 컬러를 나누고, 또한 효율적으로 할 수있는가를 고려해야 한다. 분할된 박스의 크기가 너무 크면 제대로 된 대표값을 부여하기가 힘들어지고, 너무작게 만들면 원하는 수에 맞추기가 어렵다.

Median-Cut 양자화(quantization)에서 사용하는 방법은 박스의 가장 긴축을 기준으로 그 축으로  projection된 컬러히스토그램의 메디안값을 기준으로 분할을 하여서 근사적으로 픽셀들을 절반정도되게 분리를 한다 (한축에 대한 메디안이므로 정확히 반으로 분리되지 않는다). 두개의 박스가 이렇게 해서 새로 생기는데, 다시 가장 많은 픽셀을 포함하는 박스를 다시 위의 과정을 통해서 분할을 하게 된다. 이렇게 원하는 수의 박수를 얻을 떄 까지 위의 과정을 반복적으로 시행을 하게 된다.

여기서 원래의 컬러값을 모두 이용하게 되면 계산에 필요한 히스토그램을 만들기 위해서 너무 많은 메모리를 사용하게되고 이것이 또한 연산의 오버헤드로 작용하게 되므로 RGB 컬러비트에서 적당히 하위비트를 버리면, 초기의 RGB공간에서의 histogram의 크기를 줄일 수 있게 된다.(보통  하위 3-비트를 버려서, 각각 5-비트만 이용하여, 전체 컬러의 갯수를 32x32x32= 32768 로 줄인다)

이렇게 RGB공간에서의 컬러분포가 몇개의 대표적인 컬러(예:박스의 중앙값)로 줄어들면(양자화과정:: 공간에 smooth하게 분포한것이 몇개의 점으로 대체됨), 원본영상의 각각의 픽셀에서의 대체컬러값은 원래의 컬러와 가장 유사한, 죽 RGB 공간에서 유클리디안 거리가 가장 작은 박스의 컬러로 대체하면 된다.  

그러나 너무 적은 수의 컬러로 줄이게 되면 인접픽셀간의 컬러값의 차이가 눈에 띄게 나타나는 현상이 생기게 된다. 이러한 것을 줄이기 위해서는 디더링(dithering)과정과 같은 후처리가 필요하게 된다.

출처: http://blog.naver.com/helloktk/80027584478

Color quantization using modified median cut 논문: http://www.leptonica.com/papers/mediancut.pdf