Convex digital solids

A definition of convexity of digital solids is introduced. Then it is proved that a digital solid is convex if and only if it has the chordal triangle property. Other geometric properties which characterize convex digital regions are shown to be only necessary, but not sufficient, conditions for a digital solid to be convex. An efficient algorithm that determines whether or not a digital solid is convex is presented.     

Digital and cellular convexity

We introduce a new definition of cellular convexity on square mosaics. We also define digital convexity for 4-connected sets of points on a square lattice. Using these definitions we show that a cellular complex is cellularly convex if and only if the digital region determined by the complex is digitally convex. We also show that a digital region is digitally convex if and only if the minimum-perimeter polygon (MPP) enclosing the digital region contains only the digital region. This result is related to a property of the MPP of the half-cell expansion of the complex determined by the digital region.     

On the cellular convexity of complexes

In this paper we discuss cellular convexity of complexes. A new definition of cellular convexity is given in terms of a geometric property. Then it is proven that a regular complex is celiularly convex if and only if there is a convex plane figure of which it is the cellular image. Hence, the definition of cellular convexity by Sklansky [7] is equivalent to the new definition for the case of regular complexes. The definition of Minsky and Papert [4] is shown to be equivalent to our definition. Therefore, aU definitions are virtually equivalent. It is shown that a regular complex is cellularly convex if and only if its minimum-perimeter polygon does not meet the boundary of the complex. A 0(n) time algorithm is presented to determine the cellular convexity of a complex when it resides in n × m cells and is represented by the run length code.     

Digital convexity, straightness, and convex polygons

New schemes for digitizing regions and arcs are introduced. It is then shown that under these schemes, Sklansky's definition of digital convexity is equivalent to other definitions. Digital convex polygons of n vertices are defined and characterized in terms of geometric properties of digital line segments. Also, a linear time algorithm is presented that, given a digital convex region, determines the smallest integer n such that the region is a digital convex n-gon.     

Inclusion Isotonicity of Convex–Concave Extensions for Polynomials Based on Bernstein Expansion

In this paper the expansion of a polynomial into Bernstein polynomials over an interval I is considered. The convex hull of the control points associated with the coefficients of this expansion encloses the graph of the polynomial over I. By a simple proof it is shown that this convex hull is inclusion isotonic, i.e. if one shrinks I then the convex hull of the control points on the smaller interval is contained in the convex hull of the control points on I. From this property it follows that the so-called Bernstein form is inclusion isotone, which was shown by a longish proof in 1995 in this journal by Hong and Stahl. Inclusion isotonicity also holds for multivariate polynomials on boxes. Examples are presented which document that two simpler enclosures based on only a few control points are in general not inclusion isotonic. Received September 12, 2002; revised February 5, 2003 Published online: April 7, 2003     

Three-dimensional digital line segments

Digital arcs in 3-D digital pictures are defined. The digital image of an arc is also defined. A digital arc is defined to be a digital line segment if it is the digital image of a line segment. It is shown that a digital line segment may be characterized by the chord property holding for its projections onto the coordinate planes. It is also shown that a digital line segment may not be characterized by its own chord property. A linear time algorithm is presented that determines whether or not a digital arc is a digital line segment.     

Three-dimensional digital planes

Definitions of 3-D digital surface and plane are introduced. Many geometric properties of these objects are examined. In particular, it is shown that digital convexity is neither a necessary nor a sufficient condition for a digital surface element to be a convex digital plane element, but it is both necessary and sufficient for a digital surface to be a digital plane. Also algorithms are presented to determine whether or not a finite set of digital points is a (convex) digital plane element.     

Feedback control for linear time-invariant systems with state andcontrol bounds in the presence of disturbances

The problem of the stabilizing linear control synthesis in the presence of state and input bounds for systems with additive unknown disturbances is considered. The only information required about the disturbances is a finite convex polyhedral bound. Discrete- and continuous-time systems are considered. The property of positive D -invariance of a region is introduced, and it is proved that a solution of the problem is achieved by the selection of a polyhedral set S and the computation of a feedback matrix K such that S is positively D-invariant for the closed-loop system. It is shown that if polyhedral sets are considered, the solution involves simple linear programming algorithms. However, the procedure suggested requires a great amount of computational work offline if the state-space dimension is large, because the feedback matrix K is obtained as a solution of a large set of linear inequalities. All of the vertices of S are required     

ON THE COMPUTATION OF THE DIGITAL CONVEX HULL AND CIRCULAR HULL OF A DIGITAL REGION

The problems of defining convexity and circularity of a digital region are considered. A new definition of digital convexity, called DL- (digital line) convexity, is proposed. A region is DL-convex if, for any two pixels belonging to it, there exists a digital straight line between them all of whose pixels belong to the region. DL-convexity is shown to be stronger that two other definitions, T- (triangle) convexity and L- (line) convexity. A digital region is T-convex if it is DL-convex, but the converse is not generally true. This is because a DL-convex region must be connected, but T- and L-convex regions can be disconnected. An algorithm to compute the DL-convex hull of a digital region is described. A related problem, the computation of the circular hull and its application to testing the circularity of a digital region, is also considered, and an algorithm is given that is computationally cheaper than a previous algorithm for testing circularity.     

基于外沿三角形网格划分的凸壳并行化处理

实现复杂问题的并行化处理的最基本问题之一,是如何将复杂问题分割成若干个子问题.首先研究了凸壳的一些特殊几何性质,然后利用这些性质将所讨论的点集分割在一些网格中.同时论证了凸壳顶点只能位于这些网格中的外沿三角形网格中,并且在各外沿三角形网格中所求得的凸壳顶点彼此相互独立,从而为凸壳并行化处理的设计与实现带来了极大便利.     

Geometric Constructions in the Digital Plane

We adapt several important properties from affine geometry so that they become applicable in the digital plane. Each affine property is first reformulated as a property about line transversals. Known results about transversals are then used to derive Helly type theorems for the digital plane. The main characteristic of a Helly type theorem is that it expresses a relation holding for a collection of geometric objects in terms of simpler relations holding for some of the subcollections. For example, we show that in the digital plane a collection of digital lines is parallel if and only if each of its 2-membered subcollections consists of two parallel digital lines. The derived Helly type theorems lead to many applications in digital image processing. For example, they provide an appropriate setting for verifying whether lines detected in a digital image satisfy the constraints imposed by a perspective projection. The results can be extended to higher dimensions or to other geometric systems, such as projective geometry.     

A class of stability regions for which a Kharitonov-like theoremholds

Families of complex polynomials whose coefficients lie within given intervals are discussed. In particular, the problem of determining if all polynomials in a family have the property that all of their roots lie within a given region is discussed. Towards this end, a notion of a Kharitonov region is defined. Roughly speaking, a Kharitonov region is a region in the complex plane with the following property: given any suitable family of polynomials, in order to determine if all polynomials in the family have all of their roots in the region, it suffices to check only the vertex polynomials of the family. The main result is a sufficient condition for a given region to be a Kharitonov region     

The perimeter of a fuzzy set

In pattern recognition one often wants to measure the perimeters of regions in images. This is straightforward if the region is crisply defined, but if it is fuzzy, it is not obvious how its perimeter can be measured. This paper proposes a definition of perimeter for fuzzy subsets of the plane and shows that it reduces to the standard definition if the fuzzy subset is an ordinary subset. The isoperimetric inequality does not generalize to fuzzy subsets, but certain properties of the perimeters of convex sets do generalize to fuzzy perimeters of convex fuzzy subsets.     

Recursive subdivision without the convex hull property

Recursive subdivision is a standard technique in computer aided geometric design for intersecting and rendering curves and surfaces. The convergence of recursive subdivision is critical for its effective use. Bézier and B-spline curves and surfaces have recursive subdivision algorithms that are known to converge. We show more generally that if a recursive subdivision algorithm exists for a given curve or surface type, then convergence is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. Thus, convergence of recursive subdivision does not depend on the convex hull property. We also show that even in the absence of the convex hull property, it is possible to define termination tests based on the flatness of control polygons, and to construct intersection algorithms based on recursive subdivision. Examples are given of polynomial curves to which our theorems apply.     

On the flatness of digital hyperplanes

This paper investigates the properties of digital hyperplanes of arbitrary dimension. We extend previous results that have been obtained for digital straight lines and digital planes, namely, Hung's evenness, Rosenfeld's chord, and Kim's chordal triangle property. To characterize digital hyperplanes we introduce the notion of digital flatness. We make a distinction between flatness and local flatness. The main tool we use is Helly's First Theorem, a classical result on convex sets, by means of which precise and verifiable conditions are given for the flatness of digital point sets. The main result is the proof of the equivalence of local flatness, evenness, and the chord property for certain infinite digital point sets in spaces of arbitrary dimension.     

The Digital Topology of Sets of Convex Voxels

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.     

Time optimal control of linear systems with a terminal region

In this paper we formulate a time optimal control problem for a continuous time linear system with a terminal region by the method based on functional analysis and present its solution. The solution is obtained from the results of a minimization of a convex function that is solved by a digital computer. Numerical results of an example system are shown for the two cases of amplitude constraint and energy constraint on control inputs.     

On connectivity properties of grayscale pictures

A grayscale digital picture is called “connected” if it has only one connected component of constant gray level that is maximal, i.e., not adjacent to any component of higher gray level. This note establishes some equivalent conditions for connectedness, and also defines a grayscale generalization of the genus in terms of sums of local property values.     

3次均匀B样条曲线的保形扩展

为了在不增加计算复杂度的前提下,构造既具有凸包性,又具有保形性的类3次均匀B样条曲线。首先采用逆向思维法,通过预设的曲线性质来反推调配函数的性质,进而计算出调配函数的表达式。然后采用定性分析法,分别讨论当曲线具备凸包性、保单调性、保凸性、变差缩减性时,曲线中参数的取值范围,文中图例显示了分析结果的正确性。不同情况下所得参数取值范围的交集,即为最终确定的曲线中形状参数的可行域,在可行域内改变形状参数,可以在不破坏曲线保形性的前提下调整曲线对控制多边形的逼近程度。简要讨论了与曲线对应的张量积曲面,并给出了图例。     

离散时间Hopfield网络的动力系统分析

离散时间的Hopfield网络模型是一个非线性动力系统．对网络的状态变量引入新的能量函数，利用凸函数次梯度性质可以得到网络状态能量单调减少的条件．对于神经元的连接权值且激活函数单调非减(不一定严格单调增加)的Hopfield网络，若神经元激活函数的增益大于权值矩阵的最小特征值，则全并行时渐进收敛；而当网络串行时，只要网络中每个神经元激活函数的增益与该神经元的自反馈连接权值的和大于零即可．同时，若神经元激活函数单调，网络连接权值对称，利用凸函数次梯度的性质，证明了离散时间的Hopfield网络模型全并行时收敛到周期不大于2的极限环．