Apparatus and method for implementing dilation and erosion transformations in digital image processing

• US 4,665,554 A
• Filed: 07/13/1983
• Issued: 05/12/1987
• Est. Priority Date: 07/13/1983
• Status: Expired due to Fees

• Current Assignee: Machine Vision International Corporation
• Original Assignee: Machine Vision International Corporation
• Inventors: Sternberg, Stanley R.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/513,448
• Time in Patent Office: 1,399 Days
• Field of Search: 382/27, 382/49-50, 382/54, 333/165, 307/606, 307/607
• US Class Current: 382/308
• CPC Class Codes: G06T 5/30 Erosion or dilatation, e.g. thinning
• CPC Class Codes: G06V 10/20 Image preprocessing

Abstract

The specification discloses a system and a method for processing digital representations of images to produce dilations and erosions at unparalleled speeds and efficiencies. The system includes digital circuitry for effecting a dilation by repetitively delaying the serialized digital image and ORing the delayed digital image back into the serial signal stream.

Claims

1. A method of manipulating an input digital representation of an image made up of a matrix of points by a dynamically selectable structuring element to produce an output digital representation, said method comprising:

processing the input digital representation through a plurality of sequential stages, each stage including;

selectively shifting the digital representation inputted to the stage; and

operating on the representation inputted to the stage and the representation shifted by the stage to produce a digital representation outputted by the stage; and

control means for dynamically selecting the shift provided by each shifting step, whereby the input digital representation can be sequentially shifted in a dynamically selectable pattern corresponding to a selectable structuring element.

2. A method as defined in claim 1 further comprising first serializing the input digital image representation.

3. A method as defined in claim 2 wherein each of said shifting steps comprises delaying the serialized digital signal inputted to that stage.

4. A method as defined in claim 3 wherein said selective delaying step includes controlling a programmable delay circuit.

5. A method as defined in claim 1 wherein the structuring element is polar symmetric.

6. A method as defined in claim 5 wherein the pattern represents translations between extreme points of the polar symmetric structuring element.

7. A method as defined in claim 1 wherein said operating step comprises selecting the maximum of the representation inputted to the stage and shifted by the stage.

8. A method of processing at least one image each made up of a matrix of points by a selectable structuring element, said method comprising:

serializing each matrix of points into an input serial signal;

repetitively performing the steps of;

controllably delaying at least one of the input serial signals to produce a delayed serial signal; and

operating on selected ones of the input serial signals and the delayed serial signals to produce at least one output signal; and

controlling the delay provided in each delaying step so that each input serial signal is delayed in a controllable pattern representing the selectable structuring element.

9. A method as defined in claim 8 wherein said operating step comprises selecting the maximum of the selected input and delayed signals.

10. A method as defined in claim 9 wherein the signals are binary and further wherein said selecting step comprises ORing one of the delayed signals and one of the input signals to produce the output signals.

11. A method as defined in claim 8 wherein said selective delaying step includes controlling a programmable delay circuit.

12. A method of processing a digital image representing a matrix of points by a selectable structuring element, said method comprising:

serializing the digital image into a serial signal;

repetitively performing the steps of;

controllably shifting the serial signal to produce a shifted serial signal; and

operating on the serial signal and the shifted serial signal to produce an output serial signal; and

dynamically controlling the shift provided by each shifting step to effect processing by a selectable structuring element.

13. A method as defined in claim 12 wherein each of said shifting steps comprises delaying the serial signal.

14. A method as defined in claim 13 wherein each matrix point is represented by a binary value of 0 or 1 and further wherein each of said operating steps comprises ORing the signals inputted to and delayed by the associated step group.

15. A method as defined in claim 13 wherein said selective delaying step includes controlling a programmable delay circuit.

16. A method as defined in claim 12 wherein each matrix point is represented by a binary value of 0 or 1 and further wherein each of said operating steps comprises ORing the serial signal and the shifted serial signal.

17. A method as defined in claim 12 wherein said operating step comprises selecting the maximum of the first serial signal and the second serial signal.

18. A method of manipulating at least one input serial signal each representative of an image to produce at least one resultant serial signal each representative of an image processed by a variable structuring element, said method comprising:

routing each input serial signal through a plurality of processing sequences each including;

supplying at least one serial signal each to an input port;

delaying at least one of the serial signals to produce at least one delayed signal each corresponding to one of the serial signals; and

operating on selected ones of the delayed signals and the serial signals to produce at least one output serial signal; and

varying the delay provided by each delaying step as each serial signal is routed therethrough so that each input signal is delayed in a variable pattern corresponding to a variable structuring element.

19. A method as defined in claim 18 wherein said operating step comprises selecting the maximum of the selected ones of the delayed signals and the serial signals.

20. A method as defined in claim 19 wherein the serial signals are binary signals and further wherein said selecting step comprises ORing one of the delayed signals and one of the serial signals.

21. A method as defined in claim 18 wherein said selective delaying step includes controlling a programmable delay circuit.

22. A system for processing a start image made up of a matrix of points by a dynamically selectable structuring element, said system comprising:

serializing means for producing a first serial signal representative of the start image;

a plurality of serially coupled processing stages each including;

controllable delay means for variably delaying the serial signal inputted to the stage producing a delay serial signal; and

function means for operating on the inputted serial signal and the delay serial signal producing an output serial signal outputted to the next stage; and

control means for dynamically controlling said delay means to delay the serialized signals in a pattern representing a dynamically selectable structuring element.

23. A system as defined in claim 22 wherein each point is represented by a binary value of 0 or 1 and further wherein said function means comprises means for ORing said inputted serial signal and said delay serial signal.

24. A system as defined in claim 22 wherein said function means comprises select means for selecting the maximum of the inputted serial signal and the delay serial signal.

25. A system for processing at least one serial signal each representative of an image made up of a matrix of points to produce at least one serial signal each representative of an image processed by a dynamically selectable structuring element, said system comprising:

at least one geometric logic unit, each including;

input port means for receiving at least one input serial signal;

controllable delay means for delaying at least one selected input signal to produce at least one delayed serial signal each corresponding to one of the input signals;

function means for operating on selected ones of the delayed and input signals to produce at least one output serial signal; and

output port means for outputting each output signal; and

first control means for routing the serial signal through a geometric logic unit at least twice; and

second control means for dynamically controlling the delay provided by each said delay means each time the serial signal passes therethrough, whereby the serial signal can be delayed in a dynamically selectable pattern corrresponding to a dynamically selectable structuring element.

26. A system as defined in claim 25 wherein said function means comprises means for selecting the maximum of the selected ones of the delayed and input signals.

27. A system as defined in claim 26 wherein the serial signals are binary signals and further wherein said function means comprises means for ORing the selected ones of the delayed and input signals.

28. A system as defined in claim 25 wherein said delay means comprises a controllable variable delay circuit.

29. An image processing system for processing at least one start image each made up of a matrix of points by a selectable structuring element, said system comprising:

serializing means for producing at least one start serial signal each representative of one of the start images;

controllable delay means for variably time-delaying selected ones of the signals inputted thereto to produce at least one delayed serial signal each corresponding to one of the input signals;

operating means for operating on selected ones of the delayed signals and the input signals to produce at least one output serial signal; and

first control means for repetitively routing the selected ones of the input signals through said delay means and said operating means; and

second control means for controlling the length of the time delay provided by said delay means each time an input signal is delayed therethrough to effect processing by a selectable structuring element.

30. A system as defined in claim 29 wherein said signals are binary signals and further wherein said operating means comprises means for ORing one of the delay signals and one of the input signals.

31. A system as defined in claim 29 wherein said operating means comprises select means for selecting the maximum of the selected delayed and input signals.