JPH0442711B2 - - Google Patents

Description

[Detailed Description of the Invention] Industrial Application Field The present invention provides a method for quickly determining the position of a specific pattern present in an image pattern obtained from an imaging device, which is necessary when mounting IC components on a circuit board, for example. The present invention relates to a pattern matching method used in a two-dimensional position detection method and the like.

BACKGROUND TECHNOLOGY Conventional position detection methods using pattern matching can be broadly classified as follows: 1. After storing one frame of an image pattern obtained from an imaging device in an image pattern storage device such as a semiconductor memory, matching processing with a standard pattern is performed. Method.

2. A device that generates the coordinates of the position where the imaging device is scanning, and an image pattern storage device such as a semiconductor memory that has the minimum capacity necessary for matching with the standard pattern. A method to perform the matching process while importing image patterns.

It can be classified into two types.

Therefore, we will examine three items regarding these two pattern matching methods: processing speed, processing scalability, and cost.

First, regarding the processing speed, the first method performs the matching process after capturing one frame of the image pattern into the storage device, which generally requires processing time and is not suitable for real-time processing. Image pattern 1
Assuming that the time required to import frames into the storage device is T _i and the time required to match the image pattern imported to the storage device with the standard pattern is T _p , the time required for pattern matching using the first method is T. _n1 is expressed as the sum of T _i and T _p as in equation (1).

T _n1 = T _i + T _p ...(1) In equation (1), the time T _i required to capture the image is constant, but the time T _p required to match the image pattern with the standard pattern varies depending on the processing method. They are very different, and by using a high-speed method in which the matching process is hierarchically divided into coarse matching and detailed matching, it is possible to shorten the matching process to the extent that real-time processing is possible. The second method performs the matching process while capturing the image pattern, so the processing time is short and it is suitable for real-time processing. The time T _n2 required for pattern matching by the second method is equal to T _i and is expressed as in equation (2).

T _n2 = T _i ...(2) Next, we will discuss the extensibility of processing. In the first method, the image pattern obtained from the imaging device is stored in the storage device, so the weighting of operators can be freely set in processing such as filtering, which is preprocessing for matching with standard patterns. After the matching process is completed, it is possible to selectively extract a specific area of the image pattern again and perform the confirmation process based on the result. Furthermore, when performing the matching process, it is also possible to scan the matching reference point in a direction perpendicular to the scanning direction of the imaging device. In the second method, preprocessing such as filtering and confirmation processing after collation processing are possible, but preprocessing is fixed and operator weights during filtering processing cannot be easily changed. Also, the confirmation process after the matching process cannot be performed on the same screen where the matching result was obtained.

Finally, we will discuss the cost of realizing a pattern matching device using these two methods.
The first method requires more storage elements such as semiconductor IC memories than the second method in order to store one frame of image patterns. The process of comparing the image pattern with the standard pattern at this time is performed by the microcomputer and the control program of the microcomputer in a flexible process as described in the discussion of the extensibility of the above-mentioned process. On the other hand, in the second method, the image pattern sent in real time is compared with the standard pattern, so
Unlike the first method, a large amount of semiconductor IC memory is not required to store the image pattern, but the image pattern is compared with the standard pattern at the speed at which the signal representing the image pattern obtained by digitizing the video signal flows. Therefore, this method requires more logic ICs than the first method. In the past, semiconductor IC memories were expensive and it was difficult to realize the first method at a low cost, but in recent years the degree of integration of semiconductor IC memories has increased rapidly, and the price per unit storage capacity has decreased, making it difficult to realize the first method at a low cost. The price is becoming cheaper than the logic IC used to implement the method. Therefore, at present, it is possible to realize a pattern matching device at a lower cost by adopting the first method.

The present invention relates to a pattern matching method for performing two-dimensional position detection in real time using the first method described above. The reason why the first method, which is unsuitable for high-speed processing, was intentionally adopted is because the pattern matching process is highly scalable and flexible, as described above, and it can be realized at a lower cost than the second method. In the present invention, in the pattern matching method according to the first method, the time required for matching processing of an image pattern and a standard pattern is
In order to shorten T _p , we adopt a hierarchical pattern matching method consisting of coarse matching and detailed matching. In particular, in the present invention, matching is performed at first matching reference points that are roughly provided every few pixels on the image pattern, and if a degree of matching equal to or higher than the first passing reference value is obtained, the result is immediately passed. A second matching reference point is generated for each pixel based on the first matching reference point, which has become a reference point, and a second matching is performed to find a recognition point. The method is to continue until it is detected.

Problems to be Solved by the Invention However, in the above configuration, one recognition point is detected multiple times from a plurality of first reference points, and each time a recognition point is detected, It becomes necessary to determine whether the point is the same as a recognition point detected in the past.

FIG. 2 shows two first matching reference points 21 and 22 provided every four pixels on the image pattern, and square small areas 23 and 24 each having a size of 5 pixels on one side where the second matching is performed. , and the recognition points 25 included in these two small areas. In order to avoid missing recognition points, the small areas for the second comparison set corresponding to the adjacent first reference points are set so as to overlap each other little by little, as shown in Figure 2. It will be done. Therefore, if the recognition point is included in the common part of the two small areas where the second verification is performed, as in the case of FIG. 2, the first verification process at the first verification reference point 21 is passed. After that, a small area 23 is set based on the first matching reference point 21, and a second matching process is performed at second matching reference points provided every other pixel within the small area 23, and the recognition point is 25 is detected first. Next, the process moves to the first matching reference point 22, and a series of matching processes starting from the first matching process performed previously at the first matching reference point 21 is performed, and the recognition point 25 is detected again. . In the example of FIG. 2, depending on the position of the recognition point, there is a possibility that the same recognition point will be detected four times from a maximum of four first reference points. In this case, it must be determined whether the recognition point detected for the second time or later is the same as the recognition point detected first. Further, in the process of performing pattern matching processing, since the exact number of recognition points is not known, the processing cannot be terminated when the desired number of recognition points is obtained.

In view of the above-mentioned problems, the present invention provides a flag corresponding to a first matching reference point provided every n pixels on an image pattern, and when a recognition point is detected from a certain first matching reference point, , by setting the flag to "1" for the first matching reference points around the first matching reference point, the same recognition point is detected multiple times from a plurality of first matching reference points. The number of detected recognition points can be accurately counted, and when the desired number of recognition points has been obtained, the process can be terminated at that point, thereby speeding up the processing. The present invention provides a pattern matching method that aims to achieve

Means for Solving the Problems The present invention provides the following advantages when using a hierarchical pattern matching method that performs matching in two or more stages.
A flag storage area having an initial value "0" of 1 bit per point is provided for the first matching reference point set every several pixels over the entire area of the image pattern. If the first verification is passed and a recognition point is detected in the second verification, the first verification reference point that led to the detection of the recognition point and a plurality of first verification points existing in the vicinity thereof The bit in the flag storage area corresponding to the reference point is rewritten from "0" to "1", and in subsequent processing, the first matching standard corresponding to the bit set to "1" in the flag storage area is rewritten. At this point, the first verification is not performed.

Such a method consists of an analog-to-digital conversion means that digitizes the video signal obtained from the imaging means into an image pattern, a storage means such as a frame memory that holds the digitized image pattern, and a method that converts the image signal into an image pattern. control a storage means such as a register that stores in advance a characteristic pattern to be used as a standard pattern; a flag storage means corresponding to first matching reference points provided every few pixels on the image pattern; and a flag storage area. Middle East processing means such as a flag control means, a matching processing means for matching the image pattern and the standard pattern, a matching degree calculation means for calculating the degree of matching obtained as a result of matching, and a microcomputer that comprehensively controls each of the above means. It will be realized.

Effect: With the above method, the first matching is not performed between the first matching reference point that led to the detection of one recognition point and the plurality of first matching reference points that exist in the vicinity of the first matching reference point. This prevents the recognition point from being detected multiple times from multiple first reference points.

Further, the effects of the above technical means will also be explained with reference to the drawings.

FIG. 3 shows a standard pattern 31 having a size of M×M, a matching reference point 32 on the standard pattern side, and a standard pattern 31 having a size of M×M.
It shows an image pattern 33 having a size of N (however, the pattern is not shown) and first matching reference points 34 provided every n pixels on the image pattern. The first image existing on the image pattern 33
The number of reference points 34 is given by the following equation (3).

[N-N/n+1] ² ...(3) [a] is a Gaussian symbol and represents the largest integer not exceeding a. For example, if M=16, N=512, and n=4, the number of first matching reference points is approximately 15,600, and a flag storage area corresponding to this number of bits is required. As shown in FIG. 4, the flag storage area 41 is selected by x and y addresses in one-to-one correspondence with the array of first matching reference points provided on the image pattern. The initial value "0" is given. In the pattern matching process, before performing the first matching process, the flag corresponding to the target first matching reference point is checked, and if the flag is "0", the first matching process is performed at that matching reference point. If the flag is set to "1", the first verification process is not performed and the next first verification process is performed.
The same process will be continued by moving to the matching reference point.

FIG. 5 shows an area 52 in which a bit is set to "1" in the flag storage area 51 when a recognition point is detected by performing pattern matching processing in the same direction as the scanning direction of the imaging device. . The area 52 where the bit is set to "1" is centered around the flag 53 corresponding to the first matching reference point from which the recognition point was detected, and the first matching reference point converging to one recognition point is It is set based on the existing range and the minimum distance between adjacent recognition points,
At this time, there is no need to operate the flag for the area 54 that has already been processed. Also set the flag to “1”
When a flag is set to ``1'', it is always set to ``1'' regardless of whether the flag for that bit was previously ``0'' or ``1''. First, the number of first matching reference points provided on the image pattern is approximately
15,600, but if a 1-bit flag is provided for this many first reference points, the storage area required at that time will be approximately 2K bytes. Therefore, we decided to significantly reduce the capacity of the flag storage area as follows. FIG. 6 shows a flag storage area 63 for four lines in the flag storage area 61, starting from the line 62 where the first collation reference point currently being processed exists. In the flag storage area 61 corresponding to a large number of first matching reference points existing on the image pattern, only the flag storage area 63 for four lines is necessary for processing.
In the 0th row 62 where the first matching reference point currently being processed exists, the flag corresponding to the first matching reference point being processed is “0” or “1”. It is necessary to check whether there is a flag storage area 63 for four lines from line 0 to line 3.
is necessary to set the flag to "1" in the small area 52 shown in FIG. 5 when a recognition point is detected. Therefore, the area 63 that has already been processed and the area 6 that will be processed in the future
It is not necessary to provide flag storage areas corresponding to 4 at the same time. Therefore, as shown in Figure 7, the above 4
Block the flag storage area for each line,
The start address 72 of each block storage area 71 is held in a separate 4-word storage area 73, and instead of scrolling through the block storage area 71, the start address 72 of each block is held. By scrolling the contents of the storage area 73, the flag storage area is saved and the speed of flag processing is increased. FIG. 8 shows each block 81 of the flag storage area after the state of FIG. 7 has been scrolled once, the start address 82 of each block,
and a block start address storage area 83. In the block start address storage area 83, "adr0" which was at the top becomes the bottom,
The remaining addresses move up one by one. With this operation, the flag storage area starting from "adr1", which was the first line, becomes the 0th line flag storage area, and the flag storage area starting from "adr0", which was the 0th line, becomes the 3rd line flag storage area. becomes. This block that has newly become the third line flag storage area corresponds to the line that exists below the flag storage area 63 for four lines in FIG. Reset to “0”.

The feature of the present invention is that a flag storage area corresponding to the first reference point is provided and the matching process is performed based on the value of the flag. The purpose was to speed up processing by eliminating post-processing. Therefore,
The time required for the flag operation as described above must not exceed the time required for post-processing when one recognition point is detected multiple times. Therefore, in the present invention, a dedicated circuit is provided to calculate the address of the flag storage area in order to save processing time.
FIG. 9 shows a binary representation 91 of the decimal number "368". Assuming that the first matching reference point is set every 4 pixels and the flag storage area is configured in units of 16 bits, the bit in the flag storage area that corresponds to the x-coordinate value "368" on the image pattern is
Two digits “0101”92 and “1100”93 after removing the lower two bits when expressed in binary numbers
It can be specified by The flag storage area is set so that the first matching reference point currently being processed is always the 0th row, so in order to specify the bit in the flag storage area that corresponds to the first matching reference point, It is only necessary to specify the x-coordinate of the first matching reference point. In the example shown in Figure 9, for the x-coordinate value "368", the value "0101", or "5", and the value "0011", or "3", which is the inversion of "1100", are obtained, but as shown in Figure 10. As shown in , the former represents word position (hereinafter abbreviated as WP) 5102 in the 0th row flag storage area 101, and the latter represents
It represents bit position (hereinafter abbreviated as BP) 3103 in WP5. In addition, in order to extract the bit specified by WP and BP, one word of data specified by WP is shifted to the right by the number specified by BP, and the bit content of BP = 0 is determined. Therefore, it can be generalized.

As described above, by providing a flag storage area corresponding to the first matching reference point provided every few pixels on the image pattern, and performing the first matching process based on this flag, the recognition point is are detected sequentially without duplication, and not only eliminates post-processing to verify the coordinates of recognition points, but also interrupts pattern matching processing when a predetermined number of recognition points are detected. The processing speed can be increased.

Embodiment A pattern matching method according to an embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a block diagram of a pattern matching method according to an embodiment of the present invention. 1st
In the figure, a video signal obtained from an imaging means 1 such as a television camera is binarized by a binarization means 2 and stored in an image pattern storage means 3 as an image pattern. Prior to the pattern matching process, a characteristic part of the standard pattern is cut out from the image pattern storage means 3 at the time of teaching and is stored in the standard pattern storage means 4.
The central processing means 5 has the role of controlling each block in FIG. 1, including controlling the comparison reference points and determining pass/fail of the comparison results. The pattern matching process begins with determination of the flag at the first matching reference point determined by the central processing means 5. First, when the x-coordinate of the first reference point is sent to the flag control means 6, a flag corresponding to the first reference point is obtained from the storage means 7. This flag is determined by the central processing means 5. If the flag is "0", the first verification process is performed at the first verification reference point, and if the flag is "1", the first verification process is performed. Similar processing will be performed at the matching reference point next to the reference point. The matching process between the image pattern and the standard pattern is performed by reading out the pattern data from the central processing means 5 to the image pattern control means 8 and the standard pattern control means 9 so that the corresponding pattern data of the two patterns are read out from the respective storage means. A signal is sent. Corresponding data of the two patterns are inputted from the image pattern storage means 3 and the standard pattern storage means 4 to the matching processing means 10, where exclusive OR is performed for each corresponding bit of the two pattern data. When the corresponding pixel data match, the bit becomes "1", and this data is sent to the matching degree calculation means 11, where the number of bits that are "1" is calculated and the matching degree is determined. . The obtained degree of matching is compared in the central processing means 5 with the pass standard value corresponding to the first matching and the second matching, and if the first matching process is passed, the process is performed on the second matching process. Moving on to processing, the second
If the matching process passes, the coordinate values of the matching reference point that passed are retained as the coordinate values of the recognition point, and when all processing is completed, the coordinate values of the necessary recognition point are used as the main It will be sent to the controller 12.

FIG. 11 is a diagram illustrating in detail the flag control means 6 and flag storage means 7 of FIG. 1. The x-coordinate value of the first comparison reference point sent from the central processing means 5 is set in the register 111 for storing the coordinate value. When the first comparison reference point is provided every four pixels, excluding the lower two bits of the register 111, the bottom four bits "0" and "1" are inverted and stored in the register 112, and the four bits above it are inverted. Bit register 11
Store in 3. The data stored in the register 112 is "0" of the 4-bit data 93 shown in FIG.
The inverted version of “1” represents BP, and the data stored in register 113 is shown in Figure 9.
This is 4-bit data 92 representing WP. Therefore, data including flags to be read from the flag storage area 114 is obtained by inputting the value of WP stored in the register 113 and the contents of the register 115 storing the start address of the flag 0 storage area to the adder 116. Therefore, the added address is read out by storing the address in the address selection register 117, and is stored in the shift register 118.
The shift register 118 shifts the set flag data to the right by the number of BPs stored in the register 112. Then, the value stored in BP0 is a flag register 119 whose value is 1 bit.
and the central processing means registers this register 11.
It is determined whether the first verification is to be performed depending on whether the content of 9 is "0" or "1".

Regarding the pattern matching method configured as described above, how the first matching reference point near the detected recognition point is avoided will be explained below using FIGS. 12, 13, and 14. do. In FIG. 12, the first matching reference point 12 provided every n pixels
1, sequentially 1 in the scanning direction of the imaging device.
The verification process shall be performed. The first matching process is performed when the flag corresponding to the first matching reference point is "0", but the flag storage area is initialized to "0" until the first recognition point is detected. Therefore, the first verification process is performed one after another starting from the position A1. Next, if the recognition point 123 is detected from the first matching reference point 122, a small area 124 is set based on this first matching reference point 122, and the first matching reference included in this small area 124 is set as a reference point. The flag corresponding to the point is set to "1", and the flag storage area becomes as shown in FIG. Next, the first matching process moves to the matching reference point 125 next to the first matching reference point 122, but since the flag is set to "1" from the matching reference point 125 to the matching reference point 126, during this time The first matching process is not performed, and the first matching process is eventually restarted at the first matching reference point 127. When the first matching process moves to the row one row below, the flag storage area is deleted from the top row as shown in Figure 14, and the bottom row is a row in which all bits are initialized to "0". will be added. After the first matching process is performed at the first matching reference points 128 and 129, it is performed at the matching reference point 130 with the small area 124 in between.
The first comparison reference point 122 that led to the detection of 23
From other first reference points that exist around
This prevents the recognition point 123 from being detected again.

As described above, according to this embodiment, it is possible to detect a plurality of recognition points on an image pattern while accurately counting the number of points, and the process ends when the desired number of recognition points is obtained. As a result, pattern matching processing can be sped up.

Effect of the invention FIG. 15 is a diagram illustrating the effects of the present invention.

When the matching process is performed sequentially in the scanning direction of the imaging device on the first matching reference points 152 provided every n pixels on the image pattern 151, the matching process starts from the first matching reference point 153. The recognition point 154 for the first foot from the top is detected by A bit in a flag storage area corresponding to another first reference point existing near the reference reference point 153 is set to "1" (the area for processing the flag is not shown). and the first
Continuing the matching process, the recognition point 156 for the second leg from the top is detected by the matching process from the first matching reference point 155. Assuming that a condition is given in advance to perform the process until the recognition point 156 for the second leg from the top is detected, the pattern matching process
The process can be terminated when 6 is detected. In other words, when processing is performed while accurately counting the number of recognition points using the method of the present invention, the pattern matching process aimed at detecting a plurality of recognition points can be performed without obtaining the desired number of recognition points. It can be completed in stages, significantly reducing processing time.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing the configuration of a pattern matching method which is an embodiment of the present invention, and FIG.
FIG. 3 is a diagram showing the first matching reference points provided on the standard pattern image pattern, and FIG. 4 is the image pattern. FIG. 5 is a diagram showing a flag storage area corresponding to the first comparison reference point provided in FIG. is a diagram showing the minimum required area in the flag storage area, Figure 7 is a diagram showing the configuration of the flag storage area, Figure 8 is a diagram showing how the flag storage area is scrolled, and Figure 9 is a diagram showing the flag storage area. A diagram showing that two numerical values are extracted from the given coordinate values to determine the address of the storage area. Figure 10 shows how a specific bit in the flag storage area is extracted from the two numerical values shown in Figure 9. FIG. 11 is a diagram showing the configuration of the flag control means, and FIG. 12 is a diagram showing how the first comparison reference point in the area including the small area where the flag is set to "1" is selected. FIG. 13 is a diagram showing the contents of the flag storage area corresponding to FIG. 12. FIG. 14 is also a diagram showing the contents of the flag storage area corresponding to FIG. 12. FIG. 15 is a diagram showing the effect of the present invention. 3... Image pattern storage means, 4... Standard pattern storage means, 5... Central processing means, 6... Flag control means, 7... Flag storage means, 8... Image pattern control means, 9... Standard pattern Control means, 21, 22...first reference point, 23, 2
4...Second verification processing area, 25...Recognition point, 3
1...Standard pattern, 32...Standard pattern side matching reference point, 33...Image pattern, 34...First
Verification reference point, 41...Flag storage area, 52...
...area for setting the flag to "1", 63...flag storage area necessary for processing, 71...flag storage area,
72... Flag storage area start address, 73...
Start address storage area, 83...Scrolled start address storage area, 91...Image pattern x coordinate, 102...Flag storage area word position, 103...Flag storage area bit position, 104...Flag storage area start address ,1
05...Start address storage area, 111...Image pattern x coordinate, 112...Bit position storage register, 113...Word position storage register, 114...Flag storage area, 116...
Adder, 117... Flag storage area addressing register, 118... Shift register, 119...
...Flag register, 121...First matching reference point, 123...Recognition point, 124...Area where the flag is set to "1", 152...First matching reference point,
154,156...Recognition point.

Claims (1)

[Claims] 1 A video signal obtained from an imaging device is digitized and stored as an image pattern in a storage means, and a portion of the image pattern is compared with a standard pattern previously stored in the storage means, and a match obtained as a result of the comparison is obtained. In pattern matching processing that detects one or more pixels at a specific position of a standard pattern with a high degree of accuracy, that is, one or more recognition points from the image pattern, a matching reference is used as a matching point when matching the image pattern with the standard pattern. Points are set every few pixels in a region covering the entire image pattern, and these are used as first matching reference points, and pixels at specific positions of the standard pattern are matched with the first matching reference points, A first match between the standard pattern and the image pattern is performed sequentially, and a first match degree obtained each time the first match is compared with a predetermined first acceptance criterion value. When the degree of matching of 1 becomes greater than the first pass reference value, a small area is set based on the first matching reference point, and a second matching reference point is set for each pixel within the small area. A second matching is performed at the second matching reference point, and the value of the maximum matching degree among the plurality of second matching degrees obtained as a result is set as a predetermined second passing standard value. , and when the value of the second matching degree that became the maximum becomes larger than the second acceptance standard value, the second matching reference point that gave the second matching degree that became the maximum is determined. When using a hierarchical pattern matching method using recognition points, an initial value of 1 bit per point is set to ``0'' for the first matching reference point, which is set every several pixels over the entire image pattern. ”, and if the first verification at the first verification reference point is passed and a recognition point is detected in the second verification, the first verification point that led to the detection of the recognition point is The bits in the flag storage area corresponding to the matching reference point and a plurality of first matching reference points existing in the vicinity thereof are rewritten from "0" to "1", and in subsequent processing, the bits in the flag storage area are written as "1". A pattern matching method characterized in that the first matching is not performed at the first matching reference point corresponding to the bit that is 1''.