はじめに

初投稿です。よろしくお願いします。

サイゼリヤの間違い探しを画像処理を用いて解くプログラムを作成しました。
基本的には画像の差分をとってなんやかんやして間違いを見つける、という手法ですが、それに加え今回はロバスト性に着目しました。
まずは実行結果をご覧ください。

※ロバスト性… 本義は外乱の影響の受けづらさ。差分で間違い箇所を抽出するときは全く同じ距離・角度から撮影した2枚の画像が必要となりますが(少しでもずれていると誤検出がめっちゃ増える)、少しずれた2枚の画像同士の間違いも検出できるという意味でロバスト性と言っています。

実行結果

通常、差分で間違いを探す手法では2枚の画像をきちんと位置合わせする必要があるのですが、斜めから見た画像同士からでも間違い箇所を検出できています。
最終目標は、スマホのカメラでサイゼの間違い探しを撮影し、その写真をもとに間違いを見つけることです。

アルゴリズムの概要

以下、使用した技術等をつらつらと書いていきます。
恥ずかしながら初めてGitHub使ったのでちゃんと見られるか不安ですが、一応ソース類をアップしたのでよかったらご覧ください。
https://github.com/ika-kk/SaizeriyaPj

実装と環境

C#
.NET Framework 4.6.1
OpenCvSharp4
Windows 10 Home
Intel Core i7-6700 @ 3.40GHz
RAM 16.0GB
グラボは非搭載

フローチャート

画像を2枚読み込む(以下SrcとTargetと記載します)
OpenCVの特徴量マッチングでSrcとTargetの対応点を取得する
対応点の情報をもとにSrcに射影変換を適用し、Targetと座標を一致させる
SrcとTargetの差分画像を取得する
差分画像の重要箇所のみを目立たせ、マスクを作成する
マスクをSrcとTargetにかぶせ、間違い箇所を目立たせる

1. 画像を2枚読み込む

まずはサイゼリヤの間違い探しの画像を読み込みます。
今回はサイゼリヤのホームページから画像をいただきました。
なお、実際にサイゼに行って間違い探しの写真を撮るという状況を想定し、Photoshopで歪みを加えた画像を作成しました。

また、間違い探し以外の余分な情報を極力削るために、マスク機能(手動)を追加してあります。
これに関してはこちらのブログを参考にしました。
【C#】レイヤー機能を作る｜いえひのプログラミング部屋

あと最近のスマホの写真は解像度が大きめなので、処理時間が結構がかかります。
そのため、次の処理に進む際に、画像サイズを800[px]*600[px]におさまるサイズに縮小するようにしました。
このサイズに縮小しても分解能はだいたい0.4[mm/px]になるため、幅・高さともに1~2mm以上の間違い箇所であれば検出できるはずです。

2. OpenCVの特徴量マッチングでSrcとTargetの対応点を取得する

画像同士のマッチングには、色々な種類があります。
・テンプレートマッチング (画像の濃淡を主に用いたマッチング)
・幾何形状マッチング (エッジ情報を用いたマッチング)
・特徴点マッチング (局所的な特徴点を利用するマッチング)
・その他

色々比較した結果、今回は特徴量マッチングを使うことにしました。

方式	OpenCV	形状変化への強さ	色味の変化への強さ
テンプレートマッチング	対応	×	×
幾何形状マッチング	非対応	×	○
特徴点マッチング	対応	○	△

幾何形状マッチングはOpenCVには非実装だったため、自動的に候補から除外されます。個人的にはかなり便利なマッチング方式だと思うので、実装してほしいんですけどね…。

次に、形状変化への強さは特徴点マッチングが優秀です。
テンプレートマッチングと幾何形状マッチングは、マッチングの元画像と対象画像が拡大・縮小・回転を用いて一致するものしか対応できません。
一方の特徴点マッチングは、拡大・縮小・回転に加え、せん断・歪みまで対応できます。冒頭にもあるように斜めから見た画像(=歪み変形した画像)同士を比較したいので、特徴点マッチングを採用しました。
ちなみに、拡大・縮小・回転・せん断が可能で、更に移動を実現できる変形をアフィン変換(変形)、このアフィン変換に歪み変形を加えたものを射影変換(変形)と呼びます。

画像の多くの箇所が同時に色味の変化を起こすことはないだろうと予想し、特徴点マッチングで問題ないと判断しました。
ちなみに、色味が変わってもエッジさえ検出できればマッチングの精度に影響しないという意味で、幾何形状マッチングは優秀です。一方テンプレートマッチングは輝度情報がキモになるので、色が変わると検出できなくなったり、精度が悪くなったりします。

特徴点マッチングにはSIFT法やSURF法など色々な手法が存在しますが、OpenCVではAKAZEという方式が一般的だそうです。
実装にあたってはこちらの記事を参考にさせていただきました。
OpenCvSharpでAKAZEを用いて特徴量を検出する - Qiita

最終的に、以下の画像のように特徴点同士を対応付けすることができました。
対応する特徴点同士をつないだ線がおおむね平行になっているのがわかります。
誤った特徴点が対応付けされている箇所もいくつかありますが、これは次に行う変換の際に外れ値として無視されるので、あんまり気にしなくてもいいです。
ちなみに、今回使用した特徴点の数は、全体の10%です。つまり本来はこの10倍の特徴点が検出されているのですが、処理が重くなること、外れ値を多く含むため使用する意味がないことから、一致度上位10%のみを抽出しています。

3. 対応点の情報をもとにSrcに射影変換を適用してTargetと座標を合わせる

拡大縮小回転とせん断であれば前述のようにアフィン変換で事足りますが、今回は歪みも想定しているため、射影変換を使用しました。SrcをTargetに合わせこむようなイメージです。処理の具体的なフローはこんな感じです。

特徴点の対応をベクトルで表現する
ベクトルの始点と終点を一致させるような射影変換を実現したい
そうなるような変換行列を作成する
変換行列にもとづき、画像の変形を行う

以下はイメージ画像です。簡単のために4隅のベクトルしか書いていませんが、実際は画像中の一致度上位10%の特徴点同士のベクトル全てを考慮し、かつ外れ値は無視しつつ変形が行われています。

OpenCvSharpでの実装方法はこちらを参考にしました。
画像から特徴量を抽出し、透視変換行列を導出して画像を変形する - Qiita
OpenCvSharpで透視投影の補正 - SourceChord

実装(折りたたみ)

射影変換の実装部

Mat SrcMat, TargetMat; // 素材画像
public Mat WarpedSrcMat; // 射影変換後の画像
KeyPoint[] KeyPtsSrc, KeyPtsTarget; // 特徴量
IEnumerable<DMatch> SelectedMatched; // マッチング結果

public void FitSrcToTarget()
{
    // 使用する特徴点の量だけベクトル用意
    int size = SelectedMatched.Count();
    var getPtsSrc = new Vec2f[size];
    var getPtsTarget = new Vec2f[size];

    // SrcとTarget画像の対応する特徴点の座標を取得し、ベクトル配列に格納していく。
    int count = 0;
    foreach (var item in SelectedMatched)
    {
        var ptSrc = KeyPtsSrc[item.QueryIdx].Pt;
        var ptTarget = KeyPtsTarget[item.TrainIdx].Pt;
        getPtsSrc[count][0] = ptSrc.X;
        getPtsSrc[count][1] = ptSrc.Y;
        getPtsTarget[count][0] = ptTarget.X;
        getPtsTarget[count][1] = ptTarget.Y;
        count++;
    }

    // SrcをTargetにあわせこむ変換行列homを取得する。ロバスト推定法はRANZAC。
    var hom = Cv2.FindHomography(
        InputArray.Create(getPtsSrc),
        InputArray.Create(getPtsTarget),
        HomographyMethods.Ransac);

    // 行列homを用いてSrcに射影変換を適用する。
    WarpedSrcMat = new Mat();
    Cv2.WarpPerspective(
        SrcMat, WarpedSrcMat, hom,
        new OpenCvSharp.Size(TargetMat.Width, TargetMat.Height));
}

4. SrcとTargetの差分画像を取得する

ようやく2枚の画像を得ることができました。いよいよレガシーな画像処理の出番です。
とりあえず射影変換後の画像をPhotoshopで比較してみました(レイヤースタイル：差の絶対値を使用)。なかなかいい感じです。

更に、チャンネルを別個に使用すれば検出精度が上がると思ったため、RGBとHSVの各チャンネル同士の差分画像を作成しました。ただしH(色相)、S(彩度)の差分はノイズが多くて使い物になりませんでした。変形時の補完に原因があるような気がします。
そのため、今回はRGBとV(輝度)の計4チャンネルのみを使用することにしました。これらの画像に対して処理を施し、間違い箇所のみを目立たせるマスクを作っていきます。

余談ですが、OpenCVには画素にアクセスするメソッドSet/GetPixelが用意されています。最初はそれを使って実装したのですが、クソ遅かったです(800px*600pxの差分画像を1枚作るのに5秒くらいかかった)。
その後LockBitsを使ってメモリ領域を直接いじる方法を知って、ようやく6枚で1秒というギリ耐えられるかなって速度になりました。それでも遅いけど。
更にプログラム完成後に知ったんですけどPythonだとこんな感じで差分画像取れるんですね……便利……。~~C#やめよ。~~

Python

diff = src.astype(int) - target.astype(int)

2020/05/17追記
@albireo 氏からコメントを頂き、OpenCVにも差分画像を取得する cv::absdiff があることを知りました。当然 OpenCvSharpにも組み込まれているので、これを使用すれば処理時間の大幅な短縮が見込めそうです。情報ありがとうございました。
まずは何事も調べるのは大事ですね。ごめんなC#。

5. 差分画像の重要箇所のみを目立たせ、マスクを作成する

得られたRGBとVの計4枚の差分画像を2値化しますが、このままだとノイズが結構あるので、メディアンフィルタを適用してごま塩ノイズを取っています。
メディアンフィルタ　画像処理ソリューション

ノイズ除去の次は4枚の画像をBitwizeOrで統合します。すなわち、各画像の画素ごとにOR演算を行い、どれか1枚でも白の箇所があったらその画素は白とすることで1枚の統合画像を作成します。この処理によって、検出モレを防ぐことができます。
ピクセル毎の論理演算 AND NOT OR XOR | OpenCV画像解析入門

次にブロブ処理で一定の大きさより小さい差分検出領域を省いて、ノイズ除去を行います。メディアンフィルタと被っているように思えますが、メディアンフィルタとブロブの違いは形状に依存するか否かというところです。また、ブロブ処理は、これはある大きさのかたまりをカウントすることができる、という利点があります。今回は実装~~できなかった~~していませんが「○個の間違いを表示する」といったように指定することも応用次第でできると思います。
ブロブ解析～ヴィスコの画像処理技術 | ヴィスコ・テクノロジーズ株式会社

最後に、膨張処理を適用します。膨張処理とは、ある画素が白だったらその近傍の画素も白にするという処理のことです。
完成イメージとして、間違い箇所を囲むようなマスクを作りたかったので、差分検出領域を広げるためにこの処理をかませています。これで最終的なマスク調整を行います。
膨張・収縮・オープニング・クロージング　画像処理ソリューション

フローの概略図はこんな感じです(Vチャンネル描き忘れましたが、実際は前述のとおり4チャンネルの画像を使用しています)。

なお、メディアンフィルタのカーネルサイズは3px、2値化閾値は128、膨張は5px、ブロブ面積下限値は10pxとしました。この値でおおむね良さそうですが、実際には細かい調整をすることがあるため、こんな感じのGUIも一応作成しました。

6. マスクをSrcとTargetにかぶせる

射影変換したSrcとTargetを並べて表示し、両方にマスクをかぶせます。
今回のプログラムでは、差分検出領域は透明色、それ以外は低透明度の黒とすることで、間違い箇所を際立たせています。
無事10個の間違いの周辺がハイライトされていますね。
両脇もハイライトされているのは、ダウンロードできる間違い探しの画像サイズがそもそも一致しておらず、端の方が削れてしまっているからです。

机上評価結果

適当に3種類の間違い探しを選んでプログラム実行したところ、いずれも10個の間違いが取得できています！
にしても本当に難しいですね。個人的にヤバいと思ったのは2つめの右下の焼き鳥の串の角度です。こいつはやばい。

そして現実へ…

プログラムは完成した。抜かりはない、完璧だ。
いざ実戦といこう。

実際にサイゼで写真を撮ってみた結果

くどいようですが、今回ロバスト性を重視したのは、サイゼに行って間違い探しの写真を撮ってその流れで答えを見つけるというリアルタイム感の実現を目指してのことです。
そのため、実際にiPhone Xで写真を撮ってこのプログラムに突っ込んでみました。果たして結果やいかに。

デンッ！！

ダメだったよ。

失敗の原因

この失敗の原因は、実際の対象はJpgでもPngでもなく厚紙に印刷されているというところにあるようです。つまり、画像によって3次元的な反りの具合が異なってしまっており、その歪みが補正しきれていません。射影変換ではこのタイプの歪みに対応できないのです。
その結果、端にいけばいくほど画像間のずれが大きくなり、結果として端の方で誤検出が増大しています。左端の女の子やおじさん、右端の羊なんかが顕著です。

ただし、画像の中央付近はいい感じに検出できています。特に豆の違いが検出できているので個人的にはかなり達成感があります。この豆だけが自力(人力)で解けなかったんですよね……。

対策

単なる歪みであれば任意直線上の特徴点同士の距離の比は変わらないため射影変換で対応できますが、今回の場合は3次元的に反っているため、より高度な変形によって丹念にあわせ込む必要があります。
色々調べたところ、九州大学の情報系の研究室の資料がヒットしました。
【スライド】２次元ワープを用いた顔画像処理顔画像処理 - 内田誠一氏、他2名
 【論文】粗密DPに基づく画像の弾性マッチングアルゴリズム - 宮崎洋光氏、他2名
一応概要を書いておきます。

射影変換よりもフレキシブルに変形できる弾性マッチングというアルゴリズムがある
- 対応する点同士を一致させるアルゴリズム。例えば、ある人の正面からの写真と斜めからの写真をマッチングして、斜めからの写真を正面からの写真に変換できる。
- この原理で反りに対応できそう
ただし計算量が$O(N^{2}9^{2N})$らしい。こいつはやばい。
- 指数オーダーのヤバさ → 【YouTube】フカシギの数え方
それを緩和するために粗密DPという動的計画法を適用する
- これにより計算量は$O(N^{4})$となり、ある程度現実的なアルゴリズムとなる
- 粗密DPを低解像度の画像に適用することが前提

なるほどわからん。ただ、本論文が執筆されたのは2004年とだいぶ前なので、技術自体は枯れてきているかもしれません。勉強していつか実装したいですね。

その他課題

極端に小さい間違いは検出できない

画像を合わせ込む段階で画像全体の特徴点を使っているため、当然ながら間違い箇所の特徴点も使用しています。現状、そういった箇所は閾値を設定して外れ値とすることで無視しています。
ただし、2枚の画像両方に似たような特徴点があり、かつその2点の距離が比較的近い場合、その2点は同じであるとみなされ、射影変換の精度に影響する可能性があります。サイゼの間違い探しには対象がずれているだけ、という間違いも結構あるので、この影響は無視できません。
実際、以下の画像の場合だと間違いの箇所がかなり細いため、プログラムを実行した結果ノイズとみなされてしまいました。
2006年8月の間違い探し - 左下の時計の短針に注目

この解決策として、「マッチングの閾値を追い込む」「画像の一部分のみの特徴点を用いて射影変換する」といった方法が考えられます。
ただし、前者は閾値を上回る間違い箇所の特徴点が無いことを証明できず、後者はその一部分に間違いがあった場合意味がない上に、一部分だけだと射影変換の精度が不安です。よって、これらの解決策は根本的なものではありません。
あとは紙自体の反りを補正した上での話になりますが、間違い探しの冊子のエッジを利用できるような気もします。要検討ですね。

サイゼで実行したい

「サイゼに行く→注文する→写真を撮る→実行する→料理が来るまでに間違いを全て見つける」というのが理想のフローです。
でもスマホアプリ作ったことないので諦めました。Xamarin勉強します。
また、スマホで動かすためにはもっと処理を軽くする必要がありますね。マシンパワーに頼らない実装……。

さいごに

このたび初めてOpenCV（OpenCvSharp）をまともにいじりましたが、思いの外色々なことが実現できて楽しかったです。

また、今回使用した実写画像は、サイゼにテイクアウトを買いに行ったときに撮影しました。
テイクアウトかなり良かったので是非みなさまもおうちでサイゼしましょう。
サイゼリヤトップページ｜サイゼリヤ

サイゼリヤの間違い探しをロバストな画像処理で解く