Transcription
Computational 3D and Re ectivity Imagingwith High Photon E ciencybyDongeek ShinSubmitted to the Department of Electrical Engineering and ComputerSciencein partial ful llment of the requirements for the degree ofMaster of Science in Computer Science and Engineeringat theMASSACHUSETTS INSTITUTE OF TECHNOLOGYJune 2014c Massachusetts Institute of Technology 2014. All rights reserved.Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Department of Electrical Engineering and Computer ScienceMay 21, 2014Certi ed by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Vivek K GoyalAssistant Professor, Boston UniversityThesis SupervisorCerti ed by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Je rey H. ShapiroJulius A. Stratton ProfessorThesis SupervisorAccepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Leslie KolodziejskiChairman, Department Committee on Graduate Theses
2
Computational 3D and Re ectivity Imagingwith High Photon E ciencybyDongeek ShinSubmitted to the Department of Electrical Engineering and Computer Scienceon May 21, 2014, in partial ful llment of therequirements for the degree ofMaster of Science in Computer Science and EngineeringAbstractImaging the 3D structure and re ectivity of a scene can be done using photon-countingdetectors.Traditional imagers of this type typically require hundreds of detectedphotons per pixel for accurate 3D and re ectivity imaging.Under low light-levelconditions, in which the mean photon count is small, the inverse problem of forming3D and re ectivity images is di cult due to the Poisson noise inherent in low- uxoperation.In this thesis, we propose and study two computational imagers (onepassive, one active) that can form accurate images at low light levels. We demonstratethe superior imaging quality of the proposed imagers by comparing them with thestate-of-the-art optical imaging techniques.Thesis Supervisor: Vivek K GoyalTitle: Assistant Professor, Boston UniversityThesis Supervisor: Je rey H. ShapiroTitle: Julius A. Stratton Professor3
4
AcknowledgmentsI am very fortunate to have Professor Vivek Goyal and Professor Je rey Shapiroas my research supervisors.I thank Vivek for being supportive ever since I joinedthe STIR group and guiding me and my research during my rst two years at MIT.I would like to thank Je for his great mentorship and teaching me how to be ameticulous researcher. Every research meeting with Vivek and Je has enlightenedme and a ected this thesis in positive ways.I would like to thank Ahmed Kirmani, who motivated me further to look intothe topic of time-resolved imaging and gave me invaluable advice on many ideas thatwent into this thesis.I would also like to thank my research collaborators Andrea Colaço, Dheera Venkatraman, Dr. Franco Wong, and Hye Soo Yang for creating the synergy that improvedthe quality of my research as a whole.Finally, I thank my family for their endless love and support.This research was supported in part by NSF grant No. 1161413 and a SamsungScholarship.5
6
Contents1 Introduction132 Single-Pixel Re ectivity Imaging with High Photon E ciency172.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.1.1Classical Passive Re ectivity Imaging . . . . . . . . . . . . . .182.1.2Single-Pixel Camera based on Compressive Sensing. . . . . .192.1.3Single-Pixel Camera based on Multiplexed Sensing. . . . . .212.2Multiplexed Sensing under Poisson Noise . . . . . . . . . . . . . . . .242.3Non-Negativity of Re ectivity . . . . . . . . . . . . . . . . . . . . . .252.4Novel Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . .272.4.1When is the Non-Negativity Constraint Active?. . . . . . .282.4.2Choosing the Multiplexing Pattern. . . . . . . . . . . . . .30Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . .322.5.1Comparison of Mean-Square Errors . . . . . . . . . . . . . . .322.5.2Natural Images342.5Prior Work. . . . . . . . . . . . . . . . . . . . . . . . . .3 Active 3D Imaging with High Photon E ciency3.13.2Prior Work39. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393.1.1Classical Active 3D Imaging . . . . . . . . . . . . . . . . . . .393.1.2First-Photon Imaging . . . . . . . . . . . . . . . . . . . . . . .40Single-Photon Imaging Setup. . . . . . . . . . . . . . . . . . . . . .413.2.1Active Illumination . . . . . . . . . . . . . . . . . . . . . . . .413.2.2Detection42. . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.2.33.3Data AcquisitionObservation Model. . . . . . . . . . . . . . . . . . . . . . . . .43. . . . . . . . . . . . . . . . . . . . . . . . . . . .433.3.1Poisson Detection Statistics3.3.2Statistics of Number of Detected Photons. . . . . . . . . . .443.3.3Statistics of Single Photon Arrival Times . . . . . . . . . . . .453.4Novel Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . .483.5Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .503.5.1Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . .503.5.2Re ectivity Resolution Test. . . . . . . . . . . . . . . . . . .513.5.3Depth Resolution Test. . . . . . . . . . . . . . . . . . . . . .523.5.4Natural Scenes. . . . . . . . . . . . . . . . . . . . . . . . . .533.5.5Pixelwise Root Mean-Square Error Test. . . . . . . . . . . .563.5.6E ect of System Parameters . . . . . . . . . . . . . . . . . . .563.5.7Limitations583.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Information Theory for Optical Design. . . . . . . . . . . . . . . . .4 Conclusions4458634.1Highly Photon-E cient Re ectivity Imaging . . . . . . . . . . . . . .634.2Highly Photon-E cient 3D Imaging . . . . . . . . . . . . . . . . . . .63A Proofs65A.1Multiplexing Failure using Hadamard Matrix under Poisson Noise . .65A.2Multiplexing Failure using Circulant Matrices under Poisson Noise . .66A.3Strict Concavity of Log-Likelihood under Multiplexing. . . . . . . .68A.4E ciency of Matrix Inverse Demultiplexing Solution . . . . . . . . . .69A.5Violation Probability for Symmetric i.i.d. Matrix Inverse Estimators .70A.6Covariance Matrix of Hadamard Matrix Inverse Solution71. . . . . . .B Performance Guarantees for Pixelwise Single-Photon Imaging73B.1Pixelwise Maximum-Likelihood Re ectivity Estimation. . . . . . . .74B.2Pixelwise Maximum-Likelihood Depth Estimation . . . . . . . . . . .758
List of Figures2-1E ect of shot noise on image quality for several acquisition times(top) and dark count rate valuesvalue of the saturn image is2-22-3d (bottom).25.The maximum re ectivity. . . . . . . . . . . . . . . . . . . . .The multiplexed imaging setup.i 1, 2, . . . n,TaMeasurementis collected usingpatternwipixels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .forwherenziis the total number of imageThe non-negative orthant cone and the polyhedral coneing zero dark count.negative orthant.19c(W),21assum-True re ectivity image (black) lies in the non-From one realization of data, we obtain a feasiblere ectivity estimate (blue) using the matrix inverse solution. From another realization of data, the estimate (red) has negative entries andthus is not valid.2-4. . . . . . . . . . . . . . . . . . . . . . . . . . . . .Covariance matrices of Hadamard inverse solutionsity levels of sizeset to 100.2-5x̂inv for several spar-63 vector x (k is the number of non-zero entries).non-zero support of26Thex was randomly selected and non-zero entries were. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30Simulated violation probability using Hadamard multiplexing (blue)and the derived theoretical lower bound (red) in Equation (2.16) vs.number of zeros. The re ectivity vectorxsupport of signalwere all set to2-6100.(Left) MSE vs.strengthα,has size15.The non-zerowas randomly generated and its non-zero entries. . . . . . . . . . . . . . . . . . . . . . . . . . . .number of non-zeroswherexx α · 1n 1n0 .(Right) RMSE vs.is a constant vector.931signal. . . . . . . . .33
2-7Re ectivity estimates of the MIT logo image (top) and the SheppLogan image (bottom) from traditional pixelwise ML and the proposedCML that uses multiplexed measurements. All images are sized129.2-8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36Re ectivity estimates of the Mandrill image (top) and the cameramanimage (bottom) using CPML. All images are sized3-1127 Data acquisition model. Rate functionλi,j (t)127 129. . . .37of inhomogeneous Pois-son process combining desired scene response and noise sources isshown for pixel(i, j).Here,N 3andki,j 2.A noise photon(red) was detected after the second transmitted pulse at(1)ti,j ,and asignal photon (blue) was detected after the third transmitted pulse at(2)ti,j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423-2Experimental setup for single-photon imaging. . . . . . . . . . . . . .513-3Resolution test experiments. Re ectivity chart imaging (top) was doneusingTa 300 µs and mean photon count of 0.48.(bottom) was done usingTa 6.2 µs,33 % of the pixels missing data.Depth chart imagingmean photon count of1.1,andThe mean photon count was computedsimply by averaging the number of photon counts at every pixel overthe xed acquisition time. . . . . . . . . . . . . . . . . . . . . . . .3-4Experimental results for imaging natural scenes.3-5Comparison between our framework and LIDAR technology for 3Dimaging.54. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55100 independent trials for two natural scenes.563-6Sample MSE images with3-7E ect of dwell timeTa3D recovery method.and signal-to-background ratio (SBR) on ourFor acquisition times ofcalculated the mean photon countrespectively.3-8. . . . . . . . . . .52ki,j100 µsandover all pixels to be50 µs,we1.4 and 0.6,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57Distributions of generalized Gaussian random variables for several values ofpwith xedσ. . . . . . . . . . . . . . . . . . . . . . . . . . .1059
3-9Comparison of MSE of time-delay recovery using single-photon detections for two di erent illumination pulses.Gaussian pulse, andsy (t),(Left) Plot ofsx (t),aan arbitrary bimodal pulse. (Right) MSEof ML estimators vs. number of photon detections.11. . . . . . . . . .62
12
Chapter 1IntroductionModern optical imaging systems collect a large number of photon detections in orderto suppress optical detector noise and form accurate images of object properties. Forexample, a commercially available digital camera provides the user with a clean photograph by detecting trillions of photons with the sensor array. Traditional imagersare thus required to operate with long acquisition times or at high light levels suchthat the total optical ux hitting the detector is su ciently high.In this thesis, we propose two computational imagers (one passive, one active)that can accurately recover images of scene properties, such as re ectivity and 3Dstructure, at low- ux regimes where the mean photon count per pixel can even be lessthan one. The core principle that allows high-quality imaging for both proposed imagers is the combination of the photodetection physics with the statistical propertiesof image representations. The proposed imagers are as follows.1.A single-pixel camera with high photon e ciency:We propose a passivesingle-pixel re ectivity imager that can accurately estimate the scene re ectivity in photon-limited imaging scenarios by using an extension of the theory ofmultiplexed sensing. The proposed method, which makes use of the physicallyrealistic constraint that re ectivity values are non-negative, disproves the accepted wisdom that re ectivity estimation based on multiplexed measurementsalways degrades imaging performance under low light-level Poisson noise of the13
photodetector. We demonstrate through numerical experiments that the proposed imager outperforms the classical single-pixel camera that takes directraster observations at low light levels.2.An active 3D imaging system with high photon e ciency:We pro-pose an active imager that will simultaneously recover scene re ectivity and3D structure with high accuracy using a single-photon detector. The proposedimager allows high-quality 3D imaging by combining the accurate single-photoncounting statistics with the prior information that natural scenes are spatiallycorrelated.Experimental results show that the proposed imager outperformsstate-of-the-art 3D imaging methods that incorporate denoising algorithms. Weform accurate 3D and re ectivity images even when the mean number of photon detections at a pixel is close to1.Also, we give an information-theoreticframework that can be used to choose optimal design parameters such as theillumination pulse shape, at least for the pixelwise imaging scenario.Higher photon e ciency of an imaging system directly translates to shorter data acquisition time.For 3D imaging speci cally, it can translate to lower illuminationpower and longer range imaging. Thus, the theory of highly photon-e cient imag-real-timeimaging systems that can robustly operate at low-power and under low light-leveling in this thesis opens up many interesting research areas for buildingconditions.The remainder of the thesis is organized as follows. In Chapter2,we discuss thesingle-pixel camera and propose a computational imaging method that achieves highphoton e ciency in estimating scene re ectivity.Chapter3describes the methodof 3D imaging using an active illumination source and a single-photon detector, andproposes a highly photon-e cient computational 3D imaging method.gives the conclusions of the two proposed imaging frameworks.14Chapter4
Bibliographical NoteParts of Chapter 2 appear in the paper: D. Shin, A. Kirmani, and V. K. Goyal, Low-rate Poisson intensity estimationusing multiplexed imaging",Proceedings of IEEE International Conference onAcoustics, Speech and Signal Processing, 2013, pp.1364-1368.Parts of Chapter 3 appear in the papers: D. Shin, A. Kirmani, V. K. Goyal, and J. H. Shapiro, Computational 3D andre ectivity imaging with high photon e ciency",Accepted for publication atIEEE International Conference on Image Processing, 2014. D. Shin, A. Kirmani, A. Colaço, and V. K. Goyal, Parametric Poisson processimaging",Proceedings of IEEE Global Conference on Signal and InformationProcessing, 2013, pp. 1053 1056.D. Shin, A. Kirmani, V. K. Goyal, and J. H. Shapiro, Information in a photon:relating entropy and maximum-likelihood range estimation using single-photoncounting detectors",Processing, 2013, pp. Proceedings of IEEE International Conference on Image83 87.A. Kirmani, D. Venkatraman,D. Shin,A. Colaço, F. N. C. Wong, J. H.Shapiro, and V. K. Goyal, First-photon imaging",Science, vol.343, no. 6166,pp. 58 61, 2014. A. Kirmani, A. Colaço,D. Shin,and V. K. Goyal, Spatio-temporal regular-ization for range imaging with high photon e ciency",2013, vol. 8858, pp. 88581F.15Proceeedings of SPIE,
16
Chapter 2Single-Pixel Re ectivity Imaging withHigh Photon E ciency2.1 Prior WorkPassive optical imaging relies on an ambient light source to form an image of thescene re ectivity. Commercially available digital cameras are well-known examples ofpassive optical imagers. Since a two-dimensional sensor array is used for a camera,the re ectivity image is formed by measuring the total optical power hitting thephotodetector over a nite acquisition time at every image pixel. The array allowsthe pixelwise measurements to be made in parallel.Unlike cameras with a two-dimensional sensor array, the single-pixel camera [1]uses a single photodetector that takes pixelwise measurements not in parallel, butsequentially using a light modulator. The single-pixel camera has its advantages insize, complexity, and cost compared to an array-based camera. However, array basedsensing is still preferred over single-pixel sensing when having a short acquisition timeis important such as in real-time imaging.The single-pixel camera is particularly useful in low light-level imaging scenarios,in which one is required to use single-photon avalanche detectors and photomultipliers,that are typically not available as arrays.Accurate formation of intensity imagesat low light levels is important in engineering applications such as astronomy [2],17
night vision [3], medical imaging applications such as positron emission tomography(PET), and imaging of light-sensitive biological and chemical samples [4].In allof these applications, the low-light measurements are collected using single-photondetectors. The main challenge is that the measurements made using such detectorsare inherently noisy due to low photon-count levels and are thus corrupted by signaldependent photon noise that comes from the quantum nature of light detection. Inthis section, we survey several techniques for low light-level imaging using a singlepixel camera equipped with a photon-number resolving detector.2.1.1 Classical Passive Re ectivity ImagingLetxbe the ideal pixelated scene re ectivity of sizein imaging. If the scene is two-dimensional, thenxn 1that we are interestedis its vectorized version. Here,we include the e ects of passive illumination and radial fall-o of optical ux in there ectivity vectorx.At every image pixel, we use the photon-counting photodetectorto record the number of photons detected in an acquisition time ofa total ofnyiSince we haveimage pixels in the single-pixel camera, the total image acquisition timeusing raster scanning then equalsLetTa .nTa .be the photon count measurement that the photodetector makes at the i-thpixel. In the absence of illumination, our observationscounts. We denote the dark count rate asd 0.yiare simply detector darkWe assume that we knowdexactlythrough a calibration process prior to the imaging experiment. The photon countingnoise that corrupts our observations is known as shot noise and is well-modeled asPoisson distributed [5]. Our observation model at pixeliis thenyi Poisson(Ta (xi d)).The probability mass function of our observation at pixelPr[Yi yi ; xi , d] exp{ Ta (xi18(2.1)iis thus d)} (Ta (xi d))yi,yi !(2.2)
Ta 100Ta 10Ta 1Ta 0.1d 0.1d 1d 10d 100Figure 2-1: E ect of shot noise on image quality for several acquisition timesand dark count rate valuesimage isford (bottom).Ta(top)The maximum re ectivity value of the saturn25.yi 0, 1, 2, . . .mate from our dataThus, the maximum-likelihood (ML) pixelwise re ectivity esti-y [y1 , . . . , yn ]Tis simplyx̃ y/Ta d,whered [d, . . . , d]T .We observe that the ML estimate is obtained by normalizing and bias-correcting theraw photon count observationsx̃at the i-th pixel is Var(x̃i )y.The variance of the pixelwise re ectivity estimate (xi d)/Ta .As shown in Figure 2-1, we observe thattraditional pixelwise ML estimate using the single-pixel camera is limited to havinga long acquisition timeTaand low dark count ratedto minimize the variance fromshot noise and form high-quality images in photon-limited scenarios.2.1.2 Single-Pixel Camera based on Compressive SensingRecently, the authors of [6] developed an architecture for a photon-e cient single-pixelcamera that uses compressed sensing theory. The theory of compressed sensing [7]accurate image formation is guaranteed with high probability even when the number of measurements is less than the number of image pixels. Although it uses onlyone photodetector like the raster-scanned system considered above, the compressedsensing imaging setup has a major di erence from that of traditional pixelwise imaging. Unlike traditional imaging which involves sensing one image pixel at a
Computational 3D and Re ectivity Imaging with High Photon E ciency by Dongeek Shin Submitted to the Department of Electrical Engineering and Computer Science
