Improving the Responsiveness of the Document Detector

Keeping the viewfinder smooth when detection is slow

Dropbox's document scanner overlays the detected document boundary on the live camera feed—a lightweight form of augmented reality. The challenge is that document detection is computationally heavy, while the camera delivers frames at 30 fps. On older devices, the earlier detection algorithm described in our previous post fell behind even after we leveraged vectorized instructions and GPGPU compute. This article walks through the three processing models we considered, the trade-offs of each, and the hybrid solution that made the scanner feel responsive on both new and old hardware.

For clarity, assume detection costs 100 ms per frame, while the camera produces a frame every 33 ms. The dilemma is inescapable: by the time a quad is computed, several newer frames have already been shown to the user.

Asynchronous processing: smooth video, stale overlays

The simplest approach is to let the camera run at its native rate and display every frame, computing quads on a background thread on a best-effort basis.

The result: the video stream stays buttery at 30 fps, but the overlay updates at roughly 10 fps and is always delayed relative to the image it was computed from. When the quad for a given frame finally appears, that frame has long since left the screen. The lag and choppiness are visible in the animation below, even though the underlying video is smooth.

Synchronous processing: correct quads, stuttered video

The alternative is to serialize capture and detection: grab a frame, run the detector, and display the result with its computed quad before moving on. Any frames that arrive while the detector is busy are simply dropped.

Here the quad is always perfectly synced to the displayed image, as shown below.

But the camera drops to 10 fps, and more bothersome is a constant 100 ms of latency between the physical document and what the viewfinder shows. That mismatch is uncomfortable for a user watching both the real paper and the screen—the same problem VR headsets have to fight.

Reusing work between frames

The two options above force a choice between smooth images and correct overlays. The way out is to note that adjacent camera frames are almost identical. If we already found the document quad in frame I₀, then in frame I₁ the same quad will be nearby—related by the camera motion between the two frames. If we could estimate that motion T, we could predict the new quad by transforming the old one: {T(v₀), T(v₁), T(v₂), T(v₃)}.

That converts a detection problem into a tracking one. Estimating the inter-frame transformation robustly, however, is a slow problem of its own: we experimented with keypoint matching via RANSAC, digest-based alignment, and brute-force search, and nothing was fast enough.

But there is a stronger prior available. Both frames contain a quad, and we already know the quad in the first. Instead of aligning whole images, we only need to locate that specific quad in the second frame. Treating the hypothesis as a quad, we evaluate edge strength along the candidate perimeter: the score is the line integral of the image gradient measured perpendicular to the quad's edges, so that a correct fit sits on strong document boundary edges.

Tracking only cannot stand alone—errors would accumulate over time. We therefore run both: the full detector continues to run in a loop to provide an accurate correction, while the lightweight tracker runs per-frame in between, predicting the quad for the current image based on the previous one. The handler waits just long enough for the quick tracking step before displaying the current frame together with the overlaid quad.

This yields the best of both earlier modes: a live viewfinder with an accurate, non-lagging overlay, at the cost of only a small increase in latency. The comparison table and a side-by-side animation—hybrid in blue, asynchronous in green, on an iPhone 5—illustrate the difference.

Localizing the quad without pixel-by-pixel work

For typical viewfinder motion—panning, zooming, and rolling—we can reduce the search space. The gyroscope gives us the roll angle between frames; we factor that out, and then only need to find the scale and translation of the previous quad.

Evaluating candidate quads naively would require costly line integrals along their perimeters for each hypothesis. But all candidates share only four edge orientations: the slopes of the four edges of the previous quad.

That structure allows precomputation of a sheared running sum table for each of the four slopes, integrating the gradient perpendicular to the edge direction. Each table sums contributions along one of those slopes across the image.

With these four tables, the integral over any candidate perimeter is O(1): look up the running sums at edges endpoints in the matching table, subtract to get the edge's contribution, and sum the four values. We can then scan over translations and a discretized set of scales to find the highest-scoring quad. The idea is functionally the same integral image trick that the Viola-Jones face detector uses.