(57)【要約】【課題】テンプレート画像を含む画像の検索を高速に高い精度で行う。【解決手段】領域選択受付部６０１からの画像の領域の選択に基づいてテンプレート画像生成部３０１はテンプレート画像を生成する。このテンプレート画像および検索対象になるターゲット画像は、画像縮小部３０２において所定の縮小率に縮小される。個体抽出部３１１において生成されたターゲット画像とテンプレート画像とを照合する領域の情報を有する染色体の適応度が、ターゲット画像準備値テーブル３２０およびテンプレート画像準備値テーブル３２１に保持された準備値を用いて適応度算出部３１３において算出された後、遺伝的アルゴリズム処理部３１４で選択、交配および突然変異が行われる。以上の処理を所定世代数繰り返した後に、準最適解に対応する適応値が所定の閾値を超えているか否かが類似画像判断部３１８で判断される。【選択図】図３
2007102634.tif 000002
【特許請求の範囲】
【請求項１】
検索の対象になる複数のターゲット画像を保持するターゲット画像保持手段と、
前記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手段と、
前記選択を受け付けた領域の画像をテンプレート画像として生成するテンプレート画像生成手段と、
前記テンプレート画像および前記ターゲット画像を前記テンプレート画像の縦幅および横幅に応じた縮小率に縮小する画像縮小手段と、
前記縮小されたターゲット画像において前記縮小されたテンプレート画像と類似する画像を含む前記縮小されたターゲット画像を遺伝的アルゴリズムにより検索する類似画像検索手段と
を具備することを特徴とする画像処理装置。
【請求項２】
前記画像縮小手段は、前記テンプレート画像の縦幅と横幅との積が所定値以下の場合は前記画像縮小手段における縮小は行わないことを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記テンプレート画像生成手段は、前記選択された所定の領域を所定の倍率で拡大または縮小した画像を前記テンプレート画像として生成することを特徴とする請求項１記載の画像処理装置。
【請求項４】
前記類似画像検索手段は、
前記縮小されたターゲット画像よりランダムに複数の個体を抽出して前記個体の座標および前記テンプレート画像の拡大または縮小における前記所定の倍率に基づいた染色体情報を有する染色体を生成する個体抽出手段と、
前記染色体情報および画素値に基づいて前記染色体の適応度を算出する適応度算出手段と、
前記適応度算出手段において前記適応度を算出された前記染色体に対して選択、交配および突然変異のうち少なくとも１つの処理を行って新たな染色体情報を有する染色体を生成して前記適応度算出手段において前記新たな染色体情報を有する染色体についての適応度を算出させる遺伝的アルゴリズム処理手段と、
所定の条件に従って繰り返し行われる前記遺伝的アルゴリズム処理手段における処理の終了を指示する処理終了指示手段と、
前記適応度算出手段において最後に算出された適応度のうち最も値の大きい適応度を準最適解として判断する準最適解判断手段と、
前記準最適解が第１の閾値を超えた場合に前記縮小されたテンプレート画像に類似する画像が前記縮小されたターゲット画像に含まれると判断する類似画像判断手段と
を具備することを特徴とする請求項３記載の画像処理装置。
【請求項５】
前記画素値は、ＹＵＶ、ＲＧＢおよびＨＳＶの何れかを用いて表される量であることを特徴とする請求項４記載の画像処理装置。
【請求項６】
前記ターゲット画像における前記染色体に対応する領域の前記画素値の平均値と前記テンプレート画像における領域の前記画素値の平均値との差の絶対値を算出し、前記差の絶対値が第２の閾値を超えたか否かを判断する適応度算出前処理手段をさらに具備し、
前記適応度算出手段は、前記適応度前処理手段において前記差の絶対値が前記第２の閾値を超えたと判断された場合には前記類似画像判断手段における前記判断の対象から除外される十分に小さい値を前記適応度として設定することを特徴とする請求項５記載の画像処理装置。
【請求項７】
前記染色体に対応する前記ターゲット画像における領域の前記画素値の標準偏差および前記テンプレート画像における領域の前記画素値の標準偏差のそれぞれを２乗したものの比を算出し、前記比が所定の範囲内にあるか否かを判断する適応度算出前処理手段をさらに具備し、
前記適応度算出手段は、前記適応度前処理手段において前記比が所定の範囲内にあると判断された場合には前記類似画像判断手段における前記判断の対象から除外される十分に小さい値を前記適応度として設定することを特徴とする請求項５記載の画像処理装置。
【請求項８】
前記染色体に対応する前記ターゲット画像における領域の中央点の前記画素値と前記テンプレート画像における領域の中央点の前記画素値との差の絶対値を算出し、前記差の絶対値が第２の閾値を超えたか否かを判断する適応度算出前処理手段をさらに具備し、
前記適応度算出手段は、前記適応度前処理手段において前記差の絶対値が第２の閾値を超えたと判断された場合には前記類似画像判断手段における前記判断の対象から除外される十分に小さい値を前記適応度として設定することを特徴とする請求項５記載の画像処理装置。
【請求項９】
前記適応度算出手段は、前記画素値および前記染色体情報に基づいて前記染色体の適応度を相互相関関数により算出することを特徴とする請求項５記載の画像処理装置。
【請求項１０】
前記適応度算出手段は、前記ターゲット画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記ターゲット画像の前記画素値の平均値との差、および、前記テンプレート画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記テンプレート画像の前記画素値の平均値との差の積を、前記ターゲット画像および前記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を前記相互相関関数として用いることを特徴とする請求項９記載の画像処理装置。
【請求項１１】
前記縮小されたテンプレート画像および前記縮小されたターゲット画像における原点から任意の座標までの前記画素値を積算した準備値を前記縮小されたテンプレート画像および前記縮小されたターゲット画像の全ての座標において算出する準備値算出手段と、
前記縮小されたテンプレート画像における前記準備値を前記縮小されたテンプレート画像の座標と対応付けて保持するテンプレート画像準備値テーブルと、
前記縮小されたターゲット画像における前記準備値を前記縮小されたターゲット画像の座標と対応付けて保持するターゲット画像準備値テーブルと
をさらに具備し、
前記適応度算出手段は、前記準備値を用いて前記相互相関関数における前記画素値を前記ターゲット画像および前記テンプレート画像が重なり合う領域全ての座標において積算する計算を行い、前記染色体の適応度を算出することを特徴とする請求項９記載の画像処理装置。
【請求項１２】
前記適応度算出手段は、前記ターゲット画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記ターゲット画像の前記画素値の平均値との差、および、前記テンプレート画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記テンプレート画像の前記画素値の平均値との差の積を、前記ターゲット画像および前記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を前記相互相関関数として用い、前記画素値を構成する複数の要素それぞれについての前記相互相関関数による算出値を２乗したものの和の平方根を正規化したものを前記適応度として算出することを特徴とする請求項８記載の画像処理装置。
【請求項１３】
前記適応度算出手段は、前記ターゲット画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記テンプレート画像の前記画素値の平均値との差、および、前記テンプレート画像における任意の座標の前記画素値と前記ターゲット画像および前記テンプレート画像が重なり合う領域における前記ターゲット画像の前記画素値の平均値との差の積を、前記ターゲット画像および前記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を前記相互相関関数として用いることを特徴とする請求項８記載の画像処理装置。
【請求項１４】
前記適応度算出手段は、ｗを前記テンプレート画像の幅とし、ｈを前記テンプレート画像の高さとし、前記ターゲット画像の座標（Ｘ＋ｉ、Ｙ＋ｊ）における画素値をＴａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）とし、前記テンプレート画像の座標（ｉ、ｊ）における画素値をＴｅｍｐｌａｔｅ（ｉ、ｊ）とし、前記ターゲット画像および前記テンプレート画像が重なり合う領域における画素値の平均値をＭtargetとし、前記テンプレート画像の画素値の平均値をＭtemplateとし、前記相互相関関数として座標（Ｘ，Ｙ）における相互相関関係を表す以下の式
2007102634.tif 000017
を用いることを特徴とする請求項８記載の画像処理装置。
【請求項１５】
検索の対象になる複数のターゲット画像を保持するターゲット画像保持手段と、
前記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手段と、
前記選択を受け付けた領域における画像およびその領域における画像を所定の倍率で拡大または縮小した画像をテンプレート画像として生成するテンプレート画像生成手段と、
前記縮小されたターゲット画像よりランダムに複数の個体を抽出して前記個体の座標および前記テンプレート画像の拡大または縮小における前記所定の倍率に基づいた染色体情報を有する染色体を生成する個体抽出手段と、
前記染色体情報および画素値に基づいて前記染色体の適応度を算出する適応度算出手段と、
前記適応度算出手段において前記適応度を算出された前記染色体に対して選択、交配および突然変異のうち少なくとも１つの処理を行って新たな染色体情報を有する染色体を生成して前記適応度算出手段において前記新たな染色体情報を有する染色体についての適応度を算出させる遺伝的アルゴリズム処理手段と、
所定の条件に従って繰り返し行われる前記遺伝的アルゴリズム処理手段における処理の終了を指示する処理終了指示手段と、
前記適応度算出手段において最後に算出された適応度のうち最も値の大きい適応度を準最適解として判断する準最適解判断手段と、
前記準最適解に対応する前記ターゲット画像の領域を囲む所定の領域の全てにおいて前記所定の領域における適応度を算出してその適応度のうち最も値の大きい適応度を前記所定の領域における準最適解として判断する近傍領域準最適解判断手段と、
前記準最適解判断手段において判断された前記準最適解および前記近傍領域準最適解判断手段において判断された前記所定の領域における準最適解のうち最も大きい値が所定の閾値を超えた場合に前記縮小されたテンプレート画像に類似する画像が前記縮小されたターゲット画像に含まれると判断する類似画像判断手段と
を具備することを特徴とする画像処理装置。
【請求項１６】
検索の対象になるターゲット画像を保持するターゲット画像保持手段を備えた画像処理装置における処理方法であって、
前記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手順と、
前記選択を受け付けた領域の画像をテンプレート画像として生成するテンプレート画像生成手順と、
前記テンプレート画像および前記ターゲット画像を前記テンプレート画像の縦幅および横幅に応じた縮小率に縮小する画像縮小手順と、
前記縮小されたターゲット画像において前記縮小されたテンプレート画像と類似する画像を含む前記縮小されたターゲット画像を遺伝的アルゴリズムにより検索する類似画像検索手順と
を具備することを特徴とする処理方法。
【請求項１７】
検索の対象になるターゲット画像を保持するターゲット画像保持手段を備えた画像処理装置に、
前記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手順と、
前記選択を受け付けた領域の画像をテンプレート画像として生成するテンプレート画像生成手順と、
前記テンプレート画像および前記ターゲット画像を前記テンプレート画像の縦幅および横幅に応じた縮小率に縮小する画像縮小手順と、
前記縮小されたターゲット画像において前記縮小されたテンプレート画像と類似する画像を含む前記縮小されたターゲット画像を遺伝的アルゴリズムにより検索する類似画像検索手順と
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を検索する画像処理装置に関し、特に、高速にテンプレート画像と類似する画像を検索する画像処理装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。
【背景技術】
【０００２】
近年、メモリの価格の低減やメモリに関する技術の発達により、デジタルスチルカメラおよびデジタルビデオカメラ等の撮像装置におけるメモリの容量は増加している。これに伴い、撮像装置に保持される静止画像や動画像の数も増えている。このような状況下においては、ユーザーが閲覧したい静止画像や動画像を探し出すことが困難になってきている。
【０００３】
このような問題点を解決するため、ユーザーが所望する画像をテンプレート画像として指定して、検索対象画像中よりそのテンプレート画像とマッチングする画像を検索する画像検索方法が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開平８−２６３５２２号公報（図２）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一般に、撮像装置においては、装置自体の小型化やコストの低減等の要請から高い演算処理能力を持つＣＰＵ（Central Processing Unit）を搭載することが難しい状況にある。このような撮像装置に、上述の画像検索方法を実現させたとしても、検索の演算処理に多くの時間を要し、実用性に欠くこととなる。このため、演算処理に要する時間を低減させる必要性は高い。また、演算処理にかかる時間を低減させるとともに、検索の精度を下げないようにすることも必要である。
【０００５】
そこで、本発明は、画像の検索を高速に高い精度で行う画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、検索の対象になる複数のターゲット画像を保持するターゲット画像保持手段と、上記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手段と、上記選択を受け付けた領域の画像をテンプレート画像として生成するテンプレート画像生成手段と、上記テンプレート画像および上記ターゲット画像を上記テンプレート画像の縦幅および横幅に応じた縮小率に縮小する画像縮小手段と、上記縮小されたターゲット画像において上記縮小されたテンプレート画像と類似する画像を含む上記縮小されたターゲット画像を遺伝的アルゴリズムにより検索する類似画像検索手段とを具備することを特徴とする画像処理装置である。これにより、選択されたテンプレート画像の横幅および縦幅に応じた縮小率にテンプレート画像およびターゲット画像を縮小してテンプレート画像に類似する画像が含まれたターゲット画像を高速に検索させるという作用をもたらす。すなわち、テンプレート画像およびターゲット画像を縮小することによって、テンプレート画像とターゲット画像とを照合する面積が低減されるため、照合に要する演算量を低減することができる。
【０００７】
また、この第１の側面において、上記画像縮小手段は、上記テンプレート画像の縦幅と横幅との積が所定値以下の場合は上記画像縮小手段における縮小は行わないことを特徴とするものである。これにより、選択されたテンプレート画像の横幅および縦幅が小さい場合に検索精度を低減させないという作用をもたらす。
【０００８】
また、この第１の側面において、上記テンプレート画像生成手段は、上記選択された所定の領域を所定の倍率で拡大または縮小した画像を上記テンプレート画像として生成することを特徴とするものである。これにより、テンプレート画像を拡大、縮小および回転させた画像と類似する画像をも検索させるという作用をもたらす。
【０００９】
また、上記類似画像検索手段は、上記類似画像検索手段は、上記縮小されたターゲット画像よりランダムに複数の個体を抽出して上記個体の座標および上記テンプレート画像の拡大または縮小における上記所定の倍率に基づいた染色体情報を有する染色体を生成する個体抽出手段と、上記染色体情報および画素値に基づいて上記染色体の適応度を算出する適応度算出手段と、上記適応度算出手段において上記適応度を算出された上記染色体に対して選択、交配および突然変異のうち少なくとも１つの処理を行って新たな染色体情報を有する染色体を生成して上記適応度算出手段において上記新たな染色体情報を有する染色体についての適応度を算出させる遺伝的アルゴリズム処理手段と、所定の条件に従って繰り返し行われる上記遺伝的アルゴリズム処理手段における処理の終了を指示する処理終了指示手段と、上記適応度算出手段において最後に算出された適応度のうち最も値の大きい適応度を準最適解として判断する準最適解判断手段と、上記準最適解が第１の閾値を超えた場合に上記縮小されたテンプレート画像に類似する画像が上記縮小されたターゲット画像に含まれると判断する類似画像判断手段とを具備することを特徴とするものである。ここで第１の閾値とは、テンプレート画像がターゲット画像に含まれるか否かを判断する際の基準となる値を言う。すなわち、準最適解とされた適応度の値が第１の閾値を超えていればテンプレート画像がターゲット画像に含まれることになり、準最適解とされた適応度の値が第１の閾値を超えていなければテンプレート画像がターゲット画像に含まれないことになる。これにより、遺伝的アルゴリズムにおいてテンプレート画像とターゲット画像とを照合する領域についての情報を染色体に持たせ、その染色体の適応度に基づいてテンプレート画像に類似する画像が含まれたターゲット画像を高速に検索させるという作用をもたらす。
【００１０】
また、上記画素値は、ＹＵＶ、ＲＧＢおよびＨＳＶの何れかを用いて表される量であることを特徴とするものである。これにより、ＹＵＶ、ＲＧＢおよびＨＳＶに基づいて遺伝的アルゴリズムにおける染色体の適応度を算出させるという作用をもたらす。
【００１１】
また、当該画像処理装置は、上記ターゲット画像における上記染色体に対応する領域の上記画素値の平均値と上記テンプレート画像における領域の上記画素値の平均値との差の絶対値を算出し、上記差の絶対値が第２の閾値を超えたか否かを判断する適応度算出前処理手段をさらに具備し、上記適応度算出手段は、上記適応度前処理手段において上記差の絶対値が上記第２の閾値を超えたと判断された場合には上記類似画像判断手段における前記判断の対象から除外される十分に小さい値を上記適応度として設定することを特徴とするものである。ここで第２の閾値とは、ターゲット画像における染色体に対応する領域の画素値の平均値とテンプレート画像における領域の画素値の平均値との差の絶対値に基づいて適応度を評価する際に基準となる値を言う。これにより、遺伝的アルゴリズムにおける染色体の適応度を演算量の少ない方法で決定させるという作用をもたらす。
【００１２】
また、当該画像処理装置は、上記染色体に対応する上記ターゲット画像における領域の上記画素値の標準偏差および上記テンプレート画像における領域の上記画素値の標準偏差のそれぞれを２乗したものの比を算出し、上記比が所定の範囲内にあるか否かを判断する適応度算出前処理手段をさらに具備し、上記適応度算出手段は、上記適応度前処理手段において上記比が所定の範囲内にあると判断された場合には上記類似画像判断手段における前記判断の対象から除外される十分に小さい値を上記適応度として設定することを特徴とするものである。これにより、遺伝的アルゴリズムにおける染色体の適応度を演算量の少ない方法で決定させるという作用をもたらす。
【００１３】
また、当該画像処理装置は、上記染色体に対応する上記ターゲット画像における領域の中央点の上記画素値と上記テンプレート画像における領域の中央点の上記画素値との差の絶対値を算出し、上記差の絶対値が第２の閾値を超えたか否かを判断する適応度算出前処理手段をさらに具備し、上記適応度算出手段は、上記適応度前処理手段において上記差の絶対値が第２の閾値を超えたと判断された場合には上記類似画像判断手段における前記判断の対象から除外される十分に小さい値を上記適応度として設定することを特徴とするものである。ここで第２の閾値とは、ターゲット画像における領域の中央点の画素値と上記テンプレート画像における領域の中央点の画素値との差の絶対値に基づいて適応度を評価する際に基準となる値を言う。これにより、遺伝的アルゴリズムにおける染色体の適応度を演算量の少ない方法で決定させるという作用をもたらす。
【００１４】
また、上記適応度算出手段は、上記画素値および上記染色体情報に基づいて上記染色体の適応度を相互相関関数により算出することを特徴とするものである。これにより、ターゲット画像とテンプレート画像との相互の関連性がどれくらいあるかという観点から遺伝的アルゴリズムにおける染色体の適応度を算出させるという作用をもたらす。
【００１５】
また、上記適応度算出手段は、上記ターゲット画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記ターゲット画像の上記画素値の平均値との差、および、上記テンプレート画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記テンプレート画像の上記画素値の平均値との差の積を、上記ターゲット画像および上記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を上記相互相関関数として用いることを特徴とするものである。これにより、画素値についてターゲット画像とテンプレート画像との相互の関連性がどれくらいあるかというという観点から遺伝的アルゴリズムにおける染色体の適応度を算出させるという作用をもたらす。
【００１６】
また、当該画像処理装置は、上記縮小されたテンプレート画像および上記縮小されたターゲット画像における原点から任意の座標までの上記画素値を積算した準備値を上記縮小されたテンプレート画像および上記縮小されたターゲット画像の全ての座標において算出する準備値算出手段と、上記縮小されたテンプレート画像における上記準備値を上記縮小されたテンプレート画像の座標と対応付けて保持するテンプレート画像準備値テーブルと、上記縮小されたターゲット画像における上記準備値を上記縮小されたターゲット画像の座標と対応付けて保持するターゲット画像準備値テーブルとをさらに具備し、上記適応度算出手段は、上記準備値を用いて上記相互相関関数における上記画素値を上記ターゲット画像および上記テンプレート画像が重なり合う領域全ての座標において積算する計算を行い、上記染色体の適応度を算出することを特徴とするものである。これにより、遺伝的アルゴリズムにおける染色体の適応度の算出する際の演算量を低減させるという作用をもたらす。
【００１７】
また、上記適応度算出手段は、上記ターゲット画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記ターゲット画像の上記画素値の平均値との差、および、上記テンプレート画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記テンプレート画像の上記画素値の平均値との差の積を、上記ターゲット画像および上記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を上記相互相関関数として用い、上記画素値を構成する複数の要素それぞれについての上記相互相関関数による算出値を２乗したものの和の平方根を正規化したものを上記適応度として算出することを特徴とするものである。これにより、画素値におけるそれぞれの要素を総合してターゲット画像とテンプレート画像との相互の関連性がどれくらいあるかというという観点から遺伝的アルゴリズムにおける染色体の適応度を算出させるという作用をもたらす。
【００１８】
また、  上記適応度算出手段は、上記ターゲット画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記テンプレート画像の上記画素値の平均値との差、および、上記テンプレート画像における任意の座標の上記画素値と上記ターゲット画像および上記テンプレート画像が重なり合う領域における上記ターゲット画像の上記画素値の平均値との差の積を、上記ターゲット画像および上記テンプレート画像が重なり合う領域全ての座標において積算したものを正規化した関数を上記相互相関関数として用いることを特徴とするものである。これにより、ターゲット画像およびテンプレート画像の直流成分をも加味して染色体の適応度を算出させるという作用をもたらす。すなわち、テンプレート画像に類似する画像が含まれたターゲット画像を精度よく検索させることができる。
【００１９】
また、上記適応度算出手段は、上記相互相関関数として座標（Ｘ，Ｙ）における相互相関関係を表す以下の式を用いることを特徴とするものである。なお、以下の式において、ｗ、ｈは、それぞれ上記テンプレート画像の幅と高さを表す。また、Ｔａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）は、上記ターゲット画像の座標（Ｘ＋ｉ、Ｙ＋ｊ）における画素値を表す。また、Ｔｅｍｐｌａｔｅ（ｉ、ｊ）は、上記テンプレート画像の座標（ｉ、ｊ）における画素値を表す。また、Ｍtargetは、上記ターゲット画像および上記テンプレート画像が重なり合う領域における画素値の平均値を表す。また、Ｍtemplateは、上記テンプレート画像の画素値の平均値を表す。これにより、ターゲット画像およびテンプレート画像の直流成分をも加味して染色体の適応度を算出させるという作用をもたらす。すなわち、テンプレート画像に類似する画像が含まれたターゲット画像を精度よく検索させることができる。
2007102634.tif 000003
【００２０】
また、本発明の第２の側面は、検索の対象になる複数のターゲット画像を保持するターゲット画像保持手段と、上記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手段と、上記選択を受け付けた領域における画像およびその領域における画像を所定の倍率で拡大または縮小した画像をテンプレート画像として生成するテンプレート画像生成手段と、上記縮小されたターゲット画像よりランダムに複数の個体を抽出して上記個体の座標および上記テンプレート画像の拡大または縮小における上記所定の倍率に基づいた染色体情報を有する染色体を生成する個体抽出手段と、上記染色体情報および画素値に基づいて上記染色体の適応度を算出する適応度算出手段と、上記適応度算出手段において上記適応度を算出された上記染色体に対して選択、交配および突然変異のうち少なくとも１つの処理を行って新たな染色体情報を有する染色体を生成して上記適応度算出手段において上記新たな染色体情報を有する染色体についての適応度を算出させる遺伝的アルゴリズム処理手段と、所定の条件に従って繰り返し行われる上記遺伝的アルゴリズム処理手段における処理の終了を指示する処理終了指示手段と、上記適応度算出手段において最後に算出された適応度のうち最も値の大きい適応度を準最適解として判断する準最適解判断手段と、上記準最適解に対応する上記ターゲット画像の領域を囲む所定の領域の全てにおいて上記所定の領域における適応度を算出してその適応度のうち最も値の大きい適応度を上記所定の領域における準最適解として判断する近傍領域準最適解判断手段と、上記準最適解判断手段において判断された上記準最適解および上記近傍領域準最適解判断手段において判断された上記所定の領域における準最適解のうち最も大きい値が所定の閾値を超えた場合に上記縮小されたテンプレート画像に類似する画像が上記縮小されたターゲット画像に含まれると判断する類似画像判断手段とを具備することを特徴とする画像処理装置である。これにより、テンプレート画像に類似する画像が含まれたターゲット画像の検索漏れが生じる可能性を低減させるという作用をもたらす。
【００２１】
また、本発明の第３の側面は、検索の対象になるターゲット画像を保持するターゲット画像保持手段を備えた画像処理装置において以下の手順を実行する処理方法または以下の手順をコンピュータに実行させるプログラムであって、上記複数のターゲット画像の何れか一つに対する所定の領域の選択を受け付ける領域選択受付手順と、上記選択を受け付けた領域の画像をテンプレート画像として生成するテンプレート画像生成手順と、上記テンプレート画像および上記ターゲット画像を上記テンプレート画像の縦幅および横幅に応じた縮小率に縮小する画像縮小手順と、上記縮小されたターゲット画像において上記縮小されたテンプレート画像と類似する画像を含む上記縮小されたターゲット画像を遺伝的アルゴリズムにより検索する類似画像検索手順とを具備することを特徴とする処理方法またはこれらの手順をコンピュータに実行させるプログラムである。これにより、選択されたテンプレート画像の横幅および縦幅に応じた縮小率にテンプレート画像およびターゲット画像を縮小してテンプレート画像に類似する画像が含まれたターゲット画像を高速に検索させるという作用をもたらす。
【発明の効果】
【００２２】
本発明によれば、画像の検索を高速に高い精度で行うことができるという優れた効果を奏し得る。
【発明を実施するための最良の形態】
【００２３】
次に本発明の実施の形態について図面を参照して詳細に説明する。なお、本発明の実施の形態においては、画像処理装置の一例として撮像装置について説明する。
【００２４】
図１は、本発明の実施の形態における撮像装置１００の一例である撮像装置１００ａおよび１００ｂの外観図である。撮像装置１００ａは、主として静止画像を撮像するものであり、撮像装置１００ｂは、主として動画像を撮像するものである。
【００２５】
図１（ａ）は、撮像装置１００ａの正面図である。撮像装置１００ａは、レンズ部１１０ａから被写体を撮像する。そして、撮像装置１００ａは、シャッター部１２０ａが押下されると静止画を生成する。図１（ｂ）は、撮像装置１００ａの背面図である。レンズ部１１０ａによって捕らえられた被写体の動きはディスプレイ部１３０ａに映し出される。また、生成された静止画もディスプレイ部１３０ａに映し出される。
【００２６】
図１（ｃ）は、撮像装置１００ｂの正面図である。撮像装置１００ｂは、レンズ部１１０ｂから被写体を撮像する。そして、撮像装置１００ｂは、（図示しない）録画ボタンが押下されると動画を生成する。図１（ｄ）は、撮像装置１００ｂの背面図である。レンズ部１１０ｂによって捕らえられた被写体の動きはディスプレイ部１３０ｂに映し出される。また、生成された動画もディスプレイ部１３０ｂに映し出される。また、撮像装置１００ｂは、静止画も生成する機能を有しており、生成された静止画もディスプレイ部１３０ｂに映し出される。
【００２７】
本発明の実施の形態においては、ディスプレイ部１３０ａおよび１３０ｂに映し出された静止画の一部を選択して切り出し、その切り出された静止画をテンプレート画像とするものである。本発明の実施の形態において静止画の一部を選択する操作は、ディスプレイ部１３０ａおよび１３０ｂを直接押下することにより指定するタッチパネル方式を想定しているが、これに限るものではない。
【００２８】
このテンプレート画像は、撮像装置１００ａおよび１００ｂに内蔵された（図示しない）記憶装置に保持された画像から所望の画像を検索する際に用いられるものである。以下において、検索の対象になる記憶装置に保持された画像をターゲット画像と呼ぶ。そして、本発明の実施の形態においては、テンプレート画像に類似する画像が含まれたターゲット画像を検索する。検索に際しては、まず、テンプレート画像およびターゲット画像をテンプレート画像の縦幅および横幅に応じた縮小率に縮小した後、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）を用いてテンプレート画像に類似する画像が含まれたターゲット画像を検索する。
【００２９】
なお、遺伝的アルゴリズムとは、生物の進化過程に倣って確率論的なデータ処理によって最適解を得ようとする手法である。その手法の具体的内容は、まずランダムに個体を抽出して、染色体をその個体数だけ生成して初期集団を生成する。次に初期集団に属する各染色体に対して適応度を求める。なお、適応度とは、本発明の実施の形態においては、テンプレート画像に類似する画像がターゲット画像に含まれるか否かを評価するための評価値である。
【００３０】
適応度を求めた後に、選択、交配および突然変異の処理を行い、新たな染色体を生成する。新たな染色体が生成されると、さらにその新たな染色体について上記と同様に適応度を求める。所定の終了条件を満たすと以上の処理は終了し、適応度の高い染色体が準最適解とされる。この準最適解が予め定めた所定の閾値を超える場合に、そのターゲット画像はテンプレート画像に類似する画像を含むものと判断されて、検索結果として出力される。
【００３１】
図２は、本発明の実施の形態における撮像装置１００の構成を示す図である。本発明の実施の形態における撮像装置１００は、撮像部１０と、記録再生処理部２０と、制御部３０と、バス４０と、キー入力部５０と、タッチパネル部６０、記憶装置７０とを備える。
【００３２】
撮像部１０は、撮像素子部１１と、撮像制御部１２と、画像処理部１３とを備える。撮像素子部１１は、内部に、被写体を撮像するためのレンズ群（図１におけるレンズ部１１０ａおよび１１０ｂに対応）、絞り調整機構、フォーカス調整機構および例えばＣＣＤ（Charge Coupled Devices）などの撮像素子などを備えており、レンズ群を通じた像がＣＣＤなどの撮像素子の結像面に結像される。撮像素子部１１は、シャッター操作に応じて制御部３０からバス４０を通じて供給される画像取り込みタイミング信号を受けて、撮像素子の結像面に結像されている被写体像を撮像信号に変換し、画像処理部１３に供給する。
【００３３】
撮像制御部１２は、制御部３０からバス４０を通じて供給される制御信号を受けて、撮像素子部１１に供給する制御信号を生成する。また、撮像制御部１２は、生成した制御信号を撮像素子部１１に供給して、ズーム制御、シャッター制御および露出制御などを行う。
【００３４】
画像処理部１３は、制御部３０からバス４０を通じて供給される制御信号に基づいて、撮像信号についてのガンマ補正やＡＧＣ（Auto Gain Control）などの処理を行うとともに、撮像信号をデジタル信号としての画像信号に変換する処理も行う。
【００３５】
記録再生処理部２０は、画像符号化／復号部２１と、記録制御部２２と、ＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）２３とを備える。画像符号化／復号部２１は、撮像部１０からバス４０を通じて供給される画像信号などを符号化し多重化して圧縮データに変換する符号化機能を有する。また、画像符号化／復号部２１は、圧縮データから画像信号を復号する復号機能を有する。
【００３６】
記録制御部２２は、画像符号化／復号部２１から圧縮データを受けて記憶装置７０に書き込む。また、記録制御部２２は、記憶装置７０から圧縮データを読み出して画像符号化／復号部２１に供給する。なお、記憶装置７０は、撮像装置１００に外付けされたものでも内蔵されたものであってもよい。また、記憶装置７０としては、フラッシュメモリ（Flash memory）をカード型にパッケージしたメモリカード、ハードディスク等の磁気ディスク、ＤＶＤ等の光ディスク（Optical Disk）およびＭＯ等の光磁気ディスク（Magneto-Optical disk）のいずれかが想定されるが、これに限るものではない。ＳＤＲＡＭ２３は、符号化／復号部２１における符号化または復号のための作業領域として利用される。
【００３７】
制御部３０は、システム制御部３１と、入力制御部３２と、表示制御部３３と、出力画像処理部３４と、外部機器制御部３５と、ネットワーク制御部３６とを備える。
【００３８】
システム制御部３１は、制御部３０全体の処理を司るものである。入力制御部３２に接続されるキー入力部５０には、撮影モードと再生モードなどの他のモードとを切り換えるモード切り換えキー、ズーム調整キー、露出調整のためのキー、シャッターキー（図１におけるシャッター部１２０ａに対応）、動画撮影用キーなどの複数のキーが設けられている。また、入力制御部３２に接続されるタッチパネル入力部６２は、表示部６１に表示されるメニューの選択や画像データの所定領域の指定を受け付けるものである。
【００３９】
入力制御部３２は、キー入力部５０およびタッチパネル入力部６２からの操作信号をシステム制御部３１に伝える。システム制御部３１は、キー入力部５０およびタッチパネル入力部６２においていずれのキー等が操作されたかを判別し、その判別結果に応じた制御処理を行う。
【００４０】
表示制御部３３に接続される表示部６１は、例えばＬＣＤ（Liquid Crystal Display）などにより構成され、システム制御部３１の制御の下に、撮像部１０からバス４０を通じて供給される画像信号や、記憶装置７０から読み出された画像信号を表示する。なお、表示部６１は、図１におけるディスプレイ部１３０ａおよび１３０ｂに対応するものである。
【００４１】
出力画像処理部３４は、画像データ再生時において画像データに所定の修飾処理を施すものである。修飾処理とは、例えば画像データの色補正等が想定される。なお、出力画像処理部３４で行われる画像データに対する処理をシステム制御部３１で行うように構成してもよい。
【００４２】
外部機器制御部３５に接続される外部機器８０は、例えばパーソナルコンピュータ（Personal Computer）等が想定されるが、これに限るものではない。なお、外部機器８０と外部機器制御部３５との間は、例えばＵＳＢ（Universal Serial Bus）ケーブルによって接続されることが想定されるが、これに限るものではない。外部機器制御部３５は、撮像装置１００と外部機器８０との間のデータのやりとりを制御するものである。
【００４３】
ネットワーク制御部３６は、撮像装置１００とネットワーク網９０との間でやりとりされるデータを制御するものである。なお、ネットワーク網としては、インターネットやＬＡＮ（Local Area Network）が想定されるが、これに限るものではない。
【００４４】
図３は、本発明の実施の形態における画像検索機能の構成の一例を示す図である。この画像検索機能は、領域選択受付部６０１と、テンプレート画像生成部３０１と、画像縮小部３０２と、図１において説明したターゲット画像を複数保持するターゲット画像保持部２３１と、類似画像検索部３１０とを備える。
【００４５】
領域選択受付部６０１は、ターゲット画像保持部２３１に保持された複数のターゲット画像のうち何れか一つのターゲット画像の選択およびそのターゲット画像中においてテンプレート画像として切り出すべき領域の選択を受け付けるものである。
【００４６】
テンプレート画像生成部３０１は、領域選択受付部６０１において受け付けられたターゲット画像におけるテンプレート画像として切り出すべき領域をターゲット画像から切り出すことによってテンプレート画像を生成するものである。
【００４７】
また、テンプレート画像生成部３０１は、上記切り出すことによって生成されたテンプレート画像を所定の倍率で拡大および縮小した画像も生成する。この拡大および縮小した画像もテンプレート画像として用いられる。また、テンプレート画像生成部３０１は、上記切り出すことによって生成されたテンプレート画像、拡大および縮小した画像を所定角度回転させた画像も生成する。この所定角度回転させた画像もテンプレート画像として用いられる。
【００４８】
画像縮小部３０２は、テンプレート画像生成部３０１において生成されたテンプレート画像およびターゲット画像をテンプレート画像の縦幅および横幅に応じた縮小率に縮小するものである。ターゲット画像およびテンプレート画像を縮小することによって、後に行われる検索処理における計算量を減らすことができ、検索処理を高速に行うことを可能とする。また、ターゲット画像およびテンプレート画像を縮小すると、検索において画像細部の本質的ではない差異やノイズが検出され難くなるため、検索精度も向上する。
【００４９】
しかしながら、テンプレート画像の大きさが比較的小さい場合には、縮小することによってさらに小さくなると検索精度が低くなる可能性がある。このため、例えばテンプレート画像の縦幅と横幅との積が所定値以下の場合は、ターゲット画像およびテンプレート画像の縮小率を１とする（縮小しない）ことによって検索精度の低下を防ぐことができる。
【００５０】
類似画像検索部３１０は、遺伝的アルゴリズムを用いてテンプレート画像と類似する画像を含むターゲット画像を検索するものであり、個体抽出部３１１と、適応度算出前処理部３１２と、適応度算出部３１３と、遺伝的アルゴリズム処理部３１４と、処理終了指示部３１５と、準最適解判断部３１６と、近傍領域準最適解判断部３１７と、類似画像判断部３１８と、準備値算出部３１９と、ターゲット画像準備値テーブル３２０と、テンプレート画像準備値テーブル３２１とを備える。
【００５１】
個体抽出部３１１は、画像縮小部３０２において縮小されたターゲット画像よりランダムに複数の個体を抽出して、個体のターゲット画像上における座標およびテンプレート画像の拡大または縮小における所定の倍率に基づいた染色体情報を有する染色体を個体数だけ生成するものである。これにより、図１において述べた遺伝的アルゴリズムにおける初期集団が生成される。
【００５２】
上記染色体情報における個体のターゲット画像上における座標およびテンプレート画像の拡大または縮小における所定の倍率が表しているのは、ターゲット画像と所定の倍率に拡大または縮小したテンプレート画像とを重ね合わせて照合（マッチング）を行うマッチング領域である。このマッチング領域としては、例えば、所定の倍率に拡大または縮小したテンプレート画像の原点をテンプレート画像の左上端に定めて、その左上端を染色体のターゲット画像上における座標に位置させた場合に、ターゲット画像とテンプレート画像が重なり合う領域が想定される。
【００５３】
適応度算出前処理部３１２は、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値を算出するものである。なお、本発明の実施の形態において画素値とは、例えばＹＵＶ、ＲＧＢおよびＨＳＶの何れかを用いて表される量であり、その量としては輝度[0]や色差などが想定される。この場合、適応度算出前処理部３１２は、マッチング領域におけるターゲット画像およびテンプレート画像の輝度[0]または色差の平均値の差の絶対値を算出することになる。
【００５４】
適応度算出前処理部３１２においてマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値が所定の閾値を超えていると判断されると、後述する適応度算出部３１３においてそのマッチング領域に対応する染色体の適応度は、ゼロを含む十分に小さい値とされる。すなわち、適応度算出前処理部３１２においてマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値が所定の閾値を超えていると判断された場合は、適応度を計算するまでもなくそのターゲット画像のマッチング領域にはテンプレート画像に類似する画像は含まれないと推定する。したがって、この場合に適応度算出部３１３によって設定される適応度は、類似判断から除外されるために十分に小さい値（ゼロを含む）が設定される必要がある。
【００５５】
また、適応度算出前処理部３１２は、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比を算出して、適応度計算の要否を判断してもよい。この場合、適応度算出前処理部３１２において画素値の標準偏差を２乗したものの比が所定の範囲にないと判断されると、後述する適応度算出部３１３においてそのマッチング領域に対応する染色体の適応度は、ゼロを含む十分に小さい値とされる。すなわち、適応度算出前処理部３１２において画素値の標準偏差を２乗したものの比が所定の範囲にないと判断された場合は、適応度を計算するまでもなくそのターゲット画像のマッチング領域にはテンプレート画像に類似する画像は含まれないと推定する。したがって、この場合に適応度算出部３１３によって設定される適応度は、類似判断から除外されるために十分に小さい値（ゼロを含む）が設定される必要がある。
【００５６】
また、適応度算出前処理部３１２は、マッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値を算出して、適応度計算の要否を判断してもよい。この場合、マッチング領域の中央点における画素値の平均値の差の絶対値が所定の閾値を超えていると判断されると、後述する適応度算出部３１３においてそのマッチング領域に対応する染色体の適応度は、ゼロを含む十分に小さい値とされる。すなわち、マッチング領域の中央点における画素値の平均値の差の絶対値が所定の閾値を超えていると判断された場合は、適応度を計算するまでもなくそのターゲット画像のマッチング領域にはテンプレート画像に類似する画像は含まれないと推定する。したがって、この場合に適応度算出部３１３によって設定される適応度は、類似判断から除外されるために十分に小さい値（ゼロを含む）が設定される必要がある。
【００５７】
以上のマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値による染色体の適応度の評価、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比による染色体の適応度の評価、および、マッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値による染色体の適応度の評価は、全て行うようにしてもよく、また何れかを選択して行うようにしてもよい。なお、適応度算出前処理部３１２における各染色体に対する適応度の評価についての詳細は後述する。
【００５８】
適応度算出部３１３は、染色体情報および画素値に基づいて個体抽出部３１１において抽出された個体から生成された染色体の適応度の算出を行うものである。この適応度によりターゲット画像にテンプレート画像と類似する画像が含まれるか否かの評価が行われる。すなわち、適応度が所定の閾値より高い場合、ターゲット画像にテンプレート画像と類似する画像が含まれると評価される。本発明の実施の形態においては、適応度を算出する際に用いられる関数として相互相関関数を想定しており、その相互相関関数の一例を数１に示す。
【数１】
2007102634.tif 000004
【００５９】
数１に示す相互相関関数は、マッチング領域におけるターゲット画像とテンプレート画像との類似の度合いを与える関数で、−１≦ｆ（Ｘ、Ｙ）≦１の範囲の値を与える。マッチング領域におけるターゲット画像とテンプレート画像とが完全に一致する場合には、ｆ（Ｘ、Ｙ）＝１になる。なお、数１において、ｗ、ｈは、それぞれテンプレート画像の幅と高さを表す。また、Ｔａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）は、ターゲット画像の座標（Ｘ＋ｉ、Ｙ＋ｊ）における画素値を表す。また、Ｔｅｍｐｌａｔｅ（ｉ、ｊ）は、テンプレート画像の座標（ｉ、ｊ）における画素値を表す。また、Ｍtargetは、ターゲット画像のマッチング領域における画素値の平均値を表す。また、Ｍtemplateは、テンプレート画像の画素値の平均値を表す。
【００６０】
なお、適応度算出部３１３において適応度を算出する際に用いられる相互相関関数として、数１に示す相互相関関数以外にも数２に示す相互相関関数を用いて適応度を算出してもよい。数２に示す相互相関関数は、数１におけるＭtargetとＭtemplateとを入れ替えたものであり、それ以外は数１において説明したことと同様である。
【数２】
2007102634.tif 000005
【００６１】
ここで数２の式を数１と比較して説明する。数１の相互相関関数における「Ｔａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）−Ｍtarget」はターゲット画像における画素値からターゲット画像における画素値の直流成分を除いたターゲット画像における画素値の交流成分のみを表すものであり、「Ｔｅｍｐｌａｔｅ（ｉ、ｊ）−Ｍtemplate」はテンプレート画像における画素値からテンプレート画像における画素値の直流成分を除いたテンプレート画像における画素値の交流成分のみを表すものである。数１によると、分子は、ターゲット画像における画素値の交流成分とテンプレート画像における画素値の交流成分の積になるため、直流成分を加味した結果が得られない。このため、ターゲット画像とテンプレート画像とをマッチングした場合、両者は類似していないにも関わらず、ｆ（Ｘ、Ｙ）の値としては高い値が出ることがあり得る。
【００６２】
一方、数２の相互相関関数における「Ｔａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）−Ｍtemplate」はターゲット画像における画素値からテンプレート画像における画素値の直流成分を除いたものであり、「Ｔｅｍｐｌａｔｅ（ｉ、ｊ）−Ｍtarget」はテンプレート画像における画素値からターゲット画像における画素値の直流成分を除いたものである。この場合、ターゲット画像の直流成分とテンプレート画像の直流成分に差がある場合、Ｔａｒｇｅｔ（Ｘ＋ｉ、Ｙ＋ｊ）−ＭtemplateおよびＴｅｍｐｌａｔｅ（ｉ、ｊ）−Ｍtargetには、交流成分のみならず直流成分も残る。すなわち、直流成分も加味された結果が出てくる。このため、数１により適応度を算出するよりも精度の高い検索ができる。
【００６３】
また、数１および数２を利用して適応度算出部３１３において適応度を算出する際に用いられる関数として数３に示す関数を用いても良い。
【数３】
2007102634.tif 000006
【００６４】
数３は、画素値としてＹＵＶを用いて表した場合における適応度を算出する際に用いられる関数である。ｆ＿Ｙ（Ｘ、Ｙ）は、数１または数２におけるｆ（Ｘ、Ｙ）における画素値としてＹ成分（輝度）を用いたことを表す式である。また、ｆ＿Ｕ（Ｘ、Ｙ）は、数１または数２におけるｆ（Ｘ、Ｙ）における画素値としてＵ成分（輝度信号と青色成分の差）を用いたことを表す式である。また、ｆ＿Ｖ（Ｘ、Ｙ）は、数１または数２におけるｆ（Ｘ、Ｙ）における画素値としてＶ成分（輝度信号と赤色成分の差）を用いたことを表す式である。
【００６５】
数３は、ｆ＿Ｙ（Ｘ、Ｙ）、ｆ＿Ｕ（Ｘ、Ｙ）およびｆ＿Ｖ（Ｘ、Ｙ）のそれぞれを２乗して足し合わせたものの平方根をとっている。そして、ｆ＿Ｙ（Ｘ、Ｙ）、ｆ＿Ｕ（Ｘ、Ｙ）およびｆ＿Ｖ（Ｘ、Ｙ）のそれぞれを２乗して足し合わせたものの平方根を正規化するために３の平方根で除している。数３においてはＹＵＶを１：１：１で合成したが、ＹＵＶのいずれかの成分を重視して別の比率で合成してもよい。
【００６６】
数３によれば、Ｙ成分（輝度）のみならずＵ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）も加味した結果が得られるため、高精度なマッチングが可能である。
【００６７】
なお、以上、数１乃至数３において説明したｆ（Ｘ、Ｙ）は、−１から１の範囲となるが、適応度算出部３１３における算出結果として０から１の範囲を示す適応度「ｆ´（Ｘ、Ｙ）＝（ｆ（Ｘ、Ｙ）＋１）／２」を供給することが想定される。
【００６８】
遺伝的アルゴリズム処理部３１４は、適応度算出部３１３において適応度を算出された染色体に対して選択、交配および突然変異の処理を行って新たな染色体情報を有する染色体を生成するものである。なお、選択とは、適応度算出部３１３において算出された適応度に基づいて染色体を所定数選択する処理を言う。また、交配とは、例えば上記選択によって選択された染色体のペアを作りそのペアになった染色体における染色体情報の一部を入れ換える処理を言う。また、突然変異とは、所定の確率で染色体における染色体情報の一部の値を変える処理を言う。
【００６９】
ただし、以上の選択、交配および突然変異は所定の確率をもって行われるため、遺伝的アルゴリズム処理部３１４における処理の後には、染色体情報に変化のない染色体および新たな染色体情報を持った染色体が混合した集団となり得る。そして、遺伝的アルゴリズム処理部３１４において選択、交配および突然変異の処理を行った後に、再び適応度算出前処理部３１２および適応度算出部３１３における処理が行われる。
【００７０】
処理終了指示部３１５は、所定の条件に従って、適応度算出前処理部３１２、適応度算出部３１３および遺伝的アルゴリズム処理部３１４で繰り返し行われる処理の終了を指示するものである。所定の条件として、例えば適応度算出前処理部３１２、適応度算出部３１３および遺伝的アルゴリズム処理部３１４で５０世代分の処理を行った後に終了させることが想定されるが、これに限るものではない。
【００７１】
適応度算出部３１３は、処理終了指示部３１５より処理の終了の指示を受けると最後に算出した複数の適応度を準最適解判断部３１６に供給する。準最適解判断部３１６は、適応度算出部３１３より供給された複数の適応度のうち最も高い適応度に対応する染色体を準最適解として判断するものである。
【００７２】
近傍領域準最適解判断部３１７は、準最適解判断部３１６において準最適解と判断された染色体に対応するマッチング領域の周りの所定領域全てについてターゲット画像とテンプレート画像との照合を行い、照合を行う各マッチング領域において、例えば上記数１乃至数３に示した関数を用いて適応度を算出するものである。そして、算出した適応度のうち最も高い適応度を有する染色体を近傍領域準最適解判断部３１７における準最適解と判断する。
【００７３】
準最適解判断部３１６において準最適解と判断された染色体に対応するマッチング領域の周りの所定領域の広さは、例えばマッチング領域の境界から所定ピクセルの範囲というように予め設定された広さとすることが想定される。近傍領域準最適解判断部３１７において準最適解と判断された染色体に対応するマッチング領域の周りの所定領域についてさらにターゲット画像とテンプレート画像の照合を行うのは、遺伝的アルゴリズムを用いてターゲット画像とテンプレート画像との照合をおこなった場合、毎回ターゲット画像とテンプレート画像とが照合する最適な場所を発見できるわけではないためである。
【００７４】
類似画像判断部３１８は、準最適解判断部３１６において判断された最も高い適応度と、近傍領域準最適解判断部３１７において算出された適応度とのうち、高い方の適応度が予め設定された所定の閾値を超えているか否かを判断するものである。類似画像判断部３１８において高い方の適応度が所定の閾値を超えていると判断されると、テンプレート画像に類似する画像がそのターゲット画像に含まれているとされ、検索結果として出力される。
【００７５】
準備値算出部３１９は、画像縮小部３０２において縮小されたテンプレート画像および縮小されたターゲット画像における原点から任意の座標までの画素値を積算した準備値（以下、準備値と呼ぶ。）を算出するものである。この準備値の算出は、縮小されたテンプレート画像および縮小されたターゲット画像の全ての座標において行われる。準備値をｉｉ（Ｘ、Ｙ）、ターゲット画像の（Ｘ´、Ｙ´）における画素値をｉ（Ｘ´、Ｙ´）とすると、準備値ｉｉ（Ｘ、Ｙ）を表す式は数４のように表せる。
【数４】
2007102634.tif 000007
【００７６】
数４は、ターゲット画像の左上を原点とし、左方向をＸ´の正方向および下方向をＹ´の正方向としたＸ´Ｙ´座標空間を考えたときに、０≦Ｘ´≦Ｘ、０≦Ｙ´≦Ｙで表された領域内の各座標における画素値を積算した形になっている。この準備値を計算するために、さらに中間値ｓ（Ｘ、Ｙ）を考えると、準備値ｉｉ（Ｘ、Ｙ）とターゲット画像の（Ｘ´、Ｙ´）における画素値ｉ（Ｘ´、Ｙ´）と中間値ｓ（Ｘ、Ｙ）の関係は数５に示すようになる。なお、ｉｉ（０、０）の計算に必要なｓ（Ｘ、−１）およびｉｉ（−１、Ｙ）の値はそれぞれ０とする。
【数５】
2007102634.tif 000008
【００７７】
上記数４および数５を用いて算出された準備値は、準備値算出部３１９においてターゲット画像の各座標毎に全て算出されて、その結果がターゲット画像準備値テーブル３２０において保持される。また、テンプレート画像についても上記説明したのと同様の考え方で準備値算出部３１９においてテンプレート画像の各座標毎に準備値が算出されて、その結果がテンプレート画像準備値テーブル３２１において保持される。
【００７８】
また、各座標における画素値を２乗したものを積算した準備値ｉｉｉ（Ｘ、Ｙ）も上記と同様の考え方によりターゲット画像およびテンプレート画像の各座標毎に全て算出して、それぞれターゲット画像準備値テーブル３２０およびテンプレート画像準備値テーブル３２１に保持させる。なお、ｉｉｉ（Ｘ、Ｙ）は数６のように表せる。
【数６】
2007102634.tif 000009
【００７９】
上記準備値は、上記説明した数１乃至数３を用いた計算において適応度算出部３１３で利用されるものである。数１乃至数３を計算する際の準備値の利用の仕方については、図４において説明する。
【００８０】
図４は、本発明の実施の形態における準備値を説明するための図である。図４（ａ）は、ターゲット画像２００を示す図である。準備値は、（０、０）および（Ｘ、Ｙ）で特定される領域２０１内のターゲット画像における画素値を積算したものである。（Ｘ、Ｙ）はそれぞれ０≦Ｘ≦Ｘｎ、０≦Ｙ≦Ｙｎの範囲をとり、この範囲における（Ｘ、Ｙ）全てについての準備値が求められる。
【００８１】
この準備値は、例えば画素値を輝度とした場合には各座標が積算される程値が大きくなるため右下方向に行く程画像が明るくなり、例えば図４（ｂ）に示すようなグラデーション画像２０２として表すことができる。
【００８２】
このターゲット画像２００の領域２０３における適応度を算出する場合、図３において説明した数１乃至数３を用いる。領域２０３における適応度を算出する際に、数１を用いた場合における準備値の数１への用い方について以下、図４（ｃ）および図４（ｄ）を用いて説明する。
【００８３】
図４（ｃ）における点Ａを（Ｘ、Ｙ）、ＡＢ間の長さをｗ、ＡＣ間の長さをｈとすると、領域２０３における適応度は数１に示す式を計算することにより求められる。数１の計算において数１の分母のうちターゲット画像に関する式を展開した式を数７に示す。
【数７】
2007102634.tif 000010
【００８４】
数７において項ａ１は、座標（Ｘ、Ｙ）の点Ａと座標（Ｘ＋ｗ、Ｙ＋ｈ）の点Ｄで特定される領域２０３内の画素値の２乗を積算した形になっている。この項ａ１は、ターゲット画像における準備値ｉｉｉ（Ｘ、Ｙ）を用いて計算できる。すなわち、図４（ｄ）に示す準備値を示すグラデーション画像２０２における領域２０３内の値を２乗して積算したものが項ａ１である。したがって、項ａ１は、図３で説明したターゲット画像におけるｉｉｉ（Ｘ、Ｙ）を用いて、ｉｉｉ（Ａ）＋ｉｉｉ（Ｄ）−ｉｉｉ（Ｂ）−ｉｉｉ（Ｃ）で求められる。なお、ｉｉｉ（Ａ）は、点Ａの座標における準備値ｉｉｉ（Ｘ、Ｙ）の値を示すものであり、その他についても同様の用い方をするものとする。
【００８５】
項ａ２は、座標（Ｘ、Ｙ）の点Ａと座標（Ｘ＋ｗ、Ｙ＋ｈ）の点Ｄで特定される領域２０３内の画素値を積算したものと２Ｍtargetとの積になっている。この項ａ２は、ターゲット画像における準備値ｉｉ（Ｘ、Ｙ）を用いて計算できる。項ａ２も項ａ１と同様に考えると、２Ｍtarget｛ｉｉ（Ａ）＋ｉｉ（Ｄ）−ｉｉ（Ｂ）−ｉｉ（Ｃ）｝で求められる。項ａ３は、Ｍtargetｗｈと表せる。以上より数１の分母のうちターゲット画像に関する式は、ターゲット画像におけるｉｉ（Ｘ、Ｙ）およびｉｉｉ（Ｘ、Ｙ）を用いて求めることができる。数１の分母のうちテンプレート画像に関する式も同様の考え方で求めることができる。なお、ｉｉ（Ａ）は、点Ａの座標における準備値ｉｉ（Ｘ、Ｙ）の値を示すものであり、その他についても同様の用い方をするものとする。
【００８６】
次に、数１の計算において数１の分子を展開した式を数８に示す。
【数８】
2007102634.tif 000011
【００８７】
数８において項ｂ１は、準備値を利用して計算できない。項ｂ２は、上記数７と同様に考えると、テンプレート画像における準備値ｉｉ（Ｘ、Ｙ）を用いて、Ｍtarget｛ｉｉ（Ａ）＋ｉｉ（Ｄ）−ｉｉ（Ｂ）−ｉｉ（Ｃ）｝で求められる。また、項ｂ３は、ターゲット画像における準備値ｉｉ（Ｘ、Ｙ）を用いて、Ｍtemplate｛ｉｉ（Ａ）＋ｉｉ（Ｄ）−ｉｉ（Ｂ）−ｉｉ（Ｃ）｝で求められる。また、項ｂ３は、ＭtargetＭtemplateｗｈと表せる。以上より数１の分子は、ターゲット画像およびテンプレート画像におけるｉｉ（Ｘ、Ｙ）およびｉｉｉ（Ｘ、Ｙ）を用いて求めることができる。
【００８８】
なお、以上は数１を例にして準備値の用い方を説明したが、数２および数３についても同様の考え方により準備値を用いて計算できる。準備値を用いて数１乃至数３を計算することによって計算量を低減することができるため、高速な検索処理を実現することができる。
【００８９】
図５は、本発明の実施の形態におけるターゲット画像準備値テーブル３２０を示す図である。ターゲット画像準備値テーブル３２０は、座標３２０１と、準備値ｉｉ（Ｘ、Ｙ）３２０２と、準備値ｉｉｉ（Ｘ、Ｙ）３２０３とを備える。
【００９０】
座標３２０１は、ターゲット画像の全ての座標が含まれ、その座標に対応する準備値ｉｉ（Ｘ、Ｙ）３２０２と準備値ｉｉｉ（Ｘ、Ｙ）３２０３とが保持されている。ｉｉ（Ａ）およびｉｉｉ（Ａ）は、それぞれＡの座標における準備値ｉｉ（Ｘ、Ｙ）、準備値ｉｉｉ（Ｘ、Ｙ）を表しており、その他についても同様の用い方をするものとする。このターゲット画像準備値テーブル３２０を参照して適応度算出部３１３は、各染色体について適応度を算出する。なお、テンプレート画像準備値テーブル３２１についても内容は上記と同様に考えることができる。
【００９１】
図６は、本発明の実施の形態においてテンプレート画像の領域を選択する様子を示す図である。本発明の実施の形態において表示画面６００に一度に表示させることができるターゲット画像の枚数は図６（ａ）に示すように、例えば４枚とする。他のターゲット画像を表示画面６００に表示させたい場合は、「前へ」ボタン６２１または「次へ」ボタン６２２を、例えばスタイラス５０１により押下する。これにより、他のターゲット画像が表示される。なお、本発明の実施の形態においては、操作方式として表示画面を直接押下することによって操作の入力を行うタッチパネル方式を想定しているが、これに限るものではない。
【００９２】
上記操作により所望の画像を表示画面６００に表示させた後に、スタイラス５０１により所望のターゲット画像を押下して、ＯＫボタン６２３を選択する。これにより図６（ｂ）に示すように、その選択されたターゲット画像６１１が表示画面６００に表示される。
【００９３】
表示画面６００に図６（ｂ）に示すターゲット画像６１１が表示されると、次にターゲット画像における領域を選択する。この選択した領域に含まれる画像がテンプレート画像になる。ターゲット画像における領域の選択においては、例えばスタイラス５０２により点６１２を選択した後に、スタイラス５０３により点６１３を選択する。スタイラス５０３により点６１３を選択すると、点６１２および点６１３を結んだ線を対角線とする領域６１４が表示される。
【００９４】
領域６１４が表示された後に、ＯＫボタン６２４を選択すると、テンプレート画像が生成される。一方、領域６１４が表示された後に、違う領域を選択する場合は、戻るボタン６２５を選択して再びターゲット画像６１１における領域を選択する。
【００９５】
図７は、本発明の実施の形態におけるテンプレート画像データ生成のイメージを示す図である。ターゲット画像における領域が選択されると、テンプレート画像生成部３０１においてターゲット画像における選択された領域は切り出され、図７（ａ）に示すテンプレート画像６１５が生成される。
【００９６】
また、テンプレート画像生成部３０１は、テンプレート画像６１５を拡大および縮小した画像であるテンプレート画像６１５ａ乃至６１５ｄも生成する。テンプレート画像６１５ａ乃至６１５ｄは、それぞれテンプレート画像６１５を、例えば１．２１倍、１．１倍、１．０倍、０．９０９倍、０．８２６倍したものが想定される。なお、図７（ａ）においては、テンプレート画像６１５以外のテンプレート画像データは４つしかないが、これに限るものではなくいくつあってもよい。
【００９７】
ここで、１．２１、１．１、１．０、０．９０９、０．８２６の数列は、（１．１）２、（１．１）１、（１．１）０、（１．１）−１、（１．１）−２であり、すなわち、公比が１．１の等比数列である。なお、公比を大きくするとテンプレート画像を用いて画像の検索を行う際に検索漏れを生じる可能性が高くなり、一方、公比を小さくするとテンプレート画像を用いて画像の検索を行う際に計算量が増えるという弊害が生じる。このため、公比は、１．１程度が好ましいが、これに限るものではなく、例えば１．０９や１．２等でも良い。
【００９８】
また、テンプレート画像として、テンプレート画像６１５を拡大および縮小した画像データのみならず、図７（ｂ）に示すように、さらに回転させたテンプレート画像６１６をも生成してもよい。
【００９９】
図８は、本発明の実施の形態における画像縮小部３０２においてターゲット画像およびテンプレート画像を縮小する様子を示す図である。図８（ａ）は、画像縮小部３０２において縮小される前のターゲット画像６１７およびテンプレート画像６１５を示す図である。
【０１００】
ターゲット画像６１７およびテンプレート画像６１５は、テンプレート画像の縦幅および横幅に応じた縮小率ｋに縮小される。縮小率ｋとして、例えば数９に示すような縮小率とすることが想定される。なお、テンプレート画像６１５の横幅をａ、縦幅をｂとする。
【数９】
2007102634.tif 000012
【０１０１】
図８（ｂ）は、画像縮小部３０２においてターゲット画像およびテンプレート画像を縮小した図である。画像縮小部３０２において縮小されると、ターゲット画像の横幅はｃからｋｃになり、ターゲット画像の縦幅はｄからｋｄになる。また、画像縮小部３０２において縮小されると、テンプレート画像の横幅はａからｋａになり、テンプレート画像の縦幅はｂからｋｂになる。
【０１０２】
このようにターゲット画像およびテンプレート画像を縮小することによって、後に行われる検索処理における計算量を減らすことができ、検索処理を高速に行うことを可能とする。また、ターゲット画像およびテンプレート画像を縮小すると、検索において画像細部の本質的ではない差異やノイズが検出され難くなるため、検索精度も向上する。
【０１０３】
図９は、本発明の実施の形態における染色体の染色体情報４００の一例を示す図である。本発明の実施の形態における染色体情報４００においては、個体抽出部３１１において抽出された個体のターゲット画像上における座標として、ターゲット画像とテンプレート画像の照合（マッチング）を行う位置のＸ座標４０１と、ターゲット画像とテンプレート画像の照合（マッチング）を行う位置のＹ座標４０２とを想定し、テンプレート画像の拡大または縮小における所定の倍率として、ターゲット画像と照合（マッチング）されるテンプレート画像の倍率４０３を想定している。
【０１０４】
Ｘ座標４０１およびＹ座標４０２は、それぞれグレイコードに変換した上で染色体情報にコードする。また、倍率４０３は、倍率そのものを染色体情報にコードするのではなく、例えば倍率をインデックス化してグレイコードに変換した上で染色体情報にコードする。
【０１０５】
図１０は、本発明の実施の形態における遺伝的アルゴリズムの選択において使用されるルーレット４１０を示す図である。選択は、図３において説明したように適応度算出部３１３において適応度を算出された染色体を所定数選択する処理である。ルーレット４１０の領域を染色体の数だけ分割する。この分割においては、ルーレット４１０を占める面積が、適応度算出部３１３において算出された適応度ｆ´（Ｘ、Ｙ）に比例するように設定する。
【０１０６】
例えば、個体抽出部３１１において個体がｎ個抽出されて、染色体がｎ個生成されたとする。この場合、ルーレット４１０は、ｎ個の領域に分割される。そして、染色体における適応度が、染色体Ａ、染色体Ｂ、染色体Ｃ、染色体Ｄ、・・・の順に高いとする。この場合、ルーレット４１０を占める面積は、適応度の高いものに大きな面積の領域を与えるため、図１０に示すようになる。
【０１０７】
ここでルーレット４１０を図１０に示す矢印の方向に回す。そして、ルーレット４１０が止まった所において、選択ポイント４１１が指す染色体が選択により残った染色体となる。この処理を例えばｎ回繰り返して、ｎ個の染色体から、ｎ個の染色体を選択する。なお、ルーレット４１０において占める面積の大きい染色体が残る確率が高いため、ルーレット４１０により選択を行った後は、適応度の高い染色体が多くなる可能性が高い。
【０１０８】
図１１は、本発明の実施の形態における遺伝的アルゴリズムの交配の様子を示す図である。交配は、図３において説明したように、例えば上記選択によって選択された染色体のペアを作りそのペアになった染色体における染色体情報の一部を交換する処理である。
【０１０９】
図１１（ａ）は、染色体のペアとして染色体Ａ４２１および染色体Ｂ４２２を示す図である。染色体Ａ４２１および染色体Ｂ４２２における所定の位置を選択する。この所定の位置は、図１１（ａ）において点線で示される。この点線より右側における染色体情報を交換する。この交換により、図１１（ｂ）に示す染色体Ｃ４２３および染色体Ｄ４２４が生成される。
【０１１０】
図１２は、本発明の実施の形態における遺伝的アルゴリズムの突然変異の様子を示す図である。突然変異は、図３において説明したように所定の確率で染色体における染色体情報の一部の値を変える処理である。この所定の確率は、極めて低い確率であり、その確率により選択された染色体情報４３１を有する染色体におけるランダムな位置４３２の染色体情報をビット反転させる。これにより、新たな染色体が生成される。
【０１１１】
以上、図１０乃至図１２において説明した選択、交配および突然変異を繰り返すことによって適応度の高い染色体が多く残る。そして、予め設定した終了条件に達したら、処理を終了させて、そのうち最も適応度の高い染色体に対応するマッチング領域にテンプレート画像と類似する画像が含まれる可能性が高くなる。この最も高い適応度が所定の閾値を超えた場合は、テンプレート画像と類似する画像がそのターゲット画像に含まれるものと推定され、類似する画像として出力される。
【０１１２】
図１３は、本発明の実施の形態における適応度算出前処理部３１２における処理の様子を示す図である。テンプレート画像６４０と類似する領域をターゲット画像より探索する場合、図１３に示す所定の染色体に対応するマッチング領域６３１は明らかに類似する領域とは言えない。適応度算出部３１３において上記のような染色体について適応度の算出を行うことは画像検索の高速化の妨げになる。
【０１１３】
このため、本発明の実施の形態においては、適応度算出部３１３における演算量を低減させるために、マッチング領域６３１のようなマッチング領域については数１乃至数３による適応度の算出を省く必要性がある。本発明の実施の形態においては、図３において説明したように、適応度算出前処理部３１２においてマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値による染色体の適応度の評価、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比による染色体の適応度の評価、および、マッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値による染色体の適応度の評価を行う。以上において適応度の評価が悪いものについては、適応度算出部３１３において数１乃至数３により適応度を算出することなく、類似判断から除外されるために十分に小さい値（ゼロを含む）を適応度として設定する。適応度の評価の具体例を以下説明する。
【０１１４】
画素値をＹＵＶで表した場合、染色体の適応度計算をなるべく省くための、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値に関する条件の一例を数１０に示す。なお、ＭＹtarget、Ｍｕtarget、Ｍｖtargetは、それぞれターゲット画像におけるＹ成分（輝度）、Ｕ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）の平均値である。また、ＭＹtemplate、Ｍｕtemplate、Ｍｖtemplateは、それぞれテンプレート画像におけるＹ成分（輝度）、Ｕ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）の平均値である。
【数１０】
2007102634.tif 000013
【０１１５】
適応度算出前処理部３１２において算出されたマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値が数１０に示す式全ての条件を満たした場合、適応度算出部３１３は類似判断から除外されるために十分に小さい値（ゼロを含む）を適応度として設定する。
【０１１６】
画素値をＹＵＶで表した場合、染色体の適応度計算をなるべく省くための、マッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比に関する条件の一例を数１１に示す。なお、σｕtarget、σｖtargetは、それぞれターゲット画像におけるＵ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）の平均値である。また、σｕtemplate、σｖtemplateは、それぞれテンプレート画像におけるＵ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）の平均値である。
【数１１】
2007102634.tif 000014
【０１１７】
なお、ターゲット画像におけるＹ成分（輝度）の標準偏差σＹtargetは、ターゲット画像におけるＹ成分（輝度）の平均値ＭＹtargetを用いると数１２のように表すことができる。
【数１２】
2007102634.tif 000015
【０１１８】
適応度算出前処理部３１２において算出されたマッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比が数１１に示す式全ての条件を満たした場合、適応度算出部３１３は類似判断から除外されるために十分に小さい値（ゼロを含む）を適応度として設定する。
【０１１９】
画素値をＹＵＶで表した場合、染色体の適応度計算をなるべく省くための、マッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値に関する条件の一例を数１３に示す。なお、Ｃｕtarget、Ｃｖtargetは、それぞれターゲット画像におけるマッチング領域の中央点についてのＵ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）である。また、Ｃｕtemplate、Ｃｖtemplateは、それぞれテンプレート画像におけるマッチング領域の中央点についてのＵ成分（輝度信号と青色成分の差）およびＶ成分（輝度信号と赤色成分の差）である。
【数１３】
2007102634.tif 000016
【０１２０】
適応度算出前処理部３１２において算出されたマッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値が数１３に示す式全ての条件を満たした場合、適応度算出部３１３は類似判断から除外されるために十分に小さい値（ゼロを含む）を適応度として設定する。
【０１２１】
すなわち、数１０、数１１および数１３の何れかにより適応度を評価した結果、評価の悪いものについては、適応度算出部３１３は適応度の算出にｆ（Ｘ、Ｙ）を用いることなく、類似判断から除外されるために十分に小さい値（ゼロを含む）を適応度として設定する。これにより、適応度の算出にｆ（Ｘ、Ｙ）を用いないため、テンプレート画像に類似する画像を含むターゲット画像を高速に検索することが可能となる。
【０１２２】
図１４は、本発明の実施の形態における遺伝的アルゴリズムによって求められた準最適解に対応するマッチング領域の周辺領域を示す図である。図１４においては、テンプレート画像６６０と準最適解とされた染色体に対応するマッチング領域における画像６５２は、位置が少しずれている。マッチング領域を少しずらした画像６５３の方が画像６５２よりもテンプレート画像６６０に類似する画像と評価できる。
【０１２３】
遺伝的アルゴリズムにおいては、ターゲット画像の全領域について詳細に評価するわけではないため、遺伝的アルゴリズムによって求められた準最適解の周辺領域にさらによい準最適解が存在する可能性が高い。このため、本発明の実施の形態においては、準最適解が求められた後に、その準最適解に対応するマッチング領域の周辺領域にマッチング領域をずらした上でさらに適応度を求める。この適応度は、図３で説明した数１乃至数３を用いて近傍領域準最適解判断部３１７において求められる。なお、マッチング領域の周辺領域は、例えばマッチング領域の境界より所定ピクセル離れた領域を周辺領域とする、といった具合に予め定めておく。
【０１２４】
近傍領域準最適解判断部３１７において求められた上記周辺領域における適応度のうち最も高い適応度が、準最適解判断部３１６において準最適解と判断された適応度よりも高い場合は、近傍領域準最適解判断部３１７において求められた上記周辺領域における適応度のうち最も高い適応度が新たな準最適解とされる。この判断は、類似画像判断部３１８において行われ、その準最適解と判断された適応度が、予め定められた所定の閾値を超える場合には、そのターゲット画像にはテンプレート画像に類似する画像が含まれると推定する。
【０１２５】
図１５は、本発明の実施の形態においてテンプレート画像に類似する画像を含むターゲット画像を検索している際の表示画面６００を示す図である。図１５（ａ）は、テンプレート画像に類似する画像を含むターゲット画像を検索している最中の表示画面６００を示す図である。
【０１２６】
テンプレート画像に類似する画像を含むターゲット画像が検索されると、そのターゲット画像６７１は、表示画面６００に表示される。この表示させるターゲット画像６７１は、サムネイルとすることが想定される。また、表示画面６００に表示させるターゲット画像の順番としては、適応度の高い順番が想定される。また、表示画面６００に一度に表示させるターゲット画像の枚数は、例えば２枚として、スクロール６７３を用いてその他の検索されたターゲット画像を表示する。
【０１２７】
さらに、表示画面６００に検索の進行具合を表す検索経過表示６７２を設けることによってユーザーに現在どの程度検索が進行しているかを認識させることができる。また、検索処理を中断させる中断ボタン６７４を設けると、ユーザーが所望するターゲット画像が検索結果として表示されてさらなる検索処理が不要な場合に有用である。
【０１２８】
図１５（ｂ）は、テンプレート画像に類似する画像を含むターゲット画像の検索が終了した後の表示画面６００である。検索が終了すると検索結果として、テンプレート画像に類似する画像を含むターゲット画像６８１が表示画面６００に表示される。表示画面６００に一度に表示させるターゲット画像の枚数は、例えば４枚として、スクロール６８２を用いてその他の検索されたターゲット画像を表示する。
【０１２９】
次に本発明の実施の形態における撮像装置１００の動作について図面を参照して説明する。
【０１３０】
図１６は、本発明の実施の形態におけるテンプレート画像に類似する画像を含むターゲット画像を検索する流れを示す図である。まず、領域選択受付部６０１においてターゲット画像保持部２３１に保持されたターゲット画像のうちの何れか一つの選択およびそのターゲット画像における領域の選択を受け付ける（ステップＳ９１１）。この選択が受け付けられると、検索処理が開始する。
【０１３１】
次に、選択を受け付けたターゲット画像の領域に基づいてテンプレート画像生成部３０１においてテンプレート画像が生成される（ステップＳ９１２）。なお、ステップＳ９１２においては、例えば選択を受け付けられたターゲット画像の領域に対応する画像を拡大または縮小または回転させた画像もテンプレート画像として生成される。
【０１３２】
画像縮小部３０２においてステップＳ９１２で生成されたテンプレート画像がそのテンプレート画像の縦幅および横幅に応じた縮小率に縮小される（ステップＳ９１３）。そして、縮小されたテンプレート画像における準備値が準備値算出部３１９において算出される（ステップＳ９１４）。
【０１３３】
次に、ターゲット画像保持部２３１に未検索のターゲット画像が存在するか否かが判断される（ステップ９１５）。未検索のターゲット画像がなければ処理は終了する。一方、未検索のターゲット画像が存在すると判断されると、画像縮小部３０２において未検索のターゲット画像のうちの所定のターゲット画像が縮小される（ステップＳ９１６）。なお、ステップＳ９１６における縮小における縮小率は、ステップＳ９１３におけるテンプレート画像の縮小率と同じである。そして、縮小されたターゲット画像における準備値が準備値算出部３１９において算出される（ステップＳ９１７）。
【０１３４】
以上の処理が終了すると、ステップＳ９１７において縮小された所定のターゲット画像にテンプレート画像と類似する画像が含まれるか否かを評価するための適応度が算出されて、適応度のうち最も高い適応度が準最適解とされる（ステップＳ９１８）。
【０１３５】
ステップＳ９１８において準最適解とされた適応度が、予め定められた所定の閾値よりも高いか否かが類似画像判断部３１８において判断される（ステップＳ９１９）。ステップＳ９１８において準最適解とされた適応度が、予め定められた所定の閾値よりも高いと判断されると、そのターゲット画像はテンプレート画像に類似する画像を含むとされて類似画像として出力される（ステップＳ９２０）。一方、ステップＳ９１８において準最適解とされた適応度が、予め定められた所定の閾値よりも低いと判断されると、そのターゲット画像はテンプレート画像に類似する画像を含まないとされる。以上の処理を、ステップＳ９１５において、ターゲット画像保持部２３１に未検索のターゲット画像が存在しないと判断されるまで繰り返す。
【０１３６】
図１７は、図１６におけるステップＳ９１８の準最適解算出処理の流れを示す図である。まず、ターゲット画像より個体をランダムに抽出する。この抽出された個体数だけ所定の染色体情報を有する染色体が生成される（ステップＳ９２１）。この染色体情報は、ターゲット画像上における座標およびテンプレート画像の拡大または縮小における所定の倍率に基づいて生成される。
【０１３７】
次に、各染色体の適応度が算出される（ステップＳ９２２）。この適応度の算出は、適応度算出前処理部３１２および適応度算出部３１３において２段階に分けて行われる。
【０１３８】
適応度算出前処理部３１２においては、各染色体に対応するマッチング領域におけるターゲット画像およびテンプレート画像の画素値の平均値の差の絶対値、または各染色体に対応するマッチング領域におけるターゲット画像およびテンプレート画像の画素値の標準偏差を２乗したものの比、または、各染色体に対応するマッチング領域の中央点におけるターゲット画像およびテンプレート画像の画素値の差の絶対値を算出する。適応度算出前処理部３１２は、これらの値を例えば数１０乃至数１３により評価して、類似判断から除外すべきか否かを判断する。
【０１３９】
適応度算出部３１３においては、適応度算出前処理部３１２において類似判断から除外すべきと判断されなかった染色体について、例えば数１乃至数３を用いて適応度を算出する。適応度算出前処理部３１２において予め類似判断から除外すべき染色体を判断することによって適応度算出部３１３における計算量を低減できるため、高速な検索処理を実現することができる。
【０１４０】
次に、ステップＳ９２２において適応度が算出された染色体より所定数の染色体を選択する（ステップＳ９２３）。本発明の実施の形態において染色体の選択は、例えば図１０において説明したルーレットを用いて行うことを想定しているが、これに限るものではない。
【０１４１】
次に、ステップＳ９２３において選択された所定数の染色体に対して交配を行う（ステップＳ９２４）。本発明の実施の形態における交配は、例えば図１１において説明した方法で交配を行うことを想定しているが、これに限るものではない。
【０１４２】
次に、染色体に対して突然変異を行う（ステップＳ９２５）。本発明の実施の形態における突然変異は、例えば図１２において説明した方法で行うことを想定しているが、これに限るものではない。
【０１４３】
以上のステップＳ９２２乃至ステップＳ９２５の処理は、例えば５０世代繰り返した後に終了させる等の処理を終了させるための条件が予め設定されている。この処理を終了させる条件を満たしたか否かが処理終了指示部３１５においてステップＳ９２５の後に判断される（ステップＳ９２６）。
【０１４４】
ステップＳ９２２乃至ステップＳ９２５の処理を終了させると判断されると、最後の処理において算出された適応度のうち最も高いものが準最適解判断部３１６において準最適解と判断される（ステップＳ９２７）。次に、ステップＳ９２７において判断された準最適解に対応するマッチング領域の周辺領域において適応度の算出が近傍領域準最適解判断部３１７において行われる（ステップＳ９２８）。
【０１４５】
そして、準最適解判断部３１６において判断された準最適解に対応する適応度よりもよい適応度が近傍領域準最適解判断部３１７において算出されたか否かが判断される（ステップＳ９２９）。準最適解判断部３１６において判断された準最適解に対応する適応度よりもよい適応度が近傍領域準最適解判断部３１７において算出された場合は、近傍領域準最適解判断部３１７において算出された適応度のうち最も高い適応度が準最適解とされて、その結果が上書きされる（ステップＳ９３０）。
【０１４６】
このように、本発明の実施の形態によれば、画像縮小部３０２においてテンプレート画像の横幅および縦幅に応じた縮小率でテンプレート画像およびターゲット画像が縮小されるため、テンプレート画像およびターゲット画像を照合する面積が低減され、演算量も低減される。これにより、高速な検索処理が可能となる。また、ターゲット画像およびテンプレート画像を縮小すると、検索において画像細部の本質的ではない差異やノイズが検出され難くなるため、検索精度も向上する。
【０１４７】
また、適応度算出部３１３における染色体の適応度算出前に、適応度算出前処理部３１２において演算量の少ない方法で適応度を決定することによって、適応度算出部３１３における演算量を低減させることができる。また、適応度算出部３１３における相互相関関数の計算において準備値を用いることによって、相互相関関数の計算量を低減させることができる。以上の２つの効果によって、高速な検索処理が可能となる。
【０１４８】
また、遺伝的アルゴリズムにおいて準最適解を算出した後に、その準最適解に対応するマッチング領域の周辺についてもさらに近傍領域準最適解判断部３１７において適応度を算出することによって、さらに良い値の適応度を算出でき得る。これにより、画像の検索精度を向上させることができる。
【０１４９】
なお、本発明の実施の形態では、撮像装置を例に説明したが、その他画像についての処理を行うことができる電子機器において本発明を適用することは可能である
【０１５０】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、以下に示すように特許請求の範囲における発明特定事項とそれぞれ対応関係を有するが、これに限定されるものではなく本発明の要旨を逸脱しない範囲において種々の変形を施すことができる。
【０１５１】
すなわち、請求項１において、ターゲット画像保持手段は、例えばターゲット画像保持部２３１に対応する。また、領域選択受付手段は、例えば領域選択受付部６０１に対応する。また、テンプレート画像生成手段は、例えばテンプレート画像生成部３０１に対応する。また、画像縮小手段は、例えば画像縮小部３０２に対応する。また、類似画像検索手段は、例えば類似画像検索部３１０に対応する。
【０１５２】
また、請求項４において、個体抽出手段は、例えば個体抽出部３１１に対応する。また、適応度算出手段は、例えば適応度算出部３１３に対応する。また、遺伝的アルゴリズム処理手段は、例えば遺伝的アルゴリズム処理部３１４に対応する。また、処理終了指示手段は、例えば処理終了指示部３１５に対応する。また、準最適解判断手段は、例えば準最適解判断部３１６に対応する。また、類似画像判断手段は、例えば類似画像判断部３１８に対応する。
【０１５３】
また、請求項６乃至８において、適応度算出前処理手段は、例えば適応度算出前処理部３１２に対応する。
【０１５４】
また、請求項１１において、準備値算出手段は、例えば準備値算出部３１９に対応する。また、テンプレート画像準備値テーブルは、例えばテンプレート画像準備値テーブル３２１に対応する。また、ターゲット画像準備値テーブルは、例えばターゲット画像準備値テーブル３２０に対応する。
【０１５５】
また、請求項１５において、ターゲット画像保持手段は、例えばターゲット画像保持部２３１に対応する。また、領域選択受付手段は、例えば領域選択受付部６０１に対応する。また、テンプレート画像生成手段は、例えばテンプレート画像生成部３０１に対応する。また、個体抽出手段は、例えば個体抽出部３１１に対応する。また、適応度算出手段は、例えば適応度算出部３１３に対応する。また、遺伝的アルゴリズム処理手段は、例えば遺伝的アルゴリズム処理部３１４に対応する。また、処理終了指示手段は、例えば処理終了指示部３１５に対応する。また、準最適解判断手段は、例えば準最適解判断部３１６に対応する。また、近傍領域準最適解判断手段は、例えば近傍領域準最適解判断部３１７に対応する。また、類似画像判断手段は、例えば類似画像判断部３１８に対応する。
【０１５６】
また、請求項１６および１７において、ターゲット画像保持手段は、例えばターゲット画像保持部２３１に対応する。また、領域選択受付手順は、例えばステップＳ９１１に対応する。また、テンプレート画像生成手順は、例えばステップＳ９１２に対応する。また、画像縮小手順は、例えばステップＳ９１３およびステップＳ９１６に対応する。また、類似画像検索手順は、例えばステップＳ９１５、ステップＳ９１８およびステップＳ９１９に対応する。
【０１５７】
なお、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。
【図面の簡単な説明】
【０１５８】
【図１】本発明の実施の形態における撮像装置１００の一例である撮像装置１００ａおよび１００ｂの外観図である。
【図２】本発明の実施の形態における撮像装置１００の構成を示す図である。
【図３】本発明の実施の形態における画像検索機能の構成の一例を示す図である。
【図４】本発明の実施の形態における準備値を説明するための図である。
【図５】本発明の実施の形態におけるターゲット画像準備値テーブル３２０を示す図である。
【図６】本発明の実施の形態においてテンプレート画像の領域を選択する様子を示す図である。
【図７】本発明の実施の形態におけるテンプレート画像データ生成のイメージを示す図である。
【図８】本発明の実施の形態における画像縮小部３０２においてターゲット画像およびテンプレート画像を縮小する様子を示す図である。
【図９】本発明の実施の形態における染色体の染色体情報４００の一例を示す図である。
【図１０】本発明の実施の形態における遺伝的アルゴリズムの選択において使用されるルーレット４１０を示す図である。
【図１１】本発明の実施の形態における遺伝的アルゴリズムの交配の様子を示す図である。
【図１２】本発明の実施の形態における遺伝的アルゴリズムの突然変異の様子を示す図である。
【図１３】本発明の実施の形態における適応度算出前処理部３１２における処理の様子を示す図である。
【図１４】本発明の実施の形態における遺伝的アルゴリズムによって求められた準最適解に対応するマッチング領域の周辺領域を示す図である。
【図１５】本発明の実施の形態においてテンプレート画像に類似する画像を含むターゲット画像を検索している際の表示画面６００を示す図である。
【図１６】本発明の実施の形態におけるテンプレート画像に類似する画像を含むターゲット画像を検索する流れを示す図である。
【図１７】図１６におけるステップＳ９１８の準最適解算出処理の流れを示す図である。
【符号の説明】
【０１５９】
１０  撮像部
１１  撮像素子部
１２  撮像制御部
１３  画像処理部
２０  記録再生処理部
２１  画像符号化／復号部
２２  記録制御部
２３  ＳＤＲＡＭ
３０  制御部
３１  システム制御部
３２  入力制御部
３３  表示制御部
３４  出力画像処理部
３５  外部機器制御部
３６  ネットワーク制御部
４０  バス
５０  キー入力部
６０  タッチパネル部
６１  表示部
６２  タッチパネル入力部
７０  記憶装置
８０  外部機器
９０  ネットワーク網
１００  撮像装置
２３１  ターゲット画像保持部
３０１  テンプレート画像生成部
３０２  画像縮小部
３１０  類似画像検索部
３１１  個体抽出部
３１２  適応度算出前処理部
３１３  適応度算出部
３１４  遺伝的アルゴリズム処理部
３１５  処理終了指示部
３１６  準最適解判断部
３１７  近傍領域準最適解判断部
３１８  類似画像判断部
３１９  準備値算出部
３２０  ターゲット画像準備値テーブル
３２１  テンプレート画像準備値テーブル
６０１  領域選択受付部
【図１】
2007102634.tif 000018
【図２】
2007102634.tif 000019
【図３】
2007102634.tif 000020
【図５】
2007102634.tif 000021
【図６】
2007102634.tif 000022
【図７】
2007102634.tif 000023
【図８】
2007102634.tif 000024
【図９】
2007102634.tif 000025
【図１０】
2007102634.tif 000026
【図１１】
2007102634.tif 000027
【図１２】
2007102634.tif 000028
【図１３】
2007102634.tif 000029
【図１４】
2007102634.tif 000030
【図１５】
2007102634.tif 000031
【図１６】
2007102634.tif 000032
【図１７】
2007102634.tif 000033
【図４】
2007102634.tif 000034