FINITE-STATE TRANSFORMATION OF IMAGES

Weighted finite automata (WFA) have been introduced as devices for com puting real functions on [0,1](n). The main motivation has been to gen erate functions on [0,1] x [0,1] interpreted as gray-tone images. Weig hted finite transducers (WFT) are finite state devices that serve as a powerful tool for describing and implementing a large variety of imag e transformations and more generally linear operators on real function s. Here we show new results on WFT and demonstrate that WFT are indeed an excellent tool for image manipulation and more generally for funct ion transformation. We note that every WFA transformation is a linear operator and show that most of the interesting linear operators on rea l functions (on [0,1](2)) can be easily implemented by WFT. We give a number of examples that include affine transformations, a low-pass fil ter, wavelet transform, (partial) derivatives, simple and multiple int egrals. Since the family of WFA-functions is constructively closed und er WFT, each of our examples is actually a proof of a theorem stating that for each WFA A there effectively exists another WFA B that comput es the integral (or other transformations) of the function defined by A.