Feature segmentation

• US 6,026,182 A
• Filed: 06/04/1996
• Issued: 02/15/2000
• Est. Priority Date: 10/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gray, David, Lee, Ming-Chieh
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US08/657,275
• Time in Patent Office: 1,351 Days
• Field of Search: 382/241, 382/242, 382/243, 382/256, 382/173, 382/199, 382/203, 382/298
• US Class Current: 382/173
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/563 Motion estimation with padding, i.e. with filling of non-object values in an arbitrarily shaped picture block or region for estimation purposes
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments

Abstract

A segmentation method segments selected objects from other objects within a video image frame. The objects may be of arbitrary configuration and preferably represent distinct image features in a display image. An interior outline is formed within the interior of the object perimeter. The interior outline is expanded automatically to form an exterior outline. Pixels between the interior outline and the exterior outline are classified according to predefined attributes as to whether they are within object interior, thereby to identify automatically a conformed outline that is fitted to the object perimeter.

Claims

1. A method of segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, comprising:

obtaining within the interior an interior outline of the perimeter of the arbitrary first image feature, the interior outline being generally within a predetermined distance of the perimeter; and

expanding the interior outline of the perimeter according to a predetermined factor to form a conformed outline representing the perimeter of the arbitrary first image feature;

wherein the predetermined factor includes relative multi-dimensional proximity to the first and second image characteristics of selected pixels adjacent the outline.

2. The method of claim 1 in which the predetermined factor includes a change from the first image characteristic in the interior of the arbitrary first image feature.

3. The method of claim 1 in which the predetermined factor includes a predetermined distance transverse to the interior outline of the perimeter of the arbitrary first image feature.

4. The method of claim 1 in which the predetermined factor includes a weighted combination of a change from the first image characteristic in the interior of the arbitrary first image feature and a predetermined distance transverse to the interior outline of the perimeter of the arbitrary first image feature.

5. A method of segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the interior outline are formed, the method comprising:

obtaining within the interior an interior outline of the perimeter of the arbitrary first image feature; and

expanding the interior outline of the perimeter according to a predetermined factor to form a conformed outline representing the perimeter of the arbitrary first image feature, where expanding the interior outline of the perimeter includes;

obtaining an exterior outline of pixels that bounds the perimeter of the first image feature and the interior outline,

associating the pixels bounded by the interior and exterior outlines with one or the other of the interior and exterior outlines according to the predetermined factor, and

identifying as the conformed outline the pixels associated with the interior outline and adjacent a pixel associated with the exterior outline.

6. The method of claim 5 in which the predetermined factor includes image display characteristics of the pixels in the video image frame.

7. The method of claim 6 in which the image display characteristics include color component values.

8. The method of claim 5 in which the predetermined factor includes the distances between a pixel and the interior and exterior outlines.

9. The method of claim 5 in which the predetermined factor includes a weighted combination of a change from the first image characteristic in the interior of the arbitrary first image feature and a predetermined distance transverse to the interior outline of the perimeter of the arbitrary first image feature.

10. The method of claim 5 in which each pixel is represented by red, green, and blue color component values r, g, and b, and a pixel location x, y, and the predetermined factor includes for each pixel bounded by the interior and exterior outlines a minimum of absolute distances d_imin and d_jmin to pixels i and j in the respective interior and exterior outlines determined as:

space="preserve" listing-type="equation">d.sub.imin =w.sub.color (|r-r.sub.i |+|g-g.sub.i |+|b-b.sub.i |)+w.sub.coord (|x-x.sub.i |+|y-y.sub.i |)

space="preserve" listing-type="equation">d.sub.jmin =w.sub.color (|r-r.sub.j |+|g-g.sub.j |+|b-b.sub.j |)+w.sub.coord (|x-x.sub.j |+|y-y.sub.j |)

in which w_color and w_coord are weighting factors for the respective color component values and pixel positions.

11. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, the medium comprising:

programming for obtaining as user-manipulated input a first outline of the perimeter of the arbitrary first image feature, the first outline being generally within a predetermined distance of the perimeter;

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature, where the first outline is formed of pixels of generally one image characteristic, and the programming for fitting the outline of the perimeter includes;

programming for obtaining a second outline of pixels opposite the perimeter of the first image feature from the first outline, one of the first and second outlines bounding the other; and

programming for associating the pixels bounded by the interior outline with the inner and outer outlines according to the predetermined factor to determine the perimeter.

12. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, the medium comprising:

programming for obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature, the outline being generally within a predetermined distance of the perimeter;

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature; and

wherein the predetermined factor includes relative multi-dimensional proximity to the first and second image characteristics of selected pixels adjacent the outline.

13. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, the medium comprising:

programming for obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature, the outline being generally within a predetermined distance of the perimeter;

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature; and

wherein the predetermined factor includes a relative distance between pixels and the outline.

14. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, the medium comprising:

programming for obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature, the outline being generally within a predetermined distance of the perimeter; and

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature, where the predetermined factor includes relative multi-dimensional proximity to the first and second image characteristics of selected pixels adjacent the outline and a relative distance of such pixels to the outline.

15. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the first outline are formed, the medium comprising:

programming for obtaining as user-manipulated input a first outline of the perimeter of the arbitrary first image feature, the outline being generally within a predetermined distance of the perimeter; and

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature, where the first outline is formed of pixels of generally one image characteristic, and the programming for fitting the outline of the perimeter includes;

programming for obtaining a second outline of pixels opposite the perimeter of the first image feature from the first outline, one of the first and second outlines bounding the other,

programming for associating the pixels bounded by the first and second outlines with one or the other of the first and second outlines according to the predetermined factor, and

programming for identifying as the perimeter the pixels associated with the one of the first and second outlines bounded by the other and adjacent a pixel associated with the other outline.

16. A computer-readable medium storing computer-executable programming for segmenting an arbitrary first image feature in a video image frame from an adjacent second image feature in the image video frame, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the interior outline are formed, the medium comprising:

programming for obtaining as user-manipulated input an interior outline formed within the interior of the first image feature, such outline being generally within a predetermined distance of the perimeter; and

programming for fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature, such programming including;

programming for obtaining an exterior outline of pixels that bounds the perimeter of the first image feature and the interior outline,

programming for associating the pixels bounded by the interior and exterior outlines with one or the other of the interior and exterior outlines according to the predetermined factor, and programming for identifying as the perimeter the pixels associated with the interior outline and adjacent a pixel associated with the exterior outline.

17. The medium of claim 16 in which the predetermined factor includes image display characteristics of the pixels in the video image frame.

18. The medium of claim 17 in which the image display characteristics include color component values.

19. The medium of claim 16 in which the predetermined factor includes the distances of a pixel to the interior and exterior outlines.

20. A method of identifying an arbitrary first image feature in first and second video image frames, the arbitrary first image in the first video image frame being adjacent a second image feature, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, comprising:

obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature in the first video image frame, the outline being generally within a predetermined distance of the perimeter;

fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature in the first video image frame, such fitting including associating the pixels bounded by the interior outline with the interior outline according to the predetermined factor; and

tracking the arbitrary first image feature from the first video image frame to the second video image frame;

wherein the predetermined factor includes relative multi-dimensional proximity to the first and second image characteristics of selected pixels adjacent the outline.

21. The method of claim 20 in which tracking the arbitrary first image feature includes identifying a feature point of the arbitrary first image feature in the first video image frame and determining a motion transformation of the feature point between the first and second video image frames.

31. The method of claim 20 in which the first video image frame precedes the second video image frame.

22. A method of identifying an arbitrary first image feature in first and second video image frames, the arbitrary first image in the first video image frame being adjacent a second image feature, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which are formed the image features, an outline, and a feature point, the method comprising:

obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature in the first video image frame, the outline being generally within a predetermined distance of the perimeter;

fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature in the first video image frame; and

tracking the arbitrary first image feature from the first video image frame to the second video image frame, where such tracking includes identifying a feature point of the arbitrary first image feature in the first video image frame and determining a motion transformation of the feature point between the first and second video image frames;

wherein determining the motion transformation includes identifying a first plurality of pixels that encompass the feature point in the first video image frame and identifying a corresponding second plurality of pixels that encompass the feature point in the second video image frame.

23. The method of claim 22 in which all the pixels in at least one of the first and pluralities of pixels are within the interior of the arbitrary first image feature.

24. A method of identifying an arbitrary first image feature in first and second video image frames, the arbitrary first image in the first video image frame being adjacent a second image feature, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the outline are formed, comprising:

obtaining as user-manipulated input an outline of the perimeter of the arbitrary first image feature in the first video image frame, the outline being generally within a predetermined distance of the perimeter;

fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature in the first video image frame, such factor including relative multi-dimensional proximity to the first and second image characteristics of selected pixels adjacent the outline; and

tracking the arbitrary first image feature from the first video image frame to the second video image frame.

25. A method of identifying an arbitrary first image feature in first and second video image frames, the arbitrary first image in the first video image frame being adjacent a second image feature, the arbitrary first image feature having an interior that is bounded by a perimeter and has a first image characteristic and the second image feature having a second image characteristic different from the first image characteristic, in which the video image frame includes plural pixels from which the image features and the interior outline are formed, comprising:

obtaining as user-manipulated input an interior outline of the perimeter of the arbitrary first image feature in the first video image frame, the outline being generally within a predetermined distance of the perimeter;

tracking the arbitrary first image feature from the first video image frame to the second video image frame;

fitting the outline of the perimeter according to a predetermined factor to represent the perimeter bounding the interior of the arbitrary first image feature in the first video image frame, where fitting includes;

obtaining an exterior outline of pixels bounds the perimeter and the interior outline,

associating the pixels bounded by the interior and exterior outlines with one or the other of the interior and exterior outlines according to the predetermined factor, and

identifying as the perimeter the pixels associated with the interior outline and adjacent a pixel associated with the exterior outline.

26. The method of claim 25 in which the predetermined factor includes image display characteristics of the pixels in the video image frame.

27. The method of claim 26 in which the image display characteristics include color component values.

28. The method of claim 25 in which the predetermined factor includes the distances between a pixel and the interior and exterior outlines.

29. The method of claim 25 in which the predetermined factor includes a weighted combination of a change from the first image characteristic in the interior of the arbitrary first image feature and a predetermined distance transverse to the outline of the perimeter of the arbitrary first image feature.

30. The method of claim 25 in which each pixel is represented by red, green, and blue color component values r, g, and b, and a pixel location x, y, and the predetermined factor includes for each pixel bounded by the interior and exterior outlines a minimum of absolute distances d_imin and d_jmin to pixels i and j in the respective interior and exterior outlines determined as:

space="preserve" listing-type="equation">d.sub.imin =w.sub.color (|r-r.sub.i |+|g-g.sub.i |+|b-b.sub.i |)+w.sub.coord (|x-x.sub.i |+|y-y.sub.i |)

space="preserve" listing-type="equation">d.sub.jmin =w.sub.color (|r-r.sub.j |+|g-g.sub.j |+|b-b.sub.j |)+w.sub.coord (|x-x.sub.j |+|y-y.sub.j |)

in which w_color and w_coord are weighting factors for the respective color component values and pixel positions.