# Theoretical Background

# Graph Theory basic Definitions

**Undirected Graph:** An undirected graph can be seen as a set of nodes, *V*, and a set of edges, *E*, represented by non-ordered pairs of nodes. Usually a graph *G* is
denoted by *G(V,E)*.

**Path:** A path between nodes *i* and *j* is a sequence of edges connecting these two nodes.

**Simple path:** A path with no repeated nodes is called a simple path.

**Cycle:** A cycle is defined as being a path that starts and ends at the same node.

**Connected Component:** A connected component of an undirected graph is a maximal set of nodes in which any two nodes are connected to each other by paths.

**Connected Graph:** A graph is said connected if there is a path from any node to any other node in the graph.

**Tree:** A tree is an undirected graph
that is connected and has no cycles.

An undirected graph with and is illustrated in Figure 1. The graph is not connected, since node is not connected to anyone, and the path joining nodes , , and form a cycle. A tree is illustrated in Figure 2.

Figure 1. Illustration of a graph with and .

Figure 2. Illustration of a tree.

**Rooted Tree:** A rooted tree,
, is a tree in which one of its nodes has been designated the root, therefore its edges have a natural orientation,
i.e. it is a directed graph. It has a partial ordering of its nodes. We say that
if and only if the path from the root to
passes through
.

**Parent:** The parent of a node is the node connected to it on the path to the root.

**Child:** A child of a node
is a node of which
is the parent.

**Root:** It is the only node in the rooted tree that does not have a parent.

**Leaf:** It is a node in the tree that does not have children.

**Bifurcation:** It is a node with more than one child.

**Internal:** It is any node that is neither a leaf or the root of the tree.

**Sibling:** Two nodes are said to be siblings if they have the same parent.

**Descendant:** A descendant node
of a node
is a node such that
is in the path from
to the root of the tree.

**Ancestor:**
An ancestor node of
is any node in the path from
to the root of the tree.

**Branch:** A branch is a set of nodes that join a leaf to the root node.

A rooted tree is illustrated in Figure 3. The arrows point towards the parents. Node is the root. Nodes and are leaves, nodes and are siblings. Node is a bifurcation. The sequence constitutes a branch of the tree.

Figure 3. Illustration of a rooted tree. The arrows point towards the parents.

**Binary Tree:** A binary tree is a rooted tree in which each of its nodes has at most two children. A binary tree is said to be full if
each of its nodes is either a leaf or possesses exactly two child nodes. A full binary tree has
nodes, where
is the
number of leaves in the tree.

A full binary tree is illustrated in Figure 4.

Figure 4. Illustration of a full binary tree. It has leaves, therefore the tree has nodes.

# Image Processing Definitions

**Grey-scale image:** It is a function
,
and
.
is an ordered pair
that represents a pixel of the image, and
is its luminosity intensity, usually
,
.
If
, the image is said to be a binary image, the pixels with intensity equal
compose the foreground and the pixels with intensity equal
compose the background of the binary image.

**Negative of an image:**

**Image Thresholding:** The image thresholding is a procedure that given a threshold
, it transforms an image into a binary image.
There are two cases the upper and the lower thresholding. They are expressed, respectively by the following equations:

**Neighborhood of a pixel:** The neighborhood of a pixel
corresponds to a set of coordinates
defined in relation to
in
the image domain
. The most common pixel neighborhoods used are the neighborhoods
and
defined below:

The neighborhoods and of a pixel are illustrated in Figure 5.

Figure 5. Illustration of the neighborhoods (a) and (b) of a pixel.

**Connectivity:** An image can be seen as a graph, where the pixels correspond to the nodes. Two pixels are connected, i.e. there
is an edge joining them, if they are neighbors, according to the neighborhood used, that share a common property that defines
a component. The property may be color, brightness, range of brightness values, or anything else of interest.

**Adjacency:** Two pixels
and
are adjacent, if they are connected.

**Upper threshold set:**
The upper threshold set is the set of connected components
that compose the foreground of the binary image
resulting of the upper threshold
. The similarity criterion to define the connectivity is that the pixels have the same grey-level.

An important property of threshold sets is that for each connected component resulting of the upper threshold there is a connected component resulting of the upper threshold , such that .

**Flat zone:** Flat zones are connected components in which the similarity criteria used to define connectivity is that the pixels have the same grey-level.

**Regional Maximum:** A regional maximum of an image
is a flat zone
, if
,
and
is any neighboring pixel of
.

**Partition:** A partition
of a set
is a set of nonempty subsets of
such that every element
in
is in exactly
one of these subsets.

**Grey-scale Image Ordering:** A grey-scale image
is said to be contained in a grey-scale image
of the same dimensions,
, if and only if:

**Anti-extensive Filter:** An anti-extensive filter
is a filter such that:

**Connected Filter:** is a filter in which the partition composed of the input image flat zones is always finer than the partition of the
filtered image flat zones. The mathematical definition of a connected filter
is given by:

Connected filters do not create new contours in the image and they do not modify the position of the existing contours.

**Extinction value:** Consider
a regional maximum of an image
, and
is a family of
decreasing connected anti-extensive transformations. The extinction value corresponding to
with respect to
and denoted by
is the maximal
value, such that
still is a regional maxima of
.
This definition can be expressed through the following equation:

where is the set containing all the regional maxima of . Extinction values of regional minima can be defined similarly.

Roberto SouzaIrene Fantini