In this project, we have proposed a framework to develop pattern recognition techniques based on optimum-path forests, with methods for supervised learning [1] and data clustering [2].

The previous version of this framework is the Image Forest Transform (IFT) -- a tool for the design of image processing operators based on optimum-path forests [3]. In the IFT, an image is interpreted as a graph, whose the pixels are the nodes and the arcs are defined by an adjacency relation. The minimization/maximization of a path-value function reduces the image operator to an optimum-path forest, followed by a local processing of its attributes.

We have extended this idea from the image domain to the feature space (distance space). Data samples are the nodes of a graph in the feature space, whose the arcs are defined by an adjacency relation. The minimization/maximization of a path-value function by the IFT algorithm outputs an optimum-path forest (i.e., a data partition into groups/classes).

The optimum-path forest (OPF) classifiers exploit the strength of connectedness between samples and group/class prototypes in the feature space. The prototypes can be found by either supervised [1] or unsupervised [2] learning. It is also not difficult to devise semi-supervised learning techniques.

Different methods result from the choice of prototype estimation, path-value function and adjacency relation. The prototypes compete with each other and each prototype conquers the samples more strongly connected to it than to any other, according to the path-value function. In data clustering, these samples form the nodes of an optimum-path tree (group) rooted at that prototype. In supervised classification, each class is represented by an optimum-path forest rooted at its prototypes.

Training consists of finding prototypes and an optimum-path forest from a given training set. The classification of a new sample is done by considering it as part of the original graph and incrementally computing the optimum-path up to it. The sample is then assumed to be in the same group/class of the root, which has conquered it by this optimum path.