画像処理装置及び画像処理プログラム
【課題】２つの画像の相似性の判断を、従来と比してより短時間でより少ないメモリ使用量で実現可能とする。
【解決手段】変動補正パラメータ推定部２５は、処理対象の各画像から生成された投影波形の局所ピークとなる位置座標と当該位置の投影波高値との組により表される各画像の特徴量から、一方の画像のピーク位置それぞれを、他方の画像の各ピーク位置と重ね合わせるための拡縮率ｋ及び移動量ｓで表されるｓ−ｋ平面座標上の直線式を生成し、予め決められた範囲を複数のセルに分割し、セル毎に直線式の投票を行う。そして、同じピーク位置に基づく直線式が重複して通過するセルが存在する場合、そのセルを同じピーク位置に基づく直線式が重複して存在しなくなるまで再分割し、その後最大投票値となるセル内の直線式に基づき拡縮率ｋ及び移動量ｓを変動補正パラメータとして推定する。
【解決手段】変動補正パラメータ推定部２５は、処理対象の各画像から生成された投影波形の局所ピークとなる位置座標と当該位置の投影波高値との組により表される各画像の特徴量から、一方の画像のピーク位置それぞれを、他方の画像の各ピーク位置と重ね合わせるための拡縮率ｋ及び移動量ｓで表されるｓ−ｋ平面座標上の直線式を生成し、予め決められた範囲を複数のセルに分割し、セル毎に直線式の投票を行う。そして、同じピーク位置に基づく直線式が重複して通過するセルが存在する場合、そのセルを同じピーク位置に基づく直線式が重複して存在しなくなるまで再分割し、その後最大投票値となるセル内の直線式に基づき拡縮率ｋ及び移動量ｓを変動補正パラメータとして推定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
従来から２つの文書の相似性を判断するために、例えば、従来では、文書をラスタ画像化し、各画像の特徴量を求め、各特徴量を参照に相似変換パラメータを推定し、一方の画像をこの推定した相似変換パラメータにて拡縮してから他方の画像と照合する技術が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４１４０２２１号明細書
【特許文献２】特許第３６９３１４７号明細書
【特許文献３】特開平１０−２６９３５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、２つの画像の相似性の判断を行う過程において求める相似変換パラメータの推定精度の向上を図ることを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る画像処理装置は、比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段と、取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段と、前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段と、を有し、前記相似変換パラメータ推定手段は、一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、ことを特徴とする。
【０００６】
また、前記相似変換パラメータ推定手段は、一次関数が通過する数が最大となる領域を検出してから、その検出した領域のみを対象として、前記特定したピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域の検出を行うことを特徴とする。
【０００７】
また、前記相似変換パラメータ推定手段は、領域を複数の領域に再分割した場合、分割対象となった領域において一次関数の交点を求め、再分割により生成された領域のうち、求めた交点が存在する領域及びその領域に隣接した領域のみを、通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する対象とすることを特徴とする。
【０００８】
本発明に係る画像処理プログラムは、コンピュータを、比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段、取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段、前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段、として機能させ、前記相似変換パラメータ推定手段は、一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、ことを特徴とする。
【発明の効果】
【０００９】
請求項１，４記載の発明によれば、本構成を有さない場合に比較して、２つの画像の相似性の判断を行う過程において求める相似変換パラメータの推定精度の向上を図ることができる。
【００１０】
請求項２，３記載の発明によれば、２つの画像の相似性の判断を、対象とする領域を特定しない場合と比較して、より短時間に、あるいは、より少ないメモリ使用量で実現することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。
【図２】本実施の形態における画像処理装置を形成するコンピュータのハードウェア構成図である。
【図３】本実施の形態における画像照合処理を示したフローチャートである。
【図４】本実施の形態において投影波形及び文書画像の特徴量の生成について説明するために用いる図である。
【図５】本実施の形態における変動補正パラメータ推定処理を示したフローチャートである。
【図６】本実施の形態において参照文書画像における局所ピーク座標と入力文書画像における局所ピーク座標との対応付けについて示した図である。
【図７】本実施の形態において生成するｓ−ｋ平面座標の一例を示した図である。
【図８】図７に示したｓ−ｋ平面座標に設定された補正範囲内を複数のセルに分割したときのｓ−ｋ平面座標の一例を示した図である。
【図９】本実施の形態において重複投票が発生しうる参照文書画像における局所ピーク座標と入力文書画像における局所ピーク座標との位置関係について示した図である。
【図１０】本実施の形態において重複投票が発生しているセルの一例を示した図である。
【図１１】図１０に示したセルを再分割したときの状態を示した図である。
【図１２】本実施の形態においてｓ−ｋ平面座標上で直線式が交わる部分を示した図である。
【図１３】本実施の形態においてセルを再分割したときの当該セルの要部を示した図である。
【発明を実施するための形態】
【００１２】
以下、図面に基づいて、本発明の好適な実施の形態について説明する。
【００１３】
図１は、本発明に係る画像処理装置２０の一実施の形態を示したブロック構成図であり、図２は、この画像処理装置２０を形成するコンピュータのハードウェア構成図である。本実施の形態において画像処理装置２０を形成するコンピュータは、従前から存在する汎用的なハードウェア構成で実現できる。すなわち、コンピュータは、図２に示したようにＣＰＵ１、ＲＯＭ２、ＲＡＭ３、ハードディスクドライブ（ＨＤＤ）４を接続したＨＤＤコントローラ５、入力手段として設けられたマウス６とキーボード７、及び表示装置として設けられたディスプレイ８をそれぞれ接続する入出力コントローラ９、通信手段として設けられたネットワークコントローラ１０を内部バス１１に接続して構成される。
【００１４】
図１に戻り、画像処理装置２０は、投影波形生成部２１，２２、特徴量生成部２３，２４、変動補正パラメータ推定部２５、投影波形補正部２６及び照合スコア算出部２７を有している。投影波形生成部２１は、入力文書画像から投影波形を生成する。投影波形生成部２２は、参照文書画像から投影波形を生成する。投影波形生成部２１と投影波形生成部２２は、処理対象とする画像が異なるだけで、実施する処理自体は同じでよい。特徴量生成部２３は、投影波形生成部２１により生成された投影波形から入力文書画像の特徴量を生成する。特徴量生成部２４は、投影波形生成部２２により生成された投影波形から参照文書画像の特徴量を生成する。特徴量生成部２３と特徴量生成部２４は、処理対象とする画像の投影波形が異なるだけで、実施する処理自体は同じでよい。変動補正パラメータ推定部２５は、各特徴量生成部２３，２４により得られた各文書画像の特徴量を取得すると、その各文書画像の特徴量から変動補正パラメータを相似変換パラメータとして推定する。投影波形補正部２６は、変動補正パラメータ推定部２５により得られた変動補正パラメータで入力文書画像の投影波形を補正する。照合スコア算出部２７は、参照文書画像と、投影波形補正部２６により補正された入力文書画像の投影波形とを照合することによって参照文書と入力文書との相似関係の判定指標となる照合スコアを算出する。
【００１５】
画像処理装置２０における各構成要素２１〜２７は、画像処理装置２０を形成するコンピュータと、コンピュータに搭載されたＣＰＵ１で動作するプログラムとの協調動作により実現される。
【００１６】
また、本実施の形態で用いるプログラムは、通信手段により提供することはもちろん、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に格納して提供することも可能である。通信手段や記録媒体から提供されたプログラムはコンピュータにインストールされ、コンピュータのＣＰＵがインストールプログラムを順次実行することで各種処理が実現される。
【００１７】
本実施の形態における特徴的なことは、変動補正パラメータ推定部２５における変動補正パラメータの推定処理において、重複投票を検出するようにし、そして、重複投票が検出された場合には、重複投票が検出されたセルを再分割して重複投票をなくし、重複投票がなくなった段階で最大投票値となるセルに基づき変動補正パラメータの推定を行うようにしたことである。それ以外の処理は、特許文献１と同様の処理内容としてもよい。
【００１８】
次に、本実施の形態における画像照合処理について図３に示したフローチャートを用いて説明する。
【００１９】
比較対象となる入力文書及び参照文書の各画像が送られてくると、投影波形生成部２１，２２は、それぞれの文書画像を受け取り（ステップ１００）、各画像からＸ，Ｙ方向への投影波形を生成する（ステップ２００）。そして、特徴量生成部２３，２４は、それぞれ生成された投影波形に基づき各画像の特徴量を生成する（ステップ３００）。ここまでの処理について、図４を用いて詳述する。
【００２０】
なお、参照文書の画像というのは、入力文書の画像との照合の際に参照される文書のラスタライズされた画像データである。入力文書の画像というのは、参照文書の画像と照合される文書のラスタライズされた画像データである。つまり、本実施の形態における画像処理装置２０は、入力文書が参照文書と相似関係にあるか否かについて判定を行うための指標として照合スコアを提供する。これらの画像データは、画像処理装置２０に、ユーザにより指定された各文書の画像データを画像データベースから読み出されて入力されたり、スキャナ等の画像入力手段により読み取られ、ラスタ画像データに変換された後に入力されたりする。ここで説明する投影波形及び特徴量の生成処理は、入力文書及び参照文書の各画像に対して同じ処理を施すので、ここでは、入力文書の画像を代表して説明する。
【００２１】
入力文書の画像が入力されると、投影波形生成部２１は、このラスタ画像データに対し、水平方向又は垂直方向の少なくとも一方に対する投影波形を形成する。例えば、入力される文書が縦書きであるか横書きであるかが予めわかっており、当該方向の投影波形のみで十分個々の文書の特徴を表すことができることがわかっている場合は、一方向のみへの投影を形成するだけでもよい。ただ、文書画像データの特徴が不明瞭な場合は両方向への投影波形を形成するのが好ましい。本実施の形態では、Ｘ，Ｙの両方向に対して投影波形を生成する。
【００２２】
ここで、投影とは、ラスタ形式の画像データに対し、Ｘ方向又はＹ方向に沿ったある経路において当該経路上に位置する画素の画素値を累算する処理をいう。Ｘ方向又はＹ方向に沿って経路が複数ある場合に、その累算した結果の数列が投影波形をなす。投影波形生成部２１は、画素値の累算結果を経路毎に求める。この場合、現実的には投影波形の形成処理前に公知の傾き補正技術を利用して読み取り時の軽微な傾きを補正しておくことが好ましい。
【００２３】
Ｘ方向の経路の場合、投影波形生成部２１は、文書画像１２に対し、Ｘ方向の経路上の画素の画素値を累算することにより投影波形を生成する。そして、本実施の形態では、その経路の中から所定の条件を満たす特徴部分を表す位置を選別する。特徴部分を表す位置を選別する所定の条件の一例としては、極値（局所的ピーク）、変曲点などの微分波形特徴量などがある。本実施の形態では、累算値の局所ピーク値となる位置を選別する。そして、特徴量生成部２３は、選別した局所ピークとなる位置の座標（ｘｎ）と当該位置の投影波高値（ｐｘｎ）とを組にすることによって当該位置の特徴量（ｘｎ，ｐｘｎ）として生成し、これらの特徴量のリストをＸ方向の入力文書画像特徴量として生成する。Ｙ方向においても同様にして、局所ピークとなる位置の座標（ｙｍ）と当該位置の投影波高値（ｐｙｍ）とを組にすることによって当該位置の特徴量（ｙｍ，ｐｙｍ）として生成し、これらの特徴量のリストをＹ方向の入力文書画像特徴量として生成する。なお、本実施の形態では、Ｘ，Ｙ方向それぞれにおいて局所ピーク座標を抽出しているので、ｎとｍの各値は必ずしも一致するとは限らない。
【００２４】
投影波形生成部２２及び特徴量生成部２４も同様に処理して投影波形の生成及びＸ，Ｙの各方向の参照文書画像特徴量を生成する。なお、入力文書画像及び参照文書画像のＸ方向の各局所ピーク座標の数は、必ずしも一致するとは限らない。Ｙ方向においても同様である。
【００２５】
なお、参照文書に関しては、特徴量の生成処理までを事前に実施し、その処理結果をＨＤＤ４に保存しておき、この処理結果値を以降の処理において読み出し利用するようにしてもよい。
【００２６】
続いて、変動補正パラメータ推定部２５は、上記処理にて生成した参照文書画像及び入力文書画像の各文書画像特徴量から両文書のＸ，Ｙ方向への投影波形が最も重なるような変動補正パラメータを推定する（ステップ４００）。変動補正パラメータが複数組推定される場合は、変動補正パラメータのリストを生成する。変動補正パラメータ推定部２５は、参照文書と入力文書とを照合するために入力文書画像の局所ピーク座標を参照文書画像の局所ピーク座標に重ね合わせるように処理するわけであるが、この際、入力文書画像を拡大又は縮小し、あるいは平行に移動させることになる。つまり、変動補正パラメータというのは、Ｘ，Ｙの各方向において、参照文書画像の局所ピーク座標に入力文書画像の局所ピーク座標を重ね合わせる際の入力文書画像の拡縮率と移動量により表される。この変動補正パラメータ推定部２５における変動補正パラメータ推定処理について、図５に示したフローチャートを用いて説明する。
【００２７】
変動補正パラメータ推定部２５は、参照文書と入力文書の各画像の特徴量について、次の処理をＸ，Ｙ方向毎にそれぞれ行う。まず、Ｘ方向について、図６に例示したように参照文書画像の特徴量にｍ個の局所ピーク座標ａ１〜ａｍが、入力文書画像の特徴量にｎ個の局所ピーク座標ｂ１〜ｂｎが、それぞれ含まれているとすると、変動補正パラメータ推定部２５は、参照文書画像特徴量から局所ピーク座標（ａｉ（１≦ｉ≦ｍ））を、入力文書画像特徴量から局所ピーク座標（ｂｊ（１≦ｊ≦ｎ））を、それぞれ一つずつ選び、その入力文書画像特徴量における局所ピーク座標ｂｊを参照文書画像特徴量における局所ピーク座標ａｉに重ね合わせるときの拡縮率と移動量の関係を示す直線式を生成する。この直線式は、ｓ−ｋ平面座標上において、ａｉ＝ｋ×ｂｊ＋ｓという一次関数の式にて表せる。式中のｋは原点を基準点としてｂｊをａｉに重ね合わせるために投影波形を拡縮させたときの拡縮率、ｓはｂｊを拡縮と共に平行移動させたときの移動量である。各局所ピーク座標の全ての組み合わせについて同様の直線式を生成することにより直線式のリストを生成する（ステップ４０１）。つまり、直線式のリストには、ｍ×ｎ本の直線式が含まれる。この直線式をｓ−ｋ平面座標に描画した場合の例を図７に示す。直線リストを生成する際、変動補正パラメータ推定部２５は、直線式を生成する際に対応付けた１組の局所ピーク座標（ａｉとｂｊ）を、この直線式に関連付けして記憶しておく。
【００２８】
以上の処理をＹ方向についても行う。ここまでの処理により、図７に例示したｓ−ｋ平面座標がＸ，Ｙ方向それぞれに生成される。
【００２９】
ところで、拡縮率ｋに関し、ｋ＝１は拡縮無し、０＜ｋ＜１は縮小、ｋ＞１は拡大を意味するが、例えば変動補正パラメータである拡縮率ｋが存在するであろう範囲を、最大値ｋｍａｘ＝１０．０、最小値ｋｍｉｎ＝０．１などと予め決めておく。同様に、移動量ｓに関し、例えば移動量ｓの移動範囲を最大値ｓｍａｘ＝５０ピクセル、移動範囲の最小値ｓｍｉｎ＝−５０ピクセルなどと予め決めておく。そして、このように予め設定された補正範囲を例えば１６分割などの所定数に分割する（ステップ４０２）。この分割により得られた小領域をセルと称することにする。このｓ−ｋ平面座標の補正範囲内を複数に分割したときのｓ−ｋ平面座標の例を図８に示す。なお、補正範囲を分割する所定の数については、追って説明する。
【００３０】
変動補正パラメータ推定部２５は、続いてセル毎に直線を投票し（ステップ４０３）、そして投票値が最大となるセルを検出する（ステップ４０４）。投票というのは、当該セルを通過する直線の数を積算することである。なお、投票値が最大となるセルが複数検出された場合は、それらのセルのリストを生成する。
【００３１】
そして、変動補正パラメータ推定部２５は、投票が最大となるセルの中から重複投票となるセルを検出する（ステップ４０５）。ここで、重複投票について説明する。
【００３２】
例えば、図９に例示したように、入力文書画像特徴量に含まれる局所ピーク座標ｂ２，ｂ３はそれぞれ、わずかに拡縮をするか、わずかに移動させることによって参照文書画像特徴量に含まれる局所ピーク座標ａ２と重ねられるとする。図１０は、直線式が通過するあるセルを示した図であるが、この例のように局所ピーク座標ａ２，ｂ２に基づき生成された直線式及び局所ピーク座標ａ２，ｂ３に基づき生成された直線式のように、同じ局所ピーク座標ａ２により生成された直線式が同じセルの中に重複して通過する場合があり得る。数ピクセルの間隔で引かれた罫線などが文書画像に含まれていた場合は、このようなケースが発生しうるかもしれない。しかしながら、局所ピーク座標ａ２は、局所ピーク座標ｂ２及びｂ３と同時に重ねられることはない。つまり、１つの局所ピーク座標が同時に複数の局所ピーク座標と対応付けられることはあり得ない。本実施の形態では、このように、１つの局所ピーク座標に基づき生成された直線式が１つのセルに投票されていることを重複投票と称することにするが、このような重複投票を含むセルにおける投票数は正しい値を示していない。ステップ４０６では、図１０に例示した重複投票がされているセルが検出される。
【００３３】
変動補正パラメータ推定部２５は、直線式のリストを生成する際に当該セルの中を通過する各直線式に関連付けられた局所ピーク座標を参照することによって重複投票を検出する。そして、重複投票が検出されなかった場合（ステップ４０６でＮ）、投票値が最大となるセルを特定する（ステップ４０７）。なお、投票値が最大となるセルが複数特定され場合もあり得る。そして、変動補正パラメータ推定部２５は、変動補正パラメータを推定することになるが（ステップ４０８）、この処理については追って詳述する。
【００３４】
一方、重複投票が検出された場合（ステップ４０６でＹ）、変動補正パラメータ推定部２５は、重複投票が検出されたセルのみを所定数に再分割する（ステップ４０９）。重複投票が検出されたセルのみを再分割の対象とするので、他のセルは、再分割のためにメモリ（ＲＡＭ３）にロードする必要はない。図１０に例示したセルが再分割されたときの例を図１１に示す。複数のセルで重複投票が検出された場合、その検出された複数のセル全てにおいて再分割する。再分割する所定の数については、追って説明する。そして、再分割したセルにおいて改めて投票を行う（ステップ４１０）。再分割したセル毎に投票を行った後は、最大投票値となるセルを検出する処理（ステップ４０４）に戻る。重複投票が検出されなくなるまでセルの再分割、投票する処理（ステップ４０９，４１０）は、再帰的に繰り返される。
【００３５】
以上のようにして、重複投票されたセルがない状態で最大投票値となるセルが特定されと、変動補正パラメータ推定部２５は、セルに含まれる直線式の交点、すなわち変動補正パラメータである拡縮率ｋと移動量ｓを推定する（ステップ４０８）。
【００３６】
なお、入力文書と参照文書とが相似関係にある場合、最大投票値となるセルが複数特定された場合でも、基本的には、拡縮率ｋと移動量ｓの組は１つだけ得られる。つまり、ある最大投票値となるセルの中に交点は存在しなくても、そのセルの中を通過する直線式から求められる交点は、他の最大投票値となるセルの中にある交点と一致するはずである。但し、スキャナの読取精度等の要因で、理論的には複数の交点が得られてしまう場合もあり得る。この場合、複数の変動補正パラメータが推定されることになる。ここで、変動補正パラメータを推定する処理（ステップ４０８）について詳述する。
【００３７】
参照文書と入力文書が相似関係にあるとしたならば、理論的には、正しい拡縮率ｋと移動量ｓとの組が１つだけ存在するため、あるセル内で複数の直線がｓ−ｋ平面座標のその拡縮率ｋと移動量ｓとで表される交点（ｓ＊，ｋ＊）で交わるはずである。ところが、実際には、スキャナの読取精度、各文書の用紙の伸縮、ノイズの影響などが原因で多少の誤差が生じ、これにより、本来、直線式が交点（ｓ＊，ｋ＊）で交わるところを、図１２に例示するように若干のずれが生じてくる場合があり得る。そこで、本実施の形態では、以下の説明するように拡縮率ｋ及び移動量ｓの各パラメータ値を補正して複数の直線から１つの交点（ｓ＊，ｋ＊）を求めるようにした。
【００３８】
本実施の形態においては、直線群から最小距離にある点の座標を交点の座標とみなすようにした。すなわち、セル内の点（ｓ，ｋ）から直線ａｉ＝ｋ×ｂｊ＋ｓまでの距離をｄｉ，ｊとすると、
【数１】
という式にて表せる。また、セル内を通過する直線群から最小距離にある点の座標を（ｓ＊，ｋ＊）とすると、この点は各直線からの距離の二乗和が最小となる点として求める。つまり、
【数２】
という式にて表せる。但し、上式におけるＣは、セル内を通過する直線群のパラメータ添字（ｉ，ｊ）を表す。このような（ｓ＊，ｋ＊）は次の式を解くことにより、解析的に求める。
【数３】
【００３９】
以上のようにして、変動補正パラメータ推定部２５は、セル内における点（ｓ＊，ｋ＊）、すなわち、拡縮率ｋ及び移動量ｓを変動補正パラメータとして求める。
【００４０】
なお、上記説明では、ステップ４１０において再分割した全てのセルに対して改めて投票を行うとした。ただ、再分割した場合、図１３のようにセルＡに交点があると考えられる場合、セルＣに対しセルＡと同様に投票を行っても、セルＣの直線式から得られる交点は、セルＡに存在することになるのでその投票処理は無駄になる。そこで、セルを再分割した場合、再分割したセルの中で交点が存在するセルＡをステップ４１０における投票の前に求めておき、セルＡに隣接しないセルＣに関しては、投票等以降の処理の対象外としてもよい。つまり、セルＣに関するデータは、メモリにロードする必要はない。なお、セルＡに隣接したセルＢに対しても処理対象外としてもよいが、セルＢに存在するはずの交点が、実際には誤差のためにセルＡに存在すると誤って推定されるような場合も考慮して、隣接するセルＢは処理対象外としないようにしてもよい。
【００４１】
ここで、補正範囲及びセルの分割について説明する。
【００４２】
前述したように、本実施の形態においては、ステップ４０２において補正範囲を複数のセルに分割した。ここで、補正範囲を大まかに分割すると（セルの数を少なくすると）、重複投票が発生するセルの数が増えてしまい、再分割及び再分割後の各領域への投票を行う処理にかかる負荷が増大する。一方、補正範囲を細かに分割すると（セルの数を多くすると）、直線式の投票や重複投票の検出に要する処理負荷が大きくなる。このように、補正範囲を分割する数に関しては、トレードオフの関係にある。ただ、本実施の形態では、重複投票が発生した場合、その発生したセルのみを再分割及び再度の投票の対象とすることによって、これらの問題を解消しうる。つまり、補正範囲の分割する所定数に関しては、自由度が高く、適当に設定しておいても処理速度やメモリ使用量の点で従来と比較して改善が見込める。セルの再分割についても同様である。
【００４３】
図３に戻り、以上のようにして変動補正パラメータが得られると、投影波形補正部２６は、変動補正パラメータ推定部２５により得られた変動補正パラメータ（拡縮率ｋと移動量ｓ）で入力文書画像の投影波形を補正する（ステップ５００）。なお、複数の変動補正パラメータが求められていた場合には、それぞれの変動補正パラメータで入力文書画像の投影波形を補正する。
【００４４】
照合スコア算出部２７は、参照文書画像の投影波形と、投影波形補正部２６により補正された入力文書画像の投影波形とを照合することによって参照文書と入力文書との相似関係の判定指標となる照合スコアを算出する（ステップ６００）。照合スコアは、例えば相関係数によりＸ，Ｙ方向毎に求めるようにしてもよい。
【００４５】
照合スコア算出部２７が算出した照合スコアを参照することによって、操作者が入力文書と参照文書の相似関係を判断する。あるいは、他の装置が照合スコアを予め設定した閾値と比較することによって相似関係の有無を判定する。複数の変動補正パラメータが求められていたことにより複数の組の照合スコアが算出されていた場合には、照合スコアの大きい方のみを正しい変動補正パラメータと認識して判定してもよい。
【００４６】
ところで、照合スコアをＸ，Ｙの各方向の相関値の和とした場合、Ｘ，Ｙ方向の各相関値が０．７，０．７のときも０．４，１．０のときも、照合スコアは共に１．４と算出される。ただ、前者に対し、後者の場合は、Ｘ方向の相関値が０．４と低いのにかかわらず、参照文書と入力文書とに相似関係があると判定されてしまうかもしれない。そこで、先に求めた相関値が所定の閾値より小さい場合は、入力文書と参照文書との間に相似関係はないと判定し、これ以降の処理をスキップしてもよい。
【００４７】
ところで、入力文書と参照文書の相似関係の判定を、照合スコア算出部２７を動作させることなく行うようにしてもよい。例えば、入力文書を拡縮する場合、横方向と縦方向の拡縮率を、通常は縦横ほぼ均等の割合で拡縮するはずである。つまり、通常は、縦横均等の倍率でコピーするものであり、極端に縦長や横長にコピーなどしない。本実施の形態では、変動補正パラメータ推定部２５が変動補正パラメータ（拡縮率ｋ及び移動量ｓ）をＸ，Ｙ方向それぞれに推定するわけであるが、いずれかの文書画像におけるＸ方向とＹ方向の変動補正パラメータ値があまりにも異なっていた場合、例えば入力文書画像におけるＸ方向の拡縮率がＹ方向の０．９〜１．１倍の範囲にない場合など所定の差異以上に異なっていた場合には、適切な変動補正パラメータが得られなかったとして以降の処理をスキップする。つまり、Ｘ，Ｙ方向の拡縮率ｋが所定以上に異なる場合は、照合スコア算出部２７に照合スコアを算出させるまでもなく入力文書と参照文書との間に相似関係はないものと判定する。
【符号の説明】
【００４８】
１ ＣＰＵ、２ ＲＯＭ、３ ＲＡＭ、４ ハードディスクドライブ（ＨＤＤ）、５ ＨＤＤコントローラ、６ マウス、７ キーボード、８ ディスプレイ、９ 入出力コントローラ、１０ ネットワークコントローラ、１１ 内部バス、２０ 画像処理装置、２１，２２ 投影波形生成部、２３，２４ 特徴量生成部、２５ 変動補正パラメータ推定部、２６ 投影波形補正部、２７ 照合スコア算出部。
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
従来から２つの文書の相似性を判断するために、例えば、従来では、文書をラスタ画像化し、各画像の特徴量を求め、各特徴量を参照に相似変換パラメータを推定し、一方の画像をこの推定した相似変換パラメータにて拡縮してから他方の画像と照合する技術が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４１４０２２１号明細書
【特許文献２】特許第３６９３１４７号明細書
【特許文献３】特開平１０−２６９３５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、２つの画像の相似性の判断を行う過程において求める相似変換パラメータの推定精度の向上を図ることを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る画像処理装置は、比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段と、取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段と、前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段と、を有し、前記相似変換パラメータ推定手段は、一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、ことを特徴とする。
【０００６】
また、前記相似変換パラメータ推定手段は、一次関数が通過する数が最大となる領域を検出してから、その検出した領域のみを対象として、前記特定したピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域の検出を行うことを特徴とする。
【０００７】
また、前記相似変換パラメータ推定手段は、領域を複数の領域に再分割した場合、分割対象となった領域において一次関数の交点を求め、再分割により生成された領域のうち、求めた交点が存在する領域及びその領域に隣接した領域のみを、通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する対象とすることを特徴とする。
【０００８】
本発明に係る画像処理プログラムは、コンピュータを、比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段、取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段、前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段、として機能させ、前記相似変換パラメータ推定手段は、一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、ことを特徴とする。
【発明の効果】
【０００９】
請求項１，４記載の発明によれば、本構成を有さない場合に比較して、２つの画像の相似性の判断を行う過程において求める相似変換パラメータの推定精度の向上を図ることができる。
【００１０】
請求項２，３記載の発明によれば、２つの画像の相似性の判断を、対象とする領域を特定しない場合と比較して、より短時間に、あるいは、より少ないメモリ使用量で実現することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明に係る画像処理装置の一実施の形態を示したブロック構成図である。
【図２】本実施の形態における画像処理装置を形成するコンピュータのハードウェア構成図である。
【図３】本実施の形態における画像照合処理を示したフローチャートである。
【図４】本実施の形態において投影波形及び文書画像の特徴量の生成について説明するために用いる図である。
【図５】本実施の形態における変動補正パラメータ推定処理を示したフローチャートである。
【図６】本実施の形態において参照文書画像における局所ピーク座標と入力文書画像における局所ピーク座標との対応付けについて示した図である。
【図７】本実施の形態において生成するｓ−ｋ平面座標の一例を示した図である。
【図８】図７に示したｓ−ｋ平面座標に設定された補正範囲内を複数のセルに分割したときのｓ−ｋ平面座標の一例を示した図である。
【図９】本実施の形態において重複投票が発生しうる参照文書画像における局所ピーク座標と入力文書画像における局所ピーク座標との位置関係について示した図である。
【図１０】本実施の形態において重複投票が発生しているセルの一例を示した図である。
【図１１】図１０に示したセルを再分割したときの状態を示した図である。
【図１２】本実施の形態においてｓ−ｋ平面座標上で直線式が交わる部分を示した図である。
【図１３】本実施の形態においてセルを再分割したときの当該セルの要部を示した図である。
【発明を実施するための形態】
【００１２】
以下、図面に基づいて、本発明の好適な実施の形態について説明する。
【００１３】
図１は、本発明に係る画像処理装置２０の一実施の形態を示したブロック構成図であり、図２は、この画像処理装置２０を形成するコンピュータのハードウェア構成図である。本実施の形態において画像処理装置２０を形成するコンピュータは、従前から存在する汎用的なハードウェア構成で実現できる。すなわち、コンピュータは、図２に示したようにＣＰＵ１、ＲＯＭ２、ＲＡＭ３、ハードディスクドライブ（ＨＤＤ）４を接続したＨＤＤコントローラ５、入力手段として設けられたマウス６とキーボード７、及び表示装置として設けられたディスプレイ８をそれぞれ接続する入出力コントローラ９、通信手段として設けられたネットワークコントローラ１０を内部バス１１に接続して構成される。
【００１４】
図１に戻り、画像処理装置２０は、投影波形生成部２１，２２、特徴量生成部２３，２４、変動補正パラメータ推定部２５、投影波形補正部２６及び照合スコア算出部２７を有している。投影波形生成部２１は、入力文書画像から投影波形を生成する。投影波形生成部２２は、参照文書画像から投影波形を生成する。投影波形生成部２１と投影波形生成部２２は、処理対象とする画像が異なるだけで、実施する処理自体は同じでよい。特徴量生成部２３は、投影波形生成部２１により生成された投影波形から入力文書画像の特徴量を生成する。特徴量生成部２４は、投影波形生成部２２により生成された投影波形から参照文書画像の特徴量を生成する。特徴量生成部２３と特徴量生成部２４は、処理対象とする画像の投影波形が異なるだけで、実施する処理自体は同じでよい。変動補正パラメータ推定部２５は、各特徴量生成部２３，２４により得られた各文書画像の特徴量を取得すると、その各文書画像の特徴量から変動補正パラメータを相似変換パラメータとして推定する。投影波形補正部２６は、変動補正パラメータ推定部２５により得られた変動補正パラメータで入力文書画像の投影波形を補正する。照合スコア算出部２７は、参照文書画像と、投影波形補正部２６により補正された入力文書画像の投影波形とを照合することによって参照文書と入力文書との相似関係の判定指標となる照合スコアを算出する。
【００１５】
画像処理装置２０における各構成要素２１〜２７は、画像処理装置２０を形成するコンピュータと、コンピュータに搭載されたＣＰＵ１で動作するプログラムとの協調動作により実現される。
【００１６】
また、本実施の形態で用いるプログラムは、通信手段により提供することはもちろん、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に格納して提供することも可能である。通信手段や記録媒体から提供されたプログラムはコンピュータにインストールされ、コンピュータのＣＰＵがインストールプログラムを順次実行することで各種処理が実現される。
【００１７】
本実施の形態における特徴的なことは、変動補正パラメータ推定部２５における変動補正パラメータの推定処理において、重複投票を検出するようにし、そして、重複投票が検出された場合には、重複投票が検出されたセルを再分割して重複投票をなくし、重複投票がなくなった段階で最大投票値となるセルに基づき変動補正パラメータの推定を行うようにしたことである。それ以外の処理は、特許文献１と同様の処理内容としてもよい。
【００１８】
次に、本実施の形態における画像照合処理について図３に示したフローチャートを用いて説明する。
【００１９】
比較対象となる入力文書及び参照文書の各画像が送られてくると、投影波形生成部２１，２２は、それぞれの文書画像を受け取り（ステップ１００）、各画像からＸ，Ｙ方向への投影波形を生成する（ステップ２００）。そして、特徴量生成部２３，２４は、それぞれ生成された投影波形に基づき各画像の特徴量を生成する（ステップ３００）。ここまでの処理について、図４を用いて詳述する。
【００２０】
なお、参照文書の画像というのは、入力文書の画像との照合の際に参照される文書のラスタライズされた画像データである。入力文書の画像というのは、参照文書の画像と照合される文書のラスタライズされた画像データである。つまり、本実施の形態における画像処理装置２０は、入力文書が参照文書と相似関係にあるか否かについて判定を行うための指標として照合スコアを提供する。これらの画像データは、画像処理装置２０に、ユーザにより指定された各文書の画像データを画像データベースから読み出されて入力されたり、スキャナ等の画像入力手段により読み取られ、ラスタ画像データに変換された後に入力されたりする。ここで説明する投影波形及び特徴量の生成処理は、入力文書及び参照文書の各画像に対して同じ処理を施すので、ここでは、入力文書の画像を代表して説明する。
【００２１】
入力文書の画像が入力されると、投影波形生成部２１は、このラスタ画像データに対し、水平方向又は垂直方向の少なくとも一方に対する投影波形を形成する。例えば、入力される文書が縦書きであるか横書きであるかが予めわかっており、当該方向の投影波形のみで十分個々の文書の特徴を表すことができることがわかっている場合は、一方向のみへの投影を形成するだけでもよい。ただ、文書画像データの特徴が不明瞭な場合は両方向への投影波形を形成するのが好ましい。本実施の形態では、Ｘ，Ｙの両方向に対して投影波形を生成する。
【００２２】
ここで、投影とは、ラスタ形式の画像データに対し、Ｘ方向又はＹ方向に沿ったある経路において当該経路上に位置する画素の画素値を累算する処理をいう。Ｘ方向又はＹ方向に沿って経路が複数ある場合に、その累算した結果の数列が投影波形をなす。投影波形生成部２１は、画素値の累算結果を経路毎に求める。この場合、現実的には投影波形の形成処理前に公知の傾き補正技術を利用して読み取り時の軽微な傾きを補正しておくことが好ましい。
【００２３】
Ｘ方向の経路の場合、投影波形生成部２１は、文書画像１２に対し、Ｘ方向の経路上の画素の画素値を累算することにより投影波形を生成する。そして、本実施の形態では、その経路の中から所定の条件を満たす特徴部分を表す位置を選別する。特徴部分を表す位置を選別する所定の条件の一例としては、極値（局所的ピーク）、変曲点などの微分波形特徴量などがある。本実施の形態では、累算値の局所ピーク値となる位置を選別する。そして、特徴量生成部２３は、選別した局所ピークとなる位置の座標（ｘｎ）と当該位置の投影波高値（ｐｘｎ）とを組にすることによって当該位置の特徴量（ｘｎ，ｐｘｎ）として生成し、これらの特徴量のリストをＸ方向の入力文書画像特徴量として生成する。Ｙ方向においても同様にして、局所ピークとなる位置の座標（ｙｍ）と当該位置の投影波高値（ｐｙｍ）とを組にすることによって当該位置の特徴量（ｙｍ，ｐｙｍ）として生成し、これらの特徴量のリストをＹ方向の入力文書画像特徴量として生成する。なお、本実施の形態では、Ｘ，Ｙ方向それぞれにおいて局所ピーク座標を抽出しているので、ｎとｍの各値は必ずしも一致するとは限らない。
【００２４】
投影波形生成部２２及び特徴量生成部２４も同様に処理して投影波形の生成及びＸ，Ｙの各方向の参照文書画像特徴量を生成する。なお、入力文書画像及び参照文書画像のＸ方向の各局所ピーク座標の数は、必ずしも一致するとは限らない。Ｙ方向においても同様である。
【００２５】
なお、参照文書に関しては、特徴量の生成処理までを事前に実施し、その処理結果をＨＤＤ４に保存しておき、この処理結果値を以降の処理において読み出し利用するようにしてもよい。
【００２６】
続いて、変動補正パラメータ推定部２５は、上記処理にて生成した参照文書画像及び入力文書画像の各文書画像特徴量から両文書のＸ，Ｙ方向への投影波形が最も重なるような変動補正パラメータを推定する（ステップ４００）。変動補正パラメータが複数組推定される場合は、変動補正パラメータのリストを生成する。変動補正パラメータ推定部２５は、参照文書と入力文書とを照合するために入力文書画像の局所ピーク座標を参照文書画像の局所ピーク座標に重ね合わせるように処理するわけであるが、この際、入力文書画像を拡大又は縮小し、あるいは平行に移動させることになる。つまり、変動補正パラメータというのは、Ｘ，Ｙの各方向において、参照文書画像の局所ピーク座標に入力文書画像の局所ピーク座標を重ね合わせる際の入力文書画像の拡縮率と移動量により表される。この変動補正パラメータ推定部２５における変動補正パラメータ推定処理について、図５に示したフローチャートを用いて説明する。
【００２７】
変動補正パラメータ推定部２５は、参照文書と入力文書の各画像の特徴量について、次の処理をＸ，Ｙ方向毎にそれぞれ行う。まず、Ｘ方向について、図６に例示したように参照文書画像の特徴量にｍ個の局所ピーク座標ａ１〜ａｍが、入力文書画像の特徴量にｎ個の局所ピーク座標ｂ１〜ｂｎが、それぞれ含まれているとすると、変動補正パラメータ推定部２５は、参照文書画像特徴量から局所ピーク座標（ａｉ（１≦ｉ≦ｍ））を、入力文書画像特徴量から局所ピーク座標（ｂｊ（１≦ｊ≦ｎ））を、それぞれ一つずつ選び、その入力文書画像特徴量における局所ピーク座標ｂｊを参照文書画像特徴量における局所ピーク座標ａｉに重ね合わせるときの拡縮率と移動量の関係を示す直線式を生成する。この直線式は、ｓ−ｋ平面座標上において、ａｉ＝ｋ×ｂｊ＋ｓという一次関数の式にて表せる。式中のｋは原点を基準点としてｂｊをａｉに重ね合わせるために投影波形を拡縮させたときの拡縮率、ｓはｂｊを拡縮と共に平行移動させたときの移動量である。各局所ピーク座標の全ての組み合わせについて同様の直線式を生成することにより直線式のリストを生成する（ステップ４０１）。つまり、直線式のリストには、ｍ×ｎ本の直線式が含まれる。この直線式をｓ−ｋ平面座標に描画した場合の例を図７に示す。直線リストを生成する際、変動補正パラメータ推定部２５は、直線式を生成する際に対応付けた１組の局所ピーク座標（ａｉとｂｊ）を、この直線式に関連付けして記憶しておく。
【００２８】
以上の処理をＹ方向についても行う。ここまでの処理により、図７に例示したｓ−ｋ平面座標がＸ，Ｙ方向それぞれに生成される。
【００２９】
ところで、拡縮率ｋに関し、ｋ＝１は拡縮無し、０＜ｋ＜１は縮小、ｋ＞１は拡大を意味するが、例えば変動補正パラメータである拡縮率ｋが存在するであろう範囲を、最大値ｋｍａｘ＝１０．０、最小値ｋｍｉｎ＝０．１などと予め決めておく。同様に、移動量ｓに関し、例えば移動量ｓの移動範囲を最大値ｓｍａｘ＝５０ピクセル、移動範囲の最小値ｓｍｉｎ＝−５０ピクセルなどと予め決めておく。そして、このように予め設定された補正範囲を例えば１６分割などの所定数に分割する（ステップ４０２）。この分割により得られた小領域をセルと称することにする。このｓ−ｋ平面座標の補正範囲内を複数に分割したときのｓ−ｋ平面座標の例を図８に示す。なお、補正範囲を分割する所定の数については、追って説明する。
【００３０】
変動補正パラメータ推定部２５は、続いてセル毎に直線を投票し（ステップ４０３）、そして投票値が最大となるセルを検出する（ステップ４０４）。投票というのは、当該セルを通過する直線の数を積算することである。なお、投票値が最大となるセルが複数検出された場合は、それらのセルのリストを生成する。
【００３１】
そして、変動補正パラメータ推定部２５は、投票が最大となるセルの中から重複投票となるセルを検出する（ステップ４０５）。ここで、重複投票について説明する。
【００３２】
例えば、図９に例示したように、入力文書画像特徴量に含まれる局所ピーク座標ｂ２，ｂ３はそれぞれ、わずかに拡縮をするか、わずかに移動させることによって参照文書画像特徴量に含まれる局所ピーク座標ａ２と重ねられるとする。図１０は、直線式が通過するあるセルを示した図であるが、この例のように局所ピーク座標ａ２，ｂ２に基づき生成された直線式及び局所ピーク座標ａ２，ｂ３に基づき生成された直線式のように、同じ局所ピーク座標ａ２により生成された直線式が同じセルの中に重複して通過する場合があり得る。数ピクセルの間隔で引かれた罫線などが文書画像に含まれていた場合は、このようなケースが発生しうるかもしれない。しかしながら、局所ピーク座標ａ２は、局所ピーク座標ｂ２及びｂ３と同時に重ねられることはない。つまり、１つの局所ピーク座標が同時に複数の局所ピーク座標と対応付けられることはあり得ない。本実施の形態では、このように、１つの局所ピーク座標に基づき生成された直線式が１つのセルに投票されていることを重複投票と称することにするが、このような重複投票を含むセルにおける投票数は正しい値を示していない。ステップ４０６では、図１０に例示した重複投票がされているセルが検出される。
【００３３】
変動補正パラメータ推定部２５は、直線式のリストを生成する際に当該セルの中を通過する各直線式に関連付けられた局所ピーク座標を参照することによって重複投票を検出する。そして、重複投票が検出されなかった場合（ステップ４０６でＮ）、投票値が最大となるセルを特定する（ステップ４０７）。なお、投票値が最大となるセルが複数特定され場合もあり得る。そして、変動補正パラメータ推定部２５は、変動補正パラメータを推定することになるが（ステップ４０８）、この処理については追って詳述する。
【００３４】
一方、重複投票が検出された場合（ステップ４０６でＹ）、変動補正パラメータ推定部２５は、重複投票が検出されたセルのみを所定数に再分割する（ステップ４０９）。重複投票が検出されたセルのみを再分割の対象とするので、他のセルは、再分割のためにメモリ（ＲＡＭ３）にロードする必要はない。図１０に例示したセルが再分割されたときの例を図１１に示す。複数のセルで重複投票が検出された場合、その検出された複数のセル全てにおいて再分割する。再分割する所定の数については、追って説明する。そして、再分割したセルにおいて改めて投票を行う（ステップ４１０）。再分割したセル毎に投票を行った後は、最大投票値となるセルを検出する処理（ステップ４０４）に戻る。重複投票が検出されなくなるまでセルの再分割、投票する処理（ステップ４０９，４１０）は、再帰的に繰り返される。
【００３５】
以上のようにして、重複投票されたセルがない状態で最大投票値となるセルが特定されと、変動補正パラメータ推定部２５は、セルに含まれる直線式の交点、すなわち変動補正パラメータである拡縮率ｋと移動量ｓを推定する（ステップ４０８）。
【００３６】
なお、入力文書と参照文書とが相似関係にある場合、最大投票値となるセルが複数特定された場合でも、基本的には、拡縮率ｋと移動量ｓの組は１つだけ得られる。つまり、ある最大投票値となるセルの中に交点は存在しなくても、そのセルの中を通過する直線式から求められる交点は、他の最大投票値となるセルの中にある交点と一致するはずである。但し、スキャナの読取精度等の要因で、理論的には複数の交点が得られてしまう場合もあり得る。この場合、複数の変動補正パラメータが推定されることになる。ここで、変動補正パラメータを推定する処理（ステップ４０８）について詳述する。
【００３７】
参照文書と入力文書が相似関係にあるとしたならば、理論的には、正しい拡縮率ｋと移動量ｓとの組が１つだけ存在するため、あるセル内で複数の直線がｓ−ｋ平面座標のその拡縮率ｋと移動量ｓとで表される交点（ｓ＊，ｋ＊）で交わるはずである。ところが、実際には、スキャナの読取精度、各文書の用紙の伸縮、ノイズの影響などが原因で多少の誤差が生じ、これにより、本来、直線式が交点（ｓ＊，ｋ＊）で交わるところを、図１２に例示するように若干のずれが生じてくる場合があり得る。そこで、本実施の形態では、以下の説明するように拡縮率ｋ及び移動量ｓの各パラメータ値を補正して複数の直線から１つの交点（ｓ＊，ｋ＊）を求めるようにした。
【００３８】
本実施の形態においては、直線群から最小距離にある点の座標を交点の座標とみなすようにした。すなわち、セル内の点（ｓ，ｋ）から直線ａｉ＝ｋ×ｂｊ＋ｓまでの距離をｄｉ，ｊとすると、
【数１】
という式にて表せる。また、セル内を通過する直線群から最小距離にある点の座標を（ｓ＊，ｋ＊）とすると、この点は各直線からの距離の二乗和が最小となる点として求める。つまり、
【数２】
という式にて表せる。但し、上式におけるＣは、セル内を通過する直線群のパラメータ添字（ｉ，ｊ）を表す。このような（ｓ＊，ｋ＊）は次の式を解くことにより、解析的に求める。
【数３】
【００３９】
以上のようにして、変動補正パラメータ推定部２５は、セル内における点（ｓ＊，ｋ＊）、すなわち、拡縮率ｋ及び移動量ｓを変動補正パラメータとして求める。
【００４０】
なお、上記説明では、ステップ４１０において再分割した全てのセルに対して改めて投票を行うとした。ただ、再分割した場合、図１３のようにセルＡに交点があると考えられる場合、セルＣに対しセルＡと同様に投票を行っても、セルＣの直線式から得られる交点は、セルＡに存在することになるのでその投票処理は無駄になる。そこで、セルを再分割した場合、再分割したセルの中で交点が存在するセルＡをステップ４１０における投票の前に求めておき、セルＡに隣接しないセルＣに関しては、投票等以降の処理の対象外としてもよい。つまり、セルＣに関するデータは、メモリにロードする必要はない。なお、セルＡに隣接したセルＢに対しても処理対象外としてもよいが、セルＢに存在するはずの交点が、実際には誤差のためにセルＡに存在すると誤って推定されるような場合も考慮して、隣接するセルＢは処理対象外としないようにしてもよい。
【００４１】
ここで、補正範囲及びセルの分割について説明する。
【００４２】
前述したように、本実施の形態においては、ステップ４０２において補正範囲を複数のセルに分割した。ここで、補正範囲を大まかに分割すると（セルの数を少なくすると）、重複投票が発生するセルの数が増えてしまい、再分割及び再分割後の各領域への投票を行う処理にかかる負荷が増大する。一方、補正範囲を細かに分割すると（セルの数を多くすると）、直線式の投票や重複投票の検出に要する処理負荷が大きくなる。このように、補正範囲を分割する数に関しては、トレードオフの関係にある。ただ、本実施の形態では、重複投票が発生した場合、その発生したセルのみを再分割及び再度の投票の対象とすることによって、これらの問題を解消しうる。つまり、補正範囲の分割する所定数に関しては、自由度が高く、適当に設定しておいても処理速度やメモリ使用量の点で従来と比較して改善が見込める。セルの再分割についても同様である。
【００４３】
図３に戻り、以上のようにして変動補正パラメータが得られると、投影波形補正部２６は、変動補正パラメータ推定部２５により得られた変動補正パラメータ（拡縮率ｋと移動量ｓ）で入力文書画像の投影波形を補正する（ステップ５００）。なお、複数の変動補正パラメータが求められていた場合には、それぞれの変動補正パラメータで入力文書画像の投影波形を補正する。
【００４４】
照合スコア算出部２７は、参照文書画像の投影波形と、投影波形補正部２６により補正された入力文書画像の投影波形とを照合することによって参照文書と入力文書との相似関係の判定指標となる照合スコアを算出する（ステップ６００）。照合スコアは、例えば相関係数によりＸ，Ｙ方向毎に求めるようにしてもよい。
【００４５】
照合スコア算出部２７が算出した照合スコアを参照することによって、操作者が入力文書と参照文書の相似関係を判断する。あるいは、他の装置が照合スコアを予め設定した閾値と比較することによって相似関係の有無を判定する。複数の変動補正パラメータが求められていたことにより複数の組の照合スコアが算出されていた場合には、照合スコアの大きい方のみを正しい変動補正パラメータと認識して判定してもよい。
【００４６】
ところで、照合スコアをＸ，Ｙの各方向の相関値の和とした場合、Ｘ，Ｙ方向の各相関値が０．７，０．７のときも０．４，１．０のときも、照合スコアは共に１．４と算出される。ただ、前者に対し、後者の場合は、Ｘ方向の相関値が０．４と低いのにかかわらず、参照文書と入力文書とに相似関係があると判定されてしまうかもしれない。そこで、先に求めた相関値が所定の閾値より小さい場合は、入力文書と参照文書との間に相似関係はないと判定し、これ以降の処理をスキップしてもよい。
【００４７】
ところで、入力文書と参照文書の相似関係の判定を、照合スコア算出部２７を動作させることなく行うようにしてもよい。例えば、入力文書を拡縮する場合、横方向と縦方向の拡縮率を、通常は縦横ほぼ均等の割合で拡縮するはずである。つまり、通常は、縦横均等の倍率でコピーするものであり、極端に縦長や横長にコピーなどしない。本実施の形態では、変動補正パラメータ推定部２５が変動補正パラメータ（拡縮率ｋ及び移動量ｓ）をＸ，Ｙ方向それぞれに推定するわけであるが、いずれかの文書画像におけるＸ方向とＹ方向の変動補正パラメータ値があまりにも異なっていた場合、例えば入力文書画像におけるＸ方向の拡縮率がＹ方向の０．９〜１．１倍の範囲にない場合など所定の差異以上に異なっていた場合には、適切な変動補正パラメータが得られなかったとして以降の処理をスキップする。つまり、Ｘ，Ｙ方向の拡縮率ｋが所定以上に異なる場合は、照合スコア算出部２７に照合スコアを算出させるまでもなく入力文書と参照文書との間に相似関係はないものと判定する。
【符号の説明】
【００４８】
１ ＣＰＵ、２ ＲＯＭ、３ ＲＡＭ、４ ハードディスクドライブ（ＨＤＤ）、５ ＨＤＤコントローラ、６ マウス、７ キーボード、８ ディスプレイ、９ 入出力コントローラ、１０ ネットワークコントローラ、１１ 内部バス、２０ 画像処理装置、２１，２２ 投影波形生成部、２３，２４ 特徴量生成部、２５ 変動補正パラメータ推定部、２６ 投影波形補正部、２７ 照合スコア算出部。
【特許請求の範囲】
【請求項１】
比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段と、
取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段と、
前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段と、
を有し、
前記相似変換パラメータ推定手段は、
一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、
相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、
各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、
領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、
一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、
ことを特徴とする画像処理装置。
【請求項２】
前記相似変換パラメータ推定手段は、
一次関数が通過する数が最大となる領域を検出してから、その検出した領域のみを対象として、前記特定したピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域の検出を行うことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記相似変換パラメータ推定手段は、
領域を複数の領域に再分割した場合、分割対象となった領域において一次関数の交点を求め、再分割により生成された領域のうち、求めた交点が存在する領域及びその領域に隣接した領域のみを、通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する対象とすることを特徴とする請求項１に記載の画像処理装置。
【請求項４】
コンピュータを、
比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段、
取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段、
前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段、
として機能させ、
前記相似変換パラメータ推定手段は、
一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、
相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、
各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、
領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、
一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、
ことを特徴とする画像処理プログラム。
【請求項１】
比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段と、
取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段と、
前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段と、
を有し、
前記相似変換パラメータ推定手段は、
一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、
相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、
各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、
領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、
一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、
ことを特徴とする画像処理装置。
【請求項２】
前記相似変換パラメータ推定手段は、
一次関数が通過する数が最大となる領域を検出してから、その検出した領域のみを対象として、前記特定したピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域の検出を行うことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記相似変換パラメータ推定手段は、
領域を複数の領域に再分割した場合、分割対象となった領域において一次関数の交点を求め、再分割により生成された領域のうち、求めた交点が存在する領域及びその領域に隣接した領域のみを、通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する対象とすることを特徴とする請求項１に記載の画像処理装置。
【請求項４】
コンピュータを、
比較対象とする各画像の画素値を水平又は垂直の少なくとも一方方向に累算し、その累算値のピーク位置を特定する情報を含む特徴量情報を取得する手段、
取得した各画像に対応した特徴量情報から、一方の画像の前記ピーク位置を基準点から拡縮又は平行移動の少なくとも一方をさせることにより他方の画像の前記ピーク位置に重ね合わせるための相似変換パラメータであって拡縮率及び移動量で表される相似変換パラメータを推定する相似変換パラメータ推定手段、
前記一方の画像を前記相似変換パラメータにより補正した後、前記各画像の相似関係を示す指標を算出する手段、
として機能させ、
前記相似変換パラメータ推定手段は、
一方の画像の前記ピーク位置それぞれを、他方の画像の前記ピーク位置のそれぞれと重ね合わせるための拡縮率及び移動量で表される拡縮率−移動量平面座標上の一次関数を生成し、
相似変換パラメータが存在するであろう拡縮率−移動量平面座標上の予め決められた範囲を複数の領域に分割し、
各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を領域毎に特定し、
領域毎に特定した前記ピーク位置の組の中に同じピーク位置に基づく一次関数が重複して通過する領域が存在する場合、重複して通過する領域が存在しなくなるまで、当該領域を複数の領域に再分割し、その再分割した各領域を通過する一次関数の数を求めると共に当該各一次関数を生成した各画像の前記ピーク位置の組を特定する処理を繰り返し行い、
一次関数が通過する数が最大となる領域を通過する一次関数に基づいて相似変換パラメータを求める、
ことを特徴とする画像処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１１−５９９６１（Ｐ２０１１−５９９６１Ａ）
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願番号】特願２００９−２０８５７３（Ｐ２００９−２０８５７３）
【出願日】平成２１年９月９日（２００９．９．９）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願日】平成２１年９月９日（２００９．９．９）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]