(57)【要約】  ホモトピー変換を使用して、特に水源変換を使用して、１つのイメージの複数のピクセルの赤、緑、および青の成分、または１つのイメージの複数のピクセルの全ての他の属性の集合で形成される特性空間内において、色の一意の数が上記イメージに関して発見される。各色はラベルを与えられ、次に上記イメージは複数の均一ラベルの領域に分割される。次に各分割部分の色と特性は変更されて、物体を識別するために使用される。これは任意のスケーラブルな（整数か実数のどちらか）データ集合にも応用可能である。【特許請求の範囲】
【請求項１】
コンピュータを使用して、イメージを色に基づいた少ない数の同質の領域に分割する方法であって、
１．元のイメージをデジタル化して、デジタル化されたイメージファイルを生成するステップであって、上記のイメージファイルは各々が上記イメージ内の点における色の値を表すｍ個１組の量の、ｎ次元マップであるステップ、
２．デジタル化された上記イメージファイル内の色の度数のｍ次元のヒストグラムを作成するステップ、
３．高さにより上記ヒストグラムのエントリを分類するステップ、
４．ラベルのつけられていない点により得られる最も高いヒストグラムの値をもつ点を選択するステップ、
５．この点について、
i．もし以前ラベルのつけられた点に隣接していないならば、新しいラベルと測地線距離０を割り当て、かつ
ii．もし同じラベルをもつ隣接する点があれば、このラベルを割り当て、測地線距離を、ヒストグラムの値が同じ場合、同じ値とし、その他の場合、上記最も高いヒストグラムの値をもつ上記隣接する点がもつ最小値より１大きい値にすることにより、
この点へ一意のラベルを割り当て、
iii．もし異なるラベルをもつ隣接する点がある場合は、この点を無視する
ステップ、
６．同じ高さをもつ他の全ての点を発見し、それらの点をステップ５により処理するステップ、
７．このレベルの（ステップ５のiiiで無視された）残りの各点（すなわち、一意に接続されていない各点）へ、最小値の測地線距離をもつその隣接する点のいずれかのラベルを割り当てるステップ、
８．特性空間内の全ての点がラベルを割り当てられるまでステップ４からステップ７を反復するステップ、
９．上記イメージ内の各ピクセルへ、上記特性空間内の成分の値の組み合わせに関して発見された上記ラベルを割り当てるステップ、
１０．均一な複数のラベルの各領域に分割部分を特定する一意のラベルを与えるステップ、
を備える方法。
【請求項２】
イメージ分割のための方法であって、
１．データのＮ次元のマップからなるイメージを作成またはデジタル化するステップであって、上記データの各要素がＭ次元の色データ（Ｍ個の色成分の各々のイメージ内の点における値）を含むステップ、
２．任意で、上記イメージをその元の色空間からそれと同じまたは異なる次元（Ｍ）をもつもう１つの色空間へ変換し、
および／または、元のデータからアルゴリズムで生成される更なる（Ｍを増加させる）成分、例えば「質感」、を加え、
および／または、各成分を同じまたは異なる量で尺度を変えて、帯内の一意の値の数を変更する
ステップ、
３．成分の値（「色」）の一意の組み合わせの各々の度数のヒストグラムを作成するステップであって、好ましくはハッシュ表を作ることにより、そのハッシュ表内で、もしその成分の値が特定の数の次元内で１異なると、上記ヒストグラムの複数の要素が隣接しているステップ、
４．任意で、ヒストグラムの値の順で、大きい値を最初に、ヒストグラムのエントリをバケットに分類するステップ、
５．最高値から始まって低い値へ下がりながら発見された各ヒストグラムの値に関して、上記ヒストグラムの値をもつ色の集合ＳＣを考慮して、ステップ６およびステップ７を実行するステップ、
６．ＳＣ内の各色Ｃに関し、｛
もし既にクラスをもった隣接する色がないと、新しいクラスを生成し、このクラスでは、この色は、測地線距離０で、種子点となり、
または、
もし隣接する全ての点が１つのクラスを共有していると：
この要素を上記クラスへ加え；最も短い測地線距離の隣接する要素を選択することにより、この要素の測地線距離を決定し、もし複数の点が同じ測地線距離をもっていたら、同じ距離を割り当てる、そうでなければ上記距離＋１を割り当て、
または
もし２以上のクラスの隣接する点があるときは、この時点ではクラスを割り当てないままにしておき、
｝
このヒストグラムのレベルにおいては、１つより多いクラスの隣接する点をもつ残りの色のみを残しておくステップ、
７．クラスを割り当てられていないＳＣ内の残りの色Ｃの各々に関して｛
最小の測地線距離をもつ隣接する点の上記クラスへＣを加え、もしそれらが同じヒストグラムの値をもっていたら、同じ距離を割り当てる、また、その他の場合は、上記距離＋１を割り当て、
｝
上記イメージ内の全ての色が１つのクラスを割り当てられるステップ、
８．任意に、上記イメージの要素の少ない数しか表さない複数のクラスを、近くのクラス（複数の場合あり）へ割り当て直すことにより、クラスを取り除くステップ、
９．任意に、上記イメージ内の各要素に、その色が属しているクラスのラベルを割り当てるステップ、および
１０．任意に、全てが同じクラスの色を持つ上記イメージの複数の要素の（イメージ空間内で）各々の連続した集合に一意のラベルを割り当てて、その領域を特定するステップ
を備えるイメージ分割のための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
近年、コンピュータ支援イメージ処理の分野において大きな進歩があった。イメージの創作および操作は、グラフィックアート分野、産業監視、および測量に従事する多くの者にとって朗報になることが証明されたが、すでに存在しているイメージを処理可能な形式へレンダリングする初期の段階には、まだ問題が存在する。コンピュータ化されたイメージを確保する伝統的なアプローチは、写真の原画をスキャンして、上記イメージの多数の部分、いわゆるピクセルの性質を表わすデータが格納されているファイルを形成する。各ピクセルは、色と強度に対応する多数のパラメータにより特徴づけられ、上記ファイルが、上記ファイルが適切なプログラムに呼び出された時に画面上に上記イメージが表示されるように各ピクセルの位置に関係するデータを含む。最近では、スキャンする工程は、いわゆるデジタルカメラの発達により、補われるようになり、デジタルカメラは、メージファイルを直接生成する。
【背景技術】
【０００２】
上記イメージを処理して所望の形式にするために、また、上記イメージの背景以外の部分に影響せずに、背景色のカラーバランスを変更するために、上記イメージは、例えば背景および表示対象に対応する異なる部分へ分解される必要がある。この分割工程は、時間を浪費し、高度な技術を必要とする。この工程を自動化する試みはなされた。しかし、人間にはわかる、知的に理解可能なイメージの複数部分が、単に、コンピュータにとって容易には識別不可能であるので、試みは適切にないしは容易にいかなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、人間の介入にほとんど依存しない情報を生成するイメージファイル内の上記データを解析する方法の提供を得ようとする。本発明はもしデータ集合内のパターンや構造があるならば、そのようなパターンや構造が現われ、使用されることを可能にして、上記データを記述し、かつ、そのようなパターンが再現するならば予測をしようとする。
【課題を解決するための手段】
【０００４】
本方法は現在の理論や知識に基づいた重ね合わされた仮定に依存しない。これはコンピュータシステムの使用により実現され、外の世界の映像のインポートまたは適切なカメラシステムからの直接入力により、上記コンピュータシステムが上記外の世界に関するデータを受信または収集し、次に先入観なしでそのデータを解析することを可能にする。こうして、このシステムは外の世界の理解に到達可能であり、所望ならば、外の世界についての正確な予測を可能にできる。このようなシステムは人工知能の基礎を形成するものとしてみることができる。
【０００５】
本発明に従って、デジタル化されたイメージは、主請求項に記載の方法により色に基づいて、分割される。１つの代替アプローチが請求項２に記載されている。
【０００６】
本発明は、本質的に、イメージのピクセルの色成分により生成される特性空間内において、ホモトピー（ｈｏｍｏｔｏｐｉｃ）変換、特に水源（ｗａｔｅｒｓｈｅｄ）変換を使用する。これらは、例えばＨＬＳ（色相、明度、彩度）、ＲＧＢ（赤、緑、青）、ＣＹＭＫ（シアン、黄色、マゼンタ、黒）の多くの色空間で表現される。イメージは元の色空間で処理されてもよく、または処理前に異なる色空間に変換されてもよい。さらに、例えば、各ピクセルについて質感に関する解析を実行することにより、情報の追加のチャネルがデータからアルゴリズムで生成でき、これは、分類工程の中に含まれる。さらに、全ての次元で同時に一度のみ分類を実行するよりも、数回の分類をそれぞれ特性空間のサブ空間で実行し、分割処理では上記分類のいくつかないしは全てを参照するという選択肢がある。これにより、特性空間内の一意の数の色、色の複数のグループ、または特性空間内の複数の隣接する領域（以下で「クラス」という。）がその色に対して見出されることが可能になる。各クラスはラベルが与えられ、次に、イメージは均一ラベルの複数の領域に分割される。各分割部分の色は、例えば、物体を特定するために変更できて、または、使用できる。
【０００７】
この方法は、任意のスケーラブルな（整数または実数のいずれかの）データ集合にも応用可能である。ヒストグラムの次元の通常の数は３であるが、所望ならばより多いまたはより少ない次元を使用することはもちろん可能である。しかし、３つの次元より多くを使用することは、必要な解析を実行するために必要なコンピュータ処理能力およびコンピュータメモリの量を増加させる。注目すべきは、この方法を使用すると、格子の分解能および格子の接続性は、両方とも発見される集合の数（後で定義されるように）に影響することである。
【発明を実施するための最良の形態】
【０００８】
上記方法の背景にある上記理論を理解するために、以下の定義を心にとめておく必要がある。
「格子」とは、ノードおよびノード間の接続の集合をいう。ユークリッド格子は正方形格子目パターンであり、上記ノードが交差であり、その間の線が上記接続を表す。単純な２次元ユークリッド格子では、接続性を定義するのに２つの可能な方法がある。（ａ）４接続格子は、１つの次元上で１だけ異なるときのみノードを隣接できることからなる。これは格子上の各ノードが４つの隣接ノードをもつことを意味し、それより名付けられる。（ｂ）８接続格子は、任意の数の次元上で１だけ異なるとき（ノードが２つの次元で１異なる場合も含む）ノードを隣接できる。こうして、接続性は対角線のノードも含み、この場合８つの最も近い隣接するノードがあり、それより名付けられる。任意の格子およびその接続性の特性は、任意の数の次元の場合も、２次元の場合を拡張することにより定義可能である。
「測地線距離」格子上の任意の距離は、隣接したノードの連続したストリングに沿って計測されねばならない。隣接するノードのストリングはパスとして知られている。任意の２つのノードの間の測地線距離は、２つのノード間の全ての可能なパスの中で、上記のパスであり、最短距離をもつ。
「集合」とは、複数のノードの集まりであって、複数のノードの各々が、グループ内の少なくとも１つの他のノードに隣接している。それ故、格子上の隣接するノード間を移動するだけで、上記集合内の任意の成分から、他の任意の成分へも到達可能である。
「ジョーダンの補助定理」もしパスにより以前接続されたノードが接続されたままで、パスによって接続されていないノードが接続されていないままならば、処理（例えばノードを集合に加えること／取り除くこと）はホモトピーを保つ。それ故、もし操作の前にｎ個の集合が存在したとすると、操作の後もｎ個の集合のみがなければならない。ホモトピー条件を満たす処理は、排他的に使用された場合、もし与えられた格子上に表されたデータ集合内にｎ個の集合があると、この処理の適用の終わりには、ｎ個のみの集合が「発見され」すなわち現れることが保証される。
「単調」とは、一連の数において、各数字が先行するものより大きい（小さい）またはより大きい（より小さい）ことをいう。
「降下集合（Ｆａｌｌ−ｓｅｔ）」これは、ノードの数値が高い値から始まって単調に変化するパスである。もしパスがその高い端から低い端へ進むと、山腹を流れ落ちる水の例えにより、これは水がどのように流れるか説明する。水が流れ込まず水が流れ出すノードは「水源」を定義する。従って、これらのノードを発見する複数のアルゴリズムは「水源」アルゴリズムとして知られている。
【０００９】
本発明の方法は、降下集合、測地線距離、およびジョードンの補助定理の考えに基づいている。ジョードンの補助定理は、ホモトピー（集合の数）が保存されるような集合の正規の変換を与える。
集合の定義：連続して接続されている全ての点をいう。
連続性は格子上の隣接と同等であると定義される。それ故、集合は、集合の成分である点のストリングにより接続された全ての点である。上記補助定理は、もし以前接続されていない点が接続され（または以前接続されていた点が切り離され）れば、点が加えられる（または取り除かれる）ことを記述する。この制限を満たす変換はホモトピーを維持し、すなわち、集合の数を一定に保つ。種子点として、集合に属していなければならないヒストグラムの最も高い点を選択することにより、次に、より低くて種子点に一意に接続された（それ故ジョーダンの補助定理を満たす）隣接点を上記集合へ加えることにより、種子点のための降下集合が発見され、定義される。独立していて一意に定義可能な他の種子点のアルゴリズムによる識別は、もし特性空間内にｎ個の集合（グループ、クラス）があるとｎ個のみが発見されることを保証する。上記集合内の全ての点について種子点からの上記測地線計測を使用することにより、複数の集合に接続されているかもしれず、それ故境界点である格子上の複数の点は、上記グループの種子点からの測地線距離に関して、最も近いグループに割り当てられる。
【００１０】
それ故、この処理は、任意のイメージの中の同質の色の数を発見できる。一度上記グループの数と正確な定義が知られると、元のイメージは同質の複数の領域に分割可能である。
【００１１】
本発明の方法は、統計的決定理論を使用した従来のアプローチから、定性的に区別される方法での分割を提供する。統計的決定理論では、上記データ内の上記集合の数および数学的記述、または特性空間内の分布は知られていると仮定される。さらに、各集合の形状は数学の連続関数として表現可能であると仮定される。これら全ての仮定は完全に間違いである。イメージ内の色の数を計算する合理的な手順はない。特性空間内の集合の形状（ヒストグラム）は、外形も側面も決して各面の大きさと形が等しくはない。上記データは離散していて、どの観点でもそのようなデータは連続的には扱えない。伝統的な上記統計的決定理論アプローチは、せいぜい、特性空間内の実際の分布のとても貧弱な近似であって、これはピクセルを集合に割り当てるとき必然的に誤りを生じる。対照的に、本発明による方法はデータを正確に記述し、それ故それ以上改良されても、正確さにおいて単に同等である。「任意の１つのイメージ内においていくつの集合と色があるか？」という問題の解決法を発見可能なのはこの方法のみである。任意の与えられた分解能および格子の接続性の答えは一意である。
【００１２】
少なくとも間隔のスケール上で計測されたデータ集合の複数の例は、特性空間内で表せて、その特性空間の軸はデータの次元である。一度データがそのように表されると、上記水源アルゴリズムは、上記データの独立した集合（クラス、グループ）の数、サイズおよび形を正確に示すために使用できる。これは知識の基本である。一度、特性空間のその構成する集合（クラス）への分割が完了すると、各集合に重要性が割り当てられることと、特定の集合に属する点に基づいて予測をすることが残るのみである。こうして、水源アルゴリズムは、予測の目的のためデータを記述する正確な方法である。この方法は任意のデータ集合を分割する（あるピクセルがどの色グループに属するのかを決定する）ためにも使用可能である。その成分の数、形状、大きさに関して、任意のデータ集合を正確に記述可能である点で、この方法は一意である。どの他の方法も決して水源解決法よりも優れていず、せいぜい複製物である。本発明で使用された水源アルゴリズムは、以下の特徴をもつ任意のデータ集合にも応用可能である。
１．要素（ｉｎｓｔａｎｃｅ）の数が多い。
２．データ集合内の各要素の成分の尺度が全て少なくとも間隔がある。
これらは厳しい制約ではないので、この方法は多くのデータ集合に適用可能である。
【００１３】
本発明は以下の例により示される。ピクセル化されたイメージを表す任意の現実のデータ集合とも比較して微視的なデータ集合に関して、この例は空間を保存し、理解の明瞭さを助ける。しかし、この例は、この方法がどのように適用されるかを説明するのに役立つと信じる。この例は、単純な用語で処理を説明する。しかし、実際の具体化では、全ての処理は、適切なコンピュータプログラミングを使用して実行される。
【００１４】
例
５×５ピクセルの小さなイメージがあり、各ピクセルの赤および緑の値がわかっていると仮定する。これは２次元問題を定義する。２色、すなわち赤と緑の値により定義される特性空間内で、隣接する点のパターンに純粋に基づいて，そのイメージをその構成の色に分割したい。表１および表２はイメージの成分、すなわち、１つは赤色の成分で、もう一つは緑色の成分を示す。
【表１】
2005513632.tif 000002
表１：赤色の成分
【表２】
2005513632.tif 000003
表２：緑色の成分
【００１５】
第１のステップは以下の順序で
ハッシュ表位置、赤色の成分、緑色の成分、これら２つの成分をもつピクセルの数、クラス（集合）のラベル
を含むハッシュ表（散在したデータを格納するもっとも経済的な方法）を作ることである：
この例のハッシュ関数は
Ｌ＝Ｍｏｄ（（Ｒ＋７＊Ｇ）：１３）
である。ここでＲは赤色の値、Ｇは緑色の値、そしてＬはＲ＋７＊Ｇの結果を１３で割った後の余りである。（１、７、および１３は素数である：データを格納するハッシュ技法は素数の時最もよく機能する。ハッシュ関数の素数の選択は格納される値の範囲に依存する。）各ピクセルは順番に処理され、組み合わせが発生する時、値をインクリメントされる各組み合わせエントリでハッシュ表が作られるので、最後の値のための組み合わせのヒストグラムの高さを与える。各ピクセルがハッシュ表に入力されるとき、その赤色の成分および緑色の成分がチェックされる。もし成分のどちらかが異なると、空のフィールドが見つかるまでハッシュ表のキーがインクリメントされて、そのフィールドにその色が加えられる。結果はハッシュ表１に示される。
【表３】
2005513632.tif 000004
ハッシュ表１
【表４】
2005513632.tif 000005
ハッシュ表２
【表５】
2005513632.tif 000006
ハッシュ表３
【００１６】
特性空間は、４接続のユークリッド格子と考えられる。上記ハッシュ表は、４列目（ヒストグラムの高さ）を使用して最も高い値が表の最初にあるように整理し直される。結果はハッシュ表２に示される。もしハッシュ表の２つのエントリが、その赤色または緑色の成分で（両方ではない）１つだけ異なるとすると、その２つは隣接していると考えられる。もし候補エントリが、すでに存在しているグループに属していると考えられ、上記候補エントリが上記グループの１つのエントリに隣接していて、他のグループに属しているどのエントリにも隣接していないとすると、上記グループに追加可能である。この手続きはジョーダンの補助定理に従う。
【００１７】
表の最初から始めて、各色のヒストグラムの値を表す列４は、スキャンされて、最大値を発見する。最大値は４であると分かり、２つのそのような考慮すべきフィールドがある。これらは１つの次元のみ色が１異なり、それ故隣接していて、同じラベルｇを与えられる。ハッシュ表の列４は、ヒストグラムの値３を含む全てのフィールドについてスキャンされる。それらは２つある。第１の３（表１の位置１０）は、複数の４のうちの１つ（表１の位置３）から緑色の成分のみ１異なり、それ故同じグループｇに割り当て可能である。第２の３（表１の位置１２）は、すべてのすでに存在しているエントリから１より多く異なり、それ故この位置はｇのラベルの位置に隣接しておらず、よって他の集合の一部であって、ラベルｒを与える。もう考慮する３はなくて、次にハッシュ表１の列４が複数の２に関してスキャンされる。それらは４つあり、すなわち位置４、位置９、位置１０、および位置１３である。位置４にある２は位置３にある４から１つの次元に関して１異なるので、ラベルｇを割り当てられる。位置９のエントリは位置９のエントリは位置１１のエントリに隣接していて、位置１０のエントリは位置３のエントリに隣接していて、位置１３のエントリは位置１２のエントリに隣接している。これらの位置の１つも１つより多くのグループに属している位置に隣接していないので、それぞれジョーダンの補助定理に反せずに追加可能である。各々適切なラベルが与えられる。ヒストグラムの値２の全てのエントリは説明したので、複数の１が列４に位置する。それらは５つあり、すなわちハッシュ表１の位置２、位置５、位置６、位置７、および位置８であって、位置２エントリは２つ、ハッシュ表１の位置３および位置９のエントリに隣接している。これら２つは同じラベルをもつので、位置２のエントリは上記ラベルを割り当て可能である。位置５のエントリは、すでにラベルの与えられたどの位置のエントリにも隣接していないので、ラベルを与えないままにしておく。位置６、位置７、および位置８は、すでにラベルを与えられた位置に隣接したエントリをもっているので、これらと同じラベルを与えられる。位置５を再度検証すると、今度は、そのエントリは２つの位置、位置８と位置６のエントリに隣接していることがわかる。これら２つの位置は同じラベルをもっているので、位置５は上記ラベルｒを得る。結果はハッシュ表３に示されている。
【００１８】
もしある位置が同じラベルをもたない２つ（またはそれ以上）の位置に隣接しているとわかると、それは境界ノードであり、以下の意味で最も近い集合のラベルが与えられる。第１の割り当てられた位置への測地線距離は、複数の集合各々に関して計算され、最小値が発見される。もし複数の上記測地線距離が等しいとき、その位置は最初に発見されたグループへ割り当てられる。境界点の割り当てはこの処理には必要ない。これは、分類ラベルが全てのデータの組み合わせに添付されるのを確実にする便宜である。もちろん、これらの境界の組み合わせにラベルを付けないままにして、これらの境界の組み合わせを他の方法で処理することは可能である。
【００１９】
ピクセルに関してハッシュ表のキーを計算することにより、そして、ハッシュ表からラベルを読み取ることにより、適切なラベルが、各ピクセルに対して割り当て可能である。結果は以下のようになる。
【表６】
2005513632.tif 000007
表６：最終的に「分割された」イメージ
【表７】
2005513632.tif 000008
表７：特性空間（ヒストグラム）
【００２０】
表７は正規に表されたヒストグラムすなわち特性空間である。降下集合の考えを使用することにより、上記データ中には２つの集合しかないことは容易にわかる。より多くの次元が使用されたとき、２つの表（この例の場合ハッシュ表の１３回のチェックおよびヒストグラムの２５回のチェック）をスキャンするのにかかる時間の違いは、著しく大きくなるので、ハッシュ表法のみが適している。
【国際調査報告】
2005513632.tif 000009
2005513632.tif 000010
2005513632.tif 000011