Browse Prior Art Database

Fast One Pixel Edge Detector

IP.com Disclosure Number: IPCOM000060904D
Original Publication Date: 1986-May-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Dom, BE: AUTHOR

Abstract

An algorithm and circuit provide for fast generation of single pixel thick edges from a grey scale image by comparing neighboring pixels in the direction of the local gradient. The topological properties of the detected edge regions are retained while the number of edge pixels is greatly reduced. In regions where the edge orientation is constant, the edges are only one pixel thick regardless of edge strength and extent. The edge detector is asignificant improvement over that which is known in the art in that it responds with roughly single pixel thick edges regardless of edge strength and width, provides the orientation of the detected edge, and operates successfully on complex grey-scale images. The algorithm works by first detecting edge pixels using agradient operator.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 3

Fast One Pixel Edge Detector

An algorithm and circuit provide for fast generation of single pixel thick edges from a grey scale image by comparing neighboring pixels in the direction of the local gradient. The topological properties of the detected edge regions are retained while the number of edge pixels is greatly reduced. In regions where the edge orientation is constant, the edges are only one pixel thick regardless of edge strength and extent. The edge detector is asignificant improvement over that which is known in the art in that it responds with roughly single pixel thick edges regardless of edge strength and width, provides the orientation of the detected edge, and operates successfully on complex grey-scale images. The algorithm works by first detecting edge pixels using agradient operator. Any gradient operator that is based on two equivalent orthogonal difference components may be used. In this example, Robert's [1] gradient will be used, but other similar operators such as the Prewitt [2] and Sobel [3] can also be used. The gradient image is thresholded and the edges detected in that image are effectively thinned using a form of non-maximum suppression which takes both edge magnitude and direction into account. On a square image grid the Robert's operator gives a value which corresponds to the intersection of the boundaries of four adjacent pixels. The mathematical expression for the operator is:

(Image Omitted)

where

(Image Omitted)

The edge direction is quantized into eight sectors centered about the eight cardinal directions. The algorithm, uses the arctan function to determine the direction of the gradient from W+ and W_. The following is an APL function that computes Robert's gradient, thresholds it, and computes the quantized edge direction for the detected edge pixels. An image k is formed where each pixel contains the quantized edge direction for each detected pixel in the thresholded gradient image and zero for non-detected pixels. The edge-thinning processing then takes the edge direction image, k, and the Robert's gradient image, R, as inputs. For each non-zero pixel in k two nearest neighbor pixels are examined - the one in the k direction (call its value k) and the one in the opposite (complementary) direction (call it kc). If k = k and R > R or kc = k and Rc > R then k is set to zero; otherwise, it is left as it is. A circuit for performing this algorithm at high speed is shown in the figure. The concept for the circuit is to use apipeline architecture where as many operations as possible are performed in parallel at each stage in the pipeline. Pixel data and intermediate results are clocked through the circuit from left to right. It is assumed that the image is scanned in a raster scan fashion - bottom to top, left to right. This data could be coming from a high speed video digitizer ("frame grabber") for example. Working from left to right in the figure, the components making up the circuit are as foll...