# US 2013/0259361 A1 · Content-based matching of videos using local spatio-temporal fingerprints

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0259361 A1
- Document ID: US20130259361A1
- Status: Published application
- Kind: A1
- Application number: 13/897,032
- Filed: 2013-05-17
- Published: 2013-10-03
- Earliest claimed: 2008-08-20
- Assignees: SRI International
- Applicants: Sri International
- Inventors: GAJINDER SINGH; MANIKA PURI; JEFFREY LUBIN; HARPREET SAWHNEY
- Web page: https://patentgrep.com/patent/US20130259361A1

## CPC

- G11B 27/28: by using information signals recorded by the same method as the main recording {(G11B27/22 takes precedence)}
- G06F 16/70: of video data
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06V 20/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames}
- G06V 20/48: {Matching video sequences}
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A computer implemented method for matching video data to a database containing a plurality of video fingerprints of the type described above, comprising the steps of calculating at least one fingerprint representing at least one query frame from the video data; indexing into the database using the at least one calculated fingerprint to find a set of candidate fingerprints; applying a score to each of the candidate fingerprints; selecting a subset of candidate fingerprints as proposed frames by rank ordering the candidate fingerprints; and attempting to match at least one fingerprint of at least one proposed frame.

## Claims

### Claim 1

A computer implemented method for deriving a fingerprint from video data, comprising the steps of:
receiving a plurality of frames from the video data;
selecting at least one key frame from the plurality of frames, the at least one key frame being selected from two consecutive frames of the plurality of frames that exhibiting a maximal cumulative difference in at least one spatial feature of the two consecutive frames;
detecting at least one 3D spatio-temporal feature within the at least one key frame; and
encoding a spatio-temporal fingerprint based on mean luminance of the at least one 3D spatio-temporal feature.

### Claim 2 (depends on 1)

The method of claim 1, wherein the at least one spatial feature is intensity.

### Claim 3 (depends on 1)

The method of claim 1, wherein the at least one 3D spatio-temporal feature is at least one Maximally Stable Volume (MSV).

### Claim 4 (depends on 3)

The method of claim 3, wherein the at least one MSV is based on two dimensions of length and width of at least one key frame and the third dimension is resolution.

### Claim 5 (depends on 3)

The method of claim 3, wherein the at least one MSV is based on two dimensions of length and width of at least one key frame and the third dimension is time.

### Claim 6 (depends on 3)

The method of claim 3, wherein the MSV is a volume that exhibits about a zero change in intensity for an incremental change in volume.

### Claim 7 (depends on 1)

The method of claim 1, further comprising the step of preprocessing the plurality of frames, wherein the preprocessing step further comprises the steps of:
changing the source frame rate to a predefined resampling rate;
converting each of the plurality of frames to a grey scale; and
resizing the plurality of frames to a fixed width and height.

### Claim 8 (depends on 3)

The method of claim 3, wherein the encoding step further comprises projecting an ellipse representing the at least one MSV onto a circle whose center is the origin of a local reference axis of the MSV.

### Claim 9 (depends on 8)

The method of claim 8, wherein the encoding step further comprises the steps of:
enclosing the projected ellipse by a rectangular region;
dividing the rectangular region into a plurality of rectangular blocks; and
calculating the fingerprint based on spatial and temporal differences among the blocks arranged in columns of blocks using spatial and temporal filters, respectively.

### Claim 10 (depends on 1)

The method of claim 1, further comprising the step of storing the spatio-temporal fingerprint in a lookup table (LUT).

### Claim 11 (depends on 10)

The method of claim 10, wherein the LUT associates with the spatio-temporal fingerprint:
at least one pointer to at least one video clip with at least one region having the same fingerprint value;
geometric and shape information associated with an ellipse representing the MSV projected onto the at least one key frame;
the coordinate of the center and three reference points of the key frame; and
a descriptor based on the center and the three reference points of the key frame.

### Claim 12 (depends on 11)

The method of claim 11, wherein the three points are located at the corners of a prefixed square enclosing the center of the at least one key frame transformed into the frame of reference of the MSV.

### Claim 13 (depends on 12)

The method of claim 12, wherein the descriptor is a gradient-based descriptor.

### Claim 14

An apparatus for deriving a fingerprint from video data, comprising:
a processor configured for:
receiving a plurality of frames from the video data;
selecting at least one key frame from the plurality of frames, the at least one key frame being selected from two consecutive frames of the plurality of frames that exhibiting a maximal cumulative difference in at least one spatial feature of the two consecutive frames;
detecting at least one 3D spatio-temporal feature within the at least one key frame; and
encoding a spatio-temporal fingerprint based on mean luminance of the at least one 3D spatio-temporal feature.

### Claim 15 (depends on 14)

The apparatus of claim 14, further comprising a video capturing device for generating the plurality of frames.

### Claim 16 (depends on 15)

The apparatus of claim 15, further comprising a database for storing at least the spatio-temporal fingerprint in a lookup table (LUT).

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the database is further configured for storing, in association with the at least the spatio-temporal fingerprint:
at least one pointer to at least one video clip with at least one region having the same fingerprint value;
geometric and shape information associated with an ellipse representing the MSV projected onto the at least one key frame;
the coordinate of the center and three reference points of the key frame; and
a descriptor based on the center and the three reference points of the key frame.

### Claim 18 (depends on 16)

The apparatus of claim 16, further comprising a Web crawler for locating at least one video located on the Internet having a fingerprint which matches the at least the spatio-temporal fingerprint.

### Claim 19

A computer-readable medium carrying one or more sequences for deriving a fingerprint from video data, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:
receiving a plurality of frames from the video data;
selecting at least one key frame from the plurality of frames, the at least one key frame being selected from two consecutive frames of the plurality of frames that exhibiting a maximal cumulative difference in at least one spatial feature of the two consecutive frames;
detecting at least one 3D spatio-temporal feature within the at least one key frame; and
encoding a spatio-temporal fingerprint based on mean luminance of the at least one 3D spatio-temporal feature.

### Claim 20

An apparatus for matching a video data to a database containing a plurality of video fingerprints, comprising:
a database containing video fingerprints; and
a processor configured for:
calculating at least one fingerprint representing at least one query frame from the video data;
indexing into the database using the at least one calculated fingerprint to find a set of candidate fingerprints;
applying a score to each of the candidate fingerprints;
selecting a subset of candidate fingerprints as proposed frames by rank ordering the candidate fingerprints; and
attempting to match at least one fingerprint of at least one proposed frame based on a comparison of gradient-based descriptors associated with the at least one query frame and the at least one proposed frame.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the at least one fingerprint representing at least one query frame and the plurality of video fingerprints are based on at least one Maximally Stable Volume (MSV) determined from at least one of the at least one query frame and the proposed frames and the mean luminance of the at least one MSV.

### Claim 22

A computer-readable medium carrying one or more sequences for matching a video data to a database containing a plurality of video fingerprints, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:
calculating at least one fingerprint representing at least one query frame from the video data;
indexing into the database using the at least one calculated fingerprint to find a set of candidate fingerprints;
applying a score to each of the candidate fingerprints;
selecting a subset of candidate fingerprints as proposed frames by rank ordering the candidate fingerprints; and
attempting to match at least one fingerprint of at least one proposed frame based on a comparison of gradient-based descriptors associated with the at least one query frame and the at least one proposed frame.

### Claim 23 (depends on 22)

The computer readable medium of claim 22, wherein the at least one fingerprint representing at least one query frame and the plurality of video fingerprints are based on at least one Maximally Stable Volume (MSV) determined from at least one of the at least one query frame and the proposed frames and the mean luminance of the at least one MSV.
