スタッフBLOG

おはようございます。本日の当番、プログラマのM.L.Kです（LはLiteralのLです。Literal&Figural!）。

メディアンカット法の実装編です。
プログラミングに興味がないキミを、淋しい思いさせちゃってゴメン。
これを機に、プログラミングに興味を持ってくれると、嬉しいナ。

さて、今回はソースコードを載せる都合上、スペースが余りありません。
余談は省いて、さっさと本編に入ります。

↓以下、“Ｃ＋＋で作るメディアンカット法”です。

#define NUM_PALETTE　　 (256)　　//減色数
#define NUM_ELEMENT　　 (3)　　　//ＲＧＢの３つ
#define NUM_GRADIATION　(256)　　//各チャンネル８bitsなので２５６階調

//色の分布を分割するための情報を格納する構造体
struct UNIT_ITEM
{
　　union
　　{
　　　　unsigned int nColor;
　　　　unsigned char aucElement[4];
　　};
　　int iTargetElement; //分割対象チャンネル
　　int iDifference;　　//分割対象チャンネルでの最大値と最小値の差
　　int iMedian;　　　　//分割対象チャンネルの中央値
　　int iMax;　　　　　 //分割対象チャンネルでの最大値
　　int iTop;　　　　　 //並べ替え用配列上の先頭位置
　　int iBottom;　　　　//同上の末尾位置
};

//統計量の算出関数（最大値と最小値の差、及び中央値を求める）
//pItem　　 ：分割情報を格納する変数のポインタ
//pSrcImage ：元イメージのポインタ
//pIndecies ：並べ替え用配列のポインタ
void CalcStats( UNIT_ITEM* pItem, unsigned int* pSrcImage, int* pIndecies)
{
　　int aiFrequency[NUM_GRADIATION];　　//度数カウント用の配列

　　int iHalf = (pItem->iBottom - pItem->iTop) >> 1;

　　pItem->iDifference = 0;
　　for( int i = 0; i < NUM_ELEMENT; i++)
　　{
　　　　//各チャンネル０～２５５のそれぞれの値がいくつあるかを数える
　　　　//ついでに、そのチャンネルでの最小値と最大値も求める
　　　　memset( aiFrequency, 0, sizeof(aiFrequency));
　　　　int iMin = NUM_GRADIATION;
　　　　int iMax = -1;
　　　　for( int j = pItem->iTop; j <= pItem->iBottom; j++)
　　　　{
　　　　　　int iIndex = pIndecies[j];
　　　　　　unsigned char* pElement = (unsigned char*)&pSrcImage[iIndex];
　　　　　　aiFrequency[pElement[i]]++;
　　　　　　if( (int)pElement[i] < iMin ) iMin = (int)pElement[i];
　　　　　　if( (int)pElement[i] > iMax ) iMax = (int)pElement[i];
　　　　}

　　　　//中央値（メディアン）を求める
　　　　//半分の位置（iHalf）を含んだ値を中央値とする
　　　　int iMedian = -1;
　　　　int iSum = 0;
　　　　for(int j = 0; j < NUM_GRADIATION; j++)
　　　　{
　　　　　　iSum += aiFrequency[j];
　　　　　　if( iSum > iHalf )
　　　　　　{
　　　　　　　　iMedian = j;
　　　　　　　　break;
　　　　　　}
　　　　}

　　　　//求めた中央値を各チャンネルの値として
　　　　//この分割での代表色を求めておく
　　　　pItem->aucElement[i] = (unsigned char)iMedian;

　　　　//最大値と最小値の差を算出し、
　　　　//各チャンネルで最も差の大きいものを分割対象のチャンネルとする
　　　　int iDifference = iMax - iMin;
　　　　if( iDifference > pItem->iDifference)
　　　　{
　　　　　　pItem->iTargetElement = i;
　　　　　　pItem->iMedian = iMedian;
　　　　　　pItem->iMax = iMax;
　　　　　　pItem->iDifference = iDifference;
　　　　}
　　}
}

//分割情報をその中央値で更に分割する関数
//pNewItem　：新しい分割情報を格納する変数のポインタ
//pSrcItem　：元の分布情報を格納した変数のポインタ
//pSrcImage ：元イメージのポインタ
//pIndecies ：並べ替え用配列のポインタ
void Divide( UNIT_ITEM* pNewItem, UNIT_ITEM* pSrcItem,
　　　　　　 unsigned int* pSrcImage, int* pIndecies)
{
　　int iTop = pSrcItem->iTop;
　　int iBottom = pSrcItem->iBottom;
　　int iTarget = pSrcItem->iTargetElement;
　　int iMedian = pSrcItem->iMedian;
　　if( iMedian == pSrcItem->iMax ) iMedian--;

　　//中央値以下の値はそのままの位置で、
　　//中央値よりも大きな値は、末尾側へ移動させることで、
　　//中央値を境に大小で２つに分ける
　　while( iTop < iBottom )
　　{
　　　　int iIndex = pIndecies[iTop];
　　　　unsigned char* pElement = (unsigned char*)&pSrcImage[iIndex];

　　　　if( pElement[iTarget] > iMedian )
　　　　{
　　　　　　//中央値以上なら、末尾側の値と入れ替える
　　　　　　pIndecies[iTop] = pIndecies[iBottom];
　　　　　　pIndecies[iBottom] = iIndex;
　　　　　　iBottom--;　　//末尾の位置を更新する
　　　　}
　　　　else iTop++;　　//中央値以下なら次の値へ
　　}

　　//中央値よりも大きな値のグループを新しい分割情報として設定
　　pNewItem->iTop = iBottom + 1;
　　pNewItem->iBottom = pSrcItem->iBottom;

　　//元の分割情報を中央値以下のグループとして更新
　　pSrcItem->iBottom = iBottom;
}

//メディアンカット法関数
//ppDstImage　　：減色後のイメージデータを格納するポインタ変数のポインタ
//ppDstPalette　：減色後のパレットデータを格納するポインタ変数のポインタ
//pSrcImage　　 ：元イメージのデータ（32bits色のイメージ）
//iPixels　　　 ：元イメージに含まれる画素数
void MedianCut( unsigned char** ppDstImage, unsigned int** ppDstPalette,
　　　　　　　　unsigned int* pSrcImage, int iPixels)
{
　　//分割＆並べ替えを行うための配列
　　int* pIndecies = new int[iPixels];
　　for( int i = 0; i < iPixels; i++) pIndecies[i] = i;

　　//分割情報格納用の変数を初期化
　　UNIT_ITEM aItem[NUM_PALETTE];
　　memset( aItem, 0, sizeof(aItem));

　　//全ての画素を含む分割情報を最初の１つめとして用意する
　　int iCountItem = 0;
　　aItem[iCountItem].iTop = 0;
　　aItem[iCountItem].iBottom = iPixels - 1;
　　CalcStats( &aItem[iCountItem], pSrcImage, pIndecies);
　　iCountItem++;

　　while( iCountItem < NUM_PALETTE )
　　{
　　　　//既に存在している分割情報の中から最も差の値が大きなものを
　　　　//新しい分割の対象として選び出す
　　　　int iMax = INT_MIN;
　　　　int iIndexMaxDifference = 0;
　　　　for( int i = 0; i < iCountItem; i++)
　　　　{
　　　　　　if( aItem[i].iDifference > iMax)
　　　　　　{
　　　　　　　　iMax = aItem[i].iDifference;
　　　　　　　　iIndexMaxDifference = i;
　　　　　　}
　　　　}

　　　　//選んだものを中央値で分割する
　　　　Divide( &aItem[iCountItem], &aItem[iIndexMaxDifference],
　　　　　　　　pSrcImage, pIndecies);

　　　　//分割されたそれぞれの統計量を算出
　　　　CalcStats( &aItem[iCountItem], pSrcImage, pIndecies);
　　　　CalcStats( &aItem[iIndexMaxDifference], pSrcImage, pIndecies);
　　　　iCountItem++;
　　}

　　//減色後のデータをパレットとインデックスデータの形式で用意する
　　*ppDstPalette = new unsigned int[NUM_PALETTE];
　　*ppDstImage = new unsigned char[iPixels];

　　for( int i = 0; i < NUM_PALETTE; i++)
　　{
　　　　(*ppDstPalette)[i] = aItem[i].nColor;
　　　　for( int j = aItem[i].iTop; j <= aItem[i].iBottom; j++)
　　　　{
　　　　　　(*ppDstImage)[pIndecies[j]] = (unsigned char)i;
　　　　}
　　}

　　delete[] pIndecies;
}

↑以上、ここまで。

レイアウトの都合上、インデント等のTab文字は、
すべて全角スペースに置き換わっています。
コピペして試すときは、置換しないと、コンパイラに叱られますデス。

ちなみに、NULLポインタチェック等の、
メディアンカット法の処理からすると本質的ではない記述は省かれています。

ポインタ操作を駆使すれば、もっと処理を効率化できますが、
そのあたりは全て配列による表現にして、処理の過程を追い易くしました。

メディアンカット法自体は、
僅か２００行足らずで記述できてしまうアルゴリズムなのですが、
これをスタート地点にして、様々な工夫を加えることで、減色のクオリティを
向上させることができます（分割するチャンネルの選択や、代表色の生成など）。

そこに頭を捻ることが減色処理の醍醐味です。

また次の当番の際には、今回のソースコードを足がかりにして、
そのあたりの工夫について具体的なお話ができればなぁ、と思います。