Best way of adding new random colors into a resized palette?

For context, I am developing a gui_toolkit filter which would make things easier when developing GUI filters that use dynamic amount of color selection. So, my issue is now making new colors utilizing existing image with integers and their ranges is 0-255. It should be agnostic to numbers of channels, and very fast.

  1. I tried thinking of hashmap integers inside math evaluator, but I find that way too hard to attempt. All my mental experiments leads to problems.
  2. I know you can use random values to make new palette colors, but as low probability as it is, it is possible to create a duplicate.

EDIT: I found MurmurHash3 to hash big integer number. I don’t get the algorithm nor how to implement it.

EDIT: I came up with a much better idea. Sorting palettes according to their integer values. That means the most significant channel will define their position. And best of all, this can be used as dynamic array to be used as a way to filter out colors and to create a new random color.

Okay, it looks like I managed to sort palettes according to their integer values.

$ pal 50 rep_pal_sort_colors_by_integer_values
#@cli rep_pal_sort_colors_by_integer_values:
#@cli : Sort palettes using integer values. Use on small images only! Maximum number of channels supported is 6!
rep_pal_sort_colors_by_integer_values:
foreach {
 if s>6 error max_s<=6=F fi

 ({"
  const number_of_channels=s#-1;
  const pixels_count=whd#-1;
  indexes=expr('x>>1',pixels_count<<1);
  bitshift_factors=expr('x?1<<(2+x)',number_of_channels);
  convert_color2int(color_values)=sum(color_values<<bitshift_factors);
  repeat(pixels_count,p,indexes[p<<1]=convert_color2int(I[#-1,p]););
  indexes=sort(indexes,1,pixels_count,2);
  (indexes)[1,pixels_count,2];
 "})
 
 map[-1] [-2] rm[-2]
}

I think this problem is solvable now.

And this confirms it:

$ pal 111 +rep_pal_sort_colors_by_integer_values mirror.. c rgb2int.. sort.. int2rgb.. mirror.. c

I made another approach, but problem is that it doesn’t work:

#@cli foo:
foo:

foreach {

 1,1,1,100%

 eval "
  const number_of_channels=s#0;
  const pixels_count=whd#0;
 
  bitshift_factors=expr('x?1<<(2+x)',number_of_channels);
 
  convert_color2int(color_values)=sum(color_values<<bitshift_factors);
  
  min_pos_val=-1;
  max_pos_val=inf;
  
  state_check=mode=0;
  old_value=last_known_pivot=pivot_value=-1;
 
  repeat(pixels_count,p,
  
   current_color=I[#0,p];
   current_value=convert_color2int(current_color);
   
   mode==3?(
   
    state_check=0;
   
    current_value==min_pos_val||current_value==max_pos_val||current_value==pivot_value||current_value==old_value?(
     continue();
    ):(
     old_value=current_value;
     
     current_value<min_pos_val?(
      min_pos_val=current_value;
      da_insert(#-1,0,current_color);
     ):
     current_value>max_pos_val?(
      max_pos_val=current_value;
      da_push(#-1,current_color);
     ):
     current_value>pivot_value?(
      for(q=last_known_pivot+1,q<da_size(#-1),++q,
       test_value=convert_color2int(I[#-1,q]);
       test_value>current_value?(
        da_insert(#-1,q,current_color);
        break();
       ):
       test_value==current_value?(
        state_check=1;
        break();
       );
      );
     ):( # current_value<pivot_value
      for(q=last_known_pivot-1,q>0,--q,
       test_value=convert_color2int(I[#-1,q]);
       current_value<test_value?(
        da_insert(#-1,q,current_color);
        break();
       ):
       test_value==current_value?(
        state_check=1;
        break();
       );
      );
     );
     
     if(state_check,continue(););
     last_known_pivot=da_size(#-1)>>1;
     pivot_value=convert_color2int(I[#-1,last_known_pivot]);
    );
    
   ):
   mode==2?(
   
    if(!state_check,
     min_pos_val=convert_color2int(I[#-1,0]);
     max_pos_val=convert_color2int(I[#-1,1]);
     state_check=1;
    );
    
    current_value==min_pos_val||current_value==max_pos_val?(
     continue();
    ):(
     last_known_pivot=1;
     mode=3;
     state_check=0;
     
     current_value<min_pos_val?(
      pivot_value=min_pos_val;
      min_pos_val=current_value;
      da_insert(#-1,0,current_color);
     ):
     current_value<max_pos_val?(
      pivot_value=current_value;
      da_insert(#-1,1,current_color);
     ):
     current_value>max_pos_val?(
      pivot_value=max_pos_val;
      max_pos_val=current_value;
      da_push(#-1,current_color);
     );
    );
    
   ):
   mode?(
   
    current_value>old_value?(
     da_push(#-1,current_color);
     old_value=current_value;
     mode=2;
    ):
    current_value<old_value?(
     da_insert(#-1,0,current_color);
     old_value=current_value;
     mode=2;
    );
    
   ):(
   
    da_push(#-1,current_color);
    old_value=current_value;
    mode=1;
    
   );
   
  );
  da_freeze(#-1);
  "
}

The insertion sort thing is a problem. Shows potential as this is really fast. It combines minmax sort with bidirectional insertion sort.

rgb2int sort takes .012 s.

This approach takes .001 s.

EDIT: I fixed it.

#@cli foo:
foo:

foreach {

 1,1,1,100%

 eval "
  const number_of_channels=s#0;
  const pixels_count=whd#0;
 
  bitshift_factors=expr('x?1<<(2+x)',number_of_channels);
 
  convert_color2int(color_values)=sum(color_values<<bitshift_factors);
  
  min_pos_val=-1;
  max_pos_val=inf;
  
  state_check=mode=0;
  old_value=last_known_pivot=pivot_value=-1;
 
  repeat(pixels_count,p,
  
   current_color=I[#0,p];
   current_value=convert_color2int(current_color);
   
   mode==3?(
   
    state_check=0;
   
    current_value==min_pos_val||current_value==max_pos_val||current_value==pivot_value||current_value==old_value?(
     continue();
    ):(
     old_value=current_value;
     
     current_value<min_pos_val?(
      min_pos_val=current_value;
      da_insert(#-1,0,current_color);
     ):
     current_value>max_pos_val?(
      max_pos_val=current_value;
      da_push(#-1,current_color);
     ):
     current_value>pivot_value?(
      for(q=last_known_pivot+1,q<da_size(#-1),++q,
       test_value=convert_color2int(I[#-1,q-1]);
       test_value>current_value?(
        da_insert(#-1,q-1,current_color);
        break();
       ):
       test_value==current_value?(
        state_check=1;
        break();
       );
      );
     ):( # current_value<pivot_value
     for(q=last_known_pivot-1,q>0,--q,
       test_value=convert_color2int(I[#-1,q]);
       current_value>test_value?(
        da_insert(#-1,q+1,current_color);
        break();
       ):
       test_value==current_value?(
        state_check=1;
        break();
       );
      );
     );
     
     if(state_check,continue(););
     last_known_pivot=da_size(#-1)>>1;
     pivot_value=convert_color2int(I[#-1,last_known_pivot]);
     old_value=current_value;
    );
    
   ):
   mode==2?(
   
    if(!state_check,
     min_pos_val=convert_color2int(I[#-1,0]);
     max_pos_val=convert_color2int(I[#-1,1]);
     state_check=1;
    );
    
    current_value==min_pos_val||current_value==max_pos_val?(
     continue();
    ):(
     last_known_pivot=1;
     mode=3;
     state_check=0;
     
     current_value<min_pos_val?(
      pivot_value=min_pos_val;
      min_pos_val=current_value;
      da_insert(#-1,0,current_color);
     ):
     current_value<max_pos_val?(
      pivot_value=current_value;
      da_insert(#-1,1,current_color);
     ):
     current_value>max_pos_val?(
      pivot_value=max_pos_val;
      max_pos_val=current_value;
      da_push(#-1,current_color);
     );
    );
    
   ):
   mode?(
   
    current_value>old_value?(
     da_push(#-1,current_color);
     old_value=current_value;
     mode=2;
    ):
    current_value<old_value?(
     da_insert(#-1,0,current_color);
     old_value=current_value;
     mode=2;
    );
    
   ):(
   
    da_push(#-1,current_color);
    old_value=current_value;
    mode=1;
    
   );
   
  );
  da_freeze(#-1);
  "
}

I just managed to do it, and even implemented a earlier code into it - G'MIC Challenge - All RGB - #8 by David_Tschumperle

However, I found issues with @David_Tschumperle code


I found that a lot of colors are corners of RGB cube. So, there must be some solution here that can get around that issue.

Purely random non-existent color doesn’t have that issue:

image

Current code if any one wants to play with it:

#@cli rep_non_existent_color_pal: number_of_new_colors, _appended_into_palette={ 0=do_not_append | 1=append into palette },_method={ 0=random | 1=farthest (slow) },_color_space={ 0=RGB | 1=HSV8 },_cube_size>=7
#@cli : Generates a palette of non-existent colors on each images. Either, appended onto the image, or as a new palette.
#@cli : '_appended_into_palette=1','_method=0','_color_space=0','_cube_size=64'
rep_non_existent_color_pal:
skip ${2=1},${3=0},${4=0},${5=16}
check "isint($1)&&$1>=1"

number_of_new_colors,append_into_pal,cube_size=$1,$2,$5

if isint($3) far_mode={$3&1}
else
 r,rand,random,aleatoria=0 far,farthest,distant,lejos=1
 far_mode=$$3 if !narg($far_mode) error inval_arg fi
fi

if isint($4) cs={$4&1}
else
 list_of_cs_args=rgb,RGB,rvb,RVB,hsv,HSV
 $list_of_cs_args={expr('x>>2',narg($list_of_cs_args))}
 cs=$$4 if !narg($cs) error inval_arg fi
fi

if $far_mode
 if !isint($cube_size)||!inrange($cube_size,7,256,1,1) 
  error inv_inp_\$\5
 fi
 if $cube_size==256
  initial_code=i(#-1,I)=1
  xyz_code=[xM,yM,zM]
  m "rep_non_existent_color_pal_insert_new_color: point 0,$""1,0,1,$""2,$""3,$""4"
 else
  divisor:=($cube_size-1)/255
  initial_code=i(#-1,I*$divisor)=1
  xyz_code=round([xM,yM,zM])
  m "rep_non_existent_color_pal_insert_new_color: point 0,$""1,0,1,{round([$""2,$""3,$""4]*"{255/($cube_size-1)}")}"
 fi
fi

convert_colors_fwd=${arg\ $cs+1,error,rgb2hsv8}
convert_colors_bwd=${arg\ $cs+1,error,hsv82rgb}

foreach { # For each images

 current_number_of_colors:=whd

 if $far_mode
 
  if s!=3 error inv_chans_num fi
  
  if $cs $convert_colors_fwd fi
  
  {vector3($cube_size)},1
  eval[-2] $initial_code
  
  if $append_into_pal
   1,{$number_of_new_colors+$current_number_of_colors},1,1,y
   map[-1] [-3]
   rm[-3]
  else
   1,$number_of_new_colors,1,{s#-2} rm[-3]
   current_number_of_colors=0
  fi
  
  repeat $number_of_new_colors {
   +distance.. 1,2 xyz:=$xyz_code rm. 
   point.. $xyz,1,1
   rep_non_existent_color_pal_insert_new_color. $current_number_of_colors,$xyz
   current_number_of_colors+=1
  }
  
  rm..
  
  if $cs $convert_colors_bwd fi
 else
 
  if !inrange(1,6,1,1) 
   error inv_chans_num
  fi
  
  if $cs $convert_colors_fwd fi
  
  if $append_into_pal
   1,{$number_of_new_colors+$current_number_of_colors},1,1,y 
   map[-1] [-2] 
   rm[-2]
   1,1,1,100%
  else
   1,1,1,100%x2
  fi

  eval "  # Enter JIT compiler
   const number_of_new_colors=$number_of_new_colors;
   const number_of_channels=s#0;
   const current_number_of_colors=$current_number_of_colors;
   const append_into_pal=$append_into_pal;
   const maximum_integer_value=256^number_of_channels;
 
   bitshift_factors=expr('x?1<<(2+x)',number_of_channels);
 
   convert_color2int(color_values)=sum(color_values<<bitshift_factors);
   convert_int2color(value)=(value>>bitshift_factors)&0xff;
  
   min_pos_val=-1;
   max_pos_val=inf;
  
   state_check=mode=0;
   old_value=middle_pivot=pivot_value=-1;
 
   repeat(current_number_of_colors,p,
  
    current_color=I[#0,p];
    current_value=convert_color2int(current_color);
   
    mode==3?(
   
     state_check=0;
   
     current_value==min_pos_val||current_value==max_pos_val||current_value==pivot_value||current_value==old_value?(
      continue();
     ):(
      old_value=current_value;
     
      current_value<min_pos_val?(
       min_pos_val=current_value;
       da_insert(#-1,0,current_color);
      ):
      current_value>max_pos_val?(
       max_pos_val=current_value;
       da_push(#-1,current_color);
      ):
      current_value>pivot_value?(
       for(q=middle_pivot+1,q<da_size(#-1),++q,
        test_value=convert_color2int(I[#-1,q]);
        test_value>current_value?(
         break();
        ):
        test_value==current_value?(
         state_check=1;
         break();
        );
       );
       if(state_check
       ,continue();
       ,da_insert(#-1,q,current_color);
       );
      ):( # current_value<pivot_value
      for(q=middle_pivot-1,q>0,--q,
        test_value=convert_color2int(I[#-1,q]);
        current_value>test_value?(
         break();
        ):
        test_value==current_value?(
         state_check=1;
         break();
        );
       );
       if(state_check
       ,continue();
       ,da_insert(#-1,q+1,current_color);
       );
      );
      middle_pivot=da_size(#-1)>>1;
      pivot_value=convert_color2int(I[#-1,middle_pivot]);
     );
    
    ):
    mode==2?(
   
     if(!state_check,
      min_pos_val=convert_color2int(I[#-1,0]);
      max_pos_val=convert_color2int(I[#-1,1]);
      state_check=1;
     );
    
     current_value==min_pos_val||current_value==max_pos_val?(
      continue();
     ):(
      middle_pivot=1;
      mode=3;
      state_check=0;
     
      current_value<min_pos_val?(
       pivot_value=min_pos_val;
       min_pos_val=current_value;
       da_insert(#-1,0,current_color);
      ):
      current_value<max_pos_val?(
       pivot_value=current_value;
       da_insert(#-1,1,current_color);
      ):
      current_value>max_pos_val?(
       pivot_value=max_pos_val;
       max_pos_val=current_value;
       da_push(#-1,current_color);
      );
     );
    
    ):
    mode?(
   
     current_value>old_value?(
      da_push(#-1,current_color);
      old_value=current_value;
      mode=2;
     ):
     current_value<old_value?(
      da_insert(#-1,0,current_color);
      old_value=current_value;
      mode=2;
     );
    
    ):(
   
     da_push(#-1,current_color);
     old_value=current_value;
     mode=1;
    
    );
   
   );
   
   append_into_pal?(
    insertion_pos=current_number_of_colors;
    insert_new_color(color)=I[#-2,insertion_pos++]=color;
   ):(
    insert_new_color(color)=da_push(#-2,color);
   );
   
   last_rn=inf;
   q=0; # Inserted position
   repeat(number_of_new_colors,
    selec_u=int(u(0,maximum_integer_value-da_size(#-1),1,0));
    for(q=(selec_u>=last_rn?q),q<da_size(#-1),++q,
     selec_u>=convert_color2int(I[#-1,q])?(
      ++selec_u;
     ):(break(););
    );
    new_color=convert_int2color(selec_u);
    da_insert(#-1,q,new_color);
    insert_new_color(new_color);
    last_rn=selec_u;
   );
   
   if(!append_into_pal,da_freeze(#-2););
   "
  
  keep[{!$append_into_pal}]
  
  if $cs $convert_colors_bwd round fi
 fi
}

um rep_non_existent_color_pal_insert_new_color

What issues exactly ? Could you describe them precisely ?

The issue is that finding colors with greatest distance away often lead to colors like (0,255,255),(255,0,0)… But I think I know my workaround to that. Have a 3D image with a spherical shade to be used for multiplication so that the resulting colors are more closer to the center.

Edit: I guess another solution would be inpaint method. It would be very slow, but doable.

And I solved it!

RGB - Lago Nenufar
image

RGB - Still-Life
image

HSV - Still-Life
image

Left: Palette Input
Right: New non-existent colors.

2 Likes