Floyd-Steinberg algorithm

Figure 2 The nested loop program in pseudo-MATLAB code for the Floyd-Steinberg algorithm.

Figure 5 The node domain of the Floyd-Steinberg algorithm, for N =...

We now consider a structure node in which the set of nodes is partitioned in a number of subsets. Nodes in a subset have identical behavior. These subsets are called node domains. Let D be a domain and iV be a type of node. Then a node domain V)vd is characterized by the pair (iV, D) and consists of an indexed set of nodes Vnd = i I D. The node domain of the Floyd-Steinberg algorithm is given in figure 5. The boundary planes of the domain are derived from the upper and lower bound expressions of the FOR-loop statements of its nested loop program. 

Figure 7 The port domedns found by PIP for the eirgument-result padr of variable ec of the Floyd-Steinberg algorithm. It has found one dependence relation. Its function is constant and given by F c = (—1,0), its destination domain is A, and its origin domain is C. B is an input port domain and D is an output port domain.

Figure 9 Transformed dependence graph of the Floyd-Steinberg algorithm, given that X = [3,4] and P = [0,1]. ...

The first step in the extraction process is to parse the MATLAB code and to convert it into a number of node domains. We create a node domain for every function-call statement separately. Its domain, the context of the function call, is derived from the expressions of the active loop and conditional statements. The index vector of a node domain is formed by the iterators of the active FOR-statements. For example, Floyd-Steinberg has one node domain, whereas the QR algorithm has two node domains. 

---