Just for fun, I improved the algorithm a bit. Here’s what it does now:
Still not perfect—there’s some residual banding that is never going to be 100% removable but could be made much better with more understanding of the statistics of typical images, and something at the right-hand side that seems like the existing algorithm ought to be doing better and I’m not quite sure why it doesn’t. But I don’t feel like taking a lot more time to debug it.
You’re seeing its performance on the same input image that I used for testing it, so it’s always possible that there’s some overfitting. I doubt there’s much, though; everything it does is still rather generic.
(In case anyone cares, the changes I made are: 1. At a couple of points it does a different sort of incremental row-by-row/column-by-column optimization, that tries to make each row/column in succession differ as little as possible from (only) its predecessor, and doesn’t treat wrapping around at 255⁄0 as indicating an extra-big change. 2. There’s an annoying way for the algorithm to get stuck in a local minimum, where there’s a row discontinuity and a column discontinuity and fixing one of them would push some pixels past the 255⁄0 boundary because of the other discontinuity; to address this, there’s a step that considers row/column pairs and tries making e.g. a small increase in pixel values right of the given column and a small decrease in pixel values right of the given row. Empirically, this seems to help get out of those local minima. 3. The regularizer (i.e., the “weirdness”-penalizing part of the algorithm) now tries not only to make adjacent pixels be close in value, but also (much less vigorously) to make some other nearby pixels be close in value.)
I am fascinated by the amount of effort you put into writing a comment.
I understand the call of duty and sometimes spend 30 minutes writing and editing a short comment. But designing an algorithm to prove a concept, and writing an application… wow!
(Could you perhaps expand the comment into a short article? Like, remove all the quarrel, and just keep it like: “this is a simple algorithm that achieves something seemingly impossible”; perhaps also with some pseudocode. Because this is interesting per se, in my opinion, even for someone who hasn’t read this thread.)
Thanks for the kind words! I guess it might be worth making into an article. (And I agree that if so it would be best to make it more standalone and less debate-y, though it might be worth retaining a little context.) I’m on holiday right now so no guarantees :-).
Just for fun, I improved the algorithm a bit. Here’s what it does now:
Still not perfect—there’s some residual banding that is never going to be 100% removable but could be made much better with more understanding of the statistics of typical images, and something at the right-hand side that seems like the existing algorithm ought to be doing better and I’m not quite sure why it doesn’t. But I don’t feel like taking a lot more time to debug it.
You’re seeing its performance on the same input image that I used for testing it, so it’s always possible that there’s some overfitting. I doubt there’s much, though; everything it does is still rather generic.
(In case anyone cares, the changes I made are: 1. At a couple of points it does a different sort of incremental row-by-row/column-by-column optimization, that tries to make each row/column in succession differ as little as possible from (only) its predecessor, and doesn’t treat wrapping around at 255⁄0 as indicating an extra-big change. 2. There’s an annoying way for the algorithm to get stuck in a local minimum, where there’s a row discontinuity and a column discontinuity and fixing one of them would push some pixels past the 255⁄0 boundary because of the other discontinuity; to address this, there’s a step that considers row/column pairs and tries making e.g. a small increase in pixel values right of the given column and a small decrease in pixel values right of the given row. Empirically, this seems to help get out of those local minima. 3. The regularizer (i.e., the “weirdness”-penalizing part of the algorithm) now tries not only to make adjacent pixels be close in value, but also (much less vigorously) to make some other nearby pixels be close in value.)
I am fascinated by the amount of effort you put into writing a comment.
I understand the call of duty and sometimes spend 30 minutes writing and editing a short comment. But designing an algorithm to prove a concept, and writing an application… wow!
(Could you perhaps expand the comment into a short article? Like, remove all the quarrel, and just keep it like: “this is a simple algorithm that achieves something seemingly impossible”; perhaps also with some pseudocode. Because this is interesting per se, in my opinion, even for someone who hasn’t read this thread.)
Thanks for the kind words! I guess it might be worth making into an article. (And I agree that if so it would be best to make it more standalone and less debate-y, though it might be worth retaining a little context.) I’m on holiday right now so no guarantees :-).