ビットマップ画像からのオブジェクト表現の生成

【課題】単一の画像から透明な重なりグラフィックオブジェクトを部分的に検出しかつ構成する。
【解決手段】オブジェクト表現をビットマップ画像から生成する方法（５００）、装置及びコンピュータ読み取り可能な記憶媒体が開示される。背景領域を含む一組の領域がビットマップ画像から選択される（５１０）。第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータが、一組の領域の色に応じて推定される（５２０）。推定された色及び部分的な透明性は、透明性合成モデルと一致する。第１及び第２のグラフィックオブジェクトの幾何形状モデルは、一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとから構成される（５３０）。オブジェクト表現は幾何形状モデルに応じて生成される（５４０）。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にビットマップ画像の処理に関し、特に１つ以上の部分的に透明な重なりグラフィックオブジェクトを有するビットマップ画像のオブジェクト表現に関する。
【背景技術】
【０００２】
増加し続ける計算処理能力と組み合わされた画像技術の普及に伴い、文書解析システムの分野では数多くの進展が見られる。大部分の社内文書は、Microsoft（登録商標）Word（登録商標）やMicrosoft（登録商標）Powerpoint（登録商標）などの構造化テキスト／グラフィック編集アプリケーションを使用して生成される。これらのテキスト／グラフィック編集アプリケーションは、フォーマット済みテキストの編集に加えて、基本的な図形描画ツールやオプションを含んでいる。「スキャントゥエディタブル」アプリケーションと呼ばれる重要な種類の文書解析アプリケーションは、文書のビットマップ表現を処理し、編集アプリケーションを使用して閲覧及び編集可能な文書の電子版を生成する。
【０００３】
一般的な構造化テキスト／グラフィック編集アプリケーションの図形描画オプションには、自由線描画、テンプレート形状及びコネクタ（すなわち、文書内のテンプレート形状間及び／又はテンプレート形状に連結する動的な線オブジェクト）が含まれる。テキスト／グラフィック編集アプリケーションには、複数組のグラフィックオブジェクトに対する着色、塗りつぶし、階層化及びグループ化オプションも含まれている。共通に使用される多くの幾何形状は、テンプレート形状を使用して作成できる。このオプションは望ましい形状の表現に関してより速く且つより正確であり、その後の編集がより容易になるため、ユーザは自由線を使用して形状を描画するよりもテンプレート形状を使用することを好む。Microsoft（登録商標）AutoShapeセットは、Microsoft（登録商標）Word（登録商標）やPowerPoint（登録商標）などの編集環境で操作可能なテンプレート形状の多くの例を含む。他のテンプレート形状は、Writer（登録商標）やImpress（登録商標）アプリケーションなど、OpenOffice.org（登録商標）編集アプリケーションに見つけられる。
【０００４】
重なり形状の何れかがベタ塗り又は塗りつぶしのない線形状である場合に、重なり形状を検出する技術がある。しかし、これらの技術は下位層形状が下から部分的に見えるように、上位層形状が部分的な透明性を有する場合には対処していない。
【０００５】
写真合成を目的として単一のオブジェクトを透明グラフィックオブジェクトとして表現する別の技術がある。しかし、これらの技術は透明オブジェクトが第２のオブジェクトと交差する場合には対処せず、色空間表現の外側境界上で限定された一組の色を有するオブジェクトを検出できるだけである。
【０００６】
多重ビデオフレームの処理に基づき透明領域を映像から検出する技術もある。しかし、これらの技術は複数の透明領域が交差する場合には対処せず、２つの画像間の相違が一方の画像中の透明オブジェクトの存在に起因するような少なくとも２つの画像を必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
単一の画像から透明な重なりグラフィックオブジェクトを部分的に検出し且つ再構成する技術が求められている。
【課題を解決するための手段】
【０００８】
本発明の一態様よると、オブジェクト表現をビットマップ画像から生成するコンピュータにより実現される方法が提供される。前記方法は、ビットマップ画像の背景領域を含む一組の領域をビットマップ画像から選択するステップと、一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するステップであって、推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するステップと、一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとから第１及び第２のグラフィックオブジェクトの幾何形状モデルを構成するステップと、幾何形状モデルに応じてオブジェクト表現を生成するステップとを有する。
【０００９】
オブジェクト表現は電子文書でもよく、ビットマップ画像は文書の走査版でもよい。
【００１０】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、第１及び第２のグラフィックオブジェクトの重複部の領域として考えられる一組の領域である第１の領域と、第１のグラフィックオブジェクトの一部として考えられる第１の領域に隣接する一組の領域である第２の領域と、第２のグラフィックオブジェクトの一部として考えられる第１の領域に隣接する一組の領域である第３の領域と、に応じて推定される。
【００１１】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、色差がビットマップ画像の第１の領域の色と、第２及び第３の領域並びに背景領域の色を考慮して透明性合成モデルにより定義される色との間で最小になるように推定されてもよい。
【００１２】
第２のグラフィック領域は部分的に透明でもよい。
【００１３】
第１のグラフィックオブジェクトは第２のグラフィックオブジェクト及び第３のグラフィックオブジェクトに部分的な透明性をもって重なり、第２のオブジェクトは第３のオブジェクトに部分的な透明性をもって重なり、第１、第２及び第３のグラフィックオブジェクトは部分的な透明性をもって重なり、一組の領域は第１の領域と、第１の領域の外側境界に隣接する少なくとも３つの領域と、背景領域とを備え、３つの隣接領域の各々は、部分的な透明性を有するグラフィックオブジェクトの内の２つの重なりに対応する色及び透明性パラメータを含む関連透明性モデルを有し、３つの隣接領域の透明性モデルは、部分的な透明性を有する３つのグラフィックオブジェクトの重なりに対応する透明性モデルと一致する。
【００１４】
３つのグラフィックオブジェクトは部分的な透明性をもって重なる円でもよい。
【００１５】
グラフィックオブジェクトの幾何形状モデルは、辿った境界線に隣接する領域の透明性モデルを追跡しながら領域の境界線を辿ることにより構成されてもよい。グラフィックオブジェクトの色、透明性及び階層化パラメータは、グラフィックオブジェクトの幾何形状モデルを構成する際に横断された境界線に隣接する領域の透明性モデルに応じて設定されてもよい。
【００１６】
本発明の別の態様よると、オブジェクト表現をビットマップ画像から生成する装置が提供される。前記装置は、データとコンピュータプログラムとを記憶するメモリと、コンピュータプログラムを実行するために、メモリに連結されたプロセッサ部とを有し、メモリ及びプロセッサは、オブジェクト表現をビットマップ画像から生成するように構成されている。コンピュータプログラムは、
ビットマップ画像の背景領域を含む一組の領域をビットマップ画像から選択するコンピュータプログラムコードモジュールと、
一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するコンピュータプログラムコードモジュールであって、推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するコンピュータプログラムコードモジュールと、
一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとから第１及び第２のグラフィックオブジェクトの幾何形状モデルを構成するコンピュータプログラムコードモジュールと、
幾何形状モデルに応じてオブジェクト表現を生成するコンピュータプログラムコードモジュールとを備える。
【００１７】
オブジェクト表現は電子文書でもよく、ビットマップ画像は文書の走査版でもよい。
【００１８】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、第１及び第２のグラフィックオブジェクトの重複部の領域として考えられる一組の領域である第１の領域と、第１のグラフィックオブジェクトの一部として考えられる第１の領域に隣接する一組の領域である第２の領域と、第２のグラフィックオブジェクトの一部として考えられる第１の領域に隣接する一組の領域である第３の領域と、に応じて推定されてもよい。
【００１９】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、色差がビットマップ画像の第１の領域の色と、第２及び第３の領域並びに背景領域の色を考慮して透明性合成モデルにより定義される色との間で最小になるように推定されてもよい。
【００２０】
第２のグラフィック領域は部分的に透明でもよい。
【００２１】
グラフィックオブジェクトの幾何形状モデルは、辿った境界線に隣接する領域の透明性モデルを追跡しながら領域の境界線を辿ることにより構成されてもよい。
【００２２】
本発明の更なる態様よれば、プロセッサ部による実行のためにオブジェクト表現をビットマップ画像から生成するコンピュータプログラムが記録されたコンピュータ読み取り可能な記憶媒体が提供される。前記コンピュータプログラムは、ビットマップ画像の背景領域を含む一組の領域をビットマップ画像から選択するコンピュータプログラムコードモジュールと、一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するコンピュータプログラムモジュールであって、推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するコンピュータプログラムコードモジュールと、一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとから第１及び第２のグラフィックオブジェクトの幾何形状モデルを構成するコンピュータプログラムコードモジュールと、幾何形状モデルに応じてオブジェクト表現を生成するコンピュータプログラムコードモジュールとを備える。
【００２３】
オブジェクト表現は電子文書でもよく、ビットマップ画像は文書の走査版でもよい。
【００２４】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、第１及び第２のグラフィックオブジェクトの重複部の領域であると考えられる一組の領域の第１の領域と、第１のグラフィックオブジェクトの一部であると考えられる第１の領域に隣接する一組の領域の第２の領域と、第２のグラフィックオブジェクトの一部であると考えられる第１の領域に隣接する一組の領域の第３の領域とに応じて推定されてもよい。
【００２５】
第１のグラフィックオブジェクトの部分的な透明性パラメータは、色差がビットマップ画像の第１の領域の色と、第２及び第３の領域並びに背景領域の色を考慮して透明性合成モデルにより定義される色との間で最小になるように推定されてもよい。
【００２６】
第２のグラフィック領域は部分的に透明でもよい。
【００２７】
本発明の更に別の態様よると、オブジェクト表現をビットマップ画像から生成するコンピュータにより実現される方法が提供される。前記方法は、部分的な透明性を持つ独立した第１のグラフィックオブジェクトと共に独立した第２のグラフィックオブジェクトを含む前記ビットマップ画像から、各々が塗りつぶし色を持つ塗りつぶし領域と各々が線色を持つ線領域との一組を判定するステップと、線領域の少なくとも１つにより分離された２つ以上の塗りつぶし領域を位置決めし、位置決めされた領域を隣接させることにより塗りつぶし領域の隣接性データを生成するステップと、塗りつぶし色と塗りつぶし領域の隣接性データとに応じて第２のグラフィックオブジェクトに重なる第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するステップと、線領域のうちの少なくとも１つの領域の線色に基づいて第２のグラフィックオブジェクトの輪郭線の単一の線色を決定するステップと、オブジェクト表現を生成するために、推定された色及び部分的な透明性パラメータを有する第１の独立したグラフィックオブジェクトと、決定された単一の線色を有する第２の独立したグラフィックオブジェクトとを記憶するステップとを有する。
【００２８】
単一の線色は、第１のオブジェクトの推定された色及び部分的な透明性パラメータに基づいて決定され、第１のオブジェクトにより重ねられる線領域の線色は第１のオブジェクトの推定された色及び部分的な透明性パラメータにより修正された場合に単一の線色と一致する。
【００２９】
第１及び第２のグラフィックオブジェクトを記憶するステップは、線色が第１のオブジェクトの推定された色及び部分的な透明性パラメータにより修正された場合、単一の線色と第１のグラフィックオブジェクトにより重ねられる線領域の内の１つの領域の線色との間の比較に依存してもよい。
【図面の簡単な説明】
【００３０】
【図１】本発明の１つ以上の実施形態が使用可能なシステムを例示する概略ブロック図である。
【図２ａ】、
【図２ｂ】、
【図２ｃ】部分的な透明性で重なる一組のグラフィックオブジェクトを例示する図である。
【図３ａ】、
【図３ｂ】部分的な透明性で重なる一組の３つのグラフィックオブジェクトを例示する図である。
【図４】部分的な透明性で重なる階層化グラフィックオブジェクトの種々の配置を例示するブロック図である。
【図５ａ】オブジェクト表現をビットマップ画像から生成する方法を例示する概略フローチャートである。
【図５ｂ】ビットマップ画像を処理する実施形態を例示する概略フローチャートである。
【図６】部分的な透明性で重なるグラフィックオブジェクトを検出及び構成する方法を例示する概略フローチャートである。
【図７】複数対のグラフィックオブジェクトの重なり領域に対応する一組の透明性モデルを検出する方法を例示する概略フローチャートである。
【図８】処理ステップ６３０での３つの重なりグラフィックオブジェクトの重なり領域に対応する一組の透明性モデルを検出する処理方法８００を例示する概略フローチャートである。
【図９】一組の領域及び透明性モデルに応じてグラフィックオブジェクトを構成する方法を例示する概略フローチャートである。
【図１０】ある境界線から開始する一組の透明性モデルに応じてグラフィックオブジェクトを生成する方法を例示する概略フローチャートである。
【図１１ａ】、
【図１１ｂ】記載の構成が実施可能な汎用コンピュータシステムを示す概略ブロック図である。
【図１２】重なりグラフィックオブジェクトの線スタイルを検出する方法を例示する概略フローチャートである。
【図１３ａ】、
【図１３ｂ】、
【図１３ｃ】部分的な透明性で重なる線を有する同一組のグラフィックオブジェクトを例示する図である。
【図１４】部分的な透明性で重なる階層化グラフィックオブジェクトの種々の配置を例示する図である。
【図１５ａ】オブジェクト表現をビットマップ画像から生成する方法を例示する概略フローチャートである。
【図１５ｂ】ビットマップ画像を処理する実施形態を例示する概略フローチャートである。
【図１６】オブジェクトの周囲に一致した線スタイルが存在するかを判定し、もしあれば線スタイルを算出する方法を例示する概略フローチャートである。
【図１７】線を除去し、塗りつぶし領域間の隣接性を回復するためにオブジェクト表現を修正する方法を例示する概略フローチャートである。
【図１８】線領域を除去する場合に使用する始点及び終点の選択を例示する概略フローチャートである。
【図１９】線領域の外側の周囲の入力境界線を検出する方法を例示する概略フローチャートである。
【図２０】入力境界線を分解する方法を例示する概略フローチャートである。
【図２１】線領域及びその周囲の領域を線領域の境界に隣接する境界線と共に示す図である。
【図２２】線領域を除去し、周囲の領域を再連結する中間段階における図２１の同一線領域を示す図である。
【図２３】線領域を図２１から除去した最終結果とその結果生じる境界線とを示す図である。
【図２４】線領域の多数の異なる幾何形状を示す図である。
【図２５】線の骨格に沿って領域を連結する方法を示す概略フローチャートである。
【図２６】複数の領域を線領域上で再連結した後にこれらの領域の新しいトポロジを分解する方法を示す概略フローチャートである。
【図２７】部分的な透明性と線スタイルで重なるグラフィックオブジェクトを検出及び構成する方法を示す概略フローチャートである。
【発明を実施するための形態】
【００３１】
オブジェクト表現をビットマップ画像から生成する方法、装置、及びコンピュータ読み取り可能な媒体が開示される。以下の説明では、特定のグラフィックオブジェクト形状、色空間、及び図形コンテンツ等を含む多数の具体的な詳細を説明する。しかし、本発明の範囲から逸脱することなく変形及び／又は代替が可能であることは本開示より当業者には明らかであろう。状況によっては、本発明を不明確にしないよう具体的な詳細を省略してもよい。
【００３２】
１つ以上の添付の図面において同一の図中符号を有するステップ及び／又は特徴を参照する際に、これらのステップ及び／又は特徴は反対の意図がない限り、説明を目的として同一の機能や動作を有する。
【００３３】
［システムの概要］
図１に、本発明の１つ以上の実施形態が使用可能なシステムを例示する。文書１１０はスキャナ１２０により走査され、入力走査済文書画像１３０が形成されてビットマップ画像としてメモリに記憶される。入力走査済文書画像１３０は、本発明の１つ以上の実施形態に応じて処理モジュール１４０において処理される。処理モジュール１４０は、本発明の実施形態に応じて部分的に透明なオブジェクトの検出及び再構成を含む多数のビットマップ画像解析処理段階を行ってもよい。線スタイル、塗りつぶしスタイル（部分的に透明な塗りつぶし部を含む）及び矢印など種々のスタイルを持つテンプレート形状、コネクタ及び自由形式要素の形式の図形コンテンツを含むビットマップ画像１３０（すなわち、走査済文書）のファイル記述又はオブジェクト表現１５０を生成してもよい。ファイル１５０は、ファイル１５０が提供されるコンピュータ１６０など、好適なデバイス上の構造化テキスト／グラフィック編集アプリケーションを用いた編集に好適な図形要素１６１及び１６２（グラフィックオブジェクト）を含んでもよい。
【００３４】
文書１１０は種々のコンテンツの種類を有する複合文書でもよい。コンテンツは、テキスト１１１及び表１１２など非図形要素に加え、透明なグラフィックオブジェクト１１４を部分的に重ねるフローチャート１１３、及び他のチャート１１５など図形要素を含んでもよいが、これらに限定されない。文書１１０はプリンタ、ＦＡＸ装置、プロジェクタ、又はペンと紙、ホワイトボードなど他の従来の媒体を含む種々の装置を使用して生成でき、元電子文書の不完全な表現でもよい。スキャナ１２０は、独立型スキャナ、ハンドヘルド型スキャナ又は多機能プリンタなど、より大型のシステムに組み込まれたスキャナでもよい。スキャナ１２０は、カメラ、携帯電話又は電子手帳など、他の撮像装置でもよい。スキャナ１２０により入力走査済文書画像１３０に雑音が入ることもある。処理モジュール１４０の例としては、コンピュータ、多機能プリンタ、携帯電話又は電子手帳がある。
【００３５】
透明性は、自由形式やテンプレート形状など、グラフィックオブジェクトの塗りつぶしスタイルに対して定義できる。部分的に透明な塗りつぶしグラフィックオブジェクトは、その部分的に透明な塗りつぶしグラフィックオブジェクトの下にあるオブジェクトや背景領域を完全に覆い隠せない。透明性モデルは、グラフィックオブジェクトの塗りつぶし部と部分的に透明な塗りつぶしグラフィックオブジェクトの真下の色とをある点で合成する方法を定義するのに使用される。グラフィックオブジェクトの透明性は、グラフィックオブジェクトの内部で変化したり又は一定であるようなモデルのパラメータである。ここで、完全な透明性は値「１」の透明性パラメータであり、透明性「０」は値「０」のパラメータであるが、システムの中には百分率（「０」を示す０％や完全な透明性を示す１００％）等の他の定義で動作するものもある。
【００３６】
一般に、透明性合成モデルは、各色チャンネルに対してある点において別々に重なる複数のグラフィックオブジェクトの色の凸結合として合成色を定義する。上位層のオブジェクトが色チャンネル値Ｃ⁽ⁱ⁾upperと透明性パラメータαupperとを有し、下位層のオブジェクトが色チャンネル値Ｃ⁽ⁱ⁾lowerを有する場合、合成色チャンネル値Ｃ⁽ⁱ⁾は以下のようになる。
【００３７】

【００３８】
３つ以上のオブジェクトが重ね合わされた場合、式（１）は複数回使用される。すなわち、複数層の合成結果である色を有する単一の層になるまで、後側の対の層が式（１）により決定された色を有する単一の層に繰り返し変換される。
【００３９】
処理された色チャンネルは、通常赤−緑−青（ＲＧＢ）色空間から得られる。この場合、上述の線形モデルを用いて透明性で合成することで得られた色が適切な範囲に存在することが保証される。しかし、処理された色チャンネルが他の色空間に定義される場合は、範囲外の色が得られ、処理によってはこれを取り扱う必要がある。別の透明性合成モデルも存在するが、この線形モデルはコンピュータグラフィックスで最も一般的に使用されている。
【００４０】
透明性は、いくつかの参考文献や製品では不透明性、透光性又はアルファチャンネルに関して検討されている。透光性及びアルファチャンネルが透明性と同一のものを意味する一方、不透明性は逆のパラメータである（一般に、不透明性＝１−透明性）。コンピュータグラフィックスのアプリケーションの中には、一般に効率化のために事前に乗算された色（透明性を事前に乗算された色）に関して計算を行うものがある。
【００４１】
本発明の実施形態は、上側グラフィックオブジェクト又は複数のグラフィックオブジェクトが固定の部分的な透明性（すなわち、オブジェクト上で変化しない０よりも大きく１より小さい透明性パラメータ）を有する場合、重なるグラフィックオブジェクトの幾何形状モデルを検出し且つ構成するように設計されている。簡潔にするため、他のオブジェクトと重ならないと分かったオブジェクトは透明性「０」を有すると仮定する。２つ以上の解釈が処理中のオブジェクトを正確にモデル化できる場合は、単一の単純な解釈が選択される。
【００４２】
［コンピュータシステムの実現形態］
図１１ａ及び図１１ｂは、上述の種々の構成が実施可能な汎用コンピュータシステム１１００の概略ブロック図を一括して形成する。
【００４３】
図１１ａに示すように、コンピュータシステム１１００は、コンピュータモジュール１１０１と、キーボード１１０２、マウスポインタデバイス１１０３、スキャナ１１２６、カメラ１１２７、マイク１１８０等の入力装置と、プリンタ１１１５、表示装置１１１４及びスピーカー１１１７を含む出力装置とからなる。外部変調復調（モデム）送受信装置１１１６は、接続１１２１を介して通信ネットワーク１１２０と通信するためにコンピュータモジュール１１０１により使用されてもよい。ネットワーク１１２０は、インターネットや専用ＷＡＮ等の広域通信網（ＷＡＮ）でもよい。接続１１２１が電話線の場合、モデム１１１６は従来の「ダイアルアップ」モデムでもよい。あるいは、接続１１２１が大容量(例えば、ケーブル）接続の場合、モデム１１１６はブロードバンドモデムでもよい。無線モデムはネットワーク１１２０に無線接続するために使用されてもよい。
【００４４】
コンピュータモジュール１１０１は、少なくとも１つのプロセッサ部１１０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）や半導体読出し専用メモリ（ＲＯＭ）からなるメモリ部１１０６とを一般に含む。モジュール１１０１は、表示端末１１１４、スピーカー１１１７及びマイク１１８０に結合するオーディオビデオインタフェース１１０７と、キーボード１１０２、マウス１１０３、スキャナ１１２６、カメラ１１２７及びオプションであるジョイスティック(不図示）の入出力（Ｉ／Ｏ）インタフェース１１１３と、外部モデム１１１６及びプリンタ１１１５のインタフェース１１０８とを含む多数のＩ／Ｏインタフェースも含む。いくつかの実現形態では、モデム１１１６は例えばインタフェース１１０８内のコンピュータモジュール１１０１に内蔵されてもよい。コンピュータモジュール１１０１は、コンピュータシステム１１００のローカルエリアネットワーク（ＬＡＮ）として知られるローカルコンピュータネットワーク１１２２への結合を、接続１１２３を介して許可するローカルネットワークインタフェース１１１１も有している。例示するように、ローカルネットワーク１１２２は、所謂「ファイアウォール」装置又は同様の機能の装置を一般に含む接続１１２４を介して広域ネットワーク１１２０に結合してもよい。インタフェース１１１１は、Ethernet（登録商標）回路カード、Bluetooth（登録商標）無線装置又はIEEE802.11無線装置から形成されてもよい。
【００４５】
インタフェース１１０８及び１１１３はシリアル接続性及びパラレル接続性の一方又は両方を提供してもよく、前者は一般にユニバーサルシリアルバス（ＵＳＢ）規格により実現されて対応するＵＳＢコネクタ（不図示）を有する。記憶装置１１０９が提供され、ハードディスクドライブ（ＨＤＤ）１１１０を一般に含む。フロッピー（登録商標）ディスクドライブや磁気テープドライブ（不図示）等の他の記憶装置が使用されてもよい。光ディスクドライブ１１１２は、不揮発性のデータ源として動作するように一般に提供される。光ディスク（例えば、ＣＤ−ＲＯＭやＤＶＤ）、ＵＳＢ−ＲＡＭ及びフロッピー（登録商標）ディスク等の携帯型メモリ装置は、システム１１００の適切なデータ源として使用されてもよい。
【００４６】
一般にコンピュータモジュール１１０１の構成要素１１０５〜１１１３は、当業者には既知のコンピュータシステム１１００の従来の動作モードとなるように相互接続されたバス１１０４を介して通信する。上述の構成が実施可能なコンピュータの例には、IBM-PCや互換機、Sun SparcstationsやApple Mac（登録商標）、あるいはそれから進化した同様のコンピュータシステムが含まれる。
【００４７】
オブジェクト表現をビットマップ画像から生成する方法は、図５乃至図１０の処理がコンピュータシステム１１００で実行可能な１つ以上のソフトウェアアプリケーションプログラム１１３３として実現されるコンピュータシステム１１００を使用して実現されてもよい。特に、オブジェクト表現をビットマップ画像から生成する方法のステップは、コンピュータシステム１１００内で実行されるソフトウェア１１３３の命令１１３１によって達成される。ソフトウェア命令１１３１は、各々が１つ以上の特定のタスクを行う１つ以上のコードモジュールとして形成されてもよい。ソフトウェアは２つの別個な部分に分割されてもよく、第１の部分とそれに対応するコードモジュールがオブジェクト表現をビットマップ画像から生成する方法を行い、第２の部分とそれに対応するコードモジュールが第１の部分とユーザとの間のユーザインタフェースを管理する。
【００４８】
ソフトウェア１１３３は、コンピュータ読み取り可能な媒体からコンピュータシステム１１００に一般に読み込まれ、図１１ａに例示するようにＨＤＤ１１１０又はメモリ１１０６に一般に記憶され、その後ソフトウェア１１３３はコンピュータシステム１１００により実行できる。場合によっては、アプリケーションプログラム１１３３はユーザに供給され、１つ以上のＣＤ−ＲＯＭ１１２５上で符号化され、メモリ１１１０又は１１０６への記憶の前に対応するドライブ１１１２を介して読み出されてもよい。あるいは、ソフトウェア１１３３はコンピュータシステム１１００によりネットワーク１１２０又は１１２２から読み出されるか、あるいは他のコンピュータ読み取り可能な媒体からコンピュータシステム１１００に読み込まれてもよい。コンピュータ読み取り可能な記憶媒体とは、実行及び／又は処理のために命令及び／又はデータをコンピュータシステム１１００に提供する際に関与するあらゆる記憶媒体のことを言う。そのような記憶媒体の例としては、デバイスがコンピュータモジュール１１０１の内部にあるか外部にあるかに関わらず、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、ＵＳＢメモリ、光磁気ディスク、又はＰＣＭＣＩＡカード等のコンピュータ読み取り可能なカードがある。ソフトウェア、アプリケーションプログラム、命令及び／又はデータをコンピュータモジュール１１０１に提供する際に関与するコンピュータ読み取り可能な伝送媒体の例としては、他のコンピュータやネットワークデバイスへのネットワーク接続と、ｅメール送信やウェブサイト等に記録された情報を含むインターネット又はイントラネットとに加え、無線又は赤外線伝送チャネルがある。
【００４９】
表示装置１１１４上に描画又は表現する１つ以上のグラフィカルユーザインタフェース（ＧＵＩ）を実現するために、上述のアプリケーションプログラム１１３３の第２の部分とそれに対応するコードモジュールとを実行してもよい。一般にキーボード１１０２とマウス１１０３の操作を通じて、コンピュータシステム１１００及びアプリケーションのユーザは機能的に適応可能にインタフェースを操作し、制御コマンド及び／又は入力をＧＵＩに関連したアプリケーションに提供してもよい。機能的に適応可能なユーザインタフェースの別の形態は、スピーカー１１１７を介して出力された音声プロンプトやマイク１１８０を介して入力されたユーザ音声コマンドを利用した音声インタフェース等として実現されてもよい。
【００５０】
図１１ｂは、プロセッサ１１０５及び「メモリ」１１３４の詳細な概略ブロック図である。メモリ１１３４は、図１１ａのコンピュータモジュール１１０１がアクセス可能な全てのメモリ装置（ＨＤＤ１１１０と半導体メモリ１１０６とを含む）の論理的な集合を示す。
【００５１】
最初にコンピュータモジュール１１０１の電源を入れると、電源投入自己診断（ＰＯＳＴ）プログラム１１５０を実行する。ＰＯＳＴプログラム１１５０は半導体メモリ１１０６のＲＯＭ１１４９に一般に記憶される。ＲＯＭ１１４９等のハードウェア装置に固定的に記憶されたプログラムはファームウェアと呼ばれることがある。ＰＯＳＴプログラム１１５０は、適切に機能しているかを保証するためにコンピュータモジュール１１０１内のハードウェアを検査し、正しく動作するためにプロセッサ１１０５、メモリ（１１０９、１１０６）及びＲＯＭ１１４９に一般に記憶される基本入出力システムソフトウェア（ＢＩＯＳ）モジュール１１５１を一般にチェックする。ＰＯＳＴプログラム１１５０の動作が成功すると、ＢＩＯＳ１１５１はハードディスクドライブ１１１０を起動する。ハードディスクドライブ１１１０の起動により、ハードディスクドライブ１１１０に常駐するブートストラップローダプログラム１１５２をプロセッサ１１０５を介して実行する。これによりオペレーティングシステム１１５３がＲＡＭメモリ１１０６に読み込まれ、オペレーティングシステム１１５３が動作を開始する。オペレーティングシステム１１５３は、プロセッサ管理、メモリ管理、デバイス管理、記憶管理、ソフトウェアアプリケーションインタフェース及び一般のユーザインタフェースを含む種々の高レベルの機能を実現するためにプロセッサ１１０５が実行可能なシステムレベルのアプリケーションである。
【００５２】
オペレーティングシステム１１５３は、コンピュータモジュール１１０１で動作している各処理又はアプリケーションが他の処理に割り当てられたメモリと衝突することなく実行するのに十分なメモリを有することを保証するために、メモリ（１１０９、１１０６）を管理する。更に、システム１１００で利用可能な異なる種類のメモリは、各処理が効率的に動作できるように適切に使用されなければならない。したがって、集合メモリ１１３４は、特定のメモリセグメントがどのように割り当てられるのかを例示するためのものではなく（特に指定がない限り）、コンピュータシステム１１００がアクセス可能なメモリの全体図とその使用方法とを提供するものである。
【００５３】
プロセッサ１１０５は、制御部１１３９と、演算論理部（ＡＬＵ）１１４０と、キャッシュメモリとも呼ばれるローカル又は内部メモリ１１４８とを含む多数の機能モジュールを含んでいる。キャッシュメモリ１１４８は、レジスタ部に多数の記憶レジスタ１１４４〜１１４６を一般に含む。１つ以上の内部バス１１４１はこれらの機能モジュールを機能的に相互接続する。プロセッサ１１０５は、接続１１１８を使用してシステムバス１１０４を介して外部装置と通信するために１つ以上のインタフェース１１４２も一般に有している。
【００５４】
アプリケーションプログラム１１３３は、条件付き分岐及びループ命令を含む一連の命令１１３１を含んでいる。プログラム１１３３は、プログラム１１３３の実行の際に使用されるデータ１１３２を含んでもよい。命令１１３１及びデータ１１３２は、それぞれ記憶場所１１２８〜１１３０及び１１３５〜１１３７に記憶される。命令１１３１の相対的な大きさと記憶場所１１２８〜１１３０とによっては、記憶場所１１３０に示される命令に表されるように特定の命令が単一の記憶場所に記憶されてもよい。あるいは、命令は多数の部分にセグメント化され、各々が記憶場所１１２８〜１１２９に示す命令セグメントに表されるように別個の記憶場所に記憶されてもよい。
【００５５】
一般に、一連の命令がプロセッサ１１０５に与えられ、その内部で実行される。プロセッサ１１０５は以降の入力を待機し、他の一連の命令を実行することによりその入力に対して反応する。各入力は、１つ以上の入力装置１１０２や１１０３により生成されたデータ、ネットワーク１１２０や１１２２の１つを介して外部ソースから受信されたデータ、記憶装置１１０６や１１０９の１つから検索されたデータ、又は対応するリーダ１１１２に挿入された記憶媒体１１２５から検索されたデータを含む多数のソースの内の１つ以上から提供されてもよい。一連の命令を実行することによりデータを出力する場合もある。実行には、データや変数をメモリ１１３４に記憶することが含まれてもよい。
【００５６】
開示された構成では入力変数１１５４を使用し、これらはメモリ１１３４中の対応する記憶場所１１５５〜１１５８に記憶される。これらの構成では出力変数１１６１を生成し、メモリ１１３４中の対応する記憶場所１１６２〜１１６５に記憶される。中間変数は記憶場所１１５９、１１６０、１１６６及び１１６７に記憶されてもよい。
【００５７】
プロセッサ１１０５のレジスタ部１１４４〜１１４６、演算論理部（ＡＬＵ）１１４０及び制御部１１３９は共に動作し、プログラム１１３３を構成する命令群における各命令に対して「取出し−復号−実行」サイクルを行うのに必要な一連のマイクロ動作を行う。各取出し−復号−実行サイクルは下記を含む。
（ａ）命令１１３１を記憶場所１１２８から取出すか又は読出す取出し動作
（ｂ）命令が取り出されたかを制御部１１３９が判定する復号化動作
（ｃ）制御部１１３９及び／又はＡＬＵ１１４０が命令を実行する実行動作
その後、次の命令のための更なる取出し−復号−実行サイクルが実行されてもよい。同様に、記憶サイクルを行ってもよく、これにより制御部１１３９は値を記憶場所１１３２に記憶又は書き込む。
【００５８】
図５〜１０の処理における各ステップ又はサブプロセスは、プログラム１１３３の１つ以上のセグメントに関連付けられ、プログラム１１３３の上述のセグメントの命令群の各命令に対して取出し−復号−実行サイクルを行うために共に動作しているプロセッサ１１０５中のレジスタ部１１４４〜１１４７とＡＬＵ１１４０と制御部１１３９とにより行われる。
【００５９】
あるいは、オブジェクト表現をビットマップ画像から生成する方法は、オブジェクト表現をビットマップ画像から生成する機能やサブ機能を行う１つ以上の集積回路等の専用ハードウェア内で実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ以上のマイクロプロセッサ及び関連メモリを含んでもよい。
【００６０】
［重なるグラフィックオブジェクトの例］
図２に、透明性で重なる一組のグラフィックオブジェクトを例示する。図２ａでは、グラフィックオブジェクト２０１は、部分的な透明性で縦向きの細長い矩形である一方、グラフィックオブジェクト２０２及び２０３は透明性「０」の横向きの細長い矩形（長さ方向が矩形２０１と直交する）及び正方形である。図２ｂに、垂直矩形２０１が水平矩形２０２に重なり、これらが正方形２０３に重なるように、図２ａのオブジェクト２０１、２０２及び２０３を階層化した結果を例示する。正方形２０３は２つの矩形２０１及び２０２の重なり部の背景を効果的に形成する。
【００６１】
図２ｂでは、６つの領域２１０、２１１、２１２、２１３、２１４、及び２１５が合成オブジェクトから形成される。領域２１０は、正方形２０３のみに被覆された領域である。領域２１１及び２１４は、水平矩形２０２と正方形２０３の双方に被覆された領域を示す。水平矩形２０２は透明性「０」であるため、正方形２０３は完全に隠蔽され、領域２１１及び２１４の色は矩形２０２と同一である。領域２１２及び２１５は、垂直矩形２０１と正方形２０３の双方に被覆された領域を示す。垂直矩形２０１は部分的な透明性を有するので、領域２１２及び２１５の色は、正方形２０３及び矩形２０１の色による透明性モデルに応じて決定できる。最後に、領域２１３は全３つのオブジェクト２０１、２０２及び２０３に被覆された領域を示す。この領域において水平矩形２０２は正方形２０３を完全に隠蔽するため、領域２１３の色は、矩形２０１及び２０２の色による透明性モデルに応じて決定できる。図２ｃは後述する。
【００６２】
図３ａは、透明性を有する一組の３つのグラフィックオブジェクト３０１、３０２及び３０３の第２の例示である。本例では、これらのグラフィックオブジェクトはベン図を形成するように部分的な透明性で重なる円である。合成後、低濃度の円３０１は中間濃度の円３０２に重なり、これらはより高濃度の円３０３に重なる。図３ｂは、円形オブジェクト３０１、３０２及び３０２を背景領域３１７に合成して７つの領域を形成した結果を例示する。３つの領域３１０、３１１及び３１２は、単一の円３０１、３０２、３０３が背景３１７上に存在する場所にある。領域３１０、３１１及び３１２の各々の色は、重なりオブジェクト透明性パラメータに応じて、円３０１、３０２、３０３の色を背景３１７と合成することにより得られる。更に３つの領域３１３、３１４及び３１５は、円３０１、３０２及び３０３の内２つが背景３１７上で重なる場所にある。また、領域３１３、３１４及び３１５の色は、領域３１３、３１４及び３１５におけるオブジェクト３０１、３０２、３０３の色を背景色３１７と共に合成することにより得られる。例えば、中間濃度の３０２は、領域３１３において背景３１７上で高濃度の円３０３に重なる。式（１）の透明性モデルによると、後側の対の層を合成することにより右側の大領域３１２の色チャンネル値Ｃ⁽ⁱ⁾1（高濃度の円３０３及び背景３１７）が与えられる。
【００６３】

【００６４】
式中、Ｃ⁽ⁱ⁾dark及びＣ⁽ⁱ⁾backは高濃度の円３０３及び背景３１７の色チャンネル値、αdarkは高濃度の円の透明性パラメータである。本解釈では高濃度の円３０３の透明性は０であり、この場合Ｃ⁽ⁱ⁾1＝Ｃ⁽ⁱ⁾backである。右側の大領域の色は、色チャンネルＣ⁽ⁱ⁾modと透明性（アルファ）パラメータαmodとを有する中間濃度の円と合成され、領域３１３の色Ｃ⁽ⁱ⁾2が与えられる。
【００６５】

【００６６】
全３つの円３０１、３０２及び３０３は領域３１６で重ね合わされ、領域３１６の色は上述のパラメータと淡色の円３０１の色Ｃ⁽ⁱ⁾light及び透明性αlightとを使用して決定できる。
【００６７】

【００６８】
部分的な透明性を有して重なり合う複数のオブジェクトには多数の幾何形状が存在し、これらのいくつかを図４に例示する。図４は、オブジェクトの５つのクラスタを例示し、これらの多くは重なっている。単一のグラフィックオブジェクトに対応する領域４０１〜４１５は、水平又は垂直斜線で示され、上側グラフィックオブジェクトが部分的に透明である２つのグラフィックオブジェクトの重なり領域に対応する領域４２０〜４３１は交差斜線で示される。同一の番号が付された領域は、同一のオブジェクト又は同一組のオブジェクト（例えば、４０１、４０２、４０７、４２０）で被覆された領域に対応する。このように重なる例は本発明の実施例を使用して処理可能であるが、多くの構造化テキスト／グラフィック編集アプリケーションは領域４０８及び４２５に示される自己交差オブジェクトなど、単一の層によって定義されていないオブジェクトを出力できない。
【００６９】
［ビットマップ画像からのオブジェクト表現の生成］
図５ａは、オブジェクト表現をビットマップ画像から生成する方法５００を例示する高レベルのフローチャートである。ビットマップ画像は文書の走査版でもよく、オブジェクト表現は電子文書（例えば、編集可能な）でもよい。方法５００は図１の処理モジュール１４０において実現されてもよく、コンピュータによって実現することもできる。処理はステップ５１０で開始する。ステップ５１０において、一組の領域がプロセッサ１１０５を使用してビットマップ画像から選択され、この一組の領域はビットマップ画像の背景領域を含む。選択ステップ５１０の詳細については、図５ｂを参照してより詳細に後述する。ステップ５２０において、第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータは、一組の領域の色に応じてプロセッサ１１０５を使用して推定される。推定された色及び部分的な透明性は、２つのグラフィックオブジェクトの重複部の領域の色を色及び部分的な透明性パラメータで定義する透明性合成モデルと一致する。第１及び第２のグラフィックオブジェクトの幾何形状モデルは、一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとからプロセッサ１１０５を使用して構成される。ステップ５３０において、第１及び第２のグラフィックオブジェクトの幾何形状モデルは一組の領域から構成され、これらのオブジェクトの推定された色及び透明性パラメータが設定される。ステップ５４０において、オブジェクト表現は幾何形状モデルに応じて生成される。その後、処理は終了する。
【００７０】
図５ｂは、オブジェクト表現（例えば、図１のファイル１５０）を生成するためにビットマップ画像（例えば、図１の走査済文書１３０）を処理する方法５５０をより詳細に例示する。方法５５０は図５ａのステップ５１０をより詳細に示す。ステップ５５５と、５６０と、５６５と、ステップ５７０の６１０〜６３０とがステップ５１０を実現する。方法５５０はステップ５５５で開始する。ステップ５５５において、ビットマップ画像は１つ以上の連結成分に区分される。メモリ１１０６に記憶されたビットマップ画像に対してプロセッサ１１０５により低レベルの画像分割が行われ、画像は色に応じて連結成分（ＣＣ）に分割される。ビットマップ画像の連結成分の各々はメモリ１１０６に記憶される。ステップ５６０において、プロセッサ１１０５は連結成分を分類し、種々の文書コンテンツの種類を識別する。これは、ビットマップ画像の連結成分に対して高レベルの文書レイアウト解析を実行することによって行われる。連結成分は、それらの矩形バウンディングボックスに関して処理されてもよく、処理中にマージ又はグループ化された連結成分でもよい。コンテンツの種類には、テキスト、写真、表、線画及びグラフィックという分類がある。これらのコンテンツの種類の各々は画素データ（すなわち、連結成分）に対応する。
【００７１】
高レベルの文書解析の後、ステップ５６５において、プロセッサ１１０５は定義済み幾何形状を有する領域を生成する。これは連結成分を解析することによって行われる。他の連結成分は図形コンテンツを含む確率が低いと見なされるため、線画及び／又はグラフィック領域として分類された連結成分のみがステップ５６５で処理されるのが好ましい。各領域は、単一の外側境界と、この単一の外側輪郭及び連結成分の一組の０以上の内側輪郭に対応する０以上の内側境界とによって定義できる。図２ｃは、矩形２０１及び２０２のいずれも正方形オブジェクト２０３に重ならない図２ｂの領域２１０に対応する連結成分２４０を例示する。オブジェクト２４０は、単一の外側境界２３０と単一の内側境界２３１とを有する。
【００７２】
境界は境界線区間に関して表現されてもよい。ここでは、用語「境界線」は各辺の長さ方向に隣接する独自の領域を有する境界の区間を記述するために使用される。各境界線は２つの境界に含まれる。２色のみの単純な領域構成は、図２ｃの連結成分２４０の境界２３０を定義する図２ｂの外側境界線２２０のような閉境界線を有する。一方、３色以上のより複雑な領域構成において、複数の境界線は、一緒にリンクされて複数の境界を構成する開区間でもよい。例えば、図２ｂに示す重ね合わされたのオブジェクトの組により、線２２１〜２２８で表現される８本の境界線が存在する５つの小正方形領域２１１〜２１５が形成される。閉境界は各領域の外側の周囲に構成される。例えば、上側小矩形２１５の外側境界は境界線２２８及び２２１を使用して構成できる一方、中央の小矩形２１３の外側境界は境界線２２１、２２７、２２５及び２２３から構成できる。図２ｃの大領域２４０の内側境界２３１も境界線２２８、２２２、２２４及び２２６を使用して構成できる。
【００７３】
多角形表現が自己又は相互交差のない効率的な表現となるように、一組の領域を表す境界線に対して多角形表現を生成する技術がある。境界線に沿った点は好適なデータ構造でメモリ１１０６に記憶され、境界はこれらのデータ構造によって定義される。境界上の連続する点に対して一貫性のある順序付け方式を使用するのは有用である。上述の実施形態において、順方向に横断した場合、外側境界は時計回りのループを形成し、内側境界は反時計回りのループを形成する。この方式では、いずれの境界の周囲であっても順方向に前進すると、領域はその境界の右側に位置する。
【００７４】
図５のステップ５７０において、ステップ５６５で生成された領域に基づいて、部分的な透明性で重なるグラフィックオブジェクトの幾何形状モデルは、図６を参照してより詳細に後述する方法６００に応じて検出され且つ構成される。構成された幾何形状モデルは関連色及び透明性を有する。これには、図５ａのステップ５１０において、領域を選択する最終的なサブステップが含まれる。少なくとも１つのオブジェクトの幾何形状モデルはこの段階で出力されてもよく、例えばこの段階では、グラフィックオブジェクトが自由形状であり特定の図形コンテンツの種類として分類できない。したがって、以降のステップ５７５及び５８０はオプションのステップとして示される。
【００７５】
方法５５０はオプションのステップ５７５（破線で示される）に進む。ステップ５７５では、現在の組の領域に基づいて図形コンテンツが決定される。図形コンテンツは、テンプレート形状、線オブジェクト、矢印、コネクタ及び他のオブジェクトを含んでもよい。本処理は、線及び形状検出、隠蔽形状検出、線リンク解析及びコネクタ解析のための既知の技術を採用してもよい。
【００７６】
ステップ５８０において、プロセッサ１１０５は分類されたグラフィックオブジェクトをオブジェクト表現としてオプションで（再度、破線で示す）出力する。この出力は、構造化テキスト／グラフィック編集アプリケーションでの閲覧及び編集に好適な形式でもよい。その後、方法５５０の処理は終了する。
【００７７】
［幾何形状モデルの検出及び構成］
図６に、図５ａのステップ５１０、５２０及び５３０並びに図５ｂのステップ５７０で使用される部分的な透明性で重なるオブジェクトの幾何形状モデルを検出し且つ構成する方法６００を例示する。処理はステップ６１０で開始する。ステップ６１０において、各々が一対のグラフィックオブジェクトの重なりの領域に対応する一組の透明性モデルが、図７を参照して後述する方法７００に応じて検出され、メモリ１１０６に記憶される。本実施形態において、領域の透明性モデルは以下のパラメータを含むデータ構造で記憶される。
・（一対の重なりオブジェクトの）上側グラフィックオブジェクトに対応する上位層色チャンネル値（Ｃ⁽ⁱ⁾upper）及び透明性パラメータ（αupper）、
・下側グラフィックオブジェクトに対応する下位層色チャンネル値（Ｃ⁽ⁱ⁾lower）、
・背景色チャンネル値（Ｃ⁽ⁱ⁾back）、
・モデルの領域と上側グラフィックオブジェクトの一部を形成する可能性のある領域との間の境界線に対応する上側境界線、
・モデルの領域と下側グラフィックオブジェクトの一部を形成する可能性のある領域との間の境界線に対応する下側境界線、
・モデルの品質を定量化する誤差パラメータ。
【００７８】
検出処理７００では、隣接領域において検出されたモデルの整合性はチェックされないため、透明性モデルデータのフィルタリングはステップ６２０で行われる。透明性モデルが検出された各領域は順次チェックされる。透明性モデルの上側及び下側境界線において、この領域とは反対側にある領域がテストされ、これらの領域も透明性モデルを有するかが確認される。どちらも透明性モデルを有するならば、削除するために、透明性モデルに印を付け、全ての領域を処理した後に削除される。図４は、透明性モデルが検出されるいくつかの隣接領域を例示する。領域４２６及び４２７の双方のモデルは境界線を共有するが、この境界線は何れかの領域の透明性モデルの上側又は下側境界線ではなく、領域４０８と４２６との間、領域４０９と４２６との間、領域４０８と４２７と間及び領域４１０と４２７との間の境界線である。これは領域４２８及び４２９並びに領域４３０及び４３１についても同様である。
【００７９】
透明性モデルのフィルタリングが完了すると、ステップ６３０において、部分的な透明性を有する３つのグラフィックオブジェクトの重なり領域に対応する一組の透明性モデルが、図８を参照して後述する方法８００に応じて検出され、メモリ１１０６に記憶される。ステップ６４０において、透明性モデルに対応するグラフィックオブジェクトの一組の幾何形状モデルは、図９を参照して後述する方法９００に応じて構成される。その後、方法６００の処理は終了する。
【００８０】
図７は、図６の処理ステップ６１０で使用される複数対のグラフィックオブジェクトの重なり領域に対応する一組の透明性モデルを検出する処理方法７００を例示する。処理はステップ７１０で開始する。ステップ７１０において、次の領域が選択される。すなわち、透明オブジェクト処理のために図５ｂのステップ５６０による処理に対して選択された各領域はステップ７１０で選択される。ステップ７２０において、次の境界線が選択される。領域の外側境界の各境界線区間は順次選択される。上述のように、境界線は領域が右側に位置するように方向付けられるのが好ましい。別の実施形態では、内側境界上の境界線を処理してもよいが、これらが有用な透明性モデルとなる可能性は低い。好適な実施形態では、短い境界線区間（例えば、３００ｄｐｉで２画素より短い長さの境界線区間）は本ステップでは処理も選択もされない。
【００８１】
ステップ７３０において、境界線交差が検出される。ステップ７３０では、境界方向の境界線区間の終点における境界線交差を検出する。境界線交差は、透明性モデルが評価できる現在の領域の境界に沿った一対の連続する境界線である。例えば、現在の領域が図２ｂの中央の小正方形領域２１３に対応し、現在の境界線が左側２２３にある場合、境界線交差の第２の境界線はこの領域の上部２２１に沿っている。境界線交差を検出する単純な方法は、境界データ構造に応じて境界上の次の境界線を取得することである。しかし、雑音により又はオブジェクトを生成するための画像処理のアーティファクトとして短い境界線区間が存在する場合、本方法は失敗する可能性がある。この場合、別の方法として、閾値（例えば、３００ｄｐｉで２画素）よりは長いが、境界に沿って過度に長くはない（例えば、３００ｄｐｉで５画素の第２の閾値より短い）次の境界線を選択する。
【００８２】
その後、ステップ７４０に進む。ステップ７４０において、第１の透明性モデル（次のモデル上の先行モデル）をテストする。ステップ７４０では、第１の境界線が上位層にある部分的に透明なオブジェクトの一部を形成する領域に隣接し、第２の境界線が下位層にあるグラフィックオブジェクトの一部を形成する領域に隣接し、これら２つのオブジェクトが現在の領域において重なり且つ共通の背景で囲まれていると仮定する透明性モデルをテストする。上述の図２ｂの例では、処理中の領域が中央の正方形２１３に対応し、２本の境界線２２３及び２２１がそれぞれ左側と上側にある場合、隣接領域は左側及び上側の小正方形領域２１１及び２１５に対応する。
【００８３】
背景又は親領域は、各領域に対して選択される。背景領域を選択する種々の技術が当該分野では既知であり、好ましい一方法では異なる色とある領域を完全に取り囲む異なるバウンディングボックスとを有するページ上の最小領域を検出する。図２ｂに示す例では、全ての小さいオブジェクトは大正方形領域２１０である同一の親又は背景オブジェクトを共有する。
【００８４】
多数のテストを行い、透明性モデルを棄却するかを判定してもよい。まず、隣接領域のいずれかが現在の領域の背景ならば、そのモデルは棄却される。次に、隣接領域のいずれかが以前の処理で例えばテキストとして既に分類されていたら、そのモデルは棄却される可能性がある。第三に、３つの領域の背景色が互いに整合性がないならば、そのモデルは棄却される可能性がある。一対の色の間の整合性をテストする好適な方法では、色チャンネルが０〜２５５の範囲の値を取るＲＧＢ空間の二乗差の合計を計算し、これを閾値と比較する（例えば、類似の色は１０００より小さい二乗誤差の合計を有する可能性がある）。
【００８５】
透明性モデルの一組の色は以下のように定義される。
・Ｃ⁽ⁱ⁾upperは、第２のグラフィックオブジェクトに重なる部分的な透明性を有するグラフィックオブジェクトの一部であると見なされる第１の隣接領域の色チャンネル値である。
・Ｃ⁽ⁱ⁾lowerは、第１のグラフィックオブジェクトに重なる第２のグラフィックオブジェクトの一部であると見なされる第２の隣接領域の色チャンネル値である。
・Ｃ⁽ⁱ⁾bothは、２つのグラフィックオブジェクトの重なり領域であると見なされる現在の領域の色チャンネル値である。
・Ｃ⁽ⁱ⁾backは、背景領域の色チャンネル値である。
ここで、パラメータ（ｉ）は色チャンネル（好適な実施形態では、赤、緑及び青）に対応する。例えば、処理中の領域が図２ｂの中央の小領域２１３ならば、Ｃ⁽ⁱ⁾upperは左側小正方形２１１の色チャンネル値であり、Ｃ⁽ⁱ⁾lowerは上側小正方形２１５の色チャンネル値であり、Ｃ⁽ⁱ⁾bothは中央の小正方形２１３の色チャンネル値であり、Ｃ⁽ⁱ⁾backは大正方形２１０の色チャンネル値である。
【００８６】
上側グラフィックオブジェクトの想定透明性αについては、上側、下側及び背景色に関して重なり領域における色の推定値は以下のようになる。
【００８７】

【００８８】
この式では基本的に、背景と透明性により基準化された下側オブジェクトとの色差に応じて透明オブジェクトが背景の上にある領域の色をシフトすることにより重なり領域の色チャンネル推定値を検出する。シフトの際、透明オブジェクトの下の色差を考慮する。式（５）は、透明性「０」Ｃ⁽ⁱ⁾zeroで上側グラフィックオブジェクトの色チャンネル値を想定し、透明性の合成式（１）により背景及び下側グラフィックオブジェクトに対する合成色チャンネル値を表現することにより以下のように導出できる。
【００８９】

【００９０】
これらの２つの合成色推定値を互いに減算し、透明性「０」で上側オブジェクトの色を推定することで式（５）が得られる。
【００９１】
透明性モデルに対する誤差関数Ｅ（α）は、この推定値を０〜２５５の範囲に限定し、誤差の二乗和を取ることにより得られる。
【００９２】

【００９３】
透明性モデルに対する上側グラフィックオブジェクトの透明性αupperは、透明性の範囲（０≦α≦１）で誤差関数を最小化することにより得られる。誤差関数は一般に、誤差関数がせいぜい１つの極小を有するような間隔で十分に作用し、最小化はブレント法等の関数の括弧付き最小値を検出する既知の数値法を使用して行ってもよい。最小値における誤差関数が好適な閾値（例えば、本実施形態では５００）よりも小さければ、透明性モデルを受入れて、メモリ１１０６に記憶してもよい。
【００９４】
その後、ステップ７５０に進む。ステップ７５０において、第２の透明性モデル（先行モデル上の次のモデル）をテストする。ステップ７５０では、第２の境界線が部分的に透明な上側オブジェクトに隣接し且つ第１の境界線が共通の背景上の下側オブジェクトに隣接すると仮定する透明性モデルをテストする。本処理は、第１の境界線及び第１の隣接領域を第２の境界線及び隣接領域として使用し且つ第２の境界線及び第２の隣接領域を第１の境界線及び隣接領域として使用したステップ７４０に記載の処理と同一であり、Ｃ⁽ⁱ⁾upperが第２の隣接領域に対応し且つＣ⁽ⁱ⁾lowerが第１の隣接領域に対応する。ステップ７６０において、最良の受入れ可能モデル（すなわち、そのようなモデルがあるとすれば、受入れ閾値よりも低い最小の誤差関数得点を有するモデル）が、対応する誤差関数得点と共に好適なデータ構造を使用してメモリ１１０６に記憶される。好適な実施形態において、キーが領域を表す指標に対応し、対応する値が領域に対して検出された透明性モデルのリストであるマップ構造が使用される。ステップ７４０及び７５０からのモデルの内の最良の受入れ可能モデルは、現在の領域のリストに追加される。
【００９５】
決定ステップ７７０において、現在の領域に更なる境界線が存在するかを判定するためのチェックが行われる。ステップ７７０が真（ＹＥＳ）を返すと、ステップ７２０に進む。ステップ７７０が偽（ＮＯ）を返すと、ステップ７８０に進む。
【００９６】
ステップ７８０では、２つ以上の受入れ可能モデルが検出されると、ある領域に対する一組の透明性モデルがフィルタリングされる。その領域に対する最良のモデルは、誤差パラメータが最小のモデルとして選択される。他の各モデルは、整合性のある上側、下側及び背景色と整合性のある透明性パラメータとを有するモデルをチェックすることにより最良のモデルとの整合性をチェックする。同様の透明性パラメータに対する好適なテストではモデル間の相違が０．０５（又は５％）より小さくなり、色を比較する好適な方法はステップ７４０で導入されている。ある領域に対する全ての透明性モデルが最良のモデルと整合性があると検出されると、その領域に対して最良のモデルが受入れられ、他のモデルはもはや必要ではなくなる。一方、１つ以上のモデルが最良のモデルと整合性がない場合、その領域に対する全てのモデルが棄却される。その後、決定ステップ７９０に進む。決定ステップ７９０において、処理すべき更なる領域が存在するかを判定するためのチェックが行われる。ステップ７９０が真（ＹＥＳ）を返すと、ステップ７１０に戻る。ステップ７９０が偽（ＮＯ）を返すと、方法７００は終了する。
【００９７】
図２ｂの例において、領域２１３を処理する際に４つの境界線交差が検出され、各対は２２３と２２１、２２１と２２７、２２７と２２５及び２２５と２２３である。各境界線交差は整合性のある受入れ可能透明性モデルを生成し、この内最良のものが受入れられ、他の３つはフィルタリングにより除去される。図３ｂの例では、３の境界線交差のみが受入れ可能透明性モデルを一般に生成し、これらは異なる領域に関連付けられている。これらは、上側小領域３１５（ここでは低濃度の領域３１０と高濃度の領域３１２とが隣接している）の境界線交差３２１と、左側小領域３１４（ここでは低濃度の領域３１０と中間濃度の領域３１１とが隣接している）の境界線交差３２２と、右側小領域３１３（ここでは高濃度の領域３１２と中間濃度の領域３１１とが隣接している）の境界線交差３２３である。
【００９８】
図８は、上述の処理ステップ６３０で使用される複数組の３つの重なりグラフィックオブジェクトの重なり領域に対応する一組の透明性モデルを検出する処理方法８００を例示する。ステップ８１０において、次の領域が選択される。記憶された透明性モデルを持たないステップ６１０で処理のために選択された各領域は、ステップ８１０で順次選択される。ステップ８２０において、隣接透明性モデルが収集される。現在の領域に隣接する各領域の透明性モデルが存在すれば、一組の隣接透明性モデルはその透明性モデルを含んで形成される。隣接領域は、現在の領域に対して境界線データを使用して効率的に検出してもよい。
【００９９】
ステップ８３０において、この一組の隣接領域のモデルが、現在の領域における部分的な透明性を持つ３つのグラフィックオブジェクトの重なりとの整合性のためのチェックが行われる。整合性のためにこの一組をテストする一方法は以下の通りである。まず、一組のモデルが整合性のために一対ずつチェックされ、整合性のある任意のモデル対については、誤差関数値が最も高いモデルがこの組から除去される。整合性のあるモデルは類似の色と透明性パラメータとを有し、ステップ７４０及び７８０に上述した複数対の色及び透明性パラメータの整合性又は類似性をテストする方法を使用してもよい。次に、この組の透明性モデル数が３でなければ、これらのモデルは部分的な透明性を持つ３つの領域の重なりとは整合性がない。透明性モデル数が３ならば、これら３つの選択されたモデルの全ての取りうる順序が更にテストされる。以下の条件が全て満たされるようにモデルが指標１、２及び３を割り当てられた透明性モデルの順序が存在すれば、部分的な透明性を持つ３つの領域の重なりが検出される。
・モデル１及び２の上側色及び透明性パラメータが一致し、且つ
・モデル２及び３の下側色が一致し、且つ
・モデル３の上側色がモデル１の下側色と類似であり、且つ
・全３つのモデルの背景色が一致する。
【０１００】
決定ステップ８４０において、これらのモデルが一致するか（すなわち、３つのモデルが上記条件を満たすか）を判定するためのチェックが行われる。ステップ８４０が真（ＹＥＳ）を返すと、ステップ８５０に進み、３要素重なりモデルを記憶する。これにより、現在の領域との３要素重なりを表すように選択された３つのモデルを関連付ける。この領域に関連付けられた一組の３つの透明性モデルは、３つのグラフィックオブジェクトの重なりに対する透明性モデルを構成する。その後、ステップ８６０に進む。ステップ８４０が偽（ＮＯ）を返すと、これはモデルが上記条件を満たさないことを意味し、直接、ステップ８６０に進む。決定ステップ８６０において、処理すべき更なる領域が存在するかを判定するためのチェックが行われる。ステップ８６０が真（ＹＥＳ）を返すと、ステップ８１０に進む。ステップ８６０が偽（ＮＯ）を返すと、処理は終了する。
【０１０１】
図３に例示した例では、中央の小領域３１６は３つの小領域３１３、３１４及び３１５に隣接し、各々は単一の透明性モデルを有する。これらの透明性モデルの各々は同一の背景領域３１７を有し、このため同一の背景色を有する。左側及び上側小領域３１４及び３１５は、左側大領域３１０に基づき同一の上側色と透明性パラメータとを共有するモデルを有する。上側及び右側小領域３１５及び３１３は、右側の大領域３１２に基づき同一の下側色を共有するモデルを有する。また、領域３１４及び３１３は共に下側大領域３１１に基づいているため、左側小領域３１４の下側色は右側小領域３１３の上側色と一致する。左側小領域３１４からのモデル１、上側小領域３１５からのモデル２及び右側小領域３１３からのモデル３としてのこれらモデルの順序は、中央の小領域３１６における３要素重なりと一致するため、全３つのモデル１、２及び３が領域３１６に関連付けられる。
【０１０２】
本発明の別の実施形態では、単一の領域における４つ以上のグラフィックオブジェクトの重なりを検出するために、上述の方法８００と同様の処理方法が採用されてもよい。
【０１０３】
図９に、図６のステップ６４０で使用される一組の領域及び透明性モデルに応じてグラフィックオブジェクトの幾何形状モデル及び色モデルを構成する処理方法９００を例示する。処理はステップ９１０で開始する。ステップ９１０において、透明性モデルを有する次の領域が選択される。単一の透明性モデルを有する各領域はステップ９１０で選択される。領域の透明性モデルは２本の境界線を含み、一方は上側グラフィックオブジェクトに対応し、他方は下側グラフィックオブジェクトに対応する。次の２つのステップ９２０及び９３０では、図１０を参照して詳述する方法１０００に応じて境界生成を行う。ステップ９２０において、重なっているオブジェクトの境界が生成される。すなわち、上側グラフィックオブジェクトに対応する境界線が境界生成方法でまだ使用されていなければ、ステップ９２０でこの境界線と透明性モデルとに基づき新しい境界を生成する。ステップ９３０において、重ねられたオブジェクトの境界が生成される。すなわち、下側グラフィックオブジェクトに対応する境界線が境界生成方法でまだ使用されていなければ、ステップ９３０でこの境界線と透明性モデルとに基づき新しい境界を生成する。これらの構成済み境界は、新しいグラフィックオブジェクトが右側で検出され且つ順序付けられた一組の境界線からなるように作成される。この場合、境界が時計回りならば、この境界は構成済みグラフィックオブジェクトの外側境界となり、境界が反時計回りならば、この境界は内側境界となる。
【０１０４】
決定ステップ９４０において、単一の透明性モデルを有する更なる領域が存在するかを判定するためのチェックが行われる。ステップ９４０が真（ＹＥＳ）を返すと、ステップ９１０に戻る。ステップ９４０が偽（ＮＯ）を返すと、ステップ９５０に進む。ステップ９５０において、構成済み境界からの新しいグラフィックオブジェクト及び対応する階層化（階層化情報、色及び透明性パラメータ）が生成される。可能であれば、いずれかの構成済み内側境界が外側境界に関連付けられる。内側及び外側境界がその右側で共有領域を有する場合、関連付けが行われる。例えば図４において、領域４０２に関連付けられた２つの境界が生成される。これらの境界は共に正方形であり、大きい方の正方形は時計回りであり、小さい方は反時計回りであり、これらは関連付けられている。内側境界が外側境界に関連付けできない場合、この内側境界は棄却される。
【０１０５】
新しいグラフィックオブジェクトは、外側境界といずれかの対応内側境界とで定義される各構成済み外側境界に対して作成される。グラフィックオブジェクトの相対的な層は、透明性モデルを有する領域において重なる各オブジェクト対について、上側境界線を含むオブジェクトが下側境界線を含むオブジェクトよりも高い層に存在するようにする。これを達成する一方法では、上側境界線を有するオブジェクトから下側境界線を有するオブジェクトへの有向エッジを有する有向グラフにおけるノードとして全オブジェクトを配置する。このグラフは階層化における不整合性に対応するので、サイクルを含むべきではない。何れかのサイクルが検出された場合、このサイクル中の全オブジェクトが棄却される。次に、グラフのエッジに続くパスに含まれる最大数ノードにより別個の層数が与えられ、グラフにおける一組の階層化必要条件が満たされるように（例えば、グラフを繰り返し増加／減少することにより）、これらの層をノードに割り当てることができる。グラフィックオブジェクトの色Ｃ及び透明性パラメータαは、ステップ９２０又は９３０のいずれかの生成済み外側境界に対して返された値に応じて設定される。
【０１０６】
ステップ９６０において、一組のグラフィックオブジェクトがフィルタリングされる。このフィルタリングは、透明性モデルを有する各領域を順次チェックすることによりグラフィックオブジェクトは整合性があるかを確認するために行われる。透明性モデルの下側境界線を有する境界を含むグラフィックオブジェクトが生成された場合、同一の透明性モデルの上側境界線を有する境界を含むグラフィックオブジェクトも存在しなければならない。そのようなグラフィックオブジェクトが一つしか生成されていなければ（すなわち、下側境界線はあるが上側境界線はない又はその逆）、このグラフィックオブジェクトは棄却されなければならない。棄却するグラフィックオブジェクトがなくなるまでフィルタリング処理は繰り返され、残り全てのグラフィックオブジェクトが受入れられる。次に、オプションのステップ９７０において、ページ及び境界線の領域表現を更新してもよい。受入れられた一組の新しいグラフィックオブジェクトの生成で使用される全ての境界線は、これらの境界線がグラフィックオブジェクトに隣接するように更新され、境界線に以前隣接していた領域は廃棄される。状況によっては、境界線の一方側がいずれかのオブジェクトに写像できるように、境界線区間は一組の受入れ済みグラフィックオブジェクトで２回以上使用できる。この場合、境界線区間は一般に短く、写像はいずれかのオブジェクトに対して行うことができる。その後、処理は終了する。
【０１０７】
図１０は、図９のステップ９２０及び９３０で使用される新しいグラフィックオブジェクトの境界を生成する処理方法１０００を例示する。方法１０００には境界線と透明性モデルとが提供される。処理はステップ１０１０で開始する。ステップ１０１０では、メモリ１１０６に生成済み境界を記憶するデータ構造を初期化し、提供された境界線に対する現在の境界線と提供された透明性モデルで与えられた領域（すなわち、透明性モデルが生成された領域）に対する現在の領域とを設定する。現在の境界線は、現在の領域が境界線の右側に位置するように方向付けられる。すなわち現在の境界線は、現在の領域の境界に沿って方向付けられる。オブジェクトモデルも以下のデータを記憶する提供されたデータに応じて設定される。
・オブジェクト色チャンネル値Ｃ⁽ⁱ⁾obj
・オブジェクト透明性αobj
・グラフィックオブジェクトの背景色チャンネル値Ｃ⁽ⁱ⁾back
提供された境界線が下側境界線ならば、オブジェクトモデルは上側色に応じて設定されたオブジェクト色、背景色及びオブジェクト透明性と、背景色と、提供された透明性モデルの透明性とを有する。提供された境界線が上側境界線ならば、提供された境界線は提供された透明性モデルからの下側色及び背景色に対して設定されたオブジェクト色及び背景色と、オブジェクト透明性「０」とを有する。上側境界線がモデルの下側色に応じたモデル色を取る理由は、その境界線は現在の領域で上側境界線に隣接する上側オブジェクトを有するが、下側グラフィックオブジェクトの境界の一部を形成するからである。
【０１０８】
決定ステップ１０２０において、（生成された）境界が完成したかを判定するためのチェックが行われる。境界が閉じられる（その最初と最後の点が同一である）又は境界がいずれかの境界線を２回以上含むと、その境界は完成したと見なされる。生成された境界が完成すると（ＹＥＳ）、ステップ１０８０に進む。ステップ１０８０において、境界は受入れ可能であれば記憶される。ステップ１０８０については、より詳細に後述する。その後、処理は終了する。決定ステップが偽（ＮＯ）を返すと、ステップ１０３０に進む。決定ステップ１０３０において、現在の境界線が使用されたかを判定するためのチェックが行われる。このチェックにより、現在の境界線が境界生成で使用され、ステップ６１０で検出された透明性モデルで使用されたかを判定する。これらの条件の双方が満たされると（ＹＥＳ）、ステップ１０９０に進む。ステップ１０９０において、境界は棄却される。この後半の制御は、同一の境界の多重コピーが生成されるのを防止する。その後、処理は終了する。
【０１０９】
決定ステップ１０３０が偽（ＮＯ）を返すと、ステップ１０４０に進む。ステップ１０４０において、境界線は境界に追加される。ステップ１０５０において、現在の境界線が更新される。すなわち、現在の境界線は、現在の境界線の後の現在の領域の境界に沿って次の境界線に更新される。
【０１１０】
決定ステップ１０６０において、反対側の領域は整合性があるかを判定するためのチェックが行われる。すなわち、新しい現在の境界線の現在の領域とは反対側にある領域（反対側領域と呼ぶ）が検出され、オブジェクトモデルとの整合性がチェックされる（すなわち、反対側領域が現在のグラフィックオブジェクトの一部となるべきかをチェックする）。反対側領域が以前の処理で例えばテキストとして既に分類されていたならば、反対側領域を整合性がないと見なしてもよい。反対側領域が反対側領域に関連付けられた透明性モデルを持っていなければ、その色がオブジェクトモデルのオブジェクト色と同一であれば反対側領域は整合性があると見なされる。反対側領域が反対側領域に関連付けられた１つ以上の透明性モデルを持っていれば、反対側モデルと呼ばれる各モデルに対して順次整合性チェックが行われる。好適な整合性チェックの一つでは、以下の条件の何れかが満たされるかをテストする。
１．反対側モデルの下側色がオブジェクトモデルのオブジェクト色と一致する。
２．反対側モデルの上側色がオブジェクトモデルのオブジェクト色と一致し、オブジェクトモデルのオブジェクト透明性が０である。
３．反対側モデルの上側色及び透明性がオブジェクトモデルのオブジェクト色及びオブジェクト透明性と一致する。
【０１１１】
上記条件の何れかが満たされ、オブジェクトモデルの背景色がオブジェクトモデルの背景色と一致すれば、反対側領域はオブジェクトモデルと一致する。複数対の色及び透明性パラメータの整合性をテストする好適な方法はステップ７４０及び７８０で説明した。
【０１１２】
決定ステップ１０６０が反対側領域はオブジェクトモデルと一致することを示す真（ＹＥＳ）を返すと、ステップ１０７０に進む。ステップ１０７０において、現在の境界線と領域が更新される。すなわち、ステップ１０７０では現在の領域が反対側領域に更新され、反対側領域の境界上の現在の境界線が検出され、現在の境界線が境界に沿って次の境界線に更新される。その後、ステップ１０２０に戻る。決定ステップ１０６０が反対側領域はオブジェクトモデルと一致しないことを示す偽（ＮＯ）を返すと、直接、ステップ１０２０に進む。
【０１１３】
現在の境界が完成したとステップ１０２０で見なされると、ステップ１０８０に進む。ステップ１０８０では、境界が受入れ可能か（すなわち、閉じていて、自己交差がないか）をチェックし、もしそうであるなら色と透明性データと共に境界を記憶する。記憶された透明性データはオブジェクトモデルの透明性データである一方、記憶された色Ｃ⁽ⁱ⁾storeは、オブジェクトモデル透明性αobjを有するオブジェクトモデル背景色Ｃ⁽ⁱ⁾backの上に配置された時にオブジェクトモデルのオブジェクト色を生成する色である。透明性の式（１）によると、これは以下を意味する。
【０１１４】

【０１１５】
この式を書き換えることにより、記憶するための好適な色チャンネル推定値が得られる。
【０１１６】

【０１１７】
これは、記憶された色推定値がオブジェクト色と「１−オブジェクト透明性」で除算されたオブジェクト透明性により基準化された背景色との間の相違により与えられることを意味する。これにより、方法１０００の処理が完了する。
【０１１８】
図２に例示した例では、中央の小正方形２１３という１つの領域のみが、その領域に関連付けられた透明性モデルを有する。透明性モデルは、左側及び上側境界線２２３及び２２１をそれぞれ下側及び上側境界線として作成されていてもよい。境界は、透明性モデルの上側境界線（上側境界線２２１）により与えられる現在の境界線と、透明性モデルの下側色（すなわち、左側正方形領域２１１の色）及び透明性「０」で与えられる色を有するオブジェクトモデルとから開始して生成できる。方法１０００の処理によりこの境界線は境界に記憶され、中央正方形領域２１３の次の境界線、すなわち右側境界線２２７に繰り返し進む。その後、反対側領域は右側領域２１４になり、左側及び右側正方形は同一の色を有しているため、領域２１４はオブジェクトモデルと一致する色を持つ。その後、現在の領域は右側領域に更新され、現在の境界線はこの領域の次の境界線、すなわち右側正方形２１４の上／右／底側境界線２２６に更新される。この境界は閉じていないので、現在の境界線がその境界に追加され、現在の領域の次の境界線、すなわち右側正方形の左側境界線２２７に更新される。この時点で、反対側領域は領域２１３となり、再度オブジェクトモデルと一致するため、この領域は中央正方形に更新され、現在の境界線はこの領域の境界に沿って底側境界線２２５に繰り返し進む。この現在の境界線は境界に追加され、以降の処理により左側領域２１１の底／左／上側境界線２２２が追加され、境界が完成する。同様に、上側オブジェクトは、中央正方形２１３の左側境界線２２３であり上側正方形２２８の左／上／右側境界線を含む透明性モデルの下側境界線と、中央正方形２１３の右側境界線２２７と、底側正方形２１２の右／底／左側境界線２２４とから開始して生成できる。この境界生成のためのオブジェクトモデルは、中央正方形領域の透明性モデルからの上側色と背景色と透明性モデルとにより最初に与えられる。
【０１１９】
図３に例示する例では、１つの透明性モデルを有する３つの小領域３１３、３１４及び３１５と、３要素重なりであると検出され且つこれら３つの全モデルを有する１つの中央領域３１６とがある。３つの時計回りに構成された円形境界が形成され、各々は透明性モデルのない１つの大領域からの境界線と、単一の透明性モデルを有する２つの領域と、中央領域とを有する。例えば、中間濃度の３０２の幾何形状モデルは、左側小領域３１４の上側境界線と、中央の小領域３１６の上側境界線と、右側小領域３１３の上部境界線と、最後に底側大領域３１１の底側境界線とから構成される。このオブジェクトの色及び透明性は、右側小領域３１３の透明性モデルの上側色及び透明性に基づいている。幾何形状モデルは低濃度の円と高濃度の円とに対しても作成されるが、構成されたグラフィックオブジェクトは背景上に存在するが他のオブジェクトと部分的に重ならないので、高濃度の円３０３のオブジェクトモデルは透明性「０」を有する。
【０１２０】
［他の実施形態］
オブジェクトの透明性をビットマップ画像から判定することを含む他の実施形態を以下に説明するが、少なくとも１本の線がオブジェクトの周囲に存在するというように複雑になる。線を除去することにより、上述の実施形態の技術を使用してオブジェクトの色及び透明性を判定できる。本実施形態では、１つ以上のオブジェクトが線スタイルを有し、部分的に透明な塗りつぶし部と共にグラフィックオブジェクトが重なる場合に対処する。線スタイルに対応する領域は、グラフィックオブジェクトの塗りつぶし部に対応する領域の周囲で検出される。これらの線領域は、上述の方法ではグラフィックオブジェクトの重なりが検出できないように塗りつぶし領域の隣接性を変更できる。この他の実施形態では、塗りつぶし領域の隣接性を回復して重なりが検出できるように一組の領域を変更することにより線スタイルを処理する。
【０１２１】
図１３は、１つのオブジェクトがベタ塗りの線スタイルを有する透明性を持って重なる一組のグラフィックオブジェクトを例示する。図１３ａのグラフィックオブジェクト１３１０は、部分的な透明性を有する縦長矩形である。グラフィックオブジェクト１３１１は、透明性「０」の横長矩形（長さ方向が矩形１３１０と直交する）である。グラフィックオブジェクト１３１２は、透明性「０」の大きい正方形である。横長矩形１３１１は、縦縞領域１３１３に示される塗りつぶし領域を囲む斜め縞領域１３１４が示すベタ塗りの線スタイルを有する。図１３ｂは、垂直矩形１３１０が水平矩形１３１１に重なり、水平矩形１３１１が正方形１３１２に重なるようにオブジェクトを階層化した結果を例示する。この正方形は、２つの矩形の重なりに対する背景を効果的に形成する。１０個の領域１３２０〜１３２９は、図１３ｂに示されるような合成オブジェクトから形成される。図１３ｃは、１０個の領域１３２０〜１３２９を別々に例示する。
【０１２２】
領域１３２０は正方形１３１２のみに被覆された領域である。領域１３２５及び１３２９は、水平矩形塗りつぶし部１３１３と正方形１３１２とに被覆された領域を表す。水平矩形は透明性「０」なので、正方形１３１２は完全に隠蔽され、これらの領域の色は水平矩形１３１３の塗りつぶし部と同一である。同様に、領域１３２１及び１３２４は、水平領域の線１３１４と正方形１３１２の双方に被覆された領域を表す。水平矩形は透明性「０」なので、正方形１３１２は完全に隠蔽され、これらの領域の色は矩形線１３１４と同一である。
【０１２３】
領域１３２２及び１３２７は、垂直矩形１３１０と正方形１３１２の双方に被覆された領域を表す。垂直矩形１３１０は部分的な透明性を有するので、領域１３２２及び１３２７の色は、正方形１３１２及び矩形１３１０の色による透明性モデルに応じて決定できる。式（１）で定義されるモデルについては、垂直矩形の色チャンネルＣ⁽ⁱ⁾upperと、背景正方形の色チャンネルＣ⁽ⁱ⁾lowerと、垂直矩形の透明性パラメータαupperとを減算することにより算出される。最後に、領域１３２３、１３２６及び１３２８は、全３つのオブジェクトに被覆された領域を表す。水平矩形１３１１は不透明で、領域１３２３、１３２６及び１３２８で正方形１３１２を完全に隠蔽しているので、これらの領域の色は正方形の色には依存しない。領域１３２３、１３２６及び１３２８の色は、２つの細長い矩形１３１０及び１３１１の色による透明性モデルに応じて決定できる。領域１３２３及び１３２８は、水平矩形１３１４のベタ塗りの線を有する縦長矩形１３１０の重なりに対応する。領域１３２６は、水平矩形１３１３の塗りつぶし部を有する重なりに対応する。
【０１２４】
図１４は、テンプレート形状（矩形、三角形、星、円、楕円、丸角の矩形）に定義される種々のオブジェクトと手書きで定義された他のオブジェクト（自由形式オブジェクトと呼ぶ）とを含む線や透明塗りつぶし部を有する重なりグラフィックオブジェクトの多数の異なる幾何形状を例示する。各オブジェクトは直線エッジと曲線エッジの混合から構成される。幾何形状のほとんどは２つの重なりオブジェクトを示すが、１つの幾何形状は３つの重なりオブジェクトを示す。全てのオブジェクトは部分的な透明性を有する塗りつぶし部を有し、線が部分的な透明性を有する横長矩形の場合（１４４０）を除き、いくつかのオブジェクトは、ほとんどの場合不透明（透明性「０」）である線を有する。背景領域は本図面では明示されない。
【０１２５】
重なりグラフィックオブジェクト１４１０は２つの重なり矩形を具備し、各矩形は不透明な線スタイルを有し、上側矩形（横長）は部分的に透明な塗りつぶし部を有する。重なりグラフィックオブジェクト１４２０は、線スタイルと塗りつぶし部とを有する三角形に重なっている部分的に透明な星を具備する。重なりグラフィックオブジェクト１４３０は３つの円を具備し、各円は不透明な線スタイルを有し、上側２つの円は部分的に透明な塗りつぶし部を有する。重なりグラフィックオブジェクト１４４０は２つの重なり矩形を具備し、各矩形は線を有し、上側矩形は部分的に透明な線スタイルと塗りつぶしスタイルとを有する。重なりグラフィックオブジェクト１４５０は、線と塗りつぶし部とを有する第２の自由形式オブジェクトに重なっている部分的に透明な塗りつぶし部を有する自由形式オブジェクトを具備する。重なりグラフィックオブジェクト１４６０は、楕円に重なっている線と部分的に透明な塗りつぶし部とを有する丸角の矩形を具備する。
【０１２６】
表１は、図１４の下側のキーに示すように、図１４の色領域の定義を含む。
【０１２７】

【０１２８】
図１４のキーは、表１に応じて各領域色の構成を定義する陰影方式を解釈するために使用できる。オブジェクトを有する３つの層が存在すると仮定する。層１は最上位層であり、その下が層２、さらにその下が層３である。それにもかかわらず、異なる陰影スタイルを有する領域は同一の色を有してもよい。例えば、１４１０の２つの重なり矩形の線の線色は同色でもよい。この場合、広い斜め縞（１４８８及び１４９０）の領域を表す単一の連結成分が存在してもよい。
【０１２９】
部分的な透明性を持ったグラフィックオブジェクトの重なりに対して取り得る他の幾何形状は、グラフィックオブジェクトの図４に例示した。これらのオブジェクトは線スタイルを持っていなかった。一部又は全てのオブジェクトが線スタイルを有する類似の重なりオブジェクトの幾何形状は、本発明の実施形態を用いて処理できる。
【０１３０】
図１５ａは、オブジェクト表現をビットマップ画像から生成する方法１５００を例示する高レベルのフローチャートである。ビットマップ画像は文書の走査版でもよく、オブジェクト表現は電子文書（例えば、編集可能な）でもよい。方法１５００は図１の処理モジュール１４０において実現されてもよく、コンピュータにより実現することもできる。処理はステップ１５１０で開始する。ステップ１５１０において、一組の領域がプロセッサ１１０５を使用してビットマップ画像から決定（選択）され、この一組の領域はビットマップ画像の背景領域と塗りつぶし領域と線領域とを含む。決定ステップ１５１０の詳細については以下の図１５ｂを参照してより詳細に説明する。ステップ１５２０において、塗りつぶし領域の隣接性データは、線領域で分割された塗りつぶし領域を配置し、配置された領域を隣接させることによりプロセッサ１１０５を使用して生成される。
【０１３１】
ステップ１５３０において、第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータが、一組の塗りつぶし領域の塗りつぶし色及び隣接性データに応じてプロセッサ１１０５を使用して推定される。推定された色及び部分的な透明性は、色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重なりの領域の色を定義する透明性合成モデルと一致する。第１及び第２のグラフィックオブジェクトの幾何形状モデルは、一組の領域と第１のグラフィックオブジェクトの推定された色及び透明性パラメータとからプロセッサ１１０５を使用して構成される。ステップ１５４０において、単一の線色は第２のグラフィックオブジェクトの輪郭線に対してプロセッサ１１０５を使用して決定される。これは、１つの線領域の少なくとも線色に基づいて行われてもよい。ステップ１５４５において、電子文書を形成するために、推定された色及び部分的な透明性パラメータを有する第１の独立グラフィックオブジェクトと、決定された単一の線色を有する第２の独立グラフィックオブジェクトとが記憶される。その後、処理は終了する。
【０１３２】
図１５ｂに、オブジェクト表現（例えば、図１のファイル１５０）を生成するためにビットマップ画像（例えば、図１の走査済文書１３０）を処理する方法１５５０をより詳細に例示する。方法１５５０は図１５ａのステップ１５１０をより詳細に示す。ステップ１５５５、１５６０及びス１５６５がステップ１５１０を実現する。方法１５５０はステップ１５５５で開始する。ステップ１５５５において、ビットマップ画像は１つ以上の連結成分に区分される。メモリ１１０６に記憶されたビットマップ画像に対してプロセッサ１１０５により低レベルの画像区分が行われ、画像は色に応じて連結成分（ＣＣ）に分割される。ビットマップ画像の連結成分の各々はメモリ１１０６に記憶される。ステップ１５６０において、プロセッサ１１０５は連結成分を分類し、種々の文書コンテンツの種類を識別する。これは、ビットマップ画像の連結成分に対して高レベルの文書レイアウト解析を実行することにより行われる。連結成分はそれらの矩形バウンディングボックスに関して処理されてもよく、処理中にマージ又はグループ化された連結成分でもよい。コンテンツの種類には、テキスト、写真、表、線画及びグラフィックという分類がある。これらのコンテンツの種類の各々は画素データ（すなわち、連結成分）に対応する。
【０１３３】
高レベルの文書解析の後、ステップ１５６５において、プロセッサ１１０５は定義済み幾何形状を有する領域を生成する。これは連結成分を解析することにより行われる。他の連結成分は図形コンテンツを含む確率が低いと見なされるため、線画及び／又はグラフィック領域として分類された連結成分のみがステップ１５６５で処理されるのが好ましい。各領域は、単一の外側境界と、この単一の外側輪郭及び連結成分の一組の０以上の内側輪郭に対応する０以上の内側境界とによって定義できる。
【０１３４】
上述のように、境界は境界線区間に関して表されてもよく、境界線は各辺の長さ方向に隣接する独自の領域を有する境界の区間を記述するために使用される。各境界線は２つの境界に含まれ、多角形表現により記述されてもよい。本実施形態において、境界を定義する複数の境界線は一緒にリンクされ、境界は境界線間のリンクを辿ることにより横断されてもよい。各境界線は、４つのリンクされた境界線を有し、いずれかの側の２つのオブジェクトに対する次の境界線及び先行境界線となる。リンクされた境界線のいくつかは同一でもよく、特に、背景のみに隣接するオブジェクトで生じるように全境界を表す単一の境界線はそれ自身に４回連結される。
【０１３５】
２色のみの単純な領域構成は、１つのオブジェクトの外側境界と第２のオブジェクトの内側境界とを定義する閉境界線を有する。一方、３色以上のより複雑な領域構成において、複数の境界線は、リンクされて境界を構成する開区間でもよい。多角形表現が自己又は相互交差のない効率的な表現となるように、一組の領域を表す境界線に対して多角形表現を生成する技術がある。境界線に沿った点は好適なデータ構造でメモリ１１０６に記憶され、境界はこれらのデータ構造によって定義される。境界上の連続する点に対して一貫性のある順序付け方式を使用するのは有用である。上述の実施形態において、順方向に横断した場合、外側境界は時計回りのループを形成し、内側境界は反時計回りのループを形成する。この方式では、いずれの境界の周囲であっても順方向に前進すると、領域はその境界の右側に位置する。
【０１３６】
図１３ｂ及び図１３ｃは、正方形オブジェクト１３１２に２つの矩形オブジェクト１３１０及び１３１１が重ねられた場合に形成される１０個の領域を例示する。重なり領域のビットマップ画像が処理されたならば、１０個の連結成分が領域に対応して検出されるはずである。領域１３２０は、正方形オブジェクトにいずれの矩形も重ねられないと検出された連結成分に対応する。この連結成分の生成領域は、単一の境界線からなる外側境界と、４本の境界線からなる単一の内側境界線とを有し、これらの境界線は領域１３２０がそれぞれ領域１３２１、１３２２、１３２４及び１３２７に隣接する場所に形成される。領域１３２２は、正方形１３１２に垂直矩形１３１０のみが重ねられた場所に形成された連結成分に対応する。この連結成分の生成領域は２本の境界線からなる外側境界を有し、これらの境界線は領域１３２２が領域１３２０及び１３２３に隣接する場所に形成される。これらの内の第１の境界線が上述の領域１３２０の内側境界を定義するのにも使用される。領域１３２１及び１３２３〜１３２９に対応する連結成分の外側境界も同様に検出できる。これらはいずれも内側境界がない。
【０１３７】
図１５のステップ１５７０において、線及び線領域が検出される。これは、線と関連領域とを検出するためにオブジェクトの境界の多角形表現を処理する既存の技術を使用して達成されてもよい。線は、骨格又は中心軸及びその辺の境界線表現によって定義される。その処理では、例えば接触線や重なり線を切断するか又は線オブジェクトを連結形状から分割することにより一組の領域を修正してもよい。一組の線領域が生成され、他の領域は塗りつぶし領域と呼ばれる。
【０１３８】
図２４は、ステップ１５７０で検出される多数の取りうる線の幾何形状を例示する。７本の線があり、各々が太線で表される骨格又は中心軸を有する。骨格の内３つは閉じている。すなわち、骨格の２つの端部が連結されている（２４０５、２４２０及び２４４０）が、他の４つは開いていて（２４５０、２４６０、２４７０及び２４８０）、骨格の２つの端部が離れている。縞状領域は線領域を規定する。これらの線の内４本は単一の線領域（中心軸２４０５、２４２０、２４５０及び２４６０を有する線）からなるが、他の３本は２つの線領域（２４４０、２４７０及び２４８０）からなる。線は、画像の雑音、区分化アーティファクト又は他の幾何学的オブジェクトの重なりの結果として２つ以上の領域により表現されてもよい。領域は内側境界線を有していてもよく、例えば閉じた骨格２４０５に対応する領域２４０６は外側境界２４１０と内側境界２４１５とを有する。
【０１３９】
図１５ｂのステップ１５７０は、別の実施形態ではステップ１５６５に先行してオプションで行われてもよい。例えば線検出は、直接、画素を処理する既存の技術を使用して（すなわち、細線化や疎画素ベクトル化等の形態素演算を使用して）行われてもよい。検出された線は破線でもよいが、この場合、線領域は長さ方向に延びる単一の骨格を有する個別のダッシュに対応する多数の閉境界に対応してもよい。線は画像内の線形状を認識することにより検出されてもよい。骨格は局所的に、線の中心軸の低品位の表現でもよい。
【０１４０】
ステップ１５７０では、現在の組の領域に基づき図形コンテンツをオプションで決定してもよい。図形コンテンツは、テンプレート形状、線オブジェクト、矢印、コネクタ及び他のオブジェクトを含んでもよい。本処理は、線及び形状検出、隠蔽形状検出、線リンク解析及びコネクタ解析のための既知の技術を採用してもよい。
【０１４１】
図１５のステップ１５７５において、ステップ１５７０で生成された線骨格と線領域と塗りつぶし領域とに基づき、線領域のない塗りつぶし領域の幾何形状モデル及び隣接性情報を構成し、領域を表現する。この修正された一組の領域は、以前は線領域であった領域を被覆するように延伸した塗りつぶし領域のみからなる。本ステップでは、修正された塗りつぶし領域間の隣接性に関する情報も生成する。これは、境界線と境界によってモデルを定義することにより達成される。ステップ１５７５は図１５ａのサブステップ１５２０を含み、図１７を参照してより詳細に後述する。
【０１４２】
次にステップ１５８０において、部分的な透明性を有する重なりグラフィックオブジェクトが検出され、これらの重なりグラフィックオブジェクトを記述する幾何形状モデルが図２７を参照してより詳細に後述する方法２７００に応じて構成される。構成された幾何形状モデルは、関連線スタイル（幅、色及びオプションとしてダッシュスタイル）と塗りつぶし色と部分的な透明性とを有する。これには、図１５ａの最終的なサブステップ１５３０、１５４０及び１５４５が含まれる。少なくとも１つのオブジェクトの幾何形状モデルはこの段階で出力されてもよく、例えばこの段階では、グラフィックオブジェクトは自由形状であり特定の図形コンテンツの種類として分類できない。したがって、以降のステップ１５８５及び１５９０はオプションのステップとして示される。
【０１４３】
方法１５５０はオプションのステップ１５８５（破線で示される）に進む。ステップ１５８５では、現在の組の領域に基づいて図形コンテンツが決定される。図形コンテンツは、テンプレート形状、線オブジェクト、矢印、コネクタ及び他のオブジェクトを含んでもよい。本処理は、線及び形状検出、隠蔽形状検出、線リンク解析及びコネクタ解析のための既知の技術を採用してもよい。
【０１４４】
ステップ１５９０において、プロセッサ１１０５は分類されたグラフィックオブジェクトをオブジェクト表現としてオプションで（再度、破線で示す）出力する。この出力は構造化テキスト／グラフィック編集アプリケーションでの閲覧及び編集に好適な形式でもよい。その後、方法１５５０の処理は終了する。
【０１４５】
図１７は、一組の修正済み塗りつぶし領域とそれに対応する隣接性情報とを構成する図１５ｂのステップ１５７５を行う方法１７００を例示する。これは、線領域を表現から除去するためにそれらの線領域に隣接する領域の境界線を再連結することにより行われる。図１７に示す処理では、単一の外側境界と多数（一般に０か１）の内側境界とにより定義される各検出線領域を解析する。単一の線領域に関連付けられた一組の線領域は連続して処理される。
【０１４６】
決定ステップ１７０５において、次の線領域を決定するためのチェックが行われる。すなわち、ステップ１７０５では次の線領域を選択する。そのような線領域があれば（Ｙｅｓ）、処理は１７１０に進み、そうでなければ（Ｎｏ）、ステップ１７５５に進む。ステップ１７１０において、選択された線領域の境界に対する左右の始点と終点が決定される。ステップ１７１０では、境界のどの区間が線のどちら側（左か右）を表すのかが検出される。線骨格に対する始点と終点も検出され、これにより線骨格のどの区間がこの境界に関連するかが決定される。ステップ１７１０については、図１８を参照して更に詳細に後述する。決定ステップ１７１５では、始点と終点がステップ１７１５で検出されたかをチェックする。検出されたならば（Ｙｅｓ）、ステップ１７２０に進み、始点も終点も検出されなかったならば（Ｎｏ）、ステップ１７０５に戻る。
【０１４７】
ステップ１７２０において、入力境界線が検出（識別）される。これらはその後、線領域まで延長される境界線である。ステップ１７２０については、図１９を参照して更に詳細に説明する。
【０１４８】
ステップ１７３０において、入力境界線は分解される。これにより、線の骨格上の投影位置が固定され、境界線が反対側で整列される。ステップ１７３０については、図２０を参照して更に詳細に説明する。
【０１４９】
ステップ１７４０において、これらの境界線は線の骨格に沿って連結される。新しい一組の境界線が作成され、ステップ１７１０で識別された骨格の始点と終点との中間の骨格に続く。１７２０からの入力境界線は延長されて、これらの新しい境界線に接触する。ステップ１７４０の結果として、線領域の全領域は、境界線が線領域まで延長された修正済み隣接領域により被覆される。ステップ１７４０については、図２５を参照して更に詳細に説明する。
【０１５０】
ステップ１７５０において、修正済み塗りつぶし領域の新しい幾何形状が決定される。境界線を再連結することにより、別個の境界線をマージすること又は新しい境界を作成することができる。この新しい一組の境界は、修正済み領域の幾何形状を定義するために判定する必要がある。ステップ１７５０については、図２６を参照して更に詳細に説明する。
【０１５１】
ステップ１７５０の後、ステップ１７０５に戻る。全ての線領域が処理されると（ステップ１７０５でＮｏが返されると）、ステップ１７５５で修正済み領域を形成する。これは、ステップ１７５０で修正された境界の各々を順次チェックすることにより行うことができる。本実施形態では、外側境界が時計回りである一方、内側境界は反時計回りである。各外側境界は新しい領域の外側を定義し、各内側境界はその外側境界を含む（面積が）最小のものとして同一の領域に関連付けられる。各新しい境界はオリジナル表現の領域に関連付けられるが、その新しい境界は更新されて新しい修正済み領域に関連付けられ、その境界の全ての境界線も更新される。新しい領域の色及び他の特性は、外側境界が以前に関連付けられた領域に基づいて設定される。
【０１５２】
ステップ１７５５の後、ステップ１７６０に進み、類似の色領域をマージする。各領域の各境界上の境界線の各々が検討される。いずれかの境界線の隣接領域が同一又は実質的に類似の色ならば、２つの領域はマージされる。すると、一方の領域がマージされた領域とみなされ、他方の領域は除去される。これは、まず除去された領域の全ての境界を他方の領域に割り当てることにより行われる。それにより、縮退した多数の境界線が作成され、これらの境界線は両側に同一の領域を有するようになる。これらの境界線は、隣接境界線を再連結することにより除去され、これらの隣接境界線は新しい基本境界線のリストに追加される。マージにより領域の幾何形状が変化し、多数の新しい（内側）境界が作成されてもよい。新しい幾何形状は、図２６を参照してより詳細に説明するステップ１７５０で用いられるのと同じ処理を使用して決定される。ステップ１７６０の後、処理は終了する。
【０１５３】
図１８は、図１７のステップ１７１０で行うことができる、現在の線領域に対する境界線の始点及び終点を決定（検出）する方法１８００を例示する。５つの例があり、それぞれ別々に処理する。処理はステップ１８１０で開始する。決定ステップ１８１０において、例が選択される。すなわち、線領域の幾何形状が判定される。ステップ１８１０では、骨格が開いているか又は閉じているか、且つ境界は外側境界であるか又は内側境界であるかが、境界数に基づき以下の例の中から選択される。一実施形態において、境界の始点と終点に関する情報は、線検出処理中に生成されてもよく、この場合、ステップ１８１０はオプションであってもよい。ステップ１８２０、１８３０、１８４０、１８５０及び１８６０は並列に構成され、ステップ１８１０で選択され、ステップ１８２０、１８３０、１８４０、１８５０及び１８６０の１つが実行された後、処理は終了する。
【０１５４】
ステップ１８２０では、単一の内側境界と閉じた骨格とを有する線領域の例（「閉、単一の内側」）を処理する。そのような領域の例は、図２４の２４０６である。この線領域は閉じた骨格２４０５を有し、単一の外側境界２４１０と単一の内側境界２４１５とを有する。線の骨格は時計回りであるという規定に沿って、その線の左側が全外側境界となり、その線の右側が全内側境界となる。この場合、その線骨格の始点は任意に選択してもよい。線骨格の始点に対して内側及び外側境界上の最も近い点は、それぞれ左側及び右側の境界の始点として使用される。骨格及び境界の終点は、骨格及び境界の始点と同一になるように設定され、これにより全骨格と双方の全境界が考慮されたことを保証される。
【０１５５】
ステップ１８３０では、開いていて且つ内側境界のない単一の外側境界を有する線に対する線領域の例（「開、内側無し」）を処理する。開いた線の例は２４５０及び２４６０に見られ、各々が別個の骨格の始点と終点を有する図２４の骨格２４７０及び２４８０に関連付けられた複数対の線領域でも見られる。骨格２４７０及び２４８０に対応する線は、別々に処理される２つの線領域からなる。ステップ１８３０では、まず線骨格の最初の点が当該境界の上又は内側に存在するかを判定する。最初の点が境界の上又は内側に存在すれば、その骨格の始点は最初の点となり、左側境界の始点は境界上で骨格の最初の点に最も近い点となる。例えば、線骨格２４５０の始点２４５１は線領域の境界２４５３の上にある。点２４５１は骨格の始点且つ左側境界の始点である。線骨格２４６０の始点２４６１は線領域の境界２４６５の内側にある。この場合、点２４６１は骨格の始点となる一方、境界上の最も近い点２４６２は左側境界の始点となる。骨格の始点が境界の内側にない場合、境界と線骨格との間の全ての交点が識別される。交点がない場合、骨格はどの箇所でも線領域に接触又は重ならず、骨格又は境界の始点又は終点は検出されず、ステップ１８３０は完了する。交点が検出されると、線骨格に沿って距離によりソートされる。ソートされた交点の内の最初のものは、骨格の始点及び左側境界の始点として採用される。
【０１５６】
同様に、線骨格の最後の点が境界の上又は内側に存在するかを判定する。最後の点が境界の上又は内側に存在すれば、その骨格の終点は最後の点となり、右側境界の始点は境界上で骨格の最後の点に最も近い点となる。これは、例えば線２４５０上の点２４５２の場合である。さもなければ、上述のように、全ての交点が検出されて骨格位置によりソートされ、最後の交点が骨格の終点及び右側境界線の始点の双方になる。例えば線２４６０上で、点２４６４で骨格と境界との間に交点が１つある。この点は骨格の終点且つ右側境界の始点である。
【０１５７】
左側境界の終点は右側境界の始点と等しく、右側境界の終点は左側境界の始点と等しい。これにより全境界が考慮されたことを保証する。
【０１５８】
ステップ１８４０では、多数の線領域からなる閉じた検出済み線からの内側境界のない線領域の例（「閉、線内に多数の線領域」）を処理する。多数の線領域からなる閉じた線からの線領域の例は、図２４の２４４０である。この場合、当該領域の外側境界と線骨格との間の全ての交点が検出される。それにより、当該領域の外側にある線骨格のいくつかの区間が識別される。そのような区間が検出されなければ、始点も終点も生成されない。さもなければ、そのような区間の内の最長のものが識別される。この区間の始まりは骨格の終点となり、この区間の終わりは骨格の始点となる。左側境界の始点及び右側境界の終点は共に骨格の始点と等しくなるように設定され、右側領域の始点及び左側境界の終点は共に骨格の終点と等しく設定される。例えば、図２４の線２４４０については、上側境界２４４１を処理する場合、点２４４５で開始し、点２４４３で終了するこの境界の外側の線の一区間が識別される。点２４４３は骨格の始点、左側境界の始点及び右側境界の終点となる一方、点２４４５は骨格の終点、右側境界の始点及び左側境界の終点となる。下側境界２４４２を処理する場合、点２４４４で開始し、点２４４６で終了するこの境界の外側の線の一区間が識別される。点２４４６は骨格の始点、左側境界の始点及び右側境界の終点となる一方、点２４４４は骨格の終点、左側境界の終点及び右側境界の始点となる。
【０１５９】
ステップ１８５０では、単一の線領域が存在する閉じた検出済み線からの線領域の例を処理し、この線領域には内側境界がない（「閉、線内に単一の線領域、内側無し」）。単一の線領域を有する閉じた線の線領域の例は図２４の２４２５である。例１８４０のように、骨格と境界との間の全ての交点が検出され、これにより、境界の外側にある骨格のいくつかの区間が識別される。これらの区間の各々について、境界上の点ともなる始点及び終点が検討される。両方向の境界に沿った距離が検出され、これらの２つの距離の内の最小のものが検討される。そのような最小の境界距離を有する区間が選択される。これにより、境界が他の方向に向きを変える線骨格の一部が識別され、骨格がオブジェクトの境界を少しだけ離れる場所は無視する。例１８４０のように、骨格の始点及び終点はそれぞれ境界の区間の終点及び始点となり、左側及び右側境界の始点及び終点も例１８４０のように設定される。線の例２４２０上では、点２４３０及び２４３５は骨格及び境界の始点及び終点として識別される。
【０１６０】
ステップ１８６０では、その他全ての例を処理する（「その他」）。これは、多数の内側境界を有する閉じた線でもよく、１つ以上の内側境界線を有する開いた線領域でもよい。そのような例は稀である。始点も終点も検出されず、線領域は以降の処理で処理されない。
【０１６１】
図２１の線領域例Ｌ１は、以下の説明を支援する作業例として用いられる。図２１において、線Ｌ１は境界線Ｂ１、Ｂ２、Ｂ３、Ｂ４及びＢ５からなる境界を有する中央の矩形線領域である。破線Ｓ１はＬ１の骨格を示し、骨格の始まりは底部にある。左側境界の始点及び右側境界の終点は境界線Ｂ１上の骨格の始まりにある一方、左側境界の終点及び右側境界の始点は境界線Ｂ４上の骨格の終わりにある。この線図は他の境界線Ｂ６、Ｂ７、Ｂ８、Ｂ９、Ｂ１０、Ｂ１１及びＢ１２も示し、これら全ては線Ｌ１上の境界線に隣接する。領域Ｒ１、Ｒ２、Ｒ３、Ｒ４及びＲ５も示す。例えば、境界線Ｂ１は線領域Ｌ１を領域Ｒ１から分割すると見なすことができる一方、境界線Ｂ８は領域Ｒ３を領域Ｒ４から分割する。
【０１６２】
図１９は、図１７のステップ１７２０で実現可能な線領域に対する入力境界線を検出する方法１９００を示す。ここで説明する処理は２回行われ、最初は選択された線領域の境界の左側区間に対して行われ、次に境界の右側区間に対して行われる。便宜上、左側境界に関して処理を以下に説明する。
【０１６３】
方法１９００はステップ１９１０で開始する。ステップ１９１０において、次の境界線対が検出される（取得される）。この場合の一対は、線領域の境界を辿る際に連続する境界の２つの境界線である。最初の対は、左側境界の始点を含む境界線と時計回り方向の次の境界線とからなる。対を辿ることにより、各対が先行対と共通に１本の境界線を有するように１本の境界線を時計回りに移動する。図２１の例では、第１の境界線対はＢ１とＢ２であり、その後Ｂ２とＢ３、更にＢ３とＢ４となる。
【０１６４】
決定ステップ１９２０において、境界線対をチェックし、境界線間に１本の境界線が存在するかを判定する。すなわち、現在の境界線対の中間の境界線が識別される。中間の境界線とは、現在の境界線対間の接続点と共通の終点を有する境界線である。そのような中間境界線が１本だけ存在すれば（Ｙｅｓ）、ステップ１９４０に進み、そうでなければ（Ｎｏ）、ステップ１９３０に進む。例えば図２１において、境界線Ｂ１とＢ２との間には１本の境界線Ｂ６のみが存在する。２本以上の中間境界線が存在すれば（Ｎｏ）、ステップ１９３０に進む。例えば、境界線Ｂ３とＢ４との間には２本の境界線Ｂ８及びＢ９が存在する。また、境界線Ｂ５とＢ１との間には２本の境界線Ｂ１１及びＢ１２が存在する。
【０１６５】
決定ステップ１９３０において、同一の領域が現在の境界線対の双方からの線の反対側に存在するかを判定するためのチェックが行われる。例えば、境界線Ｂ３及びＢ４は共に領域Ｒ３に隣接する一方、境界線Ｂ５及びＢ１は２つの異なる領域Ｒ１及びＲ２に隣接する。領域が同一であれば（Ｙｅｓ）、ステップ１９５０に進み、そうでなければ（Ｎｏ）、ステップ１９６０に進む。
【０１６６】
ステップ１９４０において、識別された境界線は入力境界線として設定（リストアップ）される。この境界線はその後、線骨格と接触するように線領域の下で延長される。これは、入力境界線と線との間の接続点に最も近い骨格上の点を検出することにより行われてもよく、境界線が示している方向に沿って境界線が線と接触する場所に境界線を延長することにより行われてもよい。例えば図２１の例におけるこの結果は図２２に示される。ここでは、境界線Ｂ６、Ｂ７及びＢ１０が線骨格と接触するように延長されている。境界線Ｂ６はこの境界線が示している方向に延長されていると見なすことができる一方、Ｂ７及びＢ１０いずれかの方法を使用して延長されてもよい。処理はステップ１９７０に進む。
【０１６７】
ステップ１９５０において、いずれの線とも隣接しないように境界線は再リンクされ、同様に、線上の境界線は一緒にリンクされる。例えば、境界線Ｂ８とＢ９とは一緒にリンクされる。この時、領域Ｒ３は境界線Ｂ８から境界線Ｂ３ではなく境界線Ｂ９に継続する境界を有する。また、境界線Ｂ３とＢ４とはリンクされ、領域Ｒ３の境界は境界線Ｂ４から境界線Ｂ９ではなく境界線Ｂ３に継続する。この場合、入力境界線はリストに追加されない。
【０１６８】
このように境界線を再リンクする場合、領域のトポロジを修正してもよい。再リンクにより、領域の２つの境界がマージされてもよく、境界がそれ自身とマージされ、その結果、新しい境界が作成されてもよい。領域のトポロジに影響する更なる処理において他の多数の変更が行われてもよく、これはステップ１７５０で後から分解される。しかし、処理１７５０の処理を支援するために、新しい潜在的な境界の場所を追跡することは有用である。それにより、２本の境界線が記憶され、ステップ１７５０で後から使用される。第１の記憶済み境界線は、２本の以前に隣接していた境界線の一方であり、図２１の例ではＢ８又はＢ９である。線の境界がステップ１７５０の前に廃棄されているため、第２の記憶済み境界線は、これらの境界線の一方として以前同一の境界上に存在したが線の現在処理済みの境界上には存在しない別の境界線である。本例において、Ｒ３の境界をＢ４から周回してＢ１０まで辿り、境界線Ｂ１０が記憶される。境界線を再リンクすることにより、線と他の領域（本例ではＲ３）との間にある境界がそのまま残される場合、そのような境界線は検出されないかもしれないが、この場合、そのような境界線を検出する必要がないので、この境界は廃棄される。処理はステップ１９７０に進む。
【０１６９】
ステップ１９６０において、新しい短い境界線が２つの異なる領域間に作成される。この境界線は入力境界線であり、線骨格上の最も近い点と接触するように接続点から延長される。この結果は、図２１の例に続く図２２の例に示される。ここで、新しい境界線Ｂ１３が領域Ｒ２とＲ１との間に作成されている。境界線Ｂ１３は、境界線Ｂ５とＢ１とＢ１１とＢ１２との間の接続点から始まり、延長されて線骨格と接触する。新しい境界線Ｂ１３は領域Ｒ２に対しては境界線Ｂ１１にリンクされ、領域Ｒ１に対しては境界線Ｂ１２にリンクされる。処理はステップ１９７０に進む。
【０１７０】
決定ステップ１９７０において、この側の最終の境界線対に到達したか（「終わりに到達」）を判定するためのチェックが行われる。左側境界の終点が現在の境界線対の一方に含まれるならば（Ｙｅｓ）、処理は終了する。すなわち、ステップ１７２０の処理は終了している。そうでなければ（Ｎｏ）、ステップ１９１０に戻る。
【０１７１】
境界線を分解する図１７のステップ１７３０について、図２０に示す方法２０００を参照してより詳細に説明する。各入力境界線は線骨格上の関連位置を有し、本ステップではこれらの骨格位置を処理する。処理はステップ２０１０で開始する。ステップ２０１０において、左側と右側の境界線の骨格位置間の類似の値は同一の値にマージされる。これは厳密には必要ないが、図１７のステップ１７４０で不要な短い境界線を作成することが回避される。図２２の例において、２つの骨格位置の平均を与えられて完全に同一の位置で骨格と接触するように境界線Ｂ１０及びＢ７は隣接する。
【０１７２】
ステップ２０２０において、間違った順序の入力境界線が分解される。すなわち、骨格位置が線領域の境界の周囲の入力境界線の順序と異なる順序になっている同一側からの入力境界対が検出される。これは境界線が対向していた方向に境界線を延長した結果として生じ、これにより境界線が超えてしまう。これは、骨格が複雑な形状をしている場合に境界線を骨格上の最も近い点まで延長する場合に生じる可能性もある。この場合、境界線の骨格位置は入れ換えられる。
【０１７３】
ステップ２０３０において、同一の点が分解される。すなわち、同一の骨格位置を有する同一側からの複数対の連続入力境界線（ここで「連続」とは線の境界に辿る順序で）が識別される。これらはその後、上述の処理の例１９５０及び１９６０と同様な方法で処理される。連続入力境界線であるため、これらの境界線はそれらの中間で共通の領域を共有する必要があり、これら２本の境界線はその領域に対してリンクされる。他の２つの隣接領域が異なれば、新しい（長さ０）境界線がこれら他の２つの領域間に作成され、２本の連続入力境界線は入力境界線リストにおいてこの新しい１本の境界線により置換される。他の２つの隣接領域が同一ならば、これらの境界線はステップ１９５０と同様な方法で再リンクされ、２つの入力境界線は入力境界線リストから除去される。ステップ１９５０のように、２本の境界線は識別され、ステップ１７５０で後から使用するために記憶される。一方の境界線は２本の先行入力境界線の一方となり、他方は、現在の線領域には存在しない境界線に到達するまで領域を辿ることにより検出された２本の先行入力境界線の一方として同一の境界上に以前、存在した境界線となる。その後、処理は終了する。
【０１７４】
線骨格に沿って連結する図１７のステップ１７４０について、図２５の方法２５００を参照してより詳細に説明する。方法２５００はステップ２５１０で処理を開始する。ステップ２５１０において、次の骨格区間が選択される。この骨格線は、骨格線に接触するように入力境界線が延長された場所に応じて複数の区間に分割される。図２２において、４つの骨格軸区間ａ１〜ａ４がある。処理は骨格の始点から開始し、各連続区間を介して骨格の終点まで継続するように記載されているが、区間を処理する順番は重要ではない。
【０１７５】
各骨格区間において、左側の先行入力境界線、左側の次入力境界線、右側の先行入力境界線及び右側の次入力境界線が一般に存在するが、これらの内のいくつかがいくつかの区間では失われている（例えば、第１の区間には先行入力境界線がない）。
【０１７６】
左側で先行境界線と次境界線とに共通し且つ左側から骨格線まで延長された領域が存在する。例えば、図２２の区間ａ２では、領域Ｒ２が左側から延長され、境界線Ｂ６とＢ７とに共通している。同様に、右側で先行境界線と次境界線とに共通する右側からの領域が存在する。例えば再度、区間ａ２では、領域Ｒ１が延長されている。本例では、先行する右側境界線は存在せず、領域Ｒ１が依然として次の右側境界線Ｂ１３の領域となっている。
【０１７７】
ステップ２５２０において、これら２つの左側領域及び右側領域が同一であるかを判定するためのチェックが行われる。これらの領域が同一ならば（Ｙｅｓ）、ステップ２５４０に進み、そうでなければ（Ｎｏ）、ステップ２５３０に進む。
【０１７８】
ステップ２５３０において、新しい境界線が骨格線の当該区間に続く点と共に、２つの領域間に作成される。この新しい境界線は、線オブジェクトから開始しているものとして印を付けられ、以降の処理で使用される情報となる。この新しい境界線はその後、必要に応じてリンクされる。例えば、図２２を参照すると、骨格の第２の区間（ａ２、ここでは左側の先行境界線がＢ６であり、左側の次境界線がＢ７であり、右側の次境界線がＢ１３であり、右側の先行境界線は存在しない）において、新しい境界線Ｂ１４が作成される。この新しい境界線は図２３に示される。その後、ステップ２５５０に進む。
【０１７９】
ステップ２５４０において、領域の左側部分と右側部分とが連結されるように必要に応じて境界線が再リンクされる。例えば、図２２の線骨格の第３の区間（次の左側境界線がＢ７であり、先行する左側境界線がＢ６であり、次の右側境界線がＢ１０であり、先行する右側境界線がＢ１３である）において、左側と右側の２つの領域は共に領域Ｒ２である。この場合、Ｂ１３は領域Ｒ２に対して新しい境界線Ｂ１４にリンクされ、Ｂ７は領域Ｒ２に対してＢ１０にリンクされる。次に、ステップ１７５０を支援するために２本の境界線を記憶する必要がある。特に、上側区間からの１本の境界線と底側区間からの１本の境界線とを記憶する必要がある。図２２の例では、境界線Ｂ１０及びＢ１３を記憶すればよい。処理はステップ２５５０に進む。
【０１８０】
決定ステップ２５５０において、処理すべき骨格の更なる区間が存在するかを判定するためのチェックが行われる。そうであれば（Ｙｅｓ）、ステップ２５１０に戻り、そうでなければ（Ｎｏ）、方法２５００の処理は終了する。すなわち、骨格に沿って連結するステップ１７４０は完了する。図２３は、図２１及び２２の例における本処理の最終結果を示す。図２３において、この時点で多数の境界線が一緒にマージされ、特にＢ８とＢ９、Ｂ７とＢ１０、Ｂ６とＢ１４とＢ１３がマージされる。
【０１８１】
修正済み塗りつぶし領域の幾何形状を決定する図１７のステップ１７５０について、図２６の方法２６００を参照してより詳細に説明する。修正済み塗りつぶし領域の幾何形状は、境界線と境界とにより定義される。領域の境界を一緒にマージすることにより境界が変化し、いくつかの新しい境界が作成され、他の境界が一緒にマージされる。本ステップ１７５０では、各領域に対して新しい組の境界が識別される。以前の処理の間、特にステップ１９５０、２０３０及び２５４０の間に境界線リストが記憶される。このリストは生成された新しい各境界からの少なくとも１本の境界線を含む。低効率だがより単純な別の例では、ステップ１９００、２０００及び１７００の間に着目した全ての境界線をリストする。
【０１８２】
方法２６００はステップ２６１０で処理を開始する。ステップ２６１０において、次の記憶済み境界線が選択される。決定ステップ２６２０において、当該境界線に関連付けられた境界を既に訪れたかを判定するためにこの境界が検討される。この境界がステップ１７５０の処理中に新たに作成された境界の１つであれば、この境界を既に訪れており（Ｙｅｓ）、ステップ２６１０に戻る。そうでなければ（Ｎｏ）、新しい境界が作成され、ステップ２６３０に進む。
【０１８３】
ステップ２６３０において、境界は再度ラベル付けされる。すなわち、境界は境界線間のリンクを辿ることにより横断され、訪れた各境界線は新しく作成された境界の一部としてラベル付けされる。訪れた各境界線の既存の境界は、削除されている境界のリストに入れられる。これらの境界はステップ１７５０の終了時に削除される。
【０１８４】
決定ステップ２６４０において、リスト中に更なる記憶済み境界線が存在するかを判定するためのチェックが行われる。そうであれば（Ｙｅｓ）、ステップ２６１０に進み、そうでなければ（Ｎｏ）、処理は終了する。すなわち、修正済み塗りつぶし領域の幾何形状を決定するステップ１７５０は完了する。
【０１８５】
図２７は、部分的な透明性を有する重なりグラフィック線オブジェクトを検出し、図１５に示す方法１５５０のステップ１５８０で使用されるオブジェクトを記述する幾何形状モデルを構成する方法２７００を例示する。方法２７００はステップ２７１０で処理を開始する。ステップ２７１０において、部分的な透明性を有するオブジェクトの重なりの領域が検出される。この検出は、図１５のステップ１５７５で構成された修正済み塗りつぶし領域と関連隣接性情報とに基づいている。ステップ２７２０において、部分的な透明性を持って重なるグラフィックオブジェクトが構成される。グラフィックオブジェクトは領域を一緒に組み合わせることにより構成され、部分的な透明性を有するグラフィックオブジェクトの重なりに対応するいくつかの領域は２つ以上の構成済みグラフィックオブジェクトに含まれる。一実施形態において、重なり領域の妥当性の追加テストをこの段階で使用してもよい。重なりの領域と何れかの隣接領域との間の色差が小さすぎて偽陽性となる確率が高いならば、図７のステップ７４０又は７５０で検出された２つのオブジェクトの重なりの透明性モデルを棄却してもよい。塗りつぶし色、部分的な透明性及び階層化情報はグラフィックオブジェクトと共に提供される。
【０１８６】
図２７のステップ２７３０において、部分的な透明性無しに重なるグラフィックオブジェクトを検出するために、ステップ１５７５の間に構成された領域及び関連隣接性情報をオプションで（破線で示す）処理してもよい。本処理を行う技術は既知である。
【０１８７】
ステップ２７１０、２７２０及び２７３０における重なりオブジェクトの検出及び構成の後、ステップ２７４０では、構成済み幾何形状とステップ１５７０で検出され、図１５のステップ１５７５で処理された元線領域とを処理する（それらに基づいて）ことにより重なりグラフィックオブジェクトの線スタイルを検出する。ステップ２７４０については、図１２を参照して更に詳細に後述する。ステップ２７５０において、最終出力が線を複製しないことを保証するために、線領域がグラフィックオブジェクトに割り当てられる。その後、処理は終了する。
【０１８８】
図１２は、構成済みグラフィックオブジェクトとステップ１５７０で検出され元線領域とに基づいて重なりオブジェクトの線スタイルを検出する方法１２００を例示する。方法１２００は、ステップ２７２０又は２７３０で生成される各構成済みグラフィックオブジェクトを順次ループする。処理は、（未処理の）構成済みオブジェクトが存在するかをチェックする決定ステップ１２１０で開始する。存在すれば（Ｙｅｓ）、ステップ１２２０に進み、存在しなければ（Ｎｏ）、ステップ１２６０に進み、ループ（１２１０、１２２０、１２３０、１２４０及び／又は１２５０）を抜ける。ステップ１２２０では、未処理の次の構成済みグラフィックオブジェクトを選択する。ステップ１２３０でこのオブジェクトの次の隣接線が処理され、オブジェクトの周囲に一致した線スタイルがあるかを判定し、もしあれば線スタイルを算出する。ステップ１２３０については、図１６を参照して更に詳細に後述する。決定ステップ１２４０において、受入れ可能な線スタイルがステップ１２３０で検出されたかを判定するためのチェックが行われる。受入れ可能な線スタイルがあれば（Ｙｅｓ）、ステップ１２５０に進む。ステップ１２５０において、線スタイルは記憶され、その後ステップ１２１０に戻る。１２４０が偽（Ｎｏ）を返すと、ステップ１２１０に戻る。
【０１８９】
全てのグラフィックオブジェクトが解析されると、ステップ１２１０は偽（Ｎｏ）を返し、ステップ１２６０に進み、線が出力において複製されないように線を特定のグラフィックオブジェクトに関連付けられたものとして印をつける。これは、線スタイルがステップ１２３０で順次検出されたグラフィックオブジェクトを処理することにより行うことができる。各グラフィックオブジェクトの構成済み幾何形状は、線が除去された領域からの一部を含むことができる。この情報は、ステップ１５７５で生成され且つ境界線がその下に延長された線領域に応じて印を付けられた境界線に基づいて判定できる。このように印を付けられた構成済みオブジェクトの各境界線は、対応する線に割り当てられる。全てのグラフィックオブジェクトが処理されると、線をグラフィックオブジェクトに関連付ける好適なテストとしては、オブジェクトからの線に割り当てられた境界線の全長が線の骨格の長さより０．８倍大きくなり、他のグラフィックオブジェクトに割り当てられた境界線の長さより大きくなる。この条件が満たされるならば、その線は別個のオブジェクトに対応する確率が低く、グラフィックオブジェクトの一部と見なすことができる。破線の場合、骨格の一部だけがダッシュスタイルに基づいて複数のダッシュの内側に存在する事を説明するために異なるテストを行ってもよい。例えば、オブジェクトからの線に割り当てられた境界線の全長がダッシュ内の骨格の長さより０．８倍大きければ、線をグラフィックオブジェクトに関連付けてもよい。ステップ１２６０の後、方法１２００は終了する。
【０１９０】
図１６は、オブジェクトが図１２のステップ１２３０で用いられるような一貫性のある線スタイルを有するかを判定するために構成済みグラフィックオブジェクトに隣接する線を処理する方法１６００を例示する。方法１６００はステップ１６０５で処理を開始する。ステップ１６０５において、グラフィックオブジェクトの一組の線パラメータが初期化される。これらには以下が含まれる。
・オブジェクトの幾何形状の周囲の全長を累積した全長パラメータ（ｌtot）
・線に関連付けられたオブジェクトの幾何形状の周囲の全長を累積した線内長さパラメータ（ｌline）
・グラフィックオブジェクトの周囲の線の平均幅パラメータ（ｗline）
・何れの透明領域も重ならない複数の線の全長を累積した非重なり線内長さパラメータ（ｌover）
・非重なり線の平均色（色チャンネルｉのＣⁱover）
・透明領域の下にある複数の線の全長を累積した重なり線内長さパラメータ（ｌunder）
・透明領域の下にある複数の線の平均色（色チャンネルｉのＣⁱunder）
色及び幅パラメータを未設定として印を付ながら、全ての長さパラメータをゼロに初期化する。破線が処理中ならば、最初は未設定であるオブジェクトのダッシュスタイルをオプションで記憶してもよい。パラメータの初期化後、ステップ１６１０に進み、グラフィックオブジェクトの幾何形状を定義する全ての境界線を順次ループし、必要に応じて種々のパラメータを更新する。
【０１９１】
決定ステップ１６１０では、構成済みグラフィックオブジェクト上に更なる境界線が存在するかをチェックし、存在すれば（Ｙｅｓ）、ステップ１６１５へ進み、そうでなければ（Ｎｏ）、ステップ１６５０へ進む。ステップ１６１５では、次の境界線を選択し、その長さ（ｌｂｏｒｄ）を決定し、それを全長パラメータ（ｌｔｏｔ）に累積（加算）する。決定ステップ１６２０において、現在の境界線が線領域に構成されているかを判定するためのチェックが行われる。すなわち、現在の境界線がステップ１５７５で生成されて線領域の下に延伸していることを示すように現在の境界線に印が付いているかを判定するためのチェックが行われる。ステップ１６２０が偽（Ｎｏ）を返すと、ステップ１６１０に戻る。ステップ１６２０が真（Ｙｅｓ）を返すと、ステップ１６２５に進む。印が付いた線領域は現在の線と呼ばれ、ステップ１６２５で使用される。
【０１９２】
ステップ１６２５では、現在の線の幅をチェックし、パラメータを累積する。すなわち、現在の線の幅ｗcurrが選択され、その後、線内長さパラメータ（ｌline）が非ゼロで幅パラメータｗlineが以前に設定されているならば、ステップ１６２５では受入れテストをオプションで行ってもよい。幅パラメータが３００ｄｐｉのピクセル単位で測定されるならば、修正済み幅パラメータは以下のように計算してもよい。
【０１９３】

【０１９４】
そして、修正済み幅パラメータ及び修正済みの現在の線幅パラメータの最大に対する最小の比率が閾値０．６以上ならば、現在の線幅を受入れる。
【０１９５】

【０１９６】
次に、線内長さパラメータ（ｌline）がゼロならば、幅パラメータｗlineがこの幅に設定される。さもなければ、幅パラメータは現在のパラメータｗlineと現在の線幅の加重平均に設定される。
【０１９７】

【０１９８】
破線が本システムで処理中ならば、ダッシュスタイルもオプションで処理しなければならない。線内長さパラメータ（ｌline）がゼロならば、オブジェクトのダッシュスタイルは単に現在の線ダッシュスタイルに設定される。線内長さパラメータ（ｌline）が非ゼロであり、そのためダッシュスタイルがオブジェクトに設定されているならば、現在の線ダッシュスタイルがオブジェクトの周囲の現在のダッシュスタイルと比較される。スタイルに整合性があれば、オブジェクトの周囲のダッシュスタイルは２つのダッシュスタイルに基づいて設定され、スタイルに整合性がなければ、現在の線ダッシュスタイルは棄却される。最後に、境界線長さパラメータｌbordが線長さパラメータｌlineに加算され（すなわち、ｌline＝ｌline＋ｌbord）、ステップ１６２５を完了する。
【０１９９】
決定ステップ１６３０に進み、グラフィックオブジェクトが現在の境界線で重ねられているかをチェックする。これは、境界線に隣接するグラフィックオブジェクトに含まれる領域に基づいて判定できる。領域が２つ以上のグラフィックオブジェクトに含まれ、グラフィックオブジェクトの少なくとも１つが現在のグラフィックオブジェクト上に部分的な透明性を持って重ねられているならば、そのグラフィックオブジェクトは現在の境界線で重ねられ（Ｙｅｓ）、ステップ１６４０に進む。ステップ１６３０が偽（Ｎｏ）を返すと、ステップ１６３５に進む。
【０２００】
ステップ１６３５において、色誤差がチェックされ、パラメータが本オプションのステップで累積される。非重なり線色が設定されたならば、線色に対してオプションの受入れテストを行ってもよい。受入れテストでは、非重なり線の平均色Ｃⁱoverを現在の線色Ｃⁱcurrと比較する。好適なテストでは、ＲＧＢ空間の色距離（色パラメータが０〜２５５の範囲の値を取ると仮定して）を閾値と比較するが、このテストは以下の不等式をテストすることにより行われてもよい。
【０２０１】

【０２０２】
等式が真であるならば、線色を受入れる。
【０２０３】
非重なり線の平均色Ｃⁱoverは以下のように更新される。非重なり線内長さパラメータ（ｌover）がゼロならば、各チャンネルに対する非重なり線の平均色Ｃⁱoverは現在の線色Ｃⁱcurrに設定される。さもなければ、各チャンネルに対する非重なり線の平均色Ｃⁱoverは非重なり線色及び現在の線色の加重平均に設定される。
【０２０４】

【０２０５】
色を設定した後、境界線長さパラメータｌbordが非重なり線内長さｌoverに加算され（すなわち、ｌover＝ｌover＋ｌbord）、ステップ１６３５を完了する。処理はステップ１６１０に戻る。
【０２０６】
ステップ１６４０では、透明重なり部を補償する。ステップ１６４０では、透明重なりオブジェクトがない場合の現在の線の真の線色Ｃⁱtrueを推定する。単一の重なり層については、式（１）に基づき、現在の線色Ｃⁱcurrが重なりグラフィックオブジェクトの色Ｃⁱupper及び透明性αupperと真の線色とに以下のように関連付けられる。
【０２０７】

【０２０８】
この式を書き換えると、真の線色の式が得られる。
【０２０９】

【０２１０】
多重の層を処理するため、最上位層の重なりオブジェクトから開始し最下位層のオブジェクトで終了するように上記関係式が複数回使用される。各層が処理されると、現在の線色の値が推定された真の線色と置換され、次の層に対して繰り返される。しかし、推定された線色は各処理済み追加重なり層に対して精度が低いこともあるので、多重の重なりオブジェクトが存在する場合、ステップ１６４０及び１６４５を省略するのが好ましい。
【０２１１】
ステップ１６４５において、オプションで色誤差がチェックされ、パラメータが累積される。すなわち、重なり線色が設定されたならば、線色に対してオプションの受入れテストを行ってもよい。受入れテストでは、重なり線の平均色Ｃⁱunderをステップ１６４０で推定された現在の真の線色Ｃⁱtrueと比較する。好適なテストでは、ＲＧＢ空間の色距離（色パラメータが０〜２５５の範囲の値を取ると仮定して）を閾値と比較するが、このテストは以下の不等式をテストすることで行われてもよい。
【０２１２】

【０２１３】
等式が真であるならば、線色を受入れる。
【０２１４】
重なり線の平均色Ｃⁱunderは以下のように更新される。重なり線内長さパラメータ（ｌunder）がゼロならば、各チャンネルに対する重なり線の平均色Ｃⁱunderは現在の真の線色Ｃⁱtrueに設定される。さもなければ、重なり線色及び現在の真の線色の加重平均に設定される。
【０２１５】

【０２１６】
色を設定した後、境界線長さパラメータｌbordが重なり線内長さｌunderに加算され（すなわち、ｌunder＝ｌunder＋ｌbord）、ステップ１６４５を完了する。処理はステップ１６１０に戻る。
【０２１７】
ステップ１６５０では、累積データに基づきグラフィックオブジェクトの線スタイルを形成する。線幅（ｗobj）は平均幅パラメータに基づき選択され、線色（Ｃⁱobj）はＣⁱover、Ｃⁱunder、又はこれらの組み合わせに基づいて選択される。例えば、ｗobj＝ｗline且つＣⁱobj＝Ｃⁱoverである。破線を処理中であれば、ダッシュスタイルも線スタイルの一部として記憶される。使用中の色又は幅パラメータが設定されていないならば、線スタイルは設定されない。
【０２１８】
方法１６００の最終ステップ１６５５は、受入れ可能線スタイルがグラフィックオブジェクトに対して決定されたかを判定する受入れテストである。以下の判定基準のいずれかが生じると線スタイルは棄却される。
１．線スタイルがステップ１６５０で設定されていない。
２．ステップ１６２５の線幅受入れテストがいずれかの境界線で失敗した。
３．ステップ１６３５の色受入れテストがいずれかの境界線で失敗した。
４．ステップ１６４５の色受入れテストがいずれかの境界線で失敗した。
５．線内長さパラメータ（ｌline）が、オブジェクトの全長パラメータ（ｌtot）の十分な割合（例えば、ｌline＜０．８ｌtot）を占めていない。
６．ステップ１６２５のダッシュスタイル整合性テストがいずれかの境界線で失敗した。
【０２１９】
その後、処理は終了する。
【産業上の利用可能性】
【０２２０】
上述の構成は、コンピュータ及びデータ処理産業、特に処理グラフィックオブジェクトに対して利用可能である。
【０２２１】
オブジェクト表現をビットマップ画像から生成する方法、装置及びコンピュータ可読媒体を説明した。上記では、本発明のいつかの実施形態のみを記載したが、本発明の範囲から逸脱することなく変形及び／又は変更可能であり、これらの実施形態は例示的なものであり限定的なものではない。
【０２２２】
本明細書の文脈において、用語「具備する」は、「主に含むが、単独で必要ではない」、「有する」又は「含む」ことを意味し、「〜のみから構成される」ことではない。用語「具備する」の語形変化は、それに対応して意味の変化を示す。

【特許請求の範囲】
【請求項１】
オブジェクト表現をビットマップ画像から生成するコンピュータにより実現される方法であって、
前記ビットマップ画像の背景領域を含む一組の領域を前記ビットマップ画像から選択するステップと、
前記一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するステップであって、前記推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、前記透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するステップと、
前記一組の領域と前記第１のグラフィックオブジェクトの前記推定された色及び透明性パラメータとから前記第１及び第２のグラフィックオブジェクトの幾何形状モデルを構成するステップと、
前記幾何形状モデルに応じて前記オブジェクト表現を生成するステップと、
を有する方法。
【請求項２】
前記オブジェクト表現は電子文書であり、前記ビットマップ画像は文書の走査版である請求項１に記載の方法。
【請求項３】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、
前記第１及び第２のグラフィックオブジェクトの重複部の領域として考えられる前記一組の領域である第１の領域と、
前記第１のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第２の領域と、
前記第２のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第３の領域と、
に応じて推定される請求項１に記載の方法。
【請求項４】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、前記ビットマップ画像の前記第１の領域の色と、前記第２の領域及び前記第３の領域並びに背景領域の色を考慮して前記透明性合成モデルにより定義される色との間で色差が最小になるように推定される請求項３に記載の方法。
【請求項５】
前記第２のグラフィック領域は部分的に透明である請求項１に記載の方法。
【請求項６】
前記第１のグラフィックオブジェクトは前記第２のグラフィックオブジェクト及び第３のグラフィックオブジェクトに部分的な透明性をもって重なり、前記第２のオブジェクトは前記第３のオブジェクトに部分的な透明性をもって重なり、
前記第１、第２及び第３のグラフィックオブジェクトは部分的な透明性をもって重なり、
前記一組の領域は第１の領域と、前記第１の領域の外側境界に隣接する少なくとも３つの領域と、背景領域とを有し、
前記３つの隣接領域の各々は、部分的な透明性で前記グラフィックオブジェクトの２つの重複部に対応する色及び透明性パラメータを含む関連透明性モデルを有し、
前記３つの隣接領域の前記透明性モデルは、部分的な透明性で前記３つのグラフィックオブジェクトの重複部に対応する透明性モデルと一致する請求項５に記載の方法。
【請求項７】
前記３つのグラフィックオブジェクトは部分的な透明性をもって重なる円である請求項６に記載の方法。
【請求項８】
グラフィックオブジェクトの幾何形状モデルは、辿った境界線に隣接する領域の透明性モデルを追跡しながら領域の境界線を辿ることにより構成される請求項１に記載の方法。
【請求項９】
前記グラフィックオブジェクトの色、透明性及び階層化パラメータは、グラフィックオブジェクトの幾何形状モデルを構成する際に横断された境界線に隣接する領域の透明性モデルに応じて設定される請求項８に記載の方法。
【請求項１０】
オブジェクト表現をビットマップ画像から生成する装置であって、
データとコンピュータプログラムとを記憶するメモリと、
コンピュータプログラムを実行するために、前記メモリに連結されたプロセッサ部とを有し、前記メモリ及び前記プロセッサは、前記オブジェクト表現を前記ビットマップ画像から生成するように構成され、前記コンピュータプログラムは、
前記ビットマップ画像の背景領域を含む一組の領域を前記ビットマップ画像から選択するコンピュータプログラムコード手段と、
前記一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するコンピュータプログラムコード手段であって、前記推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、前記透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するコンピュータプログラムコード手段と、
前記一組の領域と前記第１のグラフィックオブジェクトの前記推定された色及び透明性パラメータとから前記第１及び第２のグラフィックオブジェクトの幾何形状モデルを構成するコンピュータプログラムコード手段と、
前記幾何形状モデルに応じて前記オブジェクト表現を生成するコンピュータプログラムコード手段とを有する装置。
【請求項１１】
前記オブジェクト表現は電子文書であり、前記ビットマップ画像は文書の走査版である請求項１０に記載の装置。
【請求項１２】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、
前記第１及び第２のグラフィックオブジェクトの重複部の領域として考えられる前記一組の領域である第１の領域と、
前記第１のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第２の領域と、
前記第２のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第３の領域と、
に応じて推定される請求項１０に記載の装置。
【請求項１３】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、前記ビットマップ画像の前記第１の領域の色と、前記第２の領域及び前記第３の領域並びに背景領域の色を考慮して前記透明性合成モデルにより定義される色との間で色差が最小になるように推定される請求項１２に記載の装置。
【請求項１４】
前記第２のグラフィック領域は部分的に透明である請求項１０に記載の装置。
【請求項１５】
グラフィックオブジェクトの幾何形状モデルは、辿った境界線に隣接する領域の透明性モデルを追跡しながら領域の境界線を辿ることにより構成される請求項１０に記載の装置。
【請求項１６】
プロセッサ部による実行のために、オブジェクト表現をビットマップ画像から生成するコンピュータプログラムが記録されたコンピュータ読み取り可能な記憶媒体であって、前記コンピュータプログラムは、
前記ビットマップ画像から前記ビットマップ画像の背景領域を含む一組の領域を選択するコンピュータプログラムコード手段と、
前記一組の領域の色に応じて第２のグラフィックオブジェクトに重なる部分的な透明性を有する第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するコンピュータプログラムコード手段であって、前記推定される色及び部分的な透明性パラメータは透明性合成モデルと一致し、前記透明性合成モデルは色及び部分的な透明性パラメータによって２つのグラフィックオブジェクトの重複部の領域の色を定義するコンピュータプログラムコード手段と、
前記一組の領域と前記第１のグラフィックオブジェクトの前記推定された色及び透明性パラメータとから前記第１のグラフィックオブジェクト及び前記第２のグラフィックオブジェクトの幾何形状モデルを構成するコンピュータプログラムコード手段と、
前記幾何形状モデルに応じて前記オブジェクト表現を生成するコンピュータプログラムコード手段とを備えたコンピュータ読み取り可能な記憶媒体。
【請求項１７】
前記オブジェクト表現は電子文書であり、前記ビットマップ画像は文書の走査版である請求項１６に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１８】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、
前記第１及び第２のグラフィックオブジェクトの重複部の領域として考えられる前記一組の領域である第１の領域と、
前記第１のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第２の領域と、
前記第２のグラフィックオブジェクトの一部として考えられる前記第１の領域に隣接する前記一組の領域である第３の領域と、
に応じて推定される請求項１６に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１９】
前記第１のグラフィックオブジェクトの前記部分的な透明性パラメータは、前記ビットマップ画像の前記第１の領域の色と、前記第２の領域及び前記第３の領域並びに背景領域の色を考慮して前記透明性合成モデルにより定義される色との間で色差最小になるように推定される請求項１８に記載のコンピュータ読み取り可能な記憶媒体。
【請求項２０】
前記第２のグラフィック領域は部分的に透明である請求項１６に記載のコンピュータ読み取り可能な記憶媒体。
【請求項２１】
オブジェクト表現をビットマップ画像から生成するコンピュータにより実現される方法であって、
部分的な透明性を持つ独立した第１のグラフィックオブジェクトと共に独立した第２のグラフィックオブジェクトを含む前記ビットマップ画像から、各々が塗りつぶし色を持つ塗りつぶし領域と各々が線色を持つ線領域との一組を判定するステップと、
前記線領域の少なくとも１つにより分離された２つ以上の塗りつぶし領域を位置決めし、位置決めされた領域を隣接させることにより前記塗りつぶし領域の隣接性データを生成するステップと、
前記塗りつぶし色と前記塗りつぶし領域の隣接性データとに応じて前記第２のグラフィックオブジェクトに重なる前記第１のグラフィックオブジェクトの色及び部分的な透明性パラメータを推定するステップと、
前記線領域のうちの少なくとも１つの領域の線色に基づいて前記第２のグラフィックオブジェクトの輪郭線の単一の線色を決定するステップと、
前記オブジェクト表現を生成するために、前記推定された色及び部分的な透明性パラメータを有する前記第１の独立したグラフィックオブジェクトと、前記決定された単一の線色を有する前記第２の独立したグラフィックオブジェクトとを記憶するステップと、
を有する方法。
【請求項２２】
前記単一の線色は前記第１のオブジェクトの前記推定された色及び部分的な透明性パラメータに基づいて決定され、前記第１のオブジェクトにより重ねられる前記線領域の線色は前記第１のオブジェクトの前記推定された色及び部分的な透明性パラメータにより修正された場合に前記単一の線色と一致する請求項２１に記載の方法。
【請求項２３】
前記第１及び第２のグラフィックオブジェクトを記憶するステップは、前記線色が前記第１のオブジェクトの前記推定された色及び部分的な透明性パラメータにより修正された場合、前記単一の線色と前記第１のグラフィックオブジェクトにより重ねられる線領域の内の１つの領域の線色との間の比較に依存する請求項２２に記載の方法。

【図１】