[FFmpeg-devel] Fix for paletteuse to support transparency

Submitted by Bjorn Roche on Oct. 19, 2017, 10 p.m.

Details

Message ID 20171019220052.26794-1-bjorn@giphy.com
State New
Headers show

Commit Message

Bjorn Roche Oct. 19, 2017, 10 p.m.
The palettes generated by palettegen include one transparent color.
This patch enables paletteuse to identify the transparency in incoming
video and tag transparent pixels on outgoing video.

This requires tracking the transparency index in the palette,
establishing an alpha threshold below which a pixel is considered
transparent and above which the pixel is considered opaque, and
additional changes to track the alpha value throught the conversion
process. If the format of a color variable has changed in this patch,
an effort was also made to change the variable name for clarity.

This change is a partial fix for https://trac.ffmpeg.org/ticket/4443
However, animated GIFs are still output incorrectly due to a bug
in gif optimization which does not correctly handle transparency.
---
 libavfilter/vf_paletteuse.c | 210 ++++++++++++++++++++++++++++----------------
 1 file changed, 132 insertions(+), 78 deletions(-)

Comments

Carl Eugen Hoyos Oct. 19, 2017, 10:35 p.m.
2017-10-20 0:00 GMT+02:00 Bjorn Roche <bjorn@giphy.com>:
> The palettes generated by palettegen include one transparent color.
> This patch enables paletteuse to identify the transparency in incoming
> video and tag transparent pixels on outgoing video.
>
> This requires tracking the transparency index in the palette,
> establishing an alpha threshold below which a pixel is considered
> transparent and above which the pixel is considered opaque, and
> additional changes to track the alpha value throught the conversion
> process. If the format of a color variable has changed in this patch,
> an effort was also made to change the variable name for clarity.
>
> This change is a partial fix for https://trac.ffmpeg.org/ticket/4443
> However, animated GIFs are still output incorrectly due to a bug
> in gif optimization which does not correctly handle transparency.

If Clément doesn't comment, I will probably push this in a few days.

Carl Eugen
Clément Bœsch Oct. 20, 2017, 6:43 a.m.
On Fri, Oct 20, 2017 at 12:35:00AM +0200, Carl Eugen Hoyos wrote:
> 2017-10-20 0:00 GMT+02:00 Bjorn Roche <bjorn@giphy.com>:
> > The palettes generated by palettegen include one transparent color.
> > This patch enables paletteuse to identify the transparency in incoming
> > video and tag transparent pixels on outgoing video.
> >
> > This requires tracking the transparency index in the palette,
> > establishing an alpha threshold below which a pixel is considered
> > transparent and above which the pixel is considered opaque, and
> > additional changes to track the alpha value throught the conversion
> > process. If the format of a color variable has changed in this patch,
> > an effort was also made to change the variable name for clarity.
> >
> > This change is a partial fix for https://trac.ffmpeg.org/ticket/4443
> > However, animated GIFs are still output incorrectly due to a bug
> > in gif optimization which does not correctly handle transparency.
> 
> If Clément doesn't comment, I will probably push this in a few days.
> 

I need a little more time. I don't think I can do this today, but tomorrow
might be OK.

Sorry about the delay.
Moritz Barsnick Oct. 20, 2017, 5:52 p.m.
On Thu, Oct 19, 2017 at 18:00:52 -0400, Bjorn Roche wrote:
> +    { "threshold", "set the alpha threshold for transparency. Above this threshold, pixels are considered opaque, below they are considered transparent.", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, },

This seems a bit verbose. The longer texts belongs into
doc/filters.texi, where you need to document this option anyway.

> +        if ( c >> 24 >= trans_thresh ) { // ignore transparent entry

No whitespace next to the brackets, please.

> -        if ((c & 0xff000000) != 0xff000000) {
> +        if ( c >> 24 < s->trans_thresh ) {

Same here.

Moritz
Clément Bœsch Oct. 21, 2017, 4:40 p.m.
> Re: [FFmpeg-devel] [PATCH] Fix for paletteuse to support transparency

The commit message needs adjustment "lavfi/paletteuse: ..."

[...]
>  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. */

"if there is no transparent color" might be more correct but I'm not a
native speaker.

> +    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" },

> +    { "threshold", "set the alpha threshold for transparency. Above this threshold, pixels are considered opaque, below they are considered transparent.", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, },

The long explanation belongs in doc/filters.texi

[...]
> -static av_always_inline int diff(const uint8_t *c1, const uint8_t *c2)
> +static av_always_inline int diff(const uint8_t *c1, const uint8_t *c2, const int trans_thresh)
>  {
>      // XXX: try L*a*b with CIE76 (dL*dL + da*da + db*db)
> -    const int dr = c1[0] - c2[0];
> -    const int dg = c1[1] - c2[1];
> -    const int db = c1[2] - c2[2];
> -    return dr*dr + dg*dg + db*db;

> +    const static int max_diff = 195075; //equal to 255*255 + 255*255 + 255*255

That's not what I meant; I wasn't concerned about the expression but the
static const int. I was thinking "return 255*255 + 255*255 + 255*255"

[...]
>  /**
>   * 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,

I'm sorry to insist, but renaming "color" belongs in another commit.

[...]
>  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,

ditto, "c" should be renamed in another commit

[...]
>      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;

i++ is the appropriate idiom.

Aside from these nitpicks, I'm still concerned about how it's going to
conflict with GIF encoding where the transparent color is actually used as
a mean of not updating pixels from previous frames.
Carl Eugen Hoyos Oct. 21, 2017, 7:37 p.m.
2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:

> Aside from these nitpicks, I'm still concerned about how it's going
> to conflict with GIF encoding where the transparent color is actually
> used as a mean of not updating pixels from previous frames.

But is this really related to this patch?
I just tested the following and see some issues:
$ ffmpeg -i http://solvedproblems.hydex11.net/old/Images/apng/firefox.png
out.gif

Thank you, Carl Eugen
Clément Bœsch Oct. 21, 2017, 7:43 p.m.
On Sat, Oct 21, 2017 at 09:37:06PM +0200, Carl Eugen Hoyos wrote:
> 2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:
> 
> > Aside from these nitpicks, I'm still concerned about how it's going
> > to conflict with GIF encoding where the transparent color is actually
> > used as a mean of not updating pixels from previous frames.
> 
> But is this really related to this patch?

Maybe not, but we need to keep that in mind and not make a hasty decision
wrt how we handle the transparency, because it might makes future related
development much harder.

[...]
Carl Eugen Hoyos Oct. 21, 2017, 7:47 p.m.
2017-10-21 21:43 GMT+02:00 Clément Bœsch <u@pkh.me>:
> On Sat, Oct 21, 2017 at 09:37:06PM +0200, Carl Eugen Hoyos wrote:
>> 2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:
>>
>> > Aside from these nitpicks, I'm still concerned about how it's going
>> > to conflict with GIF encoding where the transparent color is actually
>> > used as a mean of not updating pixels from previous frames.
>>
>> But is this really related to this patch?
>
> Maybe not, but we need to keep that in mind and not make a
> hasty decision wrt how we handle the transparency, because
> it might makes future related development much harder.

Given that this is a libavfilter-only patch and we can reproduce
the issue without using libavfilter, I am not completely
convinced, but this is of course your decision.

Thank you, Carl Eugen
Clément Bœsch Oct. 21, 2017, 8 p.m.
On Sat, Oct 21, 2017 at 09:47:47PM +0200, Carl Eugen Hoyos wrote:
> 2017-10-21 21:43 GMT+02:00 Clément Bœsch <u@pkh.me>:
> > On Sat, Oct 21, 2017 at 09:37:06PM +0200, Carl Eugen Hoyos wrote:
> >> 2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:
> >>
> >> > Aside from these nitpicks, I'm still concerned about how it's going
> >> > to conflict with GIF encoding where the transparent color is actually
> >> > used as a mean of not updating pixels from previous frames.
> >>
> >> But is this really related to this patch?
> >
> > Maybe not, but we need to keep that in mind and not make a
> > hasty decision wrt how we handle the transparency, because
> > it might makes future related development much harder.
> 
> Given that this is a libavfilter-only patch and we can reproduce
> the issue without using libavfilter, I am not completely
> convinced, but this is of course your decision.
> 

Yes it should be fine, I just want to be sure that using
palettegen/paletteuse will not create input streams that the limited GIF
encoder does not handle well because it doesn't make a difference between
"transparency flavours". If paletteuse starts inserting transparent colors
that are not meant to be used for the frame-diff system it could become a
problem.

In any case, I'll probably apply the patch at the next version, I'm just
not exactly comfortable with that part.
Bjorn Roche Oct. 23, 2017, 11:17 p.m.
On Sat, Oct 21, 2017 at 4:00 PM, Clément Bœsch <u@pkh.me> wrote:

> On Sat, Oct 21, 2017 at 09:47:47PM +0200, Carl Eugen Hoyos wrote:
> > 2017-10-21 21:43 GMT+02:00 Clément Bœsch <u@pkh.me>:
> > > On Sat, Oct 21, 2017 at 09:37:06PM +0200, Carl Eugen Hoyos wrote:
> > >> 2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:
> > >>
> > >> > Aside from these nitpicks, I'm still concerned about how it's going
> > >> > to conflict with GIF encoding where the transparent color is
> actually
> > >> > used as a mean of not updating pixels from previous frames.
> > >>
> > >> But is this really related to this patch?
> > >
> > > Maybe not, but we need to keep that in mind and not make a
> > > hasty decision wrt how we handle the transparency, because
> > > it might makes future related development much harder.
> >
> > Given that this is a libavfilter-only patch and we can reproduce
> > the issue without using libavfilter, I am not completely
> > convinced, but this is of course your decision.
> >
>
> Yes it should be fine, I just want to be sure that using
> palettegen/paletteuse will not create input streams that the limited GIF
> encoder does not handle well because it doesn't make a difference between
> "transparency flavours". If paletteuse starts inserting transparent colors
> that are not meant to be used for the frame-diff system it could become a
> problem.
>

There is a bug in the GIF encoder. I have a fix for that issue as well.

In the meantime, I have submitted another patch to address the concerns
that are specific to this fix.

bjorn
Bjorn Roche Oct. 24, 2017, 4:44 p.m.
On Mon, Oct 23, 2017 at 7:17 PM, Bjorn Roche <bjorn@giphy.com> wrote:

> On Sat, Oct 21, 2017 at 4:00 PM, Clément Bœsch <u@pkh.me> wrote:
>
>> On Sat, Oct 21, 2017 at 09:47:47PM +0200, Carl Eugen Hoyos wrote:
>> > 2017-10-21 21:43 GMT+02:00 Clément Bœsch <u@pkh.me>:
>> > > On Sat, Oct 21, 2017 at 09:37:06PM +0200, Carl Eugen Hoyos wrote:
>> > >> 2017-10-21 18:40 GMT+02:00 Clément Bœsch <u@pkh.me>:
>> > >>
>> > >> > Aside from these nitpicks, I'm still concerned about how it's going
>> > >> > to conflict with GIF encoding where the transparent color is
>> actually
>> > >> > used as a mean of not updating pixels from previous frames.
>> > >>
>> > >> But is this really related to this patch?
>> > >
>> > > Maybe not, but we need to keep that in mind and not make a
>> > > hasty decision wrt how we handle the transparency, because
>> > > it might makes future related development much harder.
>> >
>> > Given that this is a libavfilter-only patch and we can reproduce
>> > the issue without using libavfilter, I am not completely
>> > convinced, but this is of course your decision.
>> >
>>
>> Yes it should be fine, I just want to be sure that using
>> palettegen/paletteuse will not create input streams that the limited GIF
>> encoder does not handle well because it doesn't make a difference between
>> "transparency flavours". If paletteuse starts inserting transparent colors
>> that are not meant to be used for the frame-diff system it could become a
>> problem.
>>
>
> There is a bug in the GIF encoder. I have a fix for that issue as well.
>

Okay, I've submitted that as well. Still need some feedback, but I believe
it's close.

Patch hide | download patch | download mbox

diff --git a/libavfilter/vf_paletteuse.c b/libavfilter/vf_paletteuse.c
index 79a0672891..fa5897b7f3 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" },
+    { "threshold", "set the alpha threshold for transparency. Above this threshold, pixels are considered opaque, below they are considered transparent.", 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<<shift))) << 16
+    return av_clip_uint8( px >> 24                                      ) << 24
+         | av_clip_uint8((px >> 16 & 0xff) + ((er * scale) / (1<<shift))) << 16
          | av_clip_uint8((px >>  8 & 0xff) + ((eg * scale) / (1<<shift))) <<  8
          | av_clip_uint8((px       & 0xff) + ((eb * scale) / (1<<shift)));
 }
 
-static av_always_inline int diff(const uint8_t *c1, const uint8_t *c2)
+static av_always_inline int diff(const uint8_t *c1, const uint8_t *c2, const int trans_thresh)
 {
     // XXX: try L*a*b with CIE76 (dL*dL + da*da + db*db)
-    const int dr = c1[0] - c2[0];
-    const int dg = c1[1] - c2[1];
-    const int db = c1[2] - c2[2];
-    return dr*dr + dg*dg + db*db;
+    const static int max_diff = 195075; //equal to 255*255 + 255*255 + 255*255
+    const int dr = c1[1] - c2[1];
+    const int dg = c1[2] - c2[2];
+    const int db = c1[3] - c2[3];
+
+    if (c1[0] < trans_thresh && c2[0] < trans_thresh) {
+        return 0;
+    } else if (c1[0] >= 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<<NBITS)-1);
     const uint8_t ghash = g & ((1<<NBITS)-1);
     const uint8_t bhash = b & ((1<<NBITS)-1);
@@ -340,9 +356,14 @@  static av_always_inline int color_get(struct cache_node *cache, uint32_t color,
     struct cache_node *node = &cache[hash];
     struct cached_color *e;
 
+    // first, check for transparency
+    if (a < trans_thresh && transparency_index >= 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;
     }