images of the
russian empire

approach

After the plate is read, we convert it to floating point in the range [0, 1] (so the scan results are in the same scale regardless of JPEG or TIFF) and cut it into three equal-height frames. When aligning, we only try to align based on the central 80% of each frame and trim off 10% every side. This is because the scan has borders which are 1) irrelevant and 2) high contrast. In the pseudocode, trimming is denoted as INTERIOR. We cover why this matters more in section 03.

The two cropped frames are then scored with one of two metrics, written in NumPy:

Both return a score where greater the better, which is why we have the minus sign for L2. L2 is the Euclidean distance between the two frames viewed as vectors, and greater the L2 value, the "more distance" the vectors are. We simplify the L2 in two ways. First, we drop the square root as L2 is monotonic anyways, and second, negate the sum, which turns “smallest distance” into “largest score”. NCC is similar: each frame has its mean subtracted and the product is divided by the two norms, so the result is the cosine of the angle between the mean-centered frames, +1 for a perfect match, and unaffected by a frame being brighter or more contrasty overall. As both metrics point the same way, we can now use these metrics to design an alignment function.

Searching for the right alignment is essentially a double for loop over every shift in a square window around a center, trying to find the best shift. The single-scale alignment is that search with a ±15 window around zero, 31 × 31 = 961 candidates per frame. Inside the code a displacement is (dy, dx), rows then columns. On this page the same numbers are written as (x, y).

Finally the two winning displacements are applied and the frames are stacked in RGB order.

The scores over the whole window form a surface with a single clear peak. For the cathedral, green peaks at (2, 5) and red at (3, 12). The surface is pretty smooth within the window and the peak is likely to fall somewhere in the center of the image, which is why this sort of brute-force approach works. However, this approach will not work for much larger images where the "center" is also larger.

results on the low-resolution plates

Left is the naive stack, right is the aligned result. L2 and NCC chose the same shifts on all three, so we only show one output per plate.

A natural question that arose was why 10% margin? Initially, 10% margin was chosen as a magic number. We did a rough estimate on how big the margins were on average and settled on 10%. However, it would be nice to know if this trimming is actually meaningful. We re-ran the raw-pixel NCC alignment on all fourteen course plates with the scoring margin set to 0%, 5% and the 10% (default). With no margin at all, only three of the fourteen results land within two pixels of the 10% answer. Five of the plates produce terrible results. Even the little cathedral goes wrong, to g (−1, 1) and r (−1, 7). 5% margins are much better, but the church’s green frame is still 16 pixels off. At 10% the only failure left is the Emir, and that one has nothing to do with borders (section 07).

Take the harvesters as an example. The plate has thick white and black bands along the top and left which the search algorithm is eager to line up, dragging the green frame 58 pixels away from where the people actually are.

approach

Brute-forcing on full-resolution scans are, well, very time consuming: there are about 3200 × 3600 pixels per frame, each 16 bits deep, and the frames can be shifted by over a hundred pixels. A search window wide enough to contain that, say ±180 pixels, has 361 × 361 = 130,321 candidates, and for each candidate, we have to correlate an eleven-megapixel image. This takes way too much time. The fix is to match small-scale versions of the photos and then make small corrections as while zooming back in.

We can build this scale-in alignment recursively, called the pyramid aligning method. Each frame is halved until the shorter side drops below 300 pixels, which then we run the ±15 exhaustive search exactly as in section 02. Coming back up, the estimate from the level below is doubled, because every pixel there is two pixels here, and refined with a ±3 search centered on the doubled guess.

For the church plate, this is five levels, 3202 × 3634 down to 200 × 227. Now instead of the ~130,000 comparisons, we only need to make 1157 comparisons. Of the 1157 comparisons, only 49 of them are run on the full frames. We reduce the runtime to about three seconds per plate on a laptop.

walking through the church down the pyramid

The table follows both frames of the church plate from the image above. On the 200 × 227 image the red frame is best at (0, 4); doubled that is (0, 8), the ±3 refinement moves it to (−1, 7), and so on up to (−4, 58) at full resolution.

Below we show all fourteen course images, aligned with the pyramid and raw-pixel NCC using one set of parameters: 10% scoring margin, ±15 at the coarsest level, ±3 refinement, 300-pixel stopping size. Thirteen images are reconstructed well. Reconstructing The Emir fails and we will discuss why in later sections.

The L2 and NCC metrics agree for most images, but they seriously disagree for some images where the frames differ in brightness. Let’s look at the church: NCC puts the red frame at (−4, 58), while L2 computes it at (267, 64), which is very far off. L2 measures absolute intensity differences, and the sky, water and walls of the church have different brightness in the red exposure than in the blue one, so the sum of squared differences is minimized not by matching structure but by finding some overlap of dark against dark and light against light. NCC subtracts the mean and normalizes the contrast of each frame before comparing, which helps remedy that problem. From now on, we will consider NCC the better metric and use it.

With raw pixels and NCC, the Emir’s green frame aligns fine at (24, 49), but the red frame ends up at (−205, 141). The culprit is Emir's robe, which is very, very blue. NCC removes differences in overall brightness and contrast, but it still assumes that what is bright in one frame is bright in the other. Emir's robe, being the largest object in the picture, breaks this assumption. His robe is almost white in the blue exposure and nearly black in the red one, so the robe region of the two frames are anti-correlated, causing a bad alignment score for the correct alignment.

We showed that the difference in brightness was the culprit for Emir’s frames. Fortunately, though, the edges are still similar: the outline of the robe, the pattern on the fabric and the doorway are in the same places in all three exposures regardless of brightness. So instead of correlating pixel values, we can correlate based on edge strength. Each frame is smoothed with a Gaussian (sigma 2) and passed through a Sobel filter, which gives the gradient magnitude at every pixel. We then run the pyramid search runs on the edge maps.

That fixes the Emir and the rest of the thirteen images are still reconstructed the same, so this is not a one-off fix.

but why blur?

Initially, we tried to run Sobel on the raw frames, but it looked worse than raw pixels on several plates even though it fixed the Emir. The reason is film grain. At full resolution the scans are noisy, and a gradient filter detects the grains as small edges. Since the grain is different on each frame, so the edge maps are full of random edges that confuses the alignment metrics. A light Gaussian before the Sobel removes the grain but keeps the real edges, removing the drift.

We pulled three more scans from the Library of Congress and ran them through the same pipeline with the same parameters. All three align on the first try to recreate the color images.

Now we can see the real downside of Prokudin-Gorskii’s method with the yurt plate. After we recreate the image, the reed wall and carpet resolutions are very crisp. When we zoom in, however, the woman’s necklace is less aligned. It’s really difficult for people to stay still for long durations of time, so regardless of any alignment technique, it is very hard to capture potentially moving subjects in this way.

Below we show all computed shifts for the green and red frames relative to blue. We highlighted cells where the alignments fail. As discussed in the previous section, NCC is better than L2, so for the three extra scans, we only ran on NCC. Note that alignment for church, as discussed, fails on L2, but still succeeds on NCC. Only Emir fails on both. It is also very interesting that for most images, using edges versus actual image gave us pretty similar results. However, edge-based scoring is especially powerful in the case of Emir.