https://www.softwareheritage.org/2025/06/04/history_computer_vision/ Close * Mission + Heritage + Science + Industry + Approach * Archive + Features + Browse + Save Code Now + Save Research Software o Benefits o Guidelines (HOWTO) + Save Legacy Code o SWH Acquisition Process o Software Stories + Browser extensions + Mirror Network * Community + Users + Ambassadors + Developers + Scientists + Students * Grants * Support us + Sponsors + Interest groups o ALIG members + Partners + Mirrors + Testimonials + Donate * About + FAQ + Team + Work with us + Communication kit * News + Blog + Events + Newsletter + Publications + Annual Reports * Donate * #English + #Francais + #Espanol * Home * Development * Documentation Operational * Login Software Heritage Software Heritage * Mission + Heritage + Science + Industry + Approach * Archive + Features + Browse + Save Code Now + Save Research Software o Benefits o Guidelines (HOWTO) + Save Legacy Code o SWH Acquisition Process o Software Stories + Browser extensions + Mirror Network * Community + Users + Ambassadors + Developers + Scientists + Students * Grants * Support us + Sponsors + Interest groups o ALIG members + Partners + Mirrors + Testimonials + Donate * About + FAQ + Team + Work with us + Communication kit * News + Blog + Events + Newsletter + Publications + Annual Reports * Donate * #English + #Francais + #Espanol June 4, 2025 When memory was measured in kilobytes: The art of efficient vision [Screenshot-2025-06-02-at-10] 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 Gerard Giraudon (research and principal investigator), Philippe Garnesson (a PhD student), and Patrick Cipiere (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 Scene et de Traitement d'Image Symbolique) - hinted at their serious mission. [image2]Gerard Giraudon, circa 1980 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 Gerard 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. [swhap-workshop-1024x576]Inria alumni workshop, October 2024, Inria Paris. An algorithm for outlining images The chain-linking algorithm processes a 2D pixel matrix, typically the output of a contour detection step. [image5] Raw image used as input for the algorithm. Source: Chainage efficace de contour, ndeg 605, Fevrier 1987, Gerard 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 : Chainage efficace de contour, ndeg 605, Fevrier 1987, Gerard 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 [image3] 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. [image1]Source code for memory allocation (excerpt) 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 [computer-vision] 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, "Chainage efficace de contour, ndeg 605, Fevrier 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 Chainage efficace de contour, G. Giraudon, 3eme Colloque Image-Cesta, Paris, Mai 1987 Un standard pour une representation d'objets de type liste dans le domaine du traitement d'images, ndeg 82, decembre 1988 - 3ieme edition, P. Garnesson, G. Giraudon. Un standard pour une representation d'objets de type liste dans le domaine du traitement d'images, ndeg 82, decembre 1988 - 3ieme edition, P. Garnesson, G. Giraudon. https://inria.hal.science/inria-00070061v1 << L'approximation polygonale, bilans et perspectives >>, Rapport de recherche ndeg1621 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 June 4, 2025 computer vision, computing history, Software Heritage Archive Back to top Follow us Join our newsletter [ ] [Subscribe] * About + Mission + People + Legal + Contact * Join us! + Heritage + Science + Industry + Jobs * Community + Developers + Scientists + Blog * Donate In collaboration with [UNESCO_logo_hor_blue-300x64] Search: [ ] * English * Francais (French) * Espanol (Spanish)