CN106126919A - A kind of accurate Hausdorff distance computational methods between any type point set data - Google Patents

Abstract

The invention discloses an accurate Hausdorff distance calculation method between any type of point set data. First, two point set data A and B are input. If the point set is scattered and disordered point cloud data, the Morton curve is used. (Morton Curve) preprocesses the scattered and unordered point set data A and B, so that the point set is ordered and has good spatial locality. Then use the local search algorithm to calculate the one-way Hausdorff distance h(A, B) and h(B, A) respectively. Finally, compare the one-way Hausdorff distance h(A, B) and h(B, A), and take the maximum value as the Hausdorff distance H(A, B). The present invention utilizes the spatial locality of the data to reduce the points that do not contribute to the Hausdorff distance in the traversal inner loop, thereby greatly reducing the complexity of calculation. Combined with the Morton curve method, the present invention can process any type of point Collecting data is more versatile.

Description

A Calculation Method of Accurate Hausdorff Distance Between Any Type of Point Set Data

technical field

The invention belongs to the technical field of pattern recognition and shape matching, and relates to a calculation method for precise Hausdorff distance (Hausdorff Distance) between any type of point set data, in particular to an exact Hausdorff distance for any type of point set with local search Dove distance calculation method.

Background technique

Hausdorff distance is a very important measure of similarity, widely used in pattern recognition, shape matching and other fields. However, the calculation of Hausdorff distance is a very challenging task because the calculation of Hausdorff distance includes both the maximum value and the minimum value problem. Hausdorff distance has received great attention from academia and industry and many effective algorithms have been proposed to reduce the computational complexity of Hausdorff distance. Generally speaking, according to the type of data processed, Hausdorff distance calculations can be divided into three categories: polygonal models, point sets, and mesh surfaces. Similarly, Hausdorff distance algorithms can be roughly divided into approximate algorithms and exact algorithms.

Given a point set A and a point set B, the Hausdorff distance H(A, B) is defined as follows:

H(A, B=max(h(A, B, h(B, A))

Where h(A, B) and h(B, A) are one-way Hausdorff distances, and h(A, B)≠h(B, A) one-way Hausdorff distances are defined as:

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; A</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}}{\mathrm{<span\; class="notranslate">\; min</span>}}\mathrm{<span\; class="notranslate">\; d</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; A</span>}}{\mathrm{<span\; class="notranslate">\; min</span>}}\mathrm{<span\; class="notranslate">\; d</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

The dist(.,.) function is the Euclidean distance function;

It is very difficult to calculate Hausdorff distance by brute force method, especially when dealing with large-scale point set data. At present, the latest method to calculate the exact Hausdorff distance between point sets is the EARLYBREAK method, but there are still some shortcomings in this method. First, when two point sets partially overlap, the EARLYBREAK method cannot effectively reduce the computational complexity of the Hausdorff distance for any type of point set. Second, it is the worst case when the two point sets completely overlap, and the EARLYBREAK method degenerates into a violent method to calculate the Hausdorff distance. Third, the EARLYBREAK method can only obtain accurate Hausdorff distance for regularized point set data, such as images and voxel data, while scattered point cloud data can only obtain approximate solutions, because the application of The EARLYBREAK method to calculate the Hausdorff distance needs to convert the point cloud data into regularized data first.

Contents of the invention

The present invention solves the above-mentioned technical problems. Aiming at the problem of accurate Hausdorff calculation between arbitrary point sets, the present invention utilizes the spatial locality characteristics of data and proposes an accurate Hausdorff calculation for any type of point set based on local search. distance calculation method.

The technical scheme adopted in the present invention is: a method for calculating the precise Hausdorff distance between any type of point set data, characterized in that it comprises the following steps:

Step 1: Input two point sets data A and B, and perform the following judgments;

If the point set is regularized data, then perform the following step 3; if the point set is scattered and unordered point cloud data, then perform the following step 2;

Step 2: Use the Morton curve to preprocess the scattered and unordered point set data A and B, so that the point set is regular and orderly and has good spatial locality;

Step 3: Use the local search algorithm to calculate the one-way Hausdorff distance h(A, B) and h(B, A);

Step 4: Compare the one-way Hausdorff distance h(A, B) and h(B, A), and take the maximum value as the Hausdorff distance H(A, B).

As a preference, the Morton curve is used to preprocess the scattered and disordered point set data A and B described in step 2, and its specific implementation includes the following sub-steps:

Step 2.1: Perform Morton coding on each point in the point set; for a given multi-dimensional point data coordinates, the calculation of the Morton code is to interleave the coordinate values expressed in binary for each dimension;

Step 2.2: According to the Morton code value, the radix sorting method is used to sort in ascending order of size, and the Morton curve is obtained. At this time, the point set has good spatial locality according to the order of the Morton curve.

As preferably, use the local search algorithm described in step 3 to calculate one-way Hausdorff distance h (A, B) and h (B, A) respectively, and its specific implementation includes the following sub-steps:

Step 3.1: Calculate the one-way Hausdorff distance h(A, B), define the parameter preindex and initialize it to 0, which is used to store the index position where the loop is terminated when traversing B, and this position is used as the place where the next loop search starts; Define the parameter cmax to be initialized to 0, indicating the temporary one-way Hausdorff distance; define the parameter cmin to be initialized to infinity, indicating the temporary minimum value;

Step 3.2: Set a point a in A, find h(a, B), traverse the points in B from the preindex position left and right, and calculate the European formula between point a and B[preindex+1], B[preindex-1] distance dist;

Step 3.3: compare dist with cmax, if dist<cmax, then perform the following step 3.4; if dist>=cmax, then perform the following step 3.5;

Step 3.4: If dist<cmax, then stop traversing B, jump out of the loop, assign the current index value to preindex, and assign cmin to 0, and execute the following step 3.6;

Step 3.5: If dist>=cmax, compare dist with cmin, and update the value of dist to the value of cmin when dist<cmin; then continue to traverse B in the left and right directions of preindex until you find a point smaller than cmax or all the points in B points have been traversed;

Step 3.6: Traverse the points in A in turn. After traversing all the points in A, the value of cmax is the one-way Hausdorff distance h(A, B), and obtain h(B, A) in the same way.

The beneficial effects of the present invention are: compared with the latest EAELYBREAK algorithm results, the present invention is more versatile and efficient. The invention can deal with arbitrary types of point sets, and can deal with point sets of different overlapping degrees, and at the same time greatly reduces the complexity of calculation and is easy to realize.

Description of drawings

Fig. 1 is the algorithm flowchart of the embodiment of the present invention;

Fig. 2 is the schematic diagram of Morton curve (Morton Curve) in the embodiment of the present invention;

Fig. 3 is under the non-overlapping situation of the point set in the embodiment of the present invention, the performance contrast figure of the present invention and EAELYBREAK (PAMI2015) algorithm;

Fig. 4 is a performance comparison diagram between the present invention and EAELYBREAK (PAMI2015) algorithm in the case of scattered point sets in the embodiment of the present invention.

detailed description

In order to facilitate those of ordinary skill in the art to understand and implement the present invention, the present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the implementation examples described here are only used to illustrate and explain the present invention, and are not intended to limit this invention.

Please see Fig. 1, a kind of accurate Hausdorff distance calculation method based on local search of any type of point set provided by the present invention comprises the following steps:

Step 1, input two point set data A and B, if the point set is regularized data, go to step 3, if the point set is scattered and unordered point cloud data, go to step 2;

Step 2, using Morton Curve to preprocess the scattered and unordered point set data A and B, so that the point set is regular and orderly and has good spatial locality;

Please see Fig. 2, the present embodiment uses the Morton curve preprocessing point set data to include the following steps:

In step 2.1, Morton coding is performed on each point in the point set. Given a multi-dimensional point data coordinate, its Morton code can be simply calculated as the coordinate value of each interleaved dimension expressed in binary, and the encoding process can be easily implemented in parallel by GPU.

Step 2.2 After Morton encoding is performed on the point set, the Morton code value is sorted in ascending order according to the size, and the Morton curve is obtained. At this time, the point set has good spatial locality according to the order of the Morton curve. The sorting process is a radix sort implemented in parallel using the GPU.

Step 3, use the local search algorithm to calculate the one-way Hausdorff distance h(A, B) and h(B, A); the specific implementation includes the following steps:

Step 3.1 Calculate the one-way Hausdorff distance h(A, B), define the parameter preindex and initialize it to 0, which is used to reserve the index position where the loop is terminated when traversing B, and this position can be used as the place where the next loop search starts. Define the parameter cmax to be initialized to 0, indicating the temporary one-way Hausdorff distance, and define the parameter cmin to be initialized to infinity, indicating the temporary minimum value;

Step 3.2 Set a point a in A, find h(a, B), traverse the points in B from the preindex position, and calculate the Euclidean distance dist between point a and point B[preindex];

Step 3.3 compare dist with cmax, if dist<cmax, go to step 3.4; if dist<cmax, go to step 3.5;

Step 3.4 If dist<cmax, stop traversing B, jump out of the loop, assign the current index value to preindex, and assign cmin to 0, and go to step 3.6;

Step 3.5 If dist>=cmax, compare dist with cmin, and update the value of dist to the value of cmin when dist<cmin, then continue to traverse B in the left and right direction of preindex until you find a point smaller than cmax or all points in B have been traversed;

Step 3.6 Repeat steps 3.2 and 3.3 by traversing the points in A in turn. After traversing all the points in A, the value of cmax is the one-way Hausdorff distance h(A, B), and obtain h(B) in the same way , A).

Step 4, compare the one-way Hausdorff distance h(A, B) and h(B, A), and take the maximum value as the Hausdorff distance H(A, B).

Please see Fig. 3, which is a performance comparison diagram between the present invention and the EAELYBREAK (PAMI2015) algorithm under the condition of non-overlapping point sets. The total time spent on distance calculation is much less than EAELYBREAK (PAMI2015).

Table 1

Please see Figure 4, which is a performance comparison diagram between the present invention and the EAELYBREAK (PAMI2015) algorithm in the case of a scattered point set. As shown in Table 2, the performance of the present invention in dealing with a scattered point set is better than that of EAELYBREAK (PAMI2015). It shows that the present invention is superior to the current latest technology on the problem of calculating the precise Hausdorff distance of any type of point set.

Table 2

The present invention utilizes the spatial locality of the data to reduce the points that do not contribute to the Hausdorff distance in the traversal inner loop, thereby greatly reducing the complexity of calculation. Combined with the Morton curve method, the present invention can process any type of point Collecting data is more versatile.

It should be understood that the parts not described in detail in this specification belong to the prior art.

It should be understood that the above-mentioned descriptions for the preferred embodiments are relatively detailed, and should not therefore be considered as limiting the scope of the patent protection of the present invention. Within the scope of protection, replacements or modifications can also be made, all of which fall within the protection scope of the present invention, and the scope of protection of the present invention should be based on the appended claims.

Claims (3)

1. an accurate Hausdorff distance calculation method between arbitrary type point set data, is characterized in that, comprises the following steps: Step 1: Input two point sets data A and B, and perform the following judgments; If the point set is regularized data, then perform the following step 3; if the point set is scattered and unordered point cloud data, then perform the following step 2; Step 2: Use the Morton curve to preprocess the scattered and unordered point set data A and B, so that the point set is regular and orderly and has good spatial locality; Step 3: Use the local search algorithm to calculate the one-way Hausdorff distance h(A, B) and h(B, A); Step 4: Compare the one-way Hausdorff distance h(A, B) and h(B, A), and take the maximum value as the Hausdorff distance H(A, B). 2. according to the accurate Hausdorff distance calculating method between arbitrary type point set data described in claim 1, it is characterized in that, described in step 2 adopts Morton curve preprocessing scattered and unordered point set data A and B, its specific implementation includes the following sub-steps: Step 2.1: Perform Morton coding on each point in the point set; for a given multi-dimensional point data coordinates, the calculation of the Morton code is to interleave the coordinate values expressed in binary for each dimension; Step 2.2: According to the Morton code value, the radix sorting method is used to sort in ascending order of size, and the Morton curve is obtained. At this time, the point set has good spatial locality according to the order of the Morton curve. 3. according to the accurate Hausdorff distance calculating method between arbitrary type point set data described in claim 1, it is characterized in that, use local search algorithm described in step 3 to calculate one-way Hausdorff distance respectively h(A, B) and h(B, A), its specific implementation includes the following sub-steps: Step 3.1: Calculate the one-way Hausdorff distance h(A, B), define the parameter preindex and initialize it to 0, which is used to store the index position where the loop is terminated when traversing B, and this position is used as the place where the next loop search starts; Define the parameter cmax to be initialized to 0, indicating the temporary one-way Hausdorff distance; define the parameter cmin to be initialized to infinity, indicating the temporary minimum value; Step 3.2: Set a point a in A, find h(a, B), traverse the points in B from the preindex position left and right, and calculate the European formula between point a and B[preindex+1], B[preindex-1] distance dist; Step 3.3: compare dist with cmax, if dist<cmax, then execute the following step 3.4; if dist>=cmax, then execute the following step 3.5; Step 3.4: If dist<cmax, then stop traversing B, jump out of the loop, assign the current index value to preindex, and assign cmin to 0, and execute the following step 3.6; Step 3.5: If dist>=cmax, compare dist with cmin, and update the value of dist to the value of cmin when dist<cmin; then continue to traverse B in the left and right direction of preindex until you find a point smaller than cmax or all the points in B points have been traversed; Step 3.6: Traverse the points in A in turn. After traversing all the points in A, the value of cmax is the one-way Hausdorff distance h(A, B), and obtain h(B, A) in the same way.