図面 (/)

技術 画像処理装置、画像処理方法及びプログラム

出願人 キヤノン株式会社
発明者 チンソクイ
出願日 2015年5月14日 (6年7ヶ月経過) 出願番号 2015-099197
公開日 2016年12月22日 (5年0ヶ月経過) 公開番号 2016-218516
状態 特許登録済
技術分野 イメージ分析
主要キーワード 代表候補 データループ アクセス順番 距離空間 三角不等式 写真検索 代表データ スーパーピクセル
関連する未来課題
重要な関連分野

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

図面 (10)

課題

クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割できるようにする。

解決手段

まず、代表データ間のユークリッド距離(第一の距離)を算出しておき、次に、最近傍代表データを探索する際に、処理対象の入力データに係る代表データを基点代表データとして定め、入力データと基点代表データとの距離(第二の距離)を算出する。そして、ある代表データと基点代表データとの第一の距離と第二の距離との比が閾値を超える場合には、入力データとその代表候補データとの距離(第三の距離)の算出を省略することによって、処理量を低減する。

概要

背景

従来、領域毎の色やテクスチャなどの属性が同じになるように画像を複数の領域に分割する技術として領域分割手法が用いられる。このように分割された領域は、分割領域単位符号化処理画像処理画像認識処理等を行うことができるため、様々な画像処理装置において応用することができる。その中でも近年は、組み込みシステムで画像処理を行うことが多くなったため、組み込みシステム向けの高速化した領域分割手法が注目されている。

従来、画像の領域分割に関して様々な手法が提案されている。例えば非特許文献1〜3には、画素クラスタリングすることによって画像を複数の領域に分割する手法が開示されている。また、領域分割に限らず、クラスタリングを高速化する手法として非特許文献4に記載の手法が提案されている。

非特許文献1に記載の手法は、従来のK−Meansクラスタリングを行うためのハードウェアを用いて、画像の内容に基づいた写真検索ステム実装する手法であり、距離計算の高速化を並列度の高いハードウェアで実現している。非特許文献2に記載の手法は、SLICというクラスタリングの高速化のアルゴリズムを用い、スーパーピクセルという小領域を生成する手法である。この手法では、最近傍代表データ探索範囲が限定されているため、従来のK−Meansクラスタリングよりも計算量を少なくしている。

非特許文献3に記載の手法は、非特許文献2に記載のSLICというアルゴリズムを改良してGPUを実装する手法であり、最近傍代表データの探索範囲を3×3に限定し、より処理の高速化を図っているものである。また、非特許文献4に記載の手法は、従来のK−Meansクラスタリングを高速化するため、入力データが属する代表データの情報と代表データ間の距離の情報とを保存し、三角不等式を用いて不要な計算を削減する手法である。

概要

クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割できるようにする。まず、代表データ間のユークリッド距離(第一の距離)を算出しておき、次に、最近傍代表データを探索する際に、処理対象の入力データに係る代表データを基点代表データとして定め、入力データと基点代表データとの距離(第二の距離)を算出する。そして、ある代表データと基点代表データとの第一の距離と第二の距離との比が閾値を超える場合には、入力データとその代表候補データとの距離(第三の距離)の算出を省略することによって、処理量を低減する。

目的

ROM406及びRAM407は、その処理に必要なプログラム、データ、作業領域などをCPU405に提供する

効果

実績

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

この技術が所属する分野

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

請求項1

画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定手段と、前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、を有し、前記関連付け手段は、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする画像処理装置

請求項2

前記関連付け手段は、前記基点代表データと前記他の代表データとの距離の短い順に処理を行い、前記所定の条件を満たした段階で処理の対象となる画素を代表データと関連付けることを特徴とする請求項1に記載の画像処理装置。

請求項3

前記複数の領域はインデックス割り当てられていることを特徴とする請求項1又は2に記載の画像処理装置。

請求項4

前記関連付け手段は、前記処理の対象の画素を含む領域の位置に基づいて前記基点代表データを選択することを特徴とする請求項1〜3の何れか1項に記載の画像処理装置。

請求項5

前記関連付け手段は、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との比が所定の条件を満たした場合に、前記所定の条件を満たした代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする請求項1〜4の何れか1項に記載の画像処理装置。

請求項6

前記距離は、座標空間上の特徴量と、色空間上及びテクスチャ空間上のうち少なくとも1つの特徴量とで構成されていることを特徴とする請求項1〜5の何れか1項に記載の画像処理装置。

請求項7

前記関連付け手段は、前記選択した基点代表データと対応する全ての画素と代表データとの関連付けを終了してから、次の基点代表データを選択し、前記次の基点代表データと対応する画素と代表データとの関連付けを行うことを特徴とする請求項1〜6の何れか1項に記載の画像処理装置。

請求項8

前記関連付け手段によって関連付けされた画素の集合に基づいて、前記代表データの位置を更新する更新手段を更に有することを特徴とする請求項1〜7の何れか1項に記載の画像処理装置。

請求項9

画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定工程と、前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、を有し、前記関連付け工程においては、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする画像処理方法

請求項10

画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定工程と、前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、をコンピュータに実行させ、前記関連付け工程においては、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とするプログラム

技術分野

0001

本発明は、特に、クラスタリングを行うために用いて好適な画像処理装置画像処理方法及びプログラムに関する。

背景技術

0002

従来、領域毎の色やテクスチャなどの属性が同じになるように画像を複数の領域に分割する技術として領域分割手法が用いられる。このように分割された領域は、分割領域単位符号化処理画像処理画像認識処理等を行うことができるため、様々な画像処理装置において応用することができる。その中でも近年は、組み込みシステムで画像処理を行うことが多くなったため、組み込みシステム向けの高速化した領域分割手法が注目されている。

0003

従来、画像の領域分割に関して様々な手法が提案されている。例えば非特許文献1〜3には、画素をクラスタリングすることによって画像を複数の領域に分割する手法が開示されている。また、領域分割に限らず、クラスタリングを高速化する手法として非特許文献4に記載の手法が提案されている。

0004

非特許文献1に記載の手法は、従来のK−Meansクラスタリングを行うためのハードウェアを用いて、画像の内容に基づいた写真検索ステム実装する手法であり、距離計算の高速化を並列度の高いハードウェアで実現している。非特許文献2に記載の手法は、SLICというクラスタリングの高速化のアルゴリズムを用い、スーパーピクセルという小領域を生成する手法である。この手法では、最近傍代表データ探索範囲が限定されているため、従来のK−Meansクラスタリングよりも計算量を少なくしている。

0005

非特許文献3に記載の手法は、非特許文献2に記載のSLICというアルゴリズムを改良してGPUを実装する手法であり、最近傍代表データの探索範囲を3×3に限定し、より処理の高速化を図っているものである。また、非特許文献4に記載の手法は、従来のK−Meansクラスタリングを高速化するため、入力データが属する代表データの情報と代表データ間の距離の情報とを保存し、三角不等式を用いて不要な計算を削減する手法である。

先行技術

0006

Tse-Wei Chen, et al., "Photo Retrieval based on Spatial Layout with Hardware Acceleration for Mobile Devices,"IEEE Transactions on Mobile Computing, vol. 10, no. 11. pp. 1646-1660, Nov. 2011.
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.
C. Y. Ren and I. Reid., "gSLIC: a real-time implementation of SLIC superpixel segmentation," Technical Report University of Oxford, Department of Engineering, 2011.
Elkan, C., "Using the triangle inequality to accelerate k-means," Proc. of International Conference on Machine Learning (ICML), pp147-153, Aug. 2003.

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

0007

以上のようにクラスタリングは画像認識及び機械学習における不可欠な技術となってきており、クラスタリングアルゴリズムは画像の領域分割においてよく使用されている技術である。このクラスタリングにおいては、各クラスタの代表データを求め、画素(以下、入力データと表記)を代表データに割り当てることがある。この場合、入力データと複数の代表データの候補(以下、代表候補データ)との距離を計算して最近傍に位置する代表データを探索する必要がある。

0008

組み込みシステムにクラスタリングを実装する場合、入力データと代表候補データとの距離を計算するのに必要な計算量により、ハードウェアの並列度や回路規模が変わる。回路規模を削減するためには、クラスタリングのアルゴリズムの軽量化、又は計算量の削減に関する様々な対策が望まれる。

0009

非特許文献1に記載の手法は並列度の高いハードウェアにより高速化を実現しており、非特許文献2及び3に記載の手法はアルゴリズムを高速化させている。しかし、上述した先行技術を利用しても、高解像度の画像データに対して高速にクラスタリングを処理するためには、距離計算の計算量を十分に削減できていないという課題がある。非特許文献4に記載の手法は三角不等式によって不要な計算を削減するが、入力データが属する代表データに関する情報を保存する必要があるため、メモリコストが大きいという課題がある。

0010

本発明は前述の問題点に鑑み、クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割できるようにすることを目的としている。

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

0011

本発明に係る画像処理装置は、画像中の複数の領域に対してそれぞれの代表データを設定する代表データ設定手段と、前記それぞれの代表データとの距離を算出して、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、を有し、前記関連付け手段は、前記それぞれの代表データの中から基点となる基点代表データを選択し、処理の対象の画素について、前記基点代表データと前記処理の対象の画素との距離と、前記基点代表データと他の代表データとの距離との関係が所定の条件を満たした場合に、前記所定の条件を満たした他の代表データと前記処理の対象の画素との距離を算出しないようにすることを特徴とする。

発明の効果

0012

本発明によれば、クラスタリングにおける計算量及びメモリコストを削減して、精度良く画像を複数の領域に分割することができる。

図面の簡単な説明

0013

第1の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
最近傍代表データの探索範囲を説明するための図である。
入力データ、基点代表データ及び代表候補データの位置関係を説明するための図である。
データ処理装置ハードウェア構成例を示すブロック図である。
第2の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
第3の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
基点代表データごとに入力データを処理する様子を説明するための図である。
第4の実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
最近傍代表データの探索範囲の他の例を説明するための図である。

実施例

0014

(第1の実施形態)
以下、図面を参照しながら本発明の実施形態について詳細に説明する。

0015

<データ処理装置の構成例>
図4は、本実施形態における信号処理方法を実現可能なデータ処理装置400のハードウェア構成例を示すブロック図である。
図4において、データ保存部402は、画像データを保持する記憶媒体である。データ保存部402は、ハードディスクフレキシブルディスクCD−ROM、CD−RやDVD、メモリーカード、CF(登録商標カードスマートメディアSDカードメモリスティック、xDピクチャーカード、USBメモリ等で構成される。また、データ保存部402には、画像データの他にも、プログラムやその他のデータを保存することも可能である。あるいは、後述するRAM407の一部をデータ保存部402として用いてもよい。さらに、後述する通信部403により接続した先の機器記憶装置を、通信部403を介して利用するというように仮想的に構成するのであってもよい。

0016

表示部404は、画像処理を行う前後の画像を表示したり、GUI等の画像を表示したりする装置であり、一般的にはCRT液晶ディスプレイなどが用いられる。あるいは、ケーブル等で接続された外部のディスプレイ装置であっても構わない。

0017

入力部401は、ユーザーからの指示や、データを入力する装置であり、キーボードポインティング装置などである。なお、ポインティング装置としては、マウストラックボールトラックパッドタブレット等が挙げられる。あるいは、データ処理装置400を例えば公知のデジタルカメラプリンタなどの機器に適用する場合には、ボタンダイヤル等で構成されるのであってもよい。また、キーボードをソフトウェアで構成し、ボタンやダイヤル、あるいは先に挙げたポインティングデバイスを操作して文字を入力するように構成するのであってもよい。また、表示部404にタッチパネルを搭載し、表示部404と入力部401とが同一の装置であってもよい。その場合、タッチパネルを介した入力を入力部401の入力として扱う。

0018

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

0019

CPU405は、RAM407またはデータ保存部402に書き込まれた画像データを読み出して本実施形態に係る画像処理(クラスタリング)を実行し、その処理結果を再びRAM407に書き込む。そして、クラスタリングの処理結果に基づき、CPU405は画像認識処理を行う。CPU405により処理された画像認識の処理結果は、RAM407に保存されるか、通信部403を介して外部装置に送信される。

0020

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

0021

なお、図4に示す例では、入力部401、データ保存部402、表示部404が全て1つの装置内に含まれるような例を示しているが、これらの部分が公知の通信方式による通信路で接続されており、全体としてこのような構成となっていてもよい。また、図4に示す例においては、CPUが1つだけの構成であるが、CPUを複数設けるような構成にしてもよい。システム構成については、上記以外にも様々な構成要素が存在してもよいが、本発明の主眼ではないのでその説明は省略する。

0022

<領域分割のためのクラスタリング>
図1(a)は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。
まず、クラスタリング対象のデータについて説明する。以下の式(1)は第i番目の入力データを示す。入力データは画像中の画素と対応する5次元ベクトルであり、第i番目の入力データとは、画像をラスタスキャンして第i番目に読み出された画素に関する情報である。
Xi=(Xi,1,Xi,2,Xi,3,Xi,4,Xi,5) ・・・(1)

0023

式(1)中のXi,1,Xi,2は座標空間上の二次元特徴量を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、Xi,3,Xi,4,Xi,5はそれぞれ色空間上の三次元特徴量を表す。

0024

まず、ステップS101においては、初期化した代表データを生成する。具体的には、代表データ設定処理として、例えば図2に示した画像201を座標空間上のブロックに分割し、各々のブロック203の中からそれぞれ1個の入力データを選択し、代表データ205に設定する。そして、設定した全ての代表データをインデックス化し、ブロックの処理順又は位置順インデックス値を割り当てることにより、アクセス順番を制御できるようにする。

0025

図2において、画像201の左側の数字及び下側の数字は、それぞれ代表データの縦方向のインデックス、横方向のインデックスである。網点パターンに示すブロック204の中の代表データ205の縦方向のインデックス及び横方向のインデックスはそれぞれ「7」、「8」である。そして、選択した入力データの座標空間及び色空間の特徴量のベクトルをその代表データのベクトルとする。以下の式(2)は、第j番目の代表データ205に対するベクトルCjを示している。
Cj=(Cj,1,Cj,2,Cj,3,Cj,4,Cj,5) ・・・(2)

0026

式(2)中のCi,1,Ci,2は座標空間上の二次元特徴量を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、Ci,3,Ci,4,Ci,5はそれぞれ色空間上の三次元特徴量を表す。

0027

次のステップS102においては、最大繰り返し回数を設定し、ステップS103〜S118までの繰り返し計算のループを開始する。
ステップS103においては、代表データ間のユークリッド距離(第一の距離)D(Ci,Cj)を以下の式(3)により計算し、計算結果をRAM407に保存する。

0028

0029

続いてステップS104においては、各入力データに対してループを開始する。画像の中の入力データXiの順番iを制御し、ステップS105〜S115までの処理を繰り返して全ての入力データをクラスタリングする。

0030

ステップS105においては、探索範囲を設定する。具体的には、入力データの座標位置によって代表候補データの探索範囲を設定する。ここで、入力データの代表候補データとは、該当する入力データを割り当てる(帰属させる)代表データの候補である。

0031

以下、探索範囲202の幅および高さがそれぞれ3個である場合の例について説明する。まず、処理対象の入力データ(以下、注目入力データ)206が含まれているブロックを中心に、代表候補データの探索範囲を設定する。この場合、探索範囲は3×3個の座標近傍の代表データを含む領域である。図2に示す例の場合、探索範囲は縦方向インデックスが6〜8までであり、横方向インデックスが7〜9までである。注目入力データ206を含め、ブロック204の範囲に入っている全ての入力データの探索範囲202は同じである。なお、入力データの位置と探索範囲の代表候補データとの関係は最初に固定され、繰り返し処理によって代表データの位置が変わっても、代表データのインデックスは変わらないものとする。

0032

続いてステップS106において、最近傍代表データを探索する。ここで、入力データの最近傍代表データとは、当該入力データとの距離が最短な代表データ、即ち、距離空間上一番近い代表データである。この処理の詳細については後述する。

0033

次に、ステップS115において、ステップS106の処理による最近傍代表データの探索結果に基づいて、入力データを上述した最近傍代表データに帰属させる。そして、ステップS116において、全ての入力データを処理したかどうかを判定する。この判定の結果、全ての入力データを処理した場合は、ステップS117に進み、入力データのループを終了する。一方、まだ処理していない入力データがある場合はステップS104に戻り、次の入力データの処理を開始する。

0034

ステップS117においては、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。そして、その平均ベクトルを該当する代表データの新しいベクトルCjとし、代表データを更新する。
次に、ステップS118において、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束したかを判定する。この判定の結果、何れかの条件が成立する場合は、繰り返し計算を終了する。一方、いずれの条件も成立しない場合はステップS102に戻り、次の繰り返し計算を開始する。以上のように、代表データを繰り返し更新することにより、代表データに関連付けされた画素の集合が領域の分割結果となる。クラスタリングを終了すると、CPU405は、クラスタリング結果を表示部404などに出力する。

0035

<基点代表データの情報による最近傍代表データの探索>
次に、ステップS106の詳細な処理である図1(b)のステップS107〜S114について説明する。この処理では、上述した探索範囲202の中の全ての代表候補データとの距離を計算する。

0036

まず、ステップS107において、座標空間で第i番目の入力データに対応する基点代表データを決定し、入力データと基点代表データとの距離を算出する。ここで、第i番目の入力データに対応する基点代表データのインデックスをr(i)とする。具体的な距離の算出方法は、まず、注目入力データが含まれているブロック(領域)に対応する代表データを基点代表データとする。そして、注目入力データと基点代表データとのユークリッド距離(第二の距離)D(Xi,Cr(i))を以下の式(4)により算出する。

0037

0038

図2に示す例の場合、基点代表データは縦方向インデックスが「7」であり、横方向インデックスが「8」である。このように注目入力データ206を含め、ブロック204の範囲に入っている全ての入力データが対応する基点代表データは同じである。なお、入力データの位置と基点代表データとの関係は最初に固定され、繰り返し処理によって代表データの位置が変わっても、基点代表データのインデックスは変わらないものとする。そして、この処理で求めた第二の距離を後述する最短距離初期設定する。

0039

次にステップS108において、代表候補データのループを開始する。以下、ステップS109〜S114において代表候補データCjの順番jを制御し、全ての代表候補データを探索する。

0040

まず、ステップS109においては、ステップS103で保存した基点代表データと代表候補データとの距離(第一の距離)をRAM407から読み出し、第一の距離と第二の距離との比Ri,jを、以下の式(5)により算出する。この比は、後述する第三の距離を算出するか否かを判定するための所定の条件として用いられる。

0041

0042

続いてステップS110において、上述した第一の距離と第二の距離との比Ri,jが閾値を超えるかどうかを判定する。この判定の結果、閾値を超える場合は、後述するステップS111〜S113の処理を省略し、ステップS114に進む。一方、閾値以下である場合は、ステップS111に進む。

0043

ステップS111においては、第i番目の入力データと第j番目の代表候補データとのユークリッド距離(第三の距離)D(Xi,Cj)を以下の式(6)により算出する。

0044

0045

次にステップS112において、上述した第三の距離が最短距離以上かどうかを判定する。ここで、最短距離については後述する。この判定の結果、第三の距離が最短距離以上である場合は、ステップS113を省略し、ステップS114に進む。一方、第三の距離が最短距離未満である場合は、ステップS113に進む。そして、ステップS113において、最短距離を上述した第三の距離に更新し、最近傍代表データのベクトルをベクトルCjに変更する。

0046

ステップS114においては、全ての代表候補データとの比較が終了したかどうかを判定する。この判定の結果、全ての代表候補データとの比較が終了した場合は、最近傍代表データの探索を終了する。一方、まだ比較を行っていない代表候補データがある場合はステップS108に戻り、次の代表候補データとの距離の計算を開始する。

0047

<最近傍代表データの探索の例>
図3は、図1(b)のステップS106における最近傍代表データの探索処理概要を説明するための図である。図3において、点302は注目入力データの点301に対応する基点代表データの点であり、点303〜310は、注目入力データに対応する探索範囲の中の代表候補データの点である。この場合、基点代表データが最近傍代表データになる可能性もある。基点代表データの点302と代表候補データの点303〜310との距離(第一の距離)は最近傍代表データの探索処理を行う前にステップS103で算出されている。

0048

まず、ステップS107で基点代表データの点302と注目入力データの点301との距離(第二の距離)313を計算し、第2の距離313を最短距離に指定することによって初期化し、最近傍代表データを基点代表データに仮指定する。その後、ループ処理により代表候補データの点303〜310の順番で最近傍代表データを探索することになる。

0049

代表候補データの点303について処理を開始する場合、ステップS109では基点代表データの点302と代表候補データの点303との間の第一の距離311と、上述した第二の距離313との比を求める。ここで、S110の判定で上述した比の値が閾値を超えていないと判定されるものとする。この場合には、代表候補データの点303と注目入力データの点301との距離312の計算を省略することができないため、ステップS111に進む。そして、代表候補データの点303と注目入力データの点301との第三の距離312を算出し、この第三の距離312と最短距離である第二の距離との比較によって、最近傍代表データと最短距離とを更新するかどうかを判定する。

0050

次に代表候補データの点304について処理を開始する場合も同様に、注目入力データの点301との距離計算を省略することができないものとする。この場合も代表候補データの点304と注目入力データの点301との第三の距離によって、最近傍代表データと最短距離とを更新するかどうかを判定することになる。

0051

次に代表候補データの点305について処理を開始する場合、第一の距離314と上述した第二の距離313との比の値が閾値を超えるものとする。この場合には、代表候補データの点305と注目入力データの点301との距離315の計算を省略することができる。したがって、最近傍代表データと最短距離とを更新する必要がない。

0052

以下、代表候補データの点306〜310について処理を行う場合も、前述の比が閾値を超える場合には、代表候補データの点305と同様に注目入力データの点301との距離計算を省略することができ、最近傍代表データと最短距離とを更新する必要がない。

0053

以上のように本実施形態によれば、基点代表データの情報を利用するようにしたので、入力データと一部の代表候補データとの距離の計算を省略することによって処理を高速化することができる。また、本実施形態では、式(4)で説明したように、注目入力データが含まれているブロック(領域)に対応する代表データを基点代表データにする。したがって、従来手法のように注目入力データが対応する基点代表データの情報を保存する必要がないため、メモリコストを削減することができる。

0054

なお、本実施形態では、入力データの座標空間上の特徴量として、式(1)で表されるXi,1,Xi,2という一枚の画像の座標空間の二次元特徴量について説明した。一方、一枚の画像の座標空間の二次元特徴量に限定されるわけでなく、座標空間と複数枚の画像とを処理する時の時系列空間の任意の次元の特徴量でもよい。また、本実施形態では、入力データの特徴量として、座標空間及び色空間の特徴量について説明した。一方、座標空間及び色空間に限定されるわけでなく、座標空間上と、色空間上及びテクスチャ空間上のうち少なくとも1つとの特徴量であってもよい。また、色空間上の特徴量は三次元に限定される訳でなく、任意の次元の特徴量であってもよい。

0055

また、本実施形態においては、探索範囲の幅及び高さがそれぞれ3個の代表データを含む領域の例について説明したが、探索範囲の幅はそれに限定されるわけでなく、任意の探索範囲であってもよい。また、式(3)、式(4)及び式(6)には座標空間と色空間でのユークリッド距離を用いたが、ユークリッド距離に限定されるわけでなく、任意の距離尺度であってもよい。

0056

(第2の実施形態)
以下、本発明の第2の実施形態について、第1の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。

0057

図5は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図1と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
図5(a)のステップS501においては、代表データ間のユークリッド距離(第一の距離)を式(3)により計算する。そして、基点代表データを1つ定めた場合に、基点代表データとの距離順によって代表データに順位を付け、計算結果をRAM407に保存する。この順位付けパターンは、代表データの数だけ存在することになる。

0058

図5(b)のステップS108においては、代表候補データのループを開始する。本実施形態では、代表候補データCjの順番jを制御し、ステップS104のループで対象となっている入力データに係る基点代表データの順位付けの情報をRAM407から読み出す。そして、その読み出した情報によって、基点代表データとの距離が短い代表候補データから基点代表データとの距離が長い代表候補データまでという順番で全ての代表候補データを探索する。図5(b)のステップS502の判定では、上述した第一の距離と第二の距離との比が閾値を超える場合に、代表候補データのループを途中で終了するようにする。

0059

<最近傍代表データの探索の例>
本実施形態に係る処理について図3を参照しながら説明する。代表候補データの点303〜310は、基点代表データの点302との距離が短い順に並んでいる。つまり、代表候補データの点303と基点代表データの点302との距離が一番短く、代表候補データの点310と基点代表データの点302との距離が一番長い。

0060

まず、ステップS107で基点代表データの点302と注目入力データの点301との距離(第二の距離)313を計算し、第二の距離313を最短距離に指定することによって初期化し、最近傍代表データを基点代表データに指定する。その後、代表候補データの点303〜310までという距離の短い順で最近傍代表データを探索する。

0061

まず、代表候補データの点303について処理を開始し、基点代表データの点302と代表候補データの点303との間の第一の距離311と、上述した第二の距離313との比を求める。上述した比の値が閾値を超えていないため、代表候補データの点303と注目入力データの点301との距離312の計算を省略することができない。そこで、代表候補データの点303と注目入力データの点301との第三の距離312によって、最近傍代表データと最短距離とを更新するかどうかを判定する。

0062

次に、代表候補データの点304について処理を開始する。この場合も上述した比の値が閾値を超えていないため、注目入力データの点301との第三の距離の計算を省略することができない。そして、代表候補データの点304と注目入力データの点301との第三の距離によって、最近傍代表データと最短距離とを更新するかどうかを判定する。

0063

次に、代表候補データの点305について処理を開始する。第一の距離314と上述した第二の距離313との比の値が閾値を超えるため、代表候補データの点305と注目入力データの点301との第三の距離315の計算を省略することができる。この段階で、代表候補データの点306〜310と基点代表データの点302との第一の距離は、それぞれ代表候補データの点305と基点代表データの点302との第一の距離314よりも長いことが判別できる。したがって、代表候補データの点306〜310についても、上述した比が閾値を超えることが判別できるため、ループ処理を終了することができる。

0064

以上のように本実施形態によれば、基点代表データと代表候補データとの距離によって順番を制御するようにしたので、ループ処理を途中で終了させることができ、不要な計算を省略することができる。このように第1の実施形態よりもさらに距離計算の回数が減り、処理を高速化することができる。

0065

(第3の実施形態)
以下、本発明の第3の実施形態について、第1の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。

0066

図6は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図1と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
まず、図6(a)のステップS601においては、基点代表データのループを開始する。画像の中の基点代表データCkの順番kを制御し、ステップS602〜S604までの繰り返しにより全ての基点代表データCkに対応する入力データを処理する。

0067

ステップS602においては、探索範囲を設定する。具体的には、基点代表データの座標位置によって入力データの代表候補データの探索範囲を設定する。そして、ステップS603においては、基点代表データCkと探索範囲の中の代表データとのユークリッド距離(第一の距離)D(Ck,Cj)を以下の式(7)により計算し、計算結果をRAM407に保存する。

0068

0069

図6(a)のステップS104においては、入力データのループを開始する。入力データXiが対応する基点代表データは上述した基点代表データCkであり、第i番目の入力データの対応する基点代表データのインデックスr(i)はkである。上述した基点代表データCkに対応する入力データXiの順番iを制御し、ステップS105〜S115までの繰り返しにより基点代表データCkに対応する全ての入力データをクラスタリングする。

0070

図6(a)のステップS604においては、上述した基点代表データCkに対応する全ての入力データを処理したかどうかを判定する。この判定の結果、基点代表データCkに対応する全ての入力データを処理した場合は、ステップS605に進み、入力データループを終了し、そうでない場合はステップS104に戻り、次の入力データの処理を開始する。具体的には、図7に示すように、基点代表データ703に対応するブロック701の中の全ての入力データを処理した後に基点代表データ704に対応するブロック702の中の全ての入力データを処理することになる。ブロック702の中の入力データを処理する時は、基点代表データ704と探索範囲の中の代表データとの距離のみを保存し、基点代表データ703と探索範囲の中の代表データとの距離を保存する必要がない。

0071

図6(a)のステップS605においては、全ての基点代表データについて処理を終了したかどうかを判定する。この判定の結果、全ての基点代表データについて処理が終了した場合は、ステップS117に進み、入力データループを終了する。一方、まだ処理を行っていない基点代表データがある場合は、ステップS601に戻り、次の基点代表データの処理を開始する。なお、図6(b)に示す処理は、図1(b)に示す処理と同様である。

0072

以上のように本実施形態によれば、探索範囲の中の代表データとの距離だけを計算して保存するようにしたので、従来手法のように全ての代表データとの距離の計算を不要することができ、処理をより高速化することができる。また、第一の距離の保存量を少なくすることができるため、メモリコストをより削減することができる。

0073

(第4の実施形態)
以下、本発明の第4の実施形態について説明する。本実施形態では、第2の実施形態と第3の実施形態とを組み合わせており、第2または第3の実施形態と異なる部分についてのみを説明する。したがって、本実施形態に係るデータ処理装置の構成等については説明を省略する。

0074

図8は、本実施形態におけるクラスタリングの処理手順の一例を示すフローチャートである。なお、図5または図6と同様の処理については同じ符号を付しており、これらの処理の説明は省略する。
図8(a)のステップS803においては、基点代表データCkと探索範囲の中の代表データとのユークリッド距離(第一の距離)を式(7)で計算して距離の短い順に整列し、計算結果を距離順にRAM407に保存する。本実施形態では、基点代表データのループ処理を行っているため、距離の順序として1つのパターンのみを保存することになる。ステップS108では、距離の短い順に代表候補データのループを開始する。なお、図8(b)に示す処理は、図5(b)に示す処理と同様である。

0075

以上のように本実施形態によれば、探索範囲の代表候補データのみを対象としてステップS502の判定を行うようにしたので、より計算を省略することができる。このように第3の実施形態と比べて第三の距離の計算回数が減り、処理をより高速化することができる。また、探索範囲の中の代表データとの第一の距離だけを保存するため、メモリコストをより削減することができる。

0076

(その他の実施形態)
<探索範囲の幅および高さがそれぞれ偶数個の代表データの例>
前述した実施形態では、探索範囲の幅および高さがそれぞれ奇数個(3つ)の代表データを含む領域である例について説明した。一方、探索範囲の幅および高さは奇数個の代表データに限定されるわけでなく、探索範囲の幅および高さがそれぞれ偶数個の代表データを含む領域の場合にも同様に適用可能である。

0077

図9は、探索範囲の幅および高さがそれぞれ偶数個の代表データを含む領域に設定した場合の探索範囲を説明するための図である。第1の実施形態で説明したように、まず、図9に示した画像901を座標空間上のブロックに分割し、各ブロック903の中に1個の代表データ905を配置する。そして、注目入力データ906に一番近いブロックの角を中心にして、代表候補データの探索範囲902を設定する。この場合、探索範囲の代表データは縦方向インデックスが6〜7であり、横方向インデックスが8〜9である。注目入力データ906を含め、矩形904の範囲に入っている全ての入力データに対して同じ探索範囲902となる。なお、探索範囲902の幅および高さがそれぞれ2個の代表データを含む領域の例について説明したが、探索範囲の幅は2個の代表データを含む領域に限定されるわけでなく、任意の探索範囲であってもよい。

0078

<任意の空間上のブロック分割
また、前述した実施形態では、入力データを座標空間上のブロックに分割する例について説明したが、座標空間に限定されるわけでなく、入力データを任意の距離空間上のブロックに分割してもよい。

0079

本発明は、上述の実施形態の1以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける1つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、1以上の機能を実現する回路(例えば、ASIC)によっても実現可能である。

0080

405 CPU

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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