Skip to content

triangulation

triangulation #

triangulate — tracks placed in the world by the cameras that saw them.

  1. Pixels. Each frame's keypoints give the pixel every track row names; the frames' poses give the cameras.
  2. Solve. Every track is triangulated by the N-view DLT (geometry.triangulated) from all of its views at once.
  3. Check. A point survives only when two of its views see it from at least MIN_ANGLE_DEGREES apart, it lies in front of every one of them, and it reprojects within MAX_REPROJECTION_PX; triangulated_tracks is this solve-and-check, which the incremental reconstruction reuses.

track_colors(colors, track, camera, keypoint) #

The mean keypoint colour of each track, one uint8 row per distinct track in order.

Source code in capturegraph-recipes/capturegraph_recipes/sfm/reconstruction/triangulation.py
def track_colors(
    colors: list[np.ndarray],
    track: np.ndarray,
    camera: np.ndarray,
    keypoint: np.ndarray,
) -> np.ndarray:
    """The mean keypoint colour of each track, one ``uint8`` row per distinct track in order."""
    offsets = np.cumsum([0, *(len(found) for found in colors)])
    all_colors = np.concatenate(colors) if colors else np.zeros((0, 3))
    sampled = all_colors[offsets[camera] + keypoint].astype(np.float64)
    ids, inverse, counts = np.unique(track, return_inverse=True, return_counts=True)
    summed = np.zeros((len(ids), 3))
    np.add.at(summed, inverse.reshape(-1), sampled)
    return np.rint(summed / counts[:, None]).astype(np.uint8)

triangulate(frames, tracks) #

The sparse model of frames' poses and the tracks they triangulate.

Every frame's pose is a camera of the result, keyed by its index; a point's colour is the mean of its keypoints' colours; the observations are the kept tracks' rows.

Parameters:

Name Type Description Default
frames Array[PosedImage]

The posed images the tracks index.

required
tracks Tracks

The tracks of frames.image.

required
Source code in capturegraph-recipes/capturegraph_recipes/sfm/reconstruction/triangulation.py
@cg.pure_function("sfm.triangulate/1")
def triangulate(frames: cg.Array[PosedImage], tracks: Tracks) -> Reconstruction:
    """The sparse model of ``frames``' poses and the ``tracks`` they triangulate.

    Every frame's pose is a camera of the result, keyed by its index; a
    point's colour is the mean of its keypoints' colours; the observations
    are the kept tracks' rows.

    Args:
        frames: The posed images the tracks index.
        tracks: The tracks of ``frames.image``.
    """
    pixels: list[np.ndarray] = []
    colors: list[np.ndarray] = []
    for frame in cg.logging.progress(frames, label="Reading keypoints"):
        found = keypoints(frame.image).arrays()
        pixels.append(found["xy"])
        colors.append(found["color"])
    rows = tracks.arrays()
    cameras = Cameras.of([frame.pose for frame in frames])
    points, kept, rejected, errors = triangulated_tracks(
        cameras,
        pixels,
        rows["track"],
        rows["image"],
        rows["keypoint"],
    )
    observed = np.isin(rows["track"], kept)
    _, point = np.unique(rows["track"][observed], return_inverse=True)
    cg.logging.info(
        "Triangulated",
        points=int(len(points)),
        rejected_angle=rejected["angle"],
        rejected_behind=rejected["behind"],
        rejected_reprojection=rejected["reprojection"],
        median_reprojection_px=float(np.median(errors)) if len(errors) else 0.0,
    )
    return Reconstruction(
        cameras=cg.Map[cg.String, cg.Pose](
            {camera_key(index): frame.pose for index, frame in enumerate(frames)}
        ),
        points=cg.PointCloud.of_points(
            points.astype(np.float32),
            track_colors(
                colors, rows["track"][observed], rows["image"][observed], rows["keypoint"][observed]
            ),
        ),
        observations=Observations.of(
            point=point.reshape(-1),
            image=rows["image"][observed],
            keypoint=rows["keypoint"][observed],
        ),
    )

triangulated_tracks(cameras, pixels, track, camera, keypoint) #

Every track solved from its rows and checked.

Parameters:

Name Type Description Default
cameras Cameras

The cameras the camera column indexes.

required
pixels list[ndarray]

Each camera's keypoint pixels, indexed by camera then keypoint.

required
track ndarray

The track of each row; rows are grouped by track.

required
camera ndarray

The camera of each row.

required
keypoint ndarray

The keypoint of each row.

required

Returns:

Type Description
ndarray

(points, kept, rejected, errors): the N×3 points of the kept

ndarray

tracks, those tracks' ids in point order, how many tracks each

dict[str, int]

rejection reason removed, and the kept points' mean reprojection

ndarray

errors in pixels.

Source code in capturegraph-recipes/capturegraph_recipes/sfm/reconstruction/triangulation.py
def triangulated_tracks(
    cameras: Cameras,
    pixels: list[np.ndarray],
    track: np.ndarray,
    camera: np.ndarray,
    keypoint: np.ndarray,
) -> tuple[np.ndarray, np.ndarray, dict[str, int], np.ndarray]:
    """Every track solved from its rows and checked.

    Args:
        cameras: The cameras the ``camera`` column indexes.
        pixels: Each camera's keypoint pixels, indexed by ``camera`` then ``keypoint``.
        track: The track of each row; rows are grouped by track.
        camera: The camera of each row.
        keypoint: The keypoint of each row.

    Returns:
        ``(points, kept, rejected, errors)``: the N×3 points of the kept
        tracks, those tracks' ids in point order, how many tracks each
        rejection reason removed, and the kept points' mean reprojection
        errors in pixels.
    """
    offsets = np.cumsum([0, *(len(found) for found in pixels)])
    all_pixels = np.concatenate(pixels) if pixels else np.zeros((0, 2))
    ids, starts = np.unique(track, return_index=True)
    ends = np.append(starts[1:], len(track))
    points: list[np.ndarray] = []
    kept: list[int] = []
    errors: list[float] = []
    rejected: dict[str, int] = dict.fromkeys(REASONS, 0)
    for id_, start, end in zip(ids, starts, ends, strict=True):
        views = camera[start:end]
        seen = all_pixels[offsets[views] + keypoint[start:end]]
        point = triangulated(cameras, views, seen)
        reason = rejection(cameras, views, seen, point, MIN_ANGLE_DEGREES, MAX_REPROJECTION_PX)
        if reason is not None:
            rejected[reason] += 1
            continue
        points.append(point)
        kept.append(int(id_))
        errors.append(
            float(
                np.linalg.norm(
                    cameras.project(views, np.broadcast_to(point, (len(views), 3))) - seen,
                    axis=1,
                ).mean()
            )
        )
    return (
        np.array(points).reshape(-1, 3),
        np.array(kept, dtype=np.int64),
        rejected,
        np.array(errors),
    )