# Changeset 2291 for research/2008-displacement/paper/paper.texTweet

Ignore:
Timestamp:
Apr 16, 2008, 12:11:47 AM (15 years ago)
Message:
• More fixes in the paper.
File:
1 edited

### Legend:

Unmodified
 r2290 \begin{abstract} In this contribution we introduce a little-known property of error diffusion halftoning algorithms which we call error diffusion displacement. halftoning algorithms which we call {\it error diffusion displacement}. By accounting for the inherent sub-pixel displacement caused by the error propagation, we correct an important flaw in most metrics used to assess the address the problem of colour reduction. Comparing two algorithms in terms of speed or memory usage is often straightforward, but how exactly a halftoning algorithm performs in terms of quality is a far more complex issue, as it highly depends on the display device and the inner workings of the human eye. algorithm performs quality-wise is a far more complex issue, as it highly depends on the display device and the inner workings of the human eye. Though this document focuses on the particular case of bilevel halftoning, yielding visually pleasing results. Error diffusion dithering, introduced in 1976 by Floyd and Steinberg \medskip Error diffusion dithering, introduced in 1976 by Floyd and Steinberg \cite{fstein}, tries to compensate for the thresholding error through the use of feedback. Typically applied in raster scan order, it uses an error diffusion matrix such as the following one: matrix such as the following one, where $x$ denotes the pixel being processed: \[ \frac{1}{16} \left| \begin{array}{ccc} Though efforts have been made to make error diffusion parallelisable \cite{parfstein}, it is generally considered more computationally expensive than screening. Model-based halftoning is the third important algorithm category. It relies on a model of the human visual system (HVS) and attempts to minimise an error value based on that model. One such algorithm is direct binary seach (DBS) \cite{allebach}, also referred to as least-squares model-based halftoning than screening, but carefully chosen coefficients yield good visual results \cite{kite}. \medskip Model-based halftoning is the third important algorithm category. It relies on a model of the human visual system (HVS) and attempts to minimise an error value based on that model. One such algorithm is direct binary seach (DBS) \cite{allebach}, also referred to as least-squares model-based halftoning (LSMB) \cite{lsmb}. DBS yields halftones of impressive quality. However, despite efforts to make it more efficient \cite{bhatt}, it suffers from its large computational requirements and error diffusion remains a widely used technique. requirements and error diffusion remains a more widely used technique. \section{Error diffusion displacement} bottom-right of each pixel (Fig. \ref{fig:direction}), one may expect the resulting image to be slightly translated. This expectation is confirmed when alternatively viewing an error diffused image and the corresponding DBS halftone. visually when rapidly switching between an error diffused image and the corresponding DBS halftone. \begin{figure} This small translation is visually innocuous but we found that it means a lot in terms of error computation. A common way to compute the error between an image $h_{i,j}$ and the corresponding halftone $b_{i,j}$ is to compute the mean square error between modified versions of the images, in the form: image $h_{i,j}$ and the corresponding binary halftone $b_{i,j}$ is to compute the mean square error between modified versions of the images, in the form: convolution and $v$ is a model for the human visual system. To compensate for the slight translation experienced in the halftone, we use the following error metric instead: To compensate for the slight translation observed in the halftone, we use the following error metric instead: \noindent where $t_{dx,dy}$ is an operator which translates the image along the $(dx,dy)$ vector. $(dx,dy)$ vector. By design, $E_{0,0} = E$. A simple example can be given using a Gaussian HVS model: \end{figure} For instance, a Floyd-Steinberg dither of \textit{Lena}, with $\sigma = 1.2$ yields a per-pixel mean square error of $8.51\times10^{-4}$. However, when taking the displacement into account, the error becomes $7.77\times10^{-4}$ for $(dx,dy) = (0.167709,0.299347)$. The new, corrected error is significantly smaller, with the exact same input and output images. For instance, a Floyd-Steinberg dither of \textit{Lena} with $\sigma = 1.2$ yields a per-pixel mean square error of $3.67\times10^{-4}$. However, when taking the displacement into account, the error becomes $3.06\times10^{-4}$ for $(dx,dy) = (0.165,0.293)$. The new, corrected error is significantly smaller, with the exact same input and output images. Experiments show that the corrected error is always noticeably smaller except vision sets and from the image board \textit{4chan}, providing a representative sampling of the photographs, digital art and business graphics widely exchanged on the Internet. In addition to the classical Floyd-Steinberg and Jarvis, Judice and Ninke kernels, we tested two serpentine error diffusion algorithms: Ostromoukhov's simple error diffusion \cite{ostromoukhov}, which uses a variable coefficient kernel, and Wong and Allebach's optimum error diffusion kernel \cite{wong}. on the Internet nowadays \cite{4chan}. In addition to the classical Floyd-Steinberg and Jarvis-Judice-Ninke kernels, we tested two serpentine error diffusion algorithms: Ostromoukhov's simple error diffusion \cite{ostromoukhov}, which uses a variable coefficient kernel, and Wong and Allebach's optimum error diffusion kernel \cite{wong}. \begin{center} \begin{tabular}{|l|l|l|} \hline & $E$ & $E_{min}$ \\ \hline raster Floyd-Steinberg & 0.00089705 & 0.000346514 \\ \hline raster Ja-Ju-Ni & 0.0020309 & 0.000692003 \\ \hline Ostromoukhov & 0.00189721 & 0.00186343 \\ \hline %    raster optimum kernel & 0.00442951 & 0.00135092 \\ \hline optimum kernel & 0.00146338 & 0.00136522 \\ \begin{tabular}{|l|c|c|} \hline &~ $E\times10^4$ ~&~ $E_{min}\times10^4$ ~\\ \hline ~raster Floyd-Steinberg ~&~ 3.7902 ~&~ 3.1914 ~\\ \hline ~raster Ja-Ju-Ni        ~&~ 9.7013 ~&~ 6.6349 ~\\ \hline ~Ostromoukhov           ~&~ 4.6892 ~&~ 4.4783 ~\\ \hline ~optimum kernel         ~&~ 7.5209 ~&~ 6.5772 ~\\ \hline \end{tabular} visual error measurement than $E(h,b)$. However, its major drawback is that it is highly computationally expensive: for each image, the new $(dx,dy)$ values need to be calculated to minimise the energy value. need to be calculated to minimise the error value. Fortunately, we found that for a given raster or serpentine scan \begin{center} \begin{tabular}{|l|l|l|l|l|} \hline & $E$ & $dx$ & $dy$ & $E_{fast}$ \\ \hline raster Floyd-Steinberg & 0.00089705 & 0.16 & 0.28 & 0.00083502 \\ \hline raster Ja-Ju-Ni & 0.0020309 & 0.26 & 0.76 & 0.00192991 \\ \hline Ostromoukhov & 0.00189721 & 0.00 & 0.19 & 0.00186839 \\ \hline optimum kernel & 0.00146338 & 0.00 & 0.34 & 0.00138165 \\ \begin{tabular}{|l|c|c|c|c|} \hline &~ $E\times10^4$ ~&~ $dx$ ~&~ $dy$ ~&~ $E_{fast}\times10^4$ ~\\ \hline ~raster Floyd-Steinberg ~&~ 3.7902 ~&~ 0.16 ~&~ 0.28 ~&~ 3.3447 ~\\ \hline ~raster Ja-Ju-Ni        ~&~ 9.7013 ~&~ 0.26 ~&~ 0.76 ~&~ 7.5891 ~\\ \hline ~Ostromoukhov           ~&~ 4.6892 ~&~ 0.00 ~&~ 0.19 ~&~ 4.6117 ~\\ \hline ~optimum kernel         ~&~ 7.5209 ~&~ 0.00 ~&~ 0.34 ~&~ 6.8233 ~\\ \hline \end{tabular} diffusion kernels. According to the original authors, the coefficients were found "mostly by trial and error" \cite{fstein}. With our improved metric, we now have the tools to confirm or infirm Floyd and Steinberg's initial proposal. now have the tools to confirm or infirm Floyd and Steinberg's initial choice. We chose to do an exhaustive study of every $\frac{1}{16}\{a,b,c,d\}$ integer combination. We deliberately chose positive integers whose sum is 16. Error combination. We deliberately chose positive integers whose sum was 16: error diffusion coefficients smaller than zero or adding up to more than 1 are known to be unstable \cite{stability}, and diffusing less than 100\% of the error is known to cause important error in shadow and highlight areas of the image. First we studied all possible coefficients on a pool of 250 images with an error metric $E$ based on a standard Gaussian HVS model. Since we are studying algorithms on different images but error values are only meaningful for a given image, we chose a Condorcet voting scheme to determine winners. $E_{min}$ is only given here as an indication and had no role in the computation: to be unstable \cite{stability}, and diffusing less than 100\% of the error causes important loss of detail in the shadow and highlight areas of the image. We studied all possible coefficients on a pool of 3,000 images with an error metric $E$ based on a standard Gaussian HVS model. $E_{min}$ is only given here as an indication and only $E$ was used to elect the best coefficients: \begin{center} \begin{tabular}{|c|c|c|c|} \hline rank & coefficients & $E$ & $E_{min}$ \\ \hline 1 & 8 3 5 0 & 0.00129563 & 0.000309993 \\ \hline 2 & 7 3 6 0 & 0.00131781 & 0.000313941 \\ \hline 3 & 9 3 4 0 & 0.00131115 & 0.000310815 \\ \hline 4 & 9 2 5 0 & 0.00132785 & 0.000322754 \\ \hline 5 & 8 4 4 0 & 0.0013117 & 0.00031749 \\ \hline \dots & \dots & \dots & \dots \\ ~ rank ~&~ coefficients ~&~ $E$ ~&~ $E_{min}$ ~\\ \hline ~ 1 ~&~ 8 3 5 0 ~&~ 0.00129563 ~&~ 0.000309993 ~\\ \hline ~ 2 ~&~ 7 3 6 0 ~&~ 0.00131781 ~&~ 0.000313941 ~\\ \hline ~ 3 ~&~ 9 3 4 0 ~&~ 0.00131115 ~&~ 0.000310815 ~\\ \hline ~ 4 ~&~ 9 2 5 0 ~&~ 0.00132785 ~&~ 0.000322754 ~\\ \hline ~ 5 ~&~ 8 4 4 0 ~&~ 0.00131170 ~&~ 0.000317490 ~\\ \hline ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline \end{tabular} The exact same operation using $E_{min}$ as the decision variable yields very different results. Again, $E$ is only given here as an indication: different results. Similarly, $E$ is only given here as an indication: \begin{center} \begin{tabular}{|c|c|c|c|} \hline rank & coefficients & $E_{min}$ & $E$ \\ \hline 1 & 7 3 5 1 & 0.000306251 & 0.00141414 \\ \hline 2 & 6 3 6 1 & 0.000325488 & 0.00145197 \\ \hline 3 & 8 3 4 1 & 0.000313537 & 0.00141632 \\ \hline 4 & 7 3 4 2 & 0.000336239 & 0.00156376 \\ \hline 5 & 6 4 5 1 & 0.000333702 & 0.00147671 \\ \hline \dots & \dots & \dots & \dots \\ ~ rank ~&~ coefficients ~&~ $E_{min}$ ~&~ $E$ ~\\ \hline ~ 1 ~&~ 7 3 5 1 ~&~ 0.000306251 ~&~ 0.00141414 ~\\ \hline ~ 2 ~&~ 6 3 6 1 ~&~ 0.000325488 ~&~ 0.00145197 ~\\ \hline ~ 3 ~&~ 8 3 4 1 ~&~ 0.000313537 ~&~ 0.00141632 ~\\ \hline ~ 4 ~&~ 7 3 4 2 ~&~ 0.000336239 ~&~ 0.00156376 ~\\ \hline ~ 5 ~&~ 6 4 5 1 ~&~ 0.000333702 ~&~ 0.00147671 ~\\ \hline ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline \end{tabular} \end{center} Our improved metric was able to confirm that the original Floyd-Steinberg coefficients were indeed the best possible for raster scan. Our improved metric allowed us to confirm that the original Floyd-Steinberg coefficients were indeed amongst the best possible for raster scan. More importantly, using $E$ as the decision variable may have elected $\frac{1}{16}\{8,4,4,0\}$, which is in fact a poor choice. For serpentine scan, however, our experiment suggests that the optimum coefficients $\frac{1}{16}\{7,4,5,0\}$ that improve on the standard Floyd-Steinberg coefficients in terms of visual quality for a given HVS model} quality for the HVS model studied in section 3.} \label{fig:lena7450} \end{center} work is only the beginning: future work may cover more complex HVS models, for instance by taking into account the angular dependance of the human eye \cite{sullivan}. And now that we have a proper metric, we plan to improve all error diffusion methods that may require fine-tuning of their propagation coefficients. \cite{sullivan}. We plan to use our new metric to improve all error diffusion methods that may require fine-tuning of their propagation coefficients. % SPIE 3648, 485--494 (1999) \bibitem[6]{quality} \bibitem[6]{kite} T. D. Kite, \textit{Design and Quality Assessment of Forward and Inverse Error-Diffusion \bibitem[7]{halftoning} R. Ulichney, \textit{Digital Halftoning} \textit{Digital Halftoning}. MIT Press, 1987 \bibitem[8]{spacefilling} L. Velho and J. Gomes, \textit{Digital halftoning with space-filling curves} \textit{Digital halftoning with space-filling curves}. Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81--90, 1991 \bibitem[9]{peano} I.~H. Witten and R.~M. Neal, \textit{Using peano curves for bilevel display of continuous-tone images} \textit{Using peano curves for bilevel display of continuous-tone images}. IEEE Computer Graphics \& Appl., 2:47--52, 1982 \bibitem[10]{nasanen} R. Nasanen, \textit{Visibility of halftone dot textures} \textit{Visibility of halftone dot textures}. IEEE Trans. Syst. Man. Cyb., vol. 14, no. 6, pp. 920--924, 1984 \bibitem[11]{allebach} M. Analoui and J.~P. Allebach, \textit{Model-based halftoning using direct binary search} \textit{Model-based halftoning using direct binary search}. Proc. of SPIE/IS\&T Symp. on Electronic Imaging Science and Tech., February 1992, San Jose, CA, pp. 96--108 \bibitem[12]{mcnamara} Ann McNamara, \textit{Visual Perception in Realistic Image Synthesis} \textit{Visual Perception in Realistic Image Synthesis}. Computer Graphics Forum, vol. 20, no. 4, pp. 211--224, 2001 \bibitem[13]{bhatt} Bhatt \textit{et al.}, \textit{Direct Binary Search with Adaptive Search and Swap} \textit{Direct Binary Search with Adaptive Search and Swap}. \url{http://www.ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf} \bibitem[15]{wong} P.~W. Wong and J.~P. Allebach, \textit{Optimum error-diffusion kernel design} \textit{Optimum error-diffusion kernel design}. Proc. SPIE Vol. 3018, p. 236--242, 1997 \bibitem[16]{ostromoukhov} Victor Ostromoukhov, \textit{A Simple and Efficient Error-Diffusion Algorithm} \textit{A Simple and Efficient Error-Diffusion Algorithm}. in Proceedings of SIGGRAPH 2001, in ACM Computer Graphics,  Annual Conference Series, pp. 567--572, 2001 \bibitem[17]{lsmb} T.~N. Pappas and D.~L. Neuhoff, \textit{Least-squares model-baed halftoning} \textit{Least-squares model-based halftoning}. in Proc. SPIE, Human Vision, Visual Proc., and Digital Display III, San Jose, CA, Feb. 1992, vol. 1666, pp. 165--176 \bibitem[18]{stability} R. Eschbach, Z. Fan, K.~T. Knox and G. Marcu, \textit{Threshold Modulation and Stability in Error Diffusion} \textit{Threshold Modulation and Stability in Error Diffusion}. in Signal Processing Magazine, IEEE, July 2003, vol. 20, issue 4, pp. 39--50 \bibitem[19]{kite} T.~D. Kite, \textit{Design and quality assessment of forward and inverse error diffusion halftoning algorithms} Ph.~D. in Electrical Engineering (Image Processing), August 1998 \bibitem[20]{sullivan} \bibitem[19]{sullivan} J. Sullivan, R. Miller and G. Pios, \textit{Image halftoning using a visual model in error diffusion} \textit{Image halftoning using a visual model in error diffusion}. J. Opt. Soc. Am. A, vol. 10, pp. 1714--1724, Aug. 1993