(57)【要約】      （修正有）【課題】高速に物体領域（前景領域）を切り抜くことが可能な前景領域抽出方法を提供する。【解決手段】ユーザにより指定された前景ピクセル及び背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定し、各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行うと共に各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行った後、各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行い、前景ピクセル又は背景ピクセルとして確定する確定処理を行い、前記画像から前景領域を抽出するように構成した。【選択図】図２
2010079477.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
画像を表示させる表示制御手段、
前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付手段、
前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定手段、
前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出手段、
各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別手段、
前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出手段、及び、
前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定手段、として機能させ、
前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を前記コンピュータに繰り返し行わせることにより、前記画像から前景領域を抽出するように機能させることを特徴とする前景領域抽出プログラム。
【請求項２】
請求項１に記載の前景領域抽出プログラムであって、
前記基準ピクセルに隣接する隣接ピクセルが、前記基準分割色空間に属する場合には、前記重み付けが小さくされることを特徴とする前景領域抽出プログラム。
【請求項３】
請求項１又は２に記載の前景領域抽出プログラムであって、  
前記ユーザにより指定される前記前景ピクセルは、前記前景領域上に表われるテクスチャパターンを構成する互いに異なる少なくとも２つの色の夫々に対応する前景ピクセルであることを特徴とする前景領域抽出プログラム。
【請求項４】
請求項１乃至３の何れか一項に記載の前景領域抽出プログラムであって、
前記基準ピクセルに隣接する隣接ピクセルが、前記基準分割色空間に属さない場合には、前記コストを蓄積し、蓄積されたコストが閾値を超えた場合に、前景と背景を反転させることを特徴とする前景領域抽出プログラム。
【請求項５】
画像を表示させる表示制御手段と、
前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付手段と、
前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定手段と、
前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出手段と、
各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別手段と、
前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出手段と、
前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定手段と、を備え、
前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を繰り返し行うことにより、前記画像から前景領域を抽出することを特徴とする前景領域抽出装置。
【請求項６】
コンピュータにより行われる前景領域抽出方法であって、
画像を表示させる表示制御工程と、
前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付工程と、
前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定工程と、
前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出工程と、
各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別工程と、
前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出工程と、
前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定工程と、を含み、
前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を繰り返し行うことにより、前記画像から前景領域を抽出することを特徴とする前景領域抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像から物体領域を切り抜く技術の分野に関する。
【背景技術】
【０００２】
画像からの物体領域（前景領域）の抽出は、写真や動画の加工など多くの場面で利用されている。このような物体領域の抽出技術としては、例えば、物体領域上にユーザが引いた手がかり線と、背景領域上にユーザが引いた手がかり線から、物体領域を抽出する、例えばLazy Snappingのロジック等の技術（非特許文献１参照）が知られている。Lazy Snappingの特徴は、領域内に数本手がかり線を引くだけで物体領域抽出を実現している点にあり、また、線を１本追加する度に、逐次的に物体領域の再抽出が行われるため、ユーザは抽出結果を見ながら線の追加、削除を行うことができる。
【非特許文献１】Y. Li, J. Sun, C. K. Tang and H. Y. Shum, “Lazy Snapping,” ACM Transactions on Graphics (TOG), Vol.23, Issue.3, pp.303-308, Aug.2004.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上述したような従来の物体領域の抽出技術では、例えば手がかり線を追加するなどして、最終的にユーザが所望する物体領域を切り抜くことができるが、当該物体領域を正確に切り抜くまでに時間がかかる場合もある。
【０００４】
本発明は、このような問題等に鑑みてなされたものであり、その課題の一例は、高速に物体領域（前景領域）を切り抜くことが可能な前景領域抽出プログラム、前景領域抽出装置、及び前景領域抽出方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、請求項１に記載の前景領域抽出プログラムの発明は、コンピュータを、画像を表示させる表示制御手段、前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付手段、前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定手段、前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出手段、各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別手段、前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出手段、及び、前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定手段、として機能させ、前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を前記コンピュータに繰り返し行わせることにより、前記画像から前景領域を抽出するように機能させることを特徴とする。
【０００６】
この発明によれば、ユーザが所望する物体領域（前景領域）を高速に切り抜くことができる。
【０００７】
請求項２に記載の発明は、請求項１に記載の前景領域抽出プログラムであって、前記基準ピクセルに隣接する隣接ピクセルが、前記基準分割色空間に属する場合には、前記重み付けが小さくされることを特徴とする。
【０００８】
請求項３に記載の発明は、請求項１又は２に記載の前景領域抽出プログラムであって、前記ユーザにより指定される前記前景ピクセルは、前記前景領域上に表われるテクスチャパターンを構成する互いに異なる少なくとも２つの色の夫々に対応する前景ピクセルであることを特徴とする。
【０００９】
この発明によれば、テクスチャパターンが画像上にあっても正確に前景と背景を分けることができる。
【００１０】
請求項４に記載の発明は、請求項１乃至３の何れか一項に記載の前景領域抽出プログラムであって、前記基準ピクセルに隣接する隣接ピクセルが、前記基準分割色空間に属さない場合には、前記コストを蓄積し、蓄積されたコストが閾値を超えた場合に、前景と背景を反転させることを特徴とする。
【００１１】
この発明によれば、飛び地の輪郭部分にアンチエイリアスがあっても、飛び地において前景と背景を正確に反転させることができる。
【００１２】
請求項５に記載の発明は、画像を表示させる表示制御手段と、前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付手段と、前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定手段と、前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出手段と、各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別手段と、前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出手段と、前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定手段と、を備え、前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を繰り返し行うことにより、前記画像から前景領域を抽出することを特徴とする。
【００１３】
請求項６に記載の発明は、コンピュータにより行われる前景領域抽出方法であって、画像を表示させる表示制御工程と、前記表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付ける受付工程と、前記指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定する分割色空間特定処理を行う分割色空間特定工程と、前記各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行う色距離算出工程と、各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行う属否判別工程と、前記各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行うコスト算出工程と、前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行う確定工程と、を含み、前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を繰り返し行うことにより、前記画像から前景領域を抽出することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、ユーザにより指定された前景ピクセル及び前記指定された背景ピクセルを夫々基準ピクセルとして、３次元の色空間が複数に分割された分割色空間のうちから、各前記基準ピクセルが属する分割色空間を基準分割色空間として特定し、各基準ピクセルとこれに隣接する隣接ピクセルとの前記色空間における色の距離を算出する色距離算出処理を行うと共に各前記隣接ピクセルが前記各基準分割色空間に属するか否かを判別する属否判別処理を行った後、各隣接ピクセルについて算出された前記色の距離と、前記各隣接ピクセルについて判別された前記基準分割色空間への属否に基づく重み付けと、に基づいて前記各隣接ピクセルについてのコストを算出するコスト算出処理を行い、さらに、前記算出されたコストが最も小さい隣接ピクセルを前景ピクセル又は背景ピクセルとして確定する確定処理を行い、前記確定された隣接ピクセルを基準ピクセルとして、前記色距離算出処理、前記属否判別処理、前記コスト算出処理、及び前記確定処理を繰り返し行うことにより、前記画像から前景領域を抽出するように構成したので、ユーザが所望する物体領域（前景領域）を高速に切り抜くことができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。以下に説明する実施の形態は、ユーザにより描かれた手がかり線（手書き線）をヒントに前景、背景を分けることで画像から物体領域を切り抜く画像編集装置に対して本発明を適用した場合の実施形態である。ここで「前景」とは人物や物品等の検索対象を表示する画像を意味し、「背景」とは検索対象を除く画像を意味する。
【００１６】
図１は、本実施形態に係る画像編集装置Ｓの概要構成例を示す図である。
【００１７】
図１に示すように、画像編集装置Ｓは、操作部１、表示部２、ドライブ部３、記憶部４、入出力インターフェース部５、及びシステム制御部６等を備えており、システム制御部６と入出力インターフェース部５とは、システムバス７を介して接続されている。なお、画像編集装置Ｓとしてはパーソナルコンピュータを適用することができる。
【００１８】
操作部１は、例えば、キーボード及びマウス等からなり、ユーザからの操作指示を受け付け、その指示内容を指示信号としてシステム制御部６に出力する。
【００１９】
表示部２は、例えば、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ等からなり、文字や画像等の情報を表示する。
【００２０】
ドライブ部３は、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）等のディスクＤＫ（記録媒体）からデータ等を読み出す一方、当該ディスクＤＫ（記録媒体）に対してデータ等を記録する。
【００２１】
入出力インターフェース部５は、操作部１乃至記憶部４とシステム制御部６との間のインターフェース処理を行う。
【００２２】
記憶部４は、例えば、ハードディスクドライブ等からなり、オペレーティングシステム（Ｏ／Ｓ），各種プログラム及びデータ等を記憶する。ここで、記憶部４に記憶されるプログラムには、動画像編集アプリケーションプログラム（本発明の前景領域抽出プログラムを有する）等が含まれる。
【００２３】
なお、動画像編集アプリケーションプログラムは、例えばＣＤ−ＲＯＭ等のディスクＤＫに記録されて提供されるか、或いはネットワークＮＷに接続されたサーバからのダウンロードにより提供され、インストールされて利用される。
【００２４】
システム制御部６は、ＣＰＵ（Central Processing Unit）６ａ，ＲＯＭ（Read Only Memory）６ｂ，及びメインメモリと画像メモリとして使用されるＲＡＭ（Random Access Memory）６ｃ等を備えて構成されている。そして、システム制御部６は、上記動画像編集アプリケーションプログラムを実行することにより、本発明における表示制御手段、受付手段、分割色空間特定手段、色距離算出手段、属否判別手段、コスト算出手段、及び確定手段等として機能し、前景領域抽出処理を行うようになっている。
【００２５】
ここで、前景領域抽出処理について図２を参照して説明する。
【００２６】
図２は、システム制御部６における前景領域抽出処理の一例を示すフローチャートである。
【００２７】
図２に示す処理は、例えば、動画像編集アプリケーションプログラムが起動することにより開始される。当該処理が開始されると、システム制御部６は、ユーザから操作部１を通じて指示された動画中の静止画像を表示部２上に表示させる（ステップＳ１）。
【００２８】
次いで、システム制御部６は、当該表示された画像に含まれる前景領域上における少なくとも一つの前景ピクセル、及び当該画像に含まれる背景領域上における少なくとも一つの背景ピクセルの指定をユーザから受け付け（ステップＳ２）、確定した前景ピクセル、及び背景ピクセルとして登録（ＲＡＭの登録領域に記憶）する。例えば、前景ピクセルは、ユーザがマウスを操作して所望する前景領域（物体領域）上に手がかり線を描くことで指定でき、背景ピクセルは、ユーザがマウスを操作して所望する背景領域上に手がかり線を描くことで指定できる。
【００２９】
図３は、写真の画像において、前景領域上及び背景領域上に描かれた手がかり線の例を示す図である。図３の例では、手がかり線５１と重なっている複数のピクセルが前景ピクセルとして指定され、手がかり線５２と重なっている複数のピクセルが背景ピクセルとして指定されることになる。なお、図３の例では、犬の物体領域が、ユーザが所望する前景領域となっている。図３中、ユーザが所望する前景領域が樹木であれば、その樹木の物体領域が前景領域となり、犬を含む他の領域が背景領域となる。
【００３０】
次いで、システム制御部６は、分割色空間特定処理を行う（ステップＳ３）。この分割色空間特定処理においては、上記指定された少なくとも１つの前景ピクセル及び少なくとも１つの指定された背景ピクセルを夫々基準ピクセルとして、３次元のＲＧＢ色空間が複数に分割された分割色空間（以下、「バケツ」と称する）のうちから、各基準ピクセルが属する基準バケツが特定される。
【００３１】
図４は、ＲＧＢ色空間を分割数ｓのグリッドで分割したバケツを示す図である。図４の例では、Ｒ（レッド），Ｇ（グリーン），Ｂ（ブルー）の３つの軸を有し、夫々の輝度を０〜２５５の範囲とするＲＧＢ色空間を示しており、Ｒ，Ｇ，Ｂが夫々４分割（ｓ＝４）されている。これにより、ＲＧＢ色空間は、６４個のバケツに分割されることになる。なお、この例では、６４個のバケツに分割したが、これより少なく分割しても良いし、これより多く分割しても良い。
【００３２】
ここで、基準ピクセルｐ（＝（ｐｒ，ｐｇ，ｐｂ））が属するバケツｂ（ｐ）は、以下の（１）式で算出できる。
【数１】
2010079477.tif 000003
【００３３】
こうして、図４に示すように、前景ピクセル６１が属する基準バケツ６２と、背景ピクセル６３が属する基準バケツ６４とが特定されることになり、基準バケツ６２は前景色クラスタ（言い換えれば、前景色グループ）として登録され、基準バケツ６４は背景色クラスタ（言い換えれば、背景色グループ）として登録される（このような、クラスタ分けを、バケツを用いたクラスタリング法と称する）。なお、上述した手がかり線によれば、前景ピクセル及び背景ピクセルは夫々手がかり線上にあるピクセルについて複数指定され、夫々のピクセルが属する前景色クラスタ又は背景色クラスタが登録されることになる。
【００３４】
ところで、例えば、前景領域上に、図５に示すようなテクスチャパターン（模様の連続）が表われている場合がある。このようなテクスチャパターンでは、同じ前景領域においてもテクスチャパターンを構成する少なくとも２つの色の色空間における距離が大きくなるため、前景と背景を分けることが困難になる。そこで、本実施形態においては、テクスチャパターンが前景領域上に表われる場合、当該テクスチャパターンを構成する互いに異なる（色空間における色の距離が一定距離以上離れた）少なくとも２つの色（図５の例では、領域７１における色と、領域７２における色）の夫々に対応する前景ピクセルが指定されるように前景領域上にユーザが手がかり線７３を描くことで、少なくとも２つの前景色クラスタを登録させる。これにより、テクスチャパターンがあっても、後述するように正確に前景と背景を分けることが可能となる。
【００３５】
図６は、前景領域にテクスチャパターンが表われている場合において、登録された前景色クラスタ及び背景色クラスタを示す図である。この場合、図６に示すように、２つの前景色クラスタが登録されることになり、夫々の前景色クラスタには、テクスチャパターンを構成する各色に対応する前景ピクセルが夫々属することになる。なお、背景領域にテクスチャパターンが表われることもあり、この場合、前景領域と同様、少なくとも２つの背景色クラスタが登録される。
【００３６】
次に、システム制御部６は、前景、背景かが確定していないピクセルがあるか否かを判別し（ステップＳ４）、ある場合には（ステップＳ４：ＹＥＳ）、ステップＳ５に進み、ない場合には（ステップＳ４：ＮＯ）、前景と背景の区別が完了したことになるので、前景領域をユーザが所望する物体領域として画像から切り抜き（ステップＳ１０）、当該処理を終了する。
【００３７】
一方、ステップＳ５において、システム制御部６は、基準ピクセル（前景ピクセル又は背景ピクセル）に隣接（上下左右の何れかに隣り合う）する隣接ピクセルのうち、ｇｒｏｗ候補として未だ特定されていない１又は２以上のピクセルをｇｒｏｗ候補として特定する。
【００３８】
図７は、画像上におけるピクセルが前景又は背景として確定されていく様子を示す図である。図７（Ａ）の例では、初期段階として、ユーザにより指定された前景ピクセル８１に隣接するピクセル８３，８４と、ユーザにより指定された背景ピクセル８２に隣接するピクセル８５，８６とがｇｒｏｗ候補として特定されている。
【００３９】
次いで、システム制御部６は、特定した各ｇｒｏｗ候補に対して色距離算出処理を行う（ステップＳ６）。この色距離算出処理においては、基準ピクセルとこれに隣接するｇｒｏｗ候補とのＲＧＢ色空間における色の距離が算出される。この色の距離Ｄ（ｐｉ，ｐｊ）は、以下の（２）式で算出できる。
【数２】
2010079477.tif 000004
【００４０】
ここで、ｐｉ（＝（ｐｉ,ｒ，ｐｉ,ｇ，ｐｉ,ｂ））はｇｒｏｗ先ピクセル（ｇｒｏｗ候補）を、ｐｊ（＝（ｐｊ,ｒ，ｐｊ,ｇ，ｐｊ,ｂ））はｇｒｏｗ元ピクセル（基準ピクセル）を示す。
【００４１】
次いで、システム制御部６は、上記色の距離が算出されたｇｒｏｗ候補が、前景色クラスタに属するか否か、及び背景色クラスタに属するか否かを夫々判別する属否判別処理を行う（ステップＳ７）。この属否判別処理においては、ｇｒｏｗ候補ｐｉが属するバケツｂ（ｐｉ）が上記（１）式で算出される。このように、バケツを用いたクラスタリング法によれば、当該ｇｒｏｗ候補が前景色クラスタと背景色クラスタに属するかを、従来の例えばｋ−ｍｅａｎｓ法（Ｋ個のクラスタの各々にその代表であるプロトタイプ（平均値（mean））を与え、夫々の個体を最も近いプロトタイプに割り当てることでクラスタリングを行う手法）に比べ高速（少ない計算量）で判別することが可能となる。
【００４２】
なお、当該判別結果を示す情報はｇｒｏｗ候補に対応付けられて記憶される。
【００４３】
次いで、システム制御部６は、ｇｒｏｗ候補について算出された色の距離Ｄ（ｐｉ，ｐｊ）と、当該ｇｒｏｗ候補について判別された前景色クラスタ及び背景色クラスタへの属否に基づく重み付けと、に基づいて、各ｇｒｏｗ候補についてのｇｒｏｗコストを算出するコスト算出処理を行う（ステップＳ８）。このｇｒｏｗコストｃｏｓｔｉは、以下の（３）式で算出できる。
【数３】
2010079477.tif 000005
【００４４】
ここで、Ｃ１（ｐｉ）及びＣ２（ｐｉ）は、上記クラスタへの属否に基づく重み付けを示している。より具体的には、Ｃ１（ｐｉ）は色の距離Ｄ（ｐｉ，ｐｊ）の重み付けであり、テクスチャパターンへの対応を意図したものである。一方、Ｃ２（ｐｉ）はｇｒｏｗコストの蓄積条件であり、後述する飛び地への対応を意図したものである。また、ｃｏｓｔｊは、ｇｒｏｗ元ピクセルがｇｒｏｗ候補であったときのｇｒｏｗコストを示す。なお、ユーザにより指定されたピクセルの場合、ｇｒｏｗコストはそもそも計算されないのでｃｏｓｔｊ＝０である。
【００４５】
Ｃ１（ｐｉ）は以下の（４）式で表わされる。
【数４】
2010079477.tif 000006
【００４６】
ここで、ｇｒｏｗ元ピクセルｐｊが前景ピクセルの場合、Ｋ１は前景色クラスタであり、Ｋ２は背景色クラスタである一方、ｇｒｏｗ元ピクセルｐｊが背景ピクセルの場合、Ｋ１は背景色クラスタであり、Ｋ２は前景色クラスタである。
【００４７】
この（４）式よれば、ｇｒｏｗ元ピクセルｐｊが前景ピクセルである場合において、ｇｒｏｗ候補ｐｉが前景色クラスタのみに属するときＣ１（ｐｉ）＝１となり、ｇｒｏｗ候補ｐｉが前景色クラスタ及び背景色クラスタの両方に属するか或いは前景色クラスタ及び背景色クラスタのどちらにも属さないときＣ１（ｐｉ）＝２となり、ｇｒｏｗ候補ｐｉが背景色クラスタのみに属するときＣ１（ｐｉ）＝４となる。一方、ｇｒｏｗ元ピクセルｐｊが背景ピクセルである場合において、ｇｒｏｗ候補ｐｉが背景色クラスタのみに属するときＣ１（ｐｉ）＝１となり、ｇｒｏｗ候補ｐｉが前景色クラスタ及び背景色クラスタの両方に属するか或いは前景色クラスタ及び背景色クラスタのどちらにも属さないときＣ１（ｐｉ）＝２となり、ｇｒｏｗ候補ｐｉが前景色クラスタのみに属するときＣ１（ｐｉ）＝４となる。
【００４８】
図８は、画像上にテクスチャパターンがある場合におけるｇｒｏｗコストの大きさを示す図である。
【００４９】
図８に示すように、ピクセルが前景から前景（又は背景から背景）へ移行する（飛ぶ）場合にはＣ１（ｐｉ）は小さくなるのでｇｒｏｗコストは小さくなる一方、ピクセルが前景から背景（又はその逆）へ移行する場合にはＣ１（ｐｉ）は大きくなるのでｇｒｏｗコストは大きくなる。
【００５０】
これにより、重み付けの値を色の距離Ｄ（ｐｉ，ｐｊ）に乗算することにより、テクスチャパターンがあっても正確に前景と背景を分けることが可能となる。
【００５１】
なお、（４）式では、Ｃ１（ｐｉ）は、１,２,４の何れかの値を取り得るようにしたが、この大小関係が重要であり、例えば０．５,１,２としても良い。ただし、Ｃ１（ｐｉ）を１,２,４とした方が、ｇｒｏｗコストの計算を整数演算で済ませることができ、切り捨て誤差を考えると、このように２のべき乗とすることが望ましい。
【００５２】
一方、Ｃ２（ｐｉ）は以下の（５）式で表わされる。
【数５】
2010079477.tif 000007
【００５３】
この（５）式よれば、ｇｒｏｗ元ピクセルｐｊが前景ピクセルである場合において、ｇｒｏｗ候補ｐｉが前景色クラスタのみに属するときＣ２（ｐｉ）＝０となり、ｇｒｏｗ候補ｐｉが前景色クラスタのみに属するものでないときＣ２（ｐｉ）＝１となる。一方、ｇｒｏｗ元ピクセルｐｊが背景ピクセルである場合において、ｇｒｏｗ候補ｐｉが背景色クラスタのみに属するときＣ２（ｐｉ）＝０となり、ｇｒｏｗ候補ｐｉが背景色クラスタのみに属するものでないときＣ２（ｐｉ）＝１となる。
【００５４】
つまり、ｇｒｏｗ候補ｐｉが前景又は背景であることが明らかな場合、Ｃ２（ｐｉ）＝０となり、ｇｒｏｗコスト（ｃｏｓｔｊ）は蓄積されない。一方、ｇｒｏｗ候補ｐｉが前景又は背景であることが明らかでない場合、Ｃ２（ｐｉ）＝１となり、ｇｒｏｗコスト（ｃｏｓｔｊ）は蓄積される。このようにｇｒｏｗコストを蓄積することにより、正確に飛び地への対応を図ることができる。
【００５５】
ここで、飛び地とは、前景領域に囲まれた背景領域（又は背景領域に囲まれた前景領域）を意味し、例えばドーナツの中央部分が該当する。手がかり線をヒントに前景、背景を分ける手法では、上記飛び地内に手がかり線を付け足さない限り、例えば前景領域に囲まれた飛び地を背景としてシステム制御部６が認識することはできない。従って、飛び地をシステム制御部６に認識させるためには、ｇｒｏｗコストが閾値Ｔを超えたときに前景と背景を反転させる必要がある。なお、閾値Ｔは、以下の（６）式で算出できる。
【数６】
2010079477.tif 000008
【００５６】
ここで、Ｆｂは最大輝度の前景色を示し、Ｆｄは最小輝度の前景色を示し、Ｂｂは最大輝度の背景色を示し、Ｂｄは最小輝度の背景色を示す。つまり、閾値Ｔは、最大輝度の前景色Ｆｂと最小輝度の背景色Ｂｄとの距離Ｄ（Ｆｂ，Ｂｄ）と、最小輝度の前景色Ｆｄと最大輝度の背景色Ｂｂとの距離Ｄ（Ｆｄ，Ｂｂ）と、のうち大きい方（ｍａｘ）となる。
【００５７】
しかしながら、飛び地の輪郭部分（例えば前景領域との境界部分）には、一般に、アンチエイリアス（輪郭部分のボケ）があることから、当該輪郭部分において隣接するピクセル間の色の距離は小さく、したがって、前景と背景を閾値Ｔにより正確に反転させることは困難である。そこで、本実施形態においては、上述したように、Ｃ２（ｐｉ）＝１であるときにｇｒｏｗコスト（ｃｏｓｔｊ）を蓄積させ、ｇｒｏｗコストを増大させることで、飛び地において前景と背景を閾値Ｔにより正確に反転させることができる。
【００５８】
図９は、画像上にアンチエイリアスがある場合において、ｇｒｏｗコストを蓄積させない場合（Ａ）と、ｇｒｏｗコストを蓄積させた場合（Ｂ）と、の比較例を示す図である。
【００５９】
図９（Ａ）の例では、ｇｒｏｗコストを蓄積させないので、各ピクセル間で閾値Ｔを超えることができないが、図９（Ｂ）の例では、ｇｒｏｗコストを蓄積させるので、ピクセル９１からピクセル９２へ移行するときのｇｒｏｗコストは閾値Ｔを超えることができる。
【００６０】
そして、システム制御部６は、以上のようにして各ｇｒｏｗ候補についてのｇｒｏｗコストを算出すると、当該算出されたｇｒｏｗコストが最も小さいｇｒｏｗ候補を前景ピクセル又は背景ピクセルとして確定する前景／背景確定処理を行う（ステップＳ９）。例えば、当該ｇｒｏｗ候補との間で色の距離の算出（上記ステップＳ６）が行われた基準ピクセルと同じ前景又は背景ピクセルとして確定（例えば、隣接する基準ピクセルが前景ピクセルであればｇｒｏｗ候補は前景ピクセルとして確定）される。こうして確定されたｇｒｏｗ候補は、以後、新たな基準ピクセルとして扱われることになる。
【００６１】
図７（Ｂ）の例では、ｇｒｏｗコストが最小のピクセル８５が背景ピクセルとして確定されることにより、当該ピクセル８５に隣接するピクセル８７，８８が、新たなｇｒｏｗ候補として特定されている。
【００６２】
そして、システム制御部６は、ステップＳ４に戻り、前景、背景かが確定していないピクセルがあるか否かを判別し、ある場合には（ステップＳ４：ＹＥＳ）、ステップＳ５に進む。次いで、システム制御部６は、新たな基準ピクセルに隣接する隣接ピクセルのうち、ｇｒｏｗ候補として特定されていないピクセルをｇｒｏｗ候補として特定し、当該ｇｒｏｗ候補に対して、上記と同様、色距離算出処理（ステップＳ６）、属否判別処理（ステップＳ７）、コスト算出処理（ステップＳ８）、及び前景／背景確定処理（ステップＳ９）を行う。このような処理がｇｒｏｗ候補が無くなるまで繰り返し行われることにより、当該画像上におけるピクセルが前景又は背景として次第に確定されていき、図７（Ｃ）に示すように、当該画像上における全てのピクセルが前景又は背景として確定されると、上記ステップＳ１０にて、前景領域がユーザが所望する物体領域として当該画像から切り抜きされることになる。
【００６３】
なお、図７（Ｃ）の状態に近づいていくにつれ、あるｇｒｏｗ候補に隣接する基準ピクセルが複数出てくる場合があるが、かかる場合、各基準ピクセルとの間の色の距離及びｇｒｏｗコストが算出されることになり、当該ｇｒｏｗ候補は、ｇｒｏｗコストが小さい方の基準ピクセルと同じ前景又は背景として確定されることになる。
【００６４】
以上説明したように、上記実施形態によれば、ユーザにより指定された前景ピクセル及び背景ピクセルの夫々が属する各基準バケツを特定して前景色クラスタ及び背景色クラスタを事前に登録しておき、前景ピクセル又は背景ピクセルに隣接する隣接ピクセルをｇｒｏｗ候補として特定し、各ｇｒｏｗ候補に対して色距離算出処理、及びバケツを用いたクラスタリング法による属否判別処理を行い、これにより得た色の距離Ｄ（ｐｉ，ｐｊ）と、前景色クラスタ及び背景色クラスタへの属否に基づく重み付けと、に基づいて、各ｇｒｏｗ候補についてのｇｒｏｗコストを算出し、当該ｇｒｏｗコストが最も小さいｇｒｏｗ候補を前景ピクセル又は背景ピクセルとして確定し、このような処理をｇｒｏｗ候補が無くなるまで繰り返し行うように構成したので、ユーザが所望する物体領域（前景領域）を高速に切り抜くことができる。
【００６５】
また、テクスチャパターンが前景領域又は背景領域上に表われる場合、当該テクスチャパターンを構成する互いに異なる少なくとも２つの色の夫々に対応するピクセルを指定して夫々のクラスタ（前景色クラスタ又は背景色クラスタ）を登録させてから、上述したようにｇｒｏｗコストを計算するように構成したので、テクスチャパターンが画像上にあっても正確に前景と背景を分けることができる。
【００６６】
更に、上述した蓄積条件によりｇｒｏｗコストを増大させることで、飛び地の輪郭部分にアンチエイリアスがあっても、飛び地において前景と背景を正確に反転させることができる。
【００６７】
なお、本実施形態における画像編集装置Ｓの利用形態としては、パーソナルコンピュータにおいてスタンドアローンで利用される他にも、例えばインターネット上でクライアントに対して種々の情報提供サービスを行うＷｅｂサーバ等に画像編集装置Ｓの構成及び機能を組み込んで利用されるものであっても良い。
【図面の簡単な説明】
【００６８】
【図１】本実施形態に係る画像編集装置Ｓの概要構成例を示す図である。
【図２】システム制御部６における前景領域抽出処理の一例を示すフローチャートである。
【図３】前景領域上及び背景領域上に描かれた手がかり線の例を示す図である。
【図４】ＲＧＢ色空間を分割数ｓのグリッドで分割したバケツを示す図である。
【図５】テクスチャパターンの一例を示す図である。
【図６】前景領域にテクスチャパターンが表われている場合において、登録された前景色クラスタ及び背景色クラスタを示す図である。
【図７】画像上におけるピクセルが前景又は背景として確定されていく様子を示す図である。
【図８】画像上にテクスチャパターンがある場合におけるｇｒｏｗコストの大きさを示す図である。
【図９】画像上にアンチエイリアスがある場合において、ｇｒｏｗコストを蓄積させない場合（Ａ）と、ｇｒｏｗコストを蓄積させた場合（Ｂ）と、の比較例を示す図である。
【符号の説明】
【００６９】
１  操作部
２  表示部
３  ドライブ部
４  記憶部
５  入出力インターフェース部
６  システム制御部
７  システムバス
Ｓ  画像編集装置
【図１】
2010079477.tif 000009
【図２】
2010079477.tif 000010
【図３】
2010079477.tif 000011
【図４】
2010079477.tif 000012
【図５】
2010079477.tif 000013
【図６】
2010079477.tif 000014
【図７】
2010079477.tif 000015
【図８】
2010079477.tif 000016
【図９】
2010079477.tif 000017