(57)【要約】【課題】より正確に画像のエッジ特徴量を算出可能な画像処理装置及び方法を提供する。【解決手段】画像処理装置は、画像を該画像の部分領域である複数の第１のイメージブロックへ分割し、更に第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得し、フィルタに基づいて第１のイメージブロックの画像のエッジ方向を判定する。また、画像処理装置は、上記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成し、これら複数の区画とフィルタに基づいて第２のイメージブロックの画像のエッジ方向を判定する。そして、第１、第２のイメージブロックの少なくともいずれかによって判定されたエッジ方向に基づいて画像に含まれる部分領域のエッジ方向が決定される。【選択図】  図５
2008262424.tif 000002
【特許請求の範囲】
【請求項１】
画像を該画像の部分領域である複数の第１のイメージブロックへ分割する分割手段と、
前記分割手段で得られた第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得する取得手段と、
前記取得手段で取得した複数の区画と前記フィルタに基づいて前記第１のイメージブロックの画像のエッジ方向を判定する第１判定手段と、
前記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成する生成手段と、
前記生成手段で生成した複数の区画と前記フィルタに基づいて前記第２のイメージブロックの画像のエッジ方向を判定する第２判定手段と、
前記第１判定手段と前記第２判定手段の少なくともいずれかによって判定されたエッジ方向に基づいて前記画像に含まれる部分領域のエッジ方向を決定する決定手段とを備えることを特徴とする画像処理装置。
【請求項２】
前記生成手段は、前記第１のイメージブロックの大きさを変更し、該生成された第２のイメージブロックを前記フィルタに対応した複数の区画へ分割することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記生成手段は、前記第１のイメージブロックを前記フィルタに対応した複数の区画への分割において、分割の比率を変更することにより、前記変更された複数の区画を取得することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記第１判定手段でエッジ方向を判定できなかった場合に、前記第１のイメージブロックの輝度分布に基づいて、前記イメージブロックにおけるエッジの存在の可能性を判定する第３判定手段と、
前記第３判定手段で前記イメージブロックにエッジの存在する可能性があると判定された場合に、前記生成手段と前記第２判定手段による処理を実行させる制御手段とを更に備えることを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
前記分割手段は、入力された画像を複数のサブイメージへ分割し、前記複数のサブイメージの各々を前記複数のイメージブロックへ分割するものであり、
前記複数のサブイメージの各々について、前記決定手段によって決定されたエッジ方向のヒストグラムを生成して、前記入力された画像の特徴量とする生成手段を更に備えることを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
画像処理装置の制御方法であって、
分割手段が、画像を該画像の部分領域である複数の第１のイメージブロックへ分割する分割工程と、
取得手段が、前記分割工程で得られた第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得する取得工程と、
第１判定手段が、前記取得工程で取得した複数の区画と前記フィルタに基づいて前記第１のイメージブロックの画像のエッジ方向を判定する第１判定工程と、
生成手段が、前記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成する生成工程と、
第２判定手段が、前記生成工程で生成した複数の区画と前記フィルタに基づいて前記第２のイメージブロックの画像のエッジ方向を判定する第２判定工程と、
決定手段が、前記第１判定工程と前記第２判定工程の少なくともいずれかによって判定されたエッジ方向に基づいて前記画像に含まれる部分領域のエッジ方向を決定する決定工程とを備えることを特徴とする画像処理装置の制御方法。
【請求項７】
前記生成工程では、前記第１のイメージブロックの大きさを変更し、該生成された第２のイメージブロックを前記フィルタに対応した複数の区画へ分割することを特徴とする請求項６に記載の画像処理装置の制御方法。
【請求項８】
前記生成工程では、前記第１のイメージブロックを前記フィルタに対応した複数の区画への分割において、分割の比率を変更することにより、前記変更された複数の区画を取得することを特徴とする請求項６に記載の画像処理装置の制御方法。
【請求項９】
前記第１判定工程でエッジ方向を判定できなかった場合に、第３判定手段が、前記第１のイメージブロックの輝度分布に基づいて、前記イメージブロックにおけるエッジの存在の可能性を判定する第３判定工程と、
制御手段が、前記第３判定工程で前記イメージブロックにエッジの存在する可能性があると判定された場合に、前記生成工程と前記第２判定工程による処理を実行させる制御工程とを更に備えることを特徴とする請求項６乃至８の何れか１項に記載の画像処理装置の制御方法。
【請求項１０】
前記分割工程では、入力された画像を複数のサブイメージへ分割し、前記複数のサブイメージの各々を前記複数のイメージブロックへ分割するものであり、
生成手段が、前記複数のサブイメージの各々について、前記決定工程によって決定されたエッジ方向のヒストグラムを生成して、前記入力された画像の特徴量とする生成工程を更に備えることを特徴とする請求項６乃至９の何れか１項に記載の画像処理装置の制御方法。
【請求項１１】
コンピュータに
画像を該画像の部分領域である複数の第１のイメージブロックへ分割する分割工程と、
前記分割工程で得られた第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得する取得工程と、
前記取得工程で取得した複数の区画と前記フィルタに基づいて前記第１のイメージブロックの画像のエッジ方向を判定する第１判定工程と、
前記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成する生成工程と、
前記生成工程で生成した複数の区画と前記フィルタに基づいて前記第２のイメージブロックの画像のエッジ方向を判定する第２判定工程と、
前記第１判定工程と前記第２判定工程の少なくともいずれかによって判定されたエッジ方向に基づいて前記画像に含まれる部分領域のエッジ方向を決定する決定工程とを実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像からエッジ特徴を抽出する画像処理装置、その制御方法、コンピュータプログラムに関するものである。
【背景技術】
【０００２】
従来より、エッジ特徴を用いた様々な画像検索方法や認識方法が提案されている。エッジの抽出方法としては、画素ごとに、周囲の画素を含めた範囲に対して、微分フィルタを用いて演算を行う方法が一般的である。フィルタとしては、Prewittフィルタ、Sobelフィルタ、Robinsonフィルタ、Kirishフィルタなどがある。エッジ特徴を画像検索などに用いる場合には、多くの場合、画像の部分領域におけるエッジの分布を特徴量とする。
【０００３】
また、非特許文献１のエッジヒストグラムでは、Sobelフィルタなどを用いる方法と比べて、より少ない計算コストでエッジ分布を得るのに必要なエッジ抽出方法を用いている。以下、非特許文献１に記載されたエッジ抽出方法について説明する。
【０００４】
まず、図１２に示したように入力画像１０を４×４のサブイメージ１１（sub-image）に分割する。それぞれのサブイメージを更に所定数に近くなるように正方形のイメージブロック１２（image-block）に分割する。次に、イメージブロックを更に４（２×２）つの区画１３に分割し、それぞれの区画に対して平均輝度a(0)〜a(3)を求める。次に、図１３に示した４つの方向、（ａ）垂直方向、（ｂ）水平方向、（ｃ）４５度方向、（ｄ）１３５度方向、（ｅ）無方向に対応するフィルタを用いて、それぞれのエッジ強度m_v、m_h、m_d45、m_d135、m_ndを計算する。例えば、m_vは、イメージブロック１２の４分割された各区画の平均輝度をa(n)と表現すると次式のようになる（なお、ｎ＝０〜３であり、４分割された各区画に付加した番号を示している。
m_v＝｜1×a(0)＋(-1)×a(1)＋1×a(2)＋(-1)×a(3)｜    …（１）
【０００５】
そして、エッジ強度m_v、m_h、m_d45、m_d135、m_ndの中の最大値が、所定の閾値Ａ以上のとき、その最大値の方向が当該イメージブロックのエッジの方向であると判定する。閾値Ａは、エッジが存在しているとみなせる強度の下限値である。サブイメージ１１に含まれる各イメージブロック１２の方向をカウントすることで、エッジヒストグラムＥijが計算される。なお、ｉ＝０〜４は図１３の（ａ）〜（ｅ）に示される各フィルタに対応し、ｊ＝０〜１５は各サブイメージ１１に対応する。こうして得られたエッジヒストグラムＥijを特徴量とする。
【非特許文献１】ETRI Journal, Volume 24, Number 1,February 2002(“Efficient Use of MPEG-7 Edge Histogram Descriptor”  CheeSun Won et al.)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、文献１で示されるエッジ抽出方法は、Sobelフィルタなどを用いたエッジ抽出方法に比べて、計算コストが小さいという利点があるものの、エッジ特徴を十分に得ることができない場合がある。特に顕著に表れる例として２値画像の線画を対象とした画像検索に適用した場合について説明する。
【０００７】
図１４（ａ）に、等間隔の線２１を４本と、幅２ｄの４つのイメージブロックをそれぞれ４分割した計１６領域とを重ねて示す。２値画像の線画では、線２１に対応した領域で表現されているように、特定の濃度領域を表現するために、直線を等間隔で並べたハッチングが用いられることが多い。このようなハッチングの領域に対して、イメージブロック１２のサイズとハッチングの線２１の間隔との関係によって、ハッチングが抽出できなくなる場合がある。例えば、図１４の（ａ）に示したように、イメージブロック１２のサイズと線２１の間隔が同期した場合を考える。イメージブロック１２のサイズ（幅および高さ）を２ｄ、線２１の太さ（幅）をｂ、線２１と線２１の間の隙間をｇとして、これらが例えば以下の（２）式の関係にあるとき、式（１）において、a(n)の値がすべて同じ値になる。このため、m_vの値は０になり、明らかにくっきりと縦線が存在しているにもかかわらず、縦線が検出できなくなる。
ｄ＝ｂ＋ｇ      …（２）
【０００８】
エッジヒストグラムを用いた画像検索を行う場合、データベースに格納されている画像のエッジヒストグラムと、クエリで与える画像のエッジヒストグラムが類似していれば検索ができる。従って、図１４の（ａ）のように線２１が存在していても常にエッジを検出できないのであれば、データベースとクエリとでエッジヒストグラムの特徴量が類似する。しかしながら、図１４の（ｂ）のように、イメージブロック１２のサイズと線２１の間隔の同期が少しずれている場合は、そのずれ具合によって、エッジが検出できたりできなかったりする場合がある。例えば、図１４の（ｂ）のような関係でイメージブロック１２とハッチングの線２１が配置された場合を考える。また、イメージブロック１２のサイズ（幅および高さ）を２ｄ、イメージブロック１２の左端から線２１の左端のずれをａ、線２１の太さをｂ、線２１間の隙間をｇ、線２１の輝度を０、紙白の輝度を２５５とすると、式（１）の値は、以下のようになる。
【０００９】
a(0)＝a(2)＝(ｄ−(ｂ−ａ)×２５５)／ｄ
a(1)＝a(3)＝((ｄ−ｂ)×２５５)／ｄ
m_v＝(ａ×２５５)／ｄ                        …（３）
したがって、イメージブロックのサイズがクエリの画像とデータベースの画像とで同じであるとすると、m_vの値は、ａの値によって、閾値Ａより大きくなったり小さくなったりして、エッジが検出できたりできなかったりする。
【００１０】
このような状態は、ハッチングの線２１が長ければ、線２１の方向に沿って広がっていき、線２１の太さや間隔等の条件によっては、線２１の鉛直方向に広がっていく。ハッチングは、広い領域に適用される場合も有り、このような場合は、人間にとっては非常に似通った画像であっても、エッジヒストグラムの特徴量は大きく異なることにつながり、結果的に、類似する画像が検索できないという不具合が発生する。
【００１１】
本発明は上記の課題に鑑みてなされたものであり、より正確に画像のエッジ特徴量を算出可能な画像処理装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の目的を達成するための本発明の一態様による画像処理装置は以下の構成を備える。即ち、
画像を該画像の部分領域である複数の第１のイメージブロックへ分割する分割手段と、
前記分割手段で得られた第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得する取得手段と、
前記取得手段で取得した複数の区画と前記フィルタに基づいて前記第１のイメージブロックの画像のエッジ方向を判定する第１判定手段と、
前記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成する生成手段と、
前記生成手段で生成した複数の区画と前記フィルタに基づいて前記第２のイメージブロックの画像のエッジ方向を判定する第２判定手段と、
前記第１判定手段と前記第２判定手段の少なくともいずれかによって判定されたエッジ方向に基づいて前記画像に含まれる部分領域のエッジ方向を決定する決定手段とを備える。
【００１３】
また、上記の目的を達成するための本発明の他の態様による画像処理装置の制御方法は、
画像処理装置の制御方法であって、
分割手段が、画像を該画像の部分領域である複数の第１のイメージブロックへ分割する分割工程と、
取得手段が、前記分割工程で得られた第１のイメージブロックを分割して、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画を取得する取得工程と、
第１判定手段が、前記取得工程で取得した複数の区画と前記フィルタに基づいて前記第１のイメージブロックの画像のエッジ方向を判定する第１判定工程と、
生成手段が、前記複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックを生成する生成工程と、
第２判定手段が、前記生成工程で生成した複数の区画と前記フィルタに基づいて前記第２のイメージブロックの画像のエッジ方向を判定する第２判定工程と、
決定手段が、前記第１判定工程と前記第２判定工程の少なくともいずれかによって判定されたエッジ方向に基づいて前記画像に含まれる部分領域のエッジ方向を決定する決定工程とを備える。
【発明の効果】
【００１４】
本発明によれば、より正確に画像のエッジ特徴量を算出することができる。また、本発明によれば、イメージブロックを単位としたエッジ方向判定を行なうので、Sobelフィルタなどを用いる手法に比べて高速である。即ち、本発明によれば、高速、且つ、画像検索などに用いるのに十分なエッジ特徴を得ることが可能な画像処理装置及び方法が提供され得る。
【発明を実施するための最良の形態】
【００１５】
以下、添付の図面を参照して本発明の好適な実施形態について詳細に説明する。以下の実施形態では、画像のエッジ抽出方法を、エッジヒストグラムを特徴量とした画像検索に応用した例で説明する。
【００１６】
図１は、本実施形態における画像処理装置１００の制御構成を示すブロック図である。図１において、１０１はＣＰＵであり、本実施形態の画像処理装置１００における各種制御を実行する。１０２はＲＯＭであり、本装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するためのコンピュータプログラムを格納するとともに、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１７】
１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、光ディスク、磁気ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカード等で構成される。１０７は表示器であり、ディスプレイなどで構成され、結果等をユーザに対して表示する。１０８はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。１０９はＩＥＥＥ１３９４、ＵＳＢなどのインターフェースであり、スキャナ１１１やデジタルカメラ１１２などの機器と通信を行う。１１０はシステムバスであり、上述した各構成を通信可能に接続する。
【００１８】
なお、上記の構成において外部記憶装置１０６、スキャナ１１１、デジタルカメラ１１２はネットワーク上に配置されたもので代用されてもよい。
【００１９】
図２は、本実施形態の画像処理装置１００によるエッジ抽出及び特徴量算出処理に関する機能構成を示すブロック図である。
【００２０】
図２において、２０１は画像入力部であり、スキャナ１１１やデジタルカメラ１１２などの機器で取得した画像をインターフェース１０９を介して、或いは、インターネット上やＬＡＮ上に存在する画像をネットワークインターフェース１０８を介して入力する。２０２は前処理部であり、入力された画像に対して必要な前処理を行う。２０３はエッジ抽出部であり、前処理部２０２による前処理後の画像に対してエッジ抽出処理を行う。２０４はヒストグラム生成部であり、エッジ抽出部２０３によるエッジ抽出結果に基づいてエッジ方向の出現頻度を表すエッジヒストグラムを生成する。２０５は画像データベースであり、入力された画像とエッジヒストグラムを関連付けて記憶・管理する。２０６は画像間距離算出部であり、検索時に画像データベース２０５中の画像のエッジヒストグラムと、検索元として入力された画像のエッジヒストグラムの距離を算出する。２０７は表示部であり、画像間距離算出部２０６による距離の算出結果に基づいて、ユーザに対して検索結果の画像の表示を行う。上述した各部はＣＰＵ１０１がＲＯＭ１０２に格納されたコンピュータプログラム或は外部記憶装置１０６からＲＡＭ１０３にロードされたコンピュータプログラムを実行することにより実現される。
【００２１】
［登録処理］
まず、画像処理装置１００への画像の登録処理について、図３のフローチャートを用いて説明する。
【００２２】
まず、ステップＳ３０１において、画像入力部２０１は、ネットワークインターフェース１０８やインターフェース１０９を介して登録対象の画像を入力する。次に、ステップＳ３０２において前処理部２０２は、入力画像がカラーかグレースケールかを判定する。入力画像がカラーの場合は、ステップＳ２０３において、前処理部２０２は、当該入力画像をグレースケールに変換する。尚、カラーかグレースケールかの判定は、デジタルカメラ１１２から画像を取得した場合などでは、画像のデータフォーマットを解析し、そのヘッダ情報を参照することで判定できる。また、スキャナ１１１から画像を取得した場合などでは、ユーザによって設定されたスキャン条件から判定できる。又、ステップＳ３０３におけるカラーからグレースケールへの変換は、例えば以下の(４)式により、カラー画像データの各画素のＲ（赤）、Ｇ（緑）、Ｂ（青）の値をグレースケールの信号（Ｙ）へ変換することにより行われる。
【００２３】
Ｙ＝０．２９９×Ｒ＋０．５８７×Ｇ＋０．１１４×Ｂ      …（４）
次に、ステップＳ３０４においてエッジ抽出部２０３は、入力画像に対してエッジの抽出を行う。エッジ抽出の処理の詳細は後述する。次に、ステップＳ３０５においてエッジヒストグラム生成部２０４は、ステップＳ３０５で抽出されたエッジを集計し、図１２、図１３により上述したようにエッジヒストグラムEijを生成する。次に、ステップＳ３０６においてエッジヒストグラム生成部２０４は、生成したエッジヒストグラムEijをインデックスとして画像と関連付けて画像データベース２０５に記憶する。
【００２４】
図４は、エッジヒストグラムによるインデックスの例である。画像ＩＤ４０１は、登録される画像にふられたＩＤ(識別子)である。エッジヒストグラム４０２は、対応する画像のエッジヒストグラムEijである。画像ファイルへのパス４０３は、登録された画像ファイルへのパス情報であり、これを参照することで、画像データの本体を読み出すことができる。
【００２５】
[エッジ抽出処理]
エッジ抽出処理の詳細について、図５のフローチャートを用いて説明する。
【００２６】
まず、ステップＳ５０１において、エッジ抽出部２０３は、入力画像をイメージブロックに分割する。これは、図１２により上述したように、４ｘ４のサブイメージ１１中に所定数に近い数の正方形のイメージブロック１２を確保するように分割することである。ここで「所定数」は特に限定されるものではないが、後にイメージブロックに対して２×２のフィルタ処理を施すことになるので、正方形の一辺は、２画素以上であり、かつ、偶数でなければならない。すなわち、ステップＳ５０１において、画像が当該画像の部分領域である複数のイメージブロックへ分割される。本願では、このステップＳ５０１で得られた複数のイメージブロックを第１のイメージブロックと称する。複数の第１のイメージブロックの各々からは、イメージブロックの画像のエッジ方向を判定するフィルタに対応した複数の区画が取得される。
【００２７】
次に、ステップＳ５０２において、イメージブロックを一つずつ順番に取り出す。全てのイメージブロックについて処理を終えた場合は、ステップＳ５０３から本エッジ抽出処理を終了する。未処理のイメージブロックが取り出された場合は、ステップＳ５０３からステップＳ５０４へ処理が進む。
【００２８】
ステップＳ５０４において、上記取得された複数の区画とフィルタに基づいて第１のイメージブロックの画像のエッジ方向が判定される（第１判定処理）。すなわち、対象のイメージブロックに対して、図１３に示した４つの方向と無方向のフィルタを掛け、それぞれのエッジ強度（m_v、m_h、m_d45、m_d135、m_nd）を求める。そして、求めたエッジ強度のうちの最大のエッジ強度に閾値Ａ以上であれば、そのエッジ強度に対応する方向を当該イメージブロック１２の方向として決定し、方向とエッジ強度をＲＡＭ１０３に一時保存する。一方、最大のエッジ強度が閾値Ａ未満であれば、エッジの方向は決定できないままである。このとき、当該イメージブロック１２の平均輝度をＲＡＭ１０３に一時保存しておく。（１）式に示したように、エッジ強度を求める際に、イメージブロックの４分割された各小領域の平均輝度（a(0)〜a(3)）を求めてあるので、イメージブロック１２の平均輝度は少ない処理コストで求めることができる。
【００２９】
ステップＳ５０４においてエッジの方向が決定できた場合は、ステップＳ５０５からステップＳ５０２に戻る。一方、ステップＳ５０４においてエッジの方向が決定できなかった場合は、ステップＳ５０５からステップＳ５０６へ進む。
【００３０】
ステップＳ５０６において、エッジ抽出部２０３は、処理対象のイメージブロック１２に対して、エッジの抽出漏れが発生したかどうかを判定する。エッジ抽出漏れの判定は図６の参照により後述する。ステップＳ５０６において抽出漏れが発生していると判定された場合、処理はステップＳ５０７へ進む。ステップＳ５０７において、エッジ抽出部２０３は、対象のイメージブロック１２のエッジの方向を補正処理によって決定しなおす（方向決定補正処理）。なお、このステップＳ５０７においてなされるエッジ方向の判定を、上記第１判定処理に対して第２判定処理ともいう。また、ステップＳ５０６による判定処理は、第１判定手段でエッジ方向を判定できなかった場合に、第１のイメージブロックの輝度分布等に基づいて、イメージブロックにおけるエッジの存在の可能性を判定する第３判定処理であり、第３判定処理ともいう。そして、処理はステップＳ５０２に戻る。この補正処理の詳細は、図８の参照により後述する。尚、ステップＳ５０６においてエッジの抽出漏れは発生していないと判定された場合には、処理はそのままステップＳ５０２へ戻る。
【００３１】
続いて、ステップＳ５０６によるエッジ抽出漏れの判定処理の詳細を、図６のフローチャートを用いて説明する。
【００３２】
ステップＳ６０１において、エッジ抽出部２０３は、処理対象のイメージブロック１２の平均輝度値が所定の値よりも大きいかどうかを判定する。本発明が解決しようとしている課題は、主に線画において発生し、線画の背景が白地である場合が多く、また、線画では、線分が存在しないイメージブロックも多数存在する可能性が高い。そこで、本実施形態では、処理対象のイメージブロックの平均輝度が所定の値よりも大きければ、線分が存在しない、或は、エッジが少ないイメージブロックであると判断する。即ち、平均輝度が所定の値よりも大きければ、エッジの抽出漏れはないとして本処理を終了する。これにより、線分が少ないイメージブロックに不必要な補正処理を行ってしまうことを防止でき、エッジ抽出処理の高速化を図ることができる。一方、ステップＳ６０１においてイメージブロック１２の平均輝度値が所定の値以下の場合はステップＳ６０２へ進む。
【００３３】
ステップＳ６０２において、エッジ抽出部２０３は、複数の当該イメージブロック１２に線分が存在しているかどうかを判定するために、複数の当該イメージブロック１２に関して輝度ヒストグラムを生成する。この輝度ヒストグラムの生成では、ステップＳ５０４で求めた当該イメージブロック１２の平均輝度が用いられる。ヒストグラムの生成について以下により詳細に説明する。
【００３４】
イメージブロック１２の輝度ヒストグラムは、線分が存在しない場合には、一様な図７の（ａ）に示されるような分布を取ると思われる。しかしながら、図１４に示したようにイメージブロック１２内に線分が存在する場合には、図７の（ｂ）に示されるように、平均輝度の度数よりも平均輝度の両側の極大値の度数の方が大きくなる。線の太さによりどちらかの山が高くなることもある。したがって、本実施形態では、図７の（ｃ）に示されるように、ビン数を３とし、ビンの境界を平均輝度から所定の値Ｗを引いた値と、平均輝度に所定の値Ｗを加えた値として輝度ヒストグラムを生成する。このような輝度ヒストグラムによれば、図７の（ａ）と（ｂ）の違いを容易に判定できるようになる。
【００３５】
ステップＳ６０３において、エッジ抽出部２０３は、ステップＳ６０２で生成した輝度ヒストグラムを用いてエッジの抽出漏れが発生したかどうかを判定する。本実施形態では、エッジ抽出部２０３は、平均輝度に対応したビンの度数の値が、他の２つのビンのどちらの値よりも所定の値Ｚ以上に小さければ抽出漏れが発生したと判断し、そうでなければ、抽出漏れは発生していないと判断する。このように、エッジの抽出漏れが発生しているかどうかを、ステップＳ５０７の補正処理を行う前に行うことにより、エッジ漏れの発生していないイメージブロックに対して補正処理が実行されてしまうことを防止できる。後述のように、ステップＳ５０７の補正処理はイメージブロックのサイズを変えて何度もエッジの方向決定処理を試みるため、無駄な補正処理を省くことは、処理速度の向上に著しく貢献する。
【００３６】
続いて、ステップＳ５０７による補正処理の詳細を、図８のフローチャートを用いて説明する。補正処理では、上記第１のイメージブロックについて取得された複数の区画とは大きさが異なる複数の区画から構成される第２のイメージブロックが生成され、これら複数の区画とフィルタに基づいて第２のイメージブロックの画像のエッジ方向が判定される。
【００３７】
ステップＳ８０１において、エッジ抽出部２０３は、対象のイメージブロック１２に対して、当該イメージブロック１２の高さと幅を２画素ずつ減らしていく。こうして、ステップＳ５０１で取得された複数の区画とは大きさの異なる複数の区画が取得されることになる。図１５を見れば明らかなように、イメージブロックの大きさを徐々に小さくしていけば、ハッチングに対してエッジが抽出できていない場合でも、いつかはエッジが抽出できるようになる。例えば、図１５の（ａ）に示されるように線２１とイメージブロック１２が配置されていると、上下左右の区画に平均輝度値の差が発生しないのでエッジは検出されない。図１５の（ｂ）に示されるように、元のイメージブロック１２から縦横２画素を減少させても、上下左右の区画に平均輝度値の差は生じない。これに対して、図１５の（ｃ）に示されるように、元のイメージブロック１２の大きさを縦横４画素ずつ減少させると、左右の区画で平均輝度値に差が生じ、縦方向のエッジが検出されることになる。
【００３８】
次に、ステップＳ８０２において、エッジ抽出部２０３は、イメージブロックのサイズに応じて分岐する。処理時のイメージブロックのサイズが、初めのイメージブロックのサイズより所定の割合以下になったかどうかで分岐する。例えば、イメージブロックのサイズが元のサイズの２分の１よりも小さくなれば、エッジは抽出できなかったものとして、ＲＡＭ１０３にエッジがないということを一時保存し処理を終了する。イメージブロックのサイズが元のサイズの２分の１以上であれば処理はステップＳ８０３へ進む。
【００３９】
ステップＳ８０３において、エッジ抽出部２０３は、エッジの方向を決定する（第２判定処理。この処理はステップＳ５０４と同じ処理である。そして、ステップＳ８０４において、エッジ抽出部２０３は、ステップＳ８０３においてエッジの方向が決定できたかどうかを判定する。エッジの方向が決定できていない場合は、処理はステップＳ８０１へ戻り、決定できていれば、処は終了する。以上のようにして、イメージブロックのサイズを徐々に縮小してエッジの方向を決定することによって、ハッチングなどに対してステップＳ５０４で決定できなかったエッジの方向を決定して補正することができる。
【００４０】
尚、上記の処理では、ステップＳ５０６の第３判定処理で抽出漏れありと判定された場合にのみステップＳ５０７の方向決定処理が行われるが、これに限られるものではない。例えば、ステップＳ５０６の判定を行わずに、ステップＳ５０７の方向決定補正処理を必ず実行するようにしてもよい。この場合、例えば、イメージブロックのサイズを変更することにより得られた複数種類のエッジ方向判定結果から、最もエッジ強度の強いエッジ方向判定結果を採用する。以上のように、本実施形態によれば、第１判定処理と第２判定処理の少なくともいずれかによって判定されたエッジ方向に基づいて画像に含まれる部分領域のエッジ方向が決定される。
【００４１】
［検索処理］
画像処理装置１００による検索処理について、図９のフローチャートを用いて説明する。
【００４２】
まず、ステップＳ９０１〜Ｓ９０５において、画像入力部２０１により検索元画像を入力し、前処理部２０２、エッジ抽出部２０３、エッジヒストグラム生成部２０４によりエッジヒストグラムを生成する。ここまでの処理は、図３の登録処理におけるステップＳ３０１〜ステップＳ３０５と同じである。
【００４３】
次に、ステップＳ９０６において、画像間距離算出部２０６は、画像データベース２０５内の各画像のエッジヒストグラムを順に読み出し、検索元画像のエッジヒストグラムとの距離を算出する。具体的には、例えば、エッジヒストグラムＥijの各ビンの差分の絶対値の総和を算出する。算出された距離が小さいほど両画像が類似していることになり、最も距離が小さいものが第１候補となる。このように算出された距離と検索先画像のＩＤのリストをＲＡＭ１０３に一時保存する。
【００４４】
次に、ステップＳ９０７において画像間距離算出部２０６は、ステップＳ９０７で取得したリストを距離の昇順にソートした後、順に画像ＩＤからインデックスを参照して画像を画像データベース２０５より読み出し、縮小してサムネイル画像とする。
【００４５】
次に、ステップＳ９０８において、表示部２０７は検索結果を表示する。より具体的には、表示部２０７は、ステップＳ９０７で取得されたサムネイル画像を距離と共にマトリックス上に並べて表示する。例えば、第１候補から順に列の左から右へ、上の列から下の列へ並べて表示する。ユーザはこれにより所望の画像が得られたかを確認することができる。
【００４６】
[他の実施形態]
上記実施形態においては、画像検索に用いられる特徴量として文献１に記載されているエッジヒストグラムを使用したが、もちろん、これに限定されるものではない。例えば、無方向フィルタを用いず、方向フィルタのみを用いるようにしてもよい。また、式（１）では、エッジの向きの違いは考慮していない（絶対値をとっている）が、式（１）においてプラスの値とマイナスの値を別々に扱うようにして、向きの違いを考慮するようにしてもよい。また、方向フィルタを５つ以上用いてもよい。例えば、図１３に示した（ａ）〜（ｄ）の方向フィルタに、２２．５度、６７．５度、１１２．５度、１５７．５度を加えた８つの方向フィルタを用いてもよい。
【００４７】
また、上記実施形態では、エッジの抽出漏れが発生し、エッジの方向決定を補正するために、ステップＳ９０１に示したように、イメージブロックのサイズを縮小して補正していたが、これに限られるものではない。例えば、イメージブロックのサイズを拡大して補正を行うようにしてもよく、このような手法でもハッチングなどに対してエッジが抽出できるようになる。また、イメージブロックのサイズを変えるのではなく、図１０に示すように、イメージブロック中の区画のサイズを変えるようにしてもよい。すなわち、図１０に示されるように、ｄ２の値を小さくし、ｄ１の値を大きくするといったように、分割の比率を変更することにより、イメージブロック１２内の区画の形状が変更される。このように区画の形状を変更して上記フィルタによるエッジ方向検出を行なうことにより、ハッチングなどに関連したエッジを抽出できるようになる。即ち、上記実施形態によれば、イメージブロックから取得される複数の区画の画素構成を異ならせて変更された複数の区画を取得し、新たな複数の区画についてフィルタによるエッジ方向検出を行なうことにより、線分の検出漏れが防止されるのである。
【００４８】
また、上記実施形態では、エッジ抽出漏れと判定されたイメージブロックに対してエッジ方向決定の補正を行っていたが、複数種類のイメージブロックで複数のエッジヒストグラムを生成し、度数の大きいエッジヒストグラムを採用するようにしてもよい。例えば、最初のイメージブロックのサイズでエッジヒストグラムを生成した後、イメージブロックのサイズを段階的に小さくしていって、エッジヒストグラムを再生成する。こうして得られた複数のエッジヒストグラムの中から、サブイメージに対する各方向の度数の大きいほうを採用する。尚、異なるサイズのイメージブロック（即ち、異なる個数のサブイメージ内のイメージブロック）に対するエッジヒストグラムの度数を比較する場合、当然のことながら、度数はイメージブロックの個数で正規化を行っておく必要がある。
【００４９】
図１１は、上記複数のエッジヒストグラムを生成する場合の処理を説明するフローチャートである。エッジ抽出部２０３は、ステップＳ１１０１において、初期のイメージブロックサイズを設定する。ステップＳ１１０２において、エッジ抽出部２０３は、設定されたブロックサイズのイメージブロックへ入力画像を分割する。ステップＳ１１０２〜Ｓ１１０５は図５ステップＳ５０１〜Ｓ５０４と同様である。ステップＳ１１０４で全てのイメージブロックについて処理を終えたと判定されると、処理はステップＳ１１０６へ進む。ステップＳ１１０６においてエッジ抽出部２０３は、イメージブロックのブロックサイズを変更する。例えば、縦横に２画素ずつ小さいイメージブロックのサイズを設定する。予め用意した全てのブロックサイズについて処理を終えている場合は、ステップＳ１１０７から本処理を終了する。未処理のブロックサイズがあれば、処理をステップＳ１１０２に戻し、当該変更されたブロックサイズのイメージブロックへ分割してエッジ方向の決定を行う。ステップＳ３０５では、こうして、複数のイメージブロックのサイズに対応したエッジ抽出結果から度数の大きいエッジヒストグラムが選択され、当該入力画像のエッジヒストグラムとして採用される。
【００５０】
また、上記実施形態では、ステップＳ６０１に示すように、イメージブロックの平均輝度が大きい場合にエッジの抽出漏れ無しと判定していたが、イメージブロックの平均輝度が所定閾値よりも小さい場合にもエッジの抽出漏れ無しと判定するようにしてもよい。また、上記実施形態では、ステップＳ６０２に示したように、イメージブロックの平均を中心とした輝度ヒストグラムを用いてエッジの抽出漏れを判定していたがこれに限られるものではない。例えば、イメージブロック内の輝度の分散を求めて、分散が所定の値よりも大きければエッジの抽出漏れありと判定するようにしてもよい。即ち、イメージブロック内の輝度分布（輝度ヒストグラムや輝度の分散）に基づいてエッジの存在の可能性が判定される。
【００５１】
以上説明したように、上記実施形態によれば、Sobelフィルタなどを用いる手法に比べて高速であり、かつ、ハッチング等に対してエッジの抽出漏れを回避したエッジ抽出が可能となり、エッジ特徴を利用した画像検索の高精度化を図ることができる。
【００５２】
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００５３】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したプログラムである。
【００５４】
従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００５５】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であっても良い。
【００５６】
プログラムを供給するためのコンピュータ可読記憶媒体としては以下が挙げられる。例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などである。
【００５７】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明のコンピュータプログラムをハードディスク等の記録媒体にダウンロードすることが挙げられる。この場合、ダウンロードされるプログラムは、圧縮され自動インストール機能を含むファイルであってもよい。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００５８】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布するという形態をとることもできる。この場合、所定の条件をクリアしたユーザに、インターネットを介してホームページから暗号を解く鍵情報をダウンロードさせ、その鍵情報を使用して暗号化されたプログラムを実行し、プログラムをコンピュータにインストールさせるようにもできる。
【００５９】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。
【００６０】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれて前述の実施形態の機能の一部或いは全てが実現されてもよい。この場合、機能拡張ボードや機能拡張ユニットにプログラムが書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行なう。
【図面の簡単な説明】
【００６１】
【図１】実施形態による画像処理装置の構成例を示すブロック図である。
【図２】実施形態による画像処理装置の機能構成例を示すブロック図である。
【図３】実施形態による登録処理を示すフローチャートである。
【図４】実施形態における、エッジヒストグラムによるインデックスのデータ構成例を示す図である。
【図５】実施形態によるエッジ抽出処理を示すフローチャートである。
【図６】実施形態によるエッジ抽出漏れの判定処理を示すフローチャートである。
【図７】実施形態によるイメージブロックの輝度ヒストグラムの例を示す図である。
【図８】実施形態によるエッジ方向の補正処理を示すフローチャートである。
【図９】実施形態による検索処理を示すフローチャートである。
【図１０】イメージブロックの区画のサイズ変更の例を示す図である。
【図１１】実施形態によるエッジ抽出処理の変形例を示すフローチャートである。
【図１２】画像におけるサブイメージとイメージブロック及び区画の関係を表した図である。
【図１３】エッジの型と抽出フィルタの例を示した図である。
【図１４】従来のエッジ抽出方法の課題を説明する図である。
【図１５】イメージブロックの縮小を説明する図である。
【図１】
2008262424.tif 000003
【図２】
2008262424.tif 000004
【図３】
2008262424.tif 000005
【図４】
2008262424.tif 000006
【図５】
2008262424.tif 000007
【図６】
2008262424.tif 000008
【図７】
2008262424.tif 000009
【図８】
2008262424.tif 000010
【図９】
2008262424.tif 000011
【図１０】
2008262424.tif 000012
【図１１】
2008262424.tif 000013
【図１２】
2008262424.tif 000014
【図１３】
2008262424.tif 000015
【図１４】
2008262424.tif 000016
【図１５】
2008262424.tif 000017