This is a multi-part message in MIME format.
------_=_NextPart_001_01C8B137.A53B5190
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Terje Mathisen wrote:
> rep_movsd wrote:
> > The thing is Floyd-Steinberg dithering works serially one pixel at a
> > time... Each pixel processed affects the pixel to its right and the
> > pixels on the next scanline.
>
> Interesting algorithm, very serially dependent. :-(
>
> How does it handle the corner/edge cases?
It ignores them.
> I.e. the last pixel on a scan line has no down-right neighbor, the =
first
> pixel has no down-left and the last scanline has nothing below at all!
The errors are just thrown away.
> > So the best I can hope for is to handle one pixels R, G and B byte
> > values in one go.
>
> > Let me clarify with actual code ( highly unoptimal C++ , for =
clarities
> > sake )
>
> It seems to me like the getNearestPalColor() function could easily
> dominate the processing time here!
It does in my implementation. Simple exhaustive search through
up to 256 palette colors. Not too bad with 16.
> I guess a 3D space partition would be a good way to go, using an =
initial
> lookup table based on something like 3:3:3 bits to start in the proper
> subvolume, or simply use that table to point to lists of possible
> palColor candidates for each starting point.
>
> (Due to truncation effects, several pal entries might belong to =
multiple
> lists, depending upon the value of the rounded/truncated RGB bits, but
> with a good set of palette colors, the number of values to test =
against
> should be (on average) pretty low.
The palette colors can be quite constrained in some pictures.
And occupy almost the entire RGB space in others. Maybe some
sort of binary partition scheme?
> Anyway, to speed up the dithering stage I would use MMX/SSE and work =
on
> multiple lines in parallel, keeping the intermediate results in
> registers until we're finished with them.
For all of the multiple lines, except the first, you would have to
process an extra line to provide the error values for the first
plotted.
Steve N.
------_=_NextPart_001_01C8B137.A53B5190
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
6.5.7653.19">
<TITLE>Re: MMX speedup for Floyd Steinberg error diffusion</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=3D2>Terje Mathisen wrote:<BR>
<BR>
> rep_movsd wrote:<BR>
> > The thing is Floyd-Steinberg dithering works serially one =
pixel at a<BR>
> > time... Each pixel processed affects the pixel to its right =
and the<BR>
> > pixels on the next scanline.<BR>
><BR>
> Interesting algorithm, very serially dependent. :-(<BR>
><BR>
> How does it handle the corner/edge cases?<BR>
<BR>
It ignores them.<BR>
<BR>
> I.e. the last pixel on a scan line has no down-right neighbor, the =
first<BR>
> pixel has no down-left and the last scanline has nothing below at =
all!<BR>
<BR>
The errors are just thrown away.<BR>
<BR>
> > So the best I can hope for is to handle one pixels R, G and B =
byte<BR>
> > values in one go.<BR>
><BR>
> > Let me clarify with actual code ( highly unoptimal C++ , for =
clarities<BR>
> > sake )<BR>
><BR>
> It seems to me like the getNearestPalColor() function could =
easily<BR>
> dominate the processing time here!<BR>
<BR>
It does in my implementation. Simple exhaustive =
search through<BR>
up to 256 palette colors. Not too bad with 16.<BR>
<BR>
> I guess a 3D space partition would be a good way to go, using an =
initial<BR>
> lookup table based on something like 3:3:3 bits to start in the =
proper<BR>
> subvolume, or simply use that table to point to lists of =
possible<BR>
> palColor candidates for each starting point.<BR>
><BR>
> (Due to truncation effects, several pal entries might belong to =
multiple<BR>
> lists, depending upon the value of the rounded/truncated RGB bits, =
but<BR>
> with a good set of palette colors, the number of values to test =
against<BR>
> should be (on average) pretty low.<BR>
<BR>
The palette colors can be quite constrained in some =
pictures.<BR>
And occupy almost the entire RGB space in others. Maybe some<BR>
sort of binary partition scheme?<BR>
<BR>
> Anyway, to speed up the dithering stage I would use MMX/SSE and =
work on<BR>
> multiple lines in parallel, keeping the intermediate results in<BR>
> registers until we're finished with them.<BR>
<BR>
For all of the multiple lines, except the first, you would =
have to<BR>
process an extra line to provide the error values for the first<BR>
plotted.<BR>
<BR>
Steve N.</FONT>
</P>
</BODY>
</HTML>
------_=_NextPart_001_01C8B137.A53B5190--
|
