System incorporating feature-oriented signal enhancement using shock filters

• US 5,644,513 A
• Filed: 04/16/1993
• Issued: 07/01/1997
• Est. Priority Date: 12/22/1989
• Status: Expired due to Term

• Current Assignee: Rudin, Leonid I., Stanley osher
• Original Assignee: Rudin, Leonid I., Stanley osher
• Inventors: Osher, Stanley, Rudin, Leonid I.
• Primary Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US08/049,637
• Time in Patent Office: 1,537 Days
• Field of Search: 364/570, 364/572, 364/574, 367/24, 367/43, 367/100, 395/128, 382/22, 382/54, 382/266, 382/269
• US Class Current: 702/190
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A method and apparatus for enhancing signals such as images, speech, remotely sensed data, medical, tactile, radar and audio. It proceeds by the construction of certain discrete approximations to certain nonlinear time-dependent partial differential equations. These approximations preserve the variation of the discrete solution as discrete time increases for one space dimension. The approximate solutions satisfy certain maximum principles in one and two dimensions. Thus, the method enhances images and other general signals without being plagued by the phenomenon of ringing near edges and other features, or by smearing of these edges and other features, typical of the prior art. As discrete time increases the signal is enhanced. The process may reach steady state, but for some applications, the dynamical procedure is important. The method is fast, requiring only local operations on a special purpose computer described herein.

Claims

1. A method for performing edge-enhancement of an N-dimensional original image containing transitions corresponding to edges in said image, said transitions corresponding to different respective edge pixel values on respective sides of a given edge, so as to produce an edge-enhanced image in data processing apparatus of the type wherein said original image is represented by an array of pixels having respective pixel values, said method comprising the following steps:

(1. ) propagating pixel value changes toward respective edges from all sides thereof in successive iterations while prohibiting propagation of the pixel value changes across any of said edges, each said successive iteration of said propagating step comprising;

(a) computing for each one of said dimensions a respective change in the value of each respective one of said pixels toward the corresponding edge pixel value in accordance with a difference between values of said one pixel and a neighboring pixel further away from an edge nearest said one pixel along said one dimension,

(b) combining the changes computed for said one pixel for each of said dimensions to produce a combined pixel value change for said one pixel, and changing said original image in accordance with the combined pixel value changes of said pixels to produce an enhanced image, and substituting said enhanced image for said original image; and

(2. ) transmitting an enhanced image of a latest iteration to an image output device for one of displaying and recording of said enhanced image.

2. The method of claim 1 wherein said computing step comprises multiplying each difference by an edge detection function which changes sign across any edge in said image.

3. The method of claim 2 wherein said combining step comprises computing a sum of absolute values of the differences computed for all of said dimensions.

4. The method of claim 3 wherein said computing and combining steps comprise:

computing said differences in forward and backward directions along the respective dimension relative to the edge nearest said one pixel to produce forward and backward differences respectively for all pixels of said image along all dimensions of said image;

computing a sum of absolute values of positive terms of said forward differences and negative terms of said backward differences and multiplying said sum by negative terms of said edge detection function; and

computing a sum of absolute values of negative terms of said forward differences and positive terms of said backward differences and multiplying said sum by positive terms of said edge detection function.

5. The method of claim 4 wherein said image is one-dimensional and said edge detection function corresponds to a second derivative.

6. The method of claim 4 wherein said image is multi-dimensional and said edge detection function corresponds to a component of a Laplacian operator.

7. The method of claim 4 wherein each of said edges corresponds to a zero-crossing in said image.

8. The method of claim 1 wherein said enhanced image has a total variation which is no greater than the total variation of said original image.

9. The method of claim 1 wherein said repeating is carried out until the differences between enhanced images of successive iterations is less than a predetermined threshold.

10. A system for performing edge-enhancement of an N-dimensional original image containing transitions corresponding to edges in said image, said transitions corresponding to different respective edge pixel values on respective sides of a given edge, so as to produce an edge-enhanced image, wherein said original image is represented by an array of pixels having respective pixel values, said system comprising:

(1. ) means for propagating combined pixel value changes toward respective edges from all sides thereof in successive iterations while prohibiting propagation of the combined pixel value changes across any of said edges, said means for propagating comprising;

(a) means operative in each one of said successive iterations for computing for each one of said dimensions a respective change in the value of each respective one of said pixels toward the corresponding edge pixel value in accordance with a difference between values of said one pixel and a neighboring pixel further away from an edge nearest said one pixel along said one dimension,

(b) means operative in each one of said successive iterations for combining the changes computed for said one pixel for each of said dimensions to produce a combined pixel value change for said one pixel, and for changing said original image in accordance with the combined pixel value changes of said pixels to produce an enhanced image, and for substituting said enhanced image for said original image; and

(2. ) means for transmitting an enhanced image of a latest iteration to an image output device for one of displaying and recording of said enhanced image.

11. The system of claim 10 wherein said means for computing comprises means for multiplying each difference by an edge detection function which changes sign across any edge in said image.

12. The system of claim 11 wherein said means for combining comprises means for computing a sum of absolute values of the differences computed for all of said dimensions.

13. The system of claim 12 wherein said means for computing and said means for combining comprise:

means for computing said differences in forward and backward directions along the respective dimension relative to the edge nearest said one pixel to produce forward and backward differences respectively for all pixels of said image along all dimensions of said image;

means for computing a sum of absolute values of positive terms of said forward differences and negative terms of said backward differences and multiplying said sum by negative terms of said edge detection function; and

means for computing a sum of absolute values of negative terms of said forward differences and positive terms of said backward differences and for multiplying said sum by positive terms of said edge detection function.

14. The system of claim 13 wherein said image is one-dimensional and said edge detection function corresponds to a second derivative.

15. The system of claim 13 wherein said image is multi-dimensional and said edge detection function corresponds to a component of a Laplacian operator.

16. The system of claim 13 wherein each of said edges corresponds to a zero-crossing in said image.

17. The system of claim 10 wherein said enhanced image has a total variation which is no greater than the total variation of said original image.

18. The system of claim 10 wherein the number of said iterations is such that a last iteration is performed in which the differences between enhanced images of successive iterations is less than a predetermined threshold.