JPH10340348A

JPH10340348A - 画像位置合わせ方法、ファックス文字認識方法および記録媒体

Info

Publication number: JPH10340348A
Application number: JP9150675A
Authority: JP
Inventors: Kenji Fukumizu; 健次福水
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1997-06-09
Filing date: 1997-06-09
Publication date: 1998-12-22
Anticipated expiration: 2017-06-09
Also published as: JP3781324B2

Abstract

(57)【要約】【課題】対応する座標から誤対応を高精度に削除す
る。【解決手段】正対応確率算出部２は、対応座標取得部
１のマッチング距離を基に、各対応座標に正対応確率を
付与して格納部３に記憶する。パラメータ推定部４は、
座標の対応の発生分布を、正しい対応と誤った対応の混
合モデルでモデル化し、モデル関数のパラメータを最尤
推定によって求め、誤対応削除部５は、対応が誤ってい
る確率が所定の閾値以上の座標データを削除し、残った
対応座標を用いてパラメータを再計算する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ある画像と、それ
にアフィン的な変換を施された画像との座標の対応をと
る画像位置合わせ方法、ファックス文字認識方法および
記録媒体に関する。

【０００２】

【従来の技術】画像処理においては、位置や拡大率など
の異なるほぼ同一の内容の２つの画像間で、座標の対応
をとる技術が用いられる。例えば、ファックス文字認識
装置（ＦＡＸＯＣＲ装置）の前処理では、ＦＡＸで送信
された画像を原画像と比較することにより、認識対象と
なる領域を特定することが必要になる。そこで、送信さ
れた帳票画像とあらかじめ用意された参照画像との座標
対応を取る画像位置合わせの技術が重要となる。画像の
変換を推定するためにはまず、送信された処理対象画像
のある点が計算機内にあらかじめ保持された参照画像の
どの点に対応づけられているかを計算機が自動的に知る
必要がある。

【０００３】ＦＡＸＯＣＲ装置における従来の位置合わ
せ方法としては、特定の形状で特定の位置に印字された
タイミングマークを利用した手法が用いられていた（例
えば、特開平４−２６１２５９号公報を参照）。

【０００４】

【発明が解決しようとする課題】しかしながら、上記し
たタイミングマークを用いた方法では、タイミングマー
クを印字した新たな帳票の作成に要するコストがかかる
などの問題がある。そこで、これを解決するために、本
出願人は先に、処理対象画像と参照画像とに共通する複
数のパターンを抽出し、抽出されたパターンに関し、該
参照画像と該処理対象画像の対応した同一パターンを検
出し、該対応したパターンの相互の位置関係を求め、該
位置関係に基づき該処理対象画像と該参照画像との位置
合わせのための補正式を決定する画像処理方法を提案し
た（特願平８−５４３０８号）。この方法では、抽出パ
ターンをタイミングマークの代わりに用いている。

【０００５】ところで、参照画像と処理対象画像とのパ
ターンマッチングによって座標の対応をとる方法では、
マッチングの誤りのために誤った対応点データが含まれ
る可能性がある。そのために、正しい対応点を多く残し
ながら誤った対応点をすべて取り除くことが重要な課題
となり、これまでに、本出願人によってパターンの対応
の誤りを削除する手法が提案されているが（特願平８−
２４０１５４号）、誤対応が完全に除去されない場合も
あり、より精度の高い方法が求められていた。

【０００６】本発明の目的は、対応する座標から誤対応
を高精度に削除する画像位置合わせ方法、ファックス文
字認識方法および記録媒体を提供することにある。

【０００７】

【課題を解決するための手段】前記目的を達成するため
に、請求項１記載の発明では、参照画像と、該参照画像
に対して所定の幾何学的変換が施されて得られた処理対
象画像との座標対応をとる画像位置合わせ方法であっ
て、前記参照画像から抽出されたパターンの座標と、画
像マッチングにより抽出された処理対象画像中の同一パ
ターンの座標との対応を基に変換関数のパラメータを計
算するとき、パターンのマッチング距離を基に対応の正
しさを表す確率を算出し、該確率値と、対応座標から算
出される変換関数からの外れ度合いとを用いて、誤対応
であると判定された対応を削除し、前記変換関数のパラ
メータを再計算することを特徴としている。

【０００８】請求項２記載の発明では、前記座標の対応
の発生分布を、正しい対応を発生させる分布と誤った対
応を発生させる分布の２つの混合モデルとしてモデル化
し、正しい対応から発生する確率を、前記パターンマッ
チングに基づく対応の正しさを表す確率を用いて表した
とき、その尤度を最大化する変換関数のパラメータを求
め、該パラメータを用いて各対応に対して誤った対応の
分布の尤度の比率を求め、該比率が所定の閾値よりも高
い対応を誤対応であると判定することを特徴としてい
る。

【０００９】請求項３記載の発明では、前記尤度を最大
化する変換関数のパラメータを求めるとき、正しい対応
であるか誤った対応であるかを示す変数を隠れ変数とし
て用い、ＥＭ法による逐次的計算を行うことを特徴とし
ている。

【００１０】請求項４記載の発明では、前記ＥＭ法によ
る逐次的計算を行う際の初期パラメー夕は、大きな残差
を持ったデータの寄与度が小さくなるように重みをつけ
るロバスト推定法により求めることを特徴としている。

【００１１】請求項５記載の発明では、前記変換関数を
アフィン変換部分と非線形部分に分け、前記アフィン変
換による変換関数のパラメータ推定を行った後、残差の
大きさが所定の閾値を越えた場合に非線形関数系を用い
た残差部分の追加推定を行うことを特徴としている。

【００１２】請求項６記載の発明では、前記非線形関数
系として、多層パーセプトロンモデルを用いることを特
徴としている。

【００１３】請求項７記載の発明では、請求項１乃至６
記載の方法を用いて、ファクシミリから受信した処理対
象画像と、予め保持された参照画像との座標の対応をと
り、前記参照画像で指定された領域に対応する前記処理
対象画像中の領域を、文字認識することを特徴としてい
る。

【００１４】請求項８記載の発明では、参照画像と、該
参照画像に対して所定の幾何学的変換が施されて得られ
た処理対象画像との座標対応をとるために、前記参照画
像から抽出されたパターンの座標と、画像マッチングに
より抽出された処理対象画像中の同一パターンの座標と
の対応を基に変換関数のパラメータを計算する機能と、
パターンのマッチング距離を基に対応の正しさを表す確
率を算出する機能と、該確率値と、対応座標から算出さ
れる変換関数からの外れ度合いとを用いて、誤対応であ
ると判定された対応を削除する機能と、前記変換関数の
パラメータを再計算する機能をコンピュータに実現させ
るためのプログラムを記録したコンピュータ読み取り可
能な記録媒体であることを特徴としている。

【００１５】

【発明の実施の形態】以下、本発明の一実施例を図面を
用いて具体的に説明する。本発明の画像位置合わせ方法
は、様々な装置、システムに適用できるが、ここではＦ
ＡＸＯＣＲ装置を一例にして説明する。前述したよう
に、ＦＡＸＯＣＲ装置は、ファクシミリにより送られて
きた帳票の画像を取り込み、この入力画像（処理対象画
像）と同種帳票の参照画像とを位置合わせした後、入力
画像中の必要な記載事項（これは、参照画像で予め指定
された領域に対応するもの）を切り出し、文字認識処理
を行ってデータとして出力するものである。

【００１６】このＦＡＸＯＣＲ装置は、画像入力部と、
画像位置合わせ部と、認識処理部とに大きく分けられ
る。本発明は画像位置合わせ部に係るものであるが、本
発明では、前掲した出願（特願平８−５４３０８号）の
手法を一部用いる。すなわち、画像位置合わせ部は、入
力画像メモリと、パターン抽出部と、同一パターン抽出
部と、参照画像パターンメモリと、対応点検出部からな
り、パターン抽出部は入力画像から所定の大きさのパタ
ーンを抽出し、同一パターン抽出部は、抽出された入力
パターンと同一のパターンを参照画像パターンメモリか
ら見つけ、対応点検出部では、入力画像と参照画像の対
応した同一パターンの座標を検出する。

【００１７】〈実施例１〉図１は、本発明の実施例１の
構成を示す。本発明の画像位置合わせ部は、対応座標取
得部１と、正対応確率算出部２と、対応格納部３と、混
合モデルパラメータ推定部４と、誤対応削除部５からな
る。また、図２は、本発明の処理フローチャートを示
す。

【００１８】まず、対応座標取得部１は、２つの画像間
の座標の対応をとるためのデータとして、対応している
と想定される、参照画像と処理対象画像の座標の組

【００１９】

【数１】

【００２０】を取得する。ここで

【００２１】

【数２】

【００２２】は参照画像の座標を表す２次元ベクトルで
あり、

【００２３】

【数３】

【００２４】は処理対象画像の座標を表す２次元ベクト
ルである。この座標の組の取得のために、前述した出願
の方法を用いることができる。

【００２５】この対応を作成する際には、パターンマッ
チングが行われるので、これら対応にそれぞれマッチン
グ距離ｄ₁，，，，，ｄ_Nが計算されている。このマッチ
ング距離に基づいて、正対応確率算出部２は、各対応に
正対応確率ｐ₁，，，，ｐ_Nを付与する。これらの確率
は、それぞれの対応が正しい確率をマッチングの距離に
基づいて算出したものである。座標の対応と正対応確率
の組

【００２６】

【数４】

【００２７】は対応格納部３に記憶され、変換関数のパ
ラメータ計算に用いられる。

【００２８】正対応確率の求め方の一例として、あらか
じめ作成した表によるものがあげられる。この方法は、
多数の参照画像と処理対象画像のパターンの例に対し
て、マッチング距離とその対応の正誤の組を与え、マッ
チング距離ｄを持つ対応が正しい対応である確率ｐ
（ｄ）をｐ（ｄ）＝（マッチング距離ｄで正しい対応の個数）／（マッチング距離がｄである対応の個数）（１）により計算し、適当な粗さに量子化したｄに対してｐ
（ｄ）を与える正対応確率テーブルをもつものである。

【００２９】変換関数を求めるためには、パラメータθ
を持った関数の族ｆ（ｘ；θ）を用いて、データに当て
はまるθを計算するというパラメトリック推定法を用い
る。例えば、ＦＡＸＯＣＲのオリジナル画像と受信画像
との間の変換を求める際には、その変換が拡大縮小、回
転などに起因することを考慮して、ｆ（ｘ；θ）をアフ
ィン変換ｆ（ｘ；θ）＝Ａｘ＋ｂ（２）（θ＝（Ａ，ｂ））に設定するとよい。ここでＡは２×
２行列であり、ｂは２次元ベクトルである。

【００３０】また、本実施例では、正しい対応を発生さ
せる分布と、誤った対応を発生させる分布を、平均が同
一で分散が異なる２つの分布によってモデル化し、それ
ぞれの発生頻度をマッチング距離に基づく正対応確率に
よって定めることを特徴としている。特に計算を簡単に
する目的からは、この２つの分布を正規分布に設定する
と都合がよい。このため、以降では正規分布の場合のみ
を説明する。

【００３１】対応（ｘ，ｙ）がマッチング距離ｄを持つ
とき、それを発生させる確率モデルを

【００３２】

【数５】

【００３３】で定める。σ，τはそれぞれ正対応、誤対
応の誤差分布の分散を表し、σ＜＜τであると考える。
これらの分散はあらかじめ問題に対する知識によってあ
る定数に設定しておくものとし、パラメータ推定部４に
おいてデータから推定するパラメータはθのみとする。
パラメータθを求める基準として最尤推定を用いる。

【００３４】推定量

【００３５】

【数６】

【００３６】が得られた後に（ステップ１０１）、誤っ
た対応だと考えられるものを除外する処理を、誤対応削
除部５で行う。各対応

【００３７】

【数７】

【００３８】に対し、誤った対応の分布の尤度の比率

【００３９】

【数８】

【００４０】を計算する（ステップ１０２、１０３）。
Ｐ_false（ν）は対応

【００４１】

【数９】

【００４２】が誤っている確率を表している。

【００４３】Ｐ_false（ｎ）がある閾値Ｄ_th以上の時に
（ステップ１０４）、そのデータは誤っているとして削
除する（ステップ１０５）。こうして、すべての対応に
対して処理が終了した後（ステップ１０６、１０７）、
残った対応に対してパラメータの再計算を行い最終的な
結果を得る（ステップ１０８）。このパラメータの計算
としては、通常の最小２乗誤差推定量を用いればよい。

【００４４】次に、混合モデルの最尤推定量の求め方に
ついて説明する。対応格納部に記憶された座標の対応と
正対応確率の組

【００４５】

【数１０】

【００４６】に対し、最尤推定によりθを求めるため
に、逐次的なパラメータ更新手法であるＥＭ法を用い
る。

【００４７】ＥＭアルゴリズムは、観測されない隠れ変
数がある場合に、最尤推定量を得ることを目的とした逐
次的手法である。ここで、その一般的な方法を簡単に説
明する。パラメータθを持った、変数（ｖ，ｕ）上の確
率密度関数の族｛ｐ（ｖ，ｕ；θ）｝を考える。確率変
数ｖは観測可能な変数であり、その標本を取得すること
ができるが、変数ｕは隠れ変数と呼ばれ、パラメータθ
の推定にあたってその標本を採取することができないと
仮定する。すべての変数が観測できれば対数尤度

【００４８】

【数１１】

【００４９】を最大化すればよいが、隠れ変数がある場
合には、

【００５０】

【数１２】

【００５１】を用いることができないため、逐次的な手
法として、現在得られているパラメータを

【００５２】

【数１３】

【００５３】とするとき、隠れ変数ｕについて

【００５４】

【数１４】

【００５５】が与えられた時の条件付き平均をとった

【００５６】

【数１５】

【００５７】を最大にするθを新たな

【００５８】

【数１６】

【００５９】とする。条件付き平均値を計算する過程を
Ｅステップ、対数尤度を計算する過程をＭステップと呼
ぶ。ＥＭアルゴリズムはこの２つのステップの繰返しに
より尤度の最大化をはかる。

【００６０】ＥＭアルゴリズムを本発明に適用する場合
には、以下のようにモデル化を行う。すなわち、得られ
た対応（ｘ，ｙ，ｄ）に対し、これが正しい対応である
か誤った対応であるかを示すラベルｕを隠れ変数として
導入する。ｕは２次元の変数であり、（１，０）か
（０，１）かの何れかの値をとる。隠れ変数も含めた統
計モデルは、

【００６１】

【数１７】

【００６２】となる。このモデルに対する周辺分布ｐ
（ｙ｜ｘ，ｄ；θ）は（３）式と一致しているため、上
式に対する最尤推定ができれば、（３）式に対する最尤
推定にもなっている。このモデルに対して上で述べたＥ
Ｍアルゴリズムの一般的な枠組を適用すると、隠れ変数
に関する期待値は

【００６３】

【数１８】

【００６４】で計算される。ここで、

【００６５】

【数１９】

【００６６】は以下のように定められている。

【００６７】

【数２０】

【００６８】ここで表記を簡単にするため、

【００６９】

【数２１】

【００７０】とおいた。従って、この最大化は以下の
（６）式の重み付き２乗誤差最小化により解くことがで
きる。

【００７１】このＥＭ手法は、図３のような手順で実行
される。まず、パラメータθの初期化を行い、初期パラ
メータをθ（０）とおく（ステップ２０１）。第ｔステ
ップ目には推定量θ（ｔ−１）が得られているとして、
各対応

【００７２】

【数２２】

【００７３】に対して上記

【００７４】

【数２３】

【００７５】を計算する（ステップ２０２、２０３）。

【００７６】第ｔステップの推定量

【００７７】

【数２４】

【００７８】は

【００７９】

【数２５】

【００８０】の解として求められる。特にｆ（ｘ；θ）
がアフィン変換の場合には、

【００８１】

【数２６】

【００８２】と書くことにして

【００８３】

【数２７】

【００８４】により計算される（ステップ２０４）。こ
れらの計算が終了判定条件を満すまで繰り返され（ステ
ップ２０５、２０６）、最終的な推定量

【００８５】

【数２８】

【００８６】が得られる（ステップ２０７）。終了判定
条件には処理フローに示すように、繰返しの回数を用い
てもよいし、推定量の変化量が一定の閾値以内であれば
終了としてもよい。

【００８７】次に、ＥＭ法の繰返し計算を行う際の初期
値の決定方法について説明する。ＥＭ法などのような繰
返し演算では、初期値によって最終的な結果が大きな影
響を受けやすい。そのため、ある程度よい初期値から演
算を始めた方がよい。そこで、本発明では、ロバスト推
定としてよく知られたＷ推定量を用いる。Ｗ推定量の計
算は、図４に示されたような処理フローで行われる。

【００８８】まず、適当な重み関数ρ（ｕ）を定める。
これは大きな残差を持ったデータの寄与を小さくするた
めの関数であり、例えば

【００８９】

【数２９】

【００９０】などを用いる。

【００９１】まず重みの初期値

【００９２】

【数３０】

【００９３】を、例えばすべて同一の値のように、適当
な値で初期化する（ステップ３０１）。第（ｔ−１）段
の重みが決まっているとき、第ｔ段の推定値としては、
重みつき２乗誤差

【００９４】

【数３１】

【００９５】を最小にする推定量を計算する。アフィン
変換の場合には

【００９６】

【数３２】

【００９７】によって得られる（ステップ３０２、３０
３）。この推定量を用いて、あらたな重みを

【００９８】

【数３３】

【００９９】によって計算する（ステップ３０４）。こ
の計算を繰返し行う（ステップ３０５、３０６）。最終
的にステップ３０７で得られた推定量が、図３のステッ
プ２０１の初期パラメータとなる。

【０１００】さらに、本実施例では、画像の変換に非線
形性が存在する場合にも有効性を持つ。まず、上記した
本発明の方法でアフィン変換による推定を行った後、非
線形用データとして、アフィン変換による残差

【０１０１】

【数３４】

【０１０２】を算出する。このとき平均２乗残差

【０１０３】

【数３５】

【０１０４】がある閾値以上であると、非線形変換によ
る残差補償を行う。そのために、非線形関数系

【０１０５】

【数３６】

【０１０６】を用意し、データ

【０１０７】

【数３７】

【０１０８】を用いて２乗誤差最小基準により最適なパ
ラメータωを求める。非線形関数系としては、多項式系
などのようなものも用いることができるが、本実施例で
は特に多層パーセプトロンモデルを用いる。ここでは中
間素子をＨ個持つ３層パーセブトロンモデルを説明す
る。このモデルはパラメータ

【０１０９】

【数３８】

【０１１０】に対し、

【０１１１】

【数３９】

【０１１２】という関数系で定義される非線形モデルで
ある。ここでｓ（ｔ）はシグモイド関数と呼ばれ

【０１１３】

【数４０】

【０１１４】という形である。シグモイド関数は局所的
な伸び縮みを表現できるので、３層パーセプトロンによ
る非線形補償は、ファクシミリ画像でしばしば見受けら
れる、ある方向（特にスキャン方向）への局所的な伸び
縮みをよくモデル化できると考えられる。

【０１１５】３層パーセプトロンのパラメータを最適化
するには、公知の技術であるエラーバックプロパゲーシ
ョンが用いられる。こうして得られたパラメータを

【０１１６】

【数４１】

【０１１７】とすると、画像の変換を計算する際には、

【０１１８】

【数４２】

【０１１９】によって変換先を計算する。

【０１２０】〈実施例２〉本発明は上記した実施例に限
定されず、ソフトウェアによっても実現することができ
る。本発明をソフトウェアによって実現する場合には、
図５に示すように、ＣＰＵ、ＲＯＭ、ＲＡＭ、表示装
置、ハードディスク、キーボード、ＣＤ−ＲＯＭドライ
ブ、スキャナなどからなるコンピュータシステムを用意
し、ＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記
録媒体には、本発明の画像位置合わせ機能、文字認識機
能を実現するプログラムが記録されている。また、ＦＡ
Ｘなどから入力された帳票などの画像は一時的にハード
ディスクなどに格納される。そして、該プログラムが起
動されると、一時保存された画像データが読み込まれ
て、画像位置合わせ処理を実行すると共に、帳票画像の
特定領域を文字認識し、その認識結果をディスプレイな
どに出力する。

【０１２１】

【発明の効果】以上、説明したように、本発明によれ
ば、ＦＡＸＯＣＲなどの画像位置合わせにおいて、ロバ
スト（頑健）で誤りの少ない変換関数のパラメータ推定
を行うことが可能となる。その結果、ＦＡＸＯＣＲにお
ける認識領域の特定精度が向上し、ひいては文字認識の
認識率が向上する。

【図面の簡単な説明】

【図１】本発明の実施例１の構成を示す。

【図２】本発明の処理フローチャートを示す。

【図３】ＥＭ法によるパラメータ計算のフローチャート
を示す。

【図４】Ｗ推定量の計算を行うフローチャートを示す。

【図５】本発明をソフトウェアによって実現する場合の
実施例２の構成例を示す。

【符号の説明】

１対応座標取得部２正対応確率算出部３対応格納部４混合モデルパラメータ推定部５誤対応削除部

Claims

【特許請求の範囲】

【請求項１】参照画像と、該参照画像に対して所定の
幾何学的変換が施されて得られた処理対象画像との座標
対応をとる画像位置合わせ方法であって、前記参照画像
から抽出されたパターンの座標と、画像マッチングによ
り抽出された処理対象画像中の同一パターンの座標との
対応を基に変換関数のパラメータを計算するとき、パタ
ーンのマッチング距離を基に対応の正しさを表す確率を
算出し、該確率値と、対応座標から算出される変換関数
からの外れ度合いとを用いて、誤対応であると判定され
た対応を削除し、前記変換関数のパラメータを再計算す
ることを特徴とする画像位置合わせ方法。
【請求項２】前記座標の対応の発生分布を、正しい対
応を発生させる分布と誤った対応を発生させる分布の２
つの混合モデルとしてモデル化し、正しい対応から発生
する確率を、前記パターンマッチングに基づく対応の正
しさを表す確率を用いて表したとき、その尤度を最大化
する変換関数のパラメータを求め、該パラメータを用い
て各対応に対して誤った対応の分布の尤度の比率を求
め、該比率が所定の閾値よりも高い対応を誤対応である
と判定することを特徴とする請求項１記載の画像位置合
わせ方法。
【請求項３】前記尤度を最大化する変換関数のパラメ
ータを求めるとき、正しい対応であるか誤った対応であ
るかを示す変数を隠れ変数として用い、ＥＭ法による逐
次的計算を行うことを特徴とする請求項２記載の画像位
置合わせ方法。
【請求項４】前記ＥＭ法による逐次的計算を行う際の
初期パラメー夕は、大きな残差を持ったデータの寄与度
が小さくなるように重みをつけるロバスト推定法により
求めることを特徴とする請求項３記載の画像位置合わせ
方法。
【請求項５】前記変換関数をアフィン変換部分と非線
形部分に分け、前記アフィン変換による変換関数のパラ
メータ推定を行った後、残差の大きさが所定の閾値を越
えた場合に非線形関数系を用いた残差部分の追加推定を
行うことを特徴とする請求項１記載の画像位置合わせ方
法。
【請求項６】前記非線形関数系として、多層パーセプ
トロンモデルを用いることを特徴とする請求項５記載の
画像位置合わせ方法。
【請求項７】請求項１乃至６記載の方法を用いて、フ
ァクシミリから受信した処理対象画像と、予め保持され
た参照画像との座標の対応をとり、前記参照画像で指定
された領域に対応する前記処理対象画像中の領域を、文
字認識することを特徴とするファックス文字認識方法。
【請求項８】参照画像と、該参照画像に対して所定の
幾何学的変換が施されて得られた処理対象画像との座標
対応をとるために、前記参照画像から抽出されたパター
ンの座標と、画像マッチングにより抽出された処理対象
画像中の同一パターンの座標との対応を基に変換関数の
パラメータを計算する機能と、パターンのマッチング距
離を基に対応の正しさを表す確率を算出する機能と、該
確率値と、対応座標から算出される変換関数からの外れ
度合いとを用いて、誤対応であると判定された対応を削
除する機能と、前記変換関数のパラメータを再計算する
機能をコンピュータに実現させるためのプログラムを記
録したコンピュータ読み取り可能な記録媒体。