Method for encoding a video signal using feature point based motion estimation

• US 5,673,339 A
• Filed: 07/31/1995
• Issued: 09/30/1997
• Est. Priority Date: 03/20/1995
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics (Government of South Korea)
• Inventors: Lee, Min-Sup
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US08/509,313
• Time in Patent Office: 792 Days
• Field of Search: 382/232, 382/236, 382/241, 382/243, 348/699, 348/700, 348/701, 348/399, 348/400, 348/401, 348/402, 348/409, 348/415, 348/413, 348/416, 348/407, 348/430, 348/431, 358/430, 358/433
• US Class Current: 382/236
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: H04N 19/54 using feature points or meshes

Abstract

A method for providing an accurately predicted current frame, comprising the steps of: selecting feature points in the previous frame and detecting a first set of motion vectors for the feature points; defining quadrangles by connecting the feature points; defining horizontally split triangles by splitting quadrangles and calculating a variance for each triangle and comparing the variance to select the smallest variance as first variance; defining vertically split triangles by splitting the quadrangles and calculating the variance for each triangle and comparing the variance to select the smallest variance value as second variance value; comparing the first and the second variance and selecting the smaller variance as a third variance and providing triangle information representing the split direction for the third variance; determining quasi-feature points on the current frame and a second set of motion vectors for the quasi-feature points; defining quadrangles formed by connecting the quasi-feature points, and splitting each quadrangle into two triangles; determining a predicted position on the previous frame for pixel contained in triangle of the current frame; determining a third set of motion vectors for the pixels contained in triangle of the current frame; and providing value of each pixel to be contained in the predicted current frame by using the second and the third set of motion vectors.

Claims

1. A method, for use in a video signal encoder, for effectively encoding a digital video signal based on a feature point-based motion estimation technique, said digital video signal having a plurality of frames including a current frame and a previous frame, by providing an accurately predicted current frame, comprising the steps of:

(a) selecting a multiplicity of pixels in the previous frame as feature points and detecting a first set of motion vectors for the feature points between the current frame and the previous frame, said feature points representing motions of objects in the digital video signal;

(b) defining non-overlapping quadrangles by line segments connecting the feature points;

(c) defining horizontally split triangles by splitting each of the quadrangles in a horizontal direction and calculating a variance value of the pixel values for each of the horizontally split triangles and comparing the variance values for all the horizontally split triangles to select, as a first variance value, the smallest variance value;

(d) defining vertically split triangles by splitting each of the quadrangles in a vertical direction and calculating the variance value of the pixel values for each of the vertically split triangles and comparing the variance values for all the vertically split triangles to select, as a second variance value, the smallest variance value;

(e) comparing the first and the second variance values and selecting, as a third variance value, the smaller variance value and providing triangle information representing the split direction for the triangle having the third variance value;

(f) determining a multiplicity of quasi-feature points on the current frame and a second set of motion vectors for the quasi-feature points based on the feature points and the motion vectors thereof;

(g) defining non-overlapping quadrangles formed by line segments connecting the quasi-feature points, wherein four of the quasi-feature points corresponding to four feature points forming one quadrangle in the previous frame form one quadrangle in the current frame, and splitting, in response to the triangle information, each of the quadrangles into two triangles;

(h) determining a predicted position on the previous frame for each pixel contained in each triangle of the current frame based on positional relationships between the quasi-feature points forming said each triangle and their corresponding feature points;

(i) determining a third set of motion vectors for the pixels contained in each triangle of the current frame based on the displacement between a pixel position and its predicted position; and

(j) providing a value of each of the pixels to be contained in the predicted current frame by using each of the second and the third sets of motion vectors.