類似画像の判別方法－－濃淡分布による判定

作成開始日 2014.05.22
最終更新日 2014.06.03

■一般に、画像の類似判別はかなり難しい。スクリプトでちょこちょこっとできるものではない。しかし、用途を《サイズ違い》（ファイルサイズ／画像サイズ）および《差分画像》（コラージュを含む）の判別に限定すれば、簡単なREXXスクリプトでも何とかならないことはない。ただし、以下の方法では、《切り抜き》や《回転》およびスキャン画像の《濃淡差》にはまったく対応できない。

●濃淡コードの算出

①画像を8×8＝64ドットのグレイスケール画像に変換する。
②各ドットの濃淡を4ビット(16階調)=16進数1文字で表現する。
③64ドットの濃淡分布を64桁の16進数で表現する：これを《濃淡コード》と呼ぶ。

8×8という分割数に深い意味はない。 分割数が少なければ精度が落ち、多ければ速度が落ちる。そのバランスで選んだ。 それに、8×8＝64桁だと、テキストエディタの1行（80桁）に収まって便利。

●類似画像の判断

①２枚の画像の濃淡コードを算出する。
②濃淡コードの各桁（各ドットに相当）ごとに差を算出する。
③差が一定以上（たとえば±2以上）であれば異なるドットと判断する。
④異なるドットが一定数以下（たとえば20以内）であれば類似画像と判断する。

●8×8ドットのグレイスケール画像への変換

GBMを使用すると良い（v.176：Hobbesから入手可能）。 GBMSIZEコマンドを用いて、以下の要領で変換する。 ポイントは、テキスト形式のPGM（Portable Greyscale-map）に変換する点。 
GBMSIZE -w 8 -h 8 myimg.jpg myimg.pgm,ascii
当初はBMP形式のグレイスケール画像への変換を考えていたが、 グレイスケールBMPはパレットによる濃淡管理をしていて、 各ドットのデータがそのまま濃淡値を表現しているわけではない。 その点、PGMにはパレット管理の発想がなく、 各ドットのデータは単純に濃淡を表現している。 こちらの方が遥かに扱いやすい。

さらに、PGMは通常のバイナリ形式だけでなく、テキスト形式でも表現できる。 これならば、テキストエディタで中味が確認できるし、スクリプトでも扱いやすい。 GBMはこのテキスト形式のPGMもサポートしている（「,ascii」オプション）。 カレントのJPG画像から8×8のPGMを作成するには、次のようにすれば良い。 

rc=SysFileTree('*.jpg',img,'FO')
Do n=1 to img.0
  fname=FILESPEC('N',img.n)
  PARSE var fname body '.' ext
  fpgm=body'.pgm'
  SAY fname
  '@gbmsize -w 8 -h 8' img.n fpgm',ascii'
End
なお、ImageMagickでもconvertに「-compress none」オプションを付ければ、テキスト形式のPGMを作成することはできる。ただし、データ部分が8桁×8行ではなく、12桁×5行＋4桁という表記になるので少々扱い難い。

●PGMファイルから濃淡コードを生成

上記で変換したPGMファイルの中味は、たとえば次のようになっている。 
P2				←ファイル形式：P2＝グレイスケール／テキスト
8 8				←画像サイズ：8×8
255				←階調：0～255の256階調＝8bit/pixel
234 061 014 053 054 032 200 086 ←以下、各ドットの濃淡値
048 220 047 034 046 192 204 255
172 198 040 200 113 221 202 204
204 089 051 095 059 180 214 227
191 031 061 114 075 040 194 195
056 038 245 025 073 040 214 072
077 028 095 183 045 123 223 194
021 199 202 149 245 250 214 203
このように、先頭３行を読み飛ばせば、そのまま各ドットの濃淡値が得られる。 ただし、各ドットは8ビット(256階調)で表現されるため、16進数でも2桁になる。 PGM自体は4ビットモードをサポートしているが、GBMは8ビット/16ビットのみ。 そこで、各濃淡値を16で割って4ビットに変換する必要がある。 その上で16進数1桁に変換して、64ドットの濃淡を64桁の16進数に連結する。 
PGM2HEX: PROCEDURE			/* テキスト形式用 */

tmp=ARG(1)				/* 引数はPGMファイル名 */
rc=STREAM(tmp,'C','O')

Do n=1 to 3; dmy=LINEIN(tmp); END;	/* ヘッダのスキップ */
hex=''
Do While LINES(tmp)>0
  st=LINEIN(tmp)
  PARSE VAR st b.1 b.2 b.3 b.4 b.5 b.6 b.7 b.8
  Do n=1 to 8
    d=TRUNC(b.n/16)
    h=D2X(d)
    hex=hex||h
  End
End

rc=STREAM(tmp,'C','C')
RETURN hex
これによって、例えば上記のPGMファイルは； 
E30332C53D222CCFAC2C7DCCC5353BDEB13742CC32F142D4415B27DC1CC9FFDC
のような16進文字列に変換できる。 これを濃淡コードと呼ぶことにする。

●濃淡コードの差の算出

２枚の画像の類似度を判定するには、 それぞれの濃淡コードを作成し、 各桁ごとに（つまりドットごとに）値を比較する。 濃淡値が一致する桁（ドット）が多いほど、画像の類似度は高い。 なお、「一致」といっても完全一致ではなく、ある程度の幅（±1程度）は持たせる。 以上から、比較する濃淡コードをhex1、hex2とすると； 
diff=0
DO m=1 TO 64
  ch1=SUBSTR(hex1,m,1)
  ch2=SUBSTR(hex2,m,1)
  d=ABS(X2D(ch1)-X2D(ch2))
  IF d>1 THEN diff=diff+1
END

SELECT
  WHEN diff=0  THEN SAY 'ほぼ同一'
  WHEN diff<20 THEN SAY '似てる'
  WHEN diff<30 THEN SAY '少し似てる'
  OTHERWISE SAY '別物'
END
のような感じになる。 ポイントは、各ドットの差の大きさを考慮に入れないこと。 差が閾値（例えば±1）を超えたドットは、差の大きさに拘らず1カウントとする。 一部分の差異が全体の類似度に影響を与えては、正しい判断ができない。 一部分が極端に異なっていても、他の部分が一致すれば類似画像である。

●PNGのgAMA問題

上記のGBMを用いた方法は簡便で良いのだが、実は一つ大きな問題がある。それは、一部のPNGファイルでエラーが発生して処理不能になってしまうことだ。たとえば、次のようなメッセージが出る。 
gbmconv: can't read bitmap data of 0003.png: can't read file
同じファイルを今度はImageMagickで処理しようとすると、次のような警告メッセージが出るが、処理自体は続行される。 
Ignoring incorrect gAMA value when sRGB is also present.
このgAMAとsRGBというチャンク（ヘッダ部にある情報）に不整合が起きているらしい。これに限らず、PNGのgAMAチャンク不正はかなり一般的な問題のようだ（特にMacのPhotoshopで作成した画像で多く発生するらしい）。ただし、これらは表示時のγ補正に関るもので、データ内容の根本に関る問題ではない。そもそもgAMAチャンクなどなくてもかまわないらしい。したがって、ImageMagickのように処理を続行しても構わない。

が、GBMは律義にも？エラー発生で処理を中止してしまう。これはけっこう困る。少なくとも私が所有しているPNG画像の数％程度はこのエラーが発生するからだ。無視できる量ではない。ひょっとすると、GBMでもエラーを無視して処理を続行するオプションがあるのかも知れないが、発見できなかった。

●ImageMagickでの処理

ということで、処理全体をGBMからImageMagickに移行することにした。この場合問題になるのは、OS/2のImageMagick（2004年版）でテキスト形式のPGMへの変換が可能かどうか？結論を言えば可能だったが、表示形式に若干の問題が生じた。GBMと違って奇麗な８桁×８行ではなく、12桁×５行＋４桁という変則形式になってしまった。 
convert -geometory 8x8! -compress none 0003.png 0003.pgm
この「-compress none」オプションがテキスト化を意味するようだ。そして、この処理の 結果として得られる0003.pgmは； 
P2
8 8
255
251 242 242 251 251 175 200 238 251 234 245 252
242 138 130 205 227 212 252 252 234 117 125 163
163 178 242 245 245 184 138 157 175 227 223 251
216 212 163 183 230 251 251 245 212 212 194 205
200 227 227 230 194 178 167 205 130 148 216 216
184 157 157 200
この形式はちょっと扱いにくい。

●バイナリ形式での処理

しかし、ここまでくれば、テキスト形式にこだわる必要はない。バイナリ形式のPGMに変換・処理する方が早い。今回の処理ではヘッダが「P5/8 8/255」固定なので（P5はバイナリ形式のグレイスケール）、データの先頭もオフセット=12に決め打ちできる（ただし、ImageMagickではファイルに埋め込まれたコメントまで変換してしまうので、-commentオプションでコメントを削除する必要がある）。また、各データは2桁の16進数として取り出すことが可能で、2桁のうちの1桁目だけを使えば、8ビット→4ビット変換（16で割る）をしたことになる。 
convert -geometory 8x8! -comment "" img.jpg img.pgm

PGM2HEX: PROCEDURE			/* バイナリ形式用 */

gbmf=ARG(1)
rc=STREAM(gbmf,'C','O')
rc=STREAM(gbmf,'C','seek =12')		/* ヘッダをスキップ */

hex=''
Do 64					/* 回数は決め打ち；複数ページ画像対策 */
  ch=CHARIN(gbmf)
  hex=hex||LEFT(C2X(ch),1)		/* 16進2桁に変換して1桁目だけを使用 */
End

rc=STREAM(gbmf,'C','C')
RETURN hex
こちらの方が遥かにスッキリしたアルゴリズムで、処理も高速だと思われる。ちなみに、GBMで作成した濃淡コードと、ImgeMagickで作成した濃淡コードは全く互換性がない。恐らく、リサイズのアルゴリズムが異なるからだろう。混在不可。

■サンプルプログラムSIMISE

と言うことで、以上を踏まえて、サンプルプログラムを作ってみた。プログラム名は「SIMISE：Similar Image Selector」［シミーズ］。chemiseじゃないよ(^_^;

●ファイル構成

▼メインプログラム
SIMISED.CMD 濃淡コード作成プログラム
SIMISEF.CMD 類似画像検索プログラム

▼データファイル
SIMISE.DIR 検索対象ディレクトリ・リスト

▼外部サブルーチン
SETVAR.CMD 共用変数設定
GETIMGFL.CMD 所定のディレクトリ内から画像ファイルのみを検索して配列に入れる
PGM2HEX.CMD 8×8のPGMファイルから濃淡コードを作成する
READDIRL.CMD ディレクトリ名一覧を読み込む(ｺﾒﾝﾄ対応/存否確認付)

▼動作環境
ImageMagick 4.2.2 Hobbesから入手
GBM 1.76 Hobbesから入手
GBMRX 1.16 Hobbesから入手
以上が任意のディレクトリから使用可能になっている状態

●使い方

▼ファイルの展開
SIMISE.ZIPを任意のディレクトリにUNZIPする。

▼検索ディレクトリの設定
検索対象としたいディレクトリをSIMISE.DIRに書き込む。 

E:\MyImage
E:\MyCG
#G:\Photo
o ディレクトリ名は各自の環境に合わせて変更のこと。 なお、サブディレクトリも検索対象になる。
o 先頭に「#」がついている行はコメント。 テストのときなどは、不要なディレクトリをコメント化すると便利。
o ディレクトリ数に特に上限はない（REXXの制限に従う）が、 まあ10個程度が現実的な上限かと…

▼濃淡コードの作成
コマンドラインからSIMISEDを実行する。
上記で指定されたディレクトリごとに、濃淡コード$pgm.datが作成される。
ファイルの出入りがあった場合には、同じ手順で濃淡コードを作り直す。 その場合、更新分のみが作成される。

注意： 同一ディレクトリ・同一ファイル名で、中身の異なるファイルに 入れ代わった場合は更新検出不可能。

▼画像の検索
コマンドラインでSIMISEFを実行する。 

構文）SIMISEF ファイル名
用例）SIMISEF G:\DOWNLOAD\cg0123.jpg
類似画像が見つかると、SIMISE.HTMというファイルにHTML形式で結果が書き込まれる。 
[ 08 ]E:\MyCG\x2020.jpg［画像］
[ 24 ]E:\MyImage\9999.jpg［画像］
………
先頭の数字は相違度で、数字が小さいほど類似性が高い。 相違度の範囲は0～64だが、初期設定では相違度25までの画像をピックアップする （閾値はSIMISEFのthreshold=25の行で指定している）。

類似性が高い場合（相違度10未満）は赤で、 類似性が低い場合（相違度20以上）は灰色で表示される。 ［画像］をクリックすると、当該画像が表示される。

●判別精度

アルゴリズムが非常に単純なため、判別精度には限界がある。しかし；

①内容と縦横比がまったく同じで、サイズや画像形式のみが異なるファイルはほぼ確実に検出できる。たとえば、画像の内容が全く同じならば、800×600のJPG画像でも1024×768のPNG画像でも、相違度0で検出可能。

②ゲームなどの差分画像もかなりの確率で検出できる。たとえば、顔の表情だけが異なるような画像であれば、ほぼ確実に検出可能。ただし、人物部分が同じで、背景が異なるような画像の検出は困難。

③構図が似た画像もかなり検出できる。たとえば、背景が淡い色で、人物が右上から左下に掛けて対角線上に配置されているような画像は、ものすごく沢山検出される。

反面、判別基準が濃淡分布だけであるため、色に関してはまったく判別できない。淡いピンクも薄いブルーも同一の扱いとなってしまう。また、縦横比の異なる画像は検出できない。たとえば、横長画像を縦長に回転させたり、左右をカットしたような場合は検出不可能。これは原理上のものなので仕方がない。

【逆襲のOS/2目次】 【ホーム】