同一画像検索(5): 同一判定方法の再考

前回簡易版を作ってみたが、縮小した画像が「同一」と見做されなかった。今回はこれにどう対処するか検討してみる。この問題は、各画像を4x4解像度に変換した結果(=fingerprint)を取った時に、元画像と縮小画像とで微妙に異なるのが原因だった。簡易版は「同一画像ならfingerprintが全く同じになる」ことを前提に作ってあったからだ。

そこで、同一画像と見做せるようにする対策案を考えてみた。

解像度をもっと減らす
色階調を減らす
fingerprintの微妙な違いを許容する

a. 解像度をもっと減らす

前回のサンプル画像で試してみる。解像度を2x2に減らしたところ、2つの画像の差はなくなった。これは行けるかもと思ったが、別の画像で試したらやはり差が生じた。また、そもそも2x2程度では、異なる画像がたまたま同一のfingerprintになる可能性も高まる。この方法は却下だ。

b. 色階調を減らす

各色256階調、3原色で1600万色であるから、画像の縮尺が変われば同じ画像でも多少の差が出てきてしかるべき。であれば、階調を減らせば多少の差は吸収されるのではないか。階調を減らすには256段階(=1byte)の下数桁をマスクして 0にしてやれば良いだろう。たとえば、

<色値> AND 0xFC (0xFCは下2桁を除外するマスク→64段階にする）

といった処理をfingerprintの全バイトへ適用するということ。

しかしこの方法は根本解決にならない。階調を減らしたところで近い色値が「同一」になる保証はない。極端な例だと、2つの画像のある点で色値がそれぞれ127と128となるような場合、きわめて近い色なのにどのようなマスクを設定しても「同一」と見做されない。ゆえにこの方法も却下だ。

c. fingerprintの微妙な違いを許容する

微妙な違いを許容して「同一」と考えるために、2画像のfingerprintの各点が閾値以下の差なら「同一」とみなそう。(当初のロジックで、2段階目に解像度16x16でやろうとしたことだ)

元々、fingerprintが一致する前提ならMapを使って計算量を抑えられそうと見込んだ。Mapなら計算量は $O(\log N)$ (?)。しかし、差を調べるには総当たりするしかないので計算量は $O(N^{2})$ だ。画像数が数千枚レベルになると大変そうなので嫌なのだが・・・仕方ない。

総当たりなので基本的なロジックは、、、

リスト中の最初の画像とそれ以降の画像のfingerprintを比較して同じとみなせるものがあればそれらをリストで返す => (n-1回の比較)
二番目の画像とそれ以降の・・・（以下略）=> (n-2回の比較)
三番目の・・・（以下略)
・・・n-1番目の・・・（以下略）=> (1回の比較)
=> しめて $(n-1)!$ 回の比較

だろう。返ってくるのは「同一」と判断されたリストの集合（リスト）。

ちなみに、比較がやり易いようにFingerPrintの型をByteStringから [Word8]に変更し、画像を表すあらたな型Imageも定義してみた。

type FingerPrint = [Word8]
type Image = (FingerPrint, FilePath)

先のロジックをコードにすると次のような感じ。

matchImage :: [Image] -> [[FilePath]]
matchImage [] = []
matchImage (x:[]) = []
matchImage (x:xs)
  | ps == [] = matchImage xs
  | otherwise = (snd x:ps):(matchImage xs)
  where
    ps = roundRobin x xs

roundRobin :: Image -> [Image] -> [FilePath]
roundRobin x [] = []
roundRobin x (y:ys)
  | isSame x y == False = roundRobin x ys
  | otherwise = (snd y):(roundRobin x ys)

matchImageでn-1回の繰り返し、roundRobinである画像とその他の画像を比較して同じとみなせるものがあればリストにして返す、とやっている。なおisSameが同一かどうかの判別関数であり、同一の場合はその画像をリストに加えている。

画像(のfingerprint)を同じとみなす方法もいくつかある(fingerprintをn次ベクトルとみて距離を取るとか、同色の点が何割以上とか)が、今回は「各点の色の差がすべて閾値以下」を条件とした。上記の通りfingerprintをWord8 (1バイト符号なし整数)のリストと定義しなおしたので、二つのリストを先頭から順に比べていけばよいだろう。閾値を超えたところで「違う」のだから比較をやめればよい。

isSame :: Image -> Image -> Bool
isSame x y = d == Nothing
  where
    d = find differ (zip (fst x) (fst y))
    differ :: (Word8, Word8) -> Bool
    differ (a, b) = d' > threshold
    where
      d' = if a > b then a - b else b - a

threshold = 4 :: Word8

何かもっとスマートな書き方がありそうだが…。これは今後の課題にしよう。 thresholdは各点の各色の差の許容範囲(閾値)。ここでは4にしたが、適当に決めた。色階調が256段階だから1.5%ぐらい。どれぐらいが適当か不明だが 5%ぐらいまでは許容範囲かなと思う。

あと、getFingerPrintにバグがあった。修正したものは以下の通り。

getFingerPrint :: Int -> FilePath -> IO FingerPrint
getFingerPrint r f = do
  (sin, sout, serr, ph) <- runInteractiveCommand command
  waitForProcess ph
  fp <- BS.hGet sout size
  return $ B.unpack fp
  where
    geo = (show r) ++ "x" ++ (show r)
    size = r * r * 3
    command = "convert -filter Cubic -resize " ++ geo ++ "! "
           ++ f ++ " PPM:- | tail -c " ++ (show size)

まず、コマンドの出力を取り込むところ、BS.hGetLineをBS.hGetに訂正。出力にたまたま改行コードと同じものがあるとそこで切れてしまうバグだった。次にImageMagickのコマンド部分、引数から-defineを抜いた。これをつけると縮小処理が大幅に高速化するのだが、逆に画像の品質が悪くなった。今回の場合 fingerprintの誤差が本来よりかなり大きくなってしまった。これはいただけない。 (気付くのにだいぶ時間がかかった…)

実行してみた結果がこれ。

probably same: work/IMG_0309-2.jpg, work/IMG_0309-3.jpg, work/IMG_0309-4.jpg, work/IMG_0309.jpg
probably same: work/IMG_0309-3.jpg, work/IMG_0309-4.jpg, work/IMG_0309.jpg
probably same: work/IMG_0309-4.jpg, work/IMG_0309.jpg
probably same: work/sample1.jpg, work/sample7.jpg
probably same: work/sample2.jpg, work/sample5.jpg

前回試した画像に対し、50%、25%縮小画像でもちゃんと同一とみなしてくれている。他にも2種類の画像(sample?.jpg)を試したが、いずれも認識できた。やれやれ。ただ、一行目と二行目を比べるとわかるように、3つ以上の画像A,B,Cがあって、それらが互いに「同一」と判断された場合は複数行に結果が出てくる。しかも後の方は前のリストに包含されているので無駄だ。これは何とかしたい。

ということで、次回はこの件の最終回。上記の無駄を省く処理と若干のソースの改善をしたいと思う。