JP2735866B2 - データベースのデータ検索方法 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、複数の記憶データ、例えば、画像データを
キーワード検索するデータベースのデータ検索方法に関
する。

［発明の概要］ 本発明は、キーワード検索により得られるデータのキ
ーワード列が類似していることに着目し、キーワード検
索結果の中の１つのデータとして、これに類似したデー
タをキーワード検索結果の中からモデル検索し、そのモ
デル検索により得られたデータ相互のキーワード列の距
離計算を行って、データ全体を、キーワード列が特に類
似するデータ群に自動的に分類する。さらには、分類さ
れたデータ群のキーワード列とキーデータのキーワード
列との距離計算を実行し、距離計算結果、すなわち、類
似度に応じて優先順を定めるようにしたので、従来では
必要であった人間による検索結果の分類処理が不要とな
る。さらには、優先順毎に上記データ群のキーワード列
を文字の画像形態で出力するようにしたので、検索者は
自動分類の基になったキーワードを確認することがで
き、次回のキーワード検索に用いることができる。

［従来の技術］ 従来、放送などにおいて広い分野の多種類の画像を記
憶しておく画像データベースのための検索方式として
は、一般的にキーワード検索方式が知られている。その
他、データベースに記憶されたデータの中から検索の手
がかりとなるデータと類似するデータを検索するベクト
ル型検索モデルによる検索方法も知られている。

上記キーワード検索方法では、１枚の画像を記憶する
時に、その内容に対応した複数の言葉、すなわち、キー
ワードを画像データに付加し、索引付けしておく。次
に、このキーワードを手がかりにデータベースの中に記
憶された複数の画像データの中から必要な画像データを
検索する。このようなキーワード検索方式は一元的な画
像データの分類に比べ画像に対する表現力が大きく、１
枚の画像に対しても多くの見方ができる多様な画像を扱
うデータベースに適している。

上記ベクトル型検索モデルによる検索方式は、文献検
索を行うデータベースシステムに適用されることが多
い。この方式ではデータベースシステムに記憶する各デ
ータに、キーワードを付与すると共にそのデータに付与
されたキーワードのそれぞれに重み付けを行う。次に、
検索の手がかりをキーワードの重みを要素とするベクト
ルで表し、検索に際しては検索の手がかりとなるベクト
ルと、データベースの中の各データのキーワードの重み
を要素とするベクトルとの間の類似度を計算し、次に、
計算された各データに対応する類似度をそのデータの検
索質問に対する適合度として表わす。この適合度の大き
さの順に検索結果を出力する。このように検索結果を検
索質問との適合度でランクづけることにより、効率的な
検索が可能となる。

［発明が解決しようとする課題］ しかしながら、キーワード検索方式では、該当するキ
ーワードを有するデータ全てを出力するので、検索結果
の個数を所定量に限定したいときには、その、検索の意
図をキーワードの論理的な組分せで適確に表現する必要
がある。さらに、検索の際に使用可能なキーワード個数
が限定されるときなど、適確な表現を得るためにはキー
ワードの論理的な組合せを変えて検索操作を繰り返す検
索試行が必要になる。加えて検索者がキーワードに対す
る知識が不足している場合には、この検索試行の効率が
非常に悪くなる欠点が従来のキーワード検索方式の画像
検索方法にはあった。

一方、ベクトル型検索モデルによる検索方式を画像デ
ータベースに対して適用すれば、上記キーワード検索に
よる検索試行の課程で得られた中間的な検索結果に含ま
れる画像の中で、もっとも検索の意図に近い画像のキー
ワード列を用いてこのキーワード列に類似した画像を検
索する。このため、検索試行の効率を上げることができ
る。しかし、放送局などで撮影画像を記憶し、後に画像
検索を行う場合、ベクトル型検索モデルによる検索方式
を用いても、検索結果として得られる類似画像は非常に
多数であり、かつ、それらの画像にも多くの種類が含ま
れている。

具体的には検索された各画像は、重みの高いキーワー
ドは一致しているが、重みの低いキーワードは異なって
いることが多い。このため類似度の順序による検索結果
の整理方法だけでは検索を十分に整理しきれないという
欠点があった。このため、ベクトル型検索モデルによる
検索方法では、検索結果が把握しにくくなり、逆に、検
索試行の効率が低下するという問題が生じていた。

そこで、本発明の目的は、このような不具合を解消
し、ベクトル型検索モデルにより検索された検索結果
を、分類し、その分類結果について優先順位を定めるこ
とが可能なデータベースのデータ検索方法を提供するこ
とにある。

［課題を解決するための手段］ このような目的を達成するために、本発明の第１形態
は予め記憶された複数のデータをキーワード検索し、当
該キーワード検索により得られる検索結果の中の１つの
データをキーデータとして選択し、検索結果の中からキ
ーデータのキーワード列と類似するデータをモデル検索
するデータベースのデータ検索方法であって、当該モデ
ル検索により得られた各データ相互のキーワード列につ
いての距離計算を実行し、当該距離計算の結果が所定値
以下となるデータを統合することにより複数の第１のデ
ータ群を作成し、当該作成された複数の第１データ群相
互のキーワード列についての距離計算を実行し、当該距
離計算の結果が所定値以下となる第１データ群を統合す
ることにより複数の第２データ群を作成して、モデル検
索により得られたデータを複数の第２のデータ群に分類
し、当該分類された複数の第２のデータ群の各々のキー
ワード列とキーデータのキーワード列との距離計算を実
行し、当該距離計算の結果に応じて分類された複数のデ
ータ群の優先順位を定めることを特徴とする。

本発明の第２形態は複数の第２データ群の各々に含ま
れるキーワード列を、文字を表わす画像の形態で優先順
位に従って出力することを特徴とする。

［作 用］ 本発明は、キーワード検索により得られるデータのキ
ーワード列が類似していることに着目し、キーワード検
索結果の中の１つのデータをキーデータとして、これに
類似したデータをキーワード検索結果の中からモデル検
索し、そのモデル検索により得られたデータ相互のキー
ワード列の距離計算を行って、データ全体を、キーワー
ド列が特に類似するデータ群に自動的に分類する。さら
には、分類されたデータ群のキーワード列とキーデータ
のキーワード列との距離計算を実行し、距離計算結果、
すなわち、類似度に応じて優先順を定めるようにしたの
で、従来では必要であった人間による検索結果の分類処
理が不要となる。さらには、優先順毎に上記データ群の
キーワード列を文字の画像形態で出力するようにしたの
で、検索者は自動分類の基になったキーワードを確認す
ることができ、次回のキーワード検索に用いることがで
きる。

［実施例］ 以下、図面を参照して本発明の実施例を詳細に説明す
る。

本発明の説明に先立って、本発明を適用した画像検索
システムのシステム構成を、第２図を参照して説明す
る。

第２図において、画像検索システムは、ホストコンピ
ュータ1,キーワード検索部2,類似画像検索部3,フレーム
メモリ4,画像表示装置5,記憶装置6,および画像分類部11
により主に構成されている。

次に、上述の構成各部の機能について説明する。

ホストコンピュータ１は各構成部を動作制御すると共
に、画像検索結果および画像検索結果の分類結果をフレ
ームメモリ４を介して画像表示装置５に表示する。

キーワード検索部２は、記憶装置６に格納された画像
データを、キーワードを基に検索して、キーワードが合
致する画像データを抽出する。

類似画像検索部３は、検索の基（キー）となる画像デ
ータのキーワード列と各画像データに付与されたキーワ
ード列との距離計算を行い、しきい値以下となる画像デ
ータを抽出する。

フレームメモリ４は画像表示装置５に表示すべき情
報、例えば、検索された画像データおよび後述の分類各
文字列を優先順に記憶する。

記憶装置６には画像キーワード番号行列ファイル（PK
行列ファイルと呼する）8,キーワードファイル９および
画像データファイル10を記憶する領域が設けられてい
る。

画像キーワード番号行列ファイル８は、第３図に示す
ように、記憶画像データの画像番号毎に、その画像デー
タに予め付与されたキーワード番号が記憶されている。

キーワードファイル９には、第４図に示すように検索
に用いられるキーワードとなる文字列とその番号および
そのキーワードの重みを示す数値が記憶されている。

画像データファイル10には画像番号と共に、例えば、
１画面分の画像データが格納されている。

本発明に関わる画像分類部11は、キーワード検索部２
および類似画像検索部３により検索された複数の検索結
果を後述の手法を用いて自動的に分類する。

第１図は第２図に示す画像分類部11の回路構成を示
す。

第１図において、画像分類部11は入力バッファ12,初
期分類回路13,分類統合回路15,分類順位決定回路17,分
類名生成回路19,画像ベクトル生成回路21,分類ベクトル
生成回路22およびベクトル距離計算回路23によって構成
される。この内、初期分類回路13,分類統合回路15,分類
順位決定回路17は内部バス24を介して画像ベクトル生成
回路21,分類ベクトル生成回路22,ベクトル距離計算回路
23に接続している。画像ベクトル生成回路21,分類ベク
トル生成回路22,ベクトル距離計算回路23,分類名生成回
路19は、バス７を介して記憶装置６と接続し、記憶装置
６に格納された画像キーワード番号行列ファイル8,キー
ワードファイル９の記憶データを参照して後述の処理を
行う。

なお、上述の回路13,15,17,19,21,22,23はそれぞれ、
演算プロセッサや論理演算回路を用いればよい。

第１図に示す画像分類部11の回路動作を説明する。

類似画像検索部３により、例えば、画像番号“2",
“5",“7",“9",“15",“23",“24",“31",“33"の計９
つの類似画像番号が検索結果として得られ、入力バッフ
ァ12には第５図に示すように、検索結果の個数“9"およ
び類似画像番号（以下、類似画像番号配列27と呼する）
が格納される。

次に、初期分類回路13は、第６図に示す以下の制御手
順を実行して、入力バッファ12に記憶された類似画像番
号配列27を初期分類する。

ステップS10） 入力バッファ12から類似画像番号配列2
7を読取ると共に、距離しきい値d_thを類似画像検索部３
から受信する。この距離しきい値d_thは、類似画像検索
部３において実行された類似画像番号の抽出に用いられ
た距離しきい値であり、本実施例では数値0.6を用い
る。

ステップS11） 分類しきい値c_thを距離しきい値d_thか
ら次式に従って求める。

c_th＝μ×d_th ……（１） ここで、μは０≦μ≦１の予め定めた定数で例え
ば、μ＝0.55とする。

ステップS12） 類似画像番号配列27に含まれる画像番
号に対応する各画像どうしの距離を画像距離計算回路14
により計算し、類似画像間距離行列Ｄを求める。

このために、画像距離計算回路14はベクトル距離計
算回路23に類似画像番号配列27を送り、下記（２）式の
計算を実行させる。

d_AB＝１−W_AB/（W_AA×W_BB）^0.5 ……（２） d_AB:ベクトルＡ、Ｂ間の距離 W_AB:A、Ｂに共通に含まれるキーワード要素に
対応する重み要素の自乗和 W_AA:Aの重み要素の自乗和 W_BB:Bの重み要素の自乗和 ここで、ベクトルA,Bには、画像ベクトル（第８図
参照）が用いられる。画像ベクトルは各画像番号の画像
が有するキーワード要素および重み要素により構成され
る。

画像ベクトル生成回路21では、類似画像番号配列27
の中の２つの画像番号を選択し、その画像番号を基にPK
行列ファイル８およびキーワードファイル９から画像番
号と対応するキーワード要素および重み要素を読み出し
て画像ベクトルを生成する。

次に、画像ベクトル生成回路21により作成されたベク
トルA,Bを用いて上記（１）式の計算がベクトル距離計
算回路23により行われる。続いてベクトル距離計算回路
23は、類似画像番号配列27の中の画像番号の組み合せを
変えて、上述と同様の手順で画像相互の距離を計算す
る。

このようにして得られた各距離計算結果d_ijが類似画
像距離行列Ｄの要素となる。

ステップS13） 類似画像距離間行列Ｄの各要素d_ijをス
テップS11において算出された分類しきい値c_thと比較
し、その比較結果r_ijを要素とした類似画像間関連行列
Ｒを求める。ここで、 d_ij＞c_thの時 r_ij＝０ d_ij≦c_thの時 r_ij＝１ ……（３） ステップS14） 類似画像間関連行列Ｒのグラフ表現の
極大完全部分グラフに対応した類似画像番号の部分集合
C₁,…,C_Nを、例えば、C.BronとJ.Kerboschによる文献Co
mmunications of ACM.Vol.16.No.9（1973）p.577のアル
ゴリズムに従って求める。本実施例では同じ部分集合に
含まれる画像間に対応した類似画像間関連行列Ｒの要素
r_ijがすべて“1"になる、すなわち、類似している画像
の画像番号の部分集合を抽出する。

上記部分集合C₁,…,C_Nから第９図に示すような各部
分集合に含まれる画像番号を要素とする分類画像番号配
列28を生成し、分類統合回路15へ入力する。以上の計算
課程で得られる各行列の一例を第７図に示す。

分類統合回路15では、第10図に示す制御手順を実行
し、以下に説明するステップS21〜ステップS24の処理に
より部分集合C₁,…,C_Nの統合を行う。

すなわち、 ステップS20） 距離しきい値d_thおよび分類番号配列28
を入力する。

ステップS21） 分類しきい値c_thを、距離しきい値d_th
を用いて（１）式に従って求める。

ステップS22） 分類画像番号配列28に含まれる分類ど
うしの距離と分類ベクトルを分類距離計算回路16（第１
図参照）によって計算する。具体的には、分類距離計算
回路16は、分類ベクトル生成回路22へ分類画像番号配列
28の各分類に属する画像の画像番号を送り、分類ベクト
ル生成回路22に分類ベクトルを生成させる。第12図に具
体例を示す分類ベクトルはその分類に含まれる画像番号
と対応した画像ベクトルの和である。分類ベクトル生成
回路22の指示する画像番号に基いて画像ベクトル生成回
路21により画像ベクトルを生成した後、生成された画像
ベクトルに基き、分類ベクトルを生成する（第11図参
照）。

分類毎に生成された分類ベクトルの集合を分類ベク
トル配列30と称する。分類距離計算回路16は生成された
分類ベクトルを順次ベクトル距離計算回路23へ送り、分
類ベクトル相互の距離計算を指示する。この指示に応じ
て、ベクトル距離計算回路23では画像ベクトルの距離計
算（ステップS12）のときと同様に（２）式により分類
ベクトル相互の距離計算を行う。次に、計算結果の中の
最小値Cdminを抽出し、その最小値Cdminを与える分類番
号の組（c₁,c₂）を検出する。

ステップS23） 次に分類距離の最小値cdminとしきい値
c_thを比較する。

cd_min≧c_thのとき、 分類同士の類似度は低い、すなわち、分類処理が終
了したと判断し、分類画像番号配列28を分類画像番号配
列29（第14図参照）として、分類ベクトル配列30ととも
に分類順位決定回路17へ入力する。

なお、第14図は分類画像番号配列29の構成内容を示
し、第14図において符号29−１は分類番号，符号29−２
は分類画像番号配列29に含まれる画像数を示す。符号29
−３は分類画像番号配列29に含まれる画像番号を示す。

cd_min＜c_thのとき、 次のステップS24へ進む。

ステップS24） 分類画像番号配列28の中の分類番号c₁,
c₂の分類に属する画像番号集合どうしの和集合Ｃを求め
分類の統合を行う。次に、分類画像番号配列28から分類
番号c₁,c₂に対応する分類を削除して分類番号を更新す
る。更新後の分類画像番号配列28の末尾に先の和集合Ｃ
を新たな分類として追加する。このようにして得られた
分類画像配列を新たな分類画像番号配列28として、ステ
ップS22へ戻り、距離最小値cdminがc_thよりも大きくな
るまで上述のステップS22〜S24の手順を繰り返す。

以上の手順を分類統合回路15で繰り返すことにより、
初期分類回路で初期的に分類された分類結果の中の類似
する分類結果を統合した分類の画像データ群が自動的に
生成される。分類順位決定回路17では、分類統合回路15
から出力の分類ベクトル配列30の各分類ベクトルと、キ
ー画像番号25（不図示）に対応する画像の画像ベクトル
の距離を画像分類距離計算回路18によって計算する。す
なわち、画像分類距離計算回路18は、キー画像番号25を
画像ベクトル生成回路21へ送り、キー画像番号25の画像
ベクトルを得て、この画像ベクトルと分類ベクトル配列
30の分類ベクトルを順次ベクトル距離計算回路23へ送
り、キー画像と各分類に対応する分類ベクトルとの距離
を求める。

次に、距離の小さい分類ほど優先順位が高いと考え、
この優先順に分類画像番号配列29,分類ベクトル配列30
の分類を分類順位決定回路17で並べ換える。並び換え結
果は、それぞれが分類画像番号配列31（第15図参照），
分類ベクトル配列32（第16図参照）として出力される。

なお、第15図は分類画像番号配列31の構成内容を示
し、第15図において符号31−１は分類番号、符号31−２
は画像番号の画像数、符号31−３は分類画像配列31に含
まれる画像番号を示す。

第16図は分類ベクトル配列32の構成内容を示し、第16
図において、符号32−１は分類番号、符号32−２は要素
の個数を示す。符号32−３は分類ベクトル配列32に含ま
れるキーワード番号、符号32−３はキーワード番号の重
みを示す。

分類名生成回路19は、分類順位決定回路17からの分類
ベクトル配列32を入力する。次に分類名生成回路19は分
類ベクトル配列32の各部類に対応した分類ベクトルの重
み要素の内でもっと大きいものの1/n以上の大きさで、
かつ、最も大きいものからｍ番目までの重みを持つ要素
を選択する。次に分類名生成回路19は選択した要素に対
応するキーワード要素のキーワード番号のキーワード文
字列を記憶装置６内のキーワードファイル９からバス７
を介して読み出し、キーワード文字列を分類毎に集めた
分類名キーワードの各文字を表わす画像を配列した文字
列配列33（第17図参照）として出力する。ここでn,mは
整数の定数で、例えばｎ＝2,m＝３とする。

なお、第17図は分類名キーワード文字列配列33の内容
の一例を示し、第17図において符号33−１は分類番号、
符号33−２は要素、符号33−３は要素を構成するキーワ
ード列を示す。

［発明の効果］ 本発明は、キーワード検索により得られるデータのキ
ーワード列が類似していることに着目し、キーワード検
索結果の中の１つのデータをキーデータとして、これに
類似したデータをキーワード検索結果の中からモデル検
索し、そのモデル検索により得られたデータ相互のキー
ワード列の距離計算を行って、データ全体を、キーワー
ド列が特に類似するデータ群に自動的に分類する。さら
には、分類されたデータ群のキーワード列とキーデータ
のキーワード列との距離計算を実行し、距離計算結果、
すなわち、類似度に応じて優先順を定めるようにしたの
で、従来では必要であった人間による検索結果の分類処
理が不要となる。さらには、優先順毎に上記データ群の
キーワード列を文字の画像形態で出力するようにしたの
で、検索者は自動分類の基になったキーワードを確認す
ることができ、次回のキーワード検索に用いることがで
きる。

【図面の簡単な説明】

第１図は第２図に示す画像分類部11の回路構成を示すブ
ロック図、 第２図は本発明実施例のシステム構成を示すブロック
図、 第３図は本発明実施例の画像キーワード番号行列ファイ
ル８の内容を示す説明図、 第４図は本発明実施例のキーワードファイル９の内容を
示す説明図、 第５図は本発明実施例の類似画像番号配列27の内容を示
す説明図、 第６図は第１図に示す初期分類回路13の処理手順を示す
フローチャート、 第７図は第１図に示す初期分類回路13の処理内容を示す
説明図、 第８図は本発明実施例の画像ベクトルの内容を示す説明
図、 第９図は本発明実施例の分類画像番号配列28の内容を示
す説明図、 第10図は第１図に示す分類統合回路15の処理手順を示す
フローチャート、 第11図は第１図に示す分類ベクトル生成回路22の分類ベ
クトル生成手順を示す説明図、 第12図は本発明実施例の分類ベクトルの内容を示す説明
図、 第13図は本発明実施例の分類ベクトル配列30の内容を示
す説明図、 第14図は本発明実施例の分類画像番号配列29の内容を示
す説明図、 第15図は本発明実施例の分類画像番号配列31の内容を示
す説明図、 第16図は本発明実施例の分類ベクトル配列32の内容を示
す説明図、 第17図は本発明実施例の分類名キーワード文字列配列33
の内容を示す説明図である。 １……ホストコンピュータ、 ３……類似画像検索部、 ６……記憶装置、 ８……画像キーワード番号行列（PK行列）ファイル、 ９……キーワードファイル、 10……画像データファイル、 11……画像分類部、 12……入力バッファ、 13……初期分類回路、 15……分類統合回路、 17……分類順位決定回路、 19……分類名生成回路、 20……出力バッファ。

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】予め記憶された複数のデータをキーワード
   検索し、当該キーワード検索により得られる検索結果の
   中の１つのデータをキーデータとして選択し、前記検索
   結果の中から前記キーデータのキーワード列と類似する
   データをモデル検索するデータベースのデータ検索方法
   であって、 当該モデル検索により得られた各データ相互のキーワー
   ド列についての距離計算を実行し、 当該距離計算の結果が所定値以下となるデータを統合す
   ることにより複数の第１のデータ群を作成し、 当該作成された複数の第１データ群相互のキーワード列
   についての距離計算を実行し、 当該距離計算の結果が所定値以下となる第１データ群を
   統合することにより複数の第２データ群を作成して、前
   記モデル検索により得られたデータを前記複数の第２デ
   ータ群に分類し、 当該分類された複数の第２データ群の各々のキーワード
   列と前記キーデータのキーワード列との距離計算を実行
   し、 当該距離計算の結果に応じて前記分類された複数のデー
   タ群の優先順位を定めることを特徴とするデータベース
   のデータ検索方法。
2. 【請求項２】請求項１に記載のデータベースのデータ検
   索方法において、 前記複数の第２データ群の各々に含まれるキーワード列
   を、文字を表わす画像の形態で前記優先順位に従って出
   力することを特徴とするデータベースのデータ検索方
   法。