Changeset 2291


Ignore:
Timestamp:
04/16/08 00:11:47 (5 years ago)
Author:
sam
Message:
  • More fixes in the paper.
Location:
research/2008-displacement
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • research/2008-displacement/README

    r2290 r2291  
    44# Put all my 4chan images in 100 separate /tmp directories 
    55for x in $(seq -w 00 09); do echo $x; mkdir -p /tmp/4chan/$x; cp $(find ~/4chan/unsorted-4chan/http* -name '1[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]'$x'.???') /tmp/4chan/$x; done 
     6 
     7# Results for part 1 
     8for x in 1 2 3 4; do 
     9    grep '^\['$x part1/dionoea.txt | awk '{ e+=$4; ef+=$7; em+=$10; n++ } END { print e/n, ef/n, em/n }' | read a1 b1 c1 
     10    grep '^\['$x part1/4chan.txt | awk '{ e+=$4; ef+=$7; em+=$10; n++ } END { print e/n, ef/n, em/n }' | read a2 b2 c2 
     11    echo $(((3 * $a1 + $a2) / 4)) $(((3 * $b1 + $b2) / 4)) $(((3 * $c1 + $c2) / 4)) 
     12done 
    613 
    714# Condorcet voting for phase 2 results 

  • research/2008-displacement/paper/paper.tex

    r2290 r2291  
    4040\begin{abstract} 
    4141In this contribution we introduce a little-known property of error diffusion 
    42 halftoning algorithms which we call error diffusion displacement. 
     42halftoning algorithms which we call {\it error diffusion displacement}. 
    4343By accounting for the inherent sub-pixel displacement caused by the error 
    4444propagation, we correct an important flaw in most metrics used to assess the 
    … …  
    6565address the problem of colour reduction. Comparing two algorithms in terms of 
    6666speed or memory usage is often straightforward, but how exactly a halftoning 
    67 algorithm performs in terms of quality is a far more complex issue, as it 
    68 highly depends on the display device and the inner workings of the human eye. 
     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. 
    6969 
    7070Though this document focuses on the particular case of bilevel halftoning, 
    … …  
    8282yielding visually pleasing results. 
    8383 
    84 Error diffusion dithering, introduced in 1976 by Floyd and Steinberg 
     84\medskip Error diffusion dithering, introduced in 1976 by Floyd and Steinberg 
    8585\cite{fstein}, tries to compensate for the thresholding error through the use 
    8686of feedback. Typically applied in raster scan order, it uses an error diffusion 
    87 matrix such as the following one: 
     87matrix such as the following one, where $x$ denotes the pixel being processed: 
    8888 
    8989\[ \frac{1}{16} \left| \begin{array}{ccc} 
    … …  
    9393Though efforts have been made to make error diffusion parallelisable 
    9494\cite{parfstein}, it is generally considered more computationally expensive 
    95 than screening. 
    96  
    97 Model-based halftoning is the third important algorithm category. It relies 
    98 on a model of the human visual system (HVS) and attempts to minimise an error 
    99 value based on that model. One such algorithm is direct binary seach (DBS) 
    100 \cite{allebach}, also referred to as least-squares model-based halftoning 
     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 
    101102(LSMB) \cite{lsmb}. 
    102103 
    … …  
    108109DBS yields halftones of impressive quality. However, despite efforts to make 
    109110it more efficient \cite{bhatt}, it suffers from its large computational 
    110 requirements and error diffusion remains a widely used technique. 
     111requirements and error diffusion remains a more widely used technique. 
    111112 
    112113\section{Error diffusion displacement} 
    … …  
    121122bottom-right of each pixel (Fig. \ref{fig:direction}), one may expect the 
    122123resulting image to be slightly translated. This expectation is confirmed 
    123 when alternatively viewing an error diffused image and the corresponding DBS 
    124 halftone. 
     124visually when rapidly switching between an error diffused image and the 
     125corresponding DBS halftone. 
    125126 
    126127\begin{figure} 
    … …  
    134135This small translation is visually innocuous but we found that it means a lot 
    135136in terms of error computation. A common way to compute the error between an 
    136 image $h_{i,j}$ and the corresponding halftone $b_{i,j}$ is to compute the 
    137 mean square error between modified versions of the images, in the form: 
     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: 
    138139 
    139140\begin{equation} 
    … …  
    144145convolution and $v$ is a model for the human visual system. 
    145146 
    146 To compensate for the slight translation experienced in the halftone, we 
    147 use the following error metric instead: 
     147To compensate for the slight translation observed in the halftone, we use the 
     148following error metric instead: 
    148149 
    149150\begin{equation} 
    … …  
    152153 
    153154\noindent where $t_{dx,dy}$ is an operator which translates the image along the 
    154 $(dx,dy)$ vector. 
     155$(dx,dy)$ vector. By design, $E_{0,0} = E$. 
    155156 
    156157A simple example can be given using a Gaussian HVS model: 
    … …  
    185186\end{figure} 
    186187 
    187 For instance, a Floyd-Steinberg dither of \textit{Lena}, with $\sigma = 1.2$ 
    188 yields a per-pixel mean square error of $8.51\times10^{-4}$. However, when 
    189 taking the displacement into account, the error becomes $7.77\times10^{-4}$ 
    190 for $(dx,dy) = (0.167709,0.299347)$. The new, corrected error is significantly 
    191 smaller, with the exact same input and output images. 
     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. 
    192193 
    193194Experiments show that the corrected error is always noticeably smaller except 
    … …  
    196197vision sets and from the image board \textit{4chan}, providing a representative 
    197198sampling of the photographs, digital art and business graphics widely exchanged 
    198 on the Internet. 
    199  
    200 In addition to the classical Floyd-Steinberg and Jarvis, Judice and Ninke 
    201 kernels, we tested two serpentine error diffusion algorithms: Ostromoukhov's 
    202 simple error diffusion \cite{ostromoukhov}, which uses a variable coefficient 
    203 kernel, and Wong and Allebach's optimum error diffusion kernel \cite{wong}. 
     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}. 
    204205 
    205206\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 \\ 
     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 ~\\ 
    214214  \hline 
    215215  \end{tabular} 
    … …  
    227227visual error measurement than $E(h,b)$. However, its major drawback is that it 
    228228is highly computationally expensive: for each image, the new $(dx,dy)$ values 
    229 need to be calculated to minimise the energy value. 
     229need to be calculated to minimise the error value. 
    230230 
    231231Fortunately, we found that for a given raster or serpentine scan 
    … …  
    271271 
    272272\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 \\ 
     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 ~\\ 
    280280  \hline 
    281281  \end{tabular} 
    … …  
    291291diffusion kernels. According to the original authors, the coefficients were 
    292292found "mostly by trial and error" \cite{fstein}. With our improved metric, we 
    293 now have the tools to confirm or infirm Floyd and Steinberg's initial proposal. 
     293now have the tools to confirm or infirm Floyd and Steinberg's initial choice. 
    294294 
    295295We chose to do an exhaustive study of every $\frac{1}{16}\{a,b,c,d\}$ integer 
    296 combination. We deliberately chose positive integers whose sum is 16. Error 
     296combination. We deliberately chose positive integers whose sum was 16: error 
    297297diffusion coefficients smaller than zero or adding up to more than 1 are known 
    298 to be unstable \cite{stability}, and diffusing less than 100\% of the error is 
    299 known to cause important error in shadow and highlight areas of the image. 
    300  
    301 First we studied all possible coefficients on a pool of 250 images with an 
    302 error metric $E$ based on a standard Gaussian HVS model. Since we are studying 
    303 algorithms on different images but error values are only meaningful for a given 
    304 image, we chose a Condorcet voting scheme to determine winners. $E_{min}$ is 
    305 only given here as an indication and had no role in the computation: 
     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: 
    306304 
    307305\begin{center} 
    308306  \begin{tabular}{|c|c|c|c|} 
    309307  \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 \\ 
     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 ~\\ 
    317315  \hline 
    318316  \end{tabular} 
    … …  
    320318 
    321319The exact same operation using $E_{min}$ as the decision variable yields very 
    322 different results. Again, $E$ is only given here as an indication: 
     320different results. Similarly, $E$ is only given here as an indication: 
    323321 
    324322\begin{center} 
    325323  \begin{tabular}{|c|c|c|c|} 
    326324  \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 \\ 
     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 ~\\ 
    334332  \hline 
    335333  \end{tabular} 
    336334\end{center} 
    337335 
    338 Our improved metric was able to confirm that the original Floyd-Steinberg 
    339 coefficients were indeed the best possible for raster scan. 
     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. 
    340340 
    341341For serpentine scan, however, our experiment suggests that 
    … …  
    350350             the optimum coefficients $\frac{1}{16}\{7,4,5,0\}$ that improve 
    351351             on the standard Floyd-Steinberg coefficients in terms of visual 
    352              quality for a given HVS model} 
     352             quality for the HVS model studied in section 3.} 
    353353    \label{fig:lena7450} 
    354354  \end{center} 
    … …  
    365365work is only the beginning: future work may cover more complex HVS models, 
    366366for 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 
    368 error diffusion methods that may require fine-tuning of their propagation 
    369 coefficients. 
     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. 
    370369 
    371370% 
    … …  
    401400SPIE 3648, 485--494 (1999) 
    402401 
    403 \bibitem[6]{quality} 
     402\bibitem[6]{kite} 
    404403T. D. Kite, 
    405404\textit{Design and Quality Assessment of Forward and Inverse Error-Diffusion 
    … …  
    410409\bibitem[7]{halftoning} 
    411410R. Ulichney, 
    412 \textit{Digital Halftoning} 
     411\textit{Digital Halftoning}. 
    413412MIT Press, 1987 
    414413 
    415414\bibitem[8]{spacefilling} 
    416415L. Velho and J. Gomes, 
    417 \textit{Digital halftoning with space-filling curves} 
     416\textit{Digital halftoning with space-filling curves}. 
    418417Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81--90, 1991 
    419418 
    420419\bibitem[9]{peano} 
    421420I.~H. Witten and R.~M. Neal, 
    422 \textit{Using peano curves for bilevel display of continuous-tone images} 
     421\textit{Using peano curves for bilevel display of continuous-tone images}. 
    423422IEEE Computer Graphics \& Appl., 2:47--52, 1982 
    424423 
    425424\bibitem[10]{nasanen} 
    426425R. Nasanen, 
    427 \textit{Visibility of halftone dot textures} 
     426\textit{Visibility of halftone dot textures}. 
    428427IEEE Trans. Syst. Man. Cyb., vol. 14, no. 6, pp. 920--924, 1984 
    429428 
    430429\bibitem[11]{allebach} 
    431430M. Analoui and J.~P. Allebach, 
    432 \textit{Model-based halftoning using direct binary search} 
     431\textit{Model-based halftoning using direct binary search}. 
    433432Proc. of SPIE/IS\&T Symp. on Electronic Imaging Science and Tech., 
    434433February 1992, San Jose, CA, pp. 96--108 
    … …  
    436435\bibitem[12]{mcnamara} 
    437436Ann McNamara, 
    438 \textit{Visual Perception in Realistic Image Synthesis} 
     437\textit{Visual Perception in Realistic Image Synthesis}. 
    439438Computer Graphics Forum, vol. 20, no. 4, pp. 211--224, 2001 
    440439 
    441440\bibitem[13]{bhatt} 
    442441Bhatt \textit{et al.}, 
    443 \textit{Direct Binary Search with Adaptive Search and Swap} 
     442\textit{Direct Binary Search with Adaptive Search and Swap}. 
    444443\url{http://www.ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf} 
    445444 
    … …  
    450449\bibitem[15]{wong} 
    451450P.~W. Wong and J.~P. Allebach, 
    452 \textit{Optimum error-diffusion kernel design} 
     451\textit{Optimum error-diffusion kernel design}. 
    453452Proc. SPIE Vol. 3018, p. 236--242, 1997 
    454453 
    455454\bibitem[16]{ostromoukhov} 
    456455Victor Ostromoukhov, 
    457 \textit{A Simple and Efficient Error-Diffusion Algorithm} 
     456\textit{A Simple and Efficient Error-Diffusion Algorithm}. 
    458457in Proceedings of SIGGRAPH 2001, in ACM Computer Graphics,  Annual Conference 
    459458Series, pp. 567--572, 2001 
    … …  
    461460\bibitem[17]{lsmb} 
    462461T.~N. Pappas and D.~L. Neuhoff, 
    463 \textit{Least-squares model-baed halftoning} 
     462\textit{Least-squares model-based halftoning}. 
    464463in Proc. SPIE, Human Vision, Visual Proc., and Digital Display III, San Jose, 
    465464CA, Feb. 1992, vol. 1666, pp. 165--176 
    … …  
    467466\bibitem[18]{stability} 
    468467R. Eschbach, Z. Fan, K.~T. Knox and G. Marcu, 
    469 \textit{Threshold Modulation and Stability in Error Diffusion} 
     468\textit{Threshold Modulation and Stability in Error Diffusion}. 
    470469in Signal Processing Magazine, IEEE, July 2003, vol. 20, issue 4, pp. 39--50 
    471470 
    472 \bibitem[19]{kite} 
    473 T.~D. Kite, 
    474 \textit{Design and quality assessment of forward and inverse error diffusion 
    475 halftoning algorithms} 
    476 Ph.~D. in Electrical Engineering (Image Processing), August 1998 
    477  
    478 \bibitem[20]{sullivan} 
     471\bibitem[19]{sullivan} 
    479472J. Sullivan, R. Miller and G. Pios, 
    480 \textit{Image halftoning using a visual model in error diffusion} 
     473\textit{Image halftoning using a visual model in error diffusion}. 
    481474J. Opt. Soc. Am. A, vol. 10, pp. 1714--1724, Aug. 1993 
    482475 
Note: See TracChangeset for help on using the changeset viewer.