Construction and exploitation of a 3D model from 2D image features

Karl S. Ni, Zachary Sun, Nadya T. Bliss, Noah SnavelyComputational Imaging 2010 · DOI

TL;DR

This paper presents a novel computer vision pipeline for automatically registering objects within 2D images to a pre-existing 3D model of the scene. By combining Structure from Motion (SfM) for scene reconstruction with object detection, the system can determine the real-world 3D coordinates of detected objects, enabling applications like enhanced image search and augmented reality.

What Problem Does This Paper Address?

The proliferation of digital images has created a wealth of visual data, but extracting meaningful spatial information from these images remains a challenge. While techniques like Structure from Motion (SfM) can reconstruct 3D scenes from collections of 2D images, and object detection algorithms can identify specific objects within an image, bridging the gap between these two capabilities to precisely locate objects in 3D space has been an open problem. Specifically, the paper addresses the need to answer "Where are specific objects in this image?" by determining their real-world 3D coordinates, which has implications for applications ranging from military surveillance to enhanced photo organization and retrieval.

Methods

The proposed approach integrates several key computer vision techniques into a two-phase pipeline: initialization and testing.

Initialization (Offline): * 3D Scene Representation: This phase leverages Noah Snavely's Photo Tourism framework. It begins with SIFT feature extraction from a collection of images to identify salient points. These features are then matched using Approximate Nearest Neighbor (ANN) search. Finally, Structure from Motion (SfM) with Bundle Adjustment is applied to simultaneously estimate the 3D structure of the scene (as a point cloud) and the camera poses for each input image. * Object Detection Training: This involves training an object detector using both positive examples (objects of interest) and negative examples (background patches). The paper notes that for certain objects like faces and cars, their features might not be well-represented in the SfM point cloud, suggesting they should be handled separately.

Testing (Online): * Incremental Image Matching: A new test image is matched against the pre-computed 3D point cloud. Instead of matching to individual images, the system matches features from the test image to the representative features of the voxels in the 3D point cloud. This is achieved by finding the closest feature in the point cloud and using a ratio test to validate matches. * Object Detection: Standard object detection algorithms (specifically mentioning Viola and Jones with an OpenCV implementation for faces) are used to identify objects of interest within the test image. * Projective Object Registration: This is the core novel contribution. Once an object is detected and its 2D bounding box is obtained, and the image has been registered to the 3D point cloud, the system determines the object's real-world 3D coordinates. This involves: * Optimal Feature Selection: Identifying a "best" feature within the detected object's vicinity based on criteria like re-projection error, feature count, and distance from the camera center. * Single-View Camera Geometry: Using the selected optimal feature and camera parameters to determine the object's position relative to the camera. * Distance Alignment: Projecting the object onto a plane parallel to the image plane and using assumptions about the object's size (e.g., typical face size) to derive its 3D real-world coordinates.

Datasets

  • Training/Reconstruction: A dataset of 1201 images of the Boston skyline, taken from MIT campus, was used to reconstruct the 3D point cloud. These images were at 8MP resolution, and some were also decimated to 10MP, then by 2 and 4, to test across scales.
  • Testing: A subset of 330 images from the Boston skyline dataset was used for testing and cross-validation.
  • Negative Set: An additional 319 images of the New York City skyline from Flickr were used as a negative set, meaning these images should not be part of the reconstructed scene.
  • Object Detection Training Data: For face detection, a mix of 4916 hand-labeled faces (from Peter Carbonetto) and post-processed versions of the UCD database were used. The negative set for object detection was hand-selected from the 1201 skyline images.

Key Insights and Ideas

  • Decoupling Scene Reconstruction and Object Registration: The paper effectively separates the problem into two stages: first, building a 3D representation of the scene, and second, detecting and locating objects within that scene. This modularity allows for leveraging existing powerful SfM and object detection techniques.
  • Matching to Point Cloud, Not Images: For incremental image matching, matching features directly to the aggregated 3D point cloud (via representative voxel features) is more efficient and robust than re-running SfM or matching against all previous images.
  • Object Features vs. Scene Features: The authors highlight that features of "interesting" foreground objects (like faces, cars) often reconstruct poorly in 3D via SfM. This insight justifies treating object detection and registration as a separate, subsequent step rather than relying solely on SfM features for object localization.
  • Leveraging Object Size for 3D Estimation: When direct 3D measurement is ambiguous, using prior knowledge about the typical size of an object (e.g., a human face) can be a crucial heuristic for estimating its real-world 3D coordinates.

Key Results

  • The system successfully reconstructs a 3D point cloud of the Boston skyline from 1201 images.
  • The image matching component demonstrates a low false alarm rate, especially for images clearly outside the reconstructed scene (e.g., forests, indoors).
  • The object registration pipeline can determine real-world measurements (3D coordinates) of detected objects.
  • The paper presents error analysis showing that registration error increases with distance from the camera, and that the primary source of error is often the image registration phase rather than the object registration itself. Figures 5 and 6 illustrate these error trends.

Limitations and Future Work

  • Approximations in Object Size: The reliance on assumed object sizes for 3D estimation introduces approximations. The paper acknowledges that the bounding box size derived from detectors can be imprecise, and this is a topic for future work.
  • Image Registration Sensitivity: The accuracy of the entire pipeline is sensitive to the quality of the initial image registration. Improving the robustness of image registration, particularly for challenging image attributes, is an area for future research.
  • Object Detection Flexibility: The authors suggest that making object detection classifiers more flexible in terms of what targets they can detect and their sensitivity would be beneficial.
  • Data Fusion: A significant area for future work is fusing more data sources, such as LiDAR, aerial imagery, and videos, to drastically improve accuracy and precision in object registration.
  • Skeletal Graph Construction: Investigating skeletal graph construction for observing connectivity could improve image registration.

Summary updated

BibTeX
@inproceedings{ni2010construction,
  author = {Karl S. Ni and Zachary Sun and Nadya T. Bliss and Noah Snavely},
  title = {{Construction and exploitation of a 3D model from 2D image features}},
  booktitle = {Computational Imaging},
  year = {2010},
  doi = {10.1117/12.849919},
}
Figure