Open classification: probability theory, stochastic process
Markov chain, Andre? Markov (A.A.Markov, 1856- 1922) is mathematically named as a discrete-time stochastic process with Markov properties. In this process, given the current knowledge or information, the past (that is, the historical state before the current period) is irrelevant to predict the future (that is, the future state after the current period).
Markov chain is a sequence of random variables X_ 1, X_2, X_3 ... The range of these variables, that is, the set of all their possible values, is called "state space", and the value of X_n is in time.
P(X_{n+ 1}=x|X_0，X_ 1，X_2，\ldots，X_n) = P(X_{n+ 1}=x|X_n)。
Where x is a state in the process. The above identities can be regarded as Markov properties.
Markov first did this process in 1906. Kolmogorov extended this to countable infinite state space in 1936.
Markov chain is related to Brownian motion and ergodic hypothesis, two important topics in physics at the beginning of the 20th century. However, it seems that Markov seeks not only mathematical motives, but also an extension of the law of large numbers of vertical events in name.
They are indispensable conditions for the following deduction: (1) scale has Markov property. Random fields form a Markov chain from top to bottom, that is, the distribution of Xi only depends on Xi, and has nothing to do with other coarser scales. (2) Conditional independence of pixels in random fields. If the parent node of the Xi pixel is known, then the Xi pixels are independent of each other. This property makes it unnecessary for us to consider the relationship between adjacent pixels in the plane grid, but to study the relationship between adjacent pixels (that is, parent-child nodes) between scales. (3) Given Xn, the pixels in y are independent of each other. (4) separability. If any node xs is given, the variables corresponding to the subtree whose children are root nodes are independent of each other.
From the root with only one node to the leaf node with the same size as the image, a complete quadtree model is established. The causal relationship of Markov chain between layers enables us to quickly calculate the maximum posterior probability or posterior marginal probability of X through non-iterative derivation.
The complete quadtree model also has some problems. (1) Because the probability value is too small, it is difficult to guarantee the accuracy of the computer. If there are more levels, this problem will be more prominent. Although a small value close to 0 can be converted into a large negative value by taking logarithm, if there are too many levels and the probability value is too small, this method will be difficult to work. In addition, the techniques used for these transformations add a lot of calculations. (2) When the image is large, resulting in more layers, layer-by-layer calculation is very complicated, and underflow will definitely occur, and the intermediate variables in the storage will also occupy a lot of space, which will consume more time and space.
(3) There is a blocking effect in the layered model, that is, the boundary of the region may jump, because in this model, adjacent pixels in the same layer of the random field do not necessarily have the same parent node, and there is no interaction between adjacent pixels in the same layer, so the boundary may be discontinuous.
In order to solve these problems, we propose a new hierarchical MRF model-semi-tree model, which is similar in structure to Figure 1 5 and is still a quadtree.
Only the number of layers is greatly reduced compared with the complete quadtree, which is equivalent to cutting the complete quadtree into two parts and removing only the half part. The lowest layer of the model is still consistent with the size of the image, but the top layer has multiple nodes. The properties of the complete quadtree model are completely applicable to the semi-tree model, but the difference is at the top. The complete quadtree model constitutes a complete causal dependence from top to bottom, while the causal relationship between the layers of the semi-tree model is truncated. The parent node and ancestor node of this layer node are deleted, so each node of this layer does not have conditional independence, that is, it does not meet the above property 2, so the relationship between adjacent nodes of this layer is considered. Compared with the complete tree model, the semi-tree model has many layers, so that the information between layers is transmitted quickly, and the probability value will not overflow because of too many layer-by-layer calculations. However, Layer 0 brings new problems. In order to get the correct derivation result, we must consider the interaction between nodes. It is precisely because the influence between adjacent nodes is considered in Layer 0 that the block phenomenon of this model is better than that of the complete tree model. We don't think the selected series is appropriate. Too many levels can't simplify the model, and its advantages can't be reflected, but it can't be too few. Because the probability calculation of layer 0 still needs non-iterative algorithm, the number of nodes in layer 0 is still relatively large because of the small number of layers.
MPM algorithm for trident tree model
Image segmentation, that is, knowing the observed image Y and estimating the configuration of X, can be expressed by using the optimization problem of Bayesian estimator:
X = argmin [e c (x, x) ′| y = y], where the cost function c gives the cost when the real configuration is x and the actual segmentation result is x ′. When y is known, the expectation of this cost is minimized and the optimal segmentation is obtained. Different estimators are obtained by taking different cost functions. If c (x, x')= 65438, δ(x, x') (when x = x', δ(x, x')= 1, otherwise δ(x, x')= 0) gets a MAP estimator, which means that as long as x and x' are different in one pixel.
In practice, some wrong classifications are completely allowed. If the MPM algorithm of semi-tree model is named HT-MPM, it is divided into two steps: upward algorithm and downward algorithm. The upward algorithm calculates P(yd(s)|xs) and P(xs, xρ(s)|yd(s)) layer by layer according to equations (2) and (3). For the lowest layer P(yd(s)|xs)=P(ys|xs), the downward algorithm calculates P(xs|y) layer by layer according to the formula (1), and the sampling x0 (1), ..., x0 (n) starts from the top layer.