実は、これは今回の最大の難関だったりするんだけど、グラフによって縦軸のMAX値が違うんだよね。人によって1〜500くらいまで幅があるので、それを考慮しないといけない。画像処理の素人に文字判別はハードル高すぎだろ・・・。とはいえ、こういうアルゴリズムって嫌いじゃないので時間さえ許せばGAとかHMMとかニューラルネットとか使って文字判定を行う処理を作ればいいんだけど、いかんせん素人なもんでアルゴリズム自体は知ってるけど実装したことない*1からすぐにはできない。
そんな面倒な統計処理をするよりは、単純なパターンマッチングでいけるんじゃね？ということで、できるだけ単純なパターンマッチの方法を考えることに。
まず考えたのは、該当の部分を抜き出した画像サンプルのテンプレートをいくつも作って、それとのマッチングをする方法。これは一番分かりやすいけど、画像が合計1000以上あるのにいちいちテンプレート画像を読み込むってのはオーバーヘッド多すぎないか？っていうのと、ポータビリティが下がるなあ・・・っていうのが気になる。理想的には実行ファイル1つでできるようになりたいし。
んで考えたのが、該当部分をビット列とみなして、ビットパターンのマッチングをすればいいんじゃないかということ。それならint型*縦の長さ分だけですむし、プログラム中にハードコーディングすればポータビリティも抜群。パターンを追加したいならコピペしてリコンパイルするだけだし、それほどメンテナンス性も悪くならないでしょ。都合のいいことに、グラフの左枠は32pixelを超えることはないようなので*2、0pixel目から全て取ってきてもint1つで間に合うでしょう。
具体的数値の話としては、横範囲は枠線の左端から画面の左0ピクセル目まで、最大32bitでOK。縦範囲は固定で、枠線の上端+4〜-2までの範囲になってるので遠慮なくハードコーディング。
実際のコーディングはこんな感じ。
#define OFFSET_COUNTER_UP 4 #define OFFSET_COUNTER_DOWN 3 #define COUNTER_HEIGHT (OFFSET_COUNTER_UP + OFFSET_COUNTER_DOWN) #define INT_BITS (sizeof(int)*8) void get_bit_pattern(graph_area *g) { int i1, i2, j1, j2; int sh = g->top - OFFSET_COUNTER_UP; int sw = (g->left < INT_BITS) ? 0 : g->left - INT_BITS; printf("max_value area: sh=%d sw=%d eh=%d ew=%d\n", sh, sw, sh+COUNTER_HEIGHT, g->left); dump_graph(g, sh, sw, sh+COUNTER_HEIGHT, g->left); for(i1=0; i1<COUNTER_HEIGHT; i1++){ g->bit_pattern[i1]=0; } printf("max_value bit_pattern:\n"); for(i1=0, i2=sh; i1<COUNTER_HEIGHT; i1++, i2++){ for(j1=0, j2=sw; j1<g->left; j1++, j2++){ printf("%d", g->image[i2][j2]); g->bit_pattern[i1] |= (g->image[i2][j2] << (INT_BITS-(j1+1))); } printf("\n"); } printf("max_value hex_pattern: {"); for(i1=0; i1<COUNTER_HEIGHT; i1++){ printf("0x%08x, ", g->bit_pattern[i1]); } printf("},\n"); } void dump_graph(graph_area *g, int sh, int sw, int eh, int ew) { int i, j; for(i=sh; i<eh; i++){ for(j=sw; j<ew; j++){ putchar((g->image[i][j] == 0) ? ' ' : '*'); } putchar('\n'); } }
$ ./png nana.png
input file: [nana.png]
png signature: 89 50 4e 47 0d 0a 1a 0a
graph border: t=17 b=161 l=32 r=389
max_value area: sh=13 sw=0 eh=20 ew=32
** **** **
* * * * *
* *** * **
* * ** *
* * * *
* * * * *
**** ** **
max_value bit_pattern:
00000000000011001111001100000000
00000000000100101000010010000000
00000000000000101110010110000000
00000000000001000001011010000000
00000000000010000001010010000000
00000000000100001001010010000000
00000000000111100110001100000000
max_value hex_pattern: {0x000cf300, 0x00128480, 0x0002e580, 0x00041680, 0x00081480, 0x00109480, 0x001e6300, },参考までに、全ファイルのビットパターンは以下の通り。$ grep "^max_value hex_pattern:" bit_pattern.list | sort | uniq -c | sort -r
191 max_value hex_pattern: {0x000f0000, 0x00080000, 0x000e0000, 0x00010000, 0x00010000, 0x00090000, 0x00060000, },
152 max_value hex_pattern: {0x00000080, 0x00000180, 0x00000080, 0x00000080, 0x00000080, 0x00000080, 0x000001c0, },
124 max_value hex_pattern: {0x000c0780, 0x00120400, 0x00020700, 0x00040080, 0x00080080, 0x00106480, 0x001e6300, },
120 max_value hex_pattern: {0x00086000, 0x00189000, 0x0008b000, 0x0008d000, 0x00089000, 0x00089000, 0x001c6000, },
107 max_value hex_pattern: {0x000cf000, 0x00128000, 0x0002e000, 0x00041000, 0x00081000, 0x00109000, 0x001e6000, },
29 max_value hex_pattern: {0x000f3000, 0x00084800, 0x000e5800, 0x00016800, 0x00014800, 0x00094800, 0x00063000, },
5 max_value hex_pattern: {0x000403c0, 0x000c0200, 0x00040380, 0x00040040, 0x00040040, 0x00043240, 0x000e3180, },
3 max_value hex_pattern: {0x000cf300, 0x00128480, 0x0002e580, 0x00041680, 0x00081480, 0x00109480, 0x001e6300, },
3 max_value hex_pattern: {0x00086300, 0x00189480, 0x0008b580, 0x0008d680, 0x00089480, 0x00089480, 0x001c6300, },
1 max_value hex_pattern: {0x000f3180, 0x00084a40, 0x000e5ac0, 0x00016b40, 0x00014a40, 0x00094a40, 0x00063180, },
