Sam, our team locksmith, tells the story of a customer who was locked out of her car, with her key in plain view on the driver’s seat. Instead of breaking into the car, Sam photographs the key and makes a new key out of the photo.
He did this in the early 80s. No computers. No megapixel imagers. Just an old-fashioned Polaroid and a lot of craftsmanship.
Stories of duplicating keys from photos go back decades. But automating that process with the pictures customers send us pushes the limits of modern cameras and computer vision.
Here’s a photo of my old apartment key. I carefully aligned my camera with my key so they’d be parallel to each other (so that the key is “fronto-parallel” to the camera, as photogrammetrists say):
A picture of my old apartment key. I was careful to keep the key and the camera parallel.
It’s straightforward to analyze this photo by hand. From the manufacturer of the key, we know that the distance between the bottom of the blade (the "root" of the key) to the bottom of each tooth ranges from 5.08 mm to 8.51 mm in increments of .38 mm (see the Anatomy article for some background). The highest cut, leaves 100% of the blade intact while the deepest cut leaves only 60% of the blade intact. The depths of the cuts increase in steps of 4%. The cuts are 0: 60%, 1: 64%, 2: 69%, 3: 73%, 4: 78%, 5: 82%, 6: 87%, 7: 91%, 8: 96%, 9: 100%.
A manual analysis of my key. The ratio between the height of the blade and the depth of each cut in the image is the same as their ratio on the actual key.
When the key is photographed straight on, the ratios of the cuts are correct as they appear in the image. In the case of my key, these cuts are at 56%, 59%, 73%, 62%, 67% of the blade height. The closest valid cut percentage for each of these are the 9,9,6,8,7 respectively. That’s all you need to cut my old apartment key.
But what about this photo?
A picture of the same key. This time, the camera and the key are slightly askew from each other.
It’s a picture of the same key, but the camera is slightly tilted away from the key.
The same analysis is now off by a full cut depth for teeth near the tip of the key.
Using the same technique, the cut depths now appear at 57%, 61%, 76%, 67%, 74%, corresponding to cuts 9,9,5,7,6. We’re off by a full cut on the teeth closer to the tip! What happened?
Here’s what went wrong. The groove lines, which are parallel to each other in reality, are slightly askew in the image.
The groove lines, which are parallel to each other on the key, are slightly askew in the image. These few pixels of skew caused the error in the bitting.
Parallel lines on objects do not necessarily stay parallel in a photo of the object. This is the same vanishing point effect that causes parallel railroad tracks to appear to converge in the horizon.
Parallel lines needn’t appear parallel in a photograph.
This effect is more salient when the object is close to the camera. Because we need closeup pictures of keys, this effect is very strong in the images we receive. For example, when the bottom of the key is 10 cm away from the camera and the tip is 11 cm away from the camera, a feature at the tip is imaged 10% smaller than a feature at the bottom. That’s more than two cut increments!
To analyze images of keys, we have to compensate for this perspective effect. Vanishing lines and the math to make them parallel again is well understood in the field of projective geometry. The problem is that these groove lines are difficult to detect accurately in images of keys. We’d have to localize these lines to within 3-4 pixels. That’s not easy to do. Here’s what the grooves look like when you zoom in.
A portion of the blade of the key. Can you locate the keyway grooves? The blue dot is 4 pixels wide. That’s how accurately we’d have to localize the keyway grooves to correct for the perspective effect. Not easy.
Between the shadows caused by the 3D geometry, the specular reflections off the metal, and the wear patterns on the surface, it’s very difficult to localize these lines more accurately than 10 pixels. We could conceivably rely on the geometry of the handle of the key, but the handles vary subtly across manufacturers of the same blank.
We’ll reveal how we get around these problems in upcoming posts.