JP2004192307A

JP2004192307A - 類似画像抽出装置、類似画像抽出方法および類似画像抽出プログラム

Info

Publication number: JP2004192307A
Application number: JP2002358985A
Authority: JP
Inventors: Makoto Ouchi; 真大内
Original assignee: Seiko Epson Corp
Current assignee: Seiko Epson Corp
Priority date: 2002-12-11
Filing date: 2002-12-11
Publication date: 2004-07-08
Also published as: CN1711558A; WO2004053796A1; EP1574991A1; US20060115148A1; EP1574991A4

Abstract

【課題】従来の画像検索においては検索精度が充分ではなかった。また、高速に画像を検索可能な手法が望まれていた。
【解決手段】元画像データと検索対象画像データとを取得し、元画像の複数の位置に照合画素を設定するとともに当該照合画素の階調値を取得し、検索対象画像上に元画像と同じ大きさの領域を設定し、当該領域を逐次変更しながら、当該領域において上記照合画素と同じ位置に相当する比較画素の階調値を取得し、上記照合画素の階調値と比較画素の階調値との類似度を示す照合値を算出する工程を行い、上記照合値が示す類似度が高い領域について当該領域内の略全画素の階調値と上記元画像の略全画素の階調値との類似度を算出して、類似度の高い領域を抽出する。
【選択図】図４

Description

【０００１】
【発明の属する技術分野】
本発明は、類似画像抽出装置、類似画像抽出方法および類似画像抽出プログラムに関する。
【０００２】
【従来の技術】
近年、デジタルカメラ等による撮像画像あるいはその一部などを検索する画像検索やパノラマ写真画像を連結する際の接続位置検索等を実施する当たり、検索対象の画像内で元画像に類似する部位を検索する種々の手法が提案されている。（例えば、特許文献１，特許文献２）。
【特許文献１】
特開平４−３２９４９０号公報
【特許文献２】
特開昭６３−１４２９９１号公報
【０００３】
【発明が解決しようとする課題】
上述した従来の検索においては検索精度が充分ではなかった。また、高速に画像を検索可能な手法が望まれていた。例えば、上記特許文献１における手法では、ヒストグラムの類似度を計算して対象枠内の画像と類似度枠内の画像とを照合しており、正確に画像検索をすることができなかった。また、上記特許文献２における手法では相互相関係数ｆ（τ）を縦横画素について求めることによって画像と画像をつなぎ合わせており、計算対象が全画素になるため処理速度が遅かった。
本発明は、上記課題にかんがみてなされたもので、画像検索の精度が高く、また、高速に処理を実行可能な類似画像抽出装置、類似画像抽出方法および類似画像抽出プログラムの提供を目的とする。
【０００４】
【課題を解決するための手段および発明の効果】
上記目的を達成するため、本発明では元画像内の一部の画素を利用して検索対象画像の中から類似部位の候補を探し、これらの候補と元画像とを画素毎に比較することによって元画像と類似する部位を検索対象画像から抽出する。このために、本発明は画像データ取得手段と照合画素階調値取得手段と比較画素階調値取得手段と照合値算出手段と走査手段とを備えている。これらの手段によって、元画像データと検索対象画像データとを取得し、元画像と同じ大きさの領域で検索対象画像を走査しながら、照合画素の階調値と比較画素の階調値との類似度を示す照合値を算出する。
【０００５】
ここで、照合画素は元画像内の複数の位置に配置されるが、元画像の画素数より少ない画素数である。従って、元画像と同じ大きさの領域毎に検索対象画像を走査することにより、検索対象画像内の一部の画素と元画像の一部の画素とを照合するのみで検索対象画像内で元画像内に類似する部位を候補として探し出すことができる。このため、検索対象画像の全画素について元画像と類似するか否かを検討する処理と比較して、非常に高速に処理を行うことができる。
【０００６】
さらに本発明では、上述のようにして探し出した候補の中から、類似領域抽出手段によって元画像に類似する領域を抽出する。すなわち、これらの候補は上記類似度を示す照合値によって元画像との類似度が高いことが示されているので、これらのいずれかが検索対象であると考えられる。そこで、上述のようにして候補を限定した上で候補内の全画素と元画像の全画素との類似度を算出する。この結果、最も類似するとされた領域が元画像に最も類似している可能性が高く、この領域を抽出することにより、検索対象画像内で元画像と類似する画像を検索することができる。
【０００７】
本発明においては、元画像の全画素と上述の処理によって候補となった複数の領域内の全画素とで類似度を計算しているが、この候補を決定するためには上述のように一部の画素のみが使用されているため高速に候補を決定することができるし、この候補は検索対象画像の一部であるため、元画像の全画素と比較して類似度を算出する対象も検索対象画像の一部である。従って、検索対象画像の全画素について元画像と類似するか否かを検討する処理と比較して、非常に高速に処理を行うことができる。
【０００８】
また、上述の候補は上記照合画素と比較画素との類似度を示す照合値に基づいて抽出される。この照合値に基づく判別によれば、上記照合画素と比較画素とが類似するか否かを判別することができるが、元画像の全画素と候補内の全画素とが非常に似通っているか否かを決定することはできない。しかし、照合値によって上述の候補を複数個検出するように構成すれば、照合値のみによって最終的に元画像と類似度の高い領域を抽出するのではなく、複数個の候補から最も類似する領域を抽出することができる。
【０００９】
検索対象画像内に元画像と一致する部位あるいは非常に類似している部位が存在するのであれば、これらの候補の中に非常に高い確率で検索対象の部位が含まれる。従って、少ない照合画素数で候補を挙げた上で元画像内の全画素と比較する構成であっても非常に高精度に検索を実行することができる。尚、本発明によれば、検索対象画像から元画像に類似する領域を抽出することができるので、むろん、検索対象画像から元画像と同一の領域を抽出することも可能である。
【００１０】
ここで、上記照合画素は上記元画像の一部であって、当該照合画素と検索対象画像内の比較画素とを照合することによって、比較された部位が元画像に類似しているか否かを判定することができればよく、種々の位置，数の照合画素を設定することができる。その構成例として、元画像の縦およびまたは横の一定画素数毎に照合画素を設定する構成等を採用可能である。
【００１１】
より具体的には、元画像中の縦横５〜１０画素毎に照合画素を配置する構成や元画像の縦または横画素数の１／８〜１／１６に相当する画素毎に照合画素を配置する構成等を採用可能である。このような構成によれば、元画像の中から位置的な偏りを生じさせることなく照合画素を設定することができる。むろん、照合画素のピッチとしては上述の具体例以外にも種々のピッチを採用可能であり、元画像や検索対象画像の大きさ，必要な検索精度，検索速度に応じて調整可能である。
【００１２】
さらに、照合値はその値によって照合画素の階調値と比較画素の階調値との類似度を示していればよく、例えば、同じ位置に相当する照合画素と比較画素との階調値の差分を加え合わせた値等を採用可能である。この差分は照合画素の階調値と比較画素の階調値との差異が大きいほど大きくなる。従って、この差分が小さければ類似度が高いと言える。類似領域抽出手段において照合値から類似度が高い領域を候補として抽出する際には、差分が小さいものの上位いくつかを候補としたり、差分が所定の閾値以下となるものを候補とするなど、種々の構成を採用可能である。いずれにしても、照合画素と比較画素との階調値の加減演算のみで候補を抽出することができ、高速に候補を抽出することができる。
【００１３】
類似領域抽出手段において照合値から類似度が高い領域を候補として抽出するためには種々の構成を採用可能である。例えば、照合値を算出した領域とその照合値自体を記憶媒体に保存しておき、検索対象画像の走査を終了した後に記憶媒体を参照して類似度が高い領域を抽出する構成を採用可能である。走査を実施する上で好適な他の構成として、予め決められた領域数を限度として記憶媒体に類似度の高い照合値を与える領域を示すデータを逐次記憶していってもよい。
【００１４】
この場合さらに、照合値算出手段において照合値を算出したときに、既に記憶した領域の照合値を参照し、算出された照合値がより高い類似度を示しているときに記憶媒体の記憶内容を更新する。この構成によれば、上記走査を終了した時点で記憶媒体に記憶されている上記領域を示すデータは類似度が高い上位いくつかの領域に関するデータとなる。従って、類似領域抽出手段では、この記憶媒体のデータを参照するのみで類似度が高い上位の領域について処理を行うことができ、走査終了と同時に上記領域内の略全画素の階調値と上記元画像の略全画素の階調値との類似度を算出する処理に移行することができる。尚、この類似度は、元画像の全画素と上述の各候補の全画素とが類似している度合を示す情報であればよく、上述の照合値と同様に元画像の全画素と上述の各候補の全画素とについて階調値の差分を加え合わせた値等によって構成することができる。
【００１５】
以上のように、類似領域抽出手段での処理によって検索対象画像の中から元画像に類似した部位を検索することができるが、上述のように走査手段においては、検索対象画像上で上記領域を逐次変更して照合値の算出を行わせており、走査の過程において重複しないように各領域を選択した場合には、各領域を微調整した方がより高い類似度になる場合もある。そこで、類似領域抽出手段において、上記類似度の高い領域を抽出した後に当該領域の近隣にて上記元画像と同じ大きさの領域を設定するとともに当該設定した領域と上記元画像との類似度を算出してもよい。かかる構成においては、この類似度の中から最も高い類似度を有する領域を元画像の類似画像とすることにより、検索対象画像の中から元画像と最も合致する部位を類似画像として抽出することができる。
【００１６】
ところで、上述した類似画像抽出装置は、単独で実施される場合もあるし、ある機器に組み込まれた状態で他の方法とともに実施されることもあるなど、発明の思想としては各種の態様を含むものであって、適宜、変更可能である。また、上述した元画像の一部の画素から検索部位の候補を限定した後に、元画素の全画素について類似度を算出することによって類似画像を検索する手法は、所定の手順に従って処理を進めていくうえで、その根底にはその手順に発明が存在するということは当然である。したがって、本発明は方法としても適用可能であり、請求項６にかかる発明においても、基本的には同様の作用となる。本発明を実施しようとする際に、類似画像抽出装置にて所定のプログラムを実行させる場合もある。本発明はこのプログラムとしても適用可能であり、請求項７にかかる発明においても、基本的には同様の作用となる。
【００１７】
むろん、請求項２〜請求項５に記載された構成を上記方法やプログラムに対応させることも可能であることは言うまでもない。また、いかなる記憶媒体もプログラムを提供するために使用可能である。例えば、磁気記録媒体や光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。また、一部がソフトウェアであって、一部がハードウェアで実現される場合においても本発明の思想において全く異なるものではなく、一部を記録媒体上に記録しておいて必要に応じて適宜読み込む形態のものも含まれる。さらに、一次複製品、二次複製品などの複製段階については全く問う余地なく同等である。
【００１８】
【発明の実施の形態】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）システムハードウェア構成：
（２）類似画像抽出プログラムの構成および処理：
（３）類似画像抽出処理の例：
（４）他の実施形態：
【００１９】
（１）システムハードウェア構成：
図１は、本発明の一実施形態にかかる類似画像抽出プログラムを実行するコンピュータシステムをブロック図により示している。同図において、コンピュータシステム１０は、画像入力デバイスとして、スキャナ１１ａとデジタルスチルカメラ１１ｂとビデオカメラ１１ｃとを備えており、コンピュータ本体１２に接続されている。それぞれの入力デバイスは、画像をドットマトリクス状の画素で表現した画像データを生成してコンピュータ本体１２に出力可能となっており、ここで、同画像データは、ＲＧＢの三原色においてそれぞれ２５６階調表示することにより、約１６７０万色を表現可能となっている。
【００２０】
コンピュータ本体１２には、外部補助記憶装置としてのフレキシブルディスクドライブ１３ａと、ハードディスク１３ｂと、ＣＤ−ＲＯＭドライブ１３ｃとが接続されている。また、ハードディスク１３ｂには、システム関連の主要プログラムが記録されており、フレキシブルディスク１３ａ１やＣＤ−ＲＯＭ１３ｃ１などから適宜必要なプログラムや画像データなどを読み込み可能となっている。
【００２１】
さらに、コンピュータ本体１２を外部のネットワークなどに接続するための通信デバイスとしてモデム１４ａが接続されており、外部のネットワークに同公衆通信回線等を介して接続し、ソフトウェアや画像データなどをダウンロードして導入可能となっている。この例ではモデム１４ａにて電話回線を介して外部にアクセスするようにしているが、ＬＡＮアダプタを介してネットワークに対してアクセスする構成とすることも可能であるし、ルーターを介して外部回線にアクセスしてもよい。この他、コンピュータ本体１２の操作用にキーボード１５ａやマウス１５ｂも接続されている。本発明における元画像データと検索対象画像データとはそれぞれ、上記入力デバイスや外部補助記憶装置、通信デバイス等からコンピュータ本体１２に入力される。
【００２２】
また、画像出力デバイスとして、ディスプレイ１７ａとカラープリンタ１７ｂとを備えている。ディスプレイ１７ａについては水平方向に１０２４画素と垂直方向に７６８画素の表示エリアを備えており、各画素毎に上述した１６７０万色の表示が可能となっている。むろん、この解像度は一例に過ぎず、６４０×４８０画素であったり、８００×６００画素であるなど、適宜変更可能である。
【００２３】
一方、このような画像入力デバイスを使用して画像を入力しつつ、画像出力デバイスに表示あるいは出力するため、コンピュータ本体１２内では所定のプログラムが実行されることになる。そのうち、基本プログラムとして稼働しているのはオペレーティングシステム（ＯＳ）１２ａであり、このオペレーティングシステム１２ａにはディスプレイ１７ａでの表示を行わせるディスプレイドライバ（ＤＳＰＤＲＶ）１２ｂとカラープリンタ１７ｂに印刷出力を行わせるプリンタドライバ（ＰＲＴＤＲＶ）１２ｃが組み込まれている。これらのドライバ１２ｂ，１２ｃの類はディスプレイ１７ａやカラープリンタ１７ｂの機種に依存しており、それぞれの機種に応じてオペレーティングシステム１２ａに対して追加変更可能である。また、機種に依存して標準処理以上の付加機能を実現することもできるようになっている。すなわち、オペレーティングシステム１２ａという標準システム上で共通化した処理体系を維持しつつ、許容される範囲内での各種の追加的処理を実現できる。
【００２４】
むろん、このようなプログラムを実行する前提として、コンピュータ本体１２内にはＣＰＵ１２ｅとＲＯＭ１２ｆとＲＡＭ１２ｇとＩ／Ｏ１２ｈなどが備えられており、演算処理を実行するＣＰＵ１２ｅがＲＯＭ１２ｆを一時的なワークエリアや設定記憶領域として使用したりプログラム領域として使用しながら、ＲＡＭ１２ｇに書き込まれた基本プログラムを適宜実行し、Ｉ／Ｏ１２ｈを介して接続されている外部機器及び内部機器などを制御している。
【００２５】
この基本プログラムとしてのオペレーティングシステム１２ａ上でアプリケーション（ＡＰＬ）１２ｄが実行される。アプリケーション１２ｄの処理内容は様々であり、操作デバイスとしてのキーボード１５ａやマウス１５ｂの操作を監視し、操作された場合には各種の外部機器を適切に制御して対応する演算処理などを実行し、さらには、処理結果をディスプレイ１７ａに表示したり、カラープリンタ１７ｂに出力したりすることになる。
【００２６】
ここで上述したカラープリンタ１７ｂには、プリンタドライバ１２ｃを介してアプリケーション１２ｄの処理結果が印刷データとして出力され、同カラープリンタ１７ｂは色インクを用いて印刷用紙上にドットを付すことにより、対応する文字や画像を印刷する。本発明にかかる類似画像抽出プログラムは、上記アプリケーション１２ｄとして提供することもできるし、アプリケーション１２ｄの機能の一部を実現するプログラムとして提供することもできる。パノラマ写真の合成プログラムや画像検索プログラムに本発明にかかる類似画像抽出プログラムを組み込むと特に好ましい。
【００２７】
（２）類似画像抽出プログラムの構成および処理：
図２は類似画像抽出プログラムの機能ブロック図および処理において使用するデータを示しており、図３は類似画像抽出プログラムでの処理フローを示している。以下、これらの図にしたがってプログラムの機能および処理を説明する。類似画像抽出プログラム２０は、図２に示すように画像データ取得モジュール２１と照合画素階調値取得モジュール２２と走査部２３と類似領域抽出モジュール２４とを備えている。走査部２３はさらに、比較画素階調値取得モジュール２３ａと照合値算出モジュール２３ｂとを備えている。
【００２８】
図では元画像データと検索対象画像データとがハードディスク１３ｂに保存されている例について説明しているが、むろん、他の媒体に保存されていてもよいし、デジタルスチルカメラ１１ｂ等の機器から取得されるデータであってもよいし、モデム１４ａ等を介して取得されるデータであってもよい。類似画像抽出プログラム２０の処理が開始されると、画像データ取得モジュール２１はステップＳ１００においてハードディスク１３ｂから元画像データを読み出してＲＡＭ１２ｇに一時記憶させる（元画像データ１２ｇ１）。ここでは、画像データの全色成分について取得して以下の処理を行ってもよいし、特定の色成分のみであってもよいし、ＲＧＢ以外の成分（例えば輝度成分）を取得してもよい。
【００２９】
ステップＳ１０５では、照合画素階調値取得モジュール２２が元画像データ１２ｇ１に対して照合画素を設定し、当該照合画素の階調値（照合画素階調値１２ｇ３）を取得する。図４は後に詳述する本実施形態での処理例であり、このステップＳ１０５では同図左側の元画像データ１２ｇ１に黒丸で示すように、元画像内のごく一部の画素を照合画素としている。照合画素は一定の画素ピッチ毎に設定されており、元画像の縦横画素数の１／ｍ（ｍは自然数）毎に照合画素を設定したり、ｌ画素毎（ｌは自然数）に照合画素を設定するなど種々の手法で位置を決定することができる。
【００３０】
ステップＳ１１０では画像データ取得モジュール２１がハードディスク１３ｂから検索対象画像データを読み出してＲＡＭ１２ｇに一時記憶させる（検索対象画像データ１２ｇ２）。ステップＳ１１５〜Ｓ１４０では、走査部２３の制御によるループ処理が行われる。すなわち、ステップＳ１１５では比較画素階調値取得モジュール２３ａが検索対象画像上に上記元画像と同じ大きさの領域（以下、比較領域という）を設定する。さらに、ステップＳ１２０では比較画素階調値取得モジュール２３ａが当該比較領域内で上記照合画素と同じ位置に相当する比較画素を設定し、その階調値（比較画素階調値１２ｇ４）を取得する。
【００３１】
ステップＳ１２５では、照合値算出モジュール２３ｂが照合画素階調値１２ｇ３と比較画素階調値１２ｇ４とを参照して照合値を算出する。ここで照合値は、同じ位置に相当する照合画素と比較画素との階調値の差分を加え合わせた値であり、値が小さいほど高い類似度を示す。さらに、照合値算出モジュール２３ｂはステップＳ１３０，Ｓ１３５で照合値が示す類似度の上位３位までをＲＡＭ１２ｇに保存する処理を行う。具体的には、ＲＡＭ１２ｇには照合値およびその照合値を与える領域の位置を示す照合値１２ｇ５を保存する記憶容量であって、３箇所分の記憶が可能な記憶容量が確保されている。
【００３２】
そして、上記算出した照合値がＲＡＭ１２ｇ内に既に記憶されている照合値より小さい（高い類似度）か否かを判別（ステップＳ１３０）し、既存の照合値より小さいと判別されたときには、上記算出した照合値でＲＡＭ１２ｇ内の照合値１２ｇ５を更新（ステップＳ１３５）する。すなわち、既存の照合値１２ｇ５の中から最大の照合値を削除し、算出した照合値をＲＡＭ１２ｇに記憶させる。ステップＳ１３０にて既存の照合値より小さいと判別されないときにはＲＡＭ１２ｇの更新をスキップする。
【００３３】
ステップＳ１４０では、上記比較領域について照合値を算出する処理が検索対象画像内の全領域について終了したか否かを判別し、終了したと判別されるまで上記ステップＳ１１５以降の処理を繰り返す。本実施形態の繰り返し段階においてステップＳ１１５では、検索対象画像内で重複をしないように新たな比較領域を設定するが、むろん、一部重複させながら比較領域を変更して処理を進めてもよい。
【００３４】
ＲＡＭ１２ｇには上述のように、３箇所分の照合値を記憶可能な記憶容量が確保されているので、ステップＳ１４０にて検索対象画像内の全領域について照合値を算出する処理が終了したと判別された後には、ＲＡＭ１２ｇの照合値１２ｇ５は各比較領域の中で類似度の上位３位までが保存されていることになる。尚、繰り返し処理の最初の３回については、ＲＡＭ１２ｇ内に既存の照合値が３個以下しか保存されていないので、最初の３箇所は判別せずに記憶する処理を行えばよい。むろん、初期値として照合値の最大値を３個記憶させておいてもよい。
【００３５】
ステップＳ１４５では、上記照合値１２ｇ５が示す比較領域を候補とし、類似領域抽出モジュール２４がこれら各候補と元画像の類似度を算出する。また、これら各候補の位置を上下左右に移動させた位置に上記元画像と同じ大きさの周辺領域を設定し、この周辺領域の画像と元画像の類似度を算出する。ここで、類似度は、元画像と比較領域（あるいは周辺領域）とのそれぞれに属する総ての画素について同じ位置に相当する画素の階調値の差分を加え合わせた値である。従って、本実施形態における類似度は上述の照合値とでは、対象とする画素数が異なるものの考え方としては同じであり、類似度が小さいほど元画像と比較領域（あるいは周辺領域）の画像が類似していることになる。ステップＳ１５０では、当該ステップＳ１４５にて算出した類似度の中で最小の値（最も類似している）となった比較領域あるいは周辺領域を類似画像とし、当該類似画像の位置を示すデータをＲＡＭ１２ｇに保存する（類似画像データ１２ｇ６）。
【００３６】
（３）類似画像抽出処理の例：
次に、以上の構成および処理による動作例を説明する。図４，図５は山を被写体とした写真の検索対象画像データ１２ｇ２から元画像データ１２ｇ１が示す画像に類似した部位を検索する様子を説明する説明図である。照合画素階調値取得モジュール２２は、図４の左側に示すように元画像データ１２ｇ１内に複数の照合画素Ｘ_０を設定し、各照合画素Ｘ_０の階調値を取得する。走査部２３においては、図４の右側に示すように検索対象画像データ１２ｇ２に対して比較領域Ｃを設定し、検索対象画像データ１２ｇ２内で比較領域Ｃを逐次変更する処理を行う。
【００３７】
このとき、この比較領域Ｃを左から右に移動させ、比較領域Ｃが右端に達したときには比較領域Ｃを下に移動させるとともに再び左から右に移動させて検索対象画像データ１２ｇ２の全体について走査を行う。さらに、この走査の過程において比較画素階調値取得モジュール２３ａは比較領域内で照合画素Ｘ_０の位置に対応した比較画素Ｘ_ｃを設定し、各比較画素Ｘ_ｃの階調値を取得する。照合値算出モジュール２３ｂは照合画素と比較画素との差分を加え合わせて照合値を算出する。
【００３８】
尚、図４に示す照合値の式Σ（Ｘ_０（ｉＴ，ｊＴ）−Ｘ_ｃ（ｉＴ，ｊＴ））において、ｉは横方向の画素位置を特定する番号であり、ｊは縦方向の画素位置を特定する番号であり、双方とも自然数である。また、各（）内の原点は元画像や比較領域の左端の座標である。従って、これらｉ，ｊの組み合わせによって元画像内の照合画素や比較領域内の比較画素が指定される。Ｔは照合画素や比較画素のピッチを示しており、元画像内の所定ピッチで画素が取得され、照合値が計算されることを示している。
【００３９】
すなわち、照合画素Ｘ_０や比較画素Ｘ_ｃは元画像や比較領域のごく一部の画素であり、これらごく一部の画素から照合値を算出することによって、元画像の全画素分の照合値を算出する場合と比較して非常に高速に処理を行うことができる。照合値算出モジュール２３ｂは、類似度が高い順に上位３位までの照合値をＲＡＭ１２ｇに保存する。
【００４０】
類似領域抽出モジュール２４はＲＡＭ１２ｇに保存されている照合値１２ｇ５を参照し、当該照合値１２ｇ５が示す比較領域の位置を３箇所特定する。そして、これら比較領域の上下左右に当該比較領域と同じ大きさの領域（周辺領域）を設定して元画像の全画素と比較領域（あるいは周辺画素）の全画素についての類似度を算出する。すなわち、図５に示すように、照合値１２ｇ５に基づいて候補として比較領域Ｃ１，Ｃｎ等が抽出されている状況において、破線に示すように比較領域の位置を変動させて類似度を算出する。
【００４１】
類似領域抽出モジュール２４においては、類似度を図５に示す式Σ（Ｘ_０（ｉ，ｊ）−Ｘ_ｃｎ（ｉ，ｊ））に従って算出している。ここで、ｉ，ｊは自然数であって元画像，比較領域，周辺領域の座標を示している。ここでも原点は画像の左端の座標である。尚、このｉ，ｊは上記図４に示すものより値域が大きく、ｉは元画像，比較領域，周辺領域の横画素数を値域とし、ｊは元画像，比較領域，周辺領域の縦画素数を値域としている。また、ｎは自然数であって、比較領域およびその周辺領域を指定する番号である。
【００４２】
以上の式で算出した類似度によれば、比較領域と周辺領域との中から元画像に最も類似する領域を抽出することができる。比較領域は、検索対象画像データ１２ｇ２の中から図４に示す照合値によって類似画像の候補として抽出された領域であるので、図５に示す類似度に基づいて最も類似する部位として抽出された領域は検索対象画像データ１２ｇ２の総ての中で元画像に最も類似する部位である確率が非常に高い。従って、以上の処理によって類似画像を決定することができる。上述のように、本発明ではごく一部の画素に基づいて比較領域の候補を決定しているが、類似領域抽出モジュール２４において最終的には全画素に対する比較を行っているし、さらに、比較対象を周辺領域にまで拡大しているので、非常に正確に類似画像を検索することができる。
【００４３】
（４）他の実施形態：
上記類似画像抽出処理の構成および処理は一例であって、他にも種々の構成を採用可能である。例えば、類似領域抽出モジュール２４において類似度を算出する対象を周辺領域間で広げることなく、上記候補としての比較領域のみに対して類似度を算出し、最も類似度の高い領域を抽出する処理を行ってもよい。この場合、抽出された領域が検索対象画像内で元画像に最も類似しているとは必ずしも言えないが、最も類似した画像に近い部位を非常に高速に検索することができる。
【００４４】
また、上記実施形態において走査部２３は、比較領域の設定に際して重複を避けつつ検索対象画像の総てが走査対象になるようにしていたが、むろん、かかる構成が必須というわけではない。例えば、照合値算出モジュール２３ｂによって算出された照合値が非常に大きかった場合（類似度が非常に小さかった場合）は、次の比較領域を設定するに際して走査ピッチを大きく（次の比較領域をより遠くに設定）し、照合値が大きくなったら走査ピッチを小さくする構成を採用可能である。また、照合値が非常に大きかった場合に照合画素数を少なくする構成としてもよい。これらの構成によれば、冗長な処理を効果的に削減し、より高速に候補となる比較領域を抽出することができる。
【００４５】
さらに、本発明は種々の場面に適用することができる。例えば、上述のようにパノラマ写真の合成に際して連結する写真同士で一致する領域を特定したい場合、一方の画像から元画像を切り出し、他方の画像に対して本発明にかかる類似画像抽出プログラムを実施すると、両画像で一致する部位を容易に特定することができる。従って、両者を連結する位置を容易に特定することが可能になる。この場合、比較領域の候補が複数抽出されたとしても、類似画像とされた部位は一方の画像の左側に存在し、他方の画像の右側に存在すべきであるという条件を課するなどして、より高速に処理を完了することができる。
【図面の簡単な説明】
【図１】コンピュータシステムのブロック図である。
【図２】類似画像抽出プログラムの機能ブロック図である。
【図３】類似画像抽出プログラムでの処理フローチャートである。
【図４】本実施形態での処理例を説明する説明図である。
【図５】本実施形態での処理例を説明する説明図である。
【符号の説明】
１０…コンピュータシステム、１２ｇ…ＲＡＭ、１２ｇ１…元画像データ、１２ｇ２…検索対象画像データ、１２ｇ３…照合画素階調値、１２ｇ４…比較画素階調値、１２ｇ５…照合値、１２ｇ６…類似画像データ、２０…類似画像抽出プログラム、２１…画像データ取得モジュール、２２…照合画素階調値取得モジュール、２３…走査部、２３ａ…比較画素階調値取得モジュール、２３ｂ…照合値算出モジュール、２４…類似領域抽出モジュール

Claims

元画像をドットマトリクス状の画素で表現した元画像データと当該元画像に類似した画像の検索対象となる検索対象画像をドットマトリクス状の画素で表現した検索対象画像データとを取得する画像データ取得手段と、
上記元画像の複数の位置に照合画素を設定するとともに当該照合画素の階調値を取得する照合画素階調値取得手段と、
上記検索対象画像上に上記元画像と同じ大きさの領域を設定するとともに当該領域において上記照合画素と同じ位置に相当する比較画素の階調値を取得する比較画素階調値取得手段と、
上記照合画素の階調値と比較画素の階調値との類似度を示す照合値を算出する照合値算出手段と、
上記検索対象画像上で上記領域を逐次変更して上記比較画素階調値の取得と照合値の算出とを行う走査手段と、
上記照合値が示す類似度が高い領域について当該領域内の略全画素の階調値と上記元画像の略全画素の階調値との類似度を算出して、類似度の高い領域を抽出する類似領域抽出手段とを具備することを特徴とする類似画像抽出装置。
上記照合画素階調値取得手段では、上記元画像の縦およびまたは横の一定画素数毎に照合画素を設定することを特徴とする上記請求項１に記載の類似画像抽出装置。
上記照合値は、上記照合画素の階調値と同じ位置に相当する比較画素の階調値との差分を加え合わせた値であることを特徴とする上記請求項１または請求項２のいずれかに記載の類似画像抽出装置。
予め決められた領域数を限度として高い類似度の照合値を与える領域を示すデータを記憶する記憶媒体を備え、上記照合値算出手段は上記走査の過程で算出した照合値が既に記憶した領域の照合値より高い類似度を示しているときに当該記憶媒体の記憶内容を更新することを特徴とする上記請求項１〜請求項３のいずれかに記載の類似画像抽出装置。
上記類似領域抽出手段は、上記類似度の高い領域を抽出した後に当該領域の近隣にて上記元画像と同じ大きさの領域を設定するとともに当該設定した領域と上記元画像との類似度を算出し、最も高い類似度を有する領域を元画像の類似画像とすることを特徴とする上記請求項１〜請求項４のいずれかに記載の類似画像抽出装置。
元画像をドットマトリクス状の画素で表現した元画像データと当該元画像に類似した画像の検索対象となる検索対象画像をドットマトリクス状の画素で表現した検索対象画像データとを取得する画像データ取得工程と、
上記元画像の複数の位置に照合画素を設定するとともに当該照合画素の階調値を取得する照合画素階調値取得工程と、
上記検索対象画像上に上記元画像と同じ大きさの領域を設定し、当該領域を逐次変更しながら、当該領域において上記照合画素と同じ位置に相当する比較画素の階調値を取得し、上記照合画素の階調値と比較画素の階調値との類似度を示す照合値を算出する工程を行い、
上記照合値が示す類似度が高い領域について当該領域内の略全画素の階調値と上記元画像の略全画素の階調値との類似度を算出して、類似度の高い領域を抽出することを特徴とする類似画像抽出方法。
所定の記憶媒体に元画像をドットマトリクス状の画素で表現した元画像データと当該元画像に類似した画像の検索対象となる検索対象画像をドットマトリクス状の画素で表現した検索対象画像データとを一時記憶するとともに検索対象画像から元画像に類似した画像を検索する類似画像抽出プログラムであって、
上記元画像の複数の位置に照合画素を設定するとともに当該照合画素の階調値を取得する照合画素階調値取得機能と、
上記検索対象画像上に上記元画像と同じ大きさの領域を設定するとともに当該領域において上記照合画素と同じ位置に相当する比較画素の階調値を取得する比較画素階調値取得機能と、
上記照合画素の階調値と比較画素の階調値との類似度を示す照合値を算出する照合値算出機能と、
上記検索対象画像上で上記領域を逐次変更して上記比較画素階調値の取得と照合値の算出とを行う走査機能と、
上記照合値が示す類似度が高い領域について当該領域内の略全画素の階調値と上記元画像の略全画素の階調値との類似度を算出して、類似度の高い領域を抽出する類似領域抽出機能とをコンピュータに実現させることを特徴とする類似画像抽出プログラム。