6 ms·

Animated GIFs the Hard Way

190 points by jskinner 14y ago

nicam 14y ago
cool idea
hungrymedia 14y ago
Clever stuff.
kicweed 14y ago
This idea (weaving bits of multiple frames in a single image and using JS to decode it) sounds remarkably similar to what Apple did for the iPhone 5 page: https://docs.google.com/document/pub?id=1GWTMLjqQsQS45FWwqNG9ztQTdGF48hQYpjQHR_d1WsI https://docs.google.com/document/pub?id=1GWTMLjqQsQS45FWwqNG... I'm only saying this because it's interesting that the same problem has been solved by very similar methods at almost the same time (SublimeText HQ being the first by a couple of months).
jskinner 14y ago
I got inspired to finally write this up after seeing the discussion today about Apple's use of a similar technique. Code is available at https://github.com/sublimehq/anim_encoder https://github.com/sublimehq/anim_encoder, although you'll undoubtedly need to do some wrangling to use it for your own projects.
- ZeroGravitas 14y ago
  Did you do any size comparison with an x264 or vp8 encoded version?
  - jskinner 14y ago
    I didn't, no. I'd be interested in seeing the result, given that video codecs aren't optimised for lossless encoding. In truth, I didn't want to get into the quagmire of real video formats, and producing something that works everywhere.
    - ZeroGravitas 14y ago
      They're not really optimised for lossless, but I think they both do pretty well on stuff that doesn't change from frame to frame, effectively using the same technique you've used to encode only the diffs. It would be interesting to compare.
__alexs 14y ago
Doesn't GIF already have a differential animation mode since you can set unchanged pixels in each frame to transparent? e.g. http://www.imagemagick.org/Usage/anim_opt/#opt_trans http://www.imagemagick.org/Usage/anim_opt/#opt_trans With PNG24 you'd at least get better colour depth. In which case why not use the same Dispose None technique in APNG (https://wiki.mozilla.org/APNG_Specification#.60fcTL.60:_The_Frame_Control_Chunk https://wiki.mozilla.org/APNG_Specification#.60fcTL.60:_The_...) and a polyfill (https://github.com/davidmz/apng-canvas https://github.com/davidmz/apng-canvas) to provide cross-browser support? Actually it might be preferable to always use the polyfill if you want to do something like the Apple thing where you can scrub around the video. Still doesn't have I-Frames to do frame-skip during fast movements though.
- vlasta2 14y ago
  Indeed, it is very strange that an animated GIF would be so ineffective in this case. The image does not seem to have too many colors and the animated changes are minimal. Have you tried an encoder that attempts to use at least the basic GIF optimization techniques?
- jskinner 14y ago
  Based on my hazy understanding of the animated GIF file format, I believe that what I ended up with is very similar to animated GIFs, from a high level at least (i.e., a collection of frames, each of which containing multiple rectangles where the frame differs from the previous one). I have no idea why the animated gif encoders I tried did such a poor job size wise, it looked as if none of them even tried to find the minimal set of changes from one frame to another. I didn't spend too long looking, as 8-bit color was always going to be a show stopper.
  - __alexs 14y ago
    Your example image (http://www.sublimetext.com/anim/rename2_packed.png http://www.sublimetext.com/anim/rename2_packed.png) is in 8-bit colour. Perhaps you just only tried the awful GIF encoders that couldn't even do the dithering well :)
tim_hutton 14y ago
But... 71KB for the whole animation as a GIF: https://picasaweb.google.com/lh/photo/k-JwpH7ZluIb2Mn0rna1PNMTjNZETYmyPJy0liipFm0?feat=directlink https://picasaweb.google.com/lh/photo/k-JwpH7ZluIb2Mn0rna1PN... Gimp, Filters > Animation > Optimize (for GIF)
- sirn 14y ago
  But it looks horrible, there's a lot of dithering.
  - tim_hutton 14y ago
    It looks perfect in Firefox and Chrome and IE and locally, for me. The slightest of banding on the tab, now I come to look for it. I guess you're using a browser that doesn't render animated GIFs very well.
    - sirn 14y ago
      I tested on Chrome 23, Firefox 15 and Safari 6 on Mac OS X. All the same result. Edit: looks the same in Photoshop too: http://i.imgur.com/nu90E.png http://i.imgur.com/nu90E.png
      - tim_hutton 14y ago
        That's really interesting. I'm on Windows 7. Just tested in Debian Linux and it's fine there too. Must be a Mac issue? (Edit: I confirm that I can see faint green spots all over the background in your Photoshop screenshot.)
        sirn 14y ago
        Likely. I remembered OSX used to have few issues with GIF rendering in Core Graphics, but I'm sure Chrome and Firefox aren't using Core Graphics for GIF rendering. Strange.
        ZoFreX 14y ago
jules 14y ago
Instead of the rectangles, you could do something far simpler. Encode the first frame as a png image as usual. For the subsequent frames, set all the pixels that are the same as in the previous frame to transparent. Now in the HTML+JS just put all the images on top of each other with all but the first frame hidden. For the animation unhide each of the following frames in sequence. The standard PNG compression will do a very good job of encoding all the transparent pixels. As long as you're not moving the viewport, this method probably works very well. You also get progressive loading for free.
- jskinner 14y ago
  I initially tried something along these lines. However even with small animations, you end up with files that while small on disk, consume a large amount of memory after they've been decompressed, resulting in browsers refusing to load them.
treelovinhippie 14y ago
Is the traffic even really there "from IE6 to iPad" to justify the extra effort?
vog 14y ago
Interesting hack, but there's one thing that looks unnecessary complicated to me: Why do you need metadata to describe where the "patches" are located? Why not simply putting all frames one below another, where all unchanged areas are transparent? In case missing transparency support in old browsers is an issue, just use a special unused color instead. Since PNG does a very good job in compressing away those empty areas, the resulting image won't become noticeably bigger. Is there any reason for which you excluded this option?
- jskinner 14y ago
  I touched on this in another reply: http://news.ycombinator.com/item?id=4532495 http://news.ycombinator.com/item?id=4532495, with the short answer being unusably high memory usage. From memory PNG doesn't compress as well as you may intuitively think in this scenario, with the resulting files being around 3X the size.
im3w1l 14y ago
I have a small algorithm to make the comparisons more efficient, assuming you just bruteforce right now. I don't know the name of it. Preparation, this code sets hash[y][x] to the sum (overflow is ok) of all pixel values in the region to the top left of the pixel at x,y. This should done for both the image and the thing we want to find in it. hash[0][0] = pixel[0][0]; for (x=1; x < width; ++x) { hash[0][x] = hash[0][x-1] + pixel[0][x]; } for (y = 1; y < height; ++y) { hash[y][0] = hash[y-1][0] + pixel[y][0]; for (x = 1; x < width; ++x) { hash[y][x] = hash[y][x-1] + hash[y-1][x] - hash[y-1][x-1] + pixel[y][x]; } } Now, when we look for a match for a small image , we could check if the sum of the pixels match by doing following comparison hashSmallImg[smallheight-1][smallwidth-1] == hash[offsetY+smallheight-1][offsetX+smallwidth-1] - hash[offsetY][offsetX+smallwidth-1] - hash[offsetY+smallheight-1][offsetX] + hash[offsetY][offsetX] If this fails we know for sure the pixels wont match. Illustrated: http://i.imgur.com/dHMKj.png http://i.imgur.com/dHMKj.png A 2-dimensional state machine might be possible, but I don't know how.
bajsejohannes 14y ago
Unfortunately, it won't look great on a lot of displays since it's using subpixel anti-aliasing for fonts. Examples being retina displays doubling the size of the pixels or a tablet turned on the side.
- thatjoshguy 14y ago
  Shouldn't tablets be avoiding subpixel anti-aliasing if they can be turned on the side? Doesn't it just _not work_?
  - bajsejohannes 14y ago
    That's a good question, and I'd be interested to know how this is generally solved (it seems the ipad just doesn't du subpixel AA). I don't see a problem with subpixel anti-aliasing if it's with rotation in mind, i.e. different rendering depending on orientation. In context of the original post, of course, there's not much the ipad can do since the subpixel AA is already encoded in the image.
  - smiddereens 14y ago
    Orientation sensors allow the operating system to know how the subpixels are currently oriented and adjust the text rendering accordingly.
timb 14y ago
Echoing what dflock said in the Apple thread, it would be great if webkit (and IE) added animated PNG support: http://caniuse.com/apng http://caniuse.com/apng Also, it's interesting to note that out of 31,000 open issues on the chromium site, APNG support is at #9 counting by user votes. http://code.google.com/p/chromium/issues/list?sort=-stars&colspec=ID%20Stars%20Pri%20Area%20Status%20Owner%20Summary http://code.google.com/p/chromium/issues/list?sort=-stars&#3...
- deleted 14y ago
  [deleted]
ComputerGuru 14y ago
From my experience with GIF back in the day (with the file type, not the protocol, I did not do any GIF-related development), the problem is not with the specification. The problem is with shitty encoders and shitty software that was all written during the late 80s and early 90s then never touched and improved since. It seems all the GIF encoders out there just take the easiest way out. GIF itself (from what little studying I've done of the spec) isn't such a terrible "codec" to work with, and it has features comparable to basic, decent video codecs. It has the potential to be decent (color space issues aside). The problem is with the crappy-ass encoders that take the laziest approach possible, rendering each frame separately, literally not cross-optimizing anything, applying random dithering in hopes it'll look OK on the pathetic monitors that were the best the 80s had to offer, and trying to do it all with as little RAM and CPU time as possible with no regard for searching for similarities across frames and finding ways to optimize the results appropriately. There's no reason a good GIF encoder couldn't do what you did in your post. I don't know if one actually exists - I gave up on GIF long ago, after a string of horrendous failures similar to yours, where even the simplest animations would result in 1 MiB outputs and have horrible dithering banding throughout. Add to that the similar disregard in decoding in browsers - where a 256 KiB GIF takes a full 45 seconds to load (stuttering and freezing for 20 seconds at a time) on a 50mpbs connection running on an i7 CPU as a result of the combined failure of encoders and decoders alike. It's pathetic. APNG is at least a chance to wipe the slate clean. Anyway, nifty animator there. Thanks for sharing, it'll really come in handy for screencast demos.
- __alexs 14y ago
  > There's no reason a good GIF encoder couldn't do what you did in your post. I don't know if one actually exists Graphics(/Image)Magick http://www.imagemagick.org/Usage/anim_opt/ http://www.imagemagick.org/Usage/anim_opt/
edddy 14y ago
How did you take the original PNGs and saved with the timestamp in the names?
maxst 14y ago
What if you simply create APNG using this: http://sourceforge.net/projects/apngasm/ http://sourceforge.net/projects/apngasm/ And then convert APNG to GIF using this: http://sourceforge.net/projects/apng2gif/ http://sourceforge.net/projects/apng2gif/ It would be interesting to compare the results...
rustyburt 14y ago
Couldn't get your code working. I get the following error: Traceback (most recent call last): File "./anim_encoder.py", line 230, in <module> generate_animation(sys.argv[1]) File "./anim_encoder.py", line 139, in generate_animation images = [misc.imread(f) for t, f in frames] File "/usr/lib/python2.6/dist-packages/scipy/misc/pilutil.py", line 37, in imread im = Image.open(name) File "/usr/lib/python2.6/dist-packages/PIL/Image.py", line 1980, in open raise IOError("cannot identify image file") IOError: cannot identify image file I have python-scipy, python-numpy and opencv installed.

190 points by jskinner 14y ago

nicam 14y ago

cool idea

hungrymedia 14y ago

Clever stuff.

kicweed 14y ago

This idea (weaving bits of multiple frames in a single image and using JS to decode it) sounds remarkably similar to what Apple did for the iPhone 5 page: https://docs.google.com/document/pub?id=1GWTMLjqQsQS45FWwqNG9ztQTdGF48hQYpjQHR_d1WsI https://docs.google.com/document/pub?id=1GWTMLjqQsQS45FWwqNG... I'm only saying this because it's interesting that the same problem has been solved by very similar methods at almost the same time (SublimeText HQ being the first by a couple of months).

jskinner 14y ago

I got inspired to finally write this up after seeing the discussion today about Apple's use of a similar technique. Code is available at https://github.com/sublimehq/anim_encoder https://github.com/sublimehq/anim_encoder, although you'll undoubtedly need to do some wrangling to use it for your own projects.

ZeroGravitas 14y ago
Did you do any size comparison with an x264 or vp8 encoded version?
- jskinner 14y ago
  I didn't, no. I'd be interested in seeing the result, given that video codecs aren't optimised for lossless encoding. In truth, I didn't want to get into the quagmire of real video formats, and producing something that works everywhere.
  - ZeroGravitas 14y ago
    They're not really optimised for lossless, but I think they both do pretty well on stuff that doesn't change from frame to frame, effectively using the same technique you've used to encode only the diffs. It would be interesting to compare.

__alexs 14y ago

Doesn't GIF already have a differential animation mode since you can set unchanged pixels in each frame to transparent? e.g. http://www.imagemagick.org/Usage/anim_opt/#opt_trans http://www.imagemagick.org/Usage/anim_opt/#opt_trans With PNG24 you'd at least get better colour depth. In which case why not use the same Dispose None technique in APNG (https://wiki.mozilla.org/APNG_Specification#.60fcTL.60:_The_Frame_Control_Chunk https://wiki.mozilla.org/APNG_Specification#.60fcTL.60:_The_...) and a polyfill (https://github.com/davidmz/apng-canvas https://github.com/davidmz/apng-canvas) to provide cross-browser support? Actually it might be preferable to always use the polyfill if you want to do something like the Apple thing where you can scrub around the video. Still doesn't have I-Frames to do frame-skip during fast movements though.

vlasta2 14y ago
Indeed, it is very strange that an animated GIF would be so ineffective in this case. The image does not seem to have too many colors and the animated changes are minimal. Have you tried an encoder that attempts to use at least the basic GIF optimization techniques?
jskinner 14y ago
Based on my hazy understanding of the animated GIF file format, I believe that what I ended up with is very similar to animated GIFs, from a high level at least (i.e., a collection of frames, each of which containing multiple rectangles where the frame differs from the previous one). I have no idea why the animated gif encoders I tried did such a poor job size wise, it looked as if none of them even tried to find the minimal set of changes from one frame to another. I didn't spend too long looking, as 8-bit color was always going to be a show stopper.
- __alexs 14y ago
  Your example image (http://www.sublimetext.com/anim/rename2_packed.png http://www.sublimetext.com/anim/rename2_packed.png) is in 8-bit colour. Perhaps you just only tried the awful GIF encoders that couldn't even do the dithering well :)

tim_hutton 14y ago

But... 71KB for the whole animation as a GIF: https://picasaweb.google.com/lh/photo/k-JwpH7ZluIb2Mn0rna1PNMTjNZETYmyPJy0liipFm0?feat=directlink https://picasaweb.google.com/lh/photo/k-JwpH7ZluIb2Mn0rna1PN... Gimp, Filters > Animation > Optimize (for GIF)

sirn 14y ago
But it looks horrible, there's a lot of dithering.
- tim_hutton 14y ago
  It looks perfect in Firefox and Chrome and IE and locally, for me. The slightest of banding on the tab, now I come to look for it. I guess you're using a browser that doesn't render animated GIFs very well.
  - sirn 14y ago
    I tested on Chrome 23, Firefox 15 and Safari 6 on Mac OS X. All the same result. Edit: looks the same in Photoshop too: http://i.imgur.com/nu90E.png http://i.imgur.com/nu90E.png
    - tim_hutton 14y ago
      That's really interesting. I'm on Windows 7. Just tested in Debian Linux and it's fine there too. Must be a Mac issue? (Edit: I confirm that I can see faint green spots all over the background in your Photoshop screenshot.)
      - sirn 14y ago
        Likely. I remembered OSX used to have few issues with GIF rendering in Core Graphics, but I'm sure Chrome and Firefox aren't using Core Graphics for GIF rendering. Strange.
      - ZoFreX 14y ago

jules 14y ago

Instead of the rectangles, you could do something far simpler. Encode the first frame as a png image as usual. For the subsequent frames, set all the pixels that are the same as in the previous frame to transparent. Now in the HTML+JS just put all the images on top of each other with all but the first frame hidden. For the animation unhide each of the following frames in sequence. The standard PNG compression will do a very good job of encoding all the transparent pixels. As long as you're not moving the viewport, this method probably works very well. You also get progressive loading for free.

jskinner 14y ago
I initially tried something along these lines. However even with small animations, you end up with files that while small on disk, consume a large amount of memory after they've been decompressed, resulting in browsers refusing to load them.

treelovinhippie 14y ago

Is the traffic even really there "from IE6 to iPad" to justify the extra effort?

vog 14y ago

Interesting hack, but there's one thing that looks unnecessary complicated to me: Why do you need metadata to describe where the "patches" are located? Why not simply putting all frames one below another, where all unchanged areas are transparent? In case missing transparency support in old browsers is an issue, just use a special unused color instead. Since PNG does a very good job in compressing away those empty areas, the resulting image won't become noticeably bigger. Is there any reason for which you excluded this option?

jskinner 14y ago
I touched on this in another reply: http://news.ycombinator.com/item?id=4532495 http://news.ycombinator.com/item?id=4532495, with the short answer being unusably high memory usage. From memory PNG doesn't compress as well as you may intuitively think in this scenario, with the resulting files being around 3X the size.

im3w1l 14y ago

I have a small algorithm to make the comparisons more efficient, assuming you just bruteforce right now. I don't know the name of it. Preparation, this code sets hash[y][x] to the sum (overflow is ok) of all pixel values in the region to the top left of the pixel at x,y. This should done for both the image and the thing we want to find in it. hash[0][0] = pixel[0][0]; for (x=1; x < width; ++x) { hash[0][x] = hash[0][x-1] + pixel[0][x]; } for (y = 1; y < height; ++y) { hash[y][0] = hash[y-1][0] + pixel[y][0]; for (x = 1; x < width; ++x) { hash[y][x] = hash[y][x-1] + hash[y-1][x] - hash[y-1][x-1] + pixel[y][x]; } } Now, when we look for a match for a small image , we could check if the sum of the pixels match by doing following comparison hashSmallImg[smallheight-1][smallwidth-1] == hash[offsetY+smallheight-1][offsetX+smallwidth-1] - hash[offsetY][offsetX+smallwidth-1] - hash[offsetY+smallheight-1][offsetX] + hash[offsetY][offsetX] If this fails we know for sure the pixels wont match. Illustrated: http://i.imgur.com/dHMKj.png http://i.imgur.com/dHMKj.png A 2-dimensional state machine might be possible, but I don't know how.

bajsejohannes 14y ago

Unfortunately, it won't look great on a lot of displays since it's using subpixel anti-aliasing for fonts. Examples being retina displays doubling the size of the pixels or a tablet turned on the side.

thatjoshguy 14y ago
Shouldn't tablets be avoiding subpixel anti-aliasing if they can be turned on the side? Doesn't it just _not work_?
- bajsejohannes 14y ago
  That's a good question, and I'd be interested to know how this is generally solved (it seems the ipad just doesn't du subpixel AA). I don't see a problem with subpixel anti-aliasing if it's with rotation in mind, i.e. different rendering depending on orientation. In context of the original post, of course, there's not much the ipad can do since the subpixel AA is already encoded in the image.
- smiddereens 14y ago
  Orientation sensors allow the operating system to know how the subpixels are currently oriented and adjust the text rendering accordingly.

timb 14y ago

Echoing what dflock said in the Apple thread, it would be great if webkit (and IE) added animated PNG support: http://caniuse.com/apng http://caniuse.com/apng Also, it's interesting to note that out of 31,000 open issues on the chromium site, APNG support is at #9 counting by user votes. http://code.google.com/p/chromium/issues/list?sort=-stars&colspec=ID%20Stars%20Pri%20Area%20Status%20Owner%20Summary http://code.google.com/p/chromium/issues/list?sort=-stars&#3...

deleted 14y ago
[deleted]

ComputerGuru 14y ago

From my experience with GIF back in the day (with the file type, not the protocol, I did not do any GIF-related development), the problem is not with the specification. The problem is with shitty encoders and shitty software that was all written during the late 80s and early 90s then never touched and improved since. It seems all the GIF encoders out there just take the easiest way out. GIF itself (from what little studying I've done of the spec) isn't such a terrible "codec" to work with, and it has features comparable to basic, decent video codecs. It has the potential to be decent (color space issues aside). The problem is with the crappy-ass encoders that take the laziest approach possible, rendering each frame separately, literally not cross-optimizing anything, applying random dithering in hopes it'll look OK on the pathetic monitors that were the best the 80s had to offer, and trying to do it all with as little RAM and CPU time as possible with no regard for searching for similarities across frames and finding ways to optimize the results appropriately. There's no reason a good GIF encoder couldn't do what you did in your post. I don't know if one actually exists - I gave up on GIF long ago, after a string of horrendous failures similar to yours, where even the simplest animations would result in 1 MiB outputs and have horrible dithering banding throughout. Add to that the similar disregard in decoding in browsers - where a 256 KiB GIF takes a full 45 seconds to load (stuttering and freezing for 20 seconds at a time) on a 50mpbs connection running on an i7 CPU as a result of the combined failure of encoders and decoders alike. It's pathetic. APNG is at least a chance to wipe the slate clean. Anyway, nifty animator there. Thanks for sharing, it'll really come in handy for screencast demos.

__alexs 14y ago
> There's no reason a good GIF encoder couldn't do what you did in your post. I don't know if one actually exists Graphics(/Image)Magick http://www.imagemagick.org/Usage/anim_opt/ http://www.imagemagick.org/Usage/anim_opt/

edddy 14y ago

How did you take the original PNGs and saved with the timestamp in the names?

maxst 14y ago

What if you simply create APNG using this: http://sourceforge.net/projects/apngasm/ http://sourceforge.net/projects/apngasm/ And then convert APNG to GIF using this: http://sourceforge.net/projects/apng2gif/ http://sourceforge.net/projects/apng2gif/ It would be interesting to compare the results...

rustyburt 14y ago

Couldn't get your code working. I get the following error: Traceback (most recent call last): File "./anim_encoder.py", line 230, in <module> generate_animation(sys.argv[1]) File "./anim_encoder.py", line 139, in generate_animation images = [misc.imread(f) for t, f in frames] File "/usr/lib/python2.6/dist-packages/scipy/misc/pilutil.py", line 37, in imread im = Image.open(name) File "/usr/lib/python2.6/dist-packages/PIL/Image.py", line 1980, in open raise IOError("cannot identify image file") IOError: cannot identify image file I have python-scipy, python-numpy and opencv installed.