Re: MMX speedup for Floyd Steinberg error diffusion

Terje Mathisen <spamtrap@xxxxxxxxxx> writes:
rep_movsd wrote:
On May 8, 7:00 pm, Terje Mathisen <spamt...@xxxxxxxxxx> wrote:
How does it handle the corner/edge cases?

The edges are handled by ignoring all pixels which do not have the
neighbours, the simplest way I found was to keep my x and y loops
ranging over [1, width-1) and [0, height-1).

OK. Quick & dirty indeed.

It seems to me like the getNearestPalColor() function could easily
dominate the processing time here!

Well Initially the code used the standard distance matching algorithm
as seen in zillions of color reduction libraries :

For each color in the palette
Compute the RGB colorspace distance between the palette entry and the
target color -> (r - rp)^2 + (g - gp)^2 + (b - bp)^2
Choose the index with the minimum distance.

This was pathetically slow... It has to loop 256 times for each pixel
doing several arithmetic ops!
One optimization is to use abs and get rid of the multiplications.

But that messes up the distance calculation because it gives the wrong
answer for many edge cases. OTOH, the error diffusion would tend to
distribute this error across the neighboring pixels, making the visual
impact much less.

It doesn't "mess up the distance calculations" at all, it
simply selects a different metric, namely the L_1 metric
rather than the L_2 metric. However, both are "wrong" in
the strict sense, as a metric which models human vision with
any attempt at fidelity would weight the three different
chroma components differently, giving more weight to the
green component, and less to the red component. (Or even
take place in a different colour-space entirely.) The
volume of space for which the unweighted L_2 metric choses
the wrong palate colour (not the nearest according to the
model of human visual perception) will most probably be
larger than the volume of the corner cases where L_2 selects
the correct colour but L_1 doesn't. (And of course,
there will even be times where the L_1 selects a better
palate colour than L_2.)

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration

.

Relevant Pages

  • Print resolution (was: Where are the BEST Point and Shoot Photos?)
    ... viewing conditions and at normal viewing distance of 22" needs only 156 ... PPI for excellent results, ... CRT high frequency response limits the contrast between adjacent pixels ... Measure your distance from the screen at this point. ...
    (rec.photo.digital)
  • Re: More on 720 vs 1080, plasma
    ... From the chart on viewing ... The sizes in the second chart seem very large to me, but if you want a home ... Most charts give you the distance where a normal eye can resolve the ... distance is to increase the distance somewhat so that the pixels blend ...
    (alt.tv.tech.hdtv)
  • Re: Where are the BEST Point and Shoot Photos ?
    ... viewing conditions and at normal viewing distance of 22" needs only 156 ... camera when viewed at a distance of two feet. ... You're looking at the details so much because your photography ... resolution, more clarity, more pixels, THEN someone will be able to see my ...
    (rec.photo.digital)
  • Re: How can I determine if a point is a given distance from a second point?
    ... I want to limit the points collected to a certain distance from other ... cell) and keep status of each cell in the array. ... 2D working space has 600 x 600 pixels size than you would need array ... too expensive in memory you can limit yourslef to comparing just delta ...
    (microsoft.public.dotnet.languages.csharp)