US6711278B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tracking semantic objects in vector image sequences
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-09-10
•
Granted: 2004-03-23
•
Expires: 2018-09-10
Abstract
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 performs a region based motion estimation between each spatially segmented region and the previous frame to compute 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.
Inventors
- 👤 Chuang Gu
- 👤 Ming-Chieh Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:17
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/80; G; G06; G06T; G06T7/00; G06T7/10; G06T7/11; G06T7/174; G06T7/20; G06T7/215; G06T7/246; G06V; G06V10/00; G06V10/20; G06V10/24; H04N19/50; H04N19/503; H04N19/51; H04N19/537; H04N19/543
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
160 words
A method for tracking video objects in video frames, the method comprising: performing spatial segmentation on a current video frame to identify plural regions of pixels with homogenous intensity values; performing motion estimation between each of the plural regions in the current video frame and a previous video frame in which a boundary of a video object was previously computed; using the motion estimation for each of the plural regions to warp pixel locations in the region to locations in the previous video frame; determining whether the warped pixel locations are within the previously computed boundary of the video object in the previous video frame to identify a set of the plural regions that are likely to be part of the video object in the current video frame; and forming a boundary of the video object in the current video frame as a combination of each of the plural regions in the current video frame that are in the set.
Claim 2
Independent Claim
160 words
A method for tracking video objects in video frames, the method comprising: performing spatial segmentation on a current video frame to identify plural regions of pixels with homogenous intensity values; performing motion estimation between each of the plural regions in the current video frame and a previous video frame in which a boundary of a video object was previously computed; using the motion estimation for each of the plural regions to warp pixel locations in the region to locations in the previous video frame; determining whether the warped pixel locations are within the previously computed boundary of the video object in the previous video frame to identify a set of the plural regions that are likely to be part of the video object in the current video frame; and forming a boundary of the video object in the current video frame as a combination of each of the plural regions in the current video frame that are in the set.
Claim 3
Dependent Claim
36 words
The method of claim 1 further including: repeating claim 1 for a subsequent video frame using the boundary of the video object in the current video frame as a reference boundary for the subsequent video frame.
Claim 4
Dependent Claim
25 words
The method of claim 1 further including: filtering the current video frame to remove noise from the current video frame before performing the spatial segmentation.
Claim 5
Dependent Claim
40 words
The method of claim 1 wherein the spatial segmentation includes, for each of the plural regions, ensuring that a difference between a maximum intensity value in the region and a minimum intensity value in the region is below a threshold.
Claim 6
Dependent Claim
105 words
The method of claim 1 wherein the spatial segmentation is a sequential region growing comprising: starting with a first pixel location in the current video frame, growing a first region of connected pixels around the first pixel location by adding pixel locations to the first region such that a homogeneity criteria is satisfied; when no boundary pixels around the first region satisfy the homogeneity criteria, repeating the growing for another region with a pixel location outside the first region; and continuing the growing until each of the pixel locations in the current video frame is identified as being part of one of the plural regions.
Claim 7
Dependent Claim
65 words
The method of claim 1 wherein the motion estimation comprises: for each of the plural regions identified through spatial segmentation in the current video frame, performing a region-based motion estimation including matching only pixels within the region with pixels in the previous video frame; and applying a motion model to approximate motion of the pixels within the region to corresponding locations in the previous frame.
Claim 8
Dependent Claim
22 words
The method of claim 6 wherein the motion model is used to find a motion vector for each of the plural regions.
Claim 9
Dependent Claim
73 words
The method of claim 1 wherein the determining includes for each of the plural regions: counting the warped pixel locations that are within the boundary of the video object in the previous video frame; when a majority of the warped pixel locations are within the boundary of the video object, classifying the region as being in the set that are likely to be part of the video object in the current video frame.
Claim 10
Dependent Claim
22 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform the method of claim 1 .
Claim 11
Dependent Claim
221 words
A computer system for tracking semantic objects in a vector image sequence of image frames, the system comprising: a spatial segmentation module for segmenting a current image frame in the vector image sequence into plural regions, each of the plural regions comprising image points having image values that satisfy a homogeneity criterion; a motion estimator module for estimating the motion between each of the plural regions in the current image frame and a reference image frame, and for determining a motion parameter for each of the plural regions that approximates the motion of the region between the current image frame and the reference image frame, wherein the reference image frame includes a semantic object for which a semantic object boundary was previously computed; and a region classifier module for applying the motion parameter of each of the plural regions to the region to compute a predicted region in the reference image frame, and for classifying each of the plural regions as being part of or not being part of the semantic object depending on the extent to which the predicted region for the region falls within the previously computed semantic object boundary in the reference image frame; wherein a corresponding semantic object boundary in the current image frame is formed from each region classified as being part of the semantic object.
Claim 12
Dependent Claim
221 words
A computer system for tracking semantic objects in a vector image sequence of image frames, the system comprising: a spatial segmentation module for segmenting a current image frame in the vector image sequence into plural regions, each of the plural regions comprising image points having image values that satisfy a homogeneity criterion; a motion estimator module for estimating the motion between each of the plural regions in the current image frame and a reference image frame, and for determining a motion parameter for each of the plural regions that approximates the motion of the region between the current image frame and the reference image frame, wherein the reference image frame includes a semantic object for which a semantic object boundary was previously computed; and a region classifier module for applying the motion parameter of each of the plural regions to the region to compute a predicted region in the reference image frame, and for classifying each of the plural regions as being part of or not being part of the semantic object depending on the extent to which the predicted region for the region falls within the previously computed semantic object boundary in the reference image frame; wherein a corresponding semantic object boundary in the current image frame is formed from each region classified as being part of the semantic object.
Claim 13
Dependent Claim
63 words
The computer system of claim 10 wherein the homogeneity criteria of the spatial segmentation module comprises a maximum difference value between a maximum image value for a first region and a minimum image value for the first region, and wherein the spatial segmentation module selectively adds neighboring image points to the first region so long as the first region satisfies the homogeneity criteria.
Claim 14
Dependent Claim
20 words
The computer system of claim 10 wherein the motion parameter of each of the plural regions is a motion vector.
Claim 15
Dependent Claim
99 words
The computer system of claim 10 wherein: the reference image frame includes two or more semantic objects, each of the two or more semantic objects occupying a non-overlapping area of the reference image frame, the region classifier module classifies each of the plural regions as being part of one of the two or more semantic objects depending on which of the two or more semantic objects in the reference image frame has maximum overlap with the predicted region for the region, and wherein corresponding semantic object boundaries in the current image frame are formed from the plural classified regions.
Claim 16
Dependent Claim
26 words
The computer system of claim 13 further including: a majority operator for defining a structure of points around each image point in the current image frame.
Claim 17
Independent Claim
164 words
A method for tracking semantic objects in vector image sequences, the method comprising: performing spatial segmentation on a current image frame to identify plural regions of discrete image points with homogenous image values; performing motion estimation between each of the plural regions in the current image frame and a target image frame in which a boundary of a semantic object is known; using the motion estimation for each of the plural regions to warp the image points in the region to locations in the target image frame; for each region of the plural regions, when at least a threshold amount of the warped image points for the region overlap the semantic object with the known boundary in the target image frame, classifying the region as originating from the semantic object; and forming a boundary of the semantic object in the current image frame based upon each of the plural regions in the current image frame that are classified as originating from the semantic object.
Claim 18
Independent Claim
164 words
A method for tracking semantic objects in vector image sequences, the method comprising: performing spatial segmentation on a current image frame to identify plural regions of discrete image points with homogenous image values; performing motion estimation between each of the plural regions in the current image frame and a target image frame in which a boundary of a semantic object is known; using the motion estimation for each of the plural regions to warp the image points in the region to locations in the target image frame; for each region of the plural regions, when at least a threshold amount of the warped image points for the region overlap the semantic object with the known boundary in the target image frame, classifying the region as originating from the semantic object; and forming a boundary of the semantic object in the current image frame based upon each of the plural regions in the current image frame that are classified as originating from the semantic object.
Claim 19
Dependent Claim
41 words
The method of claim 15 further including: for each of one or more additional image frames, designating the current image frame as the target image frame; designating the additional image frame as the current image frame; and repeating claim 15 .
Claim 20
Dependent Claim
51 words
The method of claim 15 wherein each of the plural regions is determined to be homogenous by only adding neighboring image points to the region where the difference between a maximum image value and a minimum image value in the region after adding each neighboring image point is below a threshold.
Claim 21
Dependent Claim
78 words
The method of claim 15 wherein: the target image frame is the previous image frame of the current image frame, each of the plural regions segmented from the current image frame is classified as originating from exactly one semantic object, boundaries for semantic objects in the current image frame are computed based upon boundaries of regions classified as originating from the respective semantic objects, and claim 15 is repeated for successive image frames in the vector image sequence.
Claim 22
Dependent Claim
22 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform the method of claim 15 .
Claim 23
Independent Claim
227 words
A method for tracking semantic objects in vector image sequences, the method comprising: performing spatial segmentation on a current image frame to identify plural regions of discrete image points with homogenous image values, where each of the plural regions comprises image points, and where each of the plural regions is determined to be homogenous by only adding neighboring image points to the region where the difference between a maximum image value and a minimum image value in the region after adding each neighboring image point is below a threshold; performing region-based motion estimation between each of the plural regions in the current image frame and an immediate previous image frame in the vector image sequence in which a boundary of a semantic object is known; using the motion estimated for each of the plural regions to warp the image points in the region to locations in the immediate previous image frame; for each of the plural regions, when at least a threshold amount of the warped image points for the region overlap the semantic object with the known boundary in the immediate previous image frame, classifying the region as originating from the semantic object; and forming a boundary for the semantic object in the current image frame based upon which of the plural regions in the current image frame are classified as originating from the semantic object.
Claim 24
Independent Claim
227 words
A method for tracking semantic objects in vector image sequences, the method comprising: performing spatial segmentation on a current image frame to identify plural regions of discrete image points with homogenous image values, where each of the plural regions comprises image points, and where each of the plural regions is determined to be homogenous by only adding neighboring image points to the region where the difference between a maximum image value and a minimum image value in the region after adding each neighboring image point is below a threshold; performing region-based motion estimation between each of the plural regions in the current image frame and an immediate previous image frame in the vector image sequence in which a boundary of a semantic object is known; using the motion estimated for each of the plural regions to warp the image points in the region to locations in the immediate previous image frame; for each of the plural regions, when at least a threshold amount of the warped image points for the region overlap the semantic object with the known boundary in the immediate previous image frame, classifying the region as originating from the semantic object; and forming a boundary for the semantic object in the current image frame based upon which of the plural regions in the current image frame are classified as originating from the semantic object.
Claim 25
Independent Claim
106 words
A method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a first image frame of a vector image sequence; segmenting a second image frame of the vector image sequence into plural regions; based upon motion estimates, warping each of the plural regions backward into the first image frame; for each of the plural regions of the second image frame, if a threshold portion of the warped region lies within the previously computed boundary in the first image frame, classifying the region of the second image frame as part of the object.
Claim 26
Independent Claim
106 words
A method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a first image frame of a vector image sequence; segmenting a second image frame of the vector image sequence into plural regions; based upon motion estimates, warping each of the plural regions backward into the first image frame; for each of the plural regions of the second image frame, if a threshold portion of the warped region lies within the previously computed boundary in the first image frame, classifying the region of the second image frame as part of the object.
Claim 27
Dependent Claim
33 words
The method of claim 21 further comprising: forming a new boundary of the object in the second image frame from one or more of the plural regions classified as part of the object.
Claim 28
Dependent Claim
44 words
The method of claim 22 further comprising: repeating the segmenting, warping, and classifying for a third image frame, wherein the warping proceeds from the third image frame backward into the second image frame, and wherein the classifying occurs by comparison to the new boundary.
Claim 29
Dependent Claim
87 words
The method of claim 21 wherein the segmenting comprises: growing a first region of the plural regions from a first image point by adding neighboring image points that satisfy a homogeneity criterion for the first region, wherein the homogeneity criterion constrains the difference between a maximum image point value and a minimum image point value in the first region; and repeating the growing for other regions of the plural regions until each image point of the second image frame is part of one of the plural regions.
Claim 30
Dependent Claim
36 words
The method of claim 21 wherein the first image frame includes plural objects having boundaries, and wherein the classifying indicates one of the plural objects for each of the plural regions of the second image frame.
Claim 31
Dependent Claim
22 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform the method of claim 21 .
Claim 32
Dependent Claim
134 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform a method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a previous image frame of a vector image sequence; segmenting a current image frame of a vector image sequence into plural regions; based upon motion estimates for the plural regions of the current image frame, warping each of the plural regions backward into the previous image frame; for each of the plural regions of the current image frame, if a threshold portion of the warped region lies within the previously computed boundary of the object in the previous image frame, classifying the region of the current image frame as part of the object.
Claim 33
Dependent Claim
134 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform a method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a previous image frame of a vector image sequence; segmenting a current image frame of a vector image sequence into plural regions; based upon motion estimates for the plural regions of the current image frame, warping each of the plural regions backward into the previous image frame; for each of the plural regions of the current image frame, if a threshold portion of the warped region lies within the previously computed boundary of the object in the previous image frame, classifying the region of the current image frame as part of the object.
Claim 34
Independent Claim
124 words
A method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a first image frame of a vector image sequence; segmenting a second image frame of the vector image sequence into plural regions; for each of the plural regions of the second image frame, associating the region with a corresponding region of the first image frame based upon motion estimation from the second image frame back to the first image frame; and if a threshold portion of the associated corresponding region of the first image frame lies within the previously computed boundary in the first image frame, classifying the region of the second image frame as part of the object.
Claim 35
Independent Claim
124 words
A method of tracking an object in a vector image sequence using backward region-based classification, the method comprising: computing a boundary of an object in a first image frame of a vector image sequence; segmenting a second image frame of the vector image sequence into plural regions; for each of the plural regions of the second image frame, associating the region with a corresponding region of the first image frame based upon motion estimation from the second image frame back to the first image frame; and if a threshold portion of the associated corresponding region of the first image frame lies within the previously computed boundary in the first image frame, classifying the region of the second image frame as part of the object.
Claim 36
Dependent Claim
33 words
The method of claim 28 further comprising: forming a new boundary of the object in the second image frame from one or more of the plural regions classified as part of the object.
Claim 37
Dependent Claim
47 words
The method of claim 29 further comprising: repeating the segmenting, associating, and classifying for a third image frame, wherein the associating is based upon motion estimation from third image frame back to the second image frame, and wherein the classifying occurs by comparison to the new boundary.
Claim 38
Dependent Claim
22 words
A computer-readable medium having instructions stored thereon for causing a computer system programmed thereby to perform the method of claim 28 .
References Cited (Backward Citations)
US4783833A
Cited
US5136659A
Cited
US5034986A
Cited
US5175808A
Cited
US5103305A
Cited
WO1991011782A1
Cited
US5214504A
Cited
US5148497A
Cited
US5117287A
Cited
US5103306A
Cited
US5274453A
Cited
EP0474307A2
Cited
US5258836A
Cited
US6011596A
Cited
US5684886A
Cited
US5471535A
Cited
US5259040A
Cited
US5684509A
Cited
US5295201A
Cited
US5731849A
Cited
US5809161A
Cited
US5706417A
Cited
EP0579319A2
Cited
US5524068A
Cited
US5376971A
Cited
EP0614318A2
Cited
US5557684A
Cited
US5577131A
Cited
US5329311A
Cited
US5598215A
Cited
EP0625853A2
Cited
US5572258A
Cited
US5923365A
Cited
US5761326A
Cited
US5666434A
Cited
US6005625A
Cited
US5978497A
Cited
US5761341A
Cited
US5619281A
Cited
US5581308A
Cited
US5673339A
Cited
US5598216A
Cited
US5694487A
Cited
US5734737A
Cited
US5546129A
Cited
US5612743A
Cited
US5654771A
Cited
US5717463A
Cited
US5668608A
Cited
WO1997005746A2
Cited
US5627591A
Cited
US5731836A
Cited
US5784175A
Cited
US6026182A
Cited
US5764805A
Cited
US5802220A
Cited
US5692063A
Cited
US5946419A
Cited
US5778098A
Cited
US5764814A
Cited
US6037988A
Cited
US5982909A
Cited
US6005493A
Cited
US6075875A
Cited
US5748789A
Cited
US5864630A
Cited
US6097854A
Cited
US5946043A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-03-23 | 2007-09-22 | 2008-03-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-23 | 2011-09-22 | 2012-03-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-23 | 2015-09-22 | 2016-03-23 | $7700.00 | Window Closed / Lapsed |