In this paper we have developed a family of shape measures. All the measures from the family evaluate the degree to which a shape looks like a predefined convex polygon. A quite new approach in designing object shape based measures has been applied. In most cases such measures were defined by exploiting some shape properties. Such properties are optimized (e.g., maximized or minimized) by certain shapes and based on this, the new shape measures were defined. An illustrative example might be the shape circularity measure derived by exploiting the well-known result that the circle has the largest area among all the shapes with the same perimeter. Of course, there are many more such examples (e.g., ellipticity, linearity, elongation, and squareness measures are some of them). There are different approaches as well. In the approach applied here, no desired property is needed and no optimizing shape has to be found. We start from a desired convex polygon, and develop the related shape measure. The method also allows a tuning parameter. Thus, there is a new 2-fold family of shape measures, dependent on a predefined convex polygon, and a tuning parameter, that controls the measure's behavior. The measures obtained range over the interval (0,1] and pick the maximal possible value, equal to 1, if and only if the measured shape coincides with the selected convex polygon that was used to develop the particular measure. All the measures are invariant with respect to translations, rotations, and scaling transformations. An extension of the method leads to a family of new shape convexity measures.

A new family of shape ellipticity measures is introduced. Each measure from the family distinguishes among the ellipses with different axis length ratios. This is not case for existing ellipticity measures. The new measures are theoretically well founded, which helps us to better understand their behavior and suitability to certain applications. All measures from the family are invariant with respect to translation, rotation, and scaling transformations; range over $(0,1]$; and pick the value 1 only for the ellipses with a specific ratio between minor and major axis lengths. The measures from the new family are applied to the galaxy classification tasks. The 100% classification rate was achieved by using a $k$-NN classifier. Only six parameters (feature vector components), computed from three different ellipticity measures, were used. Based on 100 mutually independent experiments, an average classification rate of 95.6% was obtained. Previously accuracies of 92.3% and 95.1% were obtained using nearest neighbor and neural network classifiers, respectively [S. Lekshmi, K. Revathy, and S. R. Prabhakaran Nayar, Astron. Astrophys., 405 (2003), pp. 1163--1167].

This paper introduces a family of rectangularity measures. The measures depend on two parameters which enable their flexibility, i.e. the possibility to adapt with respect to a concrete application. Several rectangularity measures exist in the literature, and they are designed to evaluate numerically how much the shape considered differs from a perfect rectangle. None of these measures distinguishes rectangles whose edge ratios differ, i.e. they assume that all rectangles (including squares) have the same shape. Such property can be a disadvantage in applications. In this paper, we consider differently elongated rectangles to have different shapes, and propose a family of new rectangularity measures which assigns different values to rectangles whose edge ratios differ. The new rectangularity measures are invariant with respect to translation, rotation and scaling transformations. They range over the interval ]0, 1] and attain the value 1 only for perfect rectangles with a desired edge ratio.

The number of two-dimensional threshold functions was considered recently in [SIAM J. Discrete Math., 24 (2010), pp. 1617–1631]. By this note we point out that some of the results presented are easy consequences of already known results.

A digital disc is the set of all integer points inside some given disc. Let {\cal D}_{N} be the number of different digital discs consisting of N points (different up to translation). The upper bound D(N) = O(N(2)) 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 [formula: see text] has upper and lower bounds which are of polynomial growth in N.

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.

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).

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.

In this paper, we deal with encoding and enumerating threshold functions defined on n-dimensional binary inputs. The paper specifies situations in which the unique characterization of functions from a given class is preserved by usage of an appropriate set of discrete moments. Moreover, sometimes such a characterization (coding) is optimal with respect to the number of necessary bit rate per coded function. By estimating the number of possible values of the discrete moments used, several upper bounds (for different classes of threshold functions) are derived, some of which are better than those previously known.

The paper introduces a shape measure intended to describe the extent to which a closed polygon is rectilinear. Other than somewhat obvious measures of rectilinearity (e.g., the sum of the differences of each corner's angle from multiples of 90/spl deg/), there has been little work in deriving a measure that is straightforward to compute, is invariant under scale, rotation, and translation, and corresponds with the intuitive notion of rectilinear shapes. There are applications in a number of different areas of computer vision and photogrammetry. Rectilinear structures often correspond to human-made objects and are therefore justified as attentional cues for further processing. For instance, in aerial image processing and reconstruction, where building footprints are often rectilinear on the local ground plane, building structures, once recognized as rectilinear, can be matched to corresponding shapes in other views for stereo reconstruction. Perceptual grouping algorithms may seek to complete shapes based on the assumption that the object in question is rectilinear. Using the proposed measure, such systems can verity this assumption.

We introduce the concept of multilinear partition of a point set V/spl sub/R/sup n/ and the concept of multilinear separability of a function f:Vtwo head right arrowK={0,...,k-1}. Based on well-known relationships between linear partitions and minimal pairs, we derive formulae for the number of multilinear partitions of a point set in general position and of the set K(2). The (n,k,s)-perceptrons partition the input space V into s+1 regions with s parallel hyperplanes. We obtain results on the capacity of a single (n,k,s)-perceptron, respectively, for V subset R(n) in general position and for V=K(2). Finally, we describe a fast polynomial-time algorithm for counting the multilinear partitions of K(2).

Convexity estimators are commonly used in the analysis of shape. In this paper we define and evaluate a new easily computable measure of convexity for polygons. Let P be an arbitrary polygon. If 7 ) (P, c) denotes the perimeter in the sense of l metrics of the polygon obtained by the rotation of P by angle c with the origin as the center of the applied rotation, and if 7)2 (R(P, c)) is the Euclidean perimeter of the minimal rectangle R(P, c) having the edges parallel to coordinate axes which includes such a rotated polygon P, then we show that C(P) defined as C(P) = min 7)2(R(P,c)) a C[0,2rr] 7)1 (P, c) can be used as an estimate for the convexity of P. Several desirable properties of C (P) are proved, as well.

In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of the proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with /spl les/53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with <48 percent for /spl les/3, /spl les/40 percent for d/spl ges/10, and /spl les/20 percent for d/spl ges/25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings.

We consider estimates of worst-case bounds for quantization errors in calculating moments of arbitrary order. New estimates are provided which are based on Huxley's theorem and a general definition of families of sets, propagating an estimate for zero-order moments towards estimates for moments of arbitrary order.

In this paper, our studies are focused on ellipses and problems related to their representation and reconstruction from the data resulting from their digitization. The main result of the paper is that a finite number of discrete moments, corresponded to digital ellipses, is in one-to-one correspondence with digital ellipses, which enables coding of digital ellipses with an asymptotically optimal amount of memory. In addition, the problem of reconstruction, based on the same parameters, is considered. Since the digitization of real shapes causes an inherent loss of information about the original objects, the precision of the original shape estimation from the corresponding digital data is limited. We derive a sharp upper bound for the errors in reconstruction of the center position and half-axes of the ellipse, in function of the applied picture resolution (i.e., the number of pixels per unit). An extension of these results to the 3D case is also given.

Binary images of objects are digitized by coloring a pixel cell black if more than half of its area is within the interior of the object. For simplicity, the digitization is often modified by looking only at the center point of a cell to determine its pixel value. The digitized boundary curve consists of a sequence of 4-directional links, sometimes called a "crack" code since it follows the cracks or edges of the pixel cells. Of interest here is the entropy of digitized binary objects or planar curves on an m/spl times/m integer grid. Let D(m) denote the number of digital convex polygons which can be inscribed into an integer grid of size m/spl times/m. The asymptotic estimation of log D(m) is of interest in determining the entropy of digitized convex shapes. It is shown that log D(m) is of the order m/sup 2/3/.>