JP2008171411A - 動的なコネクタ解析のための方法及び装置 - Google Patents

Abstract

【課題】編集可能なドキュメントを作成する方法を提供する。
【解決手段】グラフィカルオブジェクトのビットマップ表現、及び線オブジェクトのビットマップ表現を検出する。また、グラフィカルオブジェクトを複数のテンプレート形状とマッチングし、当該テンプレート形状は不連続な接続点を有する。また、線オブジェクトの少なくとも１つの終端が接続点のうちの１つの予め定められた距離内にある場合に線オブジェクトに対して当該接続点の１つを選択し、関連付ける。さらに、そのテンプレート形状に接続された線オブジェクトとともに当該テンプレート形状を含む編集可能なドキュメントを作成し、線オブジェクトは、ドキュメント内でテンプレート形状が修正されるときに当該選択された接続点と関連付けられたままであり、その結果、線オブジェクトはテンプレート形状に動的に接続されたままである。
【選択図】図１１

Description

本発明は、概してドキュメント解析に関し、具体的にはドキュメントを作成する方法、装置、及びドキュメントを作成するためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体に関するものである。

高まり続ける計算処理能力と相まった走査（スキャン）技術の普及は、ドキュメント解析システムの領域において多くの進歩をもたらした。これらのシステムは、例えば光学式文字認識（ＯＣＲ）技術を用いて、スキャンされたドキュメントから意味情報を抽出するために使用される。この技術は、自動帳票読み取りなどのより多くのアプリケーションにおいて使用される。ドキュメント解析システムは、ドキュメントのページの各部のコンテンツに応じて適切な圧縮方法を選択的に使用することによってドキュメントの電子的な表現の圧縮を改善させるためにも使用される。改善されたドキュメントの圧縮は、アーカイブ及び電子配信などの用途に適している。

かなりの割合のオフィスドキュメントが、Ｍｉｃｒｏｓｏｆｔ（商標）Ｗｏｒｄ（商標）、Ｍｉｃｒｏｓｏｆｔ（商標）Ｐｏｗｅｒｐｏｉｎｔ（商標）などの構造化されたテキスト／グラフィックス編集アプリケーションを使用して作成される。定型化されたテキスト編集に加えて、これらのテキスト／グラフィックス編集アプリケーションは、基本的な図形描画ツール及びオプションを含む。ドキュメント解析アプリケーションの重要な種類はドキュメントのビットマップ表現を処理して、そのような編集アプリケーションを使用して閲覧され、編集可能なドキュメントの電子的形態を生成する。そのようなドキュメント解析アプリケーションは、「スキャントゥエディタブル（ｓｃａｎ−ｔｏ−ｅｄｉｔａｂｌｅ）」ドキュメント解析アプリケーションと呼ばれる。

典型的な構造化されたテキスト／グラフィックス編集アプリケーションの図形描画オプションは、自由な線の描画、テンプレート形状、及びコネクタ（即ち、ドキュメント内のテンプレート形状に接続する、及び／又はドキュメント内のテンプレート形状の間を接続する動的な線オブジェクト）を含む。また、テキスト／グラフィックス編集アプリケーションは、オブジェクトの組に対する彩色、塗り潰し、レイヤ化、及びグループ化オプションを含んでもよい。

自由な線の描画は、オブジェクトの経路に沿って１組の点を定義することによって直線部分又は曲線部分を用いて開いたオブジェクト及び閉じたオブジェクトを描画するために使用される。閉じたＮ点多角形は、順序付けられた１組の頂点を定義することによって描画される。例えば、図１は、線多角形１００上の黒い正方形によって表される頂点（例えば、１０１）を含む一般的な線多角形１００を示す。自由に描画されるオブジェクトは、単色、透明、混合、及びパターンを含む塗り潰しオプションを適用可能な範囲で塗り潰されるか、又は塗り潰されない場合もある。

多くの通常使用される幾何学形状は、テンプレート形状を使用して作成される。ユーザは、テンプレート形状のオプションの方がより早く、所望の形状の表現の点でより正確であり、後で編集するのが容易であるために、自由な線を使用して形状を描画するよりもテンプレート形状を使用することを好む可能性がある。よく知られているＭｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓの組は、Ｍｉｃｒｏｓｏｆｔ（商標）Ｗｏｒｄ（商標）及びＰｏｗｅｒＰｏｉｎｔ（商標）などの編集環境内で操作されるテンプレート形状のいくつかの例を含む。その他のテンプレート形状は、Ｗｒｉｔｅｒ（商標）及びＩｍｐｒｅｓｓ（商標）アプリケーションなどのＯｐｅｎＯｆｆｉｃｅ（商標）編集アプリケーションにおいて見られる。

通常、テンプレート形状は、オフィスドキュメントにおいて、特に図形及びフローチャートで見られる。いくつかのテンプレート形状の例４０５〜４６０を図４に示す。通常、図４に示すように、塗り潰されていない線オブジェクト４０５〜４２０、同色の中身が塗り潰されたオブジェクト４２５〜４４０、又は異なる色の中身が塗り潰されたオブジェクト４４５〜４６０を含む塗り潰しオプションの範囲が、線、透明、混合、又はパターン塗り潰しに対して利用可能である。

上述のように、コネクタはドキュメント内のテンプレート形状を接続する動的な線オブジェクトである。そのような線オブジェクトは、直線コネクタと屈曲したコネクタとを含む。コネクタを形成する線オブジェクトは、矢尻形状を有するか、又はその他の線の終端の効果を有する。図２に示すように、テンプレート形状が編集又は移動されると、当該テンプレート形状に接続された任意のコネクタは変更に合わせて更新され、接続されたままに保たれる。図２（ａ）は、両端に矢尻形状を有する直線コネクタ２１０と、終端の効果を有していない屈曲したコネクタ２２０とによって接続された３つの形状、角丸長方形２０５、菱形２１５、及び缶２２５を示す。図２（ｂ）は、形状２０５、２１５、２２５並びにコネクタ２１０、２２０の同じ組を示す。しかし、菱形２１５はその他の形状２０５、２２５に対して上方に移動されている。コネクタの２１０、２２０の両方はこの移動に応じて更新されており、直線コネクタ２１０は今度は斜めにされ、屈曲したコネクタ２２０は方向が裏返しにされている。図２（ｃ）は、形状２０５、２１５、２２５及びコネクタ２１０、２２０の同じ組を示す。しかし、図２（ｃ）において、菱形２１５は右下に移動されている。コネクタ２１０、２２０はそれに応じて更新されており、屈曲したコネクタ２２０は重なりなしに２つの形状２１５、２２５を接続するためにさらなる２つの折り返しを含む。コネクタを形成する線オブジェクトの例は、Ｍｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓの中に見ることができる。

いくつかの構造化された／テキスト編集アプリケーションにおいて、コネクタは、既定の接続点における有限の組においてテンプレート形状に接続することのみ可能である。概して、これらの既定の接続点は、対称的に、及び予め定められたテンプレート形状の境界周囲における外向きに突き出た点に配置される。図３は、１組の塗り潰されていないテンプレート形状３０１〜３２１を示す。テンプレート形状のそれぞれ（例えば、３０１）は、テンプレート形状の境界上に配置された中身が塗り潰された四角として表される接続点の対応する組を含む。図３の形状の組は、四角形（３０１）、角丸四角形（３０２）、楕円（３０３）、三角形（３０４）、平行四辺形（３０５）、台形（３０６）、六角形（３０７）、プラス記号（３０８）、星（３０９）、矢印（３１０）、ホームベース（３１１）、吹き出し（３１２）、ブローチ（３１３）、山形（３１４）、８角シール（３１５）、１６角シール（３１６）、３２角シール（３１７）、くさび四角形コールアウト（３１８）、くさび角丸四角形コールアウト（３１９）、くさび楕円コールアウト（３２０）、及び波形（３２１）を含む。

既存のスキャントゥエディタブルアプリケーションは、テキスト及び表の処理に偏っている傾向があり、一般的に図形の処理に効果的に対処していない。そのようなスキャントゥエディタブルアプリケーションは、光学式文字認識（ＯＣＲ）処理を使用してドキュメントの画像から文字及び単純な記号を認識することができる。多くの基本的なスキャントゥエディタブルアプリケーションは、テキスト又は表として認識されない画像の部分を概して圧縮された形式の、及びときには低解像度のビットマップ画像として単に組み入れる。そのような基本的なスキャントゥエディタブルアプリケーションは、組み入れられたビットマップ画像が幾何学的描画ツールを使用して容易に編集されることができず、さらに全体的なファイルサイズが大きい可能性があるためユーザにとって明らかに不都合である。

その他のアプリケーションは、線オブジェクト及び中身が塗り潰されたオブジェクトを発見するためにベクトル化方法を使用する。線オブジェクト及び中身が塗り潰されたオブジェクトは、特定のテンプレート形状のインスタンスではなく、出力において自由な線の描画として表される可能性がある。これは、テンプレート形状に対して定義された特定の編集オプションが利用できず、対応する編集可能な電子的形態の有用性を制限するのでユーザにとって不都合である。また、そのようなアプリケーションは、ドキュメントのコンテンツに関して、あまり精度の高くない意味情報を提供する。したがって、このようなデータを当てにするデータベースアプリケーションは、あまり有用でない可能性がある。

グラフィカルな要素の認識のために使用されうるいくつかの既存の方法が存在する。いくつかの方法は、個々の要素又は要素の組合せの全種類を認識している。ここで、同じ種類であると認識された異なるオブジェクトは、特定されない歪曲の範囲によって関連付けられる。そのような方法は、いくつかの異なる形状及び不明な歪曲の形で提供される可能性があるオブジェクトを認識すること（例えば、人物顔認識の用途）に対して有用である。しかし、これらの方法は、編集可能なドキュメントにおいて、出力用の予め定められた形状表現の特定のパラメータ化を認識する手段及び指定する手段を提供しない。他の方法は、特定の形状を認識し、線形変換の制限された組を指定するが、典型的なテンプレート形状ライブラリ内の形状に対して実行される変換のカスタマイズされた組合せには対応しない。

したがって、スキャンされた画像入力からドキュメントの電子的形態を作成する改良された方法に対するニーズが存在する。

本発明の一形態によれば、編集可能なドキュメントを作成する方法が提供され、前記方法は、ａ．少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析するステップと、ｂ．前記グラフィカルオブジェクトを、１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするステップと、ｃ．前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に、前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択するステップと、ｄ．前記線オブジェクトを前記選択された接続点と関連付けるステップと、ｅ．前記テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成するステップとを含み、前記線オブジェクトは、前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、テンプレート形状に動的に接続されたままであることを特徴とする。

本発明の他の形態によれば、編集可能なドキュメントを作成する装置が提供され、前記装置は、少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析する解析手段と、前記グラフィカルオブジェクトを１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするマッチング手段と、前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択する選択手段と、前記線オブジェクトを前記選択された接続点と関連付ける関連付け手段と、テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成する作成手段とを備え、前記線オブジェクトは前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、テンプレート形状に動的に接続されたままであることを特徴とする。

本発明のさらに他の形態によれば、編集可能なドキュメントを作成するための手順をコンピュータに実行させるプログラムを記憶したコンピュータ読み取り可能な記憶媒体が提供され、前記プログラムは、少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析するステップと、前記グラフィカルオブジェクトを１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするステップと、前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択するステップと、前記線オブジェクトを前記選択された接続点と関連付けるステップと、テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成するステップとを含み、前記線オブジェクトは、前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、テンプレート形状に動的に接続されたままであることを特徴とする。

また、本発明のその他の形態も開示される。

本発明は、スキャンされた画像入力からドキュメントの電子的形態を作成する改良された方法を提供できる。

以下では、従来技術のいくつかの形態と本発明の１つ以上の実施形態とが図面及び付録を参照して説明される。

添付の図面のうちの任意の１つ以上において同じ参照番号を有するステップ及び／又は特徴に対する参照がなされる場合、それらのステップ及び／又は特徴は、相容れない意図が現れない限りこの説明の目的のために同じ（１つ以上の）機能又は（１つ以上の）動作を有する。

「背景技術」の欄に含まれる検討、及び従来技術の構成に関連する上記の内容は、それらのそれぞれの公表及び／又は使用を通じて公知の知識を形成する文書又はデバイスの検討に関連することに留意されたい。このようなことは、そのような文書又はデバイスが何らかの形で当技術分野の技術常識の一部を形成するという（１人又は複数の）本発明者又は特許出願人による陳述と解釈されるべきでない。

以下では、ドキュメントを作成する方法について説明する。説明する方法は、図２５に示すコンピュータシステムなどのコンピュータシステム２５００を使用して実行され、当該コンピュータシステムにおいて、図１乃至図２４のプロセスがコンピュータシステム２５００内で実行可能な１つ以上のアプリケーションプログラムなどのソフトウェアとして実行される。具体的には、説明する方法のステップは、コンピュータシステム２５００内で実行されるソフトウェアの命令によって達成される。命令は、それぞれが１つ以上の特定のタスクを実行することを目的とする１つ以上のコードモジュールとして形成される。ソフトウェアは、第１の部分及び対応するコードモジュールが説明する方法を実行し、第２の部分及び対応するコードモジュールが第１の部分とユーザとの間のユーザインターフェースを管理する２つの別個の部分に分割される。ソフトウェアは、例えば後述する記憶装置を含むコンピュータ読み取り可能な記憶媒体に記憶される。ソフトウェアは、コンピュータ読み取り可能な記憶媒体からコンピュータシステム２５００にロードされ、続いてコンピュータシステム２５００によって実行される。ソフトウェア又はコンピュータプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、コンピュータプログラム製品となる。コンピュータシステム２５００において、当該コンピュータプログラム可読媒体の使用が、説明する方法を実行するための有利な装置をもたらすであろう。

図２５に示すように、コンピュータシステム２５００は、コンピュータモジュール２５０１、キーボード２５０２及びマウスポインタデバイス２５０３などの入力デバイスと、プリンタ２５１５、ディスプレイデバイス２５１４、及びスピーカ２５１７を含む出力デバイスとによって形成される。外付け変調復調装置（モデム）トランシーバデバイス２５１６が、接続２５２１を介した通信ネットワーク２５２０への通信、及び通信ネットワーク２５２０からの通信のためにコンピュータモジュール２５０１によって使用される。ネットワーク２５２０は、インターネット又はプライベート広域ネットワーク（ＷＡＮ）などのＷＡＮであってもよい。接続２５２１が電話回線である場合、モデム２５１６は従来の「ダイヤルアップ」モデムでもよい。代替例として、接続２５２１が大容量（例えば、ケーブル）接続である場合、モデム２５１６はブロードバンドモデムであってもよい。ネットワーク２５２０への無線接続のために無線モデムを使用してもよい。

通常、コンピュータモジュール２５０１は、少なくとも１つのプロセッサユニット２５０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されたメモリユニット２５０６とを備える。モジュール２５０１は、ビデオディスプレイ２５１４及びスピーカ２５１７に接続されるオーディオビデオインターフェース２５０７と、キーボード２５０２、マウス２５０３及び任意選択でジョイスティック（図示せず）のための入力／出力（Ｉ／Ｏ）インターフェース２５１３と、外付けモデム２５１６及びプリンタ２５１５のためのインターフェース２５０８とを含むいくつかのＩ／Ｏインターフェースも含む。一部の実装において、モデム２５１６は、コンピュータモジュール２５０１内、例えばインターフェース２５０８内に組み込まれてもよい。コンピュータモジュール２５０１は、接続２５２３を介して、コンピュータシステム２５００をローカルエリアネットワーク（ＬＡＮ）として知られるローカルコンピュータネットワーク２５２２に接続することを可能にするローカルネットワークインターフェース２５１１も有する。図２５に示すように、ローカルネットワーク２５２２は、通常、いわゆる「ファイアウォール」デバイス又は同様の機能を含む接続２５２４を介して広域ネットワーク２５２０に接続してもよい。インターフェース２５１１は、イーサネット（登録商標）回路カード、無線Ｂｌｕｅｔｏｏｔｈ（商標）、又はＩＥＥＥ８０２．１１無線装置によって形成されてもよい。

インターフェース２５０８、２５１３は、シリアル及びパラレル両方の接続性を与え、通常、前者はユニバーサルシリアルバス（ＵＳＢ）規格に従って実装され、対応するＵＳＢコネクタ（図示せず）を有する。通常、ハードディスクドライブ（ＨＤＤ）２５１０を備える記憶装置２５０９が提供される。また、フロッピー（登録商標）ディスクドライブ及び磁気テープドライブ（図示せず）などのその他のドライブが使用されてもよい。また、光ディスクドライブ２５１２が提供されて、不揮発性のデータのソースとして働く。例えば光ディスク（例えば、ＣＤ−ＲＯＭ、ＤＶＤ）、ＵＳＢ−ＲＡＭ、及びフロッピー（登録商標）ディスクなどのポータブルメモリデバイスが、システム２５００に対する適切なデータのソースとしてさらに使用されてもよい。

通常、コンピュータモジュール２５０１のコンポーネント２５０５〜２５１３までは、相互接続されたバス２５０４を介して、及び当業者に知られているコンピュータシステム２５００の動作の通常の形態をもたらすやり方で通信が行われる。そのコンピュータ上で説明された構成が実施されるコンピュータの例は、ＩＢＭ−ＰＣ及び互換機、Ｓｕｎ Ｓｐａｒｃｓｔａｔｉｏｎ、Ａｐｐｌｅ Ｍａｃ（商標）、又はそれらから発展した同様のコンピュータシステムを含む。

概して、上述したアプリケーションプログラムはハードディスクドライブ２５１０上に存在し、プロセッサ２５０５による実行において読み出され、制御される。そのようなプログラム、及びネットワーク２５２０、２５２２から取得された任意のデータの中間記憶が、場合によってはハードディスクドライブ２５１０と連動して半導体メモリ２５０６を使用することによって実行されてもよい。いくつかの例において、１つ以上のＣＤ−ＲＯＭ上に符号化され、対応するドライブ２５１２を介して読み出されるアプリケーションプログラムがユーザに供給されるか、又は代替として、アプリケーションプログラムがネットワーク２５２０又はネットワーク２５２２からユーザによって読み出されてもよい。さらに、ソフトウェアは、その他のコンピュータ読み取り可能な記憶媒体からコンピュータシステム２５００にロードされてもよい。コンピュータ読み取り可能な記憶媒体は、命令及び／又はデータを、実行及び／又は処理のためにコンピュータシステム２５００に提供する任意の記憶媒体を示す。そのような媒体の例には、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ若しくは集積回路、光磁気ディスク、又はＰＣＭＣＩＡカードなどのコンピュータ可読カードが、そのようなデバイスがコンピュータモジュール２５０１の内部又は外部にあるか否かに関わらず含まれる。同様に命令及び／又はデータの供給に関与するコンピュータ可読伝送媒体の例には、無線又は赤外線伝送チャネル、並びに他のコンピュータ又はネットワークデバイスへのネットワーク接続、及び電子メールの伝送とウェブサイトなどに記録された情報とを含むインターネット又はイントラネットが含まれる。

アプリケーションプログラムの第２の部分及び対応するコードモジュールは、ディスプレイ２５１４上に描画されるか、又はそうでなければ表示されるべき１つ以上のグラフィカルユーザインターフェース（ＧＵＩ）を実行するために実行されてもよい。キーボード２５０２及びマウス２５０３の操作を通じて、コンピュータシステム２５００及びアプリケーションのユーザは、インターフェースを操作して、（１つ以上の）ＧＵＩに関連するアプリケーションに制御命令及び／又は入力を与えることができる。

代替的に、説明する方法は、当該方法の機能又は従属機能を実行する１つ以上の集積回路などの専用ハードウェアにおいて実行されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ若しくは複数のマイクロプロセッサ及び関連するメモリを含んでよい。

以下で使用される用語「テンプレート形状」は、指定された編集又はビュー環境内の閉じた外側境界を有する修正可能な非テキストの形状オブジェクトの形態を定義する予め定められたモデルを示す。したがって、本明細書において説明されるテンプレート形状は、「修正可能な閉じた形態である非テキストのテンプレート形状」である。多くのテンプレート形状は単一の閉じた外側境界から構成されるが、図４に示された「缶」テンプレート形状４２０などの一部のテンプレート形状はその他の内側の線を含む。テンプレート形状は、それらのパラメータの解釈がモデル内で定義された複数のパラメータによって指定される。複数のパラメータには、アフィンパラメータ、制御パラメータ、及び線幅パラメータが含まれる。テンプレート形状を定義するパラメータは以下でさらに詳細に説明される。

図２７（ａ）、（ｂ）は、Ｍｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓの抜粋を示す図である。さらに、付録Ａは、図２７（ａ）、（ｂ）のＭｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓのそれぞれの名称を図２７（ａ）、（ｂ）におけるそれらの図形の参照とともに一覧にする表である。

テンプレート形状のアフィンパラメータは、閉じた形態の非テキストのテンプレート形状に対する修正を定義する。そのような修正は線形行列変換によって記述されてもよい。また、修正は、拡大縮小、回転、及びオフセットを含み、特定の形状の種類に対しては傾斜を含んでもよい。それぞれｘ軸及びｙ軸に沿ったｓ_ｘ及びｓ_ｙの拡大縮小と、θの回転と、それぞれｘ軸及びｙ軸に沿ったΔｘ及びΔｙのオフセットとに関して、線形行列変換は以下の式（１）によって表される。

変換が傾斜ｃも含む場合、行列変換は以下の式（２）によって表される。

アフィンパラメータの観点でのみ異なるテンプレートの種類のオブジェクトは、適切な行列変換を使用して一致するように修正される。図５（ａ）は、テンプレート形状５００の拡大縮小ｓ_ｘ及びｓ_ｙ、回転θ、並びにオフセットΔｘ及びΔｙのアフィンパラメータが修正されるにつれて第１にテンプレート形状５０１に、第２にテンプレート形状５０２に、第３にテンプレート形状５０３に変化する五角形テンプレート形状５００を示す。

図５（ｂ）は、三角形５０４の傾斜パラメータが修正されるにつれて取得されるいくつかの異なる三角形５０５〜５０７を示す。特定の形状に関する傾斜パラメータは、いくつかのユーザインターフェース内に制御パラメータとして現れる可能性があることに留意されたい。しかし、本明細書において説明されるように、傾斜パラメータはアフィンパラメータとみなされる。

制御パラメータは、概してテンプレート形状の線形行列変換を用いて定義されることができない、テンプレート形状に対するさらなる幾何学的修正を定義する。それぞれのテンプレート形状はＮ個の制御パラメータの定義された組を有し、ここでＮはモデルによって指定され、０である可能性もある。具体的には、通常、テンプレート形状は最大で４個の（即ち、４個以下の）制御パラメータを含む。しかし、一部のテンプレート形状は４個を超える制御パラメータを含んでもよい。テンプレート形状は直線的な辺（即ち、多角形）又は曲線によって全体的に定義されるか、又は１組の頂点の間の直線的な辺及び曲線部分の混合を含む。通常、各制御パラメータは、複数の頂点、複数の曲線部分、又は複数の頂点及び曲線部分の両方を修正する。

代替的に、閉じた形態のテンプレート形状は、特定のテンプレート形状における個々の頂点の座標を示すパラメータによって定義される。さらに、閉じた形態のテンプレート形状は、当該テンプレート形状の各曲線部分を独立に修正するパラメータによって定義される。よく使用される曲線のパラメータ化方法には、３次スプライン及びベジェ曲線がある。２つ以上の頂点及び／又は曲線部分を修正する制御パラメータを使用してテンプレート形状を定義することの利点は、実質的により少ないパラメータが要求され、パラメータがその特定の形状により適した修正を記述することである。

テンプレート形状の制御パラメータを修正することの効果は、テンプレート形状に関するテンプレートモデルによって定義される。制御パラメータは、閉じた形態の非テキストのテンプレート形状を非アフィン形式で修正するために使用される。１つの制御パラメータを有するテンプレート形状の例６０１〜６２４の組６００が図６に示される。各テンプレート形状（例えば、６０６）に隣接しているのは、その正方形のｘ座標が制御パラメータの値を表す黒い正方形（例えば、６２５）である。図６は、それらの角丸四角形に関して制御パラメータが角の曲率半径を修正する１組の角丸四角形（即ち、６０１〜６０４）を含む。図６は、制御パメータ（例えば、６２５）が、上部の水平な部分を有するテンプレート形状の左側の線の交差する点を定義する台形（即ち、６０５〜６０８）、六角形（即ち、６０９〜６１２）、及び八角形（即ち、６１３〜６１６）も含む。図６は、制御パラメータ（例えば、６２６）が凸部及び凹部の頂点の相対的な半径を定義する１６角シール（即ち、６１７〜６２０）も含む。最後に、図６は、制御パラメータ（例えば、６２７）が当該部分的に欠けた月形の段階を定義する部分的に欠けた月形（即ち、６２１〜６２４）を含む。

図７は、２つの制御パラメータを有するテンプレート形状の例７０１〜７１６、即ち矢印の組７００を示す図である。黒い正方形は制御パラメータの値を表し、この場合、２つのパラメータがそれぞれｘ座標及びｙ座標によって表される。

同様に、図８は、２つの制御パラメータを有するテンプレート形状の例８０１〜８１６、即ち角丸コールアウトの組８００を示す図である。ここでも、黒い正方形は制御パラメータの値を表し、この場合、２つのパラメータがそれぞれｘ座標及びｙ座標によって表される。

通常、テンプレート形状は、当該テンプレート形状の外側境界を定義する部分の数よりも少ない制御パラメータを有する。例えば、図６の形状の例の組６００は、単一の制御パラメータを用いて定義される。しかし、台形（６０５〜６０８）は４つの部分からなり、六角形（６０９〜６１２）は６つの部分からなり、八角形（６１３〜６１６）は８つの部分からなり、１６角シール（６１７〜６２０）は３２の部分からなり、月形（６２１〜６２４）は２つの部分からなる。同様に、図７及び図８に示されたテンプレート形状は２個の制御パラメータを用いて定義されるが、各テンプレート形状は３つ以上の部分からなる。Ｍｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓの組のほとんどのテンプレート形状は、４個以下の制御パラメータを有する。

いくつかの場合、拡大縮小パラメータは特定のテンプレート形状に対してアフィンパラメータとして機能しない可能性があることに留意されたい。例えば、図９に示すように、角丸長方形テンプレート形状９１０の拡大縮小がアフィンスケーリングを用いる場合に期待されるような楕円形態を取るのではなく、角丸長方形形状９２０を形成するように修正されながら、当該角丸長方形テンプレート形状９１０の角が円弧のようなそれらの角の形態を維持する。このような振る舞いは、テンプレート形状の縦横比（即ち、垂直方向の拡大縮小パラメータと水平方向の拡大縮小パラメータとの間の比）に対応する追加の制御パラメ―タをテンプレート形状に加えることによってモデル化される。

線幅パラメータは、予め定められたテンプレート形状を定義する線の幅を単に定義する。通常、テンプレート形状全体に対する一定の線の幅を定義する唯一の線幅パラメータが存在する。図１０は、ページの左から右に向かって増加する線幅パラメータの組を有する、塗り潰されていない六角形テンプレート形状１００１を示す図である。

本明細書において説明される方法は、幾何学モーメント、中心幾何学モーメント、及びツェルニケモーメントなどのいくつかのモーメントを使用して実装される。

（ｐ，ｑ）次の幾何学モーメントは、以下のように式（３）に従って予め定められた形状オブジェクト（例えば、グラフィカルオブジェクト）の内部によって覆われる領域Ａに渡る積分によって定義される。

ここでｐ及びｑは整数≧０である。幾何学モーメントは、速度に関する境界線の積分によって決定される。モーメントＭ_００は形状オブジェクトの面積を表し、点（ｘ_０，ｙ_０）＝（Ｍ_１０／Ｍ_００，Ｍ_０１／Ｍ_００）はその形状オブジェクトの重心を表す。

中心幾何学モーメントは、例えば、以下の式（４）による、形状オブジェクトの重心が原点に位置付けられるように変換された形状オブジェクトの幾何学モーメントである。

ツェルニケモーメントは画像処理の形状認識処理においてよく使用される。ツェルニケモーメントは、少ない数の項を使用して形状を識別する点で優れた特性を有する。ツェルニケモーメントは、単位円上で直交する１組の基底関数を用いて定義される。これらの基底関数は以下のように式（５）によって与えられる。

ツェルニケモーメントは以下のように式（６）によって決定される。

以下で説明される方法は、「正規化形状オブジェクト」と呼ばれる形状オブジェクトの代替表現を使用する。正規化形状オブジェクトは、形状オブジェクトの重心が原点に一致するようにシフトされた元の形状オブジェクトに基づいており、回転及び伸張の効果を小さくするように修正される。正規化はアフィン変換によって表されることが好ましい。任意の２次元（２Ｄ）形状オブジェクトをその形状オブジェクトの標準的な形態にマッピングするための一連の線形変換である通常のアフィン正規化が、正規化を実行するために使用されることが好ましい。具体的には、元の形状オブジェクトが、当該形状オブジェクトの重心が原点にあるようにシフトされ、２次モーメントが１（ｍ_２０＝ｍ_０２＝１）になるようにｘ軸及びｙ軸に沿って伸張され、４５度回転され、続いて２次モーメントがやはり１（ｍ_２０＝ｍ_０２＝１）になるように再び伸張される。代替的な正規化方法が、例えば元の形状オブジェクトの主軸及び境界ボックスに基づいて使用される。

上述のアフィン正規化は、以下のように行列式（７）によって表される。

ここで、（ｘ，ｙ）^Ｔ及び（ｘ’，ｙ’）^Ｔはそれぞれ変換の前後の形状オブジェクトにおける特定の点を定義し、（Δｘ，Δｙ）^Ｔは元の形状オブジェクトの重心の位置であり、正規化行列Ｎは以下のように式（８）を使用して２次中心幾何学モーメントによって定義される。

以下で説明される方法は、グラフィカルな領域を有するドキュメントのビットマップ画像を解析して修正可能なテンプレート形状及びコネクタを有するドキュメントを作成するために使用される。説明する方法の多くは、例えばタブレットＰＣ及びホワイトボード用途における手書きのデジタルインク入力の解析にも適用可能である可能性がある。通常、デジタルインク入力はベクトルの形態で記憶されるので、説明されるベクトル化方法は必要とされない可能性がある。

図１１は、一実施形態に係る修正可能な形状（即ち、閉じた形態の非テキストのテンプレート形状）を含むドキュメントを作成する方法１１００を示すフローチャートである。方法１１００は、グラフィカルな領域を有する入力画像を、修正可能なテンプレート形状及びコネクタ（即ち、ドキュメント内のテンプレート形状を接続する動的な線オブジェクト）を有するドキュメントに変換することによってドキュメントを作成する。方法１１００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５による実行において制御されるソフトウェアとして実装される。

図１１に示すように、方法１１００は、ステップ１１１０において始まり、ここではビットマップ画像が低レベルの画像分割にかけられる。このように、ビットマップ画像はプロセッサ２５０５によって色に応じて１つ以上の領域に分割される。次に、ステップ１１２０において、プロセッサ２５０５は、ビットマップ画像の分割された領域に対して高レベルのドキュメントレイアウト解析を実行して、様々なドキュメントにおけるコンテンツ種類の領域を識別する。この例示的な実施形態において、領域は矩形であり、コンテンツの種類は、以下の分類、即ちテキスト、写真（ハーフトーン）、及びグラフィカルオブジェクトを含んでもよい。これらのコンテンツの種類のそれぞれはピクセルデータで構成される。代替の実施形態において、表、線画などの他のドキュメントにおけるコンテンツの種類が含まれてもよい。分類された領域は、ゾーン、ブロック、又は対象領域と呼ばれる場合もある。また、当該領域の境界ボックスは重なり合う可能性がある。

次のステップ１１３０において、検出されたグラフィックス領域が、図１２を参照して以下でさらに詳細に説明される方法１２００に従って、当該グラフィックス領域内のグラフィカルオブジェクトを検出するためにさらに解析される。したがって、ステップ１１３０において、プロセッサ２５０５は、グラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像のグラフィックス領域を解析するステップを実行する。

方法１１００は、次のステップ１１４０において継続し、ここではプロセッサ２５０５が、個々の検出されたグラフィカルオブジェクトが何であるかを判定するために、上述のように、検出されたグラフィカルオブジェクトを複数の予め定められた修正可能な閉じた形態である非テキストにおけるテンプレート形状のうちの１つとマッチングするステップを実行する。各テンプレート形状は、１つ以上の予め定められた有限の不連続な接続点の組を有する。上述のように、通常、テンプレート形状のそれぞれは、閉じた形態の非テキストのテンプレート形状を非アフィン形式で修正するための最大４個の制御パラメータを含む。通常、予め定められた修正可能な閉じた形態である非テキストのテンプレート形状の制御パラメータ数は、修正可能な閉じた形態である非テキストのテンプレート形状を構成する部分の数よりも少ない。ステップ１１４０において、検出されたグラフィカルオブジェクトを予め定められたテンプレート形状とマッチングする方法１３００が実行される。方法１３００についての詳細は、図１３を参照して後述する。方法１３００の出力は、１つ以上の候補テンプレート形状、及び関連する形状パラメータである。

方法１１００は、次のステップ１１５０において継続し、ここではプロセッサ２５０５が線オブジェクトがコネクタを形成するかどうかを判定するためにグラフィックス領域内の線オブジェクトを解析するステップを実行する。また、プロセッサ２５０５は、マッチングされたグラフィカルオブジェクトに対する線オブジェクトの接続点の位置を判定する。ステップ１１５０において実行される線オブジェクトを解析する方法１４００についての詳細は、図１４を参照して後述する。

次のステップ１１６０において、プロセッサ２５０５は、マッチングされた修正可能な閉じた形態である非テキストのテンプレート形状と、当該テンプレート形状に接続された任意の線オブジェクト（又はコネクタ）とを含むドキュメントの編集可能な形態（バージョン）を作成するステップを実行する。ドキュメントの編集可能な形態は、任意の認識されたテキスト、ドキュメントの要素、及び修復された背景を含む。後述するように、ステップ１４８０（図１４参照）におけるテンプレート形状の選択された接続点に関連する線オブジェクトは、ドキュメント内でテンプレート形状が修正されると、当該選択された接続点と関連付けられたままである。したがって、線オブジェクトは、テンプレート形状に動的に接続されたままとなる。ステップ１１６０において、マッチングされた閉じた形態の非テキストのテンプレート形状、コネクタ、及びその他のドキュメントの要素を含む編集可能なドキュメントを作成する方法２０００が実行される。方法２０００については、図２０を参照して後述する。

ステップ１１３０において、グラフィックス領域（即ち、ステップ１１２０において特定されたグラフィックス領域）内のグラフィカルオブジェクトを識別（又は検出）するためにグラフィックス領域を解析する方法１２００が実行される。ここで方法１２００について図１２を参照して説明する。方法１２００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。

方法１２００は、ステップ１１２０において特定されたグラフィックス領域から線オブジェクト及び中身が塗り潰されたグラフィカルオブジェクトを作成するためのループ構造を使用する。

方法１２００は、ステップ１２１０において始まり、ここではプロセッサ２５０５が処理のためにグラフィックス領域を有する分割色マスク／レイヤを選択する。続いて次のステップ１２２０において、プロセッサ２５０５は、色レイヤから開いた線オブジェクト及び閉じた線オブジェクトの両方をベクトルとして抽出する。開いた線オブジェクトは、２つの未接続の終端を有する１つ以上の接続された線セグメントからなる。閉じた線オブジェクトは、閉じた多角形を形成するいくつかの接続された線セグメントからなる。線セグメントは直線であることが望ましい。代替の実施形態において、線セグメントは曲線であってもよい。ステップ１２３０において、予め定められた分割色マスク／レイヤから開いた線オブジェクト及び閉じた線オブジェクトをベクトルとして抽出する方法１６００が実行される。方法１６００については、図１６を参照して後述する。

ステップ１２３０において、色レイヤは、塗り潰された形状などの非線オブジェクトを抽出するためにさらに処理される。抽出された塗り潰された形状は、多角形オブジェクトとして表されることが望ましい。ステップ１２３０において実行される非線オブジェクトを抽出する方法２１００は、図２１を参照して以下でより詳細に説明される。次のステップ１２４０において、何らかのさらなる色レイヤが存在する場合、方法１２００は、次の色レイヤが選択され、処理されるステップ１２１０に戻る。何らかのさらなる色レイヤが存在しない場合、方法１２００は終了する。

ステップ１１４０において、検出されたグラフィカルオブジェクトを予め定められたテンプレート形状とマッチングする方法１３００が実行される。ここで方法１３００について、図１３を参照して説明する。方法１３００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。方法１３００は、それぞれの検出されたグラフィカルオブジェクトに対して最も一致するテンプレート形状を選択するためのループ構造を使用する。

方法１３００は、ステップ１３１０において始まり、ここではプロセッサ２５０５が処理のために次の検出されたグラフィカルオブジェクトを選択する。続いて、次のステップ１３２０において、グラフィカルオブジェクトに対する１組の候補テンプレート形状が、機械学習分類器を使用して決定される。ステップ１３２０において、グラフィカルオブジェクトに対する１組の候補テンプレート形状を決定する方法１７００が実行される。方法１７００については、図１７を参照して後述する。

全ての選択された候補テンプレート形状を順番に処理して現在のグラフィカルオブジェクトに対して最も一致するテンプレート形状を発見するために方法１３００において第２のループ構造が使用される。ステップ１３３０において、次の候補テンプレート形状が選択され、続いてステップ１３４０において、現在のグラフィカルオブジェクトに最もよく一致するように候補テンプレート形状を修正する候補テンプレート形状の形状パラメータの組と、グラフィカルオブジェクト及び修正されたテンプレート形状が互いにどれだけよく一致するかを定量化する一致スコアとが決定される。ステップ１３４０において、グラフィカルオブジェクトに一致するように候補テンプレート形状（即ち、修正可能な閉じた形態である非テキストのテンプレート形状）を修正するための１組のパラメータを決定する方法１８００が実行される。方法１８００については、図１８を参照して後述する。

解析されるべきさらなる候補テンプレート形状が存在する場合、ステップ１３５０から、方法１３００はステップ１３３０に戻る。さらなる候補テンプレート形状が存在しない場合、方法１３００は、ステップ１３６０において継続し、ここでは現在のグラフィカルオブジェクトに対して最も高い一致スコアを有する候補テンプレート形状が選択される。続いてステップ１３７０において、そのスコアが形状認識に関する予め定められた閾値よりも大きい場合、方法１３００はステップ１３８０に進む。ここで、予め定められた閾値は、９５％の適合スコア（即ち、ｆ＞０．９５）であることが望ましい。当該スコアが予め定められた閾値よりも大きい場合、ステップ１３６０において選択された候補テンプレート形状は関連する形状パラメータとともに、ステップ１３８０における出力のためにメモリ２５０６に記憶され、続いて方法１３００はステップ１３９０に続く。当該スコアが予め定められた閾値以下の場合、処理はステップ１３７０からステップ１３９０に直接続く。

ステップ１３９０において、処理されるべき何らかのさらなるグラフィカルオブジェクトが存在する場合、方法１３００はステップ１３１０に戻る。処理されるべき何らかのさらなるグラフィカルオブジェクトが存在しない場合、方法１３００は完了する。

図１４を参照して、ステップ１１５０において実行される、線オブジェクトを解析する方法１４００について説明する。方法１４００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。方法１４００は、それぞれの開いた線セグメントの各終端に対して、選択されたテンプレート形状上の最も満足できる接続点を選択するためのループ構造を使用する。

方法１４００は、ステップ１４１０において始まり、そこではプロセッサ２５０５が処理のために次の開いた線オブジェクトを選択する。テンプレート形状として認識された全てのオブジェクトを順に処理して現在の開いた線オブジェクトに対する満足できる接続点を発見するために第２のループ構造が使用される。ステップ１４２０において次のテンプレート形状が選択され、続いてステップ１４３０において、選択されたテンプレート形状に対する１組の予め定められた接続点が決定される。

方法１４００は、ステップ１４４０において継続し、ここでは線オブジェクトの線の終端点が現在のテンプレート形状の各接続点と比較される。例示的な実施形態において、線の終端点と接続点との間の距離が判定され、予め定められた閾値距離に対して試験されてもよい。閾値距離は、線幅と、テンプレート形状の大きさと、線オブジェクト及びテンプレート形状に関するその他の幾何学情報に応じて決まってよい。例示的な実施形態において、予め定められた閾値距離は、（ｉ）３００ｄｐｉにおける３０ｐｔ、並びに（ｉｉ）テンプレート形状の幅及び高さのうちの小さい方の１０％によって与えられる２つの値のうちの小さい方によって与えられてもよい。線オブジェクトの終端とテンプレート形状の接続点との間の距離が予め定められた閾値距離よりも短い場合、線オブジェクトはメモリ２５０６内で接続点と関連付けられる。一例として、図１５は、テンプレート形状１５１０と、一方の終端に矢尻形状を有する１つの開いた線オブジェクト１５７０、及び終端の効果を有していない１つの開いた線オブジェクト１５６０の２つの開いた線オブジェクトとを示す。テンプレート形状１５１０に関する４つの接続点が黒い正方形１５２０、１５３０、１５４０、及び１５５０によって表されている。各接続点の周りにあるのは、発見されるべき満足できる接続点に関する線オブジェクトの終端への最大距離を表す破線の円である。図１５の例において、線オブジェクト１５６０の右側の終端は満足できる接続点１５５０を有する一方、線オブジェクト１５６０、１５７０のその他の３つの線の終端はテンプレート形状１５１０上に満足できる接続点を有していない。

解析されるべきさらなるテンプレート形状が存在する場合、ステップ１４５０から、方法１４００はステップ１４２０に戻る。さらなるテンプレート形状が存在しない場合、方法１４００はステップ１４６０に続く。ステップ１４６０において、プロセッサ２５０５は、上述のように線オブジェクトの少なくとも１つの終端が予め定められた接続点のうちの１つの予め定められた閾値距離内にある場合に線オブジェクトに対して当該予め定められた接続点のうちの当該１つを選択するステップを実行する。具体的には、ステップ１４６０において、最も満足できる接続点が線オブジェクトに対して選択される。例示的な実施形態において、最も満足できる接続点は、線オブジェクトの終端と接続点との間の最も短い距離を有する接続点であってもよい。

ステップ１４７０は、最も満足できる接続点が線オブジェクトに対して発見されたかどうかをチェックし、発見されている場合はステップ１４８０において、プロセッサ２５０５が、線オブジェクトを選択された接続点と関連付けるステップを実行する。線オブジェクトは、当該線オブジェクトを選択された接続点に対する参照とともにメモリ２５０６内に記憶することによって、選択された接続点と関連付けられる。一方、最も満足できる接続点が発見されなかった場合、方法１４００は直接、ステップ１４９０に続く。

ステップ１４８０において、プロセッサ２５０５は、線オブジェクトを分類するステップを実行してもよい。具体的には、線オブジェクトは、当該線オブジェクトが単一の直線セグメントからなる場合は直線コネクタとして分類される。線オブジェクトが互いに直角である１組の直線セグメントからなる場合、線オブジェクトは屈曲コネクタとして分類されてもよい。その他の場合は、線オブジェクトに関連するあらゆる接続点は破棄され、線オブジェクトは動的なコネクタとして分類されない。

例示的な実施形態において、屈曲コネクタの分類は、後述するようにＡｕｔｏＳｈａｐｅ（商標）ライブラリの屈曲コネクタに基づいてもよい。線オブジェクトは２つから５つの間の直線セグメントから構成されなければならず、それらの直線セグメントのそれぞれは画像のｘ軸又はｙ軸に対してほぼ並行である。これらの特性を有する屈曲コネクタへの元の線オブジェクトの適合を表す修正された線オブジェクトが形成される。元の線オブジェクトが（ｎ＋１）個の点によって定義されたｎ個の線の部分からなる場合、修正された線オブジェクトも（ｎ＋１）個の点によって定義されたｎ個の線の部分から構成される。元の線オブジェクト内の点は（ｘ_ｉ，ｙ_ｉ）と称され、修正された線オブジェクト内のそれらの点は（ｘ’_ｉ，ｙ’_ｉ）と称され、ここでｉは１から（ｎ＋１）までの整数値を取る。

線オブジェクトの第１の部分は、ｘ軸に沿った変位の大きさが当該部分上の垂直方向の変位の大きさよりも大きい場合に水平として分類される。そうでない場合、線オブジェクトの第１の部分は垂直として分類される。線オブジェクトの引き続く部分は、隣接する部分の対が同じ分類を持たないように水平及び垂直として順々に分類される。修正される線オブジェクトの第１の点は、線オブジェクト内の第１の点と一致するように設定される（即ち、（ｘ’_１，ｙ’_１）＝（ｘ_１，ｙ_１））。次に、線オブジェクトの部分のそれぞれが、修正される線オブジェクトに新しい点を追加するために順に処理される。ｉ番目の部分が水平として分類される場合、（ｉ＋１）番目の修正される点が、ｉ＝（ｎ−１）でない限り（ｘ’_ｉ＋１，ｙ’_ｉ＋１）＝（ｘ_ｉ＋１，ｙ’_ｉ）に設定され、ｉ＝（ｎ−１）である場合、（ｉ＋１）番目の修正される点が（ｘ’_ｉ＋１，ｙ’_ｉ＋１）＝（ｘ_ｎ＋１，ｙ’_ｉ）に設定される。同様に、ｉ番目の部分が垂直として分類される場合、（ｉ＋１）番目の修正される点が、ｉ＝（ｎ−１）でない限り（ｘ’_ｉ＋１，ｙ’_ｉ＋１）＝（ｘ’_ｉ，ｙ_ｉ＋１）に設定され、ｉ＝（ｎ−１）である場合、（ｉ＋１）番目の修正される点が（ｘ’_ｉ＋１，ｙ’_ｉ＋１）＝（ｘ’_ｉ，ｙ_ｎ＋１）に設定される。

修正された線オブジェクトは、以下のように、修正された線オブジェクト及び元の線オブジェクトからの頂点の対応する組を比較することによって試験される。１組の修正された線の点の誤差を定義するために、修正された線の点と元の線の点との間のユークリッド距離が判定され、記憶される。線の点の誤差の最大値が閾値よりも小さい場合、線オブジェクトは屈曲コネクタとして分類される。この場合、線オブジェクトは屈曲コネクタとして分類され、修正された線の点の組はコネクタのパラメータを定義するために使用される。例示的な実施形態において、閾値パラメータの値は、３００ｄｐｉにおける１０点によって与えられてもよい。

ここで、図２６を参照して、上述の屈曲コネクタの分類について説明する。図２６は、４つの点（２６３０、２６４０、２６５０、及び２６６０）によって定義される３つの部分（例えば、２６０１）からなる線オブジェクト２６１０を示す図である。対応する修正された線オブジェクト２６２０は、４つの点（２６３０、２６７０、２６８０、及び２６６０）によって定義される３つの部分からなる破線によって表される。線オブジェクト２６１０及び修正された線オブジェクト２６２０の第１の点２６３０及び最後の点２６６０は同一である。線オブジェクト２６１０の第１の部分（即ち、点２６３０から２６４０まで）は水平として分類され、したがって修正された線オブジェクト２６２０の第２の点２６７０は点２６４０と同じｘ座標及び点２６３０と同じｙ座標を用いて定義される。線オブジェクト２６１０の第２の部分（即ち、点２６４０から２６５０まで）は垂直であり、最後から２番目の部分であり、したがって修正された線オブジェクト２６２０の点２６８０は点２６７０と同じｘ座標及び点２６６０と同じｙ座標を用いて定義される。修正された線オブジェクト２６２０が屈曲コネクタとして分類されるかどうかを判定するために、点２６４０と２６７０の間の距離及び点２６５０と２６８０の間の距離が判定される。ステップ１４９０において、プロセッサ２５０５が、処理されるべきさらなる開いた線オブジェクトが存在すると判定する場合、方法１４００はステップ１４１０に戻る。プロセッサ２５０５が、さらなる開いた線オブジェクトが存在しないと判定する場合、方法１４００は終了する。

図１６を参照して、ステップ１２３０において実行される、予め定められた分割色マスク／レイヤから開いた線オブジェクト及び閉じた線オブジェクトをベクトルとして抽出する方法１６００について説明する。方法１６００は、予め定められた分割色マスク／レイヤ内の開いた線オブジェクトと、閉じた線オブジェクトと、中心線と、幅とを見つける。方法１６００は、ベクトル化方法と呼ばれる場合がある。例示的な実施形態において、分割色マスクは処理のためにピクセルの連続として表されてもよいが、代替的な表現が好適である可能性がある。

方法１６００は、ステップ１６１０において始まり、ここではプロセッサ２５０５が、次の線セグメントのシードを選択する。線セグメントのシードは、線オブジェクトがいかなるその他のオブジェクトとも交差せず、線オブジェクトの幅及び方向が実質的に一定である線オブジェクトの短い部分である。概して、線のシードのセグメントは、分割色マスク／レイヤ内のオブジェクトの垂直な及び／又は水平な部分を解析して局所領域内で実質的に一定の幅及び方向を持つオブジェクトを発見することによって見つけられる。

方法１６００は、ステップ１６２０に続き、ここでは線セグメントのシードが両方の終端点に沿って伸張されて線オブジェクトの長さを完全に決定する。ステップ１６２０は、分割色マスク／レイヤ内の線セグメントのシードの両側のオブジェクトの垂直な及び／又は水平な部分を解析すること、並びにそれらの位置及び大きさが線セグメントのシードの位置及び大きさに一致するかどうかを検証することによって実行される。線セグメントのシードが伸張されるとき、線オブジェクトの方向のわずかな逸脱が認められ、線オブジェクトの真の方向をより十分に反映するために線の方向に対する適切な調整がなされてもよい。線の伸張プロセスは、伸張される線の水平な及び／又は垂直な部分の方向又は大きさが、線セグメントのシードの方向又は大きさと実質的に異なるときに終了する。線オブジェクトの検出が完了された後で、線の経路（即ち、中心線）及び幅（即ち、中心線に垂直な方向の平均の幅）が判定及び記憶され、次のステップ１６３０において、再検出、及びその他の線オブジェクトの検出に対する起こりうる妨害を避けるために、検出された線オブジェクトがソース画像から消去される。

次のステップ１６４０において、処理されるべきさらなる線セグメントのシードが存在する場合、方法１６００はステップ１６１０に戻る。さらなる線セグメントのシードが存在しない場合、方法１６００はステップ１６５０に続く。ステップ１６１０から１６４０は、好ましい線ベクトル化方法を説明する。線オブジェクトを検出するためにその他の知られているベクトル化方法が使用されてもよい。

方法１６００は、次のステップ１６５０において継続し、ここでは方法１６００が検出された線オブジェクトの組を解析し、開いた多角形及び閉じた多角形を形成するために適切な線オブジェクトの終端点を接続する。例示的な実施形態において、線オブジェクトの終端点の間の距離が判定され、予め定められた閾値距離と比較されてもよい。線オブジェクトの終端点の間の距離が予め定められた閾値距離よりも短い場合、終端点は１つに接続される。例示的な実施形態において、予め定められた閾値距離は平均線幅の２倍に基づいて決定されてもよい。

次のステップ１６６０において、プロセッサ２５０５は、開いている線の終端に対応する線の終端のスタイルを発見するために、線オブジェクトのベクトルが削除された後でビットマップ画像内のオブジェクトを解析する。以下では図２２を参照して、ステップ１６６０において実行される、開いている線の終端に関する線の終端のスタイルを判定する方法２２００について説明する。

また、図１７を参照して、ステップ１３２０において実行される、グラフィカルオブジェクトに対する１組の候補テンプレート形状を決定する方法１７００について説明する。方法１７００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。

方法１７００は、ステップ１７１０において始まり、ここではプロセッサ２５０５が、現在のグラフィカルオブジェクトの正規化形状オブジェクトを決定する。ステップ１７２０において、プロセッサ２５０５は、正規化形状オブジェクトから１組の正規化された形状の特徴値を抽出する。これらの特徴値は、単純なモーメント、フーリエ記述子、又は単純な半径方向距離関数に基づいてもよい。

続いてステップ１７３０において、現在の正規化された形状の特徴ベクトルが、候補テンプレート形状を作成するために、前もってトレーニングされた機械学習分類器を用いて解析される。分類器は、サポートベクタマシン（ＳＶＭ）アルゴリズムを使用してトレーニングされることが望ましい。代替の実施形態において、トレーニング及び分類のためにその他の機械学習アルゴリズムが実行されてもよい。好適な機械学習アルゴリズムの例は、人工ニューラルネットワーク、ｋ近傍法、及び決定木を含んでもよい。

任意的に、方法１７００のステップ１７３０の後に、分類の速度を向上させるためのステップ１７４０を実行してもよい。ステップ１７４０は、分類器によって作成された混同行列を使用して候補テンプレート形状の組を合理化する。混同行列は、予め定められたテンプレート形状が別のテンプレート形状と混同され得る（又は、別のテンプレート形状として誤って分類され得る）可能性を特定する。候補テンプレート形状が別のテンプレート形状と高い混同の可能性を共有する場合、後者のテンプレート形状もさらなる処理のために候補テンプレート形状として選択される。

図１８を参照して、ステップ１３４０において実行される、グラフィカルオブジェクトに一致するように候補テンプレート形状を修正するための１組のパラメータを決定する方法１８００について説明する。方法１８００は、グラフィカルオブジェクトに一致するように候補テンプレート形状を最適に修正する１組の変換パラメータを決定する。変換パラメータは、２つの拡大縮小パラメータｓ_ｘ及びｓ_ｙ、２つのオフセットパラメータΔｘ及びΔｙ、回転角、並びにグラフィカルオブジェクトによっては線幅、及びいくつかの追加的な制御パラメータからなることが好ましい。線幅は、グラフィカルオブジェクトが線オブジェクトである場合は線オブジェクトの幅に設定され、又は線オブジェクトでない場合は０に設定されることが好ましい。方法１８００は、グラフィカルオブジェクトの特徴又は記述子の組と、モーメントなどのそのグラフィカルオブジェクトの正規化された形態とを用いて実行される。例示的な実施形態において、正規化されたグラフィカルオブジェクトの幾何学モーメント、中心幾何学モーメント、及びツェルニケモーメントが、テンプレート形状パラメータを推定するために使用されてもよい。

ステップ１８１０において、プロセッサ２５０５が、マッチング中のテンプレート形状が少なくとも１つの制御パラメータによって修正可能であると判定する場合、方法１８００はステップ１８４０に進む。プロセッサ２５０５が、修正可能であると判定しない場合、方法１８００はステップ１８２０に進む。ステップ１８２０において、プロセッサ２５０５が、テンプレート形状がせん断パラメータを有すると判定する場合、方法１８００はステップ１８３０に進む。プロセッサ２５０５が、テンプレート形状がせん断パラメータを有すると判定しない場合、方法１８００はステップ１８５０に進む。

ステップ１８３０において、プロセッサ２５０５は、グラフィカルオブジェクトに対する可能な拡大縮小パラメータ、回転パラメータ、及び傾斜パラメータの組を特定することによって、傾斜パラメータを伴うテンプレート形状に対するアフィン変換パラメータを決定する。ステップ１８３０において、正規化されたテンプレート形状に対する１組のあり得る回転パラメータが決定され、続いて、テンプレート形状のｘ軸及びｙ軸における拡大縮小（ｓ_ｘ及びｓ_ｙ）と、回転（θ）と、傾斜制御パラメータｃとをそれぞれ定義する４つの未知のパラメータについて行列式が解かれることが望ましい。正規化されたテンプレート形状が回転対称であり、この正規化されたテンプレート形状の対称変換の次数がｋである場合、可能な正規化空間回転角φ_ｎの組が、正規化された形状のフーリエ位相と正規化されたテンプレート形状のフーリエ位相とを比較することによって決定される。予め定められた形状のフーリエ位相は式（９）によって与えられる。

ここでＡは形状によって覆われる領域である。そのとき、角度φ_ｎは、式（１０）によって与えられる。

ここで、Ａ’は正規化された形状の領域であり、Ａ_Ｔ’は正規化されたテンプレート形状の領域であり、ｎは｛０，．．．，ｋ−１｝の範囲内の任意の整数である。正規化されたテンプレート形状が対称的でない場合、以下に説明される回転方法などの代替的な回転方法が使用されてもよい。

角度φ_ｎの各値に関して、以下の行列式（１１）を用いて、ｘ軸及びｙ軸における拡大縮小（ｓ_ｘ及びｓ_ｙ）と、回転（θ）と、傾斜制御パラメータｃとを定義する４つの未知のパラメータが解かれる。

ここで、Ｎはテンプレート形状のアフィン正規化行列である。角度φ_ｎのｋ個の可能な値に対応する１組のｋ個のあり得るアフィン変換パラメータの組が発見される。例示的な実施形態において、パラメータに関する有効範囲の外にある解は取り除かれる一方、残りの解はステップ１８６０に回されてもよい。

ステップ１８４０において、制御パラメータを有する形状に関するパラメータ推定が実行される。ステップ１８４０において、グラフィカルオブジェクトに一致するようにテンプレート形状を変換する最適な制御パラメータ値を決定する方法１９００が実行される。方法１９００については、図１９を参照して後述する。

次のステップ１８５０において、１組のあり得る回転パラメータ及び拡大縮小パラメータがテンプレート形状に対して決定される。ステップ１８５０において、グラフィカルオブジェクトに一致するようにテンプレート形状を修正することに使用するための回転パラメータ及び拡大縮小パラメータを決定する方法２４００が実行される。方法２４００については、図２４を参照して後述する。

方法１８００は、次のステップ１８６０において継続し、ここで前の処理ステップにおいて推定されたパラメータの各組に対してグラフィカルオブジェクトのｘオフセット及びｙオフセット（Δｘ，Δｙ）が決定される。具体的には、ステップ１８６０において、プロセッサ２５０５は、グラフィカルオブジェクトの重心を判定し、テンプレート形状の重心がグラフィカルオブジェクトと同じ位置にあるようにテンプレート形状をシフトする。

次に、方法１８００は、パラメータのそれぞれの可能な組に対するスコアが決定されるステップ１８７０に続く。スコアとは、パラメータの予め定められた組に関してグラフィカルオブジェクトがテンプレート形状にどれだけよく一致するかの尺度を示す。例示的な実施形態において、スコアｆは、以下のように式（１１）に従って決定される。

ここでＡ_ｉｎｔはテンプレート形状とグラフィカルオブジェクトとの共通部分の面積を示し、Ａ_ｔ及びＡ_ｓはそれぞれテンプレート形状の面積及びグラフィカルオブジェクトの面積を示す。代替の実施形態において、ハウスドルフ距離、及び境界の間の平均２乗距離などのその他の距離測定基準が使用されてもよい。

方法１８００は、次のステップ１８９０において終了し、ここではプロセッサ２５０５が、最も高いスコアを有するパラメータの組を決定する。

ステップ１８４０に戻ると、最も優れたパラメータの組が最も高い一致スコアを有するパラメータの組であると判定される。次に、この一致スコアは、候補テンプレート形状を他の候補テンプレート形状と比較するためにステップ１３６０において使用されるために戻される。

ステップ１８４０において、グラフィカルオブジェクトに一致するようにテンプレート形状を変換する最適な制御パラメータ値を決定する方法１９００が実行される。ここで方法１９００について、図１９を参照して説明する。方法１９００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。

方法１９００は、ステップ１９１０において始まり、ここではグラフィカルオブジェクトに対して１組の記述子が決定される。これは、グラフィカルオブジェクトの制御パラメータの関数として表される形状における特徴の任意の組であってもよい。例示的な実施形態においてグラフィカルオブジェクトのツェルニケモーメントが使用されてもよいが、フーリエ記述子、中心幾何学モーメント、又は境界の長さ若しくは角などの識別可能な特徴の位置などのより具体的な特徴などのその他の記述子が使用されてもよく、さらには様々な種類の特徴の任意の組合せが使用されてもよい。

ステップ１９２０において、グラフィカルオブジェクトの記述子がテンプレート形状の記述子と比較される。制御パラメータの予め定められた組に対するテンプレート形状の記述子と、グラフィカルオブジェクトの記述子との間の距離が定義される。例示的な実施形態において、この距離は、グラフィカルオブジェクトの記述子と、対応するテンプレート形状の記述子との間における差の２乗の合計となる。この距離の尺度の値は、グラフィカルオブジェクトに関する制御パラメータの関数であってもよい。Ｎ個の制御パラメータが存在する場合、この距離の尺度はＮ次元の関数を定義する。制御パラメータの推定値は、通常、関数最小化方法を使用して当該関数の最小値を発見することによって決定される。

ステップ１１６０において、マッチングされた閉じた形態の非テキストのテンプレート形状、及びコネクタ（即ち、ドキュメント内のテンプレート形状に接続する、及び／又はドキュメント内のテンプレート形状の間を接続する線オブジェクト）、及びその他のドキュメントの要素を含む編集可能なドキュメントを作成する方法２０００が実行される。ここで方法２０００について、図２０を参照して説明する。方法２０００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。

方法２０００は、第１のステップ２０１０において始まり、ここではプロセッサ２５０５が、マッチングされた閉じた形態の非テキストのテンプレート形状を入力するためのドキュメントファイルを記述し、作成するためにメモリ２５０６内でドキュメントファイルを開く。次のステップ２０２０において、背景画像が修復される。修復は、認識されたテキスト及び形状を元の画像から削除する。形状の一部又はテキストとして認識される画素は、周辺の背景色で置き換えられる。次のステップ２０３０において、この修復された背景画像が、ドキュメントの背景として働くように任意的にドキュメントファイルに書き込まれる。これは、写真画像などの何らかのものを含む可能性がある、認識されなかった任意のオブジェクトがドキュメント中で今まで通り見えることを保証する。ステップ２０４０において、マッチングされたテンプレート形状と、分類された直線コネクタ及び屈曲コネクタとが、対応するパラメータを用いてドキュメントファイルに書き込まれる。コネクタは、それらのコネクタが接続していると認識されたテンプレート形状に接続するように出力される。ステップ２０５０において、あらゆる残りの線オブジェクトが線としてドキュメントファイルに出力される。続いて次のステップ２０６０において、前に認識されたテキスト及び表がドキュメントファイルに追加される。方法２０００は、ドキュメントが完成し、ドキュメントファイルが閉じられる次のステップ２０７０において終了する。

ステップ１２３０において、色レイヤから非線オブジェクトを抽出する方法２１００が実行される。ここで方法２１００について、図２１を参照して説明する。方法２１００は、ハードディスクドライブ２５１０上に存在し、プロセッサ２５０５での実行において制御されるソフトウェアとして実装されてもよい。

方法２１００は、第１のステップ２１１０において始まり、ここでは抽出されるべき非線オブジェクトの外側境界が判定される。ステップ２１１０は、ラスタ順の第１のオブジェクトの画素などの、オブジェクトの境界上にあることが分かっているオブジェクトの点において開始することによって実行される。次に、非線オブジェクトの境界が、各境界画素から隣接する８近傍画素に時計回りに移動することによって辿られる。いったん開始点が再び到達されると、非線オブジェクトの外側境界が完成する。

次のステップ２１２０において、抽出されるべき非線オブジェクトに対してクリティカルポイントのツリーが作成される。最初に、開始点の対が見つけられる。第１の開始点は、抽出されるべき非線オブジェクトの中心から最も遠い点であり、第２の開始点は、非線オブジェクトの境界上で、第１の点から最も遠い点である。これは、第１の点で始まり第２の点で終わる１つの線と、第２の点で始まり第１の点で終わるもう一方の線との２つの線からなる単純な多角形を定義する。各線は抽出されるべき非線オブジェクトの境界の部分の概略を表し、ここで境界の当該部分は、線の始まりと終わりの間を時計回りの方向に移動することによって発見される境界点によって構成される。次に、各線は、最も短い線の長さが到達されるまでさらなる２本の線に再帰的に分割される。一実施形態において、最も短い線の長さは４画素である。再帰的な分割操作において使用される分割点は、線が表す境界の部分上でその線から最も遠い点である。したがって、各線の両方の終端点は非線オブジェクトの境界上にあり、各線は抽出されるべき非線オブジェクトの境界の部分を表す。ステップ２１２０の間に形成された線の全てはメモリ２５０６に記憶され、それぞれの線が当該線がそれらの２本の線に分割される２本の線の親であるツリー構造で表される。

次のステップ２１３０において、ツリー中の各線に対して重要性の尺度が与えられる。一実施形態において、重要性は、線の長さを、その線が表すオブジェクトの境界の部分上の最も遠い点の当該線からの距離で割ったものとして定義される。一実施形態において、最も遠い点の距離は、当該距離が短すぎる場合には最小値まで増加される。一実施形態において、最小値は１画素の距離である。

方法２１００は、次のステップ２１４０において、メモリ２５０６内に構成されるリストに主要な線が書き込まれ、処理を終了する。主要な線とは、ツリー内のそれらの線よりも下の全ての線よりも高い重要性を有する線を示す。多角形の形態でオブジェクトの境界全体を表す主要な線の順序付けられた組が形成され、多角形作成ステップ１２３０が完了する。

ステップ１６６０において、開いている線の終端に関する線の終端のスタイルを判定する方法２２００が実行される。ここで方法２２００について、図２２を参照して詳細に説明する。方法２２００において、ビットマップ中のオブジェクトが、開いている線の終端に対応する線の終端のスタイルを発見するために、線オブジェクトのベクトルが削除された後に解析される。ベクトル化の前のビットマップの例示が図２３（ａ）に示され、ベクトル化の後のビットマップの例示が図２３（ｂ）に示される。図２３（ａ）に示すように、ベクトル化前の画像は、角丸四角形線オブジェクト２３４０に取り付けられた通常の矢印を有する線の終端のスタイルを有する線オブジェクト２３１０、鋭い矢印を有する線の終端のスタイルを有する線オブジェクト２３２０、及び円形の終端のスタイルを有する線の終端のスタイルを有する線オブジェクト２３３０の３つの線オブジェクトを含む。図２３（ｂ）に示すように、ベクトル化の後、これらの線オブジェクトの線の構成要素が削除されて、元の３つの線の終端のスタイル２３５０から２３７０に対応する残りの形状オブジェクトが残される。通常、これらの残りの形状は、非線形制御パラメータを有していない単純なテンプレート形状のオブジェクトとみなされる。例えば、通常の矢印２３２０の先端（即ち、通常の矢尻）が二等辺三角形にマッチングされる一方で、円形の矢尻が円形のテンプレートにマッチングされる。

方法２２００は、残りのビットマップを処理して線の終端のスタイルを判定する。方法２２００は、ステップ２２１０において始まり、ここではビットマップ上の次のオブジェクトが選択される。次にステップ２２２０において、プロセッサ２５０５が次の線の終端のスタイルであるテンプレート形状の候補を選択し、続いてステップ２２３０において、現在のオブジェクトを上述のように方法１８００に従って現在のテンプレート形状に適合させる。

次のステップ２２４０において、さらに線の終端のスタイルであるテンプレート形状の候補が存在する場合、方法２２００はステップ２２２０に戻る。さらなる線の終端のスタイルであるテンプレート形状の候補が存在しない場合、方法２２００はステップ２２５０において継続する。

ステップ２２５０において、最良の候補テンプレート形状が選択され、当該最良の候補テンプレート形状が許容できるかどうかを判定するために、ステップ２２６０においてこのテンプレート形状が閾値と比較される。この閾値は、９０％の適合スコア（即ち、ｆ＞０．９）であることが望ましい。テンプレート形状が許容可能である場合、方法２２００はステップ２２６５に続く。テンプレート形状が許容可能でない場合、方法２２００はステップ２２９５に直接続く。

ステップ２２６５において、少なくとも１つの終端に記憶された線の終端のスタイルを現在有していない次の開いた線オブジェクトが選択される。続いて、ステップ２２７０において、適合された線の終端のスタイルのテンプレート形状が、まだ線の終端のスタイルを有していない現在の線オブジェクトの終端にマッチングされる。次にステップ２２７５において、現在の終端のスタイルのテンプレート形状と現在の線の終端との間のマッチングが許容可能な場合、方法２２００はステップ２２９０に進む。マッチングが許容可能でない場合、方法２２００はステップ２２８０に進む。適合されたテンプレート形状に対する閾値距離内に線の終端点が位置付けられ、線の終端点から、当該線の終端点における線に対する局所的な垂線に沿って射影された適合されたテンプレート形状の重心までの距離が第２の閾値未満であり、テンプレート形状の適合の方向と線の終端点における線の角度との間の角度の差の絶対値が第３の閾値未満である場合に、マッチングは許容可能とみなされる。これらの３つの閾値は、それぞれ線幅の２倍、線幅の２分の１、及び１０度によって与えられることが望ましい。

ステップ２２９０において、プロセッサ２５０５は線の終端のスタイルを記憶し、マッチングされたものとして現在のビットマップオブジェクトに印を付け、続いて方法２２００はステップ２２９５に続く。一方、マッチングが許容可能でない場合、方法２２００はステップ２２８０に続く。記憶されたスタイルを有していない少なくとも１つの終端を有するさらなる開いた線が存在する場合、ステップ２２８０から、方法２２００はステップ２２６５に戻る。さらなる開いた線が存在しない場合、方法２２００はステップ２２９５に続く。処理されるべきさらなるオブジェクトが存在する場合、ステップ２２９５から、方法２２００はステップ２２１０に戻る。さらなるオブジェクトが存在しない場合、線の終端のスタイルの方法２２００は終了する。

ステップ１８５０において、グラフィカルオブジェクトに一致するようにテンプレート形状を修正することに使用するための回転パラメータ及び拡大縮小パラメータを決定する方法２４００が実行される。ここで方法２４００について、図２４を参照して説明する。方法２４００は、拡大縮小パラメータ（ｓ_ｘ及びｓ_ｙ）、及び回転θをより詳細に推定する。これらのパラメータは、現在のグラフィカルオブジェクトの特徴の組を使用して推定される。例示的な実施形態において、拡大縮小パラメータは、回転に対して不変である中心幾何学モーメントの組合せを使用して推定されてもよい。｛ｍ_００，ｍ_２０，ｍ_０２｝及び

は、それぞれ未変換のテンプレート形状の中心幾何学モーメントの組と、グラフィカルオブジェクトの中心幾何学モーメントの組とを表すものとする。ｓ_ｘ及びｓ_ｙによって表される拡大縮小パラメータは、以下の式（１２）、（１３）に従って決定される。

ステップ２４１０において、式（１２）、（１３）を満たす拡大縮小パラメータの絶対値に関する２組の解が、式（１５）、（１６）、（１７）、及び（１８）に従って決定される。

いったん拡大縮小パラメータに対して２組の解が見つけられると、次のステップ２４２０において、プロセッサ２５０５は回転角に関する値を決定する。

例示的な実施形態において、基本的な回転角を決定するために４次のツェルニケモーメントが使用されてもよい。ツェルニケモーメントは、形状検出に使用される（実部及び虚部を含む）複素形状記述子である。４次のツェルニケモーメントは、式（１９）、（２０）に従って０次、２次、及び４次の中心幾何学モーメントによって表される。

ｍ_ｐｑは未変換のテンプレート形状の中心幾何学モーメントを表すものとし、ｍ’_ｐｑはそれぞれｘ軸及びｙ軸に沿ってｓ_ｘ及びｓ_ｙによって拡大縮小した後のテンプレート形状の中心幾何学モーメントを表すものとし、

はグラフィカルオブジェクトの中心幾何学モーメントを表すものとする。同様に、ｚ’_４ｎ及び

（ｎ＝２，４）は、拡大縮小されたテンプレート形状の４次ツェルニケモーメントとグラフィカルオブジェクトの４次ツェルニケモーメントとをそれぞれ表す。

例示的な実施形態において、使用される回転角は式（２１）の根である。

式（２１）は、式（２２）、（２３）、（２４）、及び（２５）に従って形状のモーメントと形状の回転との間の関係を使用して

（ここで、ｃ＝ｃｏｓθ及びｓ＝ｓｉｎθ）式（２６）の極小値を発見することによって導出される。

式（２１）の解は、拡大縮小パラメータの絶対値に関する解のそれぞれに対してθに関する基本的な回転角を与える。θの各値に関して、そのとき、以下の符号付きの拡大縮小パラメータに関する４つの解に対応して追加される最大４つの解が存在する。

｛ｓ_ｘ，ｓ_ｙ｝，｛ｓ_ｘ，−ｓ_ｙ｝，｛−ｓ_ｘ，ｓ_ｙ｝，｛−ｓ_ｘ，−ｓ_ｙ｝
ｓ_ｘ及びｓ_ｙの両方の負数を取るものは１８０度の回転と異なり、当該オプションは以下のように書かれてもよい。

｛ｓ_ｘ，｜ｓ_ｙ｜，θ｝，
｛ｓ_ｘ，｜ｓ_ｙ｜，θ＋π｝，
｛ｓ_ｘ，−｜ｓ_ｙ｜，θ｝，
｛ｓ_ｘ，−｜ｓ_ｙ｜，θ＋π｝
ｘ又はｙ対称性を有するテンプレート形状に関して、ｓ_ｘ及びｓ_ｙの負数はテンプレート形状にいかなる効果も持たず、したがってそれらの可能性は無視されてもよい。また、１８０度回転対称性を有するテンプレート形状は、回転された可能性を考慮する必要がない。両方の種類の対称性を有するテンプレート形状は、それぞれの基本的な角度に対して１つの解の可能性のみを必要とする。

方法２４００は、次のステップ２４３０において終了し、ここでは上述のようにθの各値に対する解の全てがリストに追加される。ステップ１８７０において、適合スコアに基づいて最良の解が決定される。

説明された方法において使用されるテンプレート形状は、Ｍｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅアプリケーションによって定義されたテンプレート形状のうちの１つであってよい。テンプレート形状は、Ｗｒｉｔｅｒ（商標）及びＩｍｐｒｅｓｓ（商標）などのＯｐｅｎＯｆｆｉｃｅ．ｏｒｇ編集アプリケーションによって定義されたテンプレート形状のうちの１つであってもよい。さらに、テンプレート形状は、ＶＩＳＩＯ（商標）編集アプリケーションによって定義されたテンプレート形状のうちの１つであってもよい。その上さらに、テンプレート形状は、ＳｍａｒｔＤｒａｗ．ｃｏｍによって開発されたＳｍａｒｔ Ｄｒａｗ（商標）編集アプリケーションによって定義されたテンプレート形状のうちの１つであってもよい。

説明された構成がコンピュータ及びデータ処理産業に適用可能であることは上述の内容から明らかである。

上述の内容は本発明のいくつかの実施形態のみを説明するが、本発明の範囲及び精神を逸脱することなくそれらの実施形態に修正及び／又は変更がなされることができ、それらの実施形態は例示的であって、限定的ではない。

本明細書の文脈において、用語「含む（ｃｏｍｐｒｉｓｉｎｇ）」は、「主に、しかし必ずしもそれ単独でなく含む（ｉｎｃｌｕｄｉｎｇ）」、又は「持つ」もしくは「含む（ｉｎｃｌｕｄｉｎｇ）」を意味し、「〜のみからなる（ｃｏｎｓｉｓｔｉｎｇ ｏｎｌｙ ｏｆ）」を意味しない。「含む（ｃｏｍｐｒｉｓｅ）」及び「含む（ｃｏｍｐｒｉｓｅｓ）」などの用語「含む（ｃｏｍｐｒｉｓｉｎｇ）」の変化形は、対応して変化した意味を持つ。

以下に記載する付録Ａは、図２７（ａ）及び（ｂ）のＭｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓのそれぞれの名称をそれらの図形の参照とともに一覧にする表である。

付録Ａ
形状の名称 参照番号

四角形 ２７００１
角丸四角形 ２７００２
楕円 ２７００３
菱形 ２７００４
二等辺三角形 ２７００５
直角三角形 ２７００６
平行四辺形 ２７００７
台形 ２７００８
六角形 ２７００９
八角形 ２７０１０
プラス記号 ２７０１１
星 ２７０１２
矢印 ２７０１３
太い矢印 ２７０１４
ホームベース ２７０１５
吹き出し ２７０１６
シール ２７０１７
ブローチ ２７０１８
山形 ２７０１９
五角形 ２７０２０
８角シール ２７０２１
１６角シール ２７０２２
３２角シール ２７０２３
くさび四角形コールアウト ２７０２４
くさび角丸四角形コールアウト ２７０２５
くさび楕円コールアウト ２７０２６
波形 ２７０２７
左矢印 ２７０２８
下矢印 ２７０２９
上矢印 ２７０３０
左右矢印 ２７０３１
上下矢印 ２７０３２
不規則シール１ ２７０３３
不規則シール２ ２７０３４
稲妻 ２７０３５
ハート ２７０３６
四方向矢印 ２７０３７
左矢印コールアウト ２７０３８
右矢印コールアウト ２７０３９
上矢印コールアウト ２７０４０
下矢印コールアウト ２７０４１
左右矢印コールアウト ２７０４２
上下矢印コールアウト ２７０４３
四方向矢印コールアウト ２７０４４
左上矢印 ２７０４５
上屈折矢印 ２７０４６
屈折矢印 ２７０４７
２４角シール ２７０４８
Ｖ字型右矢印 ２７０４９
ブロックアーク ２７０５０
環状矢印 ２７０５１
Ｕターン矢印 ２７０５２
フローチャートプロセス ２７０５３
フローチャート判断 ２７０５４
フローチャート入出力 ２７０５５
フローチャート書類 ２７０５６
フローチャート端子 ２７０５７
フローチャート準備 ２７０５８
フローチャート手操作入力 ２７０５９
フローチャート手作業 ２７０６０
フローチャート結合子 ２７０６１
フローチャートせん孔カード ２７０６２
フローチャートせん孔テープ ２７０６３
フローチャート抜き出し ２７０６４
フローチャート組合せ ２７０６５
フローチャートオンライン記憶 ２７０６６
フローチャート磁気テープ ２７０６７
フローチャート表示 ２７０６８
フローチャート遅延 ２７０６９
フローチャート代替処理 ２７０７０
フローチャート他ページ結合子 ２７０７１
左右上矢印 ２７０７２
月 ２７０７３
４角シール ２７０７４
二重波形 ２７０７５
立方体 ２７０７６
缶 ２７０７７
ドーナツ ２７０７８
リボン ２７０７９
リボン２ ２７０８０
禁煙 ２７０８１
折り返された角 ２７０８２
面取り ２７０８３
ストライプ右矢印 ２７０８４
縦巻き ２７０８５
横巻き ２７０８６
右カーブ矢印 ２７０８７
左カーブ矢印 ２７０８８
上カーブ矢印 ２７０８９
下カーブ矢印 ２７０９０
雲コールアウト ２７０９１
楕円リボン ２７０９２
楕円リボン２ ２７０９３
フローチャート定義済み処理 ２７０９４
フローチャート内部記憶 ２７０９５
フローチャート複数書類 ２７０９６
フローチャート和接合 ２７０９７
フローチャート論理和 ２７０９８
フローチャート照合 ２７０９９
フローチャート分類 ２７１００
フローチャートオフィス記憶 ２７１０１
フローチャート磁気ディスク ２７１０２
フローチャート磁気ドラム ２７１０３
太陽 ２７１０４

概括的な線多角形を示す図である。 直線コネクタ及び屈曲コネクタによって接続された１組のテンプレート形状を示す図である。 テンプレート形状のうちの１つが移動された図２（ａ）と同じ１組のテンプレート形状を示す図である。 テンプレート形状のうちの１つが移動された図２（ａ）と同じ１組のテンプレート形状を示す図である。 １組の塗り潰されていないテンプレート形状を示す図である。 ドキュメント内で通常見られるいくつかのテンプレート形状の例を示す図である。 テンプレート形状の拡大縮小ｓ_ｘ及びｓ_ｙ、回転θ、並びにオフセットΔｘ及びΔｙのアフィンパラメータが修正されるにつれて変化する五角形テンプレート形状を示す図である。 三角形の傾斜パラメータが修正されるにつれて取得されるいくつかの異なる三角形を示す図である。 １つの制御パラメータを有する１組のテンプレート形状の例を示す図である。 ２つの制御パラメータを有する１組のテンプレート形状の例を示す図である。 ２つの制御パラメータを有するテンプレート形状の例の別の組を示す図である。 角丸長方形テンプレート形状の拡大縮小が修正されるときの角丸長方形テンプレート形状を示す図である。 左から右に向かって増加する線幅パラメータの組を有する塗り潰されていない六角形テンプレート形状を示す図である。 修正可能なテンプレート形状（即ち、閉じた形態の非テキストのテンプレート形状）を含むドキュメントを作成する方法を示すフローチャートである。 グラフィックス領域内のグラフィカルオブジェクトを特定（又は検出）するためにグラフィックス領域を解析する方法を示すフローチャートである。 検出されたグラフィカルオブジェクトを予め定められたテンプレート形状とマッチングする方法を示すフローチャートである。 線オブジェクトを解析する方法を示すフローチャートである。 テンプレート形状及び２つの開いた線オブジェクトを示す図である。 予め定められた分割色マスク／レイヤから開いた線オブジェクト及び閉じた線オブジェクトをベクトルとして抽出する方法を示すフローチャートである。 グラフィカルオブジェクトに対する１組の候補テンプレート形状を決定する方法を示すフローチャートである。 グラフィカルオブジェクトに一致するように候補テンプレート形状を修正するための１組のパラメータを決定する方法を示すフローチャートである。 グラフィカルオブジェクトに一致するようにテンプレート形状を変換する最適な制御パラメータ値を決定する方法を示すフローチャートである。 編集可能なドキュメントを作成する方法を示すフローチャートである。 非線オブジェクトを抽出する方法を示すフローチャートである。 開いた線の終端に関する線の終端のスタイルを判定する方法を示すフローチャートである。 ベクトル化の前のビットマップの一例を示す図である。 ベクトル化の後のビットマップの一例を示す図である。 グラフィカルオブジェクトに一致するようにテンプレート形状を修正することに使用するための回転パラメータ及び拡大縮小パラメータを決定する方法を示すフローチャートである。 説明された構成がそのコンピュータ上で実施される多目的コンピュータの概略構成図である。 屈曲コネクタの分類の一例を示す図である。 、 Ｍｉｃｒｏｓｏｆｔ（商標）ＡｕｔｏＳｈａｐｅｓの抜粋を示す図である。

符号の説明

５００：五角形テンプレート形状
５０１：テンプレート形状
５０２：テンプレート形状
５０３：テンプレート形状
５０４：三角形
５０５：三角形
５０６：三角形
５０７：三角形
６００：１つの制御パラメータを有するテンプレート形状の例の組
６０１：１つの制御パラメータを有するテンプレート形状の例、角丸四角形
６０２：１つの制御パラメータを有するテンプレート形状の例、角丸四角形
６０３：１つの制御パラメータを有するテンプレート形状の例、角丸四角形
６０４：１つの制御パラメータを有するテンプレート形状の例、角丸四角形
６０５：１つの制御パラメータを有するテンプレート形状の例、台形
６０６：１つの制御パラメータを有するテンプレート形状の例、台形
６０７：１つの制御パラメータを有するテンプレート形状の例、台形
６０８：１つの制御パラメータを有するテンプレート形状の例、台形
６０９：１つの制御パラメータを有するテンプレート形状の例、六角形
６１０：１つの制御パラメータを有するテンプレート形状の例、六角形
６１１：１つの制御パラメータを有するテンプレート形状の例、六角形
６１２：１つの制御パラメータを有するテンプレート形状の例、六角形
６１３：１つの制御パラメータを有するテンプレート形状の例、八角形
６１４：１つの制御パラメータを有するテンプレート形状の例、八角形
６１５：１つの制御パラメータを有するテンプレート形状の例、八角形
６１６：１つの制御パラメータを有するテンプレート形状の例、八角形
６１７：１つの制御パラメータを有するテンプレート形状の例、１６角シール
６１８：１つの制御パラメータを有するテンプレート形状の例、１６角シール
６１９：１つの制御パラメータを有するテンプレート形状の例、１６角シール
６２０：１つの制御パラメータを有するテンプレート形状の例、１６角シール
６２１：１つの制御パラメータを有するテンプレート形状の例、月形
６２２：１つの制御パラメータを有するテンプレート形状の例、月形
６２３：１つの制御パラメータを有するテンプレート形状の例、月形
６２４：１つの制御パラメータを有するテンプレート形状の例、月形
７００：２つの制御パラメータを有するテンプレート形状の例の組
７０１：２つの制御パラメータを有するテンプレート形状の例、矢印
７０２：２つの制御パラメータを有するテンプレート形状の例、矢印
７０３：２つの制御パラメータを有するテンプレート形状の例、矢印
７０４：２つの制御パラメータを有するテンプレート形状の例、矢印
７０５：２つの制御パラメータを有するテンプレート形状の例、矢印
７０６：２つの制御パラメータを有するテンプレート形状の例、矢印
７０７：２つの制御パラメータを有するテンプレート形状の例、矢印
７０８：２つの制御パラメータを有するテンプレート形状の例、矢印
７０９：２つの制御パラメータを有するテンプレート形状の例、矢印
７１０：２つの制御パラメータを有するテンプレート形状の例、矢印
７１１：２つの制御パラメータを有するテンプレート形状の例、矢印
７１２：２つの制御パラメータを有するテンプレート形状の例、矢印
７１３：２つの制御パラメータを有するテンプレート形状の例、矢印
７１４：２つの制御パラメータを有するテンプレート形状の例、矢印
７１５：２つの制御パラメータを有するテンプレート形状の例、矢印
７１６：２つの制御パラメータを有するテンプレート形状の例、矢印
８００：２つの制御パラメータを有するテンプレート形状の例の組
８０１：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０２：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０３：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０４：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０５：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０６：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０７：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０８：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８０９：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１０：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１１：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１２：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１３：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１４：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１５：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
８１６：２つの制御パラメータを有するテンプレート形状の例、角丸コールアウト
９１０：角丸長方形テンプレート形状
９２０：角丸長方形形状
１００１：六角形テンプレート形状
１５１０：テンプレート形状
１５２０：接続点
１５３０：接続点
１５４０：接続点
１５５０：接続点、満足できる接続点
１５６０：終端の効果を有していない１つの開いた線オブジェクト
１５７０：一方の終端に矢尻形状を有する１つの開いた線オブジェクト
２３１０：通常の矢印を有する線の終端のスタイルを有する線オブジェクト
２３２０：鋭い矢印を有する線の終端のスタイルを有する線オブジェクト、通常の矢印
２３３０：円形の終端のスタイルを有する線の終端のスタイルを有する線オブジェクト
２３４０：角丸四角形線オブジェクト
２３５０：線の終端のスタイル
２３６０：線の終端のスタイル
２３７０：線の終端のスタイル
２５００：コンピュータシステム
２５０１：コンピュータモジュール
２５０２：キーボード
２５０３：マウスポインタデバイス、マウス
２５０４：バス
２５０５：プロセッサユニット、プロセッサ
２５０６：メモリユニット、半導体メモリ
２５０７：オーディオビデオインターフェース
２５０８：インターフェース
２５０９：記憶装置
２５１０：ハードディスクドライブ（ＨＤＤ）
２５１１：ローカルネットワークインターフェース
２５１２：光ディスクドライブ、ドライブ
２５１３：入力／出力（Ｉ／Ｏ）インターフェース
２５１４：ディスプレイデバイス、ビデオディスプレイ、ディスプレイ
２５１５：プリンタ
２５１６：外付け変調復調装置（モデム）トランシーバデバイス、モデム、外付けモデム
２５１７：スピーカ
２５２０：通信ネットワーク、ネットワーク
２５２１：接続
２５２２：ローカルコンピュータネットワーク
２５２３：接続
２５２４：接続
２５２５：広域ネットワーク
２６０１：部分
２６１０：線オブジェクト
２６２０：線オブジェクト
２６３０：点、第１の点
２６４０：点
２６５０：点
２６６０：点、最後の点
２６７０：点、第２の点
２６８０：点

Claims (16)

1. 編集可能なドキュメントを作成する方法であって、
   ａ．少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析するステップと、
   ｂ．前記グラフィカルオブジェクトを、１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするステップと、
   ｃ．前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択するステップと、
   ｄ．前記線オブジェクトを前記選択された接続点と関連付けるステップと、
   ｅ．前記テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成するステップと
   を含み、
   前記線オブジェクトは、前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、前記テンプレート形状に動的に接続されたままであることを特徴とする方法。
2. 前記複数のテンプレート形状のうちの１つは、１組のテンプレート形状から選択された１組の候補テンプレート形状であることを特徴とする請求項１に記載の方法。
3. 前記候補テンプレート形状は、機械学習分類器を用いて選択されることを特徴とする請求項２に記載の方法。
4. 前記マッチングする前記ステップ（ｂ）は、
   最適な組の制御パラメータを推定するステップと、
   前記グラフィカルオブジェクト及び前記推定された制御パラメータに基づいて、最適な組のアフィンパラメータを推定するステップと、
   前記グラフィカルオブジェクトと、前記推定されたアフィンパラメータ及び前記制御パラメータを使用する前記テンプレート形状との間の一致スコアを計算するステップと
   を含むことを特徴とする請求項１に記載の方法。
5. 前記線オブジェクトを分類するステップをさらに含むことを特徴とする請求項１に記載の方法。
6. 前記線オブジェクトが屈曲コネクタとして分類されることを特徴とする請求項１に記載の方法。
7. 前記線オブジェクトが直線コネクタとして分類されることを特徴とする請求項１に記載の方法。
8. 前記テンプレート形状のそれぞれが有限の接続点の組を有することを特徴とする請求項１に記載の方法。
9. 前記テンプレート形状が最大で４つの制御パラメータを含むことを特徴とする請求項１に記載の方法。
10. 前記グラフィカルオブジェクトに一致するように、少なくとも１つの修正可能な閉じた形態である非テキストの前記テンプレート形状を修正するステップをさらに含むことを特徴とする請求項１に記載の方法。
11. 前記テンプレート形状は、Ｍｉｃｒｏｓｏｆｔ ＡｕｔｏＳｈａｐｅｓのうちの１つであることを特徴とする請求項１に記載の方法。
12. 前記テンプレート形状は、ＯｐｅｎＯｆｆｉｃｅ（商標）アプリケーションによって定義されたテンプレート形状のうちの１つであることを特徴とする請求項１に記載の方法。
13. 前記テンプレート形状は、ＶＩＳＩＯ（商標）アプリケーションによって定義されたテンプレート形状のうちの１つであることを特徴とする請求項１に記載の方法。
14. 前記テンプレート形状は、ＳＭＡＲＴ ＤＲＡＷ（商標）アプリケーションによって定義されたテンプレート形状のうちの１つであることを特徴とする請求項１に記載の方法。
15. 編集可能なドキュメントを作成する装置であって、
    少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析する解析手段と、
    前記グラフィカルオブジェクトを、１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするマッチング手段と、
    前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択する選択手段と、
    前記線オブジェクトを前記選択された接続点と関連付ける関連付け手段と、
    前記テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成する作成手段と、
    を備え、
    前記線オブジェクトは、前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、前記テンプレート形状に動的に接続されたままであることを特徴とする装置。
16. 編集可能なドキュメントを作成するための手順をコンピュータに実行させるプログラムを記憶したコンピュータ読み取り可能な記憶媒体であって、
    前記プログラムは、
    少なくとも１つのグラフィカルオブジェクトのビットマップ表現及び線オブジェクトのビットマップ表現を検出するためにビットマップ画像を解析するステップと、
    前記グラフィカルオブジェクトを、１つ以上の予め定められた不連続な接続点を有する複数の予め定められたテンプレート形状のうちの１つとマッチングするステップと、
    前記線オブジェクトの少なくとも１つの終端が前記予め定められた接続点のうちの１つの予め定められた距離内にある場合に前記線オブジェクトに対して前記予め定められた接続点のうちの１つを選択するステップと、
    前記線オブジェクトを前記選択された接続点と関連付けるステップと、
    前記テンプレート形状に接続された前記線オブジェクトとともに前記テンプレート形状を含む編集可能なドキュメントを作成するステップと、
    を含み、
    前記線オブジェクトは、前記ドキュメント内で前記テンプレート形状が修正されると、前記選択された接続点と関連付けられたままであり、その結果、前記テンプレート形状に動的に接続されたままであることを特徴とする記憶媒体。

Images