Re: MMX speedup for Floyd Steinberg error diffusion

Novosad, Stephan R. wrote:
Terje wrote:

> To do a mathematically perfect job I would start with a 5:5:5 (32 K) or
> 4:4:4 (4 K) table, with each entry being the start of a list of all the
> possible palette entries for that entry:
[snip]
Well, doing a crude implementation with a 4:4:4 array using
just one of 256 palette entries in each (no extra lists), I
ran some tests. On a nice slow Pentium, with a couple of test
images, the speed-up was maybe a factor of 50+ in display time.
With F-S dithering on, the image "looks" the same. With F-S
turned off, there was some obvious differences between the
table look up and the brute force search. The list of possible
entries version appears to be needed for an "optimum" result.

The really nice part here is that for most images/palettes, the majority of lookup table entries will map to a single pal color, with most of the remainder having just two or three possible alternatives, right?

This means that using a 4:4:4 lookup table with collision lists will be nearly as fast as the straight lookup case (i.e. 50x faster! :-), but still delivering "perfect" results.

The palette optimization problem is in some ways much more interesting, particularly since it is almost certainly one of the HARD (as in NP) problems, it seems similar to the knapsack problem.

When we combine them, and want to generate an optimized palette for an image encoded with some form of error diffusion, then the search space becomes _very_ large indeed.

(It seems intuitively obvious that you must first determine the 3D outer boundary of the volume that surrounds all the true color pixels, then make sure that the surface described in the same space by your palette selection can cover the same volume: Any point outside the outside boundary is impossible to reach using any linear combination of the pal entries on the inside, right?)

Terje
--
- <Terje.Mathisen@xxxxxxxxxxxxx>
"almost all programming can be viewed as an exercise in caching"

.

Relevant Pages

  • Re: The Anime Primer "Pre-Approved List"
    ... but aren't yet in the Primer. ... only write entries for shows you like enough to recommend to ... quarterly anime review lists, three stars on Manbow Papa's quarterly ... Ouran High School Host Club ...
    (rec.arts.anime.fandom)
  • Re: Synchronization routine
    ... Basically I have two lists, one on my firewall and one in a database. ... current sizes are over 1 million entries and I expect to see 2 million rows ... which I can randomly access ... quicksort wasn't too efficient and finally caused a stack overflow. ...
    (comp.programming)
  • Re: Best writers I havent yet read
    ... Science Fiction> and. ... considered was to look for authors represented by multiple books in my ... So I've spent much of this past week compiling a list of author entries ... If anyone wants the full lists, or whatever, well, e-mail or post, ...
    (rec.arts.sf.written)
  • [info] The Anime Primer "Pre-Approved List"
    ... but aren't yet in the Primer. ... only write entries for shows you like enough to recommend to ... quarterly anime review lists, three stars on Manbow Papa's quarterly ... Tokyo Mew Mew / Mew Mew Power ...
    (rec.arts.anime.misc)
  • Re: OL2002: Adding list of contacts to a Distribution List after search
    ... My Contacts entries have multiple Categories, so let's say I want to ... or simply Friends New York. ... Categories - once in Friends, again in Business, and a 3rd time in New ... |> I need to create email distribution lists of people that meet ...
    (microsoft.public.outlook.contacts)