Computational Photography Final Report - Automatic Timestamp Detection and Removal from Digital Photos

By: Stephen J. Guy
On: December 5th, 2008

Current Code: Code, Executable, Presentation

Progress Report 1, Progress Report 2, Progress Report 3

For my final project, my goal was to automatically detect and remove timestamps from digital images. This task breaks into two obvious goals: Timestamp Detection and Timestamp Removal.

Many digital cameras can automatically include a visible timestamp or datestamp directly on the pictures they take. This is often undesirable, especially as image metadata can easily store the time and date a picture was taken without modifying the visible picture. While experienced Photoshop users can remove timestamps manually, that is not an option for novices nor for batch processing of several images.

Challenges

The main challenge in this project is the lack of prior work. A related task is automated CAPTHCA cracking and other OCR software. However, these tasks face a different goal. Rather than locating text, the aim is to classify it. As such, in OCR it is sufficient be able to correctly guess the letter from a few curves, but not know the exact shape of the letter. In this work, it is important to know the entire shape of the letter, not just what it is. It is not clear that knowing the letters of the timestamp would be a direct indicator of its shape, especially because of the wide verity of differences in font. Additionally, the best CAPTHCA reading programs use priors to help decipher the characters. By assuming they are looking for words, they can use the guess of previous and proceeding characters to refine the current guess. Timestamps however, are often just a series of numbers, slashes, and dots. There is little predictive information to take advantage of. Most importantly, OCR programs generally rely on matching the edges of shapes to a database of characters. Both modifying and retraining a per-character feature database specifically for timestamps or creating a new database from scratch seemed more heavyweight than was appropriate for this task. The goal here was to find a lighter weight solution, based on features generally common to all timestamps.

Additionally, the lack of a labeled database of timestamps is limiting. Specially, it makes using learning based approaches difficult. Creating my own hand labeled set of timestamp images seemed daunting when I started this project, in retrospect, it might have been worth it.

Another problem is the variety of possible timestamps. As can be seen in the above collection, timestamps differ in color (red, orange, yellow, blue, and white), length (from 8 characters "2007 05 05" to 16 characters"2004/01/01 00:14:10"), numbers of lines (both 1 and 2 lines), position (any of the four corners), orientation, character size, etc. A fully robust technique should be able to handle all this variety.

Finally, JPEG compression is the source of most of the difficulty in detection. The JPEG compression of the timestamp adds difficulty in four separate ways. Firstly, the color of the timestamp is modified from what the camera puts on the image. Secondly, the color of the timestamp will now depend on the content of the image. Thirdly, the color of a timestamp can vary over an image depending on the local background. Lastly, JPEG compression can blur sharp edges which are a key feature of timestamps.

Despite all these challenges, the final system was able to successfully detect and remove timestamps automatically on verity of images.

Detection Algorithm

After a lot of experimentation I have found several features that were fairly well correlated with timestamps: Position, Color Value, Color Saturation, & Gradient Magnitude

1. 1. Position — Timestamps occur almost exclusively in the corners of images.
2. 2. Color Value — In HSV color space, timestamps have very high value (V) component.
   Presumably, this is to cause unnatural colors to maximize the contrast with surrounding pixels.
3. 3. Color Saturation — In HSV color space, timestamps tend not to have small saturation values.
   Again, this comes from the fact that timestamps are rarely dull, but colors with low saturation would be grayish. The exception is white timestamps which have low saturation, but are still striking against most backgrounds.
4. 4. Gradient Magnitude — Text is high frequency and should have strong edges. Better results were obtained when using the gradient in the value space. This helped bring out contrast in pixels with similar luminance
   
5. 5. Color Hue — Green pixels are specifically excluded from timestamps. No timestamps are green as it would not contrast well against grass.
   

The resulting algorithm is a 6 step process:

1. 1. Intial Timestamp Estimate — Find pixels that have all the above features common in timestamps
   
2. Median Filter — Median Filter the above result to reduce noise

2. 3. Choose Corner — Select the corner which has the most timestamp features, this should be the corner with the timestamp
   
3. 4. Develop Gausian Color Model — Use the timestamp pixels in the chosen corner to find mean and standard deviation of the timestamp color.
   
4. 5. Choose timestamp pixels — All pixels in the selected corner witch match the Gaussian color model and have high saturation or values are chosen as part of the timestamp.
   
5. 6. Dialate — The above process can be a conservative timestamp estimate on some pictures. By dilating 1 pixel from the result after step 4 an overestimate of the timestamp area will be made. This is okay for this application as the removal should replace the overestimated pixels with colors close to their original value.
   

Above we can see the results of checking the different features for each pixel of an image. Only pixels which meet all the above features are used on detect the location of the timestamp.

These pixels are then filtered to reduce noise, and the remaining pixels are taken as an initial timestamp guess. The corner with the most remaining pixels is chosen as the timestamp corner. All pixels in that corner which are of similar color to the initial timestamp pixels are chosen as the final timestamp.

Detection Results

Successesful Images

This successful data set contains a wide variety of pictures size, timestamp size, timestamp text and timestamp color and timestamp position.

Partial Sucesses

The timestamp is the same color as a portion of the ground...	So the color model picks up the ground too.
The timestamp is the same color as a part of my hand...	So my hand is picked up as part of the timestamp
Same story as above	This time much of my arm is picked up
Interestingly, these timestamps don't have just one color. This violates my assumption when trying to find an average timestamp color.

There are two interacting problems here. 1) The color of the timestamp changes in one image 2) Pixels near the timestamp are similar colors to the timestamp

Texture Synthesis Implementation

Per pixel texture synthesis is very slow. I've tried to implement an approximation which examines only every other patch, or every third patch. Furthermore, I only sample patches from the same corner as the timestamp. Even with these improvements, it can still take several minutes to remove a timestamp.

The overall approach is very similar to Efros and Leung. For each pixel the timestamp, a small patch around that pixel is examined. The remaining image is scanned for patches that look similar by comparing luminances using a Sum of Squared Differences (SSD). The image patch with the lowest SSD with the timestamp patch is used as a reference; the center of the image patch replaces the unknown timestamp pixel. This new pixel is now treated as know and the process repeats until all pixels are filled.

To order the synthesis, I choose the pixels in the order of how many non-timestamp neighbors the have. The theory is that the more pixels in the neighborhood which are know, the better estimation we can make of the unknown pixels.

Original Image	Precomputed Fill Order	Dynamically Updated Fill Order

I originally computed the fill order just once at the beginning of the fill process. Much better results were obtained by recomputing the fill order. The difference is very noticeable on artificial images as can be seen above. This better fill order also helps in natural images with regular structure, such as the siding of the snowy house in the Results section.

Results

Successes Images

I was glad to have a fair amount of success. This is a wide variety of pictures size, timestamp size, timestamp text and color and position, etc...

Partial Sucesses

The regular structure of the building can cause some difficulty	But, the inpainting works fine except for some minor blemishes.
This example appears to work, but...	The wire doesn't connect fully on the bottom right. A Criminisi style method might help.
The image looks mostly good	But I mistakenly cut of a girls pinky as part of the timestamp.
The timestamp is the same color as a part of my hand...	So my hand is inpainted in, unfortunately its replaced by my shirt, rather than as a hand

Limitations

The biggest limitation of my overall system comes from the inaccuracies in detecting the timestamp. In all the images where the timestamp was detected correctly it was removed with relative satisfying results. However, if the timestamp is completely off, there is no hope of removing it. For example, if the wrong corner is chosen, the filled in pixels will be meaningless. The wrong timestamp detection is particularly noticeable in the results with orange timestamps over skin. The skin is incorrectly labeled as timestamp, and when the algorithm removes the timestamp, it replaces the skin with the surrounding materials (often clothing).

Potential Improvements

The most immediate place for an improvement would be a more robust detection of the timestamp. After detecting candidate timestamp pixels, I currently median filter the results which can remove many pixels, and can degrade the quality of the detected timestamp. Much better, would be to take the noisy candidate timestamp pixels and try to detect a dominate color. This could be done by looking at a color histogram of the timestamp pixels, or by using some form of clustering.

Another improvement to be made in timestamp detection would be a machine learning based approach to selecting features. Currently, the features used in detecting the timestamps where hand selected and tuned. While the results are okay, it would be better to do this process automatically using a global optimization. A hand labeled collection of images and timestamps would allow an automated offline training process to select and tune the best features.

A simple dilate process is used as a way of expanding from a conservative subset of timestamp pixels to the entire timestamp. This is much to aggressive! The process often captures near non-timestamp pixels, or miss slight far timestamp pixels. Really, this is a labeling problem; there is a known set of timestamp pixels which we are trying to separate from the background. A graph cut based approach seems much more appropriate.

While I was happy with the hole filling results when using a dynamic fill order, there is still some room for improvement. As can be seen in the goat example, not taking gradients into account with fill order can lead to structures not properly connecting. The Criminsi et al. method would help alleviate this problem.

Lastly, I was not happy with the overall speed of the system. The vast majority of the time is spent in the hole filling. Because I am using a pixel-by-pixel approach, filling in large timestamps can take 10 minutes or more. I'd like to improve the speed by at least an order of magnitude. While optimizing the code will result in some improvement, switching to a patch based filling technique should vastly improve the speed. Again, Criminsi et al. report very fast times for their patch based implementation, while retaining satisfying results.

Conclusions

The overall system ended up worked very well on variety of images. There where cases where errors in timestamp detection where corrected by proper hole-filling which was a very nice result. While the overall success rate isn't as high as I would have liked, the system worked quite well on a wide verity on timestamps and images. There is certainly room for improvement, using clustering, graph cuts, and Criminisi et al.’s technique will clearly improve all the results, but the project clearly demonstrates that automatic detection and removal of timestamps from digital photos is possible.

On a more personal note, this was a very satisfying project to work on. At each checkpoint I was able to progress with a substantial improvement. From noisy detection, to a cleaner detection, to decent removal, to a proper fill order, the project moved along nicely for the entire semester. It was especially rewarding to used what I had learned in this class (and computer vision) in a novel fashion to tackle a problem without a know solution. All in all, this was one of my favorite projects in graduate school.

References