tag:blogger.com,1999:blog-5246987755651065286.post8108049297863408006..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 06-20-10 - Some notes on PNGcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-5246987755651065286.post-18327434632285977922010-06-25T04:01:46.792-07:002010-06-25T04:01:46.792-07:00Haar written in this way actually can be made non-...<i>Haar written in this way actually can be made non-range-expanding of course</i><br /><br />Right, that's what I meant, you just have to interpret the variables as implicitly 8-bit, sorry, I thought that was obvious.<br /><br /><i>I'm pretty sure it's the *only* simple shear (other that obvious permutations of RGB).</i><br /><br />LOCO is something like:<br /><br />out[0] = R-G<br />out[1] = G<br />out[2] = B-G<br /><br />so there's all sorts of other simple reversible shears:<br /><br />out[0] = R-(G>>1)<br />out[1] = G<br />out[2] = B-(G>>2)<br /><br />etc. etc. I have no idea if there's any point to them, though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-81852014582654326702010-06-24T14:40:58.737-07:002010-06-24T14:40:58.737-07:00I guess the crucial thing about LOCO is that the l...I guess the crucial thing about LOCO is that the lowpass part (G) is not affected by the modulo in weird ways.<br /><br />The terrible thing about Modulo-YCoCg is that it can do weird things to the lowpass part.<br /><br />(BTW Modulo-YCoCg is known as "CFH" and is discussed in the literature)cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-26200647278198305052010-06-24T09:20:37.525-07:002010-06-24T09:20:37.525-07:00Eh .. actually, this :
Co = R - B
t = B + (Co >...Eh .. actually, this :<br /><br />Co = R - B<br />t = B + (Co >> 1)<br /><br />is a Haar step in the lifting form. This is {t,Co} <- Haar(R,B)<br /><br />Haar written in this way actually can be made non-range-expanding of course, it's just <br /><br />Co = [ R - B ] mod 256<br />t = [ B + (Co >> 1) ] mod 256<br /><br />t is supposed to be the "low" part of the Haar, it should be close to (R+B)/2 , but when the modulos kick in it can wind up being completely different than that which is annoying.<br /><br />I dunno maybe this might be a win once in a while.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-76621176703003649272010-06-24T08:00:22.963-07:002010-06-24T08:00:22.963-07:00"So isn't that not-range-expanding? I gue..."So isn't that not-range-expanding? I guess it's basically four shears."<br /><br />Of course that is range expanding.<br /><br />That is a standard "lifting" way to write lossless YCoCg. Constructing a transform through lifting ensures a transform is lossless, but tells you nothing about volume expansion or range expansion.<br /><br />"To ryg's argument, I think it's that the AABB is a distraction."<br /><br />No, the AABB is exactly the right thing to look at, because that tells you the range of each coordinate needed.<br /><br />"The other question is whether LOCO is the best simple shear."<br /><br />I'm pretty sure it's the *only* simple shear (other that obvious permutations of RGB).cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-12532131053093039062010-06-24T03:04:45.853-07:002010-06-24T03:04:45.853-07:00So, actually, it looks to me like the the descript...So, actually, it looks to me like the the description for YCoCg on the multimedia.cx wiki is written as a series of reversible liftings, although maybe I'm misunderstanding something...<br /><br /><i><br />Co = R - B<br /> t = B + (Co >> 1)<br />Cg = G - t<br /> Y = t + (Cg >> 1)<br /></i><br /><br />and then<br /><br /><i><br /> t = Y - (Cg >> 1)<br /> G = Cg + t<br /> B = t - (Co >> 1)<br /> R = Co + B<br /></i><br /><br />So isn't that not-range-expanding? I guess it's basically four shears.<br /><br />Also, since you allow per-line filtering, and as you said you can do the colorspace "conversion" in the filter, then you could have multiple ones and decide them in a fine-grained way.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-50067133791092183712010-06-24T00:11:00.077-07:002010-06-24T00:11:00.077-07:00"Oh yeah, that Haar transform was the thing I..."Oh yeah, that Haar transform was the thing I was thinking of that squeezed in the same range."<br /><br />Sorry, I just realized I miswrote that, which is why it sounded dumb. That Haar transform was the thing I was thinking of that I *thought* at the time you meant squeezed them in the same range. I was assuming that the reason you were going to so much effort to recover the extra bit from (a+b)/2 instead of just storing (a+b) in the first place was because the whole thing fit in 16 bits as is, not because you were trying to keep it in 17 bits instead of 18. But if you can't actually store (a-b) mod 256, then yeah.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-81691890232252578592010-06-24T00:03:28.417-07:002010-06-24T00:03:28.417-07:00Ok, but there are rotational transformations that ...Ok, but there are rotational transformations that pack a square perfectly, although they involve an additional scale and reshuffling (normally you see this as a rotated grid mapped to a square). Since the area of the two shapes is identical by definition it's probably equivalent to scaling one axis shorter and one axis longer. So yeah, I don't see how to get from A to B.<br /><br />To ryg's argument, I think it's that the AABB is a distraction. The "height" of any given slice of the rotated solid is longer than the original square's height without even looking at the bounds. (And the bounds are where the shear looks equally bad.)<br /><br />Or to make it concretely obvious, take some coordinate axis of tre transformed data after rotation, and transform that back through the inverse rotation, so it comes out to some diagonal in the RGB cube. If the pre-transform one is long enough to cover the whole line segment through the cube, it must have been longer than a side of the cube.<br /><br />The other question is whether LOCO is the best "simple" shear. For example, you could find a shear that maps the Y to a primary axis. LOCO is mapping the grays onto the G axis--a perfect gray comes out as pure G (IIRC). So you could have the R and B computation involve a YCoCg-like shifted version of G to reduce the dominance of G's effect on R and B.<br /><br />However, since you're lossless, you don't care about perceptual effects at all, you just care about modelling the data. So the 'shades of grey is most important'/'most neutral' might well be the better model, rather than something that optimizes for colors where Co=Cg=0 .Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-68675769623309128952010-06-22T16:33:26.452-07:002010-06-22T16:33:26.452-07:00I should say a Haar is not actually a 45 degree ro...I should say a Haar is not actually a 45 degree rotation. A Hadamard is a 45 degree rotation which is volume expanding. A Haar is a Hadamard with a non-uniform scale (one axis gets /2). The Haar is not volume expanding, but is "range" expanding. Haar is the same as S Transform.<br /><br />The "PL Haar" and "Modulo transform" papers are both quite good, I encourage interested readers to follow up there.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-1625968948365554772010-06-22T16:12:38.164-07:002010-06-22T16:12:38.164-07:00" Oh yeah, that Haar transform was the thi..." Oh yeah, that Haar transform was the thing I was thinking of that squeezed in the same range."<br /><br />Well to be clear Haar does *not* make output values in the same range. There is a funny thing like Haar called PLHaar which nobody uses which does go into the same range.<br /><br />" Unless I'm misunderstanding ryg's response, I think his explanation is off the mark."<br /><br />Ryg is right he's just being not completely thorough. A Haar is a 45 degree rotation, which means the AABB gets bigger. That is true as he said. Of course you can take your funny diamond shape and pack it back into a square, but no *linear* transform will do it. In that sense if you pack it back into a square it's not really YCoCg any more.<br /><br />" Technically LOCO is also range expanding (that is, it's range expanding under his argument); "<br /><br />Yeah, I suppose so. The problem is not that YCoCg is range expanding - it's that it's range expanding and there's no simple operation to get back into a cube.<br /><br />In particular, geometrically LOCO is not a rotation, it's a shear. Imagine a square and shear up one side and shear down the other side. Obviously you can take the sheared square and cut it along a horizontal line and put the top under bottom. Now you have a square again. This is what the modulo does.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-38262224826353489332010-06-22T14:03:55.863-07:002010-06-22T14:03:55.863-07:00Oh yeah, that Haar transform was the thing I was t...Oh yeah, that Haar transform was the thing I was thinking of that squeezed in the same range.<br /><br />Unless I'm misunderstanding ryg's response, I think his explanation is off the mark. (Although I don't know what "the S transform trick" is.)<br /><br /><i>Technically</i> LOCO is also range expanding (that is, it's range expanding under his argument); obviously R-G requires 9 bits. However you can do everything mod 256 without losing data. So it requires a deeper analysis than just "a rotated box is larger". Which is why I asked. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-88093169321585838882010-06-22T10:36:49.923-07:002010-06-22T10:36:49.923-07:00"Your YUV code points are a uniformly spaced ..."Your YUV code points are a uniformly spaced cubic lattice. The RGB color space you're trying to cover is a rotated cube relative to that lattice, and the AABB for any such rotated cube (which defines the range of output values) is always at least as large as the original cube."<br /><br />Yeah, well said. There is actually a way around this. I think it's in the paper on Piecewise Linear Haar that I link here :<br /><br />http://cbloomrants.blogspot.com/2008/09/09-08-08-1.html<br /><br />http://cbloomrants.blogspot.com/2008/09/09-11-08-2.html<br /><br />I also note that YCoCg is just two Haars : Haar[R,B] then Haar[G,B] <br /><br />So you could do a non-expanding YCoCg by doing two PLHaars.<br /><br />Not useful in practice.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-44375381963886841522010-06-22T01:12:10.214-07:002010-06-22T01:12:10.214-07:00"Didn't you write up previously that ther..."Didn't you write up previously that there's a YCoCg that's reversible (you just have to do some kind of odd/even analysis to undo the rounding)?"<br />YCoCg or any other YUV-like transform (i.e. transforms that are basically rotations of RGB + rounding) have to increase the dynamic range if they're to be reversible. Your YUV code points are a uniformly spaced cubic lattice. The RGB color space you're trying to cover is a rotated cube relative to that lattice, and the AABB for any such rotated cube (which defines the range of output values) is always at least as large as the original cube. The S-transform trick can only get you so far - as long as you code the three channels independently, you need the extra range.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-11293304626425816082010-06-21T09:18:33.689-07:002010-06-21T09:18:33.689-07:00" Didn't you write up previously that the..." Didn't you write up previously that there's a YCoCg that's reversible (you just have to do some kind of odd/even analysis to undo the rounding)? "<br /><br />Yeah but it goes to 9 bits. You can deal with that either by being lossy in chroma (dividing the chroma by 2) , or by escaping. That is, YCoCg followed by a DPCM predictor will have a range of [-256,256] but will almost always fit in [-128,128] , so you could just save one value to indicate "one more byte" and write the extra rare byte when needed.<br /><br />BTW both of these modes would make good sense for PNG2. (lossy YCoCg in particular would be valuable).cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-12247704665247341372010-06-21T03:52:23.095-07:002010-06-21T03:52:23.095-07:00This is the only lossless color conversion you can...<i>This is the only lossless color conversion you can do that is not range expanding (eg. stays in bytes).</i><br /><br />Didn't you write up previously that there's a YCoCg that's reversible (you just have to do some kind of odd/even analysis to undo the rounding)?Anonymousnoreply@blogger.com