When memory was measured in kilobytes: The art of efficient vision
By Mathilde Fichen
In the early days of computer vision, when memory was scarce and every byte counted, innovation thrived under constraint. “An Efficient Chain-Linking Algorithm,” developed at Inria in the late 1980s, is a brilliant example of this spirit. Now preserved and shared by Software Heritage, this compact yet powerful piece of C code showcases how elegance and efficiency went hand in hand in outlining the future of image processing—one pixel chain at a time.
The code resulted from research work carried out between 1985 and 1991 at Inria, by Gérard Giraudon (research and principal investigator), Philippe Garnesson (a PhD student), and Patrick Cipière (software engineer). Down in sunny Sophia Antipolis, a tech park 20 minutes inland from Antibes, the team tackled computer vision with a distinctly local flavor. They called themselves PASTIS, a playful nod to the anise drink. Still, the acronym – Scene Analysis and Symbolic Image Processing Project (Projet d’Analyse de Scène et de Traitement d’Image Symbolique) – hinted at their serious mission.
Preserving Inria legacy software
The effort to preserve this source code is part of a broader initiative to preserve the legacy codes of Inria (France’s National Institute for Research in Digital Science and Technology), launched in 2023 in a joint effort of Software Heritage, Inria Alumni, and Inria. The project to preserve Inria’s legacy software started by reaching out to the institute’s community, past and present, through a survey (as detailed in our iPres article.) This initial outreach informed a dedicated, hands-on workshop in 2024, which kicked off the practical work of exploring these historical codes. The current focus is on securely archiving the important legacy software we’ve identified within Software Heritage. Sharing the stories behind these codes with the broader community is just as vital.
The recovery of some code has been surprisingly straightforward. For instance, the code for “An Efficient Chain-Linking Algorithm” was readily accessible thanks to Gérard Giraudon’s personal preservation efforts on a local drive. That small success story is a reminder of how important individual initiative is for preserving digital work. Each piece of software recovered isn’t just code; it’s a piece of research history, carrying the stories of the people who created it.
An algorithm for outlining images
The chain-linking algorithm processes a 2D pixel matrix, typically the output of a contour detection step.
Raw image used as input for the algorithm. Source: Chaînage efficace de contour, n° 605, Février 1987, Gérard Giraudon
The output is a list of contour chains. Each chain in this list is a sequence of pixel coordinates that define a continuous boundary, ready for further steps like polygonal approximation or shape analysis..
Processed image. Source : Chaînage efficace de contour, n° 605, Février 1987, Gérard Giraudon
Basically, the chain-linking connects the edge pixels to create smooth outlines, just like tracing the shape with a pencil.
Computer vision in the 80s
The mid-1980s aspiration of seeing robots hit a speed bump: computer vision algorithms weren’t fast enough. The core challenge? Real-time performance – the essential ingredient for giving robots camera “eyes” that could truly see and react. At the time, such a system was conceived as a pipeline of operations from image acquisition (one shot or video) to a decision-making system.
The goal was to extract meaningful information from raw image data, typically represented as an 8-bit matrix of pixel intensities, and convert it into a graph in list form (i.e., from matrix to list). This process begins with detecting and recognizing shapes within the image, either in 2D or 3D, depending on the available data. From there, the system identifies objects and analyzes their spatial relationships, ultimately constructing a graph of semantic connections between them. This graph captures not just what the objects are, but how they relate to one another within the observed scene. In some cases, the analysis extends over time (3D + t), allowing for the interpretation of motion and dynamic interactions in a sequence of frames.
Solving key memory issues
The algorithm was first developed on a PerkinElmer Model 3250 computer, seen above in a brochure via 1000bit.
Another challenge in early image processing was the limited amount of short-term memory (RAM) available in computers. This made it essential to focus on reducing the amount of data stored and processed at any given time, while preserving important information.
Due to these constraints, the Efficient Chain-Linking Algorithm could only store three lines of the image at a time while reading it line by line. As each new line was read, the algorithm would build and extend chains of connected pixels on the fly, without knowing how those chains might continue in future lines. Once the entire image was scanned, a final processing stage merged pixel chains belonging to the same contour and resolved junctions or branching points. Importantly, this was done using just one full pass over the data, making it memory-efficient.
But the algorithm wasn’t the only clever bit. From a programming standpoint, the code’s true ingenuity lay in its dynamic memory allocation for storing the chain lists. Back then, predicting memory needs upfront was impossible, making Patrick Cipiere’s approach an elegant solution to an unpredictable challenge.
Computer vision today
With the dramatic advancements in computer vision, fueled by deep learning and the prevalence of large memory capacities, contemporary methods often involve storing the full image and constructing contour chains sequentially, possibly necessitating multiple passes over the data, one for each chain. Yet, even with today’s abundant memory, this algorithm retains its power: remarkable efficiency when every byte counts. By processing the image sequentially, storing only a few lines at a time, and building pixel chains incrementally without looking back, it offers a lean and effective alternative to the memory-hungry approaches now common.
Links and references
The preserved source code can be found on Software Heritage archive: https://archive.softwareheritage.org/browse/origin/directory/?origin_url=https://github.com/mathfichen/chainage_de_contour
The original 79-page paper in French, “Chaînage efficace de contour, n° 605, Février 1987, Gerard Giraudon” https://inria.hal.science/inria-00075949/document
An Efficient Chain-Linking Algorithm, G. Giraudon, in The 5th Scandinavian Conference on Image Analysis, Stockholm, June 1987.
A Real Time Parallel Edge Following in Single Pass, GG, in Workshop on Computer Vision, Miami, 1987
Chaînage efficace de contour, G. Giraudon, 3ème Colloque Image-Cesta, Paris, Mai 1987
Un standard pour une représentation d’objets de type liste dans le domaine du traitement d’images, n° 82, décembre 1988 – 3ieme édition, P. Garnesson, G. Giraudon.
Un standard pour une représentation d’objets de type liste dans le domaine du traitement d’images, n° 82, décembre 1988 – 3ieme édition, P. Garnesson, G. Giraudon.
https://inria.hal.science/inria-00070061v1
« L’approximation polygonale, bilans et perspectives », Rapport de recherche n°1621 INRIA, juin 1991 Garnesson P. and Giraudon G.
https://inria.hal.science/inria-00074940v1/document
This work has resulted in citations and a hardware implementation presented at the 16th GRETSI COLLOQUIUM — SEPTEMBER 15-19, 1997