Matching Apparatus, Image Search System, and Histogram Approximate Restoring Unit, and Matching Method, Image Search Method, and Histogram Approximate Restoring Method

• US 20080205756A1
• Filed: 11/08/2005
• Published: 08/28/2008
• Est. Priority Date: 11/12/2004
• Status: Active Grant

• Current Assignee: Kitakyushu Foundation for the Advancement of Industry, Science and Technology, Waseda University (Waseda University Educational Association)
• Original Assignee: Kitakyushu Foundation for the Advancement of Industry, Science and Technology, Waseda University (Waseda University Educational Association)
• Inventors: Kamata, Seiichiro, Tsuneycshi, Kazuyu
• Granted Patent: US 8,155,451 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

To provide a matching technology for determining the similarity between two objects at high velocity with high precision.

A matching method for comparing a set of feature points of two objects projected to an N-dimensional space and determining the similarity between the two objects, includes a mapping step (S3) of mapping the set to a one-dimensional space, a pairing step (S6) of creating a set of pairs of a feature point of first object that is the most approximate to a feature point of second object, a partial-set creating step (S7) of partly extracting the pairs in small order of the pair distance from the set of the pairs of the feature points and creating a partial set of the pairs of the feature points, an average-value calculating step (S8) of calculating a rating-scale of the pair belonging to the partial set of the pair of the feature points, and a determining step (S10) of determining the similarity between the first object and the second object on the basis of an average value of the distance.

Claims

1. A matching apparatus for comparing a reference object with a compared object and determining the similarity between both the objects, comprising:

mapping means that maps feature points extracted from the objects to a one-dimensional space by bijection for developing data elements of the objects on the one-dimensional space;

pairing means that searches for the feature point of the compared object existing the most nearest to the feature point of the reference object on the one-dimensional space and creates a set (hereinafter, referred to as a “

pair set”

) of pairs of the feature point of the reference object and the feature points of the compared object;

pair extracting means that creates a partial pair set obtained by partly extracting the pairs from the pair set in small order of the distance (hereinafter, referred to as “

pair-distance”

) between the feature points forming the pair;

rating-scale calculating means that calculates a rating scale between the reference object and the compared object on the basis of the pair distance of the pair belonging to the partial pair set; and

determining means that determines the similarity between the reference object and the compared object on the basis of the rating scale.

2. The matching apparatus according to claim 1, wherein the pair extracting means creates a partial pair set obtained by extracting the pair having the pair distance not more than a predetermined threshold from the pair set, and

the rating-scale calculating means calculates a sum S1 of the pair distance of the pair belonging to the partial pair set, further calculates a value S2 obtained by multiplying a predetermined weight value to the number of pairs non-belonging to the partial pair set, and divides a sum S1+S2 of the sum S1 and the value S2 by the total number of pairs in the pair set, thereby calculating the rating scale.

3. The matching apparatus according to claim 1, wherein the mapping means maps the feature point on a space filling curve passing through all data elements of the objects.

4. The matching apparatus according to claim 3, wherein the space filling curve is Hilbert curve.

5. The matching apparatus according to claim 1, wherein the object is an image.

6. The matching apparatus according to claims 5, wherein the feature point is an edge point.

19. A program for enabling a computer to function as the matching apparatus according to claim 1 by reading the program to the computer and executing the program.

22. A program for enabling a computer to function as the matching apparatus according to claim 2 by reading the program to the computer and executing the program.

23. A program for enabling a computer to function as the matching apparatus according to claim 3 by reading the program to the computer and executing the program.

24. A program for enabling a computer to function as the matching apparatus according to claim 4 by reading the program to the computer and executing the program.

25. A program for enabling a computer to function as the matching apparatus according to claim 5 by reading the program to the computer and executing the program.

26. A program for enabling a computer to function as the matching apparatus according to claim 6 by reading the program to the computer and executing the program.

7-11. -11. (canceled)

12. An image search system comprising:

an image database that stores a plurality of pieces of image data (hereinafter, referred to as “

compressed image data”

) of a compressed image obtained by quantizing and run-length encoding pixel values of pixels of original image data; and

reference-histogram storing means that stores pixel value histogram data (hereinafter, referred to as “

reference histogram data”

) of a reference image. The image search system searches for the compressed image data stored in the image database that is similar to the reference image from among the compressed image data,

the image search system further comprising;

discrete-histogram creating means that creates discrete histogram data by calculating a total L_i (hereinafter, referred to as a “

degree of pixel value”

) of run lengths corresponding to a pixel value C_i (i=1, 2, . . . , M;

where M is a total number of pixel values included in the compressed image data) of the compressed image data stored in the image database, at the entire region or a specific partial region of the compressed image data from among the pixel values;

approximate-histogram creating means that creates approximate histogram data approximately expressing the appearance frequency of the pixel value of the original image data by distributing the degree L_i of pixel value of the discrete histogram data corresponding to the pixel value C_i (i=1, 2, . . . , M) of the compressed image data to a degree L(x) of pixel value of a pixel value x approximate to the pixel value C_i so as to have a normal distribution of a standard deviation s with the pixel value C_i as center;

similarity calculating means that calculates the similarity between the approximate histogram data and the reference histogram data stored in the reference-histogram storing means;

image selecting means that selects one or a plurality of the image compressed data similar to the reference image on the basis of the similarity of the compressed image data;

first feature-point extracting means that sets one or a plurality of the compressed image data selected by the image selecting means as the compressed image data of a candidate image, extracts a feature point of the candidate image on the basis of the compressed image data of the candidate image, and calculates the coordinates of the feature point on the one-dimensional space;

second feature-point extracting means that extracts a feature point of the reference image and calculates the coordinates of the feature point on the one-dimensional space;

pairing means that searches for a feature point of the candidate image that is the most approximate to the feature point of the reference image on the one-dimensional space, and creates a set (hereinafter, referred to as a “

set of pairs”

) of pairs of the feature point of the reference image and of the feature point of the candidate image;

pair extracting means that creates a partial pair set obtained by extracting a part of the pairs in small order of the distance (hereinafter, referred to as a “

pair-distance”

) between both the feature points of the pair from among the pair set;

rating-scale calculating means that calculates a rating scale between the reference image and the candidate image on the basis of the pair-distance of the pair belonging to the partial pair set; and

determining means that determines the similarity between the reference image and the candidate image on the basis of the rating scale.

13. The image search system according to claim 12, wherein the similarity calculating means calculates the difference between the approximate histogram data and the reference histogram data as the similarity.

21. A program for enabling a computer to function as the image search system according to claim 12 by reading the program to the computer and executing the program.

27. A program for enabling a computer to function as the image search system according to claim 13 by reading the program to the computer and executing the program.

14. (canceled)

15. A matching method for comparing a reference object with a compared object and determining the similarity between both the objects, comprising:

a mapping step of mapping a feature point extracted from the objects by bijection for developing data elements of the objects on a one-dimensional space to the one-dimensional space;

a pairing step of searching for a feature point of the compared object that is the most approximate to a feature point of the reference object on the one-dimensional space, and creating a pair set of the feature point (hereinafter, referred to as a “

pair set”

) of the reference object and the feature point of the compared object;

a pair extracting step of creating a partial pair set obtained by extracting a part of the pairs in small order of the distance (hereinafter, referred to as a “

pair-distance”

) between both the feature points of the pair from among the pair set;

a rating-scale calculating step of calculating a rating scale between the reference image and the candidate image on the basis of the pair-distance of the pair belonging to the partial pair set; and

a determining step of determining the similarity between the reference image.

16. (canceled)

17. An image search method of a system comprising:

an image database that stores a plurality of pieces of image data (hereinafter, referred to as “

compressed image data”

) of a compressed image obtained by quantizing and run-length encoding pixel values of pixels of original image data; and

reference-histogram storing means that stores pixel value histogram data (hereinafter, referred to as “

reference histogram data”

) of a reference image, the image search method for searching for the compressed image data stored in the image database that is similar to the reference image from among the compressed image data, comprising;

a discrete-histogram creating step of creating discrete histogram data by calculating a total L_i (hereinafter, referred to as a “

degree of pixel value”

) of run lengths corresponding to a pixel value C_i (i=1, 2, . . . , M;

where M is a total number of pixel values included in the compressed image data) of the compressed image data stored in the image database, at the entire region or a specific partial region of the compressed image data from among the pixel values;

an approximate-histogram creating step of creating approximate histogram data approximately expressing the appearance frequency of the pixel value of the original image data by distributing the degree L_i of pixel value of the discrete histogram data corresponding to the pixel value C_i (i=1, 2, . . . , M) of the compressed image data to a degree L(x) of pixel value of a pixel value x approximate to the pixel value C_i so as to have a normal distribution of a standard deviation s with the pixel value C_i as center;

a similarity calculating step of calculating the similarity between the approximate histogram data and the reference histogram data stored in the reference-histogram storing means;

an image selecting step of selecting one or a plurality of the image compressed data similar to the reference image on the basis of the similarity of the compressed image data;

a first feature-point extracting step of setting one or a plurality of the compressed image data selected by the image selecting step as the compressed image data of a candidate image, extracting a feature point of the candidate image on the basis of the compressed image data of the candidate image, and calculating the coordinates of the feature point on the one-dimensional space;

a second feature-point extracting step of extracting a feature point of the reference image and calculating the coordinates of the feature point on the one-dimensional space;

a pairing step of searching for the feature point of the candidate image that is the most approximate to the feature point of the reference image on the one-dimensional space, and creating a set (hereinafter, referred to as a “

set of pairs”

) of pairs of the feature point of the reference image and of the feature point of the candidate image;

a pair extracting step of creating a partial pair set obtained by extracting a part of the pairs in small order of the distance (hereinafter, referred to as a “

pair-distance”

) between both the feature points of the pair from among the pair set;

a rating-scale calculating step of calculating a rating scale between the reference image and the candidate image on the basis of the pair-distance of the pair belonging to the partial pair set; and

a determining step of determining the similarity between the reference image and the candidate image on the basis of the rating scale.

18. (canceled)

20. (canceled)