CN103337068B - The multiple subarea matching process of spatial relation constraint - Google Patents

Abstract

The invention discloses a multi-subregion matching method based on spatial relationship constraints, which selects a plurality of subregions in a matching template as sub-templates and simultaneously matches with an image to be matched respectively, and uses the spatial position relationship of each sub-template to realize image accuracy. Matching, which includes: selecting several sub-regions in the matching template as sub-templates; determining the spatial positional relationship between each sub-template; each sub-template keeps its spatial positional relationship unchanged to form a combined template, and utilizes the combined template in the image to be matched Move up and search for matching, and obtain multiple similarity values of the combined template; compare the above multiple similarity values, and use the position with the largest similarity value as the best matching position to complete the matching. The method of the present invention utilizes the mutual spatial relationship between each sub-area to achieve matching accuracy and precision requirements. Compared with the traditional large template grayscale or contour matching algorithm, the method has a greater real-time performance in target recognition performance. improve.

Description

Multi-subregion matching method with spatial relationship constraints

technical field

The invention belongs to the technical field of digital image matching, and in particular relates to an image multi-subregion matching method.

Background technique

With the rapid development of science and technology, especially computer technology, image processing technology that directly obtains information from images has developed rapidly. Image matching is one of the very important technologies in computer vision and image processing.

Image matching is the process of finding subimages corresponding to known patterns through matching calculations in one or more unknown images. At present, image matching technology is widely used in various fields such as military, industry, remote sensing, medicine and machine vision.

In an actual image matching application, it is necessary to select a template with an appropriate size. However, in the matching calculation, if the template graph is enlarged, the calculation amount of the matching will increase dramatically, which will not be able to adapt to the occasions with high real-time requirements. If the size of the template is reduced in order to reduce the calculation amount, it will affect the matching performance. Accuracy and precision. In applications that require high real-time performance, sometimes the accuracy and accuracy of matching have to be reduced in order to ensure real-time performance.

In recent technologies, there are many similar methods using template matching, such as "Research on Infrared Forward-Looking Technology for Recognition of a Class of Special Building Targets" by Ming Tian et al. 31, No. 4), in view of the characteristics of infrared/visible multi-mode image matching, a calculation method based on the gradient vector correlation coefficient is proposed. For the shortcomings of the gradient strength correlation coefficient calculation method that loses the gradient direction information, this method uses the gradient vector Matching is carried out using the field to avoid the loss of direction information, and the similarity measure of large template matching is used to greatly improve the matching performance. However, in occasions with high real-time requirements, this method will be lacking, and it cannot make full use of the important information of the template in a short calculation time to achieve the effect of fast calculation.

Existing methods for improving matching speed are difficult to guarantee better matching performance, either because the accuracy and accuracy of matching are significantly different from matching algorithms that have not been speeded up, or because the stability of improving matching speed is poor, and in some In some cases, it can reduce the amount of calculation and increase the matching speed, but in some cases it can hardly reduce the amount of calculation, that is, the calculation speed of the matching algorithm after speed-up is basically the same as that of the matching algorithm without speed-up.

Contents of the invention

In view of the above defects or improvement needs of the prior art, the present invention provides a multi-subregion matching method based on spatial relationship constraints, the purpose of which is to divide a large template into several smaller sub-templates, each sub-template Maintain the same positional relationship as the large template, thereby solving the technical problem of reducing the amount of calculation and improving the calculation speed while ensuring the matching accuracy and accuracy.

The concrete technical scheme that takes for realizing the object of the present invention is as follows:

(1) Select a sub-area

Several small areas belonging to the large area are called sub-areas, and several sub-areas are selected on the template, and the sub-areas are also used as sub-templates.

The principle of sub-area selection is generally to select corner points, areas with obvious line features, areas that are different from other sub-areas or have a certain degree of discrimination, and try to avoid areas with many repeated patterns. The size of each sub-area should not be too small, otherwise, when there is a scale or angle error, it will have a great impact on the matching accuracy and correct rate. Pay attention to the spatial relationship constraints when selecting sub-regions. The selection of each sub-region should not be too close to each other. These sub-regions should contain most of the information of the large template, which can also reduce errors and improve matching accuracy.

(2) Calculate the spatial position relationship of the sub-areas

The spatial position relationship between the sub-regions is calculated through the template map. The calculation method is as follows:

First, take any sub-area as the benchmark, and take any point in the benchmark sub-area (for example, the upper left corner point or the center point) as the coordinate origin, and calculate the distance between the corresponding point of other sub-areas and the any point on the benchmark sub-area. The coordinate points of other sub-areas are obtained, so as to obtain the spatial position relationship between other sub-areas and the reference sub-area.

Since the calculation is the relative positional relationship of each sub-area, the positional relationship between the sub-areas is fixed, so no matter which sub-area is selected as the reference, the spatial positional relationship of each sub-interval remains unchanged and has no effect on the matching performance.

(3) Match calculation

Matching refers to searching for the same or the closest matching area by using the sub-areas in the reference image in the real-time image to be matched. When performing matching calculation, the spatial position relationship of each sub-region is kept unchanged, and each sub-template is moved on the image to be matched at the same time for matching. The degree of matching is measured by similarity, and the matching process is the process of calculating similarity.

When calculating the similarity, you can calculate the similarity value of each sub-region separately, and then add the similarity (confidence) values of each sub-region to obtain a sum of similarity values, which is used as a measure The degree of similarity of the area formed by the above-mentioned multiple sub-areas.

There are many mature methods for the calculation of similarity. Now, the normalized cross-correlation method is used to explain how to calculate the similarity value R of a sub-region.

The normalized cross-correlation method (Normal cross-correlation referred to as NCC) is calculated as formula (1):

$\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}{\sqrt{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; I</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}\sqrt{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

In the formula: R(x, y) is the similarity value, I(i, j) is the search image with the size of W×H, that is, the image to be matched, and T(i, j) is the sub-region template with the size of M×N , where (i, j) is any pixel point, M, N, W, H are all positive integers, representing the length and width of the search map, and the length and width of the sub-region template, respectively. (x, y) is the coordinate of any point in the subgraph covered by the template (such as the upper left corner vertex) in the search graph.

Of course, when calculating the similarity value, it is also possible to calculate an overall similarity value by considering each sub-area as a large template.

(4) Get the best matching point

Compare these similarity values in the search area, and take the position with the largest similarity as the best matching position.

The method of the present invention splits a large template into several smaller sub-templates, each sub-template maintains the same positional relationship as the large template, and each sub-template only contains important information in the large template, ignoring the information in the large template. Information with little reusability can be applied to multiple occasions while fully ensuring the matching accuracy and accuracy. On the premise of ensuring the matching accuracy and accuracy, the matching speed is greatly improved, and the amount of calculation is greatly reduced. To achieve the purpose of improving the operation speed.

Image matching is carried out by the multi-subregion matching method constrained by the spatial relationship of the present invention, which not only makes full use of the important information in the large template graph, but ignores the information in the large template that is not reusable in the calculation process, and reduces the amount of calculation. To meet the real-time requirements, the mutual spatial relationship between each sub-area can also be used to meet the matching accuracy and precision requirements. A large number of experimental results show that, compared with the traditional large template grayscale or contour matching algorithm, the real-time performance of this method is greatly improved in target recognition performance.

Description of drawings

FIG. 1 is a schematic flowchart of a multi-subregion matching method with spatial relationship constraints according to an embodiment of the present invention.

FIG. 2 is a scene diagram of a specific application of the embodiment of the present invention.

Fig. 3 is a large target template diagram selected by the embodiment of the present invention.

Fig. 4 is a schematic diagram of multiple sub-regions selected in the embodiment of the present invention.

Fig. 5 is a schematic diagram of the mutual positional relationship of each sub-area according to the embodiment of the present invention.

Fig. 6 is the coordinates of each sub-region on the image to be matched during the matching calculation according to the embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

As shown in Figure 1, the specific steps of the multi-subregion matching method based on spatial relationship constraints in this embodiment are as follows:

(1) Select a sub-area

The scene graph and target are shown in Figure 2, and the template graph selected to match the target is shown in Figure 3. According to the characteristics of the template map and the sub-area selection principle introduced earlier, multiple (for example, 5) sub-areas with a certain degree of distinction are selected on the template map. These areas mainly include corner points, line features, and features different from other areas. The special shape of the sub-area or other content with a certain degree of discrimination, the selected area is shown in Figure 4.

(2) Obtain the spatial position relationship of each sub-area

After selecting the sub-areas, it is also necessary to obtain the spatial position relationship of each sub-area.

Any sub-area can be taken as a reference, and a point in the reference sub-area (preferably the upper left corner point or center point) is used as the origin of coordinates. By calculating the relative distance between other sub-areas and the reference sub-area, the calculation of the distance, Their relative coordinates can be read through their relative positions on the large template to obtain the coordinate values of other sub-regions.

Here, taking the upper left corner point of the reference sub-area as the coordinate origin as an example, the spatial position relationship of other sub-areas on the template map with respect to the reference sub-area is shown in Figure 5.

If the image of the target is observed from different angles of view at high altitude, the size and shape of the image will change due to the existence of perspective transformation. , making the alignment difficult. In order to reduce the influence of high-altitude perspective, before matching, each sub-template should be perspective-transformed from the down-view direction to the front-view direction, and then the transformed sub-templates should be used for matching.

(3) Match calculation

When performing matching calculations, the spatial positional relationship of each sub-area is maintained for matching, that is, each sub-area keeps its positional relationship unchanged and simultaneously searches and matches on the image to be matched.

In order to maintain the spatial position relationship of each sub-area, the position of the reference sub-area can be determined first, and then the position of other sub-areas on the map to be matched is calculated through the mutual positional relationship between other sub-areas and the reference sub-area, and then the matching calculation is performed .

For example, the coordinates of the reference sub-region on the image to be matched are (70, 221), then the coordinates of other sub-regions on the image to be matched are calculated through their mutual positional relationship, as shown in Figure 6.

After determining the matching position of each sub-region on the image to be matched, the similarity between the template and the image to be matched can be calculated.

When calculating the similarity measure, the similarity of each sub-area is calculated separately, and then the similarity of each sub-area is added together to obtain the final result as shown in formula 2.

c＝c ₁ +c ₂ +...+c _n (2)

Where c is the similarity calculated at a position of the template map on the real-time map, c ₁ , c ₂ ... c _n represent the similarity of each sub-region, and n represents the number of sub-regions.

Of course, it is also possible to use each sub-area as a whole large template for calculation, that is, when calculating, the combination of each sub-area is regarded as a large template, and an overall similarity value c is directly calculated. In this way, each sub-area The calculation of the area as a whole is similar to the method of separately calculating the similarity of the sub-areas and adding them together. Compared with directly using all the information of the large template for matching, it also has an advantage in speed. This method of multi-subregion matching using spatial relationship constraints accumulates the similarity obtained by each subregion combined, makes full use of the important feature information contained in the large template map, and eliminates redundant feature information in the large template. The amount of calculation is reduced, so it is more advantageous in matching real-time performance.

(4) Get the best matching point

Finally, compare these similarity values in the search area, obtain the position with the largest similarity, and use it as the best matching position to complete the matching.

It is easy for those skilled in the art to understand that the above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, All should be included within the protection scope of the present invention.

Claims (3)

1. the multiple subarea matching process based on spatial relation constraint, it mates with image to be matched as subtemplate respectively by choosing multiple subregion in matching template simultaneously, the spatial relation of each subtemplate is utilized to realize accurate matching of image, it is characterized in that, the method specifically comprises:

Choose several subregions at matching template, respectively as subtemplate, described all subregion is separate, does not respectively overlap;

Determine the spatial relation between each subtemplate, wherein the spatial relation of each subtemplate is determined by the distance of corresponding point in each subtemplate, namely using any subtemplate as benchmark, and with any point in this benchmark subtemplate for true origin, calculate the point of other subtemplate corresponding position and the distance of this this any point, the spatial relation between other subtemplate and benchmark subtemplate can be obtained;

Each subtemplate keeps the indeformable one-tenth gang form of its spatial relation, utilizes the mobile search on image to be matched of this gang form to mate, to obtain the Similarity value of this gang form multiple;

More above-mentioned multiple Similarity value, and using the maximum position of wherein Similarity value as best match position, complete coupling.

2. the multiple subarea matching process based on spatial relation constraint according to claim 1, is characterized in that, the Similarity value of described gang form is added by the Similarity value of each subtemplate in this gang form and obtains.

3. the multiple subarea matching process based on spatial relation constraint according to claim 1, is characterized in that, any point in described benchmark subtemplate can be other arbitrfary points on the central point in subtemplate region, frontier point or region.