One of the problems we have encountered was converting the set of relations between closed regions to the proposed syntax for describing objects. For example, the syntax of Figure 10 is:
C(C(C(),C()),C())
and the relations generated by the image processing program are:
Relation (1): B A
Relation (2): C A
Relation (3): D B
Relation (4): D A
Relation (5): E B
Relation (6): E A
These relations can be represented by a graph as shown in
Figure 11. The
problem is to convert this graph to an equivalent tree structure, which is the most
convenient data structure to represent our syntax.
Our method is to scan the relations, count the
number of occurrences for each closed region name mentioned in the left side of the
relations giving an array RANK(), where
{A,B,C,...}, and select the
relations (
) that satisfy the following
condition:
RANK() - RANK(
) = 1
This guarantees that no redundant relations will be selected. Applying this algorithm to the relations of Figure 10 we have,
RANK(A) = 0; RANK(B) = 1; RANK(C) = 1;
RANK(D) = 2; RANK(E) = 2
The selected relations will be:
B A; C
A; D
B; E
B
Now arranging these relations to construct the syntax gives:
A(B()) A(B(),C())
A(B(D()), C())
A(B(D(),E()),C())
which is the required syntax. A tree representing this syntax is easily constructed and shown in Figure 12. The next step would be to insert the open regions, if any, and this is done by traversing the tree from the maximum depth and upwards. Any open region can be tested by checking any point in it and checking whether it lies within the maximum depth leaves of the closed region's tree hierarchy. (The test is easily done by extending a line and checking how many times it intersects a closed region, as in the test for closed regions enclosures.) Then the upper levels of the hierarchy are tested in ascending order till the root is reached or all open regions have been exhausted. Any open region found to be inside a closed one while traversing the tree is inserted in the tree as a child for that closed region. It should be noticed that this algorithm is not a general graph to tree conversion algorithm; it only works on the specific kind of graphs that the image processing module recovers. That is, the conversion algorithm is tailored to the visual recursion paradigm.
