1.

INTRODUCTION

The Compressive Sensing (CS) theory^{1, 2} offers a much more economical sensing framework, in terms of number of samples, compared to the traditional Shannon-Nyquist paradigm. A natural application of CS is for 3D imaging due to the large dimensionality of the 3D data. The acquisition of 3D is always challenged by the fact that the available sensors have at most two-dimensions. Moreover, the captured data is typically large, thus often imposes demanding storage memory and transmission bandwidth requirements. All those challenges can be remedied by employing a CS scheme³.

Randomization of the sensing process plays a pivotal role in the CS theory³. Usually the data, or its transform, are uniformly sampled. However, images typically possess inherent properties that can be better exploited by employing a non-uniform sampling process. Indeed, a decade ago we have introduced the concept of non-uniform random CS sampling for Fresnel coherent digital holography.⁴ Here we overview the non-uniform CS random concept and demonstrate its application for 3D coherent and incoherent holography, and for 3DLiDAR imaging. In Section 2 we supply a heuristic motivation for non-uniform random sampling in CS. In Sec. 3 we overview applications of the variable density random CS scheme for holography, and in Sec, 4 we overview recent application for LiDAR imaging.

2.

HEURISTIC MOTIVATION FOR THE VARIABLE DESITY SAMPLING SCHEME

The CS process is a linear sensing process mathematically described by

where f is an N dimensional vector describing the input, g is an M dimensional vector describing the measurements, and Φ is an M by N matrix describing the sensing process. The sensing matrix is performing dimensional reduction, therefore M<N. If the input f is sparse and if the sensing matrix Φ exhibits certain technical properties, the input can be reconstructed from the lower dimensional g by employing appropriate algorithms.³ In case that the signal f is not sparse in its native representation, the CS framework still can be applied if it can be represented as a linear transform of a sparse vector α:

There are two main types of CS sensing processes: by random modulation (RM), and by using a random basis ensemble (RBE)³. The sensing matrix for a RM is an M by N sensing random matrix with entries drawn from a sub-Gaussian distribution, such as Gaussian or Bernoulli. The RM is often preferable because it is universal (in the sense that it is applicable to any sparse representation Ψ), and theoretical guarantees for its performance are available. However, it is not always possible to realize the RM with optical hardware. Another shortcoming of the RM in context of 3D imaging is that the random matrix Φ is prohibitively large for storage and reconstruction.

In this paper we consider the RBE scheme. With this scheme, Φ is constructed from a unitary matrix with rows picked at random. This process is illustrated in Fig. 1. The best known such a sensing scheme is the random partial Fourier (RPF) matrices.

Fig. 1

. The RBE CS process; the sensing matrix Φ is constructed by choosing randomly M rows from an orthogonal matrix.

In the construction of the RBE sampling (Fig. 1) no other prior information about the signal is considered besides the sparsity prior. However there are structural properties common for large classes of signals that can be utilized. Consider for example the case that RBE implemented with Φ being a Fourier transform, leading to the RPF matrix. It is well-known that most of a natural signal energy is concentrated at the low spatial frequencies, and follow a power-low decay distribution (Fig. 2). This implies that more sensing effort should be placed in the lower frequencies than in the higher frequencies. Consequently, a non-uniform random sampling as that illustrated in Fig. 2 should better capture the image information. As illustrated in Fig. 2 the density of the samples are higher al low-frequencies and gradually decays for higher frequencies. We emphasize that the randomized sampling process should be maintained in order to capture information at all the frequencies.

Fig. 2

Variable density with random partial Fourier sampling employing the variation of the image Fourier coefficients over the frequencies (note that their density is larger for lower frequencies).

3.

COMPRESSIVE HOLOGRAPHY WITH VARIABLE SAMPLING DENSITY

3.1

Variable sampling for coherent compressive holography

We have first proposed variable random density sensing approach for Fresnel holography in Ref. 4 Starting from a certain object-to-sensor distance (Fig. 3) the Fresnel transform, which describes the object field propagation, behaves as a Fourier transform.^{3, 5-7} In such a case the conditions described in Fig. 2 hold, implying that more random samples should be taken at the center of the hologram and fewer random samples at the margin of the hologram (Fig. 3). The variable random sampling scheme can be motivated also through a phase space analysis, as done in Ref. 4.

Fig. 3.

In Fresnel holography the sensing model is closely related to the RPF (Fig. 2), therefore the hologram plane should be better sampled randomly with a variable density.

Figure 4 demonstrates the advantage of the variable-density random sampling for compressive off-line Fresnel holography⁸. The object is a 5NIS coin that was captured with off-line Fresnel holography [Fig. 4(a)]. Figure 4(b) shows the uniform random sampling pattern while Fig. 4(c) shows the variable-density random pattern. In both cases only 6% of the samples were used. The respective reconstruction are shown in Figs. 4 (d)-(e) exhibiting an improvement of 2.2 dB with the variable-density scheme.

Fig. 4

Compressive off-line holography of a 5NIS coin with uniformly random (b), variable density (c) sampling, and respective reconstructions (d) and (e).

4.

VARIABLE DENSITY SAMPLING FOR COMPRESSIVE LIDAR

The light detection and ranging (LiDAR) system¹³ is a 3D imaging system that operates by scanning the distance to objects in the scene by using a laser range finder. The distance measurement is achieved by converting to distance the time it takes for a laser pulse to get to the target and back. Instead of the common raster scanning, it is more efficient to sample the scene using the CS techniques. Such CS LiDAR system is usually implemented by using the single pixel camera (SPC) scheme¹⁴, as illustrated in fig. 5. Our system operates by sending a short laser pulse (~1 ns) to the scene and collects the light back through a telescope onto a digital micro-mirror device (DMD), and from it to a single photon counter detector.¹⁵ The DMD is made of tiny micro-mirror elements that can divert the light towards and away from the detector. By changing the direction of the micro-mirrors, the 3D image can then be encoded. The patterns imprinted on the DMD are Hadamard patterns.

Fig. 5

The SPC LiDAR scheme. The laser pulse returning from the scene is focused on a DMD by a telescope. The resulting 3D image is then encoded by changing the direction of each micro-mirror to and away from the photon counting detector.

The CS scheme with a Hadamard sensing matrix is shown in Fig. 6 (a). Instead of choosing the Hadamard matrix rows uniformly at random, a variable density sampling scheme that exploits the statistics of the wavelet transform can be employed.¹⁶ Fig. 5(b) depicts the wavelet transform W of an image (Lena). As it can be seen, the horizontal, vertical and diagonal wavelet detail coefficients subbands have different significant coefficient densities.¹⁷ This observation motivates a variable density sampling scheme that is shown in Fig. 5(c). Each detail coefficients sub-band should then be sampled according to its coefficient density. The product between a multiscale ordered Hadamard sampling matrix¹⁶ and the Haar wavelet can be shown⁵ to be a block diagonal matrix [Fig. 5(d)]. Each detail coefficients sub-bands can then be sampled separately according to a variable sampling scheme.

Fig. 6

(a) CS scheme with a Hadamard sampling matrix. (b) A wavelet transform of the image (Lena). (c) Variable density sampling map of the wavelet coefficients according to the detail coefficients sub-band significant coefficient densities. (d) Variable density Hadamard sampling according to the wavelet scales.

The utility of the random CS with variable-density is demonstrated in Fig. 7. In Fig. 7 (a) a full 3D LiDAR point cloud data of a small area patch of a hospital building¹⁸ is presented. A reconstruction using the Variable Density Sampling with the multiscale ordered Hadamard sensing matrix¹⁹ at a compression ratio of 10:1 is shown in Fig. 7 (b). The reconstruction shows an almost identical distribution to the original 3D point cloud. This is achieved by using the a-priory information about the wavelet sub-band coefficient density of 3D images with the variable sampling. In contrast, the uniform, random sampling with the Hadamard sensing matrix can be seen to have a very poor reconstruction relatively to the fully scanned 3D point cloud.

Fig. 7

(a) Original 3D LiDAR point cloud data of a small area patch of a hospital building. (b) Reconstruction of the 3D point cloud using the Variable Density Sampling with the Multiscale ordered Hadamard sensing matrix (CR = 10:1). (c) Reconstruction of the 3D point cloud using the uniform random sampling with the Hadamard sensing matrix (CR = 10:1).

5.

CONCLUSIONS

We have shown that introducing some order in the common randomization CS process the performance of 3D sensing can be improved. Considering the structure exhibited by sparse representations obtained with sparsifiers such as Fourier, Fresnel and wavelet transforms, we have developed non-uniformly randomized sampling CS schemes. We have demonstrated the benefits of the variable random sampling scheme for coherent Fresnel holography, for incoherent holography, and for 3D LiDAR imaging.