{'fraction_non_alphanumeric': 0.03172321749396848, 'fraction_numerical': 0.015348288075560802, 'mean_word_length': 4.7215859030837, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Iterative Optimization of Quarter Sampling Masks for Non-Regular Sampling Sensors

Non-regular sampling can reduce aliasing at the expense of noise. Recently, it has been shown that non-regular sampling can be carried out using a conventional regular imaging sensor when the surface of its individual pixels is partially covered. This technique is called quarter sampling (also 1/4 sampling), since only one quarter of each pixel is sensitive to light. For this purpose, the choice of a proper sampling mask is crucial to achieve a high reconstruction quality. In the scope of this work, we present an iterative algorithm to improve an arbitrary quarter sampling mask which results in a continuous increase of the reconstruction quality. In terms of the reconstruction algorithms, we test two simple algorithms, namely, linear interpolation and nearest neighbor interpolation, as well as two more sophisticated algorithms, namely, steering kernel regression and frequency selective extrapolation. Besides PSNR gains of +0.31 dB to +0.68 dB relative to a random quarter sampling mask resulting from our optimized mask, visually noticeable enhancements are perceptible.


INTRODUCTION
Non-regular sampling of images can be used to reduce aliasing conventionally occurring from regular sampling [1,2,3]. Additionally, it has been suggested to use non-regular sampling to enhance the spatial resolution of an imaging sensor [4]. This so called quarter sampling (1/4 sampling) can increase the resolution of an image by physically masking three quarters of each pixel of a low resolution sensor. While the same amount of energy, cost and data bandwidth is needed as for the low resolution sensor, the higher resolution is achieved at the expense of an additional post-processing step performing the extrapolation on the high resolution grid which features twice the resolution in both dimensions. Figure 1 depicts the concept behind quarter sampling: Fig. 1(a) shows a high resolution test image taken with a high resolution sensor with twice the resolution of our presumed low resolution sensor. In a simplified model, the low resolution sensor measures a downscaled version of that image by averaging 2×2 pixels at a time. A simulated measurement of the low resolution sensor is shown in Fig. 1(b). Conversely, when quarter sampling is used three quarters of each pixel of the low resolution sensor are covered. Figure 1(c) shows a random quarter sampling mask. Each of these pixels is covered by three quarters (black) and only one quarter of the pixel surface is transparent such that the measurement can be describes as a sub-sampling of the image in Fig. 1(a). The sub-sampled image is depicted in Fig. 1(d). Finally, the missing pixels on the high resolution grid need to be reconstructed yielding an image as in Fig. 1(e). It is important to note that the complete high resolution data is not present in an actual hardware implementation of the sensor because only the data depicted in Fig. 1(d) is measured and used for the reconstruction. Therefore, Fig. 1(b) and Fig. 1(e) have the same number of sampling data points but placing them non-regularly leads to higher image quality.
It turns out that the resulting image quality depends on the chosen quarter sampling mask. For example, a regular quarter sampling mask, which contains the transparent area in the same corner for each low resolution pixel, is disadvantageous since it leads to aliasing again. On the other hand, random quarter sampling masks are expected to be non-optimal since they may contain large covered areas which are in turn harder to reconstruct.
In terms of the reconstruction algorithm we investigate linear interpolation and nearest neighbor interpolation, as well as two more sophisticated algorithms, namely, steering kernel regression (SKR) [5] and frequency selective reconstruction (FSR) [6]. FSR has shown to be a successful reconstruction scheme for various inpainting and extrapolation tasks [7,8,9] and showed best results for non-regular sampling and quarter sampling in [4,6].
This work is organized as follows: Section 2 summarizes existing optimization strategies for quarter sampling masks. In Section 3, we identify properties of a good quarter sampling mask and use these properties to propose an algorithm which iteratively improves the quality of an arbitrary quarter sampling mask. This leads to high quality masks of size 8×8 and 32×32. In Section 4, the reconstruction quality using these masks is evaluated. Therein, visual comparisons are presented as well.

EXISTING MASK OPTIMIZATION STRATEGIES
In order to find an optimal quarter sampling mask, Jonscher et.al. suggest to use a brute force method [10]. They suggest to randomly generate quarter sampling masks of size b×b, b ∈ {2, 4, 8, 16, . . . and repeat them periodically to match the image size on the high resolution grid. The masks are then applied to a set of test images. Afterwards, high resolution images are reconstructed from the subsampled data and the PSNR can be calculated. The mask yielding to the highest average PSNR for a given reconstruction algorithm is chosen for future sampling tasks. Of course, care has to be taken when choosing the test images as these need to be representative.
Unfortunately, there is a serious downside with this approach. For each of the (b/2) 2 low resolution pixels on a quarter sampling masks of size b×b, there are four possible choice to place the transparent pixel. Therefore, the number of possible masks is N b =4 b 2 /4 and thus scales exponentially with the number of pixels. The actual values are N2 = 4, N4 = 256, N8 ≈ 4 × 10 9 , N16 ≈ 3 × 10 38 , ... . For large masks (b ≥ 8), the number of all possible masks makes it computationally infeasible to generate all possible masks and perform the reconstruction on several sub-sampled test images.
Jonscher et.al. incorporate this issue by choosing 256 randomly selected quarter sampling masks for each b ≥ 4. This means, that only a small subset of all possible masks is tested for b ≥ 8. Then, they evaluate all chosen masks on a set of test images and find the mask with the best average PSNR for each b and each investigated reconstruction algorithm. For example, for the FSR their best mask found is of size b = 8. Even though their brute force method theoretically works, it is practically unsatisfactory, because only a small subset of masks is tested for b ≥ 8. Since all masks of size b are included in the set of all masks of size b = 2 · b. the reconstruction quality cannot decrease for larger masks, if all possible masks are taken into account.
To overcome the problems with this brute force method, we propose an optimization strategy in the next section. We circumvent calculating all possible masks and additionally do not need to perform any reconstruction during the mask optimization. It is not our goal to find the one and only best mask for a given reconstruction algorithm but rather to provide a method to find a very good mask based on reasonable heuristic assumptions.

Properties of a good mask
Before being able to optimize a quarter sampling mask, we need to identify properties to distinguish favorable and unfavorable masks.
We claim that two properties are favorable for a good quarter sampling mask: (A) low regularity and (B) uniformity. (A) Regularity leads to high peaks in the spectrum of the masking function. As an immediate consequence, aliasing occurs. This is unfavorable since information about the image is irretrievable lost. In order to  achieve a low regularity, a random quarter sampling mask could be chosen. (B) Uniformity is the second desired property. Within an image, details consisting of very few pixels can be anywhere with the same probability and should be captured independent of their location. This condition implies that the mask should be as uniform as possible. While a regular mask means high uniformity, a random mask means low uniformity. Putting these two properties together, both the random mask and the regular masks are extreme cases complying only with one of the properties.

Proposed optimization strategy
An optimized mask should combine both properties, i.e., it should be both non-regular and uniform. To achieve this, we propose that an arbitrary quarter sampling mask can be improved by reducing the occurrences of the following structures (see also Fig. 2): 2-spx horizontal/vertical pair of transparent pixels forming a superpixel (spx). 4-spx pair of two 2-spx forming a transparent 2×2 superpixel, already mentioned in [10]. 8-void 2×4 or 4×2 block of masked pixels forming a large unknown area. 3-regular three transparent pixels in a horizontal/vertical line, spaced with two masked pixels. 3-diag three neighboring pixels lying on a diagonal. 5-zigzag five pixels in a horizontal/vertical zigzag assembly.
Removing the superpixel structures (2-spx, 4-spx) and the void structure (8-void) results in a more uniform mask, while the removal of the regular structures (3-regular, 3-diag and 5-zigzag) makes the mask less regular.
To produce masks with a reduced number of these structures from an arbitrary quarter sampling mask, we propose an iterative algorithm consisting of four core steps (A-D) to remove the structures. A flow graph illustrating the whole algorithm is depicted in Fig. 3. The steps are exemplarily shown for the removal of a 4-spx and a 8-void structure in Fig. 4 and can be described as follows: (A) First, one randomly selected structure of those depicted in Fig. 2 is selected to be removed. (B) Then, one of the pixels contributing to this structure is randomly selected (marked with an asterisk in Fig. 4). (C) Temporarily, all pixels of its corresponding quarter-block are masked. (D) Finally, a randomly selected pixel of that quarter-block is unmasked, such that the quarter sampling condition is fulfilled. random mask best 8×8 mask 8×8 mask 32×32 mask from [10] no structures no structures 32×32 pixels 8×8 pixels Fig. 5. Different quarter sampling masks (repeated periodically if necessary) cropped to 36×36 pixels. Whereas the random mask features many structures (some marked with blue rounded rectangles) and does not have a uniform appearance, our optimized masks are structure-free and have a uniform appearance while still being non-regular.
The steps (A)-(D) are repeated over and over again. With this algorithm, the structures are removed most of the time while it actually allows to reproduce them. Furthermore, the algorithm potentially creates structures of a different type that were not present before. Nevertheless, the total number of structures is expected to decrease in average. During the search and the removal of the structures periodic boundary conditions have to be taken into account, since masks being smaller than the size of the image are repeated periodically. Now, our goal is to generate a quarter sampling mask without any structures to reach a high quality of uniformity and nonregularity. In terms of the desired size of the quarter sampling masks, we will restrict ourselves to sizes up to b×b = 32×32 high resolution pixels. This simplification can be made because all investigated reconstruction algorithms act locally, i.e., the masked data is reconstructed from its immediate vicinity. However, our algorithm is capable of creating larger masks, if necessary. As a side effect, the periodicity of the masks may allow for a simpler manufacturing process of the actual quarter sampling sensor.
To generate a quarter sampling mask without any structures, a 32×32 random quarter sampling mask is used as initial mask and optimized using the just described algorithm. In the beginning, the number of remaining structures goes down quickly because removing one structure might even remove another structure simultaneously. Conversely, removing the last remaining structures is more difficult, because with every removal new structures may be generated. Later, these new structures need to be removed in addition to the remaining ones. The optimization is stopped, after all structures have been removed. Finally, a 32×32 quarter sampling mask without any structures is found. Similarly, we created a additional quarter sampling mask of size 8×8 without any structures. remove all remove 4-spx remove 2-spx remove 8-void Fig. 6. PSNR (averaged over the first ten TECNICK images using FSR for the reconstruction) as a function of stepwise reduction of different structures. The PSNR increases steadily as more and more structures are removed -as expected. Furthermore, removing all structures within each step leads to the best results. Figure 5 shows a random quarter sampling mask, the best 8×8 mask from [10] and our two just described masks. While the random mask contains all types of structures, the best 8×8 mask from [10] contains only 8-void, 3-diag, 3-regular and 5-zigzag and our 8×8 mask as well as our 32×32 mask contains no structures at all.

Validation of the iterative algorithm
In order to test the performance of our algorithm, we perform an experiment with a random quarter sampling mask and stepwise remove more and more structures. After each step, the PSNR averaged over the first ten TECNICK images [11] using the FSR as an exemplarily reconstruction algorithm is calculated. Figure 6 shows the average PSNR for 26 different masks of size 256×256 where in each step 5-10 % of the structures were randomly selected and removed as explained in Section 3.2. To separate the contributions of the different structures, only the 8-voids, only the 2-spx, only the 4-spx and all structures were removed, respectively. All cases show that the average PSNR increases more than 0.2 dB after 25 steps. When only one of the other structures (3-regular, 3-diag and 5-zigzag) is removed, the PSNR does not increase. This is due to the fact that when removing those regular structures, too many other structures like 8-void, 4-spx and 2-spx are generated. Conversely, when only removing 8-void, 4-spx and 2-spx a high number of 3-regular, 3diag and 5-zigzag structures are generated, which finally leads to a locally regular mask. This is again disadvantageous and limits the maximally achievable reconstruction quality. For this reason, it is most effective and leads to the highest average PSNR in our experiment, when a fraction of all structures is removed in every step.

Reconstruction quality using our structure-free masks
In order to evaluate the quality of our structure-free quarter sampling masks, we compare our masks with the best 8×8 mask using the FSR from [10] and a random mask (all depicted in Fig. 5). For completeness, the results are also provided for a regular mask. We use linear interpolation, nearest neighbor interpolation (both from [12]), steering kernel regression (SKR) [5] and frequency selective reconstruction (FSR) [6] for the reconstruction of the unknown pixels on the high resolution grid. All PSNR values are averaged over all 100 images of the TECNICK image database [11]. Since these images are taken with a regular sensor, we simulate a quarter sampling sensor by sub-sampling the images according to the quarter sampling masks (as in Fig. 1). The reconstructed images can finally be compared with the original image.   Table 1 and Fig. 7 present the PSNR for the four masks depicted in Fig. 5 and a regular mask. For all reconstruction algorithms we tested, the PSNR increases from the random quarter sampling mask via the best 8×8 mask from [10] to our 32×32 mask without structures. The PSNR gains are between +0.31 dB and +0.68 dB. For linear interpolation also the regular mask shows an improvement, whereas in case of the other reconstruction algorithms the regular mask is an unfavorable choice. In case of FSR, this can be explained with the regularity yielding to high contributions in the spectrum of the masked image which finally results in disadvantageous basis functions being selected within the FSR. On the other hand, linear interpolation seems to benefit most from the uniformity of the regular mask compared to other masks. However, for images with high frequency contributions, the regular mask will create severe aliasing and the high resolution data cannot be reconstructed with any of the algorithms as the data is irretrievable lost due to aliasing.
Putting these evaluations together, we can summarize that our approach to find a better quarter sampling mask worked and results in an improvement of +0.31 dB to +0.68 dB compared to the random quarter sampling mask. The highest PSNR is reached using the FSR independent of the chosen mask. For the FSR, using the 8×8 (32×32) mask without structures yielded to an PSNR gain of +0.49 dB (+0.59 dB). To put this into perspective, the best 8×8 mask from [10] resulted in an +0.36 dB increase compared to the random mask using the FSR. It should be highlighted again that the tendency of our achieved quality improvement is independent of the tested reconstruction algorithms.

Visual comparison
In addition to the improvement in the PSNR, we also observe visually noticeable enhancements. Figure 8 shows two image details reconstructed with the FSR using different quarter sampling masks. In both cases, it can be observed that some edges (marked with a small arrow) show severe artifacts with the best 8×8 mask from [10]. These artifacts can be explained by the sampling mask which coincidentally consists of large voids in the region of these edges making the reconstructions less accurate. This also explains why a similar edge occurring multiple times in the exterior wall (bottom row) is sometimes reconstructed poorly and sometimes successfully. Using our 8×8 mask without structures already reduces these artifacts. Using our 32×32 mask without structures, no such artifacts are observed and multiple occurring edges are reconstructed with comparable quality.

CONCLUSION
An iterative algorithm to improve quarter sampling masks was presented within this paper. Our proposal is to remove certain structures such that the quarter sampling mask becomes less regular and more uniform. It has been shown, that when the 8-void, the 2-spx, the 4-spx or all structures are stepwise removed with our approach, the reconstruction quality also increases stepwise. Furthermore, masks of size 8×8 and 32×32 without any of the structures were generated with the proposed algorithm (see Fig. 5). Using these masks improves the reconstruction quality compared to the random mask using any of the tested reconstruction algorithms. The best average PSNR is reached using the FSR together with our structurefree mask of size 32×32. It results in an average PSNR gain of +0.59 dB compared to a random quarter sampling mask and therefore surpasses the best 8×8 mask from [10] by +0.23 dB. We were able to show that our proposal that a uniform and non-regular mask is favorable is independent of the tested reconstruction algorithms. Though higher reconstruction qualities may be achieved with a regular mask when restricting ourselves to linear interpolation, such a mask faces the severe issue that high frequencies are lost completely as a consequence of aliasing. Future work may cover more theoretical approaches in order to find an optimal quarter sampling mask and prove its optimality.

ACKNOWLEDGMENT
The authors gratefully acknowledge that this work has been supported by the Deutsche Forschungsgemeinschaft (DFG) under contract number KA 926/5-3.