Applications of weighted finite automata and transducers to image processing
Peter Rajčáni · University Microfilms International eBooks · 1995
Weighted finite transducers (WFT) have been introduced by Culik and Fris as a generalization of weighted finite automata (WFA) to 2 tapes and provide a useful tool in image manipulation. WFT can perform almost any operation on images including zooming, shrinking, rotation, flipping, stretching, creating various regular patterns as well as low-pass and high-pass filtering used in image processing. We present an implementation of an efficient image manipulation system which includes efficient algorithms for an application of a WFT transformation to an image in either pixel or WFA representation and for operations defined on WFA and WFT, such as composition of WFT, concatenation of two WFA or two WFT, and Cartesian product of WFA. The system also includes a WFA minimalization algorithm which minimizes the number of states and a WFT inference algorithm which learns the WFT from a transformation performed on a test image. The program has been implemented in C using X-windows OSF/Motif graphical user interface and handles both gray-scale and color images. We show that probabilistic mutually recursive function systems (PMRFS) can be simulated by iterative weighted finite transductions. We conjecture that iterative WFT are more powerful than PMRFS and give an example of WFT that supports this conjecture. Furthermore, we show that the family of images defined by iterative WFT is closed under continuous invertible WFT relations including affine transformations as a special case. We give a necessary and sufficient condition for invertibility of $\epsilon$-free WFT relations. We show that it is decidable whether two $\epsilon$-free WFT define the same weighted relation for all finite words over a fixed alphabet. Finally, we give a sufficient condition for continuity of functions computed by WFA. Such a condition has been previously known only for a special class of WFA called level automata.