Image Compression: Modeling (cont.)

So far, our output has been as expected. Ariadne's models, however, are quite coarse and it is often useful to investigate a match further using AVE's query facilities. In this case, because we know that the resulting compressed image was too small, we are suspicious that erroneous, extra MERGE events are occurring. To check this, we want to determine the number of elements executing MERGE events in each COMPRESSLEVEL. So, we define an additional attribute, MERGELTS, for MERGE nodes and display the number of merges at each compress level.
with BIC foreach Merge compute MergeElts = Elemid(U_PCXX_user_event3);
with BIC foreach NoMerge compute NoMergeElts = Elemid(U_PCXX_user_event2);
with BIC foreach CompressLevel compute MergeSet = MergeElts(Merge);
with BIC foreach CompressLevel compute NoMergeSet = NoMergeElts(NoMerge);
with BIC foreach CompressLevel compute NumMerges = sizeof(MergeSet(CompressLevel));
with BIC show NumMerges(CompressLevel) wrt CompressLevel;

These plots are not as expected. At each level in the bintree, only those nodes that were successfully merged at the previous level are available for merger; thus, the number of successful merges at any level should be no more than half the number from the previous step. We see a problem. 32 events were compressed at the third level but this is more than half of the 63 that had been compressed at the second level. There were too many MERGEs on the third level. We next investigate the possibility that some of the mergers were invalid because one of the siblings represented a subtree where compression had already failed at a lower level. This would result in a NOMERGE event being followed by a subsequent MERGE event on the same element. To check this, we first compute

  
with BIC foreach CompressLevel compute MergeFlag = disjoint(MergeSet(CompressLevel), NoMergeSet(left(CompressLevel)));
with BIC show MergeFlag(CompressLevel) wrt CompressLevel;
where LEFT refers to the immediately preceding COMPRESSLEVEL event (that is, its left sibling in the match tree). This query produces output showing that the sets on the third level were not disjoint, as they should have been. (We know this because the output value for the third level was ``0'', indicating that the DISJOINT predicate was false.) Thus some element on level three did a compression on a subtree that had not been compressed at level two.

[Next]