Matching apparatus, image search system, and histogram approximate restoring unit, and matching method, image search method, and histogram approximate restoring method

• US 8,155,451 B2
• Filed: 11/08/2005
• Issued: 04/10/2012
• Est. Priority Date: 11/12/2004
• Status: Expired due to Fees

• 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, Tsuneyoshi, Kazuyuki
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): HU, FRED H.
• Application Number:
  US11/667,565
• Publication Number:
  US 20080205756A1
• Time in Patent Office: 2,345 Days
• Field of Search: None
• US Class Current: 382/209
• 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

A matching apparatus and method compares a set of feature points of two objects projected to an N-dimensional space and determines the similarity between the objects and includes mapping the set to a one-dimensional space, creating a set of pairs of a feature point of first object that is the most approximate to a feature point of second object, 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, calculating a rating-scale of the pair belonging to the partial set of the pair of the feature points, and 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 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 a feature point of the compared object existing the most nearest to a feature point of the reference object on the one-dimensional space and creates 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 a 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 similarity between the reference object and the compared object on the basis of the rating scale, 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.

2. 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.

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

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

5. The matching apparatus according to claim 4, wherein the feature point is an edge point.

10. A non-transitory computer readable storage medium including a computer readable program enabling a computer to function as the matching apparatus according to claim 1 by reading the program to the computer and executing the program.

12. A non-transitory computer readable storage medium including a computer readable 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.

13. A non-transitory computer readable storage medium including a computer readable 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.

14. A non-transitory computer readable storage medium including a computer readable 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.

15. A non-transitory computer readable storage medium including a computer readable 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.

6. An image search system comprising:

an image database that stores compressed image data comprising a plurality of pieces of 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 reference histogram data comprising pixel value 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 degree of pixel value, L_i, of run lengths corresponding to a pixel value C_i, wherein i=1, 2, . . . , M, and 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 an 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 an appearance frequency of the pixel value of original image data by distributing the degree L_i of pixel value of the discrete histogram data corresponding to the pixel value C_i 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 a 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 compressed image data similar to the reference image on the basis of 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 coordinates of the feature point on a one-dimensional space;

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

pairing means that searches for a feature point of the candidate image that is most approximate to the feature point of the reference image on the one-dimensional space, and creates a set 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 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, 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.

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

11. A non-transitory computer readable storage medium including a computer readable program for enabling a computer to function as the image search system according to claim 6 by reading the program to the computer and executing the program.

16. A non-transitory computer readable storage medium including a computer readable program for enabling a computer to function as the image search system according to claim 7 by reading the program to the computer and executing the program.

8. A matching method for comparing a reference object with a compared object and determining similarity between both the objects, wherein the method is implementable on a computer including a processor programmed with computer readable code, the method comprising:

mapping, with the processor, 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;

searching, with the processor, 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 of the reference object and the feature point of the compared object;

creating, with the processor, a partial pair set obtained by extracting a part of the pairs in small order of a pair distance between both the feature points of a pair from among the pair set;

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

determining, with the processor, similarity between the reference image, wherein

in the step of creating, a 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

in the step of calculating, a 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.

9. An image search method of a system, the system including a computer having a processor programmed with computer readable code, comprising:

with the processor, storing compressed image data comprising a plurality of pieces of image data of a compressed image obtained by quantizing and run-length encoding pixel values of pixels of original image data in an image database; and

with the processor, storing reference histogram data comprising pixel value histogram data of a reference image in a reference-histogram storing means, 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, with the processor, discrete histogram data by calculating a total degree of pixel value, L_i, of run lengths corresponding to a pixel value C_i, where i=1, 2, . . . , M, and 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 an entire region or a specific partial region of the compressed image data from among the pixel values;

an approximate-histogram creating step of creating, with the processor, approximate histogram data approximately expressing appearance frequency of the pixel value of the original image data by distributing the degree L_i of pixel value of discrete histogram data corresponding to the pixel value C_i 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, with the processor, similarity between the approximate histogram data and the reference histogram data stored in the reference-histogram storing means;

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

a first feature-point extracting step of setting, with the processor, 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 coordinates of the feature point on a one-dimensional space;

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

a pairing step of searching, with the processor, for the feature point of the candidate image that is most approximate to the feature point of the reference image on the one-dimensional space, and creating a set 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, with the processor, a partial pair set obtained by extracting a part of the pairs in small order of a pair distance between both the feature points of the pair from among the pair set;

a rating-scale calculating step of calculating, with the processor, 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, with the processor, similarity between the reference image and the candidate image on the basis of the rating scale, wherein

in the step of creating, a 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

in the step of calculating, a 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 51 and the value S2 by the total number of pairs in the pair set, thereby calculating the rating scale.