JP2005352543A

JP2005352543A - Template matching device

Info

Publication number: JP2005352543A
Application number: JP2004169520A
Authority: JP
Inventors: Hiroyuki Abe; 啓之阿部
Original assignee: Nikon Corp
Current assignee: Nikon Corp
Priority date: 2004-06-08
Filing date: 2004-06-08
Publication date: 2005-12-22

Abstract

PROBLEM TO BE SOLVED: To provide a template matching device capable of accurately specifying a coinciding position even when an input image is rotated and changed. SOLUTION: This device comprises a means for preparing a concentration histogram of a known circular template image 22, a means for extracting a circular partial operation image 25 from a plurality of different positions (X<SB>2</SB>, Y<SB>2</SB>) in the input image 21, a means for preparing a concentration histogram of the extracted partial image, a means for finding the similarity between the template image and the partial image on the basis of the histogram of the template image and that of the partial image, and a means for specifying a coinciding position (X<SB>1</SB>, Y<SB>1</SB>) with the template image in the input image by comparing the similarity found at each position (X<SB>2</SB>, Y<SB>2</SB>) of the input image. COPYRIGHT: (C)2006,JPO&NCIPI

Description

本発明は、入力画像に対してテンプレートマッチングを行うテンプレートマッチング装置に関する。 The present invention relates to a template matching apparatus that performs template matching on an input image.

テンプレートマッチングは、入力画像の中から既知のテンプレート画像に合致する部分画像（ターゲット）を探索して、ターゲットの位置（合致位置）を特定する処理である。この処理では、矩形状のテンプレート画像を用いるのが一般的であり、入力画像の中から矩形状の部分画像をマッチング演算用に抽出すると共に、この部分画像の抽出位置を少しずつ移動させながら、部分画像とテンプレート画像とのマッチング演算を繰り返し行っている。そして、入力画像の中の各位置でのマッチング演算の結果を大小比較することで、合致位置が特定される。 Template matching is a process of searching for a partial image (target) that matches a known template image from an input image and specifying the position of the target (matching position). In this process, a rectangular template image is generally used, and a rectangular partial image is extracted from the input image for matching calculation, and the extraction position of the partial image is moved little by little. The matching operation between the partial image and the template image is repeated. Then, the matching position is specified by comparing the size of the matching calculation result at each position in the input image.

また、マッチング演算には、周知の相互相関法や残差逐次検定法などが用いられる（例えば特許献１を参照）。これらの方法は、演算用の部分画像とテンプレート画像との対応画素どうしで濃度の演算を行い、その結果を画像全体で集計するものである。
特開平５−８１４３３号公報 For the matching operation, a well-known cross-correlation method or a residual sequential test method is used (see, for example, Patent Document 1). In these methods, the density is calculated between corresponding pixels of the partial image for calculation and the template image, and the results are totaled over the entire image.
JP-A-5-81433

しかしながら、矩形状のテンプレート画像を用い、矩形状の部分画像との対応画素どうしで濃度の演算を行う場合、入力画像に回転変化があると（図１２参照）、その入力画像から抽出される部分画像にも回転変化が現れるため、合致位置の特定を正確に行えるとは限らず、疑似マッチングやマッチング不可能になることがあった。
本発明の目的は、入力画像に回転変化があっても正確に合致位置を特定できるテンプレートマッチング装置を提供することにある。 However, when a density is calculated between pixels corresponding to a rectangular partial image using a rectangular template image, if there is a rotational change in the input image (see FIG. 12), the portion extracted from the input image Since a rotational change also appears in the image, it is not always possible to specify the matching position accurately, and pseudo matching or matching may not be possible.
An object of the present invention is to provide a template matching apparatus that can accurately specify a matching position even if there is a rotational change in an input image.

請求項１に記載のテンプレートマッチング装置は、円形状の既知のテンプレート画像の濃度のヒストグラムを作成する第１の作成手段と、入力画像の中の異なる複数の位置から円形状の演算用の部分画像を抽出する抽出手段と、前記抽出手段により抽出された前記部分画像の濃度のヒストグラムを作成する第２の作成手段と、前記テンプレート画像の前記ヒストグラムと前記部分画像の前記ヒストグラムとに基づいて、前記テンプレート画像と前記部分画像との類似度を求める演算手段と、前記入力画像の各位置で求められた前記類似度を大小比較することにより、前記入力画像の中の前記テンプレート画像との合致位置を特定する特定手段とを備えたものである。 The template matching apparatus according to claim 1, a first creation unit that creates a density histogram of a known circular template image, and a partial image for calculating a circle from a plurality of different positions in the input image Based on the extraction means for extracting the image, the second creation means for creating a histogram of the density of the partial image extracted by the extraction means, the histogram of the template image and the histogram of the partial image, By calculating the similarity between the template image and the partial image and the similarity obtained at each position of the input image, the matching position with the template image in the input image is determined. And specifying means for specifying.

請求項２に記載のテンプレートマッチング装置は、円形状の既知のテンプレート画像の濃度の慣性モーメントを算出する第１の算出手段と、入力画像の中の異なる複数の位置から円形状の演算用の部分画像を抽出する抽出手段と、前記抽出手段により抽出された前記部分画像の濃度の慣性モーメントを算出する第２の算出手段と、前記テンプレート画像の前記慣性モーメントと前記部分画像の前記慣性モーメントとに基づいて、前記テンプレート画像と前記部分画像との類似度を求める演算手段と、前記入力画像の各位置で求められた前記類似度を大小比較することにより、前記入力画像の中の前記テンプレート画像との合致位置を特定する特定手段とを備えたものである。 The template matching apparatus according to claim 2, a first calculation unit that calculates a moment of inertia of the density of a known circular template image, and a circular calculation part from a plurality of different positions in the input image An extracting means for extracting an image; a second calculating means for calculating a moment of inertia of the density of the partial image extracted by the extracting means; and the inertia moment of the template image and the inertia moment of the partial image. Based on the calculation means for obtaining the similarity between the template image and the partial image, and by comparing the similarity obtained at each position of the input image with the template image in the input image And a specifying means for specifying the matching position.

請求項３に記載のテンプレートマッチング装置は、円形状の既知のテンプレート画像の予め定めた第１範囲と第２範囲との各々における平均濃度の差を算出する第１の算出手段と、入力画像の中の異なる複数の位置から円形状の演算用の部分画像を抽出する抽出手段と、前記抽出手段により抽出された前記部分画像の前記第１範囲と前記第２範囲との各々における平均濃度の差を算出する第２の算出手段と、前記テンプレート画像の前記平均濃度の差と前記部分画像の前記平均濃度の差とに基づいて、前記テンプレート画像と前記部分画像との類似度を求める演算手段と、前記入力画像の各位置で求められた前記類似度を大小比較することにより、前記入力画像の中の前記テンプレート画像との合致位置を特定する特定手段とを備えたものである。 The template matching apparatus according to claim 3, a first calculation unit that calculates a difference in average density in each of a predetermined first range and a second range of a circular known template image; Extraction means for extracting circular partial images for calculation from a plurality of different positions, and difference in average density in each of the first range and the second range of the partial images extracted by the extraction means Second calculating means for calculating the difference between the template image and the partial image based on the average density difference of the template image and the average density difference of the partial image; And a specifying means for specifying a matching position with the template image in the input image by comparing the similarity obtained at each position of the input image. That.

請求項４に記載の発明は、請求項１に記載のテンプレートマッチング装置において、前記テンプレート画像と前記入力画像と前記部分画像とは、複数の色成分を含み、前記第１の作成手段は、前記テンプレート画像の前記ヒストグラムを各色成分ごとに作成し、前記第２の作成手段は、前記部分画像の前記ヒストグラムを各色成分ごとに作成し、前記演算手段は、前記テンプレート画像の各色成分の前記ヒストグラムと前記部分画像の各色成分の前記ヒストグラムとに基づいて、同じ色成分どうしを比較することにより、前記類似度を求めるものである。 According to a fourth aspect of the present invention, in the template matching apparatus according to the first aspect, the template image, the input image, and the partial image include a plurality of color components, and the first creating means The histogram of the template image is created for each color component, the second creating means creates the histogram of the partial image for each color component, and the computing means includes the histogram of each color component of the template image. Based on the histogram of each color component of the partial image, the similarity is obtained by comparing the same color components.

請求項５に記載の発明は、請求項２に記載のテンプレートマッチング装置において、前記テンプレート画像と前記入力画像と前記部分画像とは、複数の色成分を含み、前記第１の算出手段は、前記テンプレート画像の前記慣性モーメントを各色成分ごとに算出し、前記第２の算出手段は、前記部分画像の前記慣性モーメントを各色成分ごとに算出し、前記演算手段は、前記テンプレート画像の各色成分の前記慣性モーメントと前記部分画像の各色成分の前記慣性モーメントとに基づいて、同じ色成分どうしを比較することにより、前記類似度を求めるものである。 According to a fifth aspect of the present invention, in the template matching apparatus according to the second aspect, the template image, the input image, and the partial image include a plurality of color components, and the first calculation unit includes the first calculation unit, The moment of inertia of the template image is calculated for each color component, the second calculation means calculates the moment of inertia of the partial image for each color component, and the calculation means calculates the color component of each color component of the template image. The similarity is obtained by comparing the same color components based on the moment of inertia and the moment of inertia of each color component of the partial image.

請求項６に記載の発明は、請求項３に記載のテンプレートマッチング装置において、前記テンプレート画像と前記入力画像と前記部分画像とは、複数の色成分を含み、前記第１の算出手段は、前記テンプレート画像の前記平均濃度の差を各色成分ごとに算出し、前記第２の算出手段は、前記部分画像の前記平均濃度の差を各色成分ごとに算出し、前記演算手段は、前記テンプレート画像の各色成分の前記平均濃度の差と前記部分画像の各色成分の前記平均濃度の差とに基づいて、同じ色成分どうしを比較することにより、前記類似度を求めるものである。 According to a sixth aspect of the present invention, in the template matching apparatus according to the third aspect, the template image, the input image, and the partial image include a plurality of color components, and the first calculation unit includes the first calculation unit, The average density difference of the template image is calculated for each color component, the second calculation unit calculates the average density difference of the partial image for each color component, and the calculation unit calculates the template image The similarity is obtained by comparing the same color components based on the difference in average density of each color component and the difference in average density of each color component of the partial image.

本発明のテンプレートマッチング装置によれば、入力画像に回転変化があっても正確に合致位置を特定することができる。 According to the template matching apparatus of the present invention, it is possible to accurately specify the matching position even if the input image has a rotational change.

以下、図面を用いて本発明の実施形態を詳細に説明する。
（第１実施形態）
ここでは、第１実施形態のテンプレートマッチング装置について、図１に示す観察装置１０を例に説明する。観察装置１０には、ステージ１１と光学系１２とカメラ１３と画像処理部１４とが設けられる。ステージ１１は、試料１０Ａを支持する。光学系１２は、試料１０Ａの局所領域の光像を形成する。カメラ１３は、不図示の撮像素子により試料１０Ａの光像を撮像し、撮像信号を画像処理部１４に出力する。 Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
(First embodiment)
Here, the template matching apparatus according to the first embodiment will be described using the observation apparatus 10 shown in FIG. 1 as an example. The observation apparatus 10 includes a stage 11, an optical system 12, a camera 13, and an image processing unit 14. The stage 11 supports the sample 10A. The optical system 12 forms an optical image of a local region of the sample 10A. The camera 13 captures an optical image of the sample 10 A with an image sensor (not shown), and outputs an imaging signal to the image processing unit 14.

画像処理部１４は、カメラ１３から撮像信号を取り込むと、これを所定ビット（例えば８ビット）のディジタル画像に変換し、入力画像２１（図２）として不図示のメモリに記憶させる。そして、入力画像２１に対して後述のテンプレートマッチングを行う。画像処理部１４が第１実施形態のテンプレートマッチング装置に対応する。観察装置１０を用いて、試料１０Ａの観察や検査や位置合わせなどが行われる。試料１０Ａは、例えば、半導体ウエハや液晶基板、プリント基板、生物標本(例えば細胞)などである。 When the image processing unit 14 captures an imaging signal from the camera 13, the image processing unit 14 converts the imaged signal into a digital image of a predetermined bit (for example, 8 bits), and stores it in a memory (not shown) as an input image 21 (FIG. 2). Then, template matching described later is performed on the input image 21. The image processing unit 14 corresponds to the template matching device of the first embodiment. Using the observation apparatus 10, observation, inspection, alignment, and the like of the sample 10A are performed. The sample 10A is, for example, a semiconductor wafer, a liquid crystal substrate, a printed board, a biological specimen (for example, a cell), or the like.

次に、画像処理部１４におけるテンプレートマッチングについて説明する。このテンプレートマッチングは、図２に示す円形状の既知のテンプレート画像２２を用い、図３に示すフローチャートの手順（ステップＳ１〜Ｓ１１）にしたがって行われる。図３の処理では、入力画像２１とテンプレート画像２２が、各々、３つの色成分（つまり加色の三原色または光の三原色と呼ばれるＲＧＢ成分）を含むとする。ＲＧＢ成分を含む画像(２１,２２)はカラー画像である。 Next, template matching in the image processing unit 14 will be described. This template matching is performed according to the procedure of the flowchart shown in FIG. 3 (steps S1 to S11) using the circular known template image 22 shown in FIG. In the process of FIG. 3, it is assumed that the input image 21 and the template image 22 each include three color components (that is, RGB components called additive primary colors or light primary colors). The images (21, 22) including the RGB components are color images.

図３のステップＳ１において、画像処理部１４は、テンプレート画像２２の全体からＲＧＢ成分の濃度ヒストグラムＨ₂₂を各色成分ごとに作成する（図４(ａ)参照）。濃度ヒストグラムＨ₂₂の作成は、テンプレート画像２２の全画素の濃度値を調べ、各濃度値ごとに画素数を計数することにより行われる。テンプレート画像２２が８ビットの場合、画素の濃度値は２５６段階（０〜２５５）となる。濃度ヒストグラムＨ₂₂は、テンプレート画像２２の中に各濃度値の画素が現れる頻度（画素数）を表した濃度のヒストグラム（度数分布）であり、画素の位置に依存しない特徴量である。濃度ヒストグラムＨ₂₂の横軸は濃度値、縦軸は画素数である。 In step S1 of FIG. 3, the image processing unit 14, a density histogram H ₂₂ of the RGB components is created for each color component from the entire template image 22 (see Figure 4 (a)). The density histogram H ₂₂ is created by examining the density values of all the pixels of the template image 22 and counting the number of pixels for each density value. When the template image 22 is 8 bits, the density value of the pixel is 256 steps (0 to 255). The density histogram H ₂₂ is a density histogram (frequency distribution) representing the frequency (number of pixels) in which the pixels of each density value appear in the template image 22 and is a feature quantity independent of the pixel position. The horizontal axis density value of the density histogram H _22, the vertical axis is the number of pixels.

次に（ステップＳ２）、画像処理部１４は、入力画像２１の中から円形状の部分画像２５（図２）をマッチング演算用に抽出する。この抽出処理は、例えば２段階で行われ、入力画像２１の中から矩形状の部分画像２４を抽出した後、部分画像２４の四隅付近にマスクを掛け、部分画像２４に内接する円形状の部分画像２５をマッチング演算用として抽出するものである。円形状の部分画像２５は、テンプレート画像２２と同じ大きさ(画素数)である。部分画像２５とテンプレート画像２２は、共に、入力画像２１より小さい（画素数が少ない）。また、演算用の部分画像２５も、入力画像２１と同じ色成分（つまりＲＧＢ成分）を含むカラー画像である。 Next (step S 2), the image processing unit 14 extracts a circular partial image 25 (FIG. 2) from the input image 21 for matching calculation. This extraction process is performed, for example, in two stages. After extracting a rectangular partial image 24 from the input image 21, a mask is applied to the vicinity of the four corners of the partial image 24, and a circular portion that is inscribed in the partial image 24. The image 25 is extracted for matching calculation. The circular partial image 25 has the same size (number of pixels) as the template image 22. Both the partial image 25 and the template image 22 are smaller than the input image 21 (the number of pixels is small). In addition, the calculation partial image 25 is also a color image including the same color components (that is, RGB components) as the input image 21.

次に（ステップＳ３）、画像処理部１４は、ステップＳ２で抽出した演算用の部分画像２５の全体からＲＧＢ成分の濃度ヒストグラムＨ₂₅を各色成分ごとに作成する（図４(ｂ)参照）。この濃度ヒストグラムＨ₂₅の作成も、上記したテンプレート画像２２の濃度ヒストグラムＨ₂₂と同様にして行われる。濃度ヒストグラムＨ₂₅も、画素の位置に依存しない特徴量であり、横軸は濃度値、縦軸は画素数である。 Next (step S3), the image processing unit 14 creates a density histogram H ₂₅ of RGB components for each color component from the entire partial image 25 for calculation extracted in step S2 (see FIG. 4B). The density histogram H ₂₅ is generated in the same manner as the density histogram H ₂₂ of the template image 22 described above. The density histogram H _{25 is} also a feature quantity that does not depend on the position of the pixel, the horizontal axis is the density value, and the vertical axis is the number of pixels.

ここで、演算用の部分画像２５の濃度ヒストグラムＨ₂₅と、入力画像２１の回転変化との関係について説明する。図５から分かるように、入力画像２１に回転変化があると、入力画像２１から抽出される矩形状の部分画像２４には同様の回転変化が現れ、その四隅付近の濃度情報が変化してしまう。しかし、矩形状の部分画像２４から抽出される円形状の部分画像２５には回転変化が現れず、その濃度情報が変化することはない。このため、円形状の部分画像２５から作成した濃度ヒストグラムＨ₂₅（図４(ｂ)）は、入力画像２１の回転変化に対して不変な特徴量と考えられる。 Here, the relationship between the density histogram H ₂₅ of the partial image 25 for calculation and the rotation change of the input image 21 will be described. As can be seen from FIG. 5, when the input image 21 has a rotational change, a similar rotational change appears in the rectangular partial image 24 extracted from the input image 21, and the density information in the vicinity of the four corners changes. . However, a rotational change does not appear in the circular partial image 25 extracted from the rectangular partial image 24, and its density information does not change. Therefore, the density histogram H ₂₅ (FIG. 4B) created from the circular partial image 25 is considered to be a feature quantity that is invariant with respect to the rotational change of the input image 21.

画像処理部１４は、図３のステップＳ１〜Ｓ３を経て、テンプレート画像２２の濃度ヒストグラムＨ₂₂（図４(ａ)）と、部分画像２５の濃度ヒストグラムＨ₂₅（図４(ｂ)）とを作成し終えると、２つの濃度ヒストグラムＨ₂₂,Ｈ₂₅に基づいて、部分画像２５とテンプレート画像２２とのマッチング演算（Ｓ４〜Ｓ７）を行う。マッチング演算（Ｓ４〜Ｓ７）は、部分画像２５とテンプレート画像２２との類似度を求める演算である。 The image processing unit 14 obtains the density histogram H ₂₂ (FIG. 4A) of the template image 22 and the density histogram H ₂₅ (FIG. 4B) of the partial image 25 through steps S1 to S3 of FIG. When the creation is completed, matching calculation (S4 to S7) between the partial image 25 and the template image 22 is performed based on the two density histograms H ₂₂ and H ₂₅ . The matching calculation (S4 to S7) is a calculation for obtaining the similarity between the partial image 25 and the template image 22.

まず（ステップＳ４）、画像処理部１４は、部分画像２５のＲ成分の濃度ヒストグラムＨ₂₅と、テンプレート画像２２のＲ成分の濃度ヒストグラムＨ₂₂とを比較し、２つのＲ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の重なり部分（図６の斜線部分）の画素数を集計する。この重なり部分（図６の斜線部分）の総画素数Ｋ_Rは、Ｒ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の類似性に関する指標である。重なり部分（図６の斜線部分）とは、濃度ヒストグラムＨ₂₅,Ｈ₂₂の同じ濃度値どうしで画素数を比較したときの小さい方の画素数に相当する。 First (step S4), and the image processing unit 14 includes a concentration histogram H ₂₅ of the R component of the partial image 25 is compared with the density histogram H ₂₂ of the R component of the template image 22, two density histogram H ₂₅ R component , counts the number of pixels overlapping portion of the H ₂₂ (hatched portion in FIG. 6). The total number of pixels K _R of the overlapping portion (shaded portion in FIG. 6) is an index relating to the similarity between the density histograms H ₂₅ and H ₂₂ of the R component. The overlapping portion (shaded portion in FIG. 6) corresponds to the smaller number of pixels when the number of pixels is compared between the same density values of the density histograms H ₂₅ and H ₂₂ .

同様に、ステップＳ５では、部分画像２５のＧ成分の濃度ヒストグラムＨ₂₅と、テンプレート画像２２のＧ成分の濃度ヒストグラムＨ₂₂とを比較し、２つのＧ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の重なり部分の画素数を集計する（総画素数Ｋ_G）。さらに、ステップＳ６では、部分画像２５のＢ成分の濃度ヒストグラムＨ₂₅と、テンプレート画像２２のＢ成分の濃度ヒストグラムＨ₂₂とを比較し、２つのＢ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の重なり部分の画素数を集計する（総画素数Ｋ_B）。 Similarly, in step S5, a density histogram H ₂₅ of the G component of the partial image 25 is compared with the density histogram H ₂₂ of the G component of the template image 22, the overlapping of the two density histogram H ₂₅ G component, H ₂₂ The number of pixels in the portion is totaled (total number of pixels K _G ). In step S6, the B component density histogram H _{25 of the} partial image 25 is compared with the B component density histogram H _{22 of the} template image 22, and the two B component density histograms H ₂₅ and H ₂₂ are overlapped. Are totaled (total number of pixels K _B ).

上記した通り、演算用の部分画像２５は円形状であり、この部分画像２５から作成した濃度ヒストグラムＨ₂₅（図４(ｂ)）は、ＲＧＢ成分の何れも、入力画像２１の回転変化に対して不変な特徴量である。したがって、上記ステップＳ４の集計結果（Ｒ成分の重なり部分の総画素数Ｋ_R）と、ステップＳ５の集計結果（Ｇ成分の重なり部分の総画素数Ｋ_G）と、ステップＳ６の集計結果（Ｂ成分の重なり部分の総画素数Ｋ_B）は、各々、入力画像２１の回転変化に対して不変な特徴量と考えられる。 As described above, the calculation partial image 25 has a circular shape, and the density histogram H ₂₅ (FIG. 4B) created from this partial image 25 is free from any rotational change of the input image 21. Is an invariant feature quantity. Therefore, the summation result of step S4 (total number of pixels K _R of overlapping portions of R components), the summation result of step S5 (total number of pixels K _G of overlapping portions of G components), and the summation results of step S6 (B The total pixel count K _B ) of the overlapping parts of the components is considered to be a feature quantity that is invariant to the rotational change of the input image 21.

次に（ステップＳ７）、画像処理部１４は、上記ステップＳ４〜Ｓ６の各々の集計結果（ＲＧＢ成分の重なり部分の総画素数Ｋ_R,Ｋ_G,Ｋ_B）の和を求め、その値を「部分画像２５とテンプレート画像２２との類似度」とする。この類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）は、部分画像２５とテンプレート画像２２との「類似性に関する指標」であり、入力画像２１の回転変化に対して不変な特徴量と考えられる。 Next (step S7), the image processing unit 14 obtains the sum of the total results (total number of pixels K _R , K _G , K _B of the overlapping portions of the RGB components) of the above steps S4 to S6, and calculates the value. “Similarity between partial image 25 and template image 22”. This degree of similarity (= K _R + K _G + K _B ) is an “index for similarity” between the partial image 25 and the template image 22, and is considered to be a feature quantity that is invariable with respect to the rotational change of the input image 21.

ステップＳ７で求めた類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）は、傾向として、その値が大きいほど、部分画像２５とテンプレート画像２２との類似性が高いことを表している。また、テンプレート画像２２との類似性が高いとは、図２に示す部分画像２５の抽出位置(Ｘ₂,Ｙ₂)がテンプレート画像２２に合致する部分画像（ターゲット２３）の位置（以下「合致位置(Ｘ₁,Ｙ₁)」という）に近いことを表す。 The degree of similarity (= K _R + K _G + K _B ) obtained in step S7 indicates that, as the value increases, the similarity between the partial image 25 and the template image 22 increases. Further, high similarity to the template image 22 means that the extraction position (X ₂ , Y ₂ ) of the partial image 25 shown in FIG. 2 matches the position of the partial image (target 23) (hereinafter referred to as “match”). It represents that the position is close to (position (X ₁ , Y ₁ ) ”).

上記のマッチング演算（Ｓ４〜Ｓ７）が終了すると、画像処理部１４は、次のステップＳ８において、マッチング演算の結果である類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）を、部分画像２５の抽出位置(Ｘ₂,Ｙ₂)と対応づけてメモリに保存する。これらのステップＳ２〜Ｓ８の処理を経て、入力画像２１の中の１つの抽出位置(Ｘ₂,Ｙ₂)に対する処理が終わる。そして、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を次の位置へ移動させる場合には（ステップＳ９がＹｅｓ）、ステップＳ１０の処理に進む。 When the matching calculation (S4 to S7) is completed, the image processing unit 14 uses the similarity (= K _R + K _G + K _B ) as a result of the matching calculation to extract the position of the partial image 25 in the next step S8. Corresponding to (X ₂ , Y ₂ ) and storing in memory. After the processing of these steps S2 to S8, processing is completed for one extraction position in the input image _{_{21 (X 2, Y 2)}} . When the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation is moved to the next position (Yes in step S9), the process proceeds to step S10.

ステップＳ１０の処理は、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)の移動処理である。画像処理部１４は、部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を現在の位置から次の位置へ移動させる。その後、ステップＳ２の処理に戻り、新たな抽出位置(Ｘ₂,Ｙ₂)において、演算用の部分画像２５の抽出（Ｓ２）→ＲＧＢ成分の濃度ヒストグラムの作成（Ｓ３）→マッチング演算（Ｓ４〜Ｓ７）→結果保存（Ｓ８）を繰り返す。 The process of step S10 is a process of moving the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation. The image processing unit 14 moves the extraction position (X ₂ , Y ₂ ) of the partial image 25 from the current position to the next position. Thereafter, the processing returns to step S2, and at the new extraction position (X ₂ , Y ₂ ), extraction of the partial image 25 for calculation (S2) → creation of density histogram of RGB components (S3) → matching calculation (S4˜) S7) → Save result (S8) is repeated.

このようにして、ステップＳ２→…→Ｓ１０→Ｓ２…の処理を繰り返すことにより、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を少しずつ移動させながら、各々の位置で部分画像２５を順に抽出し、部分画像２５を抽出する毎に、ＲＧＢ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂に基づいてマッチング演算（Ｓ４〜Ｓ７）を繰り返し行うことになる。
そして、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)が終点に到達し、そこでのステップＳ２〜Ｓ８の処理が終了すると、画像処理部１４は、次の位置への移動を行わずに（Ｓ９がＮｏ）、ステップＳ１１の処理に進む。ステップＳ１１では、入力画像２１の中の異なる複数の位置で求められた類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）を大小比較することにより、その値が最も大きく、テンプレート画像２２との類似性が最も高い部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を合致位置(Ｘ₁,Ｙ₁)と特定する。以上で入力画像２１に対するテンプレートマッチングの処理は終了となる。 In this way, by repeating the process of steps S2 →... → S10 → S2..., The partial image at each position is moved while the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation is moved little by little. Each time 25 is extracted in order and the partial image 25 is extracted, the matching calculation (S4 to S7) is repeated based on the density histograms H ₂₅ and H ₂₂ of the RGB components.
Then, when the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation reaches the end point and the processing in steps S2 to S8 is completed, the image processing unit 14 moves to the next position. Without (S9 is No), it progresses to the process of step S11. In step S11, the similarity (= K _R + K _G + K _B ) obtained at a plurality of different positions in the input image 21 is compared in magnitude, and the value is the largest, and the similarity with the template image 22 is the same. The extraction position (X ₂ , Y ₂ ) of the highest partial image 25 is specified as the matching position (X ₁ , Y ₁ ). The template matching process for the input image 21 is thus completed.

上記のように、第１実施形態のテンプレートマッチングでは、マッチング演算（Ｓ４〜Ｓ７）の結果である類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）が、図５に示すような入力画像２１の回転変化に対して不変な特徴量として求められ、この類似度（＝Ｋ_R＋Ｋ_G＋Ｋ_B）を大小比較する。このため、入力画像２１に回転変化があっても正確に合致位置(Ｘ₁,Ｙ₁)を特定することができる。 As described above, in the template matching according to the first embodiment, the similarity (= K _R + K _G + K _B ), which is the result of the matching calculation (S4 to S7), is the rotational change of the input image 21 as shown in FIG. The similarity (= K _R + K _G + K _B ) is compared in magnitude. For this reason, even if there is a rotational change in the input image 21, the matching position (X ₁ , Y ₁ ) can be accurately specified.

また、演算用の部分画像２５の濃度範囲とテンプレート画像２２の濃度範囲とを一致させることにより（正規化処理）、入力画像２１のコントラストの変化やノイズにも対応でき、正確に合致位置(Ｘ₁,Ｙ₁)を特定することができる。
さらに、第１実施形態のテンプレートマッチングでは、各々の画像(２１,２５,２２)に含まれる全ての色成分（つまりＲＧＢ成分）の濃度ヒストグラムＨ₂₅,Ｈ₂₂に基づいて、同じ色成分どうしを比較することにより、マッチング演算（Ｓ４〜Ｓ７）を行う。このため、多くの情報量を確保でき、より正確に合致位置(Ｘ₁,Ｙ₁)を特定できる。 Further, by matching the density range of the partial image 25 for calculation with the density range of the template image 22 (normalization processing), it is possible to cope with the contrast change and noise of the input image 21 and accurately match the matching position (X ₁ , Y ₁ ) can be specified.
Furthermore, in the template matching of the first embodiment, the same color components are calculated based on the density histograms H ₂₅ and H ₂₂ of all color components (that is, RGB components) included in each image (21, ₂₅ , ₂₂ ). By performing the comparison, a matching calculation (S4 to S7) is performed. For this reason, a large amount of information can be secured, and the matching position (X ₁ , Y ₁ ) can be specified more accurately.

なお、上記した第１実施形態では、図３のステップＳ７において、ステップＳ４〜Ｓ６の集計結果の和（＝Ｋ_R＋Ｋ_G＋Ｋ_B）を求め、その値を「部分画像２５とテンプレート画像２２との類似度」としたが、本発明はこれに限定されない。ステップＳ４〜Ｓ６の集計結果の平均値（＝[Ｋ_R＋Ｋ_G＋Ｋ_B]/３）を求め、その値を「部分画像２５とテンプレート画像２２との類似度」としてもよい。平均値（＝[Ｋ_R＋Ｋ_G＋Ｋ_B]/３）の場合でも、その値が大きいほど、部分画像２５とテンプレート画像２２との類似性が高く、部分画像２５の抽出位置(Ｘ₂,Ｙ₂)が合致位置(Ｘ₁,Ｙ₁)に近いことを表す。 In the first embodiment described above, in step S7 of FIG. 3, the sum (= K _R + K _G + K _B ) of the summation results of steps S4 to S6 is obtained, and the value is expressed as “partial image 25 and template image 22”. However, the present invention is not limited to this. An average value (= [K _R + K _G + K _B ] / 3) of the aggregation results in steps S4 to S6 may be obtained, and the value may be set as “similarity between the partial image 25 and the template image 22”. Even in the case of the average value (= [K _R + K _G + K _B ] / 3), the larger the value, the higher the similarity between the partial image 25 and the template image 22, and the extraction position (X ₂ , Y of the partial image 25). ₂ ) represents that it is close to the matching position (X ₁ , Y ₁ ).

また、上記した第１実施形態では、図３のステップＳ４〜Ｓ６において、図６に示すような濃度ヒストグラムＨ₂₅,Ｈ₂₂の重なり部分（斜線部分）の画素数を集計したが、本発明はこれに限定されない。その他、濃度ヒストグラムＨ₂₅,Ｈ₂₂の差分の絶対値（図７の斜線部分）の画素数を集計してもよい。この場合、ステップＳ４〜Ｓ６のＲＧＢ成分の集計結果（濃度ヒストグラムＨ₂₅,Ｈ₂₂の差分の絶対値の総画素数Ｋ_R’,Ｋ_G’,Ｋ_B’）の和または平均値は、部分画像２５とテンプレート画像２２との類似度に相当し、その値が小さいほど、部分画像２５とテンプレート画像２２との類似性が高く、抽出位置(Ｘ₂,Ｙ₂)が合致位置(Ｘ₁,Ｙ₁)に近いことを表す。
（第２実施形態）
ここでは、演算用の部分画像２５とテンプレート画像２２とのマッチング演算を、後述の濃度慣性モーメントに基づいて行う場合を説明する。第２実施形態のテンプレートマッチングは、図３のステップＳ１,Ｓ３において“濃度ヒストグラム”の代わりに“濃度慣性モーメント”を算出し、図３のステップＳ４〜Ｓ７に代えて図８のステップＳ２１〜Ｓ２４の処理を実行するものである。第２実施形態でも、ＲＧＢ成分を含む画像(２１,２５,２２)を例に説明する。 In the first embodiment described above, in steps S4 to S6 in FIG. 3, the number of pixels in the overlapping portion (hatched portion) of the density histograms H ₂₅ and H ₂₂ as shown in FIG. 6 is tabulated. It is not limited to this. In addition, the absolute value of the difference between the density histograms H ₂₅ and H ₂₂ (shaded area in FIG. 7) may be totaled. In this case, the sum or average value of the RGB component summation results (total pixel counts K _R ', K _G ', K _B 'of the differences between the density histograms H ₂₅ , H ₂₂₎ in steps S4 to S6 is a partial This corresponds to the degree of similarity between the image 25 and the template image 22, and the smaller the value, the higher the similarity between the partial image 25 and the template image 22, and the extraction position (X ₂ , Y ₂ ) matches the matching position (X ₁ , Y ₁ ).
(Second Embodiment)
Here, a case will be described in which the matching calculation between the calculation partial image 25 and the template image 22 is performed based on a density inertia moment described later. In the template matching of the second embodiment, “density inertia moment” is calculated instead of “density histogram” in steps S1 and S3 of FIG. 3, and steps S21 to S24 of FIG. 8 are substituted for steps S4 to S7 of FIG. The process is executed. Also in the second embodiment, an image (21, 25, 22) including RGB components will be described as an example.

まず（図３のＳ１のタイミングで）、画像処理部１４は、テンプレート画像２２の全体からＲＧＢ成分の濃度慣性モーメントＭ₂₂を各色成分ごとに算出する。例えば、Ｒ成分の濃度慣性モーメントＭ₂₂は、テンプレート画像２２のＲ成分（図９）の位置(ｘ,ｙ)における濃度値Ａ_iを用い、次の式(１)により算出される。濃度値Ａ_iの“ｉ”は、テンプレート画像２２の中での画素番号である。 First (at the timing of S1 in FIG. 3), the image processing unit 14 calculates the concentration of inertia moment M ₂₂ of the RGB components for each color component from the entire template image 22. For example, the density inertia moment M ₂₂ of the R component is calculated by the following equation (1) using the density value A _i at the position (x, y) of the R component (FIG. 9) of the template image 22. “I” of the density value A _i is a pixel number in the template image 22.

Ｍ₂₂＝ Σ(ｘ_i ²＋ｙ_i ²)Ａ_i …(１)
式(１)の濃度慣性モーメントＭ₂₂は、原点（画像中心）まわりの濃度の慣性モーメントであり、Ｘ軸まわりの濃度の慣性モーメント（Ｍ_X＝Σｘ_i ²Ａ_i）と、Ｙ軸まわりの濃度の慣性モーメント（Ｍ_Y＝Σｙ_i ²Ａ_i）との和に相当する。Ｒ成分の他、Ｇ成分,Ｂ成分の濃度慣性モーメントＭ₂₂は、各々、テンプレート画像２２のＧ成分,Ｂ成分の全体から、上記の式(１)と同様の式により算出される。ＲＧＢ成分の濃度慣性モーメントＭ₂₂は、画素の位置に依存しない特徴量である。 M ₂₂ = Σ (x _i ² + y _i ² ) A _i (1)
The density inertia moment M _{22 in} the equation (1) is the inertia moment of density around the origin (image center), and the inertia moment of density around the X axis (M _X = Σx _i ² A _i ) This corresponds to the sum of the concentration moment of inertia (M _Y = Σy _i ² A _i ). In addition to the R component, the density inertia moments M ₂₂ of the G component and the B component are calculated from the entire G component and B component of the template image 22 by the same formula as the above formula (1), respectively. Concentration inertia moment M ₂₂ of the RGB components is a characteristic quantity that is independent of the position of the pixel.

また、画像処理部１４は、入力画像２１の中から円形状の部分画像２５をマッチング演算用に抽出すると、図３のＳ３のタイミングで、部分画像２５の全体からＲＧＢ成分の濃度慣性モーメントＭ₂₅を各色成分ごとに算出する。例えば、Ｒ成分の濃度慣性モーメントＭ₂₅の算出は、部分画像２５のＲ成分の全体から上記した式(１)と同様の式により行われる。Ｇ成分,Ｂ成分も同様である。ＲＧＢ成分の濃度慣性モーメントＭ₂₅は、画素の位置に依存しない特徴量である。 In addition, when the image processing unit 14 extracts the circular partial image 25 from the input image 21 for matching calculation, the density inertia moment M _{25 of the} RGB component from the entire partial image 25 at the timing of S3 in FIG. Is calculated for each color component. For example, the calculation of the concentration inertia moment M ₂₅ of the R component is performed from the entire R component of the partial image 25 by the same equation as the above equation (1). The same applies to the G component and the B component. The density inertia moment M ₂₅ of the RGB component is a feature amount that does not depend on the position of the pixel.

ここで、演算用の部分画像２５の濃度慣性モーメントＭ₂₅と、入力画像２１の回転変化との関係について説明する。既に説明した通り、入力画像２１に回転変化（図５参照）があると、矩形状の部分画像２４の濃度情報は四隅付近で変化するが、円形状の部分画像２５の濃度情報は変化しない。このため、円形状の部分画像２５から算出した濃度慣性モーメントＭ₂₅は、入力画像２１の回転変化に対して不変な特徴量と考えられる。 Here, the concentration of inertia moment M ₂₅ of the partial image 25 for computation, the relationship between the rotation change of the input image 21 will be described. As described above, when the input image 21 has a rotational change (see FIG. 5), the density information of the rectangular partial image 24 changes near the four corners, but the density information of the circular partial image 25 does not change. For this reason, the density inertia moment M ₂₅ calculated from the circular partial image 25 is considered to be a feature quantity that is invariant to the rotational change of the input image 21.

画像処理部１４は、上記のようにして、テンプレート画像２２の濃度慣性モーメントＭ₂₂と、部分画像２５の濃度慣性モーメントＭ₂₅とを算出し終えると、２つの濃度慣性モーメントＭ₂₂,Ｍ₂₅に基づいて、部分画像２５とテンプレート画像２２とのマッチング演算（図８）を行う。マッチング演算（図８）は、部分画像２５とテンプレート画像２２との類似度を求める演算である。 The image processing unit 14, as described above, the concentration of inertia moment M ₂₂ of the template image 22, after finishing calculating the concentration inertia M ₂₅ of the partial image 25, the two concentrations inertia M _22, M ₂₅ Based on this, a matching operation (FIG. 8) between the partial image 25 and the template image 22 is performed. The matching operation (FIG. 8) is an operation for obtaining the similarity between the partial image 25 and the template image 22.

まず（図８のステップＳ２１）、画像処理部１４は、部分画像２５のＲ成分の濃度慣性モーメントＭ₂₅と、テンプレート画像２２のＲ成分の濃度慣性モーメントＭ₂₂とを比較し、２つのＲ成分の濃度慣性モーメントＭ₂₅,Ｍ₂₂の差分の絶対値を出力する。この場合の出力値Ｏ_Rは、Ｒ成分の濃度慣性モーメントＭ₂₅,Ｍ₂₂の類似性に関する指標である。
同様に、ステップＳ２２では、部分画像２５のＧ成分の濃度慣性モーメントＭ₂₅と、テンプレート画像２２のＧ成分の濃度慣性モーメントＭ₂₂とを比較し、２つのＧ成分の濃度慣性モーメントＭ₂₅,Ｍ₂₂の差分の絶対値を出力する（出力値Ｏ_G）。さらに、ステップＳ２３では、部分画像２５のＢ成分の濃度慣性モーメントＭ₂₅と、テンプレート画像２２のＢ成分の濃度慣性モーメントＭ₂₂とを比較し、２つのＢ成分の濃度慣性モーメントＭ₂₅,Ｍ₂₂の差分の絶対値を出力する（出力値Ｏ_B）。 First (step S21 in FIG. 8), the image processing unit 14 compares the concentration of inertia moment M ₂₅ of the R component of the partial image 25, and a concentration of inertia moment M ₂₂ of the R component of the template image 22, the two R components The absolute value of the difference between the concentration inertia moments M ₂₅ and M ₂₂ is output. The output value O _{R in} this case is an index relating to the similarity between the concentration inertia moments M ₂₅ and M ₂₂ of the R component.
Similarly, in step S22, the concentration of inertia moment M ₂₅ of the G component of the partial image 25 is compared with the concentration of inertia moment M ₂₂ of the G component of the template image 22, density moment of inertia of the two G components M _25, M The absolute value of the difference of ₂₂ is output (output value O _G ). Further, in step S23, the B component concentration inertia moment M _{25 of} the partial image 25 is compared with the B component concentration inertia moment M _{22 of} the template image 22, and the two B component concentration inertia moments M ₂₅ and M ₂₂ are compared. The absolute value of the difference is output (output value O _B ).

上記した通り、演算用の部分画像２５は円形状であり、この部分画像２５から算出した濃度慣性モーメントＭ₂₅は、ＲＧＢ成分の何れも、入力画像２１の回転変化に対して不変な特徴量である。したがって、上記したステップＳ２１のＲ成分の出力値Ｏ_Rと、ステップＳ２２のＧ成分の出力値Ｏ_Gと、ステップＳ２３のＢ成分の出力値Ｏ_Bは、各々、入力画像２１の回転変化に対して不変な特徴量と考えられる。 As described above, the calculation partial image 25 has a circular shape, and the density moment of inertia M ₂₅ calculated from the partial image ₂₅ is a feature amount that is invariant to the rotational change of the input image 21. is there. Accordingly, the output value O _R of the R component in step S21 described above, the output value O _G of the G component in step S22, the output value O _B of the B component in step S23, respectively, with respect to the rotation change of the input image 21 Is considered to be an invariant feature.

次に（ステップＳ２４）、画像処理部１４は、上記したステップＳ２１〜Ｓ２３の各々の出力値Ｏ_R,Ｏ_G,Ｏ_Bの和を求め、その値を「部分画像２５とテンプレート画像２２との類似度」とする。この類似度（＝Ｏ_R＋Ｏ_G＋Ｏ_B）は、部分画像２５とテンプレート画像２２との「類似性に関する指標」であり、入力画像２１の回転変化に対して不変な特徴量と考えられる。また、類似度（＝Ｏ_R＋Ｏ_G＋Ｏ_B）の傾向は、その値が小さいほど、部分画像２５とテンプレート画像２２との類似性が高く、部分画像２５の抽出位置(Ｘ₂,Ｙ₂)が合致位置(Ｘ₁,Ｙ₁)に近いことを表す。 Then (step S24), and the image processing unit 14 obtains the sum of the above-described respective output values O _R of Step S21 to S23, O _G, O _B, the value of the "partial image 25 and the template image 22 "Similarity". This degree of similarity (= O _R + O _G + O _B ) is an “index for similarity” between the partial image 25 and the template image 22, and is considered to be a feature quantity that is invariant with respect to the rotational change of the input image 21. The tendency of the similarity (= O _R + O _G + O _B ) is higher as the value is smaller, and the similarity between the partial image 25 and the template image 22 is higher, and the extraction position (X ₂ , Y ₂ ) of the partial image 25 Is close to the matching position (X ₁ , Y ₁ ).

第２実施形態のテンプレートマッチングでは、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を少しずつ移動させながら、各々の位置で部分画像２５を順に抽出し、部分画像２５を抽出する毎に、ＲＧＢ成分の濃度慣性モーメントＭ₂₅,Ｍ₂₂に基づいてマッチング演算（Ｓ２１〜Ｓ２４）を繰り返し行う。そして、入力画像２１の中の異なる複数の位置で求められた類似度（＝Ｏ_R＋Ｏ_G＋Ｏ_B）を大小比較することにより、その値が最も小さく、テンプレート画像２２との類似性が最も高い部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を合致位置(Ｘ₁,Ｙ₁)と特定する。 In the template matching of the second embodiment, the partial image 25 is sequentially extracted at each position while the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation is moved little by little, and the partial image 25 is extracted. Each time, the matching calculation (S21 to S24) is repeatedly performed based on the density inertia moments M ₂₅ and M ₂₂ of the RGB components. Then, the similarities (= O _R + O _G + O _B ) obtained at a plurality of different positions in the input image 21 are compared in magnitude, so that the value is the smallest and the similarity to the template image 22 is the highest. The extraction position (X ₂ , Y ₂ ) of the partial image 25 is specified as the matching position (X ₁ , Y ₁ ).

上記のように、第２実施形態のテンプレートマッチングでは、マッチング演算（Ｓ２１〜Ｓ２４）の結果である類似度（＝Ｏ_R＋Ｏ_G＋Ｏ_B）が、図５に示すような入力画像２１の回転変化に対して不変な特徴量として求められ、この類似度（＝Ｏ_R＋Ｏ_G＋Ｏ_B）を大小比較する。このため、入力画像２１に回転変化があっても正確に合致位置(Ｘ₁,Ｙ₁)を特定することができる。 As described above, in the template matching of the second embodiment, the similarity (= O _R + O _G + O _B ), which is the result of the matching calculation (S21 to S24), is the rotational change of the input image 21 as shown in FIG. The similarity (= O _R + O _G + O _B ) is compared in magnitude. For this reason, even if there is a rotational change in the input image 21, the matching position (X ₁ , Y ₁ ) can be accurately specified.

さらに、第２実施形態のテンプレートマッチングでは、各々の画像(２１,２５,２２)に含まれる全ての色成分（つまりＲＧＢ成分）の濃度慣性モーメントＭ₂₅,Ｍ₂₂に基づいて、同じ色成分どうしを比較することにより、マッチング演算(Ｓ２１〜Ｓ２４)を行う。このため、多くの情報量を確保でき、より正確に合致位置(Ｘ₁,Ｙ₁)を特定できる。
（第３実施形態）
ここでは、演算用の部分画像２５とテンプレート画像２２とのマッチング演算を、後述の領域濃度差に基づいて行う場合を説明する。第３実施形態のテンプレートマッチングは、図３のステップＳ１,Ｓ３において“濃度ヒストグラム”の代わりに“領域濃度差”を算出し、図８のステップＳ２１〜Ｓ２４において“濃度慣性モーメント”の代わりに“領域濃度差”を用いるものである。第３実施形態でも、ＲＧＢ成分を含む画像(２１,２５,２２)を例に説明する。 Furthermore, in the template matching of the second embodiment, the same color components are based on the density inertia moments M ₂₅ and M ₂₂ of all color components (that is, RGB components) included in each image (21, ₂₅ , ₂₂ ). Are compared to perform a matching operation (S21 to S24). For this reason, a large amount of information can be secured, and the matching position (X ₁ , Y ₁ ) can be specified more accurately.
(Third embodiment)
Here, a case will be described in which the matching calculation between the calculation partial image 25 and the template image 22 is performed based on a region density difference described later. In the template matching of the third embodiment, “region density difference” is calculated instead of “density histogram” in steps S1 and S3 of FIG. 3, and “density moment of inertia” is substituted for “density inertia moment” in steps S21 to S24 of FIG. The “region density difference” is used. In the third embodiment, an image (21, 25, 22) including RGB components will be described as an example.

まず（図３のＳ１のタイミングで）、画像処理部１４は、テンプレート画像２２の全体からＲＧＢ成分の領域濃度差Ｄ₂₂を各色成分ごとに算出する。例えば、Ｒ成分の領域濃度差Ｄ₂₂は、テンプレート画像２２のＲ成分（図１０）の予め定めた中央領域２Ａと周辺領域２Ｂとの各々における平均濃度の差により算出される（式(２)）。なお、中央領域２Ａと周辺領域２Ｂは、請求項の「第１範囲」と「第２範囲」に対応する。 First (at the timing of S1 in FIG. 3), the image processing unit 14 calculates an area density difference D ₂₂ of the RGB components for each color component from the entire template image 22. For example, the R component region density difference D ₂₂ is calculated by the difference in average density between the predetermined central region 2A and the peripheral region 2B of the R component (FIG. 10) of the template image 22 (formula (2)). ). The central region 2A and the peripheral region 2B correspond to “first range” and “second range” in the claims.

Ｄ₂₂＝ (中央領域２Ａの平均濃度)−(周辺領域２Ｂの平均濃度) …(２)
式(２)の領域濃度差Ｄ₂₂は、周辺領域２Ｂに対する中央領域２Ａの平均的な濃度差を表している。このため、例えば図１１(ａ)に示すように、テンプレート画像２２のＲ成分が、暗い背景（濃度値が最小）の中央に明るい点（濃度値が最大）を含むような場合、濃度値を２５６段階（０〜２５５）とすると、中央領域２Ａは大きな平均濃度(例えば２０５)、周辺領域２Ｂは小さな平均濃度(例えば２１)となり、式(２)の領域濃度差Ｄ₂₂は大きなプラスの値(例えば１８４)となる。逆に中央領域２Ａが暗く周辺領域２Ｂが明るい場合、領域濃度差Ｄ₂₂はマイナスの値になる。 D ₂₂ = (average density of central area 2A) − (average density of peripheral area 2B) (2)
The area density difference D _{22 in} the expression (2) represents an average density difference of the central area 2A with respect to the peripheral area 2B. Therefore, for example, as shown in FIG. 11A, when the R component of the template image 22 includes a bright point (density value is maximum) in the center of a dark background (density value is minimum), the density value is changed. When 256 (0 to 255), large average concentration (e.g. 205) is the central area 2A, the peripheral region 2B is small average concentration (e.g. 21), and the area density difference D ₂₂ is large positive value of the expression (2) (For example, 184). If conversely the central area 2A is dark peripheral region 2B is bright, the area density difference D ₂₂ becomes a negative value.

また、例えば図１１(ｂ)に示すように、テンプレート画像２２のＲ成分が、暗い背景（濃度値が最小）の中に分散して多数の明るい点（濃度値が最大）を含むような場合、中央領域２Ａは中間的な平均濃度(例えば１２３)、周辺領域２Ｂも中間的な平均濃度(例えば１０８)となり、式(２)の領域濃度差Ｄ₂₂は小さな値(例えば１５)となる。上記したＲＧＢ成分の領域濃度差Ｄ₂₂は、画素の位置に依存しない特徴量である。 Further, for example, as shown in FIG. 11B, the R component of the template image 22 includes many bright spots (maximum density value) dispersed in a dark background (density value is minimum). the central region 2A is an intermediate average concentration (e.g. 123), the peripheral region 2B also intermediate average density (e.g. 108), and the area density difference D ₂₂ of the formula (2) is a small value (e.g., 15). The above-described RGB component region density difference D ₂₂ is a feature quantity independent of the pixel position.

また、画像処理部１４は、入力画像２１の中から円形状の部分画像２５をマッチング演算用に抽出すると、図３のＳ３のタイミングで、部分画像２５の全体からＲＧＢ成分の領域濃度差Ｄ₂₅を各色成分ごとに算出する。例えば、Ｒ成分の領域濃度差Ｄ₂₅の算出は、部分画像２５のＲ成分の全体から、テンプレート画像２２と同じ中央領域２Ａ,周辺領域２Ｂ（図１０）を用い、上記した式(２)と同様の式により行われる。Ｇ成分,Ｂ成分も同様である。ＲＧＢ成分の領域濃度差Ｄ₂₅は、画素の位置に依存しない特徴量である。 When the image processing unit 14 extracts the circular partial image 25 from the input image 21 for matching calculation, the RGB component region density difference D ₂₅ is extracted from the entire partial image 25 at the timing of S3 in FIG. Is calculated for each color component. For example, the calculation of the R component region density difference D ₂₅ uses the same central region 2A and peripheral region 2B (FIG. 10) as the template image 22 from the entire R component of the partial image 25, and the above equation (2) and The same formula is used. The same applies to the G component and the B component. The RGB component region density difference D ₂₅ is a feature quantity independent of the pixel position.

ここで、演算用の部分画像２５の領域濃度差Ｄ₂₅と、入力画像２１の回転変化との関係について説明する。既に説明した通り、入力画像２１に回転変化（図５参照）があると、矩形状の部分画像２４の濃度情報は四隅付近で変化するが、円形状の部分画像２５の濃度情報は変化しない。このため、円形状の部分画像２５から算出した領域濃度差Ｄ₂₅は、入力画像２１の回転変化に対して不変な特徴量と考えられる。 Here, the area density difference D ₂₅ of the partial image 25 for computation, the relationship between the rotation change of the input image 21 will be described. As described above, when the input image 21 has a rotational change (see FIG. 5), the density information of the rectangular partial image 24 changes near the four corners, but the density information of the circular partial image 25 does not change. For this reason, the area density difference D ₂₅ calculated from the circular partial image 25 is considered to be a feature quantity that is invariant to the rotational change of the input image 21.

画像処理部１４は、上記のようにして、テンプレート画像２２の領域濃度差Ｄ₂₂と、部分画像２５の領域濃度差Ｄ₂₅とを算出し終えると、２つの領域濃度差Ｄ₂₂,Ｄ₂₅に基づいて、部分画像２５とテンプレート画像２２とのマッチング演算を行う。
まず（図８のステップＳ２１のタイミングで）、画像処理部１４は、部分画像２５のＲ成分の領域濃度差Ｄ₂₅と、テンプレート画像２２のＲ成分の領域濃度差Ｄ₂₂（図１１(ａ)の場合は１８４)(図１１(ｂ)の場合は１５）とを比較し、２つのＲ成分の領域濃度差Ｄ₂₅,Ｄ₂₂の差分の絶対値を出力する。この出力値Ｐ_Rは、Ｒ成分の領域濃度差Ｄ₂₅,Ｄ₂₂の類似性に関する指標である。 The image processing unit 14, as described above, the area density difference D ₂₂ of the template image 22, after finishing calculating an area density difference D ₂₅ of the partial image 25, into two regions density difference D _22, D ₂₅ Based on this, a matching operation between the partial image 25 and the template image 22 is performed.
First (at the timing of step S21 in FIG. 8), the image processing unit 14 determines the R component area density difference D ₂₅ of the partial image 25 and the R component area density difference D 22 of the template image ₂₂ (FIG. 11A). 184) (15 in the case of FIG. 11B) and the absolute value of the difference between the two R component area density differences D ₂₅ and D ₂₂ is output. The output value P _R is a measure of the similarity in the region of the R component concentration difference D _25, D _22.

同様に（図８のステップＳ２２のタイミングで）、部分画像２５のＧ成分の領域濃度差Ｄ₂₅と、テンプレート画像２２のＧ成分の領域濃度差Ｄ₂₂とを比較し、２つのＧ成分の領域濃度差Ｄ₂₅,Ｄ₂₂の差分の絶対値を出力する（出力値Ｐ_G）。さらに（ステップＳ２３のタイミングで）、部分画像２５のＢ成分の領域濃度差Ｄ₂₅と、テンプレート画像２２のＢ成分の領域濃度差Ｄ₂₂とを比較し、２つのＢ成分の領域濃度差Ｄ₂₅,Ｄ₂₂の差分の絶対値を出力する（出力値Ｐ_B）。 Similarly (at the timing of step S22 in FIG. 8), the G component region density difference D _{25 of} the partial image 25 is compared with the G component region density difference D _{22 of} the template image 22, and two G component regions are compared. The absolute value of the difference between the density differences D ₂₅ and D ₂₂ is output (output value P _G ). Further (at the timing of step S23), the B component area density difference D _{25 of} the partial image 25 is compared with the B component area density difference D _{22 of} the template image 22, and the two B component area density differences D ₂₅ are compared. , D ₂₂ is output as an absolute value (output value P _B ).

上記した通り、演算用の部分画像２５は円形状であり、この部分画像２５から算出した領域濃度差Ｄ₂₅は、ＲＧＢ成分の何れも、入力画像２１の回転変化に対して不変な特徴量である。したがって、上記したＲ成分の出力値Ｐ_Rと、Ｇ成分の出力値Ｐ_Gと、Ｂ成分の出力値Ｐ_Bは、各々、入力画像２１の回転変化に対して不変な特徴量と考えられる。
次に（ステップＳ２４のタイミングで）、画像処理部１４は、上記したＲＧＢ成分の出力値Ｐ_R,Ｐ_G,Ｐ_Bの和を求め、その値を「部分画像２５とテンプレート画像２２との類似度」とする。この類似度（＝Ｐ_R＋Ｐ_G＋Ｐ_B）は、部分画像２５とテンプレート画像２２との「類似性に関する指標」であり、入力画像２１の回転変化に対して不変な特徴量と考えられる。また、類似度（＝Ｐ_R＋Ｐ_G＋Ｐ_B）の傾向は、その値が大きいほど、部分画像２５とテンプレート画像２２との類似性が高く、部分画像２５の抽出位置(Ｘ₂,Ｙ₂)が合致位置(Ｘ₁,Ｙ₁)に近いことを表す。 As described above, the partial image 25 for calculation has a circular shape, and the region density difference D ₂₅ calculated from the partial image ₂₅ is a feature amount that is invariant to the rotational change of the input image 21. is there. Accordingly, the output value PR of the _R component, the output value P _G of the _G component, and the output value P _B of the B component are each considered to be a feature amount that is invariant to the rotational change of the input image 21.
Next (at the timing of step S24), the image processing unit 14 obtains the sum of the output values P _R , P _G , and P _B of the RGB components described above, and determines the value as “similarity between the partial image 25 and the template image 22”. "Degree". This degree of similarity (= P _R + P _G + P _B ) is an “index for similarity” between the partial image 25 and the template image 22, and is considered to be a feature quantity that is invariant to the rotational change of the input image 21. Further, the tendency of the similarity (= P _R + P _G + P _B ) is higher as the value is larger, and the similarity between the partial image 25 and the template image 22 is higher, and the extraction position (X ₂ , Y ₂ ) of the partial image 25 is higher. Is close to the matching position (X ₁ , Y ₁ ).

第３実施形態のテンプレートマッチングでは、演算用の部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を少しずつ移動させながら、各々の位置で部分画像２５を順に抽出し、部分画像２５を抽出する毎に、ＲＧＢ成分の領域濃度差Ｄ₂₅,Ｄ₂₂に基づいてマッチング演算を繰り返し行う。そして、入力画像２１の中の異なる複数の位置で求められた類似度（＝Ｐ_R＋Ｐ_G＋Ｐ_B）を大小比較することにより、その値が最も大きく、テンプレート画像２２との類似性が最も高い部分画像２５の抽出位置(Ｘ₂,Ｙ₂)を合致位置(Ｘ₁,Ｙ₁)と特定する。 In the template matching of the third embodiment, the partial image 25 is extracted in order at each position while the extraction position (X ₂ , Y ₂ ) of the partial image 25 for calculation is moved little by little, and the partial image 25 is extracted. Each time, the matching calculation is repeated based on the RGB component area density differences D ₂₅ and D ₂₂ . Then, by comparing the similarities (= P _R + P _G + P _B ) obtained at a plurality of different positions in the input image 21, the value is the largest and the similarity to the template image 22 is the highest. The extraction position (X ₂ , Y ₂ ) of the partial image 25 is specified as the matching position (X ₁ , Y ₁ ).

上記のように、第３実施形態のテンプレートマッチングでは、マッチング演算（Ｓ２１〜Ｓ２４参照）の結果である類似度（＝Ｐ_R＋Ｐ_G＋Ｐ_B）が、図５に示すような入力画像２１の回転変化に対して不変な特徴量として求められ、この類似度（＝Ｐ_R＋Ｐ_G＋Ｐ_B）を大小比較する。このため、入力画像２１に回転変化があっても正確に合致位置(Ｘ₁,Ｙ₁)を特定することができる。 As described above, in the template matching according to the third embodiment, the similarity (= P _R + P _G + P _B ) as a result of the matching calculation (see S21 to S24) is the rotation of the input image 21 as shown in FIG. It is obtained as a feature quantity that is invariant to changes, and this similarity (= P _R + P _G + P _B ) is compared in magnitude. For this reason, even if there is a rotational change in the input image 21, the matching position (X ₁ , Y ₁ ) can be accurately specified.

また、演算用の部分画像２５の濃度範囲とテンプレート画像２２の濃度範囲とを一致させることにより（正規化処理）、入力画像２１のコントラストの変化やノイズにも対応でき、正確に合致位置(Ｘ₁,Ｙ₁)を特定することができる。
さらに、第３実施形態のテンプレートマッチングでは、各々の画像(２１,２５,２２)に含まれる全ての色成分（つまりＲＧＢ成分）の領域濃度差Ｄ₂₅,Ｄ₂₂に基づいて、同じ色成分どうしを比較することにより、マッチング演算(Ｓ２１〜Ｓ２４参照)を行う。このため、多くの情報量を確保でき、より正確に合致位置(Ｘ₁,Ｙ₁)を特定できる。
（変形例）
なお、上記した実施形態では、濃度ヒストグラムＨ₂₅,Ｈ₂₂に基づくマッチング演算の例と、濃度慣性モーメントＭ₂₅,Ｍ₂₂に基づくマッチング演算の例と、領域濃度差Ｄ₂₅,Ｄ₂₂に基づくマッチング演算の例をそれぞれ説明したが、本発明はこれに限定されない。任意の２種類を組み合わせてマッチング演算を行う場合にも、本発明を適用できる。あるいは相互相関や最小残差と濃度ヒストグラムなどを組み合わせてもよい。 Further, by matching the density range of the partial image 25 for calculation with the density range of the template image 22 (normalization processing), it is possible to cope with the contrast change and noise of the input image 21 and accurately match the matching position (X ₁ , Y ₁ ) can be specified.
Furthermore, in the template matching of the third embodiment, the same color components are based on the area density differences D ₂₅ and D ₂₂ of all the color components (that is, RGB components) included in each image (21, ₂₅ , ₂₂ ). Are compared to perform a matching operation (see S21 to S24). For this reason, a large amount of information can be secured, and the matching position (X ₁ , Y ₁ ) can be specified more accurately.
(Modification)
In the embodiment described above, an example of the matching calculation based on the density histograms H ₂₅ and H ₂₂ , an example of the matching calculation based on the density inertia moments M ₂₅ and M _22, and the matching based on the area density differences D ₂₅ and D ₂₂ Although the example of each calculation was demonstrated, this invention is not limited to this. The present invention can also be applied to a case where a matching operation is performed by combining two arbitrary types. Alternatively, cross-correlation, minimum residual and density histogram may be combined.

また、上記した実施形態では、３つの色成分（つまりＲＧＢ成分）を含む画像(２１,２５,２２)の例で説明したが、本発明はこれに限定されない。色成分の数が２つであっても４つ以上であっても本発明を適用できる。つまり複数の色成分を含む場合に本発明を適用できる。さらに、画像(２１,２５,２２)が複数の色成分を含まない場合、つまり単色の濃淡画像である場合にも、本発明を適用できる。 In the above-described embodiment, the example of the image (21, 25, 22) including three color components (that is, RGB components) has been described, but the present invention is not limited to this. The present invention can be applied regardless of whether the number of color components is two or four or more. That is, the present invention can be applied to a case where a plurality of color components are included. Furthermore, the present invention can also be applied to a case where the image (21, 25, 22) does not include a plurality of color components, that is, a single-color gray image.

また、上記した実施形態では、入力画像２１の中から円形状の部分画像２５を抽出する処理を２段階で行う例（図２参照）を説明したが、本発明はこれに限定されない。入力画像２１の中から直接（１回の処理で）円形状の部分画像２５を抽出しても構わない。
さらに、上記した実施形態では、図１の観察装置１０のような光学顕微鏡装置を例にテンプレートマッチングの説明を行ったが、本発明はこれに限定されない。その他、試料の局所領域を電子線で走査して画像を取り込む電子顕微鏡装置にも、本発明を適用できる。試料の局所領域の画像に限らず、試料の全面の画像を一括で取り込む装置にも、本発明を適用できる。観察装置１０などに接続された外部のコンピュータを用いた場合でも、同様の効果を得ることができる。 In the above-described embodiment, an example (see FIG. 2) in which the process of extracting the circular partial image 25 from the input image 21 is described in two stages has been described, but the present invention is not limited to this. A circular partial image 25 may be directly extracted from the input image 21 (by one process).
Furthermore, in the above-described embodiment, the template matching has been described by taking an optical microscope apparatus such as the observation apparatus 10 in FIG. 1 as an example, but the present invention is not limited to this. In addition, the present invention can also be applied to an electron microscope apparatus that scans a local region of a sample with an electron beam and captures an image. The present invention can be applied not only to an image of a local region of a sample but also to an apparatus that captures an image of the entire surface of the sample at once. Even when an external computer connected to the observation apparatus 10 or the like is used, the same effect can be obtained.

観察装置１０の概略図である。1 is a schematic view of an observation apparatus 10. FIG. 入力画像２１,テンプレート画像２２,ターゲット２３,演算用の部分画像２５などを説明する図である。It is a figure explaining the input image 21, the template image 22, the target 23, the partial image 25 for a calculation, etc. 第１実施形態のテンプレートマッチングの処理手順を示すフローチャートである。It is a flowchart which shows the process sequence of the template matching of 1st Embodiment. テンプレート画像２２のＲＧＢ成分の濃度ヒストグラムＨ₂₂と部分画像２５のＲＧＢ成分の濃度ヒストグラムＨ₂₅とを説明する図である。It is a diagram for explaining a density histogram H ₂₅ of the RGB components of the density histogram H ₂₂ and the partial image 25 of the RGB components of the template image 22. 円形状の演算用の部分画像２５における濃度情報と、入力画像２１の回転変化との関係を説明する図である。It is a figure explaining the relationship between the density information in the partial image 25 for circular calculation, and the rotation change of the input image. ＲＧＢ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の重なり部分に基づくマッチング演算について説明する図である。Is a diagram for matching operation will be described based on the overlapping portion of the RGB components of the density histogram H _25, H _22. ＲＧＢ成分の濃度ヒストグラムＨ₂₅,Ｈ₂₂の差分に基づくマッチング演算について説明する図である。It is a figure explaining the matching calculation based on the difference of density histograms H ₂₅ and H ₂₂ of RGB components. 第２実施形態のテンプレートマッチングにおける処理手順の一部を示すフローチャートである。It is a flowchart which shows a part of process procedure in the template matching of 2nd Embodiment. Ｒ成分の濃度慣性モーメントＭ₂₂について説明する図である。Is a diagram illustrating the concentration of inertia moment M ₂₂ of the R component. 第３実施形態において領域濃度差Ｄ₂₅,Ｄ₂₂を算出するための領域について説明する図である。It is a diagram illustrating a region for calculating the area density difference D _25, D ₂₂ in the third embodiment. テンプレート画像２２のＲ成分の一例について説明する図である。It is a figure explaining an example of R component of template image. 矩形状の演算用の部分画像における濃度情報と、入力画像の回転変化との関係を説明する図である。It is a figure explaining the relationship between the density information in the partial image for a rectangular calculation, and the rotation change of an input image.

Explanation of symbols

１０観察装置
１１ステージ
１２光学系
１３カメラ
１４画像処理部
２１入力画像
２２テンプレート画像
２３ターゲット
２５演算用の部分画像 DESCRIPTION OF SYMBOLS 10 Observation apparatus 11 Stage 12 Optical system 13 Camera 14 Image processing part 21 Input image 22 Template image 23 Target 25 Partial image for calculation

Claims

First creation means for creating a histogram of the density of a known circular template image;
Extraction means for extracting partial images for circular calculation from a plurality of different positions in the input image;
Second creation means for creating a density histogram of the partial image extracted by the extraction means;
An arithmetic means for obtaining a similarity between the template image and the partial image based on the histogram of the template image and the histogram of the partial image;
A template matching device comprising: specifying means for specifying a matching position with the template image in the input image by comparing the similarity obtained at each position of the input image. .

First calculating means for calculating a moment of inertia of the density of a known circular template image;
Extraction means for extracting partial images for circular calculation from a plurality of different positions in the input image;
Second calculating means for calculating the moment of inertia of the density of the partial image extracted by the extracting means;
An arithmetic means for obtaining a similarity between the template image and the partial image based on the inertia moment of the template image and the inertia moment of the partial image;
A template matching device comprising: specifying means for specifying a matching position with the template image in the input image by comparing the similarity obtained at each position of the input image. .

First calculating means for calculating a difference in average density in each of a predetermined first range and a second range of a known template image having a circular shape;
Extraction means for extracting partial images for circular calculation from a plurality of different positions in the input image;
Second calculating means for calculating a difference in average density in each of the first range and the second range of the partial image extracted by the extracting means;
An arithmetic means for obtaining a similarity between the template image and the partial image based on the difference in average density of the template image and the difference in average density of the partial image;
A template matching device comprising: specifying means for specifying a matching position with the template image in the input image by comparing the similarity obtained at each position of the input image. .

The template matching apparatus according to claim 1,
The template image, the input image, and the partial image include a plurality of color components,
The first creation means creates the histogram of the template image for each color component,
The second creation means creates the histogram of the partial image for each color component,
The computing means obtains the similarity by comparing the same color components based on the histogram of each color component of the template image and the histogram of each color component of the partial image. Matching device.

The template matching device according to claim 2,
The template image, the input image, and the partial image include a plurality of color components,
The first calculating means calculates the moment of inertia of the template image for each color component,
The second calculating means calculates the moment of inertia of the partial image for each color component,
The calculation means obtains the similarity by comparing the same color components based on the moment of inertia of each color component of the template image and the moment of inertia of each color component of the partial image. Template matching device.

The template matching apparatus according to claim 3,
The template image, the input image, and the partial image include a plurality of color components,
The first calculation means calculates a difference in the average density of the template image for each color component,
The second calculation means calculates a difference in the average density of the partial images for each color component,
The calculation means obtains the similarity by comparing the same color components based on the difference between the average densities of the color components of the template image and the difference of the average densities of the color components of the partial image. A template matching apparatus characterized by that.