This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
My father is a historical metrologist. He was a professional metrologist and a hobbyist historian before retirement and now he does both. He publishes books and papers on the matter and he uses really crappy pictures to illustrate them. The worst one he had, if I'm not mistaken, was a photo of a book page with a scan of an old newspaper with a roadsign in it.
I'm willing to help him without getting involved too much so, naturally, I write code. I wrote Unpager — a thing that bends pictures of book pages, straightens roadsigns, and cleans up dirt stains from old newspapers.
The latter appeared to be the most demanded feature. I called it darning because of how it works. It is surprisingly potent. With it, you can literally erase Russia from the political map of the world.
The selected rectangle is filled using only the pixel values on its border. The whole magic is in inverse-weights interpolation. In the general case, a pixel (x, y) in the rectangular selection of bitmap B bound by (x0, y0); (x1, y1) should have all its channels computed by this formula.
| B(x, y) = | B(x0, y) k(x-x0) + B(x1, y) k(x1-x) + B(x, y0) k(y-y0) + B(x, y1) k(y1-y) |
| k(x - x0) + k(x1 - x) + k(y - y0) + k(y1 - y) |
| k(z) = | 1 |
| z |
To fill the rectangle, you compute every pixel inside one by one. Since only the border contributes, the noise on the border gets dragged inside the rectangle and, if you look very closely, you'll see that the noise inside now consists of vertical and horizontal lines. It looks a bit like the image was darned by a thread and a needle.
The formula works for a rectangle with all four sides inside a bitmap. But what if we have a stain somewhere in the corner? Then only the two sides of the rectangle from inside the bitmap should contribute.
Luckily, with weight interpolation, it's trivial. If you don't want some particular B(xj, yi) to influence your result, assign its coefficient k(z) to 0. You don't want it — you throw it away, and that's it.
For instance, for the top left corner, the formula will automatically reduce itself to:
| B(x, y) = | B(x1, y) k(x1 - x) + B(x, y1) k(y1 - y) |
| k(x1 - x) + k(y1 - y) |
It's as simple as that. The whole algorithm is only 27 lines in JavaScript.
| Index #mathematics #algorithms #demos | ← there's more. |
+ Github & RSS |