Feature Track Length

1. Background Knowledge

In Structure from Motion (SfM), a 3D point in the scene is reconstructed from its 2D projections (feature detections) across multiple images. Each time a feature detector finds the same physical point in a new image and the matcher links it consistently to previous views, that 2D detection becomes another observation of the same 3D point. The collection of all such observations for one 3D point is called a track.

Formally, a track is a set of tuples like $($\text{camera_id}$, x, y)$ that all correspond to the same underlying 3D point. The track length is just the number of distinct cameras (or images) in that set. Longer tracks give better geometry: more views mean more constraints on the 3D point position and camera poses, which helps triangulation and bundle adjustment to be more stable and accurate. Very short tracks (e.g., appearing in only 1–2 images) are often unreliable or unhelpful and are commonly filtered out.

2. Algorithm/Approach

At an algorithmic level, this problem is simply counting how many cameras observe a given 3D point. In coding-interview terms, this usually reduces to one of these patterns:

• If the input already groups observations by 3D point (e.g., a list of camera indices per point), then:

• The track length = size of that list (or the size of the set, if duplicates are possible).

• If the input is a flat list of observations (e.g., pairs/triples containing point ID and camera ID), then:

• Group by point ID, then count unique camera IDs per group.

So the core approach is: aggregate all observations belonging to the same 3D point and then count how many cameras are involved.

3. Step-by-Step Strategy

Assume you are given all observations for a single 3D point, or you first isolate them from a larger dataset:

1. Identify the observations of the target 3D point

• If input is already “for this point, here are its cameras”, you are done with this step.
• If input is global, filter observations where point_id == target_point_id.

2. Extract camera identifiers

• From each observation, take the camera_id (or image index).