Open farindk opened 1 month ago
This seems like a reasonable thing to add.
It kind of relates to the exploration on compressed meta
boxes that was discussed at the last meeting. That proposal was dropped in favor of the current dedicated low-overhead approach since that gives better results for simple files, but the conclusion of the discussion was that it would help a lot with large and complicated files.
Running deflate
on the meta
box would give you even better compression than the syntax above, but you would still have to parse all of the entries. So maybe we the best approach is to have both.
For 256x256 tiles, this sums to at least 2 MB of unnecessary overhead.
Could you share a range of the expected file size of a file representative of the use case you mentioned?
HEIF images that consist of many tiles
Is this use case sharing other complex ISOBMFF/HEIF features?
meta
components.Running
deflate
on themeta
box would give you even better compression than the syntax above, but you would still have to parse all of the entries. So maybe we the best approach is to have both.
A simple encoding that matches the typical data is usually better than deflate
:
I tried to compress the byte sequence consisting of 0x00
to 0xff
(0 1 2 3 4 ... 255).
With deflate
, those 256 bytes "compressed" to 261 bytes.
The 512 bytes sequence 0x0000
to 0x00ff
(as they appear in the iref
) only compressed to 347 bytes.
The simple scheme like proposed above would only use 4 bytes for the same.
For the extreme case of 256x256 tiles, we have the iref
sequence 0x0000
to 0xffff
. These are 2*65536=131072 bytes (ignoring the fact that the grid image itself will need another ID, so that we would have to switch to 4 bytes, doubling the memory size). With deflate
, this compresses to 118960 bytes, which is only 10% smaller. With the simple scheme above, still only 4 bytes.
Running
deflate
on themeta
box would give you even better compression than the syntax above, but you would still have to parse all of the entries. So maybe we the best approach is to have both.A simple encoding that matches the typical data is usually better than
deflate
:I tried to compress the byte sequence consisting of
0x00
to0xff
(0 1 2 3 4 ... 255). Withdeflate
, those 256 bytes "compressed" to 261 bytes.The 512 bytes sequence
0x0000
to0x00ff
(as they appear in theiref
) only compressed to 347 bytes. The simple scheme like proposed above would only use 4 bytes for the same.For the extreme case of 256x256 tiles, we have the
iref
sequence0x0000
to0xffff
. These are 2*65536=131072 bytes (ignoring the fact that the grid image itself will need another ID, so that we would have to switch to 4 bytes, doubling the memory size). Withdeflate
, this compresses to 118960 bytes, which is only 10% smaller. With the simple scheme above, still only 4 bytes.
Fair point. I would have expected deflate to be able to do better here, but it's been a long time since I looked into exactly how it codes stuff. I thought it could handle incrementing sequences, but I must have misremembered.
For 256x256 tiles, this sums to at least 2 MB of unnecessary overhead.
Could you share a range of the expected file size of a file representative of the use case you mentioned?
There are a couple of different aspects to this - "storage size on disk" and "actually transferred bytes" might be ways to describe it.
Reducing the meta
size on a small image makes a proportionally larger difference to storage size for object storage, but may not make any difference for block storage (because its 4K blocks, typically).
On a huge image, reducing the meta
size makes almost no difference proportionally to the overall file size. However if that is on an object store (like S3 bucket or other cloud equivalent), there is a lot to be gained by making the meta
smaller. Consider that the user may not be viewing the whole image at full resolution. Instead, they are probably interested in a smaller region of interest. This is one of the cases for Cloud Optimised GeoTIFF (aka COG).
If the meta
was smaller such that the initial HTTP GET operation (maybe for a byte range of the first 128K, 4M or something like that) got all of the information required to determine how to decode the structure, and ideally provide an overview image (top of the pymd
), then we can provide a good user experience.
If meta
is large, such that you miss part of it in the first GET, you have another round trip before you can do anything.
As the user zooms in, we can select which parts of the image we want using Range header byte ranges to only download the parts of the file we will show to the user. Actual transferred bytes could be (and often will be, in this use case) much less than the total size.
So while the total image size is still important, it may not be that useful a metric here.
Got it, thank you for the detailed explanation.
What would be the reduced meta
size with this proposal, when applied to the 2MB example above?
I would imagine boxes such as iloc
cannot be modified in the same run-length fashion as iref
and others.
So maybe the whole meta
size will remain in the same magnitude range; and deflate-like schemes could result in smaller files when applied to the whole meta
box instead of applied to specific sequences as tested in https://github.com/MPEGGroup/FileFormat/issues/106#issuecomment-2228211076.
In order to put some numbers on @y-guyon comment above, I decided to take a look at the largest HEIF file I have created. It's a 93356x32872 HEIF file using 10974 512x512 tiles, with each tile having ispe
and hvcC
. So not close to the limit of 64k tiles, but much larger than normal use-cases.
('meta' "Meta Box", size = 483819)
('iinf' "Item Information Box", size = 230552)
('iref' "Item Reference Box", size = 22014)
('iprp' "Item Properties Box", size = 55473)
('ipco' "Item Property Container Box", size = 560)
('ipma' "Item Property Association", size = 54905)
('iloc' "Item Location Box", size = 175664)
Size-wise, the iinf
and iloc
are the boxes to care mostly about, followed by ipma
and iref
.
Assuming 4 byte item IDs.
For iloc
, assuming no base offset and offset and length sizes of 4.
iinf
: 8 + 4 + 4 + 2 + 4 + 1 = 23 * numTilesiref
: 4 + 4 + 2 + numTiles 4 = 10 + numTiles 4ipma
: ((4 + 1) + 1 numProperties) numTilesiloc
: (4 + 2 + 2 + 2 + 4 + 4) numTiles = 18 numTilesiinf
, iref
and ipma
could all get dedicated run-length coding as proposed above, but that leaves us with iloc
.
Taking the meta
box from the file above, dumping it and running tar
with various algorithms on it gives us the following sizes as reference:
Taking the iloc
box from the file above and doing the same exercise gives us:
So deflate definitely helps. If used on the full meta
box it gives us roughly the same size as you would get by implementing the dedicated run-length encoding schemes on iinf
, iref
and ipma
. But the optimal approach would be to do all of the dedicated schemes and use something like lzma.
For the iloc entries in that specific, is it all single extent per item and all in mdat
?
Of those extents, how many follow-on such that the first byte of item n is immediately after the last byte of item n-1?
My interest is in whether offset + extent for the previous item can determine the offset of this item.
So you could get an effect of "items 1 to 10974 have extents [ ], first item at (base) offset x".
For the iloc entries in that specific, is it all single extent per item and all in
mdat
?
Yes
Of those extents, how many follow-on such that the first byte of item n is immediately after the last byte of item n-1?
All of them
My interest is in whether offset + extent for the previous item can determine the offset of this item.
So you could get an effect of "items 1 to 10974 have extents [ ], first item at (base) offset x".
Yes, that's definitely something that could be done.
The file basically has something like this:
...
Item ID: 8
Construction method: 0, Data reference index: 0
Extent 1/1: Offset 1652670, Length 3092
Item ID: 9
Construction method: 0, Data reference index: 0
Extent 1/1: Offset 1655762, Length 3118
Item ID: 10
Construction method: 0, Data reference index: 0
Extent 1/1: Offset 1658880, Length 3088
Item ID: 11
Construction method: 0, Data reference index: 0
Extent 1/1: Offset 1661968, Length 3219
Item ID: 12
Construction method: 0, Data reference index: 0
Extent 1/1: Offset 1665187, Length 3206
...
For all of these the offset is the offset+length of the previous item. So the only thing that would really be needed would be to store the starting offset, the range of item IDs and the lengths for each item. In this case we could get away with using a 2-byte length for each entry which would save a lot of space.
If you want to get fancy you could also experiment with trying to predict the length from the previous length, but that could break down fast depending on your content and won't really save you that much unless we start doing variable length integers.
Here is an example image with 256x255 tiles: large tiled images (the image file is quite large as it uses JPEG compression).
The meta
box total size is 3,329,568 bytes. This includes:
iinf
: 1,370,907 bytesipma
: 391,700 bytesiref
: 130,584 bytesiloc
: 1,436,192 bytesSo deflate definitely helps. If used on the full meta box it gives us roughly the same size as you would get by implementing the dedicated run-length encoding schemes on iinf, iref and ipma.
I have to disagree. With the syntax proposed above for iinf
, iref
, ipma
, each of them would have about the size of a single item + 4 or 8 bytes. Or, if I counted correctly:
iinf
: 38 bytes (iinf header + 1 infe entry for all tiles)ipma
: 25 bytes (ipma header + 1 item entry for all tiles)iref
: 30 bytes (iref header + 1 range for all tiles)The iloc
box could also use a much more compact syntax. The idea would be that for a range of items (all the tiles), we assume that they are stored in the mdat
one after another and then only have to provide pointers to the start of each tile. This is similar to how h265 does this in the slice_segment_header
:
h265 uses an adjustable number of bits for the size of each tile, but to simplify parsing and be in line with how other boxes work, we could use either 4 or 8 bytes for each tile.
This would reduce the size of iloc
to something like:
iloc
size: 16 + 4 256 255 = 261,136 bytes.If we would further allow tile sizes to be stored at lengths other than 4 or 8 bytes, this could be reduced even further to maybe at most half of that.
I can write a detailed proposal for an iloc
syntax if that helps.
@farindk
I have to disagree. With the syntax proposed above for iinf, iref, ipma, each of them would have about the size of a single item + 4 or 8 bytes.
You can't really disagree that it helps, I gave you actual numbers for an actual file. Just using deflate on the full meta
is equivalent with completely removing iinf
, ipma
and iref
. So deflate
~= implementing efficient schemes for iinf
, iref
and ipma
.
That doesn't mean you can't get even better results by implementing the range schemes for iinf
, iref
, ipma
and iloc
. But the most optimal solution is very likely all of those schemes plus a lossless compression algorithm.
@leo-barnes Ah, sorry, I misunderstood your experiment. I tought you were applying deflate
only on iinf
,ipma
, and iref
and comparing that to the range-based syntax.
But yes, if you also include iloc
and don't apply an improved syntax for iloc
, you will get those numbers.
HEIF images that consist of many tiles contain a lot of redundant information:
infe
item entry with usually identical content,ipma
property associations for each tile are usually referring to the same properties,iref
of typedimg
, defining the grid image tiles, usually consists of a long list of consecutive item IDs (1,2,3,4,5,6, ...).On images with many tiles (#105), this can lead to significant overhead. E.g. 21 bytes for each
infe
, 2 or 4 bytes for eachiref
reference, and usually >=6 bytes for eachipma
entry. For 256x256 tiles, this sums to at least 2 MB of unnecessary overhead.In order to reduce this amount of data, I propose the following changes:
infe
to hold not only anitem_ID
, but a range ofitem_ID
s. The content of a singleinfe
will then define all items in the given range. This could be implemented with a newinfe
box version or flag that enables storing anitem_ID_count
. The range would then be defined byitem_ID
toitem_ID + item_ID_count
.ipma
entry could store a range ofitem_ID
s instead of a singleitem_ID
to which it relates in order to eliminate the unnecessary copies.iref
could be extended with aversion=2
, operating as follows:class SingleItemTypeReferenceBoxRanges(referenceType) extends Box(referenceType) { unsigned int(32) from_item_ID; unsigned int(32) reference_count; for (j=0; j<reference_count; ) { unsigned int(32) to_item_ID; unsigned int(32) count_minus_one;
} }