Weighted Finite Automata

Weighted Finite Automata
The method discussed here starts with a bi-level (monochromatic) image and creates a finite-state automaton that completely describes the image. The automaton is then written on the compressed stream and it becomes the compressed image. The method is lossless the method is based on two principles:
1. Any quadrant, subquadrant, and pixel in the image can be represented by a string of the digits 0, 1, 2, and 3.
2. Images used in practice have a certain amount of self similarity, i.e., it is possible many times to find part of the image that looks the same as another part or is at least very similar to it. Sometimes part of an image has to be rotated, or reflected.
it is easy to see how an image can be represented by a finite-state automation. This is based on three rules:
1. Each state of the automaton represents part of the image. State 0 is the entire image; other states represent quadrants or subquadrants of various sizes.
2. Given a state i that represents part of the image, it is divided into four quadrants. If, e.g., quadrants 2 of i is identical to the image part represented by state j, then an arc is drawn from state i to state j, and is labeled 2 (the label is the "weight" of the arc, hence tha name "weighted finite automata" or WFA).
3. There is no need to worry about parts that are totally white. If quadrant leaf state i , e.g., is completely white, there is no need to find an identical state and to have an arc with weight 1 coming out of i . When the automaton is used to reconstruct the image (i.e., when the compressed stream is decoded) any missing arcs are assumed to point to white subquadrants of the image.