ducha-aiki/ds-sac

This repository re-implements a computer vision algorithm called DS-SAC, which stands for Density Search for Sample Consensus. The specific case handled here is homography estimation, a common task where you find the geometric transform that maps one image to another using matching feature points. The code is an independent, from-scratch implementation based on a research paper, not the original authors' code, and it has not been checked against the official version. Most methods for this task use randomness, trying many small samples and hoping to find a good fit. DS-SAC takes a different approach: it is fully deterministic, meaning it produces the exact same result every time you run it with the same inputs. It starts with a broad fit on all points, then searches by progressively shrinking the point set to smaller top-percentile slices. It expands back out from the best slice, splits the points into separate groups based on how they deviate from the current model, and finishes with a refinement pass that gradually tightens the acceptance threshold. The code is written in Python and depends only on NumPy, a standard numerical library. Installing an optional package called numba makes the same logic run roughly nine times faster. Using it involves passing in two arrays of matching point coordinates and a threshold, and the function returns a 3x3 transform matrix plus a list indicating which points were inliers. There is also a batch interface for processing many pairs of images at once using multiple CPU cores. Benchmark results are included, comparing DS-SAC against three established alternatives, OpenCV RANSAC, MAGSAC++, and pydegensac, on two small standard test sets. DS-SAC lands in the middle of the pack: slower than the fastest baseline but ahead of one, with competitive accuracy. The results note that the test sets are small, so differences of a few percent should be treated as noise. A key practical advantage noted is that DS-SAC is bit-exact reproducible, whereas the randomized baselines vary slightly between runs. The full README is longer than what was shown.