The ways of segmenting general images (edges or regions)
ﬁnding conﬁgurations of edges in parametrically-deﬁned shapes (Hough transform)
For every possible position, rotation, or other geometric transformation, compare each pixel’s neighborhood to a template.
After computing the strength of the match for each possibility, select the largest one, the largest n, or all that exceed some threshold.
Comparing Neighorhoods to Templates:
- You already have a template for what you’re looking for, One way of ﬁnding matches is correlation:
Dot product of each neighborhood with the template: shifting the template to each point in the image, point-wise multiplying each pixel in the neighborhood with the template, and adding the results.
The dot product of two vectors is essentially the projection of one onto the other—the more they match, the larger the dot product.
- The other ways of measuring similarity of individual neighborhoods to a template, also based on vector similarity metrics.
- The most common vector (or matrix) similarity metric is the L-norm of their difference.
- The most common forms of L-norms are the L1 norm (sum of absolute values), the L2 norm (square root of the sum of squares—i.e., Euclidean distance), and the L∞ norm (maximum absolute value).
Sometimes, what we’re looking for might not be exactly the same in every image. One way to deal with this is to break the template into pieces and try to match each piece as if it was its own template.
Position the entire template over the neighborhood, then search around the normal position of each sub-template for the best match. The best combined match for all sub-templates gives the match for the overall template.
Avoid checking all possible transformations:
- Hierarchical Matching (Pyramids)
One way to reduce the computational complexity of matching is to use the pyramid structure
- By matching a coarser template to a coarser level of the pyramid, fewer comparisons must be performed.
- Once the strength of each coarser-resolution match is calculated, only those that exceed some threshold need to be evaluated/compared for the next-ﬁner resolution.
This process proceeds until the ﬁnest resolution (or at least a sufﬁciently ﬁne resolution for the current task) is reached.
- Iterative Reﬁnement
- use gradient-descent minimization techniques to iteratively tweak the transformation parameters until the best match is found.
- these techniques require starting “near” the right solution.
- we don’t have to check all possible transformations, just a sufﬁcient number to allow us to ﬁnd the matches through further reﬁnement.
- e.g., we might test rotations in 5- or 10-degree increments only
For each initial rotation, then further reﬁne the match by iteratively minimizing the difference from then template.
- Chamfer Matching
- use distance maps to guide edge-based matches to corresponding edges.
- a chamfer is a map of the distance from each point to the nearest boundary.
- characterize the degree of mismatch for two curves (boundaries or other curve-based representations) by creating a distance map for one and then integrating the distance map for the ﬁrst curve over all positions in the second curve.
- Then iteratively adjust the position/orientation of the second curve until this integrated distance is minimized.
Chamfer matching has also been used to match skeletal structures such as the medial axis.
Distance Transforms(Distance Maps):
- assigns to each point x in the image a minimal distance D(x) from some locus of points (usually object boundaries)
- zero at the boundary
- increasing values just inside it, yet higher values farther inside
- Similarly, we get distances increasing as we go outward from the boundary.
A large number of applications use a positive distance map outside the object and a negative one inside, or vice versa.
Distance maps have several applications:
- Shape description
Since shape and spatial relationships (distance) are so integrally related, this would seem to be an obvious application.
One speciﬁc such application is the medial axis, a shape representation
interpolating between two shapes by interpolating between their (positive outside, negative inside) distance maps