Wednesday, May 09, 2007
Graphical Models for COPAP
At a high level, the graphical model for COPAP looks like this:
where phi is the correspondence vector from shape x to shape y. The independence assumption in local features breaks the model into
where {x_i} and {y_i} are local shape descriptors. We wish to maximize P(phi|x,y), which is broken down into (1/Z)*P(x,y|phi)*P(phi), where Z is a normalizing constant. We model P(x,y|phi) using the PLSD assignment costs. In order to model P(phi), we note that building the cyclic-ordering constraint into P(phi) introduces dependencies between the phi_i's. In fact, these dependencies will be non-Markovian since phi_i depends on the last non-zero (i.e. non-skipped) assignment, which may or may not be phi_{i-1}. However, we can transform the model for P(phi) into a cyclic Markov chain by adding the following state:
alpha_i = last non-zero assignment (before phi_i)
omega_i = wrapping point (i.e. j s.t. phi_j < alpha_j)
In a legal matching, all omega_i's must be the same (i.e. there is only one wrapping assignment), and aside from the wrapping assignment, phi_i > alpha_i for all i. Graphically, the structure is:
where the graph wraps around on itself to form a cycle. If we collapse the tuple (phi_i, alpha_i, omega_i) into a single variable, phi'_i, we get the following cyclic Markov chain:
Now, if we knew ahead of time where the wrapping point was going to be (i.e. omega_i = k for all i, k known), then the cycle would be broken between phi'_{k-1} and phi'_k, yielding a linear chain:
Therefore a naive approach (and the approach we will ultimately use, with some modifications), is to simply try each wrapping point, k, each time solving the linear Markov chain using dynamic programming, and then to pick the k that yields the maximum likelihood assignment vector, phi.
where phi is the correspondence vector from shape x to shape y. The independence assumption in local features breaks the model into
where {x_i} and {y_i} are local shape descriptors. We wish to maximize P(phi|x,y), which is broken down into (1/Z)*P(x,y|phi)*P(phi), where Z is a normalizing constant. We model P(x,y|phi) using the PLSD assignment costs. In order to model P(phi), we note that building the cyclic-ordering constraint into P(phi) introduces dependencies between the phi_i's. In fact, these dependencies will be non-Markovian since phi_i depends on the last non-zero (i.e. non-skipped) assignment, which may or may not be phi_{i-1}. However, we can transform the model for P(phi) into a cyclic Markov chain by adding the following state:
alpha_i = last non-zero assignment (before phi_i)
omega_i = wrapping point (i.e. j s.t. phi_j < alpha_j)
In a legal matching, all omega_i's must be the same (i.e. there is only one wrapping assignment), and aside from the wrapping assignment, phi_i > alpha_i for all i. Graphically, the structure is:
where the graph wraps around on itself to form a cycle. If we collapse the tuple (phi_i, alpha_i, omega_i) into a single variable, phi'_i, we get the following cyclic Markov chain:
Now, if we knew ahead of time where the wrapping point was going to be (i.e. omega_i = k for all i, k known), then the cycle would be broken between phi'_{k-1} and phi'_k, yielding a linear chain:
Therefore a naive approach (and the approach we will ultimately use, with some modifications), is to simply try each wrapping point, k, each time solving the linear Markov chain using dynamic programming, and then to pick the k that yields the maximum likelihood assignment vector, phi.
Monday, May 07, 2007
MPEG-7 Shape Classification Results
15 training shapes per class, 5 testing shapes. Classification rates were about as expected, perhaps slightly better than expected, since correct classification means that the correct model must have the highest likelihood out of all 70 shape models. In other words, there is no difference between 2nd best and worst in terms of classification error.
Figure 1. Classification rate (averaged over all shape classes) vs. number of principle components retained in the tangent space PCA shape models in each class. There was an error in the classification with 15 PCs (perhaps due to singularities). On average, overfitting does not appear to be a major problem in the models since the classification rate increases monotonically with model dimensionality.
Figure 2. Average classification rates for each shape class (averaged over all numbers of principle components).
Figure 3. Max. classification rates for each shape class (maximized over all numbers of principle components).
Figure 1. Classification rate (averaged over all shape classes) vs. number of principle components retained in the tangent space PCA shape models in each class. There was an error in the classification with 15 PCs (perhaps due to singularities). On average, overfitting does not appear to be a major problem in the models since the classification rate increases monotonically with model dimensionality.
Figure 2. Average classification rates for each shape class (averaged over all numbers of principle components).
Figure 3. Max. classification rates for each shape class (maximized over all numbers of principle components).
