JP3151229B2 - Image matching method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates generally to image processing techniques for aligning two images, and more particularly to an apparatus and method for targeting a missile utilizing image processing.

[0002]

2. Description of the Related Art In certain military operations, it is important to launch missiles from aircraft at specific targets on the ground. Significant military benefits can be gained if the missile can guide itself to the target and the aircraft can move away from the danger zone near the target with the pilot. To achieve this capability, the missile must be able to obtain information to set targets and be able to identify specific targets during flight.

In one envisioned weapon system, both aircraft and missiles will be equipped with synthetic aperture radars (SARs). In general, SARs are well known. It will be sufficient here to state that the SAR mounted on the flying object produces an image of the target in the field of view on the ground located below. The video can be represented in any of a number of ways. In the case of an image that is further processed by a computer, the image will be represented by a series of digital words, each word describing the radar reflection intensity from a small area in the field of view. Also, an image intended to be displayed for a human would be similar to an image of a terrestrial part taken by a photo camera.

[0004] In addition, in the case of a prescribed weapon system, it is desirable that a person on the aircraft designates a specific target in the video. The video portion adjacent to the target becomes the reference image.
In that case, the image processor on the aircraft would send a reference image to the missile. After launch, the missile will fly toward the target and form its own SAR image. Processing on the missile will cause the reference image to be compared with the video from the missile. According to the missile guidance system, the missile may be steered in the designated target direction using the comparison result of the images.

However, it is necessary to overcome some problems in order for the assumed weapon system to function. 1
One important issue is that the viewing angle changes as the missile approaches the target. As a result, the SAR image formed by the missile in flight will differ from the SAR image formed by the aircraft as the missile moves away from the launch point. Therefore, the image processing needs to be relatively insensitive to changes in the viewing angle. Another problem to overcome is that the missile must be able to process the SAR image so that the missile guidance system can react quickly to the required course changes. Furthermore, because the entire missile is a consumable,
It is desirable that image processing on the missile requires relatively simple hardware.

[0006]

SUMMARY OF THE INVENTION It is an object of the present invention to provide a signal processing technique for matching two videos (images).

It is a further object of the present invention to provide a signal processing technique for matching two images when the viewing angles of the images are different.

Another object of the present invention is to provide a signal processing technique for matching two images using relatively quick and simple processing.

[0009] These and other objects are obtained by processing the first of two images to create a reference template. By comparing the reference template with each region of the second image, a region of the second image that matches the reference template is found. The reference template is formed by filtering the first image to reduce noise and increase contrast between different regions in the image. Thereafter, two maps are formed from the filtered video. The initial map includes an indication of the target edge position in the video and is formed by finding locations in the video where the brightness changes rapidly. The second map sets the intensity of each pixel in the filtered image to one of the image intensities with a very low number of levels, and then designates all neighboring pixels of different intensity as pixel edges. Formed by
The two maps are then compared with each other to form a new map containing only the edges formed in both maps. If those edges meet the additional criteria that suggest they are true edges, the additional processing will cause the edges to be mapped to a new map corresponding to edges that appear on only one of the edges. Will be added. The resulting map is then coded as a template and can be quickly compared to the second video.

In particular, the first map is formed by operating on a sub-array (part of the array) of pixels in the first image. Each sub-array is divided into two equal-sized groups of adjacent pixels. The sum of the intensities of the pixels in each group is calculated and the ratio between the two sums is calculated. Each sub-array is divided in four different ways, and the division method that produces the maximum ratio is selected. If the ratio is above a predetermined threshold, the pixel in the first map corresponding to the center of the sub-array is set to a value indicating the edge in the direction of the dividing line between the two groups of pixels.

The second map is formed by first calculating one threshold. The threshold is calculated by calculating a ratio corresponding to each pixel in the first image that reflects the luminance ratio of the compared pixel to the pixel having the closest maximum luminance difference. Thereafter, the average of the luminance of the pixels in the image having the higher luminance and the higher ratio is calculated, as is the average of the pixels having the lower luminance and the higher ratio. The average of the two averages forms a threshold, and one pixel in the first image having an intensity whose edges in the second map are on one side of the threshold is one pixel having an intensity on the other side of the threshold Is instructed in the vicinity.

The map is first stored in the true edge map.
And a second map including true edges by including pixels corresponding to the edges in both the first and second maps. Pixels corresponding to edges in the second map, but not the first map, are selected for further processing. The selected pixels are tested in much the same way as used to identify edges and their angles in forming the first map, but with different relaxed parameters. Another is that it increases the likelihood that one pixel will be identified as an edge. If the angles of the edge pixels identified by the relaxation parameters are similar to the angles of adjacent pixels already identified as edges in the new map, those pixels are also added to the new map.

[0013] The reference template comprises a sub-array of pixels and a correlation threshold. The sub-array includes two sets of pixels describing the pixels near the identified edge.
The first set corresponds to the pixels on the bright side of the edge and the second set
Correspond to the pixels on the low intensity side of the edge. The correlation threshold is calculated to reflect the ratio of the average luminance of the high luminance pixels set to the average luminance of the pixels in the low luminance set.

The sub-arrays that make up the template are matched to a portion of the second image by comparing the template to a sub-array formed from the second image. The comparison is made by first calculating two thresholds. The first threshold is calculated by averaging the pixels in the sub-array of the second image that correspond to the pixels in the template on the bright side of the edge weighted by the inverse of the correlation threshold, the second threshold being It is calculated by averaging the pixels in the sub-array of the second image that correspond to the pixels in the template on the low threshold side of the edge weighted by the correlation threshold. Then, the number of pixels in the sub-array in the second image corresponding to the pixels in the set of high-intensity templates above the second threshold and the number of pixels in the set of low-intensity templates below the first threshold. A correlation variable reflecting the number of pixels in the sub-array of the two images is calculated. By selecting the sub-array that gives the maximum value of the correlation variable, matching of the template to the sub-array of the second image is performed.

[0015]

FIG. 1 shows an airplane 14 equipped with a missile 16. Both the airplane 14 and the missile 16 are equipped with synthetic aperture radars (SARs) 18A and 18B, respectively. The target indicator 19 receives a video (image) formed by the SAR 18A. In this case, the target indicator 19
Consists of a digital computer having a screen for displaying images from the SAR 18A. The indicator 19 also includes certain input means (which allow the pilot of the aircraft 14 (not shown) to indicate the target in the image (in this case, the Trestle Bridge T across the river, unnumbered). (Not shown). The target indicator 19 selects an area in the image to be passed (transferred) to the processor 20 on the aircraft to be a reference image. The area in the reference image has a certain relationship with the target. In this case, the processor 20 on the aircraft is S
A template (not shown) for generating a template (not shown) from the AR output signal is constituted by software described in detail below. As shown, the SAR output signal is composed of signals defining river embankments (unnumbered), trestle bridges, and other objects in view such as buildings and trees (unnumbered). The position of the target with respect to the template and the reference image is passed via digital link 15 to the on-missile processor 40,
Stored in the missile-on-processor 40. In this case, digital link 15 may be any known bus for passing digital information from one computer to another.

When the missile 16 is launched onto the Trestle Bridge T, the digital link 15 is broken. Missile 16
SAR18 as he flies toward Trestle Bridge T
B further creates an image of the target area. Processor 40 on the missile compares the template formed by processor 20 on the aircraft and stored in missile processor 40 with each of the images produced by processor 40 on the missile from signals from SAR 18B. Missile processor 20 matches the template to the portion of the image produced by missile processor 40. Then a missile guidance system (not shown)
Operates to operate the missile 16. The missile is steered toward a point on the ground that has the same relationship to the reference image used to form the template for the portion of the image that matches the template. The result calculated by missile processor 40 is thus useful in guiding missile 16 to a designated target.

(Terms) Before explaining the processing performed on the SAR image, some introductory concepts and terms will be explained. The SAR image is divided into a two-dimensional pixel array, each represented by one digital word. In this case, the array is 36 × 36, but those skilled in the art will appreciate that the techniques described herein are applicable to arrays of various sizes and shapes. The value of each digital word corresponds to the image intensity of that pixel. Techniques for displaying images displayed in such a manner, as well as techniques for passing such images from one processor to another processor, are well known.

In the following, any image formed by the SAR or a processed variant of the same will be referred to simply as an image. However, when processing the same image, individual pixels may be considered. In that case, it is often more convenient to consider each image as a two-dimensional pixel array. Each pixel has X and Y locations in the array. 2 in parentheses
Array number followed by one number (for example, SRBE
(I, j)) means that the pixel in the named array has its x, y position in the array. In certain cases, a value or group of values is associated with each pixel in an image. An array of values is sometimes called a "map."

In some cases, certain images are processed in a number of different ways and the resulting images or maps are compared. Also, in some cases, the processed image may have a different number of pixels than the unprocessed image or each other's processed image. When comparing such images, it is important to correlate the exact pixels in each image. The center pixels of the image correspond and have the same x, y array coordinates. Pixels near the center pixel also correspond. Corresponding pixels can be identified by moving outward from the center of each image until they are identified for all pixels in the smaller image. For pixels remaining in the large image, there is no corresponding pixel. The comparison result for those pixels is ambiguous and will not be used in subsequent processing. Often, the pixels in a given image are selected for simultaneous consideration. Such a selection technique is called a “local window”. For example, if we consider a 3x3 pixel sub-array, the group of pixels is called a 3x3 local window. The local window is centered on the center pixel of the window. It is often necessary to process all such groups of pixels that can be formed from one image. In that case, the local window is considered to be "sliding" across the image to focus on one pixel and then move, focus on another pixel, and so on. However, if the local window is concentrated along the side of the array above one pixel, a sub-array of pixels cannot be formed near the pixel because there is no pixel on one side of the pixel. It should be noted that In general, if one local window slides along a certain image, the window will not be concentrated along the side of the array above the pixels because certain pixels at the bottom of the window will have indeterminate values . However, there are algorithms that prepare for that. In those algorithms, the local window can be centered on pixels along the sides of the array.

In some cases, the numbers representing the ratios are compared. When those numbers are compared in a "ratio sense", it means more than just choosing the largest of the numbers. Numbers are compared as if they were all integers. Further, a multiplicative inverse of less than one is considered. (That is, all ratios are converted to positive numbers greater than one and compared.) Pre-Processing Filtering Referring now to FIG. .
First, the operation of the on-board processor 20 will be considered.

A non-coherent integrator 22A, luminance level spreader 24, and smoothing filter 26 enhance features in the image prior to template formation. Those skilled in the art will also appreciate that various other feature enhancement techniques can be used. The non-coherent integrator 22A forms an average of a fixed number, eg, four, images created by the SAR using different radar frequencies. The average is calculated on a pixel-by-pixel basis. (That is, corresponding pixels in different images are averaged to create corresponding pixels in the output image.) The brightness level spreader 24 changes the brightness of each pixel in the image to reduce the brightness level distribution of the image by two. Focus around one brightness level. In this case, each pixel is represented by a discrete number of digital words representing one luminance level, for example 256 possible values. The input image has a certain arbitrary luminance distribution changed by the luminance level spreader 24. First,
The overall median luminance value of all pixels in the 36 × 36 image is determined. Next, the output image of the brightness level spreader 24 is formed by processing every possible 9 pixel group selected by sliding a 3x3 local window across the input image. The pixel value in the output image corresponding to the pixel at the center of the 3 × 3 local window is calculated from the 9 pixels below the local window. For each location of the local window, i.e., for each of the two groups of pixels, the local (local) median of the pixels in the window is calculated. If the local median is less than the global median, the output pixel is set equal to the local minimum. That is, a value equal to the lowest luminance of all the pixels in the window is given. Conversely, if the local median is not less than the global median, the output pixel is set to local maximum. Local window is 3
The image formed by sliding the local window over the entire input image produces a 34x34 output array because it cannot be centered on any pixel on the outer edge of the 6x36 array.

The smoothing filter 26 uses a 34.times.34 output array of luminance level spreaders 24 as its input array. First, the global median of the input array is calculated by finding the median of all pixel values in the input array. A 3x3 window is slid over the input image,
Pixels in the output image corresponding to the pixel at the center of the window are calculated at each window position. If the center cell of the local window is greater than or equal to the global median, the pixels in the output image are set equal to the median of all pixels in the local window that are greater than or equal to the global median. Conversely, if the center cell in the local window is less than the global median, the local window in the output image is set equal to the median of all pixels in the local window that is less than or equal to the global median. The resulting filtered image is described as a 32 × 32 pixel array, and will be described below as an EPS image.

In an alternative to the brightness level spreader 24 and the smoothing filter 26, the filtered image could have the same number of pixels as the reference image. For example, pixels near the edges of the reference image that are not processed because the local window cannot be centered on top of them could simply be copied as is into the filtered image.

The filtered image is then processed by local edge detector 28 and global edge detector 30. Each produces one edge map. The edge map is represented as an array of digital words, similar to a filtered image. The value of each word is provided by local edge detector 28 or global edge detector 30 to indicate whether the corresponding pixel in the filtered image indicates an edge between two objects in the image. Local edge detector 28 and global edge detector 30 use different processes to identify edges in the input image. The edge extractor 32 opens the information from the filtered image and combines both edge maps with the identified edge map. The identified edge map contains edges that appear to represent true edges. The reference template generator 34 uses the validated edge map to create a template that passes to the on-missile processor 40 where the template is compared by the edge template correlator 42 with the image formed by the SAR 18B to determine the target. Hereinafter, the operation of each of these elements will be described in detail.

(Global Edge Detector) FIG. 3 shows a flowchart of a process executed in the global edge detector 30 to create a global edge map. The above map is also called an SRBE map. Rectangular elements (typically element 50) referred to herein as "processing blocks" represent computer software instructions or instructions. Diamond-shaped elements (typically element 54), referred to herein as "decision blocks," indicate computer software instructions or instructions that affect the execution of the computer software instructions represented by the processing blocks. The above flowchart does not illustrate the syntax of any particular computer programming language. Rather, the above flowchart illustrates the functional information required by those skilled in the art to generate computer software to perform the processing required for global edge detector 30. Note that many routine program elements, such as initializing loops and using general variables, are not shown.

As shown in FIG. 2, the global edge detector 30 processes the filtered image created by the smoothing filter 26. At the start of the process shown in FIG. 3, the image is represented by a 32 × 32 digital word, ie, an array of pixels. The global edge detector 30 converts a pixel in the image into one of two values depending on whether the pixel luminance is above or below a threshold (hereinafter referred to as binarization). Edges are indicated at any point in the image where one value pixel is close to the other value pixel. As can be seen from FIGS. 3 and 4, an important feature of the global edge detector 30 is the selection of an appropriate threshold in binarizing the image.

Referring now to FIG. 3, processing block 50 changes any pixel having a value of 0 to have a value of 0.1. Thus, when using that pixel value to calculate the ratio, undefined values that may result from dividing by zero are avoided.

Processing blocks 52 and 56 and decision block 54 form a loop in which a ratio corresponding to a pixel in the image is calculated. The 3 × 3 local window slides across the input image, and a processing block 52 calculates the ratio of the center pixel to luminance. This ratio is equal to the ratio of the luminance of the center pixel to the third highest luminance or the third lowest luminance of the other pixels, depending on which is higher. Decision block 54 checks if the 3x3 pixels in the image have been used as much as possible to calculate the ratio. If all possible pixel groups have not been used, processing block 56 selects the next group and processing block 52 and decision block 54 are repeated. If decision block 54 determines that all groups of pixels have been used, then the ratio is associated with each pixel except those on the image edges.

Processing block 58 sorts (classifies) pixels in the image by luminance. Those skilled in the art will appreciate that processing block 58 can be implemented using any known sorting technique, such as bubble sort or shell sort. The output of processing block 58 does not depend on the location of the pixels in the image, but the original is retained for further processing. However, the ratio calculated in processing block 52 is still related to the sort pixel calculated in processing block 58.

Processing block 60 selects a pixel having a luminance value between the 35th and 90th percentile. The pixels are used to calculate the upper average, i.e., the average of the pixels that are likely to be above the optimal threshold, as described below. Processing block 62 rearranges the selected pixels into two groups. That is, a first group of pixels having a higher luminance than the other pixels selected to form the ratio when used to construct the ratio when used in processing block 52, and forming a ratio in processing block 52. And a second group of pixels having a lower brightness than the other pixels selected to form that ratio when used. Within each group of pixels, the pixels are further rearranged so that pixels with a higher ratio precede those with a lower ratio. Processing block 63 selects the top 2% of the pixels aligned by processing block 62 for further processing.

Processing block 64 further excludes pixels having ratios in the range of 0.5 to 2.0. Decision block 66 checks that the deletion in processing block 64 leaves a sufficient number of pixels for further processing. If less than 1% of the pixels selected in the processing block 63, that is, one-half remain, the processing by the global edge detector 30 (FIG. 2) ends. This termination corresponds to the occurrence of an exceptional condition. Empirically, it is unlikely that a good edge or boundary can be found in the input image if an exceptional condition occurs. Once an exception condition occurs, the target designator 1
9 will select a different reference image, which will be processed starting from the non-coherent integrator 22A (FIG. 2).

If processing does not end after decision block 66, processing block 70 edits the pixel selected in processing block 63. FIG. 4 shows details of the processing block 70. The process shown in FIG. 4 has the advantageous effect of removing pixels corresponding to singularities rather than true edges from consideration when selecting a threshold.

Processing block 100 calculates the average and standard deviation of the ratios of the selected pixel values using known methods. The reciprocal of the pixel less than one is used for the calculation.

The decision block 102 determines whether the ratio of the standard deviation to the average is less than 0.1. If the ratio is less than 0.1, the processing in processing block 70 ends. If not, processing continues to decision block 104 where it is determined whether the ratio of the standard deviation to the average is less than or equal to a fixed threshold T ₂ , in this case 0.5. . If so, processing block 106 calculates a second threshold level according to the following equation:

THR = M + KD (1−D / M) where M is an average value, D is a standard deviation, K is a constant, in this case, 2. If not, the THR is calculated at processing block 108 according to the following equation:

THR = M + K (D / 2) Thereafter, decision block 110 checks if any of the input ratios exceed a threshold calculated in either processing block 106 or 108. If the ratios are above the threshold, processing block 116 removes those ratios from further processing and adds additional ratios instead. Recall that processing block 63 (FIG. 3) selected only the top 2% of the list of ratios sorted by value. Processing block 116 replaces the removed ratio with the next ratio in the list if the ratio in the list exceeds the minimum value of 2.0.

Decision block 118 determines whether the process shown in FIG. 4 should be repeated again. If the above processing has been performed less than the maximum number of times (3 in this case) and more than half (FIG. 3) of the ratio selected in processing block 63 remains, FIG. The processing in the processing block 100 uses the compiled list of ratios.
Is repeated. Otherwise, the process ends. The process could end after decision block 110 if no ratio exceeds the threshold THR. The decision block is at least 1% of the pixel, ie, processing block 63.
Check that half of the initially selected pixel remains. If a sufficient number of pixels remain, processing at processing block 70 ends. Otherwise, processing block 114 uses the previously removed ratios in the reverse order that they were removed until the list contains a number of pixels equal to half the number of pixels selected in the processing block. Return to the list (FIG. 3). The need for processing block 114 arises in processing block 1
16 would not add pixels to a list that does not have a ratio of at least 2.0. Thus, in some cases, when reaching decision block 118, less than 1% of the pixels could remain.

Returning to FIG. 3, it can be seen that the edited list of ratios is used by processing block 72. The luminance levels corresponding to the pixels in the edit list are averaged to produce an average value. The process of calculating one average is repeated twice, once with the upper group of pixels selected in processing block 60 and once with the lower group of pixels selected in processing block 76. Decision block 74 determines whether the process has been repeated for the lower group of pixels. If not, processing block 76 selects a pixel having a 10th-65th percentile luminance level. The selection is made in processing block 58
Is simplified by the fact that has already sorted the pixels by luminance. The ratio corresponding to the selected pixel is then reciprocal in processing block 78 and processed just like the upper group of pixels. For the lower group of pixels, processing block 62 precedes those pixels whose pixels used to form the ratio in processing block 52 have a greater value than the other pixels selected to form that ratio. It should be noted that the pixels are aligned in two groups, as described above, except that they have a lower intensity than the other pixels selected to form the ratio.

However, after processing the lower group of pixels, decision block 74 recognizes that the lower group has been processed and processing is continuing at processing block 80.

Processing block 80 calculates the average of the two averages calculated in processing block 72, one for the upper group of pixels and one for the lower group of pixels. This “average of the average value” is used as a threshold for dividing the image in the processing block 82. Pixels in the global edge map that correspond to values in the input image above the threshold are set to "4" and pixels below the threshold are set to "1". Hereinafter, the global edge map at the output of the global edge detector 30 may be referred to as a segmented image or binary image, or may be referred to as SRBE. A specific pixel in the divided image is represented as SRBE (i, j).

In an alternative processing method, the process of determining the thresholds could be repeated more than once to create three thresholds and then the image divided in processing block 82. Second
Is determined by essentially repeating the processing shown in FIGS. 3 and 4 for pixels that exceed the "average average" threshold calculated in processing block 80. The third threshold is essentially determined by repeating the process shown in FIGS. 3 and 4 for pixels that are below the "average average" threshold calculated in processing block 80. Thereafter, the division of the image in processing block 82 would be performed by assigning each pixel in the input image a number in the range of 1-4. If the pixel brightness is below all three thresholds, a value of 1 will be assigned. A value of 2 if less than two of the above three, a value of 3 if only one of the three is less, and a value of 4 if more than all three more. Will be given. If adjacent pixels have different values, an edge will be identified. Alternatively, an edge could be identified only if the values assigned to adjacent pixels differ by two or more.

(Local Edge Detector) Returning briefly to FIG. 2, it can be seen that the local edge detector 28 is processing the same input image as the global edge detector 30. The output of local edge detector 28 is used by edge extractor 32, just like the output of global edge detector 30. Therefore, the processing represented by local edge detector 28 could be processed simultaneously with the processing of global edge detector 30. If both processes are performed using one general purpose digital computer, the processes will be performed one after the other.

In the case of local edge detector 28, a 7 × 7 local window slides over a 32 × 32 pixel input array. An output edge map having 26 × 26 pixels is formed by assigning one value to the pixel in the edge map corresponding to the pixel at the center of the 7 × 7 local window. The pixel value in the edge map indicates whether the pixel corresponds to an edge in the input image and the orientation of that edge.

The processing required to identify an edge and its orientation can be better understood by referring to FIGS. 5A, 5B, 5C and 5D. Each of these figures shows a 7 × 7 pixel window with some pixels marked “+” and others marked “−”. The window specified in this way is called a “mask”. As the window slides along the input array, two sums are calculated at each window position. That is, one of all pixels corresponding to “+” in the mask and one of all pixels corresponding to “−” in the mask are added. The ratio of these two sums is calculated. The masks in FIGS. 5A, 5B, 5C, and 5D are applied sequentially at each window location, producing four ratios. The largest ratio is selected. If the selected ratio is greater than a certain threshold, in this case 2, the pixel in the local edge map is set to +1 to indicate one edge. The orientation of the edge angle is determined from the mask corresponding to the maximum ratio and from whether the inverse ratio has been selected. The masks in FIGS. 5A, 5B, 5C, and 5D have angles of 0 °, −45 °, −90 °, and −1, respectively.
Related to 35 °. If the selected ratio is greater than the threshold in absolute value, the angle of the mask is the angle associated with the pixel in the output edge map. If the ratio selected is absolute and less than the threshold, the negative angle of the mask is the angle associated with the pixel in the output edge map. Finally, the local edge detector 28 removes pixels from the local edge map that indicate an edge but are not adjacent to another pixel indicating an edge at an angle in the range of 45 degrees of the first pixel. Hereinafter, the local edge detector 2
The output of 8 will also be referred to as the AED, and the particular pixel in the image will be referred to as AED (i, j).

(Edge Extractor) Referring again to FIG. 2, the edge map generated by the local edge detector 28, the divided image generated by the global edge detector 30, and the filtering generated by the smoothing filter 26 The image is found to be an input to the edge extractor 32. Edge extractor 32 combines information from all three sources to create a verified edge map that includes edges that are easily recognized in images processed by processor 40 on the missile. Edge extractor 3
2A to 7F,
And FIG.

The edge extractor 32 (FIG. 2) first extracts the edge / edge from the AED map generated by the local edge detector 28 and the SRBE image generated by the global edge detector 30.
Form a cross correlation map of the boundaries. Each pixel in the edge / boundary cross correlation map is called EBCC (i, j). They are calculated by the following formula:

EBCC (i, j) = IS (i, j) AND [AED (i, j) OR AED (i + 1, j) OR AED (i, j + 1) OR AED (i−1, j) OR AED ( i, j−1)] where IS (i, j) = [(SRBE (i, j) ≠ SRBE (i + 1, j) OR (SRBE (i, j) ≠ SRBE (i, j + 1) OR (SRBE ( i, j) ≠ SRBE (i-1, j) OR (SRBE (i, j) ≠ SRBE (i, j-1))] Equation (1) IS (i, j) is the output of the global edge detector 30 If the pixel SRBE (i, j) in the image is different from any of the neighboring pixels in the image, it is a logical 1 (ie, a Boolean true) .The term in square brackets in equation (1) is SRBE (i, j).
j) any of the pixels in the AED map corresponding to, or any of its neighboring pixels, is a logical 1 (ie,
Edge), it is always logic 1. Thus,
In the EBCC image, the local edge detector 28 and the global edge detector 30 both have one edge and a 0 in all other pixels.
Pixels that identify (i.e., false in Boolean) contain all ones.

Next, the edge extractor 32 forms a difference map called "D". In that case, any individual pixel in the map is denoted D (i, j). Each pixel in the difference map is calculated according to the following equation:

[0049]

(Equation 1)

Where IS (i, j) has the same meaning as in equation (1). Each pixel in the D-map with a value of 1 indicates that the global edge detector 30 reported one edge at that pixel but the local edge detector 28 did not.

Also, the edge extractor 32 forms an alternative ratio map RD. The alternative ratio map indicates where the local edge detector 28 would have reported an edge if a less stringent edge detection method was used. 6A and 6B illustrate the processing performed to create an RD map. This process is executed once for each pixel set to 1 in the D map. Processing block 130 is E
Select a 3 × 3 local window from the PS map.
The local window is composed of pixels concentrated near the pixel corresponding to the pixel set to 1 in the D map. Then, the local window is shown in FIG.
Processed by several pairs of masks shown in 7D, 7E, 7F. Processing block 132 applies the first mask in each pair to the selected local window. Each number in the mask is multiplied by the value of the corresponding pixel of the EPS image in the selected local window. The sum of the products is the value corresponding to the mask. Processing block 134 similarly applies the second mask in the pair. Thereafter, processing block 136 includes processing blocks 132 and 134
Calculate the difference and ratio of the values calculated in. If FIG. 7C, 7
If each of the four pairs of masks shown in D, 7E, and 7F is not assigned to the local window, processing block 14
0 selects the next pair and the value for that pair is calculated.

Processing block 142 is processing block 136
Sort the absolute value of the difference calculated in. Decision block 144 checks if the maximum difference found in processing block 142 exceeds a threshold THR, in this case 2.0. If more than one pair of masks produces a difference equal to the maximum difference in the processing block, the ratio corresponding to all of the pairs having the difference is checked by decision block 144 to determine if any of those ratios exceeds a threshold. It is determined whether or not. If the threshold is not exceeded, the pixel in the RD map corresponding to the pixel in the D map set to 1 is set to 0 in processing block 160.
If the threshold THR is exceeded, then decision block 146 leaves the execution to decision block 147 if one or more pairs of masks produces a difference equal to the maximum difference, and a pair of masks produces a difference equal to the maximum difference. If so, it is left to processing block 152. Decision block 147 checks all the ratios corresponding to mask pairs that produce a difference equal to the maximum difference. If only one of the ratios corresponding to the maximum difference is equal to the threshold T
If HR is exceeded, processing continues at processing block 152. Otherwise, processing continues at decision block 148. Decision block 148 checks whether any two of the maximums were generated by a pair of orthogonal masks. The pair of masks 170A and 170B (FIG. 7C) is orthogonal to the pair of masks 174A and 174B. (FIG. 7E) A pair of masks 172A and 172B (FIG.
D) is orthogonal to the pair of masks 176A and 176B (FIG. 7F). If the difference includes the difference generated by a set of orthogonal masks, the pixel in the RD image is set to zero in processing block 160. Otherwise, processing block 150 selects one of the maximums by selecting the pair having the maximum ratio as calculated in processing block 136.

Thereafter, processing continues at processing block 152. If decision block 146 identifies only one maximum difference, or decision block 147 identifies only one maximum value having a ratio greater than threshold THR, processing continues at processing block 152 in a similar manner. Processing the mask pair in block 152 the edge angle A ₁ has the maximum difference calculated at process block 136, or if the processing block is executed that is selected based on the mask pair selected at process block 150. In that case, processing block 132 or processing block 1
The mask that produces the maximum at 34 is identified and the angle associated with that mask is selected. 45 °, 90 °, 135
The angles of °, 180 °, 225 °, 270 °, 315 °, and 360 ° correspond to the mask 170A (FIG. 7C), respectively.
172A (FIG. 7D), 174A (FIG. 7E), 176A
(FIG. 7F), 170B (FIG. 7C), 172B (FIG.
D) 174B (FIG. 7E) and 176B (FIG. 7F).

Processing block 154 calculates a _second angle A ₂ equal to the arc tangent of the ratio of the difference calculated in processing block 136 for the mask in FIG. 7D to the difference calculated for the mask in FIG. 7F. Arctangent by taking into account the sign of their difference (ARCTAN) A ₂ 0
It is possible to take an arbitrary value in the range of ° to 360 °. The difference calculated for the mask pair in FIG. 7D reflects the edge strength in the 90 ° direction, and the difference calculated for the mask pair in FIG. 7F reflects the edge strength in the 360 ° (or 0 °) direction. I do. Thus, the arc tangent of their difference reflects the angle of the edge.

The decision block 156 is a processing block 15
The absolute value of the difference between the angles A ₁ and A ₂ calculated in 2,154 is 4
Check if it is greater than 5 °. Recall that A ₁ and A ₂ reflect the angle of the edge at the selected pixel calculated in two different ways. If the difference is greater than 45 °, the pixel in the RD map is set to zero in processing block 160. (I.e., the selected pixel is not indicated as a possible edge in the RD map). Otherwise, the pixel is set to one in processing block 158. The completed RD map is formed by repeating the above process (shown in FIGS. 6A and 6B) for each pixel equal to 1 in the D image.

FIGS. 8A and 8B show details of how the output of the edge extractor 32 (FIG. 2) is formed from the EBCC, D, SRBE and RD maps. The output of the edge extractor 32 (FIG. 2) is EEB
It is composed of a pixel array indicated by (i, j). Each pixel has a value of either 1 indicating one edge or 0 indicating no edge. 8A and 8B
The processing shown in (1) sets each pixel in the EEB map corresponding to 1 in the EBCC map to 1. Other pixels in the EEB map that correspond to pixels in the D map that are considered to represent edges are also set to one.

At processing block 180, the EBCC map is copied to an array variable represented by "TEMP". The TEMP array is processed one pixel at a time. In doing so, the current pixel to be processed is selected by processing block 182. Decision block 184 checks if the pixel in the D map corresponding to the selected pixel is zero. If the pixel is equal to zero, processing block 190 ignores the selected pixel and the next pixel is considered.

On the other hand, if the pixel is not zero, it will represent an edge. Decision block 186
Checks the selected pixel in the TEMP array and its nearest pixel. The four closest pixels are the pixels above, below, and on both sides of the selected pixel in the two-dimensional array. If all those pixels are zero, the selected pixel is processed block 190
Are no longer considered as edges and the next pixel is selected. If any one of the four closest pixels is non-zero (ie, an edge), then processing block 1
88 holds the selected pixel as a potential edge for further processing.

If more pixels remain to be processed as determined at decision block 192, processing block 182 selects the next pixel to be similarly processed. If all pixels in the image have been processed, decision block 194 determines whether the selection process should be repeated. The process will be repeated if the following two conditions are met: That is,
(1) The entire array has been processed less than 50 times. (2) The pixels held in the current iteration are different from the pixels held in the last iteration. If another iteration is to be performed as determined at decision block 194, processing block 196 sets the pixel in the TEMP array corresponding to the holding pixel equal to one to one and the other Set all pixels to zero.

Thus, the TEMP array starts with all pixels for which one edge has been identified as a possible edge by both the local edge detector 28 and the global edge detector 30. An additional pixel that may represent an edge as indicated by a 1 in the D-map is added to the TEMP array at each iteration if it is adjacent to a pixel already identified as a possible edge.
Once a sufficient number of iterations have been performed, as determined at decision block 194, the retained pixels, ie, T
One in the EMP array will represent a pixel that may be an edge.

All pixels held in the TEMP array are considered to determine which pixels actually represent edges and should appear in the EEB map at the output of edge extractor 32. (FIG. 2) Processing block 198 selects and processes one pixel at a time. If decision block 2
If that pixel in the EBCC map is equal to 1 as determined at 00, processing block 202 sets the corresponding pixel in the EBB map to 1 and the next pixel is processed. If the selected pixel in the EBCC map is 0
If so, decision block 204 checks whether the corresponding pixel in the TEMP array is 0, ie, has not been considered as a pixel representing an edge. If a pixel in the TEMP array is 0, that pixel is ignored and the next pixel is considered.

Conversely, if the pixel in the TEMP array is 1, the corresponding pixel in the alternate ratio map RD is considered. If the pixel in the RD map is 0, as determined at decision block 206, the next pixel will be considered. If the pixel in the RD map is not zero, processing block 208 determines if the corresponding array in output array EEB is 1 using the following equation:
To determine if it should be set.

EEB (pixel) = TEMP (adjacent) AND [SRBE (adjacent) = SRBE (pixel)] AND [RD (adjacent) OR EBCC (adjacent)] Expression (3) where “pixel” is selected. The pixel corresponding to the pixel and “neighbor” refer to the pixel next to the pixel corresponding to the selected pixel. Note that each pixel has a total of eight adjacent pixels on each of the four sides and on each of the four diagonals. Thus, the right side of equation (3) needs to be determined once for each adjacent pixel, up to a total of eight times, and if the right side evaluates to logic 1 for any of the eight adjacent pixels, EEB (pixel)
Will be a logical one. If there are more pixels remaining as determined by decision block 210, processing block 198 will select the next pixel and the process will be repeated.

At the end of the process shown in FIG. 8B, the EEB image is converted to the local image detector 28 (FIG. 2) and the global edge detector 30.
If both (FIG. 2) report one edge, all pixels will contain one. In addition, the results of the processing shown in FIG. 6A are used in decision block 206 and processing block 208 to identify and set one to other pixels that may represent extensions of the verification edge. Thus, E
The EB image represents edges in the reference image representing image features likely to match subsequent images possibly taken from different angles of the target area. One of them in the EEB image represents the confirmation image.

(Reference Template Generator) The reference template generator 34 (FIG. 2) creates a template from the description of the edge in the EEB map. The template is a two-dimensional array of the same size as the EEB map. The reference template generator 34 is EE
Based on the edge information included in the B map and the division information in the SRBE map, any one of +1, -1 and 0 is assigned to each element in the template. The reference template generator 34 (FIG. 2) determines the pixels in the three (or other relatively small number) pixels of the identifying edge that are likely to correspond to high intensity pixels when aligned on the SAR image of the template array or target area. 1 for the pixels and -1 for the pixels in the three pixels of the validation edge that are likely to correspond to the low intensity array when the template array is aligned on the SAR image. Pixels not within the three pixels of the validation edge are assigned a value of zero. The reference template generator 34 (FIG. 2) calculates a correlation threshold K. The equivalency is used by the edge template correlator 42 (FIG. 2) in matching the template to the SAR image captured by the SAR 18B (FIG. 1) as the missile 16 (FIG. 1) flies in its target direction. 9A and 9B show details of the processing performed by reference template generator 34 (FIG. 2) to calculate the template and correlation threshold. All pixels in the EEB image are processed sequentially when selected by processing block 240. If the pixel is at decision block 242
If it does not correspond to an edge when judged in,
The next pixel is processed. If the pixel is an edge, i.e., if the pixel in the EEB map is not zero, multiple pixels will be set in the corresponding template.

Decision block 246 checks whether the selected pixel is on the light or dark side of the edge. The level of the corresponding pixel in the SRBE map is compared with the value of a neighboring pixel in the SRBE map having a different value to determine which side of the edge the pixel is on. If the value of the corresponding pixel is greater than the value of the neighboring pixel, then that pixel is on the lighter side of the edge. If the pixel is on the lighter side of the edge, the variable BRTT is incremented by processing block 248 to +1.
Is set to Otherwise, BRTT is set to -1 at processing block 250.

Processing block 252 is processing block 240
Select the pixel in the 5x5 local window in the SRBE map that is centered on the pixel selected in. In processing the pixels at the bottom of the local window, the four outermost pixels are eliminated. When the local window is centered at the top of the pixel near the sides of the SRBE image, a portion of the local window may "overhang" over the image edges. In such a case, only the pixels in the image at the bottom of the window are considered.

Processing block 254 includes processing block 240
Identifies all pixels in the local window that have the same value as the pixel in the SRBE map corresponding to the pixel selected in (i.e., pixels on the same side of the edge).
The corresponding pixel in the template is set to that value whatever the BRTT is given in processing block 248 or 250. The remaining pixels in the EEB map are then processed until all of the decision blocks 256 have been processed and the template is completed.

FIG. 9B shows the processing required to calculate the correlation threshold value K. Each pixel in the template is processed sequentially as processed by processing block 258. If the pixel is zero as determined by decision block 260, the pixel is processed. If the pixel is greater than zero as determined by decision block 262, the value of the corresponding pixel in the EPS image is added to variable THRP in processing block 264,
At processing block 266, the counter variable NTHRP is incremented. Conversely, if pixel is 0
If so, the value of the pixel in the corresponding EPS image is added to the variable THRM at processing block 268 and the counter variable NTHRM is incremented at processing block 270. The process is repeated for all pixels in the image as determined by decision block 272. Processing block 274 calculates the value of variable CR according to the following equation:

CR = (THRP / NTHRP) / (THRM / NTHRM) Note that CR must be greater than one. A CR value less than 1 indicates that the reference image selected by the target indicator 19 (FIG. 1) does not contain edges that form a good template. If CR is less than one, target indicator 19 (FIG. 1) may select a different reference image. Finally, a correlation threshold K is calculated in processing block 276 according to the following equation:

K = CR (ln CR) / (CR-1) Equation (5) where ln is a natural logarithmic function. In an alternative embodiment of the present invention, the entire process shown in FIG. 9B can be omitted by setting K equal to 1.4.

(Missile Onboard Processor) Thereafter, the template and the correlation threshold are passed to the missile onboard processor 40 (FIG. 1). The missile-mounted processor 40 (FIG. 1) uses the template SAR18B (FIG. 1).
Matches the image created by Note that the processing required to create the template is performed once in the processor 20 (FIG. 1) onboard the aircraft. As shown in FIG. 2, a small amount of processing is required to identify a target from an image created by the SAR 18B (FIG. 1).

It should be noted that the template was formed from a reference image composed of image portions created by SAR 18A (FIG. 1). The image portion is selected to include enough edges to provide a relatively high CR value as calculated by equation (4). For example, the reference image is a 32 × 3 selected from a larger 64 × 64 pixel array.
Could be a two pixel array. In that case, S
The target area image formed by AR18B (FIG. 1) will be a 64 × 64 pixel array as well. In a manner to be described in detail below, the missile-mounted processor 40 (FIG. 2) will match the template with the 32 × 32 pixel portion of the target area image created by the SAR 18B (FIG. 1). The position of the matching portion in the target area image indicates the direction of the target relative to the direction of movement of the missile 16 (FIG. 1). For example, if the specified target position of the matching part is immediately to the right of the center of the target area image,
The missile-mounted processor 40 (FIG. 1) identifies that the target is to the right of the missile's 16 travel line and sends a signal to a missile guidance system (not shown) to guide the missile 16 to the right. It will be. The missile-mounted processor 40 (FIG. 1) can provide additional information to the missile guidance system as to how far the travel line should be adjusted.

Details of the processing performed by the edge template correlator (FIG. 2) to match the template to the target area image formed by the SAR 18B (FIG. 1) are shown in FIGS. 10A and 10B. Before elaborating on FIGS. 10A and 10B, the target area image formed by SAR 18B (FIG. 1) is filtered before being processed by edge template correlator 42 (FIG. 2), for example, non-coherent integrator 22B (FIG. 2). It should be noted that noise such as due to) can be removed. The non-coherent integrator 22B (FIG. 2) performs the same operation as the previously described non-coherent integrator 22A (FIG. 2).

Referring now to FIGS. 10A and 10B,
Processing in the edge template correlator 42 (FIG. 2) begins at processing block 300. The same block is SAR
Select a local window in the target area image generated by 18B (FIG. 1). The local window is the same size as the template created by the reference template generator 34 (FIG. 2). The local window slides over the image generated by SAR 18B, and processing block 300 selects one local window that was not previously considered. Processing block 3
02 selects a pixel in the template. All pixels in the template are considered and processing block 302
Selects pixels that were not previously considered. If the selected pixel was zero when determined by decision block 304, the next pixel in the template is considered. If the pixel is not zero, decision block 306 determines whether the pixel is greater than or less than zero. If the pixel is greater than zero, the value of the corresponding pixel in the detected image is added to the variable SUMP at processing block 308. The counter NPOS is similarly incremented by one. Conversely, if the pixel is less than zero, processing block 310 adds the value of the corresponding pixel in the detected image to variable SUMN and increments counter NNEG by one. Each pixel is processed sequentially, and eventually all pixels are processed as determined by decision block 312. Once all pixels in one local window have been processed, processing block 314 sets a positive threshold THRP according to the following formula:
Is calculated.

THRP = (1 / K) (SUMP / NPOS) where K is the reference template generator 34 (FIG. 2)
Is the correlation threshold generated by
Is a variable set in processing block 308. Processing block 316 includes a negative threshold THRN according to the following formula:
Is calculated.

THRM = K (SUMN / NNEG) where SUMN and NNEG are variables set in the processing block 310. Processing block 318 creates a binary array of the same dimensions as the template. All pixels in the binary array that correspond to pixels equal to zero in the template are equal to zero. For each pixel in the template having a value greater than zero, the corresponding pixel in the local window selected in processing block 300 is compared to a threshold THRM. For each pixel in the template having a value less than zero, the corresponding pixel in the local window is compared to a threshold THRP. For any threshold, if a pixel in the local window is above the threshold, the corresponding pixel in the binary array will be equal to +1. Otherwise, the pixels in the binary array will be equal to -1.

[0078] Processing block 320 compares the pixels in the binary image with the template to determine values for the following variables.

The number of pixels in the template having a value less than or equal to R ₁ = 0 The number of pixels in the template having a value greater than or equal to R ₂ = 0 The number of pixels in a binary array having a value less than or equal to S ₁ = 0 S ₂ = The number of pixels in the binary array having a value greater than or equal to zero The number of pixels in the template having a value less than or equal to H ₁₁ = 0 and correspondingly less than or equal to zero in the binary array having a value less than or equal to H ₁₂ = 0 The number of pixels that have a value and the corresponding pixel value in the binary array is greater than or equal to 0 and the value of the pixel in the binary array that is greater than or equal to H ₂₁ = 0 and greater than or equal to 0; numerical number of pixels in a certain kind of template _{R 1, R 2, S 1} , S 2, H 11, H 12, H 21 and H ₂₂
Is used in processing block 322 to calculate the correlation map CM according to the following equation:

[0080] ^{_{CM = (H 11 KR1 H 22}} KR2) / (AH 21 KR2 + H 22 KR2) (AH 12 KR1 + H 11 KR1)) Equation (6) _{where, K = 2CC / (R 1} + R 2) A and CC Is a constant empirically selected to change the correlation map enhancement.

CC is usually in the range of 0 to 4, and A is usually in the range of 1 to 7. Note that processing block 320 enters a loop in the flow chart such that a CM value is calculated for each local window selected from the target area image. Processing block 324 checks each value of the CM and stores the maximum value. At the same time, processing block 324 stores the position in the target area image where the local window selected in processing block 300 generated the maximum CM value. The entire process is repeated by decision block 326 for every possible local window in the detected image.

Upon completion of the process of FIG. 10, the maximum CM value is identified by processing block 324. The maximum CM value means that the template best matches the local window in the target area image used to calculate that CM value. The position of the matching local window in the target area image formed by the SAR 18B (FIG. 1) indicates the target position in the target area image. (That is, the center of the matching local window in the image formed by SAR 18B is the relationship between the center of the reference image selected by target designator 19 (FIG. 1) and the target in the image formed by SAR 18A. The same relationship holds for the target.) By providing this position in the missile control system, the missile's flight line can be adjusted.

(Alternative Examples of Template Generator and Edge Template Correlator) It is also possible to generate a template by using an alternative method and match it to the target area image. The above method is an alternative to the method shown in FIGS. 9A, 9B and 10a, 10B. The above method requires more processing in the reference template generator 34 (FIG. 2), and is less desirable in some applications than in the previous preferred embodiment. However, the alternative described below creates a template that more accurately matches the target area image, often resulting in less processing in the edge template correlator 42 (FIG. 2).

In the preferred embodiment described above, the template was an array representing the identified edges detected in the reference image. A single threshold K was calculated for the template and used by the edge template correlator 42 to match the template to the target area image. In this alternative, the template consists of a pair of pixel lists for each edge identified in the reference image. A separate threshold is calculated for each edge. Because of the different thresholds for each edge, it is more likely that the edge template correlator 42 will match the template to the portion of the target area image that actually contains the target.
This alternative template requires less digital memory than a computer incorporating a missile-based processor 40 (FIG. 2) to store the template using the preferred embodiment described above. It offers an additional advantage in that it does not.

FIG. 11 shows the processing performed by the reference template generator 34 (FIG. 2) in an alternative embodiment. Processing block 350 selects one pixel in the EEB map. As each pixel in the map is processed, processing block 350 selects a previously unprocessed pixel.

[0086] Decision block 352 determines whether the selected pixel is equal to zero, ie, it does not represent an edge. If the selected pixel does not represent an edge, then if more pixels remain to be processed, the next pixel in the EEB map will be selected. Decision block 354 determines whether more pixels remain.

The selected pixel representing the edge will be the first entry in the list of pixel locations along the edge.
In subsequent processing, by examining neighboring pixels to determine if they lie along an edge,
Add the position of other pixels along the edge.

Decision block 358 determines whether each of the four pixels closest to the selected pixel has been checked to see if it can be added to the list. If one or more of the nearest pixels remains to be tested, processing block 360 selects one of the remaining neighboring pixels. On the other hand, if all of the neighboring pixels have been tested, processing moves to decision block 354 where another pixel can be selected. If the two pixels are adjacent and testing the second pixel to determine if it is on the same edge as the first, then testing the first pixel and Note that it is not necessary to determine if they are on the same edge as the two. Decision block 35
Numeral 8 utilizes this commutative property to avoid redundant processing of adjacent pixels.

Decision block 362 determines if the pixel in the SBRE map corresponding to the pixel selected in processing block 350 and the adjacent pixel selected in processing block 360 have the same value (ie, on the same side of the edge). Skip the selected neighboring pixels (if any).
If the value is 0 (ie, not on an edge), the adjacent pixel is also skipped if the pair of pixels has already been processed according to a pixel list along a different edge.

If the adjacent pixel is not skipped as determined at decision block 362, the location becomes part of the list of pixel locations along the edge. Processing block 364 uses these two selected pixels as starting points to identify pixels along its edges. FIG. 12 shows a portion 410 of a two-dimensional array, showing how processing block 364 selects pixels to add to the list of pixels on the edge. Pixel 400 ₁ indicates the pixel selected in processing block 350. (FIG. 11) Pixel 400 ₂ is processing block 3
60 represents the neighboring pixel selected. (FIG. 11) Nodes 402 ₁ and 402 ₁ indicate points where four pixels connect. Pixels 400 ₁ and 40 on different sides of the edge
0 ₂ edge segment 404 when selected indicates that edges come there.

The edge will be extended by finding another pair of pixels on the opposite side of the edge and adjacent to at least one of the pixels already known to be on the edge. The edge could extend from one of its two sides. 12, the edge will be able to extend from the node 402 ₁ or the node 402 _2. In this case, assume that the edge extends from node 402 ₂ .

[0092] When extending an edge from node 402 _2, potential node 406 _1, 406 ₂ or 406 ₃
Could be extended from The direction in which the edge extends depends on which side of the edge the pixels 408 ₁ and 408 ₂ fall. As described above for the global edge detector 30 (FIG. 2), the SRBE map divides the reference map into a series of regions, and for this template generation, the edges are formed to be between those regions. . If the pixel ₄₀₈₁ is in the same area as the pixel 400 ₁ as described by SRBE map pixels 408 ₂ is in the same region as the pixel 400 _2, the edge must contain a potential node 406 _2, pixels 4
08 ₁ and 408 ₂ are added to the list of edge pixels. Also, pixels 408 ₁ and 408 ₂ are
_May be in the same area as ₁ . In that case, the edge extends to include potential node 406 _3,
Pixel 408 ₂ is added to the list of edge pixels. The last possibility is that pixels 408 ₁ and 408 ₂ are in the same area as pixel 400 ₂ . If the edge extends to include potential node 406 _1, pixel ₄₀₈₁ is added to the list of edge pixels.

The edge is further extended by the following pattern shown in FIG. Node 402 ₂ in the last node to be added to the edge, 402 ₁ was the previous node of the last node to be added to the edge. Once it is added to one of edges of potential nodes 406 _1, 406 _2, or 406 ₃ Ralt, node 402 ₂ is the second node from the last, any potential node it be added to the list is the last Become a node. A new set of potential nodes near the last node on the edge is shown in FIG.
2 is determined using the same pattern as that shown in FIG. In following the pattern, two pixels adjacent to the last node added to the edge and adjacent to the node before the last node added to the edge are pixels 400 ₁ and 400 ₂
Used when and are used. Similarly, when pixels 408 ₁ and 408 ₂ are used, _two pixels adjacent to the last node added to the edge and not adjacent to the node before the last node added to the edge are used. Is done.

The pattern shown in FIG. 12 continues until a complete edge has been tracked. Two pixels (eg, pixels 408 ₁ and 408 ₂ ) at the end of the edge are adjacent to the last node and not adjacent to the node before the last node.
Detected when not on an edge as reported by the EB map (ie, when the corresponding value in the EEB map is 0). Edge edges could be recognized even if there were no pixels that had to be considered to follow the pattern to reach some boundary of the array. Instead, if any of the pixels that must be considered to follow the pattern of FIG. 12 have already been added to the list of edge pixels, as if the closed edge were tracked throughout, the edge edge would be Is detected. Also, the edge of the edge is adjacent to the last node and not adjacent to the penultimate one (ie, pixels 408 ₁ and 408 ₂ ) are either pixels selected in processing block 350 or 360. (Ie, pixel 400 ₁
Or, it is also detected when it does not have the same value as 400 ₂ ). This condition can only occur when forming an SRBE image using the above alternatives so that the pixels in the image can take on values of 1, 2, 3, or 4. .

Once processing block 364 traces the edge completely in one direction, processing block proceeds to processing block 366, which traces the edge in the other direction. Processing block 366 follows the same pattern followed by processing block 364 except that first node 402 ₁ is considered the last node and node 402 ₂ is considered the penultimate node. Then, the edge extends from the node 402 _1. In the special case where the edge was traced around in a closed loop at processing block 364, processing block 366 does not perform any further processing. Once the edges have been traced to both ends by processing blocks 364 and 366, the list of pixels on the edge is broken down into two lists in processing block 368. Each pixel on the bright side of one edge, as evidenced by the large value in the SRBE map, is placed in the bright list. The remaining pixels are placed in the low intensity list. The list also includes the pixels in the two pixels adjacent to the edge, eg, on each side of the edge.

Processing block 370 includes processing block 368
Calculate the correlation threshold for the edge represented by the pair list formed in. Processing block 370 uses the process shown in FIG. 9B and described above. Since the edge pixels have already been identified and separated into a list of pixels on the high and low intensity sides of one edge, the processing in FIG. 9B that serves that role is omitted for simplicity. Decision block 2 of FIG. 9B
60 checks whether the selected pixel is on one edge. Since all the pixels in the list are on one edge, the decision block can be omitted. Decision block 262 checks whether one selected pixel is on the high or low intensity side of the edge. Because the pixels have already been sorted into the high and low intensity lists, decision block 262 directs execution of the program to processing block 264 if a pixel from the high intensity list is selected in processing block 258;
If a pixel from the low intensity list has been selected, it is directed to processing block 268.

Returning now to FIG. 11, once the correlation threshold K has been calculated in processing block 276 (FIG. 9B), decision block 372 checks if the value of K is greater than one. If the value of K is too small, the list pairs will be discarded by processing block 374 and those lists will not be considered for further inclusion in the template. On the other hand, if K is large enough, the list is stored at processing block 376 for further processing. Processing block 376 also stores the correlation threshold K calculated for those lists. Regardless of whether the list has been retained, processing returns to decision block 358.

[0098] Decision block 358 determines whether or not it has been checked that all pixels adjacent to the pixel selected in the decision block as described above are along the same edge as the selected pixel. If all pixels adjacent to the selected pixel are checked, decision block 354
Another pixel is selected as long as it determines that there are more pixels to be tested. However,
Block 362 will skip any pixel-neighbor pixel pair if the pixel is already in the list of pixels near the edge of the neighboring pixel and is on the list on the other side of the edge. Otherwise, even though the pixel is already on one list, the selected pixel may represent a pixel on a different edge than the one tracked earlier. In that case, the edge will be tracked in processing blocks 364 and 366 and will eventually be in another list pair. The list pair is also stored at processing block 376 in response to the result of the comparison performed by decision block 372. Thus, E
Once all the pixels in the EB map have been selected and processed, a list of pairs of pixels along different edges will have been retained by processing block 367. When all the pixels in the image have been processed as determined by decision block 354, the retained list pair will form the basis of the template.

The retained list pair is further processed in processing block 3
Processed at 56. Details of the processing will be described below with reference to FIGS. The output of processing block 356 is the output of reference template generator 34. (FIG. 2) Alternatively, processing block 356 can be skipped so that the output of the reference template generator (FIG. 2) consists of all the list pairs held in processing block 376.

Referring now to FIGS. 13 and 14, there is shown the processing for the retained pairs of pixel lists on the edge. Each paired list represents an evaluation of the position of one edge. For any reason, the evaluation of the edge position may not be the best possible evaluation of the edge position. The process shown in FIGS. 13 and 14 serves to modify the list of pairs describing the edges in order to find a better evaluation of the edge position. Processing block 500 selects one of the list pairs stored in processing block 376. (FIG. 11) Each list pair must be processed, and processing block 500 selects the previously unprocessed pair.

Processing block 502 selects pixels from the filtered image created by smoothing filter 26. (FIG. 2) Processing block 502 selects a pixel corresponding to a pixel in the high intensity list of the selected list pair.

Processing block 504 sorts the selected pixels according to their respective intensities. Decision block 5
05 checks if it is possible to identify edges by calculating a new threshold and dividing the selected pixel into pixels above and below the threshold. (Edges will be between pixel areas above and below the threshold.)
To determine if a suitable threshold exists, decision block 505 identifies pixels that are an unknown quarter of the way from the end of the order created by processing block 504. Thereafter, decision block 504 determines whether any of the other pixels selected in processing block 502 have a value different from the value of the last quarter pixel. If there is such a pixel with a different value, a new threshold is calculated at processing block 506. Otherwise, processing resumes at decision block 512.

[0103] Processing block 506 calculates the new threshold. The threshold is the average of the value of the last quarter pixel in the order created by the processing block and the value of the next closest pixel with a different value in the order. In this case, the degree of “close” is determined by processing block 504.
It is measured in proportion to the end (bottom) of the order created by. For example, a pixel that is one-eighth from the end of the order will be farther from the last one-half pixel than the last-half pixel. This is because one-eighth is only one-half from the quarter to the end, and one-half is only one-third from the quarter to the beginning (top).

Thereafter, the processing block 82A binarizes the filtered image using the calculated threshold value. Pixels in the divided image corresponding to pixels in the filtered image having a luminance equal to or less than the threshold are given a value of one. Pixels in the segmented image that correspond to pixels in the filtered image having a luminance above the threshold are given a value of four. The binarization process is the same as that in the processing block 82 (FIG. 3), and finally a divided image is obtained. However, processing block 82A processes the selected pixel rather than the entire image. Processing block 82A processes the pixels selected in processing block 502 and the eight nearest neighbors for each of them.

The divided image serves as an input to the edge extractor 32A. Since edge extractor 32A is identical to edge extractor 32 (FIG. 2), it performs the processing already described with respect to FIGS. 8A and 8B except that only a small portion of the image is included. Processing block 32A processes the same group of pixels as processing block 82A.

The confirmation edge map created by the edge extractor 32A is used as a reference template generator 34.
A. The operation of the alternative reference template generator 34 (FIG. 2) is shown in FIG. The reference template generator 34A has the configuration shown in FIG. 11 except for one example.
The same processing as the processing shown in (1) is performed. The processing block 356 (FIG. 11) where the pairs of pixel lists along the edge are edited is not processed. Processing block 376
The list pairs with their respective correlation thresholds maintained in (FIG. 11) are simply provided as outputs of the reference template generator 34A in FIGS.

Decision block 510 compares the correlation threshold of the list pair created by reference template generator 34 A with the correlation threshold of the list pair selected in processing block 500. If no list pairs have been created by reference template generator 34A, processing proceeds at decision block 512. If the correlation threshold of all newly created est pairs is below the correlation threshold of the list pair selected in processing block 500, no further processing is performed on the newly created list pair. Is not performed. Thereafter, processing continues at decision block 512 for the list pair selected in processing block 500, and the newly created list pair is effectively ignored.

If one of the newly created list pairs at the time of the decision at decision block 510 is
If it has a correlation threshold that is greater than the correlation threshold of the list pair selected at 0, processing continues at decision block 516. Decision block 516 determines whether one or more list pairs have been created by reference template generator 34A. If only one list pair has been created, the list pair selected in processing block 500 is deleted from the template in processing block 518, and the newly created list is added to the template.

If multiple list pairs are generated by reference template generator 34A, decision block 520 indicates that all of the newly generated list pairs have a correlation threshold greater than the correlation threshold of the list pair selected in processing block 500. Determine whether or not. If all newly generated list pairs have a correlation threshold that is greater than the correlation threshold of the list pair selected in processing block 500,
Processing block 522 retains all of the list pairs as part of the template for further consideration. Processing block 518 replaces the list pair selected in processing block 500 with one of the newly generated list pairs. Other newly created list pairs are stored by processing block 522. Those newly created list pairs are called "spin-off list pairs" and processing block 376
Treated just like list pairs held in. (FIG. 11) If not all of the newly generated list pairs have a correlation threshold that is greater than the correlation threshold of the list pair selected in processing block 500, decision block 524 returns to the newly generated list pair. Check the maximum correlation threshold for the list pair of. If the correlation threshold is equal to processing block 5
If it is sufficiently greater than the correlation threshold of the list pair selected at 00, all of the newly generated list pairs will be processed in processing blocks 522 and 518 as described above. Otherwise, none of the newly created list pairs will be processed and processing will continue at decision block 512. In this embodiment, decision block 524 determines that the newly generated correlation threshold is at least 5% greater than another threshold, or sufficiently greater if it is at least 0.1 greater.

If processing block 518 is processing block 5
If the above condition occurs to replace the list pair selected at 00, processing returns to processing block 502. The above process is then superseded by a new risk pair to be used instead of the previously selected list pair in processing block 500. However, if certain restrictions are not imposed, processing will return to iterative processing block 502. Decision block 526 determines how many times processing returns to processing block 502. If processing block 518 is executed three times without execution of decision block 512, then decision block 526 prevents processing from returning to processing block 502. Instead, decision block 512 is executed.

Processing block 502 includes processing block 500
Recall that we have selected the pixels in the EPS image that correspond to the pixels in the bright list of the list pair selected in. The low brightness list of the selected list pair is processed in the same manner. Decision block 512 determines whether the low intensity list of the selected list pair is to be processed. in this case,
The selected list pair will be an alternative to the list pair created in processing block 518 within the list selected in processing block 500. If the selected list is a new list pair stored by processing block 522,
If the alternative list pair is stored at processing block 518, the low intensity list of that pair is processed only if the correlation threshold of the selected list pair is less than the correlation threshold of the original list pair. If the low intensity list has already been processed or does not need to be processed, the process passes to decision block 530, which illustrates the minimum correlation threshold for the selected list pair, in this case 1. Check if it exceeds 25. If the correlation threshold is below that value, the list pair is discarded at processing block 32 and will not be part of the template. Execution then moves to decision block 528, which loops execution to processing block 500, where another list pair is selected and the entire process is repeated.

If the low intensity list of the selected list pair is to be processed, processing block 502 selects a pixel in the EPS image corresponding to a pixel in the low intensity list. Processing of those selected pixels proceeds to the same extent as did for the selected pixels using the high intensity list. The only difference is that decision block 505 and processing block 506 process the last three-quarters of the sorted list from the last four-quarter pixels. That is.

Once all of the list pairs held at the time of the determination at decision block 528 have been processed, the template editing process ends. The list pairs with their respective correlation thresholds are stored in a reference template generator 34.
(FIG. 2).

Note that the template generated by the alternative to reference template generator 34 (FIG. 2) produces a different form of template than the preferred embodiment of reference template generator 34 (FIG. 2). Thus, a modification to the edge template correlator 42 (FIG. 2) is required.

FIG. 15 shows the processing performed by an alternative example of the edge template correlator 42 (FIG. 2). Processing block 300A combines local window with processing block 300 and decision block 32 according to decision block 326A.
6 (FIG. 10) is slid on the target area image.

Processing block 550 selects one of the list pairs that make up the template. This time, as each list pair is processed, processing block 550 selects a previously unprocessed list pair. Decision block 552 verifies that the selected list pair has an entry in the high and low intensity lists. If no list has an entry, the list pair is skipped. Otherwise, execution continues at processing block 554.

[0117] Processing block 554 calculates two thresholds for the selected list pair. Threshold THRP and THR
M is calculated according to the following equation.

THRP = (SUMP / NPOS) / K THRM = K (SUMN / NNEG) where K is the correlation threshold for the list pair, and SUMP is the local window of the target area image corresponding to the pixel in the high brightness list. Sum of luminance values of all pixels, SUM
N is the sum of the luminance values of all the pixels in the local window of the target area image corresponding to the pixels in the low luminance list;
POS is the number of pixels in the high brightness list, and NNEG is the number of pixels in the low brightness list. Processing block 556 uses SERP + and SENB using thresholds THRP and THRM.
Form two binary detected image lists marked-. S
The ENB + list has as many entries as pixels in the high intensity pixel list. The SENB list has as many entries as the pixels in the low intensity pixel list. For each pixel in the bright pixel list, the corresponding pixel in the local window of the target area image is identified. If the brightness of the pixel exceeds THRM, the SEN corresponding to the pixel in the high brightness list
The entry in the B + list is set to one. Otherwise, the entry in the SEB + list is set to -1. Similarly, for each pixel in the low intensity list, the corresponding pixel in the local window of the target area image is identified. If the brightness of the pixel is THRP
, The corresponding entry in SENB- is set to one. Otherwise, it is set to -1.

Processing block 558 comprises SENB + and SEN
B—Update the variables R ₁ , R ₂ , S ₁ , S ₂ , H ₁₁ , H ₁₂ , H ₂₁ , H ₂₂ based on the values assigned to the entries in the list. These variables are initialized to zero before the start of the processing in FIG. 10, and are updated according to the following equations.

[0120] R ₁ is incremented by the number of pixels in the low luminance list.

R ₂ is incremented by the number of pixels in the high intensity list.

[0122] S ₁ is only an incremental number of positive entries in the middle SENB + and SENB-.

[0123] S ₂ is only an incremental number of negative entries in the middle SENB + and SENB-.

[0124] H ₁₁ is incremented by the number of positive entries in the middle SENB-.

[0125] H ₁₂ is incremented by the number of negative entries in the middle SENB-.

[0126] H ₂₁ is incremented by the number of positive entries in the middle SENB +. H ₂₂ is incremented by the number of negative entries medium SENB +.

Once the variables are updated for one list pair, decision block 560 determines whether there are any remaining list pairs to be processed. If so, execution returns to processing block 550. The next list pair is selected and processed. When all list pairs have been processed,
Decision block 560 yields execution to processing block 322A. Note that processing blocks 322A and 324A and decision block 326A are identical to processing blocks 322 and 324 and decision block 326. (FIG. 10) Thus, the edge template correlator 4
The result produced by the second alternative (FIG. 2) is identical to the result produced by its preferred embodiment (FIG. 2).

[Brief description of the drawings]

FIG. 1 is a sketch diagram of a system using the present invention.

FIG. 2 is a block diagram of a process for generating target coordinates used in guiding a missile.

FIG. 3 is a flowchart of a process executed by the global edge detector of FIG. 2;

FIG. 4 is a flowchart of a process executed by a template editor in the global edge detector of FIG. 3;

FIG. 5 is a mask diagram used in the processing performed by the local edge detector of FIG. 2;

FIG. 6A is an illustration of FIG. 2 for forming an alternative ratio image.
FIG. 9 is a first partial diagram of a flowchart of a process executed by the edge extractor of FIG. FIG. 6B is a continuation of the flow diagram of FIG. 6A.

7C, 7D, 7E, and 7F are mask diagrams used in the processing of FIG. 6A.

FIG. 8A is a first partial view of a flowchart of a process performed by the edge extractor in FIG. 2 to form an edge-extended boundary image. FIG. 8B is a continuation of the flowchart of FIG. 8A.

FIG. 9A is a flowchart of a process performed by the reference template generator of FIG. 2 to form a reference template. FIG. 9B is a flowchart of a process performed by the reference template generator of FIG. 2 to form a correlation threshold.

FIG. 10A is a first partial view of a flowchart of a process executed by the missile-mounted processor of FIG. 2; FIG. 10B is a continuation of the flowchart of FIG. 10A.

FIG. 11 is a flowchart of a process performed by an alternative of the reference template generator of FIG.

FIG. 12 is a sketch diagram of the pixels considered during the process shown in FIG.

FIG. 13 is a first partial view of a flowchart of template editing executed as a part of the processing shown in FIG. 11;

FIG. 14 is a continuation of the flowchart in FIG. 13;

FIG. 15 is a flowchart of a process executed by an alternative example of the missile-mounted processor in FIG. 2;

Continued on the front page (72) Inventor Albert H. Long, Geraldine Road, Framingham 01701, Massachusetts, USA 7 (72) Inventor Stephen El Richter, Massachusetts 01451, Harvard, Highness Lane 16 (72) ) Inventor Harold Jay Geller, Laurie Road, Framingham, Mass., USA 01701, Massachusetts 3 (72) Inventor Irving Canter 02173, Lexington, Waltham Street, Massachusetts, USA 277 (72) Inventor Gordon Elle Kettering Lido Lane, Bedford, Mass., United States 01730, Bedford 7 (56) References JP-A-63-284686 (JP, A) JP-A-64-46890 (JP, A) JP-A-2-226378 (JP, A) ) 106186 (JP, A) JP-A-2-18751 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06T ⁷ /00-7/60 G06T 5/00 H04N 7/12- 7/137 F41G 7/22 JICST file (JOIS)

Claims (2)

(57) [Claims] 1. A method of registering two images of the same scene, each comprising a pixel array, comprising: (a) forming a first map of a portion of a first image, wherein the first map is a pixel array; And each of said pixels in the first map has a value indicating whether a pixel in the first image corresponding to a pixel in the local window surrounding the pixel in the first map forms an edge. (B) forming a second map for a portion of the first image, the second map comprising a pixel array, each of the pixels in the second map corresponding to a pixel in the second map; (C) combining said first and second maps to form a third map comprising a pixel array. Forming a map, wherein each pixel in the third map has a value indicating whether a corresponding pixel in a portion of the first image represents an edge of an object in the image, and (d) modifying the third map. Calculating a score for each portion of the second image by successively comparing with a portion of the second image, the score corresponding to a pixel in the third map having a value representing an edge in the first map; Indicating that the pixels in a portion of the second image may also be edges in the second image at the same time, and (e) selecting a portion of the second image that yields the highest score corresponding to a portion of the first image; A method consisting of steps. 2. A first image representing an area near a target and formed on an aircraft carrying a missile by a first SAR, and a second image comprising a second image generated by the second SAR after the missile is launched from the aircraft. The method of claim 1 wherein the missile is formed and (b) the missile is guided based on a second image portion selected to produce a highest score.