OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 25 — Dec. 10, 2007
  • pp: 17072–17092

Optimal multiplexed sensing: bounds, conditions and a graph theory link

Netanel Ratner, Yoav Y. Schechner, and Felix Goldberg  »View Author Affiliations

Optics Express, Vol. 15, Issue 25, pp. 17072-17092 (2007)

View Full Text Article

Enhanced HTML    Acrobat PDF (314 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



Measuring an array of variables is central to many systems, including imagers (array of pixels), spectrometers (array of spectral bands) and lighting systems. Each of the measurements, however, is prone to noise and potential sensor saturation. It is recognized by a growing number of methods that such problems can be reduced by multiplexing the measured variables. In each measurement, multiple variables (radiation channels) are mixed (multiplexed) by a code. Then, after data acquisition, the variables are decoupled computationally in post processing. Potential benefits of the use of multiplexing include increased signal-to-noise ratio and accommodation of scene dynamic range. However, existing multiplexing schemes, including Hadamard-based codes, are inhibited by fundamental limits set by sensor saturation and Poisson distributed photon noise, which is scene dependent. There is thus a need to find optimal codes that best increase the signal to noise ratio, while accounting for these effects. Hence, this paper deals with the pursuit of such optimal measurements that avoid saturation and account for the signal dependency of noise. The paper derives lower bounds on the mean square error of demultiplexed variables. This is useful for assessing the optimality of numerically-searched multiplexing codes, thus expediting the numerical search. Furthermore, the paper states the necessary conditions for attaining the lower bounds by a general code. We show that graph theory can be harnessed for finding such ideal codes, by the use of strongly regular graphs.

© 2007 Optical Society of America

OCIS Codes
(030.4280) Coherence and statistical optics : Noise in imaging systems
(110.6980) Imaging systems : Transforms
(150.2950) Machine vision : Illumination
(300.6380) Spectroscopy : Spectroscopy, modulation
(340.7430) X-ray optics : X-ray coded apertures
(110.1758) Imaging systems : Computational imaging

ToC Category:
Imaging Systems

Original Manuscript: September 4, 2007
Revised Manuscript: November 13, 2007
Manuscript Accepted: November 14, 2007
Published: December 5, 2007

Netanel Ratner, Yoav Y. Schechner, and Felix Goldberg, "Optimal multiplexed sensing: bounds, conditions and a graph theory link," Opt. Express 15, 17072-17092 (2007)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk, "A new compressive imaging camera architecture using optical-domain compression," Proc. SPIE 6065, (2006). [CrossRef]
  2. W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. "The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph," Vib. Spectrosc. 29,163-170 (2002). [CrossRef]
  3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. "Longwave infrared (LWIR) coded aperture dispersive spectrometer," Opt. Express 15,5742-5753 (2007). [CrossRef] [PubMed]
  4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. "Static two-dimensional aperture coding for multimodal, multiplex spectroscopy," Appl. Opt. 43,2965-2974 (2006). [CrossRef]
  5. Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. "Spectrally resolved fluorescence lifetime imaging microscopy," Appl. Spectrosc. 56, 63-84 (2002). [CrossRef]
  6. G. Nitzsche and R. Riesenberg. "Noise, fluctuation and HADAMARD-transform-spectrometry," In Proc. SPIE 5111, 273-282 (2003). [CrossRef]
  7. J. F. Turner and P. J. Treado. "Adaptive filtering and hadamard transform imaging spectroscopy with an acoustooptic tunable filter (AOTF)," Proc. SPIE 2599, 285-293 (1996). [CrossRef]
  8. E. E. Fenimore and T. M. Cannon. "Coded aparture imaging with uniformly redundent arrays," Appl. Opt. 17,337-347 (1978). [CrossRef] [PubMed]
  9. M. Harwit and N. J. A. Sloane, Hadamard Transform Optics, (Academic Press, New York, 1979).
  10. T. M. Palmieri, "Multiplex methods and advantages in X-ray astronomy," Astrophys. Space Sci. 28,277-287 (1974). [CrossRef]
  11. R. J. Proctor, G. K. Skinner, and A. P. Willmore, "The design of optimum coded mask X-ray telescopes," Royal Astron. Soc. Monthly Notices 187,633-643 (1979).
  12. G. K. Skinner. "X-ray imaging with coded masks," Sci. Am. 259,84-89 (1988). [CrossRef] [PubMed]
  13. A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel, "Fusion of 2d and 3d data in three-dimensional face recognition," In Proc. IEEE ICIP Vol. 1, pages 87-90 (2004).
  14. O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang, "Polarization multiplexing and demultiplexing for appearancebased modeling," IEEE Trans. PAMI 29,362-367 (2007). [CrossRef]
  15. K. C. Lee, J. Ho, and D. J. Kriegman, "Acquiring linear subspaces for face recognition under variable lighting," IEEE Trans. PAMI 27,684-698 (2005). [CrossRef]
  16. M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas, "Synthetic aperture confocal imaging," ACM TOG 23,825-834 (2004).
  17. F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur, "Optimal illumination for image and video relighting," In Proc. CVMP pages 201-210 (2005).
  18. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur, "A theory of multiplexed illumination," In Proc. IEEE ICCV Vol. 2, pages 808-815 (2003).
  19. A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec, "Performance relighting and reflectance transformation with time-multiplexed illumination," ACM TOG 24,756-764 (2005).
  20. A. Busboom, H. D. Schotten, and H. Elders-Boll, "Coded aperture imaging with multiple measurements," J. Opt. Soc. Am. A 14,1058-1065 (1997). [CrossRef]
  21. E. E. Fenimore, "Coded aperture imaging: predicted performance of uniformly redundant arrays," Appl. Opt. 17,3562-3570 (1978). [CrossRef] [PubMed]
  22. N. Ratner and Y. Y. Schechner, "Illumination multiplexing within fundamental limits," In Proc. IEEE CVPR (2007).
  23. A. Wuttig, "Optimal transformations for optical multiplex measurements in the presence of photon noise," Appl. Opt. 44,2710-2719 (2005). [CrossRef] [PubMed]
  24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur, "Multiplexing for optimal lighting," IEEE Trans. PAMI 29,1339-1354 (2007). [CrossRef]
  25. V. P. Kozlov and E. V. Sedunov, "Optimization of multiplex measuring systems in the presence of statistical signal fluctuations," Cybern. Syst. Anal. 28,830-839 (1992). [CrossRef]
  26. Y. A. Shutova, "Optimization of binary masks for Hadamard-transform optical spectrometers," J. Opt. Technol. 67,50-53 (2000). [CrossRef]
  27. C. D. Meyer. Matrix Analysis and Applied Linear Algebra, (SIAM 2000). [CrossRef]
  28. R. A. Horn and C. R. Johnson, Matrix Analysis, (Cambridge, New York, 1985).
  29. M. T. Chu, "A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values," SIAM J. on Numerical Analysis 37,1004-1020 (2000). [CrossRef]
  30. R. Diestel, Graph Theory, 3rd edition (Springer, 2000).
  31. P. J. Cameron and J. H. V. Lint, Designs, Graphs, Codes, and Their Links, (Cambridge University Press, New York, NY, USA, 1991). [CrossRef]
  32. J. J. Seidel, "Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3," Numer. Linear Algebra Appl. 1,281-289 (1968). [CrossRef]
  33. W. Haemers, "Matrix techniques for strongly regular graphs and related geometries," Intensive course on Finite Geometry and its Applications, University of Ghent (2000).
  34. M. Alicacute, B. Mond, J. Pecbreve aricacute and V. Volenec, "The arithmetic-geometric-harmonic-mean and related matrix inequalities," Numer. Linear Algebra Appl. 264,55-62 (1997). [CrossRef]
  35. K. Coolsaet and J. Degraer, "The strongly regular (45,12,3,3) graphs," Electron. J. Comb. 13, (2006).
  36. T. Spence. "Strongly Regular Graphs on at most 64 vertices" http://www.maths.gla.ac.uk/ es/srgraphs.html
  37. G. Royle, "Strongly regular graphs," (1996). http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html
  38. P. Puxley and T. Geballe, "Transmission Spectra," (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html
  39. S. Ioué and K. R. Spring, Video Microscopy, 2nd ed., (Plenum Press, New York, 1997) chaps. 6, 7, 8.
  40. C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang, "Noise estimation from a single image," In Proc. CVPR 1, 901-908 (2006).
  41. F. Alter, Y. Matsushita, and X. Tang, "An intensity similarity measure in low-light conditions," In Proc. ECCV 4, 267-280 (2006).
  42. H. H. Barrett and W. Swindell, Radiological Imaging, (Academic press, New York 1981) Vol. 1.

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited