Ignore:
Timestamp:
Apr 16, 2008, 12:12:05 AM (13 years ago)
Author:
Sam Hocevar
Message:
  • Final version of the paper. Uploaded at the last minute, of course.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • research/2008-displacement/paper/paper.tex

    r2292 r2293  
    102102(LSMB) \cite{lsmb}.
    103103
    104 HVS models are usually low-pass filters. Nasanen \cite{nasanen}, Analoui
    105 and Allebach \cite{allebach} found that using Gaussian models gave visually
    106 pleasing results, an observation confirmed by independent visual perception
    107 studies \cite{mcnamara}.
     104HVS models are usually low-pass filters. Nasanen \cite{nasanen}, Analoui and
     105Allebach found that using Gaussian models gave visually pleasing results, an
     106observation confirmed by independent visual perception studies \cite{mcnamara}.
    108107
    109108DBS yields halftones of impressive quality. However, despite efforts to make
     
    116115Boustrophedonic (serpentine) scanning has been shown to cause fewer visual
    117116artifacts \cite{halftoning}, but other, more complex processing paths such as
    118 Hilbert curves \cite{spacefilling}, \cite{peano} are seldom used as they do not
    119 improve the image quality significantly.
     117Hilbert curves \cite{spacefilling} are seldom used as they do not improve the
     118image quality significantly.
    120119
    121120Intuitively, as the error is always propagated to the bottom-left or
     
    169168Experiments show that for a given image and a given corresponding halftone,
    170169$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
     170\ref{fig:lena-values}). Let $E$ be an error metric where this remains true. We
    172171call the local minimum $E_{min}$:
    173172
     
    177176
    178177\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}
     178  \begin{minipage}[c]{0.8\textwidth}
     179    \input{lena-values}
     180  \end{minipage}
     181  \begin{center}
     182    \caption{Mean square error for the \textit{Lena} image ($\times10^4$). $v$
     183             is a simple $11\times11$ Gaussian convolution kernel with $\sigma
     184             = 1.2$ and $(dx,dy)$ vary in $[-1,1]\times[-1,1]$.}
     185    \label{fig:lena-values}
    185186  \end{center}
    186187\end{figure}
     
    202203we tested two serpentine error diffusion algorithms: Ostromoukhov's simple
    203204error diffusion \cite{ostromoukhov}, which uses a variable coefficient kernel,
    204 and Wong and Allebach's optimum error diffusion kernel \cite{wong}.
     205and Wong and Allebach's optimum error diffusion kernel \cite{wong}:
    205206
    206207\begin{center}
     
    268269the error computed at $(dx,dy)$. As $E_{fast}$ does not depend on the image, it
    269270is 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$E_{min}$, we can expect it to be a better error estimation than $E$:
    271272
    272273\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 ~\\
     274  \begin{tabular}{|l|c|c|c|c|c|}
     275  \hline
     276  &~ $E\times10^4$ ~&~ $E_{min}\times10^4$ ~&~ $dx$ ~&~ $dy$ ~&~ $E_{fast}\times10^4$ ~\\ \hline
     277  ~raster Floyd-Steinberg ~&~ 3.7902 ~&~ 3.1914 ~&~ 0.16 ~&~ 0.28 ~&~ 3.3447 ~\\ \hline
     278  ~raster Ja-Ju-Ni        ~&~ 9.7013 ~&~ 6.6349 ~&~ 0.26 ~&~ 0.76 ~&~ 7.5891 ~\\ \hline
     279  ~Ostromoukhov           ~&~ 4.6892 ~&~ 4.4783 ~&~ 0.00 ~&~ 0.19 ~&~ 4.6117 ~\\ \hline
     280  ~optimum kernel         ~&~ 7.5209 ~&~ 6.5772 ~&~ 0.00 ~&~ 0.34 ~&~ 6.8233 ~\\
    280281  \hline
    281282  \end{tabular}
     
    309310  ~ 1 ~&~ 7 3 6 0 ~&~ 4.65512 ~&~ 3.94217 ~\\ \hline
    310311  ~ 2 ~&~ 8 3 5 0 ~&~ 4.65834 ~&~ 4.03699 ~\\ \hline
    311   ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline
     312  \hline
    312313  ~ 5 ~&~ 7 3 5 1 ~&~ 4.68588 ~&~ 3.79556 ~\\ \hline
    313   ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline
     314  \hline
    314315  ~ 18 ~&~ 6 3 5 2 ~&~ 4.91020 ~&~ 3.70465 ~\\ \hline
    315316  ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\
     
    327328  ~ 1 ~&~ 6 3 5 2 ~&~ 3.70465 ~&~ 4.91020 ~\\ \hline
    328329  ~ 2 ~&~ 7 3 5 1 ~&~ 3.79556 ~&~ 4.68588 ~\\ \hline
    329   ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline
     330  \hline
    330331  ~ 15 ~&~ 7 3 6 0 ~&~ 3.94217 ~&~ 4.65512 ~\\ \hline
    331   ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\ \hline
     332  \hline
    332333  ~ 22 ~&~ 8 3 5 0 ~&~ 4.03699 ~&~ 4.65834 ~\\ \hline
    333334  ~ \dots ~&~ \dots ~&~ \dots ~&~ \dots ~\\
     
    339340coefficients were indeed amongst the best possible for raster scan.
    340341More importantly, using $E$ as the decision variable may have elected
    341 $\frac{1}{16}\{8,4,4,0\}$, which is in fact a poor choice.
     342$\frac{1}{16}\{7,3,6,0\}$ or $\frac{1}{16}\{8,3,5,0\}$, which are in fact poor
     343choices.
    342344
    343345For serpentine scan, however, our experiment suggests that
     
    348350\begin{figure}
    349351  \begin{center}
    350     \includegraphics[width=0.8\textwidth]{lena.eps}
    351     \caption{halftone of \textit{Lena} using serpentine error diffusion and
    352              the optimum coefficients $\frac{1}{16}\{7,4,5,0\}$ that improve
    353              on the standard Floyd-Steinberg coefficients in terms of visual
    354              quality for the HVS model studied in section 3.}
     352    \includegraphics[width=0.4\textwidth]{output-7-3-5-1-serp.eps}
     353    ~
     354    \includegraphics[width=0.4\textwidth]{output-7-4-5-0-serp.eps}
     355  \end{center}
     356  \begin{center}
     357    \includegraphics[width=0.4\textwidth]{crop-7-3-5-1-serp.eps}
     358    ~
     359    \includegraphics[width=0.4\textwidth]{crop-7-4-5-0-serp.eps}
     360    \caption{halftone of \textit{Lena} using serpentine error diffusion
     361             (\textit{left}) and the optimum coefficients
     362             $\frac{1}{16}\{7,4,5,0\}$ (\textit{right}) that improve on the
     363             standard Floyd-Steinberg coefficients in terms of visual quality
     364             for the HVS model used in section 3. The detailed area
     365             (\textit{bottom}) shows fewer structure artifacts in the regions
     366             with low contrast.}
    355367    \label{fig:lena7450}
    356368  \end{center}
     
    419431Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81--90, 1991
    420432
    421 \bibitem[9]{peano}
    422 I.~H. Witten and R.~M. Neal,
    423 \textit{Using peano curves for bilevel display of continuous-tone images}.
    424 IEEE Computer Graphics \& Appl., 2:47--52, 1982
    425 
    426 \bibitem[10]{nasanen}
     433\bibitem[9]{nasanen}
    427434R. Nasanen,
    428435\textit{Visibility of halftone dot textures}.
    429436IEEE Trans. Syst. Man. Cyb., vol. 14, no. 6, pp. 920--924, 1984
    430437
    431 \bibitem[11]{allebach}
     438\bibitem[10]{allebach}
    432439M. Analoui and J.~P. Allebach,
    433440\textit{Model-based halftoning using direct binary search}.
     
    435442February 1992, San Jose, CA, pp. 96--108
    436443
    437 \bibitem[12]{mcnamara}
     444\bibitem[11]{mcnamara}
    438445Ann McNamara,
    439446\textit{Visual Perception in Realistic Image Synthesis}.
    440447Computer Graphics Forum, vol. 20, no. 4, pp. 211--224, 2001
    441448
    442 \bibitem[13]{bhatt}
     449\bibitem[12]{bhatt}
    443450Bhatt \textit{et al.},
    444451\textit{Direct Binary Search with Adaptive Search and Swap}.
    445452\url{http://www.ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf}
    446453
    447 \bibitem[14]{4chan}
     454\bibitem[13]{4chan}
    448455moot,
    449456\url{http://www.4chan.org/}
    450457
    451 \bibitem[15]{wong}
     458\bibitem[14]{wong}
    452459P.~W. Wong and J.~P. Allebach,
    453460\textit{Optimum error-diffusion kernel design}.
    454461Proc. SPIE Vol. 3018, p. 236--242, 1997
    455462
    456 \bibitem[16]{ostromoukhov}
     463\bibitem[15]{ostromoukhov}
    457464Victor Ostromoukhov,
    458465\textit{A Simple and Efficient Error-Diffusion Algorithm}.
     
    460467Series, pp. 567--572, 2001
    461468
    462 \bibitem[17]{lsmb}
     469\bibitem[16]{lsmb}
    463470T.~N. Pappas and D.~L. Neuhoff,
    464471\textit{Least-squares model-based halftoning}.
     
    466473CA, Feb. 1992, vol. 1666, pp. 165--176
    467474
    468 \bibitem[18]{stability}
     475\bibitem[17]{stability}
    469476R. Eschbach, Z. Fan, K.~T. Knox and G. Marcu,
    470477\textit{Threshold Modulation and Stability in Error Diffusion}.
    471478in Signal Processing Magazine, IEEE, July 2003, vol. 20, issue 4, pp. 39--50
    472479
    473 \bibitem[19]{sullivan}
     480\bibitem[18]{sullivan}
    474481J. Sullivan, R. Miller and G. Pios,
    475482\textit{Image halftoning using a visual model in error diffusion}.
     
    479486
    480487\end{document}
    481 
Note: See TracChangeset for help on using the changeset viewer.