(57)【特許請求の範囲】
【請求項１】
表示手段に画像間の類似性が定義された複数の画像を、コンピュータのプロセッサとメモリとを用いて、２次元の格子状に表示するステップを有するデータ集合表示方法において、
(e) 単位時間長に対応する更新ステップ数をS、更新頻度の下限をq_min、前記更新頻度の上限をq_maxとし、前記プロセッサと前記メモリとを用いて、更新ステップのカウンタtおよび更新頻度のカウンタnに0をセットし(310)、
(f)次に、前記プロセッサと前記メモリとを用いて、前記格子点をランダムに一つ選択し、その格子点上に前記データが配置されていた場合は、前記全対象データ中からそのデータを除いた集合から、別の前記データをランダムに１つ選択し、その格子点上に前記データが配置されていない場合は、前記全対象データ中から、前記別のデータをランダムに１つ選択し(312)、
(g) 前記(f)に引き続いて、前記プロセッサと前記メモリとを用いて、前記一つ選択した前記データが、前記格子点上の前記データであるならば(数3)
【数３】
0004304929.tif 000011
により、前記格子点上の前記データでなければ(数4)
【数４】
0004304929.tif 000012
により、更新後のエネルギ関数の変化量を計算し(313)、
(h) 前記(g)に引き続いて、前記プロセッサと前記メモリとを用いて、前記エネルギ関数の変化量に基づき（数５）
【数５】
0004304929.tif 000013
により更新確率Pを求め(314)、
(i) 前記(h)に引き続いて、前記プロセッサと前記メモリとを用いて、区間[0-1]の一様乱数rを生成し(315)、
(j) 前記(i)に引き続いて、前記プロセッサと前記メモリとを用いて、その乱数値rが前記更新確率Pの値より大ならば次のステップ(k)を行い、その乱数値rが前記更新確率Pの値より大でなければ、（数３）
【数３】
0004304929.tif 000014
を用いる場合にはすでに表示されている２つの前記データ間の配置一を交換する更新を行い、（数４）
【数４】
0004304929.tif 000015
を用いる場合には既に表示されている１つの前記データの位置に表示されていない２つ目の前記データを表示する更新を行い、その後にn=n+1の処理を行い(317)、
(k) 前記プロセッサと前記メモリとを用いて、t=t+1の処理を行い(318)、
(l) 前記プロセッサと前記メモリとを用いて、t＜S(ここで、Sは所定の単位時間である。) を満足する場合には、前記ステップ (f) の処理を行い、この条件を満足しない場合には、次のステップ (m) の処理を行い (319) 、
(m) 前記プロセッサと前記メモリとを用いて、単位時間内の更新頻度q=n/Sを求め(320)、
(n) 前記(m)に引き続いて、前記プロセッサと前記メモリとを用いて、ΔT(ここでΔTはその絶対値が１よりも十分に小さい値である。) ＜0を満足する場合には次のステップ (o) の処理を行い、その条件を満足しない場合には次のステップ (p) の処理を行い (330) 、
(o) 前記プロセッサと前記メモリとを用いて、ｑが下限q_minを下回っていたならステップ(p)の処理を行い、ｑが下限q_minを下回わる条件を満足しない場合にはステップ(q)の処理を行い(340)、
(p) 前記プロセッサと前記メモリとを用いて、ΔTの符号を反転して正の値とし、その後、次のステップ(q)の処理を行い(360)、
(q) 前記プロセッサと前記メモリとを用いて、T=T*(1+ΔT)の処理を行い(370)、その後前記(e)の処理を行うことを特徴とするデータ集合表示方法。
【請求項２】
前記ステップ (e)の前に次の(a)〜(d)のステップを有することを特徴とする請求項１記載のデータ集合表示方法。
(a) Aを前記表示手段に対して未表示の前記表示対象データの集合、Gを前記データが配置されていない格子点の集合とし、前記２次元の格子上の前記データの初期配置を求める方法の初期状態では、前記Aは前記表示手段に対しての表示対象の全ての前記データの集合とし、前記Gは表示領域中の全格子点の集合とし(200)、前記プロセッサと前記メモリとを用いて、前記未表示データ集合Aから前記データを１つ選択し(210)、
(b)前記(a)に引き続いて、前記プロセッサと前記メモリとを用いて、前記データが配置されていない格子点集合前記Gから、(数4)を用いて、選択された前記データを配置した際のエネルギ関数の増加量が最小となる格子点を求め、かつ、最小値を与える格子点が複数個存在する場合にはその中からランダムに１格子点を選択し（220）、
（ｃ）前記(b)に引き続いて、前記プロセッサと前記メモリとを用いて、前記(b)において選択された格子点上に、前記(a)において選択された前記データを配置し、前記集合AおよびGから前記(a) において選択された前記データを削除し、前記(b)において選択された前記格子点を削除し(230)、
(d) 前記（ｃ）に引き続いて、前記プロセッサと前記メモリとを用いて、前記A又はGのどちらかが空集合となるまで、前記(a)乃至（ｃ）の処理を繰り返して初期値を求める(240)。
【請求項３】
前記(e)〜(q)の処理中にコンピュータの割り込みが発生した場合には、その時点でその処理を終了することを特徴とする請求項１または２のいずれかに記載のデータ集合表示方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算機上でデータを表示する方法、及び該方法を実行させるためのプログラムに関する。
【０００２】
【従来の技術】
集合中の各要素を表現する小画像が定義されたデータ集合を、グラフィックスユーザインタフェース上の画面に表示する場合の方法として、最も一般的なものはリスト表示である。リスト表示では、集合中の要素に対して何かしらの基準に基づいた順序付けを行い、通常は、左上を始点として、横方向にデータを配列していく。横方向のデータ数が表示領域の最大幅に達したら、次の行の左端から、データを配列する。
【０００３】
各データに対して類似性を定義することができる場合、参照データとの類似性に基づいて集合を順序付け、類似性が高い順序でリスト状に表示することができる。類似性に基づくリスト表示では、参照データとの関係は表現されているが、表示されているデータ間の関係は表現されていない。これに対して、各データにベクトルが定義されており、データ間の類似性がベクトル空間中の距離を反映するものと仮定できる場合、ベクトル空間中から適切な２軸を選択することによって、データ集合を２次元散布図として表現することが可能である。この場合、データ間の類似性は、画面上での空間的距離として表現される。
【０００４】
なお、データが元来ベクトル空間中で定義される場合、上記の仮定は自明であるが、場合によっては、データ間類似性のみが定義されている場合がある。この場合は、データ間類似性から、それを導くベクトル空間を構成する多次元尺度構成法等の手法を用いて、各データのベクトル値を得ることができる。
【０００５】
【発明が解決しようとする課題】
散布図表現では、各データを表現する小画像が重複し、あるデータが他のデータを隠蔽する場合がある。また、散布図中の画面には、データが表示されていない領域も存在し、表示画面の利用としては効率的ではない。
【０００６】
一方、リスト表示は、データ表示が重複することなく、かつ、画面中に無用な隙間も生じない。従って、表示画面の利用としては効率的である。しかし、先述したように、データ間の類似性を反映した表現にはなっていない。
【０００７】
以上により、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示方法が得られれば、データ集合の表示方法として非常に有用であることが言える。
【０００８】
【課題を解決するための手段】
本出願は、各要素のデータ間に類似性が定義されたデータの集合を平面に格子状に配列する方法であって、前記各要素を前記格子上の隣接する他の前記要素との類似性を最大化するように配置することを特徴とするデータ集合表示方法を開示する。より具体的に説明すると、表示画面上にデータを格子状に配置する表現において、隣接するデータ間の類似性が低いと高くなるエネルギー関数を定義する。本エネルギー関数が低くなるようにデータの配置を更新していくことによって、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示を実現する。
【０００９】
【発明の実施の形態】
データ集合を格子状に配列した場合のエネルギー関数を以下のように定義する。
各格子点の近傍を定義し、近傍に存在するデータとの距離を全格子点について総和したものをエネルギー関数とする。この関数は、隣接するデータ間の類似性が低いと高くなる。
【００１０】
【数１】
0004304929.tif 000002
式中のv_iは、ｉ番目のデータのベクトル、Ｃは、互いに近傍に位置する関係にあるデータの組合せの集合、N_Cは近傍点の数である。本実施例では、図１に示す８近傍系を用いる。図1中央の格子点110を囲む図中では＋の記号が振られた格子点120が110の近傍格子点である。この場合、近傍点数N_Cは８である。次式は、同一のエネルギー関数を各ベクトルのノルムからなる成分と、ベクトル間の内積からなる成分に分離して表記したものである。
【００１１】
【数２】
0004304929.tif 000003
各格子点上のデータを交換した場合の上記エネルギー関数の変化量は、2通りに場合分けされる。
【００１２】
第１は、共に格子上に存在するデータiとjを交換する場合である。この場合のエネルギー関数の変化量は以下のようになる。
【００１３】
【数３】
0004304929.tif 000004
ここで、C(i)は、交換前の時点でのi番目のデータの近傍に存在するデータの集合、同様に、C(j)は、交換前の時点でのj番目のデータの近傍に存在するデータの集合である。なお、i番目のデータとj番目のデータが近傍に存在する場合、本式中の積和は重複することになるが、減算によって相殺されるので、本式は矛盾しない。
【００１４】
第2は、格子上に存在するデータiと格子上に存在しないデータjを交換する場合である。この場合のエネルギー関数の変化量は以下のようになる。
【００１５】
【数４】
0004304929.tif 000005
次に、上記エネルギー関数を用いて、実際にデータ集合の表示を構成する手続きについて述べる。手続きは、初期配置を求める部分と、配置を逐次的に更新していく部分に分けられる。
【００１６】
事前処理としは、表示対象データについての平均ベクトルを求め、各データのベクトルから引く。また、データが配置されていない格子点上には、0ベクトルを持つデータが存在すると仮定する。同様に、境界条件、すなわち、表示領域の外側に対応する格子点の状態についても、0ベクトルを持つデータが存在すると仮定する。従って、本手続きでは、境界条件として、対象データの平均ベクトルを設定していることとなる。
【００１７】
なお、表示対象データの個数と表示領域の格子点数の関係は任意とする。表示対象データが表示領域の格子点数を下回る場合、表示領域上の幾つかの格子点には、データは配置されない。データが配置されない格子点の位置は、データは配置の更新と全く同様に処理され、配置更新によって変動する。
【００１８】
初期配置を求める手続きを図2に示す。
【００１９】
Aを未表示の表示対象データの集合、Gをデータが配置されていない格子点の集合とする。本手続きの初期状態では、Aは、全表示対象データの集合、Gは、表示領域中の全格子点の集合となる200。
【００２０】
まず、未表示データ集合Aから、データを１つ選択する210。選択は、一定の順序に従って先頭から順番に行っても良いし、ランダムに行ってもよい。次に、データが配置されていない格子点集合Gから、選択されたデータを配置した際のエネルギー関数の増加量が最小となる格子点を求める。この際のエネルギー関数増加量の算出は、形式的には数4に帰着するが、元のデータが常に0ベクトル、かつ、追加データは既に選択された状態なので、第1項のノルムの項は無関係、第2項の内積の項のみが有効である。一般には、最小値を与える格子点は、複数個存在する。例えば、1番目のデータを配置する場合には、どの格子点上に配置してもエネルギー増加量は等しい。最小値を与える格子点が複数個存在する場合は、その中からランダムに１格子点を選択する220。選択された格子点上に、選択されたデータを配置し、集合A、G、それぞれから、それらの選択された要素を外す230。最後に、A、G、どちらかが空集合となるまで、上記処理を繰り返す240。
【００２１】
上記手続きにて得られた初期配置を初期値として、より適切な配置、すなわち、エネルギー関数が小さな配置となるように、逐次的な更新を行う。本更新は、エネルギー関数の増加量に従って変動する確率Pに基づき、確率的に行われる。Pは次式によって定義する。
【００２２】
【数５】
0004304929.tif 000006
ここで、Tは、確率性を制御する非負のパラメータである。T=0の場合、エネルギー関数の増加量ΔEが負なら、確率１で更新が行われ、ΔEが正なら、更新は行われない。Tが十分大ならば、更新が行われるかどうかは、ΔEの大小に関わりなく、ランダムに近い確率で決められる。なお、T=0、かつ、ΔE=0の場合は、P=0.5とする。
【００２３】
配置更新の手続きを図3に示す。本手続きでは、配置更新を行うループの外側で、パラメータTを調整するためのループが繰り返される。Tは、単位時間当たりの更新頻度が一定範囲の値をとるように制御される。図3では、単位時間長に対応する更新ステップ数をS、更新頻度の下限をq_min、上限をq_maxで表記している。また、ΔTは、1より十分小さい値である。
【００２４】
まず、更新ステップのカウンタ、および、更新頻度のカウンタに0がセットされる310。次に、格子点上をランダムに1つ選択し311、その格子点上にデータが配置されていた場合は、全対象データ中からそのデータを除いた集合から、別のデータをランダムに１つ選択する312。2つ目の選択データが、格子上のデータならば数3、そうでなければ数4に従って、更新後のエネルギー関数の変化量を計算する313。一方、311において選択された格子点上にデータが配置されていない場合とは、表示対象データ数が表示領域の格子点数を下回ってのみに生じる。従って、2つ目の選択データは、常に配置済みデータであるから、数６に従ってエネルギー関数の変化量が計算される。ただし、数3中のv_iにあたるベクトルは0ベクトルである。以上のようにして計算された変化量に基づき更新確率Pを計算する314。区間[0-1]の一様乱数を生成し315、その乱数がPより小なら316、更新を行う317。311からの手続きを１ステップとしてカウントし318、それが単位時間に達するまで繰り返す319。
【００２５】
ステップ数が単位時間に達したら、単位時間内の更新頻度ｑを計算し320、その値に基づいて確率性を制御するパラメータTの更新手続きを行う。ΔTが負の場合、すなわち、その時点で確率性を減少させる方向にTを更新していた場合、ｑが下限q_minを下回っていたなら、ΔTの符号を反転し正にする。逆に、ΔTが正の場合、すなわち、その時点で確率性を増大させる方向にTを更新していた場合、ｑが上限q_maxを上回っていたなら、ΔTの符号を反転し負にする。これらの条件が成立しなければ、ΔTはそのままである。最後に、Tの値を更新し370、310に戻る。本ループは、ユーザ割り込み等が生じない限り、無限に繰り返される。
【００２６】
次に、実際のシステム上で、上記手法を適用したソフトウェアプログラムを利用した例を示す。本例は、画像データを対象とした、特徴量ベクトル間の類似性に基づく検索を行なうシステムである。
【００２７】
本システムでは、特徴量ベクトルとして、画像中の色分布をヒストグラム化した色特徴量と、画像の輝度勾配ベクトルの方向成分の分布をヒストグラム化した形特徴量を用いる。両特徴量は、それぞれが50次元の数値ベクトルとして表現されており、合わせて100次元のベクトル空間中で検索は実行される。
本システムの構成を図4に示す。本システムは、画像特徴量に基づく検索を行う検索サーバ410、画像データの配信を行うWEBサーバ420、検索要求の発行、および、検索結果の表示を行うクライアントプログラム430からなる。検索サーバ410は、システム起動時に、画像特徴量のデータベース411から全画像分の特徴量ベクトルをメモリー内に取り込む。ユーザは、クライアントプログラム430上で、検索のキーとなる画像を指定し検索サーバ410に送信する。検索サーバ410は、指定されたキー画像とデータ全件と類似性を算出し、高類似度のデータのURLを検索結果としてクライアントプログラム430に送付する。クライアントプログラム430は、WEBサーバ420を経由して、検索結果に対応する画像を画像のデータベース421から取得し、ユーザインタフェース上の画面に表示する。
【００２８】
図5は、クライアントプログラム430が実行した画面表示例である。500で示したのが、検索のキー画像で、その画像と類似した画像を検索した結果が、表示領域510に表示されている。本例の場合、クライアントプログラム430が検索サーバ410に要求した検索結果の件数が、表示画像数と一致している。従って、画面上には常に同一の画像集合が表示されており、その配置のみが更新される。また、図２に示した初期表示の導出では、検索キーと類似性が高い順序にデータが選択され、配置される。
【００２９】
520は、配置の更新を止めるためのボタンである。530は、配置の更新を再開するためのボタンである。540と550は、図2の配置更新手続きにおけるパラメータq_minとq_maxを指定するスライダである。540がq_min、550がq_maxに対応する。560は、特徴量ベクトルを構成する2種類の下位成分である色特徴量と形特徴量のエネルギー関数に対する効果を調整するためのスライダである。スライダを上に上げると、各データのベクトルの内、色特徴量に対応する成分に対して1に近い数値が乗算され、形特徴量に対応する成分に対して0に近い数値が乗算される。スライダ下に下げると、各データのベクトルの内、色特徴量に対応する成分に対して0に近い数値が乗算され、形特徴量に対応する成分に対して1に近い数値が乗算される。図5の表示例では、色特徴量に対応する成分、形特徴量に対応する成分両者に0.5が乗算された状態である。本スライダを調整することによって、データの集まり方を、色を基準にして集まるようにするか、あるいは、形を基準にして集まるようにするか、といった設定が可能である。
【００３０】
本表示方法では、表示画面中に類似したデータどうしが集まった形での表現を得ることが出来る。従って、類似したデータを一括して選択することが容易である。図6は、表示画面中でのデータ選択を図示したものである。本図の例では、マウスカーソル610によって、矩形領域620を指定することによって、類似性が高い６つのデータを容易に一括選択することが出来ている。選択された画像については表示方法を変える等して抽出されたことを明示する。なお、配置更新によってデータの表示位置が変動すると、ユーザがデータ選択を行う上で不便である。本表示画面では、ユーザがマウスカーソルを操作してデータ選択を行おうとすると、自動的にデータの配置更新が中断される。その後、ボタン530をクリックすることによって、配置更新を再開することができる。
【００３１】
次に数1とは異なるエネルギー関数を定義した場合の表示方法について述べる。
【００３２】
まず、表示領域の各格子点について2種類の近傍を定義する。図７は、本定義を図示したものである。着目する格子点710の周囲の+で示した格子点720よりなる近傍と、そのまた周囲を取り囲む−で示した格子点730よりなる近傍を考える。以下、前者を＋タイプの近傍系、後者を−タイプの近傍系と呼ぶ。＋タイプの近傍系は、図1で示した近傍系と同一である。これに対して、−タイプの近傍系は、＋タイプの近傍系と相反するエネルギー関数に対する作用、すなわち、距離が大なほどエネルギー関数を減少させる作用を与えるものとして定義する。次式は、数1に対応するエネルギー関数の定義式である。
【００３３】
【数６】
0004304929.tif 000007
ここで、Ｃ+は、＋タイプの近傍関係にあるデータの組合せの集合、Ｃ-は、−タイプの近傍関係にあるデータの組合せの集合である。N_Ｃ+、N_C-は、それぞれ、＋タイプ、−タイプの近傍系の格子点数で、N_Ｃ+ = 8、N_C- = 16である。ρ+、ρ-は、これらを総近傍点数N_Ｃ+ ＋ N_C- =24で除したもので、ρ+ = 1/3、ρ- = 2/3である。数6を書き直した次式から明らかなように、本エネルギー関数では、各データのベクトルノルムのみの効果は相殺され消滅し、内積の効果のみが存在する。
【００３４】
【数７】
0004304929.tif 000008
次に、数3に対応する、共に格子上に配置されたデータiとjを交換する場合のエネルギー関数の変化量は次式のようになる。
【００３５】
【数８】
0004304929.tif 000009
ここで、C+(i)とC-(i)は、数3での表記と同様で、それぞれ、交換前の時点でのi番目のデータの＋タイプの近傍に存在するデータの集合と、−タイプの近傍に存在するデータの集合である。C+(j)、C-(j)も、同様に、交換前の時点でのj番目のデータの＋タイプの近傍に存在するデータの集合と、−タイプの近傍に存在するデータの集合である。
【００３６】
数4に対応する、格子上に配置されたデータiと格子上に配置されていないデータjを交換する場合のエネルギー関数の変化量は次式のようになる。
【００３７】
【数９】
0004304929.tif 000010
実際の配置の更新手続きについては、数3を数8に、数4を数9に置き換えることを除いて、図2、図3等で示した手続きと全く同一である。本エネルギー関数を用いる利点は、ベクトルノルムの効果が存在しない点である。数4を見れば明らかなように、数1のエネルギー関数を用いた場合、ノルムが小さいベクトルを持つデータ、すなわち、表示対象データの平均値ベクトルと近い値を持つデータが優先的に表示位置に現れる傾向を持つ。これに対して、数6で定義するエネルギー関数を用いた場合は、このような傾向は存在せず、結果として、表示内容のバリエーションを維持することができる。
【００３８】
【発明の効果】
本発明によって、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示方法が実現された。
【図面の簡単な説明】
【図１】８近傍系の説明図。
【図２】初期配置導出用の手続き。
【図３】配置逐次更新用の手続き。
【図４】システム構成図。
【図５】ユーザインタフェース上での画面表示例。
【図６】ユーザインタフェース上でのデータ選択の例。
【図７】数6のエネルギー関数で用いた近傍系の説明図。
【符号の説明】
110：着目した格子点。
120：近傍の格子点。
200：初期状態の定義。
210：データの選択。
220：格子点の選択。
230：データ更新。
240：終了判定。
310：カウンタのリセット。
311：格子点の選択。
312：データの選択。
313：エネルギー関数変化量の計算。
314：更新確率の計算。
315：乱数発生。
316：更新するか否かの判定。
317：配置の更新。
318：ステップカウンタの更新。
319：単位時間に達したかの判定。
320：更新頻度の計算。
330：ΔTの符号判定。
340：更新頻度の下限判定。
350：更新頻度の上限判定。
360：ΔTの符号反転。
370：Tの更新。
410：検索サーバ。
411：画像特徴量データベース。
420：WEBサーバ。
421：画像データベース。
430：クライアントプログラム。
500：検索キー画像。
510：表示画面。
520：配置更新中止用ボタン。
530：配置更新再開用ボタン。
540：更新頻度の下限を設定するスライダ。
550：更新頻度の上限を設定するスライダ。
560：特徴量の効果を調整するスライダ。
610：マウスカーソル。
620：選択領域。
710：着目する格子点。
720：＋タイプの近傍点。
730：−タイプの近傍点。
【図１】
0004304929.tif 000016
【図２】
0004304929.tif 000017
【図３】
0004304929.tif 000018
【図４】
0004304929.tif 000019
【図５】
0004304929.tif 000020
【図６】
0004304929.tif 000021
【図７】
0004304929.tif 000022