(57)【要約】【課題】複数の画像の検索に要する時間を短縮する。【解決手段】コンポーネントツリー作成部16は被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフ(コンポーネントツリー)を作成し、キーコンポーネント抽出部18は、検索対象画像(テンプレート画像)とのサイズの違いが閾値以内で、かつ階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分(キーコンポーネント)を探索し、キーコンポーネント照合部20は、探索した連結成分と検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する。【選択図】図１
2014182617.tif 000002
【特許請求の範囲】
【請求項１】
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成する階層グラフ作成部と、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する探索部と、
前記探索部によって探索された連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する距離演算部と、
を含む画像処理装置。
【請求項２】
前記探索部は、前記階層グラフの系列に対して階層の深さ優先で探索することで、検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する請求項１記載の画像処理装置。
【請求項３】
前記距離演算部は、前記探索部によって探索された連結成分と前記検索対象画像との相対位置をずらしたときの複数の位置について前記距離を各々演算し、演算した距離が所定値以下の位置に対応する連結成分の対応領域を検索結果として出力する請求項１又は請求項２記載の画像処理装置。
【請求項４】
前記探索部は、前記階層グラフ作成部によって作成された単一の前記階層グラフに基づき、複数の前記検索対象画像について前記連結成分の探索を順に行い、
前記距離演算部は、複数の前記検索対象画像について前記距離の演算及び検索結果の出力を順に行う請求項１〜請求項３の何れか１項記載の画像処理装置。
【請求項５】
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成し、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索し、
探索した連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する
ことを含む画像処理方法。
【請求項６】
コンピュータに、
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成し、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索し、
探索した連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する
ことを含む処理を行わせるための画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の技術は画像処理装置、画像処理方法及び画像処理プログラムに関する。
【背景技術】
【０００２】
与えられた画像に対して所望のパターンを検索して抽出する技術としてテンプレートマッチング法が知られている(図１５参照)。テンプレートマッチング法は、被検索対象画像全体に亘ってウィンドウを走査させ、各位置のウィンドウに相当する部分領域の画像とテンプレート画像との距離計算を行うことで、被検索対象画像上のテンプレート画像が最も合致する位置を求める方法である。２つの画像の距離は次の(１)式によって計算される。
【０００３】
【数１】
2014182617.tif 000003
【０００４】
なお、(１)式において、Ｉ(ｘ,ｙ)は被検索対象画像、Ｔ(ｘ,ｙ)は横Ｍ画素、縦Ｎ画素のテンプレート画像、Ｗ(ｕ,ｖ)は左上頂点の座標を(ｕ,ｖ)とするウィンドウである。
【０００５】
しかし、上記のテンプレートマッチング法は、被検索対象画像から切り出した部分領域画像とテンプレート画像との距離計算を多数回繰り返す必要があり、処理に多くの時間が掛かる。このため、被検索対象画像から切り出した部分領域画像とテンプレート画像との距離計算の途中で、それ迄に計算した値が閾値を超えている場合に、距離計算を打ち切って次の部分領域の計算に移る残差逐次検定法(ＳＳＤＡ法)が提案されている。また、三角不等式から得られる距離の下限値を算出することにより、各照合位置で具体的な距離計算をせずに候補対象外としてよいか否か判定するSuccessive Elimination Algorithm(ＳＥＡ法)も提案されている。
【０００６】
ＳＥＡ法では、距離計算を行う前に三角不等式によって距離計算の必要性を判定する。具体的には、テンプレート画像の大きさ|Ｔ|((２)式参照)、被検索対象画像のウィンドウＷ(ｕ,ｖ)の部分領域画像の大きさ|Ｗ(ｕ,ｖ)|((３)式参照)及び閾値θminが||Ｔ|−|Ｗ(ｕ,ｖ)||≧θminを満たすならば距離計算の候補対象外としてスキップし、次の距離計算に移る。
【０００７】
【数２】
2014182617.tif 000004
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】DANIEL I.BARNEA,HARVEY F.SILVERMAN,"A Class of Algorithms for Fast Digital Image Registration",IEEE TRANSACTIONS ON COMPUTERS,VOL.C-21,NO.2,FEBRUARY 1972,pp.179-186
【非特許文献２】W.Li,E.Salari,"Successive Elimination Algorithm for Motion Estimation",IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.4,NO.1,JANUARY 1995,pp.105-107
【発明の概要】
【発明が解決しようとする課題】
【０００９】
コンピュータの画面をキャプチャした画像から指定された文字やアイコンの画像を検出することによって、コンピュータの画面が予定通りに表示されているかどうかを確認する作業を自動化したいというニーズがある。上記作業の自動化は、検索対象の文字やアイコンの画像をテンプレートとして複数用意しておき、被検索対象画像から検索対象の個々の文字やアイコンを自動で検出することで実現される。なお、コンピュータの画面をキャプチャした画像上において、文字やアイコンなどの検索対象画像は、背景から独立した形で配置されていることが多いという特徴を有する。
【００１０】
しかしながら、従来の画像検索技術は、何れも検索対象画像(テンプレート)毎に被検索対象画像の全体を走査する必要があり、検索対象画像の数が増加するに従い、検索に要する時間が長時間化するという課題があった。
【００１１】
開示の技術は、一つの側面として、複数の画像の検索に要する時間を短縮することが目的である。
【課題を解決するための手段】
【００１２】
開示の技術は、階層グラフ作成部により、被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成する。また、探索部は、検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する。そして、距離演算部は、前記探索部によって探索された連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する。
【発明の効果】
【００１３】
開示の技術は、一つの側面として、複数の画像の検索に要する時間を短縮することができる、という効果を有する。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る画像処理装置の機能ブロック図である。
【図２】図１の画像処理装置として機能することが可能なコンピュータの概略ブロック図である。
【図３】被検索対象画像上の検索対象画像の一例を示すイメージ図である。
【図４】テンプレートマッチング処理を示すフローチャートである。
【図５】マッチング候補検出処理を示すフローチャートである。
【図６】キーコンポーネント探索処理を示すフローチャートである。
【図７】キーコンポーネント照合処理を示すフローチャートである。
【図８】コンポーネントツリーの作成を説明するための概念図である。
【図９】コンポーネントツリーからのキーコンポーネントの抽出を説明するための概念図である。
【図１０】コンポーネントツリーに対する深さ優先探索を説明するための概念図である。
【図１１】テンプレート画像とキーコンポーネント画像との距離演算を説明するための概念図である。
【図１２】テンプレート画像とキーコンポーネント画像との距離演算を説明するための概念図である。
【図１３】被検索対象画像上でのキーコンポーネント画像の領域の一例を示すイメージ図である。
【図１４】処理結果の一例を示す図表である。
【図１５】テンプレートマッチング法を説明するための概念図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して開示の技術の実施形態の一例を詳細に説明する。図１には、本実施形態に係る画像処理装置１０が示されている。画像処理装置１０は、コンピュータの画面をキャプチャする等によって得られた被検索対象画像に対し、検索対象画像(テンプレート画像)を探索するテンプレートマッチング処理を行う装置である。画像処理装置１０によるテンプレートマッチング処理により、コンピュータの画面が予定通りに表示されているかどうかを確認する作業が自動化される。
【００１６】
画像処理装置１０は、マッチング候補検出部１２及びマッチング候補検証部１４を備えており、マッチング候補検出部１２はコンポーネントツリー作成部１６、キーコンポーネント抽出部１８及びキーコンポーネント照合部２０を含んでいる。
【００１７】
マッチング候補検出部１２は、被検索対象画像に対し、検索対象画像(テンプレート画像)と対応していると推定されるマッチング候補を検出する処理を行う。マッチング候補検出部１２によるマッチング候補の検出は、より詳しくは、コンポーネントツリー作成部１６、キーコンポーネント抽出部１８及びキーコンポーネント照合部２０によって実現される。
【００１８】
すなわち、コンポーネントツリー作成部１６は、被検索対象画像をグレー化し、被検索対象画像のグレー画像を走査する。そしてコンポーネントツリー作成部１６は、被検索対象画像のグレー画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフ(コンポーネントツリー)を作成する。
【００１９】
キーコンポーネント抽出部１８は、検索対象画像(テンプレート画像)とのサイズの違いが閾値以内で、コンポーネントツリー作成部１６によって作成されたコンポーネントツリーの系列上で、対応する二値化閾値が最も低濃度側に位置している連結成分を探索する。なお、本実施形態では、キーコンポーネント抽出部１８によって探索される連結成分をキーコンポーネントと称する。
【００２０】
キーコンポーネント照合部２０は、キーコンポーネント抽出部１８によって探索された連結成分と検索対象画像との距離を演算し、距離が最小の連結成分に対応する領域をマッチング候補として出力する。
【００２１】
マッチング候補検証部１４は、マッチング候補検出部１２によって検出されたマッチング候補が検索対象画像(テンプレート画像)と対応しているか否かを、色情報を照合して検証する処理を行う。
【００２２】
なお、コンポーネントツリー作成部１６は開示の技術に係る階層グラフ作成部の一例であり、キーコンポーネント抽出部１８は開示の技術における探索部の一例であり、キーコンポーネント照合部２０は開示の技術における距離演算部の一例である。
【００２３】
画像処理装置１０は、例えば図２に示すコンピュータ３０で実現することができる。コンピュータ３０はＣＰＵ３２、メモリ３４、記憶部３６、入力部３８及び表示部４０を備えている。ＣＰＵ３２、メモリ３４、記憶部３６、入力部３８及び表示部４０はバス４２を介して互いに接続されている。
【００２４】
記憶部３６はＨＤＤ(Hard Disk Drive)やフラッシュメモリ等によって実現できる。記憶部３６には、コンピュータ３０を画像処理装置１０として機能させるためのテンプレートマッチングプログラム４４が記憶されている。ＣＰＵ３２は、テンプレートマッチングプログラム４４を記憶部３６から読み出してメモリ３４に展開し、テンプレートマッチングプログラム４４が有するプロセスを順次実行する。
【００２５】
テンプレートマッチングプログラム４４は、マッチング候補検出プロセス４６及びマッチング候補検証プロセス４８を有する。またマッチング候補検出プロセス４６は、コンポーネントツリー作成プロセス５０、キーコンポーネント抽出プロセス５２及びキーコンポーネント照合プロセス５４を含んでいる。
【００２６】
ＣＰＵ３２は、マッチング候補検出プロセス４６を実行することで、図１に示すマッチング候補検出部１２として動作する。またＣＰＵ３２は、マッチング候補検証プロセス４８を実行することで、図１に示すコンポーネントツリー作成部１６として動作する。またＣＰＵ３２は、コンポーネントツリー作成プロセス５０を実行することで、図１に示すマッチング候補検証部１４として動作する。またＣＰＵ３２は、キーコンポーネント抽出プロセス５２を実行することで、図１に示すキーコンポーネント抽出部１８として動作する。またＣＰＵ３２は、キーコンポーネント照合プロセス５４を実行することで、図１に示すキーコンポーネント照合部２０として動作する。
【００２７】
これにより、テンプレートマッチングプログラム４４を実行したコンピュータ３０が、画像処理装置１０として機能することになる。なお、テンプレートマッチングプログラム４４は開示の技術に係る画像処理プログラムの一例である。また、コンピュータ３０としては、例えばパーソナル・コンピュータ(ＰＣ：Personal Computer)や、携帯情報端末(ＰＤＡ：Personal Digital Assistants)の機能を搭載した携帯型の情報処理装置であるスマート端末を適用できる。
【００２８】
また、記憶部３６には、被検索対象画像が記憶されており、複数の検索対象画像(テンプレート画像)も記憶されている。本実施形態において、被検索対象画像はコンピュータの画面をキャプチャする等によって得られる画像であり、検索対象画像はコンピュータの画面に含まれるアイコン等を表す画像である。なお、被検索対象画像及び検索対象画像は記憶部３６に予め記憶されていることに限られるものではなく、外部の機器から取得するようにしてもよい。
【００２９】
なお、画像処理装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ(Application Specific Integrated Circuit)等で実現することも可能である。
【００３０】
次に本実施形態の作用を説明する。コンピュータの画面をキャプチャする等によって得られた被検索対象画像において、画像中の文字やアイコンなどの検索対象画像は、例えば図３に示すように、濃度や色の相違に基づき二値化等を行うことで背景から容易に分離することができる。このため、被検索対象画像から検索対象画像(テンプレート画像)の大きさにほぼ等しい部分領域を特定して抽出し、その領域のみに対して距離計算を行えば距離計算を効率化できる。
【００３１】
被検索対象画像から検索対象画像の大きさにほぼ等しい部分領域を抽出する方法としては、被検索対象を二値化し、二値画像に対してラベリング処理を行うことにより二値画像の中から検索対象画像の大きさにほぼ等しい部分領域を抽出する方法が考えられる。但し、被検索対象画像上での検索対象画像の背景の色及び濃度は未知であるため、二値化閾値をどのように設定すればよいのかが問題になる。例えば０〜２５５迄の全ての値を二値化閾値として二値化を２５６回行い、２５６枚の二値画像に対してラベリング処理を行い、検索対象画像の大きさにほぼ等しい領域を抽出することも考えられる。しかし、この方法は処理に時間が掛かり大容量のメモリを必要とするので効率的ではない。
【００３２】
上記に鑑み、本実施形態では被検索対象画像についてコンポーネントツリーを作成し、作成したコンポーネントツリーの情報を用いることにより、被検索対象画像に対する検索対象画像の探索を効率的に行う。コンポーネントツリーは、画像を１回走査することにより得られるグラフ情報であり、階調画像の各階調値に関する切断画像（階調値を二値化閾値とする二値画像）の各連結成分を要素(コンポーネント)としている。コンポーネントツリーは、階調値(二値化閾値)を変えていったときの連結成分の包含関係によって要素（コンポーネント）を関係付けたツリー状の階層グラフである。
【００３３】
以下、コンピュータ３０によってテンプレートマッチングプログラム４４が実行されることで実現されるテンプレートマッチング処理について説明する。なお、テンプレートマッチング処理は、例えば、コンピュータの画面をキャプチャした画像から指定された文字やアイコンの画像を検出することによって、コンピュータの画面が予定通りに表示されているかどうかを確認する等を目的として実行が指示される。
【００３４】
図４に示すように、テンプレートマッチング処理のステップ１００において、マッチング候補検出部１２は、被検索対象画像に対して検索対象画像(テンプレート画像)と対応していると推定されるマッチング候補領域を検出するマッチング候補検出処理を行う。なお、マッチング候補検出処理の詳細は後述する。
【００３５】
また、次のステップ１０２において、マッチング候補検証部１４は、マッチング候補検出部１２によって検出されたマッチング候補領域が検索対象画像(テンプレート画像)と対応しているか否かを、色情報を照合して検証するマッチング候補検証処理を行う。具体的には、検出されたマッチング候補領域について、原画像のカラー画像における被検索対象画像と検索対象画像(テンプレート画像)との色情報の差分を求め、求めた差分が閾値以内であれば、マッチング領域として出力する。出力する処理結果は、図１４に示すように、個々の検索対象画像について、検出した領域の数と、検出した個々の領域を表す外接矩形の座標を情報として含んでいる。
【００３６】
次に図５を参照し、マッチング候補検出処理の詳細を説明する。マッチング候補検出処理のステップ１１０において、コンポーネントツリー作成部１６は、カラー画像である被検索対象画像をグレー画像に変換する。カラー画像のグレー化は、３次元のＲＧＢ空間において、原点を通る所定の直線へ射影することに相当するので、３次元空間の方向ベクトルの取り方だけバリエーションがある。例えば、最もよく使用されるのが明度であり、次の(４)式によって計算される。ここで、ＲＧＢ空間の点を座標(Ｒ,Ｇ,Ｂ)によって表す。
明度＝0.299Ｒ＋0.587Ｇ＋0.114Ｂ    …(４)
なお、カラー画像のグレー化は上記に明度に限られるものではなく、例えば色差Ｒ−Ｂや色差Ｇ−Ｂを明度に代えて用いてもよい。
【００３７】
次のステップ１１２において、コンポーネントツリー作成部１６は、被検索対象画像のグレー画像に対してコンポーネントツリーを作成する。グレー画像のコンポーネント・ツリーは、グレー画像の各濃度値に関する切断画像(各濃度値を二値化閾値とする二値画像)の各連結成分を要素(コンポーネント)としている。コンポーネント・ツリーは、グレー画像を１回走査し、二値化閾値を変えていったときの連結成分の包含関係によって要素(コンポーネント)を階層的に関係付けたツリー状の階層グラフである。グレー画像とコンポーネント・ツリーの具体例を図８に示す。
【００３８】
コンポーネントツリーの階層グラフ上では、個々のコンポーネント(黒画素で構成される連結成分)がノードとして表現され、個々のコンポーネントの関係はノードとノードを結ぶエッジで表現される。また、コンポーネントツリーには、二値化閾値が最も低濃度側に単一のノードが存在しており、それをルートノードと称する。図８の例では、二値化閾値がｔ0のときに切断画像は全面黒画素の画像となり、対応するノードは単一のルートノードとなる。
【００３９】
作成されたコンポーネントツリーは以下の情報を含む。
(1)ノードの集合
(2)ノードの個数
(3)ルートへのポインタ
また、コンポーネントツリーの個々のノードは以下の情報を含む。
(1)ノードＩＤ（正の整数）
(2)濃度値
(3)コンポーネントの外接矩形の座標
(4)コンポーネントの黒画素の個数（コンポーネントの面積）
(5)子供コンポーネントのノードＩＤ
(6)子供コンポーネントの個数
(7)親コンポーネントのノードＩＤ
【００４０】
なお、コンポーネントツリーの作成に関しては、幾つかの方法が提案されている(例えば、Laurent Najman,Michel Couprie,"Building the Component Tree in Quasi-Linear Time",IEEE Transactions on Image Processing,2006,3531〜3539)。
【００４１】
次のステップ１１４において、マッチング候補検出部１２は、未処理の検索対象画像が有るか否か判定する。ステップ１１４の判定が肯定された場合はステップ１１６へ移行する。ステップ１１６において、キーコンポーネント抽出部１８は、被検索対象画像のコンポーネントツリーからキーコンポーネントを探索するキーコンポーネント探索処理を行う。また、次のステップ１１８において、キーコンポーネント照合部２０は、キーコンポーネント探索処理で探索されたキーコンポーネントを検索対象画像と照合するキーコンポーネント照合処理を行う。
【００４２】
ステップ１１８の処理を行うとステップ１１４に戻り、ステップ１１４の判定が肯定される迄、ステップ１１４〜ステップ１１８を繰り返す。これにより、個々の検索対象画像に対して、ステップ１１６のキーコンポーネント探索処理及びステップ１１８のキーコンポーネント照合処理が各々行われる。
【００４３】
次に図６を参照し、キーコンポーネント探索処理の詳細について説明する。キーコンポーネント探索処理の実行が開始される際には、コンポーネントツリーのルートノードが基準ノード及び入力ノードに設定される。そしてステップ１２０において、入力ノード(最初は基準ノード)がキーコンポーネントの大きさの条件を満たすか否か判定する。
【００４４】
キーコンポーネントとは、検索対象画像(テンプレート画像)とほぼ同じ大きさを持つコンポーネントのことである(図９も参照)。具体的には、検索対象のテンプレート画像の大きさを横Ｍ画素×縦Ｎ画素とするとき、|Ｍ−Ｘ|＜ε1かつ|Ｎ−Ｙ|＜ε2を満たすＸ画素×Ｙ画素の大きさを持ち、かつ、コンポーネントツリーの系列上で最もルートノード側に位置しているコンポーネントである。なお、ε1,ε2は定数である。
【００４５】
ステップ１２０の判定が肯定された場合はステップ１２６へ移行し、ステップ１２６において、キーコンポーネント抽出部１８は、入力ノードをキーコンポーネントとして登録し、キーコンポーネント探索処理を終了する。
【００４６】
一方、ステップ１２０の判定が否定された場合はステップ１２２へ移行する。ステップ１２２において、キーコンポーネント抽出部１８は、現在の入力ノードよりも下位(二値化閾値の高濃度側)に、キーコンポーネントか否かを未判定の子ノードが有るか否か判定する。なお、ステップ１２２において、現在の入力ノードよりも下位に、キーコンポーネントか否かを未判定の子ノードが存在しない場合、基準ノードよりも下位に、キーコンポーネントか否かを未判定の子ノードが有るか否かを判定する。
【００４７】
ステップ１２２の判定が否定された場合はキーコンポーネント探索処理を終了する。また、ステップ１２２の判定が肯定された場合は、発見された、キーコンポーネントか否かを未判定の子ノードを入力ノードに設定して、図６に示すキーコンポーネント探索処理を再帰的に実行する。これにより、コンポーネントツリーに対して、深さ優先探索によりルートノードよりも下位に存在する全てのキーコンポーネントが探索されることになる(図１０も参照)。
【００４８】
続いて図７を参照し、キーコンポーネント照合処理の詳細について説明する。
【００４９】
キーコンポーネント照合処理のステップ１４０において、キーコンポーネント照合部２０は、距離の閾値θに非常に大きな値を、距離最小値を与える領域の個数argmin_noに０を設定し、距離最小値を与える領域の座標情報の配列argmin[]を初期化する。次のステップ１４２において、キーコンポーネント照合部２０は、未処理のキーコンポーネントが有るか否か判定する。ステップ１４２の判定が肯定された場合はステップ１４４へ移行する。ステップ１４４において、キーコンポーネント照合部２０は、複数位置でキーコンポーネントと検索対象画像(テンプレート画像)との距離計算を行う。
【００５０】
距離計算は、図１１に示すように、キーコンポーネントに対応する被検索対象画像の領域に対し、検索対象画像(テンプレート画像)の相対位置を左上から右下へ順次変化させながら各位置で各々行う。キーコンポーネントと検索対象画像(テンプレート画像)とは必ずしも大きさが一致するとは限らないので、若干のマージンを設定して計算を行う。
【００５１】
具体的には、図１２に示すように、キーコンポーネントに対応する領域の大きさを横Ｘ画素、縦Ｙ画素とし、左上頂点を座標(0, 0)で表す。このとき、座標(−α,−α)の点に検索対象画像の左上点が一致する位置で距離計算を開始し、検索対象画像を右側に１画素ずつずらしていき、検索対象画像の右上点が座標(Ｘ＋α,0)に一致するまで距離計算を繰り返す。次に、検索対象画像を下に１画素ずらし、同じように右側の限界まで距離計算を繰り返す。下方向の限界はＹ＋αで、座標(−α,Ｙ＋α)の点に検索対象画像の左下点が一致する位置から距離計算を開始し、検索対象画像を右側に１画素ずつずらしていき、検索対象画像の右下点が(Ｘ＋α,Ｙ＋α)に一致するまで距離計算を繰り返す。そして、複数位置で演算した距離の最小値を距離ｄとして抽出する。
【００５２】
次のステップ１４６において、キーコンポーネント照合部２０は、ステップ１４４で計算した距離ｄが距離の閾値θよりも小さいか否か判定する。ステップ１４６の判定が肯定された場合はステップ１５０へ移行する。ステップ１５０において、キーコンポーネント照合部２０は、距離の閾値θに距離ｄを設定し、距離最小値を与える領域の座標情報の配列argmin[0]にキーコンポーネントに対応する被検索対象画像の領域の座標を設定する。また、距離最小値を与える領域の個数argmin_noに１を設定する。ステップ１５０の処理を行うとステップ１４２に戻る。
【００５３】
また、ステップ１４６の判定が否定された場合はステップ１４８へ移行する。ステップ１４８において、キーコンポーネント照合部２０は、ステップ１４４で計算した距離ｄが距離の閾値θに等しいか否か判定する。ステップ１４８の判定が否定された場合はステップ１４２に戻る。一方、ステップ１４８の判定が肯定された場合はステップ１５２へ移行する。ステップ１５２において、キーコンポーネント照合部２０は、距離最小値を与える領域の座標情報の配列argmin[argmin_no]にキーコンポーネントに対応する被検索対象画像の領域の座標を設定する。またキーコンポーネント照合部２０は、距離最小値を与える領域の個数argmin_noを１だけインクリメントする。ステップ１５２の処理を行うとステップ１４２に戻る。
【００５４】
なお、ステップ１４４における距離ｄの計算の途中で、それ迄に計算した距離ｄが距離の閾値θを超えている場合には、距離ｄの計算を打ち切り、次のキーコンポーネントの計算に移ってもよい。
【００５５】
上記のコンポーネントツリーの作成には被検索対象画像を１回走査する必要がある。但し、作成したコンポーネントツリーは複数の検索対象画像の探索に共通に用いることができるので、コンポーネントツリーの作成(被検索対象画像の走査)は１回のみで済む。また、コンポーネントツリーからのキーコンポーネントの探索は簡単な処理で済む。そして、コンポーネントツリーからキーコンポーネントを抽出した後に距離計算を行うことで、図１３に黒塗りの領域で示すように、検索対象画像(テンプレート画像)との距離計算を行う対象領域も絞られる。これにより、複数の画像の検索に要する時間を短縮することができる。
【００５６】
また、上記ではコンポーネントツリーに対するキーコンポーネントの探索に深さ優先探索を適用している。これにより、キーコンポーネントの探索に幅優先探索を適用する場合と比較して、見つかったキーコンポーネントと同系列で二値化閾値がより高濃度側に位置しているノードに対してキーコンポーネントの判定を省略する場合に、アルゴリズムが簡単になる。
【００５７】
また、上記ではキーコンポーネントに対応する被検索対象画像の領域に対し、検索対象画像(テンプレート画像)の相対位置を左上から右下へ順次変化させながら各位置で距離計算を各々行っている。これにより、キーコンポーネントと検索対象画像(テンプレート画像)との大きさが一致しない場合にも距離の最小値を得ることができる。
【００５８】
なお、上記では被検索対象画像の一例としてコンピュータの画面をキャプチャする等によって得られた画像を挙げたが、これに限定されるものではない。開示の技術は、被検索対象画像が、被検索対象画像上での検索対象画像のサイズや向き、色が変化しない画像であれば適用可能であり、例えばイラストなどの画像であってもよい。
【００５９】
また、上記ではテンプレートマッチングプログラム４４が記憶部３６に予め記憶（インストール）されている態様を説明したが、これに限定されるものではない。開示の技術に係る画像処理プログラムは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記録媒体に記録されている形態で提供することも可能である。
【００６０】
本明細書に記載された全ての文献、特許出願及び技術規格は、個々の文献、特許出願及び技術規格が参照により取り込まれることが具体的かつ個々に記された場合と同程度に、本明細書中に参照により取り込まれる。
【００６１】
以上の実施形態に関し、更に以下の付記を開示する。
【００６２】
（付記１）
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成する階層グラフ作成部と、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で、対応する二値化閾値が最も低濃度側に位置している連結成分を探索する探索部と、
前記探索部によって探索された連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が最小の連結成分に対応する領域を検索結果として出力する距離演算部と、
を含む画像処理装置。
【００６３】
（付記２）
前記探索部は、前記階層グラフの系列に対して階層の深さ優先で探索することで、検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する付記１記載の画像処理装置。
【００６４】
（付記３）
前記距離演算部は、前記探索部によって探索された連結成分と前記検索対象画像との相対位置をずらしたときの複数の位置について前記距離を各々演算し、演算した距離が所定値以下の位置に対応する連結成分の対応領域を検索結果として出力する付記１又は付記２記載の画像処理装置。
【００６５】
（付記４）
前記探索部は、前記階層グラフ作成部によって作成された単一の前記階層グラフに基づき、複数の前記検索対象画像について前記連結成分の探索を順に行い、
前記距離演算部は、複数の前記検索対象画像について前記距離の演算及び検索結果の出力を順に行う付記１〜付記３の何れか１項記載の画像処理装置。
【００６６】
（付記５）
前記距離演算部から検索結果として出力された領域と前記検索対象画像との色の差に基づいて、前記領域が前記検索結果として適正か否か検証する検証部を更に備えた付記１〜付記４の何れか１項記載の画像処理装置。
【００６７】
（付記６）
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成し、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索し、
探索した連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する
ことを含む画像処理方法。
【００６８】
（付記７）
前記階層グラフの系列に対して階層の深さ優先で探索することで、検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する付記６記載の画像処理方法。
【００６９】
（付記８）
前記探索部によって探索された連結成分と前記検索対象画像との相対位置をずらしたときの複数の位置について前記距離を各々演算し、演算した距離が所定値以下の位置に対応する連結成分の対応領域を検索結果として出力する付記６又は付記７記載の画像処理方法。
【００７０】
（付記９）
作成した単一の前記階層グラフに基づき、複数の前記検索対象画像について前記連結成分の探索を順に行い、
複数の前記検索対象画像について前記距離の演算及び検索結果の出力を順に行う付記６〜付記８の何れか１項記載の画像処理方法。
【００７１】
（付記１０）
前記検索結果として出力した領域と前記検索対象画像との色の差に基づいて、前記領域が前記検索結果として適正か否か検証する付記６〜付記９の何れか１項記載の画像処理方法。
【００７２】
（付記１１）
コンピュータに、
被検索対象画像から、互いに異なる二値化閾値における対応する連結成分を階層的に関連付けた階層グラフを作成し、
検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索し、
探索した連結成分に対応する領域と前記検索対象画像との距離を演算し、距離が所定値以下の連結成分に対応する領域を検索結果として出力する
ことを含む処理を行わせるための画像処理プログラム。
【００７３】
（付記１２）
前記階層グラフの系列に対して階層の深さ優先で探索することで、検索対象画像とのサイズの違いが閾値以内で、かつ前記階層グラフの系列上で対応する二値化閾値が最も低濃度側に位置している連結成分を探索する付記１１記載の画像処理プログラム。
【００７４】
（付記１３）
前記探索部によって探索された連結成分と前記検索対象画像との相対位置をずらしたときの複数の位置について前記距離を各々演算し、演算した距離が所定値以下の位置に対応する連結成分の対応領域を検索結果として出力する付記１１又は付記１２記載の画像処理プログラム。
【００７５】
（付記１４）
作成した単一の前記階層グラフに基づき、複数の前記検索対象画像について前記連結成分の探索を順に行い、
複数の前記検索対象画像について前記距離の演算及び検索結果の出力を順に行う付記１１〜付記１３の何れか１項記載の画像処理プログラム。
【００７６】
（付記１５）
前記検索結果として出力した領域と前記検索対象画像との色の差に基づいて、前記領域が前記検索結果として適正か否か検証する付記１１〜付記１４の何れか１項記載の画像処理プログラム。
【符号の説明】
【００７７】
１０  画像処理装置
１２  マッチング候補検出部
１４  マッチング候補検証部
１６  コンポーネントツリー作成部
１８  キーコンポーネント抽出部
２０  キーコンポーネント照合部
３０  コンピュータ
３２  ＣＰＵ
３４  メモリ
３６  記憶部
４４  テンプレートマッチングプログラム
【図１】
2014182617.tif 000005
【図２】
2014182617.tif 000006
【図４】
2014182617.tif 000007
【図５】
2014182617.tif 000008
【図６】
2014182617.tif 000009
【図７】
2014182617.tif 000010
【図１４】
2014182617.tif 000011
【図３】
2014182617.tif 000012
【図８】
2014182617.tif 000013
【図９】
2014182617.tif 000014
【図１０】
2014182617.tif 000015
【図１１】
2014182617.tif 000016
【図１２】
2014182617.tif 000017
【図１３】
2014182617.tif 000018
【図１５】
2014182617.tif 000019