Abstract

Fast decimation-in-frequency direct binary search (DBS) algorithms for the computation of binary computer-generated holograms (CGH’s) are developed. The algorithms use the geometry of the image plane and the decimation-in-frequency property to design a fast method of scanning the hologram with the DBS method. In this way the computational complexity of the method is substantially reduced. For complex-amplitude-based error, the asymptotic computational complexity for an L-point CGH is reduced by a factor of O[(L/log2L)1/2]. For intensity-based error, the asymptotic computational complexity for an L-point CGH is reduced by a factor of O[(L log2L)1/4]. When the probability of accepting an inversion is small, an acceleration technique is also used to reduce further the time complexity.

© 1994 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Hauck, O. Bryngdahl, “Computer-generated holograms with pulse-density modulation,” J. Opt. Soc. Am. A 1, 5–10 (1984).
    [CrossRef]
  2. E. Barnard, “Optimal error diffusion for computer-generated holograms,” J. Opt. Soc. Am. A 5, 1803–1817 (1988).
    [CrossRef]
  3. M. A. Seldowitz, J. P. Allebach, D. W. Sweeney, “Synthesis of digital holograms by direct binary search,” Appl. Opt. 26, 2788–2798 (1987).
    [CrossRef]
  4. B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Iterative approaches to computer-generated holography,” Opt. Eng. 28, 629–637 (1989).
    [CrossRef]
  5. O. K. Ersoy, J-Y. Zhuang, J. Brede, “An iterative interlacing approach for synthesis of computer-generated holograms,” Appl. Opt. 31, 6894–6901 (1992).
    [CrossRef] [PubMed]
  6. B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Efficient design of direct-binary-search computer-generated holograms,” J. Opt. Soc. Am. A 8, 652–660 (1991).
    [CrossRef]
  7. P. M. Hirsch, J. A. Jordan, L. B. Lesem, “Method of making an object-dependent diffuser,” U. S. patent3,619,022 (Nov.9, 1971).
  8. R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).
  9. N. C. Gallagher, B. Liu, “Method for computing kinoforms that reduces image reconstruction error,” Appl. Opt. 12, 2328–2335 (1973).
    [CrossRef] [PubMed]
  10. M. P. Chang, O. K. Ersoy, “Iterative interlacing error diffusion for synthesis of computer-generated holograms,” Appl. Opt. 32, 3122–3129 (1993).
    [CrossRef] [PubMed]

1993

1992

1991

1989

B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Iterative approaches to computer-generated holography,” Opt. Eng. 28, 629–637 (1989).
[CrossRef]

1988

1987

1984

1973

1972

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).

Allebach, J. P.

Barnard, E.

Brede, J.

Bryngdahl, O.

Chang, M. P.

Ersoy, O. K.

Gallagher, N. C.

Gerchberg, R. W.

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).

Hauck, R.

Hirsch, P. M.

P. M. Hirsch, J. A. Jordan, L. B. Lesem, “Method of making an object-dependent diffuser,” U. S. patent3,619,022 (Nov.9, 1971).

Jennison, B. K.

B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Efficient design of direct-binary-search computer-generated holograms,” J. Opt. Soc. Am. A 8, 652–660 (1991).
[CrossRef]

B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Iterative approaches to computer-generated holography,” Opt. Eng. 28, 629–637 (1989).
[CrossRef]

Jordan, J. A.

P. M. Hirsch, J. A. Jordan, L. B. Lesem, “Method of making an object-dependent diffuser,” U. S. patent3,619,022 (Nov.9, 1971).

Lesem, L. B.

P. M. Hirsch, J. A. Jordan, L. B. Lesem, “Method of making an object-dependent diffuser,” U. S. patent3,619,022 (Nov.9, 1971).

Liu, B.

Saxton, W. O.

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).

Seldowitz, M. A.

Sweeney, D. W.

Zhuang, J-Y.

Appl. Opt.

J. Opt. Soc. Am. A

Opt. Eng.

B. K. Jennison, J. P. Allebach, D. W. Sweeney, “Iterative approaches to computer-generated holography,” Opt. Eng. 28, 629–637 (1989).
[CrossRef]

Optik

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).

Other

P. M. Hirsch, J. A. Jordan, L. B. Lesem, “Method of making an object-dependent diffuser,” U. S. patent3,619,022 (Nov.9, 1971).

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

Fig. 1
Fig. 1

Geometry of the desired image region with respect to the whole image plane.

Fig. 2
Fig. 2

Example of decimation in frequency for μ = 2 and ν = 2. There are four blocks distinguished by four different symbols.

Fig. 3
Fig. 3

Iteration number versus (a) probability of accepting an inversion and (b) time required for an iteration for RMSE–CABE, FDIFDBS–CABE, and acceleration technique.

Fig. 4
Fig. 4

Schematic diagram for the update of the appropriate elements of the DFT’s for Nin cells from cell i + n + 1 to cell i + Ni following a retained inversion at cell i + n.

Tables (4)

Tables Icon

Table 1 Asymptotic Number of Operations Required for a Single Iteration of the RMSE–CABE and FDIFDBS–CABE Algorithms

Tables Icon

Table 2 Average CPU Time (s) Required for the RMSE–CABE and the FDIFDBS–CABE Algorithms

Tables Icon

Table 3 Asymptotic Number of Operations Required for a Single Iteration of the RMSE–IBE and FDIFDBS–IBE Algorithms

Tables Icon

Table 4 Average CPU Time (s) Required for the RMSE–IBE and the FDIFDBS–IBE Algorithms

Equations (48)

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

h ( m , n ) = 1 M N k = 0 M - 1 l = 0 N - 1 H ( k , l ) W M - m k W N - n l ,
W u = exp ( - i 2 π / u ) ,             u = M             or             N .
e c = 1 A B f - λ c h 2 ,
e I = 1 A B f 2 - λ I h 2 2
λ c = f , h h 2 ,
λ I = f 2 , h 2 h 2 2 ,
e c = 1 A B ( f 2 - f , h 2 h 2 ) .
h ( m , n ) = h ( m , n ) + a M N W M - m k W N - n l ,
f , h = f , h + a M N F ( k , l ) ,
F ( k , l ) = f , W M - k W N - l = ( m , N ) R f ( m , n ) W M m l W N n l
h 2 = h 2 + A B ( M N ) 2 + 2 a M N Re h , W M - k W N - l = h 2 + A B ( M N ) 2 + 2 a M N Re [ H ˜ ( k , l ) ] ,
H ˜ ( k , l ) = DFT [ r ( m , n ) h ( m , n ) ] k , l = ( m , n ) R h ( m , n ) W M m k W N n l
r ( m , n ) = { 1 ( m , n ) R 0 otherwise .
h ( m , n ) = h i - S ( m , n ) + 1 M N s = 1 S a s W M - m k s W N - n l s .
H ˜ ( k , l ) = H ˜ i - S ( k , l ) + 1 M N s = 1 S a s R ( k - k s , l - l s ) ,
S * = ( 2 p C u / C i ) 1 / 2 - 1 ,
E * = ( 2 p C u C i ) 1 / 2 - C i / 2.
R ( k , l ) = DFT [ r ( m , n ) ] k , l = ( m , n ) R W M m k W N n l = m = M 1 A + M 1 - 1 n = N 1 B + N 1 - 1 W M m k W N n l = { W M M 1 k W N N 1 l 1 - W μ k 1 - W M 1 - W ν l 1 - W N k 0 , l 0 A W N N 1 l 1 - W ν l 1 - W N k = 0 , l 0 B W M M 1 k 1 - W μ k 1 - W M k 0 , l = 0 A B k = 0 , l = 0 .
h ( m , n ) = 1 M N k = 0 A - 1 l = 0 B - 1 [ α = 0 μ - 1 β = 0 ν - 1 H ( μ k + α , ν l + β ) × W M - m α W N - n β ] W A - m k W B - n l ,             0 m M - 1 ,             0 n N - 1.
h ( m + M 1 , n + N 1 ) = 1 M N α = 0 μ - 1 β = 0 ν - 1 [ k = 0 A - 1 l = 0 B - 1 H ( μ k + α , ν l + β ) × W A - ( m + M 1 ) k W B - ( n + N 1 ) l ] W M - ( m + M 1 ) α W N - ( n + N 1 ) β , 0 m A - 1             and             0 n B - 1.
h α , β ( m , n ) = IDFT A B [ H ( μ k + α , ν l + β ) ] m n = 1 A B k = 0 A - 1 l = 0 B - 1 H ( μ k + α , ν l + β ) W A - m k W B - n l ,             0 α μ - 1 ,             0 β ν - 1 ,             0 m A - 1 ,             0 n B - 1 ,
h ( m + M 1 , n + N 1 ) = 1 μ ν α = 0 μ - 1 β = 0 ν - 1 [ h α , β ( m + M 1 , n + N 1 ) × W M - ( m + M 1 ) α W N - ( n + N 1 ) β ] ,             0 m A - 1 ,             0 n B - 1.
H ˜ ( k , l ) = k = 0 A - 1 l = 0 B - 1 h ( m + M 1 , n + N 1 ) W M ( m + M 1 ) k W N ( n + N 1 ) l ,             0 k M - 1 ,             0 l N - 1.
H ˜ ( μ k + α , ν l + β ) = 1 μ ν W A M 1 k W B N 1 l DFT A B [ h ˜ α , β ( m , n ) ] k , l , 0 α μ - 1 ,             0 β ν - 1 ,             0 k A - 1 ,             0 l B - 1 ,
h ˜ α , β ( m , n ) = W M ( m + M 1 ) α W N ( n + N 1 ) β × α = 0 μ - 1 β = 0 ν - 1 W M - ( m + M 1 ) α W N - ( n + N 1 ) β h α , β × ( m + M 1 , n + N 1 ) , 0 α μ - 1 ,             0 β ν - 1 ,             0 m A - 1 ,             0 n B - 1.
H ˜ ( μ k + α , ν l + β ) = 1 μ ν { H ( μ k + α , ν l + β ) + W A M 1 k W N N 1 l DFT A B [ h ˜ α , β ( m , n ) ] k , l } , 0 α μ - 1 ,             0 β ν - 1 ,             0 k A - 1 ,             0 l B - 1 ,
h ˜ α , β ( m , n ) = W M α ( m + M 1 ) W N β ( n + N 1 ) × α = 0 , α α μ - 1 β = 0 , β β ν - 1 W M - α ( m + M 1 ) W N - β ( n + N 1 ) h α , β × ( m + M 1 , n + N 1 ) , 0 α μ - 1 ,             0 β ν - 1 ,             0 m A - 1 ,             0 n B - 1.
e I = 1 A B ( f 2 2 - f 2 , h 2 2 h 2 2 ) .
f 2 , h 2 = f 2 , h 2 + 1 ( M N ) 2 f 2 + 2 a M N Re [ DFT ( f 2 h i - S ) k , l + 1 M N s = 1 S a s DFT ( f 2 ) k - k s , l - l s ] ,
h 2 2 = h 2 2 + A B ( M N ) 4 + 4 ( M N ) 2 h 2 + 4 a ( M N ) 3 Re [ H ˜ ( k , l ) ] + 4 a M N Re [ DFT ( r h 2 h ) k , l ] + 2 ( M N ) 2 Re [ DFT ( r h 2 ) 2 k , 2 l ] ,
DFT ( r h 2 ) k , l = DFT ( r h i - S 2 h i - S ) k , l + 2 M N s = 1 S a s DFT ( r h i - S 2 ) k - k s , l - l s + 1 M N s = 1 S a s DFT [ r ( h i - S ) 2 ] k + k s , l + l s + 2 ( M N ) 2 s = 1 S t = 1 S a s a t H ˜ i - S × ( k - k s + k t , l - l s + l t ) + 1 ( M N ) 2 s = 1 S t = 1 S a s a t H ˜ i - S × ( k s + k t - k , l s + l t - l ) * + 1 ( M N ) 3 s = 1 S t = 1 S u = 1 S a s a t a u R × ( k - k s - k t + k u , l - l s - l t + l u ) ,
DFT ( r h 2 ) 2 k , 2 l = DFT [ r ( h i - S ) 2 2 k , 2 l + 2 M N × s = 1 S a s H ˜ i - S ( 2 k - k s , 2 l - l s ) + 1 ( M N ) 2 s = 1 S t = 1 S a s a t R × ( 2 k - k s - k t , 2 l - l s - l t ) .
S * = O ( C u 1 / 4 ) = O [ ( L log 2 L ) 1 / 4 ] .
E * = O [ I L 7 / 4 ( log 2 L ) 3 / 4 ] .
DFT ( r h 2 h ) k , l = DFT ( r h i - 1 2 h i - 1 ) k , l + 2 M N α 1 DFT ( r h i - 1 2 ) k - k 1 , l - l 1 + 1 M N a 1 DFT [ r ( h i - 1 ) 2 ] k + k 1 , l + l 1 + 2 ( M N ) 2 H ˜ i - 1 ( k , l ) + 1 ( M N ) 2 H ˜ i - 1 ( 2 k 1 - k , 2 l 1 - l ) * + 1 ( M N ) 3 a 1 R ( k - k 1 , l - l 1 ) ,
DFT ( r h 2 ) k , l = DFT [ r ( h i - 1 ) 2 ] k , l + 2 M N a 1 H ˜ i - 1 ( k - k 1 , l - l 1 ) + 1 ( M N ) 2 R ( k - 2 k 1 , l - 2 l 1 ) ,
DFT ( r h 2 ) k , l = DFT ( r h i - 1 2 ) k , l + 1 M N a 1 H ˜ i - 1 ( k + k 1 , l + l 1 ) + 1 ( M N ) a 1 H ˜ i - 1 ( k 1 - k , l 1 - l ) * + 1 ( M N ) 2 R ( k , l ) ,
H ˜ ( k , l ) = H ˜ i - 1 ( k , l ) + 1 M N a 1 R ( k - k 1 , l - l 1 ) .
E N i = n = 1 N i p ( N i - n ) C i + C u = p N i ( N i - 1 ) 2 C i + C u .
E ¯ N i = E N i N i = p ( N i - 1 ) C i 2 + C u N i .
N i * = [ 2 C u / ( p C i ) ] 1 / 2 .
E ¯ N i * = ( 2 p C u C i ) 1 / 2 - p C i / 2.
DFT ( r h 2 h ) k , l = m = 0 A - 1 n = 0 B - 1 h ( m + M 1 , n + N 1 ) 2 × h ( m + M 1 , n + N 1 ) W M ( m + M 1 ) k W N ( n + N 1 ) l ,             0 k M - 1 ,             0 l - 1 ,
DFT ( r h 2 ) k , l = m = 0 A - 1 n = 0 B - 1 h 2 ( m + M 1 , n + N 1 ) × W M ( m + M 1 ) k W N ( n + N 1 ) l             0 k M - 1 ,             0 l N - 1 ,
DFT ( r h 2 ) k , l = m = 0 A - 1 n = 0 B - 1 h ( m + M 1 , n + N 1 ) 2 × W M ( m + M 1 ) k W N ( n + N 1 ) l ,             0 k M - 1 ,             0 l N - 1.
DFT ( r h 2 h ) μ k + α , ν l + β = W A M 1 k W B N 1 l × DFT A B [ h ( m + M 1 , n + N 1 ) 2 × h ( m + M 1 , n + N 1 ) × W M ( m + M 1 ) α W N ( n + N 1 ) β ] k , l , 0 α μ - 1 ,             0 β ν - 1 ,             0 k A - 1 ,             0 l B - 1 ,
DFT ( r h 2 ) μ k + α , ν l + β = W A M 1 k W B N 1 l × DFT A B [ h 2 ( m + M 1 , n + N 1 ) × W M ( m + M 1 ) α W N ( n + N 1 ) β ] k , l , 0 α μ - 1 ,             0 β ν - 1 ,             0 k A - 1 ,             0 l B - 1 ,
DFT ( r h 2 ) μ k + α , ν l + β = W A M 1 k W B N 1 l × DFT A B [ h ( m + M 1 , n + N 1 ) 2 × W M ( m + M 1 ) α W N ( n + N 1 ) β ] k , l , 0 α μ - 1 ,             0 β ν - 1 ,             0 k A - 1 ,             0 l B - 1.

Metrics