Theoretical Background

MainPage

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.

(a) C4

(b) C8

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.

[–] Comments
Roberto Souza at 2015-05-18 12:15h
 0
Thanks, I've corrected the page.

Irene Fantini at 2015-05-17 14:19h
 0
I think that in the last phrase the values are valid for C1 and C2, not y.