2010年08月20日

メディアンカット法による画像の減色



DIBのビット深度の変更」でのシステムパレットを使った減色処理では、使用できる色が固定されるため、どうしても不自然な色の画像になります。そこで今回はメディアンカット法を使った減色手法を紹介します。尚メディアンカット法での減色の手順は以下の通りです。

  1. 24ビットDIBRGBピクセルからYUVテーブルを作成する。
  2. メディアンカット法で色を分ける。
  3. 減色カラーテーブルを作成する。
  4. カラーテーブルYUV値をRGBに変換する。
  5. BITMAPINFO構造体を作成し、空のDIBを作成する。
  6. ピクセルデータDIBにコピーする。




ビットマップバイト幅の算出マクロです。

//ビットマップバイト幅の算出マクロ
#ifndef WIDTHBYTES
#define WIDTHBYTES(bits) (((bits)+31)/32*4)
#endif//WIDTHBYTES


YUV平均値を求める際に使用する構造体です。

//YUV平均値を求める際の作業テーブル
typedef struct tagAVGYUV{
double y;
double u;
double v;
int cnt;
}AVGYUV,*PAVGYUV;


YUVテーブルの作成に使用する構造体です。

//RGB変換で使用
typedef struct tagYUV{
float y;
float u;
float v;
int no;
} YUV,*PYUV;


24ビットDIBから指定色数までメディアンカット減色したDIBを作成します。

//メディアンカット減色DIBの作成
HBITMAP __stdcall _MedianCut(HBITMAP hbm24bit,UINT cEntries)
{
//減色する色数が512以上2以下ならFALSEを返して終了する。
if ((cEntries>512)||(cEntries<2)) return FALSE; //cEntriesは減色する色数
//DIBSECTION構造体の取得

DIBSECTION ds={0};
if (!::GetObject(hbm24bit,sizeof(DIBSECTION),&ds)) //hbm24bitは減色するDIBのハンドル
return FALSE;

//DIBでないか、ビット深度が24ビットでなければFALSEを返して終了する。
if ((ds.dsBmih.biSize!=sizeof(BITMAPINFOHEADER))||
(ds.dsBmih.biBitCount!=24)) return FALSE;

//パレット色数からビットカウントを取得する
UINT nBpp=24;
if (cEntries<=2) nBpp=1; //cEntriesは減色する色数
else if (cEntries<=16) nBpp=4;
else if (cEntries<=256) nBpp=8;

UINT width =ds.dsBmih.biWidth; //画像幅
UINT height=abs(ds.dsBmih.biHeight); //画像高さ

//YUVテーブル作成
DWORD dwSizeDimension=width*height; //YUVテーブルのサイズ
YUV* pYUV=new YUV[dwSizeDimension]; //YUVテーブル領域確保
int iYUV=0;
RGBQUAD rgb;
for(UINT y=0;y<height;y++){
//y行の一番左端のピクセルへのポインタの算出
PBYTE src=(PBYTE)ds.dsBm.bmBits+y*ds.dsBm.bmWidthBytes;
for(UINT x=0;x<width;x++){
//DIBのピクセルデータを取り出す
rgb.rgbBlue =*src++;
rgb.rgbGreen=*src++;
rgb.rgbRed =*src++;
//RGBからYUVへ変換する
pYUV[iYUV].y= 0.29891f*(float)(rgb.rgbRed)+0.58661f*(float)(rgb.rgbGreen)+
0.11448f*(float)(rgb.rgbBlue);
pYUV[iYUV].u=-0.16874f*(float)(rgb.rgbRed)-0.33126f*(float)(rgb.rgbGreen)+
0.50000f*(float)(rgb.rgbBlue);
pYUV[iYUV].v= 0.50000f*(float)(rgb.rgbRed)-0.41869f*(float)(rgb.rgbGreen)-
0.08131f*(float)(rgb.rgbBlue);
pYUV[iYUV].no = 0;
iYUV++;
}
}

//入力色数から2の乗数を算出します。
int nShift=cEntries>>1;
int divBit=0;
while(nShift>0){
nShift>>=1;
divBit++;
}
//色を分けるメディアンカット減色関数を呼び出します。
_MedianCut(pYUV,dwSizeDimension,0,divBit);

//減色カラーテーブルを作成する。
int nColors=(nBpp>8)?cEntries:(cEntries/2)*2+(cEntries%2)*2;
RGBQUAD* pColorTable=new RGBQUAD[nColors];
::ZeroMemory(pColorTable,sizeof(RGBQUAD)*nColors);
AVGYUV* pAvgYUV=new AVGYUV[nColors];
::ZeroMemory(pAvgYUV,sizeof(AVGYUV)*nColors);

for(UINT y=0;y<height;y++){
for(UINT x=0;x<width;x++){
iYUV=y*width+x;
pAvgYUV[pYUV[iYUV].no].y+=(double)pYUV[iYUV].y;
pAvgYUV[pYUV[iYUV].no].u+=(double)pYUV[iYUV].u;
pAvgYUV[pYUV[iYUV].no].v+=(double)pYUV[iYUV].v;
pAvgYUV[pYUV[iYUV].no].cnt++;
}
}

//カラーテーブルのYUV値をRGBに変換する。
for(int i=0;i<nColors;i++){
if (pAvgYUV[i].cnt>0){
pAvgYUV[i].y=pAvgYUV[i].y/(double)pAvgYUV[i].cnt;
pAvgYUV[i].u=pAvgYUV[i].u/(double)pAvgYUV[i].cnt;
pAvgYUV[i].v=pAvgYUV[i].v/(double)pAvgYUV[i].cnt;

//赤成分のYUV->RGB変換
double red=pAvgYUV[i].y+1.40200*pAvgYUV[i].v;
red+=0.49;
if (red<0.0) red=0.0;
if (red>255.0) red=255.0;
pColorTable[i].rgbRed=(BYTE)red;

//緑成分のYUV->RGB変換
double green=pAvgYUV[i].y-0.34414*pAvgYUV[i].u-0.71414*pAvgYUV[i].v;
green+=0.49;
if (green<0.0) green=0.0;
if (green>255.0) green=255.0;
pColorTable[i].rgbGreen=(BYTE)green;

//青成分のYUV->RGB変換
double blue=pAvgYUV[i].y+1.77200*pAvgYUV[i].u;
blue+=0.49;
if (blue<0.0) blue=0.0;
if (blue>255.0) blue=255.0;
pColorTable[i].rgbBlue=(BYTE)blue;
}
}
delete[] pAvgYUV;

//BITMAPINFO構造体を作成します。
UINT nSizeOfColorTable=(nColors>256)? 0:sizeof(RGBQUAD)*nColors;
UINT nSizeOfBitmapInfo=sizeof(BITMAPINFOHEADER)+nSizeOfColorTable;
BITMAPINFO* pBmpInfo=(BITMAPINFO*)(new BYTE[nSizeOfBitmapInfo]);
::ZeroMemory(pBmpInfo,nSizeOfBitmapInfo);
::CopyMemory(&pBmpInfo->bmiHeader,&ds.dsBmih,sizeof(BITMAPINFOHEADER));
pBmpInfo->bmiHeader.biBitCount=nBpp;
DWORD dwBytesOfLine=WIDTHBYTES(width*nBpp);
pBmpInfo->bmiHeader.biSizeImage=dwBytesOfLine*height;
pBmpInfo->bmiHeader.biCompression=BI_RGB;
pBmpInfo->bmiHeader.biClrUsed=(nColors<256)? nColors:0;

//減色する色数が256以下ならパレットDIBなので、
//カラーテーブルをBITMAPINFO構造体のカラーテーブルにコピーします。

if (nColors<=256)
::CopyMemory(&pBmpInfo->bmiColors,pColorTable,nSizeOfColorTable);

//空のDIBを作成します。
LPVOID pvBits;
HBITMAP hbmDst=::CreateDIBSection(0,pBmpInfo,DIB_RGB_COLORS,&pvBits,0,0);
delete[]pColorTable;
delete[]pBmpInfo;
BITMAP bm;
//DIBの作成に失敗したら、YUVテーブルを削除してから
//FALSEを返して終了します。

if (!::GetObject(hbmDst,sizeof(BITMAP),&bm)){
delete[] pYUV;
return FALSE;
}

//ピクセルデータをDIBに格納します。
switch(nBpp){
case 24: //24ビットDIB
for(UINT y=0;y<height;y++){
PBYTE dst=(PBYTE)bm.bmBits+y*bm.bmWidthBytes;
for(UINT x=0;x<width;x++){
iYUV=y*width+x;
int index=pYUV[iYUV].no;
*dst++=pColorTable[index].rgbBlue;
*dst++=pColorTable[index].rgbGreen;
*dst++=pColorTable[index].rgbRed;
}
}
break;

case 8: //8ビットDIB
for(UINT y=0;y<height;y++){
PBYTE dst=(PBYTE)bm.bmBits+y*bm.bmWidthBytes;
for(UINT x=0;x<width;x++){
iYUV=y*width+x;
int index=pYUV[iYUV].no;
*dst++=index;
}
}
break;

case 4: //4ビットDIB
for(UINT y=0;y<height;y++){
PBYTE dst=(PBYTE)bm.bmBits+y*bm.bmWidthBytes;
for(UINT x=0;x<width;x++){
iYUV=y*width+x;
int index=pYUV[iYUV].no;
if (x%2==0) *dst=index<<4;
else *dst++|=index;
}
}
break;

case 1: //モノクロDIB
for(UINT y=0;y<height;y++){
PBYTE dst=(PBYTE)bm.bmBits+y*bm.bmWidthBytes;
for(UINT x=0;x<width;x++){
iYUV=y*width+x;
int index=pYUV[iYUV].no;
if (x%8==0) *dst=(index&1)<<7;
else *dst|=(index&1)<<(7-(x%8));
if (x%8==7) dst++;
}
}
break;

}
delete[] pYUV;
return hbmDst;
}


色を分けるメディアンカット減色関数です。

//メディアンカット減色
void __stdcall _MedianCut(YUV* tblYUV,int maxTbl,int base,int divBit)
{
if (tblYUV==NULL) return;
if (divBit<1) return;

//作業する変数の数を数える
int idx=0;
float minY,minU,minV;
float maxY,maxU,maxV;
float avgY,avgU,avgV;
double allY,allU,allV;

for (int i=0;i<maxTbl;i++){
if (tblYUV[i].no==base){
if (idx==0){ //初めての値の入力ならば
allY=minY=maxY=avgY=tblYUV[i].y;
allU=minU=maxU=avgU=tblYUV[i].u;
allV=minV=maxV=avgV=tblYUV[i].v;
}
else{
if (tblYUV[i].y<=minY) minY=tblYUV[i].y;
if (tblYUV[i].y>=maxY) maxY=tblYUV[i].y;
if (tblYUV[i].u<=minU) minU=tblYUV[i].u;
if (tblYUV[i].u>=maxU) maxU=tblYUV[i].u;
if (tblYUV[i].v<=minV) minV=tblYUV[i].v;
if (tblYUV[i].v>=maxV) maxV=tblYUV[i].v;
allY+=(double)tblYUV[i].y;
allU+=(double)tblYUV[i].u;
allV+=(double)tblYUV[i].v;
}
idx++;
}
}
if (idx==0) return; //作業する変数がないので終了

int a=base;
int b=base+(1<<(divBit-1));

avgY=(float)(allY/idx);
avgU=(float)(allU/idx);
avgV=(float)(allV/idx);

//メディアンカット法を行うので、幅が最大になる要素を探す。
int swData;
if ((maxY-minY)>(maxU-minU))
swData=((maxY-minY)>(maxV-minV))?0:2;
else
swData=((maxU-minU)>(maxV-minV))?1:2;

//平均値で色の切り分け
switch(swData){
case 0: // Y
for (int i=0;i<maxTbl;i++)
if (tblYUV[i].no==base)
tblYUV[i].no=(tblYUV[i].y<avgY)?a:b;
break;
case 1: // U
for (int i=0;i<maxTbl;i++)
if (tblYUV[i].no==base)
tblYUV[i].no=(tblYUV[i].u<avgU)?a:b;
break;
case 2: // V
for (int i=0;i<maxTbl;i++)
if (tblYUV[i].no==base)
tblYUV[i].no=(tblYUV[i].v<avgV)?a:b;
break;
}

//再起する
_MedianCut(tblYUV,maxTbl,a,divBit-1);
_MedianCut(tblYUV,maxTbl,b,divBit-1);
}


hbmDstの内容が、メディアンカット法で減色して作成したDIBのハンドルになります。

サンプルプログラム(VisualC++net2003ソリューション)DIBFileTest06.zip

上記のzipファイルをダウンロードしてからWinRAR等で解凍し、DIBFileTest06フォルダー内にある「DIBFileTest.sln」を開きます。「F5」キーを押すと、ビルド確認のダイヤログが表示されるので「Yes」を選択してソリューションをビルドします。



ビルドが終わると直ちにプログラムが自動起動してウィンドウが表示されます。ウィンドウのメニューで「ファイル」/「開く」を選択して、「ファイルを開く」ダイヤログを表示させ、resフォルダー内の「GP500cc24bit.bmp」を読み込みます。



24ビットフルカラー画像が表示されます。



画像が表示されたところで「編集」/「ビット深度の変更」で「ビット深度の変更」ダイヤログを表示させ、「ビット深度」コンボボックスで8ビットを選択し、「メディアンカット」チェックボックスにチェックを入れて、「OK」ボタンを押します。



256色パレットDIBにメディアンカット法で減色した画像が表示されます。



DIBのビット深度の変更」で作成した画像と比較して、色品質が向上しているか確認してください。



次に「Ctrl+Z」で24ビットフルカラー画像に戻しておいてから、再び「編集」/ビット深度の変更」で「ビット深度の変更」ダイヤログを表示させ、「ビット深度」コンボボックスで今度は4ビットを選択し、「メディアンカット」チェックボックスがチェックされていることを確認してから、「OK」ボタンを押します。



16色パレットDIBに減色した画像が表示されます。



DIBのビット深度の変更」で作成した画像と比較して、色品質が向上しているか確認してください。



最後に「Ctrl+Z」で24ビットフルカラー画像に戻しておいてから、再び「編集」/ビット深度の変更」で「ビット深度の変更」ダイヤログを表示させ、「ビット深度」コンボボックスで今度は1ビットを選択し、「メディアンカット」チェックボックスがチェックされていることを確認してから、「OK」ボタンを押します。



モノクロDIBに減色した画像が表示されます。



DIBのビット深度の変更」で作成した画像と比較して、色品質が向上しているか確認してください。




posted by ひろし at 03:07| Comment(0) | DIBファイルフォーマット | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。