Idea for math experts...

페이지 4/9
1 | 2 | 3 | | 5 | 6 | 7 | 8 | 9

By ARTRAG

Enlighted (6543)

ARTRAG의 아바타

13-05-2007, 12:20

the idea is simple:

each line is a set of 512 vectors in the RGB space

If you had 12 colors to be chosen freely you would apply kmeans (or any Vector Quantization algorithm) in order to
find the 12 best centroids of the data.

As we can move only 4 colors of the above 12, we need to modify kmeans in order to take into account that only 4 cluster
of the 12 needs to be updated

As I told in a previous post there are (8 chosen among 12 )= 495 sets of "fixed" colors, thus
you need to run the "constrained kmeans" 495 times and choose the solution that gives
the minimum distortion

this seems the best and easiest solutionl, do you agree?

By DamageX

Master (217)

DamageX의 아바타

14-05-2007, 07:00

you need to run the "constrained kmeans" 495 times and choose the solution that gives
the minimum distortion

I've never coded kmeans before (not really a math expert!) and don't really know how it works. I guess that what I have done is probably faster but less accurate.

here is the result
http://www.hyakushiki.net/msx/beckimsx.bmp
http://www.hyakushiki.net/msx/beckimsx.lzh
http://www.hyakushiki.net/msx/napali4.bmp
http://www.hyakushiki.net/msx/napali.lzh
http://www.hyakushiki.net/msx/worldmsx.bmp
http://www.hyakushiki.net/msx/worldmsx.lzh

The lzh file contains two screen 7 pages (interlaced) that can be BLOADed. There are also two palette files with 32 bytes for the first line and 12 bytes for each subsequent line. NYYRIKKI, will you try to display the files on MSX with palette changing? (hopefully all the data is correct...)

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

14-05-2007, 12:03

@DamageX Wow, I said I would appreciate your help, but I didn't think that you would make a conversion program! Big smile Great! I'm still very busy, but I'll try to take some time for this. I already tested the routine that I posted and it seems that I managed to make totally not working routine Smile Don't worry, I'll fix it...

@ARTRAG I can follow your idea untill you start talking about 8 colors. What is this number? You should select 16 colors. On next line use & leave unchanged 12 of them and change 4.

By ARTRAG

Enlighted (6543)

ARTRAG의 아바타

14-05-2007, 12:40

@NYYRIKKI

You canchange 4 colors per line, so you cannot use them in current line or you get random values displayed.

This gives the 12 color limit on the current (say #1)

Now the next line (say#2) has the same 12 color limit, as while line #2 is diplayed, you need to set up colors for line #3;

so, for line #2, you need to select 12 colors among the 12 colors of the previous line and the 4 colors that can be freely chosen

I assume you decide to change always the palette of 4 colors, as they can best fit the new line in this way.

Now, in order to reach 12 colors, you need to select only 8 colors among those in the previous line.

How many ways there in order to select 8 colors among 12 ?

This gives 495 ways for selecting the "fixed" 8 colors: the remaining 4 can be freely optimized.

The rest of the algorithm goes as I said before

Do you agree?

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

14-05-2007, 18:13

@ARTRAG:

The problem why you end up with 8 fixed colors is that you expect that you don't know what colors need to be changed for next line, but this is not true. If you start selecting of colors from BOTTOM of the screen you know what is needed to be done, so you can always use 12-16 colors for every line and change 0-4 colors.

You just need to swap your thinking around. Do not think that you have to select colors from previous line but just 12 colors of next line.

Let's say that we have picture that has 3 lines and we always need to change all 4 colors (that might not be true in real life. You can skip the colors by defining color 0 as black for example) Anyway:

line #3 can use all of the 16 colors since there is no need to make changes while displaying this line as this line is the last line. (select for exampple all 16 colors palette (0=black) using this line)

line #2 can use 12 colors identical to line #3 and can not use 4 colors that are going to be changed during the display of this line for line #3 (color numbers are defined by worst suitable colors of line #3 for representing line #2)

line #1 can use 12 colors identical to line #2 and can not use 4 colors that are going to be changed during the display of this line for line #2 (color numbers are defined by worst suitable colors of line #2 for representing line #1)

On VBLANC we have to setup 16 color palette that has 12 colors for line #2 and 4 colors for line #1. Note that the color numbers for line #1 are in "random" places as the color numbers depends of all following lines. Because color numbers change (what colors best fit for displaying this line among colors of next line), you don't ever need to think about previous line.

Do you follow my idea? This seems to be very hard to explain...

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

14-05-2007, 19:09

I still tryed to put this in more easy to understand form:

Let's say that there is happening the maximum color palette change in end of the picture. I now call the last line N. "Colors of" is defining the line the color is originally meant for. This is clean example how things might go:

Line N has 16 colors of line N
Line N-1 palette has 12 colors of line N and 4 colors of line N-1. (12 colors of these 16 colors is used, 4 are changeing)
Line N-2 palette has 8 colors of line N, 4 colors of line N-1 and 4 colors of line N-2. (12 colors of these 16 colors is used, 4 are changeing)
Line N-3 palette has 4 colors of line N, 4 colors of line N-1, 4 colors of line N-2 and 4 colors of line N-3. (12 colors of these 16 colors is used, 4 are changeing)

This should work because you should not ever need to "throw away" the colors you have selected for the line.

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

15-05-2007, 21:01

Ok, now I feel stupid...

When I tested first time how many colors you can change on one line I made a stupid mistake that caused the number to be doubled.

So the actual amount of colors that we can change on each line is only two colors. CryingCryingCrying

Here is the working (and this time tested) version of the routine:


; SCREEN 7 512 colors ondemand

	DEFB #FE    ; BASIC header.
	DEFW BEGIN
	DEFW END
	DEFW START

	ORG #D000
DATA:	EQU #A000   ; Put your pallette data in this address
	    	 ; 16 * %0RRR0BBB, %00000GGG (32 bytes of first line pallette)
	    	 ; lines * 2 * %0000CCCC, %0RRR0BBB, %00000GGG (6 bytes / line)

BEGIN:
START:

      	LD A,(#2D)
      	CP 3
      	LD A,#80
      	CALL Z,#180 ; Change to Z80 if MSX tR

	DI
 	IN A,(#AA)
 	AND #f0
 	or 8
 	OUT (#AA),A

	LD A,#90	 ; PALETTE register
	OUT (#99),A
	LD A,#91
	OUT (#99),A
AGAIN:
      	XOR A
      	OUT (#9B),A
      	LD HL,DATA
      	LD BC,#209A
      	OTIR	; First palette

	LD A,1
	OUT (#99),A
	LD A,#8F
	OUT (#99),A

WAITLINE0:
	IN A,(#99)
	RRA
	JR NC,WAITLINE0

	LD A,2
	OUT (#99),A
	LD A,#8F
	OUT (#99),A

           LD E,210	; Number of lines

WAIT:
	IN A,(#99)
	AND 32
	JP Z,WAIT
;----------------------

           INC C
           OUTI
	DEC C
	OUTI
	OUTI

	INC C
	OUTI
	DEC C
	OUTI
	OUTI

	DEC E
	JP NZ,WAIT

;----------------------

     	IN A,(#A9)
	AND 1
	JP NZ,AGAIN ; SPACE pressed?

EXIT:
	XOR A
	OUT (#99),A
	LD A,#8F
	OUT (#99),A
 	EI
	RET

END:

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

15-05-2007, 21:30

@DamageX It seems that red and blue are swapped in your routine.

By Maggoo

Paragon (1214)

Maggoo의 아바타

15-05-2007, 21:34

NYYRIKKI: Why not pre-selecting the color numbers that can be re-defined at each line to be statics ones, say only color 1,2,3,4. This way you can do just outi 8 times and only reset the color pointer once per line. Also your palette table will be 2 bytes per color instead of 3. It makes the conversion routine more complex since you'll need to re-assign colors to different pixels but allow a faster display routine and more color updates.

This old demo http://vscreen.hypercu.be/iodcolor.zip uses this method to update 4 colors/line (3 on TR) for the display of the top part of the screen.

By NYYRIKKI

Enlighted (5875)

NYYRIKKI의 아바타

15-05-2007, 23:18

I'm not sure, but I think that 2 carefully selected color changes gives better result than 4 "random" color changes. Usually lines next to each other are quite a close if we thing about colors. When I took a look of the data DamageX had created most of the changes were just "dummy changes" (change color back to same it was) If we can skip some line (line uses only for example 12 colors) we can get 4 changes done for next line.

What comes to size of color table I don't think that is important at least at the moment. We can easyly put this method to 2 bytes as well, because at the moment we have 8 unused bits.

페이지 4/9
1 | 2 | 3 | | 5 | 6 | 7 | 8 | 9