I have been contemplating a variation on PNG.



Shape/next byte:

Shape: The current pixel is a either a rectangle, a pixel, or a jiggle

Next: The next 0-63 bits are of the same type or the next 0-127 bits are of the same type.  The latter applies in the case of pixels and the former in the case of rectangles and jiggles.



Color byte

If a pixel: This is all that is needed

If a rectangle: Need byte for width and byte for height.  If width or height is greater than 256, break it up into multiple rectangles.

If a jiggle: Each byte represents a set of 4 directions.  Color all pixels encountered when traveling around in that color.  An end byte consists of a sequence that repeats two visits (e.g. up, down, up down).  The pixel visited by "up" is considered part of the jiggle, in that example.



The groupings that had a shape bit or a jiggle bit can be compressed using Huffman.  Note, however, that removing the shapes means that this compression will be less effective.  I believe that, if one ignores the additional overhead from the Shape bits and Next bits, , the benefits of using shapes and jiggles combined with using Huffman on the sequences of colors and on the direction sequences within the jiggles will be at least as good (but possibly better) than PNG.  However, I am less confident that the benefits will be sufficiently good to justify the additional overhead.



The main purpose of this algorithm is to compress vertically adjacent pixels together.  As I understand it, PNG works on individual rows and thus will provide lower benefits.



While reading such an image is easy, producing one is more difficult.  Finding the rectangle components could be done using a scanline algorithm like http://enchantia.com/software/graphapp/doc/tech/ellipses.html .  Jiggles are groups of components that are too small or too awkward to make into rectangles.  While a jiggle sounds pretty nice (4 pixels per byte), some of the data will be wasted as the jiggle will potentially get only 2 pixels per byte in places where a the jiggle has to backtrack across individual pixels.  Generally, a jiggle would be used for shapes of size 4 or greater, but a rectangle will take precedence (but only be used for rectangles of size 9 or higher).



Practicle considerations for jiggle compression: In generall, a jiggle will only travel in 3 of the 4 directions, particularly if one deliberately generates them that way.  Thus, the 4th direction would be rare enough to make effective use of Huffman without compromising the other directions.







I think this algorithm might be serviceable for images like diagrams and other images made up predominantly of solid colors.