Recognizing Convex Blobs

Introduction

In designing or programming digital machines to recognize two-dimensional connected objects, one is often concerned with the geometric proper­ ties of the presented objects. Examples of such properties are convexity, elongatedness, three­

lobedness, etc.

The properties of continuous convex figures are well defined and understood 1 · But a computer "sees" these objects in the form of cellular rather than continuous images, each cell holding a number that represents the object's projection into that cell.

Hence it is important a) to define rigorously the geometric properties. of cellular blobs in terms of the continuous objects of which the cellular blobs are images, and b) to develop al­ gorithms that test cellular blobs for these properties.

In this paper we restrict our attention to two-dimensional binary objects or "blobs", i.e., black figures on a white background, and to binary cellular "images" of these objects, i.e., l's on a background of O's. A cell holding a 1 represents a nonempty projection of the object into th~ cell. Two examples of continuous binary objects are shown in Figure 1. Figure 2 shows how these objects are usually seen by a digital computer. In this figure the cellular images are arranged on a rectangular mosaic. Other mosaics, such as hexagonal or irregular mosaics, are also possible.

We describe the problem of defining and test­ ing convexity of bounded cellular blobs, and we present a solution. In presenting our solution,

by

J. Sklansky University of California Irvine, California 92664

we develop the elements of a theory of convex blobs. In the interest of brevity, the presenta­ tion of the theory is partly nonrigorous and intuitive. For rigorous proofs, see Reference 4.

Statement of the Problem

A figure is defined to be convex if it con­ tains the line segment that joins any two points of the figure. Otherwise the figure is concave.

Consider the cellular blobs illustrated in Figure 2. Intuition tells us that Blob A is a cellular image of a convex object, and that Blob B is a cellular image of a concave object. Blob A, considered as a continuous figure, is clearly concave, as shown by the dotted line. 'Hence we need to find a reasonable, intuitively satisfying definition of "convex cellular blob." The proper­ ties we believe such a definition must have are discussed in the next two paragraphs.

We think of "convexity" as a form of "smooth­ ness." I.e., the more convex an object is, the smoother it is. When we ask whether a cellular image J is convex or concave, we are therefore ask­ ing whether the smoothest object q, such that I(q) = J, is convex or concave, where I(q)~ cellu­ lar image of q. Thus if we can find~ plane figure, say r, such that I(r) · J and such that r is convex, then all objects smoother than r, say qi' such that I(qi) J, will also be convex.

This leads us to the following preliminary definition of cellular convexity: A cellular blob is convex if and only if there exists at least one convex figure r of which the given cellular blob is an image.

Searching for such an r is not a practical test for convexity, however, because even after an indefinitely long unsuccessful search such an r may still exist. What we need is an algorithm for constructing an object p, such that I(p) = J, and such that if p is concave then every other object whose image is J will necessarily be concave, too. We show in Theorems 1 to 3 that the "minimum­ perimeter polygon" answers this need.

Unger's algorithms for detecting "vertical con­ cavity" and "horizontal concavity" are the closest known earlier approaches to the detection of convex cellular blobs 3 · It is easy, however, to draw a concave blob that is vertically convex and hori­ zontally convex. Such a blob is shown in Fig. 3.

The dotted line shows that this blob is concave.

Elementary Concepts of Plane Figures

A simple curve is defined intuitively as the curve obtained from the continuous motion of a point on a plane, such that the path of the point never crosses or becomes tangent to itself, except possibly when the path reenters itself. A simple closed curve is a simple curve which reenters it­ self. A simple curve may be bounded or unbounded at either of its "ends." (For rigorous defini­ tions of these entities, see Alexandrov 1 .) If the distance of precisely one of a simple curve's ends from the plane's origin is infinite, the curve is singly unbounded; if both of a simple curve's ends are infinitely distant from the origin, the curve is doubly unbounded.

A plane figure, or simply a figure, is defin­ ed here as a set of points f having the following properties.

1. f lies in a plane
2. f ~ ¢, where ¢ is the empty set
3. f contains a simple curve c which is either closed or doubly unbounded
4. f contains the interior of c
5. f contains no point of the exterior of c

Curve c is the boundary of f.

We usually represent a figure by a lower case character, such as p, q, r.

A figure is bounded if it lies entirely with­ in some circle of finite diameter. Thus quadri­ laterals and ellipses are bounded figures. A blob is any bounded figure. Note that if a figure is bounded, its boundary must be closed.

A set of points s is connected if it is non­ empty and if every pair of points in s is contain­ ed in a simple curve belonging entirely to s. A set of points is simply connected if it is connect­ ed and if there exists no figure f whose boundary lies ins, but some point in f does not lie ins. Note that every figure, as we have defined it, is simply connected.

A polygon is a figure whose boundary contains only straight line segments. Thus, in this paper, a rectangle is a polygon, but a quadrilaterial with a pair of intersecting opposite sides is not.

The vertex angle of a polygon is the interior angle between two adjacent edges of the polygon. Note that a vertex angle lies in one of the open intervals (O,n), (n, 2n).

As a consequence of the definition of con­ vexity, a polygon is convex if and only if each of its vertex angles is less than n radians. Hence every triangle is convex. The above obser­ vations lead to the following definitions. A vertex of a polygon is a convex vertex if its ver­ tex angle is less than n radians; it is a concave vertex if its vertex angle exceeds n radians.

Elements of the Theory of Cellular Blobs

A cellular mosaic* is a set of bounded convex figures {ci}' called cells, such that Ci n c· = either ¢ or part of the boundary of c. for all i, j, and such that the union of all the~cells covers the entire plane.

A cellular mosaic is illustrated in Figure 4. An array of cells which is somewhat like a cellu­ lar mosaic, but which violates the convexity re­ quirement, is shown in Figure 5.

Let p, q denote cells in a cellular mosaic. q is a neighbor of p if p n q is a curve of non­ zero length. It can be shown that this curve must be a straight line segment. Hence every cell of a cellular mosaic is a convex polygon.

A cellular map is a nonempty subset of cells of a cellular mosaic. A cellular map may consist of just one cell. Note that a cellular map need not be connected, bounded or convex.

A chain is a sequence of cells each of which is a neighbor of its predecessor, its successor, or both. A cellular map J is chained if it is non­ empty, and if for every pair of cells (a,b) in J there exists a chain belonging entirely to J and containing cells a and b. Note that if the boun­ dary of the union of the elements of a cellular map J is a simple closed curve, then J is chained.

A cellular map J is the cellular image, or briefly the image, of a figure p if and only if a) the union of the members of J contains p, and b) every member of J containing an exterior point of p also contains a boundary point of p. We use the notation I(p) to denote the cellular image of p.

The degree of a polygon is the number of sides it has. A minimum-degree polygon of a cellu­ lar image J is any polygon p such that I(p) = J, and such that there exists no polygon q whose degree is less than that of p and such that I(q)=J.

A minimum perimeter polygon of J is any poly­ on p such that I(p) = J, and such that there exists no polygon q whose perimeter is less than that of p and such that I(q) = J.

The cellular exterior of a cellular figur~ J is the set consisting of all cells not in J. J denotes the cell exterior of J.

QJ~ boundary of the union of all cells of J. Clearly £3 is the boundary of a polygon, since every cell of J is a polygon. At each vertex of QJ draw a circle of radius £, with £ sufficiently small so that the circle intersects only the sides forming the vertex. Replace every corner of QJ

*A cellular mosaic is similar, but not identical to, a "topological complex." 1

by the portion of the corresponding circle in the interior of QJ. This replacement results in a new closed figure Q£J in which every vertex of QJ is replaced by a circular corner.

!::. !::. ~J = t!5 [I(Q£J)) = cellular boundary of J.

Note that ~J = ~J

Let ~J denote the cell exterior of BJ. The cellu­ lar interior of J, denoted by QJ (G for "_g_uts"), consists of all cells in J that are not in ~J. Thus QJ ~ J n BBJ.

A cellular map is strongly chained if its cellular interior is chained. A cellular blob is a bounded strongly chained cellular map.

Theorem 1.

A cellular blob has precisely one minimum­ perimeter polygon.

Sketch of proof:

Suppose PI and pz are minimum-perimeter poly­ gons of a cellular blob J, and suppose Pl ~ P2· Let s denote those portions of Pl not in the interior of pz, and let t denote those portions of P2 not in the interior of Pl· Let p ~ s n t. Note that the boundary of p, namely Qp, must lie wholly in ~J.

At least one vertex V of p is convex with respect top and is a vertex of Pl or P2· Suppose Vis a vertex of Pl· (If it is a vertex of pz, interchange the subscripts of Pl and pz.) Con­ struct a straight line segment AB joining the sides of p that have V in common, close enough to V so that AB lies wholly in p. Let q denote the polygon formed by AB and the complement of AVB with respect to Qp 1 · Since Qq lies in p, Qq lies in ~J. Hence I(q) = J. But the perimeter of q is clearly shorter than that of Pl· contradicting the hypothesis that Pl is a minimum-perimeter polygon of J.

Q.E.D.

We now arrive at the main theorem of this paper, for which we give a plausibility argument.

Theorem 2.

If the minimum-perimeter polygon q of a cellular blob I(q) is concave, and if p is any bounded figure such that I(p) = I(q), then pis concave.

Plausibility argument:

The unshaded portion of Figure 5 represents the cell boundary ~I(p) of the cellular image of p. Since q is concave, there must exist at least one concave vertex touching the boundary of I(p). Since q is the minimal permeter polygon of I(p), the two vertices of q adjacent to V lie on the boundary of QI(p) as shown in Figure 5 by vertices A, B. The dashed lines AV, VB denote two segments of the boundary of q.

Since the cellular images of p and q are identical, p must lie inside ~I(q). Note that both AV, VB obstruct passage through ~I(p). Hence p must intersect both AV and VB. In Figure 6, p is indicated by dash-dotted lines, and the intersections of p with AV, VB are indicated by R, S. Clearly lineRS must lie outside I(q), as does every line joining the edges of vertex V. Hence line RS lies outside p. Hence p is concave, and the theorem is demonstrated.

Basing our argument partly on the above theorem, we can show that if a) p is a minimum­ degree or minimum-perimeter polygon of J, b) q is a minimum-degree or minimum-perimeter polygon of J, and c) J is strongly chained, then p and q are either both concave or both convex.

Convex Cellular Blobs

As a result of the above theory, we may speak of any bounded strongly chained cellular map as "convex" or "concave." Hence we construct the following definitions.

A cellular blob J is concave if and only if J has a concave minimum-perimeter polygon. If J has no such polygon, J is convex. Thi.s leads us to the following revised definition of cellular convexity.

A cellular blob is convex if and only if its minimum-perimeter polygon is convex.

Theorems 1 and 2 and the above definition suggest the following approach to the automatic recognition of convex cellular blobs. Let a "spider" spin a taut elastic thread around QI(p). As the spider moves along, the thread provides an estimate of a portion of the minimum-perimeter path around QI(p). If during the spinning process, the thread is forced to touch QI(p) and thereby generate a concave vertex in the stretched thread, the image is proved concave, provided the initial point of the thread lies on QQI(p). If the thread does not touch QI(p) after a stable path of the thread is established, the blob is proved convex.

The following theorem is an interesting consequence of our definition of convex cellular maps.

Theorem 3.

If a bounded figure p is convex and has a strongly chained cellular image I(p), then I(p) is convex.

Proof:

Suppose p is convex and I(p) is concave. Let q be the minimum-perimeter polygon of I(p). Since I(p) is concave, so is q. But since I(p) = I(q) it is impossible that p is convex and q is concave, by Theorem 2. Hence, if p is convex, I(p) must be convex. Thus the theorem is proved.

It follows that if a convex figure p is con­ vex, its image I(p) remains convex under all ro­ tations and translations of p, provided I(p) is strongly chained. Thus if a cellular blob I(p) is convex and p is a minimum-degree or minimum­ perimeter polygon of I(p), it follows that a) pis convex, and b) any strongly chained image of a rotation or translation of p is also convex.

Concluding Remarks

The relationships among convex figures, con­ cave figures, the cellular images of these figures, and the minimum-degree and minimum-perimeter poly­ gons of cellular blobs are described by the table in Figure 7. In this figure the set of cellular images of any entry in the table is the same as the set of cellular images of any entry directly above or below the first entry. For example the set of cellular images of all concave minimum­ degree polygons is the same as that of all concave minimum-perimeter polygons. On the other hand, Figure 7 indicates that the set of cellular images of all convex figures is a proper subset of the set of cellular images of all concave figures.

An algorithm for finding the minimum-peri­ meter polygon of any cellular blob in a rectan­ gular cellular mosaic has been written and success­ fully executed on a large variety of blobs. This algorithm will be described and discussed else­ where.

Acknowledgments

This research was partly supported by the National Science Foundation under Grant No. GK-4226.

The author is indebted to Bruce Hanson for his help in developing Theorem 2 and for dis­ cussions of the basic concepts of cellular blobs.