My algorithm for colorizing the Prokudin-Gorskii plates consists of 3 stages:
The algorithm first calculates the offset vectors necessary to translate the green and red layers of into alignment with the blue layer.
The general approach is to shift a layer by some amount of rows and columns, then compare that layer to the blue layer using normalized cross correlation (NCC). The green and red layers are handled independently of each other.
The algorithm uses the pyramid refinement method. The pyramid refinement method uses scaled-down images to progressively refine a guess for the proper shift at the full size. For the low-resolution plates, the initial image is scaled down to 1/2 size. For the high-resolution plates, the initial image is scaled down to 1/32 size. (My implementation does not automatically detect the size of the image, so the user will need to change a line in colorize_skel.m.)
This allows the algorithm to use a smaller search window because the guessed center is being continually refined, so an additional required shift to refine the center is never that far away.
At each level in the pyramid, the algorithm does a brute-force search for the maximum correlation over a window of [-5, 5] pixels in both directions. Additionally, the image edges had colored bands which were throwing off the correlation calculations, so the algorithm only compares on the middle 65% of the image.
After determining the best shift at the scaled-down size, the algorithm will first shift the next level of the pyramid, which is double of the previous size (eg, 1/32 to 1/16), by the best guess shift determined at the scaled-down size before doing the brute-force search. Eventually, the algorithm reaches full size and runs one last search and terminates.
The effectiveness of the pyramid method borne out in practice. Prior to implementing the pyramid method, I needed to use a window of [-15, 15] to get good results on the low-resolution photos. As a result the algorithm had to run NCC on 31^2 photos per layer to find the best shift. This took several minutes. By using a window of [-5, 5] and scaling down to a minimum of 1/2 size, the algorithm had to run NCC on 2*(11^2) photos per layer, which took the run time down to under 2 seconds.
I noticed that many of the colored bands showed up as strong vertical or horizontal edges. Using MATLAB's built in edge detector (Sobel method, threshold of 0.05), the algorithm determined which pixels were part of an edge. This threshold is user configurable.
Then, if the number of edge pixels in any row or column was over a certain threshold (15% of the rows or columns in the photo), then the image would be cropped at that row or column. This threshold is user configurable.
The cropping was limited to only the outside of the image. This value is user configurable as a percentage of the rows and columns to determine an outside border to operate in.
This algorithm successfully cropped out most of the colored edges, but left some colored portions where one color was present but it faded into the rest of the image.
One major disadvantage with this algorithm is that it does not handle slightly slanted edges well. Imagine a vertical edge that spanned three pixels horizontally. Approximately 1/3 of the edge would exist in each column. Depending on the thresholds used, the algorithm would not handle this edge. An algorithm that calculated the edge length would work on this edge, but that would be getting pretty complicated.
To crop out these sections, I needed to do color similarity and remove rows and columns where one color was overwhelmingly present and the other colors were not.
The algorithm finds the average value of the three channels of color of each pixel, and if any individual channel is outside a threshold of variance from the average (70%), then the pixel was considered improperly colored. This threshold is user configurable.
Then, if the number of improperly colored pixels in any row or column was over a certain threshold (80% of the rows or columns in the photo), then the image would be cropped out at that row or column. This threshold is user configurable.
The cropping was limited to only the outside of the image. This value is user configurable as a percentage of the rows and columns to determine an outside border to operate in.
This algorithm had significant issues with overcropping on the lower resolution images. Lowering the variance threshold, decreasing the border percentage, and increasing the cropping threshold could decrease the incidence of these issues. Additionally, it did not crop all of the discolored portions.
As somewhat of a preservationist, I was somewhat disappointed with the results of this cropping. I feel that cropping out the black edges which were not part of the original plates is a good addition, but cropping out sections of the image that had degraded with time removes information at the edges that the photographer attempted to convey.
However, at this point, I was tweaking constants and not programming, and I was having much less fun so I left it as is. I suppose an algorithm to try ranges of constants and a scoring function based on the number of pixels kept could help me refine the constants...
Click for 100% resolution
Colorized | Cropped by edge | Cropped by color | Notes |
---|---|---|---|
Green: (43,6) Red: (87,32) Time: 240s original data |
|||
Green: (13,-6) Red: (133,-12) Time: 242s original data |
|||
Green: (-16,10) Red: (11,17) Time: 235s original data This image is slightly misaligned. I believe the bold colors of the girls' dresses created large contrast between the plates, so the plates would not correlate. |
|||
Green: (24,20) Red: (71,33) Time: 236s original data |
|||
Green: (50,39) Red: (106,60) Time: 236s original data I think this is my favorite image because its aligned really well and its a very intricate object. |
|||
Green: (55,9) Red: (117,11) Time: 240s original data |
|||
Green: (71,39) Red: (148,63) Time: 237s original data |
Colorized | Cropped by edge | Cropped by color | Notes |
---|---|---|---|
Green: (5,2) Red: (10,1) Time: 1.64s original data This picture was significantly overcropped on the bottom, using the edge cropper. I believe the grass was detected as individual edges so a higher edge detector threshold would help mitigate this problem. |
|||
Green: (7,3) Red: (14,5) Time: 1.72s original data This time, the left side is overcropped since the wood panel that should be there is missing. I believe the a higher average color variance would have helped here. |
|||
Green: (0,0) Red: (5,1) Time: 1.62s original data This picture was significantly overcropped on the right side. Notice the building has three columns of windows in the first image, and only two in subsequent images. The edge detector may have found the light pole. A higher edge pixels threshold would have helped here. |
|||
Green: (5,3) Red: (11,4) Time: 1.71s original data The color cropper worked really well here. |
|||
Green: (2,0) Red: (9,0) Time: 1.64s original data The color cropper saw the red splotches and ended up removing that entire set of rows. |
|||
Green: (4,2) Red: (9,2) Time: 1.76s original data You can see severe overcropping on the bottom. The edge detector saw the shadow as an edge. I'm not really sure how to get around this. Even a higher threshold would probably detect this edge. |
|||
Green: (4,1) Red: (13,1) Time: 1.73s original data The steeple on the building to the right was cropped out. The edge detector may have found each brick in that building as an edge and cropped accordingly. I believe the only reason why the edge detector did not crop more of the building is because of the border limits. If you look at my program output, it seemed to have cropped the maximum it was allowed. |
|||
Green: (-3,1) Red: (-4,1) Time: 1.61s original data |
|||
Green: (8,0) Red: (13,0) Time: 1.62s original data Hey, that's not Russian... |
|||
Green: (5,0) Red: (11,0) Time: 1.58s original data |
Images were taken semi-randomly from the Library of Congress's digitized Prokudin-Gorskii Collection
Colorized | Cropped by edge | Cropped by color | Notes |
---|---|---|---|
Green: (2,2) Red: (8,3) Time: 1.67s original data Again, severe overcropping from the edge cropper, likely due to the grass. |
|||
Green: (-3,1) Red: (1,0) Time: 1.69s original data |
|||
Green: (2,-1) Red: (7,-3) Time: 1.74s original data |
In addition to the cropping algorithms described earlier, my web page also validates! I always do my part to promote open standards. Can I get extra credit for that? :)