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

Last change on this file since 2274 was 2273, checked in by Sam Hocevar, 13 years ago
  • Put the initial (Feb 08) version of the ED displacement paper into SVN, as well as the associated C source code. Both will require huge cleanup for a final release.
File size: 18.7 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 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 in terms of quality is a far more complex issue, as it
68highly depends 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
84Error 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:
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.
96
97Model-based halftoning is the third important algorithm category. It relies
98on a model of the human visual system (HVS) and attempts to minimise an error
99value based on that model. One such algorithm is direct binary seach (DBS)
100\cite{allebach}, also referred to as least-squares model-based halftoning
101(LSMB) \cite{lsmb}.
102
103HVS models are usually low-pass filters. Nasanen \cite{nasanen}, Analoui
104and Allebach \cite{allebach} found that using gaussian models gave visually
105pleasing results, an observation confirmed by independent visual perception
106studies \cite{mcnamara}.
107
108DBS yields halftones of impressive quality. However, despite efforts to make
109it more efficient \cite{bhatt}, it suffers from its large computational
110requirements and error diffusion remains a widely used technique.
111
112\section{Error diffusion displacement}
113
114Most error diffusion implementations parse the image in raster scan order.
115Boustrophedonic (serpentine) scan has been shown to cause fewer visual
116artifacts \cite{halftoning}, but other, more complex processing paths such as
117Hilbert curves \cite{spacefilling}, \cite{peano} are seldom used as they do not
118improve the image quality significantly.
119
120Intuitively, as the error is always propagated to the bottom-left or
121bottom-right of each pixel (Fig. \ref{fig:direction}), one may expect the
122resulting image to be slightly translated. This expectation is confirmed
123when alternatively viewing an error diffused image and the corresponding DBS
124halftone.
125
126\begin{figure}
127  \begin{center}
128    \input{direction}
129    \caption{Floyd-Steinberg error diffusion direction in raster scan (left)
130             and serpentine scan (right).}\label{fig:direction}
131  \end{center}
132\end{figure}
133
134This small translation is visually innocuous but we found that it means a lot
135in terms of error computation. A common way to compute the error between an
136image $h_{i,j}$ and the corresponding halftone $b_{i,j}$ is to compute the
137mean square error between modified versions of the images, in the form:
138
139\begin{equation}
140  E(h,b) = \frac{(||v * h_{i,j} - v * b_{i,j}||_2)^2}{wh}
141\end{equation}
142
143where $w$ and $h$ are the image dimensions, $*$ denotes the convolution and $v$
144is a model for the human visual system.
145
146To compensate for the slight translation experienced in the halftone, we
147use the following error metric instead:
148
149\begin{equation}
150  E_{dx,dy}(h,b) = \frac{(||v * h_{i,j} - v * t_{dx,dy} * b_{i,j}||_2)^2}{wh}
151\end{equation}
152
153where $t_{dx,dy}$ is an operator which translates the image along the $(dx,dy)$
154vector.
155
156A simple example can be given using a gaussian HVS model:
157
158\begin{equation}
159  v(x,y) = e^{\frac{x^2+y^2}{2\sigma^2}}
160\end{equation}
161
162Finding the second filter is then straightforward:
163
164\begin{equation}
165  (v * t_{dx,dy})(x,y) = e^{\frac{(x-dx)^2+(y-dy)^2}{2\sigma^2}}
166\end{equation}
167
168Experiment shows that for a given image and a given corresponding halftone,
169$E_{dx,dy}$ has a local minimum almost always away from $(dx,dy) = (0,0)$ (Fig.
170\ref{fig:lena-min}). Let $E$ be an error metric where this remains true. We
171call the local minimum $E_{min}$:
172
173\begin{equation}
174  E_{min}(h,b) = \min_{dx,dy}E_{dx,dy}(h,b)
175\end{equation}
176
177\begin{figure}
178  \begin{center}
179   \input{lena-min}
180   \caption{Mean square error for the \textit{Lena} image. $v$ is a simple
181            $11\times11$ gaussian convolution kernel with $\sigma = 1.2$ and
182            $(dx,dy)$ vary in $[-1,1]\times[-1,1]$.}
183   \label{fig:lena-min}
184  \end{center}
185\end{figure}
186
187For instance, a Floyd-Steinberg dither of \textit{Lena}, with $\sigma = 1.2$
188yields a per-pixel mean square error of $8.51\times10^{-4}$. However, when
189taking the displacement into account, the error becomes $7.77\times10^{-4}$
190for $(dx,dy) = (0.167709,0.299347)$. The new, corrected error is significantly
191smaller, with the exact same input and output images.
192
193Experiment shows that the corrected error is always noticeably smaller except
194in the case of images that are already mostly pure black and white. The
195experiment was performed on a database of 10,000 images from common computer
196vision sets and from the image board \textit{4chan}, providing a representative
197sampling of the photographs, digital art and business graphics widely exchanged
198on the Internet.
199
200In addition to the classical Floyd-Steinberg and Jarvis, Judice and Ninke
201kernels, we tested two serpentine error diffusion algorithms: Ostromoukhov's
202simple error diffusion \cite{ostromoukhov}, which uses a variable coefficient
203kernel, and Wong and Allebach's optimum error diffusion kernel \cite{wong}.
204
205\begin{center}
206  \begin{tabular}{|l|l|l|}
207  \hline
208  & $E$ & $E_{min}$ \\ \hline
209  raster Floyd-Steinberg & 0.00089705 & 0.000346514 \\ \hline
210  raster Ja-Ju-Ni & 0.0020309 & 0.000692003 \\ \hline
211  Ostromoukhov & 0.00189721 & 0.00186343 \\ \hline
212%    raster optimum kernel & 0.00442951 & 0.00135092 \\ \hline
213  optimum kernel & 0.00146338 & 0.00136522 \\
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 energy 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|l|l|l|l|}
274  \hline
275  & $E$ & $dx$ & $dy$ & $E_{fast}$ \\ \hline
276  raster Floyd-Steinberg & 0.00089705 & 0.16 & 0.28 & 0.00083502 \\ \hline
277  raster Ja-Ju-Ni & 0.0020309 & 0.26 & 0.76 & 0.00192991 \\ \hline
278  Ostromoukhov & 0.00189721 & 0.00 & 0.19 & 0.00186839 \\ \hline
279  optimum kernel & 0.00146338 & 0.00 & 0.34 & 0.00138165 \\
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 proposal.
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 is 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 is
299known to cause important error in shadow and highlight areas of the image.
300
301First we studied all possible coefficients on a pool of 250 images with an
302error metric $E$ based on a standard gaussian HVS model. Since we are studying
303algorithms on different images but error values are only meaningful for a given
304image, we chose a Condorcet voting scheme to determine winners. $E_{min}$ is
305only given here as an indication and had no role in the computation:
306
307\begin{center}
308  \begin{tabular}{|c|c|c|c|}
309  \hline
310  rank & coefficients & $E$ & $E_{min}$ \\ \hline
311  1 & 8 3 5 0 & 0.00129563 & 0.000309993 \\ \hline
312  2 & 7 3 6 0 & 0.00131781 & 0.000313941 \\ \hline
313  3 & 9 3 4 0 & 0.00131115 & 0.000310815 \\ \hline
314  4 & 9 2 5 0 & 0.00132785 & 0.000322754 \\ \hline
315  5 & 8 4 4 0 & 0.0013117 & 0.00031749 \\ \hline
316  \dots & \dots & \dots & \dots \\
317  \hline
318  \end{tabular}
319\end{center}
320
321The exact same operation using $E_{min}$ as the decision variable yields very
322different results. Again, $E$ is only given here as an indication:
323
324\begin{center}
325  \begin{tabular}{|c|c|c|c|}
326  \hline
327  rank & coefficients & $E_{min}$ & $E$ \\ \hline
328  1 & 7 3 5 1 & 0.000306251 & 0.00141414 \\ \hline
329  2 & 6 3 6 1 & 0.000325488 & 0.00145197 \\ \hline
330  3 & 8 3 4 1 & 0.000313537 & 0.00141632 \\ \hline
331  4 & 7 3 4 2 & 0.000336239 & 0.00156376 \\ \hline
332  5 & 6 4 5 1 & 0.000333702 & 0.00147671 \\ \hline
333  \dots & \dots & \dots & \dots \\
334  \hline
335  \end{tabular}
336\end{center}
337
338Our improved metric was able to confirm that the original Floyd-Steinberg
339coefficients were indeed the best possible for raster scan.
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 a given HVS model}
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}. And now that we have a proper metric, we plan to improve all
368error diffusion methods that may require fine-tuning of their propagation
369coefficients.
370
371%
372% ---- Bibliography ----
373%
374\begin{thebibliography}{}
375%
376\bibitem[1]{bayer}
377B. Bayer,
378\textit{Color imaging array}.
379U.S. patent 3,971,065 (1976)
380
381\bibitem[2]{void1}
382R.A. Ulichney (Digital Equipment Corporation),
383\textit{Void and cluster apparatus and method for generating dither templates}.
384U.S. patent 5,535,020 (1992)
385
386\bibitem[3]{void2}
387H. Ancin, A. Bhattacharjya and J. Shu (Seiko Epson Corporation),
388\textit{Void-and-cluster dither-matrix generation for better half-tone
389uniformity}.
390U.S. patent 6,088,512 (1997)
391
392\bibitem[4]{fstein}
393R.W. Floyd, L. Steinberg,
394\textit{An adaptive algorithm for spatial grey scale}.
395Proceedings of the Society of Information Display 17, (1976) 75--77
396
397\bibitem[5]{parfstein}
398P. Metaxas,
399\textit{Optimal Parallel Error-Diffusion Dithering}.
400Color Imaging: Device-Indep. Color, Color Hardcopy, and Graphic Arts IV, Proc.
401SPIE 3648, 485--494 (1999)
402
403\bibitem[6]{quality}
404T. D. Kite,
405\textit{Design and Quality Assessment of Forward and Inverse Error-Diffusion
406Halftoning Algorithms}.
407PhD thesis, Dept. of ECE, The University of Texas at Austin, Austin, TX, Aug.
4081998
409
410\bibitem[7]{halftoning}
411R. Ulichney,
412\textit{Digital Halftoning}
413MIT Press, 1987
414
415\bibitem[8]{spacefilling}
416L. Velho and J. Gomes,
417\textit{Digital halftoning with space-filling curves}
418Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81--90, 1991
419
420\bibitem[9]{peano}
421I.~H. Witten and R.~M. Neal,
422\textit{Using peano curves for bilevel display of continuous-tone images}
423IEEE Computer Graphics \& Appl., 2:47--52, 1982
424
425\bibitem[10]{nasanen}
426R. Nasanen,
427\textit{Visibility of halftone dot textures}
428IEEE Trans. Syst. Man. Cyb., vol. 14, no. 6, pp. 920--924, 1984
429
430\bibitem[11]{allebach}
431M. Analoui and J.~P. Allebach,
432\textit{Model-based halftoning using direct binary search}
433Proc. of SPIE/IS\&T Symp. on Electronic Imaging Science and Tech.,
434February 1992, San Jose, CA, pp. 96--108
435
436\bibitem[12]{mcnamara}
437Ann McNamara,
438\textit{Visual Perception in Realistic Image Synthesis}
439Computer Graphics Forum, vol. 20, no. 4, pp. 211--224, 2001
440
441\bibitem[13]{bhatt}
442Bhatt \textit{et al.},
443\textit{Direct Binary Search with Adaptive Search and Swap}
444\url{http://www.ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf}
445
446\bibitem[14]{4chan}
447moot,
448\url{http://www.4chan.org/}
449
450\bibitem[15]{wong}
451P.~W. Wong and J.~P. Allebach,
452\textit{Optimum error-diffusion kernel design}
453Proc. SPIE Vol. 3018, p. 236--242, 1997
454
455\bibitem[16]{ostromoukhov}
456Victor Ostromoukhov,
457\textit{A Simple and Efficient Error-Diffusion Algorithm}
458in Proceedings of SIGGRAPH 2001, in ACM Computer Graphics,  Annual Conference
459Series, pp. 567--572, 2001
460
461\bibitem[17]{lsmb}
462T.~N. Pappas and D.~L. Neuhoff,
463\textit{Least-squares model-baed halftoning}
464in Proc. SPIE, Human Vision, Visual Proc., and Digital Display III, San Jose,
465CA, Feb. 1992, vol. 1666, pp. 165--176
466
467\bibitem[18]{stability}
468R. Eschbach, Z. Fan, K.~T. Knox and G. Marcu,
469\textit{Threshold Modulation and Stability in Error Diffusion}
470in Signal Processing Magazine, IEEE, July 2003, vol. 20, issue 4, pp. 39--50
471
472\bibitem[19]{kite}
473T.~D. Kite,
474\textit{Design and quality assessment of forward and inverse error diffusion
475halftoning algorithms}
476Ph.~D. in Electrical Engineering (Image Processing), August 1998
477
478\bibitem[20]{sullivan}
479J. Sullivan, R. Miller and G. Pios,
480\textit{Image halftoning using a visual model in error diffusion}
481J. Opt. Soc. Am. A, vol. 10, pp. 1714--1724, Aug. 1993
482
483\end{thebibliography}
484
485\end{document}
486
Note: See TracBrowser for help on using the repository browser.