VIDEO SEGMENTATION METHOD

• US 20130329987A1
• Filed: 06/11/2012
• Published: 12/12/2013
• Est. Priority Date: 06/11/2012
• Status: Abandoned Application

• Current Assignee: Genesis Group Inc.
• Original Assignee: Genesis Group Inc.
• Inventors: GONG, Minglun
• Application Number:
  US13/493,482
• Publication Number:
  US 20130329987A1
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• 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
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

A system and method implemented as a software tool for foreground segmentation of video sequences in real-time, which uses two Competing 1-class Support Vector Machines (C-1SVMs) operating to separately identify background and foreground. A globalized, weighted optimizer may resolve unknown or boundary conditions following convergence of the C-1SVMs. The objective of foreground segmentation is to extract the desired foreground object from live input videos, with fuzzy boundaries captured by freely moving cameras. The present disclosure proposes the method of training and maintaining two competing classifiers, based on Competing 1-class Support Vector Machines (C-1SVMs), at each pixel location, which model local color distributions for foreground and background, respectively. By introducing novel acceleration techniques and exploiting the parallel structure of the algorithm (including reweighing and max-pooling of data), real-time processing speed is achieved for VGA-sized videos.

Claims

1. A computer implemented method for segmenting a digital image into foreground and background comprising the steps of:

(a) Initializing design parameters for a background 1-class support vector machine (B-1SVM) and for a foreground 1-class support vector machine (F-1SVM) as computer implemented functions within a computer system;

(b) Inputting the digital image to the computer system;

(c) Inputting a background sample set of known background pixels in the image and a foreground sample set of known foreground pixels in the image, to the computer system to define an current label of the image;

(d) Until no further changes occur in the current label of the image, perform the following computer implemented steps of;

(i) Training a B-1SVM based on the design parameters at each pixel using pixels labelled as background within the current label of the image, and training a F-1SVM based on the design parameters at each pixel using pixels labelled as foreground within the current label of the image;

(ii) Classifying each pixel using the B-1SVM and the F-1SVM to obtain a competing classification for each pixel; and

(iii) Relabeling the current label of the image to identify the pixels which the competing classification agrees to be background and to identify the pixels which the competing classification agrees to be foreground.

2. The computer implemented method of claim 1 further comprising the step of:

(e) Applying a global optimizing function to relabel as either foreground or background within the current label of the image, pixels in the image which have not yet been labelled as foreground or background by the B-1SVM and the F-1SVM.

3. The computer implemented method of claim 1 wherein the background sample set is obtained through unsupervised means.

4. The computer implemented method of claim 1 wherein the background sample set is obtained through supervised means.

5. The computer implemented method of claim 1 wherein the foreground sample set is obtained through unsupervised means.

6. The computer implemented method of claim 1 wherein the foreground sample set is obtained through supervised means.

7. The computer implemented method of claim 1 wherein the design parameters include a kernel function k(•

,•

) from the group of kernel functions consisting of;

homogeneous polynomial basis function, unhomogeneous polynomial basis function, Guassian radial basis function, and hyperbolic tangent basis function.

8. The computer implemented method of claim 7 wherein the kernel function k(•

,•

) is a Guassian radial basis function.

9. The computer implemented method of claim 1 wherein the design parameters include a neighbourhood, and the training step and classifying step at each pixel occur over the entire neighbourhood about such pixel.

10. The computer implemented method of claim 1 wherein the design parameters include a neighbourhood further divided into subgroups, the training step at each pixel uses only pixels in the subgroup centred on such pixel and the classifying step uses only centre pixels at the subgroups in the neighbourhood.

11. The computer implemented method of claim 10 wherein the neighbourhood about each pixel is 3n by 3n pixels centred on such pixel (n an odd integer greater than 1), and the subgroups are 9 non-intersecting n by n squares within the neighbourhood.

12. The computer implemented method of claim 10 wherein the neighbourhood about each pixel is a square of k times n plus (k−

1) times g pixels on each side, where n is an odd integer greater than 1 being the width of each subgroup, k is an odd integer greater than 1 with k² being the number of subgroups, and g is the width in pixels of a gap between subgroups such that g times 2 plus 1 is not greater than n.

13. The computer implemented method of claim 10 wherein the neighbourhood about each pixel is 33 by 33 pixels centred on such pixel, the neighbourhood is further divided into twenty-five non-intersecting subgroups of 5 by 5 pixel squares with adjacent subgroups all separated by a 2 pixel wide gap.

14. The computer implemented method of claim 2 wherein the global optimizing function solves, for each pixel, a Markov random field based energy function having a data term determined by costs of assigning such pixel to foreground and background and a contrast term which adaptively penalizes segmentation boundaries based on local color differences.

15. The computer implemented method of claim 1 wherein the training step is performed by a learning method from the group of learning methods consisting of batch learning methods, online learning methods of modified online learning methods.

16. The computer implemented method of claim 15 wherein the modified online learning method is performed according to Equation (3) and Equation (4).

17. The computer implemented method of claim 10 wherein the training step is performed according to the following algorithm, for a centre subgroup {circumflex over (Ω

)}_p within the neighbourhood of each pixel p, for the current label of the image L^t

18. The computer implemented method of claim 17 wherein the classifying step is performed according to the following algorithm, with design parameters , , , set, foreground score function at pixel p being f(p), background score function at pixel p being f_B(p), and subgroups {circumflex over (Ω

)}_q being the subgroups in neighbourhood Ω

_p of pixel p which do not intersect pixel p;

19. The computer implemented method of claim 18 wherein the following design parameters are set as margin γ

=1, =0.1, =0.3, ==0.4, cut off value C=0.5, and spacial decay τ

_spacial=0.05.

20. A computer implemented method for segmenting a video stream of digital images into foreground and background comprising the steps of:

(a) Initializing design parameters for a background 1-class support vector machine (B-1SVM) and for a foreground 1-class support vector machine (F-1SVM) as computer implemented functions within a computer system;

(b) Inputting the digital images of the video stream to the computer system;

(c) Inputting to the computer system a background sample set of known background pixels in a current image and a foreground sample set of known foreground pixels in such current image, to define a current label of the current image;

(d) Until no further changes occur in the current label of the current image, perform on pixels of the current image the train-relabel steps of;

(i) Training a B-1SVM based on the design parameters at each pixel within the current image using pixels labelled as background within the current label of the current image, and training a F-1SVM based on the design parameters at each pixel using pixels labelled as foreground within the current label of the current image;

(ii) Classifying each pixel using the B-1SVM and the F-1SVM to obtain a competing classification for each pixel; and

(iii) Relabeling the current label of the current image to identify the pixels which the competing classification agrees to be background and to identify the pixels which the competing classification agrees to be foreground;

(e) While images remain to be processed in the video stream, set the next image in the video stream as the current image and return to step (d).

21. The computer implemented method of claim 20 further comprising the step after step (d) and before step (e) of:

(d.1) Applying a global optimizing function to relabel as either foreground or background within the current label of the current image, pixels in the image which have not yet been labelled as foreground or background by the B-1SVM and the F-1SVM.

22. The computer implemented method of claim 21 further comprising the step after step (d.1):

(d.2) relabeling the current label for the current image to the output of the global optimizing function with morphological erosion on a boundary where pixels identified as foreground are otherwise adjacent to pixels identified as background.

23. The computer implemented method of claim 20 wherein the background sample set is obtained through unsupervised means.

24. The computer implemented method of claim 20 wherein the background sample set is obtained through supervised means.

25. The computer implemented method of claim 20 wherein the foreground sample set is obtained through unsupervised means.

26. The computer implemented method of claim 20 wherein the foreground sample set is obtained through supervised means.

27. The computer implemented method of claim 20 wherein the design parameters include a kernel function k(•

,•

) from the group of kernel functions consisting of;

homogeneous polynomial basis function, unhomogeneous polynomial basis function, Guassian radial basis function, and hyperbolic tangent basis function.

28. The computer implemented method of claim 27 wherein the kernel function k(•

,•

) is a Guassian radial basis function.

29. The computer implemented method of claim 20 wherein the design parameters include a neighbourhood, and the training step and classifying step at each pixel occur over the entire neighbourhood about such pixel.

30. The computer implemented method of claim 20 wherein the design parameters include a neighbourhood further divided into subgroups, the training step at each pixel uses only pixels in the subgroup centred on such pixel and the classifying step uses only centre pixels at the subgroups in the neighbourhood.

31. The computer implemented method of claim 30 wherein the neighbourhood about each pixel is 33 by 33 pixels centred on such pixel, the neighbourhood is further divided into twenty-five non-intersecting subgroups of 5 by 5 pixel squares with adjacent subgroups all separated by a 2 pixel wide gap.

32. The computer implemented method of claim 21 wherein the global optimizing function solves, for each pixel, a Markov random field based energy function having a data term determined by costs of assigning such pixel to foreground and background and a contrast term which adaptively penalizes segmentation boundaries based on local color differences.

33. The computer implemented method of claim 20 wherein the training step is performed by a learning method from the group of learning methods consisting of batch learning methods, online learning methods of modified online learning methods.

34. The computer implemented method of claim 33 wherein the modified online learning method is performed according to Equation (3) and Equation (4).

35. The computer implemented method of claim 30 wherein the training step is performed according to the following algorithm, for a centre subgroup {circumflex over (Ω

)}_p within the neighbourhood of each pixel p, for the current label of the image L^t

36. The computer implemented method of claim 35 wherein the classifying step is performed according to the following algorithm, with design parameters , , , set, foreground score function at pixel p being (p), background score function at pixel p being f_B(p), and subgroups {circumflex over (Ω

)}_q being the subgroups in neighbourhood Ω

_v of pixel p which do not intersect pixel p;

37. The computer implemented method of claim 36 wherein the following design parameters are set as margin γ

=1, =0.1, =0.3, ==0.4, cut off value C=0.5, and spacial decay τ

_spacial=0.05.

38. A method for real-time segmentation of a foreground object from a video stream comprising the steps of:

(a) Inputting the video stream to a computer system;

(b) Applying computer implemented instructions on the computer system to establishing a background 1-class support vector machine (B-1SVM) and a foreground 1-class support vector machine (F-1 SVM) to analyse pixels in frames of the video stream;

(c) Obtaining user selected criteria on a location of the foreground object within one or more of the frames;

(d) Applying the background C-1SVM and the foreground C-1SVM to the video image initialized by the user selected criteria on the location of the foreground object;

(e) Applying computer implemented instructions to implement the following initialization algorithm on desired subgroups of pixels;