画像分類装置、画像分類プログラム、プリンタ、撮像装置及び携帯電話機
【課題】クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を実現しつつ、違和感の少ない画像分類を実現し易くする。
【解決手段】画像分類装置は、総クラスタ数が指定値nogとなるとともに各クラスタの所属画像枚数が上限枚数gp_max以下となるように、分類対象画像をクラスタに分類する。まず、上限枚数gp_maxを越えることを許容しつつ、総クラスタ数がnogとなるように初期分類する。初期分類状態で上限枚数gp_maxを越えている各クラスタを、上限枚数gp_max以下の複数のクラスタに、分割する。初期分類状態において上限枚数gp_maxを越えているクラスタに所属していた画像は他のクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、nogとgp_maxの条件を満たすように、前記分割後の中間分類状態の少なくとも一部のクラスタを組み替える。
【解決手段】画像分類装置は、総クラスタ数が指定値nogとなるとともに各クラスタの所属画像枚数が上限枚数gp_max以下となるように、分類対象画像をクラスタに分類する。まず、上限枚数gp_maxを越えることを許容しつつ、総クラスタ数がnogとなるように初期分類する。初期分類状態で上限枚数gp_maxを越えている各クラスタを、上限枚数gp_max以下の複数のクラスタに、分割する。初期分類状態において上限枚数gp_maxを越えているクラスタに所属していた画像は他のクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、nogとgp_maxの条件を満たすように、前記分割後の中間分類状態の少なくとも一部のクラスタを組み替える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像分類装置、画像分類プログラム、プリンタ、撮像装置及び携帯電話機に関するものである。
【背景技術】
【０００２】
下記特許文献１において、指定したクラスタ上限枚数と、分類対象画像の枚数から、クラスタリングのグループ数閾値を算出し、上限枚数を超えたクラスタについて再帰的にクラスタリング処理を行うことによって、入力画像群を上限枚数以内のクラスタに分類する処理が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２１７５３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１で提案された従来手法では、分類後のクラスタ上限枚数を指定することによってクラスタリングを行うことができる。これによって、画像出力デバイスの一画面に表示できる画像枚数に制約がある場合においても、撮影時刻の近しい画像集合を一度に表示することができる。撮影時刻の近しい画像集合に分類されるので、違和感の少ない（すなわち、クラスタの分かれ目が不自然な位置となっていない）画像分類を実現し易い。例えば、入学式、遠足、運動会及び学芸会の画像からなる画像群を分類対象とするとき、遠足の一部の画像が入学式の画像と同じクラスタに分類される一方で、遠足の残りの画像が運動会の画像と同じクラスタに分類されて、遠足の２枚の画像間がクラスタの分かれ目となっている場合に比べて、遠足の画像が全て同一クラスタに分類される場合の方が、違和感が少なくなる。
【０００５】
その一方で、紙のアルバムのように「１ページにレイアウトできる写真枚数」と「利用可能なページ数」の両方に制約がある場合などのように、分類後のクラスタ上限枚数（各クラスタに所属させ得る画像の最大枚数）及び分類後の総クラスタ数の両方の制約条件を満たした画像分類が要請される場合が考えられる。
【０００６】
しかしながら、前記従来手法においては、クラスタ上限枚数は指定できるものの、総クラスタ数は指定することができず、「利用可能なページ数」を超過する可能性があった。
【０００７】
本発明は、このような事情に鑑みてなされたもので、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができ、しかも、違和感の少ない画像分類を実現し易い画像分類装置及び画像分類プログラム、並びに、前記画像分類装置を用いたプリンタ、撮像装置及び携帯電話機を提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するための手段として、以下の各態様を提示する。第１の態様による画像分類装置は、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、撮影時刻情報が関連づけられた分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する画像分類装置であって、クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えることを許容しつつ、総クラスタ数が前記所与の総クラスタ数となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類手段と、前記初期分類手段により分類された後の初期分類状態のクラスタのうちの少なくとも１つのクラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えている場合に、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えている各クラスタを、所属画像の枚数が前記所与のクラスタ上限枚数以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割手段と、可能であれば、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えているクラスタに所属していた画像は、前記初期分類状態において自己が所属していなかったクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、総クラスタ数が前記所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となるように、前記分割手段により分割された後の中間分類状態の少なくとも一部のクラスタを組み替えるクラスタ組み替え手段と、前記クラスタ組み替え手段による前記組み替えによって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段と、を備えたものである。
【０００９】
第２の態様による画像分類装置は、前記第１の態様において、前記クラスタ組み替え手段は、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていたクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第１の処理を行う第１の処理手段を、含み、前記第１の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１０】
第３の態様による画像分類装置は、前記第２の態様において、前記クラスタ組み替え手段は、前記第１の処理が不能である場合及び前記第１の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第２の処理を、前記第１の処理に劣後して行う第２の処理手段を、含み、前記第２の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１１】
第４の態様による画像分類装置は、前記第３の態様において、前記クラスタ組み替え手段は、前記第２の処理が不能である場合及び前記第２の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていた同じクラスタを起源とするクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第３の処理を、前記第２の処理に劣後して行う第３の処理手段を、含み、前記第３の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１２】
第５の態様による画像分類装置は、前記第４の態様において、前記クラスタ組み替え手段は、前記第３の処理が不能である場合及び前記第３の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第４の処理を、前記第３の処理に劣後して行う第４の処理手段を、含み、前記第４の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１３】
第６の態様による画像分類装置は、前記第１乃至第５のいずれかの態様において、前記クラスタ組み替え手段による前記組み替えが不能である場合に、前記中間分類状態を用いることなく、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する分類手段と、前記分類手段によって分類された後の分類状態を、前記分類対象の画像の分類結果とする手段とを備えたものである。
【００１４】
第７の態様による画像分類装置は、前記第１乃至第６のいずれかの態様において、前記初期分類状態の各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下である場合に、前記初期分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１５】
第８の態様による画像分類装置は、前記第１乃至第７のいずれかの態様において、前記初期分類手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分類対象の画像を分類するものである。
【００１６】
第９の態様による画像分類装置は、前記第１乃至第８のいずれかの態様において、前記分割手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分割を行うものである。
【００１７】
第１０の態様による画像分類プログラムは、コンピュータを、前記第１乃至第９のいずれかの態様による画像分類装置として機能させるためのプログラムである。
【００１８】
第１１の態様によるプリンタは、前記第１乃至第９のいずれかの態様による画像分類装置を備えたものである。
【００１９】
第１２の態様による撮像装置は、前記第１乃至第９のいずれかの態様による画像分類装置を備えたものである。
【００２０】
第１３の態様による携帯電話機は、前記第１２の態様による撮像装置を備えたものである。
【発明の効果】
【００２１】
本発明によれば、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができ、しかも、違和感の少ない画像分類を実現し易い画像分類装置及び画像分類プログラム、並びに、前記画像分類装置を用いたプリンタ、撮像装置及び携帯電話機を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態による画像分類装置のハードウエア構成を示す概略構成図である。
【図２】図１に示す画像分類装置の動作を示す概略フローチャートである。
【図３】図２中の初期分類処理の例を示す系統図である。
【図４】図２中の初期分類処理により得られる初期分類状態の例を示す図である。
【図５】図２中のクラスタ調整処理を示す概略フローチャートである。
【図６】図５中の枚数優先クラスタ分割処理を示す概略フローチャートである。
【図７】図５中の枚数優先クラスタ分割処理の例を示す図である。
【図８】図５中の枚数優先クラスタ分割処理により得られる中間分類状態の例を示す図である。
【図９】図５中のクラスタ組み替え処理を示す概略フローチャートである。
【図１０】図９中の第１の処理及び第２の処理の例を示す図である。
【図１１】図９中の第３の処理及び第４の処理の例を示す図である。
【図１２】図１に示す画像分類装置による分類結果の例を、系統図を用いて示す図である。
【図１３】図１に示す画像分類装置による分類結果の例を、各クラスタの画像として示す図である。
【図１４】図５中の、中間分類状態を用いない分類処理の例を示す図である。
【図１５】本発明の第２の実施の形態によるプリンタのハードウエア構成を示す概略構成図である。
【図１６】本発明の第３の実施の形態による撮像装置のハードウエア構成を示す概略構成図である。
【図１７】本発明の第４の実施の形態による携帯電話機を模式的に示す概略構成図である。
【発明を実施するための形態】
【００２３】
以下、本発明による画像分類装置、画像分類プログラム、プリンタ、撮像装置及び携帯電話機について、図面を参照して説明する。
【００２４】
［第１の実施の形態］
図１は、本発明の第１の実施の形態による画像分類装置１のハードウエア構成を示す概略構成図である。
【００２５】
本実施の形態による画像分類装置１は、ハードウエアとしては、一般的なパーソナルコンピュータを用いて構成され、ＣＰＵ２と、ＲＯＭ３と、ＲＡＭ４と、ハードディスク５と、キーボード及びマウス等の入力部６と、液晶パネル等の表示部７と、デジタルカメラ等と接続するためのインターフェース８と、取り外し自在に装着されたメモリカード１２と接続するためのカードインターフェース９と、インターネット等のネットワークと接続するための通信部１０と、プリンタ１３と接続されプリンタ１３に印刷データ及び制御信号を供給するプリンタ制御部１１と、これらを相互を接続するバス１４とを備えている。ハードディスク５には、画像分類プログラムの他、各種プログラムが予めインストールされており、前記画像分類プログラム等を読み込んで実行することによって、前記ＣＰＵ２等により以下に説明する機能が実現されるようになっている。
【００２６】
本実施の形態による画像分類装置１は、デジタルカメラからインターフェース８を介してハードディスク５内に取り込まれた画像、メモリカード１２からカードインターフェース９を介してハードディスク５内に取り込まれた画像、及び、通信部１０を介してハードディスク５内に取り込まれた画像のうち、入力部６により指定された画像（画像データ）を分類対象とする。なお、メモリカード１２内の画像を、ハードディスク５内に取り込むことなく直接に分類対象としてもよい。前記画像にはその撮影時刻を示す撮影時刻情報が関連づけられており、その撮影時刻情報も画像と共にハードディスク５内に格納されている。画像と撮影時刻情報は、互いに対応づけられた別ファイルを形成していてもよいし、両者が一体化されたファイル形式（Ｅｘｉｆ等）を採用してもよい。
【００２７】
本実施の形態による画像分類装置１は、ユーザが、入力部６を操作して、分類対象の画像を指定するとともに、総クラスタ数（nog）及びクラスタ上限枚数（gp_max）を指定した後、画像分類の開始を指令すると、図２に示す動作を開始する。図２は、本実施の形態による画像分類装置１の動作を示す概略フローチャートである。本実施の形態では、この指定総クラスタ数（nog）及び指定クラスタ上限枚数（gp_max）が、分類条件を示す所与の総クラスタ数及び所与のクラスタ上限枚数として用いられる。
【００２８】
なお、分類対象の画像を必ずしもユーザが指定できるようにする必要はなく、例えば、常に、メモリカード１２に記録されている全ての画像を分類対象とするようにしてもよい。また、総クラスタ数（nog）及びクラスタ上限枚数（gp_max）も必ずしもユーザが指定できるようにする必要はなく、予め固定された総クラスタ数（nog）及びクラスタ上限枚数（gp_max）を分類条件を示す所与の総クラスタ数及び所与のクラスタ上限枚数として用いてもよい。
【００２９】
ＣＰＵ２は、図２に示す動作を開始すると、まず、指定された分類対象画像の総数（ｎ）、指定総クラスタ数（nog）及び指定クラスタ上限枚数（gp_max）が分類可能なものであるか否かをチェックする（ステップＳ１）。nog、gp_max、ｎが全て１以上の整数であり、gp_max × nog ≧ ｎを満たし、かつ、ｎ ≧ nogを満たす場合に、分類可能であると判定し、そうでなければ分類不能であると判定する。ステップＳ１で分類不可能であると判定されると、ＣＰＵ２は分類失敗とし例えば表示部７に分類失敗である旨を表示させ（ステップＳ１３）、一連の分類処理を終了する。
【００３０】
一方、ステップＳ１で分類可能であると判定されると、ＣＰＵ２は、ステップＳ２へ移行してステップＳ２以降の処理を行うことで、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、指定された分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する。
【００３１】
図１３は、その分類結果の例を模式的に示している。図１３に示す例では、ｎ＝１７枚の分類対象の画像0001.jpg〜0017.jpgが、指定総クラスタ数nog＝４でかつ指定クラスタ上限枚数gp_max＝５のクラスタ１〜４に分類されている。画像0001.jpg〜0017.jpgの撮影時刻はそのフィル名の番号順になっており、画像0001.jpgの撮影時刻は最も古く、画像0017.jpgの撮影時刻は最も新しい。これらの点は、後述する図３、図４、図７、図８、図１０〜図１２に示す例についても同様である。
【００３２】
図１３に示す例では、クラスタ１の画像0001.jpg，0002.jpgが入学式の画像、クラスタ１の画像0003.jpg〜0005.jpgが遠足の画像、クラスタ２の画像0006.jpgが運動会の開会式の画像、クラスタ２の画像0007.jpg，0008.jpgが運動会の玉入れの画像、クラスタ３の画像0009.jpg〜0012.jpgが運動会の徒競走の画像、クラスタ４の画像0013.jpg〜0017.jpgが学芸会の画像となっている。その分類結果のデータ形式は何ら限定されるものではないが、例えば、分類結果として、各画像に対して画像毎に関連づけて付与されたクラスタ番号（当該画像が所属するクラスタの番号）を採用することができる。
【００３３】
ステップＳ２において、ＣＰＵ２は、クラスタに所属する画像の枚数がgp_maxを越えることを許容しつつ、総クラスタ数がnogとなるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類処理を行う。本実施の形態では、具体的には、ＣＰＵ２は、nogを閾値とした撮影時刻に基づく公知の階層的クラスタリングを用いて、この初期分類処理を行う。この場合、ＣＰＵ２は、例えば、図３に示すような系統図を作成し、この系統図をクラスタ数がnogとなるように切断することによって、クラスタリング結果（分類結果）を得る。その後、ＣＰＵ２は、初期分類処理Ｓ２により得た分類結果を、初期分類状態ＡとしてＲＡＭ４に記憶させる（ステップＳ３）。図４は初期分類状態Ａの例を示しており、図３に対応している。図４に示す例の初期分類状態Ａでは、１７枚の対象画像0001.jpg〜0017.jpgは、４個のクラスタ、すなわち、２枚の画像0001.jpg，0002.jpgが所属するクラスタ、３枚の画像0003.jpg〜0005.jpgが所属するクラスタ、７枚の画像0006.jpg〜0012.jpgが所属するクラスタ、及び、５枚の画像0013.jpg〜0017.jpgが所属するクラスタに、分類されている。
【００３４】
なお、初期分類処理Ｓ２は、階層的クラスタリングに代えて、例えば、K-meansクラスタリング、自己組織化マップ又はその他のクラスタリングを用いて行ってもよい。
【００３５】
次に、ＣＰＵ２は、ステップＳ３で保存した初期分類状態Ａの各クラスタについて、当該クラスタに所属する画像の枚数がgp_max以下であるか否かを判別し、gp_max以下である場合に当該クラスタが「Compactグループ」に所属することをＲＡＭ４に記憶させ、gp_maxを越えている場合に当該クラスタが「Largeグループ」に所属することをＲＡＭ４に記憶させる（ステップＳ４〜Ｓ７）。
【００３６】
このようにして得た、初期分類状態Ａの各クラスタがCompactグループ及びLargeグループのいずれに所属するかの情報に基づいて、ＣＰＵ２は、初期分類状態Ａにおいて個々のCompactグループ及びLargeグループを識別し、そのグループ識別結果をＲＡＭ４に記憶させる（ステップＳ８）。すなわち、ＣＰＵ２は、初期分類状態Ａにおいて、Largeグループに属するとされた個々のクラスタをそれぞれ個々のLargeグループとする。したがって、初期分類状態ＡにおいてLargeグループに属するとされたクラスタと、Largeグループとは１対１の関係にある。また、ＣＰＵ２は、Compactグループに所属するクラスタのうち孤立する１つのクラスタを１つのCompactグループとするとともに、Compactグループに所属するクラスタのうち連続する２つ以上のクラスタを１つのCompactグループとする。図４に示す例では、所属画像の枚数が２枚（≦ gp_max）のクラスタと所属画像の枚数が３枚（≦ gp_max）のクラスタとが連続しているので、これら２つのクラスタが１つのCompactグループとされている。また、所属画像の枚数が７枚（＞ gp_max）の１つのクラスタが１つのLargeグループとされている。さらに、所属画像の枚数が５枚（≦ gp_max）の１つクラスタは、Compactグループに所属する他のクラスタと連続せずに、Compactグループに所属する他のクラスタから孤立しているので、１つのCompactグループとされている。
【００３７】
各Compactグループ及び各Largeグループは、このように初期分類状態Ａのクラスタによって決定されるが、当該１つのグループとされる初期分類状態Ａの１つ又は２つ以上のクラスタに所属する画像の集合によって定義される。よって、後述するクラスタ調整処理Ｓ１０により、各グループを構成する画像の集合自体は変動することはない。ただし、後述するクラスタ調整処理Ｓ１０によって当該グループ内でクラスタが組み替えられることで、当該グループを構成するクラスタは変動し得る。例えば、図４に示す初期分類状態Ａの例では、左側の１つのCompactグループは、５枚の画像0001.jpg〜0005.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。また、中央の１つのLargeグループは、７枚の画像0006.jpg〜0012.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。さらに、右側の１つのCompactグループは、５枚の画像0013.jpg〜0017.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。
【００３８】
次に、ＣＰＵ２は、ステップＳ８でＲＡＭ４に記憶されたグループ識別結果に基づいて、初期分類状態Ａにおいて１つ以上のLargeグループが存在するか否かについて判定する（ステップＳ９）。初期分類状態Ａの中に１つ以上のLargeグループが存在しない場合、初期分類状態Ａはgp_maxの条件も満たしていることになる。よって、この場合は、分類成功として、初期分類状態Ａを最終的な分類結果として採用し、その分類結果をハードディスク５内に記憶し（ステップＳ１２）、一連の分類処理を終了する。
【００３９】
一方、初期分類状態Ａの中に１つ以上のLargeグループが存在する場合、ＣＰＵ２は、クラスタ調整処理を行う（ステップＳ１０）。図５は、クラスタ調整処理Ｓ１０を示す概略フローチャートである。
【００４０】
クラスタ調整処理Ｓ１０では、ＣＰＵ２は、まず、初期分類状態Ａの各Largeグループのクラスタ（すなわち、初期分類状態Ａのクラスタのうち所属画像枚数がgp_maxを越えている各クラスタ）を、所属画像枚数がgp_max以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割処理（枚数優先クラスタ分割処理）を行う（ステップＳ２１，Ｓ２２）。
【００４１】
図６は、初期分類状態Ａの各Largeグループのクラスタについて行われる枚数優先クラスタ分割処理Ｓ２２の具体例を示す概略フローチャートである。枚数優先クラスタ分割処理Ｓ２２では、ＣＰＵ２は、ステップＳ２１で順次処理対象とされるLargeグループについて、当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まっているか否かを判定する（ステップＳ４１）。当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まっていなければ、当該Largeグループ内の枚数超過クラスタ（所属画像枚数がgp_maxを越えているクラスタ）を、２を閾値とした撮影時刻に基づく公知の階層的クラスタリングを用いて、２つのクラスタに分割し（ステップＳ４２）、ステップＳ４１へ戻り、当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まるまで、ステップＳ４２，Ｓ４１を繰り返す。当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まると、当該Largeグループについての枚数優先クラスタ分割処理Ｓ２２を終了し、他のLargeグループについても同様の枚数優先クラスタ分割処理が順次行われる。
【００４２】
図７は、この枚数優先クラスタ分割処理Ｓ２２の例を示している。図７では、初期分類状態Ａが図４に示す通りである場合に、図４中の所属画像枚数が７枚（＞gp_max）のLargeグループ内のクラスタが分割される様子を示している。図７中の上側部分は、１回目のステップＳ４１でＮｏと判定された後の１回目のステップＳ４２で、当該Largeグループ内の７枚（＞gp_max）の画像0006.jpg〜0012.jpgが所属するクラスタが、１枚（≦gp_max）の画像0006.jpgが所属するクラスタと、６枚（＞gp_max）の画像0007.jpg〜0012.jpgが所属するクラスタとに分割される様子を示している。図７中の下側部分は、２回目のステップＳ４１でＮｏと判定された後の２回目のステップＳ４２で、当該Largeグループ内の６枚（＞gp_max）の画像0007.jpg〜0012.jpgが所属するクラスタが、２枚（≦gp_max）の画像0007.jpg，0008.jpgが所属するクラスタと、４枚（≦gp_max）の画像0009.jpg〜0012.jpgが所属するクラスタとに分割される様子を示している。この場合、３回目のステップＳ４１でＹｅｓと判定されることになる。
【００４３】
なお、前述したステップＳ４２のクラスタ分割は、階層的クラスタリングに代えて、例えば、K-meansクラスタリング、自己組織化マップ又はその他のクラスタリングを用いて行ってもよい。
【００４４】
全てのLargeグループについて枚数優先クラスタ分割処理Ｓ２２が終了すると、ＣＰＵ２は、その分割結果を中間分類状態ＢとしてＲＡＭ４に記憶させる（ステップＳ２３）。図８は中間分類状態Ｂの例を示しており、図３、図４及び図７に対応している。図４に示す初期分類状態Ａでは、Largeグループ内が所属画像枚数が７枚（＞gp_max）の１つのクラスタであったのに対し、図８に示す中間分類状態Ｂでは、Largeグループ内が３つのクラスタ（所属画像枚数が１枚（≦gp_max）のクラスタと、所属画像枚数が２枚（≦gp_max）のクラスタと、所属画像枚数が４枚（≦gp_max）のクラスタ）となっている。
【００４５】
その後、ＣＰＵ２は、ステップＳ２３で保存した中間分類状態Ｂの各クラスタが、初期分類状態Ａで決定されたいずれのLargeグループ又はCompactグループに所属するかをＲＡＭ４に記憶させる（ステップＳ２４）。
【００４６】
中間分類状態Ｂでは、全てのクラスタの所属画像枚数がgp_max以下に収まっている。しかし、中間分類状態Ｂでは、総クラスタ数がnogであった初期分類状態Ａからクラスタを分割しているため、総クラスタ数はnogを超過している。そこで、総クラスタ数をnogにするため、ＣＰＵ２は、ステップＳ２４の後に、中間分類状態Ｂに対してクラスタ組み替え処理Ｓ２５を試みる。
【００４７】
このクラスタ組み替え処理Ｓ２５は、可能であれば、初期分類状態Ａにおいて所属画像の枚数がgp_maxを越えているクラスタに所属していた画像（すなわち、Largeグループに所属する画像）は、初期分類状態Ａにおいて自己が所属していなかったクラスタに所属していた画像（すなわち、他のLargeグループ又はCompactグループに所属している画像）とは同じクラスタに所属させないという条件（組み替え基本条件）下で、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、中間分類状態Ｂの少なくとも一部のクラスタを組み替える処理である。前記組み替え基本条件を換言すると、後述する表１に記載されているように、各Largeグループを他のグループと混ぜないという条件である。
【００４８】
図９は、このクラスタ組み替え処理Ｓ２５の具体例を示す概略フローチャートである。また、図９中の第１乃至第４の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７の優先順位と主な特徴を、下記の表１に示す。図９及び表１に示すように、本実施の形態では、クラスタ組み替え処理Ｓ２５において、クラスタを組み替える複数の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７を、分類結果に与える違和感の少ないものから順に試み、総クラスタ数がnogとなった場合は、その時点の分類状態を最終的な分類結果として採用する。以下に、クラスタ組み替え処理Ｓ２５について、図９及び表１等を参照して具体的に説明する。
【００４９】
【表１】
【００５０】
クラスタ組み替え処理Ｓ２５では、ＣＰＵ２は、まず、中間分類状態Ｂに対して第１の処理Ｓ５１を行う。この第１の処理Ｓ５１は、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_maxを起源とする隣接クラスタ対（すなわち、Largeグループ内の隣接クラスタ対）のうち、当該クラスタ対に所属する画像の枚数の合計がgp_max以下である隣接クラスタ対について、クラスタ間距離（この距離は時間間隔に相当する。）の最も小さい隣接クラスタ対から順に統合する処理である。この第１の処理Ｓ５１は、前記組み替え基本条件下で行われる。ここで、統合は、隣接クラスタ対を１つのクラスタにまとめる（マージする、結合する）ことであり、既存のクラスタ分割を崩さない（すなわち、既存のクラスタ分割位置を変更しない）。この点は、後述する統合についても同様である。また、前記クラスタ間距離の定義としては、特に限定されるものではなく、例えば、公知の最近隣法、最遠隣法、群平均法、重心法などによる定義を採用することができる。この点は、後述するクラスタ間距離についても同様である。なお、第１の処理Ｓ５１の例及び後述する第２の処理Ｓ５３の例を併せて図１０に示しているので、図１０も参照されたい。図１０に示す分類状態は、図８に示す分類状態と同じであるものとしている。
【００５１】
その後、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５２）。第１の処理Ｓ５１によって総クラスタ数がnogとなっていれば、ステップＳ５２でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５２】
第１の処理Ｓ５１が不能であるか又は第１の処理Ｓ５１によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５２でＹｅｓとなり、ステップＳ５３へ移行する。
【００５３】
ステップＳ５３において、ＣＰＵ２は、現在の分類状態に対して第２の処理を行う。この第２の処理Ｓ５３は、第１の処理Ｓ５１が不能である場合及び第１の処理Ｓ５１を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_max以下であったクラスタを起源とする隣接クラスタ対（すなわち、Compactグループ内の隣接クラスタ対）のうち、当該クラスタ対に所属する画像の枚数の合計がgp_max以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する処理である。この第２の処理Ｓ５３は第１の処理Ｓ５１に劣後して行われる。換言すれば、第１の処理Ｓ５１は第２の処理Ｓ５３に優先して行われる。この第２の処理Ｓ５３も、前記組み替え基本条件下で行われる。なお、ここでも、図１０を参照されたい。
【００５４】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５４）。第２の処理Ｓ５３によって総クラスタ数がnogとなっていれば、ステップＳ５４でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５５】
第２の処理Ｓ５３が不能であるか又は第２の処理Ｓ５３によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５４でＹｅｓとなり、ステップＳ５５へ移行する。
【００５６】
ステップＳ５５において、ＣＰＵ２は、現在の分類状態に対して第３の処理を行う。この第３の処理Ｓ５５は、第２の処理Ｓ５３が不能である場合及び第２の処理Ｓ５３を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_maxを越えていた同じクラスタを起源とするクラスタからなるグループ（すなわち、Largeグループ）について、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数がgp_max以下となることを条件として、当該グループ内のクラスタを組み替える処理である。この第３の処理Ｓ５５は第２の処理Ｓ５３に劣後して行われる。換言すれば、第２の処理Ｓ５３は第３の処理Ｓ５５に優先して行われる。この第３の処理Ｓ５５も、前記組み替え基本条件下で行われる。
【００５７】
この第３の処理Ｓ５５では、具体的には、例えば、各Largeグループの中から、平均クラスタ間距離の最も小さいLargeグループを選び、グループ先頭からgp_maxごとに単純詰め込みを行うことによって、クラスタ数が減少するかどうかを試みてゆく。単純詰め込みによって、総クラスタ数が減少する場合（例えばgp_maxが５枚で、４枚２枚４枚の３クラスタになっているグループなど）は単純詰め込みを行い、クラスタ数が変わらない場合（例えばgp_maxが５枚で、３枚４枚５枚の３クラスタになっているグループなど）は詰め込みを行わない。なお、第３の処理Ｓ５５の例及び後述する第４の処理Ｓ５７の例を併せて図１１に示しているので、図１１も参照されたい。図１１に示す分類状態は、図８に示す分類状態と異なっているものとしている。なお、グループ先頭からgp_maxごとの詰め込みに代えて、グループ後尾からgp_maxごとの詰め込みを行ってもよい。なお、グループ先頭又はグループ後尾からのgp_maxごとの詰め込みを行うと、総数クラスタ数が１つ減る場合のみならず、総数クラスタ数が２つ以上減る場合もあり得る。総数クラスタ数が２つ以上減ることによって、総数クラスタ数がnogを下回ってしまう場合には、総数クラスタ数がnogとなるように各クラスタへの詰め込み画像枚数を調整すればよい。
【００５８】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５６）。第３の処理Ｓ５５によって総クラスタ数がnogとなっていれば、ステップＳ５６でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５９】
第３の処理Ｓ５５が不能であるか又は第３の処理Ｓ５５によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５６でＹｅｓとなり、ステップＳ５７へ移行する。
【００６０】
ステップＳ５７において、ＣＰＵ２は、現在の分類状態に対して第４の処理を行う。この第４の処理Ｓ５７は、第３の処理Ｓ５５が不能である場合及び第３の処理Ｓ５５を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるまで、初期分類状態Ａにおいて所属画像の枚数がgp_max以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループ（すなわち、Compactグループ）について、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数がgp_max以下となることを条件として、当該グループ内のクラスタを組み替える処理である。この第４の処理Ｓ５７は第３の処理Ｓ５５に劣後して行われる。換言すれば、第３の処理Ｓ５５は第４の処理Ｓ５７に優先して行われる。この第４の処理Ｓ５７も、前記組み替え基本条件下で行われる。
【００６１】
この第４の処理Ｓ５７では、具体的には、例えば、各Compactグループの中から、平均クラスタ間距離の最も小さいCompactグループを選び、グループ先頭からgp_maxごとに単純詰め込みを行うことによって、クラスタ数が減少するかどうかを試みてゆく。単純詰め込みによって、総クラスタ数が減少する場合は単純詰め込みを行い、クラスタ数が変わらない場合は詰め込みを行わない。なお、ここでも、図１１も参照されたい。なお、グループ先頭からgp_maxごとの詰め込みに代えて、グループ後尾からgp_maxごとの詰め込みを行ってもよい。なお、グループ先頭又はグループ後尾からのgp_maxごとの詰め込みを行うと、総数クラスタ数が１つ減る場合のみならず、総数クラスタ数が２つ以上減る場合もあり得る。総数クラスタ数が２つ以上減ることによって、総数クラスタ数がnogを下回ってしまう場合には、総数クラスタ数がnogとなるように各クラスタへの詰め込み画像枚数を調整すればよい。
【００６２】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５８）。第４の処理Ｓ５７によって総クラスタ数がnogとなっていれば、ステップＳ５８でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００６３】
第４の処理Ｓ５５が不能であるか又は第４の処理Ｓ５５によって総クラスタ数がnogとならない場合は、ステップＳ５８でＹｅｓとなり、ＣＰＵ２は、クラスタ組み替え処理が失敗したとして、その旨をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００６４】
クラスタ組み替え処理Ｓ２５が終了すると、図５中のステップＳ２６へ移行する。ステップＳ２６において、ＣＰＵ２は、ステップＳ５９，Ｓ６０でＲＡＭ４に記憶された、クラスタ組み替え処理Ｓ２５が成功したか否かの情報に基づいて、クラスタ組み替え処理Ｓ２５が成功したか否かを判定する。
【００６５】
ステップＳ２６で成功したと判定されると、ＣＰＵ２は、ステップＳ６０でＲＡＭ４に記憶されたクラスタ組み替え結果をクラスタ調整結果として採用し、そのクラスタ調整結果をＲＡＭ４に記憶し（ステップＳ２７）、クラスタ調整処理Ｓ１０を終了する。
【００６６】
図１２は、ステップＳ５４でＮｏの場合に得られた（すなわち、第１の処理Ｓ５１及び第２の処理Ｓ５２を行った時点で得られた）最終的な分類結果の例を、系統図を用いて示した図である。図１２は図１０に対応している。前述した図１３は、図１２と同じ分類処理を示している。例えば、図１３において遠足の一部の画像0005.jpgのみがクラスタ２内に所属するように分類が改変されていれば、遠足の画像0004.jpgと遠足の画像0005.jpgとの間がクラスタ１，２間の分かれ目となってしまうので、違和感が大きくなる。これに対し、図１３では、遠足の全ての画像0003.jpg〜0005.jpgはクラスタ１に所属しており、クラスタ１，２間の分かれ目は遠足の画像0005.jpgと運動会の画像0006.jpgとなっているので、違和感は少ない。
【００６７】
ステップＳ２６で失敗したと判定されると、ＣＰＵ２は、中間結果をクリアして初期分類状態Ａに戻り（ステップＳ２８）、その後、中間分類状態Ｂを用いない分類処理を行う（ステップＳ２９）。この分類処理Ｓ２９は、クラスタ組み替え処理Ｓ２５が不能である場合に、中間分類状態Ｂを用いることなく、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、指定された分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する処理である。
【００６８】
本実施の形態では、分類処理Ｓ２９において、初期分類状態Ａにおいて、Largeグループのクラスタについて着目し、当該クラスタのgp_maxを超えている数の画像を隣接クラスタへ移動していく。移動によって、移動先のクラスタがgp_maxを超過した場合は、そのクラスタの画像を更に隣接するクラスタに移動させる。これらの移動に際して、隣接するクラスタへの移動方向を、移動元のクラスタにおいてgp_maxを超えている数の画像を吸収する余裕がある方向に設定する。このような超過枚数画像の隣接クラスタへの移動を、全てのクラスタの所属画像枚数がgp_maxとなるまで繰り返す。このような分類処理Ｓ２９の例を図１４に示している。
【００６９】
なお、分類処理Ｓ２９は、前述したような初期分類状態Ａを用いた手法に限定されるものではない。例えば、分類処理Ｓ２９では、nog個のクラスタに、時系列の先頭から｛ｎ／（nog）｝個ずつ画像を単純に詰め込んでもよい。このとき、｛ｎ／（nog）｝が整数でない場合は、各クラスタに｛ｎ／（nog）｝の小数点以下を切り上げた個数又は｛ｎ／（nog）｝の小数点以下を切り下げた個数の画像を詰め込めばよい。
【００７０】
分類処理Ｓ２９の後、ＣＰＵ２は、分類処理Ｓ２９の分類結果をクラスタ調整結果として採用し、そのクラスタ調整結果をＲＡＭ４に記憶し（ステップＳ３０）、クラスタ調整処理Ｓ１０を終了する。
【００７１】
クラスタ調整処理Ｓ１０が終了すると、ＣＰＵ２は、ステップＳ２７又はＳ３０でＲＡＭ４に記憶されたクラスタ調整結果を最終的な分類結果として採用し、その分類結果をハードディスク５内に記憶し（ステップＳ１１）、一連の分類処理を終了する。
【００７２】
本実施の形態による画像分類装置では、図２に示す動作によって最終的な分類結果が得られた後、ユーザが、入力部６を操作して、その分類結果に応じた画像印刷を指令すると、ＣＰＵ２は、分類結果の各クラスタを１枚の印刷ページとし、各クラスタに属する画像を当該印刷ページにレイアウトした印刷データを生成し、この印刷データをプリンタ制御部１１を介してプリンタ１３に供給する。これにより、プリンタは、印刷ページとクラスタとを１対１に対応づけて、各印刷ページに対応クラスタの画像がレイアウトして印刷される。このようにして、紙のアルバムのように「１ページにレイアウトできる写真枚数」と「利用可能なページ数」の両方に制約があるような画像印刷を、実現することができる。
【００７３】
なお、図２に示す動作によって得た分類結果を最終的な分類結果の候補として、表示部７に表示してユーザに提示し、ユーザが入力部６の操作によって、その分類状態を修正できるようにし、その修正後の分類結果に応じた印刷を実現し得るようにしてもよい。なお、分類結果の表示形式は特に限定されるものではないが、例えば、表示部７の画面とクラスタとを１対１に対応づけ、各画面を入力部６の操作に応じて順次表示し、各画面に対応クラスタの画像をレイアウトして表示してもよい。
【００７４】
本実施の形態によれば、先の説明からわかるように、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができる。
【００７５】
そして、本実施の形態では、クラスタに所属する画像の枚数がgp_maxを越えることを許容した初期分類処理Ｓ２が行われ、その結果の初期分類状態Ａにおいてgp_maxを越えた各クラスタ（各Largeグループ）について枚数優先クラスタ分割処理Ｓ２２が行われ、可能であれば、その結果の中間分類状態Ｂに対して、各Largeグループを他のグループと混ぜないという条件を組み替え基本条件としたクラスタ組み替え処理Ｓ２５が行われる。したがって、このクラスタ組み替え処理Ｓ２５が可能な場合、各Largeグループを他のグループと混ぜないという条件が維持されるので、違和感の少ない画像分類が実現される。そして、本実施の形態では、違和感低減に重きを置かないいわば強制的な分類処理である分類処理Ｓ２９は、クラスタ組み替え処理Ｓ２５が不能な場合に行われ、クラスタ組み替え処理Ｓ２５が分類処理Ｓ２９に優先して行われるので、違和感の少ない画像分類を実現し易い。
【００７６】
しかも、本実施の形態では、前述したように、図９及び表１に示すように、クラスタ組み替え処理Ｓ２５において、クラスタを組み替える複数の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７を、分類結果に与える違和感の少ないものから順に試み、総クラスタ数がnogとなった場合は、その時点の分類状態を最終的な分類結果として採用している。なお、表１に記載されている第１の処理Ｓ５１、第２の処理Ｓ５３、第３の処理Ｓ５５、第４の処理Ｓ５７の特徴から、その順に、分類結果に与える違和感が少なくなる。したがって、本実施の形態によれば、より違和感の少ない画像分類の実現を容易し易い。
【００７７】
もっとも、本発明では、例えば、クラスタ組み替え処理Ｓ２５において、ステップＳ５７，Ｓ５８を除去し、ステップＳ５６でＹｅｓの場合はステップＳ５９へ移行してもよい。また、クラスタ組み替え処理Ｓ２５において、ステップＳ５５〜Ｓ５８を除去し、ステップＳ５４でＹｅｓの場合はステップＳ５９へ移行してもよい。さらに、クラスタ組み替え処理Ｓ２５において、ステップＳ５３〜Ｓ５８を除去し、ステップＳ５２でＹｅｓの場合はステップＳ５９へ移行してもよい。
【００７８】
また、本実施の形態では、前述したような処理で画像分類が実現され、あらゆる画像分類状態について所定指標で評価した上で最も評価の高い画像分類状態を最終的な分類結果として採用するような処理で画像分類を実現するものではない。したがって、後者の場合は、処理量は膨大となってしまい、膨大な処理時間を要するのに対し、本実施の形態では、処理量が少なくて済み、処理時間もさほど要しない。
【００７９】
［第２の実施の形態］
図１５は、本発明の第２の実施の形態によるプリンタ２１のハードウエア構成を示す概略構成図である。図１５において、図１中の要素と同一又は対応する要素には同一符号を付し、その重複する説明は省略する。
【００８０】
本実施の形態によるプリンタ２１では、プリンタ制御部１１は除去され、その代わりに印刷部２２が設けられている。本実施の形態では、インターフェース８には、デジタルカメラの他にパーソナルコンピュータ等が接続されるようになっている。パーソナルコンピュータからインターフェース８を介して印刷データが入力されると、その印刷データが示す印刷が、印刷部２２により行われるようになっている。
【００８１】
本実施の形態によるプリンタ２１は、前記第１の実施の形態による画像分類装置１の各要素と対応する要素によって、前記第１の実施の形態と同様の画像分類動作を行うようになっている。これにより、プリンタ２１は、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。本実施の形態によるプリンタ２１では、画像分類動作によって得られた分類結果に応じた画像印刷は、印刷部２２により行われる。
【００８２】
本実施の形態によるプリンタ２１は、家庭用のプリンタとして構成してもよいし、写真店やミニラボ等で使用する業務用のプリンタ（写真プリント機）として構成してもよい。後者の場合、ユーザが店頭に持参した画像を記録したメモリカード１２を画像分類対象とするが操作は店員が行うプリント機として構成してもよいし、ユーザが店頭に持参した画像を記録したメモリカード１２を画像分類対象とするとともに、操作もユーザが行ういわゆるセルフプリント機として構成してもよい。
【００８３】
［第３の実施の形態］
図１６は、本発明の第３の実施の形態による撮像装置としてのデジタルカメラ３１のハードウエア構成を示す概略構成図である。図１６において、図１中の要素と同一又は対応する要素には同一符号を付し、その重複する説明は省略する。
【００８４】
本実施の形態によるデジタルカメラ３１では、ハードディスク５及びプリンタ制御部１１は除去され、撮影レンズ及びＣＣＤ等の固体撮像素子などからなる撮像部３２、及び、撮像部３２で撮像された画像に対して種々の画像処理を行う画像処理部３３が、設けられている。本実施の形態では、撮像部３２で撮像された画像は、メモリカード１２に記憶されるようになっている。メモリカード１２に記憶された画像を、画像分類の対象とし得るようになっている。また、入力部６の操作により、メモリカード１２内の画像を通信部１０を介してネットワークに接続されたサーバに格納したり、インターフェース８を介してパーソナルコンピュータに送ったりすることができるようになっている。
【００８５】
本実施の形態によるデジタルカメラ３１は、前記第１の実施の形態による画像分類装置１の各要素と対応する要素によって、前記第１の実施の形態と同様の画像分類動作を行うようになっている。これにより、デジタルカメラ３１は、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。本実施の形態によるデジタルカメラ３１では、画像分類動作によって得られた分類結果に応じた画像表示を表示部７に表示したり、メモリカード１２に記憶された画像と共に画像分類結果もパーソナルコンピュータに送ったりすることができるようになっている。
【００８６】
［第４の実施の形態］
図１７は、本発明の第４の実施の形態による携帯電話機４１を模式的に示す概略構成図である。
【００８７】
本実施の形態による携帯電話機４１は、無線通話を行う無線通話部４２と、カメラ部４３とを有している。カメラ部４３は、前記第３の実施の形態によるデジタルカメラ３１と同様に構成され、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。
【００８８】
以上、本発明の各実施の形態について説明したが、本発明はこれらの実施の形態に限定されるものではない。
【符号の説明】
【００８９】
１ 画像分類装置
２１ プリンタ
３１ デジタルカメラ（撮像装置）
４１ 携帯電話機
【技術分野】
【０００１】
本発明は、画像分類装置、画像分類プログラム、プリンタ、撮像装置及び携帯電話機に関するものである。
【背景技術】
【０００２】
下記特許文献１において、指定したクラスタ上限枚数と、分類対象画像の枚数から、クラスタリングのグループ数閾値を算出し、上限枚数を超えたクラスタについて再帰的にクラスタリング処理を行うことによって、入力画像群を上限枚数以内のクラスタに分類する処理が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２１７５３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１で提案された従来手法では、分類後のクラスタ上限枚数を指定することによってクラスタリングを行うことができる。これによって、画像出力デバイスの一画面に表示できる画像枚数に制約がある場合においても、撮影時刻の近しい画像集合を一度に表示することができる。撮影時刻の近しい画像集合に分類されるので、違和感の少ない（すなわち、クラスタの分かれ目が不自然な位置となっていない）画像分類を実現し易い。例えば、入学式、遠足、運動会及び学芸会の画像からなる画像群を分類対象とするとき、遠足の一部の画像が入学式の画像と同じクラスタに分類される一方で、遠足の残りの画像が運動会の画像と同じクラスタに分類されて、遠足の２枚の画像間がクラスタの分かれ目となっている場合に比べて、遠足の画像が全て同一クラスタに分類される場合の方が、違和感が少なくなる。
【０００５】
その一方で、紙のアルバムのように「１ページにレイアウトできる写真枚数」と「利用可能なページ数」の両方に制約がある場合などのように、分類後のクラスタ上限枚数（各クラスタに所属させ得る画像の最大枚数）及び分類後の総クラスタ数の両方の制約条件を満たした画像分類が要請される場合が考えられる。
【０００６】
しかしながら、前記従来手法においては、クラスタ上限枚数は指定できるものの、総クラスタ数は指定することができず、「利用可能なページ数」を超過する可能性があった。
【０００７】
本発明は、このような事情に鑑みてなされたもので、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができ、しかも、違和感の少ない画像分類を実現し易い画像分類装置及び画像分類プログラム、並びに、前記画像分類装置を用いたプリンタ、撮像装置及び携帯電話機を提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するための手段として、以下の各態様を提示する。第１の態様による画像分類装置は、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、撮影時刻情報が関連づけられた分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する画像分類装置であって、クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えることを許容しつつ、総クラスタ数が前記所与の総クラスタ数となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類手段と、前記初期分類手段により分類された後の初期分類状態のクラスタのうちの少なくとも１つのクラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えている場合に、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えている各クラスタを、所属画像の枚数が前記所与のクラスタ上限枚数以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割手段と、可能であれば、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えているクラスタに所属していた画像は、前記初期分類状態において自己が所属していなかったクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、総クラスタ数が前記所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となるように、前記分割手段により分割された後の中間分類状態の少なくとも一部のクラスタを組み替えるクラスタ組み替え手段と、前記クラスタ組み替え手段による前記組み替えによって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段と、を備えたものである。
【０００９】
第２の態様による画像分類装置は、前記第１の態様において、前記クラスタ組み替え手段は、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていたクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第１の処理を行う第１の処理手段を、含み、前記第１の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１０】
第３の態様による画像分類装置は、前記第２の態様において、前記クラスタ組み替え手段は、前記第１の処理が不能である場合及び前記第１の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第２の処理を、前記第１の処理に劣後して行う第２の処理手段を、含み、前記第２の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１１】
第４の態様による画像分類装置は、前記第３の態様において、前記クラスタ組み替え手段は、前記第２の処理が不能である場合及び前記第２の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていた同じクラスタを起源とするクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第３の処理を、前記第２の処理に劣後して行う第３の処理手段を、含み、前記第３の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１２】
第５の態様による画像分類装置は、前記第４の態様において、前記クラスタ組み替え手段は、前記第３の処理が不能である場合及び前記第３の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第４の処理を、前記第３の処理に劣後して行う第４の処理手段を、含み、前記第４の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１３】
第６の態様による画像分類装置は、前記第１乃至第５のいずれかの態様において、前記クラスタ組み替え手段による前記組み替えが不能である場合に、前記中間分類状態を用いることなく、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する分類手段と、前記分類手段によって分類された後の分類状態を、前記分類対象の画像の分類結果とする手段とを備えたものである。
【００１４】
第７の態様による画像分類装置は、前記第１乃至第６のいずれかの態様において、前記初期分類状態の各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下である場合に、前記初期分類状態を、前記分類対象の画像の分類結果とする手段を備えたものである。
【００１５】
第８の態様による画像分類装置は、前記第１乃至第７のいずれかの態様において、前記初期分類手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分類対象の画像を分類するものである。
【００１６】
第９の態様による画像分類装置は、前記第１乃至第８のいずれかの態様において、前記分割手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分割を行うものである。
【００１７】
第１０の態様による画像分類プログラムは、コンピュータを、前記第１乃至第９のいずれかの態様による画像分類装置として機能させるためのプログラムである。
【００１８】
第１１の態様によるプリンタは、前記第１乃至第９のいずれかの態様による画像分類装置を備えたものである。
【００１９】
第１２の態様による撮像装置は、前記第１乃至第９のいずれかの態様による画像分類装置を備えたものである。
【００２０】
第１３の態様による携帯電話機は、前記第１２の態様による撮像装置を備えたものである。
【発明の効果】
【００２１】
本発明によれば、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができ、しかも、違和感の少ない画像分類を実現し易い画像分類装置及び画像分類プログラム、並びに、前記画像分類装置を用いたプリンタ、撮像装置及び携帯電話機を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態による画像分類装置のハードウエア構成を示す概略構成図である。
【図２】図１に示す画像分類装置の動作を示す概略フローチャートである。
【図３】図２中の初期分類処理の例を示す系統図である。
【図４】図２中の初期分類処理により得られる初期分類状態の例を示す図である。
【図５】図２中のクラスタ調整処理を示す概略フローチャートである。
【図６】図５中の枚数優先クラスタ分割処理を示す概略フローチャートである。
【図７】図５中の枚数優先クラスタ分割処理の例を示す図である。
【図８】図５中の枚数優先クラスタ分割処理により得られる中間分類状態の例を示す図である。
【図９】図５中のクラスタ組み替え処理を示す概略フローチャートである。
【図１０】図９中の第１の処理及び第２の処理の例を示す図である。
【図１１】図９中の第３の処理及び第４の処理の例を示す図である。
【図１２】図１に示す画像分類装置による分類結果の例を、系統図を用いて示す図である。
【図１３】図１に示す画像分類装置による分類結果の例を、各クラスタの画像として示す図である。
【図１４】図５中の、中間分類状態を用いない分類処理の例を示す図である。
【図１５】本発明の第２の実施の形態によるプリンタのハードウエア構成を示す概略構成図である。
【図１６】本発明の第３の実施の形態による撮像装置のハードウエア構成を示す概略構成図である。
【図１７】本発明の第４の実施の形態による携帯電話機を模式的に示す概略構成図である。
【発明を実施するための形態】
【００２３】
以下、本発明による画像分類装置、画像分類プログラム、プリンタ、撮像装置及び携帯電話機について、図面を参照して説明する。
【００２４】
［第１の実施の形態］
図１は、本発明の第１の実施の形態による画像分類装置１のハードウエア構成を示す概略構成図である。
【００２５】
本実施の形態による画像分類装置１は、ハードウエアとしては、一般的なパーソナルコンピュータを用いて構成され、ＣＰＵ２と、ＲＯＭ３と、ＲＡＭ４と、ハードディスク５と、キーボード及びマウス等の入力部６と、液晶パネル等の表示部７と、デジタルカメラ等と接続するためのインターフェース８と、取り外し自在に装着されたメモリカード１２と接続するためのカードインターフェース９と、インターネット等のネットワークと接続するための通信部１０と、プリンタ１３と接続されプリンタ１３に印刷データ及び制御信号を供給するプリンタ制御部１１と、これらを相互を接続するバス１４とを備えている。ハードディスク５には、画像分類プログラムの他、各種プログラムが予めインストールされており、前記画像分類プログラム等を読み込んで実行することによって、前記ＣＰＵ２等により以下に説明する機能が実現されるようになっている。
【００２６】
本実施の形態による画像分類装置１は、デジタルカメラからインターフェース８を介してハードディスク５内に取り込まれた画像、メモリカード１２からカードインターフェース９を介してハードディスク５内に取り込まれた画像、及び、通信部１０を介してハードディスク５内に取り込まれた画像のうち、入力部６により指定された画像（画像データ）を分類対象とする。なお、メモリカード１２内の画像を、ハードディスク５内に取り込むことなく直接に分類対象としてもよい。前記画像にはその撮影時刻を示す撮影時刻情報が関連づけられており、その撮影時刻情報も画像と共にハードディスク５内に格納されている。画像と撮影時刻情報は、互いに対応づけられた別ファイルを形成していてもよいし、両者が一体化されたファイル形式（Ｅｘｉｆ等）を採用してもよい。
【００２７】
本実施の形態による画像分類装置１は、ユーザが、入力部６を操作して、分類対象の画像を指定するとともに、総クラスタ数（nog）及びクラスタ上限枚数（gp_max）を指定した後、画像分類の開始を指令すると、図２に示す動作を開始する。図２は、本実施の形態による画像分類装置１の動作を示す概略フローチャートである。本実施の形態では、この指定総クラスタ数（nog）及び指定クラスタ上限枚数（gp_max）が、分類条件を示す所与の総クラスタ数及び所与のクラスタ上限枚数として用いられる。
【００２８】
なお、分類対象の画像を必ずしもユーザが指定できるようにする必要はなく、例えば、常に、メモリカード１２に記録されている全ての画像を分類対象とするようにしてもよい。また、総クラスタ数（nog）及びクラスタ上限枚数（gp_max）も必ずしもユーザが指定できるようにする必要はなく、予め固定された総クラスタ数（nog）及びクラスタ上限枚数（gp_max）を分類条件を示す所与の総クラスタ数及び所与のクラスタ上限枚数として用いてもよい。
【００２９】
ＣＰＵ２は、図２に示す動作を開始すると、まず、指定された分類対象画像の総数（ｎ）、指定総クラスタ数（nog）及び指定クラスタ上限枚数（gp_max）が分類可能なものであるか否かをチェックする（ステップＳ１）。nog、gp_max、ｎが全て１以上の整数であり、gp_max × nog ≧ ｎを満たし、かつ、ｎ ≧ nogを満たす場合に、分類可能であると判定し、そうでなければ分類不能であると判定する。ステップＳ１で分類不可能であると判定されると、ＣＰＵ２は分類失敗とし例えば表示部７に分類失敗である旨を表示させ（ステップＳ１３）、一連の分類処理を終了する。
【００３０】
一方、ステップＳ１で分類可能であると判定されると、ＣＰＵ２は、ステップＳ２へ移行してステップＳ２以降の処理を行うことで、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、指定された分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する。
【００３１】
図１３は、その分類結果の例を模式的に示している。図１３に示す例では、ｎ＝１７枚の分類対象の画像0001.jpg〜0017.jpgが、指定総クラスタ数nog＝４でかつ指定クラスタ上限枚数gp_max＝５のクラスタ１〜４に分類されている。画像0001.jpg〜0017.jpgの撮影時刻はそのフィル名の番号順になっており、画像0001.jpgの撮影時刻は最も古く、画像0017.jpgの撮影時刻は最も新しい。これらの点は、後述する図３、図４、図７、図８、図１０〜図１２に示す例についても同様である。
【００３２】
図１３に示す例では、クラスタ１の画像0001.jpg，0002.jpgが入学式の画像、クラスタ１の画像0003.jpg〜0005.jpgが遠足の画像、クラスタ２の画像0006.jpgが運動会の開会式の画像、クラスタ２の画像0007.jpg，0008.jpgが運動会の玉入れの画像、クラスタ３の画像0009.jpg〜0012.jpgが運動会の徒競走の画像、クラスタ４の画像0013.jpg〜0017.jpgが学芸会の画像となっている。その分類結果のデータ形式は何ら限定されるものではないが、例えば、分類結果として、各画像に対して画像毎に関連づけて付与されたクラスタ番号（当該画像が所属するクラスタの番号）を採用することができる。
【００３３】
ステップＳ２において、ＣＰＵ２は、クラスタに所属する画像の枚数がgp_maxを越えることを許容しつつ、総クラスタ数がnogとなるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類処理を行う。本実施の形態では、具体的には、ＣＰＵ２は、nogを閾値とした撮影時刻に基づく公知の階層的クラスタリングを用いて、この初期分類処理を行う。この場合、ＣＰＵ２は、例えば、図３に示すような系統図を作成し、この系統図をクラスタ数がnogとなるように切断することによって、クラスタリング結果（分類結果）を得る。その後、ＣＰＵ２は、初期分類処理Ｓ２により得た分類結果を、初期分類状態ＡとしてＲＡＭ４に記憶させる（ステップＳ３）。図４は初期分類状態Ａの例を示しており、図３に対応している。図４に示す例の初期分類状態Ａでは、１７枚の対象画像0001.jpg〜0017.jpgは、４個のクラスタ、すなわち、２枚の画像0001.jpg，0002.jpgが所属するクラスタ、３枚の画像0003.jpg〜0005.jpgが所属するクラスタ、７枚の画像0006.jpg〜0012.jpgが所属するクラスタ、及び、５枚の画像0013.jpg〜0017.jpgが所属するクラスタに、分類されている。
【００３４】
なお、初期分類処理Ｓ２は、階層的クラスタリングに代えて、例えば、K-meansクラスタリング、自己組織化マップ又はその他のクラスタリングを用いて行ってもよい。
【００３５】
次に、ＣＰＵ２は、ステップＳ３で保存した初期分類状態Ａの各クラスタについて、当該クラスタに所属する画像の枚数がgp_max以下であるか否かを判別し、gp_max以下である場合に当該クラスタが「Compactグループ」に所属することをＲＡＭ４に記憶させ、gp_maxを越えている場合に当該クラスタが「Largeグループ」に所属することをＲＡＭ４に記憶させる（ステップＳ４〜Ｓ７）。
【００３６】
このようにして得た、初期分類状態Ａの各クラスタがCompactグループ及びLargeグループのいずれに所属するかの情報に基づいて、ＣＰＵ２は、初期分類状態Ａにおいて個々のCompactグループ及びLargeグループを識別し、そのグループ識別結果をＲＡＭ４に記憶させる（ステップＳ８）。すなわち、ＣＰＵ２は、初期分類状態Ａにおいて、Largeグループに属するとされた個々のクラスタをそれぞれ個々のLargeグループとする。したがって、初期分類状態ＡにおいてLargeグループに属するとされたクラスタと、Largeグループとは１対１の関係にある。また、ＣＰＵ２は、Compactグループに所属するクラスタのうち孤立する１つのクラスタを１つのCompactグループとするとともに、Compactグループに所属するクラスタのうち連続する２つ以上のクラスタを１つのCompactグループとする。図４に示す例では、所属画像の枚数が２枚（≦ gp_max）のクラスタと所属画像の枚数が３枚（≦ gp_max）のクラスタとが連続しているので、これら２つのクラスタが１つのCompactグループとされている。また、所属画像の枚数が７枚（＞ gp_max）の１つのクラスタが１つのLargeグループとされている。さらに、所属画像の枚数が５枚（≦ gp_max）の１つクラスタは、Compactグループに所属する他のクラスタと連続せずに、Compactグループに所属する他のクラスタから孤立しているので、１つのCompactグループとされている。
【００３７】
各Compactグループ及び各Largeグループは、このように初期分類状態Ａのクラスタによって決定されるが、当該１つのグループとされる初期分類状態Ａの１つ又は２つ以上のクラスタに所属する画像の集合によって定義される。よって、後述するクラスタ調整処理Ｓ１０により、各グループを構成する画像の集合自体は変動することはない。ただし、後述するクラスタ調整処理Ｓ１０によって当該グループ内でクラスタが組み替えられることで、当該グループを構成するクラスタは変動し得る。例えば、図４に示す初期分類状態Ａの例では、左側の１つのCompactグループは、５枚の画像0001.jpg〜0005.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。また、中央の１つのLargeグループは、７枚の画像0006.jpg〜0012.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。さらに、右側の１つのCompactグループは、５枚の画像0013.jpg〜0017.jpgの集合（図３も参照）として定義され、後述するクラスタ調整処理Ｓ１０によって変動することはない。
【００３８】
次に、ＣＰＵ２は、ステップＳ８でＲＡＭ４に記憶されたグループ識別結果に基づいて、初期分類状態Ａにおいて１つ以上のLargeグループが存在するか否かについて判定する（ステップＳ９）。初期分類状態Ａの中に１つ以上のLargeグループが存在しない場合、初期分類状態Ａはgp_maxの条件も満たしていることになる。よって、この場合は、分類成功として、初期分類状態Ａを最終的な分類結果として採用し、その分類結果をハードディスク５内に記憶し（ステップＳ１２）、一連の分類処理を終了する。
【００３９】
一方、初期分類状態Ａの中に１つ以上のLargeグループが存在する場合、ＣＰＵ２は、クラスタ調整処理を行う（ステップＳ１０）。図５は、クラスタ調整処理Ｓ１０を示す概略フローチャートである。
【００４０】
クラスタ調整処理Ｓ１０では、ＣＰＵ２は、まず、初期分類状態Ａの各Largeグループのクラスタ（すなわち、初期分類状態Ａのクラスタのうち所属画像枚数がgp_maxを越えている各クラスタ）を、所属画像枚数がgp_max以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割処理（枚数優先クラスタ分割処理）を行う（ステップＳ２１，Ｓ２２）。
【００４１】
図６は、初期分類状態Ａの各Largeグループのクラスタについて行われる枚数優先クラスタ分割処理Ｓ２２の具体例を示す概略フローチャートである。枚数優先クラスタ分割処理Ｓ２２では、ＣＰＵ２は、ステップＳ２１で順次処理対象とされるLargeグループについて、当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まっているか否かを判定する（ステップＳ４１）。当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まっていなければ、当該Largeグループ内の枚数超過クラスタ（所属画像枚数がgp_maxを越えているクラスタ）を、２を閾値とした撮影時刻に基づく公知の階層的クラスタリングを用いて、２つのクラスタに分割し（ステップＳ４２）、ステップＳ４１へ戻り、当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まるまで、ステップＳ４２，Ｓ４１を繰り返す。当該Largeグループ内の全てクラスタの所属画像枚数がgp_max以下に収まると、当該Largeグループについての枚数優先クラスタ分割処理Ｓ２２を終了し、他のLargeグループについても同様の枚数優先クラスタ分割処理が順次行われる。
【００４２】
図７は、この枚数優先クラスタ分割処理Ｓ２２の例を示している。図７では、初期分類状態Ａが図４に示す通りである場合に、図４中の所属画像枚数が７枚（＞gp_max）のLargeグループ内のクラスタが分割される様子を示している。図７中の上側部分は、１回目のステップＳ４１でＮｏと判定された後の１回目のステップＳ４２で、当該Largeグループ内の７枚（＞gp_max）の画像0006.jpg〜0012.jpgが所属するクラスタが、１枚（≦gp_max）の画像0006.jpgが所属するクラスタと、６枚（＞gp_max）の画像0007.jpg〜0012.jpgが所属するクラスタとに分割される様子を示している。図７中の下側部分は、２回目のステップＳ４１でＮｏと判定された後の２回目のステップＳ４２で、当該Largeグループ内の６枚（＞gp_max）の画像0007.jpg〜0012.jpgが所属するクラスタが、２枚（≦gp_max）の画像0007.jpg，0008.jpgが所属するクラスタと、４枚（≦gp_max）の画像0009.jpg〜0012.jpgが所属するクラスタとに分割される様子を示している。この場合、３回目のステップＳ４１でＹｅｓと判定されることになる。
【００４３】
なお、前述したステップＳ４２のクラスタ分割は、階層的クラスタリングに代えて、例えば、K-meansクラスタリング、自己組織化マップ又はその他のクラスタリングを用いて行ってもよい。
【００４４】
全てのLargeグループについて枚数優先クラスタ分割処理Ｓ２２が終了すると、ＣＰＵ２は、その分割結果を中間分類状態ＢとしてＲＡＭ４に記憶させる（ステップＳ２３）。図８は中間分類状態Ｂの例を示しており、図３、図４及び図７に対応している。図４に示す初期分類状態Ａでは、Largeグループ内が所属画像枚数が７枚（＞gp_max）の１つのクラスタであったのに対し、図８に示す中間分類状態Ｂでは、Largeグループ内が３つのクラスタ（所属画像枚数が１枚（≦gp_max）のクラスタと、所属画像枚数が２枚（≦gp_max）のクラスタと、所属画像枚数が４枚（≦gp_max）のクラスタ）となっている。
【００４５】
その後、ＣＰＵ２は、ステップＳ２３で保存した中間分類状態Ｂの各クラスタが、初期分類状態Ａで決定されたいずれのLargeグループ又はCompactグループに所属するかをＲＡＭ４に記憶させる（ステップＳ２４）。
【００４６】
中間分類状態Ｂでは、全てのクラスタの所属画像枚数がgp_max以下に収まっている。しかし、中間分類状態Ｂでは、総クラスタ数がnogであった初期分類状態Ａからクラスタを分割しているため、総クラスタ数はnogを超過している。そこで、総クラスタ数をnogにするため、ＣＰＵ２は、ステップＳ２４の後に、中間分類状態Ｂに対してクラスタ組み替え処理Ｓ２５を試みる。
【００４７】
このクラスタ組み替え処理Ｓ２５は、可能であれば、初期分類状態Ａにおいて所属画像の枚数がgp_maxを越えているクラスタに所属していた画像（すなわち、Largeグループに所属する画像）は、初期分類状態Ａにおいて自己が所属していなかったクラスタに所属していた画像（すなわち、他のLargeグループ又はCompactグループに所属している画像）とは同じクラスタに所属させないという条件（組み替え基本条件）下で、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、中間分類状態Ｂの少なくとも一部のクラスタを組み替える処理である。前記組み替え基本条件を換言すると、後述する表１に記載されているように、各Largeグループを他のグループと混ぜないという条件である。
【００４８】
図９は、このクラスタ組み替え処理Ｓ２５の具体例を示す概略フローチャートである。また、図９中の第１乃至第４の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７の優先順位と主な特徴を、下記の表１に示す。図９及び表１に示すように、本実施の形態では、クラスタ組み替え処理Ｓ２５において、クラスタを組み替える複数の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７を、分類結果に与える違和感の少ないものから順に試み、総クラスタ数がnogとなった場合は、その時点の分類状態を最終的な分類結果として採用する。以下に、クラスタ組み替え処理Ｓ２５について、図９及び表１等を参照して具体的に説明する。
【００４９】
【表１】
【００５０】
クラスタ組み替え処理Ｓ２５では、ＣＰＵ２は、まず、中間分類状態Ｂに対して第１の処理Ｓ５１を行う。この第１の処理Ｓ５１は、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_maxを起源とする隣接クラスタ対（すなわち、Largeグループ内の隣接クラスタ対）のうち、当該クラスタ対に所属する画像の枚数の合計がgp_max以下である隣接クラスタ対について、クラスタ間距離（この距離は時間間隔に相当する。）の最も小さい隣接クラスタ対から順に統合する処理である。この第１の処理Ｓ５１は、前記組み替え基本条件下で行われる。ここで、統合は、隣接クラスタ対を１つのクラスタにまとめる（マージする、結合する）ことであり、既存のクラスタ分割を崩さない（すなわち、既存のクラスタ分割位置を変更しない）。この点は、後述する統合についても同様である。また、前記クラスタ間距離の定義としては、特に限定されるものではなく、例えば、公知の最近隣法、最遠隣法、群平均法、重心法などによる定義を採用することができる。この点は、後述するクラスタ間距離についても同様である。なお、第１の処理Ｓ５１の例及び後述する第２の処理Ｓ５３の例を併せて図１０に示しているので、図１０も参照されたい。図１０に示す分類状態は、図８に示す分類状態と同じであるものとしている。
【００５１】
その後、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５２）。第１の処理Ｓ５１によって総クラスタ数がnogとなっていれば、ステップＳ５２でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５２】
第１の処理Ｓ５１が不能であるか又は第１の処理Ｓ５１によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５２でＹｅｓとなり、ステップＳ５３へ移行する。
【００５３】
ステップＳ５３において、ＣＰＵ２は、現在の分類状態に対して第２の処理を行う。この第２の処理Ｓ５３は、第１の処理Ｓ５１が不能である場合及び第１の処理Ｓ５１を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_max以下であったクラスタを起源とする隣接クラスタ対（すなわち、Compactグループ内の隣接クラスタ対）のうち、当該クラスタ対に所属する画像の枚数の合計がgp_max以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する処理である。この第２の処理Ｓ５３は第１の処理Ｓ５１に劣後して行われる。換言すれば、第１の処理Ｓ５１は第２の処理Ｓ５３に優先して行われる。この第２の処理Ｓ５３も、前記組み替え基本条件下で行われる。なお、ここでも、図１０を参照されたい。
【００５４】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５４）。第２の処理Ｓ５３によって総クラスタ数がnogとなっていれば、ステップＳ５４でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５５】
第２の処理Ｓ５３が不能であるか又は第２の処理Ｓ５３によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５４でＹｅｓとなり、ステップＳ５５へ移行する。
【００５６】
ステップＳ５５において、ＣＰＵ２は、現在の分類状態に対して第３の処理を行う。この第３の処理Ｓ５５は、第２の処理Ｓ５３が不能である場合及び第２の処理Ｓ５３を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるかあるいはnogに可能な限り近づくまで、初期分類状態Ａにおいて所属画像の枚数がgp_maxを越えていた同じクラスタを起源とするクラスタからなるグループ（すなわち、Largeグループ）について、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数がgp_max以下となることを条件として、当該グループ内のクラスタを組み替える処理である。この第３の処理Ｓ５５は第２の処理Ｓ５３に劣後して行われる。換言すれば、第２の処理Ｓ５３は第３の処理Ｓ５５に優先して行われる。この第３の処理Ｓ５５も、前記組み替え基本条件下で行われる。
【００５７】
この第３の処理Ｓ５５では、具体的には、例えば、各Largeグループの中から、平均クラスタ間距離の最も小さいLargeグループを選び、グループ先頭からgp_maxごとに単純詰め込みを行うことによって、クラスタ数が減少するかどうかを試みてゆく。単純詰め込みによって、総クラスタ数が減少する場合（例えばgp_maxが５枚で、４枚２枚４枚の３クラスタになっているグループなど）は単純詰め込みを行い、クラスタ数が変わらない場合（例えばgp_maxが５枚で、３枚４枚５枚の３クラスタになっているグループなど）は詰め込みを行わない。なお、第３の処理Ｓ５５の例及び後述する第４の処理Ｓ５７の例を併せて図１１に示しているので、図１１も参照されたい。図１１に示す分類状態は、図８に示す分類状態と異なっているものとしている。なお、グループ先頭からgp_maxごとの詰め込みに代えて、グループ後尾からgp_maxごとの詰め込みを行ってもよい。なお、グループ先頭又はグループ後尾からのgp_maxごとの詰め込みを行うと、総数クラスタ数が１つ減る場合のみならず、総数クラスタ数が２つ以上減る場合もあり得る。総数クラスタ数が２つ以上減ることによって、総数クラスタ数がnogを下回ってしまう場合には、総数クラスタ数がnogとなるように各クラスタへの詰め込み画像枚数を調整すればよい。
【００５８】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５６）。第３の処理Ｓ５５によって総クラスタ数がnogとなっていれば、ステップＳ５６でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００５９】
第３の処理Ｓ５５が不能であるか又は第３の処理Ｓ５５によって総クラスタ数がnogに可能な限り近づいたがnogとならない場合は、ステップＳ５６でＹｅｓとなり、ステップＳ５７へ移行する。
【００６０】
ステップＳ５７において、ＣＰＵ２は、現在の分類状態に対して第４の処理を行う。この第４の処理Ｓ５７は、第３の処理Ｓ５５が不能である場合及び第３の処理Ｓ５５を経たが総クラスタ数がnogとならない場合に、可能であれば、総クラスタ数がnogとなるまで、初期分類状態Ａにおいて所属画像の枚数がgp_max以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループ（すなわち、Compactグループ）について、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数がgp_max以下となることを条件として、当該グループ内のクラスタを組み替える処理である。この第４の処理Ｓ５７は第３の処理Ｓ５５に劣後して行われる。換言すれば、第３の処理Ｓ５５は第４の処理Ｓ５７に優先して行われる。この第４の処理Ｓ５７も、前記組み替え基本条件下で行われる。
【００６１】
この第４の処理Ｓ５７では、具体的には、例えば、各Compactグループの中から、平均クラスタ間距離の最も小さいCompactグループを選び、グループ先頭からgp_maxごとに単純詰め込みを行うことによって、クラスタ数が減少するかどうかを試みてゆく。単純詰め込みによって、総クラスタ数が減少する場合は単純詰め込みを行い、クラスタ数が変わらない場合は詰め込みを行わない。なお、ここでも、図１１も参照されたい。なお、グループ先頭からgp_maxごとの詰め込みに代えて、グループ後尾からgp_maxごとの詰め込みを行ってもよい。なお、グループ先頭又はグループ後尾からのgp_maxごとの詰め込みを行うと、総数クラスタ数が１つ減る場合のみならず、総数クラスタ数が２つ以上減る場合もあり得る。総数クラスタ数が２つ以上減ることによって、総数クラスタ数がnogを下回ってしまう場合には、総数クラスタ数がnogとなるように各クラスタへの詰め込み画像枚数を調整すればよい。
【００６２】
次に、ＣＰＵ２は、現在の分類状態において総クラスタ数がnogが越えているか否か（すなわち、総クラスタ数がnogでないかnogであるか）について、判定する（ステップＳ５８）。第４の処理Ｓ５７によって総クラスタ数がnogとなっていれば、ステップＳ５８でＮｏとなり、ＣＰＵ２は、クラスタ組み替え処理が成功したとして、その旨と現在の分類状態（クラスタ組み替え結果）をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００６３】
第４の処理Ｓ５５が不能であるか又は第４の処理Ｓ５５によって総クラスタ数がnogとならない場合は、ステップＳ５８でＹｅｓとなり、ＣＰＵ２は、クラスタ組み替え処理が失敗したとして、その旨をＲＡＭ４に記憶し（ステップＳ６０）、クラスタ組み替え処理Ｓ２５を終了する。
【００６４】
クラスタ組み替え処理Ｓ２５が終了すると、図５中のステップＳ２６へ移行する。ステップＳ２６において、ＣＰＵ２は、ステップＳ５９，Ｓ６０でＲＡＭ４に記憶された、クラスタ組み替え処理Ｓ２５が成功したか否かの情報に基づいて、クラスタ組み替え処理Ｓ２５が成功したか否かを判定する。
【００６５】
ステップＳ２６で成功したと判定されると、ＣＰＵ２は、ステップＳ６０でＲＡＭ４に記憶されたクラスタ組み替え結果をクラスタ調整結果として採用し、そのクラスタ調整結果をＲＡＭ４に記憶し（ステップＳ２７）、クラスタ調整処理Ｓ１０を終了する。
【００６６】
図１２は、ステップＳ５４でＮｏの場合に得られた（すなわち、第１の処理Ｓ５１及び第２の処理Ｓ５２を行った時点で得られた）最終的な分類結果の例を、系統図を用いて示した図である。図１２は図１０に対応している。前述した図１３は、図１２と同じ分類処理を示している。例えば、図１３において遠足の一部の画像0005.jpgのみがクラスタ２内に所属するように分類が改変されていれば、遠足の画像0004.jpgと遠足の画像0005.jpgとの間がクラスタ１，２間の分かれ目となってしまうので、違和感が大きくなる。これに対し、図１３では、遠足の全ての画像0003.jpg〜0005.jpgはクラスタ１に所属しており、クラスタ１，２間の分かれ目は遠足の画像0005.jpgと運動会の画像0006.jpgとなっているので、違和感は少ない。
【００６７】
ステップＳ２６で失敗したと判定されると、ＣＰＵ２は、中間結果をクリアして初期分類状態Ａに戻り（ステップＳ２８）、その後、中間分類状態Ｂを用いない分類処理を行う（ステップＳ２９）。この分類処理Ｓ２９は、クラスタ組み替え処理Ｓ２５が不能である場合に、中間分類状態Ｂを用いることなく、総クラスタ数がnogとなるとともに各クラスタに所属する画像の枚数がgp_max以下となるように、指定された分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する処理である。
【００６８】
本実施の形態では、分類処理Ｓ２９において、初期分類状態Ａにおいて、Largeグループのクラスタについて着目し、当該クラスタのgp_maxを超えている数の画像を隣接クラスタへ移動していく。移動によって、移動先のクラスタがgp_maxを超過した場合は、そのクラスタの画像を更に隣接するクラスタに移動させる。これらの移動に際して、隣接するクラスタへの移動方向を、移動元のクラスタにおいてgp_maxを超えている数の画像を吸収する余裕がある方向に設定する。このような超過枚数画像の隣接クラスタへの移動を、全てのクラスタの所属画像枚数がgp_maxとなるまで繰り返す。このような分類処理Ｓ２９の例を図１４に示している。
【００６９】
なお、分類処理Ｓ２９は、前述したような初期分類状態Ａを用いた手法に限定されるものではない。例えば、分類処理Ｓ２９では、nog個のクラスタに、時系列の先頭から｛ｎ／（nog）｝個ずつ画像を単純に詰め込んでもよい。このとき、｛ｎ／（nog）｝が整数でない場合は、各クラスタに｛ｎ／（nog）｝の小数点以下を切り上げた個数又は｛ｎ／（nog）｝の小数点以下を切り下げた個数の画像を詰め込めばよい。
【００７０】
分類処理Ｓ２９の後、ＣＰＵ２は、分類処理Ｓ２９の分類結果をクラスタ調整結果として採用し、そのクラスタ調整結果をＲＡＭ４に記憶し（ステップＳ３０）、クラスタ調整処理Ｓ１０を終了する。
【００７１】
クラスタ調整処理Ｓ１０が終了すると、ＣＰＵ２は、ステップＳ２７又はＳ３０でＲＡＭ４に記憶されたクラスタ調整結果を最終的な分類結果として採用し、その分類結果をハードディスク５内に記憶し（ステップＳ１１）、一連の分類処理を終了する。
【００７２】
本実施の形態による画像分類装置では、図２に示す動作によって最終的な分類結果が得られた後、ユーザが、入力部６を操作して、その分類結果に応じた画像印刷を指令すると、ＣＰＵ２は、分類結果の各クラスタを１枚の印刷ページとし、各クラスタに属する画像を当該印刷ページにレイアウトした印刷データを生成し、この印刷データをプリンタ制御部１１を介してプリンタ１３に供給する。これにより、プリンタは、印刷ページとクラスタとを１対１に対応づけて、各印刷ページに対応クラスタの画像がレイアウトして印刷される。このようにして、紙のアルバムのように「１ページにレイアウトできる写真枚数」と「利用可能なページ数」の両方に制約があるような画像印刷を、実現することができる。
【００７３】
なお、図２に示す動作によって得た分類結果を最終的な分類結果の候補として、表示部７に表示してユーザに提示し、ユーザが入力部６の操作によって、その分類状態を修正できるようにし、その修正後の分類結果に応じた印刷を実現し得るようにしてもよい。なお、分類結果の表示形式は特に限定されるものではないが、例えば、表示部７の画面とクラスタとを１対１に対応づけ、各画面を入力部６の操作に応じて順次表示し、各画面に対応クラスタの画像をレイアウトして表示してもよい。
【００７４】
本実施の形態によれば、先の説明からわかるように、クラスタ上限枚数及び総クラスタ数の両方の制約条件を満たした画像分類を行うことができる。
【００７５】
そして、本実施の形態では、クラスタに所属する画像の枚数がgp_maxを越えることを許容した初期分類処理Ｓ２が行われ、その結果の初期分類状態Ａにおいてgp_maxを越えた各クラスタ（各Largeグループ）について枚数優先クラスタ分割処理Ｓ２２が行われ、可能であれば、その結果の中間分類状態Ｂに対して、各Largeグループを他のグループと混ぜないという条件を組み替え基本条件としたクラスタ組み替え処理Ｓ２５が行われる。したがって、このクラスタ組み替え処理Ｓ２５が可能な場合、各Largeグループを他のグループと混ぜないという条件が維持されるので、違和感の少ない画像分類が実現される。そして、本実施の形態では、違和感低減に重きを置かないいわば強制的な分類処理である分類処理Ｓ２９は、クラスタ組み替え処理Ｓ２５が不能な場合に行われ、クラスタ組み替え処理Ｓ２５が分類処理Ｓ２９に優先して行われるので、違和感の少ない画像分類を実現し易い。
【００７６】
しかも、本実施の形態では、前述したように、図９及び表１に示すように、クラスタ組み替え処理Ｓ２５において、クラスタを組み替える複数の処理Ｓ５１，Ｓ５３，Ｓ５５，Ｓ５７を、分類結果に与える違和感の少ないものから順に試み、総クラスタ数がnogとなった場合は、その時点の分類状態を最終的な分類結果として採用している。なお、表１に記載されている第１の処理Ｓ５１、第２の処理Ｓ５３、第３の処理Ｓ５５、第４の処理Ｓ５７の特徴から、その順に、分類結果に与える違和感が少なくなる。したがって、本実施の形態によれば、より違和感の少ない画像分類の実現を容易し易い。
【００７７】
もっとも、本発明では、例えば、クラスタ組み替え処理Ｓ２５において、ステップＳ５７，Ｓ５８を除去し、ステップＳ５６でＹｅｓの場合はステップＳ５９へ移行してもよい。また、クラスタ組み替え処理Ｓ２５において、ステップＳ５５〜Ｓ５８を除去し、ステップＳ５４でＹｅｓの場合はステップＳ５９へ移行してもよい。さらに、クラスタ組み替え処理Ｓ２５において、ステップＳ５３〜Ｓ５８を除去し、ステップＳ５２でＹｅｓの場合はステップＳ５９へ移行してもよい。
【００７８】
また、本実施の形態では、前述したような処理で画像分類が実現され、あらゆる画像分類状態について所定指標で評価した上で最も評価の高い画像分類状態を最終的な分類結果として採用するような処理で画像分類を実現するものではない。したがって、後者の場合は、処理量は膨大となってしまい、膨大な処理時間を要するのに対し、本実施の形態では、処理量が少なくて済み、処理時間もさほど要しない。
【００７９】
［第２の実施の形態］
図１５は、本発明の第２の実施の形態によるプリンタ２１のハードウエア構成を示す概略構成図である。図１５において、図１中の要素と同一又は対応する要素には同一符号を付し、その重複する説明は省略する。
【００８０】
本実施の形態によるプリンタ２１では、プリンタ制御部１１は除去され、その代わりに印刷部２２が設けられている。本実施の形態では、インターフェース８には、デジタルカメラの他にパーソナルコンピュータ等が接続されるようになっている。パーソナルコンピュータからインターフェース８を介して印刷データが入力されると、その印刷データが示す印刷が、印刷部２２により行われるようになっている。
【００８１】
本実施の形態によるプリンタ２１は、前記第１の実施の形態による画像分類装置１の各要素と対応する要素によって、前記第１の実施の形態と同様の画像分類動作を行うようになっている。これにより、プリンタ２１は、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。本実施の形態によるプリンタ２１では、画像分類動作によって得られた分類結果に応じた画像印刷は、印刷部２２により行われる。
【００８２】
本実施の形態によるプリンタ２１は、家庭用のプリンタとして構成してもよいし、写真店やミニラボ等で使用する業務用のプリンタ（写真プリント機）として構成してもよい。後者の場合、ユーザが店頭に持参した画像を記録したメモリカード１２を画像分類対象とするが操作は店員が行うプリント機として構成してもよいし、ユーザが店頭に持参した画像を記録したメモリカード１２を画像分類対象とするとともに、操作もユーザが行ういわゆるセルフプリント機として構成してもよい。
【００８３】
［第３の実施の形態］
図１６は、本発明の第３の実施の形態による撮像装置としてのデジタルカメラ３１のハードウエア構成を示す概略構成図である。図１６において、図１中の要素と同一又は対応する要素には同一符号を付し、その重複する説明は省略する。
【００８４】
本実施の形態によるデジタルカメラ３１では、ハードディスク５及びプリンタ制御部１１は除去され、撮影レンズ及びＣＣＤ等の固体撮像素子などからなる撮像部３２、及び、撮像部３２で撮像された画像に対して種々の画像処理を行う画像処理部３３が、設けられている。本実施の形態では、撮像部３２で撮像された画像は、メモリカード１２に記憶されるようになっている。メモリカード１２に記憶された画像を、画像分類の対象とし得るようになっている。また、入力部６の操作により、メモリカード１２内の画像を通信部１０を介してネットワークに接続されたサーバに格納したり、インターフェース８を介してパーソナルコンピュータに送ったりすることができるようになっている。
【００８５】
本実施の形態によるデジタルカメラ３１は、前記第１の実施の形態による画像分類装置１の各要素と対応する要素によって、前記第１の実施の形態と同様の画像分類動作を行うようになっている。これにより、デジタルカメラ３１は、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。本実施の形態によるデジタルカメラ３１では、画像分類動作によって得られた分類結果に応じた画像表示を表示部７に表示したり、メモリカード１２に記憶された画像と共に画像分類結果もパーソナルコンピュータに送ったりすることができるようになっている。
【００８６】
［第４の実施の形態］
図１７は、本発明の第４の実施の形態による携帯電話機４１を模式的に示す概略構成図である。
【００８７】
本実施の形態による携帯電話機４１は、無線通話を行う無線通話部４２と、カメラ部４３とを有している。カメラ部４３は、前記第３の実施の形態によるデジタルカメラ３１と同様に構成され、前記第１の実施の形態による画像分類装置１と同様の画像分類装置を有している。
【００８８】
以上、本発明の各実施の形態について説明したが、本発明はこれらの実施の形態に限定されるものではない。
【符号の説明】
【００８９】
１ 画像分類装置
２１ プリンタ
３１ デジタルカメラ（撮像装置）
４１ 携帯電話機
【特許請求の範囲】
【請求項１】
総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、撮影時刻情報が関連づけられた分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する画像分類装置であって、
クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えることを許容しつつ、総クラスタ数が前記所与の総クラスタ数となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類手段と、
前記初期分類手段により分類された後の初期分類状態のクラスタのうちの少なくとも１つのクラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えている場合に、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えている各クラスタを、所属画像の枚数が前記所与のクラスタ上限枚数以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割手段と、
可能であれば、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えているクラスタに所属していた画像は、前記初期分類状態において自己が所属していなかったクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、総クラスタ数が前記所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となるように、前記分割手段により分割された後の中間分類状態の少なくとも一部のクラスタを組み替えるクラスタ組み替え手段と、
前記クラスタ組み替え手段による前記組み替えによって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段と、
を備えたことを特徴とする画像分類装置。
【請求項２】
前記クラスタ組み替え手段は、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていたクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第１の処理を行う第１の処理手段を、含み、
前記第１の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項１記載の画像分類装置。
【請求項３】
前記クラスタ組み替え手段は、前記第１の処理が不能である場合及び前記第１の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第２の処理を、前記第１の処理に劣後して行う第２の処理手段を、含み、
前記第２の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項２記載の画像分類装置。
【請求項４】
前記クラスタ組み替え手段は、前記第２の処理が不能である場合及び前記第２の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていた同じクラスタを起源とするクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第３の処理を、前記第２の処理に劣後して行う第３の処理手段を、含み、
前記第３の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項３記載の画像分類装置。
【請求項５】
前記クラスタ組み替え手段は、前記第３の処理が不能である場合及び前記第３の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第４の処理を、前記第３の処理に劣後して行う第４の処理手段を、含み、
前記第４の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項４記載の画像分類装置。
【請求項６】
前記クラスタ組み替え手段による前記組み替えが不能である場合に、前記中間分類状態を用いることなく、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する分類手段と、
前記分類手段によって分類された後の分類状態を、前記分類対象の画像の分類結果とする手段と、
を備えたことを特徴とする請求項１乃至５のいずれかに記載の画像分類装置。
【請求項７】
前記初期分類状態の各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下である場合に、前記初期分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項１乃至６のいずれかに記載の画像分類装置。
【請求項８】
前記初期分類手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分類対象の画像を分類することを特徴とする請求項１乃至７のいずれかに記載の画像分類装置。
【請求項９】
前記分割手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分割を行うことを特徴とする請求項１乃至８のいずれかに記載の画像分類装置。
【請求項１０】
コンピュータを、請求項１乃至９のいずれかに記載の画像分類装置として機能させるための画像分類プログラム。
【請求項１１】
請求項１乃至９のいずれかに記載の画像分類装置を備えたことを特徴とするプリンタ。
【請求項１２】
請求項１乃至９のいずれかに記載の画像分類装置を備えたことを特徴とする撮像装置。
【請求項１３】
請求項１２記載の撮像装置を備えたことを特徴とする携帯電話機。
【請求項１】
総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、撮影時刻情報が関連づけられた分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する画像分類装置であって、
クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えることを許容しつつ、総クラスタ数が前記所与の総クラスタ数となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する初期分類手段と、
前記初期分類手段により分類された後の初期分類状態のクラスタのうちの少なくとも１つのクラスタに所属する画像の枚数が前記所与のクラスタ上限枚数を越えている場合に、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えている各クラスタを、所属画像の枚数が前記所与のクラスタ上限枚数以下でありかつ１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成される複数のクラスタに、分割する分割手段と、
可能であれば、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えているクラスタに所属していた画像は、前記初期分類状態において自己が所属していなかったクラスタに所属していた画像とは同じクラスタに所属させないという条件下で、総クラスタ数が前記所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となるように、前記分割手段により分割された後の中間分類状態の少なくとも一部のクラスタを組み替えるクラスタ組み替え手段と、
前記クラスタ組み替え手段による前記組み替えによって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段と、
を備えたことを特徴とする画像分類装置。
【請求項２】
前記クラスタ組み替え手段は、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていたクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第１の処理を行う第１の処理手段を、含み、
前記第１の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項１記載の画像分類装置。
【請求項３】
前記クラスタ組み替え手段は、前記第１の処理が不能である場合及び前記第１の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とする隣接クラスタ対のうち、当該クラスタ対に所属する画像の枚数の合計が前記所与のクラスタ上限枚数以下である隣接クラスタ対について、クラスタ間距離の最も小さい隣接クラスタ対から順に統合する第２の処理を、前記第１の処理に劣後して行う第２の処理手段を、含み、
前記第２の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項２記載の画像分類装置。
【請求項４】
前記クラスタ組み替え手段は、前記第２の処理が不能である場合及び前記第２の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるかあるいは前記所与の総クラスタ数に可能な限り近づくまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数を越えていた同じクラスタを起源とするクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第３の処理を、前記第２の処理に劣後して行う第３の処理手段を、含み、
前記第３の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項３記載の画像分類装置。
【請求項５】
前記クラスタ組み替え手段は、前記第３の処理が不能である場合及び前記第３の処理を経たが総クラスタ数が前記所与の総クラスタ数とならない場合に、可能であれば、総クラスタ数が前記所与の総クラスタ数となるまで、前記初期分類状態において所属画像の枚数が前記所与のクラスタ上限枚数以下であったクラスタを起源とするクラスタのうち、孤立する１つのクラスタ又は連続する２つ以上のクラスタからなるグループについて、平均クラスタ間距離の最も小さいグループから順に、当該グループ内のクラスタ数が減るとともに各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下となることを条件として、当該グループ内のクラスタを組み替える第４の処理を、前記第３の処理に劣後して行う第４の処理手段を、含み、
前記第４の処理によって総クラスタ数が前記所与の総クラスタ数となったときの分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項４記載の画像分類装置。
【請求項６】
前記クラスタ組み替え手段による前記組み替えが不能である場合に、前記中間分類状態を用いることなく、総クラスタ数が所与の総クラスタ数となるとともに各クラスタに所属する画像の枚数が所与のクラスタ上限枚数以下となるように、前記分類対象の画像を、１枚の画像又は撮影時刻が連続する時系列をなす２枚以上の画像から構成されるクラスタに分類する分類手段と、
前記分類手段によって分類された後の分類状態を、前記分類対象の画像の分類結果とする手段と、
を備えたことを特徴とする請求項１乃至５のいずれかに記載の画像分類装置。
【請求項７】
前記初期分類状態の各クラスタに所属する画像の枚数が前記所与のクラスタ上限枚数以下である場合に、前記初期分類状態を、前記分類対象の画像の分類結果とする手段を備えたことを特徴とする請求項１乃至６のいずれかに記載の画像分類装置。
【請求項８】
前記初期分類手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分類対象の画像を分類することを特徴とする請求項１乃至７のいずれかに記載の画像分類装置。
【請求項９】
前記分割手段は、階層的クラスタリング、K-meansクラスタリング、自己組織化マップ及びその他のクラスタリングのうちの１つを用いて、前記分割を行うことを特徴とする請求項１乃至８のいずれかに記載の画像分類装置。
【請求項１０】
コンピュータを、請求項１乃至９のいずれかに記載の画像分類装置として機能させるための画像分類プログラム。
【請求項１１】
請求項１乃至９のいずれかに記載の画像分類装置を備えたことを特徴とするプリンタ。
【請求項１２】
請求項１乃至９のいずれかに記載の画像分類装置を備えたことを特徴とする撮像装置。
【請求項１３】
請求項１２記載の撮像装置を備えたことを特徴とする携帯電話機。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１２−４８６４１（Ｐ２０１２−４８６４１Ａ）
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１０−１９２４４２（Ｐ２０１０−１９２４４２）
【出願日】平成２２年８月３０日（２０１０．８．３０）
【出願人】（５９２２１７０９３）株式会社ニコンシステム (102)
【Ｆターム（参考）】
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２２年８月３０日（２０１０．８．３０）
【出願人】（５９２２１７０９３）株式会社ニコンシステム (102)
【Ｆターム（参考）】
[ Back to top ]