Video retrieval based on optimized selected fingerprints

Patent metadata

Field	Value
Publication number	US-2016267178-A1
Application number	US-201514656979-A
Country	US
Kind code	A1
Filing date	Mar 13, 2015
Priority date	Mar 13, 2015
Publication date	Sep 15, 2016
Grant date	—

Abstract

A video retrieval method is provided. The method includes dividing video sequences stored in a video database into a plurality of video frames, extracting by a predetermined feature extracting algorithm a plurality of selected fingerprints from the plurality of video frames representing features having characteristic information specific to the plurality of video frames, and storing the plurality of extracted selected fingerprints in a fingerprint database. The method also includes receiving a query video sequence submitted by a user, extracting by the predetermined feature extracting algorithm at least one query fingerprint representing at least one query frame from the received query video sequence, and calculating similarity between the query fingerprint and the selected fingerprints from the fingerprint database to search for a match for the query fingerprint. Further, the method includes determining a matching fingerprint in the selected fingerprints by applying a fast dynamic programming algorithm and generating a matching result.

First claim

What is claimed is:

1 . A video retrieval method, comprising:
dividing video sequences stored in a video database into a plurality of video frames; extracting by a predetermined feature extracting algorithm a plurality of selected fingerprints from the plurality of video frames representing features having characteristic information specific to the plurality of video frames; storing the plurality of extracted selected fingerprints in a fingerprint database; receiving a query video sequence submitted by a user; extracting by the predetermined feature extracting algorithm at least one query fingerprint representing at least one query frame from the received query video sequence; calculating similarity between the query fingerprint and the selected fingerprints from the fingerprint database to search for a match for the query fingerprint; determining a matching fingerprint in the selected fingerprints by applying a fast dynamic programming algorithm; and based on the matching fingerprint, generating a matching result to be presented to the user.

2 . The method according to claim 1 , wherein determining a matching fingerprint in the selected fingerprints by applying a fast dynamic programming algorithm further includes:
analyzing a query error caused by using a limited number of the selected fingerprints to approximate an original fingerprint set; based on the plurality of fingerprints stored in the fingerprint database, building indices to generate an inverted file indexing table of fingerprints, wherein each of the plurality of fingerprints is divided into a plurality of words, and vertical and horizontal dimensions of the inverted file indexing table represent respectively possible values of a word and a position of the word in the fingerprint; based on the inverted file indexing table, matching the fingerprint of the query video with the fingerprints stored in the fingerprint database by using a voting-based matching approach; and finding a desired set of the selected fingerprints that minimizes the query error subject to a storage constraint.

3 . The method according to claim 2 , wherein matching the fingerprint of the query video and the fingerprints stored in the fingerprint database by using a voting-based matching approach further includes:
counting a total number of matched words for each of the fingerprints that have at least one matched word with the query fingerprint; identifying a matching fingerprint with a most number of matched words from the fingerprints as the matching fingerprint; and when multiple fingerprints have a same number of the matched words, performing a linear search to find one fingerprint with a largest similarity value.

4 . The method according to claim 2 , wherein finding a desired set of the selected fingerprints that minimizes the query error subject to a storage constraint further includes:
finding a single-source shortest path in a Directed Acyclic Graph (DAG), wherein all nodes are topologically ordered with each node representing one fingerprint in an original video sequence.

5 . The method according to claim 1 , wherein generating a matching result to be presented to the user further includes:
combining the matching result with additional information obtained from the fingerprint database to form a search report for the user.

6 . The method according to claim 2 , wherein:
provided that F={f i |0≦i≦n−1} denotes the at least one fingerprint for the query video sequence, a query is defined by:

q


(

f
i

,
X

)

=

{

x
O

x
O

=

arg


max

x
l



{

sim


(

f
i

,

f

x
l

)



f

x
l

∈
X

}

,

and




sim


(

f
i

,

f

x
O

)

≥

Assignees

• Tcl Res America Inc

Inventors

• Wang Haohong
• Yang Yimin

Classifications

• G06F16/783 Primary

  using metadata automatically derived from the content · CPC title

• G06F16/71

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/30784 Primary

  Physics · mapped topic

• G06F17/30858

  Physics · mapped topic

• G06V20/48

  Matching video sequences · CPC title