(57)【要約】【課題】  デジタル画像のエッジの位置を特定する。【解決手段】  画像内において、ゼロ交差するピクセル位置ｎ０が識別され（１１）、サブピクセル位置オフセットａが決定される（２１）。このオフセットは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である。最後に、ピクセル位置ｎ０およびサブピクセル位置オフセットａから、エッジ位置の補間された位置ｔ０が決定される（２６）。検出されたエッジをモデルオブジェクトのエッジと整合させるため、画像内のオブジェクトの検出されたエッジと、モデルオブジェクトの対応するエッジとの間の並進［ｖ１，ｖ２］が決定され（４４）、検出されたエッジと、対応するモデルのエッジとの相互相関が計算され（４６）、並進誤差［ｅ１，ｅ２］が決定される（４８）。
2005525607.tif 000002
【特許請求の範囲】
【請求項１】
画像内において、ゼロ交差するピクセル位置ｎ０を識別すること（１１）、
前記ゼロ交差するピクセル位置におけるサブピクセル位置オフセットａを決定すること（２１）であって、前記オフセットａは、前記ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である、決定すること（２１）、および
前記ピクセル位置ｎ０および前記サブピクセル位置オフセットａを使用して、前記画像のエッジ位置ｔ０を決定すること（２６）
を含む画像処理方法。
【請求項２】
所望のスケールの１次微分フィルタＭ（ｔ）を決定すること（１２）
をさらに含み、
Ｍ（ｔ）は、不連続点が整数点に位置する不連続な区分線形関数である
請求項１に記載の画像処理方法。
【請求項３】
第１の離散フィルタ列Ｆ１を決定するステップ（１６）と、
第２の離散フィルタ列Ｆ２を決定するステップ（１６）と、
第３の離散フィルタ列Ｆ３を決定するステップ（１６）と、
前記第１の離散フィルタを使用して前記画像をフィルタリングすること（１８）であって、それによって、第１の相関値Ｙ１［ｎ０］を含む相関列を求める、前記画像をフィルタリングするステップ（１８）と、
前記相関列を使用して、前記ゼロ交差するピクセル位置ｎ０を特定するステップ（２０）と、
前記第２の離散フィルタ列を使用して、前記ピクセル位置ｎ０において前記画像をフィルタリングすること（２２）であって、それによって、第２の相関値Ｙ２［ｎ０］を得る、前記画像をフィルタリングするステップ（２２）と、
前記第３の離散フィルタ列を使用して、前記ピクセル位置ｎ０において前記画像をフィルタリングすること（２２）であって、それによって、第３の相関値Ｙ３［ｎ０］を得る、前記画像をフィルタリングするステップ（２２）と
をさらに含む請求項１に記載の画像処理方法。
【請求項４】
以下の２次関係の解を求めることによって、サブピクセルオフセットを決定すること（２４）
をさらに含む
請求項３に記載の画像処理方法。
０＝Ｙ１［ｎ０］−（Ｙ２［ｎ０］＊ａ）＋（Ｙ３［ｎ０］＊ａ＊（１−ａ））
【請求項５】
ａ．画像内のオブジェクトの検出されたエッジ位置と、モデルオブジェクトの対応するエッジ位置との間の並進［ｖ１，ｖ２］を決定すること（４４）、
ｂ．前記検出されたオブジェクトのエッジ位置と前記対応するモデルのエッジ位置との相互相関を決定すること（４６）、
ｃ．並進誤差ベクトル［ｅ１，ｅ２］を決定すること（４８）、および
ｄ．前記並進を更新すること（５０）
を含む画像処理方法。
【請求項６】
前記モデルのエッジの相関行列Ｖが、以下の数式として定義される場合において、前記モデルのエッジの逆相関行列Ｖ−１を決定すること（４２）
をさらに含む請求項５に記載の画像処理方法。
【数１】
2005525607.tif 000017
上記数式において、
【数２】
2005525607.tif 000018
および
【数３】
2005525607.tif 000019
は、それぞれ第１の軸および第２の軸におけるＬ［ｋ，ｊ］の離散微分である。
【請求項７】
画像処理装置（６０）であって、
プロセッサ（６２）と、
前記プロセッサ（６２）に接続された記憶装置（６４）であって、前記プロセッサ（６２）が、
画像内において、ゼロ交差するピクセル位置ｎ０を識別すること（１１）、
前記ゼロ交差するピクセル位置におけるサブピクセル位置オフセットａを決定すること（２１）であって、前記オフセットａは、前記ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である、決定すること（２１）、および
前記ピクセル位置ｎ０および前記サブピクセル位置オフセットａを使用して、前記画像のエッジ位置ｔ０を決定すること（２６）
を行うようにする命令
を含む記憶装置（６４）と
を備える画像処理装置。
【請求項８】
画像処理装置（６０）であって、前記記憶装置（６４）は、前記プロセッサが、
第１の離散フィルタ列Ｆ１を決定すること（１６）、
第２の離散フィルタ列Ｆ２を決定すること（１６）、
第３の離散フィルタ列Ｆ３を決定すること（１６）、
前記第１の離散フィルタを使用して前記画像をフィルタリングすること（１８）であって、それによって、第１の相関値Ｙ１［ｎ０］を含む相関列を求める、前記画像をフィルタリングすること（１８）、
前記相関列を使用して、前記ゼロ交差するピクセル位置ｎ０を特定すること（２０）、
前記第２の離散フィルタ列を使用して、前記ピクセル位置ｎ０において前記画像をフィルタリングすること（２２）であって、それによって、第２の相関値Ｙ２［ｎ０］を得る、前記画像をフィルタリングすること（２２）、および
前記第３の離散フィルタ列を使用して、前記ピクセル位置ｎ０において前記画像をフィルタリングすること（２２）であって、それによって、第３の相関値Ｙ３［ｎ０］を得る、前記画像をフィルタリングすること（２２）
を行うようにする命令をさらに含む
請求項８に記載の画像処理装置。
【請求項９】
前記画像処理装置（６０）であって、前記画像を解析のために取り込む画像取り込みデバイス（６８）に接続される
請求項８に記載の画像処理装置。
【請求項１０】
画像処理装置（６０）であって、
プロセッサ（６２）と、
前記プロセッサ（６２）に接続された記憶装置（６４）であって、前記プロセッサ（６２）が、
画像内のオブジェクトの検出されたエッジ位置と、モデルオブジェクトの対応するエッジ位置との間の並進［ｖ１，ｖ２］を決定すること（４４）、
前記検出されたオブジェクトのエッジ位置と前記対応するモデルのエッジ位置との相互相関を決定すること（４６）、
並進誤差ベクトル［ｅ１，ｅ２］を決定すること（４８）、および
前記並進を更新すること（５０）、
を行うようにする命令
を含む記憶装置（６４）と
を備える画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル画像の処理技術に関する。
特に、本発明は、デジタル画像のエッジの位置を特定する技術に関する。
【背景技術】
【０００２】
多くの外観検査の用途、例えば、製造中の作業管理および品質保証では、正確なエッジ検出および測定が不可欠である。
製造された物品のエッジを検出する、すなわちエッジの位置を特定するために、その商品の１つまたは２つ以上の画像が取り込まれる。
コンピュータビジョンまたはマシンビジョンの用途では、取り込まれた画像は、通常、２次元（２Ｄ）ピクセルアレイによって表される。
各ピクセルは、１つのグレー値（または色を表す３つの値）を有する。
その後、画像は、例えば、取り込んだ画像のオブジェクトの位置を決定するために、計算機によって処理されて、エッジ検出が行われる。
【０００３】
大きな画像を処理する場合のハードウェアコストおよび多くの計算必要量を低減するために、画像は、アンダーサンプリングされることが多く、また、処理アルゴリズム（例えばエッジ検出）の各部は、サブピクセルの測定に頼ることが多い。
２Ｄ離散グリッド上にサンプリングされた（オブジェクトの）グレー値画像が与えられると、サブピクセルの精度でオブジェクトのエッジの位置を推定することができる。
【０００４】
サブピクセルのエッジ検出は、自然画像に共通の２つの特性、すなわち、（１）近傍のピクセル間に存在する高い空間相関、および、（２）サブピクセルのエッジ位置を示す中間グレー値、に依拠する。
これらの特性を使用して画像のエッジを検出するいくつかの方法が存在する。
【０００５】
例えば、まず、補間を使用して、画像が拡大ズームされる。
この状況で、補間により、ピクセル値が原画像の近傍のピクセル値から数学的に推定された拡大画像が作成される。
次に、１つまたは２つ以上のエッジ検出カーネル（フィルタとも呼ばれる）を使用して、ズーム画像がフィルタリングされ、それによって、エッジが強調され、検出される。
すなわちエッジの位置が特定される。
フィルタリングプロセスでは、２つのアレイの数値（例えば、補間画像およびフィルタカーネル）が合成積されて、第３のアレイの数値が作成される。
このようなエッジ検出フィルタは、補間画像の２次微分を効率的に取得することができる。
エッジは、２次微分がゼロ値と交差するピクセルの境界に位置する。
この技法は、ゼロクロス技法と呼ばれることが多い。
このゼロクロス技法およびフィルタリングステップは、当該技術分野において既知である。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
この方法の１つの欠点は、計算コストが高いこと、および、精度を上げるのに計算能力を上げる必要があることである。
例えば、Ｎ×Ｎ画像（例えば１００×１００の２Ｄグリッド画像）のサブピクセルのエッジを検出するには、まず、画像が、補間によって増倍率（例えば２、４、または別の整数）だけ拡大される。
係数４を補間に使用すると、１００×１００の画像（合計１０，０００ピクセルを有する）は、４００×４００の画像（合計１６０，０００ピクセルを有する）に補間される。
次に、拡大された補間画像に対してフィルタリングステップ（計算集約的なステップ）が実行されて、画像のエッジが見つけ出される。
このエッジ検出プロセスの精度を向上させるには、より大きな原画像を取り込むか、または、補間ステップの増倍率を大きくすることが行われる。
いずれにしても、フィルタリングステップの計算必要量は、補間画像のサイズの増加の２乗で増加する。
【０００７】
計算コストを増加させることなく、エッジ検出精度を向上させる技法に対するニーズが存在する。
【課題を解決するための手段】
【０００８】
［概要］
上記ニーズは、本発明によって満たされる。
本発明の第１の態様によると、画像処理方法が開示される。
まず、画像内において、ゼロ交差するピクセル位置ｎ０が識別される。
次に、サブピクセル位置オフセットａが求められる。
このオフセットは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である。
最後に、画像のエッジ位置ｔ０が、ピクセル位置ｎ０およびサブピクセル位置オフセットａを使用して決定される。
【０００９】
本発明の第２の態様によると、画像処理方法が開示される。
まず、画像内のオブジェクトの検出されたエッジ位置と、モデルオブジェクトの対応するエッジ位置との間の並進［ｖ１，ｖ２］が求められる。
次に、検出されたオブジェクトのエッジ位置と対応するモデルオブジェクトのエッジ位置との相互相関が決定される。
次に、並進誤差ベクトル［ｅ１，ｅ２］が計算される。
最後に、並進が更新される。
【００１０】
本発明の第３の態様によると、プロセッサと、このプロセッサに接続された記憶装置とを含む画像処理装置が開示される。
この記憶装置は、プロセッサが、画像内において、ゼロ交差するピクセル位置ｎ０を識別すること、サブピクセル位置オフセットａを決定することであって、このオフセットは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である、決定すること、およびピクセル位置ｎ０およびサブピクセル位置オフセットａを使用して、画像のエッジ位置ｔ０を決定することを行うようにする命令を有する。
【００１１】
本発明の第４の態様によると、プロセッサと、このプロセッサに接続された記憶装置とを含む画像処理装置が開示される。
この記憶装置は、プロセッサが、画像内のオブジェクトの検出されたエッジ位置と、モデルオブジェクトの対応するエッジ位置との間の並進［ｖ１，ｖ２］を決定すること、検出されたオブジェクトと、対応するモデルのエッジとの相互相関を決定すること、並進誤差ベクトル［ｅ１，ｅ２］を決定すること、および並進を更新することを行うようにする命令を有する。
【００１２】
本発明の第５の態様によると、コンピュータ用の製品が開示される。
この製品には、コンピュータメモリが含まれる。
このコンピュータメモリには、プログラムが記憶される。
このプログラムは、実行されると、画像内において、ゼロ交差するピクセル位置ｎ０を識別すること、サブピクセル位置オフセットａを決定することであって、このオフセットは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である、決定すること、およびピクセル位置ｎ０およびサブピクセル位置オフセットａを使用して、画像のエッジ位置ｔ０を決定することをコンピュータに行わせる。
【００１３】
本発明の第６の態様によると、コンピュータ用の製品が開示される。
この製品には、コンピュータメモリが含まれる。
このコンピュータメモリには、プログラムが記憶される。
このプログラムは、実行されると、画像内のオブジェクトの検出されたエッジ位置と、モデルオブジェクトの対応するエッジ位置との間の並進［ｖ１，ｖ２］を決定すること、検出されたオブジェクトのエッジ位置と、対応するモデルのエッジ位置との相互相関を決定すること、並進誤差ベクトル［ｅ１，ｅ２］を決定すること、および並進を更新することをコンピュータに行わせる。
【００１４】
本発明の他の態様および利点は、本発明の原理を一例として示した添付図面と共に以下の詳細な説明を読むことにより明らかになる。
【発明を実施するための最良の形態】
【００１５】
例示の目的で図面に示すように、まず、画像内においてゼロ交差するピクセル位置ｎ０を識別することにより、エッジ位置を検出、すなわち決定する画像処理方法に本発明を具体化する。
ゼロ交差するピクセル位置ｎ０は、ピクセルのグレースケール値が、その近傍のピクセルに対して最も急激に変化する箇所であり、したがって、そのピクセル位置は、エッジの位置である可能性が最も高い。
このピクセルは、ピクセルのグレー値を表す画像信号の２次微分の値がゼロであるピクセル位置を特定することによって、見つけることができる。
【００１６】
エッジの位置は、ピクセル位置ｎ０からのオフセットａを決定することによりさらに精緻化される。
本明細書で以下に詳述するように、オフセットａは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係を使用して、ある程度見つけられる。
本発明の方法によると、計算コストの高いフィルタリングステップを、補間画像（通常、より大きな画像）の代わりに原画像に対して実行することにより、エッジを検出する計算必要量を大部分削減する。
【００１７】
サブピクセルのエッジ検出
画像サンプル、専門用語、および概要
図１Ａは、光学的にアンダーサンプリングすることにより、不明確になったエッジを有する２Ｄ画像サンプルを示している。
図１Ａでは、エッジは、灰色エリア内に存在する。
この灰色エリア内では、ピクセル番号（位置）が増加するにつれて、グレー値が階段状に次第に明るくなっている。
図１Ｂは、図１Ａの直線Ａ−Ａにおける２Ｄ画像サンプルの正規化したピクセル値を示している。
これらのピクセル値は、直線Ａ−Ａにおける単一列のピクセルの１次元（１Ｄ）データ点として示されている。
簡潔にするために、データ点を、集合的に、離散関数ｘ［ｎ］と総称する。
ここで、ｎは、離散値（ピクセル位置）であり、ｘ［ｎ］は、位置ｎにおけるピクセルのグレー値である。
【００１８】
図１Ａおよび図１Ｂに示すこの例では、ｎは、ピクセル位置のインデックスであり、１および２０を含めて１から２０の範囲を有する。
ここでは、１次元（１Ｄ）アレイｘ［ｎ］のエッジ検出について解説する。
しかしながら、本発明は、多次元画像に適用可能であり、多次元画像では、例えば、このような１Ｄ位置測定を少なくとも２回使用して、２Ｄ画像のエッジのサブピクセル位置が決定されることが明らかである。
【００１９】
１Ｄ関数ｘ［ｎ］により表される画像が与えられた場合、補間関数ｘ（ｔ）が、離散関数ｘ［ｎ］の直線補間を表し、図１Ｂに曲線６として示されている。
関数ｘ（ｔ）において、ｔは、サブピクセルの位置パラメータであり、ｘ（ｔ）は、補間位置ｔにおける補間されたグレー値である。
【００２０】
ｔがｎと等しい場合、関数ｘ（ｔ）はｘ［ｎ］と等しい。
ｔがｎと等しくないが、２つの離散点ｎ−１とｎとの間にある場合、ｔは、次の式として表される。
ｔ＝ｎ−１＋ａ                                                  （Ｅｑ．１）
上記式で、ａは、０と１の間の値を有するオフセット値である。
【００２１】
方程式Ｅｑ．１を補間関数ｘ（ｔ）に適用すると、ｘ（ｔ）を次のように表すことができる。
ｘ（ｔ）＝（１−ａ）ｘ［ｎ−１］＋ａｘ［ｎ］
【００２２】
この方程式は、Ｅｑ．１が次のように書き換えることができることによるものである。
ｔ＝（１−ａ）（ｎ−１）＋ａｎ
【００２３】
本発明の一実施の形態による方法は、図２のフローチャート１０を使用して説明することができる。
要約すると、本発明の技法は、３つの主なステップを含む。
１つ目は、破線のボックス１１に示すように、画像内において、ゼロ交差するピクセル位置ｎ０を識別することである。
２つ目は、破線のボックス２１に示すように、ゼロ交差するピクセル位置におけるサブピクセル位置オフセットａを決定することである。
このオフセットａは、ゼロ交差するピクセル位置における補間画像と補間カーネルとの関係である。
そして、３つ目は、ボックス２６に示すように、ピクセル位置ｎ０およびサブピクセル位置オフセットａを使用して、画像のエッジ位置ｔ０を決定することである。
ボックス、すなわちステップ１１および２１は、本明細書で以下に解説するように、より詳細なステップを含む。
【００２４】
エッジ検出に使用する１次微分フィルタの決定
さらに、図２では、最初のステップ（手順ボックス１２で示す）において、所望の１次微分フィルタ（「所望のフィルタ」）が決定される。
この所望のフィルタは、不連続点が整数点にのみ存在する、潜在的に不連続な区分線形形状を有するエッジ検出フィルタである。
図３Ａは、Ｍ（ｔ）として示す、このような１次微分エッジ検出フィルタの例としての曲線３０を示している。
図３Ａに示すサンプルの関数Ｍ（ｔ）３０は、区分線形であり、不連続点が離散的な整数点に存在する。
関数Ｍ（ｔ）３０は、所与のスケールで１次微分を離散近似したものである。
【００２５】
一般に、マスク関数Ｍ（ｔ）のプロファイルがガウス関数の１次微分と類似し、ガウシアンの分散（シグマ）が、対応するエッジのスケールとなるマスク関数Ｍ（ｔ）と合成積することにより、１次微分のよい近似が得られる。
【００２６】
ガウシアンの微分および整合フィルタの目当てとするプロファイル（matched filter motivated profile）の双方は、スケールの概念を有する。
整合フィルタは、通信および信号処理の技術分野で既知である。
整合フィルタは、カーネルプロファイルが（ミラーリングおよび並進次第で）予測信号と同一となるフィルタである。
整合フィルタは、「白色ガウス雑音」（ほとんどの通信システムの雑音の優れたモデル）内で所与の信号の特定する最適なフィルタである。
ガウシアンの標準偏差パラメータおよび予測エッジのブラーは、予測エッジのスケールのインジケータである。
一般に、予測スケールよりも小さなスケールのエッジは、テクスチャまたは雑音を表すことがあり、適切なスケールでは互いに打ち消し合うことがある。
一方、予測エッジよりも大きなスケールのエッジは、例えば、平面の照度の変動の一部であることがある。
【００２７】
それにもかかわらず、Ｍ（ｔ）は、必ずしも上記近似のいずれかであるとは限らない。
関数Ｍ（ｔ）３０は、微分の異なる近似の例である。
サンプルの関数Ｍ（ｔ）の水平方向の−５から５までの範囲のピクセルは、異なる用途では異なることがある（通例、所望のエッジのスケールに比例する）ことに留意されたい。
【００２８】
微分フィルタのパラメータの決定
Ｍ（ｔ）を使用することにより、パラメータ関数ｂ［ｎ］およびｄ［ｎ］が決定される（図２のステップ１４）。
これらのパラメータは、空間スケールの微分フィルタＭ（ｔ）を記述し、フィルタ、すなわちカーネルを構成するのに使用することができる。
このカーネルは、その後、エッジ位置をさらに精緻化するのに使用される。
【００２９】
整数点にのみ不連続点を有する潜在的に不連続なあらゆる区分線形関数、例えばＭ（ｔ）は、以下の一般式によって表すことができるので、パラメータ関数ｂ［ｎ］およびｄ［ｎ］を使用して、Ｍ（ｔ）を記述することができる。
【００３０】
【数４】
2005525607.tif 000003
【００３１】
上式において、ｔは、位置パラメータであり、
ｄ［ｉ］は、区間［ｉ，ｉ＋１］のスカラのランプパラメータ（ramp parameter）であり、ランプパラメータ関数と呼ぶことができ、
ｂ［ｉ］は、区間［ｉ，ｉ＋１］のスカラのバイアスパラメータであり、ステップパラメータ関数と呼ぶことができ、
ｒ（ｔ）は、以下の式で表されるランプ関数であり、
【００３２】
【数５】
2005525607.tif 000004
【００３３】
μ（ｔ）は、以下の式で表されるステップ関数であり、
【００３４】
【数６】
2005525607.tif 000005
【００３５】
すべてのパラメータ関数ｂ［ｎ］およびｄ［ｎ］（定義されない値は０とみなされる）をカバーするように、インデックスｉのすべてにわたって、総和が求められる。
【００３６】
ステップパラメータ関数ｂ［ｎ］は、Ｍ（ｔ）のバイアス列であり、この場合、ｂ［ｎ］は、区間［ｎ，ｎ＋１］のＭ（ｔ）の平均値となる。
この平均値は、その線形性のため、次の式で表される。
ｂ［ｎ］＝（Ｍ（ｎ）＋Ｍ（ｎ＋１））／２
【００３７】
ランプパラメータ関数ｄ［ｎ］は、Ｍ（ｔ）のランプ列であり、この場合、ｄ［ｎ］は、区間［ｎ，ｎ＋１］のＭ（ｔ）の傾きである。
この傾きは、次の式で表される。
ｄ［ｎ］＝（Ｍ（ｎ）−Ｍ（ｎ＋１））／２
【００３８】
ステップパラメータ関数ｂ［ｎ］のサンプルを、図３Ｂの曲線３０ｂとして示す。
ランプパラメータ関数ｄ［ｎ］のサンプルを、図３Ｃの曲線３０ｄとして示す。
【００３９】
離散フィルタ列の決定
次に、本明細書で上記に定義したパラメータ列を使用して、３つのフィルタ列が決定される（ステップ１６）。
これらのフィルタ列は、空間的次元に使用されて、エッジｎ０を含むピクセルを特定し、以下にさらに説明するように、ピクセル位置ｎ０の近傍の画像の補間関数を記述する多項式の係数を求める。
【００４０】
第１の離散ステップフィルタＦ１は、ステップパラメータ関数ｂ［ｎ］と［１，−１］との合成積であり、次の式で表される。
Ｆ１＝［…ｂ−１，ｂ０，ｂ１，ｂ２，…］＊［１，−１］
すなわち、
Ｆ１［ｉ］＝ｂ［ｉ＋１］−ｂ［ｉ］
【００４１】
第２の離散フィルタＦ２は、ステップパラメータ関数ｂ［ｎ］と［１，−２，１］との合成積であり、次の式で表される。
Ｆ２＝［…ｂ−１，ｂ０，ｂ１，ｂ２，…］＊［１，−２，１］
すなわち、
Ｆ２［ｉ］＝ｂ［ｉ＋１］−２ｂ［ｉ］＋ｂ［ｉ−１］
【００４２】
第３の離散フィルタＦ３は、ランプパラメータ関数ｄ［ｎ］と［１，−２，１］との合成積であり、次の式で表される。
Ｆ３＝［…ｄ−１，ｄ０，ｄ１，ｄ２，…］＊［１，−２，１］
すなわち、
Ｆ３［ｉ］＝ｄ［ｉ＋１］−２ｄ［ｉ］＋ｄ［ｉ−１］
【００４３】
第１の離散フィルタを使用した画像のフィルタリング
次に、ステップ１８で、（特定されるエッジがクロスするエリアの画像の）１Ｄ離散列ｘ［ｎ］のピクセル値が、フィルタＦ１によってフィルタリングされる。
この時、原画像は、第１のフィルタＦ１と相関し、すなわちフィルタリングされて、ゼロ交差するピクセルが決定される。
この相関ステップの結果は、第１の相関列Ｙ１［ｎ］となる。
ここで、Ｙ１［ｎ］は次のようになる。
【００４４】
【数７】
2005525607.tif 000006
【００４５】
上式において、ｋは、Ｆ１のエントリを定義する範囲をカバーする。
ｎは、ｘのエントリを定義する範囲をカバーする。
【００４６】
第１の相関列を使用したゼロ交差するピクセルｎ０の特定
ステップ２０で、ゼロ交差が起こるピクセル位置ｎ０が決定される。
これは、Ｙ１［ｎ０］＋Ｙ１［ｎ０−１］がゼロ（０）以下となるピクセル位置ｎ０である。
ｘ［ｎ］が、Ｍ（ｔ）を設計したスケールで単一のエッジと交差するものと仮定すると、ｎ０は１つだけとなる。
【００４７】
ｎ０における相関値の決定
次に、ステップ２２で、画像ｘ［ｎ］は、ゼロ交差するピクセル位置ｎ０においてのみ、フィルタＦ１、Ｆ２、およびＦ３によりフィルタリングされ、すなわちこれらのフィルタと相関して、次のような３つの相関値が求められる。
【００４８】
【数８】
2005525607.tif 000007
【００４９】
ゼロ交差するピクセル位置においてのみ、これらの相関値を決定する必要があるので、計算オーバヘッドの多くが削減されることに留意されたい。
ｎ０における相関値Ｙ１［ｎ０］、Ｙ２［ｎ０］、およびＹ３［ｎ０］のそれぞれは、スカラ値である。
第１の相関値Ｙ１［ｎ０］は、前のステップから入手できる。
【００５０】
オフセットの決定
次のステップ２４では、以下の２次方程式を変数ａについて解くことにより、オフセット値ａが決まる。
０＝Ｙ１［ｎ０］−（Ｙ２［ｎ０］＊ａ）＋（Ｙ３［ｎ０］＊ａ＊（１−ａ））
【００５１】
この２次方程式の解は、当該技術分野において一般に既知である。
値０と値１との間では、この方程式が単一解を有することが容易に検証され、その解が、我々の用途の所望の解である。
【００５２】
サブピクセルのエッジ位置の決定
最後に、ステップ２６で、オフセットａが使用され、かつ、以下の式が使用されて、ピクセル位置ｎ０におけるサブピクセルのエッジ位置ｔ０が決定される。
ｔ０＝ｎ０−１＋ａ
【００５３】
本技法の多次元画像への拡張
２次元（２Ｄ）画像の場合、各エッジ点を［ｔ１−０，ｔ２−０］として表すことができる。
ここで、ｔ１−０は、第１の軸（例えばｘ軸）のエッジ位置パラメータであり、ｔ２−０は、第２の軸（例えばｘ軸と直交するｙ軸）のエッジ位置パラメータである。
図示したステップを、同じ直線エッジまたはそれ以外にパラメータで定義されたエッジを横切る複数の行および列に対して繰り返すことができ、それによって、解析中の画像のエッジの位置が決定される。
【００５４】
概ね直線に配置されたエッジを有する２Ｄ画像の場合、その直線エッジの位置を決定するために、上述したステップを使用すると、直線エッジのいくつかの（少なくとも２つ）のエッジ点を見つけることができる。
概ね円形に配置されたエッジを有する２Ｄ画像の場合、その円形エッジの位置を決定するために、上述したステップを使用すると、円形エッジのいくつかの（少なくとも３つ）のエッジ点を見つけることができる。
２Ｄ画像は、その離散形式ではｘ［ｋ，ｊ］と表すことができ、その補間形式ではｘ（ｔ１，ｔ２）と表すことができる。
【００５５】
線形適合アルゴリズム（linear fitting algorithm）またはパラメータ適合アルゴリズム（parametric fitting algorithm）により多くのエッジ位置の測定を使用して、エッジを記述するパラメータを決定することができる。
次に、それらのパラメータを使用して、エッジ全体を決定することができる。
パラメータ曲線上の点を使用してパラメータ関数を決定するパラメータ適合アルゴリズムは、当該技術分野で既知である。
【００５６】
検出したエッジのモデルのエッジとの比較
（解析中の画像のオブジェクト、すなわち「検出したオブジェクト」の）検出したエッジ位置を、事前に構成されたデータベースのモデルオブジェクトの既知のエッジ位置と比較することにより、画像のエッジの位置をさらに精緻化することができる。
図４のフローチャート４０は、検出したオブジェクトをモデルオブジェクトデータと相関させる一方法を示している。
この技法の目標は、検出した画像のモデルを使用して、モデルと画像との相互相関のピークとしてパターンおよび整合を特定することである。
【００５７】
この方法は、グレー値情報だけでなく、空間データも利用する。
サブピクセルの精度については、上記の方法と類似して、（検出したオブジェクトおよびモデルオブジェクトの双方の）エッジが、補間により拡大され、サブピクセルの位置が決定される。
前節で使用した方法と類似して、直接補間を省略することができ、相互相関関数に補間を適用することができる。
【００５８】
ここで、相互相関項を、（計算の複雑さの観点から）より便利な平均２乗誤差（ＭＳＥ）の量に置き換えるものとする。
したがって、探索する位置は、検出したオブジェクトのエッジ位置とモデルオブジェクトのエッジ位置との間で最小のＭＳＥを与える位置となる。
【００５９】
ＭＳＥの基準の最小化を実施する効率的な方法は、差分アプローチを通じて行う方法である。
特定の点におけるＭＳＥ値が判明しているものと仮定する。
ＭＳＥ関数は、空間的に滑らかであると予想されるので、ＭＳＥ値の小さいほうに向かって下降することにより、ＭＳＥが見つけられる。
これは、オプティカルフロー（ＯＦ）（Optical Flow）推定としても知られている差分アプローチを使用して実施することができる。
ＯＦは、サブピクセル精度の結果を得ることを可能にするシンプルで高速なアルゴリズムである。
【００６０】
便宜上、２Ｄモデルオブジェクト（そのピクセル値を含み、エッジ検出データを含む）を関数Ｌ［ｋ，ｊ］と表すものとする。
ここで、ｋは、第１の軸（例えばｘ軸）のインデックスであり、ｊは、第２の軸（例えばｘ軸と直交するｙ軸）のインデックスであり、Ｌ［ｋ，ｊ］は、位置［ｋ，ｊ］におけるピクセル値である。
さらに、Ｌ（ｔ１，ｔ２）は、補間形式のモデルデータである。
【００６１】
次に、本発明は、並進ベクトル［ｖ１，ｖ２］を求める。
ここで、ｖ１は、第１の方向における差分であり、ｖ２は、第１の方向と直交する第２の方向における差分である。
ここでは、変換ベクトル［ｖ１，ｖ２］は、信号ｘ（ｔ１，ｔ２）とＬ（ｔ１＋ｖ１，ｔ２＋ｖ２）との間の最適な整合を提供する。
【００６２】
モデルのエッジの逆相関行列の決定
まず、モデルのエッジの逆相関行列Ｖ−１が決定される（ステップ４２）。
ここで、行列Ｖは、モデル画像のエッジの相関行列である。
したがって、モデルのエッジの相関行列Ｖは、次のようになる。
【００６３】
【数９】
2005525607.tif 000008
【００６４】
上式において、
【００６５】
【数１０】
2005525607.tif 000009
【００６６】
および
【００６７】
【数１１】
2005525607.tif 000010
【００６８】
は、それぞれ第１の軸および第２の軸におけるＬ［ｋ，ｊ］の離散微分であり、例えば、次のようになる。
【００６９】
【数１２】
2005525607.tif 000011
【００７０】
【数１３】
2005525607.tif 000012
【００７１】
は、それぞれ第１の軸および第２の軸におけるＬ［ｋ，ｊ］の離散微分の２乗である。
【００７２】
モデルのエッジの逆相関行列Ｖ−１は、行列Ｖの逆行列である。
【００７３】
初期並進の決定
次に、モデルオブジェクトのエッジ位置と検出したオブジェクトのエッジ位置との差分（「並進」）が決定される（ステップ４４）。
例えば、上述したアルゴリズムを使用して、検出したエッジ位置が、モデルデータの対応するエッジ位置と比較され、並進、すなわち差分が、サブピクセル単位で決定される。
この初期並進ベクトルを粗い推定とすることができる。
【００７４】
相互相関ベクトルの決定
次に、相互相関ベクトルＣ（ｖ１，ｖ２）が決定される（ステップ４６）。
この相互相関ベクトルＣ（ｖ１，ｖ２）は、ｘ（ｔ１，ｔ２）およびＬ［ｋ，ｊ］を並進したものとＬ［ｋ，ｊ］の微分との差分であり、すなわち、次のように表される。
【００７５】
【数１４】
2005525607.tif 000013
【００７６】
上式において、
【００７７】
【数１５】
2005525607.tif 000014
【００７８】
および
【００７９】
【数１６】
2005525607.tif 000015
【００８０】
は、それぞれ第１の軸および第２の軸におけるＬ［ｋ，ｊ］の離散微分であり、
【００８１】
【数１７】
2005525607.tif 000016
【００８２】
は、補間（最近傍双一次または最近傍双三次）により推定できる［ｖ１，ｖ２］分の離散空間画像ｘ［ｋ，ｊ］の変位である。
【００８３】
並進誤差の決定
次に、ステップ４８に示すように、並進相互相関Ｃ（ｖ１，ｖ２）およびモデルのエッジの逆相関行列Ｖ−１を使用して、並進誤差ベクトル［ｅ１，ｅ２］が次のように決定される。
［ｅ１，ｅ２］＝Ｖ−１＊Ｃ（ｖ１，ｖ２）
上式において、ｅ１およびｅ２は、それぞれ第１の軸および第２の軸における並進の誤差である。
この点、実際には、補間は、画像に直接適用されるのではなく、相互相関ベクトルに適用される。
【００８４】
並進値の更新
（ステップ５０に示すように）誤差は、並進ベクトル［ｖ１，ｖ２］に加えられて、並進ベクトルが更新される。
数学的には、次のように表される。
［ｖ１，ｖ２］ｎｅｗ＝［ｖ１，ｖ２］＋［ｅ１，ｅ２］
【００８５】
必要な場合の繰り返し
ステップ４６からステップ５２に示すように、新しい並進ベクトル［ｖ１，ｖ２］を繰り返し使用して、並進誤差を減少させることができる。
この様子は、判定ステップ５２およびループ５３によって示される。
これらのステップ（４６から５２）は、あらかじめ定めた許容誤差に合致するか、または、あらかじめ定めた繰り返し回数が実行されるまで繰り返される。
その後、オペレーションは終了する（ステップ５４）。
【００８６】
本発明の実施するように構成された装置
図５に、本発明の一実施の形態による計算装置６０を示す。
プロセッサ６２と、プロセッサ６２に接続された記憶装置６４とを含む装置６０が示されている。
プロセッサ６２は、システムバス６６を介して記憶装置６４に接続される。
【００８７】
他のデバイスもシステムバス６６に接続され、例えば、ベルトコンベア７２上のオブジェクト７０の画像を取り込むカメラ６８などがシステムバス６６に接続される。
画像は、画像ファイル７４として記憶装置６４に記憶される。
また、記憶装置６４は、モデル画像ファイルも含む。
さらに、記憶装置６４は、プロセッサ６２が、本明細書で上記に解説した画像処理オペレーションおよびステップを実行するようにする命令７６を含む。
このオペレーションおよびステップとして、フィルタリング（合成積および相関）オペレーションならびに補間オペレーションがあるが、これらに限定されるものではない。
記憶装置１４は、ソリッドステートランダムアクセスメモリ（ＲＡＭ）、光（例えばＣＤ−ＲＯＭ）、磁気（例えばハードドライブ）、またはこれらの任意の組み合わせを含むあらゆるマシン可読形式を取ることができる。
装置６０は、そのバス６６を介して、例えばプリンタといった他のデバイスに接続することができる。
【００８８】
上記から、本発明は、新規であり、現在の技術を上回る利点を提供することが十分理解される。
上記では、本発明の特定の実施の形態について説明し、例示してきたが、本発明は、特定の形式に、または、そのように説明され、例示された各部分の機構に限定されるものでもない。
本発明は、添付の特許請求の範囲によって画定される。
【図面の簡単な説明】
【００８９】
【図１Ａ】デジタルフォーマットの画像サンプルの一部を示す図である。
【図１Ｂ】ピクセルの（図１Ａの画像の直線Ａ−Ａに沿った）列の値のプロファイルおよびその列の補間曲線を示す図である。
【図２】本発明の一態様を示すフローチャートである。
【図３Ａ】不連続点が整数点にのみ存在するサンプルの不連続な区分線形関数Ｍ（ｔ）を示す図である。
【図３Ｂ】図３Ａの関数Ｍ（ｔ）のステップ列を示す図である。
【図３Ｃ】図３Ａの関数Ｍ（ｔ）のランプ列を示す図である。
【図４】本発明の別の態様を示すフローチャートである。
【図５】本発明の一実施の形態による装置を示す図である。
【符号の説明】
【００９０】
６０・・・計算装置、
６２・・・プロセッサ、
６４・・・記憶装置、
６６・・・システムバス、
６８・・・カメラ、
７０・・・オブジェクト、
７２・・・ベルトコンベア、
７４・・・画像、
７６・・・命令、
７８・・・モニタ、
８０・・・プリンタ、
【図１Ａ】
2005525607.tif 000020
【図１Ｂ】
2005525607.tif 000021
【図２】
2005525607.tif 000022
【図３Ａ】
2005525607.tif 000023
【図３Ｂ】
2005525607.tif 000024
【図３Ｃ】
2005525607.tif 000025
【図４】
2005525607.tif 000026
【図５】
2005525607.tif 000027
【国際調査報告】
2005525607.tif 000028
2005525607.tif 000029
2005525607.tif 000030
2005525607.tif 000031