The ecological statistics of good continuation: multi-scale Markov models for contours

Background Previous models of good continuation [e.g., Williams & Jacobs 95] make the first-order Markov assumption, i.e., if we parametrize a curve by arc length t, the tangent direction of the contour at t+1 only depends on the tangent at t. The goal of this study is to use human-marked boundary contours in a large database of natural images to empirically determine the validity of this model. Methods Experiment 1: We measure the distribution of lengths of contours segmented at local curvature maxima. If the first-order Markov assumption holds, the lengths of the segments would have an exponential distribution. Experiment 2: We evaluate higher-order Markov models, in which the tangent direction of a contour at t+1 depends on the tangent at t and the tangents at the same location t of this contour at coarser scales. This is done by empirically measuring the information gain when the order of our model increases, i.e., the mutual information between the tangent at t+1 and the tangent at t at scale s conditioned on all the tangents at t at scales finer than s. Results Experiment 1: We observe a power law, instead of an exponential law, in the distribution of the contour segment length. The probability is inversely proportional to the square of segment length. The power law justifies the intuition that contours are multi-scale in nature; the first-order Markov assumption is shown to be empirically invalid. Experiment 2: The information gain shows that coarser scales contain a significant amount of information (17% of the base scale). We accordingly propose a multi-scale algorithm for contour completion, which uses higher-order Markov models. Completion is done in a coarse-to-fine manner. Conclusion Any algorithm for contour processing has to be intrinsically multi-scale. Higher-order Markov models exploit information across scales and lead to an efficient algorithm for multi-scale contour completion.