I've been looking over Benjamin Schwartz's Skeleton A-mod proposal. I've been pretty busy with other projects over the past few months, so haven't had a chance to look at Ogg indexing until now... In general, I think Benjamin's ideas are sound, they're improvements, and I'm open to being convinced to take them in the next index version. We may as well get the index as right as we can first time. I like the ideas of storing the end time/max granulepos in the index packets, and of a b_max value for corruption detection. They're sensible. I will include them in the next version. We should try to avoid changing the 'fishead' packet to be incompatible with previous minor-versions. If we move the start/end time fields into the index packets, which is sensible, it would break backwards compatibility of this version with earlier versions of the same major version. Silvia et al wanted to add some new fields to the skeleton track, so maybe we should increment the version to 4.0, include those fields, and change the rest of the index format? Benjamin: have you made any index A-mod prototype encoders to get an encoded-index size comparison? I also have a few questions about your proposal...> The Golomb-Rice encoded integers are encoded by subtracting 1, > dividing by the > Golomb-Rice parameter, representing first the quotient in unary (1s), > then a 0, > and then the remainder in binary. We subtract 1 because a Golomb-Rice code > naturally represents 0, but 0 is not a valid delta between subsequent > values. > For example, consider encoding a delta of 2496 with a scaling > coefficient of 64 > and a Golomb-Rice parameter of 16. First, 2496 is divided by 64, > giving 39. We > subtract 1, then divide 38 by 16, yielding a quotient of 2 and > remainder of 6. > The quotient and remainder are coded as 110 0110. This is a prefix > code, so no additional delimeters are needed to separate values.Am I right to assume that the binary value of the remainder is encoded in a fixed width field of log2(Golomb_Rice_parameter)? e.g. log2(16)=4 bits in this example?> Note that it is not always safe to > round granpos down after division: if rounding down would cause the > granpos > to move too early, then it must be rounded up.Can you give an example of this? Is it the case when you divide the granulepos such that it moves to before the previous keypoint's granulepos?> 9. 'n' key points, each of which contain, in the following order: > - the keypoint's byte offset delta, as a shifted Golomb-Rice encoded > integer. This is the number of bytes that this keypoint is after the > preceeding keypoint's offset, or from the start of the segment > if this > is the first keypoint. The keypoint's byte offset is therefore > the sum > of the byte-offset-deltas of all the keypoints which come before it. > - the granpos delta for this keypoint as a shifted Golomb-Rice encoded > integer. This is the difference from the previous keypoint's granpos > value. The keypoint's granpos is therefore the sum of > all the granpos deltas up to and including the keypoint's.Would you expect the granulepos scaling shift to be equal to the granuleshift for theora streams, at least initially? Have you given any thought to how to determine good values for the shifts and Rice parameters? All the best, Chris P.
If it's not backwards compatible, it should definitely have a new major number. I'm happy with that and would also be keen to get the metadata fields added. Cheers, Silvia. On Fri, Apr 23, 2010 at 6:23 PM, Chris Pearce <chris at pearce.org.nz> wrote:> I've been looking over Benjamin Schwartz's Skeleton A-mod proposal. I've > been pretty busy with other projects over the past few months, so > haven't had a chance to look at Ogg indexing until now... > > In general, I think Benjamin's ideas are sound, they're improvements, > and I'm open to being convinced to take them in the next index version. > We may as well get the index as right as we can first time. > > I like the ideas of storing the end time/max granulepos in the index > packets, and of a b_max value for corruption detection. They're > sensible. I will include them in the next version. > > We should try to avoid changing the 'fishead' packet to be incompatible > with previous minor-versions. If we move the start/end time fields into > the index packets, which is sensible, it would break backwards > compatibility of this version with earlier versions of the same major > version. Silvia et al wanted to add some new fields to the skeleton > track, so maybe we should increment the version to 4.0, include those > fields, and change the rest of the index format? > > Benjamin: have you made any index A-mod prototype encoders to get an > encoded-index size comparison? I also have a few questions about your > proposal... > >> The Golomb-Rice encoded integers are encoded by subtracting 1, >> dividing by the >> Golomb-Rice parameter, representing first the quotient in unary (1s), >> then a 0, >> and then the remainder in binary. We subtract 1 because a Golomb-Rice code >> naturally represents 0, but 0 is not a valid delta between subsequent >> values. >> For example, consider encoding a delta of 2496 with a scaling >> coefficient of 64 >> and a Golomb-Rice parameter of 16. First, 2496 is divided by 64, >> giving 39. We >> subtract 1, then divide 38 by 16, yielding a quotient of 2 and >> remainder of 6. >> The quotient and remainder are coded as 110 0110. This is a prefix >> code, so no additional delimeters are needed to separate values. > > Am I right to assume that the binary value of the remainder is encoded > in a fixed width field of log2(Golomb_Rice_parameter)? e.g. log2(16)=4 > bits in this example? > > >> Note that it is not always safe to >> round granpos down after division: if rounding down would cause the >> granpos >> to move too early, then it must be rounded up. > > Can you give an example of this? Is it the case when you divide the > granulepos such that it moves to before the previous keypoint's granulepos? > > >> 9. 'n' key points, each of which contain, in the following order: >> ? ? - the keypoint's byte offset delta, as a shifted Golomb-Rice encoded >> ? ? ? integer. This is the number of bytes that this keypoint is after the >> ? ? ? preceeding keypoint's offset, or from the start of the segment >> if this >> ? ? ? is the first keypoint. The keypoint's byte offset is therefore >> the sum >> ? ? ? of the byte-offset-deltas of all the keypoints which come before it. >> ? ? - the granpos delta for this keypoint as a shifted Golomb-Rice encoded >> ? ? ? integer. This is the difference from the previous keypoint's granpos >> ? ? ? value. The keypoint's granpos is therefore the sum of >> ? ? ? all the granpos deltas up to and including the keypoint's. > > Would you expect the granulepos scaling shift to be equal to the > granuleshift for theora streams, at least initially? Have you given any > thought to how to determine good values for the shifts and Rice parameters? > > > All the best, > Chris P. > _______________________________________________ > theora mailing list > theora at xiph.org > http://lists.xiph.org/mailman/listinfo/theora >
Chris Pearce wrote:> In general, I think Benjamin's ideas are sound, they're improvements, > and I'm open to being convinced to take them in the next index version.Wow. Thank you. I have to admit that it's definitely not perfect. I still don't know quite what to do about rolling-intra and out-of-order streams (Dirac).> We should try to avoid changing the 'fishead' packet to be incompatible > with previous minor-versions.OK. I put them on the end of fishead, thinking that this would be sufficient for compatibility. If it's not sufficient, then I agree we should avoid breaking compatibility.> If we move the start/end time fields into > the index packets, which is sensible, it would break backwards > compatibility of this version with earlier versions of the same major > version. Silvia et al wanted to add some new fields to the skeleton > track, so maybe we should increment the version to 4.0, include those > fields, and change the rest of the index format?Do the new fields proposed by Silvia require a new format? I thought the point of fisbone was to be extensible. Maybe Silvia has proposed more things that I don't know about.> Benjamin: have you made any index A-mod prototype encoders to get an > encoded-index size comparison?I'm afraid not. My few statistics that suggest a typical stream might spend a total of 4 bits per keypoint.> Am I right to assume that the binary value of the remainder is encoded > in a fixed width field of log2(Golomb_Rice_parameter)? e.g. log2(16)=4 > bits in this example?Yes, the remainder is fixed-width (but not aligned).>> Note that it is not always safe to >> round granpos down after division: if rounding down would cause the >> granpos >> to move too early, then it must be rounded up. > > Can you give an example of this? Is it the case when you divide the > granulepos such that it moves to before the previous keypoint's granulepos?If you were to round down the granulepos but not the byte offset, then the granulepos might say "seek to this offset to get granulepos 4", when in fact the granulepos at that offset is 7. If you were looking for granulepos 5, you're too late in the stream. This can still happen even if both are being rounded down. The safe solution is to round the offset down and the granpos up. However, it will sometimes be valid, and slightly more efficient for seeking, to round both down.>> 9. 'n' key points, each of which contain, in the following order: >> - the keypoint's byte offset delta, as a shifted Golomb-Rice encoded >> integer. This is the number of bytes that this keypoint is after >> the >> preceeding keypoint's offset, or from the start of the segment >> if this >> is the first keypoint. The keypoint's byte offset is therefore >> the sum >> of the byte-offset-deltas of all the keypoints which come before >> it. >> - the granpos delta for this keypoint as a shifted Golomb-Rice >> encoded >> integer. This is the difference from the previous keypoint's >> granpos >> value. The keypoint's granpos is therefore the sum of >> all the granpos deltas up to and including the keypoint's. > > Would you expect the granulepos scaling shift to be equal to the > granuleshift for theora streams, at least initially? Have you given any > thought to how to determine good values for the shifts and Rice parameters?The spec suggests that for most streams a granularity of 2 seconds or 64 KB is sufficient. I think that corresponds to a granulepos scaling shift of granuleshift+log2(2 seconds / granulerate), and a byte offset scaling shift of log2(64K) = 16. That quantization may be a touch excessive; maybe 1 second and 32 KB would be sufficient. For selecting the Rice parameter, the optimum parameter is log2(mean(data)) up to rounding. --Ben -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 198 bytes Desc: OpenPGP digital signature Url : http://lists.xiph.org/pipermail/theora/attachments/20100423/62b48022/attachment.pgp