I see that you use euclidean distance of perceptual color and named your color function bad_color_distance. My only input here would be to try something like the CIEDE2000 color difference formula to see if the result can be further improved.