(57)【要約】【課題】  エッジの特徴が反映されるヒストグラムの生成を可能とすると共に、当該ヒストグラムを利用した画像の類似性判定を可能とする。【解決手段】  画像内のエッジを検出し、画像の部分領域においてエッジにより構成される線分を検出し、検出した線分につき、部分領域における所定の方向成分ごとの本数又は長さをカウントし、ヒストグラムを作成する。生成したヒストグラムの比較により画像の類似度を判定する。【選択図】図２
2006127159.tif 000002
【特許請求の範囲】
【請求項１】
画像内のエッジを検出するエッジ検出手段と、
前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出手段と、
前記線分検出手段で検出された線分につき、前記部分領域における所定の方向成分ごとの本数をカウントし、ヒストグラムを作成するヒストグラム生成手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記ヒストグラム生成手段は、カウントされた前記本数を、前記部分領域における前記所定の方向成分ごとの線分の最大本数により正規化する正規化手段を備え、前記正規化手段の正規化結果により前記ヒストグラムを生成することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
画像内のエッジを検出するエッジ検出手段と、
前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出手段と、
前記線分検出手段で検出された線分につき、前記部分領域における所定の方向成分ごとの長さを合計し、ヒストグラムを作成するヒストグラム生成手段と
を備えることを特徴とする画像処理装置。
【請求項４】
前記ヒストグラム生成手段は、前記長さの合計を、前記部分領域における前記所定の方向成分ごとの長さの合計の最大値により正規化する第１の正規化手段を備え、前記第１の正規化手段の正規化結果により前記ヒストグラムを生成することを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記ヒストグラム生成手段は更に、
前記所定方向成分における長さの最大値を前記長さの合計の最大値により正規化する第２の正規化手段と、前記第１の正規化手段の正規化結果を、前記第２の正規化手段の正規化結果により量子化する量子化手段とを備え、前記量子化手段の量子化結果により前記ヒストグラムを生成することを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記線分検出手段は、前記所定の部分領域における注目方向において該注目方向と同一方向を有するエッジの数を利用して前記線分を検出することを特徴とする請求項１乃至５のいずれかに記載の画像処理装置。
【請求項７】
前記線分検出手段は、
前記所定の部分領域における注目方向において該注目方向と同一方向を有するエッジの数を利用して前記線分を検出し、
前記注目方向と同一方向を有するエッジに連続するエッジであって、前記注目方向と交差する方向のエッジを利用して前記線分としての折れ線を検出することを特徴とする請求項３乃至５のいずれかに記載の画像処理装置。
【請求項８】
前記部分領域を設定する部分領域設定手段を更に備え、
前記部分領域設定手段は、隣接する部分領域同士が重複領域を有するように部分領域を設定することを特徴とする請求項１乃至７のいずれかに記載の画像処理装置。
【請求項９】
前記ヒストグラム生成手段により生成されたヒストグラムを、前記ヒストグラムに対応する画像と関連づけて格納する格納手段と、
画像の指定を受け付ける指定受付手段と、
指定を受け付けた前記画像について前記ヒストグラム生成手段により生成されたヒストグラムと、前記格納手段に格納されたヒストグラムとを比較し、前記対応する画像のうち前記指定を受け付けた画像に類似する画像を決定する類似画像決定手段と
を更に備えることを特徴とする請求項１乃至８のいずれかに記載の画像処理装置。
【請求項１０】
前記ヒストグラム生成手段により生成されたヒストグラムを、前記ヒストグラムに対応する画像と関連づけて格納する格納手段と、
画像の指定を受け付ける指定受付手段と、
指定を受け付けた前記画像について前記ヒストグラム生成手段により生成されたヒストグラムと、前記格納手段に格納されたヒストグラムとを比較し、前記対応する画像のうち前記指定を受け付けた画像に類似する画像を決定する類似画像決定手段と、
検索時の曖昧さに関する情報の指定を受け付ける指定受付手段と、
前記指定受付手段により指定を受け付けた曖昧さに応じて、前記第２の正規化手段と前記量子化手段とによる演算結果を利用するか否かを決定する決定手段と
を更に備えることを特徴とする請求項５に記載の画像処理装置。
【請求項１１】
画像内のエッジを検出するエッジ検出工程と、
前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出工程と、
前記線分検出工程において検出された線分につき、前記部分領域における所定の方向成分ごとの本数をカウントし、ヒストグラムを作成するヒストグラム生成工程と
を備えることを特徴とする画像処理方法。
【請求項１２】
前記ヒストグラム生成工程は、カウントされた前記本数を、前記部分領域における前記所定の方向成分ごとの線分の最大本数により正規化する正規化工程を備え、前記正規化工程の正規化結果により前記ヒストグラムが生成されることを特徴とする請求項１１に記載の画像処理方法。
【請求項１３】
画像内のエッジを検出するエッジ検出工程と、
前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出工程と、
前記線分検出工程において検出された線分につき、前記部分領域における所定の方向成分ごとの長さを合計し、ヒストグラムを作成するヒストグラム生成工程と
を備えることを特徴とする画像処理方法。
【請求項１４】
前記ヒストグラム生成工程は、前記長さの合計を、前記部分領域における前記所定の方向成分ごとの長さの合計の最大値により正規化する第１の正規化工程を備え、前記第１の正規化工程における正規化結果により前記ヒストグラムが生成されることを特徴とする請求項１３に記載の画像処理方法。
【請求項１５】
前記ヒストグラム生成工程は更に、
前記所定方向成分における長さの最大値を前記長さの合計の最大値により正規化する第２の正規化工程と、前記第１の正規化工程における正規化結果を、前記第２の正規化工程における正規化結果により量子化する量子化工程とを備え、前記量子化工程における量子化結果により前記ヒストグラムを生成することを特徴とする請求項１４に記載の画像処理方法。
【請求項１６】
前記線分検出工程では、前記所定の部分領域における注目方向において該注目方向と同一方向を有するエッジの数を利用して線分が検出されることを特徴とする請求項１１乃至１５のいずれかに記載の画像処理方法。
【請求項１７】
前記線分検出工程では、
前記所定の部分領域における注目方向において該注目方向と同一方向を有するエッジの数を利用して前記線分が検出され、
前記注目方向と同一方向を有するエッジに連続するエッジであって、前記注目方向と交差する方向のエッジを利用して前記線分としての折れ線が検出されることを特徴とする請求項１３乃至１５のいずれかに記載の画像処理方法。
【請求項１８】
前記部分領域を設定する部分領域設定工程を更に備え、
前記部分領域設定工程では、隣接する部分領域同士が重複領域を有するように部分領域が設定されることを特徴とする請求項１１乃至１７のいずれかに記載の画像処理方法。
【請求項１９】
前記ヒストグラム生成工程において生成されたヒストグラムを、前記ヒストグラムに対応する画像と関連づけて格納部に格納する格納工程と、
画像の指定を受け付ける指定受付工程と、
指定を受け付けた前記画像について前記ヒストグラム生成工程において生成されたヒストグラムと、前記格納部に格納されたヒストグラムとを比較し、前記対応する画像のうち前記指定を受け付けた画像に類似する画像を決定する類似画像決定工程と
を更に備えることを特徴とする請求項１１乃至１８のいずれかに記載の画像処理方法。
【請求項２０】
前記ヒストグラム生成工程において生成されたヒストグラムを、前記ヒストグラムに対応する画像と関連づけて格納部に格納する格納工程と、
画像の指定を受け付ける指定受付工程と、
指定を受け付けた前記画像について前記ヒストグラム生成工程において生成されたヒストグラムと、前記格納部に格納されたヒストグラムとを比較し、前記対応する画像のうち前記指定を受け付けた画像に類似する画像を決定する類似画像決定工程と
検索時の曖昧さに関する情報の指定を受け付ける指定受付工程と、
前記指定受付工程において指定を受け付けた曖昧さに応じて、前記第２の正規化工程と前記量子化工程とにおける演算結果を利用するか否かを決定する決定工程と
を更に備えることを特徴とする請求項１５に記載の画像処理方法。
【請求項２１】
請求項１１乃至請求項２０のいずれかに記載の画像処理方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項２２】
請求項２０に記載のコンピュータプログラムを格納したコンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法、コンピュータプログラム及び記憶媒体に関する。
【背景技術】
【０００２】
従来より、画像データベースから画像を検索する際に、画像そのものから、類似した画像を検索したり、予め標準的な画像との類似性を判定することにより、入力された画像がどのような画像であるかを認識する方法が提案されている。また、動画像中の場面の切り替わり(カット点)を検出することを可能とするために、画像の類似性を判定する方法が提案されている。このような画像の類似性判定の方法としては、画像を解析して特徴量を抽出し、特徴量同士の距離を求める方法が提案されている。特徴量としては、色、テクスチャ、エッジなど様々なものが提案されている。
【０００３】
エッジを用いたものとしては、その多くは文字認識方法として提案されており、例えば、画像中の各画素ごとにエッジ(グラディエントベクトル)の方向を求め、いくつかの方向成分に量子化し、画像を部分領域としてのブロックに分割し、各ブロックに含まれる各方向成分のヒストグラム(以降、エッジヒストグラムと呼ぶ)を特徴量とする方法が提案されている（特許文献１を参照。）。
【０００４】
このようなヒストグラムによる画像の類似性判定を行う場合を図１を例として説明する。図１は１ブロック内の各画素に対応するエッジの方向を示している。ここで方向成分としては、図６に示したように0度、45度、90度、135度の4方向とし、向きは考慮しないものとする。 (a)は0度方向のエッジがまばらに存在しており、(b)は0度方向のエッジが直線をなしている。エッジが直線をなしているときは、画像が自然画であれば画像中の対象物などの輪郭に相当している。
【０００５】
このような輪郭の線分である場合は、人の目につきやすいため、違いが認識されやすい。よって、(a)と(b)は人にとっては識別しやすいものになっている。類似性を判定する上で、このように人間にとって識別しやすい特徴を捉えた特徴量を作成することは重要なポイントである。しかしながらヒストグラムに基づく判定方法では、(a),(b)のエッジヒストグラムは、図１の下側に示したように、それぞれ0度方向のエッジが6個存在するので、同じものになってしまい、区別がつかなくなってしまう。
【特許文献１】特許第３１５０７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このように、ヒストグラムを特徴量として画像の類似性を判定した場合には、エッジの特徴が判定結果に反映されないために、精度が低くなってしまう。
【０００７】
本発明はこのような課題に鑑みてなされたものであり、エッジの特徴が反映されるヒストグラムの生成を可能とすると共に、当該ヒストグラムを利用した画像の類似性判定を可能とすることを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を個別に又はまとめて解決するための本発明は、画像内のエッジを検出するエッジ検出手段と、前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出手段と、前記線分検出手段で検出された線分につき、前記部分領域における所定の方向成分ごとの本数をカウントし、ヒストグラムを作成するヒストグラム生成手段とを備える。
【０００９】
また、本発明は、画像内のエッジを検出するエッジ検出手段と、前記画像の部分領域において前記エッジにより構成される線分を検出する線分検出手段と、前記線分検出手段で検出された線分につき、前記部分領域における所定の方向成分ごとの長さを合計し、ヒストグラムを作成するヒストグラム生成手段とを備える。
【００１０】
更に、本発明は、前記ヒストグラム生成手段により生成されたヒストグラムを、前記ヒストグラムに対応する画像と関連づけて格納する格納手段と、画像の指定を受け付ける指定受付手段と、指定を受け付けた前記画像について前記ヒストグラム生成手段により生成されたヒストグラムと、前記格納手段に格納されたヒストグラムとを比較し、前記対応する画像のうち前記指定を受け付けた画像に類似する画像を決定する類似画像決定手段とを更に備える。
【発明の効果】
【００１１】
本発明によれば、エッジの特徴が反映されるヒストグラムの生成が可能となると共に、当該ヒストグラムを利用した画像の類似性判定が可能となる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施形態について図面を参照して詳細に説明する。
【００１３】
図２は、本実施形態に対応する本発明の画像処理装置の構成の一例を示すブロック図である。図２において、２００は画像処理装置全体を示す。２０１はＣＰＵであり、画像処理装置２００における各種制御を実行する。２０２はＲＯＭであり、画像処理装置２００の起動時に実行されるブートプログラムや各種データを格納する。２０３はＲＡＭであり、ＣＰＵ２０１が処理するための制御プログラムを格納するとともに、ＣＰＵ２０１が各種制御を実行する際の作業領域を提供する。２０４はキーボード、２０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１４】
２０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、光ディスク、磁気ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカード等で構成される。２０７は表示器であり、ディスプレイなどで構成され、結果等をユーザに対して表示する。２０８はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。２０９はIEEE1394、USBなどのインターフェースであり、２１０のスキャナや２１１のデジタルカメラなどの機器と通信を行う。上記各構成は内部バス２１２により接続されている。
【００１５】
なお、上記の構成において外部記憶装置２０６、スキャナ２１０、デジタルカメラ２１１はネットワーク上に配置されたもので代用してもよい。
【００１６】
図３は、本実施形態に対応する画像処理装置２００の機能構成を示すブロック図である。図３において、３０１は画像入力部であり、スキャナ２１０、デジタルカメラ２１１などの機器で取得した画像をインターフェース２０９を介して、或いは、インターネット上やＬＡＮ上に存在する画像を、ネットワーク(インターネット、ＬＡＮ)からネットワークインターフェース２０８を介して入力するものである。３０２は入力された画像に対して前処理を行う前処理部である。３０３は、前処理後の画像に対してエッジを検出するエッジ検出部である。
【００１７】
３０４は、エッジからラインヒストグラムを作成するラインヒストグラム作成部３０４である。３０５は画像データベースであり、入力された画像とラインヒストグラムを関連付けて記憶・管理するものである。３０６は検索時に、画像データベース３０５中のラインヒストグラムと、検索元として入力された画像についてラインヒストグラム生成部３０４において生成されたラインヒストグラムとの距離を算出する画像間距離算出部である。３０７はユーザに対して検索結果の画像の表示を行う表示部３０７である。
【００１８】
［登録処理］
まず、画像処理装置２００への画像の登録処理について、図４のフローチャートを用いて説明する。
【００１９】
まず、ステップＳ４０１において、画像入力部３０１により登録対象の画像の入力を行う。
【００２０】
次に、ステップＳ４０２において前処理部３０２において、入力画像がカラーかグレースケールかの判定を行ない、カラーならばステップＳ４０３でグレースケールに変換される。この変換は、カラー画像データのそれぞれの画素のR(赤)、G(緑)、B(青)の画素値からグレースケールの信号(Y)へ次式で変換できる。
【００２１】
Ｙ＝0.29900＊Ｒ＋0.58700＊Ｇ＋0.11400＊Ｂ                ‥‥式１
次に、ステップＳ４０４において前処理部３０２では、コントラストを強調するために、濃淡ヒストグラムの平坦化を行なう。この平坦化処理は、それぞれの濃度に対応する画素数が一定になるように割り当て直していく処理である。
【００２２】
次に、ステップＳ４０５においてエッジ検出部３０３では、エッジの検出を行って各画素に対応するエッジの強度と方向を得る。エッジの検出方法としては、各画素ごとに、周囲の画素を含めた範囲に対して、微分フィルタを用いて演算を行う方法が挙げられる。フィルタとしては、Prewittフィルタ、Sobelフィルタ、Robinsonフィルタ、Kirishフィルタなどがある。ここでは、Prewittフィルタ(図７)を用いて演算する例を示す。
【００２３】
なお、本実施形態では図６に示すように４つの方向成分に量子化し、向きは考慮しないものとするので、例えば、180度のフィルタで検出されたものは、0度方向として扱う。まず、注目する画素とその周りの８画素それぞれに対して、Prewittフィルタの値を係数として乗じ、総和を求めることによって、方向成分ごとのエッジ強度を求める。この中で最もエッジ強度が大きい方向成分を、注目画素のエッジ方向とする。ただし、最大のエッジ強度が所定の閾値よりも小さい場合は、エッジなしと判定する。
【００２４】
次に、ステップＳ４０６においてラインヒストグラム作成部３０４では、ラインヒストグラムを作成する。処理の詳細は後述する。
【００２５】
次に、ステップＳ４０７においてラインヒストグラム作成部３０４では、作成したラインヒストグラムをインデックスとして画像と関連付けて画像データベース３０５に記憶する。図８は、インデックスの例である。画像ＩＤは、登録される画像に与えられた識別子としてのＩＤである。ラインヒストグラムは、対応する画像のラインヒストグラムである。画像ファイルへのパスは、登録された画像ファイルへのパス情報であり、ここを参照することで、画像本体を読み出すことができる。
【００２６】
尚、画像ファイルのファイル形式は、例えば、ＢＩＴＭＡＰ形式とするが、これに限定されるものではなく、色情報を保存しておくことが可能なファイル形式（例えば、ＧＩＦ、ＪＰＥＧ）であればどのようなものでも良い。
【００２７】
[カラー／グレースケール判定処理]
次に、図４のステップＳ４０２におけるカラー／グレースケール判定処理の詳細について説明する。デジタルカメラ２１１から画像を取得した場合などでは、画像のデータフォーマットを解析し、そのヘッダ情報を参照することで判定できる。
【００２８】
一方、スキャナ２１０から画像を取得した場合などでは、スキャン条件をカラーとしていても、読み取る対象はグレースケールである場合がある。このときは、データフォーマット上はカラー画像であるのに、その中はグレースケール画像となる。このような場合には、画像の色に関する解析を利用する方法がある。
【００２９】
この解析は、画像に占める色情報の割合を解析するものであり、画像に占める色情報の割合が予め定められた閾値以上である場合に色情報が十分であると判定し、閾値未満である場合に色情報が不十分であると判定する、というものである。
【００３０】
図１８は、本実施形態における色情報の割合を判定する処理の一例に対応するフローチャートである。ステップＳ１８１０で、画像を構成する全画素の色の平均色を算出する。ステップＳ１８２０で、平均色を輝度成分と色差成分に変換する。ステップＳ１８３０で、輝度成分値に対する色差成分値の割合Ｒを算出する。ここで、色を輝度成分と色差成分に分離する分離方法については、公知の方法を用いる。
【００３１】
例えば、ＹＣｂＣｒ色空間を用いると、２４ビットＲＧＢ値との関連は、
Ｙ  ＝0.29900＊Ｒ＋0.58700＊Ｇ＋0.11400＊Ｂ
Ｃｂ＝-0.16874＊Ｒ−0.33126＊Ｇ＋0.50000＊Ｂ＋128
Ｃｒ＝0.50000＊Ｒ−0.41869＊Ｇ＋（-0.08131）＊Ｂ＋128‥‥式２
と表現される。
【００３２】
この式２に従って平均色から算出した輝度成分及び色差成分を、それぞれＹave、Ｃｂave及びＣｒaveとすると、割合Ｒは以下のように求めることができる。
【００３３】
割合Ｒ＝sqrt（Ｃｂave＊Ｃｂave＋Ｃｒave＊Ｃｒave）／Ｙave‥‥式３
そして、ステップＳ１８４０で、この割合Ｒが所定の閾値以上であるか否かを判定する。閾値以上である場合（ステップＳ１８４０でＹＥＳ）、ステップＳ１８５０に進み、画像の色情報が十分であると判定する（即ち、カラー画像であると判定する）。一方、閾値未満である場合（ステップＳ１８４０でＮＯ）、ステップＳ１８６０に進み、画像の色情報が不十分であると判定する（即ち、グレースケール画像であると判定する）。
【００３４】
[ラインヒストグラム作成処理]
次に、図４のステップＳ４０６におけるラインヒストグラム作成処理の詳細について説明する。ラインヒストグラム作成処理の方法には、２つの方法がある。
【００３５】
第１の方法は、画像を部分領域としてのブロックに分割し、そのブロックに存在する方向成分ごとの線分の数をビンとすることでヒストグラムを表現するものである。また、第２の方法は、画像を部分領域としてのブロックに分割し、そのブロックに存在する方向成分ごとの線分の長さをビンとすることでヒストグラムを表現するものである。この２つの方法により生成されるヒストグラムを比較すると、第１の方法で生成されるヒストグラム（以下、「第１ヒストグラム」という。）の方が第２の方法により生成されるヒストグラム（以下、「第２ヒストグラム」という。）に比べて、より曖昧な検索が可能となるのが特徴である。よって、２種類のヒストグラムを用途に応じて使い分けることが好ましい。
【００３６】
図１５はステップＳ４０６のラインヒストグラム作成処理のうち、上記第１の方法を実行した場合に対応するフローチャートである。
【００３７】
まず、ステップＳ１５０１において、ステップＳ４０５によって抽出されたエッジ画像を所定のブロックに分割する。このブロック分割の手法は特に限定されるものではないが、本実施形態では１枚の画像を４×４、８×８など縦横でブロック数が同数になるように分割する場合について説明する。この場合、元々の画像のアスペクト比の影響により各ブロックを構成する画素数は縦横で必ずしも一致しない。また、画像に対するブロックの大きさも特に限定されるものではない。但し、ブロックが大きいほど粗く特徴量を抽出することになるので、より曖昧な検索が可能になる。
【００３８】
次に、ブロック毎にステップＳ１５０２からステップＳ１５０６までの処理を行う。
【００３９】
まず、ステップＳ１５０２において、ある方向成分に着目してブロック中の線分の検出を行う。図９は、0度方向に着目して線分を検出する例を示した図である。図中の各升目は１画素を示している。0度方向のときは、行ごとに0度方向のエッジがどれだけ含まれているかを計数する。９０１の行のように全て0度方向のエッジであれば、当然に線分であるとみなす。また、９０２のように途中でエッジが検出されない画素がいくつか存在する場合であっても線分とみなすことができる場合がある。これは自然画、特にスキャナ２１０で入力された場合、輪郭線がかすれたりすることがあることに対応するためのものである。
【００４０】
また、９０３のように他の方向のものが混じっていても、注目する方向と45度以内の方向(0度方向に対しては、45度と135度)であれば許容するものとする。これは、エッジ検出において方向成分が量子化されているため、例えば、22.5度方向近辺のエッジは0度方向として判定されることも、45度方向として判定されることもあるためである。
【００４１】
以上を踏まえて、例えば、次式、
((注目方向と同一方向のエッジ数)＋(注目方向と45度以内のエッジ数)／2)／(１行の画素数)ｘ100＞＝80(％)‥‥式４
を満たすものを線分とみなすようにすればよい。なお、(注目方向と45度以内のエッジ数)は、同一方向とみなせる可能性があるが、確定的ではないので式４では１／２倍として評価したが、これに限られるものではない。また、80％以上としたのも、1行の画素数の大半を占めていればよいという意味で、値はこれに限られるものではない。
【００４２】
45度方向、90度方向、135度方向も同様であり、90度方向ならば、列ごとにチェックし、45度方向ならば、図１０の矢印の単位にチェックする。22.5度方向などのように、各方向の中間付近の線分は、近い方向成分のうち、特定の方向の線分として扱う。例えば22.5度方向ならば図１１の斜線部分の単位にチェックし、付近の0度と45度のうち左側の、45度方向の線分として扱うようにする。
【００４３】
どの方向成分として扱うかは、特に上記のパターンに限定されるものではなく、例えば斜め方向の45度か135度の近い方として扱うようにしてもよいし、近い方向の両方であるとして扱ってもよい。チェックするタイミングとしては、４５度方向とみなすのならば、４５度方向をチェックする時に併せてチェックを行うようにすればよい。
【００４４】
ところで、上記のように線分を検出すると、以下のような場合に問題が発生する。図１２のＢ１２０１、Ｂ１２０２はブロックであり、Ｌ１２０１、Ｌ１２０２は同じ長さの線分である。この場合、Ｌ１２０１は線分として検出されるが、Ｌ１２０２はブロックＢ１２０１ではブロック幅の80％に満たないために検出されず、ブロックＢ１２０２においても同様の理由で検出されない。
【００４５】
また、45度(または135度)方向の場合は、対角線上の画素数が式４の1行の画素数に相当するが、もともとブロック内に45度(または135度)方向の線分をひくと、対角線上の画素数の80％未満となる線分も出てくるので、式４を使うと全ての線分を検出できなくなる。
【００４６】
このような場合、画像の中の物体の位置がずれているような画像同士では距離が大きくなる。例えば、２つの画像間で画像内の物体位置が移動しているような場合、１枚目の画像では物体の輪郭線が丁度ブロック内に収まるが、２枚目の画像では物体の輪郭線が移動して２つのブロックにまたがってしまう場合が考えられる。この場合、１枚目では物体の輪郭線が検出されるが、２枚目では物体の輪郭線が検出されなくなってしまうので、特徴量の距離は大きくなってしまう。
【００４７】
これに対処すべく、画像中の物体の位置ずれに対する曖昧性をもたせるためには、Ｌ１２０２のような線分もどちらかのブロックで検出できるようにする必要がある。そこで、これに対応するために、検出の範囲をブロックを注目している方向にブロック同士が重複領域を有するようにずらした形に広げるようにする。
【００４８】
例えば、0度方向であれば、図１３のように実線のブロックに対しては、点線のようにずらして、実線と点線の両方を含めた範囲で検出を行うようにする。同様に45度方向であれば、図１４のようになる。(もちろん、ずらす向きはどちらでも構わない。)  このように検出の範囲を広げた上で、上記条件で線分を検出するようにすれば、Ｌ１２０２のような線分も、検出できるようになる。
【００４９】
次に、ステップステップＳ１５０２で、注目している方向成分の単位中に線分が検出された場合は、ステップＳ１５０３において、線分の本数をインクリメントする。そして、ステップＳ１５０４において、注目している方向の線分を注目しているブロックに対して全て検出したかをチェックし、検出し終えていなければ、ステップＳ１５０２、Ｓ１５０３を繰り返す。検出し終えていれば次にステップＳ１５０５において、ブロックにおける方向毎の線分の最大数を１として、方向毎の総本数の正規化を行う。
【００５０】
正規化を行うのは、本実施形態のように縦横を同数のブロックに分割すると、画像のアスペクト比によって、ブロックの縦横のサイズ（画素数）が変わり、総本数の最大値が変化してしまうためである。例えば、0度方向であれば、ブロック中の行数の半分が線分の最大数となる。第１のラインヒストグラムでは、注目するブロックの注目する方向成分の正規化された総線分数が、ヒストグラムのひとつのビンになる。即ち、ステップＳ１５０２からステップＳ１５０５までの処理でひとつのビンを算出することができる。
【００５１】
次に、ステップＳ１５０６において、全方向成分について処理を終えたかどうかをチェックし、終えてなければステップＳ１５０２からステップＳ１５０５までの処理を繰り返す。終えていれば、１つのブロックに対するラインヒストグラムは作成できたので、ステップＳ１５０７で、画像中の全ブロックについて処理を終了したか否かを判定する。未処理のブロックがある場合には、未処理ブロックについてステップＳ１５０２からステップＳ１５０６を繰り返す。全ブロックについて処理を終了している場合は、１画像に対してラインヒストグラムを作成できたので、本ラインヒストグラム作成処理を終了する。
【００５２】
次に、第２のラインヒストグラム作成方法について説明する。図１６はステップＳ４０６におけるラインヒストグラム作成処理のうち、上記第２の方法を実行した場合に対応するフローチャートである。
【００５３】
図１６のフローチャートにおいて、図１５に示した第１の方法のラインヒストグラム作成処理と同一の処理ステップについては、図１５と同一のステップ番号を付与し、その詳細については説明を省略する。第２の方法では方向成分ごとの線分の長さをビンとするので、ひとつのビンを求める処理が第１の方法と異なる。
【００５４】
ステップＳ１６０２において、ステップＳ１５０２と同様に線分の検出を行い、線分が検出された場合、検出された線分の長さとして同一方向のエッジを持つ画素の数をカウントする。例えば、図９の９０１では６となり、９０２は５となる。９０２のように途切れていても、第１の方法と同様に所定以上の長さであれば線分とみなすが、第１の方法では、本数をカウントしていたので、９０１でも、９０２でもカウント結果は“１本”と同一になるのに対し、第２の方法では、線分を構成する画素数をカウントするので、９０１は“６”であるのに対し９０２は“５”となり、カウント結果が異なる。また、９０３のような場合は、４５度方向として検出されたエッジを０度方向とみなし、０．５として扱い、全体では５．５になる。これにより、輪郭線のかすれなどに対する曖昧性はなくなるが、より厳密な比較が可能になる。なお、45度方向を０．５として扱ったのは、第1の方法と同様に、同一方向としてみなせる可能性があるためであり、値はこれに限られるものではない。
【００５５】
第２の方法においても、検出の範囲を注目しているブロック内にすると、図１２のような場合では第１の方法と同様にＬ１２０２を検出できない問題が発生するので、検出範囲を図１３及び図１４に示すように拡張することができる。このとき、線分の長さの最長は、もちろんブロック内に引ける線分の長さの最長と同一となる。
【００５６】
また、図１７のような折れ線の場合は次のようになる。(a)は一つだけ角をもつ折れ線の例であり、(b)は2つ以上角をもつ折れ線の例である。(a)の様に角が一つだけの折れ線の場合、人の目で判別しやすいが、(b)の様に角が2つ以上あると形状が複雑になり、人の目で判別しにくくなる。
【００５７】
従って、画像処理装置２００において類似画像判定を行う場合には、図１７（ａ）のような人の目に判別しやすい特徴を優先的に利用することが、判定結果に対するユーザの評価を高める上で好ましく、結果として精度の高い画像検索や、画像の認識や、カット点検出などが可能となる。
【００５８】
そこで、図１７の(a)の場合についてのみ特徴を抽出し、比較できるようにする。これを実現するために、線分の検出方法としては、注目方向と同一方向を有するエッジに連続するエッジであって、該注目方向と交差する方向のエッジをを追跡することで折れ線を検出することができる。即ち、ブロックの１辺から他の辺まで１つの角だけもつ条件で、エッジを追跡し、追跡できた時のみ線分(折れ線)として認める。
【００５９】
この場合、ある線分の一部が重複してカウントされることもあり得るが、全ての画像の全てのブロックについて同様に折れ線をカウントする限りは、重複カウントによる問題は生じない。また、重複を避ける方法としては、例えば次の方法がある。折れ線よりも直線の方が人の目で判別しやすいことから、特徴として優先的に利用すべきである。そこで、まず、直線のみを検出し、直線として検出済みのエッジにはフラグを立てておき、次に折れ線を検出する際にフラグが立っているエッジは検出対象外とする。折れ線のカウントは、長さとして、辺から角までの長さをカウントするようにする。例えば図１７の(a)の場合は、45度方向が２、0度方向が４となる。追跡の方法は、直線の場合と同様である。
【００６０】
ステップＳ１６０２において注目している方向成分の単位中に線分が検出された場合は、ステップＳ１６０３において、その長さをＮに足してこれを新たなＮとする。ここでＮは線分の長さの合計値を表すパラメータであり、Ｎの初期値は０である。
【００６１】
次に、ステップＳ１６０４において、注目している方向の線分を注目ブロックについて全て検出したかを判定し、検出し終えていない場合は、ステップＳ１６０２、Ｓ１６０３を繰り返す。
【００６２】
同一方向の線分を全て検出した場合、この時点でのＮは検出された線分の長さの総長となる。ステップＳ１６０５では、このＮを正規化する。例えば、0度方向のときは、ブロックの横の長さが一つの線分の最大長であり、線分は縦の長さ分の半分引けるので、結局ブロックに含まれる画素数分の半分が最大長となる。９０度方向、４５度方向、１３５度方向についても同様である。以上のように求めた最大長を１となるように正規化を行う。
【００６３】
このようにして、自然画像に含まれる対象物の輪郭線や、グラフや線画などの線分の違いを識別可能な特徴量である、ラインヒストグラムを作成することが可能となる。
【００６４】
［検索処理］
次に、画像処理装置２００における検索処理について、図５のフローチャートを参照して説明する。まず、検索元画像が入力され、入力された検索元画像のラインヒストグラムが作成される。ここまでの処理は、図４の登録処理におけるステップＳ４０１からステップＳ４０６と同様であるので、図５においても、同一のステップ番号を付加し、その詳細については説明を省略する。
【００６５】
検索元画像のラインヒストグラムが作成されると、ステップＳ５０７において画像間距離算出部３０６は、画像ＤＢ３０５中の各画像のラインヒストグラムを順次読み出して、検索元画像のラインヒストグラムとの距離を算出する。具体的には、ラインヒストグラムの各ビンの差分の絶対値の総和を求めればよい。この総和が小さいほど距離が小さくなり互いの画像が類似していることを示す。よって、最も距離が小さいものが、検索元画像の類似画像の第一候補となる。このように算出された距離と検索先画像のＩＤのリストをＲＡＭ２０３に一時保存する。
【００６６】
次に、ステップＳ５０８において画像間距離算出部３０６は、当該リストを距離の昇順にソートした後、順に画像ＩＤからインデックスを参照して画像を画像ＤＢ３０５より読み出し、縮小してサムネイル画像とする。
【００６７】
次に、ステップＳ５０９において表示部３０７は、検索結果として候補のサムネイル画像を距離と共にマトリックス上に並べて表示する。第一候補から順に列の左から右へ、上の列から下の列へ並べて表示する。ユーザはこれにより所望の画像が得られたかを確認することができる。
【００６８】
なお、本実施形態では方向成分について向きを考慮しなかったが、もちろん、向きを考慮するようにしても構わない。すなわち、図６の例でいえば、４つでなく８つにするようにしてもよい。このようにすればより厳密な検索が可能になる。
【００６９】
なお、本実施形態においては、エッジの検出は入力画像の画素単位に行ったが、前処理部３０２において縮小し、縮小画像の画素単位に行っても良い。こうすることで、入力画像にノイズが含まれている場合であっても、ノイズの影響を軽減することができる。また、微小で複雑な形状が含まれている場合であっても、その影響を軽減することができる。縮小する方法としては、例えば、画像をブロック分割するときのブロックよりもはるかに小さいメッシュブロックに分割し、メッシュブロック内の画素の輝度値を平均化し、新たな画素の輝度値とする方法がある。
【００７０】
なお、本実施形態に対応する登録処理においては、エッジ検出後、ラインヒストグラムを作成しているが、エッジ検出後、エッジ画像に対して細線化処理を行った後に、ラインヒストグラム作成を行っても良い。このように細線化処理を行った場合は、ラインヒストグラムが輪郭線の太さに依存しなくなるので、検索元画像として手書きの線画を入力し、類似する自然画像を検索するといったことが可能となる。
【００７１】
なお、本実施形態においては、ラインヒストグラム作成の方法として方向ごとの線分の本数をラインヒストグラムとする第１の方法と、方向ごとの線分の長さをラインヒストグラムとする第２の方法を挙げた。第１の方法の方が、第２の方法に比べて、より曖昧な検索が可能となるのが特徴である。これらは、用途に応じて選択して使用するとしたが、第２の方法でラインヒストグラムを作成しておき、検索時に詳細な検索を行いたい時は、実施形態に記載の通りに行い、より曖昧な検索を行う場合は、ラインヒストグラムのビンを線分１本の最大長単位で量子化し、第１の方法で作成したヒストグラムと同じにして、距離計算を行ってもよい。
【００７２】
例えば、図９のような場合、水平方向のビンは第２の方法では、１６.５を１８で正規化して０.９１６６..となる。ここで、線分の１本の最大長は６であり、これを１８で正規化して０.３３３３..となる。このステップで量子化することになる。よって、０.９１６６を量子化すると、１.００００..となる。このように量子化した値は、第１の方法で抽出した時と同じになるので、第１の方法のときと同様な曖昧性をもった検索が行える。
【００７３】
更にこのとき、曖昧な検索をするか否かを、ユーザが指定できる手段を設けるようにしてもよい。曖昧な検索が指定された場合は、前述の通り、ラインヒストグラムを量子化した上で、距離計算を行えばよい。このようにすることで、２つの方法の特徴を検索時に使い分けることが可能になる。
【００７４】
尚、実施形態において、画像入力部３０１から入力した画像を検索元画像として用いたが、既に登録された画像ＤＢ中の画像を検索元画像として用いるようにすることもできる。例えば、表示部３０７に画像ＤＢ中の画像のいくつかをランダムに選び出して、そのサムネイルを表示し、ユーザから所望の画像に類似する画像の検索指示を受け付けることで検索を行う。なお、このときは、既にライヒストグラムが、画像ＤＢに記憶されているので、改めてラインヒストグラム作成処理を行う必要がないことはいうまでもない。
【００７５】
以上説明したように、本発明によれば、人の目につきやすい画像中の対象物の輪郭線などを識別しやすい、画像の類似判定が可能となる。これにより精度の高い画像検索や、画像の認識や、カット点検出などが可能となる。
【００７６】
以上、本発明の実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能であり、具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７７】
尚、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図に示すフローチャートに対応したプログラム）を、システムあるいは装置に直接あるいは遠隔から供給し、そのシステムあるいは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００７８】
従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００７９】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であっても良い。
【００８０】
プログラムを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などがある。
【００８１】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００８２】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００８３】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００８４】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００８５】
【図１】従来のエッジヒストグラムの問題点を説明するための図である
【図２】本発明の実施形態に対応する画像処理装置２００のハードウェア構成の一例を示すブロック図である。
【図３】本発明の実施形態に対応する画像処理装置２００の機能構成の一例を示すブロック図である。
【図４】本発明の実施形態の登録処理の一例に対応するフローチャートである。
【図５】本発明の実施形態の検索処理の一例に対応するフローチャートである。
【図６】本発明の実施形態におけるエッジの方向成分の一例を示す図である。
【図７】本発明の実施形態に対応する微分フィルタの一例を示す図である。
【図８】本発明の実施形態に対応するインデックスの一例を示す図である
【図９】本発明の実施形態に対応する線分の検出方法の一例を説明するための図である。
【図１０】本発明の実施形態に対応する線分の検出方法の一例を説明するための図である。
【図１１】本発明の実施形態に対応する線分の検出方法の一例を説明するための図である。
【図１２】本発明の実施形態に対応する線分の検出における問題点を説明するための図である。
【図１３】本発明の実施形態に対応する線分の検出方法をの一例を説明するための図である。
【図１４】本発明の実施形態に対応する線分の検出方法をの一例を説明するための図である。
【図１５】本発明の実施形態の第１ラインヒストグラムの作成処理の一例に対応するフローチャートである。
【図１６】本発明の実施形態の第２ラインヒストグラムの作成処理の一例に対応するフローチャートである。
【図１７】本発明の実施形態に対応する線分の検出方法の一例を説明するための図である。
【図１８】本発明の実施形態のカラー／グレースケール判定処理の一例に対応するフローチャートである。
【図１】
2006127159.tif 000003
【図２】
2006127159.tif 000004
【図３】
2006127159.tif 000005
【図４】
2006127159.tif 000006
【図５】
2006127159.tif 000007
【図６】
2006127159.tif 000008
【図７】
2006127159.tif 000009
【図８】
2006127159.tif 000010
【図９】
2006127159.tif 000011
【図１０】
2006127159.tif 000012
【図１１】
2006127159.tif 000013
【図１２】
2006127159.tif 000014
【図１３】
2006127159.tif 000015
【図１４】
2006127159.tif 000016
【図１５】
2006127159.tif 000017
【図１６】
2006127159.tif 000018
【図１７】
2006127159.tif 000019
【図１８】
2006127159.tif 000020