(57)【特許請求の範囲】
【請求項１】
複数の画像から、所定の条件に基づいて画像の組を特定する組特定手段と、
前記組特定手段により前記画像の組が特定された後に、画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類するクラスタリング手段と、
前記クラスタリング手段によって生成された前記クラスタに含まれる画像のうち、前記画像の組を構成する画像をまとめて選択する画像選択手段と、
前記画像選択手段によって前記クラスタから選択された前記画像の組を構成する画像を、当該クラスタと一対一で対応している前記画像配置領域に配置する画像配置手段と、を有し、
前記クラスタリング手段は、前記組特定手段により特定された前記画像の組を構成する画像が同じクラスタに含まれるように、前記画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類することを特徴とする情報処理装置。
【請求項２】
前記クラスタリング手段は、撮影日時の順で相互に隣接する２つの画像の間を分割点として、撮影日時の順に並べられた前記複数の画像を複数に分け、当該複数に分けた画像ごとに同一の前記クラスタに分類するに際し、前記画像の組を構成する画像の間に前記分割点が位置しないようにすることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
それぞれに前記複数の画像の少なくとも１つが分類されるクラスタの候補であって、前記画像配置領域の数と同じ数のクラスタの候補のそれぞれについて評価値を、前記クラスタの候補の複数の組み合わせのそれぞれについて導出する導出手段を更に有し、
前記クラスタリング手段は、前記評価値に基づいて、前記複数のクラスタの候補の組み合わせから前記クラスタを決定することを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記画像選択手段は、１つの前記画像の組に含まれる画像が１つの前記クラスタに含まれていない場合であって、予め設定された条件を満たす場合に、当該クラスタとは別の前記クラスタから、当該画像の組に含まれる残りの画像の少なくとも１つを取得することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記画像選択手段は、１つの前記画像の組に含まれる画像が１つの前記クラスタに含まれていない場合に、当該画像の組を代表する予め設定された代表画像が、当該画像の組に含まれているか否かに基づいて、前記クラスタとは別の前記クラスタから、当該画像の組に含まれる画像を取得するか否かを判定することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記クラスタの候補の評価値は、値が大きいほど評価が高いことを示し、
前記クラスタリング手段は、撮影日時の順で相互に隣接する２つの画像の間を分割点として、撮影日時の順に並べられた前記複数の画像を複数に分け、当該複数に分けた画像ごとに同一の前記クラスタに分類するに際し、
撮影日時の順で相互に隣接する２つの画像の何れかを含む２つの前記クラスタの候補の組み合わせのそれぞれについて、２つのクラスタの候補の評価値の和、および差を算出し、当該２つのクラスタの候補の評価値の和が最も大きく、且つ、当該２つのクラスタの候補の評価値の差が最も小さい２つのクラスタの候補を前記クラスタとして決定することを特徴とする請求項３〜５の何れか１項に記載の情報処理装置。
【請求項７】
前記クラスタの候補の評価値は、前記クラスタに含まれる前記画像の組の数と、前記クラスタに含まれる画像の数であって前記画像の組を代表する予め設定された代表画像の数との少なくとも何れか一方が多いほど評価が高いことを示す値であることを特徴とする請求項３〜６の何れか１項に記載の情報処理装置。
【請求項８】
前記画像選択手段は、１つの前記クラスタに含まれる、前記画像の組を構成する画像の選択が終了した後、当該選択した画像の数が、前記画像配置領域に配置できる前記画像の数の上限値よりも少ない場合であって、当該クラスタに未選択の前記画像がある場合に、前記画像配置領域に配置できる前記画像の数の上限値を上限として、当該未選択の画像を選択することを特徴とする請求項１〜７の何れか１項に記載の情報処理装置。
【請求項９】
前記画像選択手段は、前記画像の評価値を導出し、前記未選択の画像のうち、前記画像の評価値が評価を高いことを示す画像から順に前記未選択の画像を選択することを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
情報処理装置が行う情報処理方法であって、
前記情報処理装置が有する組特定手段により、複数の画像から、所定の条件に基づいて画像の組を特定する組特定工程と、
前記情報処理装置が有するクラスタリング手段により、前記組特定工程において前記画像の組が特定された後に、画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類するクラスタリング工程と、
前記情報処理装置が有する画像選択手段により、前記クラスタリング工程において生成された前記クラスタに含まれる画像のうち、前記画像の組を構成する画像をまとめて選択する画像選択工程と、
前記情報処理装置が有する画像配置手段により、前記画像選択工程において前記クラスタから選択された前記画像の組を構成する画像を、当該クラスタと一対一で対応している前記画像配置領域に配置する画像配置工程と、を有し、
前記クラスタリング工程では、前記組特定工程において特定された前記画像の組を構成する画像が同じクラスタに含まれるように、前記画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類することを特徴とする情報処理方法。
【請求項１１】
請求項１〜９の何れか１項に記載の情報処理装置の各手段としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、デジタルカメラやスマートフォンの普及に伴い、撮影の機会は以前と比較して大きく増加してきている。また、撮影した写真を活用するため、フォトブックやスライドショーといった商材を作成するサービスの利用が広がっている。
このような商材を作成する場合、何の意図も持たずランダムに画像を選択し、配置することは稀であり、ある意図を持って商材に使用する画像の選択と、選択した画像の配置を行うのが一般的である。特に、ユーザの意図を表現するように画像を組み合わせることによって、商材に統一感やストーリー性を持たせることが考えられる。
【０００３】
このような場合において、ユーザの編集上の意図が込められた画像の組を特定し、商材の画像配置領域にまとめて配置することが望まれる。
特許文献１には、画像を配置する配置枠を一つ以上備えたテンプレートの当該配置枠に、配置すべき画像の条件を設定することが開示されている。特許文献１に記載の技術では、各々の配置枠に対して、編集上の意図に基づき一連の条件を設定することで、画像の組を特定することが可能である。
また、特許文献２には、撮影時間などの情報に基づき、入力された動画像や静止画像に対してグルーピングを行い、グループの中で画像の組を特定し、特定した画像の組のレイアウトを決定することが開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−３１２０５８号公報
【特許文献２】特開２０１２−４４６４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１、２に記載の技術では、編集上の意図を画像の組として表現することはできるものの、画像の組をまとめて選択・配置することができない。また、考えられる全ての画像の組を選択の対象とすることができない。従って、画像の組を画像配置領域にまとめて配置したとしても、ユーザの意図を十分に表現できない可能性がある。
【０００６】
特許文献１に記載の技術では、配置枠はそれぞれ独立している。従って、一連の条件を設定した複数の配置枠の全てにユーザの意図通りの画像が配置されるとは限らない。例えば、色味が青である画像が入力画像群に２枚含まれ、テンプレート内に３つの配置枠がある場合、３つの配置枠のうち２つの配置枠に色味が青である画像が配置される。この場合、特許文献１に記載の技術では、残りの１つの配置枠にユーザの意図する色味の画像が配置されるとは限られない。
【０００７】
また、特許文献２に記載の技術では、画像の組の特定はグルーピングの後に行われる。このため、単純に撮影間隔などに基づいて、入力画像群を複数のグループに分割する際の分割点が決定される。よって、ユーザの意図する画像の組が得られない場合がある。
【０００８】
本発明は、このような問題点に鑑みてなされたものであり、ユーザの意図する画像の組を画像配置領域にまとめて配置できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の情報処理装置は、複数の画像から、所定の条件に基づいて画像の組を特定する組特定手段と、前記組特定手段により前記画像の組が特定された後に、画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類するクラスタリング手段と、前記クラスタリング手段によって生成された前記クラスタに含まれる画像のうち、前記画像の組を構成する画像をまとめて選択する画像選択手段と、前記画像選択手段によって前記クラスタから選択された前記画像の組を構成する画像を、当該クラスタと一対一で対応している前記画像配置領域に配置する画像配置手段と、を有し、前記クラスタリング手段は、前記組特定手段により特定された前記画像の組を構成する画像が同じクラスタに含まれるように、前記画像配置領域の数と同じ数のクラスタの何れかに前記複数の画像を分類することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、ユーザの意図する画像の組を画像配置領域にまとめて配置することができる。
【図面の簡単な説明】
【００１１】
【図１】商材作成装置の機能構成の第１の例を示す図である。
【図２】商材作成装置のハードウェア構成を示す図である。
【図３】画像情報管理テーブルの構成の第１の例を示す図である。
【図４】組特定条件管理テーブルの構成を示す図である。
【図５】商材作成装置の全体の処理の第１の例を説明するフローチャートである。
【図６】ステップＳ５０３の詳細を説明するフローチャートである。
【図７】ステップＳ５０４の詳細を説明するフローチャートである。
【図８】クラスタ管理テーブルの構成を示す図である。
【図９】ステップＳ５０５の詳細を説明するフローチャートである。
【図１０】画像の組を特定してページに配置する様子を示す図である。
【図１１】クラスタの分割点を決定する様子の一例を示す図である。
【図１２】商材作成装置の機能構成の第２の例を示す図である。
【図１３】画像情報管理テーブルの構成の第２の例を示す図である。
【図１４】商材作成装置の全体の処理の第２の例を説明するフローチャートである。
【図１５】ステップＳ１４０１の詳細を説明するフローチャートである。
【図１６】ステップＳ１４０２の詳細を説明するフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら、実施形態を説明する。尚、以下の実施形態において示す構成は一例に過ぎず、本発明は以下の実施形態に限定されるものではない。
【００１３】
＜第１の実施形態＞
図１は、商材作成装置（情報処理装置）１０の機能構成の一例を示すブロック図である。尚、本実施形態では、商材の一例として、フォトブックを作成する場合について説明する。なお、商材作成装置は情報処理装置の一例であり、本発明は、その他の種々の装置に適用可能である。例えば、電子的なアルバムを作成する装置にも適用可能である。
画像入力部１０１は、ユーザが指定した画像群を入力し、画像管理部１０４に保管する。画像群は、ＣＤやＤＶＤ等の記憶メディアやインターネット等のネットワークを介して画像入力部１０１に入力されてもよい。画像管理部１０４は、画像入力部１０１に入力された画像群を保管する画像保管部と、図３に示す画像情報管理テーブル３０とを有する。画像情報管理テーブル３０の詳細については後述する。
【００１４】
画像情報取得部１０３は、画像管理部１０４に保管された画像群に対し、各画像が持つ撮影日時や撮影位置等のメタデータや、色平均値等の画像情報を取得する。画像情報取得部１０３で取得された画像情報は、その取得元である画像と相互に関連付けられて画像情報管理テーブル３０で管理される。
【００１５】
商材情報入力部１０２は、ユーザが入力した、商材に関する情報を入力する。商材に関する情報とは、例えば、フォトブックやスライドショー等といった商材の種類、商材のページ数、および１ページあたりの上限画像枚数等である。商材情報入力部１０２は、予め商材に関する情報を記述した設定ファイルを入力してもよい。
【００１６】
組特定条件管理部１０５は、予め定められた、画像の組を特定するための条件を、図４に示す組特定条件管理テーブル４０で管理する。尚、組特定条件管理テーブル４０の詳細については後述する。また、以下の説明では、「画像の組を特定するための条件」を必要に応じて「組特定条件」と称する。ユーザが指定した組特定条件を組特定条件管理テーブル４０に追加することにより、組特定条件をユーザが後から追加できるようにしてもよい。
【００１７】
組特定部１０６は、組特定条件管理テーブル４０で管理されている組特定条件を用いて、画像管理部１０４に保管されている画像群から、２つ以上の画像からなる画像の組を特定し、特定した画像の組に含まれる画像に同一の組ラベルを付与する。組ラベルの詳細については図３を参照しながら後述する。
【００１８】
画像クラスタリング部１０７は、商材情報入力部１０２で入力されたページ数と、クラスタ数とが一致するように入力画像群をクラスタリングし、複数のクラスタの何れかに、画像入力部１０１で入力した画像の何れかを分類する。
画像選択部１０８は、画像クラスタリング部１０７によって生成されたそれぞれのクラスタから、商材に使用する画像を１枚以上選択する。画像配置部１０９は、画像選択部１０８により選択された画像を、それぞれのページに配置する。このようにして商材が作成される。
【００１９】
図２は、商材作成装置１０のハードウェア構成の一例を示す図である。
ＣＰＵ（中央演算装置）２０１は、コンピュータシステムの制御を司る。ＣＰＵ２０１が、制御プログラムに基づいて、情報の演算や加工、各ハードウェアの制御を実行することにより後述する各機能構成、処理を実現する。ＲＡＭ（ランダムアクセスメモリ）２０２は、ＣＰＵ２０１の主メモリとして、実行プログラムのロードやプログラム実行に必要なワークメモリとして機能する。
【００２０】
ＲＯＭ（リードオンリーメモリ）２０３は、ＣＰＵ２０１の動作処理手順を規定する制御プログラムを記録している。ＲＯＭ２０３には、コンピュータシステムの機器制御を行うシステムプログラムである基本ソフト（ＯＳ）を記録したプログラムＲＯＭとシステムを稼働するために必要な情報等が記録されたデータＲＯＭがある。ＲＯＭ２０３の代わりに後述のＨＤＤ２０５を用いる場合もある。
【００２１】
ＮＥＴ ＩＦ（ネットワークインターフェース）２０４は、ネットワークを介して送受信されるデータの入出力制御を行う。ＨＤＤ（ハードディスクドライブ）２０５は、アプリケーションプログラム等のデータ保存用に用いられる。入出力バス２０６は、前述した各ユニット間を接続するためのものである。入出力バス２０６は、例えばアドレスバス、データバス、および制御バスを有する。
【００２２】
図３は、画像情報管理テーブル３０の構成の一例を示す図である。画像情報管理テーブル３０は、画像ＩＤ、画像名、組ラベル、撮影日時、撮影位置、色平均値、および顔タグのそれぞれの情報を相互に関連付けて記憶するテーブルである。
【００２３】
組ラベル列３０１には組ラベルが格納される。組ラベルは画像の組を特定するために用いられる。共通する組ラベルを持つ画像群を一つの画像の組として扱う。図３（ｂ）において、組ラベルの末尾に付加された数字（０１）は、同一の組特定条件に対して画像の組が複数生成された場合、それぞれの画像の組に対して一意な組ラベルを与えるためのものである。図３（ｂ）に示す例では、画像ＩＤが１、３、４である３つの画像が、同一の画像の組に含まれることを示す。顔タグ列３０５には、画像内に登場する各人物を一意に特定可能な文字列が格納されている。色平均値列３０４には、各画像のＲ値、Ｇ値、Ｂ値の平均値が色平均値として格納されている。
【００２４】
図４は、組特定条件管理テーブル４０の構成の一例を示す図である。組特定条件管理テーブル４０は、画像の組を特定するための条件（組特定条件）を管理するテーブルである。組特定条件管理テーブル４０は、条件ＩＤ、組ラベル、および組特定条件を相互に関連付けて記憶するテーブルである。
【００２５】
組ラベル列４０１には、対応する組特定条件によって特定された画像の組に含まれる画像に共通して与えられる文字列であって、組特定条件ごとに固有の文字列が格納されている。組特定条件列４０２には、画像の組を特定するための具体的な条件（すなわち、組特定条件の具体的な内容）が格納されている。
【００２６】
図５は、商材を作成する際の商材作成装置１０の全体の処理の一例を説明するフローチャートである。
まず、ステップＳ５０１において、画像入力部１０１は、商材に使用される画像群を入力する。画像情報取得部１０３は、入力したそれぞれの画像の画像情報を取得する。画像管理部１０４は、画像情報取得部１０３で取得された画像情報を、取得元の画像と相互に関連付けて画像情報管理テーブル３０に記憶する。
【００２７】
次に、ステップＳ５０２において、商材情報入力部１０２は、商材に関する情報を入力する。商材に関する情報として、例えば、ページ数や、１ページあたりの上限画像枚数が入力される。１ページあたりの上限画像枚数とは、１ページに配置することができる画像の枚数の上限値である。
次に、ステップＳ５０３において、組特定部１０６は、画像管理部１０４に保管されている画像群から画像の組を特定する。そして、組特定部１０６は、特定した画像の組に含まれる画像に同一の組ラベルを付与する。図３（ｂ）では、組ラベルが付与された後の状態の画像情報管理テーブル３０の一例を示す。ステップＳ５０３の詳細については、図６のフローチャートを参照しながら後述する。
【００２８】
次に、ステップＳ５０４において、画像クラスタリング部１０７は、ステップＳ５０１で入力された画像群を、商材のページ数とクラスタ数とが一致するようにクラスタリングする。ステップＳ５０４の詳細については、図７のフローチャートを参照しながら後述する。尚、ここでは商材の編集単位をページ単位とする場合を例に挙げて説明する。しかしながら、例えば、ページ２枚からなる見開きを編集単位としたり、１枚のページを複数の編集単位に分割したりしてもよい。クラスタリング処理では、編集単位の数に合わせてクラスタの数を決定する。
【００２９】
次に、ステップＳ５０５において、画像選択部１０８は、ステップＳ５０４で生成された各クラスタから、共通する組ラベルを持つ画像の組を選択する。ステップＳ５０５の詳細については、図９のフローチャートを参照しながら後述する。
【００３０】
次に、ステップＳ５０６において、画像配置部１０９は、ステップＳ５０４で生成された各クラスタと商材の各ページとを一対一に対応させ、各クラスタから選択された画像群を、当該クラスタに対応するページに配置することで商材を作成する。画像配置部１０９は、画像を配置する配置枠を複数備えたテンプレートを予め多数用意し、ステップＳ５０５で選択された画像の枚数と内容との少なくとも何れか１つに基づいて、テンプレートをページごとに選択することができる。また、画像配置部１０９は、ステップＳ５０３において特定された画像の組の情報を用いて、当該画像の組に含まれる画像を同一のページにまとめて配置することができる。本実施形態では、フォトブックを作成する場合を例に挙げて説明しているので、ページに対して画像群が割り当てられる。フォトブックとは異なる種類の商材を作成する場合、例えばスライドショーを商材とする場合、画像配置部１０９は、一つ以上続く小節等、商材の種類に応じた画像配置領域に対して画像の組に含まれる画像を配置すれば（割り当てれば）よい。画像配置領域は、紙を用いたフォトブックであれば紙面であり、電子アルバムであれば、背景となる画像の領域である。
【００３１】
図６は、図５のステップＳ５０３の詳細を説明するフローチャートである。前述したように、ステップＳ５０３では、ステップＳ５０１で入力された画像群から画像の組が特定される。
まず、ステップＳ６０１において、組特定部１０６は、カウンタｉに１を設定する。カウンタｉは、組特定条件管理テーブル４０に含まれる組特定条件を特定するためのものである。本実施形態では、カウンタｉは、組特定条件管理テーブル４０の条件ＩＤの値に対応するものとする。
【００３２】
次に、ステップＳ６０２において、組特定部１０６は、組特定条件管理テーブル４０の先頭からｉ番目の組特定条件を取得する。
次に、ステップＳ６０３において、組特定部１０６は、ステップＳ６０２で取得した組特定条件を満たす画像群をグループ化する。例えば、組特定条件４０４が取り出された場合、組特定部１０６は、撮影位置が所定の範囲内に収まっており、かつ、色平均値の類似度が閾値以上の複数の画像が同一のグループに含まれるようにグループを生成する。このようなグループは複数生成される可能性がある。例えば、相互に離れた複数の撮影位置のそれぞれにおいて、このような組特定条件４０４が成立する場合があるからである。ここで、組特定条件４０４には、撮影位置と色平均値とが使われている。このため、組特定部１０６は、画像情報管理テーブル３０の撮影位置列３０３および色平均値列３０４を参照して、必要な画像情報を取得する。尚、組特定条件は、図４に示した組特定条件４０４、４０５に限定されず、例えば、画像の属性（画像に付加されるメタデータや画像そのものから得られる情報）に基づく条件であれば、どのような条件であってもよい。
【００３３】
次に、ステップＳ６０４において、組特定部１０６は、カウンタｊに１を設定する。カウンタｊは、ステップＳ６０３で生成されたグループを特定するためのものである。
次に、ステップＳ６０５において、組特定部１０６は、ステップＳ６０３で生成された複数のグループからｊ番目のグループを取得する。
【００３４】
次に、ステップＳ６０６において、組特定部１０６は、ｊ番目のグループに含まれる画像に対して、同一の組ラベルを付与する。ここで付与される組ラベルは、ステップＳ６０２で取得した組特定条件４０４に対応する組ラベル４０３である。画像情報管理テーブル３０の行３０６、３０８、３０９の組ラベル列３０１には、同一の組ラベルが格納されている。したがって、行３０６、３０８、３０９の画像ＩＤを有する３つの画像が１つの組として特定されたことを示す。
【００３５】
次に、ステップＳ６０７において、組特定部１０６は、カウンタｊの値をインクリメントする。
次に、ステップＳ６０８において、組特定部１０６は、ステップＳ６０３で生成された全てのグループについて、ステップＳ６０６の処理が完了したか否かを判定する。この判定の結果、未処理のグループがある場合には、ステップＳＳ６０５へ戻り、未処理のグループについてステップＳ６０５、Ｓ６０６の処理を行う。そして、全てのグループについて処理が完了すると、ステップＳ６０９へ進み、組特定部１０６は、カウンタｉの値をインクリメントする。
【００３６】
次に、ステップＳ６１０において、組特定部１０６は、組特定条件管理テーブル４０に含まれる全ての組特定条件についてステップＳ６０３〜Ｓ６０９の処理が完了したか否かを判定する。この判定の結果、未処理の組特定条件がある場合には、ステップＳ６０２に戻り、前述したように、未処理の組特定条件を満たす画像群のグループ化と、それぞれのグループに含まれる画像に組ラベルを付与する処理が行われる。そして、全ての組特定条件について処理が完了すると、図６のフローチャートを終了し、図５のステップＳ５０４の処理に進む。
図７は、図５のステップＳ５０４の詳細を説明するフローチャートである。前述したように、ステップＳ５０４では、ステップＳ５０１で入力された画像群を、商材のページ数とクラスタ数とが一致するようにクラスタリングする。
【００３７】
まず、ステップＳ７０１において、画像クラスタリング部１０７は、ステップＳ５０１で入力された画像群を時系列（撮影日時順）に整列する。
次に、ステップＳ７０２において、画像クラスタリング部１０７は、ステップＳ５０１で入力された画像群の全てを要素とする初期クラスタを生成する。
【００３８】
図８は、クラスタ管理テーブル８０の構成の一例を示す図である。クラスタ管理テーブル８０は、クラスタＩＤ、クラスタの先頭画像の画像ＩＤ８０１、クラスタの先頭画像の撮影日時８０２、クラスタの末尾画像の画像ＩＤ８０３、およびクラスタの末尾画像の撮影日時８０４を相互に関連付けて記憶するテーブルである。クラスタ管理テーブル８０は、図７のフローチャートによる処理の際にクラスタを管理するためのものである。
【００３９】
クラスタ管理テーブル８０の各行は、それぞれ１つのクラスタを表す。初期クラスタを生成した時点では、図８（ａ）のクラスタ管理テーブル８０に示すように、一件のみエントリが登録されており、全ての画像が一つのクラスタに属する。
【００４０】
次に、ステップＳ７０３において、画像クラスタリング部１０７は、撮影間隔の閾値を設定する。ここで、撮影間隔とは、時系列に整列した画像群において、ある画像とその次の画像の撮影日時の差である。
次に、ステップＳ７０４において、画像クラスタリング部１０７は、時系列に並べた画像群において相互に隣接する２つの画像の間の位置であって、ステップＳ７０３で設定した閾値よりも大きい撮影間隔を有する位置をクラスタ分割の候補点として取得する。以下の説明では、この「クラスタ分割の候補点」を必要に応じて「分割候補点」と称する。具体的に画像クラスタリング部１０７は、時系列に並べた画像群を先頭から走査し、閾値よりも撮影間隔が大きい位置を分割候補点として取得する。
【００４１】
次に、ステップＳ７０５において、画像クラスタリング部１０７は、ステップＳ７０４において１つ以上の分割候補点を取得できたか否かを判定する。この判定の結果、分割候補点を１つも取得できなかった場合、ステップＳ７１４に進む。ステップＳ７１４に進むと、画像クラスタリング部１０７は、エラーメッセージを出力し、図７のフローチャートを終了する。この場合には、図５のフローチャート自体も終了する。
【００４２】
一方、ステップＳ７０５において、分割候補点を１つ以上取得できたと判定された場合には、ステップＳ７０６に進む。ステップＳ７０６に進むと、画像クラスタリング部１０７は、カウンタｉに１を設定する。カウンタｉは、ステップＳ７０４で取得された分割候補点を特定するためのものである。
【００４３】
次に、ステップＳ７０７において、画像クラスタリング部１０７は、ステップＳ７０４で取得された分割候補点群からｉ番目の分割候補点を取得する。
次に、ステップＳ７０８において、画像クラスタリング部１０７は、ｉ番目の分割候補点でクラスタを分割できるか否かを判定する。具体的に画像クラスタリング部１０７は、ｉ番目の分割候補点でクラスタを分割した場合に、画像の組が別のクラスタに分かれることがない場合に、ｉ番目の分割候補点でクラスタを分割できると判定する。一方、そうでない場合、画像クラスタリング部１０７は、ｉ番目の分割候補点でクラスタを分割できないと判定する。
【００４４】
この判定の結果、ｉ番目の分割候補点でクラスタを分割できる場合には、ステップＳ７０９に進む。ステップＳ７０９に進むと、画像クラスタリング部１０７は、ステップＳ７０７で取得した分割候補点を分割点として決定し、当該分割点でクラスタを分割する。図８（ｂ）のクラスタ管理テーブル８０は、初期クラスタを分割した後のクラスタの状態を示す。図８（ｂ）のクラスタ管理テーブル８０では、エントリが２件となり、初期クラスタが画像ＩＤ＝１の画像から画像ＩＤ＝３６の画像までのクラスタと、画像ＩＤ＝３７から画像ＩＤ＝７５の画像との２つのクラスタに分割されたことを示す。図８（ｂ）に示す例では、画像ＩＤ＝３６の画像と画像ＩＤ＝３７の画像の撮影間隔が閾値よりも大きく、これらの画像の間の位置が、ステップＳ７０９で使用された分割点である。
【００４５】
次に、ステップＳ７１０において、画像クラスタリング部１０７は、ステップＳ７０９で分割した後のクラスタの数と、商材（フォトブック）のページ数とが等しいか否かを判定する。この判定の結果、クラスタの数と商材のページ数とが等しい場合には、図７のフローチャートによる処理を終了し、図５のステップＳ５０５に進む。
【００４６】
一方、クラスタの数と商材のページ数とが等しくない場合には、クラスタを更に分割する必要がある。そこで、ステップＳ７１１に進み、画像クラスタリング部１０７は、カウンタｉの値をインクリメントする。
次に、ステップＳ７１２において、画像クラスタリング部１０７は、ステップＳ７０４で取得した全ての分割候補点について、分割の可否の判定を完了したか否かを判定する。この判定の結果、全ての分割候補点について、分割の可否の判定を完了していない場合には、ステップＳ７０７に戻り、前述したように、残りの分割候補点から新たに分割候補点を取得し、当該分割候補点での分割の可否の判定を行う。
【００４７】
そして、全ての分割候補点について、分割の可否の判定が完了すると、ステップＳ７１３に進む。ステップＳ７１３に進むと、画像クラスタリング部１０７は、撮影間隔の閾値を引き下げる。そして、ステップＳ７０４に進む。そして、新たな閾値に基づいて新たな分割候補点群を取得し、各分割候補点での分割の可否の判定とクラスタの分割を行う。
【００４８】
一方、ステップＳ７０８の判定の結果、ｉ番目の分割候補点でクラスタを分割できない場合、すなわち、ステップＳ７０７で取得した分割候補点でクラスタを分割した場合に画像の組が別のクラスタに分かれてしまう場合には、クラスタの分割は行われない。この場合には、ステップＳ７０８から前述したステップＳ７１１に進む。
【００４９】
図９は、図５のステップＳ５０５の詳細を説明するフローチャートである。前述したように、ステップＳ５０５では、ページ数とクラスタ数とが一致するように分割されたクラスタから、同一の組ラベルを持つ画像の組をまとめて選択する。
まず、ステップＳ９０１において、画像選択部１０８は、カウンタｉに１を設定する。カウンタｉは、ステップＳ５０４で得られたクラスタを特定するためのものである。本実施形態では、カウンタｉは、図８のクラスタ管理テーブル８０のクラスタＩＤに対応するものとする。
【００５０】
次に、ステップＳ９０２において、画像選択部１０８は、クラスタ管理テーブル８０を参照し、先頭からｉ番目のクラスタを１つ取得する。
次に、ステップＳ９０３において、画像選択部１０８は、ステップＳ９０２で取得したクラスタに画像の組が含まれているか否かを判定する。ここで、クラスタに画像の組が含まれているかどうか調べるには、クラスタに含まれる画像の画像ＩＤをキーとして、画像情報管理テーブル３０の組ラベル列３０１を参照すればよい。同一の組ラベルを持つ画像群が画像の組である。
【００５１】
この判定の結果、クラスタに画像の組が含まれていれば、ステップＳ９０４に進み、画像選択部１０８は、カウンタｊに１を設定する。カウンタｊは、ｉ番目のクラスタに含まれる画像の組を特定するためのものである。
次に、ステップＳ９０５において、画像選択部１０８は、クラスタに含まれているｊ番目の画像の組を取得する。このようにしてクラスタに含まれている画像の組を選択するのは、クラスタには、画像の組が複数含まれている可能性があるからである。
次に、ステップＳ９０６において、画像選択部１０８は、ｊ番目の画像の組に含まれる画像の数が、１ページあたりの上限画像枚数を超えるか否かを判定する。ここでページあたりの上限画像枚数は、図５のステップＳ５０２で取得した商材に関する情報を利用してもよいし、クラスタのサイズに比例させて決定してもよい。
【００５２】
この判定の結果、ｊ番目の画像の組に含まれる画像の数が、１ページあたりの上限画像枚数を超えない場合には、ステップＳ９０７に進む。ステップＳ９０７に進むと、画像選択部１０８は、ステップＳ９０５で取得した画像の組をまとめて選択する。そして、ステップＳ９０８に進む。一方、ｊ番目の画像の組に含まれる画像の数が、１ページあたりの上限画像枚数を超える場合には、ステップＳ９０７を省略してステップＳ９０８に進む。
【００５３】
ステップＳ９０８に進むと、画像選択部１０８は、カウンタｊの値をインクリメントする。
次に、ステップＳ９０９において、画像選択部１０８は、ステップＳ９０２において取得したｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ９０６〜Ｓ９０８の処理が完了したか否かを判定する。この判定の結果、ｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ９０６〜Ｓ９０８の処理が完了していない場合には、ステップＳ９０５に戻る。そして、ｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ９０６〜Ｓ９０８の処理が完了するまで、ステップＳ９０５〜Ｓ９０９の処理を繰り返し行う。
【００５４】
以上のようにしてｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ９０６〜Ｓ９０８の処理が完了すると、ステップＳ９１０に進む。ステップＳ９１０に進むと、画像選択部１０８は、ステップＳ９０７で選択した画像の組に含まれる画像の数が、１ページあたりの上限画像枚数を超えるか否かを判定する。この判定の結果、画像の組に含まれる画像の数が、１ページあたりの上限画像枚数を超えず、さらに画像を選択する余裕がある場合には、ステップＳ９１３に進む。
【００５５】
ステップＳ９１３に進むと、画像選択部１０８は、ｉ番目のクラスタに未選択の画像が残っているか否かを判定する。この判定の結果、未選択の画像がまだ残っている場合には、ステップＳ９１４に進む。ステップＳ９１４に進むと、画像選択部１０８は、未選択の画像から１枚の画像を選択する。例えば、画像に対する評価値が最も高い画像を選択することができる。彩度が高い画像、三分割法等の基本的な構図に従っている画像、登場人物が多い画像、および登場人物の表情が豊かな画像等に対して高評価を与えるような公知の手法によって、画像に対する評価値を算出することができる。尚、以下の説明では、「画像に対する評価値」を必要に応じて「画像評価値」と称する。
【００５６】
そして、ステップＳ９１０に戻る。ステップＳ９１４からステップＳ９１０に戻った場合には、ステップＳ９０７で選択した画像の組に含まれる画像の数と、ステップＳ９１４で選択した画像の数との和が、１ページあたりの上限画像枚数を超えるか否かを判定する。
【００５７】
以上のようにしてステップＳ９１０において、画像の数が、１ページあたりの上限画像枚数を超えると判定されると、ステップＳ９１１に進む。ステップＳ９１１に進むと、画像選択部１０８は、カウンタｉの値をインクリメントする。
次に、ステップＳ９１２において、画像選択部１０８は、クラスタ管理テーブル８０に登録されている全てのクラスタについての処理が完了したか否かを判定する。この判定の結果、全てのクラスタについての処理が完了していない場合には、ステップＳ９０２に戻る。そして、クラスタ管理テーブル８０に登録されている全てのクラスタについての処理が完了するまで、ステップＳ９０２〜Ｓ９１４の処理を繰り返し行う。
そして、クラスタ管理テーブル８０に登録されている全てのクラスタについての処理が完了すると、図９のフローチャートによる処理を終了する。
【００５８】
以上のように本実施形態では、組特定条件を満たす画像の組を特定し、特定した画像の組が維持されるように、（画像の組を特定した後に）画像のクラスタリングを行う。したがって、ユーザの編集上の意図を、画像の組によって表現することができる。また、それらの画像の組を商材の画像配置領域にまとめて配置することが可能となり、商材に統一性やストーリー性を持たせることができる。
【００５９】
図１０は、組特定条件に基づいて画像の組を特定し、特定した画像の組をページに配置する様子の一例を示す図である。図１０（ａ）は、商材作成装置１０に入力された画像群の一例を示し、図１０（ｂ）は、図１０（ａ）に示す画像群から画像の組を特定し、特定した画像の組をページに配置する様子を示す。図１０では、組特定条件が「ページ全体の色味を揃える」ことであり、１ページの配置枠が３つである場合を例に挙げて説明する。
【００６０】
この場合、図１０（ａ）に示す画像群には、３つの配置枠１００１ａ〜１００１ｃを同じ色味で揃えるための十分な数の画像が存在しない。本実施形態では、このような組特定条件を満たすような画像の組が存在しない場合、画像の組の特定を諦め、例えば、前述の画像評価値に基づいて配置する画像を決定する。そのため、特許文献１に記載の技術のように、画像の組を不完全な形で揃えることで結果的にページ全体の品質が低下することを防ぐことができる。
【００６１】
図１１は、画像の組の特定を予め行った後、商材作成装置１０に入力された画像を時系列に整列し、撮影間隔の大きさによってクラスタの分割点を決定する様子の一例を示す図である。
本実施形態では、クラスタリングに先立って画像の組の特定を行う。このため、クラスタリング時に画像の組の情報を参考にすることができる。特許文献２の記載の技術では、クラスタリング時に画像の組の情報がないため、単純に大きな撮影間隔で分割点を決定する。したがって、ユーザの意図する画像の組が得られない場合がある。これに対し、本実施形態では、図１１に示すように、撮影間隔が大きい画像２、３の間の分割点ではなく、画像３、４の間の分割点で複数の画像１〜６を分割し、同じ画像の組の画像１、２、３については、同じクラスタに分類されるようにする。このように本実施形態では、画像の組を無視したクラスタの分割を防ぐことができ、同一のクラスタに画像の組をおさめることができる。よって、ユーザの意図する画像の組を得ることができる。
【００６２】
＜第２の実施形態＞
次に、第２の実施形態について説明する。第１の実施形態では、特定された画像の組が同一のクラスタに属すようにクラスタリングを行い、個々のクラスタから画像の組をまとめて選択することで商材を作成する場合を例に挙げて説明した。
例えば、撮影日時に基づいたクラスタリングを行う場合に、時間的に離れた画像の組を同一のクラスタに含めようとすると、非常に大きなクラスタが生成される。例えば、フォトブックの１ページに１クラスタを割り当てる場合、このような状態では、各ページに割り当てられる画像の枚数に大きな偏りができる虞がある。
【００６３】
そこで、本実施形態では、クラスタリングの段階において、分割後のクラスタの状態を評価するためのスコア（クラスタスコア）を導出し、当該クラスタスコアに基づいたクラスタリングを行うことにより、画像の組が複数のクラスタに跨ることを許容する。このように本実施形態と第１の実施形態とでは、分割後のクラスタの状態を評価するためのスコア（クラスタスコア）を用いることによる構成および処理が主として異なる。したがって、本実施形態の説明において、第１の実施形態と同一の部分については、図１〜図１１に付した符号と同一の符号を付す等して詳細な説明を省略する。
【００６４】
図１２は、商材作成装置１２０の機能構成の一例を示すブロック図である。本実施形態の商材作成装置１２０は、第１の実施形態の商材作成装置１０の機能構成に対し、クラスタスコアを算出するクラスタスコア算出部１２０１と、重要な画像を特定する重要画像特定部１２０２とを加えたものである。
【００６５】
クラスタスコア算出部１２０１は、クラスタに含まれる画像の組の数や重要な画像の数に基づいて、クラスタスコアを算出する。本実施形態では、クラスタスコアは、画像の組や重要な画像をより多く含むクラスタほど評価が高いことを示す値として大きな値を示すものとする。重要画像特定部１２０２は、画像入力部１０１に入力された画像群を対象として、第１の実施形態で説明した画像評価値が閾値を超える画像や、予めユーザによってお気に入りの画像として指定された画像を重要な画像として特定する。
【００６６】
図１３は、画像情報管理テーブル１３０の構成の一例を示す図である。本実施形態の画像情報管理テーブル１３０は、第１の実施形態の画像情報管理テーブル３０に重要画像フラグを加えたものである。重要画像フラグ列１３０６には、ある画像が重要な画像であることを示すフラグが格納される。図１３では、重要な画像に対して値が１の重要フラグを付与する場合を例に挙げて示す。
【００６７】
図１４は、商材を作成する際の商材作成装置１２０の全体の処理の一例を説明するフローチャートである。
第１の実施形態の処理（図５）との主な差異は、図５のステップＳ５０４、Ｓ５０５の代わりに、それぞれステップＳ１４０１、Ｓ１４０２が実行される点である。
【００６８】
図１４のステップＳ５０１では、第１の実施形態と同様に、画像入力部１０１は、商材に使用される画像群を入力し、画像情報取得部１０３は、当該画像群のそれぞれの画像に対して、画像情報を取得する。画像管理部１０４は、この画像情報を、取得元の画像と相互に関連付けて画像情報管理テーブル１３０に保管する。ここで、本実施形態においては、ステップＳ５０１において、商材に使用する画像群が入力されると、重要画像特定部１２０２は、当該画像群に含まれる画像のうち、重要な画像を特定する。ある画像が重要な画像として特定された場合、画像管理部１０４は、画像情報管理テーブル１３０の対応する行の重要画像フラグ列１３０６に重要フラグを立てる（重要フラグとしての値として１を付与する）。図１４のステップＳ５０２、Ｓ５０３、Ｓ５０６は、それぞれ図５における該当する処理と同様の処理である。
【００６９】
本実施形態では、ステップＳ５０３において、図４の組特定条件４０４、４０５によって画像の組が特定される場合を例に挙げて説明する。図１３（ｂ）の画像情報管理テーブル１３０では、ステップＳ５０３の処理によって画像の組が特定された様子を示す。行１３０１、１３０３、１３０４と、行１３０２、１３０５の組ラベル列３０１には、それぞれ同一の組ラベルが格納されている。前者は、時間的に近い（撮影日時が近い）画像の組であり、後者は時間的に離れた（撮影日時が離れた）画像の組である。後者のような画像の組は、第１の実施形態のような撮影日時に基づいたクラスタリング処理では、別々のクラスタに分かれる。
【００７０】
そこで、ステップＳ１４０１において、画像クラスタリング部１２０３は、クラスタスコアに基づいて、ステップＳ５０１で入力された画像群を、商材のページ数とクラスタ数とが一致するようにクラスタリングする。ステップＳ１４０１の詳細については、図１５のフローチャートを参照しながら後述する。クラスタスコアに基づくクラスタリングでは、画像の組は同一のクラスタに含まれることもあるし、別々のクラスタに分かれることもある。尚、ここでは商材の編集単位をページ単位とする場合を例に挙げて説明する。しかしながら、例えば、ページ２枚からなる見開きを編集単位としたり、１枚のページを複数の編集単位に分割したりしてもよい。クラスタリング処理では、編集単位の数に合わせてクラスタの数を決定してよい。また、クラスタリングの基準に、前述の画像評価値、撮影位置、および登場人物の少なくとも何れか１つを用いてもよい。
【００７１】
ステップＳ１４０２において、画像選択部１２０４は、画像の組の選択を行う。画像選択部１２０４は、画像の組が同一のクラスタに含まれる場合と別々のクラスタに分かれる場合とのどちらにおいても、画像の組をまとめて選択する。ステップＳ１４０２の詳細については、図１６のフローチャートを参照しながら後述する。
図５を参照しながら説明したように、ステップＳ１４０２で選択された画像の組は、画像配置部１０９により、商材の画像配置領域にまとめて配置され、商材が作成される。
【００７２】
図１５は、図１４のステップＳ１４０１の詳細を説明するフローチャートである。第１の実施形態で説明した図７のフローチャート（ステップＳ５０４）との差異は、クラスタを分割する条件に関する部分である。具体的には、クラスタを分割候補点で分割した際に、画像の組を分割してしまうか否かを判定するステップＳ７０８が、クラスタスコアに基づく分割の可否を判定するステップＳ１５０２に置き換わる。また、ステップＳ１５０２の直前に、クラスタスコアを算出するステップＳ１５０１が挿入される。
【００７３】
ステップＳ１５０１では、クラスタスコア算出部１２０１は、ステップＳ７０７で取得された分割候補点でクラスタを分割した際にできる、分割後の２つのクラスタそれぞれについて、クラスタスコアを算出する。前述したように、クラスタスコアは、クラスタに含まれる画像の組の数や重要な画像の枚数が多いほど大きな値となるように算出される。画像の組の数を取得するために、クラスタスコア算出部１２０１は、まず、画像情報管理テーブル１３０を参照して、画像全体で同一の組ラベルを持つ画像群（画像の組）を取得する。次に、クラスタスコア算出部１２０１は、クラスタスコアの算出対象となっているクラスタ内において、構成画像が全て含まれる画像の組の個数を数える。あるクラスタに、画像の組に構成画像が全て含まれているか否かを確かめるには、画像の組を構成する画像の画像ＩＤをキーとして、クラスタ管理テーブル８０を参照すればよい。
【００７４】
次に、ステップＳ１５０２において、画像クラスタリング部１２０３は、ステップＳ１５０１で算出されたクラスタスコアに基づいて、クラスタの分割の可否を判定する。重要な画像が全てのクラスタにできるだけまんべんなく配分され、画像の組を構成する画像ができるだけ同一のクラスタに含まれるように、クラスタの分割点を決定する。そのような分割点を決定するために、本実施形態では、画像クラスタリング部１２０３は、分割後に撮影日時の順で相互に隣接する２つのクラスタスコアの和が最大、かつ、当該２つのクラスタスコアの差が最小となる分割点を分割候補点から選択する。分割後に撮影日時の順で相互に隣接する２つのクラスタのクラスタスコア和が最大となるような場合は、画像の組が同一のクラスタに含まれるような場合である。また、分割後に撮影日時の順で相互に隣接する２つのクラスタのクラスタスコア差が最小となるような場合は、重要な画像が２つのクラスタにまんべんなく分配されているような場合である。
以上のようにクラスタの分割点を決定する部分以外については、第１の実施形態で説明した図７のフローチャートと同じであるため、その詳細な説明を省略する。
【００７５】
図１６は、図１４のステップＳ１４０２の詳細を説明するフローチャートである。第１の実施形態で説明した図９のフローチャート（ステップＳ５０５）との差異は、画像の組が別々のクラスタに分かれた場合に対応する部分である。具体的には、クラスタに含まれる画像の組を取得するステップＳ９０５の後に、ステップＳ９０５で取得した画像の組を構成する画像が全て同一のクラスタに含まれるか、他のクラスタに分かれているか判定するステップＳ１６０１が追加される。さらに、ステップＳ１６０１で、画像の組の一部が他のクラスタに分かれていると判定されると、その画像の組の一部を他のクラスタから取得するためのステップＳ１６０２、Ｓ１６０３の処理が行われる。
【００７６】
図１６のステップＳ９０１〜Ｓ９０５は、図９の該当する処理と同じである。すなわち、図１５のフローチャートによる処理によって生成されたクラスタを１つずつ取得し、各クラスタに含まれる各画像の組について以下の処理を行う。
【００７７】
まず、ステップＳ１６０１において、画像選択部１２０４は、ステップＳ９０５で取得したｊ番目の画像の組が完全であるか否か判定する。ここで、画像の組が完全であるとは、同一の組ラベルが付与された画像群が、その画像の組にもれなく含まれていることを指す。すなわち、画像の組が完全であるとは、画像の組の一部が他のクラスタに分かれていないことを示す。
【００７８】
この判定の結果、ステップＳ９０５で取得したｊ番目の画像の組が完全でない、つまり、画像の組の一部が他のクラスタに属している状態である場合には、ステップＳ１６０２に進む。そうでない場合には、ステップＳ１６０２、Ｓ１６０３を省略してステップＳ９０６に進む。
【００７９】
一方、ステップＳ１６０２に進む場合、ステップＳ９０５で取得したｊ番目の画像の組は完全ではなく、その一部はｉ番目のクラスタ以外の他のクラスタに存在する。そこで、ステップＳ１６０２において、画像選択部１２０４は、この不完全な画像の組と同じ組に属する画像（構成画像）を、ｉ番目のクラスタ以外の他のクラスタから取得するか否かを判定する。例えば、ステップＳ５０３において、画像の組の中で最も前述の画像評価値が高い画像を予め代表画像と定めておき、不完全な画像の組に代表画像が含まれているか否かをステップＳ１６０２の判定基準とすることができる。また、画像の組の中で最も撮影日時が新しい画像を代表画像としてもよい。この場合、例えば、不完全な画像の組に代表画像が含まれていないと、当該構成画像を他のクラスタから取得することができる。
【００８０】
この判定の結果、不完全な画像の組と同じ組に属する画像（構成画像）を、ｉ番目のクラスタ以外の他のクラスタから取得する場合には、ステップＳ１６０３に進む。ステップＳ１６０３に進むと、画像選択部１２０４は、不完全な画像の組と同じ組に属する画像（構成画像）を、ｉ番目のクラスタ以外の他のクラスタから取得する。一方、不完全な画像の組と同じ組に属する画像（構成画像）を、ｉ番目のクラスタ以外の他のクラスタから取得しない場合には、ステップＳ９０８に進む。
【００８１】
ステップＳ９０６において、画像選択部１２０４は、ステップＳ９０５で取得した画像の組に含まれる画像の数と、ステップＳ１６０３で取得した画像の数との和が、ページあたりの上限画像枚数を超えるか否かを判定する。ステップＳ１６０３の処理を行っていない場合には、ステップＳ１６０３で取得した画像の数は０（ゼロ）になることは言うまでもない。
【００８２】
この判定の結果、ステップＳ９０５で取得した画像の組に含まれる画像の数と、ステップＳ１６０３で取得した画像の数との和が、ページあたりの上限画像枚数を超えない場合には、ステップＳ９０７に進む。ステップＳ９０７に進むと、画像選択部１２０４は、ステップＳ９０５で取得した画像の組に、ステップＳ１６０３で取得した画像を含め、当該画像の組をまとめて選択する。そして、ステップＳ９０８に進む。
一方、ステップＳ９０５で取得した画像の組に含まれる画像の数と、ステップＳ１６０３で取得した画像の数との和が、１ページあたりの上限画像枚数を超える場合には、ステップＳ９０７を省略してステップＳ９０８に進む。
【００８３】
ステップＳ９０８に進むと、画像選択部１２０４は、カウンタｊの値をインクリメントする。
次に、ステップＳ９０９において、画像選択部１２０４は、ステップＳ９０２において取得したｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ１６０１〜Ｓ１６０３、Ｓ９０６〜Ｓ９０８の処理が完了したか否かを判定する。この判定の結果、ｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ１６０１〜Ｓ１６０３、Ｓ９０６〜Ｓ９０８の処理が完了していない場合には、ステップＳ９０５に戻る。そして、ｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ１４０１〜Ｓ１４０３、ステップＳ９０６〜Ｓ９０８の処理が完了するまで、ステップＳ９０５、Ｓ１６０１〜Ｓ１６０３、Ｓ９０６〜Ｓ９０９の処理を繰り返し行う。
【００８４】
以上のようにしてｉ番目のクラスタに含まれる全ての画像の組について、ステップＳ１６０１〜Ｓ１６０３、Ｓ９０６〜Ｓ９０８の処理が完了すると、ステップＳ９１０に進む。
以降の処理（Ｓ９１０〜Ｓ９１４）は、選択済みの画像の数が、１ページあたりの上限画像枚数に満たない場合に、ｉ番目のクラスタ内の画像のうち前述の画像評価値の高い画像から順に一つずつ画像を取得する処理であり、図９の該当する処理と同様である。したがって、ここでは、かかる処理の詳細な説明を省略する。
【００８５】
以上のように本実施形態では、分割後の２つのクラスタスコアの和が最大となり、且つ、当該クラスタスコアの差が最小になるような分割点を、分割候補点から選択し、選択した分割点で別々のクラスタに画像群を分ける。したがって、商材作成装置１２０に入力された画像群に時間的に離れた（撮影日時が離れた）画像の組が含まれていても、柔軟にクラスタリングを行うことができる。柔軟なクラスタリングとは、例えば、時間的に近い画像の組は同一のクラスタに属すようにし、時間的に離れている画像の組は無理に同一のクラスタに含めず、別々のクラスタに分けるようなクラスタリングを指す。このようにすることで、第１の実施形態で説明した効果に加え、クラスタに含まれる画像の枚数に大きな偏りが生まれることを防ぐことができる。よって、例えば、フォトブックを作成する際には、ページあたりの印象のバラつきを抑えることができる。
【００８６】
尚、前述した実施形態の商材作成装置１０、１２０が有する機能を複数の機器（例えば、ホストコンピュータ、インタフェース機器、撮像装置、webアプリケーション等）から構成されるシステムに適用しても良い。
また、前述した実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【００８７】
＜その他の実施形態＞
本発明は、前述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００８８】
１０３：画像情報取得部、１０４：画像管理部、１０５：組特定条件管理部１０６：組特定部、１０７：画像クラスタリング部、１０８：画像選択部、１０９：画像配置部
【図１】
0006685682.tif 000002
【図２】
0006685682.tif 000003
【図３】
0006685682.tif 000004
【図４】
0006685682.tif 000005
【図５】
0006685682.tif 000006
【図６】
0006685682.tif 000007
【図７】
0006685682.tif 000008
【図８】
0006685682.tif 000009
【図９】
0006685682.tif 000010
【図１０】
0006685682.tif 000011
【図１１】
0006685682.tif 000012
【図１２】
0006685682.tif 000013
【図１３】
0006685682.tif 000014
【図１４】
0006685682.tif 000015
【図１５】
0006685682.tif 000016
【図１６】
0006685682.tif 000017