A new convexity measure for polygons

Abstract-Convexity estimators are commonly used in the analysis of shape. In this paper, we define and evaluate a new convexity measure for planar regions bounded by polygons. The new convexity measure can be understood as a "boundary-based" measure and in accordance with this it is more sensitive to measured boundary defects than the so called "area-based" convexity measures. When compared with the convexity measure defined as the ratio between the Euclidean perimeter of the convex hull of the measured shape and the Euclidean perimeter of the measured shape then the new convexity measure also shows some advantages-particularly for shapes with holes. The new convexity measure has the following desirable properties: 1) the estimated convexity is always a number from (0, 1], 2) the estimated convexity is 1 if and only if the measured shape is convex, 3) there are shapes whose estimated convexity is arbitrarily close to 0, 4) the new convexity measure is invariant under similarity transformations, and 5) there is a simple and fast procedure for computing the new convexity measure.     

Measuring linearity of planar point sets

Our goal is to design algorithms that give a linearity measure for planar point sets. There is no explicit discussion on linearity in literature, although some existing shape measures may be adapted. We are interested in linearity measures which are invariant to rotation, scaling, and translation. These linearity measures should also be calculated very quickly and be resistant to protrusions in the data set. The measures of eccentricity and contour smoothness were adapted from literature, the other five being triangle heights, triangle perimeters, rotation correlation, average orientations, and ellipse axis ratio. The algorithms are tested on 30 sample curves and the results are compared against the linear classifications of these curves by human subjects. It is found that humans and computers typically easily identify sets of points that are clearly linear, and sets of points that are clearly not linear. They have trouble measuring sets of points which are in the gray area in-between. Although they appear to be conceptually very different approaches, we prove, theoretically and experimentally, that eccentricity and rotation correlation yield exactly the same linearity measurements. They however provide results which are furthest from human measurements. The average orientations method provides the closest results to human perception, while the other algorithms proved themselves to be very competitive.     

On the orientability of shapes.

The orientation of a shape is a useful quantity, and has been shown to affect performance of object recognition in the human visual system. Shape orientation has also been used in computer vision to provide a properly oriented frame of reference, which can aid recognition. However, for certain shapes, the standard moment-based method of orientation estimation fails. We introduce as a new shape feature shape orientability, which defines the degree to which a shape has distinct (but not necessarily unique) orientation. A new method is described for measuring shape orientability, and has several desirable properties. In particular, unlike the standard moment-based measure of elongation, it is able to differentiate between the varying levels of orientability of n-fold rotationally symmetric shapes. Moreover, the new orientability measure is simple and efficient to compute (for an n-gon we describe an O(n) algorithm).     

The number of N-point digital discs

A digital disc is the set of all integer points inside some given disc. Let D_N be the number of different digital discs consisting of N points (different up to translation). The upper bound D _N = O(N²) was shown recently; no corresponding lower bound is known. In this paper, we refine the upper bound to D_N = O(N), which seems to be the true order of magnitude, and we show that the average D_N = D₁ + D₂ ... D_N)/N has upper and lower bounds which are of polynomial growth in N     

Separating points by parallel hyperplanes--characterization problem.

This paper deals with partitions of a discrete set S of points in a d-dimensional space, by h parallel hyperplanes. Such partitions are in a direct correspondence with multilinear threshold functions which appear in the theory of neural networks and multivalued logic. The characterization (encoding) problem is studied. We show that a unique characterization (encoding) of such multilinear partitions of S = {0, 1,..., m-1}d is possible within theta(h x d2 x log m) bit rate per encoded partition. The proposed characterization (code) consists of (d + 1) x (h + 1) discrete moments having the order no bigger than 1. The obtained bit rate is evaluated depending on the mutual relations between h, d, and m. The optimality is reached in some cases.