(57)【要約】      （修正有）【課題】文書画像中の水平線および垂直線を、その線と交わる文字のストロークの全体を保護しながら除去する方法。【解決手段】それぞれの検出された水平線について、垂直なランレングスプロファイルが計算される。間に谷を挟んだ二つの隣り合ったピークを含むランレングスプロファイルの領域が検出され、この領域は垂直線でない線と、水平線との交差点に対応する。そのようなピークおよび谷を検出するために、第一の微分曲線が使用される。連続したピクセル位置に大きなランレングス値をもったランレングスプロファイルの領域も検出され、この領域は垂直に近い線と水平線との交差点に対応する。水平線は、交差領域の内部にあるピクセルが保護されつつ、交差領域の外側にピクセルが除去される。垂直線の除去も同様に実行され得る。このテンプレートのない方法は、表、型における線および下線を除去でき、手書きまたは印刷された文字を抽出できる。【選択図】図１
2015036992.tif 000002
【特許請求の範囲】
【請求項１】
第一の方向に伸延している直線を含む文書画像を処理する方法であって、
（ａ）前記第一の方向に伸延している直線を特定するステップと、
（ｂ）前記直線に対するランレングスプロファイルを計算するステップと、ここで、当該ランレングスプロファイルは前記直線に沿った前記第一の方向における位置の関数としてのランレングス値であり、所定位置における各前記ランレングス値は、前記第一の方向に垂直な第二の方向に伸延して連続する白でないピクセルの数であり、当該白でないピクセルには、前記直線の中にある白でないピクセルが含まれ、
（ｃ）前記ランレングスプロファイルの第一類型の特徴的な形状を検出することによって、前記直線の第一類型の交差領域のセットを検出するステップと、ここで、前記第一類型の特徴的な形状は、一つの谷および前記谷の両側の所定距離内に位置する二つのピークを含み、前記二つのピークおよび前記谷のそれぞれのランレングス値の差が第一の閾値より大きく、
（ｄ）前記ランレングスプロファイルの第二類型の特徴的な形状を検出することによって、前記直線の第二類型の交差領域のセットを検出するステップと、ここで、前記第二類型の特徴的な形状は、ランレングス値が第二の閾値より大きい連続する位置を複数含み、
（ｅ）前記第一および第二類型の交差領域の内部にある線を保護しつつ、前記第一および第二類型の交差領域の外側にある前記直線を除去するステップと、
を含む方法。
【請求項２】
前記ステップ（ｂ）は、
前記直線の中心軸を計算するステップと、
前記中心軸上のピクセルに連なり前記第二の方向に伸延する連続した白でないピクセルの数をカウントすることによって、前記中心軸の各ピクセル位置における前記ランレングス値を計算するステップと、
をさらに含む請求項１に記載の方法。
【請求項３】
前記ステップ（ｃ）は、
ランレングスプロファイルの第一の微分曲線を計算するステップと、
前記第一の微分曲線における上昇ゼロクロスポイントおよび下降ゼロクロスポイントを検出するステップと、
前記上昇ゼロクロスポイントおよび前記下降ゼロクロスポイントをマッチングすることによって、前記第一類型の交差領域を特定するステップと、
をさらに含む請求項１に記載の方法。
【請求項４】
前記ステップ（ｃ）は、
（ｃ１）前記ランレングスプロファイルの第一の微分曲線ｄ（ｉ）を計算するステップと、ここで、ｉは第一の方向における位置であり、
（ｃ２）前記第一の微分曲線上の前記上昇ゼロクロスポイントｊを検出するステップと、
前記ゼロクロスポイントｊは、
ｄ（ｊ）≦０およびｄ（ｊ＋１）＞０、および
ｄ（ｊ＋１）−ｄ（ｊ）＞Ｔ１
を満足し、ここで、Ｔ１は第三の閾値であり、
（ｃ３）前記第一の微分曲線上の前記下降ゼロクロスポイントｋを検出するステップと、
前記ゼロクロスポイントｋは、
ｄ（ｋ）≧０およびｄ（ｋ＋１）＜０および
ｄ（ｋ）−ｄ（ｋ＋１）＞Ｔ２
を満足し、ここで、Ｔ２は第四の閾値であり、
（ｃ４）前記第一類型の交差領域のセットを特定するステップと、
を含み、
前記第一類型の交差領域は、二つの前記下降ゼロクロスポイントが、前記上昇ゼロクロスポイントの両側に所定距離内に位置し、前記下降ゼロクロスポイントと前記上昇ゼロクロスポイントとのランレングス値の差が第一の閾値より大きい場合に、二つの前記下降ゼロクロスポイントの間の領域として定義される請求項１に記載の方法。
【請求項５】
前記ステップ（ｃ１）において、前記第一の微分曲線は、Ｎ点の中心差分、
ｄ（ｉ）＝Ｓ（ｉ＋Ｎ）−Ｓ（ｉ−Ｎ）を用いて計算され、ここで、Ｓはランレングス値であり、Ｎは所定の数である請求項４に記載の方法。
【請求項６】
前記ステップ（ｃ）は、
（ｃ５）前記ランレングスプロファイルの他の第一の微分曲線を計算するために、異なるＮ値を用いて、ステップ（ｃ１）を繰り返すステップと、
（ｃ６）他の第一類型の交差領域のセットを特定するために、前記他の第一の微分曲線を用いてステップ（ｃ２）、（ｃ３）および（ｃ４）を繰り返すステップと、
（ｃ７）前記ステップ（ｃ４）において特定された第一類型の交差領域のセットと、前記ステップ（ｃ６）において特定された第一類型の交差領域のセットとを結合させるステップと、
をさらに含む請求項５に記載の方法。
【請求項７】
前記ステップ（ｃ２）の前に、Ｎ点の中心差分により計算された第一の微分曲線をスムージングするステップをさらに含む請求項５に記載の方法。
【請求項８】
データ処理装置を制御するために、コンピュータ利用可能な一時的ではない媒体に組み込まれるコンピュータ読み取り可能なプログラムコードを含むコンピュータプログラム製品であって、当該コンピュータ読み取り可能なプログラムは、第一の方向に延長している直線を含む文書画像の処理を前記データ処理装置に実行させるように構成され、当該処理は、
（ａ）前記第一の方向に伸延している直線を特定するステップと、
（ｂ）前記直線に対するランレングスプロファイルを計算するステップと、ここで、当該ランレングスプロファイルは前記直線に沿った前記第一の方向における位置の関数としてのランレングス値であり、所定位置における各前記ランレングス値は、前記第一の方向に垂直な、第二の方向に伸延して連続する白でないピクセルの数であり、当該白でないピクセルには、前記直線の中にある白でないピクセルが含まれ、
（ｃ）第一ランレングスプロファイルの第一類型の特徴的な形状を検出することによって、前記直線の第一類型の交差領域のセットを検出するステップと、ここで、前記第一類型の特徴的な形状は、一つの谷および前記谷の両側の所定距離内に位置する二つのピークを含み、前記二つのピークおよび前記谷のそれぞれのランレングス値の差が第一の閾値より大きく、
（ｄ）前記ランレングスプロファイルの第二類型の特徴的な形状を検出することによって、前記直線の第二類型の交差領域のセットを検出するステップと、ここで、前記第二類型の特徴的な形状は、ランレングス値が第二の閾値より大きい連続する位置を複数含み、
（ｅ）前記第一および第二類型の交差領域の内部にある線を保護しつつ、前記第一類型および前記第二類型の交差領域の外側にある前記直線を除去するステップと、
を含むコンピュータプログラム製品。
【請求項９】
前記ステップ（ｂ）は、
前記直線の中心軸を計算するステップと、
前記中心軸上のピクセルに連なり前記第二の方向に伸延する連続した白でないピクセルの数をカウントすることによって、前記中心軸の各ピクセル位置における前記ランレングス値を計算するステップと、
をさらに含む請求項８に記載のコンピュータプログラム製品。
【請求項１０】
前記ステップ（ｃ）は、
ランレングスプロファイルの第一の微分曲線を計算するステップと、
前記第一の微分曲線における上昇ゼロクロスポイントおよび下降ゼロクロスポイントを検出するステップと、
前記上昇ゼロクロスポイントおよび前記下降ゼロクロスポイントをマッチングすることによって、前記第一類型の交差領域を特定するステップと、
をさらに含む請求項８に記載のコンピュータプログラム製品。
【請求項１１】
前記ステップ（ｃ）は、
（ｃ１）ランレングスプロファイルの第一の微分曲線ｄ（ｉ）を計算するステップと、ここで、ｉは第一の方向における位置であり、
（ｃ２）前記第一の微分曲線上の前記上昇ゼロクロスポイントｊを検出するステップと、
前記ゼロクロスポイントｊは、
ｄ（ｊ）≦０およびｄ（ｊ＋１）＞０、および
ｄ（ｊ＋１）−ｄ（ｊ）＞Ｔ１
を満足し、ここで、Ｔ１は第三の閾値であり、
（ｃ３）前記第一の微分曲線上の前記下降ゼロクロスポイントｋを検出するステップと、
前記ゼロクロスポイントｋは、
ｄ（ｋ）≧０およびｄ（ｋ＋１）＜０および
ｄ（ｋ）−ｄ（ｋ＋１）＞Ｔ２
を満足し、ここで、Ｔ２は第四の閾値であり、
（ｃ４）前記第一類型の交差領域のセットを特定するステップと、
を含み、
前記第一類型の交差領域は、二つの前記下降ゼロクロスポイントが、前記上昇ゼロクロスポイントの両側に所定距離内に位置し、前記下降ゼロクロスポイントと前記上昇ゼロクロスポイントとのランレングス値の差が第一の閾値より大きい場合に、二つの前記下降ゼロクロスポイントの間の領域として定義される請求項８に記載のコンピュータプログラム製品。
【請求項１２】
前記ステップ（ｃ１）において、前記第一の微分曲線は、Ｎ点の中心差分、
ｄ（ｉ）＝Ｓ（ｉ＋Ｎ）−Ｓ（ｉ−Ｎ）を用いて計算され、ここで、Ｓはランレングス値であり、Ｎは所定の数である請求項１１に記載のコンピュータプログラム製品。
【請求項１３】
前記ステップ（ｃ）は、
（ｃ５）ランレングスプロファイルの他の第一の微分曲線を計算するために、異なるＮ値を用いて、ステップ（ｃ１）を繰り返すステップと、
（ｃ６）他の第一類型の交差領域のセットを特定するために、前記他の第一の微分曲線を用いてステップ（ｃ２）、（ｃ３）および（ｃ４）を繰り返すステップと、
（ｃ７）前記ステップ（ｃ４）において特定された第一類型の交差領域のセットと、前記ステップ（ｃ６）において特定された第一類型の交差領域のセットとを結合させるステップと、
をさらに含む請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記ステップ（ｃ２）の前に、Ｎ点の中心差分により計算された第一の微分曲線をスムージングするステップをさらに含む請求項１２に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書画像処理に関し、特に、水平、垂直、あるいは他の直線を、それらと交差する文字のストローク（文字の運筆、字画）の連続性を保護しながら、文書画像中から除去する処理に関する。
【背景技術】
【０００２】
文書画像のデジタル処理、すなわち、デジタル画像であって、文書を表現するものにおいて、画像中の水平あるいは垂直線を除去することが求められている。そのような直線の例としては、文章における下線や、表やフォームにおける水平、垂直線がある。例えば、光学文字認識手段（ＯＣＲ）を文書画像に適用して文書中の文字を抽出しようとしたとき、しばしばはじめに下線を取り除くことが求められる。なぜならば、それらは文字を認識する上で、障害となるからである。他の例では、バンクチェックの画像をデジタル処理する場面においても、しばしば種々の線の除去が求められる。当該文書画像は典型的には、スキャンや文書のハードコピーを写真で撮影したものから取得できる。線の検出および除去は、グレースケールの文書画像を二値の文書画像へと変換するプロセスである、二値化の前または、後に実行される。
【０００３】
種々の線の検出および除去の方法が提案されてきた。線要素の検出は、二値画像中において実行され得る。当該方法のカテゴリーは、ランレングス符号化、最小二乗法、ホッフ変換、および隣接する中心点に関して対称である、平坦な線形構造要素をもつ数学的形態を含む。最小二乗法は、ノイズによって多大な影響を受ける。ランレングス符号化は、線要素とみなされる局所的な線形の構造を検出ないし追跡する方法に基づいている。ブロック隣接関係グラフ（ＢＡＧ）は、隣接する水平線が結合されている線形隣接グラフの一般化である。例えば、Ｂｉｎ  Ｙｕ  ａｎｄ  Ａｎｉｌ  Ｋ．  Ｊａｉｎ，  “Ａ  Ｇｅｎｅｒｉｃ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｆｏｒｍ  Ｄｒｏｐｏｕｔ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ＰＡＭＩ，  Ｖｏｌ．  １８，  Ｎｏ．  １１，  １９９６  （ｈｅｒｅｉｎａｆｔｅｒ  “Ｙｕ  ｅｔ  ａｌ．  １９９６”）を参照のこと。しかしながら、ランレングスコードおよびこれの拡張であるＢＡＧ方法は、除去すべき線が結合されていない場合には、しばしうまく機能しない。ＢＡＧを基にしたシステムにおいては、白紙の形文書が、フォームの構造のテンプレートを生み出すために提供される場合に限り、手書きの文字も、機械でプリントされた文字も両方抽出され得る。ホッフ変換は、極めて時間がかかる方法である。なぜならば、画像中の全てのピクセルを、手間のかかる三角法の計算を通して、ホッフパラメータへと変換するからである。
【０００４】
線要素の検出は、グレーレベルの文書画像においても実行され得る。典型的な方法としては、ベクトル化ベースのトレーシング、数学的形態、そして、線要素検出（ＬＳＤ）が挙げられる。ＬＳＤを基にした方法は、文書画像中においてはうまく機能しない。なぜならば、ＬＳＤは勾配フィッティングに基づいているからである。複雑な文章の場の勾配マップは、局所的に線の勾配分布を変更しうる。
【０００５】
多くの既存の線除去方法では、そのような線と交差する手書きあるいはプリントされた文字のストローク（文字の運筆、字画）を完全に保持できない。その結果、時として、線を除去した後の、二値画像において、個別のシンボルが、結合されていないいくつかの分裂した部分に分かれてしまったり、シンボルのある部分が切り取られたりする。線を除去した後で、破壊された文字を元に戻す方法がいくらか試されてきた。たとえば、Ｙｕ  ｅｔ  ａｌ．  １９９６においては、局在化している線、文字と線の分離、および、前記分離の間に破損してしまったストロークの再構築へのアプローチが記載されている。
【０００６】
Ｘｉａｎｇｙｕｎ  Ｙｅ，  Ｍｏｈａｍｅｄ  Ｃｈｅｒｉｅｔ，  Ｃｈｉｎｇ  Ｙ．  Ｓｕｅｎ，  ａｎｄ  Ｋｅ  Ｌｉｕ，  “Ｅｘｔｒａｃｔｉｏｎ  ｏｆ  ｂａｎｋｃｈｅｃｋ  ｉｔｅｍｓ  ｂｙ  ｍａｔｈｅｍａｔｉｃａｌ  ｍｏｒｐｈｏｌｏｇｙ，”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊ．  ｏｎ  Ｄｏｃｕｍｅｎｔ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｒｅｃｏｇｎｉｔｉｏｎ  （１９９９）  （ｈｅｒｅｉｎａｆｔｅｒ  “Ｙｅ  ｅｔ  ａｌ．  １９９９”）においては、線検出のための数学的形態を使用して、バンクチェックから文字を抽出する方法が記載されている。線除去の後に、破損されたストロークは力学的カーネルを用いて回復される。Ｙｅのストローク回復方法においては、破損されたストロークを修復するための、正しい力学的カーネルを見出すために、線およびストロークの交差点の周囲の正しい局所的な位置がわかっていなければならない。しかしながら、局所的な位置は、交差している線とストロークの長さおよび太さに依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、文書画像中の線を除去する方法およびこれに関連する装置に関し、上記関連技術の限定および不利に起因する複数の問題を実質的に解消する。
【０００８】
本発明の目的は、線と交差するストロークを保護しながら、文書画像から直線を取り除く方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の更なる特徴および利点は、後述する発明の詳細な説明により明らかになり、発明の実施形態により更に理解される。本発明の目的および他の利点は、後述する発明の詳細な説明および特許請求の範囲に記載された構造的な特徴から理解され、達成される。
【００１０】
具体化され、広く描写された、これら、および他の目的の少なくとも一つを達成するために、本発明は、特定の方向に拡張された直線を含む文書画像の処理方法を提供する。当該方法は、（ａ）前記第一の方向に延長している直線を特定するステップと、（ｂ）前記直線に対するランレングスプロファイルを計算するステップと、ここで、当該ランレングスプロファイルは前記直線に沿った前記第一の方向における位置の関数としてのランレングス値であり、所定位置における各前記ランレングス値は、前記第一の方向に垂直な第二の方向に伸延して連続する白でないピクセルの数であり、当該白でないピクセルには、前記直線の中にある白でないピクセルが含まれ、（ｃ）第一類型のランレングスプロファイルの第一類型の特徴的な形状を検出することによって、前記直線の第一類型の交差領域のセットを検出するステップと、ここで、前記第一類型の特徴的な形状は、一つの谷および前記谷の両側の所定距離内に位置する二つのピークを含み、前記二つのピークおよび前記谷のそれぞれのランレングス値の差が第一の閾値より大きく、（ｄ）前記第二類型のランレングスプロファイルの第二類型の特徴的な形状を検出することによって、前記直線の第二類型の交差領域のセットを検出するステップと、ここで、前記第二類型の特徴的な形状は、ランレングス値が第二の閾値より大きい連続する位置を複数含み、（ｅ）前記第一および第二類型の交差領域の内部にある線を保護しつつ、前記第一および第二類型の交差領域の外側にある直線を除去するステップと、を含む。
【００１１】
一つの実施例として、前記ステップ（ｃ）は、ランレングスプロファイルの第一の微分曲線を計算するステップと、前記第一の微分曲線における上昇ゼロクロスポイントおよび下降ゼロクロスポイントを検出するステップと、前記上昇ゼロクロスポイントおよび前記下降ゼロクロスポイントをマッチングすることによって、前記第一類型の交差領域を特定するステップと、を含む。一つの実施例として、第一の微分曲線はＮ点の中心差分を用いて計算される。
【００１２】
本発明の他の側面によれば、上記の方法を達成するためのコンピュータプログラムおよびコンピュータプログラムが内蔵されているデータ処理装置を制御するために具備された装置や、コンピュータプログラムが内蔵されたデータ処理装置メモリやストレージ装置といった、非一時的な媒体からなる計算装置からなるコンピュータプログラム製品を提供する。
【００１３】
前述した内容および後述する発明の内容はともに例示的、説明的なものであって、特許請求の範囲に記載されている発明の更なる理解をより促進させるためのものであるということを理解しなければならない。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態による文書画像から直線を検出し、除去する方法の段階を概略的に示す図である。
【図２ａ】手書き文字のストロークと交わる水平な直線を含んだ、グレースケールの文書画像の例を示す図である。
【図２ｂ】本発明の実施形態による方法を用いて、水平線を除去した後の、図２ａから得られた二値画像を示す図である。
【図３ａ】水平の線と文字のストロークの一部分が交差するところを示した文書画像の一部を、より概略的に示す図である。
【図３ｂ】本発明の実施形態による方法を用いて、交差する文字のストロークを保護しつつ、線が除去された後の図３ａの画像の一部を概略的に示す図である。
【図４ａ】水平な線について、垂直なランレングスプロファイルを示す図である。
【図４ｂ】図４ａのランレングスプロファイルから得られた最初の微分曲線を示す図である。
【図５】本発明の実施形態による線が交差する領域を検出する方法を概略的に示す図である。
【図６】本発明の実施形態が実施されうる、データ処理機器を概略的に示す図である。
【図７】従来の方法を用いた直線の除去の例を示す図である。
【発明を実施するための形態】
【００１５】
本発明は、線と交差する文字のストローク（文字の運筆、字画）は保護しつつ、線を検出し、除去する文書画像処理方法を提供する。文書における文字は印刷されたものや、手描きの文字を含んでも良い。線の例として、文章の下線、表およびフォームの線、その他を含む。このような線は垂直もしくは水平に非常に近いため、本願においては、垂直線、水平線と呼称される。しかしながら、これらは、ゆがみや画像処理における他の歪曲のために厳密に水平、垂直とはならないことに留意する。換言すれば、本願および添付した特許請求の範囲においては、「水平線」や、「垂直線」といった用語は、水平成分へ伸びている線および垂直成分に伸びている線や、水平に近い線、垂直に近い線は、例えば、厳密に水平、垂直な線とは１度のずれがあるような線をも、それぞれ含んでいる。例えば、スキャニングや撮影といった造影プロセスから得られた元の画像はしばしば曲がったものや歪みを含んでいる。曲がりを正すことは、文書画像処理において広く使用されている技術であって、事前処理のステップとして、画像処理において導入された曲がりを正すために画像に適用されなければならない。現在入手可能な曲がりを正す技術はたかだか１度の曲がりを正すことしかできない。
【００１６】
下記の説明においては、水平および垂直線の除去に焦点を当てる。しかしながら、後に議論されるように、まず、画像を回転させることで垂直でないものおよび水平でないものを除去することにも、当該方法が使用される。
【００１７】
図１は、本発明の実施形態による真っ直ぐな水平線または垂直線を文書画像から検出し、除去する方法を概略的に示したものである。この方法は、二値化された文書画像に適用される。この方法は３つの段階からなる。まず、線の存在が、たとえば、数学的形態を用いて検出される（ステップＳ１）。既知の方法が、この段階にて適用され得る。次に、局所的なランレングスプロファイルを登用した方法を用いて、文字のストロークと線との交差領域が検出される（ステップＳ２）。最後に、ステップ２から得られた検出結果に基づいて、文字のストロークが保護されつつ、線が除去される（ステップＳ３）。
【００１８】
図１で示されているステップＳ１〜Ｓ３に先立って、文書画像に、当技術分野で一般的なある種の事前処理ステップが施され得る。
【００１９】
これらの段階を、図２ａ〜４ｂで示された例を用いて、下記でより詳細に説明する。下記の説明は、水平な線を例として用いているが、この方法は、適切な修正、例えば、この方法におけるピクセル座標のｘとｙとを変更させることによって、垂直な線にも適用可能である。
【００２０】
図２ａは、グレースケールのオリジナル文書画像の一部の例を示し、３つの水平線が、いくつかの領域に亘り、それぞれの線が、ある手書きの文字と交差した例を示す。図２ｂは、図２ａが二値化された後であって、水平線が図１の方法を用いて除去されたところを示している。図３ａは、水平線３１と文字のストローク／線３２の一部とが交差していることを示している文書画像の部分拡大図である。図３ａにおける破線は、２つの線の、おおよそ中心を表す。簡単のため、文字のストローク部分３２は直線で示されているが、もちろん曲線であってもよいことに留意する。
【００２１】
第一の段階Ｓ１では、線の検出において、数学的形態学が採用され得る。基本的な数学的形態学の作用は、浸食、膨張、開放および閉鎖を含む。水平線を検出するために、固定された長さの均一な線形構造要素（例えば、線の構造の大きさについて、１５０ピクセルが選択される）について、水平的な開放作用が、画像に対して適用される。ホッフ変換、ランレングスコーディング、複数スケールの線検出など、他の線検出方法が用いられてもよい。これらの方法のいくつかは、任意の方向に延長する線を検出でき、それは水平に近いもののみならず、垂直に近い線をも含む。これらの方法の多くはよく知られている。線検出のステップは、文書画像から線を抽出し、抽出された線のみを含んでいる中間画像を生成する。中間画像は、抽出された線と交差する他の線を含んでいない。
【００２２】
線とストロークの交差点の検出（第二の段階Ｓ２）は、図３ａ、４ａ、４ｂを参照して示されている。交差点の検出方法は、検出された水平線のランレングスプロファイルを用いる。垂直なランレングスは、連続する白でない、垂直方向（ｙ方向）のピクセルの数である。水平線の、垂直なランレングスプロファイルは、ここでは垂直なランレングスプロファイルを、線に沿った水平座標ｘの関数として、ランレングス値と、ここでは定義する。垂直方向における白でないピクセルの走査は、線を構成し、（ｙ方向に）連続してつながっている白でない任意のピクセルを含む。交差に巻き込まれていない線に沿った位置ｘにおいて、垂直なランレングスは、一定値を保つ傾向にあり、それは線の高さである（水平線の幅は一般に、線の高さと呼称される）。図４ａは、水平線についての、垂直なランレングスプロファイルを表した図である。この例において、それは図２ａにおいて署名の上に位置する水平線のランレングスプロファイルである。例えば、任意の交点に巻き込まれていない線の要素に対応する要素４１に見ることができる。この線要素についてのこの線の長さはおよそ８ピクセルであり、垂直方向のランレングスの値は７から９ピクセルの間をゆらいでいる。ピクセルのｘとｙ座標の値は、整数値であることに留意する。
【００２３】
他の線（たとえば、文字のストローク）との交点付近の位置ｘにおいては、図３ａに概略的に表されているように、垂直なランレングスの値は、一定の値（線の高さ）からは著しく離れている。図３ａにおいて、たくさんの短い、２つの矢印がついた垂直な線が描かれており、概略的に、様々な位置ｘにおけるランレングスを概略的に示している。ランレングスプロファイルの典型的な性質は次の通りである。交差領域の外側の位置ｘから始めて、ｘが増加すると、ランレングスの値はほぼ一定の値（線の高さ）である。ｘが交差領域の始まりに近づくに連れて、ランレングスの値は急に増加した後、比較的に穏やかに減少してゆき、ｘが交差領域の中心であるとき最小となる。ｘが交差領域の終端につくと、ランレングスの値は急に一定値付近へと戻る。換言すれば、ｘ軸に沿ったランレングスプロファイルは２つのピークとその間の谷を有しており、ピークの外側の傾斜（谷に背を向けているもの）は急であり、内側の傾斜（谷に向かい合っているもの）は比較的なだらかである。図４ａにおいて、４２とラベリングされた挿入ボックスはこの性質を表したランレングスプロファイルの拡大図の一部である。
【００２４】
ランレングスプロファイルのこの性質は、線の交差領域における特徴であるので、交差点を検出するために使用される。図５は、本発明の実施形態による、ストロークを保護しながら、線にそって交差点を検出して、線を除去する方法を概略的に示したものである。この方法は、図１の段階Ｓ２およびＳ３に対応する。図５で示されているこのステップは、段階Ｓ１におけるそれぞれの検出された線に適用される。
【００２５】
検出された線のみを含んでいる中間画像を用いて、形態学的平滑化が、平滑に処理されるべき線に対してまず適用される（ステップＳ５１）。このステップは望ましいが選択的である。そして、線のバウンディングボックスが計算される（ステップＳ５２）。画像オブジェクトのバウンディングボックスは、箱であり、典型的には長方形の形状をしており、画像オブジェクトに境界をつける。中間画像は検出された線のみを含んでおり、他の交差している線を含んでいないので、もし線が厳密に水平であったら、バウンディングボックスは実質的に線の形状を保つ。もし線が厳密に水平でなかったら、バウンディングボックスは線の高さよりも高くなってしまう。そして、多くのサンプル点（すなわち、位置ｘ）が線の高さを推定するために使用される（ステップＳ５３）。好ましくは、サンプル点の数は事前に決定されていて、点は等しく間を空けて線に添って位置するのがよい。それぞれのサンプル点ｘにおける線の高さは、位置ｘにおけるバウンディングボックスのなかにある白でないピクセルの数を数えることで計算される。一つの例として、３０個のサンプル点が使用される。
【００２６】
そして、線の中心軸が計算される（ステップＳ５４）。一般的に言えば、物体の中心軸とは物体の境界上において最も近い点を一つ以上持っている点を全て集めたものである。しかし、特に線が厳密に水平線でない場合には、線の中心軸はピクセルの中心を通らない場合があることに留意する。ここで線の中心軸は真の中心軸に最も近いところに位置するピクセルと定義され得る。そして、もし線がわずかに傾いていれば、中心軸は段差状に形成され得る。中心軸は、線を追跡することで得られる場合がある。再び、中間画像は、分岐をもたない水平線のみを保持しているので、追跡は複雑ではない。２つの線が平行で互いに非常に近くにある場合であっても、中心軸の追跡は線の境界に交差しない。
【００２７】
そして、線の垂直なランレングスプロファイル、すなわち、中心軸に沿ったそれぞれの位置（位置ｘ）における垂直なランレングスの値が計算される（ステップＳ５５）。たとえば、中心軸のピクセルから始めて、上下方向に垂直な、連続に連なる白でないピクセルの数を数えることによって実行される。好ましくは、水平線が垂直線または文字のストロークと交わるような場合に、垂直なランレングスを計算するときには、中心軸の、それぞれ上と下とにある、ｙ座標の上限と下限を、過剰に長いランレングスを避けるために固定しておく必要がある。
【００２８】
そして、ランレングスプロファイル（たとえば、図４ａ）を用いて、交点領域がステップＳ５６１〜５６５において検出される。まず、第一のランレングスプロファイルの微分が、Ｎ点の中心差分を用いて計算される（ステップＳ５６１）  。
【００２９】
Ｎ点の中心差分は以下のように定義される。  
【００３０】
ｄ（ｉ）＝Ｓ（ｉ＋Ｎ）−Ｓ（ｉ−Ｎ）
ここで、Ｓはシグナル（ランレングス）の値であり、ｄは第一の微分、ｉは位置ｘ、そしてＮは所定の数である。Ｎの値は、たとえば、１から１０である。一般的に言えば、交わる線がより垂直に近づくほど、ピークおよび谷は狭くなるので、比較的小さなＮの値が好ましい。
【００３１】
第一の微分を計算するためのより単純な式は、
ｄ（ｉ）＝Ｓ（ｉ＋１）−Ｓ（ｉ）
である。この、より典型的な定義と比較すると、図４ａの挿入ボックス４２で示されているように、本実施形態におけるＮポイントの中心差分は、局所的なノイズを取り除くことを助け、垂直なランレングスプロファイルにおける平坦なピーク頂点を取り扱うのに便利である。もし、上記のより単純な式が使用されるならば、平坦なピーク領域においては、第一の微分は０となり、後で詳しく述べるゼロクロスを検出するのに困難をきたす。
【００３２】
第一の微分を計算する他の方法が使用される場合もあるが、好ましくは、使用される式は、平坦な頂点の効果を減らすか削除するために平均化する形式を有していなければならない。
【００３３】
例えば、スライディングウインドウ平均化を用いて、第一の微分曲線は、好ましくは平滑化される（ステップＳ５２６）。このウインドウサイズは、例えば、６ピクセルである。
【００３４】
図４ｂは、図４ａに示された垂直なランレングスプロファイルの第一の微分曲線を示したものである。この顕著な例においては、第一の微分はＮ＝３のＮ点中心差分を用いて計算される。挿入ボックス４３は、交差領域における第一の微分曲線の拡大領域を示したものである。交差領域における垂直なランレングスプロファイルは２つのピークをもち、その間に谷を有するという形態的特徴を有しているので、この領域における第一の微分曲線は次のような形態的特徴を有している。ゼロレベル付近から始まり、正の値へと急速に上昇し、そして、負の値へと急速に下降しつつ、第一のゼロクロスポイントを通過する。そして第二の正の値へ急速に上昇しつつ、第二のゼロクロスポイントを通過する。そして、第二の負の値へ急速に下降しつつ、第三のゼロクロスポイントを通過し、最終的にはゼロレベル付近へと浮かび上がる。第一および第三のゼロクロスポイント（下降ゼロクロス）はランレングスプロファイルにおけるピークの頂点に対応する。第二のゼロクロスポイント（上昇ゼロクロス）は、谷の底に対応する。
【００３５】
この第一の微分曲線の形態的特徴は、谷を検出するために使用され（ステップＳ５６３）、同じく、ランレングスプロファイルのピークを検出するためにも用いられる（ステップＳ５６４）。具体的には、第一の微分曲線における上昇ゼロクロス（谷に対応する）は、以下の条件を満たす位置ｘ、ｊを見つけ出すことで検出できる。
【００３６】
ｄ（ｊ）≦０  および、ｄ（ｊ＋１）＞０、および、
ｄ（ｊ＋１）−ｄ（ｊ）＞Ｔ１
換言すれば、第一の微分値が、位置ｊ付近において負（または０）から正へと変化し、その地点における第一の微分曲線の傾きが、閾値Ｔ１より大きいことである。閾値Ｔ１の目的は、第一の微分値がゼロの周辺を微小にゆらいでいる交差していない領域における点を除去することである。
【００３７】
第一の微分曲線における下降ゼロクロス（ピークに対応する）は、以下の様な条件を満足するｋの位置にあるｘを探し出すことで検出しうる。
【００３８】
ｄ（ｋ）≧０および、ｄ（ｋ＋１）＜０、および
ｄ（ｋ）−ｄ（ｋ＋１）＞Ｔ２
ここで、Ｔ２は閾値である。
【００３９】
この方法で見出された位置ｊおよびｋは、垂直なランレングスプロファイルにおけるピークおよび谷の位置に対応する。
【００４０】
全ての谷およびピークの位置が見出された後、谷の位置およびピークの位置を適合することで、交差領域の存在が確認できる（ステップＳ５６５）。具体的には、それぞれの谷の位置（上昇ゼロクロスポイント）について、もし２つのピークの位置（下降ゼロクロスポイント）が、谷の左右にそれぞれ、特定の距離の中に存在し、もしピーク位置および谷の位置の間のランレングス値の差が、左右のピークについて、閾値より大きければ、谷および２つの対応するピークは、交差領域であると推察される。この交差領域は、それぞれ、左および右のピーク位置の始まりと終わりであると定義され得る。または、交差領域は、左右のそれぞれのピークに対して所定の数のピクセルを含むものと定義され得る。
【００４１】
前述したとおり、一般的に言えば、Ｎ点の中心差分について、比較的小さなＮの値をとれば、より垂直に近い線の交わりの検出にとってよく機能する傾向にある。また、比較的大きなＮの値をとれば、より水平に近い先の交わりの検出にとってよく機能する傾向にある。典型的な文書について、注意深く選ばれたＮの値（例えば、５）は満足な結果を与えることとなるであろう。線の検出の信頼性および安定性を強化するために、一つの実施例として、ステップＳ５６１〜Ｓ５６５は異なるＮの値、例えばＮ＝３およびＮ＝６をそれぞれ２回ずつ用いて実行され、複数回の実行により、ステップＳ５６５において検出された交差領域が共に結合される（すなわち、検出された交点の複数セットの集合による）。
【００４２】
上述した垂直なランレングスプロファイルおよびその第一の微分曲線の性質の特徴は、水平線が垂直でない線と交わるような交差領域で発生する。水平線が垂直または垂直に近い線と交わる、第二類型の交差領域においては、垂直なランレングスプロファイルは谷および２つのピークを有さない。むしろ、それは多くの長いランレングス値を有する、連続する位置ｘを有し、典型的には、その長さは線の高さの３倍以上となる。前述したとおり、垂直なランレングスを計算する場合、上限および下限が固定されている。すなわち、垂直または垂直に近い線が交わる領域におけるランレングスの値は、上限値および／または下限値と同じ程度の高さが許容される。ランレングスプロファイルにおけるそのような特徴を検出することによって、これらの第二類型の交差領域が検出される（ステップＳ５６６）。
【００４３】
ステップＳ５７において（図１の段階Ｓ３に対応する）、検出された線は除去される。たとえば、２つの類型の交差領域、すなわち、ステップＳ５６５およびＳ５６６において検出された交差領域の外側に位置している線の全てのピクセルに対して、ピクセル値を白に変化させるなどする。交差領域の内部に位置するピクセルについてのピクセル値は保存される。図３ｂは、図３ａにおいて示された線要素に対して線の除去を施した結果を概略的に示したものである。
【００４４】
ここで示された線の検出および除去の方法は、線の位置についての予備知識または予想を必要としない。換言すれば、この方法は表、型、そして下線を除去し、手書きまたは印刷された文字を抽出することに関してのテンプレートを必要としないシステムである。
【００４５】
上述した方法は、垂直線の除去のために修正され得る。たとえば、垂直なランレングスプロファイルの代わりに、垂直線のための水平線のランレングスプロファイルを用いる。
【００４６】
また、この方法は水平線および垂直線の除去に限定されない。この方法は、斜線を除去することにも同様にできる。これを達成するために、線を検出する段階（Ｓ１）において、ホッフ変換方法などといった、任意の方向の線を検出できる方法が用いられる。検出された線の方向が計算されたのちに、斜線を含む画像または画像の一部が、当該斜線が水平（または垂直）線となるように回転される。そして、その回転された画像に対して、交差の検出段階および線の除去段階（図１のステップＳ２およびＳ３、図５におけるステップＳ５１〜５７）が実行される。先が除去された後で、その画像は、元の場所にもどるように回転される。
【００４７】
ここで説明された線の除去の方法は、図６に示されたコンピュータ１２０といった、データ処理システムにおいて実行され得る。コンピュータ１２０は、プロセッサー１２１、ストレージデバイス（例えば、ハードディスクドライブ）１２２、そして、内部メモリ（たとえば、ＲＡＭ）１２３から構成される。ストレージデバイス１２２はソフトウェアプログラムを記録し、この方法を実行するためにＲＡＭ１２３に読み出され、プロセッサー１２１によって実行される。
【００４８】
この技術の分野における当業者においては、本発明の精神および範囲から逸脱することなく、線の除去方法に対して様々な修正や変更を加えることができることは明白である。したがって、本発明は、特許請求の範囲およびこれに均等な範囲における修正および変更を網羅することを意図している。
【図１】
2015036992.tif 000003
【図２ａ】
2015036992.tif 000004
【図２ｂ】
2015036992.tif 000005
【図３ａ】
2015036992.tif 000006
【図３ｂ】
2015036992.tif 000007
【図４ａ】
2015036992.tif 000008
【図４ｂ】
2015036992.tif 000009
【図５】
2015036992.tif 000010
【図６】
2015036992.tif 000011
【図７】
2015036992.tif 000012
【手続補正書】
【提出日】平成26年10月9日(2014.10.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第一の方向に伸延している直線を含む文書画像を処理する方法であって、
（ａ）前記第一の方向に伸延している直線を特定するステップと、
（ｂ）前記直線に対するランレングスプロファイルを計算するステップと、ここで、当該ランレングスプロファイルは前記直線に沿った前記第一の方向における位置の関数としてのランレングス値であり、所定位置における各前記ランレングス値は、前記第一の方向に垂直な第二の方向に伸延して連続する白でないピクセルの数であり、当該白でないピクセルには、前記直線の中にある白でないピクセルが含まれ、
（ｃ）前記ランレングスプロファイルの第一類型の特徴的な形状を検出することによって、前記直線の第一類型の交差領域のセットを検出するステップと、ここで、前記第一類型の特徴的な形状は、一つの谷および前記谷の両側の所定距離内に位置する二つのピークを含み、前記二つのピークおよび前記谷のそれぞれのランレングス値の差が第一の閾値より大きく、
（ｄ）前記ランレングスプロファイルの第二類型の特徴的な形状を検出することによって、前記直線の第二類型の交差領域のセットを検出するステップと、ここで、前記第二類型の特徴的な形状は、ランレングス値が第二の閾値より大きい連続する位置を複数含み、
（ｅ）前記第一および第二類型の交差領域の内部にある線を保護しつつ、前記第一および第二類型の交差領域の外側にある前記直線を除去するステップと、
を含む方法。
【請求項２】
前記ステップ（ｂ）は、
前記直線の中心軸を計算するステップと、
前記中心軸上のピクセルに連なり前記第二の方向に伸延する連続した白でないピクセルの数をカウントすることによって、前記中心軸の各ピクセル位置における前記ランレングス値を計算するステップと、
をさらに含む請求項１に記載の方法。
【請求項３】
前記ステップ（ｃ）は、
ランレングスプロファイルの第一の微分曲線を計算するステップと、
前記第一の微分曲線における上昇ゼロクロスポイントおよび下降ゼロクロスポイントを検出するステップと、
前記上昇ゼロクロスポイントおよび前記下降ゼロクロスポイントをマッチングすることによって、前記第一類型の交差領域を特定するステップと、
をさらに含む請求項１または請求項２に記載の方法。
【請求項４】
前記ステップ（ｃ）は、
（ｃ１）前記ランレングスプロファイルの第一の微分曲線ｄ（ｉ）を計算するステップと、ここで、ｉは第一の方向における位置であり、
（ｃ２）前記第一の微分曲線上の前記上昇ゼロクロスポイントｊを検出するステップと、
前記ゼロクロスポイントｊは、
ｄ（ｊ）≦０およびｄ（ｊ＋１）＞０、および
ｄ（ｊ＋１）−ｄ（ｊ）＞Ｔ１
を満足し、ここで、Ｔ１は第三の閾値であり、
（ｃ３）前記第一の微分曲線上の前記下降ゼロクロスポイントｋを検出するステップと、
前記ゼロクロスポイントｋは、
ｄ（ｋ）≧０およびｄ（ｋ＋１）＜０および
ｄ（ｋ）−ｄ（ｋ＋１）＞Ｔ２
を満足し、ここで、Ｔ２は第四の閾値であり、
（ｃ４）前記第一類型の交差領域のセットを特定するステップと、
を含み、
前記第一類型の交差領域は、二つの前記下降ゼロクロスポイントが、前記上昇ゼロクロスポイントの両側に所定距離内に位置し、前記下降ゼロクロスポイントと前記上昇ゼロクロスポイントとのランレングス値の差が第一の閾値より大きい場合に、二つの前記下降ゼロクロスポイントの間の領域として定義される請求項１または請求項２に記載の方法。
【請求項５】
前記ステップ（ｃ１）において、前記第一の微分曲線は、Ｎ点の中心差分、
ｄ（ｉ）＝Ｓ（ｉ＋Ｎ）−Ｓ（ｉ−Ｎ）を用いて計算され，ここで、Ｓはランレングス値であり、Ｎは所定の数である請求項４に記載の方法。
【請求項６】
前記ステップ（ｃ）は、
（ｃ５）前記ランレングスプロファイルの他の第一の微分曲線を計算するために、異なるＮ値を用いて、ステップ（ｃ１）を繰り返すステップと、
（ｃ６）他の第一類型の交差領域のセットを特定するために、前記他の第一の微分曲線を用いてステップ（ｃ２）、（ｃ３）および（ｃ４）を繰り返すステップと、
（ｃ７）前記ステップ（ｃ４）において特定された第一類型の交差領域のセットと、前記ステップ（ｃ６）において特定された第一類型の交差領域のセットとを結合させるステップと、
をさらに含む請求項５に記載の方法。
【請求項７】
前記ステップ（ｃ２）の前に、Ｎ点の中心差分により計算された第一の微分曲線をスムージングするステップをさらに含む請求項５または請求項６に記載の方法。
【請求項８】
データ処理装置を制御するためのコンピュータプログラムであって、当該コンピュータプログラムは、第一の方向に延長している直線を含む文書画像の処理を前記データ処理装置に実行させるように構成され、当該処理は、
（ａ）前記第一の方向に伸延している直線を特定するステップと、
（ｂ）前記直線に対するランレングスプロファイルを計算するステップと、ここで、当該ランレングスプロファイルは前記直線に沿った前記第一の方向における位置の関数としてのランレングス値であり、所定位置における各前記ランレングス値は、前記第一の方向に垂直な、第二の方向に伸延して連続する白でないピクセルの数であり、当該白でないピクセルには、前記直線の中にある白でないピクセルが含まれ、
（ｃ）第一ランレングスプロファイルの第一類型の特徴的な形状を検出することによって、前記直線の第一類型の交差領域のセットを検出するステップと、ここで、前記第一類型の特徴的な形状は、一つの谷および前記谷の両側の所定距離内に位置する二つのピークを含み、前記二つのピークおよび前記谷のそれぞれのランレングス値の差が第一の閾値より大きく、
（ｄ）前記ランレングスプロファイルの第二類型の特徴的な形状を検出することによって、前記直線の第二類型の交差領域のセットを検出するステップと、ここで、前記第二類型の特徴的な形状は、ランレングス値が第二の閾値より大きい連続する位置を複数含み、
（ｅ）前記第一および第二類型の交差領域の内部にある線を保護しつつ、前記第一類型および前記第二類型の交差領域の外側にある前記直線を除去するステップと、
を含むコンピュータプログラム。
【請求項９】
前記ステップ（ｂ）は、
前記直線の中心軸を計算するステップと、
前記中心軸上のピクセルに連なり前記第二の方向に伸延する連続した白でないピクセルの数をカウントすることによって、前記中心軸の各ピクセル位置における前記ランレングス値を計算するステップと、
をさらに含む請求項８に記載のコンピュータプログラム。
【請求項１０】
前記ステップ（ｃ）は、
ランレングスプロファイルの第一の微分曲線を計算するステップと、
前記第一の微分曲線における上昇ゼロクロスポイントおよび下降ゼロクロスポイントを検出するステップと、
前記上昇ゼロクロスポイントおよび前記下降ゼロクロスポイントをマッチングすることによって、前記第一類型の交差領域を特定するステップと、
をさらに含む請求項８または請求項９に記載のコンピュータプログラム。
【請求項１１】
前記ステップ（ｃ）は、
（ｃ１）ランレングスプロファイルの第一の微分曲線ｄ（ｉ）を計算するステップと、ここで、ｉは第一の方向における位置であり、
（ｃ２）前記第一の微分曲線上の前記上昇ゼロクロスポイントｊを検出するステップと、
前記ゼロクロスポイントｊは、
ｄ（ｊ）≦０およびｄ（ｊ＋１）＞０、および
ｄ（ｊ＋１）−ｄ（ｊ）＞Ｔ１
を満足し、ここで、Ｔ１は第三の閾値であり、
（ｃ３）前記第一の微分曲線上の前記下降ゼロクロスポイントｋを検出するステップと、
前記ゼロクロスポイントｋは、
ｄ（ｋ）≧０およびｄ（ｋ＋１）＜０および
ｄ（ｋ）−ｄ（ｋ＋１）＞Ｔ２
を満足し、ここで、Ｔ２は第四の閾値であり、
（ｃ４）前記第一類型の交差領域のセットを特定するステップと、
を含み、
前記第一類型の交差領域は、二つの前記下降ゼロクロスポイントが、前記上昇ゼロクロスポイントの両側に所定距離内に位置し、前記下降ゼロクロスポイントと前記上昇ゼロクロスポイントとのランレングス値の差が第一の閾値より大きい場合に、二つの前記下降ゼロクロスポイントの間の領域として定義される請求項８または請求項９に記載のコンピュータプログラム。
【請求項１２】
前記ステップ（ｃ１）において、前記第一の微分曲線は、Ｎ点の中心差分、
ｄ（ｉ）＝Ｓ（ｉ＋Ｎ）−Ｓ（ｉ−Ｎ）を用いて計算され、ここで、Ｓはランレングス値であり、Ｎは所定の数である請求項１１に記載のコンピュータプログラム。
【請求項１３】
前記ステップ（ｃ）は、
（ｃ５）ランレングスプロファイルの他の第一の微分曲線を計算するために、異なるＮ値を用いて、ステップ（ｃ１）を繰り返すステップと、
（ｃ６）他の第一類型の交差領域のセットを特定するために、前記他の第一の微分曲線を用いてステップ（ｃ２）、（ｃ３）および（ｃ４）を繰り返すステップと、
（ｃ７）前記ステップ（ｃ４）において特定された第一類型の交差領域のセットと、前記ステップ（ｃ６）において特定された第一類型の交差領域のセットとを結合させるステップと、
をさらに含む請求項１２に記載のコンピュータプログラム。
【請求項１４】
前記ステップ（ｃ２）の前に、Ｎ点の中心差分により計算された第一の微分曲線をスムージングするステップをさらに含む請求項１２または請求項１３に記載のコンピュータプログラム。
【外国語明細書】
2015036992000001.pdf
2015036992000002.pdf
2015036992000003.pdf
2015036992000004.pdf