Addition of Arbitrary Shapes

You can't add apples and oranges but you can add their shapes.

To avoid ambiguity shapes whose sums I plan to consider will be finite-dimensional sets, say, subsets of a space or a plane or a general vector space V. Talking of apples and oranges, these probably more naturally perceived as sets of points not vectors. Then consider R³ as a set of points and select a point (the origin) so that it would be possible to identify a point with the vector emanating from the origin and ending at the point.

Returning to the sets of vectors, let X and Y be subsets of V. Then X + Y is a subset of V that consists of all the sums A + B with A from X and B from Y. In other words, every element of X + Y can be represented as a sum of elements of X and Y. This is very similar to the componentwise addition and is known as the "Parallelogram Rule". For any two points A and B from X and Y, respectively, A + B is the point that completes the parallelogram with the three vertices O, A, and B.

Verification that the addition is associative and commutative is straightforward. Zero is {O}, the set that consists of a single point - the origin.

This addition has some very desirable properties, especially when restricted to the collection of convex sets. Even more so when it's restricted to a pair of convex polygons.

1. If any of the sets X, Y is translated (as a whole) so will be their sum X + Y
2. If the origin is chosen differently, then the sum X + Y will be translated in the opposite direction but by the same distance as the origin.
3. If X and Y are convex, so is X + Y
4. Let X = B(A, R) and Y = B(B, S) be balls of radii R and S, respectively. Then X + Y = B(A + B, R + S) the ball of radius R + S.

This addition has no inverse element.

However, there is a related operation that very nearly comes to being an inverse. The following also shows that even when equivalent some definitions may (and often are) more fruitful than others. Let's use a new symbol ⊕ to denote the above addition of shapes:

(1)	A⊕B = {a + b: a∈A and b∈B}.

Note that if we use a-b in the definition instead of a+b we would gain precious little. Indeed, in case where B is centrally symmetric the result will be exactly the same. Now let's reformulate the definition. First, let's agree to write A + b for the set {a + b: a∈A}. Now,

(2)	A⊕B = ∪(A + b),

where union is taken over all b∈B. The definitions are equivalent (check this) but (2) has a degree of freedom that provides for possible modifications. A curious mind may ask, what if we use a set operation other than the union. Hermann Minkowski (1864-1909) after whom (2) is known as Minkowski addition also defined (Minkowski) subtraction

(3)	A = ∩(A + b),

Both operations are widely used in image processing or, more specifically, morphological analysis of images, where they are known as dilation (⊕) and erosion (). The terminology is due to the fact that AB ⊂ A ⊂ A⊕B, for any B. Dilation and erosion are not inverse of each other. There are two more useful operations that are defined in terms of dilation and erosion: (for B with central symmetry)

(4)	Closing: O(A, B) = (A⊕B)B Opening: C(A, B) = (AB)⊕B

Assuming B is a circle one may think of the opening as having a ball B roll inside A smoothing its corners (internal angles). More accurately

Theorem

O(A, B) = ∪{B + x: B + x ⊂ A}.

If D^c stands for the complement of D, then C(A, B) = O(A^c, B)^c. So closing may be thought of as having a ball B roll on the ouside of A smoothing its external angles. Both operation are used for noise reduction and feature extraction.

Reference

1. E. R. Dougherty and C. R. Giardina, Mathematical Methods for Artificial Intelligence and Autonomous Systems, Prentice Hall, 1988
2. I. M. Yaglom and B. G. Boltyansky, Convex shapes, Nauka, Moscow, 1951. (in Russian)

Resource Limit Is Reached

The website is temporarily unable to service your request as it exceeded resource limit. Please try again later.

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny