Abstract

Optical hardware for symbolic substitution is under serious consideration for parallel optical computing applications. Symbolic substitution replaces chosen patterns of ones and zeros in a binary array with other chosen patterns of ones and zeros. Implemented with specialized substitution rules, symbolic substitution can be applied to the processing of imges that are represented in binary form. Important operations investigated in this paper are (1) nonlinear filtering operations applied to shapes (morphological transformations, including erosion, dilation, opening, closing) and (2) linear filtering operations applied to binary digital representations of continuous-tone images. Examples presented include a nonlinear noise-removal operation, thresholding, a gradient operator, and convolution. The results of an engineering study of system complexity for linear filtering operations are also presented.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Huang, “Parallel Algorithms for Optical Digital Computers,” in IEEE Tenth International Optical Computing Conference, IEEE Catalog 83CH1880-4 (1983), p. 13.
    [CrossRef]
  2. A. Huang, “Architectural Considerations Involved in the Design of an Optical Digital Computer,” Proc. IEEE 72, 780 (1984).
    [CrossRef]
  3. K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
    [CrossRef] [PubMed]
  4. K.-H. Brenner, A. Huang, “An Optical Processor Based on Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985), paper WA4.
  5. J. N. Mait, K.-H. Brenner, “Optical Systems for Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), paper MB3.
  6. J. Serra, Image Analysis and Mathematical Morphology (Academic, New York, 1982).
  7. K.-H. Brenner, “New Implementation of Symbolic Substitution Logic,” Appl. Opt. 25, 3061 (1986).
    [CrossRef] [PubMed]
  8. H. K. Liu, “Coherent Optical Analog-to-Digital Conversion using a Single Halftone Photograph,” Appl. Opt. 17, 2181 (1978).
    [CrossRef] [PubMed]
  9. H. Stark, Applications of Optical Fourier Transforms (Academic, New York, 1982), Chap. 9.
  10. These rules are essentially those of an EXCLUSIVE-OR between the current Gray code bit plane and the next most significant binary bit plane.
  11. P. A. Maragos, R. W. Schafer, “Morphological Skeleton Representation and Coding in Binary Images,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 1228 (1986).
    [CrossRef]
  12. E. R. Dougherty, C. R. Giardina, Matrix Structured Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1982).
  13. A. A. Sawchuck, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
    [CrossRef]
  14. This technique is contrasted with the homomorphic filtering in H. Kato, J. W. Goodman, “Nonlinear Filtering in Coherent Optical Systems Through Halftone Screen Processes,” Appl. Opt. 14, 1813 (1975).
    [CrossRef] [PubMed]
  15. A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
    [CrossRef]
  16. B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
    [CrossRef]

1986 (4)

P. A. Maragos, R. W. Schafer, “Morphological Skeleton Representation and Coding in Binary Images,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 1228 (1986).
[CrossRef]

K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
[CrossRef] [PubMed]

K.-H. Brenner, “New Implementation of Symbolic Substitution Logic,” Appl. Opt. 25, 3061 (1986).
[CrossRef] [PubMed]

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

1984 (2)

A. Huang, “Architectural Considerations Involved in the Design of an Optical Digital Computer,” Proc. IEEE 72, 780 (1984).
[CrossRef]

A. A. Sawchuck, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
[CrossRef]

1978 (1)

1975 (1)

1961 (1)

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Avizienis, A.

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Bocker, R. P.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Brenner, K.-H.

K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
[CrossRef] [PubMed]

K.-H. Brenner, “New Implementation of Symbolic Substitution Logic,” Appl. Opt. 25, 3061 (1986).
[CrossRef] [PubMed]

K.-H. Brenner, A. Huang, “An Optical Processor Based on Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985), paper WA4.

J. N. Mait, K.-H. Brenner, “Optical Systems for Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), paper MB3.

Dougherty, E. R.

E. R. Dougherty, C. R. Giardina, Matrix Structured Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1982).

Drake, B. L.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Giardina, C. R.

E. R. Dougherty, C. R. Giardina, Matrix Structured Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1982).

Goodman, J. W.

Huang, A.

K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
[CrossRef] [PubMed]

A. Huang, “Architectural Considerations Involved in the Design of an Optical Digital Computer,” Proc. IEEE 72, 780 (1984).
[CrossRef]

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in IEEE Tenth International Optical Computing Conference, IEEE Catalog 83CH1880-4 (1983), p. 13.
[CrossRef]

K.-H. Brenner, A. Huang, “An Optical Processor Based on Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985), paper WA4.

Kato, H.

Lasher, M. E.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Liu, H. K.

Mait, J. N.

J. N. Mait, K.-H. Brenner, “Optical Systems for Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), paper MB3.

Maragos, P. A.

P. A. Maragos, R. W. Schafer, “Morphological Skeleton Representation and Coding in Binary Images,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 1228 (1986).
[CrossRef]

Micelli, W. J.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Patterson, R. H.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Sawchuck, A. A.

A. A. Sawchuck, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
[CrossRef]

Schafer, R. W.

P. A. Maragos, R. W. Schafer, “Morphological Skeleton Representation and Coding in Binary Images,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 1228 (1986).
[CrossRef]

Serra, J.

J. Serra, Image Analysis and Mathematical Morphology (Academic, New York, 1982).

Stark, H.

H. Stark, Applications of Optical Fourier Transforms (Academic, New York, 1982), Chap. 9.

Strand, T. C.

A. A. Sawchuck, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
[CrossRef]

Streibl, N.

Appl. Opt. (4)

IEEE Trans. Acoust. Speech Signal Process. (1)

P. A. Maragos, R. W. Schafer, “Morphological Skeleton Representation and Coding in Binary Images,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 1228 (1986).
[CrossRef]

IRE Trans. Electron. Comput. (1)

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Opt. Eng. (1)

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Micelli, “Photonic Computing Using the Modified Signed-Digit Number Represenation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Proc. IEEE (2)

A. A. Sawchuck, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
[CrossRef]

A. Huang, “Architectural Considerations Involved in the Design of an Optical Digital Computer,” Proc. IEEE 72, 780 (1984).
[CrossRef]

Other (7)

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in IEEE Tenth International Optical Computing Conference, IEEE Catalog 83CH1880-4 (1983), p. 13.
[CrossRef]

E. R. Dougherty, C. R. Giardina, Matrix Structured Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1982).

H. Stark, Applications of Optical Fourier Transforms (Academic, New York, 1982), Chap. 9.

These rules are essentially those of an EXCLUSIVE-OR between the current Gray code bit plane and the next most significant binary bit plane.

K.-H. Brenner, A. Huang, “An Optical Processor Based on Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985), paper WA4.

J. N. Mait, K.-H. Brenner, “Optical Systems for Symbolic Substitution,” in Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), paper MB3.

J. Serra, Image Analysis and Mathematical Morphology (Academic, New York, 1982).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1
Fig. 1

Dark and light pels for symbolic substitution patterns.

Fig. 2
Fig. 2

Decomposition of an array into bit planes. The composite array has all bits present in one large array with the most significant bit to the left.

Fig. 3
Fig. 3

Spatial representation of 0 and 1 in the dual-rail format using dark and light pels.

Fig. 4
Fig. 4

Morphological transformations: (a) original image; (b) structuring element; (c) eroded image; (d) opened image; (e) dilated image; (f) closed image.

Fig. 5
Fig. 5

Example of edge detection: (a) original image; (b) structuring element; (c) eroded image; (d) dilated image; (e) difference (exclusive-OR) between the dilated and eroded images.

Fig. 6
Fig. 6

Removal of undesirable features: (a) original image from Fig. 4 with vertical bars superimposed; (b) structuring element for isolating the bars; (c) the opening of the original; (d) the result after the vertical bars have seen EXCLUSlVE-ORed with the original image; (e) the structuring element for closing up the empty spaces; (f) the closure of the image after having been EXCLUSlVE-ORed with bars; (g) the opening of the original image with the structuring element from Fig. 6(e).

Fig. 7
Fig. 7

Substitution rules for subtracting a threshold from an array to generate a borrow and a difference. The borrow bit is displaced one position to the left indicating that the borrow is to be combined with the next most significant bit in the subsequent iteration.

Fig. 8
Fig. 8

Symbolic substitution rules for the Robert’s gradient operator. Two entries of the bit plane and the borrow are combined to give the difference and borrow for the next bit plane.

Fig. 9
Fig. 9

Spatial encoding for the bits of the MSD representation.

Fig. 10
Fig. 10

Process of multiplication using symbolic substitution: (a) An exploded view of the individual parts of the layout. (b) The substitution rule for forming the bit planes. The upper bit of the result is a duplication of the upper bit of the input. (c) The sequence of steps of multiplying −3 and 3 using three MSD bits for each number.

Fig. 11
Fig. 11

Symbolic substitution rules for MSD-to-binary conversion. (a) Basic conversion rules. (b) The sequence of steps with successive applications of the rules for the example of converting −29 from the MSD representation into the binary representation.

Tables (1)

Tables Icon

Table I Summary of the Numbers of Symbolic Substitution Rules and Iterations Required for Various Numerical Operations

Metrics