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@[EMAIL PROTECTED]
>
"almost all programming can be viewed as an exercise in caching"
|
