Shape context

Calculates the shape context descriptor for a set of points that describe the shape of an object. The shape context descriptor is given a large set of points that describes the shape and a (usually) smaller set of key points at which the feature vectors (descriptors) will be calculated.

The feature vector collects the locations of the other points of the object as seen from a key point into a two-dimensional polar histogram. At each key point, the direction and distance of every point in points is calculated. A two-dimensional histogram bin index is found by quantizing direction and distance to a predefined number of discrete levels.

Usually, the input for this tool is generated using boundary detection. The shape context descriptor can however be extracted from any arbitrary set of points. If rotational invariance is needed, local shape orientation must be provided.

The descriptor can be made invariant against scaling and rotation. An invariant descriptor is necessarily less descriptive and slightly slower to calculate. Thus, if it is known that the orientation or size of the target objects doesn’t change, best performance is obtained by not enabling the invariance options.

This tool rarely needs to be used explicitly. Boundary shape detection provides a more user-friendly interface.

Inputs

• points: A set of points that form the boundaries of an object in an image. Each row in the matrix contains the (x, y) world coordinates of a point.

• keyPoints: A selected set of points at which the local shape descriptors are collected. The key points are usually a subset of points, but need not be. If key points are not provided, points will be used as key points.

• orientations: Local shape orientation for each key point in radians. If this input is connected, the resulting key point descriptors will be normalized along the provided orientations. This input must be a 1-by-N matrix, where N is the number of rows in keyPoints (if connected) or points. If this parameter is connected, the resulting descriptors will be rotationally invariant.

• scaleInvariant: Enables and disables scale invariance. If scale invariance is enabled, distances are normalized by dividing them by the (approximate) mean distance between point pairs.

• angleBins: The number of quantization bins for angle in the polar histogram. The width of each sector will be 360° / angleBins.

• distanceBins: The number of quantization bins for distance in the polar coordinate system. The size of each distance bin will grow exponentially based on firstAbsoluteDistance and distanceScale. The total length of each key point descriptor will be angleBins × distanceBins.

• firstAbsoluteDistance: Absolute size of the first quantization bin for distance. Distance is quantized to exponentially growing bins. Everything closer than firstAbsoluteDistance will be put into the first distance bin. The distance is expressed as an absolute measurement in world coordinates and it will be used if the scaleInvariant flag is false. Note that setting firstAbsoluteDistance to zero produces an empty descriptor.

• firstRelativeDistance: Relative size of the first quantization bin for distance. This parameter has the same effect as firstAbsoluteDistance, but it is relative to the mean distance between points in a shape. For example, 0.1 means that the first distance bin will cover 10% of the mean distance. This parameter will be used if scaleInvariant is true. If this value is set to zero, the tool automatically picks a value that scales the distance bins so that the last one just reaches the mean distance between point pairs.

• distanceScale: A scaling factor for the exponentially growing distance bins. If the first distance (either firstAbsoluteDistance or firstRelativeDistance depending on scaleInvariant) is denoted by f, the first distance bin will be from zero to f. The second one will be from f to f × distanceScale and so on. The last bin will be from \(f × distanceScale^{distanceBins - 2}\) to \(f × distanceScale^{distanceBins - 1}\).

• globalDescriptor: A flag that controls how to treat points whose distance to the key point is greater than the reach of the last distance bin (distance is greater than \(f × distanceScale^{distanceBins - 1})\). If this flag is true, all these points will be collected to the last distance bin. If the value is false, they will be discarded. This makes it possible to switch between a local and global descriptor. A global descriptor may provide more accuracy if it is known that there are no occlusions or overlapping objects. Otherwise, a local descriptor is better as it is more likely to collect points from a single object.

• maxSamplesPerKeyPoint: The maximum number of samples on the contour to collect for each key point. This parameter poses a hard upper limit for the processing time for the algorithm. If every point on a contour was considered, a total number of points.rows * keyPoints.rows point pairs would need to be evaluated. This would make processing of long contours really heavy. This parameter sets an upper limit to the number of evaluations, after which the contour will be uniformly subsampled to reduce the computational burden. Even if*maxSamplesPerKeyPoint* is set to a small value, the algorithm will take at least angleBins* × *distanceBins* samples for each key point. Setting *maxSamplesPerKeyPoint to zero removes the upper bound.

Outputs

• features: A polar histogram of point locations for each key point. The number of rows in the feature matrix is the same as that of the keyPoints input. Each row contains a two-dimensional polar histogram that is folded into a one-dimensional vector with angleBins × distanceBins entries. The sum of each histogram is normalized to one.