Trying to Create a Palette of 14-16 Million Colors

[Forkanion]

Trying to use the selective palette plugin tool on an image with 16.74 million pixels, and around 90% of them are unique colors. My PC has a 3060ti and an i9-11900K CPU, and the program stops responding when I use the selective palette tool, but I feel like it'll work if I give it some hours. Is this possible? Is it a matter of time or my PC's ability? 

[BoltBait]

Palette files in Paint.NET are limited to 96 colors.

[Forkanion]

I actually managed to save it as a palette using the "MakePalette" tool, and it is a 13830KB .txt file. I just now need to use the SelectivePalette tool to apply it to another image I want to convert, it and so far it seems to really in fact be a matter of time rather than my PC or Paint.NET's program performance.

[NinthDesertDude]

Might be another way to go about accomplishing your goal, depending on what it is. I don't know what you need a palette of a million colors for, but if you just want to reduce the total color range or something to that effect, take a look at the built-in Posterize effect

[Forkanion]

Converting an image into purple-scale, the palette involves colors from (respectively) RGB 64 0 255, to RGB 192 0 255, and then THAT gradient has a black fade and white fade on it, and then THAT gradient fades into gray by multiplying those colors by 256. I'd send the image here but it exceeds the limit.

[Reptillian]

I have something for you. You can do 'colormap 0' in gmic.

 

 

The right image is all of the unique color found in the first image with the colormap command. I know this is a paint.net thread, but this solution is so much faster for your need and it is pretty specific. I will refer you to discuss.pixls.us if you find this is a good starting point.

Edited November 22, 2021 by Reptillian

[Forkanion]

21 minutes ago, Reptillian said:

I have something for you. You can do 'colormap 0' in gmic.

 

 

The right image is all of the unique color found in the first image with the colormap command. I know this is a paint.net thread, but this solution is so much faster for your need and it is pretty specific. I will refer you to discuss.pixls.us if you find this is a good starting point.

Wow, that seems very helpful. How would I be able to use that to apply it to an image and use it as its palette? 

[Reptillian]

1 hour ago, Forkanion said:

Wow, that seems very helpful. How would I be able to use that to apply it to an image and use it as its palette? 

 

That's why I refer you to discuss.pixls.us as this is not a gmic forum. In G'MIC cli, you do '$ i image.png colormap 0' to create a palette of unique colors. There's also CLUT-mapping which allows you to map color from a image onto another image.

[MJW]

3 hours ago, Reptillian said:

The right image is all of the unique color found in the first image with the colormap command.

 

To see that for 14 million distinct colors, I suggest a wide monitor.

 

Perhaps the gmic colormap command does allow recoloring an image with a 14-16 million entry palette, but color me skeptical. Which is to say, while I believe there are algorithms that could efficiently do that, time-wise, as far as I know, they're quite non-obvious, and require lots of memory.

 

If the colormap command can truly quickly recolor an image to such a large palette, I would be very interested to know the algorithm it uses.

 

The selective palette plugin is slow, because for each color in the image it has to do 14-16 million color comparisons to find the best match. Obviously, that takes a bit of time.

[Reptillian]

1 hour ago, MJW said:

 

To see that for 14 million distinct colors, I suggest a wide monitor.

 

Perhaps the gmic colormap command does allow remapping an image to a 14-16 million color palette, but I'm a bit skeptical. Which is to say, while I believe there are algorithms that could efficiently do that, time-wise, as far as I know, they're quite non-obvious, and require lots of memory.

 

If the colormap command can truly quickly remap an image to such a large palette, I would be very interested to know the algorithm it uses.

 

The selective palette plugin is slow, because for each color in the image it has to do 14-16 million color comparisons to find the best match. Obviously, that takes a bit of time.

 

The built-in colormap command is pretty slow for millions of color. I did however found an algorithm that may work. This is my test:

 

C:\Windows\System32>gmic 4096,4096,1,3,vector(#3,u(255),u(255),u(255)) round. tic rep_fast_algorithm toc
[gmic]-0./ Start G'MIC interpreter.
[gmic]-0./ Input image at position 0, with values 'vector(#3,u(255),u(255),u(255))' (1 image 4096x4096x1x3).
[gmic]-1./ Round values of image [0] by 1 and nearest rounding.
[gmic]-1./ Initialize timer.
[gmic_math_parser] da_size(#-1) = 10595667
[gmic]-2./ Elapsed time: 6.067 s.
[gmic]-2./ Display images [0,1] = '[image of 'vector(#3,u(255),u(255),u(255))'], [unnamed]'.
[0] = '[image of 'vector(#3,u(255),u(255),u(255))']':
  size = (4096,4096,1,3) [192 Mio of floats].
  data = (142,199,31,146,201,248,254,110,5,69,118,239,(...),254,198,176,114,43,244,8,101,104,125,177,161).
  min = 0, max = 255, mean = 127.494, std = 73.6169, coords_min = (1401,0,0,0), coords_max = (824,0,0,0).
[1] = '[unnamed]':
  size = (1,10595667,1,3) [121 Mio of floats].
  data = (7;29;32;37;39;48;53;55;56;58;60;67;(...),255;255;255;255;255;255;255;255;255;255;255;255).
  min = 0, max = 255, mean = 127.5, std = 73.6853, coords_min = (0,54,0,0), coords_max = (0,166,0,0).

da_size is the size of finalized array. That's the number of color in initial image.

 

In pseudo-code speak, this is how the algorithm work:

1. Create a 3D integer array of 256,256,256. This is your "color box".
2. Loop over the image, and use the RGB channel as coordinates to increment the 3D array or "color box"
3. Create a dynamic list.
4. Loop over your 3D box, and if there exists a color, insert into the dynamic list. 

 

Edited November 23, 2021 by Reptillian

[Forkanion]

2 hours ago, Reptillian said:

 

That's why I refer you to discuss.pixls.us as this is not a gmic forum. In G'MIC cli, you do '$ i image.png colormap 0' to create a palette of unique colors. There's also CLUT-mapping which allows you to map color from a image onto another image.

Where do I input this command?

[Reptillian]

@MJW Could it be possible to alter clipboard or send to clipboard? I think I know how to do it in C# or I feel like I can do it though you'll beat me to it if this was a race.

 

3D integer array of size 256,256,256 would be int[,,] arr = new int[256,256,256]; or something like this. And then, a dynamic array of RGB color is as simple as either ColorBRGA list or the equivalent of list for integer array of size 3. After the dynamic array has been generated from the 3D integer array, the problem of @Forkanion would be solved. I however don't know what he wants to do with said palette.

 

@Forkanion Do you want it as a file?

Edited November 23, 2021 by Reptillian

[MJW]

23 minutes ago, Reptillian said:

In pseudo-code speak, this is how the algorithm work:

 

Perhaps I'm dense, but that's not enough detail for me to understand the color-matching algorithm.

 

If you're willing to construct a 256x256x256 three of four byte table, I believe the ideas described in Fast algorithm for finding the minimum distances to a set could be used to construct a nearest-color table in linear time.  From then on, it's just a lookup per image color. Though the thread describes a two-dimensional version, the algorithm for finding the nearest set array element extends to any number of dimensions.

 

[Reptillian]

@MJW It's not about color-matching, but rather finding all unique colors. Utilizing a color-matching algorithm would be very slow for this purpose.

 

Here's the C# code:

 

List<(int,int,int)> RGB_Colors = new List<(int,int,int)>{
            (0,0,0)
};

int [,,] RGB_Box = new int[256,256,256];

void PreRender(Surface dst, Surface src)
{
    ColorBgra Coordinates;

    // The below code increments a pixel in 3D box using the coordinates generated from the color of the image.

    for (int x=0 ; x < src.Width ; x++){
        for (int y=0 ; y < src.Height ; y++){
            Coordinates = src[x,y];
            RGB_Box[Coordinates.R,Coordinates.G,Coordinates.B]++;
        }
    }

    //Add only unique colors

    for (int x=0 ; x<256 ; x++){
        for (int y=0 ; y<256 ; y++){
            for (int z=0 ; z<256 ; z++){
                if (RGB_Box[x,y,z]>0){
                    RGB_Colors.Add((z,y,x));
                }
            }
        }
    }
}

 

Edited November 23, 2021 by Reptillian

[Forkanion]

42 minutes ago, Reptillian said:

@MJW Could it be possible to alter clipboard or send to clipboard? I think I know how to do it in C# or I feel like I can do it though you'll beat me to it if this was a race.

 

3D integer array of size 256,256,256 would be int[,,] arr = new int[256,256,256]; or something like this. And then, a dynamic array of RGB color is as simple as either ColorBRGA list or the equivalent of list for integer array of size 3. After the dynamic array has been generated from the 3D integer array, the problem of @Forkanion would be solved. I however don't know what he wants to do with said palette.

 

@Forkanion Do you want it as a file?

Sure, expect I feel I wouldn't know how to use that since this is my first time using GIMP.

[MJW]

22 minutes ago, Reptillian said:

It's not about color-matching, but rather finding all unique colors. Utilizing a color-matching algorithm would be very slow for this purpose.

 

I thought the point was to find the nearest matching color. Finding the unique colors is pretty easy, I think. Just construct a linear bit-array of length 256x256x256. Then go through the image colors, setting the bit corresponding to (B << 16| G << 8 | R).

[Forkanion]

1 minute ago, MJW said:

 

I thought the point was to find the nearest matching color. Finding the unique colors is pretty easy, I think. Just construct a linear bit-array of length 256x256x256. Then go through the image colors, setting the bit corresponding to (B << 16| G << 8 | R).

I'm trying to succeed at finding all unique colors. and THEN applying it as a palette, to another image.

[MJW]

1 minute ago, Forkanion said:

m trying to succeed at finding all unique colors. and THEN applying it as a palette, to another image.

 

I kind of think the first part is pretty trivial compared to the second part.

[Forkanion]

23 minutes ago, MJW said:

 

I kind of think the first part is pretty trivial compared to the second part.

I still don't know how to do either...

[Reptillian]

18 minutes ago, Forkanion said:

I'm trying to succeed at finding all unique colors. and THEN applying it as a palette, to another image.

 

Does the result within the new image has to contain all the colors found in old image? Or are you looking for an approximate? The problem with restricting to only found colors is that it is very slow.

 

Here's the closest to what you want:

 

 

There is also the G'MIC-QT plugin which does have a filter to do this. Copy your reference image. Then, open G'MIC-QT, Colors-> Transfer Colors [Patch-Based]. Transfer Colors[PCA] works well.

[MJW]

20 minutes ago, Reptillian said:

Does the result within the new image has to contain all the colors found in old image?

 

I'm pretty sure the idea is that the new image contain only colors from the image used to build the palette.

[Forkanion]

4 minutes ago, MJW said:

 

I'm pretty sure the idea is that the new image contain only colors from the image used to build the palette.

Yes

[Reptillian]

Never mind, it is feasible.

Edited November 23, 2021 by Reptillian

[MJW]

28 minutes ago, Reptillian said:

If that's the case, then I do have bad news in one of my test. It is so slow. I actually don't think it's feasible with modern high-end PCs.

 

As I mentioned, there is an algorithm I describe in Fast algorithm for finding the minimum distances to a set that I believe could do the job in a reasonable time. The updated code for the "nearest pixel transform"  algorithm (which would become the nearest color transform) is given in a later comment, since for some reason I couldn't update the lead comment. The "set pixels" mentioned in the algorithm correspond the the colors that are present in the palette image. The algorithm would need to be extended from two dimensions to three, to handle the three color components. I'm confident that would fairly straightforward -- it's just applying the second stage in the algorithm again in the other direction.

 

Once the Nearest Color table is build, the colors in the second image could be replaced just by indexing into the table and fetching the color. Each entry in the 256x256x256 table is the nearest palette color.

 

I'd be happy to help anyone who wants to try it, but I'm not inclined to do it myself. It seems like quite a lot of work for a very limited audience. I can't imagine why anyone would want to use a palette of 14 million color.

[Forkanion]

7 minutes ago, MJW said:

 

As I mentioned, there is an algorithm I describe in Fast algorithm for finding the minimum distances to a set that I believe could do the job in a reasonable time. The updated code for the "distance transform"  algorithm is given in a later comment, since for some reason I couldn't update the lead comment. The "set pixels" mentioned in the algorithm correspond the the colors that are present in the palette image. The algorithm would need to be extended from two dimensions to three, to handle the three color components. I'm confident that would fairly straightforward -- it's just applying the second stage in the algorithm again in the other direction.

 

Once the Nearest Color table is build, the colors in the second image could be replaced just by indexing into the table and fetching the color. Each entry in the 256x256x256 table is the nearest palette color.

 

I'd be happy to help anyone who wants to try it, but I'm not inclined to do it myself. It seems like quite a lot of work for a very limited audience. I can't imagine why anyone would want to use a palette of 14 million color.

I actually already have the palette in the form of a .txt file, because of the "MakePalette" plugin tool, I now just need  to use it as a palette for another image. 

 

My Ultimate goal is to "purplify" this image.the color palette I'm using actually appears to have only have 1 million unique colors, but I can't use any Paint.NET plugin to basically round up the closest purple to each of the colors you see in that image. I'm trying to convert each color to it's nearest value in those 1 million purples.