Improved halftoning method for autostereoscopic display based on float
grid-division multiplexing

Duo Chen; Xinzhu Sang; Xunbo Yu; Zhidong Chen; Peng Wang; Xin Gao; Nan Guo; Songlin Xie

doi:10.1364/OE.24.018114

1. Introduction

Currently, autostereoscopic products for three-dimensional displaying are familiar to most people. Compared with LCD-based display [1–5], the printing products is able to present higher resolution and provide more three dimensional contents. In general, parallax contents are synthesized as a single image and can be seen from different views with a lenticular lens array [1, 2]. As to printing, halftoning is required. Halftoning is a process that reproduce grayscale images with black-and-white dots which looks like continuous-tone when viewed at a distance [6]. Commonly, there are three categories of halftoning, including point (e.g. ordered dithering), neighborhood (e.g. error diffusion) and iterative processes (e.g. direct binary search) [7]. A square grid is always used to present a gray scale pixel and the number of binary dots inside determines its gray-level. For example, a grid of $5 \times 5$ dots can demonstrate 26 levels [8].

An autostereoscopic printing product comprises of two parts, a lenticular lens array and a high-resolution halftoned printing image. The lines per inch ( $L P I$ ) of array and dots per inch ( $D P I$ ) of print determine the final result, including view-numbers, resolution and gray-levels. In the past, primitive 3D products employing low LPI ( $< 30 L P I$ ) array and low DPI ( $< 30 D P I$ ) do not achieve satisfactory results. Amplitude Modulation (AM) screening for halftoning with high DPI ( $\geq 2400 D P I$ ) was introduced in [9,10]. Considering the imaging proceeding characteristic of the lenticular lens array, a deformation grid is used as dithering matrix containing $1 \times n$ dots arrayed in vertical, as shown in Fig. 1(a). After equipping the material with lenticular lens, printed dots can be seen in different views, as shown in Fig. 1(b). By controlling the vertical dot density to represent gray-scales, this method provides much more view-numbers than before. However, if an arbitrary lenticular lens array is used, which does not match with integer grids, the display performance is deteriorated and serious dislocations appear as shown in Fig. 1(c).

Fig. 1 (a) A gray pixel is represented by an integer grid of binary dots. (b) The imaging process with different view-points. (c) The method of integer grids causes dislocation with the lenticular lens array.

Download Full Size | PDF

According to the method in Ref [9], view-numbers and gray-levels are given by following expressions,

{\begin{matrix} N_{v i e w} = \frac{D P I}{L P I} \\ L_{g r a y} = \frac{D P I}{L P I} + 1 \end{matrix}

where

L P I

and

D P I

are properties of lenticular lens array and printer. View-number is the result of

D P I

divided by

L P I

. Gray-level is 1 greater than view-number. From Eq. (1), we can see that parameters must be carefully design to maintain an integer in computation, which causes two problems. Firstly, the design of lenticular lens array must be customized, because if

(D P I - N_{v i e w} \times L P I) \neq 0

, there would be obvious dislocations between lenticular lens array and grids. Secondly, the number of view-points and gray-levels cannot be set arbitrarily.

Here, an improved printing method for autostereoscopic display based on float grid-division multiplexing (fGDM) is presented. Compared with the integer grid, the float grid contains partial dots to express a pixel. With fGDM, dislocation errors can be solved, and more view-numbers and gray-levels can be displayed. Simultaneous algebraic reconstruction technique (SART) is used to optimize dot distribution and executed on GPU. Simulations and experimental results show that the fGDM is very effective for three-dimensional display and an improved performance is achieved.

2. The printing method based on fGDM

2.1 Float grid-division multiplexing

The synthesized image of continuous parallax views for autostereoscopic displaying is halftoned by the method based on float grid-division multiplexing (fGDM). The gray-level of all view contents are firstly reduced through the error diffusion [8]. Different view-points are synthesized as an image. Each gray pixel in the synthesized image is expressed by a float grid of $n_{x s} \times n_{y}$ dots, as shown in Fig. 2(a). Different view pixels are printed on float grids by $n_{x t}$ apart from each other, as shown in Fig. 2(b) and 2(c). From Fig. 2(d), we can see that after fGDM is used and $n_{x t}$ is adjusted precisely, printed float grids can be kept alignment with lenticular lens, even if $L P I$ and $D P I$ are not matching. $n_{x t}$ and $n_{x s}$ are given as following expressions,

{\begin{matrix} n_{x t} = \frac{D P I}{N_{v ​ i ​ e ​ w} \times L P I} \\ n_{x s} = \frac{L_{g r a ​ y} - 1}{n_{y}} \end{matrix}

where

n_{x s}

is the number of horizontal partial binary dots of float grid, and

n_{y}

is the number of vertical dots, and

n_{x t}

is the number of dots between left edge of two adjacent float grids.

Fig. 2 (a) A gray pixel is represented by a float grid of partial binary dots. (b) The method of float grids keeps alignment with lenticular lens. (c) Views are printed on float grids. (d) All view-points are printed on float grids and kept alignment with the lenticular lens array.

Download Full Size | PDF

Based on the theory of fGDM, view-numbers and gray-levels are given as following expressions,

{\begin{matrix} N_{v i e w} = i n t (\frac{D P I}{n_{x t} \times L P I}) \\ L_{g r a y} = i n t (n_{x s} \times n_{y}) + 1 \end{matrix}

It can be seen that

N_{v i e w}

or

L_{g r a y}

can be separately calculated. As a result, fGDM will not be constrained by physical conditions, and we can improve view-numbers and gray-levels respectively while keeping the alignment between lens and grids. Note that, if we set

n_{x s} \geq n_{x t}

, view n and view 1 should be truncated, in order to avoid adjacent view-zones stride into the others. The truncation principle is based on the percentage of border dot occupied.

2.2 Optimization algorithm of halftoning with SART

Conventionally, all view-points images are halftoned into black or white dots by a single pixel-threshold matrix as Ref [9]. Under fGDM, a dot is multiplexed by two float grids or more, so some optimization algorithms of halftoning are applied.

To address the multiplexing problem, the parameterization of fGDM is illustrated in Fig. 3. The synthesized gray pixel image is parameterized as a column vector $A_{M \times 1}$ with M elements, and the simulated gray image is parameterized as a vector ${\tilde{A}}_{M \times 1}$ . The final binary halftoned image is represented as a column vector $X_{N \times 1}$ with N elements. $W_{M \times N}$ represents a weight matrix mapping dots to pixels with M rows and $N$ columns. The element of $W_{M \times N}$ is $w_{m n}$ which ranges from 0 to 1, mapping dot n to pixel m. $w_{m N}$ is the row float vector of $W_{M \times N}$ at row m, mapping $N$ dots to pixel m. And $w_{M n}$ is the column float vector of $W_{M \times N}$ at column n, mapping dot n to M pixels.

Fig. 3 The parameterization of the synthesized image, the simulated image, the halftoned image and the weight matrix.

Download Full Size | PDF

Each element of ${\tilde{A}}_{M \times 1}$ is the sum of white grid dots ( $x_{n} = 1$ ), which is given as,

{\tilde{A}}_{m} = \sum_{i \in (n_{x s} \times n_{y})} w_{i} x_{i} = \sum_{n = 1}^{N} w_{m n} x_{n}

where

{\tilde{A}}_{m}

is the pixel m of

{\tilde{A}}_{M \times 1}

,

x_{n}

is the binary dot of

X_{N \times 1}

. The squares cost function is defined as

f_{m}

expressing the difference between

A_{m}

and

{\tilde{A}}_{m}

, as shown in Fig. 4(a), and it is given by the following expression,

f_{m} = {‖ A_{m} - {\tilde{A}}_{m} ‖}_{2} = {‖ A_{m} - w_{m N} x_{n} ‖}_{2}

It is considered that when the sum of all related

f_{m}

is the least,

x_{n}

is the output binary dot, which can be formulated as the following least squares problem, as illustrated in Fig. 4(b).

f_{m}

can be written on vector form

F_{M \times 1}

.

x_{n} = a r g m i n (\sum_{M} e_{m n} f_{m} (x_{n}))

X = a r g m i n (e_{M n}^{T} F_{M \times 1} (X))

where

e_{M n}

is a column flag vector of

w_{m n}

(if

w_{m n} > 0

,

e_{m n} = 1

).

Fig. 4 (a) The example of the computation of $f_{m}$ , where $w_{m n}$ is the row float vector of $W_{M \times N}$ at row m, mapping N dots to pixel m. (b) The example of the computation of $x_{n}$ , where $w_{M n}$ and $e_{M n}$ are the column float vectors mapping dot n to M pixels.

Download Full Size | PDF

We note that this least squares formula is similar to that mentioned in Ref [11] and it can be efficiently solved with SART. So for each dot $x_{n}$ , it provides an iterative rule and at t times it has the following forms,

x_{n}^{'} = \frac{e_{M n}^{T} (A_{M \times 1} - (W_{M \times N} X_{N \times 1}))}{w_{M n}^{T} e_{M n}}

x_{n} = {\begin{matrix} 0 (x_{n}^{'} > 0) \\ d o n o t h i n g (x_{n}^{'} = 0) \\ 1 (x_{n}^{'} < 0) \end{matrix}

SART has provided a rapid convergence to optimize the halftone image within about 20 iterative processes.

2.3 Random solving sequence

The optimization process with the threshold formula as Eqs. (7) and (8) for fGDM, is operated upon all float grids on GPU in parallel, but updates each child dots inside in sequence. The sequence equivalent to the halftoning matrix is crucial to the dot distribution and hence affects the performance of the halftone image, because non-uniform order can cause image brightness changes. In Ref [9], the author uses three different screen methods to reproduce gray-scales. However, these methods have not taken the similarity of horizontal pixels into consideration, and black dots would be aggregated as lines in halftoning. In this case, vertical and horizontal distributions are very regular and not uniform, as shown in Fig. 5(a), and these will cause severe moire sometimes. In practice, we use a random solving sequence instead of any scale patterns to avoid such non-uniform gathering. And to ensure uniform, the random sequence is renewed in every iteration. The halftone image generated by the method of random solving sequence is shown in Fig. 5(b). In fGDM, the sequence here is just a solving order rather than a filling order. Only in integer grids and when $n_{x s} = n_{x t}$ , the distribution of halftone image is fulfilled by the random sequence.

Fig. 5 (a) The horizontal black dots are aggregated as lines in the halftone image. (b) The method of random solving sequence generates uniform dot distribution in the halftone image.

Download Full Size | PDF

3. Implementation and assessment

3.1 Algorithm programming

During programming, the optimization algorithm of Eqs. (7) and (8) is implemented on GPU, of which the configuration is CUDA v7.5 and NVIDIA GTX970. As mentioned above, dots are picked randomly from all float grids, and optimized in parallel. So each iteration needs about $n_{x s} \times n_{y}$ times parallelizing updates. In practice, because the CUDA register cannot support such large image data, the image is split into parts and composed in a single BMP file. For 20 times iteration, a relative good result is received and the GPU-based code only needs about $38 s$ . To ensure the precision of float computation, $n_{x s}$ and $n_{x t}$ are up to 4 decimal places in program.

3.2 Simulation estimation

To verify the effectiveness of fGDM for alignment, three image groups are used for testing, as shown in Fig. 6. The lenticular lens array is arbitrary and has a pitch of $200.1 L P I$ . The halftone images based on fGDM are printed on films with $3600 D P I$ by a laser typesetter that is able to generate such dense dots stably. Each multiview-points image is printed in about $2.7 inches$ . In contrast, all images are also generated by AM screening method, which is the conventional method as Eq. (1). For the random screening method, $n_{x s} = n_{x t} = i n t e g e r$ . It should be noted that methods of AM and Random uses integral grids, and the simulation results are almost the same. The only difference between them is the printing dot distribution. The detail configuration is shown as Table 1. The average peak signal-to-noise ratio (PSNR) of simulated three dimensional results are calculated for estimation. The residual image is also obtained, which describes the absolute error between the original image and the simulation image.

Fig. 6 Three image groups. (a) is the image of “badge”. (b) is the image of “horse”. (c) is the image of “plane”.

Download Full Size | PDF

Table 1. The configuration of each halftoning method.

View Table

Based on the algorithm, it can be seen that the width of float grids is $9715$ , dots and the one of integer grids is 9720. These five dots can avoid the dislocation effectively and keep the alignment between lenticular lens array and printed grids. In simulation, the original synthesized image is halftoned with AM screening, Random screening and fGDM. After that, these halftoned images are resampled to simulate the lens imaging and simulated images are generated. The resampling step for dot is $D P I / (L P I * N_{v i e w})$ . The simulation result shows an image set of all simulated view-points, and the residual image can demonstrate the overall difference between the original synthesized image and the simulated ones. It should be noted that, the simulation of AM and Random are the same. Figure 7 shows three groups of simulated images and residual images. In the middle column of Fig. 7, we can see that contents of AM and Random simulations are similar to the original, but two pixels dislocation occurs when it is over 4000 in the X direction. In the right column, residues of AM and Random are severe and the image right side are more grievous than the left side. The reason for this is that when $L P I$ and $D P I$ are not matching, the conventional printed grids cannot be kept alignment with the array, and dislocation errors are accumulated. For the simulation of fGDM, by precisely adjusting $n_{x t}$ in printed float grids, the dislocation can be eliminated clearly and contents are kept alignment with the array. Errors in residual are greatly decreased and PSNR is improved from 18dB to around 50dB. In summary, fGDM can effectively address the dislocation problem in autostereoscopic printing.

Fig. 7 Simulated and residual images generated by AM screening, random screening and fGDM. (a) The simulation and residues of “badge”. (b) The simulation and residues of “horse”. (c) The simulation and residues of “plane”.

Download Full Size | PDF

For the autostereoscopic display, the number of view-points determines the smoothness of three-dimensional scene. Based on the method of fGDM, it is not limited to the printing scale and is able to be increased arbitrarily. We employ PSNR to qualify the final halftoning results of “badge” under different view-numbers and different gray-levels. In this scene, the parameter of $n_{y}$ is kept as 18 dots, and $n_{x s}$ is adjusted so that the gray-level ranges from 20 to 48, and $n_{x t}$ is computed so that view-numbers varies from 7 to 16. The map of PSNR is shown in Fig. 8. One white line staying at about 45dB, identifies the boundary line above which is the area of $n_{x t} \leq n_{x s}$ . The other white line stays at 30dB. We can see that PSNR is inverse proportion to view-numbers or gray-scales. With more view-numbers or gray-scales multiplexed, image quality descends all along. When $N_{v i e w} = 16$ and $L_{g r a y} = 48$ , the value is decreased to the lowest value 23dB, which is attributed to the large amount of content to be multiplexed between float grids. Such grids are hardly to carry too much dissimilarity and it results in image quality decreasing. Generally, there should be a balance between scene smoothness and 3D image quality. Considering the assessment of image quality, the balance should be above 30dB, which can provide an image with low distortion. Increasing gray-levels can cause similar effects, and it will not be discussed here.

Fig. 8 PSNR of halftoning images when view-number ranges from 7 to 16 and gray-levels are set from 20 to 48. The white line identifies the area of $n_{x t} \leq n_{x s}$ . The other white line identifies 30dB.

Download Full Size | PDF

3.3 Experimental assessment

In experiments, the configuration of each halftoning method is the same with simulations, where _LPI of the lenticular lens array is _200.1 and _DPI of the halftoned image is.3600 These halftoned contents are printed on films by a laser typesetter. When the lenticular lens array is placed on the film, autostereoscopic views can be displayed. Photographs are taken at 1 meter away in a particular direction to capture a single view. Related results of and simulation is shown in Fig. 9. In Fig. 9(a), it shows the simulation images of AM and Random screening, which are the same because the integer grid configurations are the same. Figure 9(d) is the simulation of fGDM. Figures 9(b), 9(c) and 9(e) shows experimental photos for three groups of films. It can be seen that the ghost and crosstalk are very obviously in Figs. 9(a)-9(c). They have shown a very low image quality and PSNR is no more than 24dB. The crosstalk from other view-points is caused by the dislocation between lens array and printed grids. For Figs. 9(d) and 9(e) with the method of fGDM, the quality of simulated and experimental images is greatly improved, which is attributed to the alignment between lenticular lens array and printed grids. Ghosts of “badge”, “leaves” and “plane head” are effectively eliminated. With fGDM, PSNR of simulated images is improved to 50dB.

Fig. 9 Images of a single view generated by different methods. (a) Simulation image generated by AM screening and Random screening. (b) Photos of AM screening. (c) Photos of random screening. (d) The simulation image generated by fGDM. (e) Photos of fGDM. The magenta rectangle is the detail part of images above.

Download Full Size | PDF

Figure 10 shows photographs under different view-points at 36 gray levels. It can be seen that with the view-points number increasing, the smoothness between different viewpoints is improved. As to the photo of AM screening and Random screening with 9 view-points, there are obvious jumps when switching adjacent view-points. After applied fGDM and enhanced view-points to 12, jumps are eased and switching views becomes very smooth. With more view-points, continuous parallax contents can be displayed vividly and effectively. However, as the simulation illustrated in Fig. 8 and experiment in Fig. 11, the number of view-point increasing is not unlimited. From Fig. 11, we can see that increasing the number of view-points or the gray-level can lead to decreasing the image quality. And too many multiplexed contents could result in vision blurred. So the smooth switching and the vision quality should be balanced for the autostereoscopic printing. When increasing the view-point or gray-level, the vision quality should be at least beyond 30dB.

Fig. 10 Photographs under different view-points at 36 gray levels. (a) The photo based on AM screening under 9 view-points. (b) The photo based on random screening under 9 view-points. (c) The photo based on fGDM under 12 view-points (see Visualization 1).

Download Full Size | PDF

Fig. 11 Photographs of fGDM under different view-points at different gray-levels.

Download Full Size | PDF

4. Conclusion

In summary, an improved halftoning method for autostereoscopic printing based on fGDM is demonstrated. There are several advantages of fGDM. Firstly, it can use any $LPI$ lenticular lens array and keep the alignment between grids and lenticular lens array. Secondly, it can improve view-number and gray-level by multiplexing grids, which make full use of such high $DPI$ dots. Simulation and experimental results show that fGDM is a very effective method for autostereoscopic display, and an improved performance of three-dimensional display is achieved.

Funding

National Natural Science Foundation of China (NSFC) (61575025); the fund of the State Key Laboratory of Information Photonics and Optical Communications.

References and links

1. X. Yu, X. Sang, S. Xing, T. Zhao, D. Chen, Y. Cai, B. Yan, K. Wang, J. Yuan, C. Yu, and W. Dou, “Natural three-dimensional display with smooth motion parallax using active partially pixelated masks,” Opt. Commun. 313(4), 146–151 (2014). [CrossRef]

2. X. Yu, X. Sang, X. Gao, Z. Chen, D. Chen, W. Duan, B. Yan, C. Yu, and D. Xu, “Large viewing angle three-dimensional display with smooth motion parallax and accurate depth cues,” Opt. Express 23(20), 25950–25958 (2015). [CrossRef] [PubMed]

3. X. Gao, X. Sang, X. Yu, P. Wang, X. Cao, L. Sun, B. Yan, J. Yuan, K. Wang, C. Yu, and W. Dou, “Aberration analyses for improving the frontal projection three-dimensional display,” Opt. Express 22(19), 23496–23511 (2014). [CrossRef] [PubMed]

4. P. Wang, S. Xie, X. Sang, D. Chen, C. Li, X. Gao, X. Yu, C. Yu, B. Yan, W. Dou, and L. Xiao, “A large depth of field frontal multi-projection three-dimensional display with uniform light field distribution,” Opt. Commun. 354, 321–329 (2015). [CrossRef]

5. S. Xie, P. Wang, X. Sang, and C. Li, “Augmented reality three-dimensional display with light field fusion,” Opt. Express 24(11), 11483–11494 (2016). [CrossRef] [PubMed]

6. R. A. Ulichney, Digital Halftoning (MIT Press, 1987).

7. D. L. Lau and G. R. Arce, Modern Digital Halftoning (CRC Press, 2001).

8. R. L. Adler, B. P. Kitchens, M. Martens, C. P. Tresser, and C. W. Wu, “The mathematics of halftoning,” IBM J. Res. Develop. 47(1), 5–15 (2003). [CrossRef]

9. S. Sakamoto and Y. Takaki, “Three-dimensional print using a one-dimensional screen technique,” Jpn. J. Appl. Phys. 47(7), 5486–5492 (2008). [CrossRef]

10. H. Yamazaki and Y. Takaki, “Printing 3D Light Field with 1D Halftone Screening,” SIGGRAPH (2012).

11. D. Lanman, G. Wetzstein, M. Hirsch, W. Heidrich, and R. Raskar, “Polarization fields: dynamic light field display using multi-layer LCDs,” Acm Trans. Graphic 30(6), 61–64 (2011). [CrossRef]

Improved halftoning method for autostereoscopic display based on float grid-division multiplexing

Abstract

1. Introduction

2. The printing method based on fGDM

2.1 Float grid-division multiplexing

2.2 Optimization algorithm of halftoning with SART

2.3 Random solving sequence

3. Implementation and assessment

3.1 Algorithm programming

3.2 Simulation estimation

3.3 Experimental assessment

4. Conclusion

Funding

References and links

Supplementary Material (1)

Cited By

Figures (11)

Tables (1)

Equations (9)

Optics Express

Value	AM screening	Random screening	fGDM
$L P I$	200.1	200.1	200.1
$D P I$	3600	3600	3600
$N_{v i e w}$	9	9	9
$L_{g r a y}$	36	36	36
$n_{x s}$	2	2	2
$n_{x t}$	-	2	1.9990°
$n_{y}$	18	18	18
Width(dots)	9720	9720	9715