(57)【要約】【課題】  画像パターンに基づき類似する画像をデータベースから検索する際に、幾何学的変換によらず、かつ十分な識別性能を有すると共に、少ない計算量で識別・検索を行う。【解決手段】  本発明は、提示直線パターンを構成する直線のパラメータ集合を取得し、直線パラメータ集合から可能な全ての二直線が成す交点座標とその交差角を算出する交点・交差角を算出し、各々の交点を基準点として該基準点から直線パラメータ集合中の各直線までの距離を算出し、各々の二直線距離比の関数値からなる距離不変量とその二直線が成す交差角の対を直線不変量対として算出し、各交点に対する全ての直線不変量対及び該交点の交差角を一つの不変量セットＸとして該パターンの識別子と共にＤＢに格納し、ＤＢの不変量セットＹと不変量セットＸを照合することでその類似性スコアを算出し、スコアを判定して類似している場合には不変量セットＹの識別子を識別結果として出力する。【選択図】  図１
2006163916.tif 000002
【特許請求の範囲】
【請求項１】
複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別方法において、
パターンを構成する直線のパラメータ集合を取得する直線パラメータ取得手順と、
前記直線パラメータ集合から可能な全ての二直線が成す交点座標とその交差角を算出する交点・交差角算出手順と、
前記交点・交差角算出手順により得られる各々の交点を基準点として、その基準点から前記直線パラメータ集合中の各直線までの距離を算出する距離算出手順と、
前記距離算出手順により得られる各々の二直線距離比の関数値からなる距離不変量と、その二直線が成す交差角の対を直線不変量対として算出する不変量算出手順と、
前記不変量算出手順により得られる各交点に対する全ての直線不変量対及び該交点の交差角を一つの不変量セットとする不変量セット作成手順と、
前記不変量セットＸの該パターンの識別子と共にデータベースに格納する不変量セット格納手順と、
前記データベースから格納された任意のパターンに対する不変量セットＹを取得する不変量セット取得手順と、
前記不変量セットＸ及びＹを照合することで、その類似性スコアを算出する不変量セット照合手順と、
前記スコアを判定し、類似している場合には不変量セットＹの識別子を識別結果として出力する識別結果出力手順と、
更に他の不変量セットに対して識別処理を行うかどうかを判定する識別判定手順と、
を行うことを特徴とする直線パターン識別方法。
【請求項２】
前記不変量セット照合手順において、
前記不変量セットＸ及びＹにおける交点の交差角を取得する交差角取得手順と、
前記交差角取得手順により得られる各々の交差角を比較し照合の是非を決定する交差角比較手順と、
前記交差角比較手順により照合が実施される場合に、前記不変量セットＸ及びＹにおける直線不変量対を照合する直線不変量対照合手順と、
を行う請求項１記載の直線パターン識別方法。
【請求項３】
前記不変量セット作成手順において、
全ての直線不変量対をヒストグラム化するためのマトリクスを生成するマトリクス生成手順と、
各直線不変量対から加算すべきマトリクス上の位置を算出するインデクス算出手順と、
前記インデクス算出手順により得られるマトリクスの位置に投票値を加算するマトリクス投票手順と、
前記マトリクス投票手順により得られるマトリクスヒストグラムと交差角を一つの不変量セットとする不変量ヒストグラムセット作成手順と、
を行い、
前記直線不変量対照合手順において、
不変量セットにおけるマトリクスヒストグラムを照合するマトリクスヒストグラム照合手順と、
前記マトリクスヒストグラム照合手順により得られる照合スコアに基づいて類似性スコアを算出する類似性スコア算出手順と、
を行う請求項２記載の直線パターン識別方法。
【請求項４】
複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別装置であって、
パターンを構成する直線のパラメータ集合を取得する直線パラメータ取得手段と、
前記直線パラメータ集合から可能な全ての二直線が成す交点座標とその交差角を算出する交点・交差角算出手段と、
前記交点・交差角算出手段により得られる各々の交点を基準点として、その基準点から前記直線パラメータ集合中の各直線までの距離を算出する距離算出手段と、
前記距離算出手段により得られる各々の二直線距離比の関数値からなる距離不変量と、その二直線が成す交差角の対を直線不変量対として算出する不変量算出手段と、
前記不変量算出手段により得られる各交点に対する全ての直線不変量対及び該交点の交差角を一つの不変量セットとする不変量セット作成手段と、
前記不変量セットＸを該パターンの識別子と共に格納する不変量セットデータベースと、
前記不変量セット作成手段から得られるユーザ提示の不変量セットＸを、前記不変量データベースからえら得る任意のパターンに対する不変量セットＹと照合することで、その類似性スコアを算出する不変量セット照合手段と、
前記スコアを判定し、類似している場合には不変量セットＹの識別子を識別結果として出力する識別結果出力手段と、
を有することを特徴とする直線パターン識別装置。
【請求項５】
前記不変量セット照合手段は、
前記不変量セットＸ及びＹにおける交点の交差角を取得する交差角取得手段と、
前記交差角取得手段により得られる各々の交差角を比較し照合の是非を決定する交差角比較手段と、
前記交差角比較手段により照合が実施される場合に、前記不変量セットＸ及びＹにおける直線不変量対を照合する直線不変量対照合手段と、
を有する請求項４記載の直線パターン識別装置。
【請求項６】
前記不変量セット作成手段は、
全ての直線不変量対をヒストグラム化するためのマトリクスを生成するマトリクス生成手段と、
各直線不変量対から加算すべきマトリクス上の位置を算出するインデクス算出手段と、
前記インデクス算出手段により得られるマトリクスうえの位置に投票値を加算するマトリクス投票手段と、
前記マトリクス投票手段により得られるマトリクスヒストグラムと交差角を一つの不変量セットとする不変量ヒストグラムセット作成手段と、を有し、
前記直線不変量対照合手段は、
不変量セットにおけるマトリクスヒストグラムを照合するマトリクスヒストグラム照合手段と、
前記マトリクスヒストグラム照合手段により得られる照合スコアに基づいて類似性スコアを算出する類似性スコア算出手段と、
を有することを特徴とする直線パターン識別装置。
【請求項７】
複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別プログラムであって、
請求項１乃至３記載の直線パターン識別方法を実現するための処理をコンピュータに実行させることを特徴とする直線パターン識別プログラム。
【請求項８】
複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別プログラムを格納した記憶媒体であって、
請求項１乃至３記載の直線パターン識別方法を実現するための処理をコンピュータに実行させることを特徴とする直線パターン識別プログラムを格納した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、直線パターン識別方法及び装置及びプログラムに係り、特に、画像を蓄積したデータベースからユーザが提示した画像パターンに基づき類似する画像を検索する場合に用いられる画像の識別技術に係り、拡大縮小・回転・平行移動などの幾何学的変換によらず画像内の直線を用いて類似画像を検索する直線パターンによる識別方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
従来の画像検索システムは、予めデータベースに蓄積された画像データに対してその画像を記述するパラメータとしての関連情報を付与し、そのキーワードを用いたキーワード検索により実現されている。しかし、この検索における問題点の一つに、上記のメタデータが必ずしも画像内容を十分に表現しているとは限らない点をあげることができる。即ち、あるオペレータにより付与されたキーワードは、必ずしもユーザが想起するキーワードと一致しないことが起こり得るわけである。この問題を解決するための一つの手法に、キーワードではなく画像データが保有する、もしくは、保有すると想定される特徴量を提示することで検索を行う、類似画像検索がある。この場合は、オペレータやユーザによる主観が入らないため、常に同じ検索処理が期待される。しかし、その一方で、どのような特徴量を用いるか、検索時にユーザはその特徴量をどのように求め、提示するのか、どのように照合を行うのかなどの技術課題が発生する。
【０００３】
類似画像検索における特徴量提示の一手法としては、ユーザが画像自身もしくは画像が持つ特徴的な形状パターンを提示することによって検索する手法が考えられ、これまでに様々な方法が考えられている（例えば、非特許文献１参照）。
【０００４】
このとき重要となるのは、ユーザが提示する画像・パターンとデータベース内に存在する該当画像との間に存在する、拡大縮小・回転・平行移動などの幾何学的変換や特徴量の誤差・不一致によらず、正しく検索が行われることである。このような検索を実現するための識別技術の一つとして、画像特徴点から幾何学的不変量を算出・照合することで識別を実現する、ジオメトリックハッシング法（Geometric Hashing）がある（例えば、非特許文献２参照）。ジオメトリックハッシング法は、幾何学的変換に対する不変量を画像から抽出される特徴点などのパラメータから算出してハッシュテーブルに登録することでその形状を表現し、検索キーとしての画像・パターンに対しても同じ不変量を算出してハッシュテーブルに投票を行い、モデルのハッシュテーブルと投票数を比較することで幾何学的変換に対して不変な識別を行うものである。
【０００５】
ジオメトリックハッシング法は、幾何学的変換によらない識別・検索を可能とするが、画像から抽出された特徴点を用いる場合、画像への重畳ノイズなどに起因する抽出誤りにより識別性能が低下する問題がある。そこで、ノイズに対して安定したパラメータ検出が可能なハフ変換（特許文献１参照）などを用いた直線パラメータにより同様の識別を行う方法がある。この方法には、以下のような種々の方法がある。
【０００６】
１つは、画像の縦横比と直線の傾きから直線の配置を正規化することで特徴量を抽出する方法である（例えば、特許文献２参照）。
【０００７】
また、画像内の直線特徴ベクトルを抽出し、その特徴ベクトルの類似性に基づいて識別を行う方法がある（例えば、特許文献３参照）。
【０００８】
また、前述のジオメトリックハッシング法を用い、不変量算出のための特徴量として直線パラメータを用いる方法である（例えば、非特許文献３参照）。
【０００９】
また、２直線間の角度を不変量として用いることで識別を行う方法である（例えば、非特許文献４参照）。
【特許文献１】P.V.C. Hough: ”Method and Means for Recognizing Complex Patterns”, U.S. Patent, 3069654, 1962
【特許文献２】特許第３４４８２１７号「直線による画像の検索方法、検索装置及びそのプログラム記憶媒体」
【特許文献３】特許第３５１０９８０「直線による画像の検索装置、検索方法及びそのプログラム記憶媒体」
【非特許文献１】串間他「色や形状等の表層的特徴量に基づく画像内容検索技術」、情報処理学会論文誌、データベース、Vol.40, SIG3(TOD1),pp. 177-184, 1999
【非特許文献２】Y. Lamdan and H. J. Wolfson: “Geometric Hashing: a general and efficient model-based recognition scheme”, International Conference on Computer Vision (ICCV)”, pp. 238-249, 1998
【非特許文献３】F. C. D. Tsai:”A Probabilistic Approach to Geometric Hashing Using Lione Features”, Computer Vision and Image Understanding, Vol.63, No.1, pp. 182-195, 1996
【非特許文献４】P. Franti et.al:”Hough Transform for Rotation Invariant Matching of Line-Drawing images”, International Conference on Pattern Recognition  (ICPR), pp. 389-392, 2000
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記の従来の類似画像識別・検索技術には、次のような問題点がある。
【００１１】
まず、従来の直線パラメータによる類似画像識別方法における、画像の縦横比と直線の傾きから直線の配置を正規化することで特徴量を抽出する方法（例えば、特許文献２）は、画像内に描画された内容が回転・平行移動された後に画像として再配置されるような場合には、本方法による正規化では同じ特徴量が得られず、識別されないという問題がある。
【００１２】
また、従来の直線パラメータによる類似画像識別方法における、画像内の直線特徴ベクトルを抽出し、その特徴ベクトルの類似性に基づいて識別を行う方法（例えば、特許文献３）では、特徴ベクトルは、幾何学的変換により容易にその値が変化するため（回転によりベクトルの傾きが、平行移動により座標位置が、拡大縮小により長さが変化する）、幾何学的変換を受けた画像の識別ができなくなるという問題が存在する。
【００１３】
また、従来のジオメトリックハッシング法を用い、不変量算出のための特徴量として直線パラメータを用いる方法（例えば、非特許文献３）は、幾何学的変換に対する不変量を算出し、識別に用いることで、幾何学的変換に対する識別保証することができる。しかし、例えば、回転・拡大縮小・平行移動の幾何学的変換（すなわち、相似変換）に対する不変量を算出するためには、３直線を用いて基底を得る必要がある。画像内の直線パラメータ数をＮとすると、本方法における基底算出にはＮの3乗オーダという膨大な計算量を要するという問題が存在する。
【００１４】
また、従来の２直線間の角度を不変量として用いることで識別を行う方法（例えば、非特許文献４）は、Ｎの2乗オーダ程度の計算回数で不変量を得ることができるが、角度情報だけでは十分な識別能力を得ることができないという問題が存在する。
【００１５】
本発明は、上記の点に鑑みなされたもので、幾何学的変換によらずかつ十分な識別性能を有する特徴量を提供すると共に、少ない計算量で識別・検索を可能とする直線パターン識別方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
図１は、本発明の原理を説明するための図である。
【００１７】
請求項１の発明は、複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別方法において、
パターンを構成する直線のパラメータ集合を取得する直線パラメータ取得手順（ステップ１）と、
直線パラメータ集合から可能な全ての二直線が成す交点座標とその交差角を算出する交点・交差角算出手順（ステップ２）と、
交点・交差角算出手順（ステップ２）により得られる各々の交点を基準点として、その基準点から直線パラメータ集合中の各直線までの距離を算出する距離算出手順（ステップ３）と、
距離算出手順（ステップ３）により得られる各々の二直線距離比の関数値からなる距離不変量と、その二直線が成す交差角の対を直線不変量対として算出する不変量算出手順（ステップ４）と、
不変量算出手順（ステップ４）により得られる各交点に対する全ての直線不変量対及び該交点の交差角を一つの不変量セットとする不変量セット作成手順（ステップ５）と、
不変量セットＸの該パターンの識別子と共にデータベースに格納する不変量セット格納手順（ステップ６）と、
データベースから格納された任意のパターンに対する不変量セットＹを取得する不変量セット取得手順（ステップ７）と、
不変量セットＸ及びＹを照合することで、その類似性スコアを算出する不変量セット照合手順（ステップ８）と、
スコアを判定し、類似している場合には不変量セットＹの識別子を識別結果として出力する識別結果出力手順（ステップ９）と、
更に他の不変量セットに対して識別処理を行うかどうかを判定する識別判定手順（ステップ１０）と、を行う。
【００１８】
また、請求項２の発明は不変量セット照合手順（ステップ８）において、
不変量セットＸ及びＹにおける交点の交差角を取得する交差角取得手順と、
交差角取得手順により得られる各々の交差角を比較し照合の是非を決定する交差角比較手順と、
交差角比較手順により照合が実施される場合に、不変量セットＸ及びＹにおける直線不変量対を照合する直線不変量対照合手順と、を行う。
【００１９】
また、請求項３の発明は、不変量セット作成手順（ステップ５）において、
全ての直線不変量対をヒストグラム化するためのマトリクスを生成するマトリクス生成手順と、
各直線不変量対から加算すべきマトリクス上の位置を算出するインデクス算出手順と、
インデクス算出手順により得られるマトリクスの位置に投票値を加算するマトリクス投票手順と、
マトリクス投票手順により得られるマトリクスヒストグラムと交差角を一つの不変量セットとする不変量ヒストグラムセット作成手順と、
を行い、
直線不変量対照合手順において、
不変量セットにおけるマトリクスヒストグラムを照合するマトリクスヒストグラム照合手順と、
マトリクスヒストグラム照合手順により得られる照合スコアに基づいて類似性スコアを算出する類似性スコア算出手順と、を行う。
【００２０】
図２は、本発明の原理構成図である。
【００２１】
請求項４の発明は、複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別装置であって、
パターンを構成する直線のパラメータ集合を取得する直線パラメータ取得手段１１と、
直線パラメータ集合から可能な全ての二直線が成す交点座標とその交差角を算出する交点・交差角算出手段１２と、
交点・交差角算出手段１２により得られる各々の交点を基準点として、その基準点から直線パラメータ集合中の各直線までの距離を算出する距離算出手段１３と、
距離算出手段１３により得られる各々の二直線距離比の関数値からなる距離不変量と、その二直線が成す交差角の対を直線不変量対として算出する不変量算出手段１４と、
不変量算出手段１４により得られる各交点に対する全ての直線不変量対及び該交点の交差角を一つの不変量セットとする不変量セット作成手段１５と、
不変量セットＸを該パターンの識別子と共に格納する不変量セットデータベース１６と、
不変量セット作成手段１５から得られるユーザ提示の不変量セットＸを、不変量データベース１６から得られる任意のパターンに対する不変量セットＹと照合することで、その類似性スコアを算出する不変量セット照合手段１７と、
スコアを判定し、類似している場合には不変量セットＹの識別子を識別結果として出力する識別結果出力手段１８と、を有する。
【００２２】
請求項５の発明における直線パターン識別装置１の不変量セット照合手段１７は、
不変量セットＸ及びＹにおける交点の交差角を取得する交差角取得手段と、
交差角取得手段により得られる各々の交差角を比較し照合の是非を決定する交差角比較手段と、
交差角比較手段により照合が実施される場合に、不変量セットＸ及びＹにおける直線不変量対を照合する直線不変量対照合手段と、を有する。
【００２３】
請求項６における直線パターン識別装置１の不変量セット作成手段１５は、
全ての直線不変量対をヒストグラム化するためのマトリクスを生成するマトリクス生成手段と、
各直線不変量対から加算すべきマトリクス上の位置を算出するインデクス算出手段と、
インデクス算出手段により得られるマトリクスうえの位置に投票値を加算するマトリクス投票手段と、
マトリクス投票手段により得られるマトリクスヒストグラムと交差角を一つの不変量セットとする不変量ヒストグラムセット作成手段と、を有し、
直線不変量対照合手段は、
不変量セットにおけるマトリクスヒストグラムを照合するマトリクスヒストグラム照合手段と、
マトリクスヒストグラム照合手段により得られる照合スコアに基づいて類似性スコアを算出する類似性スコア算出手段と、を有する。
【００２４】
請求項７の発明は、複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別プログラムであって、
請求項１乃至３記載の直線パターン識別方法を実現するための処理をコンピュータに実行させるプログラムである。
【００２５】
請求項８の発明は、複数の直線が描画されている直線パターンの画像を蓄積したデータベースから、ユーザが提示する直線パターンと類似したパターンを含む画像を幾何学的変換によらず識別・検索する直線パターン識別プログラムを格納した記憶媒体であって、
請求項１乃至３記載の直線パターン識別方法を実現するための処理をコンピュータに実行させる直線パターン識別プログラムを格納した記憶媒体である。
【発明の効果】
【００２６】
上記のように、本発明によれば、幾何学的変換によらず、かつ、十分な識別性能を有する特徴量を提供すると共に、少ない計算量で識別・検索を可能とすることができる。
【発明を実施するための最良の形態】
【００２７】
以下、図面と共に本発明の実施の形態を説明する。
【００２８】
図３は、本発明の一実施の形態における直線パターン識別装置の構成を示す。同図に示す直線パターン識別装置１は、直線パラメータ取得部１１、交点・交差角算出部１２、距離算出部１３、不変量算出部１４、不変量セット作成部１５、不変量セットデータベース１６、不変量セット照合部１７、識別結果出力部１８から構成される。
【００２９】
直線パラメータ取得部１１は、ユーザが提示する直線パターンから、そのパターンを構成する直線のパラメータ集合を取得する。
【００３０】
交点・交差角算出部１２は、直線パラメータ取得部１１により得られる直線パラメータ集合から、可能な全ての２直線が成す交点座標とその交差角を算出する。
【００３１】
距離算出部１３は、交点・交差角算出部１２により得られる各々の交点を基準点として、その基準点から直線パラメータ取得部１１により得られる直線パラメータ集合中の各直線までの距離を算出する。
【００３２】
不変量算出部１４は、距離算出部１３により得られる各々二直線距離の組み合わせに対し、その距離比を算出し、更に与えられた関数式に従って距離比の間数値を算出して距離不変量とし、更に該当する二直線が成す交差角を交点・交差角算出部１２より取得し、距離不変量と交差角の対を直線不変量対として算出する。
【００３３】
不変量セット作成部１５は、不変量算出部１４により得られた各基準点に対するすべての直線不変量対と、交点・交差角算出部１２により得られるその基準点の交差角を、一つの不変量セットとして作成する。
【００３４】
不変量セットデータベース１６は、不変量セット作成部１５からの不変量セットを、その不変量が属する直線パターンの識別子と共に格納する。
【００３５】
不変量セット照合部１７は、ユーザ提示の直線パターンから得られる不変量セットＸを、不変量セットデータベース１６から得られる任意のパターンに対する不変量セットＹと照合することで、その類似性スコアを算出する。
【００３６】
識別結果出力部１８は、不変量セット照合部１７から得られるスコアを判定し、類似している場合には不変量セットＹの識別子を識別結果として出力する。
【００３７】
図４は、本発明の一実施の形態における直線パラメータと直線不変量対の関係概念図を示し、図５は、本発明の一実施の形態における不変量セットの概念図を示す。また、図６は、本発明の一実施の形態における不変量セット照合を説明するための図である。
【００３８】
図４に示すように、二直線のパラメータに対し、別の二直線から得られる交点Ｃｘｙを基準点として距離比関数値と交差角を算出することで直線不変量対を算出する。これにより、拡大縮小・回転・平行移動の相似変換に対して不変な特徴量としての不変量セットを得ることができる。直線パラメータ数をＮとすると、基底数に相当する交点数は、Ｎの２乗オーダとなり、少ない計算量での識別が可能となる。また、図５に示すように二直線間の交差角ｔに加え、二直線距離比の関数値としての距離不変量ｒを用いることで、より高い識別性能を有する特徴量としての不変量セットを得ることが可能となる。また、図６に示すように、各基準点に対するすべての直線不変量を一つの不変量セットとして照合することで、幾何学的変換や特徴量の誤差・不一致を許容できる識別が可能となる。
【００３９】
次に、不変量セット照合部１７について説明する。
【００４０】
図７は、本発明の一実施の形態における不変量セット照合部の構成を示す。同図に示す不変量セット照合部１７は、交差角取得部２１、交差角比較部２２、直線不変量対照合部２３から構成される。
【００４１】
交差角取得部２１は、不変量セット作成部15から得られる不変量セットＸ及び不変量セットでデータベース１６から得られる不変量セットＹにおける、それぞれの基準点の交差角を取得する。
【００４２】
交差角比較部２２は、交差角取得部２１により得られる各々の交差角を比較し、その交差角がほぼ同一であるか否かを決定する。
【００４３】
直線不変量対照合部２３は、交差角比較部２２により交差角がほぼ同一であるとされた場合、不変量セットＸ及びＹから直線不変量対の集合を取り出し、その照合を行って類似性スコアを算出する。
【００４４】
図８は、本発明の一実施の形態における交差角比較を説明するための図である。図8に示すように、予め基準点間の交差角を比較することで、照合すべき不変量セットを取捨選択することができる。これにより、より少ない計算量での識別が可能となる。
【００４５】
次に、不変量セット作成部１５及び直線不変量対照合部２３について説明する。
【００４６】
図９は、本発明の一実施の形態における不変量セット作成部及び直線不変量対照合部の構成を示す。同図に示す不変量セット作成部１５は、マトリクス生成部３１、インデクス算出部３２、マトリクス投票部３３、不変量ヒストグラムセット作成部３４から構成される。
【００４７】
マトリクス生成部３１は、不変量算出部14より得られる各基準点に対するすべての直線不変量対をヒストグラム化するためのマトリクスを生成する。
【００４８】
インデクス算出部３２は、不変量算出部１４により得られる各基準点に対する各々の直線不変量対から、加算すべきマトリクス上の位置を算出する。
【００４９】
マトリクス投票部３３は、インデクス算出部32により得られるマトリクス上の位置に対し、投票値を加算する。
【００５０】
不変量ヒストグラムセット作成部３４は、マトリクス投票部３３により得られるマトリクス上のヒストグラムと、交点・交差角算出部１２により得られる基準点の交差角を、一つの不変量ヒストグラムセットとして作成する。
【００５１】
同図に示す直線不変量対照合部２３は、マトリクスヒストグラム照合部３５、類似性スコア算出部３６から構成される。
【００５２】
マトリクスヒストグラム照合部３５は、不変量セットにおけるマトリクスヒストグラムを照合して照合スコアを算出する。
【００５３】
類似性スコア算出部３６は、マトリクスヒストグラム照合部３５により得られる照合スコアに基づいて類似性スコアを算出する。
【００５４】
図１０は、本発明の一実施の形態におけるマトリクスヒストグラム照合を説明するための図である。直線パラメータ数をＮとすると、直線不変量対の総数は、Ｎの２乗オーダとなり、直線不変量対の照合回数も同じオーダとなる。同図に示すように、すべての直線不変量対をマトリクス上の該当位置におけるヒストグラム値として格納することにより、その照合回数はマトリクスのセル数となり、直線パラメータ数によらない定数オーダとなる。これにより、更に少ない計算量での識別が可能となる。
【００５５】
次に、直線パターン識別情報をユーザに提供する方法について説明する。
【００５６】
図１１は、本発明の一実施の形態における直線パターン識別方法のフローチャートである。
【００５７】
直線パラメータ取得部１１は、ユーザが提示する直線パターンから、そのパターンを構成する直線のパラメータ集合を取得する（ステップ１０１）。
【００５８】
交点・交差角算出部１２は、取得した直線パラメータ集合から、可能なすべての二直線が成す交点座標とその交差角を算出する（ステップ１０２）。
【００５９】
距離算出部１３は、ステップ１０２により得られる各々の交点を基準点として、その基準点からステップ１０１で得られる直線パラメータ集合中の各直線までの距離を算出する（ステップ１０３）。
【００６０】
不変量算出部１４は、ステップ１０３により得られる各直線への距離を用い、与えられた関数式に従って各々の二直線距離の組み合わせに対する距離比の関数値を算出して距離不変量とし、ステップ１０２において既に得られている該当する二直線が成す交差角と対にすることで、直線不変量対を算出する（ステップ１０４）。
【００６１】
不変量セット作成部１５は、ステップ１０４により得られる、各基準点に対するすべての直線不変量対及び該基準点の交差角を一つの不変量セットとする（ステップ１０５）。
【００６２】
不変量セット作成部１５は、ステップ１０５により得られるすべての不変量セットＸを、その不変量セットが属する直線パターンの識別子と共に不変量セットデータベース１６に格納する（ステップ１０６）。
【００６３】
不変量セット照合部１７は、不変量セットデータベース１６に格納された任意のパターンに対する不変量セットＹを取得する（ステップ１０７）。
【００６４】
不変量セット照合部１７は、ユーザにより提示された直線パターンから得られる不変量セットＸを、ステップ１０７により得られる不変量セットＹと照合することで、その類似性スコアＳを算出する（ステップ１０８）。
【００６５】
識別結果出力部１８は、ステップ１０８により得られるスコアＳを判定し（ステップ１０９）、不変量セットＸ及びＹが類似していると判定される場合には、不変量セットＹの識別子を識別結果として出力する（ステップ１１０）。
【００６６】
更に、他の不変量セットに対して識別処理を行うかどうかを判定する（ステップ１１１）。
【００６７】
次に、上記のステップ１０８における、ある不変量セットＸ及びＹの照合を行う際に、その照合処理の要否を判定することで照合を的確に実施し、計算量を削減する方法を説明する。
【００６８】
図１２は、本発明の一実施の形態における不変量セット照合方法のフローチャートである。
【００６９】
不変量セット照合部１７の交差角取得部２１は、不変量セット作成部１５から得られる不変量セットＸと、不変量セットデータベース１６より得られる不変量セットＹにおける、それぞれの基準点の交差角を取得する（ステップ２０１）。
【００７０】
交差角比較部２２において、各々の交差角を比較し、その交差角がほぼ同一であるか否かを決定する（ステップ２０２）。
【００７１】
直線不変量対照合部２３は、交差角がほぼ同一であるとされた場合、不変量セットＸ及びＹから直線不変量対の集合を取り出し、その照合を行って類似性スコアＳを算出する（ステップ２０３）。
【００７２】
上記のステップ１０５及びステップ２０３における、直線不変量対集合の生成及び照合を行う際に、マトリクスヒストグラムを用いることで、計算量を削減する方法を説明する。
【００７３】
図１３は、本発明の一実施の形態における不変量セット生成方法の詳細な処理のフローチャートである。
【００７４】
不変量セット生成部１５のマトリクス生成部３１は、不変量算出部１４により得られる、各基準点に対するすべての直線不変量対をヒストグラム化するためのマトリクスを初期生成する（ステップ３０１）。
【００７５】
インデクス算出部３２は、不変量算出部１４により得られる、各基準点に対する各々の直線不変量対から、加算すべきマトリクス上の位置を算出する（ステップ３０２）。
【００７６】
マトリクス投票部３３は、ステップ３０２により得られる各々の直線不変量対に対応するマトリクス上の位置に対し、与えられた投票値を加算する（ステップ３０３）。
【００７７】
不変量ヒストグラムセット作成部３４は、ステップ３０３により得られるマトリクス上のヒストグラムと、交点・交差角算出部１２により得られる基準点の交差角を、一つの不変量ヒストグラムセットとして作成する（ステップ３０４）。
【００７８】
図１４は、本発明の一実施の形態における直線不変量対照合方法のフローチャートである。
【００７９】
直線不変量対照合部２３のマトリクスヒストグラム照合部３５は、不変量ヒストグラムセットＸ及びＹからマトリクスヒストグラムを取り出し照合することで、その照合スコアＭを算出する（ステップ３０５）。
【００８０】
類似性スコア算出部３６において、ステップ３０５により得られる照合スコアＭに基づいて類似性スコアＳを算出する（ステップ３０６）。
【実施例】
【００８１】
以下、図面と共に本発明の実施例を説明する。
【００８２】
［第１の実施例］
図１５は、本発明の第１の実施例によるシステム構成図である。
【００８３】
同図におけるデータとしては、画像を対象としている。ユーザは識別対象となる画像を提示し、その画像に類似していると判定された登録済画像の識別子を、その識別結果として受け取る。
【００８４】
また、本システムでの直線パターンは、画像における主要直線成分を検出することにより得られ、検出された直線パラメータの集合を当該画像の直線パターンと規定する。
【００８５】
同図に示すシステムは、ユーザ側のクライアント装置１００と、サービス提供者側のサーバ装置２００とを有する。
【００８６】
サーバ装置２００には、複数のクライアント装置１００が接続され得る。また、各装置間は同一ＬＡＮで接続されていても、異種ＷＡＮで接続されていてもよい。
【００８７】
クライアント装置１００は、直線パラメータ取得部１１１、直線パラメータファイル１１２、直線パラメータ送信部１１３、識別子受信部１１４、及び、利用者インタフェース１１５から構成される。
【００８８】
直線パラメータ取得部１１１は、利用者インタフェース１１５から対象となる画像を受け取り、直線検出処理により画像中の主要直線パラメータを検出し、その直線パラメータ集合を出力する。
【００８９】
直線パラメータファイル１１２は、直線パラメータ取得部１１１が出力した直線パラメータ集合を直線パターンとしてファイル化したものである。なお、その実現方法としては、どのようなファイル形式であってもよく、また、データベース中の１項目としてクライアント装置１００に格納されていてもよい。
【００９０】
直線パラメータ送信部１１３は、直線パラメータファイル１１２の記述内容をサーバ２００に送信する。
【００９１】
識別子受信部１１４は、サーバ装置２００から、提示した画像に類似していると判定された画像を表す識別子を受信する。
【００９２】
利用者インタフェース１１５は、ユーザが画像を転送する。また、同インタフェースは、識別子受信部１１４が受信した識別子をユーザに表示する。なお、この識別子に基づいて該当画像及びその関連情報を表示するシステムを構成することが別途実現可能である。
【００９３】
サーバ装置２００は、直線パラメータ受信部２１１、交点・交差角算出部２１２、距離算出部２１３、不変量算出部２１４、マトリクス生成部２１５、インデクス算出部２１６、マトリクス投票部２１７、不変量ヒストグラムセット作成部２１８、不変量セットデータベース２１９、交差角取得部２２０、交差角比較部２２１、マトリクスヒストグラム照合部２２２、類似性スコア算出部２２３、類似性判定部２２４、識別子送信部２２５から構成される。
【００９４】
直線パラメータ受信部２１１は、クライアント装置１００により送信された直線パラメータファイル１１２の記述内容である直線パラメータ集合を受信し、交点・交差角算出部２１２及び距離算出部２１３へ転送する。
【００９５】
交点・交差角算出部２１２は、クライアント装置１００から送信された直線パラメータ集合の受信を識別処理開始要求と見なし、直線パラメータ集合の中で可能なすべての二直線がなす交点座標とその交点角を算出する。
【００９６】
距離算出部２１３は、交点・交差角算出部２１２により得られる各々の交点を基準点として、その基準点から直線パラメータ集合中の各直線までの距離を算出する。距離算出は、各々の基準点に対して行われる。
【００９７】
不変量算出部２１４は、距離算出部２１３により得られる各直線への距離を用い、予め与えられた関数式に従って各々の二直線距離の組み合わせに対する距離比の関数値を算出して距離不変量を算出すると同時に、交点・交差角算出部２１２において既に得られている該当する二直線が成す交差角と対にすることで、直線不変量対を算出する。
【００９８】
マトリクス生成部２１５は、不変量算出部２１４により各基準点に対するすべての直線不変量対が算出された時点で処理を開始し、すべての直線不変量対をヒストグラム化するためのマトリクスを生成・初期化する。
【００９９】
インデクス算出部２１６は、各基準点に対する各々の直線不変量対から、加算すべきマトリクス上の位置を算出する。
【０１００】
マトリクス投票部２１７は、インデクス算出部２１６により得られる各々の直線不変量対に対応するマトリクス上の位置に対し、与えられた投票値を加算する。
【０１０１】
不変量ヒストグラムセット作成部２１８は、マトリクス投票部２１７によりすべての直線不変量対に対する投票が終了した時点で処理を開始し、マトリクス上のヒストグラムデータと、交点・交差角算出部２１２により得られる基準点の交差角を、一つの不変量ヒストグラムセットとして作成する。
【０１０２】
不変量データベース２１９は、不変量ヒストグラムセット作成部２１８において作成された不変量セットＸを、識別対象とした画像の識別子と共に格納すると同時に、交差角取得部２２０からのリクエストを待ち受ける。不変量セットデータベース２１９は、既存のデータベース製品により実現することも可能であり、また、不変量セット毎のファイルを格納することで実現することも、１つのファイル内の１エントリとして記述することで実現することも可能である。
【０１０３】
交差角取得部２２０は、クライアント装置１００からの受信にはじまる一連の処理を経て不変量ヒストグラムセット作成部２１８により得られる不変量セットＸの入力を処理開始要求と見なし、不変量セットデータベース２１９から順次不変量セット取得を行う。交差角取得部２２０は、取得すべき不変量セットを指示し、該当不変量セットＹｉにおける基準点の交差角を取得する。また、不変量セットＸにおける基準点の交差角も取得する。順次取得する不変量セットＹｉは、不変量セットデータベース２１９中のすべてのセットを対象としてもよく、また何らかのルールに基づいて対象を制限してもよい。
【０１０４】
交差角比較部２２１は、交差角取得部２２０により得られる不変量セットＸ及びＹｉの交差角を比較し、その交差角がほぼ同一であるとした場合にはマトリクスヒストグラム照合部２２２に対して照合処理を指示する。
【０１０５】
マトリクスヒストグラム照合部２２２は、交差角比較部２２１による照合処理指示により不変量セットＸ及びＹｉのマトリクスヒストグラムを取得し、その照合スコアＭを算出する。
【０１０６】
類似性スコア算出部２２３は、マトリクスヒストグラム照合部２２２により得られる照合スコアＭに基づいて類似性スコアＳを算出する。
【０１０７】
類似性判定部２２４は、類似性スコア算出部２２３により得られた類似性スコアに基づいて、不変量セットＸとＹｉの類似性を判定する。類似していると判定された場合は、その識別子ｉを識別子送信部２２５に転送する。
【０１０８】
識別子送信部２２５は、類似性判定部２２４から転送された識別子ｉをクライアント装置１００に送信する。
【０１０９】
図１６は、本発明の第１の実施例における直線パターン識別方法を示すシーケンスチャートである。
【０１１０】
以下、図１６を参照して、本実施例における直線パターン識別方法の動作について説明する。
【０１１１】
まず、ユーザは、利用者インタフェース１１５を介して識別対象となる画像を指示する（ステップ４０１）。
【０１１２】
次に、利用者インタフェース１１５から転送された画像を直線パラメータ取得部１１１が受け取り、直線検出処理により画像中の主要直線パラメータを検出し、その直線パラメータ集合を取得する（ステップ４０２）。本実施例における直線パラメータ取得手段としては、「P.V.C. Hough: ”Method and Means for Recognizing Complex Patterns”, U.S. Patent, 3069654, 1962」に記載されているハフ変換などを用いることができる。
【０１１３】
次に、直線パラメータ取得部１１１が取得した直線パラメータ集合を、直線パラメータファイル１１２としてクライアント装置１００内に書き込む（ステップ４０３）。直線パラメータとしては、傾き・切片（ａ，ｂ）による表現方法や、原点からの直線に下ろした垂線の長さ及び、垂線とＸ軸との角度（ρ，θ）による表現方法などを用いることができる。ファイル形式として、例えば、ｃｓｖ形式を用いることができる。
【０１１４】
次に、直線パラメータ送信部１１３が直線パラメータファイル１１２内の記述内容をサーバ装置２００へ送信する（ステップ４０４）。サーバ装置２００内の直線パラメータ受信部２１１は、その内容を受信する（ステップ４０５）。
【０１１５】
次に、交点・交差角算出部２１２は、受信された直線パラメータ集合の中で可能なすべての二直線がなす交点座標とその交差角を算出する（ステップ４０６）。対象とする二直線が平行である場合には、交点・交差角を算出しない。また、二直線が平行に近い場合には、画像上へのノイズなどに起因するパラメータ誤差に伴う交点座標の変動が大きくなるため、やはり交点・交差角を求めないようにすることも可能である。
【０１１６】
次に、距離算出部２１３は、交点・交差角算出部２１２により得られる各々の交点を基準点として、その基準点から直線パラメータ集合中の各直線までの距離を算出する（ステップ４０７）。
【０１１７】
次に、不変量算出部２１４は、距離算出部２１３により得られる各直線への距離を用い、予め与えられた関数式に従って各々二直線距離の組み合わせに対する距離比の関数値を算出して距離不変量を算出する（ステップ４０８）。関数式は、単なる距離比の定数倍であってもよく、log関数などであってもよい。また、距離比は０より大きく１以下の値を取るとすることができる。この場合、１より大きいときにはその逆数を求めることになる。
【０１１８】
また、ある直線に対する距離がゼロである場合には、その直線を対象とする距離比を求めない。同様に距離ある閾値より小さい場合には、画像上へのノイズなどに起因するパラメータ誤差に伴う距離比の変動が大きくなるため、やはりその直線を対象としないようにすることも可能である。
【０１１９】
更に、不変量算出部２１４は、交点・交差角算出部２１２において既に得られている、該当する二直線がなす交差角と距離比関数値を対にすることで、直線不変量対を算出する（ステップ４０９）。
【０１２０】
上記のステップ４０７からステップ４０９のまでの処理は、ある交点を基準点とした際の、その交点を形成する二直線を除くすべての直線パラメータに対して実施することで、すべての直線不変量対を算出する。
【０１２１】
次に、マトリクス生成部２１５は、直線不変量対をヒストグラム化するためのマトリクスを生成し、初期化する（ステップ４１０）。そのマトリクスは、例えば、２次元のテーブル（配列）として生成される。直線不変量対がとる値域に応じて、各セルの量子化サイズとテーブルサイズを決定する。
【０１２２】
次に、インデクス算出部２１６は、各々の直線不変量対から、加算すべきマトリクス上の位置を算出する（ステップ４１１）。例として、直線不変量対における距離比関数値をｒ、交差角をｔ、マトリクスのセル量子化サイズをそれぞれΔｒ・Δｔ、マトリクスのオフセット値（値がゼロであるときのインデクス値）をｒ０・ｔ０としたとき、インデクス値（Ｉｒ，Ｉｔ）は、
Ｉｒ＝floor(ｒ／Δｒ）＋ｒ０，    Ｉｔ＝floor(ｔ／Δｔ)＋ｔ０
により算出することができる（floor(x)は、ｘを超えない整数)。なお、インデクス値は必ずしも１つである必要はなく、複数箇所をその位置として算出してもよい。また、その複数箇所の位置として、正規分布や矩形分布に従った領域を取ることも可能であり、直線不変量対の値に応じて可変であってもよい。
【０１２３】
次に、マトリクス投票部２１７は、インデクス算出部２１６により得られる各々の直線不変量対に対応するマトリクス上の位置に対し、与えられた投票値を加算する（ステップ４１２）。
【０１２４】
上記のステップ４１１において複数箇所のインデックスが得られる場合には、それぞれのマトリクス上の位置に対して投票値を加算する。投票値は定数であってもよく、またマトリクス上の位置や直線不変量対の値に応じて可変であってもよい。
【０１２５】
上記のステップ４１１からステップ４１２までの処理は、すべての直線不変量対に対して実施することで、投票結果としてのマトリクスヒストグラムを算出する。
【０１２６】
次に、不変量ヒストグラムセット作成部２１８は、マトリクス投票部２１７によりすべての直線不変量対に対する投票が終了した時点で処理を開始し、マトリクス上のヒストグラムデータと、交点・交差角算出部２１２により得られる基準点の交差角を、一つの不変量ヒストグラムセットとして作成する（ステップ４１３）。
【０１２７】
次に、不変量セットデータベース２１９は、不変量ヒストグラムセット作成部２１８において作成された不変量セットＸを格納する（ステップ４１４）。不変量セットデータベース２１９として、例えば、１つのファイル内のｃｓｖエントリとしての登録・参照で実現することができる。
【０１２８】
ステップ４０７からステップ４１４までの処理は、交点・交差角算出部２１２において得られるすべての交点を基準点として繰り返し実施する。直線パラメータ数をＮとすると、交点数は概ねＮの２乗オーダである。従って１つの直線パラメータ集合に対して、不変量セットＸはＮの２乗オーダの数だけ存在することになる。以下のステップでは、識別対象とする画像における不変量セットの一つをＸｊと表し、識別対象とする画像における全不変量セットをＸと表す。
【０１２９】
次に、交差角取得部２２０は、不変量セットデータベース２１９内の不変量セットから交差角を順次取得する（ステップ４１５）。交差角取得部２２０は取得対象とする不変量セットを指示するが、ここでは、Ｘ以外の不変量セットを対象とし、Ｘを除く１不変量セット毎に以降のステップ４１６からステップ４１８までの処理を繰り返すことで、識別処理を実現することができる。ここでは、指示された不変量セットをＹｉとし、その画像識別子をｉとする。交差角取得部２２０は、不変量セットＸｊ及びＹｉにおける基準点の交差角を取得する。
【０１３０】
次に、交差角比較部２２１は、交差角取得部２２０により得られる不変量セットＸｊ及びＹｉの交差角を比較し、その交差角がほぼ同一であるとした場合には、マトリクスヒストグラム照合部２２２に対して照合処理を指示する（ステップ４１６）。不変量Ｘｊの交差角をθｊ、不変量Ｙｉの交差角をθｉとしたとき、例として、
│θｊ−θｉ│mod  π  ＜Ｔｈ
を満たす不変セットＹｉを照合対象とすることができる（Ｔｈは閾値）。
【０１３１】
次に、マトリクスヒストグラム照合部２２２は、交差角比較部２２１による照合処理指示により不変量セットＸｊ及びＹｉのマトリクスヒストグラムを取得し、その照合スコアＭを算出する（ステップ４１７）。照合スコアの算出は、各マトリクスにおけるヒストグラムの一致度を表す尺度であればよい。例として、Ｘｊのマトリクスにおける各セルの値を、ｖｊｋ，Ｙｉのマトリクスにおける各セルの値をｖｉｋとしたとき、照合スコアＭ＝（Ｈ，Ｖｉ，Ｖｊ）、但し、
Ｖｊ＝Σｖｊｋ（ｋに関するｖｊｋの総和）
Ｖｉ＝Σｖｉｋ（ｋに関するｖｉｋの総和）
Ｈ＝Σmin（ｖｉｋ，ｖｊｋ）（ｋに関するｖｉｋとｖｊｋの小さい方の総和）
とすることができる（ｋは各セルのインデクスを表す）。
【０１３２】
次に、類似性スコア算出部２２３は、マトリクスヒストグラム照合部２２２により得られる称号スコアＭに基づいて類似性スコアＳを算出する（ステップ４１８）。類似性スコアＳは、ＸｊとＹｉの類似性を表す尺度であればよく、照合スコアＭを用いて算出する。例として、前述のＭ＝（Ｈ，Ｖｉ，Ｖｊ）を用いて、
Ｓ＝Ｈ／（Ｖｉ＋Ｖｊ−Ｈ）
とすることができる。この類似性スコア算出式によれば、ＸｊとＹｉが同一に近いほどそのスコアは大きく、一方が他方に含まれるような場合にはＶｉもしくはＶｊがＨに比して大きくなるためそのスコアは小さくなる。
【０１３３】
次に、類似性判定部２２４は、類似性スコア算出部２２３により得られた類似性スコアＳに基づいて、不変量セットＸｊとＹｉの類似性を判定し、類似していると判定された場合は、その識別子ｉを識別子送信部２２５に転送する（ステップ４１６）。類似性判定ルールは任意であり、例えば、単にスコアＳが設定した閾値を超えた場合であってもよい。もしくは、あるＸｊに対するすべてのＹｉにおける類似性スコアを比較し、最大値をとる識別子に対して得点を加算し、その処理をすべてのＸｊに対して行った後に、最も総合得点の高い識別子を識別結果として判定することも可能である。
【０１３４】
識別子送信部２２５は、類似性判定部２２４から転送された識別子ｉをクライアント装置１００に送信する（ステップ４２０）。クライアント装置１００内の識別子受信部１１４は、その識別子ｉを受信する（ステップ４２１）。そして、利用者インタフェース１１５がその識別子ｉを表示する（ステップ４２２）。
【０１３５】
以上の実施例は、画像を識別対象データとして想定しているが、直線パラメータ集合そのものを対象データと想定し、ユーザがパラメータ値そのものを利用者インタフェース１１５に提示するような実施例も可能である。
【０１３６】
また、直線パラメータ取得部１１１の機能がサーバ装置２００内に存在し、クライアント装置１００は、ユーザにより提示された画像そのものをサーバ装置２００に送信するような実施例も可能である。同様に交点・交差角算出部２１２から不変量セット作成部２１８までをクライアント装置１００で保有し、不変量セットデータをサーバ装置２００に送信するような実施例も可能である。
【０１３７】
なお、図１５で示したシステムにおける装置（クライアント、サーバ）各部の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行し、本発明を実現することができること、あるいは、図１６のシーケンスチャートや本文記載の説明文や式で示した処理の手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることはいうまでもなく、コンピュータでその機能を実現するためのプログラム、あるいは、コンピュータにその処理の手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記憶媒体、例えば、ＨＤＤ，ＭＯ，ＲＯＭ，メモリカード，ＣＤ，ＤＶＤ，リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。
【０１３８】
上記のプログラムは、インターネットや電子メールなど、ネットワークを通して提供することも可能である。また、上記のプログラムは、サーバやクライアントのコンピュータ別に作成されることは当然であるが、記憶媒体への記録や、ネットワークを通しての提供に際しては、ひとまとめにしたり、個別にしたり、組み合わせたりして行ってもよい。
【０１３９】
以上、本発明の代表的な実施の形態及び実施例を説明したが、本発明は上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【０１４０】
本発明は、画像を蓄積したデータベースからユーザが提示した画像パターンに基づいて類似する画像を検索する画像検索システムに適用可能である。
【図面の簡単な説明】
【０１４１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における直線パターン識別装置の構成図である。
【図４】本発明の一実施の形態における直線パラメータと直線不変量対の関係概念図である。
【図５】本発明の一実施の形態における不変量セットの概念図である。
【図６】本発明の一実施の形態における不変量セット照合を説明するための図である。
【図７】本発明の一実施の形態における不変量セット照合部の構成図である。
【図８】本発明の一実施の形態における交差角比較を説明するための図である。
【図９】本発明の一実施の形態における不変量セット作成部及び直線不変量対照合部の構成図である。
【図１０】本発明の一実施の形態におけるマトリクスヒストグラム照合を説明するための図である。
【図１１】本発明の一実施の形態における直線パターン識別方法のフローチャートである。
【図１２】本発明の一実施の形態における不変量セット照合方法のフローチャートである。
【図１３】本発明の一実施の形態における不変量セット生成方法の詳細な処理のフローチャートである。
【図１４】本発明の一実施の形態における直線不変量対照合方法のフローチャートである。
【図１５】本発明の第１の実施例によるシステム構成図である。
【図１６】本発明の第１の実施例における直線パターン識別方法手順を示すシーケンスチャートである。
【図１７】本発明の第１の実施例における直線パターン識別方法手順を示すシーケンスチャートである。
【符号の説明】
【０１４２】
１  直線パターン識別装置
１１  直線パラメータ取得手段、直線パラメータ取得部
１２  交点・交差角算出手段、交点・交差角算出部
１３  距離算出手段、距離算出部
１４  不変量算出手段、不変量算出部
１５  不変量セット作成手段、不変量セット作成部
１６  不変量セットデータベース
１７  不変量セット照合手段、不変量セット照合部
１８  識別結果出力手段、識別結果出力部
２１  交差角取得部
２２  交差角比較部
２３  直線不変量対照合部
３１  マトリクス生成部
３２  インデクス算出部
３３  マトリクス投票部
３４  不変量ヒストグラムセット作成部
３５  マトリクスヒストグラム照合部
３６  類似性スコア算出部
１００  クライアント装置
１１１  直線パラメータ取得部
１１２  直線パラメータファイル
１１３  直線パラメータ送信部
１１４  識別子受信部
１１５  利用者インタフェース
２００  サーバ装置
２１１  直線パラメータ受信部
２１２  交点・交差角算出部
２１３  距離算出部
２１４  不変量算出部
２１５  マトリクス生成部
２１６  インデクス算出部
２１７  マトリクス投票部
２１８  不変量ヒストグラムセット作成部
２１９  不変量セットデータベース
２２０  交差角取得部
２２１  交差角比較部
２２２  マトリクスヒストグラム照合部
２２３  類似性スコア算出部
２２４  類似性判定部
２２５  識別子送信部
【図１】
2006163916.tif 000003
【図２】
2006163916.tif 000004
【図３】
2006163916.tif 000005
【図４】
2006163916.tif 000006
【図５】
2006163916.tif 000007
【図６】
2006163916.tif 000008
【図７】
2006163916.tif 000009
【図８】
2006163916.tif 000010
【図９】
2006163916.tif 000011
【図１０】
2006163916.tif 000012
【図１１】
2006163916.tif 000013
【図１２】
2006163916.tif 000014
【図１３】
2006163916.tif 000015
【図１４】
2006163916.tif 000016
【図１５】
2006163916.tif 000017
【図１６】
2006163916.tif 000018
【図１７】
2006163916.tif 000019