Shape detection using coherent appearance modeling

1. A method of finding an object in an image comprising:

(a) describing an object shape by one or more sets of feature points;

(b) estimating positions of the feature points;

(c) finding new locations for each feature point based on a first appearance model, having a first resolution, of an aggregate appearance of the object in local neighborhoods of all feature points; and

(d) constraining the positions of the feature points based on a shape model;

wherein step (c) of finding new locations for each feature further comprises:

(c1) extracting windows of the image depicting an appearance in the local neighborhood of the feature points;

(c2) concatenating the windows to create an aggregate texture vector;

(c3) finding an acceptable vector within the appearance model space;

(c4) extracting texture targets from the acceptable vector;

(c5) comparing targets at locations surrounding the feature points; and

(c6) selecting most similar locations.

2. A method as in claim 1 further comprising:

(e) testing for stopping criteria; and

(f) if stopping criteria has not been reached repeat steps (c)-(f).

3. A method as in claim 2 further comprising:

(g) testing if a final resolution has been reached; and

(h) if final resolution has not been reached replace first the first appearance model with a second appearance model having a different resolution and repeat steps (c)-(h).

4. A method as in claim 1 wherein the feature points are connected in one or more sets.

5. A method as in claim 1 wherein the positions of the feature points are estimated by aligning an average relative positions of the feature points with an automatically or manually specified starting position.

6. A method as in claim 1 wherein the shape model is constructed by analyzing one or more exemplar shapes.

7. A method as in claim 6 wherein principle components analysis is applied to the exemplar shapes to develop the shape model.

8. A method as in claim 7 wherein the shape model is defined by an average shape and primary modes of shape variation.

9. A method as in claim 8 wherein:

the shape model is used to constrain the positions of the feature points by limiting a range of shape variability along the primary modes of shape variation.

10. A method of finding an object in an image comprising:

(a) describing an object shape by one or more sets of feature points;

(b) estimating positions of the feature points;

(c) finding new locations for each feature point based on a first appearance model, having a first resolution, of an aggregate appearance of the object in local neighborhoods of all feature points; and

(d) constraining the positions of the feature points based on a shape model, wherein the shape model is defined by an average shape and primary modes of shape variation and is constructed by applying principal components analysis to analyze one or more exemplar shapes, and wherein the shape model is used to constrain the positions of the feature points by limiting a range of shape variability along the primary modes of shape by:

(i) determining vector of weights for a current shape that form parameters of the shape model;

(ii) constraining the vector of weights; and

(iii) determining the shape that corresponds to the constrained vector of weights.

11. A method as in claim 10 wherein:

constraining the vector of weights is done by clipping the vector of weights to a given number of standard deviations of the exemplar shapes along each mode of the shape model.

12. A method as in claim 10 wherein:

constraining the vector of weights is done by finding the closest vector of weights such that Mahalanobis distance is within a suitable maximum value.

13. A method as in claim 2 wherein:

stopping criteria is elapsed time, stability of feature points, stability of appearance at the feature points, or number of iterations.

14. A method as in claim 1 wherein the windows of the image are aligned to a consistent position relative to a shape.

15. A method as in claim 1 wherein the appearance model is constructed by analyzing an appearance of one or more exemplar images depicting the object.

16. A method of finding an object in an image comprising:

(a) describing an object shape by one or more sets of feature points;

(b) estimating positions of the feature points;

(c) finding new locations for each feature point based on a first appearance model, having a first resolution, of an aggregate appearance of the object in local neighborhoods of all feature points; and

(d) constraining the positions of the feature points based on a shape model;

wherein the appearance model is constructed by analyzing an appearance of one or more exemplar images depicting the object by,

(i) determining preferred feature positions within the exemplar images;

(ii) extracting windows of the image depicting an appearance in the local neighborhood of the feature points;

(iii) concatenating an appearance windows for each exemplar image to create exemplar aggregate texture vectors; and

(iv) constructing an aggregate appearance model by analyzing one or more exemplar aggregate texture vectors.

17. A method as in claim 16 wherein principle components analysis is applied to the exemplar aggregate texture vectors to develop the appearance model.

18. A method as in claim 17 wherein the appearance model is defined by an average appearance and primary modes of appearance variation.

19. A method as in claim 1 wherein:

the appearance model is used to find an acceptable vector within the aggregate model space by constraining the appearance of the aggregate texture vector by limiting the range of appearance variability along the primary modes of appearance variation.

20. A method of constraining the appearance of the aggregate texture vector as in claim 19 comprising;

(a) determining vector of weights for a current aggregate texture vector that form parameters of the appearance model;

(b) constraining the vector of weights; and

(c) determining the aggregate texture vector that corresponds to the vector of weights.

21. A method as in claim 20 wherein:

constraining the vector of weights is done by clipping the vector of weights to a given number of standard deviations of the exemplar shapes along each mode of the shape model.

22. A method as in claim 20 wherein:

constraining the vector of weights is done by finding the closest weights such that the Mahalanobis distance is within a suitable maximum value.

23. A method as in claim 1 wherein the step of comparing targets at locations surrounding the feature points comprises:

measuring an error between the targets and similarly sized regions surrounding the feature points.

24. A method as in claim 23 wherein the error is measured using absolute difference, mean squared error, correlation, or normalized correlation.

25. A method as in claim 1 wherein the step of finding new locations for each feature point also utilizes independent models of a local appearance around the feature points.

26. A method as in claim 25 wherein the independent models are weighted more significantly during early iterations of the method and the aggregate model is weighted more significantly during the later iterations.

27. A method as in claim 3 wherein the different resolutions of the appearance model, span coarse to fine scales, wherein the coarser scales cover larger local neighborhoods of the feature points than the finer scales.

28. A method as in claim 27 wherein the coarsest aggregate appearance model is used in conjunction with a wide search area in a first iteration of the method, and successively finer appearance models and narrower search areas are used in subsequent iterations.

29. A method as in claim 1 wherein the method is a component of a software program stored on a computer-readable medium.