CN102200999A - Method for retrieving similarity shape - Google Patents
Method for retrieving similarity shape Download PDFInfo
- Publication number
- CN102200999A CN102200999A CN 201110106315 CN201110106315A CN102200999A CN 102200999 A CN102200999 A CN 102200999A CN 201110106315 CN201110106315 CN 201110106315 CN 201110106315 A CN201110106315 A CN 201110106315A CN 102200999 A CN102200999 A CN 102200999A
- Authority
- CN
- China
- Prior art keywords
- shape
- distance
- retrieved
- matrix
- measure
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Image Analysis (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
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
Technical field
The present invention relates to shape is retrieved, be specifically related to a kind of method of retrieving the similarity shape.
Background technology
Form fit/retrieval is a very important problem in the computer vision.The existing different shape matching method of many kinds, and on the raising matching precision, obtained certain progress.Yet nearly all these methods all emphasis are absorbed in the similarity measurement between the shape in twos, attempt by more rational shape description of proposition and matching algorithm, thereby better measure two similarity or distances between the shape.These methods are all based on a typical viewpoint, and two shapes are similar more, and the difference between them is just more little, and this difference is measured by distance function usually.Yet this viewpoint has been ignored a fact: for shape, the difference between some similar shape may be very big, and the difference between some inhomogeneity shape may be less relatively on the contrary.This phenomenon causes by the complicacy of shape, because blocking between similar shape, distortion or nonrigid deformation etc., similar shape has very big difference.In other words, for the very big similar shape of difference,, all can not well measure with regard to two very big shapes and compare, make them very similar original difference in any case improve shape description or matching algorithm.Though this species diversity may not be the essential distinction between the shape, be difficult to eliminate.Address this problem, need improve the thinking of at present merely carrying out similarity measurement from the characteristic of two shapes itself.
" interior distance in shape hereinafter " is a kind of effectively shape description that proposes in recent years.It has stronger stability for the non-rigid variation of similar shape.In system of the present invention, distance in shape hereinafter in shape description used.In apart from the contextual particular content of shape, show, be published in 2007 periodical " IEEE Transactions onPattern Analysis and Machine Intelligence " the 26th at HaibinLing and David W.Jacobs and roll up in the article " ShapeClassification Using the Inner-Distance " on the o. 11th detailed introduction is arranged.
Dynamic programming method is a branch of operational research, is a kind of mathematical method that solves multistage decision process.In recent years, dynamic programming method has been obtained widely in form fit, shape retrieval and has been used.In the present invention, shape is mated the use dynamic programming method.The content of using in form fit about dynamic programming method, showing, be published in 2000 in the article " Shape Retrieval Based on Dynamic Programming " of periodical " IEEE Transactions on Image Processing " on the 9th the 1st phase of volume at Evangelos Milios and Euripides G.M.Petrakis has detailed introduction.
Summary of the invention
The object of the present invention is to provide a kind of method of retrieving the similarity shape, this method can improve the accuracy rate of shape retrieval.
A kind of method of retrieving the similarity shape provided by the invention comprises the steps:
(1) the shape profile of image to be retrieved in extraction input inquiry image and the database, query image is referred to as to inquire about shape, and image to be retrieved is referred to as shape to be retrieved;
(2) on the basis of inquiry shape that step (1) is extracted and shape to be retrieved, calculate the feature of each shape profile, just descriptor;
(3) on the basis of the shape facility that step (2) calculates, gather for the shape that the inquiry shape and the shape to be retrieved in the database of input are formed, mate between any two shapes in the pair set, obtain its measure of dissimilarity value between any two, form a measure of dissimilarity matrix according to these measure of dissimilarity values;
(4) the measure of dissimilarity matrix of trying to achieve according to step (3) calculates the inquiry shape with the similarity between any one shape to be retrieved in the database;
(5) follow the similarity between all shapes to be retrieved in the database based on the input inquiry shape of trying to achieve in the step (4), deterministic retrieval output result.
The present invention possesses following character: (1) only calculates each mode to the similarity of shape before having replaced, and has utilized the stream shape of being made up of known all shapes more; (2) there are not dominance ground study stream shape or geodesic line, bigger because this calculating expends.A better similarity is transmitted similarity by inquiry shape shape to be retrieved in database and is obtained.To be further described effect of the present invention in the embodiment part.
Description of drawings
Fig. 1 is the test pattern example that the present invention imports;
Fig. 2 is a shape profile sample point and interior apart from synoptic diagram, (A) configuration sampling point synoptic diagram, and (B) shape is interior apart from synoptic diagram, and (C) local shape is interior apart from synoptic diagram;
Fig. 3 is interior angle synoptic diagram;
Fig. 4 is the concentric circles of band angular divisions and the application synoptic diagram on contour representation thereof;
Fig. 5 is apart from synoptic diagram in the concentric circles of band angular divisions reaches;
Fig. 6 is a counting statistics histogram synoptic diagram;
Fig. 7 is configuration sampling point and statistic histogram synoptic diagram thereof;
Fig. 8 is a system flowchart of implementing the inventive method;
Fig. 9 is the comparison of recall ratio on the MPEG-7 database;
Figure 10 is the result's that retrieves on the MPEG-7 database comparison;
Figure 11 is that the result of the local shape retrieval of losing of band compares.
Embodiment
The present invention relates to a kind of search method and system of similar shape.A shape database is arranged in the system, comprise several shapes in this database, these shapes are to wait for the shape (being designated hereinafter simply as " shape to be retrieved ") of the output that is retrieved.In addition, as the input of system, an inquiry shape is arranged, the shape to be retrieved in the database can be respectively be carried out similarity relatively with this input inquiry shape, thereby determines which shape to be retrieved is enough similar to the input inquiry shape and export as result for retrieval.
Retrieval work receives the input inquiry shape from system, returns the SOME RESULTS shape that draws by retrieval with system and finishes.
A given shape database, an inquiry shape and a shape distance function, it needs not to be a tolerance, the present invention learns a distance function, and this distance function obtains by the shortest path on the stream shape of the similarity formation between any two of the shape to be retrieved in inquiry shape and the database.The present invention does not need this stream shape of dominance ground study.Experiment showed, that the distance function of new study can integrate the knowledge of inner shape difference.This learning process is non-supervision.
In the method that the present invention proposes, on shape similarity basis, further calculate new similarity according to existing shape description and the acquisition of form fit algorithm computation.Say intuitively, for a given shape S
1Even, shape S
3With shape S
1Dissmilarity, but if with shape S
3Similar shapes S
2Similar in appearance to S
1, shape S so
1With shape S
3Similarity also can be very high.Yet, even shape S
1With shape S
3Very similar, if but with shape S
3Similar shapes S
2With shape S
1And dissmilarity, shape S so
1With shape S
3Similarity will be very low.Therefore, the new similarity that obtains is to content erotic, and the content of given shape is exactly and its similar shapes here.
Even shape S
1With shape S
3Differ greatly, but a shape S is arranged
2All very little with their difference, still think shape S
1With shape S
3Similar.This situation is possible for most shapes distance, because they do not satisfy the relation of triangle inequality, i.e. and d (S
1, S
3)≤d (S
1, S
2)+d (S
2, S
3) be not to set up always.If to some shape S
1, S
2, S
3,, satisfy d (S
1, S
3)＞d (S
1, S
2)+d (S
2, S
3) this situation, the method for this chapter proposition can be acquired one newly apart from d ' (S so
1, S
3) satisfy d ' (S
1, S
3)≤d (S
1, S
2)+d (S
2, S
3).Equally, if in metric space, exist a paths to make d (S
1, S
3)＞d (S
1, S
2,1)+...+d (S
2, u, S
3), wherein u is the quantity of shape on this path, so this method obtain one new for d ' (S
1, S
3)≤d (S
1, S
2,1)+...+d (S
2, u, S
3).Because this paths is represented one from shape S
1To shape S
3The process of minimal distortion distortion, can ignore the shape difference that is not very crucial, and concentrate on the crucial shape difference, so just obtained one new for d '.The present invention has promoted the accuracy of shape retrieval by this new distance metric.
Below in conjunction with accompanying drawing and example the inventive method is described in further detail.
As shown in Figure 8, the inventive method comprises the steps:
(1) profile of image to be retrieved in extraction input inquiry image and the database.The query image of input and the image to be retrieved in the database all are bianry images.If the query image of input is not a bianry image, convert thereof into bianry image earlier.The method of conversion comprises artificial manual mark or image partition method (for example, figure normalization cutting scheduling algorithm) etc.As shown in Figure 1, the shape shown in the figure is an input picture of the present invention.From the query image and the image to be retrieved of database of input, obtain the shape profile by the profile extraction algorithm.
The shape profile that extracts from the query image of input is called the inquiry shape, and the shape profile that image to be retrieved extracted from database is called shape to be retrieved.Because the shape profile has comprised the key message of bianry image, profile extracts and is very easy to realize simultaneously, so the query image of input also can be described as the input inquiry shape, the binary image data storehouse also can be described as shape database, and the image to be retrieved in the database also can be described as shape to be retrieved.The back is adopted the saying of " inquiry shape ", " shape database " and " shape to be retrieved " respectively in the literary composition.
For the image to be retrieved in the database, obtain the work of treatment of corresponding shape profile from bianry image, not be used in retrieval phase and carry out, can finish in advance.For the query image of input, its work of extracting the shape profile can only be finished in retrieval phase.
(2) on the basis of inquiry shape that step (1) is extracted and shape to be retrieved, calculate the feature of each shape profile, just descriptor.Distance was in shape hereinafter as the descriptor of shape in the present invention used.Specific practice is as follows:
(2.1) each shape profile is carried out uniform sampling.N point of each profile up-sampling, the value of N are set in different applied environments as required, as N=100.See shown in Fig. 2 (A) that the circular solids point on the outline of scissors is the sampled point on the profile in the figure.
(2.2) for each the sampled point p on each shape profile
i, i represents the sequence number of sampled point, i=1 ..., N, in using distance in shape hereinafter descriptor be described.For certain shape, all N sampled point on its shape profile interior apart from shape description formed the feature of this shape jointly.
The interior distance of calculating each sampled point is descriptor hereinafter in shape, and specific practice is as follows:
(2.2.1) calculate interior distance.Interior distance between the definition sampled point is in the inner length that connects the shortest path of two sampled points of shape.Use shortest path first to calculate certain sampled point p
iInterior distance on the shape border between other sampled point, computing method are as follows: 1. at first construct a graph structure, in this graph structure, each sampled point p
iAs the summit of figure, establishing wherein any two sampled points is p
1And p
2, judge whether the limit that connects these two summits drops on the inside of shape, if drop on the inside of shape, so just between these two summits, keep the connection on a limit, the limit weight equals the Euclidean distance between them || p
1-p
2||.If the inside of shape is not dropped on this limit fully, then there is not a limit directly to link to each other between these two summits.2. use shortest path first (as enlightening Coase thorough (Dijkstra) algorithm) on whole weight map, obtain the shortest connection between any two points, this bee-line is interior distance.It in Fig. 2 (C) the shortest path line segment on the shape local detail.
(2.2.2) calculate interior angle.Define a sampled point p
1With respect to another sampled point p
2Interior angle be configuration sampling point p
1Tangential direction and from a p
1The p that sets out
1, p
2Between the shortest path direction between angle.In Fig. 3, p
1And p
2Be two sampled points on the profile, the angle θ shown in the figure is p
1And p
2Between interior angle.
(2.2.3) calculate in distance descriptor hereinafter in shape.The concentric circles that uses the division of band direction among the present invention is as the instrument that calculates descriptor, and so-called band direction is divided and is meant with sampled point p
iTangential direction be the zero angle direction, with 360 the degree spaces evenly be divided into G the interval, as shown in Figure 4, the concentrically ringed center of circle is in certain configuration sampling point p
i, each radius of a circle of concentric circles and concentrically ringed orientation angle are divided according to the concrete occasion of using and are decided, and suppose that the zero degree direction is sampled point p
iTangential direction, suppose angular divisions be G interval, use in this example be with 360 degree be divided into G=12 interval, each zone is 30 to spend.Hypothesis has R concentric circles again, R=5 in this example, and then R concentric circles and G angular interval combine and have constituted (R+1) * G interval.Then in conjunction with (2.2.1) and (2.2.2) the interior distance and the interior angle of acquisition, the point of determining on the profile other is with a p
iFor the band direction in the center of circle apart from the distribution of dividing in concentrically ringed (R+1) * G interval, obtain a statistic histogram, this histogram is seen shown in Fig. 7 right side.Distance descriptor hereinafter in shape in this statistic histogram is.Its mathematical definition is:
h
i(k)＝#{p
j：1≤j≤N，j≠i，p
j-p
i∈bin(k)}
In following formula, h
iThe interior distance of i sampled point statistic histogram hereinafter in shape on the expression profile, h
i(k) expression drops on the number of putting in k the interval of this statistic histogram, and the span of k is from 1 integer to (R+1) * G.p
iRepresent i sampled point, the object described of this statistic histogram just, p
jThen represent in N the sampled point on the shape profile, except p
iIn addition other N-1 the point in any one.p
iBe the above-mentioned concentrically ringed center of circle, p
j-p
iRepresent a vector, this vector points to p
jBin represents the interval division that the above-mentioned concentric circles with being with direction apart from division obtains, and k of bin (k) expression is interval.The implication of expression formula is if vectorial p
j-p
iDrop among the interval bin (k), then think a p
jDrop among the interval k of statistic histogram, the quantity h of the point among the interval k of corresponding statistic histogram
i(k) add 1.Symbol # represents the implication that adds up.
Explain further that in conjunction with Fig. 4, Fig. 5 in Fig. 4, the position of establishing place, the center of circle is p
i, the position of arrow points is p
j, through an intermediate point p
wLength from the broken line in the center of circle among Fig. 5 is interior distance, in calculating apart from shape hereinafter during descriptor, at first the broken line among Fig. 5 is done partial rotation and obtain the straight-line segment shown in Fig. 6, in seeing that then which distance regions this straight-line segment terminal point drops between, judge this straight-line segment and put p
iThe number of degrees of angle (being among Fig. 6) of tangential direction near angle θ that home position indicated drop in which angular interval, in conjunction with above-mentioned two parts information, finally determine a some p
jDrop in which interval, accumulated value that then should the interval adds 1 on basis before.
The final statistic histogram that obtains as shown in Figure 7, the dark more place of color is represented to count few more, the shallow more place of color is represented to count many more.
In the statistic histogram of Fig. 7, X direction is represented the angular interval division, and y direction is represented apart from interval division.
(2.3) calculate the feature of each shape profile
Repeat the process of (2.2), calculate the interior distance descriptor hereinafter in shape that obtains each sampled point on certain shape profile, thereby obtain description this shape.This description to whole shape is to form by one group of statistic histogram of describing as (2.2.3), and each statistic histogram all is the description of some points on this shape profile.Such one group of descriptor is exactly foregoing shape facility.
Repeat this process, calculate the feature that obtains all shapes to be retrieved in input inquiry shape and the database.
For the shape to be retrieved in the database, the calculating of its shape contour feature not be used in retrieval phase to be carried out, and can finish in advance.For the inquiry shape of input, the calculating of its shape contour feature can only be finished in retrieval phase.
(3) form fit
On the basis of the shape facility that step (2) calculates, gather for the shape that the inquiry shape and the shape to be retrieved in the database of input are formed, mate between any two shapes in the pair set, obtain its measure of dissimilarity value (distance) between any two.
Coupling between (3.1) two shapes
The present invention uses dynamic programming method, finds the solution the best correspondence of any two shape profile up-sampling points and the measure of dissimilarity value (distance) between this two shapes, finishes form fit.Specific practice is as follows:
Suppose that to be matched one of them is shaped as A, another one is shaped as B, forms two arrangement sets by the configuration sampling point of A and B, is designated as { p respectively
i, i=1 ..., N}, { q
j, j=1 ..., N}.
(3.1.1) the difference sequence of calculation { p
i, i=1 ..., any one the some p among the N}
iWith sequence { q
j, j=1 ..., any one the some q among the N}
jBetween characteristic distance c (i, j), this distance definition point p that (2.2) calculate that serves as reasons
iStatistic histogram with the some q
jStatistic histogram between distance, its mathematical definition is as follows:
H wherein
A, i, h
B, jBe the statistic histogram of definition in (2.2.3), subscript A and B represent h
A, i(k), h
B, j(k) be the statistic histogram of shape A and shape B respectively, c (i, j) expression point p
iWith a q
iCharacteristic distance.
By calculating the characteristic distance of being had a few on the have a few and shape B on the shape A, the characteristic distance matrix of acquisition N * N c (i, j), i=1 ..., N, j=1 ..., N}:
(3.1.2) two sequence { p of hypothesis
i, i=1 ..., N} and { q
j, j=1 ..., N} is at a p
1And q
1Place's alignment.Use dynamic programming method, try to achieve dissimilar degree (distance) D1 of two sequences, its solution procedure is as follows:
1. generate the empty matrix M of a N * N, be called the dynamic programming matrix.
2. initialization marginal condition:
M(0，0)＝0；
M(i，0)＝γ×i，i＝1，...，N；
M(0，j)＝γ×j，j＝1，...，N；
These numerical value are not included in the dynamic programming matrix M, because the scope of the line index of the element among the M and column index is from 1 to N integer.The scalar penalty factor of γ for setting.
3. according to from left to right, from top to bottom order, calculate successively each element in the dynamic programming matrix M value S (i, j), i=1 ..., N, j=1 ..., N.Computing formula is as follows:
Wherein (i j) is a p to c
iWith a q
jBetween characteristic distance.
4. the value of each element is all calculated and is finished in the dynamic programming matrix, and then dynamic programming method finishes.The dissimilar degree D of two sequences
1=M (N, N).
(3.1.4) process of repetition (3.1.3) is supposed two sequence { p respectively
iAnd { q
iAt p
2With q
1Place's alignment, p
3With q
1Place's alignment ..., p
NWith q
1Place's alignment uses dynamic programming algorithm to try to achieve dissimilar degree (distance) D respectively
2, D
3..., D
N
(3.1.5) choose minimum that in try to achieve in the step (3.1.3) to (3.1.4) N the distance, as shape A, the measure of dissimilarity value (distance) between the B:
D(A，B)＝min(D
i)，i＝1，...，N
(3.2) coupling between the shape in twos in the shape set
For the shape set of forming by the inquiry shape and the shape to be retrieved in the database of input, utilize the described method of step (3.1), any two shapes in the pair set utilize dynamic programming algorithm to mate, and obtain its measure of dissimilarity value (distance).
Contain n shape to be retrieved in the tentation data storehouse, n is a positive integer, and the n of inquiry shape in a database shape of input has been formed n+1 shape { x altogether
i, i=1 ..., n+1}.According to step (3.1), can obtain this n+1 shape measure of dissimilarity value (distance) between any two respectively, form a measure of dissimilarity matrix (distance matrix) { D
I, j, i, j=1 ..., n, n+1}:
Wherein, D
I, jRepresent the measure of dissimilarity value (distance) between i shape and j the shape.In addition, the inquiry shape with input is placed in this n+1 shape first, i.e. x
1
For the n in the database shape to be retrieved, its coupling and measure of dissimilarity between any two calculates, and not be used in retrieval phase and carries out, and can finish in advance.If but comprised the inquiry shape of input in two shapes of mating, then its coupling and measure of dissimilarity work could only be finished in retrieval phase.That is to say that for matrix D, the element value of its first row and first row must calculate in retrieval phase, but the equal calculated in advance of other element values is tried to achieve.
(4) measure of dissimilarity (distance) matrix of trying to achieve according to step (3) calculates the inquiry shape with the similarity between any one shape to be retrieved in the database.
This step just obtains result for retrieval by the shape method for measuring similarity that uses content erotic, and its specific practice is as follows:
(4.1) defining relation matrix w
I, j, its computing formula is as follows:
Wherein, D
I, jBe the dissimilar metric matrix (distance matrix) that obtains in the step (3.2), λ
I, jBe normalized parameter, the computing method of this normalized parameter are as follows:
λ
i，j＝α·mean({knnd(x
i)，knnd(x
j)})
In following formula, mean ({ knnd (x
i), knnd (x
j)) expression shape x
i, x
jThe mean distance of preceding b nearest neighbor distance.So-called nearest neighbor distance is meant and middle b the minimum distance of the measure of dissimilarity value (distance) of this shape.Parameter b and α be rule of thumb decision in actual application environment, b=10 in this example, α=0.27.
(4.2) definition probability transfer matrix P, this probability transfer matrix passes through w
I, jFollow direction normalization and obtain, computing formula is as follows:
W wherein
I, jBe above-mentioned relational matrix.
(4.3) define crucial function f, and find the solution crucial function by the process of following recurrence:
And have
f
t+1(x
1)＝1
P wherein
I, jBe above-mentioned probability transfer matrix; This recursive procedure need be passed through T iteration, and parameter T is predetermined in actual application environment, T=5000 in this example.
(4.4) the crucial function f of using the recursive iteration process of step (4.3) to obtain, result's note is made f
T(x
i), i=1 ..., n, n+1, solving result are the matrixes of capable 1 row of n+1.Remove f
T(x
1), in the matrix of capable 1 row of remaining n, i the shape in the capable value representation database of i and the similarity of input inquiry shape.
(5) follow the similarity f between the individual shape to be retrieved of n in the database based on the input inquiry shape of trying to achieve in (4)
T(x
i), i=2 ..., n, n+1, deterministic retrieval output result.
To f
T(x
i), i=2 ..., the n among the n+1 is capable, and value sorts from big to small, the order later according to ordering, the retrieval output of shape to be retrieved order in the specified data storehouse.For example, i value is maximum, Shu Chu result for retrieval then, and i-1 shape comes first of result for retrieval, obtains second result for retrieval, the 3rd result for retrieval by that analogy, or the like.
What retrieval was exported is not the shape profile, but the original bianry image in the database.As Figure 10, shown in Figure 11.
Set a parameter l, the quantity of the image result that the expression retrieval is returned.That is to say, retrieval is returned be in the database with preceding l image of input inquiry image similarity maximum.The value of parameter l is set according to the demand of practical application flexibly by the user, l=40 in this example.
The present invention of experimental result proof can improve the retrieval performance of existing shape matching method.
Provided in the present invention on the MPEG-7CE-Shape-1 database in the table 1 and be published in the comparison of the main method in international important periodical and the meeting over nearly 10 years, the present invention has obtained 91.61% retrieval precision, is the highest among the result who obtains on this database at present.
Provided the result of on Kimia99 data set the present invention and in recent years important method in the table 2 and compare, the result shows that the result of method of the present invention on each rank all is higher than additive method.
In embodiment (4.1), exist two parameter b and α, table 3 has provided the retrieval precision that system can reach under different parameters, can see, and under the situation of fine setting parameter, Supreme Procuratorate of the present invention rope precision can reach 92.57%.
What provide among Fig. 9 is the distance hereinafter comparison of the recall ratio (curve of " * " labelled notation) of the recall ratio of method (curve of circles mark) and use the inventive method in shape in directly using on the MPEG-7 database.Can see method effect that the present invention provides obviously be better than directly using in distance method hereinafter in shape.
That Figure 10 provides is the result who retrieves on the MPEG-7 database, first row are shapes to be retrieved, the right 10 row are distance result for retrieval of the result for retrieval of method (odd-numbered line) and the inventive method (even number line) hereinafter in shape in directly using, and have provided preceding 10 results the most close among the figure.Can see method effect that the present invention provides obviously be better than directly using in distance method hereinafter in shape.
What Figure 11 provided is the local shape retrieval experiment of losing of band.First classifies the image to be retrieved of having lost a part as, the right 10 row be in directly using distance in shape hereinafter method (odd-numbered line) retrieve and use the inventive method (even number line) to retrieve the result for retrieval that obtains, provided preceding 10 result for retrieval the most similar among the figure.
The recall ratio of table 1 distinct methods on the MPEG-7 data set (bull ' s eyes)
The result for retrieval of table 2Kimia 99 data sets
Bull ' the s eye recall ratio of table 3 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 not only is confined to above-mentioned embodiment; persons skilled in the art are according to content disclosed by the invention; can adopt other multiple embodiment to implement the present invention; therefore; every employing project organization of the present invention and thinking; do some simple designs that change or change, all fall into the scope of protection of the invention.
Claims (7)
1. a method of retrieving the similarity shape comprises the steps:
(1) the shape profile of image to be retrieved in extraction input inquiry image and the database, query image is referred to as to inquire about shape, and image to be retrieved is referred to as shape to be retrieved;
(2) on the basis of inquiry shape that step (1) is extracted and shape to be retrieved, calculate the feature of each shape profile, just descriptor;
(3) on the basis of the shape facility that step (2) calculates, gather for the shape that the inquiry shape and the shape to be retrieved in the database of input are formed, mate between any two shapes in the pair set, obtain its measure of dissimilarity value between any two, form the measure of dissimilarity matrix according to the measure of dissimilarity value of obtaining;
(4) the measure of dissimilarity matrix of trying to achieve according to step (3) calculates the inquiry shape with the similarity between any one shape to be retrieved in the database;
(5) follow the similarity between the individual shape to be retrieved of n in the database, deterministic retrieval output result based on the input inquiry shape of trying to achieve in (4).
2. the method for retrieval similarity shape according to claim 1 is characterized in that, step (2) comprises following process:
(2.1) each shape profile is carried out uniform sampling;
(2.2) for each the sampled point p on each shape profile
i, i represents the sequence number of sampled point, i=1 ..., N, in using distance in shape hereinafter descriptor be described, N represents the quantity of the sampled point on the shape profile;
(2.3) repeat the process of (2.2), calculate the interior distance descriptor hereinafter in shape that obtains each sampled point on certain shape profile, thereby obtain description this shape.
3. the method for retrieval similarity shape according to claim 1 is characterized in that, step (2.2) comprises following process:
(2.2.1) calculate interior distance: the interior distance between the definition sampled point is in the inner length that connects the shortest path of two sampled points of shape, uses shortest path first to calculate certain sampled point p
iInterior distance on the shape border between other sampled point;
(2.2.2) calculate interior angle: define a sampled point p
1With respect to another sampled point p
2Interior angle be configuration sampling point p
1Tangential direction and from a p
1The p that sets out
1, p
2Between the shortest path direction between angle;
(2.2.3) calculate in distance descriptor hereinafter in shape: use concentric circles that the band direction divides as the instrument that calculates descriptor, the concentrically ringed center of circle is in certain configuration sampling point p
i, suppose angular divisions be G interval, hypothesis has R concentric circles again, then R concentric circles and G angular interval combine and have constituted (R+1) * G interval; Then in conjunction with (2.2.1) and (2.2.2) the interior distance and the interior angle of acquisition, the point of determining on the profile other is with a p
iFor the band direction in the center of circle apart from the distribution of dividing in concentrically ringed (R+1) * G interval, obtains a statistic histogram, this statistic histogram is interior apart from descriptor hereinafter in shape.
4. the method for retrieval similarity shape according to claim 1 is characterized in that, step (3) specifically comprises following process:
Coupling between (3.1) two shapes:
Use dynamic programming method, find the solution the best correspondence of any two shape profile up-sampling points and the measure of dissimilarity value between this two shapes, finish form fit;
(3.2) coupling between the shape in twos in the shape set obtains dissimilar metric matrix { D
I, j, i, j=1 ..., n, n+1}:
Shape set for being made up of the inquiry shape and the shape to be retrieved in the database of input utilizes the described method of step (3.1), and any two shapes in the pair set utilize dynamic programming algorithm to mate, and obtain its measure of dissimilarity value;
Contain n shape to be retrieved in the tentation data storehouse, n is a positive integer, and the n of inquiry shape in a database shape of input has been formed n+1 shape { x altogether
i, i=1 ..., n+1}; According to step (3.1), obtain this n+1 shape measure of dissimilarity value between any two respectively, form a dissimilar metric matrix { D
I, j, i, j=1 ..., n, n+1}:
Wherein, D
I, jRepresent the measure of dissimilarity value between i shape and j the shape.
5. the method for retrieval similarity shape according to claim 3 is characterized in that, step (3) specifically comprises following process:
Coupling between (3.1) two shapes:
Use dynamic programming method, find the solution the best correspondence of any two shape profile up-sampling points and the measure of dissimilarity value between this two shapes, finish form fit;
(3.2) coupling between the shape in twos in the shape set obtains dissimilar metric matrix { D
I, j, i, j=1 ..., n, n+1}:
Shape set for being made up of the inquiry shape and the shape to be retrieved in the database of input utilizes the described method of step (3.1), and any two shapes in the pair set utilize dynamic programming algorithm to mate, and obtain its measure of dissimilarity value;
Contain n shape to be retrieved in the tentation data storehouse, n is a positive integer, and the n of inquiry shape in a database shape of input has been formed n+1 shape { x altogether
i, i=1 ..., n+1}; According to step (3.1), obtain this n+1 shape measure of dissimilarity value between any two respectively, form a dissimilar metric matrix { D
I, j, i, j=1 ..., n, n+1}:
Wherein, D
I, jRepresent the measure of dissimilarity value between i shape and j the shape.
6. the method for retrieval similarity shape according to claim 5 is characterized in that, step (3.1) specifically comprises following process:
(3.1.1) the difference sequence of calculation { p
i, i=1 ..., any one the some p among the N}
iWith sequence { q
j, j=1 ..., any one the some q among the N}
jBetween characteristic distance c (i, j), this distance definition point p that (2.2) calculate that serves as reasons
iStatistic histogram with the some q
jStatistic histogram between distance, its mathematical definition is as follows:
H wherein
A, i, h
B, jBe the statistic histogram of definition in the step (2.2.3), subscript A and B represent h
A, i(k), h
B, j(k) be the statistic histogram of shape A and shape B respectively, c (i, j) expression point p
iWith a q
iCharacteristic distance;
By calculating the characteristic distance of being had a few on the have a few and shape B on the shape A, the characteristic distance matrix of acquisition N * N c (i, j), i=1 ..., N, j=1 ..., N}:
(3.1.2) two sequence { p of hypothesis
i, i=1 ..., N} and { q
j, j=1 ..., N} is at a p
1And q
1Dynamic programming method is used in place's alignment, tries to achieve the dissimilar degree of two sequences, as D
1, its solution procedure is as follows:
1. generate the empty matrix M of a N * N, be called the dynamic programming matrix;
2. initialization marginal condition:
M(0，0)＝0；
M(i，0)＝γ×i，i＝1，...，N；
M(0，j)＝γ×j，j＝1，...，N；
The scalar penalty factor of γ for setting;
3. according to from left to right, from top to bottom order, calculate successively each element in the dynamic programming matrix M value S (i, j), i=1 ..., N, j=1 ..., N, computing formula is as follows:
Wherein (i j) is a p to c
iWith a q
jBetween characteristic distance;
4. the value of each element is all calculated and is finished in the dynamic programming matrix, and then dynamic programming method finishes, the dissimilar degree D of two sequences
1=M (N, N);
(3.1.3) process of repetition (3.1.2) is supposed two sequence { p respectively
iAnd { q
iAt p
2With q
1Place's alignment, p
3With q
1Place's alignment ..., p
NWith q
1Place's alignment uses dynamic programming algorithm to try to achieve dissimilar degree D respectively
2, D
3..., D
N
(3.1.4) choose minimum that in try to achieve in the step (3.1.2) to (3.1.3) N the distance, as shape A, the measure of dissimilarity value between the B:
D(A，B)＝min(D
i)，i＝1，...，N。
7. according to the method for arbitrary described retrieval similarity shape in the claim 1 to 6, it is characterized in that step (4) specifically comprises following process:
(4.1) defining relation matrix w
I, j, its computing formula is as follows:
Wherein, D
I, j, be the dissimilar metric matrix that obtains in the step (3.2), λ
I, jBe normalized parameter, the computing method of this normalized parameter are as follows:
λ
i，j＝α·mean({knnd(x
i)，knnd(x
j)})
In following formula, mean ({ knnd (x
i), knnd (x
j)) expression shape x
i, x
jThe mean distance of preceding b nearest neighbor distance, so-called nearest neighbor distance is meant b minimum distance in the measure of dissimilarity value with this shape;
(4.2) definition probability transfer matrix P, this probability transfer matrix passes through w
I, jFollow direction normalization and obtain, computing formula is as follows:
(4.3) define crucial function f, and find the solution crucial function by the process of following recurrence:
And have
f
t+1(x
1)＝1
P wherein
I, jBe above-mentioned transition probability matrix; This recursive procedure need be passed through T iteration, and parameter T is predefined iterations;
(4.4) use the recursive iteration process of step (4.3) to obtain crucial function f, result's note is made f
T(x
i), i=1 ..., n, n+1, solving result are the matrixes of capable 1 row of n+1; Remove f
T(x
1), in the matrix of capable 1 row of remaining n, i the shape in the capable value representation database of i and the similarity of input inquiry shape.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110106315A CN102200999B (en) | 2011-04-27 | 2011-04-27 | A method for retrieving similarity shapes |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110106315A CN102200999B (en) | 2011-04-27 | 2011-04-27 | A method for retrieving similarity shapes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102200999A true CN102200999A (en) | 2011-09-28 |
| CN102200999B CN102200999B (en) | 2012-10-10 |
Family
ID=44661674
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110106315A Expired - Fee Related CN102200999B (en) | 2011-04-27 | 2011-04-27 | A method for retrieving similarity shapes |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102200999B (en) |
Cited By (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102306202A (en) * | 2011-09-30 | 2012-01-04 | 中国传媒大学 | High-dimension vector rapid searching algorithm based on block distance |
| CN102521287A (en) * | 2011-11-28 | 2012-06-27 | 上海交通大学 | Expectation model-based image re-ranking method |
| CN103093461A (en) * | 2013-01-14 | 2013-05-08 | 大连理工大学 | Shape matching method based on measurement information |
| WO2013143222A1 (en) * | 2012-03-31 | 2013-10-03 | 中国科学技术大学 | Method and system for obtaining earthquake parameter estimates, and earthquake search engine |
| CN104299226A (en) * | 2014-09-22 | 2015-01-21 | 大冶市华兴玻璃有限公司 | Round container contour similarity retrieving method |
| CN104487961A (en) * | 2012-10-30 | 2015-04-01 | 惠普发展公司，有限责任合伙企业 | Analyzing data with computer vision |
| CN104680132A (en) * | 2015-01-30 | 2015-06-03 | 哈尔滨工程大学 | Sonar target identification method based on shape context method |
| WO2015047479A3 (en) * | 2013-09-12 | 2015-06-04 | The Boeing Company | Isotropic feature matching |
| US9239395B2 (en) | 2012-03-31 | 2016-01-19 | University Of Science And Technology Of China | Method and system of determining earthquake parameters, earthquake search engine |
| CN106682693A (en) * | 2016-12-23 | 2017-05-17 | 浙江大学 | A recognition method for overlapping images of plastic bottles |
| CN108563767A (en) * | 2018-04-19 | 2018-09-21 | 深圳市商汤科技有限公司 | Image search method and device |
| CN109426791A (en) * | 2017-09-01 | 2019-03-05 | 深圳市金溢科技股份有限公司 | A kind of polynary vehicle match method of multi-site, server and system |
| CN109685837A (en) * | 2018-11-07 | 2019-04-26 | 中国矿业大学 | A kind of heterologous remote sensing image matching method based on ground object structure similarity |
| CN113379777A (en) * | 2021-05-26 | 2021-09-10 | 西安电子科技大学 | Shape description and retrieval method based on minimum circumscribed rectangle vertical internal distance proportion |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001011563A1 (en) * | 1999-08-05 | 2001-02-15 | Koninklijke Philips Electronics N.V. | Detection of auxiliary data in an information signal |
| CN1379364A (en) * | 2001-03-29 | 2002-11-13 | 日本电气株式会社 | Graph comparing device and graph comparing method |
-
2011
- 2011-04-27 CN CN201110106315A patent/CN102200999B/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001011563A1 (en) * | 1999-08-05 | 2001-02-15 | Koninklijke Philips Electronics N.V. | Detection of auxiliary data in an information signal |
| CN1379364A (en) * | 2001-03-29 | 2002-11-13 | 日本电气株式会社 | Graph comparing device and graph comparing method |
Cited By (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102306202B (en) * | 2011-09-30 | 2013-09-04 | 中国传媒大学 | High-dimension vector rapid searching algorithm based on block distance |
| CN102306202A (en) * | 2011-09-30 | 2012-01-04 | 中国传媒大学 | High-dimension vector rapid searching algorithm based on block distance |
| CN102521287A (en) * | 2011-11-28 | 2012-06-27 | 上海交通大学 | Expectation model-based image re-ranking method |
| US9239395B2 (en) | 2012-03-31 | 2016-01-19 | University Of Science And Technology Of China | Method and system of determining earthquake parameters, earthquake search engine |
| CN103365916A (en) * | 2012-03-31 | 2013-10-23 | 中国科学技术大学 | Earthquake event parameter estimation and acquirement method and system and earthquake event search engine |
| JP2014517377A (en) * | 2012-03-31 | 2014-07-17 | 中国科学技▲術▼大学 | Method and system for obtaining an estimation of seismic event parameters, seismic event search engine |
| WO2013143222A1 (en) * | 2012-03-31 | 2013-10-03 | 中国科学技术大学 | Method and system for obtaining earthquake parameter estimates, and earthquake search engine |
| CN103365916B (en) * | 2012-03-31 | 2016-12-14 | 中国科学技术大学 | Earthquake parameter estimates acquisition methods and system, seismic events search engine |
| CN104487961A (en) * | 2012-10-30 | 2015-04-01 | 惠普发展公司，有限责任合伙企业 | Analyzing data with computer vision |
| CN104487961B (en) * | 2012-10-30 | 2018-05-18 | 企业服务发展公司有限责任合伙企业 | Analyzing Data with Computer Vision |
| CN103093461B (en) * | 2013-01-14 | 2015-11-18 | 大连理工大学 | A kind of shape matching method based on metric |
| CN103093461A (en) * | 2013-01-14 | 2013-05-08 | 大连理工大学 | Shape matching method based on measurement information |
| WO2015047479A3 (en) * | 2013-09-12 | 2015-06-04 | The Boeing Company | Isotropic feature matching |
| US9305233B2 (en) | 2013-09-12 | 2016-04-05 | The Boeing Company | Isotropic feature matching |
| CN104299226B (en) * | 2014-09-22 | 2017-07-28 | 大冶市华兴玻璃有限公司 | A kind of method of circular Bottle ＆ Can profile similarity retrieval |
| CN104299226A (en) * | 2014-09-22 | 2015-01-21 | 大冶市华兴玻璃有限公司 | Round container contour similarity retrieving method |
| CN104680132A (en) * | 2015-01-30 | 2015-06-03 | 哈尔滨工程大学 | Sonar target identification method based on shape context method |
| CN104680132B (en) * | 2015-01-30 | 2017-11-21 | 哈尔滨工程大学 | A kind of sonar target recognition methods based on Shape context method |
| CN106682693A (en) * | 2016-12-23 | 2017-05-17 | 浙江大学 | A recognition method for overlapping images of plastic bottles |
| CN109426791A (en) * | 2017-09-01 | 2019-03-05 | 深圳市金溢科技股份有限公司 | A kind of polynary vehicle match method of multi-site, server and system |
| CN108563767A (en) * | 2018-04-19 | 2018-09-21 | 深圳市商汤科技有限公司 | Image search method and device |
| US11328171B2 (en) | 2018-04-19 | 2022-05-10 | Shenzhen Sensetime Technology Co., Ltd. | Image retrieval method and apparatus |
| CN109685837A (en) * | 2018-11-07 | 2019-04-26 | 中国矿业大学 | A kind of heterologous remote sensing image matching method based on ground object structure similarity |
| CN109685837B (en) * | 2018-11-07 | 2024-03-22 | 中国矿业大学 | Heterologous remote sensing image registration method based on feature structure similarity |
| CN113379777A (en) * | 2021-05-26 | 2021-09-10 | 西安电子科技大学 | Shape description and retrieval method based on minimum circumscribed rectangle vertical internal distance proportion |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102200999B (en) | 2012-10-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102200999A (en) | Method for retrieving similarity shape | |
| Alon et al. | Adversarial laws of large numbers and optimal regret in online classification | |
| Cucuringu et al. | SPONGE: A generalized eigenproblem for clustering signed networks | |
| Chang et al. | Sparse regularization in fuzzy $ c $-means for high-dimensional data clustering | |
| Cucuringu | Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization | |
| Rayana et al. | Sequential ensemble learning for outlier detection: A bias-variance perspective | |
| Fogel et al. | Spectral ranking using seriation | |
| D’yachkov et al. | Bounds on the rate of disjunctive codes | |
| CN103838803A (en) | Social network community discovery method based on node Jaccard similarity | |
| WO2016029230A1 (en) | Automated creation of join graphs for unrelated data sets among relational databases | |
| CN105550368A (en) | Approximate nearest neighbor searching method and system of high dimensional data | |
| Ma et al. | Coronal mass ejection data clustering and visualization of decision trees | |
| Sigirci et al. | Spectral-spatial classification of hyperspectral images using bert-based methods with hyperslic segment embeddings | |
| Schlegel et al. | Visual localization and loop closing using decision trees and binary features | |
| CN107103206A (en) | The DNA sequence dna cluster of local sensitivity Hash based on standard entropy | |
| CN107480471A (en) | The method for the sequence similarity analysis being characterized based on wavelet transformation | |
| Imaduwage | Skippool: Improved sparse hierarchical graph pooling with differentiable exploration | |
| CN114510971A (en) | Association outlier knowledge based quasi-star spectrum parallelization cross-certification method | |
| Rolnick et al. | Algorithms for Tverberg's theorem via centerpoint theorems | |
| CN119761311A (en) | Medical institution name management method based on contrast learning | |
| US20200258105A1 (en) | Mutually repulsing centroids for segmenting a vast social graph | |
| CN105404892B (en) | Penicillin fermentation process stage division method based on orderly fuzzy C-means clustering | |
| Bian et al. | QSRP: Efficient Reverse $ k-\text {Ranks} $ Query Processing on High-Dimensional Embeddings | |
| CN108984601A (en) | A kind of image search method and system based on probability histogram area similarity | |
| Wu et al. | A high available and strong generalization capability data-driven-based wireless fingerprint positioning model |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20121010 |