Jing Liu, Guoxian Zhang, Kai Zhao, and Xiaoyu Jiang, "Compressive holography algorithm for the objects composed of point sources," Appl. Opt. 56, 530-542 (2017)
A compressive holography algorithm is proposed for the objects composed of point sources in this work. The proposed algorithm is based on Gabor holography, an amazingly simple and effective encoder for compressed sensing. In the proposed algorithm, the three-dimensional sampling space is uniformly divided into a number of grids since the virtual object may appear anywhere in the sampling space. All the grids are mapped into an indication vector, which is sparse in nature considering that the number of grids occupied by the virtual object is far less than that of the whole sampling space. Consequently, the point source model can be represented in a compressed sensing framework. With the increase of the number of grids in the sampling space, the coherence of the sensing matrix gets higher, which does not guarantee a perfect reconstruction of the sparse vector with large probability. In this paper, a new algorithm named fast compact sensing matrix pursuit algorithm is proposed to cope with the high coherence problem, as well as the unknown sparsity. A similar compact sensing matrix with low coherence is constructed based on the original sensing matrix using similarity analysis. In order to tackle unknown sparsity, an orthogonal matching pursuit algorithm is utilized to calculate a rough estimate of the true support set, based on the similar compact sensing matrix and the measurement vector. The simulation and experimental results show that the proposed algorithm can efficiently reconstruct a sequence of 3D objects including a Stanford Bunny with complex shape.
You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
Computational Complexity of the Ray Tracing Method and the Proposed Hologram Calculation Algorithm
Algorithm
On-Line Complexity
On-Line Operations
Ray tracing method
1 exp, , ,
Proposed algorithm
,
Algorithm 1
FCSMP Algorithm
Input: Sensing matrix , measurement vector
Output: The estimated signal
1. Constructing the similar compact sensing matrix (described in Section 4.B.1).
2. Obtaining an initial estimate of the correct subspace. The OMP algorithm is used to find an estimate of the support set based on the measurement vector and the similar compact sensing matrix . The estimated support set is represented as , , where indicates that the first element of corresponds to the th condensed column . We obtain an initial estimate of the correct subspace, , spanned by the columns , defined as .
For clarity of representation, the columns spanning the initial estimate of the correct subspace, , are defined as the contributing condensed columns, and their corresponding similar column groups, , are defined as the contributing similar column groups. Each contributing similar column group contains a set of columns from the original sensing matrix, e.g., , where indicates the number of columns in .
3. Testing each contributing similar column group one by one to find the true vectors spanning the correct subspace.
For the contributing similar column group ,
(a) Calculating the candidate subspaces corresponding to. List all the combination sets of as . The th combination set of is denoted as , where represents the number of combination sets in . In the initial estimate of the correct subspace, , replace the contributing condensed column with a combination set from . As a result, each combination set from , e.g., , together with the fixed contributing condensed columns from (expect ), forms a candidate subspace, e.g., the th candidate subspace is represented as .
(b) Finding the true combination set in. For each candidate subspace, , the proposed algorithm solves a least-squares problem to approximate the nonzero entries of the original sparse vector [Eq. (13)], and sets other entries as zeros [Eq. (14)], resulting in a candidate estimate , as where indicates the pseudo-inverse operation, is composed of the entries of indexed by , and is composed of the entries of indexed by . For each candidate estimate , calculate the residual via Eq. (15): The norm of is indicated as . Among the candidate subspaces, find the one with the least residual (the residual with the least norm), and choose its associate combination set (from ) as the true combination set, i.e., the true vectors from , that span the correct subspace. We denote the true combination set from as .
4. Repeating Step 3 for the remaining contributing similar column groups, . We can obtain a number of true combination sets, which are denoted as .
5. Obtaining a final estimate of the correct subspace. We can obtain the final estimate of the correct subspace by combining the true combination sets from all the contributing similar column groups, as .
6. Calculating the estimated signal. Based on the estimated subspace , the proposed algorithm solves a least-squares problem to approximate the nonzero entries of the original sparse vector [Eq. (16)], and sets other entries as zeros [Eq. (17)], resulting in a final estimate , as
Table 2.
Computational Complexity of the Proposed FCSMP Algorithm
Off-Line Processing
Rough Estimation
Refined Estimation
Table 3.
Computational Complexity of the SP, BP, GSSMP, and FCSMP Algorithms
Algorithm
SP
BP
GSSMP
FCSMP
Computational complexity
Table 4.
Computing Time in Hologram Calculation
BOX
Ray Tracing Method
Proposed Method
0.7605 s
0.0213 s
Cube Frame
Ray Tracing Method
Proposed Method
0.8717 s
0.0498 s
Stanford Bunny
Ray Tracing Method
Proposed Method
1.6287 s
0.0421 s
Table 5.
Reconstruction Errors and Computing Time in the Noiseless Condition
Object
“,” “,” “”
Algorithm
FCSMP
GSSMP
BCS
BP
SP
ERROR
0.0020
0.0009
0.3450
0.2440
1.2817
TIME (s)
49.7432
235.4573
29.4095
57.1620
22.9276
Object
Cube Frame
Algorithm
FCSMP
GSSMP
BCS
BP
SP
ERROR
0.0018
0.0006
0.8166
0.6202
1.3229
TIME (s)
51.5301
247.9542
31.2426
58.3590
29.0700
Object
Stanford Bunny
Algorithm
FCSMP
GSSMP
BCS
BP
SP
ERROR
0.4585
0.3038
0.5266
0.9625
1.3476
TIME (s)
120.7584
397.5426
107.0405
132.5899
101.7001
Tables (6)
Table 1.
Computational Complexity of the Ray Tracing Method and the Proposed Hologram Calculation Algorithm
Algorithm
On-Line Complexity
On-Line Operations
Ray tracing method
1 exp, , ,
Proposed algorithm
,
Algorithm 1
FCSMP Algorithm
Input: Sensing matrix , measurement vector
Output: The estimated signal
1. Constructing the similar compact sensing matrix (described in Section 4.B.1).
2. Obtaining an initial estimate of the correct subspace. The OMP algorithm is used to find an estimate of the support set based on the measurement vector and the similar compact sensing matrix . The estimated support set is represented as , , where indicates that the first element of corresponds to the th condensed column . We obtain an initial estimate of the correct subspace, , spanned by the columns , defined as .
For clarity of representation, the columns spanning the initial estimate of the correct subspace, , are defined as the contributing condensed columns, and their corresponding similar column groups, , are defined as the contributing similar column groups. Each contributing similar column group contains a set of columns from the original sensing matrix, e.g., , where indicates the number of columns in .
3. Testing each contributing similar column group one by one to find the true vectors spanning the correct subspace.
For the contributing similar column group ,
(a) Calculating the candidate subspaces corresponding to. List all the combination sets of as . The th combination set of is denoted as , where represents the number of combination sets in . In the initial estimate of the correct subspace, , replace the contributing condensed column with a combination set from . As a result, each combination set from , e.g., , together with the fixed contributing condensed columns from (expect ), forms a candidate subspace, e.g., the th candidate subspace is represented as .
(b) Finding the true combination set in. For each candidate subspace, , the proposed algorithm solves a least-squares problem to approximate the nonzero entries of the original sparse vector [Eq. (13)], and sets other entries as zeros [Eq. (14)], resulting in a candidate estimate , as where indicates the pseudo-inverse operation, is composed of the entries of indexed by , and is composed of the entries of indexed by . For each candidate estimate , calculate the residual via Eq. (15): The norm of is indicated as . Among the candidate subspaces, find the one with the least residual (the residual with the least norm), and choose its associate combination set (from ) as the true combination set, i.e., the true vectors from , that span the correct subspace. We denote the true combination set from as .
4. Repeating Step 3 for the remaining contributing similar column groups, . We can obtain a number of true combination sets, which are denoted as .
5. Obtaining a final estimate of the correct subspace. We can obtain the final estimate of the correct subspace by combining the true combination sets from all the contributing similar column groups, as .
6. Calculating the estimated signal. Based on the estimated subspace , the proposed algorithm solves a least-squares problem to approximate the nonzero entries of the original sparse vector [Eq. (16)], and sets other entries as zeros [Eq. (17)], resulting in a final estimate , as
Table 2.
Computational Complexity of the Proposed FCSMP Algorithm
Off-Line Processing
Rough Estimation
Refined Estimation
Table 3.
Computational Complexity of the SP, BP, GSSMP, and FCSMP Algorithms
Algorithm
SP
BP
GSSMP
FCSMP
Computational complexity
Table 4.
Computing Time in Hologram Calculation
BOX
Ray Tracing Method
Proposed Method
0.7605 s
0.0213 s
Cube Frame
Ray Tracing Method
Proposed Method
0.8717 s
0.0498 s
Stanford Bunny
Ray Tracing Method
Proposed Method
1.6287 s
0.0421 s
Table 5.
Reconstruction Errors and Computing Time in the Noiseless Condition