# US 10,878,280 B2 · Video content indexing and searching

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

- Number: US 10,878,280 B2
- Document ID: US10878280B2
- Status: Granted
- Kind: B2
- Application number: 16/880,391
- Filed: 2020-05-21
- Published: 2020-11-26
- Granted: 2020-12-29
- Earliest claimed: 2019-05-23
- Assignees: Webkontrol, Inc.
- Applicants: Webkontrol, Inc.
- Inventors: Pavel Koval; Olga Valigourskaia
- Web page: https://patentgrep.com/patent/US10878280B2

## CPC

- G06F 16/71: Indexing; Data structures therefor; Storage structures
- G06F 16/735: Filtering based on additional data, e.g. user or group profiles
- G06F 16/75: Clustering; Classification
- G06F 16/783: using metadata automatically derived from the content
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06F 18/2321: using statistics or function optimisation, e.g. modelling of probability density functions
- G06N 3/04: Architecture, e.g. interconnection topology
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/09: Supervised learning
- G06V 20/41: {Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items (segmenting video sequences G06V20/49)}
- 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}
- G06V 20/49: {Segmenting video sequences, i.e. computational techniques such as parsing or cutting the sequence, low-level clustering or determining units such as shots or scenes}
- G06N 3/045: Combinations of networks
- G06N 3/08: Learning methods
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A method of indexing and searching for video content is provided. For each frame of a first plurality of frames, a first global feature and a first plurality of local features may be identified. The first plurality of local features may be clustered around a first plurality of cluster centers. The first plurality of local features may be converted into a first plurality of binary signatures. An index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames may be generated. A search request associated with a second video may be received and its direct and indirect features may be identified. The identified features of the second video may be compared against the index and a candidate video may be selected as a result of the search request.

## Claims

### Claim 1

A method comprising:
dividing a decoded first video into a first plurality of frames;
discarding at least one frame from the first plurality of frames, wherein a first color histogram corresponding to the at least one frame is different from a second color histogram corresponding to a reference frame of the first plurality of frames by at least a threshold value;
for each remaining frame of the first plurality of frames in the first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 2 (depends on 1)

The method of claim 1, wherein the dividing the first video into the first plurality of frames comprises applying a filter to the first plurality of frames to suppress noise.

### Claim 3 (depends on 2)

The method of claim 2, wherein the filter comprises at least a Gaussian blur filter.

### Claim 4 (depends on 2)

The method of claim 2, wherein the dividing the first video into the first plurality of frames comprises rejecting an edge area of a frame in the first plurality of frames, wherein the edge area has a brightness value below a threshold.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first global feature, for each remaining frame of the first plurality of frames in the first video, is identified by using a convoluted neural network.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first global feature comprises vectors that uniquely identify each frame of the first plurality of frames in the first video.

### Claim 7 (depends on 1)

The method of claim 1, wherein the first plurality of local features comprise at least a color feature or a gradient.

### Claim 8 (depends on 1)

The method of claim 1, wherein each of the first plurality of local features corresponds to a respective coordinate location in a corresponding frame of the first plurality of frames.

### Claim 9 (depends on 1)

The method of claim 1, wherein the index comprises a hybrid structure based on at least two of locality-sensitive hashing, a randomized k-d tree, or a hierarchical k-means tree.

### Claim 10 (depends on 1)

The method of claim 1, wherein clustering the first plurality of local features around the first plurality of cluster centers comprises:
identifying, among the first plurality of local features, a subset of local features having descriptors that are proximate to each other above a threshold, and
identifying a cluster center that is a coordinate-wise mean of the descriptors of the subset of local features.

### Claim 11 (depends on 1)

The method of claim 1, wherein converting the first plurality of local features into the first plurality of binary signatures comprises:
projecting first descriptors of the first plurality of local features onto second descriptors by using a projection matrix, wherein each of the second descriptors has a smaller dimension than a corresponding descriptor of the first descriptors,
selecting a median value of the second descriptors, and
performing coordinate-wise binarization of a vector difference between the second descriptors and the median value.

### Claim 12 (depends on 1)

The method of claim 1, wherein each of the first plurality of binary signatures comprises a locality-sensitive hash of a position of a corresponding local feature, relative to a corresponding cluster center of the first plurality of cluster centers.

### Claim 13 (depends on 1)

The method of claim 1, wherein the frame in the second video is a key frame.

### Claim 14 (depends on 1)

The method of claim 1, wherein the second cluster center is identified using a bag-of-words model.

### Claim 15 (depends on 1)

The method of claim 1, wherein selecting the candidate video comprises:
identifying, from the index and based on the second cluster center and the second plurality of binary signatures, a plurality of candidate videos for the frame in the second video;
ranking the plurality of candidate videos in relation to the frame in the second video;
removing, from the plurality of candidate videos, at least one candidate video that does not satisfy a threshold condition;
assigning votes to the plurality of candidate videos based on histogram cells associated with the plurality of candidate videos in relation to the frame of the second video; and
selecting, among the plurality of candidate videos, the candidate video that has a highest vote.

### Claim 16 (depends on 15)

The method of claim 15, wherein the plurality of candidate videos are identified using a nearest neighbor search.

### Claim 17

A system comprising:
a processor; and
memory storing instructions which, when executed by the processor, cause the system to perform operations comprising:
dividing a decoded first video into a first plurality of frames;
discarding at least one frame from the first plurality of frames, wherein a first color histogram corresponding to the at least one frame is different from a second color histogram corresponding to a reference frame of the first plurality of frames by at least a threshold value;
for each remaining frame of the first plurality of frames in the first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 18

A non-transitory computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform operations comprising:
dividing a decoded first video into a first plurality of frames;
discarding at least one frame from the first plurality of frames, wherein a first color histogram corresponding to the at least one frame is different from a second color histogram corresponding to a reference frame of the first plurality of frames by at least a threshold value;
for each remaining frame of the first plurality of frames in the first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 19

A method comprising:
dividing a decoded first video into a first plurality of frames;
applying a filter to the first plurality of frames to reject an edge area of a frame in the first plurality of frames, wherein the edge area has a brightness value below a threshold;
for each frame of the first plurality of frames in the first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 20

A method comprising:
for each frame of a first plurality of frames in a first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers, wherein the clustering comprises:
identifying, among the first plurality of local features, a subset of local features having descriptors that are proximate to each other above a threshold, and
identifying a cluster center that is a coordinate-wise mean of the descriptors of the subset of local features;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 21

A method comprising:
for each frame of a first plurality of frames in a first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures, wherein the converting comprises:
projecting first descriptors of the first plurality of local features onto second descriptors by using a projection matrix, wherein each of the second descriptors has a smaller dimension than a corresponding descriptor of the first descriptors,
selecting a median value of the second descriptors, and
performing coordinate-wise binarization of a vector difference between the second descriptors and the median value;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video.

### Claim 22

A method comprising:
for each frame of a first plurality of frames in a first video, identifying:
a first global feature, and
a first plurality of local features;
clustering the first plurality of local features around a first plurality of cluster centers;
converting, based on the first plurality of cluster centers, the first plurality of local features and into a first plurality of binary signatures;
generating an index that maps the first plurality of cluster centers and the first plurality of binary signatures to the first plurality of frames;
receiving a search request associated with a second video;
identifying, for a frame in the second video, identifying a second global feature and a second plurality of local features;
identifying, for the frame in the second video and based on the second plurality of local features, a second cluster center;
converting, for the frame in the second video and based on the second cluster center, the second plurality of local features into a second plurality of binary signatures; and
selecting, from the index and based on the second cluster center and the second plurality of binary signatures, a candidate video, wherein the selecting comprises:
identifying, from the index and based on the second cluster center and the second plurality of binary signatures, a plurality of candidate videos for the frame in the second video;
ranking the plurality of candidate videos in relation to the frame in the second video;
removing, from the plurality of candidate videos, at least one candidate video that does not satisfy a threshold condition;
assigning votes to the plurality of candidate videos based on histogram cells associated with the plurality of candidate videos in relation to the frame of the second video; and
selecting, among the plurality of candidate videos, the candidate video that has a highest vote.