Wednesday, December 26, 2018

PNG seam carving chunks. (seMw, seMh)

As a fun quirk I recently read the PNG specifications and that's some clever stuff. It's wildly extensible even by 3rd party folks. I recall messing around with seam carving years ago, and I now realized that PNG files themselves would be a fine way to store seam carving data. seMw seMh chunks would define the seam carving width and seam carving height enumerations. The data in these blocks would contain zlib compressed data (compression identical to that of other PNG chunks) of 8/16/24/32/etc bit numbers, one number, per pixel laid out left to right, top to bottom. The required bits of the number is the ceiling function to the next full byte needed to express the maximum value to enumerate that dimension. So if your width is 255 you can make do with a 8 bit number but between 256 and 65535 you need a 16 bit number. The numbers are stored in big endian notation (like that of PNG) The blocks for seMw and SeMh are independent (as required by PNG) so if you have a 360 x 240 image it will require 2 bytes per width, and 1 byte per height.

That's it. We just provide a number for each pixel, in one or two directions.

Height carving will be done first. Because of the need for pixels from other scanlines to fill in the gaps left by the now missing pixels and then the width carving.

Height carving:
* All pixels that are above a given height threshold are declared blank
* Entirely blank columns are removed.
* All pixels are copied to the topmost available pixel and blank pixels are overwritten.
* The new height is the position of the last complete scanline.
* If some scanlines are the new height, that they are truncated.

Width carving:
* All pixels that are above a given width threshold are declared blank.
* Entirely blank scanlines are removed.
* All scanlines pixels are copied to the first available pixel and blank pixels are overwritten.
* The new width is the shortest valid scanline.
* If some scanlines are longer than new width, they are truncated.

Do note, that if a threshold value causes all values in a scanline to be blanked that scanline, during width carving, is removed. Likewise if all column pixels are blank in height carving that column is removed. This allows for thresholds within width carving that remove entire lines (so long as they are the same scanline). These removed scanlines and columns are disqualified from being the shortest valid scanline or causing no scanline to be completed.

There is no guarantee you will get a particular width or height, just that it can be reduced. If at a certain pixels have a value of 0, these cannot be removed until the value is actually 0 (unless removed by the other directional carving). If all pixels are given a minimum value of 120-width the entire image is gone below that value. If well behaved it will simply reduce gradually losing seams in a proper and effective manner, if not we behaved it could do a bunch of weird and kind of rebellious things, all of which are valid. If a block (seMh, seMw) does not exist, it's assumed that it values are all entirely 0. That is to say regardless the threshold given (above zero) it won't change, and need not be implemented.

You should not assume the values are actually seams, they simply number assigned to pixels in width and height directions. The removal algorithm remains the same.

The process is not iterative. You remove the height pixels then the width pixels. If you perform this operation again, the the correct result is if you did this from the original image.

There is no requirement that both width and height carving be implemented, you could simply implement direction (width would be the easiest there).

--- The general advantage of this scheme is that in most cases it'll just be a normal PNG and work like a graphics file except in something or other that cares about this data. And when nothing cares about that data it'll be fine and just store a normal image file anyway.

No comments: