画像処理装置および方法
【解決手段】
一実施形態では、画像を複数のスーパーピクセルに分割する方法が開示される。各スーパーピクセルは該画像の複数のピクセルを含む。該方法は、画像内ピクセル対間の類似性の測定により初期ウェイトセットを計算することを含む。該初期ウェイトセットから、画像上で閾値距離未満のピクセル対について合成ウェイトセットが計算される。合成ウェイトセットの計算は、ピクセル対のウェイトを、ピクセル対の第１ピクセルの第３ピクセルとの初期ウェイトと、第２ピクセルとの第３ピクセルのウェイトとの積の、第３ピクセルセットにわたる和として計算することを含む。その後、各ウェイトはべき乗係数演算を受ける。合成ウェイトセットの計算に続いて、合成ウェイトセットと初期ウェイトセットは、収束チェックのために比較されるウェイトが収束する場合、該収束したウェイトセットは画像をスーパーピクセルに分割するために用いられる。
一実施形態では、画像を複数のスーパーピクセルに分割する方法が開示される。各スーパーピクセルは該画像の複数のピクセルを含む。該方法は、画像内ピクセル対間の類似性の測定により初期ウェイトセットを計算することを含む。該初期ウェイトセットから、画像上で閾値距離未満のピクセル対について合成ウェイトセットが計算される。合成ウェイトセットの計算は、ピクセル対のウェイトを、ピクセル対の第１ピクセルの第３ピクセルとの初期ウェイトと、第２ピクセルとの第３ピクセルのウェイトとの積の、第３ピクセルセットにわたる和として計算することを含む。その後、各ウェイトはべき乗係数演算を受ける。合成ウェイトセットの計算に続いて、合成ウェイトセットと初期ウェイトセットは、収束チェックのために比較されるウェイトが収束する場合、該収束したウェイトセットは画像をスーパーピクセルに分割するために用いられる。
【発明の詳細な説明】
【関連出願】
【０００１】
この出願は、２０１１年３月２３日に提出され、参照することによりその全内容が本明細書に組み込まれる英国特許出願第１１０４９０９．５号に基づいており、その優先権の利益を主張するものである。
【技術分野】
【０００２】
本明細書で説明する実施形態は、一般に画像をセグメント化するための方法およびシステムに関する。
【背景技術】
【０００３】
多くの画像処理技術は、画像をセグメント化する前処理ステップを含んでいる。画像をセグメント化することは、デジタル画像をスーパーピクセルに分割することを含む。各スーパーピクセルは画像の一組のピクセルである。セグメント化の後に、スーパーピクセルについての画像処理が実行される。スーパーピクセルへの画像のセグメント化は、入力画像が画像内の構造的情報を反映するコンパクトな方法で符号化されることを可能にする。これにより、例えば画像内の特徴を分類するための画像処理が容易になる。
【０００４】
セグメント化後の画像のさらなる処理を効率化するために、大きさが一定で形状がコンパクトな均一のスーパーピクセルを生成することが多くの場合に有利である。この要件は、多くの場合、画像をスーパーピクセルにセグメント化する計算コストとのバランスがとられなければならない。
【図面の簡単な説明】
【０００５】
以下では、次の図面を参照しながら発明の実施形態を説明する。
【図１】図１は、画像をスーパーピクセルに分割するためのデータ処理システムのブロック図である。
【図２】図２は、画像をスーパーピクセルに分割するための方法のフローチャートである。
【図３】図３は、画像をスーパーピクセルに分割する方法を示している。
【図４】図４は、スーパーピクセルに分割された画像である。
【図５】図５は、画像のセクションの概要図である。
【図６】図６は、ピクセルの対間のウェイトを計算するのに用いられるパスを示す画像のセクションの概要図である。
【図７】図７は、スーパーピクセルに分割された画像である。
【図８】図８は、画像を処理する方法を示すフローチャートである。
【図９】図９は、画像内のノイズを低減する方法を示すフローチャートである。
【図１０】図１０は、画像の物体を検出する方法を示すフローチャートである。
【図１１】図１１は、画像の３次元再構成の計算方法を示すフローチャートである。
【発明を実施するための形態】
【０００６】
本明細書で説明する実施形態は、画像をスーパーピクセルに分割し、該画像をスーパーピクセルを用いて処理することを対象とする。一実施形態では、画像を複数のスーパーピクセルに分割する方法が示される。各スーパーピクセルは、該画像の複数のピクセルを含む。該方法は該画像のピクセル対間のウェイトを計算することを含んでいる。該計算されたウェイトは、後に画像をスーパーピクセルに分割する方法において用いられる。該ウェイトは、ピクセル対間の類似性の測定から計算される初期ウェイトセットから反復して再計算される。該初期ウェイトセットから、画像上で閾値距離未満のピクセル対について合成ウェイトセットが計算される。該合成ウェイトセットの計算は、ピクセル対のウェイトを、ピクセル対の第１ピクセルの第３ピクセルとの初期ウェイトと、第２ピクセルとの第３ピクセルのウェイトとの積の、第３ピクセルセットにわたる和として計算することを含む。その後、各ウェイトはべき乗係数演算を受ける。合成ウェイトセットの計算に続いて、合成ウェイトセットと初期ウェイトセットは、収束チェックのために比較されるウェイトが収束する場合、該収束したウェイトセットは画像をスーパーピクセルに分割するために用いられる。
【０００７】
本発明の実施形態は、計算上効率的な態様で画像のスーパーピクセルへの分割を容易化する。画像上で互いに閾値距離内のピクセル対のみについて合成ウェイトを計算するので、該方法は、複雑さを大きく増加させることなく、サイズの大きな画像に用いることができる。また、該方法で得られるスーパーピクセルはサイズおよび形状が均一である。このことは、該方法により生成されたスーパーピクセル表現を用いる処理ステップにおける正確な画像処理を可能にする。
【０００８】
実施形態では、第１ピクセルおよび第２ピクセルのウェイトの計算は第１ルックアップテーブルを読み出すことを含む。第１ルックアップテーブルは、第１ピクセルと、第１ピクセルの閾値距離内のピクセルセットの間の画像上の変換セットを表す。画像の正規特性により、互いに閾値距離内にある画像上のピクセル対間の変換は、アルゴリズムの実行前に計算し、ルックアップテーブルに記憶することができる。
【０００９】
実施形態では、第１ピクセルおよび第２ピクセルのウェイトの計算は、第２ルックアップテーブルを読み出すことをさらに含む。第２ルックアップテーブルは、第３ピクセルセットを経由した第１ピクセルから第２ピクセルへの画像上の変換セットを表す。
【００１０】
実施形態では、ピクセル間の類似性の測定はピクセル間の強度の差から計算される。
【００１１】
実施形態では、画像の各ピクセルに関連付けられたウェイトセットを記憶するためのメモリが割り当てられる。該メモリは、所与のピクセルに対して閾値距離内のピクセルの数に応じて割り当てられる。閾値距離未満のピクセル対間でウェイトが計算されるので、所与ピクセルに関連付けられたウェイトの数は当該ウェイトが計算される前に分かる。これは、該方法を開始する前に、ウェイトを記憶するためのメモリを割り当てることができることを意味する。
【００１２】
実施形態では、初期ウェイトは各ピクセルに関連付けられたウェイトセットとしてメモリに記憶される。初期ウェイトセットは、合成ウェイトセットの計算の後に、該合成ウェイトセットに置き換えられる。
【００１３】
一実施形態では、画像を処理する方法は、画像をスーパーピクセルに分割し、該スーパーピクセルを用いて該画像を処理することを含む。
【００１４】
実施形態では、画像を処理することは画像内の特徴を認識することを含む。
【００１５】
実施形態では、画像を処理することは画像を符号化することを含む。
【００１６】
実施形態では、画像を処理することは画像の三次元再構成を計算することを含む。
【００１７】
実施形態では、スーパーピクセルを用いて画像を処理することは、画像内のノイズを低減することを含む。
【００１８】
実施形態では、計算機によって実行された時、該計算機に画像をスーパーピクセルに分割する方法を実行させる計算機実行可能命令を持つ計算機可読媒体が提供される。
【００１９】
実施形態では、画像を複数のスーパーピクセルに分割するための画像処理装置を開示している。各スーパーピクセルは、画像の複数のピクセルを含む。該システムはプロセッサを含む。該プロセッサは、初期ウェイトセットを計算する。各ウェイトは、画像のピクセル対に関連付けられる。初期ウェイトセットは、隣接するピクセル間の類似性の測定を用いて計算される。プロセッサは、初期ウェイトセットから合成ウェイトセットを計算する。画像内において閾値距離未満で離れたピクセル対について合成ウェイトセットが計算される。該合成ウェイトセットは、第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算し、べき乗係数への各ウェイトの値を計算し、ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することにより計算される。該プロセッサは、収束ウェイトセットへの収束をチェックするために、初期ウェイトセットと合成ウェイトセットを比較する。ピクセルは、該収束ウェイトセットを用いて、スーパーピクセルにグループ化される。
【００２０】
実施形態では、システムは、第１ルックアップテーブルのためのストレージをさらに含む。該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示す。プロセッサは、第１ルックアップテーブルを読み出すことにより第１ピクセルおよび第２ピクセルのウェイトを計算する。
【００２１】
実施形態では、システムは、第２ルックアップテーブルのためのストレージをさらに含む。第２ルックアップテーブルは、第３ピクセルセットを経由した第１ピクセルから第２ピクセルへの画像上の変換セットを表す。プロセッサは、第２ルックアップテーブルを読み出すことにより第１ピクセルおよび第２ピクセルのウェイトを計算する。
【００２２】
実施形態では、システムはさらにメモリを含む。該メモリは、画像の各ピクセルに関連付けられたウェイトセットを記憶するために割り当てられる。該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる。
【００２３】
実施形態では、プロセッサは、各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶し、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える。
【００２４】
実施形態では、システムは、スーパーピクセルを用いて画像に更なる処理を施す。
【００２５】
実施形態では、プロセッサは、スーパーピクセルを用いて画像内のノイズを低減する。
【００２６】
実施形態では、プロセッサは、スーパーピクセルを用いて画像内の特徴を認識する。
【００２７】
実施形態では、プロセッサは、スーパーピクセルを用いて画像を符号化する。
【００２８】
実施形態では、プロセッサは、スーパーピクセルを用いて、画像の三次元表現を計算する。
【００２９】
図１は、画像をスーパーピクセルに分割するためのデータ処理システム１００を示している。データ処理システム１００は、プロセッサ１０２、メモリ１０４、入力モジュール１０８および出力モジュール１１０を含む。メモリ１０４は、画像をスーパーピクセルに分割するためのプログラム１０６を記憶する。プログラム１０６は、プロセッサ１０２で実行することができる。入力モジュール１０８は、処理のために画像の入力を受け取ることができる。また、出力モジュール１１０は処理の結果を出力することができる。データ処理システム１００は、画像をさらに処理してもよい。この更なる処理は、スーパーピクセルに基づいてもよい。あるいは、出力モジュール１１０がスーパーピクセルを出力してもよい。入力モジュール１０８は、カメラまたはビデオカメラからイメージデータを受け取ることが可能なデータ接続とすることができる。入力モジュール１０８は、インターネットのようなネットワーク上の画像データを受信することができるネットワーク接続とすることができる。データ処理システム１００は、従来型の計算機であってもよい。以下、プログラム１０６が従う方法を説明する。
【００３０】
図２は、本発明の実施形態に従って画像をスーパーピクセルに分割する方法のフローチャートを示している。該方法は、画像のピクセル間のウェイトを反復して計算することを含んでいる。このウェイトセットの収束が観測されると、該収束したウェイトセットを用いて画像はスーパーピクセルに分割される。ステップＳ１０では、画像のピクセル間の初期ウェイトセットが計算される。初期ウェイトセットは、隣接ピクセル間の類似性の測定から計算される。この類似性の測定は、例えばピクセルの対の強度の差に基づいてもよい。ステップＳ１２では、初期ウェイトセットを用いて合成ウェイトセットが計算される。合成ウェイトセットは、初期ウェイトセットより画像内の多くのピクセル対について計算されうる。合成ウェイトセットは、互いに閾値距離内のピクセルの対に限定して計算される。ステップＳ１４において収束のチェックが行なわれる。これは、初期ウェイトセットと合成ウェイトセットを比較することを含んでいる。合成ウェイトセットと初期ウェイトセットが収束していないことが判明した場合、ステップＳ１６において、合成ウェイトセットは初期ウェイトセットとして記憶される。Ｓ１６に続いて、新しい初期ウェイトセットから更なる合成ウェイトセットが計算される。ステップＳ１４においてウェイトの収束が分かると、ステップＳ１８において画像がスーパーピクセルに分割される。画像をスーパーピクセルに分割することは、非ゼロ・ウェイトを持つピクセルをスーパーピクセルにグループ化することを含む。
【００３１】
上記方法は、マルコフクラスタリング（ＭＣＬ）アルゴリズムに基づいている。ＭＣＬアルゴリズムは、確率的なグラフに反復して２つの演算子を適用することを含む。ＭＣＬアルゴリズムを適用した結果、確率的なグラフは１組のクラスタに分割される。確率的なグラフへの２つの演算子の適用は、グラフのノードがランダムウォーク中にアクセスされる確率付きの、グラフ内のランダムウォークを作ることである（そのランダムウォークにおける他のノードのようにそのノードが同じクラスタの一部を形成するかどうかを決定する）とみなすことができる。画像をスーパーピクセルに分割する問題にＭＣＬアルゴリズムを適用する場合、画像はグラフであるとみなす。グラフ上の各ピクセルは、グラフ上のノードに対応する。グラフ上のエッジは、ピクセルに対応するノードをリンクする。ＭＣＬアルゴリズムのグラフへの適用の結果は、バラバラな木の組である。グラフが画像を表わす場合、これらのバラバラな木は、画像のピクセル群(group of pixels)である。本発明の実施形態は、ＭＣＬアルゴリズムを適用する計算コストおよび生成されたスーパーピクセルの形への影響を低減するＭＣＬアルゴリズムへの修正を含んでいる。
【００３２】
上記のように、ＭＣＬアルゴリズムは確率的なグラフに反復して２つの演算子を適用することを含んでいる。これらはｅｘｐａｎｓｉｏｎ演算子とｉｎｆｌａｔｉｏｎ演算子である。ｅｘｐａｎｓｉｏｎ演算子はグラフ内のフローを巡回するように振る舞い、類似したアピアランスの領域を混ぜ合わせる傾向がある。ｉｎｆｌａｔｉｏｎ演算子は、強いエッジをより強くし、弱いエッジをより弱くする。これは、クラスタ境界を作り、同時に各クラスタの代表を選出するという二重の目的に役立つ。ｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子は、収束まで繰り返し適用される。収束は、グラフがｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子の下で安定している場合に起こると考えられる。収束では、グラフはバラバラな木の組になる。
【００３３】
ＭＣＬアルゴリズムは、以下のように数学的に表すことができる。無向グラフＧ＝（Ｖ，Ｅ）は、ノードｖ∈Ｖおよびエッジｅ∈Ｅで規定される。２のノードｖαおよびｖβにかかるエッジｅは、ｅαβとして表わされる。また、このエッジについてのウェイトはｗ（ｅαβ）と規定され、ｗαβと表わされる。グラフＧはマルコフグラフに変形される。マルコフグラフは、すべてのノードに関して、ノードを基点とするエッジのウェイトが正であって合計が１のグラフである。
【００３４】
マルコフグラフに関して、マルコフ行列として知られる確率行列は、各エントリがエッジウェイトとなるように：
【数１】
【００３５】
のように書くことができる。ここで、Ｎはノードの総数である。
【００３６】
上記定式化において、ｅｘｐａｎｓｉｏｎ演算子とはＭの二乗を計算することである。ｉｎｆｌａｔｉｏｎ演算子とは行列Ｍのアダマール累乗を求めることであって、これにスケーリングステップが続き、結果として得られる行列を再び確率的なものとする。行列のアダマール累乗は、要素について累乗をとることにより計算される。
【００３７】
したがって、マルコフグラフＧ＝（Ｖ，Ｅ）の非負の確率行列Ｍについて、ＭＣＬアルゴリズムのステップは次のように定式化することができる：
【数２】
【００３８】
ここで、Ｈｐ（・）は、べき乗係数ｐによる、要素についてのべき乗演算を表わし、Ｎ（・）は、列についての正規化を表す。これらステップは、ＭをＭｎｅｗに更新しながら繰り返される。ＭとＭｎｅｗの間で差異が観察されない平衡に達すると処理は停止する。この段階で、得られた確率行列によって表される結果のグラフは、その結合が全体のグラフをカバーするバラバラな木の組として現われる。各木は、木のルートによってユニークに表わすことができるクラスタを定義する。したがって、ある所与のノードについて、それが属するクラスタの識別（identity）は、ルートまでその木をトレースすることにより検索することができる。ＭＣＬ処理の振る舞いを司る重要なパラメーターは、インフレーションパラメーターｐである。これは、出力の解像度に影響を及ぼす。高いインフレーション値は、より多数の小クラスタを生成する。ＭＣＬによって生成されるクラスタの数はエマージェント(emergent)であることに留意されたい。すなわち、それは直ちに(directly)設定されない。ＭＣＬの収束時間は、クラスタ化の目標解像度に大きく依存する。これは、予期するクラスタがより粗くなると、より長くなる。さらに、ＭＣＬの収束は、高解像度ではより安定することが知られている。したがって、ＭＣＬは典型的に高い解像度が必要とされるスーパーピクセルの計算に好適であると考えられる。
【００３９】
ＭＣＬアルゴリズムは、以下のように画像をスーパーピクセルに分割するのに用いることができる。ｎｘ×ｎｙピクセルの入力画像ＩをグラフＧ＝（Ｖ，Ｅ）であると解釈する。画像Ｉの各ピクセルは、次の集合内のノードに対応する：
【数３】
【００４０】
ここで、ｆ（ｉ，ｊ）＝ｊ・ｎｘ＋ｉは、ノード（ｉ，ｊ）への１次元インデックスを返すフラットインデックス関数である。ノード数Ｎはピクセル数の合計Ｎ＝ｎｘｎｙである。エッジＥ＝｛ｅαβ｝の集合は例えば隣接のノードを接続する：
【数４】
【００４１】
画像構造は、画像強度の差をエッジウェイトにマッピングする関数を定義することによってグラフ上にマッピングされる。画像に対応するグラフの隣接行列は、８つの近隣類似関数を用いて初期化することができる：
【数５】
【００４２】
ここで、Ｉ［ｉ，ｊ］＝（ｒ，ｇ，ｂ）は、利用可能なチャネル上の画像の強度を表す。パラメーターμは、自由パラメーターとして選ぶことができる。本明細書で提示した結果を得るためにμ＝１０を用いた。
【００４３】
本発明の実施形態において、上述したＭＣＬ処理は、ｅｘｐａｎｓｉｏｎステップにおいてエッジを延長可能な長さを制限するように変更される。この変更には２つの利点があることが判明した。第１に、変更した方法によって得られたスーパーピクセルの形状は均一である。第２に、エッジの長さの制限によって画像をセグメント化する際の計算コストは、エッジ長を制限しないＭＣＬ処理と比較して低下する。
【００４４】
変更されたＭＣＬスキームは、ｅｘｐａｎｓｉｏｎステップで作成された新しいエッジの長さに上界を適用する。これは、ｅｘｐａｎｓｉｏｎステップにおいて下記条件を課すことを含んでいる：
【数６】
【００４５】
ここで、ｒはピクセルの距離しきい値である。
【００４６】
ＭＣＬ処理の収束には形式的証明が存在することに留意されたい。上記条件がｅｘｐａｎｓｉｏｎステップに含まれる場合、処理は近似になる。しかし、変更されたＭＣＬ処理は、適用されたすべての画像について収束することがわかった。
【００４７】
図３は、本発明の実施形態によって画像をスーパーピクセルに分割することに関するステップを示している。図３ａでは、類似性測定を用いてピクセル間のウェイトが初期化される。非ゼロ・ウェイトを持ったピクセル間のリンクあるいはエッジが示される。図３ｂは、数回にわたりｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子を適用した後のピクセル間ウェイトを示している。ここで、ｅｘｐａｎｓｉｏｎ演算子は、ピクセルの対についてウェイトが計算される距離には上界がある、という制約を条件として適用される。図３ｃは、ｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子を収束するまで反復して適用した後の非ゼロ・ウェイトを示す。図３ｄは、図３ｃに示されたウェイトを用いてスーパーピクセルに分割された画像を示している。
【００４８】
図４は、当初のＭＣＬ法によって生成されたスーパーピクセル（図４ａ）と、距離しきい値を含むＭＣＬ法によって生成されたスーパーピクセル（図４ｂ）との間の比較を示す。図４ｂに示されるスーパーピクセルは、サイズおよび形状がより均一であることが明らかである。
【００４９】
上述したエッジ最大長が制約されたＭＣＬ法を適用する際の計算コストは、行列Ｍにおける非ゼロ要素の数を減らし、従ってｅｘｐａｎｓｉｏｎステップにおけるＭ２を算出する際の計算コストを低減する。さらに、ノードに接続されるエッジの最大数が距離制約によって制限され、計算が開始される前にその数が分かることから、行列Ｍの変換を以下のように実装することができる。行列Ｍは、画像の２Ｄ構造を保存し、ノードを基点とする各エッジのウェイトを当該ノードに対応するピクセルに関連させることにより記憶される。ピクセルに対応するノードに関連づけられた非ゼロ・ウェイトの最大数は計算の開始前に既知であることから、計算が初期化される際にボリュームが割り付けられ、この割付けは計算の全体を通じて維持される。
【００５０】
エッジウェイトがボリュームＬに記憶される。ボリュームＬはサイズｎｘ×ｎｙ×Ｎｅを持つ。ここで、ｎｘ×ｎｙは入力画像のピクセルサイズ、Ｎｅは各ノードから発する非ゼロ・ウェイトを持ったエッジの数である。Ｎｅは、画像の各ピクセルの関連づけられたウェイトの数とみなすこともできる。
【００５１】
画像上の位置（ｉ，ｊ）のピクセルについて、エッジ・エントリーＬ［ｉ，ｊ；ｅ］はノードｖｉ，ｊから始まり、（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅ］のノードを指す。ｏｆｆｓｅｔ［ｅ］は、所与ノードからの可能なすべてのジャンプを表わすテーブルである。ｏｆｆｓｅｔ［ｅ］は、エッジｒの最大長に基づいてあらかじめ計算することができる。例えば、ｒ＝１の場合、テーブルオフセットは［（０，０），（−１，０），（＋１，０），（０，−１），（０，＋１）］と与えられる。このテーブルはあらかじめ計算され、グラフ内のすべてのノードで共有することができる。
【００５２】
図５は、画像のピクセルに関連づけられた非ゼロ・ウェイトを示す画像部分の概要図である。画像５００は、複数のピクセル５０２、５０４、５０６を含む。画像５０２のピクセルは、距離ｒ内のピクセル５０４とともに非ゼロ・ウェイトを持っている。図５の例において、ｒ＝√２である。ピクセル５０２とそれ自体の間のエッジ５０３に関連づけられた非ゼロ・ウェイト、および、ピクセル５０２と、画像中でピクセル５０２からｒ＝√２未満のピクセル群５０４との間のエッジ群５０５に関連づけられた非ゼロ・ウェイトがある。
【００５３】
図５に示される場合では、ｏｆｆｓｅｔ＝［（０；０）；（１；０）；（１；１）；（０；１）；（−１；１）；（−１；０）；（−１；−１）；（０；−１）；（１；−１）］である。このテーブルは、画像グラフの正規の特性を示すことから、すべてのノードによって共有される。
【００５４】
上述した行列変換は、変更されたＭＣＬ処理のｅｘｐａｎｓｉｏｎ演算の計算におけるＭ２の計算を容易にする。Ｍ２＝Ｍ２の各要素は下記から与えられる：
【数７】
【００５５】
グラフの観点では、この式は、パス上のウェイトｗαβを、第三のノードｖγを介してノードｖαをノードｖβにつなぐ２−パス上のすべてのウェイトの積和で置き換えることであると考えられる。上記の変換によれば、所与のノードを基点とするエッジを効率的に判定することが可能になる。
【００５６】
２つのノードをつなぐ２−パスの組はあらかじめ計算され、ルックアップテーブルに記憶される。これは、画像に関するグラフの正規の特性によって可能である。
【００５７】
図６は、ノードｖｉ，ｊとノードｖｍ，ｎの間のエッジのウェイト計算に用いられる２−パスの組を示す。ノードｖｍ，ｎは画像内のｖｉ，ｊの１ピクセル上であって１ピクセル右であるから、このエッジはｏｆｆｓｅｔ［ｅ］＝（１，１）に対応する。
【００５８】
Ｍ２を計算する場合、ｅ∈［０，Ｎｅ］から与えられたエッジのウェイトが各ノードについて更新される。ｅ番目のエッジは、ノードｖｍ，ｎから始まり、ｖｉ，ｊで終わる。ここで、（ｍ，ｎ）＝（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅ］である。（ｉ，ｊ）→（ｓ，ｔ）→（ｍ，ｎ）を接続する一般的な２パスは、［ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄ］と定義される。ここで、
（ｓ，ｔ）＝（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅｆｉｒｓｔ］、
（ｍ，ｎ）＝（ｓ，ｔ）＋ｏｆｆｓｅｔ［ｅｓｅｃｏｎｄ］
である。
【００５９】
ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄのあらかじめ計算された２−パスを用いるルックアップテーブルが、各ｅについて用いられる。このテーブルをｄｅｔｏｕｒ［ｅ］と表記する。テーブルｄｅｔｏｕｒ［ｅ］は、ｖｍ，ｎを経由したｖｉ，ｊからｖｓ，ｔへのジャンプが可能な全てのインデックス（ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄ）を含んでいる。
【００６０】
上述のアルゴリズムの複雑さは、当初のＭＣＬの場合のＯ（Ｎ３）とは対照的にＯ（Ｎｒ４）である。これは、本アルゴリズムがサイズの大きな画像をスーパーピクセルにセグメント化するのに適していることを意味する。
【００６１】
さらに、Ｍ２を計算するための上述のアルゴリズムは、１ピクセルあたり１スレッドのパラレルアーキテクチャーに効率的にマッピングすることができる。ｉｎｆｌａｔｉｏｎ演算の計算についても、１ピクセルあたり１スレッドで実装することができる。したがって、本発明の実施形態によれば、上述のように変更したＭＣＬ処理はＧＰＵ上に実装することができる。
【００６２】
上記実装においては、当初のＭＣＬ法と比較して１０倍の高速化が見られた。さらに、当該変更された方法は、当初のＭＣＬ法の場合ではメモリを使い果たすようなサイズの大きな画像をセグメント化することができる。
【００６３】
図７は、上述した方法を用いるスーパーピクセルへの画像分割を示す。当該画像は４１２×４００ピクセルである。この例において、インフレーションパラメーターｐ＝１．４とし、距離しきい値はｄ＝４．５とした。本アルゴリズムは、単精度浮動小数点（３４５ＧＦＬＯＰ）を用いるＮＶＩＤＩＡ Ｑｕａｄｒｏ Ｆｘ ４６００ ＧＰＵ上でＮＶＩＤＩＡ ＣＵＤＡ並列処理アーキテクチャを用いて実装された。本アルゴリズムは、図７に示すようなスーパーピクセルに画像を分割するのに２１．４５秒を要した。図７から分かるように、本アルゴリズムは、形が一様でサイズが均一なスーパーピクセルを生成する。
【００６４】
図８は、スーパーピクセルへの画像分割に上述した方法を用いる場合の画像処理方法のフローチャートである。ステップＳ８０２では、原画像を受け取る。ステップＳ８０４では、上述した方法によって当該画像をスーパーピクセルに分割する。Ｓ８０６では、Ｓ８０４において得られたスーパーピクセル表現を用いて当該画像を処理する。
【００６５】
スーパーピクセルを用いた画像処理は、例えば画像内の物体検出であってもよい。例えば、画像内のスーパーピクセルに基づいて、当該画像から人間の顔が検出され得る。スーパーピクセルを用いた画像処理は、画像分類、画像の３Ｄ再構成、画像の圧縮または符号化であってもよい。例えば、当業者に既知のアルゴリズムを用いて画像を圧縮または暗号化してもよい。
【００６６】
図９は、画像のノイズを低減する方法のフローチャートを示している。ステップＳ９０２では、上述した方法を用いて画像がスーパーピクセルに分割される。ステップＳ９０４では、各スーパーピクセル内のノイズが次のように推定される。各スーパーピクセル内のピクセル輝度を平滑化し、その残余を抽出する。この残余をノイズとする。ステップＳ９０６では、画像に双方向フィルタが適用される。双方向フィルタの平滑化能力は、各ピクセルで推定されたノイズに適合する。上述した方法を用いて画像がスーパーピクセルに分割される場合、均一のスーパーピクセルが生成されることに留意されたい。図９に示されるノイズ低減法において、均一のスーパーピクセルとしていることにより、画像の全体にわたってノイズを一貫して推定することが可能である。
【００６７】
図１０は、画像内の物体を検出する方法のフローチャートを示している。該方法は、一枚の画像から物体を検出したり、映像シーケンスのフレーム群にわたって物体を追跡するのに用いることができる。ステップＳ１００２では、上述した方法を用いて、画像がスーパーピクセルに分割される。ステップＳ１００４では、各スーパーピクセルが、検出する物体の一部に対応する確率が計算される。これは、背景からのスーパーピクセルのセパレーション、形状の手掛かり、シェーディング、物体の部分を表わす可能性のあるスーパーピクセルのグループと背景を表わすグループの間にはっきりした差異があるかどうかといった要素に基づく。ステップＳ１００６では、候補部分から物体表現が選ばれる。このステップＳ１００６における選択は、ステップＳ１００４で計算された確率、さらには、検出物体の相対的位置、相対サイズおよび対称性についての拘束を用いてなされる。
【００６８】
図１０に示された方法を用いて検出される物体は、人物であってもよい。この場合、Ｓ１００４では、物体の部分を人物の手足もしくはその一部、頭部もしくはその一部、または胴体もしくはその一部として確率を計算する。これらの部分の候補が画像内で識別されると、ステップＳ１００６において、当該画像から人物を検出することができる。ここで、相対位置は、頭部と胴体に対する手足の位置である。対称性の要件とは、例えば左腕と右腕の衣服には対称性があることである。
【００６９】
本出願で述べた方法によって生成されるスーパーピクセルは均一であることから、これらは類似ブロックと見なすことができ、アセンブルステップＳ１００６はより簡単になり、様々な形やサイズのスーパーピクセルが用いられる場合よりも正確になる。
【００７０】
図１１は、画像の三次元再構成を計算する方法のフローチャートを示している。ステップＳ１１０２では、上述した方法を用いて、画像がスーパーピクセルに分割される。本方法では、各スーパーピクセルは平面であることを仮定している。ステップＳ１１０４では、各スーパーピクセルの奥行きおよび法線方向が計算される。これは、マルコフ確率場（Ｍａｒｋｏｖ Ｒａｎｄｏｍ Ｆｉｅｌｄ：ＭＲＦ）の最大事後確率割当を探索することにより実行される。これは、シーンのビューに投影する場合、最小のフォトコンシステンシ（ｐｈｏｔｏｃｏｎｓｉｓｔｅｎｃｙ）エラーを与える各スーパーピクセルの奥行きおよび法線方向を検出するとともに、隣接するスーパーピクセルの奥行きおよび法線の滑らかな変更を考慮することを含んでいる。ステップＳ１１０６では、奥行きと法線方向に基づいて三次元再構成が計算される。該三次元再構成が二以上の画像に基づいてもよい。例えば、該三次元再構成が異なる位置から撮影された一連の画像に基づいてもよい。
【００７１】
図１１に示す方法において均一のスーパーピクセルを用いる場合、低い計算コストで正確な結果を得ることができる。非均一性がＭＲＦソルバーの性能を低下させうることが知られている。
【００７２】
いくつかの実施形態を説明したが、これらの実施形態は例示のみを目的としており、発明の範囲を制限することは意図していない。実際には、本明細書で説明した新規の方法およびシステムは他の様々な形で具体化することができ、また発明の要旨から逸脱しない範囲で、本明細書で説明した方法およびシステムの構造における様々な省略、置換、および変更を行ってもよい。添付の特許請求の範囲およびその均等物は、発明の範囲および要旨に含まれうる構造あるいは改良に及ぶことが意図される。
【関連出願】
【０００１】
この出願は、２０１１年３月２３日に提出され、参照することによりその全内容が本明細書に組み込まれる英国特許出願第１１０４９０９．５号に基づいており、その優先権の利益を主張するものである。
【技術分野】
【０００２】
本明細書で説明する実施形態は、一般に画像をセグメント化するための方法およびシステムに関する。
【背景技術】
【０００３】
多くの画像処理技術は、画像をセグメント化する前処理ステップを含んでいる。画像をセグメント化することは、デジタル画像をスーパーピクセルに分割することを含む。各スーパーピクセルは画像の一組のピクセルである。セグメント化の後に、スーパーピクセルについての画像処理が実行される。スーパーピクセルへの画像のセグメント化は、入力画像が画像内の構造的情報を反映するコンパクトな方法で符号化されることを可能にする。これにより、例えば画像内の特徴を分類するための画像処理が容易になる。
【０００４】
セグメント化後の画像のさらなる処理を効率化するために、大きさが一定で形状がコンパクトな均一のスーパーピクセルを生成することが多くの場合に有利である。この要件は、多くの場合、画像をスーパーピクセルにセグメント化する計算コストとのバランスがとられなければならない。
【図面の簡単な説明】
【０００５】
以下では、次の図面を参照しながら発明の実施形態を説明する。
【図１】図１は、画像をスーパーピクセルに分割するためのデータ処理システムのブロック図である。
【図２】図２は、画像をスーパーピクセルに分割するための方法のフローチャートである。
【図３】図３は、画像をスーパーピクセルに分割する方法を示している。
【図４】図４は、スーパーピクセルに分割された画像である。
【図５】図５は、画像のセクションの概要図である。
【図６】図６は、ピクセルの対間のウェイトを計算するのに用いられるパスを示す画像のセクションの概要図である。
【図７】図７は、スーパーピクセルに分割された画像である。
【図８】図８は、画像を処理する方法を示すフローチャートである。
【図９】図９は、画像内のノイズを低減する方法を示すフローチャートである。
【図１０】図１０は、画像の物体を検出する方法を示すフローチャートである。
【図１１】図１１は、画像の３次元再構成の計算方法を示すフローチャートである。
【発明を実施するための形態】
【０００６】
本明細書で説明する実施形態は、画像をスーパーピクセルに分割し、該画像をスーパーピクセルを用いて処理することを対象とする。一実施形態では、画像を複数のスーパーピクセルに分割する方法が示される。各スーパーピクセルは、該画像の複数のピクセルを含む。該方法は該画像のピクセル対間のウェイトを計算することを含んでいる。該計算されたウェイトは、後に画像をスーパーピクセルに分割する方法において用いられる。該ウェイトは、ピクセル対間の類似性の測定から計算される初期ウェイトセットから反復して再計算される。該初期ウェイトセットから、画像上で閾値距離未満のピクセル対について合成ウェイトセットが計算される。該合成ウェイトセットの計算は、ピクセル対のウェイトを、ピクセル対の第１ピクセルの第３ピクセルとの初期ウェイトと、第２ピクセルとの第３ピクセルのウェイトとの積の、第３ピクセルセットにわたる和として計算することを含む。その後、各ウェイトはべき乗係数演算を受ける。合成ウェイトセットの計算に続いて、合成ウェイトセットと初期ウェイトセットは、収束チェックのために比較されるウェイトが収束する場合、該収束したウェイトセットは画像をスーパーピクセルに分割するために用いられる。
【０００７】
本発明の実施形態は、計算上効率的な態様で画像のスーパーピクセルへの分割を容易化する。画像上で互いに閾値距離内のピクセル対のみについて合成ウェイトを計算するので、該方法は、複雑さを大きく増加させることなく、サイズの大きな画像に用いることができる。また、該方法で得られるスーパーピクセルはサイズおよび形状が均一である。このことは、該方法により生成されたスーパーピクセル表現を用いる処理ステップにおける正確な画像処理を可能にする。
【０００８】
実施形態では、第１ピクセルおよび第２ピクセルのウェイトの計算は第１ルックアップテーブルを読み出すことを含む。第１ルックアップテーブルは、第１ピクセルと、第１ピクセルの閾値距離内のピクセルセットの間の画像上の変換セットを表す。画像の正規特性により、互いに閾値距離内にある画像上のピクセル対間の変換は、アルゴリズムの実行前に計算し、ルックアップテーブルに記憶することができる。
【０００９】
実施形態では、第１ピクセルおよび第２ピクセルのウェイトの計算は、第２ルックアップテーブルを読み出すことをさらに含む。第２ルックアップテーブルは、第３ピクセルセットを経由した第１ピクセルから第２ピクセルへの画像上の変換セットを表す。
【００１０】
実施形態では、ピクセル間の類似性の測定はピクセル間の強度の差から計算される。
【００１１】
実施形態では、画像の各ピクセルに関連付けられたウェイトセットを記憶するためのメモリが割り当てられる。該メモリは、所与のピクセルに対して閾値距離内のピクセルの数に応じて割り当てられる。閾値距離未満のピクセル対間でウェイトが計算されるので、所与ピクセルに関連付けられたウェイトの数は当該ウェイトが計算される前に分かる。これは、該方法を開始する前に、ウェイトを記憶するためのメモリを割り当てることができることを意味する。
【００１２】
実施形態では、初期ウェイトは各ピクセルに関連付けられたウェイトセットとしてメモリに記憶される。初期ウェイトセットは、合成ウェイトセットの計算の後に、該合成ウェイトセットに置き換えられる。
【００１３】
一実施形態では、画像を処理する方法は、画像をスーパーピクセルに分割し、該スーパーピクセルを用いて該画像を処理することを含む。
【００１４】
実施形態では、画像を処理することは画像内の特徴を認識することを含む。
【００１５】
実施形態では、画像を処理することは画像を符号化することを含む。
【００１６】
実施形態では、画像を処理することは画像の三次元再構成を計算することを含む。
【００１７】
実施形態では、スーパーピクセルを用いて画像を処理することは、画像内のノイズを低減することを含む。
【００１８】
実施形態では、計算機によって実行された時、該計算機に画像をスーパーピクセルに分割する方法を実行させる計算機実行可能命令を持つ計算機可読媒体が提供される。
【００１９】
実施形態では、画像を複数のスーパーピクセルに分割するための画像処理装置を開示している。各スーパーピクセルは、画像の複数のピクセルを含む。該システムはプロセッサを含む。該プロセッサは、初期ウェイトセットを計算する。各ウェイトは、画像のピクセル対に関連付けられる。初期ウェイトセットは、隣接するピクセル間の類似性の測定を用いて計算される。プロセッサは、初期ウェイトセットから合成ウェイトセットを計算する。画像内において閾値距離未満で離れたピクセル対について合成ウェイトセットが計算される。該合成ウェイトセットは、第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算し、べき乗係数への各ウェイトの値を計算し、ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することにより計算される。該プロセッサは、収束ウェイトセットへの収束をチェックするために、初期ウェイトセットと合成ウェイトセットを比較する。ピクセルは、該収束ウェイトセットを用いて、スーパーピクセルにグループ化される。
【００２０】
実施形態では、システムは、第１ルックアップテーブルのためのストレージをさらに含む。該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示す。プロセッサは、第１ルックアップテーブルを読み出すことにより第１ピクセルおよび第２ピクセルのウェイトを計算する。
【００２１】
実施形態では、システムは、第２ルックアップテーブルのためのストレージをさらに含む。第２ルックアップテーブルは、第３ピクセルセットを経由した第１ピクセルから第２ピクセルへの画像上の変換セットを表す。プロセッサは、第２ルックアップテーブルを読み出すことにより第１ピクセルおよび第２ピクセルのウェイトを計算する。
【００２２】
実施形態では、システムはさらにメモリを含む。該メモリは、画像の各ピクセルに関連付けられたウェイトセットを記憶するために割り当てられる。該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる。
【００２３】
実施形態では、プロセッサは、各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶し、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える。
【００２４】
実施形態では、システムは、スーパーピクセルを用いて画像に更なる処理を施す。
【００２５】
実施形態では、プロセッサは、スーパーピクセルを用いて画像内のノイズを低減する。
【００２６】
実施形態では、プロセッサは、スーパーピクセルを用いて画像内の特徴を認識する。
【００２７】
実施形態では、プロセッサは、スーパーピクセルを用いて画像を符号化する。
【００２８】
実施形態では、プロセッサは、スーパーピクセルを用いて、画像の三次元表現を計算する。
【００２９】
図１は、画像をスーパーピクセルに分割するためのデータ処理システム１００を示している。データ処理システム１００は、プロセッサ１０２、メモリ１０４、入力モジュール１０８および出力モジュール１１０を含む。メモリ１０４は、画像をスーパーピクセルに分割するためのプログラム１０６を記憶する。プログラム１０６は、プロセッサ１０２で実行することができる。入力モジュール１０８は、処理のために画像の入力を受け取ることができる。また、出力モジュール１１０は処理の結果を出力することができる。データ処理システム１００は、画像をさらに処理してもよい。この更なる処理は、スーパーピクセルに基づいてもよい。あるいは、出力モジュール１１０がスーパーピクセルを出力してもよい。入力モジュール１０８は、カメラまたはビデオカメラからイメージデータを受け取ることが可能なデータ接続とすることができる。入力モジュール１０８は、インターネットのようなネットワーク上の画像データを受信することができるネットワーク接続とすることができる。データ処理システム１００は、従来型の計算機であってもよい。以下、プログラム１０６が従う方法を説明する。
【００３０】
図２は、本発明の実施形態に従って画像をスーパーピクセルに分割する方法のフローチャートを示している。該方法は、画像のピクセル間のウェイトを反復して計算することを含んでいる。このウェイトセットの収束が観測されると、該収束したウェイトセットを用いて画像はスーパーピクセルに分割される。ステップＳ１０では、画像のピクセル間の初期ウェイトセットが計算される。初期ウェイトセットは、隣接ピクセル間の類似性の測定から計算される。この類似性の測定は、例えばピクセルの対の強度の差に基づいてもよい。ステップＳ１２では、初期ウェイトセットを用いて合成ウェイトセットが計算される。合成ウェイトセットは、初期ウェイトセットより画像内の多くのピクセル対について計算されうる。合成ウェイトセットは、互いに閾値距離内のピクセルの対に限定して計算される。ステップＳ１４において収束のチェックが行なわれる。これは、初期ウェイトセットと合成ウェイトセットを比較することを含んでいる。合成ウェイトセットと初期ウェイトセットが収束していないことが判明した場合、ステップＳ１６において、合成ウェイトセットは初期ウェイトセットとして記憶される。Ｓ１６に続いて、新しい初期ウェイトセットから更なる合成ウェイトセットが計算される。ステップＳ１４においてウェイトの収束が分かると、ステップＳ１８において画像がスーパーピクセルに分割される。画像をスーパーピクセルに分割することは、非ゼロ・ウェイトを持つピクセルをスーパーピクセルにグループ化することを含む。
【００３１】
上記方法は、マルコフクラスタリング（ＭＣＬ）アルゴリズムに基づいている。ＭＣＬアルゴリズムは、確率的なグラフに反復して２つの演算子を適用することを含む。ＭＣＬアルゴリズムを適用した結果、確率的なグラフは１組のクラスタに分割される。確率的なグラフへの２つの演算子の適用は、グラフのノードがランダムウォーク中にアクセスされる確率付きの、グラフ内のランダムウォークを作ることである（そのランダムウォークにおける他のノードのようにそのノードが同じクラスタの一部を形成するかどうかを決定する）とみなすことができる。画像をスーパーピクセルに分割する問題にＭＣＬアルゴリズムを適用する場合、画像はグラフであるとみなす。グラフ上の各ピクセルは、グラフ上のノードに対応する。グラフ上のエッジは、ピクセルに対応するノードをリンクする。ＭＣＬアルゴリズムのグラフへの適用の結果は、バラバラな木の組である。グラフが画像を表わす場合、これらのバラバラな木は、画像のピクセル群(group of pixels)である。本発明の実施形態は、ＭＣＬアルゴリズムを適用する計算コストおよび生成されたスーパーピクセルの形への影響を低減するＭＣＬアルゴリズムへの修正を含んでいる。
【００３２】
上記のように、ＭＣＬアルゴリズムは確率的なグラフに反復して２つの演算子を適用することを含んでいる。これらはｅｘｐａｎｓｉｏｎ演算子とｉｎｆｌａｔｉｏｎ演算子である。ｅｘｐａｎｓｉｏｎ演算子はグラフ内のフローを巡回するように振る舞い、類似したアピアランスの領域を混ぜ合わせる傾向がある。ｉｎｆｌａｔｉｏｎ演算子は、強いエッジをより強くし、弱いエッジをより弱くする。これは、クラスタ境界を作り、同時に各クラスタの代表を選出するという二重の目的に役立つ。ｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子は、収束まで繰り返し適用される。収束は、グラフがｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子の下で安定している場合に起こると考えられる。収束では、グラフはバラバラな木の組になる。
【００３３】
ＭＣＬアルゴリズムは、以下のように数学的に表すことができる。無向グラフＧ＝（Ｖ，Ｅ）は、ノードｖ∈Ｖおよびエッジｅ∈Ｅで規定される。２のノードｖαおよびｖβにかかるエッジｅは、ｅαβとして表わされる。また、このエッジについてのウェイトはｗ（ｅαβ）と規定され、ｗαβと表わされる。グラフＧはマルコフグラフに変形される。マルコフグラフは、すべてのノードに関して、ノードを基点とするエッジのウェイトが正であって合計が１のグラフである。
【００３４】
マルコフグラフに関して、マルコフ行列として知られる確率行列は、各エントリがエッジウェイトとなるように：
【数１】
【００３５】
のように書くことができる。ここで、Ｎはノードの総数である。
【００３６】
上記定式化において、ｅｘｐａｎｓｉｏｎ演算子とはＭの二乗を計算することである。ｉｎｆｌａｔｉｏｎ演算子とは行列Ｍのアダマール累乗を求めることであって、これにスケーリングステップが続き、結果として得られる行列を再び確率的なものとする。行列のアダマール累乗は、要素について累乗をとることにより計算される。
【００３７】
したがって、マルコフグラフＧ＝（Ｖ，Ｅ）の非負の確率行列Ｍについて、ＭＣＬアルゴリズムのステップは次のように定式化することができる：
【数２】
【００３８】
ここで、Ｈｐ（・）は、べき乗係数ｐによる、要素についてのべき乗演算を表わし、Ｎ（・）は、列についての正規化を表す。これらステップは、ＭをＭｎｅｗに更新しながら繰り返される。ＭとＭｎｅｗの間で差異が観察されない平衡に達すると処理は停止する。この段階で、得られた確率行列によって表される結果のグラフは、その結合が全体のグラフをカバーするバラバラな木の組として現われる。各木は、木のルートによってユニークに表わすことができるクラスタを定義する。したがって、ある所与のノードについて、それが属するクラスタの識別（identity）は、ルートまでその木をトレースすることにより検索することができる。ＭＣＬ処理の振る舞いを司る重要なパラメーターは、インフレーションパラメーターｐである。これは、出力の解像度に影響を及ぼす。高いインフレーション値は、より多数の小クラスタを生成する。ＭＣＬによって生成されるクラスタの数はエマージェント(emergent)であることに留意されたい。すなわち、それは直ちに(directly)設定されない。ＭＣＬの収束時間は、クラスタ化の目標解像度に大きく依存する。これは、予期するクラスタがより粗くなると、より長くなる。さらに、ＭＣＬの収束は、高解像度ではより安定することが知られている。したがって、ＭＣＬは典型的に高い解像度が必要とされるスーパーピクセルの計算に好適であると考えられる。
【００３９】
ＭＣＬアルゴリズムは、以下のように画像をスーパーピクセルに分割するのに用いることができる。ｎｘ×ｎｙピクセルの入力画像ＩをグラフＧ＝（Ｖ，Ｅ）であると解釈する。画像Ｉの各ピクセルは、次の集合内のノードに対応する：
【数３】
【００４０】
ここで、ｆ（ｉ，ｊ）＝ｊ・ｎｘ＋ｉは、ノード（ｉ，ｊ）への１次元インデックスを返すフラットインデックス関数である。ノード数Ｎはピクセル数の合計Ｎ＝ｎｘｎｙである。エッジＥ＝｛ｅαβ｝の集合は例えば隣接のノードを接続する：
【数４】
【００４１】
画像構造は、画像強度の差をエッジウェイトにマッピングする関数を定義することによってグラフ上にマッピングされる。画像に対応するグラフの隣接行列は、８つの近隣類似関数を用いて初期化することができる：
【数５】
【００４２】
ここで、Ｉ［ｉ，ｊ］＝（ｒ，ｇ，ｂ）は、利用可能なチャネル上の画像の強度を表す。パラメーターμは、自由パラメーターとして選ぶことができる。本明細書で提示した結果を得るためにμ＝１０を用いた。
【００４３】
本発明の実施形態において、上述したＭＣＬ処理は、ｅｘｐａｎｓｉｏｎステップにおいてエッジを延長可能な長さを制限するように変更される。この変更には２つの利点があることが判明した。第１に、変更した方法によって得られたスーパーピクセルの形状は均一である。第２に、エッジの長さの制限によって画像をセグメント化する際の計算コストは、エッジ長を制限しないＭＣＬ処理と比較して低下する。
【００４４】
変更されたＭＣＬスキームは、ｅｘｐａｎｓｉｏｎステップで作成された新しいエッジの長さに上界を適用する。これは、ｅｘｐａｎｓｉｏｎステップにおいて下記条件を課すことを含んでいる：
【数６】
【００４５】
ここで、ｒはピクセルの距離しきい値である。
【００４６】
ＭＣＬ処理の収束には形式的証明が存在することに留意されたい。上記条件がｅｘｐａｎｓｉｏｎステップに含まれる場合、処理は近似になる。しかし、変更されたＭＣＬ処理は、適用されたすべての画像について収束することがわかった。
【００４７】
図３は、本発明の実施形態によって画像をスーパーピクセルに分割することに関するステップを示している。図３ａでは、類似性測定を用いてピクセル間のウェイトが初期化される。非ゼロ・ウェイトを持ったピクセル間のリンクあるいはエッジが示される。図３ｂは、数回にわたりｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子を適用した後のピクセル間ウェイトを示している。ここで、ｅｘｐａｎｓｉｏｎ演算子は、ピクセルの対についてウェイトが計算される距離には上界がある、という制約を条件として適用される。図３ｃは、ｅｘｐａｎｓｉｏｎ演算子およびｉｎｆｌａｔｉｏｎ演算子を収束するまで反復して適用した後の非ゼロ・ウェイトを示す。図３ｄは、図３ｃに示されたウェイトを用いてスーパーピクセルに分割された画像を示している。
【００４８】
図４は、当初のＭＣＬ法によって生成されたスーパーピクセル（図４ａ）と、距離しきい値を含むＭＣＬ法によって生成されたスーパーピクセル（図４ｂ）との間の比較を示す。図４ｂに示されるスーパーピクセルは、サイズおよび形状がより均一であることが明らかである。
【００４９】
上述したエッジ最大長が制約されたＭＣＬ法を適用する際の計算コストは、行列Ｍにおける非ゼロ要素の数を減らし、従ってｅｘｐａｎｓｉｏｎステップにおけるＭ２を算出する際の計算コストを低減する。さらに、ノードに接続されるエッジの最大数が距離制約によって制限され、計算が開始される前にその数が分かることから、行列Ｍの変換を以下のように実装することができる。行列Ｍは、画像の２Ｄ構造を保存し、ノードを基点とする各エッジのウェイトを当該ノードに対応するピクセルに関連させることにより記憶される。ピクセルに対応するノードに関連づけられた非ゼロ・ウェイトの最大数は計算の開始前に既知であることから、計算が初期化される際にボリュームが割り付けられ、この割付けは計算の全体を通じて維持される。
【００５０】
エッジウェイトがボリュームＬに記憶される。ボリュームＬはサイズｎｘ×ｎｙ×Ｎｅを持つ。ここで、ｎｘ×ｎｙは入力画像のピクセルサイズ、Ｎｅは各ノードから発する非ゼロ・ウェイトを持ったエッジの数である。Ｎｅは、画像の各ピクセルの関連づけられたウェイトの数とみなすこともできる。
【００５１】
画像上の位置（ｉ，ｊ）のピクセルについて、エッジ・エントリーＬ［ｉ，ｊ；ｅ］はノードｖｉ，ｊから始まり、（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅ］のノードを指す。ｏｆｆｓｅｔ［ｅ］は、所与ノードからの可能なすべてのジャンプを表わすテーブルである。ｏｆｆｓｅｔ［ｅ］は、エッジｒの最大長に基づいてあらかじめ計算することができる。例えば、ｒ＝１の場合、テーブルオフセットは［（０，０），（−１，０），（＋１，０），（０，−１），（０，＋１）］と与えられる。このテーブルはあらかじめ計算され、グラフ内のすべてのノードで共有することができる。
【００５２】
図５は、画像のピクセルに関連づけられた非ゼロ・ウェイトを示す画像部分の概要図である。画像５００は、複数のピクセル５０２、５０４、５０６を含む。画像５０２のピクセルは、距離ｒ内のピクセル５０４とともに非ゼロ・ウェイトを持っている。図５の例において、ｒ＝√２である。ピクセル５０２とそれ自体の間のエッジ５０３に関連づけられた非ゼロ・ウェイト、および、ピクセル５０２と、画像中でピクセル５０２からｒ＝√２未満のピクセル群５０４との間のエッジ群５０５に関連づけられた非ゼロ・ウェイトがある。
【００５３】
図５に示される場合では、ｏｆｆｓｅｔ＝［（０；０）；（１；０）；（１；１）；（０；１）；（−１；１）；（−１；０）；（−１；−１）；（０；−１）；（１；−１）］である。このテーブルは、画像グラフの正規の特性を示すことから、すべてのノードによって共有される。
【００５４】
上述した行列変換は、変更されたＭＣＬ処理のｅｘｐａｎｓｉｏｎ演算の計算におけるＭ２の計算を容易にする。Ｍ２＝Ｍ２の各要素は下記から与えられる：
【数７】
【００５５】
グラフの観点では、この式は、パス上のウェイトｗαβを、第三のノードｖγを介してノードｖαをノードｖβにつなぐ２−パス上のすべてのウェイトの積和で置き換えることであると考えられる。上記の変換によれば、所与のノードを基点とするエッジを効率的に判定することが可能になる。
【００５６】
２つのノードをつなぐ２−パスの組はあらかじめ計算され、ルックアップテーブルに記憶される。これは、画像に関するグラフの正規の特性によって可能である。
【００５７】
図６は、ノードｖｉ，ｊとノードｖｍ，ｎの間のエッジのウェイト計算に用いられる２−パスの組を示す。ノードｖｍ，ｎは画像内のｖｉ，ｊの１ピクセル上であって１ピクセル右であるから、このエッジはｏｆｆｓｅｔ［ｅ］＝（１，１）に対応する。
【００５８】
Ｍ２を計算する場合、ｅ∈［０，Ｎｅ］から与えられたエッジのウェイトが各ノードについて更新される。ｅ番目のエッジは、ノードｖｍ，ｎから始まり、ｖｉ，ｊで終わる。ここで、（ｍ，ｎ）＝（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅ］である。（ｉ，ｊ）→（ｓ，ｔ）→（ｍ，ｎ）を接続する一般的な２パスは、［ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄ］と定義される。ここで、
（ｓ，ｔ）＝（ｉ，ｊ）＋ｏｆｆｓｅｔ［ｅｆｉｒｓｔ］、
（ｍ，ｎ）＝（ｓ，ｔ）＋ｏｆｆｓｅｔ［ｅｓｅｃｏｎｄ］
である。
【００５９】
ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄのあらかじめ計算された２−パスを用いるルックアップテーブルが、各ｅについて用いられる。このテーブルをｄｅｔｏｕｒ［ｅ］と表記する。テーブルｄｅｔｏｕｒ［ｅ］は、ｖｍ，ｎを経由したｖｉ，ｊからｖｓ，ｔへのジャンプが可能な全てのインデックス（ｅｆｉｒｓｔ，ｅｓｅｃｏｎｄ）を含んでいる。
【００６０】
上述のアルゴリズムの複雑さは、当初のＭＣＬの場合のＯ（Ｎ３）とは対照的にＯ（Ｎｒ４）である。これは、本アルゴリズムがサイズの大きな画像をスーパーピクセルにセグメント化するのに適していることを意味する。
【００６１】
さらに、Ｍ２を計算するための上述のアルゴリズムは、１ピクセルあたり１スレッドのパラレルアーキテクチャーに効率的にマッピングすることができる。ｉｎｆｌａｔｉｏｎ演算の計算についても、１ピクセルあたり１スレッドで実装することができる。したがって、本発明の実施形態によれば、上述のように変更したＭＣＬ処理はＧＰＵ上に実装することができる。
【００６２】
上記実装においては、当初のＭＣＬ法と比較して１０倍の高速化が見られた。さらに、当該変更された方法は、当初のＭＣＬ法の場合ではメモリを使い果たすようなサイズの大きな画像をセグメント化することができる。
【００６３】
図７は、上述した方法を用いるスーパーピクセルへの画像分割を示す。当該画像は４１２×４００ピクセルである。この例において、インフレーションパラメーターｐ＝１．４とし、距離しきい値はｄ＝４．５とした。本アルゴリズムは、単精度浮動小数点（３４５ＧＦＬＯＰ）を用いるＮＶＩＤＩＡ Ｑｕａｄｒｏ Ｆｘ ４６００ ＧＰＵ上でＮＶＩＤＩＡ ＣＵＤＡ並列処理アーキテクチャを用いて実装された。本アルゴリズムは、図７に示すようなスーパーピクセルに画像を分割するのに２１．４５秒を要した。図７から分かるように、本アルゴリズムは、形が一様でサイズが均一なスーパーピクセルを生成する。
【００６４】
図８は、スーパーピクセルへの画像分割に上述した方法を用いる場合の画像処理方法のフローチャートである。ステップＳ８０２では、原画像を受け取る。ステップＳ８０４では、上述した方法によって当該画像をスーパーピクセルに分割する。Ｓ８０６では、Ｓ８０４において得られたスーパーピクセル表現を用いて当該画像を処理する。
【００６５】
スーパーピクセルを用いた画像処理は、例えば画像内の物体検出であってもよい。例えば、画像内のスーパーピクセルに基づいて、当該画像から人間の顔が検出され得る。スーパーピクセルを用いた画像処理は、画像分類、画像の３Ｄ再構成、画像の圧縮または符号化であってもよい。例えば、当業者に既知のアルゴリズムを用いて画像を圧縮または暗号化してもよい。
【００６６】
図９は、画像のノイズを低減する方法のフローチャートを示している。ステップＳ９０２では、上述した方法を用いて画像がスーパーピクセルに分割される。ステップＳ９０４では、各スーパーピクセル内のノイズが次のように推定される。各スーパーピクセル内のピクセル輝度を平滑化し、その残余を抽出する。この残余をノイズとする。ステップＳ９０６では、画像に双方向フィルタが適用される。双方向フィルタの平滑化能力は、各ピクセルで推定されたノイズに適合する。上述した方法を用いて画像がスーパーピクセルに分割される場合、均一のスーパーピクセルが生成されることに留意されたい。図９に示されるノイズ低減法において、均一のスーパーピクセルとしていることにより、画像の全体にわたってノイズを一貫して推定することが可能である。
【００６７】
図１０は、画像内の物体を検出する方法のフローチャートを示している。該方法は、一枚の画像から物体を検出したり、映像シーケンスのフレーム群にわたって物体を追跡するのに用いることができる。ステップＳ１００２では、上述した方法を用いて、画像がスーパーピクセルに分割される。ステップＳ１００４では、各スーパーピクセルが、検出する物体の一部に対応する確率が計算される。これは、背景からのスーパーピクセルのセパレーション、形状の手掛かり、シェーディング、物体の部分を表わす可能性のあるスーパーピクセルのグループと背景を表わすグループの間にはっきりした差異があるかどうかといった要素に基づく。ステップＳ１００６では、候補部分から物体表現が選ばれる。このステップＳ１００６における選択は、ステップＳ１００４で計算された確率、さらには、検出物体の相対的位置、相対サイズおよび対称性についての拘束を用いてなされる。
【００６８】
図１０に示された方法を用いて検出される物体は、人物であってもよい。この場合、Ｓ１００４では、物体の部分を人物の手足もしくはその一部、頭部もしくはその一部、または胴体もしくはその一部として確率を計算する。これらの部分の候補が画像内で識別されると、ステップＳ１００６において、当該画像から人物を検出することができる。ここで、相対位置は、頭部と胴体に対する手足の位置である。対称性の要件とは、例えば左腕と右腕の衣服には対称性があることである。
【００６９】
本出願で述べた方法によって生成されるスーパーピクセルは均一であることから、これらは類似ブロックと見なすことができ、アセンブルステップＳ１００６はより簡単になり、様々な形やサイズのスーパーピクセルが用いられる場合よりも正確になる。
【００７０】
図１１は、画像の三次元再構成を計算する方法のフローチャートを示している。ステップＳ１１０２では、上述した方法を用いて、画像がスーパーピクセルに分割される。本方法では、各スーパーピクセルは平面であることを仮定している。ステップＳ１１０４では、各スーパーピクセルの奥行きおよび法線方向が計算される。これは、マルコフ確率場（Ｍａｒｋｏｖ Ｒａｎｄｏｍ Ｆｉｅｌｄ：ＭＲＦ）の最大事後確率割当を探索することにより実行される。これは、シーンのビューに投影する場合、最小のフォトコンシステンシ（ｐｈｏｔｏｃｏｎｓｉｓｔｅｎｃｙ）エラーを与える各スーパーピクセルの奥行きおよび法線方向を検出するとともに、隣接するスーパーピクセルの奥行きおよび法線の滑らかな変更を考慮することを含んでいる。ステップＳ１１０６では、奥行きと法線方向に基づいて三次元再構成が計算される。該三次元再構成が二以上の画像に基づいてもよい。例えば、該三次元再構成が異なる位置から撮影された一連の画像に基づいてもよい。
【００７１】
図１１に示す方法において均一のスーパーピクセルを用いる場合、低い計算コストで正確な結果を得ることができる。非均一性がＭＲＦソルバーの性能を低下させうることが知られている。
【００７２】
いくつかの実施形態を説明したが、これらの実施形態は例示のみを目的としており、発明の範囲を制限することは意図していない。実際には、本明細書で説明した新規の方法およびシステムは他の様々な形で具体化することができ、また発明の要旨から逸脱しない範囲で、本明細書で説明した方法およびシステムの構造における様々な省略、置換、および変更を行ってもよい。添付の特許請求の範囲およびその均等物は、発明の範囲および要旨に含まれうる構造あるいは改良に及ぶことが意図される。
【特許請求の範囲】
【請求項１】
画像を複数のスーパーピクセルに分割する方法であって、各スーパーピクセルは該画像の複数のピクセルを含み、該方法は、
隣接するピクセル間の類似性の測定を用いて、各ウェイトが該画像のピクセル対に関連付けられる初期ウェイトセットを計算すること；
該画像における閾値距離未満で分けられたピクセル対について、初期ウェイトセットから合成ウェイトセットを計算すること、該合成ウェイトセットの計算は、
第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算すること；
べき乗係数への各ウェイトの値を計算すること；および
ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することを含み；
収束ウェイトセットへの収束をチェックするために該初期ウェイトセットと該合成ウェイトセットを比較すること；および
該収束ウェイトセットを用いて、ピクセルをスーパーピクセルにグループ化すること
を含む方法。
【請求項２】
第１ピクセルおよび第２ピクセルのウェイトを計算することは、第１ルックアップテーブルを読み出すことを含み、該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示す請求項１の方法。
【請求項３】
第１ピクセルおよび第２ピクセルのウェイトを計算することは、第２ルックアップテーブルを読み出すことをさらに含み、該第２ルックアップテーブルは、第３ピクセルのセットを経由した該第１ピクセルから該第２ピクセルへの該画像の変換セットを示す請求項２の方法。
【請求項４】
前記ピクセル間の類似性の測定は、ピクセル間の強度の差から計算される請求項１の方法。
【請求項５】
該画像の各ピクセルに関連付けられたウェイトセットを記憶するためのメモリを割り当てることをさらに含み、該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる請求項１の方法。
【請求項６】
各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶すること、および、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える請求項５の方法。
【請求項７】
請求項１の方法を用いて、画像をスーパーピクセルに分割すること；および
該スーパーピクセルを用いて、該画像を処理すること
を含む、画像を処理する方法。
【請求項８】
該スーパーピクセルを用いて該画像を処理することは、該画像内の特徴を認識することを含む請求項７の方法。
【請求項９】
該スーパーピクセルを用いて該画像を処理することは、該画像を符号化することを含む請求項７の方法。
【請求項１０】
該スーパーピクセルを用いて該画像を処理することは、該画像の三次元再構成を計算することを含む請求項７の方法。
【請求項１１】
該スーパーピクセルを用いて該画像を処理することは、該画像のノイズを低減することを含む請求項７の方法。
【請求項１２】
計算機によって実行された時に、該計算機に請求項１の方法を実行させる計算機実行可能命令を持つ計算機可読媒体。
【請求項１３】
画像を複数のスーパーピクセルに分割する画像処理システムであって、各スーパーピクセルは該画像の複数のピクセルを含み、該システムは、
隣接するピクセル間の類似性の測定を用いて、各ウェイトが該画像のピクセル対に関連付けられる初期ウェイトセットを計算し；
第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算し、べき乗係数への各ウェイトの値を計算し、ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することにより、該画像における閾値距離未満で分けられたピクセル対について、該初期ウェイトセットから合成ウェイトセットを計算し；
収束ウェイトセットへの収束をチェックするために該初期ウェイトセットと該合成ウェイトセットを比較し；および
該収束ウェイトセットを用いて、ピクセルをスーパーピクセルにグループ化する
プロセッサを具備するシステム。
【請求項１４】
第１ルックアップテーブルのストレージをさらに具備し、該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示し、前記プロセッサは、該第１ルックアップテーブルを読み出すことにより、第１ピクセルおよび第２ピクセルのウェイトを計算する、請求項１３のシステム。
【請求項１５】
第２ルックアップテーブルのストレージをさらに具備し、該第２ルックアップテーブルは、第３ピクセルのセットを経由した該第１ピクセルから該第２ピクセルへの該画像の変換セットを示し、前記プロセッサは、該第２ルックアップテーブルを読み出すことにより、第１ピクセルおよび第２ピクセルのウェイトを計算する、請求項１４のシステム。
【請求項１６】
メモリをさらに具備し、該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる、該画像の各ピクセルに関連付けられたウェイトセットを記憶するため割り当てられる請求項１３のシステム。
【請求項１７】
前記プロセッサは、各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶し、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える、請求項１６のシステム。
【請求項１８】
前記プロセッサは、該スーパーピクセルを用いて、該画像内のノイズを低減する請求項１３のシステム。
【請求項１９】
前記プロセッサは、該スーパーピクセルを用いて、該画像内の特徴を認識する請求項１３のシステム。
【請求項２０】
前記プロセッサは、該スーパーピクセルを用いて、該画像の三次元表現を計算する請求項１３のシステム。
【請求項１】
画像を複数のスーパーピクセルに分割する方法であって、各スーパーピクセルは該画像の複数のピクセルを含み、該方法は、
隣接するピクセル間の類似性の測定を用いて、各ウェイトが該画像のピクセル対に関連付けられる初期ウェイトセットを計算すること；
該画像における閾値距離未満で分けられたピクセル対について、初期ウェイトセットから合成ウェイトセットを計算すること、該合成ウェイトセットの計算は、
第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算すること；
べき乗係数への各ウェイトの値を計算すること；および
ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することを含み；
収束ウェイトセットへの収束をチェックするために該初期ウェイトセットと該合成ウェイトセットを比較すること；および
該収束ウェイトセットを用いて、ピクセルをスーパーピクセルにグループ化すること
を含む方法。
【請求項２】
第１ピクセルおよび第２ピクセルのウェイトを計算することは、第１ルックアップテーブルを読み出すことを含み、該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示す請求項１の方法。
【請求項３】
第１ピクセルおよび第２ピクセルのウェイトを計算することは、第２ルックアップテーブルを読み出すことをさらに含み、該第２ルックアップテーブルは、第３ピクセルのセットを経由した該第１ピクセルから該第２ピクセルへの該画像の変換セットを示す請求項２の方法。
【請求項４】
前記ピクセル間の類似性の測定は、ピクセル間の強度の差から計算される請求項１の方法。
【請求項５】
該画像の各ピクセルに関連付けられたウェイトセットを記憶するためのメモリを割り当てることをさらに含み、該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる請求項１の方法。
【請求項６】
各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶すること、および、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える請求項５の方法。
【請求項７】
請求項１の方法を用いて、画像をスーパーピクセルに分割すること；および
該スーパーピクセルを用いて、該画像を処理すること
を含む、画像を処理する方法。
【請求項８】
該スーパーピクセルを用いて該画像を処理することは、該画像内の特徴を認識することを含む請求項７の方法。
【請求項９】
該スーパーピクセルを用いて該画像を処理することは、該画像を符号化することを含む請求項７の方法。
【請求項１０】
該スーパーピクセルを用いて該画像を処理することは、該画像の三次元再構成を計算することを含む請求項７の方法。
【請求項１１】
該スーパーピクセルを用いて該画像を処理することは、該画像のノイズを低減することを含む請求項７の方法。
【請求項１２】
計算機によって実行された時に、該計算機に請求項１の方法を実行させる計算機実行可能命令を持つ計算機可読媒体。
【請求項１３】
画像を複数のスーパーピクセルに分割する画像処理システムであって、各スーパーピクセルは該画像の複数のピクセルを含み、該システムは、
隣接するピクセル間の類似性の測定を用いて、各ウェイトが該画像のピクセル対に関連付けられる初期ウェイトセットを計算し；
第１ピクセルおよび第２ピクセルのウェイトを該第１ピクセルと第３ピクセルの間の初期ウェイトと該第３ピクセルと該第２ピクセルの間の初期ウェイトの積の、第３ピクセルにわたる和として計算し、べき乗係数への各ウェイトの値を計算し、ピクセルのすべてのウェイトセットの合計が１になるように、該ウェイトセットを該べき乗係数に正規化することにより、該画像における閾値距離未満で分けられたピクセル対について、該初期ウェイトセットから合成ウェイトセットを計算し；
収束ウェイトセットへの収束をチェックするために該初期ウェイトセットと該合成ウェイトセットを比較し；および
該収束ウェイトセットを用いて、ピクセルをスーパーピクセルにグループ化する
プロセッサを具備するシステム。
【請求項１４】
第１ルックアップテーブルのストレージをさらに具備し、該第１ルックアップテーブルは、第１ピクセルから該第１ピクセルの閾値距離内のピクセルセットへの該画像の変換セットを示し、前記プロセッサは、該第１ルックアップテーブルを読み出すことにより、第１ピクセルおよび第２ピクセルのウェイトを計算する、請求項１３のシステム。
【請求項１５】
第２ルックアップテーブルのストレージをさらに具備し、該第２ルックアップテーブルは、第３ピクセルのセットを経由した該第１ピクセルから該第２ピクセルへの該画像の変換セットを示し、前記プロセッサは、該第２ルックアップテーブルを読み出すことにより、第１ピクセルおよび第２ピクセルのウェイトを計算する、請求項１４のシステム。
【請求項１６】
メモリをさらに具備し、該メモリは、所与のピクセルに対して閾値距離を有するピクセルの数によって割り当てられる、該画像の各ピクセルに関連付けられたウェイトセットを記憶するため割り当てられる請求項１３のシステム。
【請求項１７】
前記プロセッサは、各ピクセルに関連付けられたウェイトセットとして該メモリに該初期ウェイトセットを記憶し、該合成ウェイトセットの計算の後に該合成ウェイトセットで該初期ウェイトセットを置き換える、請求項１６のシステム。
【請求項１８】
前記プロセッサは、該スーパーピクセルを用いて、該画像内のノイズを低減する請求項１３のシステム。
【請求項１９】
前記プロセッサは、該スーパーピクセルを用いて、該画像内の特徴を認識する請求項１３のシステム。
【請求項２０】
前記プロセッサは、該スーパーピクセルを用いて、該画像の三次元表現を計算する請求項１３のシステム。
【図１】
【図２】
【図３ａ】
【図３ｂ】
【図３ｃ】
【図３ｄ】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３ａ】
【図３ｂ】
【図３ｃ】
【図３ｄ】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−２０３９１０（Ｐ２０１２−２０３９１０Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−６５１０６（Ｐ２０１２−６５１０６）
【出願日】平成２４年３月２２日（２０１２．３．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１２−６５１０６（Ｐ２０１２−６５１０６）
【出願日】平成２４年３月２２日（２０１２．３．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]