IMAGE RECOGNITION SYSTEM AND METHOD FOR IDENTIFYING SIMILARITIES IN DIFFERENT IMAGES

• US 20140219569A1
• Filed: 02/07/2013
• Published: 08/07/2014
• Est. Priority Date: 02/07/2013
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Manson, Steven James, Trumbull, Tara L.
• Granted Patent: US 9,092,697 B2
• Time in Patent Office: Days
• US Class Current: 382/201
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

Embodiments for determining the similarity of different images are generally described herein. In some embodiments, image features of different images are converted to clusters, the clusters from each image are sorted based on one or more attributes of the clusters, and a plurality of three-point sets are generated for each image from a selected portion of the sorted clusters. Each three-point set defines a triangle. Matching triangles may be identified from the different images. The corresponding clusters of the matching triangles represent corresponding image features providing for a measure of the similarity of the two different images.

Claims

1. A method for identifying similarities in different images, the method comprising:

converting image features of the different images to clusters;

sorting the clusters based on one or more attributes of the clusters;

generating, for each of the different images, a plurality of three-point sets from a selected portion of the sorted clusters, each three-point set defining a triangle; and

identifying matching triangles from the different images, wherein corresponding clusters of the matching triangles establish whether there are similarities between the different images.

2. The method of claim 1, wherein sorting the clusters comprises sorting the clusters based on an average contrast level and size of each of the clusters, and

wherein the method further comprises selecting a predetermined number of the sorted clusters for use in generating the three-point sets.

3. The method of claim 2, wherein generating the plurality of three-point sets comprises generating nearest-neighbor triangles, and

wherein identifying matching triangles from the different images comprises identifying matching nearest-neighbor triangles.

4. The method of claim 3, wherein identifying the matching triangles from the different images comprises:

applying a sphericity algorithm to pairs of nearest-neighbor triangles from the different images to determine when corresponding triangles match,

wherein the matching triangles include nearest-neighbor triangles from the different images that have a sphericity above a predetermined threshold.

5. The method of claim 3, wherein identifying the matching triangles from the different images comprises:

applying a weighted centroid algorithm or an inscribed circle algorithm to pairs of nearest-neighbor triangles from the different images to determine when a pair of nearest-neighbor triangles matches.

6. The method of claim 2, wherein generating the plurality of three-point sets comprises considering all possible groups of three-point sets and determining matching triangles in the different images.

7. The method of claim 6, wherein determining matching triangles in the different images comprises:

applying a sphericity algorithm to pairs of triangles from the different images to determine when corresponding triangles match,

wherein the matching triangles include triangles from the different images that have a sphericity above a predetermined threshold.

8. The method of claim 1, wherein converting the image features of the different images to clusters comprises converting the different images to corresponding cluster maps comprised of a plurality of clusters, wherein each cluster corresponds to one of the clusters.

9. The method of claim 8, wherein each cluster corresponds to a region in one of the images having a high change in contrast,

wherein each cluster is selected for inclusion in one of the cluster maps based on a change in contrast between nearby pixels, and

wherein each cluster is represented by image coordinates of the cluster'"'"'s centroid, an average contrast level of the cluster and a cluster size.

10. The method of claim 9, wherein sorting the clusters comprises sorting the clusters of each of the cluster maps based on a weighting factor for each cluster,

wherein prior to sorting the clusters, the method comprises:

generating the weighting factor for each of the clusters based on the average contrast level of the cluster and the size of the cluster; and

eliminating clusters that are either larger or smaller than a predetermined size range.

11. The method of claim 10, wherein the matching triangles comprise corresponding triangles generated from corresponding cluster maps that have a sphericity above a predetermined threshold, and

wherein the method further comprises eliminating low-confidence triangles of the triangles to generate a constellation of high-confidence triangles for each cluster map.

12. The method of claim 11, wherein the sphericity is determined by a two-dimensional sphericity algorithm that comprises determining a similarity of pairs of the triangles of the cluster maps by:

inscribing a circle in a first triangle;

translating coordinates of the circle to a second triangle to generate an ellipse inscribed in the second triangle; and

determining the sphericity of the second triangle based on lengths of major and minor axes of the inscribed ellipse.

13. The method of claim 12, further comprising:

generating a constellation of high-confidence triangles from candidate corresponding clusters of the cluster maps by testing assertions of corresponding triangles; and

based on the tested assertions, either retaining or eliminating corresponding triangles from the constellation to generate a high-confidence constellation,

wherein vertices of triangles of the high-confidence constellation correspond to corresponding image locations.

14. The method of claim 1, wherein establishing whether there are similarities between the different images includes calculating an aggregate score of the similarity between the different images.

15. The method of claim 14, wherein calculating an aggregate score of the similarity between the different images includes using at least one of:

a mean sphericity value, a weighted average of sphericity values, or a mean sphericity value having disposed of sphericity values below a threshold.

16. The method of claim 1, wherein each of the different images was generated from a separate source, and wherein both images include a similar feature.

17. The method of claim 1, wherein each of the different images was obtained from the same source image, and wherein at least one of the different images was subject to any combination of the following manipulations:

rescaling, warping, distortion, skewing, cropping, rotation, mirroring, recoloring, addition of text or watermark, noise addition, a format change, steganography, and metadata changes.

18. An image-registration system for identifying similarities in different images, the system comprising one or more processors configured to:

convert image features of the different images to clusters;

sort the clusters based on one or more attributes of the clusters;

generate, for each of the different images, a plurality of three-point sets from a selected portion of the sorted clusters, each three-point set defining a triangle; and

identify matching triangles from the different images, wherein corresponding clusters of the matching triangles establish whether there are similarities between the different images.

19. The system of claim 18, further comprising a computer-readable storage device configured to store the different images,

wherein the one or more processors are configured to:

sort the clusters based on an average contrast level and size of each of the clusters; and

select a predetermined number of the sorted clusters for use in generating the three-point sets.

20. A computer-readable storage device that stores instructions for execution by one or more processors to perform operations for identifying similarities in different images, the instructions to configure the one or more processors to:

convert image features of the different images to clusters;

sort the clusters based on one or more attributes of the clusters;

generate, for each of the different images, a plurality of three-point sets from a selected portion of the sorted clusters, each three-point set defining a triangle; and

identify matching triangles from the different images, wherein corresponding clusters of the matching triangles establish whether there are similarities between the different images.