Open Access
Add to BibSonomyAbstract
We apply two novel nonuniform quantization techniques to digital holograms of three-dimensional real-world objects. Our companding approach, combines the efficiency of uniform quantization with the improved performance of nonuniform quantization. We show that the performance of companding techniques can be comparable with k-means clustering and a competitive neural network, while only requiring a single-pass processing step. The quantized holographic pixels are coded using lossless techniques for the calculation of compression ratio.
©2006 Optical Society of America
1. Introduction
With the development of megapixel CCD sensors with high spatial resolution and dynamic range, digital holography [1, 2, 3, 4, 5, 6, 7] has become a popular technique for three-dimensional (3D) imaging [8]. A technique known as phase-shift interferometry [2, 5] was used to record our in-line digital holograms. The resulting digital holograms are in a suitable form for processing or transmission. Each hologram encodes multiple views of the object from a small range of angles. By applying numerical Fresnel propagation techniques [3, 5, 9] to appropriate regions [10, 11], we can reconstruct any one of these perspectives of the object.
The dimensions of our digital holograms are 2028×2044 pixels, storing 8bytes of real information and 8bytes of imaginary information for each pixel. To increase storage and transmission efficiency [12], we compress our holograms. The noisy appearance of digital holograms causes lossless data compression techniques, such as Huffman, to perform poorly [13]. The use of lossy compression techniques to initially quantize our hologram data seems essential.
Quantization and phase quantization have been applied successfully to Fourier and holographic data in the past [14, 13, 15, 16, 12, 17, 18, 19, 20, 21]. In this paper, we apply quantization directly to the complex-valued holographic pixels. Uniform quantization has been chosen in the past because of the time-efficient implementations it admits [13, 12, 21]. Nonuniform quantization achieves better compression ratios, but at the cost of requiring an iterative clustering technique. Companding quantization exhibits the speed of uniform quantization combined with the improved results of nonuniform quantization. We employ two companding approaches to quantize our holographic data and further apply lossless compression to the quantized data.
2. Digital Hologram Quantization
Two 3D objects (a die and a bolt) were used in our experiments. The digital holograms are stored in real-imaginary format, with each holographic pixel requiring two floating-point values. Uniform quantization is defined for an individual pixel H(x,y) as
and is applied to each x ∊[1,Nx],y∊[1,Ny], where
Here, Nx and Ny are the number of samples in the x and y directions, respectively, b represents the number of bits per real and imaginary value, max(·) returns the maximum scalar in its argument(s), and round(α)=⌊α +0.5⌋. All real and imaginary values will then be integers in the range [-2(b-1)+1,2(b-1)-1]. After decompression and prior to object reconstruction, each value is rescaled, by dividing by 2(b-1)-1, to the [-1,1] interval.
Fig. 1. NRMS error of the reconstructed die object plotted against number of clusters with uniform quantization and (a) k-means quantization and (b) Kohonen competitive. Non-optimized means using the clusters from the bolt to quantize the die.
In our compression experiments, a digital hologram H is compressed and then decompressed as H ′, and an object U ′ reconstructed by numerical propagation. The quality of the compressed reconstruction is measured using normalized rms (NRMS) difference, calculated from
where (m,n) are discrete spatial coordinates in the reconstruction plane. In order to reduce the effects of speckle noise, only amplitude in the reconstruction plane is considered and a 5×5 pixel mean filtering operation is applied prior to calculation of NRMS difference.
2.1. Nonuniform iterative quantization
The nonuniform distribution of our hologram data prevents uniform quantization from performing optimally. We require nonuniform quantization, since in a histogram representation, our data is denser around the origin (low amplitudes), thus requiring more cluster centers, and sparser away from the origin (high amplitudes). By nonuniformly positioning the cluster centers to match the fact that there is a higher probability that the pixel will have a low amplitude value, the cluster centers can be used more efficiently.
We previously employed the k-means clustering algorithm [22] and a Kohonen competitive neural network [23] to nonuniformly quantize our hologram data. The iterative techniques produce satisfactory results, however it is not practical to iterate the algorithms each time a hologram is to be compressed. Ideally, the cluster centers from one hologram could be stored in a lookup table and applied with reasonable results to the quantization of subsequent holograms. (The JPEG algorithm uses a hard-coded lookup table of cosine-domain quantization values arrived at through performance evaluation over a database of sample input images.) However, given that these algorithms adapt so well to the data they have been trained on, we have found that the set of cluster centers is significantly less effective when used to quantize a different hologram. This is illustrated in Fig. 1 (a), where it can be seen that quantizing the die hologram using the clusters obtained by applying k-means to the bolt hologram results in consistently increased compression errors. Figure 1 (b) shows similar results for the competitive network.
To overcome the computational requirements of iteration, we decided to produce a general hard-coded pattern of clusters that would be effective as a quantization codebook. This hard-coded pattern would need to be in the form of a cluster-generating function parameterized by a number of clusters. If this pattern was sufficiently general, it would also overcome the over-adaption problem.
Fig. 3. NRMS error of the reconstructed object plotted against number of clusters with uniform, companding diamond, k-means, and Kohonen competitive for (a) die and (b) bolt.
3. Companding quantization
Since uniform quantizers are simpler and more time-efficient than nonuniform quantizers, one effective nonuniform quantization technique involves nonlinearly transforming the data so that a uniform quantizer can be applied. This so-called companding quantization technique, works well if the distribution of the data can be described, or closely approximated, analytically. A compander is a nonuniform quantizer that is composed of a compressor, a uniform quantizer, and an expander. Companding quantization has been widely used in digitization, compression, and noise-free transmission of audio signals but little research has been done to investigate its usefulness in the compression of images.
3.1. Diamond companding grid
We have developed an approach analogous to companding that involves nonuniformly transforming a fixed-interval sampling grid of the complex plane, rather than transforming the input data. The grid is compressed in regions where the input data is dense (for example, close to the origin) and the grid is stretched in regions where the input data is sparse. The samples are then treated as cluster centers to quantize the input data. Figure 2 shows a companding grid, which we call the diamond pattern, based on a logarithmic sampling distribution. The inter-cluster spacing for the diamond pattern was determined through quantization experiments with several digital holograms. Figure 3 shows the results of using the companding grid to quantize a 1024×1024pixel window of each hologram. For both holograms, the companding grid performs as well as k-means and Kohonen competitive over numbers of cluster centers in the [25,100] range. This is a significant improvement over the non-optimized iterative techniques shown in Fig. 1. For smaller and larger numbers of clusters than the [25,100] range (corresponding to higher compression ratios and higher quality reconstructions, respectively) the iterative techniques clearly outperform the non-iterative companding technique. In the case of a larger number of clusters, this is not considered significant; as the ratio of number of pixels to number of clusters decreases, the performance of uniform and nonuniform quantization will converge (this trend is visible in Fig. 3).
Fig. 5. NRMS error of the reconstructed object plotted against number of clusters with companding diamond and spiral grids for (a) die and (b) bolt.
Fig. 6. Reconstructions with 5×5 mean filtering using the spiral companding grid for die with (a) 9 clusters, and (b) 49 clusters, and for bolt with (c) 9 clusters, and (d) 49 clusters.
3.2. Logarithmic spiral companding grid
In order to improve the performance of companding for smaller numbers of clusters, we developed a second companding grid using a logarithmic spiral function (known as the Bernoulli spiral or Fibonacci spiral). In polar coordinates, the spiral has the form r=ae bθ, where r is the distance from the origin, θ is the angle, and a and b are arbitrary constants.
Figure 4 shows the distribution of clusters for the spiral companding grid. Figure 5 shows plots of NRMS error in reconstructions for both holograms quantized using the diamond and the spiral companding grids. For numbers of clusters less than 25, spiral companding improves on the performance of the diamond companding technique, while being as effective for larger numbers of clusters. Reconstructions of both holograms quantized with the spiral companding grid are shown in Fig. 6.
4. Lossless compression of quantized digital holograms
To complete the compression procedure, lossless techniques (Huffman, Lempel-Ziv (LZ77), Lempel-Ziv-Welch (LZW) and Burrows-Wheeler (BW)) were applied to the quantized digital hologram data. Huffman coding [24], an entropy-based technique, is one of the oldest and most widely used compression methods. Each symbol in the input is replaced by a codeword, with more frequent symbols assigned shorter codewords. The LZ77 algorithm [25] takes advantage of repeated substrings in the input data and replaces variable length strings with a pointer to the previous occurrence of that string. LZW [26] improves upon LZ77 by maintaining a lookup table of variable sized codewords, and is also less biased towards local redundancy. BW [27] uses a sorting operation to transform its input into a format that can be compressed very successfully using one of the other three techniques (in our particular implementation, Huffman coding).
Fig. 7. NRMS error of the reconstructed object plotted against compression ratio with companding spiral grid for (a) die and (b) bolt.
Compression ratio, r, is a measure of the number of bits of uncompressed data that are actually communicated with a single bit of compressed data and is calculated from
In practice, the actual compression ratio will be dependent on the needs of the user, specifically how much reconstruction loss they are willing to tolerate for their particular applications.
Figure 7 shows NRMS error plotted against compression ratio for all lossless techniques for the spiral companding grid for both holograms. BW outperforms the other three lossless compression techniques for most numbers of cluster centers for both holograms.
5. Conclusion
Although it is a fast technique, uniform quantization does not make efficient use of its quantization space (set of cluster centers). Iterative nonuniform quantization techniques achieve lower hologram reconstruction errors with the same number of clusters, but learning is computationally expensive. To find a trade-off between speed and satisfactory results, we investigated two companding quantization patterns: a diamond grid and a spiral grid. Experimentation has shown that this technique provides comparable hologram reconstruction quality for quantization compression equal to that of k-means and Kohonen competitive, combined with the advantage that the quantization can be performed during a single pass of the data. It has also been shown that careful construction of the companding grid can make it insensitive to moderate changes in the distribution of hologram data. This is a particular problem for other iterative nonuniform quantization techniques, where a set of quantization clusters trained to perform well on one digital hologram, will not necessarily perform well on an unseen digital hologram. Finally, lossless techniques were applied to the quantized holograms, with BW producing the highest compression ratios over all techniques for both holograms used in our experiments. Compression ratios in excess of 70 were obtained.
The authors wish to thank Enrique Tajahuerce and Yann Frauel for use of their hologram data. This research received the support of Enterprise Ireland and Science Foundation Ireland.
References and links
1. J. W. Goodman and R. W. Lawrence, “Digital image formation from electronically detected holograms,” Appl. Phys. Lett. 11, 77–79 (1967). [CrossRef]
2. J. H. Bruning, D. R. Herriott, J. E. Gallagher, D. P. Rosenfeld, A. D. White, and D. J. Brangaccio, “Digital wave-front measuring interferometer for testing optical surfaces and lenses,” Appl. Opt. 13(11), 2693–2703 (1974). [CrossRef]
3. L. Onural and P. D. Scott, “Digital decoding of in-line holograms,” Opt. Eng. 26(11), 1124–1132 (1987).
4. U. Schnars and W. P. O. Jüptner, “Direct recording of holograms by a CCD target and numerical reconstruction,” Appl. Opt. 33(2), 179–181 (1994). [CrossRef]
5. I. Yamaguchi and T. Zhang, “Phase-shifting digital holography,” Opt. Lett. 22(16), 1268–1270 (1997). [CrossRef]
6. E. Cuche, F. Bevilacqua, and C. Depeursinge, “Digital holography for quantitative phase-contrast imaging,” Opt. Lett. 24(5), 291–293 (1999). [CrossRef]
7. T. Kreis, Handbook of Holographic Interferometry: Optical and Digital Methods (Wiley-VCH, Berlin, 2004). [CrossRef]
8. B. Javidi and F. Okano, eds., Three-Dimensional Television, Video, and Display Technologies (Springer, Berlin, 2002).
9. B. Javidi and E. Tajahuerce, “Three-dimensional object recognition by use of digital holography,” Opt. Lett. 25(9), 610–612 (2000). [CrossRef]
10. H. J. Caulfield, ed., Handbook of Optical Holography (Academic Press, New York, 1979).
11. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, New York, 1996).
12. T. J. Naughton, J. B. Mc Donald, and B. Javidi, “Efficient compression of Fresnel fields for Internet transmission of three-dimensional images,” Appl. Opt. 42(23), 4758–4764 (2003). [CrossRef]
13. T. J. Naughton, Y. Frauel, B. Javidi, and E. Tajahuerce, “Compression of digital holograms for three-dimensional object reconstruction and recognition,” Appl. Opt. 41(20), 4124–4132 (2002). [CrossRef]
14. W. J. Dallas and A. W. Lohmann, “Phase quantization in holograms - depth effects,” Appl. Opt. 11(1), 192–194 (1972). [CrossRef]
15. T. Nomura, A. Okazaki, M. Kameda, Y. Morimoto, and B. Javidi, “Image reconstruction from compressed encrypted digital hologram,” Opt. Eng. 44(7), 075,801-1–075,801-7 (2005).
16. O. Matoba, T. J. Naughton, Y. Frauel, N. Bertaux, and B. Javidi, “Real-time three-dimensional object reconstruction by use of a phase-encoded digital hologram,” Appl. Opt. 41(29), 6187–6192 (2002). [CrossRef]
17. T. J. Naughton and B. Javidi, “Compression of encrypted three-dimensional objects using digital holography,” Opt. Eng. 43(10), 2233–2238 (2004). [CrossRef]
18. D. Kayser, T. Kreis, and W. Jüptner, “Compression of digital holographic data using its electromagnetic field properties,” Proc. SPIE 5908, 97–105 (2005).
19. I. Yamaguchi, K. Yamamoto, G. A. Mills, and M. Yokota, “Image reconstruction only by phase in phase-shifting digital holography,” Appl. Opt. 45(5), 975–983 (2006). [CrossRef]
20. E. Darakis and J. J. Soraghan, “Compression of interference patterns with application to phase-shifting digital holography,” Appl. Opt.45 (2006). [CrossRef] [PubMed]
21. A. E. Shortt, T. J. Naughton, and B. Javidi, “Compression of digital holograms of three-dimensional objects using wavelets,” Opt. Express 14(7), 2625–2630 (2006). [CrossRef]
22. J. MacQueen, “Some methods for classification and analysis of multivariate observations.” Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1, 281–297 (1967).
23. T. Kohonen, Self-Organizing Maps (Springer-Verlag, Berlin, 1994).
24. D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE 40, 1098–1101 (1952). [CrossRef]
25. J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23(3), 337–343 (1977). [CrossRef]
26. T. A. Welch, “A technique for high performance data compression,” IEEE Computer 17(6), 8–19 (1984). [CrossRef]
27. M. Burrows and D. J. Wheeler, “A block-sorting lossless data compression algorithm,” Tech. Rep. 124, Digital Systems Research Center, Palo Alto, California (1994).
