For image registration photo and video cameras with millions of pixels are usually used. Part of information in these images can be considered as superfluous. Development of computational photography new methods [1-2], including compressed sensing (CS, compressive sensing, compressed sampling) allows to obtain full object image with an acceptable quality through registration of several projections of object.
Compressed sensing (compressive sensing, sparse sampling, or) has become to be widely applied about ten years ago [3-6] and has already found a lot of opportunities for application:
For example, CS is being more and more widely used for digital holography tasks. Digital holography is a method that allows obtaining information about object's characteristics (amplitude or phase profile, temperature, index of refraction , etc.) by registration of interference of object and reference beams. CS was implemented for digital Gabor  and Fresnel  holograms in the visible range, for registration of amplitude  and phase  wave parameters by millimeter range holograms, for holographic tomography , for depth resolution increasing by inline holography , for acceleration of hologram processing by using graphic processors , and etc.
In the paper CS methods are considered and experimental results on reconstruction of binary and non-binary images from single-pixel camera registrations are given.
Compressed sensing is based on sparsity of signals. Decomposition of these signals in an appropriate basis contains many coefficients that are close or equal to zero. Since most coefficients are small then the relatively few large coefficients include majority of the object information. Therefore the method exploits the sparsity of a signal to achieve full signal reconstruction with a significantly little quantity of single measurements. Similar ideas underlie in many image, video and audio compression methods (such as JPEG , MPEG, and etc.).
Compressed sensing is based on Nyquist-Shannon's theorem: if an analog signal is bandlimited then it can be reconstructed lossless when discrete peaks are taken with the more often period than maximum frequency half-cycle. By nonlinear algorithms of reconstruction the high resolution signals and images can be reconstructed from incomplete data. A few number of selections decomposed in an appropriate basis that differs from the sparse signal basis are received in the beginning of the CS. Since the number of selections is limited the problem of image reconstruction in initial basis requires solution of underdetermined system of linear equations (system has fewer equations than variables). There are a huge number of various image candidates which can be result for this selection. Therefore to select the best candidate additional constraint is necessary to be introduced.
The classical solution of these problems is to minimize system energy (norm minimization). Usually it is mathematical operation including product of the reverse matrixes and basis selection. However this method can give not good results for many practical applications as few number of unknown coefficients (that are absent in selection) have zero energy. The sum in absolute values is subject to minimization . Therefore search algorithm of the candidate with the smallest norm can be written rather as the linear programming task that has already effective methods of solution. It results in comparable results of norm using when many coefficients are equal to zero.
A single-pixel detector [15-20] using is very practical CS technology. To provide a set of random masks, a digital micromirror device (DMD) consisting of N tiny mirrors array is used. The radiation from an object is reflected from a set of DMD mirrors and is registered by a single-pixel detector. The number of registrations with the different masks (positions of DMD mirrors) was equal to hundreds or thousands. That number is significantly less than a number of pixels of nowaadays digital cameras. Firstly a single-pixel detector was used in CS for object information acquisition using standard diffraction registration [15-16]. Further it was applied for digital holographic information: registration of phase objects in inline holography [27-28], two-step inline holography , optical scanning holography , and etc.
The implementation scheme for numerical model experiments is showed in Fig. 1. It is one of the possible CS scheme implementation on the basis of a single-pixel detector and DMD.
The beam passes through the object and is reflected from DMD that forms random pattern of zero and unit values. Next the radiation is focused by lens on to the single-pixel detector that measures obtained light intensity. The researcher can do any number of registrations. The obtained vector of the registered signals can be presented as a convolution of signal distribution on an object and on DMD:
(1) where у is a single m registered signal, DMD[•,m] is a m random matrix transformed to 1D array, x[•] is unknown amplitude distribution of object image transformed to 1D array, [•] is 1D array with N pixels, N is quantity of pixels of the DMD and initial object image, [•, •] is 2D matrix with N M pixels, M is quantity of registrations. Values of x[•] can be approximately decomposed in some basis (for example, discrete cosine transform basis).
The DMD[•, •] matrix with DMD arrays for all registrations is computational transformed in frequency representation by means of transform to the matrix DMD [•, •]. As a result there is a set of the low and high frequencies. Next m differences of DMD [•, m] x [•] - y are minimized, where x [•] is initial image that is represented in frequency domain. The object image reconstructed by selecting of obtained x values and inverse transform calculation.
Quality of image was evaluated by means of the normalized standard deviation (NSTD) between initial and reconstructed object images :
where R(n ,n ) is the array of signals of the reconstructed image; O(n ,n ) is the array of signals of the initial image; (n ,n ) are discrete coordinates in the object plane; N N is quantity of pixels of the initial and reconstructed object images. NSTD value shows degree of visual resemblance to initial object image, including similarity in reproduction of halftones. If NSTD value is equal to zero, then images are identical and if to unit (1 or 100 %) - they are completely different. Usually, if NSTD value is less than 0.03 (or 3 %), then from the visual point of view the images seem identical. If NSTD value is more than 0.5 (or 50 %), then images seem different.
Dependencies of NSTD value vs normalized quantity of registrations will be constructed. Quantity of registration will be normalized on number of initial object pixels. Calculation time will be estimated on the computer Intel Core i7-2600 CPU 3.40GHz 16GB RAM Geforce GTX 760 4GB. Dependencies of processing time vs normalized quantity of registrations will be constructed. Quantity of registration will be normalized on number of initial object pixels too.
Reconstruction of binary objects
Numerical experiments on reconstruction of binary objects by using compressed sensing and l2-norm minimization were performed. Examples of initial binary objects are shown in Fig. 2.: “M” letter (Fig. 2a; 142 80 pixels; total 11360 pixels), “Е” letter (Fig. 2b; 70 80 pixels; total 5600 pixels), “Ph” letters (Fig. 2c; 142 80 pixels; total 11360 pixels), “I” letter (Fig. 2d; 50 80 pixels; total 4000 pixels).
The results of image reconstruction are shown in Fig. 3 and Fig. 4. The average number of registrations for each object in Fig. 3 and Fig. 4a-d is equal to 800 that is 10 times less than the average number of pixels in initial objects (about 8000 pixels in each object): 1140 registrations of “M”, 560 registrations of “E”, 1140 registrations of “Ph”, and 390 registrations of “I”. For objects in Fig 4e-h average number of registrations is equal to 565 (7 % of average total pixel quantity for each object): 800 registrations of “M”, 390 registrations of “E”, 800 registrations of “Ph”, and 270 registrations of “I”. For objects in Fig 4j-m the average number of registrations is equal to 242 (3 % of total pixel quantity for each object): 340 registrations of “M”, 170 registrations of “E”, 340 registrations of “Ph”, and 120 registrations of “I”.
Obtained results demonstrated that the quality of the reconstructed images remains acceptable even if losses are more than 90% for the standard l2-norm minimization. Only several percentage of total number of pixels is enough for acceptable recovery of images from visual point of view by the CS. Dependencies of reconstruction quality (NSTD) vs normalized quantity of registrations (in percentage relatively total object pixels quantity) for the CS and l2-norm minimization are shown in Fig. 5-6.
As it can be seen for CS use of 50% registrations relatively total object pixels quantity decreases the error to 0.1 (or 10 %) that corresponds to high reconstruction quality. The l2-norm minimization can give acceptable quality of image reconstruction from the visual point of view. However NSTD value is 5 times higher.
Obtained dependencies of reconstruction time vs normalized quantity of registrations (in percentage relatively total object pixels quantity) for binary objects using compressed sensing is shown in Fig. 7.
As it can be seen direct object reconstruction implementation lasts from several seconds to several minutes for up to 1200 registrations (15 % relatively average total object pixels quantity). The main contributions to the calculation time are processes of image decomposition on basis, calculating coefficients of decomposition and image reconstruction. The core of compressed sensing technique lasts an order of magnitude less time and equal to from the fraction of second to several seconds only.
Reconstruction of non-binary images
Single-pixel registrations and reconstruction of 2D grayscale and color objects by l2-norm minimization and compressed sensing is modeled. Example of the test object is standard grayscale image “Lenna”. The resolution is 128 128 pixels and so it consists of 16384 pixels. The “Lenna” image is shown in Fig. 8.
The results of numerical reconstruction of this object by using the l2-norm minimization and compressed sensing methods are shown in Fig. 9-10. The average number of signal registrations is equal to:
• 1000 that is 16.4 times less than total number of object's pixels (Fig. 9a, 10a),
• 3000 that is 5.5 times less than total number of object's pixels (Fig. 9b, 10b),
• 5000 that is 3.3 times less than total number of pixels (Fig. 9c, 10c),
• 7000 that is 2.3 times less than total number of object's pixels (Fig. 9d, 10d).
The object image reconstructed by the compressed sensing can be visually distinguishable at losses about 90% of pixel's information (Fig. 10a). The l2-norm minimization is significantly worse in compare than compressed sensing as doesn't use various optimization features of the CS. The quality of the reconstructed image is acceptable if losses are 60% of information. The image quality can be increased by growth of number of registrations by a single-pixel detector.
Obtained dependencies of reconstruction quality (NSTD) vs normalized quantity of registrations (in percentage relatively total object pixels quantity) for grayscale object using l2-norm minimization and compressed sensing are shown in Fig. 11.
Average NSTD values are better than that ones for the case of binary objects (see Fig. 5-6) due to a large effect of zero signal pixels to the binary objects NSTDs.
Dependency of reconstruction time vs normalized quantity of registrations (in percentage relatively total object pixels quantity) for grayscale object using compressed sensing is shown in Fig. 12.
As it can be seen direct object reconstruction implementation lasts from several minutes to tens of minutes for up to 10000 registrations (60 % relatively average total object pixels quantity). These values are larger than that ones for the binary object cases because grayscale object is more complicated and more quantity of registrations is needed.
The main contributions to the calculation time are processes of image decomposition on basis, calculating coefficients of decomposition and image reconstruction like in the binary case. The core of compressed sensing technique lasts an order of magnitude less time and equal to from tens of seconds to several minutes only. Acceleration of the processing time can be performed by use of more powerful computers or systems, processors (GPUs, CUDA, DSPs), FPGAs, optimization of program codes, and other similar methods.
The analysis of image reconstruction by the compressed sensing and l2-norm minimization methods by using a single-pixel detector and the digital micromirror device was performed.
Numerical experiments on reconstruction of binary, gray-scale and color objects were conducted. Images with up to 256 256 pixels were used as objects. Quantity of registrations was normalized to number of initial object pixels and ranged from 0.01 % to 70 %.
Obtained results demonstrated that binary objects can be distinguishable using 97 % (in quantity of registrations relatively total object pixels quantity) losses of information content. The reconstructed images of grayscale objects have acceptable visual quality at 80 % losses.
Obtained values of processing time are equal to several seconds for binary objects and several minutes for grayscale images using direct implementation of reconstruction by compressed sensing. These values can be significantly reduced by use of more powerful computers or systems, processors, FPGAs, optimization of program codes, and other similar methods.