System and method for image and video segmentation by anisotropic kernel mean shift

• US 7,397,948 B1
• Filed: 03/08/2004
• Issued: 07/08/2008
• Est. Priority Date: 03/08/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cohen, Michael, Wang, Jue, Xu, Ying-Qing, Thiesson, Bo
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): Bayat; Ali
• Application Number:
  US10/796,736
• Time in Patent Office: 1,583 Days
• Field of Search: 382/162, 382/164, 382/166, 382/167, 382/171, 382/173, 382/201, 382/205, 382/128, 382/131, 708/490, 707/6
• US Class Current: 382/167
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/56 relating to colour

Abstract

Mean shift is a nonparametric estimator of density which has been applied to image and video segmentation. Traditional mean shift based segmentation uses a radially symmetric kernel to estimate local density, which is not optimal in view of the often structured nature of image and more particularly video data. The system and method of the invention employs an anisotropic kernel mean shift in which the shape, scale, and orientation of the kernels adapt to the local structure of the image or video. The anisotropic kernel is decomposed to provide handles for modifying the segmentation based on simple heuristics. Experimental results show that the anisotropic kernel mean shift outperforms the original mean shift on image and video segmentation in the following aspects: 1) it gets better results on general images and video in a smoothness sense; 2) the segmented results are more consistent with human visual saliency; and 3) the system and method is robust to initial parameters.

Claims

1. A computer-implemented process for segmenting image data, comprising the process actions of:

inputting an image;

segmenting said image using a mean shift segmentation technique employing anisotropic kernels;

wherein segmenting said image comprises;

initializing kernel data;

for each of a set of feature points, determining an anisotropic kernel with a spatial component and a related color component;

associating a mean shift point with every feature point and initializing said mean shift point to coincide with that feature point;

updating mean shift points by iterative anisotropic mean shift updates; and

merging vectors associated with feature points that are approximately the same to produce homogeneous color regions.

2. The computer-implemented process of claim 1 wherein the anisotropic kernels comprise a spatial/lattice component and a space dependent range/color domain component.

3. The computer-implemented process of claim 1 wherein the anisotropic kernels comprise a spatial/lattice component and a range/color domain component that is not space dependent.

4. The computer-implemented process of claim 1 wherein initializing the kernel data comprises the process actions of:

transferring pixels of said image into multi-dimensional feature points, x_i;

specifying an initial spatial domain parameter h₀^s and an initial range domain parameter h₀^r;

associating kernels with said feature points;

initializing means of kernels as the value of said feature points associated with kernels; and

setting initial kernel bandwidth matrices in the spatial/lattice domain as the diagonal matrix H_i^s=(h₀^s)²I and in the range/color domain setting h^r(H_i^s)=h₀^r, where I is the identity matrix.

5. The computer-implemented process of claim 1, wherein for each of a set of feature points, determining an anisotropic kernel with a spatial/lattice component and a related range/color component, comprising the process actions of:

for each feature point x_i, searching the neighbors of said feature point x_j, j=1, . . . , n to obtain all feature points that satisfy the constraints of the kernels;

iteratively updating a bandwidth matrix of the anisotropic kernel in the spatial domain,

modulating the bandwidth of the anisotropic kernel in the spatial domain; and

modulating the color tolerance of the related color component.

6. The computer-implemented process of claim 5 wherein the constraints of kernels are defined by:

$k^2(g<br><br>\left(\left(x_i,x_j,H_i^S\right)\right)<<br><br>1;<br><br>k^r<br><br>{<br><br><br><br>\frac{x_i-x_j}{h^r<br><br>\left(H_i^S\right)}<br><br><br><br>}^2<<br><br>1$

where H_i^s is the spatial/lattice bandwidth matrix and h^r is the range/color bandwidth, parameter.

7. The computer-implemented process of claim 5 wherein the bandwidth matrix H_i^s is updated as:

$H_i^s\leftarrow <br><br>\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>{<br><br><br><br>\frac{x_i^r-x_j^r}{h^r<br><br>\left(H_i^s\right)}<br><br><br><br>}^2<br><br>\left(x_j^s-x_i^s\right)<br><br>{\left(x_i^s-x_i^s\right)}^T}{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>{<br><br><br><br>\frac{x_i^r-x_j^r}{h^r<br><br>\left(H_i^s\right)}<br><br><br><br>}^2}.$

8. The computer-implemented process of claim 7 wherein the range/color bandwidth parameter h^r(H_i^s) is updated as:

$h^r<br><br>\left(H_i^S\right)\leftarrow <br><br>\sqrt{\frac{{\mathrm{\lambda <br><br>}}^{\mathrm{\prime <br><br>}}}{\mathrm{\lambda <br><br>}}}·<br><br>h^r<br><br>\left(H_i^S\right).$

9. The computer-implemented process of claim 5 wherein the segmentation is a single image segmentation and wherein modulations are applied to exaggerate eccentricity and modify scale.

10. The computer-implemented process of claim 5 wherein the segmentation is video segmentation and wherein modulations are applied for exaggerating eccentricity, scaling static segments, and overall scale.

11. The computer-implemented process of claim 1, wherein updating the mean shift points by iterative anisotropic mean shift updates, comprises the process actions of:

for each mean shift point M (x_i),

determining the neighboring feature points x_i;

calculating a mean shift vector M (x_i) summing over all the neighboring mean shift points; and

updating the mean shift points;

until the change in the mean shift points is less than a specified amount.

12. The computer-implemented process of claim 11 wherein the mean shift vector is calculated as:

$M_v<br><br>\left(x_i\right)=\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\left(x_j-M<br><br>\left(x_i\right)\right)<br><br>{<br><br><br><br>\frac{M<br><br>\left(x_i^r\right)-x_j^r}{h^r<br><br>\left(H_j^s\right)}<br><br><br><br>}^2}{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>\frac{M<br><br>\left(x_i^r\right)-x_j^r}{h^r<br><br>\left(H_j^s\right)}<br><br><br><br>}.$

13. A system for segmenting image data, comprising:

defining an anisotropic kernel of influence for each pixel in an image, wherein said kernel defines a measure of intuitive distance between pixels, where distance encompasses both spatial/lattice and range/color distance; and

assigning to each pixel a mean shift point initialized to coincide with said pixel;

iteratively moving each mean shift point upwards along the gradient of the kernel density function defined by the sum of all the kernels until they reach a stationary point; and

considering pixels that are associated with the set of mean shift points that migrate to the approximately same stationary point to be members of a single segment.

14. The system of claim 13, further comprising:

combining neighboring segments.

15. The system of claim 13, further comprising eliminating segments that contain less than a specified number of pixels.

16. The system of claim 13 wherein the image is a portion of video data and wherein distance further comprises temporal distance.

17. A computer-readable storage medium encoded with computer executable instructions for segmenting image data, said computer executable instructions comprising:

inputting image data; and

segmenting said image data using a mean shift segmentation technique employing generally elliptical kernels wherein the computer-executable instruction for segmenting said image data comprises sub-instructions for;

initializing kernel data;

for each feature point, determining a kernel being a product of kernels with at least one of these kernels being elliptical;

associating a mean shift point with every feature point and initializing said mean shift point to coincide with that feature point;

updating mean shift points by an iterative anisotropic mean shift update; and

merging vectors associated with feature points that are approximately the same to produce homogeneous color regions.

18. The computer-readable storage medium of claim 17 wherein an elliptical kernel comprises a spatial component.

19. The computer-readable storage medium of claim 18 wherein the image is a portion of video data and wherein the generally elliptical kernel further comprises a time component.

20. The computer-readable medium of claim 18 wherein said spatial kernel has a constant profile, k^s(z)=1 if |z|<

1, and 0 otherwise.

21. The computer-readable storage medium of claim 17 wherein a non-elliptical kernel comprises a color domain component.

22. The computer-readable medium of claim 21 wherein said color component uses an Epanechnikov kernel with a profile k^r(z)=1−

|z| if |z|<

1 and 0 otherwise.

23. The computer-readable storage medium of claim 17 wherein the computer-executable instruction for segmenting said image data using a mean shift segmentation technique, comprises a sub-instruction for defining the shape of a elliptical kernel as λ

DAD^T where λ

defines the overall volume of the kernel, A defines the relative lengths of the axes, and D is a rotation matrix that orients the kernel in space and time.

24. The computer-readable storage medium of claim 23 wherein the computer-executable instruction for segmenting said image data using a mean shift segmentation technique, further comprises a sub-instruction to modify the shape of an elliptical kernel by varying λ

, A or D.

25. The computer-readable storage medium of claim 24 wherein by varying λ

the spatial size of the kernel is adjusted.

26. The computer-readable storage medium of claim 24 wherein by varying A the shape of the kernel is varied.

27. The computer-readable storage medium of claim 26 wherein segmentation to segment elongated regions is encouraged by defining A as a diagonal matrix of Eigen values which is normalized to satisfy:

$\underset{i=1}{\overset{p}{\prod <br><br>}}<br><br><br><br>a_i=1$

where a_i is the i^th diagonal elements of A, and a_i≧

a_j, for i<

j; and

wherein the smaller Eigen values of A are diminished by;

$a_i=\{\begin{array}{cc}{a}_i^{3/2}& a_i<<br><br>=1\\ \sqrt{a_i}& a_i><br><br>1\end{array},i=2,\mathrm{\dots <br><br>}<br><br>,p.$

28. The computer-readable storage medium of claim 26 wherein larger segments for static objects are created by

computing a scale factor s₁ as

$s_t=\alpha$

+ ( 1 - α

) ⁢

∏

i = 1 p - 1 ⁢

⁢

d 1 ⁡

( i ) 2

where d₁ is the first Eigen vector in D, which corresponds with the largest Eigen value a₁•

d₁(i) stands for the ith element in d₁, which is the x, y and t component of the vector when i=1, 2, 3, respectively, and α

is a constant between 0 and 1;

setting α

to 0.25;

changing A to a_i′

=a_i·

s_t, i=2, . . . , p;

modifying A as

$a_i=\{\begin{array}{cc}{a}_i^{3/2}& a_i<<br><br>=1\\ \sqrt{a_i}& a_i><br><br>1\end{array},i=2,\mathrm{\dots <br><br>}<br><br>,p$

or modifying A as

$s_t=\mathrm{\alpha <br><br>}+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>\underset{i=1}{\overset{p-1}{\prod <br><br>}}<br><br><br><br>{d_1<br><br>\left(i\right)}^2;<br><br>$

and

changing global scalar λ

as

${\mathrm{\lambda <br><br>}}^{\mathrm{\prime <br><br>}}=\mathrm{\lambda <br><br>}<br><br>\underset{i=1}{\overset{p}{\prod <br><br>}}<br><br><br><br>\frac{a_i}{a_i^{\mathrm{\prime <br><br>}}}.$