Next: Changing the Linear Algebra Up: Function Object Classes Previous: Indicator Cdf Estimator

Subsections

## Search Tree

search_tree<T, allocator>

Consider a random variable Z() which can take K different values Z1,..., ZK. 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:

DT() =  {Z( + ),..., Z( + )}

u is called the central node of the template. Provided the training image is stationary, the same data event (i.e. the same sequence of values) can be observed at different locations.

Guardiano, and later, Strebelle proposed to model the probability

PZ() = zk  {z( + ),..., z( + )}

by the frequency of occurrence in the training image of event

z() = zk  {z( + ),..., z( + )}

( is a location of the training image): if for a given data event dT, there are n locations in the training image such that:

DT() = dT    i = 1,..., n

and among these n locations, nk are such that the central pixel value z() = zk ( j = 1,..., nk), then the probability PZ() = zk  dT is modeled by

PZ() = zk  dT =

In some cases, data event dT 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 dT can not be found in the training image, template T is recursively simplified into T-1,...,T-j, until dT-j can be found. Typically, the nodes are dropped according to the amount of information they bring in estimating the probability distribution of Z() = zk. The probability PZ() = zk  dT is then approximated by

PZ() = zk  dT PZ() = zk  dT-j

A search tree is a data structure that enables to store all the data events dT-j (j = 0,..., t - 1) present in the training image, along with the corresponding frequencies of occurrence of zk (k = 1,..., K) at the central node.

### Template Parameters

 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.

### Model of

Single Variable Cdf Estimator

### Members

• template<class window_neighborhood, class forward_iterator>
search_tree::search_tree(forward_iterator begin, forward_iterator end
window_neighborhood& neighbors,
int window_size, int nb_of_categories)

Constructs a search_tree.

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.

• template<class location, class non_param_cdf>
int search_tree::operator()(const location& u,
const window_neighborhood& neighbors,
non_param_cdf& ccdf)

Function call operator. It estimates the non-parametric cdf parameters and modifies ccdf accordingly. location is a model of Location, and window_neighborhood is a model of Window Neighborhood.

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 ith geo-value in the neighborhood is Z( + ). The function returns 0 if no problem occurred.

Next: Changing the Linear Algebra Up: Function Object Classes Previous: Indicator Cdf Estimator
nicolas
2002-05-07