Major Implementation Details of the

Compass Operator

Mark A. Ruzon

In our explanation of the compass operator, we stated that our main data structure is a color signature, a variable-length set of color point masses. To build two color signatures, one for either side of the edge, we split our circular compass in half along a particular orientation and assign each pixel a mass based on how much of that pixel's area falls inside the circle and how far away it is from the center (assuming the pixel is entirely inside the circle, the mass is r exp{-r²}, where r is the distance from the center of the circle to the center of the pixel).

In theory, we could consider each pixel as a separate point mass. However, to make the problem computationally manageable, we perform vector quantization. We have chosen a greedy vector quantization algorithm that allows one to specify the maximum codebook size (10, in our case).

Before we can use the Earth Mover's Distance (EMD) to compute the distance between two color signatures (refer to the previous explanation for more information), we must define the distance between two colors, which means choosing a color space and a distance function. We use the CIE-Lab color space, in which small Euclidean distances are perceptually meaningful. However, beyond a threshold, the Euclidean distance is no longer meaningful; the colors are simply different. Therefore, we scale small distances (below this threshold) to lie between 0 and 1, while the distance between any two perceptually different colors is 1. Because we normalize the total mass of the smaller signature to be 1 (which happens only when we are detecting corners, otherwise they are both 1), and the maximum ground distance is 1, the maximum EMD is 1, regardless of the scale.

We do this at a fixed number of orientations; this partitions the compass into wedges for efficiencient updating. The color signature of each wedge is computed separately, and we add point masses representing the same color in two different wedges together to get the color signature for an entire semicircle. The figure to the left shows a compass with a radius of 4 pixels divided into 16 wedges.