(57)【要約】複数ページ内へ複数イメージを配置するために、少なくとも１つのイメージング装置により捕捉されたイメージが受信される。該受信したイメージにコンテンツベース・フィルタリングを適用して該受信したイメージの少なくとも１つを除去してイメージのコレクションを生成する。次いで該コレクション中のイメージにテーマベース・クラスタリングを実行して複数のイメージクラスタを生成し、該複数のイメージクラスタは、時間とイメージ間のテーマ上の類似性の指示を提供する少なくとも１つの他の属性とに基づくテーマにそれぞれ関連するものである。該複数のイメージクラスタが出力表現の各ページへマッピングされる。【選択図】図２
2012507189.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実行されるページ内へのイメージの配置方法であって、
少なくとも１つのイメージング装置により捕捉されたイメージを受信し、
少なくとも１つのフィルタリング基準が満たされた場合に前記受信したイメージのうちの少なくとも１つを除去してイメージのコレクションを生成する、コンテンツベース・フィルタリングを適用し、
前記コレクション中のイメージのテーマベース・クラスタリングを実行して複数のイメージクラスタを生成し、該複数のイメージクラスタが、時間とイメージ間のテーマ上の類似性の指示を提供する少なくとも１つの他の属性とに基づく個々のテーマに関連するものであり、
該複数のイメージクラスタを出力表現の各ページへマッピングする、
という各ステップを含む、コンピュータにより実行されるページ内へのイメージの配置方法。
【請求項２】
コンテンツベース・フィルタリングを適用する前記ステップが、複製イメージを識別して該複製イメージを除去するステップを含む、請求項１に記載の方法。
【請求項３】
コンテンツベース・フィルタリングを適用する前記ステップが、前記受信したイメージのシャープネスに関する少なくとも１つの基準が満たされた場合に該受信したイメージのうちの少なくとも１つを除去するステップを含む、請求項１又は請求項２に記載の方法。
【請求項４】
コンテンツベース・フィルタリングを適用する前記ステップが、前記受信したイメージに対する関心を示す少なくとも１つの基準が満たされた場合に該受信したイメージのうちの少なくとも１つを除去するステップを含む、請求項１ないし請求項３の何れか一項に記載の方法。
【請求項５】
前記少なくとも１つの他の属性が、前記コレクションのイメージ間の色の類似性に関する属性を含む、請求項１ないし請求項４の何れか一項に記載の方法。
【請求項６】
前記少なくとも１つの他の属性が、前記コレクションの各イメージにおける人々の複数の顔又は人々の識別に関する別の属性を更に含む、請求項５に記載の方法。
【請求項７】
前記少なくとも１つの他の属性が、前記コレクション中のイメージにより示される場所に関する別の属性を更に含む、請求項５に記載の方法。
【請求項８】
前記イメージクラスタを前記出力表現の各ページへマッピングする前記ステップが、該イメージクラスタをフォトアルバムの各ページへマッピングするステップを含む、請求項１ないし請求項７の何れか一項に記載の方法。
【請求項９】
前記クラスタのイメージを各ページ内にレイアウトするステップを更に含み、該レイアウトステップが、複数の前記クラスタのうちの特定の１つ内の複数のイメージに重みを割り当るステップを含み、該重みが、該特定のクラスタに対応するページ中の複数のイメージのそれぞれのサイズを示すものである、請求項１ないし請求項８の何れか一項に記載の方法。
【請求項１０】
前記特定のクラスタ中のイメージの重みに基づいて該特定のクラスタに複数のページを割り当てるステップを更に含む、請求項９に記載の方法。
【請求項１１】
前記重みが、色の変化、顔の数、顔の大きさ、及びユーザ指定の中から選択された少なくとも１つの基準に基づいて決定される、請求項９に記載の方法。
【請求項１２】
実行時に請求項１ないし請求項１１の何れか一項に記載の方法をコンピュータに実行させる命令を含む少なくとも１つのコンピュータ読み取り可能記憶媒体を含む物品。
【請求項１３】
コンピュータシステムであって、
イメージを格納するための記憶手段と、
プロセッサであって、
少なくとも１つのフィルタリング基準が満たされた場合に前記格納されているイメージのうちの少なくとも１つが除去されるように該格納されているイメージに対してコンテンツベース・フィルタリングを適用することにより一組のイメージを生成し、
複数のクラスタを生成し、その各クラスタが、前記一組のイメージのうちの少なくとも１つのイメージを含み、該複数のクラスタは、前記一組のイメージ中の各イメージの時間属性に基づいて、更に該一組のイメージ中の各イメージ間のテーマ上の類似性の指示を提供する少なくとも１つの他の属性に基づいて生成され、
該複数のクラスタのイメージを出力表現の対応するページへ出力する、
という各ステップを実行するためのプロセッサと
を備えている、コンピュータシステム。
【請求項１４】
前記コンテンツベース・フィルタリングが、複製基準、シャープネス基準、及び関心基準というフィルタリング基準のうちの１つ又は２つ以上に基づくものである、請求項１３に記載のコンピュータシステム。
【請求項１５】
前記少なくとも１つの他の属性が、前記一組のイメージ中の各イメージ間の色の類似性に関する属性、前記一組のイメージ中の各イメージにおける人々の複数の顔に関する属性、前記一組のイメージ中の各イメージにおける顔の識別に関する属性、対象物の種類の属性、活動の種類の属性、及び前記一組のイメージ中の各イメージの場所に関する属性の中から選択された１つの属性からなる、請求項１３又は請求項１４に記載のコンピュータシステム。
【請求項１６】
前記プロセッサが、前記出力表現のための複数の表紙イメージ候補を識別し、及び該出力表現のための表紙イメージとして選択するために該複数の表紙イメージ候補をユーザに提示する、という各ステップを更に実行する、請求項１３ないし請求項１５の何れか一項に記載のコンピュータシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
ディジタルカメラ（スチルカメラ及び／又はビデオカメラ）は、ユーザが大量のディジタルイメージを捕捉することを可能にする。かかるディジタルカメラで使用されるメモリカードの容量は増大し、該メモリカードのコストは低下している。また、今日のディジタルカメラには、比較的大容量のディスクベースの記憶手段を有するものがある。
【０００２】
大量のディジタルイメージを捕捉するのは容易であるが、かかるディジタルイメージの整理はユーザにとって課題であることが多い。数百あるいは数千ものディジタルイメージを手作業で探索してその整理を行うことは、通常は長時間を要し得る退屈な作業である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ディジタルイメージのコレクション（ディジタルイメージを収集したもの）の自動的なクラスタリングを行うための幾つかの技法が提案されているが、かかる技法は、満足のいく結果をもたらすものではなく、又は効率の悪さという欠点を有するものとなる。
【図面の簡単な説明】
【０００４】
【図１】本発明の一実施形態を組み込んだ典型的なシステムのブロック図である。
【図２】一実施形態による、一群のイメージから複数ページへのページネーションを行うプロセスのフローチャートである。
【図３】一実施形態によるコンテンツベース・フィルタリングを行うフローチャートである。
【図４】一実施形態によるテーマベース・クラスタリングを行うフローチャートである。
【発明を実施するための形態】
【０００５】
本発明の幾つかの実施形態を図面に関連して説明する。
【０００６】
幾つかの実施形態によれば、複数のイメージをテーマによって出力表現のページ上にグループ化する、ディジタルイメージの自動的なテーマベース・ページネーションを行うための機構が提供される。複数のイメージの複数のページを含む前記出力表現は、フォトアルバム又は写真集とすることが可能である。代替的に、該出力表現は、フォトスライドショー又は複数のページを含む他のあらゆるタイプの出力とすることが可能である。一般に、フォトアルバム又は写真集とは、ディジタルイメージをテーマによって別個の異なるページ上に配置して、該ディジタルイメージを整理されて審美的に美しい態様で提示することを可能にする、ディジタルイメージを収容するものを指すものである。用語「写真集」及び「フォトアルバム」は本書では互いに置換可能なものとして用いられる。フォトスライドショーは、ユーザに対して順次表示される多数のスライド（ページ）を提供するものである。
【０００７】
フォトアルバムは、コンピュータやＰＤＡ又はその類といった電子的な装置を使用してユーザがアクセスすることができるディジタル文書とすることが可能である。代替的に、フォトアルバムは、イメージが配置された多数のページを有する物理的なアルバムとすることが可能であり、例えば、幾つかの実施形態による技法を用いてディジタルイメージのページネーションを行った後、そのディジタルイメージからなるページをプリントして、物理的なフォトアルバムを作成することが可能である。
【０００８】
「ディジタルイメージ」（又はより簡単に「イメージ」）とは、対象物（例えば、景色、人、その他）のディジタル表現を指すものである。ディジタルイメージは、スチルカメラ又はビデオカメラ等のカメラを使用して取得することができる。
【０００９】
ディジタルカメラを使用して、ユーザは、大量のイメージを捕捉することができる。幾つかの実施形態によるページネーション機構は、大量のディジタルイメージをテーマに基づいてページ上に整理するための便利で効率的な方法を提供する。該ページネーション機構の結果として得られるフォトアルバムのページは、個々のテーマに関連付けられたものとなる。ここで、１つのテーマは、イメージ中の人々、イメージの景色、イメージ中の色その他に基づくものとすることができる。
【００１０】
効率を改善するために、幾つかの実施形態によるテーマベース・ページネーション機構は、コンテンツベース・フィルタリングを実行して、フォトアルバム内の望ましくない可能性のあるイメージを除去する。イメージ群から除去することができるイメージの例としては、比較的低品質のイメージ、関心がないと思われるイメージ、重複するイメージ、及び／又はユーザが手動で望ましくないとマークしたイメージが挙げられる。
【００１１】
該コンテンツベース・フィルタリングは、イメージがぼやけすぎているか否かの判定を可能にするシャープネス基準、イメージがつまらないか否か又は興味深いか否かの判定を可能にする関心基準、及び或るイメージが別のイメージの複製であるか否かの判定を可能にする重複基準のうちの１つ又は２つ以上を含む、１つ又は２つ以上のフィルタリング基準を使用する。
【００１２】
幾つかの実施形態によるコンテンツベース・フィルタリングを適用することによって、ページネーションのために考察しなければならないイメージの量を削減することができ、これによりイメージのページネーションに伴う更なるタスクを実行するための計算上の負担が低減される。更に、コンテンツベース・フィルタリングを実行することにより、最終的にフォトアルバムページに出力されるイメージが、良好に設計され審美的に魅力的なフォトアルバムをもたらすものとなる可能性が一層高くなる。
【００１３】
コンテンツベース・フィルタリングを実行して削減された一組のイメージを生成した後（この場合、上記の１つ又は２つ以上のフィルタリング基準を使用することにより当初の一群のイメージ中の幾つかのイメージが削除されており）、次いでページネーション機構がテーマベース・クラスタリングを実行する。該テーマベース・クラスタリングは、時間属性や、受容したイメージ間のテーマに関する類似性の指示を提供する少なくとも別の属性を含む、幾つかのクラスタリング属性を考察する。該時間属性は、時間的に近接して捕捉されたイメージが時間的に大きく離れて捕捉されたイメージよりも一層近い関係にある傾向を有することを特定するものである。
【００１４】
実施形態によっては、テーマベース・クラスタリングを実行するために前記時間属性と組み合わせて考察される前記少なくとも別の属性は、（イメージを比較して該イメージ中の色がどの程度近い関係にあるかを判定することを可能にするための）色属性、（イメージ中の人の数に基づくイメージのクラスタリングを可能にするための）顔数属性、及び（地理的な位置に基づくイメージのクラスタリングを可能にするための）場所属性の中から選択することが可能である。
【００１５】
顔数属性を用いたイメージのクラスタリングは、正確に同数の顔を有するイメージの極めて単純なグループ化ではない場合がある。顔数０のイメージと顔数１以上のイメージとの違いに重きを置く場合がある。単一の顔を有するイメージからなるグループは、一層強力なクラスタ（集団）を形成する可能性がある。代替的に、２つ以上の顔を有するイメージからなるグループが１クラスタを形成することが可能である。１グループから３つ又は５つの顔を有するイメージを（他のイメージが４つの顔を有する場合に）除去するのが望ましいという場合はありそうにない。別のルールは、例えば７つ以上の顔を含む大勢の場面（グループショット）が存在する場合に（かかるグループショットが通常は取得するのが非常に困難なものであるため）該イメージをページ全体を占めるように設定することができる、というものである。
【００１６】
イメージをグループ化するために考察することができるもう１つの属性は、一人又は二人以上の同じ人を含むイメージをグループ化しようとする顔識別属性である。例えば、一人又は二人以上の同じ人のイメージを、人を中心としたテーマを提供する１つのページ上に配置するのが望ましい場合がある。
【００１７】
クラスタリング属性を使用して、テーマベース・クラスタリングは、複数のイメージクラスタ（各クラスタは少なくとも１つのイメージを含む）を生成する。該複数のクラスタは、複数のテーマに対応するものである。該クラスタは、フォトアルバムの各ページへとマッピングされる。
【００１８】
図１は、コンピュータシステム100と１つ又は２つ以上のイメージング装置（スチルディジタルカメラ102及びビデオカメラ104を含む）とを含む典型的な構成を示している。該スチルカメラ102及びビデオカメラ104はディジタルイメージを捕捉することが可能なものであり、該ディジタルイメージは、該スチルディジタルカメラ102及びビデオカメラ104が例えば入出力ポート（例えばユニバーサルシリアルバス又はUSBポート）を介して又はネットワーク（例えばLAN、WAN、インターネット等）を介して前記コンピュータシステム100に接続されている場合に該コンピュータシステム100へ転送することが可能である。
【００１９】
前記スチルディジタルカメラ102及び／又はビデオカメラ104により捕捉されたディジタルイメージは、コンピュータシステム100により受信され、該コンピュータシステム100の記憶装置108内にディジタルイメージのコレクション106として格納される。該記憶装置108は、磁気ディスクベースの記憶装置または光ディスクベースの記憶装置といったディスクベースの記憶装置とすることが可能である。代替的に、記憶装置108は、半導体記憶装置を含むことが可能である。
【００２０】
コンピュータシステム100はまた、１つ又は２つ以上の中央処理装置（CPU）112上で実行することが可能なページネーションソフトウェア110を含む。該ページネーションソフトウェア110は、幾つかの実施形態によるページネーション技術を実行して、コレクション106中のイメージをフォトアルバム114のページ上に割り付け、該フォトアルバム114もまた記憶装置108に格納される。
【００２１】
コンピュータシステム100を単一のコンピュータシステムとして示したが、代替的な実施形態では、コンピュータシステム100は、複数のコンピュータから構成することが可能であり、この場合には、ページネーションソフトウェア110は、分散した態様で該複数のコンピュータ上で実行することが可能である、ということに留意されたい。
【００２２】
表示装置116もまたコンピュータシステム100に接続される。該表示装置116は、ページネーションソフトウェア110に関するグラフィカルユーザインタフェイス（ＧＵＩ）118を表示する。該ＧＵＩ118は、フォトアルバム114（該フォトアルバムの各ページを含む）を表示するために使用することが可能である。ＧＵＩ118はまた、ページネーションソフトウェア110に対する制御を行う（例えば一群のイメージに対してページネーションを行うようページネーションソフトウェア110に指示する）ために使用することが可能である。ＧＵＩ118はまた、ページネーションソフトウェア110の設定を調節する（例えば、ページネーションの実行に使用すべきフィルタリング基準及びクラスタリング属性を選択する）ために使用することが可能である。
【００２３】
フォトアルバム114を表示装置116に提示することに加えて、該フォトアルバム114を他の機構により出力することも可能である、ということに留意されたい。例えば、フォトアルバム114の各ページをカラープリンタでプリントすることが可能である。代替的に、フォトアルバムをネットワークを介して遠隔地のユーザへ送ることが可能である。後者の場合、コンピュータシステム100は、サービスプロバイダ（例えば、顧客により提供されたイメージのページネーションサービスを販売するプロバイダ）に関係するコンピュータシステムとすることが可能である。
【００２４】
図２は、一実施形態によるページネーションを実行するための全体的なフローチャートを示している。イメージは、１つ又は２つ以上のイメージング装置から、例えば図１のコンピュータシステム100によって受信される（ステップ202）。該イメージはコレクション106（又は複数のコレクション）内に収集される。イメージは、その処理のためにリアルタイムで受信することが可能であり、この場合には、ページネーションソフトウェア110により実行されるページネーションは、新しいイメージが受信された際に実行される、ということに留意されたい。代替的に、イメージのコレクションを予め格納しておき、ページネーションをオフラインで実行することが可能である（換言すれば、ページネーションを実行する際に新しいイメージは受信されない）。
【００２５】
受信したイメージのコレクションは、極めて大きなものとなり得る。処理の効率を高めるため、及び望ましくないイメージがフォトアルバムに挿入されるのを回避するために、ページネーションソフトウェア110によりコンテンツベース・フィルタリングが実行される（ステップ204）。該コンテンツベース・フィルタリングは、（上述したような）１つ又は２つ以上のフィルタリング基準が満たされた場合に前記コレクションから１つ又は２つ以上のイメージを除去することが可能である。場合によっては、コンテンツベース・フィルタリングの適用は、イメージが何れのフィルタリング基準をも満たさない場合には該イメージを除去しないものである、ということに留意されたい。しかし、一般に、コンテンツベース・フィルタリングの目的は、削減された一組のイメージを生成することにある。
【００２６】
次いで、ページネーションソフトウェア110は、削減された一組のイメージのテーマベース・クラスタリングを実行する（ステップ206）。該テーマベース・クラスタリングは、時間属性、色属性、顔数属性、及び場所属性を含む様々なクラスタリング属性を考察する。顔識別属性、対象物の種類の属性（例えば、自動車を含むイメージや飛行機を含むイメージ等をグループ化するためのもの）、活動の種類の属性（例えば、サッカー、バスケットボール等に関連するイメージをグループ化するためのもの）、又はその他のクラスタリング属性といった、他のクラスタリング属性を追加的に又は代替的に考察することが可能である。テーマベース・クラスタリングは、複数のテーマに対応する複数のクラスタを生成する。
【００２７】
次いで、該クラスタは、フォトアルバムの対応するページへとマッピングされる（ステップ208）。該マッピングは、一対一マッピングとすることが可能であり、又は、１クラスタ中にあまりにも多くのイメージが存在する場合には、該クラスタのイメージを複数のページへとマッピングすることが可能である。代替的に、幾つかのクラスタ中に十分なイメージが存在しない場合には、かかる複数クラスタを１ページ上にマッピングすることが可能である。
【００２８】
更に一般的には、１クラスタ中のイメージの数に基づくマッピングの代わりに、該マッピングを該クラスタ中のイメージのページ空間要件に基づくものとすることが可能である。特定のイメージに他のイメージよりも多くのフォトアルバムページ空間を割り当てるべきことを決定することが可能である。大量のアルバム空間を必要とするイメージを含むクラスタに多くのアルバムページを割り当てることが可能である。これが望ましい場合の一例として、大勢の人々のイメージを含むクラスタの場合が挙げられる。大勢のイメージに１ページ上の大量の空間（おそらくは１ページ全体）を占有させるのが望ましい。この場合には、１クラスタ中のイメージの数がそれほど多くない場合であっても、大勢の場面を含む該クラスタに２ページ以上を割り当てることが可能である。
【００２９】
１つのイメージに割り当てるためのアルバムページ空間の相対的な量を判定するための基準は、（例えば、ユーザによる「お気に入り」の指定を可能にすることにより又は「星評価」機構を使用することにより）手作業で決定することが可能であり、又は一層多くの空間を占有すべき「ビジー」イメージを検出することにより自動的に決定することが可能である。自動的に検出することができる「ビジーさ」の例として、大勢の人（例えば７以上の顔の数）、及び大きく異なる色を有する多数の小領域を含むイメージが挙げられる。これらの測定基準は、以下で説明する「重み」と同じである。
【００３０】
クラスタのイメージは、フォトアルバムの対応するページ上にレイアウトされる（ステップ210）。１ページ上へのクラスタのイメージのレイアウトを行う際に、個々のイメージに割り当てられた重みに基づいて各イメージのサイズを判定することが可能である。１クラスタ中のイメージには、ページ上に配置された際のイメージの相対的なサイズを示す重みを関連付けることが可能である。第１のイメージの重みが大きいということは、一層小さな重みが関連付けられた第２のイメージよりも該第１のイメージの方が大きなサイズを有することになることを示している。一実施形態では、多数の顔を有するイメージに一層大きな重みを関連付けることが可能であり、これは、かかるイメージが、顔を一層明瞭に見ることができるよう一層大きくすることにより利益を得ることになるグループ写真である可能性があることを示している。また、比較的大量のテクスチャを有するイメージ（ビジーイメージ）にも大きな重みを割り当てて、該イメージがフォトアルバムの対応するページ上で一層大きくなるようにすべきである。更に、重みは、顔のサイズ及び／又は色の変化に基づいて割り当てることが可能である。
【００３１】
ページ上へイメージをレイアウトするプロセスを単純化させるために、所定のテンプレートを使用することが可能である。クラスタのテーマが与えられると、該テーマが複数の前記テンプレートと照合される。最高の照合スコアを有するテンプレートを使用して、クラスタのイメージのレイアウトが行われる。一実施形態では、この照合は、ページに割り当てられるイメージと同数のイメージ配置場所を有し該イメージと同じ方向づけを有するテンプレートを選択するステップを含む。この段階で一致する選択が存在する場合には、例えば相対的なイメージサイズの重みが満たされる度合いに従って、その選択肢をランク付けすることが可能である。
【００３２】
他の実施態様では、より高機能なレイアウト機構を採用することができる。かかるレイアウト機構の一つが、C. Brian Atkinsの「Blocked Recursive Image Compositon」（マルチメディアに関する第16回ACM国際会議議事録、第821〜824頁（2008年10月26日））に記載されている。かかるアルゴリズムは、複数のイメージ形状の特定の組み合わせ並びにイメージに関する相対的な重み等のあらゆる追加の仕様に合うようにテンプレートを効率的に設計することが可能なものである。
【００３３】
コンテンツベース・フィルタリング204は、図３により詳細に示されている。該コンテンツベース・フィルタリング204は、複製フィルタリングの適用（ステップ302）、シャープネスフィルタリングの適用（ステップ304）、及び関心フィルタリングの適用（ステップ306）を含む。
【００３４】
図３の３つの異なるフィルタは、特定の順序で示されているが、それらフィルタは、別の実施形態では異なる順序で適用することが可能である。また、図３に示すフィルタの幾つかを省略することが可能である。別の実施態様では、他のフィルタを追加することが可能である。
【００３５】
ステップ302で適用される複製フィルタリングは、複製イメージを除去する。２つのイメージが同一でなくとも、１つ又は２つ以上の測定基準を計算することにより該２つのイメージが互いに十分に類似するものである限り、該２つのイメージは複製であるとみなすことが可能である。ユーザは、同じ光景、人々、又はその他の対象物の写真を複数枚撮る傾向を有する。かかる複数枚の写真は、同じ見た目を有する場合があり、又は異なる見た目を有する（例えば対象物に対して異なるカメラアングルで撮影が行われる）場合がある。
【００３６】
複製検出は、単にイメージの類似性のみに基づいて行うことが可能である。例えば、一対のイメージにおける色クラスタを抽出することが可能であり、該色クラスタを比較することにより色の類似性を確認することが可能である。イメージの類似性は、前記一対のイメージの色クラスタについてのEMD（Earth Movers Distance）に基づくものとすることが可能である。他の実施態様では、他の測定基準を使用して２つのイメージ間の色クラスタの類似性を表すことが可能である。一実施態様では、高速色量子化アルゴリズムをイメージに適用してその主要な色クラスタを抽出することが可能である。かかる高速色量子化アルゴリズムの一例が、Jun Xiao等の「Mixed-Initiative Photo Collage Authoring」（マルチメディアに関する第16回ACM国際会議議事録、第509〜518頁（2008年10月26日））に記載されている。
【００３７】
代替的に、複製検出は、時間に基づくものとすることが可能である。複数の複製写真は、互いに対して近い時刻に撮影される傾向を有するものである。このため、イメージに関するメタデータで時刻情報を得ることができる場合には、該時刻情報を抽出して複製検出に使用することが可能である。一実施態様では、イメージの該メタデータは、EXIF（Exchangeable Image File Format）内に存在することが可能である。EXIFメタデータに含まれる時刻情報は、タイムスタンプという形を有するものである。別の実施態様では、イメージに関する時刻情報は、別の形式のものであることが可能である。
【００３８】
複製検出に資するために、対方式（pair-wise manner）で複製検出を実行するよう二値分類手段をトレーニングすることが可能である（この場合には、一対のイメージを互いに比較してそれらイメージが互いの複製であるか否かが判定される）。該二値分類手段は結果を出力し、該結果は該一対のイメージが互いの複製であること又は該一対のイメージが複製でないことを示すことができる。該二値分類手段のトレーニングは、ユーザが手作業でラベル付けした一組のイメージを使用して行うことが可能である。トレーニングが完了すると、該二値分類手段は新しいイメージを処理して複製を識別することが可能となる。
【００３９】
複製イメージを識別する際に二値分類手段により考察されるイメージの特徴は、上述した色クラスタの類似性、及びイメージに関する時間的な近接性を含む。複製検出関数Dup(X,Y)は、時間差特徴Dt(X,Y)に基づいて分類手段を構築することにより構成することが可能である（X,Yは複製に関して比較している２つのイメージを表している）。該時間差特徴Dt(X,Y)は、イメージX,Yのタイムスタンプ間の隔たりを表すものである。該分類手段はまた、（EMD間隔を考察してイメージX,Yの色クラスタ間の類似性を判定する）色間隔特徴Dc(X,Y)に基づいて構築される。複製検出関数Dup(X,Y)は、考え得るあらゆる一対のイメージに適用することが可能である。
【００４０】
一実施態様では、複製グラフを構築することが可能であり、この場合、グラフ中の２つのノード（２つのイメージをそれぞれ表すもの）は、（上述した二値分類手段により識別された際に）それらが複製であるとき且つそのときに限り接続される。接続されたノードは、グラフ中で識別することができる。２つの複製イメージのうち一層良好な方に関するノードが保持され、該複製イメージを表す他方のノードは複製グラフから削除される。「一層良好な」イメージとは、例えば、顔の数が多い方のイメージ、シャープネススコアが高い方のイメージ、色のバリエーションが豊富な方のイメージ等とすることが可能である。複製グラフから複製ノードが削除された後、最終的な結果は、非複製イメージに対応する非接続ノードのリストとなる。
【００４１】
（ステップ304で）適用されるシャープネスフィルタリングは、シャープネス基準に基づくものである。該シャープネスフィルタは、動き又は合焦の欠如の結果として生じることが多いぼやけたイメージを除去するよう設計される。イメージのぼやけは、イメージ中の主要な縁部を弱めることが多い。
【００４２】
一実施態様では、以下のシャープネススコア(Q)を使用することが可能である。
【００４３】
Q＝強度(e)／エントロピー(h)
ここで、強度(e)は、上位10％の強い縁部の平均縁部強度であり、エントロピー(h)は、正規化された縁部強度ヒストグラムのエントロピーである。
【００４４】
直観的に、ぼやけていないイメージは、強い縁部と、よりピークの強い縁部強度分布とを有しており、それ故、ぼやけていないイメージは、より大きな強度とより小さなエントロピーとを有しており、その結果として大きなQ値を有することになる。所定のシャープネスしきい値Teを設定して、シャープネススコアが該Teよりも小さいイメージをコレクションから除去するようにすることが可能である。
【００４５】
上記のシャープネススコアを使用する代わりに、他の実施形態では、イメージのシャープネス（又はシャープネスの欠如）を表すために他のタイプのスコアを使用することが可能である。
【００４６】
（ステップ308で）適用される関心フィルタは、関心フィルタリング基準を使用する。ユーザは、「関心」のない写真を撮る場合がある。関心がなく又は退屈なイメージは、色のバリエーションが少ないイメージとして識別することが可能である。「関心」スコアを定量化するために、上述した高速色量子化アルゴリズムをイメージに適用してその主要な色クラスタを抽出することが可能である。
【００４７】
次いで、最大色クラスタの平均色を有する均質な（homogeneous）基準イメージが生成される。こうすることにより、オリジナルイメージの「退屈」バージョンが生成され、該オリジナルイメージの色バリエーションが実際に低い場合には、該退屈なイメージからの「色距離（color distance）」が小さくなるはずである。オリジナルイメージと生成された退屈なイメージとの間の色距離を測定するために、該２つのイメージから抽出された色クラスタについてEMD距離が計算される。該計算されたEMD距離がしきい値Ti（所定値）と比較され、該Tiよりも低い関心スコア（EMD距離）を有するイメージがイメージコレクションから除去されることになる。
【００４８】
テーマベース・クラスタリング206が図４に示されている。上述したように、テーマベース・クラスタリングは、コンテンツベース・フィルタリング（図３のステップ204）を適用することによりオリジナルのイメージコレクションよりも一般に少数のイメージを含む削減された一組のイメージについて実行される。
【００４９】
テーマとは、時間、色、人々、及び場所といった何らかの特徴の類似性を一般に意味するものである。時間の類似性は（上述した）時差関数Dt(X,Y)を使用して計算することができ、色の類似性は（上述した）色距離関数Dc(X,Y)を使用して計算することができ、人々に基づく類似性は、顔検出関数F(X)に基づいて計算することができる。該顔検出関数F(X)は、イメージX内の顔の数を計算する。別の関数を使用して、２つのイメージにより表される場所の類似性を識別することができる。イメージのメタデータがGPS（Global Positioning System）座標を含む場合には、かかる位置情報を使用して、場所に従ったクラスタリングを行うことができる。
【００５０】
探索空間を削減するために、以下の合理的な観察が使用される：時間的に近接して撮影されたイメージには、それよりも時間的に離れているイメージよりも、クラスタリングアルゴリズムで共にグループ化されるべき一層高い優先順位が与えられるべきである。一組のイメージは、重複しない時間クラスタへと最初に分割される（ステップ402）。時刻t1,t2,...,tn+1に撮影され時間順に順序づけされた一連のイメージI1,I2,...,In+1について、時間間隔はg1,g2,...,gnである（gi=ti+1-ti）。一連のイメージを時間クラスタへと分割する単純な方法は、しきい値Gを選定し、該一連のイメージをあらゆる時間間隔gi（gi＞G）で部分集合へと分割することである。その結果として得られる一連のイメージの部分集合（時間クラスタ）は、S1,S2,...,Sm（m≦n+1）となる。
【００５１】
次いで、結果的に得られた各時間クラスタ内で、テーマベース・クラスタリングが、時間の類似性、色の類似性、顔の数、顔識別、場所の近接性、及び／又はその他のクラスタリング属性に基づく類似性を検出するための上述した関数を含む一組のグループ検出手段を使用したテーマグループ化の検出（ステップ404）を試行する。成功裏にグループ化されたイメージは、時間クラスタから除去されて（ステップ406）ページネーションのために送られる（ステップ208）。このプロセスが、時間クラスタ内に残っているイメージについて繰り返されて、該時間クラスタから更なるテーマクラスタが見出される。時間クラスタ内のイメージがなくなったとき、又は更なるクラスタが見出されない場合には、該アルゴリズムは、ステップ408で判定されるように一連の時間クラスタがなくなるまで、次の時間クラスタに対して繰り返し適用される。
【００５２】
この機構は、フォトアルバム中でイメージが出現する順番を、該イメージが撮影された時間順から切り離すことを可能にする。時間クラスタは、該フォトアルバム中でその時間順を維持するが、ページのグループ化に使用されるテーマベース・クラスタリングは、時間クラスタ内のイメージがフォトアルバム内で現れる際に該イメージを再順序づけさせることができる。
【００５３】
一実施形態では、テーマグループ検出器は次のように働く。所与の一組のイメージノードに関し、該検出器は、削減された一組のイメージの各イメージを表すノードの全てを含むテーマグラフを最初に構築する。次いで、以下の１つ又は２つ以上のテーマ条件が満たされた場合に２つのノード間の縁部が構築される：（関数Dc(X,Y)の出力の比較に基づき）イメージの色が色類似性に類似している、（時間しきい値に対する関数Dt(X,Y)の出力の比較に基づき）イメージの時間が近接している、（上述したように）各イメージにおける顔の数に基づきイメージが類似していると判定された、イメージが同じ人（人々）を含む、（２つのイメージ間の地理的な距離を計算する関数の出力と場所しきい値との比較に基づき）イメージが類似する場所で撮られている。次いで、テーマグラフの小集団又は接続された構成要素を見出すことにより、テーマグループを識別することができる。
【００５４】
幾つかの実施形態にしたがってページネーションソフトウェア110により実行することができる別のタスクは、フォトアルバムの表紙として使用するための表紙イメージの選択である。ページネーションソフトウェア110は、ページネーションの対象となる一組のイメージから表紙イメージ候補を選択する。突発的な活動は、関心のある事象に関係するものであると考えられる（「突発的」とは、短時間内に撮られた比較的多数枚のイメージを意味している）。それ故、表紙イメージ候補は、かかる突発的に撮られたイメージ内に存在するイメージである。各々の突発的に撮られたイメージから選択すべき表紙イメージ候補は、顔の数に関する基準（例えば、突発的に撮られたイメージから選択される表紙イメージ候補は、顔の数が最も多いイメージである）といった、幾つかの基準に基づくものとすることができる。別の実施態様では他の基準を使用することが可能である。
【００５５】
複数の表紙イメージ候補がユーザへ提示され、次いで該ユーザが、該表紙イメージ候補の中から、フォトアルバムに使用するための表紙イメージを選択することができる。
【００５６】
（図１のページネーションソフトウェア110を含む）上述したソフトウェアの命令は、ロードされてプロセッサ（図１の１つ又は２つ以上のCPU112）上で実行される。該プロセッサは、マイクロプロセッサ、マイクロコントローラ、（１つ又は２つ以上のマイクロプロセッサ又はマイクロコントローラを含む）プロセッサモジュール又はサブシステム、又はその他の制御装置又は計算装置を含む。本書で用いる場合、「プロセッサ」とは、単一の構成要素又は複数の構成要素（例えば、１つのCPU又は多数のCPU）を意味し得るものである。
【００５７】
データ及び（ソフトウェアの）命令は、個々の記憶装置に格納され、該記憶装置は、１つ又は２つ以上のコンピュータ読み取り可能記憶媒体又はコンピュータ使用可能記憶媒体として実施される。該記憶媒体は、ダイナミック又はスタティックランダムアクセスメモリ（DRAM又はSRAM）、EPROM（Erasable and Programmable Read-Only Memory）、EEPROM（Electrically Erasable and Programmable Read-Only Memory）及びフラッシュメモリ等の半導体メモリデバイス、固定ディスク、フロッピーディスク及びリムーバブルディスク等の磁気ディスク、テープを含む他の磁気媒体、及びコンパクトディスク（CD）又はディジタルビデオディスク（DVD）等の光媒体を含む、異なる形態の記憶手段を含む。上述のソフトウェアの命令は、１つのコンピュータ読み取り可能記憶媒体又はコンピュータ使用可能記憶媒体で提供することが可能であり、また代替的には、おそらくは複数のノードを有する大規模なシステムにおいて複数のコンピュータ読み取り可能記憶媒体又はコンピュータ使用可能記憶媒体で提供することが可能である、ということに留意されたい。かかる１つ又は２つ以上のコンピュータ読み取り可能記憶媒体又はコンピュータ使用可能記憶媒体は、物品（又は製品）の一部であるとみなされる。物品又は製品とは、製造された単一の構成要素又は複数の構成要素を意味し得るものである。
【００５８】
上記では、本発明の理解を提供するために様々な詳細について説明した。しかし、本発明は、それら詳細なしでも実施することが可能である、ということが当業者には理解されよう。限られた数の実施形態に関して本発明を開示したが、当業者であれば、かかる実施形態から様々な修正例及び変形が理解されよう。特許請求の範囲は、かかる修正及び変形を本発明の真の思想及び範囲内のものとして網羅するものである、ということが意図されている。
【図１】
2012507189.tif 000003
【図２】
2012507189.tif 000004
【図３】
2012507189.tif 000005
【図４】
2012507189.tif 000006
【国際調査報告】
2012507189.tif 000007
2012507189.tif 000008