Method and apparatus for determining feature points

• US 5,694,487 A
• Filed: 05/04/1995
• Issued: 12/02/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-Sub
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/434,824
• Time in Patent Office: 943 Days
• Field of Search: 382/199, 382/205, 382/236, 382/201, 348/402, 348/407, 348/413, 348/416
• US Class Current: 382/201
• 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 determining feature points comprises a step for (a) providing directional gradients and a gradient magnitude for each pixel in the video frame, (b) normalizing the directional gradients by dividing the directional gradients with the gradient magnitude, (c) generating a first edge map having the gradient magnitude for each pixel, (d) generating a second edge map having the normalized direction gradients for each pixel, (e) dividing the first edge map into a plurality of blocks of an identical size, (f) providing, for each of the pixels included in each of the blocks, normalized directional gradients for a set of a predetermined number of pixels from the second edge map, (g) obtaining a variance for each of the pixels included in each of the blocks based on the provided normalized directional gradients, (h) determining a feature point for each of the blocks based on the gradient magnitude and variance corresponding to each of the pixels therein.

Claims

1. An apparatus, for use in a video signal processor which adopts a feature point based motion compensation technique, for determining feature points, said feature points being pixels capable of representing motions of objects in a video frame, comprising:

means for providing directional gradients and a gradient magnitude for each pixel in the video frame;

means for normalizing the directional gradients by dividing the directional gradients with the gradient magnitude;

means for generating a first edge map having the gradient magnitude for each pixel based on the gradient magnitude for each pixel, wherein the first edge map includes a number of edge points, each having a gradient magnitude, and a multiplicity of non-edge points, each having a zero value;

means for generating a second edge map having the normalized directional gradients for each pixel;

means for generating a plurality of grid points;

means for dividing the first edge map into a plurality of first processing blocks of an identical size, wherein the blocks do not overlap each other and each of the first processing blocks includes (N+1)×

(N+1) gradient magnitudes corresponding to the pixels therein and has a grid points at the center thereof, N being an even integer;

means for providing, for the pixels included in each of the first processing blocks, (N+1)×

(N+1) number of second processing blocks, each having normalized directional gradients for (2M+1)×

(2M+1) number of pixels from the second edge map, wherein each of the second processing blocks includes said each of the pixels included in the first processing block at center thereof, M being an odd integer;

means for obtaining a variance for each of the pixels included in each of the first processing blocks based on the provided normalized directional gradients for each of the second processing blocks; and

means for determining a feature point for each of the first processing blocks based on the gradient magnitude and variance corresponding to each of the pixels therein.

2. The apparatus according to claim 1, wherein said determination means includes:

means for selecting maximum P pixels, for each of the first processing blocks, in the order of the variances thereof beginning from a largest one, P being a predetermined number larger than 1, such that if P or more pixels having non-zero valued gradient magnitudes are included in each of the first processing blocks, P pixels are selected in a descending order of their variances, if fewer than P number of pixels having non-zero valued gradient magnitudes exist, all of those pixels are selected, and if all the pixels in each of the first processing blocks have the zero-valued gradient magnitude, no pixel is selected; and

means for determining a pixel having a largest gradient magnitude among the selected maximum pixels as the feature point for each of the blocks.

3. A method for use in a video signal processor which adopts a feature point based motion compensation technique, for determining feature points, said feature points being pixels capable of representing motions of objects in a video frame, comprising the steps of:

(a) providing directional gradients and a gradient magnitude for each pixel in the video frame;

(b) normalizing the directional gradients by dividing the directional gradients with the gradient magnitude;

(c) generating a first edge map having the gradient magnitude for each pixel based on the gradient magnitude for each pixel, wherein the first edge map includes a number of edge points, each having a gradient magnitude, and a multiplicity of non-edge points, each having a zero value;

(d) generating a second edge map having the normalized direction gradients for each pixel;

(e) generating a plurality of grid points;

(f) dividing the first edge map into a plurality of first processing blocks of an identical size, wherein the blocks do not overlap each other and each of the first processing blocks includes (N+1)×

(N+1) gradient magnitudes corresponding to the pixels therein and has a grid points at the center thereof, N being an even integer;

(g) providing, for the pixels included in each of the first processing blocks, (N+1)×

(N+1) number of second processing blocks, each having normalized directional gradients for (2M+1)×

(2M+1) number of pixels from the second edge map, wherein each of the second processing blocks includes said each of the pixels included in the first processing block at center thereof, M being an odd integer;

(h) obtaining e variance for each of the pixels included in each of the first processing blocks based on the provided normalized directional gradients for each of the second processing blocks; and

(i) determining e feature point for each of the first processing blocks based on the gradient magnitude and variance corresponding to each of the pixels therein.

4. The method in accordance with claim 3, wherein said step (h) includes the steps of:

(h1) selecting maximum P pixels, for each of the first processing blocks, in the order of the variances thereof beginning from a largest one, P being a predetermined number larger than 1, such that if P or more pixels having non-zero valued gradient magnitudes are included in each of the first processing blocks, P pixels are selected in a descending order of their variances, if fewer than P number of pixels having non-zero valued gradient magnitudes exist, all of those pixels are selected, and if all the pixels in each of the first processing blocks have the zero-valued gradient magnitude, no pixel is selected; and

(h2) determining a pixel having a largest gradient magnitude among the selected maximum pixels as the feature point for each of the blocks.