Digital video fingerprinting using motion segmentation

• US 10,318,813 B1
• Filed: 03/13/2017
• Issued: 06/11/2019
• Est. Priority Date: 03/11/2016
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Pereira, Jose Pio, Stojancic, Mihailo M.
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US15/456,856
• Time in Patent Office: 820 Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/44 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/45 Clustering; Classification
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20004 Adaptive image processing
• CPC Class Codes: G06T 2207/20224 Image subtraction
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• 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/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
• CPC Class Codes: G06V 20/635 Overlay text, e.g. embedded captions in a TV program
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18086 by performing operations within image blocks or by using histograms
• CPC Class Codes: G10L 15/02 : Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/063 : Training
• CPC Class Codes: G10L 15/10 : using distance or distortion measures between unknown speech and reference templates
• CPC Class Codes: G10L 15/142 : Hidden Markov Models [HMMs]
• CPC Class Codes: G10L 15/20 : Speech recognition techniques specially adapted for robustness in adverse environments, e.g. in noise, of stress induced speech G10L21/02 takes precedence
• CPC Class Codes: G10L 2015/025 : Phonemes, fenemes or fenones being the recognition units
• CPC Class Codes: G10L 2021/02166 : Microphone arrays; Beamforming
• CPC Class Codes: G10L 21/0232 : Processing in the frequency domain
• CPC Class Codes: G10L 25/81 : for discriminating voice from music

Abstract

Methods of processing video are presented to generate signatures for motion segmented regions over two or more frames. Two frames are differenced using an adaptive threshold to generate a two-frame difference image. The adaptive threshold is based on a motion histogram analysis which may vary according to motion history data. Also, a count of pixels is determined in image regions of the motion adapted two-frame difference image which identifies when the count is not within a threshold range to modify the motion adaptive threshold. A motion history image is created from the two-frame difference image. The motion history image is segmented to generate one or more motion segmented regions and a descriptor and a signature are generated for a selected motion segmented region.

Claims

1. A method of processing video to generate signatures for motion segmented regions over two or more frames, the method comprising:

differencing two frames using an adaptive threshold to generate a two-frame difference image;

creating a motion history image from the two-frame difference image;

segmenting the motion history image to generate one or more motion segmented regions;

generating a descriptor and a signature for a selected motion segmented region; and

aligning a background by;

computing a distance between a pixel at location x on each frame and a pixel at the location x on the aligned background for the location x in the two-frame difference image, and

comparing the distance for each location x to the adaptive threshold to generate foreground pixels used in the segmenting of the motion history image.

2. The method of claim 1, wherein the two frames are a first frame and an second frame immediately following in sequence from the first frame.

3. The method of claim 1, wherein the two frames are a first frame and a third frame skipping an intermediary second frame, wherein the second frame and third frame are in sequence from the first frame.

4. The method of claim 1 further comprising:

tracking previously detected segments in previously segmented motion history images that are not included among the one or more motion segmented regions.

5. The method of claim 1 further comprising:

adaptively modifying a threshold when a pixel count in a detected image region of the differenced frames is outside defined limits.

6. The method of claim 1, wherein the selected motion segmented region has a higher motion activity and larger size compared to the rest of the one or more motion segmented regions.

7. The method of claim 1, wherein the segmenting of the motion history image uses a weighted function of motion gradient and motion orientation.

8. The method of claim 1, wherein the segmenting of the motion history image uses similarity measures of pixels based on brightness, continuity and color.

9. The method of claim 1 further comprising:

extracting a compressed video stream from a compressed input; and

extracting block motion vectors and transform coefficients from the extracted compressed video stream.

10. A method of fingerprinting moving images taking into account motion across multiple frames, the method comprising:

differencing two frames using a motion adaptive threshold based on a motion histogram analysis to generate a motion adapted two-frame difference image;

as frames are received, determining a motion history image from generated motion adapted two-frame difference images over a plurality of frames;

segmenting the motion history image to generate one or more motion segmented regions;

generating a descriptor and a signature for a selected motion segmented region; and

aligning a background by;

computing a distance between a pixel at location x on each frame and a pixel at the location x on the aligned background for the location x in the two-frame difference image, and

comparing the distance for each location x to the adaptive threshold to generate foreground pixels used in the segmenting of the motion history image.

11. The method of claim 10, wherein the motion adapted two-frame difference image includes at least one image region in motion that is monitored to produce the motion histogram analysis.

12. The method of claim 10 further comprising:

determining the motion histogram analysis of at least one image region in motion from the motion adapted two-frame difference image over a plurality of frames.

13. The method of claim 10 further comprising:

determining a count of pixels in image regions of the motion adapted two-frame difference image; and

modifying the motion adaptive threshold to a new value based on the motion histogram analysis when the count is not within a threshold range.

14. The method of claim 10, wherein the motion adaptive threshold is set to a median of the motion histogram analysis.

15. The method of claim 14, wherein outliers of the motion histogram analysis are not considered in the generating the median of the motion histogram analysis.

16. The method of claim 14, wherein the median of the motion histogram analysis is biased lower or higher based on history data.

17. The method of claim 10 further comprising:

tracking of motion segmented regions per frame is used to store previous motion segmented regions which are selectively included in the one or more motion segmented regions for which descriptors and signatures are generated.

18. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method of processing video to generate signatures for motion segmented regions over two or more frames, the method comprising:

differencing two frames using an adaptive threshold to generate a two-frame difference image;

creating a motion history image from the two-frame difference image;

segmenting the motion history image to generate one or more motion segmented regions;

generating a descriptor and a signature for a selected motion segmented region; and

aligning a background by;

computing a distance between a pixel at location x on each frame and a pixel at the location x on the aligned background for the location x in the two-frame difference image, and

comparing the distance for each location x to the adaptive threshold to generate foreground pixels used in the segmenting of the motion history image.

19. The computer readable non-transitory medium of claim 18 further comprising:

adaptively modifying a threshold when a pixel count in a detected image region of the differenced frames is outside defined limits.

20. The computer readable non-transitory medium of claim 18 further comprising:

extracting a compressed video stream from a compressed input; and

extracting block motion vectors and transform coefficients from the extracted compressed video stream.