文書内の表の自動的な位置特定
本発明は、文書内で表を位置特定するための方法であって、文書のための複数のタイルを定義するステップと、タイル毎に水平プロファイルおよび垂直プロファイルを決定するステップと、水平プロファイルおよび垂直プロファイルの勾配を用いて線の位置を検出するステップと、前記線から存続する線を選択するステップと、存続線に基づいて文書の少なくとも１つのコーナ内の矩形を決定するステップと、文書の表として決定された矩形を受け入れまたは拒絶するためにヒューリスティックを適用するステップとを含む、方法に関する。本発明はまた、本発明による方法の適用によって文書内で表を自動的に位置特定するための機器にも関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書内で表を自動的に位置特定するための方法であって、文書のための複数のタイルを定義するステップと、タイル毎に水平プロファイルおよび垂直プロファイルを決定するステップと、プロファイルを用いて線を検出するステップと、少なくとも１つの矩形を線から決定するステップと、少なくとも１つの矩形から文書の表としての矩形を受け入れるステップとを含む、方法に関する。本発明はまた、方法の適用によって文書内で表を自動的に位置特定するための機器にも関する。
【背景技術】
【０００２】
そのような表は、たとえば書式上に存在する表（ここではセルの二次元の組立体である「表」）の全体または部分になり得る。しかしながら、本発明は、製図におけるタイトルブロック（または凡例）の自動的な位置特定に関して特に対象とするものである。本発明の文書では、用語「表」は、前述された例および一般的な表様の構造のすべてを指すために使用される。
【０００３】
本発明の技術は、普通、但し非限定的に、アナログ文書を走査することによって、またはデジタル文書を作成することによって得られるビットマップの形式での文書の表示に適用される。
【０００４】
文書内に存在する表の位置を自動的に検出ことができることが有利である数多くの分野が存在する。１つの例は、書式処理であり、セル内のデータを読み取ることによってデータベース入力が自動的に生み出されるように書式上の表内のセルを自動的に位置特定できることが望ましい。さまざまな提案が、この分野ですでになされてきている。しかしながら、現在利用可能な書式認識コンピュータプログラムの多くは、書式自体からなり、ほとんど他のものからならない画像内の制約されたポーズの書式の認識に頼っている。
【０００５】
自動的な表の位置特定は、特に製図（機械工学図面または建築図面など）を処理する分野を対象とするものである。後者の分野では、図のタイトルブロックが自動的に位置特定され得る場合、以下のプロセスが実現され得る：
タイトルブロックが見えたままになるように図面を自動的に折り畳み、
（タイトルブロックは、一般に、画像に関して指定されたコーナ、たとえば右下に位置特定されるので）正しい向きで図面を配置し、
たとえばパーソナルコンピュータを用いた図面の走査画像の処理において、タイトルブロックは、手動割り付けを助けるために拡大スケールで表示されることが可能であり、かつ
第１のステップが、図面の自動的割り付けで行われ、タイトルブロックが位置特定された時点で、これは、単にその中に含まれた情報を引き出すという問題となる。
【０００６】
製図におけるタイトルブロック（凡例）の内容および配置を管理するさまざまな標準が、国レベルおよび国際レベルで定義されている。これらの標準は、ＩＳＯ５４５７およびＩＳＯ７２００ならびに仏国標準ＮＦ Ｅ０４−５０３を含む。より詳細には、標準は、欧州特許第１２３７１１５号明細書で説明されている。
【０００７】
上記で述べられたタイプの方法は、欧州特許第１２３７１１５号明細書で開示されており、表は、本発明におけるタイルに類似したその小区域の分析によって位置特定される。タイルは、ソリッド矩形、ソリッド三角形、ソリッド六角形または任意の他のソリッド多角形を形成する複数の画素からなる画像の小区域として定義される。ソリッド多角形の画素の数は、タイルサイズとして定義される。欧州特許第１２３７１１５号明細書における分析は、タイル内の画素各列の黒色画素の合計に基づいて水平プロファイルおよび垂直プロファイル、好ましくはソリッド矩形を作成することによって線の位置を決定することを伴う。特定の閾値を上回る長さを有する線が、決定され、グループに割り当てられる。隣接線の組が、その組内の線の隣接する対間の分離が閾値を下回る場合に共通のグループに割り当てられる。矩形は、それがすべての調査された矩形の中で最も多い線を有するグループを含む場合、表の位置としてすべての調査された矩形から選択される。この技術が製図内でのタイトルブロックの位置特定に適用されるとき、文書のコーナまたは端部に対応する矩形が、分析される。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】欧州特許第１２３７１１５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
欧州特許第１２３７１１５号明細書による方法の欠点は、文書のコーナまたは端部だけが、分析されることである。たとえば、文書の大きなマージンの場合、タイトルブロックは、発見されないことがある。さらには、水平プロファイルおよび垂直プロファイルを用いたタイトルブロックの決定は、画像内の各々決定された画素列上の黒色画素の合計に基づく。そのような決定は、連続階調画像には適用可能でない。欧州特許第１２３７１１５号明細書による方法の別の欠点は、タイトルブロックの傾斜効果が、含められないことである。
【００１０】
本発明の目的は、表の位置特定の従来技術の方法固有の問題および欠点を克服することである。より具体的には、本発明の目的は、文書上に存在する特有の表が、確実にかつすばやく位置特定され得るロバストな表の位置特定の方法および機器を提供することである。
【課題を解決するための手段】
【００１１】
本発明の目的は、上記で述べられた種類の方法であって、水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップと、位置特定された線から存続する線を選択するステップと、少なくとも１つの矩形を存続線から決定するステップと、決定された矩形毎に、矩形を文書の表として受け入れまたは拒絶するためにヒューリスティックを適用するステップとを特徴とする方法において達成される。プロファイルの勾配を用いて、局所的極限が検出され得る。極大値、それに続く所定の差違閾値を備えた極小値は、画像内の線の存在をはっきりと表示するものである。そのようにすることにより、方法は、連続階調画像に特に適合される。タイルサイズは、虫食い線または点線に対しても、その結果においていかなる変更も有することなく変更され得る。さらには、この方法は、プロファイルがタイルの縦列または横列内のグレイ値の平均として算出されるとき、ノイズに対してロバストであるが、それというのもノイズは、平均によって平滑化されるからである。
【００１２】
有利な実施形態では、方法は、複数のタイルが、文書の画像の少なくとも一部をカバーし、所定の重複係数で互いに重複し、所定のタイルサイズを有することを特徴とする。より高い重複係数は、方法の精度を高めるが、それというのも連続タイル上の線は、小片に切断されず、小片を線の一部ではなくノイズとして考えることを防止するからである。タイルサイズはまた、方法の精度および性能に影響を及ぼす。タイルサイズの高い値は精度を低下させるが、性能はより良好になる。タイルサイズは、小さいフォーマット、大きいフォーマット、または小さいフォーマットおよび大きいフォーマットの両方に合わせた方法を適用するように調整され得る。
【００１３】
次の実施形態によれば、少なくとも１つの矩形を存続線から決定するステップは、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げるステップを含む。これは、インク領域境界の場合有利である。インク領域境界の内側線は、画像の境界として考えられ得る。
【００１４】
次の実施形態によれば、水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップは、勾配閾値を決定し、勾配における極大値、それに続いて勾配における極小値を決定するために勾配を調べるステップであって、極大値と極小値の間の絶対的差違は、勾配閾値より大きい、ステップを含む。そのようにすることにより、勾配閾値は、文書の表の線となる可能性が低い、それほど極端ではない局所的極限をふるいにかける。
【００１５】
次の実施形態によれば、存続する線を選択するステップは、線の幅に依存する線の存続度を裁定するステップを含む。線の幅が所定の幅を上回る場合、これは、恐らくは線の一部ではなく、ソリッドのフルカラー領域である。
【００１６】
次の実施形態によれば、存続する線を選択するステップは、複数の連続タイルを決定し、連続タイルの数のすべてにおいて線の存在に依存する線の存続度を裁定するステップを含む。そのようにすることにより、小さい線は、文書の表の線になると考えられることから除外される。
【００１７】
次の実施形態によれば、存続する線を選択するステップは、許容値パラメータを決定し、許容値パラメータの値より多い画素によって分離されない連続タイル内の線を、同じ存続線として考えるステップを含む。これは、傾斜線が、文書の表を検出するために検出され考慮に入れられ得るために有利である。
【００１８】
次の実施形態によれば、決定された矩形の受け入れおよび拒絶は、矩形の二次元の高さおよび幅の比によって決まる。文書の可能性のある表として考えられるには、矩形は、容易に読み取り可能で良好に配置された形の複数の標識単語を含むのに十分な二次元的大きさでなければならない。一方向において「薄すぎる」矩形は、文書の可能性のある表として拒絶される。
【００１９】
次の実施形態によれば、決定された矩形の受け入れおよび拒絶は、文書の画像のコーナの少なくとも１つにおける矩形の存在および文書の画像の向きによって決まる。文書の可能性のある表として考えられるには、矩形は、画像の境界に十分近くなければならない。これは、文書の画像の向きによって決まり、文書のコーナは、文書の表を含むことがより好ましい。
【００２０】
本発明は、さらに、上記で述べられた方法の適用によって文書内で表を自動的に位置特定する機器を提供する。方法は、プリンタコントローラの印刷パスおよびコピーパスの両方、ならびに折り畳みサービス向け用途において使用され得る。文書内の表が検出されたとき、畳み込まれた文書の上部に表が位置するように文書を向けるために、文書の画像に回転が適用され得る。
【００２１】
本発明のさらなる特徴および利点は、例として与えられ、添付の図によって示されたその詳細な実施形態の以下の説明から明確になる。
【図面の簡単な説明】
【００２２】
【図１】本発明が使用され得る環境の概略図である。
【図２】図１による写真製版システムの制御ユニットの概略図である。
【図３】文書内で表を検出するための方法のフロー図である。
【図４】文書内で線を検出するためのフロー図である。
【図５】本発明の方法によるタイル内の線検出を示す。
【図６】許容値パラメータを用いて存続線を検出するためのフロー図である。
【図７】重複係数および最小の線長さを伴ったタイリングを示す。
【図８】傾斜補正を用いて存続線を検出するためのフロー図である。
【図９】傾斜補正の例を示す。
【図１０】残りの候補矩形にヒューリスティックを適用するためのフロー図である。
【図１１】ケース１、ケース２、ケース３、ケース４の場合のヒューリスティックの適用を示す。
【発明を実施するための形態】
【００２３】
図１は、本発明が使用され得る環境の概略図である。ここで提示される写真製版システム１は、走査ユニット２、印刷ユニット３、および制御ユニット４を備える。走査ユニット２は、サポート材料上に支持された元のカラー文書を走査するために設けられる。走査ユニットには、反射された光を原色の赤色（Ｒ）、緑色（Ｇ）および青色（Ｂ）に対応する電気信号に変換するＣＣＤタイプのカラー画像センサ（すなわち光電変換装置）が設けられる。ローカルユーザーインターフェースパネル５が、走査およびコピー操作を開始するために設けられる。
【００２４】
印刷ユニット３は、画像サポート上のデジタル画像を印刷するために設けられる。印刷ユニットは、どのような数の印刷技術を使用してもよい。これは、たとえば熱によるまたは圧電性のインクジェットプリンタ、ペンプロッタ、または有機光伝導体技術に基づくプレスシステムでよい。図１に示す例では、印刷は、シアン、マゼンタ、黄色および黒色などの４つの異なる基本インクが設けられた大きいフォーマット用のインクジェットプリンタを用いて達成される。ハウジングは、キャリッジ上に装着された、画像帯を印刷するための印刷ヘッドを含む。画像は、紙ロールによって供給された一枚の紙などのインク受承媒体上に印刷される。ローカルユーザーインターフェースパネル６には、ユーザ、ジョブを選択し、印刷操作などを開始するためのボタンなどの入力手段が設けられる。
【００２５】
走査ユニット２および印刷ユニット３はいずれも制御ユニット４に接続される。制御ユニット４は、入力データを走査ユニット２から受信する、ネットワーク８を介して投入されたデータファイルを取り扱い、スケジューリングする、走査ユニット２および印刷ユニット３を制御する、画像データを印刷可能なデータに変換するなどのさまざまなタスクを実行する。制御ユニットには、タスクを実行し、設定を行うためのコマンドの広範なメニューをオペレータに提供するためのユーザーインターフェースパネル７が設けられる。
【００２６】
さらには、制御ユニットは、同様にネットワークに接続されている複数のクライアントコンピュータ９が、写真製版システム１を利用できるようにネットワーク８に接続される。制御ユニットは、図２により詳細に提示されている。図２に示されるように、写真製版システム１の制御ユニット４は、中央処理装置（ＣＰＵ）４０、ランダムアクセスメモリ（ＲＡＭ）４８、リードオンリメモリ（ＲＯＭ）６０、ネットワークカード４６、インターフェースカード４７、ハードディスク（ＨＤ）５０および画像処理ユニット５４（ラスターイメージプロセッサまたはＲＩＰなど）を備える。上述されたユニットは、バスシステム４２を通して相互接続されている。
【００２７】
ＣＰＵ４０は、ＲＯＭ６０またはＨＤ５０に記憶された制御プログラムにしたがって制御ユニット４のそれぞれのユニット、ローカルユーザーインターフェース７を制御する。ＣＰＵ４０はまた、画像処理ユニット５４も制御する。
【００２８】
ＲＯＭ６０は、起動プログラム、セットアッププログラム、さまざまなセットアップデータまたは類似のものなどの、ＣＰＵ４０によって読み取られ実行されるプログラムおよびデータを記憶する。
【００２９】
ハードディスク５０は、後述される印刷プロセスをＣＰＵ４０に実行させるプログラムおよびデータを記憶および保存するための記憶ユニットの一例である。ハードディスク５０はまた、外部的に投入された印刷ジョブのデータを保存するための領域も含む。ＨＤ５０上のプログラムおよびデータは、必要に応じてＣＰＵ４０によってＲＡＭ４８上に読み取られる。ＲＡＭ４８は、ＣＰＵ４０によってＲＯＭ６０およびＨＤ５０から読み取られたプログラムおよびデータを一時的に記憶するための領域と、さまざまなプロセスを実行するためにＣＰＵ４０によって使用される作業領域とを有する。
【００３０】
インターフェースカード４７は、制御ユニットを走査ユニット２および印刷ユニット３に接続する。
【００３１】
ネットワークカード４６は、制御ユニット４をネットワーク８に接続し、ワークステーション９、およびネットワークを介して到達可能な他のデバイスとの通信をもたらすように設計される。
【００３２】
画像処理ユニット５４は、制御ユニット４上で実行するオペレーティングシステムのソフトウエア構成要素として、またはＦＰＧＬＡ内に具現化されるファームウエアプログラムとして実装され得る。画像処理ユニット５４は、印刷ジョブデータを読み取り、解釈し、ラスタライズするための機能を有する。前記印刷ジョブデータは、印刷される対象の画像データ（すなわちページ記述言語（Ｐａｇｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ）またはそのようなもので表現された、印刷される対象の文書の内容を表現するフォントおよびグラフィック）、画像処理特性、および印刷設定を含む。有利な実施形態では、画像処理ユニット５４は、本発明による方法を実施する。
【００３３】
写真製版システムのオペレーションの基本的形態は、走査、コピー、および印刷である。原色の赤色（Ｒ）、緑色（Ｇ）、および青色（Ｂ）に対応する電気信号が、走査中に得られた状態で、デジタル画像が、ラスター画像ファイルの形式で組み立てられる。ラスター画像ファイルは、一般的に、画素として知られている、定期的にサンプリングされた値の矩形配列になると定義される。各々の画素（画像画素）は、画素に関連付けられた、一般的には画素が表示されるべき色を指定する１つまたは複数の番号を有する。画像の表示は、各々の画素内のＲ、Ｇ、およびＢそれぞれの量を定義する、３つの８ビット（合計２４ビット）の測色値（０〜２５５の範囲）によって指定された各々の画素を有することができる。正しい比率において、Ｒ、Ｇ、およびＢは組み合わされて黒色、白色、２５４の階調、および無数の色（約１６００万色）を形成することができる。走査ユニット２によって得られたデジタル画像は、制御ユニット４のメモリ上に記憶され、コピーパスにしたがって取り扱われ得、この場合画像は、印刷エンジン３によって印刷される。あるいは、デジタル画像は、コントローラからクライアントコンピュータ９に転送されてよい（ファイルを走査するパス）。最終的に、クライアントコンピュータ９のユーザは、システムのオペレーションの印刷モードを反映するデジタル画像を印刷することを決定することができる。
【００３４】
本発明による方法のフロー図が、図３に示されており、これは、複数のステップＳ１０〜Ｓ８０からなる。
【００３５】
方法は、文書のための複数のタイルを定義するステップＳ１０で開始する。文書の画像は、画素からなる。複数のタイルが、画像の画素をカバーしており、次の４つのステップＳ１５、Ｓ２０、Ｓ３０、Ｓ４０において画像内の線を探し、検出するために使用される。
【００３６】
ステップＳ１５では、タイルが選択される。次に、プロファイルが決定される（ステップＳ２０）。決定されたプロファイルに対して、一連の勾配が決定される（ステップＳ３０）。次のステップＳ４０では、線が一連の勾配から検出される。このステップは、さらに図４で詳述される。プロファイルから線が検出された後、次のステップＳ４３において、次のプロファイルが得られるかが確認される。そうである（はいの）場合、方法はステップＳ２０に戻る。そうでない（いいえの）場合、水平および垂直の両方のプロファイルは処理されているため、次のプロファイルは得られず、方法はステップＳ４６に続く。ステップＳ４６では、次のタイルが得られるかが確認される。そうである（はいの）場合、方法はステップＳ１５に戻る。そうでない（いいえの）場合、すべてのタイルが処理されているため、次のタイルは得られず、方法はステップＳ５０に続く。
【００３７】
ステップＳ５０では、複数の連続タイル内の存続線が、検出される。このステップは、図６でさらに詳述される。ステップＳ６０では、存続線が、傾斜補正によって検出される。ステップＳ６０は、先のステップＳ５０で検出された存続線、ならびに一連の勾配によって検出され、先のステップＳ５０で検出された存続線に属さない線に対して適用される。ステップＳ６０は、図８でさらに詳述される。
【００３８】
次のステップＳ７０は、少なくとも１つの矩形の決定であり、最大でも４つの矩形が存続線を形成する。これは、画像のコーナ内の矩形に関する。
【００３９】
最後のステップＳ８０は、文書の表を検出するために、決定された矩形にヒューリスティックを適用するものである。
【００４０】
次にステップＳ１０〜Ｓ８０が、さらに詳細に説明される。方法は、文書のための複数のタイルを決定するステップＳ１０で開始する。文書の画像は、複数の画素からなる。複数のタイルが、画像をカバーしており、線を探し、検出するために使用される。方法は、画像を水平方向および垂直方向にタイルとして切断する。好ましくは各々のタイルは、画素のソリッド正方形であるが、矩形、三角形、六角形などの適切な他の形態を有することができる。タイルに関してここからは、正方形であると仮定する。各々のタイルは、ソリッド正方形の画素数として定義されるタイルサイズを有する。初期値のタイルサイズが定義され得る。大判フォーマット、たとえばＡ０フォーマットでは、５０×５０画素のタイルサイズが、本出願人の実験によって良好な結果を与える。より小さいフォーマットでは、適切なより小さいタイルサイズが、たとえば画像の等価解像度で選択されてよく、Ａ３フォーマットでは、１２×１２画素のタイルサイズが、最適になり得る（１２≒５０／４であることに留意されたい）。最大のタイルサイズ、たとえば画像サイズもまた定義されてよい。タイルサイズは、方法の精度および性能に影響を及ぼす。タイルサイズの高い値は、精度を低下させ得るが、性能はより良好になり得る。タイルサイズの高い値では、タイルの数は低下し、算出の回数は減少し、性能はより良好になる。
【００４１】
次のステップＳ１５は、先のステップＳ１０で定義された複数のタイルからタイルを選択することである。次の３つのステップＳ２０、Ｓ３０、Ｓ４０が、このタイルに適用され、その後、次のタイルが調査される。
【００４２】
次のステップＳ２０は、選択されたタイルのための水平プロファイルを決定するものである。タイル内の各々の画素は、０の白色画素から１の黒色画素に変化するグレイレベルを有することができる。方法の特定の実施形態では、グレイレベルは、２５５段階で０から１まである。タイルの水平プロファイルは、複数の値からなり、各々の値は、タイルの画素横列から算出される。タイルの垂直プロファイルは、複数の値からなり、各々の値は、タイルの画素縦列から算出される。好ましくは、水平プロファイルの値および垂直プロファイルの値は、同じ方式で決定される。水平プロファイルの値は、画素横列内のグレイレベルの総和および画素横列内の画素の総数の商を算出することによって決定されてよい。垂直プロファイルの値は、画素縦列内のグレイレベルの総和および画素縦列内の画素の総数の商を算出することによって同様に決定され得る。このようにすることにより、決定されたプロファイル値は、０から１までの間で変化することができ、プロファイルの値の数は、タイルサイズと等しい。画像がグレイレベルデータからなる場合であっても、プロファイリングの算出は、横列または縦列内の画素のグレイレベルの平均をとることによって確立される。特に、方法はまた、連続階調画像にも適用されてよい。グレイレベルの平均を用いることにより、タイルサイズは、虫食い線または点線であっても、その結果においていかなる変更も有することなく変更され得る。さらには、この方法は、平均によって平滑化されるノイズに対してロバストなものになる。ステップＳ３０、Ｓ４０が水平プロファイルに適用された後、方法はステップＳ１５に戻り、垂直プロファイルがステップＳ２０において決定され、同じステップＳ３０、Ｓ４０が、この垂直プロファイルに対して実行される。プロファイルがステップＳ２０において進められる順番は、タイル毎かつタイル毎に水平プロファイルそれに続いて垂直プロファイルであるが、いかなる影響も及ぼすことなく、タイル毎かつタイル毎に垂直プロファイル、それに続いて水平プロファイルでもよい。
【００４３】
次のステップＳ３０は、調査下のプロファイルに対する一連の勾配を決定するものである。方法によれば、一連の勾配は、一連の一次元の勾配として定義される。各々の一次元の勾配は、画像内の２つの隣接する画素横列の間、または画像内の２つの隣接する画素縦列の間のグレイレベルの変化度として差分商を算出することによってプロファイルの導関数の近似値によって決定される。隣接する画素横列の各々の対に関して、差分商は、水平プロファイルの場合、隣接する画素横列のプロファイル値の差違および隣接する横列の間の距離の商をとることによって算出される。隣接する画素横列の対の差分商は、水平勾配と呼ばれる。垂直プロファイルの場合、差分商は、同様に算出される。隣接する画素縦列の対に対する差分商は、垂直勾配と呼ばれる。隣接する画素横列間の距離および隣接する画素縦列間の距離が１に等しいと推定することにより、差分商は、１で割ることによって算出される。
【００４４】
次のステップＳ４０は、調査下の一連の勾配を用いて文書内で線を検出するものである。線の検出は、図４に示されるフロー図におけるステップを用いてさらに説明される。第１のサブステップＳ４２０は、極大値ｌｍａｘ、それに続いて極小値ｌｍｉｘまたはその逆のすべての出現を一連の勾配において見つけるものである。一連の勾配は、極大値ｌｍａｘ、それに続いて極小値ｌｍｉｘまたはその逆を含むことができ、これは、画像内の線の存在を示すことができる。線の存在を評価するために、勾配閾値ｔｈｒｇｒａｄが、方法のための入力パラメータとして導入される。代替の実施形態では、勾配閾値ｔｈｒｇｒａｄは、一定のハードコード化されたパラメータとして実装される。次のステップＳ４２５では、１つの極大値、それに続いて極小値、またはその逆の出現が見つけられたかが確認される。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。出現が見つけられた（はいの）場合、次のサブステップＳ４３０は、そのような出現を選択するものである。出現の選択の後、次のサブステップＳ４４０は、極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値と勾配閾値ｔｈｒｇｒａｄを比較するものである。極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値が、勾配閾値ｔｈｒｇｒａｄより大きい（はいの）場合、線の存在が想定され、この線は、文書内の表の線の候補になり得る。そのような勾配閾値ｔｈｒｇｒａｄの最小値、最大値、および初期値は、それぞれ０、タイルサイズ値の平方根の２倍、およびタイルサイズ値の平方根になり得る。矩形の形態のタイルの場合、水平プロファイルの最小値、最大値、および初期値は、垂直プロファイルの最小値、最大値、および初期値それぞれとは比例的に異なり得る。極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値が、勾配閾値ｔｈｒｇｒａｄより大きくない（いいえの）場合、線の存在は想定されない。次のステップＳ４６５では、得られる次の出現が存在するかが確認される。そうである（はいの）場合、方法は、同じ一連の勾配において、極大値、それに続いて極小値またはその逆の次の出現を選択するステップ４３０に戻る。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。
【００４５】
線の存在が推定される場合、次のサブステップＳ４５０において、プロファイル内の最大の位置Ｘｍａｘおよび最小の位置Ｘｍｉｘが決定され、この位置は、タイル内の可能性のある線の位置に関連する。画像内のタイルの位置は、画像内のタイルのオフセット情報が保存されている場合に容易になり得る。一連の勾配における最大の位置Ｘｍａｘと最小の位置Ｘｍｉｘの間の距離は、線の幅になると想定される。一連の勾配を介して検出された線は、線の幅が最大の線幅ｌｗｍａｘ未満である場合、表の一部であると想定され得る。したがって、サブステップＳ４５０では、線幅が、最大の線幅ｌｗｍａｘと比較される。極小値ｌｍｉｘの位置Ｘｍｉｘおよび極大値ｌｍａｘの位置Ｘｍａｘの差違が、最大線幅ｌｗｍａｘより小さい（はいの）場合、線の存在が検出され（Ｓ４６０）、この線は、文書内の表の線の候補になり得る。最大線幅ｌｗｍａｘは、方法の入力パラメータになり得る。代替の実施形態では、最大線幅ｌｗｍａｘは、一定のハードコード化されたパラメータとして実装される。方法は、サブステップＳ４６５に続く。極小値ｌｍｉｘの位置Ｘｍｉｘおよび極大値ｌｍａｘの位置Ｘｍａｘの差違が、最大線幅ｌｗｍａｘより小さくない（いいえの）場合、線の存在は検出されない。方法は、サブステップＳ４６５に続く。
【００４６】
サブステップＳ４６５において、得られる次の出現が存在するかがチェックされる。そうである（はいの）場合、方法はサブステップＳ４３０に戻る。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。
【００４７】
最大線幅ｌｗｍａｘは、０からタイルサイズの間で変化することができ、この場合０に等しい値およびタイルサイズに等しい値は除外される。最大線幅ｌｗｍａｘの初期値、たとえば３０が５０×５０画素のタイルサイズで使用されてよい。この最大線幅ｌｗｍａｘを用いることにより、ソリッド黒、グレイ、または他のフルカラー領域は、線検出から除外される。
【００４８】
図４のフロー図によって説明された線検出の適用の例が、図５に示されている。表の検出のために画像分析を開始する際、画像は、所定のタイルサイズのタイルに分割される。タイル毎に、オフセットが画像の所定の原点に対して算出される。図５によれば、タイル１０は、８×８画素のタイルサイズを備えて示されている。タイル１０は正方形の画素であるため、タイル内の画素の総数は、８×８＝６４画素に等しい。８×８画素のタイルサイズは、水平プロファイルおよび垂直プロファイルの原理を実証するために選択される。実際には、より大きいタイルサイズ、たとえば５０×５０画素が使用されてよい。タイル１０は、８列の横列Ｒ１〜Ｒ８を含む。タイル１０はまた、８列の縦列Ｃ１〜Ｃ８を含む。一部の画素１１、１２、１３は、白色にされ、一部の画素１４、１５は、黒色にされる。白色画素は、数字０によってデジタル化される。黒色画素は、数字１によってデジタル化される。この例におけるタイル内の数字は、０および１であるが、一般的に数字は、０から１の間のどのような数でもよい。これはグレイレベルデータおよび連続階調画像の場合有用である。水平プロファイル１Ｈを確立するために、各々の横列の画素値の総和が決定される。垂直プロファイル１Ｖを確立するために、各々の縦列の画素値の総和が決定される。水平プロファイル１Ｈは、横列Ｒ１〜Ｒ８に対して０、０、８、１、１、１、１、１の値それぞれを含む。垂直プロファイル１Ｖは、縦列Ｃ１〜Ｃ８に対して１、１、１、１、６、１、１、１の値それぞれを含む。このとき垂直プロファイルおよび水平プロファイルの一連の勾配が、線を検出するために使用される。水平プロファイルの一連の勾配は、隣り合う水平プロファイル値およびタイルの対応する隣り合う画素横列の距離の差分商をとることによって算出される。垂直プロファイルの一連の勾配は、隣り合う垂直プロファイル値およびタイルの対応する隣り合う画素縦列の距離の差分商をとることによって算出される。２つの隣り合う縦列間の距離が１に設定され、２つの隣り合う横列間の距離もまた１に設定されることが推定される。
【００４９】
水平プロファイルの差分商は、０／１、８／１、−７／１、０／１、０／１、０／１、０／１である。第２および第３の差分商が絶対的に大きく、値８の極大値、それに続いて値−７の極小値が、第２および第３の差分商において検出される。これは、タイル１０内の第３の横列Ｒ３における極大値を指しており、この極大値は、タイル１０内の第３の横列Ｒ３内に線または線の一部が存在することを示すものである。線の存在をこうして表示させることを本方法の適用において現実にするために、たとえばタイルサイズの平方根に等しい８の勾配閾値が導入される。極大値および極小値の絶対差違が、勾配閾値より大きい場合、線の存在が想定される。水平プロファイルにおけるこの場合、絶対差違は、８−（−７）＝１５であり、これは８に等しい勾配閾値より大きく、そのために水平線が存在すると考えられる。
【００５０】
垂直プロファイルの差分商は、０／１、０／１、０／１、５／１、−５／１、０／１、０／１である。第４および第５の差分商が、絶対的に大きく、値５の極大値、それに続いて値−５の極小値が、第４および第５の差分商において検出される。これは、タイル１０内の第５の縦列Ｃ５における極大値を指しており、この極大値は、タイル１０内の第５の縦列Ｃ５内に線または線の一部が存在することを示すものである。極大値および極小値の絶対差違が、勾配閾値より大きい場合、線の存在が想定される。垂直プロファイルにおけるこの場合、絶対差違は、５−（−５）＝１０であり、これは８に等しい勾配閾値より大きく、そのために垂直線が存在すると考えられる。
【００５１】
タイルサイズに関連して小さい線は、勾配閾値のために失われる。そのような線は、勾配閾値より小さいプロファイル値を有し、線よりもノイズとして考えられる。線として考えられるために、たとえば垂直または水平の平坦線を反映するデータ（垂直プロファイル値は、垂直平坦線の場合、タイル内の横列の数と等しく、水平プロファイル値は、水平平坦線の場合、タイル内の縦列の数に等しい）は、タイル上で一貫していなければならない。より少ない検出線でより大きい勾配閾値と数多くの検出された線でより小さい勾配閾値との間でバランスをとるために、最適値が、勾配閾値に対して選択される（多すぎるノイズは線として考えられる）。（正方形タイルの場合）タイルサイズの平方根に等しい勾配閾値が、良好な結果を与えることを経験が明らかにしている。
【００５２】
プロファイルにおける極大値と極小値の間の距離は、線幅を与える。この場合、第３の横列Ｒ３内の検出された水平線に対する線幅は、第５の縦列Ｃ５内の検出された垂直線の線幅と同様に１に等しい。画像内の水平線または垂直線の位置は、画像内のタイルのすでに算出されたオフセット値のために容易に計算可能である。追加の試験が、検出された線幅に関連して導入され得る。線の幅は、最大の線幅入力パラメータ未満、本発明ではたとえば６になり得る。タイル１０内の水平線ならびに垂直線の線幅は、１に等しく、６に等しい最大の線幅入力パラメータ未満であるので、検出された線は、方法のさらなるステップに対する適切な線であると考えられる。
【００５３】
方法における次のステップＳ５０は、複数の連続タイル内で存続線を検出することである。このステップは、図６のフロー図に示されるサブステップＳ５１０〜Ｓ５３０によって説明される。表の線は、所定の最小長さを有するため、表の線が、１つのタイルまたは複数の連続タイル内に検出されるかはタイルサイズによって決まる。しばしば連続タイル内に出現する表の線が、検出される。これは、水平方向の連続タイルならびに垂直方向の連続タイル内になり得る。各々のタイル内の小さい線は、連続タイル内に存在するより小さい線からなる、より大きい線の一部になり得るため、ステップＳ５０は、複数の連続タイルを決定し、連続タイルの数のすべてにおいて線の存在に依存する線の存続度を裁定するステップを含む。
【００５４】
方法の精度を向上させるために、タイリングが、タイルが重複するような方式で行われ得る。０から１の間で変わり得る重複係数は、重複度を決定する。０に等しい重複係数は、連続タイル間に重複が存在しないことを示す。連続タイルの完全な重複を決定する１に等しい重複係数は、除外されてよい。重複係数の初期値は、０．５になり得、これは、タイルの半分が、連続タイルによって一方向に重複されていることを意味する。好ましくは、重複は、画像の水平方向ならびに垂直方向に起こる。
【００５５】
すべてのタイルが、先のステップＳ１５、Ｓ２０、Ｓ３０、Ｓ４０において分析されたとき、すべての検出された線ｌ１〜ｌｍが、ステップＳ５０において調べられる。十分に長い線が、保持される。短い線は、文書の表になるのに十分な大きさの矩形の一部にはなり得ない。存続線だけが、レース内に保持され得る。存続線は、連続タイルの特定の数ｎｃｏｎｓｅｃ内で検出されたものである。この数ｎｃｏｎｓｅｃは、方法の入力パラメータになり得、タイルの重複係数によって変わる。代替の実施形態では、数ｎｃｏｎｓｅｃは、一定のハードコード化されたパラメータとして実装される。複数の水平の連続タイルの同じ横列内で出現する複数の線は、同じ水平の存続線になると考えられる。複数の垂直の連続タイルの同じ縦列内で出現する複数の線は、同じ垂直の存続線になると考えられる。したがって、サブステップＳ５１０では、線ｌ１〜ｌｍが、ｍｉ個の連続タイル内でｋ個の線のグループにグループ化される。線のグループ毎に、数ｍｉが、次のサブステップＳ５２０において数ｎｃｏｎｓｅｃと比較される。数ｍｉが、数ｎｃｏｎｓｅｃより大きい、またはこれと等しい場合、ｉ番目のグループの線は、サブステップＳ５３０で示されるように存続線を形成する。ｋ個のグループの線をすべて調べた後、複数の存続線が検出され、これは、文書の表の一部となる候補になる。
【００５６】
図７では、第１の矢印ＯＦによって示された重複係数で互いに重複する５つの連続タイルＴ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５が、示されている。この特定の場合、重複係数は、０．５に等しい。８×８画素に等しいタイルサイズの場合、重複は、４列の画素縦列である。５つの連続タイルＴ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５は、各々３×８＝２４画素の横列を含む。存続線を想定するための連続タイルの数ｎｃｏｎｓｅｃが、５に等しい場合、検出された線の最小の総サイズは、２４画素である。これはまた、図７の第２の矢印ＭＬによって示されるように最小の線長さとも呼ばれ得る。
【００５７】
方法の次のステップＳ６０は、傾斜補正を用いて存続線を検出することである。このステップＳ６０のサブステップＳ６１０〜Ｓ６５０が、図８に示されており、ステップＳ５０において検出された存続線に適用され、また、ステップＳ４０においてすでに検出されており、ステップＳ５０において存続線として検出されていない線にも適用される。
【００５８】
プロファイルが、タイリングを用いて計算され、タイルの重複が、画像内で線を検出するために適用されるため、画像内の傾斜効果が、補正され得る。許容値パラメータｔｐの値ｖｔｐは、傾斜効果を補正するための方法の入力パラメータである。代替の実施形態では、許容値パラメータｔｐの値ｖｔｐは、一定のハードコード化されたパラメータとして実装される。毎回調査される線から、水平の隣接タイル内の線の対または垂直の隣接線内の線の対が、第１のサブステップＳ６１０で選択される。２本の選択された隣接線が一方向に異なる画素の数ｎｐｉｘｅｌが、次のサブステップＳ６２０において決定される。画素の数ｎｐｉｘｅｌは、次のサブステップＳ６３０において許容値パラメータｔｐの値ｖｔｐと比較される。画素の数ｎｐｉｘｅｌが、許容値パラメータｔｐの値ｖｔｐ未満またはこれと等しい場合、２本の隣接線は、次のサブステップＳ６４０においてそれぞれ同じ水平または垂直の存続線であると考えられる。次のサブステップＳ６５０では、隣接線のすべての対が調査されたかが確認される。そうでない場合、先のサブステップＳ６１０、Ｓ６２０、Ｓ６３０が、繰り返される。そのような許容値パラメータｔｐの初期設定値ｖｔｐは、５になり得る。利点は、そのような許容値パラメータｔｐが、ネーティブファイルならびに走査されたファイル上に適用され得ることである。このようにして、走査に対する潜在的なスキューエフェクトが、考慮に入れられる。
【００５９】
傾斜効果の補償は、図９ａから図９ｄに示されるように潜在的なスキューエフェクトを考慮に入れるために適用される。傾斜効果を考慮に入れるために、許容値パラメータｔｐが、先のステップにおいて検出された存続線の位置に適用される。傾斜効果の補償は、それまで検出された線のすべてに適用され、ここからその長さおよび位置が知られる。したがって画像全体が、考慮に入れられる。図９ａは、傾斜した矩形３１を含む画像３０を示している。この傾斜した矩形３１を用いて、傾斜効果の補償がどのようにして局所的に働くかが示されている。傾斜した矩形３１の傾斜線３３の対象の第１の領域３２（領域３２が垂直および水平の両方向の複数の隣接タイルからなる）の画素レベルに注目すると、図９ｂに示されるようにより小さい（垂直）線３４、３５、３６が検出される。線３４、３５、３６は、各々１つまたは複数のタイル上を延びることができる。図９ｂは、傾斜線３３の一部が、（黒色）画素の３本の垂直線３４、３５、３６からなることを示している。垂直線３４、３５、３６は、３画素未満分離される。許容値パラメータｔｐが、３に等しい、またはそれ以上になる場合、垂直線３４、３５および３６は、図９ｃに示された同じ存続線３７の一部であると考えられる。上側線３４の位置は、傾斜効果の補償のための基準位置になると想定される。この基準位置は、点線３４Ａで示されている。矢印３８は、下側線３５、３６が、上側線３４の下方から点線３４Ａによって示された基準位置にシフトされる傾斜効果の補償を示している。第１の領域３２の下方の次の領域が、次に調査される。最低線３６から３画素未満分離された隣接線が、この次の領域内で検出された場合、これらの線もまた、基準位置３４Ａにシフトされる。このようにして、矩形３１をカバーする複数の領域が、取り扱われる。この傾斜効果の補償が、矩形３１をカバーする線に対して適用される場合、結果は、図９ｄに表示されるように達成される。点線による実際の傾斜した矩形３９は、実線による補償された矩形３９Ａとして考えられる。教示的理由のために、矩形３１の傾斜は、誇張されている。
【００６０】
すべての垂直および水平線および傾斜が少ない線が、画像全体において検出された時点で、方法の次のステップＳ７０は、文書内の表の候補となる矩形を探すためのものである。先のステップＳ５０〜Ｓ６０にしたがって存続線を検出することにより、少なくとも１つの矩形が決定され得る。たとえば、２本が水平に向けられ、２本の線が垂直に向けられた４本の線が、矩形の数学的定義にしたがって矩形を形成することができる。方法の一実施形態によれば、少なくとも１つの矩形が、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げることによって存続線から決定される。主に、各コーナ内の最大矩形が探される。文書の潜在的な表として考えられるために、矩形は、画像の境界に十分近くなければならない。両方の方向において、画像サイズの何分の１か、たとえば画像サイズの１０分の１に等しい最大距離が、使用されてよく、この場合、画像サイズは、垂直方向の高さと等しく、画像サイズは、水平方向の幅に等しい。新しく検出された矩形が、その時点の最大の１つの矩形よりも大きい場合でも、境界から遠すぎる場合は拒絶され得る。インク領域境界が、画像の境界として考えられ得ることに留意されたい。言い換えれば、マージンが考慮に入れられる。このステップＳ７０は、候補矩形の数を最大でも４つに減じる。
【００６１】
しかしながら、決定された矩形のすべてが、たとえばそのサイズ、位置または形態のために、文書の表にならないことがある。特定の場合、決定された矩形は、文書の表として受け入れられない。この特定の場合の結果は、文書は、そのような表を含まないことである。
【００６２】
ヒューリスティックは、決定された矩形を文書の表として受け入れまたは拒絶するために適用されるために本出願人によって開発されている。方法の次のステップＳ８０では、ヒューリスティックは、ステップＳ７０からの少なくとも１つ、最大でも４つの残りの候補矩形に適用される。ヒューリスティックのサブステップＳ８００〜Ｓ８８０が、図１０を用いて説明されている。
【００６３】
矩形がコーナで検出されているとき、その目的は、これが文書の表になり得るかなり得ないかを知ることである。簡単なルールが矩形に適用され、矩形は、これが表の特性に適合しない場合に拒絶され得る。これらのルールは、テストファイルを観察することによって決定されている。以下に、候補矩形上に適用されるルールの順序付きリストが、与えられる。ハードコード化された値は、ファイルの代表的なテストセットにおける経験によって調整されている。
【００６４】
開始状況Ｓ８００は、少なくとも１つの、最大でも４つの残りの候補矩形が、調査されるものである。第１のルールおよび第２のルールが、第１のサブステップＳ８１０において適用される。
【００６５】
第１のルールは、候補矩形が、その寸法（幅、高さ）の１つが、他の寸法より１５倍大きい場合に拒絶されることである。このことにより、薄すぎる矩形の拒絶をもたらす。
【００６６】
第２のルールは、上部左コーナ、上部右コーナ、底部左コーナおよび底部右コーナとして説明される、４つのコーナを有する画像の向きによって決まる。４つのケース（ケース１、ケース２、ケース３、ケース４）が、図１１に示されるように区別され得る。入力画像が横方向を有する場合、上部右コーナ内の矩形および底部左コーナ内の矩形は、画像の上部左コーナまたは底部右コーナ内に少なくとも１つの矩形が存在する場合にのみ拒絶される（ケース１）。入力画像が縦方向を有する場合、底部右コーナ内の矩形および上部左コーナ内の矩形は、画像の上部右コーナ内または底部左コーナ内に少なくとも１つの矩形が存在する場合にのみ拒絶される（ケース２）。ケース３は、実行されていないケース１の状況であるが、画像は横長である。ケース４は、実行されていないケース２の状況であるが、画像は縦長である。図１１では、すべての拒絶された矩形は、各々の拒絶された矩形上の十字記号によってマークされる。
【００６７】
２つの上記で述べられたルールを適用することにより、残りの候補矩形の数が、最大でも２つに等しい次の状態Ｓ８２０が、達成される。多くの他のルールが、第２のルールの後に適用され得る。たとえば：
ａ）矩形は、画像内の最も強く検出された線によって区切られた画像境界との交差部を有さない場合に拒絶され得る。
ｂ）矩形は、画像境界から遠すぎる場合に拒絶され得る。境界からの最大距離は、境界から最も近い矩形の距離の所定倍数に等しくなり得る。そのような所定数は、４になり得る。
ｃ）残りの矩形の数が、２に等しい場合、１つの矩形が、他方の１つより所定倍数小さい面積を有する場合に拒絶される。そのような所定数は、１０になり得る。
ｄ）残りの矩形の数が２に等しく、ケース１が実行された場合、縦長矩形（もし一方がそうである場合）は、他方の１つが横長である場合に拒絶される。
ｅ）残りの矩形の数が２に等しく、ケース２が実行された場合、横長矩形（もし一方がそうである場合）は、他方の１つが縦長である場合に拒絶される。
ｆ）残りの矩形の数が２に等しく、ケース３が実行された場合、横長矩形（もし一方がそうである場合）は、他方の１つが縦長である場合に拒絶される。
ｇ）残りの矩形の数が２に等しく、ケース４が実行された場合、縦長矩形（もし一方がそうである場合）は、他方の１つが横長である場合に拒絶される。
ｈ）残りの矩形の数が２に等しい場合、境界から最も遠い矩形を拒絶する。
【００６８】
ルールａ）〜ｈ）を適用した後、残りの候補矩形の数が１つまたはゼロに等しい次の状態Ｓ８５０が、達成される。残りの候補矩形の数がゼロに等しい場合、表が見つけられない次の状態Ｓ８８０が、達成される。残りの候補矩形の数が１つに等しい場合（Ｓ８６０）、表が見つけられた別の状態Ｓ８７０が、達成される。表が位置特定される画像のコーナ、画像内の表の位置および検出された表の寸法が知られ、さらなる処理に使用され得る。
【００６９】
ヒューリスティックは、処理される文書内に表、たとえばタイトルブロックを検出するために、制御ユニットを含む画像処理機器の種類によって変わり得る。これは、２つの異なる機械の場合、ヒューリスティックが異なり得ることを意味している。上記で説明されたヒューリスティックは、ヒューリスティックの一例である。ヒューリスティックはまた、処理される画像の種類に応じて変更されてもよい。そのようなヒューリスティックは、テストファイルから導出されてよく、異なる決定アルゴリズム、すなわち異なるヒューリスティックをもたらす。
【００７０】
タイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータなどの述べられたパラメータもまた、処理される画像の種類によって変わり、これに合わせて調整される。述べられたパラメータであるタイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータは、方法のための入力パラメータになり得る。代替の実施形態では、述べられたパラメータであるタイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータは、一定のハードコード化されたパラメータとして実装される。代替の実施形態では、ポスター、写真またはＧＩＳファイル上の線の誤判定の検出を最小限に抑えることが必要である。地図上の不定形の線、たとえば川または道路は、矩形を形成するように見えることがある。
【００７１】
代替の実施形態では、入力画像は、黒色画素が値１を有し、白色画素が値０を有し、グレイ画素がその間の値を有するようにコード化される。方法のそのような実施形態のための入力パラメータは、測光法に関する規則である。上記で述べられたコードは、「ｍｉｎ−ｉｓ−ｂｌａｃｋ」規則と呼ばれ、逆のコードは、「ｍｉｎ−ｉｓ−ｗｈｉｔｅ」規則と呼ばれる。「ｍｉｎ−ｉｓ−ｗｈｉｔｅ」規則を使用する場合、勾配を用いた線の検出は、「ｍｉｎ−ｉｓ−ｂｌａｃｋ」規則の場合に最初に極大値、それに続いて極小値を探す代わりに、最初に極小値、それに続いて極大値を探すことによって実施される。そのようなパラメータを使用することにより、入力画像のより広い範囲を処理することが可能になる。
【００７２】
有利な実施形態では、方法は、カラー画像に適用される。カラー情報は、方法には必要でない。白黒入力画像またはグレイレベル画像で十分である。カラー画像に適用されるために、カラー画像は、最初に１つの平坦画像、たとえば１画素当たり１ビットの白黒または１画素当たり８ビットのグレイレベルのビットマップに変換される。カラーまたはそうではない文書は、線の保存を保証するために特有のガンマ曲線を備えて、たとえば１インチ当たり１００ドットの白黒画像にラスタライズされてよい。その結果が、本発明による方法のステップが適用された入力画像であるハーフトーン画像である。
【００７３】
本発明は、その具体的な好ましい実施形態を参照して説明されてきたが、数多くの変形形態および改変形態が、本発明から逸脱することなく加えられ得ることが理解されるものとする。
【００７４】
さらに、本発明の好ましい実施形態の上記の説明は、特定の方法ステップおよびパラメータ値の組合せを提示した。本発明は、特徴のこの特定の組合せに限定されないことが理解されるものとする。より具体的には、これらの特徴は、分離可能であり、異なる副組合せで組み合わされてよい。本発明の範囲は、したがって特許請求の範囲において具体的に記述されたときのみに限定されるものとする。
【技術分野】
【０００１】
本発明は、文書内で表を自動的に位置特定するための方法であって、文書のための複数のタイルを定義するステップと、タイル毎に水平プロファイルおよび垂直プロファイルを決定するステップと、プロファイルを用いて線を検出するステップと、少なくとも１つの矩形を線から決定するステップと、少なくとも１つの矩形から文書の表としての矩形を受け入れるステップとを含む、方法に関する。本発明はまた、方法の適用によって文書内で表を自動的に位置特定するための機器にも関する。
【背景技術】
【０００２】
そのような表は、たとえば書式上に存在する表（ここではセルの二次元の組立体である「表」）の全体または部分になり得る。しかしながら、本発明は、製図におけるタイトルブロック（または凡例）の自動的な位置特定に関して特に対象とするものである。本発明の文書では、用語「表」は、前述された例および一般的な表様の構造のすべてを指すために使用される。
【０００３】
本発明の技術は、普通、但し非限定的に、アナログ文書を走査することによって、またはデジタル文書を作成することによって得られるビットマップの形式での文書の表示に適用される。
【０００４】
文書内に存在する表の位置を自動的に検出ことができることが有利である数多くの分野が存在する。１つの例は、書式処理であり、セル内のデータを読み取ることによってデータベース入力が自動的に生み出されるように書式上の表内のセルを自動的に位置特定できることが望ましい。さまざまな提案が、この分野ですでになされてきている。しかしながら、現在利用可能な書式認識コンピュータプログラムの多くは、書式自体からなり、ほとんど他のものからならない画像内の制約されたポーズの書式の認識に頼っている。
【０００５】
自動的な表の位置特定は、特に製図（機械工学図面または建築図面など）を処理する分野を対象とするものである。後者の分野では、図のタイトルブロックが自動的に位置特定され得る場合、以下のプロセスが実現され得る：
タイトルブロックが見えたままになるように図面を自動的に折り畳み、
（タイトルブロックは、一般に、画像に関して指定されたコーナ、たとえば右下に位置特定されるので）正しい向きで図面を配置し、
たとえばパーソナルコンピュータを用いた図面の走査画像の処理において、タイトルブロックは、手動割り付けを助けるために拡大スケールで表示されることが可能であり、かつ
第１のステップが、図面の自動的割り付けで行われ、タイトルブロックが位置特定された時点で、これは、単にその中に含まれた情報を引き出すという問題となる。
【０００６】
製図におけるタイトルブロック（凡例）の内容および配置を管理するさまざまな標準が、国レベルおよび国際レベルで定義されている。これらの標準は、ＩＳＯ５４５７およびＩＳＯ７２００ならびに仏国標準ＮＦ Ｅ０４−５０３を含む。より詳細には、標準は、欧州特許第１２３７１１５号明細書で説明されている。
【０００７】
上記で述べられたタイプの方法は、欧州特許第１２３７１１５号明細書で開示されており、表は、本発明におけるタイルに類似したその小区域の分析によって位置特定される。タイルは、ソリッド矩形、ソリッド三角形、ソリッド六角形または任意の他のソリッド多角形を形成する複数の画素からなる画像の小区域として定義される。ソリッド多角形の画素の数は、タイルサイズとして定義される。欧州特許第１２３７１１５号明細書における分析は、タイル内の画素各列の黒色画素の合計に基づいて水平プロファイルおよび垂直プロファイル、好ましくはソリッド矩形を作成することによって線の位置を決定することを伴う。特定の閾値を上回る長さを有する線が、決定され、グループに割り当てられる。隣接線の組が、その組内の線の隣接する対間の分離が閾値を下回る場合に共通のグループに割り当てられる。矩形は、それがすべての調査された矩形の中で最も多い線を有するグループを含む場合、表の位置としてすべての調査された矩形から選択される。この技術が製図内でのタイトルブロックの位置特定に適用されるとき、文書のコーナまたは端部に対応する矩形が、分析される。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】欧州特許第１２３７１１５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
欧州特許第１２３７１１５号明細書による方法の欠点は、文書のコーナまたは端部だけが、分析されることである。たとえば、文書の大きなマージンの場合、タイトルブロックは、発見されないことがある。さらには、水平プロファイルおよび垂直プロファイルを用いたタイトルブロックの決定は、画像内の各々決定された画素列上の黒色画素の合計に基づく。そのような決定は、連続階調画像には適用可能でない。欧州特許第１２３７１１５号明細書による方法の別の欠点は、タイトルブロックの傾斜効果が、含められないことである。
【００１０】
本発明の目的は、表の位置特定の従来技術の方法固有の問題および欠点を克服することである。より具体的には、本発明の目的は、文書上に存在する特有の表が、確実にかつすばやく位置特定され得るロバストな表の位置特定の方法および機器を提供することである。
【課題を解決するための手段】
【００１１】
本発明の目的は、上記で述べられた種類の方法であって、水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップと、位置特定された線から存続する線を選択するステップと、少なくとも１つの矩形を存続線から決定するステップと、決定された矩形毎に、矩形を文書の表として受け入れまたは拒絶するためにヒューリスティックを適用するステップとを特徴とする方法において達成される。プロファイルの勾配を用いて、局所的極限が検出され得る。極大値、それに続く所定の差違閾値を備えた極小値は、画像内の線の存在をはっきりと表示するものである。そのようにすることにより、方法は、連続階調画像に特に適合される。タイルサイズは、虫食い線または点線に対しても、その結果においていかなる変更も有することなく変更され得る。さらには、この方法は、プロファイルがタイルの縦列または横列内のグレイ値の平均として算出されるとき、ノイズに対してロバストであるが、それというのもノイズは、平均によって平滑化されるからである。
【００１２】
有利な実施形態では、方法は、複数のタイルが、文書の画像の少なくとも一部をカバーし、所定の重複係数で互いに重複し、所定のタイルサイズを有することを特徴とする。より高い重複係数は、方法の精度を高めるが、それというのも連続タイル上の線は、小片に切断されず、小片を線の一部ではなくノイズとして考えることを防止するからである。タイルサイズはまた、方法の精度および性能に影響を及ぼす。タイルサイズの高い値は精度を低下させるが、性能はより良好になる。タイルサイズは、小さいフォーマット、大きいフォーマット、または小さいフォーマットおよび大きいフォーマットの両方に合わせた方法を適用するように調整され得る。
【００１３】
次の実施形態によれば、少なくとも１つの矩形を存続線から決定するステップは、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げるステップを含む。これは、インク領域境界の場合有利である。インク領域境界の内側線は、画像の境界として考えられ得る。
【００１４】
次の実施形態によれば、水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップは、勾配閾値を決定し、勾配における極大値、それに続いて勾配における極小値を決定するために勾配を調べるステップであって、極大値と極小値の間の絶対的差違は、勾配閾値より大きい、ステップを含む。そのようにすることにより、勾配閾値は、文書の表の線となる可能性が低い、それほど極端ではない局所的極限をふるいにかける。
【００１５】
次の実施形態によれば、存続する線を選択するステップは、線の幅に依存する線の存続度を裁定するステップを含む。線の幅が所定の幅を上回る場合、これは、恐らくは線の一部ではなく、ソリッドのフルカラー領域である。
【００１６】
次の実施形態によれば、存続する線を選択するステップは、複数の連続タイルを決定し、連続タイルの数のすべてにおいて線の存在に依存する線の存続度を裁定するステップを含む。そのようにすることにより、小さい線は、文書の表の線になると考えられることから除外される。
【００１７】
次の実施形態によれば、存続する線を選択するステップは、許容値パラメータを決定し、許容値パラメータの値より多い画素によって分離されない連続タイル内の線を、同じ存続線として考えるステップを含む。これは、傾斜線が、文書の表を検出するために検出され考慮に入れられ得るために有利である。
【００１８】
次の実施形態によれば、決定された矩形の受け入れおよび拒絶は、矩形の二次元の高さおよび幅の比によって決まる。文書の可能性のある表として考えられるには、矩形は、容易に読み取り可能で良好に配置された形の複数の標識単語を含むのに十分な二次元的大きさでなければならない。一方向において「薄すぎる」矩形は、文書の可能性のある表として拒絶される。
【００１９】
次の実施形態によれば、決定された矩形の受け入れおよび拒絶は、文書の画像のコーナの少なくとも１つにおける矩形の存在および文書の画像の向きによって決まる。文書の可能性のある表として考えられるには、矩形は、画像の境界に十分近くなければならない。これは、文書の画像の向きによって決まり、文書のコーナは、文書の表を含むことがより好ましい。
【００２０】
本発明は、さらに、上記で述べられた方法の適用によって文書内で表を自動的に位置特定する機器を提供する。方法は、プリンタコントローラの印刷パスおよびコピーパスの両方、ならびに折り畳みサービス向け用途において使用され得る。文書内の表が検出されたとき、畳み込まれた文書の上部に表が位置するように文書を向けるために、文書の画像に回転が適用され得る。
【００２１】
本発明のさらなる特徴および利点は、例として与えられ、添付の図によって示されたその詳細な実施形態の以下の説明から明確になる。
【図面の簡単な説明】
【００２２】
【図１】本発明が使用され得る環境の概略図である。
【図２】図１による写真製版システムの制御ユニットの概略図である。
【図３】文書内で表を検出するための方法のフロー図である。
【図４】文書内で線を検出するためのフロー図である。
【図５】本発明の方法によるタイル内の線検出を示す。
【図６】許容値パラメータを用いて存続線を検出するためのフロー図である。
【図７】重複係数および最小の線長さを伴ったタイリングを示す。
【図８】傾斜補正を用いて存続線を検出するためのフロー図である。
【図９】傾斜補正の例を示す。
【図１０】残りの候補矩形にヒューリスティックを適用するためのフロー図である。
【図１１】ケース１、ケース２、ケース３、ケース４の場合のヒューリスティックの適用を示す。
【発明を実施するための形態】
【００２３】
図１は、本発明が使用され得る環境の概略図である。ここで提示される写真製版システム１は、走査ユニット２、印刷ユニット３、および制御ユニット４を備える。走査ユニット２は、サポート材料上に支持された元のカラー文書を走査するために設けられる。走査ユニットには、反射された光を原色の赤色（Ｒ）、緑色（Ｇ）および青色（Ｂ）に対応する電気信号に変換するＣＣＤタイプのカラー画像センサ（すなわち光電変換装置）が設けられる。ローカルユーザーインターフェースパネル５が、走査およびコピー操作を開始するために設けられる。
【００２４】
印刷ユニット３は、画像サポート上のデジタル画像を印刷するために設けられる。印刷ユニットは、どのような数の印刷技術を使用してもよい。これは、たとえば熱によるまたは圧電性のインクジェットプリンタ、ペンプロッタ、または有機光伝導体技術に基づくプレスシステムでよい。図１に示す例では、印刷は、シアン、マゼンタ、黄色および黒色などの４つの異なる基本インクが設けられた大きいフォーマット用のインクジェットプリンタを用いて達成される。ハウジングは、キャリッジ上に装着された、画像帯を印刷するための印刷ヘッドを含む。画像は、紙ロールによって供給された一枚の紙などのインク受承媒体上に印刷される。ローカルユーザーインターフェースパネル６には、ユーザ、ジョブを選択し、印刷操作などを開始するためのボタンなどの入力手段が設けられる。
【００２５】
走査ユニット２および印刷ユニット３はいずれも制御ユニット４に接続される。制御ユニット４は、入力データを走査ユニット２から受信する、ネットワーク８を介して投入されたデータファイルを取り扱い、スケジューリングする、走査ユニット２および印刷ユニット３を制御する、画像データを印刷可能なデータに変換するなどのさまざまなタスクを実行する。制御ユニットには、タスクを実行し、設定を行うためのコマンドの広範なメニューをオペレータに提供するためのユーザーインターフェースパネル７が設けられる。
【００２６】
さらには、制御ユニットは、同様にネットワークに接続されている複数のクライアントコンピュータ９が、写真製版システム１を利用できるようにネットワーク８に接続される。制御ユニットは、図２により詳細に提示されている。図２に示されるように、写真製版システム１の制御ユニット４は、中央処理装置（ＣＰＵ）４０、ランダムアクセスメモリ（ＲＡＭ）４８、リードオンリメモリ（ＲＯＭ）６０、ネットワークカード４６、インターフェースカード４７、ハードディスク（ＨＤ）５０および画像処理ユニット５４（ラスターイメージプロセッサまたはＲＩＰなど）を備える。上述されたユニットは、バスシステム４２を通して相互接続されている。
【００２７】
ＣＰＵ４０は、ＲＯＭ６０またはＨＤ５０に記憶された制御プログラムにしたがって制御ユニット４のそれぞれのユニット、ローカルユーザーインターフェース７を制御する。ＣＰＵ４０はまた、画像処理ユニット５４も制御する。
【００２８】
ＲＯＭ６０は、起動プログラム、セットアッププログラム、さまざまなセットアップデータまたは類似のものなどの、ＣＰＵ４０によって読み取られ実行されるプログラムおよびデータを記憶する。
【００２９】
ハードディスク５０は、後述される印刷プロセスをＣＰＵ４０に実行させるプログラムおよびデータを記憶および保存するための記憶ユニットの一例である。ハードディスク５０はまた、外部的に投入された印刷ジョブのデータを保存するための領域も含む。ＨＤ５０上のプログラムおよびデータは、必要に応じてＣＰＵ４０によってＲＡＭ４８上に読み取られる。ＲＡＭ４８は、ＣＰＵ４０によってＲＯＭ６０およびＨＤ５０から読み取られたプログラムおよびデータを一時的に記憶するための領域と、さまざまなプロセスを実行するためにＣＰＵ４０によって使用される作業領域とを有する。
【００３０】
インターフェースカード４７は、制御ユニットを走査ユニット２および印刷ユニット３に接続する。
【００３１】
ネットワークカード４６は、制御ユニット４をネットワーク８に接続し、ワークステーション９、およびネットワークを介して到達可能な他のデバイスとの通信をもたらすように設計される。
【００３２】
画像処理ユニット５４は、制御ユニット４上で実行するオペレーティングシステムのソフトウエア構成要素として、またはＦＰＧＬＡ内に具現化されるファームウエアプログラムとして実装され得る。画像処理ユニット５４は、印刷ジョブデータを読み取り、解釈し、ラスタライズするための機能を有する。前記印刷ジョブデータは、印刷される対象の画像データ（すなわちページ記述言語（Ｐａｇｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ）またはそのようなもので表現された、印刷される対象の文書の内容を表現するフォントおよびグラフィック）、画像処理特性、および印刷設定を含む。有利な実施形態では、画像処理ユニット５４は、本発明による方法を実施する。
【００３３】
写真製版システムのオペレーションの基本的形態は、走査、コピー、および印刷である。原色の赤色（Ｒ）、緑色（Ｇ）、および青色（Ｂ）に対応する電気信号が、走査中に得られた状態で、デジタル画像が、ラスター画像ファイルの形式で組み立てられる。ラスター画像ファイルは、一般的に、画素として知られている、定期的にサンプリングされた値の矩形配列になると定義される。各々の画素（画像画素）は、画素に関連付けられた、一般的には画素が表示されるべき色を指定する１つまたは複数の番号を有する。画像の表示は、各々の画素内のＲ、Ｇ、およびＢそれぞれの量を定義する、３つの８ビット（合計２４ビット）の測色値（０〜２５５の範囲）によって指定された各々の画素を有することができる。正しい比率において、Ｒ、Ｇ、およびＢは組み合わされて黒色、白色、２５４の階調、および無数の色（約１６００万色）を形成することができる。走査ユニット２によって得られたデジタル画像は、制御ユニット４のメモリ上に記憶され、コピーパスにしたがって取り扱われ得、この場合画像は、印刷エンジン３によって印刷される。あるいは、デジタル画像は、コントローラからクライアントコンピュータ９に転送されてよい（ファイルを走査するパス）。最終的に、クライアントコンピュータ９のユーザは、システムのオペレーションの印刷モードを反映するデジタル画像を印刷することを決定することができる。
【００３４】
本発明による方法のフロー図が、図３に示されており、これは、複数のステップＳ１０〜Ｓ８０からなる。
【００３５】
方法は、文書のための複数のタイルを定義するステップＳ１０で開始する。文書の画像は、画素からなる。複数のタイルが、画像の画素をカバーしており、次の４つのステップＳ１５、Ｓ２０、Ｓ３０、Ｓ４０において画像内の線を探し、検出するために使用される。
【００３６】
ステップＳ１５では、タイルが選択される。次に、プロファイルが決定される（ステップＳ２０）。決定されたプロファイルに対して、一連の勾配が決定される（ステップＳ３０）。次のステップＳ４０では、線が一連の勾配から検出される。このステップは、さらに図４で詳述される。プロファイルから線が検出された後、次のステップＳ４３において、次のプロファイルが得られるかが確認される。そうである（はいの）場合、方法はステップＳ２０に戻る。そうでない（いいえの）場合、水平および垂直の両方のプロファイルは処理されているため、次のプロファイルは得られず、方法はステップＳ４６に続く。ステップＳ４６では、次のタイルが得られるかが確認される。そうである（はいの）場合、方法はステップＳ１５に戻る。そうでない（いいえの）場合、すべてのタイルが処理されているため、次のタイルは得られず、方法はステップＳ５０に続く。
【００３７】
ステップＳ５０では、複数の連続タイル内の存続線が、検出される。このステップは、図６でさらに詳述される。ステップＳ６０では、存続線が、傾斜補正によって検出される。ステップＳ６０は、先のステップＳ５０で検出された存続線、ならびに一連の勾配によって検出され、先のステップＳ５０で検出された存続線に属さない線に対して適用される。ステップＳ６０は、図８でさらに詳述される。
【００３８】
次のステップＳ７０は、少なくとも１つの矩形の決定であり、最大でも４つの矩形が存続線を形成する。これは、画像のコーナ内の矩形に関する。
【００３９】
最後のステップＳ８０は、文書の表を検出するために、決定された矩形にヒューリスティックを適用するものである。
【００４０】
次にステップＳ１０〜Ｓ８０が、さらに詳細に説明される。方法は、文書のための複数のタイルを決定するステップＳ１０で開始する。文書の画像は、複数の画素からなる。複数のタイルが、画像をカバーしており、線を探し、検出するために使用される。方法は、画像を水平方向および垂直方向にタイルとして切断する。好ましくは各々のタイルは、画素のソリッド正方形であるが、矩形、三角形、六角形などの適切な他の形態を有することができる。タイルに関してここからは、正方形であると仮定する。各々のタイルは、ソリッド正方形の画素数として定義されるタイルサイズを有する。初期値のタイルサイズが定義され得る。大判フォーマット、たとえばＡ０フォーマットでは、５０×５０画素のタイルサイズが、本出願人の実験によって良好な結果を与える。より小さいフォーマットでは、適切なより小さいタイルサイズが、たとえば画像の等価解像度で選択されてよく、Ａ３フォーマットでは、１２×１２画素のタイルサイズが、最適になり得る（１２≒５０／４であることに留意されたい）。最大のタイルサイズ、たとえば画像サイズもまた定義されてよい。タイルサイズは、方法の精度および性能に影響を及ぼす。タイルサイズの高い値は、精度を低下させ得るが、性能はより良好になり得る。タイルサイズの高い値では、タイルの数は低下し、算出の回数は減少し、性能はより良好になる。
【００４１】
次のステップＳ１５は、先のステップＳ１０で定義された複数のタイルからタイルを選択することである。次の３つのステップＳ２０、Ｓ３０、Ｓ４０が、このタイルに適用され、その後、次のタイルが調査される。
【００４２】
次のステップＳ２０は、選択されたタイルのための水平プロファイルを決定するものである。タイル内の各々の画素は、０の白色画素から１の黒色画素に変化するグレイレベルを有することができる。方法の特定の実施形態では、グレイレベルは、２５５段階で０から１まである。タイルの水平プロファイルは、複数の値からなり、各々の値は、タイルの画素横列から算出される。タイルの垂直プロファイルは、複数の値からなり、各々の値は、タイルの画素縦列から算出される。好ましくは、水平プロファイルの値および垂直プロファイルの値は、同じ方式で決定される。水平プロファイルの値は、画素横列内のグレイレベルの総和および画素横列内の画素の総数の商を算出することによって決定されてよい。垂直プロファイルの値は、画素縦列内のグレイレベルの総和および画素縦列内の画素の総数の商を算出することによって同様に決定され得る。このようにすることにより、決定されたプロファイル値は、０から１までの間で変化することができ、プロファイルの値の数は、タイルサイズと等しい。画像がグレイレベルデータからなる場合であっても、プロファイリングの算出は、横列または縦列内の画素のグレイレベルの平均をとることによって確立される。特に、方法はまた、連続階調画像にも適用されてよい。グレイレベルの平均を用いることにより、タイルサイズは、虫食い線または点線であっても、その結果においていかなる変更も有することなく変更され得る。さらには、この方法は、平均によって平滑化されるノイズに対してロバストなものになる。ステップＳ３０、Ｓ４０が水平プロファイルに適用された後、方法はステップＳ１５に戻り、垂直プロファイルがステップＳ２０において決定され、同じステップＳ３０、Ｓ４０が、この垂直プロファイルに対して実行される。プロファイルがステップＳ２０において進められる順番は、タイル毎かつタイル毎に水平プロファイルそれに続いて垂直プロファイルであるが、いかなる影響も及ぼすことなく、タイル毎かつタイル毎に垂直プロファイル、それに続いて水平プロファイルでもよい。
【００４３】
次のステップＳ３０は、調査下のプロファイルに対する一連の勾配を決定するものである。方法によれば、一連の勾配は、一連の一次元の勾配として定義される。各々の一次元の勾配は、画像内の２つの隣接する画素横列の間、または画像内の２つの隣接する画素縦列の間のグレイレベルの変化度として差分商を算出することによってプロファイルの導関数の近似値によって決定される。隣接する画素横列の各々の対に関して、差分商は、水平プロファイルの場合、隣接する画素横列のプロファイル値の差違および隣接する横列の間の距離の商をとることによって算出される。隣接する画素横列の対の差分商は、水平勾配と呼ばれる。垂直プロファイルの場合、差分商は、同様に算出される。隣接する画素縦列の対に対する差分商は、垂直勾配と呼ばれる。隣接する画素横列間の距離および隣接する画素縦列間の距離が１に等しいと推定することにより、差分商は、１で割ることによって算出される。
【００４４】
次のステップＳ４０は、調査下の一連の勾配を用いて文書内で線を検出するものである。線の検出は、図４に示されるフロー図におけるステップを用いてさらに説明される。第１のサブステップＳ４２０は、極大値ｌｍａｘ、それに続いて極小値ｌｍｉｘまたはその逆のすべての出現を一連の勾配において見つけるものである。一連の勾配は、極大値ｌｍａｘ、それに続いて極小値ｌｍｉｘまたはその逆を含むことができ、これは、画像内の線の存在を示すことができる。線の存在を評価するために、勾配閾値ｔｈｒｇｒａｄが、方法のための入力パラメータとして導入される。代替の実施形態では、勾配閾値ｔｈｒｇｒａｄは、一定のハードコード化されたパラメータとして実装される。次のステップＳ４２５では、１つの極大値、それに続いて極小値、またはその逆の出現が見つけられたかが確認される。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。出現が見つけられた（はいの）場合、次のサブステップＳ４３０は、そのような出現を選択するものである。出現の選択の後、次のサブステップＳ４４０は、極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値と勾配閾値ｔｈｒｇｒａｄを比較するものである。極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値が、勾配閾値ｔｈｒｇｒａｄより大きい（はいの）場合、線の存在が想定され、この線は、文書内の表の線の候補になり得る。そのような勾配閾値ｔｈｒｇｒａｄの最小値、最大値、および初期値は、それぞれ０、タイルサイズ値の平方根の２倍、およびタイルサイズ値の平方根になり得る。矩形の形態のタイルの場合、水平プロファイルの最小値、最大値、および初期値は、垂直プロファイルの最小値、最大値、および初期値それぞれとは比例的に異なり得る。極大値ｌｍａｘおよび極小値ｌｍｉｘの差違の絶対値が、勾配閾値ｔｈｒｇｒａｄより大きくない（いいえの）場合、線の存在は想定されない。次のステップＳ４６５では、得られる次の出現が存在するかが確認される。そうである（はいの）場合、方法は、同じ一連の勾配において、極大値、それに続いて極小値またはその逆の次の出現を選択するステップ４３０に戻る。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。
【００４５】
線の存在が推定される場合、次のサブステップＳ４５０において、プロファイル内の最大の位置Ｘｍａｘおよび最小の位置Ｘｍｉｘが決定され、この位置は、タイル内の可能性のある線の位置に関連する。画像内のタイルの位置は、画像内のタイルのオフセット情報が保存されている場合に容易になり得る。一連の勾配における最大の位置Ｘｍａｘと最小の位置Ｘｍｉｘの間の距離は、線の幅になると想定される。一連の勾配を介して検出された線は、線の幅が最大の線幅ｌｗｍａｘ未満である場合、表の一部であると想定され得る。したがって、サブステップＳ４５０では、線幅が、最大の線幅ｌｗｍａｘと比較される。極小値ｌｍｉｘの位置Ｘｍｉｘおよび極大値ｌｍａｘの位置Ｘｍａｘの差違が、最大線幅ｌｗｍａｘより小さい（はいの）場合、線の存在が検出され（Ｓ４６０）、この線は、文書内の表の線の候補になり得る。最大線幅ｌｗｍａｘは、方法の入力パラメータになり得る。代替の実施形態では、最大線幅ｌｗｍａｘは、一定のハードコード化されたパラメータとして実装される。方法は、サブステップＳ４６５に続く。極小値ｌｍｉｘの位置Ｘｍｉｘおよび極大値ｌｍａｘの位置Ｘｍａｘの差違が、最大線幅ｌｗｍａｘより小さくない（いいえの）場合、線の存在は検出されない。方法は、サブステップＳ４６５に続く。
【００４６】
サブステップＳ４６５において、得られる次の出現が存在するかがチェックされる。そうである（はいの）場合、方法はサブステップＳ４３０に戻る。そうでない（いいえの）場合、方法は、図３にしたがってステップＳ４３に続く。
【００４７】
最大線幅ｌｗｍａｘは、０からタイルサイズの間で変化することができ、この場合０に等しい値およびタイルサイズに等しい値は除外される。最大線幅ｌｗｍａｘの初期値、たとえば３０が５０×５０画素のタイルサイズで使用されてよい。この最大線幅ｌｗｍａｘを用いることにより、ソリッド黒、グレイ、または他のフルカラー領域は、線検出から除外される。
【００４８】
図４のフロー図によって説明された線検出の適用の例が、図５に示されている。表の検出のために画像分析を開始する際、画像は、所定のタイルサイズのタイルに分割される。タイル毎に、オフセットが画像の所定の原点に対して算出される。図５によれば、タイル１０は、８×８画素のタイルサイズを備えて示されている。タイル１０は正方形の画素であるため、タイル内の画素の総数は、８×８＝６４画素に等しい。８×８画素のタイルサイズは、水平プロファイルおよび垂直プロファイルの原理を実証するために選択される。実際には、より大きいタイルサイズ、たとえば５０×５０画素が使用されてよい。タイル１０は、８列の横列Ｒ１〜Ｒ８を含む。タイル１０はまた、８列の縦列Ｃ１〜Ｃ８を含む。一部の画素１１、１２、１３は、白色にされ、一部の画素１４、１５は、黒色にされる。白色画素は、数字０によってデジタル化される。黒色画素は、数字１によってデジタル化される。この例におけるタイル内の数字は、０および１であるが、一般的に数字は、０から１の間のどのような数でもよい。これはグレイレベルデータおよび連続階調画像の場合有用である。水平プロファイル１Ｈを確立するために、各々の横列の画素値の総和が決定される。垂直プロファイル１Ｖを確立するために、各々の縦列の画素値の総和が決定される。水平プロファイル１Ｈは、横列Ｒ１〜Ｒ８に対して０、０、８、１、１、１、１、１の値それぞれを含む。垂直プロファイル１Ｖは、縦列Ｃ１〜Ｃ８に対して１、１、１、１、６、１、１、１の値それぞれを含む。このとき垂直プロファイルおよび水平プロファイルの一連の勾配が、線を検出するために使用される。水平プロファイルの一連の勾配は、隣り合う水平プロファイル値およびタイルの対応する隣り合う画素横列の距離の差分商をとることによって算出される。垂直プロファイルの一連の勾配は、隣り合う垂直プロファイル値およびタイルの対応する隣り合う画素縦列の距離の差分商をとることによって算出される。２つの隣り合う縦列間の距離が１に設定され、２つの隣り合う横列間の距離もまた１に設定されることが推定される。
【００４９】
水平プロファイルの差分商は、０／１、８／１、−７／１、０／１、０／１、０／１、０／１である。第２および第３の差分商が絶対的に大きく、値８の極大値、それに続いて値−７の極小値が、第２および第３の差分商において検出される。これは、タイル１０内の第３の横列Ｒ３における極大値を指しており、この極大値は、タイル１０内の第３の横列Ｒ３内に線または線の一部が存在することを示すものである。線の存在をこうして表示させることを本方法の適用において現実にするために、たとえばタイルサイズの平方根に等しい８の勾配閾値が導入される。極大値および極小値の絶対差違が、勾配閾値より大きい場合、線の存在が想定される。水平プロファイルにおけるこの場合、絶対差違は、８−（−７）＝１５であり、これは８に等しい勾配閾値より大きく、そのために水平線が存在すると考えられる。
【００５０】
垂直プロファイルの差分商は、０／１、０／１、０／１、５／１、−５／１、０／１、０／１である。第４および第５の差分商が、絶対的に大きく、値５の極大値、それに続いて値−５の極小値が、第４および第５の差分商において検出される。これは、タイル１０内の第５の縦列Ｃ５における極大値を指しており、この極大値は、タイル１０内の第５の縦列Ｃ５内に線または線の一部が存在することを示すものである。極大値および極小値の絶対差違が、勾配閾値より大きい場合、線の存在が想定される。垂直プロファイルにおけるこの場合、絶対差違は、５−（−５）＝１０であり、これは８に等しい勾配閾値より大きく、そのために垂直線が存在すると考えられる。
【００５１】
タイルサイズに関連して小さい線は、勾配閾値のために失われる。そのような線は、勾配閾値より小さいプロファイル値を有し、線よりもノイズとして考えられる。線として考えられるために、たとえば垂直または水平の平坦線を反映するデータ（垂直プロファイル値は、垂直平坦線の場合、タイル内の横列の数と等しく、水平プロファイル値は、水平平坦線の場合、タイル内の縦列の数に等しい）は、タイル上で一貫していなければならない。より少ない検出線でより大きい勾配閾値と数多くの検出された線でより小さい勾配閾値との間でバランスをとるために、最適値が、勾配閾値に対して選択される（多すぎるノイズは線として考えられる）。（正方形タイルの場合）タイルサイズの平方根に等しい勾配閾値が、良好な結果を与えることを経験が明らかにしている。
【００５２】
プロファイルにおける極大値と極小値の間の距離は、線幅を与える。この場合、第３の横列Ｒ３内の検出された水平線に対する線幅は、第５の縦列Ｃ５内の検出された垂直線の線幅と同様に１に等しい。画像内の水平線または垂直線の位置は、画像内のタイルのすでに算出されたオフセット値のために容易に計算可能である。追加の試験が、検出された線幅に関連して導入され得る。線の幅は、最大の線幅入力パラメータ未満、本発明ではたとえば６になり得る。タイル１０内の水平線ならびに垂直線の線幅は、１に等しく、６に等しい最大の線幅入力パラメータ未満であるので、検出された線は、方法のさらなるステップに対する適切な線であると考えられる。
【００５３】
方法における次のステップＳ５０は、複数の連続タイル内で存続線を検出することである。このステップは、図６のフロー図に示されるサブステップＳ５１０〜Ｓ５３０によって説明される。表の線は、所定の最小長さを有するため、表の線が、１つのタイルまたは複数の連続タイル内に検出されるかはタイルサイズによって決まる。しばしば連続タイル内に出現する表の線が、検出される。これは、水平方向の連続タイルならびに垂直方向の連続タイル内になり得る。各々のタイル内の小さい線は、連続タイル内に存在するより小さい線からなる、より大きい線の一部になり得るため、ステップＳ５０は、複数の連続タイルを決定し、連続タイルの数のすべてにおいて線の存在に依存する線の存続度を裁定するステップを含む。
【００５４】
方法の精度を向上させるために、タイリングが、タイルが重複するような方式で行われ得る。０から１の間で変わり得る重複係数は、重複度を決定する。０に等しい重複係数は、連続タイル間に重複が存在しないことを示す。連続タイルの完全な重複を決定する１に等しい重複係数は、除外されてよい。重複係数の初期値は、０．５になり得、これは、タイルの半分が、連続タイルによって一方向に重複されていることを意味する。好ましくは、重複は、画像の水平方向ならびに垂直方向に起こる。
【００５５】
すべてのタイルが、先のステップＳ１５、Ｓ２０、Ｓ３０、Ｓ４０において分析されたとき、すべての検出された線ｌ１〜ｌｍが、ステップＳ５０において調べられる。十分に長い線が、保持される。短い線は、文書の表になるのに十分な大きさの矩形の一部にはなり得ない。存続線だけが、レース内に保持され得る。存続線は、連続タイルの特定の数ｎｃｏｎｓｅｃ内で検出されたものである。この数ｎｃｏｎｓｅｃは、方法の入力パラメータになり得、タイルの重複係数によって変わる。代替の実施形態では、数ｎｃｏｎｓｅｃは、一定のハードコード化されたパラメータとして実装される。複数の水平の連続タイルの同じ横列内で出現する複数の線は、同じ水平の存続線になると考えられる。複数の垂直の連続タイルの同じ縦列内で出現する複数の線は、同じ垂直の存続線になると考えられる。したがって、サブステップＳ５１０では、線ｌ１〜ｌｍが、ｍｉ個の連続タイル内でｋ個の線のグループにグループ化される。線のグループ毎に、数ｍｉが、次のサブステップＳ５２０において数ｎｃｏｎｓｅｃと比較される。数ｍｉが、数ｎｃｏｎｓｅｃより大きい、またはこれと等しい場合、ｉ番目のグループの線は、サブステップＳ５３０で示されるように存続線を形成する。ｋ個のグループの線をすべて調べた後、複数の存続線が検出され、これは、文書の表の一部となる候補になる。
【００５６】
図７では、第１の矢印ＯＦによって示された重複係数で互いに重複する５つの連続タイルＴ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５が、示されている。この特定の場合、重複係数は、０．５に等しい。８×８画素に等しいタイルサイズの場合、重複は、４列の画素縦列である。５つの連続タイルＴ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５は、各々３×８＝２４画素の横列を含む。存続線を想定するための連続タイルの数ｎｃｏｎｓｅｃが、５に等しい場合、検出された線の最小の総サイズは、２４画素である。これはまた、図７の第２の矢印ＭＬによって示されるように最小の線長さとも呼ばれ得る。
【００５７】
方法の次のステップＳ６０は、傾斜補正を用いて存続線を検出することである。このステップＳ６０のサブステップＳ６１０〜Ｓ６５０が、図８に示されており、ステップＳ５０において検出された存続線に適用され、また、ステップＳ４０においてすでに検出されており、ステップＳ５０において存続線として検出されていない線にも適用される。
【００５８】
プロファイルが、タイリングを用いて計算され、タイルの重複が、画像内で線を検出するために適用されるため、画像内の傾斜効果が、補正され得る。許容値パラメータｔｐの値ｖｔｐは、傾斜効果を補正するための方法の入力パラメータである。代替の実施形態では、許容値パラメータｔｐの値ｖｔｐは、一定のハードコード化されたパラメータとして実装される。毎回調査される線から、水平の隣接タイル内の線の対または垂直の隣接線内の線の対が、第１のサブステップＳ６１０で選択される。２本の選択された隣接線が一方向に異なる画素の数ｎｐｉｘｅｌが、次のサブステップＳ６２０において決定される。画素の数ｎｐｉｘｅｌは、次のサブステップＳ６３０において許容値パラメータｔｐの値ｖｔｐと比較される。画素の数ｎｐｉｘｅｌが、許容値パラメータｔｐの値ｖｔｐ未満またはこれと等しい場合、２本の隣接線は、次のサブステップＳ６４０においてそれぞれ同じ水平または垂直の存続線であると考えられる。次のサブステップＳ６５０では、隣接線のすべての対が調査されたかが確認される。そうでない場合、先のサブステップＳ６１０、Ｓ６２０、Ｓ６３０が、繰り返される。そのような許容値パラメータｔｐの初期設定値ｖｔｐは、５になり得る。利点は、そのような許容値パラメータｔｐが、ネーティブファイルならびに走査されたファイル上に適用され得ることである。このようにして、走査に対する潜在的なスキューエフェクトが、考慮に入れられる。
【００５９】
傾斜効果の補償は、図９ａから図９ｄに示されるように潜在的なスキューエフェクトを考慮に入れるために適用される。傾斜効果を考慮に入れるために、許容値パラメータｔｐが、先のステップにおいて検出された存続線の位置に適用される。傾斜効果の補償は、それまで検出された線のすべてに適用され、ここからその長さおよび位置が知られる。したがって画像全体が、考慮に入れられる。図９ａは、傾斜した矩形３１を含む画像３０を示している。この傾斜した矩形３１を用いて、傾斜効果の補償がどのようにして局所的に働くかが示されている。傾斜した矩形３１の傾斜線３３の対象の第１の領域３２（領域３２が垂直および水平の両方向の複数の隣接タイルからなる）の画素レベルに注目すると、図９ｂに示されるようにより小さい（垂直）線３４、３５、３６が検出される。線３４、３５、３６は、各々１つまたは複数のタイル上を延びることができる。図９ｂは、傾斜線３３の一部が、（黒色）画素の３本の垂直線３４、３５、３６からなることを示している。垂直線３４、３５、３６は、３画素未満分離される。許容値パラメータｔｐが、３に等しい、またはそれ以上になる場合、垂直線３４、３５および３６は、図９ｃに示された同じ存続線３７の一部であると考えられる。上側線３４の位置は、傾斜効果の補償のための基準位置になると想定される。この基準位置は、点線３４Ａで示されている。矢印３８は、下側線３５、３６が、上側線３４の下方から点線３４Ａによって示された基準位置にシフトされる傾斜効果の補償を示している。第１の領域３２の下方の次の領域が、次に調査される。最低線３６から３画素未満分離された隣接線が、この次の領域内で検出された場合、これらの線もまた、基準位置３４Ａにシフトされる。このようにして、矩形３１をカバーする複数の領域が、取り扱われる。この傾斜効果の補償が、矩形３１をカバーする線に対して適用される場合、結果は、図９ｄに表示されるように達成される。点線による実際の傾斜した矩形３９は、実線による補償された矩形３９Ａとして考えられる。教示的理由のために、矩形３１の傾斜は、誇張されている。
【００６０】
すべての垂直および水平線および傾斜が少ない線が、画像全体において検出された時点で、方法の次のステップＳ７０は、文書内の表の候補となる矩形を探すためのものである。先のステップＳ５０〜Ｓ６０にしたがって存続線を検出することにより、少なくとも１つの矩形が決定され得る。たとえば、２本が水平に向けられ、２本の線が垂直に向けられた４本の線が、矩形の数学的定義にしたがって矩形を形成することができる。方法の一実施形態によれば、少なくとも１つの矩形が、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げることによって存続線から決定される。主に、各コーナ内の最大矩形が探される。文書の潜在的な表として考えられるために、矩形は、画像の境界に十分近くなければならない。両方の方向において、画像サイズの何分の１か、たとえば画像サイズの１０分の１に等しい最大距離が、使用されてよく、この場合、画像サイズは、垂直方向の高さと等しく、画像サイズは、水平方向の幅に等しい。新しく検出された矩形が、その時点の最大の１つの矩形よりも大きい場合でも、境界から遠すぎる場合は拒絶され得る。インク領域境界が、画像の境界として考えられ得ることに留意されたい。言い換えれば、マージンが考慮に入れられる。このステップＳ７０は、候補矩形の数を最大でも４つに減じる。
【００６１】
しかしながら、決定された矩形のすべてが、たとえばそのサイズ、位置または形態のために、文書の表にならないことがある。特定の場合、決定された矩形は、文書の表として受け入れられない。この特定の場合の結果は、文書は、そのような表を含まないことである。
【００６２】
ヒューリスティックは、決定された矩形を文書の表として受け入れまたは拒絶するために適用されるために本出願人によって開発されている。方法の次のステップＳ８０では、ヒューリスティックは、ステップＳ７０からの少なくとも１つ、最大でも４つの残りの候補矩形に適用される。ヒューリスティックのサブステップＳ８００〜Ｓ８８０が、図１０を用いて説明されている。
【００６３】
矩形がコーナで検出されているとき、その目的は、これが文書の表になり得るかなり得ないかを知ることである。簡単なルールが矩形に適用され、矩形は、これが表の特性に適合しない場合に拒絶され得る。これらのルールは、テストファイルを観察することによって決定されている。以下に、候補矩形上に適用されるルールの順序付きリストが、与えられる。ハードコード化された値は、ファイルの代表的なテストセットにおける経験によって調整されている。
【００６４】
開始状況Ｓ８００は、少なくとも１つの、最大でも４つの残りの候補矩形が、調査されるものである。第１のルールおよび第２のルールが、第１のサブステップＳ８１０において適用される。
【００６５】
第１のルールは、候補矩形が、その寸法（幅、高さ）の１つが、他の寸法より１５倍大きい場合に拒絶されることである。このことにより、薄すぎる矩形の拒絶をもたらす。
【００６６】
第２のルールは、上部左コーナ、上部右コーナ、底部左コーナおよび底部右コーナとして説明される、４つのコーナを有する画像の向きによって決まる。４つのケース（ケース１、ケース２、ケース３、ケース４）が、図１１に示されるように区別され得る。入力画像が横方向を有する場合、上部右コーナ内の矩形および底部左コーナ内の矩形は、画像の上部左コーナまたは底部右コーナ内に少なくとも１つの矩形が存在する場合にのみ拒絶される（ケース１）。入力画像が縦方向を有する場合、底部右コーナ内の矩形および上部左コーナ内の矩形は、画像の上部右コーナ内または底部左コーナ内に少なくとも１つの矩形が存在する場合にのみ拒絶される（ケース２）。ケース３は、実行されていないケース１の状況であるが、画像は横長である。ケース４は、実行されていないケース２の状況であるが、画像は縦長である。図１１では、すべての拒絶された矩形は、各々の拒絶された矩形上の十字記号によってマークされる。
【００６７】
２つの上記で述べられたルールを適用することにより、残りの候補矩形の数が、最大でも２つに等しい次の状態Ｓ８２０が、達成される。多くの他のルールが、第２のルールの後に適用され得る。たとえば：
ａ）矩形は、画像内の最も強く検出された線によって区切られた画像境界との交差部を有さない場合に拒絶され得る。
ｂ）矩形は、画像境界から遠すぎる場合に拒絶され得る。境界からの最大距離は、境界から最も近い矩形の距離の所定倍数に等しくなり得る。そのような所定数は、４になり得る。
ｃ）残りの矩形の数が、２に等しい場合、１つの矩形が、他方の１つより所定倍数小さい面積を有する場合に拒絶される。そのような所定数は、１０になり得る。
ｄ）残りの矩形の数が２に等しく、ケース１が実行された場合、縦長矩形（もし一方がそうである場合）は、他方の１つが横長である場合に拒絶される。
ｅ）残りの矩形の数が２に等しく、ケース２が実行された場合、横長矩形（もし一方がそうである場合）は、他方の１つが縦長である場合に拒絶される。
ｆ）残りの矩形の数が２に等しく、ケース３が実行された場合、横長矩形（もし一方がそうである場合）は、他方の１つが縦長である場合に拒絶される。
ｇ）残りの矩形の数が２に等しく、ケース４が実行された場合、縦長矩形（もし一方がそうである場合）は、他方の１つが横長である場合に拒絶される。
ｈ）残りの矩形の数が２に等しい場合、境界から最も遠い矩形を拒絶する。
【００６８】
ルールａ）〜ｈ）を適用した後、残りの候補矩形の数が１つまたはゼロに等しい次の状態Ｓ８５０が、達成される。残りの候補矩形の数がゼロに等しい場合、表が見つけられない次の状態Ｓ８８０が、達成される。残りの候補矩形の数が１つに等しい場合（Ｓ８６０）、表が見つけられた別の状態Ｓ８７０が、達成される。表が位置特定される画像のコーナ、画像内の表の位置および検出された表の寸法が知られ、さらなる処理に使用され得る。
【００６９】
ヒューリスティックは、処理される文書内に表、たとえばタイトルブロックを検出するために、制御ユニットを含む画像処理機器の種類によって変わり得る。これは、２つの異なる機械の場合、ヒューリスティックが異なり得ることを意味している。上記で説明されたヒューリスティックは、ヒューリスティックの一例である。ヒューリスティックはまた、処理される画像の種類に応じて変更されてもよい。そのようなヒューリスティックは、テストファイルから導出されてよく、異なる決定アルゴリズム、すなわち異なるヒューリスティックをもたらす。
【００７０】
タイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータなどの述べられたパラメータもまた、処理される画像の種類によって変わり、これに合わせて調整される。述べられたパラメータであるタイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータは、方法のための入力パラメータになり得る。代替の実施形態では、述べられたパラメータであるタイルサイズ、重複係数、最大の線幅、勾配閾値および許容値パラメータは、一定のハードコード化されたパラメータとして実装される。代替の実施形態では、ポスター、写真またはＧＩＳファイル上の線の誤判定の検出を最小限に抑えることが必要である。地図上の不定形の線、たとえば川または道路は、矩形を形成するように見えることがある。
【００７１】
代替の実施形態では、入力画像は、黒色画素が値１を有し、白色画素が値０を有し、グレイ画素がその間の値を有するようにコード化される。方法のそのような実施形態のための入力パラメータは、測光法に関する規則である。上記で述べられたコードは、「ｍｉｎ−ｉｓ−ｂｌａｃｋ」規則と呼ばれ、逆のコードは、「ｍｉｎ−ｉｓ−ｗｈｉｔｅ」規則と呼ばれる。「ｍｉｎ−ｉｓ−ｗｈｉｔｅ」規則を使用する場合、勾配を用いた線の検出は、「ｍｉｎ−ｉｓ−ｂｌａｃｋ」規則の場合に最初に極大値、それに続いて極小値を探す代わりに、最初に極小値、それに続いて極大値を探すことによって実施される。そのようなパラメータを使用することにより、入力画像のより広い範囲を処理することが可能になる。
【００７２】
有利な実施形態では、方法は、カラー画像に適用される。カラー情報は、方法には必要でない。白黒入力画像またはグレイレベル画像で十分である。カラー画像に適用されるために、カラー画像は、最初に１つの平坦画像、たとえば１画素当たり１ビットの白黒または１画素当たり８ビットのグレイレベルのビットマップに変換される。カラーまたはそうではない文書は、線の保存を保証するために特有のガンマ曲線を備えて、たとえば１インチ当たり１００ドットの白黒画像にラスタライズされてよい。その結果が、本発明による方法のステップが適用された入力画像であるハーフトーン画像である。
【００７３】
本発明は、その具体的な好ましい実施形態を参照して説明されてきたが、数多くの変形形態および改変形態が、本発明から逸脱することなく加えられ得ることが理解されるものとする。
【００７４】
さらに、本発明の好ましい実施形態の上記の説明は、特定の方法ステップおよびパラメータ値の組合せを提示した。本発明は、特徴のこの特定の組合せに限定されないことが理解されるものとする。より具体的には、これらの特徴は、分離可能であり、異なる副組合せで組み合わされてよい。本発明の範囲は、したがって特許請求の範囲において具体的に記述されたときのみに限定されるものとする。
【特許請求の範囲】
【請求項１】
文書内で表を自動的に位置特定するための方法であって、
文書のための複数のタイルを定義するステップと、
各々のタイルに対して水平プロファイルおよび垂直プロファイルを決定するステップと、
プロファイルを用いて線を検出するステップと、
少なくとも１つの矩形を線から決定するステップと、
少なくとも１つの矩形から、文書の表としての矩形を受け入れるステップとを含み、
前記方法が、さらに、
水平プロファイルおよび前記垂直プロファイルの１つの勾配を用いて線の位置を決定するステップと、
位置特定された線から、存続する線を選択するステップと、
少なくとも１つの矩形を前記存続線から決定するステップと、
決定された矩形毎に、矩形を文書の表として受け入れまたは拒絶するためにヒューリスティックを適用するステップとを特徴とする、方法。
【請求項２】
前記複数のタイルが、文書の画像の少なくとも一部をカバーし、所定の重複係数で互いに重複し、所定のタイルサイズを有することを特徴とする、請求項１に記載の方法。
【請求項３】
少なくとも１つの矩形を前記存続線から決定するステップが、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げるステップを含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップが、勾配閾値を決定し、勾配における極大値、それに続いて勾配における極小値を見つけるために勾配を調べるステップであって、極大値と極小値の間の絶対的差違が、勾配閾値より大きい、ステップを含むことを特徴とする、請求項１から３のいずれかに記載の方法。
【請求項５】
存続する線を選択するステップが、前記線の幅に依存する線の存続度を裁定するステップを含むことを特徴とする、請求項１から４のいずれかに記載の方法。
【請求項６】
存続する線を選択するステップが、複数の連続タイルを決定し、連続タイルの数のすべてにおいて前記線の存在に依存する線の存続度を裁定するステップを含むことを特徴とする、請求項１から５のいずれかに記載の方法。
【請求項７】
存続する線を選択するステップが、許容値パラメータを決定し、線が許容値パラメータの値より多い画素によって分離されない連続タイル内の線を、同じ存続線として考えるステップを含むことを特徴とする、請求項１から６のいずれかに記載の方法。
【請求項８】
決定された矩形の受け入れおよび拒絶が、矩形の二次元の高さおよび幅の比によって決まることを特徴とする、請求項１から７のいずれかに記載の方法。
【請求項９】
決定された矩形の受け入れおよび拒絶が、文書の画像のコーナの少なくとも１つにおける矩形の存在および文書の画像の向きによって決まることを特徴とする、請求項１から８のいずれかに記載の方法。
【請求項１０】
技術図面内のタイトルブロックの位置特定に適用される、請求項１から９のいずれかに記載の方法。
【請求項１１】
請求項１から１０のいずれか一項に記載の方法の適用によって文書内で表を自動的に位置特定するための機器。
【請求項１】
文書内で表を自動的に位置特定するための方法であって、
文書のための複数のタイルを定義するステップと、
各々のタイルに対して水平プロファイルおよび垂直プロファイルを決定するステップと、
プロファイルを用いて線を検出するステップと、
少なくとも１つの矩形を線から決定するステップと、
少なくとも１つの矩形から、文書の表としての矩形を受け入れるステップとを含み、
前記方法が、さらに、
水平プロファイルおよび前記垂直プロファイルの１つの勾配を用いて線の位置を決定するステップと、
位置特定された線から、存続する線を選択するステップと、
少なくとも１つの矩形を前記存続線から決定するステップと、
決定された矩形毎に、矩形を文書の表として受け入れまたは拒絶するためにヒューリスティックを適用するステップとを特徴とする、方法。
【請求項２】
前記複数のタイルが、文書の画像の少なくとも一部をカバーし、所定の重複係数で互いに重複し、所定のタイルサイズを有することを特徴とする、請求項１に記載の方法。
【請求項３】
少なくとも１つの矩形を前記存続線から決定するステップが、文書のマージンを決定し、前記マージンを考慮に入れてコーナ内の最大の矩形を取り上げるステップを含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
水平プロファイルおよび垂直プロファイルの１つの勾配を用いて線の位置を決定するステップが、勾配閾値を決定し、勾配における極大値、それに続いて勾配における極小値を見つけるために勾配を調べるステップであって、極大値と極小値の間の絶対的差違が、勾配閾値より大きい、ステップを含むことを特徴とする、請求項１から３のいずれかに記載の方法。
【請求項５】
存続する線を選択するステップが、前記線の幅に依存する線の存続度を裁定するステップを含むことを特徴とする、請求項１から４のいずれかに記載の方法。
【請求項６】
存続する線を選択するステップが、複数の連続タイルを決定し、連続タイルの数のすべてにおいて前記線の存在に依存する線の存続度を裁定するステップを含むことを特徴とする、請求項１から５のいずれかに記載の方法。
【請求項７】
存続する線を選択するステップが、許容値パラメータを決定し、線が許容値パラメータの値より多い画素によって分離されない連続タイル内の線を、同じ存続線として考えるステップを含むことを特徴とする、請求項１から６のいずれかに記載の方法。
【請求項８】
決定された矩形の受け入れおよび拒絶が、矩形の二次元の高さおよび幅の比によって決まることを特徴とする、請求項１から７のいずれかに記載の方法。
【請求項９】
決定された矩形の受け入れおよび拒絶が、文書の画像のコーナの少なくとも１つにおける矩形の存在および文書の画像の向きによって決まることを特徴とする、請求項１から８のいずれかに記載の方法。
【請求項１０】
技術図面内のタイトルブロックの位置特定に適用される、請求項１から９のいずれかに記載の方法。
【請求項１１】
請求項１から１０のいずれか一項に記載の方法の適用によって文書内で表を自動的に位置特定するための機器。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公表番号】特表２０１３−５００５２７（Ｐ２０１３−５００５２７Ａ）
【公表日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１２−５２２０９０（Ｐ２０１２−５２２０９０）
【出願日】平成２２年７月１５日（２０１０．７．１５）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０６０２０５
【国際公開番号】ＷＯ２０１１／０１２４５５
【国際公開日】平成２３年２月３日（２０１１．２．３）
【出願人】（３９００３９４３５）オセ−テクノロジーズ・ベー・ヴエー (103)
【氏名又は名称原語表記】ＯＣＥ’−ＮＥＤＥＲＬＡＮＤ ＢＥＳＬＯＴＥＮ ＶＥＮＮＯＯＴＳＨＡＰ
【Ｆターム（参考）】
【公表日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２２年７月１５日（２０１０．７．１５）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０６０２０５
【国際公開番号】ＷＯ２０１１／０１２４５５
【国際公開日】平成２３年２月３日（２０１１．２．３）
【出願人】（３９００３９４３５）オセ−テクノロジーズ・ベー・ヴエー (103)
【氏名又は名称原語表記】ＯＣＥ’−ＮＥＤＥＲＬＡＮＤ ＢＥＳＬＯＴＥＮ ＶＥＮＮＯＯＴＳＨＡＰ
【Ｆターム（参考）】
[ Back to top ]