JP5952428B2 - ボーダレステーブル検出エンジン - Google Patents

Description

[0001]可変フォーマット文書（flow format document）及び固定フォーマット文書（fixed format document）は、広く用いられているがそれぞれが持つ目的は異なる。可変フォーマット文書は、セクション、パラグラフ、列、及びテーブル等の複雑な論理フォーマット構造を用いて文書を整える。結果として、可変フォーマット文書は柔軟性と修正のしやすさを提供し、頻繁に更新される又は著しく編集がなされる文書に関わるタスクに適している。それに対して固定フォーマット文書は、文字列（text runs）、パス(path)、及びイメージ等の基本的な物理的レイアウト要素を用いて、オリジナルの体裁を保つように文書を整える。固定フォーマット文書は、一貫性のある正確なフォーマットレイアウトを提供し、頻繁に又は大幅に変更されることのない文書又は統一性が望まれる文書に関わるタスクに適している。このようなタスクの例は、記録文書、高品質の複製、及び商業用の出版及び印刷のソースファイルを含む。固定フォーマット文書は、可変フォーマットのソース文書から作成されることが多い。固定フォーマット文書は、物理的（例えば、紙の）文書のデジタル複製（例えば、スキャン及び写真）も含む。

[0002]固定フォーマット文書を編集したくても可変フォーマットのソース文書が利用できない状況では、固定フォーマット文書を可変フォーマット文書に変換しなければならない。変換は、固定フォーマット文書を解析すること、及び固定フォーマット文書の基本的な物理的レイアウト要素を、可変フォーマット文書で使用されるいっそう複雑な論理要素に変形することを含む。ボーダレステーブルなどの複雑な要素に直面した既存の文書変換は、出力文書の可変性を犠牲にして、レイアウトの視覚忠実度を保つよう設計された基本技術（例えば、テキストフレーム、行間隔、及び文字間隔）を用いる。その結果、本当に有用な可変フォーマット文書にするにはユーザが手動による相当な再構成を行う必要がある、限定された可変フォーマット文書になる。これら及びその他の懸念に対してこの発明がなされた。

[0003]この発明の概要は、以下の発明の詳細な説明でさらに述べるコンセプトを簡単に紹介するものである。発明の概要は、特許請求された主題の重要な特徴又は必須の特徴を特定するものではなく、特許請求された主題の範囲を限定するために用いるものでもない。

[0004]ボーダレステーブル検出エンジンの一実施形態は、空白検出を用いてボーダレステーブル候補を選択することで始まる。ボーダレステーブル検出エンジンは、境界ボックスが互いに垂直方向に重なる空白を、空白グループにグループ化する。２つの空白の境界ボックスが垂直方向に重なっている場合、そしてそういう場合に限り、２つの空白の間に端がある（すなわち、空白は結合している）。結合している空白全部で、一つの空白グループを作る。

[0005]空白グループが検出されると、空白グループのそれぞれからテーブル候補が作成される。各空白グループの一番上の空白が特定され、その上境界がテーブル候補の上境界を画定する。同様に、各空白グループの一番下の空白が特定され、その下境界がテーブル候補の下境界を画定する。次に、テーブル候補の上境界と下境界との間のテキスト全てが収集されてテーブル候補に割り当てられる。テキストを収集した後、ボーダレステーブル検出エンジンは、このテーブル候補の境界ボックスを確立する。境界ボックスは、テーブル候補に割り当てられた全てのテキストを含む最小の長方形である。

[0006]最初のテーブル候補のセットが検出された後、ボーダレステーブル検出エンジンは、各テーブル候補を別個に分析する。第１のステップは、テーブル候補をスクリーニングして、見込みの低いテーブル候補を廃棄することである。テーブル候補が最初にスクリーニングされたら、ボーダレステーブル検出エンジンは、残った各テーブル候補のセルレイアウトを再構成する処理を開始する。セルレイアウトを決定する処理は、最小空白幅閾値による空白検出を用いて、列セパレータ候補を決定するステップから開始する。この最狭空白幅閾値は、潜在的な列セパレータを検出するのに有益であるが、列セパレータが存在すべきではない場所、すなわちテーブルセル内、で空白の検出を許してしまう。したがって、列セパレータ検出中に探し出された空白は高さに基づいてスクリーニングされ、しかるべきものは廃棄される。

[0007]空白が廃棄されると、ボーダレステーブル検出エンジンは、残っている空白それぞれの右境界に列セパレータを作成する。次に、ボーダレステーブル検出エンジンは、上境界上又は下境界上にない列セパレータの終端それぞれについて、行セパレータを追加する。利用可能であれば、テキストのレンダリング順といったネイティブな固定フォーマット文書から得た情報を用いて、ボーダレステーブル検出エンジンはボーダレステーブル候補の行をさらに分割する。

[0008]セルレイアウトの再構成の完了時に、ボーダレステーブル検出エンジンは、テキストを個別セルに割り当てる。テキスト割り当て処理は、各テーブル候補をスクリーニングし、ボーダレステーブル候補の前又は後の要素の一部でありそうなテキストを廃棄することから始まる。最後に、一列しか持たないテーブル候補が廃棄される。残りのテーブル候補は、例えばシリアライゼーション中にテーブルとして再構成する準備が整った状態になっている。

[0009]１又は複数の実施形態の詳細は、以下に添付の図面及び説明で述べられている。他の特徴及び利点は以下の詳細な説明を読み、関連図面を検討すれば明らかであろう。なお、以下の詳細な説明は例にすぎず、請求項に記載の発明を制限するものではない。

[0010]さらなる特徴、態様、及び利点は、以下の詳細な説明、添付の請求項、及び付随する図面を参照することで理解が深まるであろう。図面において、要素は詳細をより明確に示す程まではスケールされておらず、複数の図面で同じ番号は同じ要素を指す。

ボーダレステーブル検出エンジンを含むシステムの一実施形態を示すブロック図である。 文書プロセッサの一実施形態の動作フローを示すブロック図である。 ボーダレステーブル検出エンジンにより実行されるボーダレステーブル検出方法の一実施形態のフロー図である。 ボーダレステーブル検出エンジンにより実行されるボーダレステーブル検出方法の一実施形態のフロー図である。 ページ上に現れている２つの空白の様々な位置関係を示す図である。 ページ上に現れている２つの空白の様々な位置関係を示す図である。 ページ上に現れている２つの空白の様々な位置関係を示す図である。 潜在的なボーダレステーブル候補のロケーションを示す例示的な空白グループを示す図である。 最初の空白検出中に特定された空白をもつ例示的なボーダレステーブル候補を示す図である。 空白検出処理中に検出された空白を図示するものである。 ボーダレステーブル検出エンジンの一実施形態で用いられる最小空白高さ／テーブル高さ比のグラフである。 テーブルより下のヘディング及びテーブルより上のパラグラフの一部を収集したボーダレステーブル候補を示す図である。 ボーダレステーブル検出エンジンの一実施形態を実行するタブレットコンピューティング装置を示す図である。 ボーダレステーブル検出エンジンの実施形態を実行するのに適した例示的なコンピューティング装置の簡易ブロック図である。 ボーダレステーブル検出エンジンの一実施形態を実行するモバイルコンピューティング装置の一実施形態を示す図である。 ボーダレステーブル検出エンジンの実施形態を実行するのに適した例示的なモバイルコンピューティング装置の簡易ブロック図である。 ボーダレステーブル検出エンジンの実施形態を実行するのに適した例示的な分散コンピューティングシステムの簡易ブロック図である。

[0011]固定フォーマット文書から抽出されたデータに現れるボーダレステーブルを特定するためのボーダレステーブル検出エンジン及び関連する方法を、本明細書に記述し付随する図面に例示する。目に見える境界がないため、ボーダレステーブルの信頼性のある自動検出は困難である。ボーダレステーブル検出エンジンはコンテンツではなく空白を用いてボーダレステーブル候補を検出する。ヒューリスティックな分析を適用し、ボーダレステーブル検出エンジンは、充分なテーブル特性がなく有効なボーダレステーブルではなさそうなレイアウトを持つボーダレステーブル候補を廃棄する。

[0012]図１は、ボーダレステーブル検出エンジン１００を組み込んだシステムを示す。示されている実施形態では、ボーダレステーブル検出エンジン１００は、コンピューティング装置１０４で実行される文書変換器１０２の一部として動作する。文書変換器１０２は、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４を用いて、固定フォーマット文書１０６を可変フォーマット文書１０８へ変換する。パーサー１１０は、固定フォーマット文書１０６からデータを抽出する。固定フォーマット文書から抽出されたデータは、文書プロセッサ１１２及びシリアライザ１１４によりアクセス可能なデータストア１１６に書き込まれる。文書プロセッサ１１２は、１又は複数の検出エンジン及び／又は再構成エンジン（例えば、本発明のボーダレステーブル検出エンジン１００）を用いて、データを分析し可変可能な要素に変換する。最後に、シリアライザ１１４は、可変可能な要素を可変可能な文書フォーマット（例えばワープロのフォーマット）に書き込む。

[0013]図２は、文書プロセッサ１１２の動作フローの実施形態をより詳細に示す。文書プロセッサ１１２は、オプションの光学式文字認識（ＯＣＲ）エンジン２０２、レイアウト分析エンジン２０４、及び意味解析エンジン２０６を備える。データストア１１６に含まれるデータは、物理レイアウトオブジェクト２０８及び論理レイアウトオブジェクト２１０を含む。いくつかの実施形態では、物理レイアウトオブジェクト２０８及び論理レイアウトオブジェクト２１０は、ツリー状のアレイのグループ（すなわちデータオブジェクト）に階層的に配置される。様々な実施形態において、ページは、物理レイアウトオブジェクト２０８の最上位グループであり、セクションは、論理レイアウトオブジェクト２１０の最上位グループである。固定フォーマット文書１０６から抽出されたデータは、固定フォーマット文書１０６に含まれるページにより組織化される物理レイアウトオブジェクト２０８として記憶されるのが通常である。固定フォーマット文書から取得される基本的な物理レイアウトオブジェクトは、文字列、イメージ、及びパスを含む。文字列は、固定フォーマット文書を表示するとき文字が書かれる場所を指定する、ページコンテンツストリーム内のテキスト要素である。イメージは、固定フォーマット文書１０６に記憶されたラスタ画像（すなわちピクチャ）である。パスは、ベクトルグラフィックスを構成するために用いる、線、曲線（例えば３次ベジェ曲線）、及びテキストアウトライン等の要素を記述する。論理データオブジェクトは、セクション、パラグラフ、列、及びテーブル等の可変可能な要素を含む。

[0014]ここで処理は、解析された固定フォーマット文書１０６のタイプに応じて開始する。可変フォーマットソース文書から直接作成されたネイティブな固定フォーマット文書１０６ａは、基本的な物理的レイアウト要素のいくつか又は全てを含む。一般的に、ネイティブな固定フォーマット文書１０６ａから抽出されたデータは、文書変換器により直ちに使用することができる。ただし、場合によっては、わずかな再フォーマット又は他のわずかな処理を適用してデータを組織化又は標準化する。対照的に、物理的文書をデジタルにイメージ化すること（例えばスキャン又は撮影）により作成されたイメージベースの固定フォーマット文書１０６ｂ内の情報は全て、追加データを持たない（すなわち文字列もパスもない）一連のページイメージとして記憶される。この場合、オプションの光学式文字認識エンジン２０２が、各ページイメージを分析して対応する物理レイアウトオブジェクトを作成する。物理レイアウトオブジェクト２０８が利用可能になると、レイアウト分析エンジン２０４が固定フォーマット文書のレイアウトを決定して新しい情報でデータストアを充実させる（例えば、物理レイアウトオブジェクトを追加、削除、及び更新する）。レイアウト分析が完了した後、意味解析エンジン２０６が、物理レイアウトオブジェクト及び論理レイアウトオブジェクトの双方又は一方の分析から取得した意味情報でデータストアを充実させる。

[0015]図３Ａ〜３Ｂは、ボーダレステーブル検出エンジン１００により実行されるボーダレステーブル検出方法の一実施形態を示す。ボーダレステーブル検出方法３００は、固定フォーマット文書のページのデータ上で実行される空白検出（３１１）を用いて、ボーダレステーブル候補を特定すること（３１０）から始まる。最初の空白検出は、幾何学的には同じ行にあるが、（選択された最小空白幅閾値に基づくと）あまりにも離れていて意味的に同じグループ（例えば同じ文）に属してはいないテキストを発見するために用いられる。したがって、各空白は、ボーダレステーブルが存在する可能性、及びこのボーダレステーブルが問題になっている空白の左及び右の双方又は一方にテキストを含んでいる可能性、を示すものである。最初の空白検出で使用される最小空白幅閾値は、テーブル領域について誤検出の数を最小化するために選択されている。一実施形態では、空白検出処理は、文字列の間に位置する（すなわち垂直方向に重なっている）空白を探し出す。２より多い列又は統合セルを含む１つのテーブルは、複数の空白を含むことになる。ボーダレステーブル検出エンジン１００は、互いに境界ボックスが垂直方向に重なる空白を、空白グループにグループ化する（３１２）。

[0016]図４Ａ〜４Ｃは、ページ上の２つの空白４００ａ、４００ｂの様々な位置関係を示す。図４Ａは、第１の空白４００ａと第２の空白４００ｂとの垂直オーバラップ（すなわち、少なくとも部分的な水平アライメント）４０２の例である。垂直オーバラップは、２つの空白４００ａ、４００ｂの少なくとも一部が水平に並んでいることを示している。図４Ｂは、第１の空白４００ａと第２の空白４００ｂとの水平オーバラップ（すなわち、少なくとも部分的な垂直アライメント）４０４の例である。図４Ｃは、第１の空白４００ａと第２の空白４００ｂとの交差部４０６の例である。交差部は、２つの空白４００ａ、４００ｂの少なくとも一部が水平かつ垂直に並んでいることを示している。垂直オーバラップに基づけば、図４Ａ及び図４Ｃにおける空白は、ボーダレステーブル候補を潜在的に含むページ上の領域を示している。しかし、図４Ｃの空白は廃棄されない。なぜなら水平オーバラップが空白の間にテキストが現れないことを示しているためである。最終的な空白グループは、グラフ上のノードとして表すことができる。ページ上の各空白は、グラフ内の１つのノードである。２つのノード間には、２つの空白の境界ボックスが垂直に重なる場合、そしてそういう場合に限り、端がある（すなわち、ノードは結合している）。結合している空白全部で１つの空白グループを作る。

[0017]図５は、潜在的なボーダレステーブル候補のロケーションを示す例示的な空白グループ５００を示す。空白グループ５００は、数多くの結合空白５０２を含む。空白グループの一番上の空白が特定されて、その上端がボーダレステーブル候補の上境界５０４を画定する。同様に、空白グループの一番下の空白が特定されて、その下端がテーブル候補の下境界５０６を画定する。次に、上境界と下境界との間のテキスト全てが収集されて（３１３）ボーダレステーブル候補に割り当てられる。図６は、例示的なボーダレステーブル候補６００であり、空白検出中に特定された２つの空白６０２及び対応する上境界５０４及び下境界５０６が示されている。空白の上境界及び下境界の間のテキストを収集した後、ボーダレステーブル検出エンジン１００は、ボーダレステーブル候補の境界ボックス６０４を作成する（３１４）。様々な実施形態において、境界ボックス６０４は、ボーダレステーブル候補６００に割り当てられた全てのテキストを含む最小の長方形である。しかし、別の実施形態では境界ボックスの大きさが異なってもよい。

[0018]最初のテーブル候補のセットが検出された後、ボーダレステーブル検出エンジン１００は各テーブル候補を別個に分析する。第１のステップは、テーブル候補をスクリーニングして、見込みの低いテーブル候補を廃棄することである（３２０）。テーブル候補を廃棄するために用いられるテストの１つが、テーブル候補の全領域に関係するテキストによりカバーされるテーブル候補の領域を計算すること（３２１）である。境界のあるテーブルと違って、ボーダレステーブルはコンテンツ（例えば、テキスト又はイメージ）のみを含み、このボーダレステーブルのコンテンツがセルレイアウトを決定することになる。したがって、ボーダレステーブルがテキストをほとんど有しないのに大きな領域をカバーしている、という可能性は低い。テキストカバレッジパーセンテージが、選択された閾値より下であれば、テーブル候補は廃棄される。テーブル候補を廃棄するために用いられる他のテストは、実際には黒丸又は番号付きのリストであるテーブル候補をチェックすることである。黒丸／番号付きのリストは、ボーダレステーブル検出エンジンにとっては、黒丸又は番号の列及びテキストの列、又は垂直の空白により分離された他のコンテンツに見える。黒丸／番号付きのリストとボーダレステーブルとが構造的に類似しているため、黒丸／番号付きのリストはボーダレステーブル候補として特定されてしまう場合がある。したがって、リスト検出を適用することにより、ボーダレステーブル検出エンジン１００は、黒丸／番号付きリストの構造と一致するボーダレステーブル候補を廃棄する（３２２）ことが可能になる。

[0019]テーブル候補が最初にスクリーニングされてから、ボーダレステーブル検出エンジン１００は、残った各テーブル候補のセルレイアウトを再構成する処理（３３０）を開始する。再構成処理は、列の切れ目に対応している可能性のあるより狭い空白を、最小空白幅閾値を用いて検出することで、第２の空白検出を行うこと（３３１）から始まる。最狭空白幅閾値は潜在的な列セパレータの検出にも役立つが、最狭空白幅閾値により列セパレータが存在すべきではない場所、すなわちテーブルセル内における空白の検出が可能である。ボーダレステーブルの場合、セルレイアウトはかなり規則的であって格子状構造をもち統合セルが少ないのが通常である。このため、列の間にある大抵の空白はボーダレステーブルの高さ全体に渡って広がるか、又は少なくともその大部分に渡っている。一実施形態では、空白の高さの閾値は、テーブルの高さ及びテキストの平均高さに依存する。図８は、次式、
minWhitespaceHeight=tableHeight×[1-2/π×arctan(tableHeight/avgTextHeight×factor)]
を用いて計算される最小空白高さ／テーブル高さ比をグラフにしたものであり、因数は定数である。グラフからわかるように、最小空白高さ／テーブル高さ比は、テーブル高さが増加するにつれて減少する。したがって、検出された空白は高さに基づいてスクリーニングされ、しかるべきものが廃棄される。

[0020]高さ閾値を満たさない空白が廃棄される（３３２）と、ボーダレステーブル検出エンジン１００は列セパレータを作成する。図７は、空白検出処理中に、ボーダレステーブル検出エンジン１００により作成された最小空白幅閾値及び列セパレータ７０４を用いて検出された、空白７０２を図示している。列セパレータ７０４は、ボーダレステーブル候補６００における各空白７０２の右境界に置かれている（３３３）。セルレイアウトを完成するために、ボーダレステーブル検出エンジン１００は行セパレータを作成する。有効なセルレイアウトを達成するために、各列セパレータの各終端は、行セパレータ上、テーブル候補の上境界上、又はテーブル候補の下境界上にある必要がある。ボーダレステーブル検出エンジン１００は、上境界又は下境界上にない列セパレータの終端それぞれについて、行セパレータを追加する（３３４）。選択された列セパレータの終端から開始して、ボーダレステーブル検出エンジン１００は、左に現れる最初の列セパレータ（テーブル候補の左境界を含む)まで、及び右に現れる最初の列セパレータ（テーブル候補の左境界を含む）まで（すなわち左／右テーブル境界）まで、水平な線を引く。

[0021]いくつかのネイティブな固定フォーマット文書は、テキストのレンダリング順等の情報を含んでおり、これによりボーダレステーブル検出エンジン１００はボーダレステーブル候補の行をさらに分割することができる。テーブルにおいてセルのレンダリング順は、左から右、上から下であり、これは、ある行中のテキストのレンダリング順がその後の全行中のテキストのレンダリング順よりも若いことを意味する。そのような情報が利用可能な場合、ボーダレステーブル検出エンジン１００は、連続するテキストのラインの間に左境界から右境界へ行セパレータを引き（３３５）、次の不等式、
max(renderingOrder)(X)|X∈textAboveTheRowSeparater)
<min(renderingOrder(Y)|Y∈textBelowTheRowSepartor)
をチェックする。この不等式に当てはまらない場合、この行セパレータは廃棄される。レンダリング順に基づく行セパレータが、列セパレータ検出中に作成された行セパレータと重なるときは、テーブル候補の幅全体に及ぶレンダリング順に基づく行セパレータが優先され、列セパレータ検出中に作成された行セパレータは廃棄される。

[0022]セルレイアウトの再構成の完了時に、ボーダレステーブルのレイアウトの最終決定が行われる（３４０）。図９は、最終セルレイアウト９００の例を示しており、テーブル候補境界６０４、列セパレータ７０４、及び行セパレータ９０２を含む。まず、ボーダレステーブル検出エンジン１００は、テキストを個別セルに割り当てる（３４１）。画定された境界という助けがないため、ボーダレステーブル検出エンジン１００を用いた空白検出は、実際にはボーダレステーブル候補の一部ではないボーダレステーブル候補より上及び下のコンテンツを潜在的に捕えてしまう。例えば、テーブルに先行するパラグラフの最後のライン又はテーブル候補に後続するヘディングが、最初又は最後の列の中身と合う場合は収集されることがある。図９は、最初の行の最初のセル９０６ａに割り当てられた先行するパラグラフの一部と、最後の行の最初のセル９０６ｂに割り当てられたヘディングとを示す。したがって、テキスト割り当て処理は各テーブル候補をスクリーニングし、そのようなテキストを廃棄する（３４２）。より正確には、ボーダレステーブル検出エンジン１００がテーブル候補の行を一番上から分析し、行の最初のセル又は最後のセルのみがテキストを含む場合、その行を廃棄する。この分析は、２つ以上のセルにテキストを含む行に遭遇すると終了する。同じアプローチが下のテーブル行にも用いられ、これは一番下から始まる。スクリーニング処理がいくつかの有効な行をテーブルから除去する可能性が潜在的にあるが、有効ではない行が除去されなかった場合のようにパラグラフが誤って分割されることがないため、このような誤りかたのほうがユーザ経験はより良いものになる。最後に、１列しか持たないボーダレステーブル候補が廃棄される（３４３）。なぜなら、ボーダレステーブル内のこのようなコンテンツは、テーブルの外の通常のコンテンツと同じ方法で再構築されるからである。この段階で、残りのボーダレステーブル候補は、例えばシリアライゼーション中にテーブルとして再構成する準備が整った状態になっている。

[0023]本明細書に述べるボーダレステーブル検出エンジン及び関連するボーダレステーブル検出方法は、固定フォーマット文書のボーダレステーブルに対応する構造を有するコンテンツを検出するのに役立ち、それにより、固定フォーマット文書が可変フォーマット文書に変換されるときにコンテンツを可変可能なテーブルとして再構築できるようにする。本発明は、コンピュータのオペレーティングシステムで実行するアプリケーションプログラムと一緒に実行するプログラムモジュール、という一般的な状況において記述したが、当業者であれば、本発明が他のプログラムモジュールと組み合わせて実装することもできることが解かるであろう。一般に、プログラムモジュールは、ルーティン、プログラム、コンポーネント、データ構造、及び特定のタスクを行うか又は特定の抽象データ型を実装する他のタイプの構造を含む。

[0024]本明細書に記載する実施形態及び機能は、数多くのコンピューティングシステムにより動作することができ、コンピューティングシステムは、デスクトップコンピューティングシステム、有線又は無線のコンピューティングシステム、モバイルコンピューティングシステム（例えば、モバイル電話、ネットブック、タブレット又はスレート型コンピュータ、ノートブックコンピュータ、及びラップトップコンピュータ）、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベース又はプログラマブルの消費者向け家電、ミニコンピュータ、及びメインフレームコンピュータを含むが、これに限定するものではない。図１０は、ボーダレステーブル検出エンジン１００の実施形態を実行する例示的なタブレットコンピューティング装置１０００を示す。さらに、本明細書に記載の実施形態及び機能は、分散型システム（例えば、クラウドベースのコンピューティングシステム）で動作することができ、分散システムでは、アプリケーションの機能、メモリ、データの記憶及び検索、及び様々な処理機能を、インターネット又はイントラネット等の分散コンピューティングネットワーク上で互いから遠隔で操作することができる。様々なタイプのユーザインターフェース及び情報を、コンピューティング装置に搭載されたディスプレイにより、あるいは１又は複数のコンピューティング装置に関連付けされた遠隔のディスプレイユニットにより、表示することができる。例えば、様々なタイプのユーザインターフェース及び情報を壁の表面に表示し、様々なタイプのユーザインターフェース及び情報が投影されている壁の表面上でやりとりを行うことができる。本発明の実施形態を実施できる数多くのコンピューティングシステムとのやりとりは、キーストローク入力、タッチ画面入力、声又は他の音声入力、関連するコンピューティング装置がコンピューティング装置の機能を制御するためにユーザのジェスチャを取り込んで解釈するための検出（例えばカメラ）機能を備えている場合はジェスチャ入力、等を含む。図１１から図１３及びそれに関連する記述では、本発明の実施形態が実行される種々の動作環境について検討する。ただし、図１１から図１３について示され検討される装置及びシステムは例示を目的としたものであり、本明細書に記載した発明の実施形態を実施するために使用できる膨大な数のコンピュータ装置の構成を限定するものではない。

[0025]図１１は、本発明の実施形態を実施することができるコンピューティング装置１１００の物理的部品（すなわち、ハードウェア）の例を示すブロック図である。以下に記述するコンピューティング装置部品は、上述したコンピューティング装置に適合することができる。基本構成では、コンピューティング装置１１００は、少なくとも１つの処理ユニット１１０２及びシステムメモリ１１０４を備えることができる。コンピューティング装置の構成及びタイプにより、システムメモリ１１０４は、揮発性記憶装置（例えばランダムアクセスメモリ）及び非揮発性記憶装置、（例えば読み出し専用メモリ）、フラッシュメモリ、又はそのようなメモリの任意の組み合わせを含んでよいが、これに限定するものではない。システムメモリ１１０４は、オペレーティングシステム１１０５、及びボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４等のソフトウェアアプリケーション１１２０を実行するのに適した１又は複数のプログラムモジュール１１０６を含んでよいが、これに限定するものではない。オペレーティングシステム１１０５は、例えば、コンピューティング装置１１００の動作の制御を行うのに適合するものであってよい。さらに、本発明の実施形態は、グラフィックライブラリ、他のオペレーティングシステム、又は任意の他のアプリケーションプログラムと一緒に実行することができ、任意の特定のアプリケーション又はシステムに限定されない。この基本構成は図１１では点線１１０８内の部品により示されている。コンピューティング装置１１００は、追加的な特徴又は機能を備えることができる。例えば、コンピューティング装置１１００は、例えば、磁気ディスク、光ディスク、又はテープ等の追加的なデータ記憶装置（取り外し可能及び取り外し不可能なものの双方又は一方）を含むこともできる。このような追加的な記憶装置は図１１では取り外し可能記憶装置１１０９、取り外し不可能な記憶装置１１１０により示されている。

[0026]上述したように、数多くのプログラムモジュール及びデータファイルを、システムメモリ１１０４に記憶することができる。ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４等のプログラムモジュール１１０６は、処理ユニット１１０２で実行している間に、例えばボーダレステーブル検出方法３００の１又は複数のステージを含む処理を行うことができる。上記の処理は例であり、処理ユニット１１０２は他の処理を行ってもよい。本発明の実施形態により用いることができる他のプログラムモジュールは、電子メール及びコンタクトアプリケーション、ワープロアプリケーション、表計算アプリケーション、データベースアプリケーション、スライドプレゼンテーションアプリケーション、描画又はコンピュータ支援アプリケーションプログラム等を含むことができる。

[0027]さらに、本発明の実施形態は、離散した電子素子を備えた電気回路、論理ゲートを含むパッケージ化された又は集積された電子チップ、マイクロプロセッサを使用する回路、又は電子素子又はマイクロプロセッサを含む単一チップで実施される。例えば、本発明の実施形態は、図１１に示した部品それぞれ又は部品の多くを単一の集積回路上に集積することができるシステムオンチップ（ＳＯＣ）により実施することができる。このようなＳＯＣ装置は、１又は複数の処理ユニット、グラフィックスユニット、通信ユニット、システム仮想化ユニット及び様々なアプリケーション機能を全て、単一の集積回路としてチップ基板上に集積（又は「焼き付け」）した状態で含むことができる。ＳＯＣで動作するときは、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４に関する本明細書に記載の機能は、単一の集積回路（チップ）上にコンピューティング装置１１００の他の部品とともに集積された、特定用途向けの論理で動作することができる。本発明の実施形態は、例えば、ＡＮＤ、ＯＲ、及びＮＯＴ等の論理動作を実行することができる他の技術を用いて実施することもでき、機械的、光学的、流体的、及び量子力学的な技術を含むがこれに限定するものではない。さらに、本発明の実施形態は、汎用コンピュータ内で又は任意の他の回路又はシステムで実施することができる。

[0028]コンピューティング装置１１００は、キーボード、マウス、ペン、音声入力装置、タッチ入力装置等の１又は複数の入力装置１１１２を含むことができる。ディスプレイ、スピーカ、プリンタ等の出力装置１１１４を含んでもよい。上記の装置は例であって他のものを用いてもよい。コンピューティング装置１１００は、他のコンピューティング装置１１１８との通信を可能にする１又は複数の通信接続１１１６も含むことができる。適切な通信接続１１１６の例は、ＲＦトランスミッタ回路、レシーバ回路及び／又はトランシーバ回路、ユニバーサルシリアルバス（ＵＳＢ）ポート、パラレルポート、又はシリアルポート、及び適用できるコンピュータ可読媒体とともに使用するのに適した他の接続を含むが、それに限定するものではない。

[0029]本発明の実施形態は、例えば、コンピュータ処理（方法）、コンピューティングシステム、又はコンピュータプログラム製品やコンピュータ可読媒体等の製品として実装することができる。コンピュータプログラム製品は、コンピューティングシステムが読めるものであってコンピュータ処理を実行するための命令であるコンピュータプログラム、をエンコードしているコンピュータ記憶媒体であってもよい。

[0030]本明細書においてコンピュータ可読媒体という用語は、コンピュータ記憶媒体及び通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータ等の情報を記憶するために任意の方法又は技術で実装される、揮発性及び非揮発性の記憶媒体、取り外し可能及び取り外し不可能な記憶媒体を含むことができる。システムメモリ１１０４、取り外し可能な記憶装置１１０９、及び取り外し不可能な記憶装置１１１０は全て、コンピュータ記憶媒体例（すなわち、メモリストレージ）である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、電気的に消去可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリ又は他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）又は他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置又は他の磁気記憶装置、又は情報を記憶するために使用することができコンピューティング装置１１００によりアクセス可能な任意の他の媒体を含むことができるが、これに限定するものではない。任意のこのようなコンピュータ記憶媒体がコンピューティング装置１１００の一部になり得る。

[0031]通信媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、又は搬送波や他の輸送機構等の変調されたデータ信号内の他のデータ、により具体化されるものであり、任意の情報配信媒体を含む。「変調されたデータ信号」という用語は、情報を信号の中にエンコードするように設定又は変更される１又は複数の特徴を有する信号である。例であってこれに限定するものではないが、通信媒体は、有線ネットワーク又は直接有線接続等の有線媒体、及び音響、ラジオ周波数（ＲＦ）、赤外線、及び他のワイヤレス媒体等のワイヤレス媒体を含んでもよい。

[0032]図１２Ａ及び図１２Ｂは、例えば、移動電話、スマートフォン、タブレットパーソナルコンピュータ、ラップトップコンピュータ等の本発明の実施形態を実施することができるモバイルコンピューティング装置１２００を示す。図１２Ａを参照すると、本実施形態を実装するための例示的なモバイルコンピューティング装置１２００が示されている。基本構成では、モバイルコンピューティング装置１２００は、入力要素及び出力要素の両方を有するハンドヘルドコンピュータである。モバイルコンピューティング装置１２００は、典型的にはディスプレイ１２０５及びユーザがモバイルコンピューティング装置１２００へ情報を入力することを可能にする１又は複数の入力ボタン１２１０を含む。モバイルコンピューティング装置１２００のディスプレイ１２０５は、入力装置（例えば、タッチクリーンディスプレイ）としても機能することができる。オプションの副入力要素１２１５が含まれていれば、さらなるユーザ入力が可能になる。副入力要素１２１５は、ロータリースイッチ、ボタン、又は任意の他のタイプの手動入力要素であってよい。代替的な実施形態では、モバイルコンピューティング装置１２００は、より多くの又はより少ない入力要素を組み込んでいてもよい。例えば、いくつかの実施形態ではディスプレイ１２０５はタッチスクリーンではないかもしれない。さらに他の代替的な実施形態では、モバイルコンピューティング装置１２００は、セルラー電話等の携帯電話システムである。モバイルコンピューティング装置１２００は、オプションのキーパッド１２３５を含むこともできる。オプションのキーパッド１２３５は、物理キーパッド又はタッチスクリーンディスプレイ上に生成された「ソフト」キーパッドであってもよい。さまざまな実施形態において、出力要素は、グラフィカルユーザインターフェース（ＧＵＩ）、視覚インジケータ１２２０（例えば、発光ダイオード）、及びオーディオトランスデューサ１２２５（例えば、スピーカ）のうちの１つ以上を示すための、ディスプレイ１２０５を含む。いくつかの実施形態では、モバイルコンピューティング装置１２００は、ユーザに触覚フィードバックを提供する振動トランスデューサを組み込んでいる。さらに別の実施形態では、モバイルコンピューティング装置１２００は、外部装置への信号の送信又は外部装置からの信号の受信を行うための、音声入力（例えば、マイクロフォンジャック）、音声出力（例えばヘッドフォンジャック）、及び映像出力（例えば、ＨＤＭＩ（登録商標）ポート）等の、入力ポート及び出力ポートの双方又は一方を組み込んでいる。

[0033]図１２Ｂは、モバイルコンピューティング装置の一実施形態のアーキテクチャを示すブロック図である。つまり、モバイルコンピューティング装置１２００は、いくつかの実施形態を実装するためのいくつかのシステム（すなわち、アーキテクチャ）１２０２を組み込むことができる。一実施形態では、システム１２０２は、１又は複数のアプリケーション（例えば、ブラウザ、電子メール、カレンダリング、コンタクトマネージャ、メッセージングクライアント、ゲーム、及びメディアクライアント／プレイヤ）を実行する「スマートフォン」として実装される。いくつかの実施形態では、システム１２０２は、個人用携帯情報端末（ＰＤＡ）とワイヤレス電話とが統合されたもの等のコンピューティング装置として実装される。

[0034]１又は複数のアプリケーションプログラム１２６６は、メモリ１２６２にロードされて、オペレーティングシステム１２６４上で又はオペレーティングシステム１２６４と関連付けられて実行することができる。アプリケーションプログラムの例は、電話ダイヤラプログラム、電子メールプログラム、個人情報管理（ＰＩＭ）プログラム、ワープロプログラム、表計算プログラム、インターネットブラウザプログラム、メッセージングプログラム、その他を含む。システム１２０２は、メモリ１２６２内の非揮発性記憶領域１２６８も含む。非揮発性記憶領域１２６８は、システム１２０２の電源が切れても失われてはならない永続性の情報を記憶するために使用することができる。アプリケーションプログラム１２６６は、電子メール又は電子メールアプリケーションにより使用される他のメッセージ等の、非揮発性記憶領域１２６８内の情報を使用すること及び記憶することができる。同期アプリケーション（図示せず）もシステム１２０２にあり、ホストコンピュータにある対応する同期アプリケーションとやりとりを行い、非揮発性記憶領域１２６８に記憶された情報をホストコンピュータに記憶された対応する情報と同期させておくようプログラムされている。当然ながら、他のアプリケーションをメモリ１２６２にロードしてモバイルコンピューティング装置１２００で実行してもよく、このようなアプリケーションは本明細書で述べたボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアイザ１１４等を含む。

[0035]システム１２０２は、１又は複数の電池として実装することができる電源１２７０を備えている。電源１２７０は、電池を補完又は再充電するＡＣアダプタ又は電源供給用ドッキングクレードル等の外部電源をさらに含むこともある。

[0036]システム１２０２は、ラジオ周波数通信を伝送及び受信する機能を実行するラジオ１２７２も含むことができる。ラジオ１２７２は、通信事業者又はサービスプロバイダを介して、システム１２０２と「外部世界」との間のワイヤレス通信を容易にする。ラジオ１２７２への伝送及びラジオ１２７２からの伝送は、オペレーティングシステム１２６４の制御の下で行われる。言い換えれば、ラジオ１２７２が受信した通信は、オペレーティングシステム１２６４を介してアプリケーションプログラム１２６６へ広まり、その逆もまた然りである。

[0037]ラジオ１２７２は、システム１２０２がネットワーク上等で他のコンピューティング装置と通信することを可能にする。ラジオ１２７２は、通信媒体の一例である。通信媒体は、典型的にはコンピュータ可読命令、データ構造、プログラムモジュール、又は搬送波や他の輸送機構等の変調されたデータ信号内の他のデータ、により具体化されるものであり、任意の情報配信媒体を含む。「変調されたデータ信号」という用語は、情報を信号の中にエンコードするように設定又は変更される１又は複数の特徴を有する信号である。例であってこれに限定するものではないが、通信媒体は、有線ネットワーク又は直接有線接続等の有線媒体、及び音響、ラジオ周波数（ＲＦ）、赤外線、及び他のワイヤレス媒体等のワイヤレス媒体を含んでもよい。本明細書においてコンピュータ可読媒体という用語は、記憶媒体及び通信媒体の両方を含む。

[0038]システム１２０２のこの実施形態は、視覚通知を提供するために使用できる視覚インジケータ１２２０、及びオーディオトランスデューサ１２２５を介して可聴通知を生成する音声インターフェース１２７４の双方又は一方を用いて、通知を提供する。示されている実施形態では、視覚インジケータ１２２０は発光ダイオード（ＬＥＤ）であり、オーディオトランスデューサ１２２５はスピーカである。これらの装置は電源１２７０へ直接接続されているので、起動されると、たとえプロセッサ１２６０及び他の部品が電池節約のためにシャットダウンする可能性がある場合でも、通知機構に指示された持続時間の間はオンのままである。ＬＥＤは、ユーザがこの装置の電源オン状態を指示する処置をとるまでは無制限にオンの状態であるようにプログラムすることができる。音声インターフェース１２７４は、ユーザへ可聴信号を提供しユーザから可聴信号を受信するために用いられる。例えば、音声インターフェース１２７４は、オーディオトランスデューサ１２２５に接続されるだけでなく、可聴入力を受信するマイクロフォンにも接続されることにより、電話の会話を容易にすること等が可能である。本発明の実施形態によれば、マイクロフォンは通知の制御を容易にする音声センサとしても機能することができ、これについては後述する。システム１２０２は、搭載カメラ１２３０が静止イメージ、映像ストリーム、等を記録する動作をできるようにする映像インターフェース１２７６、をさらに含んでもよい。

[0039]システム１２０２を実装しているモバイルコンピューティング装置１２００は、追加的な特徴又は機能を備えることができる。例えば、モバイルコンピューティング装置１２００は、磁気ディスク、光ディスク、又はテープ等の追加的なデータ記憶装置（取り外し可能及び取り外し不可能なものの双方又は一方）を含むこともできる。このような追加的な記憶装置は、図１２Ｂでは非揮発性記憶領域１２６８により示されている。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータ等の情報を記憶するために任意の方法又は技術で実装される、揮発性及び非揮発性の媒体、取り外し可能及び取り外し不可能な媒体を含むことができる。

[0040]モバイルコンピューティング装置１２００により生成又は捕えられてシステム１２０２を介して記憶されたデータ／情報は、上述したようにモバイルコンピューティング装置１２００にローカルに記憶されるか、あるいは、データは装置１２００がアクセスできる任意の数の記憶媒体に記憶されてもよく、このアクセスは、ラジオ１２７２を介して、又はモバイルコンピューティング装置１２００とモバイルコンピューティング装置１２００と関連付けされた別個のコンピューティング装置、例えばインターネット等の分散コンピューティングネットワークにおけるサーバコンピュータ、との有線接続を介して行うことができる。当然ながら、このようなデータ／情報は、ラジオ１２７２を介して、又は分散コンピューティングネットワークを介してモバイルコンピューティング装置１２００によりアクセスされ得る。同様に、このようなデータ／情報は、電子メール及び共同のデータ／情報共有システムを含む周知のデータ／情報伝送及び記憶手段に従って記憶及び使用するために、コンピューティング装置間で容易に伝送することができる。

[0041]図１３は、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４を、上述したように１又は複数のクライアント装置へ提供するためのシステムのアーキテクチャの一実施形態を示す。ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４と関連して作成、やりとり、又は編集が行われたコンテンツは、さまざまな通信チャネル又は他のタイプの記憶装置に記憶することができる。たとえば、種々の文書は、ディレクトリサービス１３２２、ウェブポータル１３２４、メールボックスサービス１３２６、インスタントメッセージングストア１３２８、又はソーシャルネットワーキングサイト１３３０を用いて記憶することができる。これらのタイプのシステムその他のうち任意のものを用いて、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４は、本明細書で述べたようにデータの利用を可能にすることがきる。サーバ１３２０は、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４をクライアントに提供することができる。一例として、サーバ１３２０は、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４をウェブ上で提供するウェブサーバであってもよい。サーバ１３２０は、ネットワーク１３１５を経由して、ボーダレステーブル検出エンジン１００、パーサー１１０、文書プロセッサ１１２、及びシリアライザ１１４を、ウェブ上でクライアントに提供することができる。例を挙げると、クライアントコンピューティング装置１３１８は、コンピューティング装置１１００として実装され、パーソナルコンピュータ１３１８ａ、タブレットコンピューティング装置１３１８ｂ、及びモバイルコンピューティング装置１３１８ｃ（例えばスマートフォン）のうちの１つ以上に具体化することができる。クライアントコンピューティング装置１３１８のこれらの実施形態はいずれも、ストア１３１６からコンテンツを取得することができる。さまざまな実施形態では、本発明を構成するコンピューティング装置間の通信に用いられるネットワークのタイプは、インターネット、イントラネット、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、及び仮想プライベートネットワーク（ＶＰＮ）を含むが、これに限定するものではない。本出願において、ネットワークは、企業ネットワーク、及びクライアントコンピューティング装置が企業ネットワークへアクセスするために経由するネットワーク（すなわち、クライアントネットワーク）を含む。一実施形態では、クライアントネットワークは企業ネットワークの一部である。別の実施形態では、クライアントネットワークは、ゲートウェイ、遠隔アクセスプロトコル、あるいはパブリック又はプライベートなインターネットアドレス等の外部から利用可能なエントリポイントを経由して企業ネットワークへアクセスする、別個のネットワークである。

[0042]本出願で提供された１又は複数の実施形態についての記載及び例示は、特許請求される本発明の範囲を決して限定又は制限するものではない。この出願で提供された実施形態、例、及び詳細は、特許請求された発明の有する権利を伝え、その最良の形態を他者が作成及び使用するのに充分なものであると考える。この特許請求された発明は、この出願で提供された任意の実施形態、例、又は詳細に限定されるものと見なすべきではない。種々の特徴（構造的なもの及び方法的なものの両方）は、図示及び説明が一緒に行われたか別個に行われたかに関わらず、特定の一連の特徴をもつ実施形態を作り出すために選択的に包含又は省略されるものとする。本出願の記述及び例示に触れた当業者であれば、特許請求された発明の広範な態様の精神及びこの出願で具体化された発明概念全体の範囲にあって特許請求された発明の広い範囲から逸脱しない、変形実施形態、修正実施形態、及び代替実施形態を想像することができるであろう。

Claims (17)

1. 固定フォーマット文書から解析されたデータに含まれるボーダレステーブルを検出するためのボーダレステーブル検出方法であって、前記方法は、
   互いに垂直オーバラップを有する空白を、上境界及び下境界を有する空白グループにグループ化するステップと、
   前記空白グループの上境界と下境界との間にあるテキストを、被収集テキストとして収集するステップと、
   前記被収集テキストを含むとともに上境界、下境界、左境界、右境界を有するテーブル候補内で検出された空白のそれぞれの右端に位置する列セパレータを作成するステップであって、前記列セパレータのそれぞれは一対の終端を画定している、ステップと、
   複数の個別セルを形成するために、選択された前記終端にある行セパレータを含む第１の行セパレータのセットを作成するステップと、
   被収集テキストを、前記複数の個別セルのうちの対応する１つに割り当てるステップと、
   レンダリング順の情報が前記固定フォーマット文書から利用可能なとき、前記固定フォーマット文書から取得された前記レンダリング順に基づいて、前記テーブル候補内のテキストの連続するラインの間に第２の行セパレータのセットを作成するステップと、
   前記行セパレータより上にある前記被収集テキストの最大の垂直位置又はレンダリング順が、前記行セパレータより下にある前記被収集テキストの最小の垂直位置又は前記レンダリング順よりも大きいとき、前記第２の行セパレータのセットのうちの前記行セパレータを廃棄するステップと、
   前記第１の行セパレータのセットのうちの第１の前記行セパレータが、前記第２の行セパレータのセットのうちの第２の前記行セパレータと同一線上にあるとき、前記第１の行セパレータを廃棄するステップと、
   を含む、ボーダレステーブル検出方法。
2. 固定フォーマット文書から解析されたデータに含まれるボーダレステーブルを検出するためのボーダレステーブル検出方法であって、前記方法は、
   互いに垂直オーバラップを有する空白を、上境界及び下境界を有する空白グループにグループ化するステップと、
   前記空白グループの上境界と下境界との間にあるテキストを、被収集テキストとして収集するステップと、
   前記被収集テキストを含むとともに上境界、下境界、左境界、右境界を有するテーブル候補内で検出された空白のそれぞれの右端に位置する列セパレータを作成するステップであって、前記列セパレータのそれぞれは一対の終端を画定している、ステップと、
   複数の個別セルを形成するために、選択された前記終端にある行セパレータを含む第１の行セパレータのセットを作成するステップと、
   被収集テキストを、前記複数の個別セルのうちの対応する１つに割り当てるステップと、
   前記テーブル候補内で黒丸付きリスト及び番号付きリストの双方又は一方を検出するステップと、
   前記テーブル候補が前記黒丸付きリスト及び番号付きリストの双方又は一方を、１つしか含まない場合、前記テーブル候補を廃棄するステップと
   を含む、ボーダレステーブル検出方法。
3. 請求項１又は２に記載のボーダレステーブル検出方法であって、前記テーブル候補内で検出された前記空白のそれぞれが、前記テーブル候補の高さの大部分に対応する高さ閾値を超える高さを有する、方法。
4. 請求項３に記載のボーダレステーブル検出方法であって、前記高さ閾値は、前記テーブル候補の高さ及び前記被収集テキストの平均高さに応じて変化する、方法。
5. 請求項１〜４のいずれか一項に記載のボーダレステーブル検出方法であって、第１の行セパレータのセットを作成する前記ステップは、
   前記上境界及び前記下境界のいずれにもかからない前記終端のそれぞれから、別の前記列セパレータ又は前記左境界と交わるまで左へ延びる水平な線を引くステップと、
   前記上境界及び前記下境界のいずれにもかからない前記終端のそれぞれから、別の前記列セパレータ又は前記右境界と交わるまで右へ延びる水平な線を引くステップと
   をさらに含む、方法。
6. 請求項１〜５のいずれか一項に記載のボーダレステーブル検出方法であって、
   前記被収集テキストによりカバーされる前記テーブル候補の領域に対応するテキストカバレッジパーセンテージを計算するステップと、
   前記テキストカバレッジパーセンテージが、選択されたテキストカバレッジパーセンテージ閾値に満たない場合、前記テーブル候補を廃棄するステップと、
   をさらに含む、方法。
7. 請求項１〜６のいずれか一項に記載のボーダレステーブル検出方法であって、前記列セパレータにより画定された各行が最初のセル及び最後のセルを有し、前記方法は、前記被収集テキストが行の前記最初のセル又は前記最後のセルのみに割り当てられている場合その行を廃棄するステップ、をさらに含む方法。
8. 請求項１〜７のいずれか一項に記載のボーダレステーブル検出方法であって、一列しか含まないテーブルを廃棄するステップ、をさらに含む方法。
9. 請求項１〜８のいずれか一項に記載の方法を実行するためのプログラム。
10. 請求項１〜８のいずれか一項に記載の方法を実行するためのプログラムを記録した記録媒体。
11. 固定フォーマット文書に現れるボーダレステーブルを検出するためのシステムであって、前記システムはボーダレステーブル検出エンジンアプリケーションを含み、該アプリケーションは、
    第１の最小空白幅閾値を用いて、ページ上の空白を検出するよう動作し、
    互いに垂直オーバラップを有する空白を、上境界及び下境界を有する空白グループにグループ化するよう動作し、
    前記空白グループの上境界と下境界との間にあるテキストを、被収集テキストとして収集するよう動作し、
    テーブル候補を形成するために前記被収集テキストの周りに境界ボックスを作成するよう動作し、前記境界ボックスは上境界、下境界、左境界、右境界を有するものであり、
    第２の最小空白幅閾値を用いて、前記テーブル候補内の空白を検出するよう動作し、前記第２の最小空白幅閾値は前記第１の最小空白幅閾値よりも小さいものであり、
    前記テーブル候補内の前記空白のそれぞれの右端に位置する列セパレータを作成するよう動作し、前記列セパレータのそれぞれは一対の終端を画定しており、
    複数の個別セルを形成するために、前記境界ボックスの前記上境界及び前記境界ボックスの前記下境界のいずれにもかからない前記終端のそれぞれにある行セパレータを含む第１の行セパレータのセットを作成するよう動作し、かつ
    被収集テキストを、前記複数の個別セルのうちの対応する１つに割り当てるよう動作し、前記行セパレータにより画定された各行は最初のセル及び最後のセルを有するものである、
    システム。
12. 請求項１１に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、前記テーブル候補の高さの大部分に対応する高さ閾値を超えるとともに前記テーブル候補の高さ及び前記被収集テキストの平均高さに応じて変化する高さ、を有する前記テーブル候補内で検出された空白から、列セパレータを作成するよう動作する、システム。
13. 請求項１１又は１２に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、前記境界ボックスの上境界及び前記境界ボックスの下境界のいずれにもかからない前記終端の各側へ、前記終端の各側上の別の前記列セパレータと交わるまで延びる、水平な線を引くように動作する、システム。
14. 請求項１１〜１３のいずれか一項に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、レンダリング順の情報が前記固定フォーマット文書から利用可能なとき、前記固定フォーマット文書から取得された前記レンダリング順の情報に基づいて、前記テーブル候補内のテキストの連続するラインの間に第２の行セパレータのセットを作成するよう動作し、
    前記行セパレータより上にある前記被収集テキストの最大の垂直位置又はレンダリング順が、前記行セパレータより下にある前記被収集テキストの最小の垂直位置又はレンダリング順よりも大きいとき、前記第２の行セパレータのセットのうちの前記行セパレータを廃棄するよう動作し、かつ
    前記第１の行セパレータのセットのうちの第１の前記行セパレータが、前記第２の行セパレータのセットのうちの第２の前記行セパレータと同一線上にあるとき、前記第１の行セパレータを廃棄するよう動作する、
    システム。
15. 請求項１１〜１４のいずれか一項に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、前記被収集テキストによりカバーされる前記テーブル候補の領域に対応するテキストカバレッジパーセンテージが、選択されたテキストカバレッジパーセンテージ閾値に満たない場合、前記テーブル候補を廃棄するよう動作する、
    システム。
16. 請求項１１〜１５のいずれか一項に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、複数の個別セルを含むセルレイアウトを形成するために、前記境界ボックスの前記上境界及び前記境界ボックスの前記下境界のいずれにもかからない前記終端のそれぞれ、及び前記固定フォーマット文書から取得されたレンダリング順の情報を用いて決定される前記テーブル候補内のテキストの連続するライン、からなる群より選択された垂直位置に位置する行セパレータを作成するステップ、をさらに含むシステム。
17. 請求項１１〜１６のいずれか一項に記載のシステムであって、前記ボーダレステーブル検出エンジンアプリケーションは、前記被収集テキストが、行の前記最初のセル又は前記最後のセルのみに割り当てられている場合、その行を廃棄するように動作する、システム。

Images