Minimum delay dilation/erosion filter

• US 5,436,984 A
• Filed: 10/26/1993
• Issued: 07/25/1995
• Est. Priority Date: 05/14/1991
• Status: Expired due to Fees

• Current Assignee: Rautaruukki Oyj (Ssab AB)
• Original Assignee: Rautaruukki Oyj (Ssab AB)
• Inventors: Tiensyraja, Kari, Sarkkinen, Timo, Piironen, Timo
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): ANDERSON, DAVID
• Application Number:
  US08/137,158
• Time in Patent Office: 637 Days
• Field of Search: 382/54, 382/27, 382/41, 382/49, 382/50, 382/53, 382/55
• US Class Current: 382/258
• CPC Class Codes: G06T 5/30 Erosion or dilatation, e.g. thinning

Abstract

A filter for performing dilation and/or erosion operations associated with mathematical morphology using a W×H rectangular structuring element to a two-dimensional matrix of discrete values, the width of the matrix being x and the height being y, includes a horizontal portion for applying the selected operation to a W×1 local neighbourhood and a vertical portion for applying the selected operation to a 1×H local neighbourhood. According to one aspect of the filer, the portions are connected one after the other and the matrix elements are applied serially to the first portion, the output of one portion being connected to the input of the other portion. Each of the above-mentioned portions includes a multiplicity of delay devices, each device providing an equal delay, and a multiplicity of comparing devices for comparing two input values. Each comparing device can produce a selected one of the lesser or greater of the input values at their output so as to permit erosion and dilation operations, respectively. According to another aspect of the invention, each portion includes a set of identical operator elements connected one after another, the horizontal portion having W such operator elements while the vertical portion having H such operator elements.

Claims

1. A filter for applying a selected one of dilation and erosion operations of mathematical morphology using a W×

H rectangular structuring element to a two-dimensional matrix of discrete values, the width of the matrix being x and the height being y, said filter comprising;

(a) a horizontal portion for applying said selected one of said dilation and erosion operations to a W×

1 local neighbourhood, said horizontal portion having an input and an output and comprising W identical operator elements connected one after another, each of said operator elements comprising;

(i) comparing means having two inputs and one output for producing the lesser or greater of the input values at said output, in the cases of said erosion and said dilation operations, respectively; and

(ii) delay means having one input and one output, the output of said comparing means being connected to the input of said delay means and the output of the delay means being connected to the first input of the comparing means of a following one of said operator elements;

the input of the horizontal portion being connected to the first input of the comparing means of a respective first operator element and also to the second input of the comparing means of each of said operator elements in the horizontal portion, the output of the delay means of the Wth of said operator elements forming the output of said horizontal portion, and

(b) a vertical portion for applying said selected one of said dilation and said erosion operations to a 1×

H local neighbourhood, said vertical portion having an input and an output and comprising;

H operator elements identical with said operator elements of the horizontal portion and connected one after another; and

H delay lines each having an input and an output and comprising x+1 further delay means connected one after another;

the input of said vertical portion being connected to both first and second inputs of the comparing means of a respective first operator element of said vertical portion and also to the input of the first of said delay lines, the output of each delay line being connected both to the second input of the comparing means of a following one of said operator elements and to the input of the following delay line, and the output of the respective Hth operator element forming the output of said vertical portion;

said horizontal and vertical portions being connected one after the other such that the output of one of said portions is connected to the input of the other of said portions, the input of the first one of said portions forming the input of the filter to which the matrix elements are serially applied, and the output of the second one of said portions forming the output of the filter.

2. A filter for applying an operation associated with mathematical morphology using a W×

H rectangular structuring element to a two-dimensional matrix of discrete values, the width of the matrix being x and the height being y, the filter comprising;

(a) a horizontal portion for applying said operation to a W×

1 local neighbourhood, said horizontal portion having an input and an output and comprising W identical horizontal operating means connected one after another, each of said operating means comprising;

(i) first comparing means having two inputs for receiving respective input values and one output for producing a comparison output; and

(ii) first delay means having one input and one output, the output of said first comparing means being connected to the input of said first delay means and the output of the first delay means being connected to the first input of the first comparing means of a following one of said horizontal operating means;

wherein the input of the horizontal portion is connected to a respective first input of the first comparing means of a respective first of said horizontal operating means and also to the second input of the first comparing means of each of said horizontal operating means;

wherein the output of the respective first delay means of the Wth of said operating means forms the output of said horizontal portion, and

(b) a vertical portion of applying said operation to a 1×

H local neighbourhood, said vertical portion having an input and an output and comprising;

H vertical operating means comprising respective second means for comparing and second means for delaying identical those associated with said horizontal operating means and connected one after another; and

H delay lines each having an input and an output and comprising x+1 further delay means for delaying connected one after another;

wherein the input of said vertical portion is connected to both first and second inputs of the second comparing means of a respective first of said vertical operating means and also to the input of the first of said delay lines,

wherein the output of each delay line is connected both to the second input of the second comparing means of a respective following one of said vertical operating means and to the input of the following one of said delay lines,

wherein the output of the respective Hth vertical operating means forms the output of said vertical portion;

wherein said horizontal and vertical portions are connected one after the other so as to permit a respective output of one of said portions to be connected to an associated input of the other of said portions,

wherein the input of the first one of said portions forms the input of the filter to which the matrix elements are serially applied, and

wherein the output of the second one of said portions forms the output of the filter.

3. The filter as recited in claim 2, wherein said operation is an erosion operation and wherein said comparing means comprises comparing means for generating said comparison value representing a minimum of said two input values.

4. The filter as recited in claim 2, wherein said operation is a dilation operation and wherein said comparing means comprises comparing means for generating said comparison value representing a maximum of said two input values.