Image edge finder which operates over multiple picture element ranges

• US 5,420,971 A
• Filed: 03/15/1994
• Issued: 05/30/1995
• Est. Priority Date: 01/07/1994
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Corporation Of America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Westerink, Peter, Devaney, Patrick, Topper, Robert, Gnanaprakasam, Daniel
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/213,127
• Time in Patent Office: 441 Days
• Field of Search: 395/126-132, 395/133, 395/134, 395/141, 395/143, 395/155, 395/161, 382/6, 382/8, 382/41, 382/47, 382/16, 382/22, 356/73.1
• US Class Current: 382/199
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges

Abstract

An edge finder for an image processing system locates edges in a digitized image over several different ranges of pixel values and assigns, to each pixel value an edge characteristic value which represents a minimum edge value for the pixel in the image. The exemplary edge finder that is able to resolve transitions occurring between two pixels or over groups of four or eight pixels to determine whether an edge should be defined between the original two pixels. The edge finder simultaneously examines four edges in two dimensions to determine the edgeness value for each pixel in the digitized image.

Claims

1. Apparatus for processing a matrix of picture element (pixel) data values representing an image, to define edges within the image comprising:

means for defining a potential edge location in a predetermined direction between first and second ones of the pixel data values which first and second pixel data values are adjacent in the matrix of pixel data values;

means for determining a first edge strength value in the predetermined direction said first edge strength value being a measure of a difference in magnitude between the first and second pixel data values;

manes for determining a second edge strength value in the predetermined direction said second edge strength value being a measure of a difference in magnitude over a group of N successive pixel data values in the predetermined direction where N is an integer greater than 2, the N successive pixel values being defined on the matrix of pixel data and including the first and second pixel data values;

means for analyzing the N pixel data values to determine if the N pixel data values define an edge at the potential edge location and for modifying the second edge strength value to indicate a null edge if it is determined that the N pixel values do not define an edge at the potential edge location;

means for comparing the first edge strength value to the second edge strength value to assign one of the first and second edge strength values to the potential edge location.

2. Apparatus according to claim 1, wherein each pixel data value in the matrix of pixel data values defines four link values to pixel data values in respective directions above, below, to the right of and to the left of the pixel data value in the matrix, the apparatus further comprising:

means for determining a respective edge strength value for each of the four links, representing the four respective directions, for each pixel data value in the matrix; and

means for selecting one of the four edge strength values of each one pixel data value in the matrix as an edgeness value for the one pixel data value.

3. Apparatus according to claim 2 further including:

means for comparing each of the edge strength values of each of the four links for each pixel value in the matrix to a threshold value; and

means for associating with each one pixel value in the matrix, an indication of the relative magnitude of each of the edge strength values of the one pixel value and the threshold value.

4. Apparatus for processing a matrix of picture element values representing an image, to locate edges within the image comprising:

first edge evaluation means, responsive to a first set of the pixel values in the matrix for determining a first magnitude value for an edge in a predetermined direction between first and second ones of the pixel values in the first set of pixel values

second edge evaluation means, responsive to a second set of the pixel values in the matrix, the second set of pixel values being arranged in the predetermined direction in the matrix, having a greater number of pixel values than the first set of pixel values and including the first set of pixel values, for determining a second magnitude for the edge between the first and second pixel values; and

means for comparing the first and second edge magnitudes to assign one of the first and second edge magnitudes as an edge value between the first and second pixel values.

5. Apparatus for processing a matrix of picture element (pixel) data representing an image, to locate edges within the image comprising:

first edge evaluation means, responsive to a first set of pixel values in the matrix for determining a first magnitude value for an edge between first and second pixel values in the first set of pixel values

second edge evaluation means, responsive to a second set of pixel values in the matrix, the second set having a greater number of pixel values than the first set and including the first set of pixel values, for determining a second magnitude for the edge between the first and second pixel values wherein the first set of pixel values is composed of the first and second pixel values and the second set of pixel values includes the first and second pixel values and third and fourth pixel values at either end of a line in the matrix defined by the first and second pixel values; and

means for comparing the first and second edge magnitudes to assign one of the first and second edge magnitudes as an edge value between the first and second pixel values.

6. Apparatus according to claim 5, wherein the second edge evaluation means includes:

means for processing the second set of pixel values to produce first and second parameters which define a normalized profile of the second set of pixel values;

means for processing the second set of pixel values to produce a third parameter which defines the second magnitude;

edge profile means for processing the first and second parameters to determine if the second set of pixel values defines an edge between the first and second pixel values; and

means, coupled to the edge profile means, for providing the third parameter as the second magnitude if the edge profile means determines that the second set of pixel values defines an edge between the first and second pixel values and for providing a null value as the second magnitude otherwise.

7. A method for processing a matrix of picture element (pixel) data values representing an image, to define edges within the image, the method comprising the steps of:

defining a potential edge location in a predetermined direction between first and second ones of the pixel data values which first and second pixel data values are adjacent in the matrix of pixel data values;

determining a first edge strength value in the predetermined direction as being a difference in magnitude between the first and second pixel data values;

determining a second edge strength value in the predetermined direction as being a difference in magnitude over a group of N successive ones of the pixel data values in the predetermined direction where N is an integer greater than 2, the group of N successive pixel values being defined on the matrix of pixel data values and including the first and second pixel data values;

analyzing the N pixel data values to determine if the N pixel data values have a profile consistent with an edge at the potential edge location and for modifying the second edge strength value to indicate a null edge if it is determined that the N pixel values are not consistent with an edge at the potential edge location;

comparing the first edge strength value to the second edge strength value to assign one of the first and second edge strength values to the potential edge location.