JP2008059081A - 画像処理装置及び画像処理方法、並びにコンピュータ・プログラム - Google Patents

Abstract

【課題】デジタル画像に含まれる写真や名刺、本の表紙などさまざまな書画を複雑な背景画像から正確に抽出処理する。
【解決手段】入力画像を隣接グラフとして扱い、隣接するノード同士を統合すべきか否かを統計的処理アルゴリズムに基づいて判断し、ノードの統合を繰り返し実行していくことにより、画像セグメンテーションを行なう。統計的処理アルゴリズムに基づく判断式のパラメータ値を変更することで、デジタル画像に含まれる書画領域を抽出する、あるいは書画画像からなる前景領域をそれ以外の背景と分離するのにちょうどよい粗さのセグメントとなるように画像分割する。
【選択図】 図２

Description

本発明は、デジタル画像を処理する画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに係り、特に、デジタルカメラにより捕捉された画像に含まれるオブジェクトの画像を処理する画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに関する。

さらに詳しくは、本発明は、デジタル画像に含まれる書画情報を処理する画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに係り、特に、複数の書画情報を含むデジタル画像から各書画原稿を背景イメージから分離して取り出す画像処理装置及び画像処理方法、並びにコンピュータ・プログラムに関する。

最近、ＣＣＤ（Ｃｈａｒｇｅ Ｃｏｕｐｌｅｄ Ｄｅｖｉｃｅ）やＣＭＯＳ（Ｃｏｍｐｌｅｍｅｎｔａｒｙ Ｍｅｎｔａｌ−Ｏｘｉｄｅ Ｓｅｍｉｃｏｎｄｕｃｔｏｒ）などの固体撮像素子で捕捉した画像をデジタル符号化するデジタルカメラが広範に普及している。デジタルカメラは、フィルムや感光板を使って撮影する銀塩カメラと比較すると、デジタル符号化された画像をメモリに記憶し、コンピュータによる画像処理や画像管理を行なうことができ、さらにフィルムの寿命という問題がないといった利点がある。

デジタルカメラは、一般には風景や人の撮影に用いるが、他の用途として、書画情報のデジタル化を挙げることができる。例えば、紙面文書や名刺などの書類、プレゼンテーションや会議などにおいて筆記された黒板若しくはホワイトボード、プロジェクタで投影されたスクリーンなどの書画情報を、デジタルカメラを通してデジタル入力し、情報の保存や管理を始めさまざまな画像処理を適用することができる。

例えば、名刺取り込み機能を備えた画像撮影装置について提案がなされている（例えば、特許文献１を参照のこと）。この画像撮影装置は、名刺を撮影する際に名刺のサイズに合わせて自動的にズームを行ない、撮影画角と同程度の大きさで名刺を撮影するようになっている。

また、名刺や看板などの被写体を撮影した画像信号から文字情報を抽出してテキスト文字列に変換し、テキスト文字列から認識される所定の項目に基づいて文字情報の項目を分類して格納する電子カメラについて提案がなされており（例えば、特許文献２を参照のこと）、初期投資や手間を掛けずに簡便に名刺データの管理を行なうことができる。

また、デジタル画像を書画などの前景オブジェクトと背景に分離して、書画の領域のみを取り出して１つの写真画像として利用することができる。本発明者らは、写真画像に含まれている別の写真画像を取り出す技術のことを“ＰｉｃｓＩｎＰｉｃ”と呼んでいる。

従来は、元画像を微分処理して得られるエッジ画像に基づいて書画などの画像オブジェクトの輪郭を抽出して背景画像から切り出すことが一般的である。例えば、撮影対象のエッジ画像からラドン変換を用いて直線検出を行ない、検出した直線パラメータから撮影対象の輪郭を形成する四角形を形成し、これを射影変換して撮影対象を正面から撮影したような画像を取得する画像処理装置について提案がなされている（例えば、特許文献２を参照のこと）。

しかしながら、エッジ画像を用いて輪郭抽出を行なう場合、書画と背景には絶対的なコントラストがあることが前提となり、背景や書画自体にエッジ情報が含まれている場合には、正確に輪郭を抽出することが困難となる。例えば、柄模様の絨毯の上に置かれた写真を抽出することは難しい。また、複数の書画が含まれるデジタル画像から個々の書画を１つずつ抽出することは難しい。

特開２００３−２８３９０９号公報 特開２００５−２７５４４７号公報

本発明の目的は、デジタルカメラにより捕捉された画像などのデジタル画像に含まれる１以上のオブジェクトの画像を好適に処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。

本発明のさらなる目的は、デジタル画像に含まれる１以上の書画を背景画像から分離して抽出処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。

本発明のさらなる目的は、デジタル画像に含まれる写真や名刺、本の表紙などさまざまな書画情報を複雑な背景画像から正確に抽出処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することにある。

本発明は、上記課題を参酌してなされたものであり、その第１の側面は、画像に含まれる書画情報を抽出する画像処理装置であって、
入力画像を領域毎に分割する画像分割手段と、
分割された領域の輪郭に基づいて書画情報を含んだ書画領域を抽出する領域抽出手段と、
を具備することを特徴とする画像処理装置である。

この画像処理装置は、前記領域抽出手段により抽出された書画領域から四角形を検出する四角形検出手段と、該検出した四角形領域を正面から眺めた画像となるように逆射影変換するとともにアスペクト比を調整する画像変換手段をさらに備えていてもよい。

デジタルスチルカメラによる撮影画像から書画領域を抽出することによって、抽出した画像オブジェクトや、さらに画像に含まれるテキストなどの文字情報を認識して、さまざまなサービスを提供することができる。

しかしながら、元画像を微分処理して得られるエッジ画像に基づいて書画の輪郭を抽出して背景画像から切り出すという旧来の方法では、書画と背景には絶対的なコントラストがあることが前提となり、背景や書画自体にエッジ情報が含まれている場合には、正確に輪郭を抽出することが困難となる。例えば、柄模様の絨毯の上に置かれた写真を抽出することは難しい。また、複数の書画が含まれるデジタル画像から個々の書画を抽出することは難しい。

これに対し、本発明に係る画像処理装置では、画像分割手段は、入力画像を隣接グラフとして扱う。この隣接グラフは、ピクセル若しくはピクセルの塊からなる多角形などの画像の構成単位をノードとして扱い、隣接するノード間をエッジで接続することで画像情報を記述するものである。そして、エッジで結ばれる各ノードが持つ属性値を比較した結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングすると、ソートされた順に従ってエッジを挟むノードのペアを取り出し、ノード同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、ノードの統合処理を行なう。このような統合処理を繰り返すことによって、入力画像を複数の画像領域に分割する。

すなわち、画像分割手段は、隣接するノード同士を統合すべきか否かを統計的処理アルゴリズムに基づいて判断し、ノードの統合を繰り返し実行していくことにより、個々を知覚できない多数のノードからなる生のデータから、セグメントと呼ばれる知覚可能な少数の単位に成長させることができる。ここで言う統計的処理アルゴリズムでは、例えば各ノードがそれぞれ持つ属性情報における集中不均衡（ｃｏｎｃｅｎｔｒａｔｉｏｎ ｉｎ−ｅｑｕａｌｉｔｙ）現象から導き出される判断式に基づいて、隣接するノード同士が類似するか、言い換えればノードを統合することができるかどうかを判別する。

このような統計的処理アルゴリズムに基づくノードの統合処理は、各ノードが持つ属性情報を統計処理するという簡素な計算で構成されることから、高速化が可能である。例えば、パーソナル・コンピュータなどの一般的な計算機を用いて毎秒百万個の多角形を処理することができる。また、判断式に含まれるパラメータ値を調整することによって、ノード同士を統合する基準を自在に設定して、所望する粗さのセグメントまで成長させることができ、システムはスケーラビリティを持つ。

したがって、本発明によれば、生のデータを構成する複数のノードのトポロジを入力値とし、ノードの統合処理を統計的処理アルゴリズムに従って再帰的に行なっていく（すなわち、ｍｅｓｈ ｇｒｏｗｉｎｇを行なう）ことで、任意の粗さのセグメントを生成することができる。また、統計的処理アルゴリズムに基づく判断式のパラメータ値を変更することで、デジタル画像に含まれる書画領域を抽出する、あるいは書画画像からなる前景領域をそれ以外の背景と分離するのにちょうどよい粗さのセグメントとなるように、入力画像を画像分割することができる。

但し、書画が複雑なテクスチャを持つ、あるいは書画が載せられている背景もテクスチャを持つ場合には、書画の領域もセグメント化されて一体ではなくなる、あるいは背景もセグメント化されて書画の領域との区別がつかなくなることから、画像分割手段が良好に動作しない可能性がある。

そこで、画像分割手段は、原画像から個々の書画などからなる前景領域を抜き取る第１の画像分割処理と、原画像から書画など以外の背景領域を抜き取る第２の画像分割処理を２元的に行なうことによって、画像セグメンテーションの精度を向上させるようにしてもよい。

画像処理装置は、入力画像を微分処理する微分処理手段をさらに備える。そして、前記隣接グラフ生成手段は、前記微分処理手段から出力される微分画像のうち帯域が所定値未満となる（例えば、書画やテクスチャなどの領域の輪郭に該当しない）ピクセルに対してのみ、他のピクセルと接続するエッジを付与して、部分的隣接グラフを作成する。隣接するピクセルであっても、エッジがなければ統合されることはなく、分離されたまま画像セグメンテーションの処理が進行していくことになる。

したがって、統合処理手段は、境界に差し掛かっているノード同士を統合処理して、背景を１つの領域として統合することができる。この結果、画像処理装置としては、書画などの前景の画像領域を抜き取るとともに、書画が載せられている背景の画像領域を抜き取り、それぞれを出力することができる。

また、画像分割手段により画像セグメンテーション処理を行なった結果、セグメント化された領域の中に、さらに他の小さな領域が含まれている場合がある。しかしながら、別の領域の含まれる小領域は基本的には書画情報に含まれる個々のコンテンツに過ぎず、最外周の輪郭からなる領域しか必要がない。そこで、領域抽出手段は、このような小領域を破棄する。

また、本発明の第２の側面は、画像に含まれる書画情報を抽出するための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
入力画像を領域毎に分割する画像分割手順と、
分割された領域の輪郭に基づいて書画情報を含んだ書画領域を抽出する領域抽出手順と、
前記領域抽出手順において抽出された書画領域から四角形を検出する四角形検出手順と、
該検出した四角形領域を正面から眺めた画像となるように逆射影変換するとともに、アスペクト比を調整する画像変換手順と、
を実行させることを特徴とするコンピュータ・プログラムである。

本発明の第２の側面に係るコンピュータ・プログラムは、コンピュータ・システム上で所定の処理を実現するようにコンピュータ可読形式で記述されたコンピュータ・プログラムを定義したものである。換言すれば、本発明の第２の側面に係るコンピュータ・プログラムをコンピュータ・システムにインストールすることによって、コンピュータ・システム上では協働的作用が発揮され、本発明の第１の側面に係る画像処理装置と同様の作用効果を得ることができる。

本発明によれば、デジタル画像に含まれる１以上の書画を背景画像から抽出処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することができる。

また、本発明によれば、デジタル画像に含まれる写真や名刺、本の表紙などさまざまな書画を複雑な背景画像から正確に抽出処理することができる、優れた画像処理装置及び画像処理方法、並びにコンピュータ・プログラムを提供することができる。

本発明のさらに他の目的、特徴や利点は、後述する本発明の実施形態や添付する図面に基づくより詳細な説明によって明らかになるであろう。

以下、図面を参照しながら本発明の実施形態について詳解する。

画像処理の分野では、ピクセル（若しくはピクセルの塊からなる多角形（ポリゴン）メッシュ）からなるノードで構成される画像データを、隣接するノード間の接続関係を記述した隣接グラフ（Ｉｎｃｉｄｅｎｃｅ Ｇｒａｐｈ若しくはＲｅｇｉｏｎ Ａｄｊａｃｅｎｔ Ｇｒａｐｈ（ＲＡＧ））の形式で表現することは一般的に行なわれている。本発明は、デジタル画像を複数のノード並びにノード間を結ぶエッジで構成される隣接グラフの形式で記述し、エッジで結ばれているノード同士の統合処理を繰り返していくことを通じて元のデジタル画像の画像分割を行ない、最終的には、デジタル画像に含まれる絵葉書や名刺、本の表紙などの書画の画像領域を背景画像から分離させるものである。例えば、元のデジタル画像が図１Ａに示すような、４個の書画を含んだ８メガバイトの画像データである場合、本発明によれば、図１Ｂに示すように、それぞれ約１メガバイトの画像データを背景から分離して取り出すことができる。

本発明に係る画像処理方法では、隣接グラフの形式で記述された画像データを用いて、デジタル画像に含まれるそれぞれの書画（ｐｉｃｔｕｒｅｓ ｉｎ ｐｉｃｔｕｒｅ）を認識し、これらを１つずつ画像領域としてまとめ上げてそれぞれの絵を生成するようになっている。また、元のデジタル画像に含まれている四角形を射影変換して、適当な矩形領域にする。模様のある背景画像から個々の絵を正確に取り出すためには、システムが堅牢であることと高速処理が可能であることが必要である。

本発明は、例えばデジタルカメラに適用することで、紙面文書や名刺などの書類、プレゼンテーションや会議などにおいて筆記された黒板若しくはホワイトボード、プロジェクタで投影されたスクリーンといった書画情報を撮影して、撮影画像に含まれる書画を抽出することができる。図２４には、本発明の一実施形態に係るデジタルスチルカメラの構成を示している。

図示のデジタルスチルカメラ２００は、撮像素子２１１と、前処理部２１２と、カメラ・デジタル信号処理部（ＤＳＰ）２１６で構成され、

撮像素子２１１は、ＣＣＤやＣＭＯＳなどの光電変換効果を持つ各画素が２次元に配列され、受光側には例えばＧ市松ＲＢ色コーディング単板が配設されている。各色フィルタを通した入射光量に対応する信号電荷が各画素に蓄積され、各画素から読み出される３色の各信号電荷量からその画素位置における入射光の色を再現することができる。

前処理部２１２は、ＣＤＳ／ＡＧＣ／ＡＤＣブロック２１３と、タイミング・ジェネレータ２１４と、Ｖドライバ２１５で構成される。

ＣＤＳ／ＡＧＣ／ＡＤＣブロック２１３では、画素信号中の撮像素子２１１から受ける信号の低雑音を高精度に抑圧した後（Ｃｏｒｒｅｌａｔｅｄ Ｄｏｕｂｌｅ Ｓａｍｐｌｉｎｇ（相関二重サンプリング）：ＣＤＳ）、デジタル信号に変換し、さらにＡＧＣ（Ａｕｔｏｍａｔｉｃ Ｇａｉｎ Ｃｏｎｔｒｏｌ：自動利得制御回路）により適正なゲイン・コントロールをかける。

タイミング・ジェネレータ２１４は、撮像素子２１１を駆動するためのタイミング・パルス信号を生成する。そして、Ｖドライバ２１５は、このタイミング・パルス信号に従って、撮像素子２１１の各画素の電荷を垂直方向にライン単位で出力するための駆動信号を出力する。

カメラＤＳＰ部２１６は、カメラ信号処理部２１７と、解像度変換部２１８と、画像コーデック処理部２１９と、メモリ制御部２２０と、表示制御部２２１と、メディア制御部２２２を備えている。

カメラ信号処理部２１７は、前処理部２１２から送られてくる画像信号に対しＡＷＢ（Ａｕｔｏ Ｗｈｉｔｅ Ｂａｌａｎｃｅ）によりホワイトバランス・ゲインを掛けて適正な色状態を再現し、さらにデモザイク処理によりＲＧＢ画面信号を作成する。また、カメラ信号処理部２１７は、ＲＧＢ画像信号に対してγ補正を施し、画像情報をモニタ出力、プリントアウト、又は画像記録する際に適した階調に変換する。

解像度変換部２１８は、画像のサイズの変更を行なう。画像コーデック処理部２１９は、ＲＧＢ画像信号を輝度信号と色差信号（Ｙ／Ｃｒ／Ｃｂ）に色空間変換し、ＪＰＥＧ（Ｊｏｉｎｔ Ｐｉｃｔｕｒｅ Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ）圧縮などの符号化処理を行なう。

メモリ制御部２２０は、撮影した画像情報などのデータを、ＳＤＲＡＭ（Ｓｙｎｃｈｒｏｎｏｕｓ ＤＲＡＭ）などからなるメモリ装置２２４に対して書き込みや読み出しを行なうためのアクセス動作を制御する。

表示制御部２２１は、ＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）などで構成されるモニタ・ディスプレイ２２５の駆動を制御し、例えばメモリ装置２２４に保持されている撮影画像の表示出力を行なう。

メディア制御部２２２は、メモリスティック（登録商標）などの着脱可能な記録メディア２２６を装填するためのスロットを備え、記録メディア２２６へのデータの書き込みや読み出しを行なう。例えばメモリ装置２２４に保持されている撮影画像ファイルを記録メディア２２６に記録する。

また、カメラＤＳＰ部２１６は、バス・インターフェース・ユニット（ＢＩＵ）２２３を介して制御部２２７に接続されている。制御部２２７は、シャッターボタンやズーム、その他のカメラ・ワークなどをユーザが指示するための操作部２２８と、ユーザ操作に応じて当該装置全体の動作を統括的に制御するＣＰＵ２２９と、ＣＰＵ２２９にとっての主記憶メモリであるＲＡＭ２３０と、プログラム・コードや装置情報などを不揮発的に保持するＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ Ｅｒａｓａｂｌｅ ａｎｄ Ｐｒｏｇｒａｍｍａｂｌｅ ＲＯＭ）２３１などで構成される。

図２には、図１に示したデジタルカメラに搭載される、デジタル画像から書画領域の抽出を行なう画像処理機能の構成を模式的に示している。図示の画像処理機能を構成する各機能モジュールは、実際には、ＣＰＵ上で実行する所定のプログラム・コードによって実現される。

図示の画像処理機能は、専用のハードウェア装置としてデザインしてもよいが、デジタルカメラ２００の組み込みアプリケーションとして実現することができる。あるいは、デジタルカメラから撮影画像を取り込むパーソナル・コンピュータ（ＰＣ）などの一般的な計算機システム上で各機能モジュール１〜４に相当する処理を実行するアプリケーション・プログラムを起動するという形態で実現することも可能である。一般的な計算機システムは、例えばプロセッサに米インテル社のＰｅｎｔｉｕｍ（登録商標）ＩＶ（１．６ＧＨｚ）を使用し、１ＧＢのＲＡＭで構成されるメイン・メモリを備える。また、アプリケーション・プログラムは、例えばＯｐｅｎＧＬで提供されるＡＰＩ（アプリケーション・プログラミング・インターフェース）を利用して、Ｃ⁺⁺言語でコーディングすることができる。

図示の画像処理機能は、隣接グラフを用いた画像領域のセグメンテーション処理を行なう画像セグメンテーション部１１と、外側の輪郭から領域を抽出する領域抽出部１２と、セグメント化された画像から書画を構成する四角形領域を探索する四角形領域探索部１３と、四角形領域の元のアスペクト比を推定するアスペクト比推定部１４を備え、推定されたアスペクト比に応じて四角形領域を矩形領域に再割り当てして、１又は複数の絵（書画）を出力する。

図３には、複数の名刺を撮影したデジタル画像に画像セグメンテーション処理を施した画像から矩形領域を認識して、個々の名刺の画像を再マッピングする様子を示している。このようなアプリケーションは、一種のＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅｃｏｇｎｉｚｅｒ）の代替技術となり得る。

例えば、この技術をデジタルカメラに搭載した場合、通常の撮影モード下では、ファインダ上には図４Ａに示すように複数の名刺が散在した現実の画像が表示される。一方、ｐｉｃｓｉｎｐｉｃ（書画表示）モード下では、ファインダ上には、図４Ｂに示すように、認識された個々の名刺を所定のアスペクト比に再割り当てした画像が整然と並べられている。

また、図２に示した画像処理機能によれば、書画として名刺以外に、書籍の表紙（ｂｏｏｋ ｃｏｖｅｒ）なども扱うことができる。図５Ａに示すように、絨毯の上に散在する書籍を撮像したデジタル画像に対し、隣接グラフを用いた画像領域のセグメンテーション処理を施し、図５Ｂに示すように外側の輪郭から個々の書籍の領域を抽出する。さらに、図５Ｃに示すように、抽出された個々の領域の画像をコンピュータなどのネットワーク接続された情報機器に取り込んで、表紙の画像を文字認識して本のタイトルやＩＳＢＮ（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｔｙａｎｄａｒｄ Ｂｏｏｋ Ｎｕｎｂｅｒ）などの文字列情報を取り出し、データベース検索を行なうことができる。さらにデータベース検索結果を基に、書籍のオンラインショッピングや、ブログ討論、その他の付加的な情報提供といった、他のサービス・アプリケーションとの連携を図ることができる。

また、さまざまな書画が散在するデジタル画像から抽出した四角形領域に含まれる文字列情報をデータベース検索した結果、書画がＣＤやＤＶＤなどのメディアのジャケットであることが判明したときには、図６に示すように、抽出された四角形領域をジャケットが持つアスペクト比の矩形領域に再マッピングするようにしてもよい。

以下では、図２に示した画像処理機能を構成する各部１１〜１４における処理について詳解する。

画像セグメンテーション：
図７には、画像セグメンテーション部１１の内部構成を示している。図示の画像セグメンテーション部１１は、処理対象となる３次元画像情報を隣接グラフの形式に編集する画像情報編集部１１１と、入力した隣接グラフの各エッジを評価してソーティングを行なう隣接グラフ評価部１１２と、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、これらを統計的処理アルゴリズムに基づいて評価して統合処理（ｍｅｓｈ ｇｒｏｗｉｎｇ）を行なう画像領域統合処理部１１３と、画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理部１１４を備えている。

画像処理の分野では、画像領域としての多角形メッシュを、その構成要素となる複数の多角形間の関係を記述した隣接グラフ（Ｉｎｃｉｄｅｎｃｅ Ｇｒａｐｈ若しくはＲｅｇｉｏｎ Ａｄｊａｃｅｎｔ Ｇｒａｐｈ（ＲＡＧ））の形式で表現することは一般的に行なわれている。隣接グラフの具体的な記述方法は幾つか挙げられる。隣接グラフは、複数のノードと、ノード間を結ぶエッジで構成されるが、ノード及びエッジに何を扱うかはさまざまである。例えば、多角形をノードとすると、その辺又は頂点をエッジにすることができる。あるいは、多角形の辺をノードとした場合、頂点又は多角形をエッジにすることができる。あるいは、頂点をノードとした場合、多角形の辺又は多角形をエッジにすることができる。

本実施形態では、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフを扱う。すなわち、画像情報入力部１１１は、多角形メッシュを構成する個々の多角形をノードとし、隣接する多角形同士が接する辺に相当するエッジを用いて対応するノード間を結んで記述される隣接グラフを入力データとする。

ここで、隣接グラフの作成方法について説明しておく。

まず、対象とする画像領域に属する各多角形Ｔ_iをノードＮ_iに関連付ける。そして、ノードＮ_iとノードＮ_j間において、双方に対応する多角形Ｔ_i及びＴ_jに属する唯一の辺があれば、両ノード間を結ぶエッジｅ_ijとして生成する。

隣接グラフは、エッジの端点に従って多角形のソーティングを行なうことによって、頂点及び面のインデックス配列から直接的に構築することができる。個々の多角形に属する辺すなわちエッジは、多角形メッシュすなわち画像領域の境界となるエッジ（Ｂｏｕｎｄａｒｙ ｅｄｇｅ）と、多角形メッシュではなく多角形メッシュ内の隣接する他の多角形と接するエッジ（Ｉｎｔｅｒｉｏｒ Ｅｄｇｅ）に分けられる。画像領域の境界に当たるエッジは１つの多角形にしか属さないので、境界以外（すなわち画像領域の内側の）エッジのみを処理対象にする。この処理には、頂点及び面のインデックス配列があれば十分であり、ｈａｌｆ−ｅｄｇｅ、ｑｕａｄ−ｅｄｇｅといった複雑な隣接データ構造は必要でない。

図８には、最も単純な隣接グラフの例を示している。同図左に示す多角形メッシュは、辺すなわちエッジｅ_ijで接する２つの３角形Ｔ_i及びＴ_jで構成される。この多角形メッシュを記述した隣接グラフは、同図右に示すように、各３角形Ｔ_i及びＴ_jに相当する２つのノードＮ_i及びＮ_jと、両ノードを結ぶエッジｅ_ijで構成される。

また、図９には、少し複雑な隣接グラフの構成例を示している。同図左に示す多角形メッシュは、７個の３角形Ｔ₁〜Ｔ₇で構成され、Ｔ₁はＴ₂と接し、Ｔ₂はＴ₁、Ｔ₃、Ｔ₄と接し、Ｔ₃はＴ₂及びＴ₆と接し、Ｔ₄はＴ₂及びＴ₅と接し、Ｔ₅はＴ₄及びＴ₆と接し、Ｔ₆はＴ₃、Ｔ₅、Ｔ₇と接している。この多角形メッシュを記述した隣接グラフは、同図右に示すように、隣接する双方の３角形に属する辺すなわちエッジによってそれぞれの３角形に相当するノード間を結んで構成される。

なお、ノードは、初期状態では２次元イメージにおける個々のピクセルである。あるいは、多角形メッシュの最小単位の多角形（ｐｏｌｙｇｏｎ）や、３次元の立体イメージであればボクセル（ｖｏｘｅｌ）が１つのノードである。画像の統合処理が進むと、ノードは複数の多角形（あるいは、ピクセル又はボクセル）からなる多角形メッシュで構成される画像領域に成長する。図２に示した画像処理の過程では、各ノードＮ_iに関して、一意に識別するための識別情報ｉｄ（Ｎ_i）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎ_i）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎ_i）（初期値は１）を、「ノード統計情報」として保持している。各ノードが面積及び多角形の個数を保持するのは、ノードすなわち画像領域の統合の成否を統計的処理アルゴリズムに基づく判断式により判定処理するために必要な情報だからである。

隣接グラフ評価部１１２では、入力された隣接グラフの各エッジを評価してソーティングを行なう。エッジの評価は、具体的には、エッジで結ばれる各画像領域が持つ属性値を比較して比較結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする。ここで言う画像領域は、最小単位である多角形と、複数の多角形を統合した多角形メッシュとして構成される画像領域を含む。

属性値として例えば画像領域が持つ面積（画像領域に統合されたすべての多角形の面積の平均値）を用い、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順（ｉｎｃｒｅａｓｉｎｇ ｏｒｄｅｒ）にソーティングを行なう。この場合、画像領域間の面積の差が小さいほど重み値は小さくなり、後続の画像統合処理では処理順位が高くなる。

図１０には、エッジの評価を行なう処理方法を図解している。ここでは、エッジｅ_ijで接する２つの３角形Ｔ_i及びＴ_jを想定し、その隣接グラフは、同図右に示すように、各３角形Ｔ_i及びＴ_jに相当する２つのノードＮ_i及びＮ_jと、両ノードを結ぶエッジｅ_ijで構成される。ここで、多角形Ｐの面積を求める関数ａｒｅａ（Ｐ）が定義されているとすると、エッジｅ_ijの重み値Ｗ（ｅ_ij）は下式によって計算される。

あるいは、画像領域を構成する多角形の面積の他に、画像領域の法線方向、色などの画素属性情報（ＲＧＢのうちの少なくとも１成分の平均色）（但し、テクスチャを持つ多角形メッシュの場合）といった、隣接する頂点が持つさまざまな属性値の差分を用いてエッジの重みを与えることができる。

例えば、幅ｗで高さｈからなるＲＧＢカラー画像において、ｉ行ｊ列目の画素のノードをＶ_i,jとし、その識別情報をＲｅｇＩＤ（Ｖ_i,j）＝ｉ×ｗ＋ｊとおく。内側の各画素は４つの隣接ノードを持つことになり、エッジの総数ｍは２ｗｈ−ｗ−ｈとなる。そして、ノードＶ_i,jとＶ_i’,j’間の重み因子は、例えば以下の式で表すことができる。

画像領域統合処理部１１３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出し、統合処理（ｍｅｓｈ ｇｒｏｗｉｎｇ）を行なう。エッジには、エッジで結ばれる画像領域間の類似度の指標となる重みが与えられるので、重みが小さい順に統合処理を行なうことは、類似する画像領域間の統合処理を優先的に実行することに相当する。

画像領域統合処理部１１３では、ソーティングされた順に従って取り出されたエッジで結ばれる画像領域のペアに対し、統計的処理アルゴリズムに基づいて、統合すべきかどうかを判断する。具体的には、エッジの重みが上式（１）に示したように面積情報を基に算出される場合には、エッジで結ばれる２つの画像領域Ｒ_k及びＲ_lに関して、以下の統計的アルゴリズムに基づく判断式（Ｐｒｅｄｉｃａｔｅ）を満たすときに、画像領域Ｒ_k及びＲ_lを統合すべきと判定する。但し、下式において、画像領域Ｒ_kは面積Ｓ_kを持つとともにｎ_k個の多角形で構成され、画像領域Ｒ_lは面積Ｓ_lを持つとともにｎ_l個の多角形で構成されるものとする。また、Ａは多角形の最大面積とし、Ｑはセグメンテーションの粗さを制御するためのパラメータとする。

上記の判断式（３）は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものである。この現象は、統計学の分野では、中心極限定理として一般的である（母集団が任意の分布であるとしても、その母集団からの標本の大きさを増大するならば、標本平均の分布はやがて正規分布へと収束する）。

上式の右辺のＱはセグメンテーションの粗さを制御するためのパラメータである。Ｑを大きくとると右辺の値が小さくなり、判断式を満たすのが困難となる結果、画像領域の統合が抑制される。逆に、Ｑを小さい値にすると右辺の値が大きくなり、判断式を容易に満たすようになるので、画像領域の統合が促進され、より粗いメッシュ・セグメンテーション結果を得ることができる。

あるいは、エッジの重みが上式（２）に示したようにＲＧＢ色情報を基に算出される場合には、エッジで結ばれる隣接ノードＶ_i,j及びＶ_i’,j’に関して、以下の統計的アルゴリズムに基づく判断式（Ｐｒｅｄｉｃａｔｅ）を満たすときにノードを統合すべきと判定する。

但し、上式中の関数ｂ（ｘ）は以下の通りである。下式中で、ｎ_i,j並びにｎ_i’,j’は該当するノードに含まれる画素数である。また、Ｑはセグメンテーションの粗さを制御するためのパラメータとなる。

ノードは、初期状態ではデジタル画像を構成する個々のピクセル、若しくは多角形メッシュの最小単位の多角形であるが、画像領域の統合処理が進むと、複数の多角形からなる多角形メッシュで構成される画像領域に成長する。ノード統計情報では、各ノードＮ_iに関して、一意に識別するための識別情報ｉｄ（Ｎ_i）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎ_i）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎ_i）（初期値は１）などを保持するレコードが設けられている。そして、画像領域統合処理部１１３は、ノード同士を統合したときには、新しいノードを識別するための新たなｉｄが与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう。新たな識別情報の生成には、Ｕｎｉｏｎ−Ｆｉｎｄアルゴリズムを用いることができる。Ｕｎｉｏｎ−Ｆｉｎｄアルゴリズムに関しては、例えば、Ｔ．Ｈ．Ｃｏｒｍｅｎ，Ｃ．Ｅ．Ｌｅｉｓｅｒｓｏｎ，Ｒ．Ｌ．Ｒｉｖｅｓｔ共著“Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏｒ Ｄｉｓｊｏｉｎｔ Ｓｅｔｓ”（Ｃｈａｐｔｅｒ ２２，ｐｐ．４４０−４６１，Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ）を参照されたい。

微小領域処理部１１４は、画像領域の統合処理をした結果として残された微細な領域を処理する。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。

図１１には、画像セグメンテーション部１１においてメッシュ・セグメンテーション処理を行なうための処理手順の一例をフローチャートの形式で示している。

まず、画像情報編集部１１１において、処理対象となる３次元オブジェクトの画像情報を編集する（ステップＳ１）。本実施形態では、画像情報は、多角形をノードとし、多角形の辺をエッジとして構成される隣接グラフの形式で記述される（前述並びに図３を参照のこと）。

画像情報入力部１１１は、入力された隣接グラフをスキャンして、各ノードＮ_iに識別情報ｉｄ（Ｎ_i）を付与するとともに、相当する多角形の面積を求め、ノード毎の識別情報、面積、及び多角形の個数（初期値は１）をノード統計情報に登録（初期化）する。ノード統計情報を初期化する擬似プログラム・コードを以下に示しておく。但し、ｉｄ（）は引数で示されるノードの識別情報を格納する配列であり、ａｒｅａ（）は引数で示される識別情報のノードの面積を格納する配列であり、ｎ（）は引数で示される識別情報のノードを構成する多角形の個数を格納する配列である。

隣接グラフからｉ番目に取り出されたノードＮ_iに関し、識別情報ｉｄ（Ｎ_i）にｉを代入し、ノードＮ_iの面積ａｒｅａ（ｉ）に該当する多角形の面積ａｒｅａ（Ｔ_i）を代入し、多角形の個数ｎ（ｉ）に初期値１を代入する。

次いで、隣接グラフ評価部１１２では、入力された隣接グラフの各エッジを評価してソーティングを行なう（ステップＳ２）。具体的には、エッジで結ばれる画像領域間の面積の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう。画像領域間の面積の差が小さいほど重み値は小さくなり、後続の画像統合処理では処理順位が高くなる。

続いて、パラメータ設定部１１５からセグメンテーションの粗さをコントロールするためのパラメータＱを設定する（ステップＳ３）。

画像領域統合処理部１１３では、ソーティングされた順に従ってエッジを挟む画像領域のペアを取り出す（ステップＳ４）。そして、これらの画像領域が統計的アルゴリズムに基づく判断式を満たすかどうかに基づいて統合処理を行なう（ステップＳ５）。ここで用いる判断式は、画像領域を構成する多角形の面積において現れる現象である、統計的な集中不均衡から導き出されるものであり（前述）、ステップＳ３で設定されたパラメータＱを用いる。

ノード統計情報では、各ノードＮ_iに関して、一意に識別するための識別情報ｉｄ（Ｎ_i）と、該当する画像領域（最初は１つの多角形）が持つ面積ａｒｅａ（Ｎ_i）と、該当する画像領域すなわち多角形メッシュを構成する多角形の個数ｎ（Ｎ_i）（初期値は１）などを保持するレコードが設けられている（前述）。画像領域統合処理部１１３は、画像領域同士を統合したときには、新しいノードを生成して、このノードを識別するための新たなｉｄを与え、統合により新たに生成された画像領域の面積及び多角形の個数を算出して、ノード統計情報の更新処理を行なう（ステップＳ６）。

画像領域を統合し、その後にノード統計情報を更新する擬似プログラム・コードを以下に示しておく。但し、Ｍｅｒｇｅ（）は、引数で示される各画像領域を統合処理する関数である。

まず、Ｍｅｒｇｅ関数の引数で示されるノードＮ_i及びＮ_jの統合処理を行なう。そして、各ノードＮ_i及びＮ_jに対し同じ新規の識別情報ｉｄ´（Ｎ_i）＝ｉｄ´（Ｎ_j）を与えることで、両画像領域が統合され、新しいノードが生成されたことを示す。本実施形態では、新しいノードの識別情報としてＮ_i又はＮ_jいずれか一方の旧識別情報を用いる。新しいノードに識別情報を与える際に、Ｒｏｂｅｒｔ Ｅｎｄｒｅ Ｔａｒｊａｎが考案したＵｎｉｏｎ−Ｆｉｎｄアルゴリズム（前述）を使用することができる。

続いて、新しいノードの面積ａｒｅａ（ｉｄ´（Ｎ_i））に元の各画像領域の面積の和ａｒｅａ（Ｎ_i）＋ａｒｅａ（Ｎ_j）を代入するとともに、新しいノードの多角形の個数ｎ（ｉｄ´（Ｎ_i））に元の各画像領域の多角形の個数の和ｎ（ｉｄ（Ｎ_i））＋ｎ（ｉｄ（Ｎ_j））を代入する。そして、元の各ノードＮ_i及びＮ_jに対し新規の識別情報ｉｄ´（Ｎ_i）及びｉｄ´（Ｎ_j）をそれぞれ与えることで、ノード統計情報の更新処理を終える。

そして、隣接グラフ中のすべてのエッジについて処理を終えると（ステップＳ４）、微小領域処理部１１４は、画像領域の統合処理をした結果として残された微細な領域を処理する（ステップＳ７）。例えば、大きな画像領域の間あるいは内部に、統合されないまま残された微小な多角形メッシュを、判断式（３）を満たすか否かに変わらず、隣接するいずれかの画像領域に統合し、処理結果の見栄えを良くする。ここで言う微小領域は、例えばメッシュ表面全体に対して数パーセント未満の面積しかない多角形メッシュである。

上述したような統計的処理アルゴリズムに基づく画像領域の統合処理は、多角形の面積を統計処理するという簡素な計算で構成されることから高速化が可能である。例えば、一般的な計算機システム（前述）を用いて毎秒百万個程度の多角形を処理することができる。また、判断式に含まれるパラメータ値Ｑを調整することによって、画像領域同士を統合する基準を自在に設定して、所望する粗さの多角形メッシュを生成することができ、システムはスケーラビリティを持つ。

Ｑを大きくとると上式（３）の右辺の値が小さくなり、判断式（３）を満たすのが困難となる結果、画像領域の統合が抑制される（図１２を参照のこと）。逆に、Ｑを小さい値にすると上式（３）の右辺の値が大きくなり、判断式を容易に満たすようになるので、画像領域の統合が促進され、より粗いメッシュ・セグメンテーション結果を得ることができる（図１３を参照のこと）。

このように本実施形態に係る画像セグメンテーション方法によれば、判断式（３）において適正なＱの値を設定することによって、撮影画像に含まれる書画の領域とそれ以外の背景領域とを分離するようなセグメンテーションを行なうことができる。例えば、図３や図５に示したように、撮影画像に含まれる名刺やブックカバー、ＣＤ／ＤＶＤのラベルのように、テクスチャ領域を持つ書画オブジェクトについては画像セグメンテーションにより原画像から取り出すことができる。

ところが、書画が複雑なテクスチャを持つ、あるいは書画が載せられている背景もテクスチャを持つ場合には、書画の領域もセグメント化されて一体ではなくなる、あるいは背景もセグメント化されて書画の領域との区別がつかなくなることから、所望の書画の領域だけを分離して取り出すことは困難である。例えば、複雑なセマンティクスからなる写真に関しては、画像セグメンテーションを行なうと、１つの書画として領域は取り出されず、図１４に示すようにさらに複数の領域に分割されてしまうため、画像セグメンテーションには失敗する。

そこで、本実施形態では、複雑なテクスチャからなる背景を正確に処理するために、原画像から個々の書画などからなる前景領域を抜き取るセグメンテーション処理と、原画像から書画など以外の背景領域を抜き取るセグメンテーション処理を２元的に行なうという「２元的セグメンテーション（Ｂｉｎａｒｙ Ｓｅｇｍｅｎｔａｔｉｏｎ）」を実施するようにしている。また、２元的セグメンテーションには原画像を微分フィルタリングして得られるカラー・エッジ画像を用いる。

図１５には、２元的な画像セグメンテーションを行なうための概略的な処理手順をフローチャートの形式で示している。

まず、微分フィルタリングにより原画像からカラー・エッジ画像を得る（ステップＳ１１）。

次いで、部分的隣接グラフ（ｐａｒｔｉａｌ ｇｒａｐｈ）を生成してから、図１１に示した画像セグメンテーション処理を行なう（ステップＳ１２）。

既に述べたように、隣接グラフの初期状態ではノードは２次元画像における個々のピクセルであり、隣接するノード間がエッジで接続され、エッジに付与される重み因子を統計的処理アルゴリズムに基づく判断式を用いて判定処理を行ない、ノード同士の統合を繰り返していくことで、画像セグメンテーションが進行する。ステップＳ１２では、微分フィルタリングされたカラー・エッジ画像において、エッジ・カラーの帯域が所定値未満となる（例えば、書画やテクスチャなどの領域の輪郭に該当しない）ピクセルに対してのみ、他のピクセルと接続するエッジを付与して、部分的隣接グラフを作成する。隣接するピクセルであっても、エッジがなければ統合されることはなく、分離されたまま画像セグメンテーションの処理が進行していくことになる。

画像セグメンテーションが終了すると、続いて、例えば１０ピクセル以下となるような微細な領域を周辺の領域に統合してしまう（ステップＳ１３）。

ステップＳ１２及びＳ１３における画像セグメンテーション処理が終了すると、処理対象となっている画像の境界に差し掛かっている幾つかの領域を統合する（ステップＳ１４）。この処理ステップでは、画像の４隅の領域と同様である境界に接したすべての領域を統合してしまう。例えば、画像セグメンテーション処理の結果、図１６Ａに示すように背景が幾つかの領域にセグメント化されている場合であっても、境界に差し掛かっている領域同士を統合していくことで、図１６Ｂに示すように背景が１つの領域として統合される。

そして、書画などの前景の画像領域を抜き取るとともに（ステップＳ１５）、書画が載せられている背景の画像領域を抜き取る（ステップＳ１６）。

図１７Ａ〜Ｇには、画像に対して２元的画像セグメンテーションを適用した具体例を示している。図１７Ａに示す元の画像は、絨毯などのテクスチャを備えた背景の上に４枚の絵葉書が置かれた様子を撮影して得たものである。

図１７Ｂには、この元画像に微分フィルタリング処理を施して得られたエッジ・カラー画像を示している。図示の例からも分るようにエッジ・カラー画像上では、各絵葉書の周縁部分や絵柄が高帯域として表出される。

図１７Ｃには、エッジ・カラー画像を利用して部分的隣接グラフを作成し、この部分的隣接グラフに対して画像セグメンテーション処理を施した結果を示している。また、図１７Ｄには、さらに微小な領域の統合処理を行なった結果を示している。部分的隣接グラフでは、書画やテクスチャなどの領域の輪郭に該当しないピクセルに対してのみエッジが付与されているので、言い換えれば統計的処理アルゴリズムに従ってノード間の統合処理を繰り返していっても、図１７Ｄからも分るように輪郭をまたいで領域が統合されることはなく、書画やテクスチャなどの領域の輪郭はそのまま残される。

図１７Ｅには、処理対象となっている画像の境界に差し掛かっている領域を統合した結果を示している。図１７Ｄのように背景が幾つかの領域にセグメント化されている場合であっても、境界に差し掛かっている領域同士を統合していくことで、背景が１つの領域として統合される。

図１７Ｆには、図１７Ｄに示した画像から書画などの前景の画像領域を抜き取った結果を示している。また、図１７Ｇには、図１７Ｄに示した画像から背景の画像領域を抜き取った結果を示している。

領域抽出：
画像セグメンテーション処理を行なった結果、セグメント化された領域の中に、さらに他の小さな領域が含まれている場合がある。図１８に示す例では、書画としての名刺の最外周の輪郭には、名刺に印刷されたロゴマークを囲む輪郭からなる小さな領域が含まれている。しかしながら、同図からも明らかなように、別の領域の含まれる小領域は基本的には書画情報に含まれる個々のコンテンツに過ぎず、最外周の輪郭からなる領域しか必要がない。そこで、領域抽出を行なう際には、このような小領域を破棄する。

画像セグメンテーションが施された画像から領域抽出を行なう際、まず水平・垂直走査線に沿って画像を走査し、閉じた輪郭を検出する。そして、各々の閉じた輪郭に対して、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを適用して、画像を更新する。そして、最外周の輪郭からなる領域オブジェクトのみを取り出す。

上述したような２元的な画像セグメンテーションを行なう場合には、背景に該当しないすべての領域を取り出して、所望する四角形領域の集合を生成する。

そして、各々の四角形領域について、画像を走査して、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを適用する。

図１９Ａ〜Ｃには、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを用いた領域抽出処理の手順を図解している。ここでは、図１９Ａに示すように、最外周の輪郭からなる領域（ｏｕｔｅｒ ｃｏｎｔｏｕｒ）の中に、複数の小さな輪郭からなる領域（ｉｎｎｅｒ ｃｏｎｔｏｕｒ）が含まれている。

図１９Ｂに示すように、水平・垂直走査線に沿って画像を走査することによって、最外周の輪郭からなる領域が検出される。

ここで、最外周の輪郭からなる領域を取り出して、図１９Ｃに示すようにｆｌｏｏｄ ｆｉｌｌアルゴリズムを適用することによって、内側に含まれる輪郭からなる領域が誤って取り出されないようにする。

なお、ｆｌｏｏｄ ｆｉｌｌアルゴリズムの詳細については、例えば、ニールセン・フランク著“Ｖｉｓｕａｌ Ｃｏｍｐｕｔｉｎｇ： Ｇｅｏｍｅｔｒｙ， Ｇｒａｐｈｉｃｓ， ａｎｄ Ｖｉｓｉｏｎ”（Ｃｈａｒｌｅｓ Ｒｉｖｅｒ Ｍｅｄｉａ， ＩＳＢＮ： １−５８４５０−４２７−７，２００５． Ｃｈａｐｔｅｒ ２， ｐａｇｅ ２６）を参照されたい。

四角形領域探索：
最外周の輪郭からからほぼ四角形となる領域を検出したとき、この領域が遠近により変形している矩形をなしているときには（図２０Ａを参照のこと）、さらに正面から眺めた画像となるように画像変換を施す（図２０Ｂを参照のこと）。正面から眺めた画像へ変換するのは、２台のカメラやａｃｔｉｖｅ ｌｉｇｈｔｉｎｇ（プロジェクタやホログラムＡＦ）などを用いて平坦な表面を見たがるという人間の一般的な傾向に依拠するものである。

最外周となる輪郭を抽出する際に、その輪郭が四角形領域をなしているかどうかを判別する。具体的には、処理対象となっている輪郭の各ピクセルについて、接線の傾きを計算して５度毎に刻んで、２つの主な傾き（方向）を同定する（図２１を参照のこと）。

輪郭の境界部分のピクセルを、接線の傾きによって４つの集合にまとめ、個々の集合毎に直線回帰（ｌｉｎｅ ｒｅｇｒｅｓｓｉｏｎ）を行なう。そして、四角形領域を４つの半平面が交差する領域として検出する（図２２を参照のこと）。

あるいは、四角形領域を探索する代替的な手法として、ダグラス＆ポーカーによる頂点抽出アルゴリズム（ｌｉｎｅ ｓｉｍｐｌｉｆｉｃａｔｉｏｎ）を適用して、最外周の輪郭（閉じたＣ４曲線）を構成するピクセルを抽出することができる。なお、この頂点抽出アルゴリズムの詳細については、例えば、ｈｔｔｐ：／／ｇｅｏｍｅｔｒｙａｌｇｏｒｉｔｈｍｓ．ｃｏｍ／Ａｒｃｈｉｖｅ／ａｌｇｏｒｉｔｈｍ＿０２０５／（平成１８年７月２７日現在）や、Ｊｏｈｎ Ｈｅｒｓｈｂｅｒｇｅｒ及びＪａｃｋ Ｓｎｏｅｙｉｎｋ共著“Ｓｐｅｅｄｉｎｇ Ｕｐ ｔｈｅ Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ Ｌｉｎｅ−Ｓｉｍｐｌｉｆｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ”（Ｐｒｏｃ ５ｔｈ Ｓｙｍｐ ｏｎ Ｄａｔａ Ｈａｎｄｌｉｎｇ，１３４−１４３（１９９２））などを参照されたい。

そして、このようにして四角形領域を抽出した後、元の線分群とのハウスドルフ距離（Ｈａｕｓｓｄｏｒｆｆ ｄｉｓｔａｎｃｅ）を計算して、該距離が所定値以内であれば抽出した領域をまさしく四角形であるとして受け容れる。

なお、Ｈａｕｓｓｄｏｒｆｆ ｄｉｓｔａｎｃｅは、距離尺度を用いて形状の照合を行なう周知の手法である。

アスペクト比推定：
最後に、検出した四角形領域を正面から眺めた画像となるように逆射影変換を行なうとともに、アスペクト比を調整する。

矩形画像を逆射影する方法は数多存在し、本発明の要旨は特定の方法には限定されない。

アスペクト比が与えられている場合には、寸法効果のみを考慮すればよい。

例えば、式ａ＝（ｈ１＋ｈ２）／（ｗ１＋ｗ２）に基いて、アスペクト比の平均を計算する。また、所定のアスペクト比のセットの中から最も近いものを見つけ出す。例えば、Ａ４や写真、葉書であればアスペクト比は１０：１５、名刺であれば５．５：９．１である（書画が９０度回転している場合には、アスペクト比はこれらの逆数となる）。

矩形画像を再マッピングする処理手順について、以下で説明しておく。

ａ×ｓ²が四角形領域内の画素数と等しくなるような寸法因子ｓを選択する（但し、ａはアスペクト比）。あるいは、逆射影変換された２点間の距離が所定値以内（例えば、１．０又は１．４１４）に収まるように寸法因子を選択する。

画像変換は、“ｈｏｍｏｇｒａｐｈｙ”若しくは“ｃｏｌｌｉｎｅａｃｔｉｏｎ”とも呼ばれ、８個の係数で決定される３×３の同次行列Ｈで表される。

四角形領域のピクセルｐがアスペクト比ａを以って縮尺が調整されたピクセルｐ´にマッピングされたとする。ｐとｐ´が同次座標で、ｐ＝（ｘ，ｙ，ｚ）、ｐ´＝（ｘ´，ｙ´，ｚ´）であれば、ｐ´＝Ｈｐである。同次でない場合はｐ´＝（ｘ´／ｗ´，ｙ´／ｗ´）である。

そして、図２３に示すように、合成した画像を元の画像に逆方向でマッピングする。逆方向でマッピングされたピクセルＰは、Ｐ＝Ｈ^-1ｐ´で表される。

なお、逆方向マッピングなどに関しては、例えば、Ｆｒａｎｋ Ｎｉｅｌｓｅｎ著“Ｖｉｓｕａｌ Ｃｏｍｐｕｔｉｎｇ：Ｇｅｏｍｅｔｒｙ，Ｇｒａｐｈｉｃｓ，ａｎｄ Ｖｉｓｉｏｎ”（Ｃｈａｒｌｅｓ Ｒｉｖｅｒ Ｍｅｄｉａ，ＩＳＢＮ：１−５８４５０−４２７−７，２００５ Ｃｈａｐｔｅｒ ３，ｐ１２７、Ｃｈａｐｔｅｒ ４，ｐ２０３）を参照されたい。

以上、特定の実施形態を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施形態の修正や代用を成し得ることは自明である。

本発明に係る画像処理技術は、デジタルカメラから撮影画像を取り込んで画像の加工を行なうパーソナル・コンピュータなどの情報機器や、デジタルスチルカメラ本体、若しくはデジタルカメラを搭載したさまざまな機器に搭載することができる。

本発明に係る画像処理技術によれば、デジタルカメラの撮影画像などに含まれる、名刺や絵葉書、本の表紙といった複数の書画を前景領域として他の背景領域から分離して取り出すことができる。また、取り出した個々の書画の画像をさらに正面から撮影したように射影変換したり、アスペクト比を調整したりして、元の書画に近い画像オブジェクトに復元することができる。これらの画像オブジェクトは、コンテンツとして再利用可能であり、さらに書画に含まれるテキストを文字認識して、得られた文字情報を画像オブジェクトの保管・整理に活用したり、文字情報を基に情報検索やその他のサービスを提供したりすることも可能である。

要するに、例示という形態で本発明を開示してきたのであり、本明細書の記載内容を限定的に解釈するべきではない。本発明の要旨を判断するためには、特許請求の範囲を参酌すべきである。

図１Ａは、複数の書画画像を含んだデジタル画像の一例を示した図である。 図１Ｂは、図１Ａに示したデジタル画像に含まれる個々の書画画像を抽出した様子を示した図である。 図２は、画像処理機能の構成を模式的に示したブロック図である。 図３は、複数の名刺を撮影したデジタル画像に画像セグメンテーション処理を施した画像から矩形領域を認識して、個々の名刺の画像を再マッピングする様子を示した図である。 図４Ａは、撮影モード下で撮影したデジタル画像の表示例を示した図である。 図４Ｂは、書画表示モード下で撮影したデジタル画像の表示例を示した図である。 図５Ａは、絨毯の上に散在する書籍を撮像したデジタル画像を示した図である。 図５Ｂは、図５Ａに示したデジタル画像から抽出した書画画像を示した図である。 図５Ｃは、図５Ｂに示した書画画像に含まれる文字列情報を基に情報検索を行なった結果を示した図である。 図６は、抽出された四角形領域をジャケットが持つアスペクト比の矩形領域に再マッピングした様子を示した図である。 図７は、画像セグメンテーション部１１の内部構成を示した図である。 図８は、最も単純な隣接グラフの例を示した図である。 図９は、少し複雑な隣接グラフの構成例を示した図である。 図１０は、エッジの評価を行なう処理方法を説明するための図である。 図１１は、画像セグメンテーション部１１においてメッシュ・セグメンテーション処理を行なうための処理手順を示したフローチャートである。 図１２は、画像領域の統合が抑制された場合の画像セグメンテーションの結果を示した図である。 図１３は、画像領域の統合が促進された場合の画像セグメンテーションの結果を示した図である。 図１４は、複雑なセマンティクスからなる写真に関して画像セグメンテーションに失敗した様子を示した図である。 図１５は、元的な画像セグメンテーションを行なうための概略的な処理手順を示したフローチャートである。 図１６Ａは、背景が幾つかの領域にセグメント化されている様子を示した図である。 図１６Ｂは、図１６Ａに示した背景が１つの領域として統合されている様子を示した図である。 図１７Ａは、絨毯などのテクスチャを備えた背景の上に４枚の絵葉書が置かれた様子を撮影して得た元画像を示した図である。 図１７Ｂは、図１７Ａに示した元画像に微分フィルタリング処理を施して得られたエッジ・カラー画像を示した図である。 図１７Ｃは、図１７Ｂに示したエッジ・カラー画像を利用して作成された部分的隣接グラフに対して画像セグメンテーション処理を施した結果を示した図である。 図１７Ｄは、図１７Ｃに示した画像に対しさらに微小な領域の統合処理を行なった結果を示した図である。 図１７Ｅは、図１７Ｄに示した画像の境界に差し掛かっている領域を統合した結果を示した図である。 図１７Ｆは、図１７Ｄに示した画像から書画などの前景の画像領域を抜き取った結果を示した図である。 図１７Ｇは、図１７Ｄに示した画像から背景の画像領域を抜き取った結果を示した図である。 図１８は、書画としての名刺の最外周の輪郭に、名刺に印刷されたロゴマークを囲む輪郭からなる小さな領域が含まれている様子を示した図である。 図１９Ａは、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを用いた領域抽出処理の手順を説明するための図である。 図１９Ｂは、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを用いた領域抽出処理の手順を説明するための図である。 図１９Ｃは、ｆｌｏｏｄ ｆｉｌｌアルゴリズムを用いた領域抽出処理の手順を説明するための図である。 図２０Ａは、四角形領域を探索する処理手順を説明するための図である。 図２０Ｂは、四角形領域を探索する処理手順を説明するための図である。 図２１は、最外周となる輪郭の輪郭が四角形領域をなしているかどうかを判別する処理手順を説明するための図である。 図２２は、最外周となる輪郭の輪郭が四角形領域をなしているかどうかを判別する処理手順を説明するための図である。 図２３は、合成した画像を元の画像に逆方向でマッピングする様子を示した図である。 図２４は、本発明の一実施形態に係るデジタルスチルカメラの構成を示した図である。

符号の説明

１１…画像セグメンテーション部
１２…領域抽出部
１３…四角形領域探索部
１４…アスペクト比推定部
１１１…画像情報編集部
１１２…隣接グラフ評価部
１１３…画像領域統合処理部
１１４…微小領域処理部
１１５…パラメータ設定部
２００…デジタルスチルカメラ
２１１…撮像素子
２１２…前処理部
２１３…ＣＤＳ／ＡＧＣ／ＡＤＣブロック
２１４…タイミング・ジェネレータ
２１５…Ｖドライバ
２１６…カメラ・デジタル信号処理部
２１７…カメラ信号処理部
２１８…解像度変換部
２１９…画像コーデック処理部
２２０…メモリ制御部
２２１…表示制御部
２２２…メディア制御部
２２３…バス・インターフェース・ユニット
２２４…メモリ装置
２２５…モニタ・ディスプレイ
２２６…記録メディア
２２７…制御部
２２８…操作部
２２９…ＣＰＵ
２３０…ＲＡＭ
２３１…ＥＥＰＲＯＭ

Claims (19)

1. 画像に含まれる書画情報を抽出する画像処理装置であって、
   入力画像を領域毎に分割する画像分割手段と、
   分割された領域の輪郭に基づいて書画情報を含んだ書画領域を抽出する領域抽出手段と、
   を具備することを特徴とする画像処理装置。
2. 前記領域抽出手段により抽出された書画領域から四角形を検出する四角形検出手段と、
   該検出した四角形領域を正面から眺めた画像となるように逆射影変換するとともに、アスペクト比を調整する画像変換手段と、
   をさらに備えることを特徴とする請求項１に記載の画像処理装置。
3. 前記画像分割手段は、
   ピクセル（若しくはピクセルの塊からなる多角形）からなるノードで構成される入力画像から、隣接するノード間をエッジで接続する隣接グラフを生成する隣接グラフ生成手段と、
   エッジで結ばれる各ノードが持つ属性値を比較した結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価手段と、
   ソートされた順に従ってエッジを挟むノードのペアを取り出し、ノード同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、ノードの統合処理を行なう統合処理手段を備え、
   入力画像を、それぞれのノードからなる複数の画像領域に分割する、
   ことを特徴とする請求項１に記載の画像処理装置。
4. 前記統合手段により画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理手段をさらに備える、
   ことを特徴とする請求項３に記載の画像処理装置。
5. 前記隣接グラフ評価手段は、隣接グラフのエッジで結ばれる各ノードが持つ属性値の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう、
   ことを特徴とする請求項３に記載の画像処理装置。
6. 前記画像領域統合処理手段は、ノードを構成する画像領域の面積における集中不均衡現象から導き出される判断式に基づいて、隣接グラフのエッジで結ばれるノード同士を統合すべきかどうかを判断する、
   ことを特徴とする請求項３に記載の画像処理装置。
7. 前記画像分割手段は、原画像から個々の書画などからなる前景領域を抜き取る第１の画像分割処理と、原画像から書画など以外の背景領域を抜き取る第２の画像分割処理を２元的に行なう、
   ことを特徴とする請求項３に記載の画像処理装置。
8. 入力画像を微分処理する微分処理手段をさらに備え、
   前記隣接グラフ生成手段は、前記微分処理手段から出力される微分画像のうち帯域が所定値未満となるピクセルに対してのみ、他のピクセルと接続するエッジを付与して、部分的隣接グラフを作成し、
   前記統合処理手段は、境界に差し掛かっているノード同士を統合処理して、背景を１つの領域として統合して、書画からなる前景の画像領域を抜き取るとともに、書画が載せられている背景の画像領域を抜き取る、
   ことを特徴とする請求項７に記載の画像処理装置。
9. 前記領域抽出手段は、別の領域の含まれる小領域を破棄し、最外周の輪郭からなる領域のみを抽出する、
   ことを特徴とする請求項１に記載の画像処理装置。
10. 画像に含まれる書画情報を抽出する画像処理方法であって、
    入力画像を領域毎に分割する画像分割ステップと、
    分割された領域の輪郭に基づいて書画情報を含んだ書画領域を抽出する領域抽出ステップと、
    を具備することを特徴とする画像処理方法。
11. 前記領域抽出ステップにおいて抽出された書画領域から四角形を検出する四角形検出ステップと、
    該検出した四角形領域を正面から眺めた画像となるように逆射影変換するとともに、アスペクト比を調整する画像変換ステップと、
    をさらに備えることを特徴とする請求項１０に記載の画像処理方法。
12. 前記画像分割ステップは、
    ピクセル（若しくはピクセルの塊からなる多角形）からなるノードで構成される入力画像から、隣接するノード間をエッジで接続する隣接グラフを生成する隣接グラフ生成ステップと、
    エッジで結ばれる各ノードが持つ属性値を比較した結果に基づいて重み因子をエッジに付与し、重み値に基づいて隣接グラフ中のエッジをソーティングする隣接グラフ評価ステップと、
    ソートされた順に従ってエッジを挟むノードのペアを取り出し、ノード同士を統計的処理アルゴリズムに基づいて統合すべきか否かを評価し、ノードの統合処理を行なう統合処理ステップを備え、
    入力画像を、それぞれのノードからなる複数の画像領域に分割する、
    ことを特徴とする請求項１０に記載の画像処理方法。
13. 前記統合ステップにおいて画像領域の統合処理をした結果として残された微細な領域を処理する微小領域処理ステップをさらに備える、
    ことを特徴とする請求項１２に記載の画像処理方法。
14. 前記隣接グラフ評価ステップでは、隣接グラフのエッジで結ばれる各ノードが持つ属性値の相違をエッジの重み値として与えて、重み値の小さい順にソーティングを行なう、
    ことを特徴とする請求項１２に記載の画像処理方法。
15. 前記画像領域統合処理ステップでは、ノードを構成する画像領域の面積における集中不均衡現象から導き出される判断式に基づいて、隣接グラフのエッジで結ばれるノード同士を統合すべきかどうかを判断する、
    ことを特徴とする請求項１２に記載の画像処理方法。
16. 前記画像分割ステップでは、原画像から個々の書画などからなる前景領域を抜き取る第１の画像分割処理と、原画像から書画など以外の背景領域を抜き取る第２の画像分割処理を２元的に行なう、
    ことを特徴とする請求項１２に記載の画像処理方法。
17. 入力画像を微分処理する微分処理ステップをさらに備え、
    前記隣接グラフ生成ステップでは、前記微分処理ステップにより得られる微分画像のうち帯域が所定値未満となるピクセルに対してのみ、他のピクセルと接続するエッジを付与して、部分的隣接グラフを作成し、
    前記統合処理ステップでは、境界に差し掛かっているノード同士を統合処理して、背景を１つの領域として統合して、書画からなる前景の画像領域を抜き取るとともに、書画が載せられている背景の画像領域を抜き取る、
    ことを特徴とする請求項１６に記載の画像処理方法。
18. 前記領域抽出ステップでは、別の領域の含まれる小領域を破棄し、最外周の輪郭からなる領域のみを抽出する、
    ことを特徴とする請求項１０に記載の画像処理方法。
19. 画像に含まれる書画情報を抽出するための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
    入力画像を領域毎に分割する画像分割手順と、
    分割された領域の輪郭に基づいて書画情報を含んだ書画領域を抽出する領域抽出手順と、
    前記領域抽出手順において抽出された書画領域から四角形を検出する四角形検出手順と、
    該検出した四角形領域を正面から眺めた画像となるように逆射影変換するとともに、アスペクト比を調整する画像変換手順と、
    を実行させることを特徴とするコンピュータ・プログラム。