Patent US5805736A successfully refreshed from Google Patents.
US5805736A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for encoding a contour of an object in a video signal by using a contour motion estimation technique
Assignee: Quarterhill Inc
•
Filing: 1996-07-25
•
Granted: 1998-09-08
•
Expires: 2016-07-25
Abstract
Abstract A method encodes a contour of an object expressed in a digital video signal, the video signal having a plurality of video frames including a current and a previous frames, by using an improved contour motion estimation. Centroids of a current and a previous contours are first determined by averaging pixel positions on each contour, respectively, and a displacement therebetween is outputted as a motion vector. The previous contour is shifted based on the motion vector in order to produce the predicted current contour. Deviation information representing the difference between the predicted current and the current contours is detected based on the predicted current and the current contours and the centroid of the current contour and then is encoded.
Inventors
- 👤 Jin-Hun Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 11:13
CPC Classifications
H; H04; H04N; H04N5/00; H04N5/14; H04N5/21; H04N5/213; G; G06; G06T; G06T9/00; G06T9/20; H04N19/00; H04N19/50; H04N19/503; H04N19/51; H04N19/537; H04N19/543; H04N19/20
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
276 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour based on the previous and the current contours and the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and (e) encoding the deviation information, wherein said step (c) includes the steps of: (c1) producing a predicted current contour by shifting the previous contour by the displacement; and (c2) overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said step (d) includes the steps of: (d11) drawing a plural number of radial segmentation lines from the centroid of the current contour; (d12) detecting a current contour intersection point and a predicted current contour intersection point for each segmentation line, said each segmentation line intersecting the current and the predicted current contours at the current contour and the predicted current contour intersection points, respectively; and (d13) calculating an error at the current contour intersection point based on a difference between the intersection points of each segmentation line, thereby generating the deviation information.
Claim 2
Independent Claim
276 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour based on the previous and the current contours and the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and (e) encoding the deviation information, wherein said step (c) includes the steps of: (c1) producing a predicted current contour by shifting the previous contour by the displacement; and (c2) overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said step (d) includes the steps of: (d11) drawing a plural number of radial segmentation lines from the centroid of the current contour; (d12) detecting a current contour intersection point and a predicted current contour intersection point for each segmentation line, said each segmentation line intersecting the current and the predicted current contours at the current contour and the predicted current contour intersection points, respectively; and (d13) calculating an error at the current contour intersection point based on a difference between the intersection points of each segmentation line, thereby generating the deviation information.
Claim 3
Dependent Claim
54 words
The method as recited in claim 1, wherein the error is based on the distance between the centroid of the current contour and the predicted current contour intersection point on each segmentation line, wherein the predicted current contour intersection point is determined based on a distance between the intersection points for each segmentation line.
Claim 4
Dependent Claim
46 words
The method as recited in claim 2, wherein the error is determined by subtracting a distance between the centroid of the current contour and the current contour intersection point from a distance between the centroid of the current contour and the predicted current contour intersection point.
Claim 5
Dependent Claim
45 words
The method as recited in claim 3, wherein said step (d) further includes, before step (d11), the steps of: (d21) detecting a size of the overlapped contour; and (d22) determining the number of the radial segmentation lines based on the size of the overlapped contour.
Claim 6
Dependent Claim
36 words
The method as recited in claim 3, wherein said step (d) further includes, after step (d13), the step of grouping the deviation information into a multiplicity of arrays, each array having a predetermined number of errors.
Claim 7
Dependent Claim
18 words
The method as recited in claim 5, wherein the grouped deviation information is encoded on an array-by-array basis.
Claim 8
Independent Claim
379 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour based on the previous and the current contours and the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and (e) encoding the deviation information, wherein said step (c) includes the steps of: (c1) producing a predicted current contour by shifting the previous contour by the displacement; and (c2) overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour; and, said step (d) includes the steps of: (d31) drawing M number of primary radial segmentation lines from the centroid of the current contour starting from a preset reference radial segmentation line, M being an integer larger than 1; (d32) detecting one or more turning points on the current contour, a turning point representing a point on the current contour at which a line connecting the centroid of the current contour and the turning point being tangential to the current contour; (d33) drawing N-1 number of secondary radial segmentation lines between every two adjacent primary radial segmentation lines, N being a positive integer; (d34) noticing one or more intersection points of each of the primary and the secondary radial segmentation lines with the current contour; (d35) finding one intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour; and (d36) calculating, moving in a predetermined direction along the current contour, an error at each current contour intersection point based on the difference between the intersection point on the current contour and the intersection point on the predicted current contour for said each segmentation line, thereby generating the deviation information.
Claim 9
Independent Claim
379 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour based on the previous and the current contours and the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and (e) encoding the deviation information, wherein said step (c) includes the steps of: (c1) producing a predicted current contour by shifting the previous contour by the displacement; and (c2) overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour; and, said step (d) includes the steps of: (d31) drawing M number of primary radial segmentation lines from the centroid of the current contour starting from a preset reference radial segmentation line, M being an integer larger than 1; (d32) detecting one or more turning points on the current contour, a turning point representing a point on the current contour at which a line connecting the centroid of the current contour and the turning point being tangential to the current contour; (d33) drawing N-1 number of secondary radial segmentation lines between every two adjacent primary radial segmentation lines, N being a positive integer; (d34) noticing one or more intersection points of each of the primary and the secondary radial segmentation lines with the current contour; (d35) finding one intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour; and (d36) calculating, moving in a predetermined direction along the current contour, an error at each current contour intersection point based on the difference between the intersection point on the current contour and the intersection point on the predicted current contour for said each segmentation line, thereby generating the deviation information.
Claim 10
Dependent Claim
52 words
The method as recited in claim 7, wherein the intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour is an intersection point closest to the centroid of the current contour among intersection points of said each segmentation line with the predicted current contour.
Claim 11
Dependent Claim
41 words
The method as recited in claim 8, wherein said step (d) further includes, before step (d31), the steps of: (d41) detecting a size of the overlapped contour; and (d42) determining the number M based on the size of the overlapped contour.
Claim 12
Dependent Claim
69 words
The method as recited in claim 8, wherein said step (d) further includes, if a turning point is detected, after the step (d32), the step of finding a primary radial segmentation line closest to the turning point and shifting the primary radial segmentation line to the turning point and when the closest primary radial segmentation line is not available, a next closest available primary radial segmentation line is used.
Claim 13
Dependent Claim
36 words
The method as recited in claim 10, wherein said step (d) further includes, after step (d36), the step of grouping the deviation information into a multiplicity of arrays, each array having a predetermined number of errors.
Claim 14
Dependent Claim
16 words
The method as recited in claim 11, wherein the predetermined number corresponds to the number N.
Claim 15
Dependent Claim
18 words
The method as recited in claim 12, wherein the grouped deviation information is encoded on an array-by-array basis.
Claim 16
Independent Claim
281 words
An apparatus for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises: means for determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; means for detecting a displacement between the centroids; means for generating an overlapped contour based on the previous and the current contours and the displacement; means for detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and means for encoding the deviation information, wherein said overlapped contour generating means includes: means for producing a predicted current contour by shifting the previous contour by the displacement; and means for overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said deviation information detecting means includes: means for drawing a plural number of radial segmentation lines from the centroid of the current contour; means for detecting a current contour intersection point and a predicted current contour intersection point for each segmentation line, said each segmentation line intersecting the current and the predicted current contours at the current contour and the predicted current contour intersection points, respectively; and means for calculating an error at the current contour intersection point based on a difference between the intersection points of each segmentation line, thereby generating the deviation information.
Claim 17
Independent Claim
281 words
An apparatus for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises: means for determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; means for detecting a displacement between the centroids; means for generating an overlapped contour based on the previous and the current contours and the displacement; means for detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and means for encoding the deviation information, wherein said overlapped contour generating means includes: means for producing a predicted current contour by shifting the previous contour by the displacement; and means for overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said deviation information detecting means includes: means for drawing a plural number of radial segmentation lines from the centroid of the current contour; means for detecting a current contour intersection point and a predicted current contour intersection point for each segmentation line, said each segmentation line intersecting the current and the predicted current contours at the current contour and the predicted current contour intersection points, respectively; and means for calculating an error at the current contour intersection point based on a difference between the intersection points of each segmentation line, thereby generating the deviation information.
Claim 18
Dependent Claim
54 words
The apparatus as recited in claim 14, wherein the error is based on the distance between the centroid of the current contour and the predicted current contour intersection point on each segmentation line, wherein the predicted current contour intersection point is determined based on a distance between the intersection points for each segmentation line.
Claim 19
Dependent Claim
46 words
The apparatus as recited in claim 15, wherein the error is determined by subtracting a distance between the centroid of the current contour and the current contour intersection point from a distance between the centroid of the current contour and the predicted current contour intersection point.
Claim 20
Dependent Claim
43 words
The apparatus as recited in claim 16, wherein said deviation information detecting means further includes: means for detecting a size of the overlapped contour; and means for determining the number of the radial segmentation lines based on the size of the overlapped contour.
Claim 21
Dependent Claim
34 words
The apparatus as recited in claim 16, wherein said deviation information detecting means further includes means for grouping the deviation information into a multiplicity of arrays, each array having a predetermined number of errors.
Claim 22
Dependent Claim
18 words
The apparatus as recited in claim 18, wherein the grouped deviation information is encoded on an array-by-array basis.
Claim 23
Independent Claim
387 words
An apparatus for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises: means for determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; means for detecting a displacement between the centroids; means for generating an overlapped contour based on the previous and the current contours and the displacement; means for detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and means for encoding the deviation information, wherein said overlapped contour generating means includes: means for producing a predicted current contour by shifting the previous contour by the displacement; and means for overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said deviation information detecting means includes: means for drawing M number of primary radial segmentation lines from the centroid of the current contour starting from a preset reference radial segmentation line, M being an integer larger than 1; means for detecting one or more turning points on the current contour, a turning point representing a point on the current contour at which a line connecting the centroid of the current contour and the turning point being tangential to the current contour; means for drawing N-1 number of secondary radial segmentation lines between every two adjacent primary radial segmentation lines, N being a positive integer; means for noticing one or more intersection points of each of the primary and the secondary radial segmentation lines with the current contour; means for finding one intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour; and means for calculating, moving in a predetermined direction along the current contour, an error at each current contour intersection point based on the difference between the intersection point on the current contour and the intersection point on the predicted current contour for said each segmentation line, thereby generating the deviation information.
Claim 24
Independent Claim
387 words
An apparatus for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises: means for determining centroids of a current and a previous contours by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; means for detecting a displacement between the centroids; means for generating an overlapped contour based on the previous and the current contours and the displacement; means for detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the current contour; and means for encoding the deviation information, wherein said overlapped contour generating means includes: means for producing a predicted current contour by shifting the previous contour by the displacement; and means for overlapping the predicted current contour and the current contour with reference to the centroid of the current contour to thereby generate the overlapped contour, and, said deviation information detecting means includes: means for drawing M number of primary radial segmentation lines from the centroid of the current contour starting from a preset reference radial segmentation line, M being an integer larger than 1; means for detecting one or more turning points on the current contour, a turning point representing a point on the current contour at which a line connecting the centroid of the current contour and the turning point being tangential to the current contour; means for drawing N-1 number of secondary radial segmentation lines between every two adjacent primary radial segmentation lines, N being a positive integer; means for noticing one or more intersection points of each of the primary and the secondary radial segmentation lines with the current contour; means for finding one intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour; and means for calculating, moving in a predetermined direction along the current contour, an error at each current contour intersection point based on the difference between the intersection point on the current contour and the intersection point on the predicted current contour for said each segmentation line, thereby generating the deviation information.
Claim 25
Dependent Claim
52 words
The apparatus as recited in claim 20, wherein the intersection point of each of the primary and the secondary radial segmentation lines with the predicted current contour is an intersection point closest to the centroid of the current contour among intersection points of said each segmentation line with the predicted current contour.
Claim 26
Dependent Claim
39 words
The apparatus as recited in claim 21, wherein said deviation information detecting means further includes: means for detecting a size of the overlapped contour; and means for determining the number M based on the size of the overlapped contour.
Claim 27
Dependent Claim
66 words
The apparatus as recited in claim 21, wherein said deviation information detecting means further includes, if a turning point is detected, means for finding a primary radial segmentation line closest to the turning point and shifting the primary radial segmentation line to the turning point and when the closest primary radial segmentation line is not available, a next closest available primary radial segmentation line is used.
Claim 28
Dependent Claim
34 words
The apparatus as recited in claim 23, wherein said deviation information detecting means further includes means for grouping the deviation information into a multiplicity of arrays, each array having a predetermined number of errors.
Claim 29
Dependent Claim
16 words
The apparatus as recited in claim 24, wherein the predetermined number corresponds to the number N.
Claim 30
Dependent Claim
18 words
The apparatus as recited in claim 25, wherein the grouped deviation information is encoded on an array-by-array basis.
Claim 31
Independent Claim
228 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contour by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour by shifting one of the current contour and the previous contour by the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the previous contour; and (e) encoding the deviation information, wherein said step (d) includes the steps of: (d51) drawing a plurality of radial segmentation lines from the centroid of the previous contour; (d52) detecting a current contour intersection point and a previous contour intersection point for each segmentation line, said each segmentation line intersecting the shifted current and the previous contours at the current contour and the previous contour intersection points, respectively; and (d53) calculating an error at the current contour intersection point based on a difference between the intersection points of the segmentation lines, thereby generating the deviation information.
Claim 32
Independent Claim
228 words
A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of video frames including a current frame and a previous frame, which comprises the steps of: (a) determining centroids of a current and a previous contour by averaging pixel positions on each of the contours, wherein the current and the previous contours represent the contours of the object in the current and the previous frames, respectively; (b) detecting a displacement between the centroids; (c) generating an overlapped contour by shifting one of the current contour and the previous contour by the displacement; (d) detecting deviation information representing the shape difference between the previous and the current contours based on the overlapped contour and the centroid of the previous contour; and (e) encoding the deviation information, wherein said step (d) includes the steps of: (d51) drawing a plurality of radial segmentation lines from the centroid of the previous contour; (d52) detecting a current contour intersection point and a previous contour intersection point for each segmentation line, said each segmentation line intersecting the shifted current and the previous contours at the current contour and the previous contour intersection points, respectively; and (d53) calculating an error at the current contour intersection point based on a difference between the intersection points of the segmentation lines, thereby generating the deviation information.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-07 | 2002-03-09 | 2002-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-07 | 2006-03-09 | 2006-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-07 | 2010-03-09 | 2010-09-08 | $7700.00 | Window Closed / Lapsed |