### 单像素成像中哈达玛基掩模优化排序前沿进展

Frontier Advances in Optimized Ordering of the Hadamard Basis Patterns Used in Single-Pixel Imaging

1 北京理工大学物理学院，北京 100081
2 北京理工大学先进光电量子结构设计与测量教育部重点实验室，北京 100081

Abstract
Single-pixel imaging applies a series of spatial light modulated patterns to subsample the target scene with the assistance of a single-pixel detector, and subsequently reconstructs the object image according to the correlation between patterns and measurements. This indirect image acquisition method ensures reconstruction quality because of the reconstruction algorithm applied, and more crucially, the measurement mask construction. With the introduction of compressed sensing theory, random patterns emerged, but making the measurements blind and lacking specificity. Such patterns fail to facilitate storage and calculation, and thus significantly limit spatial pixel resolution. Recently, Hadamard basis patterns received widespread attention owing to their structured features that enable fast computation and facilitate storage and extraction. Considering this, numerous optimized ordering methods for the Hadamard basis patterns were developed, and proven to significantly reduce the sampling ratios. This study systematically reviews the design frameworks and frontier advances of these methods, and summarizes the future development trends of deterministic pattern construction. Finally, this contribution provides a beneficial reference point including guidance for subsequent research in this specific field.

## 2.1　单像素成像的数学测量模型

$y=Ax+e=AΨx'+e=Φx'+e,$

$minx'λx'τ+η2AΨx'-y22,$

## 2.2　单像素成像的受限等距性质

$1-δKx'22≤Φx'≤1+δKx'22,$

## 3　哈达玛基掩模优化排序

Hadamard矩阵是由1和-1元素组成的$n$阶方阵，记作$Hn∈Rn×n$，满足$HnHnT=HnTHn=nIn$，其中，$In$为单位矩阵。所以，$1nHn$为标准正交矩阵，满足$(1nHn)(1nHn)T=(1nHn)T(1nHn)=In$$Hn$的行列式$det(Hn)=nn/2$。只有当$n=2$或者$n$是4的整数倍时，Hadamard矩阵才存在。规范化Hadamard矩阵为对称矩阵，其第1行和第1列均为1。$Hn$的任意一行或者任意一列称为基底/基，并且该矩阵的任意两行或任意两列相互正交，其点积和为0。Hadamard矩阵在信息论、信号处理、光学成像、移动通信等领域应用非常广泛，其基底/基还可用来仿真码分多址中各个用户的扩频波形向量。若将完整的Hadamard矩阵$Hn$左乘于$x$，便是对$x$实施了Hadamard变换，由于$Hn$的元素只取1和-1，故Hadamard变换也是唯一只使用加减法的标准正交变换。而在SPI中，一般选取Hadamard矩阵的前面连续若干行组成子矩阵，作为测量矩阵，而其中的每一行均可重组为一个调制掩模。

## 3.1.1　自然序

$Hn=Hn/2Hn/2Hn/2-Hn/2,$

$H2=111-1。$

$Hn=Hn/2⊗H2=H2⊗⋯⊗H2︸k。$

## 3.1.8　多分辨率管线序

$HPE:,:,i=HPE:,:,1=+H+H+H+HHPE:,:,2=+H+H-H-HHPE:,:,3=+H-H+H-HHPE:,:,4=+H-H-H+H$

## 3.2.5　索引序

$fdi,j=ij,d=0id+jd1/d,d≠0,$

## 5　确定性掩模构造的思考

#### Table 1. Hadamard basis pattern optimized ordering and within-pattern pixel alignment methods

CategoryMethodDesign ideaFeature description
Space domainNatural orderRecursionOriginal order
Sequency orderNumber of sign changes within each basisIncremental order of the number of 1D connected domains
Random orderRandomly disrupt the basesNot random within each pattern
Russian dolls orderRecursive grouping and inclusionGrouping + 2D connected domains
Origami orderSymmetrical reverse folding，axial symmetry，and partial order adjustmentFiner grouping + 2D connected domains
Cake-cutting orderCounting the number of 2D connected domainsIncremental order of the number of 2D connected domains
Multi-resolution pipeline orderUsing the pipeline encoderEvolution of grouping
Frequency domainDiscrete cosine transform orderPerforming discrete cosine transformTransform + norm
Wavelet transform orderPerforming wavelet transformTransform + norm
Discrete Fourier transform orderPerforming discrete Fourier transformTransform + norm
Total variation orderCalculating total variationTotal variation（norm）
Index orderDesigning index functionIndex function
Gray-level co-occurrence matrix contrast orderUtilizing gray-level co-occurrence matrixTextural feature of basis patterns
Within-pattern pixel alignmentRow-major or column-major alignmentHorizontal and vertical linesIsometric resolution
Zigzag alignmentSlanting linesIsometric resolution
Snake alignmentFolded linesIsometric resolution
Visual fovea diffusion arrangementSpiraling outwards from visual foveaSpatially variant pixel grid with multi-resolution

## 6　总结与展望

[1] Yu W K, Liu X F, Yao X R, et al. Single-photon compressive imaging with some performance benefits over raster scanning[J]. Physics Letters A, 2014, 378(45): 3406-3411.

[2] BracewellR N. The Fourier transform and its applications[M]∥McGraw-Hill series in electrical engineering, networks and systems. 2nd ed. New York: McGraw-Hill, 1986.

[3] Pratt W K, Kane J, Andrews H C. Hadamard transform image coding[J]. Proceedings of the IEEE, 1969, 57(1): 58-68.

[4] Sloane N J A, Harwit M. Masks for Hadamard transform optics, and weighing designs[J]. Applied Optics, 1976, 15(1): 107-114.

[5] Swift R D, Wattson R B, Decker J A,, et al. Hadamard transform imager and imaging spectrometer[J]. Applied Optics, 1976, 15(6): 1595-1609.

[6] Duarte M F, Davenport M A, Takhar D, et al. Single-pixel imaging via compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 83-91.

[7] Shapiro J H. Computational ghost imaging[J]. Physical Review A, 2008, 78(6): 061802.

[8] 马宇轩, 孟照魁, 黄宏旭, 等. 高速结构光器件及其在光学成像与测量中的应用[J]. 光学学报, 2022, 42(17): 1723001.

Ma Y X, Meng Z K, Huang H X, et al. High-speed structured optical devices and their applications in optical imaging and measurement[J]. Acta Optica Sinica, 2022, 42(17): 1723001.

[9] 吴自文, 邱晓东, 陈理想. 关联成像技术研究现状及展望[J]. 激光与光电子学进展, 2020, 57(6): 060001.

Wu Z W, Qiu X D, Chen L X. Current status and prospect for correlated imaging technique[J]. Laser & Optoelectronics Progress, 2020, 57(6): 060001.

[10] Zhang Z B, Ma X, Zhong J G. Single-pixel imaging by means of Fourier spectrum acquisition[J]. Nature Communications, 2015, 6: 6225.

[11] 邵晓鹏, 刘飞, 李伟, 等. 计算成像技术及应用最新进展[J]. 激光与光电子学进展, 2020, 57(2): 020001.

Shao X P, Liu F, Li W, et al. Latest progress in computational imaging technology and application[J]. Laser & Optoelectronics Progress, 2020, 57(2): 020001.

[12] Edgar M P, Gibson G M, Padgett M J. Principles and prospects for single-pixel imaging[J]. Nature Photonics, 2019, 13(1): 13-20.

[13] Gibson G M, Johnson S D, Padgett M J. Single-pixel imaging 12 years on: a review[J]. Optics Express, 2020, 28(19): 28190-28208.

[14] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[15] Katz O, Bromberg Y, Silberberg Y. Compressive ghost imaging[J]. Applied Physics Letters, 2009, 95(13): 131110.

[16] Studer V, Bobin J, Chahid M, et al. Compressive fluorescence microscopy for biological and hyperspectral imaging[J]. Proceedings of the National Academy of Sciences of the United States of America, 2012, 109(26): E1679-E1687.

[17] Pian Q, Yao R Y, Sinsuebphon N, et al. Compressive hyperspectral time-resolved wide-field fluorescence lifetime imaging[J]. Nature Photonics, 2017, 11(7): 411-414.

[18] Howland G A, Dixon P B, Howell J C. Photon-counting compressive sensing laser radar for 3D imaging[J]. Applied Optics, 2011, 50(31): 5917-5920.

[19] Zhao C Q, Gong W L, Chen M L, et al. Ghost imaging lidar via sparsity constraints[J]. Applied Physics Letters, 2012, 101(14): 141123.

[20] Wu H D, Zhao M, Li F Q, et al. Underwater polarization-based single pixel imaging[J]. Journal of the Society for Information Display, 2020, 28(2): 157-163.

[21] 杨莫愁, 吴仪, 冯国英. 水下鬼成像的研究进展[J]. 光学学报, 2022, 42(17): 1701003.

Yang M C, Wu Y, Feng G Y. Research progress on underwater ghost imaging[J]. Acta Optica Sinica, 2022, 42(17): 1701003.

[22] Clemente P, Durán V, Tajahuerce E, et al. Compressive holography with a single-pixel detector[J]. Optics Letters, 2013, 38(14): 2524-2527.

[23] 张华, 曹良才, 金国藩, 等. 基于压缩感知算法的无透镜数字全息成像研究[J]. 激光与光电子学进展, 2020, 57(8): 080001.

Zhang H, Cao L C, Jin G F, et al. Progress on lensless digital holography imaging based on compressive holographic algorithm[J]. Laser & Optoelectronics Progress, 2020, 57(8): 080001.

[24] Li X H, Deng C J, Chen M L, et al. Ghost imaging for an axially moving target with an unknown constant speed[J]. Photonics Research, 2015, 3(4): 153-157.

[25] Shi D F, Yin K X, Huang J, et al. Fast tracking of moving objects using single-pixel imaging[J]. Optics Communications, 2019, 440: 155-162.

[26] Jiao S M, Sun M J, Gao Y, et al. Motion estimation and quality enhancement for a single image in dynamic single-pixel imaging[J]. Optics Express, 2019, 27(9): 12841-12854.

[27] Sun S A, Gu J H, Lin H Z, et al. Gradual ghost imaging of moving objects by tracking based on cross correlation[J]. Optics Letters, 2019, 44(22): 5594-5597.

[28] Deng Q W, Zhang Z B, Zhong J G. Image-free real-time 3-D tracking of a fast-moving object using dual-pixel detection[J]. Optics Letters, 2020, 45(17): 4734-4737.

[29] Yu W K. Cryptographic key distribution over a public network via variance-based watermarking in compressive measurements[J]. Applied Optics, 2019, 58(19): 5294-5300.

[30] Yu W K, Wei N, Li Y X, et al. Multi-party interactive cryptographic key distribution protocol over a public network based on computational ghost imaging[J]. Optics and Lasers in Engineering, 2022, 155: 107067.

[31] Yu W K, Yang Y, Li Y X, et al. Multi-party cryptographic key distribution protocol over a public network based on a quick-response code[J]. Sensors, 2022, 22(11): 3994.

[32] Chan W L, Charan K, Takhar D, et al. A single-pixel terahertz imaging system based on compressed sensing[J]. Applied Physics Letters, 2008, 93(12): 121105.

[33] Watts C M, Shrekenhamer D, Montoya J, et al. Terahertz compressive imaging with metamaterial spatial light modulators[J]. Nature Photonics, 2014, 8(8): 605-609.

[34] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61.

[35] PatiY C, RezaiifarR, KrishnaprasadP S. Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[C]∥Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, November 1-3, 1993, Pacific Grove, CA, USA. New York: IEEE Press, 2002: 40-44.

[36] Daubechies I, Defrise M, De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J]. Communications on Pure and Applied Mathematics, 2004, 57(11): 1413-1457.

[37] Wang Y L, Yang J F, Yin W T, et al. A new alternating minimization algorithm for total variation image reconstruction[J]. SIAM Journal on Imaging Sciences, 2008, 1(3): 248-272.

[38] 宗岩峰, 郑淮斌, 吴鑫伟, 等. 基于时序控制的赝热光鬼成像系统[J]. 光学学报, 2023, 43(7): 0711001.

Zong Y F, Zheng H B, Wu X W, et al. Sequence-controlled pseudothermal optical ghost imaging system[J]. Acta Optica Sinica, 2023, 43(7): 0711001.

[39] Candès E J, Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.

[40] Candès E J. The restricted isometry property and its implications for compressed sensing[J]. Comptes Rendus Mathematique, 2008, 346(9/10): 589-592.

[41] EladM. Sparse and redundant representations: from theory to applications in signal and image processing[M]. New York: Springer, 2010.

[42] Candès E J, Tao T. Near-optimal signal recovery from random projections: universal encoding strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[43] Yu W K, Liu X F, Yao X R, et al. Complementary compressive imaging for the telescopic system[J]. Scientific Reports, 2014, 4: 5834.

[44] Yu W K, Yao X R, Liu X F, et al. Compressive moving target tracking with thermal light based on complementary sampling[J]. Applied Optics, 2015, 54(13): 4249-4254.

[45] Yu W K, Yao X R, Liu X F, et al. Compressive microscopic imaging with “positive-negative” light modulation[J]. Optics Communications, 2016, 371: 105-111.

[46] Li Y X, Yu W K, Leng J A, et al. Pseudo-thermal imaging by using sequential-deviations for real-time image reconstruction[J]. Optics Express, 2019, 27(24): 35166-35181.

[47] Sun M J, Meng L T, Edgar M P, et al. A Russian Dolls ordering of the Hadamard basis for compressive single-pixel imaging[J]. Scientific Reports, 2017, 7: 3464.

[48] Yu W K, Liu Y M. Single-pixel imaging with origami pattern construction[J]. Sensors, 2019, 19(23): 5135.

[49] Yu W K. Super sub-Nyquist single-pixel imaging by means of cake-cutting Hadamard basis sort[J]. Sensors, 2019, 19(19): 4122.

[50] Yu W K, Li M F, Yao X R, et al. Adaptive compressive ghost imaging based on wavelet trees and sparse representation[J]. Optics Express, 2014, 22(6): 7133-7144.

[51] Dai H D, Gu G H, He W J, et al. Adaptive video compressed sampling in the wavelet domain[J]. Optics & Laser Technology, 2016, 81: 90-99.

[52] Wu H, Zhao G P, Wang R Z, et al. Computational ghost imaging system with 4-connected-region-optimized Hadamard pattern sequence[J]. Optics and Lasers in Engineering, 2020, 132: 106105.

[53] MundyJ L, JoynsonR E. Pipeline Walsh-Hadamard transformations: US3956619[P]. 1976-05-11.

[54] Fan C P, Yang J F. Fixed-pipeline two-dimensional Hadamard transform algorithms[J]. IEEE Transactions on Signal Processing, 1997, 45(6): 1669-1674.

[55] Zhou C, Zhao X W, Huang H Y, et al. Multi-resolution single-pixel imaging via Hadamard ‘pipeline’ coding[J]. Applied Physics B, 2020, 126(10): 163.

[56] Gao Z H, Li M H, Zheng P X, et al. Single-pixel imaging with Gao-Boole patterns[J]. Optics Express, 2022, 30(20): 35923-35936.

[57] 李明飞, 阎璐, 杨然, 等. 基于Hadamard矩阵优化排序的快速单像素成像[J]. 物理学报, 2019, 68(6): 064202.

Li M F, Yan L, Yang R, et al. Fast single-pixel imaging based on optimized reordering Hadamard basis[J]. Acta Physica Sinica, 2019, 68(6): 064202.

[58] Yu X, Yang F, Gao B, et al. Deep compressive single pixel imaging by reordering Hadamard basis: a comparative study[J]. IEEE Access, 2020, 8: 55773-55784.

[59] Vaz P G, Gaudêncio A S, Ferreira L F R, et al. Re-ordering of Hadamard matrix using Fourier transform and gray-level co-occurrence matrix for compressive single-pixel imaging in low resolution images[J]. IEEE Access, 2022, 10: 46975-46985.

[60] Yu X, Stantchev R I, Yang F, et al. Super sub-Nyquist single-pixel imaging by total variation ascending ordering of the Hadamard basis[J]. Scientific Reports, 2020, 10: 9338.

[61] 袁梓豪, 赵琳琳, 李明飞, 等. 一种对Hadamard测量基进行排序的方法: CN111130556A[P]. 2020-05-08.

YuanZ H, ZhaoL L, LiM F, et al. A method for reordering the Hadamard measurement basis: CN111130556A[P]. 2020-05-08.

[62] Ben-Artzi G, Hel-Or H, Hel-Or Y. The gray-code filter kernels[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(3): 382-393.

[63] López-García L, Cruz-Santos W, García-Arellano A, et al. Efficient ordering of the Hadamard basis for single pixel imaging[J]. Optics Express, 2022, 30(8): 13714-13732.

[64] Ma H Y, Sang A J, Zhou C, et al. A zigzag scanning ordering of four-dimensional Walsh basis for single-pixel imaging[J]. Optics Communications, 2019, 443: 69-75.

[65] Thiele S, Arzenbacher K, Gissibl T, et al. 3D-printed eagle eye: compound microlens system for foveated imaging[J]. Science Advances, 2017, 3(2): e1602655.

[66] Phillips D B, Sun M J, Taylor J M, et al. Adaptive foveated single-pixel imaging with dynamic supersampling[J]. Science Advances, 2017, 3(4): e1601782.

[67] Zhang K Y, Cao J, Hao Q, et al. Modeling and simulations of retina-like three-dimensional computational ghost imaging[J]. IEEE Photonics Journal, 2019, 11(1): 6900713.

[68] Zhai X, Cheng Z D, Hu Y D, et al. Foveated ghost imaging based on deep learning[J]. Optics Communications, 2019, 448: 69-75.

[69] Gao Z Q, Cheng X M, Zhang L F, et al. Compressive ghost imaging in scattering media guided by region of interest[J]. Journal of Optics, 2020, 22(5): 055704.

[70] Cao J E, Zhou D, Zhang F H, et al. A novel approach of parallel retina-like computational ghost imaging[J]. Sensors, 2020, 20(24): 7093.

[71] Hua J Y, Hua E K, Zhou F B, et al. Foveated glasses-free 3D display with ultrawide field of view via a large-scale 2D-metagrating complex[J]. Light: Science & Applications, 2021, 10: 213.

[72] Cao J E, Zhou D, Zhang Y Q, et al. Optimization of retina-like illumination patterns in ghost imaging[J]. Optics Express, 2021, 29(22): 36813-36827.

[73] Vaz P G, Amaral D, Ferreira L F R, et al. Image quality of compressive single-pixel imaging using different Hadamard orderings[J]. Optics Express, 2020, 28(8): 11666-11681.

[74] Yuan Y L A, Feng J, Jiao S M, et al. Adaptive and dynamic ordering of illumination patterns with an image dictionary in single-pixel imaging[J]. Optics Communications, 2021, 481: 126527.

[75] Higham C F, Murray-Smith R, Padgett M J, et al. Deep learning for real-time single-pixel video[J]. Scientific Reports, 2018, 8: 2369.

[76] Barbastathis G, Ozcan A, Situ G H. On the use of deep learning for computational imaging[J]. Optica, 2019, 6(8): 921-943.