28.1 Photo mosaics🔗⧉

Photography stopped being scarce a long time ago. Phone cameras have made vast personal and public image collections routine. A single archive can contain more photographs than its owner can inspect individually. That is a change of kind, not of degree: when photographs are that abundant, the interesting object is no longer the single picture but the collection. A pile that large is simultaneously a problem (you cannot look at it, search it, or curate it by hand) and an opportunity (it is, in aggregate, a sample of the visual world dense enough to reconstruct places, learn what scenes look like, and build new images out of old ones). This whole part is about treating the collection as the unit of computation: searching, curating, mosaicking, and reconstructing the world from collections. We start with the most literal version of "build a picture out of other pictures."

A photomosaic is built from one simple instruction repeated over a grid. Take the target image, for example a portrait, and downsample it to a coarse grid of cells, each cell a single average color. Then, for every cell, reach into a tile library of thousands of small photographs and pick the one whose appearance best matches that cell. Lay the chosen tiles down in place of the cells, and the assembled wall of photographs reads, from far enough away, as the original target. Up close it dissolves back into hundreds of unrelated snapshots; from across the room it snaps into the portrait. That two-distances-two-images effect is engineered, not accidental.

The matching at the heart of it is a nearest-neighbor search over an image database, the same primitive that, scaled up and dressed in learned features, drives every method in this part (Chapter 28.2, Retrieval). For each target cell you compute a descriptor and ask the tile library for the photo whose descriptor is closest. The simplest descriptor is a single mean color: average each library tile down to one RGB value, average each target cell the same way, and match by nearest color in RGB space. A slightly richer descriptor is a small low-resolution thumbnail of each tile, a handful of pixels, matched by sum-of-squared-differences against the equally-downsampled cell, so that not just the average color but the coarse internal layout (a dark top, a bright bottom) lines up. Either way the recipe is identical: downsample the target, describe each cell, and run a per-cell nearest-neighbor query against the tile library (Figure 28.1.1⛶ fullscreen).

The original popular photomosaics are Robert Silvers and Michael Hawkins's Photomosaics (around 1996), and the technique was given an algorithmic treatment by Finkelstein and Range; from there it became a standard teaching case for nearest-neighbor matching over an image collection. It makes such a good first example because it shows where the difficulty lives: the matching is trivial, and almost all of the craft is in everything that surrounds it (color correction, repeat avoidance, and the multi-scale layout), which is exactly the texture of real collection-scale image problems.

28.1.1 The tiling-and-matching pipeline🔗⧉

Strip the pipeline to its bones and it is three steps. First, downsample the target to the grid resolution, with one descriptor per cell, where the grid spacing is the tile size in the final image. Second, describe each cell: mean color for the cheap version, a small thumbnail descriptor for the better one. Third, match each cell to the library by nearest neighbor under that descriptor, and paste the winning tile into the cell. The coarseness of the target downsample is the most important parameter: it sets how many tiles span the image, and therefore the viewing distance at which the illusion fuses.

The descriptor choice is an important design decision, and it is a miniature of the descriptor question that runs through all of Chapter 28.2, Retrieval. A mean color is one number per channel and matches in constant time per comparison; it is blind to everything but average tone, so a tile of a red barn and a tile of a red sunset are interchangeable. A low-resolution thumbnail descriptor, say a $4\times4$ or $8\times8$ downsample, keeps a little spatial structure, so the chosen tile shares not just the cell's color but its rough gradient, which markedly improves the read at intermediate distances. Richer still, one could match on a small texture or edge descriptor, but for photomosaics the returns flatten quickly: the eye is going to throw the tile detail away anyway.

Two implementation details matter in practice. The library tiles should be pre-cropped to the cell aspect ratio and pre-summarized to their descriptors once, up front, so the per-cell query is a fast lookup rather than a re-computation. And because the target cell and the tile must be compared on equal footing, both are reduced to the same descriptor resolution before the distance is taken: exactly the downsample-then-compare discipline that keeps the comparison meaningful.

28.1.2 Color correction and avoiding repeats🔗⧉

Pure nearest-neighbor matching has two visible failure modes, and the craft of a good photomosaic is in fixing both. The first is color mismatch: even the best-matching tile is rarely the exact color the cell wants, and a grid of slightly-off tiles looks muddy. The standard remedy is a per-tile color correction, which gently shifts each placed tile's color toward its target cell's color, by tinting or a mild channel scaling, so the assembled grid carries the target's color field faithfully while each tile stays recognisably a photograph. There is a dial here: correct too little and the target washes out; correct too much and the tiles all bleed toward flat color patches and lose their identity as photos. The pleasing setting is a partial nudge, not a full repaint.

The second failure mode is repetition. With a finite library and a greedy nearest-neighbor rule, large flat regions of the target, such as a clear sky or a cheek, will all match the same best tile, producing conspicuous blocks of identical photographs that shatter the illusion of variety. The fix is to forbid or penalize reuse: once a tile is placed, remove it from the candidate pool, or down-weight it for nearby cells, so the search is pushed to its second- and third-best choices and the grid stays visually diverse. This turns the per-cell independent nearest-neighbor search into a mildly constrained assignment: which can still be solved greedily with updated costs, or optimized jointly at greater expense, and it is the difference between a photomosaic that looks crafted and one that looks like a tiling bug.

28.1.3 Multi-scale and irregular tilings🔗⧉

A uniform grid spends the same number of tiles on a featureless sky as on a detailed eye, which is backwards: the eye needs fine tiles to render its structure, the sky needs almost none. Multi-scale tilings fix this by varying the tile size across the image, with small tiles where the target has high-frequency detail and large tiles where it is smooth, typically driven by a quadtree that subdivides only where the target's local variance is high. The result spends the tile budget where the perception actually needs it, sharpening faces and edges without wasting photographs on flat fields.

The same logic pushes toward irregular tilings that abandon the square grid altogether, packing tiles of varying shape, or jittering their placement, so the assembled image avoids the tell-tale regular lattice and reads more like a continuous picture. These retain the same matching operation but need additional layout rules: each cell, whatever its size or shape, is still described and matched by nearest neighbor against the library. The multi-scale machinery simply decides which cells to ask about, leaving the matching engine untouched: a clean separation of "where to look" from "what to match," which recurs throughout the part.

28.1.4 Why it resolves into the target at a distance🔗⧉

A photomosaic works because of the viewer's visual system, not because of any special property of the matching algorithm. Human vision is multi-scale and effectively low-pass at a distance: as you step back, the fine detail of each tile shrinks below your eye's resolving power and is averaged away, leaving only the coarse spatial-frequency content, and that coarse content is, by construction, the downsampled target (Human vision). The visual system's contrast sensitivity function (CSF) rolls off at high spatial frequencies, so fine tile texture becomes less visible at sufficient distance. The surviving low-frequency color field approximates the target to the extent that the selected tiles match it. The two-distances-two-images effect is therefore a designed exploitation of how the eye integrates across scale.

This is why the downsample resolution and the intended viewing distance are two ends of the same parameter. At fixed physical print size, a fine grid has smaller tiles, so their internal detail becomes unresolved at a shorter viewing distance. A coarse grid needs more distance to hide the larger tiles and represents the target more crudely. Enlarging the print changes both distances. It also explains why mean-color matching, crude as it is, suffices: the only tile property that survives to the fused percept is its average color, so matching average color is matching precisely the quantity that will matter. Everything else about the tile matters mainly at close range, where the viewer notices that it is a real photograph, and the far-distance percept discards it.