The ways of segmenting general images (edges or regions)

finding configurations of edges in parametrically-defined shapes (Hough transform)

Template matching:

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 finding 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 otherthe 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).

Flexible Templates:

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-finer resolution.

This process proceeds until the finest resolution (or at least a sufficiently fine resolution for the current task) is reached.

  • Iterative Refinement
    • 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 sufficient number to allow us to find the matches through further refinement.
    • e.g., we might test rotations in 5- or 10-degree increments only

      For each initial rotation, then further refine 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 first 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 specific such application is the medial axis, a shape representation

    • Interpolation

interpolating between two shapes by interpolating between their (positive outside, negative inside) distance maps


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Just another site

Jing's Blog

Just another site

Start from here......







Just another site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision


Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness



Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: