どうも。フロントエンドエンジニアの @Quramy です。
さて、前回、1日10万枚の画像を検証するためにやったことで書いているとおり、reg-suitという画像に特化した回帰テストツールをメンテしています。
画像回帰テストという文脈において、差分の可視化方法はとても重要なファクターです。なぜなら、画像(=スナップショット)に差分が発生したからといって、それすなわち棄却、というわけではなく、その差分の内容を判断して、意図せぬ変更であれば棄却、意図した変更であればexpectedを更新する必要があります。すなわち、ワークフローに目視による差分のレビューが発生するのです。
そこで、少しだけ異なる2枚の画像について差分を効果的に可視化する、というテーマに向き合ってみました。
主にC++とOpenCVでの実装ですが、これらの知識が無くとも読めるよう、コードやAPIへの言及を少なくして、中間画像で説明するようにしてみたので、軽い気持ちで読んでいただければと。
既存の画像比較表示方法の課題
画像の差分といえば、真っ先に思いつくのは、各画素毎に色空間距離等を測り、非ゼロである画素を強調表示する方法です。ImageMagickに同梱されているcompareコマンドなどで簡単に利用することができます。
例として、以下の2枚の画像を対象としましょう。
compare after.png before.png diff.png
このコマンドの結果は次のようになります。
見ての通り、Like 表示の部分が強調表示され、一目で差分の内容がわかります。
それでは、似たような画像ですが、対象が下記の場合どうでしょうか。
こちらの場合、compareコマンドの結果は以下のようになってしまいます。
ほとんどすべての画素で差分が出てしまうため、真っ赤になってしまいました。
ところで、ここで比較していた画像は、実はコメント数とLike数がbefore/afterで異なっていたのですが、気づきましたか？
このように、縦ズレが発生してしまうと、その違いに埋もれて、本当に発生している差分を見逃してしまうかもしれません。
画像の差分を強調する手段としては、画素ごと比較以外にも、Onion SkinningやSwipeなどの手法がありますが1、ここで例示したような縦ズレに対しては、やはり効果が期待できません。
間違い探し
縦ズレによって真っ赤になってしまう、というのは、テキストファイルで例えると、ソースコードに1行追加に対してそれ以降の全行がdiff扱いされるのと一緒です。もし、diffコマンドやGitHubのdiff画面がそんな様子だったら、PRレビュー時にうんざりしてしまうでしょう。
diffコマンドは、言ってしまえば効率良く2つのテキストファイルの間違い探しをする手段、と捉えることができますよね。要するに、僕が欲しているものは「スマートな間違い探し」なのです。
そんな言葉遊びをしているうちに頭をよぎったのは、何年か前に読んだ 河本の実験室: サイゼリヤの間違い探しが難しすぎたので大人の力で解決した というブログ記事です。
ざっくりと説明すると、「子供向けの間違い探しに画像処理技術を駆使して取り組む」という内容です。
このブログが執筆されたのが2014年なので、おそらく読んだのも書かれた直後だと思うのですが、僕の深層意識に「間違い探しといえばOpenCV」という印象が強烈に焼き付けられた結果、約3年の時を経て浮上してきたのです。
そうです、OpenCVならなんとかしてくれるに違いない。
作ってみた
ということでC++とOpenCVで実装してみました。先程の入力に対して、次のようにマーキングを行います。
- 青枠: 平行移動を検知した領域
- 赤枠: それぞれの青枠内部同士で、ピクセル距離により差分が検出された箇所
- 紫枠: 青枠外の外側にあるオブジェクトを囲んだ部分。diffにおけるaddition / deletion的な位置づけ
wasm版
そういえば弊社フロントチームが今年に書いたアドカレを読んでみると、謎のWeb Assembly圧力がかかっています。こいつらJavaScriptとか本当は嫌いなんじゃないのか、という気持ちになってきます。
とりあえずWeb Assemblyに絡めた何かをしないと村八分にされそうなので、emscriptenでポーティングしてブラウザから実行できるようにしてみました。下記URLから実際の動作が確認できます。
真面目な話をしておくと、reg-suitが出力する画像差分レポートは、ブラウザで閲覧する前提で作られているため、ユーザーが画像を表示したタイミングで実行すれば十分、ということもありwasmにしてみました2。また、2017年は主要なモダンブラウザでWeb Assemblyの実装が進んだこともあり、手を出すならちょうどいいタイミングなのではという気持ちがありました。
処理の流れ
ここからの話に興味がある人がどれだけいるのか怪しいものですが、折角なのでアルゴリズムについても触れておきます。「サイゼリヤの間違い探しが〜」と同様、局所特徴記述子のマッチングが根底にあります。
順を追って見ていきましょう。
まず、それぞれの画像から特徴記述子を計算してマッチングをかけます3。
書籍やサンプルでよくあるのは、得られたマッチング結果に対して cv::findHomograpy を利用して、2枚の画像における射影変換行列を算出して、、、というやつですが、僕が向き合っているのは写真ではなく、スクリーンショットで得られる画像ですので、回転や拡大縮小が生じているとは考えにくいです。単一の射影変換行列ではなく、複数の線形移動ベクトルが欲しいのです。
そこで、マッチングされた各特徴点の差分ベクトルの値を利用して、マッチング結果をクラスタリングしていきます。言い換えると、各点の移動距離に重みをつけてカテゴライズする、ということです。
ここではK平均法を使いました。特徴点の差分ベクトルについて、ユニークな成分値の個数を数え上げてから、適当な定数をかけてクラスタ数とします。
K平均法の初期値は少し多めに設定しているので、得られたクラスタについて、距離が近く線形移動量が同一である矩形については結合していくと、次のような結果が得られます。
挿入されたアバター部分を挟んで、2つの線形移動領域を類推できました。この領域内同士の画素でピクセル比較を行えば、線形移動を考慮した画像差分となりそうです。
ところが、上の画像を見ての通り、矩形によりカバーされていない範囲がまだまだあります。特徴点が都合よく画像の端点に存在するわけもないですし、アルゴリズムから考えてもエッジ上の点は検出されにくいため、これは当然です。
そこで、領域の外側についても少しずつ比較を行って、マッチング領域自体を拡張することを考えます。
要は「マッチングした領域の近傍も差分が出ない可能性が高いはずだ」という仮定にもとづいて、一定の差分が検出されるまで領域を拡張していきます。
下図にて、水色で表示しているのが拡張後のマッチング領域です。この領域について、色空間距離で差分をとると赤枠部分が検出できます。
最後に、マッチングした領域の外側にのみ存在する部分を強調表示しましょう。
元画像にエッジ抽出を行い、マッチング領域をすべて塗りつぶすと、次のような画像になります。
この画像について、適当に矩形を抽出してやれば「片方の画像にのみ存在する物体(=追加または削除された可能性が高い部分)」となります。
これで、最終的に下記の画像を得ることができます。
おわりに
今回はOpenCVを利用した画像差分検出について書いてみました。如何でしたでしょうか。
作ってはみたものの、実際のところは「そうじゃないんだよなー」的な表示をすることもしばしばです。
まだまだ感は拭えませんが、ちょっとずつ改良していこうと思います。
それでは、また。