Octree Color Quantization 구현

 

컬러 양자화는 이미지의 색상 수(예: 24-bit True Color)를 지정된 수(예: 256색 이하)로 줄이면서도 시각적 손실을 최소화하는 기법이다. Octree 자료구조를 활용하면 색상 공간을 효율적으로 분할하고 축소할 수 있다. Octree는 양자화 과정에서 메모리를 효율적으로 사용하고, 탐색 속도를 향상시켜준다.

• RGB 색상은 Red, Green, Blue의 3개 축으로 이루어진 3차원 공간(Cuboid)의 각 점에 대응한다. 8개의 자식 노드를 갖는 Octree는 3차원 공간을 8등분씩 균일하게 분할하는 데 최적화된 자료구조이므로 직관적으로 RGB 공간을 구조화를 할 수 있다.
• 메모리 및 계산 효율성 이미지에 존재하지 않는 색상 영역은 트리의 노드로 생성되지 않아서 256×256×256(=약 1,670만 개) 전체 색상 공간을 배열로 생성할 때 발생하는 메모리 낭비를  줄여준다.
• 빠른 탐색과 대표색 통합 비트 연산을 통해 픽셀의 RGB 값을 노드 인덱스로 빠르게 변환할 수 있다. 또한, 지정된 최대 색상 수를 초과할 경우 가장 깊은 단계의 자식 노드들을 부모 노드로 병합하는 과정이 간편해 색상 공간상 가까운 색상들을 효율적으로 병합할 수 있다.

1. 핵심 자료구조 (COctreeQuantizer::NODE)

Octree의 각 노드는 8개의 자식 노드(pChild[8])를 가질 수 있으며, 이는 RGB 각각의 Bit값 조합(0~7)에 대응한다.

• IsLeaf: 리프 노드 여부를 나타내며, 리프 노드에 최종 대표 색상을 저장
• PixelCount: 해당 노드(또는 하위 영역)에 속한 픽셀의 총개수
• RedSum, GreenSum, BlueSum: 픽셀들의 RGB 채널별 누적 합산값으로, 최종 팔레트 색상 계산(평균값)에 사용
• pNext: 축소 가능한 동일 깊이의 노드들을 단방향 연결 리스트로 관리하기 위한 포인터

2. 주요 처리 과정

• 트리 생성 및 색상 추가 (AddColor) 이미지의 각 픽셀 RGB 값을 탐색하며 트리를 내려갑니다. 비트 연산(rBit << 2 | gBit << 1 | bBit)으로 자식 노드의 인덱스를 결정하며, 리프 노드에 도달하면 픽셀 카운트와 RGB 누적값을 갱신
• 트리 축소 (ReduceTree) 생성된 리프 노드의 수(m_nLeafCount)가 목표 색상 수(m_MaxColors)를 초과하면, 가장 깊은 레벨의 노드부터 자식 노드들을 병합(Delete & Clear)하여 하나의 리프 노드로 통합
• 팔레트 생성 (GetPalette) 완성된 Octree의 리프 노드들을 재귀적으로 순회하며, 누적된 RGB 합을 픽셀 수로 나누어 평균 색상을 구한 뒤 최종 팔레트 Vector에 저장
• 픽셀 재매핑 (QuantizeColor) 원본 이미지의 각 픽셀을 Octree 탐색을 통해 가장 적절하게 양자화된 팔레트 인덱스로 변환

class COctreeQuantizer {
    struct NODE {
        bool IsLeaf;                    // TRUE if node has no children
        uint64_t  PixelCount;           // Number of pixels represented by this leaf
        uint64_t  RedSum;               // Sum of red components
        uint64_t  GreenSum;             // Sum of green components
        uint64_t  BlueSum;              // Sum of blue components
        int  Index;                     // Index of current node;
        struct NODE* pChild[8];    
        struct NODE* pNext;        
    };
    
protected:
    NODE	*m_pTree;
    int		m_nLeafCount;
    NODE	*m_pReducibleNodes[9];
    int		m_MaxColors;
    int		m_ColorBits;
public:
    COctreeQuantizer(int nMaxColors, int nColorBits);
    virtual ~COctreeQuantizer();
    std::vector<RGBQUAD> ProcessImage(const CRaster& raster);
    int QuantizeColor(BYTE r, BYTE g, BYTE b);
protected:
    std::vector<RGBQUAD> GetPalette();
    void AddColor(BYTE r, BYTE g, BYTE b);
    void* CreateNode(int nLevel);
    void ReduceTree();
private:
    void Reset();
    void DeleteTree();
    void DeleteSubtree(NODE* &pNode);
};
COctreeQuantizer::COctreeQuantizer(int nMaxColors, int nColorBits) {
    m_ColorBits  = nColorBits < 8 ? max(1, nColorBits) : 8;
    m_pTree      = NULL;
    m_nLeafCount = 0;
    for	(int i = 0; i <= m_ColorBits; i++) 
        m_pReducibleNodes[i] = NULL;

    m_MaxColors = max(1, nMaxColors);
}
COctreeQuantizer::~COctreeQuantizer() {
    DeleteTree();
}
void COctreeQuantizer::AddColor(BYTE r, BYTE g, BYTE b) {
    // 1. 루트 노드가 없으면 생성
    if (m_pTree == NULL)
        m_pTree = (NODE *)CreateNode(0);

    NODE* pNode = m_pTree;
    // 2. 루프를 통해 트리를 아래로 탐색
    for (int nLevel = 0; nLevel <= m_ColorBits; ++nLevel) {
        // 리프 노드에 도달했으면 RGB값 및 픽셀 수 갱신 후 종료
        if (pNode->IsLeaf) {
            pNode->PixelCount++;
            pNode->RedSum   += r;
            pNode->GreenSum += g;
            pNode->BlueSum  += b;
            return;
        }
        // 비트 연산으로 이동할 자식 노드 인덱스 계산
        int shift  = 7 - nLevel;
        BYTE currentMask = (0x80 >> nLevel);
        int nIndex = (((r & currentMask) >> shift) << 2) |
                     (((g & currentMask) >> shift) << 1) |
                      ((b & currentMask) >> shift);

        // 자식 노드가 없으면 다음 레벨(nLevel + 1) 노드로 새로 생성
        if (pNode->pChild[nIndex] == NULL)
            pNode->pChild[nIndex] = (NODE*)CreateNode(nLevel + 1);
        // 다음 레벨 자식 노드로 이동
        pNode = pNode->pChild[nIndex];
    }
}
void* COctreeQuantizer::CreateNode(int nLevel) {
    NODE* pNode = new NODE (); // 0으로 초기화;

    pNode->IsLeaf = (nLevel ==	m_ColorBits) ? true : false;
    if (pNode->IsLeaf) 
        m_nLeafCount++;
    else {
        pNode->pNext = m_pReducibleNodes[nLevel];
        m_pReducibleNodes[nLevel] = pNode;
    }
    return pNode;
}
void COctreeQuantizer::ReduceTree() {
    // 축소 가능한 노드가 존재하는 가장 깊은 레벨(i)을 탐색;
    int i;
    for	(i = m_ColorBits - 1; (i > 0) && (m_pReducibleNodes[i] == NULL); i--);
    
    // 해당 레벨의 연결 리스트에서 가장 최근에 추가된 노드 1개를 꺼냄;
    NODE* pNode	= m_pReducibleNodes[i];
    m_pReducibleNodes[i] = pNode->pNext;
    
    uint64_t RedSum = 0;
    uint64_t GreenSum = 0;
    uint64_t BlueSum = 0;
    int nChildren = 0;

    for	(int k = 0; k < 8; ++k)	{
        NODE* pChildNode = pNode->pChild[k];
        if (pChildNode) {
            RedSum            += pChildNode->RedSum;
            GreenSum          += pChildNode->GreenSum;
            BlueSum           += pChildNode->BlueSum;
            pNode->PixelCount += pChildNode->PixelCount;
            nChildren++;
            
            delete pChildNode; 
            pNode->pChild[k] = NULL;
        }
    }
    pNode->IsLeaf   = true;
    pNode->RedSum   = RedSum;
    pNode->GreenSum = GreenSum;
    pNode->BlueSum  = BlueSum;
    m_nLeafCount   -= (nChildren - 1);
}
void COctreeQuantizer::DeleteTree() {
    DeleteSubtree(m_pTree);
    m_pTree = NULL;
    m_nLeafCount = 0;
}
void COctreeQuantizer::DeleteSubtree(NODE* &pNode) {
    if (pNode == NULL) return;
    for (int i = 0; i < 8; ++i)
        if (pNode->pChild[i])
            DeleteSubtree(pNode->pChild[i]);

    delete pNode;
    pNode = NULL;
}
void COctreeQuantizer::Reset() {
    DeleteTree();
    for (int i = 0; i <= m_ColorBits; ++i)
        m_pReducibleNodes[i] = NULL;
}
// 최종적으로 leaf node에 대응하는 팔레트 컬러와 인덱스를 생성;
std::vector<RGBQUAD> COctreeQuantizer::GetPalette() {
    if (m_pTree == NULL) return std::vector<RGBQUAD> ();
    
    std::vector<RGBQUAD> Palette;
    Palette.reserve(m_MaxColors);
    
    int nIndex = 0;
    std::stack<NODE*> nodeStack;
    nodeStack.push(m_pTree);
    while (!nodeStack.empty()) {
        NODE* pCurrent = nodeStack.top();
        nodeStack.pop();

        // Leaf 노드인 경우 대표 색상 계산 후 팔레트에 추가;
        if (pCurrent->IsLeaf) {
            RGBQUAD rgba;
            rgba.rgbRed      = BYTE(pCurrent->RedSum   / pCurrent->PixelCount);
            rgba.rgbGreen    = BYTE(pCurrent->GreenSum / pCurrent->PixelCount);
            rgba.rgbBlue     = BYTE(pCurrent->BlueSum  / pCurrent->PixelCount);
            rgba.rgbReserved = 0;

            Palette.push_back(rgba);
            pCurrent->Index = nIndex++;
        } 
        // Leaf 노드가 아닌 경우 자식 노드들을 스택에 푸시
        else {
            // 역순(7->0)으로 푸시해야 순차 탐색(0->7) 순서와 일치;
            for (int i = 7; i >= 0; --i)
                if (pCurrent->pChild[i])
                    nodeStack.push(pCurrent->pChild[i]);
        }
    }
    return Palette;
}
int COctreeQuantizer::QuantizeColor(BYTE r, BYTE g, BYTE b) {
    // 주어진 (r, g, b) 컬러에 대응하는 팔레트 인덱스를 반환; 
    NODE* pNode = m_pTree;
    for (int nLevel = 0; nLevel <= m_ColorBits; ++nLevel) {
        if (pNode->IsLeaf) return pNode->Index;
        int shift = 7 - nLevel;
        BYTE currentMask = (0x80 >> nLevel);
        int nIndex = (((r & currentMask) >> shift) << 2) |
                     (((g & currentMask) >> shift) << 1) |
                      ((b & currentMask) >> shift);
        pNode = pNode->pChild[nIndex];
        if (!pNode) break;
    }
    return 0;
}
std::vector<RGBQUAD> COctreeQuantizer::ProcessImage(const CRaster& raster) {
    // 같은 객체를 재사용하는 경우 대비 reset;
    Reset();
    if (raster.IsEmpty()) return std::vector<RGBQUAD>();
    
    CSize sz = raster.GetSize();
    switch (raster.GetBPP()) {
    case 24: //	24-bit DIB
        for (int y = 0; y < sz.cy; y++) {
            BYTE *p = (BYTE *)raster.GetLinePtr(y) ;
            for	(int x = 0; x < sz.cx; x++, p += 3)	{
                AddColor(p[2], p[1], p[0]);
                while (m_nLeafCount > m_MaxColors) 
                    ReduceTree();
            }
        }
        return GetPalette();       
    default: //	Unrecognized color format
        return std::vector<RGBQUAD>();
    }
    return std::vector<RGBQUAD>();
}
CRaster OctreeQuantizerTest(CRaster& raster) {
    const int nColors = 128;
    COctreeQuantizer oq(nColors, 8) ;
    std::vector<RGBQUAD> Palette = oq.ProcessImage(raster);
    CSize sz = raster.GetSize();
    // 양자화된 컬러를 가지는 24비트 이미지 생성;
    CRaster out;
    out.SetDimensions(sz, 24);
    for (int y = 0; y < sz.cy; y++) {
        BYTE *p = (BYTE*)raster.GetLinePtr(y);
        BYTE *q = (BYTE*)out.GetLinePtr(y);
        for (int x = 0 ; x < sz.cx; x++, p += 3) {
            int idx = oq.QuantizeColor(p[2], p[1], p[0]);
            *q++ = Palette[idx].rgbBlue ;
            *q++ = Palette[idx].rgbGreen ;
            *q++ = Palette[idx].rgbRed ;
        }
    }
    return out;
}