Pat
J-GLOBAL ID：201003019985607493
2次元図形マッチング方法
Inventor：
Applicant, Patent owner：
Agent (1)：
北川 泰隆
Gazette classification：公開公報
Application number (International application number)：2009114066
Publication number (International publication number)：2010262546
Application date： May. 09, 2009
Publication date： Nov. 18, 2010
Summary：
【課題】逐次性を有する高速な2次元図形マッチング方法を提供することを目的とする。【解決手段】入力地図および参照地図に新たな点を挿入し(S102,S108)、入力地図および参照地図の局所特徴を抽出し(S104,S110)、抽出された参照地図の局所特徴を記憶し(S112)、抽出された入力地図内の局所特徴の一つをクエリとし、類似する参照地図内の局所特徴を検索し(S114)、検索結果から解候補としての仮説を含む仮説集合を生成し(S116)、仮説集合に含まれる各仮説の確からしさを評価する(S118)。この際、参照地図の局所特徴のLSH関数によるハッシュ値に対応するビンに記憶し(S112)、クエリに関する局所特徴のLSH関数によるハッシュ値に対応するビンを検索し(S114)、点と仮説との対である点仮説ペアを評価する順序を計画し(S118a)、最良の仮説を選出する(S118b)。【選択図】図11
Claim (excerpt)：
点列で構成された2次元図形の位置合せをする2次元図形マッチング方法であって、
入力2次元図形および参照2次元図形に新たな点を挿入する図形更新工程と、
前記入力2次元図形および前記参照2次元図形各々の局所特徴を抽出する特徴抽出工程と、
前記特徴抽出工程によって抽出された前記参照2次元図形の前記局所特徴を記憶する記憶工程と、
前記特徴抽出工程によって抽出された前記入力2次元図形内の前記局所特徴の一つをクエリとし、前記記憶工程で記憶された前記参照2次元図形内で、前記クエリに関する前記局所特徴と類似する前記参照2次元図形内の局所特徴群を検索する検索工程と、
前記検索工程での検索結果から解候補としての仮説を含む仮説集合を生成する仮説生成工程と、
前記仮説集合に含まれる各仮説の確からしさを評価する仮説評価工程とを有し、
前記記憶工程は、前記特徴抽出工程によって抽出された前記参照2次元図形の前記局所特徴を、LSH関数でハッシュ値に変換し、当該ハッシュ値に対応するハッシュ表の全てのビンに前記参照2次元図形の前記局所特徴を関連付けて記憶し、
前記検索工程は、前記特徴抽出工程によって抽出された前記入力2次元図形内の前記局所特徴を、LSH関数でハッシュ値に変換し、当該ハッシュ値に対応する前記ハッシュ表の前記ビンにアクセスし、前記ハッシュ表中で前記入力2次元図形内の前記局所特徴に対応する前記局所特徴群を検索し、
前記仮説評価工程は、点と仮説との対である点仮説ペアの当該仮説のスコア値を計算し、計算された前記スコア値に基づき、前記点仮説ペアを評価する順序を計画する順序ルール工程と、前記順序ルール工程で計算された前記スコア値に基づき更新された、前記仮説の前記スコア値の履歴をもとに、最良の仮説を選出する選択ルール工程とを有することを特徴とする2次元図形マッチング方法。
IPC (5)：
G06T 7/20
, G09B 29/00
, G09B 29/10
, G01C 21/00
, G06T 7/60
G06T7/20 100
, G09B29/00 A
, G09B29/10 A
, G01C21/00 E
, G06T7/60 150P
, G06T7/60 150B
2C032HB15
, 2C032HD27
, 2C032HD30
, 2F129BB08
, 2F129BB33
, 2F129BB49
, 2F129CC20
, 2F129GG17
, 5H301BB14
, 5H301CC03
, 5H301GG03
, 5H301GG08
, 5H301QQ06
, 5L096BA18
, 5L096DA02
, 5L096EA17
, 5L096EA23
, 5L096EA27
, 5L096FA52
, 5L096FA67
, 5L096FA69
, 5L096GA53
, 5L096HA08
