(57)【特許請求の範囲】
【請求項１】
基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付ける方法であって、
（ａ）基準画像を予め複数の小ブロックに分割し、
（ｂ）各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、さらに小ブロック内に含まれる対応付けに有益な画素の数に基づき各小ブロックの探索優先度を決定し、
（ｃ）小ブロックに分割された基準画像及び各小ブロックの探索範囲および探索優先度を記憶し、
（ｄ）小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定し、
（ｅ）ステップ（ｄ）の実行中において、既に決定された小ブロックの入力画像内における対応位置に基づき、入力画像における対応位置が未だ決定されていない小ブロックの探索優先度及び探索範囲を修正するステップを具備し、
ステップ（ａ）において基準画像はそれぞれが複数の小ブロックを含む複数の中ブロックに分割され、
ステップ（ｅ）は、
（ｉ）対応位置が決定済の小ブロックを所定個以上有する中ブロックについて、該中ブロック内の小ブロックの決定済の対応位置から中ブロック全体の変形パラメータの値を算出し、
（ii）算出された変形パラメータの値から、該中ブロック内で対応位置が未決定の小ブロックの探索範囲を決定し、
（iii)  対応位置が決定済の小ブロックを前記所定個以上有しない中ブロックの変形パラメータの値を、サブステップ（ｉ）で算出された変形パラメータの値から推定し、
（iv）推定された変形パラメータの値から、前記対応位置が決定済の小ブロックを所定個以上有しない中ブロック内の小ブロックの探索範囲を決定するサブステップを含む方法。
【請求項２】
ステップ（ｄ）において、対応位置が決定済の小ブロックに基づき基準画像に対する入力画像の傾き程度を推定し、推定された傾き程度の値から小ブロックに分割された基準画像に対する画像の入力画像内における位置の決定が補正される請求項１記載の方法。
【請求項３】
基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付ける方法であって、
（ａ）基準画像を予め複数の小ブロックに分割し、
（ｂ）各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、
（ｃ）小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶し、
（ｄ）小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定するステップを具備し、
ステップ（ｄ）は、
（ｉ）基準画像のエッジを抽出して基準エッジ画像を予め生成し、
（ii）入力画像のエッジを抽出して入力エッジ画像を生成し、
（iii)  入力エッジ画像の推定対応位置に基準エッジ画像を重ねたときの入力エッジ画像のエッジを構成する各画素と基準エッジ画像のエッジを構成する各画素との間の距離の頻度を計算し、
（iv）計算された頻度が所定の閾値を超えているものを入力画像と基準画像の距離と決することによって、対応位置を決定するサブステップを含み、
サブステップ（ｉ）は、
基準画像の上、下、左及び右のエッジを抽出して基準上エッジ画像、基準下エッジ画像、基準左エッジ画像及び基準右エッジ画像をそれぞれ生成するサブステップを含み、
サブステップ（ii）は、
入力画像の上、下、左及び右のエッジを抽出して入力上エッジ画像、入力下エッジ画像、入力左エッジ画像及び入力右エッジ画像をそれぞれ生成するサブステップを含み、
サブステップ（iii)は、入力上エッジ画像、入力下エッジ画像、入力左エッジ画像及び入力右エッジ画像に基準上エッジ画像、基準下エッジ画像、基準左エッジ画像及び基準右エッジ画像をそれぞれ重ねたときの、両者を構成する各画素の上下方向、上下方向、左右方向及び左右方向における距離の頻度をそれぞれ計算するサブステップを含み、
サブステップ（iv）は、
上エッジ及び下エッジに関して計算された距離の頻度が所定の閾値を超え、かつ、両者が所定の誤差範囲内で一致するものを入力画像と基準画像の上下方向における距離と決定し、
左エッジ及び右エッジに関して計算された距離の頻度が所定の閾値を超え、かつ、両者が所定の誤差範囲内で一致するものを入力画像と基準画像の左右方向における距離と決定するサブステップを含む方法。
【請求項４】
ステップ（ｄ）は、
（ｖ）基準画像内で上下方向及び左右方向の直線を検出し、
（vi）サブステップ（iii)の前に、基準エッジ画像内で、サブステップ（ｖ）で検出された直線に対応するエッジを該直線の切片で置き換えるサブステップをさらに含む請求項３記載の方法。
【請求項５】
基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付けるための装置であって、
複数の小ブロックに分割された基準画像の各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、さらに小ブロック内に含まれる対応付けに有益な画素の数に基づき各小ブロックの探索優先度を決定する探索範囲および優先度決定手段と、
小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、
小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段と、
探索手段の探索の実行中において、既に決定された小ブロックの入力画像内における対応位置に基づき、入力画像における対応位置が未だ決定されていない小ブロックの探索優先度及び探索範囲を修正する修正手段とを具備し、
基準画像はそれぞれが複数の小ブロックを含む複数の中ブロックに分割され、
修正手段は、
対応位置が決定済の小ブロックを所定個以上有する中ブロックについて、該中ブロック内の小ブロックの決定済の対応位置から中ブロック全体の変形パラメータの値を算出する手段と、
算出された変形パラメータの値から、該中ブロック内で対応位置が未決定の小ブロックの探索範囲を決定する手段と、
対応位置が決定済の小ブロックを前記所定個以上有しない中ブロックの変形パラメータの値を、算出された変形パラメータの値から推定する手段と、
推定された変形パラメータの値から、前記対応位置が未決定の小ブロックを所定個以上有しない中ブロック内の小ブロックの探索範囲を決定する手段とを含む装置。
【請求項６】
探索手段は、対応位置が決定済の小ブロックに基づき基準画像に対応する入力画像の傾き程度を推定し、推定された傾き程度の値から小ブロックに分割された基準画像に対する画像の入力画像における位置の決定を補正する請求項５記載の装置。
【請求項７】
基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付けるための装置であって、
複数の小ブロックに分割された基準画像の各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定する探索範囲決定手段と、
小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、
小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段とを具備し、
探索手段は、
基準画像のエッジを抽出して基準エッジ画像を予め生成する基準エッジ画像生成手段と、
入力画像のエッジを抽出して入力エッジ画像を生成する入力エッジ画像生成手段と、
入力エッジ画像の推定対応位置に基準エッジ画像を重ねたときの入力エッジ画像のエッジを構成する各画素と基準エッジ画像のエッジを構成する各画素との間の距離の頻度を計算する頻度計算手段と、
計算された頻度が所定の閾値を超えているものを入力画像と基準画像の距離と決定することによって、対応位置を決定する距離決定手段とを含み
基準エッジ画像生成手段は、
基準画像の上、下、左及び右のエッジを抽出して基準上エッジ画像、基準下エッジ画像、基準左エッジ画像及び基準右エッジ画像をそれぞれ生成する手段を含み、
入力エッジ画像生成手段は、
入力画像の上、下、左及び右のエッジを抽出して入力上エッジ画像、入力下エッジ画像、入力左エッジ画像及び入力右エッジ画像をそれぞれ生成する手段を含み、
頻度計算手段は、入力上エッジ画像、入力下エッジ画像、入力左エッジ画像及び入力右エッジ画像に基準上エッジ画像、基準下エッジ画像、基準左エッジ画像及び基準右エッジ画像をそれぞれ重ねたときの、両者を構成する各画素の上下方向、上下方向、左右方向及び左右方向における距離の頻度をそれぞれ計算する手段を含み、
距離決定手段は、
上エッジ及び下エッジに関して計算された距離の頻度が所定の閾値を超え、かつ、両者が所定の誤差範囲内で一致するものを入力画像と基準画像の上下方向における距離と決定する手段と、
左エッジ及び右エッジに関して計算された距離の頻度が所定の閾値を超え、かつ、両者が所定の誤差範囲内で一致するものを入力画像と基準画像の左右方向における距離と決定する手段とを含む装置。
【請求項８】
探索手段は、
基準画像内で上下方向及び左右方向の直線を検出する手段と、
頻度計算手段による頻度の計算の前に、基準エッジ画像内で、検出された直線に対応するエッジを該直線の切片で置き換える手段とをさらに含む請求項７記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、基準画像に対して追加または削除された可能性があり位置ずれ、伸縮及び傾きの変形を受けた可能性がある入力画像を基準画像に対応付ける方法、これを利用した文字認識方法、相違個所検出方法、印刷方法、これらの方法を実現するための装置、及びこれらの方法を実現するプログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
手書き文字を読み取るＯＣＲ装置（光学的文字読取装置）においては、あらかじめ帳票上の読み取り領域の座標を定規等で計っておき、これを帳票定義体として記憶することが行われている。帳票が入力された時には、この定義体を参照し、同じ位置を切り出して文字認識を行う。この方式では帳票の印刷ずれがごく微量であり、かつイメージスキャナー入力時のずれや傾きが０かあるいは計測できることを必要とする。そうでないと、正しい場所の文字を読み取ることはできない。そのため１）用紙の印刷精度や裁断精度を厳密に規定することで印刷ずれや裁断誤差の影響を無くし、２）入力するスキャナーの搬送精度を高めることで用紙の傾きや伸縮、蛇行を無くす、ということが行われる。これらは帳票の制限やシステムのコストアップなどのさまざまな制限を生む。
【０００３】
近年これらの制限の緩和が強く要求されており、この問題を解決する方法として、用紙にあらかじめ印刷されたマークや枠線などのプレ印刷をもとに、位置決めを行う方法が用いられている。
マークをあらかじめ印刷する方法では、たとえばＯＣＲでは帳票の隅に＋やＬ字型などのマークを印刷しておき、入力された画像からマークを検出することで対応づけるものである。しかしこの方法では既存の帳票がそのまま使用できず、マークの仕様に合わせて新規に帳票を作成する必要があるため、コストが上昇し、また帳票修正のために手間ひまがかかるという問題がある。また、マークの近傍は精度が高いが、マークから離れた領域は位置精度が低くなる。これは入力画像の変形パラメータ（位置ずれ、回転、伸縮）が一定ではなく、画像上で変化するためである。そのため精度を上げるためにはマークを沢山設ける必要があるが、これはレイアウト上許されないことが多い。
【０００４】
この問題に鑑み、近年、画像上に本来存在する要素、たとえば帳票上に印刷されている表の線分を対応づける方法が考案されている（例えば特開平７−２４９０９９号、特開平７−２８２１９３号、及び特開平８−７７２９４号参照）。帳票上の線分１本１本を対応づけることは、前述の方式でマークの数を増やしたと同一の効果があるため、画像の変形に対して有利である。
【０００５】
しかしながら、これらの方法では原理的に線分で構成される帳票しか処理できないという欠点がある。たとえばアンケート用紙では文書中に括弧でくくって文字記入される箇所や、“年月日”の印刷文字の前に日付を記入するもの等があるが、このような場所ではこの方法は使用できない。一般の帳票・伝票類には○の中に文字記入させるものなど線分を用いないレイアウトが沢山存在するため、線分に基づき対応付けする方式では対応できない。
【０００６】
【発明が解決しようとする課題】
上記に鑑みれば、線分に限らない任意の図形要素又は文字からなる画像について、基準画像に追加／削除が行なわれ、位置ずれ、伸縮及び傾斜の変形を受けた入力画像を基準画像の各部分に対応付けることができれば、線分を含まないかまたは線分を多く含まない書式用紙に記入された文字を、位置ずれ、伸縮及び傾きの変形を受けていても読み取ることができる。
【０００７】
したがって本発明の目的は、線分に限定されない任意の図形要素及び／又は文字からなる画像について、基準画像に対して追加または削除された可能性があり全体が位置ずれ、伸縮及び傾きの変形を受けた可能性がある入力画像を基準画像に対応付ける方法及びこの方法を実現するための装置を提供することにある。
本発明の他の目的は、上記の対応付け方法を利用した文字認識方法、相違個所検出方法、印刷方法及びこれらを実現するための装置を提供することにある。
【０００８】
本発明のさらに他の目的は、上記の方法を実現するプログラムを格納した記憶媒体を提供することにある。
【０００９】
【課題を解決するための手段】
本発明によれば、基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付ける方法であって、基準画像を予め複数の小ブロックに分割し、各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶し、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定するステップを具備する方法が提供される。
【００１０】
前記の探索するステップは、基準画像のエッジを抽出して基準エッジ画像を予め生成し、入力画像のエッジを抽出して入力エッジ画像を生成し、入力エッジ画像の推定対応位置に基準エッジ画像を重ねたときの入力エッジ画像のエッジを構成する各画素と基準エッジ画像のエッジを構成する各画素との間の距離の頻度を計算し、計算された頻度が所定の閾値を超えているものを入力画像と基準画像の距離と決定することによって、対応位置を決定するサブステップを含むことが好適である。
【００１１】
本発明によれば、文字が記入された書式用紙から得られた入力画像から記入された文字を認識する方法であって、文字が記入されていない書式用紙から得られた基準画像を予め複数の小ブロックに分割し、各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶し、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定し、予め記憶されている記入領域に対応する入力画像における文字の記入領域を、決定された対応位置に従って決定し、決定された入力画像における文字の記入領域内の画像について文字認識を行なうステップを具備する方法もまた提供される。
【００１２】
本発明によれば、文字が記入された書式用紙から得られた入力画像から記入された文字を認識する方法であって、文字が記入されていない書式用紙から得られた基準画像を予め複数の小ブロックに分割し、各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定し、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶し、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定し、決定された各小ブロックの対応位置に従って入力画像から基準画像に対応するものを除去し、基準画像が除去された入力画像について文字認識を行なうステップを具備する方法もまた提供される。
【００１３】
本発明によれば、第１の画像と第２の画像の間の相違個所を検出する方法であって、第１の画像を予め複数の小ブロックに分割し、各小ブロックについて、第２の画像において対応部分を探索すべき範囲を決定し、小ブロックに分割された第１の画像及び各小ブロックの探索範囲を記憶し、小ブロックに分割された第１の画像に対応する画像を第２の画像について探索範囲内で探索して、小ブロックに分割された第１の画像に対応する画像の第２の画像内における位置を決定し、決定された各小ブロックの対応位置に従って第２の画像から第１の画像に対応するものを除去し、第１の画像が除去された第２の画像に残る画素をグループ化し、グループ化された画素の数が所定値以上の画素グループを相違個所と決定するステップを具備する方法もまた提供される。
【００１４】
本発明によれば書式用紙に文字を印刷する方法であって、基準となる書式用紙から得られた基準画像を予め複数の小ブロックに分割し、各小ブロックについて、文字を印刷すべき書式用紙から得られた入力画像において対応部分を探索すべき範囲を決定し、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶し、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定し、予め記憶されている印刷位置に対応する入力画像における印刷位置を、決定された対応位置に従って決定し、決定された印刷位置に従って、文字を印刷すべき書式用紙に文字を印刷するステップを具備する方法もまた提供される。
【００１５】
本発明によれば、基準画像の各部分に対応する入力画像の部分の入力画像における位置を決定することによって、入力画像と基準画像を対応付けるための装置であって、複数の小ブロックに分割された基準画像の各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定する探索範囲決定手段と、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段とを具備する装置もまた提供される。
【００１６】
前記の探索手段は、基準画像のエッジを抽出して基準エッジ画像を予め生成する基準エッジ画像生成手段と、入力画像のエッジを抽出して入力エッジ画像を生成する入力エッジ画像生成手段と、入力エッジ画像の推定対応位置に基準エッジ画像を重ねたときの入力エッジ画像のエッジを構成する各画素と基準エッジ画像のエッジを構成する各画素との間の距離の頻度を計算する頻度計算手段と、計算された頻度が所定の閾値を超えているものを入力画像と基準画像の距離と決定することによって、対応位置を決定する距離決定手段とを含むことが好適である。
【００１７】
本発明によれば、文字が記入された書式用紙から得られた入力画像から記入された文字を認識するための装置であって、文字が記入されていない書式用紙から得られた基準画像を予め複数の小ブロックに分割する分割手段と、各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定する探索範囲決定手段と、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段と、予め記憶されている記入領域に対応する入力画像における文字の記入領域を、探索手段が決定した対応位置に従って決定する記入領域決定手段と、記入領域決定手段が決定した、入力画像における文字の記入領域内の画像について文字認識を行なう手段とを具備する装置もまた提供される。
【００１８】
本発明によれば、文字が記入された書式用紙から得られた入力画像から記入された文字を認識するための装置であって、文字が記入されていない書式用紙から得られた基準画像を予め複数の小ブロックに分割する分割手段と、各小ブロックについて、入力画像において対応部分を探索すべき範囲を決定する探索範囲決定手段と、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段と、決定された各小ブロックの対応位置に従って入力画像から基準画像に対応するものを除去する手段と、基準画像が除去された入力画像について文字認識を行なう手段とを具備する装置もまた提供される。
【００１９】
本発明によれば、第１の画像と第２の画像の間の相違個所を検出するための装置であって、複数の小ブロックに分割された第１の画像の各小ブロックについて、第２の画像において対応部分を探索すべき範囲を予め決定する探索範囲決定手段と、小ブロックに分割された第１の画像及び各小ブロックの探索範囲を記憶する記憶手段と、小ブロックに分割された第１の画像に対応する画像を第２の画像について探索範囲内で探索して、小ブロックに分割された第１の画像に対応する画像の第２の画像内における位置を決定する探索手段と、決定された各小ブロックの対応位置に従って第２の画像から第１の画像に対応するものを除去する手段と、第１の画像が除去された第２の画像に残る画素をグループ化する手段と、グループ化された画素の数が所定値以上の画素グループを相違個所と決定する手段とを具備する装置もまた提供される。
本発明によれば、書式用紙に文字を印刷するための装置であって、基準となる書式用紙から得られた基準画像を予め複数の小ブロックに分割する分割手段と、各小ブロックについて、文字を印刷すべき書式用紙から得られた入力画像において対応部分を探索すべき範囲を決定する探索範囲決定手段と、小ブロックに分割された基準画像及び各小ブロックの探索範囲を記憶する記憶手段と、小ブロックに分割された基準画像に対応する画像を入力画像について探索範囲内で探索して、小ブロックに分割された基準画像に対応する画像の入力画像内における位置を決定する探索手段と、予め記憶されている印刷位置に対応する入力画像における印刷位置を、探索手段が決定した対応位置に従って決定する印刷位置決定手段と、印刷位置決定手段が決定した印刷位置に従って、文字を印刷すべき書式用紙に文字を印刷する手段とを具備する装置もまた提供される。
【００２０】
本発明によれば、コンピュータに接続されたときに上記の方法を実現するプログラムを格納したコンピュータによる読み出し可能な記憶媒体もまた提供される。
【００２１】
【発明の実施の形態】
本発明に係る基準画像と入力画像の対応づけにおいては、線分や表などの特定の要素に依存しないで対応付けを可能にするために、基準画像として、例えば未記入の帳票又はアンケート用紙等の書式用紙の画像をあらかじめ入力しておき、これを入力された画像と比較して合わせ込む方法を取る。具体的には、基準画像または基準画像から明るさの変化する場所だけを取り出した基準エッジ画像を小領域のブロックに分割して保存しておく。対応づけ処理のために画像が入力されると、保存したブロックのうち当てはめやすいものから、入力画像またはそれから生成した入力エッジ画像の中で基準画像または基準エッジ画像のブロックと一致する箇所を求める。もし一致する場所が見つかった場合、他のブロックに対応する場所を探す範囲を見つかった場所を元に絞り込む。これを繰り返すことで画像の対応づけを行う。
【００２２】
図１は本発明の実施例に係る装置のハードウェアの構成を示す。図１において、パーソナルコンピュータ１０には帳票またはアンケート用紙等の書式用紙の読み取り装置１１が接続される。パーソナルコンピュータ１０はＣＤ−ＲＯＭドライブ１２を備え、また、回線モデムを内蔵している。本発明の実施例に係る方法を実現するためのプログラムは、パーソナルコンピュータに備え付けのハードディスクに格納しても良いし、ＣＤ−ＲＯＭ  １３に記憶させて必要に応じてＣＤ−ＲＯＭ  １３をＣＤ−ＲＯＭドライブ１２へ挿入することにより、ＣＤ−ＲＯＭ  １３に格納されたプログラムをパーソナルコンピュータ１０内のメモリへ読み込ませても良いし、回線モデムを介して回線に接続されたデータベースから必要に応じてパーソナルコンピュータ１０内のメモリへ読み込ませても良い。それによって、本発明の方法及び装置が実現される。
【００２３】
図２は読み取り装置１１の内部構造の詳細を示す。図２において、ホッパ１４に積まれた帳票またはアンケート用紙等はピックローラ１５によって上から１枚ずつピックされ、搬送ローラ１６で図２中の一点鎖線に沿って搬送される。ホッパ１４は用紙の積み上げ高さに応じて上下する。搬送中の用紙に光源１７から光が照射され、その反射光が反射鏡１８に反射され、レンズ１９を経て一次元のＣＣＤ素子２０へ入射する。これによって搬送中の帳票又はアンケート用紙の画像が電気信号の形で得られる。ＣＣＤ素子２０で得られた画像信号は画像インターフェース（図示せず）を介してパーソナルコンピュータ１０へ入力される。印字ユニット２１はパーソナルコンピュータ１０からの指令により、搬送中の用紙に所望の文字を印字する。画像が読み取られ、印字された帳票またはアンケート用紙はスタッカ２２または２３に送られ、そこに積み上げられる。パーソナルコンピュータ１０からの指示により、文字認識結果に異常があるものは正常なものと分けてスタッカ２２または２３の一方に積み上げられる。
【００２４】
図３は図１のパーソナルコンピュータ１０及びＣＤ−ＲＯＭ  １３に格納されたソフトウェアプログラムの協働により実現される、本発明の一実施例に係る画像対応付け装置の機能ブロック図である。図３において、エッジ生成部３０は、図４にその一部を例示するような２値画像からなる基準画像から、図５に示す上下エッジ画像及び図６に示す左右エッジ画像を生成する。エッジ画像、例えば左エッジ画像は次式によって生成する。
【００２５】
（（Ａ＞＞１）＊Ａ）ＡＮＤ  Ａ
式中、Ａは図４８に示すように水平な１ライン上の画素の値を表わし＞＞１は１ラインの画素値Ａを右方向へ１画素分シフトする演算を表わし、＊は排他的論理和演算子、ＡＮＤは論理積演算子である。図４８からわかるように、上記の演算を各ラインについて実施することにより、左エッジ画像が得られる。右エッジ画像及び上下エッジ画像についても同様である。エッジ画像ではなく２値画像そのものを用いる場合にはこの処理は不要である。また、後に詳述するように、図５及び図６の上下エッジ画像及び左右エッジ画像の代わりに、図７〜図１０に示す上エッジ画像、下エッジ画像、左エッジ画像及び右エッジ画像を別々に用いる場合もある。
【００２６】
図３に戻って、ブロック分割部３２は、基準画像（２値画像またはエッジ画像）を例えば１辺が２５０画素程度の大きさの矩形の中ブロックに分割し、さらに、各中ブロックを、図１１〜図１３に示すように、例えば３２画素×３２画素の正方形の小ブロックに分割する。なお、４００ｄｐｉ  （ドット／インチ）の場合、３２画素の長さは約２ｍｍである。
【００２７】
図３の探索範囲／優先度決定部３４は、小ブロックに分割された基準画像（２値画像またはエッジ画像）のそれぞれについて、入力画像（２値画像またはエッジ画像）中で探索すべき範囲と探索の優先度の初期値を決定する。探索範囲の初期値は基準画像のサイズ、入力画像のサイズ、入力画像の最大伸縮率と最大スキュー角度から決定される。例えば、図１４（ａ）に示す基準画像３６内の或る小ブロック３８内の点（ｘ，ｙ）の探索範囲については、まず許容する伸縮率の最大まで基準画像３６を縮小し、これを図１４（ｂ）〜（ｅ）に示すように入力画像４０の４隅に置いたときの座標（ｘ，ｙ）に対応する入力側の座標（ｘ１，ｙ１），（ｘ２，ｙ２），（ｘ３，ｙ３），（ｘ４，ｙ４）を求める。次にこれを入力画像の隅を中心として、最大スキュー角度分回転しおのおのの座標の移動範囲を求める。同様の処理を基準画像を伸縮率の最大まで拡大したものについても行う。小ブロック３８内の各点について得られた座標範囲を囲む外接長方形４２（図１４（ｆ））は最大伸縮率と最大スキュー角度内で小ブロック３８内の各点が取りうる範囲を示すので、これを初期探索範囲とする。
【００２８】
各小ブロックの探索優先度は、小ブロック内の黒画素数及び探索範囲の広さから計算された得点により決定する。小ブロック（ｘ０，ｙ０）の得点Ｓｃｏｒｅ（ｘ０，ｙ０）は例えば次式により計算される。
Ｓｃｏｒｅ  （ｘ０，  ｙ０）＝  Ｋ×（ＰＨ  （ｘ０，  ｙ０）＋  ＰＶ  （ｘ０，  ｙ０））  ＋  Ｌ×Σ（ＰＨ  （ｘ，  ｙ）＋  ＰＶ  
（ｘ，  ｙ））                                                          …（１）
ｉｆ（ＰＨ  （ｘ０，  ｙ０）＞＝  Ｐ Ｔｈｒｅｓｈｏｌｄ  ＆＆  ＰＶ  （ｘ０，  ｙ０）＞＝  Ｐ Ｔｈｒｅｓｈｏｌｄ）…（２）
Ｓｃｏｒｅ  （ｘ０，  ｙ０）＋＝Ｂｏｎｕｓ  ；
ｉｆ（ＳｅａｒｃｈＳｉｚｅ  （ｘ０，  ｙ０）＜＝  Ｓ Ｔｈｒｅｓｈｏｌｄ）                        …（３）
Ｓｃｏｒｅ  （ｘ０，  ｙ０）＝Ｓｃｏｒｅ  （ｘ０，  ｙ０）×Ｍ  ×（Ｓ Ｔｈｒｅｓｈｏｌｄ  −ＳｅａｒｃｈＳｉｚｅ  （ｘ０，  ｙ０））
上式中、＆＆はその左右の式の結果が共に真であるときのみ結果を真とする論理演算子、＋＝はその左辺に右辺を加算した後、左辺に代入する演算子である。ＰＨ  （ｘ０，ｙ０）はエッジ画像を用いる場合の小ブロック（ｘ０，ｙ０）における上下エッジ黒画素数、ＰＶ  （ｘ０，ｙ０）は左右エッジ黒画素数である。Ｋは（ｘ０，ｙ０）のブロックに対する重みづけ係数、右側のＬ×Σ（ＰＨ  （ｘ，ｙ）＋ＰＶ  （ｘ，ｙ））は（ｘ０，ｙ０）の周囲ブロックのエッジ黒画素数の総和に重みづけ係数Ｌを掛けたものである。エッジの黒画素数が大きいほど輪郭線が長く入力側に対応づけ易いため、（１）式においてエッジ画素数に比例して得点を付けている。また得点の高いブロックが集まっている箇所の方が対応付けが容易であるので、周囲のブロックのエッジ黒画素数に係数をかけて足し合わせている。また、もし左右エッジと上下エッジの両方の黒画素数がある程度以上ならＸ方向とＹ方向の両方の位置決めが容易になる。そのため（２）式によって既定値Ｐ Ｔｈｒｅｓｈｏｌｄより大きければ得点を上げる。さらに、探索範囲が小さいほど誤りにくいため、（３）式により、もし探索範囲ＳｅａｒｃｈＳｉｚｅがある値以下なら、得点を上乗せしている。ここで、探索範囲が小さいほど得点を上げるために、Ｍ×（Ｓ Ｔｈｒｅｓｈｏｌｄ−ＳｅａｒｃｈＳｉｚｅ（ｘ０，ｙ０））を掛けている（Ｍは係数）。なお、エッジ画像を生成する代わりに２値画像そのものを用いる場合、（１）式中のＰＨ  （ｘ０，ｙ０）＋ＰＶ  （ｘ０，ｙ０）及びＰＨ  （ｘ，ｙ）＋ＰＶ  （ｘ，ｙ）は２値画像における黒画素数Ｐ（ｘ０，ｙ０）及びＰ（ｘ，ｙ）に置き換えられ、（２）式による加点は行なわれない。
【００２９】
図３に戻って、探索範囲／優先度決定部３４が決定した各小ブロックの探索範囲及び探索優先順位はブロックに分割された基準画像とともに記憶部３７に格納される。ここまでの処理は、読み取り装置１１に未記入の帳票またはアンケート用紙がセットされ、その画像が基準画像としてパーソナルコンピュータ１０へ読み込まれるときにのみ１回だけ実行される。
【００３０】
エッジ生成部４４は、読み取り装置１１に記入済の帳票またはアンケート用紙がセットされて読み込まれた入力画像についてエッジ生成部３０と同じ処理を行なって入力エッジ画像を生成する。２値画像そのものを使って対応付け処理を行なう場合にはこの処理は不要である。
ブロック選択部４６は記憶部３７に格納されている、一致判定が終っていない小ブロックの中で最も優先度の高い小ブロックとその探索範囲のデータを取り出す。一致判定部４８はブロック選択部４６が取り出した小ブロックについて、それと一致する部分を入力画像内で探索する。
【００３１】
一致判定において、例えば図１５に示すように２値画像の小ブロック３８を入力画像４０の全領域にわたって動かして画素値の一致するものの数が閾値以上で最も高い位置を探すことで一致判定を行なっても良いが、この方法では計算量が膨大になる。図１６の破線５２で示すように探索範囲を絞ったとしても、探索範囲の面積に比例した計算量が必要である。しかし、小ブロックの大きさが充分に小さく、かつ、その探索範囲が充分に絞り込めていれば図１６中に矢印５４で示すように、上下方向と左右方向をそれぞれ独立に探索することにより、計算量を著しく削減することができる。さらに、２値画像を使う代わりに、上下方向の探索には図５の上下エッジを使い、左右方向の探索には図６の左右エッジ画像を使えば計算量をさらに削減できるとともに、黒ベタ部分の色ヌケの影響を低減することができる。
【００３２】
さらに、本発明では、エッジ画像を実際に上下及び左右に動かして一致判定を行なうのでなく、図１７及び図１８に示すように上下エッジ画像５６及び左右エッジ画像５８を入力上下エッジ画像及び入力左右エッジ画像の探索範囲６０，６２の中央（推定位置）に重ね、両者のエッジの上下方向及び左右方向の距離ｄｘまたはｄｙを算出し（図１９）、図２０に示す距離のヒストグラムにおいて出現頻度が所定の閾値を超えているものを一致点の推定位置からのずれｄｘ，ｄｙとすることにより、対応位置を決定する。なお、図２０のヒストグラムでは、左右の２点を含む３点で移動平均をとることにより、エッジのがたつきによる分布のばらつきを吸収することが望ましい。
【００３３】
上述の上下エッジ画像及び左右エッジ画像を用いる手法では、印刷の濃淡又は画像の明るさの違いにより線の太さに違いがある場合に閾値を超えるピークを有するヒストグラムを得ることが困難である。そこで、他の手法として、図７〜図１０に示した、上、下、左及び右エッジ画像についてそれぞれ別々にｄｘまたはｄｙの分布を図２１に示すように求め、上エッジと下エッジの間で所定の誤差範囲内で一致するピークの位置の平均を上下のずれ量とし、左エッジと右エッジの間で所定の誤差範囲内で一致するピークの位置の平均を左右のずれ量とする。図２２はこの手法により推定位置からのずれ量を算出する部分の機能ブロック図である。エッジ生成部６４は基準画像から上、下、左及び右のエッジ画像を生成し、エッジ生成部６６は入力画像から上、下、左及び右のエッジ画像を生成する。左エッジヒストグラム生成部６８は、図２１（ａ）に示す、左エッジ画像についての基準画像と入力画像のｘ方向における距離ｄｘのヒストグラムを生成し、右エッジヒストグラム生成部７０は、図２１（ｂ）に示す、右エッジ画像についての基準画像と入力画像のｘ方向の距離ｄｘのヒストグラムを生成する。同様に、上エッジヒストグラム生成部７２及び下エッジヒストグラム生成部７４は、上エッジ画像及び下エッジ画像についての距離ｄｙのヒストグラムをそれぞれ生成する。ｄｘ決定部７６は左エッジのヒストグラムと右エッジのヒストグラムの間で所定の誤差範囲内で一致しかつ閾値を超えているピークの位置の平均を左右のずれ量ｄｘと決定し（図２１参照）、ｄｙ決定部７８は同様に上エッジのヒストグラムと下エッジのヒストグラムの間で所定の誤差範囲内で一致しかつ閾値を超えているピークの位置の平均を上下のずれ量とする。
【００３４】
図３に戻って、一致判定部４８が処理した小ブロックの推定位置からのずれ量ｄｘ，ｄｙが決定されたら、その小ブロックについては対応付けが成功したものとして、対応位置決定部５０は推定対応位置及びずれ量ｄｘ，ｄｙから対応位置を決定し記憶部３７に格納する。探索範囲／優先度更新部８０は、決定された小ブロックの対応位置に基づいて対応付けが未決定の小ブロックの探索範囲及び優先度を更新して記憶部３７に格納する。探索範囲／優先度更新部８０の動作の詳細については後述する。
【００３５】
この様な、ブロック４６，４８，５０及び８０の動作を繰り返すことによって、全小ブロックの対応付けを行なう。
図２３は読み取り装置１１のホッパ１４に未記入の帳票またはアンケート用紙がセットされて、基準画像が読み込まれた際の画像対応付け装置の動作のフローチャートである。図２３において、基準画像の２値画像が入力されたら、ステップ１０００において、エッジ生成部３０が入力された２値画像からエッジ画像を生成する。前述したように、２値画像を対応位置決定に用いる場合にはこの処理は省略される。次にステップ１００２において、ブロック分割部３２が中ブロック及び小ブロックの分割を行ない、ステップ１００４において、探索範囲／優先度決定部３４が各小ブロックの探索範囲及び優先度の初期値を決定し、ステップ１００６において、ブロックに分割された基準画像（２値画像またはエッジ画像）が探索範囲及び優先度とともに記憶部３７に格納される。
【００３６】
図２４は読み取り装置１１のホッパ１４に記入済の帳票またはアンケート用紙が積まれ、入力画像が読み込まれたときの画像対応付け装置の動作のフローチャートである。図２４において、入力画像の２値画像が入力されたら、ステップ１１００において、エッジ生成部４４が入力された２値画像からエッジ画像を生成する。前述したように、２値画像を対応位置決定に用いる場合にはこの処理は省略される。次に、ステップ１１０２においてすべての小ブロックについて一致判定が終了したか否かが判定され、終了していなければステップ１１０４においてブロック選択部４６が一致判定が終っていない小ブロックのうち最も優先度が高い小ブロックとその探索範囲のデータを取り出す。ステップ１１０６において一致判定部４８が探索範囲内で基準画像の小ブロックと入力画像の一致判定を行ない、一致判定が成功したらステップ１１１０において対応位置決定部５０がずれ量ｄｘ，ｄｙから対応位置を決定して記憶部３７に格納する。ステップ１１１２において探索範囲／優先度更新部８０が決定された小ブロックの対応位置に基いて対応付けが未決定の小ブロックの探索範囲と優先度を更新して記憶部３７へ格納し、ステップ１１０２の処理へ戻る。
【００３７】
探索範囲／優先度更新部８０における、対応付けが未決定の小ブロックの探索範囲の絞り込みの手法としては次の３つを採用する。
（１）対応位置が決定された小ブロックの近傍の小ブロックについて、決定済の対応位置に基づいてその近傍の小ブロックの探索範囲を決定し、それらを優先的に判定する。
【００３８】
（２）対応位置が決定された３つの小ブロックを頂点とする３角形の内側の小ブロックの探索範囲を頂点の小ブロックの対応位置から直線補間で決定する。
（３）対応位置が決定された複数の小ブロックの対応位置から、中ブロック（前述）の変形パラメータの値を最小２乗法で決定し、決定された変形パラメータの値から逆に未決定の小ブロックの探索範囲を決定する。
【００３９】
上記（１）の手法においては、例えば図２５に示すように、対応位置が決定された小ブロック（ｘ０，ｙ０）の周囲のハッチングが付された８個の小ブロックについては、小ブロック（ｘ０，ｙ０）の対応位置からブロックサイズＷＩＤを用いて小ブロックに変形がないものとして幾何学的に決定される推定位置を中心とする±ｄの範囲を探索範囲とし、そのさらに周囲の２重ハッチングが付された１６個の小ブロックについては、幾何学的に決定される推定位置を中心とする±２ｄの範囲を探索範囲とする。例えば小ブロック（ｘ０，ｙ０）の左上の小ブロックの中心は、（（ｘ０−ＷＩＤ±ｄ），（ｙ０−ＷＩＤ±ｄ））にあるものとする。ただし、ｄは
ｄ＝ｄＭ×ＷＩＤ
で決定され、ｄＭは許容する最大伸縮率と最大スキュー角度を考慮して決める定数である。例えばｄＭを１／８、ＷＩＤを３２画素の長さとすると、ｄは４画素の長さである。
【００４０】
上記（２）の手法においては、図２６において、二重ハッチングで示す３つの小ブロックの対応位置が決定済であるとすると、図２７にハッチングで示す小ブロックの推定対応位置が、頂点の３つの小ブロックの対応位置から、内挿により決定される。この手法をあまり大きい３角形に適用すると誤差が大きくなるので中ブロックサイズ程度までに制限することが望ましい。この場合に、１つの中ブロック内で形成される３角形のみに限定すれば処理が簡単である。この手法は（１）の手法よりも精度が低いので探索範囲は例えば推定対応位置±２ｄ程度にするのが望ましい。
【００４１】
上記（３）の手法においては、図２８に示すように、基準画像３６の１つの中ブロック８２内でハッチングで示す所定個以上の小ブロックについて対応位置が決定済であれば、それらのデータから当該中ブロック全体の上下方向（ｙ方向）及び左右方向（ｘ方向）の伸縮率、傾き、及び位置ずれからなる中ブロックの変形パラメータの値を最小２乗法により決定し、決定された値から逆に当該中ブロック内の対応位置が未決定の小ブロックの推定対応位置を計算する。また、対応位置が決定できた小ブロックを所定個以上含まないために変形パラメータが計算できない中ブロックについては、図２９に示すように、それに隣接し変形パラメータが計算できた中ブロックの値を使用してその中ブロック内の未決定の小ブロックの推定対応位置を決定する。図３０に示すように、隣接する複数の中ブロックで変形パラメータの値が計算されている場合には、例えばそれらの平均をとる。（３）の手法によれば、画像中に大きい空白がある場合でも網羅的に推定対応位置が得られる。
【００４２】
最小２乗法による中ブロックの変形パラメータの計算及びそれからの小ブロックの推定対応位置の逆算の方法を以下に説明する。
基準側の小ブロックの例えば中心の座標がｐｉ  ＝（ｐｘｉ  ，ｐｙｉ  ）であり、これに対応する入力側の座標がｑｉ  ＝（ｑｘｉ  ，ｑｙｉ  ）とする。これらの組がｎ個（ｉ＝１〜ｎ）あるとする。
【００４３】
まず、以下の式を計算する。
Ａ＝Σ  （ｑｘ・ｐｘ）  −（Σｑｘ・Σｐｘ）  ／ｎ
Ｂ＝Σ  （ｐｘ・ｐｘ）  −（Σｐｘ・Σｐｘ）  ／ｎ
Ｃ＝Σ  （ｐｘ・ｐｙ）  −（Σｐｘ・Σｐｙ）  ／ｎ
Ｄ＝Σ  （ｑｘ・ｐｙ）  −（Σｑｘ・Σｐｙ）  ／ｎ
Ｅ＝Σ  （ｐｙ・ｐｙ）  −（Σｐｙ・Σｐｙ）  ／ｎ
Ｆ＝Σ  （ｑｙ・ｐｙ）  −（Σｑｙ・Σｐｙ）  ／ｎ
Ｇ＝Σ  （ｑｙ・ｐｘ）  −（Σｑｙ・Σｐｘ）  ／ｎ
ここでΣ（ｑｘ・ｐｘ）＝ｑｘ１・ｐｘ１＋ｑｘ２・ｐｘ２＋…ｑｘｎ・ｐｘｎ（１〜ｎ点分の総和）となる。他も同様。
【００４４】
上のＡ〜Ｇまでを用いて、以下の値を計算する。ただし、ＤＤ，Ｄ１，Ｄ２のどれかが０なら、以降の計算はできない（点が一直線上に並んでいる等、計算不能な並びである）。
ＤＤ＝Ｂ・Ｅ−Ｃ・Ｃ
Ｄ１＝Ａ・Ｅ−Ｄ・Ｃ
Ｄ２＝Ｂ・Ｆ−Ｃ・Ｇ
これにより以下の値を求める。
【００４５】
ｋｘ＝（Ａ・Ｅ−Ｄ・Ｃ）／ＤＤ：Ｘ方向の伸縮率
ｋｙ＝（Ｂ・Ｆ−Ｃ・Ｇ）／ＤＤ：Ｙ方向の伸縮率
上記ｋｘ，ｋｙをもとに以下の計算を行って傾きθを計算する。
ＤＬ１  ＝ｋｘ・ｋｘ・Ｅ＋ｋｙ・ｋｙ・Ｂ
ＤＬ２  ＝ｋｘ・Ｄ−ｋｙ・Ｇ−（ｋｘ・ｋｘ−ｋｙ・ｋｙ）・Ｃ
θ＝−ＤＬ２  ／ＤＬ１  （ラジアン）
ＤＬ１＝０の場合には傾きは求められない。縮小率が０などの特殊な場合である。
【００４６】
位置ずれ量は、以下のように傾きθを使って求める。
ｄｘ＝（Σｑｘ−ｋｘ・（Σｐｘ−θ・Σｐｙ））／ｎ：Ｘ方向の位置ずれ量
ｄｙ＝（Σｑｙ−ｋｙ・（Σｐｙ＋θ・Σｐｘ））／ｎ：Ｙ方向の位置ずれ量
以上により中ブロックの変形パラメータ（ｋｘ，ｋｙ）（ｄｘ，ｄｙ），θの値が計算される。これらから対応位置が未決定の小ブロックの推定対応位置は次式
ｑｘｉ  ＝ｋｘ  （ｐｘｉｃｏｓθ−ｐｙｉｓｉｎθ）  ＋ｄｘ
ｑｙｉ  ＝ｋｙ  （ｐｘｉｓｉｎθ＋ｐｙｉｃｏｓθ）  ＋ｄｙ
により計算される。なお前述の最小二乗法の計算式はこれらの式から導かれたものである。
【００４７】
（３）の手法における探索範囲は例えば推定対応位置±２ｄとする。
上記（１）〜（３）の手法のうち、（１）の手法が最も精度が高いが探索範囲を絞り込める範囲が狭い、一方、（３）の手法は中ブロック内を網羅的に絞り込むことができるが精度が低い。（２）の手法は（１）と（３）の中間の性質がある。そこで、優先度の初期値の順に対応付けを行ないながら、対応付けに成功するごとにその周辺の小ブロックに（１）の手法をそれが行き詰まるまで繰り返し適用する。全部の小ブロックについて対応付けの試みが終ったら、各中ブロックについて対応付けに成功した小ブロックの例えば中心点のすべてを囲む凸型閉包をつくり、この凸型閉包を３角形で分割して（２）の手法を適用する。このとき対応付けに成功した小ブロックがあればその周辺の小ブロックについて行き詰まるまで（１）の手法を繰り返し適用する。最後に（３）の手法を適用し、対応付けに成功した小ブロックがあれば再度その周辺の小ブロックに行き詰まるまで（１）の手法を繰り返し適用する。
【００４８】
図３に示す本発明に係る画像対応付け装置では、従来のように線分や表などの特定の要素に依存することなく、対応づけが可能である。また基準画像を小ブロックに分割しておき、これを順に入力画像に当てはめていくことで対応づけを行う。このため図３１のように入力画像の歪みに応じてブロックがずれて対応づくため、入力画像の伸縮・傾き・局所的な歪みが吸収できる。
【００４９】
図３２は図３に示した対応付け装置の一変形の機能ブロック図である。図３と同一の構成要素には同一の参照番号を付してその説明を省略する。
図３２において、水平垂直エッジ検出部８４は２値画像から画面の左右方向に平行な直線の画像及び上下方向に平行な直線の画像を検出することによって、水平なエッジ及びそれに垂直なエッジの位置をｙ軸の切片の値及びｘ軸の切片の値として決定する。置換部８６は検出された左右方向の直線に対応する上下エッジのデータ及び上下方向の直線に対応する左右エッジのデータを上記のｙ軸の切片の値及びｘ軸の切片の値で置換してデータ量を削減する。一致判定部８８では、検出された左右方向の直線の上下エッジについてはｙ軸の切片の値を用い、検出された上下方向の直線の左右エッジについてはｘ軸の切片の値を用いるので、処理量が著しく削減される。
【００５０】
図３３〜図３６を参照して上記の過程を詳細に説明する。図３３及び図３４に示すように、基準画像の２値画像を小ブロックの幅で上下方向及び左右方向に短冊状に切ったものを想定する。上下方向に切った短冊については、図３５の左側に示す短冊状の２値画像の黒画素数の上下方向の分布を図３５の右側に示すように計算し、矢印で示す、黒画素数の変化が急峻な場所を上エッジ又は下エッジとする。そして、図３６に示すように、各小ブロック内の上下エッジをｙ軸の切片の値ｙ０，ｙ１，ｙ２で置き換える。左右方向に切った短冊についても同様にしてｘ軸の切片を決定し、左右エッジをｘ軸の切片の値で置き換える。
【００５１】
図３６からわかるように、エッジが多少斜めであってもブロックが小さいのでこの傾きを無視することができる。逆にエッジに多少の凹凸があっても精度良く対応付けすることができる。
図３７は図３の対応付け装置の他の変形の機能ブロック図である。図３と同一の構成要素には同一の参照番号を付してその説明を省略する。
【００５２】
図３８に示すように、基準側と入力側の傾きが異なっている場合に正しい対応付けができない可能性がある。傾き補正部９０は前述の（３）の手法で決定された中ブロックの傾き角θに基づきその中ブロック内の小ブロックについて式
ｄｙ′＝ｄｙ・Ｘ・θ
により（Ｘは図３８参照）一致判定部４８の一致判定におけるずれ量ｄｙを補正することによって、傾きが異なっている場合でも対応付けを可能にする。
【００５３】
図３９はこれまでに説明した画像対応付け方法を利用した文字認識装置の機能ブロック図である。画像対応付け部９２はこれまでに説明した画像対応付け装置に相当する。位置変換部９４は画像対応付け部９２の対応付け結果に基づき、予め設定された基準画像における文字読み取り位置を入力画像における文字読み取り位置に変換する。画像切り出し部９６は位置変換部９４が出力する文字読み取り位置に従って、入力画像から入力文字の領域を切り出す。文字認識部９８は画像切り出し部９６が切り出した入力文字の画像から文字を認識する。
【００５４】
画像対応付け部９２における対応づけにより図４０に示すように基準側の各小ブロックに対して、対応する入力側の座標を得ることができる。例えば小ブロックの大きさが３２×３２画素とし、画像の画素密度が４００ｄｐｉ  であれば基準側の約２ｍｍごとに入力側の座標が求められる。この対応付け結果から基準側の任意の座標について、２ｍｍおきに求めた座標を線形補完して入力側の座標を求めることができる。たとえば図４１のように四隅の座標が（ｘ０，ｙ０），（ｘ１，ｙ１），（ｘ２，ｙ２），（ｘ３，ｙ３）である小ブロック中の（ｘｐ，ｙｐ）なる座標を変換するには、
変換後Ｘ座標  ｘｐ′＝Ｆｘ（ｘ０，  ｙ０）＋（Ｆｘ（ｘ２，  ｙ２）  −Ｆｘ（ｘ０，  ｙ０））  ×  （ｘｐ−ｘ０）  ／  （ｘ２−ｘ０）
変換後Ｙ座標  ｙｐ′＝Ｆｙ（ｘ０，  ｙ０）＋（Ｆｙ（ｘ２，  ｙ２）  −Ｆｙ（ｘ０，  ｙ０））  ×  （ｙｐ−ｙ０）  ／  （ｙ２−ｙ０）
とすればよい。ただし、Ｆｘ（ｘ，ｙ）は基準側の座標（ｘ，ｙ）を入力側の座標に変換したときのｘ座標、Ｆｙ（ｘ，ｙ）はｙ座標である。位置変換部９４は文字を読み取る領域を上式に基いて図４２のように変換し画像切り出し部９６は入力画像から読み取り領域を切り出し、さらに、読取り領域内の画像を１文字分づつ切り出す。これは最も簡単には、図４３に示すように位置決めされた読取り領域に対し、上下に黒画素を投影するようにして黒画素数の分布を算出し、黒画素のない場所（文字と文字とのすきま）を検出する方法で行うことができる。画像が傾いているときは、傾き量に合わせて投影する方向を変えれば、切り出し精度を向上させることができる。
【００５５】
最後に、切り出した１文字づつの画像を先頭から順番に文字認識処理部９８に渡して、文字認識することで、記入された文字の文字コードを得ることができる。文字認識処理部９８における文字認識処理は当業者に周知であるから説明を省略する。
図４４は本発明の文字認識装置の他の例の機能ブロック図である。図３９と同一の構成要素には同一の参照番号を付してその説明を省略する。画像変形部１００は画像対応付け部９２の対応付け結果に基づき、基準画像を図４５に示すように変形する。この場合に各小ブロック間の距離に応じて小ブロック内の画像を伸縮する。小ブロックが小さいので傾斜は考慮する必要はないが中ブロックの傾斜パラメータθにより傾斜の変形を加えても良い。減算部１０２は変形した基準画像を入力画像に重ね、基準側の画素と入力側の画素が等しい場所を白く塗りつぶす。これにより入力画像から文字枠や説明文等の文字認識には不要な部分が消去され、記入された文字だけが残る。この画像を画像切り出し部９６に渡して切り出した後、文字認識部９８で文字認識を行う。
【００５６】
本発明の文字認識装置は、線分やマーク等の特定の要素に依存せずに帳票の位置決めが可能であり、入力帳票に、位置ずれや伸縮・回転があっても文字を読み取ることが可能である。
さらにまた、基準側に存在する印刷を入力側から削除することが可能であるため、読み取りに不要な文字枠などの印刷を削除して読み取ることが可能であり、この際特定の枠の形に依存しない利点を持つ。
【００５７】
図４６は本発明の画像対応付け方法を利用した相違個所検出装置の機能ブロック図である。図４４と同一の構成要素には同一の参照番号を付してその説明を省略する。比較部１０４は画像変形部１００において変形された基準画像を入力画像に重ね合わせて比較し、両者が不一致である部分を検出する。グループ化部１０６は比較部１０４において検出された不一致の画素について互いに接近しているものどうしをグループ化して所定の面積以上の画素グループのみを表示出力する。
【００５８】
グループ化の方法は、たとえば互いに接している画素どうしをまとめて孤立領域とし、孤立領域をラベリングした後、異なるラベル領域で輪郭間の距離がある閾値以下のものをひとつにまとめる処理を行う。求めた領域の面積がある閾値以上ある箇所を、入力側のイメージに重畳して表示することで、相違点の表示を行う。
【００５９】
本発明の相違箇所検出装置は、基準画像と入力画像に位置ずれや伸縮・回転が存在しても、２枚の画像を対応づけて相違箇所を示すことが可能である。
図４７は本発明の画像対応付け方法を利用した印刷装置の機能ブロック図である。図３９と同一の構成要素には同一の参照番号を付す。２０は図２を参照して既に説明した一次元ＣＣＤ素子であり、２１は印字ユニットである。画像対応付け部９２は予め格納されている基準画像と、搬送中の帳票等から一次元ＣＣＤ素子２０で得られる入力画像との間で既に説明した手法により、対応付けを行なう。位置変換部９４は予め格納されている、基準画像における印刷位置を画像対応付け部９２の対応付け結果に基いて入力画像における位置に変換する。印刷画像生成部１０８は与えられた文字コード及び位置変換部９４から与えられる印刷位置に従って印刷画像を生成し、印字ユニット２１へ印字を指令する。これにより搬送中の帳票等への印刷が行なわれる。
【００６０】
本発明の印刷装置は、帳票にマークを印刷する必要がなく、また帳票のプレ印刷に歪みが存在しても、正確に位置決めを行って印刷することが可能である。
本発明の画像対応付けにおいては、以下のことを行うことが望ましいが、いずれも当業者にとっては自明なことであるため、詳細な説明は省略する。
１）エッジ画像を求める際、ノイズを消去するためにゴミ取りやフィルタリングを行う。
【００６１】
２）網掛けや濃淡の抽出によってエッジが不安定となる領域を抽出し、この箇所は対応づけから除外する。
３）線分やマークによる対応づけ方式と本方式を併用し、計算量の削減と精度の向上を得る。
４）対応づけの履歴を記憶しておき、ある時点で対応づけ誤りを検出したとき、以前の状態に後戻りしてやり直す。
【００６２】
５）エッジ画像を求める際、線幅の細い箇所はエッジを求めないようにすることで、濃度が薄い場合に影響が出る箇所を除外する。
６）あらかじめ基準画像から直線を検出し、断線結合処理によりかすれた部分を接続して画像に書き戻すことで、線分のかすれ部分を精度よく対応づける。
【００６３】
【発明の効果】
本発明では基準側と入力側のエッジ画像を求め、それらを重ね合わせたときのエッジ間の距離の頻度を求めることで対応づけを行う。そのため、従来のように線分や表などの特定の要素に依存することなく、対応づけが可能である。また本発明では基準側エッジ画像を小ブロックに分割しておき、これを順に入力側エッジ画像に当てはめていくことで対応づけを行う。このため入力画像の歪みに応じてブロックがずれて対応づくため、入力画像の伸縮・傾き・局所的な歪みが吸収できる。
【００６４】
また、本発明では基準側と入力側のエッジ間の距離の頻度を求める際、上下方向及び左右方向のみについて距離の頻度を求めることにより、大幅な計算量の削減が可能である。
また、画像を入力する際、濃度設定の違いや、対象の個体差からサンプル側画像に対して若干のつぶれや細まりが存在するが、エッジ画像を上下左右の４種類作成し、上下左右のエッジに対して左と右、上と下のエッジを別々に処理することにより、入力時の濃度設定の違いなどで基準画像と入力画像の太さが変わってしまう場合にも正しい対応づけが可能になる。
【００６５】
また、垂直線・水平線をなすエッジに対して、これを切片のパラメータに近似して距離の頻度を求めることにより、水平・垂直をなすエッジ箇所が多少凸凹している場合にも精度良く対応づけられると同時に、入力側の画像を切片の値だけで表すことができるので、計算に要する時間を節約できる。対応付けの精度を向上させると同時に計算量の削減が可能である。
【００６６】
また、対応付けの計算の際に、基準側と入力した画像との傾きが異なっている場合、正しい対応が取れなくなる可能性があるが、本発明では対応付けする際に、今までの対応結果から傾き推定値を求めて、距離の頻度の計算を補正することにより、精度よく対応づけすることが可能である。
また、本発明では対応づいた基準側ブロックをまとめた中ブロックを構成し、この中ブロックの入力側イメージとの位置ずれ・伸縮・傾きのパラメータを計算し、これを元にまだ対応づいていない箇所の対応位置を推定する。これにより、たとえば画像中に大きい空白があるときなどにも対応づけを行うことが可能になる。
【００６７】
また、本発明により構成した文字認識装置は、線分やマーク等の特定の要素に依存せずに帳票の位置決めが可能であり、入力帳票に、位置ずれや伸縮・回転があっても文字を読み取ることが可能である。
さらにまた、基準側に存在する印刷を入力側から削除することが可能であるため、読み取りに不要な文字枠などの印刷を削除して読み取ることが可能であり、この際特定の枠の形に依存しない利点を持つ。
【００６８】
また、本発明により構成した相違箇所検出装置は、基準側と入力側に位置ずれや伸縮・回転が存在しても、２枚の画像を対応づけて相違箇所を示すことが可能である。
また、本発明により構成した印刷装置は、帳票にマークを印刷する必要がなく、また帳票のプレ印刷に歪みが存在しても、正確に位置決めを行って印刷することが可能である。
【００６９】
以上説明したように、本発明によればレイアウトに依存しない画像の対応づけを得ることができ、なおかつ伸縮・スキュー・局所的な歪みが存在しても対応づけることが可能である。従って、ＯＣＲ装置の読み取り位置の位置決めや、印刷装置の位置決め、および２枚の画像の相違箇所の検出などの性能向上に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明に係る装置のハードウェアの構成を示す図である。
【図２】図１の読み取り装置１１の内部構造を示す図である。
【図３】本発明の一実施例に係る画像対応付け装置の機能ブロック図である。
【図４】２値画像としての基準画像の一部を示す図である。
【図５】上下エッジ画像を示す図である。
【図６】左右エッジ画像を示す図である。
【図７】上エッジ画像を示す図である。
【図８】下エッジ画像を示す図である。
【図９】左エッジ画像を示す図である。
【図１０】右エッジ画像を示す図である。
【図１１】２値画像の小ブロックを示す図である。
【図１２】上下エッジ画像の小ブロックを示す図である。
【図１３】左右エッジ画像の小ブロックを示す図である。
【図１４】探索範囲の初期値の決定方法を説明する図である。
【図１５】一致判定の第１の方法を説明する図である。
【図１６】一致判定の第２の方法を説明する図である。
【図１７】一致判定の第３の方法を説明する図である。
【図１８】一致判定の第３の方法を説明する図である。
【図１９】一致判定の第３の方法を説明する図である。
【図２０】一致判定の第３の方法を説明する図である。
【図２１】一致判定の第４の方法を説明する図である。
【図２２】一致判定の第４の方法を説明する機能ブロック図である。
【図２３】画像対応付け装置の動作のフローチャートである。
【図２４】画像対応付け装置の動作のフローチャートである。
【図２５】探索範囲の絞り込みの第１の手法を説明する図である。
【図２６】探索範囲の絞り込みの第２の手法を説明する図である。
【図２７】探索範囲の絞り込みの第２の手法を説明する図である。
【図２８】探索範囲の絞り込みの第３の手法を説明する図である。
【図２９】探索範囲の絞り込みの第３の手法を説明する図である。
【図３０】探索範囲の絞り込みの第３の手法を説明する図である。
【図３１】画像対応付け装置による対応付け結果を説明する図である。
【図３２】画像対応付け装置の第１の変形の機能ブロック図である。
【図３３】図３２の装置の動作を説明する図である。
【図３４】図３２の装置の動作を説明する図である。
【図３５】図３２の装置の動作を説明する図である。
【図３６】図３２の装置の動作を説明する図である。
【図３７】画像対応付け装置の第２の変形の機能ブロック図である。
【図３８】図３７の装置の動作を説明する図である。
【図３９】本発明の他の実施例に係る文字認識装置の機能ブロック図である。
【図４０】図３９の装置の動作を説明する図である。
【図４１】図３９の装置の動作を説明する図である。
【図４２】図３９の装置の動作を説明する図である。
【図４３】図３９の装置の動作を説明する図である。
【図４４】本発明のさらに他の実施例に係る文字認識装置の機能ブロック図である。
【図４５】図４４の装置の動作を説明する図である。
【図４６】本発明のさらに他の実施例に係る相異個所検出装置の機能ブロック図である。
【図４７】本発明のさらに他の実施例に係る印刷装置の機能ブロック図である。
【図４８】エッジ画像の生成方法を説明する図である。
【符号の説明】
１０…パーソナルコンピュータ
１１…読み取り装置
１２…ＣＤ−ＲＯＭドライブ
１３…ＣＤ−ＲＯＭ
１４…ホッパ
１５…ピックローラ
１６…搬送ローラ
１７…光源
１８…反射鏡
１９…レンズ
２０…１次元ＣＣＤ素子
２１…印字ユニット
２２，２３…スタッカ
３６…基準画像
３８…小ブロック
４０…入力画像
５２，６０，６２…探索範囲
５４…探索方向
５６…上下エッジ画像
５８…左右エッジ画像
【図１】
0003580670.tif 000002
【図２】
0003580670.tif 000003
【図３】
0003580670.tif 000004
【図４】
0003580670.tif 000005
【図５】
0003580670.tif 000006
【図６】
0003580670.tif 000007
【図７】
0003580670.tif 000008
【図８】
0003580670.tif 000009
【図９】
0003580670.tif 000010
【図１０】
0003580670.tif 000011
【図１１】
0003580670.tif 000012
【図１２】
0003580670.tif 000013
【図１３】
0003580670.tif 000014
【図１４】
0003580670.tif 000015
【図１５】
0003580670.tif 000016
【図１６】
0003580670.tif 000017
【図１７】
0003580670.tif 000018
【図１８】
0003580670.tif 000019
【図１９】
0003580670.tif 000020
【図２０】
0003580670.tif 000021
【図２１】
0003580670.tif 000022
【図２２】
0003580670.tif 000023
【図２３】
0003580670.tif 000024
【図２４】
0003580670.tif 000025
【図２５】
0003580670.tif 000026
【図２６】
0003580670.tif 000027
【図２７】
0003580670.tif 000028
【図２８】
0003580670.tif 000029
【図２９】
0003580670.tif 000030
【図３０】
0003580670.tif 000031
【図３１】
0003580670.tif 000032
【図３２】
0003580670.tif 000033
【図３３】
0003580670.tif 000034
【図３４】
0003580670.tif 000035
【図３５】
0003580670.tif 000036
【図３６】
0003580670.tif 000037
【図３７】
0003580670.tif 000038
【図３８】
0003580670.tif 000039
【図３９】
0003580670.tif 000040
【図４０】
0003580670.tif 000041
【図４１】
0003580670.tif 000042
【図４２】
0003580670.tif 000043
【図４３】
0003580670.tif 000044
【図４４】
0003580670.tif 000045
【図４５】
0003580670.tif 000046
【図４６】
0003580670.tif 000047
【図４７】
0003580670.tif 000048
【図４８】
0003580670.tif 000049