Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (804)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Converting RGB images to a master palette  (Read 5928 times)
0 Members and 1 Guest are viewing this topic.
Offline Archive
« Posted 2016-08-20 18:05:40 »

Hi, so I have a master palette of 256 colors. I want to convert a loaded RGB image to use this palette. Essentially, clamping the colors in the RGB image to the closest color it can find in the palette. I've tried for a few hours now to brute force it but it takes too long and produces vastly incorrect results. Does anyone have a solution?

Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #1 - Posted 2016-08-20 19:33:54 »

did you try hashing yet ? i mean something like
int idx = int(luminance(color.rgb) * 255)
- for a gray-scale ramp.

anyway, i guess after brute force some sort of hashing would do the trick.
Offline ddyer
« Reply #2 - Posted 2016-08-20 19:41:03 »

There are different solutions depending on if the palette is fixed or flexible.  

You can do pretty well by taking a color distance metric and selecting the nearest palette color. Keep track
of the RGB error and add it into the next pixel, so the average selected pixel stays near the original RGB colors.

If you can choose your palette, then histogram your colors, and use a peano curve to walk the histogram
to group histogram colors to select palette colors, and make the palette colors conform to the centroid of
the corresponding histogram boxes.  This can produce magically good pictures even with very few colors.

Of course, doing all this efficiently is difficult to do yourself, and I have no idea what commercial color reduction
programs will work well for you.   Photoshop is not bad.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #3 - Posted 2016-08-20 21:01:00 »

I guess a reverse lookup table would kinda work. If you have 256*256*256 different colors possible, you can simply create a table for all those combinations (16MB). I guess doing some kind of approximation to reduce the size of the table would be a good idea though. xd

Myomyomyo.
Offline richierich
« Reply #4 - Posted 2016-08-20 23:04:23 »

^ Yes that would also reduce lookup misses a lot so fewer times to calculate colour distance. And if the image is getting reduced to 256 colours anyway it sounds like it could stand some simple posterizing first, like truncate the R, G, B each to the nearest multiple of 8 or 16.

The OP question said that brute forcing wasn't working and producing incorrect results. I was just curious what the brute forcing consisted of? Also how accurate the results have to be.
Offline Archive
« Reply #5 - Posted 2016-08-21 00:42:22 »

Thanks everyone Smiley richierich, the brute force version was when I converted all the RGB colors from the image to LAB format since I read that that format makes distance calculations simple and correct.

Offline CoDi^R
« Reply #6 - Posted 2016-08-22 08:47:17 »

I've been experimenting with color distances a while back since we are using some kind of master palette ourselves. Right now we don't use them, but do exact RGB to palette matching (meaning, color distance must be == 0 all the time) and output warnings/errors if no match is found by choice of our pixel artists (they produce art *using* our palette, and want to see if they are using a color not available in the palette), but I kept the utility functions around just in case.

I tried using both RGB and HSV color spaces. In our case, results were pretty much the same. Of course, the max distance depends a lot on the palette you use.

Also, I didn't invent these formulas, but I don't remember the references right now.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
   // note: returns the square distance, avoiding the sqrt()
   public static float distanceSqrRGB(float r0, float g0, float b0, float r1, float g1, float b1) {
      float r = 0.30f * (r0 - r1);
      float g = 0.59f * (g0 - g1);
      float b = 0.11f * (b0 - b1);

      return r * r + g * g + b * b;
   }

   public static float distanceHSV(float r0, float g0, float b0, float r1, float g1, float b1) {
      float avgHue = Math.abs(r0 - (r0 + r1) * 0.5f);
      float avgSaturation = Math.abs(g0 - (g0 + g1) * 0.5f);
      float avgValue = Math.abs(b0 - (b0 + b1) * 0.5f);

      return avgHue * 0.4750f + avgSaturation * 0.2875f + avgValue * 0.2375f;
   }

Robotality - steamworks4j - @code_disaster - codi^r @ #java-gaming
Offline Archive
« Reply #7 - Posted 2016-08-22 14:16:52 »


Thank you! This will help a ton!

Offline richierich
« Reply #8 - Posted 2016-08-23 10:07:52 »

1  
2  
3  
4  
5  
6  
7  
   public static float distanceSqrRGB(float r0, float g0, float b0, float r1, float g1, float b1) {
      float r = 0.30f * (r0 - r1);
      float g = 0.59f * (g0 - g1);
      float b = 0.11f * (b0 - b1);

      return r * r + g * g + b * b;
   }

These magic numbers are fascinating! I've been reading Wikipedia about colour spaces for a couple of hours and still don't quite understand what's going on.

I thought humans were particularly sensitive to colours near to green (ancestors living in trees), so would have expected changes in the G channel of RGB to be especially noticeable, if anything. But the weightings in this distance formula show the opposite, with G needing to be magnified by a factor of more than 5 compared to the B to create the equivalent apparent distance. Atm my best attempt to understand this is that in addition to mid-frequency sensitivity our eyes are *even more* sensitive to changes in brightness, and especially at the dark end (predators come out at night!) So the green component of RGB, featuring disproportionately in lighter colours (middle of the spectrum) actually contains less difference information because darker colours are the easiest to distinguish. The diagrams on Wikipedia show a huge area of green chromaticity (in LAB terms) getting squashed down into the green corner of the RGB model, which seems to support that but I really don't know! Cheesy

Re the function gut feeling is it might be faster if it could somehow all be done with the integer representations of the RGB, but who knows what the profiler would say. Anyway maybe performance isn't really an issue now if at least you're getting accurate results?

Edit: theagentd's gamma correction article&tutorial is interesting and relevant. It seems to have no appreciate button so I'll appreciate here Smiley
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2016-08-23 20:03:02 »

Don't forget you can use dithering to approximate colors (in groups of pixels).

Here I created code to approximate any RGB input in the EGA16 palette (obviously only 16 colors)
http://www.java-gaming.org/topics/tinygame-resources/22266/msg/184436/view.html#msg184436




If you add animation, you can dither in the 3rd dimension (time).
Click to Play
I remind you, these are just 16 colors, evenly spaced out colors in the RGB color space, which means I probably use only 8-12 per frame in this specific image.

Just run this JAR for yourself:
http://indiespot.net/files/ega-dithering.jar

It should be relatively easy to use this concept to match an arbitrary palette.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Archive
« Reply #10 - Posted 2016-08-23 23:06:34 »

..
Whoa! That looks awesome! Definitely will look into this. Thanks!

EDIT: One thing I can't make my mind up about is the following:

Should I make a master palette for the engine or allow each texture to have its own palette?
Keep in mind that this palette is a 256x64 table of 256 hues and 64 shades of the hue.

It's essentially a tradeoff between memory and color depth.

Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2016-08-24 18:43:46 »

Why is memory such a constraint?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Archive
« Reply #12 - Posted 2016-08-24 18:59:49 »

Why is memory such a constraint?
Just for memory locality. I'd rather have the texture mapper point to one area in memory rather than a bunch of different areas haha.
By the way, I implemented your thing (without dithering) with a 256*64 color table Smiley. I ended up using a master palette and the results are surprisingly not that bad.



Up next is to do gamma correction Smiley Thank you so much Riven!

Pages: [1]
  ignore  |  Print  
 
 

 
Riven (581 views)
2019-09-04 15:33:17

hadezbladez (5511 views)
2018-11-16 13:46:03

hadezbladez (2403 views)
2018-11-16 13:41:33

hadezbladez (5773 views)
2018-11-16 13:35:35

hadezbladez (1225 views)
2018-11-16 13:32:03

EgonOlsen (4663 views)
2018-06-10 19:43:48

EgonOlsen (5683 views)
2018-06-10 19:43:44

EgonOlsen (3198 views)
2018-06-10 19:43:20

DesertCoockie (4095 views)
2018-05-13 18:23:11

nelsongames (5115 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!