(57)【要約】【課題】リスト表示は、データ表示が重複することなく、かつ、画面中に無用な隙間も生じないため、表示画面の利用としては効率的であるが、データ間の類似性を反映した表現にはなっていない。一方、散布図表現は、データ間の類似性は空間的に表現されるが、各データの表示領域の重複、隠蔽が生じる場合がある。また、データが表示されていない領域が存在し、表示画面の利用としては効率的ではない。【解決手段】表示画面上にデータを格子状に配置する表現において、隣接するデータ間の類似性が低いと高くなるエネルギー関数を定義する。本エネルギー関数が低くなるようにデータの配置を更新していくことによって、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示を実現する。【選択図】図５
2004062356.tif 000002
【特許請求の範囲】
【請求項１】
各要素のデータ間に類似性が定義されたデータの集合を平面に格子状に配列するデータ集合表示方法であって、前記各要素を前記格子上の隣接する他の前記要素との類似性を最大化するように配置することを特徴とするデータ集合表示方法。
【請求項２】
表示手段に画像間の類似性が定義された複数の画像を２次元の格子状に表示するステップと、
前記表示された前記各画像の配置を隣接する他の前記画像との類似性を最大化するように更新するステップとを有することを特徴とするデータ表示方法をコンピュータに実行させるためのプログラム。
【請求項３】
指示手段からの指示に応じて前記配置の更新を中止するステップをさらに有することを特徴とする請求項２記載のプログラム。
【請求項４】
指示手段からの前記表示される複数の画像を含む領域の指定を受けて、該複数の画像を抽出するステップを更に有することを特徴とする請求項２又は３に記載のプログラム。
【請求項５】
前記配置を更新するステップは、前記表示手段の格子状の配置中に画像がない領域についても、画像があると仮定して前記画像の更新を行うことを特徴とする請求項２乃至４の何れかに記載のプログラム。
【請求項６】
前記配置を変換するステップは、前記隣接するデータ間の類似性が低いと高くなる関数を定義し、該関数が低くなるようにデータの配置を更新することを特徴とする請求項２乃至５のいずれかに記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算機上でデータを表示する方法、及び該方法を実行させるためのプログラムに関する。
【０００２】
【従来の技術】
集合中の各要素を表現する小画像が定義されたデータ集合を、グラフィックスユーザインタフェース上の画面に表示する場合の方法として、最も一般的なものはリスト表示である。リスト表示では、集合中の要素に対して何かしらの基準に基づいた順序付けを行い、通常は、左上を始点として、横方向にデータを配列していく。横方向のデータ数が表示領域の最大幅に達したら、次の行の左端から、データを配列する。
【０００３】
各データに対して類似性を定義することができる場合、参照データとの類似性に基づいて集合を順序付け、類似性が高い順序でリスト状に表示することができる。類似性に基づくリスト表示では、参照データとの関係は表現されているが、表示されているデータ間の関係は表現されていない。これに対して、各データにベクトルが定義されており、データ間の類似性がベクトル空間中の距離を反映するものと仮定できる場合、ベクトル空間中から適切な２軸を選択することによって、データ集合を２次元散布図として表現することが可能である。この場合、データ間の類似性は、画面上での空間的距離として表現される。
【０００４】
なお、データが元来ベクトル空間中で定義される場合、上記の仮定は自明であるが、場合によっては、データ間類似性のみが定義されている場合がある。この場合は、データ間類似性から、それを導くベクトル空間を構成する多次元尺度構成法等の手法を用いて、各データのベクトル値を得ることができる。
【０００５】
【発明が解決しようとする課題】
散布図表現では、各データを表現する小画像が重複し、あるデータが他のデータを隠蔽する場合がある。また、散布図中の画面には、データが表示されていない領域も存在し、表示画面の利用としては効率的ではない。
【０００６】
一方、リスト表示は、データ表示が重複することなく、かつ、画面中に無用な隙間も生じない。従って、表示画面の利用としては効率的である。しかし、先述したように、データ間の類似性を反映した表現にはなっていない。
【０００７】
以上により、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示方法が得られれば、データ集合の表示方法として非常に有用であることが言える。
【０００８】
【課題を解決するための手段】
本出願は、各要素のデータ間に類似性が定義されたデータの集合を平面に格子状に配列する方法であって、前記各要素を前記格子上の隣接する他の前記要素との類似性を最大化するように配置することを特徴とするデータ集合表示方法を開示する。より具体的に説明すると、表示画面上にデータを格子状に配置する表現において、隣接するデータ間の類似性が低いと高くなるエネルギー関数を定義する。本エネルギー関数が低くなるようにデータの配置を更新していくことによって、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示を実現する。
【０００９】
【発明の実施の形態】
データ集合を格子状に配列した場合のエネルギー関数を以下のように定義する。
各格子点の近傍を定義し、近傍に存在するデータとの距離を全格子点について総和したものをエネルギー関数とする。この関数は、隣接するデータ間の類似性が低いと高くなる。
【００１０】
【数１】
2004062356.tif 000003
式中のｖ＿ｉは、ｉ番目のデータのベクトル、Ｃは、互いに近傍に位置する関係にあるデータの組合せの集合、Ｎ＿Ｃは近傍点の数である。本実施例では、図１に示す８近傍系を用いる。図１中央の格子点１１０を囲む図中では＋の記号が振られた格子点１２０が１１０の近傍格子点である。この場合、近傍点数Ｎ＿Ｃは８である。次式は、同一のエネルギー関数を各ベクトルのノルムからなる成分と、ベクトル間の内積からなる成分に分離して表記したものである。
【００１１】
【数２】
2004062356.tif 000004
各格子点上のデータを交換した場合の上記エネルギー関数の変化量は、２通りに場合分けされる。
【００１２】
第１は、共に格子上に存在するデータｉとｊを交換する場合である。この場合のエネルギー関数の変化量は以下のようになる。
【００１３】
【数３】
2004062356.tif 000005
ここで、Ｃ（ｉ）は、交換前の時点でのｉ番目のデータの近傍に存在するデータの集合、同様に、Ｃ（ｊ）は、交換前の時点でのｊ番目のデータの近傍に存在するデータの集合である。なお、ｉ番目のデータとｊ番目のデータが近傍に存在する場合、本式中の積和は重複することになるが、減算によって相殺されるので、本式は矛盾しない。
【００１４】
第２は、格子上に存在するデータｉと格子上に存在しないデータｊを交換する場合である。この場合のエネルギー関数の変化量は以下のようになる。
【００１５】
【数４】
2004062356.tif 000006
次に、上記エネルギー関数を用いて、実際にデータ集合の表示を構成する手続きについて述べる。手続きは、初期配置を求める部分と、配置を逐次的に更新していく部分に分けられる。
【００１６】
事前処理としは、表示対象データについての平均ベクトルを求め、各データのベクトルから引く。また、データが配置されていない格子点上には、０ベクトルを持つデータが存在すると仮定する。同様に、境界条件、すなわち、表示領域の外側に対応する格子点の状態についても、０ベクトルを持つデータが存在すると仮定する。従って、本手続きでは、境界条件として、対象データの平均ベクトルを設定していることとなる。
【００１７】
なお、表示対象データの個数と表示領域の格子点数の関係は任意とする。表示対象データが表示領域の格子点数を下回る場合、表示領域上の幾つかの格子点には、データは配置されない。データが配置されない格子点の位置は、データは配置の更新と全く同様に処理され、配置更新によって変動する。
【００１８】
初期配置を求める手続きを図２に示す。
【００１９】
Ａを未表示の表示対象データの集合、Ｇをデータが配置されていない格子点の集合とする。本手続きの初期状態では、Ａは、全表示対象データの集合、Ｇは、表示領域中の全格子点の集合となる２００。
【００２０】
まず、未表示データ集合Ａから、データを１つ選択する２１０。選択は、一定の順序に従って先頭から順番に行っても良いし、ランダムに行ってもよい。次に、データが配置されていない格子点集合Ｇから、選択されたデータを配置した際のエネルギー関数の増加量が最小となる格子点を求める。この際のエネルギー関数増加量の算出は、形式的には数４に帰着するが、元のデータが常に０ベクトル、かつ、追加データは既に選択された状態なので、第１項のノルムの項は無関係、第２項の内積の項のみが有効である。一般には、最小値を与える格子点は、複数個存在する。例えば、１番目のデータを配置する場合には、どの格子点上に配置してもエネルギー増加量は等しい。最小値を与える格子点が複数個存在する場合は、その中からランダムに１格子点を選択する２２０。選択された格子点上に、選択されたデータを配置し、集合Ａ、Ｇ、それぞれから、それらの選択された要素を外す２３０。最後に、Ａ、Ｇ、どちらかが空集合となるまで、上記処理を繰り返す２４０。
【００２１】
上記手続きにて得られた初期配置を初期値として、より適切な配置、すなわち、エネルギー関数が小さな配置となるように、逐次的な更新を行う。本更新は、エネルギー関数の増加量に従って変動する確率Ｐに基づき、確率的に行われる。Ｐは次式によって定義する。
【００２２】
【数５】
2004062356.tif 000007
ここで、Ｔは、確率性を制御する非負のパラメータである。Ｔ＝０の場合、エネルギー関数の増加量ΔＥが負なら、確率１で更新が行われ、ΔＥが正なら、更新は行われない。Ｔが十分大ならば、更新が行われるかどうかは、ΔＥの大小に関わりなく、ランダムに近い確率で決められる。なお、Ｔ＝０、かつ、ΔＥ＝０の場合は、Ｐ＝０．５とする。
【００２３】
配置更新の手続きを図３に示す。本手続きでは、配置更新を行うループの外側で、パラメータＴを調整するためのループが繰り返される。Ｔは、単位時間当たりの更新頻度が一定範囲の値をとるように制御される。図３では、単位時間長に対応する更新ステップ数をＳ、更新頻度の下限をｑ＿ｍｉｎ、上限をｑ＿ｍａｘで表記している。また、ΔＴは、１より十分小さい値である。
【００２４】
まず、更新ステップのカウンタ、および、更新頻度のカウンタに０がセットされる３１０。次に、格子点上をランダムに１つ選択し３１１、その格子点上にデータが配置されていた場合は、全対象データ中からそのデータを除いた集合から、別のデータをランダムに１つ選択する３１２。２つ目の選択データが、格子上のデータならば数３、そうでなければ数４に従って、更新後のエネルギー関数の変化量を計算する３１３。一方、３１１において選択された格子点上にデータが配置されていない場合とは、表示対象データ数が表示領域の格子点数を下回ってのみに生じる。従って、２つ目の選択データは、常に配置済みデータであるから、数６に従ってエネルギー関数の変化量が計算される。ただし、数３中のｖ＿ｉにあたるベクトルは０ベクトルである。以上のようにして計算された変化量に基づき更新確率Ｐを計算する３１４。区間［０−１］の一様乱数を生成し３１５、その乱数がＰより小なら３１６、更新を行う３１７。３１１からの手続きを１ステップとしてカウントし３１８、それが単位時間に達するまで繰り返す３１９。
【００２５】
ステップ数が単位時間に達したら、単位時間内の更新頻度ｑを計算し３２０、その値に基づいて確率性を制御するパラメータＴの更新手続きを行う。ΔＴが負の場合、すなわち、その時点で確率性を減少させる方向にＴを更新していた場合、ｑが下限ｑ＿ｍｉｎを下回っていたなら、ΔＴの符号を反転し正にする。逆に、ΔＴが正の場合、すなわち、その時点で確率性を増大させる方向にＴを更新していた場合、ｑが上限ｑ＿ｍａｘを上回っていたなら、ΔＴの符号を反転し負にする。これらの条件が成立しなければ、ΔＴはそのままである。最後に、Ｔの値を更新し３７０、３１０に戻る。本ループは、ユーザ割り込み等が生じない限り、無限に繰り返される。
【００２６】
次に、実際のシステム上で、上記手法を適用したソフトウェアプログラムを利用した例を示す。本例は、画像データを対象とした、特徴量ベクトル間の類似性に基づく検索を行なうシステムである。
【００２７】
本システムでは、特徴量ベクトルとして、画像中の色分布をヒストグラム化した色特徴量と、画像の輝度勾配ベクトルの方向成分の分布をヒストグラム化した形特徴量を用いる。両特徴量は、それぞれが５０次元の数値ベクトルとして表現されており、合わせて１００次元のベクトル空間中で検索は実行される。
本システムの構成を図４に示す。本システムは、画像特徴量に基づく検索を行う検索サーバ４１０、画像データの配信を行うＷＥＢサーバ４２０、検索要求の発行、および、検索結果の表示を行うクライアントプログラム４３０からなる。検索サーバ４１０は、システム起動時に、画像特徴量のデータベース４１１から全画像分の特徴量ベクトルをメモリー内に取り込む。ユーザは、クライアントプログラム４３０上で、検索のキーとなる画像を指定し検索サーバ４１０に送信する。検索サーバ４１０は、指定されたキー画像とデータ全件と類似性を算出し、高類似度のデータのＵＲＬを検索結果としてクライアントプログラム４３０に送付する。クライアントプログラム４３０は、ＷＥＢサーバ４２０を経由して、検索結果に対応する画像を画像のデータベース４２１から取得し、ユーザインタフェース上の画面に表示する。
【００２８】
図５は、クライアントプログラム４３０が実行した画面表示例である。５００で示したのが、検索のキー画像で、その画像と類似した画像を検索した結果が、表示領域５１０に表示されている。本例の場合、クライアントプログラム４３０が検索サーバ４１０に要求した検索結果の件数が、表示画像数と一致している。従って、画面上には常に同一の画像集合が表示されており、その配置のみが更新される。また、図２に示した初期表示の導出では、検索キーと類似性が高い順序にデータが選択され、配置される。
【００２９】
５２０は、配置の更新を止めるためのボタンである。５３０は、配置の更新を再開するためのボタンである。５４０と５５０は、図２の配置更新手続きにおけるパラメータｑ＿ｍｉｎとｑ＿ｍａｘを指定するスライダである。５４０がｑ＿ｍｉｎ、５５０がｑ＿ｍａｘに対応する。５６０は、特徴量ベクトルを構成する２種類の下位成分である色特徴量と形特徴量のエネルギー関数に対する効果を調整するためのスライダである。スライダを上に上げると、各データのベクトルの内、色特徴量に対応する成分に対して１に近い数値が乗算され、形特徴量に対応する成分に対して０に近い数値が乗算される。スライダ下に下げると、各データのベクトルの内、色特徴量に対応する成分に対して０に近い数値が乗算され、形特徴量に対応する成分に対して１に近い数値が乗算される。図５の表示例では、色特徴量に対応する成分、形特徴量に対応する成分両者に０．５が乗算された状態である。本スライダを調整することによって、データの集まり方を、色を基準にして集まるようにするか、あるいは、形を基準にして集まるようにするか、といった設定が可能である。
【００３０】
本表示方法では、表示画面中に類似したデータどうしが集まった形での表現を得ることが出来る。従って、類似したデータを一括して選択することが容易である。図６は、表示画面中でのデータ選択を図示したものである。本図の例では、マウスカーソル６１０によって、矩形領域６２０を指定することによって、類似性が高い６つのデータを容易に一括選択することが出来ている。選択された画像については表示方法を変える等して抽出されたことを明示する。なお、配置更新によってデータの表示位置が変動すると、ユーザがデータ選択を行う上で不便である。本表示画面では、ユーザがマウスカーソルを操作してデータ選択を行おうとすると、自動的にデータの配置更新が中断される。その後、ボタン５３０をクリックすることによって、配置更新を再開することができる。
【００３１】
次に数１とは異なるエネルギー関数を定義した場合の表示方法について述べる。
【００３２】
まず、表示領域の各格子点について２種類の近傍を定義する。図７は、本定義を図示したものである。着目する格子点７１０の周囲の＋で示した格子点７２０よりなる近傍と、そのまた周囲を取り囲む−で示した格子点７３０よりなる近傍を考える。以下、前者を＋タイプの近傍系、後者を−タイプの近傍系と呼ぶ。＋タイプの近傍系は、図１で示した近傍系と同一である。これに対して、−タイプの近傍系は、＋タイプの近傍系と相反するエネルギー関数に対する作用、すなわち、距離が大なほどエネルギー関数を減少させる作用を与えるものとして定義する。次式は、数１に対応するエネルギー関数の定義式である。
【００３３】
【数６】
2004062356.tif 000008
ここで、Ｃ＋は、＋タイプの近傍関係にあるデータの組合せの集合、Ｃ−は、−タイプの近傍関係にあるデータの組合せの集合である。Ｎ＿Ｃ＋、Ｎ＿Ｃ−は、それぞれ、＋タイプ、−タイプの近傍系の格子点数で、Ｎ＿Ｃ＋　＝　８、Ｎ＿Ｃ−　＝　１６である。ρ＋、ρ−は、これらを総近傍点数Ｎ＿Ｃ＋　＋　Ｎ＿Ｃ−　＝２４で除したもので、ρ＋　＝　１／３、ρ−　＝　２／３である。数６を書き直した次式から明らかなように、本エネルギー関数では、各データのベクトルノルムのみの効果は相殺され消滅し、内積の効果のみが存在する。
【００３４】
【数７】
2004062356.tif 000009
次に、数３に対応する、共に格子上に配置されたデータｉとｊを交換する場合のエネルギー関数の変化量は次式のようになる。
【００３５】
【数８】
2004062356.tif 000010
ここで、Ｃ＋（ｉ）とＣ−（ｉ）は、数３での表記と同様で、それぞれ、交換前の時点でのｉ番目のデータの＋タイプの近傍に存在するデータの集合と、−タイプの近傍に存在するデータの集合である。Ｃ＋（ｊ）、Ｃ−（ｊ）も、同様に、交換前の時点でのｊ番目のデータの＋タイプの近傍に存在するデータの集合と、−タイプの近傍に存在するデータの集合である。
【００３６】
数４に対応する、格子上に配置されたデータｉと格子上に配置されていないデータｊを交換する場合のエネルギー関数の変化量は次式のようになる。
【００３７】
【数９】
2004062356.tif 000011
実際の配置の更新手続きについては、数３を数８に、数４を数９に置き換えることを除いて、図２、図３等で示した手続きと全く同一である。本エネルギー関数を用いる利点は、ベクトルノルムの効果が存在しない点である。数４を見れば明らかなように、数１のエネルギー関数を用いた場合、ノルムが小さいベクトルを持つデータ、すなわち、表示対象データの平均値ベクトルと近い値を持つデータが優先的に表示位置に現れる傾向を持つ。これに対して、数６で定義するエネルギー関数を用いた場合は、このような傾向は存在せず、結果として、表示内容のバリエーションを維持することができる。
【００３８】
【発明の効果】
本発明によって、データ間の類似性が表示画面中に表現され、かつ、表示画面を効率的に用いるデータ表示方法が実現された。
【図面の簡単な説明】
【図１】８近傍系の説明図。
【図２】初期配置導出用の手続き。
【図３】配置逐次更新用の手続き。
【図４】システム構成図。
【図５】ユーザインタフェース上での画面表示例。
【図６】ユーザインタフェース上でのデータ選択の例。
【図７】数６のエネルギー関数で用いた近傍系の説明図。
【符号の説明】
１１０：着目した格子点。
１２０：近傍の格子点。
２００：初期状態の定義。
２１０：データの選択。
２２０：格子点の選択。
２３０：データ更新。
２４０：終了判定。
３１０：カウンタのリセット。
３１１：格子点の選択。
３１２：データの選択。
３１３：エネルギー関数変化量の計算。
３１４：更新確率の計算。
３１５：乱数発生。
３１６：更新するか否かの判定。
３１７：配置の更新。
３１８：ステップカウンタの更新。
３１９：単位時間に達したかの判定。
３２０：更新頻度の計算。
３３０：ΔＴの符号判定。
３４０：更新頻度の下限判定。
３５０：更新頻度の上限判定。
３６０：ΔＴの符号反転。
３７０：Ｔの更新。
４１０：検索サーバ。
４１１：画像特徴量データベース。
４２０：ＷＥＢサーバ。
４２１：画像データベース。
４３０：クライアントプログラム。
５００：検索キー画像。
５１０：表示画面。
５２０：配置更新中止用ボタン。
５３０：配置更新再開用ボタン。
５４０：更新頻度の下限を設定するスライダ。
５５０：更新頻度の上限を設定するスライダ。
５６０：特徴量の効果を調整するスライダ。
６１０：マウスカーソル。
６２０：選択領域。
７１０：着目する格子点。
７２０：＋タイプの近傍点。
７３０：−タイプの近傍点。
【図１】
2004062356.tif 000012
【図２】
2004062356.tif 000013
【図３】
2004062356.tif 000014
【図４】
2004062356.tif 000015
【図５】
2004062356.tif 000016
【図６】
2004062356.tif 000017
【図７】
2004062356.tif 000018