(57)【要約】【課題】  複数のオブジェクトに基づいて複数のキューを統合化する方法を提供すること。【解決手段】  本方法は：（ａ）前記複数のオブジェクト中の既知のメンバシップを有する標本から、理想的な遷移グラフ及び理想的な遷移確率行列を導出するステップ；（ｂ）複数のオブジェクトキューに基づいて、前記複数のオブジェクトの関係を距離グラフ及び距離行列として導出するステップ；（ｃ）前記距離グラフ及び距離行列を、指数関数的減衰性の単独の遷移確率グラフ及び遷移行列に統合化するステップ；及び（ｄ）前記理想的な遷移確率行列と、前記ステップ（ｃ）におけるキュー統合化により導出された遷移行列との間の距離を最小化することで、前記ステップ（ｃ）における前記距離グラフ及び距離行列を最適化するステップ；より成り、前記の統合化が、キュー表現及び実効性に関する従前の知識を黙示的に捕捉する。【選択図】  図２
2004152297.tif 000002
【特許請求の範囲】
【請求項１】
複数のオブジェクトに基づいて複数のキューを統合化する方法であって：
（ａ）  前記複数のオブジェクト中の既知のメンバシップを有する標本から、理想的な遷移グラフ及び理想的な遷移確率行列を導出するステップ；
（ｂ）  複数のオブジェクトキューに基づいて、前記複数のオブジェクトの関係を距離グラフ及び距離行列として導出するステップ；
（ｃ）  前記距離グラフ及び距離行列を、指数関数的減衰性の単独の遷移確率グラフ及び遷移行列に統合化するステップ；及び
（ｄ）  前記理想的な遷移確率行列と、前記ステップ（ｃ）におけるキュー統合化により導出された遷移行列との間の距離を最小化することで、前記ステップ（ｃ）における前記距離グラフ及び距離行列の統合を最適化するステップ；
より成り、前記の統合化が、キュー表現及び実効性に関する従前の知識を黙示的に捕捉することを特徴とする方法。
【請求項２】
前記理想的な遷移確率行列と、キュー統合化により導出された前記遷移行列との間の距離が、クロスエントロピから決定されることを特徴とする請求項１記載の方法。
【請求項３】
前記ステップ（ｄ）における最適化が、反復的手法によってなされることを特徴とする請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に複数の対象又はオブジェクトのパターン分類を行なう技術分野に関連し、特に複数のキュー（ｃｕｅ）を利用するモデル適合化に関連する。
【背景技術】
【０００２】
複数の未分類（ｕｎｓｏｒｔｅｄ）のオブジェクトを一貫性のある集団又はコヒーレントなクラスタ（ｃｏｈｅｒｅｎｔ  ｃｌｕｓｔｅｒ）に分類するという問題は、長い間研究されている。その作業は、未分類のオブジェクトを所定の判断基準に従ってグループ（クラスタ）に分けることである。判断基準の１つは、クラスタ内距離（同一クラスタ中のオブジェクト間の距離）を最小化すること及びクラスタ間距離（異なるクラスタ内のオブジェクト間の距離）を最小化することである。他の例は、数個の例，見本又は標本（ｅｘａｍｐｌｅ）を示しながら複数のオブジェクトを分類し、残余のオブジェクトが同じ方法で分類されるようにするものである。科学技術の分野における広範なアプリケーションに関し、これは重要な作業である。
【０００３】
最近になって、グラフに準拠する手法が特に注目されており、それは、ある分野（ｄｏｍａｉｎ）に特有の問題を、グラフ区分によって一般的なグラフ表現にする。グラフＧ（Ｖ，Ｅ）は、ノード（ｎｏｄｅ）Ｖ及びエッジ（ｅｄｇｅ）Ｅの集合の数学的な表現である。ノードνｉは、画像、イベント、オーディオ、自動車、遺伝子、人々等のようなエンティティ（実体）／オブジェクト（対象）の抽象的な表現である。エッジｅｉｊは、例えば距離、類似性（ｓｉｍｉｌａｒｉｔｙ）、近縁性（ａｆｆｉｎｉｔｙ）等のような、２つのノード間の関係を捕らえるものである。接続されたグラフは、いくつかのサブグラフに区分され（グラフ分離又はグラフカットとして知られている）、それらのノードはエッジ重み又はエッジウエイト（ｅｄｇｅ  ｗｅｉｇｈｔ）を利用してメタノード（ｍｅｔａ−ｎｏｄｅ）にグループ分けされ得る。従って、グラフノードで表現されたオブジェクトは、コヒーレントなクラスタ（一貫した集団）にグループ化される。関連する作業のいくつかの例は、画像区分化（画素を領域にグループ分けすること）、知覚的グループ化（ｐｅｒｃｅｐｔｕａｌ  ｇｒｏｕｐｉｎｇ）（エッジを輪郭に連結すること）、画像及び形状の組織化（画像及び輪郭の集まりをグループに分けること）、マルチオブジェクト動作区分化（固定オブジェクトを動かして独立にグループ分けすること）並びに映像シーケンスにおけるイベント分析（映像フレームをイベント群に組織化すること）等である。
【０００４】
複数のオブジェクトをクラスタに分類するために、統計的パターン分類やベイズ（Ｂａｙｅｓｉａｎ）ネットワーク分析のような他の手法が存在する。これらの手法は、オブジェクトから特徴を抽出し、それらを高次元特徴空間（ｈｉｇｈ  ｄｉｍｅｎｓｉｏｎａｌ  ｆｅａｔｕｒｅ  ｓｐａｃｅ）で表現する。しかしながら、識別力（ｄｉｓｃｒｉｍｉｎａｔｉｏｎ  ｐｏｗｅｒ）と演算負担との間でトレードオフがある。多くの次元を有する特徴ベクトルは、より多くの識別性を有するが、それらはより高次元の空間にあり、より負担の大きい演算を要する。不都合なことには、それらは、特に高次元特徴空間にて、以前の統計的分布を学習するのに充分なトレーニングデータを必要とする（これは手に負えないことが多い）。しかしながら、グラフを利用する手法は、グラフ重みとして特徴ベクトルの類似性を採用し、それは特徴次元とは分離されるものである。グラフ区分化のグラフ理論に関しては充分に研究された効率的なアルゴリズムも存在し、グラフを用いた手法を非常に魅力的なものにする。
【０００５】
ある分野特有の問題をグラフカットによりグラフ表現にすることは、複数のオブジェクトを分類するための様々なアプリケーションに使用されつつある。例えば、Ｒ．Ｓｈａｍｉｒ  ａｎｄ  Ｒ．Ｓｈａｒａｎによる“Ｍｅｔｈｏｄ  ａｎｄ  Ｓｙｓｔｅｍ  ｆｏｒ  ｃｌｕｓｔｅｒｉｎｇ  ｄａｔａ”と題する国際特許出願番号ＷＯ０１７３４２８（特許文献１）は、生物の遺伝子のような要素の集合を、（遺伝子から導出された指紋の類似性と共に）グラフ表現及びグラフカットを利用することによって分類する方法を開示している。
【０００６】
また、この話題に関し、多くの文献が存在する。選択した公開済みの論文を列挙すると：（１）画像区分化アプリケーションを利用するデータ分析のグラフ手法を開示する非特許文献１。（２）画像区分化における（規格化分離（ｎｏｉｍａｌｉｚｅｄ  ｃｕｔ）として知られる新たなグラフカットアルゴリズム及びそのアプリケーションを開示する非特許文献２。（３）更なる画像区分化における２つの異なるキュー、輪郭（ｃｏｎｔｏｕｒ）及び模様（ｔｅｘｔｕｒｅ）を利用することを開示する非特許文献３。（４）３つの自己組織化タスクについての新たな確率的グラフカットアルゴリズム及びそのアプリケーションを開示する非特許文献４。（５）より最近の、画像区分化に関し、カルバック−レブラ発散（Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ  ｄｉｖｅｒｇｅｎｃｅ）を最小化することによる従前のモデルの学習を開示する非特許文献５。従来の手法の多くは、オブジェクトから抽出した代表的なキュー（ｃｕｅ）のみを使用し、主にそのグラフカットアルゴリズムに焦点を当てている、即ちグラフをどのようにして所与のグラフ重み（ノード間の類似性）を有するサブグラフに区分するかに焦点を当てている。メイラ及びシの論文（非特許文献５）は、画像区分化に従来のモデルを学習することを示唆している。しかしながら、その最適化、距離メトリックの選択、及び画像区分化以外のアプリケーションの詳細を開示していない。
【特許文献１】国際公開ＷＯ０１／７３４２８号パンフレット
【非特許文献１】“Ａｎ  ｏｐｔｉｍａｌ  ｇｒａｐｈ  ｔｈｅｏｒｅｔｉｃ  ａｐｐｒｏａｃｈ  ｔｏ  ｄａｔａ  ｃｌｕｓｔｅｒｉｎｇ：ｔｈｅｏｒｙ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ，”ｂｙ  Ｚ．Ｗｕ  ａｎｄ  Ｒ．Ｌｅａｔｈｙ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ（ＴＰＡＭＩ），ｖｏｌ．１５，ｐｐ．１１０１−１１１３，１９９３
【非特許文献２】“Ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ  ａｎｄ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ”，ｂｙ  Ｊ．Ｓｈｉａｎｄ  Ｊ．Ｍａｌｉｋ，ＴＰＡＭＩ，ｖｏｌ．２２，ｐｐ．８８８−９０５，Ａｕｇｕｓｔ  ２０００
【非特許文献３】“Ｃｏｎｔｏｕｒ  ａｎｄ  ｔｅｘｔｕｒｅ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ”，ｂｙ  Ｊ．Ｍａｌｉｋ，ｅｔ  ａｌ，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，ｖｏｌ．４３，ｐｐ．７０２７，Ｊｕｎｅ  ２００１
【非特許文献４】“Ｓｅｌｆ−ｏｒｇａｎｉｚａｔｉｏｎ  ｉｎ  ｖｉｓｉｏｎ：ｓｔｏｃｈａｓｔｉｃ  ｃｌｕｓｔｅｒｉｎｇ  ｆｏｒ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ，ｐｅｒｃｅｐｔｕａｌ  ｇｒｏｕｐｉｎｇ，ａｎｄ  ｉｍａｇｅ  ｄａｔａｂａｓｅ  ｏｒｇａｎｉｚａｔｉｏｎ”，ｂｙＹ．Ｇｄａｌｙａｈｕ，ｅｔ  ａｌ，ＴＰＡＭＩ，ｖｏｌ．２３，ｐｐ．１０５３−１０７４，Ｏｃｔｏｂｅｒ  ２００１
【非特許文献５】“Ｌｅａｒｎｉｎｇ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｂｙ  ｒａｎｄｏｍ  ｗａｌｋｓ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  ｓｙｓｔｅｍ，ｂｙ  Ｍ．Ｍｅｉｌａ  ａｎｄ  Ｊ．Ｓｈｉ，ＭＩＴ  Ｐｒｅｓｓ  ２００１
【発明の開示】
【発明が解決しようとする課題】
【０００７】
一般的グラフ区分化は、一般的且つ重要な関心事であるが、特定のタスクを成功させるには、グラフ重みを割り当てる事前の処理ステップが重要である。色彩、テクスチャ（ｔｅｘｔｕｒｅ）、タイムスタンプ、動き等のような複数のオブジェクトキューが利用可能である場合には、複合的な基準又は測定値（ｍｅａｓｕｒｅ）としての表現をどのように統合するかが問題である。キュー統合（ｃｕｅ  ｉｎｔｅｇｒａｔｉｏｎ）は、様々なキューからの類似性測定値を、複合的な規格化された測定値に統合する。キュー統合の典型的な選択肢は、指数関数的崩壊
【０００８】
【数１】
2004152297.tif 000003
であり、様々なキューからのペアワイズ類似性（ｐａｉｒｗｉｓｅ  ｓｉｍｉｌａｒｉｔｙ）ｆｉｊｋを単一の複合測定値に組み合わせる。パラメータ
【０００９】
【数２】
2004152297.tif 000004
は、キューの相対的な表現を捕らえ、その分野及びタスク特有の以前の知識を黙示的にエンコードする。タスクデフォルト値の代りに、これらのパラメータは、所与のデータセットについて適切に調整され且つ類似のオブジェクトに適用される例又は標本によって、学習され得る。
【００１０】
直感的には複数のオブジェクトキューを統合することで良好な結果が得られると思われる。しかしながら、様々なキューから導出するオブジェクト類似性の処理は困難なタスクである。各キューは、タイプ、スケール、数値範囲のような様々な特徴を有し得る。それらは冗長（ｒｅｄｕｎｄａｎｔ）であり一貫していない。更に、複数のオブジェクト間の類似性は、常にその脈絡の中での相対的な基準である。予測可能なタスク全体における任意のオブジェクト集合をほぼ表現する一般的な記述は存在しない。従って、特定のデータセットについて一貫したキューを調整する適合手法を得ることは非常に有利であり、必要とされている。
【課題を解決するための手段】
【００１１】
本発明は、上記の１つ又はそれ以上の問題に対処するものである。簡単に述べると、本発明の一態様によれば、本発明は、複数のオブジェクトに基づいて複数のキューを統合化する方法を用いる。本方法は、（ａ）前記複数のオブジェクト中の既知のメンバシップを有する標本から、理想的な遷移（ｔｒａｎｓｉｔｉｏｎ）グラフ及び理想的な遷移確率行列を導出するステップ；（ｂ）複数のオブジェクトキューに基づいて、前記複数のオブジェクトの関係を距離グラフ及び距離行列として導出するステップ；（ｃ）前記距離グラフ及び距離行列を、指数関数的減衰性の単独の遷移確率グラフ及び遷移行列に統合化するステップ；及び（ｄ）前記理想的な遷移確率行列と、前記ステップ（ｃ）におけるキュー統合化により導出された遷移行列との間の距離を最小化することで、前記ステップ（ｃ）における前記距離グラフ及び距離行列を最適化するステップ；より成り、前記の統合化が、キュー表現及び実効性に関する従前の知識を黙示的に捕捉する。
【発明の効果】
【００１２】
従って、本発明は、様々なキューからの複数のグラフを単独のグラフに統合する、複数キューのための適合化方法により上記の要請に合致させ、理想的な遷移確率行列とキュー統合から導出されたものとの間の距離が最適化されるようにする。ドメイン及びタスク固有の知識は、一般的パターン分類タスクを支援するために使用される。
【００１３】
本発明は、様々な状況に特有の利点を有する。例えば、本方法は（ａ）効果的な画像分類を行うために内容に基づく画像記述が適用され；（ｂ）複数のオブジェクトキューを統合することで、複数のオブジェクトを特定のグラフ区分化による遷移グラフとして分類するために使用され；（ｃ）画像をアルバムに整理するための写真アルバムアプリケーションに使用され；（ｄ）画像支援アルゴリズムを利用して写真現像アプリケーションに使用され、その画像支援アルゴリズムのパラメータは入力画像のカテゴリに適用するものである。これらの用途は限定を意味するものではなく、本発明による方法は、当業者にとって明白且つ周知の他の様々な環境に使用され得る。
【００１４】
本発明に関するこれら及び他の態様、対象、特徴並びに利点は、添付図面を参照しながら以下の好適実施例の詳細な説明及び特許請求の範囲を検討することで一層明瞭に理解されるであろう。
【発明を実施するための最良の形態】
【００１５】
以下の説明では、通常はソフトウエアプログラムで実現されるという観点から、本発明の実施例が説明される。当業者は、そのようなソフトウエアに等価なものがハードウエアでも構築され得ることを認識するであろう。画像処理アルゴリズム及びシステム自体は周知であるので、本説明は、本発明によるそのシステム及び方法を形成する又はそれらと更に直接的に協同するアルゴリズム及びシステムに特化している。それらに包含される画像信号を生成する及び処理するためのそのようなアルゴリズム及びシステム並びにハードウエア及び／又はソフトウエアに関する他の態様は、当該技術分野で既知のそのようなシステム、アルゴリズム、部品及び要素の中から選択され得る。関連する要素の中で本発明に説明されるような所与のシステムに関し、本発明を実現するのに有益な具体的には図示、示唆又は記載されていないソフトウエアは、一般的なものであり当該技術分野の範疇におけるものである。
【００１６】
更に、ここで使用されるように、コンピュータプログラムはコンピュータ読み取り可能な記憶媒体に格納され、その記憶媒体は例えば；（ハードドライブ又はフロッピディスクのような）磁気ディスクや磁気テープのような磁気格納媒体；光ディスク、光テープ又は機械読み取り式バーコードのような光記憶媒体；ランダムアクセスメモリ（ＲＡＭ）又は読み取り専用メモリ（ＲＯＭ）のような半導体記憶装置；コンピュータプログラムを格納するために使用される他の任意の物理的装置又は媒体；を含む。
【００１７】
図１を参照するに、本発明を実現するコンピュータシステム１１０が図示されている。コンピュータシステム１１０は好適実施例を説明する目的で図示されているが、本発明は図示のコンピュータシステム１１０に限定されず、家電コンピュータ、キオスク、小売又は卸売り写真現像その他任意のディジタル画像処理システムのような任意の電子処理システムに使用され得る。コンピュータシステム１１０は、ソフトウエアプログラムを受信及び処理し、他の処理機能を実行するマイクロプロセッサ装置１１２を有する。ディスプレイ１１４は、マイクロプロセッサ装置１１２に電気的に接続され、例えばグラフィックユーザインターフェース等を利用して、ソフトウエアに関連するユーザ関連情報を表示する。また、キーボード１１６もマイクロプロセッサ装置１１２に電気的に接続され、ユーザがそのソフトウエアに対する情報を入力することを可能にする。入力用のキーボード１１６を利用する代りに、マウス１１８を利用して、当該技術分野でよく知られているように、ディスプレイ１１４上のセレクタ１２０を動かし、セレクタ１２０が重なる項目を選択することができる。
【００１８】
典型的にはソフトウエアプログラムを含むコンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）１２４は、マイクロプロセッサ装置１１２に挿入され、マイクロプロセッサ装置には、ソフトウエアプログラムその他の情報をマイクロプロセッサ装置１１２に入力する手段を設けている。加えて、フロッピディスク１２６も、ソフトウエアプログラムを包含し、そのソフトウエアプログラムを入力するためにマイクロプロセッサ装置１１２に挿入される。コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）１２４又はフロッピディスク１２６は、代替的に、マイクロプロセッサ装置１１２に接続された外部に設けられたディスクドライブ装置１２２に挿入され得る。更に、マイクロプロセッサ装置１１２は、当該技術分野でよく知られているように、ソフトウエアプログラムを内部に格納するようにプログラムされ得る。また、マイクロプロセッサ装置１１２は、ローカルエリアネットワーク又はインターネットのような外部ネットワークへの、電話回線のようなネットワーク接続１２７を有し得る。また、プリンタ１２８も、マイクロプロセッサ装置１１２に接続され、コンピュータシステム１１０からの出力のハードコピーを印刷する。
【００１９】
また、画像は、以前に知られていた（パーソナルコンピュータメモリカード国際協会の仕様に準拠した）ＰＣＭＣＩＡカードのようなパーソナルカード（ＰＣカード）を通じてディスプレイ１１４に表示され、それはカード１３０に電子的に組み込まれたディジタル画像を包含する。ＰＣカード１３０は最終的にはマイクロプロセッサ装置１１２に挿入され、ディスプレイ１１４における画像の視覚的な表示を許可する。或いは、ＰＣカード１３０は、マイクロプロセッサ装置１１２に接続された外部に設けられたＰＣカードリーダ１３２に挿入されることも可能である。また、画像は、コンパクトディスク１２４、フロッピディスク１２６又はネットワーク接続１２７を通じて入力される。ＰＣカード１３０、フロップディスク１２６若しくはコンパクトディスク１２４に格納される画像又はネットワーク接続１２７を介する入力は、ディジタルカメラ（１３４）又はスキャナ（図示せず）のような様々なソースから取得され得る。また、画像は、マイクロプロセッサ装置１１２に接続されたカメラ接続部１３６を通じてディジタルカメラ１３４から直接的に入力され、又はマイクロプロセッサ装置１１２へのケーブル接続１３８を通じて若しくはマイクロプロセッサ装置１１２への無線接続１４０を通じてディジタルカメラ１３４から直接的に入力され得る。
【００２０】
図２を参照するに、本発明よる方法が説明される。図２は多キュー統合に関する適合化法の一例を示す。多数の距離グラフ２１０及び対応する距離行列が、オブジェクトの同一集合中の様々なキューから導出される。グラフは、キュー統合により単独の遷移グラフ２５０として統合され、グラフは分類のためにサブグラフに区分される。クラスタメンバシップのいくつかの例が利用可能であるならば、その例及びそれらの関係も理想的な遷移グラフ２７０としてモデル化され得る。グラフ２５０及び２７０間の距離を最小化することで、その例を分類するのに使用される背後の従前の知識（ｕｎｄｅｒｌｙｉｎｇ  ｐｒｉｏｒ  ｋｎｏｗｌｅｄｇｅ）が推測され、システムモデル３００を調整するために使用され、それは残余のオブジェクトに対する一層良好な分類に使用され得る。
【００２１】
図２では、６つのオブジェクト及びそれらの関係が、オブジェクトキュー（例えば、色彩、形状、高さ、時間、速度、価格等を表現する個々のキュー）毎に１つの多数のグラフとしてモデル化される。ノード２２０は単一又は複数のオブジェクトを包含し、ペアワイズ関係２３０が導出及び評価されるので、階層的なグラフは非常に柔軟性のある（様々な対象に適用され得る）表現である。また、オブジェクトｉ及びオブジェクトｊの間の関係を示す要素（ｉ，ｊ）を有する行列によって、同じ関係が表現され得る。距離グラフにおける重み２３０は、２つのオブジェクト間の距離／非類似性（ｄｉｓｓｉｍｉｌａｒｒｉｔｙ）を示す。類似するオブジェクトは小さな重みを有する。例えば、オブジェクト２は、第１キューにおける重み５及び６８、ｋ番目のキューにおける重み０．１２及び０，９８により、オブジェクト３よりもオブジェクト１に類似している。Ｋ個の異なるキューに関し、全部でＫ個の距離グラフ及び距離行列が導出される。これらは、２４０にて、モデル３００で要求されるキューの強調（ｅｍｐｈａｓｉｓ）を施した単独の遷移グラフ及び遷移確率行列２５０として共に統合される。遷移グラフでは、エッジ重み２６０が、実際に、あるノードから他への遷移確率になる。本発明の目的は、遷移グラフの構造及び遷移確率行列が簡潔であり一意的であり、以下の一般的な分類手段に多くの成功の機会を与えるような最適なモデル３００を見出すことである。図２のモジュールは、図３乃至図６にて詳細に説明される。
【００２２】
図３は、一群のオブジェクト２２０及びそれらの関係から距離グラフ及び距離行列２１０をどのようにして構成するかを示す。オブジェクトはここではアプリケーションの分野（用途）に依存する抽象的な表現物である。例えば、タスクが、会議に出席する人々を分類することであるならば、オブジェクトは人々であり得る。タスクが写真をアルバムに置くことであるならば、それらは写真であり得る。モジュール３１０はオブジェクトからキュー記述３２０として固有の特徴（指紋）を抽出する。各オブジェクトは総て、人物に関しては年齢、身長及び性別、画像に関しては色彩及び模様等のような多数の様相を有する。明らかに、これらの様相及び強調性に依存して、同一のオブジェクト集合が別々に分類され得る。内容又はコンテンツ記述３２０ｈｉｋは、オブジェクトｉに関するｋ番目のキューの記述であり、通常は数のベクトルとして表現される。コンテンツ記述の類似性比較は、３３０で実行される。キューｋに関するオブジェクト間の距離／非類似性は、距離グラフ２１０及び行列要素ｄｉｊｋのエッジ重みになる。オブジェクトのペアが同一であっても、ｋ＝１，．．．，Ｋの異なるキューからのｄｉｊｋは冗長的又は不一致であり得る。例えば、あるキュー（色彩）にて類似する画像は、別のキュー（空間的配置）では全く相違し得ることが理解されるであろう。
【００２３】
図４に、距離グラフ及び距離行列から遷移グラフ及び遷移行列への、多キュー２４０統合の詳細が示される。ペアワイズ距離ｄｉｊｋが、先ず
【００２４】
【数３】
2004152297.tif 000005
として、３５０にて規格化される。
【００２５】
ローカルスケール因子σｋは、統計的な検査により評価され、又は距離行列Ｄｋ中の第ｋ最近接要素（ｋ−ｎｅａｒｅｓｔ−ｎｅｉｇｈｂｏｒ）として選択され得る。様々なキューからの基準又は測定値ｄｉｊｋは、０から無限大の間で様々な数値範囲を有し得る。規格化は、あるキューが他よりも過剰に優先されることを回避しつつ、ｆｉｊｋが類似する範疇に入るようにする。
【００２６】
規格化された距離測定値ｆｉｊｋは、３５５にて、指数関数的減衰性によって単独の遷移確率ｐｉｊとして統合及び結合され、
【００２７】
【数４】
2004152297.tif 000006
ｐｉｊは、ノードｉからノードｊへの経験的な遷移確率であり、Ｚｉはノードｉに関する規格化因子であり、ノードｉから他のノードへの遷移確率の合計が１になるようにするものである。
【００２８】
キュー統合２４０はギブス（Ｇｉｂｂｓ）形式である。他の単調関数も潜在的に使用可能であるが、指数関数的な減衰は心理物理学的な検証によって支持されている。重み
【００２９】
【数５】
2004152297.tif 000007
は、相対的なキューの重要性／表現を調整する。それらは、所与のオブジェクト集合に関してどのキューが表現及び識別されるかというような従前の知識をエンコードする。以下、各例（標本）からモデルΛをどのようにして学習するかを示す。
【００３０】
図５を参照するに、（未知のクラスタメンバシップと共に）多数の未分類オブジェクト２２０、及び（既知のクラスタメンバシップを有する）いくつかの分類例を有するものとする。その例は、それらを分類するのに使用した従前の知識を暗に捕らえている。最適なモデルΛ＊３００を見出すことによって、未分類オブジェクト２２０を同様な方法で分類することを目指す。
【００３１】
図３，図４における以下の手順、遷移確率行列Ｐ２５０、及び理想的な遷移確率行列Ｐ＊は、未分類オブジェクト２２０及び例３６０からそれぞれ導出され得る。理想的な遷移確率行列Ｐ＊は対称的なブロック対角行列であることが示され得る。クラス内（ｉｎｔｒａ−ｃｌａｓｓ）遷移は等しい確からしさでなされ、クラス間（ｉｎｔｅｒ−ｃｌａｓｓ）遷移は厳密に禁止される。その簡易な構造は、一義的なピース状（ｐｉｅｃｅｗｉｓｅ）一定の固有ベクトルを導出し、その固有ベクトルは容易に分類されることが可能であり、対応するグラフ遷移を強固に（ｒｏｂｕｓｔ）且つ効率的にする。実際には、キュー統合により導出された遷移行列Ｐは、複雑な構造を有する。それは対称的でなく、一意の固有ベクトルを有しない場合がある。クラス内遷移は等しい確からしさでなく、クラス間遷移確率は常にゼロではない。これらの要因は総てその支配的な固有ベクトルの構造を複雑にし、分類を困難にする。
【００３２】
そこで、最適化の３８０にて、理想的な遷移分布Ｐ＊及びキュー統合により得られたものＰの間の距離を最少にする最適なモデルΛ＊３００
【００３３】
【数６】
2004152297.tif 000008
を見出すことを目指す。
【００３４】
図６の最適化の詳細を参照する。入力は、理想的な遷移分布Ｐ＊２７０及び統合化から導出されたものＰ２５０である。距離‖Ｐ＊−Ｐ‖は、距離測定４００の選択内容により最小化される。フロベニウス（Ｆｒｏｂｅｎｉｕｓ）ノルム４１０、カルバック−レブラ（Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ）発散４２０、ジェフリ（Ｊｅｆｆｒｅｙ）発散４３０及びクロスエントロピ（Ｃｒｏｓｓ  ｅｎｔｒｏｐｙ）４４０のような、２つの行列間の相違を測定する様々な手法が存在する。パラメータΛに関する‖Ｐ＊−Ｐ‖の偏微分をとり、それがゼロになるように設定し、一群の非線形方程式ｆ（Λ）＝Ｙを求め、ここでｆは未知変数Λを観測（ｏｂｓｅｒｖａｔｉｏｎ）Ｙにマッピングするものである。そして、最適な解Λ＊を求めるために、ｆ（Λ）＝Ｙ４５０を解く。
【００３５】
ａ）フロベニウスノルム４１０は、同次元の２つの行列の間の距離に関する対称性の尺度である。
【００３６】
【数７】
2004152297.tif 000009
これを選択すると、非線形方程式ｆ（Λ）＝Ｙは、
【００３７】
【数８】
2004152297.tif 000010
のような明示的な形式を有する。
【００３８】
ｂ）カルバック−レブラ発散４２０は、ある確率分布から他へ向けられる相違量を測定し、
【００３９】
【数９】
2004152297.tif 000011
【００４０】
【数１０】
2004152297.tif 000012
のような最適化方程式を導く。
【００４１】
ｃ）ジェフリ発散４３０は、２つの確率遷移の対称性尺度であり、
【００４２】
【数１１】
2004152297.tif 000013
これが距離測定に採用されると、非線形方程式ｆ（Λ）＝Ｙは、
【００４３】
【数１２】
2004152297.tif 000014
のような形式になる。
【００４４】
ｄ）クロスエントロピは、
【００４５】
【数１３】
2004152297.tif 000015
として定義され、
【００４６】
【数１４】
2004152297.tif 000016
のような異なる形式の非線形方程式を導出する。
【００４７】
以下、非線形方程式ｆ（Λ）＝Ｙを解くステップを提示する。先ず、非線形方程式は、解Λの近傍で、
ＪΔ＝ε
として線形化され、ここで、
【００４８】
【数１５】
2004152297.tif 000017
は、ヤコビアン行列であり、ΔはΛに関する調整量であり、ε＝Ｙ−ｆ（Λ）は、線形化による近似誤差である。線形システムに関する解は、
Λｔ＋１＝Λｔ＋Δｔ
として、モジュール４９０において反復的に再定義され、以前の解が次の反復に対する開始点となるようにする。この反復は、‖Δｔ‖が充分に小さくなるまで、又は事前に指定された反復回数に達するまで続く。反復の出力は最適なモデルΛ＊３００であり、これは未分類の残余のオブジェクトを分類するために使用され得る。
【００４９】
ステップサイズのより良好な制御性及びより高速な収束性を得るために、リーベンバーグ−マーガード（Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｇｕａｒｄｔ）法を利用し得る。基本的な概念は、高速収束に関するニュートン反復法と、コスト関数の減少に関する降下法との間で切り替えを行なうことで、反復される推定のステップサイズを適切にするというものである。このため、ＪΔ＝εに対する線形な解は、
【００５０】
【数１６】
2004152297.tif 000018
とし、ここでＩは単位行列である。対角要素ζに関する摂動項（ｐｅｒｔｕｒｂａｔｉｏｎ  ｔｅｒｍ）は、大きなζが小さなステップサイズを与えるように、ステップサイズを調整する。最初にζは、例えばζ＝０．００１のような、ある小さな数として設定される。反復の後、Δｔが誤差を減少させるならば、その解が受け入れられ、ζは１０で除算される。そうでなければζには１０が乗算され、次の反復におけるステップサイズを減少させる。この手順は、小数の又はほどほどの数のキューに関して、通常は少ない反復数で収束する。
【００５１】
多キュー統合に対する適法手法の詳細を提示しながら、好適実施例の画像コンテンツ記述の特定のアプリケーションに戻る。グラフノードの物理的な意味を変更することで、同一の手法が別の分類作業にも適用され得る。
【００５２】
画像分類は、画像内容に基づいて、一群の未分類の画像をコヒーレントなクラスタ（一貫した集団）として分類することを意図する（例えば、写真のアルバム編集作業）。問題は、どのようにして画像内容を記述し、効率的且つ効果的にロバストな分類を行なうかである。この目的のため、図７では、日没、バラ、顔、模様及び指紋の５つの異なるカテゴリから、２５個のテスト画像が選択される。２５個の画像のグランドトルス（ｇｒｏｕｎｄ  ｔｒｕｔｈ）及び５つのカテゴリのそれらのメンバシップは、分類例３６０として機能する。理想的な遷移確率行列Ｐ＊２７０は、図９（５６０）に示されるように導出され得る。その行列は、ロバスト的及び効率的なグラフ区分化を可能にする、非常に特殊な構造を有する。
【００５３】
色彩コレログラム（ｃｏｒｒｅｌｏｇｒａｍ）及び色彩ウェーブレット（ｗａｖｅｌｅｔ）に関する特徴が、低レベル画像コンテンツ記述キューとして選択される。従って、図２における２つの距離行列２１０が存在し、１つは色彩コレログラムに関するものであり、もう１つは色彩ウェーブレットモーメント（ｍｏｍｅｎｔ）に関するものである。色彩コレログラム（λ１）は空間的な色彩分布を捕らえるのに効果的であり、ウェーブレットモメント（λ２）は模様判別に良好であることが、示されている。バンド距離（ｂａｎｄ  ｄｉｓｔａｎｃｅ）ｋ＝３，５，７に関するバンド自動コレログラム（ｂａｎｄｅｄ  ａｕｔｏ−ｃｏｒｒｅｌｏｇｒａｍ）は、チャネル毎に３ビットのＹＵＶ色彩空間にて一様に量子化された画像から抽出され（図３のモジュール３１０）、１５３６（３＊２（３＋３＋３））の特徴次元を生成する。類似性測定に関してχ２統計検査が実行され（モジュール３３０）、２５×２５の距離行列Ｄ１を生成する。色彩ウェーブレットモーメントに関し、画像を、３レベルのウェーブレットピラミッドに分解及びサブサンプル化し、（ＹＵＶ空間内で）各レベル及び格式最チャネルにおける平均並びにＨＬ，ＬＨ及びＨＨサブバンドの標準偏差を収集する。各特徴は５４次元を有する（２モーメント＊３サブバンド＊３レベル＊３色彩チャネル）。特徴ベクトルの各成分は、全画像集合に関するその要素の標準偏差によって更に規格化される。１ノルム距離が類似性測定のために測定され、他の距離行列Ｄ２を生成する。
【００５４】
図８は、画像コンテンツ記述キューへの強調性を調整することによる、キュー統合の影響を図示する。Ｘ及びＹ軸はλ１（コレログラム）及びλ２（ウェーブレット）である。Ｚ軸は、理想的な遷移行列と、４つの異なる基準で測定されたキュー統合によるものとの間の距離を示す。‖Ｐ＊−Ｐ‖を最小化する最適なモデル（λ１*，λ２＊）は、後続のグラフカットに対する良好な開始点となる。
【００５５】
理想的な遷移行列Ｐ＊５６０、最適な遷移確率行列（フロベニウスノルムによるＰｆ５８０、カルバック−レブラ発散によるＰｋｌ６００、ジェフリ発散によるＰｊｆ６２０、クロスエントロピによるＰｃｅ６４０）及びそれらに対応する上位３つの支配的な固有ベクトルが、図９乃至図１３に示されている。これらの図において、黒色、白色及び灰色は、それぞれｐｉｊ＝０，ｐｉｊ＝１及び０＜ｐｉｊ＜１に対応する。スペクトルグラフ法は、グラフカットに関する支配的な固有ベクトルを使用する。従って、簡易且つ特有の構造を有するこれら固有ベクトルは、より効率的にロバスト的に分類され得る。図９では、理想的な遷移行列にて５つのクラスタを見出すことは容易である。システムモデルΛを調整することで、低レベル画像記述が、２５の画像に示される例に適合され、残余の画像はそれに従って分類され得る。
【図面の簡単な説明】
【００５６】
【図１】本願実施例によるコンピュータシステムの全体図を示す。
【図２】複数キュー統合の適合法を示す図である。
【図３】距離グラフ及び距離行列を生成する様子を示す図である。
【図４】単一遷移グラフ及び遷移確率行列として、複数キューから距離グラフ及び行列を統合する詳細な様子を示す図である。
【図５】理想的な遷移行列とキュー統合から導出されたものとの間の距離を最小化する最適化ステップを示す図である。
【図６】最適化の詳細な様子を示す図である。
【図７】内容に基づく画像記述に使用される（日没、バラ、顔、模様及び指紋のカテゴリからの）２５個のテスト画像を示す図である。
【図８】（ａ）フロベニウス距離；（ｂ）カルバック−レブラ発散；（ｃ）ジェフリ発散；（ｄ）クロスエントロピの様々な距離測定によるＰ＊及びＰ間の距離（ｘ軸は相関性、ｙ軸はウェーブレット、ｚ軸は距離を表す）を示す図である。
【図９】（ａ）理想的な遷移確率行列Ｐ＊及び（ｂ）その上位３つの支配的な固有ベクトルを示す図である。
【図１０】（ａ）フロベニウス距離による最適な遷移確率行列Ｐ及び上位３つの支配的な固有ベクトルを示す図である。
【図１１】（ａ）カルバック−レブラ発散による最適な遷移確率行列Ｐ及び上位３つの支配的な固有ベクトルを示す図である。
【図１２】（ａ）ジェフリ発散による最適な遷移確率行列Ｐ及び上位３つの支配的な固有ベクトルを示す図である。
【図１３】（ａ）クロスエントロピによる最適な遷移確率行列Ｐ及び上位３つの支配的な固有ベクトルを示す図である。
【符号の説明】
【００５７】
１１０  コンピュータシステム
１１２  マイクロプロセッサ装置
１１４  ディスプレイ
１１６  キーボード
１１８  マウス
１２０  ディスプレイ上のセレクタ
１２２  ディスクドライブ装置
１２４  コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）
１２６  フロッピディスク
１２７  ネットワーク接続
１２８  プリンタ
１３０  パーソナルコンピュータカード（ＰＣカード）
１３２  ＰＣカードリーダ
１３４  ディジタルカメラ
１３６  カメラ接続部
１３８  ケーブル接続
１４０  無線接続
２１０  （距離行列により表現される）距離グラフ
２２０  グラフノードとして表現されるオブジェクト
２３０  グラフエッジによるオブジェクト非類似性
２４０  複数キュー統合
２５０  （遷移確率行列Ｐにより表現される）遷移グラフ
２６０  遷移確率
２７０  （理想的遷移行列Ｐ＊により表現される）理想的遷移グラフ
２８０  ノード（オブジェクト）１，２，６に関するサブグラフ１
２９０  ノード（オブジェクト）１，２，６に関するサブグラフ１
３００  最適モデルΛ
３１０  特徴抽出
３２０  低レベル特徴表現（署名／指紋）
３３０  類似性測定
３５０  スケール規格化
３５５  指数関数的減少
３６０  分類例
３８０  適応的最適化
４００  行列距離測定
４１０  フロベニウス距離
４２０  カルバック−レブラ発散
４３０  ジェフリ発散
４４０  クロスエントロピ
４５０  非線形最適化
４６０  線形システム
４７０  線形システムに対する解
４８０  反復停止条件
４９０  モデルΛの解更新
５００  ５カテゴリによる２５の試験画像
５１０  フロベニウスノルムによるＰ＊及びＰ間距離
５２０  カルバック−レブラ発散によるＰ＊及びＰ間距離
５３０  ジェフリ発散によるＰ＊及びＰ間距離
５４０  クロスエントロピによるＰ＊及びＰ間距離
５６０  Ｐ＊のグラフ表現
５７０  Ｐ＊の上位３つの支配的固有ベクトル
５８０  Ｐｆのグラフ表現
５９０  Ｐｆの上位３つの支配的固有ベクトル
６００  Ｐｋｌのグラフ表現
６１０  Ｐｋｌの上位３つの支配的固有ベクトル
６２０  Ｐｊｆのグラフ表現
６３０  Ｐｊｆの上位３つの支配的固有ベクトル
６４０  Ｐｃｅのグラフ表現
６５０  Ｐｃｅの上位３つの支配的固有ベクトル
【図１】
2004152297.tif 000019
【図２】
2004152297.tif 000020
【図３】
2004152297.tif 000021
【図４】
2004152297.tif 000022
【図５】
2004152297.tif 000023
【図６】
2004152297.tif 000024
【図７】
2004152297.tif 000025
【図８】
2004152297.tif 000026
【図９】
2004152297.tif 000027
【図１０】
2004152297.tif 000028
【図１１】
2004152297.tif 000029
【図１２】
2004152297.tif 000030
【図１３】
2004152297.tif 000031