System and method for video processing by image segmentation
View Patent ↗Video data is segmented by representing the pixel location, RGB values and other features such as motion vectors, as points in a multidimensional segmentation space. Initialized segments are represented as locations in the segmentation space and segment membership then determined by the distance in segmentation space from the data point representing the pixel to the location of the segment. The distance measure takes into consideration the covariance of the data, for the segment or for the picture.
1. A method of segmenting in a processor image data having a plurality of feature values at each pixel in a sequence of pictures, the feature values including pixel values and motion vector values, comprising:
representing the data as points in a segmentation vector space which is the product of a vector space of feature values and a vector space of pixel addresses,
representing segments as locations in the segmentation vector space,
calculating a displaced frame difference by applying a motion vector from the segment to the pixel, and
determining, using said processor, the membership of a segment for each pixel by a distance measured in segmentation vector space from the data point representing the pixel to the location of the segment,
said distance in segmentation vector space comprising the components of:
differences in pixel values between the pixel and the segment,
differences in motion vector values between the pixel and the segment, and
a displaced frame difference calculated by applying a motion vector from the segment to the pixel.
2. A method according to claim 1 , in which the segments are represented as points.
3. A method according to claim 1 , in which the segments are represented as linear functions mapping the vector space of pixel locations to the vector space of pixel values.
4. A method according to claim 1 , in which the distance measure is a Euclidean distance.
5. A method according to claim 1 , in which the distance measure is a Manhattan distance.
6. A method according to claim 1 , in which the coordinate axes are scaled to equalize the variances of the data along each axis.
7. A method according to claim 1 , in which the coordinate axes are scaled in order to minimize the product of errors evaluated along each axis, with the constraint that the scaling factors sum to a constant value.
8. A method according to Claim 1 , in which the distance measure is a Mahalanobis distance.
9. A method according to claim 1 , further comprising the steps of
determining a covariance matrix of the image data in each segment; and
measuring a distance in segmentation vector space of each pixel to each segment location taking into consideration said covariance matrix.
10. A method according to claim 9 , where the covariance matrix Λ of the data in the segment is given by
Λ
ij
=
1
K
S
-
1
∑
k
∈
S
(
x
ik
-
μ
i
)
(
x
jk
-
μ
j
)
where (x 1 , x 2 , . . . , x N ) k ,kεS are vectors in the multidimensional space belonging to segment S, and the location of the segment is given by
(
μ
1
,
μ
2
,
…
,
μ
N
)
=
1
K
S
∑
k
∈
S
(
x
1
,
x
2
,
…
,
x
N
)
k
,
where K s is the number of points in segment S.
11. A method according to claim 10 , wherein the distance measure is equal to (x−μ).Λ −1 .(x−μ) T .
12. A method according to claim 1 , comprising the step for each picture of initially assigning pixels to segments according to the segment membership of the respective pixel in the preceding picture in the sequence.
13. A method according to claim 1 , in which each pixel is chosen to be a member of a single segment determined by minimizing the distance measure.
14. A method according to claim 1 , in which the number of segments is chosen by the user.
15. A method according to claim 1 , in which the number of segments is chosen as a function of the input data.
16. A method according to claim 1 , in which the number of segments is chosen so that the variance of an overall error measure approaches a predetermined value.
17. A method according to claim 1 , in which two or more parallel versions of the algorithm are run with different numbers of segments and the number of segments chosen is based on the relative performance of the two versions.
18. A method according to claim 1 , in which the representations of segments in the vector space are updated according to the segment membership of pixels.
19. A method according to claim 1 , in which the processes of assigning pixels to segments and of updating the representations of segments are repeated alternately.
20. A method according to claim 1 , in which the initial segmentation is taken from the previous picture in a sequence of pictures.
21. A method according to claim 1 , in which the displaced frame differences are calculated by applying motion vectors derived from the current state of the segmentation to the input pixel data.
22. A method of segmenting in a processor image data having a plurality of feature values at each pixel, comprising the steps of
representing the image data as points in a segmentation vector space which is the product of a vector space of feature values and a vector space of pixel addresses, said segmentation vector space having a canvas which is toroidal such that the location of a segment which would otherwise disappear from one edge of the canvas appears as a result of the toroidal shape of the canvas at an opposing edge of the canvas;
initially assigning pixels to segments represented as locations in the segmentation vector space, and
determining, using said processor, the membership of a segment for each pixel according to a distance measured from the data point representing the pixel to the representation of the segment, said distance comprising the components of:
differences in pixel values between the pixel and the segment, and
differences in motion vector values between the pixel and the segment.