サイゼリヤ キッズメニュー 間違い探し【答え】2019
はじめに 初投稿です。 よろしくお願いします。 サイゼリヤの間違い探しを画像処理を用いて解くプログラムを作成しました。 基本的には 画像の差分をとってなんやかんやして間違いを見つける、という手法ですが、それに加え今回は ロバスト性に着目しました。 まずは実行結果をご覧ください。 差分で間違い箇所を抽出するときは全く同じ距離・角度から撮影した2枚の画像が必要となりますが 少しでもずれていると誤検出がめっちゃ増える 、少しずれた2枚の画像同士の間違いも検出できるという意味でロバスト性と言っています。 実行結果 通常、差分で間違いを探す手法では2枚の画像をきちんと位置合わせする必要があるのですが、斜めから見た画像同士からでも間違い箇所を検出できています。 最終目標は、 スマホのカメラでサイゼの間違い探しを撮影し、その写真をもとに間違いを見つけることです。 アルゴリズムの概要 以下、使用した技術等をつらつらと書いていきます。 恥ずかしながら初めてGitHub使ったのでちゃんと見られるか不安ですが、一応ソース類をアップしたのでよかったらご覧ください。 実装と環境 C. NET Framework 4. 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で歪みを加えた画像を作成しました。 また、間違い探し以外の余分な情報を極力削るために、マスク機能 手動 を追加してあります。 これに関してはこちらのブログを参考にしました。 あと最近のスマホの写真は解像度が大きめなので、処理時間が結構がかかります。 このサイズに縮小しても分解能はだいたい0. OpenCVの特徴量マッチングでSrcとTargetの対応点を取得する 画像同士のマッチングには、色々な種類があります。 ・ 画像の濃淡を主に用いたマッチング ・ エッジ情報を用いたマッチング ・ 局所的な特徴点を利用するマッチング ・その他 色々比較した結果、今回は 特徴量マッチングを使うことにしました。 個人的にはかなり便利なマッチング方式だと思うので、実装してほしいんですけどね…。 次に、形状変化への強さは特徴点マッチングが優秀です。 テンプレートマッチングと幾何形状マッチングは、マッチングの元画像と対象画像が拡大・縮小・回転を用いて一致するものしか対応できません。 一方の特徴点マッチングは、拡大・縮小・回転に加え、せん断・歪みまで対応できます。 ちなみに、拡大・縮小・回転・せん断が可能で、更に移動を実現できる変形を アフィン変換 変形 、このアフィン変換に歪み変形を加えたものを 射影変換 変形 と呼びます。 画像の多くの箇所が同時に色味の変化を起こすことはないだろうと予想し、特徴点マッチングで問題ないと判断しました。 ちなみに、色味が変わってもエッジさえ検出できればマッチングの精度に影響しないという意味で、幾何形状マッチングは優秀です。 一方テンプレートマッチングは輝度情報がキモになるので、色が変わると検出できなくなったり、精度が悪くなったりします。 特徴点マッチングにはSIFT法やSURF法など色々な手法が存在しますが、OpenCVではAKAZEという方式が一般的だそうです。 実装にあたってはこちらの記事を参考にさせていただきました。 最終的に、以下の画像のように特徴点同士を対応付けすることができました。 対応する特徴点同士をつないだ線が おおむね平行になっているのがわかります。 誤った特徴点が対応付けされている箇所もいくつかありますが、これは次に行う変換の際に 外れ値として無視されるので、あんまり気にしなくてもいいです。 対応点の情報をもとにSrcに射影変換を適用してTargetと座標を合わせる 拡大縮小回転とせん断であれば前述のようにアフィン変換で事足りますが、今回は歪みも想定しているため、射影変換を使用しました。 SrcをTargetに合わせこむようなイメージです。 処理の具体的なフローはこんな感じです。 特徴点の対応をベクトルで表現する• ベクトルの始点と終点を一致させるような射影変換を実現したい• そうなるような変換行列を作成する• 変換行列にもとづき、画像の変形を行う 以下はイメージ画像です。 OpenCvSharpでの実装方法はこちらを参考にしました。 QueryIdx ]. TrainIdx ]. ロバスト推定法はRANZAC。 FindHomography InputArray. Create getPtsSrc , InputArray. Create getPtsTarget , HomographyMethods. WarpPerspective SrcMat , WarpedSrcMat , hom , new OpenCvSharp. Size TargetMat. Width , TargetMat. SrcとTargetの差分画像を取得する ようやく2枚の画像を得ることができました。 いよいよレガシーな画像処理の出番です。 とりあえず射影変換後の画像をPhotoshopで比較してみました レイヤースタイル：差の絶対値を使用。 なかなかいい感じです。 更に、チャンネルを別個に使用すれば検出精度が上がると思ったため、RGBとHSVの各チャンネル同士の差分画像を作成しました。 ただしH 色相 、S 彩度 の差分はノイズが多くて使い物になりませんでした。 変形時の補完に原因があるような気がします。 そのため、今回は RGBと V 輝度 の 計4チャンネルのみを使用することにしました。 これらの画像に対して処理を施し、間違い箇所のみを目立たせるマスクを作っていきます。 その後LockBitsを使ってメモリ領域を直接いじる方法を知って、ようやく6枚で1秒というギリ耐えられるかなって速度になりました。 それでも遅いけど。 更にプログラム完成後に知ったんですけどPythonだとこんな感じで差分画像取れるんですね……便利……。 C やめよ。 astype int - target. 当然 ので、これを使用すれば処理時間の大幅な短縮が見込めそうです。 情報ありがとうございました。 まずは何事も調べるのは大事ですね。 ごめんなC。 差分画像の重要箇所のみを目立たせ、マスクを作成する 得られたRGBとVの計4枚の差分画像を2値化しますが、このままだとノイズが結構あるので、 メディアンフィルタを適用してごま塩ノイズを取っています。 ノイズ除去の次は4枚の画像を BitwizeOrで統合します。 すなわち、各画像の画素ごとにOR演算を行い、 どれか1枚でも白の箇所があったらその画素は白とすることで1枚の統合画像を作成します。 この処理によって、検出モレを防ぐことができます。 次に ブロブ処理で 一定の大きさより小さい差分検出領域を省いて、ノイズ除去を行います。 メディアンフィルタと被っているように思えますが、メディアンフィルタとブロブの違いは形状に依存するか否かというところです。 また、ブロブ処理は、これはある大きさのかたまりをカウントすることができる、という利点があります。 最後に、膨張処理を適用します。 膨張処理とは、 ある画素が白だったらその近傍の画素も白にするという処理のことです。 完成イメージとして、間違い箇所を囲むようなマスクを作りたかったので、差分検出領域を広げるためにこの処理をかませています。 これで最終的なマスク調整を行います。 フローの概略図はこんな感じです Vチャンネル描き忘れましたが、実際は前述のとおり4チャンネルの画像を使用しています。 なお、メディアンフィルタのカーネルサイズは3px、2値化閾値は128、膨張は5px、ブロブ面積下限値は10pxとしました。 この値でおおむね良さそうですが、実際には細かい調整をすることがあるため、こんな感じのGUIも一応作成しました。 マスクをSrcとTargetにかぶせる 射影変換したSrcとTargetを並べて表示し、両方にマスクをかぶせます。 今回のプログラムでは、差分検出領域は透明色、それ以外は低透明度の黒とすることで、間違い箇所を際立たせています。 無事10個の間違いの周辺がハイライトされていますね。 両脇もハイライトされているのは、ダウンロードできる間違い探しの画像サイズがそもそも一致しておらず、端の方が削れてしまっているからです。 机上評価結果 適当に3種類の間違い探しを選んでプログラム実行したところ、いずれも10個の間違いが取得できています！ にしても本当に難しいですね。 個人的にヤバいと思ったのは2つめの右下の焼き鳥の串の角度です。 こいつはやばい。 そして現実へ… プログラムは完成した。 抜かりはない、完璧だ。 いざ実戦といこう。 実際にサイゼで写真を撮ってみた結果 くどいようですが、今回ロバスト性を重視したのは、 サイゼに行って間違い探しの写真を撮ってその流れで答えを見つけるというリアルタイム感の実現を目指してのことです。 そのため、実際にiPhone Xで写真を撮ってこのプログラムに突っ込んでみました。 果たして結果やいかに。 デンッ！！ ダメだったよ。 失敗の原因 この失敗の原因は、実際の対象はJpgでもPngでもなく 厚紙に印刷されているというところにあるようです。 つまり、画像によって3次元的な 反りの具合が異なってしまっており、その歪みが補正しきれていません。 射影変換ではこのタイプの歪みに対応できないのです。 その結果、端にいけばいくほど画像間のずれが大きくなり、結果として端の方で誤検出が増大しています。 左端の女の子やおじさん、右端の羊なんかが顕著です。 ただし、画像の中央付近はいい感じに検出できています。 特に豆の違いが検出できているので個人的にはかなり達成感があります。 この豆だけが自力 人力 で解けなかったんですよね……。 対策 単なる歪みであれば任意直線上の特徴点同士の距離の比は変わらないため射影変換で対応できますが、今回の場合は3次元的に反っているため、より高度な変形によって丹念にあわせ込む必要があります。 色々調べたところ、九州大学の情報系の研究室の資料がヒットしました。 一応概要を書いておきます。 射影変換よりもフレキシブルに変形できる 弾性マッチングというアルゴリズムがある• 対応する点同士を一致させるアルゴリズム。 例えば、ある人の正面からの写真と斜めからの写真をマッチングして、斜めからの写真を正面からの写真に変換できる。 この原理で反りに対応できそう• こいつはやばい。 それを緩和するために 粗密DPという動的計画法を適用する• 粗密DPを低解像度の画像に適用することが前提 なるほどわからん。 ただ、本論文が執筆されたのは2004年とだいぶ前なので、技術自体は枯れてきているかもしれません。 勉強していつか実装したいですね。 その他課題 極端に小さい間違いは検出できない 画像を合わせ込む段階で画像全体の特徴点を使っているため、当然ながら間違い箇所の特徴点も使用しています。 現状、そういった箇所は閾値を設定して外れ値とすることで無視しています。 ただし、 2枚の画像両方に似たような特徴点があり、かつその2点の距離が比較的近い場合、その2点は同じであるとみなされ、 射影変換の精度に影響する可能性があります。 サイゼの間違い探しには対象がずれているだけ、という間違いも結構あるので、この影響は無視できません。 実際、以下の画像の場合だと間違いの箇所がかなり細いため、プログラムを実行した結果ノイズとみなされてしまいました。 この解決策として、「マッチングの閾値を追い込む」「画像の一部分のみの特徴点を用いて射影変換する」といった方法が考えられます。 ただし、前者は閾値を上回る間違い箇所の特徴点が無いことを証明できず、後者はその一部分に間違いがあった場合意味がない上に、一部分だけだと射影変換の精度が不安です。 よって、これらの解決策は根本的なものではありません。 あとは紙自体の反りを補正した上での話になりますが、間違い探しの 冊子のエッジを利用できるような気もします。 要検討ですね。 でもスマホアプリ作ったことないので諦めました。 Xamarin勉強します。 また、スマホで動かすためにはもっと処理を軽くする必要がありますね。 マシンパワーに頼らない実装……。 さいごに このたび初めてOpenCV（OpenCvSharp）をまともにいじりましたが、思いの外色々なことが実現できて楽しかったです。 また、今回使用した実写画像は、サイゼにテイクアウトを買いに行ったときに撮影しました。 テイクアウトかなり良かったので是非みなさまもおうちでサイゼしましょう。
次の
