CN1290061C - An image retrieval method using marked edge - Google Patents

Abstract

The present invention relates to an image retrieving method using an obvious edge, which is suitable for images with clear edges. The basic concept is that edges describing image characteristics are purposefully selected, and obvious edges are used. The present invention is characterized in that firstly, edge detection and refinement are carried out to an inquired image, and an edge image is obtained; secondly, an independent edge automatic reinforcing method is used, and the obvious edges in the image are selected by repeatedly and instantly searching and reinforcing edge points in a heuristic type; thirdly, three typical characteristics, crunode rate, rotating frequency and angle-point rate are used for describing each obvious edge in order to generate the characteristic vector of the image; fourthly, the similarity degree among the images is measured by using a method of integrating obvious edge match in match; finally, sequence arrangement is carried out according to similarity to output similar image aggregate. Compared with other methods, the retrieving accuracy rate of the method is high. The obvious edges and a many-to-many matching strategy are used, and thus, the preset invention has high retrieving accuracy rate.

Description

A Method of Image Retrieval Using Salient Edges

Technical field: The present invention relates to a method for image retrieval using salient edges, which belongs to the fields of computer vision, image understanding and pattern recognition. It is suitable for images with relatively clear edges, and is designed to retrieve images whose edges are easy to obtain.

Background Art: Since the 1990s, with the rapid development of computer technology, multimedia technology and network technology, more and more images appear in people's daily life. The explosive growth of image data makes image management and retrieval critical. Currently, many image retrieval methods use shape to characterize images. Shape is one of the essential characteristics of objects. In many cases, people can recognize objects only by their shape information, which is the key to distinguishing shape from other visual features such as color and texture. The shape description methods currently applied in image retrieval can be roughly divided into two categories: image edge-based and region-based. The method based on the edge of the image uses the edge information of the object to describe and query the image. This method is suitable for images with clearer image edges and easier acquisition. The region-based method mainly relies on the color distribution information of the pixels in the region to describe the image. This type of method is more suitable for the image where the region can be segmented more accurately and the color distribution in the region is more uniform.

Researchers and technicians have proposed a variety of image retrieval methods based on image edges, but there are still many problems. Method 1: First extract the edge information, each edge is approximated by a polygon, and the vertices of the approximate polygon represent the shape information of the image. The disadvantage of this method is that it requires the edge curves to be closed, which is difficult to achieve for general images. Method 2: A shape elastic matching algorithm is used for image retrieval. First, regions of interest are manually specified. In these regions, the hill-climbing optimization algorithm is used to obtain image edges, and the edges in these regions of interest are used to represent the object shape. The advantage of this method is that the edges are screened, and the disadvantage is that it requires manual intervention, which is often not realistic in image retrieval. Method 3: Image retrieval using sketches. In their work, the image first goes through a series of processing such as scale normalization, edge detection, thinning, and then simply matches the acquired edge image with the user's sketch according to the template. Method 4: Use the corner points on the edge to describe the shape. First, perform affine transformation on the basis of the corner points, and use affine invariant features to represent the shape. Second, use the phase histogram of the edge points to characterize the image shape features. Third, a curvature scale space method is proposed to describe the shape. It performs Gaussian smoothing at different scales for each edge curve, extracts points with larger curvature at each scale, and selects the longest survival time under multiple scales. points to describe the edge curve. The common disadvantage of the above methods is that only the information of special edge points is considered, and these edge points cannot describe the shape of the object well. Method 5: An edge-based structural feature to describe the shape, which uses the "water filling _i ± (Water-Filling) algorithm to extract edge curves, and each edge curve uses some structural features such as: watering time, number of forks, forks Histogram, etc., and the shape features of the entire image are characterized by several "special" edge curves, such as: the edge with the most forks, the longest irrigation time curve, etc. The advantage of this method is that it uses the edge curve The disadvantage of using structural information rather than single edge point information to represent shapes is that only individual edge curves are used, and these edge curves are often inaccurate due to noise or errors in the edge extraction process, which will reduce the accuracy of retrieval. Method 6 : A method based on Fourier analysis. This method first obtains a characteristic function that can describe the shape, such as a curvature-based characteristic function or a radius-based characteristic function. Then perform a discrete Fourier transform on this characteristic function, and use the transformed Fourier coefficients Retrieve images as shape features. This method is quite sensitive to small changes in edge point positions and noise, so it does not achieve good results in actual retrieval. Method 7: Triangle division, first select the corner points on the edge of the image As feature points, and then use Delaunay triangles to divide, the shape features of the triangles can be recorded to describe the shape features of the image. This method is also sensitive to noise and point position changes because it is also based on some special points on the edge.

The existing methods that rely on edge information to describe the image shape and then retrieve the image have the following two main defects: First, the edge is not analyzed and selected before the edge is used to extract the shape information, and most algorithms use all the information in the image. edge. The purpose of image retrieval is to search for similar images, but in actual processing, due to the inaccuracy of edge extraction and the influence of noise, not all edges will have a positive effect on describing image shape and image matching; second, When measuring the similarity between images, a simple "one-to-one" matching strategy is adopted. The calculation of this matching strategy is quite simple, but due to the influence of noise and the inaccuracy of edge extraction, the extracted edge of the longest watering time and the edge of the most cross point are often inaccurate, which directly leads to the occurrence of false matching, thus affecting the accuracy of retrieval. Rate.

Summary of the invention: In order to avoid the defects of the prior art, the present invention systematically studies the description method of edge-based shape features and the application of shape features in image retrieval, and proposes an image retrieval method based on salient edges. Different from other methods, we believe that it can best represent the salient edges in the image where the shape should be, and design a self-enhancement algorithm with independent boundaries to extract the salient edges in the image. Then, we use three features to describe each salient edge, which in turn forms the feature vector of the image. When measuring the similarity between images, we did not use the traditional "one-to-one" matching criterion, but a "many-to-many" matching criterion. adverse effects caused. A large number of experiments prove that the method proposed by the present invention has excellent performance compared with other methods: 1. Due to the use of prominent edges, short and small edges are eliminated, and a disadvantageous factor affecting the retrieval accuracy is removed. At the same time, it also reduces the amount of calculation and improves the retrieval speed; 2. The "many-to-many" matching strategy can reduce the influence of inaccurate edges to a certain extent.

The basic idea of the present invention is to select the edges describing the features of the image, and to use salient edges. They are robust to scaling, noise, inaccurate edge extraction, etc. The salient edge refers to the edge with greater visual intensity and longer length in the image. It is characterized in that: firstly, edge detection and refinement are performed on the query image to obtain the edge map; secondly, the independent edge self-enhancement method is used to Repeated random heuristic search and enhancement to select the salient edges in the image; then, for each salient edge, use three typical features to describe, and then generate the feature vector of the image; Then, the method of comprehensive salient edge matching is used to measure the similarity between images; finally, according to the similarity sorting, a set of similar images is output.

Independent edge self-enhancement is to connect independent edge points into edge curves, and properly process the acquired edge curves to provide convenience for subsequent significant edge selection. The method is: take the edge strength information as a guide measure, obtain various possible image edges through repeated random heuristic search, and then use the accumulator to self-enhance each independent edge, so that the salient edges in the image can be obtained It has been greatly enhanced, and finally it is easy to select the significant edge by using the enhanced result. The biggest advantage of the independent boundary self-enhancement method is that the magnitude of edge enhancement is proportional to its own salient degree, so the enhanced result is more conducive to the selection of salient edges. In addition, the process of extracting edges is less affected by noise due to multiple random heuristic searches.

Since the Canny operator has good positioning and thinning performance, the edge detection in the present invention adopts the Canny operator. The image after edge detection is called an edge map (Edge map). The brightness of each point in the map represents its edge strength. The greater the brightness, the greater the edge strength, and you can find the pixel point where the gray level changes locally.

Generation of image feature vectors: For each salient edge, three typical features are used to describe the intersection rate, rotation frequency and corner rate.

Fork rate: The number of fork points on the edge curve can be a good measure of the structural complexity of the edge. Correspond each salient edge to the original edge graph, and perform "watering" along the endpoint of the salient edge, and define the number of bifurcation points as the total number of bifurcations when the water flows along the edge. Then the fork rate of this significant edge is: the total number of forks//the length of the significant edge. For a significant edge, the higher its intersection rate, the more complex its structure.

Rotation Frequency: The rotation frequency of the curve is used to describe the curvature of the edge. The rotation frequency of each salient edge is: the total number of times the edge is rotated//the length of the salient edge. The higher the frequency of rotation, the greater the curvature of this edge curve.

Corner rate: The corner frequency is used to measure the smoothness of the edge curve. The corner point is an important special point on the edge curve. The more corner points, the more severe the local change of the edge direction, and the less smooth the edge is overall. The corner rate of each salient edge is: the number of corner points//the length of the salient edge.

It is stipulated that only one corner point can exist in a small-scale curve segment, and the number of small-scale pixel points is set to 5.

After the original features of each salient edge are determined, a salient edge set of an image is obtained, and an image feature vector is also obtained.

Since the cross point rate, rotation frequency and corner point rate are used as the original features to describe the image, the curve characteristics are described from the three aspects of the structure complexity, curvature and smoothness of the curve, and the calculation is quite simple. These three original features are insensitive to translation and rotation, that is, they satisfy translation and rotation invariance. As for scale invariance, this is quite difficult to satisfy for the feature vector used for image retrieval. Since our three original features use ratios, the shape descriptor should be able to describe the image features accurately, the algorithm is simple, It should be easy to operate, and should also have the property of invariance to rotation, translation, and scaling.

In image matching, the similarity between images is generally measured by the distance between corresponding feature vectors, and finally, the set of images with the smallest distance is considered as similar images. The comprehensive salient edge matching method proposed by the present invention for image matching does not adopt the traditional "one-to-one" matching, but relaxes the strict requirements for matching. It adopts a "many-to-many" matching scheme. A salient edge of is allowed to match with multiple salient edges of another image. The specific matching strategy relies on two criteria to constrain, namely: the importance meets the criterion and the most similar first matching criterion. The final similarity between images is determined by all valid matches. The outstanding advantages of this method are: it reduces the false matching caused by inaccurate edge extraction, and can improve the retrieval accuracy to a certain extent.

Description of drawings:

Fig. 1: basic flowchart of the inventive method

Figure 2: An example of a sample query with the system

Figure 3: An example of a sample query with the system

(a) A user-drawn sketch

(b) Results retrieved from user-drawn sketches

Detailed ways:

The present invention will be further described now in conjunction with accompanying drawing:

According to the salient edge-based image retrieval method proposed by the present invention, we implemented a prototype system of image retrieval with C++ language. Currently, there are 4,500 images in our image database, including: buildings, landscapes, trademarks, icons, human faces, etc. The sources of the images are: downloading from the Internet, extraction from Corel stock photo library, digital camera shooting and Yale research Lab face database. The images in our image database are grayscale images with sharp edges.

Assuming an image Q to be queried, search for an image I similar to Q in the image database, ie: D(X _Q , X _I )≤t. In the above formula, D is the distance function of the feature vector, t is the threshold set by the user, X _Q is the feature vector of image Q, and X _I is the feature vector of image I. The similarity between two images Q and I can be expressed by the distance between their feature vectors X _Q and X _I , the smaller the distance is, the more similar the two images are. The result of the query varies with the threshold, and the distance to the image to be queried is always less than or equal to the threshold. The user can also directly request the system to output a collection of images most similar to the image to be queried, for example, output the 20 images closest to the image to be queried.

First, edge detection and refinement are performed on the image Q to obtain an edge map. Then use the independent edge self-enhancement method: that is, through repeated random heuristic search and enhancement of the edge points, the significant edges in the image are selected. Calculate the intersection rate, turning frequency and corner rate of each salient edge. Assuming a significant edge C _i , its length is l _i , and the number of bifurcation points calculated by the "watering" algorithm is f _ci . Then the cross point rate fr _i =f _ci /l _i of C _i ; the rotation frequency rf _C =rn _T /l _i , where rn _T is the total number of rotations of significant edge C _i ; when the number of its corner points is cn _i , then the inflection point rate cf _i =cn _i /l _i .

After determining the original features of each salient edge, we can get the feature vector of the image. According to the salient edge set C={c ₁ , c ₂ , ..., c _i , ..., c _v ,} of image Q, use f ₁ , f ₂ , ..., f _i ..., f _v represent the features of salient edges c ₁ , c ₂ , ..., _ci , ..., c _v respectively, then:

f ₁ =(fr ₁ ,r _f ,cf ₁ ), f ₂ =(fr ₂ ,rf ₂ ,cf ₃ ),..., f _i =(fr _i ,rf _i ,cf _i ),..., f _L = (fr _v , rf _v , cf _v )

Then, the feature vector of image Q for: ${\stackrel{\‾}{f}}_Q=[f_1,f_2,...f_i,...f_v].$

为： ${\stackrel{-}{f}}_Q=[f_1,f_2,...f_i,...f_v],$ 那么图像Q’的特征矢量f_Q’为：f_Q’＝[f₁’，f₂’，...，f_j’...，f_v]’。以对应特征矢量之间的距离来度量，最终，距离最小的图像集合认为是相似图像。For image matching, the comprehensive salient edge matching method is adopted. One salient edge of one image is allowed to match with multiple salient edges of another image in a "many-to-many" matching scheme for image matching. The feature vector of image Q

for: ${\stackrel{-}{f}}_Q=[f_1,f_2,...f_i,...f_v],$ Then the feature vector f _Q ' of the image Q' is: f _Q '=[f ₁ ', f ₂ ', . . . , f _j '..., f _v ]'. It is measured by the distance between the corresponding feature vectors, and finally, the set of images with the smallest distance is considered as similar images.

The system implemented by the present invention supports users to perform two kinds of queries: query by example and query by sketch. For example, query means that the user provides an image to be queried, and the system automatically outputs several images similar to it. The number of similar images can be specified by the user, and the range is between 0 and 100. Sketch query means that the user draws a sketch and submits it to the system for query. Similarly, the user can specify the system to output a certain number of similar images. During the query process, the user can "double-click" the output image of the system to view its size, source and other related information, and the user can also use a certain query result image as an example image to conduct a new query.

Figure 2 shows an example of a good query result of the retrieval system in this chapter. The first image in the upper left corner of the image is the query image. The one marked with "√" indicates the correct retrieval result, while the one marked with "×" indicates the wrong one. Search Results. Figure 3 shows an example of a good sketch query result of the retrieval system in this chapter. The image shown in (a) is the sketch drawn by the user, and the image in (b) is the retrieval result.

From the experimental results, it can be seen that the salient edges extracted by this method are more in line with human subjective judgment; compared with other methods, the retrieval accuracy is higher; due to the use of salient edges and the "many-to-many" matching strategy, it has a high retrieval accuracy. Accuracy.

Claims (8)

1, a kind of method of utilizing prominent edge to carry out image retrieval is characterized in that: at first query image is carried out rim detection and refinement, obtain outline map; Secondly, use the separate edge self-strengthening method,, pick out the prominent edge in the image by to marginal point heuristic search immediately and enhancing repeatedly; Then, use three characteristic features for each bar prominent edge, crunode rate, rotational frequency and angle point rate are described, and then generate the eigenvector of image; Then, the time adopt similarity degree between comprehensive prominent edge Matching Algorithm dimensioned plan picture in coupling; At last, according to sequencing of similarity, the set of output similar image.

2, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1, it is characterized in that: the separate edge self-strengthening method: the strength information with the edge is measured as guiding, heuristic search at random by repeatedly obtains various possible image borders, utilize integrator that each bar separate edge is carried out self-enhancement then, utilize the result after strengthening just to choose prominent edge easily at last.

3, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1, it is characterized in that: comprehensive prominent edge matching process, adopted the matching scheme of a kind of " multi-to-multi ", a prominent edge of piece image allows to be complementary with many edges of another width of cloth image; Concrete matching strategy relies on two criterions to retrain, that is: importance degree satisfies criterion and the most similar matching criterior at first, and similarity final between image is decided by all effective couplings.

4, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1 is characterized in that: rim detection adopts the Canny operator.

5, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1, it is characterized in that: each bar prominent edge is corresponded in the original outline map, end points along prominent edge, carry out " pouring water ", the definition bifurcated is counted and is the total degree of the time-division fork that flows along the edge when current, and then the crunode rate of this prominent edge is: the length of the total degree/prominent edge of bifurcated.

6, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1, it is characterized in that: the rotational frequency of each bar prominent edge is: this boundary curve degree of crook of the high more expression of the length of total degree/prominent edge that this edge rotates, rotational frequency is big more.

7, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 1, it is characterized in that: the angle point rate of each bar prominent edge is: the length of corner point number/prominent edge.

8, a kind of method of utilizing prominent edge to carry out image retrieval according to claim 7 is characterized in that: be defined in the segment of curve among a small circle, can only have a corner point, the number of pixel among a small circle is taken as 5.

Images