読者です 読者をやめる 読者になる 読者になる

Haskellでいってみよう

日曜プログラマにも満たないレベルでもHaskellで何かソフトウェアを作りたい!

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

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

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

  1. 解像度をもっと減らす
  2. 色階調を減らす
  3. 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.hGetLineBS.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があって、 それらが互いに「同一」と判断された場合は複数行に結果が出てくる。しかも 後の方は前のリストに包含されているので無駄だ。これは何とかしたい。

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