説明
[グレイサーチ(正規化相関サーチ)]

グレイサーチとは
グレイサーチとは、正規化相関による8bit濃淡画像のパターンマッチングを利用したサーチプログラムの当社での通称です。
gs2_patmat.png

パターンマッチングの基本

  • M : サーチの基準にする、事前に用意した画像（パタン画像）
  • I : サーチの対象にする、撮像したばかりの画像（サーチ対象画像）
  • B : Mと比較するための、サーチ対象画像の部分画像

    上記の図において、パタン画像Mがサーチ対象画像Iのどこにあるかを探したいとします。 Mと同じサイズのIの部分画像B1とB2を取り出してきた時に、Mとどちらがより似ているかを数値化できれば、 Iの中の全ての部分画像に対して同様に比べることで最もMに似ている部分画像を見つけることができます。 グレイサーチではその似ている・似ていないという情報を相互相関係数として数値化し、一番似ている所を探します。
相互相関係数とは
いかなる画像であっても、相互相関係数 $R$ は $-1.0 \leq R \leq 1.0$ となります。 また、 $ R = 1.0 $ の場合が最もよく似ており、 $ R= -1.0 $ の場合が濃度反転している状況です。 分散を使用して計算しているため、パタン画像に対してサーチ対象画像の視野の明るさが変動した場合でも 相関係数の値はあまり変動しません。（サーチ対象画像の線形な輝度変動に対して頑健）
$R$は以下の式で与えられます。

\begin{eqnarray*} R &=& \frac{ V_{im} }{ \sqrt{ V_{input} \cdot V_{master} } }\\ V_{master} &=& \frac{1}{N}\sum_{n = 0}^{N-1}(M_n ^2) - \frac{1}{N^2}( \sum_{n = 0}^{N-1}M_n )^2\\ V_{input} &=& \frac{1}{N}\sum_{n = 0}^{N-1}(I_n ^2) - \frac{1}{N^2}( \sum_{n = 0}^{N-1}I_n )^2\\ V_{im} &=& \frac{1}{N}\sum_{n = 0}^{N-1}(M_n \cdot I_n) - \frac{1}{N^2} \sum_{n = 0}^{N-1}M_n \cdot \sum_{n = 0}^{N-1}I_n \end{eqnarray*}

ただし、
  • $N$ : サーチするパタンのPixel数
  • $M_n$ : パタン画像の第nピクセルの濃度値
  • $I_n$ : サーチエリアの部分画像の第nピクセルの濃度値
  • $R$ : 相互相関係数
  • $V$ : 分散
粗密探索と画像圧縮
パタン画像とサーチ対象画像の部分画像の間で全ての組み合わせを試し、 最も似ている部分画像を決定できればサーチ完了となります。 しかし、大きな画像でサーチすると極めて大きな処理時間がかかります。 小さな画像同士なら高速に計算できるため、サーチ前に画像を小さくしてからサーチを行います。
gs2_pyramid1.png

画像ピラミッド

グレイサーチでは縦横半分に縮小した画像「圧縮画像」を作成し、 圧縮画像をさらに複数回圧縮して複数枚の画像を持つ「画像ピラミッド」を生成します。 圧縮していない画像を圧縮度0の画像と呼び、縦横を $\frac{1}{2^{n}}$ にした画像を圧縮度nの画像と呼びます。
gs2_pyramid2.png

粗密探索

はじめに最も圧縮された小さな画像（図のLV3）においてサーチを実行し、回答候補を算出します。 候補点の周囲だけ次の大きさの画像（図のLV2）でサーチを行い、次第に大きな画像でサーチすることでわずかな処理時間で回答の精度を高めています。
FIEグレイサーチの簡単な使い方
gs2_how2use.png

使い方

FIEグレイサーチライブラリは3つの関数を使うだけでサーチを行うことができます。
まず fnFIE_gs2_alloc() で作業領域となるFIEグレイサーチオブジェクトを作成し、 次に fnFIE_gs2_pattern_alloc() でパターンにする画像からFIEグレイサーチパターンオブジェクトを作成します。 最後に fnFIE_gs2_search() または fnFIE_gs2_search_enforce2() のどちらかに上記二つのオブジェクトとサーチ対象にする画像を与えればサーチ完了です。 具体的なコードのサンプルは fnFIE_gs2_search() や fnFIE_gs2_search_enforce2() のドキュメントを参照してください。
FIEグレイサーチのデータとシリアライズ
  • FIEグレイサーチオブジェクトにはサーチ実行のための一時領域と継続サーチのための画像ピラミッドが格納されています。保存の必要はありません。
  • FIEグレイサーチパターンオブジェクトには以下のような情報が含まれています。
    gs2_pattern.png
    • パタン画像
    • マスク画像
    • 回答位置オフセット
    • 画像ピラミッド生成に使用したフィルタ
  • パタンを保存する場合、以下の4種の情報取得関数でパタンから情報や画像オブジェクトを取得し、個別に保存してください。 fnFIE_gs2_pattern_alloc() に以下で取得した情報を与えればまったく同じパタンが作成できます。
パラメータ解説
圧縮フィルタ filter
( fnFIE_gs2_pattern_alloc(), fnFIE_gs2_pattern_get_comp_filter(), fnFIE_gs2_pattern_set_comp_filter() )
圧縮画像生成時に使用するフィルタを指定します。
  • 通常（平均）フィルタ F_COMP_MODE_SMOOTH
    2x2の平均を圧縮画像の画素値とします。特に問題がなければこれを使用します。
  • 最小値フィルタ F_COMP_MODE_MIN
    2x2の最小値を圧縮画像の画素値とします。パタンが黒い細線で構成されているような場合に指定します。
  • 最大値フィルタ F_COMP_MODE_MAX
    2x2の最大値を圧縮画像の画素値とします。パタンが白い細線で構成されているような場合に指定します。
  • 再平均フィルタ F_COMP_MODE_AVERAGE2
    通常フィルタのあと再度平均化を行うフィルタです。画像にノイズが多い場合に指定します。
マークオフセット mark_offsetx, mark_offsety
( fnFIE_gs2_pattern_alloc(), fnFIE_gs2_pattern_get_offset(), fnFIE_gs2_pattern_set_offset() )
パタンの左上画素と、出力する回答位置の差をピクセル座標の100倍値で指定します。
サーチウインドウ search_window
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
gs2_window.png
サーチする範囲をサーチ対象画像上の座標で指定します。もし画像が512x480のサイズなら、(0,0)〜(511,479)が最大で画像の外に出るような指定はできません。
途中相関値 threshold_mid
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
サーチ途中での候補の絞り込みに使います。 値は 0 〜 9999 で、相互相関係数の一万倍値です。 サーチ開始圧縮度の処理からサーチ終了圧縮度の処理まで共通して利用します。
最終相関値 threshold_final
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
サーチ完了時での回答の絞り込みに使います。値は 0 〜 9999 で、相互相関係数の一万倍値です。 サーチ終了圧縮度での処理で利用します。
反転パタン検出モード reverse_mode
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
gs2_rvsptn.png
TRUEのとき反転パタンを検出し、FALSEのときは検出しません。 圧縮フィルタ指定で最小値フィルタや最大値フィルタを指定している場合には、 反転パタンは圧縮度が上がるほどスコアが落ちるので反転パタン検出モードTRUEとの組み合わせはお勧めしません。
サーチウインドウ周囲接触フラグ edge_detect
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
gs2_window_edge_detect.png
図のaとcはフラグにかかわらずサーチしますが、bをサーチするかどうかに影響します。 （回答位置がサーチウインドウに接触した場合の処理ではなく、パタン画像がサーチウインドウに接触した場合の処理に影響します。） TRUEで検出、FALSEで検出しません。
ピッチ pitch_x, pitch_y
( fnFIE_gs2_search(), fnFIE_gs2_search_enforce(), fnFIE_gs2_search_enforce2() )
グレイサーチでは近い範囲に複数のサーチ結果が出た場合、相関係数がより1.0に近いものだけを残します。
gs2_pitch.png
図で X_diff < Pitch_x かつ Y_diff < Pitch_y のとき、サーチ結果は相関値の高いほうのみ採用されます。
サーチ開始圧縮度、サーチ終了圧縮度、サーチ複雑度、サーチ精度
gs2_comp_level.png
超高精度・高精度・通常精度の精度指定はサーチ終了圧縮度を直接指定するのと同じです。 複雑度指定を使うと、パタン画像の分散値を考慮してサーチ開始圧縮度を自動決定してくれます。 複雑度を高く設定するほど、開始圧縮度が低めになります。
ウルトラ超高精度の精度指定はサーチ終了圧縮度を0に指定し、サブピクセル推定の近傍指定を8近傍に指定するのと同じです。
精サーチ・サブピクセル推定の近傍指定 subpxl_neib
( fnFIE_gs2_search_enforce2() )
サーチ終了圧縮度でサーチ位置のサブピクセル推定に用いる近傍の数を指定します。 8近傍の方が精度向上します。4近傍ではFVLのグレイサーチ等従来の製品と同じアルゴリズムで計算します。
サーチ精度指定あるいは近傍指定による精サーチ・サブピクセル推定の違い
通常精度、高精度、超高精度の各精度の指定、あるいは4近傍指定では、 各座標軸方向独立に、相関値に2次関数をあてはめ、その頂点位置を各方向におけるサブピクセル位置としています。 このため，例えば下図のように、ｘ軸方向における相関値のピーク点 γ が真値 α からずれてしまうことがあります。
gs2_subpixel.png
一方、ウルトラ超高精度の指定、あるいは8近傍指定では、 相関値ピーク点近傍9点に2次元ガウス関数をあてはめ、その頂点位置をサブピクセル位置としているため、 精度良く位置推定を行うことができます。
gs2_2dim_gaussian.png

2次元ガウス関数

TIPS:
うまくみつからないときは
  • サーチ開始圧縮度でパタンが圧縮されすぎて形状が崩れているのが原因の場合、 サーチ開始圧縮度を下げてあまり圧縮されていないパターンにすればみつかります。
  • パターンが幅数画素程度の白くて細い線でつくられていて、サーチ開始圧縮度でパタンが圧縮されすぎて形状が崩れているのが原因の場合、 圧縮フィルタを F_COMP_MODE_MAX にすればみつかります。
  • パターンが幅数画素程度の黒くて細い線でつくられていて、サーチ開始圧縮度でパタンが圧縮されすぎて形状が崩れているのが原因の場合、 圧縮フィルタを F_COMP_MODE_MIN にすればみつかります。
  • fnFIE_gs2_search() で自動決定された圧縮度が高すぎるのが原因の場合、 fnFIE_gs2_search_enforce() ,fnFIE_gs2_search_enforce2() を使ってサーチ開始圧縮度を下げて強制指定すればみつかります。
  • サーチ対象画像においてサーチしたいものがノイズが多かったり形が安定しないような場合、パターン画像との相関値があまり高くなりません。 途中相関値や最終相関値を下げると、それまで厳しすぎて候補から外していたサーチ対象を発見できます。
  • サーチウインドウが狭すぎたり、マークオフセットを含めた座標を指定するのだと誤解して指定しているのが原因で、 サーチするべき場所を探していない場合があります。適切に設定すれば見つかります。
  • サーチ結果取得個数が少なすぎるのが原因でほしい個数の結果が得られないことがあります。増やせば見つかります。
  • サーチ結果取得個数を少なく設定していると、極めて類似したものがサーチウインドウ内に混在し、そちらを優先的に見つけて要求した個数に達しているために発見したい方の対象を回答しないことがあります。 サーチ取得個数を増やせばみつかるので他の手段で判別してください。類似のものをサーチウインドウから外してサーチすることでもみつかります。
  • ピッチを広く指定した場合、ピッチ内でもっとも相関値の高いもの一つだけを回答するので距離の近いものはサーチしません。ピッチを狭く設定するとみつかります。 デフォルトの0を指定した場合にもパターンサイズの半分が採用されるため1以上で明示的に指定します。
  • 圧縮フィルタが F_COMP_MODE_MIN や F_COMP_MODE_MAX になっていると、反転パタンを上手く検出できないことがあります。 画像圧縮の過程で元の画像を反転してから圧縮する場合と圧縮してから反転する場合の画像が大きく異なるためです。 圧縮フィルタをF_COMP_MODE_SMOOTH にするとみつかります。
サーチが遅いときは
  • 処理する画像が大きいと遅くなります。
    • パターン画像が不必要に大きくないか検討し、小さくします。
    • サーチ対象画像を画像全体ではなく小さなチャイルド画像にします。 同じサーチ対象画像に対して様々なサーチウインドウで継続サーチを行う場合を除き、サーチウインドウを小さくするより効果的です。 ただし、チャイルド画像の原点がサーチ結果やサーチウインドウの原点になってしまうので注意。
  • 圧縮度の設定が適切でないと遅くなります。
    • サーチ開始圧縮度での探索はサーチ対象画像とパターン画像を全ての組み合わせで比較するため時間がかかります。サーチ開始圧縮度をあげると小さな画像同士で比較するため高速になります。
    • 高精度な結果を求めるには時間がかかります。サーチ精度を通常精度にしたり、サーチ終了圧縮度をあげたりしてみましょう。
  • サーチ結果の候補が多数になると遅くなります。
    • 途中相関値を上げると探索の途中で断念する候補が増え、高速になります。
    • サーチウインドウを小さくして探索の当初から候補を減らすと高速になります。
  • マスクのあるパターンの処理はマスクのないパターンより時間がかかるので、可能ならマスクをはずします。
  • 同一のサーチ対象画像の圧縮ピラミッドを何度も作成すると無駄に時間がかかります。 全く同一のサーチ対象画像に対して複数のパタンをサーチする場合、継続サーチにすると一度で済ませることができます。

Documentation copyright © 2009-2024 FAST Corporation.
Generated on Fri Aug 9 16:38:47 2024 for FIEライブラリ by doxygen 1.5.6-FASTSP-p2