Medial axis

In geometry , the medial axis of an area is a set of points that lie in a kind of geometric center of the area. It was proposed by Harry Blum in the 1960s to describe biological forms. Since then, the medial axis has found a multitude of applications in a wide variety of areas, from the formation of galaxies, path planning for robots or the recognition of characters to the representation of molecular structures.

Medial axis in the plane

Blum defined the medial axis of an area in the plane as the set of centers of maximum circles in . A circle is maximal in if it lies completely in and there is no other circle in which contains. From this it immediately follows that the points of the medial axis must also lie inside . It is found that maximal circles touch the edge of the area tangentially, i.e. H. the tangent direction of the circle at the point of contact corresponds to the tangent direction of the edge (if this is defined - with polygons, for example, this is not the case in the corner points). In general, the maximum circles touch the edge in two points , but there are also situations with one or an infinite number of points of contact. The points of contact are also referred to as base points. ${\ displaystyle MA_ {G}}$ ${\ displaystyle G \ subset \ mathbf {R} ^ {2}}$ ${\ displaystyle G}$ ${\ displaystyle K}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle K}$ ${\ displaystyle G}$ ${\ displaystyle \ partial G}$ ${\ displaystyle g_ {1}, g_ {2} \ in \ partial G}$ ${\ displaystyle n}$

If you assign the radius of the corresponding maximum circle to each point on the medial axis, you get an image . This so-called radius function assigns its distance to the edge to each point on the medial axis . Medial axis and radius function together are referred to as medial axis transformation, as they make it possible to reconstruct the original area again. ${\ displaystyle r: MA_ {G} \ rightarrow \ mathbf {R} _ {+}}$ ${\ displaystyle \ partial G}$

An alternative definition of the medial axis results from the observation that there is generally more than one shortest path to the edge for a point on the MA - these paths are the distances to the base points. So the medial axis can also be defined as the set of points inside the area, from which there is no uniquely determined shortest path to the edge of the set. This means that there are at least two directions in which one can get the fastest from a point on the medial axis to the edge.

{\ displaystyle MA_ {G}: = \ left \ {p \ in \ mathbf {R} ^ {2} \ mid \ exists g_ {1} \ neq g_ {2} \ in \ partial G: \ min _ {g \ in \ partial G} d (p, g) = d (p, g_ {1}) = d (p, g_ {2}) \ right \},}

where the metric describes the distance between points and . Usually the Euclidean distance is used for this . ${\ displaystyle d (p, x), x \ in \ mathbf {R} ^ {2}}$ ${\ displaystyle p}$ ${\ displaystyle x}$

The medial axis only depends on the choice of a metric - the first definition also contains this implicitly: a circle with a center and radius is defined as the set of all points that are at a distance , the edge of the circle is formed by the points at a distance . ${\ displaystyle m}$ ${\ displaystyle r}$ ${\ displaystyle p}$ ${\ displaystyle d (m, p) <r}$ ${\ displaystyle d (m, p) = r}$

Special situations

If the edge of the area has corners, the medial axis touches the edge at these points. This is not the case in all other places.

Higher dimensions

The definition of the medial axis given above can be canonically extended to higher dimensions; it is, as already mentioned, only dependent on the existence of a metric in the space in which the area is located. Instead of maximum circles, maximum -dimensional (hyper) spheres are then considered in -dimensional space . ${\ displaystyle n}$ ${\ displaystyle n}$

calculation

In the 2D case, the medial axis of an area can be approximated by calculating the Voronoi diagram of a scan of the edge. The Voronoi nodes then approximate the medial axis, the accuracy of the approximation depending on the sampling density and the fineness of structures on the edge.

Application in art analysis

When investigating the aesthetic effect of works of art, the media axis transformation was used. The apparently random arrangement of the stones in Japanese rock gardens can be traced back to a geometrically appealing figure.

Individual evidence

↑ Harry Blum: A Transformation for Extracting New Descriptors of Shape , in W. Wathen-Dunn (ed.), Proc. Models for the Perception of Speech and Visual Form, pp. ~ 362-380, MIT Press, Cambridge, MA, November 1967. ( PDF )
↑ Frederic F. Leymarie and Benjamin B. Kimia: From the Infinitely Large to the Infinitely Small , in Medial Representations , pp 327-351, Springer, 2008. [1]
↑ Van Tonder et al .: Visual structure of a Japanese Zen garden. Nature. 2002; 419 (6905): 359-60. PMID 12353024 full text (.pdf; 102 kB)

[1] Harry Blum: A Transformation for Extracting New Descriptors of Shape , in W. Wathen-Dunn (ed.), Proc. Models for the Perception of Speech and Visual Form, pp. ~ 362-380, MIT Press, Cambridge, MA, November 1967. ( PDF )

[2] Frederic F. Leymarie and Benjamin B. Kimia: From the Infinitely Large to the Infinitely Small , in Medial Representations , pp 327-351, Springer, 2008. [1]

[3] Van Tonder et al .: Visual structure of a Japanese Zen garden. Nature. 2002; 419 (6905): 359-60. PMID 12353024 full text (.pdf; 102 kB)