画像処理装置及び画像処理方法
【課題】参照画像からある特定の条件を満たす点の検出精度を維持しつつ更に検出に要する処理時間の短縮化を図る。
【解決手段】許容誤差の範囲内に含まれる画素数分スキップさせながら参照画像の中から抽出された照合画像とテンプレートとの間で、選出された画素位置において比較を行う高速マッチング処理を行う高速マッチング処理部２６と、高速マッチング処理により画像が合致する可能性があると判断された場合、照合画像をテンプレートから許容誤差範囲内でずらした位置でそれぞれ相関を求める高精度マッチング処理部２７と、最大相関係数が得られた照合画像を出力する結果出力部２８を有する。
【解決手段】許容誤差の範囲内に含まれる画素数分スキップさせながら参照画像の中から抽出された照合画像とテンプレートとの間で、選出された画素位置において比較を行う高速マッチング処理を行う高速マッチング処理部２６と、高速マッチング処理により画像が合致する可能性があると判断された場合、照合画像をテンプレートから許容誤差範囲内でずらした位置でそれぞれ相関を求める高精度マッチング処理部２７と、最大相関係数が得られた照合画像を出力する結果出力部２８を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理方法に関する。
【背景技術】
【０００２】
テンプレートマッチングに代表されるような、参照画像からある特定の条件を満たす点を見つける処理を行う際、一般的な方法では、可能性のある全ての点（位置）に対して調査を行う。ただ、参照画像が大きい場合は処理時間が膨大になってしまうため、これを解消するための技術が数々提案されている。例えば、画素を固定の画素数ずつスキップさせてサーチしたり、最初に粗サーチを行って基準領域を求め、その後に精サーチを行ったり（例えば、特許文献１）、あるいは、スキップする間隔を自動算出する方法もが提案されている（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−２６２３７０号公報
【特許文献２】特開平１１−２３８１３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明では、参照画像からある特定の条件を満たす点の検出精度を維持しつつ更に検出に要する処理時間の短縮化を図ることを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る画像処理装置は、探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において、前記参照画像内から抽出点を順次選出する選出手段と、前記選出手段により選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査手段と、前記第１の調査手段による調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査手段と、前記第２の調査手段による調査の結果、前記特定の条件を満たすと判定された位置を出力する手段と、を有し、前記選出手段は、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする。
【０００６】
また、前記予め定められた誤差が１画素の場合、前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出することを特徴とする。
【０００７】
また、前記予め定められた誤差が２画素の場合、前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出することを特徴とする。
【０００８】
本発明に係る画像処理方法は、探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において実施され、前記参照画像内から抽出点を順次選出する選出ステップと、前記選出ステップにより選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査ステップと、前記第１の調査ステップによる調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査ステップと、前記第２の調査ステップによる調査の結果、前記特定の条件を満たすと判定された位置を出力するステップと、を含み、前記選出ステップは、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、参照画像からある特定の条件を満たす点の検出精度を維持しつつ、画素値の比較のためにサンプルする画素の数を大幅に減少させることによって検出処理の高速化を実現することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。
【図２】本実施の形態における画像処理装置を形成するコンピュータのハードウェア構成図である。
【図３】本実施の形態におけるテンプレートマッチング処理を示したフローチャートである。
【図４Ａ】本実施の形態において用いるテンプレートの一例を示した図である。
【図４Ｂ】図４Ａにおいてサンプル点を明示した図である。
【図５Ａ】本実施の形態におけるテンプレートマッチング処理において、許容誤差が１画素の場合に照合画像の中心として選出されうる画素位置を示した図である。
【図５Ｂ】図５Ａにおいて１画素の許容誤差の範囲を明示した図である。
【図６Ａ】本実施の形態におけるテンプレートマッチング処理において、許容誤差が２画素の場合に照合画像の中心として選出されうる画素位置を示した図である。
【図６Ｂ】図６Ａにおいて２画素の許容誤差の範囲を明示した図である。
【発明を実施するための形態】
【００１１】
以下、図面に基づいて、本発明の好適な実施の形態について説明する。
【００１２】
図１は、本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。本実施の形態における画像処理装置２０は、探索対象となる参照画像の中から特定の条件を満たす位置を探索する処理を実施する。本実施の形態では、この実施する処理としてテンプレートマッチング処理を例にして説明する。従って、特定の条件を満たす位置というのは、参照画像においてテンプレートに合致する画像領域若しくはその画像領域を特定しうる点である。画像領域を特定しうる点というのは、例えばその画像領域の中心点や左上の角である。
【００１３】
図２は、本実施の形態における画像処理装置２０を形成するコンピュータのハードウェア構成図である。本実施の形態において画像処理装置２０を形成するサーバコンピュータは、従前から存在する汎用的なハードウェア構成で実現できる。すなわち、コンピュータは、図２に示したようにＣＰＵ１、ＲＯＭ２、ＲＡＭ３、ハードディスクドライブ（ＨＤＤ）４を接続したＨＤＤコントローラ５、入力手段として設けられたマウス６とキーボード７、及び表示装置として設けられたディスプレイ８をそれぞれ接続する入出力コントローラ９、通信手段として設けられたネットワークコントローラ１０を内部バス１１に接続して構成される。
【００１４】
図１に戻り、本実施の形態において画像処理装置２０は、参照画像取得部２１、テンプレート取得部２２、テンプレートマッチング処理部２３、比較対象画素特定部２４、照合画像特定部２５、高速マッチング処理部２６、高精度マッチング処理部２７及び結果出力部２８を有している。参照画像取得部２１は、テンプレートの探索対象となる参照画像を取得する。テンプレート取得部２２は、部分画像に相当するテンプレートを取得する。テンプレートマッチング処理部２３は、比較対象画素特定部２４、照合画像特定部２５、高速マッチング処理部２６及び高精度マッチング処理部２７を含み、テンプレートマッチングを行う。比較対象画素特定部２４は、テンプレートにおいて照合画像と比較する比較対象画素位置を１又は複数選出する。照合画像特定部２５は、参照画像の中からテンプレートとパターンマッチを行う照合画像を特定するが、そのために、照合画像の中心点を抽出点として選出する選出手段として動作する。高速マッチング処理部２６は、第１の調査手段として動作し、選出された１又は複数の比較対象画素位置において照合画像及びテンプレートの比較を行う高速マッチング処理を行う。高精度マッチング処理部２７は、第２の調査手段として動作し、照合画像及びテンプレートの画素位置を合致させた状態に加え、テンプレートから照合画像を許容誤差範囲内でずらした位置でそれぞれ相関を求める高精度マッチング処理を行う。結果出力部２８は、テンプレートマッチング処理部２３における処理結果を出力する。
【００１５】
選出手段として動作する照合画像特定部２５は、予め定められた誤差が１画素の場合、探索対象となる参照画像の特定範囲に、その特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、その拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、その拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出する。また、予め定められた誤差が２画素の場合、探索対象となる参照画像の特定の範囲に、その特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、その拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出する。
【００１６】
画像処理装置２０における各構成要素２１〜２８は、画像処理装置２０を形成するコンピュータと、コンピュータに搭載されたＣＰＵ１で動作するプログラムとの協調動作により実現される。
【００１７】
また、本実施の形態で用いるプログラムは、通信手段により提供することはもちろん、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に格納して提供することも可能である。通信手段や記録媒体から提供されたプログラムはコンピュータにインストールされ、コンピュータのＣＰＵがインストールプログラムを順次実行することで各種処理が実現される。
【００１８】
次に、本実施の形態におけるテンプレートマッチング処理について図３に示したフローチャートを用いて説明する。
【００１９】
参照画像取得部２１は、ＨＤＤ４から、あるいはネットワーク経由でテンプレートに合致する画像が含まれているであろうラスタ画像（以降、「参照画像」）を取得し、一方、テンプレート取得部２２は、ＨＤＤ４から、あるいはネットワーク経由で参照画像の中から検出したい特定のパターン画像（以降、「テンプレート」）を取得する（ステップ１１０）。
【００２０】
参照画像は、図示しないスキャナにより印刷媒体が読み取られることで得られたモノクロの画像データを想定している。参照画像の大きさを、Ｗ×Ｈピクセルで１ピクセル８ビットとする。参照画像の幅（Ｗ）及び高さ（Ｈ）の各値は、参照画像取得部２１又はテンプレートマッチング処理部２３が参照画像を解析することで得ることができる。また、テンプレートは、図４Ａに例示したような“あ”という文字を含む２７×２７ピクセルの画像データを想定している。テンプレートの大きさは、テンプレート取得部２２又はテンプレートマッチング処理部２３がテンプレートを解析することで得ることができる。本実施の形態では、テンプレートの中心を基準画素位置としてテンプレートマッチングを行うので、その基準画素位置が簡単に特定できるようにテンプレートの幅及び高さの各ピクセル数をそれぞれ奇数とした。また、説明の便宜上、テンプレートの中心の検出は、参照画像の外縁からｍ画素以内にある位置を除いた領域において行うことにする。本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出できなくてもよいとする。この５０というピクセル数は、ユーザに指定させるようにしてもよい。更に、テンプレートの向きや大きさは既知であるものとする。なお、本実施の形態では、参照画像内においてテンプレートを探索する範囲を矩形形状とするが、必ずしも矩形形状に限定する必要はない。
【００２１】
続いて、テンプレートマッチング処理部２３は、検出したテンプレートの中心位置を示す座標データを格納するバッファＰ、当該中心点のときに算出した相関係数を格納するバッファＳ及び参照画像上におけるｙ座標の処理の開始点をそれぞれ初期化する（ステップ１２０）。バッファＰには、初期値として（０，０）などあり得ない無効を意味する座標データを設定しておく。バッファＳには、初期値として相関係数の算出値として許容できる数値を設定しておく。ｙ座標の処理の開始点としては、前述した条件に従い５０−１＝４９を設定する。
【００２２】
比較対象画素特定部２４は、取得されたテンプレート内において、後述する高速マッチング処理において照合画像と比較する画素位置を特定する（ステップ１３０）。本実施の形態では、処理の高速化を優先して２７×２７画素のうち比較する１又は複数個の画素を比較対象画素位置（以下、「サンプル点」ともいう）として選出する。本実施の形態では２０画素のみ選出する。図４Ａに図示したテンプレートに対し、選出したサンプル点に“×”で示したマークを付けたときのテンプレートの例を図４Ｂに示す。本実施の形態では、１画素ずれても画素値（輝度値）に影響がないような点をサンプル点として選出することにしている。例えば、図４Ｂにおいて黒色の×印で示した輝度の明るい画素４１は、上下左右に１画素ずれた位置も図面上白色で表される輝度の明るい画素である。一方、図４Ｂにおいて白色の×印で示した輝度の暗い画素４２は、上下左右に１画素ずれた位置も同様に図面上黒色で表される輝度の暗い画素である。このように、以降に説明する本実施の形態におけるテンプレートマッチング処理は、予め定められた許容誤差が１画素の場合についてである。この点については、追って詳述する。なお、比較対象画素特定部２４は、１画素ずれても画素値（輝度値）に影響がない画素４１，４２のようなサンプル点を、自動的に選出してもよいし、ユーザに指定させてもよい。
【００２３】
続いて、照合画像特定部２５は、ｍｏｄ（ｙ×３，５）＋（５０−１）という式にｙの値を代入してｘ座標の値を算出する。なお、ｍｏｄ（ａ，ｂ）は、ａをｂで除算した余りを示す関数である。ここでは、ｙ＝４９なので、ｘの値は、４９の３倍の値を５で割った余り、つまり２に（５０−１）を加算して５１と求まる。従って、照合画像特定部２５は、（５１，４９）という基準画素位置（抽出点）を中心とする２７×２７ピクセルの部分画像を参照画像から抽出することで、テンプレートとの照合画像を特定する（ステップ１４０）。
【００２４】
照合画像が特定されると、高速マッチング処理部２６は、高精度マッチング処理と比較して、精度は相対的に低いかもしれないけれども処理時間は相対的に短い高速マッチング処理を実行する（ステップ１５０）。具体的には、テンプレートと照合画像とを完全に位置合わせした状態、この例では、テンプレートと照合画像の各中心点（５１，４９）を合致させた状態で、前述した２０箇所のサンプル点の画素値を、照合画像及びテンプレートからそれぞれ取り出して比較する。比較した結果、所定の条件に合致した場合（ステップ１６０でＹ）、高精度マッチング処理部２７における高精度マッチング処理に移行する。ここで、所定の条件というのは、次の通りである。
【００２５】
本実施の形態の場合、図４Ｂの×印の点（２０箇所）に対応する点をサンプル点として画素値を比較する。照合画像上のサンプル点とテンプレート上の対応する点の画素値が１２７以下か否かが一致する箇所の個数を数える。一致する箇所の個数が閾値（例えば、１８個）以上である場合、所定の条件を満たすとする。前述の通り、１画素のずれは許容されているので、所定の条件を満たしている場合、（ｘ，ｙ），（ｘ±１，ｙ），（ｘ，ｙ±１）の５点のいずれかを中心とした画像がテンプレート画像に酷似している可能性が高い。 しかし、サンプル点が少ないため、本所定の条件を偶然満たしているという可能性もある。そこで、所定の条件を満たしている場合、高精度マッチング処理へ移行する。
【００２６】
高精度マッチング処理部２７は、高速マッチング処理と比較して、処理時間は相対的に長いかもしれないけれども精度は相対的に高い高精度マッチング処理を実行する（ステップ１７０）。高精度マッチング処理は、具体的に次の処理を行う。すなわち、テンプレート内のある画素位置を（ｘａ，ｙａ）とすると、照合画像における対応するその画素位置（ｘａ，ｙａ）との相関係数を求める。相関係数を求める画素位置（ｘ，ｙ）は、画像上の全画素位置、すなわちｘ＝０〜２６，ｙ＝０〜２６なので２７×２７＝７２９画素に対して求める。あるいは少し間引いて、例えばｘ座標及びｙ座標共に偶数のみ、すなわち１４×１４＝１９６画素に対して求めるようにしてもよい。更に、テンプレートの画素位置（ｘ，ｙ）に対し、照合画像におけるその画素位置を許容誤差に相当する１画素ずらした隣接点（ｘ＋１，ｙ）、（ｘ，ｙ＋１）、（ｘ−１，ｙ）及び（ｘ，ｙ−１）それぞれとも相関係数を求める。
【００２７】
つまり、高精度マッチング処理では、結果として、対応する画素位置（ｘ，ｙ）同士を比較するテンプレート及び照合画像を完全に重ねた状態に加え、テンプレートの（ｘ，ｙ）と照合画像の（ｘ＋１，ｙ）などのようにテンプレートから照合画像を許容誤差範囲内でずらした位置でそれぞれ相関を求めることで５つの相関係数が得られることになるが、テンプレートマッチング処理部２３は、このうち最大値の相関係数ＲＭＡＸ及び相関係数ＲＭＡＸが得られた画素位置（ｘｍａｘ，ｙｍａｘ）を特定する（ステップ１８０）。
【００２８】
ここで、テンプレートマッチング処理部２３は、新たに得られた最大相関係数ＲＭＡＸとバッファＳとの値を比較し、最大相関係数ＲＭＡＸがバッファＳの値以上の場合（ステップ１９０でＹ）、その最大相関係数ＲＭＡＸでバッファＳを更新し、また画素位置（ｘｍａｘ，ｙｍａｘ）をバッファＰに保存する（ステップ２００）。この保存した画素位置Ｐを中心とした画像が現時点においてテンプレートに最も類似している画像である。なお、この最も類似している画像としては、ステップ１４０において特定された照合画像に限らず、この照合画像から１画素ずれた画像が選択されるかもしれない。
【００２９】
以上の処理の後、ｘ座標に５が加えられる（ステップ２１０）。高速マッチング処理の結果、所定条件に合致しない場合（ステップ１６０でＮ）、また高精度マッチング処理の結果、得られた最大相関係数ＲＭＡＸがバッファＳの値を下回った場合も（ステップ１９０でＮ）、このステップ２１０に移行し、ｘ座標に５が加えられる。そして、本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出しないという条件だったので、ｘ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達するまで参照画像のうちｙ座標において（ｘ，ｙ）を中心とする照合画像について前述したステップ１５０〜２００の処理が繰り返し施されることになる（ステップ２２０でＹ）。
【００３０】
そして、ｘ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達すると（ステップ２２０でＮ）、ｙ座標に１が加えられる（ステップ２３０）。そして、本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出しないという条件だったので、ｙ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達するまで（ｘ，ｙ）を中心とする照合画像について前述したステップ１４０〜２２０の処理が繰り返し施されることになる（ステップ２４０でＹ）。
【００３１】
以上の処理を行うことで、最終的に最大相関係数値Ｓ及びその値Ｓが得られた画像の中心座標Ｐが得られることになるが、結果出力部２８は、この値をテンプレートマッチング処理の結果として、処理要求元に送信したり、ディスプレイ８に表示するなど出力する（ステップ２５０）。この処理結果のうちＰの値は、参照画像においてテンプレートと同じ画像が含まれる画像の中心点である。
【００３２】
本実施の形態によれば、高速マッチング処理を行うことによってテンプレートと合致する可能性のある部分画像を参照画像の中から抽出し、その抽出した部分画像に対してのみ精度の高いマッチング処理を行うことによってテンプレートの検出精度を維持できるようにした。なお、図３に示した処理では、最大相関係数となる部分画像をただ１つ選出するようにしたが、所定の閾値を予め設定し、その閾値以上の部分画像を選出することによってテンプレートに合致する１又は複数の部分画像を抽出するようにしてもよい。より具体的には、ステップ１８０において求めた最大相関係数ＲＭＡＸが予め設定した閾値以上の場合に、その最大相関係数が得られた画素位置（ｘｍａｘ，ｙｍａｘ）を中心とする画像をテンプレートと合致する部分画像として検出する。つまり、図３においては、ステップ１９０，２００の処理内容が異なってくる。
【００３３】
ところで、本実施の形態では、テンプレートマッチングを行う際にｙ座標は１ずつスキップさせ（ステップ２３０）、ｘ座標は５ずつスキップさせているが（ステップ２１０）、特にｘ座標を５ずつスキップさせてもテンプレートの検出精度を維持できることについて以下に説明する。
【００３４】
図５Ａは、本実施の形態におけるテンプレートマッチング処理において照合画像の中心として選出されうる画素位置を示した図である。この図５Ａにおいては、Ａ１，Ａ２，・・・，Ａｎと“Ａ”で始まる画素位置が処理対象の照合画像の中心点として選出される画素位置、すなわち抽出点である。本実施の形態では、１画素ずれても画素値（輝度値）に影響がないような点を選出することにした。つまり、許容誤差を１画素としているので、高精度マッチング処理では、抽出点に加え、上下左右の隣接する画素を含めた５画素についても抽出点と同様に相関係数の算出対象としている。
【００３５】
図５Ｂは、図５Ａに示した図において１画素の許容誤差を加味した図である。例えば、抽出点が画素位置Ａ１２の場合、隣接する画素位置Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３が許容誤差（１画素）の中に含まれていることになる。図５Ｂでは、隣接する画素位置Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３を白色で図示した。なお、抽出点の斜めの位置にある画素、例えば図５Ａにおいて画素位置Ｂ３６，Ｂ３８，Ｂ５２，Ｂ５４は、画素位置Ａ１２とはルート２の距離があるので許容誤差範囲外である。そして、画素位置Ａ１２は、サンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５に取り囲まれているが、これらの画素位置Ａ８，Ａ９，Ａ１４，Ａ１５も画素位置Ａ１２と同様に１画素の許容誤差を有している。すなわち、画素位置Ａ８の場合、隣接する画素位置Ｂ２２，Ｂ２９，Ｂ３０，Ｂ３８が許容誤差（１画素）の中に含まれていることになる。画素位置Ａ９の場合、隣接する画素位置Ｂ２７，Ｂ３５，Ｂ３６，Ｂ４３が許容誤差（１画素）の中に含まれていることになる。画素位置Ａ１４の場合、隣接する画素位置Ｂ４６，Ｂ５４，Ｂ５５，Ｂ６３が許容誤差（１画素）の中に含まれていることになる。そして、画素位置Ａ１５の場合、隣接する画素位置Ｂ５２，Ｂ６０，Ｂ６１，Ｂ６８が許容誤差（１画素）の中に含まれていることになる。なお、図５Ｂでは、これらの隣接する画素位置を黒色で図示した。そうすると、図５Ｂを参照すれば明らかなように、画素位置Ａ１２から許容誤差範囲内に位置する画素位置Ａ１２，Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３の５画素は、画素位置Ａ１２を取り囲むサンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５それぞれに隣接する画素（黒色）によって囲まれる。つまり、高精度マッチング処理において許容誤差範囲内に存在する５画素を相関係数の算出対象画素としておけば、隙間となる画素位置が存在しない。換言すると、算出対象とならない画素は存在しない。
【００３６】
一方、Ｂ１，Ｂ２，・・・，Ｂｎと“Ｂ”で始まる抽出点以外の点（画素位置）に着目してみると、これらの点Ｂｎの最近傍の抽出点は、いずれかの抽出点Ａｎに一意に定まる。例えば、点Ｂ２０は、抽出点Ａ５のみを最近傍の抽出点とし、かつ最近傍となる抽出点は他に存在しない。また、抽出点Ａｎ自体は、自らが最近傍の抽出点となる。照合画像特定部２５は、参照画像の特定範囲に含まれる任意の点（画素位置）における最近傍の抽出点が一位に定まるように抽出点を選出する。許容誤差が１画素の場合、図３のフローチャートに示したように、照合画像特定部２５は、参照画像の外縁から５０画素を除いた特定範囲内においてｙを（５０−１）からＨ−（５０−１）に達するまで１ずつ増加させる間に、ｘをｍｏｄ（ｙ×３，５）＋（５０−１）からＷ−（５０−１）に達するまで５ずつ増加させながら得られる点（ｘ，ｙ）を抽出点として選出する。
【００３７】
この例では、画素位置Ａ１２に着目して説明したが、この画素位置Ａ１２と、画素位置Ａ１２を取り囲むサンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５との関係は、他のサンプルされる画素位置Ａｎにも当てはまる。つまり、許容誤差を１画素とした場合、ｙ座標は１ずつスキップさせる一方、ｘ座標は５ずつスキップさせても、全ての画素位置についての調査を行うことは可能となり、これにより、参照画像の中に含まれているであろうテンプレートと同一画像は、確実に検出することができる。本実施の形態においては、以上説明したように、ｘ座標は５ずつスキップさせてもテンプレートの検出精度を維持することができる。
【００３８】
なお、照合画像特定部２５は、一辺の長さがルート５画素長で、ｘ座標軸に対してａｒｃｔａｎ（１／２）ラジアン傾いた格子を参照画像上に描画したときの格子点に位置する画素位置を抽出点として選出すると表現してもよい。
【００３９】
なお、厳密には、参照画像の外縁付近、例えば図５Ａにおいて画素位置Ｂ３は、近傍の画素位置Ａ２，Ａ３，Ａ５から許容誤差である１画素より離れているため相関係数の算出対象外となりうる。しかしながら、外縁に位置する画素位置Ｂ３は、テンプレートの中心点とはなり得ないので精度上問題にならない。ただ、このような状態を解消したいのであれば、本実施の形態のように外縁からｍ（ｍは自然数）ピクセル以内を処理対象外としてもよいし、参照画像の周囲にダミーの画素を付加して外縁に位置する画素を外縁としないように参照画像を前処理してからテンプレートマッチング処理を行ってもよい。
【００４０】
図６Ａは、許容誤差を２画素とした場合において、本実施の形態におけるテンプレートマッチング処理において照合画像の中心として選出されうる画素位置を示した図である。図６Ａでは、図５Ａと同様にＡ１，Ａ２，・・・，Ａｎと“Ａ”で始まる画素位置が抽出点である。図６Ａに示したように、許容誤差を２画素とした場合、照合画像特定部２５は、参照画像の外縁から５０画素を除いた特定範囲内においてｙを（５０−２）からＨ−（５０−２）に達するまで１ずつ増加させる間に、ｘをｍｏｄ（ｙ×５，１３）＋（５０−２）からＷ−（５０−２）に達するまで１３ずつ増加させながら得られる点（ｘ，ｙ）を抽出点として選出する。
【００４１】
図６Ｂは、図６Ａに示した図において２画素の許容誤差を加味した図である。許容誤差が１画素の場合、サンプルされる画素位置を含む上下左右の計５画素が許容誤差範囲内となる。よって、高精度マッチング処理においては、抽出点から許容誤差範囲内にある５画素位置に対して相関係数を求めればよい。これに対し、許容誤差が２画素の場合、図６Ｂにおいて画素位置Ａ５を中心とした太線で囲ったように、サンプルされる画素位置Ａ５から上下左右の各方向に２画素ずつに加えて、距離がルート２の位置関係にある斜め方向の画素を合わせた計１３の画素位置が許容誤差範囲内となる。このため、高精度マッチング処理においては、抽出点から許容誤差範囲内にある１３画素位置それぞれに対して相関係数を求めることになる。Ｂ１，Ｂ２，・・・，Ｂｎと“Ｂ”で始まる抽出点以外の点（画素位置）に着目してみると、許容誤差が１画素の場合と同様に、これらの点Ｂｎの最近傍の抽出点は、いずれかの抽出点Ａｎに一意に定まる。
【００４２】
図６Ｂに示したように、抽出点である画素位置Ａ１０は、サンプルされる画素位置Ａ７，Ａ８，Ａ１３，Ａ１４に取り囲まれているが、この画素位置の関係から明らかなように、ｘ座標は１３ずつスキップさせても、画素位置Ａ１０を中心とした許容誤差２画素以内の画素と、これを取り囲む画素との間に隙間は形成されない。つまり、許容誤差を２画素とした場合、ｙ座標は１ずつスキップさせる一方、ｘ座標は１３ずつスキップさせても、全ての画素位置についての調査を行うこと、つまり相関係数の算出対象とすることが可能となり、これにより、参照画像の中に含まれているであろうテンプレートと同一画像を確実に検出することができる。本実施の形態においては、以上説明したように、ｘ座標は１３ずつスキップさせてもテンプレートの検出精度を維持することができる。
【００４３】
なお、照合画像特定部２５は、一辺の長さがルート１３画素長で、ｘ座標軸に対してａｒｃｔａｎ（２／３）ラジアン傾いた格子を参照画像上に描画したときの格子点に位置する画素位置を抽出点として選出すると表現してもよい。
【００４４】
本実施の形態においては、以上のように「あ」という文字をテンプレートとしてマッチングを行うようにした。ただ、テンプレートとしては、文字に限らず、印刷物に付けるトンボや２次元コードの中の位置検出シンボル、記号等のマークやパターンでもよい。更に、特定の条件を満たす位置を探索する際に利用する技術としては、テンプレートマッチングに限定しない。
【００４５】
また、本実施の形態では、テンプレートと照合画像を対応付ける基準画素位置として画像の中心点を用いたが、それ以外の画素位置、例えば画像の左上角の画素等を基準位置としてもよい。
【符号の説明】
【００４６】
１ ＣＰＵ、２ ＲＯＭ、３ ＲＡＭ、４ ハードディスクドライブ（ＨＤＤ）、５ ＨＤＤコントローラ、６ マウス、７ キーボード、８ ディスプレイ、９ 入出力コントローラ、１０ ネットワークコントローラ、１１ 内部バス、２０ 画像処理装置、２１ 参照画像取得部、２２ テンプレート取得部、２３ テンプレートマッチング処理部、２４ 比較対象画素特定部、２５ 照合画像特定部、２６ 高速マッチング処理部、２７ 高精度マッチング処理部、２８ 結果出力部。
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理方法に関する。
【背景技術】
【０００２】
テンプレートマッチングに代表されるような、参照画像からある特定の条件を満たす点を見つける処理を行う際、一般的な方法では、可能性のある全ての点（位置）に対して調査を行う。ただ、参照画像が大きい場合は処理時間が膨大になってしまうため、これを解消するための技術が数々提案されている。例えば、画素を固定の画素数ずつスキップさせてサーチしたり、最初に粗サーチを行って基準領域を求め、その後に精サーチを行ったり（例えば、特許文献１）、あるいは、スキップする間隔を自動算出する方法もが提案されている（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−２６２３７０号公報
【特許文献２】特開平１１−２３８１３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明では、参照画像からある特定の条件を満たす点の検出精度を維持しつつ更に検出に要する処理時間の短縮化を図ることを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る画像処理装置は、探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において、前記参照画像内から抽出点を順次選出する選出手段と、前記選出手段により選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査手段と、前記第１の調査手段による調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査手段と、前記第２の調査手段による調査の結果、前記特定の条件を満たすと判定された位置を出力する手段と、を有し、前記選出手段は、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする。
【０００６】
また、前記予め定められた誤差が１画素の場合、前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出することを特徴とする。
【０００７】
また、前記予め定められた誤差が２画素の場合、前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出することを特徴とする。
【０００８】
本発明に係る画像処理方法は、探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において実施され、前記参照画像内から抽出点を順次選出する選出ステップと、前記選出ステップにより選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査ステップと、前記第１の調査ステップによる調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査ステップと、前記第２の調査ステップによる調査の結果、前記特定の条件を満たすと判定された位置を出力するステップと、を含み、前記選出ステップは、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、参照画像からある特定の条件を満たす点の検出精度を維持しつつ、画素値の比較のためにサンプルする画素の数を大幅に減少させることによって検出処理の高速化を実現することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。
【図２】本実施の形態における画像処理装置を形成するコンピュータのハードウェア構成図である。
【図３】本実施の形態におけるテンプレートマッチング処理を示したフローチャートである。
【図４Ａ】本実施の形態において用いるテンプレートの一例を示した図である。
【図４Ｂ】図４Ａにおいてサンプル点を明示した図である。
【図５Ａ】本実施の形態におけるテンプレートマッチング処理において、許容誤差が１画素の場合に照合画像の中心として選出されうる画素位置を示した図である。
【図５Ｂ】図５Ａにおいて１画素の許容誤差の範囲を明示した図である。
【図６Ａ】本実施の形態におけるテンプレートマッチング処理において、許容誤差が２画素の場合に照合画像の中心として選出されうる画素位置を示した図である。
【図６Ｂ】図６Ａにおいて２画素の許容誤差の範囲を明示した図である。
【発明を実施するための形態】
【００１１】
以下、図面に基づいて、本発明の好適な実施の形態について説明する。
【００１２】
図１は、本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。本実施の形態における画像処理装置２０は、探索対象となる参照画像の中から特定の条件を満たす位置を探索する処理を実施する。本実施の形態では、この実施する処理としてテンプレートマッチング処理を例にして説明する。従って、特定の条件を満たす位置というのは、参照画像においてテンプレートに合致する画像領域若しくはその画像領域を特定しうる点である。画像領域を特定しうる点というのは、例えばその画像領域の中心点や左上の角である。
【００１３】
図２は、本実施の形態における画像処理装置２０を形成するコンピュータのハードウェア構成図である。本実施の形態において画像処理装置２０を形成するサーバコンピュータは、従前から存在する汎用的なハードウェア構成で実現できる。すなわち、コンピュータは、図２に示したようにＣＰＵ１、ＲＯＭ２、ＲＡＭ３、ハードディスクドライブ（ＨＤＤ）４を接続したＨＤＤコントローラ５、入力手段として設けられたマウス６とキーボード７、及び表示装置として設けられたディスプレイ８をそれぞれ接続する入出力コントローラ９、通信手段として設けられたネットワークコントローラ１０を内部バス１１に接続して構成される。
【００１４】
図１に戻り、本実施の形態において画像処理装置２０は、参照画像取得部２１、テンプレート取得部２２、テンプレートマッチング処理部２３、比較対象画素特定部２４、照合画像特定部２５、高速マッチング処理部２６、高精度マッチング処理部２７及び結果出力部２８を有している。参照画像取得部２１は、テンプレートの探索対象となる参照画像を取得する。テンプレート取得部２２は、部分画像に相当するテンプレートを取得する。テンプレートマッチング処理部２３は、比較対象画素特定部２４、照合画像特定部２５、高速マッチング処理部２６及び高精度マッチング処理部２７を含み、テンプレートマッチングを行う。比較対象画素特定部２４は、テンプレートにおいて照合画像と比較する比較対象画素位置を１又は複数選出する。照合画像特定部２５は、参照画像の中からテンプレートとパターンマッチを行う照合画像を特定するが、そのために、照合画像の中心点を抽出点として選出する選出手段として動作する。高速マッチング処理部２６は、第１の調査手段として動作し、選出された１又は複数の比較対象画素位置において照合画像及びテンプレートの比較を行う高速マッチング処理を行う。高精度マッチング処理部２７は、第２の調査手段として動作し、照合画像及びテンプレートの画素位置を合致させた状態に加え、テンプレートから照合画像を許容誤差範囲内でずらした位置でそれぞれ相関を求める高精度マッチング処理を行う。結果出力部２８は、テンプレートマッチング処理部２３における処理結果を出力する。
【００１５】
選出手段として動作する照合画像特定部２５は、予め定められた誤差が１画素の場合、探索対象となる参照画像の特定範囲に、その特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、その拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、その拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出する。また、予め定められた誤差が２画素の場合、探索対象となる参照画像の特定の範囲に、その特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、その拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出する。
【００１６】
画像処理装置２０における各構成要素２１〜２８は、画像処理装置２０を形成するコンピュータと、コンピュータに搭載されたＣＰＵ１で動作するプログラムとの協調動作により実現される。
【００１７】
また、本実施の形態で用いるプログラムは、通信手段により提供することはもちろん、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に格納して提供することも可能である。通信手段や記録媒体から提供されたプログラムはコンピュータにインストールされ、コンピュータのＣＰＵがインストールプログラムを順次実行することで各種処理が実現される。
【００１８】
次に、本実施の形態におけるテンプレートマッチング処理について図３に示したフローチャートを用いて説明する。
【００１９】
参照画像取得部２１は、ＨＤＤ４から、あるいはネットワーク経由でテンプレートに合致する画像が含まれているであろうラスタ画像（以降、「参照画像」）を取得し、一方、テンプレート取得部２２は、ＨＤＤ４から、あるいはネットワーク経由で参照画像の中から検出したい特定のパターン画像（以降、「テンプレート」）を取得する（ステップ１１０）。
【００２０】
参照画像は、図示しないスキャナにより印刷媒体が読み取られることで得られたモノクロの画像データを想定している。参照画像の大きさを、Ｗ×Ｈピクセルで１ピクセル８ビットとする。参照画像の幅（Ｗ）及び高さ（Ｈ）の各値は、参照画像取得部２１又はテンプレートマッチング処理部２３が参照画像を解析することで得ることができる。また、テンプレートは、図４Ａに例示したような“あ”という文字を含む２７×２７ピクセルの画像データを想定している。テンプレートの大きさは、テンプレート取得部２２又はテンプレートマッチング処理部２３がテンプレートを解析することで得ることができる。本実施の形態では、テンプレートの中心を基準画素位置としてテンプレートマッチングを行うので、その基準画素位置が簡単に特定できるようにテンプレートの幅及び高さの各ピクセル数をそれぞれ奇数とした。また、説明の便宜上、テンプレートの中心の検出は、参照画像の外縁からｍ画素以内にある位置を除いた領域において行うことにする。本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出できなくてもよいとする。この５０というピクセル数は、ユーザに指定させるようにしてもよい。更に、テンプレートの向きや大きさは既知であるものとする。なお、本実施の形態では、参照画像内においてテンプレートを探索する範囲を矩形形状とするが、必ずしも矩形形状に限定する必要はない。
【００２１】
続いて、テンプレートマッチング処理部２３は、検出したテンプレートの中心位置を示す座標データを格納するバッファＰ、当該中心点のときに算出した相関係数を格納するバッファＳ及び参照画像上におけるｙ座標の処理の開始点をそれぞれ初期化する（ステップ１２０）。バッファＰには、初期値として（０，０）などあり得ない無効を意味する座標データを設定しておく。バッファＳには、初期値として相関係数の算出値として許容できる数値を設定しておく。ｙ座標の処理の開始点としては、前述した条件に従い５０−１＝４９を設定する。
【００２２】
比較対象画素特定部２４は、取得されたテンプレート内において、後述する高速マッチング処理において照合画像と比較する画素位置を特定する（ステップ１３０）。本実施の形態では、処理の高速化を優先して２７×２７画素のうち比較する１又は複数個の画素を比較対象画素位置（以下、「サンプル点」ともいう）として選出する。本実施の形態では２０画素のみ選出する。図４Ａに図示したテンプレートに対し、選出したサンプル点に“×”で示したマークを付けたときのテンプレートの例を図４Ｂに示す。本実施の形態では、１画素ずれても画素値（輝度値）に影響がないような点をサンプル点として選出することにしている。例えば、図４Ｂにおいて黒色の×印で示した輝度の明るい画素４１は、上下左右に１画素ずれた位置も図面上白色で表される輝度の明るい画素である。一方、図４Ｂにおいて白色の×印で示した輝度の暗い画素４２は、上下左右に１画素ずれた位置も同様に図面上黒色で表される輝度の暗い画素である。このように、以降に説明する本実施の形態におけるテンプレートマッチング処理は、予め定められた許容誤差が１画素の場合についてである。この点については、追って詳述する。なお、比較対象画素特定部２４は、１画素ずれても画素値（輝度値）に影響がない画素４１，４２のようなサンプル点を、自動的に選出してもよいし、ユーザに指定させてもよい。
【００２３】
続いて、照合画像特定部２５は、ｍｏｄ（ｙ×３，５）＋（５０−１）という式にｙの値を代入してｘ座標の値を算出する。なお、ｍｏｄ（ａ，ｂ）は、ａをｂで除算した余りを示す関数である。ここでは、ｙ＝４９なので、ｘの値は、４９の３倍の値を５で割った余り、つまり２に（５０−１）を加算して５１と求まる。従って、照合画像特定部２５は、（５１，４９）という基準画素位置（抽出点）を中心とする２７×２７ピクセルの部分画像を参照画像から抽出することで、テンプレートとの照合画像を特定する（ステップ１４０）。
【００２４】
照合画像が特定されると、高速マッチング処理部２６は、高精度マッチング処理と比較して、精度は相対的に低いかもしれないけれども処理時間は相対的に短い高速マッチング処理を実行する（ステップ１５０）。具体的には、テンプレートと照合画像とを完全に位置合わせした状態、この例では、テンプレートと照合画像の各中心点（５１，４９）を合致させた状態で、前述した２０箇所のサンプル点の画素値を、照合画像及びテンプレートからそれぞれ取り出して比較する。比較した結果、所定の条件に合致した場合（ステップ１６０でＹ）、高精度マッチング処理部２７における高精度マッチング処理に移行する。ここで、所定の条件というのは、次の通りである。
【００２５】
本実施の形態の場合、図４Ｂの×印の点（２０箇所）に対応する点をサンプル点として画素値を比較する。照合画像上のサンプル点とテンプレート上の対応する点の画素値が１２７以下か否かが一致する箇所の個数を数える。一致する箇所の個数が閾値（例えば、１８個）以上である場合、所定の条件を満たすとする。前述の通り、１画素のずれは許容されているので、所定の条件を満たしている場合、（ｘ，ｙ），（ｘ±１，ｙ），（ｘ，ｙ±１）の５点のいずれかを中心とした画像がテンプレート画像に酷似している可能性が高い。 しかし、サンプル点が少ないため、本所定の条件を偶然満たしているという可能性もある。そこで、所定の条件を満たしている場合、高精度マッチング処理へ移行する。
【００２６】
高精度マッチング処理部２７は、高速マッチング処理と比較して、処理時間は相対的に長いかもしれないけれども精度は相対的に高い高精度マッチング処理を実行する（ステップ１７０）。高精度マッチング処理は、具体的に次の処理を行う。すなわち、テンプレート内のある画素位置を（ｘａ，ｙａ）とすると、照合画像における対応するその画素位置（ｘａ，ｙａ）との相関係数を求める。相関係数を求める画素位置（ｘ，ｙ）は、画像上の全画素位置、すなわちｘ＝０〜２６，ｙ＝０〜２６なので２７×２７＝７２９画素に対して求める。あるいは少し間引いて、例えばｘ座標及びｙ座標共に偶数のみ、すなわち１４×１４＝１９６画素に対して求めるようにしてもよい。更に、テンプレートの画素位置（ｘ，ｙ）に対し、照合画像におけるその画素位置を許容誤差に相当する１画素ずらした隣接点（ｘ＋１，ｙ）、（ｘ，ｙ＋１）、（ｘ−１，ｙ）及び（ｘ，ｙ−１）それぞれとも相関係数を求める。
【００２７】
つまり、高精度マッチング処理では、結果として、対応する画素位置（ｘ，ｙ）同士を比較するテンプレート及び照合画像を完全に重ねた状態に加え、テンプレートの（ｘ，ｙ）と照合画像の（ｘ＋１，ｙ）などのようにテンプレートから照合画像を許容誤差範囲内でずらした位置でそれぞれ相関を求めることで５つの相関係数が得られることになるが、テンプレートマッチング処理部２３は、このうち最大値の相関係数ＲＭＡＸ及び相関係数ＲＭＡＸが得られた画素位置（ｘｍａｘ，ｙｍａｘ）を特定する（ステップ１８０）。
【００２８】
ここで、テンプレートマッチング処理部２３は、新たに得られた最大相関係数ＲＭＡＸとバッファＳとの値を比較し、最大相関係数ＲＭＡＸがバッファＳの値以上の場合（ステップ１９０でＹ）、その最大相関係数ＲＭＡＸでバッファＳを更新し、また画素位置（ｘｍａｘ，ｙｍａｘ）をバッファＰに保存する（ステップ２００）。この保存した画素位置Ｐを中心とした画像が現時点においてテンプレートに最も類似している画像である。なお、この最も類似している画像としては、ステップ１４０において特定された照合画像に限らず、この照合画像から１画素ずれた画像が選択されるかもしれない。
【００２９】
以上の処理の後、ｘ座標に５が加えられる（ステップ２１０）。高速マッチング処理の結果、所定条件に合致しない場合（ステップ１６０でＮ）、また高精度マッチング処理の結果、得られた最大相関係数ＲＭＡＸがバッファＳの値を下回った場合も（ステップ１９０でＮ）、このステップ２１０に移行し、ｘ座標に５が加えられる。そして、本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出しないという条件だったので、ｘ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達するまで参照画像のうちｙ座標において（ｘ，ｙ）を中心とする照合画像について前述したステップ１５０〜２００の処理が繰り返し施されることになる（ステップ２２０でＹ）。
【００３０】
そして、ｘ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達すると（ステップ２２０でＮ）、ｙ座標に１が加えられる（ステップ２３０）。そして、本実施の形態では、参照画像の外縁から５０ピクセル以内にある場合は検出しないという条件だったので、ｙ座標が参照画像の幅（Ｗ）から５０ピクセル以内に到達するまで（ｘ，ｙ）を中心とする照合画像について前述したステップ１４０〜２２０の処理が繰り返し施されることになる（ステップ２４０でＹ）。
【００３１】
以上の処理を行うことで、最終的に最大相関係数値Ｓ及びその値Ｓが得られた画像の中心座標Ｐが得られることになるが、結果出力部２８は、この値をテンプレートマッチング処理の結果として、処理要求元に送信したり、ディスプレイ８に表示するなど出力する（ステップ２５０）。この処理結果のうちＰの値は、参照画像においてテンプレートと同じ画像が含まれる画像の中心点である。
【００３２】
本実施の形態によれば、高速マッチング処理を行うことによってテンプレートと合致する可能性のある部分画像を参照画像の中から抽出し、その抽出した部分画像に対してのみ精度の高いマッチング処理を行うことによってテンプレートの検出精度を維持できるようにした。なお、図３に示した処理では、最大相関係数となる部分画像をただ１つ選出するようにしたが、所定の閾値を予め設定し、その閾値以上の部分画像を選出することによってテンプレートに合致する１又は複数の部分画像を抽出するようにしてもよい。より具体的には、ステップ１８０において求めた最大相関係数ＲＭＡＸが予め設定した閾値以上の場合に、その最大相関係数が得られた画素位置（ｘｍａｘ，ｙｍａｘ）を中心とする画像をテンプレートと合致する部分画像として検出する。つまり、図３においては、ステップ１９０，２００の処理内容が異なってくる。
【００３３】
ところで、本実施の形態では、テンプレートマッチングを行う際にｙ座標は１ずつスキップさせ（ステップ２３０）、ｘ座標は５ずつスキップさせているが（ステップ２１０）、特にｘ座標を５ずつスキップさせてもテンプレートの検出精度を維持できることについて以下に説明する。
【００３４】
図５Ａは、本実施の形態におけるテンプレートマッチング処理において照合画像の中心として選出されうる画素位置を示した図である。この図５Ａにおいては、Ａ１，Ａ２，・・・，Ａｎと“Ａ”で始まる画素位置が処理対象の照合画像の中心点として選出される画素位置、すなわち抽出点である。本実施の形態では、１画素ずれても画素値（輝度値）に影響がないような点を選出することにした。つまり、許容誤差を１画素としているので、高精度マッチング処理では、抽出点に加え、上下左右の隣接する画素を含めた５画素についても抽出点と同様に相関係数の算出対象としている。
【００３５】
図５Ｂは、図５Ａに示した図において１画素の許容誤差を加味した図である。例えば、抽出点が画素位置Ａ１２の場合、隣接する画素位置Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３が許容誤差（１画素）の中に含まれていることになる。図５Ｂでは、隣接する画素位置Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３を白色で図示した。なお、抽出点の斜めの位置にある画素、例えば図５Ａにおいて画素位置Ｂ３６，Ｂ３８，Ｂ５２，Ｂ５４は、画素位置Ａ１２とはルート２の距離があるので許容誤差範囲外である。そして、画素位置Ａ１２は、サンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５に取り囲まれているが、これらの画素位置Ａ８，Ａ９，Ａ１４，Ａ１５も画素位置Ａ１２と同様に１画素の許容誤差を有している。すなわち、画素位置Ａ８の場合、隣接する画素位置Ｂ２２，Ｂ２９，Ｂ３０，Ｂ３８が許容誤差（１画素）の中に含まれていることになる。画素位置Ａ９の場合、隣接する画素位置Ｂ２７，Ｂ３５，Ｂ３６，Ｂ４３が許容誤差（１画素）の中に含まれていることになる。画素位置Ａ１４の場合、隣接する画素位置Ｂ４６，Ｂ５４，Ｂ５５，Ｂ６３が許容誤差（１画素）の中に含まれていることになる。そして、画素位置Ａ１５の場合、隣接する画素位置Ｂ５２，Ｂ６０，Ｂ６１，Ｂ６８が許容誤差（１画素）の中に含まれていることになる。なお、図５Ｂでは、これらの隣接する画素位置を黒色で図示した。そうすると、図５Ｂを参照すれば明らかなように、画素位置Ａ１２から許容誤差範囲内に位置する画素位置Ａ１２，Ｂ３７，Ｂ４４，Ｂ４５，Ｂ５３の５画素は、画素位置Ａ１２を取り囲むサンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５それぞれに隣接する画素（黒色）によって囲まれる。つまり、高精度マッチング処理において許容誤差範囲内に存在する５画素を相関係数の算出対象画素としておけば、隙間となる画素位置が存在しない。換言すると、算出対象とならない画素は存在しない。
【００３６】
一方、Ｂ１，Ｂ２，・・・，Ｂｎと“Ｂ”で始まる抽出点以外の点（画素位置）に着目してみると、これらの点Ｂｎの最近傍の抽出点は、いずれかの抽出点Ａｎに一意に定まる。例えば、点Ｂ２０は、抽出点Ａ５のみを最近傍の抽出点とし、かつ最近傍となる抽出点は他に存在しない。また、抽出点Ａｎ自体は、自らが最近傍の抽出点となる。照合画像特定部２５は、参照画像の特定範囲に含まれる任意の点（画素位置）における最近傍の抽出点が一位に定まるように抽出点を選出する。許容誤差が１画素の場合、図３のフローチャートに示したように、照合画像特定部２５は、参照画像の外縁から５０画素を除いた特定範囲内においてｙを（５０−１）からＨ−（５０−１）に達するまで１ずつ増加させる間に、ｘをｍｏｄ（ｙ×３，５）＋（５０−１）からＷ−（５０−１）に達するまで５ずつ増加させながら得られる点（ｘ，ｙ）を抽出点として選出する。
【００３７】
この例では、画素位置Ａ１２に着目して説明したが、この画素位置Ａ１２と、画素位置Ａ１２を取り囲むサンプルされる画素位置Ａ８，Ａ９，Ａ１４，Ａ１５との関係は、他のサンプルされる画素位置Ａｎにも当てはまる。つまり、許容誤差を１画素とした場合、ｙ座標は１ずつスキップさせる一方、ｘ座標は５ずつスキップさせても、全ての画素位置についての調査を行うことは可能となり、これにより、参照画像の中に含まれているであろうテンプレートと同一画像は、確実に検出することができる。本実施の形態においては、以上説明したように、ｘ座標は５ずつスキップさせてもテンプレートの検出精度を維持することができる。
【００３８】
なお、照合画像特定部２５は、一辺の長さがルート５画素長で、ｘ座標軸に対してａｒｃｔａｎ（１／２）ラジアン傾いた格子を参照画像上に描画したときの格子点に位置する画素位置を抽出点として選出すると表現してもよい。
【００３９】
なお、厳密には、参照画像の外縁付近、例えば図５Ａにおいて画素位置Ｂ３は、近傍の画素位置Ａ２，Ａ３，Ａ５から許容誤差である１画素より離れているため相関係数の算出対象外となりうる。しかしながら、外縁に位置する画素位置Ｂ３は、テンプレートの中心点とはなり得ないので精度上問題にならない。ただ、このような状態を解消したいのであれば、本実施の形態のように外縁からｍ（ｍは自然数）ピクセル以内を処理対象外としてもよいし、参照画像の周囲にダミーの画素を付加して外縁に位置する画素を外縁としないように参照画像を前処理してからテンプレートマッチング処理を行ってもよい。
【００４０】
図６Ａは、許容誤差を２画素とした場合において、本実施の形態におけるテンプレートマッチング処理において照合画像の中心として選出されうる画素位置を示した図である。図６Ａでは、図５Ａと同様にＡ１，Ａ２，・・・，Ａｎと“Ａ”で始まる画素位置が抽出点である。図６Ａに示したように、許容誤差を２画素とした場合、照合画像特定部２５は、参照画像の外縁から５０画素を除いた特定範囲内においてｙを（５０−２）からＨ−（５０−２）に達するまで１ずつ増加させる間に、ｘをｍｏｄ（ｙ×５，１３）＋（５０−２）からＷ−（５０−２）に達するまで１３ずつ増加させながら得られる点（ｘ，ｙ）を抽出点として選出する。
【００４１】
図６Ｂは、図６Ａに示した図において２画素の許容誤差を加味した図である。許容誤差が１画素の場合、サンプルされる画素位置を含む上下左右の計５画素が許容誤差範囲内となる。よって、高精度マッチング処理においては、抽出点から許容誤差範囲内にある５画素位置に対して相関係数を求めればよい。これに対し、許容誤差が２画素の場合、図６Ｂにおいて画素位置Ａ５を中心とした太線で囲ったように、サンプルされる画素位置Ａ５から上下左右の各方向に２画素ずつに加えて、距離がルート２の位置関係にある斜め方向の画素を合わせた計１３の画素位置が許容誤差範囲内となる。このため、高精度マッチング処理においては、抽出点から許容誤差範囲内にある１３画素位置それぞれに対して相関係数を求めることになる。Ｂ１，Ｂ２，・・・，Ｂｎと“Ｂ”で始まる抽出点以外の点（画素位置）に着目してみると、許容誤差が１画素の場合と同様に、これらの点Ｂｎの最近傍の抽出点は、いずれかの抽出点Ａｎに一意に定まる。
【００４２】
図６Ｂに示したように、抽出点である画素位置Ａ１０は、サンプルされる画素位置Ａ７，Ａ８，Ａ１３，Ａ１４に取り囲まれているが、この画素位置の関係から明らかなように、ｘ座標は１３ずつスキップさせても、画素位置Ａ１０を中心とした許容誤差２画素以内の画素と、これを取り囲む画素との間に隙間は形成されない。つまり、許容誤差を２画素とした場合、ｙ座標は１ずつスキップさせる一方、ｘ座標は１３ずつスキップさせても、全ての画素位置についての調査を行うこと、つまり相関係数の算出対象とすることが可能となり、これにより、参照画像の中に含まれているであろうテンプレートと同一画像を確実に検出することができる。本実施の形態においては、以上説明したように、ｘ座標は１３ずつスキップさせてもテンプレートの検出精度を維持することができる。
【００４３】
なお、照合画像特定部２５は、一辺の長さがルート１３画素長で、ｘ座標軸に対してａｒｃｔａｎ（２／３）ラジアン傾いた格子を参照画像上に描画したときの格子点に位置する画素位置を抽出点として選出すると表現してもよい。
【００４４】
本実施の形態においては、以上のように「あ」という文字をテンプレートとしてマッチングを行うようにした。ただ、テンプレートとしては、文字に限らず、印刷物に付けるトンボや２次元コードの中の位置検出シンボル、記号等のマークやパターンでもよい。更に、特定の条件を満たす位置を探索する際に利用する技術としては、テンプレートマッチングに限定しない。
【００４５】
また、本実施の形態では、テンプレートと照合画像を対応付ける基準画素位置として画像の中心点を用いたが、それ以外の画素位置、例えば画像の左上角の画素等を基準位置としてもよい。
【符号の説明】
【００４６】
１ ＣＰＵ、２ ＲＯＭ、３ ＲＡＭ、４ ハードディスクドライブ（ＨＤＤ）、５ ＨＤＤコントローラ、６ マウス、７ キーボード、８ ディスプレイ、９ 入出力コントローラ、１０ ネットワークコントローラ、１１ 内部バス、２０ 画像処理装置、２１ 参照画像取得部、２２ テンプレート取得部、２３ テンプレートマッチング処理部、２４ 比較対象画素特定部、２５ 照合画像特定部、２６ 高速マッチング処理部、２７ 高精度マッチング処理部、２８ 結果出力部。
【特許請求の範囲】
【請求項１】
探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において、
前記参照画像内から抽出点を順次選出する選出手段と、
前記選出手段により選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査手段と、
前記第１の調査手段による調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査手段と、
前記第２の調査手段による調査の結果、前記特定の条件を満たすと判定された位置を出力する手段と、
を有し、
前記選出手段は、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする画像処理装置。
【請求項２】
請求項１記載の画像処理装置において、
前記予め定められた誤差が１画素の場合、
前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出することを特徴とする画像処理装置。
【請求項３】
請求項１記載の画像処理装置において、
前記予め定められた誤差が２画素の場合、
前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出することを特徴とする画像処理装置。
【請求項４】
探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において実施され、
前記参照画像内から抽出点を順次選出する選出ステップと、
前記選出ステップにより選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査ステップと、
前記第１の調査ステップによる調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査ステップと、
前記第２の調査ステップによる調査の結果、前記特定の条件を満たすと判定された位置を出力するステップと、
を有し、
前記選出ステップは、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする画像処理方法。
【請求項１】
探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において、
前記参照画像内から抽出点を順次選出する選出手段と、
前記選出手段により選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査手段と、
前記第１の調査手段による調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査手段と、
前記第２の調査手段による調査の結果、前記特定の条件を満たすと判定された位置を出力する手段と、
を有し、
前記選出手段は、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする画像処理装置。
【請求項２】
請求項１記載の画像処理装置において、
前記予め定められた誤差が１画素の場合、
前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が１画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×３＋Ｎ）が５の倍数である点を抽出点として選出することを特徴とする画像処理装置。
【請求項３】
請求項１記載の画像処理装置において、
前記予め定められた誤差が２画素の場合、
前記選出手段は、前記特定の範囲に前記特定の範囲までの距離が２画素以下である領域を加えた領域を拡大領域とし、前記拡大領域内の点の座標を（ｘ，ｙ）とし、Ｎを予め定められた正の整数としたとき、前記拡大領域内の点であり、かつ（ｘ＋ｙ×５＋Ｎ）が１３の倍数である点を抽出点として選出することを特徴とする画像処理装置。
【請求項４】
探索対象となる参照画像の特定範囲の中から特定の条件を満たす位置を探索する画像処理装置において実施され、
前記参照画像内から抽出点を順次選出する選出ステップと、
前記選出ステップにより選出された抽出点が、前記特定の条件を満たす位置であるか否かを、予め定められた誤差を許容して調査する第１の調査ステップと、
前記第１の調査ステップによる調査の結果、当該抽出点が前記特定の条件を満たす位置の可能性有りと判断された場合、当該抽出点を最近傍の抽出点とする全ての位置を当該抽出点と共に調査対象として、前記特定の条件を満たす位置であるか否かを調査する第２の調査ステップと、
前記第２の調査ステップによる調査の結果、前記特定の条件を満たすと判定された位置を出力するステップと、
を有し、
前記選出ステップは、前記参照画像の特定範囲に含まれる任意の位置における最近傍の抽出点が一意に特定されるように抽出点を選出することを特徴とする画像処理方法。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【公開番号】特開２０１０−２７１８５８（Ｐ２０１０−２７１８５８Ａ）
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願番号】特願２００９−１２２２９６（Ｐ２００９−１２２２９６）
【出願日】平成２１年５月２０日（２００９．５．２０）
【出願人】（５９１２２７６８６）富士ゼロックスエンジニアリング株式会社 (41)
【Ｆターム（参考）】
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願日】平成２１年５月２０日（２００９．５．２０）
【出願人】（５９１２２７６８６）富士ゼロックスエンジニアリング株式会社 (41)
【Ｆターム（参考）】
[ Back to top ]