Foreground detection using fractal dimensional measures

• US 9,916,662 B2
• Filed: 06/11/2015
• Issued: 03/13/2018
• Est. Priority Date: 03/17/2015
• Status: Expired due to Fees

• Current Assignee: Lyrical Labs Video Compression Technology, LLC
• Original Assignee: Lyrical Labs Video Compression Technology, LLC
• Inventors: Raburn, Daniel Louis, Ratner, Edward
• Primary Examiner(s): Do, Anh
• Application Number:
  US14/737,418
• Publication Number:
  US 20160275692A1
• Time in Patent Office: 1,006 Days
• Field of Search: 382173, 382180, 382181, 382232, 382257, 3584261, 375 E7081
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

A technique for foreground determination includes analyzing pixels that are deemed to be changing between frames, and applying a filtration technique that is based on fractal methods. Implementations include applying a filter that is designed to eliminate structures of dimensionality less than unity while preserving those of dimensionality unity and greater. The technique may be performed in real-time and makes use of a variable threshold for foreground determination and image segmentation techniques.

Claims

1. A method of foreground detection performed by a processor, the method comprising:

receiving a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

receiving a segment map corresponding to the current image, the segment map defining at least one segment of the current image;

constructing a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification corresponding to a foreground or a background, wherein constructing the foreground indicator map comprises;

constructing an ambient background image; and

constructing a difference image, the difference image comprising a set of pixels, wherein each pixel of the difference image indicates a difference between a corresponding pixel in the ambient background image and a corresponding pixel in the current image;

constructing a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identifying, based on the filtered foreground indicator map, the at least one segment as a foreground segment or a background segment.

2. The method of claim 1, wherein the ambient background image comprises a median background image, the median background image comprising a set of pixels, each of the set of pixels of the median background image having a plurality of color components, wherein each color component of each pixel of the median background image comprises the median of a corresponding component of corresponding pixels in the current image, the first previous image, and the second previous image.

3. The method of any of claims 1-2, wherein the foreground indicator map is a binary foreground indicator map (BFIM).

4. The method of any of claims 1-2, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM).

5. A method of foreground detection performed by a processor, the method comprising:

receiving a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

receiving a segment map corresponding to the current image, the segment map defining at least one segment of the current image;

constructing a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification corresponding to a foreground or a background, wherein the foreground indicator map is a binary foreground indicator map (BFIM), and wherein constructing the BFIM comprises;

determining, for each of the set of pixels in the BFIM, whether a corresponding pixel in the difference image corresponds to a difference that exceeds a threshold, wherein the threshold is indicated by a corresponding pixel in the threshold image, the threshold image comprising a set of pixels, wherein each pixel of the threshold image indicates an amount by which a pixel can change between images and still be considered part of the background; and

assigning an initial classification to each of the set of pixels in the BFIM, wherein the initial classification of a pixel is foreground if the corresponding difference exceeds the threshold;

constructing a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identifying, based on the filtered foreground indicator map, the at least one segment as a foreground segment or a background segment.

6. The method of claim 5, wherein filtering the BFIM comprises:

constructing a neighbor sum map, the neighbor sum map comprising, for a first pixel of the set of pixels in the BFIM, a first neighbor sum map value and a second neighbor sum map value, wherein the first pixel includes an initial classification as foreground;

applying, for the first pixel, a set of filter criteria to the first and second neighbor sum map values; and

retaining the initial classification of foreground for the first pixel if the filter criteria are satisfied.

7. The method of claim 6, wherein constructing the neighbor sum map comprises:

identifying, for the first pixel, a first box having a first box half size, s1, centered at the first pixel;

determining the first neighbor sum map value, the first neighbor sum map value comprising a number of pixels contained within the first box that have an initial classification as foreground;

identifying, for the first pixel, a second box having a second box half size, s2, centered at the first pixel; and

determining the second neighbor sum map value, the second neighbor sum map value comprising a number of pixels contained within the second box that have an initial classification as foreground.

8. The method of claim 7, wherein s1 is less than s2, and wherein retaining the initial classification of foreground for the first pixel if the filter criteria are satisfied comprises retaining the first pixel if all of the following are true:

the first neighbor sum map value is greater than or equal to the greatest integer that is not greater than the product of s1 and a first constant;

the second neighbor sum map value is greater than or equal to the greatest integer that is not greater than the product of s2 and the first constant; and

the second neighbor sum map value is greater than or equal to the sum of the first neighbor sum map value and the greatest integer that is not greater than the product of a second constant and the difference between s2 and s1.

9. The method of claim 8, wherein the first constant is 0.9 and the second constant is 0.4.

10. The method of any of claims 5-9, wherein identifying the at least one segment as a foreground segment or a background segment comprises:

determining, based on the filtered BFIM, at least one foreground metric corresponding to the at least one segment;

determining, based on the at least one foreground metric, at least one variable threshold; and

applying the at least one variable threshold to the filtered BFIM to identify the at least one segment as a foreground segment or a background segment.

11. The method of claim 10, wherein determining the at least one foreground metric comprises:

determining an un-weighted foreground area fraction (UFAF) by dividing the number of foreground pixels in the at least one segment by the total number of pixels in the at least one segment;

determining a foreground perimeter fraction (FPF) by dividing the number of foreground pixels on the perimeter of the at least one segment by the total number of pixels on the perimeter of the at least one segment; and

determining a weighted foreground area fraction (WFAF) by applying a variable weight to each of the pixels in the at least one segment and dividing the weighted number of foreground pixels in the at least one segment by the weighted total number of pixels in the segment.

12. The method of claim 11, wherein determining, based on the at least one foreground metric, the at least one variable threshold comprises:

constructing, based on the UFAF, a first foreground curve;

constructing, based on the FPF, a second foreground curve;

constructing, based on the WFAF, a third foreground curve;

determining a first variable threshold by determining an intersection between the first foreground curve and a first monotonically decreasing threshold curve;

determining a second variable threshold by determining an intersection between the second foreground curve and a second monotonically decreasing threshold curve; and

determining a third variable threshold by determining an intersection between the third foreground curve and a third monotonically decreasing threshold curve;

wherein if the at least one segment is above the first variable threshold, the second variable threshold or the third variable threshold, the at least one segment is identified as foreground.

13. A method of foreground detection performed by a processor, the method comprising:

receiving a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

receiving a segment map corresponding to the current image, the segment map defining at least one segment of the current image;

constructing a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification corresponding to a foreground or a background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM), and wherein constructing the NBFIM comprises;

constructing a normalized absolute difference image (NADI), wherein the NADI comprises a set of pixels, each of the set of pixels comprising a plurality of components, wherein each component of each pixel of the NADI is equal to a corresponding value in the difference image divided by a corresponding value in the foreground threshold image;

constructing an unfiltered NBFIM, having a set of pixels, wherein each pixel of the NBFIM is equal to the arc-hyperbolic sine of the sum of the squares of the components of a corresponding pixel in the NADI with a coefficient of 0.5 for each of the chroma components; and

applying a non-binary fractal-based analysis to generate a filtered NBFIM;

constructing a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identifying, based on the filtered foreground indicator map, the at least one segment as a foreground segment or a background segment.

14. The method of claim 13, wherein filtering the NBFIM comprises:

constructing a neighbor sum map, the neighbor sum map comprising, for each of the pixels of the NBFIM, a first neighbor sum map value and a second neighbor sum map value; and

applying, for each of the pixels of the NBFIM, a set of filter criteria to the first and second neighbor sum map values.

15. The method of claim 14, wherein constructing the neighbor sum map comprises:

identifying, for each of the pixels of the NBFIM, a first box having a first box half size, s1, centered at the pixel;

determining the first neighbor sum map value, the first neighbor sum map value comprising a sum of the values of the NBFIM pixels contained within the first box;

identifying, for each of the pixels of the NBFIM, a second box having a second box half size, s2, centered at the pixel; and

determining the second neighbor sum map value, the second neighbor sum map value comprising a sum of the values of the NBFIM pixels contained within the second box.

16. The method of claim 15, wherein s1 is less than s2, and wherein retaining each of the pixels of the NBFIM for which the filter criteria are satisfied comprises retaining each of the pixels of the NBFIM for which all of the following are true:

the second neighbor sum map value corresponding to the pixel is greater than or equal to the product of a variable coefficient and s2; and

the second neighbor sum map value corresponding to the pixel is greater than or equal to the sum of the first neighbor sum map value and the product of a second variable coefficient and the difference between s2 and s1.

17. The method of claim 16, wherein the first variable coefficient comprises three times the mean value of the NBFIM at that iteration, and wherein the second variable coefficient comprises ten times the mean value of the NBFIM at that iteration.

18. The method of claim 17, wherein identifying the at least one segment as a foreground segment or a background segment comprises:

determining, based on the filtered NBFIM, at least one foreground metric corresponding to the at least one segment;

determining, based on the at least one foreground metric, at least one variable threshold; and

applying the at least one variable threshold to the filtered NBFIM to identify the at least one segment as a foreground segment or a background segment.

19. The method of claim 18, wherein determining the at least one foreground metric comprises calculating the sum of the filtered NBFIM over each segment divided by the area of the segment.

20. The method of any of claims 13-19, further comprising applying an edge-enhancing technique to the filtered NBFIM to facilitate identification of at least one edge of a moving object.

21. One or more computer-readable media having computer-executable instructions embodied thereon for foreground detection in a digital image, the instructions configured to cause a processor, upon execution, to instantiate at least one component, the at least one component comprising:

a foreground detector, the foreground detector configured to;

receive a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

receive a segment map corresponding to the current image, the segment map defining at least one segment of the current image;

construct a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification as foreground or background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM);

construct a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identify, based on the filtered foreground indicator map, the at least one segment as a foreground segment or a background segment.

22. A system for performing foreground detection, the system comprising:

an encoding device having a processor configured to instantiate at least one component stored in a memory, the at least one component comprising a foreground detector configured to;

receive a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

receive a segment map corresponding to the current image, the segment map defining at least one segment of the current image;

construct a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification as foreground or background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM);

construct a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identify, based on the filtered foreground indicator map, the at least one segment as a foreground segment or a background segment.

23. A method of foreground detection performed by a processor, the method comprising:

receiving a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

constructing a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification corresponding to a foreground or a background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM);

constructing a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identifying, based on the filtered foreground indicator map, each of the set of pixels as a foreground pixel or a background pixel.

24. One or more computer-readable media having computer-executable instructions embodied thereon for foreground detection in a digital image, the instructions configured to cause a processor, upon execution, to instantiate at least one component, the at least one component comprising:

a foreground detector, the foreground detector configured to;

receive a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

construct a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification as foreground or background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM);

construct a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identify, based on the filtered foreground indicator map, each of the set of pixels as a foreground pixel or a background pixel.

25. A system for performing foreground detection, the system comprising:

an encoding device having a processor configured to instantiate at least one component stored in a memory, the at least one component comprising a foreground detector configured to;

receive a set of digital images, the set of digital images including a current image having a set of pixels, a first previous image having a set of pixels, at least one of which corresponds to at least one of the set of pixels of the current image, and a second previous image having a set of pixels, at least one of which corresponds to at least one pixel in each of the current image and the first previous image;

construct a foreground indicator map, the foreground indicator map comprising a set of pixels, wherein each of the set of pixels of the foreground indicator map corresponds to one of the set of pixels in the current image, and wherein each of the set of pixels of the foreground indicator map includes an initial classification as foreground or background, wherein the foreground indicator map is a non-binary foreground indicator map (NBFIM);

construct a filtered foreground indicator map by filtering the foreground indicator map by applying a filter configured to preserve structures having a fractal dimensionality of at least one; and

identify, based on the filtered foreground indicator map, each of the set of pixels as a foreground pixel or a background pixel.