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

Culik, Karel II; Friš, Ivan

Discrete Appl. Math. 58, No. 3, 223-237 (1995).

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.

MSC:

68U10	Computing methodologies for image processing
68Q45	Formal languages and automata

Keywords:

weighted finite automata; weighted finite transducers; WFT transformations

References:

[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., ()