Abstract

A binary image algebra (BIA) that gives a mathematical description of parallel processing operations is described. Rigorous and concise BIA representations of parallel arithmetic and symbolic substitution operations are given. A sequence of programming steps for implementation of these operations on a parallel architecture is specified by the BIA representation. Examples of arithmetic operations implemented on a digital optical cellular image processor architecture are given.

© 1989 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. A. Sawchuk, T. C. Strand, “Digital Optical Computing,” Proc. IEEE 72, 758 (1984).
    [CrossRef]
  2. Special Issue on Optical Computing, Proc. IEEE 72, No. 7 (1984).
  3. A. Huang, Y. Tsunoda, J. W. Goodman, S. Ishihara, “Optical Computation Using Residue Arithmetic,” Appl. Opt. 18, 149 (1979).
    [CrossRef] [PubMed]
  4. D. Psaltis, D. Casasent, “Optical Residue Arithmetic: A Correlation Approach,” Appl. Opt. 18, 163 (1979).
    [CrossRef] [PubMed]
  5. F. A. Horrigan, W. W. Stoner, “Residue-Based Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 185, 19 (1979).
  6. A. M. Tai, I. Cindrich, J. R. Fienup, C. C. Aleksoff, “Optical Residue Arithmetic Computer with Programmable Computation Modules,” Appl. Opt. 18, 2812 (1979).
    [CrossRef] [PubMed]
  7. G. Abraham, “Multiple-Values Logic for Optoelectronics,” Opt. Eng. 25, 3 (1986).
    [CrossRef]
  8. T. T. Tao, D. M. Campbell, “Multiple-Valued Logic: An Implementation,” Opt. Eng. 25, 14 (1986).
  9. R. Arrathoon, S. Kozaitis, “Shadow Casting for Multiple-Valued Associative Logic,” Opt. Eng. 25, 29 (1986).
    [CrossRef]
  10. S. L. Hurst, “Multiple-Valued Threshold Logic: Its Status and Its Realization,” Opt. Eng. 25, 44 (1986).
    [CrossRef]
  11. B. K. Jenkins, A. A. Sawchuk, T. C. Strand, R. Forchheimer, B. H. Soffer, “Sequential Optical Logic Implementation,” Appl. Opt. 23, 3455 (1984).
    [CrossRef] [PubMed]
  12. B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T.C. Strand, “Architectural Implications of a Digital Optical Processor,” Appl. Opt. 23, 3465 (1984).
    [CrossRef] [PubMed]
  13. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Digital Optical Cellular Image Processors,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 20–23.
  14. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).
  15. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures Based on Binary Image Algebra,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle (Oct.1987), pp. 19 –26.
  16. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.
  17. A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference (1983), pp. 13 –17.
  18. K. Brenner, A. Huang, “An Optical Processor Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985), paper WA4.
  19. K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
    [CrossRef] [PubMed]
  20. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra Representations of Optical Cellular Logic and Symbolic Substitution,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).
  21. D. Psaltis, R. A. Athale, “High Accuracy Computation with Linear Analog Optical Systems: A Critical Study,” Appl. Opt. 25, 3071 (1986).
    [CrossRef] [PubMed]
  22. J. Serra, Image Analysis and Mathematical Morphology (Academic, New York, 1982).
  23. K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Programming a Digital Optical Cellular Image Processor,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).
  24. B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures for Image Processing,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Florida (Nov.1985), pp. 61–65.
  25. K.-H. Brenner, “New Implementation of Symbolic Substitution Logic,” Appl. Opt. 25, 3061 (1986).
    [CrossRef] [PubMed]
  26. K.-H. Brenner, G. Stucke, “Programmable Optical Processor Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 6–8.
  27. J. N. Mait, K.-H. Brenner, “Optical Systems for Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 12–15.
  28. T. J. Cloonan, “Strengths and Weaknesses of Optical Architectures Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 12–15.
  29. C. D. Capps, R. A. Falk, T. L. Houk, “Optical Arithmetic/Logic Unit Based on Residue Number Theory and Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 62–65.
  30. P. A. Ramamoorthy, S. Antony, “Optical MSD Adder Using Polarization Coded Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 111–114.
  31. Jeon Ho-In, “Digital Optical Processor Based on Symbolic Substitution Using Matched Filtering,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 115–118.
  32. M. T. Taso et al., “Symbolic Substitution Using ZnS Interference Filters,” Opt. Eng. 26, 41 (1987).

1989 (1)

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.

1987 (2)

M. T. Taso et al., “Symbolic Substitution Using ZnS Interference Filters,” Opt. Eng. 26, 41 (1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).

1986 (7)

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]

D. Psaltis, R. A. Athale, “High Accuracy Computation with Linear Analog Optical Systems: A Critical Study,” Appl. Opt. 25, 3071 (1986).
[CrossRef] [PubMed]

G. Abraham, “Multiple-Values Logic for Optoelectronics,” Opt. Eng. 25, 3 (1986).
[CrossRef]

T. T. Tao, D. M. Campbell, “Multiple-Valued Logic: An Implementation,” Opt. Eng. 25, 14 (1986).

R. Arrathoon, S. Kozaitis, “Shadow Casting for Multiple-Valued Associative Logic,” Opt. Eng. 25, 29 (1986).
[CrossRef]

S. L. Hurst, “Multiple-Valued Threshold Logic: Its Status and Its Realization,” Opt. Eng. 25, 44 (1986).
[CrossRef]

1984 (4)

1979 (4)

Abraham, G.

G. Abraham, “Multiple-Values Logic for Optoelectronics,” Opt. Eng. 25, 3 (1986).
[CrossRef]

Aleksoff, C. C.

Antony, S.

P. A. Ramamoorthy, S. Antony, “Optical MSD Adder Using Polarization Coded Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 111–114.

Arrathoon, R.

R. Arrathoon, S. Kozaitis, “Shadow Casting for Multiple-Valued Associative Logic,” Opt. Eng. 25, 29 (1986).
[CrossRef]

Athale, R. A.

Brenner, K.

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

Brenner, K.-H.

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

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

K.-H. Brenner, G. Stucke, “Programmable Optical Processor Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 6–8.

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

Campbell, D. M.

T. T. Tao, D. M. Campbell, “Multiple-Valued Logic: An Implementation,” Opt. Eng. 25, 14 (1986).

Capps, C. D.

C. D. Capps, R. A. Falk, T. L. Houk, “Optical Arithmetic/Logic Unit Based on Residue Number Theory and Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 62–65.

Casasent, D.

Chavel, P.

Cindrich, I.

Cloonan, T. J.

T. J. Cloonan, “Strengths and Weaknesses of Optical Architectures Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 12–15.

Falk, R. A.

C. D. Capps, R. A. Falk, T. L. Houk, “Optical Arithmetic/Logic Unit Based on Residue Number Theory and Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 62–65.

Fienup, J. R.

Forchheimer, R.

Goodman, J. W.

Ho-In, Jeon

Jeon Ho-In, “Digital Optical Processor Based on Symbolic Substitution Using Matched Filtering,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 115–118.

Horrigan, F. A.

F. A. Horrigan, W. W. Stoner, “Residue-Based Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 185, 19 (1979).

Houk, T. L.

C. D. Capps, R. A. Falk, T. L. Houk, “Optical Arithmetic/Logic Unit Based on Residue Number Theory and Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 62–65.

Huang, A.

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

A. Huang, Y. Tsunoda, J. W. Goodman, S. Ishihara, “Optical Computation Using Residue Arithmetic,” Appl. Opt. 18, 149 (1979).
[CrossRef] [PubMed]

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

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference (1983), pp. 13 –17.

Huang, K. S.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra Representations of Optical Cellular Logic and Symbolic Substitution,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Programming a Digital Optical Cellular Image Processor,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures Based on Binary Image Algebra,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle (Oct.1987), pp. 19 –26.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Digital Optical Cellular Image Processors,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 20–23.

Hurst, S. L.

S. L. Hurst, “Multiple-Valued Threshold Logic: Its Status and Its Realization,” Opt. Eng. 25, 44 (1986).
[CrossRef]

Ishihara, S.

Jenkins, B. K.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).

B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T.C. Strand, “Architectural Implications of a Digital Optical Processor,” Appl. Opt. 23, 3465 (1984).
[CrossRef] [PubMed]

B. K. Jenkins, A. A. Sawchuk, T. C. Strand, R. Forchheimer, B. H. Soffer, “Sequential Optical Logic Implementation,” Appl. Opt. 23, 3455 (1984).
[CrossRef] [PubMed]

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Programming a Digital Optical Cellular Image Processor,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra Representations of Optical Cellular Logic and Symbolic Substitution,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Digital Optical Cellular Image Processors,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 20–23.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures Based on Binary Image Algebra,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle (Oct.1987), pp. 19 –26.

B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures for Image Processing,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Florida (Nov.1985), pp. 61–65.

Kozaitis, S.

R. Arrathoon, S. Kozaitis, “Shadow Casting for Multiple-Valued Associative Logic,” Opt. Eng. 25, 29 (1986).
[CrossRef]

Mait, J. N.

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

Psaltis, D.

Ramamoorthy, P. A.

P. A. Ramamoorthy, S. Antony, “Optical MSD Adder Using Polarization Coded Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 111–114.

Sawchuk, A. A.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).

B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T.C. Strand, “Architectural Implications of a Digital Optical Processor,” Appl. Opt. 23, 3465 (1984).
[CrossRef] [PubMed]

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

B. K. Jenkins, A. A. Sawchuk, T. C. Strand, R. Forchheimer, B. H. Soffer, “Sequential Optical Logic Implementation,” Appl. Opt. 23, 3455 (1984).
[CrossRef] [PubMed]

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra Representations of Optical Cellular Logic and Symbolic Substitution,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Programming a Digital Optical Cellular Image Processor,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures Based on Binary Image Algebra,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle (Oct.1987), pp. 19 –26.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Digital Optical Cellular Image Processors,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 20–23.

B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures for Image Processing,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Florida (Nov.1985), pp. 61–65.

Serra, J.

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

Soffer, B. H.

Stoner, W. W.

F. A. Horrigan, W. W. Stoner, “Residue-Based Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 185, 19 (1979).

Strand, T. C.

Strand, T.C.

Streibl, N.

Stucke, G.

K.-H. Brenner, G. Stucke, “Programmable Optical Processor Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 6–8.

Tai, A. M.

Tao, T. T.

T. T. Tao, D. M. Campbell, “Multiple-Valued Logic: An Implementation,” Opt. Eng. 25, 14 (1986).

Taso, M. T.

M. T. Taso et al., “Symbolic Substitution Using ZnS Interference Filters,” Opt. Eng. 26, 41 (1987).

Tsunoda, Y.

Appl. Opt. (8)

Comput. Vision Graphics Image Process. (1)

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Optical Cellular Logic Processor Design,” Comput. Vision Graphics Image Process.Feb.1989.

Opt. Eng. (5)

M. T. Taso et al., “Symbolic Substitution Using ZnS Interference Filters,” Opt. Eng. 26, 41 (1987).

G. Abraham, “Multiple-Values Logic for Optoelectronics,” Opt. Eng. 25, 3 (1986).
[CrossRef]

T. T. Tao, D. M. Campbell, “Multiple-Valued Logic: An Implementation,” Opt. Eng. 25, 14 (1986).

R. Arrathoon, S. Kozaitis, “Shadow Casting for Multiple-Valued Associative Logic,” Opt. Eng. 25, 29 (1986).
[CrossRef]

S. L. Hurst, “Multiple-Valued Threshold Logic: Its Status and Its Realization,” Opt. Eng. 25, 44 (1986).
[CrossRef]

Proc. IEEE (2)

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

Special Issue on Optical Computing, Proc. IEEE 72, No. 7 (1984).

Proc. Soc. Photo-Opt. Instrum. Eng. (2)

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “A Cellular Hypercube Architecture for Image Processing,” Proc. Soc. Photo-Opt. Instrum. Eng. 829, 331 (1987).

F. A. Horrigan, W. W. Stoner, “Residue-Based Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 185, 19 (1979).

Other (14)

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra Representations of Optical Cellular Logic and Symbolic Substitution,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

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

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Programming a Digital Optical Cellular Image Processor,” in Technical Digest of 1987 Annual Meeting (Optical Society of America, Washington, DC, 1987).

B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures for Image Processing,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Florida (Nov.1985), pp. 61–65.

K.-H. Brenner, G. Stucke, “Programmable Optical Processor Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 6–8.

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

T. J. Cloonan, “Strengths and Weaknesses of Optical Architectures Based on Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 12–15.

C. D. Capps, R. A. Falk, T. L. Houk, “Optical Arithmetic/Logic Unit Based on Residue Number Theory and Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 62–65.

P. A. Ramamoorthy, S. Antony, “Optical MSD Adder Using Polarization Coded Symbolic Substitution,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 111–114.

Jeon Ho-In, “Digital Optical Processor Based on Symbolic Substitution Using Matched Filtering,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 115–118.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Optical Cellular Logic Architectures Based on Binary Image Algebra,” in Proceedings, IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle (Oct.1987), pp. 19 –26.

K. S. Huang, B. K. Jenkins, A. A. Sawchuk, “Binary Image Algebra and Digital Optical Cellular Image Processors,” in Technical Digest of Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987), pp. 20–23.

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference (1983), pp. 13 –17.

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

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 (21)

Fig. 1
Fig. 1

Example of fundamental operations: complement −, union ∪, and dilation ⊕.

Fig. 2
Fig. 2

Some standard derived image operations. The shaded regions in (1)−(d) correspond to pixels with value 1: (a) difference; (b) intersection; (c) erosion; (d) symmetric difference; (e) hit or miss transform (template matching).

Fig. 3
Fig. 3

Digital optical cellular image processor (DOCIP) architecture—one implementation of binary image Algebra (BIA). The DOCIP-array requires 9 (or 5) control bits for reference image Ei. The DOCIP-hypercube requires O(logN) control bits for reference image Ei.

Fig. 4
Fig. 4

DOCIP physical concept. Each processing element (PE) or cell connects with its cellular array or cellular hypercube neighbors and itself by optical 3-D interconnections. The optical hologram provides both intracell and intercell interconnections. Intracell interconnections and imaging optics are omtted for clarity. The input and output sides of the optical gate array are interconnected by an optical feedback path and are shown separately for clarity.

Fig. 5
Fig. 5

Binary row-coded numbers.

Fig. 6
Fig. 6

Parallel addition of binary row-coded numbers (I): (a) image X of operands; (b) image R of other operands; (c) output X + R.

Fig. 7
Fig. 7

Parallel addition of binary row-coded numbers (II): The procedure for parallel addition X + R where X and R are shown in Fig. 6. S(t5), = S = X + R and C(t5) = ϕ.

Fig. 8
Fig. 8

Parallel (matrix-constant) multiplication of binary row-coded numbers: (a) image X of operands; (b) image Rr containing only a single number; (c) output XRr.

Fig. 9
Fig. 9

Parallel (element–element) multiplication of binary row-coded numbers: (a) image X of operands; (b) image R of other operands; (c) output X × R; (d) mask M; (e) image j   =   0 k     1 A j ; (f) image ( R M ) j   =   0 k     1 A j .

Fig. 10
Fig. 10

Binary column-coded numbers.

Fig. 11
Fig. 11

Binary stack-coded numbers. xi(m) represents the mth bit of the ith number in the image plane. X(0) represents the image plane of least significant bits and X(k−1) represents the image plane of most significant bits.

Fig. 12
Fig. 12

Parallel arithmetic with binary stack-coded numbers: (a) sequence of images X = [X(3),X(2),X(1),X(0)]; (b) sequence of images R = [R(3),R(2),R(1),R(0)]; (c) sum X + R = [S(4),S(3),S(2),S(1),S(0)]; (d) difference D = XR = [D(3),D(2),D(1),D(0)]; (e) product M = X × R = [M(7),M(6),… ,M(0)].

Fig. 13
Fig. 13

BIA representation of symbolic substitution. The optional mask M is for controlling the block seach region.

Fig. 14
Fig. 14

Symbolic sunstitution system with p symbolic substitution rules.

Fig. 15
Fig. 15

Bit encoded as a symbol: (a) single-pixel coding of zero and one (a bit is a pixel); (b) two-pixel coding of zero and one (a bit is encoded as two pixels) (adapted from Refs. 18 and 19); (c) six-pixel coding of zero and one (a bit with value zero or one is encoded as six pixels) (adapted from Ref. 31).

Fig. 16
Fig. 16

Binary symbol-coding (symbolic substitution) binary arithmetic): (a) input image X contains the operands xi and ri;(b) output of parallell addition; (c) output of parallel subtraction.

Fig. 17
Fig. 17

Parallel addition of binary symbol-coded numbers: (a) four symbolic substitution rules for addition; (b) reference image pairs R(i) and reference images Q(i),i = 1,2,3,4, used for addition; Q(1) is a null image, Rule 1 is not needed for this single-pixel coding;(c) mask M; (d) example of parallel addition of binary symbol-coded numbers.

Fig. 18
Fig. 18

Symbolic substitution binary addition with two-pixel coding: (a) reference image pairs R(i) and reference images Q(i),i = 1,2,3,4, used for addition (with two-pixel coding) (adapted from Refs. 18 and 19); (b) mask M.

Fig. 19
Fig. 19

Symbolic substitution binary addition with encoding a bit as six pixels (adapted from Ref. 31).

Fig. 20
Fig. 20

Parallel subtraction of binary row-coded numbers: (a) image X of operands; (b) image R of other operands; (c) ouput XR; (d) procedure for parallel subtraction XR.

Fig. 21
Fig. 21

Parallel subtraction of binary symbol-coded numbers: (a) four symbolic substitution rules for subtraction; (b) reference image pairs R(i) and reference images Q(i),i = 1,2,3,4, used for subtraction; because Q(1) and Q(4) are null images, Rules 1 and 4 are not needed for single-pixel coding; (c) mask M; (d) example of parallel subtraction of binary symbol-coded numbers.

Tables (2)

Tables Icon

Table I Complexity of Parallel Optical Binary Addition of Two N × N Arrays of k-Bit Binary Numbers; Each Parallel Fundamental Operation Corresponds to P Processing Elements Executing in Parallel

Tables Icon

Table II Complexity of Parallel Optical Binary Subtraction of Two N × N Arrays of k-Bit Binary Numbers

Equations (73)

Equations on this page are rendered with MathJax. Learn more.

BIA = [ P ( W ) ; , , , I , A , A 1 , B , B 1 ]   ,
X = { ( x , y ) | ( x , y )   W ( x , y ) X } .
X R = { ( x , y )   |   ( x , y )     X   ( x , y )   R } .
X     R = { { ( x 1 + x 2 , y 1 + y 2 )     W |   ( x 1 , y 1 )     X , ( x 2 , y 2 )   R } ( X ) ( R ) , otherwise .
X = ( i , j )     X A i B j ,
A i A A A i = { ( i , 0 ) } if i > 0 , A i A 1 A 1 A 1 i = { ( i , 0 ) } if i < 0 , A 0 A A 1 = I .
R = { ( x , y )   |   ( x , y )   R } .
X / R = { ( x , y )   |   ( x , y )     X   ( x , y )     R } = X R = X R .
X R = { ( x , y )   |   ( x , y )     X   ( x , y )     R } = X R .
X     R = X     Ř ,
X Δ R = ( X / R ) ( R / X ) = X R R X .
X R = ( X R 1 ) ( X R 2 ) = ( X     Ř 1 ) ( X     Ř 2 ) .
DOCIP = [ P ( W × W × W ) ; , , , N c ]   ,
N array 4 = I A A 1 B B 1 .
N array 8 = i , j   =   1 A i B j .
N hypercube 4 = i   =   0 , ± 1 , ± 2 , , ± 2 k ( A i B i ) ,
N hypercube 8 = i   =   0 , ± 1 , ± 2 , , ± 2 k ( A i B i A i B i A i B i )  .
X     R = { [ ( X     E 1 )     E 2 ]         E k } .
X     R = ( X     R 1 ) ( X     R 2 ) ( X     R k ) ,
sum bit :   S i ( o ) = x i ( o )  XOR r i ( o ) ,
carry bit :   c i ( o ) =   x i ( o )  AND r i ( o ) .
S ( t 0 ) = X , C ( t 0 ) = R .
S ( t i  +  1 ) = S ( t i )   Δ   C ( t i ) = S ( t i ) C ( t i ) S ( t i ) C ( t i ) ,
C ( t i  +  1 ) = [ S ( t i ) C ( t i ) ]     A 1 = S ( t i ) C ( t i )     A 1 ,
S ( t k  +  1 ) = X + R , C ( t k  +  1 ) = .
X · R r = l ,   r ( l )   =   1 X     A 1 ,
A l = ( A 1 ) l A 1     A 1         A 1 l , X     A l = { [ ( X     A 1 )     A 1 ]         A 1 } l .
A l = j = 0 log 2 l A a ( j ) · 2 j A a ( 0 ) A a ( 1 ) · 2 1 A a ( log 2 l ) · 2 log 2 l ,
X     A l = ( { [ X     A a ( 0 ) ]     A a ( 1 ) · 2 l         A a ( log 2 l ) · 2 log 2 l )
X     A l = [ X     A ( l     1 ) ]     A 1 ,
l , r ( l )   =   1 X     A l
( 1 )   M 1     A 2 M ( = X     A 2 ) .
M 1 +   M 2  out ( =   X · R r ) .
X × R = l = 0 k 1 ( X A l ) { [ R ( M A l ) ] j = 0 k l 1 A j } = l = 0 k 1 X A l R M A l j = 0 k l 1 A j ,
j   =   0 k     l     1 A 1 = ( j   =   0 1 A j ) k     l     1 ( j   =   0 1 A j ) ( j   =   0 1 A j )         ( j   =   0 1 A j ) , k     l     1
j   =   0 k     l     1 A 1 = n   =   0 log ( k     l     1 ) [ j   =   0 k     l     1 A a ( j )  ⋅ 2 j ] ,
X     A 1 { [ R ( M     A l ) ]     j   =   0 k     l     1 A j } .
l   =   0 k     1 X     A l R M     A l     j   =   0 k     l     1 A j .
S ( 0 ) = X ( 0 ) Δ R ( 0 ) = X ( 0 ) R ( 0 ) X ( 0 ) R ( 0 )  ,
C ( 1 ) = X ( 0 ) R ( 0 ) = X ( 0 ) R ( 0 ) .
S ( i ) = X ( i ) Δ R ( i ) Δ C ( i ) = [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] = [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] [ X ( i ) R ( i ) C ( i ) ] ,
C ( i + 1 ) = [ X ( i ) R ( i ) ] [ X ( i ) C ( i ) ] [ R ( i ) C ( i ) ] = [ X ( i ) R ( i ) ] [ X ( i ) C ( i ) ] [ R ( i ) C ( i ) ] ,
X + R = S = [ S ( k ) , S ( k 1 ) ,   .   .   .   , S ( 0 ) ]  .
P ( 0 ) = [ 0 , 0 , , 0 , X ( k     1 ) k R ( 0 ) , X ( k     2 ) R ( 0 ) , , X ( 0 ) R ( 0 ) ]   ,
P ( i ) = [ 0 , 0 , , 0 , X ( k     1 ) k     i R ( i ) , X ( k 2 ) R ( i ) , , X ( 0 ) R ( i ) , 0 , 0 , , 0 , ]   ,
X × R = M = i = 0 k     1 P ( i ) P ( 0 ) + P ( 1 ) + + P ( k     1 ) ,
X     R 1 = X     R 1   .
X     R 2 = X     R 2 .
X R = ( X     R 1 ) ( X     R 2 ) = ( X     R 1 ) ( X     R 2 ) .
( X R ) Q = [ ( X R 1 ) ( X R 2 ) ] Q = ( X R 1 ) ( X R 2 ) Q .
[ ( X R ) M ] Q .
i   =   1 p [ X R ( i ) ] Q ( i ) ,
Y ( t 0 ) = X ,
Y ( t j   +   1 ) = i   =   1 4 { [ Y ( t j ) R ( i ) ] M } Q ( i ) ,
{ [ Y ( t j ) R ( 1 ) ] M } Q ( 1 ) = ,
Y ( t j   +   1 ) = i   =   1 4 { [ Y ( t j ) R ( i ) ] M } Q ( i ) = i   =   2 4 { [ Y ( t j ) R ( i ) ] M } Q ( i ) = i   =   2 4 { [ Y ( t j ) Ř 1 ( i ) ] [ Y ( t j ) Ř 2 ( i ) ] M } Q ( i ) .
t ( k ) ( 3 × 5 + 2 )   ( k + 1 ) = 17 ( k + 1 ) = O ( k ) .
Y ( t j + 1 ) = i = 1 4 { [ Y ( t j ) R ( i ) ] M } Q ( i ) = i = 2 4 { [ Y ( t j ) Ř 1 ( i ) ] [ Y ( t j ) Ř 2 ( i ) ] M } Q ( i ) = i = 1 4 [ Y ( t j ) Ř 2 ( i ) M ] Q ( i ) ,
[ Y ( t j ) Ř 1 ( i ) ] [ Y ( t j ) Ř 2 ( i ) ] = [ Y ( t j ) Ř 1 ( i ) ] = [ Y ( t j ) Ř 2 ( i ) ] ,
Y ( t j   +   1 = i   =   1 4 [ Y ( t j ) R ( i ) ] Q ( i ) ,
diffrence  bit : s i ( 0 ) = x i ( 0 )  XOR  r i ( 0 ) ,
borrow bit : c i ( 0 ) = x i ( 0 ) AND r i ( 0 ) .
D ( t 0 ) = X , B ( t 0 ) = R .
D ( t i   +   1 ) = D ( t i ) Δ B ( t i ) = D ( t i ) B ( t i ) D ( t i ) B ( t i ) ,
B ( t i   +   1 ) = [ D ( t i ) B ( t i ) ] A 1 = D ( t i ) B ( t i ) A 1 ,
D ( t k   +   1 ) = X R , B ( t k   +   1 ) = .
D ( 0 ) = X ( 0 ) Δ R ( 0 ) = X ( 0 ) R ( 0 ) R ( 0 ) X ( 0 ) ,
B ( 1 ) = X ( 0 ) R ( 0 ) = X ( 0 ) R ( 0 ) .
D ( i ) = [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] = [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] ,
B ( i   +   1 ) = [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] = [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] [ X ( i ) R ( i ) B ( i ) ] ,
X R = D = [ D ( k     1 ) , D ( k     2 ) , ... , D ( 0 ) ] .
Y ( t 0 ) = X ,
Y ( t j   +   1 ) = i   =   1 4 { [ Y ( t j ) R ( i ) ] M } Q ( i ) = i   =   1 4 { [ Y ( t j ) Ř 1 ( i ) ] [ Y ( t j ) Ř 2 ( i ) ] M } Q ( i ) = i   =   2 3 { [ Y ( t j ) Ř 1 ( i ) ] [ Y ( t j ) Ř 2 ( i ) ] M } Q ( i ) ,

Metrics