[FFmpeg-devel] [PATCH 13/15] avfilter/palettegen: use variance per-axis instead of the range

["Clément Bœsch" <u@pkh.me>]

The split decision is now based on the per-axis variance instead of how
wide they are.
---
 libavfilter/vf_palettegen.c        | 61 ++++++++++++++++--------------
 tests/ref/fate/filter-palettegen-1 |  2 +-
 tests/ref/fate/filter-palettegen-2 |  2 +-
 3 files changed, 35 insertions(+), 30 deletions(-)

diff --git a/libavfilter/vf_palettegen.c b/libavfilter/vf_palettegen.c
index 4c2bcba7f7..2976012512 100644
--- a/libavfilter/vf_palettegen.c
+++ b/libavfilter/vf_palettegen.c
@@ -45,6 +45,7 @@ struct color_ref {
 struct range_box {
     uint32_t color;     // average color
     double variance;    // overall variance of the box (how much the colors are spread)
+    double axis_variance[3]; // axis specific variance
     int start;          // index in PaletteGenContext->refs
     int len;            // number of referenced colors
     int sorted_by;      // whether range of colors is sorted by red (0), green (1) or blue (2)
@@ -136,24 +137,29 @@ static int cmp_color(const void *a, const void *b)
     return FFDIFFSIGN(box1->color , box2->color);
 }
 
-static av_always_inline float diff(const uint32_t a, const uint32_t b)
-{
-    const struct Lab lab0 = ff_srgb_u8_to_oklab(a);
-    const struct Lab lab1 = ff_srgb_u8_to_oklab(b);
-    const float dL = lab0.L - lab1.L;
-    const float da = lab0.a - lab1.a;
-    const float db = lab0.b - lab1.b;
-    return dL*dL + da*da + db*db;
-}
-
 static void compute_box_variance(PaletteGenContext *s, struct range_box *box)
 {
     double variance = 0.0;
 
     for (int i = 0; i < box->len; i++) {
         const struct color_ref *ref = s->refs[box->start + i];
-        variance += diff(ref->color, box->color) * ref->count;
+        const struct Lab lab0 = ff_srgb_u8_to_oklab(ref->color);
+        const struct Lab lab1 = ff_srgb_u8_to_oklab(box->color);
+        const float dL = lab0.L - lab1.L;
+        const float da = lab0.a - lab1.a;
+        const float db = lab0.b - lab1.b;
+
+        variance += (dL*dL + da*da + db*db) * ref->count;
+
+        /*
+         * No need to normalize the per-axis variances since they are compared
+         * only locally within the box and thus share the same weight.
+         */
+        box->axis_variance[0] += dL*dL * ref->count;
+        box->axis_variance[1] += da*da * ref->count;
+        box->axis_variance[2] += db*db * ref->count;
     }
+
     /*
      * The variance is computed as a Mean Squared Error of the distance of the
      * current color to the box color average, with an important difference:
@@ -198,6 +204,7 @@ static int get_next_box_id_to_split(PaletteGenContext *s)
             }
         } else {
             box->variance = -1.0;
+            memset(box->axis_variance, 0, sizeof(box->axis_variance));
         }
     }
     return best_box_id;
@@ -249,6 +256,8 @@ static void split_box(PaletteGenContext *s, struct range_box *box, int n)
     new_box->color = get_avg_color(s->refs, new_box);
     box->variance     = -1.0;
     new_box->variance = -1.0;
+    memset(box->axis_variance, 0, sizeof(box->axis_variance));
+    memset(new_box->axis_variance, 0, sizeof(new_box->axis_variance));
 }
 
 /**
@@ -346,38 +355,34 @@ static AVFrame *get_palette_frame(AVFilterContext *ctx)
     box->sorted_by = -1;
     box->color = get_avg_color(s->refs, box);
     box->variance = -1.0;
+    memset(box->axis_variance, 0, sizeof(box->axis_variance));
+    compute_box_variance(s, box);
     s->nb_boxes = 1;
 
     while (box && box->len > 1) {
         int i, longest;
-        double Lr, ar, br;
+        double Lv, av, bv;
         uint64_t median, box_weight = 0;
 
         /* compute the box weight (sum all the weights of the colors in the
-         * range) and its boundings */
-        float min[3] = {FLT_MAX, FLT_MAX, FLT_MAX};
-        float max[3] = {-FLT_MAX, -FLT_MAX, -FLT_MAX};
+         * range) */
         for (i = box->start; i < box->start + box->len; i++) {
             const struct color_ref *ref = s->refs[i];
-            const struct Lab lab = ref->lab;
-            min[0] = FFMIN(lab.L, min[0]), max[0] = FFMAX(lab.L, max[0]);
-            min[1] = FFMIN(lab.a, min[1]), max[1] = FFMAX(lab.a, max[1]);
-            min[2] = FFMIN(lab.b, min[2]), max[2] = FFMAX(lab.b, max[2]);
             box_weight += ref->count;
         }
 
-        /* define the axis to sort by according to the widest range of colors */
-        Lr = max[0] - min[0];
-        ar = max[1] - min[1];
-        br = max[2] - min[2];
+        /* pick the axis with the biggest variance */
+        Lv = box->axis_variance[0];
+        av = box->axis_variance[1];
+        bv = box->axis_variance[2];
         longest = 0;
-        if (br >= Lr && br >= ar) longest = 2;
-        if (ar >= Lr && ar >= br) longest = 1;
-        if (Lr >= ar && Lr >= br) longest = 0;
+        if (bv >= Lv && bv >= av) longest = 2;
+        if (av >= Lv && av >= bv) longest = 1;
+        if (Lv >= av && Lv >= bv) longest = 0;
 
-        ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" ranges:[%.3f %.3f %.3f] sort by %c (already sorted:%c) ",
+        ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" var:[%.3f %.3f %.3f] sort by %c (already sorted:%c) ",
                 box_id, box->start, box->start + box->len - 1, box->len, box_weight,
-                Lr, ar, br, "Lab"[longest], box->sorted_by == longest ? 'y':'n');
+                Lv, av, bv, "Lab"[longest], box->sorted_by == longest ? 'y':'n');
 
         /* sort the range by its longest axis if it's not already sorted */
         if (box->sorted_by != longest) {
diff --git a/tests/ref/fate/filter-palettegen-1 b/tests/ref/fate/filter-palettegen-1
index 7b7ce98b76..35730a659f 100644
--- a/tests/ref/fate/filter-palettegen-1
+++ b/tests/ref/fate/filter-palettegen-1
@@ -3,4 +3,4 @@
 #codec_id 0: rawvideo
 #dimensions 0: 16x16
 #sar 0: 1/1
-0,          0,          0,        1,     1024, 0xf1fb64c1
+0,          0,          0,        1,     1024, 0xd8fd2c22
diff --git a/tests/ref/fate/filter-palettegen-2 b/tests/ref/fate/filter-palettegen-2
index b856a79273..548902fed0 100644
--- a/tests/ref/fate/filter-palettegen-2
+++ b/tests/ref/fate/filter-palettegen-2
@@ -3,4 +3,4 @@
 #codec_id 0: rawvideo
 #dimensions 0: 16x16
 #sar 0: 1/1
-0,          0,          0,        1,     1024, 0xe84a671a
+0,          0,          0,        1,     1024, 0xd1f29072
-- 
2.38.1

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".