Representing space for practical reasoning

摘要

The paper describes a new approach to representing space and time for practical reasoning, based on space-filling cells. Unlike Rn, the new models can represent a bounded region of space using only a finite number of cells, so they can be manipulated directly. Unlike Zn, they have useful notions of function continuity and region ‘connectedness’. The topology of space is allowed to depend on the situation being represented, accounting for sharp changes in function values and lack of connectedness across object boundaries. Algorithms based on this model of space are neither purely region based not purely boundary based, but a blend of the two. This new style of algorithm design is illustrated by a new program for finding edges in grey-scale images. Although the program is based on a fairly conventional second directional difference operator, it can detect fine texture in the presence of camera noise, produce connected boundaries around sharp corners and return thin boundaries without ‘feathering’. New algorithms are presented for combining directional differences, suppressing the effects of camera noise, reconstructing image intensities from the second difference values and merging results from different scales (including suppression of spurious boundaries in staircase patterns).