NYYRIKKI

a new proposal:

1) Select the 16 color palette in order to optimize it on the first N lines, say e.g. N=4

2) Use the palette optimized on line 1:N to encode only the first line. Store the result and the 16 colors palette.

3) Move the N line window one line below. Now consider lines 2 : (N+1).

4) Try to encode lines 2: (N+1) using the 16 colors from the previous palette.

5) Choose the 2 colors that give the maximum distortion.

6) Optimize only those 2 colors given that the other 14 colors stay fixed (use a "partial" kmeans)

7) Encode line 2 with this new optimized palette. Store the result and the two optimized colors.

8) goto 3 till the end

why this should work better than yours?

Because the 16 initial colors are selected on a "window" of N lines

and before line M get encoded, 2xN colors have changed on the basis of an observation window

that contains also line M.

Moreover, if 2xN >=16, you are sure that all colors could have changed before line M get encoded,

thus distortion on line M is for sure limited.

On the opposite, having N large does not allow prompt color transitions on the vertical direction, as

you need at least N/2 lines to change all the colors.

Do you like the proposal?

[edit]

Some details are wrong due to the fact you cannot use the whole 16 colors on all lines,

but the main ideas stay fine. Replace 16 with 14 and everything should work.

[/edit]

ARTRAG

Your "window" idea sounds like well working. It is really hard for me to say what kind of algorithm would work best before you can see the result.

As you said this does not allow prompt transitions but that may be a good thing. Sudden big changes in palette may cause horizontal stripes that you don't want to see.

Anyway I think that big changes in palette are quite a rare. There might be many lines that does not need any changes. This is a good thing as then we can use more colors on these lines. This ofcourse depends of the picture a lot.

DamageX

BTW could you tell how you selected the colors to change in your program?

The window is good as, due to limits on the z80, the most part of the colors used in line 1, must stay the

same in line 2, 3 and so on.

A window of e.g. 4 lines allows to adapt the palette non only to the current line but somehow also to

the following lines.

Provided that, passing from line 1 to line 2, you can "optimize" only 2 colors, the remaining 14 colors,

being chosen on a window that included line 2, are "fine" also for the line 2.

I agree... Now we only need some converted pictures.

Well, can you run matlab ?

By if you already not knows how to select the four colors to be changed for less distortion I have a Idea of how mathly calculate that.

There is two ways, BRUTE FORCE (I like this one by its simplicity).

And the Two arrays to be compared system.

In order to do better task about thw Two arrays idea!.

we needs to asks SOMETHING?.....

What we want to distort less?.. the luminance (Y) factor, or crominance (UV or JK) factor!.

In real life is known that if you reproduce better the (Y) luminance factor, you get a best result BUT offcourse the crominance also does its part.!!!! So, in the formula to compare the components we needs to manage a subfactor of how much the crominances values has effect in the final choice, the idea is that this factor must be calibrated using real experience.

...

So, the lines are 512 pixel width!... ok

Make two arrays of 512 elements, one for each line, with four sub-elements and to convert RGB -> YJK using the standard math formula because we want to manage those sub-components freely.

' For line 1

Arry1(0,CoordX) for (Y) component.

Arry1(1,CoordX) for (J) component.

Arry1(2,CoordX) for (K) component.

Arry1(3,CoordX) for the numer of pallete chosen. (that is already preset according to the YJK components of LINE1).

' For line 2

Arry2(0,CoordX) for (Y) component

Arry2(1,CoordX) for (J) component

Arry2(2,CoordX) for (K) component

Arry2(3,CoordX) for the numer of pallete chosen.

The pseudo formula:

When we need to chose the palette for the first pixel of LINE2 we compare the YUV component with each palette of the line1

so

a rush formula can be like (not related to variables before mentioned)

LessDiff=256

PalWithLessDiff=0

for pal = 0 to 15

Diff = (PaletteY(pal)-PixY(CoordX))+Angle(PaletteJ(pal),PaletteK(pal))-Angle(PixJ(CoordX),PixK(CoordX))/Factor

if Diff

So, after the loop you has the Pallete more apropiated for this pixel

You can store the DIFF result of each pixel... and to chose those pixels that has the bigger DIFF (DIFF= Difference)

The Angle(J,K) function is a standard function that returns the color ANGLE in the J K plane.

My color selection routine works like this for the first line:

1)count the number of unique colors and rank them by usage

2)check whether number of colors is above the limit

3)set error threshold to 1

4)starting at the bottom of the list (least used color), compare with the other colors starting at the top of the list, until a close match is found. (error threshold = sum of the squares of r1-r2, g1-g2, b1-b2)

5)remove the less-used color from the list

6)replace all occurences of that color in the line with the substitute

7)adjust the rank of the substitute color

8)check whether number of colors is still above the limit

9)after parsing the whole list, increase the error threshold and go to step 4 again

For the other lines, up to x number of colors from the previous line that are used the most often in the current line are automatically selected.

I modified it for changing only two colors per line but I haven't got it to display quite right, there is still some kind of glitch...

@flyguille

my algorithm (or better proposal of algorithm) deals with 3D points

they can be RGB, YJK or any perceptually uniform color space.

It is a matter of choice.

Kmeans (or the partial kmeans I propose, works on 3D vectors).

Your procedure seems too greedy to give good performance,

but, only results count. We'll compare them once we get them.

Well, can you run matlab ?

I don't really know what it is, but I guess it's not freeware.

erhh, no

www.mathworks.com

http://en.wikipedia.org/wiki/MATLAB

*_*

BTW this is free

http://users.powernet.co.uk/kienzle/octave/matcompat/