Wednesday 12th March, 2pm-3pm
Tetsuo ASANO, Japan Advanced Institute for Science and Technology (JAIST)
Constant-Working-Space Algorithms for Image Processing
Slides: not yet available
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.