Title: Constant-Working-Space Algorithms for Image Processing

Speaker:  Tetsuo Asano 
JAIST, Japan


Date: Wednesday, Feb 27, 2008
Time 11:00-12:00PM
Venue: Room 3464, HKUST

Abstract:
  In this talk we present a new direction of algorithms for image processing.
That is, we present algorithms which require no array of size depending on
input image but use only constant working space, while keeping the running
time. Three problems are considered. (1) Connected component labelling
in which we label each pixel with its component number, (2) image-rotation
with interpolation, and (3) image scan in an arbitrary slope. An input
image of size $O(n^2)$ is stored in a two-dimensional array, but no other
array is available for the algorithms. Our algorithms run in $O(n^2)$ time.