(57)【特許請求の範囲】
【請求項１】
コンピュータシステムを作動させて複数の画像をイベントに分類する方法であって、
該コンピュータシステムは、
（ａ）画像捕捉の日付及び時間を有する時間的な順に配置された複数の画像を受ける段階と；
（ｂ）前記時間的な順にされた複数の画像において隣接する画像間の時間差を決定する段階であって、該時間差は前記画像捕捉の日付及び時間から計算される、段階と；
（ｃ）前記隣接する画像間の時間差に対する画像数を表すヒストグラムを生成する段階と；
（ｄ）ｋ平均クラスタリングを用いて前記ヒストグラムを隣接する画像間の時間差の少なくとも２つのクラスタに分ける段階であって、該クラスタのうちの１つは最大の前記隣接する画像間の時間差を有する最大時間差クラスタである、段階と；
（ｅ）前記複数の画像を前記イベントに分類する段階であって、前記イベントはイベント境界により分けられ、前記イベント境界は、前記最大時間差クラスタ内の全ての隣接する画像間の時間差に対応する、段階と；
（ｆ）前記イベントに分類された画像の内容を分析することにより、少なくとも１つの前記イベントを所定のグループに更に分ける段階と、
を実行する、
方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はイベントなどにより画像を自動的に分類する画像理解を有する画像処理の分野に関し、より詳細には時間及びデータ解析により、及び画像のブロックを相互に選択的に比較するブロックに基づく解析による画像の自動分類に関する。
【０００２】
【従来の技術】
絵画的画像は画像の検索、レビュー、アルバム化の便のために特定のイベント、対象（ｓｕｂｊｅｃｔ）、又はそのようなものによりしばしば分類される。典型的にはこれはマニュアルで画像をセグメント化することにより、又は下記の自動化された方法により達成されてきた。自動化された方法は画像を類似の画像特徴の群に分割するするために画像のカラー、形状、テクスチャーによるグルーピングを含む。
【０００３】
画像を分割するために現在知られ、用いられている方法は満足できるものであるが、欠点が存在する。マニュアルの分類は明らかに時間を浪費し、理論的には画像をイベントに分類する自動化された処理はカラー、形状、又はテクスチャーによる分類に含まれる本質的な不正確さにより誤って分類されるおそれがある。
従って、上記の欠点を克服する必要が存在する。
【０００４】
【発明が解決しようとする課題】
本発明は上記の欠点を克服することを目的とする。
【０００５】
【課題を解決するための手段】
短く要約すると、本発明の一特徴によれば本発明は画像捕捉の日付及び／又は時間のいずれか又は両方を有する複数の画像を受け；画像のクラスタリングに基づき複数の画像の一以上の最大の時間差を決定し；一以上の境界が一以上の時間差に対応するイベント間の一以上の境界を有することに基づき複数の画像をイベントに分ける各段階からなる画像をイベントに自動的に分類する方法である。
【０００６】
【発明の実施の形態】
本発明のこれらの及び他の特徴、目的、利点は以下に図面を参照して、好ましい実施例及び請求項の詳細な説明により明らかとなる。
以下の記述で、本発明はソフトウエアプログラムとしての好ましい実施例で記載される。当業者にはそのようなソフトウエアの等価物はまたハードウエアで構成可能なことは容易に明らかである。
【０００７】
更にまた、ここで用いられるように、コンピュータ読み取り可能な記憶媒体は例えば磁気ディスク（フロッピーディスクのような）又は磁気テープのような磁気記憶媒体、光ディスク又は光テープのような光記憶媒体、又は機械読み取り可能なバーコード、ランダムアクセスメモリ（ＲＡＭ）又はリードオンリーメモリ（ＲＯＭ）のような固体電子記憶デバイス、又はコンピュータプログラムを記憶するために用いられる他の物理的デバイスからなる。
【０００８】
加えて、”イベント”という用語はここでは画像捕捉装置のユーザーの主観的な意図により知覚されるような顕著な出来事又は発生として決定される。
本発明を説明する前に、本発明がパーソナルコンピュータのような如何なる良く知られているコンピュータシステム上で好ましく用いられることを注意することが理解を容易にする。従って、コンピュータシステムはここでは詳細には説明しない。画像は（例えばデジタルカメラにより）コンピュータシステムに直接入力されるか又は（例えばスキャンニングにより）コンピュータシステムに入力される前にデジタル化されるかのいずれかである。
【０００９】
図１を参照するに、本発明の概略を示すフローダイアグラムを示す。デジタル化された画像はコンピュータシステムに入力され、ここで本発明のソフトウエアプログラムはそれらを区別されたカテゴリーに分類する。画像はまず、各画像の捕捉の時間及び日付を解析されることにより時間的な順序でランクされるＳ１０。各画像の捕捉の日付及び／又は時間は例えばアドバンストフォトシステム（ＡＰＳ）画像のフィルム片上にエンコードされた情報から、又はデジタルカメラから得られる情報から抽出される。画像の表現は下記の日付及び時間クラスタリング解析により複数の区別されるイベントの一つに配置されるＳ２０。各イベントで、画像の内容は隣接するイベントに時間的に最も近い画像がクラスタリング解析により決定されるイベントに維持されるべきか、又は隣接するイベントが共にマージされるかを決定するために解析されるＳ２０。画像がイベントに入ることが決定された後で、各イベントで更なる副分類（グルーピング）がなされる。これに関して、各イベントの画像は類似の内容の画像を共にグルーピングするために内容により解析されＳ３０、それから更にグルーピングを詳細にするために日付及び時間を解析されるＳ３０。
【００１０】
日付及び時間情報を用いるイベントセグメント化Ｓ２０は下記に説明するｋ平均（ｋ−ｍｅａｎｓ）クラスタリング技術によりなされ、これは画像をイベント又はセグメントに分類する。境界チェックはこれも以下で説明するように、境界画像がクラスタリングにより識別されたセグメントにグループ化されなければならないことを確認するためにセグメントＳ２０でなされる。
【００１１】
画像のこれらのグループは次に、内容を解析するためにブロックに基づくヒストグラム相関器に送られるＳ３０。相関器に送られた各イベント又はセグメントに対して内容又は対象のグルーピングは特定のイベントセグメントの対象により画像を更に副分類するためにそこでなされる。例えば、一のイベントで、幾つかの異なる対象が現れ、これらの対象のグルーピングはこれらの特定の対象を決定する。対象のグルーピングは画像内容に主に基づき、これはブロックに基づく相関技術によりなされる。この相関は以下に詳細に説明するように２つの画像の部分を相互に比較する。ランキングの結果は各セグメントの画像の異なる対象のグルーピングへの分類である。各対象のグルーピングの画像全ての日付と時間がどの２つ以上の対象のグルーピングも単一の対象のグルーピングにマージ可能か否かをチェックするために比較されるＳ３０。
【００１２】
詳細及び対象の再配置解析Ｓ４０は更に対象のグループのある画像を再配置することにより分類の全体及び対象のグルーピングを改善する。
図２を参照するに、日付及び時間クラスタリング技術Ｓ２０を示す詳細なブロックダイアグラムを示す。まず、隣接する画像間の時間間隔（時間差）が計算されるＳ２０ａ。時間差のヒストグラムが次に計算されＳ２０ｂ、その一例がブロック１０に示される。ヒストグラムの横軸は好ましくは分単位の時間であり、縦軸は特定の時間差を有する画像の数である。ヒストグラムは次に図３に示される時間差スケーリング関数を用いてスケール化されたヒストグラムにマップされるＳ２０ｃ。このマッピングは小さい時間差を有する画像の時間差を実質的に維持し、大きな時間差を有する画像の時間差を圧縮する。
【００１３】
２平均クラスタリングはマップされたヒストグラム１０を時間差に基づく２つのクラスターに分けるマップされた時間差ヒストグラムでなされ、破線は２つのクラスタに対する分離点を表す。２平均（２−ｍｅａｎ）クラスタリングの更なる詳細については、Ｋｅｉｎｏｓｕｋｅ  Ｆｕｋｕｎａｇａの１９９０年のＩｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｓｔａｔｉｓｔｉｃａｌ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ第二版を参照。故に、２平均クラスタリングの処理はここでは詳細に説明しない。図４を参照するに、２平均クラスタリングがヒストグラムを２つの部分１０ａ及び１０ｂにセグメント化することである。故に２平均クラスタリングはこれらの大きな時間差が実際に存在するところを決定することである。これに関して平均クラスタリング出力の右部分１０ｂはイベント境界に対応する大きな時間差を決定する。
【００１４】
図５を参照するに、イベント間の境界チェックの一例を示す。２つの連続するイベントｉ，ｊに対して、複数のブロックに基づく、ヒストグラム比較が一のイベントの境界で画像が他のイベントの境界の画像と異なるか否かをチェックするためになされる。内容の比較が類似している場合には２つのセグメントは一のセグメントにマージされる。そうでなければ、セグメントはマージされない。好ましくは、比較は図示されるように各イベントの３つの境界画像（ｉ３，ｉ４，ｉ５とｊ１，ｊ２，ｊ３）でなされる。例えば画像ｉ５は画像ｊ１と比較され、等々。このブロックに基づくヒストグラム比較技術は以下に詳細に説明される。
【００１５】
図６を参照するに、各セグメント化されたイベントに対する対象（内容）グルーピングの概略を示す。各セグメント化されたイベントｉでは隣接する画像は以下に説明するブロックに基づくヒストグラム技術を用いて相互に比較される（矢印により示される）。例えば、ブロックに基づくヒストグラム技術は図示されるように一のイベントｉから５つの対象のグルーピング（例えばグループ１から５）を形成する。対象のグルーピングの配置は対象の配置中に将来の検索のために記憶される（段階ｓ４０）。特に、単一の画像を有する対象のグルーピングが記憶される（例えばグループ２、３、５）。
【００１６】
図７を参照するに、内容によるグルーピングの後に、時間及び日付の順序づけが時間及び日付解析に基づくグループ（群）を共にマージするグルーピングでなされる。イベントの隣接する画像間の時間差のヒストグラムは図４と同様に計算される。最大時間差（例えば境界ａ12）の所定の数がブロックに基づく解析により決定される対象グルーピングの境界（例えば境界ｂ12，ｂ23，ｂ34，ｂ45）と比較される。最大時間差の所定の数はイベント内の画像の全数をグループ毎の画像の平均数で割ることにより決定される（本発明では４が用いられる）。対象グルーピングの境界が選択された時間差に基づく境界に適合する場合には対象のグルーピングはマージされない。２つの境界の間に適合が見られない場合には、境界を有し、ヒストグラムで適合された時間差を有さない対象のグルーピングは単一の対象グルーピングにマージされる（例えばグループｂ1 ，ｂ2 ，ｂ3 はマージされ、グループｃ1 が得られる）。
【００１７】
図８を参照するに、各グループの画像再配置のダイアグラムを示す。初期対象グルーピングの配置は単一の画像を含む対象グルーピングを識別するために検索される（例えば、図６の単一の画像を有するグループ：グループ２、３、５はグループ２、３、５として図８に再び示される）。マージされた対象グルーピングにより識別されたとしてマージされた（例えば図７のグループｃ1 ，ｃ2 ）同一の対象グルーピングからの、どの単一の画像も矢印で示されるようにマージされた対象のグルーピングの他の画像全てと比較される。この比較はブロックに基づくヒストグラム解析に基づく。比較が類似である場合には、これらの画像は再配置され、それにより類似の画像は例えばグループｄ1 ，ｄ2 のように相互に隣接して配置される。
【００１８】
更なる詳細化（リファインメント）はイベントの全ての画像で上記の過程の後に単一画像をなお含むどのグループとも比較することによりなされる。これはこれらの単一な画像グループがイベントグルーピングでよりよく配置されたか否かをチェックすることである。この比較は図８の対象再配置段階と類似である。
図９を参照するに、上記の解析で用いられたブロックに基づくヒストグラム相関のフローチャートを示す。まず両方の画像の全体の画像のヒストグラムがグローバルヒストグラムとして計算されるＳ５０。２つのヒストグラムの比較が以下の式に示されるようにヒストグラム交差（インターセクション）によりなされる。
【００１９】
【数１】
0004976608.tif 000002
【００２０】
ここでＲは基準画像のヒストグラム、Ｃは候補画像のヒストグラム、ｎはヒストグラムのビン（ｂｉｎ）の数である。交差が閾値（好ましくは０．３４であるが、他の閾値も用いられる）以下の場合にＳ６５、画像は異なる。閾値と等しい又はそれ以上の場合にはＳ６５、ブロックに基づくヒストグラム相関は達成されたＳ７０。これに関して、各画像は本発明で好ましくは３２ｘ３２画素である与えられた大きさのブロックに分割される。当業者は本発明の範囲から離れることなく画像の解像度に依存してブロックの大きさを変更することが可能である。各ブロックに対して、カラーヒストグラムが計算される。図１０を参照するに、一の画像が基準画像であり、一の画像が候補画像であると考えられ、これらの画像は以下のようにして比較される。基準画像の各ブロック２０は候補画像の対応するブロック３０及び隣接するブロック４０（本発明では８ブロックである）と比較される。
【００２１】
図９を参照するに、基準画像と候補画像との間のブロックヒストグラムは上記Ｓ８０で定義されたヒストグラム交差の式を用いて比較される。平均交差値はブロック比較のそれぞれから最良の交差値の平均を計算することにより得られる。この平均交差値は低い閾値（好ましくは０．３５５）及び高い閾値（好ましくは０．５５７）と比較される。平均交差値が低い閾値より低い場合にはＳ９５、二つの画像は異なると考えられる。平均交差値が高い閾値より高い場合にはＳ９６、二つの画像は類似であると考えられる。平均交差値が二つの閾値の間にある場合には更なる解析が以下に説明するようになされる（３セグメント平均交差マップＳ１００）。
【００２２】
図９と１１の両方を参照するに、３セグメント解析が２つの画像が類似の対象を含むか否かを決定するためになされる。これはまずブロック比較、例えば９の比較が図１０で示されるようになされ、最大の二つの平均がマップ６０で用いられ、それぞれの最大の２つの交差値の平均を含むマップ６０を形成することによりなされる。図１１は、例えば９ｚ６ブロックを示すが、マップサイズは画像のサイズに依存するものである。このマップは３つの部分に分割され、左の部分７０ａ、中央部分７０ｂ、右の部分７０ｃである。中央部分７０ｂの平均交差値が閾値（好ましくは０．３８）より高い場合にはＳ１０５、２つの画像は画像の中央部分７０ｂに非常に類似の対象を含み、２つの画像は対象により類似であると考えられる。加えて、ヒストグラムの比較は基準及び候補画像を逆にすることにより達成される。２つの画像が類似な場合には両方の方法は実質的に類似の相関を与え、それらが異なる場合には結果は類似でないことは明らかである。画像は右、左、上、下の方向の一つで高い交差値が存在するか否かを決定するために次にチェックされるＳ１１０。
【００２３】
図９から１２を参照するに、シフト検出は２つの画像９０、１００（図で２つのことなる大きさの）が画像の異なる位置に現れた非常に類似の対象を有する場合を決定するために用いられる。例えば主な対象が位置の画像の中央に位置し、他の画像の左側に位置するとする。そのようなシフトは候補ブロックの対応する座標と共に基準ブロックの最良交差値の両方を記録することにより決定されうる。これは４つの方向（上下左右）でブロックの交差値を比較することにより達成される。全体の画像は最良の交差値が最大である方向の一つ（図では右）で一ブロック（矢印で示される）だけシフトされる。上記の解析及びシフトは類似性に対するチェックをなすために繰り返されるＳ１２０。
【００２４】
本発明は好ましい実施例を参照して説明されてきた。しかしながら変更及び改良は本発明の範囲から離れることなく当業者になされうる。
【００２５】
【発明の効果】
本発明は日付及び時間情報の両方を用い、画像の対象及び背景の類似性に対するチェックをなすブロックに基づく比較により画像の改善された分類をなすという利点を有する。日付及び時間情報が利用可能でない場合には、ブロックに基づく解析は分類に対してそれのみに基づくように用いられる。
【図面の簡単な説明】
【図１】本発明の概略を示すブロック図である。
【図２】本発明の時間及び日付クラスタリング技術を示すブロック図である。
【図３】２平均クラスタリングの結果のマップを用いたスケーリング関数を示すグラフである。
【図４】図３のスケーリング関数の典型的な結果を示すグラフである。
【図５】時間及び日付クラスタリングの後のイベント境界チェックを示すブロック図である。
【図６】内容に基づく各イベント内の画像のグルーピングを示す図である。
【図７】本発明のグループマージング段階を示すブロック図である。
【図８】各群の再配置の概略を示すブロック図である。
【図９】ブロックに基づくヒストグラム相関技術のフローチャートである。
【図１０】ブロックヒストグラム間の比較を示す図である。
【図１１】３セグメント解析に対する最適交差マッピングの一例を示す。
【図１２】ブロックに基づくヒストグラム相関のシフト検出を示す。
【符号の説明】
２０、３０、４０  ブロック
６０  マップ
７０ａ  左の部分
７０ｂ  中央部分
７０ｃ  右の部分
９０、１００  画像
【図１】
0004976608.tif 000003
【図２】
0004976608.tif 000004
【図３】
0004976608.tif 000005
【図４】
0004976608.tif 000006
【図５】
0004976608.tif 000007
【図６】
0004976608.tif 000008
【図７】
0004976608.tif 000009
【図８】
0004976608.tif 000010
【図９】
0004976608.tif 000011
【図１０】
0004976608.tif 000012
【図１１】
0004976608.tif 000013
【図１２】
0004976608.tif 000014