Scene completion with a billion photos (and then 12 million better ones)
I'm currently taking CS180 (Berkeley's computer vision class, which I'd highly recommend to anyone interested in vision). Today's lecture was all about data, and frankly it was one of the more interesting lectures I've watched. Professor Efros told a series of anecdotes about how a simple algorithm with simply a lot of data can perform really well.
He showed us the outcome of his work with James Hays on filling in images (Scene Completion Using Millions of Photographs, SIGGRAPH 2007), which was super interesting to me. He showed the comparison between a small image collection and a couple of million images, and how much nicer the fill-in was with more data. (In the paper: a first try with about 10,000 images was "very discouraging", and 2.3 million Flickr photos gave "a qualitative leap".) He also showed off his colorization work (Colorful Image Colorization, ECCV 2016).
Another anecdote: he reviewed the PlaNet paper, and when he asked the authors to constrain the images they trained on, the result was very similar to the nearest-neighbour approach (im2gps). (The published version of this comparison is Vo, Jacobs & Hays, Revisiting IM2GPS in the Deep Learning Era, ICCV 2017.)
| Im2GPS test set, % within | Street (1 km) | City (25 km) | Region (200 km) | Country (750 km) | Continent (2500 km) |
|---|---|---|---|---|---|
| Im2GPS (Hays & Efros, 2015 version) | 2.5 | 21.9 | 32.1 | 35.4 | 51.9 |
| PlaNet (Weyand et al., 2016) | 8.4 | 24.5 | 37.6 | 53.6 | 71.3 |
| Classification, PlaNet-style ([L] 7011C) | 6.8 | 21.9 | 34.6 | 49.4 | 63.7 |
| Nearest-neighbour retrieval ([L] kNN, σ=4) | 12.2 | 33.3 | 44.3 | 57.4 | 71.3 |
| … same, with a 28M-image database | 14.4 | 33.3 | 47.7 | 61.6 | 73.4 |
Table 1 of Vo, Jacobs & Hays, Revisiting IM2GPS in the Deep Learning Era (ICCV 2017). The two [L] rows use the same network and training images.
On this note, I thought it would be cool to see how far we could take this. Today there's the LAION dataset with billions of images (5.85 billion image–text pairs, to be exact). After it was taken down in 2023, it was re-released as Re-LAION-5B to be safer. That's the one I used.
The plan
I wanted to extend the original paper by using efficient search to find the nearest neighbours, then blend the result in to create a "not-so-generative AI fill-in". Every pixel in the output comes from a real photo.
Here's the exact plan:
- Search a billion images in under a second. LAION publishes a prebuilt CLIP index of 966,492,509 images (Re-LAION-2B-en research-safe). I embed the photo (with the hole roughly painted over), search the index, and get back the nearest ~8,000 images in 0.45 s (median). That's on a CPU, no GPU.
- Download only those. You obviously can't download a billion images, so I fetch just the nearest few thousand from their original URLs.
- Re-rank with the original 2007 descriptor. CLIP knows the photo is "a harbour" but not where the water is. The 2007 gist descriptor (a coarse 4×4 grid of edge directions plus colour) cares about layout, so I use it to pick the 200 best scenes.
- Then exactly the 2007 pipeline: slide each candidate around the hole to find where it lines up best, use a graph cut to pick the seam where the two photos agree, and do Poisson blending to hide the colour difference. (I used Poisson instead of pyramid blending because that's what the paper uses.)
- Rank the results and show the top few. Instead of adding randomness, you can just flip through the top-k. That's what the carousels below are.
Plot twist: a billion links is not a billion photos
The search was instant. Getting the pixels was the hard part. LAION is a list of links, and many are dead, blocked, or rate-limited. Worse, a photo's nearest neighbours tend to come from the same few websites. For the harbour, 7,098 of the top 8,000 were from one site.
Across my 10 test photos I asked LAION for 80,000 images and could actually use 8,693 (11%). Some photos got thousands, but the lighthouse got 13 and the car got 2.
So I tried a second database: PD12M, 12.4 million public-domain images (mostly Wikimedia Commons, iNaturalist and museum collections). It's 80× smaller than LAION, but every image sits in one cloud storage bucket, and it ships the same CLIP embeddings, so I could search all 12.4M exactly (about 3 minutes for all 10 photos at once). Of 20,000 requested images, 14,654 (73%) were usable. Every photo got at least 1,100.
| LAION (Re-LAION-2B research-safe) | PD12M | |
|---|---|---|
| images searched | 966M | 12.4M |
| search | approximate, 0.45 s / photo | exact, ~19 s / photo |
| usable candidates per photo (median) | 313 | 1,454 |
| worst photo | 2 (car) | 1,112 (lighthouse) |
| licence | whatever the original site says | public domain / CC0 |
Results
Venice is the easy case for both. It's one of the most photographed places on earth. LAION even drops Santa Maria della Salute's dome into the gap.
Removing a mountain: the treeline just continues. In the third result, a completely different peak shows up.
My favourite failure/success: LAION filled a Prague church tower with the Leaning Tower of Pisa. Same lighting, same sky, completely wrong country.
Carousels: for each photo, flip through the top 8 completions. Each slide shows the matched photo, the seam (red), and the result.
Why the neighbours look the way they do
Here are the 24 nearest neighbours for each photo, LAION on top and PD12M below. (Grey tiles were removed by the safety filter, or the link now serves a different image.)
-
LAION finds the place, PD12M finds the stuff. For the Maine harbour, LAION returns Maine-harbour photos: boats, lighthouses, cottages, all the things people caption and post. PD12M returns marsh grass, rocks and still water, much of it nature documentation from iNaturalist and Wikimedia. To fill a hole you want the boring texture photos, not the postcard.
-
LAION is full of duplicates. For Prague, many of LAION's neighbours are the same tourist shot of the same square, reposted across sites. A billion images is a lot fewer distinct scenes than it sounds.
-
LAION is stock- and wallpaper-heavy. For the mountain lake and the tree, LAION's neighbours are saturated wallpapers, misty mood shots, heavy blur (bokeh) and edited images. They match the "vibe" but not the actual pixels. PD12M returns plain amateur lake and field photos that look like the query. Early on, those blurry web images were filling holes with mush, so I added a sharpness check (not in the original paper) that rejects them.
-
CLIP looks at the subject, not the scene. For the cow in the rice field, LAION's neighbours are mostly… other cows, even a cartoon cow. CLIP embeds what the photo is about. PD12M's neighbours are paddies and wetland plants, which is what's actually behind the cow.
-
When LAION runs dry, there's nothing to rank. For the lighthouse, almost every LAION neighbour is grey (unusable) or a blurry wallpaper, so the one completion is mush. PD12M has hundreds of plain sea-horizon shots.
Does the 2007 layout descriptor still matter?
I compared using CLIP alone against CLIP plus the 2007 gist reranking. It's mixed. Gist helps when layout matters (Venice: the canal lines up), and sometimes CLIP alone picks a nicer source (harbour). With only ~10 photos I wouldn't call a winner.
Where it fails
The car: LAION had 2 usable images, so no result. PD12M found plenty of country roads but none with road surface where the car was, so it fills the hole with grass. The method can only paste what some photo actually contains in that spot.
Cost and speed
- Search: 0.45 s over 966M images (LAION, approximate); 189 s for all 10 photos over 12.4M images (PD12M, exact).
- Per photo, the slow parts are the downloads (~45–55 s) and the original 2007 alignment step on CPU (~50–120 s). The paper reported over an hour per image on one CPU in 2007.
- Total cloud bill for the whole project, including false starts: $3.51 (one 16-core CPU machine plus storage for the index).
Credits: query photos from Wikimedia Commons (CC BY-SA 4.0; authors listed below). Completions built from them are shared under the same licence. PD12M source images are public domain/CC0. LAION source images belong to their original creators and are shown here for research commentary.
Query photos
- 2021-07-20 Maine Marine Patrol Boat at Winter Harbor ME USA by Gordon Leggett, CC BY-SA 4.0
- 20190816 Rynek Staromiejski w Pradze 1143 5231 by Jakub Hałun, CC BY-SA 4.0
- Mount Shasta, Lake Siskiyou, SW view by Radomianin, CC BY-SA 4.0
- 2016-11-13 01 Kjeungskjær Lighthouse, Sør-Trøndelag, Norway by Gordon Leggett, CC BY-SA 4.0
- Dülmen, Merfeld, Volvo PV 544 B18 -- 2021 -- 0075-9 by Dietmar Rabich, CC BY-SA 4.0
- Prague, Old Town Square, COVID by Tadeáš Gregor, CC BY-SA 4.0
- Four dogs running at golden hour in the countryside of Don Det Laos by Basile Morin, CC BY-SA 4.0
- Water reflection of a boy feeding hay to a cow in a paddy field at golden hour in Laos by Basile Morin, CC BY-SA 4.0
- Panorama of Canal Grande and Ponte di Rialto, Venice - September 2017 by Martin Falbisoner, CC BY-SA 4.0
- Seal Rocks, Ocean Beach, San Francisco by Radomianin, CC BY-SA 4.0
