el.dvi


Convexity Measure for Shapes with Partially Extracted

Boundaries

Jovǐsa Žunić,a, ∗ Paul L. Rosinb

a Department of Computer Science, University of Exeter, Exeter EX4 4QF, U.K.

e-mail: J.Zunic@ex.ac.uk

b School of Computer Science, Cardiff University, Cardiff CF24 3AA, Wales, U.K.

e-mail: Paul.Rosin@cs.cf.ac.uk

Abstract

Shape descriptors are used in many computer vision tasks. Convexity is one of

the most widely used shape descriptors in practical applications and also one of the

most studied in the literature. There are already several defined convexity measures.

The most standard one comes from the comparison between a given shape and its

convex hull, but there also other approaches. Independently of whether the convexity

descriptors are area based or boundary based, all of them assume that the shape (or

shape boundary) is completely known and that the measures apply to the complete

data. In this paper we define a convexity measure that can be applied to shapes with

partially extracted boundaries. More formally, the new convexity measure deals with

planar curves or with disconnected curves consisting of several planar curve segments.

Key words: Shape, shape descriptors, convexity, measure.

∗J. Žunić is also with the Mathematical Institute, Serbian Academy of Arts and Sciences, Belgrade.

1



1 Introduction

Shape is one of the basic terms in the area of computer vision and image processing. Usually

a shape corresponds to a compact planar region. There are many ways to characterise

shapes; one approach is to use a suitably selected set of shape descriptors. One of the

mostly employed shape descriptors is convexity. Over the years many convexity measures

have been developed (e.g. [1, 2, 3, 4, 6, 7]) and have been applied to tasks such as image

segmentation, shape decomposition, object classification, grouping, etc. Their usefulness in

such applications has led to a continual interest in shape descriptors and development of

new ones.

Typically, approaches to defining and computing global shape descriptors assume that

the complete shape (or the shape boundary) is known. However, in some image processing

tasks it is not possible to extract the complete shape boundary. For example, if there is some

overlap between objects or there is no clear difference between foreground and background

pixels (see Fig. 1). In such cases only fragments of the boundary can be extracted; neverthe-

less, it would still be worth computing shape information from the available data. Another

motivation for this work is that some (very thin) objects, because of their nature, are more

adequately represented by curve segments than by planar regions. A person’s signature is an

example. Based on the previous observation it seems reasonable to define descriptors that

correspond to a curve or a disconnected curve consisting of several curve segments.

(a) (b) M = 0.309 (c) M = 0.767 (d) M = 0.708
Figure 1: (a) Extracting the boundary of Lena’s hat is difficult due to poor contrast in places

as well as clutter. (b) After edge detection and linking, the edge segments relating to the hat

have been manually selected. (c) The outer boundary curves. (c) Gaps between the outer

boundary curves completed by straight line segments. The new convexity measure proposed

in this paper can cope with all those situations.

2



2 Convexity Measure for Curves

In this section we define a convexity measure for curves or disconnected curves consisting of

several curve segments.

Perhaps the most common definition of a convex curve is the next definition that comes

from the mathematical theory.

Definition 1 A curve γ is convex if and only if for each point A on the curve γ there is a

line l such that the curve γ completely lies in one of the halfplanes determined by the line l.

For our purpose we will use another definition that is equivalent to Definition 1.

Definition 2 A curve γ is convex if and only if for each two points A and B on the curve

γ the open line segment (AB) does not intersect the curve γ (i.e. (AB) ∩ γ = ∅) or (AB)
completely belongs to the curve γ (i.e. (AB) ⊂ γ).

Remark. In mathematical terms, the strict convexity of a given curve γ does not allow

straight line sections in γ. We will use the convexity definition as given by Definition 2 rather

then the strict convexity definition. In computer vision and image processing applications

we often use polygonal approximations, and such a weaker definition allows polygons which

are boundaries of convex polygonal regions to be understood as convex curves.

For our purpose we need a straightforward extension of Definition 2 to the curves that

are not necessarily connected. In other words, the curve γ from Definition 2 can be a

disconnected curve γ = γ1 ∪ . . . ∪ γn consisting of n curve segments γ1, . . . , γn.
Now, based on Definition 2, we define a new convexity measure for curves and for dis-

connected curves consisting of several curve segments.

Definition 3 Let γ = γ1 ∪ . . . ∪ γn be a curve that consists of n ≥ 1 curve segments, and let
A and B be two randomly selected points from γ. The convexity measure M(γ) is defined as
the probability that

• the open straight line segment (AB) does not intersect γ (i.e. (AB) ∩ γ = ∅), or

• the open straight line segment (AB) completely belongs to γ (i.e. (AB) ⊂ γ).

The following theorem summarises the desirable properties of the convexity measure

proposed here.

3



...3
1
2

4

1 2 3 4 nn−1

Figure 2: The measured convexity of the presented zigzag curve tends to 0 as n tends to ∞.

Theorem 1 Let γ = γ1 ∪ . . . ∪ γn be a (not necessarily connected) curve. Then

i) M(γ) ∈ (0, 1];

ii) M(γ) = 1 if and only if there is a convex curve ρ such that γ ⊂ ρ;

iii) for any ε > 0 there is a curve γ such that M(γ) < ε;

iv) M(γ) is invariant under similarity transformations.

Proof. The items i, ) ii), and iv) follow easily from the definition.

In order to prove iii) just consider the “zigzag” curve from Fig.2 which consists of 2(n−1)
edges having the length a =

√
37/2. By using the total probability formula we derive (P(E|F)

means “probability of E given F”):

M(γ) = P((AB) ∩ γ = ∅ or P((AB) ⊂ γ | A belongs to the first edge of γ)

+ P((AB) ∩ γ = ∅ or P((AB) ⊂ γ | A belongs to the last edge of γ)

+ P((AB) ∩ γ = ∅ or P((AB) ⊂ γ | A belongs to a middle edge of γ)

=
1

2(n − 1) ·
2

2(n − 1) +
1

2(n − 1) ·
2

2(n − 1) +
2(n−2)∑

i=1

1

2(n − 1) ·
3

2(n − 1) =
3n − 4

2(n − 1)2 .

Since M(γ) = 3n − 4
2(n − 1)2 → 0 as n → ∞, the statement holds. ✷

3 Computation of M(γ)
The exact value of M(γ) can be computed only in particular cases as it was in case of
the zigzag curve from Fig.2 (see the proof of Theorem 1). In most image processing tasks

4



the equation of γ or the equations of γ-segments remain unknown. In such a case it is only

possible to estimate the convexity M(γ). We give the following simple and natural procedure
that can be used for an estimate of M(γ).

Estimation of M(γ)
Input: A curve γ = γ1 ∪ . . . ∪ γn and a number M that depends on the required
precision that should be reached.

Step 1 Estimate the total length of curve γ :

length of γ = length of γ1 + . . . + length of γn

and express the interval [0, length of γ] as the union of n intervals

[0, length of γ] = I1 ∪ I2 ∪ . . . ∪ In =
[0, length of γ1) ∪ [length of γ1, length of γ1 + length of γ2)
∪ . . . ∪ [∑1≤i≤n−1 length of γi, length of γ];

Step 2 Generate M pairs

(a1, b1), (a2, b2), . . . , (aM, bM)

of random numbers from the interval [0, length of γ];

(a) For any pair (ai, bi), i = 1, 2, . . . , N, determine the intervals Iu(ai) and

Iv(bi) such that ai ∈ Iu(ai) and bi ∈ Iv(bi);
(b) Determine the point Xi that is on distance ai −

∑

1≤i≤u(ai)−1

length of γi

from the starting point of γu(ai) and

determine the point Yi that is on distance bi −
∑

1≤i≤v(bi)−1

length of γi

from the starting point of γv(bi);

(c) Check if the straight line segment (XiYi) intersects γ or belongs to it.

Output: The convexity M(γ) is estimated as K
M

where K is the number of straight

line segments (XiYi) which do not intersect γ or completely belong to it.

4 Experimental results

In this section, the convexity measure is demonstrated on several examples. In all cases the

data was preprocessed by performing polygonal approximation using Ramer’s algorithm [5]

5



with a threshold of 2, and 100000 line segment tests were used to compute M. Fig 3 shows
handwritten digits which contain substantial natural variations, not only in their overall

shape, but also in topology.

0.512 0.528 0.538 0.581 0.590 0.611 0.625 0.648 0.677 0.678

0.681 0.694 0.762 0.775 0.841 0.877 0.887 0.947 0.936 1.000

Figure 3: Handwritten digits ordered by their M convexity values.

For instance, of each of the “0”, “2” and “8” digits one example is self intersecting while

the other is not. Nevertheless, ranking the digits according to convexity demonstrates a

reasonable separation between many of them (i.e. “1”, “4”, “5”, “7” and “8”), indicating

that the convexity measure would be a useful property for classification of the digits.

0.067 0.083 0.097

0.113 0.169 0.183

0.225 0.247 0.256

Figure 4: Signatures of Walt Disney, Henri Matisse and Dr. Seuss ordered by their M
convexity values.

6



In the second example signatures, which are made up from multiple curve segments, are

used (see Fig 4). Again noticeable variability is evident within each individual. Note that

since these curves are more complex than the individual digits in Fig 3 they have considerably

lower convexity values. It can be seen from the ranking by M that convexity is a sufficient
descriptor for classification in this small example.

References

[1] L. Boxer. Computing deviations from convexity in polygons. Pattern Recognition Letters,

14:163–167, 1993.

[2] R. Kakarala. Testing for convexity with Fourier descriptors. Electronics Letters,

34(14):1392–1393, 1998.

[3] R.R. Martin and P.L. Rosin. Turning shape decision problems into measures. Int. J.

Shape Modelling, 10(1):83–113, 2004.

[4] E. Rahtu, M. Salo, and J. Heikkilä. A new convexity measure based on a probabilistic

interpretation of images. IEEE Transactions on Pattern Analysis and Machine Intelli-

gence, 28(9):1501–1512, 2006.

[5] U. Ramer. An iterative procedure for the polygonal approximation of plane curves.

Computer Graphics and Image Processing, 1:244–256, 1972.

[6] P.L. Rosin and C.L. Mumford. A symmetric convexity measure. Computer Vision and

Image Understanding, 103(2):101–111, 2006.

[7] J. Žunić and P.L. Rosin. A new convexity measurement for polygons. IEEE Transactions

on Pattern Analysis and Machine Intelligence, 26(7):923–934, 2004.

7