(57)【要約】【課題】文書画像中の文字が直線状に並んでいない場合や文字に直線的な部分が存在しない場合にもスキュー補正できる手法を提供する。射影変換やアフィン変換などの変形を受けた画像の補正にも適用できる手法を提供する。【解決手段】不変量と変量を組み合わせた幾何変形推定法を用い、変形量を推定し、推定に基づき画像を補正する。実施形態では、あらかじめ様々な文字フォントを回転させながら変量（例えば、文字の外接矩形の面積）の変化を測定し、これを不変量（例えば、文字凸包内の黒画素と白画素の面積）と共に事例として記憶しておく。そして補正したい画像の各連結成分（多くは単文字に相当）から算出した回転不変量により事例を呼び出し、同じく算出した回転変量から文字の回転角を得る。文書画像44サンプルを用いて、簡単な傾き推定実験を行ったところ、25サンプルにおいて誤差1度以下、42サンプルにおいて誤差2度以下という精度を得た。【選択図】図１
2008252856.tif 000002
【特許請求の範囲】
【請求項１】
幾何学的変形を受けた画像を入力とし、前記画像が受けた変形を補正する方法であって、
入力された画像を局所的なパターンである局所パターンに分割する工程と、
各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出工程と、
算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する工程と、
各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定工程と、
推定結果に基づいて画像を補正する工程とを備え、
各工程をコンピュータが実行することを特徴とする画像の補正方法。
【請求項２】
前記幾何学的変形は、射影変換、アフィン変換もしくは相似変換である請求項１記載の方法。
【請求項３】
前記画像は文書画像であり、少なくとも一部の局所パターンは文字パターンである請求項１または２記載の方法。
【請求項４】
前記幾何学的変形は回転であり、
変量は、局所パターンを回転させることにより変化する値であり、
不変量は、局所パターンを回転させても略一定の値である請求項１〜３の何れか一つに記載の方法。
【請求項５】
前記幾何学的変形は射影変換であり、
変量は、奥行きにより変化する値であり、
不変量は、奥行きの変化に対して略一定の値である請求項１〜３の何れか一つの記載の方法。
【請求項６】
前記変量は局所パターンに外接する矩形の面積である請求項１〜４のいずれか一つに記載の方法。
【請求項７】
前記変量は局所パターンの黒画素部分の面積である請求項１、２、３および５のいずれか一つに記載の方法。
【請求項８】
前記不変量は、局所パターンの凸包内の面積である請求項１〜５のいずれか一つに記載の方法。
【請求項９】
前記局所パターンは画像中の連結成分として分割されるパターン、もしくは、そのパターンの集合である請求項１〜８のいずれか一つに記載の方法。
【請求項１０】
各カテゴリは、そのカテゴリに対する不変量をqc、各局所パターンの不変量をqxとするとき、
【数１】
2008252856.tif 000031
（ただし、εは予め定められた定数）
の関係を満たす局所パターンからなる請求項１〜９の何れか一つに記載の方法。
【請求項１１】
前記推定工程は、各局所パターンから算出される変量と各カテゴリに対応して予め記憶された基準値とを比較して局所パターン毎に変形の程度を仮推定し、仮推定された各結果を統計的に処理して変形の程度を推定する請求項１〜１０の何れか一つに記載の方法。
【請求項１２】
前記基準値は、各カテゴリの標準パターンを段階的に変形させて変量を測定し、各段階の変形量と測定された変量とを対応付けて記憶されたものである請求項１１記載の方法。
【請求項１３】
前記推定工程は、各局所パターンの位置とその局所パターンの変量との関係に基づいて変形の程度をカテゴリ別に仮推定し、仮推定された各結果を統計的に処理して変形の程度を推定する請求項１〜１０の何れか一つに記載の方法。
【請求項１４】
入力された画像は文書画像であり、
前記幾何学的変形は射影変換であり、
変量は、局所パターンの黒画素部分の面積であり、
不変量は、局所パターンの凸包内の面積であり、
前記推定工程は、各局所パターンの黒画素部分の面積とその紙面上の位置との関係に基づいて前記文書画像の紙面の傾きの仮推定を行う請求項５に記載の方法。
【請求項１５】
幾何学的変形を受けた画像を入力としてその画像が受けた変形を補正するためのプログラムであって、
入力された画像を局所的なパターンである局所パターンに分割する処理と、
各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出処理と、
算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する処理と、
各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定処理と、
推定結果に基づいて画像を補正する処理とをコンピュータに実行させることを特徴とする画像の補正プログラム。
【請求項１６】
幾何学的変形を受けた画像を入力としてその画像が受けた変形を補正する装置であって、
入力された画像を局所的なパターンである局所パターンに分割する分割部と、
各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出部と、
算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する分類部と、
各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定部と、
推定結果に基づいて画像を補正する補正部とを備えることを特徴とする画像歪み補正装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、広くは、画像の補正方法、補正プログラムおよび画像歪み補正装置に関する。より詳細には、画像が受けた幾何学的変形を補正する方法、プログラムおよび装置に関する。
【背景技術】
【０００２】
文書画像を対象とする文字認識において、幾何学的な変形（幾何変形）の推定および補償は重要な問題の1つである。ここで、「文書画像」は、画像の一種であって、文書が画像として記録されたものをいう。その一部に写真やイラスト等、文字以外の画像が含まれていてもよい。例えば、スキャナによって取得された文書画像中の文字については、紙面の傾き(スキュー)による回転変形が重要な問題とされてきた。このスキュー補正については、後述のように従来より非常に多くの研究事例がある。
一方、カメラによって取得された文書画像の場合、その画像中の文字が受けている幾何変形はより多様で複雑なものになる（例えば、非特許文献１参照）。例えば、カメラと紙面が正対していないことによる射影変換歪み、紙面自体が平面になっていないことによる非線形な歪みが生じうる。これらの歪みの補正法はdewarpingと呼ばれており、カメラベース文字認識の隆盛と共に、現在活発に研究されている。
【０００３】
デジタルカメラを用いる処理では、スキャナでは起こり得ない非一様な照明やフォーカスのずれ、対象を斜めから撮影したときに生じる射影歪みなどによって画像が劣化するため、一般にスキャナを用いた処理に比べて難しい。しかし、それにも関わらずスキャナに替えてデジタルカメラを用いる理由は、その可搬性や簡便性にある。例えば、スキャナの設置には時間と手間を要するため、手軽に移動したり、持ち歩いたりする用途には適さない。また、ポスターや看板など、大きな物や移動できない物には利用できない。一方、デジタルカメラであれば、思い立ったときに手軽に撮影することができ、これまでにない新しい使用形態に発展する可能性を秘めている。
【０００４】
文書画像の傾き補正法については数多くの研究事例がある。その多くは、文書画像の大局な特徴を利用している。例えば回転角度を変えながら求めた周辺分布を手がかりにした方法はその典型的な例である。一方、局所領域(例えば連結成分)毎に傾き角を推定し、それを画像全体で統合することで、文書画像全体の回転角を推定する方法も幾つか提案されている。以下にそれらを概説する。
【０００５】
まず、非特許文献２では、画像中にある一定の大きさの円の局所領域を取り出し、その円内に引いた直線上の文書の画素値の変化を測定する。角度を変えて直線を引き、その変化が最も大きかった直線の角度方向を局所領域の回転角推定結果とする。また、統合方法としては変化が最も大きかった直線の角度を文書全体の回転角とする。
【０００６】
次に、非特許文献３では、まずある局所領域内の連結成分から特徴点を検出する。各特徴点に対してその最近傍の特徴点３つの間の線分の比較によりおよその回転方向を表す直線を求め、それから微小距離以内にある点を一定数用いて最小２乗近似により最終的な局所回転角を表す直線を求める。この操作を各特徴点についてそれぞれ行い、その結果を投票し、全体としての回転角を求める。
【０００７】
さらに、非特許文献４では、まずある連結成分について、一定の近傍条件を満たす連結成分を結合して拡大連結成分を形成する。次にその中で最遠点となる2画素間に直線を引き、その角度を局所回転角とする。ここでこの近傍条件とは、例えば文字行の直進性を考慮するようなものである。条件を満たす連結成分がない場合は、局所回転角も求められないことになる。以上の処理を各連結成分について行い、複数求めた局所回転角の中央値を全体の回転角とする。
【０００８】
また、文書画像の射影歪み補正は、カメラを用いた文書画像処理における基本的な課題であるため、既に様々な研究が行われている。それらは(1)文書の枠を利用する方法、(2)文書中の文字行を利用する方法、(3)ステレオ視を利用する方法、に大別できる。
【０００９】
(1)の方法は、文書の枠が長方形であり、撮影した文書画像から明瞭に求められることを前提とする。長方形が射影歪みの影響を受ければ、本来平行であるはずの対辺の平行性が失われるため、取得した画像中では一般の四角形になる。ここで四角形が本来長方形であったという情報を用いて長方形に戻るような変換を求めれば、射影歪みを受けた文書画像を正対した画像に復元することができる（例えば、非特許文献５参照）。また、市販のデジタルカメラ(Ricoh Caplio（登録商標） R6等)に実装されている。
【００１０】
(2)の方法は、文字行の平行性を仮定している。例えば、非特許文献５では消失点から傾き具合を推定する手法が提案されている。また、非特許文献５には、(1)の手法と(2)の手法の両方が記載されている。この手法ではまず、文書画像中の文字行を抽出して、文書の横方向の消失点を求める。次に、文字行の両端がほぼ揃っていることを仮定して、文字行の右端、中央、左端の3本の直線を推定し、文書の縦方向の消失点も求める。このように求めた2つの消失点を利用して正対した文書画像を復元する。
(3)は、複数のカメラ（例えば、非特許文献６参照）もしくは動画（例えば、非特許文献７参照）を用いて3次元形状を復元する方法である。
【００１１】
【非特許文献１】黄瀬浩一、大町真一郎、内田誠一、岩村雅一、"ディジタルカメラによる文字・文書の認識・理解" 電子情報通信学会誌、vol.89, no.9, pp.36-841, Sep. 2006.
【非特許文献２】Y.Ishitani, "Document Skew Detection Based on Local Region Complexity," Proc. Int. Conf. Doc. Anal. Recog., pp.49-52, 1993.
【非特許文献３】X.Jiang, H.Bunke，and D.Widmer-Kljajo, "Skew Detection of Document Images by Focused Nearest-Neighbor Clustering," Proc. Int. Conf. Doc. Anal. Recog., pp.629-632, 1999.
【非特許文献４】Y.Lu and C.L.Tan，"Improved Nearest Neighbor Based Approach to Accurate Document Skew Estimation," Proc. Int. Conf. Doc. Anal. Recog., pp.503-507, 2003.
【非特許文献５】P.Clark and M.Mirmehdi, "Recognising text in real scenes," Int'l Journal of Document Analysis and Recognition, vol.4, pp.243-257, 2002.
【非特許文献６】C.H. Lampert, T.Braun, A.Ulges, D.Keysers and T.M. Breuel, "Oblivious document capture and real-time retrieval", Proc. First Int'l. Workshop on Camera-Based Document Analysis and Recognition, pp.79-86, Aug. 2005.
【非特許文献７】池谷彰彦、佐藤智和、池田聖、神原誠之、中島昇、横矢直和、"カメラパラメータ推定による紙面を対象とした超解像ビデオモザイキング、"信学論(D)，vol.J88-D, no.8，pp.1490-1498，Aug. 2005．
【発明の開示】
【発明が解決しようとする課題】
【００１２】
前述したスキュー補正の手法は、いずれも、文書の局所的な直線性を仮定したものである。すなわち、文書画像を構成する成分のうち、近傍の幾つかの連結成分が直線的な文字行を為すといった仮定や、文字には直線的な部分が存在するといった仮定である。しかし、そのような仮定が成り立たない場合もある。即ち、文書画像中の文字が直線状に並んでいない場合がある。あるいは、文字に直線的な部分が存在しない場合である。従って、こうした仮定を使用せずにスキュー補正できる手法が望まれている。
【００１３】
また、文書画像のスキュー補正だけにとどまらず、より自由度の高い幾何変形、即ち、射影変換やアフィン変換などに属する幾何変形を受けた画像の補正にも適用可能な、より普遍性のある手法が望まれている。前述のように、デジタルカメラを用いた文書画像処理は優れたアプリケーションを生み出す可能性がある反面、その実現は容易ではない。その理由は、既存の文書画像処理技術の多くがスキャナで取得した文書画像を対象としていることである。つまり、デジタルカメラで取得した文書画像に既存の技術を適用するにはデジタルカメラで取得した文書画像を変換・補正し、スキャナで取得したかのような画像を得る必要がある。デジタルカメラを用いることによって生じる文書画像の劣化のうち、射影歪み補正する手法が望まれている。すなわち、デジタルカメラで斜めから撮影した文書画像から、スキャナで取得したような正対した文書画像を得ることのできる手法が望まれている。
【００１４】
前述の(1)の方法は、多くの文書の枠が長方形であるという合理的な仮定を用いている反面、枠を含めた文書画像全体の撮影を必要とする。
また、(2)の方法は、文書のレイアウトに強い仮定を課しているため、適用範囲が限定される点に課題がある。特殊なレイアウトのページにはまず適用不可能であり、レイアウトが一般的であっても文書中に図や数式を多く含むページでは文字行の両端の推定は容易でないからである。
【００１５】
上記の(1)と(2)の方法は、レイアウトが複雑(文字行が平行でない)で、かつ枠が画像中に文書の枠が含まれていない画像に対して適用することができない（例えば、図16参照）。
(3)の方法は、一台のスチルカメラを用いて撮影された画像を対象とするものではなく、この発明とは用いる装置の数や種類が異なる。
【００１６】
この発明は、前述したような事情を考慮してなされたものであり、射影変換やアフィン変換、相似変換などに属する幾何変形を受けた画像の補正に適用できる歪み補正手法を提供するものである。
【課題を解決するための手段】
【００１７】
この発明は、幾何学的変形を受けた画像を入力としてその画像が受けた変形を補正する方法であって、入力された画像を局所的なパターンである局所パターンに分割する工程と、各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出工程と、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する工程と、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定工程と、推定結果に基づいて画像を補正する工程とを備え、各工程をコンピュータが実行することを特徴とする画像の補正方法を提供する。
【００１８】
また、異なる観点から、この発明は、幾何学的変形を受けた画像を入力としてその画像が受けた変形を補正するためのプログラムであって、入力された画像を局所的なパターンである局所パターンに分割する処理と、各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出処理と、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する処理と、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定処理と、推定結果に基づいて画像を補正する処理とをコンピュータに実行させることを特徴とする画像の補正プログラムを提供する。
【００１９】
さらに、異なる観点から、この発明は、幾何学的変形を受けた画像を入力としてその画像が受けた変形を補正する装置であって、入力された画像を局所的なパターンである局所パターンに分割する分割部と、各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する算出部と、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する分類部と、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定部と、推定結果に基づいて画像を補正する補正部とを備えることを特徴とする画像歪み補正装置を提供する。
【００２０】
換言すれば、第一の側面におけるこの発明の特徴は、ある特定の幾何変形に対する「変量」と「不変量」のみを利用することで、対象が受けた幾何変形の程度（変形量）を推定する点にある。特定の幾何変形としてスキューすなわち回転を例に取ると、回転により値が変わる特徴量と変わらない特徴量を組み合わせることで回転角度を推定することになる。したがってこの発明では、文字行の傾きや各文字の縦横のストロークの傾きを手がかりとする従来のスキュー補正法とは全く異なるアプローチを取る。
【００２１】
また、第二の側面におけるこの発明の特徴は、第一の側面と異なり、事例に基づいて変形量を推定する点にある。この特徴をまず単純な定式を想定して以下に説明する。今、もし文書中の各文字パターンのカテゴリがわかっていれば、そのパターンに当該カテゴリの標準パターンを回転させながら重ね合わせ、最も重なりが大きかった回転角度がその文字の回転角度の推定値になろう。この単純な方式の場合、様々な角度で回転されている標準パターンをすべて事例とし、文書中の文字パターンを各事例と比べることで、回転角度を推定していると言える。ただしこの単純方式には、回転角の範囲や拡大縮小まで考えると、事例の数が膨大になり、現実的ではないという第１の問題がある。また、文書中の各文字パターンのカテゴリはそもそも不明であり、したがって事例の選出法という第２の問題も残っている。そこで、第1の問題については、変量というスカラー量を事例と用いることで、変形量推定の効率化を図る。第２の問題については、前述の不変量を利用することで、カテゴリが不明であっても事例が参照できるような工夫をする。
【発明の効果】
【００２２】
この発明による文書画像の補正方法は、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する工程と、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定工程と、推定結果に基づいて画像を補正する工程とを備えるので、局所パターンの不変量を用いてそのカテゴリを決定し、そのカテゴリと前記局所パターンの変量とを用いて幾何変形の程度を推定し、推定結果に基づいて画像を補正することができる。したがって、文書画像のスキュー補正だけにとどまらず、より自由度の高い幾何変形、即ち、射影変換やアフィン変換などに属する幾何変形を受けた画像の補正にも適用できる。
また、この発明の補正方法を用いて文書画像のスキュー補正を行えば、文字が直線的な部分形状と並びを持つという、従来一般に利用されてきた仮定が成り立たない場合でも、回転角度を精度よく補正することが可能となる。即ち、文書画像における局所パターンとしての文字が直線状に並んでいなくても、またひらがなのように曲線の多い文字が支配的な場合でも、回転角度を精度よく推定することができる。
【００２３】
また、この発明による文書画像の補正プログラムは、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する処理と、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する推定処理と、推定結果に基づいて画像を補正する処理とをコンピュータに実行させるので、局所パターンの不変量を用いてそのカテゴリを決定し、そのカテゴリと前記局所パターンの変量とを用いて幾何変形の程度を推定し、推定結果に基づいて画像を補正することができる。したがって、文書画像のスキュー補正だけにとどまらず、より自由度の高い幾何変形、即ち、射影変換やアフィン変換などに属する幾何変形を受けた画像の補正にも適用できる。
【００２４】
以下、この発明の好ましい実施形態について説明する。
この発明による補正方法および補正プログラムにおいて、前記幾何学的変形は、射影変換、アフィン変換もしくは相似変換であってもよい。
【００２５】
前記画像は文書画像であり、少なくとも一部の局所パターンは文字パターンであってもよい。
【００２６】
さらに、前記幾何学的変形は回転であり、変量は、局所パターンを回転させることにより変化する値であり、不変量は、局所パターンを回転させても略一定の値であってもよい。
【００２７】
前記幾何学的変形は射影変換であり、変量は、奥行きにより変化する値であり、不変量は、奥行きの変化に対して略一定の値であってもよい。
【００２８】
さらに、前記変量は局所パターンに外接する矩形の面積であってもよい。
あるいは、前記変量は局所パターンの黒画素部分の面積であってもよい。
【００２９】
またさらに、前記不変量は、局所パターンの凸包内の面積であってもよい。
ここで、凸包とは、あるパターン（ここでは、局所パターン）を包含する凸多角形のうち最小面積のものをいう。凸多角形とは、頂部の内角がすべて１８０度未満の多角形をいう。
【００３０】
局所パターンは画像中の連結成分として分割されるパターン、もしくは、そのパターンの集合であってもよい。
【００３１】
また、各カテゴリは、そのカテゴリに対する不変量をqc、各局所パターンの不変量をqxとするとき、
【数１】
2008252856.tif 000003
（ただし、εは予め定められた定数）
の関係を満たす局所パターンからなっていてもよい。
【００３２】
さらにまた、前記推定工程は、各局所パターンから算出される変量と各カテゴリに対応して予め記憶された基準値とを比較して局所パターン毎に変形の程度を仮推定し、仮推定された各結果を統計的に処理して変形の程度を推定してもよい。
【００３３】
さらに前記基準値は、各カテゴリの標準パターンを段階的に変形させて変量を測定し、各段階の変形量と測定された変量とを対応付けて記憶されたものであってもよい。
【００３４】
また、前記推定工程は、各局所パターンの位置とその局所パターンの変量との関係に基づいて変形の程度をカテゴリ別に仮推定し、仮推定された各結果を統計的に処理して変形の程度を推定してもよい。
具体的には、例えば、「変量」として連結成分の面積、「不変量」として面積の比を用いる。これらの値はどのような文書からも計算できる基本的な量であり、簡便に計算できるため、他の手法のように文書の長方形の枠が完全に写っていることや、文書中の文字が直線上に並んでいるなどのレイアウトに関する強い制約を課さない。そのため、図1５に示す特異なレイアウトの文書を始め、幅広い対象に適用することが可能である
【００３５】
入力された画像は文書画像であり、前記幾何学的変形は射影変換であり、変量は、局所パターンの黒画素部分の面積であり、不変量は、局所パターンの凸包内の面積であり、前記推定工程は、各局所パターンの黒画素部分の面積とその紙面上の位置との関係に基づいて前記文書画像の紙面の傾きの仮推定を行ってもよい。
【００３６】
ここで示した種々の好ましい実施形態は、それら複数を組み合わせることもできる。
【発明を実施するための最良の形態】
【００３７】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
≪実施の形態１≫
この実施形態では、まず、この発明の手法を文書画像のスキュー補正に適用する場合を例としてその手順を説明する。なお、補正の結果の定量的・定性的な説明は、実験例１に後述する。
【００３８】
しかし、この発明の技術的思想は、それに限定されるものではなく、射影変換やアフィン変換など、より自由度の高い幾何変形を受けた画像の補正に適用することも原理的に可能である。また、補正の対象は文書画像に限定されず、所定のパターンを含む画像であれば、原理的に適用可能である。一般的な幾何変形および補正対象への拡張については、文書画像のスキュー補正を説明した後に触れる。
【００３９】
1. 変量と不変量の組み合わせによる傾き推定
ここでは、変量と不変量の組み合わせによる幾何変形推定の方法について述べる。前述のように、幾何変形のうち回転を例にとって説明する。また、補正の対象についても文書画像に限定して論ずる。この発明の補正方法を用いて文書画像のスキュー補正を行えば、文字が直線的な部分形状と並びを持つという、従来一般に利用されてきた仮定が成り立たない場合でも、回転角度を精度よく補正することが可能となる。即ち、文書画像における局所パターンとしての文字が直線状に並んでいなくても、またひらがなのように曲線の多い文字が支配的な場合でも、回転角度を精度よく推定することができる。
【００４０】
1-1. 傾き推定の原理
まず、文書画像内に存在しうる文字カテゴリについて、標準パターンを準備する。前述のように、この標準パターンのすべての回転画像を事例として登録しておけば、それらすべてと入力文書画像中の各文字(連結成分)を比較照合し、最も照合した回転標準パターン画像の角度から、文書画像の回転角を推定できる。この力づくの単純方式は、非常に明確ではあるが、明らかに効率が悪い。
【００４１】
そこでこの発明は、回転変量を事例として用いることで効率的な傾き推定を行う。推定を行うための準備段階として、事例の収集を行う。事例の収集を終えたら、その結果を用いて、入力された文書画像の傾きを推定する。なお、理解を容易にするために、ここでの説明では、入力文書画像中のある文字のカテゴリがcとわかっているものと仮定する。(後に述べる手法によりこの仮定は不要になる。)
【００４２】
1-1-1. 事例の収集(学習ステップ)
各カテゴリcの標準パターンを少しずつ回転させながら変量pを測定する。これを回転角θと変量pの関係p=pc(θ)として保存しておく。一種の学習ステップであり、事例の収集段階でもある。カテゴリ集合については、英文書画像の場合、"A"〜"Z"、"a"〜"z"である。
【００４３】
1-1-2. 傾きの推定(推定ステップ)
入力文書画像中の(傾いた)文字パターンxについて変量pxを求める。そのカテゴリをcとすれば、px=pc(θ)を満たすθが、入力文書画像の回転角の候補になる。このθを求めるのは、1次元関数pc(θ)の逆引きテーブルを作っておけばよく、O(1)の少ない計算量で済む。
このように回転変量を使えば、非常に容易に傾き推定が可能になる。以下では、カテゴリcの推定法、推定ステップの詳細、ならびに実際に用いる変量と不変量について述べる。
【００４４】
1-2. 不変量によるカテゴリcの推定
前節では、各文字のカテゴリcがわかっていることを仮定していた。しかし、傾き補正以前の段階でカテゴリcを知ることができるならば、そもそも傾き補正の不要な状況であろう。このため、不確かながら、事例を参照するためのカテゴリの確定が必要になる。
そこで、各文字(連結成分)のカテゴリcを、画像情報から計算される回転不変量qを用いて、回転変形に対してロバストに（安定して確実に）推定することを考える。具体的には、各カテゴリcの標準パターンについて、その回転不変量qcを求めておく。そうして、入力文字xのカテゴリを推定する際は、その文字から回転不変量qxを求め、qx=qcとなるcを求める。文書画像の回転についてqxは不変であるから、原理的には正しいcが求められる。
【００４５】
しかし実際には回転不変量qだけを頼りに文字カテゴリを唯一に絞り込むのは難しい。その難易度は用いる不変量やカテゴリ数、文書画像のノイズなどに因るが、要するに単一の特徴量による文字認識であり、厳密なカテゴリ推定を望むのには無理がある。このため、実際には小数ε（epsilon、イプシロン）を用いて、
【００４６】
【数２】
2008252856.tif 000004
を満たす複数のcをカテゴリ候補として利用することになる。
【００４７】
1-3. 推定ステップの詳細
以上の推定ステップで「候補」という言葉が用いられていることからもわかるように、1文字だけではθを一意に決めることは困難である。これは次の理由による。
【００４８】
第一は、pとθが一対一対応でなく、同じ変量pに複数のθが対応することが多い点にある。したがって1文字では複数の回転角候補が与えられることになる。
第二に、回転角θを変えても変量pがあまり変化しないような場合(関数pc(θ)が平坦になる場合)、変量pの測定誤差にθが鋭敏に反応し、推定値θの信頼性が低くなる。
第三に、前述したように推定されるカテゴリcが複数存在する点である。結局、これら複数のcについて、前節の推定ステップを駆動する他なく、結局複数の回転角の候補が与えられることになる。
【００４９】
そこで文書画像中の複数の文字から推定される角度を投票していき、最も投票結果の多いものを推定結果とする。即ち、統計的手法の一つとして投票処理を適用し、推定結果を得る。文書画像中に異なるカテゴリの文字が複数存在すれば、それだけ異なった事例によって候補が与えられることになり、多くの誤った候補が混入したとしても、それらが誤った一点に集中する可能性は低いと期待される。
【００５０】
以上の推定ステップの処理を、図1を通して具体的に説明する。図１は、文書画像の回転角度を推定する様子を示す説明図である。
ステップ１：まず、入力文書画像中の文字パターンxについて変量px、不変量qxを計算する。
ステップ２：算出されたqxに基づき、
【数３】
2008252856.tif 000005
となるカテゴリを選択する。
ステップ３：px=pc(θ)となる角度、θ1, θ2, θ3にそれぞれ投票する。図１の場合、θ2が2つあるので2回投票する。このような処理を文書画像中の全ての連結成分に対して行い、最も投票数の多かったものをその文書の回転角とする。
【００５１】
事例pc(θ)を基に投票する際、不変量の場合と同様に、pxの誤差に配慮し、
【数４】
2008252856.tif 000006
を満たす範囲のθについてすべて投票する。図2は、上式の関係を満たす回転角度θに対する投票の様子を示すグラフである。ここで留意すべき点は、変量関数pc(θ)の傾きによって投票範囲の大きさが異なることである。
以上のステップで画像の回転角度（傾き）が推定できたならば、その推定結果に応じて対象の文書画像を補正する。つまり、傾きがゼロになるように画像を回転させる。
【００５２】
1-4. 変量と不変量の具体例
この発明では、回転に対する任意の変量と不変量を用いてもよいが、この発明では最も単純なものを用いる。具体的には、変量pとして、文書画像中の1連結成分を回転させることにより変化する値、具体的には外接矩形の面積(図3(a))を用いる。また、不変量qとして、回転させても変化しない値、具体的には凸包内の面積(図3(b))を用いる。図３は、文字「A」を例に、この実施形態における変量／不変量である文字の外接矩形の面積／凸包の面積を示す説明図である。ここで、これらの面積と黒画素の面積の比をとることによりこの変量と不変量を、画像中に占める連結成分の大きさに依らないようにしておく。すなわち、p，q共にスケール不変量としておく。
【００５３】
なお、この明細書で黒画素は、「地」、即ち、背景が白色、局所パターンが黒色であると想定して「黒画素」、「白画素」の語を用いている。しかし、局所パターンと「地」とが識別できれば、それらの色は黒と白に限定されない。例えば、赤色のパターンは、赤色の画素をこの明細書でいう「黒画素」とすればよい。地が黄色の場合は、黄色の画素をこの明細書でいう「白画素」とすればよい。
【００５４】
回転変量pおよび不変量qを改めて式で表すと以下のようになる。
【数５】
2008252856.tif 000007
以上の変量pは、図4のように周期的に変化する。図４は、この実施形態におけるカテゴリ“y"につき、回転角度が-180°から180°の範囲における変量pの値を示すグラフである。そのため、その1周期分、この場合-45°から45°だけが使用可能であり、この実施形態による推定可能な回転角も同様の範囲に限定される。
【００５５】
≪実施の形態２≫
この実施形態では、文書画像の射影歪みをアフィン歪みに補正する場合を例としてその手順を説明する。なお、補正の結果の定量的・定性的な説明は、実験例２に後述する。
この実施形態の説明のために、最初にコンピュータビジョンにおける3次元座標と2次元座標の関係について述べ、その後この実施形態の詳細について述べる。
【００５６】
2.1. カメラ座標系と画像座標系
3次元空間の物体をカメラで対象の物体を撮影するとき、どのように2次元画像が得られるかを考える。図11は、ピンホールカメラをモデルとする座標系と、それを配置し直した座標系（コンピュータビジョンの技術分野で慣用される座標系）とを示す説明図である。
通常、カメラのモデルに図11(a)のようなピンホールカメラを用いる。点Cがピンホールで、物体11から来る光は全てピンホールを通り、画像平面Iに像を結ぶ。点Cを焦点と呼ぶ。また、画像平面Iと焦点Cの距離fを焦点距離、焦点Cを通り画像平面に垂直な直線を光軸と呼び、光軸と画像平面の交点を画像中心cとおく。このモデルでは平行な2線は必ずしも平行線に変換されない。このような変換を射影変換、射影変換による歪みを射影歪みと呼ぶ。また射影変換のうち、平行線を変換したとき平行線であるものをアフィン変換、アフィン変換を受けたときの歪みをアフィン歪みと呼ぶ。
【００５７】
コンピュータビジョンの技術分野では一般に、画像平面を図11(b)のように配置し直して用いる（例えば、徐剛、辻三郎著，「3次元ビジョン」，共立出版，1998年、および、出口光一郎著，「画像と空間」，昭晃堂，1991年参照）。画像平面で画像中心cを原点とし、図11(b)のようにx軸とy軸を持つ座標系を画像座標系と呼ぶ。また、焦点Cを原点、光軸をZ軸とし、画像座標系のx軸、y軸に対応する方向にX軸、Y軸を持つ3次元座標系をカメラ座標系と呼ぶ。カメラ座標系の点(X,Y,Z)Tを画像平面に射影したとき、画像平面の座標系でこれに対応する点(X,Y)Tは
【００５８】
【数６】
2008252856.tif 000008
で求まる。
【００５９】
2.2. 黒画素の面積と奥行き
文書画像中の各文字に注目すると、本来同じ字種であっても位置によって大きさが変化している。例えば、画像中からアルファベットのaのような特定の文字だけを取り出したときを考える。このとき、文字の黒画素の面積は射影歪みによって、カメラから近い方が大きく、遠い方が小さくなる。この面積の変化から文書の奥行き情報を求めることができるので、この実施形態ではこれを基に文書画像の補正を行う。
【００６０】
奥行きと文字の黒画素の面積の関係について求める。紙面13上の同じ種類の文字を選んだときに、それらの中心のZ座標がそれぞれZ1,Z2であるとする。問題を簡単にするため、図12の模式図を用いて奥行きと文字の長さの関係を考える。図12は、傾いた紙面13をカメラから見たときの文字の射影と近似を説明するための説明図である。図12で、取り出した文字の本来の長さをLとすると、このときZ1,≠Z2なので、画像から得られる文字の射影の長さl1，l2は異なっている。それぞれの長さを簡単に求めるため、図12(b)のような近似を行う。つまり、それぞれの中心に画像平面と平行な平面をおき、文字の正射影を得る。紙面13と画像平面のなす角をα、正射影の長さをL'とすると、
【００６１】
【数７】
2008252856.tif 000009
である。従って、式(1)のx座標についてのみ考えれば、
【００６２】
【数８】
2008252856.tif 000010
が得られる。
【００６３】
次に、これらの文字の面積に関しても同様に考える。それぞれの面積がSであり、正射影の面積をS'とすると、
【００６４】
【数９】
2008252856.tif 000011
となる。このとき、画像平面への写像の面積sjは、
【００６５】
【数１０】
2008252856.tif 000012
である。
【００６６】
式(5)より画像平面上の面積は本来の面積に対して、奥行きの2乗に反比例していることがわかる。従って、ある字種の黒画素の面積に注目したとき、j番目の文字の奥行きZjを黒画素の面積sjで表すと、
【００６７】
【数１１】
2008252856.tif 000013
となる。また、焦点距離f、紙面13と画像平面のなす角αは撮影時に決まっているので、それぞれ定数である。
次に各文字の奥行きからカメラ座標系における紙面13の傾きを考える。式(1)よりj番目の文字の座標(Xj,Yj,Zj)Tは、
【００６８】
【数１２】
2008252856.tif 000014
である。ここで、Zを1/f倍したZ'で置き換えた座標系で各座標を表現すると、
【００６９】
【数１３】
2008252856.tif 000015
となり、形の上では未知の定数fを消去できる。画像中の文字は本来同一平面上にあるので、式(7)を用いて各文字の3次元座標を計算し、Z'=aX+bY+cで表される平面に当てはめることで紙面13の傾きが推定できる。詳細は、2.4で述べる。
【００７０】
2.3. 面積比によるクラスタリング
前記項目2.2で述べた、面積から奥行きを推定する方法は文書中に文字が一種類しか存在しない場合にのみ使用できる。しかし、実際の文書中には複数の字種が混在しているため、あらかじめ文字をその種類ごとに分けておく必要がある。字種を判別する方法として、文字認識が考えられるが、射影歪みを受けている場合は処理が難しい。また、ここでは字種を分類できればよく、文字認識のように文字にラベルを付ける必要はない。
【００７１】
そこでこの実施形態では、アフィン変換を受けても変化しない量(アフィン不変量)である面積比を用いた分類を考える。すなわち、文字から2つの領域を得たとき、その2領域の面積比から不変量を得、これを用いて字種を分類する。アフィン不変量は射影変換に対して不変ではないが、局所領域において射影変換をアフィン変換に近似できることから、文字領域のように面積の小さな領域の面積比を射影不変量のように扱うことができる。
【００７２】
字種の判別に面積比が満たすべき条件は次の2つである。
(1) 面積比(面積)を計算する領域は射影変換を受けても同一でなければならない。
(2) 面積比は、字種を十分に判別できなくてはならない。
【００７３】
前記項目(1)について、面積比は不変量であるため、同一の領域から(近似的に)同一の値を算出することができる。しかし、面積を計算する領域が異なれば同一の値を計算することができないため、射影変換に不変な領域抽出法が必要となる。この実施形態では、各領域の凸包が線形変換に対して不変であることを利用する。
【００７４】
前記項目(2)については、異なる字種が偶然同一の面積比を持つ可能性がある。その場合、字種の混同が生じ、紙面の傾きを正しく推定できない。そこで複数の面積比を用い、面積比の判別性能を向上させる。異なる字種から計算した1種類の面積比が偶然近くなる確率に比べて、複数の面積比が偶然同時に近くなる確率は小さいからである。1文字から計算できる面積の種類は限られているため、この実施形態では最近傍の2文字を組み合わせ、2文字から計算した面積を使用する。図13および図14は、選ばれた2文字から変量と不変量とを得る例を示す説明図である。図13に示すように、2文字を選んだとき(この場合は"t"と"h")、文字の黒画素領域と凸包領域から図14(a)〜(e)の5種類の領域が得られる。これらを組み合わせることで、面積比を複数作り出すことができる。得られたm個の面積比はm次元の不変量ベクトルとして用いる。
【００７５】
文書中から取り出された文字の集合(以降クラスタあるいはカテゴリと呼ぶ)を、面積比の近い文字の部分集合に分けることを考える。この実施形態ではクラスタリングにk-means法を用いる。クラスタリングにより得られたそれぞれのクラスタには同じ字種の組が含まれると期待される。以降の処理は2文字毎に行う。
【００７６】
ここでクラスタリングに関して、この実施形態の文字の大きさに関する制約を述べておく。前記項目2.2で述べた、面積と奥行きの関係は、本来の文字の大きさが同じであることを仮定している。しかし、面積比を用いたクラスタリングでは、字形が同じで大きさのみが異なる文字は区別できない。そのため、クラスタ内に異なる大きさの文字が存在すると、文字の大きさの違いが奥行きの変化によるものなのか、本来の大きさが異なることに起因するものなのかの区別ができず、奥行き情報の外乱要因となる。ただし、通常の文書のように、ほとんどの文字が同じ大きさで、見出し部分のような一部分のみが大きな文字である程度であれば、後述するノイズ除去処理で棄却することができるため、問題ないと考えられる。
【００７７】
2.4. 平面への当てはめ
以上のようにクラスタリングを行うと、各クラスタにおいて前記項目2.2で述べた平面への当てはめを考えることができる。紙面の傾きを高精度に推定するためには同一字種が文書中で分散していることが望ましいが、このような状況は必ずしも期待できない。そこで、クラスタ(字種)毎に推定した紙面の傾き情報を統合することを考える。その際に問題になるのは黒画素の面積Sである。前記項目2.2の説明ではSが既知であるとしていたが、実際には未知であり、文字毎に異なる。そこで、それぞれの平面の傾きが等しくなるように、クラスタ毎の黒画素の面積の比も同時に推定することにする。以下でその詳細を述べるが、以降の説明では前記項目2.2におけるS，(Xj,Yj,Zj)T，Z'jにクラスタ番号iを付し、Si，(Xij,Yij,Zij)T，Z'ijとしてそれぞれ用いる。式(6)〜式(8)も同様である。
まず、式(8)は式(6)を利用して、
【００７８】
【数１４】
2008252856.tif 000016
と表すことができる。この式は、各文字の座標(Xij,Yij,Z'ij)を画像から得られるxij,yij,sijを用いて計算できることを意味している。しかし、式(9)中の文字の本来の面積を表すSiと、紙面の傾きαが未知のため、
【００７９】
【数１５】
2008252856.tif 000017
とおき、平面に対する各文字の奥行きの誤差を
【００８０】
【数１６】
2008252856.tif 000018
と定義する。そして、全ての文字の誤差の和
【００８１】
【数１７】
2008252856.tif 000019
【００８２】
を最小にする[Ki]と平面のパラメータa,b,cを求める。ここで、[Ki]には定数倍の任意性があり、各パラメータが一意に 定まらないため、この実施形態ではc=1に固定して[Ki]，a，bを求める。
ただし、平面への当てはめを行う際にはノイズ(外れ値)の影響を考慮する必要がある。ノイズの原因としては、画像中から文字を抽出する際の画像処理の失敗やクラスタリングにおける誤分類、更には2.3で述べた、文書中に同一字種で複数の大きさの文字が存在する場合が考えられる。これらのノイズに対応するために、この実施形態では2種類のノイズ除去を行う。
【００８３】
2種類のノイズ除去は、(A)クラスタ内の外れ値を除去するもの、(B)クラスタ自体を除去するもの、である。(A)については、クラスタごとに平面から各文字までの距離εijを計算し、距離が閾値t1以上の文字を除去する。(B)については、要素数が少ない(t2以下である)クラスタを除去する。そのようなクラスタからは誤った平面が推定される可能性が高いと考えられるからである。
【００８４】
2.5. 紙面の回転
最後に画像中の紙面を回転して、正面に向ける。これは紙面の正面に視点を移すことと等価であるので、傾いた紙面の法線ベクトルを求め、これの延長上に視点を移すことを考える。回転表現には、任意の回転をZ軸周りの回転φ，Y軸周りの回転θ，X軸周りの回転psiの3段階の回転で表すロール・ピッチ・ヨー型の回転変換を利用する。ロール・ピッチ・ヨーを用いた回転行列Rは次式で表される。
【００８５】
【数１８】
2008252856.tif 000020
【００８６】
紙面がZ'=aX+bY+1と表されているとき、Z'=Z/fとおいたので、Z=afX+bfY+fである。その法線ベクトルは(afbf(-f))Tである。従って、このx座標とy座標を0にするようにRを用いて回転変換すればよい。Z軸周りの回転を行わないことを考慮すると、Rの回転角は
【００８７】
【数１９】
2008252856.tif 000021
【００８８】
となる。式(13)は角度の推定に未知パラメータfが必要なことを示している。しかし、現段階ではfを推定していないので、暫定的にf=1とした。この場合、射影歪み補正後に、本来は長方形である図形が平行四辺形になるアフィン歪みが残る可能性がある。
以下、回転後の2次元画像を求める。カメラ座標系の点(Xij,Yij,Zij)Tを回転して得られる点を
【００８９】
【数２０】
2008252856.tif 000022
とおけば、
【００９０】
【数２１】
2008252856.tif 000023
となる。さらにこれを画像平面に射影することによって、回転による2次元画像の座標
【００９１】
【数２２】
2008252856.tif 000024
を得ることができる。
【００９２】
実施形態１と実施形態２とは、補正の対象が異なる。しかし、それだけではなく、事前に学習が必要かどうかという点でも大きく異なる。実施形態１は、字種毎に回転角と変量(文字の外接矩形の面積)の対応をあらかじめ登録しておくので、学習結果との差異が小さくても精度よく補正を行うことができる。ただし、学習の手順と、それを記憶するための記憶部が必要である。また、文書中の文字は全て同じ方向を向いている(回転していない)という仮定を用いている。これに対して、実施形態２は、事前の学習処理やレイアウトに対する仮定を一切用いないで補正をすることができる。従って、多様なレイアウトの様々なフォントに(文字ではないマークの類いにさえ)適用可能である。また、学習結果を記憶するための記憶部が必要ない。さらに、学習対象とされていないフォントからなる文書にも適用することができる。
【００９３】
≪より一般的な幾何変形の推定≫
以上、回転に対する補正および射影歪みからアフィン歪みへの補正を例にとって説明したが、これは他の幾何変形の推定とそれに基づく補正にも応用できる。すなわち、補正したい幾何学的変形の変量と不変量を組み合わせることにより、様々な幾何変形の程度を推定できる。例えば、アフィン変換に対する不変量(当然平行移動・スケール変換・回転にも不変)と、相似変換(平行移動・スケール変換・回転)に不変である量があるとすれば、これら2つの量を組み合わせることによりアフィン変換のうちせん断成分を推定できると考える。
【００９４】
≪実験例１≫
以下の実験例１では、実施の形態１に対応した実験例について述べる。
3-1. 実験試料
スキュー推定の対象は、テキストベースの組版処理システムとして知られるLaTeXで作成された5種類の文書画像D1, D2, D3, D4およびD5である。それら文書の画像を図5に示す。大部分は事例と同じフォントから構成されるが、数式を含む文書もある。これら数式中のイタリックフォントや数学記号については対応する事例がなく、したがって誤推定の要因になりうる。それぞれの文書画像を±30°，±20°，±10°，±5°，±2°，0°で回転させて44個のテスト画像を生成した。図6はその例である。これらのテスト画像に対して左上から順に右下まで1連結成分(多くの場合、単文字)づつ投票を行うこととした。
【００９５】
単一フォント(Times-Roman)の"A"から"Z"、"a"から"z"の52文字それぞれを-45°から45°まで0.1°刻みで変量と不変量を測定して事例を作成した。図7に実際に測定した変量と不変量の例を示す。カテゴリごとに測定した不変量は誤差が生じるので、事例として記憶しておく不変量qcはその平均をとった。
【００９６】
3-2. この発明による傾き補正結果
44枚のテスト画像について傾きを推定した結果をまとめたものを表1に示す。表1のカッコ内の単位は％である。テスト画像の95%を誤差2.0°以下で推定することができた。
【００９７】
【表１】
2008252856.tif 000025
【００９８】
傾き推定の成功例としてテスト画像D1を-2.0°回転させた推定結果を図8のD1(-2°)に示す。図８(a)の推定角度は-1.4°であり、十分な精度で推定できたといえる。
【００９９】
また、図８(b)の縦軸は推定に使用した文字数を表しており、上から下に行く方向で投票が進む。すなわち、推定に利用した文字数が増加する。推定に使用した文字数が増えるに従い推定精度が向上していることが確認できる。しかし、正解角度付近でわずかながら振動が起こっている。これは、図８(a)に示す通り、正解角度付近にほぼ同数の投票が行われているためである。項目1.3で述べたように、pxの誤差を考慮するため、
【数２３】
2008252856.tif 000026
を満たすθに投票している。このため、pxとして常に同じ値が求まったとしても、２εpの幅の分だけ推定角度に曖昧さがでる。その結果、正解角度付近に複数のピークが見られる。
【０１００】
各テスト画像に対する傾きの推定誤差（単位°）を表2に示す。傾き推定誤差の平均は1.4°であった。テスト画像D3，D4のように事例を持たない文字を含む画像でも、大部分の連結成分が事例を持っていれば投票により正しく推定できている。また、D5のような文字が直線上に並んでいないテスト画像の回転角は従来法では推定することが難しいが、この発明では正しく推定できた。
【０１０１】
【表２】
2008252856.tif 000027
【０１０２】
テスト画像D3の傾き20°とD5の傾き-5°とは、誤差が2.0°以上になった。これらの推定結果を図8のD3(20°)，D4(-5°)に示す。前者では全く違った角度に投票しており、後者では正解角度付近で振動している。これには現在の不変量では複数の事例を参照してしまうという共通した原因がある。詳細を以下に示す。
【０１０３】
【表３】
2008252856.tif 000028
【０１０４】
項目1-2で、小数εを用いて、
【数２４】
2008252856.tif 000029
【０１０５】
を満たす複数のcをカテゴリ候補として利用することを説明した。しかし、これにより誤った事例が参照されそれらが間違った角度へ正解の角度以上に投票してしまう場合がある。文書中に最も多く表れる"e"を例にとる。表3に、カテゴリ"e"及びその近辺のカテゴリとその不変量を示している。入力としてx="e"が与えられた場合、表3によると事例として参照されるのは"e"の他に"u"，"n"である。さらに、不変量の測定誤差により"s"まで投票する範囲に入ることがある。結果、誤った角度に多くの投票がなされた。
以上の原因を踏まえて誤差の大きくなった2サンプルについて考察する。テスト画像D3の傾き20°の場合の、入力x="e"における投票の様子は図9のようになっている。20°回転させた文字"e"の変量は同図のpxである。このpxに応じて投票される角度は、斜線部分では1つ、黒色部分では変量が重なっているために2つ投票される。その結果、投票してほしい20°近辺よりも、-11°から-12°に2倍近く投票されることになる。結果、正しい角度よりも誤った角度に多く投票されてしまったと考えられる。
【０１０６】
テスト画像D4の傾き-5°の場合、"e"は正しく投票されていたものの、D4の文書中に占める割合の大きい"t"において先程と同様に誤った角度に投票していた。図10に"t"とその不変量の近辺にあるカテゴリ"b"，"f"，"t"の変量と角度の関係のグラフを示す。pxは入力x="t"の-5°における変量を表している。同図の斜線部分では1ずつ、黒色部分は変量のグラフが2本もしくは3本重なっているためそれぞれ2、3ずつ投票される。その結果、正しい角度の周辺で2、3倍の投票を行っているため、正しい角度の近くで振動してしまった。
【０１０７】
≪実験例２≫
次に、実施形態２の有効性を検証するために実験を行った。実験データには Canon EOS 5D で撮影した、サイズが4,368×2,912の画像を使用した。実験結果の定量評価は今後行うことにして、この実施形態では実験結果を目視で評価した。実施の形態２の手法は文書の枠を必要としないが、今回の実験では手法の効果がわかりやすいように、枠が写っている画像を選んだ。
不変量の組み合わせを考える上で、2文字のうち黒画素の面積が大きい方を「文字大」、面積が小さい方を「文字小」と呼ぶことにする。用いた5種類の不変量の組み合わせは、
【０１０８】
【数２５】
2008252856.tif 000030
【０１０９】
である。不変量ベクトルの次元数が5次元の場合は5種類全て、3次元の場合はi.〜iii.のみを使用する。
図15は、この発明に係る射影歪みの補正の実験結果を示す説明図である。図15は、対象の画像1〜3、それらの画像の補正に用いたパラメータおよび画像1〜3の補正結果を示す。
【０１１０】
クラスタリングとノイズ除去の各パラメータは、クラスタリング結果が最適になるように調節した。図15の「補正前」が元画像である。また、図16は、図15の「画像2」の元画像の詳細を示すものである。「画像2」は、文書中の文字が直線上に並んでいないレイアウトであってもこの発明の手法が適用可能なことを実証するためのサンプルである。
補正結果について、まず未知である焦点距離をf=1としたときの結果を図15に「補正後(f=1)」として示す。理想的には文書の角の直角は復元されないものの、平行線は復元されるはずである。実験の結果、画像1の平行線はほぼ復元されるものの、画像2と画像3では若干の誤差が残った。この主な原因は、平面当てはめの際に外れ値が影響し、パラメータの推定に誤差が生じたことである。
【０１１１】
次に焦点距離fを手動で探索し、ほぼ最適となる値を定めたときの結果を図15に「補正後(fは最適値)」として示す。理想的には、文書の枠の長方形が復元されるはずである。しかし、f=1のときと同様の理由で、この場合も画像1の長方形はほぼ復元されたものの、画像2と画像3では誤差が残った。
【０１１２】
以上のように、実施形態１および実験例１では、ある特定の幾何変形に対する「変量」と「不変量」のみを利用することで変形量を推定し、推定結果に基づいて補正する方法を説明した。特定の幾何変形としてスキューすなわち回転を例に取って、回転により値が変わる特徴量と変わらない特徴量を組み合わせることで回転角度を推定した。その結果、文書画像中の文字が直線状に並んでいなくても、回転角度を推定することが可能となった。また、事例に基づいて変形量を推定した。標準パターンをそのまま事例として用いるのではなく、変量と回転角の関係を標準パターンから求め、それを事例として登録しておくことで、効率のよい変形量推定を可能にした。さらに前述の不変量を利用することで、カテゴリが不明であっても事例が参照できるような工夫をした。
【０１１３】
また、実施形態２および実験例２では、紙面の傾きに対する「変量」と「不変量」を組み合わせることで文書画像の射影歪みを補正する態様を示した。文書画像中の各連結成分に対して、面積を「変量」として、面積比を「不変量」として用いることにより、各連結成分の相対的な奥行き情報を推定することができる。そして、紙面全体の情報を統合することにより、紙面の傾き角度の推定を行う。実施形態２では、連結成分が持つ相対的な情報のみを利用しており、撮影方法やレイアウトに強い制約を用いていないため、多様な文書画像の射影歪みを補正することができる。
実験例２では、本来は長方形である物を平行四辺形に(射影歪みをアフィン歪み程度に)復元できる潜在能力を確認したが、本来の長方形を復元するまでには至っていない。この原因は推定した奥行き情報に定数倍の不確定性が残っていることと、平面の当てはめに誤差が生じていることによる。前者は実施形態２で用いたのとは別の「変量」と「不変量」を利用することで解決できると考えられ、後者はロバスト推定の導入やノイズ除去の精度向上によって解決可能であると思われる。なお、ここでいうロバスト推定とは、この技術分野の用語であって、パラメータの推定に用いるサンプルにその性質が他と異なるもの（いわゆる「外れ値」）が混じっている場合、その影響が極力排除されるような推定方法のことをいう。
【０１１４】
≪装置のブロック構成≫
図17は、この発明の画像歪み補正装置の機能的な構成を示すブロック図である。図17に示すように、この発明の装置は、分割部21、算出部23、分類部25、推定部27および補正部29を備えてなる。この装置を実現するハードウェアの一態様は、パーソナルコンピュータに、この発明の補正プログラムがインストールされたものである。パーソナルコンピュータのCPUがその補正プログラムを実行することによって各ブロックの機能が実現される。即ち、入力された画像を局所的なパターンである局所パターンに分割する処理を前記CPUが実行することによって分割部21の機能が実現される。各局所パターンについて、変形の程度によって値が略一定である不変量と変形の程度に応じて値が変化する変量とを所定の手順に基づいて算出する処理を前記CPUが実行することによって算出部23の機能が実現される。また、算出された不変量に基づいて各局所パターンを複数カテゴリの何れかに分類する処理を前記CPUが実行することによって分類部25の機能が実現される。さらに、各カテゴリの各局所パターンについて算出された変量に基づいてその局所パターンが受けた変形の程度を推定する処理を前記CPUが実行することによって推定部27の機能が実現される。さらにまた、推定結果に基づいて画像を補正する処理を前記CPUが実行することによって補正部29の機能が実現される。
【０１１５】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【図面の簡単な説明】
【０１１６】
【図１】この実施形態において、文書画像の回転角度を推定する様子を示す説明図である。
【図２】この実施形態において、所定の関係を満たす回転角度θに対する投票の様子を示すグラフである。
【図３】文字「A」を例に、この実施形態における変量／不変量である文字の外接矩形の面積／凸包の面積を示す説明図である。
【図４】この実施形態におけるカテゴリ"y"につき、回転角度が-180°から180°の範囲における変量pの値を示すグラフである。
【図５】この実施形態において、実験に使用した文書画像を示す説明図である。
【図６】この実施形態において、実験例として回転させた文書画像の例を示す説明図である。
【図７】この実施形態において、実験例で求めた変量と不変量の回転角度に対する値を示すグラフである。
【図８】この実施形態において、実験例の投票結果と、使用した文字数による推定結果の推移とをそれぞれ縦軸にとり、回転角度を横軸にとったグラフである。
【図９】この実施形態において、カテゴリ"e", "n"および"s"の変量と回転角度との関係を示すグラフである。
【図１０】この実施形態において、カテゴリ"b", "f", "p"および"t"の変量と回転角度との関係を示すグラフである。
【図１１】ピンホールカメラをモデルとする座標系と、それを配置し直した座標系とを示す説明図である。
【図１２】傾いた紙面をカメラから見たときの文字の射影と近似を説明するための説明図である。
【図１３】この実施形態で、選ばれた2文字から変量と不変量とを得る例を示す第１の説明図である。
【図１４】この実施形態で、選ばれた2文字から変量と不変量とを得る例を示す第２の説明図である。
【図１５】この発明に係る射影歪みの補正の実験結果を示す説明図である。
【図１６】図15の「画像2」の詳細を示す説明図である。
【図１７】この発明の画像歪み補正装置の機能的な構成を示すブロック図である。
【符号の説明】
【０１１７】
１１  物体、撮影対象
１３  紙面
２１  分割部
２３  算出部
２５  分類部
２７  推定部
２９  補正部
C  焦点
D1, D2, D3, D4, D5  文書画像
I  画像平面
f  焦点距離
【図４】
2008252856.tif 000032
【図１】
2008252856.tif 000033
【図２】
2008252856.tif 000034
【図３】
2008252856.tif 000035
【図５】
2008252856.tif 000036
【図６】
2008252856.tif 000037
【図７】
2008252856.tif 000038
【図８】
2008252856.tif 000039
【図９】
2008252856.tif 000040
【図１０】
2008252856.tif 000041
【図１１】
2008252856.tif 000042
【図１２】
2008252856.tif 000043
【図１３】
2008252856.tif 000044
【図１４】
2008252856.tif 000045
【図１５】
2008252856.tif 000046
【図１６】
2008252856.tif 000047
【図１７】
2008252856.tif 000048