(57)【要約】【課題】  任意形状の画像についての高速かつ高精度な検索を実現する。【解決手段】  任意の形状である任意形状画像が、そのブロック毎の画像特徴量とともにデータベースに予め登録されており、検索画像をそのブロック毎の画像特徴量とともに入力し(S401)、前記任意形状画像および前記検索画像についてのブロック毎の画像特徴量に基づき、データベースにおいて検索対象となる任意形状画像を絞り込み(S402)、前記検索画像と前記絞りこまれた任意形状画像について、ブロック毎に画像特徴量同士の類似度を算出し(S403)、該算出された類似度に基づき、検索結果を出力する(S404,S405)。【選択図】  図13
2007034613.tif 000002
【特許請求の範囲】
【請求項１】
任意形状の画像を入力する画像入力手段と、
前記画像に対して外接矩形を与え作成する外接矩形作成手段と、
前記外接矩形をブロックに分割するブロック分割手段と、
前記ブロックの画像特徴量を抽出する画像特徴量抽出手段と、
前記ブロック内の形状情報を抽出するブロック内形状情報抽出手段と、
前記画像特徴量と前記ブロック内形状情報を前記画像と関連付けて登録する登録手段と、
前記画像特徴量と前記ブロック内形状情報を用いて画像を検索する画像検索手段と、
を有することを特徴とする画像検索処理装置。
【請求項２】
前記画像検索手段は、
前記ブロック内形状情報からブロックごと毎の重みを決定する重み決定手段と、
前記ブロックごと毎の画像特徴量の距離に前記重みによる重み付けを行うことにより、画像間の類似度を算出する類似度算出手段と、
を有することを特徴とする請求項１に記載の画像検索処理装置。
【請求項３】
前記画像検索手段は、
前記ブロック内形状情報を用いて絞込検索を行う絞込検索手段と
を更に有することを特徴とする請求項１から２のいずれかに記載の画像検索処理装置。
【請求項４】
前記ブロック内形状情報は、ブロックにおける前記画像の占有情報を含むことを特徴とする請求項１から３のいずれかに記載の画像検索処理装置。
【請求項５】
前記占有情報は、ブロックにおける前記画像の占有率を含むことを特徴とする請求項４に記載の画像検索処理装置。
【請求項６】
前記ブロック内形状情報は、ブロックにおける前記画像の近似形状情報を含むことを特徴とする請求項１から５のいずれかに記載の画像検索処理装置。
【請求項７】
前記占有情報は、ブロックが前記画像を含んでいるかを０か１で示すことを含み、
前記絞込検索手段は、検索元画像の前記占有情報と検索先画像の前記占有情報とを論理積で計算することにより絞込みを行う
ことを特徴とする請求項１から６のいずれかに記載の画像検索処理装置。
【請求項８】
前記占有情報は、ブロックが前記画像を含んでいるかを０か１で示すことを含み、
前記登録手段は、
０か１を用いて表された占有情報が同一である画像特徴量とブロック内形状情報とをまとめ、占有情報をキーとして登録し、
前記絞込検索手段は、検索元画像の前記占有情報と前記キーが一致する画像特徴量とブロック内形状情報を取り出すことにより絞込みを行う
ことを特徴とする請求項１から６のいずれかに記載の画像処理検索装置。
【請求項９】
前記外接矩形作成手段は、正規化された外接矩形を与え作成する
ことを特徴とする請求項１から８のいずれかに記載の画像検索処理装置。
【請求項１０】
前記画像特徴量抽出手段は、各ブロックにおいて、前記画像を含んでいる範囲のみから画像特徴量を抽出する
ことを特徴とする請求項１から９のいずれかに記載の画像検索処理装置。
【請求項１１】
任意形状の画像を入力する画像入力ステップと、
前記画像に対して外接矩形を作成する外接矩形作成ステップと、
前記外接矩形をブロックに分割するブロック分割ステップと、
前記ブロックの画像特徴量を抽出する画像特徴量抽出ステップと、
前記ブロック内の形状情報を抽出するブロック内形状情報抽出ステップと、
前記画像特徴量と前記ブロック内形状情報を前記画像と関連付けて登録する登録ステップと、
前記画像特徴量と前記ブロック内形状情報を用いて画像を検索する画像検索ステップと、
を有することを特徴とする画像処理方法。
【請求項１２】
情報処理装置で実行されることによって、該情報処理装置を請求項１乃至１０の何れかに記載された情報処理装置として動作するように制御することを特徴とするプログラム。
【請求項１３】
請求項１２に記載されたプログラムが記録されたことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理装置およびその方法に関し、特に、任意形状の類似画像を検索する画像処理装置およびその方法に関する。
【背景技術】
【０００２】
近年、画像を解析して、色、エッジ、テクスチャなどの特徴量を抽出し、特徴量同士の比較によって、2枚の画像の類似性を判定する技術が発達しており、類似画像の検索や、動画像のカット点検出等に利用されている。
【０００３】
このような類似性を判定する技術は、矩形画像に対して有効なものを中心に発達してきたが、任意形状の画像に適用可能な技術も提案されている。
【０００４】
例えば特許文献１によれば、任意形状を含む矩形画像を生成し、任意形状の画像部分から得られる代表値で背景領域部分を補完し、その矩形画像に対して従来の画像特徴抽出を適用することによって、類似性を判定している。
【０００５】
また、例えば特許文献２によれば、任意形状の注目領域外に相当する背景領域部分については、他のあらゆる特徴量との距離が0となるような特別な特徴量を設定し、距離計算への影響を排除している。
【特許文献１】特開2002-245456公報
【特許文献２】特開平11-312248号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１に開示された技術においては、以下のような問題があった。
【０００７】
すなわち、形状によらず矩形画像を生成してから画像を登録するので、検索元画像であるクエリ画像がどのような形状であってもまず、予め検索先画像として登録されている全ての画像との比較が必要となる。したがって、登録画像数が増えれば増えるほど、検索速度が低下してしまう。
【０００８】
また、任意形状の画像部分から得られる代表値で背景領域部分を補完するため、任意形状の画像の差が背景領域部分にも積み重なって距離計算されてしまい、高精度な検索ができない。
【０００９】
一方、上記特許文献２に開示された技術においても、以下のような問題があった。
【００１０】
すなわち、画像ごとに最頻の特徴量をキーとして検索対象を絞り込めるが、背景領域のみのブロックについても、通常どおりに特徴量を抽出して登録しているため、検索対象の絞り込みは、注目領域に対する検索時には有効ではない。従って、登録画像数が増えるほど、任意形状の画像(注目領域)についての検索速度は低下してしまう。
【００１１】
また、任意形状の画像が含まれるブロックについては、背景領域部分も含めて特徴量が抽出されるため、背景領域部分が多い場合には、有効な特徴量が抽出されず、高精度な検索ができない。
【００１２】
本発明は上述した問題を個々にまたはまとめて解決するためになされたものであり、任意形状の画像についての高速な検索を可能とする画像処理装置及びその方法を提供することを目的とする。
【００１３】
また、任意形状の画像についての高精度な検索を可能とする画像処理装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するための一手段として、本発明の画像処理装置は以下の構成を備える。
【００１５】
すなわち、任意形状の画像を入力する画像入力手段と、前記画像に対して外接矩形を作成する外接矩形作成手段と、前記外接矩形をブロックに分割するブロック分割手段と、前記ブロックの画像特徴量を抽出する画像特徴量抽出手段と、前記ブロック内の形状情報を抽出するブロック内形状情報抽出手段と、前記画像特徴量と前記ブロック内形状情報を前記画像と関連付けて登録する登録手段と、前記画像特徴量と前記ブロック内形状情報を用いて画像を検索する画像検索手段とを有することを特徴とする。
【００１６】
また、本発明の画像処理方法は以下の構成を備える。
【００１７】
すなわち、任意形状の画像を入力する画像入力ステップと、前記画像に対して外接矩形を作成する外接矩形作成ステップと、前記外接矩形をブロックに分割するブロック分割ステップと、前記ブロックの画像特徴量を抽出する画像特徴量抽出ステップと、前記ブロック内の形状情報を抽出するブロック内形状情報抽出ステップと、前記画像特徴量と前記ブロック内形状情報を前記画像と関連付けて登録する登録ステップと、前記画像特徴量と前記ブロック内形状情報を用いて画像を検索する画像検索ステップとを有することを特徴とする。
【発明の効果】
【００１８】
以上の構成からなる本発明によれば、画像のブロック単位に抽出した画像特徴量に基づいて類似度算出前の絞り込みを高速に行うことによって、任意形状の類似画像を高速に検索することが可能となる。
【００１９】
また、画像のブロック単位に抽出した画像特徴量に基づいて類似度算出を行うことによって、任意形状の類似画像を高精度に検索することが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下、添付の図面を参照して、本発明をその好適な実施形態に基づいて詳細に説明する。
【００２１】
＜第１実施形態＞
●システム構成
図1は、本実施形態における画像処理装置の構成を示すブロック図である。同図において、101はCPUであり、本実施形態の画像処理装置における各種制御を実行する。102はROMであり、本装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。
【００２２】
103はRAMであり、CPU101が処理するための制御プログラムを格納するとともに、CPU101が各種制御を実行する際の作業領域を提供する。104はキーボード、105はマウスであり、ユーザによる各種入力操作環境を提供する。
106は外部記憶装置であり、ハードディスクやフレキシブルディスク、光ディスク、磁気ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカード等で構成される。107は表示器であり、ディスプレイなどで構成され、結果等をユーザに対して表示する。108はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。109はIEEE1394,USBなどのインターフェースであり、スキャナ110やデジタルカメラ111などの機器と通信を行う。また、112は上記の各構成を接続するバスである。
【００２３】
なお、上記構成において外部記憶装置106、スキャナ110、デジタルカメラ111は、ネットワーク上に配置されたもので代用することができる。
【００２４】
図2は、図1に示す構成からなる画像処理装置の機能構成を示すブロック図である。同図において、201は画像入力部であり、スキャナ110、デジタルカメラ111などの機器で取得した画像を、インターフェース109を介して、或いは、インターネットやLAN等のネットワーク上に存在する画像を、ネットワークインターフェース108を介して入力する。202は領域抽出部であり、画像入力部201で入力された画像から登録する画像領域を抽出する。203は正規化部であり、領域抽出部202で抽出された画像領域の正規化を行う。204は特徴抽出部であり、正規化部203で正規化された画像領域から、画像特徴量を抽出する。
【００２５】
205は画像DB部であり、外部記憶装置106によって構成され、画像領域と画像特徴量を関連付けて記憶する。206は操作部であり、キーボード104、マウス105等で構成され、ユーザからの検索指示等を可能にする。207は距離計算部であり、検索元画像の特徴量と画像DB部205中の検索先画像の特徴量との距離を計算する。208は表示部であり、表示器107から構成され、距離計算部207の結果に基づいて検索候補を表示し、ユーザに提示する。
【００２６】
●画像登録処理
以下、本実施形態における画像登録処理について、図3のフローチャートを用いて説明する。
【００２７】
まず、画像入力部201により登録対象となる画像を入力する(S301)。入力画像としては、登録対象となるクリップアートなどの1枚の画像であってもよいし、文書画像のように複数画像が配置されているものであってもよい。なお、本実施形態では後者の文書画像が入力されたものとして、以降の説明を行う。
【００２８】
次に、領域抽出部202において入力画像に対する領域抽出を行い、登録対象となるクリップアートなどの画像領域を抽出する(S302)。なお、この領域抽出処理の詳細については後述する。
【００２９】
次に、正規化部204において、ステップS302で登録対象として抽出された画像領域を正規化する(S303)。これは例えば、文書画像にクリップアートを貼り付ける際に、回転などの処理が施されていることがあるため、この影響を排除するために行う。なお、この正規化処理の詳細については後述する。
【００３０】
次に、特徴抽出部204において、正規化された画像領域からブロック情報を抽出する(S304)。ブロック情報は、画像特徴量とブロック占有率、ブロック形状情報からなる。画像特徴量としては、ベクトル表現を可能とするものであれば特に限定しないが、ここでは画像上の色の配置を表すカラーラベルであるとする。なお、ブロック占有率、ブロック形状情報については後述する。抽出されたブロック情報は、画像と関連付けられて画像DB部205へ登録される(S305)。なお、カラーラベル抽出処理の詳細、および画像DB部205におけるインデックスの詳細については後述する。
【００３１】
次に、入力画像中の登録対象となる全領域について、ステップS302〜S305の処理を行ったか否かを確認し(S306)、全領域について処理が行われていれば本登録処理を終了するが、未処理の領域が残っていればステップS302へ戻る。
【００３２】
●領域抽出処理(S302)
以下、ステップS302における領域抽出処理について、図4を用いて詳細に説明する。ここで領域抽出処理とは、例えば図4に示すラスタ画像901を、領域分類画像902に示すように意味のあるブロック毎の塊として認識し、各ブロックを属性ごとに分類することによって、それぞれの領域を抽出する処理である。ここでブロック属性としては領域分類画像902に示すように、文字(TEXT)，図画(PICTURE)，写真(PHOTO)，線(LINE)，表(TABLE)、等である。
【００３３】
具体的には、まず入力画像を白黒に二値化し、輪郭線追跡を行って黒画素輪郭で囲まれる画素の塊を抽出する。面積の大きい黒画素の塊については、内部にある白画素に対しても輪郭線追跡を行って白画素の塊を抽出し、さらに一定面積以上の白画素の塊の内部からは再帰的に黒画素の塊を抽出する。
【００３４】
このようにして得られた黒画素の塊を、大きさ及び形状で分類し、異なる属性を持つ領域へ分類していく。例えば、まず縦横比が1に近く、大きさが一定の範囲の領域は文字相当の画素塊とする。そしてさらに、近接する文字が整列良くグループ化可能な部分を文字領域、扁平な画素塊を線領域、一定大きさ以上でかつ矩形の白画素塊を整列よく内包する黒画素塊の占める範囲を表領域とする。また、不定形の画素塊が散在している領域を写真領域、それ以外の任意形状の画素塊を図画領域、と分類する。本実施形態では、例えばクリップアート等、任意形状の図画(PICTURE)領域が登録対象として抽出される。
【００３５】
●正規化処理(S303)
以下、ステップS303における正規化処理について、図5のフローチャートを用いて詳細に説明する。
【００３６】
まずステップS501において、図6に示すように、登録対象である任意形状画像に対して外接矩形を作成する。水平に対して時計回りに0度から80度まで10度ずつ傾けた矩形を、任意形状画像に外接するように配置するようにすることにより、９つの外接矩形を作成する。図6においては、これらの外接矩形のうち、0度および60,70,80度の矩形の例を示す。なお、本実施形態では10度ずつに傾けた９つの外接矩形を作成しているが、本発明は特にこの例に限定されるものではない。
【００３７】
このようにして得られた9種類の外接矩形のうち、面積が最小になる最小外接矩形をステップS502において選択する。図6の例では、80度の外接矩形が最小外接矩形である。
【００３８】
次にステップS503において、最小外接矩形の傾斜角度が0度の場合は任意形状画像に対して手を加えずに処理を終了する。最小外接矩形の傾斜角度が10〜40度の場合はステップS504において、任意形状画像を反時計回りに傾斜角度分回転し、処理を終了する。最小外接矩形の傾斜角度が50〜80度の場合はステップS505において、任意形状画像を時計回りに(90-傾斜角度)分回転し、処理を終了する。
【００３９】
こうして正規化された外接矩形を、以下では正規化外接矩形と呼ぶこととする。また、任意形状の画像の正規化外接矩形における、任意形状の画像の部分を有効領域、それ以外の部分を無効領域と呼ぶこととする。
【００４０】
●画像DB部におけるインデックス
ここで、画像DB部205におけるインデックスについて、詳細に説明する。図7は、画像DB部205におけるインデックスのデータ格納状態を説明する図である。同図において、画像IDは登録順に採番される。また、画像のフルパスのファイル名、ブロック占有率行列、ブロック形状行列、カラーラベル行列は、画像データとして画像IDとともに図7に示されるデータ形態で格納される。なお、ブロック占有率行列、ブロック形状行列およびカラーラベル行列についての詳細は後述する。
【００４１】
●ブロック情報抽出処理(S304)
以下、ステップS304におけるブロック情報抽出処理について、図8のフローチャートを用いて詳細に説明する。
【００４２】
尚、この処理では、処理対象である任意形状の画像の正規化外接矩形を複数のブロックに分割した、各ブロックの色ヒストグラム中の最頻色を有する色のラベルと各ブロックの位置情報を対応づけた情報を、色特徴量(カラーラベル)として抽出する。また、各ブロック内における有効領域の割合を各ブロックの位置情報と対応付けた情報を、ブロック占有率として抽出する。また、各ブロック内における有効領域の近似形状をラベル化して、各ブロックの位置情報と対応付けてブロック形状情報として抽出する。
【００４３】
まずステップS1020において、画像を複数のブロックに分割する。本実施形態では図9に示すように、画像の縦横をそれぞれ9ブロックに分割する。なお本実施形態では、表記の都合上9×9=81ブロックに分割する例を示すが、本発明は特にこの例に限定されるものではない。
【００４４】
次にステップS1030において、処理対象となる着目ブロックを左上端のブロックに設定する。尚、この着目ブロックの設定は、例えば図10に示すように、予め処理順序が決定された順序決定テーブルを参照して行う。
【００４５】
そしてステップS1040において、未処理の着目ブロックの有無を判定する。未処理の着目ブロックがない場合には処理を終了するが、未処理の着目ブロックがある場合にはステップS1050に進む。
【００４６】
ステップS1050では、着目ブロック内の有効領域全画素の各濃度値を、図11に示すような色空間を分割して作成した部分空間である色ビンへ射影し、色ビンに対する色ヒストグラムを生成する。なお本実施形態では図11に示すように、RGB色空間を3×3×3=27に分割した色ビンへ着目ブロックの全画素の濃度値を射影する場合を示すが、本発明は特にこの例に限定されるものではない。
【００４７】
次にステップS1060では、色ヒストグラムの最頻色ビンの色ビンのラベルをその着目ブロックの代表色として決定し、該代表色をその着目ブロックとその位置に対応づけて、RAM103に一時記憶する。
【００４８】
次にステップS1070において、着目ブロックにおける有効領域の割合(％)の1の位を四捨五入して0〜100％まで10％刻みの割合にし、0〜10の11種類のラベルに変換し、着目ブロックとその位置に対応づけてブロック占有率としてRAM103に一時記憶する。なお本実施形態では割合を11段階に分割する例を示すが、本発明はこの例に限定されない。例えば極端な例として、0％とそれ以外もしくは100％とそれ以外の2種類に分割してもよいし、0％と100％とそれ以外の3種類に分割してもよい。また、刻みをより細かくもしくは粗くしてもよいし、刻み幅が均等でなくてもよい。
【００４９】
そしてステップS1080では、着目ブロックにおける有効領域の形状をラベル化し、着目ブロックとその位置に対応付けてブロック形状情報としてRAM103に一時記憶する。形状のラベル化は、図12に示すブロック近似図形(a)〜(j)のいずれに最も似ているかを判断し、それぞれ0から9のラベルを付与することによって行う。なお本実施形態では、近似図形として10種類を用意する例を示したが、本発明はこの例に限定されるものではない。
【００５０】
いずれの形状に最も似ているかの判断手法としては、着目ブロックが有効領域でかつ近似図形が無効領域である領域の面積と、着目ブロックが無効領域でかつ近似図形が有効領域である領域の面積の総和が、最小になる図形を選ぶ手法を用いる。なお、面積を用いずに、各辺における着目ブロックの有効領域の占有率を考慮して決定することもできる。
【００５１】
次にステップS1090では、図10に示す順序決定テーブルを参照して次の処理対象となる着目ブロックを設定する。このとき、RAM103に一時記憶されていた、カラーラベル情報、ブロック占有率情報、およびブロック形状情報が、図7に示すようにブロック情報行列として画像DB部205へ格納される。
【００５２】
その後、ステップS1040に戻り、未処理の着目ブロックがなくなるまで、ステップS1040〜S1080の処理を再帰的に繰り返す。
【００５３】
●類似画像検索処理
以上説明した画像登録処理によって、画像DB部205には図7に示すような形式で複数画像のブロック情報行列が登録されている。
【００５４】
以下、本実施形態の画像処理装置における類似画像の検索処理について、図13のフローチャートを用いて説明する。
【００５５】
まず、検索元画像を指定する(S401)。検索元画像を指定する方法としては例えば、画像DB部205中の画像をランダムに選び出して表示部208に表示し、ユーザがその中から所望する画像に近いものを操作部206により指示して、対応するブロック情報行列を読み出す方法がある。また、ユーザが所望の画像に類似した画像そのものを画像入力部201より入力する方法も有効であるが、この場合、入力された検索元画像についての画像特徴量が、上述した画像登録処理と全く同様なステップで抽出される。
【００５６】
このように指定された検索元画像の特徴量と、画像DB部205に格納されている検索先画像の特徴量との距離を計算することによって、類似画像を検索することができる。しかしながら本実施形態ではこの距離計算に先立って、検索先画像を、検索元画像の特徴量に近い特徴量を有するもののみに絞込む、プリサーチを行うことを特徴とする(S402)。なお、距離計算部207におけるプリサーチ処理の詳細については、後述する。
【００５７】
次に距離計算部207において、プリサーチによって画像DB部205から検索対象として抽出された検索先画像の特徴量と、検索元画像の特徴量との距離を計算し、その計算結果を画像IDと距離のリストとしてRAM103に一時保存する(S403)。なお、距離計算の詳細については後述する。
【００５８】
次に距離計算部207は、前記リストを距離の昇順にソートした後、順に画像IDからインデックス(フルパスのファイル名）を参照して画像DB部205より画像を読み出し、縮小してサムネイル画像を生成する(S404)。
【００５９】
次に表示部208に、検索結果として該サムネイル画像を、算出された距離と共にマトリックス上に並べて表示する(S405)。例えば、第一候補から順に、列の左から右へ、上の列から下の列へ、という風に距離の昇順に並べて表示する。この表示によりユーザは、所望の画像が検索されたかどうかを確認することができる。
【００６０】
●プリサーチ処理(S402)
以下、ステップS402におけるプリサーチ処理について詳細に説明する。
【００６１】
上述したように、画像DB部205に格納されたブロック占有率情報によって、各ブロックが有効領域であるか、無効領域であるか、両方の領域を含むものであるか、を判定することができる。これはすなわち、任意形状画像の(ブロック単位で)おおよその形状を反映したものである。本実施形態ではこのことを利用して、画像DB部205内の検索先画像群を、そのおおよその形状が検索元画像と同じであるもののみに絞り込む。
【００６２】
そこで、まず、検索元画像と全ての検索先画像のブロック占有率行列のみを比較する。比較の方法としては例えば、検索先画像のブロック占有率行列のうち、ブロック内の有効領域が0％のブロックを0、それ以外のブロックを1に変換した上で、検索元画像のブロック占有率行列との論理積をとる方法がある。これにより、検索元画像のブロック占有率行列が変化していなければ、次の距離計算の対象としてRAM103に画像IDを一時保存し、変化していれば、距離計算の対象から外してしまうことができる。なお、これは無効領域が同じである画像に絞り込む方法であるが、逆に、有効領域が同じである画像に絞り込む方法も可能である。いずれにしても、論理積など、演算コストの小さい方法で比較を行うことができるため、全ての検索先画像との比較を行っても、距離計算に比べて極めて高速な演算が可能となる。
【００６３】
●距離計算(S403)
以下、ステップS403における距離計算について詳細に説明する。
【００６４】
本実施形態では、ステップS402のプリサーチで絞り込まれた画像の画像IDを参照して、そのブロック情報占有率行列、ブロック形状行列、ラベル行列(ここではカラーラベル行列)を取得し、検索元画像との距離を式1を使用して求める。
2007034613.tif 000003
…（式1）
【００６５】
式1は、ラベル行列間の距離（最終解）を得るための式である。ここで、Ｄｉｓｔｋは、検索元画像のｋ番目のブロックのラベルと、検索先画像のｋ番目のブロックのラベルとのラベル間の距離である。また、ＷｅｉｇｈｔＰＰｋは、検索元画像のｋ番目のブロック内における有効領域の割合と、検索先画像のｋ番目のブロック内における有効領域の割合に対する重みである。また、ＷｅｉｇｈｔＳＳｋは、検索元画像のｋ番目のブロックのブロック形状と、検索先画像のｋ番目のブロックのブロック形状とのブロック形状の差に対する重みである。
【００６６】
図14は、ラベル行列を比較して距離を求める際に用いる、ラベル間のペナルティマトリックスの一例を示す図である。マトリックス中の値(ペナルティ)が小さい程、ラベルの類似度が高いことを示し、すなわち、ペナルティの値がラベル間の距離を示す。例えば、ラベル2とラベル6のペナルティは"7"である。また、同じラベル同士のペナルティは当然のことながら"0"となっている。本マトリックスの使用目的は、ラベルの類似に応じた距離判定を行うことにある。すなわち本実施形態では、特徴量空間としてRGBカラー空間を用いているので、色の類似度に応じた距離判定が行えることになる。
【００６７】
例えば、検索元画像と検索先画像のラベル行列中において、それぞれ対応する位置（ブロック）のラベル値から、図14のペナルティマトリクスを参照してラベル間の距離を求める。
【００６８】
ブロックの割合に対する重みは、検索元画像のｋ番目のブロック内における有効領域の割合と、検索先画像のｋ番目のブロック内における有効領域の割合の平均を求め、平均値に対しリニアな重みを与えることにより得られる。平均値に対しリニアな重みを与えるとは、すなわち、平均値（０〜１００％）を一次関数で０〜１に変換することである。なお本実施形態においては、ブロック内における有効領域の割合の平均を用いる例を示したが、本発明はこの例に限定されるものではなく、割合の大きい方の値を用いたり、割合の小さいほうの値を用いたり、二乗平均を用いたりしてもよい。また、そのような値を重みに変換するに際し、0％から100％の値に対しリニアな重みを与える例を示したが、本発明はこの例に限定されるものではなく、0％から100％の値に対し二次関数を用いることによって重みに変換してもよい。
【００６９】
ブロック形状の差に対する重み付けは、図15に示すような表を作成することによって行う。図15において、表の縦軸および横軸に記された(a)〜(j)の文字は、図12に示すブロック近似形状(a)〜(j)にそれぞれ対応する。例えば、検索元のブロック形状が(c)であり、検索先のブロック形状が(g)であった場合は、"1.2"倍の重みが乗じられることになる。重みは、ブロック近似形状情報の重なりの面積に応じて決定されている。なお、図15の表に示した重みは一例に過ぎず、本発明はこの例に限定されるものではない。
【００７０】
ここで図16に、ラベル比較の具体例を示す。図16においては、検索元画像のラベル行列が"11231344X"であり、検索先画像のラベル行列が"11322445X"である。なお最後のブロックについては、ブロック占有率行列の値が0(ブロック内全領域が無効領域)であるため、ラベルの値は未定義である。このようなラベル行列に対し、図14に示すペナルティマトリクスおよび式(1)を用いたマッチングを行うことにより、Dist,WeightP,WeightSが定まり、距離(最終解)が求まる。
【００７１】
以上のように本実施形態の距離計算においては、ブロックの近似図形の形状の違いに応じて重みを変えられるよう、図15に示すような重み付けテーブルを導入したことを特徴とする。また、ブロック内における有効領域の割合を距離計算の重みとして使用することを特徴とする。また、ラベル間のパターンマッチングの際に、隣接するセル同士ではペナルティ(距離)を小さくし、遠いものには大きなペナルティを与えるために、図14に示すようなラベル間でのペナルティマトリックスを導入することを特徴とする。
【００７２】
以上説明したように本実施形態によれば、任意形状の画像を検索する際に、ブロック内の有効領域の割合に応じたプリサーチを行うことによって、任意形状画像の高速な検索処理が可能となる。
【００７３】
また、任意形状の画像を検索する際に、ブロック内の有効領域の割合もしくは／および近似形状情報に応じて距離計算の重みを設定することによって、任意形状画像高精度な検索が可能となる。
【００７４】
＜変形例＞
本実施形態のプリサーチ処理においては、検索元画像のブロック占有率行列と全ての検索先画像のブロック占有率行列との比較を行う例を示した。ここで、画像DB部205のインデックスを図17のように構成することによって、更に高速、かつ、少ないメモリ容量で、同様の検索処理を実現することができる。
【００７５】
すなわち、画像登録時に、既に登録済みである画像のブロック占有率行列と、登録対象画像のブロック占有率行列とを前述の方法で比較する。そして、ほぼ同じ形状であると判定できる場合に、そのカラーラベルをひとまとめにして保持しておくことによって、図17に示すようなインデックスが作成される。
【００７６】
図17において、ブロック占有率行列キーとは、ブロック占有率行列の比較の際に用いた、ブロック内の有効領域が0％のブロックを0、それ以外のブロックを1に変換した行列である。そして、同じブロック占有率行列キーとなる画像ID、ブロック占有率行列、カラーラベル行列のセット(以下、ラベル行列群と称する)をひとまとめにして、インデックスとする。
【００７７】
従って検索時には、検索元画像のブロック占有率行列とブロック占有率行列キーの論理積をとり、検索元画像のブロック占有率行列が変化しない場合のみ、対応するラベル行列群をRAM203に読み込むことによって、検索対象画像の絞り込みを行う。そして、RAM203上に絞りこまれたラベル行列群中の画像に対してのみ、距離演算を行うようにする。
【００７８】
このようにすれば、ブロック占有率行列の比較数が少なくなるので、上述した本実施形態で説明した方法よりもさらに高速な処理が可能となる。なお、画像IDとフルパスのファイル名のセットは、別なインデックスとして作成しておき、検索結果を表示する際など、画像ファイル本体を読み出す際には、画像IDに基づいてフルパスファイル名の情報を利用するようにすればよい。もちろん、フルパスファイル名の情報をラベル行列群に含めてもよいが、その場合はメモリの消費量が増えることになる。
【００７９】
また、プリサーチを可能とすることのみを目的とするならば、上述したブロック占有率行列キーのみを使用すればよく、ブロック占有率行列、ブロック形状行列は記録しておく必要がなくなるので、このとき、最も小さなインデックスにより本発明を実現することが可能となる。
【００８０】
また、検索時間が長くなっても構わなければ、プリサーチを行はない公正も可能である。このときは、もちろん、インデックスは図７のようになる。また、画像特徴量の距離計算においては、ブロック占有率とブロック形状情報それぞれから求めた重みの両方を使用したが、検索精度が許容範囲であれば、ブロック占有率から求めた重みのみ、或いは、ブロック形状情報から求めた重みのみを用いても良い。もちろん、ブロック占有率から求めた重みのみ使用する場合は、ブロック形状情報の抽出・記録は必要なく、また、ブロック形状情報から求めた重みのみ使用する場合は、ブロック占有率の抽出・記録は必要ない。
【００８１】
＜他の実施形態＞
以上、実施形態例を詳述したが、本発明は、例えば、システム、装置、方法、プログラム若しくは記憶媒体（記録媒体）等としての実施態様をとることが可能であり、具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００８２】
尚、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図に示すフローチャートに対応したプログラム）を、システムあるいは装置に直接あるいは遠隔から供給し、そのシステムあるいは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００８３】
従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００８４】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、OSに供給するスクリプトデータ等の形態であっても良い。
【００８５】
プログラムを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、MO、CD-ROM、CD-R、CD-RW、磁気テープ、不揮発性のメモリカード、ROM、DVD(DVD-ROM，DVD-R)などがある。
【００８６】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるWWWサーバも、本発明に含まれるものである。
【００８７】
また、本発明のプログラムを暗号化してCD-ROM等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００８８】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているOSなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００８９】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００９０】
【図１】本発明に係る一実施形態における画像処理装置の構成を示すブロック図である。
【図２】本実施形態における画像処理装置の機能構成を示すブロック図である。
【図３】画像登録処理を示すフローチャートである
【図４】領域抽出処理の一例を示す図である。
【図５】画像の正規化処理を示すフローチャートである。
【図６】任意形状に対する外接矩形の作成例を示す図である。
【図７】画像DB部におけるインデックスのデータ格納形式を示す図である。
【図８】ブロック情報抽出処理を示すフローチャートである。
【図９】画像のブロック分割例を示す図である。
【図１０】順序決定テーブルの一例を示す図である。
【図１１】色空間上の色ビンの構成例を示す図である。
【図１２】ブロック近似図形の一例を示す図である。
【図１３】画像検索処理を示すフローチャートである
【図１４】ラベル間におけるペナルティマトリックスの一例を示す図である。
【図１５】ブロック近似図形間の差に対する重み付けテーブルの一例を示す図である。
【図１６】ラベル比較処理の具体例を示す図である。
【図１７】画像DB部におけるインデックスのデータ格納形式を示す図である。
【図１】
2007034613.tif 000004
【図２】
2007034613.tif 000005
【図３】
2007034613.tif 000006
【図４】
2007034613.tif 000007
【図５】
2007034613.tif 000008
【図６】
2007034613.tif 000009
【図７】
2007034613.tif 000010
【図８】
2007034613.tif 000011
【図９】
2007034613.tif 000012
【図１０】
2007034613.tif 000013
【図１１】
2007034613.tif 000014
【図１２】
2007034613.tif 000015
【図１３】
2007034613.tif 000016
【図１４】
2007034613.tif 000017
【図１５】
2007034613.tif 000018
【図１６】
2007034613.tif 000019
【図１７】
2007034613.tif 000020