Method for encoding a contour of an object in a video signal by using a contour motion estimation technique

• US 5,635,986 A
• Filed: 06/27/1996
• Issued: 06/03/1997
• Est. Priority Date: 04/09/1996
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics (Government of South Korea)
• Inventors: Kim, Jin-Hun
• Primary Examiner(s): Au, Amelia
• Application Number:
  US08/672,165
• Time in Patent Office: 341 Days
• Field of Search: 348/390, 348/400, 348/401, 348/402, 348/409, 348/412, 348/413, 348/415, 348/416, 348/420, 348/699, 382/236, 382/238, 382/241, 382/242, 382/250, 382/199
• US Class Current: 375/240.16
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/543 using regions

Abstract

A method for encoding a contour of an object predicts a current contour by using a current and a reconstructed previous contours and generates the motion vector representing a displacement between the reconstructed previous and the predicted current contours. A matched contour between the predicted current and the current contours is subtracted from the current contour to provide a differential contour. Thereafter, vertex points is determined based on a polygonal approximation for the differential contour. A set of approximation errors calculated at a predetermined number of sample points on each line segment between two vertex points is transformed and quantized to obtain a set of quantized discrete sine transform coefficients. The quantized discrete sine transform coefficients are encoded together with the motion vector, and the vertex points are encoded based on the predicted current contour for transmission thereof. And, the coded vertex information is decoded based on the predicted current contour, and the quantized discrete sine transform coefficients are converted into the reconstructed errors to reconstruct the differential contour. The reconstructed differential contour is added to the matched contour to provide the reconstructed previous contour.

Claims

1. A method for encoding a contour of an object expressed in a digital video signal, said digital video signal having a plurality of frames including a current frame and a previous frame, comprising the steps of:

(a) detecting a boundary of the object within the current frame to generate a current contour, wherein the current contour provides current contour information for tracing the boundary of the object in the current frame, the current contour information including position data of the pixels along the boundary of the object;

(b) storing a reconstructed previous contour, wherein the reconstructed previous contour provides reconstructed previous contour information for tracing the boundary of the object in the previous frame;

(c) determining a motion vector by finding a movement of the reconstructed previous contour that gives a best match between the current and the reconstructed previous contours when the reconstructed previous contour is moved to overlap with the current contour, and generating the motion vector and a predicted current contour, wherein the motion vector represents a displacement between the reconstructed previous contour and the predicted current contour, the predicted current contour representing a contour shifted from the reconstructed previous contour by the motion vector;

(d) overlapping the predicted current contour with the current contour to thereby provide a matched contour representing an overlapped contour portion therebetween;

(e) generating a differential contour by subtracting the matched contour from the current contour, the differential contour denoting the differential contour portion between the current and the matched contours;

(f) determining a number of vertex points on the differential contour;

(g) providing a polygonal approximation of the differential contour by fitting the differential contour with a multiplicity of line segments, to thereby generate vertex information representing the positions of the vertex points of the differential contour, each of the line segments joining two neighboring vertex points;

(h) providing N sample points, wherein N is an integer, for each of the line segments and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for each of the line segments, wherein said N sample points are equi-distanced on each of the line segments and each set of errors represents the distance between said each of the N sample points and the differential contour;

(i) transforming the set of errors for each of the line segments into a set of discrete sine transform coefficients corresponding thereto;

(j) converting the set of the discrete sine transform coefficients into a set of quantized discrete sine transform coefficients corresponding thereto;

(k) encoding the motion vector and the set of quantized discrete sine transform coefficients for each set of discrete sine transform coefficients;

(l) encoding the vertex information based on the predicted current contour, to thereby provide encoded vertex information;

(m) decoding the encoded vertex information based on the predicted current contour, thereby providing decoded vertex information;

(n) converting the set of quantized discrete sine transform coefficients for each set of discrete sine transform coefficients into a set of reconstructed discrete sine transform coefficients;

(o) converting the set of reconstructed discrete sine transform coefficients into a set of reconstructed errors for said each of the line segments;

(p) providing the reconstructed differential contour based on the decoded vertex information and the set of reconstructed errors; and

(q) adding the matched contour to the reconstructed differential contour to thereby provide the added contour as the reconstructed previous contour.

2. The method according to claim 1, wherein said step (l) includes:

(l1) assigning an index to each pixel on the predicted current contour starting from a selected pixel; and

(l2) encoding a displacement between the previously encoded vertex point and the vertex point if none of the pixels on the predicted current contour is incorporated in a circle of radius R centered at the vertex point, otherwise, finding a closest pixel to the vertex point among the pixels included in the circle, and encoding the index corresponding to the closest pixel and the displacement between the vertex point and the closest pixel, R being a predetermined value.