JP2007149018A - 図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法 - Google Patents

Abstract

【課題】図形検索処理の高精度化および効率化を図ること。
【解決手段】（Ａ）では、代表図形画像Ｒ１の形状特徴量の種類Ｃａに関するユークリッド距離区間Ｉ１（Ｉ１＝［０，ｄ１］）に、形状特徴量の種類Ｃａを用いた場合のクエリ図形画像Ｑのユークリッド距離ｄ１ｑが、ユークリッド距離ｄ１よりも大きいため（ｄ１＜ｄ１ｑ）、クエリ図形画像Ｑの形状特徴量の種類としては、形状特徴量の種類Ｃａは相応しくないことがわかる。一方、（Ｂ）では、代表図形画像Ｒ２の形状特徴量の種類Ｃｂに関するユークリッド距離区間Ｉ２（Ｉ２＝［０，ｄ２］）に、形状特徴量の種類Ｃｂを用いた場合のクエリ図形画像Ｑのユークリッド距離ｄ２ｑが、ユークリッド距離ｄ２以下であるため（ｄ２≧ｄ２ｑ）、クエリ図形画像Ｑの形状特徴量の種類としては、形状特徴量の種類Ｃｂは相応しいことがわかる。
【選択図】図９

Description

この発明は、図形画像の検索をおこなう図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法に関する。

従来、製造業では競争力のある製品を低コストで開発し早期に市場投入するために，既存製品の図面などの技術資産を有効活用することが求められている。これまで蓄積してきた大量の図面の中から必要な情報を見つけるためには、必要な部品が描かれている図面を効率よく検索する技術が必要となる。

そこで単純な方法として、図面に付与した部品名などをキーワードとして入力するテキスト中心の検索が多く用いられていた。最近、テキストでは表現が難しい部品の形状を使った検索を実現するために、図面に描かれた部品の形状情報を用いた類似形状検索技術（たとえば、下記非特許文献１〜３を参照。）も用いられつつある。

馬場、劉汝傑、遠藤、椎谷、上原、増本、長田著 「機械系組立図面からの形状に基づく部品検索手法の提案」 電子情報通信学会技術研究報告書 PRMU2004-225, pp.79-84(2005) 劉汝傑、馬場、増本著 「アトリビュート グラフ マッチングベースド エンジニアリング ドローイングス リトリーバル（Attributed Graph Matching based Engineering Drawings Retrieval）」 プロク オブ アイ・エー・ピー・アール ワークショップ オン ドキュメント アナリシス システムス （Proc. of IAPR Workshop on Document Analysis Systems(DAS04)） ２００４年９月 , pp.378-388 劉汝傑、馬場、増本著 「コンポーネント パーツ エクストラクション フロム アセンブリー ドローイングス フォー コンテント ベースド リトリーバル（Component Parts Extraction from Assembly Drawings for Content based Retrieval）」 プロク オブ ジ アイ・イー・イー インターナショナル カンファレンス オン ビジュアル インフォメーション（Proc. of The IEE International Conference on Visual Information Engineering: Convergence in Graphics and Vision(VIE2005)） ２００５年４月 pp.45-50

しかしながら、上述した非特許文献１〜３に開示されている従来の類似形状検索技術では、図面から抽出する形状などの情報は、あらかじめ決められた特徴量の種類がいくつか用意されているが、検索時に利用すべき特徴量を、ユーザが試行錯誤的に指定しなければならなかった。

このため、指定された特徴量が適切でない場合には、検索精度の低下を招くという問題があった。また、所望する図形が得られなかった場合には、再度特徴量を指定して検索しなければならないため、検索作業に時間がかかるという問題があった。

ここで、上記問題点を具体的に説明する。従来の類似形状検索におけるクエリ画像の指定方法では、最初にユーザが指定するクエリ画像として、たとえば、ボルトやナットなどの大まかな図面の種類（ジャンル）ごとに代表クエリ画像と呼ばれる画像を用意しておく。

そのような場合に、たとえば、代表クエリ画像Ａには特徴量ａを、代表クエリ画像Ｂには特徴量ｂを用いた方がそれぞれ検索精度が良いというように、代表クエリ画像によって異なる種類の特徴量を用いた方が検索精度が良いことが経験的にわかっている場合においても、従来の類似形状検索では、このような経験的に得られた情報を検索に生かす仕組みが存在しない。

そのため、新たなクエリ画像αが与えられた場合に、従来技術では経験的に得られた情報を生かせず、クエリ画像αの検索時に利用すべき特徴量を、ユーザが試行錯誤的に指定しなければならなかった。

この発明は、上述した従来技術による問題点を解消するため、クエリ図形画像の検索時に利用すべき最適な形状特徴量の種類を自動設定することにより、図形検索処理の高精度化および効率化を図ることができる図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法を提供することを目的とする。

上述した課題を解決し、目的を達成するため、この発明にかかる図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法は、代表的な図形画像（以下、「代表図形画像」という）を取得し、取得された代表図形画像の形状特徴量の種類に関する利用条件を設定し、クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付け、設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力手段によって入力されたクエリ図形画像の形状特徴量の種類に決定し、決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索し、検索結果を出力することを特徴とする。

この発明によれば、クエリ図形画像の検索時に利用すべき最適な形状特徴量の種類を自動設定することができる。

また、上記発明において、前記形状特徴量の種類を用いて、前記代表図形画像とサンプル図形画像との類似度を算出し、算出された類似度に基づいて、前記利用条件を設定することとしてもよい。

この発明によれば、代表図形画像の類似範囲を自動設定することができる。

また、上記発明において、前記代表図形画像から前記サンプル図形画像までの距離情報を算出し、算出された距離情報に基づいて、前記利用条件を設定することとしてもよい。

この発明によれば、代表図形画像の類似範囲を、サンプル図形画像との距離情報として自動設定することができる。

また、上記発明において、前記距離情報に関する前記サンプル図形画像の確率密度分布を作成し、作成された確率密度分布に基づいて、前記利用条件を設定することとしてもよい。

この発明によれば、代表図形画像の類似範囲を、代表図形画像と類似するサンプル図形画像の数により自動設定することができる。

また、上記発明において、前記検索結果に基づいて、前記検索手段による検索精度を算出し、算出された検索精度に基づいて、決定された形状特徴量の種類に関する利用条件を、前記検索精度に応じて変更することとしてもよい。

この発明によれば、検索精度の向上を図ることができる。

また、上記発明において、前記形状特徴量の種類を用いて、前記代表図形画像と前記クエリ図形画像との類似度を算出し、算出された類似度が前記利用条件を満たすか否かを判定し、判定された判定結果に基づいて、前記代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定することとしてもよい。

この発明によれば、形状特徴量の種類を適用した場合の代表図形画像とクエリ図形画像との類似度により、クエリ図形画像の検索時に利用すべき最適な形状特徴量の種類を自動設定することができる。

また、上記発明において、前記代表図形画像ごとに、当該代表図形画像の形状特徴量の種類を用いて、前記クエリ図形画像との類似度を算出し、算出された類似度ごとに、当該類似度が前記利用条件を満たすか否かを判定し、前記利用条件を満たすと判定された類似度が複数存在する場合、当該複数の類似度のうち最大類似度となる代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定することとしてもよい。

この発明によれば、クエリ図形画像の検索時に利用すべき形状特徴量の種類が複数候補存在する場合、最適な形状特徴量の種類を自動設定することができる。

また、上記発明において、前記代表図形画像から前記クエリ図形画像までの距離情報を算出し、算出された距離情報に基づいて、前記利用条件を満たすか否かを判定することとしてもよい。

この発明によれば、代表図形画像の類似範囲を、クエリ図形画像との距離情報として自動設定することができる。

また、上記発明において、前記代表図形画像ごとに、当該代表図形画像の形状特徴量の種類を用いて、前記クエリ図形画像までの距離情報を算出し、算出された距離情報ごとに、当該距離情報が前記利用条件を満たすか否かを判定し、前記利用条件を満たすと判定された距離情報が複数存在する場合、当該複数の距離情報のうち最小距離情報となる代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定することとしてもよい。

この発明によれば、クエリ図形画像の検索時に利用すべき形状特徴量の種類が複数候補存在する場合、最適な形状特徴量の種類を自動設定することができる。

本発明にかかる図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法によれば、クエリ図形画像の検索時に利用すべき最適な形状特徴量の種類を自動設定することにより、図形検索処理の高精度化および効率化を図ることができるという効果を奏する。

以下に添付図面を参照して、この発明にかかる図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法の好適な実施の形態を詳細に説明する。

（図形検索装置のハードウェア構成）
まず、この発明の実施の形態にかかる図形検索装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる図形検索装置のハードウェア構成を示すブロック図である。

図１において、図形検索装置は、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、ＨＤＤ（ハードディスクドライブ）１０４と、ＨＤ（ハードディスク）１０５と、ＦＤＤ（フレキシブルディスクドライブ）１０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）１０７と、ディスプレイ１０８と、Ｉ／Ｆ（インターフェース）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１００によってそれぞれ接続されている。

ここで、ＣＰＵ１０１は、図形検索装置の全体の制御を司る。ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。ＨＤＤ１０４は、ＣＰＵ１０１の制御にしたがってＨＤ１０５に対するデータのリード／ライトを制御する。ＨＤ１０５は、ＨＤＤ１０４の制御で書き込まれたデータを記憶する。

ＦＤＤ１０６は、ＣＰＵ１０１の制御にしたがってＦＤ１０７に対するデータのリード／ライトを制御する。ＦＤ１０７は、ＦＤＤ１０６の制御で書き込まれたデータを記憶したり、ＦＤ１０７に記憶されたデータを図形検索装置に読み取らせたりする。

また、着脱可能な記録媒体として、ＦＤ１０７のほか、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、メモリーカードなどであってもよい。ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。

Ｉ／Ｆ１０９は、通信回線を通じてインターネットなどのネットワーク１１４に接続され、このネットワーク１１４を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。

キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。

スキャナ１１２は、画像を光学的に読み取り、図形検索装置内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。

（図形画像データベース（ＤＢ）の内容）
つぎに、この発明の実施の形態にかかる図形検索装置における図形画像ＤＢについて説明する。図２は、この発明の実施の形態にかかる図形検索装置における図形画像ＤＢを示す説明図である。図２において、図形画像ＤＢ２００は、代表図形画像ＤＢ２０１と、サンプル図形画像ＤＢ２０２と、図面ＤＢ２０３と、を有している。図形画像ＤＢ２００は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５などの記録媒体により、その機能を実現する。

代表図形画像ＤＢ２０１には、各種代表図形画像が記憶されている。代表図形画像とは、たとえばボルトやナットなどの図形の基本形状をあらわす図形画像であり、種類（ジャンル）ごとに用意されている。サンプル図形画像ＤＢ２０２には、サンプル図形画像が記憶されている。サンプル図形画像とは、代表図形画像の変形例となる図形画像であり、種類（ジャンル）ごとに用意されている。また、図面ＤＢ２０３には、検索対象となる図面データが記憶されている。

図３は、代表図形画像ＤＢ２０１の記憶内容を示す説明図である。図３において、代表図形画像には固有のＩＤ：Ｒ１〜Ｒｎが振り分けられている。以下、ＩＤ：Ｒｉ（ｉ＝１〜ｎ）の代表図形画像を『代表図形画像Ｒｉ』と称す。

また、各代表図形画像Ｒｉには、それぞれ形状特徴量の種類Ｃｘ（ｘ＝ａ〜ｚ）が関連付けられている。形状特徴量とは、代表図形画像Ｒｉの色合いや形状など、代表図形画像Ｒｉ自体から抽出される数値情報である。形状特徴量の種類Ｃｘとは、形状特徴量の抽出形式を特定する情報である。

たとえば、代表図形画像Ｒ１には形状特徴量の種類Ｃａを、代表図形画像Ｒｎには形状特徴量の種類Ｃｚを用いた方がよいというように、代表図形画像Ｒｉによって異なる形状特徴量の種類Ｃｘを用いた方がよいことが経験的にわかっている場合、このような経験的に得られた情報を検索に生かすために、代表図形画像Ｒ１に対しては、検索に適した形状特徴量の種類Ｃａを、また、代表図形画像Ｒｎに対しては、検索に適した形状特徴量の種類Ｃｚが関連付けられる。なお、利用条件については、設定部６０２により設定されるため後述する。

図４は、サンプル図形画像ＤＢ２０２の記憶内容を示す説明図である。図４において、サンプル図形画像には固有のＩＤ：Ｓ１〜Ｓｍが振り分けられている。以下、ＩＤ：Ｓｊ（ｊ＝１〜ｍ）のサンプル図形画像を『サンプル図形画像Ｓｊ』と称す。

図５は、図面ＤＢ２０３の記憶内容を示す説明図である。図５において、図面データには固有のＩＤ：Ｄ１，Ｄ２，・・・が振り分けられている。たとえば、図面ＩＤ：Ｄ１の図面データは、携帯電話機の分解斜視図に関する図面データである。また、各図面データには、メタデータが関連付けられている。メタデータとしては、たとえば、図面データ内の図形の特徴を示すテキストデータが記述されている。

（図形検索装置の機能的構成）
つぎに、この発明の実施の形態にかかる図形検索装置の機能的構成について説明する。図６は、この発明の実施の形態にかかる図形検索装置の機能的構成を示すブロック図である。図６において、図形検索装置６００は、図形画像ＤＢ２００と、取得部６０１と、設定部６０２と、入力部６０３と、決定部６０４と、検索部６０５と、出力部６０６と、から構成されている。

まず、取得部６０１は、代表図形画像Ｒｉを取得する。具体的には、たとえば、図形画像ＤＢ２００内の代表図形画像ＤＢ２０１から任意の代表図形画像Ｒｉを抽出する。また、代表図形画像とともにその種類も抽出する。たとえば、代表図形画像Ｒｉとその形状特徴量の種類Ｃｘを抽出する。

また、設定部６０２は、取得部６０１によって取得された代表図形画像Ｒｉの形状特徴量の種類Ｃｘに関する利用条件を設定する。ここで、利用条件とは、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを図形検索に利用するための条件である。具体的には、形状特徴量の種類Ｃｘを用いた場合の代表図形画像Ｒｉの類似範囲を規定する条件である。

たとえば、代表図形画像Ｒｉの形状特徴量の種類Ｃｘが設定されている場合、代表図形画像Ｒｉの類似範囲を規定する条件を設定する。また、代表図形画像Ｒｉの形状特徴量の種類Ｃｘが設定されていない場合、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを設定するとともに、設定された形状特徴量の種類Ｃｘを用いた場合のクエリ図形画像Ｒｉの類似範囲を規定する条件を設定する。

いずれにしても代表図形画像Ｒｉの形状特徴量の種類Ｃｘが設定されていれば、形状特徴量の種類Ｃｘでの代表図形画像Ｒｉからのユークリッド距離区間Ｉｉ（Ｉｉ＝［０，ｄｉ］）が代表図形画像Ｒｉの類似範囲として規定される。ユークリッド距離区間Ｉｉ（Ｉｉ＝［０，ｄｉ］）は、代表図形画像Ｒｉを原点０とするため、０に近づくほど類似度が高くなる。なお、利用条件の具体的な設定手法については後述する。

また、入力部６０３は、ユーザからのクエリ図形画像Ｑの入力を受け付ける。具体的には、図１に示したキーボード１１０やマウス１１１をユーザが操作することでクエリ図形画像Ｑの入力を受け付ける。また、決定部６０４は、設定部６０２によって設定された利用条件に基づいて、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを、入力部６０３によって入力されたクエリ図形画像Ｑの形状特徴量の種類に決定する。決定部６０４による具体的な決定手法については後述する。

また、検索部６０５は、決定部６０４によって決定された形状特徴量の種類Ｃｘを用いて、クエリ図形画像Ｑに類似する図形画像を検索する。具体的には、たとえば、図面ＤＢ２０３の中から、クエリ図形画像Ｑと同一または類似する図形画像を検索する。検索手法としては、具体的には、たとえば、上述した非特許文献１に示されているように、図面データ内の図形画像の色や形状などの画像特徴量を利用する方法や、図面データに付随するメタデータを利用してテキスト特徴量を利用する方法がある。

たとえば、各図面データ内の図形画像から画像特徴量やテキスト特徴量などの特徴量を抽出し、クエリ図形画像Ｑと各図面データ内の図形画像との特徴量の類似度を算出する。この類似度により、クエリ図形画像と同一または類似の図形画像であるか否かを判断する。類似度を算出する手法として、特徴量ベクトル間の距離を測定し、距離が小さいほど類似度が高いとみなすことができる。

また、出力部６０６は、検索部６０５によって検索された検索結果を出力する。検索結果とは、具体的には、クエリ図形画像と同一または類似の図形画像や、その識別情報、メタデータなどが含まれているリスト情報である。検索結果は、図１に示したディスプレイ１０８やプリンタ１１３から出力される。

つぎに、設定部６０２の具体的な機能的構成について説明する。図７は、設定部６０２の具体的な機能的構成を示すブロック図である。図７において、設定部６０２は、サンプル図形画像類似度算出部７０１と、作成部７０２と、検索精度算出部７０３と、利用条件設定部７０４と、から構成されている。

まず、サンプル図形画像類似度算出部７０１は、画像特徴量の種類Ｃｘを用いて、代表図形画像Ｒｉとサンプル図形画像Ｓｊとの類似度を算出する。具体的には、たとえば、サンプル図形画像ＤＢ２０２からサンプル図形画像Ｓｊを順次抽出する。そして、抽出されたサンプル図形画像Ｓｊごとに、代表図形画像Ｒｉに設定されている形状特徴量の種類Ｃｘでの当該代表図形画像Ｒｉからサンプル図形画像Ｓｊまでのユークリッド距離を算出する。

たとえば、代表図形画像Ｒｉの場合、その形状特徴量の種類Ｃｘを用いて代表図形画像Ｒｉの特徴量ベクトルを生成するとともに、形状特徴量の種類Ｃｘを用いてサンプル図形画像Ｓｊの特徴量ベクトルを生成する。この生成された両特徴量ベクトルにより代表図形画像Ｒｉからサンプル図形画像Ｓｊまでのユークリッド距離を算出する。

また、作成部７０２は、算出されたユークリッド距離に関するサンプル図形画像Ｓｊの確率密度分布３００を作成する。具体的には、たとえば、図３に示した確率密度分布３００を作成する。確率密度分布３００は、横軸をユークリッド距離、縦軸をサンプル図形画像数としたグラフである。この確率密度分布３００は、図１に示したディスプレイ１０８に表示することができる。

また、検索精度算出部７０３は、検索精度を算出する。ここで、検索精度Ａｘは、形状特徴量の種類Ｃｘを用いた場合のサンプル図形画像Ｓｊに基づく検索精度である。

検索精度Ａｘは、サンプル図形画像類似度算出部７０１において、代表図形画像Ｒｉについて、代表図形画像Ｒｉに関連付けられているサンプル図形画像数をｐ、形状特徴量の種類Ｃｘを用いた場合の上位ｐ番目までのサンプル図形画像数をｑとすると、Ａｘ＝ｑ／ｐであらわすことができる。

また、利用条件設定部７０４は、サンプル図形画像類似度算出部７０１によって算出された類似度に基づいて、利用条件を設定する。具体的には、たとえば、作成部７０２によって確率密度分布３００が作成された場合、運用者がディスプレイ１０８に表示された確率密度分布３００を見ることで、任意の利用条件となるユークリッド距離区間Ｉｉ（Ｉｉ＝［０，ｄｉ］）を運用者が手動設定することができる。

また、あらかじめ所定の確率（たとえば、８０％）を設定しておき、確率密度分布３００が作成された場合、サンプル図形画像数が所定の確率以上出現すると、当該所定の確率に相当するユークリッド距離区間Ｉｉ（Ｉｉ＝［０，ｄｉ］）を利用条件に自動設定することができる。

また、利用条件設定部７０４は、代表図形画像Ｒｉについて形状特徴量の種類が設定されていない場合において、検索精度算出部７０３によって形状特徴量の種類Ｃｘごとに検索精度Ａｘが算出されたとき、代表図形画像Ｒｉについて形状特徴量の種類を、算出された検索精度Ａｘのうち最大検索精度となる形状特徴量の種類Ｃｘに設定する。

また、利用条件設定部７０４は、決定部６０４によって決定された形状特徴量の種類に関する利用条件を、第２の検索精度Ａ２に応じて変更する。具体的には、たとえば、第２の検索精度Ａ２が所定精度以下である場合、ユークリッド距離区間Ｉｉを狭くするように変更する。この変更は、運用者またはユーザの手動操作による変更でもよく、また、所定量を自動的に狭くする変更であってもよい。設定または変更された形状特徴量の種類Ｃｘは、代表図形画像ＤＢ２０１に記憶される。

つぎに、決定部６０４の具体的な機能的構成について説明する。図８は、決定部６０４の具体的な機能的構成を示すブロック図である。図８において、決定部６０４は、クエリ図形画像類似度算出部８０１と、利用条件判定部８０２と、形状特徴量種類決定部８０３と、から構成されている。

まず、クエリ図形画像類似度算出部８０１は、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを用いて、代表図形画像Ｒｉとクエリ図形画像Ｑとの類似度を算出する。具体的には、代表図形画像Ｒｉとクエリ図形画像Ｑとのユークリッド距離ｄｑを算出する。

より具体的には、たとえば、代表図形画像Ｒｉの場合、その形状特徴量の種類Ｃｘを用いて代表図形画像Ｒｉの特徴量ベクトルを生成するとともに、形状特徴量の種類Ｃｘを用いてクエリ図形画像Ｑの特徴量ベクトルを生成する。この生成された両特徴量ベクトルにより代表図形画像Ｒｉからクエリ図形画像Ｑまでのユークリッド距離ｄｑを類似度として算出する。

また、利用条件判定部８０２は、クエリ図形画像類似度算出部８０１によって算出された類似度が利用条件を満たすか否かを判定する。具体的には、たとえば、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを用いた場合の代表図形画像Ｒｉとクエリ図形画像Ｑとのユークリッド距離ｄｑが、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを用いた場合のユークリッド距離区間Ｉｉ内であるか否かを判定する。

また、形状特徴量種類決定部８０３は、利用条件判定部８０２によって判定された判定結果に基づいて、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを、クエリ図形画像Ｑの形状特徴量の種類に決定する。具体的には、たとえば、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを用いた場合の代表図形画像Ｒｉとクエリ図形画像Ｑとのユークリッド距離ｄｑが、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを用いた場合のユークリッド距離区間Ｉｉ内である場合、代表図形画像Ｒｉの形状特徴量の種類Ｃｘを、クエリ図形画像Ｑの形状特徴量の種類に決定する。

また、複数のユークリッド距離ｄｑがユークリッド距離区間Ｉｉ内に存在する場合、最も０に近いユークリッド距離ｄｑに対応する形状特徴量の種類Ｃｘを、クエリ図形画像Ｑの形状特徴量の種類に決定する。

図９は、決定部６０４による決定処理の具体例を示す説明図である。図９に示した（Ａ）では、代表図形画像Ｒ１の形状特徴量の種類Ｃａに関するユークリッド距離区間Ｉ１（Ｉ１＝［０，ｄ１］）に、形状特徴量の種類Ｃａを用いた場合のクエリ図形画像Ｑのユークリッド距離ｄ１ｑが、ユークリッド距離ｄ１よりも大きいため（ｄ１＜ｄ１ｑ）、クエリ図形画像Ｑの形状特徴量の種類としては、形状特徴量の種類Ｃａは相応しくないことがわかる。

一方、図９に示した（Ｂ）では、代表図形画像Ｒ２の形状特徴量の種類Ｃｂに関するユークリッド距離区間Ｉ２（Ｉ２＝［０，ｄ２］）に、形状特徴量の種類Ｃｂを用いた場合のクエリ図形画像Ｑのユークリッド距離ｄ２ｑが、ユークリッド距離ｄ２以下であるため（ｄ２≧ｄ２ｑ）、クエリ図形画像Ｑの形状特徴量の種類としては、形状特徴量の種類Ｃｂは相応しいことがわかる。

なお、上述した取得部６０１、設定部６０２、入力部６０３、決定部６０４、検索部６０５、および出力部６０６は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５などの記録媒体に記録されたプログラムをＣＰＵ１０１が実行することにより、またはＩ／Ｆ１０９により、その機能を実現する。

（図形検索処理手順）
つぎに、この発明の実施の形態にかかる図形検索装置６００の図形検索処理手順について説明する。図１０は、この発明の実施の形態にかかる図形検索装置６００の図形検索処理手順を示すフローチャートである。図１０において、ｉ＝１とし（ステップＳ１００１）、取得部６０１により、代表図形画像ＤＢ２０１から代表図形画像Ｒｉを抽出する（ステップＳ１００２）。そして、設定部６０２により、利用条件設定処理を実行する（ステップＳ１００３）。

このあと、ｉ＞ｎであるか否かを判断する（ステップＳ１００４）。ｉ＞ｎでない場合（ステップＳ１００４：Ｎｏ）、ｉをインクリメントして（ステップＳ１００５）、ステップＳ１００２に戻る。一方、ｉ＞ｎである場合（ステップＳ１００４：Ｙｅｓ）、入力部６０３により、クエリ図形画像Ｑが入力されたか否かを判断する（ステップＳ１００６）。

クエリ図形画像が入力されていない場合（ステップＳ１００６：Ｎｏ）、ステップＳ１０１０に移行する。一方、クエリ図形画像が入力された場合（ステップＳ１００６：Ｙｅｓ）、決定部６０４により、形状特徴量種類決定処理を実行する（ステップＳ１００７）。

このあと、検索部６０５により、図面ＤＢ２０３からクエリ図形画像と同一または類似の図形画像を検索する（ステップＳ１００８）。そして、出力部６０６により、検索結果を出力する（ステップＳ１００９）。

そのあと、図形検索を終了するか否かを判断する（ステップＳ１０１０）。図形検索を継続する場合（ステップＳ１０１０：Ｎｏ）、ステップＳ１００６に戻る。一方、図形検索を終了する場合（ステップＳ１０１０：Ｙｅｓ）、一連の図形検索処理を終了する。

つぎに、図１０に示した利用条件設定処理（ステップＳ１００３）の具体的な処理手順について説明する。図１１は、図１０に示した利用条件設定処理（ステップＳ１００３）の具体的な処理手順を示すフローチャートである。

図１１において、形状特徴量の種類の指定があったか否かを判断する（ステップＳ１１０１）。形状特徴量の種類の指定があった場合（ステップＳ１１０１：Ｙｅｓ）、サンプル図形画像類似度算出部７０１により、指定された形状特徴量の種類Ｃｘを用いて、代表図形画像Ｒｉからサンプル図形画像Ｓｊまでのユークリッド距離ｄｉを算出する（ステップＳ１１０２）。

一方、形状特徴量の種類の指定がなかった場合（ステップＳ１１０１：Ｎｏ）、形状特徴量の種類Ｃｘごとに、形状特徴量の種類Ｃｘを用いて、代表図形画像Ｒｉからサンプル図形画像Ｓｊまでのユークリッド距離ｄを算出する（ステップＳ１１０３）。そして、検索精度算出部７０３により、検索精度Ａｘを算出し（ステップＳ１１０４）、形状特徴量種類決定部８０３により、形状特徴量の種類を設定する（ステップＳ１１０５）。

ステップＳ１１０２またはＳ１１０５のあと、作成部７０２により確率密度分布３００を作成し（ステップＳ１１０６）、利用条件設定部７０４により、利用条件（ユークリッド距離区間Ｉ）を設定する（ステップＳ１１０７）。そして、図１０に示したステップＳ１００４に移行する。

つぎに、図１０に示した形状特徴量種類決定処理（ステップＳ１００７）の具体的な処理手順について説明する。図１２は、図１０に示した形状特徴量種類決定処理（ステップＳ１００７）の具体的な処理手順を示すフローチャートである。

図１２において、ｉ＝１とし（ステップＳ１２０１）、代表図形画像Ｒｉの利用条件が設定されているか否かを判断する（ステップＳ１２０２）。設定されていない場合（ステップＳ１２０２：Ｎｏ）、ステップＳ１２０６に移行する。一方、代表図形画像Ｒｉの利用条件が設定されている場合（ステップＳ１２０２：Ｙｅｓ）、クエリ図形画像類似度算出部８０１により、代表図形画像Ｒｉの形状特徴量Ｃｘを用いた場合の代表図形画像Ｒｉに対するクエリ図形画像の類似度（ユークリッド距離）を算出する（ステップＳ１２０３）。

そして、算出された類似度が利用条件を満たすか否か、すなわち、算出されたユークリッド距離ｄｉがユークリッド距離区間Ｉｉ内であるか否かを判断する（ステップＳ１２０４）。利用条件を満たさない場合（ステップＳ１２０４：Ｎｏ）、ステップＳ１２０６に移行する。

一方、利用条件を満たす場合（ステップＳ１２０４：Ｙｅｓ）、クエリ図形画像までのユークリッド距離ｄｉｑを保持する（ステップＳ１２０５）。このあと、ステップＳ１２０６において、ｉ＞ｎであるか否かを判断する。ｉ＞ｎでない場合（ステップＳ１２０６：Ｎｏ）、ｉをインクリメントして（ステップＳ１２０７）、ステップＳ１２０２に戻る。

一方、ｉ＞ｎである場合（ステップＳ１２０６：Ｙｅｓ）、形状特徴量種類決定部８０３により、保持されているユークリッド距離ｄｉｑに対応する形状特徴量の種類Ｃｘの中から、最も０に近いユークリッド距離ｄｉｑに対応する形状特徴量の種類Ｃｘを、クエリ図形画像の形状特徴量の種類に決定する（ステップＳ１２０８）。このあと、図１０に示したステップＳ１００８に移行する。

このように、上述した実施の形態では、クエリ図形画像ごとに、そのクエリ図形画像に適した形状特徴量の種類を自動設定することができる。したがって、図形検索精度の向上を図ることができる。また、ユーザが検索結果に満足せず別の形状特徴量の種類を指定して再検索するという手戻りが減少するため、ユーザによる図形検索時間の短縮化を図ることができる。

また、運用前の段階（図１０に示したステップＳ１００１〜Ｓ１００５）では、ユーザが保有する図面データの種類に応じたカスタマイズによる微調整が可能となるだけでなく、ユーザが頭に描いている類似性を図形検索装置６００に反映しやすくなるため、ユーザ環境に応じた図形検索を実現することができる。

なお、上述した実施の形態では、利用条件の設定や類似度算出において、ユークリッド距離区間Ｉｉやユークリッド距離ｄｉを用いたが、距離情報としてマンハッタン距離（区間）を用いることとしてもよい。

また、図３に示した確率密度分布３００を、確率密度関数を用いて設定することとしてもよい。たとえば、確率密度関数として正規分布を用いた場合について述べる。図１３は正規分布を示すグラフである。図１３において、符号１３００は正規分布で、平均値μと標準偏差σが決まれば記述することができる。

そこで、代表図形画像Ｒｉから各サンプル図形画像Ｓｊまでのユークリッド距離を算出し、ユークリッド距離の標準偏差を正規分布の標準偏差σとし、ユークリッド距離の平均を正規分布の平均値μとして正規分布１３００を作成する。この正規分布１３００を参考として見ながら、運用者が適当な区間を利用条件として設定する。または、代表図形画像Ｒｉの利用条件を［０,３σ］と予め固定した値を利用することとしてもよい。

以上説明したように、図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法によれば、クエリ図形画像の検索時に利用すべき最適な形状特徴量の種類を自動設定することにより、図形検索処理の高精度化および効率化を図ることができるという効果を奏する。

なお、本実施の形態で説明した図形検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。

以上のように、本発明にかかる図形検索プログラム、該プログラムを記録した記録媒体、図形検索装置、および図形検索方法は、図面検索、部品検索や、ナレッジマネジメント、ＰＬＭ（Ｐｒｏｄｕｃｔ Ｌｉｆｅｃｙｃｌｅ Ｍａｎａｇｅｍｅｎｔ）、ＰＤＭ（Ｐｒｏｄｕｃｔ Ｄａｔａ Ｍａｎａｇｅｍｅｎｔ）などの幅広い分野における画像化された図形に関するマルチメディア情報の検索に有用である。

（付記１）代表的な図形画像（以下、「代表図形画像」という）を取得させる取得工程と、
前記取得工程によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定させる設定工程と、
クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付けさせる入力工程と、
前記設定工程によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力工程によって入力されたクエリ図形画像の形状特徴量の種類に決定させる決定工程と、
前記決定工程によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索させる検索工程と、
前記検索工程によって検索された検索結果を出力させる出力工程と、
をコンピュータに実行させることを特徴とする図形検索プログラム。

（付記２）前記設定工程は、
前記形状特徴量の種類を用いて、前記代表図形画像とサンプル図形画像との類似度を算出させるサンプル図形画像類似度算出工程と、
前記サンプル図形画像類似度算出工程によって算出された類似度に基づいて、前記利用条件を設定させる利用条件設定工程と、
をコンピュータに実行させることを特徴とする付記１に記載の図形検索プログラム。

（付記３）前記サンプル図形画像類似度算出工程は、
前記代表図形画像から前記サンプル図形画像までの距離情報を算出させ、
前記利用条件設定工程は、
前記サンプル図形画像類似度算出工程によって算出された距離情報に基づいて、前記利用条件を設定させることを特徴とする付記２に記載の図形検索プログラム。

（付記４）前記距離情報に関する前記サンプル図形画像の確率密度分布を作成させる作成工程をコンピュータに実行させ、
前記利用条件設定工程は、
前記作成工程によって作成された確率密度分布に基づいて、前記利用条件を設定させることを特徴とする付記３に記載の図形検索プログラム。

（付記５）前記設定工程は、
前記検索結果に基づいて、前記検索工程による検索精度を算出させる検索精度算出工程をコンピュータに実行させ、
前記利用条件設定工程は、
前記検索精度算出工程によって算出された検索精度に基づいて、前記決定工程によって決定された形状特徴量の種類に関する利用条件を、前記検索精度に応じて変更させることを特徴とする付記１〜４のいずれか一つに記載の図形検索プログラム。

（付記６）前記決定工程は、
前記形状特徴量の種類を用いて、前記代表図形画像と前記クエリ図形画像との類似度を算出させるクエリ図形画像類似度算出工程と、
前記クエリ図形画像類似度算出工程によって算出された類似度が前記利用条件を満たすか否かを判定させる利用条件判定工程と、
前記利用条件判定工程によって判定された判定結果に基づいて、前記代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定させる形状特徴量決定工程と、
をコンピュータに実行させることを特徴とする付記１〜５のいずれか一つに記載の図形検索プログラム。

（付記７）前記クエリ図形画像類似度算出工程は、
前記代表図形画像ごとに、当該代表図形画像の形状特徴量の種類を用いて、前記クエリ図形画像との類似度を算出させ、
前記利用条件判定工程は、
前記クエリ図形画像類似度算出工程によって算出された類似度ごとに、当該類似度が前記利用条件を満たすか否かを判定させ、
前記形状特徴量決定工程は、
前記利用条件判定工程によって前記利用条件を満たすと判定された類似度が複数存在する場合、当該複数の類似度のうち最大類似度となる代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定させることを特徴とする付記６に記載の図形検索プログラム。

（付記８）前記クエリ図形画像類似度算出工程は、
前記代表図形画像から前記クエリ図形画像までの距離情報を算出させ、
前記利用条件判定工程は、
前記クエリ図形画像類似度算出工程によって算出された距離情報に基づいて、前記利用条件を満たすか否かを判定させることを特徴とする付記６に記載の図形検索プログラム。

（付記９）前記クエリ図形画像類似度算出工程は、
前記代表図形画像ごとに、当該代表図形画像の形状特徴量の種類を用いて、前記クエリ図形画像までの距離情報を算出させ、
前記利用条件判定工程は、
前記クエリ図形画像類似度算出工程によって算出された距離情報ごとに、当該距離情報が前記利用条件を満たすか否かを判定させ、
前記形状特徴量決定工程は、
前記利用条件判定工程によって前記利用条件を満たすと判定された距離情報が複数存在する場合、当該複数の距離情報のうち最小距離情報となる代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定することを特徴とする付記８に記載の図形検索プログラム。

（付記１０）付記１〜９のいずれか一つに記載の図形検索プログラムを記録したコンピュータに読み取り可能な記録媒体。

（付記１１）代表的な図形画像（以下、「代表図形画像」という）を取得する取得手段と、
前記取得手段によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定する設定手段と、
クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付ける入力手段と、
前記設定手段によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力手段によって入力されたクエリ図形画像の形状特徴量の種類に決定する決定手段と、
前記決定手段によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索する検索手段と、
前記検索手段によって検索された検索結果を出力する出力手段と、
を備えることを特徴とする図形検索装置。

（付記１２）代表的な図形画像（以下、「代表図形画像」という）を取得する取得工程と、
前記取得工程によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定する設定工程と、
クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付ける入力工程と、
前記設定工程によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力工程によって入力されたクエリ図形画像の形状特徴量の種類に決定する決定工程と、
前記決定工程によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索する検索工程と、
前記検索工程によって検索された検索結果を出力する出力工程と、
を含んだことを特徴とする図形検索方法。

この発明の実施の形態にかかる図形検索装置のハードウェア構成を示すブロック図である。 この発明の実施の形態にかかる図形検索装置における図形画像ＤＢを示す説明図である。 代表図形画像ＤＢの記憶内容を示す説明図である。 サンプル図形画像ＤＢの記憶内容を示す説明図である。 図面ＤＢの記憶内容を示す説明図である。 この発明の実施の形態にかかる図形検索装置の機能的構成を示すブロック図である。 この発明の実施の形態にかかる設定部の具体的な機能的構成を示すブロック図である。 この発明の実施の形態にかかる図形検索装置の決定部の具体的な機能的構成を示すブロック図である。 この発明の実施の形態にかかる図形検索装置の決定部による決定処理の具体例を示す説明図である。 この発明の実施の形態にかかる図形検索装置の図形検索処理手順を示すフローチャートである。 図１０に示した利用条件設定処理（ステップＳ１００３）の具体的な処理手順を示すフローチャートである。 図１０に示した形状特徴量種類決定処理（ステップＳ１００７）の具体的な処理手順を示すフローチャートである。 この発明の実施の形態にかかる図形検索装置における正規分布を示すグラフである。

符号の説明

６０１ 取得部
６０２ 設定部
６０３ 入力部
６０４ 決定部
６０５ 検索部
６０６ 出力部
７０１ サンプル図形画像類似度算出部
７０２ 作成部
７０３ 検索精度算出部
７０４ 利用条件設定部
８０１ クエリ図形画像類似度算出部
８０２ 利用条件判定部
８０３ 形状特徴量種類決定部

Claims (10)

1. 代表的な図形画像（以下、「代表図形画像」という）を取得させる取得工程と、
   前記取得工程によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定させる設定工程と、
   クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付けさせる入力工程と、
   前記設定工程によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力工程によって入力されたクエリ図形画像の形状特徴量の種類に決定させる決定工程と、
   前記決定工程によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索させる検索工程と、
   前記検索工程によって検索された検索結果を出力させる出力工程と、
   をコンピュータに実行させることを特徴とする図形検索プログラム。
2. 前記設定工程は、
   前記形状特徴量の種類を用いて、前記代表図形画像とサンプル図形画像との類似度を算出させるサンプル図形画像類似度算出工程と、
   前記サンプル図形画像類似度算出工程によって算出された類似度に基づいて、前記利用条件を設定させる利用条件設定工程と、
   をコンピュータに実行させることを特徴とする請求項１に記載の図形検索プログラム。
3. 前記サンプル図形画像類似度算出工程は、
   前記代表図形画像から前記サンプル図形画像までの距離情報を算出させ、
   前記利用条件設定工程は、
   前記サンプル図形画像類似度算出工程によって算出された距離情報に基づいて、前記利用条件を設定させることを特徴とする請求項２に記載の図形検索プログラム。
4. 前記距離情報に関する前記サンプル図形画像の確率密度分布を作成させる作成工程をコンピュータに実行させ、
   前記利用条件設定工程は、
   前記作成工程によって作成された確率密度分布に基づいて、前記利用条件を設定させることを特徴とする請求項３に記載の図形検索プログラム。
5. 前記設定工程は、
   前記検索結果に基づいて、前記検索工程による検索精度を算出させる検索精度算出工程をコンピュータに実行させ、
   前記利用条件設定工程は、
   前記検索精度算出工程によって算出された検索精度に基づいて、前記決定工程によって決定された形状特徴量の種類に関する利用条件を、前記検索精度に応じて変更させることを特徴とする請求項１〜４のいずれか一つに記載の図形検索プログラム。
6. 前記決定工程は、
   前記形状特徴量の種類を用いて、前記代表図形画像と前記クエリ図形画像との類似度を算出させるクエリ図形画像類似度算出工程と、
   前記クエリ図形画像類似度算出工程によって算出された類似度が前記利用条件を満たすか否かを判定させる利用条件判定工程と、
   前記利用条件判定工程によって判定された判定結果に基づいて、前記代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定させる形状特徴量決定工程と、
   をコンピュータに実行させることを特徴とする請求項１〜５のいずれか一つに記載の図形検索プログラム。
7. 前記クエリ図形画像類似度算出工程は、
   前記代表図形画像ごとに、当該代表図形画像の形状特徴量の種類を用いて、前記クエリ図形画像との類似度を算出させ、
   前記利用条件判定工程は、
   前記クエリ図形画像類似度算出工程によって算出された類似度ごとに、当該類似度が前記利用条件を満たすか否かを判定させ、
   前記形状特徴量決定工程は、
   前記利用条件判定工程によって前記利用条件を満たすと判定された類似度が複数存在する場合、当該複数の類似度のうち最大類似度となる代表図形画像の形状特徴量の種類を、前記クエリ図形画像の形状特徴量の種類に決定させることを特徴とする請求項６に記載の図形検索プログラム。
8. 請求項１〜７のいずれか一つに記載の図形検索プログラムを記録したコンピュータに読み取り可能な記録媒体。
9. 代表的な図形画像（以下、「代表図形画像」という）を取得する取得手段と、
   前記取得手段によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定する設定手段と、
   クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付ける入力手段と、
   前記設定手段によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力手段によって入力されたクエリ図形画像の形状特徴量の種類に決定する決定手段と、
   前記決定手段によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索する検索手段と、
   前記検索手段によって検索された検索結果を出力する出力手段と、
   を備えることを特徴とする図形検索装置。
10. 代表的な図形画像（以下、「代表図形画像」という）を取得する取得工程と、
    前記取得工程によって取得された代表図形画像の形状特徴量の種類に関する利用条件を設定する設定工程と、
    クエリとなる図形画像（以下、「クエリ図形画像」という）の入力を受け付ける入力工程と、
    前記設定工程によって設定された利用条件に基づいて、前記代表図形画像の形状特徴量の種類を、前記入力工程によって入力されたクエリ図形画像の形状特徴量の種類に決定する決定工程と、
    前記決定工程によって決定された形状特徴量の種類を用いて、前記クエリ図形画像と同一または類似の図形画像を検索する検索工程と、
    前記検索工程によって検索された検索結果を出力する出力工程と、
    を含んだことを特徴とする図形検索方法。
    
    

Images