source: research/2008-displacement/paper/paper.tex @ 2291

Last change on this file since 2291 was 2291, checked in by Sam Hocevar, 13 years ago
  • More fixes in the paper.
File size: 18.9 KB
Line 
1% This is LLNCS.DEM the demonstration file of
2% the LaTeX macro package from Springer-Verlag
3% for Lecture Notes in Computer Science,
4% version 2.2 for LaTeX2e
5%
6\documentclass{llncs}
7%
8\usepackage{makeidx}  % allows for indexgeneration
9\usepackage{graphicx} % for gnuplot epslatex stuff
10\usepackage{color}    % ditto
11\usepackage{pstricks} % for inkscape TeX output
12%
13\begin{document}
14%
15\mainmatter              % start of the contributions
16%
17\title{Reinstating Floyd-Steinberg: Improved Metrics for Quality Assessment
18of Error Diffusion Algorithms}
19%
20\titlerunning{Adapting Qualitative Metrics to Common Error Diffusion Algorithms}  % abbreviated title (for running head)
21%                                     also used for the TOC unless
22%                                     \toctitle is used
23%
24\author{Sam Hocevar\inst{1} \and Gary Niger\inst{2}}
25%
26\authorrunning{Sam Hocevar et al.} % abbreviated author list (for running head)
27%
28%%%% modified list of authors for the TOC (add the affiliations)
29\tocauthor{Sam Hocevar, Gary Niger (Laboratoire d'Imagerie Bureautique et de
30Conception Artistique)}
31%
32\institute{Laboratoire d'Imagerie Bureautique et de Conception Artistique\\
3314 rue de Plaisance, Paris, France
34\and
35143 Rolloffle Avenue, Tarzana, California 91356\\
36\email{sam@hocevar.net}, \email{gary\_niger@gnaa.us}}
37
38\maketitle              % typeset the title of the contribution
39
40\begin{abstract}
41In this contribution we introduce a little-known property of error diffusion
42halftoning algorithms which we call {\it error diffusion displacement}.
43By accounting for the inherent sub-pixel displacement caused by the error
44propagation, we correct an important flaw in most metrics used to assess the
45quality of resulting halftones. We find these metrics to usually highly
46underestimate the quality of error diffusion in comparison to more modern
47algorithms such as direct binary search.
48Using empirical observation, we give a method for creating computationally
49efficient, image-independent, model-based metrics for this quality assessment.
50Finally, we use the properties of error diffusion displacement to justify
51Floyd and Steinberg's well-known choice of algorithm coefficients.
52
53{\bf Keywords}: halftoning, error diffusion, image quality, human visual
54system, color quantization
55\end{abstract}
56%
57\section{Introduction}
58
59Image dithering is the process of reducing continuous-tone images to images
60with a limited number of available colours. Applications vary tremendously,
61from laser and ink-jet printing to display on small devices such as cellphones,
62or even the design of banknotes.
63
64Countless methods have been published for the last 40 years that try to best
65address the problem of colour reduction. Comparing two algorithms in terms of
66speed or memory usage is often straightforward, but how exactly a halftoning
67algorithm performs quality-wise is a far more complex issue, as it highly
68depends on the display device and the inner workings of the human eye.
69
70Though this document focuses on the particular case of bilevel halftoning,
71most of our results can be directly adapted to the more generic problem of
72colour reduction.
73
74\section{Halftoning algorithms}
75
76The most ancient halftoning method is probably classical screening. This highly
77parallelisible algorithm consists in tiling a dither matrix over the image
78and using its elements as threshold values. Classical screening is known for
79its structural artifacts such as the cross-hatch patterns caused by Bayer
80ordered dither matrices \cite{bayer}. However, modern techniques such as the
81void-and-cluster method \cite{void1}, \cite{void2} allow to generate screens
82yielding visually pleasing results.
83
84\medskip Error diffusion dithering, introduced in 1976 by Floyd and Steinberg
85\cite{fstein}, tries to compensate for the thresholding error through the use
86of feedback. Typically applied in raster scan order, it uses an error diffusion
87matrix such as the following one, where $x$ denotes the pixel being processed:
88
89\[ \frac{1}{16} \left| \begin{array}{ccc}
90- & x & 7 \\
913 & 5 & 1 \end{array} \right| \]
92
93Though efforts have been made to make error diffusion parallelisable
94\cite{parfstein}, it is generally considered more computationally expensive
95than screening, but carefully chosen coefficients yield good visual results
96\cite{kite}.
97
98\medskip Model-based halftoning is the third important algorithm category. It
99relies on a model of the human visual system (HVS) and attempts to minimise
100an error value based on that model. One such algorithm is direct binary seach
101(DBS) \cite{allebach}, also referred to as least-squares model-based halftoning
102(LSMB) \cite{lsmb}.
103
104HVS models are usually low-pass filters. Nasanen \cite{nasanen}, Analoui
105and Allebach \cite{allebach} found that using Gaussian models gave visually
106pleasing results, an observation confirmed by independent visual perception
107studies \cite{mcnamara}.
108
109DBS yields halftones of impressive quality. However, despite efforts to make
110it more efficient \cite{bhatt}, it suffers from its large computational
111requirements and error diffusion remains a more widely used technique.
112
113\section{Error diffusion displacement}
114
115Most error diffusion implementations parse the image in raster scan order.
116Boustrophedonic (serpentine) scanning has been shown to cause fewer visual
117artifacts \cite{halftoning}, but other, more complex processing paths such as
118Hilbert curves \cite{spacefilling}, \cite{peano} are seldom used as they do not
119improve the image quality significantly.
120
121Intuitively, as the error is always propagated to the bottom-left or
122bottom-right of each pixel (Fig. \ref{fig:direction}), one may expect the
123resulting image to be slightly translated. This expectation is confirmed
124visually when rapidly switching between an error diffused image and the
125corresponding DBS halftone.
126
127\begin{figure}
128  \begin{center}
129    \input{direction}
130    \caption{Floyd-Steinberg error diffusion direction in raster scan (left)
131             and serpentine scan (right).}\label{fig:direction}
132  \end{center}
133\end{figure}
134
135This small translation is visually innocuous but we found that it means a lot
136in terms of error computation. A common way to compute the error between an
137image $h_{i,j}$ and the corresponding binary halftone $b_{i,j}$ is to compute
138the mean square error between modified versions of the images, in the form:
139
140\begin{equation}
141  E(h,b) = \frac{(||v * h_{i,j} - v * b_{i,j}||_2)^2}{wh}
142\end{equation}
143
144\noindent where $w$ and $h$ are the image dimensions, $*$ denotes the
145convolution and $v$ is a model for the human visual system.
146
147To compensate for the slight translation observed in the halftone, we use the
148following error metric instead:
149
150\begin{equation}
151  E_{dx,dy}(h,b) = \frac{(||v * h_{i,j} - v * t_{dx,dy} * b_{i,j}||_2)^2}{wh}
152\end{equation}
153
154\noindent where $t_{dx,dy}$ is an operator which translates the image along the
155$(dx,dy)$ vector. By design, $E_{0,0} = E$.
156
157A simple example can be given using a Gaussian HVS model:
158
159\begin{equation}
160  v(x,y) = e^{\frac{x^2+y^2}{2\sigma^2}}
161\end{equation}
162
163Finding the second filter is then straightforward:
164
165\begin{equation}
166  (v * t_{dx,dy})(x,y) = e^{\frac{(x-dx)^2+(y-dy)^2}{2\sigma^2}}
167\end{equation}
168
169Experiments show that for a given image and a given corresponding halftone,
170$E_{dx,dy}$ has a local minimum almost always away from $(dx,dy) = (0,0)$ (Fig.
171\ref{fig:lena-min}). Let $E$ be an error metric where this remains true. We
172call the local minimum $E_{min}$:
173
174\begin{equation}
175  E_{min}(h,b) = \min_{dx,dy}E_{dx,dy}(h,b)
176\end{equation}
177
178\begin{figure}
179  \begin{center}
180   \input{lena-min}
181   \caption{Mean square error for the \textit{Lena} image. $v$ is a simple
182            $11\times11$ Gaussian convolution kernel with $\sigma = 1.2$ and
183            $(dx,dy)$ vary in $[-1,1]\times[-1,1]$.}
184   \label{fig:lena-min}
185  \end{center}
186\end{figure}
187
188For instance, a Floyd-Steinberg dither of \textit{Lena} with $\sigma = 1.2$
189yields a per-pixel mean square error of $3.67\times10^{-4}$. However, when
190taking the displacement into account, the error becomes $3.06\times10^{-4}$ for
191$(dx,dy) = (0.165,0.293)$. The new, corrected error is significantly smaller,
192with the exact same input and output images.
193
194Experiments show that the corrected error is always noticeably smaller except
195in the case of images that are already mostly pure black and white. The
196experiment was performed on a database of 10,000 images from common computer
197vision sets and from the image board \textit{4chan}, providing a representative
198sampling of the photographs, digital art and business graphics widely exchanged
199on the Internet nowadays \cite{4chan}.
200
201In addition to the classical Floyd-Steinberg and Jarvis-Judice-Ninke kernels,
202we tested two serpentine error diffusion algorithms: Ostromoukhov's simple
203error diffusion \cite{ostromoukhov}, which uses a variable coefficient kernel,
204and Wong and Allebach's optimum error diffusion kernel \cite{wong}.
205
206\begin{center}
207  \begin{tabular}{|l|c|c|}
208  \hline
209  &~ $E\times10^4$ ~&~ $E_{min}\times10^4$ ~\\ \hline
210  ~raster Floyd-Steinberg ~&~ 3.7902 ~&~ 3.1914 ~\\ \hline
211  ~raster Ja-Ju-Ni        ~&~ 9.7013 ~&~ 6.6349 ~\\ \hline
212  ~Ostromoukhov           ~&~ 4.6892 ~&~ 4.4783 ~\\ \hline
213  ~optimum kernel         ~&~ 7.5209 ~&~ 6.5772 ~\\
214  \hline
215  \end{tabular}
216\end{center}
217
218We clearly see that usual metrics underestimate the quality of error-diffused
219halftones, especially in raster scan. Algorithms such as direct binary search,
220on the other hand, do not suffer from this bias since they are designed to
221minimise the very error induced by the HVS model.
222
223\section{An image-independent corrected quality metric for error-diffused
224halftones}
225
226We have seen that for a given image, $E_{min}(h,b)$ is a better and fairer
227visual error measurement than $E(h,b)$. However, its major drawback is that it
228is highly computationally expensive: for each image, the new $(dx,dy)$ values
229need to be calculated to minimise the error value.
230
231Fortunately, we found that for a given raster or serpentine scan
232error diffusion algorithm, there was often very little variation in
233the optimal $(dx,dy)$ values (Fig. \ref{fig:table-historaster} and
234\ref{fig:table-histoserp}).
235
236\begin{figure}
237  \begin{center}
238    \begin{minipage}[c]{0.50\textwidth}
239      \input{fs-histo}
240    \end{minipage}
241    \begin{minipage}[c]{0.40\textwidth}
242      \input{jajuni-histo}
243    \end{minipage}
244    \caption{error diffusion displacement histograms for the raster
245             Floyd-Steinberg (left) and raster Jarvis, Judis and Ninke (right)
246             algorithms applied to a corpus of 10,000 images}
247    \label{fig:table-historaster}
248  \end{center}
249\end{figure}
250
251\begin{figure}
252  \begin{center}
253    \begin{minipage}[c]{0.50\textwidth}
254      \input{ostro-histo}
255    \end{minipage}
256    \begin{minipage}[c]{0.40\textwidth}
257      \input{serpopt-histo}
258    \end{minipage}
259    \caption{error diffusion displacement histograms for the Ostromoukhov                    (left) and optimum kernel (right) algorithms applied to a corpus
260             of 10,000 images}
261    \label{fig:table-histoserp}
262  \end{center}
263\end{figure}
264
265For each algorithm, we choose the $(dx,dy)$ values at the histogram peak and
266we refer to them as the \textit{algorithm's displacement}, as opposed to the
267\textit{image's displacement} for a given algorithm. We call $E_{fast}(h,b)$
268the error computed at $(dx,dy)$. As $E_{fast}$ does not depend on the image, it
269is a lot faster to compute than $E_{min}$, and as it is statistically closer to
270$E_{min}$, we can expect it to be a better error estimation than $E$.
271
272\begin{center}
273  \begin{tabular}{|l|c|c|c|c|}
274  \hline
275  &~ $E\times10^4$ ~&~ $dx$ ~&~ $dy$ ~&~ $E_{fast}\times10^4$ ~\\ \hline
276  ~raster Floyd-Steinberg ~&~ 3.7902 ~&~ 0.16 ~&~ 0.28 ~&~ 3.3447 ~\\ \hline
277  ~raster Ja-Ju-Ni        ~&~ 9.7013 ~&~ 0.26 ~&~ 0.76 ~&~ 7.5891 ~\\ \hline
278  ~Ostromoukhov           ~&~ 4.6892 ~&~ 0.00 ~&~ 0.19 ~&~ 4.6117 ~\\ \hline
279  ~optimum kernel         ~&~ 7.5209 ~&~ 0.00 ~&~ 0.34 ~&~ 6.8233 ~\\
280  \hline
281  \end{tabular}
282\end{center}
283
284\section{Using error diffusion displacement for optimum kernel design}
285
286We believe that our higher quality $E_{min}$ error metric may be useful in
287kernel design, because it is the very same error that admittedly superior yet
288computationally expensive algorithms such as DBS try to minimise.
289
290Our first experiment was a study of the Floyd-Steinberg-like 4-block error
291diffusion kernels. According to the original authors, the coefficients were
292found "mostly by trial and error" \cite{fstein}. With our improved metric, we
293now have the tools to confirm or infirm Floyd and Steinberg's initial choice.
294
295We chose to do an exhaustive study of every $\frac{1}{16}\{a,b,c,d\}$ integer
296combination. We deliberately chose positive integers whose sum was 16: error
297diffusion coefficients smaller than zero or adding up to more than 1 are known
298to be unstable \cite{stability}, and diffusing less than 100\% of the error
299causes important loss of detail in the shadow and highlight areas of the image.
300
301We studied all possible coefficients on a pool of 3,000 images with an error
302metric $E$ based on a standard Gaussian HVS model. $E_{min}$ is only given here
303as an indication and only $E$ was used to elect the best coefficients:
304
305\begin{center}
306  \begin{tabular}{|c|c|c|c|}
307  \hline
308  ~ rank ~&~ coefficients ~&~ $E$ ~&~ $E_{min}$ ~\\ \hline
309  ~ 1 ~&~ 8 3 5 0 ~&~ 0.00129563 ~&~ 0.000309993 ~\\ \hline
310  ~ 2 ~&~ 7 3 6 0 ~&~ 0.00131781 ~&~ 0.000313941 ~\\ \hline
311  ~ 3 ~&~ 9 3 4 0 ~&~ 0.00131115 ~&~ 0.000310815 ~\\ \hline
312  ~ 4 ~&~ 9 2 5 0 ~&~ 0.00132785 ~&~ 0.000322754 ~\\ \hline
313  ~ 5 ~&~ 8 4 4 0 ~&~ 0.00131170 ~&~ 0.000317490 ~\\ \hline
314  ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\
315  \hline
316  \end{tabular}
317\end{center}
318
319The exact same operation using $E_{min}$ as the decision variable yields very
320different results. Similarly, $E$ is only given here as an indication:
321
322\begin{center}
323  \begin{tabular}{|c|c|c|c|}
324  \hline
325  ~ rank ~&~ coefficients ~&~ $E_{min}$ ~&~ $E$ ~\\ \hline
326  ~ 1 ~&~ 7 3 5 1 ~&~ 0.000306251 ~&~ 0.00141414 ~\\ \hline
327  ~ 2 ~&~ 6 3 6 1 ~&~ 0.000325488 ~&~ 0.00145197 ~\\ \hline
328  ~ 3 ~&~ 8 3 4 1 ~&~ 0.000313537 ~&~ 0.00141632 ~\\ \hline
329  ~ 4 ~&~ 7 3 4 2 ~&~ 0.000336239 ~&~ 0.00156376 ~\\ \hline
330  ~ 5 ~&~ 6 4 5 1 ~&~ 0.000333702 ~&~ 0.00147671 ~\\ \hline
331  ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\
332  \hline
333  \end{tabular}
334\end{center}
335
336Our improved metric allowed us to confirm that the original Floyd-Steinberg
337coefficients were indeed amongst the best possible for raster scan.
338More importantly, using $E$ as the decision variable may have elected
339$\frac{1}{16}\{8,4,4,0\}$, which is in fact a poor choice.
340
341For serpentine scan, however, our experiment suggests that
342$\frac{1}{16}\{7,4,5,0\}$ is a better choice than the Floyd-Steinberg
343coefficients that have nonetheless been widely in use so far (Fig.
344\ref{fig:lena7450}).
345
346\begin{figure}
347  \begin{center}
348    \includegraphics[width=0.8\textwidth]{lena.eps}
349    \caption{halftone of \textit{Lena} using serpentine error diffusion and
350             the optimum coefficients $\frac{1}{16}\{7,4,5,0\}$ that improve
351             on the standard Floyd-Steinberg coefficients in terms of visual
352             quality for the HVS model studied in section 3.}
353    \label{fig:lena7450}
354  \end{center}
355\end{figure}
356
357\section{Conclusion}
358
359We have disclosed an interesting property of error diffusion algorithms
360allowing to more precisely measure the quality of such halftoning methods.
361Having showed that such quality is often underestimated by usual metrics,
362we hope to see even more development in simple error diffusion methods.
363
364Confirming Floyd and Steinberg's 30-year old "trial-and-error" result with our
365work is only the beginning: future work may cover more complex HVS models,
366for instance by taking into account the angular dependance of the human eye
367\cite{sullivan}. We plan to use our new metric to improve all error diffusion
368methods that may require fine-tuning of their propagation coefficients.
369
370%
371% ---- Bibliography ----
372%
373\begin{thebibliography}{}
374%
375\bibitem[1]{bayer}
376B. Bayer,
377\textit{Color imaging array}.
378U.S. patent 3,971,065 (1976)
379
380\bibitem[2]{void1}
381R.A. Ulichney (Digital Equipment Corporation),
382\textit{Void and cluster apparatus and method for generating dither templates}.
383U.S. patent 5,535,020 (1992)
384
385\bibitem[3]{void2}
386H. Ancin, A. Bhattacharjya and J. Shu (Seiko Epson Corporation),
387\textit{Void-and-cluster dither-matrix generation for better half-tone
388uniformity}.
389U.S. patent 6,088,512 (1997)
390
391\bibitem[4]{fstein}
392R.W. Floyd, L. Steinberg,
393\textit{An adaptive algorithm for spatial grey scale}.
394Proceedings of the Society of Information Display 17, (1976) 75--77
395
396\bibitem[5]{parfstein}
397P. Metaxas,
398\textit{Optimal Parallel Error-Diffusion Dithering}.
399Color Imaging: Device-Indep. Color, Color Hardcopy, and Graphic Arts IV, Proc.
400SPIE 3648, 485--494 (1999)
401
402\bibitem[6]{kite}
403T. D. Kite,
404\textit{Design and Quality Assessment of Forward and Inverse Error-Diffusion
405Halftoning Algorithms}.
406PhD thesis, Dept. of ECE, The University of Texas at Austin, Austin, TX, Aug.
4071998
408
409\bibitem[7]{halftoning}
410R. Ulichney,
411\textit{Digital Halftoning}.
412MIT Press, 1987
413
414\bibitem[8]{spacefilling}
415L. Velho and J. Gomes,
416\textit{Digital halftoning with space-filling curves}.
417Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81--90, 1991
418
419\bibitem[9]{peano}
420I.~H. Witten and R.~M. Neal,
421\textit{Using peano curves for bilevel display of continuous-tone images}.
422IEEE Computer Graphics \& Appl., 2:47--52, 1982
423
424\bibitem[10]{nasanen}
425R. Nasanen,
426\textit{Visibility of halftone dot textures}.
427IEEE Trans. Syst. Man. Cyb., vol. 14, no. 6, pp. 920--924, 1984
428
429\bibitem[11]{allebach}
430M. Analoui and J.~P. Allebach,
431\textit{Model-based halftoning using direct binary search}.
432Proc. of SPIE/IS\&T Symp. on Electronic Imaging Science and Tech.,
433February 1992, San Jose, CA, pp. 96--108
434
435\bibitem[12]{mcnamara}
436Ann McNamara,
437\textit{Visual Perception in Realistic Image Synthesis}.
438Computer Graphics Forum, vol. 20, no. 4, pp. 211--224, 2001
439
440\bibitem[13]{bhatt}
441Bhatt \textit{et al.},
442\textit{Direct Binary Search with Adaptive Search and Swap}.
443\url{http://www.ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf}
444
445\bibitem[14]{4chan}
446moot,
447\url{http://www.4chan.org/}
448
449\bibitem[15]{wong}
450P.~W. Wong and J.~P. Allebach,
451\textit{Optimum error-diffusion kernel design}.
452Proc. SPIE Vol. 3018, p. 236--242, 1997
453
454\bibitem[16]{ostromoukhov}
455Victor Ostromoukhov,
456\textit{A Simple and Efficient Error-Diffusion Algorithm}.
457in Proceedings of SIGGRAPH 2001, in ACM Computer Graphics,  Annual Conference
458Series, pp. 567--572, 2001
459
460\bibitem[17]{lsmb}
461T.~N. Pappas and D.~L. Neuhoff,
462\textit{Least-squares model-based halftoning}.
463in Proc. SPIE, Human Vision, Visual Proc., and Digital Display III, San Jose,
464CA, Feb. 1992, vol. 1666, pp. 165--176
465
466\bibitem[18]{stability}
467R. Eschbach, Z. Fan, K.~T. Knox and G. Marcu,
468\textit{Threshold Modulation and Stability in Error Diffusion}.
469in Signal Processing Magazine, IEEE, July 2003, vol. 20, issue 4, pp. 39--50
470
471\bibitem[19]{sullivan}
472J. Sullivan, R. Miller and G. Pios,
473\textit{Image halftoning using a visual model in error diffusion}.
474J. Opt. Soc. Am. A, vol. 10, pp. 1714--1724, Aug. 1993
475
476\end{thebibliography}
477
478\end{document}
479
Note: See TracBrowser for help on using the repository browser.