(57)【要約】  登録画像、検索画像の二値化後の画像から得られる連結領域重心に関して、一方の画像では接触し、かつ、他方の画像では分離している場合には、接触又は分離によって異なる特徴点が抽出されるので、一致する特徴量が得られなかった。  文書画像特徴量生成装置は、入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置であって、統合特徴点抽出手段と、特徴量生成手段とを備える。統合特徴点抽出手段は、入力された入力画像から連結領域を決定し、連結領域の重心と特徴点とを計算すると共に、少なくとも一部の連結領域を統合し、統合された連結領域の重心から統合特徴点を求める。特徴量生成手段は、求められた特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と統合特徴点とから、統合された連結領域の特徴量を生成する。
2008066152.tif 000002
【特許請求の範囲】
【請求項１】
入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置であって、
入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出手段と、
求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成手段と、
を備えることを特徴とする文書画像特徴量生成装置。
【請求項２】
前記特徴量生成手段は、前記統合特徴点と、前記注目特徴点以外の前記特徴点とから前記近傍特徴点を選択し、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１記載の文書画像特徴量生成装置。
【請求項３】
前記特徴量生成手段は、前記統合特徴点と、当該統合特徴点を生成する元となった前記特徴点とが、同時に選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１又は２に記載の文書画像特徴量生成装置。
【請求項４】
前記特徴量生成手段は、前記注目特徴点を生成する元となった前記特徴点を、前記近傍特徴点として選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１乃至３の何れか1項に記載の文書画像特徴量生成装置。
【請求項５】
前記統合特徴点計算手段は、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことを特徴とする請求項１乃至４の何れか1項に記載の文書画像特徴量生成装置。
【請求項６】
前記統合特徴点計算手段は、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことを特徴とする請求項５に記載の文書画像特徴量生成装置。
【請求項７】
前記統合特徴点計算手段は、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことを特徴とする請求項５又は６に記載の文書画像特徴量生成装置。
【請求項８】
請求項１乃至７の何れか1項に記載の文書画像特徴量生成装置を用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行う手段を備える
ことを特徴とする文書画像検索照合装置。
【請求項９】
請求項１乃至７の何れか1項に記載の文書画像特徴量生成装置を用いて生成された前記特徴量を格納する手段を備えることを特徴とする文書画像検索特徴量格納装置。
【請求項１０】
入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成方法であって、
入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出ステップと、
求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成ステップと、
を備えることを特徴とする文書画像特徴量生成方法。
【請求項１１】
前記特徴量生成ステップでは、前記統合特徴点と、前記注目特徴点以外の前記特徴点とから前記近傍特徴点を選択し、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１０記載の文書画像特徴量生成方法。
【請求項１２】
前記特徴量生成ステップでは、前記統合特徴点と、当該統合特徴点を生成する元となった前記特徴点とが、同時に選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１０又は１１に記載の文書画像特徴量生成方法。
【請求項１３】
前記特徴量生成ステップでは、前記注目特徴点を生成する元となった前記特徴点を、前記近傍特徴点として選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことを特徴とする請求項１０乃至１２の何れか1項に記載の文書画像特徴量生成方法。
【請求項１４】
前記統合特徴点計算ステップでは、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことを特徴とする請求項１０乃至１３の何れか1項に記載の文書画像特徴量生成方法。
【請求項１５】
前記統合特徴点計算ステップでは、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことを特徴とする請求項１４に記載の文書画像特徴量生成方法。
【請求項１６】
前記統合特徴点計算ステップでは、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことを特徴とする請求項１４又は１５に記載の文書画像特徴量生成方法。
【請求項１７】
請求項１０乃至１６の何れか1項に記載の文書画像特徴量生成方法を用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行うステップを備える
ことを特徴とする文書画像検索照合方法。
【請求項１８】
請求項１０乃至１６の何れか1項に記載の文書画像特徴量生成方法を用いて生成された前記特徴量を格納するステップを備えることを特徴とする文書画像検索特徴量格納方法。
【請求項１９】
入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成用プログラムであって、
入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出手順と、
求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成手順と、
をコンピュータに実行させることを特徴とする文書画像特徴量生成用プログラム。
【請求項２０】
前記特徴量生成手順では、前記統合特徴点と、前記注目特徴点以外の前記特徴点とから前記近傍特徴点を選択し、前記統合された連結領域の特徴量を生成する
ことをコンピュータに実行させることを特徴とする請求項１９記載の文書画像特徴量生成用プログラム。
【請求項２１】
前記特徴量生成手順では、前記統合特徴点と、当該統合特徴点を生成する元となった前記特徴点とが、同時に選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことをコンピュータに実行させることを特徴とする請求項１９又は２０に記載の文書画像特徴量生成用プログラム。
【請求項２２】
前記特徴量生成手順では、前記注目特徴点を生成する元となった前記特徴点を、前記近傍特徴点として選択されることを排除して、前記統合された連結領域の特徴量を生成する
ことをコンピュータに実行させることを特徴とする請求項１９乃至２１の何れか1項に記載の文書画像特徴量生成用プログラム。
【請求項２３】
前記統合特徴点計算手順では、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことをコンピュータに実行させることを特徴とする請求項１９乃至２２の何れか1項に記載の文書画像特徴量生成用プログラム。
【請求項２４】
前記統合特徴点計算手順では、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことをコンピュータに実行させることを特徴とする請求項２３に記載の文書画像特徴量生成用プログラム。
【請求項２５】
前記統合特徴点計算手順では、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことをコンピュータに実行させることを特徴とする請求項２３又は２４に記載の文書画像特徴量生成用プログラム。
【請求項２６】
請求項１９乃至２５の何れか1項に記載の文書画像特徴量生成用プログラムを用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行う手順をコンピュータに実行させることを特徴とする文書画像検索照合用プログラム。
【請求項２７】
請求項１９乃至２５の何れか1項に記載の文書画像特徴量生成用プログラムを用いて生成された前記特徴量を格納する手順をコンピュータに実行させることを特徴とする文書画像検索特徴量格納用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書画像特徴量生成装置、文書画像特徴量生成方法、文書画像特徴量生成用プログラム、文書画像特徴量格納装置、文書画像特徴量格納方法、文書画像特徴量格納用プログラム、文書画像特徴量照合装置、文書画像特徴量照合方法及び文書画像特徴量照合用プログラムに関し、特に、登録文書画像と検索文書画像の撮像条件の違いによる連結領域の出現の違いがもたらす画像検索又は同定への悪影響を抑制するための文書画像検索特徴量の文書画像特徴量生成装置、文書画像特徴量生成方法、文書画像特徴量生成用プログラム及び前記特徴量を用いた検索もしくは文書画像特徴量格納装置、文書画像特徴量格納方法、及び文書画像特徴量格納用プログラム、前記特徴量を格納する文書画像特徴量照合装置、文書画像特徴量照合方法及び文書画像特徴量照合用プログラムに関する。
【背景技術】
【０００２】
従来、文書や画像を取込み、その文書や画像の特徴量を計算する装置が知られている。また、その装置を用いたシステムの一例が、非特許文献１に記載されている。【０００３】
このシステムは、文書画像検索特徴量生成システムＲを含んだシステムであり、図３１を参照すると、文書画像検索特徴量生成システムＲは、登録画像特徴量計算装置Ｒ１と、検索画像特徴量計算装置Ｒ２と、登録画像特徴量格納装置Ｒ３とを備えている。【０００４】
はじめに、図３２を参照しながら、登録画像特徴量計算装置Ｒ１の構成を説明する。【０００５】
登録画像特徴量計算装置Ｒ１は、特徴点抽出部Ｒ１１と、登録画像特徴量計算部Ｒ１２とを備えている。【０００６】
また、特徴点抽出部Ｒ１１は、二値画像生成部Ｒ１１１と、単語領域計算部Ｒ１１２と、単語重心計算部Ｒ１１３とを備えている。【０００７】
一方、登録画像特徴量計算部Ｒ１２は、注目特徴点設定部Ｒ１２１と、近傍特徴点計算部Ｒ１２２と、近傍特徴点選択部Ｒ１２３と、不変量計算部Ｒ１２４とを備えている。【０００８】
なお、不変量計算部Ｒ１２４は、計算結果を、登録画像特徴量計算装置Ｒ１から出力し、その計算結果が登録画像特徴量格納装置Ｒ３に入力されるようになっている。【０００９】
次に、登録画像が登録画像特徴量計算装置Ｒ１に入力された場合の文書画像特徴量生成システムの動作について、フローチャートを用いて順に説明する。【００１０】
図３３を参照すると、登録画像が登録画像特徴量生成装置Ｒ１に入力されると、まず、特徴点抽出部Ｒ１１は、入力された登録画像から特徴点を抽出（これを特徴点抽出処理と言う。）する（ステップＳＲ１１）。【００１１】
そして、ステップＳＲ１１の特徴点抽出処理によって特徴点が求められると、ステップＳＲ１２へ移動し、登録画像特徴量計算部Ｒ１２（図３２）が、求められた特徴点から特徴量を計算する処理（これを登録画像用特徴量抽出処理と言う。）を行う。【００１２】
このように、登録画像特徴量計算装置Ｒ１は、特徴点抽出処理と登録画像用特徴量抽出処理とを行い、特徴量を生成するようになっている。【００１３】
次に、ステップＳＲ１１の特徴点抽出処理について、図３４に示すフローチャートを用いて、特徴点抽出部Ｒ１１（図３２）の動作を説明する。【００１４】
まず、図３４に示すフローチャートでは、二値画像生成部Ｒ１１１（図３２）が、入力された登録画像に対して、適応二値化を施して二値画像を生成する（ステップＳＲ１１１）。【００１５】
次に、単語領域計算部Ｒ１１２（図３２）では、生成された二値画像に対してガウシアンフィルタを適用した後に、再度、二値化を行うことで登録画像の単語領域を得る（ステップＳＲ１１２）。なお、ステップＳＲ１１２におけるこの処理を、単語領域ラベリング処理という。【００１６】
そして次に、単語重心計算部Ｒ１１３（図３２）が、登録画像の単語領域の重心を求め（これを単語重心計算処理と言う。）、これを特徴点とする（ステップＳＲ１１３）。【００１７】
ステップＳＲ１１３において特徴点が求められた後は、登録画像特徴量計算部Ｒ１２（図３２）が、求められた特徴点から特徴量を計算（上述の登録画像用特徴量抽出処理のこと指す。）を行うようになっている（図３３のステップＳＲ１２）。【００１８】
次に、登録画像特徴量計算部Ｒ１２が、登録画像用特徴量抽出処理を行う処理内容について、図３５に示すフローチャートを用いて説明する。【００１９】
図３５に示すフローチャートを参照すると、登録画像特徴量計算部Ｒ１２（図３２）は、注目特徴点設定部Ｒ１２１（図３２）が、特徴点抽出部Ｒ１１によって計算された特徴点から、ある特徴点を注目特徴点と設定する（ステップＳＲ１２０１）。【００２０】
そして、近傍特徴点計算部Ｒ１２２（図３２）は、その注目特徴点の近傍にあるＮ個の特徴点（これを近傍特徴点と言う。）を選択する（ステップＳＲ１２０２）。【００２１】
次に、Ｎ個の近傍特徴点から選ぶことのできるＭ個の特徴点の組み合わせのすべてに対して特徴ベクトルを計算するようになっており、近傍特徴点選択部Ｒ１２３（図３２）によって、まずＭ個の中から組み合わせの１つの近傍特徴点が選択（ステップＳＲ１２０３）され、不変量計算部Ｒ１２４（図３２）により、特徴量（ベクトル）の計算が行われる（ステップＳＲ１２０４）。【００２２】
ここで、近傍特徴点選択部Ｒ１２３（図３２）は、選択されたＭ個の点に対し、ある注目特徴点を中心として、注目特徴点とその注目特徴点から最も近い特徴点を基準として反時計回りとなるように、Ｍ個の点の順序付けを行う。【００２３】
これにより、不変量計算部Ｒ１２４は、順序付けされたＭ個の点の組み合わせの１つから、１つの特徴ベクトルを計算する。【００２４】
更に詳述すると、不変量計算部Ｒ１２４は、順序付けされたＭ個の点の組み合わせから、選択しうる全てのｆ点の組み合わせの順序を保存して抜き出し、その順序が保存されたｆ個の組み合わせから、予め定められた種類の不変量を、予め決められた方法で、繰り返し計算することによって特徴ベクトルを計算し、格納する。【００２５】
ここで、繰り返し計算する回数は、次式
【数１】
2008066152.tif 000003
によって定義され、（１）式のＭＣｆ回繰り返すことにより、ＭＣｆ次元の特徴ベクトルが１つ生成される。【００２６】
例えば、この順序付けされたＭ個の点の組合せから、特徴ベクトルを計算する具体例を、図３６及び図３７を用いて例示する。【００２７】
図３６は、Ｎ点からＭ点が選択されると共に、Ｍ点からｆ点が選択される様子を表したものである。【００２８】
図３６では、具体例として、Ｎ＝７、Ｍ＝６、ｆ＝４の場合を示しており、図３７では、Ｎ点から選択されたＭ点の組み合わせが、或いは、Ｍ点から選択されたｆ点の組み合わせが、登録画像特徴量計算（ステップＳＲ１２０４）における特徴ベクトルの計算に、どのように利用されるかを示している。【００２９】
図３６及び図３７に示すように、１つの注目特徴点に対して、（１）式で示した、ＭＣｆ（Ｍ点の組み合わせからｆ点の組み合わせを選ぶ全ての組み合わせの数に相当）次元の特徴ベクトルが、ＮＣＭ（Ｎ点の組み合わせからＭ点の組み合わせを選ぶ全ての組み合わせの数に相当）個から、計算されることを示している。【００３０】
つまり、これは、順序付けされた６個の点の組み合わせから、選択しうる全ての４点の組み合わせの順序を保存して抜き出し、その順序が保存された４個の組み合わせから予め定められた種類の不変量を計算し、１５回繰り返すことによって、１５次元の特徴ベクトルが、１つ生成される（図３５のステップＳＲ１２０４）。【００３１】
このように、不変量計算部Ｒ１２４は、ある注目特徴点から、最も近い近傍特徴点により順序付けされたＭ個の点の組み合わせの１つについて、特徴ベクトルを計算する。【００３２】
そして、不変量計算部Ｒ１２４は、この特徴ベクトルの計算を、（１）式で示したＮＣＭの回数である７回繰り返し行うことによって、７個の１５次元の特徴ベクトルを生成する。【００３３】
具体的には、不変量計算部Ｒ１２４は、Ｎ点から選択しうる全てのＭ点の組み合わせについて、ＮＣＭ個（例えば、７個）全てについて、特徴ベクトルの計算が終了したか否か、判定する（図３５のステップＳＲ１２０５）。【００３４】
ここで、Ｍ個全ての近傍特徴点に対して、１つでも特徴ベクトルの計算が終了していない場合には、ステップＳＲ１２０３へ戻り、再び、近傍特徴点選択部Ｒ１２３によって、まだ選択されていない近傍特徴点が選択されると共に、引き続き、計算されていない特徴ベクトルが計算される。【００３５】
一方、不変量計算部Ｒ１２４は、ある注目特徴点に対して、Ｎ点から選択しうる全てのＭ点の組み合わせについて、ＮＣＭ個（例えば、７個）全ての特徴ベクトルの計算が終了した場合には、ステップＳＲ１２０６へ進み、全ての特徴点について特徴ベクトルの計算が終了したか判定する。【００３６】
ここで、全ての特徴点に対して、特徴ベクトルの計算が終了した場合には、登録画像用特徴量抽出処理（図３２のステップＳＲ１２）を終了する。【００３７】
これに対し、まだ全ての特徴点に対して特徴ベクトルの計算が終了していない場合には、ステップＳＲ１２０１に戻り、まだ計算されていない特徴点を注目特徴点として設定されると共に、選択されていない特徴ベクトルが計算されるので、登録画像用特徴量抽出処理において、全ての特徴ベクトルが計算される。【００３８】
これにより、登録画像特徴量計算部Ｒ１２の処理（すなわち図３３の登録画像用特徴量抽出処理のことである。）は、特徴点抽出部Ｒ１１によって抽出された全ての特徴点を注目特徴点として、全ての特徴ベクトルを計算するまで継続される。【００３９】
なお、非特許文献１によれば、特徴量ベクトルの計算がされた後に、ハッシュを用いた特徴量の登録処理が行われるが、本発明が解決したい課題とは無関係であるため省略する。【００４０】
ところで、この不変量計算部Ｒ１２４（図３２）は、Ｍ個から選ばれるｆ個の特徴点のすべてに対して、予め定められた順番でｆ個の特徴点から計算される幾何学的不変量を計算することにより、各幾何学的不変量の値を要素とした特徴量ベクトルを計算する。【００４１】
なお、このｆの値は、利用する幾何学的不変量により異なっている。従って、利用する幾何学的不変量の種類は、システム上、登録画像と検索画像の間で許容したい変換を、予め定めることにより決定されている。【００４２】
例えば、非特許文献１中では、アフィン変換を許容することをあらかじめ想定し、任意の４点の座標から計算されるアフィン不変量を幾何学的不変量として用いているので、ｆ＝４である。また、ＮとＭの値については、Ｎ≧Ｍ≧ｆを満たす任意の値に予め定めておく必要がある。【００４３】
具体的には例えば、非特許文献１中では、（Ｎ，Ｍ）として（１０，１０）、（８，７）などの場合についての結果が報告されている。【００４４】
次に、文書画像検索特徴量生成システムＲの備える検索画像特徴量計算装置Ｒ２について、図３８を参照しながら説明する。図３８は、検索画像特徴量計算装置Ｒ２の構成を示したものである。【００４５】
検索画像特徴量計算装置Ｒ２（図３８）は、特徴点抽出部Ｒ２１と、検索画像特徴量計算部Ｒ２２とを備えている。【００４６】
特徴点抽出部Ｒ２１（図３８）は、二値画像生成部Ｒ２１１と、単語領域計算部Ｒ２１２と、単語重心計算部Ｒ２１３とを備えている。この特徴点抽出部Ｒ２１は、登録画像特徴量計算装置Ｒ１における特徴点抽出部Ｒ１１（図３２）と同一である。【００４７】
一方、特徴量計算部Ｒ２２（図３８）は、注目特徴点設定部Ｒ２２１と、近傍特徴点計算部Ｒ２２２と、近傍特徴点選択部Ｒ２２３と、巡回計算部Ｒ２２４と、不変量計算部Ｒ２２５とを備えている。【００４８】
ここで、注目特徴点設定部Ｒ２２１、近傍特徴点計算部Ｒ２２２、近傍特徴点選択部Ｒ２２３、不変量計算部Ｒ２２５は、それぞれ、登録画像特徴量計算装置Ｒ１（図３２）における特徴点抽出部Ｒ１２１、近傍特徴点計算部Ｒ１２２、近傍特徴点選択部Ｒ１２３、不変量計算部Ｒ１２４と同一である。【００４９】
従って、検索画像特徴量計算装置Ｒ２（図３８）は、登録画像特徴量計算装置Ｒ１に対し、巡回計算部Ｒ２２４を更に備えていることを特徴としている。【００５０】
次に、図３９及び図４０に示すフローチャートを参照して、検索画像特徴量計算装置Ｒ２の動作について説明する。【００５１】
文書画像特徴量生成システムＲは、検索画像特徴量計算装置Ｒ２（図３８）に登録画像が入力されると、まず、特徴点抽出部Ｒ２１が、入力された登録画像から特徴点を抽出する（図３９のステップＳＲ２１）。この場合、特徴点抽出部Ｒ２１（図３８）は、登録画像特徴量計算装置Ｒ１における特徴量抽出部Ｒ１１（図３２）と同じ動作によって特徴点を抽出する。【００５２】
従って、特徴点抽出部Ｒ２１（図３８）は、特徴点抽出部Ｒ１１（図３２）と同じ動作であるので、説明は省略する。【００５３】
特徴点抽出部Ｒ２１（図３８）によって特徴点が求められた後、検索画像特徴量計算装置Ｒ２は、検索画像特徴量計算部Ｒ２２（図３８）が、文書画像検索用特徴量を計算（これを検索画像用特徴量抽出処理と言う。）する（ステップＳＲ２２）。【００５４】
このように、検索画像特徴量計算部Ｒ２２（図３８）の動作は、図３９のフローチャートに示す通り、登録画像特徴量計算部Ｒ１２（図３２）の動作とほぼ同一である。【００５５】
しかしながら、検索画像特徴量計算装置Ｒ２が、登録画像特徴量計算装置Ｒ１に対して異なっている点は、図４０のステップＳＲ２２０４において、近傍特徴点選択部Ｒ２２３（図３８）によって求められた順序つき組み合わせに対して、巡回置換を求めることである。【００５６】
ここで、巡回置換について説明すると、巡回置換とは、元が順序付けられた集合（例えば、｛Ｐ１，Ｐ２，Ｐ３，Ｐ４｝）が与えられたときに、Ｐ１→Ｐ２→Ｐ３→Ｐ４(→Ｐ１)と、元の順番を巡回させるように、元の順番を変更させる（概念的には、それぞれの元をＰ１→Ｐ２→Ｐ３→Ｐ４(→Ｐ１)に従って、ｎ回右へシフトした元に置き換える。）、順序つき集合を得るための置換のことを言う。【００５７】
具体的には例えば、｛Ｐ１，Ｐ２，Ｐ３，Ｐ４｝を、｛Ｐ２，Ｐ３，Ｐ４，Ｐ１｝もしくは、｛Ｐ３，Ｐ４，Ｐ１，Ｐ２｝、或いは｛Ｐ４，Ｐ１，Ｐ２，Ｐ３｝に置換することを巡回置換と言う。【００５８】
これに対し、上記以外の、例えば｛Ｐ１，Ｐ２，Ｐ３，Ｐ４｝を、｛Ｐ１，Ｐ３，Ｐ２，Ｐ４｝や｛Ｐ１，Ｐ４，Ｐ２，Ｐ３｝への置換するものは、本願発明では巡回置換に該当しない。【００５９】
なお、ここでは、近傍特徴点が、元｛Ｐ１，Ｐ２，・・・｝に該当する。【００６０】
このように、ステップＳＲ２２０４で巡回置換を計算すると共に、後段のステップＳＲ２２０５において、ステップＳＲ２２０３で選択されたＭ個の順序つき組み合わせに関する全ての巡回置換の場合について、特徴ベクトルが求められることとなる。【００６１】
そして、ステップＳＲ２２０６において、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了したか判定する。【００６２】
ここで、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了していない場合には、ステップＳＲ２２０４に戻り、まだ計算されていない巡回配置の特徴ベクトルを計算する。【００６３】
一方、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了すると、ステップＳＲ２２０７へ移動し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定する。【００６４】
そして、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了していない場合には、ステップＳＲ２２０３へ戻り、まだ選択されていないＭ点の組み合わせについて、特徴ベクトルを計算する。【００６５】
これに対し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了した場合には、ステップＳＲ２２０８へ移動して、全ての特徴点について、特徴ベクトルの計算が終了したか判定する。【００６６】
従って、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルが計算される。【００６７】
次に、ステップＳＲ２２０８では、全ての特徴点について、特徴ベクトルの計算が終了したか判定するようになっており、全ての特徴点について特徴ベクトルの計算が終了していない場合には、ステップＳＲ２２０１へ戻り、引き続き、まだ計算されていない特徴点を注目特徴点と設定し、特徴ベクトルの計算を行う。【００６８】
これにより、全ての特徴点について、特徴ベクトルの計算を行うことができるようになっている。【００６９】
なお、Ｎ、Ｍ、ｆの値については、非特許文献１では、登録画像特徴量計算部Ｒ１２（図３２）におけるＮ、Ｍ、ｆの値と同一の値を用いることが記載されている。【００７０】
また、登録画像特徴量格納装置Ｒ３（図３１）は、登録画像特徴量計算装置Ｒ１において計算された特徴量（ベクトル）を格納する装置である。【００７１】
このような従来技術では、予め許容すべき定められた幾何学的変換に対する不変量を、特徴量（ベクトル）の要素としている。【００７２】
また、幾何学的変換に対する不変量に関しては、非特許文献２に、射影不変量、アフィン不変量、相似不変量などが説明されている。【００７３】
これにより、例えば、アフィン不変量を特徴ベクトルの要素とした場合には、検索画像と登録画像の間でアフィン変換が生じたとしても、両者から原理上同じ特徴ベクトルが計算できる。【００７４】
すなわち、予め登録画像もしくは検索画像に対して、傾き補正、サイズ補正などの前処理を行うことなく、照合に利用できる特徴ベクトルが生成できる点が利点である。【００７５】
また更に、連結領域におけるラベリングの方法として、ラン解析や境界追跡などの手法について、非特許文献３に記載されている。【００７６】
そして、従来の特徴点を抽出する特徴点抽出方法については、非特許文献４に概略が記載されている。【００７７】
【非特許文献１】中居友弘、外２名、“デジタルカメラを用いた高速文書画像検索におけるアフィン不変量および相似不変量の利用”、電子情報通信学会技術研究報告（パターン認識・メディア理解、ＰＲＭＵ２００５−１８４〜２０１）、２００６年２月１６日、第１０５巻、第６１４号、２５〜３０頁
【非特許文献２】佐藤淳著、“コンピュータビジョン”、コロナ社、１９９９年、５４〜６５頁
【非特許文献３】田村秀行編著、コンピュータ画像処理、オーム社、２００２年、１４９〜１５３頁
【非特許文献４】中居友弘、外２名、“デジタルカメラによる文書画像検索―1万ページから０．１秒で検索する―”、情報科学技術レターズ、２００５年８月、第４巻、１３３〜１３６頁（ＬＩ‐００１）
【発明の開示】
【発明が解決しようとする課題】
【００７８】
しかしながら、非特許文献１乃至４に記載されたものでは、特徴点として二値化後の画像から得られる連結成分の重心のみを用いている。従って、登録画像及び検索画像から決定された本来対応すべき連結領域が、一方で接触し、かつ、他方で分離した場合には、特徴量の計算に用いられる特徴点の配置が、本質的に異なった位置となってしまう。【００７９】
すなわち、スキャナの個体差、撮像条件の違いなどにより、登録画像及び検索画像から決定された本来対応すべき連結領域が、一方の連結領域で接触し、かつ、他方で分離した場合には、一致すべき特徴量が得られないという問題があった。【００８０】
本発明は、上記問題に鑑みてなされたものであり、登録画像及び検索画像の注目連結領域に関して、一方の画像中では接触し、かつ、他方の画像中では分離している場合であっても、対応する特徴量が得られる文書画像特徴量生成装置、文書画像特徴量生成方法、文書画像特徴量生成用プログラム、文書画像特徴量格納装置、文書画像特徴量格納方法、文書画像特徴量格納用プログラム、文書画像特徴量照合装置、文書画像特徴量照合方法及び文書画像特徴量照合用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００８１】
本発明によれば、入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置であって、入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出手段と、求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成手段と、を備えることを特徴とする文書画像特徴量生成装置が提供される。【００８２】
また、本発明によれば、入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成方法であって、入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出ステップと、求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成ステップと、を備えることを特徴とする文書画像特徴量生成方法が提供される。【００８３】
更に、本発明によれば、入力される入力画像から特徴点を抽出し、当該特徴点から特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成用プログラムであって、入力された前記入力画像から連結領域を決定し、前記連結領域の重心と前記特徴点とを計算すると共に、少なくとも一部の前記連結領域を統合し、統合された連結領域の重心から統合特徴点を求める統合特徴点抽出手順と、求められた前記特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点と前記統合特徴点とから、統合された連結領域の特徴量を生成する特徴量生成手順と、をコンピュータに実行させることを特徴とする文書画像特徴量生成用プログラムが提供される。
【発明の効果】
【００８４】
本発明によれば、統合された連結領域に関する重心を特徴点として利用し、特徴量の生成を行っているため、特徴量を計算するための特徴点の配置として、登録画像と検索画像において、ほぼ一致するような特徴点の配置を得ることができる。【００８５】
これにより、登録画像及び検索画像から計算される連結領域に関して、一方の画像で接触し、かつ、他方の画像で分離している場合にも、ほぼ一致する特徴量が生成することができるので、文書画像特徴量生成装置、文書画像特徴量生成方法、文書画像特徴量生成用プログラム、文書画像特徴量格納装置、文書画像特徴量格納方法、文書画像特徴量格納用プログラム、文書画像特徴量照合装置、文書画像特徴量照合方法、及び文書画像特徴量照合用プログラムを実現することができる。
【図面の簡単な説明】
【００８６】
【図１】本発明に係る文書画像検索特徴量生成システムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態に係る登録画像特徴量計算装置の構成を示すブロック図である。
【図３】本発明の第１の実施の形態に係る検索画像特徴量計算装置の構成を示すブロック図である。
【図４】本発明の第１の実施の形態に係る登録画像特徴量計算装置の動作を示すフローチャートである。
【図５】本発明の第１の実施の形態に係る特徴点抽出部の動作を示すフローチャートである。
【図６】本発明の第１の実施の形態に係る統合特徴点計算部の動作を示すフローチャートである。
【図７】本発明の第１の実施の形態に係る登録画像特徴量計算部の動作を示すフローチャートである。
【図８】本発明の第１の実施の形態に係る登録画像特徴量計算部の特徴量追加計算処理を説明するフローチャートである。
【図９】本発明の第１の実施の形態に係る検索画像特徴量計算装置の動作を示すフローチャートである。
【図１０】本発明の第１の実施の形態に係る検索画像特徴量計算部の動作を示すフローチャートである。
【図１１】本発明の第１の実施の形態に係る検索画像特徴量計算部の特徴量追加計算処理を説明するフローチャートである。
【図１２】本発明の第２の実施の形態に係る検索画像特徴量計算装置の構成を示すブロック図である。
【図１３】本発明の第３の実施の形態に係る登録画像特徴量計算装置の構成を示すブロック図である。
【図１４】本発明の第１の実施の形態に係る第１の実施例である文書画像検索特徴量生成システムの構成を示すブロック図である。
【図１５】本発明の第１の実施例における連結領域間の距離について説明するための図である。
【図１６】本発明の第１の実施例における登録画像ＰＲ１Ａを表した図である。
【図１７】本発明の第１の実施例における登録画像ＰＲ１Ａに関する連結領域計算部の計算結果を表した図である。
【図１８】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、特徴点抽出処理の過程を説明するための図である。
【図１９】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、連結領域間の距離を計算するためのフィルタを表した図である。
【図２０】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、連結領域間距離計算処理が終了した時点の特徴点抽出処理の過程を説明するための図である。
【図２１】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、統合特徴点計算処理が終了した時点の特徴点抽出処理の過程を説明するための図である。
【図２２】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、特徴点抽出処理の結果を説明するための図である。
【図２３】本発明の第１の実施例における登録画像特徴量計算部における近傍特徴点選択部及び検索画像特徴量計算部における巡回計算部が計算した順序付き組み合わせと、登録画像特徴量計算部及び検索画像特徴量計算部が生成する特徴量（ベクトル）を計算するにあたり、不変量計算部及び巡回計算部が計算する値と特徴量（ベクトル）の要素番号との関係について説明するための図である。
【図２４】本発明の第１の実施例における登録画像ＰＲ１Ａに関して、登録画像特徴量計算装置による特徴量（ベクトル）生成結果を説明するための図である。
【図２５】本発明の第１の実施例における登録画像ＰＲ２Ａを表した図である。
【図２６】本発明の第１の実施例における登録画像ＰＲ２Ａに関して、登録画像特徴量計算装置による特徴量（ベクトル）生成結果を説明するための図である。
【図２７】本発明の第１の実施例における登録画像ＰＲ１Ｂを表した図である。
【図２８】本発明の第１の実施例における登録画像ＰＲ１Ｂに関して、特徴点抽出処理の結果を説明するための図である。
【図２９】本発明の第１の実施例における特徴量照合装置の動作を示すフローチャートである。
【図３０】本発明の第１の実施例における登録画像ＰＲ１Ｂに関して、検索画像特徴量計算装置による特徴量（ベクトル）生成結果を説明するための図である。
【図３１】従来技術における文書画像検索特徴量生成システムＲの構成を示すブロック図である。
【図３２】従来技術の登録画像特徴量計算装置、特徴点抽出部、及び登録画像特徴量計算部の構成を示すブロック図である。
【図３３】従来技術の登録画像特徴量計算装置の動作を示すフローチャートである。
【図３４】従来技術の特徴点抽出処理の動作を説明するためのフローチャートである。
【図３５】従来技術の登録画像特徴量計算部の登録画像用特徴量抽出処理を説明するためのフローチャートである。
【図３６】従来技術における組み合わせを選択し、説明するための図である。
【図３７】従来技術における７通りの１５次元特徴ベクトルを説明するための図である。
【図３８】従来技術の検索画像特徴量計算装置、特徴点抽出部、及び検索画像特徴量計算部の構成を示すブロック図である。
【図３９】従来技術の検索画像特徴量計算装置の動作を示すフローチャートである。
【図４０】従来技術の検索画像特徴量計算部の動作を説明するためのフローチャートである。
【符号の説明】
【００８７】
Ａ，Ｂ    スキャナ
Ｃ１，Ｃ２  計算機
Ｍ１，Ｍ２  記憶装置
Ｄ，Ｒ  文書画像検索特徴量生成システム
１，Ｒ１  登録画像特徴量計算装置
２，Ｒ２  検索画像特徴量計算装置
３，Ｒ３  登録画像特徴量格納装置
４  特徴量照合装置
５  特徴ベクトル一致数格納装置
６  同定装置
１１，Ｒ１１  登録画像特徴量計算装置における特徴点抽出部
２１，Ｒ２１  検索画像特徴量計算装置における特徴点抽出部
２２，Ｒ２２  検索画像特徴量計算部
１１１，Ｒ１１１  登録画像特徴量計算装置における二値画像生成部
１１２，Ｒ１１２  登録画像特徴量計算装置における連結領域計算部
１１３，Ｒ１１３  登録画像特徴量計算装置における連結領域重心計算部
１１４  登録画像特徴量計算装置における統合特徴点計算部
１２，Ｒ１２  登録画像特徴量計算部
１２１，Ｒ１２１  登録画像特徴量計算部における注目特徴点設定部
１２２，Ｒ１２２  登録画像特徴量計算部における近傍特徴点計算部
１２３，Ｒ１２３  登録画像特徴量計算部における注目特徴点選択部
１２４，Ｒ１２４  登録画像特徴量計算部における不変量計算部
１２５  登録画像特徴量計算部における巡回計算部
２１１，Ｒ２１１  検索画像特徴量計算装置における二値画像生成部
２１２，Ｒ２１２  検索画像特徴量計算装置における連結領域計算部
２１３，Ｒ２１３  検索画像特徴量計算装置における連結領域重心計算部
２１４  検索画像特徴量計算装置における統合特徴点計算部
２２１，Ｒ２２１  検索画像特徴量計算部における注目特徴点設定部
２２２，Ｒ２２２  検索画像特徴量計算部における近傍特徴点計算部
２２３，Ｒ２２３  検索画像特徴量計算部における注目特徴点選択部
２２４，Ｒ２２４  検索画像特徴量計算部における巡回計算部
２２５，Ｒ２２５  検索画像特徴量計算部における不変量計算部
【発明を実施するための最良の形態】
【００８８】
次に、発明を実施するための最良の形態について、図面を参照して詳細に説明する。【００８９】
（第１の実施の形態）
（１）文書画像検索特徴量生成システムＤの全体構成
図１を参照すると、本発明の第１の実施の形態では、登録画像特徴量計算装置１と、検索画像特徴量計算装置２と、登録画像特徴量格納装置３とを備えている。【００９０】
（１−１）登録画像特徴量計算装置１の回路構成【００９１】
図２を参照すると、登録画像特徴量計算装置１は、特徴点抽出部１１と、登録画像特徴量計算部１２とを備えている。【００９２】
特徴点抽出部１１は、二値画像生成部１１１と、連結領域計算部１１２と、連結領域重心計算部１１３と、統合特徴点計算部１１４とを備えている。【００９３】
二値画像生成部１１１では、入力された、ある画像から二値画像を生成する。【００９４】
具体的には例えば、入力画像がグレースケール画像である場合には、予め定められた閾値による二値化、適応二値化など、予め定めた範囲の画素値の画素と、それ以外の範囲の画素値の画素とで二値化を行うなど、既存の二値化手法を用いる。【００９５】
一方、入力がカラー画像である場合には、グレースケールに既存の手法で変換した後に、グレースケール画像に対する二値化を行うことができる、また、入力画像がカラー画像の場合であれば、画素値の色空間の分布を求めた後に、色空間をクラスタリングし、１つ以上のクラスタリング領域とそれ以外の領域とで二値化する方法であっても良い。【００９６】
連結領域計算部１１２では、二値画像生成部１１１により生成された二値画像が入力されると、連結領域ラベリングを行う。この第１の実施の形態では、連結領域ラベリングを行うにあたっては、非特許文献３で記載されているような、ラン解析や境界追跡などの既存の手法を用いてラベリングを行うこととする。【００９７】
但し、連結領域ラベリングは、ラン解析や境界追跡に限定されるものではなく、入力された二値画像に対し、同じ連結領域に属する画素には同じラベルを付け、異なる連結領域に属する画素には、異なるラベルを付けるようにさえすれば良い。【００９８】
また、非特許文献１に記載されているように、連結領域ラベリングを行う前に既存の画像処理手法などを行い、単語領域に相当する領域を得るようにしても良い。【００９９】
連結領域重心計算部１１３では、連結領域計算部１１２により計算された同一ラベルに属する画素集合の重心を計算し、特徴点とする。【０１００】
統合特徴点計算部１１４では、異なるラベル付けをされた複数領域を選択し、それらの連結領域から計算された特徴点（以下、被統合特徴点と呼ぶ）、及び当該連結領域の画素数から、異なるラベル付けがされた連結領域の複数選択領域を統合して得られる新しい特徴点（以下、統合特徴点と呼ぶ。）と画素数を求める。【０１０１】
ここで、統合する連結領域を決定するには、互いの連結領域が近い位置にある連結領域集合を選ぶと良い。そして、互いの連結領域が近い位置にあるか判定するためには、重心間の距離、当該ラベルに属する連結領域の中で異なるラベルに属する連結領域までの距離の最小値、などを近さの尺度として、予め定められた値以下の近さの場合に、統合すべき連結領域であると決定する。【０１０２】
このように、特徴点抽出部１１では、二値画像生成部１１１と、連結領域計算部１１２と、連結領域重心計算部１１３と、統合特徴点計算部１１４とを備えることにより、入力される入力画像から、特徴点を抽出する機能を持つ。【０１０３】
次に、登録画像特徴量計算部１２について説明する。【０１０４】
登録画像特徴量計算部１２は、注目特徴点設定部１２１と、近傍特徴点計算部１２２と、近傍特徴点選択部１２３と、不変量計算部１２４とを備えている。【０１０５】
注目特徴点設定部１２１では、特徴量算出を行うにあたり、注目すべき特徴点（これを注目特徴点と言う。）を１つ設定する。【０１０６】
近傍特徴点計算部１２２では、注目特徴点の近傍にある、予め定められた個数（Ｎ個とする。）の特徴点を計算し、出力する。【０１０７】
近傍特徴点選択部１２３は、近傍特徴点計算部１２２で計算された近傍特徴点から、予め定められた個数の特徴点（Ｍ個とする。）を選択する。このとき、統合特徴点と、その統合特徴点を生成する元となった特徴点とを、同時に選ばないように選択するものとする。【０１０８】
また、選択された特徴点は、注目特徴点を中心として、注目特徴点と選択された特徴点のうち注目特徴点にもっとも近い特徴点を結ぶ半直線を基準として、時計回り、または反時計回り、いずれかの予め定められた方向に順序付けする。【０１０９】
不変量計算部１２４は、近傍特徴点選択部１２３によって選択された特徴点集合から、予め定められた順序で要素となる幾何学的不変量を格納することにより、特徴量（ベクトル）を生成する。【０１１０】
このとき、特徴量（ベクトル）の各要素は、予め定められた幾何学的不変量とする。この幾何学的不変量には、非特許文献２に記載されているように、相似不変量、アフィン不変量、射影不変量などがある。なお、この特徴ベクトルの格納先は、登録画像特徴量格納装置３である。【０１１１】
このように、登録画像特徴量計算部１２では、注目特徴点設定部１２１と、近傍特徴点計算部１２２と、近傍特徴点選択部１２３と、不変量計算部１２４とを備えることにより、特徴点抽出部１１から出力された特徴点と連結領域画素数とを利用して、特徴量（ベクトル）を計算し、登録画像特徴量格納装置３に格納する。【０１１２】
次に、検索画像特徴量計算装置２について、図３を参照して説明する。【０１１３】
（１−２）検索画像特徴量計算装置２の回路構成【０１１４】
図３を参照すると、検索画像特徴量計算装置２は、特徴点抽出部２１と、検索画像特徴量計算部２２とを備えている。【０１１５】
特徴量抽出部２１は、二値画像生成部２１１と、連結領域生成部２１２と、連結領域重心計算部２１３と、統合特徴点計算部２１４とを備えている。【０１１６】
検索画像特徴量計算装置２における特徴点抽出部２１は、登録画像特徴量計算装置１における特徴点抽出部１１と同じ構成であるので、詳細は省略する。【０１１７】
次に、検索画像特徴量計算部２２について説明する。【０１１８】
検索画像特徴量計算部２２は、注目特徴点設定部２２１と、近傍特徴点計算部２２２と、近傍特徴点選択部２２３と、巡回計算部２２４と、不変量計算部２２５とを備えている。【０１１９】
検索画像特徴量計算部２２における、注目特徴点設定部２２１、近傍特徴点計算部２２２、近傍特徴点選択部２２３は、それぞれ、登録画像特徴量計算部１２（図２）における注目特徴点設定部１２１、近傍特徴点計算部１２２、近傍特徴点選択部１２３と同じ構成であるので、詳細は省略する。【０１２０】
巡回計算部２２４は、近傍特徴点選択部２２３が出力した順序付き特徴点集合を入力として、特徴点集合の順序を巡回することによって変更を行う。【０１２１】
検索画像特徴量計算装置２における不変量計算部２２５は、登録画像特徴量計算部１２（図２）における不変量計算部１２４と同じであるので、詳細は省略する。【０１２２】
従って、検索画像特徴量計算部２２は、特徴点抽出部２１から出力された特徴点と、連結領域画素数とを利用して、特徴量（ベクトル）を計算する。【０１２３】
また、登録画像特徴量計算装置３（図１）は、上述のように登録画像特徴量計算装置１が生成した特徴量（ベクトル）と、連結領域画素数とを格納する装置である。【０１２４】
（２）文書画像検索特徴量生成システムＤの処理手順
（２−１）登録画像特徴量計算装置１の処理手順【０１２５】
次に、第１の実施の形態における全体の動作について、図４乃至図１１のフローチャートを用いて、順番に詳細に説明する。【０１２６】
まず、図４に示すフローチャートを参照すると、文書画像検索特徴量生成システムＤは、登録画像特徴量計算装置１に多値画像が入力されると、登録画像特徴量計算装置１（図２）の特徴量抽出部１１が、特徴点抽出処理を行う（ステップＳ１１）。【０１２７】
そして、特徴量抽出部１１の特徴点抽出処理が終了すると、次に登録画像特徴量計算部１２（図２）が、登録画像特徴量計算処理を行う（ステップＳ１２）。【０１２８】
ここで、特徴点抽出処理（ステップＳ１１）及び登録画像用特徴量計算処理（ステップＳ１２）の処理内容について、更にフローチャートを用いて詳細に説明する。【０１２９】
図５のフローチャートは、ステップＳ１１における特徴点抽出処理について示したものである。【０１３０】
まず、登録画像特徴量計算装置１（図２）の二値画像生成部１１１が、二値画像を生成する（ステップＳ１１１）。【０１３１】
次に、連結領域生成部１１２（図２）が、連結領域ラベリングを行う（ステップＳ１１２）。この第１の実施の形態では、生成された二値画像に対して、例えば、非特許文献３に記載されている、４連結のラン解析によるラベリング処理を行うこととする。【０１３２】
そして、連結領域重心計算部１１３が、各連結領域に対して、重心位置と画素数とを計算する（ステップＳ１１３）。【０１３３】
続いて、統合特徴点計算部１１４が、互いに近傍にある特徴点から統合特徴点を求め、かつ、統合した連結領域の画素数を求める（ステップＳ１１４）。この近傍を定める基準として用いる距離尺度は、特徴点間のユークリッド距離、市街地距離など、既存の距離尺度を用いることができる。【０１３４】
ここで、例えば、互いに近傍にあるかどうかを判定するためには、連結領域間の距離が閾値ＴＨ１を超えないようにする方法がある。このＴＨ１は、予め定められた値を使っても良いし、行切り出しを行ってベースラインを求めた後に、連結成分をそのベースライン上に投影して求められる連結成分の幅を求めて、その値でＴＨ１を割るなど正規化を行っても良い。【０１３５】
統合特徴点計算部１１４が、この連結領域の大きさを求める処理（これを統合特徴点計算処理と言う。）について、図６のフローチャートを用いて説明する。図６を参照すると、統合特徴点計算部１１４の動作は、概略次の通りである。【０１３６】
まず、統合特徴点計算部１１４は、連結領域ラベリング画像に対して、各連結領域間の距離を求める（これを連結領域間距離計算処理と言う。）（ステップＳ１１４１）。【０１３７】
ここで、この距離の尺度には、ユークリッド距離、市街地距離など既存の距離尺度を用いる。また、連結領域間の距離は、重心間の距離によって求められる。【０１３８】
更に、連結領域間の距離を定義する別の方法としては、連結領域ＣＣ１の任意の画像と、別の連結領域ＣＣ２の任意の画素とにおける距離尺度ｄの最小値は、次式
【数２】
2008066152.tif 000004
のように定義することもできる。【０１３９】
次に、被統合特徴点を決定し、統合特徴点の重心を計算し、統合される連結領域の画素数の和を計算し、統合特徴点に対応する画素数とする（ステップＳ１１４２）。【０１４０】
この場合、例えば、任意の連結領域対を統合する方式や距離Ｄ以下の連結領域対を統合する方式などによって、２つの連結領域を統合する方式がある。【０１４１】
または、任意の３つ以上の連結領域を統合すること方式も適用可能である。更に、単に距離Ｄ以下の連結領域同士を統合する場合は、例えば、連結成分１と連結成分２の距離がＤ以下、連結成分２と連結成分３の距離がＤ以下の場合に、３つの連結領域を統合するようにすることもできる。【０１４２】
同様にすれば、予め定められた個数Ａ個までの連結領域を統合することが可能である。また、ここでは、Ａの値は予め定めておくものとする。【０１４３】
このように、登録画像特徴量計算装置１の特徴点抽出部１１は、ステップＳ１１の特徴点抽出処理（図４）により、特徴点と、統合特徴点と、各連結領域に対応する画素数を計算することができる。【０１４４】
また、図４のフローチャートのステップＳ１１における特徴点抽出処理が、特徴量抽出部１１によって特徴点抽出処理が終了すると、登録画像特徴量計算部１２によって、ステップＳ１２の登録画像用特徴量抽出処理が行われる（図４のステップＳ１２）。【０１４５】
次に、この登録画像用特徴量抽出処理（図４のステップＳ１２）の処理内容について、更に図７のフローチャートを参照しながら、登録画像特徴量計算部１２の動作を説明する。【０１４６】
なお、背景技術と重複する処理内容については、処理内容を理解する際に必要な概略動作を説明する。【０１４７】
最初に、登録画像特徴量計算部１２に備えられた注目特徴点設定部１２１（図２）が、ある特徴点を注目特徴点と設定する（ステップＳ１２０１）。【０１４８】
次に、近傍特徴点計算部１２２は、注目特徴点が統合特徴点であるかどうかを判定する（ステップＳ１２０２）。【０１４９】
ここで、設定された注目特徴点が統合特徴点である場合には、ステップＳ１２１０以下の処理を行い、一方、設定された注目特徴点が統合特徴点でない場合には、ステップＳ１２０３以下の処理を行う。【０１５０】
まず、設定された注目特徴点が統合特徴点でない場合には、ステップＳ１２０３へ進み、近傍特徴点計算部１２２は、注目特徴点と統合特徴点を除いた特徴点のうち距離の近い方からＮ個の特徴点を選択する（ステップＳ１２０３）。【０１５１】
次に、近傍特徴点選択部１２３は、Ｎ個の特徴点からＭ個の特徴点を選択する組み合わせを求め、１つを選択する（ステップＳ１２０４）。このときＭ個の特徴点は、前述の通り、適切に順序付けするものとする。【０１５２】
そして、不変量計算部１２４が、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番に要素が格納される（ステップＳ１２０５）。【０１５３】
図７に示すステップＳ１２０４からステップＳ１２０５までの処理は、ステップＳ１２０３で選択されたＮ点から選択しうる、全てのＭ点の組み合わせについて行う。【０１５４】
そして、ステップＳ１２０６において、Ｎ点から選択しうる全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定するようになっている。【０１５５】
ここで、Ｍ点（Ｍ個）全ての近傍特徴点に対して、１個でも特徴ベクトルの計算が終了していない場合には、ステップＳ１２０４へ戻り、まだ計算されていない特徴ベクトルの近傍特徴点が選択されると共に、引き続き、特徴ベクトルの計算を行う。【０１５６】
これにより、Ｎ点から選択しうる全てのＭ点の組み合わせについて、特徴ベクトルが計算されるようになっている。【０１５７】
次に、ステップＳ１２０３にて選択したＮ個の特徴点のうち、ある統合特徴点を生成した特徴点集合の全てが含まれているかどうかを判定する（ステップＳ１２０７）。【０１５８】
ここで、もし、ある統合特徴点を生成した特徴点集合の全てが存在していれば、特徴量追加計算処理が行われる（ステップＳ１２０８）。【０１５９】
これに対し、ある統合特徴点を生成した特徴点集合の全てが含まれていなければ、ステップＳ１２０９へ進む。【０１６０】
このステップＳ１２０８における特徴量追加計算処理については、図８のフローチャートを用いて後述する。【０１６１】
また、ステップＳ１２０９へ進んだ後は、すべての特徴点において、特徴量の計算が終了したか否か判定するようになっており、すべての特徴点において特徴量の計算が終了した場合には、登録画像用特徴量抽出処理（図４のステップＳ１２）は終了する。【０１６２】
一方、ステップＳ１２０９において、まだ全ての特徴点の特徴量の計算が終了していない場合には、ステップＳ１２０１へ戻り、まだ計算されていない特徴点を注目特徴点として、特徴ベクトルを計算するようになっている。【０１６３】
また、ステップＳ１２０２において、設定した注目特徴点が統合特徴点であった場合には、ステップＳ１２１０へ進み、次のような動作となる。【０１６４】
近傍特徴点計算部１２２（図２）は、注目特徴点と、注目特徴点を生成した被統合特徴点と、統合特徴点とを除いた特徴点のうち、距離の近い方からＮ個の特徴点を選択する（ステップＳ１２１０）。【０１６５】
次に、近傍特徴点選択部１２３は、Ｎ個の特徴点からＭ個の特徴点を選択する組み合わせを求め、１つを選択する（ステップＳ１２１１）。このときＭ個の特徴点は、前述の通り、適切に順序付けするものとする。【０１６６】
次に、不変量計算部１２４が、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番に要素が格納される（ステップＳ１２１２）。【０１６７】
ステップＳ１２１１からステップＳ１２１２までの処理は、ステップＳ１２１０で選択されたＮ点から選択しうる、全てのＭ点の組み合わせについて行う。【０１６８】
そして、ステップＳ１２１３において、Ｎ点から選択しうる全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定するようになっている。【０１６９】
ここで、Ｍ点（Ｍ個）全ての近傍特徴点に対して、１個でも特徴ベクトルの計算が終了していない場合には、ステップＳ１２１１へ戻り、まだ計算されていない特徴ベクトルの近傍特徴点が選択されると共に、引き続き、特徴ベクトルの計算を行うようになっている。【０１７０】
このように、Ｎ点から選択しうる全てのＭ点の組み合わせについて、特徴ベクトルが計算される。【０１７１】
次に、ステップＳ１２１４において、選択したＮ個の特徴点のうち、ある統合特徴点を生成した特徴点集合の全てが含まれているかどうかを判定する（ステップＳ１２１４）。【０１７２】
ここで、もし、ある統合特徴点を生成した特徴点集合の全てが存在すれば、特徴量追加計算処理が行われる（ステップＳ１２１５）。【０１７３】
これに対し、ある統合特徴点を生成した特徴点集合の全てが含まれていなければ、ステップＳ１２０９へ進む。【０１７４】
この特徴点追加計算処理（ステップＳ１２１５）の処理内容は、ステップＳ１２０８と同じであり、後述する。そして、特徴点追加計算処理（ステップＳ１２１５）の終了後、ステップＳ１２０９へ進む。【０１７５】
最後に、ステップＳ１２０９において、すべての特徴点を注目特徴点として処理を行ったかどうかの判定を行う。ここでは、上述と同様に、すべての特徴点を注目特徴点として処理が行われていなければステップＳ１２０１へ戻り、一方、すべての特徴点を注目特徴点として特徴ベクトルを計算する処理が行われていれば、登録画像用特徴量抽出処理（図４のステップＳ１２）を終了する。【０１７６】
（２−２）登録画像特徴量計算装置１における特徴量追加計算処理手順【０１７７】
ここで、上述のステップＳ１２０８又はＳ１２１５における特徴量追加計算処理手順について、図８のフローチャートを用いて説明する。【０１７８】
まず、登録画像特徴量計算部１２の近傍特徴点選択部１２３（図２）は、近傍特徴点計算部１２２により計算されたＮ個の近傍特徴点から、ある統合特徴点を生成した被統合特徴点を削除し、代わりにそれらの被統合特徴点から計算された統合特徴点を加える（ステップＳ１２０８１）。また、このときの近傍特徴点の合計数をＮ’個とする。【０１７９】
もし、Ｎ’≧Ｍであれば、ステップＳ１２０８３へ進み、これに対し、Ｎ’＜Ｍであれば、ステップＳ１２０８１へ戻る。【０１８０】
ステップＳ１２０８３では、近傍特徴点選択部１２３が、Ｎ’個の特徴点からＭ個の特徴点を選択する組み合わせの１つを求める。このとき、ステップＳ１２０４（図７）と同様に、適切な順序付けを行うものとする。【０１８１】
続いて、不変量計算部１２４が、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番により、要素を格納する（ステップＳ１２０８４）。【０１８２】
ステップＳ１２０８３からステップＳ１２０８４までの処理は、Ｎ’個の特徴点からＭ個の特徴点を選択する組み合わせのすべてについて処理が行われるまで繰り返される。【０１８３】
そして、ステップＳ１２０８５において、Ｎ’点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定するようになっている。【０１８４】
ここで、Ｍ点（Ｍ個）全ての近傍特徴点に対して、１個でも特徴ベクトルの計算が終了していない場合には、ステップＳ１２０８３へ戻り、まだ計算されていない特徴ベクトルの近傍特徴点が選択されると共に、引き続き、まだ計算されていない特徴ベクトルの計算を行う。【０１８５】
これにより、Ｎ’点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルが計算される。【０１８６】
また、ステップＳ１２０８６では、近傍特徴点の中に含まれ、ある統合特徴点を生成した全ての被特徴点集合に対して、特徴ベクトルの計算が終了したか否か判定するようになっている。【０１８７】
ここで、近傍特徴点の中に含まれ、ある統合特徴点を生成した全ての被特徴点集合に対して、特徴ベクトルの計算が終了していない場合には、ステップＳ１２０８１へ戻り、まだ計算されていない特徴点集合に対して、引き続き、特徴ベクトルの計算を行う。【０１８８】
これにより、ステップＳ１２０８又はＳ１２１５における特徴量追加計算処理は、近傍特徴点計算部１２２によって計算されたＮ’個の特徴点中に含まれる統合特徴点について、特徴量追加計算の処理が行われるまで繰り返され、全ての特徴ベクトルを計算するようになっている。【０１８９】
このように、近傍特徴点の中に含まれ、ある統合特徴点を生成した、全ての被特徴点集合に対して、繰り返し不変量を計算するようになっていると共に、繰り返し処理が終了した後にステップＳ１２０９へ進む。【０１９０】
（２−３）検索画像特徴量計算装置２の処理手順【０１９１】
次に、検索画像特徴量計算装置２の動作について説明する。なおこの動作は、登録画像特徴量計算装置１の動作と同一の動作が多いので、登録画像特徴量計算装置１の動作と異なる点について、特に詳細に説明する。【０１９２】
図９に示すフローチャートを参照すると、まず、文書画像検索特徴量生成システムＤは、検索画像特徴量計算装置２に多値画像が入力されると、特徴量抽出部２１（図３）が、特徴点抽出処理を行う（ステップＳ２１）。【０１９３】
これは、登録画像特徴量計算装置１の動作における特徴点抽出処理（図４のステップＳ１１）と全く同一の処理である。【０１９４】
特徴点抽出処理（図４のステップＳ２１）が終了すると、検索画像特徴量計算部２２が、検索画像特徴量計算処理を行う（ステップＳ２２）。【０１９５】
ここで、図１０のフローチャートを参照しながら、検索画像特徴量計算部２２の検索画像特徴量計算処理（ステップＳ２２）の処理内容について説明する。【０１９６】
最初に、検索画像特徴量計算部２２に備えられた注目特徴点設定部２２１（図３）が、ある特徴点を注目特徴点と設定する（ステップＳ２２０１）。【０１９７】
次に、近傍特徴点計算部２２２は、注目特徴点が統合特徴点であるかどうかを判定する（ステップＳ２２０２）。【０１９８】
ここで、設定された注目特徴点が統合特徴点である場合には、ステップＳ２２１２以下の処理を行い、設定された注目特徴点が統合特徴点でない場合には、ステップＳ２２０３以下の処理を行う。【０１９９】
まず、設定された注目特徴点が統合特徴点でない場合には、ステップＳ２２０３へ進み、近傍特徴点計算部２２２は、注目特徴点と、統合特徴点とを除いた特徴点のうち、距離の近い方からＮ個の特徴点を選択する（ステップＳ２２０３）。【０２００】
次に、近傍特徴点選択部２２３（図３）は、Ｎ個の特徴点からＭ個の特徴点を選択する組み合わせを求め、１つを選択する（ステップＳ２２０４）。このときＭ個の特徴点は、前述の通り、適切に順序付けするものとする。【０２０１】
そして、近傍特徴点選択部２２３は、Ｍ個の順序付き組み合わせから、巡回置換の１つを計算する（ステップＳ２２０５）。【０２０２】
次に、不変量計算部２２５は、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番に要素を格納する（ステップＳ２２０６）。【０２０３】
ステップＳ２２０５からステップＳ２２０６までの処理は、Ｍ点から計算されるすべての巡回置換組み合わせについて行う。【０２０４】
また、ステップＳ２２０７において、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了したか判定するようになっている。【０２０５】
ここで、Ｍ点（Ｍ個）全ての近傍特徴点に対して、１個でも巡回配置の特徴ベクトルの計算が終了していない場合には、ステップＳ２２０５へ戻り、まだ計算されていない巡回配置の特徴ベクトルについて、特徴ベクトルの計算を行う。【０２０６】
一方、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了すると、ステップＳ２２０８へ移動し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定するようになっている。【０２０７】
ここで、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了していない場合には、ステップＳ２２０４へ戻り、まだ選択されていないＭ点の組み合わせについて、特徴ベクトルを計算する。【０２０８】
これに対し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了した場合には、ステップＳ２２０９へ移動する。【０２０９】
次に、ステップＳ２２０３にて選択したＮ個の特徴点のうち、ある統合特徴点を生成した特徴点集合の全てが含まれているかどうかを判定する（ステップＳ２２０９）。【０２１０】
ここで、もし、ある統合特徴点を生成した特徴点集合の全てが存在すれば、特徴量追加計算処理が行われる（ステップＳ２２１０）。【０２１１】
これに対し、ある統合特徴点を生成した特徴点集合の全てが含まれていなければ、ステップＳ２２１１へ進む。【０２１２】
このステップＳ２２１０における特徴量追加計算処理については、図１１のフローチャートを用いて後述する。【０２１３】
また、ステップＳ２２１１へ進んだ後は、すべての特徴点において、特徴量の計算が終了したか否か判定するようになっており、すべての特徴点において特徴量の計算が終了した場合には、検索画像用特徴量抽出処理（ステップＳ２２）は終了する。【０２１４】
一方、ステップＳ２２１１において、まだすべての特徴点の特徴量の計算が終了していない場合には、ステップＳ２２０１へ戻り、まだ計算されていない特徴点を注目特徴点として、特徴ベクトルを計算する。【０２１５】
また、ステップＳ２２０２において、設定した注目特徴点が統合特徴点であった場合には、ステップＳ２２１２へ進み、次のような動作となる。【０２１６】
検索画像特徴量計算部２２に備えられた近傍特徴点計算部２２２（図３）は、注目特徴点と、注目特徴点を生成した被統合特徴点と、統合特徴点とを除いた特徴点のうち、距離の近い方からＮ個の特徴点を選択する（ステップＳ２２１２）。【０２１７】
次に、近傍特徴点選択部２２３（図３）は、Ｎ個の特徴点からＭ個の特徴点を選択する組み合わせを求め、１つを選択する（ステップＳ２２１３）。このときＭ個の特徴点は、前述の通り、適切に順序付けするものとする。【０２１８】
次に、近傍特徴点選択部２２３（図３）が、Ｍ個の順序付き組み合わせから、巡回置換の１つを計算する（ステップＳ２２１４）。【０２１９】
そして、次に、不変量計算部２２４が、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番に要素が格納される（ステップＳ２２１５）。【０２２０】
ステップＳ２２１４からステップＳ２２１５までの処理は、Ｍ点から計算される全ての巡回置換の組み合わせについて行う。【０２２１】
そして、ステップＳ２２１６において、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了したかを判定する。【０２２２】
ここで、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了していない場合には、ステップＳ２２１４に戻り、まだ計算されていない巡回配置の特徴ベクトルを計算する。【０２２３】
一方、Ｍ点全ての巡回配置の特徴ベクトルの計算が終了すると、ステップＳ２２１７へ移動し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定する。【０２２４】
そして、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了していない場合には、ステップＳ２２１３へ戻り、まだ選択されていないＭ点の組み合わせについて、特徴ベクトルを計算する。【０２２５】
これに対し、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了した場合には、ステップＳ２２１８へ移動する。【０２２６】
また、ステップＳ２２１２において選択されたＮ個の特徴点のうち、ある統合特徴点を生成した特徴点集合の全てが含まれているかどうかを判定する（ステップＳ２２１８）。【０２２７】
ここで、もし、ある統合特徴点を生成した特徴点集合の全てが存在すれば、特徴量追加計算処理（ステップＳ２２１９）が行われる（ステップＳ２２１９）。【０２２８】
これに対し、ある統合特徴点を生成した特徴点集合の全てが含まれていなければ、ステップＳ２２１１へ進む。【０２２９】
特徴点追加計算処理（ステップＳ２２１９）の処理内容は、ステップＳ２２１０と同じであるため、特徴点追加計算処理として後述する。そして、特徴点追加計算処理の終了後、ステップＳ２２１１へ進む。【０２３０】
最後に、ステップＳ２２１１において、すべての特徴点を注目特徴点として処理を行ったかどうかの判定を行う。【０２３１】
ここでは、登録画像特徴量計算装置１と同様に、すべての特徴点を注目特徴点として処理が行われていなければステップＳ２２０１へ戻り、これに対し、全ての特徴点を注目特徴点として特徴ベクトルを計算する処理が行われていれば、検索画像用特徴量抽出処理（図９のステップＳ２２）を終了する。【０２３２】
（２−４）検索画像特徴量計算装置２における特徴量追加計算処理手順【０２３３】
ここで、上述のステップＳ２２１０又はＳ２２１９における特徴量追加計算処理手順について、図１１のフローチャートを用いて説明する。【０２３４】
まず、検索画像特徴量計算部２２の近傍特徴点選択部２２３（図３）は、近傍特徴点計算部２２２により計算されたＮ個の近傍特徴点から、ある統合特徴点を生成した被統合特徴点を削除し、代わりにそれらの被統合特徴点から計算された統合特徴点を加える（ステップＳ２２０８１）。また、このときの近傍特徴点の数をＮ’個とする。【０２３５】
もし、Ｎ’≧Ｍであれば、ステップＳ２２０８３へ進み、これに対し、Ｎ‘＜Ｍであれば、ステップＳ２２０８１へ戻る。【０２３６】
ステップＳ２２０８３では、近傍特徴点選択部２２３が、Ｎ’個の特徴点からＭ個の特徴点を選択する組み合わせの１つを求める。このとき、ステップＳ２２０４（図１０）と同様に、適切な順序付けを行うものとする。【０２３７】
続いて、近傍特徴点選択部２２３が、Ｍ個の順序付き組み合わせから、巡回置換の１つを計算する（ステップＳ２２０８４）。【０２３８】
次に、不変量計算部２２５（図３）が、Ｍ個の順序付けされた特徴点から、ｆ個の特徴点座標から計算できる不変量を計算し、予め定められた順番に要素を格納する（ステップＳ２２０８５）。【０２３９】
ステップＳ２２０８４からステップＳ２２０８５までの処理は、Ｍ個の順序付けされた特徴点の組み合わせからの全ての巡回置換について行うものとする。【０２４０】
そして、ステップＳ２２０８６において、全ての巡回置換について、特徴ベクトルを計算したか判定する。【０２４１】
ここで、Ｍ点（Ｍ個）全ての巡回置換に対して、１個でも特徴ベクトルが計算が終了していない場合には、ステップＳ２２０８４へ戻り、まだ計算されていない巡回置換について、引き続き、特徴ベクトルの計算を行うようになっている。【０２４２】
一方、全ての巡回置換について特徴ベクトルが計算されていれば、ステップＳ２２０８７へ移動する。【０２４３】
これにより、全ての巡回置換について、特徴ベクトルが計算される。そして、ステップＳ２２０８７において、Ｎ’点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定する。【０２４４】
ここで、Ｎ’個の特徴点からＭ個の特徴点を選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルが計算されていなければ、ステップＳ２２０８３へ戻り、まだ計算されていない選択しうるＭ点の組み合わせについて、特徴ベクトルを計算する。【０２４５】
これに対し、Ｎ’点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了した場合には、ステップＳ２２０８８へ移動する。【０２４６】
このように、ステップＳ２２０８３からステップＳ２２０８７までの処理は、Ｎ’個の特徴点からＭ個の特徴点を選択する組み合わせの全てについて、処理が行われるまで繰り返される。【０２４７】
これにより、Ｎ’点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルが計算されるようになっている。【０２４８】
また、ステップＳ２２０８８では、近傍特徴点の中に含まれ、ある統合特徴点を生成した全ての被特徴点集合に対して、特徴ベクトルの計算が終了したか否か判定する。【０２４９】
これにより、ある統合特徴点を生成した全ての被特徴点集合に対して、特徴ベクトルの計算が終了するまで繰り返される。【０２５０】
従って、ステップＳ２２１０及びステップＳ２２１９における特徴量追加計算処理（図１０）は、近傍特徴点計算部２２２によって計算されたＮ個の特徴点中に含まれる統合特徴点について、特徴量追加計算の処理が行われるまで繰り返される。【０２５１】
このように、近傍特徴点の中に含まれ、ある統合特徴点を生成した、全ての被特徴点集合に対して、繰り返し不変量を計算するようになっていると共に、繰り返し処理が終了した後にステップＳ２２１１へ進む。【０２５２】
（３）効果【０２５３】
第１の実施の形態では、統合特徴点計算部１１４、及び統合特徴点計算部２１４により連結成分の接触を模擬して生成した特徴点が生成され、かつ、近傍特徴点計算部１２２および近傍特徴点計算部２２２により、統合特徴点と、その統合特徴点を生成する元となった被統合特徴点とを同時に選ばないように特徴点集合を計算し、その特徴点集合を用いて特徴量を生成するので、登録画像と検索画像の一方の画像中では接触し、かつ、他方の画像中では分離している場合であっても、対応する特徴量を得ることができる。【０２５４】
（４）他の実施の形態【０２５５】
（４−１）第２の実施の形態【０２５６】
上述の第１の実施の形態では、検索画像特徴量生成部２２に、巡回計算部２２４を含んでいたが、第２の実施の形態としては、予め入力される画像が回転のみ考慮すればよい場合には、図１２に示すように、巡回計算部２２４を省略した構成とすることもできる。【０２５７】
この場合、ステップＳ２２０５、Ｓ２２１１、Ｓ２２０８４の巡回計算処理は、省略される。【０２５８】
（４−２）第３の実施の形態【０２５９】
また、本発明に係る第３の実施の形態として、図１２に示したように、検索画像特徴量計算装置２に設けられていた巡回計算部２２４を検索画像特徴量生成部２２から省略すると共に、図１３に示すように巡回計算部２２４と同一の巡回計算部１２５を、登録画像特徴量生成部１２に含むようにしても良い。【０２６０】
この場合、登録画像特徴量生成装置１と検索画像特徴量生成装置２とを入れ替えた形態に相当する。【０２６１】
また、ステップＳ２２０５、Ｓ２２１４、Ｓ２２０８４の処理を省略し、代わりにステップＳ１２０４、Ｓ１２１１、Ｓ１２０８３の後に、それぞれ、ステップＳ２２０５、Ｓ２２１４、Ｓ２２０８４の動作を組み入れて、順序付き組み合わせに関するすべての巡回組み合わせについて処理を行えばよい。
【実施例１】
【０２６２】
次に、具体的な実施例を用いて、本発明を実施するための最良の形態の動作を説明する。【０２６３】
図１４に示すように、第１の実施の形態による第１の実施例では、文書画像検索特徴量生成システムＤが、文書画像検索システムＺの一部として組み込まれている。【０２６４】
この図１４に示す文書画像検索システムＺは、スキャナＡと、スキャナＢと、計算機Ｃ１と、計算機Ｃ２と、記憶装置Ｍ１と、記憶装置Ｍ２とを備えている。【０２６５】
この第１の実施例では、登録画像特徴量生成装置１を計算機Ｃ１内に備え、検索画像特徴量生成装置２を計算機Ｃ２内に備えている。【０２６６】
また、登録画像特徴量生成装置１によって生成された特徴量を格納する登録画像特徴量格納装置３を、記憶装置Ｍ１内に備えている。【０２６７】
また、登録画像特徴量格納装置３に格納された特徴量と、検索画像特徴量生成装置２によって生成された特徴量とを照合する照合装置４が、計算機Ｃ２内に備えられている。【０２６８】
また、各登録文書が生成した特徴量（ベクトル）のうち、検索画像から生成された特徴ベクトルと一致した回数を格納する特徴ベクトル一致数格納装置５が、記憶装置Ｍ２内に備えられている。【０２６９】
更に、各登録画像の特徴量一致数から検索すべき登録画像を決定する同定装置６が、計算機Ｃ２内に備えられている。【０２７０】
なお、記憶装置Ｍ１と記憶装置Ｍ２とは同一のものであってもよく、また計算機Ｃ１と計算機Ｃ２も同一のものでもよく、スキャナＡとスキャナＢも同一のものであっても良い。【０２７１】
ここで、本実施例におけるパラメータ値としては、Ｎ＝７、Ｍ＝６、ｆ＝４を用いることとする。また、不変量としてアフィン不変量を計算することとする。【０２７２】
そして、統合する特徴点の最大数は２とする。また、特徴点を統合する基準として、連結領域間の距離は、連結領域αの任意の画像と、別の連結領域βの任意の画像との市街地距離ｄの最小値であって、（２）式によって定義されるものとする。【０２７３】
また、（２）式のＤｉｓｔ１の値がＴＨ１＝２以下となる連結領域対１つを統合するものとする。【０２７４】
具体的には例えば、図１５に示すように、２つの連結領域対α、βの間の距離値は、２となる。なお、（２）式で定義されているＣＣ１は、連結領域のαと同義であり、ＣＣ２は、連結領域のβと同義である。【０２７５】
すなわち、図１５において○印で示す箇所は、（２）式によって連結領域対αとβの距離値が２となっており、また（２）式の距離値が１の場合には、連結領域αとベータが接触していることを意味している。【０２７６】
また、特徴点間の距離は、ユークリッド距離で定義するものとする。また、画像中の座標系は、左下を原点とし、ｘ座標の正方向を画像の右方向に、ｙ座標の正方向を画像の上方向にとるものとする。【０２７７】
第１の実施例では、スキャナＡは、文書ＤＯｂｊ１とＤＯｂｊ２とを撮像し、画像ＰＲ１Ａ、ＰＲ２Ａとして登録画像特徴量を計算する。その後、スキャナＢは、文書ＤＯｂｊ１を撮像し、画像ＰＲ１Ｂとして、その画像ＰＲ１Ｂの特徴量が登録されている画像ＰＲ１Ａ、ＰＲ２Ａのいずれであるかを検索（同定）する例について説明する。【０２７８】
図１４に記載された文書画像検索システムＺにおいて、まず、ある登録画像ＰＲ１ＡがスキャナＡから入力されて、登録画像特徴量生成装置１が特徴量を生成し、登録画像特徴量格納装置３に特徴量を格納するまでの動作（図４）について説明する。【０２７９】
なお、この登録画像ＰＲ１Ａは２５６階調の濃淡画像であり、図１６に示すような画像である。【０２８０】
登録画像ＰＲ１Ａが登録画像特徴量生成装置１に入力されると、特徴点抽出部１１が特徴点抽出処理（図４のＳ１１）を行う。まず、図５に示したステップＳ１１１の二値画像生成処理により、二値画像が生成される。【０２８１】
ここでは、予め定められた閾値ＴＨ０によって二値化するものとする。【０２８２】
次に、連結領域ラベリング処理（図５のステップＳ１１２）では、一例として生成された二値画像に対して、非特許文献３に記載されている、４連結のラン解析によるラベリング処理を行う。【０２８３】
ラベリング処理が行われた後の連結領域ラベリング画像ＬＩ１の様子を、図１７に示す。図１７中では、ラベリング処理の結果として、ラベル領域の外接矩形を重畳させている。【０２８４】
図１６の画像にはかすれがあるため、本来１つの連結領域となるべき領域が２つに分離している。【０２８５】
より具体的に説明すると、図１７では、アルファベット毎に連結領域が１個であることを期待している。しかしながら、図１６に示す登録画像ＰＲ１Ａの「Ｇ」という文字は、かすれているため（この場合、薄く撮像されていることを表す。）、図１７に示す「Ｇ」の連結領域が２つに分離されていることを意味している。【０２８６】
次に、連結領域重心・画素数計算処理（図５のステップＳ１１３）により、連結領域の重心を求めて特徴点とする。【０２８７】
ここで、特徴点は、当該連結領域の画素数とともに、図１８のように格納される。【０２８８】
次に、統合特徴点計画処理（図５のステップＳ１１４）の連結領域間距離計算処理（図６のステップＳ１１４１）により、連結領域間の距離Ｄｉｓｔ１を求める。なお、本実施例ではＴＨ１＝２であるので、少なくとも距離値２までを検出できる方法で距離を求めればよい。【０２８９】
ここでは、距離値３まで計測できる図１９のようなフィルタを用いて、ラベル画像全面をスキャンすることによって、連結領域間を求めることとする。【０２９０】
なお、ここで距離値０の場合は、統合の対象外であることを表すものとする。【０２９１】
そして条件を満たした連結領域は、すでに格納されている特徴点情報（図１８）に関連付けて、更に図２０のように格納される。【０２９２】
次に、統合処理（図６のステップＳ１１４２）では、格納されている特徴点情報（図２０）を用いて、連結領域間距離がＴＨ１＝２以下の連結領域対を統合し、統合特徴点を求める。【０２９３】
この場合、連結領域重心・画素数計算処理（図５のステップＳ１１３）において、予め連結領域画素数を格納しておくと、統合処理（図６のステップＳ１１４２）において統合特徴点の重心を求める際には、二つの特徴点座標を（ｘｉ，ｙｉ），（ｘｊ，ｙｊ）とし、特徴点ｉ，ｊに対応付けられている連結成分画素数をＰｉ，Ｐｊとすると、重心の性質から、統合特徴点の座標（ｘφ，ｙφ）は、次式
【数３】
2008066152.tif 000005
により、簡便に求められる。【０２９４】
もちろん、すでに求められている特徴点座標を用いずに、連結領域ラベリング画像Ｌ１１（図示しないが、図５の連結領域ラベリング処理によって算出される画像である。）から統合した領域を求め、その領域に関する重心を用いてもよい。【０２９５】
本実施例では、以上のような特徴点抽出処理（図４のステップＳ１１）が行われる結果、得られる連結領域の統合特徴点は、図２１のようになる。【０２９６】
図２１において、かすれのため２つに分離していた領域対（例えば、４番と５番）に対して連結され、統合特徴点（例えば１４番）が計算されている。【０２９７】
また、９番と１３番とが連結され、統合特徴点１５番が計算されると共に、１０番と１１番とが連結されて、統合特徴点１６番が計算されている。【０２９８】
なお、この場合において、登録画像ＰＲ１Ａに連結領域番号を付した画像を、図２２に示す。図２１及び図２２から明らかなように、連結領域番号９番と１５番は、極めて近接していることを示している。【０２９９】
次に、登録画像特徴量生成部１２が、登録画像特徴量用特徴量抽出処理（図４のステップＳ１２）を行う。【０３００】
まず、登録画像特徴量生成部１２の注目特徴点設定部１２１が、特徴点の１つを注目特徴点として設定する（ステップＳ１２０１）。【０３０１】
本説明では、図２２に示した連結領域番号７番を注目特徴点として説明する。【０３０２】
次に、注目特徴点が統合特徴点かどうかの判定を行う（ステップＳ１２０２）。この場合、図２１の統合フラグに示されているように、統合特徴点の場合には「１」が記入されているので、これにより判定を行うことができる。なお、この場合では、判定結果はＮｏであるので、ステップＳ１２０３へ進む。【０３０３】
ステップＳ１２０３では、注目特徴点と統合特徴点とを除いた特徴点のうち、注目特徴点からのユークリッド距離の小さい方からＮ（＝７）個の特徴点を選択する。【０３０４】
本実施例では、特徴点番号８、４、５、２、１０、１１、３の７特徴点が選択される。次にステップＳ１２０４で、Ｎ（＝７）点からＭ（＝６）点を選択する組み合わせの１つが選択される。ここでは、特徴点番号８、４、５、２、１０、１１のＭ（＝６）点が選択される。【０３０５】
ここで、特徴点番号は、注目特徴点７番の最近傍特徴点４番を先頭とし、７番を軸として８番を通る半直線を基準として時計回りにソートされている。【０３０６】
次にステップＳ１２０４で、ｆ（＝４）点の座標から計算されるアフィン計算量を求める。【０３０７】
そして次に、ステップＳ１２０５において、特徴ベクトルをアフィン不変量によって計算する。【０３０８】
ここで、アフィン不変量とは、非特許文献２によれば、二次元位置ベクトルγ１，γ２，γ３，γ４に対して、次式
【数４】
2008066152.tif 000006
で定まる量のことである。【０３０９】
ここで、｜γｉγｊ｜は、二つの列ベクトルγｉ，γｊを横に並べて作った２×２行列｜γｉγｊ｜の行列式である。【０３１０】
ステップＳ１２０４からステップＳ１２０５の処理は、Ｍ点の順序付け組み合わせからｆ点を選択しうる、全ての組み合わせについて行われる。【０３１１】
そして、ステップＳ１２０６において、Ｎ点から選択しうる全てのＭ点の組み合わせについて、特徴ベクトルの計算が終了したか判定するようになっている。【０３１２】
ここで、Ｍ点（Ｍ個）全ての近傍特徴点に対して、１個でも特徴ベクトルの計算が終了していない場合には、ステップＳ１２０４へ戻り、まだ計算されていない特徴ベクトルの近傍特徴点が選択されると共に、引き続き、特徴ベクトルの計算を行うようになっている。【０３１３】
これにより、Ｎ点から選択しうる、全てのＭ点の組み合わせについて、特徴ベクトルが計算されるようになっている。【０３１４】
なお、Ｍ点の順序付き組み合わせからγ１，γ２，γ３，γ４を選択する方法は、図２３に示されているような組み合わせを選択するものとする。【０３１５】
例えば、図２３に示す１番目の要素は、Ｍ点の順序付き組み合わせ内の特徴点に関して、γ１は順序付け組み合わせの１番目の特徴点座標、γ２は２番目の特徴点座標、γ３は３番目の特徴点座標、γ４は４番目の特徴点座標を用いる。【０３１６】
また、Ｍ（＝６）点からｆ（＝４）点を選ぶ組み合わせの数は、ＭＣｆ＝１５通り存在するので、本実施例で生成される特徴量ベクトルは１５次元ベクトルとなる。【０３１７】
ステップＳ１２０４からステップＳ１２０５の処理を繰り返すことにより、結果として、図２４に示すように注目特徴点７番に関する１５次元の特徴量ベクトルが生成され、登録画像特徴量格納装置３に格納される。【０３１８】
従って、この１５次元の特徴量ベクトルを生成するステップＳ１２０４からステップＳ１２０６までの処理は、Ｎ（＝７）点からＭ（＝６）点を選択するすべての組み合わせについて、行われる。【０３１９】
また、１つのＭ点の組み合わせにつき１つの特徴量ベクトルが生成されるので、ステップＳ１２０４からステップＳ１２０６までの処理で、例えば注目特徴点８番に関するＮＣＭ＝７個の特徴ベクトルが生成され、登録画像特徴量格納装置３に格納される（図２４参照）。【０３２０】
次に、ステップＳ１２０７において、近傍特徴点の中に統合特徴点を生成した特徴点集合の全てが存在するか判定を行う。【０３２１】
この場合、ステップＳ１２０３で選択したＮ点に対応付けられている連結領域のうち、連結領域４番と５番との距離と、１０番と１１番との距離とが、連結領域間の距離が２≦ＴＨ１となっているので、ステップＳ１２０８の特徴量追加計算処理（図８）を行う。【０３２２】
まず、連結領域４番と５番とをＮ点の組みあわせから削除し、４番と５番を統合して生成された統合特徴点１４番（図２２）を付け加える（図８のステップＳ１２０８１）。【０３２３】
この結果、特徴点番号８、１４、３、２、１０、１１のＮ’（＝６）個からなる特徴点の組み合わせが求められる。【０３２４】
次に、図８のステップＳ１２０８２による判定を行う。この場合はＹｅｓであるから、ステップＳ１２０８３の処理を行う。なお、本実施例においては、必ずＹｅｓとなることから、ステップＳ１２０８２の処理をスキップすることもできる。【０３２５】
次に、ステップＳ１２０８３にて、Ｎ’（＝６）点から選ぶことのできるＭ（＝６）点の順序付き組み合わせを求める。【０３２６】
ここでは、結果として、特徴点番号８、１４、３、２、１０、１１の順序付き組み合わせが求められる。次にステップＳ１２０８４にて、特徴ベクトルを求める。【０３２７】
これは、ステップＳ１２０５の動作と同一である。【０３２８】
このように計算すると、注目特徴点７番に関する８番目の特徴ベクトルが生成され、登録画像特徴量格納装置３に格納される。また、Ｎ’（＝６）点から選ぶことのできるＭ（＝６）点の順序付き組み合わせは、この一通りのみであり（ステップＳ１２０８５）、かつ、連結領域１０番と１１番に関して統合特徴点を用いて特徴ベクトルを生成する手続きを行っていないので（ステップＳ１２０８６）、ステップＳ１２０８１へ戻り、特徴ベクトルを計算する処理を継続する。【０３２９】
このように計算すると、本実施例では、注目特徴点番号８番に関しては９種類の１５次元特徴ベクトルが生成される。【０３３０】
これらのＳ１２０１からＳ１２０９までの処理（図７）は、１番から１６番までのすべての特徴点を注目特徴点とした処理が行われるまで継続される。【０３３１】
以上により、登録画像ＰＲ１Ａに対する登録画像特徴量抽出処理（図４）が完了する。この結果として、図２４に示すような特徴量が計算される。【０３３２】
更に、登録画像ＰＲ２Ａ（図２５）に対する登録画像特徴量抽出処理（図４）も同様に行われる。結果として、図２６に示すような特徴量が計算される。【０３３３】
次に、登録画像ＰＲ１Ａ、ＰＲ２Ａに対する登録画像特徴量計算処理（図４）の終了後、文書ＤＯｂｊ１がスキャナＢによって撮像され、検索画像ＰＲ１Ｂが検索画像特徴量計算装置２に入力された場合の例について説明する。【０３３４】
ここで、登録画像のうち文書ＤＯｂｊ１が撮像されている画像はＰＲ１Ａであるから、検索（同定）結果としてＰＲ１Ａが出力されることが望ましい。【０３３５】
図２７に示す検索画像ＰＲ１Ｂが検索画像特徴量計算装置２（図１４）に入力されると、まず、特徴ベクトル一致数格納装置５（図１４）内に格納されている、各登録文書に対応する特徴ベクトル一致数を０に初期化する。【０３３６】
次に、検索画像特徴量計算装置２の特徴点抽出部２１によって、特徴点抽出処理（ステップＳ２１）が行われる。この処理は、登録画像特徴量計算装置１における特徴点抽出部１１による特徴点抽出処理（ステップＳ１１）と同じ処理である。【０３３７】
結果として、図２８に示すような特徴点が得られる。もちろん、入力となるスキャナの個体差を吸収できるよう、二値化閾値、統合に用いる閾値Ｄｉｓｔ１の値など、パラメータの値は、登録画像特徴量計算装置１の特徴点抽出部１１と検索画像特徴量計算装置２の特徴点抽出部２１とにおいて、それぞれ変更することは可能である。【０３３８】
次に、検索画像特徴量計算部２２が行う検索画像特徴量計算処理（ステップＳ２２）について説明する。なお、検索画像特徴量計算処理（図９のステップＳ２２）は、後述する特徴量照合装置４が行う特徴量照合処理と協調して動作を行う。【０３３９】
具体的には、１つの特徴量（ベクトル）が生成される度に、登録画像特徴量格納装置３に格納されている特徴量（ベクトル）との照合処理を行う。以下で、これらの動作について詳細に説明する。【０３４０】
まず、検索画像特徴量計算装置２の注目特徴点設定部２２１が、特徴点の一つを注目特徴点として設定する（図１０のステップＳ２２０１）。【０３４１】
ここでは、特徴点番号１番から５番までを注目特徴点として特徴量（ベクトル）を生成した後に、特徴点番号６番の特徴点を注目特徴点とした場合について説明する。【０３４２】
そして次に、図１０のステップＳ２２０２において、注目特徴点が統合特徴点であるかどうかの判定を行う。特徴点番号６番は統合特徴点ではないので（図２０）、ステップＳ２２０３へ進む。【０３４３】
ステップＳ２２０３では、統合特徴点と注目特徴点自身（この場合、特徴点番号６番である。）とを除いた特徴点のうち、注目特徴点番号６番近傍の特徴点をＮ（＝７）点選択する。ここでは、特徴点番号７、４、３、２、９、１０、８の７点が選択される（図２８）。【０３４４】
次に、ステップＳ２２０４にて、Ｎ（＝７）点からＭ（＝６）点を選ぶ組み合わせのひとつを選択する。ここでは、１番目の組み合わせとして、特徴点番号７、４、３、２、９、１０が選ばれたとする。この組み合わせは、ステップＳ１２０４の処理による順序付け方法と同様に順序付けされている。【０３４５】
次にステップＳ２２０５（図１０）にて、Ｍ（＝６）点からなる順序付け組み合わせの巡回置換を計算する。【０３４６】
まずは、巡回させない順序付け組み合わせ７、４、３、２、９、１０を出力する。次にこの順序付け組み合わせに対して、ステップＳ２２０６（図１０）にて特徴量（ベクトル）を計算する。この特徴量生成方法は、ステップＳ１２０５における特徴量生成方法と同一である。【０３４７】
ステップＳ２２０５からステップＳ２２０６の処理はすべての巡回組み合わせについて行われるので、他の順序付け組み合わせ、例えば、４、３、２、９、１０、７に対する特徴量（ベクトル）などについても計算が行われる。【０３４８】
また、上述のように、Ｓ２２０４からＳ２２０７までの処理は、Ｎ（＝７）点からＭ（＝６）点を選ぶすべての組み合わせについて計算されるまで繰り返される。【０３４９】
本実施例では、ステップＳ２２０６（図１０）において、特徴量（ベクトル）が１つ計算されるたびに、特徴量照合装置４（図１４）によって、後述する照合処理が行われる。【０３５０】
そして、照合処理の結果、一致すると判定された特徴ベクトルがある場合には、特徴ベクトル一致数格納装置５内に格納されている、登録文書毎の一致数が１だけ増やされる。【０３５１】
ここで、照合処理について、図２９に示すフローチャートを参照しながら、具体的に動作について説明する。【０３５２】
まず、図２９のステップＳ４１において、登録画像特徴量格納装置３に格納されている、ある特徴ベクトルと、検索画像から生成された特徴ベクトルとの距離を計算し（ステップＳ４１）、ある閾値ＴＨ１を超えない場合に一致したものと判定する（ステップＳ４２）。【０３５３】
距離尺度としては、２ベクトル間の距離を計算できる既存の尺度を用いることができる。本実施例では、距離として２つのベクトルの誤差二乗和を、ＴＨ１の値として０．１５を用いることとする。【０３５４】
例えば、ステップＳ２２０６（図１０）において計算された検索画像ＰＲ１Ｂの注目特徴点６番に関する順序付け組み合わせ、０番目に関する巡回なしの特徴ベクトルは、図３０のようになる。この場合、登録画像ＰＲ１Ａから計算された注目特徴点７番に関する８番目の特徴ベクトルとの誤差二乗和は、０．１４…となる。【０３５５】
そしてこの値は、ステップＳ４２において、閾値ＴＨ１を越えているか否かの判定が行われる。【０３５６】
ここで、閾値ＴＨ１を超えない場合には、ステップＳ４３へ移動し、２つの特徴ベクトルが一致したものとみなして、一致した特徴ベクトルが計算された登録画像（この例ではＰＲ１Ａ）に対応する特徴ベクトル一致数を１増加させる（ステップＳ４３）。【０３５７】
この例の場合は、誤差二乗和が予め定められた閾値ＴＨ１＝０．１５の値を超えないので、検索画像ＰＲ１Ａに関する特徴ベクトル一致数を１増加させる。【０３５８】
特徴量照合装置４の照合処理が終了すると、ステップＳ２２０７（図１０）に移動して、引き続き、検索画像特徴量計算部２の処理を継続する。【０３５９】
なお、本実施例では、登録画像において特徴量（ベクトル）が生成される度に照合処理を行うこととしたが、本実施の形態ではこれに限らず、予め検索画像から計算される全ての特徴ベクトルを計算し、適当な記憶装置に格納しておき、その後に、検索画像から生成された特徴ベクトルと登録画像から生成された特徴ベクトルの全ての組み合わせについて照合処理を行うことにより、結果として同じ同定（検索）結果を得るようにしても良い。【０３６０】
そして、検索画像特徴量計算部２の処理に戻った後、ステップＳ２２０９（図１０）で、統合すべき特徴点対があるかどうかの判定が行われる。この場合はＮｏとなるので、ステップＳ２２１１へ進む。【０３６１】
ステップＳ２２１１では、すべての統合点についての処理が行われたか否かの判定を行う。ここではＮｏであるので、まだ注目特徴点として設定されていない特徴点を注目特徴点として処理を継続する。【０３６２】
このように、全ての特徴点を注目特徴点として処理をすると、特徴ベクトル一致数格納装置５内（図１４）に格納されている一致数は、例えば、登録画像ＰＲ１Ａに関する一致数は６となり、一方、登録画像ＰＲ２Ａに関する一致数は１となる。【０３６３】
また、検索画像特徴量計算装置２が照合処理を終えると、同定装置６（図１４）が特徴ベクトル一致数格納装置５内（図１４）に格納されている一致数を参照して、最も特徴ベクトル一致数の多かった登録画像を同定すべき画像として判定する。【０３６４】
なお、本実施例では、一致数の一番多い登録画像を判定結果とするので、登録画像ＰＲ１Ａが出力される。もちろん、画像そのものを出力としなくとも、画像と一意に結び付けられたＩＤ、名称など、あるいはそれらの組み合わせを出力してもよい。また、一意に同定するだけでなく、特徴ベクトル一致数の上位Ｊ候補に相当する結果を出力しても良い。【０３６５】
なお、本実施例で説明した、検索画像ＰＲ１Ａから計算された注目特徴点７番に関する８番目の特徴ベクトルは、特徴点を統合することによって生成することのできた特徴量（ベクトル）である。【０３６６】
この特徴量（ベクトル）は、従来の方法では生成し得なかった特徴ベクトルであるので、本実施例に記載の特徴点を統合して特徴量（ベクトル）を生成することにより、文書の検索または同定を行う上で有効である。【０３６７】
また、本実施例では、互いに近い距離にある連結領域同士を統合するようにしている。分離や接触は、近い距離にある連結領域の間でおこる現象と考えられるから、互いに近い距離にある連結同士のみ統合する方式は、すべての連結領域対に関して統合する方式と比べ、統合にかかる計算量を効果的に削減することができるので、特に有効である。【０３６８】
また、本実施例では、連結領域間の距離Ｄｉｓｔ１を特徴点の統合判定に用いている。【０３６９】
従って、特徴点間の距離を基準とした場合などと比べて、連結成分の接触を精度良くシミュレートできるので有効である。【０３７０】
また、この方法は、本発明の第１の実施の形態や第３の実施の形態において、登録画像と検索画像の間の文書の傾きの影響を受けにくいだけでなく、登録画像や検索画像の傾き補正が不要なので、特に有効である。【０３７１】
本願は、日本の特願２００６−３２４０９５号（２００６年１１月３０日に出願）に基づいたものであり、又、特願２００６−３２４０９５号に基づくパリ条約の優先権を主張するものである。特願２００６−３２４０９５号の開示内容は、特願２００６−３２４０９５号を参照することにより本明細書に援用される。【０３７２】
本発明の代表的な実施形態が詳細に述べられたが、様々な変更(changes)、置き換え(substitutions)及び選択(alternatives)が請求項で定義された発明の精神と範囲から逸脱することなくなされることが理解されるべきである。また、仮にクレームが出願手続きにおいて補正されたとしても、クレームされた発明の均等の範囲は維持されるものと発明者は意図する。
【産業上の利用可能性】
【０３７３】
本発明によれば、撮像装置により取り込まれた文書画像を、保存しておいた文書を撮像した画像を用いて検索する文書検索装置として適用できる。また、対象物表面の特徴的な文字列、例えば郵便物の住所領域画像や、対象物を一意に識別するために設計された識別子などを用いて、対象物を検索または同定するための装置として利用できる。この検索または同定装置は、さまざまな箇所で撮像された画像から対象物を追跡するシステムに利用できる。
【図１】
2008066152.tif 000007
【図２】
2008066152.tif 000008
【図３】
2008066152.tif 000009
【図４】
2008066152.tif 000010
【図５】
2008066152.tif 000011
【図６】
2008066152.tif 000012
【図７】
2008066152.tif 000013
【図８】
2008066152.tif 000014
【図９】
2008066152.tif 000015
【図１０】
2008066152.tif 000016
【図１１】
2008066152.tif 000017
【図１２】
2008066152.tif 000018
【図１３】
2008066152.tif 000019
【図１４】
2008066152.tif 000020
【図１５】
2008066152.tif 000021
【図１６】
2008066152.tif 000022
【図１７】
2008066152.tif 000023
【図１８】
2008066152.tif 000024
【図１９】
2008066152.tif 000025
【図２０】
2008066152.tif 000026
【図２１】
2008066152.tif 000027
【図２２】
2008066152.tif 000028
【図２３】
2008066152.tif 000029
【図２４】
2008066152.tif 000030
【図２５】
2008066152.tif 000031
【図２６】
2008066152.tif 000032
【図２７】
2008066152.tif 000033
【図２８】
2008066152.tif 000034
【図２９】
2008066152.tif 000035
【図３０】
2008066152.tif 000036
【図３１】
2008066152.tif 000037
【図３２】
2008066152.tif 000038
【図３３】
2008066152.tif 000039
【図３４】
2008066152.tif 000040
【図３５】
2008066152.tif 000041
【図３６】
2008066152.tif 000042
【図３７】
2008066152.tif 000043
【図３８】
2008066152.tif 000044
【図３９】
2008066152.tif 000045
【図４０】
2008066152.tif 000046
【手続補正書】
【提出日】平成20年3月6日(2008.3.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力画像から特徴点を抽出し、当該特徴点から幾何学的不変量である特徴量を生成する文書画像特徴量生成装置であって、
前記入力画像に含まれる連結領域を決定し、その連結領域の重心を第１特徴点として計算すると共に、少なくとも一部の前記連結領域を統合した領域の重心である統合特徴点を
2008066152.tif 000047
求められた前記第１特徴点及び第２特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点基づいて、前記特徴量を生成する特徴量生成手段と、
を備えることを特徴とする文書画像特徴量生成装置。
【請求項２】
前記特徴量生成手段は、前記特徴量を生成するに際して、前記注目特徴点以外の前記第１及び第２特徴点の中から、その第２特徴点を含むように前記近傍特徴点を選択する
ことを特徴とする請求項１記載の文書画像特徴量生成装置。
【請求項３】
前記特徴量生成手段は、前記統合特徴点と、当該統合特徴点を生成する元となった前記第１特徴点とが同時に選択されることを排除して、前記特徴量を生成する
ことを特徴とする請求項１又は２に記載の文書画像特徴量生成装置。
【請求項４】
前記特徴量生成手段は、前記注目特徴点が前記統合特徴点である場合に、前記注目特徴点を生成する元となった前記第１特徴点が前記近傍特徴点として選択されることを排除して、前記特徴量を生成する
ことを特徴とする請求項１乃至３記載の何れか１項に記載の文書画像特徴量生成装置。
【請求項５】
前記特徴点計算手段は、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことを特徴とする請求項１乃至４の何れか１項に記載の文書画像特徴量生成装置。
【請求項６】
前記特徴点計算手段は、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことを特徴とする請求項５に記載の文書画像特徴量生成装置。
【請求項７】
前記特徴点計算手段は、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことを特徴とする請求項５又は６に記載の文書画像特徴量生成装置。
【請求項８】
請求項１乃至７の何れか１項に記載の文書画像特徴量生成装置を用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行う手段を備える
ことを特徴とする文書画像検索照合装置。
【請求項９】
請求項１乃至７の何れか１項に記載の文書画像特徴量生成装置を用いて生成された前記特徴量を格納する手段を備えることを特徴とする文書画像検索特徴量格納装置。
【請求項１０】
入力画像から特徴点を抽出し、当該特徴点から幾何学的不変量である特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成方法であって、
前記入力画像に含まれる連結領域を決定し、その連結領域の重心を第１特徴点として計算すると共に、少なくとも一部の前記連結領域を結合した領域の重心である総合特徴点を第２特徴点として計算する特徴点抽出ステップと、
求められた前記第１特徴点及び第２特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点に基づいて前記特徴量を生成する特徴量生成ステップと、
を備えることを特徴とする文書画像特徴量生成方法。
【請求項１１】
前記特徴量生成ステップでは、前記特徴量を生成するに際して、前記注目特徴点以外の前記第１特徴点及び第２特徴点の中から、その第２特徴点を含むように前記近傍特徴点を選択する
ことを特徴とする請求項１０記載の文書画像特徴量生成方法。
【請求項１２】
前記特徴量生成ステップでは、前記統合特徴点と、当該統合特徴点を生成する元となった前記第１特徴点とが同時に選択されることを排除して、前記特徴量を生成する
ことを特徴とする請求項１０又は１１に記載の文書画像特徴量生成方法。
【請求項１３】
前記特徴量生成ステップでは、前記注目特徴点が前記統合特徴点である場合に、前記注目特徴点を生成する元となった前記第１特徴点が前記近傍特徴点として選択されることを排除して、前記特徴量を生成する
ことを特徴とする請求項１０乃至１２の何れか１項に記載の文書画像特徴量生成方法。
【請求項１４】
前記特徴点計算ステップでは、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことを特徴とする請求項１０乃至１３の何れか１項に記載の文書画像特徴量生成方法。
【請求項１５】
前記特徴点計算ステップでは、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことを特徴とする請求項１４に記載の文書画像特徴量生成方法。
【請求項１６】
前記特徴点計算ステップでは、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことを特徴とする請求項１４又は１５に記載の文書画像特徴量生成方法。
【請求項１７】
請求項１０乃至１６の何れか１項に記載の文書画像特徴量生成方法を用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行うステップを備える
ことを特徴とする文書画像検索照合方法。
【請求項１８】
請求項１０乃至１６の何れか１項に記載の文書画像特徴量生成方法を用いて生成された前記特徴量を格納するステップを備えることを特徴とする文書画像検索特徴量格納方法。
【請求項１９】
入力画像から特徴点を抽出し、当該特徴点から幾何学的不変量である特徴量を生成する文書画像特徴量生成装置における文書画像特徴量生成用プログラムであって、
前記入力画像に含まれる連結領域を決定し、その連結領域の重心を第１特徴点として計算すると共に、少なくとも一部の前記連結領域を統合した領域の重心である統合特徴点を第２特徴点として計算する特徴点抽出手順と、
求められた前記第１特徴点及び第２特徴点の中から注目特徴点を設定すると共に、当該注目特徴点の近傍に配置される近傍特徴点に基づいて前記特徴量を生成する特徴量生成手順と、
をコンピュータに実行させることを特徴とする文書画像特徴量生成用プログラム。
【請求項２０】
前記特徴量生成手順では、前記特徴量を生成するに際して、前記注目特徴点以外の前記第１特徴点及び第２特徴点の中から、その第２特徴点を含むように前記近傍特徴点を選択する
ことをコンピュータに実行させることを特徴とする請求項１９記載の文書画像特徴量生成用プログラム。
【請求項２１】
前記特徴量生成手順では、前記統合特徴点と、当該統合特徴点を生成する元となった前記第１特徴点とが同時に選択されることを排除して、前記特徴量を生成する
ことをコンピュータに実行させることを特徴とする請求項１９又は２０に記載の文書画像特徴量生成用プログラム。
【請求項２２】
前記特徴量生成手順では、前記注目特徴点が前記統合特徴点である場合に、前記注目特徴点を生成する元となった前記第１特徴点が前記近傍特徴点として選択されることを排除して、前記特徴量を生成する
ことをコンピュータに実行させることを特徴とする請求項１９乃至２１の何れか１項に記載の文書画像特徴量生成用プログラム。
【請求項２３】
前記特徴点計算手順では、前記連結領域の統合の際、予め設定された値を超えない距離にある連結成分のみを統合する
ことをコンピュータに実行させることを特徴とする請求項１９乃至２２の何れか１項に記載の文書画像特徴量生成用プログラム。
【請求項２４】
前記特徴点計算手順では、少なくとも２つ以上の前記連結領域に対して、一方の前記連結領域に属する画素と他方の前記連結領域に属する画素との距離の最小値を、前記統合特徴点の計算に用いる
ことをコンピュータに実行させることを特徴とする請求項２３に記載の文書画像特徴量生成用プログラム。
【請求項２５】
前記特徴点計算手順では、前記連結領域の距離を計算する際に、少なくとも前記予め設定された値までの距離を求める
ことをコンピュータに実行させることを特徴とする請求項２３又は２４に記載の文書画像特徴量生成用プログラム。
【請求項２６】
請求項１９乃至２５の何れか１項に記載の文書画像特徴量生成用プログラムを用いて生成された前記特徴量を用いて文書画像検索もしくは同定を行う手順をコンピュータに実行させることを特徴とする文書画像検索照合用プログラム。
【請求項２７】
請求項１９乃至２５の何れか１項に記載の文書画像特徴量生成用プログラムを用いて生成された前記特徴量を格納する手順をコンピュータに実行させることを特徴とする文書画像検索特徴量格納用プログラム。
【国際調査報告】
2008066152.tif 000048
2008066152.tif 000049