VDPENC

Page 5/13
1 | 2 | 3 | 4 | | 6 | 7 | 8 | 9 | 10

Par ARTRAG

Enlighted (6862)

Portrait de ARTRAG

17-05-2007, 11:22

I need to pass from the use of Jannone's scr2 converter to a my own algorithm for Floyd-Steinberg able to work on 8x8 blocks.
Floyd-Steinberg algorithms for colors and screen2 conversion are hard by themself and harder to be integrated, and IMHO screen 2 conversion should be embedded in dithering.
Screen 2 conversion implies large errors on colors of single pixels (due to colorclash and palette limitations).

Dithering allows to spread on adjacent pixels the errors due to color quantization, thus giving a spatial masking of the errors.
In order to make everything work, screen 2 conversion must be included in the first step of dithering, where you compute the quantization error on a single pixel to be spread on adjacent pixels.

In our case things get harder and harder wrt the standard Floyd, as adopting a color for one pixel constrains the choice on the successive points on the same line, thus the algorithm should try to optimize somehow the choice of the colors on the whole line in order to minimize the error spread on adjacent lines.

Definitely I have the feeling that what should be minimized in the choice on the two colors per 8 pixel line is not only the distortion on the current line but also the value of the errors spread on the successive line.

On msx1 we have 105 couples of colors.
we could choice the couple, by brute force search, that minimize the squared error with respect to the sum of the current line and the errors from the previous line.
Than we apply Floyd on that line having fixed the two colors, and we get the error line to be added to next line.

The draft algorithm could be like this:

1) by brute force search, find the couple of colors that minimize the squared error on line 1
2) apply Floyd on line 1 using the two colors selected above and get a error line to be added to line 2
3) by brute force search, find the couple of colors that minimize the squared error on line 2 + the error line
4) apply Floyd on line 2 using the two colors selected above and get a error line to be added to line 3
etc.

Can it work ? Does anyone have experience on dithering ?

For grey scale dithering go here
http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering

Par ARTRAG

Enlighted (6862)

Portrait de ARTRAG

18-05-2007, 00:40

new images converted on the site

Par Hecatonchire

Supporter (11)

Portrait de Hecatonchire

18-05-2007, 01:20

not sure of your choices, imho dithering and quantization should be applied on the whole image (before screen 2 conversion).

Par pitpan

Prophet (3152)

Portrait de pitpan

18-05-2007, 18:34

Here's the code for my own TGA 24 bpp conversion to TMS9918 format. No dithering! Stardard C code for any speedy computer:

/*
---------------------------------------------------------------
TMSOPT v.0.02 - Eduardo A. Robsy Petrus, 2007
---------------------------------------------------------------
 TGA image converter (24 bpp, uncompressed) to TMS9918 format
---------------------------------------------------------------
Overview
---------------------------------------------------------------
Selects the best local solution for each 8x1 pixel block
Optimization uses the following algorithm:

(a) For each pixel, RGB differences are calculated
  - All RGB channels have the same weight
  - It uses absolute error instead of squared error

(b) This error value is added for all pixels in each 8x1 block

(c) The CHR-CLR combination with lowest error rate is selected

It is a brute-force method, computationally very expensive.
Some patience and a high-clocked CPU computed is recommended.
---------------------------------------------------------------
Compilation instructions
---------------------------------------------------------------
 Tested with GCC/Win32 [mingw]:

   GCC TMSopt.c -oTMSopt.exe -O3 -s

 It is standard C, so there is a fair chance of being portable!
---------------------------------------------------------------
History
---------------------------------------------------------------
 Ages ago   - algorithm created
 16/05/2007 - first C version (RAW format)
 17/05/2007 - TGA format included, some optimization included
---------------------------------------------------------------
Legal disclaimer
---------------------------------------------------------------
 Do whatever you want to do with this code/program.
 Use at your own risk, all responsability would be declined.
 It would be nice if you credit the author, though.
---------------------------------------------------------------
*/

// Headers!

#include<stdio.h>
#include<time.h>

// Just one function for everything

main(int argc, char **argv)
{

// Vars

 FILE *file,*CHR,*CLR;
 int bc,bp,i,j,x,y,c,p,k,MAXX,MAXY;
 unsigned int score[256][512],n,total=0,done=0,size;
 char *name;
 unsigned char image[512][512][3],header[18],palette[16][3]=

// TMS9918 RGB palette - approximated 50Hz PAL values

{{0x00,0x00,0x00}, //  0 Transparent - black (not used)
 {0x00,0x00,0x00}, //  1 Black
 {0x12,0xFF,0x00}, //  2 Green
 {0x76,0xFF,0x6F}, //  3 Light green
 {0x12,0x00,0xFF}, //  4 Blue
 {0x69,0x69,0xFF}, //  5 Light blue
 {0xA1,0x10,0x10}, //  6 Dark red
 {0x00,0xFF,0xFC}, //  7 Cyan
 {0xFF,0x00,0x00}, //  8 Red
 {0xFF,0x80,0x80}, //  9 Light red
 {0xFF,0xEA,0x00}, // 10 Yellow
 {0xFF,0xFB,0x80}, // 11 Light yellow
 {0x1D,0xA8,0x02}, // 12 Dark green
 {0xFF,0x00,0xFC}, // 13 Magenta
 {0xCC,0xCC,0xCC}, // 14 Light gray
 {0xFF,0xFF,0xFF}};// 15 White

// Get time

 clock();

// Application prompt

 printf("TMSopt v.0.01 - TGA 24bpp to TMS9918 converter\nCoded by Eduardo A. Robsy Petrus, 2007\n");
// Test if only one command-line parameter is available

 if (argc==1)
 {
  printf("Syntax: TMSopt [file.tga]\n");
  return;
 }

// Open source image (TGA, 24-bit, uncompressed)

 if ((file=fopen(argv[1],"rb"))==NULL)
 {
  printf("cannot open %s file!\n",argv[1]);
  return;
 }

// Read TGA header

 for (i=0;i<18;i++) header[i]=fgetc(file);

// Check header info

 for (i=0,n=0;i<12;i++) n+=header[i];

 if ((n!=2)||(header[2]!=2)||(header[17])||(header[16]!=24))
 {
  printf("Unsupported file format!\n");
  return;
 }

// Calculate size

 MAXX=header[12]|header[13]<<8;
 MAXY=header[14]|header[15]<<8;

 size=((MAXX+7)>>3)*MAXY;

// Check size limits

 if ((!MAXX)||(MAXX>512)||(!MAXY)||(MAXY>512))
 {
  printf("Unsupported size!");
  return;
 }

// Load image data

 for (y=MAXY-1;y>=0;y--)
  for (x=0;x3;y++)
  for (x=0;x<(MAXX+7)>>3;x++)
   for (j=0;j<8;j++)

// Generate alternatives

    {
     bp=0;bc=0;
     score[0][0]=-1;
     for (p=0;p<256;p++)
      for (c=0x12;c<256;c++)
       if (c>>4>4:c&0x0f][k]-image[x<<3|i][y<<3|j][k]);
         n<<=1;
        }

// Keep best solution found

        if (score[p][c]4:bc&0x0f][k];
      n<<=1;
     }

// Update status counter
   if (done*100/size<(done+1)*100/size) printf("\b\b\b%2i%%",100*done/size);
   done++;

   }

// Conversion done

 printf("\b\b\bOk   \n");

// Generate new name

 name=malloc(0x100);
 argv[1][strlen(argv[1])-4]=0;
 strcpy(name,argv[1]);
 strcat(name,"_tms.tga");

// Save file header

 file=fopen(name,"wb");

 for (i=0;i<18;i++) fputc(header[i],file);

// Save image data

 for (y=MAXY-1;y>=0;y--)
  for (x=0;x

You can see the result below: works fine for plain-coloured images and it is pure crap for photographic images. For photographic images, dithering is a must when only 15 fixed colours are available.

www.robsy.net/tmsopt.png

Par ARTRAG

Enlighted (6862)

Portrait de ARTRAG

18-05-2007, 19:01

You can optimize your inner code a lot!!

1) why do you store all the tests situation in matrix score[][] ?
you do not need it: simply evalue the current score, if it is better than the previous keep it, otherwise go haed

2) why do you compute all the color/pattern combinations?
your program tests all the 105*256=26880 combinations....
you do not need it.

do a outer loop on the 105 color couples
like:
for (c1=1;c1<15;c1++)
for (c2=c1+1;c2<15;c2++)
{
etc.
}

In the inner loop do not scan all the 256 patterns!
do this :
compute the distance of the color of each point from c1, (costs 8 diffences + 8 products if you use squared errors)
compute the distance of the color of each point from c2, (costs 8 diffences + 8 products if you use squared errors)

select the minimum between the two sets of values for each point. (costs 8 comparisons)
the sum of the minima is the current score (costs 7 sums)
the results of your comparisons forms the current pattern p (the best given c1 and c2)

This cuts the time a lot: instead of doing 256 tests (like you do now)
you compute only 8+8 differences, 8 comparisons and 7 sums (+ 16 producs if you use squared errors)

Smile

Par Patsie

Master (254)

Portrait de Patsie

18-05-2007, 19:09

pitpan wrote:Here's the code for my own TGA 24 bpp conversion to TMS9918 format. No dithering! Stardard C code for any speedy computer:
It could use the <string.h> and <malloc.h> headers for the strlen/strcpy/strcat and malloc functions.

Par AuroraMSX

Paragon (1902)

Portrait de AuroraMSX

18-05-2007, 20:07

pitpan wrote:Here's the code for my own TGA 24 bpp conversion to TMS9918 format. No dithering! Stardard C code for any speedy computer:
It could use the <string.h> and <malloc.h> headers for the strlen/strcpy/strcat and malloc functions.
That'll cost ya one beer

Par Patsie

Master (254)

Portrait de Patsie

18-05-2007, 20:30

pitpan wrote:Here's the code for my own TGA 24 bpp conversion to TMS9918 format. No dithering! Stardard C code for any speedy computer:
It could use the <string.h> and <malloc.h> headers for the strlen/strcpy/strcat and malloc functions.
That'll cost ya one beer

Okay, I'll bite...
"why?"

Par ARTRAG

Enlighted (6862)

Portrait de ARTRAG

18-05-2007, 20:34

Can anyone send me a TGA file ?
It seems that it is not supported by any of the standard editors /viewers from windows

Par Patsie

Master (254)

Portrait de Patsie

18-05-2007, 20:40

Can anyone send me a TGA file ?
It seems that it is not supported by any of the standard editors /viewers from windows

I recommend you use ImageMagick to convert any picture file to any other picture file

Page 5/13
1 | 2 | 3 | 4 | | 6 | 7 | 8 | 9 | 10