(57)【要約】【課題】照合する２つの文書画像が拡大または縮小の関係にある場合やスキューの関係にある場合でも、高速に類似度を計算できるようにする。【解決手段】装置は、例えばスキャナから取り込まれた第１の文書画像及び第１の文書画像の元画像候補として文書データベースから抽出される電子化された第２の文書画像の解像度をそれぞれ低解像度に変換する。措置は、低解像度に変換された第１の文書画像及び第２の文書画像をそれぞれ複数の部分領域に分割する。装置は、第１の文書画像と第２の文書画像とについて、それぞれ対応する部分領域毎に相互相関計算を行って領域毎の類似度を算出する。装置は、領域毎の類似度から第１の文書画像と第２の文書画像との画像全体の類似度を算出する。【選択図】      図１１
2015191308.tif 000002
【特許請求の範囲】
【請求項１】
画像取込手段により取り込まれた第１の文書画像及び前記第１の文書画像の元画像候補として文書データベースから抽出される電子化された第２の文書画像の解像度をそれぞれ低解像度に変換する解像度変換手段と、
前記解像度変換手段により低解像度に変換された第１の文書画像及び第２の文書画像をそれぞれ複数の部分領域に分割する分割手段と、
前記第１の文書画像と前記第２の文書画像とについて、それぞれ対応する部分領域毎に相互相関計算を行って領域毎の類似度を算出する領域類似度演算手段と、
前記領域類似度演算手段により算出される領域毎の類似度から前記第１の文書画像と前記第２の文書画像との画像全体の類似度を算出する画像類似度演算手段と、
を具備したことを特徴とする文書画像の照合装置。
【請求項２】
前記解像度変換手段，分割手段，演算手段及び判定手段を有するマッチング処理を、前記解像度変換手段により変換される解像度を上げながら複数回繰り返すことを特徴とする請求項１記載の文書画像の照合装置。
【請求項３】
前記分割手段は、前記第１の文書画像と前記第２の文書画像とについて、対応する領域の全体画像に対する位置とサイズが同じであり、かつ中央の部分領域に対して他の部分領域が点対称になるように分割することを特徴とする請求項１または２記載の文書画像の照合装置。
【請求項４】
画像取込手段により取り込まれた第１の文書画像及び前記第１の文書画像の元画像候補として文書データベースから抽出される電子化された第２の文書画像の解像度をそれぞれ低解像度に変換する解像度変換手段と、
前記解像度変換手段により低解像度に変換された第１の文書画像及び第２の文書画像をそれぞれ複数の部分領域に分割する分割手段と、
前記第１の文書画像と前記第２の文書画像とについて、それぞれ対応する部分領域毎に相互相関計算を行って領域毎の類似度を算出する領域類似度演算手段と、
前記領域類似度演算手段により算出される領域毎の類似度から前記第１の文書画像と前記第２の文書画像との画像全体の類似度を算出する全体類似度演算手段と、
前記全体類似度演算手段により算出される全体類似度を所定の閾値と比較して前記第２の文書画像が前記第１の文書画像に類似しているか否かを判定する判定手段と、
前記判定手段により前記第１の文書画像に類似していると判定された前記第２の文書画像を前記文書データベースから検出する検出する検出手段と、
を具備したことを特徴とする文書画像検索装置。
【請求項５】
前記検出手段により前記文書データベースから検出された前記第２の文書画像と前記第１の文書画像とのそれぞれの濃度信号について位置合わせを行った後に差分をとり、この差分信号を前記第１の文書画像の原信号に対してマスク処理を施して、前記第１の文書画像から追記画像を抽出する抽出手段、
をさらに具備したことを特徴とする請求項４記載の文書画像検索装置。
【請求項６】
画像取込手段により取り込んだ第１の文書画像を入力可能なコンピュータに、
前記第１の文書画像及び前記第１の文書画像の元画像候補として文書データベースから抽出される電子化された第２の文書画像の解像度をそれぞれ低解像度に変換する機能、
前記低解像度に変換された第１の文書画像及び第２の文書画像をそれぞれ複数の部分領域に分割する機能、
前記第１の文書画像と前記第２の文書画像とについて、それぞれ対応する部分領域毎に相互相関計算を行って領域毎の類似度を算出する機能、及び
前記領域毎の類似度から前記第１の文書画像と前記第２の文書画像との画像全体の類似度を算出する機能、
を実現させるための照合プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、電子化された文書画像の検索装置及びこの検索装置に組み込まれる文書画像の照合装置、並びにコンピュータを照合装置として機能させるための照合プログラムに関する。
【背景技術】
【０００２】
近年、情報処理に係るハードウェアおよびソフトウェアの発達に伴い、文書画像を電子的に作成し、電子ファイルとして記憶媒体に保存する環境が整いつつある。それに伴い、記憶媒体に保存されている大量の電子ファイル化された文書画像の中から所望の文書画像を簡易に検索するシステムの構築が要望されている。
【０００３】
一般に、電子ファイルを検索するためには検索のためのキーが必要となる。文書画像を検索する場合、検索のキーとしてテキスト情報を用いるのが主流である。しかし、会議資料のような文書画像は、テキスト情報だけでなく写真や図表等のイメージも含まれることが多い。イメージを検索のキーとして文書画像を検索できたならば、検索の幅が広がる。
【０００４】
イメージを検索のキーとして文書画像を検索するためには、２つの文書画像同士を照合して類似度を算出する必要がある。文書画像の照合方法としては、従来から相互相関法が知られている。相互相関法は、２つの文書画像に対して相対位置をずらしながら対応する画素値の差分の二乗和を算出して類似度を求める方式である。このため、一方の文書画像が拡大または縮小されていたり、２つの文書画像が回転の位置関係にあったりした場合には、相互相関法は対応できない。また相互相関法は、画像の画素数に比例して計算量が増えるだけでなく、ずらし量の範囲に比例しても計算量が増える。このため、画像の解像度が高い場合やずらしの探索範囲が広い場合に、相互相関法は計算量が膨大になるため、高速に処理できない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２‐０６８１３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一実施形態が解決しようとする課題は、照合する２つの文書画像が拡大または縮小の関係にある場合やスキューの関係にある場合でも、高速に類似度を計算できるようにすることにある。
【課題を解決するための手段】
【０００７】
一実施形態において、文書画像の照合装置は、解像度変換手段と、分割手段と、領域類似度演算手段と、画像類似度演算手段とを含む。解像度変換手段は、画像取込手段により取り込まれた第１の文書画像及び第１の文書画像の元画像候補として文書データベースから抽出される電子化された第２の文書画像の解像度をそれぞれ低解像度に変換する。分割手段は、低解像度に変換された第１の文書画像及び第２の文書画像をそれぞれ複数の部分領域に分割する。領域類似度演算手段は、第１の文書画像と第２の文書画像とについて、それぞれ対応する部分領域毎に相互相関計算を行って領域毎の類似度を算出する。画像類似度演算手段は、領域毎の類似度から第１の文書画像と第２の文書画像との画像全体の類似度を算出する。
【図面の簡単な説明】
【０００８】
【図１】文書画像検索装置の概略構成を示すブロック図。
【図２】文書データベースに保存されるデータファイルのデータ構造を示す模式図。
【図３】文書画像検索装置のハードウェア構成を示すブロック図。
【図４】検索セクションの具体的な処理手順を示す流れ図。
【図５】問合せ画像の一例を示す図。
【図６】図５の問合せ画像に対する明度のヒストグラムの一例を示す図。
【図７】図５の問合せ画像に対する横方向の射影濃度分布及び縦方向の射影濃度分布と、各濃度分布統計量の算出結果を示す図。
【図８】濃度分布統計量にしたがって問合せ画像を分割する一例を示す図。
【図９】問合せ画像を分割閾値で９分割した際の分割領域毎の濃度比率特徴量の一例を示す図。
【図１０】画像の位置ずれと相対位置行列との関係を説明するために用いる具体例を示す図。
【図１１】照合処理の手順を示す流れ図。
【図１２】マッチング処理の手順を示す流れ図。
【図１３】図１０に示す比較画像と問合せ画像に対する変換比較画像と変換問合せ画像の一例を示す図。
【図１４】図１３に示した部分画像に対するずれベクトルと中心点の位置ベクトルの一例を示す図。
【図１５】相対位置行列の更新を説明するための模式図。
【図１６】追記領域抽出処理の詳細を示すブロック図。
【発明を実施するための形態】
【０００９】
以下、文書画像検索装置及びこの検索装置に用いられる文書画像の照合装置の実施形態について、図面を用いて説明する。
【００１０】
［文書画像検索装置の構成］
図１は、文書画像検索装置１の概略構成を示すブロック図である。文書画像検索装置１は、文書データベース１１と検索処理部１２とを備える。文書データベース１１は、文書画像の元となる電子化された文書画像のデータを格納してなるデータファイル２（図２を参照）を多数保存する。
【００１１】
データファイル２のデータ構造を図２に示す。図２に示すように、データファイル２は、文書ファイル２１に、頁別のサムネール画像２２と、同じく頁別の特徴量データ２３とを付加させた構造となっている。文書ファイル２１は、電子化された文書画像のデータを格納する電子データファイルである。データのファイル形式は任意である。例えばワード、PDF、JPEG,パワーポイント等、文書画像のデータに適合した形式のファイルであればよい。
【００１２】
サムネール画像２２は、文書ファイル２１に格納されるデータにより再現される文書画像を、例えば５０dpi（dot per inch）程度の粗い画素密度で表現したビットマップデータである。文書画像のデータが複数頁に跨る場合には、頁毎にサムネール画像２２が生成され、文書ファイル２１に付加される。
【００１３】
特徴量データ２３は、文書ファイル２１に格納されるデータにより再現される文書画像の特徴量を示すデータである。例えば、濃度比率特徴量、濃度分布統計量、規格化濃度画像等が特徴量データ２３として活用される。これらの特徴量データ２３の詳細については後述する。文書画像のデータが複数頁に跨る場合には、頁毎に特徴量データ２３が生成され、文書ファイル２１に付加される。
【００１４】
検索処理部１２は、問合せ画像の入力セクション１２１、候補画像の検索セクション１２２、候補画像の出力セクション１２３、候補画像選択入力の受付セクション１２４及び確定画像の送信セクション１２５を含む。検索処理部１２は、ＬＡＮ（Local Area Network）、インターネット等のネットワークを介して、ユーザ端末３とデータ通信を行うことができる。ユーザ端末３は、例えば画像読取手段であるスキャナを接続した情報処理端末である。ユーザ端末３は、例えば撮影手段であるカメラを備えた携帯型の通信端末であってもよい。
【００１５】
入力セクション１２１は、ユーザ端末３から問合せ画像を入力する。問合せ画像は、ユーザ端末３において、紙等の印刷媒体に印刷された文書画像を撮影またはスキャンして得られるデータである。問合せ画像は、ユーザ端末３からネットワークを経由して文書画像検索装置１に送られてくる。ＵＳＢメモリ等の可搬型記憶媒体に格納された問合せ画像のデータを、記憶媒体インターフェースを介して入力セクション１２１が取り込んでもよい。入力セクション１２１は、入力された問合せ画像のデータを、所定のメモリ領域に書き込む。
【００１６】
検索セクション１２２は、問合せ画像の元となる電子化された文書画像のデータを格納してなるデータファイル２を、文書データベース１１から検索する。検索の手順については後述する。検索セクション１２２は、問合せ画像に類似する文書画像のデータを格納してなるデータファイル２を２以上検索する場合もある。
【００１７】
出力セクション１２３は、検索セクション１２２において複数のデータファイル２が検索された場合、各データファイル２から頁別サムネール画像２２を抽出する。出力セクション１２３は、ネットワークを経由してユーザ端末３に頁別サムネール画像２２のデータを送信する。
【００１８】
ユーザ端末３は、少なくとも入力デバイスと表示デバイスとを備える。ユーザ端末３は、頁別サムネール画像２２のデータを受信すると、そのサムネール画像（候補画像）の一覧を表示デバイスに表示する。ユーザは、複数のサムネール画像の中から問合せ画像の元となる文書画像に対応したサムネール画像を選択する。ユーザは、入力デバイスを用いてどのサムネール画像を選択したのかを入力する。
【００１９】
受付セクション１２４は、ユーザ端末３においてサムネール画像が選択されるのを待機する。サムネール画像が選択された場合、受付セクション１２４は、そのサムネール画像が格納されるデータファイル２を、問合せ画像の元となる文書画像のデータを格納してなるデータファイル２として確定する。
【００２０】
送信セクション１２５は、問合せ画像の元となる文書画像のデータを格納してなるデータファイル２から文書ファイル２１を抽出する。検索セクション１２２において唯一のデータファイル２が特定された場合、送信セクション１２５は、そのデータファイル２から文書ファイル２１を抽出する。検索セクション１２２において複数のデータファイル２が検索された場合、送信セクション１２５は、受付セクション１２４において確定されたデータファイル２から文書ファイル２１を抽出する。送信セクション１２５は、ネットワークを経由して文書ファイル２１をユーザ端末３に送信する。
【００２１】
ユーザ端末３は、文書画像検索装置１から文書ファイル２１を受信すると、その文書ファイル２１に格納されているデータから再現される文書画像を表示デバイスに表示する。ユーザ端末３は、表示デバイスに表示した文書画像をプリントアウトする機能を有していてもよい。またユーザ端末３は、表示デバイスに表示した文書画像をネットワークを通じて他の端末に送信出力してもよい。
【００２２】
なお、文書画像検索装置１によっては検索機能を使用するためにユーザ認証や課金のアカウントなどの情報の入力が必要な場合も考えられる。しかし、この点については本実施形態と関係しないので、ここでの説明は省略する。
【００２３】
図３は、文書画像検索装置１のハードウェア構成を示すブロック図である。文書画像検索装置１は、ＣＰＵ（Central Processing Unit）４１、ＲＯＭ（Read Only Memory）４２、ＲＡＭ（Random Access Memory）４３、補助記憶デバイス４４、コンソール４５、スキャナ４６及び通信インターフェース４７を備え、これらをシステムバス４８で接続する。
【００２４】
ＣＰＵ４１は、コンピュータの中枢部分に相当する。ＣＰＵ４１は、オペレーティングシステムやアプリケーションプログラムに従って、文書画像検索装置１としての各種の機能を実現するべく各部を制御する。
【００２５】
ＲＯＭ４２は、上記コンピュータの主記憶部分に相当する。ＲＯＭ４２は、上記のオペレーティングシステムやアプリケーションプログラムを記憶する。ＲＯＭ４２は、ＣＰＵ４１が各部を制御するための処理を実行する上で必要なデータを記憶する場合もある。
【００２６】
ＲＡＭ４３は、上記コンピュータの主記憶部分に相当する。ＲＡＭ４３は、ＣＰＵ４１が処理を実行する上で必要なデータを記憶する。またＲＡＭ４３は、ＣＰＵ４１によって情報が適宜書き換えられるワークエリアとしても利用される。
【００２７】
補助記憶デバイス４４は、上記コンピュータの補助記憶部分に相当する。補助記憶デバイス４４は、例えばＥＥＰＲＯＭ（Electric Erasable Programmable Read-Only Memory）、ＨＤＤ（Hard Disc Drive）、あるいはＳＳＤ（Solid State Drive）などである。補助記憶デバイス４４は、ＣＰＵ４１が各種の処理を行う上で使用するデータや、ＣＰＵ４１での処理によって生成されたデータを保存する。補助記憶デバイス４４は、上記のアプリケーションプログラムを記憶する場合もある。
【００２８】
補助記憶デバイス４４は、文書画像検索装置１に内蔵されていてもよいし、外付けされていてもよい。補助記憶デバイス４４は、文書データベース１１として機能する。
【００２９】
コンソール４５は、コンピュータに指示を与える入力デバイスと、情報を表示する表示デバイスとを有する。コンソール４５は、図示しない信号入出力回路を介してシステムバス４８に接続される。
【００３０】
スキャナ４６は、紙などの印刷媒体に印刷された文書画像をスキャンして電子的に読み取る。スキャナ４６は、図示しない信号入出力回路を介してシステムバス４８に接続される。
【００３１】
通信インターフェース４７は、所定のネットワークを介して接続されたユーザ端末３との間で行われるデータ通信をコントロールする。
【００３２】
［文書画像検索装置の機能説明］
文書画像検索装置１は、文書データベース１１にデータファイル２を登録する機能を有する。データファイル２の登録方法は、特に限定されない。例えば、コンソール４５の操作により電子的に作成された文書画像から文書画像検索装置１がデータファイル２を生成し、文書データベース１１に登録してもよい。スキャナ４６で光学的に読み取られた文書画像から文書画像検索装置１がデータファイル２を生成し、文書データベース１１に登録してもよい。外部のユーザ端末で作成された文書画像から文書画像検索装置１がデータファイル２を生成し、文書データベース１１に登録してもよい。この場合、文書画像は、外部のユーザ端末からネットワークを介して文書画像検索装置１にダウンロードされてもよいし、メモリカードなどの記憶媒体から文書画像検索装置１に読み込まれてもよい。
【００３３】
文書画像検索装置１は、文書画像の頁毎に、サムネール画像２２と特徴量データ２３とを生成する。そして文書画像検索装置１は、文書画像を格納した文書ファイル２１にサムネール画像２２と特徴量データ２３とを付加してデータファイル２を生成し、文書データベース１１に登録する。
【００３４】
なお、本実施形態では、文書データベース１１が補助記憶デバイス４４上で構成されるものとして説明を続けるが、これに限るものではない。例えば通信インターフェース４７を介してアクセスできるネットワーク上の記憶装置に文書データベース１１を構成してもよい。また、サムネール画像２２と特徴量データ２３とは補助記憶デバイス４４が記憶し、文書ファイル２１はネットワーク上の記憶装置が記憶するというように、データファイル２を分けて記憶してもよい。
【００３５】
文書画像検索装置１は、ユーザ端末３から、紙等の印刷媒体に印刷された文書画像を撮影またはスキャンして得られる問合せ画像を受信すると、文書データベース２を検索して、その問合せ画像の元となる文書画像のデータが格納されたデータファイル２を特定し、そのデータファイル２のデータをユーザ端末３に送信する機能を有する。データファイル２のデータは、文書ファイル２１のデータだけでもよい。データファイル２そのものをユーザ端末３に送信してもよい。この機能は、入力セクション１２１、検索セクション１２２及び送信セクション１２５によって実現される。
【００３６】
文書データベース２を検索した結果、問合せ画像の元となる文書画像に類似した画像のデータファイル２を複数検出した場合、文書画像検索装置１は、この類似画像を候補画像としてユーザに選択を促す。そしてユーザによって選択された候補画像のデータファイル２を、問合せ画像の元となる文書画像のデータが格納されたデータファイル２として特定し、そのデータファイル２のデータをユーザ端末３に送信する機能を有する。データファイル２のデータは、文書ファイル２１のデータだけでもよい。データファイル２そのものをユーザ端末３に送信してもよい。この機能は、出力セクション１２３、受付セクション１２４及び送信セクション１２５によって実現される。
【００３７】
［検索セクション１２２の詳細説明］
図４は、検索セクション１２２の具体的な処理手順を示す流れ図である。この処理は、ＣＰＵ４１が、ＲＯＭ４２または補助記憶デバイス４４に格納されるアプリケーションプログラムの１つである照合プログラムにしたがって実行する。なお、図４に示すとともに以下に説明する処理の内容は一例であって、同様な結果を得ることが可能な様々な処理を適宜に利用できる。
【００３８】
・Act１．歪補正処理
照合プログラムは、入力セクション１２１を介して問合せ画像５０（図５を参照）が入力されると起動する。問合せ画像５０の一例を図５に示す。問合せ画像５０は、文書画像の所望の頁をカメラで撮影した画像若しくはスキャナでスキャンした画像である。以下では、この問合せ画像５０を用いた場合について説明する。
【００３９】
照合プログラムが起動すると、ＣＰＵ２１は、Act１として、問合せ画像５０に対して歪補正処理を行う。この処理は、問合せ画像５０の縦および横の方向を元の文書と同じ方向に合わせるための処理である。印刷物をスキャナで読取る場合、印刷物を原稿台へ斜めに置いたり、印刷物を搬送する際の機械的なずれにより、斜めに傾いて読み取られたりする可能性がある。また、デジタルカメラなどで印刷物を撮影する場合、カメラの光軸と印刷物の向きやその距離に応じてさらに高次の歪みが発生する。この歪は一般に射影変換で表され、印刷物上の長方形が一般的な四角形に変換される。このように歪んだ問合せ画像を元の画像と同じ向きになるように補正する。文書画像は縦、横方向の直線成分を多くもっているので、これらの直線成分を検出して、これが縦横の直線に戻るように逆射影変換を行うことによって補正する。
【００４０】
・Act２．濃度信号への変換
歪補正処理が終了すると、ＣＰＵ４１は、Act２として、歪補正された問合せ画像５０を濃度信号に変換する。濃度信号は、下地部分すなわち何も印刷されていない紙の部分で“０”となり、インクが濃い部分ほど大きな値をとる信号である。
【００４１】
先ずＣＰＵ４１は、カラー画像のＲＧＢ信号をモノクロ画像の信号に変換する。本実施形態では、明度Ｙを用いてＲＧＢ信号をモノクロ画像の信号に変換する。ＲＧＢ値から明度Ｙを算出する演算式は、（１）式となる。
【数１】
2015191308.tif 000003
【００４２】
ＣＰＵ４１は、問合せ画像５０の全画素(x,y)について（１）式を演算して、画素毎に明度Ｙ(x,y)を算出する。画素毎に明度Ｙ(x,y)を算出したならば、ＣＰＵ４１は、明度Ｙ(x,y)のヒストグラムを作成する。
【００４３】
ヒストグラム６０の一例を図６に示す。ヒストグラム６０は、問合せ画像５０の画素毎の明度Ｙ(x,y)の分布を示す。図６に示すように、ヒストグラム６０には、頻度が高い部分（ピーク値）が少なくとも１か所存在する。ＣＰＵ４１は、この頻度が高いピーク値のなかで、明度Ｙ(x,y)が最も高いピーク値を下地領域の色情報、すなわち明度値Y0とする。またＣＰＵ４１は、このヒストグラム６０において、明度Ｙ(x,y)が最も小さい値を最小明度値Yminとする。
【００４４】
ＣＰＵ４１は、問合せ画像の画素毎に、明度値Y0と最小明度値Yminとを用いて、（２）式により濃度信号Ｄ(x,y)を計算する。なお、（２）式において、Y(x,y)は、画素(x,y)の色情報（明度値）である。すなわち（２）式は、下地領域の色情報［明度値Y0］と当該画素(x,y)の色情報［明度値Y(x,y)］との間の距離［Y0−Y(x,y)］を求め、この距離を当該画素(x,y)の濃度信号Ｄ(x,y)として算出する演算式である。
【数２】
2015191308.tif 000004
【００４５】
この計算により、明度Ｙ(x,y)が下地部分と同じまたは高い画素(x,y)は０となり、明度Ｙ(x,y)が画像内で最小の画素(x,y)は１となるように、濃度信号Ｄ(x,y)が規格化される。
【００４６】
ところで、印刷物の文書画像をカメラで撮影する場合には、照明やカメラの光学系に起因する照度ムラを生じる可能性がある。照度ムラの程度によっては照度ムラの補正を行う必要がある。この補正も、Act２の処理で行う。
【００４７】
照度ムラの補正方法としては、以下の方法がある。例えば、文書画像を撮影する前に一様な色の物を文書画像と同じ位置において撮影し、得られた画像データを用いて補正する方法がある。あるいは、撮影画像をメッシュ状の領域に分割し、領域毎に下地部分の有無を判定する。そして、下地部分がある領域については下地部分の明度値Y0を用い、下地部分がない領域については周辺の領域の下地部分を用いて補正する方法がある。
【００４８】
・Act３．濃度分布統計量の計算
問合せ画像５０の信号を濃度信号に変換し終えると、ＣＰＵ４１は、Act３として問合せ画像５０の濃度分布統計量を計算する。濃度分布統計量は、問合せ画像５０の特徴量を示すデータであり、具体的には、問合せ画像５０の横方向（ｘ方向）における濃度分布の重心位置μx及び標準偏差σxと、縦方向（ｙ方向）における濃度分布の重心位置μy及び標準偏差σyである。
【００４９】
先ずＣＰＵ４１は、問合せ画像５０の濃度信号について、それぞれ横方向に並ぶ全画素の濃度値を加算した射影濃度と縦方向に並ぶ全画素の濃度値を加算した射影濃度とを求める。本実施形態では、横方向に並ぶ全画素の射影濃度をf(y)とし、縦方向に並ぶ全画素の射影濃度をg(x)とする。ＣＰＵ４１は、（３）式により射影濃度f(y)と射影濃度g(x)とを算出する。
【数３】
2015191308.tif 000005
【００５０】
次にＣＰＵ４１は、横方向における射影濃度f(y)の分布と、縦方向における射影濃度g(x)の分布とから、（４）式により横方向の射影濃度f(y)の分布に対する重心位置μx及び標準偏差σxと、縦方向の射影濃度f(y)の分布に対する重心位置μy及び標準偏差σyとを算出する。
【数４】
2015191308.tif 000006
【００５１】
（４）式により算出される横方向の重心位置μx及び標準偏差σxと、縦方向の重心位置μy及び標準偏差σyとが、濃度信号の横方向及び縦方向における射影濃度の分布を表す統計量である。問合せ画像５０に対する横方向及び縦方向における射影濃度の分布と、各濃度分布統計量（μx，σx，μy，σy）の算出結果の一例とを図７に示す。
【００５２】
・Act４．画像の分割
横方向及び縦方向の濃度分布統計量（μx，σx，μy，σy）を算出し終えると、ＣＰＵ４１は、Act４として問合せ画像５０を複数の領域に分割する。本実施形態では、図８に示すように、縦、横それぞれの方向に２本ずつの分割線（図中一点鎖線）で、問合せ画像５０をマトリクス状に九つの領域A1,A2,A3,…,A9に分割する。分割線の位置Thx1、Thx2、Thy1,Thy2は、重心位置μx，μyを中心に標準偏差σx，σyの０．８倍をプラスマイナスした値である。以後、分割線の位置を分割閾値Thx1、Thx2、Thy1,Thy2と称する。分割閾値Thx1、Thx2、Thy1,Thy2は、（５）式で算出される
【数５】
2015191308.tif 000007
【００５３】
ここで、濃度分布統計量（μx，σx，μy，σy）を用いて分割閾値Thx1、Thx2、Thy1,Thy2を決定する理由について説明する。文書画像を分割する場合、単純には、文書画像全体の外形の位置を基準に分割閾値を決める方法が考えられる。しかし、このような方法で分割閾値を決めるためには、文書画像の縁の位置が分かっていることが前提となる。例えば、定型の用紙に印刷された文書画像をフラットベッドスキャナでスキャニングする場合には、文書画像の縁の位置が一義的に定まるので問題はない。
【００５４】
しかし、例えば紙送り式のスキャナで文書画像を読み取る際に読取スキューが発生した場合、スキュー補正しても文書画像の縁の位置は必ずしも一致しない。また、文書画像をデジタルカメラ等で撮影する場合には、カメラから被写体である文書画像までの距離や相対位置のずれ等の撮影条件によって、撮影画像に含まれる文書画像の倍率やポジションが変化する。このため、文書画像の縁の位置は不明である。したがって、文書画像全体の外形の位置を基準に分割閾値を決める方法は適用できない。
【００５５】
本実施形態は、問合せ画像５０の下地部分における濃度信号を０に正規化する。このため、どのような撮影条件で文書画像を撮影しても、射影濃度分布の重心位置μx，μyは相対的に等しくなる。また、撮影倍率が変わっても、射影濃度分布の標準偏差σx，σyは相対的に同じである。したがって、濃度分布統計量（μx，σx，μy，σy）を用いることで、撮影条件の変動等に関わらず分割閾値Thx1、Thx2、Thy1,Thy2を文書画像に対して相対的に決まった位置に設定できる。
【００５６】
・Act５．濃度比率特徴量の計算
問合せ画像５０を複数（本実施形態では九つ）の領域A1,A2,A3,…,A9に分割したならば、ＣＰＵ４１は、Act５として濃度比率特徴量Ｑを計算する。濃度比率特徴量Ｑは、問合せ画像５０の特徴量を示すデータである。
【００５７】
先ずＣＰＵ４１は、分割領域A1,A2,A3,…,A9毎に、濃度信号の総和S1,S2,S3,….S9を計算する。総和S1は、分割領域A1に存在する各画素の濃度信号の総和であり、総和S2は、分割領域A2に存在する各画素の濃度信号の総和である。他の総和S3,….S9についても同様である。
【００５８】
分割領域A1,A2,A3,…,A9毎に、濃度信号の総和S1,S2,S3,….S9を算出したならば、ＣＰＵ４１は、（６）式の上段の演算式のように、総和S1,S2,S3,….S9を合算して、総和合算値Sallを計算する。そしてＣＰＵ４１は、（６）式の下段の演算式のように、分割領域A1,A2,A3,…,A9毎に、その領域の濃度信号の総和S1,S2,S3,….S9を総和合算値Sallで除算して、濃度比率特徴量B1,B2,B3,….B9を算出する。
【数６】
2015191308.tif 000008
【００５９】
濃度比率特徴量B1,B2,B3,….B9は、各分割領域A1,A2,A3,…,A9における濃度信号の総和S1,S2,S3,….S9の比率である。本実施形態では、濃度比率特徴量B1,B2,B3,….B9を総称する場合に濃度比率特徴量Bと表す。つまり、濃度比率特徴量Bは、｛Bi:1≦i≦9｝を意味する。濃度比率特徴量Bは、濃度が高い領域ほど値が大きくなる。
【００６０】
問合せ画像５０を分割閾値Thx1、Thx2、Thy1,Thy2で９分割した際の分割領域A1,A2,A3,…,A9毎の濃度比率特徴量B1,B2,B3,….B9を図９に示す。すなわち、分割領域A1の濃度比率特徴量B1は0.09であり、分割領域A2の濃度比率特徴量B2は0.11である。他の分割領域A3,…,A9の濃度比率特徴量B3,….B9も、図示のとおりである。
【００６１】
濃度比率特徴量Bの分布は、文書画像の全体的な濃度の分布を表す。すなわち濃度比率特徴量Bは、文書画像に応じた値となる。このため、類似した文書画像同士は、濃度比率特徴量Bが近似する。ただし、濃度の分布だけを見ているので、濃度比率特徴量Bが近いからといって文書画像同士が必ずしも類似しているとは限らない。それでも、この濃度比率特徴量Bを用いることで、２つの文書画像が類似していないということは判断できる。つまり、問合せ画像５０に対して類似していない文書画像のデータファイル２を検索対象から排除することができる。
【００６２】
上述したように濃度比率特徴量Bは、文書画像の射影計算、重心・標準偏差等の統計計算、及び領域内濃度信号の総和の計算といったきわめて簡易な計算で求めることができる。したがって、濃度比率特徴量Bを用いた文書画像同士の類似性判断処理は、高速に処理できる。また、濃度比率特徴量Bは、問合せ画像５０のサイズや傾きなどによらず一定である。このため、濃度比率特徴量Bを用いた文書画像同士の類似性判断処理は、信頼性が高い。
【００６３】
・Act６．粗候補画像の選定
問合せ画像５０の濃度比率特徴量Bを算出したならば、ＣＰＵ４１は、Act６としてこの濃度比率特徴量Bを用いて問合せ画像５０に類似した候補画像の選定を行う。
【００６４】
先ずＣＰＵ４１は、問合せ画像５０の濃度比率特徴量B（Bi:1≦i≦9）と、文書データベース１１に登録されているすべてのデータファイル２の濃度比率特徴量BD（BDi:1≦i≦9）との距離Ｌを（７）式により計算する。すなわちＣＰＵ４１は、分割領域A1,A2,A3,…,A9毎の濃度比率特徴量B1,B2,B3,….B9と濃度比率特徴量BD1,BD2,BD3,….BD9との差の二乗和の平方根を距離Ｌとして算出する。
【数７】
2015191308.tif 000009
【００６５】
濃度比率特徴量Bと濃度比率特徴量BDとの距離Ｌを算出したならば、ＣＰＵ４１は、この距離Ｌを所定の閾値Ｌthと比較する。そして、距離Ｌが閾値Ｌth以下であればＣＰＵ４１は、その濃度比率特徴量BDを有するデータファイル２に格納される文書画像のデータは、問合せ画像５０に類似する候補画像のデータとして抽出する。
【００６６】
同一文書画像のデータでも、印刷の汚れや書込み、撮影時のノイズ、歪補正の補正誤差、歪補正の補正誤差に起因する重心位置計算誤差等の要因により、濃度比率特徴量Bは変動する。問合せ画像５０の濃度比率特徴量Bが変動したことによって、候補画像として抽出されるべきデータファイル２の文書画像が候補から外れてしまうことがある。このような不具合を解消するために、距離Ｌに対してしきい値Ｌthを設定する必要がある。
【００６７】
本願発明者は、濃度比率特徴量Bの変動量を実験的に測定したところ、最大で０．０４程度であった。そこで本実施形態では、最大変動量の２倍のマージンを取り、しきい値Ｌthを０．０８とする。このように、濃度比率特徴量Bの最大変動量に対して２倍の値をしきい値Ｌthとして設定することにより、濃度比率特徴量Bの変動が候補画像の選定に影響を及ぼさなくなる。
【００６８】
また本願発明者は、多数の文書画像についてそれぞれ濃度比率特徴量Bを算出し、さらに異なる画像間の濃度比率特徴量Bの距離Ｌを算出して、距離Ｌの頻度を求めた。その結果、約９８％の異なる画像の組み合わせにおいて、濃度比率特徴量Bの距離Ｌが０．１以上となることが判明した。したがって、しきい値Ｌthを０．１よりも小さい０．０８に設定することによって、約９８％の画像の組み合わせを除外できるので、文書データベース１１に登録されている文書画像の中の約２％に候補画像を絞り込むことができる。
【００６９】
・Act７．照合処理
Act６の処理では、問合せ画像５０と文書データベースに登録されている各文書画像との濃度比率特徴量B間の距離Ｌのみによって候補画像を選定する。このため、全く類似していない文書画像も候補画像として選定される可能性がある。そこでＣＰＵ４１は、Act７として問合せ画像５０と各候補画像とについて照合し、候補画像が類似画像であるか否かを判定する。具体的にはＣＰＵ４１は、問合せ画像５０と各候補画像間の類似度を計算し、類似度の高い画像を最終候補画像として抽出する。以下、この照合処理について、詳細に説明する。なお、説明の便宜上、問合せ画像５０と照合する候補画像を比較画像５１（図１０を参照）と称する。
【００７０】
はじめに、類似度の算出方法について説明する。本実施形態は、問合せ画像５０と比較画像５１との画素毎の濃度信号の差分の総和によって類似度を算出する。詳しくは、比較画像５１の濃度信号をP(x,y)、問合せ画像５０の濃度信号をQ(x,y)とした場合、ＣＰＵ４１は、濃度信号P(x,y)と濃度信号Q(x,y)との差分の二乗和を求める。
【００７１】
問合せ画像５０は、カメラで撮像され、若しくはスキャナでスキャンされた画像である。このため、デバイス（カメラ，スキャナ）の特性や、画像信号の処理過程によっては、問合せ画像５０の濃度が文書データベース１１上の元画像とずれる可能性がある。濃度にずれを生じた場合、２つの画像の形状が全く一致していても差分の二乗和は０にならない。このためＣＰＵ４１は、問合せ画像５０及び比較画像５１のそれぞれについて、濃度の総和で規格化してから差分をとる。ここで類似度は、値が大きいほど差異が小さくなると定義した方が扱いやすい。そこで、類似度を（８）式のように定義する。すなわち本実施形態では、濃度信号P(x,y)と濃度信号Q(x,y)との差分の二乗和を１から減算した値を類似度Ａと定義する。
【数８】
2015191308.tif 000010
【００７２】
また、問合せ画像５０を撮像若しくはスキャンするときの条件によっては、問合せ画像５０と元画像との間に幾何学的な位置ずれを生じる可能性がある。幾何学的な位置ずれとは、平行移動、回転、相似拡大または縮小等である。幾何学的な位置ずれが生じた場合には、この位置ずれを考慮せずに濃度信号P(x,y)と濃度信号Q(x,y)との差分の二乗和を求めても、正しい結果（類似度）が得られない。
【００７３】
位置関係が未知な２つの画像の類似度を調べる方法として相互相関法が知られている。相互相関法は、（９）式のように２つの画像の相対位置を変えながら類似度A(xd,yd)を算出する方法である。（９）式において、パラメータ(xd,yd)は、相対位置を表す。
【数９】
2015191308.tif 000011
【００７４】
（９）式により各相対位置の類似度A(xd,yd)が算出されると、相互相関法では、（１０）式により、各相対位置の類似度A(xd,yd)が最大となる最大類似度Amaxを求める。
【数１０】
2015191308.tif 000012
【００７５】
（１０）式により求まる最大類似度Amaxが、２つの画像の類似度となる。類似度Amaxは、［0≦Amax≦１］の範囲をとる。すなわち、２つの画像が全く同じ若しくは比例関係にある場合に、類似度Amaxは最大値１となる。そして、２つの画像の類似性が低くなればなるほど、類似度Amaxは小さい値をとる。この関係は、２つの画像に平行移動の位置ずれがあっても変わらない。したがって、相互相関法を用いることによって、２つの画像に平行移動の位置ずれがあっても類似度を求めることができる。しかし、相互相関法には、下記の問題点ａ，ｂ，ｃがある。
【００７６】
ａ．相互相関演算は画像の全画素について計算を行うために、計算量が画素数に比例して膨大になる。  
ｂ．画像の相対位置ずれ量が大きいと、パラメータ（xd,yd）の探索範囲を広くとる必要があり、計算量がさらに膨大となる。  
ｃ．平行移動して比較するだけの相互相関法では、問合せ画像が文書データベース１１の元画像に対して倍率が異なっていたり、回転していたりすると、類似度を正しく求められない。この点は、相互相関演算で平行移動ずれ以外の条件も変えて計算すれば解決できる。しかし、条件が増える分、計算量が指数関数的に増大するので、実用的でない。
【００７７】
本実施形態では、上記の問題点を解決するために、以下のように処理を行うこととした。先ず、文書画像検索装置１は、２つの画像（問合せ画像５０と比較画像５１）を低解像度に変換する。次に、文書画像検索装置１は、２つの画像５０，５１をそれぞれ複数の部分領域に分割する。そして文書画像検索装置１は、対応する部分領域同士についてマッチング処理を行って、部分領域毎に類似度を求める。文書画像検索装置１は、部分領域毎の類似度から画像全体の類似度を求める。
【００７８】
また文書画像検索装置１は、各部分領域の位置ずれ量やその分布により、画像全体の位置関係を計算する。そして文書画像検索装置１は、前段で求めた位置関係のパラメータにより、回転や倍率誤差を含めた位置の補正を行う。その後、文書画像検索装置１は、さらに解像度を上げて、同様に部分領域でのマッチング処理を繰り返す。
【００７９】
このようなマッチング処理の繰返しにより、回転や倍率誤差も補正できる。したがって、上記問題点ｃは解決する。また、低解像度では1画素のサイズが大きいため、画素数換算でみると探索範囲は小さい。しかも順次、位置ずれ量を補正しながらマッチング処理を繰り返すため、２段目以降でも探索範囲を小さくできる。したがって、上記問題点ｂも解決する。さらに、マッチング処理の繰り返しが進むにつれて解像度を上げていくので、計算量が増加する。しかし、本来、類似度の低い画像は1段目のマッチング処理で類似度が低い結果が出ると考えられる。このため、大部分の候補画像は、計算量の小さい1段目のマッチング処理で排除されて、高解像度でのマッチング処理まで進む候補画像は少ない。よって、問題点ａも解決される。
【００８０】
［相対位置行列の説明］
前述したとおり、文書画像検索装置１では、２つの画像（問合せ画像５０と比較画像５１）について部分領域の相互相関をとり、各部分領域の移動量から２つの画像５０，５１間の位置関係を求める。本実施形態では、２つの画像５０，５１間の位置関係を表すのに、相対位置行列を用いる。そこで次に、相対位置行列について簡単に説明する。
【００８１】
相対位置行列を説明するにあたり、２つの画像、すなわち第１の画像と、この第1の画像に平行移動、相似拡大または縮小、回転などの変換をかけた第２画像とを考える。第１の画像の画素(x,y)に対応する第２の画像の画素を(x’,y’)とすると、画素(x,y)と画素(x’,y’)との位置関係は、（１１）式で表される。
【数１１】
2015191308.tif 000013
【００８２】
（１１）式において、θは回転の角度、rは拡大・縮小の倍率、sx,syは平行移動の成分を表す。（１１）式は、同次座標系を用いることにより、（１２）式のように行列Ｔの乗算式にまとめられる。
【数１２】
2015191308.tif 000014
【００８３】
同次座標系とは、座標を表す２次元ベクトルに、ｘ成分及びｙ成分の他に定数１を要素として追加した３次元のベクトルである。このベクトルにより、平行移動も含めた変換を１つの行列乗算式で表現できる。また、数式が簡潔になる。このため、相対位置行列では、この同次座標系の表現を用いる。この表現を、第１の画像に対する第２の画像の相対位置行列と称する。第２の画像に対する第１の画像の相対位置行列は、行列Ｔの逆行列T-1となる。本実施形態では、比較画像５１に対する問合せ画像５０の相対位置行列を、以下、問合せ相対位置行列と称する。
【００８４】
画像の位置ずれと相対位置行列との関係を図１０の具体例を用いて説明する。図１０において、画像５１は、ｘｙ座標軸上に表現された比較画像であり、画像５０は、問合せ画像である。図１０では、説明の便宜上、座標系の原点Ｏを比較画像５１の中央部にとっている。原点Ｏは、比較画像５１の中央部に限定されない。原点Ｏは、比較画像５１の例えば左下隅でもよい。
【００８５】
比較画像５１において、原点ＯからＸ軸の正方向に＋Ｄだけずれた点をＡ、原点ＯからＹ軸の正方向に＋Ｄだけずれた点をＢとする。この場合、原点Ｏの(X,Y)座標値は(0,0)となり、点Ａの(X,Y)座標値は(D,0)となり、点Ｂの(X,Y)座標値は(0,D)となる。
【００８６】
比較画像５１上の３点Ｏ，Ａ，Ｂに対応した問合せ画像５０の３点をＯ’、Ａ’、Ｂ’とする。この場合、図１０に示すように、点Ｏ’の座標を（sx,sy）とすると、この座標（sx,sy）は、原点Ｏの平行移動量を示す。また、点Ｏ’から点Ａ’までの線分Ｏ’Ａ’の長さＬ１’と、原点Ｏから点Ａまでの線分ＯＡの長さＬ１との比ｒ＝Ｌ１’／Ｌ１は、相似拡大または縮小の倍率を示す。この比ｒは、点Ｏ’から点Ｂ’までの線分Ｏ’Ｂ’の長さＬ２’と、原点Ｏから点Ｂまでの線分ＯＢの長さＬ２との比（Ｌ２’／Ｌ２）とも等しい。また、線分Ｏ’Ａ’とＸ軸とのなす角θは、回転成分を示す。これらの値により、比較画像５１上の任意の画素(x,y)と、問合せ画像５０上の対応する画素(x’、y’)との関係は、（１２）式のように一意に決まる。
【００８７】
［照合処理の説明］
次に、照合処理（Act７）の手順について、図１1を用いて具体的に説明する。図１１は、ＣＰＵ４１が実行する照合処理の手順を示す流れ図である。照合処理に入ると、ＣＰＵ４１は先ず、候補画像の中から比較画像５１を選択する（Act１１）。次にＣＰＵ４１は、問合せ相対位置行列の初期値T0を決める（Act１２）。
【００８８】
照合処理では、問合せ相対位置行列を用いて、問合せ画像５０を比較画像５１に近い位置に変換してから、相互相関によるマッチング処理を行う。この場合において、相対位置行列の近似的な値を用いると、相互相関の探索範囲を小さくでき、ひいては処理時間を短縮できる。
【００８９】
相対位置行列の要素である相対位置は、回転、相似拡大または縮小、平行移動の３要素からなる。ここで、回転については、すでに歪補正処理（Act１）により０または十分小さい角度になっているので、回転角θの初期値は０とする。平行移動と相似拡大または縮小については、Act３の処理で求めた濃度分布統計量（μx，σx，μy，σy）を用いて近似値を求める。
【００９０】
比較画像５１の濃度分布統計量の重心位置をμx,μy、標準偏差をσx,σyとし、問合せ画像５０の濃度分布統計量の重心位置をμx’,μy'、標準偏差をσx’、σy’とする。標準偏差は、相似拡大または縮小の倍率に比例する。そこで、比較画像５０に対する問合せ画像５１の平行移動量を(sx0,sy0)、相似拡大または縮小の倍率をr0とすると、標準偏差をσx,σy及び標準偏差をσx’、σy’の関係は、（１３）式で示される。
【数１３】
2015191308.tif 000015
【００９１】
また、比較画像５１の重心位置μx,μyと、問合せ画像５０の重心位置μx‘,μy’とは、画像上のほぼ対応する点となる。したがって、重心位置μx,μyと重心位置μx‘,μy’との関係は、（１４）式で示される。
【数１４】
2015191308.tif 000016
【００９２】
（１３）式と（１４）式とから、（１５）式が得られる。
【数１５】
2015191308.tif 000017
【００９３】
ここで、相似拡大または縮小の倍率r0 は、２通りの式で表される。本実施形態では、２通りの式で表される倍率r0の平均値を倍率r0の近似値として用いる。すなわち倍率r0は、（１６）式で示される。
【数１６】
2015191308.tif 000018
【００９４】
以上により、問合せ相対位置行列の初期値T0は、（１７）式で示される。
【数１７】
2015191308.tif 000019
【００９５】
なお、問合せ画像５０の濃度分布統計量は、Act３の処理で求めた値を用いる。比較画像５１の濃度分布統計量は、事前に計算されて文書データベース１１に格納されているので、文書データベース１１の値を用いる。
【００９６】
［マッチング処理の説明］
問合せ相対位置行列の初期値T0を決めたならば、ＣＰＵ４１は、第１のマッチング処理を行う（Act１３）。図１２は、第１のマッチング処理の手順を示す流れ図である。なお、前述したようにマッチング処理は、解像度を順次高くしながら３回繰り返す。第２及び第３のマッチング処理も、解像度のパラメータが異なるだけで、第１のマッチング処理と同様な手順で処理する。したがって、第２，第３のマッチング処理についてｆ、図１２を用いて詳しい説明は省略する。
【００９７】
・Act３１．変換比較画像を生成
マッチング処理に入ると、先ずＣＰＵ４１は、比較画像５１に対して既定の倍率Ｒで解像度変換を行い、低解像度の比較画像５１を生成する（解像度変換手段）。この解像度変換後の比較画像５１を変換比較画像５１R1と称する。１回目のマッチング処理（第１のマッチング処理）では、倍率Ｒを“１／９”とする。
【００９８】
ここで、説明の便宜上、比較画像５１をP(x,y)、変換比較画像５１R1をP’(x’,y’)とする。なお、以下の説明では、比較画像の符号として「５１」と「P(x,y)」とが混在するが、同じものを指す。同様に、変換比較画像の符号として「５１R1」と「P’(x’,y’)」とが混在するが、同じものを指す。
【００９９】
解像度の変換には投影法（または画素平均法）を用いる。投影法とは、画像の縮小や解像度の低減を行う場合に変換後の画像の画素に相当する元画像のすべての画素の値を用いて変換後の画素値を用いる方式である。投影法の計算式は、（１８）式で示される。
【数１８】
2015191308.tif 000020
【０１００】
因みに、解像度変換の別方法として、線形補間法や最近傍法があるが、これらの方法は、縮小の場合には線が掠れるなどの画質劣化が生じる。このため本実施形態では、投影法を用いる。
【０１０１】
比較画像P(x,y)に対する変換比較画像P’(x’,y’)の相対位置行列TPP’は、定義により（１９）式で示される。
【数１９】
2015191308.tif 000021
【０１０２】
・Act３２．変換問合せ画像を生成
次にＣＰＵ４１は、問合せ画像５０に対して解像度変換を行い、低解像度の変換問合せ画像５０R1を作成する（解像度変換手段）。変換問合せ画像５０R1は変換比較画像５１R1と同じ位置になるように問合せ画像５０を変換したものである。
【０１０３】
ここで、説明の便宜上、問合せ画像５０をQ(x,y)、変換問合せ画像５０R1をQ’(x’,y’)とする。なお、以下の説明では、問合せ画像の符号として「５０」と「Q(x,y)」とが混在するが、同じものを指す。同様に、変換問合せ画像の符号として「５０R1」と「Q’(x’,y’)」とが混在するが、同じものを指す。
【０１０４】
問合せ画像Q(x,y)から変換問合せ画像Q’(x’,y’)への相対位置行列をTQQ’ とすると、この相対位置行列TQQ’は、問合せ画像Q(x,y)から比較画像P(x,y)への相対位置行列と比較画像P(x,y)から変換比較画像P’(x’,y’)への相対位置行列との積となる。すなわち、（２０）式で示される。
【数２０】
2015191308.tif 000022
【０１０５】
（２０）式の行列演算式を用いて座標変換を行えば、変換問合せ画像Q’(x’,y’)が得られる。すなわち、変換問合せ画像Q’(x’,y’)の値を求めるには、変換問合せ画像Q’(x’,y’)の座標の同次ベクトル(x,y,1)に相対位置行列TQQ’の逆行列を掛ける。この演算により得られるベクトル（x’,y’,1）は、対応する問合せ画像Q(x,y)の座標位置となるので、この位置の画素値を求めればよい。
【０１０６】
変換問合せ画像Q’(x’,y’)の座標（x’,y’）は、一般に整数にはならずに小数の端数が生ずる。しかし、四捨五入により最近傍の1画素の値を座標（x’,y’）として用いてもよいし、周囲の４画素の画素値から線形補間などで座標（x’,y’）を求めてもよい。
【０１０７】
図１０に示す比較画像５１と問合せ画像５０に対する変換比較画像５１R1と変換問合せ画像５０R1の例を図１３の（ａ）、（ｂ）に示す。
【０１０８】
・Act３３．変換画像を部分領域に分割
ＣＰＵ４１は、図１３に示すように、変換比較画像５１R1および変換問合せ画像５０R1を、それぞれ９つの部分領域に分割する。ここで、それぞれの部分領域をP1,P2,P3,…，P9、Q1,Q2,Q3,…，Q9とする。また、それぞれの画像の対応する領域（たとえばP1とQ1）の全体画像に対する位置とサイズはそれぞれ同じにする。さらに、中央の部分領域P4,Q4に対して他の部分領域が点対称になるように配置する。これは、後に述べるように相互位置行列の計算を簡易にするためである（分割手段）。
【０１０９】
図１３において、破線で囲まれた領域が変換比較画像５１R1および変換問合せ画像５０R1の部分領域P1,P2,P3,…，P9、Q1,Q2,Q3,…，Q9となる。変換比較画像５１R1および変換問合せ画像５０R1は解像度を落としているため、画素サイズが大きい。このため、相互相関をとる場合の探索範囲を小さくできる。また、画像がぼけるため、倍率や回転の量が小さければ部分領域内では平行移動の成分が大きくなる。このため、平行移動だけでも類似度が高くなる。
【０１１０】
・Act３４．部分領域毎の相互相関計算
ＣＰＵ４１は、変換比較画像５１R1および変換問合せ画像５０R1の各部分領域P1,P2,P3,…，P9、Q1,Q2,Q3,…，Q9について、それぞれ対応する領域毎に相互相関計算を行う。相互相関の計算式は、（２１）式に示される。
【数２１】
2015191308.tif 000023
【０１１１】
相互相関計算は、２つの領域を相対的に平行移動させ、その相対位置を変えて類似度を計算する。類似度Ａは０≦Ａ≦１の範囲の値をとる。類似度Ａは、画像同士が近いほど類似度が高くなり、完全に同じ場合には値１となる。この類似度が最大となる最大類似度Ａmaxの相対位置を求めることにより、２つの領域の位置ずれ量及びずれ方向を求めることができる。この位置ずれ量及びずれ方向をずれベクトルと称する。
【０１１２】
（２１）式において、パラメータxd,ydは、相対位置パラメータである。相対位置パラメータxd,ydは、例えば、(-3≦xd≦3, -3≦yd≦3)の範囲の値をとる。領域をiとしたとき、この領域ｉのずれベクトルは(xd i,yd i)で示される。また、そのときの最大類似度は、Amaxiで示される。
【０１１３】
ＣＰＵ４１は、他の８つの領域の組についても同様に相関計算を行い、それぞれの部分領域でのずれベクトル(xd i,yd i)とそのときの最大類似度Amaxを求める（領域類似度演算手段）。
【０１１４】
・Act３５．画像全体の類似度を計算
ＣＰＵ４１は、９つの各部分領域P1,P2,P3,…，P9、Q1,Q2,Q3,…，Q9の各類似度Amax iから画像全体の類似度を計算する。本実施形態では、（２２）式に示すように、各類似度Amax iの平均値Amax_ave を全体画像の類似度、すなわち全体類似度とする（全体類似度判定手段）。
【数２２】
2015191308.tif 000024
【０１１５】
なお、本実施形態では、各類似度Amax iの平均値Amax_ave を全体類似度としたが、全体類似度の算出方法は、これ限定されるものではない。分割領域によっては、原稿内容の濃度の総量が極端に異なる場合がある。このような場合には、濃さの小さい部分領域の重みを小さくした方が実感の類似度に近くなる。そこで例えば、比較画像の濃度平均値Psumで重みづけした類似度を全体類似度と計算してもよい。
【０１１６】
・Act３６．類似比較処理
ＣＰＵ４１は、Act３５の処理で得られた全体類似度Amax_aveを、所定の閾値ThrA1と比較する。そして、全体類似度Amax_aveが閾値ThrA1以下の場合、ＣＰＵ４１は、画像全体としての類似度が低いためこの比較画像５１は問合せ画像５０とは類似しないと判定する（Act３６にてＮＯ：判定手段）。この場合、ＣＰＵ４１は、マッチング処理を終了する。
【０１１７】
全体類似度Amax_aveが閾値ThrA1よりも大きい場合、ＣＰＵ４１は、比較画像５１は問合せ画像５０に類似すると判定する（Act３６にてＹＥＳ：判定手段）。この場合、ＣＰＵ４１は、Act３７及びAct３８の処理を実行して、マッチング処理を終了する。
【０１１８】
・Act３７．相対位置行列を計算
ＣＰＵ４１は、９つのずれベクトル(xd i,yd i)を用いて変換比較画像P’(x’,y’)に対する変換問合せ画像Q’(x’,y’)の相対位置行列の計算を行う。Act３４の処理で得られた各部分領域iのずれベクトルをdiと称する。このベクトルdiは、近似的に各部分領域iの中心点のずれベクトルと考えられる。部分領域の中心点の位置ベクトルをpiとする。本実施形態では、画像の中心を座標原点Ｏ（０，０）においているので、中央の部分領域p5の中心は原点Ｏ（０，０）となる。
【０１１９】
図１３に示した各部分領域に対するずれベクトルdiと中心点の位置ベクトルpiの例を図１４に示す。なお、実際のずれベクトルdiの長さは領域のサイズに比べて短い。しかし、わかりやすくするために、図１４では、ずれベクトルdiを実際の長さより拡大して表記している。
【０１２０】
変換比較画像P’(x’,y’)と変換問合せ画像Q’(x’,y’)との位置関係は、平行移動、相似拡大または縮小、回転の組合せよりなると考えられる。これらの平行移動量を（sx’,sy’）、相似拡大または縮小の倍率をr’、回転角をθ’とする。これら平行移動量（sx’,sy’）、相似拡大または縮小の倍率r’、及び、回転角θ’は、位置ベクトルpiとずれベクトルdiとから、以下のように計算できる。
【０１２１】
すなわち、原点の平行移動量(sx’,sy’)は、（２３）式に示すように、９つのずれベクトルdiの平均値dmとなる。
【数２３】
2015191308.tif 000025
【０１２２】
また、相似拡大または縮小の倍率をr’とすると、「di-dm＝r’・pi」の方程式が成立するはずである。しかし、ずれベクトルdiには誤差が入るため、（２４）式に示すように、両辺に位置ベクトルpiを掛けてiについての和をとる。
【数２４】
2015191308.tif 000026
【０１２３】
ここで、中央以外の部分領域は、中央の部分領域に対して点対称になるようにとっているため、「Σpi =0」となる。したがって、相似拡大または縮小の倍率r’は、次の（２５）式で示される。
【数２５】
2015191308.tif 000027
【０１２４】
上記と同様に、回転角をθ’とすると、（２６）式が成立する。（２６）式において、「×」はベクトルの外積を表す。
【数２６】
2015191308.tif 000028
【０１２５】
（２６）式の両辺についてiの総和をとると、（２７）式となる。
【数２７】
2015191308.tif 000029
【０１２６】
（２７）式により、sx’、sy’、r’、θ’の推定値が得られる。この推定値sx’、sy’、r’、θ’により、相対位置行列T’は（２８）式で示される。
【数２８】
2015191308.tif 000030
【０１２７】
・Act３８．相対位置行列を修正
本実施形態では、問合せ画像Q(x,y)から相対位置行列Tを用いて変換比較画像P’(x’,y’)と同じ位置になるように変換問合せ画像Q’(x’,y’)に変換する。したがって、最初の相対位置行列Tが正確ならば、変換比較画像P’(x’,y’)と変換問合せ画像Q’(x’,y’)との間の相対位置行列T’は、恒等行列となるはずである。換言すれば、相対位置行列T’が恒等行列でなかった場合には、最初の相対位置行列Tに誤差があったことになる。この誤差は、相対位置行列T’を用いて修正することができる。この考えに基づいて、ＣＰＵ４１は、相対位置行列Tの修正・更新を行う。
【０１２８】
この処理は、図１５の更新の模式図を用いて説明する。図１５において、画像間の矢印は、矢印の上に表記されている行列が始点の画像に対する終点の画像の相対位置行列であること表している。Act３２の処理で説明したように、変換比較画像P’(x’,y’)は、比較画像P(x,y)を倍率R1で縮小したものであるから、比較画像P(x,y)に対する変換比較画像P’(x’,y’)の相対位置行列はTRとなる。相対位置行列TRは、（２９）式で示される。
【数２９】
2015191308.tif 000031
【０１２９】
変換問合せ画像Q’(x’,y’)は、Act３３の処理で説明したように、問合せ画像Q(x,y)を相対位置行列TQQ’で変換したものである。このため、この相対位置行列TQQ’が問合せ画像Q’(x’,y’)に対する変換問合せ画像Q’(x’,y’)の相対位置行列である。
【０１３０】
また、Act３７の処理では、変換比較画像P’(x’,y’)に対する変換問合せ画像Q’(x’,y’)の相対位置行列T’を求めた。この処理を参考にすると、比較画像P(x,y)に対する問合せ画像Q(x,y)の相対位置行列T1は、（３０）式で示される。
【数３０】
2015191308.tif 000032
【０１３１】
このように、ＣＰＵ４１は、マッチング処理を行うことにより、２つの画像５０，５１の類似度と相対位置行列の両方を求めることができる。ここで、第１のマッチング処理を低解像度で行っているのは、計算量の低減のためである。先ず、低解像度画像で類似度と相対位置行列とを計算することにより、画像の画素数が小さくでき、相互相関計算の計算量を低減することができる。また、低解像度画像であるため１画素の大きさが大きい。このため、相対位置パラメータxd,ydの範囲を小さくすることができる。この点からも、計算量を小さくできる効果を奏する。また、元画像の類似度が高い場合は、後述のように第２、第３のマッチング処理を行う。その場合、トータルの計算量はそれほど小さくはならないが、類似度の低い比較画像は、計算量の小さい第１のマッチング処理で照合処理が完了するため、トータルの計算量は小さいものとなる。
【０１３２】
図１１の説明に戻る。
【０１３３】
第1のマッチング処理が終了すると、ＣＰＵ４１は、比較画像５１が問合せ画像５０に対して類似度の高い類似画像であるか否かを判定する（Act１４）。類似画像でないと判定した場合（Act１４にてＮＯ）、ＣＰＵ４１は、Act２２の処理に進む。
【０１３４】
類似画像であると判定した場合には（Act１４にてＹＥＳ）、ＣＰＵ４１は、第２のマッチング処理を行う。
【０１３５】
第１のマッチング処理では、低い解像度で類似度および相対位置パラメータの計算を行っているため、類似度の精度の高い判定ができない。また、相対位置パラメータの精度も十分ではない。このため、さらに高精度での類似度判定と相対位置パラメータの更新のために第２のマッチング処理を行う（Act１５）。
【０１３６】
第２のマッチング処理では、縮小倍率Ｒを1/3とする。また、相対位置パラメータxd,ydの範囲を、第1のマッチング処理より狭くして、(-2≦xd≦2, -2≦yd≦2)とする。この値にした理由は、前段の第１のマッチング処理と第２のマッチング処理との解像度の縮小率の比率が「３」であり、第１のマッチング処理での相対位置パラメータxd,ydが第２の解像度の画像上での３画素以内の精度となっていると考えられるからである。解像度の縮小率の比率が大きい場合には、その値に応じてこの範囲を広げることが好ましい。
【０１３７】
第２のマッチング処理が終了すると、ＣＰＵ４１は、比較画像５１が問合せ画像５０に対して類似度の高い類似画像であるか否かを判定する（Act１６）。類似画像でないと判定した場合（Act１６にてＮＯ）、ＣＰＵ４１は、Act２２の処理に進む。
【０１３８】
類似画像であると判定した場合には（Act１６にてＹＥＳ）、ＣＰＵ４１は、第３のマッチング処理を行う（Act１７）。第３のマッチング処理では、第２のマッチング処理よりも解像度を上げる。例えば、比較画像の原解像度すなわち変換倍率Ｒを「１」として、マッチング処理を行う。そしてＣＰＵ４１は、第１または第２のマッチング処理と同様に、類似度の計算し、相対位置行列を更新する。この相対位置行列が最終的な相対位置行列となる。
【０１３９】
第３のマッチング処理が終了すると、ＣＰＵ４１は、比較画像５１が問合せ画像５０に対して類似度の高い類似画像であるか否かを判定する（Act１８）。類似画像でないと判定した場合（Act１８にてＮＯ）、ＣＰＵ４１は、Act２２の処理に進む。
【０１４０】
類似画像であると判定した場合には（Act１８にてＹＥＳ）、ＣＰＵ４１は、最終的な類似度判定処理を行う（Act１９）。この処理は、例えば第３のマッチング処理で更新した相対位置行列を用いて問合せ画像５０を変換し、得られた変換問合せ画像５１R1と比較画像５１との類似度を計算する。すなわち、部分領域への分割は行わず、画像全体領域で類似度を計算する。
【０１４１】
この処理で得られた最終的な類似度Ａを所定の閾値と比較し、比較画像５１が問合せ画像５０と同じであるかどうかの最終判定を行う（Act２０）。類似度が所定の閾値に満たない場合（Act２０にてＮＯ）、ＣＰＵ４１は、Act２２の処理に進む。
【０１４２】
類似度が所定の閾値以上である場合には（Act２０にてＹＥＳ）、ＣＰＵ４１は、比較画像５１を最終候補画像として抽出する（Act２１：検出手段）。その後、ＣＰＵ２２は、Act２２の処理に進む。因みに、類似度の閾値は0.8〜0.9程度が妥当である。たたし、後述するように問合せ画像に手書きの追記がある画像も考慮する場合には、これより低い値にすることが望ましい。
【０１４３】
Act２２では、ＣＰＵ４１は、未選択の候補画像の有無を判定する。未選択の候補画像有りの場合には（Act２２にてＹＥＳ）、ＣＰＵ４１は、Act１１の処理に戻る。そしてＣＰＵ４１は、未選択の候補画像の中から比較画像を選択して,Act１２〜Act２２の処理を再度繰り返す。
【０１４４】
Act２２にて未選択の候補画像無しと判定した場合には（Act２２にてＮＯ）、ＣＰＵ４１として、候補画像を出力する（Act２３）。例えばＣＰＵ４１は、すべての最終候補画像を類似度の高い順に並べて、検索結果としてユーザ端末３に出力する。この出力により、ユーザ端末３では、ディスプレイに最終候補画像が類似度の高い順に表示される。
【０１４５】
検察結果の出力方式は、上記実施形態に限定されるものではない。例えば、ユーザ端末３にて設定された最大候補画像数までを類似度の高い順に出力するといった方法をとってもよい。
【０１４６】
以上で、Act７の照合処理は終了する。照合処理が終了すると、ＣＰＵ４１は、追記領域の抽出処理を実行する（Act８）。
【０１４７】
・Act８．追記領域の抽出
ＣＰＵ４１は、最終候補画像について、追記画像部分の抽出を行う。すなわち、問合せ画像５０が印刷物に手書きなどのメモを記入した画像であった場合に、メモ書きの部分を抽出する。抽出した追記画像は、最終候補画像とリンクさせて保存する。こうすることにより、仮に、問合せ画像とした原稿を破棄してしまっても、文書データベース１１上にある元画像と抽出した追記画像部分とにより、元の原稿を容易に再現することができる。
【０１４８】
なお、本処理の説明では、最終候補画像が１つに絞られていること、及び、何も印刷されていない用紙の白地の領域にメモが追記されていることを前提に説明する。
【０１４９】
図１６は、追記領域抽出処理の詳細を示すブロック図である。追記領域抽出処理は、第１の二値化処理６１、第１の膨張処理６２、第１の位置合わせ処理６３、第２の二値化処理６４、第２の膨張処理６５、差分処理６６、第２の位置合わせ処理６７及びマスク処理６８からなる。各処理６１〜６８は、ＣＰＵ４１、ＲＯＭ４２、ＲＡＭ４３のコンピュータ部と、このコンピュータに追記領域抽出処理を実現させるためのプログラムとによって実現される。
【０１５０】
第１の二値化処理６１は、（３１）式に示すように、最終候補画像の各画素の濃度信号P(x,y)を画素毎に閾値ThDで2値化する。閾値ThDは下地の部分と印刷されている部分が分割できるように下地の濃度よりやや高目の値に設定する。２値化した結果として、濃度が閾値以上の画素値を１、閾値以下の画素値を０とする二値化画像の濃度信号Pb(x,y)を得る。
【数３１】
2015191308.tif 000033
【０１５１】
第１の膨張処理６２は、第１の二値化処理６１で得られた２値化画像の濃度信号Pb(x,y)に、膨張処理をかける。膨張処理は、二値化画像の画素値が１の画素およびそれに隣接する８画素（x+1,y）,(x+1,y+1),(x,y+1),(x-1,y+1),(x-1,y),(x-1,y-1),(x,y-1),(x+1,y-1)の画素値を１とし、それ以外の画素値を０とする。その結果を膨張画像の濃度信号Pf(x,y)として表す。
【０１５２】
第１の位置合わせ処理６３は、問合せ画像の各画素の濃度信号Q(x,y)が最終候補画像と同じ位置になるように、相対位置パラメータを用いて濃度信号Q(x,y)を変換する。そして、変換後画像の濃度信号Q4(x,y)を得る。
【０１５３】
第２の二値化処理６４は、変換後画像の各画素の濃度信号Q4(x,y)を画素毎に閾値ThD2で２値化する。この処理も、第１の二値化処理６１と同様に下地部分を抽出するものであり、２値化した結果として、濃度が閾値以上の画素値を１、閾値以下の画素値を０とする二値化画像の濃度信号Qb(x,y)を得る。
【０１５４】
第２の膨張処理６５は、第２の二値化処理６４で得られた二値化画像の濃度信号Qb(x,y)に対して第１の膨張処理６２と同様の膨張処理を施し、その結果を膨張画像の濃度信号Qf(x,y)として表す。
【０１５５】
差分処理６６は、第１の膨張処理６２で得られた膨張画像の濃度信号Pf(x,y)と第２の膨張処理６５で得られた膨張画像の濃度信号Qf(x,y)とから、（３２）式により、差分領域画像の濃度信号D(x,y)を計算する。
【数３２】
2015191308.tif 000034
【０１５６】
差分領域画像の濃度信号D(x,y)は、膨張画像の濃度信号Pf(x,y)が０すなわち下地で、膨張画像の濃度信号Qf(x,y)が１すなわち非下地の画素のみ１、それ以外の画素は０になる。ここで、値が１の画素が追記領域である。
【０１５７】
第２の位置合わせ処理６７は、問合せ画像の原信号Qo(x,y)が最終候補画像と同じ位置になるように、相対位置パラメータを用いて原信号Qo(x,y)を変換する。そして、変換後画像の濃度信号Qof(x,y)を得る。
【０１５８】
マスク処理６８は、変換後画像の濃度信号Qof(x,y)に対して差分領域画像の濃度信号D(x,y)をマスク処理する。マスク処理は、（３３）式に示すように、濃度信号D(x,y)が１の画素では濃度信号Qof(x,y)の値をそのままにし、濃度信号D(x,y)が０の画素では濃度信号Qof(x,y)の値を白下地と等価な画素値とする。
【数３３】
2015191308.tif 000035
【０１５９】
このような追記画像抽出処理によって、手書き領域では問合せ画像の画素値と同じ、それ以外の領域では白地と同じ色の画素値となり、手書き領域だけ抽出したような画像が得られる。
【０１６０】
以上説明したように、本実施形態によれば、問合せ画像が元画像に対して幾何学的なずれを生じている場合でも、そのずれを補正して２つの画像を照合することができる。したがって、精度よく２つの画像の類似度を算出することができる。
【０１６１】
しかも、相関的なずれの範囲を小さくし、かつ画像の解像度も落として類似度を算出するので、類似度算出に必要な計算量を小さくできる。その結果、２つの画像の類似性を高速に判定できる効果を奏する。
【０１６２】
なお、本発明は、前記実施形態に限定されるものではない。  
例えば前記実施形態は、マッチング処理の段数を３段として説明したが、段数は３段に限定されるものではなく、２段でも、また４段以上でもよい。段数を増やすと、マッチング処理の回数は増えるが、次段のマッチングとの間での解像度比率が小さくなるだけであるので、トータルとしての計算量は３段の場合と大きく変わることはない。
【０１６３】
また、前記実施形態では、Act３３の分割処理において変換比較画像５１R1および変換問合せ画像５０R1をそれぞれ９つの部分領域に分割したが、分割領域数は９に限定されるものではない。各画像の対応する領域の全体画像に対する位置とサイズが同じであり、かつ中央の部分領域に対して他の部分領域が点対称になるように配置されれば、分割数は問わない。
【０１６４】
この他、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６５】
１…文書画像検索装置、２…データファイル、１１…文書データベース、１２…検索処理部、５０…文書画像、１２１…入力セクション、１２２…検索セクション、１２３…出力セクション、１２４…受付セクション、１２５…送信セクション。
【図１】
2015191308.tif 000036
【図２】
2015191308.tif 000037
【図３】
2015191308.tif 000038
【図４】
2015191308.tif 000039
【図５】
2015191308.tif 000040
【図６】
2015191308.tif 000041
【図７】
2015191308.tif 000042
【図８】
2015191308.tif 000043
【図９】
2015191308.tif 000044
【図１０】
2015191308.tif 000045
【図１１】
2015191308.tif 000046
【図１２】
2015191308.tif 000047
【図１４】
2015191308.tif 000048
【図１５】
2015191308.tif 000049
【図１６】
2015191308.tif 000050
【図１３】
2015191308.tif 000051