## Find the best 8 bit palette for an RGB image

General FreeBASIC programming questions.
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Find the best 8 bit palette for an RGB image

I believe this is a popular problem. Many programs do it, but it seems each does it their own way and the results are not always satisfying. Indexed graphics modes are not very used today, but 8 bit indexed images could be considered a very effective and simple way of lossy image compression, so I've been researching on it.

The problem: given a true colour RGB image of a certain size, possibly containing tens of thousands of colours or more, find the most suitable 256-colour palette in the shortest amount of time so that an approximation to the image made by indexing the values in the palette looks mostly the same as the original.

I've thought of the following possible solutions:

1 - Scan the image, save the first 256 distinct colours to the palette, then approximate all other colours with those. Quick, but dirty. Some images will look awful.
2 - Use a fixed palette that contains a little bit of everything. Quickest, result is often better than with option one, but the difference is always noticeable.
3 - Use a library of different fixed palettes (maybe 16 of them), try them each one by one and choose the one that looks better. This can be measured by adding the "distances" between the pixels RGB values and the resulting pixel colours for every point in the image, for each palette (distance being square root of the sum of the squares of the differences of R, G and B... or simplified, the sum of absolute values of the three differences; same thing, for the sake of ordering). This is a little bit better.
4 - Define a number of "buckets". One for white, another one for black and then for red, green, blue, magenta, cyan and yellow. Count the number of pixels that approximate better to each of these colours. Create a palette with more points for the most common ones. Yes, but how?
5 - Scan the image to find the most repeated colour and add it to the palette. Then scan again to look for the next and so on. Other colours will be approximated. This is good for very simple images, but photos and like have almost as many colours as pixels, so almost all colours appear only one in the image. It doesn't work.
6 - Scale down the image so that it contains fewer than 256 pixels and use cubic interpolation. Add the pixel colours to the palette. Then approximate the actual pixel colours with those colours. This sounds clever on first thought, but doesn't work well. brighter and darker colours are not well represented in the palette. Everything is "too average".
7 - Finally, I've thought of this idea. Seems great. Only problem is that it's too slow: Start with a palette that contains only pure black, one colour. Then iterate. On each iteration, scan the image looking for the pixel whose colour is farthest from all the colours currently in the palette. That is, add all distances. After the scan, add this colour to the palette and clear it from the image. Continue until either 256 colours have been added to the palette or the image has no more colours. Then approximate each pixel with the closest colour in the generated palette. The problem with this is that the whole image has to be scanned for each colour. In my computer, for an image about 640x480, this is taking about 10 seconds. Maybe if the code is optimised, I get it a little better. But I know procedures exist that can solve this in 3 to 5 seconds on a 386, because I had programs that did it in the 90s.

Any ideas? Anybody knows a better one?
dafhi
Posts: 1258
Joined: Jun 04, 2005 9:51

### Re: Find the best 8 bit palette for an RGB image

a worthy challenge :-)
dodicat
Posts: 5984
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Find the best 8 bit palette for an RGB image

step 1
get the 256 colours from 8 bit screen to 32 bit values.

step 2
treat r,g,b as a point in 3D space.

step 3
The distance between colours is the distance between their r,g,b values as points in 3D space.

step 4
Get the closest distance and you get the closest colour.

Code: Select all

`'8 bit to 32 bitSub set(clr() as ulong)   ReDim As ULong tmp(101*101)for i as integer = 0 to 255   ScreenRes 100,100,8,,-1   Dim As Any Ptr im=ImageCreate(100,100,,8)   Paint im,(5,5),i   BSave("tmp.bmp",im)   ScreenRes 100,100,32,,-1   BLoad("tmp.bmp",@tmp(0))    clr(i)=tmp(50)   ImageDestroy im:im=0Next iKill "tmp.bmp"End Subdim as ulong clr(255)set(clr()) 'set colours 0 to 255 8 bit into 32 bit.type pt  'simulate 3D spaceas single x,y,zend typedim shared as pt a(255)'set colours 0 to 255 as rgb (vectors)for n as long=0 to 255    '                  red                            green                       blue        a(n)=type(Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)))next    function closest(c() as ulong,v as ulong) as ulong    dim as ulong res     #define dist(p1,p2) (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) + (p1.z-p2.z)*(p1.z-p2.z)     'get r,g,b of v    dim as pt pv=type(Cptr(Ubyte Ptr,@v),Cptr(Ubyte Ptr,@v),Cptr(Ubyte Ptr,@v))    dim as single dt=1e20    for n as long=0 to 255        var distance=dist(a(n),pv)        if dt> distance then dt = distance:res=c(n) 'catch the smallest    next n    return resend functionscreen 19,32'create an image with circlesdim as ulong coldim as any ptr i=imagecreate(300,600,0)for n as long=0 to 2000    circle i,(rnd*300,rnd*600),2+rnd*20,rgb(rnd*255,rnd*255,rnd*255),,,,fnextput(0,0),i,psetdraw string(10,2),"rgb colours"'second image to hold the 256 coloursdim as any ptr im2=imagecreate(300,600,0)for x as long=0 to 299    for y as long=0 to 599        col=closest(clr(),point(x,y,i))        pset im2,(x,y),col    nextnextput(400,0),im2,psetdraw string(400,2),"256 colours"sleepimagedestroy iimagedestroy im2 `
dafhi
Posts: 1258
Joined: Jun 04, 2005 9:51

### Re: Find the best 8 bit palette for an RGB image

I did a rgb(rnd*255,0,0) on your circles, and it looks like the 8 bit pal has 4 shades of red. Which looks surprisingly good tbh.

But what I was looking to do in my previous attempts, and probably what xlucas wants as well, is a tailored palette.
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Re: Find the best 8 bit palette for an RGB image

Dodicat: Yes, that's the easy part. It's not what I'm trying to do. I am not trying to adapt a 32bit RGB image to a specific palette. I'm trying to find the best palette to convert the 32bit image to 8bit indexed.

Formally, what I am trying to do is find any set of 256 RGB colours, composed each of a red, a green, and a blue component 8 bit each (alpha channel not to be considered) for a given image whose pixels are 24 bit deep (that is, the same structure as that of the palette colours), so that the total sum of all colour distances (defined like we both described, as a standard 3D distance, or square root of the sum of the squares of the differences of each component) for all pixels between the source image and the resulting 8bit indexed image is minimum.

I understand that squaring three times and then getting a square root is a slow process and in general, so what I do is optimise this. Since both square root and square power are strictly growing functions, I use the sum of the absolute values of the differences instead because, while the result will be very different, the order of the distances will be the same and the calculation will be a lot faster (perhaps 10 times). But that's just an optimisation. We can just reason making as if we were going to perform actual distance measuring.

Dafhi: Yes, I want the best palette for the image, not adapting the image to a given palette.
dodicat
Posts: 5984
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Find the best 8 bit palette for an RGB image

This code was too slow,
Superceded below.
Last edited by dodicat on Sep 25, 2017 15:51, edited 1 time in total.
bluatigro
Posts: 598
Joined: Apr 25, 2012 10:35
Location: netherlands

### Re: Find the best 8 bit palette for an RGB image

there are several options :

calculate image to grayscale
result : no colors

calculate 8r8g8b to 2r2g2b
result : 4 shades / color

1 count colors
if <= 255 ones you are done
2 sort colors on times there
take the most 255 ones in palete
problem :
wat do i do whit the lesser ones
dodicat
Posts: 5984
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Find the best 8 bit palette for an RGB image

The 256 colours constituting 0 to 255 on an 8 bit screen give a good range for 32 bits.

Palette get using seems to get poor results.
However, it is an interesting topic, I am sure there will be other ideas put forward.
You should code up yours bluatigro, and let's have a look.
Last edited by dodicat on Sep 25, 2017 15:52, edited 1 time in total.
dodicat
Posts: 5984
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Find the best 8 bit palette for an RGB image

Here is the simplest of my tries, yet the most effective.
Simply get 256 colours from the image pointer at regular intervals.
Colours shown on the console.
Bitmap option at the top of the code.

Code: Select all

`#include "crt.bi"#include "file.bi"dim as string file="bob.bmp"type pt  'simulate 3D spaceas single x,y,zend typedim shared as pt a(255)redim shared as ulong clr(255)function spread256(i as ulong ptr) as long 'equidistant points    dim as integer w,h,ctr    imageinfo i,w,h    dim as long sz=w*h    for n as long=0 to sz step sz/256        if ctr>255 then exit for      clr(ctr)=i[n]      ctr+=1  next  return 0    end function    function closest(clr() as ulong,v as ulong) as ulong    dim as ulong res     '#define dist(p1,p2) (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) + (p1.z-p2.z)*(p1.z-p2.z)     #define dist(p1,p2) abs(p1.x-p2.x)+abs(p1.y-p2.y) + abs(p1.z-p2.z)     'get r,g,b of v    dim as pt pv=type(Cptr(Ubyte Ptr,@v),Cptr(Ubyte Ptr,@v),Cptr(Ubyte Ptr,@v))    dim as single dt=1e20    for n as long=0 to 255        var distance=dist(a(n),pv)        if dt> distance then dt = distance:res=clr(n) 'catch the smallest    next n    return resend functionfunction GetBmpSize(bmp as string,byref w as long,byref h as long) as long    dim as long f = FreeFile()    if fileexists(bmp) then    open bmp for binary as #f    get #f, 19,w    get #f, 23,h    close #f    return w*h   else    print bmp; "  not found ... using degault image"    return 0    end ifend function   '===================== bitmap  ==================screen 20,32dim as ulong coldim as long x,ydim as any ptr i,im2var v=getbmpsize(file,x,y)if v then    i=imagecreate(x,y)    bload file,i    im2=imagecreate(x,y)clsput(0,50),i,psetdraw string(10,2),"rgb colours  "spread256(i)'print to consoleputs "Frequency             rgb colours"for n as long=0 to ubound(clr)   puts str((n)) + "                " + str(Cptr(Ubyte Ptr,@clr(n)))+"  " +str(Cptr(Ubyte Ptr,@clr(n)))+"   "+str(Cptr(Ubyte Ptr,@clr(n)))next'set colours  as rgb (vectors)for n as long=0 to ubound(clr)    '                  red                            green                       blue        a(n)=type(Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)))nextfor xx as long=0 to x-1    for yy as long=0 to y-1        col=closest(clr(),point(xx,yy,i))        pset im2,(xx,yy),col    nextnextput(500,50),im2,psetdraw string(500,2),str(ubound(clr)+1) + " colours"    else'======================== no bitmap ======================== i=imagecreate(300,600,0)for n as long=0 to 50000    circle i,(rnd*300,rnd*600),2+rnd*10,rgb(rnd*200,0,rnd*5),,,,fnextclsput(0,50),i,psetdraw string(10,2),"rgb colours,  "' &totspread256(i)'print to consoleputs "Frequency             rgb colours"for n as long=0 to ubound(clr)   puts str((n)) + "                " + str(Cptr(Ubyte Ptr,@clr(n)))+"  " +str(Cptr(Ubyte Ptr,@clr(n)))+"   "+str(Cptr(Ubyte Ptr,@clr(n)))next'set colours 0 to 255 as rgb (vectors)for n as long=0 to 255    '                  red                            green                       blue        a(n)=type(Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)),Cptr(Ubyte Ptr,@clr(n)))next'second image to hold the 256 colours im2=imagecreate(300,600,0)for x as long=0 to 299    for y as long=0 to 599        col=closest(clr(),point(x,y,i))        pset im2,(x,y),col    nextnextput(500,50),im2,psetdraw string(500,2),"256 colours"end ifsleepimagedestroy iimagedestroy im2   `
vdecampo
Posts: 2982
Joined: Aug 07, 2007 23:20
Location: Maryland, USA
Contact:

### Re: Find the best 8 bit palette for an RGB image

I would resample the 888 RGB 24bit to 323 RGB 8Bit. At work right now but I could give it a try this evening.

-Vince
xlucas
Posts: 268
Joined: May 09, 2014 21:19
Location: Argentina

### Re: Find the best 8 bit palette for an RGB image

Bluatigro: That is a clever idea. The problem, when I wanted to try something similar, is that most images you can download from the web, say, random images, both drawings and photos, contain colours in the order of tens of thousands to around a million. This means repetition of colours tends to be very low. Most colours are there only once. What I mean is, while only a few colours are "frequent", if you add all the pixels whose colour is there only once, you'll see they represent the image better than the ones that do have high frequency. Yet, if you try it and optimise it your own way, you may find tricks I haven't found.

Dodicat: I tried your code and I changed the colours of the circles to be more random and still seems to give nice results. I'm currently at work, so when I finish, I'll give it a closer inspection. My guess is that your method must be most effective with images that have many colours, but don't use gradients. Still, there is a chance even they work well because you pick equally spaced pixels, so the odds are that few of them will fall on the same small gradient, which should maximise "colour diversity". Also, your code is reasonably fast :)

Vince: What you suggest works. I've already done that. It's the fastest way to get a decent palette, but it doesn't give optimal results, especially for photos. Instead of 323, I'd suggest 332 because the human eye can detect green shades better than red shades and red shades better than blue shades. But even that won't be enough. Suppose you have an image that have tons of greens and blues, but little to no reds (a field in the day), then it would make sense for that picture to use 143 instead. Also, some pics may use a lot of, say, red, but all reds are average, not too dark, not too bright. Then lower and higher values should not be assigned. Just thinking.

I wrote the following code, but I've made a mistake at some point and it goes out with segmentation fault unless I disable the part that starts drawing the new image. It's incomplete, because it's not returning a palette. It was supposed to return the 8bit image. I'll modify it and post it again, but so far, here it is:

Code: Select all

`Function Image32to8(img As Any Ptr, pal As Any Ptr) As Any Ptr   Dim As Short i, j, n   Dim As Integer w, h, bypp, spitch, dpitch   Dim img2 As Any Ptr   Dim As UByte Ptr dstart, dlin   Dim As ULong Ptr sstart, slin   Dim bpal As UByte Ptr   Dim col(0 To 255) As ULong, test As ULong   Dim maxdif As LongInt, maxcol As ULong   Dim As UByte r1, r2, g1, g2, b1, b2   Dim curcol As UByte = 0      bpal = pal      ImageInfo img, w, h, bypp, spitch, sstart   If bypp <> 4 Then Return 0      img2 = ImageCreate(w, h, 0, 8)   ImageInfo img2, , , , dpitch, dstart      'Black colour always pushed into the palette   col(0) = &HFF000000      Do      slin = sstart      dlin = dstart      maxdif = 0      For j = 0 To h - 1         slin += spitch         dlin += dpitch         For i = 0 To w - 1            test = slin[i]                        If test = col(curcol) Then               slin[i] = &HFF000000               'dlin[i] = curcol   '<-- This thing is acting up, so I've commented it out            ElseIf test <> &HFF000000 Then               Dim dif As LongInt                              dif = 0               r1 = (test ShR 16) And 255               g1 = (test ShR 8) And 255               b1 = test And 255               For n = 0 To curcol                  r2 = (col(n) ShR 16) And 255                  g2 = (col(n) ShR 8) And 255                  b2 = col(n) And 255                  dif += Abs(r2 - r1) + Abs(g2 - g1) + Abs(b2 - b1)               Next n               If dif > maxdif Then                  maxdif = dif                  maxcol = test               End If            End If         Next i      Next j            If maxdif = 0 Then Exit Do      curcol += 1      col(curcol) = maxcol            Locate , 1      Print curcol;   Loop Until curcol = 255      Return img2End Function`

What this thing is doing is what I described at the end of my last message. It rescans the image over and over in search for the colour that's the furthest from all present colours in the palette. I'll work more on it and repost it. I expect it to be pretty good, but slow, and will have one problem: for images that contain noise, it will concentrate on the noise and the image itself will lose quality.
BasicCoder2
Posts: 3403
Joined: Jan 01, 2009 7:03

### Re: Find the best 8 bit palette for an RGB image

I added two lines to the end of dodicat's program to save the two images.

Code: Select all

`sleepbsave "image1.bmp",ibsave "image2.bmp",im2imagedestroy iimagedestroy im2`

Then I used this program to compare the changes by tapping the space bar.
Indeed I think this is the easiest way to compare the difference between two image.
Perhaps an algorithm could use the same test and correct for the largest variations found.

Code: Select all

`screenres 300,600,32dim as any ptr image1,image2image1 = imagecreate(300,600)image2 = imagecreate(300,600)bload "image1.bmp",image1bload "image2.bmp",image2do    screenlock    cls    put (0,0),image1    screenunlock    while inkey="":wend    while inkey<>"":wend    screenlock    cls    put (0,0),image2    screenunlock    while inkey="":wend    while inkey<>"":wendloop until multikey(&H01)`

Also I would suggest that the human visual system could be taken into account for grouping rgb values that we find different vs. those that look much the same?
The color stripes in the rainbow are created in the brain as a result of how we group the color spectrum, they do not actually exist in the rainbow itself which is a continuous change in color (wave length).
Another thought is that the darker the color the less important it is. Two dark colors may look more alike than a brighter version of the same two colors?
.
Last edited by BasicCoder2 on Sep 25, 2017 21:08, edited 2 times in total.
D.J.Peters
Posts: 7838
Joined: May 28, 2005 3:28

### Re: Find the best 8 bit palette for an RGB image

I self use a RGB 3:3:2 256 color table and dithering.

Joshy

Left full RGB right only 256 colors :-) Code: Select all

`' Copyright D.J.Peters (Joshy) dim shared as integer rtab(1,15) = { _  {-16,  4, -1, 11,-14,  6, -3,  9,-15,  5, -2, 10,-13,  7, -4,  8}, _  { 15, -5,  0,-12, 13, -7,  2,-10, 14, -6,  1,-11, 12, -8,  3, -9}} dim shared as integer gtab(1,15) = { _  { 11,-15,  7, -3,  8,-14,  4, -2, 10,-16,  6, -4,  9,-13,  5, -1}, _  {-12, 14, -8,  2, -9, 13, -5,  1,-11, 15, -7,  3,-10, 12, -6,  0}} dim shared as integer btab(1,15) = { _  { -3,  9,-13,  7, -1, 11,-15,  5, -4,  8,-14,  6, -2, 10,-16,  4}, _  {  2,-10, 12, -8,  0,-12, 14, -6,  3, -9, 13, -7,  1,-11, 15, -5}} ' create RGB 3:3:2 Palette (rrrgggbb) sub Palette332()   dim as integer i,r,g,b   for i = 0 to 255     r=(((i shr 5) and &H07) * 255) / 7     g=(((i shr 2) and &H07) * 255) / 7     b=(((i shr 0) and &H03) * 255) / 3     palette i,r,g,b   next end sub 'r,g,b dithering to rrrgggbb sub dither332(byval x as single, _              byval y as single, _              byval r as integer, _              byval g as integer, _              byval b as integer)   dim as integer i,j   i=int(y) mod 16:j=int(x) mod 2   r+=rtab(j,i)  g+=gtab(j,i)  b+=btab(j,i)   if (r > 255) then     r=224 ' &HE0   elseif r>0 then     r=r and &HE0   else     r=0   end if   if (g > 255) then     g=28 ' &HE0 shr 3   elseif g>0 then     g=(g and &HE0) shr 3   else     g=0   end if   if (b > 255) then     b=3 ' &HC0 shr 6   elseif b>0 then     b=(b and &HC0) shr 6   else     b=0   end if   i=r or g or b   pset(x,y),i end sub union RGB32  type field=1    as ubyte b,g,r,a  end type  as ulong col32end union''' main dim as RGB32   cdim as integer pitchdim as ulong ptr pixels,rowScreenRes 360,520,32var RGBimg = imagecreate(360,520)imageinfo RGBimg,,,,pitch,pixelspitch shr=2 ' bytes to ulongbload "test.bmp",RGBimgput (0,0),RGBimg,psetScreenRes 360,520,8Palette332row=pixelsfor y as integer = 0 to 519  for x as integer = 0 to 359    c.col32=row[x]    dither332(x,y,c.r,c.g,c.b)   next  row+=pitchnextbsave "256color.bmp",0sleep`
UEZ
Posts: 337
Joined: May 05, 2017 19:59
Location: Germany

### Re: Find the best 8 bit palette for an RGB image

The more interesting challenge is to convert an image to 16 colors. When I have some free time I will port my AutoIt code to FreeBasic. The result isn't that bad compared to e.g. IrfanView or to other methods (median cut color quantization, Wu color quantizer, etc.).

@D.J.Peters (Joshy): your code does not use the full 256 color spectrum - only 203 colors. ;-)

Sneak preview:

16 colors / 255 colors / 43344 colors   So long.
Last edited by UEZ on Sep 25, 2017 21:50, edited 1 time in total.
BasicCoder2
Posts: 3403
Joined: Jan 01, 2009 7:03

### Re: Find the best 8 bit palette for an RGB image

D.J.Peters wrote:I self use a RGB 3:3:2 256 color table and dithering.

Horizontal lines appear?
Dodicat's version of your image produces color contours.
.