Consider a random variable Z() which can take K different values Z_{1},..., Z_{K}. The aim of a Search Tree is to infer the ccdf of Z() from a known realization of Z(): z(),..., z(), called ``training image''.
Call T = {,...,} the family of vectors defining a geometric template (or ``window'') of t locations. These vectors are also called nodes of the template. A data event implied by T, at location u, is the sequence of values:
Guardiano, and later, Strebelle proposed to model the probability
In some cases, data event d_{T} can not be found in the training image. Call T_{-1} the subset of T obtained by dropping one of the vectors (nodes) of T, and similarly, T_{-j} the subset of T after dropping j vectors of T, for any j {0,..., t - 1}, with T_{-0} = T. If data event d_{T} can not be found in the training image, template T is recursively simplified into T_{-1},...,T_{-j}, until d_{T-j} can be found. Typically, the nodes are dropped according to the amount of information they bring in estimating the probability distribution of Z() = z_{k}. The probability PZ() = z_{k} d_{T} is then approximated by
A search tree is a data structure that enables to store all the data events d_{T-j} (j = 0,..., t - 1) present in the training image, along with the corresponding frequencies of occurrence of z_{k} (k = 1,..., K) at the central node.
T | is the type used to represent a category. It is a ``discrete type'', e.g. int, bool, ... | |
allocator | is an object that manages the memory allocation for the search tree. Two models of allocator are available: a pool allocator and a standard allocator. The standard allocator allocates memory only when it is needed. This allows to use as little memory as possible, but may not be efficient in term of speed. Memory allocation is a slow task, and significant speed improvement can be achieved by decreasing the number of times memory is allocated. This is what the pool allocator does: memory is allocated by large chunks or pools, and when new space is needed, it is taken from the pool without requiring the system to allocate some new memory. The standard allocator should be used when memory is an issue, while the pool allocator is useful to improve performance. pool alocator is the default allocator. |
forward_iterator is a model of Forward Iterator. It iterates on a set of geo-values, the training image.
neighborhood is a model of Window Neighborhood. It is used to define the data event associated to each geo-value in range [begin,end).
window_size is the maximum number of geovalues neighbors can contain. nb_of_categories is the number of categories (e.g. "sand", "mud") that we want to work with.
u is the location at which the Gaussian conditional cdf is estimated.
neighbors is neighborhood of location u. It must be the same object (or different object with the same characteristics) as the one used in the search tree constructor. The order in which the neighbors are stored inside the neighborhood is important. Denote + , i = 1,..., N the locations of the N neighbors of u. The algorithm assumes that the i^{th} geo-value in the neighborhood is Z( + ). The function returns 0 if no problem occurred.