Tetsuo Asano
Japan Advanced Institute of Science and Technology

Small Work Space Algorithms for Image Processing

This invited talk surveys algorithms for image processing which use small amount of memory. There are two different types of small work space algorithms depending on whether the input image can be altered or not. If we can modify pixel values, then we can embed some information on the input image matrix to use it for other purposes. This type of algorithms are called in-place algorithms. In another type of algorithms we assume that an input image is stored in read-only memory. In other words, we can read any pixel value but cannot write or change any pixel value.

Starting with in-place algorithms, we introduce small-work-space algorithms for several important basic problems on image processing, including connected components labeling, which has been extensively studied and a number of algorithms have been proposed so far under several different computational models. A linear-time algorithm is known for the problem using linear work space. We will show it is possible to reduce the amount of work space into square root of n while increasing the running time from O(n) to O(n log n).

This is just one example. We will show other space-efficient algorithms and they are effective for applications to scanners.

Eric Andres
Professor in Computer Science
University of Poitiers, France
Head, Signal-Image-Communications Department
XLIM Institute

Digital Analytical Geometry: How do I define a digital object?

During this plenary talk, we will start by giving some foundational elements on digital geometry and its relations to continuous geometry. We will then explain how, from simple assumptions about properties a digital object should have, one can build mathematical sound digital objects and transforms. We will end with open problems and challenges for the future.