(57)【要約】【課題】  撮影対象に対してインデックスを付与する際に、正しい検索結果が得られる確率が向上し、マッチングに要する計算コストの削減を可能にする。【解決手段】  本発明は、入力されたドキュメント内の文字領域を特定し、各文字領域の周辺領域を特定し、周辺領域の中で該背景領域と異なるものを部分画像領域と判定し、文字領域と該文字領域の周囲にある部分画像領域と、該文字列が出現するドキュメントにおける出現位置を関連付けてインデックスＤＢに出力する。また、入力された検索対象画像内の文字領域を特定し、各文字領域の周辺領域を特定し、各周辺領域と検索対象画像の背景領域を比較し、周辺領域の中で背景領域と異なるものを部分画像領域と判定し、文字領域と、該文字領域の周囲にある部分画像領域が出現するドキュメントまたはドキュメント内における位置をインデックスＤＢに問い合わせ、問い合わせの結果を出力する。【選択図】  図１
2011129070.tif 000002
【特許請求の範囲】
【請求項１】
改ページや改行位置が確定しており、文字列を含むドキュメント内の、文字列を含む一部領域を検索クエリとして、該領域が出現するドキュメント及び該ドキュメント内における位置を取得する検索要求に応えるための検索インデックスを作成し、検索を行う検索装置であって、
インデックス作成対象のドキュメント群の入力を受け付けるドキュメント群入力手段と、
文字領域抽出方法を用いて前記ドキュメント内の文字領域を特定する文字領域特定手段と、
前記各文字領域の周囲に存在する領域である周辺領域を特定する周辺領域特定手段と、
画像特徴比較手法を用いて、前記各周辺領域と前記ドキュメントの背景領域を比較し、該周辺領域の中で該背景領域と異なるものを部分画像領域と判定する部分画像特定手段と、
前記文字領域と、該文字領域の周囲にある前記部分画像領域と、該文字列が出現するドキュメントにおける出現位置を関連付けてインデックスＤＢに出力するインデックス出力手段と、
を有することを特徴とする検索装置。
【請求項２】
前記ドキュメントは、画像も含み、
前記ドキュメント内の、画像及び文字列を含む一部領域を検索クエリとする
請求項１記載の検索装置。
【請求項３】
画像と文字列を含むドキュメントの一部領域を撮影した画像の入力を受け付ける検索対象画像入力手段と、
文字領域抽出方法を用いて前記検索対象画像内の文字領域を特定する検索対象文字領域特定手段と、
前記各文字領域の周囲に存在する領域である周辺領域を特定する検索対象周辺領域特定手段と、
画像特定比較手法を用いて、前記各周辺領域と前記検索対象画像の背景領域を比較し、周辺領域の中で背景領域と異なるものを部分画像領域と判定する検索対象部分画像特定手段と、
前記文字領域と、該文字領域の周囲にある前記部分画像領域が出現するドキュメントまたはドキュメント内における位置を、前記インデックスＤＢに問い合わせる問い合わせ手段と、
前記問い合わせの結果を出力する検索結果出力手段と、
を更に有する請求項１または２記載の検索装置。
【請求項４】
前記問い合わせ手段は、
事前に各ドキュメントの位置とコンテンツを関連付けたデータベースにアクセスし、検索結果であるドキュメント位置に関連付けられたコンテンツを検索結果として得る手段を含む
請求項３記載の検索装置。
【請求項５】
改ページや改行位置が確定しており、文字列を含むドキュメント内の、文字列を含む一部領域を検索クエリとして、該領域が出現するドキュメント及び該ドキュメント内における位置を取得する検索要求に応えるための検索インデックスを作成し、検索を行う装置における検索方法であって、
ドキュメント群入力手段が、インデックス作成対象のドキュメント群の入力を受け付けるドキュメント群入力ステップと、
文字領域特定手段は、文字領域抽出方法を用いて前記ドキュメント内の文字領域を特定する文字領域特定ステップと、
周辺領域特定手段が、前記各文字領域の周囲に存在する領域である周辺領域を特定する周辺領域特定ステップと、
部分画像特定手段が、画像特徴比較手法を用いて、前記各周辺領域と前記ドキュメントの背景領域を比較し、該周辺領域の中で該背景領域と異なるものを部分画像領域と判定する部分画像特定ステップと、
インデックス出力手段が、前記文字領域と、該文字領域の周囲にある前記部分画像領域と、該文字列が出現するドキュメントにおける出現位置を関連付けてインデックスＤＢに出力するインデックス出力ステップと、
を行うことを特徴とする検索方法。
【請求項６】
前記ドキュメントは、画像も含み、
前記ドキュメント内の、画像及び文字列を含む一部領域を検索クエリとする
請求項５記載の検索方法。
【請求項７】
検索対象画像入力手段が、画像と文字列を含むドキュメントの一部領域を撮影した画像の入力を受け付ける検索対象画像入力ステップと、
検索対象文字領域特定手段が、文字領域抽出方法を用いて前記検索対象画像内の文字領域を特定する検索対象文字領域特定ステップと、
検索対象周辺領域特定手段が、前記各文字領域の周囲に存在する領域である周辺領域を特定する検索対象周辺領域特定ステップと、
検索対象部分画像特定手段が、画像特定比較手法を用いて、前記各周辺領域と前記検索対象画像の背景領域を比較し、周辺領域の中で背景領域と異なるものを部分画像領域と判定する検索対象部分画像特定ステップと、
問い合わせ手段が、前記文字領域と、該文字領域の周囲にある前記部分画像領域が出現するドキュメントまたはドキュメント内における位置を、前記インデックスＤＢに問い合わせる問い合わせステップと、
検索結果出力手段が、前記問い合わせの結果を出力する検索結果出力ステップと、
を更に行う請求項５または６記載の検索方法。
【請求項８】
前記問い合わせステップにおいて、
事前に各ドキュメントの位置とコンテンツを関連付けたデータベースにアクセスし、検索結果であるドキュメント位置に関連付けられたコンテンツを検索結果として得るステップを更に行う
請求項７記載の検索方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の検索装置を構成する各手段としてコンピュータを機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置及び方法及びプログラムに係り、特に、画像と文字列のレイアウトが確定しているドキュメント内の領域を検索クエリとして、該領域が出現するドキュメント及びドキュメント内の各位置のインデックスを作成し、検索を実行する検索装置及び方法及びプログラムに関する。
【０００２】
特に、画像と文字列のレイアウトが確定しているドキュメント内の領域を含む可能性があるドキュメント及びドキュメント内における位置を網羅意的に取得するのではなく、一意に特定したい場合に適用される検索装置及び方法及びプログラムに関する。
【背景技術】
【０００３】
ドキュメントの一部領域から、該領域がどのドキュメントに含まれているか、あるいは、どのドキュメントのどの位置に含まれているか一意に特定することが必要なシーンは少なくない。
【０００４】
例えば、手元にカタログの切り抜きがある場合、切り抜いた元のカタログを探して、切り抜きの続きを読みたいことがある。この場合、当該切り抜きがどのカタログの一部であったか一意に特定できる必要がある。
【０００５】
上記の事例は、ドキュメントの一部領域をクエリとし、膨大な量のドキュメント群の中から、該領域を含むドキュメント名、あるいはドキュメント名及びドキュメントにおける位置を問い合わせる検索システムと捉えることができる。
【０００６】
上記の検索システムを実現する一例として、予めドキュメント内の各画像の全体領域の色分布情報をデータベースに格納しておき、ドキュメント内にある画像の全体領域の色分布情報を検索クエリとし、該画像と色分布情報が一致する画像を含むドキュメント名、あるいは、ドキュメント名及びドキュメントにおける位置をデータベースに問い合わせる検索システムが考えられる（例えば、非特許文献１参照）。
【０００７】
あるいは、各画像の部分領域のマッチングのみで検索を行うシステムもある。例えば、予めドキュメント内の各画像を既定数の複数の部分領域として分割し、各部分領域の色分布情報をデータベースに格納しておく。次に、ドキュメント内のある画像を既定数の複数の部分領域として分割し、各部分領域の色分布情報を検索クエリとし、該部分領域と色分布情報が一致する部分領域を含むドキュメント名、あるいは、ドキュメント名及びドキュメントにおける位置をデータベースに問い合わせる検索システムが考えられる（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M. J. Swain and D. H. Ballard, "Color Indexing," International Journal of Computer Vision, Vol. 7, pp. 11-32, 1991
【非特許文献２】WALRUS: A Similarity Retrieval Algorithm for Image Databases, Apostol Natsev, Rajeev Rastogi and Kyuseok Shim, IEEE Transaction on Knowledge and Data Engineering, Vol. 16, No.3, pp. 301-316, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
各画像の全体領域の色分布情報をデータベースに格納して、ある画像の全体領域の色分布情報を検索クエリとする方法は、データベース内の情報と検索クエリのマッチング処理がシンプルである一方、画像の全体領域を検索クエリに含めなければならないという問題がある。
【００１０】
一方、各画像の部分領域の色分布情報をデータベースに格納して、ある画像の部分領域の色分布情報を検索クエリとする方法は、画像の全体領域を検索クエリに含めなくてもよい一方、データベース格納時及び検索実行時に画像を複数領域の部分領域に分割し、データベース内及び検索クエリの部分領域同士で色分布情報のマッチングをとるため、マッチングをとる回数が大幅に増加するという問題がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、撮影対象に対してインデックスを付与する際に、正しい検索結果が得られる確率が向上し、マッチングに要する計算コストの削減が可能な検索装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
図１は、本発明の原理構成図である。
【００１３】
本発明（請求項１）は、改ページや改行位置が確定しており、文字列を含むドキュメント内の、文字列を含む一部領域を検索クエリとして、該領域が出現するドキュメント及び該ドキュメント内における位置を取得する検索要求に応えるための検索インデックスを作成し、検索を行う検索装置であって、
インデックス作成対象のドキュメント群の入力を受け付けるドキュメント群入力手段１０と、
文字領域抽出方法を用いてドキュメント内の文字領域を特定する文字領域特定手段１１と、
各文字領域の周囲に存在する領域である周辺領域を特定する周辺領域特定手段１２と、
画像特徴比較手法を用いて、各周辺領域とドキュメントの背景領域を比較し、該周辺領域の中で該背景領域と異なるものを部分画像領域と判定する部分画像特定手段１３と、
文字領域と、該文字領域の周囲にある部分画像領域と、該文字列が出現するドキュメントにおける出現位置を関連付けてインデックスＤＢ１５に出力するインデックス出力手段１４と、を有する。
【００１４】
また、本発明（請求項２）は、請求項１の検索装置において、
ドキュメントは、画像も含み、
ドキュメント内の、画像及び文字列を含む一部領域を検索クエリとする。
【００１５】
また、本発明（請求項３）は、請求項１または２の検索装置において、
画像と文字列を含むドキュメントの一部領域を撮影した画像の入力を受け付ける検索対象画像入力手段と、
文字領域抽出方法を用いて検索対象画像内の文字領域を特定する検索対象文字領域特定手段と、
各文字領域の周囲に存在する領域である周辺領域を特定する検索対象周辺領域特定手段と、
画像特定比較手法を用いて、各周辺領域と検索対象画像の背景領域を比較し、周辺領域の中で背景領域と異なるものを部分画像領域と判定する検索対象部分画像特定手段と、
文字領域と、該文字領域の周囲にある部分画像領域が出現するドキュメントまたはドキュメント内における位置を、インデックスＤＢに問い合わせる問い合わせ手段と、
問い合わせの結果を出力する検索結果出力手段と、を更に有する。
【００１６】
また、本発明（請求項４）は、請求項３の検索装置において、
問い合わせ手段は、
事前に各ドキュメントの位置とコンテンツを関連付けたデータベースにアクセスし、検索結果であるドキュメント位置に関連付けられたコンテンツを検索結果として得る手段を含む。
【００１７】
図２は、本発明の原理を説明するための図である。
【００１８】
本発明（請求項５）は、改ページや改行位置が確定しており、文字列を含むドキュメント内の、文字列を含む一部領域を検索クエリとして、該領域が出現するドキュメント及び該ドキュメント内における位置を取得する検索要求に応えるための検索インデックスを作成し、検索を行う装置における検索方法であって、
ドキュメント群入力手段が、インデックス作成対象のドキュメント群の入力を受け付けるドキュメント群入力ステップ（ステップ１）と、
文字領域特定手段は、文字領域抽出方法を用いてドキュメント内の文字領域を特定する文字領域特定ステップ（ステップ２）と、
周辺領域特定手段が、各文字領域の周囲に存在する領域である周辺領域を特定する周辺領域特定ステップ（ステップ３）と、
部分画像特定手段が、画像特徴比較手法を用いて、各周辺領域とドキュメントの背景領域を比較し、該周辺領域の中で該背景領域と異なるものを部分画像領域と判定する部分画像特定ステップ（ステップ４）と、
インデックス出力手段が、文字領域と、該文字領域の周囲にある部分画像領域と、該文字列が出現するドキュメントにおける出現位置を関連付けてインデックスＤＢに出力するインデックス出力ステップ（ステップ５）と、を行う。
【００１９】
また、本発明（請求項６）は、請求項５の検索方法において、
ドキュメントは、画像も含み、
ドキュメント内の、画像及び文字列を含む一部領域を検索クエリとする。
【００２０】
また、本発明（請求項７）は、請求項５または６の検索方法において、
検索対象画像入力手段が、画像と文字列を含むドキュメントの一部領域を撮影した画像の入力を受け付ける検索対象画像入力ステップと、
検索対象文字領域特定手段が、文字領域抽出方法を用いて検索対象画像内の文字領域を特定する検索対象文字領域特定ステップと、
検索対象周辺領域特定手段が、各文字領域の周囲に存在する領域である周辺領域を特定する検索対象周辺領域特定ステップと、
検索対象部分画像特定手段が、画像特定比較手法を用いて、各周辺領域と検索対象画像の背景領域を比較し、周辺領域の中で背景領域と異なるものを部分画像領域と判定する検索対象部分画像特定ステップと、
問い合わせ手段が、文字領域と、該文字領域の周囲にある部分画像領域が出現するドキュメントまたはドキュメント内における位置を、インデックスＤＢに問い合わせる問い合わせステップと、
検索結果出力手段が、問い合わせの結果を出力する検索結果出力ステップと、を更に行う。
【００２１】
また、本発明（請求項８）は、請求項７の検索方法において、
問い合わせステップにおいて、
事前に各ドキュメントの位置とコンテンツを関連付けたデータベースにアクセスし、検索結果であるドキュメント位置に関連付けられたコンテンツを検索結果として得るステップを更に行う。
【００２２】
本発明（請求項９）は、請求項１乃至４のいずれか１項に記載の検索装置を構成する各手段としてコンピュータを機能させるための検索プログラムである。
【発明の効果】
【００２３】
上記のように本発明によれば、インデックス作成時及び検索実行時に、画像の全体領域を用いるのではなく、文字列と文字列周辺の部分画像のみを用いることにより、ドキュメント群の中から特定ドキュメントの特定位置を一意に取得する検索要求に応じることができる。例えば、手元にカタログの一部の切り抜きしかない場合でも、その切り抜きがどの書籍のどの部分であったかを突き止めることができる。
【００２４】
また、上記処理を実現するための一般手法の一つである、各画像の全体領域の色分布情報をデータベースに格納して、ある画像の全体領域の色分布情報を検索クエリとする方法では、画像の全体領域を検索クエリに含めなければならないという問題があった。しかし、本発明の方法では、画像の一部分と文字列を含む領域のみを検索クエリに含めればよい。ハンディデバイスで撮影した領域を検索クエリとするシステムの場合、ドキュメントの狭い領域だけを撮影すればよいので、検索クエリ画像が鮮明に撮影できる。ハンディデバイスで撮影した領域に関連付けられたコンテンツを取得できるシステムの場合、ドキュメントの狭い部分ごとに問い合わせを行うことができるので、ドキュメントにコンテンツを関連付けるユーザは細かい粒度で関連付けを行うことができ、ドキュメントに関連付けられたコンテンツを取得するユーザは、細かい粒度でコンテンツを取得することができる。
【００２５】
また、上記処理を実現するための一般手法の一つである、各画像の部分領域の色分布情報をデータベースに格納して、ある画像の部分領域の色分布情報を検索クエリとする方法では、データベース格納時及び検索実行時に画像を複数領域の部分領域に分割し、データベース内及び検索クエリの部分領域同士で色分布情報等のマッチングをとるため、マッチングを取る回数が大幅に増加するという問題がった。しかし、本発明の方法では、文字領域の周辺の部分画像同士のマッチングのみを行っているため、マッチング回数を大幅に減らし、処理を高速にできる。
【００２６】
また、上記記載の画像を全体領域単位で扱う方法、画像を複数領域に分割する方法の両方に共通して、各画像の全領域の情報をデータベースに格納しているので、格納領域が大量に必要になるという問題があった。しかし、本発明の方法では、文字領域の周辺の部分画像と文字領域の情報のみをデータベースに格納しているため、格納領域を少なく抑えることができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の第１の実施の形態におけるインデックス作成部の構成図である。
【図４】本発明の第１の実施の形態におけるＰＤＦファイル（書名：vegetable、ファイル名：vegetable3.pdf、ページ：３ページ目）の例である。
【図５】本発明の第１の実施の形態におけるインデックス作成の処理のフローチャートである。
【図６】本発明の第１の実施の形態における入力されたドキュメントのページのデータ構造化リストである。
【図７】本発明の第１の実施の形態におけるＰＤＦファイル（書名：vegetable、ファイル名：vegetable3.pdf、ページ：３ページ目）に対する文字領域特定の例である。
【図８】本発明の第１の実施の形態における特定された文字領域のデータ構造化リストである。
【図９】本発明の第１の実施の形態におけるＰＤＦファイル（書名：vegetable、ファイル名：vegetable3.pdf、ページ：３ページ目）に対する周辺領域特定の例である。
【図１０】本発明の第１の実施の形態における特定された周辺領域のデータ構造化リストである。
【図１１】本発明の第１の実施の形態における周辺領域特定の他の実現方法（文字領域が「め」の場合の一例）である。
【図１２】本発明の第１の実施の形態におけるＰＤＦファイル（書名：vegetable、ファイル名：vegetable3.pdf、ページ：３ページ目）に対する部分領域特定の例である。
【図１３】本発明の第１の実施の形態における特定された部分画像領域のデータ構造化リストである。
【図１４】本発明の第１の実施の形態における部分画像領域の色分布情報のデータ構造化リストである。
【図１５】本発明の第１の実施の形態におけるインデックス出力部の処理のフローチャートである。
【図１６】本発明の第１の実施の形態におけるインデックスＤＢに出力されるデータの例である。
【図１７】本発明の第２の実施の形態における検索装置の構成図である。
【図１８】本発明の第２の実施の形態における検索処理のフローチャートである。
【図１９】本発明の第２の実施の形態における検索対象のドキュメント（紙媒体）の例である。
【図２０】本発明の第２の実施の形態における入力された検索対象画像（ＪＰＥＧ）の例である。
【図２１】本発明の第２の実施の形態における検索対象画像のファイル名の例である。
【図２２】本発明の第２の実施の形態における検索対象画像（2009-05-20-18-00-00.jpg）の文字領域特定処理を示す図である。
【図２３】本発明の第２の実施の形態における文字領域データの構造化リストである。
【図２４】本発明の第２の実施の形態における検索対象画像（2009-05-20-18-00-00.jpg）から周辺領域を特定する例である。
【図２５】本発明の第２の実施の形態における周辺領域データの構造化リストである。
【図２６】本発明の第２の実施の形態における周辺領域特定の他の実現方法（文字領域が「ト」の場合の一例）である。
【図２７】本発明の第２の実施の形態における検索対象画像（2009-05-20-18-00-00.jpg）から部分画像領域を特定する例である。
【図２８】本発明の第２の実施の形態における部分画像領域のデータの構造化リストである。
【図２９】本発明の第２の実施の形態における部分画像領域の色分布情報のデータの構造化リストである。
【図３０】本発明の第２の実施の形態における問い合わせ処理のフローチャートである。
【図３１】本発明の第２の実施の形態における文字領域のデータに基づく検索結果の例である。
【図３２】本発明の第２の実施の形態におけるインデックスＤＢ検索のフローチャートである。
【図３３】本発明の第２の実施の形態におけるインデックスＤＢ検索結果リストである。
【図３４】本発明の第２の実施の形態におけるインデックスＤＢ検索結果の集約処理のフローチャートである。
【図３５】本発明の第２の実施の形態における集約リストである。
【図３６】本発明の第２の実施の形態におけるコンテンツＤＢの例である。
【図３７】本発明の第２の実施の形態におけるコンテンツＤＢ検索処理のフローチャートである。
【発明を実施するための形態】
【００２８】
以下、図面と共に本発明の実施の形態を説明する。
【００２９】
以下では、インデックスを作成する処理と、そのインデックスを用いて検索を実行する処理に分けて述べる。
【００３０】
［第１の実施の形態］
本実施の形態では、検索装置内のインデックスを作成する処理について述べる。
【００３１】
図３は、本発明の第１の実施の形態におけるインデックス作成部の構成を示す。
【００３２】
同図に示すインデックス作成部は、ドキュメント入力部１０、文字領域特定部１１、周辺領域特定部１２、部分画像領域特定部１３、インデックス出力部１４、インデックスＤＢ１５から構成される。
【００３３】
ドキュメントは、文字列または画像、または文字列及び画像を含むページの集合からなる紙媒体の書籍とする。本実施の形態では、この書籍の各ページをスキャナ（一般装置）で読み取り、図４に示すように、異なる閲覧環境（ＯＳ，ＰＤＦ閲覧ソフト等）においても文字列、画像のレイアウトが変化しない電子ファイル（ＰＤＦファイル等）に変換する。なお、ドキュメントの背景色は白と判明しているものとする。
【００３４】
また、文字領域特定部１１、周辺領域特定部１２、部分画像領域特定部１３は処理の過程で文字列等の情報を一時格納するメモリ（図示せず）を有するものとする。
【００３５】
以下に、本実施の形態におけるインデックスを作成する処理フローを示す。
【００３６】
図５は、本発明の第１の実施の形態におけるインデックス作成の処理のフローチャートである。
【００３７】
以下では、インデックス作成対象となるドキュメントを入力する入力ステップ（ステップ１１０，１２０）、ドキュメント中のページ内から文字領域を特定する文字領域特定ステップ（ステップ１３０）、ドキュメント中のページ内から周辺領域（ページ内の各文字領域周辺の領域）を特定する周辺領域特定ステップ（ステップ１４０）、ドキュメント中のページ内から部分画像領域（ページ内の周辺領域のうち、インデックス作成に用いる部分画像の領域）を特定する部分画像領域特定ステップ（ステップ１５０）、検索を実行するためのインデックスを出力する出力ステップ（ステップ１６０）について説明する。
【００３８】
ステップ１１０）  ドキュメント入力部１０は、分析対象のドキュメント群の入力を受け付ける。なお、各ドキュメントの形式は図４に示すようなＰＤＦファイルであり、スキャン元である書名とページは判明しているものとする。
【００３９】
ステップ１２０）  ドキュメント入力部１０は、該ドキュメント群に含まれるドキュメント、スキャン元である書名、ページを図６に示すデータ構造でリスト化する。リスト内の各要素は、各ドキュメントを一意に示すものとする。なお、説明の便宜上、ここでは、各ドキュメントを一意に示す情報としてファイル名を用いているが、ファイルのハッシュ値等、ドキュメントを一意に識別できる情報であれば他の情報を利用しても構わない。
【００４０】
ステップ１３０）  文字領域特定部１１は、図６のリストに記載されている各ドキュメントを読み込み、各ドキュメントの各ページについて、特開２０００−４８１２０号公報等の文字領域抽出方法を用いて、図７のように各文字を含む矩形領域（文字領域）を特定し、各文字領域の文字領域ＩＤ、文字、書名、ページ、座標、サイズを図８に示すデータ構造でリスト化する。なお、文字領域ＩＤは、説明の便宜上設けた各文字領域を一意に示す識別子である。また、本実施の形態では、座標は、ドキュメントの左上隅を原点とし、右方向にｘ軸、下方向にｙ軸をとった場合に、文字領域の左上の座標をピクセル単位で表現する。他の実現方法として、座標は、各頁における行・列等で表しても構わない。
【００４１】
また、本実施の形態では、サイズは、文字領域のｘ軸方向の長さ、ｙ軸方向の長さをピクセル単位で表現する。
【００４２】
ステップ１４０）  周辺領域特定部１２は、図８のリストに記載されている各レコードを読み込み、図９のように各レコードが表す文字領域に隣接している領域（周辺領域）を特定し、各周辺領域の周辺領域ＩＤ、座標、サイズ、文字領域ＩＤ、隣接方向を、図１０に示すデータ構造でリスト化する。
【００４３】
なお、本実施の形態では、周辺領域は文字領域と上下左右いずれかの方向に隣接している領域であり、かつ、該文字領域と相似形状の領域であり、かつ、文字領域と周辺領域の相似比は１：Ｎ（ここでは、Ｎ＝１とする）であり、１つ以上の文字領域の全体または一部を含まない領域である。他の実現方法としては、図１１のように１つ以上の文字領域の全体または一部を含む領域としても構わない。
【００４４】
また、本実施の形態では、周辺領域ＩＤは、説明の便宜上設けた各周辺領域を一意に示す識別子である。
【００４５】
また、本実施の形態では、座標は、ドキュメント左上隅を原点とし、右方向にｘ軸、下方向にｙ軸をとった場合に、周辺矩形領域の左上の座標をピクセル単位で表現する。他の実現方法として、座標は各頁における行・列等で表しても構わない。
【００４６】
また、本実施の形態では、サイズは、周辺領域のｘ軸方向の長さ、ｙ軸方向の長さをピクセル単位で表現する。
【００４７】
また、本実施の形態では、文字領域ＩＤは隣接している文字領域の文字領域ＩＤである。
【００４８】
また、本実施の形態では、隣接方向は、文字領域から見た、該文字領域に隣接している周辺領域の方向を上下左右で表すものである。他の実現方法としては、文字領域の重心と周辺領域の重心を結ぶ線分が水平方向からどの程度傾いているか等で表現しても構わない。
【００４９】
ステップ１５０）  部分画像領域特定部１３は、図１０のリストに記載されている各レコードを読み込み、図１２のように各レコードが表す周辺領域の中から背景領域であるものを除いた領域（部分画像領域）を特定し、各部分画像領域の部分画像領域ＩＤ、座標、サイズ、文字領域ＩＤ、隣接方向を、図１３に示すデータ構造でリスト化し、各部分画像領域の色分布情報を図１４に示すデータ構造でリスト化する。
【００５０】
なお、本実施の形態では、周辺領域の中から背景領域であるものを除く際、及び、各部分画像領域の色分布情報をリスト化する際には、前述の非特許文献１の方法を用いる。前述の通り、事前に判明しているドキュメントの背景色である白が持つ色分布情報Ａを算出し、同じ方法で各周辺領域の色分布情報Ｂも算出し、ＡとＢが異なる場合、該周辺領域を部分画像領域と判定し、Ｂを図４の形式でリストに追加する。他の実現方法としては、周辺領域の色分散（例えば、Ｒ値、Ｇ値、Ｂ値の頻度の分散値）が一定値を超えた場合、つまり、複数の色が混じり合っている領域の場合は背景領域ではなく、部分画像領域と判定しても構わない。
【００５１】
また、本実施の形態では、部分画像領域ＩＤは説明の便宜上設けた各部分画像領域を一意に示す識別子である。
【００５２】
また、本実施の形態では、座標、サイズ、文字領域ＩＤ、隣接方向は、周辺領域における定義と同様である。
【００５３】
ステップ１６０）  インデックス出力部１４は、図８、図１３、図１４のリストに記載されている各レコードを読み込み、図１５示すフローチャートに従って、図８と図１３を文字領域ＩＤで関連付け、図１３と図１４を部分画像領域ＩＤで関連付け、図１６に示す形式のインデックスとしてインデックスＤＢ１５に出力する。
【００５４】
ステップ１６１）  図８の文字領域のリストを全件読み込む。
【００５５】
ステップ１６２）  カウントｉ＝１とする。
【００５６】
ステップ１６３）  ｉ≦Ｘである場合にはステップ１６４に移行し、ｉ＞Ｘである場合は処理を終了する。
【００５７】
ステップ１６４）  以下の処理を行う。
【００５８】
ステップ１６４１）  図８の文字領域のリストのｉ番目のレコードと同じ文字領域ＩＤを持つレコード群全Ｙ件を図１３の部分画像領域のリストから読み込む。
【００５９】
ステップ１６４２）  カウンタｊをｊ＝１とする。
【００６０】
ステップ１６４３）  ｊ≦Ｙであればステップ１６４４に移行し、ｊ＞Ｙであれば処理を終了する。
【００６１】
ステップ１６４４）  図１３の部分画像領域のリストのｊ番目のレコードと同じ部分画像領域ＩＤを持つレコード群全Ｚ件（レコード群ｚとする）を図１４の部分画像領域の色分布情報のリストから読み込む。
【００６２】
ステップ１６４５）  図８の文字領域のｉ番目のレコードの文字、書名、ページ、座標、図１３の部分画像領域のリストのｊ番目のレコードの隣接方向、図１４の部分画像領域の色分布情報のリストのレコード群ｚのＲ値、Ｇ値、Ｂ値、頻度を関連付けて、インデックスの１レコードとしてインデックスＤＢ１４に出力する。
【００６３】
ステップ１６４６）    カウンタｊをｊ＝ｊ＋１として、ステップ１６４３に移行する。
【００６４】
［第２の実施の形態］
本実施の形態では、第１の実施の形態で生成されたインデックスＤＢを用いて検索装置で検索を実行する処理の流れを示す。
【００６５】
図１７は、本発明の第２の実施の形態における検索装置の構成を示す。
【００６６】
同図に示す検索装置は、検索対象画像入力部２０、文字領域特定部２１、周辺領域特定部２２、部分画像領域特定部２３、問い合わせ部２４、検索結果出力部２５、コンテンツＤＢ２６、インデックスＤＢ１５、集約リスト記憶部２７、ハンディデバイス２００から構成される。
【００６７】
インデックスＤＢ１５は、第１の実施の形態において生成されたＤＢである。
【００６８】
ハンディデバイス２００は、カメラ、ディスプレイ、データ送受信機能を有する一般装置であり、例えば、カメラ付携帯電話がこれに該当する。
【００６９】
ドキュメントは、文字列、または、画像、または、文字列または画像を含むページの集合からなる紙媒体の書籍とし、検索対象画像は該ドキュメントの一部を撮影したものとする。なお、ドキュメントの背景色は白と判明しているものとする。
【００７０】
また、文字領域特定部２１、周辺領域特定部２２、部分画像領域特定部２３、問い合わせ部２４は、処理の過程で文字列等の情報を一時格納するメモリ（図示せず）を有するものとする。
【００７１】
以下に、本実施の形態における検索を実行する処理のフローチャートを示す。
【００７２】
図１８は、本発明の第２の実施の形態における検索処理のフローチャートである。
【００７３】
以下では、検索の対象となる検索対象画像を入力する入力ステップ（ステップ２０１，２０３）、検索対象画像中から文字領域を特定する文字領域特定ステップ（ステップ２０４）、検索対象画像内から周辺領域を特定する周辺領域特定ステップ（ステップ２０５）、検索対象画像内から部分画像領域を特定する部分画像領域特定ステップ（ステップ２０６）、検索対象画像にマッチするドキュメント、ドキュメント内における位置、該位置に予め関連付けられたコンテンツを問い合わせる問い合わせステップ（ステップ２０７〜２１０）、問い合わせを実行した結果を出力する出力ステップ（ステップ２１１，２１２）について説明する。
【００７４】
ステップ２０１）  ハンディデバイス２００で図１９のようなドキュメント（書籍）内のページ内の、画像と文字列の両方を含む部分を撮影して図２０のようなJPEG形式のファイルを作成し、これを検索対象画像とする。
【００７５】
なお、撮影された画像と文字列の情報を含んでいればファイル形式はJPEG以外でも構わない。
【００７６】
また、本実施の形態では、検索対象画像は１つのみであるが、検索対象画像を複数用意しても構わない。
【００７７】
ステップ２０２）  検索対象画像入力部２０は、ハンディデバイス２００から、ネットワークを介して検索対象画像の入力を受け付ける。
【００７８】
なお、ネットワークを介さずに、ＳＤカード等の記憶媒体を介して検索対象画像の入力を受け付けても構わない。
【００７９】
また、本実施の形態では、検索対象画像は１つのみであるが、検索対象画像が複数ある場合は、それらを同時に受け付けても構わない。
【００８０】
ステップ２０３）  検索対象画像入力部２０は、検索対象画像（複数ある場合は検索対象画像群）にシステム内で唯一となるようなファイル名を付け、図２１に示すデータ構造でリスト化する。
【００８１】
なお、説明の便宜上、ここでは、検索対象画像を一意に示すファイル名として、ファイルが入力された時刻を用いているが、ファイルのハッシュ値等、検索対象画像を一意に識別できる情報であれば他の情報を利用しても構わない。
【００８２】
以降、本実施の形態では、入力された検索対象画像が１つである場合のみを説明するが、複数の検索対象画像が入力された場合は、それらを一意に区別できるようなファイル名を付け、リストに追加し、以降の処理の各検索対象画像について繰り返し行えばよい。
【００８３】
ステップ２０４）  文字領域特定部２１は、図２１のリストに記載されている各検索対象画像を読み込み、各検索対象画像について、前述の特開２０００−４８１２０号公報等の文字領域抽出方法を用いて、図２２のように各文字を含む矩形領域（文字領域）を特定し、各文字領域の文字領域ＩＤ、文字、サイズを図２３に示すデータ構造でリスト化する。
【００８４】
なお、本実施の形態では、文字領域ＩＤは説明の便宜上設けた各文字領域を一意に示す識別子である。
【００８５】
また、本実施の形態では、サイズは、文字領域のｘ軸方向の長さ、ｙ軸方向の長さをピクセル単位で表現する。
【００８６】
ステップ２０５）  周辺領域特定部２２は、図２３のリストに記載されている各レコードを読み込み、図２４のように各レコードが表す文字領域に隣接している領域（周辺領域）を特定し、各周辺領域の周辺領域ＩＤ、サイズ、文字領域ＩＤ、隣接方向を、図２５に示すデータ構造でリスト化する。
【００８７】
なお、本実施の形態では、周辺領域は、文字領域と上下左右のいずれかの方向に隣接している領域であり、かつ、該文字領域と相似形状の領域であり、かつ、文字領域と周辺領域の相似比は１：Ｎ（ここではＮ＝１とする）であり、１つ以上の文字領域の全体または一部を含まない領域である。他の実現方法としては、図２６のように、１つ以上の文字領域の全体または一部を含む領域としても構わない。
【００８８】
また、本実施の形態では、周辺領域ＩＤは、説明の便宜上設けた各周辺領域を一意に示す識別子である。
【００８９】
また、本実施の形態では、サイズは、周辺領域ｘ軸方向の長さ、ｙ軸方向の長さをピクセル単位で表現する。
【００９０】
また、本実施の形態では、文字領域ＩＤは、隣接している文字領域の文字領域ＩＤである。
【００９１】
また、本実施の形態では、隣接方向は、文字領域から見た、該文字領域に隣接している周辺領域の方向を上下左右で表すものである。他の実現方法としては、文字領域の重心と周辺領域の重心を結ぶ線分が水平方向からどの程度傾いているか等で表現しても構わない。
【００９２】
ステップ２０６）  部分画像領域特定部２３は、図２５のリストに記載されている各レコードを読み込み、図２７のように各レコードが表す周辺領域の中から背景領域であるものを除いた領域（部分画像領域）を特定し、各部分画像領域の部分画像領域ＩＤ、サイズ、文字領域ＩＤ，隣接方向を、図２８に示すデータ構造でリスト化し、各部分画像領域の色分布情報を図２９に示すデータ構造でリスト化する。
【００９３】
なお、本実施の形態では、周辺領域の中から背景領域であるものを除く際、及び、各部分画像領域の色分布情報をリスト化する際は、第１の実施の形態のステップ１５０と同様の方法を用いる。
【００９４】
また、本実施の形態では、部分画像領域ＩＤは、説明の便宜上設けた各部分画像領域を一意に示す識別子である。
【００９５】
また、本実施の形態では、サイズ、文字領域ＩＤ、隣接方向は、周辺領域における定義と同様である。
【００９６】
ステップ２０７）  問い合わせ部２４は、図２３の文字領域のデータ、図２８の部分画像領域のデータ、図２９の部分画像領域の色分布情報のリストに記載されている各レコードを読み込み、図３０のフローチャートに従って図２３と図２８を文字領域ＩＤで関連付け、図２８と図２９を部分画像領域ＩＤで関連付け図３１に示す形式のリストを作成する。
【００９７】
図３０は、本発明の第２の実施の形態における問い合わせ処理のフローチャートである。
【００９８】
ステップ３１０）  図２３の文字領域のリストを全Ｘ件読み込む。
【００９９】
ステップ３２０）  カウンタｉをｉ＝１とする。
【０１００】
ステップ３３０）  ｉ≦Ｘであればステップ３４０に移行し、ｉ＞Ｘであれば当該問い合わせ処理を終了する。
【０１０１】
ステップ３４０）  以下の処理を行う。
【０１０２】
ステップ３４１）  図２３の文字領域のリストのｉ番目のレコードと同じ文字領域を持つレコード群全Ｙ件を図２８の部分画像領域のリストから読み込む。
【０１０３】
ステップ３４２）  カウンタｊをｊ＝１とする。
【０１０４】
ステップ３４３）  ｊ≦Ｙであればステップ３４４に移行し、ｊ＞Ｙであれば当該処理を終了する。
【０１０５】
ステップ３４４）  図２８の部分画像領域ＩＤを持つレコード群全Ｚ件（レコード群ｚとする）を図２９の部分画像領域の色分布情報のリストから読み込む。
【０１０６】
ステップ３４５）  図２３の文字領域のリストのｉ番目のレコードの文字、図２８のリストのｊ番目のレコードの隣接方向、図２９の部分画像領域の色分布情報のリストのレコード群ｚのＲ値、Ｇ値、Ｂ値、頻度を関連付けて、図３１の検索結果のリストの１レコードとして出力する。
【０１０７】
ステップ３４６）  カウンタｊをｊ＝ｊ＋１とし、ステップ３４３に移行する。
【０１０８】
ステップ３５０）  カウンタｉをｉ＝ｉ＋１とし、ステップ３３０に移行する。
【０１０９】
ステップ２０８）  問い合わせ部２４は、図１３のデータ構造を持つインデックスＤＢ１５に、図３２のフローチャートに従って問い合わせを行い、図３３に示す検索結果を得る。
【０１１０】
図３２は、本発明の第２の実施の形態におけるインデックスＤＢ検索のフローチャートである。
【０１１１】
ステップ４０１）  図３１の文字領域のリスト全Ｘ件を読み込む。
【０１１２】
ステップ４０２）  カウンタｉをｉ＝１とする。
【０１１３】
ステップ４０３）  カウンタｉ≦Ｘである場合はステップ４０４に移行し、ｉ＞Ｘである場合は当該処理を終了する。
【０１１４】
ステップ４０４）  図２３の文字領域のリストのｉ番目のレコードと同じレコードと同じ文字、隣接方向、Ｒ値、Ｇ値、Ｂ値、頻度を持つレコード群全Ｙ件の書名、ページ、座標を図１６のインデックスＤＢ１５から読み込み、図３３のインデックスＤＢ検索結果リストに追加する。
【０１１５】
ステップ４０５）  カウンタｉをｉ＝ｉ＋１とし、ステップ４０３に移行する。
【０１１６】
ステップ２０９）  問い合わせ部２４は、図３３のリストに記載されているインデックスＤＢ１５を検索した結果の各レコードを読み込み、図３４のフローチャートに従って、座標が近い検索結果をグループに集約し、各グループに集約されている元レコードの数（集約数）を集計し、図３５に示すリストを集約リスト記憶部２７に出力する。
【０１１７】
図３４は、本発明の第２の実施の形態におけるインデックスＤＢ検索結果の集約処理のフローチャートである。
【０１１８】
ステップ５１０）  図３３のインデックスＤＢ１５の検索結果のリスト全Ｘ件を読み込む。
【０１１９】
ステップ５２０）  カウンタｉをｉ＝１とする。
【０１２０】
ステップ５３０）  カウンタｉ≦Ｘであれば、ステップ５４０に移行し、ｉ＞Ｘであればステップ５６０に移行する。
【０１２１】
ステップ５４０）  以下の処理を行う。
【０１２２】
ステップ５４１）  集約先レコードの中に図３３のｉ番目のレコードと同じ書名・ページで、座標が近い（例えば、ｘ軸方向・ｙ軸方向の２０ピクセル以内）レコードがあるかを判定し、ある場合はステップ５４２に移行し、ない場合はステップ５４３に移行する。
【０１２３】
ステップ５４２）  図３３のリストのｉ番目のレコードを、座標が一番近い集約先レコード（複数存在する場合は座標が原点に最も近いもの）に集約し、該集約先レコードの集約数を１増やし、ステップ５５０に移行する。
【０１２４】
ステップ５４３）  図３３のリストのｉ番目のレコードを、新たな集約先レコードとし、当該集約先レコードの集約数を１として、書名・ページ・座標と共にメモリ（図示せず）上に保存し、ステップ５５０に移行する。
【０１２５】
ステップ５５０）  カウンタｉをｉ＝ｉ＋１とし、ステップ５３０に移行する。
【０１２６】
ステップ５６０）  ステップ５３０において、ｉ＞Ｘである場合は、メモリ（図示せず）上に保存されている集約先レコードの書名・ページ・座標・集約数を図３５のリストとして集約リスト記憶部２７に出力する。
【０１２７】
なお、本実施の形態では、座標がｘ軸方向・ｙ軸方向の２０ピクセルの範囲内にあれば、座標が近いと判定するものとする。
【０１２８】
ステップ２１０）  問い合わせ部２４は、図３５の集約リスト記憶部２７のリストの中で集約数が一番大きいレコードを読み込み、事前にシステム運用者等が作成した図３６のデータ構造を持つコンテンツＤＢ２６に対し、図３７のフローチャートに従って当該レコードに座標が近い位置に関連付けられたコンテンツを問い合わせ、得られたコンテンツを検索結果出力部２５に渡す。
【０１２９】
図３７は、本発明の第２の実施の形態におけるコンテンツＤＢ検索処理のフローチャートである。
【０１３０】
ステップ６０１）  図３５の集約リスト記憶部２７のリスト中で集約数が最大のレコードＡを読み込む。
【０１３１】
ステップ６０２）  コンテンツＤＢ２６の中に、レコードＡと書名・ページが同一のレコードＢが含まれている場合はステップ６０３に移行し、含まれていないばあいはステップ６０５に移行する。
【０１３２】
ステップ６０３）  レコードＡとレコードＢの座標が近い（ｘ軸方向・ｙ軸方向に２０ピクセル以内）場合はステップ６０４に移行し、近くない場合はステップ６０５に移行する。
【０１３３】
ステップ６０４）  レコードＢのコンテンツを出力する。
【０１３４】
ステップ６０５）  「コンテンツ無し」と判定する。
【０１３５】
なお、本実施の形態では、座標がｘ軸方向、ｙ軸方向に２０ピクセルの範囲内にあれば、座標が近いと判定する。
【０１３６】
ステップ２１１）  検索結果出力部２５は、問い合わせ部２４からコンテンツを渡されていれば、ハンディデバイス２００にネットワークを介してコンテンツを送信する。問い合わせ部２４が「コンテンツ無し」と判定していれば、ハンディデバイス２００には何も渡さない。
【０１３７】
なお、検索結果出力部２５からハンディデバイス２００にコンテンツを渡す際は、ネットワークを介さず、ＳＤカード等の記憶媒体を介してコンテンツを渡しても構わない。
【０１３８】
ステップ２１２）  ハンディデバイス２００は、検索結果出力部２５から渡されたコンテンツを、予め定められた手段で表示する。
【０１３９】
本実施の形態では、拡張子がｈｔｍｌで終わるコンテンツが渡された場合は、ハンディデバイス２００に内蔵のＷｅｂブラウザで該コンテンツを表示するものとする。
【０１４０】
なお、上記の図３、図１７に示す各構成要素の動作をプログラムとして構築し、インデックス作成部、検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１４１】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１４２】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１４３】
１０  ドキュメント入力部
１１  文字領域特定部
１２  周辺領域特定部
１３  部分画像領域特定部
１４  インデックス出力部
１５  インデックスＤＢ
２０  検索対象画像入力部
２１  文字領域特定部
２２  周辺領域特定部
２３  部分画像領域特定部
２４  問い合わせ部
２５  検索結果出力部
２６  コンテンツＤＢ
２７  集約リスト記憶部
【図１】
2011129070.tif 000003
【図２】
2011129070.tif 000004
【図３】
2011129070.tif 000005
【図４】
2011129070.tif 000006
【図５】
2011129070.tif 000007
【図６】
2011129070.tif 000008
【図７】
2011129070.tif 000009
【図８】
2011129070.tif 000010
【図９】
2011129070.tif 000011
【図１０】
2011129070.tif 000012
【図１１】
2011129070.tif 000013
【図１２】
2011129070.tif 000014
【図１３】
2011129070.tif 000015
【図１４】
2011129070.tif 000016
【図１５】
2011129070.tif 000017
【図１６】
2011129070.tif 000018
【図１７】
2011129070.tif 000019
【図１８】
2011129070.tif 000020
【図１９】
2011129070.tif 000021
【図２０】
2011129070.tif 000022
【図２１】
2011129070.tif 000023
【図２２】
2011129070.tif 000024
【図２３】
2011129070.tif 000025
【図２４】
2011129070.tif 000026
【図２５】
2011129070.tif 000027
【図２６】
2011129070.tif 000028
【図２７】
2011129070.tif 000029
【図２８】
2011129070.tif 000030
【図２９】
2011129070.tif 000031
【図３０】
2011129070.tif 000032
【図３１】
2011129070.tif 000033
【図３２】
2011129070.tif 000034
【図３３】
2011129070.tif 000035
【図３４】
2011129070.tif 000036
【図３５】
2011129070.tif 000037
【図３６】
2011129070.tif 000038
【図３７】
2011129070.tif 000039