On G'MIC 3.7, is my implementation of colormap is correct?

Software G'MIC
1

I have decided to make my own version of colormap, and I would like to know if the output is indeed correct. So, update G’MIC to test it.

Same parameters is used by my version rep_colormap. colormap 0 and rep_colormap 0 both have matching statistics, despite that they both have very different algorithm. For finding all colors, rep_colormap use 2 steps dictionary processing as to allow parallelization.

There are some numerical difference when using restricted color count, but I suspect that has to do with rep_colormap using doubles instead of float32, but I am not entirely sure of this. I do however notice that rep_colormap is faster.

You can see the output here:

C:\Windows\System32>gmic sp cat +rep_colormap 5,1,0
[gmic]./ Start G'MIC interpreter (v.3.7.0).
[gmic]./ Input sample image 'cat' (1 image 600x550x1x3).
[gmic]./ Estimate colormap with 5 entries for image [0], by k-means method.
[gmic]./ Display images [0,1] = 'cat, cat_c2'.
[0] = 'cat':
  size = (600,550,1,3) [3867.2 Kio of float32].
  data = (202,212,212,219,219,219,219,219,219,219,219,219,219,219,219,219,219,219,212,219,212,212,212,212,212,212,212,212,212,202,202,202,202,202,202,202,212,212,202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,193,193,193,193,193,193,193,188,188,188, ... ,140,128,95,95,79,80,70,81,89,95,117,115,95,70,62,70,70,51,46,45,79,99,117,128,133,128,117,59,16,19,70,80,81,89,99,79,70,79,81,115,128,128,95,59,79,106,117,117,128,128,79,79,95,103,103,95,70,79,128,147,146,117,59,13).
  min = 4, max = 244, mean = 113.418, std = 66.7981, coords_min = (293,0,0,0), coords_max = (144,29,0,0).
[1] = 'cat_c2':
  size = (5,1,1,3) [60 b of float32].
  data = (79.0526,206.922,201.203,139.304,157.566^41.3372,125.527,180.642,89.791,120.956^16.352,45.7982,156.722,40.2507,78.4207).
  min = 16.352, max = 206.922, mean = 111.99, std = 59.522, coords_min = (0,0,0,2), coords_max = (1,0,0,0).
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>gmic sp cat +colormap 5,1,0
[gmic]./ Start G'MIC interpreter (v.3.7.0).
[gmic]./ Input sample image 'cat' (1 image 600x550x1x3).
[gmic]./ Estimate colormap with 5 entries for image [0], by k-means method.
[gmic]./ Display images [0,1] = 'cat, [colormap of cat]_c1'.
[0] = 'cat':
  size = (600,550,1,3) [3867.2 Kio of float32].
  data = (202,212,212,219,219,219,219,219,219,219,219,219,219,219,219,219,219,219,212,219,212,212,212,212,212,212,212,212,212,202,202,202,202,202,202,202,212,212,202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,193,193,193,193,193,193,193,188,188,188, ... ,140,128,95,95,79,80,70,81,89,95,117,115,95,70,62,70,70,51,46,45,79,99,117,128,133,128,117,59,16,19,70,80,81,89,99,79,70,79,81,115,128,128,95,59,79,106,117,117,128,128,79,79,95,103,103,95,70,79,128,147,146,117,59,13).
  min = 4, max = 244, mean = 113.418, std = 66.7981, coords_min = (293,0,0,0), coords_max = (144,29,0,0).
[1] = '[colormap of cat]_c1':
  size = (5,1,1,3) [60 b of float32].
  data = (67.3609,178.684,206.229,150.732,195.195^27.9121,108.59,186.261,56.9209,150.91^12.7823,44.1835,160.4,14.5111,94.8767).
  min = 12.7823, max = 206.229, mean = 110.37, std = 67.0463, coords_min = (0,0,0,2), coords_max = (2,0,0,0).
[gmic]./ End G'MIC interpreter.
2

EDIT: Turns out I discovered some few more bugs for k-means. So, still not there yet.

EDIT 2: And I think I don’t understand critical() yet. It’s not doing what I’d like. So, it can’t do merge like this?

eval. :"begin(
             # Code Here
           );
           # Code Here
           critical(
             merge(vector_variable,+);
             # Code Here
           );
           end(
               # Code Here
           );

If it could, then I would finish by now.

For full context of what I want (snip):

if $red_cols_mode
	m __$0_red_cols_mode:"
		if $2 # Add k-means step
			keep[0,2]
			+_rep_colormap_median_cut[0] $1
			max_diff={(iM-im+1)/8192}

			eval.. :\"
				O=J(-1);                   # Negative Offset Vector
				SP=(O[0]<<24|O[1])-1;      # Start Point
				Q=i0<<24|i1;               # End Point - Semi Const
				const S=s#0;               # Spectrum size;

				base_new=vector(whds#-1);
				current_palette=crop(#-1);
				new_palette=incremental_palette=current_palette * 0;
				temp_vector=count=vector(#whd#-1);
				const C=size(count);

				do(
					P=SP;
					while(++P<Q,
						current_color=I[#0,P];
						selected_index=[index(current_color,current_palette,S,0,0)][0];
						copy(incremental_palette[selected_index],current_color,S,C,1,-1);
						++count[selected_index];
					);
					critical( # Suppose to merge all colors and count
						merge(incremental_palette,+);
						merge(count,+);
						count=1/vmax(count,1);
					);
					p=0;
					repeat(S,
						copy(temp_vector[0],incremental_palette[p],C,1,1);
						temp_vector*=count;
						copy(new_palette[p],temp_vector[0],C,1,1);
						p+=C;
					);
					diff=maxabs(new_palette-current_palette);
					current_palette=new_palette;
					copy(count[0],0,size(count),1,0);
					copy(incremental_palette[0],0,size(incremental_palette),1,0);
				,diff>$max_diff);
				I;
				end(
					copy(i[#2,0],current_palette);
				);
				\"
				rm[0,1]
		else
			rm[^0]
			_rep_colormap_median_cut $1
		fi
		"
fi

Per threads, I loop toward pixel starting point P, and the loop ends with Q. This loop continue until diff<max_diff. critical is meant to stop all other threads, then merge the result. then this continues back.

EDIT 3:
Made a code to test critical(). Apparently, not what I’d like to see.

foo_crit:
5 (1,2,4)
eval.. :"begin(
             # Code Here
           );
           count=v(5);
           print([t,count]);
           critical(
             repeat(1000000,count+=i[#-1,v(0,2)]);
             print([6,count]);
           );
           print(count);"

Result:

C:\Windows\System32>gmic foo_crit
[gmic]./ Start G'MIC interpreter (v.3.7.0).
[gmic_math_parser] [t,count] = (uninitialized) (mem[36]: vector2)
[gmic_math_parser] [6,count] = (uninitialized) (mem[41]: vector2)
[gmic_math_parser] count = (uninitialized) (mem[35]: scalar)
[gmic_math_parser] [t,count] = [ 4,3 ] (size: 2)
[gmic_math_parser] [t,count] = [ 3,3 ] (size: 2)
[gmic_math_parser] [t,count] = [ 0,5 ] (size: 2)
[gmic_math_parser] [t,count] = [ 2,2 ] (size: 2)
[gmic_math_parser] [t,count] = [ 1,1 ] (size: 2)
[gmic_math_parser] [6,count] = [ 6,2334714 ] (size: 2)
[gmic_math_parser] count = 2334714
[gmic_math_parser] [6,count] = [ 6,2333524 ] (size: 2)
[gmic_math_parser] count = 2333524
[gmic_math_parser] [6,count] = [ 6,2332435 ] (size: 2)
[gmic_math_parser] count = 2332435
[gmic_math_parser] [6,count] = [ 6,2332976 ] (size: 2)
[gmic_math_parser] count = 2332976
[gmic_math_parser] [6,count] = [ 6,2331716 ] (size: 2)
[gmic_math_parser] count = 2331716
[gmic]./ Display images [0,1] = '[unnamed], (1,2,4)'.
[0] = '[unnamed]':
  size = (5,1,1,1) [20 b of float32].
  data = (0,0,0,0,0).
  min = 0, max = 0, mean = 0, std = 0, coords_min = (0,0,0,0), coords_max = (0,0,0,0).
[1] = '(1,2,4)':
  size = (3,1,1,1) [12 b of float32].
  data = (1,2,4).
  min = 1, max = 4, mean = 2.33333, std = 1.24722, coords_min = (0,0,0,0), coords_max = (2,0,0,0).
[gmic]./ End G'MIC interpreter.

So, what is critical() used for anyway? It can’t stop all the other threads and work on a code in a single thread.

3

merge() is a function that is only called once in an expression, in the end() section.
You should always put it in the end() section, even if it works when put somewhere else.

Function critical(code) just execute code in a thread while blocking code execution in the other threads, until the end of code has been reached. This way, you can safely read/write parts of the math parser memory, knowing no other threads will do the same, at the same time.

1 Like
4

So, merge() never gets called in !t?(critical()). It would be interesting if merge() can be called there.

I see. So, all threads can use critical, but doing something like !t?(critical()) will do what I envisioned? Like only work on one thread.

EDIT:

Ok, I see. I think I will use images instead to do manual merging.

Seems to do the trick here:

foo_crit:
5 1x6
eval[0] :"
           i[#x+1,0]=v(0,100);
           !t?critical(
             temp=0;
             repeat(w,p,
               temp+=i[#p+1,0];
             );
             i[#-1,0]=temp;
           );"
5

The role of the merge() function is to merge the information calculated by each thread at the end of their calculation. In this context, using merge() in the middle of a calculation would not make sense. This would mean merging information from threads that are still being calculated. This would likely result in a somewhat random result, depending on the order in which the different threads are calculated. This would not be useful.

Ensuring that the merge() function is executed only once in the expression, at the end of the calculation of all threads, is the only way to obtain a consistent and usable result at the end of a mathematical expression (in the end() block).

6

Thanks. I ended up with a light bulb moment, and found a better solution, without the use of critical. So, I ended up fixing k-mode calculation for rep_colormap.

I don’t know if it is more accurate though, but for what it’s worth, my solution is faster:

C:\Windows\System32>gmic sp dog tic +rep_colormap 5,1,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.0).
[gmic]./ Input sample image 'dog' (1 image 1024x685x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate colormap with 5 entries for image [0], by k-means method.
[gmic]./ Elapsed time: 1.046 s.
[gmic]./ Display images [0,1] = 'dog, dog_c2'.
[0] = 'dog':
  size = (1024,685,1,3) [8220 Kio of float32].
  data = (67,71,67,71,67,71,71,67,67,71,71,67,71,67,67,71,67,73,67,67,67,67,67,67,67,67,67,67,61,67,61,67,67,67,67,67,67,67,67,67,67,71,67,67,67,67,67,73,67,71,77,73,73,77,81,82,77,82,77,77,82,82,82,82, ... ,106,96,96,90,78,90,90,90,90,106,78,60,77,77,53,60,66,90,96,106,106,96,90,77,77,77,78,90,90,90,78,66,66,77,78,78,78,78,90,77,66,100,77,77,66,60,66,66,68,78,78,78,79,90,90,90,79,79,84,84,84,79,79,79).
  min = 2, max = 254, mean = 119.113, std = 53.8004, coords_min = (409,183,0,0), coords_max = (474,89,0,0).
[1] = 'dog_c2':
  size = (5,1,1,3) [60 b of float32].
  data = (40.6954,149.142,215.819,110.096,105.45^47.6489,156.878,216.515,111.247,136.131^30.3598,160.292,214.624,108.469,53.0326).
  min = 30.3598, max = 216.515, mean = 123.76, std = 61.0432, coords_min = (0,0,0,2), coords_max = (2,0,0,1).
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>gmic sp dog tic +colormap 5,1,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.0).
[gmic]./ Input sample image 'dog' (1 image 1024x685x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate colormap with 5 entries for image [0], by k-means method.
[gmic]./ Elapsed time: 1.914 s.
[gmic]./ Display images [0,1] = 'dog, [colormap of dog]_c1'.
[0] = 'dog':
  size = (1024,685,1,3) [8220 Kio of float32].
  data = (67,71,67,71,67,71,71,67,67,71,71,67,71,67,67,71,67,73,67,67,67,67,67,67,67,67,67,67,61,67,61,67,67,67,67,67,67,67,67,67,67,71,67,67,67,67,67,73,67,71,77,73,73,77,81,82,77,82,77,77,82,82,82,82, ... ,106,96,96,90,78,90,90,90,90,106,78,60,77,77,53,60,66,90,96,106,106,96,90,77,77,77,78,90,90,90,78,66,66,77,78,78,78,78,90,77,66,100,77,77,66,60,66,66,68,78,78,78,79,90,90,90,79,79,84,84,84,79,79,79).
  min = 2, max = 254, mean = 119.113, std = 53.8004, coords_min = (409,183,0,0), coords_max = (474,89,0,0).
[1] = '[colormap of dog]_c1':
  size = (5,1,1,3) [60 b of float32].
  data = (40.6954,149.142,215.819,110.096,105.449^47.6489,156.921,216.515,111.247,136.171^30.3598,160.309,214.624,108.469,53.0326).
  min = 30.3598, max = 216.515, mean = 123.767, std = 61.046, coords_min = (0,0,0,2), coords_max = (2,0,0,1).
[gmic]./ End G'MIC interpreter.

That being said, I know a tiny optimization I can do. Pretty tiny though.

7

BTW, this made me add this:

Because, I see no scenario where the use of merge() outside a end() block would make sense.

8

Well, I finished my variant of colormap, and all the other derivative command which all use _rep_colors_freqstat. I think the implementation is correct. k-mean/and medium cut do vary just a tiny bit, but I like how my result is more saturated on k-mean. Also, rep_count_colors use the very same command.

Speed-wise, with multiple CPUs, it’s 300% faster on my end for images with large number of colors, and large images. 12 threads, but I think in this case, more threads would be way better.

Also, it has a noticeable weakness involving images with colors that appears over 1<<24 times, and that can be rectified with f2ui/ui2f, but not fixing any time soon. It also is slower in case of sp eagle, but I can’t do anything about it except adjust parameter and hope it works out, but don’t know.

Another test result:

D:\Pictures\A Year Folders Pictures\2025 Folders\July 2025\darktable_exported>gmic 7E4A3373.jpg tic colormap 0,0,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.1).
[gmic]./ Input file '7E4A3373.jpg' at position 0 (1 image 6984x4660x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate full colormap for image [0].
[gmic]./ Elapsed time: 9.808 s.
[gmic]./ Display image [0] = '[colormap of '7E4A3373.jpg']'.
[0] = '[colormap of '7E4A3373.jpg']':
  size = (294627,1,1,3) [3452.7 Kio of float32].
  data = (0,93,12,51,61,95,165,185,197,83,30,32,133,75,73,127,53,147,145,155,175,187,103,125,10,123,113,125,118,84,72,74,104,22,114,49,142,145,72,126,52,94,52,54,56,114,64,85,94,76,128,62,81,110,98,108,103,71,22,83,165,50,63,115, ... ,86,121,113,160,87,106,154,162,69,128,67,61,59,77,69,103,55,67,174,94,95,66,78,85,75,12,57,123,81,116,100,65,92,79,143,133,175,171,152,135,183,187,102,115,223,176,79,145,135,57,47,82,24,32,22,1,49,37,54,158,150,28,49,71).
  min = 0, max = 246, mean = 101.32, std = 47.7767, coords_min = (0,0,0,0), coords_max = (234784,0,0,2).
[gmic]./ End G'MIC interpreter.

D:\Pictures\A Year Folders Pictures\2025 Folders\July 2025\darktable_exported>gmic 7E4A3373.jpg tic rep_colormap 0,0,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.1).
[gmic]./ Input file '7E4A3373.jpg' at position 0 (1 image 6984x4660x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate full colormap for image [0].
[gmic]./ Elapsed time: 3.355 s.
[gmic]./ Display image [0] = '[empty]'.
[0] = '[empty]':
  size = (294627,1,1,3) [3452.7 Kio of float32].
  data = (153,128,53,168,0,136,58,75,169,57,33,31,120,85,110,28,110,106,102,5,49,142,163,185,88,192,195,150,205,26,100,157,130,105,30,119,168,164,115,126,182,113,104,66,70,132,34,174,46,37,112,105,156,126,132,110,90,172,86,137,73,113,65,40, ... ,135,124,75,89,70,87,84,98,116,148,110,164,157,134,75,63,112,67,158,130,62,158,63,80,138,81,144,139,49,113,66,137,76,81,5,77,122,102,76,32,46,78,82,172,174,124,148,133,63,40,139,66,54,23,8,43,50,85,7,5,129,152,59,36).
  min = 0, max = 246, mean = 101.32, std = 47.7767, coords_min = (4,0,0,0), coords_max = (209967,0,0,2).
[gmic]./ End G'MIC interpreter.
D:\Pictures\A Year Folders Pictures\2025 Folders\July 2025\darktable_exported>gmic 7E4A3512.jpg tic rep_colormap 0,0,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.1).
[gmic]./ Input file '7E4A3512.jpg' at position 0 (1 image 6984x4660x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate full colormap for image [0].
[gmic]./ Elapsed time: 4.329 s.
[gmic]./ Display image [0] = '[empty]'.
[0] = '[empty]':
  size = (988178,1,1,3) [11.3 Mio of float32].
  data = (170,93,171,132,203,142,36,70,112,127,147,70,131,83,177,134,85,33,144,155,70,150,161,144,133,173,76,127,102,139,130,145,139,120,154,123,143,145,186,132,68,85,181,134,128,129,131,107,137,54,189,28,124,18,59,164,130,155,131,114,121,80,126,113, ... ,155,7,41,69,1,61,113,85,155,27,167,73,181,159,151,185,67,195,71,115,81,101,141,225,173,101,91,145,1,147,101,121,125,181,163,129,187,139,53,35,221,97,147,149,87,7,71,143,61,145,107,171,131,125,139,183,81,179,135,157,167,169,155,139).
  min = 0, max = 255, mean = 124.892, std = 60.9835, coords_min = (319,0,0,0), coords_max = (223,0,0,0).
[gmic]./ End G'MIC interpreter.

D:\Pictures\A Year Folders Pictures\2025 Folders\July 2025\darktable_exported>gmic 7E4A3512.jpg tic colormap 0,0,0 toc
[gmic]./ Start G'MIC interpreter (v.3.7.1).
[gmic]./ Input file '7E4A3512.jpg' at position 0 (1 image 6984x4660x1x3).
[gmic]./ Initialize timer.
[gmic]./ Estimate full colormap for image [0].
[gmic]./ Elapsed time: 14.348 s.
[gmic]./ Display image [0] = '[colormap of '7E4A3512.jpg']'.
[0] = '[colormap of '7E4A3512.jpg']':
  size = (988178,1,1,3) [11.3 Mio of float32].
  data = (35,176,187,138,83,105,31,151,43,139,147,150,140,66,105,115,152,78,150,111,134,164,81,103,72,117,159,135,170,95,126,55,59,149,80,47,57,54,102,128,102,95,158,104,138,134,119,175,78,125,82,57,71,133,88,93,182,14,88,161,175,66,147,105, ... ,78,138,127,66,142,10,96,49,90,148,124,40,44,40,149,99,155,0,64,150,152,141,56,145,99,73,107,180,127,144,142,166,139,53,150,146,115,147,218,153,198,192,115,87,126,110,119,168,181,159,120,156,151,73,191,82,92,159,153,108,162,74,99,211).
  min = 0, max = 255, mean = 124.892, std = 60.9835, coords_min = (285,0,0,0), coords_max = (441,0,0,0).
[gmic]./ End G'MIC interpreter.

EDIT:
Had to disable my own implementation of color count. Can’t say where’s the bug is.

EDIT:
I found out why, I deleted part of the dict table. Now it all works fine. Seems slower on default sp cat though though palette/mode creation are faster than colormap 0,0,0. Overall, still faster counting with 400000+ colors or most of the sp images.