Weighted finite transducers in image processing. (English) Zbl 0818.68145

Summary: Culik and Karhumäki studied weighted finite automata (WFA) as devices computing real functions. The main motivation was to give specifications of graytone images as local grayness functions. Culik and Kari gave an algorithm for automatic image encoding using WFA as a basis for a practical image data compression method. In this paper we introduce \(k\)- tape weighted finite automata. We are mainly interested in the case of 2 tapes called weighted finite transducers (WFT). We show that the most commonly used image transformations can be defined by WFTs. We also show that WFT transformations are closed under union and composition and that the family of WFA images is closed under WFT transformations.


68U10 Computing methodologies for image processing
68Q45 Formal languages and automata
Full Text: DOI


[1] Barnsley, M.F., Fractal everywhere, (1988), Academic Press New York
[2] Culik, K.; Dube, S., Rational and affine expressions for image description, Discrete appl. math., 41, 85-120, (1993) · Zbl 0784.68058
[3] Culik, K.; Kari, J., Image compression using weighted finite automata, Comput. graphics, 17, 303-313, (1993)
[4] K. Culik II and J. Karhumäki, Finite automata computing real functions, SIAM J. Comput. to appear · Zbl 0820.68061
[5] Eilenberg, S., ()
[6] Salomaa, A.; Soittola, M., ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.