[gimp/gimp-2-10] app: make generated indexed palettes possibly contain pure black/white

[Øyvind "pippin" Kolås <ok src gnome org>]

commit a3f4bbbac9031dbff61c58db8ddb22c184399a73
Author: Øyvind Kolås <pippin gimp org>
Date:   Thu Apr 30 19:53:25 2020 +0200

    app: make generated indexed palettes possibly contain pure black/white
    
    The median-cut algorithm to derive a suitable palette for the image
    computes each index to be used as the average of colors in a 3d box
    in a color space, making the result value drift away from the extremes.
    This makes it nigh impossible to achieve pure white or black, even
    when the original image contained these colors, like in scans of
    printed documents and technical drawings.
    
    We counteract the drift by snapping the whitest color to white and the
    blackest color to black if the resulting colors of median-cut are
    already sufficiently close to white or black.
    
    (cherry picked from commit 9bb3ff42d708d005886aa8cfc9a8492d12f77607)

 app/core/gimpimage-convert-indexed.c | 54 ++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
---
diff --git a/app/core/gimpimage-convert-indexed.c b/app/core/gimpimage-convert-indexed.c
index 4c9c4a0c63..a675bae8d8 100644
--- a/app/core/gimpimage-convert-indexed.c
+++ b/app/core/gimpimage-convert-indexed.c
@@ -2753,11 +2753,65 @@ median_cut_pass1_gray (QuantizeObj *quantobj)
   select_colors_gray (quantobj, quantobj->histogram);
 }
 
+static void
+snap_to_black_and_white (QuantizeObj *quantobj)
+{
+  /* find whitest and blackest colors in palette, if they are closer
+   * than 24 units of euclidian distance in sRGB snap them to pure
+   * black / white.
+   */
+#define POW2(a) ((a)*(a))
+  gint   desired  = quantobj->desired_number_of_colors;
+  gint   whitest  = 0;
+  gint   blackest = 0;
+
+  glong  white_dist = POW2(255) * 3;
+  glong  black_dist = POW2(255) * 3;
+  gint   i;
+
+  for (i = 0; i < desired; i ++)
+    {
+       int dist;
+
+       dist = POW2 (quantobj->cmap[i].red   - 255) +
+              POW2 (quantobj->cmap[i].green - 255) +
+              POW2( quantobj->cmap[i].blue  - 255);
+       if (dist < white_dist)
+         {
+           white_dist = dist;
+           whitest = i;
+         }
+
+       dist = POW2(quantobj->cmap[i].red   - 0) +
+              POW2(quantobj->cmap[i].green - 0) +
+              POW2(quantobj->cmap[i].blue  - 0);
+       if (dist < black_dist)
+         {
+           black_dist = dist;
+           blackest = i;
+         }
+    }
+
+  if (white_dist < POW2(24)) /* 24 units in sRGB ~= deltaE of 9.5 */
+  {
+     quantobj->cmap[whitest].red   =
+     quantobj->cmap[whitest].green =
+     quantobj->cmap[whitest].blue  = 255;
+  }
+  if (black_dist < POW2(24))
+  {
+     quantobj->cmap[blackest].red   =
+     quantobj->cmap[blackest].green =
+     quantobj->cmap[blackest].blue  = 0;
+  }
+#undef POW2
+}
 
 static void
 median_cut_pass1_rgb (QuantizeObj *quantobj)
 {
   select_colors_rgb (quantobj, quantobj->histogram);
+  snap_to_black_and_white (quantobj);
 }