Region extraction in vector images

• US 7,088,845 B2
• Filed: 01/28/2004
• Issued: 08/08/2006
• Est. Priority Date: 09/10/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh, Gu, Chuang
• Primary Examiner(s): Choobin, Barry
• Application Number:
  US10/767,135
• Publication Number:
  US 20040189863A1
• Time in Patent Office: 923 Days
• Field of Search: 382/103, 382/107, 348/169, 734/88, 356/27
• US Class Current: 382/103
• 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/215 Motion-based segmentation
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A semantic object tracking method tracks general semantic objects with multiple non-rigid motion, disconnected components and multiple colors throughout a vector image sequence. The method accurately tracks these general semantic objects by spatially segmenting image regions from a current frame and then classifying these regions as to which semantic object they originated from in the previous frame. To classify each region, the method perform a region based motion estimation between each spatially segmented region and the previous frame to computed the position of a predicted region in the previous frame. The method then classifies each region in the current frame as being part of a semantic object based on which semantic object in the previous frame contains the most overlapping points of the predicted region. Using this method, each region in the current image is tracked to one semantic object from the previous frame, with no gaps or overlaps. The method propagates few or no errors because it projects regions into a frame where the semantic object boundaries are previously computed rather than trying to project and adjust a boundary in a frame where the object'"'"'s boundary is unknown.

Claims

1. A method comprising:

providing a vector image, wherein the vector image comprises plural m-dimensional points, and wherein m is greater than or equal to 1; and

for each of one or more regions in the vector image, growing the region from a starting point of the plural points, wherein the growing includes adding to the region one or more neighboring points that satisfy a homogeneity criterion for the region and are not already part of any region in the vector image, wherein the growing the region ends when there are no neighboring points satisfying the homogeneity criterion for the region, and wherein the growing occurs sequentially on a region-after-region basis until each of the plural points is part of one of the one or more regions.

2. The method of claim 1 wherein the plural points are organized as m ordered complete lattices for the vector image.

3. The method of claim 1 wherein the growing occurs without initially specifying starting points for all of the one or more regions.

4. The method of claim 1 wherein for each of the m dimensions the homogeneity criterion constrains the difference between a maximum point value in the region and a minimum point value in the region.

5. The method of claim 1 wherein the homogeneity criterion constrains the difference between two adjacent points.

6. The method of claim 1 wherein the homogeneity criterion is based upon a mathematical function controlling variation in intensity values of points in the region.

7. The method of claim 1 further comprising filtering the vector image before the growing to simplify the vector image.

8. The method of claim 7 wherein the filtering includes applying a median filter to remove noise while preserving boundary details.

9. The method of claim 1 wherein m is greater than or equal to 2.

10. The method of claim 1 wherein m is greater than or equal to 3.

11. The method of claim 1 wherein the vector image is a video image, and wherein the plural points are plural pixels.

12. The method of claim 11 further comprising tracking a video object into the video image using the one or more regions.

13. The method of claim 12 further comprising repeating the providing, the growing, and the tracking for each of one or more subsequent video images.

14. The method of claim 12 further comprising tracking a second video object into the video image using the one or more regions.

15. A computer-readable medium having stored therein computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 1.

16. A method comprising:

providing a vector image, wherein the vector image comprises plural m-dimensional points, and wherein m is greater than or equal to 1; and

for each of one or more regions in the vector image, growing the region by adding to the region one or more neighboring points that satisfy a homogeneity criterion for the region and are not already part of any region in the vector image, wherein for each of the m dimensions the homogeneity criterion constrains the difference between a maximum point value in the region and a minimum point value in the region, and wherein the growing the region ends when there are no neighboring points satisfying the homogeneity criterion for the region.

17. The method of claim 16 wherein the growing occurs sequentially until each of the plural points is part of one of the one or more regions, and wherein the growing occurs without initially specifying starting points for all of the one or more regions.

18. The method of claim 16 wherein the plural points are organized as m ordered complete lattices for the vector image.

19. The method of claim 16 further comprising median filtering the vector image before the growing to remove noise while preserving boundary details.

20. The method of claim 16 wherein m is greater than or equal to 2.

21. The method of claim 16 wherein m is greater than or equal to 3.

22. The method of claim 16 wherein the vector image is a video image, and wherein the plural points are plural pixels.

23. A computer-readable medium having stored therein computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 16.

24. A method comprising:

providing a video image, wherein the video image comprises plural pixels;

growing a first region in the video image starting from a first pixel of the plural pixels, wherein the growing includes adding to the first region one or more neighboring pixels that satisfy a homogeneity criterion for the first region and are not already part of any region in the video image, and wherein the growing the first region ends when there are no neighboring pixels satisfying the homogeneity criterion for the first region; and

after the growing the first region ends, sequentially repeating the growing as necessary for each of one or more other regions in the video image until each of the plural pixels of the video image is part of the first region or one of the one or more other regions in the video image, wherein the growing occurs without initially specifying starting pixels for all of the regions.

25. The method of claim 24 further comprising filtering the video image before the growing to simplify the video image.

26. The method of claim 24 wherein the homogeneity criterion constrains the difference between a maximum pixel value and a minimum pixel value in a given region.

27. The method of claim 24 wherein each of the plural pixels consists of one intensity value.

28. The method of claim 24 wherein each of the plural pixels consists of three intensity values.

29. A computer-readable medium having stored therein computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 24.