Colin Manning: Digital Video Compression

Greedy Algorithms Results

Because Greedy Algorithms had never been implemented before and because their behaviour was expected to be erratic, each of the Greedy Algorithms described on this site was implemented and tested. Greedy Algorithm parameters (such as search directions, initial step size, when and how the step size is decreased) could be combined differently to produced a large number of algorithms. Six types were tested in order to investigate the role these parameters played in a Greedy Algorithm's success. In addition, it was not known how Greedy Algorithms compared to existing Block Matching Algorithms.

This page compares the greedy algorithms to see which ones work best.

You can examine the behaviour of each of the algorithms.
Results of experiments on

This graph illustrates the relative performance of the Greedy Algorithms when coding the Football Sequence. The cluster above 2500 criteria evaluations comprises data points from Greedy Algorithms B, C and F.

Analysis of the results for the Garden sequence is not as simple however. It is tempting to examine the entire range of the data visible in the graph immediately above and describe how to achieve particular quality levels at a variety of costs. The data collected from the experiments on the Garden sequence do not form a cost-quality curve like the data collected from the Football and Tennis sequences.
Information about how to achieve lower quality images by doing more work is not very useful. No application would deliberately expend more effort to achieve worse results. Thus a small subset of the data is all that can be meaningfully considered and this is graphed below.

The graph below shows a portion of the above graph in in more detail. At this level the algorithms exhibit the familiar cost-quality curve from which some conclusions can be drawn. The success of Greedy Algorithms D and E in the midrange made Algorithm B redundant. Similarly Algorithm A had little to offer over D, E, C and F.