特集記事

画像からASCIIアートを自動生成する

画像に最も近い文字を判定する方法

ひよこ[著]

更新日: 2006/05/26
公開日: 2006/04/01

ポスト

ダウンロードサンプルファイル (140.2 KB)

切り取った画像に最も近い文字を選ぶ

　原画像の一部を切り取った分割画像と、文字画像それぞれの特徴を抽出し、これが最も近い文字を選びますが、その前に、白黒の2値画像である文字画像と比較するために分割画像も2値化しなければなりません。

画像をグレースケール化する

　さらにその前に、2値化するためには画像がグレースケールでなければなりません。グレースケールにもいろいろありますが、人間の視覚特性を考慮した輝度に変換すれば良いでしょう。RGBから輝度に変換する式は次の通りです。

輝度 = 0.298912*R + 0.586611*G + 0.114477*B

// カラー画像をグレースケール化する
void ColorToGray(BmpIO *pColor)
{
    if(pColor==NULL) return;

    BYTE *p=pColor->GetPixel();
    BYTE by=pColor->GetBitCount()/8;
    int w=(int)pColor->GetWidth();
    DWORD l=pColor->GetLength();
    int h=(int)pColor->GetHeight();

    if(p==NULL) return;

    int x,y,xb,yl;
    BYTE r,g,b,gray;
    for(y=0;y<h;y++)
    {
        yl=y*l;
        for(x=0;x<w;x++)
        {
            xb=x*by;
            b=p[xb+yl]; g=p[xb+1+yl]; r=p[xb+2+yl];
            // 輝度
            gray=(BYTE)(0.298912*r + 0.586611*g + 0.114477*b + 0.5);
            p[xb  +yl]=gray;
            p[xb+1+yl]=gray;
            p[xb+2+yl]=gray;
        }
    }
}

画像を2値化する

　グレースケール画像から2値画像を作成する最も簡単な方法は、ある値を閾値として閾値未満の値を0に、閾値以上の値を255にする閾値法です。最も良好な結果が得られた場合、綺麗に白と黒とに分かれますが、一般的にかなり難しい方法です。また階調も失われるため、アスキーアートにしたときに白または黒に対応する文字として同じ文字が選ばれやすく面白くない、という問題も発生します。

　階調を残しつつ2値化する手法として、新聞などに用いられている誤差拡散法があります。誤差拡散法はディザ法の一種で、誤差拡散ディザ法、平均誤差最小ディザ法とも言います。色の濃さによって点の密度が変化するため、擬似的に階調を表現できます。

　誤差拡散法は、「閾値を128に固定し、閾値未満なら0に、閾値以上なら255にする」までは閾値法と同じなのですが、このとき失われた差分値を周辺の画素に配分し足し込みます。ここで差分値を配分する割合が重要になってきますが、良好な結果が得られるものはほとんど見つかっておらず、Floyd & Steinberg型とJarvis, Judice & Ninke型が有名です。

Floyd & Steinberg型

Jarvis, Judice ＆ Ninke型

適用結果の比較

　広い範囲に誤差（差分値）を拡散するJarvis, Judice & Ninke型の方が良好な結果を期待できますが、処理速度などの理由からFloyd & Steinberg型の方がよく使われます。本稿でもFloyd & Steinberg型を使います。Floyd & Steinberg型において参照画素が100の場合、100-0=100を右、左下、下、右下の画素に配分し足し込みます。参照画素が200の場合、200-255=-55を配分し足し込みます。

// グレースケール画像を2値化する誤差拡散法
void GrayToMonoDither(BmpIO *pGray)
{
    if(pGray==NULL) return;

    BYTE *p=pGray->GetPixel();
    BYTE b=pGray->GetBitCount()/8;
    int w=(int)pGray->GetWidth();
    DWORD l=pGray->GetLength();
    int h=(int)pGray->GetHeight();

    if(p==NULL) return;

    // BYTE 型だとオーバーフローの危険があるため double 型にコピーする
    HANDLE hHeep=GetProcessHeap();
    double *pxl=(double*)HeapAlloc(hHeep,
        HEAP_ZERO_MEMORY, sizeof(double)*w*h);

    int x,y,yl,yw;
    for(y=0;y<h;y++)
    {
        yw=y*w; yl=y*l;
        for(x=0;x<w;x++)
        {
            pxl[x+yw]=p[x*b+yl];
        }
    }

    int xb;
    double d;
    for(y=0;y<h;y++)
    {
        yw=y*w; yl=y*l;
        for(x=0;x<w;x++)
        {
            xb=x*b;
            d=pxl[x+yw];

            if(d<0x80)
            {
                p[xb+yl]=0; p[xb+1+yl]=0; p[xb+2+yl]=0;
            }
            else
            {
                p[xb+yl]=255; p[xb+1+yl]=255; p[xb+2+yl]=255;
                d-=255;
            }

            if(d==0) continue;          // 誤差なし

            // Floyd & Steinberg 型
            if(x+1<w) pxl[x+1+yw] += d*7.0/16.0;
            if(y+1<h)
            {
                if(x-1>=0) pxl[x-1+(y+1)*w] += d*3.0/16.0;
                       pxl[x  +(y+1)*w] += d*5.0/16.0;
                if(x+1<w)  pxl[x+1+(y+1)*w] += d*1.0/16.0;
            }

            // Jarvis , Judice & Ninke 型
            //if(x+1<w) pxl[x+1+yw] += d*7.0/48.0;
            //if(x+2<w) pxl[x+2+yw] += d*5.0/48.0;
            //if(y+1<h)
            //{
            //      if(x-2>=0) pxl[x-2+(y+1)*w] += d*3.0/48.0;
            //      if(x-1>=0) pxl[x-1+(y+1)*w] += d*5.0/48.0;
            //         pxl[x  +(y+1)*w] += d*7.0/48.0;
            //      if(x+1<w)  pxl[x+1+(y+1)*w] += d*5.0/48.0;
            //      if(x+2<w)  pxl[x+2+(y+1)*w] += d*3.0/48.0;
            //}
            //if(y+2<h)
            //{
            //      if(x-2>=0) pxl[x-2+(y+2)*w] += d*1.0/48.0;
            //      if(x-1>=0) pxl[x-1+(y+2)*w] += d*3.0/48.0;
            //         pxl[x  +(y+2)*w] += d*5.0/48.0;
            //      if(x+1<w)  pxl[x+1+(y+2)*w] += d*3.0/48.0;
            //      if(x+2<w)  pxl[x+2+(y+2)*w] += d*1.0/48.0;
            //}
        }
    }

    HeapFree(hHeep,0,pxl);
}

画像の特徴を抽出して一致度を求める

　これで分割画像が2値化され、文字画像と比較するための準備ができました。問題はどうやって比較するかです。単純に一画素ずつ全画素について比較するのが最も正確なのですが、大量の文字画像と比較する必要がある今回のような場合には時間が掛かりすぎます。というわけで正確さでは劣りますが、高速に比較する方法として射影ヒストグラムを用いる方法を紹介します。

　「射影ヒストグラム」とは、ある方向について、その列の黒画素の数を「頻度」、その列に直行する方向を「軸」とするヒストグラムです。例としてiとkについて見ていきましょう。射影ヒストグラムの方向を横と縦に決め、横および縦の各列について黒画素の数を調べます。なお横および縦の長さは既知なので、黒画素の数がわかれば白画素の数も分かります。

　これを横方向の射影ヒストグラムとして表示すれば次のようになります。

　同様に縦方向の射影ヒストグラムとして表示すれば次のようになります。

　次に、横および縦の射影ヒストグラムを用いて画像の一致度を比較する方法を紹介します。射影ヒストグラムは黒画素の数を示しているので、まずは黒画素の一致度を求めます。黒画素の一致度は、射影ヒストグラムの頻度の小さい方として求められます。2つの射影ヒストグラムを重ねたときに、一致しているのは頻度が小さい部分ですね。白画素の一致度も同様に求められます。そしてこれらをヒストグラム全体について求め、合計した値が画像の一致度になります。

　なお、逆転の発想で不一致度を求め、横または縦の長さから引けば黒および白画素の合計一致度が一発で求められます。不一致度は、黒画素の数の大きい方から小さい方を引いた値として求められます。2つの射影ヒストグラムを重ねたときに、出っ張っている部分のもう一方は必ず違う色となるからですね。

　以上の方法によりiとkとを比較すると、横および縦の各列の一致度は次のようになり、これらを合計した値32を全画素数の2倍である50で割った値0.64が画像の一致度です。

黒および白画素の合計一致度

　射影ヒストグラムに変換した段階でいくらか情報が失われるため、一見ルーズな比較と思われるかもしれませんが、横および縦の両方向から比較するため、高速であるという利点の引き替えと考えれば妥当な精度が得られます。どの程度、高速になるかは画像サイズに比例しますが、10*10画素の場合は(10*10)/(10*2)=5倍高速になります。20*20画素の場合は(20*20)/(20*2)=10倍高速になります。

// ビットマップ解析
static void GetCharacteristic(DWORD yoko[],DWORD tate[],BmpIO *pMono)
{
    if(yoko==NULL || tate==NULL || pMono==NULL) return;

    BYTE *p=pMono->GetPixel();
    BYTE b=pMono->GetBitCount()/8;
    int w=(int)pMono->GetWidth();
    DWORD l=pMono->GetLength();
    int h=(int)pMono->GetHeight();

    if(p==NULL) return;

    ZeroMemory(yoko,sizeof(DWORD)*h);
    ZeroMemory(tate,sizeof(DWORD)*w);

    int x,y;
    for(y=0;y<h;y++)
    {
        for(x=0;x<w;x++)
        {
            if(p[x*b+y*l]==0)       // 黒画素
            {
                yoko[y]++; tate[x]++;
            }
        }
    }
}

// 解析情報の一致度を取得
static double GetAgree(const DWORD yoko1[],const DWORD tate1[],
               const DWORD yoko2[],const DWORD tate2[],
               int w,int h)
{
    if(yoko1==NULL || tate1==NULL || yoko2==NULL || tate2==NULL) return 0;

    DWORD dif,y_agree=0,t_agree=0;

    for(int y=0;y<h;y++)
    {
        dif = (yoko1[y]<yoko2[y])?
            yoko2[y]-yoko1[y] : yoko1[y]-yoko2[y];
        y_agree += w-dif;           // 横の一致度
    }
    for(int x=0;x<w;x++)
    {
        dif = (tate1[x]<tate2[x])?
            tate2[x]-tate1[x] : tate1[x]-tate2[x];
        t_agree += h-dif;           // 縦の一致度
    }

    return (double)(y_agree+t_agree)/(w*h*2);
}

画像を文字に変換する

　以上の関数を呼び出し、画像を最適な文字に変換するプログラムは次のようになります。

　アスキーアートに用いる文字はASCII文字の他にJISコードに採用されている半角カナ文字なども含めることにしました。JISコード表より、その値の範囲はJIS_CODEに定義したようになっていることが分かります。また全文字について実際に出力した結果は「charcode.txt」を見てください（ダウンロード後にメモ帳で開いてください）。

JISコード表

#define JIS_CODE(c) ( (c>=0x20 && c<=0x7e) || (c>=0xa1 && c<=0xdf) )

　CHARINFO構造体は、文字情報を格納するためのものです。詳細や、いつ格納するかについては後述します。

// ビットマップを文字に変換
static int BmpToAscii(BmpIO *pMono,const CHARINFO ci[256])
{
    if(pMono==NULL || ci==NULL) return 0;

    DWORD w=pMono->GetWidth();
    DWORD h=pMono->GetHeight();

    HANDLE hHeap=GetProcessHeap();
    DWORD *x_yoko=(DWORD*)HeapAlloc(
        hHeap,HEAP_ZERO_MEMORY,sizeof(DWORD)*h);
    DWORD *y_tate=(DWORD*)HeapAlloc(
        hHeap,HEAP_ZERO_MEMORY,sizeof(DWORD)*w);

    GetCharacteristic(x_yoko,y_tate,pMono);  // ビットマップ解析

    double agree,max_agree=0;
    int max_c=0x20;

    for(int c=0;c<256;c++)
    {
        if(!JIS_CODE(c)) continue;
        // 解析情報の一致度を取得
        agree=GetAgree(x_yoko,y_tate,ci[c].yoko,ci[c].tate,w,h);
        if(agree>max_agree)
        {
            max_agree=agree;
            max_c=c;        // 解析情報の一致度が最も高い文字
            if(max_c==1) break;
        }
    }

    HeapFree(hHeap,0,x_yoko);
    HeapFree(hHeap,0,y_tate);

    return max_c;           // ビットマップに最も近い文字
}