Palette 라이브러리 뜯어보기

Palette 라이브러리는 이미지에서 눈에 띄는 색상들을 추출해주는 라이브러리다.

이 라이브러리가 어떤식으로 동작하는지 확인해보자.

Median cut

Palette 라이브러리는 Median cut 알고리즘을 기반으로 동작한다. Median cut은 말 그대로 중앙값을 자른다는 뜻이다. 가장 긴 차원을 따라 중앙값이 있는 지점(인덱스)에서 각 데이터 집합을 재귀적으로 자르고 임의 개수의 차원 데이터를 일련의 집합으로 정렬하는 알고리즘이다. 이 알고리즘은 일반적으로 색상 양자화(Color quantization)에 사용된다.

여기에서 말하는 양자화(quantization)란 연속적인 값을 띄엄띄엄한 값으로 바꾸어 근사하는 과정을 의미한다.

ColorCutQuantizer(소스코드)

ColorCutQuantizer는 Palette 라이브러리에서 색상을 양자화 하는 핵심 클래스다.

이 클래스가 하는 일을 3단계로 추상화 하면 다음과 같다.

1. 픽셀을 RGB888에서 RGB555로 변환
2. 히스토그램 만들기
3. 임의의 수로 컬러 갯수를 줄이기

각각 하나씩 살펴보자

1. 픽셀 양자화

Palette 라이브러리의 ColorCutQuantizer에서는 연산량을 줄이고 최적화된 컬러 값을 추출하기 위해, quantizeFromRgb888 함수 호출을 통해 픽셀을 양자화하는 작업을 선행한다.

컴퓨터 그래픽스에서 일반적으로 픽셀 하나는 RGB888로 표현하는데 R은 빨강, G는 녹색, B는 파랑이고 8은 8bits 라는 의미다. 즉, R(0~255), G(0~255), B(0~255)로 빛의 삼원색 조합으로 약 16만 가지의 색상을 표현하게 된다. 여기에 투명도 Alpha(0~255)를 더해 일반적으로 32bits 즉 4바이트 int타입의 정수형으로 픽셀을 표현한다. Palette에서는 Alpha는 고려하지 않는다.

for (int i = 0; i < pixels.length; i++) {
    final int quantizedColor = quantizeFromRgb888(pixels[i]);
    // 양자화 된 픽셀값으로 이미지내 픽셀을 변경
    pixels[i] = quantizedColor;
    ...
}

pixels에 length에 의존하여 반복문을 수행하기 때문에 실제로 이미지의 사이즈(너비 * 높이)가 클 수록 연산량이 많아지게 된다. Palette 라이브러리는 일정 퍼포먼스를 보장하기 위해 실제로 픽셀 양자화 진행하기 전에 비트맵 이미지를 112*112 이하로 작게(scale-down) 만들고 시작한다.

위 코드에서 pixels는 원본 비트맵 이미지 배열이며, 각 픽셀들은 quantizeFromRgb888 호출 이후 양자화 된 픽셀 값으로 치환된다.

8비트로 표현되던 픽셀값은 양자화 이후에 5비트로 표현된다. 왜 그런지 내부를 quantizeFromRgb888 함수와 그 내부에서 호출하는 modifyWordWidth 함수를 살펴보자

private static int quantizeFromRgb888(int color) {
    int r = modifyWordWidth(Color.red(color), 8, QUANTIZE_WORD_WIDTH);
    int g = modifyWordWidth(Color.green(color), 8, QUANTIZE_WORD_WIDTH);
    int b = modifyWordWidth(Color.blue(color), 8, QUANTIZE_WORD_WIDTH);
    return r << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) | g << QUANTIZE_WORD_WIDTH | b;
}

private static int modifyWordWidth(int value, int currentWidth, int targetWidth) {
    final int newValue;
    if (targetWidth > currentWidth) {
        newValue = value << (targetWidth - currentWidth);
    } else {
        newValue = value >> (currentWidth - targetWidth);
    }
    return newValue & ((1 << targetWidth) - 1);
}

실제로는 modifyWordWidth 호출시에 전달하는 인수인 currentWidth 와 targetWidth는 라이브러리 외부에서는 변경이 불가능 하다. 그러므로 위 함수를 좀 더 단순화 하자면 다음과 같다. (QUANTIZE_WORD_WIDTH = 5)

private static int quantizeFromRgb888(int color) {
    int r = modifyWordWidth(Color.red(color));
    int g = modifyWordWidth(Color.green(color));
    int b = modifyWordWidth(Color.blue(color));
    return r << (5 + 5) | g << 5 | b;
}

private static int modifyWordWidth(int value) {
    int newValue = value >> 3;
    return newValue & ((1 << 5) - 1);
}

비트 연산자에 익숙하지 않다면, 이 코드가 어렵게 느껴질 수 있다. (이번 기회에 비트연산자를 다시 한번 살펴보자!)

다음과 같은 픽셀 값이 있다고 가정해보자

| RED (255) | GREEN (170) | BLUE (240) |
| 1 1 1 1 1 1 1 1 | 1 0 1 0 1 0 1 0 | 1 1 1 1 0 0 0 0 |

quantizeFromRgb888를 호출하면 픽셀값의 비트를 오른쪽으로 3번 쉬프트 했다가 다시 왼쪽으로 3번 쉬프트 하면서 양자화를 진행한다. 그러면 다음과 같은 결과를 얻게 된다.

| RED (248) | GREEN (168) | BLUE (240) |
| 1 1 1 1 1 0 0 0 | 1 0 1 0 1 0 0 0 | 1 1 1 1 0 0 0 0 |

값이 달라졌지만 색상을 눈으로 볼 때는 큰 차이를 느끼기 어려우며, 이미지에서 연속되는 비슷한 픽셀값들을 그룹화 할 수 있다.

2. 히스토그램 만들기

이 포스팅에서 말하는 히스토그램이란 이미지내에 포함된 동일 픽셀값들의 개수를 배열에 카운트 해둔것을 의미한다.

int[] hist = new int[1 << (QUANTIZE_WORD_WIDTH * 3)];

채널당 8비트로 표현하는 RGB포맷에 대한 히스토그램을 만드려면 2^(3*8) = 2^24 = 16777216 길이의 배열이 필요하지만, 위 과정에서 픽셀을 5비트로 양자화 했기 때문에 배열의 길이는 2^(3*5) = 2^15 = 32768이 된다. 즉 최대 32768개의 컬러로 이미지가 표현된다.

히스토그램 생성은 위에서 다루었던 픽셀 양자화를 진행한 직후에 바로 이루어 진다.

for (int i = 0; i < pixels.length; i++) {
    final int quantizedColor = quantizeFromRgb888(pixels[i]);
    pixels[i] = quantizedColor;
    // 히스토그램 만들기
    hist[quantizedColor]++;
}

히스토그램을 만들고 나면 다음과 같이 이미지에서 몇개의 컬러가 사용되었는지 확인하는 과정을 거친다.

int distinctColorCount = 0; // 사용된 컬러 갯수
for (int color = 0; color < hist.length; color++) {
    ...
    if (hist[color] > 0) {
        distinctColorCount++;
    }
}

사용된 컬러 갯수 계산이 끝났다면, 사용된 컬러만 포함하는 배열을 생성한다.

final int[] colors = mColors = new int[distinctColorCount];
int distinctColorIndex = 0;
for (int color = 0; color < hist.length; color++) {
    if (hist[color] > 0) {
        colors[distinctColorIndex++] = color;
    }
}

3. 임의의 수로 컬러 갯수를 줄이기

median cut이 적용되는 가장 중요한 부분이다. 픽셀 양자화를 통해 사용된 컬러 갯수를 줄이기는 했지만, 충분하지 않다. 내부에서 quantizePixels라는 메서드 호출을 통해 기본값으로 최대 16컬러를 추출하게 된다.

private List<Palette.Swatch> quantizePixels(int maxColors) { // maxColors=16

    PriorityQueue<Vbox> pq = new PriorityQueue<>(maxColors, VBOX_COMPARATOR_VOLUME);
    
    pq.offer(new Vbox(0, mColors.length - 1));

    splitBoxes(pq, maxColors);

    return generateAverageColors(pq);
}

다소 내용이 복잡할 수 있어 주요 용어를 정리하고자 한다.

• Palette.Swatch : Palette 라이브러리가 추출한 컬러를 표현하는 클래스
• PriorityQueue : java.util 패키지에 포함된 데이터 구조. 기본적으로 일반적인 큐와 같지만, comparator 로직에 따라 요소들을 재정렬한다.
• Vbox : 색 공간(color space)에서 알맞는 영역의 박스로 표현한다. (중요)
• VBOX_COMPARATOR_VOLUME : PriorityQueue<Vbox>에 사용될 comparator다. 비교할 두 Vbox 에서 볼륨이 더 큰 것을 우선적으로 정렬한다. 볼륨이란 RGB 각 채널 별 컬러 표현 범위를 다 더하여 얼마나 더 박스가 큰지를 의미 한다. 본문 위에서 median cut 설명에 포함된 삽화에서 큐브 모양의 이미지를 참조하자.

위 코드에서 두번째 라인에 있는 pq.offer(new Vbox(…)); 을 보면 최초에 pq에는 Vbox 객체가 하나만 삽입된다. 이 박스는 splitBoxes 내부에서 재귀적으로 박스를 쪼개가면서 pq의 아이템을 늘려나간다.

private void splitBoxes(final PriorityQueue<Vbox> queue, final int maxSize) {
    while (queue.size() < maxSize) {
        final Vbox vbox = queue.poll();
        if (vbox != null && vbox.canSplit()) {
            // 박스를 쪼개어 삽입
            queue.offer(vbox.splitBox());
            // 꺼낸 박스를 다시 재삽입
            queue.offer(vbox);
        } else {
            // 더 이상 박스를 쪼갤 수 없으므로 반환
            return;
        }
    }
}

실제로 박스를 쪼개는 로직은 Vbox.split()에 있다.

final Vbox splitBox() {
    ...
    // 각 채널에서 채널폭이 가장 큰 녀석의 중앙값을 찾는다
    final int splitPoint = findSplitPoint();

    Vbox newBox = new Vbox(splitPoint + 1, mUpperIndex);

    // mUpperIndex 재설정 및 fitBox() 호출로 박스의 경계값을 다시 재계산한다.
    mUpperIndex = splitPoint;
    fitBox();
    return newBox;
}

중앙 값을 찾는 로직(findSplitPoint)이 다소 복잡하다. 이 포스팅에서는 이해를 돕기위한 부분적인 소스코드만 소개하므로 이 포스팅을 읽은 이후 전체 소스코드를 확인하는 것을 권장한다.

final int findSplitPoint() {
    // R(-3),G(-2),B(-1) 중 가장 채널 폭이 큰 채널(dimension)을 찾는다.
    final int longestDimension = getLongestColorDimension(); 
    final int[] colors = mColors;
    final int[] hist = mHistogram;

    // 가장 큰 컬러 채널을 기반으로 박스 내 채널순서 바꾼다.
    // 일반적으로 RGB 순으로 표현하지만, longestDimension에 따라
    // RGB, GRB 또는 BRG 로 스왑한다.
    modifySignificantOctet(
        colors, 
        longestDimension, 
        mLowerIndex, 
        mUpperIndex
    );
    
    // 전체 컬러배열에서 박스 내 범위(mLowerIndex ~ mUpperIndex+1)만 작은순으로 재정렬
    Arrays.sort(colors, mLowerIndex, mUpperIndex + 1);

    // RGB로 다시 표현하기 위해 한번 더 modifySignificantOctet 호출로 채널을 스왑
    modifySignificantOctet(
        colors, 
        longestDimension, 
        mLowerIndex, 
        mUpperIndex
    );
    
    // 컬러의 중앙값을 찾아 반환하는 과정으로, fitBox() 호출 이후 mPopulation이 결정된다.
    // mPopulation은 Vbox가 표현할 수 있는 컬러의 갯수
    final int midPoint = mPopulation / 2;    
    for (int i = mLowerIndex, count = 0; i <= mUpperIndex; i++)  {
        count += hist[colors[i]];
        if (count >= midPoint) {
            return Math.min(mUpperIndex - 1, i);
        }
    }
    return mLowerIndex;
}

위 과정을 거쳐 maxColors 만큼 Vbox가 쪼개지면, generateAverageColors를 호출하여 최종적인 컬러셋을 만들게 된다.

private List<Palette.Swatch> generateAverageColors(Collection<Vbox> vboxes) {
    ArrayList<Palette.Swatch> colors = new ArrayList<>(vboxes.size());
    for (Vbox vbox : vboxes) {
        Palette.Swatch swatch = vbox.getAverageColor();
        colors.add(swatch);
    }
    return colors;
}

기본적으로 최대 16개의 Vbox가 생성되었을 것이고, 하나의 Vbox가 표현하는 컬러범위내에서 평균 컬러 값을 구하여 최종적으로 Swatch로 반환한다. 최대 16개의 Swatch가 생성이 될 것 이며, 이로써 컬러 추출이 끝난다.

Target

Palette에는 Target(클래스)이라는 개념을 두어, 추출한 Swatch 목록에서 다시 한번 사용자가 원하는 컬러로 정제하는 과정을 거친다.

타겟을 설정하는 기준은 채도(Saturation)와 밝기(Luminance)다

기 정의된 Target은 다음과 같다.

• Light Vibrant : 채도 ↑, 밝기 ↑
• Vibrant : 채도 ↑
• Dark Vibrant: 채도 ↑, 밝기 ↓
• Light Muted: 채도 ↓, 밝기 ↑
• Muted: 채도 ↓
• Dark Muted: 채도 ↓, 밝기 ↓

채도 및 밝기는 0f~1f 로 표현되며, 추출된 Swatch들 중에서 커스텀 타겟정의 하여 이에 부합하는 Swatch를 다시 뽑아 낼 수도 있다.

마치며

median cut을 기반으로 한 Palette의 내부 동작 원리를 알아보았다. 많은 내용이 생략 되었지만, 대부분 부수적인 내용이라 판단되어 언급하지 않았다. 전체적인 내용은 공식문서와 소스코드를 확인할 수 있다.

Palette는 활용도가 높은 라이브러리이기 때문에 다른 플랫폼에서도 안드로이드의 Palette를 카피하여 만든 라이브러리 들이 많다. 나도 KMP를 통해 이 라이브러리를 코틀린으로 재작성하고, iOS, Android, Web에서 동일한 컬러를 뽑는 결과를 기대하며, 삽질 했으나 실패한 경험이 있다. 실패기를 확인하고 싶다면, 이전 포스팅을 참조하자.