Storing Feature Descriptions as 2-D Trees

Many methods have been proposed which produce lowlevel features from digital images, e. g., the raw primal sketch or intrinsic images. However, in some cases the features occur sparsely in the image, and a more efficient storage scheme can be used than a registered array of feature images. Edges constitute one of the most useful sorts of information for scene analysis. Even though edge responses usually occur sparsely throughout an image, the output from an edge detector in most image analysis systems is itself an image of the same dimensions (but possibly multichannel) as the original intensity image. Appreciable savings in space and time can be achieved if the full edge descriptions (orientation, radius, and likelihood information) are stored as a 2-D tree. This is a binary tree which uses the (x, y) locations of the pixels as keys and splits the data at the median along the key with greatest spread (i. e., this is a k-d tree for k = 2).