mathematical morphology Mathematical morphology (MM) is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions. MM is most commonly applied to digital images, but it can be empl ...

, hit-or-miss transform is an operation that detects a given configuration (or pattern) in a binary image, using the morphological

erosion Erosion is the action of surface processes (such as water flow or wind) that removes soil, rock, or dissolved material from one location on the Earth's crust, and then transports it to another location where it is deposited. Erosion is dis ...

operator and a pair of disjoint structuring elements. The result of the hit-or-miss transform is the set of positions where the first structuring element fits in the foreground of the input image, and the second structuring element misses it completely.

Mathematical definition

In binary morphology, an image is viewed as a subset of a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

\mathbb^d

or the integer grid

\mathbb^d

, for some dimension ''d''. Let us denote this space or grid by ''E''. A structuring element is a simple, pre-defined shape, represented as a binary image, used to probe another binary image, in morphological operations such as

, dilation,

opening Opening may refer to: * Al-Fatiha, "The Opening", the first chapter of the Qur'an * The Opening (album), live album by Mal Waldron * Backgammon opening * Chess opening * A title sequence or opening credits * , a term from contract bridge * , ...

, and

closing Closing may refer to: Business and law * Closing (law), a closing argument, a summation * Closing (real estate), the final step in executing a real estate transaction * Closing (sales), the process of making a sale * Closure (business), Closing a ...

. Let

C

and

D

be two structuring elements satisfying

C\cap D=\emptyset

. The pair (''C'',''D'') is sometimes called a ''composite structuring element''. The hit-or-miss transform of a given image ''A'' by ''B''=(''C'',''D'') is given by: ::

A\odot B=(A\ominus C)\cap(A^c\ominus D)

, where

A^c

is the

set complement In set theory, the complement of a set , often denoted by (or ), is the set of elements not in . When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is th ...

of ''A''. That is, a point ''x'' in ''E'' belongs to the hit-or-miss transform output if ''C'' translated to ''x'' fits in ''A'', and ''D'' translated to ''x'' misses ''A'' (fits the background of ''A'').

Some applications

Thinning

Let

E=\mathbb^2

, and consider the eight composite structuring elements, composed of: :

C_1=\

and

D_1=\

, :

C_2=\

and

D_2=\

and the three rotations of each by 90°, 180°, and 270°. The corresponding composite structuring elements are denoted

B_1,\ldots,B_8

. For any ''i'' between 1 and 8, and any binary image ''X'', define ::

X\otimes B_i=X\setminus (X\odot B_i),

where

\setminus

denotes the set-theoretical difference. The thinning of an image ''A'' is obtained by cyclically iterating until convergence: :

A\otimes B_1\otimes B_2\otimes\ldots\otimes B_8\otimes B_1\otimes B_2\otimes\ldots

Other applications

Pattern detection Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphics ...

. By definition, the hit-or-miss transform indicates the positions where a certain pattern (characterized by the composite structuring element ''B'') occurs in the input image. *

Pruning Pruning is a horticultural, arboricultural, and silvicultural practice involving the selective removal of certain parts of a plant, such as branches, buds, or roots. The practice entails the ''targeted'' removal of diseased, damaged, dead, ...

. The hit-or-miss transform can be used to identify the end-points of a line to allow this line to be shrunk from each end to remove unwanted branches. * Computing the

Euler number In mathematics, the Euler numbers are a sequence ''En'' of integers defined by the Taylor series expansion :\frac = \frac = \sum_^\infty \frac \cdot t^n, where \cosh (t) is the hyperbolic cosine function. The Euler numbers are related to a ...

Bibliography

* ''An Introduction to Morphological Image Processing'' by Edward R. Dougherty, {{ISBN, 0-8194-0845-X (1992) Mathematical morphology Digital geometry