(57)【要約】【課題】この発明は、例えばステレオカメラによる高さデータのような、多峰関数のセグメンテーションに適した高速なクラスタリングアルゴリズムを提案する。【解決手段】本発明の画素ベース勾配クラスタリングによる多峰関数セグメンテーション方法は、勾配クラスタの定義を取り入れた高速なクラスタリングアルゴリズムを用いるものであり、多峰曲面に関して極大点を中心とした領域に分割し、勾配に沿って下降する経路を探索してクラスタ領域を決定する。前記勾配クラスタを、位相的な近傍関係を利用して離散空間における経路探索を行う。【選択図】図１
2007272466.tif 000002
【特許請求の範囲】
【請求項１】
勾配クラスタの定義を取り入れた高速なクラスタリングアルゴリズムを用いることを特
徴とする画素ベース勾配クラスタリングによる多峰関数セグメンテーション方法。
【請求項２】
前記画素ベースの多峰曲面に関して極大点を中心とした領域に分割し、勾配に沿って下
降する経路を探索してクラスタ領域を決定することを特徴とする前記請求項１記載の画素
ベース勾配クラスタリングによる多峰関数セグメンテーション方法。
【請求項３】
前記勾配クラスタを、位相的な近傍関係を利用して離散空間における経路探索を行うこと
を特徴とする前記請求項１または２記載の画素ベース勾配クラスタリングによる多峰関数
セグメンテーション方法。
【請求項４】
前記経路を選択するための基準は着目データとその近傍データとの差分であり、それに
より局所的な勾配を近似することを特徴とする前記請求項２記載の画素ベース勾配クラス
タリングによる多峰関数セグメンテーション方法。
【請求項５】
前記画素ベースの入力データがステレオビジョンによる視差データであり、ステレオ視
差データから人物を勾配クラスタとして分離することを特徴とする前記請求項１〜４の内
、いずれか１項記載の画素ベース勾配クラスタリングによる多峰関数セグメンテーション
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像解析におけるセグメンテーションまたはクラスタリング、特にステレオ
カメラによる高さデータのような、多峰関数の画素データのセグメンテーションを行うた
めの勾配クラスタリングアルゴリズムに関する。
【背景技術】
【０００２】
画像解析におけるセグメンテーションまたはクラスタリング問題は、それら自身が重要
な問題となることもあるし、後処理の認識問題にとって重要な手がかりとなることもある
。画像処理におけるクラスタ解析の問題は、これまでにも多くの研究者によって研究がな
されてきた。 
【０００３】
さまざまなクラスタリングアルゴリズムが、さまざまな問題に対して応用されてきた。
主なものは階層的手法（非特許文献１，２）、非階層的手法（非特許文献３〜５）であり
、これらの手法はサンプルデータ群に対して統計的な基準に基づいたクラスタを形成する
ものである。他にも非統計的に分布するデータに対するクラスタリング手法も提案されて
きている（非特許文献６，７）。 
【０００４】
本発明者は、ステレオカメラを利用して、人込みから人物の頭部を見つけ出す実時間ア
ルゴリズムを提案した（特開２００４−５８７３７号公報、非特許文献８）。これを多峰
関数の頂点を見つけ出す課題として考えることで、問題記述の簡略化を図った。この方法
は人物の頭部を追跡するには有効な考え方であったが、人物領域のセグメンテーションに
までは言及していない。
【０００５】
上記従来例を改良しさらに発展させれば、ステレオビジョンにおけるセグメンテーショ
ン問題は、多峰曲面に関して極大点を中心とした領域に分割するために、勾配クラスタの
定義を取り入れることができる。このような問題ではデータが2 次元行列で与えられるこ
とを考えれば、その位相的な近傍関係を積極的に使うべきである。実時間処理を行うため
には、計算時間も重要な要素であり、このための工夫も必要である。
【０００６】
勾配クラスタは、データの確率密度関数の勾配から定義される（非特許文献９，１０）
。勾配クラスタの定義をより数学的に展開し、クラスタ中心に向かうアトラクタを探索す
るためのヒューリスティックなアルゴリズムが提案されている（非特許文献１１）。
【特許文献１】特開２００４−５８７３７号公報
【非特許文献１】Johnson, P. O., “Hierarchical Clustering Schemes”, Psychometrica, Vol.32, No.3, pp.241-254, 1967.
【非特許文献２】Ward, Jr., J. H., “Hierarchical Grouping to Optimize an Objective Function”, Journal of Statist. and As-soc. Vol.58, No.301, pp.236-244, 1963.
【非特許文献３】Lloyd, S. P., “Least squares quantization in pcm”, Technical report, Bell Laboratories Technical Note, 1957, Eventually published in IEEE Transactions on Information Theory, Vol.28, No.2, pp.129-136, 1982.
【非特許文献４】Ball, G. H. and Hall, D. J., “Some fundamental con-cepts and synthesis procedures for pattern recogni-tion preprocessors”, In Proceedings of the Interna-tional Conference on Microwaves, Circuit Theory and Information Theory, Tokyo, Japan, pp.113-114, 1964.
【非特許文献５】Bezdek, J. C., “Pattern Recognition with Fuzzy Ob-jective Function Algorithms”, Plenum Press, New York, 1981.
【非特許文献６】Lipson, H. and Siegelmann, H. T., “Clustering Irregular  Shapes using High-Order Neurons”, Neural Computation, Vol.12, pp.2231-2352, 2000.
【非特許文献７】Ben-Hur, A., Horn, D., Siegelmann, H. T. and Vapnik, V., “Support Vector Clustering”, Journal of Ma- chine Learning Research, Vol.2, pp.125-137, 2001.
【非特許文献８】依田育士, 細谷大輔, 坂上勝彦, “ユビキタスステレオビジョンによる駅ホーム端安全管理”, 電気学会論文誌C, Vol.124, No.3, pp.805-811, 2004.
【非特許文献９】Schnell, P., “Eine Methode zur Au・ndung von Gruppen”, Biometrische Zeitschrift, Vol.6, pp.47-48, 1964.
【非特許文献１０】Hill, L. R., Silvestri, L. G., Ihm, P., Farchi, G. and Lanciani, P., “Automatic Classification of Staphylococci by Principal-Component Analysis and a Gradient Method”, Journal of Bacteriology, Vol.89, No.5, pp.1393-1401, 1965.
【非特許文献１１】Kowalewski, F., “A Gradient Procedure for Deter mining Clusters of Relatively High Point Density”, Pattern Recognition, Vol.28, No.12, pp.1973-1984, 1995.
【非特許文献１２】高木幹雄, 下田陽久, “画像解析ハンドブック”, 東京大学出版会, 1991.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
この発明では、例えばステレオカメラによる高さデータのような、多峰関数のセグメン
テーションに適した高速なクラスタリングアルゴリズムを提案する。
すなわち、本発明は、ステレオカメラを利用して人込みから人物の頭部を見つけ出す（
多峰関数の頂点を見つけ出す）実時間アルゴリズムを改良し、人物領域のセグメンテーシ
ョンにまで言及して、より精度の高い人物のパターン認識及びそれに基づくトラッキング
の精度を高める方法を提案することを目的とする。
【課題を解決するための手段】
【０００８】
この発明では、画素ベースの多峰関数をセグメンテーションするための勾配クラスタリ
ングアルゴリズムを提案する。ステレオビジョンにおけるセグメンテーション問題は、多
峰曲面に関して極大点を中心とした領域に分割するために、勾配クラスタの定義を取り入
れることにより、上記課題が解決される。
【０００９】
提案アルゴリズムはパラメータに依存せず、勾配クラスタの近似解を高速に算出する手
法である。勾配に沿って下降する経路を探索することでクラスタ領域を決定し、ほぼデー
タ数に比例する計算時間で終了する。実験として提案手法と既存のヒューリスティックな
手法とを比較した。その結果から、提案手法は多峰関数の頂上付近では十分な精度を持ち
、その計算時間の線形性から実時間処理に向いているといえる。
【００１０】
実問題への応用例として、地形図のクラスタリングとステレオビジョンからのオブジェ
クト切り出しを行った。数値地図の山脈から各々の山が、ステレオ視差データからは人物
が、勾配クラスタとして分離された。
【００１１】
提案手法は、多峰関数の頂点から稜線に向かって勾配を下る経路を探索する。より高速
にクラスタを決定するため、連続空間におけるアトラクタ探索問題として定義された勾配
クラスタを、位相的な近傍関係を利用して離散空間における経路探索問題に置き換えた。
そして経路探索後のグルーピング処理を省くために、凝集的手法から分割的手法へと書き
換えた。
【００１２】
経路を選択するための基準は着目データとその近傍データとの差分であり、それにより
局所的な勾配を近似する。ステレオビジョン画像のような２次元配列データの場合には、
チェス盤距離（非特許文献１２参照）を使うことによってこの比較手順をさらに簡略化す
ることができる。
【発明の効果】
【００１３】
本発明の手法によって、人物領域のセグメンテーション方法として直観的でプログラミ
ングしやすい形式になる効果がある。また、それぞれのデータは近傍データとの比較だけ
を必要とするため、計算時間はほぼデータ数に比例するだけで、従来より高速に処理でき
る効果がある。 
【発明を実施するための最良の形態】
【００１４】
提案手法では、最初のクラスタはすべてのデータの中で最大値を持つ点からその領域を
広げていく。勾配を下る経路はその頂点から探索されていく。 次に２ つ目のクラスタは
、1 番目のクラスタ以外のデータの中で最大値を持つ点から領域を広げていく。そして残
りのクラスタも同様にして求めていく。 これらの処理は再帰的に求められる。Xr (t) を
時間t における残りデータの集合であるとする。Xr (t) はすべてのデータＸ で初期化さ
れる。
【００１５】
【数１】
2007272466.tif 000003
それぞれのクラスタは順次求めていく。
【００１６】
【数２】
2007272466.tif 000004
【００１７】
【数３】
2007272466.tif 000005
【００１８】
【数４】
2007272466.tif 000006
ここで
【００１９】
【数５】
2007272466.tif 000007
はクラスタ
【００２０】
【数６】
2007272466.tif 000008
の時刻t における状態である。クラスタ
【００２１】
【数７】
2007272466.tif 000009
のためのクラスタリング処理は時刻t0 （ｌ）から開始される。 
【００２２】
すでに決定されているクラスタ
【００２３】
【数８】
2007272466.tif 000010
が時間Tl-1 で求まっているとすると、t0（ｌ） = Tl-1 + 1 となる。 初期値はt0(l) ＝
０である。 時刻t において，
【００２４】
【数９】
2007272466.tif 000011
と Xr (t) は、
【００２５】
【数１０】
2007272466.tif 000012
に対して以下のような規則に従って更新される。
【００２６】
【数１１】
2007272466.tif 000013
もしどのようなxj もクラスタ
【００２７】
【数１２】
2007272466.tif 000014
に追加されなかった場合、すなわち
【００２８】
【数１３】
2007272466.tif 000015
となったとき、次のクラスタ
【００２９】
【数１４】
2007272466.tif 000016
の処理へと進める。
【００３０】
データ集合が画像データのように等間隔サンプリングによる２次元データであれば、 
点x の近傍N(x) は単純に８ 近傍として定義できる。この場合、データ点間の距離をチェ
ス盤距離（文献１２）で近似することにより、式(５) はさらに単純な形で近似すること
ができる。
【００３１】
【数１５】
2007272466.tif 000017
計算コストを軽減するためには、式(５)の項
【００３２】
【数１６】
2007272466.tif 000018
あるいは式(６) の項
【００３３】
【数１７】
2007272466.tif 000019
は、クラスタリング処理の前にあらかじめすべてのデータに関して計算し、経路探索のと
きに参照できるようストアしておくべきである。図１と図２に、式(６)で定義された提案
アルゴリズムによるクラスタリング結果とクラスタリングの途中経過の例を示す。
【００３４】
（従来手法との比較）
さまざまなクラスタ数によるテスト用データを使い、クラスタリング精度と計算時間に
関して提案手法と既存のヒューリスティックな手法を比較する。
【００３５】
・精度と計算時間
最初に、提案手法のクラスタリング精度と計算効率に関して図３に示すデータ集合を使
って観測した。これらのデータはそれぞれの要素が高さの値を持つ２次元配列で、ランダ
ムなガウス関数の線形和によって作成された。実験用に頂点数２, ８, １６の３種類のパ
ターンを用意し，これらのデータをさまざまな種類の解像度に直したものを使って実験を
行った。実験時に設定された解像度は、200×200 = 40,000, 400×400 = 160,000, 600×
600 = 360,000, 800×800 = 640,000, 1,000×1,000 = 1,000,000, 1,200× 1,200 = 1,4
40,000 の８種類である。
【００３６】
以降、提案手法のうち式(５) で定義した手法を“method 1”，式(６) で定義した手法
を“method 2” と書くことにする。
比較手法として、Kowalewski によって提唱されたヒューリスティックな勾配クラスタ
リングアルゴリズムであるcenter of mass 手法（従来手法）を用いた。これらのアルゴ
リズムはMATLAB におけるＣ言語mex 関数で実装され、Pentium （登録商標）4 (3.4 [GHz
]) のＣＰＵ を搭載したＰＣ によって計算が行われた。
【００３７】
図４はクラスタリング結果を示している。頂点数２，８，１６のデータ集合に対するク
ラスタ境界が、上から下へ順番に描かれている。クラスタリング結果は左から順にCenter
of mass 手法、method 1 、method 2 による出力が描かれている。
【００３８】
図５は、提案手法の計算時間を示している。総計算時間はほぼデータ数に比例してい
る。図６は、１６頂点データに対する、提案手法とcenter of mass 手法の計算時間を比
較したものを示している。center of mass 手法では、更新係数δの値を３種類設定して
実験している。図より、明らかに本発明の手法の方が高速であることが分かる。
【００３９】
既存の勾配クラスタリングアルゴリズムは、極大値に収束するアトラクタを探索する凝
集的手法として定義されている。これらの手法では、算出されたアトラクタをグルーピン
グするために、後処理として別のクラスタリング手法を用いなければならない。従来はグ
ルーピングのために単連結法を用いることを提案しているが、提案手法では、クラスタ中
心はクラスタ領域を広げる前に決定されている。クラスタラベルは各データに対して、ク
ラスタ領域を拡張している最中に割り振ることができる。そのため，グルーピングのため
の後処理を必要とせず、コーディング時の複雑さが取り除かれている。
【００４０】
提案手法は位相近傍を利用することで経路探索範囲を離散空間に限定しているため、ヒ
ューリスティックな手法と比較して大幅に計算時間が速い。実際に図５を見ると、計算時
間がほぼデータ数に比例することを示している。この計算時間の線形性は、提案手法が実
時間処理に適していることを示している。図６は提案手法とcenter of mass 手法の比較
結果を示している。比較手法はヒューリスティックな手法であるため，提案手法が比較手
法よりも大幅に速いことは自明である。比較手法はすべてのデータに対してアトラクタの
すべての軌跡を収束するまで計算しなければならず，また収束時間は更新係数の設定に大
きく依存する。更新係数が大きいほど収束時間は速くなるが、その場合にはアトラクタ探
索処理が収束しない場合も発生する。従って、比較手法では更新係数の最適な値を決定す
ることが非常に重要となる。またcenter of mass 手法は、グルーピングのための単連結
法における閾値，収束条件，データの正規化係数など、さまざまなパラメータの設定を必
要とする。これに対して提案手法はコントロールパラメータを持たないためこのような設
定は不要であり、実問題への応用に対して扱いやすいものとなっている。
【００４１】
図４では、すべての手法で類似した領域が得られていることがわかる。細かく見ると、
提案手法では勾配のほとんどない領域でクラスタ境界の劣化が観測される。近似手法であ
るためクラスタ境界におけるある程度の誤差はあるが、実際には扱う問題によって適した
アルゴリズムを利用すべきである。計算時間が非常に重要とされる問題で、クラスタ境界
付近の細かい部分が後処理に対してさほど大きな影響を与えないのであれば、提案手法は
非常に利用価値の高い手段である。
【００４２】
・実問題への応用
次に、提案手法を実問題に応用した例を挙げる。
最初に、提案手法を使って数値地図を地形に従って山の領域に分割した。次いで、ステ
レオビジョンからのオブジェクト抽出の例を示す。 
【００４３】
ここではmethod 1 よりも単純で計算時間も速いという理由からmethod 2 を利用してい
る。このアルゴリズムは２次元配列で定義されたデータ集合に対して特化されており、そ
れを使ってこの節では2 種類の典型的な問題を解いている。
【００４４】
地形によるセグメンテーション問題では，数値地図に対して提案手法を用いることで、
地形に関するセグメンテーションを行う。ステレオビジョンにおけるオブジェクト抽出で
は、提案手法によるステレオビジョンからのオブジェクト抽出の例を述べる。
【００４５】
・地形によるセグメンテーション問題
数値地図(Digital elevation model, DEM) は、地形に関する標高を２次元配列で表し
たデータである。ここでは数値地図を使ったいくつかのクラスタリング結果の例を示す。
【００４６】
富士山麓に関する例を図７に示す。この数値地図は40 × 35 メッシュから成り、それ
ぞれのメッシュは1, 000[m]× 1, 000[m] のサイズを表し、標高を値として持つ。数値地
図におけるそれぞれの頂点を中心とした領域が、別々の山として分割されている。クラス
タリング結果の中に、富士山，越前岳，愛鷹山，篭坂峠，金時山，三国山などが見える。
【００４７】
・ステレオビジョンにおけるオブジェクト抽出
ここでは、ステレオビジョンにおけるオブジェクト抽出の例を示す。ステレオカメラは
視差値を計算することで物体の幾何形状情報を得ることができる。図８は、横浜駅プラッ
トフォームの天井に設置されたカメラから得られたステレオビジョンデータに対する、ク
ラスタリング結果の例を示している。これらの視差データは33× 54[pixel] の配列で与
えられている。図８において、(a) はテクスチャ画像、(b) は視差データの3 次元プロッ
ト、(c) はクラスタリング結果、(d) は抽出されたオブジェクトである。これらのデータ
は前記と同じ実験条件で行われ、計測された計算時間は1.215[ms] であった。
【００４８】
提案手法を応用した実問題の例として、地形によるセグメンテーションとステレオビジ
ョンデータからのオブジェクト抽出を行ったが、これらの問題に対するクラスタリング結
果は、提案手法が凸形状の物体を事前知識なしで分割する十分な能力を持っていることを
示している。実世界では図８のような複雑なシーンが度々発生する。このようなシーンで
は，それぞれの人物を分離するための閾値を決定することは困難である。それぞれの人物
が頭部で最も大きな視差値を持つと仮定すると、提案クラスタリング手法はこの類のオブ
ジェクト抽出問題に適した手法であるといえる。
【００４９】
図８から、提案アルゴリズムを使うことでステレオビジョンデータから人物を抜き出せ
ていることがわかる。計算コストの面から考えても1.215[ms]という計測値が得られてお
り、提案アルゴリズムの効率が改めて実証されている。
【００５０】
以上のように、本発明は、画素ベースの勾配クラスタリングにおける高速な近似解法を
提案した。この提案アルゴリズムは勾配を下る経路を探索することでクラスタ領域を拡張
していく手法で、後処理としてのグルーピング処理を必要としない分割的手法である。提
案手法は多峰関数のセグメンテーションに適したアルゴリズムで、離散空間における経路
探索問題として問題を表現することにより高速化が図られており、計算コストはデータ数
に比例する。 
【００５１】
実験では提案手法の精度と計算コストを、center of mass 手法と比較した。実験結果
から、提案手法はその計算時間の線形性から実時間処理に向いているといえる。また、提
案手法はコントロールパラメータを持たないため、パラメータ設定の必要がなく、応用を
考えたときに扱いやすいものである。
【００５２】
また、提案手法を実問題に応用した例も示した。地形によるセグメンテーション問題で
は、数値地図から山の領域を抽出する例を示した。ステレオビジョンにおけるオブジェク
ト抽出問題では、それぞれの凸形状物体が視差データから分割された。これらの問題は多
峰関数のセグメンテーション問題と仮定することができ、提案された勾配クラスタリング
アルゴリズムはこのような問題に適した手法であるといえる。
【産業上の利用可能性】
【００５３】
本発明は、例えば、駅のホームの監視システムに応用され、ホーム上の人の動きを追跡
する場合、従来のステレオカメラを利用して人込みから人物の頭部を見つけ出す（多峰関
数の頂点を見つけ出す）実時間アルゴリズムを改良し、人物領域のセグメンテーションに
まで言及して、より精度の高い人物のパターン認識及びそれに基づくトラッキングの精度
を高めることができる。
【００５４】
本発明の手法は、他の手法に比較し、高速処理ができ、実時間処理が可能になるので、
その産業上の利用性は高い。
【図面の簡単な説明】
【００５５】
【図１】式(６) で定義された提案アルゴリズムによるクラスタリング結果の例を示す図である。
【図２】式(６) で定義された提案アルゴリズムによるクラスタリング途中経過の例を示す図である。
【図３】提案手法のクラスタリング精度と計算効率に関して観測したデータ集合の例を示す図である。
【図４】図３のデータ集合のクラスタリング結果を示す図である。
【図５】提案手法の計算時間を示す図である。
【図６】１６頂点データに対する、提案手法とcenter of mass 手法の計算時間を比較したものを示す図である。
【図７】富士山麓に関する例を示す図である。
【図８】横浜駅プラットフォームの天井に設置されたカメラから得られたステレオビジョンデータに対する、クラスタリング結果の例を示す図である。
【符号の説明】
【００５６】
１      画素データ
２      クラスタリング・データ
【図１】
2007272466.tif 000020
【図２】
2007272466.tif 000021
【図３】
2007272466.tif 000022
【図４】
2007272466.tif 000023
【図５】
2007272466.tif 000024
【図６】
2007272466.tif 000025
【図７】
2007272466.tif 000026
【図８】
2007272466.tif 000027