図面 (/)

技術 クラスタリング方法及びデータ処理装置

出願人 キヤノン株式会社
発明者 中嶋大介
出願日 2014年8月7日 (6年3ヶ月経過) 出願番号 2014-161895
公開日 2016年3月22日 (4年8ヶ月経過) 公開番号 2016-038751
状態 特許登録済
技術分野 イメージ分析 検索装置
主要キーワード 代表候補 部分距離 総合距離 データループ クラスタリング処理結果 距離空間 重みセット 距離計算結果
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年3月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (8)

課題

入力データに対して適切なクラスタリングを行えるようにする。

解決手段

複数の入力データの各々が属するクラスを決定するクラスタリング方法において、入力データと複数の代表データの各々との距離を計算し、入力データに基づいて距離計算方法を選択し、選択された距離計算方法を用いて計算工程で算出された距離のうち最短の距離が得られた代表データに入力データを帰属させる。

概要

背景

近年、画像を色やテクスチャ座標など属性が類似した複数の領域に分割する技術が注目されている。分割された領域はスーパーピクセルと呼ばれ、分割領域単位符号化処理画像処理、及び画像認識処理を実行できるため、様々な画像処理装置における応用が可能である。

従来、画像の領域分割に関して様々な手法が提案されている。特に、画素クラスタリングすることによって画像を領域に分ける手法が多く提案されている。この手法は、色やテクスチャ、座標を要素にもつデータを要素間の距離に基づいてクラスタリングする。クラスタリングでは、各クラスタ代表データを求め、入力データを最近傍の代表データに割り当てる。このとき、入力データと複数の代表候補データの距離を計算して最近傍代表データを探索する。クラスタリングを用いた領域分割の先行技術として特許文献1、非特許文献1、2などが挙げられる。

非特許文献1では、SLIC(Simple Linear Iterative Clustering)と呼ばれるクラスタリング手法を用いて領域分割する方法が提案されている。SLICは、K−meansクラスタリングの最近傍代表データの探索範囲を画像中の局所領域に限定したものである。通常、入力データと各クラスの代表データとの距離計算にはユークリッド距離(L2距離)を用いるが、ユークリッド距離以外を用いる手法も提案されている。例えば、特許文献1では、データの各要素の重み付き距離を用いる手法が提案されている。また、非特許文献2では、L1距離とL∞距離の線形和を距離とする手法が提案されている。

概要

入力データに対して適切なクラスタリングを行えるようにする。複数の入力データの各々が属するクラスを決定するクラスタリング方法において、入力データと複数の代表データの各々との距離を計算し、入力データに基づいて距離計算方法を選択し、選択された距離計算方法を用いて計算工程で算出された距離のうち最短の距離が得られた代表データに入力データを帰属させる。

目的

本発明は上述した課題に鑑みてなされたものであり、入力データに応じて適切なクラスタリングを行えるようにすることを目的とする

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の入力データの各々が属するクラスを決定するクラスタリング方法であって、入力データと複数の代表データの各々との距離を計算する計算工程と、前記入力データに基づいて距離計算方法を選択する選択工程と、前記選択工程で選択された距離計算方法を用いて前記計算工程で算出された距離のうち最短の距離が得られた代表データに前記入力データを帰属させる帰属工程と、を有することを特徴とするクラスタリング方法。

請求項2

前記計算工程では、前記入力データと複数の代表データの各々との距離を複数の距離計算方法のそれぞれを用いて計算し、前記選択工程では、前記複数の距離計算方法のそれぞれを用いて算出された前記入力データと複数の代表データの各々との距離に基づいて、前記複数の距離計算方法のうちの1つを選択することを特徴とする請求項1に記載のクラスタリング方法。

請求項3

前記計算工程では、前記入力データと代表データとの距離を、複数の部分距離統合することにより算出し、前記複数の距離計算方法は、前記複数の部分距離の少なくとも一つに関する計算方法がそれぞれ異なっていることを特徴とする請求項1に記載のクラスタリング方法。

請求項4

前記入力データは座標と特徴量から構成され、前記計算工程では、前記入力データと代表データとの距離を、前記座標の距離と前記特徴量の距離とを統合して前記距離を算出し、前記複数の距離計算方法は、前記特徴量の距離の計算方法がそれぞれ異なり、前記座標の距離の計算方法は共通であることを特徴とする請求項3に記載のクラスタリング方法。

請求項5

前記計算工程では、前記複数の距離計算方法のそれぞれを用いて得られた距離を正規化し、前記選択工程では、正規化された距離に基づいて距離計算方法を選択することを特徴とする請求項2乃至4いずれか1項に記載のクラスタリング方法。

請求項6

前記選択工程では、それぞれの距離計算方法で算出された前記入力データと複数の代表データの各々との距離の分布広がりに基づいて、距離計算方法を選択することを特徴とする請求項2乃至5のいずれか1項に記載のクラスタリング方法。

請求項7

前記選択工程では、前記分布の広がりとして、前記複数の代表データについて算出された複数の距離の最大値最小値の差を用いることを特徴とする請求項6に記載のクラスタリング方法。

請求項8

前記選択工程では、前記分布の広がりとして、前記複数の代表データについて算出された複数の距離の分散を用いることを特徴とする請求項6に記載のクラスタリング方法。

請求項9

所定の領域内の入力データを解析する解析工程をさらに有し、前記選択工程では、前記解析工程による解析の結果に基づいて使用する距離計算方法を選択し、前記計算工程では、前記選択工程で選択された距離計算方法を用いて入力データと複数の代表データの各々との距離を計算することを特徴とする請求項1に記載のクラスタリング方法。

請求項10

前記所定の領域とは、前記入力データを含む所定の大きさの領域であり、前記解析工程では、前記所定の領域内のすべての入力データについて解析を行うことを特徴とする請求項9に記載のクラスタリング方法。

請求項11

前記代表データは、前記所定の領域内から選択された入力データであり、前記解析工程では、前記代表データについて解析を行うことを特徴とする請求項9に記載のクラスタリング方法。

請求項12

前記解析工程では、前記所定の領域内の入力データの統計量を算出することを特徴とする請求項9乃至11いずれか1項に記載のクラスタリング方法。

請求項13

前記データは複数の成分から構成されており、前記統計量とは、前記領域内のデータ間での各成分の差分の違いであることを特徴とする請求項12に記載のクラスタリング方法。

請求項14

前記データは複数の成分から構成されており、前記統計量とは、前記領域内のデータの各成分の分散の違いであることを特徴とする請求項12に記載のクラスタリング方法。

請求項15

コンピュータに請求項1乃至14のいずれか1項に記載のクラスタリング方法の各工程を実行させるためのプログラム

請求項16

複数の入力データの各々が属するクラスを決定するデータ処理装置であって、入力データと複数の代表データの各々との距離を計算する計算手段と、前記入力データに基づいて距離計算方法を選択する選択手段と、前記選択手段により選択された距離計算方法を用いて前記計算手段により算出された距離のうち最短の距離が得られた代表データに前記入力データを帰属させる帰属手段と、を備えることを特徴とするデータ処理装置。

技術分野

0001

本発明はクラスタリング方法及びデータ処理装置に関する

背景技術

0002

近年、画像を色やテクスチャ座標など属性が類似した複数の領域に分割する技術が注目されている。分割された領域はスーパーピクセルと呼ばれ、分割領域単位符号化処理画像処理、及び画像認識処理を実行できるため、様々な画像処理装置における応用が可能である。

0003

従来、画像の領域分割に関して様々な手法が提案されている。特に、画素クラスタリングすることによって画像を領域に分ける手法が多く提案されている。この手法は、色やテクスチャ、座標を要素にもつデータを要素間の距離に基づいてクラスタリングする。クラスタリングでは、各クラスタ代表データを求め、入力データを最近傍の代表データに割り当てる。このとき、入力データと複数の代表候補データの距離を計算して最近傍代表データを探索する。クラスタリングを用いた領域分割の先行技術として特許文献1、非特許文献1、2などが挙げられる。

0004

非特許文献1では、SLIC(Simple Linear Iterative Clustering)と呼ばれるクラスタリング手法を用いて領域分割する方法が提案されている。SLICは、K−meansクラスタリングの最近傍代表データの探索範囲を画像中の局所領域に限定したものである。通常、入力データと各クラスの代表データとの距離計算にはユークリッド距離(L2距離)を用いるが、ユークリッド距離以外を用いる手法も提案されている。例えば、特許文献1では、データの各要素の重み付き距離を用いる手法が提案されている。また、非特許文献2では、L1距離とL∞距離の線形和を距離とする手法が提案されている。

0005

特許第3611006号公報

先行技術

0006

Radhakrishna Achanta, et al., “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 11, pp.2274-2282, Nov.2012.
“Algorithmic Transformations in the Implementation of K-means Clustering on Reconfigurable Hardware”, Proceeding of International Symposium on Field Programmable Gate Arrays, pp. 103-110, 2001.

発明が解決しようとする課題

0007

先に述べたように、クラスタリングは画像の領域分割においてよく用いられる技術である。領域分割では、色やテクスチャの特性が異なる領域が分割されていることが重要である。そのため、クラスタリングにおいては、入力データと色やテクスチャの特性が類似した領域内の代表候補データとの距離は小さく、逆に入力データと色やテクスチャの特性が異なる領域内の代表候補データとの距離は大きいことが好ましい。

0008

非特許文献1の方式では、色距離と座標距離の線形和を総合的な距離とする。非特許文献1において、色距離と座標距離はいずれもユークリッド距離である。しかし、色距離の計算にユークリッド距離を用いると、色の特性が異なる領域同士であっても色距離がそれほど大きくならない場合がある。例えば、領域同士で少数の色成分のみが大きく異なり、他の多数の色成分の違いが小さい場合である。この場合、多数の色成分の違いが小さいために色距離全体としてはそれほど大きくならないため、そのような領域間では境界精度が劣化するという課題がある。

0009

特許文献1の方式では、距離の算出においてすべての要素(色成分)に異なる重みを設定することが可能であるため、ユークリッド距離を使用するよりも境界精度が向上する場合があると考えられる。また、非特許文献2の方式では、L1距離及びL∞距離というユークリッド距離とは特性の異なる距離計算方法を使用するため、ユークリッド距離を使用するよりも境界精度が向上する場合があると考えられる。しかし、これらの方式はいずれも入力データの特性を考慮しておらず、入力データに関わらず重みあるいは線形和の係数が固定されているため、処理対象の画像によっては境界精度が劣化する場合があるという課題がある。

0010

本発明は上述した課題に鑑みてなされたものであり、入力データに応じて適切なクラスタリングを行えるようにすることを目的とする。

課題を解決するための手段

0011

上記課題を解決するための本発明の一態様によるクラスタリング方法は、
複数の入力データの各々が属するクラスを決定するクラスタリング方法であって、
入力データと複数の代表データの各々との距離を計算する計算工程と、
記入力データに基づいて距離計算方法を選択する選択工程と、
前記選択工程で選択された距離計算方法を用いて前記計算工程で算出された距離のうち最短の距離が得られた代表データに前記入力データを帰属させる帰属工程と、を有する。

発明の効果

0012

本発明によれば、入力データの特性に応じて代表候補データとの距離計算方法を変更することにより、入力データに応じた精度の高いクラスタリングが可能となる。

図面の簡単な説明

0013

第1の実施形態のクラスタリング方法を示すフローチャート
最近傍代表データの探索範囲を説明する図。
入力データと代表候補データの色成分の例を示す図。
データ処理装置の構成を示すブロック図。
第2の実施形態の距離計算方法の選択方法を示すフローチャート。
第2の実施形態の最近傍データ探索方法を示すフローチャート。
第3の実施形態の距離計算方法の選択方法を示すフローチャート。

実施例

0014

以下、添付の図面を参照して本発明の好適な実施形態について説明する。なお、本実施形態では、本発明によるクラスタリング方法を用いて画像を領域分割する例について説明する。

0015

[第1の実施形態]
<データ処理装置の構成例>
図4は、第1実施形態によるクラスタリング方法を実現可能なデータ処理装置の一構成例を示すブロック図である。以下では、図1のフローチャート等を参照して説明される各処理をCPUにより実現する構成を説明するが、処理の一部が専用のハードウエアにより実現されてもよことは言うまでもない。

0016

データ保存部401は、たとえばハードディスクフレキシブルディスクCD−ROM、CD−RやDVD、メモリーカードCFカードスマートメディアSDカードメモリスティック、xDピクチャーカードUSBメモリ等で構成される。データ保存部401にはクラスタリング(あるいは領域分割)の対象となる画像が保存されるが、画像の他にも、プログラムやその他のデータを保存することも可能である。なお、後述するRAM406の一部をデータ保存部401として用いるようにしても良い。またあるいは、後述する通信部402により接続した先の機器記憶装置を通信部402を介して利用することによりデータ保存部401が構成されても良い。表示部403は、領域分割処理前、領域分割処理後の画像を表示、あるいはGUI等の画像を表示する装置で、一般的にはCRT液晶ディスプレイなどが用いられる。あるいは、ケーブル等で接続された装置外部のディスプレイ装置を表示部403として用いても構わない。

0017

CPU404は本実施形態に係る主要な処理を実行すると共に本装置全体の動作を制御する。ROM405とRAM406は、その処理に必要なプログラム、データ、作業領域などをCPU404に提供する。後述する処理に必要なプログラムがデータ保存部401に格納されている場合や、ROM405に格納されている場合には、一旦、RAM406に読み込まれてから実行される。また通信部402を経由してデータ処理装置が外部記憶装置からプログラムを受信する場合には、一旦、データ保存部401に記録した後にRAM406に読み込まれるか、通信部402からRAM406に直接読み込まれてから実行される。

0018

CPU404は、データ保存部401に格納されている処理対象の画像をRAM406に書き込んだ後、RAM406から画像を読み出しクラスタリング処理を実行する。代表候補データ等の処理途中のデータは、CPU404によりRAM406に書き込まれ、必要に応じて読み出される。そして、クラスタリング処理結果をRAM406に書き込む。あるいは、表示部403に表示する。またあるいは、通信部402を介して外部装置に送信する。なお、図4においては、CPUが1つ(CPU404)だけである構成だが、これを複数設けるような構成にしても良いことは明らかである。

0019

通信部402は、機器間の通信を行うための通信I/Fとして機能する。この通信I/Fには例えば、公知のローカルエリアネットワーク、USB、IEEE1284、IEEE1394、電話回線などの有線など、各種の通信方式をもちいることができる。あるいは、通信I/Fには、赤外線(IrDA)、IEEE802.11a、IEEE802.11b、IEEE802.11g、IEEE802.11n、Bluetooth(登録商標)、UWB(Ultra Wide Band)等の無線通信方式が用いられても良い。

0020

なお、図4ではデータ保存部401や表示部403が全て1つのデータ処理装置内に含まれているが、これに限られるものではない。すなわち、これらの構成が公知の通信方式による通信路で接続され、全体としてこのような構成となっているのであっても構わない。なお、システム構成については、上記以外にも様々な構成要素が存在するが、本発明の主眼ではないのでその説明は省略する。以下、図4に示したデータ処理装置が処理する内容について説明する。フローチャート中の各ステップはCPU404の動作を示す。

0021

<領域分割のためのクラスタリング>
図1は本実施形態におけるクラスタリング方法を示すフローチャートである。本実施形態のクラスタリング方法は、入力データセットに含まれる複数の入力データの各々が属するクラスを、代表データとの距離に基づいて決定する。以下では、入力データセットとして画像を、入力データとしてその画像を構成する画素を扱う。まず、クラスタリング対象のデータについて説明する。[数1]は第i番目の入力データを示す。入力データは画像中の画素と対応するピクセルデータであり、5次元ベクトルである。



xi,1、xi,2は二次元の座標空間上の位置であり、画像の縦方向と横方向の座標値を意味する。xi,3、xi,4、xi,5は三次元の色特徴である。

0022

ステップS101では、CPU404は、代表データを初期化して生成する。具体的には、図2に示したクラスタリング処理対象の画像201を座標空間上のブロックに分割し、各ブロック203の中に1個の代表データ205を配置する。ブロック203内の入力データをランダムに選択し、選択した入力データの座標と色特徴のベクトルを、クラスを代表する代表データのベクトルとする。[数2]は第j番目の代表データを示す。



cj,1、cj,2は二次元の座標空間上の位置であり、画像の縦方向と横方向の座標値を意味する。cj,3、cj,4、cj,5は三次元の色特徴である。

0023

ステップS102では、最大繰り返し回数を設定し、繰り返し計算のループが開始される。ステップS103では、入力データのループが開始される。CPU404は、画像の中の入力データXiの順番iを制御しながら、ステップS104からステップS106までの処理を繰り返して全ての入力データをクラスタリングする。ステップS104では、CPU404は、探索範囲を設定する。より具体的には、入力データの座標位置によって代表候補データの探索範囲(たとえば、図2の探索範囲202)を設定する。なお、入力データの代表候補データとは、該当入力データを割り当てる(帰属させる)代表データの候補であり、設定された探索範囲内の代表データである。

0024

本実施形態では、探索範囲202として5×5のブロック203の範囲、すなわち探索範囲202が幅と高さ方向にそれぞれ5個の代表データを有する例について説明する。注目入力データ206が入っているブロック204を中心に、最近傍代表データの探索範囲202を設定する。この場合、探索範囲202は5×5個の座標近傍の代表データである。図2に示した例では、探索範囲202の代表データは縦方向インデックスが5から9までであり、縦方向インデックスが6から10までである。本実施形態では、注目入力データ206を含め、ブロック204の範囲に入っている全ての入力データの探索範囲202は同じとなる。なお、入力データの位置と探索範囲の代表候補データの関係は最初に固定され、繰り返し処理によって代表データが更新されることで代表データの位置が変わっても、代表データのインデックスは変わらない。

0025

ステップS105では、最近傍代表データの探索が行われる。入力データの最近傍代表データとは、該当入力データとの距離が最短な代表データ、即ち、距離空間上一番近い代表データである。ステップS105の探索処理の詳細については、図1の右側のフローチャートの参照により後述する。ステップS106では、CPU404は、最近傍代表データの探索結果(ステップS105)に基づいて、入力データを上述した最近傍代表データに帰属させる。ステップS107では、CPU404は、全ての入力データを処理したかどうかを判定する。全ての入力データを処理したと判定された場合は、CPU404は入力データループを終了し、処理はステップS108に進む。未処理の入力データが存在する場合は、処理はステップS104に戻り、次の入力データについて上述した処理を開始する。

0026

ステップS108では、CPU404は、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。その平均ベクトルを該当代表データの新しいベクトルCjとし、代表データを更新する。ステップS109では、CPU404は、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束するかどうかといった終了条件満足するか否かを判定する。終了条件が満たされた場合は、CPU404は、繰り返し計算を終了する。終了条件が満たされていない場合は、処理はステップS103に戻り、CPU404は、次の繰り返し計算を開始する。クラスタリング処理が終了すると、クラスタリング処理の結果が領域分割の結果として出力される。

0027

<最近傍代表データ探索>
次に、ステップS105において実行される最近某代表データ探索の処理について図1の右側のフローチャートを参照して説明する。以下、ステップS121〜S127では、第i番目の入力データXiに対して、距離が最短である代表データが代表候補データの中から探索される。まず、ステップS121〜S125では、入力データと複数の代表候補データの各々との距離が複数の距離計算方法を用いて計算される。そして、ステップS126では、複数の距離計算方法を用いて算出された距離に基づいて複数の距離計算方法のうちの1つが選択される。こうして、入力データに応じた距離計算方法の選択が行われることになる。ステップS127では、選択された距離計算方法により算出された距離に基づいて最近傍代表データを決定する。

0028

各ステップにおける処理内容を説明する前に、本実施形態における入力データと代表候補データとの距離計算方法について説明する。[数3]は第i番目の入力データと、第j番目の代表候補データとの距離計算式である。

0029

i番目の入力データと代表候補データとの距離は、複数の部分距離統合されたものであり、本実施形態では、座標空間上の距離と色空間上の距離が統合される。[数3]において、Dsは座標空間上の距離(部分距離)であり、Dcは色空間上の距離(部分距離)である。Wは座標空間上の距離に対する重みである。本実施形態では、[数3]が示すように、入力データと代表候補データとの距離は、DsとDcの線形結合により算出される。以降では、このように複数の部分距離から算出される距離のことを総合距離と呼ぶ。

0030

本実施形態によるクラスタリング方法では、複数の距離計算方法の中から、入力データに応じて使用する距離計算方法を選択する。また、複数の部分距離から総合距離を算出する場合、それらのうちの少なくとも一つの部分距離に対して距離計算方法を選択する。本実施形態では、座標空間上の距離Dsの距離計算方法としてユークリッド距離(L2距離)の一種類を使用する。また、色空間上の距離Dcの距離計算方法としてマンハッタン距離(L1距離)とチェビシェフ距離(L∞距離)の二種類を使用する。

0031

[数4]はL2距離によるDsの計算式である。また、[数5]および[数6]はそれぞれL1距離、L∞距離によるDcの計算式である。









なお、H1,H∞はそれぞれL1距離、L∞距離を正規化するための係数である。

0032

これらの距離計算方法を使用する理由について説明する。まず、座標空間上の距離にはユークリッド距離(L2距離)が使用される。領域分割において、座標空間上の距離は画像上での画素と代表候補データとの直線距離を示すことが好ましいからである。一方、色空間上の距離については、マンハッタン距離(L1距離)とチェビシェフ距離(L∞距離)から選択された距離が用いられる。領域分割では、入力データと色の特性が類似した領域内にある代表候補データとの色距離は小さく、逆に色の特性が異なる領域内にある代表候補データとの色距離は大きいことが好ましい。色の特性が異なる領域間では、少数の色成分のみが大きく異なる場合と、多数の色成分が同程度に異なる場合がある。

0033

[数7]はLp距離(p=1,2、...,∞)によるDcの計算式である。



[数7]に示されるように、Lp距離では、pの値が小さい場合は、各成分の指数の値が小さいため、Dcの値は各成分の差の平均値に近くなる。逆に、pの値が大きい場合は、Dcの値は各成分のうち、差の大きい少数の成分による影響が大きくなる。

0034

したがって、
・少数の色成分のみが大きく異なる場合にはpの値が大きいLp距離を使用し、
・多数の色成分が同程度に異なる場合にはpの値が小さいLp距離を使用する、
ことにより、一つのLp距離を使用するよりも入力データと色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離の差が大きくなる。本実施形態では特に、p=1及びp=∞として、[数5]および[数6]に示した距離計算方法を使用する。ただし、Lp距離はpの値により値の範囲が異なるため、Lp距離を正規化する。本実施形態では、各Lp距離の最大値が同じ値となるように正規化する。すなわち、L1距離の最大値は255×3であり、L∞距離の最大値は255であるため、H1=1、H∞=3とする。

0035

図3は入力データと代表候補データの色成分(Lab色空間で表される色成分)の例を示す図である。図3を用いて、色距離の計算方法としてL1距離、L∞距離を選択する効果について説明する。図3(a)は領域間で少数の色成分のみが大きく異なる場合の例であり(L成分のみが大きく異なる)、図3(b)はすべての色成分が同程度に異なる場合の例である。図3(a)において、入力データ301と色の特性が類似した領域内の代表候補データ302、色の特性が異なる代表候補データ303との色距離は、L1距離及びL∞距離それぞれに対して以下のようになる。

0036

・入力データ301と代表候補データ302との色距離
−L1距離:40(=|150−130|+|100−90|+|120−110|)
−L∞距離:20(=max(|150−130|、|100−90|、|120−110|))
・入力データ301と代表候補データ303との色距離
−L1距離:150(=|150−10|+|100−90|+|120−120|)
−L∞距離:140(=max(|150−10|、|100−90|、|120−120|))

0037

したがって、代表候補データ302、303との正規化された色距離の差はL1距離では110、L∞距離では120×3=360となる。すなわち、少数の色成分のみが異なる場合にはL∞距離を選択することにより、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離との差が大きくなることが分かる。

0038

一方、図3(b)において、入力データ304と色の特性が類似した領域内の代表候補データ305、色の特性が異なる代表候補データ306との色距離は、L1距離及びL∞距離それぞれに対して以下のようになる。
・入力データ304と代表候補データ305との色距離
−L1距離:40(=|150−130|+|100−90|+|120−110|)
−L∞距離:20(=max(|150−130|、|100−90|、|120−110|))
・入力データ304と代表候補データ306との色距離
−L1距離:140(=|150−100|+|100−60|+|120−70|)
−L∞距離:50(=max(|150−100|、|100−60|、|120−70|))。

0039

図3(a)の場合と同様に正規化して比較すると、代表候補データ305、306との色距離の差はL1距離では100、L∞距離では30×3=90となる。すべての色成分が同程度に異なる場合にはL1距離を選択することにより、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離との差が大きくなることが分かる。

0040

以下、図1のステップS121〜S127における処理内容について説明する。ステップS121では距離計算方法のループが開始される。CPU404は、距離計算方法の順番kを制御し、ステップS122からステップS124までを全ての距離計算方法を用いて処理する。本実施形態では、Dcの算出に、[数5]を使用する場合と[数6]を使用する場合の二種類の距離計算方法を使用する。なお、Dsの算出にはいずれの場合も[数4]が用いられる。

0041

ステップS122では、代表候補データのループが開始される。CPU404は、代表候補データCjの順番jを制御し、全ての代表候補データを探索する。ステップS123では、入力データと複数の代表データの各々との間の距離が計算される。すなわち、CPU404は、第i番目の入力データと第j番目の代表候補データとの総合距離を第k番目の距離計算方法を用いて算出する。ステップS124では、CPU404は、全ての代表候補データとの距離計算が完了したかどうかを判定する。全ての代表j候補データについて距離計算が完了したと判定された場合は、処理はステップS125に進み、CPU404は、代表候補データのループを終了する。一方、未処理の代表データがあると判定された場合は、処理はステップS123に戻り、CPU404は、次の代表候補データとの総合距離を計算する。

0042

ステップS125では、全ての距離計算方法を用いた処理が完了したかどうかを判定する。全ての距離計算方法を用いた処理が完了したと判定された場合は、処理はステップS126に進み、距離計算方法のループが終了する。一方、未処理の距離計算方法が存在すると判定された場合は、処理はステップS122に戻り、CPU404は、次の距離計算方法を用いて入力データと代表候補データとの総合距離を算出する。

0043

ステップS126では、次のステップS127において使用する距離計算方法を選択する。本実施形態では、Dcに対して[数5]を含む距離計算方法または[数6]を含む距離計算方法のいずれを用いて算出した距離計算結果を使用するかを選択することで距離計算方法の選択を行っている。換言すれば、部分距離Dcとして、[数5]または[数6]のいずれの計算方法を用いて得られた結果を採用するかが選択される。なお、Dsの距離計算方法は[数4]に示した一種類であるため、距離計算結果の選択はしない。前述したように、[数5]と[数6]のうち、色の特性が類似した領域内の代表候補データとの色距離と、色の特性が異なる領域内の代表候補データとの色距離の差が大きくなる距離計算方法を選択することが好ましい。そのため、本実施形態では、それぞれの距離計算結果のうち、代表候補データ間の分布広がりが大きい方の距離計算結果を選択する。

0044

式(8)は、本実施形態における、代表候補データ間の色距離の広がりRを算出する計算式である。



Siは、第i番目の入力データに対する代表候補データの集合を示す。

0045

ステップS126において、CPU404は各距離計算方法によって得られた距離計算結果について[数8]のRを算出し、Rが最大となる距離計算結果を提供した距離計算方法を選択する。ステップS127では、CPU404は、ステップS126において選択した距離計算方法により算出された距離([数3]により算出された距離)のうち、最短の距離となる代表候補データを、入力データXiを帰属させるべき最近傍代表データに決定する。

0046

以上説明したように、第1実施形態のクラスタリング方法によれば、入力データと代表候補データとの総合距離を複数の距離計算方法を用いて計算した後に、代表候補データ間での広がりが大きい距離計算結果が選択される。したがって、例えば、入力データに関わらず固定された距離計算方法が使用される場合よりも、色の特性が類似した領域内の代表候補データとの距離と、色の特性が異なる代表候補データとの距離の差が大きくなるため、領域分割の境界精度が向上する。

0047

なお、第1の実施形態では、入力データが座標と特徴量から構成され、入力データと代表データの距離(総合距離)を、座標の距離と特徴量の距離という2つの部分距離を統合することで算出した。ここで、複数の距離計算式が適用されるのは特徴量による部分距離であり、座標による部分距離の計算方法は複数の距離計算方法において共通であった。しかしながら、複数の距離計算方法はこれに限られるものではない。たとえば、座標の距離にも複数の計算方法が適用されてもよい。また、複数の距離計算式が適用されるさらに別の部分距離が総合距離に含まれるようにしてもよい。複数の部分距離を統合することにより総合距離を算出する距離計算方法において、複数の部分距離の少なくとも一つに対する計算方法が異なる複数の距離計算方法であればよい。なお、複数の計算方法が適用可能な部分距離が複数存在する場合には、それぞれの部分距離に関して分布の広がりが大きい計算方法(たとえばRが最大となる計算方法)が選択される。

0048

[第2の実施形態]
第1の実施形態では、複数種類の距離計算方法を用いた距離計算結果から適切な距離計算方法を特定した。第2の実施形態では、入力データの統計量に基づいて(たとえば、所定範囲内の入力データの統計量に基づいて)、使用する距離計算方法を選択する。なお、第2実施形態によるデータ処理装置の構成は第1の実施形態(図4)と同様である。また、第2実施形態によるクラスタリング処理の全体的な流れでは図1に示されるフローチャートにおいて、ステップS102以降の処理に先立って距離計算方法の選択が実行される。図5は第2の実施形態における距離計算方法の選択方法を示すフローチャートである。フローチャート中の各ステップはCPU404の動作を示しており、本実施形態ではステップS101の前に実行されるものとする。

0049

ステップS501では、CPU404は、距離計算方法を選択する単位となる距離選択領域と、その距離選択領域における距離計算方法の選択のために使用する参照領域を設定する。同じ距離選択領域内の入力データに対しては同じ距離計算方法を使用する。本実施形態では、距離選択領域内の入力データに対する代表候補データの値に影響を与える入力データの統計量を基に距離計算方法を選択するために、代表候補データが含まれる領域を参照領域として設定する。したがって、図2に示した例では、ブロック204が距離選択領域であり、探索範囲202(距離選択領域(ブロック204)を中心とした5×5ブロックの範囲)が参照領域である。

0050

ステップS502では、距離選択領域のループが開始される。CPU404は、距離選択領域の順番rを制御し、ステップS503からステップS505までを繰返すことにより、全ての距離選択領域に対して距離計算方法を選択する。ステップS503では、CPU404は、第r番目の距離選択領域に対する参照領域内の入力データを解析して統計量を算出する。具体的には、参照領域内の入力データ間の色ベクトルの差分の大きさが特定の成分に偏っている度合いを算出する。[数9]は、本実施形態における上記統計量を算出する計算式の一例である。

0051

ここで、Irは第r番目の参照領域に含まれる入力データの集合を示す。また、V(Xm,Xn)は、[数10]により算出される。

0052

[数10]において、|xm,u−xn,u|は第u番目の色成分の差分であり、|xm,v−xn,v|は第v番目の色成分の差分である。各色成分の差分の違いの総和を計算することにより、V(Xm,Xn)の値は、2つの入力データ間で一部の色成分のみが大きく異なる場合には大きな値となり、逆に多数の色成分が同程度に異なる場合には小さな値となる。

0053

多数の色成分が同程度に異なる場合の例として、(Xm,3,Xm,4,Xm,5)=(150,100,120)、(Xn,3,Xn,4,Xn,5)=(100,60,70)の場合、V(Xm,Xn)=20(=||150−100|−|100−60||+||150−100|−|120−70||+||100−60|−|120−70||))となる。また、一部の色成分のみが大きく異なる場合の例として、(Xm,3,Xm,4,Xm,5)=(150,100,120)、(Xn,3,Xn,4,Xn,5)=(10,90,120)の場合、V(Xm,Xn)=280(=||150−10|−|100−90||+||150−10|−|120−120||+||100−90|−|120−120||)となる。

0054

ステップS504では、CPU404は、ステップS503において計算したVの値を基に距離計算方法を選択する。ここで、Vの値が大きければ参照領域内の入力データは一部の色成分のみが大きく異なり、逆にVの値が小さければ参照領域内の入力データは多数の色成分が同程度に異なるといえる。そのため、前者の場合にはL∞距離が選択され、後者の場合にはL1距離が選択される。本実施形態では、Vの値と閾値Thの比較結果を基に色距離の計算方法が選択される。具体的には、CPU404は、V≧Thの場合にはL∞距離を選択し、V<Thの場合にはL1距離を選択する。そして、選択した距離計算方法を距離選択領域の番号rと関連付けてRAM406に格納する。ステップS505では、CPU404は、すべての距離選択領域に対して距離計算方法を選択したかどうかを判定する。すべての距離選択領域に対して距離計算方法が選択された場合は距離計算方法の選択処理を終了する。未処理の距離選択領域がある場合は、処理はステップS503に戻り、CPU404は、次の距離選択領域に対して距離計算方法を選択する。

0055

以上の処理により各距離選択領域の距離計算方法を選択した後、ステップS101〜S109により入力データを順次クラスタリングする。ただし、第2実施形態では使用する距離計算方法が選択されているので、第1の実施形態とはステップS105における最近某代表データ探索処理が異なる。図6は第2の実施形態における最近傍データ探索方法を示すフローチャートである。

0056

ステップS601では、CPU404は、ステップS504によりRAM406に格納した各距離選択領域に対する距離計算方法に従って第i番目の入力データに対して使用する距離計算方法を設定する。具体的には、CPU404は、入力データの座標情報xi,1、xi,2を基に、入力データが属する距離選択領域を判定し、その距離選択領域に対してステップS504で選択された距離計算方法を設定する。ステップS122〜S124では、CPU404は、ステップS601で設定された距離計算方法を用いて、第1の実施形態と同様に第i番目の入力データと代表候補データとの距離を計算する。そして、ステップS127において、CPU404は、算出された距離のうち最短の距離である代表候補データを第i番目の入力データに対する再近傍代表データに決定する。

0057

以上説明したように、第2の実施形態によれば、参照領域内の入力データの統計量を基に、距離選択領域内の入力データに対して使用する距離計算方法が選択される。所定の領域内の入力データの特性に応じて距離計算方法を選択することにより、1つの距離計算方法を使用するよりも領域分割の境界精度が向上する。また、距離計算方法を決定してから距離を計算するので、第1の実施形態よりも距離計算に関わる計算量は減少する。

0058

[第3の実施形態]
第2の実施形態では、所定の領域内の入力データ全てを用いて統計量を算出し、算出された統計量に基づいて距離計算方法を選択したが、これに限られるものではない。所定の領域内の入力データから選択された入力データを用いて統計量を算出し、これに基づいて距離計算方法を選択するようにしてもよい。たとえば、各距離選択領域(ブロック)から所定数の入力データ(たとえば、1画素おき、1ラインおき)を選択して統計量の算出に用いるようにしてもよい。以下、第3の実施形態では、所定の領域内の代表データ(代表候補データ)を基に使用する距離計算方法を選択する例を説明する。

0059

図7は第3実施形態における距離計算方法の選択方法を示すフローチャートである。フローチャート中の各ステップはCPU404の動作を示している。本処理は、代表データを設定した後、すなわち、図1(a)のステップS102とステップS103の間に実行される。つまり、各繰返しループの最初に、前回の繰返しループにおいて生成した代表データを用いて距離計算方法を選択する。

0060

図7に示される処理は、第2実施形態の距離計算方法の選択(図5)と同様であるが、ステップS701における統計量の算出方法が異なる。すなわち、ステップS701では、第r番目の距離選択領域に対する参照領域内の代表データを解析して統計量を算出する。[数11]は、第3の実施形態における統計量を算出する式である。



Srは第r番目の参照領域に含まれる代表データの集合を示す。なお、V(Cm,Cn)は式[数10]と同じ計算式により算出される。また、その他の処理は、第1、第2実施形態と同様である。

0061

以上説明したように、第3の実施形態によれば、参照領域内の代表データの統計量を基に、距離選択領域内の入力データに対して使用する距離計算方法が選択される。入力データよりも数の少ない代表データを用いることにより、第2の実施形態に比べて計算量を少なくすることができる。

0062

[他の実施形態]
第1の実施形態では、代表候補データ間の距離計算結果の分布の広がりをDcの距離計算結果の最大値と最小値との差により算出する([数8])としたが、これに限られるものではない。たとえば、距離計算結果の分散に基づいて分布の広がりを判定してもよい。あるいは、四分位範囲のように、上位及び下位の距離計算結果を除いた上での最大値と最小値の差としてもよい。

0063

また、第1の実施形態では、繰返し計算のループ毎に距離計算結果を選択するとしたが、これに限る訳ではない。例えば、一つの処理対象のブロック(ブロック204)について最初のL回(L≧1)のループにおいてのみ距離計算結果を選択し、当該ブロックの以降の繰返し計算のループではL回目のループにおいて選択した距離計算方法を使用するようにしてもよい。

0064

また、第1の実施形態では、異なる距離計算方法の最大値が同じ値になるように正規化するとしたが、正規化の方法はこれに限られるものではない。たとえば、学習用画像セットを用意し、それらの画像セットに対して最も境界精度が良くなるように正規化してもよい。

0065

第2、第3の実施形態では、参照領域内の入力データ(第2の実施形態ではすべての入力データ、第3の実施形態では代表データ)間の色ベクトルの差分の大きさが特定の成分に偏っている度合いを[数9]〜[数11]により算出した。しかしながら、統計量の算出方法はこれに限られるものではない。例えば、[数10]における差の代わりに比を用いてもよい。あるいは、参照領域内のデータの各成分の分散を算出し、各成分の分散の差もしくは比を統計量としてもよい。

0066

また、第2、第3の実施形態では、参照領域内の入力データ(第2の実施形態ではすべての入力データ、第3の実施形態では代表データ)のすべての組み合わせに対して各成分の差分の違いを算出するとしたが、これに限られるものではない。たとえば、参照領域内の入力データの平均を算出し、その平均と参照領域内の各データとの比較により各成分の差分の違いを算出してもよい。あるいは、参照領域内の1つまたは複数の入力データあるいは代表データを選択し、選択したデータと参照領域内の各入力データとの比較により各成分の差分の違いを算出してもよい。

0067

また、第2、第3の実施形態では、距離選択領域と参照領域は異なる領域であるとしたが、同じ領域であっても良い。

0068

また、第1〜第3の実施形態では、L1距離とL∞距離のうちから使用する距離計算方法を選択するとしたが、これに限る訳ではなく、他のLp(p=1,2,...,∞)距離を選択できるようにしてもよい。また、使用するLp距離の数は2種類に限る訳ではなく、任意の数であってもよい。なお、Lp距離を計算する際には、[数5]、[数6]と同様に、正規化のための係数Hpが乗算される。係数Hpの値は、たとえば、使用するすべてのLp距離の最大値が同じ値となるように設定される。

0069

Q種類(Q≧2)のLp距離を使用する場合の例について説明する。第1の実施形態では、Q種類のLp距離のうち、[数8]によって算出されるRの値が最大となる距離計算方法を選択すればよい(ステップS126)。第2、第3の実施形態では、Q−1個の閾値Thq(q=1,2,...,Q−1)を用いて、[数9]あるいは[数10]により算出されるVの値が大きい程、pの値が大きいLp距離が選択されるようにすればよい。

0070

なお、第1〜第3の実施形態では、最大値が同じ値となるようにLp距離を正規化するとしたが、これに限る訳ではなく、前回の繰返しループにおいて算出された各Lp距離の最大値が同じ値となるように正規化してもよい。

0071

また、第1〜第3の実施形態では、Lp距離を使用するとしたが、これ以外の距離計算方法を使用しても良い。[数12]は各成分の差に重み係数掛けて足し合わせることにより第i番目の入力データと、第j番目の代表候補データとの色距離を算出する計算式である。



a3,a4,a5は各成分に対する重み係数である。

0072

そして、複数の重み係数a3,a4,a5のセットを距離計算方法の候補として用意し、第1〜第3の実施形態において説明した選択方法により選択することにより、入力データに応じた距離計算式が選択されることになる。なお、Lp距離を使用する場合と同様に、それぞれの重みセットを用いた場合の距離の最大値が同じ値となるような重み係数を使用する。

0073

また、第1〜第3の実施形態では、入力データの座標はXi,1,Xi,2の二次元であるとしたが、これに限る訳ではなく、任意の次元の座標であっても良い。例えば、三次元の画像データであってもよい。

0074

また、第1〜第3の実施形態では、入力データの特徴量はXi,3,Xi,4,Xi,5という三次元の色特徴であるとしたがこれに限られるものではない。たとえば、特徴量としてテクスチャ特徴を用いてもよいし、テクスチャ特徴と色特徴を複合した特徴量を用いてもよい。したがって、特徴量の次元も三次元に限定される訳でなく、任意の次元であって良い。また、第1〜第3の実施形態では、探索範囲202は幅と高さがそれぞれ5個の代表データの例について説明したが、探索範囲の幅は5個の代表データに限定される訳でなく、任意の探索範囲であっても良い。

0075

以上のような、各実施形態によれば、入力データの特性に応じて代表候補データとの距離計算方法を変更することにより、領域分割の境界精度が向上することが可能となる。

0076

本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ(又はCPUやMPU等)がプログラムコードを読み出して実行する処理である。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。

0077

201:画像、202:探索範囲、203、204:ブロック、205:代表データ、206:注目入力データ、401:データ保存部、402:通信部、403:表示部、404:CPU、405:ROM、406:RAM

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • アースアイズ株式会社の「 監視装置、監視システム、及び、監視方法」が 公開されました。( 2020/09/24)

    【課題】2次元画像を用いた監視装置において、監視対象とした「人」が行う監視対象とした「物」に対する不定形な一般的動作を抽出して、監視対象とした「人」が、監視対象とした「物」に対して不審度の高い所定の行... 詳細

  • 富士ゼロックス株式会社の「 データ管理システム」が 公開されました。( 2020/09/24)

    【課題】階層構造になっている管理システムにおいて、管理対象データの実体を最上位の装置が全て管理する場合と比較して、管理対象データがユーザの意図しない装置に提供されないシステムを提供する。【解決手段】管... 詳細

  • ソニー株式会社の「 情報処理装置、情報処理方法、およびプログラム」が 公開されました。( 2020/09/24)

    【課題・解決手段】本技術は、複数人のユーザが皆満足できる空間を提供することができるようにする情報処理装置、情報処理方法、およびプログラムに関する。分析部は、複数人のユーザが存在する環境におけるセンシン... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ