tag:blogger.com,1999:blog-5246987755651065286.post574776144479740632..comments2021-07-18T12:41:01.986-07:00Comments on cbloom rants: 06-16-09 - Inverse Box Samplingcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-5246987755651065286.post-14116270119702863452009-06-17T13:37:17.068-07:002009-06-17T13:37:17.068-07:00I don't mean "linear" as in whether ...I don't mean "linear" as in whether the basis function is piecewise linear or not - I mean linear in the "linear operator" sense - *any* basis function based approach will not be awesome.<br /><br />The simplest way to get a "Non-linear" approach is to have something like a few different linear solutions, and pick some blend between them that's based on the local neighborhood. For example one obvious thing to do which I tried is to run an edge detector on the DC image and do different things when you see hard edges vs. smooth areas.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-60012899713015396372009-06-17T13:25:53.373-07:002009-06-17T13:25:53.373-07:00"BTW I believe that any linear reconstruction...<i>"BTW I believe that any linear reconstruction approach to these kinds of problems is wrong and doomed to suck."</i><br /><br />Maybe, but everything else seems way too expensive to actually compute, so I focused on linear just because it seems computationally feasible, and better than DC-nearest-neighbor. <br />Are there actually other options on the table? You appeared to write all your attempts off as too expensive.<br /><br />Also, I suspect any solution to this problem is either going to be ringy or blocky; my guess it's inherent to the problem. This applies to this solution, to hats, etc. Basically, you're trying to pack a certain amount of energy into the block; either it's well-distributed over the block (blocky), or you try to keep the edges nice and then it's overconcentred in the center (ringy).<br /><br />Also, the iterative solution seemed pretty reasonable to me, was it actually too ringy? My mexican hat is just a truncation of the iterative solution with the necessary cleanup to make the DC work, so I'm not sure how much worse it would be.<br /><br />Second, if every 8x8 block is, in the end, independent (the only hard constraint is the average DC), then you can use different solutions for different blocks. So if the deconvolution approach is too slow, but the mexican hat is too ringy, then if you end up in a place where 'oh well, i'll just use nearest neighbor aka DC replication', you could still do mexican hat, have a 'ring detector' (color falls outside of convex hull of nearby elements) and substitute the constant DC blocks in those places.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-38399658708347375672009-06-17T12:26:42.332-07:002009-06-17T12:26:42.332-07:00This is an old post on super res (slightly differe...This is an old post on super res (slightly different problem) :<br /><br />http://cbloomrants.blogspot.com/2007/11/11-14-07-1.html<br /><br />I think I have better approaches & understanding now as well as finding a bunch of papers.<br /><br />Kwang In Kim is a good place to start :<br /><br />http://www.kyb.mpg.de/~kimkicbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-87244607512639824632009-06-17T12:20:47.890-07:002009-06-17T12:20:47.890-07:00BTW Sean's limited range linear reconstruction...BTW Sean's limited range linear reconstruction basis (at the end of bilerp_dc.txt) is equivalent to using linear "mexican hat" basis functions.<br /><br />http://en.wikipedia.org/wiki/File:Wavelet_-_Mex_Hat.png<br /><br />Obviously you can do quadratic or cubic or whatever mexican hats, but it's not a very tasty solution because they ring too much.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-79182686074347150632009-06-17T12:19:32.075-07:002009-06-17T12:19:32.075-07:00"The other extreme would be just having a hug..."The other extreme would be just having a huge library of "typical" images and trying to find matching patches subject to some constraints to the transitions work"<br /><br />Yes, I've written and worked on that problem as well. It's slightly different because they generally don't require that down-sampling reproduces the original low res. It's usually called "super resolution" and there are now a lot of papers on it (better than that one).<br /><br />It's definitely something on my "wish list" that I would love to work on if I had a bunch of free time. I was working on it a bit at the end of my unemployment but I got distracted by the job search and whatnot. It's a very hard problem.<br /><br />BTW I believe that any linear reconstruction approach to these kinds of problems is wrong and doomed to suck.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-5270968651699601042009-06-17T12:12:52.467-07:002009-06-17T12:12:52.467-07:00Like a lot of image processing/computer vision pro...Like a lot of image processing/computer vision problems, this one is underdetermined in an "interesting" way, and different ways of regularizing it correspond to very different algorithms.<br /><br />Your approach (deconvolution) is at one extreme, with no particular assumption of how a "typical" reconstructed image should look, but very strong assumptions in the model (linearity of the reconstruction process, bandlimitedness of the box-filtered signal so deconvolution can be applied). The other extreme would be just having a huge library of "typical" images and trying to find matching patches subject to some constraints to the transitions work, like in <a href="http://graphics.cs.cmu.edu/projects/scene-completion/scene-completion.pdf" rel="nofollow">this</a> paper. This is equivalent to learning a statistical model of typical images and using the maximum a posteriori estimate with the downsampled image being your observation, and the main problem is that there's just too many "plausible" images to ever learn a representative sample.<br /><br />...which is where slightly stronger model assumptions would help. Add some basic color correction, for example; it needs to have a very limited range since otherwise it'd introduce too much ambiguity when trying to match the lowres image. Example-driven texture synthesis algorithms could be killer here, but this is basically the inverse problem - given this repeating structure, what is the most likely pattern to have generated it, and where have I seen it before?<br /><br />Damn, all very interesting, but I wouldn't know where to start :)ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-85228600707563464092009-06-17T07:52:15.890-07:002009-06-17T07:52:15.890-07:00Note that you can get a tuning factor by just havi...Note that you can get a tuning factor by just having two solutions and weighting between them.<br /><br />My writeup offers a "half-bilerp" approach for 3x3 taps on the DC; the best "half-bilerp" approach for 1x1 taps is the standard blocky DC reconstruction. You could weight between those, but obviously you'd have block artifacts.<br /><br />So the thing might be to solve for the best approach using 5x5 taps on the DC, and then try a tuning factor between the 3x3 tap and the 5x5 tap solutions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-13081135760872863902009-06-17T07:22:04.657-07:002009-06-17T07:22:04.657-07:00Er, correction, the simplified bilerp isn't tu...Er, correction, the simplified bilerp isn't tunable, I missed that there was another constraint on it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-43672029260376692952009-06-17T07:07:52.397-07:002009-06-17T07:07:52.397-07:00My attempt at a closed form solution to the iterat...My attempt at a closed form solution to the iterated bilerp, based on this general approach:<br /><br /><a href="http://nothings.org/remote/bilerp_dc.txt" rel="nofollow">bilerp_dc.txt</a><br /><br />I solved for both a full-width (sinc-like) thing which should match the iterated one, and then a simplified bilerp with a tunable parameter and a very local filter support (only need 3x3 DC values to do a given 8x8 block as 4 4x4 bilerps).Anonymousnoreply@blogger.com