possible bug -remap IM 6.7.3.1 Q16

Post any defects you find in the released or beta versions of the ImageMagick software here. Include the ImageMagick version, OS, and any command-line required to reproduce the problem. Got a patch for a bug? Post it here.
Post Reply
User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-15T15:02:22-07:00

IM 6.7.3.1 Q16 Mac OSX Tiger

I believe that -remap is not accurately remapping according to a proper 3D color distance measure. I don't know if this is an inaccuracy in the current method, a bug, or just the way -remap works currently. Can someone clarify this for me?

Take the following image and colortable image:

Image

Image


Using IM as follows, I get:

convert 1cute_cat.png +dither -colors 24 -remap 1palette_96.png 1cute_cat_c24_im_remap.gif

Image

NOTE: the purple coloring


Using my script, which uses the formula, I get

dist=sqrt( (r1-r2)*(r1-r2)+(g1-g2)*(g1-g2)+(b1-b2)*(b1-b2)

Image

User avatar
magick
Site Admin
Posts: 10698
Joined: 2003-05-31T11:32:55-07:00

Re: possible bug -remap IM 6.7.3.1 Q16

Post by magick » 2011-10-16T06:19:31-07:00

The remap algorithm select colors from this palette:
  • convert 1palette_96.png +dither -colors 24 palette.gif
    identify -verbose palette.gif
  • 0: ( 25, 33, 31) #19211F rgb(25,33,31)
    1: ( 83, 54, 46) #53362E rgb(83,54,46)
    2: ( 93, 83, 42) #5D532A rgb(93,83,42)
    3: ( 28, 36, 85) #1C2455 rgb(28,36,85)
    4: ( 21, 79, 81) #154F51 rgb(21,79,81)
    5: (104, 92, 95) #685C5F rgb(104,92,95)
    6: ( 89, 55,109) #59376D rgb(89,55,109)
    7: (150, 86, 57) #965639 rgb(150,86,57)
    8: (158, 99, 91) #9E635B rgb(158,99,91)
    9: (228, 93, 86) #E45D56 rgb(228,93,86)
    10: (155, 40, 64) #9B2840 rgb(155,40,64)
    11: ( 61,166, 63) #3DA63F rgb(61,166,63)
    12: (196,150, 96) #C49660 rgb(196,150,96)
    13: (199,165, 61) #C7A53D rgb(199,165,61)
    14: ( 30, 97,156) #1E619C rgb(30,97,156)
    15: (121, 91,167) #795BA7 rgb(121,91,167)
    16: (217, 91,173) #D95BAD rgb(217,91,173)
    17: (151, 92,166) #975CA6 rgb(151,92,166)
    18: ( 0,193,151) #00C197 rgb(0,193,151)
    19: ( 29,160,201) #1DA0C9 rgb(29,160,201)
    20: (166,163,159) #A6A39F rgb(166,163,159)
    21: (242,170,136) #F2AA88 rgb(242,170,136)
    22: (213,211,212) #D5D3D4 rgb(213,211,212)
    23: (238,208,180) #EED0B4 rgb(238,208,180)
Is your algorithm using the same palette?

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-16T10:54:15-07:00

Thanks. That is the problem. My script is using the same mapimage (1palette_96.png), but I did not remember that -colors extended to the -remap process. Dumb on my part, I should have realized that :oops: . Sorry again for the false alarm.

I was using

convert convert 1cute_cat.png +dither -colors 24 -remap 1palette_96.png 1cute_cat_c24_im_remap.gif



However, I have tried several things until I got it right, but don't understand why the first two do not work.

1) -respect-parenthesis does not work

convert -respect-parenthesis \( 1cute_cat.png +dither -colors 24 \) \
+dither -remap 1palette_96.png 1cute_cat_c24_im_remap2.gif

Image


2) +colors followed by +dither does not work

convert \( 1cute_cat.png +dither -colors 24 \) \
+colors +dither -remap 1palette_96.png 1cute_cat_c24_im_remap3.gif

Image


3) +dither followed by +colors does work

convert \( 1cute_cat.png +dither -colors 24 \) \
+dither +colors -remap 1palette_96.png 1cute_cat_c24_im_remap4.gif

Image

The last matches my script result from above perfectly.

compare -metric rmse 1cute_cat_c24_im_remap4.gif 1cute_cat_remap4.gif null:
0 (0)


But can you explain why methods 1) and 2) above do not work. I did not think the order of +dither and +colors would make a difference

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-16T13:34:38-07:00

Please see the message above first.

Sorry to belabor this, but it is getting more confusing. For another image, I have to add an additional +dither to get the remap to work at all.

Here is the original:
Image

This case has -remap with no effect whatsoever.

convert \( 1cropped.jpeg +dither -colors 24 -write 1cropped_im_remap_test1a.gif \) \
+dither +colors -remap 1paintapic_palette.png 1cropped_im_remap_test2a.gif
convert 1cropped_im_remap_test2a.gif -format "%k" info:

After -colors 24
Image

After -remap (still 24 colors)
Image

convert 1cropped_im_remap_test2a.gif -format "%k" info:
24



This works fine:

convert \( 1cropped.jpeg +dither -colors 24 -write 1cropped_im_remap_test1b.gif \) \
+dither +colors +dither -remap 1paintapic_palette.png 1cropped_im_remap_test2b.gif
convert 1cropped_im_remap_test2b.gif -format "%k" info:

After -colors 24
Image


After -remap (19 colors)
Image

convert 1cropped_im_remap_test2b.gif -format "%k" info:
19


What am I not understanding about -colors and -remap used together, regarding +dither and +colors?


___________

P.S. OK this may be resolved by adding -depth 8 before the -remap.

This works.


convert \( 1cropped.jpeg +dither -colors 24 -write 1cropped_im_remap_test1c.gif \) \
-depth 8 +dither -remap 1paintapic_palette.png 1cropped_im_remap_test2c.gif
convert 1cropped_im_remap_test2c.gif -format "%k" info:


However, the following post is still not resolved by adding -depth 8.
Last edited by fmw42 on 2011-10-16T18:27:00-07:00, edited 3 times in total.

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-16T13:46:24-07:00

See above 2 posts. Sorry to belabor this.

With this last image example, I am getting different results from -remap than with my script.

With -remap:

convert \( 1cropped.jpeg +dither -colors 24 \) \
+dither +colors +dither -remap 1paintapic_palette.png 1cropped_im_remap_test2b.gif
convert 1cropped_im_remap_test2b.gif -format "%k" info:
19

or

convert \( 1cropped.jpeg +dither -colors 24 -depth 8 -write 1cropped_im_remap_test1b.gif \) \
-depth 8 +dither -remap 1paintapic_palette.png 1cropped_im_remap_test2b.gif
convert 1cropped_im_remap_test2b.gif -format "%k" info:
19

Image

convert 1cropped_im_remap_test2b.gif -format "%c" histogram:info: | sort -r -k 1
60449: ( 82, 45, 36) #522D24 rgb(82,45,36)
52538: (173,165,157) #ADA59D rgb(173,165,157)
45662: ( 0, 0, 0) #000000 black
43666: (156, 48, 36) #9C3024 rgb(156,48,36)
34498: (230,224,232) #E6E0E8 rgb(230,224,232)
29293: (150,103, 73) #966749 rgb(150,103,73)
24955: (156,116,100) #9C7464 rgb(156,116,100)
15078: (101, 83, 59) #65533B rgb(101,83,59)
15062: (205,215,210) #CDD7D2 rgb(205,215,210)
14318: (186,186,186) #BABABA grey73
12939: (203,193,193) #CBC1C1 rgb(203,193,193)
11378: (175,138,123) #AF8A7B rgb(175,138,123)
9823: ( 41, 42, 39) #292A27 rgb(41,42,39)
9660: (151,152,154) #97989A rgb(151,152,154)
7939: (193,151,121) #C19779 rgb(193,151,121)
6321: (109, 98, 94) #6D625E rgb(109,98,94)
6135: (147, 80, 58) #93503A rgb(147,80,58)
3586: (121, 91,167) #795BA7 rgb(121,91,167)
2972: ( 80, 64,107) #50406B rgb(80,64,107)




With my script:
infile="1cropped.jpeg"
mapfile="1paintapic_palette.png"

Output:
Image

convert 1cropped_remap4.gif -format "%k" info:
19

So the same number of colors, but the mapping is different!

Here is the list of colors that are remapped (from:to) and the minimum color distance found

dist=sqrt( ( (r1-r2)*(r1-r2)+(g1-g2)*(g1-g2)+(b1-b2)*(b1-b2) )/3 )

index=0; rgb(8,10,9):rgb(0,0,0); 9.03696
index=19; rgb(46,25,24):rgb(41,42,39); 13.404
index=26; rgb(69,58,87):rgb(80,64,107); 13.626
index=28; rgb(88,30,28):rgb(82,45,36); 10.4083
index=28; rgb(112,16,17):rgb(82,45,36); 26.4701
index=41; rgb(112,88,87):rgb(109,98,94); 7.25718
index=38; rgb(117,70,57):rgb(101,83,59); 11.9583
index=47; rgb(119,119,161):rgb(121,91,167); 16.5731
index=55; rgb(135,74,62):rgb(147,80,58); 8.0829
index=61; rgb(142,18,21):rgb(156,48,36); 20.9841
index=54; rgb(142,84,73):rgb(142,86,59); 8.16497
index=62; rgb(162,111,99):rgb(156,116,100); 4.54606
index=57; rgb(162,155,165):rgb(151,152,154); 9.14695
index=73; rgb(162,175,211):rgb(186,186,186); 20.9921
index=61; rgb(164,23,28):rgb(156,48,36); 15.843
index=70; rgb(177,135,120):rgb(175,138,123); 2.70801
index=70; rgb(180,148,141):rgb(175,138,123); 12.2338
index=79; rgb(183,203,228):rgb(205,215,210); 17.8139
index=75; rgb(197,139,121):rgb(193,151,121); 7.30297
index=75; rgb(198,150,138):rgb(193,151,121); 10.247
index=69; rgb(198,165,161):rgb(173,165,157); 14.6173
index=77; rgb(200,188,198):rgb(203,193,193); 4.43471
index=87; rgb(204,215,239):rgb(230,224,232); 16.3911
index=87; rgb(211,216,230):rgb(230,224,232); 11.9583



convert 1cropped_remap4.gif -format "%c" histogram:info: | sort -r -k 1

60449: ( 82, 45, 36) #522D24 rgb(82,45,36)
45662: ( 0, 0, 0) #000000 black
43666: (156, 48, 36) #9C3024 rgb(156,48,36)
42585: (175,138,123) #AF8A7B rgb(175,138,123)
34498: (230,224,232) #E6E0E8 rgb(230,224,232)
29293: (142, 86, 59) #8E563B rgb(142,86,59)
24955: (156,116,100) #9C7464 rgb(156,116,100)
21978: (193,151,121) #C19779 rgb(193,151,121)
15078: (101, 83, 59) #65533B rgb(101,83,59)
15062: (205,215,210) #CDD7D2 rgb(205,215,210)
14318: (186,186,186) #BABABA grey73
12939: (203,193,193) #CBC1C1 rgb(203,193,193)
9823: ( 41, 42, 39) #292A27 rgb(41,42,39)
9660: (151,152,154) #97989A rgb(151,152,154)
7292: (173,165,157) #ADA59D rgb(173,165,157)
6321: (109, 98, 94) #6D625E rgb(109,98,94)
6135: (147, 80, 58) #93503A rgb(147,80,58)
3586: (121, 91,167) #795BA7 rgb(121,91,167)
2972: ( 80, 64,107) #50406B rgb(80,64,107)

User avatar
anthony
Posts: 8874
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: possible bug -remap IM 6.7.3.1 Q16

Post by anthony » 2011-10-18T18:34:47-07:00

Color substitution (-opaque -transparent) works by doing 3d color vector distance (-fuzz). color remap and reduction (dither) does not!

I know for certain that -remap, and -colors (EG: color replacement from color reduction) is NOT selecting the closest color! This has been reported a number of times, and is caused by the use of a quad tree palette storage used for color reduction.


Essentually IM does not do an exhaustive search for the nearest color in the tree, but only a quick 'neighbourhood' search.
This is often good enough for most purposes, but it is a pain when you are wanting exact close color searches.

It also causes some colors that was found using color quantization, or remap image palette never to be found! Sometimes I see up to 30% of the colors to fail to match and get added to images.

It is a bug I would like to see fixed, but a fix using the current data store is expensive in time. :(

The current solution is to expand the search for nearest colors in the palette, using -treedepth 8.
good luck, and let me know if this helps
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
http://www.imagemagick.org/Usage/

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-18T18:42:14-07:00

The current solution is to expand the search for nearest colors in the palette, using -treedepth 8.
good luck, and let me know if this helps
I tried that and it never finished after several minutes, so I gave up. It takes much too long, even at -treedepth 7. At -treedepth 6 it finished in a reasonable amount of time, but then it has not made a good match.

I have written a script to do accurate/proper 3D distance color remapping. I will notify everyone when I have it finished.

User avatar
anthony
Posts: 8874
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: possible bug -remap IM 6.7.3.1 Q16

Post by anthony » 2011-10-18T18:58:58-07:00

See also
Joel Yliluoma's arbitrary-palette positional dithering algorithm
http://bisqwit.iki.fi/story/howto/dither/jy/

This goes into color selection (nearest color) very early on.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
http://www.imagemagick.org/Usage/

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-18T20:10:04-07:00

anthony wrote:See also
Joel Yliluoma's arbitrary-palette positional dithering algorithm
http://bisqwit.iki.fi/story/howto/dither/jy/

This goes into color selection (nearest color) very early on.

Thanks. I will take a look, but I am not interested in dithering. But the luminance weighted distance measure looks interesting. I had thought of experimenting with different color spaces. But it seems to me that the colorspaces need to have orthogonal channels and only RGB and OHTA are as far as I know. But I have not looked into the more exotic spaces, yet.

User avatar
fmw42
Posts: 22234
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: possible bug -remap IM 6.7.3.1 Q16

Post by fmw42 » 2011-10-21T14:19:00-07:00

I have uploaded a new script, remap, to my web site at the link below. It uses a proper 3D RGB color distance measure with the mapfile to remap the colors in the image. Note, it currently only works with opaque images and mapfiles.

Post Reply