From patchwork Tue Oct 10 21:41:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Bjorn Roche X-Patchwork-Id: 5521 Delivered-To: ffmpegpatchwork@gmail.com Received: by 10.2.161.90 with SMTP id m26csp23154jah; Tue, 10 Oct 2017 14:49:14 -0700 (PDT) X-Received: by 10.223.129.198 with SMTP id 64mr12925481wra.59.1507672154538; Tue, 10 Oct 2017 14:49:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1507672154; cv=none; d=google.com; s=arc-20160816; b=NcDLt3UbIJNEPadjrp20ORpJn2IkY/sQAItfNGAeGKQ0tcsQRf/zt4AcL0uFQzFdYg HFgo6ewbxLa7G+zT7tP5vHMJCnwk/Pk5WqcbBR/6Iorfu3ss+gO3WgBARXVkDP21W8Bk XQOXMZwd1s2iefEshMFxzQO98AICfw37H1uEbRn1VqAwox6MyNA5n07hvu1vJnrga1Yk g3mEp7BSktpn35Rq2ecEsv6WHbMtB4g4hQT4/PYKQTC1B5OzWP8AzTdFRVN1QE+gcCvZ dTWoWqeB7dV4iL2wZZG/AUWVwHNW/qoAJMOEvaiZbuCgcvjSsr9yT5JKceseQBydj51f TnvA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:cc:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:mime-version:message-id:date:to:from :dkim-signature:delivered-to:arc-authentication-results; bh=0ZmtY61+OaEnOd48GInjUAwzhGiQgMw4r0p3s+djAoI=; b=WDuG6Z4KppmHBuQ5a2k74mSeaUk78wF0k/A0HJS0x/aIwaTPrCl5CA+kxs52ZZxLks Hxq4Mci8l+ORA3qq8lFRv9nEMro69SgFpv9DZHt/HNmlB+0ellA9VQKNt3TCE1JBI5Mc ExR+gTXXYv60iy9hLOSueFAovld8iT4NwqMZkZwsr0vpJOSnvTrD3/t9mN+9S59ptIEu dgLm+xc2gTKH9cY/6u1ALlFnqNxg9uol7cJ+Tp8g+/QUZwPLHk7vTESEeUb/mrra8QIf wJqCp8p4KwIHXYSDUKM2LJQF4V9AZc9HxEqU4t4pzM/cbW7j2sk0kVSrHqrnMZ6S0gtU y4zQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@giphy.com header.s=google header.b=SZIodS0q; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id c9si9107964wrf.90.2017.10.10.14.49.13; Tue, 10 Oct 2017 14:49:14 -0700 (PDT) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@giphy.com header.s=google header.b=SZIodS0q; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 5F183689AFC; Wed, 11 Oct 2017 00:49:08 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-qt0-f180.google.com (mail-qt0-f180.google.com [209.85.216.180]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 1FAF1689AA9 for ; Wed, 11 Oct 2017 00:49:01 +0300 (EEST) Received: by mail-qt0-f180.google.com with SMTP id 34so38692116qtb.13 for ; Tue, 10 Oct 2017 14:49:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=giphy.com; s=google; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=jidkb3N+uw33gvb+ZJmyIvd279FAC9Xx0R00m4SqP3w=; b=SZIodS0q13rFtFejxg1HNLZ8KgZd4Gg6qOPb5HNwaPU7sbLyhmLT5ZaCl5xB2KqKqb NC9ol+pPHwrROINApcEPKFzihci64NOg7MZ/C/4LjaQ3WA7sBSLuhDtomT9dKu41Spof zlb0ingSnLNAf3wNfaWu/A5M0qVY+5PzmJI7c= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=jidkb3N+uw33gvb+ZJmyIvd279FAC9Xx0R00m4SqP3w=; b=jsqwM3w7/bEYMMAWmMB2nwYCvQqT3i+7fE0zxbIwhmnkUOP9iWBT30f5o9MqYiHesU N21DnMSyEqXhk+gKTt32kVKGI4kBQT+PCrJiEqnNyBUBcX12MRGKEj2Xy9sZlEmpvmWc KMExYXNUlxUrNeGEl5Q5QL5HZZIDMVgqMU39PjsOorJtvp+SDUuauLIV9uBTWiJTtiBw DTF9W2h3FBzKPyDZ20V+8ugQ8AzlZf8eYJOIM9fBwgcduPTTzP/hzfzT8eYUttaQdH/k vDLDz/QykBLLQaLUM/KR3M150z7Gem/UD4XG5/3YkkA+c9sPH7VPPc6vMYS9grhdZhIH VBhw== X-Gm-Message-State: AMCzsaWtJyMxZqQMsxlAkW/SN6BnfGEh4A5/EIgt4rUOvyU+2tr1pc4z lQHlixzvMY54p6BVtVG2r+bEG24ZCFI= X-Google-Smtp-Source: AOwi7QBHloXLm4BBiZWQfztDVy9BLuzFWU0GQcCNcycQVL3unBcQHTNfMYxQqoUOksZjy3PMWEqVvQ== X-Received: by 10.200.33.235 with SMTP id 40mr21360606qtz.185.1507671694896; Tue, 10 Oct 2017 14:41:34 -0700 (PDT) Received: from localhost.localdomain ([208.184.100.82]) by smtp.gmail.com with ESMTPSA id x68sm6868491qkc.84.2017.10.10.14.41.34 (version=TLS1 cipher=AES128-SHA bits=128/128); Tue, 10 Oct 2017 14:41:34 -0700 (PDT) From: Bjorn Roche To: ffmpeg-devel@ffmpeg.org Date: Tue, 10 Oct 2017 17:41:20 -0400 Message-Id: <20171010214120.94254-1-bjorn@giphy.com> X-Mailer: git-send-email 2.14.1 MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH] Fix for paletteuse to support transparency X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: Bjorn Roche Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Partial fix for https://trac.ffmpeg.org/ticket/4443 (Animated GIFs are incorrectly optimized, so they still won’t be output correctly). --- libavfilter/vf_paletteuse.c | 210 ++++++++++++++++++++++++++++---------------- 1 file changed, 132 insertions(+), 78 deletions(-) diff --git a/libavfilter/vf_paletteuse.c b/libavfilter/vf_paletteuse.c index 79a0672891..837529998e 100644 --- a/libavfilter/vf_paletteuse.c +++ b/libavfilter/vf_paletteuse.c @@ -56,7 +56,7 @@ enum diff_mode { }; struct color_node { - uint8_t val[3]; + uint8_t val[4]; uint8_t palette_id; int split; int left_id, right_id; @@ -86,6 +86,8 @@ typedef struct PaletteUseContext { struct cache_node cache[CACHE_SIZE]; /* lookup cache */ struct color_node map[AVPALETTE_COUNT]; /* 3D-Tree (KD-Tree with K=3) for reverse colormap */ uint32_t palette[AVPALETTE_COUNT]; + int transparency_index; /* index in the palette of transparency. -1 if there isn't a transparency. */ + int trans_thresh; int palette_loaded; int dither; int new; @@ -116,6 +118,7 @@ static const AVOption paletteuse_options[] = { { "bayer_scale", "set scale for bayer dithering", OFFSET(bayer_scale), AV_OPT_TYPE_INT, {.i64=2}, 0, 5, FLAGS }, { "diff_mode", "set frame difference mode", OFFSET(diff_mode), AV_OPT_TYPE_INT, {.i64=DIFF_MODE_NONE}, 0, NB_DIFF_MODE-1, FLAGS, "diff_mode" }, { "rectangle", "process smallest different rectangle", 0, AV_OPT_TYPE_CONST, {.i64=DIFF_MODE_RECTANGLE}, INT_MIN, INT_MAX, FLAGS, "diff_mode" }, + { "trans_threshold", "set the threshold for alpha values avoce which they are considered completely opaque", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, }, /* following are the debug options, not part of the official API */ { "debug_kdtree", "save Graphviz graph of the kdtree in specified file", OFFSET(dot_filename), AV_OPT_TYPE_STRING, {.str=NULL}, CHAR_MIN, CHAR_MAX, FLAGS }, @@ -157,34 +160,44 @@ static int query_formats(AVFilterContext *ctx) static av_always_inline int dither_color(uint32_t px, int er, int eg, int eb, int scale, int shift) { - return av_clip_uint8((px >> 16 & 0xff) + ((er * scale) / (1<> 24 ) << 24 + | av_clip_uint8((px >> 16 & 0xff) + ((er * scale) / (1<> 8 & 0xff) + ((eg * scale) / (1<= trans_thresh && c2[0] >= trans_thresh) { + return dr*dr + dg*dg + db*db; + } else { + return max_diff; + } } -static av_always_inline uint8_t colormap_nearest_bruteforce(const uint32_t *palette, const uint8_t *rgb) +static av_always_inline uint8_t colormap_nearest_bruteforce(const uint32_t *palette, const uint8_t *argb, const int trans_thresh) { int i, pal_id = -1, min_dist = INT_MAX; for (i = 0; i < AVPALETTE_COUNT; i++) { const uint32_t c = palette[i]; - if ((c & 0xff000000) == 0xff000000) { // ignore transparent entry - const uint8_t palrgb[] = { + if ( c >> 24 >= trans_thresh ) { // ignore transparent entry + const uint8_t palargb[] = { + palette[i]>>24 & 0xff, palette[i]>>16 & 0xff, palette[i]>> 8 & 0xff, palette[i] & 0xff, }; - const int d = diff(palrgb, rgb); + const int d = diff(palargb, argb, trans_thresh); if (d < min_dist) { pal_id = i; min_dist = d; @@ -203,13 +216,14 @@ struct nearest_color { static void colormap_nearest_node(const struct color_node *map, const int node_pos, const uint8_t *target, + const int trans_thresh, struct nearest_color *nearest) { const struct color_node *kd = map + node_pos; const int s = kd->split; int dx, nearer_kd_id, further_kd_id; const uint8_t *current = kd->val; - const int current_to_target = diff(target, current); + const int current_to_target = diff(target, current, trans_thresh); if (current_to_target < nearest->dist_sqd) { nearest->node_pos = node_pos; @@ -223,17 +237,17 @@ static void colormap_nearest_node(const struct color_node *map, else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id; if (nearer_kd_id != -1) - colormap_nearest_node(map, nearer_kd_id, target, nearest); + colormap_nearest_node(map, nearer_kd_id, target, trans_thresh, nearest); if (further_kd_id != -1 && dx*dx < nearest->dist_sqd) - colormap_nearest_node(map, further_kd_id, target, nearest); + colormap_nearest_node(map, further_kd_id, target, trans_thresh, nearest); } } -static av_always_inline uint8_t colormap_nearest_recursive(const struct color_node *node, const uint8_t *rgb) +static av_always_inline uint8_t colormap_nearest_recursive(const struct color_node *node, const uint8_t *rgb, const int trans_thresh) { struct nearest_color res = {.dist_sqd = INT_MAX, .node_pos = -1}; - colormap_nearest_node(node, 0, rgb, &res); + colormap_nearest_node(node, 0, rgb, trans_thresh, &res); return node[res.node_pos].palette_id; } @@ -242,7 +256,7 @@ struct stack_node { int dx2; }; -static av_always_inline uint8_t colormap_nearest_iterative(const struct color_node *root, const uint8_t *target) +static av_always_inline uint8_t colormap_nearest_iterative(const struct color_node *root, const uint8_t *target, const int trans_thresh) { int pos = 0, best_node_id = -1, best_dist = INT_MAX, cur_color_id = 0; struct stack_node nodes[16]; @@ -252,7 +266,7 @@ static av_always_inline uint8_t colormap_nearest_iterative(const struct color_no const struct color_node *kd = &root[cur_color_id]; const uint8_t *current = kd->val; - const int current_to_target = diff(target, current); + const int current_to_target = diff(target, current, trans_thresh); /* Compare current color node to the target and update our best node if * it's actually better. */ @@ -314,25 +328,27 @@ end: return root[best_node_id].palette_id; } -#define COLORMAP_NEAREST(search, palette, root, target) \ - search == COLOR_SEARCH_NNS_ITERATIVE ? colormap_nearest_iterative(root, target) : \ - search == COLOR_SEARCH_NNS_RECURSIVE ? colormap_nearest_recursive(root, target) : \ - colormap_nearest_bruteforce(palette, target) +#define COLORMAP_NEAREST(search, palette, root, target, trans_thresh) \ + search == COLOR_SEARCH_NNS_ITERATIVE ? colormap_nearest_iterative(root, target, trans_thresh) : \ + search == COLOR_SEARCH_NNS_RECURSIVE ? colormap_nearest_recursive(root, target, trans_thresh) : \ + colormap_nearest_bruteforce(palette, target, trans_thresh) /** * Check if the requested color is in the cache already. If not, find it in the * color tree and cache it. - * Note: r, g, and b are the component of c but are passed as well to avoid + * Note: a, r, g, and b are the components of argb, but are passed as well to avoid * recomputing them (they are generally computed by the caller for other uses). */ -static av_always_inline int color_get(struct cache_node *cache, uint32_t color, - uint8_t r, uint8_t g, uint8_t b, +static av_always_inline int color_get(struct cache_node *cache, uint32_t argb, + uint8_t a, uint8_t r, uint8_t g, uint8_t b, + int transparency_index, + int trans_thresh, const struct color_node *map, const uint32_t *palette, const enum color_search_method search_method) { int i; - const uint8_t rgb[] = {r, g, b}; + const uint8_t argb_elts[] = {a, r, g, b}; const uint8_t rhash = r & ((1<= 0) { + return transparency_index; + } + for (i = 0; i < node->nb_entries; i++) { e = &node->entries[i]; - if (e->color == color) + if (e->color == argb) return e->pal_entry; } @@ -350,21 +371,25 @@ static av_always_inline int color_get(struct cache_node *cache, uint32_t color, sizeof(*node->entries), NULL); if (!e) return AVERROR(ENOMEM); - e->color = color; - e->pal_entry = COLORMAP_NEAREST(search_method, palette, map, rgb); + e->color = argb; + e->pal_entry = COLORMAP_NEAREST(search_method, palette, map, argb_elts, trans_thresh); + return e->pal_entry; } static av_always_inline int get_dst_color_err(struct cache_node *cache, - uint32_t c, const struct color_node *map, + uint32_t argb, const struct color_node *map, const uint32_t *palette, + int transparency_index, + int trans_thresh, int *er, int *eg, int *eb, const enum color_search_method search_method) { - const uint8_t r = c >> 16 & 0xff; - const uint8_t g = c >> 8 & 0xff; - const uint8_t b = c & 0xff; - const int dstx = color_get(cache, c, r, g, b, map, palette, search_method); + const uint8_t a = argb >> 24 & 0xff; + const uint8_t r = argb >> 16 & 0xff; + const uint8_t g = argb >> 8 & 0xff; + const uint8_t b = argb & 0xff; + const int dstx = color_get(cache, argb, a, r, g, b, transparency_index, trans_thresh, map, palette, search_method); const uint32_t dstc = palette[dstx]; *er = r - (dstc >> 16 & 0xff); *eg = g - (dstc >> 8 & 0xff); @@ -385,6 +410,8 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram const int dst_linesize = out->linesize[0]; uint32_t *src = ((uint32_t *)in ->data[0]) + y_start*src_linesize; uint8_t *dst = out->data[0] + y_start*dst_linesize; + int transparency_index = s->transparency_index; + int trans_thresh = s->trans_thresh; w += x_start; h += y_start; @@ -395,14 +422,14 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram if (dither == DITHERING_BAYER) { const int d = s->ordered_dither[(y & 7)<<3 | (x & 7)]; + const uint8_t a8 = src[x] >> 24 & 0xff; const uint8_t r8 = src[x] >> 16 & 0xff; const uint8_t g8 = src[x] >> 8 & 0xff; const uint8_t b8 = src[x] & 0xff; const uint8_t r = av_clip_uint8(r8 + d); const uint8_t g = av_clip_uint8(g8 + d); const uint8_t b = av_clip_uint8(b8 + d); - const uint32_t c = r<<16 | g<<8 | b; - const int color = color_get(cache, c, r, g, b, map, palette, search_method); + const int color = color_get(cache, src[x], a8, r, g, b, transparency_index, trans_thresh, map, palette, search_method); if (color < 0) return color; @@ -410,7 +437,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_HECKBERT) { const int right = x < w - 1, down = y < h - 1; - const int color = get_dst_color_err(cache, src[x], map, palette, &er, &eg, &eb, search_method); + const int color = get_dst_color_err(cache, src[x], map, palette, transparency_index, trans_thresh, &er, &eg, &eb, search_method); if (color < 0) return color; @@ -422,7 +449,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_FLOYD_STEINBERG) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; - const int color = get_dst_color_err(cache, src[x], map, palette, &er, &eg, &eb, search_method); + const int color = get_dst_color_err(cache, src[x], map, palette, transparency_index, trans_thresh, &er, &eg, &eb, search_method); if (color < 0) return color; @@ -436,7 +463,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_SIERRA2) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; const int right2 = x < w - 2, left2 = x > x_start + 1; - const int color = get_dst_color_err(cache, src[x], map, palette, &er, &eg, &eb, search_method); + const int color = get_dst_color_err(cache, src[x], map, palette, transparency_index, trans_thresh, &er, &eg, &eb, search_method); if (color < 0) return color; @@ -455,7 +482,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_SIERRA2_4A) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; - const int color = get_dst_color_err(cache, src[x], map, palette, &er, &eg, &eb, search_method); + const int color = get_dst_color_err(cache, src[x], map, palette, transparency_index, trans_thresh, &er, &eg, &eb, search_method); if (color < 0) return color; @@ -466,10 +493,11 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 2); } else { + const uint8_t a = src[x] >> 24 & 0xff; const uint8_t r = src[x] >> 16 & 0xff; const uint8_t g = src[x] >> 8 & 0xff; const uint8_t b = src[x] & 0xff; - const int color = color_get(cache, src[x] & 0xffffff, r, g, b, map, palette, search_method); + const int color = color_get(cache, src[x], a, r, g, b, transparency_index, trans_thresh, map, palette, search_method); if (color < 0) return color; @@ -489,19 +517,19 @@ static void disp_node(AVBPrint *buf, int depth) { const struct color_node *node = &map[node_id]; - const uint32_t fontcolor = node->val[0] > 0x50 && - node->val[1] > 0x50 && - node->val[2] > 0x50 ? 0 : 0xffffff; + const uint32_t fontcolor = node->val[1] > 0x50 && + node->val[2] > 0x50 && + node->val[3] > 0x50 ? 0 : 0xffffff; av_bprintf(buf, "%*cnode%d [" "label=\"%c%02X%c%02X%c%02X%c\" " "fillcolor=\"#%02x%02x%02x\" " "fontcolor=\"#%06"PRIX32"\"]\n", depth*INDENT, ' ', node->palette_id, - "[ "[node->split], node->val[0], - "][ "[node->split], node->val[1], - " ]["[node->split], node->val[2], + "[ "[node->split], node->val[1], + "][ "[node->split], node->val[2], + " ]["[node->split], node->val[3], " ]"[node->split], - node->val[0], node->val[1], node->val[2], + node->val[1], node->val[2], node->val[3], fontcolor); if (parent_id != -1) av_bprintf(buf, "%*cnode%d -> node%d\n", depth*INDENT, ' ', @@ -536,7 +564,7 @@ static int disp_tree(const struct color_node *node, const char *fname) return 0; } -static int debug_accuracy(const struct color_node *node, const uint32_t *palette, +static int debug_accuracy(const struct color_node *node, const uint32_t *palette, const int trans_thresh, const enum color_search_method search_method) { int r, g, b, ret = 0; @@ -545,15 +573,15 @@ static int debug_accuracy(const struct color_node *node, const uint32_t *palette for (g = 0; g < 256; g++) { for (b = 0; b < 256; b++) { const uint8_t rgb[] = {r, g, b}; - const int r1 = COLORMAP_NEAREST(search_method, palette, node, rgb); - const int r2 = colormap_nearest_bruteforce(palette, rgb); + const int r1 = COLORMAP_NEAREST(search_method, palette, node, rgb, trans_thresh); + const int r2 = colormap_nearest_bruteforce(palette, rgb, trans_thresh); if (r1 != r2) { const uint32_t c1 = palette[r1]; const uint32_t c2 = palette[r2]; const uint8_t palrgb1[] = { c1>>16 & 0xff, c1>> 8 & 0xff, c1 & 0xff }; const uint8_t palrgb2[] = { c2>>16 & 0xff, c2>> 8 & 0xff, c2 & 0xff }; - const int d1 = diff(palrgb1, rgb); - const int d2 = diff(palrgb2, rgb); + const int d1 = diff(palrgb1, rgb, trans_thresh); + const int d2 = diff(palrgb2, rgb, trans_thresh); if (d1 != d2) { av_log(NULL, AV_LOG_ERROR, "/!\\ %02X%02X%02X: %d ! %d (%06"PRIX32" ! %06"PRIX32") / dist: %d ! %d\n", @@ -584,17 +612,19 @@ static int cmp_##name(const void *pa, const void *pb) \ { \ const struct color *a = pa; \ const struct color *b = pb; \ - return (a->value >> (8 * (2 - (pos))) & 0xff) \ - - (b->value >> (8 * (2 - (pos))) & 0xff); \ + return (a->value >> (8 * (3 - (pos))) & 0xff) \ + - (b->value >> (8 * (3 - (pos))) & 0xff); \ } -DECLARE_CMP_FUNC(r, 0) -DECLARE_CMP_FUNC(g, 1) -DECLARE_CMP_FUNC(b, 2) +DECLARE_CMP_FUNC(a, 0) +DECLARE_CMP_FUNC(r, 1) +DECLARE_CMP_FUNC(g, 2) +DECLARE_CMP_FUNC(b, 3) -static const cmp_func cmp_funcs[] = {cmp_r, cmp_g, cmp_b}; +static const cmp_func cmp_funcs[] = {cmp_a, cmp_r, cmp_g, cmp_b}; static int get_next_color(const uint8_t *color_used, const uint32_t *palette, + const int trans_thresh, int *component, const struct color_rect *box) { int wr, wg, wb; @@ -609,11 +639,16 @@ static int get_next_color(const uint8_t *color_used, const uint32_t *palette, for (i = 0; i < AVPALETTE_COUNT; i++) { const uint32_t c = palette[i]; + const uint8_t a = c >> 24 & 0xff; const uint8_t r = c >> 16 & 0xff; const uint8_t g = c >> 8 & 0xff; const uint8_t b = c & 0xff; - if (color_used[i] || + if (a < trans_thresh) { + continue; + } + + if (color_used[i] || (a != 0xff) || r < box->min[0] || g < box->min[1] || b < box->min[2] || r > box->max[0] || g > box->max[1] || b > box->max[2]) continue; @@ -639,9 +674,9 @@ static int get_next_color(const uint8_t *color_used, const uint32_t *palette, wr = ranges.max[0] - ranges.min[0]; wg = ranges.max[1] - ranges.min[1]; wb = ranges.max[2] - ranges.min[2]; - if (wr >= wg && wr >= wb) longest = 0; - if (wg >= wr && wg >= wb) longest = 1; - if (wb >= wr && wb >= wg) longest = 2; + if (wr >= wg && wr >= wb) longest = 1; + if (wg >= wr && wg >= wb) longest = 2; + if (wb >= wr && wb >= wg) longest = 3; cmpf = cmp_funcs[longest]; *component = longest; @@ -655,6 +690,7 @@ static int colormap_insert(struct color_node *map, uint8_t *color_used, int *nb_used, const uint32_t *palette, + const int trans_thresh, const struct color_rect *box) { uint32_t c; @@ -662,7 +698,7 @@ static int colormap_insert(struct color_node *map, int node_left_id = -1, node_right_id = -1; struct color_node *node; struct color_rect box1, box2; - const int pal_id = get_next_color(color_used, palette, &component, box); + const int pal_id = get_next_color(color_used, palette, trans_thresh, &component, box); if (pal_id < 0) return -1; @@ -673,21 +709,22 @@ static int colormap_insert(struct color_node *map, node = &map[cur_id]; node->split = component; node->palette_id = pal_id; - node->val[0] = c>>16 & 0xff; - node->val[1] = c>> 8 & 0xff; - node->val[2] = c & 0xff; + node->val[0] = c>>24 & 0xff; + node->val[1] = c>>16 & 0xff; + node->val[2] = c>> 8 & 0xff; + node->val[3] = c & 0xff; color_used[pal_id] = 1; /* get the two boxes this node creates */ box1 = box2 = *box; - box1.max[component] = node->val[component]; - box2.min[component] = node->val[component] + 1; + box1.max[component-1] = node->val[component]; + box2.min[component-1] = node->val[component] + 1; - node_left_id = colormap_insert(map, color_used, nb_used, palette, &box1); + node_left_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box1); - if (box2.min[component] <= box2.max[component]) - node_right_id = colormap_insert(map, color_used, nb_used, palette, &box2); + if (box2.min[component-1] <= box2.max[component-1]) + node_right_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box2); node->left_id = node_left_id; node->right_id = node_right_id; @@ -711,6 +748,16 @@ static void load_colormap(PaletteUseContext *s) /* disable transparent colors and dups */ qsort(s->palette, AVPALETTE_COUNT, sizeof(*s->palette), cmp_pal_entry); + // update transparency index: + if (s->transparency_index >= 0) { + for (i = 0; i < AVPALETTE_COUNT; i++) { + if ((s->palette[i]>>24 & 0xff) == 0) { + s->transparency_index = i; // we are assuming at most one transparent color in palette + break; + } + } + } + for (i = 0; i < AVPALETTE_COUNT; i++) { const uint32_t c = s->palette[i]; if (i != 0 && c == last_color) { @@ -718,7 +765,7 @@ static void load_colormap(PaletteUseContext *s) continue; } last_color = c; - if ((c & 0xff000000) != 0xff000000) { + if ( c >> 24 < s->trans_thresh ) { color_used[i] = 1; // ignore transparent color(s) continue; } @@ -727,13 +774,13 @@ static void load_colormap(PaletteUseContext *s) box.min[0] = box.min[1] = box.min[2] = 0x00; box.max[0] = box.max[1] = box.max[2] = 0xff; - colormap_insert(s->map, color_used, &nb_used, s->palette, &box); + colormap_insert(s->map, color_used, &nb_used, s->palette, s->trans_thresh, &box); if (s->dot_filename) disp_tree(s->map, s->dot_filename); if (s->debug_accuracy) { - if (!debug_accuracy(s->map, s->palette, s->color_search_method)) + if (!debug_accuracy(s->map, s->palette, s->trans_thresh, s->color_search_method)) av_log(NULL, AV_LOG_INFO, "Accuracy check passed\n"); } } @@ -756,7 +803,7 @@ static void debug_mean_error(PaletteUseContext *s, const AVFrame *in1, const uint32_t c2 = palette[src2[x]]; const uint8_t rgb1[] = {c1 >> 16 & 0xff, c1 >> 8 & 0xff, c1 & 0xff}; const uint8_t rgb2[] = {c2 >> 16 & 0xff, c2 >> 8 & 0xff, c2 & 0xff}; - mean_err += diff(rgb1, rgb2); + mean_err += diff(rgb1, rgb2, s->trans_thresh); } src1 += src1_linesize; src2 += src2_linesize; @@ -941,6 +988,8 @@ static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame) const uint32_t *p = (const uint32_t *)palette_frame->data[0]; const int p_linesize = palette_frame->linesize[0] >> 2; + s->transparency_index = -1; + if (s->new) { memset(s->palette, 0, sizeof(s->palette)); memset(s->map, 0, sizeof(s->map)); @@ -951,8 +1000,13 @@ static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame) i = 0; for (y = 0; y < palette_frame->height; y++) { - for (x = 0; x < palette_frame->width; x++) - s->palette[i++] = p[x]; + for (x = 0; x < palette_frame->width; x++) { + s->palette[i] = p[x]; + if (p[x]>>24 < s->trans_thresh) { + s->transparency_index = i; // we are assuming at most one transparent color in palette + } + ++i; + } p += p_linesize; }