Weighted Finite Automata
The method discussed here starts with a bi-level (monochromatic) image and creats a finite-state automaton that completely describes the image. The automato is then written on the compressed stream and it becomes the compressed image. The method is loss-less but it is easy to add a lossy option where a user-controlled parameter indicates the amount of loss permitted. (we later show how this method can be extended to grayscale images, where it is normally used as a loosy compression method.) 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. The longer the string, the smaller the image area it represents.
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, except for size, or is at least very similar to it. Sometimes part of an image has to be rotated, reflected, or video-reserved on order
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 represents 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.
Figure shows 2*2 chessboard. This is a simple, symmetric and highly similar image, so its WFA is especially simple. The entire image becomes state 0 of the WFA. Quadrant 0 is all white, so there is no need for labeled 0 out of state 0. Quadrant 1 is black, so we add new state , state 1, that’s all black and construct are labeled 1 from 0 to 1. We denote it 0(1)1. Quadrant 2 is also black, so we construct another arc, labeled 2, from state 0 to state1. It is denoted 0(2)1. There is no need to worry about quadrant 3 since it is white.
We next move to state 1, we divide it into four quadrants and notice that everyone is identical to the entire state. We thus construct four arcs labeled 0, 1, 2 and 3 all going from state 1 to itself. The WFA is now complete since there are no more states to be considered.