@@ -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) {
@@ -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
@@ -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