(57)【要約】【課題】テンプレート・マッチングのような画像処理に要する最大処理時間を短縮することが可能な画像処理システムを提供する。【解決手段】画像処理システムは、探索対象画像の中からテンプレート画像と一致する一致領域を探索する。操作処理部５０１と、抽出処理部５０２と、計算処理部５０３と、特定処理部５０４とを具備する。操作処理部５０１は、連続した複数の第１ビットの各々を順次操作して、不連続な複数の第２ビットの各々を順次生成する。抽出処理部５０２は、順次生成される第２ビット毎に、探索対象画像の中の連続的な探索順の位置のうち、第２ビットに対応した探索位置で部分領域を抽出する。計算処理部５０３は、抽出された部分領域とテンプレート画像との類似性に関する指標を算出する。特定処理部５０４は、複数の第２ビットに対応した複数の部分領域について算出された複数の指標に基づいて、複数の部分領域から一致領域を特定し、一致領域の位置としての合致位置を特定する。【選択図】図４
2011210178.tif 000002
【特許請求の範囲】
【請求項１】
探索対象画像の中からテンプレート画像と一致する一致領域を探索する画像処理システムであって、
連続した複数の第１ビットの各々を順次操作して、不連続な複数の第２ビットの各々を順次生成する操作処理部と、
順次生成される前記第２ビット毎に、前記探索対象画像の中の連続的な探索順の位置のうち、前記第２ビットに対応した探索位置で部分領域を抽出する抽出処理部と、
抽出された前記部分領域とテンプレート画像との類似性に関する指標を算出する計算処理部と、
前記複数の第２ビットに対応した前記複数の部分領域について算出された前記複数の指標に基づいて、前記複数の部分領域から前記一致領域を特定し、前記一致領域の位置としての合致位置を特定する特定処理部と
を具備する
画像処理システム。
【請求項２】
請求項１に記載の画像処理システムにおいて、
前記操作処理部は、前記複数の第１ビットの各々を、ビットを逆順化する処理又はビットを回転する処理で、前記複数の第２ビットの各々を順次生成する
画像処理システム。
【請求項３】
請求項２に記載の画像処理システムにおいて、
前記抽出処理部は、前記探索対象画像の中から、空間充填曲線に基づく探索順の位置に前記第２ビットを写像した前記探索位置で前記部分領域を抽出する
画像処理システム。
【請求項４】
請求項３に記載の画像処理システムにおいて、
前記空間充填曲線は、ヒルベルト曲線又はＺオーダ曲線である
画像処理システム。
【請求項５】
請求項３に記載の画像処理システムにおいて、
前記計算処理部は、前記類似性に関する指標としてＬ１ノルムを算出する
画像処理システム。
【請求項６】
探索対象画像の中からテンプレート画像と一致する一致領域を探索する画像処理方法であって、
連続した複数の第１ビットの各々を順次操作して、不連続な複数の第２ビットの各々を順次生成するステップと、
順次生成される前記第２ビット毎に、前記探索対象画像の中の連続的な探索順の位置のうち、前記第２ビットに対応した探索位置で部分領域を抽出するステップと、
抽出された前記部分領域とテンプレート画像との類似性に関する指標を算出するステップと、
前記複数の第２ビットに対応した前記複数の部分領域について算出された前記複数の指標に基づいて、前記複数の部分領域から前記一致領域を特定し、前記一致領域の位置としての合致位置を特定するステップと
を具備する
画像処理方法。
【請求項７】
請求項６に記載の画像処理方法において、
前記複数の第２ビットの各々を順次生成するステップは、前記複数の第１ビットの各々を、ビットを逆順化する処理又はビットを回転する処理で、前記複数の第２ビットの各々を順次生成するステップを備える
画像処理方法。
【請求項８】
請求項７に記載の画像処理方法において、
前記部分領域を抽出するステップは、前記探索対象画像の中から、空間充填曲線に基づく探索順の位置に前記第２ビットを写像した前記探索位置で前記部分領域を抽出するステップを備える
画像処理方法。
【請求項９】
請求項８に記載の画像処理方法において、
前記合致位置を特定するステップは、前記類似性に関する指標としてＬ１ノルムを算出するステップを備える
画像処理方法。
【請求項１０】
請求項６乃至９のいずれか一項に記載の画像処理方法を画像処理システムとしてのコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理システム及び画像処理方法に関し、特にテンプレート・マッチングを行う画像処理システム及び画像処理方法に関する。
【背景技術】
【０００２】
近年、自動車の走行安全分野や交通安全システムのインフラ分野などにおいて、カメラを搭載又は設置したシステムが急速に普及し始めている。そのシステムの目的の多くは、カメラ画像に映った映像の中から、人や物を見つけ出し、警告や警報を発することで事故を未然に防ぐことである。カメラ画像に映った映像の中から、人や物を見つけ出す処理は、多くの場合テンプレート・マッチングと呼ばれる方法を用いて実現する。
【０００３】
テンプレート・マッチングは、予め用意されたテンプレート画像と類似する部分画像を、探索対象画像内から発見する画像処理の一種である。テンプレート・マッチングは、探索に際して、人手による画像特徴抽出やパラメータ設定などが不要であり、比較的簡便な方法である。そのため、テンプレート・マッチングは、様々な場面で利用されており、画像処理における重要な技術の一つである。
【０００４】
自動車の走行安全分野などに利用する画像処理は、一般的にリアルタイム処理が必要となる。リアルタイム処理が必要とされる画像処理システムにおいては、どのような入力画像に対しても一定時間以内に処理を完了し、結果出力することを保障する必要がある。通常、画像処理システム設計時に、入力画像に対する処理完了までの許容時間は、最大処理時間を考慮して決定される。つまり、画像処理に要する最大処理時間を改善することで、画像処理システムの応答性が改善される。その結果、その画像処理システムは、より時間的制約の厳しいシステムに適用することが可能となり、その画像処理システムの適応範囲を拡大することができる。このため最大処理時間の短縮の要求（必要性）は常に存在している。
【０００５】
テンプレート・マッチングに関する技術として、Ｂａｒｎｅａ  Ｄ．Ｉ．，Ｓｉｌｖｅｒｍａｎ  Ｈ．Ｆ．，“Ａ  Ｃｌａｓｓ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｆａｓｔ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｒｅｇｉｓｔｒａｔｉｏｎ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｐｕｔ．，Ｖｏｌ．ｃ−２１，Ｎｏ．２，ｐ．１７９−１８６（Ｆｅｂ．１９７２）（以下、非特許文献１とも言う）に、テンプレート・マッチングにおけるＳＳＤＡ法の技術が記載されている。図１Ａ及び図１Ｂは、非特許文献１に記載のＳＳＤＡ法によるテンプレート・マッチングの様子を示す模式図である。ただし、図１Ａ及び図１Ｂにおいて、テンプレート画像をＴ２０１（図１Ｂ）、探索対象画像をＵ２０４（図１Ａ）とし、テンプレート画像Ｔ２０１と同じサイズとなる部分画像をＱ２０３（図１Ａ）、部分画像Ｑ２０３が移動可能な領域を探索領域Ｐ２０２（図１Ａ）とする。このとき、テンプレート・マッチングは、テンプレート画像Ｔ２０１と最も類似性の高い部分画像Ｑ２０３を探索する処理となる。テンプレート画像Ｔ２０１および探索領域Ｐ２０２は画像の左上を原点（０，０）とし、テンプレート画像Ｔ２０１はＭ×Ｎ、探索領域Ｐ２０２はＷ×Ｈのサイズを有するものとする。
【０００６】
探索において、テンプレート画像Ｔ２０１と部分画像Ｑ２０３とが、どの程度類似しているかを示す指標を定義する必要がある。上述のＳＳＤＡ法においては、類似度は、対応する各画素の差の総和（Ｌ１ノルム）であって、下記の式（１）にて定義されるＬ１（ｘ，ｙ）の値が小さいほど、画像間の類似度が高いものと定義する。以下、下記の式（１）のテンプレート画像と矩形領域の画像との突合せにより類似度を求める処理を照合処理と表現する。なお、式（１）におけるＴ（ｉ，ｊ）及びＰ（ｉ，ｊ）は、それぞれテンプレート画像及び探索領域の画像における座標（ｉ，ｊ）における画素の輝度値を示す。
【０００７】
【数１】
2011210178.tif 000003
（但し  ０≦ｘ＜Ｗ、かつ、０≦ｙ＜Ｈ）
【０００８】
ここで、探索領域Ｐの全画素に対して（１）式による照合処理を行う場合、Ｍ×Ｎ×Ｗ×Ｈ回の突合せが発生し、非常に処理負荷の高い処理となる。ＳＳＤＡ法では、図１Ａ及び図１Ｂに示す例のように、探索領域Ｐ２０２内における最良の部分画像Ｑ２０３を１個だけ探索する場合において、最適解である部分画像Ｑ２０３を座標（ｘ’，ｙ’）にて発見することができた場合を考える。その場合、以降の探索において、他の座標での類似度（Ｌ１ノルム）が、座標（ｘ’，ｙ’）における類似度（Ｌ１ノルム）を上回ることが判明した時点で、式（１）の計算を打ち切ることが可能となる。つまり、式（１）の計算を一部省略することにより、処理負荷を軽減することができ、テンプレート・マッチング処理の高速化が可能となる。
【０００９】
関連する技術として、ＳＳＤＡ法、正規化相関の技術を取り上げている特開２０００−３２２５７１号公報（特許文献１）、特開平１１−１９５１２２号公報（特許文献２）がある。また、ラスタスキャンでテンプレート画像の類似度に応じて移動量を変化させる技術が記載されている特許第４２０８０１１号公報（特許文献３）がある。その他、前述の各技術の有する問題点を改善する技術として、次回に照合処理を行う矩形領域の抽出を行うために、テーブルを利用することで抽出を行う特開２００７−１２８４８０号公報（特許文献４）がある。また、次回に照合処理を行う矩形領域の抽出を行うために、乱数発生器を使用する特開平０１−１８１１７８号公報がある（特許文献５）。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０００−３２２５７１号公報
【特許文献２】特開平１１−１９５１２２号公報
【特許文献３】特許第４２０８０１１号公報
【特許文献４】特開２００７−１２８４８０号公報（ＵＳ２００７０７６９５１（Ａ１））
【特許文献５】特開平０１−１８１１７８号公報
【非特許文献】
【００１１】
【非特許文献１】Ｂａｒｎｅａ  Ｄ．Ｉ．，Ｓｉｌｖｅｒｍａｎ  Ｈ．Ｆ．，“Ａ  Ｃｌａｓｓ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｆａｓｔ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｒｅｇｉｓｔｒａｔｉｏｎ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｐｕｔ．，Ｖｏｌ．ｃ−２１，Ｎｏ．２，ｐ．１７９−１８６（Ｆｅｂ．１９７２）．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
図２は、類似度（Ｌ１ノルム）の分布の一例を示すグラフである。カメラから撮影された一般的な画像（自然画像）においては、隣接する矩形領域Ｑ２０３とＱ’２０７には画像の相関性がある。そのため、矩形領域Ｑ２０３とＱ’２０７とは、それらの合致位置２０８（ｘ’，ｙ’）の近傍において良好な類似度（Ｌ１ノルム）が得られると考えられる。しかし、逆に、合致位置２０８（ｘ’，ｙ’）から遠ざかるにつれて、図２に示されるように、抽出された矩形領域から得られる類似度（Ｌ１ノルム）は急速に悪化すると考えられる。
【００１３】
そのため、ＳＳＤＡ法では、図２の合致位置２０８（ｘ’，ｙ’）のような合致位置を探索の早い段階（画像の左上）で発見できた場合、式（１）の計算打ち切りによる高速なテンプレート・マッチング処理が可能になる。しかし、合致位置を探索の終盤（画像の右下）で発見する場合、式（１）の計算打ち切りによる高速化は望めない。そのため、ＳＳＤＡ法では探索完了までの処理時間は、探索領域におけるテンプレート画像と矩形領域の画像との合致位置の場所に大きく影響される。
【課題を解決するための手段】
【００１４】
以下に、発明を実施するための形態で使用される番号・符号を用いて、課題を解決するための手段を説明する。これらの番号・符号は、特許請求の範囲の記載と発明を実施するための形態との対応関係を明らかにするために括弧付きで付加されたものである。ただし、それらの番号・符号を、特許請求の範囲に記載されている発明の技術的範囲の解釈に用いてはならない。
【００１５】
本発明の画像処理システムは、探索対象画像（Ｕ）の中からテンプレート画像（Ｔ）と一致する一致領域（Ｑ’）を探索する。この画像処理システムは、操作処理部（５０１）と、抽出処理部（５０２）と、計算処理部（５０３）と、特定処理部（５０４）とを具備する。操作処理部（５０１）は、連続した複数の第１ビット（ｒ）の各々を順次操作して、不連続な複数の第２ビット（ｓ）の各々を順次生成する。抽出処理部（５０２）は、順次生成される第２ビット（ｓ）毎に、探索対象画像（Ｕ）の中の連続的な探索順の位置のうち、第２ビット（ｓ）に対応した探索位置（ｘ、ｙ）で部分領域（Ｑ）を抽出する。計算処理部（５０３）は、抽出された部分領域（Ｑ）とテンプレート画像（Ｔ）との類似性に関する指標（Ｌ１）を算出する。特定処理部（５０４）は、複数の第２ビット（ｓ）に対応した複数の部分領域（Ｑ）について算出された複数の指標（Ｌ１）に基づいて、複数の部分領域（Ｑ）から一致領域（Ｑ）を特定し、一致領域（Ｑ）の位置としての合致位置（ｘ’、ｙ’）を特定する。
【００１６】
本発明は、現在までの探索回数の値のような連続した第１ビット（ｒ）のビット操作処理を行い、次回に類似性を評価する探索位置（ｘ、ｙ）（部分領域（Ｑ））のための不連続な第２ビット（ｓ）の生成を行なう。そして、連続する探索順（例えばヒルベルト曲線及びＺオーダに代表される空間充填曲線）における、不連続な第２ビット（ｓ）に対応する位置（ｘ、ｙ）の部分領域（Ｑ）を抽出する。それにより、部分領域（Ｑ）間の画像の相関性がより低くなるように、次に類似性を評価する部分領域（Ｑ）を抽出することができる。それにより、探索対象画像（Ｕ）全体に対して、偏りなく部分領域（Ｑ）を抽出することが可能となる。その結果、合致位置（ｘ’、ｙ’）（一致領域（Ｑ））の出現位置に依存しない探索が可能となる。この結果、テンプレート・マッチングに要する処理時間の平準化を図ることできる。また、次回に類似性を評価する部分領域（Ｑ）の抽出のために特別な記憶装置を用意する必要はなく、計算操作等により次回の部分領域（Ｑ）の抽出位置を一意に決定できるため、省資源での動作が求められる環境下での適用が可能である。加えて、連続する探索順（例えばヒルベルト曲線及びＺオーダに代表される空間充填曲線）を用いることにより、既出の部分領域（Ｑ）を抽出することなく、探索領域（Ｐ）全体に対して探索を行うことができる。
【００１７】
本発明の画像処理方法は、探索対象画像（Ｕ）の中からテンプレート画像（Ｔ）と一致する一致領域（Ｑ’）を探索する。この画像処理方法は、連続した複数の第１ビット（ｒ）の各々を順次操作して、不連続な複数の第２ビット（ｓ）の各々を順次生成するステップと、順次生成される第２ビット（ｓ）毎に、探索対象画像（Ｕ）の中の連続的な探索順の位置のうち、第２ビット（ｓ）に対応した探索位置（ｘ、ｙ）で部分領域（Ｑ）を抽出するステップと、抽出された部分領域（Ｑ）とテンプレート画像（Ｔ）との類似性に関する指標（Ｌ１）を算出するステップと、複数の第２ビット（ｓ）に対応した複数の部分領域（Ｑ）について算出された複数の指標（Ｌ１）に基づいて、複数の部分領域（Ｑ）から一致領域（Ｑ）を特定し、一致領域（Ｑ）の位置としての合致位置（ｘ’、ｙ’）を特定するステップとを具備する。
また、本発明のプログラムは、上記の画像処理方法を画像処理システムとしてのコンピュータに実行させる。
これら本発明の画像処理方法及びそのプログラムにおいても、上記画像処理システムと同様の作用・効果を得ることができる。
【発明の効果】
【００１８】
本発明により、テンプレート・マッチングのような画像処理に要する最大処理時間を短縮することが可能な画像処理システム及び画像処理方法を提供することができる。
【図面の簡単な説明】
【００１９】
【図１Ａ】図１Ａは、非特許文献１に記載のＳＳＤＡ法によるテンプレート・マッチングの様子を示す模式図である。
【図１Ｂ】図１Ｂは、非特許文献１に記載のＳＳＤＡ法によるテンプレート・マッチングの様子を示す模式図である。
【図２】図２は、類似度（Ｌ１ノルム）の分布の一例を示すグラフである。
【図３】図３は、本発明の第１の実施の形態に係る画像処理システムの構成の一例を示すブロック図である。
【図４】図４は、図３の画像処理プロセッサの構成を示すブロック図である。
【図５】図５は、本発明の第１の実施の形態に係る画像処理システムの構成の他の例を示すブロック図である。
【図６】図６は、図５の画像処理プロセッサと外部演算装置の構成を示すブロック図である。
【図７】図７に、本発明の第１、２の実施の形態に係る画像処理システムの動作（画像処理方法）の一例を示すフローチャートである。
【図８】図８は、ステップＳ１０３における８ビット長のデータｒに対してビットを逆順に変換する様子を示す模式図である。
【図９】図９は、ステップＳ１０４における次回に照合処理を行う矩形領域を抽出する様子を示す模式図である。
【図１０】図１０は、ステップＳ１０３における８ビット長のデータｒに対して２ビット左方向に回転する様子を示す模式図である。
【図１１】図１１は、ステップＳ１０４における次回に照合処理を行う矩形領域を抽出する様子を示す模式図である。
【図１２】図１２は、ステップＳ１０４における次回に照合処理を行う矩形領域を抽出する様子を示す模式図である。
【図１３】図１３は、ステップＳ１０４における次回に照合処理を行う矩形領域を抽出する様子を示す模式図である。
【図１４Ａ】図１４Ａは、本発明の概念を示す模式図である。
【図１４Ｂ】図１４Ｂは、本発明の概念を示す模式図である。
【発明を実施するための形態】
【００２０】
以下、本発明の画像処理システム及び画像処理方法の実施の形態に関して、添付図面を参照して説明する。
【００２１】
（第１の実施の形態）
本発明の第１の実施の形態に係る画像処理システムの構成について説明する。図３は、本発明の第１の実施の形態に係る画像処理システムの構成の一例を示すブロック図である。画像処理システム１は、画像処理プロセッサ３０２と、ホストマイコン（ホストマイクロコンピュータ）３０１と、カメラ３０３と、モニタ３０４とを具備している。画像処理プロセッサ３０２は、ホストマイコン３０１と、カメラ３０３と、モニタ３０４と接続されている。カメラ３０３は、画像を撮影し、画像処理プロセッサ３０２に出力する。モニタ３０４は、画像処理プロセッサ３０２の出力を表示する。
【００２２】
図４は、図３の画像処理プロセッサの構成を示すブロック図である。画像処理プロセッサ３０２は、ＣＰＵ４０２と、（テンプレート画像格納）メモリ４０３と、（探索対象画像格納）メモリ４０４と、テンプレート・マッチング処理部４０５とを備えている。メモリ４０３は、テンプレート画像を格納している。メモリ４０４は、カメラ３０３等から得られ、テンプレート・マッチング処理の対象となる画像としての探索対象画像を格納している。テンプレート・マッチング処理部４０５は、テンプレート・マッチング処理を実施するソフトウェアを保持している。ＣＰＵ４０２がそのソフトウェアを実行することにより、そのテンプレート・マッチング処理（画像処理方法）が実現される。そのソフトウェアは、メモリ４０３、４０４のデータについて、そのテンプレート・マッチング処理を実施する。
【００２３】
ここで、テンプレート・マッチング処理は、ビット逆順化に例示されるビット順番を操作する操作処理と、次回に照合処理を行う矩形領域（部分画像の領域である部分領域）のメモリアドレスを特定・抽出する抽出処理と、類似度Ｌ１ノルムの計算処理と、テンプレート画像と合致する矩形領域（部分領域）の合致位置を特定する特定処理を含む画像処理方法である。テンプレート・マッチング処理部４０５は、ソフトウェアとして、上記操作処理を実施する操作処理部５０１と、上記抽出処理を実施する抽出処理部５０２と、上記計算処理を実施する計算処理部５０３と、上記特定処理を実施する特定処理部５０４とを備えている。
【００２４】
図５は、本発明の第１の実施の形態に係る画像処理システムの構成の他の例を示すブロック図である。この画像処理システム１ａは、図３の場合と比較して、更に、画像処理プロセッサ３０２に接続された外部演算装置３０５（ハードウェア）を具備している。図６は、図５の画像処理プロセッサと外部演算装置の構成を示すブロック図である。外部演算装置３０５は、画像処理プロセッサ３０２に接続されたビット操作措置４０７とアドレス決定装置４０８とを備えている。この画像処理システム１ａでは、ビット操作装置（操作処理部）４０７が、ビット逆順化に例示されるビット順番を操作する操作処理を実行する。アドレス決定装置（抽出処理部）４０８が、次回に照合処理を行う矩形領域（部分領域）のメモリアドレスを特定・抽出する抽出処理を実行する。ＣＰＵ４０２がテンプレート・マッチング処理部４０５のソフトウェアを実行することで、テンプレート・マッチング処理（類似度Ｌ１ノルムの計算処理、テンプレート画像と合致する矩形領域（部分領域）の合致位置を特定する特定処理）を実現する。すなわち、外部演算装置３０５（ハードウェア）とＣＰＵ４０２のソフトウェア（計算処理部５０３、特定処理部５０４）の実行とで、テンプレート・マッチング処理（画像処理方法）が実現される。
【００２５】
本実施の形態では、上記図３及び図４の画像処理システム１、又は、上記図５及び図６の画像処理システム１ａのいずれを用いても実施することができる。ただし、これらの構成は例であり、以下に示す機能及び動作を実現可能であれば、他の構成であっても良い。
【００２６】
次に、本発明の第１の実施の形態に係る画像処理システムの動作（画像処理方法）について説明する。本実施の形態では、画像処理プロセッサ３０２のソフトウェア（画像処理システム１）、もしくは、外部演算装置３０５のハードウェア（画像処理システム１ａ）により、現在までの探索回数をビット逆順に変換し、ヒルベルト曲線に基づいて次回に照合処理を行う矩形領域のメモリアドレス特定を行う。
【００２７】
図７は、本発明の第１の実施の形態に係る画像処理システムの動作（画像処理方法）の一例を示すフローチャートである。
【００２８】
（１）ステップＳ１０１
操作処理部は、打ち切りのための閾値Ｔｈに、初期値として画像処理プロセッサ３０２が設定可能な最大の整数値を閾値Ｔｈに設定する。
【００２９】
（２）ステップＳ１０２
操作処理部は、変数ｒによる探索領域の探索ループを開始する。すなわち、初期値をｒ＝０とし、ｒ＜２２Ｄ（Ｄは自然数）の範囲で探索ループを実行する。
【００３０】
（３）ステップＳ１０３
操作処理部は、式（２）に定義する関数ｆを用いて、変数ｒを変数ｓに写像する。探索領域のサイズが２Ｄｘ２Ｄ＝２２Ｄである場合、関数ｆは以下で定義される。
ｓ＝ｆ（ｒ）  （但し、０≦ｒ＜２２Ｄ、かつ、Ｄは自然数）  …（２）
ここで、関数ｆは２Ｄビット長の２進数値ｒに対して、ビットをＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）とＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）の並びを逆順化する処理である。関数ｆは以下の式（３）、式（４）で定義することが可能である。なお、ｂｋはｒにおけるビット位置ｋの値であり、０もしくは１となる。
ｒ  ＝ｂ２Ｄ−１ｂ２Ｄ−２ｂ２Ｄ−３…ｂ２ｂ１ｂ０  …（３）
ｆ（ｒ）＝ｂ０ｂ１ｂ２…ｂ２Ｄ−３ｂ２Ｄ−２ｂ２Ｄ−１  …（４）
（但し、Ｄは自然数、かつ、ｂｋは０もしくは１）
例として、図８に、８ビット長のデータｒに対してビットを逆順に変換する様子を示す。図８より、ｒで最上位に存在したビットがｓの最下位ビットに変換されることがわかる。
【００３１】
（４）ステップＳ１０４
抽出処理部は、探索座標（ｘ、ｙ）の位置を決定する。以下の式（５）におけるＨｘ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｘ座標、また、Ｈｙ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｙ座標である。
（ｘ，ｙ）＝（Ｈｘ（ｓ），Ｈｙ（ｓ））  …（５）
（但し、０≦ｓ＜２２Ｄ、かつ、Ｄは自然数）
例として、図９に、次回に照合処理を行う矩形領域を抽出する様子を示す。この図では、１６×１６（＝２４×２４；Ｄ＝４）の探索領域Ｐ２０２を有する探索対象画像２０４に対してｒ（Ｒ空間２０５に属する）を関数ｆによりビット逆順に変換してｓ＝ｆ（ｒ）（Ｓ空間２０６に属する）を得た後、空間充填曲線のひとつであるヒルベルト曲線に基づく探索順（探索領域Ｐ２０２に矢印で表示）の位置に写像することで、次回に照合処理を行う矩形領域２０３を抽出している。
Ｒ空間２０５上の変数ｒをインクリメントすることで、探索領域Ｐ２０２上の不連続となる点（例示：０番目に選択される座標（０，０）、３２番目に選択される座標（８，８）、１６番目に選択される座標（８，０）、…）を対応点として選択することができる。すなわち、現在処理中の矩形領域２０３からより遠方の矩形領域２０３を次回の矩形領域２０３として抽出する可能性を高くすることができる。それにより、抽出される矩形領域２０３が探索対象領域Ｐ２０２の局所に集中せず、探索領域全体に対して広く探索を行うことができる。
【００３２】
（５）ステップＳ１０５
計算処理部は、前記の式（１）で定義した座標（ｘ，ｙ）における類似度（Ｌ１ノルム）の累積値の初期値を０で初期化する。すなわち、Ｌ１（ｘ、ｙ）＝０とする。
【００３３】
（６）ステップＳ１０６
計算処理部は、変数ｎによるテンプレート画像の高さのループを開始する。すなわち、初期値をｎ＝０とし、ｎ＜Ｎ（Ｎはテンプレート画像Ｔ２０１（図１Ｂ）の高さ）の範囲でループを実行する。
【００３４】
（７）ステップＳ１０７
計算処理部は、変数ｍによるテンプレート画像の幅のループを開始する。すなわち、初期値をｍ＝０とし、ｍ＜Ｍ（Ｍはテンプレート画像Ｔ２０１（図１Ｂ）の幅）の範囲でループを実行する。
【００３５】
（８）ステップＳ１０８
計算処理部は、類似度（Ｌ１ノルム）の累積処理を行う。ステップＳ１０６〜Ｓ１１１の２重ループ処理は、前記の式（１）を計算する処理（照合処理）である。
【００３６】
（９）ステップＳ１０９
計算処理部は、現在までの類似度（Ｌ１ノルム）と閾値Ｔｈとの比較を行い、類似度（Ｌ１ノルム）の累積値が閾値Ｔｈ（ステップＳ１０１で設定）を越えた場合はステップＳ１１４に分岐する。
【００３７】
（１０）ステップＳ１１０
計算処理部は、変数ｍ＜Ｍの場合、ｍを１増加させ（ｍ＝ｍ＋１）、ステップＳ１０７に分岐する。
そうでなければ、変数ｍによるテンプレート画像の幅のループを終了する。
【００３８】
（１１）ステップＳ１１１
計算処理部は、変数ｎ＜Ｎの場合、ｎを１増加させ（ｎ＝ｎ＋１）、ステップＳ１０６に分岐する。
そうでなければ、変数ｎによるテンプレート画像の高さのループを終了する。
【００３９】
（１２）ステップＳ１１２
特定処理部は、最良となる類似度（最小のＬ１ノルム）を発見した場合、閾値Ｔｈを、発見した最良類似度（Ｌ１ノルム）の値に更新する。このステップＳ１１２は、最良となる類似度（最小のＬ１ノルム）を発見した場合にのみ実施される。
【００４０】
（１３）ステップＳ１１３
特定処理部は、最良となる類似度（最小のＬ１ノルム）を発見した場合、合致位置の候補座標（ｘ，ｙ）を（ｘ’，ｙ’）に登録する。このステップＳ１１３は、最良となる類似度（最小のＬ１ノルム）を発見した場合にのみ実施される。
【００４１】
（１４）ステップＳ１１４
操作処理部は、変数ｒ＜２２Ｄの場合、ｒを１増加させ（ｒ＝ｒ＋１）、ステップＳ１０２に分岐する。
そうでなければ、変数ｒによる探索領域Ｐ２０２の探索ループを終了する。
【００４２】
（１５）ステップＳ１１５
特定処理部は、合致位置（ｘ’，ｙ’）をモニタ３０４に出力する。
【００４３】
以上のようにして、本発明の第１の実施の形態に係る画像処理システムの動作（画像処理方法）が実施される。
【００４４】
本実施の形態では、画像処理プロセッサ、もしくは、外部演算装置により、現在までの探索回数（変数ｒ）に対して、ビット操作処理（例えば、ＭＳＢとＬＳＢを逆順に変換する処理）を行い、次回に照合処理を行う矩形領域を抽出している。このとき、写像対象が、探索順が連続した関数（すなわち、ヒルベルト曲線に代表される空間充填曲線のように、多くの区間で微分可能であり、画像相関性が高い順番で探索が行われる関数）であれば、上記ビット操作処理を行うことで、より不連続となる座標を、次回の矩形領域の抽出位置として選択することができる。これにより、現在まで探索された箇所と比較して、より画像相関性の少ない矩形領域、つまり、現在処理中の矩形領域からより遠方の矩形領域を次回の矩形領域として抽出する可能性を高くすることができる。
【００４５】
非特許文献１のＳＳＤＡ法においては、探索完了までの処理時間がテンプレート画像と部分画像との合致位置に大きく影響する問題が存在する。しかし、本実施の形態においては、上述の理由により、抽出される矩形領域が探索対象領域の局所に集中せず、探索領域全体に対して広く探索を行うため、探索に要する処理時間の平準化（最大処理時間の短縮）が可能となる。
【００４６】
また、自然画像に対しては、画像相関性の少ない矩形領域を、次回の矩形領域として抽出するため、探索打ち切りのための閾値を、照合位置で得られる類似度の値に急速に収束させることができる。上述の理由から、非特許文献１のＳＳＤＡ法と比較した場合、探索の早い段階において、照合位置で得られる類似度に近い類似度が閾値に設定される。このため、探索の早い段階においても打ち切り処理が有効に作用し、非特許文献１のＳＳＤＡ法と比較した場合、探索完了までの最大処理時間の短縮、および、平均処理時間の短縮が期待される。
【００４７】
また、特開２００７−１２８４８０号公報においては、次回に照合処理を行う矩形領域を抽出するためにテーブルを記憶装置に用意する必要があった。しかし、本実施の形態では数式によって次回の矩形領域を抽出するため、事前にテーブルを用意する必要はない。
【００４８】
加えて、特開平０１−１８１１７８号公報においては、既出の矩形領域を重複探索する問題、また、乱数に基づく処理のため、探索対象画像全体に対する探索が困難となる問題があった。しかし、本実施の形態では、現在までの探索回数と、探索順が連続した関数（空間充填曲線、ヒルベルト曲線）と１対１で対応するため、既出の矩形領域に対する重複探索が発生せず、かつ、容易に探索領域全体に対して探索を行うことができる。
【００４９】
（第２の実施の形態）
本発明の第２の実施の形態では、画像処理システムの構成は第１の実施の形態と同じであるが、画像処理システムの動作（画像処理方法）について異なっている。以下では、その画像処理システムの動作（画像処理方法）について説明する。
【００５０】
図７は、本発明の第２の実施の形態に係る画像処理システムの動作（画像処理方法）の一例を示すフローチャートである。本実施の形態の画像処理システムの動作（画像処理方法）は、ステップＳ１０３が相違する以外は、第１の実施の形態と同様である。従って、以下では、ステップＳ１０３について説明する。
【００５１】
本実施の形態のステップＳ１０３では、ビット回転処理を行った結果に基づいて、空間充填曲線上の座標（変数ｓ）の取得を行う。具体的には、以下のような動作になる。
【００５２】
（３）ステップＳ１０３：
操作処理部は、式（２）に定義する関数ｆを用いて、変数ｒを変数ｓに写像する。探索領域のサイズが２Ｄｘ２Ｄ＝２２Ｄである場合、関数ｆは以下で定義される。
ｓ＝ｆ（ｒ）  （但し、０≦ｒ＜２２Ｄ、かつ、Ｄは自然数）  …（２）
ここで、関数ｆは２Ｄビット長の２進数値ｒに対して、ビットの回転を行う処理である。関数ｆは以下の式（６）、式（７）、式（８）で定義することが可能である。なお、ｂｋはｒにおけるビット位置ｋの値であり、０もしくは１となる。また、式（７）における、ｃは左方向に回転するビット数である。また、ｍｏｄは剰余算を意味しており、（ｎ＋ｃ）を２Ｄで除算した余りがｇ（ｎ）に設定される。
ｒ  ＝ｂ２Ｄ−１ｂ２Ｄ−２ｂ２Ｄ−３…ｂ２ｂ１ｂ０  …（６）
ｇ（ｎ）＝（ｎ＋ｃ）ｍｏｄ（２Ｄ）  …（７）
ｆ（ｒ）＝ｂｇ（２Ｄ−１）ｂｇ（２Ｄ−２）ｂｇ（２Ｄ−３）…ｂｇ（２）ｂｇ（１）ｂｇ（０）  …（８）
（但し、Ｄ、ｎ、ｃは自然数、かつ、ｂｋは０もしくは１）
例として、図１０に、８ビット長のデータｒに対して２ビット左方向に回転する様子を示す。図１０より、回転の結果、下位２ビットが上位２ビットに移動され、上位６ビットが右方向に移動されていることが分かる。
【００５３】
上記のステップＳ１０３のｓ＝ｆ（ｒ）に基づいて、抽出処理部がステップＳ１０４を実行した結果を図１１に示す。すなわち、図１１に、次回に照合処理を行う矩形領域を抽出する様子を示す。この図では、１６×１６の探索領域Ｐ２０２を有する探索対象画像２０４に対してｒ（Ｒ空間２０５に属する）を関数ｆにより２ビット左方向に回転してｓ＝ｆ（ｒ）（Ｓ空間２０６に属する）を得た後、空間充填曲線のひとつであるヒルベルト曲線に基づく探索順（探索領域Ｐ２０２に矢印で表示）の位置に写像することで、次回に照合処理を行う矩形領域２０３を抽出している。
Ｒ空間２０５上の変数ｒをインクリメントすることで、探索領域Ｐ２０２上の不連続となる点（例示：０番目に選択される座標（０，０）、１６番目に選択される座標（８，０）、３２番目に選択される座標（８，８）、…）を対応点として選択することができる。すなわち、現在処理中の矩形領域２０３からより遠方の矩形領域２０３を次回の矩形領域２０３として抽出する可能性を高くすることができる。それにより、抽出される矩形領域２０３が探索対象領域Ｐ２０２の局所に集中せず、探索領域全体に対して広く探索を行うことができる。
【００５４】
本実施の形態においても、第１の実施の形態と同様に非特許文献や特許文献の問題を解決することができる。また、本実施の形態においても、第１の実施の形態と同様の効果を得ることができる。
【００５５】
また、数式によって次回に照合処理を行う矩形領域を、一意に抽出しており、事前にテーブルを用意する必要がなく、かつ、既出の矩形領域に対する重複探索が発生しないことを保障できる。
【００５６】
更に、式（２）の関数ｆとして、第１の実施の形態においてはビット逆順化処理を、また、第２の実施の形態においてはビット回転処理を用いている。しかし、本発明はこの例に限定されるものではない。基本的に関数ｆは、変換前の値ｒと変換後の値ｓが１対１で写像される処理でさえあれば、既出の矩形領域に対する重複探索は発生しない。このため、入力される探索対象画像に応じて関数ｆを再定義することで、処理性能の向上を図ることができる。
【００５７】
（第３の実施の形態）
本発明の第３の実施の形態では、画像処理システムの構成は第１の実施の形態と同じであるが、画像処理システムの動作（画像処理方法）について異なっている。以下では、その画像処理システムの動作（画像処理方法）について説明する。
【００５８】
図７は、本発明の第３の実施の形態に係る画像処理システムの動作（画像処理方法）の一例を示すフローチャートである。本実施の形態の画像処理システムの動作（画像処理方法）は、ステップＳ１０４が相違する以外は、第１の実施の形態と同様である。従って、以下では、ステップＳ１０４について説明する。
【００５９】
本実施の形態のステップＳ１０４では、Ｚオーダに基づくアドレス決定装置により空間充填曲線上への座標（変数ｓ）取得を行う。具体的には、以下のような動作になる。
【００６０】
（４）ステップＳ１０４
抽出処理部は、探索座標（ｘ、ｙ）の位置を決定する。以下の式（５）におけるＨｘ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｘ座標、また、Ｈｙ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｙ座標である。
（ｘ，ｙ）＝（Ｈｘ（ｓ），Ｈｙ（ｓ））  …（５）
（但し、０≦ｓ＜２２Ｄ、かつ、Ｄは自然数）
ただし、このステップＳ１０４では、図１２に示すようにＺオーダを用いる。すなわち、図１２に、Ｚオーダ（Ｚ−Ｏｒｄｅｒｉｎｇ）を用いて次回に照合処理を行う矩形領域を抽出する様子を示す。この図では、１６×１６の探索領域Ｐ２０２を有する探索対象画像２０４に対してｒ（Ｒ空間２０５に属する）を関数ｆによりビット逆順に変換してｓ＝ｆ（ｒ）（Ｓ空間２０６に属する）を得た後、空間充填曲線のひとつであるＺオーダ（Ｚ−Ｏｒｄｅｒｉｎｇ）曲線に基づく探索順（探索領域Ｐ２０２に矢印で表示）の位置に写像することで、次回に照合処理を行う矩形領域２０３を抽出している。
Ｒ空間２０５上の変数ｒをインクリメントすることで、探索領域Ｐ２０２上の不連続となる点（例示：０番目に選択される座標（０，０）、３２番目に選択される座標（０，８）、１６番目に選択される座標（８，０）、…）を対応点として選択することができる。すなわち、現在処理中の矩形領域２０３からより遠方の矩形領域２０３を次回の矩形領域２０３として抽出する可能性を高くすることができる。それにより、抽出される矩形領域２０３が探索対象領域Ｐ２０２の局所に集中せず、探索領域全体に対して広く探索を行うことができる。
【００６１】
本実施の形態においても、第１の実施の形態と同様に非特許文献や特許文献の問題を解決することができる。また、本実施の形態においても、第１の実施の形態と同様の効果を得ることができる。
【００６２】
また、数式によって次回に照合処理を行う矩形領域を、一意に抽出しており、事前にテーブルを用意する必要がなく、かつ、既出の矩形領域に対する重複し探索が発生しないことを保障できる。
【００６３】
また、式（５）のＨｘ（ｓ）およびＨｙ（ｓ）として、第１の実施の形態においてはヒルベルト曲線を、また、第３の実施の形態においてはＺオーダを用いている。しかし、本発明はこの例に限定されるものではない。基本的には、使用する探索順は探索領域の全画素を網羅する探索順であれば、どのような探索順を用いても良い。このため、入力される探索対象画像に応じて探索順を再定義することで、処理性能の向上を図ることができる。
【００６４】
（第４の実施の形態）
本発明の第４の実施の形態では、画像処理システムの構成は第２の実施の形態と同じであるが、画像処理システムの動作（画像処理方法）について異なっている。以下では、その画像処理システムの動作（画像処理方法）について説明する。
【００６５】
図７は、本発明の第４の実施の形態に係る画像処理システムの動作（画像処理方法）の一例を示すフローチャートである。本実施の形態の画像処理システムの動作（画像処理方法）は、ステップＳ１０４が相違する以外は、第２の実施の形態と同様である。従って、以下では、ステップＳ１０４について説明する。
【００６６】
本実施の形態のステップＳ１０４では、Ｚオーダに基づくアドレス決定装置により空間充填曲線上への座標（変数ｓ）取得を行う。具体的には、以下のような動作になる。
【００６７】
（４）ステップＳ１０４
抽出処理部は、探索座標（ｘ、ｙ）の位置を決定する。以下の式（５）におけるＨｘ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｘ座標、また、Ｈｙ（ｓ）は、空間充填曲線に基づく探索順でｓ番目に選択される座標のｙ座標である。
（ｘ，ｙ）＝（Ｈｘ（ｓ），Ｈｙ（ｓ））  …（５）
（但し、０≦ｓ＜２２Ｄ、かつ、Ｄは自然数）
ただし、このステップＳ１０４では、図１３に示すようにＺオーダを用いる。すなわち、図１３に、Ｚオーダを用いて次回に照合処理を行う矩形領域を抽出する様子を示す。この図では、１６×１６の探索領域Ｐ２０２を有する探索対象画像２０４に対してｒ（Ｒ空間２０５に属する）を関数ｆによりビット逆順に変換してｓ＝ｆ（ｒ）（Ｓ空間２０６に属する）を得た後、空間充填曲線のひとつであるＺオーダ曲線に基づく探索順（探索領域Ｐ２０２に矢印で表示）の位置に写像することで、次回に照合処理を行う矩形領域２０３を抽出している。
Ｒ空間２０５上の変数ｒをインクリメントすることで、探索領域Ｐ２０２上の不連続となる点（例示：０番目に選択される座標（０，０）、１６番目に選択される座標（８，０）、３２番目に選択される座標（０，８）、…）を対応点として選択することができる。すなわち、現在処理中の矩形領域２０３からより遠方の矩形領域２０３を次回の矩形領域２０３として抽出する可能性を高くすることができる。それにより、抽出される矩形領域２０３が探索対象領域Ｐ２０２の局所に集中せず、探索領域全体に対して広く探索を行うことができる。
【００６８】
本実施の形態においても、第２、３の実施の形態と同様に非特許文献や特許文献の問題を解決することができる。また、本実施の形態においても、第２、３の実施の形態と同様の効果を得ることができる。
【００６９】
本発明の上記各実施の形態により、以下の各効果を得ることができる。
第１の効果として、探索に要する処理時間の平準化がある。その理由は、探索位置が局所領域に集中せず、分散させて探索を行うからである。第２の効果として、探索処理の高速化がある。その理由は、前回探索領域から、より画像類似度が少ない領域を優先して探索するため、より急速に探索打ち切りのための閾値を降下させることができるからである。第３の効果として、次回の探索位置を記憶する装置が不要になる。その理由は、数式によって次回に照合処理を行う矩形領域を、一意に抽出しており、事前にテーブルを用意する必要がないからである。第４の効果として、既出の矩形領域に対する重複探索が発生しない。その理由は、乱数に基づく探索ではなく、探索領域を必ず１度だけ通過する探索順（空間充填曲線）に数式によって写像するにより、重複探索が発生しないからである。
【００７０】
図１４Ａ及び図１４Ｂは、本発明の概念を示す模式図である。ただし、図１４Ａ及び図１４Ｂにおいて、テンプレート画像をＴ２０１（図１４Ｂ）、探索対象画像をＵ２０４（図１４Ａ）とし、テンプレート画像Ｔ２０１と同じサイズとなる部分画像をＱ２０３（図１４Ａ）、部分画像Ｑ２０３が移動可能な領域を探索領域Ｐ２０２（図１４Ａ）とする。
本発明は、画像処理プロセッサ、もしくは、外部演算装置により、現在までの探索回数の値のビット操作処理（たとえば、ＭＳＢとＬＳＢの順番を逆順に入れ替える処理）を行い、次回に照合処理を行なう矩形領域２０３のメモリアドレス特定を行なう。そして、連続する探索順（例えばヒルベルト曲線に代表される空間充填曲線）に対して写像することで、より画像の相関性の低い領域（現在の矩形領域２０３“０”と隣接しない、離れた矩形領域２０３“１”、“２”、“３”、“４”、“５”、“６”、…）を、次回に照合処理を行う矩形領域２０３として抽出することができる。それにより、探索対象画像Ｕ２０４全体に対して、偏りなく矩形領域２０３を抽出することが可能となり、合致位置の出現位置に依存しない探索が可能となる。この結果、テンプレート・マッチングに要する処理時間の平準化をはかる効果が得られる。
また、本発明は、次回にテンプレート照合を行う矩形領域の抽出のために特別な記憶装置を用意する必要はなく、数式により次回の矩形領域の抽出位置を一意に決定できるため、省資源での動作が求められる環境下での適用が可能である。
加えて、本発明では、空間充填曲線（空間充填曲線はヒルベルト曲線及びＺオーダに限定されない）に代表される探索順を用いることにより、既出の矩形領域を抽出することなく、探索領域全体に対して探索を行うことができる。
【００７１】
本発明は上記各実施の形態に限定されず、本発明の技術思想の範囲内において、各実施の形態は適宜変形又は変更され得ることは明らかである。
【符号の説明】
【００７２】
１、１ａ  画像処理システム
２０１  テンプレート画像（Ｔ）
２０２  探索対象領域（Ｐ）
２０３  矩形領域（Ｑ）
２０４  探索対象画像（Ｕ）
２０５  Ｒ空間
２０６  Ｓ空間
２０７  矩形領域Ｑ’
２０８  合致座標（ｘ’，ｙ’）
３０１  ホストマイコン（ホストマイクロコンピュータ）
３０２  画像処理プロセッサ
３０３  カメラ
３０４  モニタ
３０５  外部演算装置
４０２  ＣＰＵ
４０３  テンプレート画像格納メモリ（フレームバッファ）
４０４  探索対象画像格納メモリ（フレームバッファ）
４０５  テンプレート・マッチング処理部（ソフトウェア部）
４０６  外部演算装置
４０７  ビット操作装置（ハードウェア部）
４０８  アドレス決定装置（ハードウェア部）
５０１  操作処理部
５０２  抽出処理部
５０３  計算処理部
５０４  特定処理部
【図１Ａ】
2011210178.tif 000004
【図１Ｂ】
2011210178.tif 000005
【図２】
2011210178.tif 000006
【図３】
2011210178.tif 000007
【図４】
2011210178.tif 000008
【図５】
2011210178.tif 000009
【図６】
2011210178.tif 000010
【図７】
2011210178.tif 000011
【図８】
2011210178.tif 000012
【図９】
2011210178.tif 000013
【図１０】
2011210178.tif 000014
【図１１】
2011210178.tif 000015
【図１２】
2011210178.tif 000016
【図１３】
2011210178.tif 000017
【図１４Ａ】
2011210178.tif 000018
【図１４Ｂ】
2011210178.tif 000019