Home
2. Context in Image Classification a. Lower Order Markov Chains3. Context in Text Recognition a. A Quick Bit on Compound Decision Theory
|
2. Context in Image Classificationc. Markov Meshes AbendAs was mentioned in Section 2a about Lower Order Markov Chains, there is another project in this course that covers Markov Dependencies, therefore Markov meshes will not be covered in too much depth in this section of the project. What will be discussed is primarily available in a paper by Abend et al. We know already from the section on Lower Order Markov Chains, how a pixel behaves in a chain. However we know that our images exist in a two dimensional array. We have also seen from the section on Hilbert Space Filling Curves that we can efficiently traverse a pixel grid and visit every pixel only once. So what do we know about the dependence of pixels within a two dimensional pixel grid. Consider once more our happy face:
Once again we need to determine what the probability of occurrence for a certain image is in order to classify it. Therefore, if we can determine the probability of each pixel dependent on the states of the rest of the pixels in the image, we can determine what type of image has the highest probability of being classified. We know that every classification has certain classes that we want to classify our images into (let's say sad face and happy face). So what we are looking for is a way to find the which of these two categories has the highest probability based on the individual dependent probabilities. It turns out that when using Markov Meshes, the conditional probability of a pixel state dependent on a whole array, just simplifies to a pixels' dependence on it's 8 nearest neighbours or:
We can go through the math
in a little more detail below:
The following definitions are needed for the discussion about Markov Meshes. 1) is an m x n array of discrete random variables that create an array as shown below:
2) is a variable located in the row a and the column b of . 3) is the rectangular array of all random variables with i=<c and j>=d. 4) is the rectangular array with the point deleted. 5) is a nonrectangular array such that all variables to the left or above are included. This is shown in the diagram below.
What we are attempting to
do is classify an image based on the assumption that a two dimensional
image can be represented as a third order Markov Mesh and the dependencies
between pixels can be determined using the dependencies defined by the
Markov Mesh.
Consider the probability of the state of conditional on is equal to the probability of conditional on the set of the nearest neighbors to within . For the third order Markov Mesh we get: . If one now considers the joint probability of all variables in the array Xa,b, the Markov Mesh yields the following product:
where p(Xa,b) denotes the joint probability. We know already from the section on Markov Chains, that a pixel at a location k in a first order Markov Chain depends solely on it's to nearest neighbors: . If this extended two a third order Markov Mesh, we obtain the following conditional proabability: . As can be seen, the conditional probability of as it pertains to the entire array, is the same as the conditional probability of the existence of as it pertains to its eight nearest neighbors. The third order Markov Mesh is a special case of this. The general assumption is that where Ua,b are the elements of the upper left hand sector of the original pixel array. From this the probability of existence of a pixel array can be shown to be: .
Previous : 2b.Hilbert
Space Filling Curves
|