画像のパターンマッチング

特徴点抽出を使ったパターンマッチングを作ってみました。これは、１０年越しの懸案事項であった、回転対応サーチ、縮小・拡大対応サーチ、部分的な欠落画像に対するサーチなどに対応できるように考えたモノです。ＣＯＧＮＥＸ社やＨＡＬＣＯＮに少しでも近づけるようがんばります。

命題と、この問題に対する思い

　命題は、比較的簡単です。「マーク」と呼ばれる画像を、別の画像の中から探し、その位置と角度を答えるというものです。　回転を考えなければ、画像差分を全パターン検索するといった「力技」で可能です。この時でも、縮小画像同士を比べて、明らかに違う場合を「脚きり」するといった方法で高速化が可能です。
　でも、やりたいのは、角度やスケールに対応したサーチです。約１０年前、ＣＯＧＮＥＸ社のＰＡＴＭＡＸというサーチを見てから、「いつかは、こんなプログラムを作ってみたい」と思っておりました。それほど、衝撃的なプログラムだったのです。
　回転に対応するだけで、もう力技では解決できないような気になります。０．１度づつ回した画像でも作って、その全てと、全画素位置で比較して・・・今の進化したＰＣでも難しいでしょう。しかも、１０年前でもＰＡＴＭＡＸはわずか数十ｍＳで答えをハジきだしていたのです。
　回転に対応するためには、なんとなくベクトルでマッチングをする必要があるだろうなということは、想像できます。ベクトルを作るには、回転に対して強い、固定される点を求める必要があります。幸い前述の特徴点（コーナー）は回転しても抽出できているようですので、これとベクトルマッチングを使えば、パターンマッチング・マークサーチが可能になりそうです。

アルゴリズム

　まず、「マーク」を学習するということを考えます。この学習はマーク作成時に一度だけ行えばよいので、比較的時間がかかっても問題ない処理です。現在のアルゴリズムでやっているのは、
(1)特徴点の抽出
(2)特徴点の任意の２つが長い距離をとる組み合わせを３つ探す。
(3)１組み合わせをベクトルとして、その他の特徴点に対して、なす角と、辺比を求める
の３つです。(1)は、別ページで解説してありますので、ここでは、２，３について説明します。

図１　特徴点

　図１のように８つの特徴点が見つかったものとします。この８つのうち任意の２つを取り出し、その長さを求め、長い順に３候補を選びます。今回の場合 a-f 間 d-g 間 a-h間あたりが候補になりそうです。
　距離の長い２点を選ぶのは、距離の短い２点（例えばa-bの組み合わせなど）であれば、両方が消えてみえなくなる可能性があるなと思ったからです。ただ、同じ点を候補に選ぶこともあるので（今回でも、aは２回でてきます）同じ点を選ばないよう処理すべきかもしれません。また、３候補でいいのかも検討していません。この３候補のうち１候補でも検索で見つかれば、候補とすることができます。これが(2)の処理です。

図２　最長ベクトル

　(3)の処理は、３候補ともすべてに対して同じことを行いますので、ここでは、a-f間について説明します。
　当たり前ですが、図には、a-f以外にb,c,d,e,g,hの６つの点があります。この６つについて、a-fに対しての辺の比率、aを中心とした、「なす角」を求めます。例えば、bであれば、a-fとa-bの辺の長さ比は0.5くらいです。また、角bafは、40度くらいになります。なす角は、右回り、左回りで±をつけて求めておきます。プログラムでは時計周りを＋としましたので、角度は-40度になります。これらを全て計算しておきます。

　マークサーチ時には、a-fにあたる辺をイメージ上から、しらみつぶし的に探し、a-fに一致すると仮定する点a'-f'を求めます。この仮定の段階で、a-fに対する長さ許容範囲を設定することで、拡大縮小サーチに対応できます。
　そして、仮定したa'-f'と、なす角と距離比率の配列から、イメージ上に存在するであろう特徴点の位置(b',c',d',e',g',h')が求まります。２，３点なら見つからなくても良いといった処理を行えば、一部欠落サーチに対応できます。
　こうして求めた、点a'～h'を使って全ての組み合わせベクトルを作り、マーク上の同一組み合わせベクトルのなす角平均を、傾きとします。今回、市販画像ソフトで15度回した画像から、角度14.999097度を得ました。同様の処理でスケール（拡大率）も求めてみたのですが、こちらは、１５度傾いた画像だと、1.018倍となり、1.8%サイズアップしているという結果がでました。これは、傾きのある画像から特徴点を抽出すると、エッジに近づいたり、離れたりする傾向が、角度ごとにあるものと思われます。

　この処理で整数解では、回転を含んだサーチ一部欠落した画像のサーチを含めて、正しい値を求めることができました。プログラムは、まだ作っていませんが、最終処理としては、イメージからマークと思われる部分を、正しく逆回転させて大きめ（＋３ドットづつなど）に切り取り、マーク類似画像を作成します。そして、微分の縦合計、横合計などから、サブピクセル上のズレが最小になる点を求めるなどすると、答えが求まりそうです。このあたりの「最終マッチング」は、また別な機会に研究します。

結果

図３　試験マーク

図４　検索対象

図３の試験マークを図４の検索対象（640x480ドット）から探してみたところ、正しい２箇所(467,103),(288,221)を得ました。所要時間は31mSでした。（但し、まだ実数演算も多数あり、アルゴリズム的にも最適化を行っていない状態です）ちなみに左上の画像は、左右反転させてあるため、「発見できない」のが正解です。

無作為研究所トップページに戻る