文書画像データベースの登録方法および検索方法
【課題】文書画像データベースの大規模化に伴って顕在化するLocally Likely Arrangement Hashing (LLAH) のメモリ効率の問題、および、特徴量の識別性の問題を解決する改善手法を提供する。LLAH は高いロバスト性を実現するために、必要メモリ量が多く、また、大規模化に対処するには、特徴量の識別性・安定性が十分でないという側面がある。
【解決手段】以下の3 点の改良を施す。第１は、ハッシュに保存する特徴点をサンプリングすることによる必要メモリ量の削減である。第２は、特徴量の次元数を増加させることによる識別性向上である。第３は、特徴量のうち冗長性のある次元を削除することによる安定性向上である。
【解決手段】以下の3 点の改良を施す。第１は、ハッシュに保存する特徴点をサンプリングすることによる必要メモリ量の削減である。第２は、特徴量の次元数を増加させることによる識別性向上である。第３は、特徴量のうち冗長性のある次元を削除することによる安定性向上である。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、文書画像データベースの登録方法および検索方法に関する。より詳細には、文書画像から特徴点を抽出し、文書画像と共に文書画像データベースに登録する登録方法および検索方法に係り、特に文書画像の登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースへの適用に関する。
【背景技術】
【０００２】
近年、携帯電話の分野においてデジタルカメラの付属が一般的となっている。また、それら品質が著しく向上しており、通常のデジタルカメラと比較して遜色ないものとなっている。これにより、一般の利用者が高品質なデジタルカメラを常に携帯するという状況が生じている。そこで、デジタルカメラで撮影された画像を用いた画像検索が注目を集めている。この発明では、画像検索の中でも特に文書画像検索について考える。
【０００３】
この明細書で文書画像は、文書あるいは文書を含む画像を指す。
文書画像検索とは、与えられた検索質問（クエリ）に対応する文書画像を、データベースから見つける処理である。その中でも、デジタルカメラを用いた文書画像検索は、デジタルカメラで撮影された文書画像を検索質問とするものである。このような形式の文書画像検索を用いれば、印刷文書を撮影し、撮影された印刷文書を検索質問に用いて検索することでさまざまなサービスへの応用が可能になる。具体的には、学術論文の撮影による参考文献の取得や、関連Web サイトへのアクセス等のサービスが考えられる。
【０００４】
撮影画像に対応する文書画像をデータベースから検索する手法として、Locally Likely Arrangement Hashing（LLAH）が提案されている（例えば、特許文献１、２および非特許文献１参照）。LLAH とは、例えば文書画像中の単語の重心を特徴点とし、特徴点の配置から特徴量を求め、検索する手法である。LLAH の特徴として、現実的な利用において生じる撮影方向の変化や隠れ、紙面の湾曲などの外乱にロバストであるという点が挙げられる。また、単純な検索の繰り返しによりリアルタイム検索が実現できるほどの高速性を持つ。これは、特徴量計算の計算量が、検索対象の特徴点数N に対してO(N) であることに起因する（例えば、非特許文献２参照）。ここで、O(N) は、問題を解くために必要なおおよその計算量の表記方法であって、O(N) はNが定まったときの計算量がa×N＋b（a, bは定数）以下で収まることを表す。これらの性質により、文書への拡張現実（例えば、非特許文献３、４参照）や、カメラペンシステム（例えば、非特許文献５参照）等の応用がなされている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−３２１０９号公報
【特許文献２】特開２００９−７００６６号公報
【非特許文献】
【０００６】
【非特許文献１】中居友弘、黄瀬浩一、岩村雅一、“デジタルカメラを用いた高速文書画像検索におけるアフィン不変量および相似不変量の利用”、電子情報通信学会技術研究報告、vol.105，no.PRMU-614，pp.25-30，Feb. 2006．
【非特許文献２】中居友弘、黄瀬浩一、岩村雅一、“特徴点の局所的配置に基づくデジタルカメラを用いた高速文書画像検索”、電子情報通信学会論文誌Ｄ，vol.J89-D，no.9，pp.2045-2054，Sept. 2006．
【非特許文献３】R.T. Azuma, “A survey of augmented reality,” Presence, vol.6, no.4, pp.355-385, 1997.
【非特許文献４】中居友弘、黄瀬浩一、岩村雅一、“特徴点の局所的配置に基づくリアルタイム文書画像検索とその拡張現実への応用”、電子情報通信学会技術研究報告、vol.106，no.PRMU-229，pp.41-48，Sept. 2006．
【非特許文献５】近野恵、岩田和将、黄瀬浩一、岩村雅一、内田誠一、大町真一郎、“カメラペンシステムにおける射影歪みを考慮した文書画像検索の精度向上法”、画像の認識・理解シンポジウム(MIRU2010)論文集、pp.239-246，July 2010．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一方、LLAH には高い精度とロバスト性を実現するために、大量のメモリを使用するという側面がある。具体的な一例では、10,000 ページの文書画像がデータベースに登録されている場合に約200MB、1,000 万ページの文書画像を登録するためには約150GB のメモリが必要となる。このようなメモリ効率の悪さは、LLAH のスケーラビリティを制限するものである。また、データベースの登録ページ数の増加に伴い、類似した特徴点の配置を持つ文書が登録される可能性が高くなる。これにより、検索精度の低下を招くと考えられる。そのため、大規模化を行うためにはより高い識別性を持つ特徴量が求められる。
【０００８】
この発明は、以上のような事情を考慮してなされたものであって、文書画像データベースの大規模化に伴って顕在化するLLAH のメモリ効率の問題、および、特徴量の識別性の問題を解決する改善手法を提供する。
【課題を解決するための手段】
【０００９】
この発明は、
（Ｉ）コンピュータが、文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出し、前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算することを特徴とする文書画像データベースの登録方法を提供する。
【００１０】
さらに、この発明は、
(II)コンピュータが、検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、前記登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法を提供する。
【００１１】
この発明において、従来のLLAH のメモリ使用量を削減する基本的なアイディアは、データベースに保存する特徴点をサンプリングするというものである。また、特徴量の識別性を向上させるためには、次元数を増加させる。ただし、単純に次元数を増加させると、特徴量の安定性を損なうことになる（前述の、非特許文献１参照）。そこで、特徴量の次元数を増加させると同時に冗長性のある次元を削除する。これにより、情報の損失を防ぎつつ、特徴量の安定性を向上させ高い検索精度を実現できる。
【００１２】
また、この発明は、
（III）コンピュータが、文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出する文書画像データベースの登録方法を提供する。
【００１３】
さらに、この発明は、
（IV）コンピュータが、検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、前記登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法を提供する。
【００１４】
検索精度よりもメモリ量の削減を優先させる必要がある場合は、特徴量の次元数を増加させない代わりに冗長性のある次元を削減しない態様も考えられる。
【発明の効果】
【００１５】
前記（Ｉ）および（III）の登録方法において、前記特徴点抽出ステップは所定面積より小さい複数の連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出するので、すべての連結成分の重心を特徴点とする場合に比べて抽出される特徴点の数が少なくなり、必要なメモリ量を節約できる。
【００１６】
さらに、前記（Ｉ）の登録方法において、前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算するので、それらの不変量を組み合わせてなる特徴量は、同一の特性値が異なる特徴量の計算に用いられるといった不変量間の関連性、即ち、一種の冗長性がない。よって、各特徴点は、高い識別性を有しつつ前記冗長性が排除された特徴量で表される。換言すれば、各特徴点は、射影歪み、ノイズおよび／または解像度の違い等による誤差の影響が抑制され安定した特徴量で表される。
この発明によれば、登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースへの適用が可能になる。
【００１７】
また、前記（II）および（IV）の検索方法は、前述の登録方法により作成される文書画像データベースに用いる検索方法を提供するので、登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースの検索が可能になる。
【００１８】
文書画像の局所的特徴とは、文書画像中の一部の領域に記載された文字、単語あるいは画像の幾何学的な特徴をいう。実施形態では、この発明では単語に対応する領域が示す幾何学的な特徴を指すが、必ずしもこれに限定されるものではない。
【００１９】
幾何学的変換は、文書画像を回転させ、並進させ、拡大縮小し、せん断変形させ、および／または扇形変形させる変換である。回転及び並進を含むユークリッド変換、それに拡大縮小を加えた相似変換、さらにせん断変形を加えたアフィン変換、それに仰木が多辺形を加えた射影変換がある（例えば、佐藤淳著、「コンピュータビジョン−視覚の幾何学−」、第１版、株式会社コロナ社、2003 年7 月30 日、p.42−65参照）。
【００２０】
不変量とは、幾何学的変換を通じて変化しない値であり、幾何学的変換の種類に応じた不変量が存在する。例えば、図形の面積はユークリッド変換に対する不変量の例である。辺の長さの比は、相似変換に対する不変量の例である。後述するように、図形の面積比はアフィン変換に対する不変量（アフィン不変量）の例である。また、複比は射影変換に対する不変量（射影不変量）の例である。図形の面積が小さければ、前述の面積比は近似的に射影不変量として扱える。
【００２１】
この発明において、幾何学的要素から所定の演算により求まる特性値は、不変量を構成する要素をいう。具体的には、前述の不変量に係る図形の面積および辺の長さが特性値に該当する。
【００２２】
また、連結成分は、単語の文字を構成する線が連結した成分、または、その線を所定量ぼかしたときに連結した成分をいう。連結成分は、画像の中にあって互いに繋がっている画素の集まりである。なお、後述する実施形態ではぼかし処理を行って解像度を下げたときの連結成分を採用している。ぼかし処理の量は、分かち書きされる英語のような文書では一つの連結成分が単語に対応する程度に設定すればよい。分かち書きされない日本語のような文書では、一つの連結成分が、例えば漢字を構成する「へん」や「つくり」に対応する程度に設定すればよい。
【００２３】
文書識別子の統計的処理とは、選択肢として挙げられた多数の文書識別子の中から妥当な文書識別子を選択する処理である。具体的には、投票処理が挙げられる。
【００２４】
特徴点の識別性とは、一の特徴点を他と区別できるようにする、その特徴点の特性をいう。また、特徴点の安定性とは、特徴点に係る特徴量が歪み、ノイズおよび／または解像度の違い等による誤差の影響を受けにくい性質をいう。
【００２５】
後述するように、10,000 ページの文書画像を登録したデータベースを用いて実験した結果、特徴点のサンプリングにより、メモリ使用量が最大で約70% 削減されることを確認した。また1,000 万ページデータベースを用いた実験では、検索精度99.4% 、処理時間38ms で検索可能であることを確認した。
【図面の簡単な説明】
【００２６】
【図１】この発明基礎となる従来のLLAH の処理を示す説明図である。
【図２】この発明基礎となる従来のLLAH で用いるハッシュ表の構成を示す説明図である。
【図３】この発明の改良されたLLAH で用いる特徴点のサンプリングを示す説明図である。
【図４】この発明の改良されたLLAH で用いる特徴量の冗長な次元の削除について説明する説明図である。
【図５】この発明の改良されたLLAH の効果実証実験において、データベースに登録された文書画像の一例を示す説明図である。
【図６】この発明の改良されたLLAH の効果実証実験において、検索質問の一例を示す説明図である。
【図７】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と必要メモリ量の関係を示すグラフである。
【図８】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と検索精度の関係を示すグラフである。
【図９】この発明の改良されたLLAH の効果実証実験において、検索に失敗した文書画像の例を示す説明図である。
【図１０】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と処理時間の関係を示すグラフである。
【図１１】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と平均リスト長の関係を示すグラフである。
【図１２】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１３】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１４】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１５】この発明の改良されたLLAH の効果実証実験の結果として、撮影範囲による検索精度の違いを示すグラフである。
【図１６】この発明の改良されたLLAH の効果実証実験において、部分撮影での検索に失敗した文書画像の例を示す説明図である。
【図１７】この発明の改良されたLLAH の効果実証実験において、検索に失敗した特徴点の例を示す説明図である。（ａ）は、「”」、（ｂ）は「．」の失敗例である。
【図１８】この発明の改良されたLLAH の効果実証実験において、特徴量選択の有無による平均リスト長の違いを示すグラフである。
【発明を実施するための形態】
【００２７】
以下、この発明の好ましい態様について説明する。
この発明の登録方法において、前記登録ステップは、（１）前記参照子、（２）前記識別子および（３）前記特徴量またはその特徴量を簡略化した簡易特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記特徴量に応じて各特徴点を分類すべく予め定義された計算を行ってその特徴点が属する類のインデックスを得、インデックスに応じた類に前記データ組を分類し、前記文書画像と共に前記文書画像データベースに登録してもよい。このようにすれば、前記データ組が分類されて登録されるので、検索は何れか一つの類に登録された特徴点に探索の対象が絞り込まれ、探索に要する処理時間を短縮できる。
【００２８】
また、前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量としてもよい。このようにすれば、アフィン不変量としての図形の面積比を最も少ない特徴点から得ることができる。また、特徴点を頂点とする三角形の面積は、それらの特徴点を頂点とする四角形以上の図形に比べて小さいので、射影不変量としてより優れた近似特性を有している。
【００２９】
この発明の検索方法において、インデックスに応じた類にデータ組が分類されて登録された文書画像データベースの検索方法については、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とし、前記個別探索ステップは、前記登録方法に対応する計算によって各クエリ特徴点のインデックスを得、そのインデックスに係る類として登録されたデータ組を参照し、そのデータ組が簡易特徴量を有する場合は前記クエリ特徴点に係る簡易特徴量を求めたうえで同一もしくは最も類似の簡易特徴量を有するデータ組に係る参照子を得、登録されたデータ組が特徴量を有する場合は同一もしくは最も類似の特徴量を有するデータ組に係る参照子を得るようにしてもよい。このようにすれば、インデックスに応じた類にデータ組が分類されて登録された文書画像データベースについても検索方法が提供される。データ組が分類されているので、短時間に検索を行うことができる。
【００３０】
また、この発明の検索方法において、前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量としてもよい。
この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。
【００３１】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
この発明の理解を容易にするため、まず、この発明の基礎となる従来のLLAH についてここで簡単に説明しておく。
【００３２】
≪従来のLLAH による文書画像検索≫
１．処理の概要
図１は、この発明の基礎となる従来のLLAH による文書画像検索の処理の概要を示す説明図である。図１に示すように、従来のLLAH は、文書画像検索の環境を構築する段階であって、登録すべき文書画像が与えられたとき、その文書画像から特徴点を抽出して文書画像データベースに登録する段階に適用される。さらに、従来のLLAH は、検索質問としての文書画像が与えられたとき、検索質問から特徴点を抽出して文書画像データベースの中からその検索質問に対応する文書画像を検索する段階において適用される。登録と検索は何れもコンピュータによって処理が実行される。なお、この明細書でコンピュータは、ＣＰＵあるいはマイクロコンピュータ等、プログラムに従って処理を行う装置の総称として用いる。また、処理を実行するコンピュータは、単独のＣＰＵ構成に限らず、いわゆるクラウド・コンピューティングやグリッド・コンピューティングなど複数のＣＰＵによる構成を含む。さらに、前記検索に係る処理を実行するコンピュータは、前記登録に係る処理を実行するコンピュータと同一のものでなくてもよい。
【００３３】
前記登録と前記検索において、コンピュータは共通の特徴点抽出処理を実行する。特徴点抽出処理において、コンピュータは、文書画像から複数の特徴点を抽出して特徴点の集合でその文書画像を表す。さらに、コンピュータは、抽出された特徴点を用いて登録処理または検索処理を実行する。即ち、登録の段階では登録処理を実行し、検索の段階では検索処理を実行する。登録処理と検索処理は、共通の特徴量計算処理を含む。
【００３４】
登録処理において、コンピュータは、登録すべき文書画像から抽出された各特徴点につき、特徴量をそれぞれ算出する。そして、前記コンピュータは、各特徴点から算出された特徴量およびその特徴点が抽出された文書画像への参照符号をその特徴点と関連づけて文書画像データベースに登録する。つまり、前記登録処理は、特徴量によって文書画像が索引付けされるようにして文書画像を文書画像データベースに登録する。
【００３５】
検索処理において、コンピュータは、与えられた検索質問画像から抽出された各特徴点につき、登録処理と同様に特徴量を算出する。そして、前記コンピュータは、各特徴点から算出された特徴量を用いて文書画像データベースにアクセスする。即ち、検索質問画像の各特徴点と似た特徴点を含む文書画像が登録されていればその文書画像への参照符号を得る。検索質問からは通常多数の特徴点が抽出される。よって、それらの特徴点を票の単位とする投票処理を行って検索質問に対応する文書画像への参照符号を得る。
投票処理は、一般に、得られた証拠に基づいて選択肢の何れかに得点を与え、すべての証拠を集計した結果に基づいて選択肢を選択する処理をいう。通常は、最高得票数を獲得した選択肢を選択するが、得票数だけでなく、所定の得票率を上回ったか、下位の選択肢との得票差が所定以上あるか等統計的な観点から妥当性を評価することによって、複数の選択肢を選択する場合や何も選択しないこともある。以下、処理の詳細を説明する。
【００３６】
２．特徴点抽出処理
従来のLLAH において、コンピュータは、特徴点の配置に基づいて特徴量を算出し、算出された特徴量を用いて文書画像のマッチングを行う。従って、特徴点抽出処理では、与えられた文書画像に射影歪みやノイズが生じていたり、低解像度であったりしても同一の特徴点を抽出する必要がある。一つの手法は、文書画像の文書を構成する単語が占める領域（以下、単語領域）に着目し、単語領域の重心を特徴点として用いるものである。また、日本語のような、分かち書きされない文書については、単語領域に代えて例えば漢字の「へん」や「つくり」を構成する連結成分に着目し、連結成分の重心と面積とを求め、面積比と面積順位を用いて重心（特徴点）に係る特徴量を計算する手法が提案されている（例えば、特許文献１の明細書段落０００６、００４３、００４６参照）。単語領域は、文字を構成する線をぼかして得られる連結成分といえる。以下、連結成分の例としての単語領域について説明する。
【００３７】
単語領域の重心を特徴点として抽出する手順を以下に示す。まず、与えられた文書画像を適応二値化して二値画像を得る。次に、二値画像をガウシアンフィルタでぼかし、再度適応二値化を行うと、単語ごとに連結された画像が得られる。最後に連結成分の重心を計算して特徴点とする。
【００３８】
３．特徴量計算
特徴量とは、文書画像の特徴点を表現する値であり、特徴点のマッチングは特徴量に基づいて行われる。正確な検索のためには、ロバストな特徴量が必要である。また、与えられた文書画像がカメラで撮影されたものである場合、文書画像とカメラの位置関係により、通常は射影歪みが含まれる。そのため、射影歪みに対して不変となる幾何学的不変量を特徴量として用いる必要がある。そこで、ある特徴点S0 に対応する特徴量として、点S0 を含む近傍の4 点ABCD から、以下の式で求められる値を計算し、特徴量として用いる。
【００３９】
【数１】
【００４０】
ここで、P(A, B, C) は頂点ABC からなる三角形の面積であり、この２つの三角形は必ず１辺を共有する。２つの三角形の面積比である式（１）はアフィン不変量である。さらに、三角形の面積比は、面積の小さい局所領域では射影不変量に近似できる値である。LLAH ではアフィン不変量を用いることで、射影歪みに対するロバスト性を実現している。
【００４１】
射影歪のない状態で文書画像が文書画像データベースに登録されており、その文書画像に対応する検索質問を用いて検索を行う場合、検索質問が射影歪みを含んでいるとする。その場合、検索質問から抽出される特徴点S0 の近傍４点が、登録された文書画像から抽出される特徴点の近傍４点と異なることが起こりえる。射影歪みの影響により、点S0 とその近傍の特徴点との距離関係が元の文書画像と異なってしまう場合がそれである。そうであっても、近傍n 点のうちm 点（m およびn は自然数で４≦m ＜n ）までは共通のものが得られる可能性が高いと考えられることから、そのすべての組合せnCm 通りを調べることにする。すなわち、特徴点１つあたりnCm 個の特徴量を計算する。このm 点からアフィン不変量の計算に必要な４点を選ぶ組合せはmC4 通りある。すべての組合せからアフィン不変量を求め、それらmC4個の数値の列（r(0), r(1), …, r(mC4) ）を特徴量とする。
【００４２】
なお、近傍m 点から４点を選ぶ際、どの点からどの順番に４点を選んでアフィン不変量の計算を行うかという規則を定め、不変量の計算量を削減する手法も提案されている（例えば、特許文献２の明細書段落００４９参照）。処理時間を短縮するためである。
【００４３】
また、前述のようにして得られた列（r(0), r(1), …, r(mC4) ）の特徴量に、特徴点抽出の過程で得られる連結成分の面積から得られる特徴量をさらに付加する。まず、アフィン不変量の計算に用いた近傍m 点の連結成分の面積を求める。次に、隣り合う連結成分の組に番号を与え、その連結成分の面積比を計算する。つまり、全部でm 個の連結成分の組が作られる。そして、面積比の大きさの順番で連結成分の組の番号を並べる。このm 個の数値の列を、既に得られたmC4個の列（r(0), r(1), …, r(mC4) ）に追加する。したがって、特徴点１つあたりにつきnCm 個の特徴量が得られ、各特徴量は、（mC4 ＋m ）個の数値の列で表される。即ち、各特徴量は、前述の数値列を要素とする（mC4 ＋m ）次元のベクトル（特徴ベクトル）として表される。
【００４４】
４．登録処理
登録処理において、コンピュータは、各特徴点を特徴量に従ってハッシュに登録する。そして、すべての文書画像を同じハッシュに登録する。ハッシュ表のインデックスHindex は以下に示すハッシュ関数で計算される。
【００４５】
【数２】
【００４６】
ここでr(i) は特徴量の各次元の値、d は離散化レベル数、Hsize はハッシュ表のサイズ（ビンの数）である。商Q は、すべての特徴量に対して一意に決定される。つまり、同一の特徴ベクトルからは、同一のHindex と商Q が得られる。検索処理では文書画像データベースに登録された各特徴点の中で、検索質問から抽出された各特徴点に対応する特徴点を探索するところ、その探索は、インデックスHindex の照合と商Q の照合とに分割できる。即ち、検索質問から抽出された各特徴点と等しいインデックスHindex を有する類のビンに探索の対象をまず絞り込むことができる。次いで、そのビンに登録された特徴点と検索質問から抽出された特徴点とを照合する。同一ビンに登録された特徴点との照合は、特徴ベクトルの（mC4 ＋m ）次元どうしの比較に代えて、商Q どうしの比較で済ませることができる。商Q は、照合用に特徴量を簡略化した特性値といえる。
【００４７】
そこで図２に示すように、文書ID、点ID、商Q のデータ組をハッシュ表に登録する。ハッシュ表は、インデックス（ここでは、Hindex の値）ごとに区画されたビン構造を有し、登録すべきデータをインデックスの値に応じたビンに分類して登録するデータ構造である。LLAH でハッシュ表に登録されるデータは、前述のように文書ID、点ID、商Q のデータ組である。ここで、文書ID とは文書画像の識別番号であり、前述の参照符号に相当するものである。点ID とは文書画像の他の特徴点と区別するためその特徴点に付される固有の番号である。データはインデックスの値に応じたビンに登録される。登録すべきデータの中にインデックス値が等しいものが複数個存在する場合、それらのデータを同一のビンに登録しなければならない。この状態をハッシュの衝突と呼ぶ。衝突が生じた場合は、それらのデータをリスト形式でビンに登録する。リストの長さには制限値を設けておく。その制限値を超えた場合、リストでリンクされた全てのデータをインデックスごと削除する。以降、削除されたインデックスは使用しないこととする。即ち、そのインデックス値に応じたデータ組は、ハッシュ表に登録しない。それらのデータ組に係る特徴点は、類似するものが多く検索に有用でないと考えられるからである。なお、メモリ使用量を削減するため、ハッシュの衝突が生じるリストを全て削除し、ハッシュ表を単純化する手法は、既に提案されている（例えば、特許文献２の明細書段落００４４、００４５参照）。
【００４８】
５．検索処理
検索の段階では、検索質問から特徴点を抽出し、各特徴点の特徴量を算出してインデックス（Hindex の値）および商Q を得る。得られたインデックスを用いて、対応するビンに登録されたデータ組があればそれを参照する。参照したデータ組について商Q が一致するかを調べる。個別の特徴点探索である。検索質問から抽出された各特徴点について個別の特徴点探索を行う。参照したデータ組の商Q が一致していたら、そのデータ組の文書ID に投票を行う。これが投票処理である。文書ID ごとに初期値ゼロのカウンタが設けられた投票テーブルが用意されている。コンピュータは、投票テーブルの文書ID のうち、投票すべき文書ID のカウンタをインクリメントする。検索質問の各特徴点につきハッシュ表を参照し、ビンの内容に応じて投票を行う。最大の得票数を得た文書ID が付された文書画像を、正解画像として出力する。
【００４９】
≪この発明によるLLAH の改良点≫
１．メモリ使用量の削減
従来のLLAH では、特徴点抽出処理において得られたすべての特徴点を、原則としてハッシュ表に保存する。ハッシュの衝突回数（リストの長さ）が制限値を超えた場合のみが例外である。そのため、メモリ使用量が多くなる。しかし、すべての特徴点を保存しなくとも、検索はできると考えられる。これは、検索に投票処理を用いているためである。そこで、特徴点のサンプリングを行い、ハッシュに保存するデータ量を削減する。これによって、メモリ使用量の削減を図るのである。
【００５０】
特徴点をサンプリングする際に注意しなければならないのは、ハッシュに登録する特徴点に、位置的な偏りが生じないように考慮することである。
文書画像中の特徴点の分布に疎密ができると、疎な部分では正解画像が十分な得票数を得ることができず、精度の低下を招くと考えられる。
つまり、撮影範囲にロバストであるためには、サンプリングされる特徴点がある程度均等に分散して分布していなければならない。
【００５１】
さらに、サンプリングされる特徴点が、検索に有効なものであることも重要である。
そこでこの発明では、連結成分の面積に着目してサンプリングを行う。サンプリングの例を図３に示す。図３は、文書画像の一部を示している。なお、S0 〜S6 は６つの連結成分の重心として得られるそれぞれの特徴点を示す符号である。いま、中央部の“in”という単語に注目すると、その連結成分は、周囲の連結成分より面積が小さいことがわかる。サンプリングでは、このような連結成分から抽出した特徴点S0 を有効な特徴点として採用する。周囲より面積の小さい連結成分は、字数の少ない連結成分であって、前置詞や冠詞なとどして文書中に頻出する。よって、位置的に偏りのないサンプリングが行えると考えられる。
【００５２】
また、連結成分の面積が小さいということは、近傍の特徴点との距離が小さくなるということである。近傍の特徴点S1 〜S6 との距離が小さければ小さいほど、射影歪みの影響を受けにくく、安定した特徴量が得られると考えられる。しかし、これだけではハッシュに登録される特徴点数が少なすぎる場合が考えられる。そのため、サンプリングした特徴点の近傍k 点もハッシュに登録する。この実施形態では、登録する特徴点数が１文書あたり約200 点となるよう、k の値を設定する。従って、特徴点数が200 点に満たない文書画像に対しては特徴点のサンプリングを行なわず、すべての特徴点をハッシュに登録する。また、検索時にサンプリングの有無を判別することは困難である。そのため、検索時には、検索質問から得られた全ての特徴点についてハッシュを参照する。
【００５３】
２．特徴点の識別性・安定性の向上
データベースの大規模化に伴い、ハッシュ表に登録される特徴量は膨大になる。そのため、一般的にハッシュの衝突回数が増加すると考えられる。換言すれば、類似の特徴点が増えると考えられる。そのため、誤投票が増加することになり、検索精度に影響が出ると考えられる。しかし、ハッシュの衝突回数を抑えるためにその制限値を低く設定すれば、それに伴って削除されるデータ組が大量に出現すると考えられる。従って、検索に必要なデータまで削除されてしまい、検索精度が低下すると考えられる。以上のことから、特徴点の識別性を高め、衝突回数を抑制する必要がある。異なる特徴点と区別され易くするということである。
【００５４】
識別性向上の基本的な考えは、特徴量の次元数を増加させることである。従来のLLAH では、着目する特徴点S0 の特徴量計算に用いる点S0 の近傍の特徴点数をn = 7，m = 6 として、21次元の特徴量を用いている。従来のLLAH では、登録するページ数を10,000 程度に想定しているため、この次元数でも特徴点は十分な識別性を持つ。また、低次元の特徴量を使用することにより、安定性を高めているとも考えられる。
この発明では、特徴点S0 の近傍の特徴点数をn = 8，m = 7 とすることによって、次元数を増加させる。具体的には、アフィン不変量ベクトルが7C4 = 35 次元、面積比特徴量が7 次元となり、合計42 次元の特徴量を得ることができる。従来のLLAH に比べて２倍の次元数である。
【００５５】
ただし、特徴量の次元数を単純に増加させると安定性の面で不利益が伴う。m の値が大きければ大きいほど、計算される不変量の数が多くなる。そのため、検索質問に係る特徴点と同じ特徴量を有する特徴点が、その検索質問と無関係な文書画像中に偶然に現れる可能性は低くなる。しかし、検索質問の特徴点と正解画像の特徴点の特徴量が一致するためには、特徴量がすべての次元で一致する必要がある。しかし、特徴量の次元数が増加すると、射影歪み、ノイズおよび／または解像度の違い等による誤差の影響で、対応すべき特徴点から異なる特徴量が算出されてしまう可能性が高くなる。よって、特徴量の次元数を増加させると特徴点の識別性は向上するが、それと引き換えに、特徴点の安定性が低下するというジレンマが生じる。
そこで、この発明では、前述のジレンマを解決するため、特徴量から互いに関連性のある次元を削除する。
【００５６】
互いに関連性のある次元は、次のように考える。従来のLLAH で、特徴量の計算は、図４で示すように、異なるアフィン不変量の計算に同一の三角形を重複して使用する。ここで、異なるアフィン不変量とは、従来のLLAH における特徴点抽出処理の項目で述べたごとく、mC4個の数値の列（r(0), r(1), …, r(mC4) ）を構成する各数値のことである。重複した三角形を使用する不変量は互いに関連があるといえる。そして、この関連性は、一種の冗長性と考えることができる。
【００５７】
図４で、特徴点S0 の近傍に特徴点S1, S2, S3, S4, S5, S6 が特徴点S0 を取り囲むように存在する。特徴点S0 に係るアフィン不変量は、図４の右側に示す不変量１、不変量２および不変量３を含む。不変量１は、頂点が特徴点S0, S1, S2 からなる三角形１と、特徴点S0, S2, S3 からなる三角形２の面積比として算出される。不変量２は、三角形２と、頂点が特徴点S0, S3, S4 からなる三角形３の面積比として算出される。不変量３は、三角形３と、頂点が特徴点S0, S4, S5 からなる三角形４の面積比として算出される。不変量２は、三角形２を重複使用する点で不変量１と関連が高く、三角形３を重複使用する点で不変量３と関連が高い。よって、三角形２および三角形３の何れも重複使用する不変量２は、前述の冗長性があると考えられる。
【００５８】
この不変量２のような次元を削除するのである。結果、特徴量計算に使用されるいずれの三角形も、異なる不変量の計算に重複して使用されることがない。冗長性のある次元の削除により、情報の損失を抑えつつ特徴量の安定性向上を図る。当初の35次元のアフィン不変量ベクトルは、冗長性のある次元を削除することによって約半分の17次元にまで削減される、面積比特徴量7 次元との合計は24 次元となる。
これまでに説明した改良されたLLAH は、コンピュータに所定の処理を行わせるための処理プログラムの態様、その処理プログラムをコンピュータ読取り可能に記憶する不揮発性の記憶媒体の態様、およびその処理プログラムをコンピュータが実行することにより改良されたLLAHの機能を実現するシステムの態様として捉えることができる。
【００５９】
≪実験例≫
１．実験例１：改良されたLLAH の効果
前述のメモリ使用量の削減と、特徴点の識別性・安定性向上の効果を明確にするため、以下の３つのバージョンのLLAH を作成した。
ｉ．従来のLLAH 手法
ii．メモリ使用量削減版
iii．メモリ使用量削減版に識別性、安定性向上処理を加えた総合版
ｉは比較の基準となる従来のLLAH であり、iiおよびiiiが改良されたLLAH に係るものである。
【００６０】
実験で用いた文書画像データベースの登録ページ数は10,000 である。
登録された文書画像は、主に予稿集のCD-ROM から集められた、１段組および２段組の英語論文である。それらの英語論文は、PDF ファイルを解像度200dpi で画像に変換したものである。登録された文書画像の一例を図５に示す。検索質問として、印刷文書を紙面に対して斜め方向（約60°）から文書全体を撮影した画像を1003 枚用意した。撮影には、1200万画素のデジタルカメラを用いた。検索質問画像の一例を図６に示す。登録画像と検索質問の撮影角度は異なる。登録されたものと異なる撮影角度の検索質問は、各バージョンの射影歪みに対するロバスト性を明らかに示すことができる。ハッシュ表のサイズは230−1 である。実験に用いたコンピュータは、CPU がAMD 社製のOpteron（登録商標）、CPUクロック周波数が2.8GHz、メモリ容量が128GB のものである。
以下の表１に結果を示す。表１で、「使用メモリ」はハッシュ表に格納されるデータ量を表している。データ構造としてのハッシュ表自体に使用されるメモリ容量は含まれていない。
【００６１】
【表１】
【００６２】
また「正投票率」は、検索で見つかった対応点数のうち、正解画像に対応したものの割合を表す。正投票率の割合が高いほど、識別性・安定性が高いことを示す。
iiのメモリ削減版は、従来手法と比較して、約70% のメモリ削減を実現した。これは、従来手法でハッシュに登録していた特徴点数の約70% を削除したことと同義である。また、iiiの総合版は、従来手法と比較して、約65% のメモリ削減を実現した。これだけの特徴点を削除したにも関わらず、精度には全く影響がなかった。その理由の一つとして、本実験で用いた検索質問が、文書全体を撮影したものであるということが挙げられる。そこで、撮影範囲の違いによる精度への影響を検証する必要があるが、これについては後の「部分撮影への耐性」の項目で述べる。
【００６３】
次に、iiのメモリ削減版とiiiの総合版とを比較すると、メモリ使用量が10MB 増加している。これは近傍特徴点数n の値を変えることにより、１つの特徴点から得られる特徴量が増加するためである。また、誤投票が約20% 低下していることから、特徴量の識別性が向上していると考えられる。さらに、精度には全く影響がないことから、特徴量の安定性も確保できていると考えられる。処理時間が3ms 増加しているが、これは１つの特徴点で計算されるアフィン不変量の数が増加するためである。
以上のことから、改良されたLLAH は、精度を低下させることなくメモリ使用量の削減を実現し、さらに、メモリ使用量の削減と特徴点の識別性、安定性の向上を実現しているといえる。
【００６４】
２．実験例２：大規模化への対応
文書画像データベースの大規模化に対する改良されたLLAH のスケーラビリティを検証した。登録ページ数を1 万、10 万、100 万、1,000万とした4つの異なるデータベースを作成し、登録ページ数と必要メモリ量、検索精度、処理時間の関係をそれぞれ調べた。実験例２における改良されたLLAHは、実験例１におけるiiiの総合版に対応する。
比較のために、従来のLLAH 手法の結果を併記した。検索質問は、実験例１と同じものを使用した。ハッシュ表のサイズは230−1 、リスト長の制限値は100 である。
【００６５】
２−１．必要メモリ量
文書画像データベースへの登録ページ数と必要メモリ量の関係を図7 に示す。ここで必要メモリ量は、検索するために必要なすべてのメモリ使用量を表す。また、ハッシュ表を確保するためにメモリを8GB 使用している。従来手法では1,000 万ページのデータベースは作成不可能なため、100 万から1,000 万までは推定値を表す。どちらの手法も、登録ページ数が増加するに伴い、必要メモリ量も増加した。ただし、従来のLLAH と比較して、改良されたLLAH の必要メモリ量は約50% 程度となっていることがわかる。
【００６６】
２−２．検索精度
登録ページ数と検索精度の関係を図８に示す。改良されたLLAH は、従来のLLAH よりも高い検索精度を示した。また、改良されたLLAH では1,000 万ページの文書画像データベースにおいて99.4% という高い精度で検索可能であることが確認された。これより、改良された特徴量は、大規模化に耐え得る高い識別性と安定性を備えていると考えられる。しかし、登録ページ数の増加に伴い、検索精度が低下した。大規模化に伴い検索に失敗した例を図９に示す。この画像のように、ページの大部分を図表が占め、テキストの量が少ない検索質問で検索に失敗した。これは、得られる特徴点の数が少ないため、正解の文書が十分な得票数を得られないことが原因であると考えられる。
【００６７】
２−３．処理時間
登録ページ数と処理時間の関係を図１０に示す。登録ページ数の増加と比較して、処理時間の増加は抑制されている。これは、ハッシュを用いて検索することによる効果であると考えられる。また、1,000 万ページの文書画像データベースにおいて、38ms で検索可能であることが確認された。従って、改良されたLLAH は、1,000万ページの文書画像データベースにおいて実時間検索が可能であるといえる。
【００６８】
文書画像データベースの大規模化に伴い、従来のLLAH と改良されたLLAH とで処理時間の逆転が起こった。登録ページ数が少ない場合、従来のLLAH の処理時間がより短い。これは特徴点あたりの特徴量数と、特徴量あたりのアフィン不変量数の相違による。従来のLLAH では、7C6 = 7 個の特徴量と、特徴量あたり6C4 = 15 個の不変量を計算する。改良されたLLAH では、8C7 = 8 個の特徴量と、24 個の不変量を計算する。このように、従来のLLAH の計算量は改良されたLLAH よりも少ないため、処理時間が短くなったと考えられる。
【００６９】
しかし、登録ページ数の増加に伴い、改良されたLLAH は従来のLLAH より高い性能を示した。これは、ハッシュ表におけるリスト長の違いが原因であると考えられる。ここで、ハッシュ表においてリスト長がゼロでないもののリスト長の平均を図１１に示す。従来のLLAH と改良されたLLAH の何れも、登録ページ数の増加に伴って、平均リスト長が増加していることがわかる。
【００７０】
特に、100 万ページの文書画像データベースにおいて、従来のLLAH が改良されたLLAH に比べて約２倍のリスト長となっている。リスト長が大きくなると、リストをたどるために要する処理時間が増加する。従来のLLAHは、その部分でより多くの処理時間を要する。そのため、処理時間の逆転が起こったと考えられる。以上のことから、登録ページ数が増加すればするほど、改良されたLLAH は、処理時間の点で従来のLLAHよりも有利になると考えられる。
【００７１】
３．実験例３：部分撮影への耐性
実験例１で述べたように、改良されたLLAH で高い検索精度となっている理由の１つに、検索質問が文書画像全体を写していることが挙げられる。文書画像全体を撮影することにより、参照する特徴点数が増加し、正解画像が多くの得票数を得ることができるためである。文書画像の一部分が撮影された検索質問では、特徴点数が減少するために精度が低下すると考えられる。そこで、文書画像の一部分を撮影した検索質問を作成し、部分撮影への耐性を検証した。
【００７２】
実験例３で用いる文書画像データベースには、1,000 万ページの文書画像が登録されている。まず、実験例１および２で用いた検索質問から、図表が大半を占めるものを除いた989 枚を選択した。次に、それらの検索質問から文章が写っている部分を切り抜き、疑似的な部分撮影クエリを作成した。撮影範囲の大きさとして、全体の１／２，１／４，１／８の３パターンを用意した。撮影範囲の例を、それぞれ図１２、図１３および図１４に示す。
【００７３】
結果を図１５に示す。撮影範囲が狭くなるに伴い、検索精度が低下することがわかる。これは、検索質問から得られる特徴点数が少なく、正解画像が十分な得票数を得られないことが原因と考えられる。検索に失敗した例を図１６に示す。このように、文章の中に「．」や「”」が数多く分布していると、検索に失敗する傾向があった。これは、それらがノイズとなって、安定した特徴点を抽出することが困難であるためである。図１７に、検索に失敗したときの特徴点の例を示す。図１７の（ａ）および（ｂ）のそれぞれについて、左側が検索質問、右側に登録文書画像を表す。（ａ）のように「”」が連結成分から離れて新たな特徴点となったり、（ｂ）のように「．」が特徴点として抽出されなかったりする事象が生じる。これは、特徴点抽出処理における適応二値化による影響であると考えられる。これについては、特徴点抽出に新たな処理を追加する等の改良が必要である。
【００７４】
４．実験例４：特徴点の間引きと特徴量選択の効果
これまでに述べた実験例は、特徴点をサンプリングしてメモリ使用量を削減する手法（以下、間引きと呼ぶ）と特徴量の識別性を向上させつつ安定性を確保するために特徴量の冗長性を排除する手法（以下、特徴量選択と呼ぶ）とを組み合わせた態様である。次に、それらの手法の単独の効果を確認する実験を行った。
まず、間引き有無、特徴量選択有無の態様を組み合わせ、必要メモリ量、検索精度および処理時間を確認した。ただし、間引きがないと必要なメモリ量が膨大になってしまい現行の実験装置が対応できない。そのため、登録ページ数100万で実験を行った。結果を表２に示す。
【００７５】
【表２】
【００７６】
表２を見ると、特徴量選択なしの条件下で間引きなしの使用メモリ量は16.2 GB対し、間引きありでは6.4 GBである。また、特徴量選択ありの条件下で間引きなしの使用メモリ量は18.7 GBに対し、間引きありでは7.3 GBである。メモリ使用量の削減については、特徴量選択の効果はあまりなく、間引きの効果が目立つ。特徴量選択の有無による検索精度の差はそれほど大きくないようにも見える。しかし、登録ページ数が1000万ページになると、特徴量選択を行わない検索精度の差がより大きくなる。
続いて、登録ページ数1000万ページで、特徴量選択の有無による違いを比較した。結果を表３に示す。
【００７７】
【表３】
【００７８】
表３で、「必要メモリ量」は、検索に必要なすべてのメモリ使用量である。「処理時間」は、特徴点抽出処理にかかる時間を含まない。「平均リスト長」は、ハッシュにおいてリスト長がゼロでないものの平均値である。「ハッシュ表の使用率（以下，使用率）」は、リスト長がゼロでないものの割合である。
特徴量選択の有無で必要メモリ量に違いがあるのは、主として特徴点１つあたりに計算される特徴量数（特徴ベクトルの次元数）の違いによるものである。特徴量選択なしの場合は21 次元、特徴量選択ありの場合は24 次元である。
【００７９】
特徴量選択ありでの検索精度99.4 %に対して特徴量なしの検索精度は98.6 %に下がっている。精度100 %からの差分で考えたときの検索誤りの割合は、約２倍の差がある。特徴量選択なしにおける検索精度の低下は、誤投票の増加によるものと考えられる。しかし、特徴量選択の有無で平均リスト長がほぼ同じであるため、誤投票の増加が衝突回数の増加によるものかわからない。そこでハッシュ表のリスト長の頻度を調べた。その結果を図１８に示す。
【００８０】
図１８から、特徴選択なしの場合は、特徴量選択ありの場合に比べてリスト長の長いものが多いことがわかる。これが誤投票の増加につながったと考えられる。
以上の結果から、特徴点の間引きは、メモリ使用量の削減に大きく寄与している一方、特徴量の選択は検索精度の向上に寄与していることがわかる。
登録ページ数が1000万におよぶ大規模な文書画像データベースへの対応には、いずれの手法も非常に有効なものといえる。
【産業上の利用可能性】
【００８１】
改良されたLLAH では、大規模文書画像検索に対応するために、所要メモリ量の削減と、特徴点の識別性・安定性の向上の点で改良を行った。その結果、実験により1,000 万ページデータベースにおいて精度99.4% 、処理時間38ms で検索が可能であることが確かめられた。以上のことから、改良されたLLAH では、スケーラビリティが向上したといえる。
【００８２】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００８３】
S0、S1、S2、S3、S4、S5、S6：特徴点
【技術分野】
【０００１】
この発明は、文書画像データベースの登録方法および検索方法に関する。より詳細には、文書画像から特徴点を抽出し、文書画像と共に文書画像データベースに登録する登録方法および検索方法に係り、特に文書画像の登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースへの適用に関する。
【背景技術】
【０００２】
近年、携帯電話の分野においてデジタルカメラの付属が一般的となっている。また、それら品質が著しく向上しており、通常のデジタルカメラと比較して遜色ないものとなっている。これにより、一般の利用者が高品質なデジタルカメラを常に携帯するという状況が生じている。そこで、デジタルカメラで撮影された画像を用いた画像検索が注目を集めている。この発明では、画像検索の中でも特に文書画像検索について考える。
【０００３】
この明細書で文書画像は、文書あるいは文書を含む画像を指す。
文書画像検索とは、与えられた検索質問（クエリ）に対応する文書画像を、データベースから見つける処理である。その中でも、デジタルカメラを用いた文書画像検索は、デジタルカメラで撮影された文書画像を検索質問とするものである。このような形式の文書画像検索を用いれば、印刷文書を撮影し、撮影された印刷文書を検索質問に用いて検索することでさまざまなサービスへの応用が可能になる。具体的には、学術論文の撮影による参考文献の取得や、関連Web サイトへのアクセス等のサービスが考えられる。
【０００４】
撮影画像に対応する文書画像をデータベースから検索する手法として、Locally Likely Arrangement Hashing（LLAH）が提案されている（例えば、特許文献１、２および非特許文献１参照）。LLAH とは、例えば文書画像中の単語の重心を特徴点とし、特徴点の配置から特徴量を求め、検索する手法である。LLAH の特徴として、現実的な利用において生じる撮影方向の変化や隠れ、紙面の湾曲などの外乱にロバストであるという点が挙げられる。また、単純な検索の繰り返しによりリアルタイム検索が実現できるほどの高速性を持つ。これは、特徴量計算の計算量が、検索対象の特徴点数N に対してO(N) であることに起因する（例えば、非特許文献２参照）。ここで、O(N) は、問題を解くために必要なおおよその計算量の表記方法であって、O(N) はNが定まったときの計算量がa×N＋b（a, bは定数）以下で収まることを表す。これらの性質により、文書への拡張現実（例えば、非特許文献３、４参照）や、カメラペンシステム（例えば、非特許文献５参照）等の応用がなされている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−３２１０９号公報
【特許文献２】特開２００９−７００６６号公報
【非特許文献】
【０００６】
【非特許文献１】中居友弘、黄瀬浩一、岩村雅一、“デジタルカメラを用いた高速文書画像検索におけるアフィン不変量および相似不変量の利用”、電子情報通信学会技術研究報告、vol.105，no.PRMU-614，pp.25-30，Feb. 2006．
【非特許文献２】中居友弘、黄瀬浩一、岩村雅一、“特徴点の局所的配置に基づくデジタルカメラを用いた高速文書画像検索”、電子情報通信学会論文誌Ｄ，vol.J89-D，no.9，pp.2045-2054，Sept. 2006．
【非特許文献３】R.T. Azuma, “A survey of augmented reality,” Presence, vol.6, no.4, pp.355-385, 1997.
【非特許文献４】中居友弘、黄瀬浩一、岩村雅一、“特徴点の局所的配置に基づくリアルタイム文書画像検索とその拡張現実への応用”、電子情報通信学会技術研究報告、vol.106，no.PRMU-229，pp.41-48，Sept. 2006．
【非特許文献５】近野恵、岩田和将、黄瀬浩一、岩村雅一、内田誠一、大町真一郎、“カメラペンシステムにおける射影歪みを考慮した文書画像検索の精度向上法”、画像の認識・理解シンポジウム(MIRU2010)論文集、pp.239-246，July 2010．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一方、LLAH には高い精度とロバスト性を実現するために、大量のメモリを使用するという側面がある。具体的な一例では、10,000 ページの文書画像がデータベースに登録されている場合に約200MB、1,000 万ページの文書画像を登録するためには約150GB のメモリが必要となる。このようなメモリ効率の悪さは、LLAH のスケーラビリティを制限するものである。また、データベースの登録ページ数の増加に伴い、類似した特徴点の配置を持つ文書が登録される可能性が高くなる。これにより、検索精度の低下を招くと考えられる。そのため、大規模化を行うためにはより高い識別性を持つ特徴量が求められる。
【０００８】
この発明は、以上のような事情を考慮してなされたものであって、文書画像データベースの大規模化に伴って顕在化するLLAH のメモリ効率の問題、および、特徴量の識別性の問題を解決する改善手法を提供する。
【課題を解決するための手段】
【０００９】
この発明は、
（Ｉ）コンピュータが、文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出し、前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算することを特徴とする文書画像データベースの登録方法を提供する。
【００１０】
さらに、この発明は、
(II)コンピュータが、検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、前記登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法を提供する。
【００１１】
この発明において、従来のLLAH のメモリ使用量を削減する基本的なアイディアは、データベースに保存する特徴点をサンプリングするというものである。また、特徴量の識別性を向上させるためには、次元数を増加させる。ただし、単純に次元数を増加させると、特徴量の安定性を損なうことになる（前述の、非特許文献１参照）。そこで、特徴量の次元数を増加させると同時に冗長性のある次元を削除する。これにより、情報の損失を防ぎつつ、特徴量の安定性を向上させ高い検索精度を実現できる。
【００１２】
また、この発明は、
（III）コンピュータが、文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出する文書画像データベースの登録方法を提供する。
【００１３】
さらに、この発明は、
（IV）コンピュータが、検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、前記登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法を提供する。
【００１４】
検索精度よりもメモリ量の削減を優先させる必要がある場合は、特徴量の次元数を増加させない代わりに冗長性のある次元を削減しない態様も考えられる。
【発明の効果】
【００１５】
前記（Ｉ）および（III）の登録方法において、前記特徴点抽出ステップは所定面積より小さい複数の連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出するので、すべての連結成分の重心を特徴点とする場合に比べて抽出される特徴点の数が少なくなり、必要なメモリ量を節約できる。
【００１６】
さらに、前記（Ｉ）の登録方法において、前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算するので、それらの不変量を組み合わせてなる特徴量は、同一の特性値が異なる特徴量の計算に用いられるといった不変量間の関連性、即ち、一種の冗長性がない。よって、各特徴点は、高い識別性を有しつつ前記冗長性が排除された特徴量で表される。換言すれば、各特徴点は、射影歪み、ノイズおよび／または解像度の違い等による誤差の影響が抑制され安定した特徴量で表される。
この発明によれば、登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースへの適用が可能になる。
【００１７】
また、前記（II）および（IV）の検索方法は、前述の登録方法により作成される文書画像データベースに用いる検索方法を提供するので、登録ページ数が100 万ページから1,000 万におよぶ大規模な文書画像データベースの検索が可能になる。
【００１８】
文書画像の局所的特徴とは、文書画像中の一部の領域に記載された文字、単語あるいは画像の幾何学的な特徴をいう。実施形態では、この発明では単語に対応する領域が示す幾何学的な特徴を指すが、必ずしもこれに限定されるものではない。
【００１９】
幾何学的変換は、文書画像を回転させ、並進させ、拡大縮小し、せん断変形させ、および／または扇形変形させる変換である。回転及び並進を含むユークリッド変換、それに拡大縮小を加えた相似変換、さらにせん断変形を加えたアフィン変換、それに仰木が多辺形を加えた射影変換がある（例えば、佐藤淳著、「コンピュータビジョン−視覚の幾何学−」、第１版、株式会社コロナ社、2003 年7 月30 日、p.42−65参照）。
【００２０】
不変量とは、幾何学的変換を通じて変化しない値であり、幾何学的変換の種類に応じた不変量が存在する。例えば、図形の面積はユークリッド変換に対する不変量の例である。辺の長さの比は、相似変換に対する不変量の例である。後述するように、図形の面積比はアフィン変換に対する不変量（アフィン不変量）の例である。また、複比は射影変換に対する不変量（射影不変量）の例である。図形の面積が小さければ、前述の面積比は近似的に射影不変量として扱える。
【００２１】
この発明において、幾何学的要素から所定の演算により求まる特性値は、不変量を構成する要素をいう。具体的には、前述の不変量に係る図形の面積および辺の長さが特性値に該当する。
【００２２】
また、連結成分は、単語の文字を構成する線が連結した成分、または、その線を所定量ぼかしたときに連結した成分をいう。連結成分は、画像の中にあって互いに繋がっている画素の集まりである。なお、後述する実施形態ではぼかし処理を行って解像度を下げたときの連結成分を採用している。ぼかし処理の量は、分かち書きされる英語のような文書では一つの連結成分が単語に対応する程度に設定すればよい。分かち書きされない日本語のような文書では、一つの連結成分が、例えば漢字を構成する「へん」や「つくり」に対応する程度に設定すればよい。
【００２３】
文書識別子の統計的処理とは、選択肢として挙げられた多数の文書識別子の中から妥当な文書識別子を選択する処理である。具体的には、投票処理が挙げられる。
【００２４】
特徴点の識別性とは、一の特徴点を他と区別できるようにする、その特徴点の特性をいう。また、特徴点の安定性とは、特徴点に係る特徴量が歪み、ノイズおよび／または解像度の違い等による誤差の影響を受けにくい性質をいう。
【００２５】
後述するように、10,000 ページの文書画像を登録したデータベースを用いて実験した結果、特徴点のサンプリングにより、メモリ使用量が最大で約70% 削減されることを確認した。また1,000 万ページデータベースを用いた実験では、検索精度99.4% 、処理時間38ms で検索可能であることを確認した。
【図面の簡単な説明】
【００２６】
【図１】この発明基礎となる従来のLLAH の処理を示す説明図である。
【図２】この発明基礎となる従来のLLAH で用いるハッシュ表の構成を示す説明図である。
【図３】この発明の改良されたLLAH で用いる特徴点のサンプリングを示す説明図である。
【図４】この発明の改良されたLLAH で用いる特徴量の冗長な次元の削除について説明する説明図である。
【図５】この発明の改良されたLLAH の効果実証実験において、データベースに登録された文書画像の一例を示す説明図である。
【図６】この発明の改良されたLLAH の効果実証実験において、検索質問の一例を示す説明図である。
【図７】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と必要メモリ量の関係を示すグラフである。
【図８】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と検索精度の関係を示すグラフである。
【図９】この発明の改良されたLLAH の効果実証実験において、検索に失敗した文書画像の例を示す説明図である。
【図１０】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と処理時間の関係を示すグラフである。
【図１１】この発明の改良されたLLAH の効果実証実験の結果として、登録ページ数と平均リスト長の関係を示すグラフである。
【図１２】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１３】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１４】この発明の改良されたLLAH の効果実証実験において、部分撮影の耐性を調べるために用いた検索質問の第一の例を示す説明図である。
【図１５】この発明の改良されたLLAH の効果実証実験の結果として、撮影範囲による検索精度の違いを示すグラフである。
【図１６】この発明の改良されたLLAH の効果実証実験において、部分撮影での検索に失敗した文書画像の例を示す説明図である。
【図１７】この発明の改良されたLLAH の効果実証実験において、検索に失敗した特徴点の例を示す説明図である。（ａ）は、「”」、（ｂ）は「．」の失敗例である。
【図１８】この発明の改良されたLLAH の効果実証実験において、特徴量選択の有無による平均リスト長の違いを示すグラフである。
【発明を実施するための形態】
【００２７】
以下、この発明の好ましい態様について説明する。
この発明の登録方法において、前記登録ステップは、（１）前記参照子、（２）前記識別子および（３）前記特徴量またはその特徴量を簡略化した簡易特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記特徴量に応じて各特徴点を分類すべく予め定義された計算を行ってその特徴点が属する類のインデックスを得、インデックスに応じた類に前記データ組を分類し、前記文書画像と共に前記文書画像データベースに登録してもよい。このようにすれば、前記データ組が分類されて登録されるので、検索は何れか一つの類に登録された特徴点に探索の対象が絞り込まれ、探索に要する処理時間を短縮できる。
【００２８】
また、前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量としてもよい。このようにすれば、アフィン不変量としての図形の面積比を最も少ない特徴点から得ることができる。また、特徴点を頂点とする三角形の面積は、それらの特徴点を頂点とする四角形以上の図形に比べて小さいので、射影不変量としてより優れた近似特性を有している。
【００２９】
この発明の検索方法において、インデックスに応じた類にデータ組が分類されて登録された文書画像データベースの検索方法については、前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とし、前記個別探索ステップは、前記登録方法に対応する計算によって各クエリ特徴点のインデックスを得、そのインデックスに係る類として登録されたデータ組を参照し、そのデータ組が簡易特徴量を有する場合は前記クエリ特徴点に係る簡易特徴量を求めたうえで同一もしくは最も類似の簡易特徴量を有するデータ組に係る参照子を得、登録されたデータ組が特徴量を有する場合は同一もしくは最も類似の特徴量を有するデータ組に係る参照子を得るようにしてもよい。このようにすれば、インデックスに応じた類にデータ組が分類されて登録された文書画像データベースについても検索方法が提供される。データ組が分類されているので、短時間に検索を行うことができる。
【００３０】
また、この発明の検索方法において、前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量としてもよい。
この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。
【００３１】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
この発明の理解を容易にするため、まず、この発明の基礎となる従来のLLAH についてここで簡単に説明しておく。
【００３２】
≪従来のLLAH による文書画像検索≫
１．処理の概要
図１は、この発明の基礎となる従来のLLAH による文書画像検索の処理の概要を示す説明図である。図１に示すように、従来のLLAH は、文書画像検索の環境を構築する段階であって、登録すべき文書画像が与えられたとき、その文書画像から特徴点を抽出して文書画像データベースに登録する段階に適用される。さらに、従来のLLAH は、検索質問としての文書画像が与えられたとき、検索質問から特徴点を抽出して文書画像データベースの中からその検索質問に対応する文書画像を検索する段階において適用される。登録と検索は何れもコンピュータによって処理が実行される。なお、この明細書でコンピュータは、ＣＰＵあるいはマイクロコンピュータ等、プログラムに従って処理を行う装置の総称として用いる。また、処理を実行するコンピュータは、単独のＣＰＵ構成に限らず、いわゆるクラウド・コンピューティングやグリッド・コンピューティングなど複数のＣＰＵによる構成を含む。さらに、前記検索に係る処理を実行するコンピュータは、前記登録に係る処理を実行するコンピュータと同一のものでなくてもよい。
【００３３】
前記登録と前記検索において、コンピュータは共通の特徴点抽出処理を実行する。特徴点抽出処理において、コンピュータは、文書画像から複数の特徴点を抽出して特徴点の集合でその文書画像を表す。さらに、コンピュータは、抽出された特徴点を用いて登録処理または検索処理を実行する。即ち、登録の段階では登録処理を実行し、検索の段階では検索処理を実行する。登録処理と検索処理は、共通の特徴量計算処理を含む。
【００３４】
登録処理において、コンピュータは、登録すべき文書画像から抽出された各特徴点につき、特徴量をそれぞれ算出する。そして、前記コンピュータは、各特徴点から算出された特徴量およびその特徴点が抽出された文書画像への参照符号をその特徴点と関連づけて文書画像データベースに登録する。つまり、前記登録処理は、特徴量によって文書画像が索引付けされるようにして文書画像を文書画像データベースに登録する。
【００３５】
検索処理において、コンピュータは、与えられた検索質問画像から抽出された各特徴点につき、登録処理と同様に特徴量を算出する。そして、前記コンピュータは、各特徴点から算出された特徴量を用いて文書画像データベースにアクセスする。即ち、検索質問画像の各特徴点と似た特徴点を含む文書画像が登録されていればその文書画像への参照符号を得る。検索質問からは通常多数の特徴点が抽出される。よって、それらの特徴点を票の単位とする投票処理を行って検索質問に対応する文書画像への参照符号を得る。
投票処理は、一般に、得られた証拠に基づいて選択肢の何れかに得点を与え、すべての証拠を集計した結果に基づいて選択肢を選択する処理をいう。通常は、最高得票数を獲得した選択肢を選択するが、得票数だけでなく、所定の得票率を上回ったか、下位の選択肢との得票差が所定以上あるか等統計的な観点から妥当性を評価することによって、複数の選択肢を選択する場合や何も選択しないこともある。以下、処理の詳細を説明する。
【００３６】
２．特徴点抽出処理
従来のLLAH において、コンピュータは、特徴点の配置に基づいて特徴量を算出し、算出された特徴量を用いて文書画像のマッチングを行う。従って、特徴点抽出処理では、与えられた文書画像に射影歪みやノイズが生じていたり、低解像度であったりしても同一の特徴点を抽出する必要がある。一つの手法は、文書画像の文書を構成する単語が占める領域（以下、単語領域）に着目し、単語領域の重心を特徴点として用いるものである。また、日本語のような、分かち書きされない文書については、単語領域に代えて例えば漢字の「へん」や「つくり」を構成する連結成分に着目し、連結成分の重心と面積とを求め、面積比と面積順位を用いて重心（特徴点）に係る特徴量を計算する手法が提案されている（例えば、特許文献１の明細書段落０００６、００４３、００４６参照）。単語領域は、文字を構成する線をぼかして得られる連結成分といえる。以下、連結成分の例としての単語領域について説明する。
【００３７】
単語領域の重心を特徴点として抽出する手順を以下に示す。まず、与えられた文書画像を適応二値化して二値画像を得る。次に、二値画像をガウシアンフィルタでぼかし、再度適応二値化を行うと、単語ごとに連結された画像が得られる。最後に連結成分の重心を計算して特徴点とする。
【００３８】
３．特徴量計算
特徴量とは、文書画像の特徴点を表現する値であり、特徴点のマッチングは特徴量に基づいて行われる。正確な検索のためには、ロバストな特徴量が必要である。また、与えられた文書画像がカメラで撮影されたものである場合、文書画像とカメラの位置関係により、通常は射影歪みが含まれる。そのため、射影歪みに対して不変となる幾何学的不変量を特徴量として用いる必要がある。そこで、ある特徴点S0 に対応する特徴量として、点S0 を含む近傍の4 点ABCD から、以下の式で求められる値を計算し、特徴量として用いる。
【００３９】
【数１】
【００４０】
ここで、P(A, B, C) は頂点ABC からなる三角形の面積であり、この２つの三角形は必ず１辺を共有する。２つの三角形の面積比である式（１）はアフィン不変量である。さらに、三角形の面積比は、面積の小さい局所領域では射影不変量に近似できる値である。LLAH ではアフィン不変量を用いることで、射影歪みに対するロバスト性を実現している。
【００４１】
射影歪のない状態で文書画像が文書画像データベースに登録されており、その文書画像に対応する検索質問を用いて検索を行う場合、検索質問が射影歪みを含んでいるとする。その場合、検索質問から抽出される特徴点S0 の近傍４点が、登録された文書画像から抽出される特徴点の近傍４点と異なることが起こりえる。射影歪みの影響により、点S0 とその近傍の特徴点との距離関係が元の文書画像と異なってしまう場合がそれである。そうであっても、近傍n 点のうちm 点（m およびn は自然数で４≦m ＜n ）までは共通のものが得られる可能性が高いと考えられることから、そのすべての組合せnCm 通りを調べることにする。すなわち、特徴点１つあたりnCm 個の特徴量を計算する。このm 点からアフィン不変量の計算に必要な４点を選ぶ組合せはmC4 通りある。すべての組合せからアフィン不変量を求め、それらmC4個の数値の列（r(0), r(1), …, r(mC4) ）を特徴量とする。
【００４２】
なお、近傍m 点から４点を選ぶ際、どの点からどの順番に４点を選んでアフィン不変量の計算を行うかという規則を定め、不変量の計算量を削減する手法も提案されている（例えば、特許文献２の明細書段落００４９参照）。処理時間を短縮するためである。
【００４３】
また、前述のようにして得られた列（r(0), r(1), …, r(mC4) ）の特徴量に、特徴点抽出の過程で得られる連結成分の面積から得られる特徴量をさらに付加する。まず、アフィン不変量の計算に用いた近傍m 点の連結成分の面積を求める。次に、隣り合う連結成分の組に番号を与え、その連結成分の面積比を計算する。つまり、全部でm 個の連結成分の組が作られる。そして、面積比の大きさの順番で連結成分の組の番号を並べる。このm 個の数値の列を、既に得られたmC4個の列（r(0), r(1), …, r(mC4) ）に追加する。したがって、特徴点１つあたりにつきnCm 個の特徴量が得られ、各特徴量は、（mC4 ＋m ）個の数値の列で表される。即ち、各特徴量は、前述の数値列を要素とする（mC4 ＋m ）次元のベクトル（特徴ベクトル）として表される。
【００４４】
４．登録処理
登録処理において、コンピュータは、各特徴点を特徴量に従ってハッシュに登録する。そして、すべての文書画像を同じハッシュに登録する。ハッシュ表のインデックスHindex は以下に示すハッシュ関数で計算される。
【００４５】
【数２】
【００４６】
ここでr(i) は特徴量の各次元の値、d は離散化レベル数、Hsize はハッシュ表のサイズ（ビンの数）である。商Q は、すべての特徴量に対して一意に決定される。つまり、同一の特徴ベクトルからは、同一のHindex と商Q が得られる。検索処理では文書画像データベースに登録された各特徴点の中で、検索質問から抽出された各特徴点に対応する特徴点を探索するところ、その探索は、インデックスHindex の照合と商Q の照合とに分割できる。即ち、検索質問から抽出された各特徴点と等しいインデックスHindex を有する類のビンに探索の対象をまず絞り込むことができる。次いで、そのビンに登録された特徴点と検索質問から抽出された特徴点とを照合する。同一ビンに登録された特徴点との照合は、特徴ベクトルの（mC4 ＋m ）次元どうしの比較に代えて、商Q どうしの比較で済ませることができる。商Q は、照合用に特徴量を簡略化した特性値といえる。
【００４７】
そこで図２に示すように、文書ID、点ID、商Q のデータ組をハッシュ表に登録する。ハッシュ表は、インデックス（ここでは、Hindex の値）ごとに区画されたビン構造を有し、登録すべきデータをインデックスの値に応じたビンに分類して登録するデータ構造である。LLAH でハッシュ表に登録されるデータは、前述のように文書ID、点ID、商Q のデータ組である。ここで、文書ID とは文書画像の識別番号であり、前述の参照符号に相当するものである。点ID とは文書画像の他の特徴点と区別するためその特徴点に付される固有の番号である。データはインデックスの値に応じたビンに登録される。登録すべきデータの中にインデックス値が等しいものが複数個存在する場合、それらのデータを同一のビンに登録しなければならない。この状態をハッシュの衝突と呼ぶ。衝突が生じた場合は、それらのデータをリスト形式でビンに登録する。リストの長さには制限値を設けておく。その制限値を超えた場合、リストでリンクされた全てのデータをインデックスごと削除する。以降、削除されたインデックスは使用しないこととする。即ち、そのインデックス値に応じたデータ組は、ハッシュ表に登録しない。それらのデータ組に係る特徴点は、類似するものが多く検索に有用でないと考えられるからである。なお、メモリ使用量を削減するため、ハッシュの衝突が生じるリストを全て削除し、ハッシュ表を単純化する手法は、既に提案されている（例えば、特許文献２の明細書段落００４４、００４５参照）。
【００４８】
５．検索処理
検索の段階では、検索質問から特徴点を抽出し、各特徴点の特徴量を算出してインデックス（Hindex の値）および商Q を得る。得られたインデックスを用いて、対応するビンに登録されたデータ組があればそれを参照する。参照したデータ組について商Q が一致するかを調べる。個別の特徴点探索である。検索質問から抽出された各特徴点について個別の特徴点探索を行う。参照したデータ組の商Q が一致していたら、そのデータ組の文書ID に投票を行う。これが投票処理である。文書ID ごとに初期値ゼロのカウンタが設けられた投票テーブルが用意されている。コンピュータは、投票テーブルの文書ID のうち、投票すべき文書ID のカウンタをインクリメントする。検索質問の各特徴点につきハッシュ表を参照し、ビンの内容に応じて投票を行う。最大の得票数を得た文書ID が付された文書画像を、正解画像として出力する。
【００４９】
≪この発明によるLLAH の改良点≫
１．メモリ使用量の削減
従来のLLAH では、特徴点抽出処理において得られたすべての特徴点を、原則としてハッシュ表に保存する。ハッシュの衝突回数（リストの長さ）が制限値を超えた場合のみが例外である。そのため、メモリ使用量が多くなる。しかし、すべての特徴点を保存しなくとも、検索はできると考えられる。これは、検索に投票処理を用いているためである。そこで、特徴点のサンプリングを行い、ハッシュに保存するデータ量を削減する。これによって、メモリ使用量の削減を図るのである。
【００５０】
特徴点をサンプリングする際に注意しなければならないのは、ハッシュに登録する特徴点に、位置的な偏りが生じないように考慮することである。
文書画像中の特徴点の分布に疎密ができると、疎な部分では正解画像が十分な得票数を得ることができず、精度の低下を招くと考えられる。
つまり、撮影範囲にロバストであるためには、サンプリングされる特徴点がある程度均等に分散して分布していなければならない。
【００５１】
さらに、サンプリングされる特徴点が、検索に有効なものであることも重要である。
そこでこの発明では、連結成分の面積に着目してサンプリングを行う。サンプリングの例を図３に示す。図３は、文書画像の一部を示している。なお、S0 〜S6 は６つの連結成分の重心として得られるそれぞれの特徴点を示す符号である。いま、中央部の“in”という単語に注目すると、その連結成分は、周囲の連結成分より面積が小さいことがわかる。サンプリングでは、このような連結成分から抽出した特徴点S0 を有効な特徴点として採用する。周囲より面積の小さい連結成分は、字数の少ない連結成分であって、前置詞や冠詞なとどして文書中に頻出する。よって、位置的に偏りのないサンプリングが行えると考えられる。
【００５２】
また、連結成分の面積が小さいということは、近傍の特徴点との距離が小さくなるということである。近傍の特徴点S1 〜S6 との距離が小さければ小さいほど、射影歪みの影響を受けにくく、安定した特徴量が得られると考えられる。しかし、これだけではハッシュに登録される特徴点数が少なすぎる場合が考えられる。そのため、サンプリングした特徴点の近傍k 点もハッシュに登録する。この実施形態では、登録する特徴点数が１文書あたり約200 点となるよう、k の値を設定する。従って、特徴点数が200 点に満たない文書画像に対しては特徴点のサンプリングを行なわず、すべての特徴点をハッシュに登録する。また、検索時にサンプリングの有無を判別することは困難である。そのため、検索時には、検索質問から得られた全ての特徴点についてハッシュを参照する。
【００５３】
２．特徴点の識別性・安定性の向上
データベースの大規模化に伴い、ハッシュ表に登録される特徴量は膨大になる。そのため、一般的にハッシュの衝突回数が増加すると考えられる。換言すれば、類似の特徴点が増えると考えられる。そのため、誤投票が増加することになり、検索精度に影響が出ると考えられる。しかし、ハッシュの衝突回数を抑えるためにその制限値を低く設定すれば、それに伴って削除されるデータ組が大量に出現すると考えられる。従って、検索に必要なデータまで削除されてしまい、検索精度が低下すると考えられる。以上のことから、特徴点の識別性を高め、衝突回数を抑制する必要がある。異なる特徴点と区別され易くするということである。
【００５４】
識別性向上の基本的な考えは、特徴量の次元数を増加させることである。従来のLLAH では、着目する特徴点S0 の特徴量計算に用いる点S0 の近傍の特徴点数をn = 7，m = 6 として、21次元の特徴量を用いている。従来のLLAH では、登録するページ数を10,000 程度に想定しているため、この次元数でも特徴点は十分な識別性を持つ。また、低次元の特徴量を使用することにより、安定性を高めているとも考えられる。
この発明では、特徴点S0 の近傍の特徴点数をn = 8，m = 7 とすることによって、次元数を増加させる。具体的には、アフィン不変量ベクトルが7C4 = 35 次元、面積比特徴量が7 次元となり、合計42 次元の特徴量を得ることができる。従来のLLAH に比べて２倍の次元数である。
【００５５】
ただし、特徴量の次元数を単純に増加させると安定性の面で不利益が伴う。m の値が大きければ大きいほど、計算される不変量の数が多くなる。そのため、検索質問に係る特徴点と同じ特徴量を有する特徴点が、その検索質問と無関係な文書画像中に偶然に現れる可能性は低くなる。しかし、検索質問の特徴点と正解画像の特徴点の特徴量が一致するためには、特徴量がすべての次元で一致する必要がある。しかし、特徴量の次元数が増加すると、射影歪み、ノイズおよび／または解像度の違い等による誤差の影響で、対応すべき特徴点から異なる特徴量が算出されてしまう可能性が高くなる。よって、特徴量の次元数を増加させると特徴点の識別性は向上するが、それと引き換えに、特徴点の安定性が低下するというジレンマが生じる。
そこで、この発明では、前述のジレンマを解決するため、特徴量から互いに関連性のある次元を削除する。
【００５６】
互いに関連性のある次元は、次のように考える。従来のLLAH で、特徴量の計算は、図４で示すように、異なるアフィン不変量の計算に同一の三角形を重複して使用する。ここで、異なるアフィン不変量とは、従来のLLAH における特徴点抽出処理の項目で述べたごとく、mC4個の数値の列（r(0), r(1), …, r(mC4) ）を構成する各数値のことである。重複した三角形を使用する不変量は互いに関連があるといえる。そして、この関連性は、一種の冗長性と考えることができる。
【００５７】
図４で、特徴点S0 の近傍に特徴点S1, S2, S3, S4, S5, S6 が特徴点S0 を取り囲むように存在する。特徴点S0 に係るアフィン不変量は、図４の右側に示す不変量１、不変量２および不変量３を含む。不変量１は、頂点が特徴点S0, S1, S2 からなる三角形１と、特徴点S0, S2, S3 からなる三角形２の面積比として算出される。不変量２は、三角形２と、頂点が特徴点S0, S3, S4 からなる三角形３の面積比として算出される。不変量３は、三角形３と、頂点が特徴点S0, S4, S5 からなる三角形４の面積比として算出される。不変量２は、三角形２を重複使用する点で不変量１と関連が高く、三角形３を重複使用する点で不変量３と関連が高い。よって、三角形２および三角形３の何れも重複使用する不変量２は、前述の冗長性があると考えられる。
【００５８】
この不変量２のような次元を削除するのである。結果、特徴量計算に使用されるいずれの三角形も、異なる不変量の計算に重複して使用されることがない。冗長性のある次元の削除により、情報の損失を抑えつつ特徴量の安定性向上を図る。当初の35次元のアフィン不変量ベクトルは、冗長性のある次元を削除することによって約半分の17次元にまで削減される、面積比特徴量7 次元との合計は24 次元となる。
これまでに説明した改良されたLLAH は、コンピュータに所定の処理を行わせるための処理プログラムの態様、その処理プログラムをコンピュータ読取り可能に記憶する不揮発性の記憶媒体の態様、およびその処理プログラムをコンピュータが実行することにより改良されたLLAHの機能を実現するシステムの態様として捉えることができる。
【００５９】
≪実験例≫
１．実験例１：改良されたLLAH の効果
前述のメモリ使用量の削減と、特徴点の識別性・安定性向上の効果を明確にするため、以下の３つのバージョンのLLAH を作成した。
ｉ．従来のLLAH 手法
ii．メモリ使用量削減版
iii．メモリ使用量削減版に識別性、安定性向上処理を加えた総合版
ｉは比較の基準となる従来のLLAH であり、iiおよびiiiが改良されたLLAH に係るものである。
【００６０】
実験で用いた文書画像データベースの登録ページ数は10,000 である。
登録された文書画像は、主に予稿集のCD-ROM から集められた、１段組および２段組の英語論文である。それらの英語論文は、PDF ファイルを解像度200dpi で画像に変換したものである。登録された文書画像の一例を図５に示す。検索質問として、印刷文書を紙面に対して斜め方向（約60°）から文書全体を撮影した画像を1003 枚用意した。撮影には、1200万画素のデジタルカメラを用いた。検索質問画像の一例を図６に示す。登録画像と検索質問の撮影角度は異なる。登録されたものと異なる撮影角度の検索質問は、各バージョンの射影歪みに対するロバスト性を明らかに示すことができる。ハッシュ表のサイズは230−1 である。実験に用いたコンピュータは、CPU がAMD 社製のOpteron（登録商標）、CPUクロック周波数が2.8GHz、メモリ容量が128GB のものである。
以下の表１に結果を示す。表１で、「使用メモリ」はハッシュ表に格納されるデータ量を表している。データ構造としてのハッシュ表自体に使用されるメモリ容量は含まれていない。
【００６１】
【表１】
【００６２】
また「正投票率」は、検索で見つかった対応点数のうち、正解画像に対応したものの割合を表す。正投票率の割合が高いほど、識別性・安定性が高いことを示す。
iiのメモリ削減版は、従来手法と比較して、約70% のメモリ削減を実現した。これは、従来手法でハッシュに登録していた特徴点数の約70% を削除したことと同義である。また、iiiの総合版は、従来手法と比較して、約65% のメモリ削減を実現した。これだけの特徴点を削除したにも関わらず、精度には全く影響がなかった。その理由の一つとして、本実験で用いた検索質問が、文書全体を撮影したものであるということが挙げられる。そこで、撮影範囲の違いによる精度への影響を検証する必要があるが、これについては後の「部分撮影への耐性」の項目で述べる。
【００６３】
次に、iiのメモリ削減版とiiiの総合版とを比較すると、メモリ使用量が10MB 増加している。これは近傍特徴点数n の値を変えることにより、１つの特徴点から得られる特徴量が増加するためである。また、誤投票が約20% 低下していることから、特徴量の識別性が向上していると考えられる。さらに、精度には全く影響がないことから、特徴量の安定性も確保できていると考えられる。処理時間が3ms 増加しているが、これは１つの特徴点で計算されるアフィン不変量の数が増加するためである。
以上のことから、改良されたLLAH は、精度を低下させることなくメモリ使用量の削減を実現し、さらに、メモリ使用量の削減と特徴点の識別性、安定性の向上を実現しているといえる。
【００６４】
２．実験例２：大規模化への対応
文書画像データベースの大規模化に対する改良されたLLAH のスケーラビリティを検証した。登録ページ数を1 万、10 万、100 万、1,000万とした4つの異なるデータベースを作成し、登録ページ数と必要メモリ量、検索精度、処理時間の関係をそれぞれ調べた。実験例２における改良されたLLAHは、実験例１におけるiiiの総合版に対応する。
比較のために、従来のLLAH 手法の結果を併記した。検索質問は、実験例１と同じものを使用した。ハッシュ表のサイズは230−1 、リスト長の制限値は100 である。
【００６５】
２−１．必要メモリ量
文書画像データベースへの登録ページ数と必要メモリ量の関係を図7 に示す。ここで必要メモリ量は、検索するために必要なすべてのメモリ使用量を表す。また、ハッシュ表を確保するためにメモリを8GB 使用している。従来手法では1,000 万ページのデータベースは作成不可能なため、100 万から1,000 万までは推定値を表す。どちらの手法も、登録ページ数が増加するに伴い、必要メモリ量も増加した。ただし、従来のLLAH と比較して、改良されたLLAH の必要メモリ量は約50% 程度となっていることがわかる。
【００６６】
２−２．検索精度
登録ページ数と検索精度の関係を図８に示す。改良されたLLAH は、従来のLLAH よりも高い検索精度を示した。また、改良されたLLAH では1,000 万ページの文書画像データベースにおいて99.4% という高い精度で検索可能であることが確認された。これより、改良された特徴量は、大規模化に耐え得る高い識別性と安定性を備えていると考えられる。しかし、登録ページ数の増加に伴い、検索精度が低下した。大規模化に伴い検索に失敗した例を図９に示す。この画像のように、ページの大部分を図表が占め、テキストの量が少ない検索質問で検索に失敗した。これは、得られる特徴点の数が少ないため、正解の文書が十分な得票数を得られないことが原因であると考えられる。
【００６７】
２−３．処理時間
登録ページ数と処理時間の関係を図１０に示す。登録ページ数の増加と比較して、処理時間の増加は抑制されている。これは、ハッシュを用いて検索することによる効果であると考えられる。また、1,000 万ページの文書画像データベースにおいて、38ms で検索可能であることが確認された。従って、改良されたLLAH は、1,000万ページの文書画像データベースにおいて実時間検索が可能であるといえる。
【００６８】
文書画像データベースの大規模化に伴い、従来のLLAH と改良されたLLAH とで処理時間の逆転が起こった。登録ページ数が少ない場合、従来のLLAH の処理時間がより短い。これは特徴点あたりの特徴量数と、特徴量あたりのアフィン不変量数の相違による。従来のLLAH では、7C6 = 7 個の特徴量と、特徴量あたり6C4 = 15 個の不変量を計算する。改良されたLLAH では、8C7 = 8 個の特徴量と、24 個の不変量を計算する。このように、従来のLLAH の計算量は改良されたLLAH よりも少ないため、処理時間が短くなったと考えられる。
【００６９】
しかし、登録ページ数の増加に伴い、改良されたLLAH は従来のLLAH より高い性能を示した。これは、ハッシュ表におけるリスト長の違いが原因であると考えられる。ここで、ハッシュ表においてリスト長がゼロでないもののリスト長の平均を図１１に示す。従来のLLAH と改良されたLLAH の何れも、登録ページ数の増加に伴って、平均リスト長が増加していることがわかる。
【００７０】
特に、100 万ページの文書画像データベースにおいて、従来のLLAH が改良されたLLAH に比べて約２倍のリスト長となっている。リスト長が大きくなると、リストをたどるために要する処理時間が増加する。従来のLLAHは、その部分でより多くの処理時間を要する。そのため、処理時間の逆転が起こったと考えられる。以上のことから、登録ページ数が増加すればするほど、改良されたLLAH は、処理時間の点で従来のLLAHよりも有利になると考えられる。
【００７１】
３．実験例３：部分撮影への耐性
実験例１で述べたように、改良されたLLAH で高い検索精度となっている理由の１つに、検索質問が文書画像全体を写していることが挙げられる。文書画像全体を撮影することにより、参照する特徴点数が増加し、正解画像が多くの得票数を得ることができるためである。文書画像の一部分が撮影された検索質問では、特徴点数が減少するために精度が低下すると考えられる。そこで、文書画像の一部分を撮影した検索質問を作成し、部分撮影への耐性を検証した。
【００７２】
実験例３で用いる文書画像データベースには、1,000 万ページの文書画像が登録されている。まず、実験例１および２で用いた検索質問から、図表が大半を占めるものを除いた989 枚を選択した。次に、それらの検索質問から文章が写っている部分を切り抜き、疑似的な部分撮影クエリを作成した。撮影範囲の大きさとして、全体の１／２，１／４，１／８の３パターンを用意した。撮影範囲の例を、それぞれ図１２、図１３および図１４に示す。
【００７３】
結果を図１５に示す。撮影範囲が狭くなるに伴い、検索精度が低下することがわかる。これは、検索質問から得られる特徴点数が少なく、正解画像が十分な得票数を得られないことが原因と考えられる。検索に失敗した例を図１６に示す。このように、文章の中に「．」や「”」が数多く分布していると、検索に失敗する傾向があった。これは、それらがノイズとなって、安定した特徴点を抽出することが困難であるためである。図１７に、検索に失敗したときの特徴点の例を示す。図１７の（ａ）および（ｂ）のそれぞれについて、左側が検索質問、右側に登録文書画像を表す。（ａ）のように「”」が連結成分から離れて新たな特徴点となったり、（ｂ）のように「．」が特徴点として抽出されなかったりする事象が生じる。これは、特徴点抽出処理における適応二値化による影響であると考えられる。これについては、特徴点抽出に新たな処理を追加する等の改良が必要である。
【００７４】
４．実験例４：特徴点の間引きと特徴量選択の効果
これまでに述べた実験例は、特徴点をサンプリングしてメモリ使用量を削減する手法（以下、間引きと呼ぶ）と特徴量の識別性を向上させつつ安定性を確保するために特徴量の冗長性を排除する手法（以下、特徴量選択と呼ぶ）とを組み合わせた態様である。次に、それらの手法の単独の効果を確認する実験を行った。
まず、間引き有無、特徴量選択有無の態様を組み合わせ、必要メモリ量、検索精度および処理時間を確認した。ただし、間引きがないと必要なメモリ量が膨大になってしまい現行の実験装置が対応できない。そのため、登録ページ数100万で実験を行った。結果を表２に示す。
【００７５】
【表２】
【００７６】
表２を見ると、特徴量選択なしの条件下で間引きなしの使用メモリ量は16.2 GB対し、間引きありでは6.4 GBである。また、特徴量選択ありの条件下で間引きなしの使用メモリ量は18.7 GBに対し、間引きありでは7.3 GBである。メモリ使用量の削減については、特徴量選択の効果はあまりなく、間引きの効果が目立つ。特徴量選択の有無による検索精度の差はそれほど大きくないようにも見える。しかし、登録ページ数が1000万ページになると、特徴量選択を行わない検索精度の差がより大きくなる。
続いて、登録ページ数1000万ページで、特徴量選択の有無による違いを比較した。結果を表３に示す。
【００７７】
【表３】
【００７８】
表３で、「必要メモリ量」は、検索に必要なすべてのメモリ使用量である。「処理時間」は、特徴点抽出処理にかかる時間を含まない。「平均リスト長」は、ハッシュにおいてリスト長がゼロでないものの平均値である。「ハッシュ表の使用率（以下，使用率）」は、リスト長がゼロでないものの割合である。
特徴量選択の有無で必要メモリ量に違いがあるのは、主として特徴点１つあたりに計算される特徴量数（特徴ベクトルの次元数）の違いによるものである。特徴量選択なしの場合は21 次元、特徴量選択ありの場合は24 次元である。
【００７９】
特徴量選択ありでの検索精度99.4 %に対して特徴量なしの検索精度は98.6 %に下がっている。精度100 %からの差分で考えたときの検索誤りの割合は、約２倍の差がある。特徴量選択なしにおける検索精度の低下は、誤投票の増加によるものと考えられる。しかし、特徴量選択の有無で平均リスト長がほぼ同じであるため、誤投票の増加が衝突回数の増加によるものかわからない。そこでハッシュ表のリスト長の頻度を調べた。その結果を図１８に示す。
【００８０】
図１８から、特徴選択なしの場合は、特徴量選択ありの場合に比べてリスト長の長いものが多いことがわかる。これが誤投票の増加につながったと考えられる。
以上の結果から、特徴点の間引きは、メモリ使用量の削減に大きく寄与している一方、特徴量の選択は検索精度の向上に寄与していることがわかる。
登録ページ数が1000万におよぶ大規模な文書画像データベースへの対応には、いずれの手法も非常に有効なものといえる。
【産業上の利用可能性】
【００８１】
改良されたLLAH では、大規模文書画像検索に対応するために、所要メモリ量の削減と、特徴点の識別性・安定性の向上の点で改良を行った。その結果、実験により1,000 万ページデータベースにおいて精度99.4% 、処理時間38ms で検索が可能であることが確かめられた。以上のことから、改良されたLLAH では、スケーラビリティが向上したといえる。
【００８２】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００８３】
S0、S1、S2、S3、S4、S5、S6：特徴点
【特許請求の範囲】
【請求項１】
コンピュータが、
文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、
幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、
前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出し、
前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算することを特徴とする文書画像データベースの登録方法。
【請求項２】
前記登録ステップは、（１）前記参照子、（２）前記識別子および（３）前記特徴量またはその特徴量を簡略化した簡易特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記特徴量に応じて各特徴点を分類すべく予め定義された計算を行ってその特徴点が属する類のインデックスを得、インデックスに応じた類に前記データ組を分類し、前記文書画像と共に前記文書画像データベースに登録する請求項１に記載の登録方法。
【請求項３】
前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量とする請求項１または２に記載の登録方法。
【請求項４】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項１に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【請求項５】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項２に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されている特徴点の中から、各クエリ特徴点と局所的特徴が類似する特徴点を探索し、見出された類似の特徴点に関連づけられた参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とし、
前記個別探索ステップは、請求項２に記載の登録方法に対応する計算によって各クエリ特徴点のインデックスを得、そのインデックスに係る類として登録されたデータ組を参照し、そのデータ組が簡易特徴量を有する場合は前記クエリ特徴点に係る簡易特徴量を求めたうえで同一もしくは最も類似の簡易特徴量を有するデータ組に係る参照子を得、登録されたデータ組が特徴量を有する場合は同一もしくは最も類似の特徴量を有するデータ組に係る参照子を得ることを特徴とする文書画像の検索方法。
【請求項６】
前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量とする請求項４または５に記載の検索方法。
【請求項７】
コンピュータが、
文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、
幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、
前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出することを特徴とする文書画像データベースの登録方法。
【請求項８】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項１に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【請求項９】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項８に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【請求項１】
コンピュータが、
文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、
幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、
前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出し、
前記特徴量計算ステップは、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算することを特徴とする文書画像データベースの登録方法。
【請求項２】
前記登録ステップは、（１）前記参照子、（２）前記識別子および（３）前記特徴量またはその特徴量を簡略化した簡易特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記特徴量に応じて各特徴点を分類すべく予め定義された計算を行ってその特徴点が属する類のインデックスを得、インデックスに応じた類に前記データ組を分類し、前記文書画像と共に前記文書画像データベースに登録する請求項１に記載の登録方法。
【請求項３】
前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量とする請求項１または２に記載の登録方法。
【請求項４】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項１に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【請求項５】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項２に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されている特徴点の中から、各クエリ特徴点と局所的特徴が類似する特徴点を探索し、見出された類似の特徴点に関連づけられた参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とし、
前記個別探索ステップは、請求項２に記載の登録方法に対応する計算によって各クエリ特徴点のインデックスを得、そのインデックスに係る類として登録されたデータ組を参照し、そのデータ組が簡易特徴量を有する場合は前記クエリ特徴点に係る簡易特徴量を求めたうえで同一もしくは最も類似の簡易特徴量を有するデータ組に係る参照子を得、登録されたデータ組が特徴量を有する場合は同一もしくは最も類似の特徴量を有するデータ組に係る参照子を得ることを特徴とする文書画像の検索方法。
【請求項６】
前記特徴量計算ステップは、３つの特徴点を頂点とする三角形を前記幾何学的要素としてその三角形の面積を前記特性値とし、４つ以上の特徴点の何れか３点を頂点とする三角形の組み合わせのうち一辺を共有する２つの三角形の面積比を一つの不変量とする請求項４または５に記載の検索方法。
【請求項７】
コンピュータが、
文書画像データベースに登録すべき文書画像から、その文書画像の局所的特徴を表す特徴点を抽出する特徴点抽出ステップと、
幾何学的変換に対する不変量を用いた各特徴点の特徴量であって、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とする特徴量計算ステップと、
前記文書画像から抽出された各特徴点について、（１）前記文書画像の参照に用いる参照子、（２）その特徴点を他の特徴点と区別する識別子および（３）その特徴点の特徴量の前記（１）〜（３）を関連付けてなるデータ組を生成し、前記データ組を前記文書画像と共に前記文書画像データベースに登録する登録ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、所定面積より小さい連結成分の重心を特徴点として抽出し、抽出された特徴点の数が閾値に満たないとき、各特徴点の近傍にある連結成分の重心をさらに特徴点として抽出して閾値以上の特徴点が得られるように抽出することを特徴とする文書画像データベースの登録方法。
【請求項８】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項１に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、かつ、一の不変量に用いた幾何学的要素と重複しない幾何学的要素を他の不変量に用いて各不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【請求項９】
コンピュータが、
検索質問として取り込まれた文書画像から、その文書画像の局所的特徴を表す複数のクエリ特徴点を抽出する特徴点抽出ステップと、
各クエリ特徴点に係るクエリ特徴量を計算する特徴量計算ステップと、
請求項８に記載の登録方法により文書画像が登録された文書画像データベースを参照し、その文書画像データベースに登録されているデータ組の中から、各クエリ特徴点と同一もしくは類似の特徴量を有するデータ組を探索し、見出されたデータ組の参照子を得る個別探索ステップと、
各クエリ特徴点について探索を行い、得られた各文書識別子を統計的に処理し、検索結果として推奨すべき文書画像を特定する投票ステップとを実行し、
前記特徴点抽出ステップは、文書を構成する文書を構成する線の連結成分を決定し、各連結成分の重心を特徴点として抽出し、
前記特徴量計算ステップは、各特徴点とその近傍n 個（n は自然数）の特徴点とで定まる複数の幾何学的要素に対して所定の演算によりそれぞれの特性値を求め、それらの特性値を組み合わせてなる複数の不変量を計算し、算出された不変量を各次元とするベクトルを前記特徴量とすることを特徴とする文書画像の検索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１２−１８１７６５（Ｐ２０１２−１８１７６５Ａ）
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願番号】特願２０１１−４５５１３（Ｐ２０１１−４５５１３）
【出願日】平成２３年３月２日（２０１１．３．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人科学技術振興機構、戦略的創造研究推進事業、ならびに平成２２年度、日本学術振興会、科学研究費補助金 基盤研究（Ｂ）、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願日】平成２３年３月２日（２０１１．３．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人科学技術振興機構、戦略的創造研究推進事業、ならびに平成２２年度、日本学術振興会、科学研究費補助金 基盤研究（Ｂ）、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
[ Back to top ]