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.
# posted by Jared @ 5:24 PM 
