[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP2013025662A - Retrieval method, retrieval device, and program - Google Patents

Retrieval method, retrieval device, and program Download PDF

Info

Publication number
JP2013025662A
JP2013025662A JP2011161695A JP2011161695A JP2013025662A JP 2013025662 A JP2013025662 A JP 2013025662A JP 2011161695 A JP2011161695 A JP 2011161695A JP 2011161695 A JP2011161695 A JP 2011161695A JP 2013025662 A JP2013025662 A JP 2013025662A
Authority
JP
Japan
Prior art keywords
pattern
matrix
target data
score
coefficient
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2011161695A
Other languages
Japanese (ja)
Other versions
JP5476343B2 (en
Inventor
Ruche Christian
ルーシャ クリスティアン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
FIRST KK
First Co Ltd
Original Assignee
FIRST KK
First Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by FIRST KK, First Co Ltd filed Critical FIRST KK
Priority to JP2011161695A priority Critical patent/JP5476343B2/en
Publication of JP2013025662A publication Critical patent/JP2013025662A/en
Application granted granted Critical
Publication of JP5476343B2 publication Critical patent/JP5476343B2/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Image Analysis (AREA)

Abstract

PROBLEM TO BE SOLVED: To find a solution by making sampling increments as large as possible and shortening an execution time.SOLUTION: In a step S12, a retrieval device calculates a movement threshold which is a monotone non-decreasing value for an index value sequentially added to elements included in a pattern. In a step S17, the retrieval device calculates a provisional transformation coefficient T. In a step S24, on the basis of the movement threshold of the pattern elements when a score is updated, the retrieval device determines whether the updated score is small. When it is determined that the updated score is equal to or more than the movement threshold of the pattern elements, the retrieval device updates an update coefficient vector U and the transformation coefficient T. When it is determined that the updated score is less than the movement threshold, the procedure continues to a step S29.

Description

本発明は検索方法および検索装置、並びにプログラムに関する。   The present invention relates to a search method, a search apparatus, and a program.

従来から、形状を示す点群であるパタン(以下、パタンと称する)と、形状を示す点群である対象データ(以下、対象データと称する)とから、対象データで示される形状の中から、パタンで示される形状と同じ形状の位置および角度を検索する技術が提案されている。例えば、2次元点群で構成されている対象データ(以下、2D対象データと称する)の中から、2次元点群で構成されているパタン(以下、2Dパタンと称する)と同じ形状の位置および角度を検索する技術が提案されている(特許文献1参照)。また、検索結果を表す位置および角度の精度を向上させる技術(以下、この技術をICPと称する)が提案されている(非特許文献1参照)。更に、2Dパタンと2D対象データを対象とするICP(以下、2D-ICPと称する)の他に、3次元点群で構成されている対象データ(以下、3D対象データと称する)と3次元点群で構成されているパタン(以下、3Dパタンと称する)を対象とし、検索結果を表す位置および角度の精度を向上させるICP(以下、3D-ICPと称する)も提案されている(非特許文献2参照)。   Conventionally, from a pattern that is a point group indicating a shape (hereinafter referred to as a pattern) and target data that is a point group indicating a shape (hereinafter referred to as target data), from among the shapes indicated by the target data, A technique for searching for the position and angle of the same shape as the shape indicated by the pattern has been proposed. For example, the position of the same shape as the pattern (hereinafter referred to as 2D pattern) composed of the two-dimensional point group from the target data (hereinafter referred to as 2D target data) composed of the two-dimensional point group, and A technique for searching for an angle has been proposed (see Patent Document 1). In addition, a technique for improving the accuracy of the position and angle representing the search result (hereinafter, this technique is referred to as ICP) has been proposed (see Non-Patent Document 1). In addition to ICP (hereinafter referred to as 2D-ICP) for 2D patterns and 2D target data, target data (hereinafter referred to as 3D target data) and 3D points composed of 3D point groups An ICP (hereinafter referred to as 3D-ICP) that improves the accuracy of the position and angle representing a search result has also been proposed (hereinafter, referred to as 3D-ICP) for a pattern composed of a group (hereinafter referred to as a 3D pattern). 2).

更に、2次元点群の点毎に法線ベクトルを表す2次元ベクトルと言う特徴量が付いている事もあり、法線ベクトル付きの2次元点群を2Dパタンまたは2D対象データとして用いられる場合もある。また、3次元点群の点毎にノーマルベクトルを表す3次元ベクトルと言う特徴量が付いている事もあり、ノーマルベクトル付きの3次元点群を3Dパタンまたは3D対象データとして用いられる場合もある。法線ベクトルまたはノーマルベクトルと言う特徴量がパタンまたは対象データに含まれている場合は、そのベクトル特徴量を検索の際に配慮する技術が存在する。更に、3次元形状を2次元のデータに変換するプロセス(例えばカメラで3次元形状を撮影すれば得られる2次元の画像)が用いられる場合もあり、その時に、2次元対象データと、2次元点群に投影される3Dパタンが重なる様に、3Dパタンの位置および角度の精度を向上する技術(以下3D-2D-ICPと称する)も提案されている(非特許文献3参照)。抽象化すると、パタンまたは対象データが、特徴量を表す複数のベクトル(例えば、2次元点)で出来ている。以下で、パタンが持つ複数のベクトルの一つを要素とも称する。   Furthermore, a feature quantity called a two-dimensional vector representing a normal vector may be attached to each point of the two-dimensional point group, and the two-dimensional point group with the normal vector is used as a 2D pattern or 2D target data. There is also. In addition, a feature amount called a three-dimensional vector representing a normal vector may be attached to each point of the three-dimensional point group, and a three-dimensional point group with a normal vector may be used as 3D pattern or 3D target data. . When a feature amount called a normal vector or a normal vector is included in a pattern or target data, there is a technique for taking the vector feature amount into consideration when searching. Furthermore, there is a case where a process of converting a three-dimensional shape into two-dimensional data (for example, a two-dimensional image obtained by photographing a three-dimensional shape with a camera) is used. A technique for improving the position and angle accuracy of the 3D pattern (hereinafter referred to as 3D-2D-ICP) has also been proposed (see Non-Patent Document 3) so that the 3D pattern projected onto the point group overlaps. When abstracted, the pattern or target data is made up of a plurality of vectors (for example, two-dimensional points) representing feature amounts. Hereinafter, one of a plurality of vectors of the pattern is also referred to as an element.

以下、3D-ICPにおいて用いられる技術について説明する。   Hereinafter, techniques used in 3D-ICP will be described.

まず、3次元相似座標変換について説明する。   First, three-dimensional similar coordinate transformation will be described.

パタンに含まれる点に、式(1)に示す行列を、式(2)に示すようにかけることにより、パタンの3次元座標から検索空間の3次元座標に変換することができる。式(1)に示す行列のT14,T24,T34は、式(3)に示すようにX,Y,Zの移動量を示す。

Figure 2013025662
・・・(1) By applying the matrix shown in Expression (1) to the points included in the pattern as shown in Expression (2), the three-dimensional coordinates of the pattern can be converted into the three-dimensional coordinates of the search space. T14, T24, and T34 in the matrix shown in Expression (1) indicate the movement amounts of X, Y, and Z as shown in Expression (3).
Figure 2013025662
... (1)

Figure 2013025662
・・・(2)
Figure 2013025662
... (2)

Figure 2013025662
・・・(3)
Figure 2013025662
... (3)

ここで、3次元の座標変換を相似変換に制限する。式(1)に示す行列の左上の3×3の行列は、式(4)に示すように、回転行列Rとスケール係数sの積になる。回転行列Rは、式(5)に示す行列であって、式(6)および式(7)の要件を満たす行列である。すなわち変換行列Tを、式(8)に示すように、移動量Vで示される移動、回転行列Rで示される回転、およびスケール係数sで示されるスケール変換が組み合わされた3次元の座標変換とすることができる。

Figure 2013025662
・・・(4) Here, three-dimensional coordinate transformation is limited to similarity transformation. The 3 × 3 matrix at the upper left of the matrix shown in Equation (1) is the product of the rotation matrix R and the scale factor s, as shown in Equation (4). The rotation matrix R is a matrix shown in Expression (5) and satisfies the requirements of Expression (6) and Expression (7). That is, as shown in the equation (8), the transformation matrix T is converted into a three-dimensional coordinate transformation in which the movement indicated by the movement amount V, the rotation indicated by the rotation matrix R, and the scale conversion indicated by the scale factor s are combined. can do.
Figure 2013025662
... (4)

Figure 2013025662
・・・(5)
Figure 2013025662
... (5)

Figure 2013025662
・・・(6)
Figure 2013025662
... (6)

Figure 2013025662
・・・(7)
Figure 2013025662
... (7)

る。

Figure 2013025662
・・・(8) The
Figure 2013025662
... (8)

ここで、式(9)〜式(12)に示されるように、微分回転行列Hを導入する。その結果、式(13)に示す座標変換式が得られる。

Figure 2013025662
・・・(9) Here, a differential rotation matrix H is introduced as shown in the equations (9) to (12). As a result, the coordinate conversion formula shown in Formula (13) is obtained.
Figure 2013025662
... (9)

Figure 2013025662
・・・(10)
Figure 2013025662
... (10)

Figure 2013025662
・・・(11)
Figure 2013025662
(11)

Figure 2013025662
・・・(12)
Figure 2013025662
(12)

Figure 2013025662
・・・(13)
Figure 2013025662
... (13)

次に、座標変換に微妙に変換を加える。
ここでは、式(13)を式(14)で表し、式(15)および式(16)に示すように微分を行い、式(17)に示す微分の行列である微分行列Jと式(18)に示す微分の係数のベクトルである更新係数ベクトルUを得る。

Figure 2013025662
・・・(14)
Figure 2013025662
・・・(15) Next, a subtle transformation is added to the coordinate transformation.
Here, Expression (13) is expressed by Expression (14), differentiation is performed as shown in Expression (15) and Expression (16), and a differentiation matrix J and Expression (18), which is a differentiation matrix shown in Expression (17). An update coefficient vector U which is a vector of differential coefficients shown in FIG.
Figure 2013025662
(14)
Figure 2013025662
... (15)

Figure 2013025662
・・・(16)
Figure 2013025662
・・・(17)
Figure 2013025662
... (16)
Figure 2013025662
... (17)

Figure 2013025662
・・・(18)
Figure 2013025662
... (18)

次に、3次元の点のマッチングおよび座標変換Tの最適化について説明する。   Next, three-dimensional point matching and optimization of coordinate transformation T will be described.

前述のように、パタンは、形状を示す3次元の点群であり、対象データは、形状を示す3次元の点群である。パタンの点毎に、対象データの対応する点を知ることが出来るのが最も好ましい。式(19)および式(20)に示されるように、対象データの点群の中で、パタンの点に対応すると判断された点の座標を座標Xcorrと称し、変換行列Tの最適化前の誤差を誤差Xerrと称する。

Figure 2013025662
・・・(19) As described above, the pattern is a three-dimensional point group indicating a shape, and the target data is a three-dimensional point group indicating a shape. Most preferably, for each point of the pattern, the corresponding point of the target data can be known. As shown in Expression (19) and Expression (20), the coordinates of a point determined to correspond to the pattern point in the point group of the target data are referred to as coordinates X corr, and before the transformation matrix T is optimized. Is referred to as error X err .
Figure 2013025662
... (19)

Figure 2013025662
・・・(20)
Figure 2013025662
... (20)

ここで、式(21)に示されるように、微分行列J(式(17))と微分の係数のベクトルである更新係数ベクトルU(式(18))を導入する。

Figure 2013025662
・・・(21) Here, as shown in Expression (21), a differential matrix J (Expression (17)) and an update coefficient vector U (Expression (18)) that is a vector of differential coefficients are introduced.
Figure 2013025662
... (21)

式(22)に示されるように、A*U=Cの様に線形な数式となるので最小二乗法により更新係数ベクトルUを求めることができる。

Figure 2013025662
・・・(22) As shown in the equation (22), the update coefficient vector U can be obtained by the least square method because it is a linear equation such as A * U = C.
Figure 2013025662
(22)

より速く精度良く計算するためにノーマルベクトルと接触平面を利用する方法もある。ここでは、パタンは3次元の点群にノーマルベクトルを加えたものとし、対象データは3次元の点群にノーマルベクトルを加えたものとする。式(23)に示されるように、対象データの点毎に、平面(p1,p2,p3,p4)が計算される。

Figure 2013025662
・・・(23) There is also a method using normal vectors and contact planes for faster and more accurate calculations. Here, the pattern is obtained by adding a normal vector to a three-dimensional point group, and the target data is obtained by adding a normal vector to a three-dimensional point group. As shown in Expression (23), a plane (p1, p2, p3, p4) is calculated for each point of the target data.
Figure 2013025662
(23)

式(24)に示されるように、変換条件として、変換後の点が平面の上にあることとする。

Figure 2013025662
・・・(24) As shown in Expression (24), it is assumed that the converted point is on a plane as a conversion condition.
Figure 2013025662
... (24)

誤差eは、式(25)で示される。

Figure 2013025662
・・・(25) The error e is expressed by equation (25).
Figure 2013025662
... (25)

式(26)に示されるように、微分を使用して誤差eが0になるような係数ベクトルUを求めることができる。

Figure 2013025662
・・・(26) As shown in the equation (26), a coefficient vector U such that the error e becomes 0 can be obtained using differentiation.
Figure 2013025662
... (26)

そこで、式(27)に示されるように、A*U=Cの様に線形な数式となるので最小二乗法により更新係数ベクトルUを求めることができる。

Figure 2013025662
・・・(27) Therefore, as shown in the equation (27), the update coefficient vector U can be obtained by the least square method because it is a linear equation such as A * U = C.
Figure 2013025662
... (27)

以上を纏めると、式(22)や式(27)の様に、対応関係(=パタン点と対象データの点が対応していると判断されている点ペア)毎に、A*U=Cの様な線形的な式を得ることができる。すなわちそれらの式を組み合わせて、つまりそれらの行列Aを縦方向でくっつけ、そしてそれらのベクトルCを縦方向でくっつける事で、より大きな行列AとベクトルCを作り、それらのすべての対応関係に対してA*U=Cの式を作る事ができる。   Summarizing the above, for each correspondence (= point pair for which the pattern point and the point of the target data are determined to correspond), as in Expression (22) and Expression (27), A * U = C A linear expression such as can be obtained. In other words, by combining these formulas, that is, by attaching the matrix A in the vertical direction and by attaching the vectors C in the vertical direction, a larger matrix A and a vector C are created, and for all of their correspondences A * U = C can be created.

次に、更新係数ベクトルUの使い方について考える。上述の方法では、式(22)や式(27)に示したように、式(28)に示されるように線形的な式が得られるので、式(29)および式(30)に示されるように、最小二乗法など標準的な解法を利用することができる。

Figure 2013025662
・・・(28) Next, how to use the update coefficient vector U will be considered. In the above-described method, as shown in the formula (22) and the formula (27), a linear formula is obtained as shown in the formula (28). Therefore, the formula (29) and the formula (30) are used. Thus, standard solutions such as the least squares method can be used.
Figure 2013025662
... (28)

Figure 2013025662
・・・(29)
Figure 2013025662
... (29)

Figure 2013025662
・・・(30)
Figure 2013025662
... (30)

その結果、式(31)に示されるように、更新係数ベクトルUから変換行列Tを最適化することができる。すなわち微分回転行列HからRsmallが求められ、Rsmallから回転行列Rが求められる。そして移動量V,V,Vおよびスケールsが求められる。その結果、最適化された相似座標変換Tが求められる(式(8))。

Figure 2013025662
・・・(31) As a result, the transformation matrix T can be optimized from the update coefficient vector U as shown in Expression (31). That is, R small is obtained from the differential rotation matrix H, and the rotation matrix R is obtained from R small . Then, movement amounts V x , V y , V z and a scale s are obtained. As a result, an optimized similar coordinate transformation T is obtained (formula (8)).
Figure 2013025662
... (31)

ここで、makeRotation(H)は、回転行列の条件(式(6)や式(7))を満たさない3×3の行列Hから、最も近い正確な3×3の回転行列を求める関数である。SVD(特異値分析)など標準的な解法がある。   Here, makeRotation (H) is a function for obtaining the closest accurate 3 × 3 rotation matrix from the 3 × 3 matrix H that does not satisfy the conditions of the rotation matrix (Equation (6) or Equation (7)). . There are standard solutions such as SVD (singular value analysis).

次に、対応点の検索について説明する。3次元の点(x,y,z,特徴量)、3次元の対象データ点群(x,y,z,特徴量)、および最大距離や特徴量を使うなどの対応条件を入力とし、対象データの点群の中で3次元の点に最も近い、対応条件を満たす点を検索する対応点検索として、3Dセル配列、ハッシュ、K-d trees、またはOctreesなどを使用する標準的な手法がある。   Next, search for corresponding points will be described. 3D point (x, y, z, feature quantity), 3D target data point group (x, y, z, feature quantity), and corresponding conditions such as using maximum distance and feature quantity are input. There is a standard method using a 3D cell array, hash, Kd trees, or Octtrees as a corresponding point search for searching for a point that satisfies a corresponding condition that is closest to a three-dimensional point in a data point group.

また、パタンマッチスコア計算として、変換行列T、3次元のパタン、3次元の対象データ、変換後の最大距離などの対応条件を入力とし、スコア値を出力する手法が用いられている。そのアルゴリズムは、まず、スコア値に0を設定して初期化し、パタンの点毎に、変換行列Tを掛けて、変換後の座標を計算し、対応する点を検索し、対応点の有無や距離や対応条件等を配慮して、検索結果によってスコアを更新する手続きを繰り返し、最終的にスコアを返すものである。   In addition, as a pattern match score calculation, a method is used in which a corresponding condition such as a transformation matrix T, a three-dimensional pattern, three-dimensional target data, and a maximum distance after conversion is input and a score value is output. The algorithm first initializes the score value by setting it to 0, multiplies each pattern point by the transformation matrix T, calculates the coordinates after transformation, searches for the corresponding point, In consideration of distance, correspondence conditions, etc., the procedure for updating the score according to the search result is repeated, and finally the score is returned.

さらにまた、3次元のパタンの位置、回転、スケールを調整して、対象データに合わせる、いわゆる、微調整または精サーチと称する手法も用いられている。この場合、入力は、変換行列T、3次元のパタン、および3次元の対象データであり、出力は、最適化された変換行列Tとスコアとからなるポーズである。   Furthermore, a so-called fine adjustment or fine search method is also used in which the position, rotation, and scale of a three-dimensional pattern are adjusted to match target data. In this case, the input is a transformation matrix T, a three-dimensional pattern, and three-dimensional target data, and the output is a pose composed of an optimized transformation matrix T and a score.

そのアルゴリズムは、式(30)に示す行列Bおよび行列Dを初期化し、スコアに0を設定して初期化し、パタン点毎にスコアを更新し、最小二乗法にて係数ベクトルUの更新を計算して、変換行列Tを更新する処理を、最大ループ数となるまで、または収束するまで繰り返し、最終的に変換行列Tを出力するものである。ここで、パタン点毎にスコアを更新する手続きは、具体的には、現在の変換行列Tを使ってパタンの点を変換し、変換後の座標の近くに対象データの対応点を検索し、対応点が見つかれば、これを用いて行列Bおよび行列Dを更新し、さらにスコアを更新するものである。   The algorithm initializes the matrix B and matrix D shown in equation (30), sets the score to 0, initializes it, updates the score for each pattern point, and calculates the update of the coefficient vector U by the least squares method Then, the process of updating the transformation matrix T is repeated until the maximum number of loops or until the convergence is reached, and finally the transformation matrix T is output. Here, in the procedure for updating the score for each pattern point, specifically, the pattern point is converted using the current conversion matrix T, the corresponding point of the target data is searched near the converted coordinates, If a corresponding point is found, the matrix B and the matrix D are updated using this, and the score is further updated.

また、変換行列Tが不明である場合に行われる、祖サーチ(Global Search)の手法がある。この場合、入力は、3次元のパタン、3次元の対象データ、検索空間、およびスコア閾値であり、出力は、変換行列Tとスコアとからなるポーズのリストである。各出力ポーズのスコアは、閾値より高い特性がある。また、各出力ポーズは、変換行列Tを微妙に代えてもスコア値が上がらない極値であると言う特性がある。出力データに含まれていない変換行列Tではスコアが入力のスコア閾値以下であるかスコアが極値でない。   In addition, there is a method of global search performed when the transformation matrix T is unknown. In this case, the input is a three-dimensional pattern, three-dimensional target data, a search space, and a score threshold, and the output is a list of poses composed of a transformation matrix T and a score. The score of each output pose has a characteristic higher than the threshold value. Each output pose has a characteristic that it is an extreme value in which the score value does not increase even if the transformation matrix T is slightly changed. In the transformation matrix T not included in the output data, the score is equal to or lower than the input score threshold or the score is not an extreme value.

祖サーチの手法として、検索空間をサンプリングして変換行列T毎に上述したようにパタンマッチスコアを計算し、スコアが局所的に最大で閾値より高い場合、変換行列Tをリストに追加し、リストの変換行列T毎に精サーチを実行して、リストを返すというものも存在する。   As an ancestor search method, the search space is sampled and the pattern match score is calculated for each transformation matrix T as described above. If the score is locally higher than the threshold, the transformation matrix T is added to the list, There is also a method that executes a fine search for each transformation matrix T and returns a list.

特開2006−277718号公報JP 2006-277718 A

http://en.wikipedia.org/wiki/Iterative_Closest_Pointhttp://en.wikipedia.org/wiki/Iterative_Closest_Point Z.Zhang, “Iterative PointMatching for Registration of Free-Form Curves”, InriaSophia Antipolis, Programme4 - Robotique, Image et Vision, ResearchReport Nr.1658, March 1992,ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-1658.pdfZ. Zhang, “Iterative PointMatching for Registration of Free-Form Curves”, InriaSophia Antipolis, Program4-Robotique, Image et Vision, ResearchReport Nr.1658, March 1992, ftp://ftp.inria.fr/INRIA/publication/publi -pdf / RR / RR-1658.pdf J.Feldmar, N.Ayache, F.Betting, ”3D-2D projectiveregistration of free-form curves and surfaces”, InriaSophia Antipolis, Programme4 - Robotique, Image et Vision, ResearchReport Nr.2434, December 1994,http://hal.inria.fr/docs/00/07/42/41/PDF/RR-2434/pdfJ.Feldmar, N.Ayache, F.Betting, “3D-2D projectiveregistration of free-form curves and surfaces”, InriaSophia Antipolis, Program4-Robotique, Image et Vision, ResearchReport Nr. 2434, December 1994, http: // hal .inria.fr / docs / 00/07/42/41 / PDF / RR-2434 / pdf

しかしながら、祖サーチにおいて、サンプリングの刻みを充分細かくしないと解答を見落としてしまい、サンプリングの刻みを充分細かくすると、実行時間が非常に長くなる。隠蔽、ノイズ、背景などの影響もある。さらに、産業的には、数秒以内の実行時間が求められている。   However, in the ancestor search, the answer is overlooked unless the sampling step is made sufficiently fine, and if the sampling step is made sufficiently fine, the execution time becomes very long. There are also effects such as concealment, noise, and background. Furthermore, industrially, an execution time within several seconds is required.

そこで、本発明は、上記課題を解決すること、すなわち、マッチングしながら微調整を行い、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる検索方法および検索装置、並びにプログラムを提供することを目的とする。   Therefore, the present invention solves the above-described problem, that is, a search method and a search apparatus that can find an answer while performing fine adjustment while matching, increasing the sampling interval as much as possible, and shortening the execution time. It aims at providing a program.

上記課題を解決するために、本発明の検索方法の一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する検索方法であって、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Tを計算する変換係数計算ステップと、変換係数Tを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルUおよび変換係数Tを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。   In order to solve the above-described problem, one aspect of the search method of the present invention is that each of the patterns converted from the target data, the pattern, and the conversion function into the target data space by the conversion function occupies a high degree of similarity with the target data. Similarly, a search method for calculating a coefficient of a conversion function, a threshold calculation step for calculating a movement threshold value that is a monotonically non-decreasing value with respect to an index value sequentially added to an element included in a pattern, A conversion coefficient calculation step for calculating a coefficient T of a conversion function from the element that is the first of the data, a predetermined element of the target data, and a sampling coefficient of the search space, and conversion for each pattern element using the conversion coefficient T The score, the matrix B, and the matrix D are updated in consideration of the degree of matching between the corresponding element and the corresponding element calculation step for calculating the element of the target data corresponding to the pattern element. Response effect calculation step, determination step for determining whether the updated score is smaller than the movement threshold value of the pattern element when the score is updated, and the updated score is equal to or higher than the movement threshold value of the pattern element A conversion coefficient update step for updating the update coefficient vector U and the conversion coefficient T. If it is determined that the updated score is smaller than the movement threshold, the predetermined element of the target data is As the target data element, the score is initialized, and the above-described processing is continued from the first element of the pattern.

また、本発明の検索方法の一側面は、上述の構成に加えて、パタンの最初の要素に対して対応要素計算する前に、更新係数ベクトルUの係数の間の柔軟性を示す行列Bに初期値として対角行列を設定する設定ステップをさらに含み、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立する時だけに、更新係数ベクトルUおよび変換係数Tが更新されるものとされている。   One aspect of the search method of the present invention is that, in addition to the above-described configuration, the matrix B indicating the flexibility between the coefficients of the update coefficient vector U is calculated before calculating the corresponding element for the first element of the pattern. The method further includes a setting step of setting a diagonal matrix as an initial value. In the conversion coefficient updating step, when it is determined that the updated score is equal to or greater than the movement threshold, a condition for performing a predetermined fine adjustment is satisfied. Only when the update coefficient vector U and the transform coefficient T are updated.

さらに、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立する時に、更新係数ベクトルUおよび変換係数Tを更新した後で、行列Bに対角行列が設定され、誤差の小さくなる位置を示す行列Dに0が設定されるものとされている。   Further, according to one aspect of the search method of the present invention, in addition to the above-described configuration, a predetermined fine adjustment should be performed when it is determined in the conversion coefficient update step that the updated score is equal to or greater than the movement threshold. When the condition is satisfied, after updating the update coefficient vector U and the transform coefficient T, a diagonal matrix is set in the matrix B, and 0 is set in the matrix D indicating the position where the error is reduced. .

さらにまた、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するときに、更新係数ベクトルUおよび変換係数Tを更新した後で、行列Bがそのままとされ、誤差の小さくなる位置を示す行列Dに0が設定されるものとされている。   Furthermore, in addition to the above-described configuration, one aspect of the search method of the present invention performs a predetermined fine adjustment when it is determined in the transform coefficient update step that the updated score is greater than or equal to the movement threshold. When the power condition is satisfied, after updating the update coefficient vector U and the conversion coefficient T, the matrix B is left as it is, and 0 is set to the matrix D indicating the position where the error is reduced.

また、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するときに、更新係数ベクトルUおよび変換係数Tを更新した後で、行列Bがそのままとされ、誤差の小さくなる位置を示す行列Dに、行列Bに更新係数ベクトルUを乗算して得られた積をそれまでの行列Dから引き算して得られた差が設定されるものとされている。   In addition to the above-described configuration, one aspect of the search method of the present invention should perform a fine adjustment that is determined in advance when it is determined that the updated score is greater than or equal to the movement threshold in the transform coefficient update step. When the condition is satisfied, after updating the update coefficient vector U and the transform coefficient T, the matrix B is left as it is, and the matrix B indicating the position where the error is reduced is multiplied by the matrix B by the update coefficient vector U. A difference obtained by subtracting the obtained product from the matrix D so far is set.

上記課題を解決するために、本発明の検索装置の一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する検索方法を実行する検索装置であって、この検索方法は、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Tを計算する変換係数計算ステップと、変換係数Tを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルUおよび変換係数Tを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。   In order to solve the above problems, one aspect of the search device of the present invention is that each of the patterns converted from the target data, the pattern, and the conversion function to the target data space by the conversion function occupies a high degree of similarity with the target data. Similarly, a search device that executes a search method for calculating a coefficient of a conversion function, which is a monotonous non-decreasing value with respect to an index value sequentially added to an element included in a pattern A threshold value calculating step for calculating a threshold value, a conversion coefficient calculating step for calculating a coefficient T of a conversion function from a first element of the pattern, a predetermined element of the target data, and a sampling coefficient of the search space, and a conversion coefficient T Use the corresponding element calculation step to calculate the element of the target data corresponding to the converted pattern element and the degree of matching with the corresponding element for each pattern element. A correspondence effect calculating step for updating the score, the matrix B, and the matrix D, a determination step for determining whether or not the updated score is smaller than the movement threshold value of the element of the pattern when the score is updated, and updated And the conversion coefficient update step of updating the update coefficient vector U and the conversion coefficient T, and the updated score is determined to be smaller than the movement threshold. In this case, the score is initialized with the predetermined element of the target data as the next target data element, and the above-described processing is continued from the first element of the pattern.

上記課題を解決するために、本発明のプログラムの一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する処理をコンピュータに実行させるプログラムであって、この処理は、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Tを計算する変換係数計算ステップと、変換係数Tを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルUおよび変換係数Tを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。   In order to solve the above problems, one aspect of the program of the present invention is that each of the patterns converted from the target data, the pattern, and the conversion function to the target data space by the conversion function occupies a high degree of similarity with the target data. Further, a program for causing a computer to execute a process for calculating a coefficient of a conversion function, and this process sets a moving threshold value that is a monotonically non-decreasing value with respect to an index value sequentially added to an element included in a pattern. A threshold value calculating step for calculating, a conversion coefficient calculating step for calculating a coefficient T of a conversion function from a first element of a pattern, a predetermined element of target data, and a sampling coefficient of a search space, and a conversion coefficient T For each pattern element, the corresponding element calculation step for calculating the element of the target data corresponding to the converted pattern element and the degree of matching with the corresponding element In consideration of the above, a correspondence effect calculation step for updating the score, the matrix B, and the matrix D, and a determination for determining whether the updated score is smaller than the movement threshold value of the pattern element when the score is updated And a conversion coefficient update step of updating the update coefficient vector U and the conversion coefficient T when it is determined that the updated score is greater than or equal to the movement threshold of the pattern element, and the updated score is greater than the movement threshold If it is determined to be small, the score is initialized with a predetermined element of the target data as the next target data element, and the above-described processing is continued from the first element of the pattern.

本発明の一側面によれば、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる検索方法および検索装置、並びにプログラムを提供することができる。   According to one aspect of the present invention, it is possible to provide a search method, a search device, and a program that can find an answer while increasing the sampling interval as much as possible to shorten the execution time.

検索装置の機能の構成の例を示すブロック図である。It is a block diagram which shows the example of a function structure of a search device. 検索の処理の例を説明するフローチャートである。It is a flowchart explaining the example of a process of a search. 移動閾値を説明する図である。It is a figure explaining a movement threshold value. 検索の処理の他の例を説明するフローチャートである。It is a flowchart explaining the other example of the process of a search. コンピュータのハードウェアの構成例を示すブロック図である。It is a block diagram which shows the structural example of the hardware of a computer.

以下、本発明の一実施の形態の検索方法および検索装置について、図1〜図5を参照しながら説明する。   Hereinafter, a search method and a search apparatus according to an embodiment of the present invention will be described with reference to FIGS.

図1は、検索装置の機能の構成の例を示すブロック図である。検索装置は、プログラムを実行するコンピュータまたは専用の機器であり、移動閾値計算部11、変換係数計算部12、初期値設定部13、対応要素計算部14、対応関係効果計算部15、パラメータ/変換係数更新部16、およびポーズリスト生成部17を含む。   FIG. 1 is a block diagram illustrating an example of a functional configuration of the search device. The search device is a computer that executes a program or a dedicated device, and includes a movement threshold value calculation unit 11, a conversion coefficient calculation unit 12, an initial value setting unit 13, a corresponding element calculation unit 14, a corresponding relationship effect calculation unit 15, parameters / conversions. A coefficient update unit 16 and a pose list generation unit 17 are included.

移動閾値計算部11は、移動閾値を計算する。移動閾値については後述する。変換係数計算部12は、パタンの最初の要素(パタンが持つ複数のベクトルの一つ)であるパタン要素0と対象データの要素と、検索空間サンプリングから変換係数Tを計算する。初期値設定部13は、行列Bや行列Dなどを初期化する。対応要素計算部14は、変換係数Tを使って変換されたパタンの要素と類似度の高い、対象データの要素を計算する。   The movement threshold calculation unit 11 calculates a movement threshold. The movement threshold will be described later. The conversion coefficient calculation unit 12 calculates the conversion coefficient T from the pattern element 0, which is the first element of the pattern (one of a plurality of vectors included in the pattern), the element of the target data, and search space sampling. The initial value setting unit 13 initializes the matrix B, the matrix D, and the like. The corresponding element calculation unit 14 calculates an element of the target data having a high similarity with the pattern element converted using the conversion coefficient T.

対応関係効果計算部15は、対応要素計算部14から対象データの対応要素が渡された場合、行列Bおよび行列Dを更新し、スコアを更新する。パラメータ/変換係数更新部16は、最小二乗法により更新係数ベクトルUを更新して、変換係数Tを更新する。パラメータ/変換係数更新部16は、判定部31を含む。判定部31は、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する。   When the correspondence element of the target data is passed from the correspondence element calculation unit 14, the correspondence relationship effect calculation unit 15 updates the matrix B and the matrix D and updates the score. The parameter / transform coefficient updating unit 16 updates the transform coefficient T by updating the update coefficient vector U by the least square method. The parameter / transform coefficient update unit 16 includes a determination unit 31. The determination unit 31 determines whether or not the updated score is smaller than the movement threshold value of the pattern element when the score is updated.

ポーズリスト生成部17は、変換係数Tとスコアとからなるポーズリストを生成する。   The pose list generation unit 17 generates a pose list including the conversion coefficient T and the score.

図2は、検索の処理の例を説明するフローチャートである。このフローチャートを参照して、検索処理を説明する。ステップS11において、検索装置は、変換係数Tの入力変換係数リスト、パタン、対象データ、およびスコア閾値を入力する。   FIG. 2 is a flowchart illustrating an example of search processing. The search process will be described with reference to this flowchart. In step S11, the search device inputs an input conversion coefficient list, a pattern, target data, and a score threshold value of the conversion coefficient T.

ステップS12において、移動閾値計算部11は、パタンに含まれる要素に、検索順に付加されたインデックスであるパタン要素インデックスの値に対して単調非減少の値となる移動閾値を計算する。   In step S12, the movement threshold value calculation unit 11 calculates a movement threshold value that is a monotonous non-decreasing value with respect to the value of the pattern element index that is an index added to the elements included in the pattern in the search order.

図3は、移動閾値を説明する図である。図3において、実線は移動閾値を示し、点線は移動閾値の上限を示す。なお点線は全てのパタン要素(N個のパタン要素)について検索された対象データがそのパタン要素との対応関係が完全な場合のスコアの推移を示すものとなっている。   FIG. 3 is a diagram for explaining the movement threshold. In FIG. 3, the solid line indicates the movement threshold, and the dotted line indicates the upper limit of the movement threshold. The dotted line indicates the transition of the score when the object data searched for all pattern elements (N pattern elements) has a complete correspondence with the pattern element.

移動閾値は、パタン要素インデックスの値に対して単調非減少の値となるのが好ましい。例えば、概ね、0からパタン要素数Nの3分の1の範囲のパタン要素インデックスが小さい範囲(すなわち最初の方で検索されるパタン要素)については、移動閾値は単調増加し、パタン要素インデックスが中程度の範囲(概ね、パタンの要素数Nの3分の1からパタンの要素数Nの3分の2の範囲)で、移動閾値は一定の値となり、パタン要素インデックスが大きい範囲(概ね、パタンの要素数Nの3分の2からパタンの要素数Nの範囲)で、移動閾値は単調増加するようにしてもよい。また、例えば、パタン要素インデックスがパタンの要素数Nの半分以下の範囲で、移動閾値はパタン要素インデックスと同じ値とされ、パタン点インデックスがパタンの要素数Nの半分以上の範囲で、移動閾値は一定の値とするようにしてもよい。   The movement threshold value is preferably a monotonically non-decreasing value with respect to the value of the pattern element index. For example, for a range in which the pattern element index is generally in the range from 0 to one third of the number of pattern elements N (ie, the pattern element searched for first), the movement threshold increases monotonously and the pattern element index is In the middle range (generally, a range from one third of the pattern element number N to two thirds of the pattern element number N), the movement threshold is a constant value, and the pattern element index is large (approximately, The movement threshold value may be monotonously increased in a range from two-thirds of the pattern element number N to the pattern element number N). Further, for example, when the pattern element index is in a range that is less than or equal to half of the pattern element number N, the movement threshold is the same as the pattern element index, and in the range that the pattern point index is greater than or equal to half of the pattern element number N May be a constant value.

ステップS13とステップS30とは、ループ1の処理とされ、入力変換関数リストの変換係数Tを全て選択するまで、ステップS14〜ステップS29の処理が繰り返される。   Steps S13 and S30 are loop 1 processes, and the processes of steps S14 to S29 are repeated until all the conversion coefficients T in the input conversion function list are selected.

ステップS14において、検索装置は、入力変換係数リストの変換係数Tを1つ選ぶ。   In step S14, the search device selects one conversion coefficient T in the input conversion coefficient list.

ステップS15とステップS29とは、ループ2の処理とされ、対象データの全ての要素が選択されるまで、ステップS16〜ステップS28の処理が繰り返される。   Step S15 and step S29 are processing of loop 2, and the processing of step S16 to step S28 is repeated until all elements of the target data are selected.

ステップS16において、検索装置は、対象データの要素を1つ選ぶ。   In step S16, the search device selects one element of the target data.

ステップS17において、変換係数計算部12は、パタンの最初の要素であるパタン要素0と選択された対象データの要素と選択された変換係数Tから、パタン要素0が選択された対象データの要素と類似度の高い要素に変換される様に、変換係数Tを計算する(例えば、変換係数Tの中で移動量を表す移動量Vを計算してTに設定する)。   In step S <b> 17, the conversion coefficient calculation unit 12 selects the pattern element 0 that is the first element of the pattern, the element of the selected target data, and the element of the target data for which the pattern element 0 is selected from the selected conversion coefficient T. A conversion coefficient T is calculated so as to be converted into an element having a high degree of similarity (for example, a movement amount V representing a movement amount in the conversion coefficient T is calculated and set to T).

ステップS18とステップS27とは、ループ3の処理とされ、予め定められた最大ループ数まで、ステップS19〜ステップS26の処理が繰り返される。なお、収束するまで、ステップS19〜ステップS26の処理が繰り返されるようにしてもよい。   Steps S18 and S27 are processing of loop 3, and the processing of steps S19 to S26 is repeated up to a predetermined maximum number of loops. Note that the processes in steps S19 to S26 may be repeated until convergence.

ステップS19において、初期値設定部13は、行列Bおよび行列D(式(30))を初期化し、スコアを0に初期化する。   In step S19, the initial value setting unit 13 initializes the matrix B and the matrix D (formula (30)), and initializes the score to zero.

ステップS20とステップS25とは、ループ4の処理とされ、すべてのパタン要素に対して、ステップS21〜ステップS24の処理が行われる。   Step S20 and step S25 are processing of loop 4, and the processing of step S21 to step S24 is performed for all pattern elements.

ステップS21において、対応要素計算部14は、現在選択されているパタン要素を、現在の変換係数Tを用いて、対象データ要素の空間に変換し、変換した要素と類似度の高い対象データ要素を計算する。ステップS22において、対応関係効果計算部15は、対応要素との類似度を配慮し、行列Bおよび行列Dを更新する。   In step S21, the corresponding element calculation unit 14 converts the currently selected pattern element into the space of the target data element using the current conversion coefficient T, and selects the target data element having a high similarity to the converted element. calculate. In step S22, the correspondence relationship effect calculation unit 15 updates the matrix B and the matrix D in consideration of the similarity with the corresponding element.

ステップS23において、対応関係効果計算部15は、対応要素との類似度を配慮し、スコアを更新する(たとえば、値1を加算する)。ステップS24において、判定部31は、スコアがパタン要素に対応する移動閾値より、スコアが小さいか否かを判定し、スコアが移動閾値より低ければ(小さいと判定された場合)、ループ4とループ3を中断して処理はステップS29に進む。   In step S <b> 23, the correspondence effect calculation unit 15 updates the score (for example, adds a value of 1) in consideration of the degree of similarity with the corresponding element. In step S24, the determination unit 31 determines whether or not the score is smaller than the movement threshold corresponding to the pattern element. If the score is lower than the movement threshold (if determined to be smaller), the loop 4 and the loop 3 is interrupted, and the process proceeds to step S29.

ステップS26において、パラメータ/変換係数更新部16は、最小二乗法にて係数ベクトルUを更新して、変換係数Tを更新する。   In step S26, the parameter / transform coefficient updating unit 16 updates the transform coefficient T by updating the coefficient vector U by the least square method.

ステップS28において、計算されたスコアが入力スコア閾値以上の場合、ポーズリスト生成部17は、(変換係数T、スコア)を出力リストに追加する。   In step S28, when the calculated score is equal to or greater than the input score threshold, the pose list generation unit 17 adds (conversion coefficient T, score) to the output list.

ステップS31において、ポーズリスト生成部17は、ポーズのリストとして出力リストを返して、検索の処理は終了する。   In step S31, the pose list generation unit 17 returns the output list as a pose list, and the search process ends.

なお、ステップS23のスコアの更新は、足し算に限られるものではない。例えば、通常のパタン要素の場合、類似度の高い対応要素があれば、スコアを引き上げ、類似度の高い対応要素が無ければ、変更しないとする。また、例えば、マッチング機能において重要性の高いパタン要素の場合、類似度の高い対応点があれば、スコアを変更せず、類似度の高い対応点が無ければスコアを0とする。また、例えば他のパタンと識別するためのパタン要素であれば、類似度の高い対応要素があれば、スコアを引き下げて、類似度の高い対応要素が無ければ、変更しないようにしてもよい。   Note that the update of the score in step S23 is not limited to addition. For example, in the case of a normal pattern element, if there is a corresponding element with a high degree of similarity, the score is raised, and if there is no corresponding element with a high degree of similarity, no change is made. For example, in the case of a pattern element having high importance in the matching function, if there is a corresponding point having a high degree of similarity, the score is not changed, and if there is no corresponding point having a high degree of similarity, the score is set to 0. Further, for example, if there is a pattern element for identifying another pattern, if there is a corresponding element with a high degree of similarity, the score may be lowered, and if there is no corresponding element with a high degree of similarity, it may not be changed.

以上のように、スコアがパタンの要素の移動閾値より、スコアが小さいか否かを判定し(たとえば、図2のS24の処理)、スコアが移動閾値より小さいと判定された場合、ループ4とループ3を中断するようにしたので、処理を迅速に行うことができる。   As described above, it is determined whether or not the score is smaller than the movement threshold value of the pattern element (for example, the process of S24 in FIG. 2), and when it is determined that the score is smaller than the movement threshold value, Since the loop 3 is interrupted, the processing can be performed quickly.

図4は、検索の処理の他の例を説明するフローチャートである。   FIG. 4 is a flowchart for explaining another example of the search processing.

ステップS51において、検索装置は、変換係数Tの入力変換係数リスト、パタン、対象データ、およびスコア閾値を入力する。ステップS52において、移動閾値計算部11は、パタンに含まれる要素に順に付加されたインデックスであるパタン要素インデックスの値に対して単調非減少の値となる移動閾値を計算する。   In step S51, the search apparatus inputs an input conversion coefficient list, pattern, target data, and score threshold value of the conversion coefficient T. In step S52, the movement threshold value calculation unit 11 calculates a movement threshold value that is a monotonous non-decreasing value with respect to the value of the pattern element index, which is an index that is sequentially added to the elements included in the pattern.

ステップS53とステップS71とは、ループ1の処理とされ、入力変換係数リストの変換係数Tを全て選択するまで、ステップS54〜ステップS70の処理が繰り返される。   Step S53 and step S71 are processing of loop 1, and the processing of step S54 to step S70 is repeated until all the conversion coefficients T in the input conversion coefficient list are selected.

ステップS54において、検索装置は、入力変換係数リストの変換係数Tを1つ選ぶ。   In step S54, the search device selects one conversion coefficient T in the input conversion coefficient list.

ステップS55とステップS70とは、ループ2の処理とされ、対象データの全ての要素が選択されるまで、ステップS56〜ステップS69の処理が繰り返される。   Steps S55 and S70 are loop 2 processes, and the processes of steps S56 to S69 are repeated until all elements of the target data are selected.

ステップS56において、検索装置は、対象データの要素を選ぶ。   In step S56, the search device selects an element of the target data.

ステップS57において、変換係数計算部12は、パタンの最初の要素であるパタン要素0と選択された対象データの要素と選択された変換係数Tから、パタン要素0が選択された対象データの要素と類似度の高い要素に変換される様に、変換係数Tを計算する(例えば、変換係数Tの中で移動量を表す移動量Vを計算してTに設定する)。   In step S57, the transform coefficient calculation unit 12 selects the pattern element 0 that is the first element of the pattern, the element of the selected target data, and the element of the target data for which the pattern element 0 is selected from the selected transform coefficient T. A conversion coefficient T is calculated so as to be converted into an element having a high degree of similarity (for example, a movement amount V representing a movement amount in the conversion coefficient T is calculated and set to T).

ステップS58において、初期値設定部13は、行列Bおよび行列Dを初期化する。
この場合、行列Bには、対角行列が設定されて初期化される。対角行列の要素は更新係数ベクトルUの要素の重みである。例えば、式(1)から式(31)を参照して上述したように3D対象データの中から3Dパタンを検索する場合は、式(32)に示されるように対角行列が設定される。式(32)において、w,w,wは回転の重み、w,w,wは移動量の重み、wは、スケールについての重みであり、それらの値を調整することにより、たとえば、回転を制限することもできる。

Figure 2013025662
・・・(32) In step S58, the initial value setting unit 13 initializes the matrix B and the matrix D.
In this case, the matrix B is initialized by setting a diagonal matrix. The elements of the diagonal matrix are the weights of the elements of the update coefficient vector U. For example, when a 3D pattern is searched from 3D target data as described above with reference to equations (1) to (31), a diagonal matrix is set as shown in equation (32). In Expression (32), w a , w b , and w c are weights for rotation, w x , w y , and w z are weights for movement, and w s is a weight for the scale, and these values are adjusted. Thus, for example, rotation can be limited.
Figure 2013025662
... (32)

更に、ステップS58において、初期値設定部13は、スコアを0に初期化し、パタン要素インデックスを示すパタン要素インデックス変数i を0に初期化し、整数である変数 N を0に初期化する。   Further, in step S58, the initial value setting unit 13 initializes the score to 0, initializes a pattern element index variable i indicating a pattern element index to 0, and initializes a variable N that is an integer to 0.

ステップS59とステップS68とは、ループ3の処理とされ、ステップS67でパタン要素インデックスiが変数Nより高い値となるまで、ステップS60〜ステップS67の処理が繰り返される。   Step S59 and step S68 are processing of loop 3, and the processing of step S60 to step S67 is repeated until the pattern element index i becomes a value higher than the variable N in step S67.

ステップS60において、対応要素計算部14は、パタン要素インデックスiで選択されているパタン要素を、現在の変換係数Tを用いて、対象データ要素の空間に変換し、変換した要素と類似度の高い対象データ要素を計算する。   In step S60, the corresponding element calculation unit 14 converts the pattern element selected by the pattern element index i into the space of the target data element using the current conversion coefficient T, and has high similarity to the converted element. Calculate the target data element.

ステップS61において、対応関係効果計算部15は、対応要素との類似度を配慮し、行列Bおよび行列Dを更新する。ステップS62において、対応関係効果計算部15は、対応要素との類似度を配慮し、スコアを更新する(たとえば、値1を加算する)。   In step S61, the correspondence relationship effect calculation unit 15 updates the matrix B and the matrix D in consideration of the similarity with the corresponding element. In step S62, the correspondence effect calculation unit 15 updates the score (for example, adds a value of 1) in consideration of the similarity with the corresponding element.

ステップS63において、判定部31は、スコアがパタン要素に対応する移動閾値より、スコアが小さいか否かを判定し、スコアが移動閾値より低ければ(小さいと判定された場合)、ループ3を中断して処理はステップS70に進む。   In step S63, the determination unit 31 determines whether the score is smaller than the movement threshold corresponding to the pattern element. If the score is lower than the movement threshold (if it is determined to be smaller), the loop 3 is interrupted. Then, the process proceeds to step S70.

ステップS64において、判定部31は、予め定められた微調整条件が満たされたか否かを判定する。例として、微調整条件は、最後の微調整から類似度の高い対応要素が見つかった事と、パタン要素インデックスiが変数Nに等しい事である。   In step S64, the determination unit 31 determines whether or not a predetermined fine adjustment condition is satisfied. As an example, the fine adjustment condition is that a corresponding element having a high similarity is found from the last fine adjustment, and that the pattern element index i is equal to the variable N.

ステップS64において、微調整条件が満たされたと判定された場合、手続きはステップS65に進み、パラメータ/変換係数更新部16は、最小二乗法にて更新係数ベクトルUを更新して、変換係数Tを更新する。ステップS66において、パラメータ/変換係数更新部16は、行列B、行列D、変数Nを更新し、手続きはステップS67に進む。   If it is determined in step S64 that the fine adjustment condition is satisfied, the procedure proceeds to step S65, and the parameter / transform coefficient updating unit 16 updates the update coefficient vector U by the least square method to obtain the transform coefficient T. Update. In step S66, the parameter / transform coefficient updating unit 16 updates the matrix B, the matrix D, and the variable N, and the procedure proceeds to step S67.

ここで、行列Bは、係数ベクトルUの係数の間の柔軟性を示し、行列Dは、誤差の小さくなる位置を示す。ステップS66における、行列Bおよび行列Dの更新方法は、例えば、行列Bおよび行列Dが先ず初期化され、そしてパタン要素0から微調整時のパタン要素インデックスiのパタン要素、現在の変換係数Tを用いて、パタン要素を対象データ空間に変換して、類似度の高い対象データ要素を計算して、その類似度を配慮して行列Bおよび行列Dが更新される。すなわち、更新された変換係数Tを用いて、行列Bと行列Dが正確に再計算される。なお詳細に、この再計算の処理に、対応要素計算のステップにおいて、対応要素を探索しても良いし、前回の微調整時に見つけた対象データの対応要素を使っても良い。また、行列Bおよび行列Dの再計算に、更新された変換係数Tの微分を計算して使用しても良いし、更新される前の変換係数Tの微分を使用しても良い。   Here, the matrix B indicates the flexibility between the coefficients of the coefficient vector U, and the matrix D indicates the position where the error is reduced. In the updating method of the matrix B and the matrix D in step S66, for example, the matrix B and the matrix D are first initialized, and the pattern element of the pattern element index i at the time of fine adjustment from the pattern element 0, the current conversion coefficient T is obtained. The pattern element is converted into the target data space, the target data element having a high similarity is calculated, and the matrix B and the matrix D are updated in consideration of the similarity. That is, the matrix B and the matrix D are accurately recalculated using the updated conversion coefficient T. More specifically, in this recalculation process, a corresponding element may be searched for in the corresponding element calculation step, or a corresponding element of the target data found during the previous fine adjustment may be used. In addition, for recalculation of the matrix B and the matrix D, the updated derivative of the transform coefficient T may be calculated and used, or the derivative of the transform coefficient T before being updated may be used.

また、ステップ66における行列Bおよび行列Dの更新方法の例として、行列Bに、式(32)に示される様な対角行列を設定し、行列Dに、0を設定するようにしてもよい。すなわち、微調整までのマッチング情報を捨てて、初期化された状態に今後のマッチング情報を格納する。   Further, as an example of the updating method of the matrix B and the matrix D in step 66, a diagonal matrix as shown in the equation (32) may be set in the matrix B, and 0 may be set in the matrix D. . That is, the matching information up to fine adjustment is discarded, and future matching information is stored in an initialized state.

さらに、ステップ66における行列Bおよび行列Dの更新方法の例として、行列Bをそのままとし、行列Dに0を設定するようにしてもよい。すなわち、微調整までの誤差情報を捨てて、柔軟性の情報を今後のマッチングで使用するものである。   Furthermore, as an example of the updating method of the matrix B and the matrix D in step 66, the matrix B may be left as it is and 0 may be set to the matrix D. That is, the error information up to the fine adjustment is discarded and the flexibility information is used in future matching.

さらにまた、ステップ66における行列Bおよび行列Dの更新方法の例として、行列Bをそのままとし、行列Dに、行列Bに更新係数ベクトルUを乗算して得られた積をそれまでの行列Dから引き算して得られた差を設定するようにしても良い。すなわち、微調整までの柔軟性の情報を保ち、誤差情報を更新された更新係数ベクトルUに合わせるものである。   Furthermore, as an example of the updating method of the matrix B and the matrix D in step 66, the matrix B is left as it is, and the product obtained by multiplying the matrix D by the update coefficient vector U to the matrix D is calculated from the matrix D so far. A difference obtained by subtraction may be set. That is, flexibility information up to fine adjustment is maintained, and error information is matched with the updated update coefficient vector U.

ステップS64において、微調整条件が満たされていないと判定された場合、ステップS65およびステップS66の手続きはスキップされて、手続きはステップS67に進む。   If it is determined in step S64 that the fine adjustment condition is not satisfied, the procedures in steps S65 and S66 are skipped, and the procedure proceeds to step S67.

ステップS67において、パラメータ/変換係数更新部16は、変数Nを更新する。具体的には、変数Nがパタン要素の数より小さい場合、1だけインクリメントされるように、変数Nが更新される。なお、例えば2または3だけインクリメントされるように、変数Nが更新されるようにしてもよい。   In step S67, the parameter / conversion coefficient updating unit 16 updates the variable N. Specifically, when the variable N is smaller than the number of pattern elements, the variable N is updated so that it is incremented by one. Note that the variable N may be updated so as to be incremented by 2 or 3, for example.

またパラメータ/変換係数更新部16は、パタン要素インデックスiを更新する。より具体的には、微調整が行われた場合、パタン要素インデックスiが0とされ、他の場合、パタン要素インデックスiが1だけインクリメントされるように、パタン要素インデックスiが更新される。なお、パタン要素インデックスiのインクリメントは、例えば2または3だけインクリメントされるようにしてもよい。   The parameter / transform coefficient updating unit 16 updates the pattern element index i. More specifically, the pattern element index i is updated so that the pattern element index i is 0 when fine adjustment is performed, and the pattern element index i is incremented by 1 in other cases. The pattern element index i may be incremented by 2 or 3, for example.

ステップS69において、ポーズリスト生成部17は、スコアが入力スコア閾値以上である場合、(変換係数T、スコア)を出力リストに追加する。ステップS72において、ポーズリスト生成部17は、ポーズのリストとして出力リストを返す。   In step S69, the pose list generation unit 17 adds (conversion coefficient T, score) to the output list when the score is equal to or greater than the input score threshold. In step S72, the pose list generation unit 17 returns an output list as a list of poses.

ループ1から抜けた場合、検索の処理は終了する。   When the loop 1 is exited, the search process ends.

この様に、この例でループ3の最初のループでは、N=0、i =0、最初のパタン要素がマッチされる。ステップS64で微調整が行われたとする。するとステップS67で、N=1、i=0に更新が行われるので、次に、ループ3では、パタンの最初の二つの要素(i=0とi=1)がマッチされる。ステップS64で微調整が行われたとする。するとステップS68で N=2,i=0に更新が行われるので、次に、ループ3では、パタンの最初の三つの要素(i=0..2)がマッチされる。すなわち、段々微調整に使われるパタン要素数を増やしながら微調整が続けられる。   Thus, in this example, in the first loop of loop 3, N = 0, i = 0, the first pattern element is matched. It is assumed that fine adjustment is performed in step S64. In step S67, N = 1 and i = 0 are updated. Next, in loop 3, the first two elements (i = 0 and i = 1) of the pattern are matched. It is assumed that fine adjustment is performed in step S64. Then, since N = 2 and i = 0 are updated in step S68, next, in the loop 3, the first three elements (i = 0..2) of the pattern are matched. That is, fine adjustment is continued while increasing the number of pattern elements used for fine adjustment step by step.

なお、ステップS58において、変数Nが、パタン要素数に初期化され、ステップS64における微調整条件を、パタン要素インデックスiがある整数kの倍数である事とし、ステップS67において、1だけインクリメントされるようにパタン要素インデックスiが更新されるようにし、ステップS67において変数Nを変更しない様にしてもよい。この場合、パタン要素を1つずつ処理して、パタン要素インデックスiがkの倍数になっている時のみに微調整が行われる。全てのパタン要素は1回だけ処理されるので処理速度は速い。なお、この場合、ステップS64における微調整条件を、パタン要素インデックスiがパタン作成時に決まった微調整パタン要素インデックスの1つとするようにしてもよい。例えば、形状を現すパタンの場合、パタンの曲率の高い部分では、低い部分より頻繁に微調整を行う必要があると考えられ、曲率をパタン作成時に計算して、曲率が高いパタン要素のパタン要素インデックスiを微調整インデックスリストに追加して、微調整条件を、パタン要素インデックスiが、微調整インデックスリストに含まれていることとする。   In step S58, the variable N is initialized to the number of pattern elements, and the fine adjustment condition in step S64 is a pattern element index i that is a multiple of an integer k. In step S67, the variable N is incremented by one. Thus, the pattern element index i may be updated, and the variable N may not be changed in step S67. In this case, the pattern elements are processed one by one and fine adjustment is performed only when the pattern element index i is a multiple of k. Since all pattern elements are processed only once, the processing speed is fast. In this case, the fine adjustment condition in step S64 may be one of the fine adjustment pattern element indexes determined when the pattern element index i is created. For example, in the case of a pattern that expresses a shape, it is considered that fine adjustment is required more frequently in the portion where the curvature of the pattern is higher than in the lower portion, and the curvature is calculated when the pattern is created. The index i is added to the fine adjustment index list, and the fine adjustment condition is that the pattern element index i is included in the fine adjustment index list.

さらに、ステップS59において、変数Nが、パタン要素数に初期化され、ステップS64における微調整条件を、最初の微調整から集めた対応する要素ペアの最小類似度または平均類似度が閾値を下回ることとし、ステップS67において変数Nを更新しない様にし、さらに、ステップ67において、1だけインクリメントされるようにパタン要素インデックスiが更新されるようにしてもよい。この場合、対応要素との類似度が低すぎると微調整を行い、必要な時だけに微調整を行うというアプローチである。なお、この場合、微調整を行ったとき、微調整時のパタン要素インデックスiを保存して、パタン要素インデックスiを0に更新し、パタン要素インデックスiが保存した値を超えるまで微調整を無効にするようにしてもよい。   Further, in step S59, the variable N is initialized to the number of pattern elements, and the minimum similarity or the average similarity of the corresponding element pair collected from the first fine adjustment is less than the threshold value in the fine adjustment condition in step S64. In step S67, the variable N may not be updated. In step 67, the pattern element index i may be updated so as to be incremented by one. In this case, the approach is to perform fine adjustment when the degree of similarity with the corresponding element is too low, and to perform fine adjustment only when necessary. In this case, when fine adjustment is performed, the pattern element index i at the time of fine adjustment is stored, the pattern element index i is updated to 0, and fine adjustment is invalidated until the pattern element index i exceeds the stored value. You may make it.

以上で説明した、微調整条件の具体例と更新処理とを組み合わせるようにしてもよい。   The specific example of the fine adjustment condition described above and the update process may be combined.

また、パタン要素の順番を付ける方法には、例えば、未だ選択されていない要素の中からパタン要素0に最も類似度の高い要素をパタン要素iとするものがある。さらに、パタン要素の順番を付ける方法には、未だ選択されていない要素の中からパタン要素i−1に最も類似度の高い要素をパタン要素iとする方法もある。   In addition, as a method of assigning the order of pattern elements, for example, an element having the highest similarity to the pattern element 0 among elements not yet selected is used as the pattern element i. Further, as a method of assigning the order of pattern elements, there is a method in which an element having the highest similarity to the pattern element i-1 is selected as a pattern element i from elements not selected yet.

パタン要素の順番付けと移動閾値の採用により、仮に、パタン要素0に対応する要素が対象データに含まれていればパタンが検索される可能性は高い。しかし、パタン要素0に対応する要素が対象データに含まれていない場合、検索される可能性は低くなる。そこで、オーバーサンプリングの手法を採用する。すなわち、1つのパタンを複数のパタンとして扱う。但し、複数のパタンのそれぞれの最初の要素であるパタン要素0を異なる要素とする。これにより、隠蔽の影響により検索が失敗してしまう可能性が低くなる。   By adopting the pattern element ordering and the movement threshold, if the element corresponding to the pattern element 0 is included in the target data, the pattern is likely to be searched. However, if the element corresponding to the pattern element 0 is not included in the target data, the possibility of searching is low. Therefore, an oversampling technique is adopted. That is, one pattern is handled as a plurality of patterns. However, pattern element 0 which is the first element of each of a plurality of patterns is a different element. This reduces the possibility that the search will fail due to the influence of concealment.

オーバーサンプリングの手法における複数のパタン(以下、オーバーサンプリングパタンと称する)からのパタン要素0の決定は次のように行われる。すなわち、オーバーサンプリングパタンの数の削減を目指し、オーバーサンプリングパタンのパタン要素0を、対象データに含まれている可能性が高い要素にする。例えば、3D点から出来ているパタンの場合は、オーバーサンプリングパタンのパタン点0を、出来るだけ沢山の方向から見えるパタン点にすれば良い。また、パタンリンク法(以下で説明する)にて形の相似を利用し、出来るだけ他の部分に似ている部分の中心に近い点をパタン点0とするようにしてもよい。さらに、マッチングフェースで場所が違えばすぐにスコアが移動閾値を下回るように、出来るだけ特殊な形の部分の中心に近い点をパタン点0とするようにしてもよい。   Determination of pattern element 0 from a plurality of patterns (hereinafter referred to as oversampling pattern) in the oversampling technique is performed as follows. That is, with the aim of reducing the number of oversampling patterns, the pattern element 0 of the oversampling pattern is made an element that is highly likely to be included in the target data. For example, in the case of a pattern made of 3D points, the pattern point 0 of the oversampling pattern may be a pattern point that can be seen from as many directions as possible. In addition, a pattern link method (described below) may be used to make the pattern point 0 a point as close as possible to the center of a part that resembles another part as much as possible. Furthermore, a pattern point 0 may be set as close to the center of the specially shaped portion as possible so that the score falls below the movement threshold as soon as the location of the matching face is different.

また、3Dパタンの場合は、計測器(例えばカメラや距離センサー)とワークの位置関係により、対象データに穴や隠蔽があることがある。これを配慮しないと、仮に綺麗な計測データがあっても、スコアが下がって、安定した検索が不可能になる。この場合、計測器とワークの位置関係依存のパタンを定義する。すなわち、パタンの中に沢山の視点パタンを設ける。より詳細には、計測器とワークの位置関係をサンプリングして隠蔽のない3Dパタンから見える部分を計算して視点パタンに保存する。   In the case of a 3D pattern, there may be a hole or concealment in the target data depending on the positional relationship between the measuring instrument (for example, camera or distance sensor) and the workpiece. If this is not taken into consideration, even if there is clean measurement data, the score will drop and stable search will be impossible. In this case, a pattern dependent on the positional relationship between the measuring instrument and the workpiece is defined. That is, many viewpoint patterns are provided in the pattern. More specifically, the positional relationship between the measuring instrument and the workpiece is sampled, and the portion that can be seen from the 3D pattern without concealment is calculated and stored in the viewpoint pattern.

また変換係数Tによって視点パタンが選択されるようにすることもできる。すなわち、変換係数Tと計測器位置Pから暫定の位置関係を計算し、その位置関係に最も近い位置関係の視点パタンを選択することができる。   The viewpoint pattern can also be selected by the conversion coefficient T. That is, a temporary positional relationship can be calculated from the conversion coefficient T and the measuring instrument position P, and a viewpoint pattern having a positional relationship closest to the positional relationship can be selected.

また、オーバーサンプリングパタンの導入により、パタンの数が増えて実行時間が長くなってしまうこともある。仮に、複数のパタンでパタン要素0の周りが似れば、それを1回だけマッチングすれば十分のはずである。   In addition, the introduction of the oversampling pattern may increase the number of patterns and increase the execution time. If the surroundings of pattern element 0 are similar in a plurality of patterns, it should be sufficient to match them only once.

仮に、視点パタン1のオーバーサンプリングパタン2の要素0〜要素10が視点パタン3のオーバーサンプリングパタン4の要素0〜要素10とほとんど同じだとする。視点パタン1のオーバーサンプリングパタン2から視点パタン3のオーバーサンプリングパタン4の間の変換Gが計算される。視点パタン3のオーバーサンプリングパタン4を祖サーチの中でパタン要素0から使わないようにする。祖サーチで視点パタン1のオーバーサンプリングパタン2でパタン要素10までマッチングされたポーズがあれば、そのポーズに計算した変換Gをかけて、祖サーチの中で視点パタン3のオーバーサンプリングパタン4でもマッチングを続けるようにする。すなわち、視点パタン1のオーバーサンプリングパタン2のパタン要素インデックス10に視点パタン3のオーバーサンプリングパタン4へのリンクが付けられ、そのリンクに対応付けて計算した変換Gが保存される。   Assume that the elements 0 to 10 of the oversampling pattern 2 of the viewpoint pattern 1 are almost the same as the elements 0 to 10 of the oversampling pattern 4 of the viewpoint pattern 3. A transformation G between the oversampling pattern 2 of the viewpoint pattern 1 and the oversampling pattern 4 of the viewpoint pattern 3 is calculated. The oversampling pattern 4 of the viewpoint pattern 3 is not used from the pattern element 0 in the ancestor search. If there is a pose matched up to the pattern element 10 with the oversampling pattern 2 of the viewpoint pattern 1 in the ancestor search, the calculated transformation G is applied to the pose, and the oversampling pattern 4 of the viewpoint pattern 3 is also matched in the ancestor search. To continue. That is, a link to the oversampling pattern 4 of the viewpoint pattern 3 is attached to the pattern element index 10 of the oversampling pattern 2 of the viewpoint pattern 1, and the conversion G calculated in association with the link is stored.

なお、以上においては、図2のステップS11または図4のステップS51で入力される変換係数リストについて言及しなかったが、その作成方法について説明する。例えば、検索空間が3次元空間の場合は、3D回転空間とスケールはサンプリングされる。移動量Vは0に初期化され、実際にマッチングの時に(図2のステップS17または図4のステップS57)パタン要素0の3D座標と対象データの対応する要素の3D座標から移動量Vが計算される。このように得られたパラメータにより変換係数リストが作成される。サンプリングの刻みを大きくすることができたので、リストの長さが短くなる。   In the above description, the conversion coefficient list input in step S11 in FIG. 2 or step S51 in FIG. 4 has not been mentioned, but a method for creating it will be described. For example, when the search space is a three-dimensional space, the 3D rotation space and the scale are sampled. The movement amount V is initialized to 0, and the actual movement amount V is calculated from the 3D coordinates of the pattern element 0 and the corresponding element of the target data at the time of matching (step S17 in FIG. 2 or step S57 in FIG. 4). Is done. A conversion coefficient list is created based on the parameters thus obtained. Since the sampling interval can be increased, the length of the list is shortened.

更に、実行時間を改良するためピラミッドの概念を導入する事が可能である。マルチレベルピラミッドとして、パタンの要素群と対象データの要素群をサブサンプリングして、ピラミッドを作成する。祖サーチは、ピラミッドのうち、圧縮率が高いレベルで実行される。精サーチは、各ポーズを圧縮率が高いレベルから段々に圧縮率が低いレベルまで検索される。ピラミッドレベルを変える時にポーズのフィルタリングを行う事ができる。例えば、ほとんど同じポーズがあれば(たとえば、変換係数の移動量等、間の角度をみて、あれが近いと判断したら消す)、その中で一番スコアの高いポーズ以外のポーズを削除する。   Furthermore, it is possible to introduce the concept of a pyramid to improve the execution time. As a multi-level pyramid, a pyramid is created by sub-sampling the pattern element group and the target data element group. The ancestor search is executed at a high compression level in the pyramid. In the fine search, each pose is searched from a level with a high compression rate to a level with a gradually low compression rate. Pause filtering can be performed when changing pyramid levels. For example, if there is almost the same pose (for example, if it is determined that it is close by looking at the angle between the conversion coefficients, etc.), the pose other than the pose with the highest score is deleted.

以上のように、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる。   As described above, the answer can be found while increasing the sampling interval as much as possible to shorten the execution time.

上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。   The series of processes described above can be executed by hardware or can be executed by software. When a series of processing is executed by software, a program constituting the software executes various functions by installing a computer incorporated in dedicated hardware or various programs. For example, it is installed from a program recording medium in a general-purpose personal computer or the like.

図5は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。   FIG. 5 is a block diagram illustrating an example of a hardware configuration of a computer that executes the above-described series of processes using a program.

コンピュータにおいて、CPU(Central Processing Unit)101,ROM(Read Only Memory)102,RAM(Random Access Memory)103は、バス104により相互に接続されている。   In a computer, a CPU (Central Processing Unit) 101, a ROM (Read Only Memory) 102, and a RAM (Random Access Memory) 103 are connected to each other via a bus 104.

バス104には、さらに、入出力インタフェース105が接続されている。入出力インタフェース105には、キーボード、マウス、カメラなどよりなる入力部106、ディスプレイ、スピーカなどよりなる出力部107、ハードディスクや不揮発性のメモリなどよりなる記憶部108、ネットワークインタフェースなどよりなる通信部109、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア111を駆動するドライブ110が接続されている。   An input / output interface 105 is further connected to the bus 104. The input / output interface 105 includes an input unit 106 including a keyboard, a mouse, and a camera, an output unit 107 including a display and a speaker, a storage unit 108 including a hard disk and a non-volatile memory, and a communication unit 109 including a network interface. A drive 110 for driving a removable medium 111 such as a magnetic disk, an optical disk, a magneto-optical disk, or a semiconductor memory is connected.

以上のように構成されるコンピュータでは、CPU101が、例えば、記憶部108に記憶されているプログラムを、入出力インタフェース105及びバス104を介して、RAM103にロードして実行することにより、上述した一連の処理が行われる。   In the computer configured as described above, the CPU 101 loads, for example, the program stored in the storage unit 108 to the RAM 103 via the input / output interface 105 and the bus 104 and executes the program. Is performed.

コンピュータ(CPU101)が実行するプログラムは、例えば、磁気ディスク(フレキシブルディスクを含む)、光ディスク(CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)等)、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア111に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。   The program executed by the computer (CPU 101) is, for example, a magnetic disk (including a flexible disk), an optical disk (CD-ROM (Compact Disc-Read Only Memory), DVD (Digital Versatile Disc), etc.), a magneto-optical disk, or a semiconductor. The program is recorded on a removable medium 111 that is a package medium including a memory or the like, or is provided via a wired or wireless transmission medium such as a local area network, the Internet, or digital satellite broadcasting.

そして、プログラムは、リムーバブルメディア111をドライブ110に装着することにより、入出力インタフェース105を介して、記憶部108に記憶することで、コンピュータにインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部109で受信し、記憶部108に記憶することで、コンピュータにインストールすることができる。その他、プログラムは、ROM102や記憶部108にあらかじめ記憶しておくことで、コンピュータにあらかじめインストールしておくことができる。   The program can be installed in the computer by loading the removable medium 111 in the drive 110 and storing it in the storage unit 108 via the input / output interface 105. Further, the program can be installed in a computer by being received by the communication unit 109 via a wired or wireless transmission medium and stored in the storage unit 108. In addition, the program can be installed in the computer in advance by storing the program in the ROM 102 or the storage unit 108 in advance.

なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。   The program executed by the computer may be a program that is processed in time series in the order described in this specification, or in parallel or at a necessary timing such as when a call is made. It may be a program for processing.

また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。また、式(1)〜式(31)は3Dパタンを3D対象データから検索する場合使用出来る式だが、本発明は式(1)〜式(31)の使用に限定されていない、また3Dパタンを3D対象データから検出する場合に限定されるものではない。変換係数とパタンの要素から出来ている空間から、対象データの要素の空間への変換関数がある場合、そして検索範囲が限られているなら、本発明にてパタンを対象データから検出する事が可能である。また、パタンを構成する要素群は、複数の種類の要素が使われる事が可能である。同じ様に、対象データを構成する要素群は、複数の種類の要素が使われる事が可能である。例えば、3Dパタンの場合、パタンが面を表すノーマルベクトル付の3次元点群と縁を表す3D点群で構成されている場合、それらの要素の種類に基づいて、対応要素検索や対応関係効果計算が行われる。   The embodiments of the present invention are not limited to the above-described embodiments, and various modifications can be made without departing from the scope of the present invention. Moreover, although Formula (1)-Formula (31) are formulas which can be used when searching 3D pattern from 3D object data, this invention is not limited to use of Formula (1)-Formula (31), Moreover, 3D pattern However, the present invention is not limited to the case of detecting 3D target data. If there is a conversion function from the space made up of the conversion coefficient and the pattern element to the space of the element of the target data, and if the search range is limited, the present invention can detect the pattern from the target data. Is possible. In addition, a plurality of types of elements can be used for the element group constituting the pattern. Similarly, a plurality of types of elements can be used for the element group constituting the target data. For example, in the case of a 3D pattern, when the pattern is composed of a 3D point cloud with a normal vector representing a surface and a 3D point cloud representing an edge, the corresponding element search and the corresponding relationship effect are performed based on the types of those elements. Calculation is performed.

11…移動閾値計算部、12…変換係数計算部、13…初期値設定部、14…対応点検索部、15…スコア更新部、16…パラメータ/変換係数更新部、17…ポーズリスト生成部、31…判定部、101…CPU、102…ROM、103…RAM、108…記憶部、111…リムーバブルメディア   DESCRIPTION OF SYMBOLS 11 ... Movement threshold value calculation part, 12 ... Conversion coefficient calculation part, 13 ... Initial value setting part, 14 ... Corresponding point search part, 15 ... Score update part, 16 ... Parameter / conversion coefficient update part, 17 ... Pause list generation part, 31 ... Determining unit, 101 ... CPU, 102 ... ROM, 103 ... RAM, 108 ... Storage unit, 111 ... Removable media

Claims (8)

特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと上記パタンの特徴量の空間と変換係数から上記対象データの特徴量の空間への変換関数とから、上記パタンを上記変換関数で変換した要素群が上記対象データの要素群と高い類似度となるように上記変換関数の変換係数を算出する検索方法において、
上記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、
上記パタンの最初とされた要素と上記対象データの所定の要素とから暫定の変換係数Tを計算する変換係数計算ステップと、
上記変換係数Tを用いて、上記パタンの要素毎に、上記変換関数で変換された上記パタンの要素と上記対象データとのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算ステップと、
上記スコアが更新されたときの上記パタンの要素の上記移動閾値より、更新された上記スコアが小さいか否かを判定する判定ステップと、
更新された上記スコアが上記パタンの要素の上記移動閾値以上であると判定された場合、更新係数ベクトルUおよび上記変換係数Tを更新する変換係数更新ステップと
を含み、
更新された上記スコアが上記移動閾値より小さいと判定された場合、上記対象データの次の要素に対して、または上記の次の暫定の変換係数Tに対して、上記検索方法の手順を施す
ことを特徴とする検索方法。
From the pattern that is the element group that represents the feature quantity, the target data that is the element group that represents the feature quantity, the space of the feature quantity of the pattern and the conversion function from the conversion coefficient to the feature quantity space of the target data, the pattern is In the search method for calculating the conversion coefficient of the conversion function so that the element group converted by the conversion function has a high similarity with the element group of the target data,
A threshold calculation step for calculating a movement threshold value that is a monotonically non-decreasing value with respect to the index value sequentially added to the elements included in the pattern;
A conversion coefficient calculation step for calculating a provisional conversion coefficient T from the first element of the pattern and the predetermined element of the target data;
Using the conversion coefficient T, the score, matrix B, and matrix D are updated for each element of the pattern in consideration of the degree of matching between the pattern element converted by the conversion function and the target data. A correspondence effect calculation step;
A determination step of determining whether or not the updated score is smaller than the movement threshold value of the pattern element when the score is updated;
A conversion coefficient update step of updating the update coefficient vector U and the conversion coefficient T when it is determined that the updated score is equal to or greater than the movement threshold value of the pattern element;
When it is determined that the updated score is smaller than the movement threshold, the search method procedure is performed on the next element of the target data or the next provisional transformation coefficient T. A search method characterized by
請求項1に記載の検索方法において、
前記行列Bと前記行列Dを更新する前に、前記更新係数ベクトルUの係数の間の柔軟性を示す前記行列Bに初期値として対角行列を設定する設定ステップをさらに含み、
前記変換係数更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記更新係数ベクトルUおよび前記変換係数Tが更新される
ことを特徴とする検索方法。
The search method according to claim 1,
Before updating the matrix B and the matrix D, further comprising a setting step of setting a diagonal matrix as an initial value in the matrix B indicating flexibility between the coefficients of the update coefficient vector U;
In the transform coefficient updating step, when it is determined that the updated score is equal to or greater than the movement threshold value, the update coefficient vector U and the transform coefficient T are satisfied when a condition for performing a predetermined fine adjustment is satisfied. A search method characterized in that is updated.
請求項2に記載の検索方法において、
前記変換係数更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記行列Bに前記対角行列が設定され、誤差の小さくなる位置を示す行列Dに0が設定される
ことを特徴とする検索方法。
The search method according to claim 2,
In the transform coefficient update step, when it is determined that the updated score is equal to or greater than the movement threshold, the diagonal matrix is set in the matrix B when a predetermined condition for fine adjustment is satisfied. The search method is characterized in that 0 is set in the matrix D indicating the position where the error is reduced.
請求項2に記載の検索方法において、
前記変換行列更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記行列Bがそのままとされ、誤差の小さくなる位置を示す行列Dに0が設定される
ことを特徴とする検索方法。
The search method according to claim 2,
In the transformation matrix update step, when it is determined that the updated score is equal to or greater than the movement threshold, the matrix B is left as it is when a predetermined condition for fine adjustment is satisfied, and an error A search method characterized in that 0 is set in the matrix D indicating the position where it becomes smaller.
請求項2に記載の検索方法において、
前記変換行列更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記行列Bがそのままとされ、誤差の小さくなる位置を示す行列Dに、前記行列Bに前記係数ベクトルUを乗算して得られた積をそれまでの行列Dから引き算して得られた差が設定される
ことを特徴とする検索方法。
The search method according to claim 2,
In the transformation matrix update step, when it is determined that the updated score is equal to or greater than the movement threshold, the matrix B is left as it is when a predetermined condition for fine adjustment is satisfied, and an error The difference obtained by subtracting the product obtained by multiplying the matrix B by the coefficient vector U from the matrix D so far is set in the matrix D indicating the position to be reduced. .
請求項1から5に記載の検索方法において、
対応関係効果計算ステップステップの前に、対応関係効果計算ステップステップまたは判定ステップにおいて使われる前記パタンとして、前記変換係数Tの値によって複数のパタンの中から一つを選ぶパタン選択ステップを含む
ことを特徴とする検索方法。
The search method according to claim 1, wherein:
Before the correspondence effect calculation step step, the pattern selection step of selecting one of a plurality of patterns according to the value of the conversion coefficient T as the pattern used in the correspondence effect calculation step or determination step is included. A featured search method.
特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと上記パタンの特徴量の空間と変換係数から上記対象データの特徴量の空間への変換関数とから、上記パタンを上記変換関数で変換した要素群が上記対象データの要素群と高い類似度となるように上記変換関数の変換係数を算出する検索方法を実行する検索装置において、
上記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算手段と、
上記パタンの最初とされた要素と上記対象データの所定の要素とから暫定の変換係数Tを計算する変換係数計算手段と、
上記変換係数Tを用いて、上記パタンの要素毎に、上記変換関数で変換された上記パタンの要素と上記対象データとのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算手段と、
上記スコアが更新されたときの上記パタンの要素の上記移動閾値より、更新された上記スコアが小さいか否かを判定する判定手段と、
更新された上記スコアが上記パタンの要素の上記移動閾値以上であると判定された場合、更新係数ベクトルUおよび上記変換係数Tを更新する変換係数更新手段と
を有し、
更新された上記スコアが上記移動閾値より小さいと判定された場合、上記対象データの次の要素に対して、または上記の次の暫定の変換係数Tに対して、上記検索方法の手順を施す
ことを特徴とする検索装置。
From the pattern that is the element group that represents the feature quantity, the target data that is the element group that represents the feature quantity, the space of the feature quantity of the pattern and the conversion function from the conversion coefficient to the feature quantity space of the target data, the pattern is In a search device for executing a search method for calculating a conversion coefficient of the conversion function so that the element group converted by the conversion function has a high similarity with the element group of the target data,
Threshold calculation means for calculating a movement threshold that is a monotonically non-decreasing value with respect to the index value sequentially added to the elements included in the pattern;
Conversion coefficient calculation means for calculating a provisional conversion coefficient T from the first element of the pattern and the predetermined element of the target data;
Using the conversion coefficient T, the score, matrix B, and matrix D are updated for each element of the pattern in consideration of the degree of matching between the pattern element converted by the conversion function and the target data. Correspondence effect calculation means,
Determination means for determining whether or not the updated score is smaller than the movement threshold value of the element of the pattern when the score is updated;
When it is determined that the updated score is greater than or equal to the movement threshold value of the pattern element, the update coefficient vector U and conversion coefficient update means for updating the conversion coefficient T are included.
When it is determined that the updated score is smaller than the movement threshold, the search method procedure is performed on the next element of the target data or the next provisional transformation coefficient T. A search device characterized by.
特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと上記パタンの特徴量の空間と変換係数から上記対象データの特徴量の空間への変換関数とから、上記パタンを上記変換関数で変換した要素群が上記対象データの要素群と高い類似度となるように上記変換関数の変換係数を算出する検索方法の処理をコンピュータに実行させるプログラムにおいて、
この検索方法の処理は、
上記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、
上記パタンの最初とされた要素と上記対象データの所定の要素とから暫定の変換係数Tを計算する変換係数計算ステップと、
上記変換係数Tを用いて、上記パタンの要素毎に、上記変換関数で変換された上記パタンの要素と上記対象データとのマッチングの度合いを配慮して、スコアと行列Bと行列Dを更新する対応関係効果計算ステップと、
上記スコアが更新されたときの上記パタンの要素の上記移動閾値より、更新された上記スコアが小さいか否かを判定する判定ステップと、
更新された上記スコアが上記パタンの要素の上記移動閾値以上であると判定された場合、更新係数ベクトルUおよび上記変換係数Tを更新する変換係数更新ステップと
を含み、
更新された上記スコアが上記移動閾値より小さいと判定された場合、上記対象データの次の要素に対して、または上記の次の暫定の変換係数Tに対して、上記検索方法の手順を施す
ことを特徴とするプログラム。
From the pattern that is the element group that represents the feature quantity, the target data that is the element group that represents the feature quantity, the space of the feature quantity of the pattern and the conversion function from the conversion coefficient to the feature quantity space of the target data, the pattern is In a program for causing a computer to execute processing of a search method for calculating a conversion coefficient of the conversion function so that an element group converted by the conversion function has a high similarity with the element group of the target data,
The process of this search method is
A threshold calculation step for calculating a movement threshold value that is a monotonically non-decreasing value with respect to the index value sequentially added to the elements included in the pattern;
A conversion coefficient calculation step for calculating a provisional conversion coefficient T from the first element of the pattern and the predetermined element of the target data;
Using the conversion coefficient T, the score, matrix B, and matrix D are updated for each element of the pattern in consideration of the degree of matching between the pattern element converted by the conversion function and the target data. A correspondence effect calculation step;
A determination step of determining whether or not the updated score is smaller than the movement threshold value of the pattern element when the score is updated;
A conversion coefficient update step of updating the update coefficient vector U and the conversion coefficient T when it is determined that the updated score is equal to or greater than the movement threshold value of the pattern element;
When it is determined that the updated score is smaller than the movement threshold, the search method procedure is performed on the next element of the target data or the next provisional transformation coefficient T. A program characterized by
JP2011161695A 2011-07-25 2011-07-25 SEARCH METHOD, SEARCH DEVICE, AND PROGRAM Active JP5476343B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2011161695A JP5476343B2 (en) 2011-07-25 2011-07-25 SEARCH METHOD, SEARCH DEVICE, AND PROGRAM

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2011161695A JP5476343B2 (en) 2011-07-25 2011-07-25 SEARCH METHOD, SEARCH DEVICE, AND PROGRAM

Publications (2)

Publication Number Publication Date
JP2013025662A true JP2013025662A (en) 2013-02-04
JP5476343B2 JP5476343B2 (en) 2014-04-23

Family

ID=47783917

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2011161695A Active JP5476343B2 (en) 2011-07-25 2011-07-25 SEARCH METHOD, SEARCH DEVICE, AND PROGRAM

Country Status (1)

Country Link
JP (1) JP5476343B2 (en)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008176645A (en) * 2007-01-19 2008-07-31 Konica Minolta Holdings Inc Three-dimensional shape processing apparatus, control method of three-dimensional shape processing apparatus, and control program of three-dimensional shape processing apparatus

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008176645A (en) * 2007-01-19 2008-07-31 Konica Minolta Holdings Inc Three-dimensional shape processing apparatus, control method of three-dimensional shape processing apparatus, and control program of three-dimensional shape processing apparatus

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
CSNG201000036012; 増田 健: 'ICPアルゴリズム' 情報処理学会研究報告 No.168, 20091015, p.1-8, 社団法人情報処理学会 *
JPN6013026405; 増田 健: 'ICPアルゴリズム' 情報処理学会研究報告 No.168, 20091015, p.1-8, 社団法人情報処理学会 *

Also Published As

Publication number Publication date
JP5476343B2 (en) 2014-04-23

Similar Documents

Publication Publication Date Title
JP7131994B2 (en) Self-position estimation device, self-position estimation method, self-position estimation program, learning device, learning method and learning program
KR101532864B1 (en) Planar mapping and tracking for mobile devices
CN109598781B (en) Method for acquiring pseudo 3D frame from 2D bounding frame by regression analysis, learning apparatus and testing apparatus using the same
US20110288835A1 (en) Data processing device, data processing method and program
Fourie et al. Harmony filter: a robust visual tracking system using the improved harmony search algorithm
JP7350945B2 (en) Computer-implemented methods, computer program products and devices
KR101234797B1 (en) Robot and method for localization of the robot using calculated covariance
JP7272428B2 (en) Depth estimation device, depth estimation model learning device, depth estimation method, depth estimation model learning method, and depth estimation program
CN106952304B (en) A kind of depth image calculation method using video sequence interframe correlation
CN110375772A (en) The ring laser stochastic error modeling of adaptive Kalman filter and compensation method
JP2017053795A (en) Information processing apparatus, position attitude measurement method, and position attitude measurement program
TWI403818B (en) Method of automated focus
JP2010011620A (en) Apparatus, method and program for creating abridged model of electric power system
US20230153957A1 (en) System and method for training of noise model using noisy signal pairs
CN114608585A (en) Method and device for synchronous positioning and mapping of mobile robot
JP5476343B2 (en) SEARCH METHOD, SEARCH DEVICE, AND PROGRAM
KR102425270B1 (en) Method for estimating position in three-dimensional space
JP2010250611A (en) Image processor, image processing method and recording medium
CN113283152B (en) Adjustment method and driving method of driving electric signal, driving circuit and electronic equipment
JP4398919B2 (en) Image matching apparatus, image matching method, and image matching program
KR20220136884A (en) Point Cloud Completion Network Creation and Point Cloud Data Processing
KR101991626B1 (en) Method and system for detecting vanishing point for intelligent vehicles
JP7490185B2 (en) 3D reconstruction device, 3D reconstruction method, and 3D reconstruction program for analysis object
JP2020061132A (en) Methods and apparatus for processing image data for machine vision
CN113674411B (en) Map building method based on pose map adjustment and related equipment

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20130527

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20130604

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20130805

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20130903

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20131003

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20140121

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20140207

R150 Certificate of patent or registration of utility model

Ref document number: 5476343

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250