US 8,913,851 B1Granted

Fingerprinting image using points of interest for robust image identification

AssigneeGoogle Inc.

InventorsDavid Marwood, Richard Tucker

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method of use are provided for generating video fingerprints that are robust to rotation, stretching, scaling, flipping and other affine transformations. The system and method are based on determining points of interest for a target video image and a collection of images stored in a database. A method of identifying a copied video image is also provided through comparison of the fingerprint of the target video image with fingerprints of images in a database. The method of video fingerprinting involves: defining points of interest from a video image, determining an oriented bounding area encompassing said points of interest that have been transformed by the same transformations used to produce the oriented bounding area and creating a fingerprint by encoding the points of interest as Gray Code such that similar images have a small Hamming distance and dissimilar images have a large Hamming distance. The identification of points of interest are provided by a number of techniques including segmentation, identification of affine covariant regions and scale invariant features.

Claims26

Dependent claims

A computer based method of image fingerprinting, comprising:

(a) determining points of interest of an image, each point of interest corresponding to a feature of the image;
(b) determining a bounding area that encompasses said points of interest;
(c) determining a transformation that transforms the bounding area to an oriented bounding area, wherein the oriented bounding area has a predetermined size, shape, and orientation, the determining (c) further comprising:
(i) rotating as necessary to align the edges of the bounding area with predetermined first and second perpendicular axes,
(ii) scaling along the first axis as necessary for a first edge of the bounding area to have a length equal to a predefined length L, and
(iii) stretching along the second axis as necessary for a second edge of the bounding area to have a length equal to the first edge of the bounding area;
(d) transforming the points of interest in accordance with the determined transformation such that the transformed points of interest are encompassed by the oriented bounding area;
(e) encoding the transformed points of interest transformed in step (d) to create a fingerprint, wherein the fingerprint can be used to identify at least a portion of the image independently of a size, shape, and orientation of the image;
and
(f) selecting the image to be a frame of a video, wherein the fingerprint can be used to identify the frame of the video.

7 more elements

A computer based system for generating image fingerprinting comprising:

a memory;
and
at least one processor coupled to the memory and configured to:
determine points of interest of an image, each point of interest corresponding to a feature of the image;
determine a bounding area that encompasses said points of interest;
determine a transformation that transforms the bounding area to an oriented bounding area by (i) rotating as necessary to align the edges of the bounding area with predetermined first and second perpendicular axes, (ii) scaling along the first axis as necessary for a first edge of the bounding area to have a length equal to a predefined length L, and (iii) stretching along the second axis as necessary for a second edge of the bounding area to have a length equal to the first edge of the bounding area, wherein the oriented bounding area has a predetermined size, shape, and orientation;
transform the points of interest in accordance with the determined transformation such that the transformed points of interest are encompassed by the oriented bounding area;
encode the transformed points of interest transformed according to the transformation determined by the bounding box generator to create a fingerprint, wherein the fingerprint can be used to identify at least a portion of the image independently of a size, shape, and orientation of the image;
and
select the image to be a frame of a video, wherein the fingerprint can be used to identify the frame of the video.

7 more elements

A method of identifying a video program, comprising:

(a) selecting a sequence of video images from the video program;
for each image in the sequence of video images:
(b) defining points of interest of an image, each point of interest corresponding to a feature of the image;
(c) determining a hounding area based on said points of interest;
(d) determining a transformation to transform the hounding area to a predetermined size, shape, and orientation, the determining (d) further comprising:
(i) rotating as necessary to align the edges of the bounding area with predetermined first and second perpendicular axes,
(ii) scaling along the first axis as necessary for a first edge of the bounding area to have a length equal to a predefined length L, and
(iii) stretching along the second axis as necessary for a second edge of the bounding area to have a length equal to the first edge of the bounding area;
(e) applying the transformation to the points of interest;
(f) encoding the points of interest transformed in step (e) to create a fingerprint corresponding to the image, wherein the fingerprint can be used to identify the image independently of a size, shape, and orientation of the image;
(g) appending the fingerprint to a sequence of fingerprints for the video program;
(h) for predetermined fingerprint sequences in a database of fingerprint sequences, determining a similarity value corresponding to a degree of similarity between a respective predetermined fingerprint sequence and the sequence of fingerprints for the video program;
and
(i) determining whether a predetermined fingerprint sequence matches the sequence of fingerprints for the video program according to the similarity value for the predetermined fingerprint sequence and the sequence of fingerprints for the video program determined in (h).

11 more elements

Dependencies are inferred from the claim text.