Persistent feature descriptors for video

• US 10,534,964 B2
• Filed: 01/30/2017
• Issued: 01/14/2020
• Est. Priority Date: 01/30/2017
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Alrabeiah, Muhammad Rabeiah M, Chen, Jun, He, Dake, Li, Liangyan, Qiao, Yingchan, Wang, Yizhong, Yin, Ting
• Primary Examiner(s): Allison, Andrae S
• Application Number:
  US15/419,281
• Publication Number:
  US 20180218222A1
• Time in Patent Office: 1,079 Days
• Field of Search: None
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30256 Lane; Road marking
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: 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
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: G06V 20/48 Matching video sequences
• CPC Class Codes: 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

Abstract

Methods and devices for extracting feature descriptors for a video, the video having a sequence of pictures. The method includes identifying a first key picture and a second key picture later in the sequence than the first key picture; extracting a first set of feature descriptors from the first key picture and a second set of feature descriptors from the second key picture; identifying a set of pairs of feature descriptors, where each pair includes one descriptor from the first set and one descriptor from the second set; generating motion information describing the motion field between the first key picture and the second key picture; and filtering the set of pairs of feature descriptors based on correlation with the motion information to produce and output a subset of persistent descriptors.

Claims

1. A method of extracting feature descriptors for a video, in a video feature descriptor extractor, the video including a sequence of pictures, the method comprising:

identifying a first key picture and a second key picture later in the sequence than the first key picture and having at least one picture between them;

extracting a first set of feature descriptors from the first key picture and a second set of feature descriptors from the second key picture;

identifying a set of pairs of feature descriptors, where each pair includes one descriptor from the first set and one descriptor from the second set;

generating motion field information describing a motion field between the first key picture and the second key picture; and

filtering the set of pairs of feature descriptors based on correlation with the motion information to produce and output a subset of persistent descriptors, wherein filtering the set of pairs of feature descriptors includes discarding, from the set, one or more pairs of feature descriptors based on a determination of whether the pairs are consistent with the motion field, a pair of feature descriptors being consistent with the motion field if relative locations of the descriptors of the pair in their respective key picture conform to the motion field.

2. The method claimed in claim 1, wherein identifying the set of pairs of feature descriptors comprises, for each descriptor in the first set, identifying a descriptor in the second set based on minimizing Euclidean distance between the descriptor from the first set and the descriptor from the second set, and designating them as one of the pairs in the set of pairs of feature descriptors.

3. The method claimed in claim 1, wherein identifying the set of pairs of feature descriptors comprises, for each descriptor in the first set, determining whether there is a matching descriptor in the second set and, if so, designating them as one of the pairs of feature descriptors.

4. The method claimed in claim 3, wherein determining whether there is a matching descriptor comprises, for a descriptor in the first set, identifying the closest descriptor in the second set based on a first Euclidean distance from the descriptor in the first set, identifying the second closest descriptor in the second set based on a second Euclidean distance from the descriptor in the first set, and designating the closest descriptor as the matching descriptor if the ratio of the first Euclidean distance to the second Euclidean distance is less than a preset maximum.

5. The method claimed in claim 4, wherein the preset maximum is less than 0.8.

6. The method claimed in claim 1, wherein identifying the set of pairs of feature descriptors includes determining that two or more pairs of feature descriptors include the same descriptor in the second key picture and, based on that determination, scoring the quality of each of said two or more pairs of feature descriptors, retaining the highest quality pair, and discarding the remaining pairs of the two or more pairs of feature descriptors.

7. The method claimed in claim 1, wherein generating motion field information includes using an optical flow algorithm to determine relative movement between areas of the first key picture and areas of the second key picture.

8. The method claimed in claim 1, wherein filtering the set of pairs of feature descriptors includes, for each pair,

determining, based on the motion information and a location of pair'"'"'s descriptor from the first key picture, an estimated location in the second key picture;

determining whether the pair'"'"'s descriptor from the second key picture is located within a search window centered on the estimated location; and

if so, retaining the pair in the subset of persistent descriptors, and

if not, excluding the pair from the subset of persistent descriptors.

9. The method claimed in claim 1, wherein extracting comprises applying a Scale-Invariant Feature Transform (SIFT) algorithm to the first key picture and to the second key picture.

10. The method claimed in claim 1, wherein identifying comprises dividing the sequence of pictures into segments, each segment having a respective first key picture and a respective second key picture.

11. The method claimed in claim 10, wherein each segment contains a respective series of pictures, the respective first key picture of each segment is a first picture in its series, and the respective second key picture for each segment is a first picture in the subsequent segment in the sequence.

12. A video feature descriptor extractor for extracting feature descriptors for a video, the video including a sequence of pictures, the video feature descriptor extractor comprising:

a processor;

memory; and

an encoding application containing instructions executable by the processor that, when executed, cause the processor to

identify a first key picture and a second key picture later in the sequence than the first key picture and having at least one picture between them;

extract a first set of feature descriptors from the first key picture and a second set of feature descriptors from the second key picture;

identify a set of pairs of feature descriptors, where each pair includes one descriptor from the first set and one descriptor from the second set;

generate motion field information describing a motion field between the first key picture and the second key picture; and

filter the set of pairs of feature descriptors based on correlation with the motion information to produce and output a subset of persistent descriptors, wherein filtering the set of pairs of feature descriptors includes discarding, from the set, one or more pairs of features descriptors based on a determination of whether the pairs are consistent with the motion field, a pair of feature descriptors being consistent with the motion field if relative locations of the descriptors of the pair in their respective key picture conform to the motion field.

13. The video feature descriptor extractor claimed in claim 12, wherein the processor is to identify the set of pairs of feature descriptors by, for each descriptor in the first set, identifying a descriptor in the second set based on minimizing Euclidean distance between the descriptor from the first set and the descriptor from the second set, and designating them as one of the pairs of feature descriptors.

14. The video feature descriptor extractor claimed in claim 12, wherein the processor is to identify the set of pairs of feature descriptors by, for each descriptor in the first set, determining whether there is a matching descriptor in the second set and, if so, designating them as one of the pairs of feature descriptors.

15. The video feature descriptor extractor claimed in claim 14, wherein the processor is to determine whether there is a matching descriptor by, for a descriptor in the first set, identifying the closest descriptor in the second set based on a first Euclidean distance from the descriptor in the first set, identifying the second closest descriptor in the second set based on a second Euclidean distance from the descriptor in the first set, and designating the closest descriptor as the matching descriptor if the ratio of the first Euclidean distance to the second Euclidean distance is less than a preset maximum.

16. The video feature descriptor extractor claimed in claim 15, wherein the preset maximum is less than 0.8.

17. The video feature descriptor extractor claimed in claim 12, wherein the processor is to identify the set of pairs of feature descriptors by determining that two or more pairs of feature descriptors include the same descriptor in the second key picture and, based on that determination, scoring the quality of each of said two or more pairs of feature descriptors, retaining the highest quality pair, and discarding the remaining pairs of the two or more pairs of feature descriptors.

18. The video feature descriptor extractor claimed in claim 12, wherein the processor is to generate motion field information by using an optical flow algorithm to determine relative movement between areas of the first key picture and areas of the second key picture.

19. The video feature descriptor extractor claimed in claim 12, wherein the processor is to filter the set of pairs of feature descriptors by, for each pair,

determining, based on the motion information and a location of pair'"'"'s descriptor from the first key picture, an estimated location in the second key picture;

determining whether the pair'"'"'s descriptor from the second key picture is located within a search window centered on the estimated location; and

if so, retaining the pair in the subset of persistent descriptors, and

if not, excluding the pair from the subset of persistent descriptors.

20. The video feature descriptor extractor claimed in claim 12, wherein the processor is to extract feature descriptors by applying a Scale-Invariant Feature Transform (SIFT) algorithm to the first key picture and to the second key picture.

21. The video feature descriptor extractor claimed in claim 12, wherein the processor is to identify a first key picture and a second key picture by dividing the sequence of pictures into segments, each segment having a respective first key picture and a respective second key picture.

22. The video feature descriptor extractor claimed in claim 21, wherein each segment contains a respective series of pictures, the respective first key picture of each segment is a first picture in its series, and the respective second key picture for each segment is a first picture in the subsequent segment in the sequence.

23. A non-transitory processor-readable medium storing processor-executable instructions for extracting feature descriptors for a video, the video including a sequence of pictures, wherein the processor-executable instructions, when executed by a processor in a video feature descriptor extractor, cause the processor to:

identify a first key picture and a second key picture later in the sequence than the first key picture and having at least one picture between them;

extract a first set of feature descriptors from the first key picture and a second set of feature descriptors from the second key picture;

identify a set of pairs of feature descriptors, where each pair includes one descriptor from the first set and one descriptor from the second set;

generate motion field information describing a motion field between the first key picture and the second key picture; and

filter the set of pairs of feature descriptors based on correlation with the motion information to produce and output a subset of persistent descriptors, wherein filtering the set of pairs of feature descriptors includes discarding, from the set, one or more pairs of features descriptors based on a determination of whether the pairs are consistent with the motion field, a pair of feature descriptors being consistent with the motion field if relative locations of the descriptors of the pair in their respective key picture conform to the motion field.