CN102200999B - A method for retrieving similarity shapes - Google Patents

Abstract

The invention discloses a similarity shape retrieval method, the steps are: ① extracting the shape contour of the input query image and the image to be retrieved in the database; ② using the inner distance shape context descriptor to compare all shapes (including the input query shape and to be retrieved shape) to represent. ③ Use the dynamic programming method to match all shapes (including the input query shape and the shape to be retrieved in the database) between pairs. ④Using the content-sensitive similarity measurement method to calculate and obtain a new similarity measurement ranking. ⑤ Obtain the result of the shape search. The present invention no longer uses the dissimilarity (distance) between pairs of shapes as the direct basis for shape retrieval, but integrates the inherent differences of shapes and utilizes the structural information in the shape similarity space to compare the original pairwise shapes. The dissimilarity (distance) between them is improved, which effectively improves the accuracy of shape retrieval.

Description

A method for retrieving similarity shapes

technical field

The invention relates to retrieving shapes, in particular to a method for retrieving similar shapes.

Background technique

Shape matching/retrieval is a very important problem in computer vision. There are many different shape matching methods, and some progress has been made in improving the matching accuracy. However, almost all of these methods focus on the similarity measurement between two shapes, trying to better measure the similarity or distance between two shapes by proposing more reasonable shape descriptors and matching algorithms. These methods are all based on a typical idea that the more similar two shapes are, the smaller the difference between them, which is usually measured by a distance function. However, this view ignores the fact that, as far as shapes are concerned, some shapes of the same type may have large differences, while some shapes of different types may have relatively small differences. This phenomenon is caused by the complexity of shapes, which may be very different due to occlusion, distortion, or non-rigid deformation between similar shapes. In other words, for similar shapes that are very different, no matter how the shape descriptor or matching algorithm is improved, it is impossible to measure and compare two shapes that are already very different, making them very similar. While this difference may not be an essential difference between the shapes, it is difficult to remove. To solve this problem, it is necessary to improve the current idea of similarity measurement based solely on the characteristics of the two shapes themselves.

"Inner distance shape context" is a very effective shape descriptor proposed in recent years. It has strong stability for non-rigid changes of the same shape. In the system of the present invention, the shape descriptor uses an inner distance shape context. The specific content of the shape context of the inner distance is in the article "ShapeClassification Using the Inner-Distance" written by HaibinLing and David W. Jacobs and published in the journal "IEEE Transactions on Pattern Analysis and Machine Intelligence" Volume 26 Issue 11 in 2007 There are details.

Dynamic programming method is a branch of operations research, which is a mathematical method to solve multi-stage decision-making process. In recent years, dynamic programming methods have been widely used in shape matching and shape retrieval. In the present invention, a dynamic programming method is used for shape matching. Regarding the application of dynamic programming methods in shape matching, the article "Shape Retrieval Based on Dynamic Programming" written by Evangelos Milios and Euripides G.M.Petrakis and published in the journal "IEEE Transactions on Image Processing" Volume 9 Issue 1 in 2000 " has a detailed introduction.

Contents of the invention

The purpose of the present invention is to provide a method for retrieving similar shapes, which can improve the accuracy of shape retrieval.

A method for retrieving similarity shapes provided by the invention comprises the following steps:

(1) Extract the shape outline of the input query image and the image to be retrieved in the database, the query image is called the query shape, and the image to be retrieved is called the shape to be retrieved;

(2) On the basis of the query shape extracted in step (1) and the shape to be retrieved, calculate the feature of each shape outline, that is, the descriptor;

(3) On the basis of the shape features calculated in step (2), for the shape set composed of the input query shape and the shape to be retrieved in the database, match any two shapes in the set to obtain According to the dissimilarity measure value between two pairs, a dissimilarity measure matrix is formed according to these dissimilarity measure values;

(4) Calculate the similarity between the query shape and any shape to be retrieved in the database according to the dissimilarity measurement matrix obtained in step (3);

(5) Determine the retrieval output result based on the similarity between the input query shape obtained in step (4) and all the shapes to be retrieved in the database.

The present invention has the following properties: (1) instead of the previous method of only calculating the similarity of each pair of shapes, more use is made of manifolds composed of all known shapes; (2) there is no explicit learning of manifolds or Geodesics, because this calculation is relatively expensive. A better similarity is obtained by transferring the similarity of the query shape to the shape to be retrieved in the database. The effect of the present invention will be further described in the specific embodiment part.

Description of drawings

Fig. 1 is the test image example of input of the present invention;

Fig. 2 is a schematic diagram of shape contour sampling points and inner distance, (A) contour sampling point schematic diagram, (B) inner distance schematic diagram of shape, (C) inner distance schematic diagram of local shape;

Fig. 3 is a schematic diagram of an inner angle;

Fig. 4 is a schematic diagram of concentric circles with angle division and its application in contour representation;

Fig. 5 is a schematic diagram of concentric circles and inner distances divided by angles;

Fig. 6 is a schematic diagram of calculating a statistical histogram;

Fig. 7 is a schematic diagram of contour sampling points and their statistical histograms;

Fig. 8 is a system flow diagram implementing the method of the present invention;

Fig. 9 is the comparison of retrieval rate on MPEG-7 database;

Figure 10 is a comparison of the results retrieved on the MPEG-7 database;

Figure 11 is a comparison of the results of shape retrieval with local loss.

Detailed ways

The invention relates to a similar shape retrieval method and system. There is a shape database in the system, which contains several shapes, which are shapes waiting to be retrieved and outputted (hereinafter referred to as "shapes to be retrieved"). In addition, as the input of the system, there is a query shape, and the shapes to be retrieved in the database will be compared with the input query shape to determine which shapes to be retrieved are sufficiently similar to the input query shape and output as retrieval results.

The retrieval work begins with the system receiving the input query shape and ends with the system returning several result shapes obtained through retrieval.

Given a shape database, a query shape, and a shape distance function, which does not have to be a metric, the present invention learns a distance function that is formed by pairwise similarity between the query shape and the shape to be retrieved in the database The shortest path on the manifold is obtained. The present invention does not need to learn this manifold explicitly. Experiments demonstrate that the newly learned distance function is able to incorporate knowledge of intrinsic shape differences. This learning process is unsupervised.

In the method proposed by the present invention, on the basis of the shape similarity calculated by the existing shape descriptor and the shape matching algorithm, a new similarity is further calculated. Intuitively speaking, for a given shape S ₁ , even if shape S ₃ is not similar to shape S 1, if shape S ₂ similar to shape _{S 3 is} similar to S ₁ , then shape S ₁ and shape S ₃ are similar will also be high. However, even though shape _S1 and shape _S3 are very similar, if shape _S2, which is similar to shape _S3 , is not similar to shape _S1 , the similarity between shape _S1 and shape _S3 will be low. Therefore, the resulting new similarity is content-sensitive, where the content of a given shape is the shape it is similar to.

Even though the difference between shape _S1 and shape _S3 is large, but there is a shape _S2 that differs little from both of them, shape _S1 and shape _S3 are still considered similar. This case is possible for most shape distances because they do not satisfy the triangle inequality relation, that is, d(S ₁ , S ₃ )≤d(S ₁ , S ₂ )+d(S ₂ , S ₃ ) is not always established. If for some shapes S ₁ , S ₂ , S ₃ , satisfies the condition of d(S ₁ , S ₃ )>d(S ₁ , S ₂ )+d(S ₂ , S ₃ ), then the proposed The method can learn a new distance d′(S ₁ , S ₃ ) satisfying d′(S ₁ , S ₃ )≤d(S ₁ , S ₂ )+d(S ₂ , S ₃ ). Similarly, if there exists a path in distance space such that d(S ₁ , S ₃ )>d(S ₁ , S _2,1 )+...+d(S _{2, u} , S ₃ ), where u is the The number of shapes on the path, then this method obtains a new distance d′(S ₁ , S ₃ )≤d(S ₁ , S _2,1 )+...+d(S ₂ , u, S ₃ ). Since this path represents a process of minimum distortion from shape _S1 to shape _S3 , it is possible to ignore the less critical shape differences and concentrate on the more critical shape differences, thus obtaining a new distance d '. The present invention improves the correct rate of shape retrieval through this new distance measure.

Below in conjunction with accompanying drawing and example the method of the present invention is described in further detail.

As shown in Figure 8, the inventive method comprises the following steps:

(1) Extract the contours of the input query image and the image to be retrieved in the database. The input query image and the image to be retrieved in the database are both binary images. If the input query image is not a binary image, convert it to a binary image first. Conversion methods include manual labeling or image segmentation methods (for example, algorithms such as graph normalization and segmentation), etc. As shown in Figure 1, the shape shown in the figure is the input image of the present invention. From the input query image and the image to be retrieved in the database, the shape contour is obtained through the contour extraction algorithm.

The shape outline extracted from the input query image is called the query shape, and the shape outline extracted from the image to be retrieved in the database is called the shape to be retrieved. Since the shape contour contains the key information of the binary image, and the contour extraction is very easy to implement, the input query image can also be called the input query shape, the binary image database can also be called the shape database, and the images to be retrieved in the database can also be called Can be referred to as the shape to be retrieved. Later in the paper, the terms "query shape", "shape database" and "shape to be retrieved" are used respectively.

For the image to be retrieved in the database, the processing work of obtaining the corresponding shape outline from the binary image does not need to be carried out in the retrieval stage, but can be completed in advance. For the input query image, its work of extracting the shape contour can only be done in the retrieval stage.

(2) On the basis of the query shape extracted in step (1) and the shape to be retrieved, calculate the feature of each shape outline, that is, the descriptor. The present invention uses the inner distance shape context as a shape descriptor. The specific method is as follows:

(2.1) Uniformly sample each shape profile. N points are sampled on each contour, and the value of N is set according to needs in different application environments, such as N=100. As shown in Figure 2(A), the circular solid points on the outer contour of the scissors in this figure are the sampling points on the contour.

(2.2) For each sampling point p _i on each shape outline, i represents the serial number of the sampling point, i=1,...,N, described using the inner distance shape context descriptor. For a certain shape, the inner distance shape descriptors of all N sampling points on the shape contour together form the feature of this shape.

Calculate the inner distance shape context descriptor of each sampling point, the specific method is as follows:

(2.2.1) Calculate the inner distance. Defines the inner distance between sample points as the length of the shortest path connecting two sample points inside the shape. Use the shortest path algorithm to calculate the inner distance between a sampling point p _i and other sampling points on the shape boundary, the calculation method is as follows: ① first construct a graph structure, in this graph structure, each sampling point p _i is used as the graph Vertex, set any two sampling points as p ₁ and p ₂ , judge whether the edge connecting these two vertices falls inside the shape, if it falls inside the shape, then keep an edge between these two vertices connection, the edge weight is equal to the Euclidean distance between them ||p ₁ -p ₂ ||. If the edge does not fall completely inside the shape, then no edge is directly connected between the two vertices. ② Use the shortest path algorithm (such as Dijkstra's algorithm) on the entire weight graph to obtain the shortest connection between any two points, and the shortest distance is the inner distance. In Fig. 2(C) it is the shortest path segment on the local detail of the shape.

(2.2.2) Calculate the inner angle. Define the inner angle of one sampling point p ₁ relative to another sampling point p ₂ as the angle between the tangent direction of the contour sampling point p ₁ and the direction of the shortest path between p ₁ and p ₂ starting from point p ₁ . As shown in Figure 3, p ₁ and p ₂ are two sampling points on the contour, and the angle θ shown in the figure is the internal angle between p ₁ and p ₂ .

(2.2.3) Calculate the inner distance shape context descriptor. In the present invention, concentric circles with directional division are used as a tool for calculating descriptors. The so-called directional division refers to taking the tangent direction of sampling point p _i as the zero-degree angle direction, and evenly dividing the 360-degree space into G intervals, as shown in Figure 4 As shown, the center of the concentric circles is at a certain contour sampling point p _i , the radius of each concentric circle and the direction and angle division of the concentric circles depend on the specific application occasions, assuming that the zero angle direction is the tangent direction of the sampling point p _i , assuming that the angle is divided into G intervals, in this example, 360 degrees are divided into G=12 intervals, each area is 30 degrees. Assuming that there are R concentric circles, in this example R=5, then the R concentric circles and G angle intervals are combined to form (R+1)×G intervals. Then combine the inner distance and inner angle obtained by (2.2.1) and (2.2.2) to determine the (R+1)×G concentric circles of other points on the contour divided by the directional distance with the point p _i as the center distribution in the interval to obtain a statistical histogram, which is shown on the right side of Figure 7. The statistical histogram is the inner distance shape context descriptor. Its mathematical definition is:

h _i (k)=#{p _j : 1≤j≤N, j≠i, p _j -p _i ∈ bin(k)}

In the above formula, h _i represents the inner distance shape context statistical histogram of the i-th sampling point on the contour, h _i (k) represents the number of points falling in the k-th interval of the statistical histogram, and the value of k is The value range is an integer from 1 to (R+1)×G. p _i represents the i-th sampling point, which is the object described by the statistical histogram, and p _j represents any of the N sampling points on the shape outline, except for p _i , any of the other N-1 points. p _i is the center of the above-mentioned concentric circles, and p _j -p _i represents a vector pointing to p _j . bin represents the interval division obtained by the above-mentioned concentric circles with directional distance division, and bin(k) represents the kth interval. The meaning of the expression is that if the vector p _j -p _i falls in the interval bin(k), then the point p _j is considered to fall in the interval k of the statistical histogram, and the number of points in the interval k of the corresponding statistical histogram h _i (k) is incremented by 1. The symbol # indicates the meaning of accumulation.

Combined with Fig. 4 and Fig. 5 to further explain, in Fig. 4, suppose the position of the center of the circle is p _i , the position pointed by the arrow is p _j , passing through an intermediate point p _w , the length of the broken line segment starting from the center of the circle in Fig. 5 is is the inner distance, when calculating the inner distance shape context descriptor, first partially rotate the broken line segment in Figure 5 to obtain the straight line segment shown in Figure 6, and then check which distance interval the end point of the straight line segment falls in, and judge In which angle interval does the angle between the straight line segment and the tangent direction of point p _i fall (that is, the angle θ marked near the center of the circle in Figure 6) fall in which angle interval, combining the above two parts of information, finally determine which point p _j falls in interval, and then add 1 to the accumulated value of the interval on the previous basis.

The final statistical histogram is shown in Figure 7. The darker the color, the fewer points, and the lighter the color, the more points.

In the statistical histogram in FIG. 7 , the direction of the horizontal axis represents the division of angle intervals, and the direction of the vertical axis represents the division of distance intervals.

(2.3) Calculate the features of each shape profile

Repeat the process of (2.2) to calculate the inner distance shape context descriptor of each sampling point on the contour of a certain shape, so as to obtain the description of the shape. This description of the entire shape is composed of a set of statistical histograms as described in (2.2.3), and each statistical histogram is a description of a certain point on the contour of the shape. Such a set of descriptors is the shape feature mentioned above.

Repeat this process to calculate the features of the input query shape and all shapes to be retrieved in the database.

For the shape to be retrieved in the database, the calculation of its shape contour feature does not need to be carried out in the retrieval stage, but can be completed in advance. For the input query shape, the computation of its shape contour features can only be done in the retrieval stage.

(3) Shape matching

On the basis of the shape features calculated in step (2), for the shape set composed of the input query shape and the shape to be retrieved in the database, match any two shapes in the set to find the pairwise The dissimilarity measure (distance) between them.

(3.1) Matching between two shapes

The present invention uses a dynamic programming method to solve the optimal corresponding relationship of sampling points on any two shape contours and the dissimilarity measurement value (distance) between the two shapes to complete shape matching. The specific method is as follows:

Assuming that one of the shapes to be matched is A and the other is B, the contour sampling points of A and B form two sequence sets, which are respectively recorded as {p _i , i=1,...,N}, {q _j , j=1, . . . , N}.

(3.1.1) Calculate any point p _i in the sequence {p _i , i=1,..., N} and any point in the sequence {q _j , j=1,..., N} respectively The characteristic distance c(i, j) between q _j , which is defined as the distance between the statistical histogram of point p _i calculated by (2.2) and the statistical histogram of point q _j , its mathematical definition is as follows:

$\mathrm{<span\; class="notranslate">\; c</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>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; G</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}$

where h _{A, i} , h _{B, j} are statistical histograms defined in (2.2.3), subscripts A and B represent h _{A, i} (k), h _{B, j} (k) are shape A and shape The statistical histogram of B, c(i, j) represents the characteristic distance between point p _i and point q _i .

By calculating the feature distances between all points on shape A and all points on shape B, an N×N feature distance matrix {c(i, j), i=1,..., N, j=1,... ,N}:

$\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; =</span>\left(\begin{array}{ccccc}\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</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">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\end{array}\right)$

(3.1.2) Suppose two sequences {p _i , i=1, . . . , N} and {q _j , j=1, . . . , N} are aligned at points p ₁ and q ₁ . Using the dynamic programming method, the dissimilarity (distance) D1 of the two sequences is obtained, and the solution process is as follows:

① Generate an N×N empty matrix M, which is called a dynamic programming matrix.

② Initialize the marginal conditions:

M(0,0)=0;

M(i,0)=γ×i, i=1,...,N;

M(0, j)=γ×j, j=1,...,N;

These values are not included in the dynamic programming matrix M, because the row index and column index of the elements in M are integers ranging from 1 to N. γ is a scalar penalty factor set.

③ According to the order from left to right and from top to bottom, calculate the value S(i, j) of each element in the dynamic programming matrix M sequentially, i=1,..., N, j=1,... , N. Calculated as follows:

$\mathrm{<span\; class="notranslate">\; m</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>\mathrm{<span\; class="notranslate">\; min</span>}\begin{array}{}\end{array}\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; c</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>\\ \mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}\\ \mathrm{<span\; class="notranslate">\; m</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>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}\end{array}\right.$

where c(i, j) is the characteristic distance between point p _i and point q _j .

④ When the value of each element in the dynamic programming matrix is calculated, the dynamic programming method ends. The degree of dissimilarity D ₁ of two sequences = M(N, N).

(3.1.4) Repeat the process of (3.1.3), assuming that the two sequences {p _i } and {q _i } are aligned at p ₂ and q ₁ , p ₃ and q ₁ are aligned, ..... ., p _N is aligned with q ₁ , and the dissimilarity (distance) D ₂ , D ₃ , . _. .

(3.1.5) Select the smallest of the N distances obtained in steps (3.1.3) to (3.1.4) as the dissimilarity measure (distance) between shapes A and B:

D(A,B)=min(D _i ), i=1,...,N

(3.2) Matching between pairs of shapes in the shape set

For the shape set composed of the input query shape and the shape to be retrieved in the database, using the method described in step (3.1), use the dynamic programming algorithm to match any two shapes in the set to find their dissimilarity Sexual measure (distance).

Assuming that the database contains n shapes to be retrieved, n is a positive integer, and the input query shape together with n shapes in the database form a total of n+1 shapes { _xi , i=1,...,n+ 1}. According to step (3.1), the dissimilarity measure value (distance) between these n+1 shapes can be obtained respectively, and a dissimilarity measure matrix (distance matrix) {D _{i, j} , i, j =1,...,n,n+1}:

where D _i,j represents the dissimilarity measure (distance) between the i-th shape and the j-th shape. Additionally, put the input query shape in the first of these n+1 shapes, ie x ₁ .

For the n shapes to be retrieved in the database, the calculation of matching and dissimilarity measures between them does not need to be performed in the retrieval phase, but can be completed in advance. But if the input query shape is included in the two matched shapes, the matching and dissimilarity measurement work can only be done in the retrieval stage. That is to say, for the matrix D, the element values of the first row and the first column must be calculated in the retrieval stage, and other element values can be calculated in advance.

(4) Calculate the similarity between the query shape and any shape to be retrieved in the database according to the dissimilarity measure (distance) matrix obtained in step (3).

This step is to obtain the retrieval result by using the content-sensitive shape similarity measurement method, and the specific method is as follows:

(4.1) Define the relationship matrix w _{i, j} , whose calculation formula is as follows:

${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; exp</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="j"\; filenames="110426165406.png"\; state="\{\{state\}\}">j</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; )</span>$

Among them, D _{i, j} is the dissimilarity measure matrix (distance matrix) obtained in step (3.2), λ _{i, j} is a normalization parameter, and the calculation method of this normalization parameter is as follows:

λ _{i, j} = α·mean({knnd(x _i ), knnd(x _j )})

In the above formula, mean({knnd(x _i ), knnd(x _j )}) represents the average distance of the first b nearest neighbors of shape x _i and x _j . The so-called nearest neighbor distance refers to the smallest b distances among the dissimilarity measure values (distances) to the shape. The parameters b and α are determined empirically in the actual application environment, in this example b=10, α=0.27.

(4.2) Define the probability transition matrix P, which is obtained by normalizing w _{i, j} along the row direction, and the calculation formula is as follows:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\underset{\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}}}$

Wherein w _{i, j} is the above-mentioned relationship matrix.

(4.3) Define the key function f, and solve the key function through the following recursive process:

$f_{t+1}\left(x_i\right)=\underset{j=1}{\overset{\mathrm{no}+1}{\mathrm{\&Sigma;}}}{P}_{i,j}{f}_t\left(x_j\right),$ i=2,...,(n+1)

and have

f _t+1 (x ₁ )=1

Wherein P _{i, j} is the above-mentioned probability transition matrix; the recursive process needs T iterations, and the parameter T is predetermined in the actual application environment, and T=5000 in this example.

(4.4) Use the key function f obtained by the recursive iteration process of step (4.3), the result is denoted as f _T ( _xi ), i=1,..., n, n+1, and the solution result is an n+1 line A matrix with 1 column. Remove f _T (x ₁ ), and in the remaining n-row and one-column matrix, the value in the i-th row represents the similarity between the i-th shape in the database and the input query shape.

(5) Based on the similarity f _T ( _xi ) between the input query shape obtained in (4) and n shapes to be retrieved in the database, i=2,...,n,n+1, determine the retrieval Output the result.

Sort the n rows of values in f _T ( _xi ), i=2,...,n+1 from large to small, and determine the retrieval output sequence of the shapes to be retrieved in the database according to the sorted sequence. For example, if the i-th value is the largest, in the output search result, the shape i-1 will be ranked first in the search result, and so on to get the second search result, the third search result, and so on.

Instead of shape contours, the retrieval output is the original binary image in the database. As shown in Figure 10 and Figure 11.

Set a parameter l, indicating the number of image results returned by the search. That is to say, the retrieval returns the top l images in the database that have the greatest similarity with the input query image. The value of the parameter l is flexibly set by the user according to actual application requirements, in this example l=40.

Experimental results prove that the invention can improve the retrieval performance of existing shape matching methods.

Provided in table 1 on the MPEG-7CE-Shape-1 database, the present invention and the comparison of the main method published in international important periodicals and conferences in the past 10 years, the present invention has achieved 91.61% retrieval accuracy, is currently in this The highest result achieved on the database.

The results of the present invention and important methods in recent years on the Kimia99 data set are given in Table 2 and compared. The results show that the results of the method of the present invention are higher than other methods in each order.

In the specific implementation (4.1), there are two parameters b and α. Table 3 shows the retrieval accuracy that the system can achieve under different parameters. It can be seen that in the case of fine-tuning parameters, the present invention achieves the highest The retrieval accuracy can reach 92.57%.

Provided in Fig. 9 is the comparison of the retrieval rate (circle-marked curve) of directly using the inner distance shape context method on the MPEG-7 database and the retrieval rate of the method of the present invention ("*" mark curve). It can be seen that the effect of the method provided by the present invention is significantly better than that of directly using the inner distance shape context method.

What Fig. 10 provided is the result of retrieval on the MPEG-7 database, and the first column is the shape to be retrieved, and the right 10 columns are the retrieval results and the method of the present invention (even rows) directly using the inner distance shape context method (odd rows). ), the figure shows the top 10 most similar results. It can be seen that the effect of the method provided by the present invention is significantly better than that of directly using the inner distance shape context method.

Figure 11 shows the shape retrieval experiment with local loss. The first column is the image to be retrieved that lost a part, and the 10 columns on the right are the retrieval results obtained by directly using the inner distance shape context method (odd-numbered rows) and using the method of the present invention (even-numbered rows), as shown in the figure The top 10 most similar search results.

Table 1 Retrieval rate of different methods on MPEG-7 dataset (bull’s eyes)

Table 2 The retrieval results of the Kimia 99 dataset

Table 3 The retrieval rate of bull’s eye under different parameters

b=3 b=5 b=7 b=9 α＝0.1 83.9% 88.11% 89.26% 89.84% α＝0.15 84.33% 88.67% 89.66% 90.31% α＝0.2 85.77% 90.29% 91.34% 91.84% α＝0.25 88.71% 92.17% 92.57% 92.56% α＝0.3 89.69% 91.16% 91.41% 91.16% α＝0.35 89.03% 90.39% 90.30% 90.20% α＝0.4 88.74% 89.99% 89.97% 89.84%

The present invention is not limited to the above-mentioned specific embodiments, and those skilled in the art can adopt various other specific embodiments to implement the present invention according to the disclosed content of the present invention. Changes or modified designs all fall within the protection scope of the present invention.

Claims (3)

1. A method for retrieving similarity shapes, comprising the steps of: (1) Extract the shape contour of the input query image and the image to be retrieved in the database, the query image is called the query shape, and the image to be retrieved is called the shape to be retrieved; (2) Based on the query shape extracted in step (1) and the shape to be retrieved, calculate the feature of each shape outline, that is, the descriptor; (3) On the basis of the shape features calculated in step (2), for the shape set composed of the input query shape and the shape to be retrieved in the database, match any two shapes in the set to find According to the dissimilarity measure value between two pairs, a dissimilarity measure matrix is formed according to the calculated dissimilarity measure value; (4) According to the dissimilarity measurement matrix obtained in step (3), calculate the similarity between the query shape and any shape to be retrieved in the database; (5) Based on the similarity between the input query shape obtained in (4) and the n shapes to be retrieved in the database, determine the retrieval output result; Step (2) includes the following process: (2.1) Uniform sampling of each shape profile; (2.2) For each sampling point p _i on each shape contour, i represents the serial number of the sampling point, i=1,...,N, using the inner distance shape context descriptor to describe, and N represents the the number of sampling points; (2.3) Repeat the process of (2.2) to calculate the inner distance shape context descriptor of each sampling point on the outline of a certain shape, so as to obtain the description of the shape; Step (3) specifically includes the following process: (3.1) Matching between two shapes: Use the dynamic programming method to solve the best correspondence between sampling points on any two shape contours and the dissimilarity measure between the two shapes to complete the shape matching; (3.2) Matching between two shapes in the shape set, the dissimilarity metric matrix {D _i,j ,i,j=1,...,n,n+1} is obtained: For the shape set composed of the input query shape and the shape to be retrieved in the database, using the method described in step (3.1), use the dynamic programming algorithm to match any two shapes in the set to find their dissimilarity measure of sex; Assume that the database contains n shapes to be retrieved, and n is a positive integer. The input query shape and n shapes in the database form a total of n+1 shapes { _xi ,i=1,...,n+ 1}; according to step (3.1), calculate the dissimilarity measurement values between the n+1 shapes and form a dissimilarity measurement matrix {D _i,j ,i,j=1,... ,n,n+1}: ${\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\left(\begin{array}{ccccc}\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</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">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\end{array}\right)$ where D _i,j represents the dissimilarity measure between the i-th shape and the j-th shape; Step (4) specifically includes the following process: (4.1) Define the relationship matrix w _i,j , whose calculation formula is as follows: ${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; exp</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; )</span>$ Among them, D _{i, j} is the dissimilarity measure matrix obtained in step (3.2), and λ _{i, j} is the normalization parameter, and the calculation method of the normalization parameter is as follows: λ _i,j ＝α·mean({knnd(x _i ),knnd(x _j )}) In the above formula, mean({knnd(x _i ),knnd(x _j )}) represents the average distance of the first b nearest neighbor distances of shape x _i and x _j , the so-called nearest neighbor distance refers to the the smallest b distances in the dissimilarity measure; (4.2) Define the probability transition matrix P, which is obtained by normalizing w _{i, j} along the row direction, and the calculation formula is as follows: ${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{\underset{\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}}}$ (4.3) Define the key function f, and solve the key function through the following recursive process: ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</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">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$ and have f _t+1 (x ₁ )=1 Where P _i,j is the transition probability matrix mentioned above; the recursive process requires T iterations, and the parameter T is the preset number of iterations; (4.4) Use the recursive iteration process of step (4.3) to obtain the key function f, and record the result as f _T (x _i ), i=1,...,n,n+1, and the solution result is an n+1 row 1 column matrix; remove f _T (x ₁ ), and in the remaining n-row and 1-column matrix, the value of the i-th row represents the similarity between the i-th shape in the database and the input query shape. 2. The method for retrieving similarity shapes according to claim 1, wherein step (2.2) includes the following process: (2.2.1) Calculate the inner distance: define the inner distance between sampling points as the length of the shortest path connecting two sampling points inside the shape, and use the shortest path algorithm to calculate a certain sampling point p _i to other sampling points on the shape boundary the inner distance between (2.2.2) Calculate the inner angle: define the inner angle of one sampling point p ₁ relative to another sampling point p ₂ as the tangent direction of the contour sampling point p ₁ and the distance between p ₁ and p ₂ starting from point p ₁ The angle between the shortest path directions; (2.2.3) Calculate inner distance shape context descriptor: Use concentric circles with direction and distance division as a tool for calculating descriptors. The center of the concentric circles is at a certain contour sampling point p _i , assuming that the angle is divided into G intervals, and Assuming that there are R concentric circles, the R concentric circles and G angle intervals are combined to form (R+1)×G intervals; then combine the inner distance and inner distance obtained by (2.2.1) and (2.2.2) Angle, determine the distribution of other points on the contour in the (R+1)×G intervals of the concentric circles divided by the directional distance with the point p _i as the center, and obtain a statistical histogram, which is the inner distance Shape context descriptor; the so-called directional distance division means that the 360-degree space is evenly divided into G intervals with the tangent direction of the sampling point p _i as the zero-degree angle direction. 3. The method for retrieving similarity shapes according to claim 1 or 2, wherein the step (3.1) specifically includes the following process: (3.1.1) Calculate the difference between any point p _i in the sequence {p _i , i=1,...N, and any point q _j in the sequence {q _j ,j=1,...N, respectively. The characteristic distance c(i,j) between is defined as the distance between the statistical histogram of point p _i calculated by (2.2) and the statistical histogram of point q _j , and its mathematical definition is as follows: $\mathrm{<span\; class="notranslate">\; c</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>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; G</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}$ where h _{A, i} , h _{B, j} are the statistical histograms defined in step (2.2.3), subscripts A and B indicate that h _{A, i} (k), h _{B, j} (k) are shapes A and Statistical histogram of shape B, c(i,j) represents the feature distance between point p _i and point q _i ; By calculating the feature distances between all points on shape A and all points on shape B, an N×N feature distance matrix {c(i,j),i=1,...,N,j=1,... ,N}: $\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; =</span>\left(\begin{array}{ccccc}\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</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">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1,1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>& <span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>\end{array}\right)$ (3.1.2) Suppose two sequences {p _i ,i=1,...,N} and {q _j ,j,j=1,...,N} are aligned at points p ₁ and q ₁ , Using the dynamic programming method, the degree of dissimilarity between the two sequences is obtained as D ₁ , and the solution process is as follows: ① Generate an N×N empty matrix M, which is called a dynamic programming matrix; ② Initialize the marginal conditions: M(0,0)=0; M(i,0)=γ×i, i=1,...,N; M(0,j)=γ×j,j=1,...,N; γ is a set scalar penalty factor; ③ Calculate the value S(i,j) of each element in the dynamic programming matrix M in sequence from left to right and from top to bottom, i=1,...,N,j=1,... ,N, the calculation formula is as follows: $\mathrm{<span\; class="notranslate">\; m</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>\mathrm{<span\; class="notranslate">\; min</span>}\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; c</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>\\ \mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}\\ \mathrm{<span\; class="notranslate">\; m</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>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}\end{array}\right.$ Where c(i,j) is the characteristic distance between point p _i and point q _j ; ④ When the value of each element in the dynamic programming matrix is calculated, the dynamic programming method ends, and the dissimilarity degree D 1 of the two sequences is D ₁ =M(N,N); (3.1.3) Repeat the process of (3.1.2), assuming that two sequences {p _i } and {q _i } are aligned at p ₂ and q ₁ , p ₃ and q ₁ , ..., p _N Align with q ₁ , use the dynamic programming algorithm to obtain the degree of dissimilarity D ₂ , D ₃ ,..., D _N ; (3.1.4) Select the smallest of the N distances obtained in steps (3.1.2) to (3.1.3) as the dissimilarity measure between shapes A and B: D(A,B)=min(D _i ), i=1,...,N.

Images