• The Prokudin-Gorskii collection consists of blue, green, and red negatives of a subject. For example, we have a triple negative of Emir at right.

• In this project, we have created a program to automatically produce colorized photos from the triple-negatives in the Prokudin-Gorskii collection.

• Our procedure has 3-steps, explained further in the following sections.
  1. Extract the individual color channels from the original triple negative.
  2. Align the structures in these negatives to form a coherent colorized photo.
  3. Automatically trim border artifacts from these aligned images.

• We begin by extracting the blue, red, and green channels from the original triple-negative photo.

• Each color channel has approximately the same dimensions, so we simply divide the original image into three equally-sized images, vertically padding if the height is not divisible by 3.

• The rightmost image shows the output of this step.

Problem Description

• The pixels in the negatives extracted in Step 1 are not necessarily aligned because there are generally variations in their positions and the border widths between them.

• Aligning the negatives is equivalent to finding an $(x,y)$ displacement for channel so that every pixel position $(i,j)$ in each negative corresponds to the same structure.

• My alignment algorithm uses an image pyramid to efficiently compute these offsets:
  • The algorithm takes two grayscale color negatives $I_1^0$ and $I_2^0$ of the same shape, then recursively computes the displacement vector $\vec r_0$ that maximizes the objective $NCCS(I_1^0 + \vec r_0, I_2^0)$. (NCCS is defined below.)
  • To visualize this procedure, the surrounding figures show the optimal alignments at each level of the image pyramid

Alignment Algorithm

1. Set $R_0 = 1$ and $S_0 = 1$, where $R_k$ is the downsampling factor and $S_k$ is the maximum displacement in $x$ or $y$.

2. For $k\geq 0$, downsample each of $I_1^0$ and $I_2^0$ by $R_k$ to obtain $I_1^{k}$ and $I_2^k$, respectively.

3. If the largest dimension of $I_1^k$ exceeds 64, make a recursive call on $I_1^{k}$ and $I_2^{k}$ with resolution $R_{k+1} \equiv 2R_k$ and search radius $S_{k+1} \equiv 2S_k$.
   1. This recursive call will return a displacement vector $\vec r_{k+1}^*$ such that $I_1^{k+1} + \vec r^*_{k+1}$ and $I_2^{k+1}$ are well aligned.
   2. Note that $I_1^k$ has twice the dimensions of $I_1^{k+1}$, we have that $I_1^{k} + 2\vec r^*_{k+1}$ and $I_2^k$ are approximately well aligned.

4. Next, exhaustively examine all displacements $\vec d_k \in[-S_k, S_k]^2$ to find the vector $\vec d_k^*$ that best aligns $I_1^{k} + 2\vec r^*_{k+1}$ and $I_2^k$:

   $$\vec d_k^* = \argmax_{\vec d_k \in[-S_k, S_k]^2} NCCS\left((I^k_1 + 2\vec r^*_{k+1}) + \vec d_k,\ I_2^k\right)$$

5. Finally, return the displacement vector $\vec r_k^* \equiv \vec d_k^*+ 2\vec r_{k+1}^*$.

Defining NCCS

• NCCS: the Normalized Cross-Correlation between two Scharr-filtered, center-cropped grayscale images with the same shape.

• Motivation for each feature of this metric:

  • NCC: Since different channels have different baselines, it is a good idea to normalize before comparing them. Further, we’d like to ensure the structures between color channels are at the same pixel positions, and maximizing cross-correlation is a good way to do this.

  • Edge detection: Most borders of an object should be present in all colors, so we can align the structures in different color channels by aligning their edges. Edge detection filters like Scharr create sparse patterns in each color channel that have large NCC scores when they are properly aligned. This NCC score rapidly falls off when the images are not well aligned, so filtering our color channels with an edge detector is a good way to help of our alignment procedure converge on a truly optimal displacement vector.

  • Center-cropping: In my experiments, I found that it’s a lot easier to remove the image borders after alignment, so all the borders are still present during the alignment procedure. Since my metric relies on matching the edge-detections between color channels and the border-image transition is very sharp, my algorithm would often find strange alignments that tended to maximize the border-edge alignments between color channels, resulting in improperly aligned channels. A simple solution to this problem was excluding the edges from the metric calculations with a center crop.

• Notation
  • $I_1$: grayscale image.
  • $I_1^\prime$: center-cropped $I_1$.
  • $\Phi(\cdot)$: Scharr edge detection.

1. Given an aligned negative $I$ from Step 2 with dimensions $M\times N$, create the following slices of the borders of $I$.
   1. Top border: I[:M/10, :]
   2. Bottom border: I[9M/10:, :]
   3. Left border: I[:, :N/10]
   4. Right border: I[:, 9N/10:]

2. Apply the Canny edge detector with $\sigma=5$ to each of these slices.

3. Compute the median $\mu$ and standard deviation $\sigma$ of the distribution of edge-detection activations.

4. Threshold the edge detections by setting any detection with Z-score less than 2 to 0.

5. Find the column and row indices with the largest above-threshold activations, thus obtaining the top left $(r_0, c_0)$ and bottom right $(r_1, c_1)$ coordinates of the cropping rectangle.