JP4140221B2

JP4140221B2 - 画像照合装置および画像照合プログラム

Info

Publication number: JP4140221B2
Application number: JP2001284095A
Authority: JP
Inventors: 景則長尾
Original assignee: Fuji Xerox Co Ltd; Fujifilm Business Innovation Corp
Current assignee: Fujifilm Business Innovation Corp
Priority date: 2001-09-18
Filing date: 2001-09-18
Publication date: 2008-08-27
Anticipated expiration: 2021-09-18
Also published as: JP2003091730A

Description

【０００１】
【発明の属する技術分野】
本発明は、画像データ同士を照合する画像照合装置に関する。
【０００２】
【従来の技術】
近年、記憶装置が大容量化し、ネットワークが高速化してきており、これに伴って、文書データや画像データをデータベースに登録して複数の利用者で共有する、文書管理システムが普及しつつある。このような文書管理システムを用いると、他の利用者が作成した文書データや画像データを別の利用者が閲覧、流用することができる。
【０００３】
文書管理システムの効率的な運用のためには、蓄積されている大量のデータの中から閲覧や流用の対象となる文書データ等が迅速に見つけ出せるよう、検索機能の充実が望まれている。そこで従来の文書管理システムでは、文書データや画像データをデータベースに登録する際に、登録者やデータベースの管理者が検索のためにキーワードや所定の分類コードを関連づけて登録するなど、検索に配慮した登録を行う必要があって管理者等の負担が大きくなる。
【０００４】
また、すでに膨大な文書データ等が蓄積されているような場合、またはデータベースシステムの交換などデータの再登録作業を要する場合、改めて全文書データや画像データに対してキーワード等を入力するのは現実的でない。
【０００５】
文書データならば、データベースへの登録処理を自動化するために、システムが文書データからキーワードを抽出する技術や、いわゆる全文検索技術などがある。しかし、紙文書をスキャナ等で読み込んだ文書画像データにはこれらの技術をそのまま適用することはできない。このような画像データに対しては、いわゆるＯＣＲ（Optical Character Recognition）技術を利用して画像データ内に含まれているテキスト部分をテキストデータ化し、このテキストデータに対して上記の全文検索等の処理を行なうことになる。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来の文書管理システムのように、画像データをＯＣＲにて読み込む場合、紙文書に書き込みや押印などのノイズがあったり、文書のレイアウトが複雑である場合は文字認識精度が大幅に低下し、全文検索等の用途に供するには実用的でない。
【０００７】
具体的に通常の企業活動では、社内で回覧されてきた紙文書内の記述（例えばグラフなど）を流用して新たな書類を作成したいというような場合がある。この場合、回覧中になされた手書きの書き込みや押印がなければスキャナにより流用したい部分をデータ化して取り込むことも容易であるが、通常これらが存在するために、取り込みが困難になっていることも多い。そこで文書管理システムのデータベースから原本の画像データを取り出したい、という要望が生まれるのであるが、上記従来の文書管理システムでは、全文検索技術等を利用しているので、テキストデータの存在が前提であるうえ、テキストデータがあっても原本が画像データであるときには、レイアウトが複雑であったりすると（グラフなどではレイアウトは極めて複雑になる）、上述のようにＯＣＲの精度が落ち、テキストデータが正しく取り出されず、その結果、検索用のテキストデータが誤ったものとなり、全文検索の際に見落とされてしまうのである。
【０００８】
そこで、画像データ同士の比較により、所望の画像データの検索を行う技術（類似画像検索技術）が、例えば「コンピュータ画像処理：応用実践編３，総研出版，pp.187-227，1992」で紹介されている。しかし、この技術は自然画のように自由度の大きい画像データには適しているが、構造的に非常に類似した文書を識別するのは難しく、逆に識別能を高めると文書上の書き込みや押印等のノイズに対する耐性が大きく損なわれることが知られている。
【０００９】
また、特開2000-112995号公報には、罫線や線画などの情報のみを用いて画像データの照合を行う技術が開示されている。しかしこの技術ではテキストのみから構成されている文書の照合を行なうことができない。さらに特開平7-282088号公報には、単語長のパターンを照合してテキストを含んだ画像データ同士を照合する技術が開示されている。この技術は単語間が分離しているような言語、例えば英語には適しているが、単語間が必ずしも分離していない日本語にはＯＣＲを用いる必要があり、結局テキストデータを正しく抽出できないような場合には適用できない。
【００１０】
本発明は上記実情に鑑みて為されたもので、書き込みや押印等のノイズがあっても安定した結果を得ることができ、ＯＣＲ等テキストデータを抽出する必要がなく、テキストのみからなる文書データ同士をも照合することのできる画像照合装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記従来例の問題点を解決するための本発明は、画像照合装置であって、処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算する演算手段と、前記各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う手段と、を含むことを特徴としている。
【００１２】
ここで前記経路は、互いに直交する２つの軸方向のそれぞれに沿って複数配列され、各軸方向ごとに累算値系列が演算され、前記照合処理を行う手段が、各軸方向ごとの累算値系列の比較により照合の処理を行うことも好ましい。さらに、前記照合処理を行う手段が、照合の対象となった各画像データについての累算値系列間の相似性に基づき、照合を行うこととするのも好ましい。
【００１３】
また、上記従来例の問題点を解決するための本発明は、前記相似性を検出するために、照合の対象となった各画像データについて、それぞれの累算値系列内での累算値の変化が特徴的となる系列上の位置を表す、系列位置情報を生成し、当該各累算値系列に対する系列位置情報を比較して、少なくとも平行移動量を含んでなる相似変換パラメータを演算し、当該相似変換パラメータを用いて、各累算値系列の相似性を検出することを特徴としている。ここで、相似変換パラメータには、さらに一次変換パラメータを含む。すなわち、相似変換パラメータは、アフィン変換の際に用いられる一次変換係数及び平行移動の量である。また、前記累算値の変化が特徴的となる系列位置情報は、累算値のピーク位置のリストであることが好ましい。
【００１４】
さらに、前記相似変換パラメータを決定するために、照合の対象となった各画像データのうち、相異なる画像データについてのピーク位置のリストを参照し、各ピーク位置同士の組み合わせについて相似変換パラメータを推定し、前記組み合わせごとに推定された相似変換パラメータを含んでなる推定相似変換パラメータ群を生成し、当該推定相似変換パラメータ群に含まれる各推定相似変換パラメータに基づき、尤度の高いパラメータとして前記相似変換パラメータを決定することが好ましい。
【００１５】
すなわち本発明による画像照合装置では、原本である画像データを検索するために、検索対象となる画像を入力し、該入力した画像の水平・垂直方向の少なくとも一方への投影波形を形成し、該水平または垂直方向の投影波形から特徴量を抽出し、前記入力した画像の投影波形、もしくは照合対象となる基準画像（原本の候補となる画像データ群）の投影波形の少なくとも一方に対して、相似変換処理を行なった変換投影波形を生成し、入力した画像の投影波形から抽出された前記特徴量と、前記基準画像の投影波形から抽出された特徴量との対応関係から、前記投影変換手段で適用する変換パラメータを求め、前記入力した画像の投影波形またはその変換投影波形と、前記基準画像の投影波形またはその変換投影波形との類似度を測定する。
【００１６】
具体的に上記抽出される特徴量は、投影波形の局所的ピークであり、該投影波形において検出された全ての局所的ピークの中から、所定の条件を満たすピークの位置のみを選別してピークリスト（系列位置情報）として取り出したものである。
【００１７】
さらに変換パラメータを得るための処理は次のようになる。すなわち、前記入力画像のピークリストにおける局所的ピーク位置と、照合対象となる基準画像のピークリストにおける局所的ピーク位置との対応付けを全てのピーク位置の組み合わせについて行ない、最も尤度の高いパラメータを決定するために、（スケーリング補正量）−（平行移動量）平面において該直線上への投票処理を行ない、該投票処理によって前記（スケーリング補正量）−（平行移動量）平面上に形成された投票値のピーク座標を検出し、該ピーク座標に対応するスケーリング補正量及び平行移動量を見いだす。これは、上記の対応付けにおいて対応付けられた２つのピーク位置を一致させるために必要なスケーリング補正量と平行移動量が直線関係を為すことに基づく。
【００１８】
これにより、画像上の所定経路に対する投影波形を形成し、比較に係る各画像データの投影波形を利用して照合するので、文書への押印、書き込み等があっても、大域的な投影波形の変化状態（波形そのものや微分波形間の相関係数）は一致したままとなり、かかるノイズ成分が類似度測定に与える影響は限定的となる。また、所定経路を水平・垂直方向への各経路とすることで、特に水平・垂直成分を多く含む文書画像に対して高い照合能力を発揮する。
【００１９】
また入力画像の投影波形とデータベース内画像の投影波形との照合に先立って、両波形が最も良く一致するようにアフィン変換による投影波形の相似変換処理を行なうため、入力画像の拡大率の違いや位置ずれを許容することができる。ここで相似変換のためのパラメータ（相似変換パラメータ）は、投票処理、換言すれば多数決原理に基づいて尤度の高いものが求められるため、局所的ピークの検出時に少数の誤検出や検出漏れがあっても補正量は正当なものを求めることができる。
そして、本発明に係る装置は、処理対象となった画像データ及び前記照合の対象となった各画像データについて、それぞれ前記累算値系列の重心位置を計算する手段、を更に備え、前記照合処理を行う手段は、前記処理対象となった画像データの累算値系列の重心位置と、前記照合の対象となった画像データの累算値系列の重心位置と、に基づき、前記相似変換パラメータ中の前記平行移動量の推定存在範囲を限定し、前記推定相似変換パラメータ群から前記平行移動量の推定存在範囲のなかで前記尤度の高いパラメータを前記相似変換パラメータとして決定する。
【００２０】
また、参考例の画像照合方法は、処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算する工程と、前記各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う工程と、を含むことを特徴としている。
【００２１】
さらに、上記従来例の問題点を解決するための本発明は、画像照合プログラムであって、処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算する工程と、前記各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う工程と、をコンピュータに実行させることを特徴としている。
【００２２】
【発明の実施の形態】
本発明の実施の形態について図面を参照しながら説明する。まず、本発明の実施の形態に係る画像照合装置がいかなる原理に基づき画像データ間の照合を行うかについて概括的に説明する。
【００２３】
本実施の形態の画像照合装置は、いわば画像データ自体をキーとして、類似する画像データをデータベースから検索するもので、キーとなる画像データは、スキャナ等の画像入力手段によって読み取られ、ラスタ画像データに変換される。そして、このラスタ画像データに対し、水平方向又は垂直方向の少なくとも一方に対する投影波形を形成する。例えば読み込まれる文書が縦書きであるか横書きであるかが予めわかっており、当該方向の投影波形のみで十分個々の文書の特徴を表すことができることがわかっている場合は、一方向のみへの投影を形成するだけでも良いが、画像データの特徴が不明瞭な場合は両方向への投影波形を形成するのが好ましい。
【００２４】
ここで投影とは、ラスタ形式の画像データに対し、ある経路に沿って、当該経路上の画素の画素値を累算する処理をいい、当該経路が複数ある場合に、その累算した結果の数列が投影波形をなす。コンピュータ処理による場合には画素値の累算結果が経路ごとに得られ、この累算結果の組（累算値系列）により投影波形をディジタル表現することになる。この場合、現実的には投影波形の形成処理前に公知の傾き補正技術を利用して読み取り時の軽微な傾きを補正しておくことが好ましい。
【００２５】
また、データベース内の画像データに対しては、事前に投影波形を作成しておき、画像データと関連づけておくことが好ましい。ここで登録されたデータがスキャナ等によって読み込まれた画像データの場合はそのまま投影波形を生成することができるが、ワープロ等で作成したテキストデータである場合は、これをラスタライズして、画像データに変換し、その後に投影波形の生成を行なう。
【００２６】
なお、投影波形は垂直、水平方向のみならず、任意の複数経路上で画素値を累算するものであって構わないが、比較を行うために、各経路は事前に決定しておく必要があり、また累算を行う順序（各経路の順序、すなわち累算値の演算の順序）を同じにしておく必要がある。累算値系列は順列で比較されるものだからである。
【００２７】
このようにして、キーとなる画像データの投影波形とデータベース内の画像データとの投影波形が求められ、これらの投影波形の類似度を演算して、類似度の高いものを検索結果としてユーザに提示する。
【００２８】
本実施の形態において特徴的なことは、キーとなる画像データに一致する画像データがある場合でも、両画像データの縮尺が変化していたり、読み取りを行う際に異なる解像度で読み取られる可能性があり、投影波形をそのまま比較しても類似度が適切な値とならない場合に配慮して各投影波形に基づき、スケーリングのパラメータを求め、スケーリングの処理を行うことである。また、画像データの読み取りの際の都合によっては画像全体が平行移動した状態で読み取られたり、上下反転したり、縦横が置き換えられたり、傾きをもって読み取られたりする場合もある。このような場合を想定して、投影波形に対し、アフィン変換を施して比較する。これにより相似度によって比較することとなり、検索の正確性を向上できる。
【００２９】
ここでアフィン変換の対象となる投影波形は、データベース内の画像データに関するものであってもよいし、キーとなる画像データであってもよい。データベース内の画像データに対してアフィン変換を行う場合、データベース内の画像データに対し、投影波形を事前に演算してあれば、キーとなる画像データを読み取るスキャナの解像度などに合わせて、この事前に演算して得た投影波形を所定のスケール（既定スケール）にスケーリングした、いわば規格化した投影波形を用意しておくことも好ましい。
【００３０】
次に、このアフィン変換のためのパラメータ（相似変換パラメータ）を求める方法について概説する。本実施の形態では、相似変換パラメータを求めるために、各投影波形の特徴的部分を抽出し、その位置関係を比較して相似変換パラメータを得る。ここで特徴的部分としては、極値（局所的ピーク）、変曲点などの微分波形特徴量であってもよいし、最大値や、所定値となる位置、重心位置、ピークの幅など投影波形自体から得られる特徴量であってもよい。データベース内の画像データに対しては、これらの特徴量を事前に抽出し、対応する画像データに関連づけておくことも好ましい。
【００３１】
例えば各投影波形の局所的ピークが求められた場合、この局所的ピークの位置を求める。通常投影波形内に複数の局所的ピークがあるので、この位置は、位置のリストとなる。この位置のリスト（ピークリスト）が本発明の「系列位置情報」に相当するものとなる。
【００３２】
そしてキーとなる画像データの投影波形に関するピークリストと、データベース内の画像データの投影波形に関するピークリストとを比較して相似変換パラメータを求める。この比較処理においては、各ピーク位置を対応付けして相似変換パラメータを求めるのであるが、例えば図１に概略を示すように、比較される２つの投影波形にそれぞれ３つのピーク（Ａ，Ｂ，Ｃ及びα，β，γ）があり、２つの画像データが同じ画像データである場合に、Ａとα、Ｂとβとを一致させる（正しい）対応付けを行った場合と、Ａとβ、Ｂとγを一致させる（誤った）対応付けをした場合とでは次のように事情が異なる。なお、以下の説明では簡単のため、比較される両画像データの縮尺は一致しているものとする（すなわちスケーリングについては考えない）。なお、図１では説明のため、ピーク以外を平坦で示した。
【００３３】
すなわち、Ａとαとの関係により求められる平行移動量と、Ｂとβとの関係により求められる平行移動量とはほぼ一致するのに対し、Ａとβとの関係により求められる平行移動量と、Ｂとγとの関係により求められる平行移動量は一般に異なるのである。
【００３４】
そこで、すべての対応付けを総当たり的に試行し、各結果同士を比較して多数決原理により最も尤もらしい値（最尤値）を求めることにより、適切な値が求められることになる。
【００３５】
スケーリング補正を要する場合、それぞれのピークリスト内のピーク位置の対応関係からは、スケーリング量ｋと平行移動量ｓとの関係が求められる。すなわち、一方の画像データに関連するピーク位置ｘiと、他方の画像データに関連するピーク位置ξiとを対応づける場合、次の（１）式の関係が得られる。
【００３６】
【数１】

【００３７】
そして各ピーク位置の総当たり的に対応付けて、（１）式による直線をｋ−ｓ平面（（スケーリング補正量）−（平行移動量）平面）に複数描画すると、理想的には多くの直線が交差する座標が求められ、この座標値（ｋ，ｓ）として正しいスケーリング補正量が求められることとなる。ここで「理想的には」というのは、演算の誤差等の要因により、各直線から求められるｋやｓは必ずしも一致しないからである。そこで多数決原理により最尤値を選んでｋ，ｓを決定することになる。このように正しく対応付けがされた場合に、多数のパラメータの候補がある値近傍に集まることに着目し、多数決原理を利用して最尤値を求めているのである。同様にして、例えば一方の画像データの水平方向に対する投影波形のピークリストと、他方の画像データの垂直方向に対する投影波形のピークリストとが正しく対応づけられる（つまりより多数のパラメータ候補があるパラメータ値近傍に集まる）ならば９０度回転したものと判別することができ、この場合に一方のピークリストの順序を入れ替える（要するに一方の投影波形の向きを逆転する）とよりよく対応付けられるとするならば、反転しているものと判別することができるなど、回転、反転、スケーリングなどを含んだ一次変換パラメータを同様の処理によって求めることができる。なお、以下では、説明を簡約にするため、スケーリング補正と平行移動とに限って説明をする。
【００３８】
また、ここまでの説明ではキーとなる画像データの投影波形と、データベース内の画像データに対する投影波形とを比較するとしたが、それぞれの波形を微分して得た、微分波形同士を比較しても良い。キーとなる画像データとして複写文書を用いる場合、画像データに写真やドローイングのような中間調領域を含んでいると、その濃度値は大きく変化している場合が多く、その投影波高値も安定しない場合が多い。このような場合でも投影波形の凹凸の様子は多くの場合維持されているので、比較の対象として微分投影波形を用いる方が好ましい場合も多いからである。
【００３９】
さらに、ここでは投影波形からピークリストを作成するにあたり、投影波形そのものを用いているが、文字列から生成される投影波形には高周波成分が多く、また書き込みや押印などによるノイズ成分も多く含んでいる一方、相似変換パラメータの推定の際には、行のピッチや各行の長さなどの情報を用いれば十分であり、これら行のピッチなどの形状は投影波形の低域成分に反映される。そこで、ノイズ除去や局所的ピーク検出処理の安定化の観点から、投影波形の低域濾波処理を行う。さらに、低域濾波された投影波形にも微小な凹凸が残っているために、数多くの局所的ピークが検出され、演算量が大きくなるので、相似変換パラメータの推定に必要となる大局的な凹凸を表す局所的ピークの位置のみをピークリストに含めることが好ましい。
【００４０】
そこで以下、大局的な凹凸を表す局所的ピークのみを検出する方法について概説する。図２は投影波形の大局的な凹凸の様子を検出するための局所的ピーク検出法を説明する図である。図２において、ｐ（x）は低域濾波後の投影波形の位置ｘにおける波高値、αは所定のウインドウ幅である。局所的ピーク位置では投影波形の傾きがゼロになるが、これを微分投影波形のゼロ交叉点として求めるかわりに、ウインドウの両端位置での投影波高値を結ぶ直線の傾きにより求める。位置Ｘaにおけるこの直線の傾きは次の（２）式のＳ（Ｘa）に比例する。
【００４１】
【数２】

【００４２】
このＳ（Ｘa）の正負が変化する点が局所的ピーク位置である。ここで当該点が正から負へ変化する凸ピークであるか、負から正へ変化する凹ピークであるかを表す情報をピーク属性情報としてピークリストとともに取得しておくことが好ましい。このように注目位置から一定の距離αだけ離れた点での投影波高値を参照することにより、投影波形の微小な凹凸に影響されることなく、投影波形の大局的な凹凸の様子を表すピーク候補を検出することができる。
【００４３】
そしてこれらピーク候補から、相似変換パラメータの検出に有効なピークのみを選別する。相似変換パラメータは投影波形の大局的な凹凸を対応付けることによって求められるため、微小なピークは取り除いた方がよい。
【００４４】
図３は局所的ピークを選別する手段の動作原理を示す図である。図３では図２に示した方法により得られた局所的ピークの候補の位置（ｘ1〜ｘ5までの、計５点）が検出されている。この図３の例では、例えばｘ2やｘ3における局所的ピークが微小な凹凸として除外したいピーク候補である。
【００４５】
微小な局所的ピークを除外するために、本実施の形態では、以下のような処理を行なう。すなわち、ある局所的ピーク位置Ｘnについて、その位置での投影波高値と、隣接する局所的ピーク位置での波高値との差に関する量Ｄnを次の（３）式のように求める。
【００４６】
【数３】

【００４７】
また、位置ｘ1やｘ5のような片側にのみ隣接する局所的ピークを持つものに関しては、その局所的ピークの波高値との差に対する絶対値をＤnとする。
【００４８】
このようにして求めたＤnと所定のしきい値Ｔdとが次の（４）式の条件を満たす場合に、位置Ｘnにおける局所的ピークを実際に比較対照となるピークとしてピークリストに加える。
【００４９】
【数４】

【００５０】
また、隣接する局所的ピーク位置における投影波高値の差ではなく、（５）式に示すような波高値の比Ｒnを用いてピークの選別を行なってもよい。
【００５１】
【数５】

【００５２】
そして、この（５）式により求めたＲnと所定のしきい値Ｔrとが（６）式の条件を満たす場合に、位置Ｘnにおける局所的ピークをピークリストに加える。
【００５３】
【数６】

【００５４】
さらにピークリスト間の比較に補助的に資する目的で、ピーク属性情報として、投影波形の幅と重心を求めておくことも好ましい。これらの情報は変換パラメータ検出に必須のものではないが、後述するように変換パラメータの検出の高速化や信頼性の向上に役立てることができる。
【００５５】
ここでピークの幅を求める場合、投影波形にノイズか含まれておらず、また紙の地色等によるオフセット分も含まれていない場合は、投影波形の非ゼロ区間の幅を以って投影波形の幅とすれば良い。しかし、このような理想的な例は極めて希であるため、実際には投影幅を求めるためには次のような処理を行なう必要がある。
【００５６】
図４は投影波形の幅を検出するための処理を説明する図である。実際の投影波形には図４のＡ，Ｂの領域のようにノイズや紙の地色等によるオフセット分（地色により画素が部分的に「白」でなくなっているために発生する非ゼロ領域）が含まれている。そこでこれらの成分を除去するためにしきい値処理を行なう。ただし、しきい値付近の波高値が多く存在する場合は、しきい値を越えるか否かの微妙な違いが検出される投影波形の幅に大きく影響するため、図４の例では投影波形に対して２つの相異なるしきい値、ＴhとＴlを設定する。これらのうち低い方のしきい値Ｔlは、ノイズやオフセット分のほとんどがこの値を下回るように設定され、高い方のしきい値Ｔhは本来の投影波形のほとんどがこの値を上回るように設定される。
【００５７】
このようなしきい値を設定した上で、投影波形の幅Ｗを次の（７）式により求める。
【００５８】
【数７】

【００５９】
ここで、ｗ（・）は、図５に示すように、０＜ｘ＜Ｔlであるようなｘで「０」、Ｔh＜ｘとなるようなｘで「１」となり、Ｔl＜ｘ＜Ｔhでは、「０」から「１」まで線形に変化する関数である。また、Ｐは投影波形全体を表し、従って（７）式では、投影波形全体に亘って総和することを意味する。このようにしきい値Ｔh、Ｔl間になだらかな勾配を持つしきい値処理関数を設けることにより、単一しきい値を用いた時に問題となるしきい値付近の投影波形が多く存在する場合でも、検出される投影波形の幅に大きく差が生じないようにすることができる。
【００６０】
一方、投影波形の重心位置Ｇは次の（８）式から求められる。
【００６１】
【数８】

【００６２】
こうして求められたピークリスト及びピーク属性情報を利用して相似変換パラメータを求める。次に具体的に相似変換パラメータを求める手続きについて概説する。まずキーとなる画像データと、データベース内の比較対象となる画像データとのそれぞれのピークリストを参照し、ピーク位置の対応付けを行なう。ピーク位置の対応付けはピーク属性情報を参照して凸ピークと凹ピークについて別々に行なう。次に対応付けられた２つの局所的ピーク位置を一致させるために必要なスケーリング補正量と平行移動量が直線関係を為すことに基いて、（スケーリング補正量）−（平行移動量）平面において該直線上への投票処理を行なう。このような投票処理を全ての局所的ピーク位置の組合わせについて行なうと、（スケーリング補正量）−（平行移動量）平面上には投票値の累積値の分布が形成される。（スケーリング補正量）−（平行移動量）平面上において、この累積投票値が大きくなる点は、２つの局所的ピークリストが良く一致することを示しているため、その点の座標（スケーリング補正量，平行移動量）が求める相似変換パラメータとなる。
【００６３】
すなわち、図６に示すように、投影波形に対する局所的凸ピークリスト（Ａ1〜Ａ3）と、キーとなる画像データの投影波形から求められた局所的凸ピークリスト（Ｂ1〜Ｂ4）がある場合、上記２つの局所的ピークリストについてピーク位置の対応付けを行なう。例えば局所的ピークＡ1とＢ1の対応付けを行なう場合、両者のピーク位置が一致するために必要なスケーリング補正量をｋ、平行移動量をｓとすると、Ａ1の座標「１０」と、Ｂ1の座標「１９」とを用いて、次の（９）式が成り立つ。
【００６４】
【数９】

【００６５】
この（９）式はｋとｓに関する一次式であるので、これに基づきｋ−ｓ平面、即ち（スケーリング補正量）−（平行移動量）平面において一本の直線を描画できる。（９）式の条件に拘束されるｋ，ｓを用いれば、比較に係る両画像データは、少なくとも局所的ピーク位置Ａ1とＢ1では重ね合わせることができる。そこで、補正量の候補としてこの直線上に「一票を投じる」。すなわち、この直線上の各点に投票を行う。後にこの投票数の多い点を最尤点として求めたいのである。
【００６６】
また同様にして図６に示した局所的ピークＡ1を他のＢ2〜Ｂ4にも対応付けることにより、（スケーリング補正量）−（平行移動量）平面において、Ａ1に関しては都合４本の直線上への投票を行なうことになる。一般にあるデータベース内の画像データの投影波形から求められた局所的ピークリストにおけるｉ番目のピークの位置をＡix、キーとなる画像データの投影波形に対する局所的ピークリストにおけるｊ番目のピークの位置をＢjxとすると、両者のピーク位置が一致するために必要なスケーリング補正量ｋ、および平行移動量ｓの関係は（１）式と同様に、（１０）式の関係になる。
【００６７】
【数１０】

【００６８】
そして同様の投票処理を残りの局所的ピークＡ2およびＡ3についても行なうことにより、（スケーリング補正量）−（平行移動量）平面上には投票値の累積値の分布が形成される。
【００６９】
尚、投票値は上の例のように常に１票を投じる他にも、局所的ピークの波高値情報を反映した投票値を用いることもできる。局所的ピークについては、その波高値の大きなもの同士、あるいは小さなもの同士を対応付けるのが自然であるから、投票値も波高値に応じて変化させる。すなわち投影波形から求められた局所的ピークリストにおけるｉ番目のピークの波高値をＡis、キーとなる画像データの投影波形に対する局所的ピークリストにおけるｊ番目のピークの波高値をＢjsとして、例えば投票値Ｖを次の（１１）式のように定める。
【００７０】
【数１１】

【００７１】
なお、（１１）式の投票値を適用するためには、局所的ピークの波高値の最大値が所定の値になるようにするなどの正規化処理を前もって行なっておく必要がある。
【００７２】
このようにして（スケーリング補正量）−（平行移動量）平面上に形成された累積投票値は、２つの局所的ピークリストの一致度を反映している。従って、同平面上に形成された累積投票値のピーク点を探索すれば、その点の座標が求める（スケーリング補正量，平行移動量）を表す。この補正量を用いて一方の投影波形に補正を加えることにより、２つの投影波形が最も良く一致することになる。図６の例では（スケーリング補正量，平行移動量）＝（０．９，１０）において（累積投票値）＝３の最大累積投票値を持つことから、登録文書の投影波形を０．９倍し、さらに１０だけ平行移動することにより、２つの投影波形が最も良く一致する。
【００７３】
ところで、上記の補正量を適用すると、被照合文書側の局所的ピークＢ3のみがデータベース内の画像データに対応する局所的ピークを持たないことがわかる。このことから、局所的ピークＢ3は、文書上への書き込みや押印等のノイズによるピーク成分であることと推測される。本実施の形態の相似変換パラメータの検出手続きでは、このようなノイズによる局所的ピークの発生、あるいは検出漏れがあっても、投票処理という多数決原理に基づいて相似変換パラメータが推定されるため、推定される補正量の精度の低下を防止できる。
【００７４】
以上の説明では、（スケーリング補正量）−（平行移動量）平面上に形成された累積投票値のピーク点を探索することにより相似変換パラメータの検出を行なったが、これは「理想的」な例であり、実際には局所的ピーク検出時の誤差や、元々の文書の印刷精度などにより、投票を行なう直線群が厳密に一点で交わることは希である。そこで、相似変換パラメータを推定する手続きとして、（スケーリング補正量）−（平行移動量）平面を、図７のようにスケーリング補正量方向にｎ分割、平行移動量方向にｍ分割したセルに「量子化」して、各セルの投票値の累計を計算し、該累計が最大となるセルを求める方法も考えられる。そして当該累計が最大となったセルの中心座標（ｋc，ｓc）を以って相似変換パラメータの最尤値とする。このようにするとコンピュータ処理にも適合できる。
【００７５】
さらに精度を高めるためには、図８に示すように、投票値の累計が最大となるセルを求めた後、投票を行なう直線群の中から該セルを通過する直線群のみを選び、それら直線群から最短距離に位置する点の座標を求め、当該座標を最尤値とする。このような点の座標は以下の手順により求めることができる。
【００７６】
まず投票値の累計が最大となるセルを通過する直線群がｈ本あるとして、それらが（１２）式で表されるとする。
【００７７】
【数１２】

【００７８】
ただしｉ＝０，１，…，ｈ−１とする。これらの直線の一つと（スケーリング補正量）−（平行移動量）平面上の一点（ｋ，ｓ）との距離ｄiの間には次の（１３）式の関係がある。
【００７９】
【数１３】

【００８０】
点（ｋ，ｓ）から各直線までの距離の２乗和Ｄは、次の（１４）式で示される。
【００８１】
【数１４】

【００８２】
従って、投票値の累計が最大となるセルを通過する直線群から最短距離に位置する点の座標（ｋl，ｓl）は、次の（１５）、（１６）式を連立して解くことによって求めることができる。
【００８３】
【数１５】

【００８４】
さらに、直線群から最短距離に位置する点の座標を求める際に、各直線からの距離を（１１）式に定めた投票値Ｖで重み付けしても良い。投票値Ｖによる重み付けを行なうことにより、局所的ピークの対応付けが正しく行われている可能性が高い直線を重視した補正量検出が行なわれる。この場合、（１４）式は、（１７）式のように変更される。
【００８５】
【数１６】

【００８６】
（１７）式において、Ｖiはｉ番目の直線上への投票値である。またピーク属性情報のうち、投影波形の幅と重心の情報は相似変換パラメータの推定における処理の高速化や信頼性の向上に役立てることができる。
【００８７】
すなわち、一般に投票処理によるパラメータ推定では、不適切な位置に比較的大きなピークを生じる、いわゆるフォールスピーク（false peak）問題を有している。この効果を軽減するためには、投票空間全体への投票を行なうのではなく、明らかに必要ないと思われる領域への投票を行なわないことが有効である。本実施形態においては投影波形の幅と重心の情報を用いて投票領域を限定することにより、変換パラメータ検出処理を高速化すると同時に、上記問題による効果も軽減することができる。
【００８８】
具体的に投影波形の幅を用いて、（スケーリング補正量）−（平行移動量）平面上におけるスケーリング補正量方向の投票領域を限定することができる。データベース内の画像データの投影波形幅をＷr、キーとなる画像データの投影波形幅をＷiとして次の（１８）式に示す投影幅比Ｒを求めると、相似変換パラメータにおけるスケーリング補正量はＲに近い値となるはずである。なぜなら２つの文書が同一の文書であるならば、それらの投影波形も相似形をなしているはずであり、スケーリングの相違は投影幅の比となるはずだからである。
【００８９】
【数１７】

【００９０】
投影波形の幅はノイズや紙の地色等によるオフセット分などに起因する誤差分を含んでいるが、それでもなお、真の補正量、すなわち投票値のピーク位置のスケーリング座標は、（１８）式のＲに近い値であるはずである。そこで（１８）式のＲを中心とした所定のスケーリングマージンβを設定し、そのスケーリングマージンβの範囲内に投票領域を限定する。この場合、（スケーリング補正量）−（平行移動量）平面上に描画した各直線のうち、当該スケーリングマージンβの範囲内に「投票した」こととし、当該範囲の外に対しては「投票」しない。
【００９１】
また、投影波形の重心位置情報からも投票領域の限定を行なうことができる。すなわち、もし特徴抽出手段により求められた重心位置が正確なものであれば、２つの投影波形の重心位置間には（１０）式と同様に次の（１９）式の関係が成立するはずである。
【００９２】
【数１８】

【００９３】
ただし、（１９）式においてＧrとＧiはそれぞれ、データベース内の画像データの投影重心位置とキーとなる画像データの投影重心位置である。実際には求められた重心位置の情報にはノイズや紙の地色等によるオフセット分などに起因する誤差分を含んでいるが、それでもなお、真の補正量、すなわち投票値のピーク位置は（１９）式で表される直線の近傍に位置するはずである。そこで（１９）式の直線を中心として、適当な平行移動量マージンγを設定し、その範囲内に投票領域を限定する。
【００９４】
これにより、投票領域を図９に示した範囲に限定し、この領域外の直線上、あるいはそもそもこの領域を通過しない直線上への投票処理を省略し、処理を高速化するとともに、上記false peak問題による効果を低減できる。
【００９５】
なお、こうして求められた相似変換パラメータに基いて、投影波形の相似変換処理を行なうにあたり、非サンプリング位置での信号を要する場合など、補間処理を要するときには、広く知られている補間法として最近傍法、線形補間法、cubic convolution（３次畳み込み）法、スプライン補間法など様々なものを利用できる。本実施の形態の装置は特に特定の補間法に依存するものではないので、上に挙げた補間法のいずれを用いてもよい。上記の補間法は多くの文献で解説されているため、その説明を省略する。
【００９６】
次に、上述の技法により推定された相似変換パラメータを用いて相似変換した後の投影波形を比較する方法について概説する。理想的には、一方の投影波形を相似変換し、他方の投影波形と比較したとき、両画像データが一致する場合には、これらの投影波形は厳密に一致する。しかし、比較に係る両画像データが同一のものであっても、スキャナの読み取り精度や、キーとなる画像データに押印や書き込みが行われている場合、さらには相似変換パラメータの算出誤差など、様々な理由により両投影波形が厳密に一致することは少ない。また、キーとなる画像データとして複写した後の画像データを用いる場合、文書上にある写真やドローイングのような中間調領域の濃度値は大きく変化している場合が多く、その投影波高値も安定しない場合が多い。従ってノイズ等による投影波形の変形や相似変換パラメータの誤差、文書上の中間調領域に起因する投影波高値の変化などに対しても堅牢な方法で類似度の測定を行なう必要がある。
【００９７】
このような投影波形の照合方法として、本実施の形態では投影波形の微分波形間の相関係数を用いる。これは文書上にある中間調領域によって投影波形の一部にオフセットが加えられていても、その微分波形はほとんど影響を受けることがないことに着目したものである。投影波形の微分波形を生成する方法としては、本来の微分波形を用いる以外にも（２）式で示したＳ（ｘ）を用いることもできる。（２）式のＳ（ｘ）は投影波形上の微小な凹凸の影響を受けにくいため、投影波形照合にＳ（ｘ）を用いると良好な結果が得られることになる。
【００９８】
データベース内の画像データに対し、相似変換を行い、その相似変換後の微分投影波形をｑr（ｘ）、キーとなる画像データの微分投影波形をｑi（ｘ）とすると、両者の相関係数ｒは次の（２０）式のように求められる。
【００９９】
【数１９】

【０１００】
また、Ｌは波形の長さを表す。
【０１０１】
このようにして水平・垂直の両方向に投影波形を形成した場合、両方向の投影波形に対する相関係数がそれぞれ求められる。出力する画像データの類似度の情報としては、これら２つの相関係数を加味したものとしても良いし、どちらか一方の方向に対して照合処理を行なうだけで十分であることがわかっている場合は、その方向の相関係数を類似度として扱ってもよい。
【０１０２】
両方向の相関係数を加味して画像データの類似度を求める例としては、水平・垂直方向について求められた相関係数の和を類似度として出力するものがある。また別の例として、２方向の相関係数の荷重和を類似度とする方法もある。この場合、水平方向の相関係数をｒh、垂直方向の相関係数をｒvとし、水平方向の相関係数の重みをｗh、垂直方向の相関係数の重みを１−ｗhとすれば、出力すべき類似度は次の（２１）式のように表される。
【０１０３】
【数２０】

【０１０４】
どちらかの方向の相関係数が文書画像の違いをより強く反映している場合には、（２１）式によってその方向により大きな重み付けをして類似度の計算を行なうことにより、照合精度を向上させることができる。
【０１０５】
さらに、相似変換パラメータの推定により得られた補正量を類似度に反映させることもできる。これは文書のマージン幅やスケールが大きく異なる場合に別文書として扱いたい場合などに適する。この場合、水平・垂直方向の相関係数やスケーリング補正量、平行移動量などの荷重和により定義される合成変量Ｚを作り、大量の文書サンプルを用いた判別分析により各重みを調整することで、各文書を判別する判別関数を求めることができる。判別分析については多くの文献に解説されているため、詳細は割愛する。
【０１０６】
一方、両方向の相関係数を用いることなく、どちらか一方向の相関係数を類似度として扱う場合について説明する。一般に横書きの文書の場合、横方向の投影には明確な凹凸が現れるが、縦方向の投影には明確な凹凸が生じない場合が多い。このような場合、縦方向の投影波形の照合結果からは文書を特定するための有益な情報は得られないため、対象となる文書が縦書きであるか横書きであるかが予めわかっている場合には、一方向のみの相関係数を用いて類似度の測定を行なった方が好ましい。また、水平・垂直方向の局所的ピークリストに含まれるピーク数の多い方向のみを類似度測定に使用するのも有効な方法である。
【０１０７】
これによりキーとなった画像データに対し、最も高い類似度を示す、データベース内に登録された画像データがキーとなった画像データと同一の文書であると判定されることになる。
【０１０８】
なお、ここまでの説明では、相似変換パラメータの推定時に（スケーリング補正量）−（平行移動量）平面上に形成された累積投票値が最大値を取るピーク点を探索し、そのピーク点の座標を（スケーリング補正量，平行移動量）とする唯一の補正量として用いてきた。しかし、上記平面上では大きな累積投票値を持つ点が複数点形成されることも希ではなく、局所的ピーク検出の過程で多少の誤りが含まれている場合は、累積投票値において２位以下のピーク点に対応する補正量が正しい補正量となる場合もある。このような場合を想定して、上記平面に形成された累積投票値の中で、所定複数のピーク点を求め、それぞれのピーク点に対応する複数通りの補正量で投影波形の変換処理を行なう方法も考えられる。そして、上記複数通りの補正量を用いて変換処理を行なった投影波形を用いて複数通りの類似度を測定し、その最大類似度を最終的な類似度とすることで、より確実な文書画像照合処理を行なうことが可能となる。
【０１０９】
また、（スケーリング補正量）−（平行移動量）平面上に形成された累積投票値が２つの投影波形の一致度を反映しているという点に着目すれば、この投票値自体を２つの投影波形の類似度と見なすことができる場合もある。もしも局所的ピークの誤検出、あるいは検出漏れが無いことが保証できる場合は、上記投票値自体を類似度として使用し、実際の投影波形を相似変換する必要がなく、また変換後の投影波形などを比較する処理もする必要がない。
【０１１０】
以上に、本実施の形態の画像照合装置の動作原理を述べたので、以下、本発明の実施の形態に係る画像照合装置の実装例について説明する。本実施の形態の画像照合装置１は、一般的なパーソナルコンピュータを利用して実現でき、図１０に示すように制御部１１と、記憶部１２と、ストレージ１３と、外部記憶部１４と、スキャナ部１５と、表示部１６とから基本的に構成されている。
【０１１１】
ストレージ１３は、制御部１１によって実行されるオペレーティングシステム等の基本プログラムのほか、画像照合プログラムがインストールされたプログラム格納領域１３ａと、比較対象となる画像データが蓄積したデータ格納領域１３ｂとを含んでいる。
【０１１２】
制御部１１は、ストレージ１３に格納されているプログラムを実行して各種処理を行う。本実施の形態においては、この制御部１１が、画像照合プログラムに従い、本発明の演算手段、及び画像データの照合処理を行う手段を実現している。すなわち、この制御部１１は、キーとなる画像データがスキャナ部１５から入力されると、これを処理対象の画像データとして記憶部１２に格納し、事前に設定された複数の経路に沿って画素値を累算し、演算した経路の順に累算値系列として記憶部１２に格納する処理（演算処理）を実行する。また、制御部１１は、この累算値系列を利用してストレージ１３に蓄積されている画像データと、処理対象の画像データとを照合する処理を実行する。これらの処理については、後により詳しく述べる。
【０１１３】
記憶部１２は、制御部１１のワークメモリとして動作する。外部記憶部１４は、画像照合プログラムなどを格納したコンピュータ読み取り可能な記録媒体（例えばＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなど磁気的乃至光学的に情報を記録したもの）から当該画像照合プログラムなどを読み取って制御部１１に出力し、これによりストレージ１３にインストールさせる処理を行う。
【０１１４】
スキャナ部１５は、光学的に紙媒体の原稿を読み取り、これを画像データに変換して制御部１１に出力する。表示部１６は、制御部１１から入力される指示に従い、種々の情報を表示する。
【０１１５】
ここで制御部１１の画像照合プログラムの処理についてより詳しく説明する。なお、ストレージ１３に蓄積されている画像データについては、予め累算値系列の情報及びピーク位置テーブル（後にその演算方法を説明する）が関連づけられて格納されているものとする。また、以下の説明では累算値の演算の経路は水平方向及び垂直方向であるとし、順序は水平方向については紙面上側から下側へ、垂直方向については左側から右側へ走査した順序であるとする（図１１）。図１１では実線が演算経路を示し、破線が経路の演算順序を示すために用いられている。
【０１１６】
制御部１１は、スキャナ部１５からキーとなる画像データ（処理対象画像データ）の入力を受けてこれを記憶部１２に格納して図１２に示す処理を開始し、まず当該処理対象の画像データに対し図１１（ａ）に示すような水平方向に延びる複数の経路に沿って、当該経路上の画素値を累算し、各経路での累算結果を演算順に記憶部１２に格納する（Ｓ１）。同様に図１１（ｂ）に示したような垂直方向に延びる複数の経路に沿って、当該経路上の画素値を累算し、各経路での累算結果を演算順に記憶部１２に格納する（Ｓ２）。これら処理Ｓ１及びＳ２で累算した結果が本発明の累算値系列となる。ここでは第ｉ番目の演算順序の経路に対する累算値をｐiと表すこととする。
【０１１７】
この累算値を演算するにあたり、白黒画像データであれば、白の点の画素値を「０」、黒の点の画素値を「１」として累算すればよいし、中間調を含む多値画像データであれば、例えば白を「０」、黒を「２５５」等とすればよい。さらにカラー画像データの場合は、その濃度成分を分離して、該濃度画像を上記多値画像と見なして投影値を計算する。濃度成分の分離は、広く知られたカラー値の変換処理により行うことができる。
【０１１８】
制御部１１は、この累算値系列の情報に対し、その高周波成分を除去する低域濾波の処理を行って記憶部１２に格納する（Ｓ３）。この処理は、例えば隣接する経路の累算値の平均値を演算するなどの公知の処理によって行うことができる。そして低域濾波後の累算値系列について、所定のａ（ａは整数）の値を用い、（２）式に対応するＳi＝（ｐi-a）−（ｐi+a）についてｉを順次変化させながらその正負の変化点を見出し、変化点となったｉをピーク候補として取り出す。また、各変化点のｉの情報に、正から負へ変化した凸であるか、負から正へ変化した凹であるかを示すピーク属性の情報を関連づけて、記憶部１２に図１３に示すようなテーブルとして記憶する（Ｓ４）。そして（３）〜（６）式に例示したような処理により、隣接ピークとの大きさの差乃至比に基づき、顕著でないピーク候補を処理Ｓ４で生成したピーク候補のテーブルから削除し、ピーク位置テーブルを生成する（Ｓ５）。
【０１１９】
また、ここで制御部１１は、累算値系列の幅と重心とを（７）及び（８）式により求めて、ピーク位置テーブルに関連づけて記憶部１２に格納する（Ｓ６）。この処理については、既に概説したものを離散的に扱うことによりコンピュータ処理として実現できるので、詳しい説明を省略する。
【０１２０】
ここまでの処理により、記憶部１２には、ピーク位置テーブルとして上記の局所的ピークリスト、すなわち本発明の系列位置情報が格納されているようになる。
【０１２１】
次に、制御部１１はストレージ１３から画像データを順次取り出して（Ｓ７）、記憶部１２上に所定のｎ×ｍの配列を記憶する領域を確保して、この領域の値を「０」に初期化し（Ｓ８）、当該取り出した画像データに関連するピーク位置テーブルと、処理Ｓ６にて記憶部１２に格納したピーク位置テーブルとを比較して、各ピーク位置の対応付け処理を実行する（Ｓ９）。この処理は、各ピーク位置テーブル上のピークについてその第１番目と第ｊ番目、第２番目と第ｊ＋１番目、…といったような対応付けをｊを１から順次設定することによって行う。この処理Ｓ９ではそのうちの対応付けの候補の一つを設定する。
【０１２２】
そして制御部１１は、処理Ｓ９で設定された対応付けの結果に基づき、（１）式（や（９）式）に基づきスケーリング補正量ｋと、平行移動量ｓとの間の関係式を見出して、処理Ｓ９にて確保した記憶領域上に「描画」する（Ｓ１０）。すなわち、スケーリング補正量の最大値がＫ、平行移動量の最大値がＳである場合、（ｘ，ｙ）の位置にある記憶領域がＫ・ｘ／ｎ、Ｓ・ｙ／ｍの値に対応しているから、この記憶領域が（Ｋ・ｘ／ｎ）×ｋ＋ｓ＝（Ｓ・ｙ／ｍ）の関係を満たす場合に、この記憶領域内の値をインクリメント（投票）することになる。これが上記の投票処理に相当する。またここではインクリメントするだけでなく、（１１）式により演算される投票値Ｖを当該記憶領域の値に加算（投票）して上書きしてもよい。
【０１２３】
制御部１１は、さらに処理Ｓ８で設定されていない他の組み合わせがあるか否かを判断し（Ｓ１１）、他の組み合わせがあれば（Ｙｅｓならば）処理Ｓ９に戻って処理を続ける。また、他の組み合わせがなければ（Ｎｏならば）、このｎ×ｍの記憶領域を参照し、値が最も大きい記憶領域上の位置（ｘmax，ｙmax）を検索する（Ｓ１２）。そして、当該（ｘmax，ｙmax）に基づき、スケーリング補正量ｋ、及び平行移動量ｓを決定し、処理Ｓ７で取り出した画像データについて補正処理を行う（Ｓ１３）。補正後の累算値系列λｊ（０≦ｊ＜ｎｋ）は、ｎ個の経路について得られた累算値系列ｐｉ（０≦ｉ＜ｎ）に対し、λｊ＝ｐｌとして求められる。ここでｌは、ｌ＝Ｒｏｕｎｄ（（ｊ−ｓ）／ｋ）となる整数である。Ｒｏｕｎｄ（ｘ）はｘを四捨五入した整数を表すものとする。また、ｌ＜０、またはｌ≧ｎとなるｊについては、λｊ＝０とする。
【０１２４】
また、位置（ｘmax，ｙmax）に基づきスケーリング補正量ｋ及び平行移動量ｓを決定する場合には、その中心座標により、ｋ＝（Ｋ／ｎ）×（ｘmax＋１／２）、ｓ＝（Ｓ／ｍ）×（ｙmax＋１／２）としてもよいし、（１５）式、（１６）式を連立して解く方法によってもよい。なお、後者の場合、当該偏微分方程式を解く方法としては、ニュートン法のような数値解法を利用してもよいし、（１３）式や（１４）式を代入して事前に解析的な解を求めておくこととしてもよい。さらに、明らかに誤りとなる記憶領域上の位置（ｘ，ｙ）について、処理Ｓ１２に先だって当該記憶領域上の位置（ｘ，ｙ）に「０」を設定することも好適である。明らかに誤りであるか否かは、（１８）式に対応した累算値系列内の累算値の個数（系列長）の比によるスケーリング補正量ｋ方向への領域制限、（１９）式により求められる重心位置に基づく領域制限を利用することができる。またここでは処理Ｓ１３の補正処理を処理Ｓ７で取り出した画像データに対して行っているが、キーとなる画像データに対して行ってもよい。この場合処理Ｓ３１のときとはスケーリング補正量は上記ｋの逆数となり、平行移動量は、上記ｓと符号が反対のものとなる。
【０１２５】
そして、この新たな累算値系列λiについて、処理Ｓ１，Ｓ２で演算したキーとなる画像データに対する累算値系列との比較を行う、照合処理を実行する（Ｓ１４）。制御部１１は、当該照合結果を処理Ｓ７で取り出した画像データを識別する情報（例えば当該画像データのファイル名など）に関連づけて記憶部１２に格納する（Ｓ１５）。制御部１１は、まだ取り出していない画像データがあるか否かを調べ（Ｓ１６）、取り出していない画像データがあれば（Ｙｅｓならば）、処理Ｓ６に戻って次の画像データに対して処理Ｓ７〜処理１６を行い（図１２の（Ａ））、取り出していない画像データがなければ（すべての画像データに対して処理を行ったならば；Ｎｏならば）、記憶部１２に格納された照合処理の結果を表示部１６に表示するよう指示して（Ｓ１７）、処理を終了する。
【０１２６】
なお、処理Ｓ１７においては、照合処理の結果、一致度の高い順にソートした画像データの一覧を表示することが好ましい。また、各一覧には、画像データのファイル名を含め、画像データをプレビューしたり、取り出して外部記憶部１４に挿入された媒体にコピーを保存できるようにしておくことが好適である。
【０１２７】
また、制御部１１による照合処理（処理Ｓ１４，Ｓ１５）では、（２０）式で示したような相関係数を演算することによって求めることができる。つまり、水平、垂直の各方向に対し、次の演算を行う。すなわち、ηjについてその差分数列（隣接累算値間の差分からなる系列）に相当するｑr（j）と、キーとなる画像データについての累算値系列ｐiについてその差分数列に相当するｑi（i）を生成し、これについて系列長Ｌを用いて、（２０）式を演算する。こうして水平、垂直の各方向についての相関係数ｒh及びｒvが演算され、これらを利用して類似度Scoreをｒh＋ｒvとして、又は（２１）式のようにして求め、この類似度を照合処理の結果として処理Ｓ１５にて記憶部１２に格納することになる。
【０１２８】
本実施の形態の装置によると、制御部１１が、スキャナ部１５から入力される画像データを処理対象として所定の複数の経路に順次沿って画素値を累算し、当該累算（演算）順に累算値を配列した累算値系列を用いてストレージ１３に蓄積された画像データとの照合を行い、その結果を表示部１６に出力する。従って、これを利用すると、回覧された文書を再利用したい場合、これに書き込みや押印があっても、そのままスキャナ部１５で文書をスキャンして照合を行わせる。制御部１１の処理により、ストレージ１３に蓄積された画像データとの照合が行われて、その結果が表示部１６に表示され、利用者はこの結果を参照して示された文書をストレージ１３から取り出すことができる。
【０１２９】
【発明の効果】
本発明によると、処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算し、各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う画像照合装置としているので、画像データそのものを用い、その累算値系列というような特徴的な量を比較することで照合を実行することにより、書き込みや押印等のノイズがあっても安定した結果を得ることができ、ＯＣＲ等テキストデータを抽出する必要がなく、テキストのみからなる文書データ同士をも照合することができる。
【図面の簡単な説明】
【図１】ピーク位置の対応付けの概要に関する説明図である。
【図２】投影波形の大局的な凹凸の様子を検出するための局所的ピーク検出方法を表す説明図である。
【図３】局所的ピークを選別する手段の動作原理を示す説明図である。
【図４】投影波形の幅を検出するための処理を表す説明図である。
【図５】投影波形の幅を求めるための関数を表す説明図である。
【図６】ピークリストの一例を表す説明図である。
【図７】相似変換パラメータを推定する手続きの概要を表す説明図である。
【図８】相似変換パラメータを推定する手続きの概要を表す説明図である。
【図９】投票領域の制限の一例を表す説明図である。
【図１０】本発明の実施の形態に係る画像照合装置の構成ブロック図である。
【図１１】累算値系列の演算方向を表す説明図である。
【図１２】画像照合装置の処理の一例を表すフローチャート図である。
【図１３】ピークリストとしてのピーク位置テーブルの内容の例を表す説明図である。
【符号の説明】
１画像照合装置、１１制御部、１２記憶部、１３ストレージ、１４外部記憶部、１５スキャナ部、１６表示部。

Claims

処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算する演算手段と、
前記各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う手段と、
を含み、
前記照合処理を行う手段が、照合の対象となった各画像データについての累算値系列間の相似性に基づき照合を行い、前記相似性を検出するために、照合の対象となった各画像データについて、それぞれの累算値系列内での累算値の変化が特徴的となる系列上の位置を表す、系列位置情報を生成し、当該各累算値系列に対する系列位置情報を比較して、少なくとも一次変換係数と平行移動量を含んでなる相似変換パラメータを演算し、当該相似変換パラメータを用いて、各累算値系列の相似性を検出し、
前記累算値の変化が特徴的となる系列位置情報は、累算値のピーク位置のリストであり、
前記照合処理を行う手段が、前記相似変換パラメータを決定するために、照合の対象となった各画像データのうち、相異なる画像データについてのピーク位置のリストを参照し、各ピーク位置同士の組み合わせについて相似変換パラメータを推定し、前記組み合わせごとに推定された相似変換パラメータを含んでなる推定相似変換パラメータ群を生成し、当該推定相似変換パラメータ群に含まれる各推定相似変換パラメータに基づき、尤度の高いパラメータとして前記相似変換パラメータを決定する、
画像照合装置であって、
前記処理対象となった画像データ及び前記照合の対象となった各画像データについて、それぞれ前記累算値系列の重心位置を計算する手段、
を更に備え、
前記照合処理を行う手段は、前記処理対象となった画像データの累算値系列の重心位置と、前記照合の対象となった画像データの累算値系列の重心位置と、に基づき、前記相似変換パラメータ中の前記平行移動量の推定存在範囲を限定し、前記推定相似変換パラメータ群から前記平行移動量の推定存在範囲のなかで前記尤度の高いパラメータを前記相似変換パラメータとして決定する、
ことを特徴とする画像照合装置。
前記処理対象となった画像データ及び前記照合の対象となった各画像データについて、それぞれ、前記累算値系列の前記演算順方向についての幅を求める手段、
を更に備え、
前記照合処理を行う手段は、前記処理対象となった画像データの累算値系列の幅と、前記照合の対象となった画像データの累算値系列の幅と、に基づき、前記相似変換パラメータ中の前記一次変換係数の推定存在範囲を限定し、前記推定相似変換パラメータ群から前記平行移動量の推定存在範囲と前記一次変換の推定存在範囲との交わりのなかで前記尤度の高いパラメータを前記相似変換パラメータとして決定する、
ことを特徴とする請求項１記載の画像照合装置。
コンピュータを、
処理対象となった画像データに対し、複数の所定経路の各々について、経路上の画素値を累算する演算手段、
前記各経路上の画素値を累算した結果を経路の演算順に含んでなる累算値系列を用い、複数の画像データ間の照合処理を行う手段、
として機能させるためのプログラムであって、
前記照合処理を行う手段が、照合の対象となった各画像データについての累算値系列間の相似性に基づき照合を行い、前記相似性を検出するために、照合の対象となった各画像データについて、それぞれの累算値系列内での累算値の変化が特徴的となる系列上の位置を表す、系列位置情報を生成し、当該各累算値系列に対する系列位置情報を比較して、少なくとも一次変換係数と平行移動量を含んでなる相似変換パラメータを演算し、当該相似変換パラメータを用いて、各累算値系列の相似性を検出し、
前記累算値の変化が特徴的となる系列位置情報は、累算値のピーク位置のリストであり、
前記照合処理を行う手段が、前記相似変換パラメータを決定するために、照合の対象となった各画像データのうち、相異なる画像データについてのピーク位置のリストを参照し、各ピーク位置同士の組み合わせについて相似変換パラメータを推定し、前記組み合わせごとに推定された相似変換パラメータを含んでなる推定相似変換パラメータ群を生成し、当該推定相似変換パラメータ群に含まれる各推定相似変換パラメータに基づき、尤度の高いパラメータとして前記相似変換パラメータを決定する、
と共に、前記プログラムは、前記コンピュータを、
前記処理対象となった画像データ及び前記照合の対象となった各画像データについて、それぞれ前記累算値系列の重心位置を計算する手段、
として更に機能させ、
前記照合処理を行う手段は、前記処理対象となった画像データの累算値系列の重心位置と、前記照合の対象となった画像データの累算値系列の重心位置と、に基づき、前記相似変換パラメータ中の前記平行移動量の推定存在範囲を限定し、前記推定相似変換パラメータ群から前記平行移動量の推定存在範囲のなかで前記尤度の高いパラメータを前記相似変換パラメータとして決定する、
ことを特徴とするプログラム。
前記コンピュータを、
前記処理対象となった画像データ及び前記照合の対象となった各画像データについて、それぞれ、前記累算値系列の前記演算順方向についての幅を求める手段、
として更に機能させるとともに、
前記照合処理を行う手段は、前記処理対象となった画像データの累算値系列の幅と、前記照合の対象となった画像データの累算値系列の幅と、に基づき、前記相似変換パラメータ中の前記一次変換係数の推定存在範囲を限定し、前記推定相似変換パラメータ群から前記平行移動量の推定存在範囲と前記一次変換の推定存在範囲との交わりのなかで前記尤度の高いパラメータを前記相似変換パラメータとして決定する、
ことを特徴とする請求項３記載のプログラム。