The ways of segmenting general images (edges or regions)

ﬁnding conﬁgurations of edges in parametrically-deﬁned 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 ﬁ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*).

- The most common vector (or matrix) similarity metric is the

**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-template**s 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.

- use
**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.

- use

**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

**Interpolation**

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