System and method for image edge detection using discrete cosine transforms

• US 5,719,958 A
• Filed: 05/15/1995
• Issued: 02/17/1998
• Est. Priority Date: 11/30/1993
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Polaroid Corporation (PLR IP Holdings LLC)
• Inventors: Reisch, Michael L., Yang, Yibing, Wober, Munib A.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/440,651
• Time in Patent Office: 1,009 Days
• Field of Search: 382/199, 382/250, 382/266, 382/263, 382/232, 382/233, 382/235, 358/433, 358/429, 348/394-425
• US Class Current: 382/199
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20052 Discrete cosine transform [DCT]
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
• CPC Class Codes: H04N 2209/046 Colour interpolation to calculate the missing colour values
• CPC Class Codes: H04N 23/84 for processing colour signals

Abstract

The image processing system of the present invention provides electronic edge detection in keeping with ISO/JPEG/MPEG international compression standards for electronic imaging. Specifically, a novel electronic image processing system for edge detection includes: an image acquisition device for acquiring and representing an image as an electronic image signal; a video memory for storing the image signal; a display for displaying the image signal; a raster to block converter for converting the image signal into block format; a DCT/IDCT processor for transforming the converted signal in accordance with predetermined basis matrices stored in a basis matrix memory; a mask multiplier for generating a mask multiplied signal in accordance with predetermined Laplacian matrices stored in an A matrix memory; a buffer for storing the mask multiplied signal; and a controller for controlling the image processing system in accordance with instructions from a central processing unit (CPU).

Claims

1. An image edge detection system comprising:

an image acquisition device for acquiring and converting an image into an image signal;

a first memory for receiving and storing said image signal;

a raster to block converter for segmenting said image signal into segments of predefined size;

a transformation section for transforming said segmented image signal into discrete cosine transform (DCT) coefficients, taking an inverse discrete cosine transform (IDCT) of the DCT coefficients, and differentiating the IDCT coefficients to generate a differentiated signal;

a block to raster converter for converting the differentiated signal into raster format then sending the converted differentiated signal to said first memory;

a threshold comparator for binarizing said converted differentiated signal by comparing said converted differentiated signal with a predetermined threshold value;

an output device for outputting, from said first memory, said binarized converted differentiated signal representing an edge detected image; and

a controller for controlling said system in accordance with predetermined instructions from a central processing unit.

2. The system of claim 1, wherein said transformation section comprises a second memory, a third memory, a first matrix multiplier, a second matrix multiplier, a transposer, a mask multiplier and a buffer, said transformation section generating said differentiated signal by:

said first matrix multiplier multiplying the segmented image signal received from the raster to block converter times a predetermined DCT basis matrix received from the second memory to generate a first signal;

said transposer transposing the first signal;

said second matrix multiplier multiplying the transposed first signal times the DCT basis matrix received from the second memory to produce a second signal;

said mask multiplier generating a mask multiplied signal by mask multiplying the second signal times a Laplacian matrix received from the third memory;

said buffer storing said mask multiplied signal;

said second matrix multiplier multiplying said mask multiplied signal received from said buffer times said IDCT basis matrix received from said second memory to produce a third signal;

said transposer transposing said third signal; and

said first matrix multiplier multiplying said transposed third signal times said IDCT basis matrix received from said second memory to produce said differentiated signal, said differentiated signal representing an edge detected image.

3. The system of claim 2, wherein said controller generates said predetermined IDCT basis matrix as a modified IDCT basis matrix evaluated at {y,x} where y and x are real number coordinate values.

4. An image edge detection system comprising:

means for acquiring an input signal corresponding to an input image represented in an XY plane, X representing a coordinate in a horizontal direction and Y representing a coordinate in a vertical direction, said input signal comprising values of input pixels of said input image, said values defining at least one spatial domain matrix spanning over a given range;

means for producing a forward discrete even cosine transform (DCT) basis matrix, an inverse discrete even cosine transform (IDCT) basis matrix, and an inverse discrete even sine transform (IDST) basis matrix;

means for producing a DCT signal comprising DCT coefficients of at least one DCT matrix by multiplying said forward DCT basis matrix times said at least one spatial domain matrix;

means for selecting a predetermined order of a derivative of said input signal in one of said horizontal and vertical directions;

means for generating a predetermined factor dependent upon a resampling interval by differentiating said forward DCT basis matrix to a first order;

means for determining said factor raised to said predetermined order;

means for generating a product by mask multiplying said factor raised to the predetermined order of the derivative times said DCT signal;

means for generating a differentiated signal of said input signal by multiplying said product times said IDCT basis matrix when said predetermined order is even, and by multiplying said product times said IDST basis matrix when said predetermined order is odd; and

means for generating an output image in response to said differentiated signal, said output image being edge detected in said one direction.

5. The system of claim 4, wherein said means for generating an output image comprises means for binarizing said differentiated signal by comparing said differentiated signal to a predetermined threshold value.

6. The system of claim 4, wherein said means for producing basis matrices generates said predetermined IDCT basis matrix as a modified IDCT basis matrix evaluated at {y,x} where y and x are real number coordinate values.

7. An image edge detection system comprising:

means for acquiring an input signal corresponding to an input image represented in an XY plane, X representing a coordinate in a horizontal direction and Y representing a coordinate in a vertical direction, said input signal comprising values of input pixels of said input image, said values defining at least one spatial domain matrix spanning over a given X range in the X direction and a given Y range in the Y direction;

means for producing a forward discrete even cosine transform (DCT) basis matrix, a forward discrete even sine transform (DST) basis matrix, an inverse discrete even cosine transform (IDCT) basis matrix and an inverse discrete even sine transform (IDST) basis matrix;

means for producing a DCT signal comprising DCT coefficients of at least one DCT matrix by multiplying said forward DCT basis matrix times said at least one spatial domain matrix;

means for selecting a predetermined X order of an X derivative in the X direction;

means for generating a predetermined X factor dependent on an X direction resampling interval by differentiating said forward DCT basis matrix to a first order with respect to X;

means for determining said X factor raised to said predetermined X order;

means for generating an X product by mask multiplying said X factor raised to the predetermined X order times said DCT signal;

means for generating an X differentiated signal by multiplying said X product times said forward DCT basis matrix when said predetermined X order is even, and by multiplying said X product times said DST basis matrix when said predetermined X order is odd;

means for selecting a predetermined Y order of a Y derivative in the Y direction;

means for generating a predetermined Y factor dependent on a Y direction resampling interval by differentiating said forward DCT basis matrix to a first order with respect to Y;

means for determining said Y factor raised to said predetermined Y order;

means for generating a Y product by mask multiplying said Y factor raised to the predetermined Y order times said DCT signal;

means for generating a Y differentiated signal by multiplying said Y product times said forward DCT basis matrix when said predetermined Y order is even, and by multiplying said second Y times said DST basis matrix when said predetermined Y order is odd;

means for generating a gradient signal by taking the square root of the sum of the squares of the X differentiated signal and the Y differentiated signal; and

means for generating an output image in response to said gradient signal, said output image being edge detected in both the X and Y directions.

8. The system of claim 7, wherein said means for generating an output image comprises means for binarizing said gradient signal by comparing said gradient signal to a predetermined threshold value.

9. The system of claim 7, wherein said means for producing basis matrices generates said predetermined IDCT basis matrix as a modified IDCT basis matrix evaluated at {y,x} where y and x are real number coordinate values.

10. An image edge detection method comprising the steps of:

acquiring and converting an image into an image signal;

receiving and storing said image signal;

segmenting said image signal into segments of predefined size;

transforming said segmented image signal into discrete cosine transform (DCT) coefficients, taking an inverse discrete cosine transform (IDCT) of the DCT coefficients, and differentiating the IDCT coefficients to generate a differentiated signal;

converting the differentiated signal into raster format;

binarizing said converted differentiated signal by comparing said converted differentiated signal with a predetermined threshold value;

outputting said binarized converted differentiated signal representing an edge detected image; and

controlling said system in accordance with predetermined instructions from a central processing unit.

11. The method of claim 10 wherein the step of taking an inverse discrete cosine transform (IDCT) of the DCT coefficients is accomplished using a modified IDCT basis matrix evaluated at {y,x} where y and x are real number coordinate values.