# US 10,997,459 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,997,459 B2 - Document ID: US10997459B2 - Status: Granted - Kind: B2 - Application number: 16/420,977 - Filed: 2019-05-23 - Published: 2020-11-26 - Granted: 2021-05-04 - Earliest claimed: 2019-05-23 - Assignees: Webkontrol, Inc. - Applicants: Webkontrol, Inc. - Inventors: Pavel Koval; Olga Valigourskaia - Web page: https://patentgrep.com/patent/US10997459B2 ## 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: 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, based on a similarity between a plurality of vectors in the first plurality of local features, 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 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, 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 plurality of cluster centers; converting, for the frame in the second video and based on the second plurality of cluster centers, the second plurality of local features into a second plurality of binary signatures; and selecting, from the index and based on the second plurality of cluster centers and the second plurality of binary signatures, a candidate video. ### Claim 2 (depends on 1) The method of claim 1, further comprising, prior to identifying the first global feature and the first plurality of local features for each frame of the first plurality of frames in the first video: receiving the first video; decoding the first video; and dividing the first video into the first plurality of frames. ### Claim 3 (depends on 2) The method of claim 2, wherein dividing the first video into the first plurality of frames comprises 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. ### Claim 4 (depends on 2) The method of claim 2, wherein dividing the first video into the first plurality of frames comprises applying a filter to the first plurality of frames to suppress noise. ### Claim 5 (depends on 4) The method of claim 4, wherein the filter comprises at least a Gaussian blur filter. ### Claim 6 (depends on 4) The method of claim 4, 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 7 (depends on 1) The method of claim 1, wherein the first global feature, for each frame of the first plurality of frames in the first video, is identified by using a convoluted neural network. ### Claim 8 (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 9 (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 10 (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 11 (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 12 (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 13 (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 14 (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 15 (depends on 1) The method of claim 1, wherein the candidate video is selected further based on the second plurality of local features. ### Claim 16 (depends on 1) The method of claim 1, wherein the second plurality of cluster centers are identified for a use in a bag-of-words model. ### Claim 17 (depends on 1) The method of claim 1, wherein selecting the candidate video comprises: identifying, from the index and based on the second plurality of cluster centers 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, a candidate video that has a highest vote. ### Claim 18 (depends on 17) The method of claim 17, wherein the plurality of candidate videos are identified using a nearest neighbor search. ### Claim 19 A system comprising: a processor; and memory storing instructions which, when executed by the processor, cause the system to perform operations 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, based on a similarity between a plurality of vectors in the first plurality of local features, 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 plurality of cluster centers; converting, for the frame in the second video and based on the second plurality of cluster centers, the second plurality of local features into a second plurality of binary signatures; and selecting, from the index and based on the second plurality of cluster centers and the second plurality of binary signatures, a candidate video. ### Claim 20 A non-transitory computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform operations 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, based on a similarity between a plurality of vectors in the first plurality of local features, 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 plurality of cluster centers; converting, for the frame in the second video and based on the second plurality of cluster centers, the second plurality of local features into a second plurality of binary signatures; and selecting, from the index and based on the second plurality of cluster centers and the second plurality of binary signatures, a candidate video.