Shape detection using chain code states

1. A method for identifying an object in a digital image stored in a computer memory as an array of pixels, the method comprising:

traversing the pixels corresponding to a contour of an unknown object in the digital image, wherein traversing comprises:

i. loading a next chain-code symbol in the contour into a computer memory;

ii. maintaining a current state if the next chain-code symbol in the contour is within a first set of chain-code symbols;

iii. transitioning to a next state if the next chain-code symbol in the contour is within a second set of chain-code symbols; and

iv. designating the unknown object as a first type of object if the next chain-code symbol is within neither of the first or second sets of chain-code symbols,

wherein the unknown object is identified as a second type of object if a predetermined number of states are visited.

2. The method of claim 1 , wherein the first type of object comprises a non-round object and the second type of object comprises a round object.

3. The method of claim 2 , wherein the extended chain codes comprise a code for an end-of-contour pixel and a code for a multi-contour pixel.

4. The method of claim 1 , further comprising assigning extended chain codes to pixels in the digital image.

5. The method of claim 1 , further comprising searching for the contour in the digital image.

6. The method of claim 5 , wherein searching for the contour comprises searching for a chain code in the digital image.

7. The method of claim 6 , further comprising searching for an opposite chain code in the digital image.

8. The method of claim 5 , wherein searching for the contour comprises searching for a first chain code in clockwise objects in the digital image and for a second chain code in counter-clockwise objects in the digital image.

9. The method of claim 1 , further comprising filtering the unknown object via a chain-code histogram.

10. The method of claim 1 , further comprising:

computing a gradient of a plurality of previous chain-code symbols; and

designating the unknown object as a non-round object if the gradient is less than a first threshold or greater than a second threshold.

11. The method of claim 10 , wherein computing the gradient comprises computing a first average of a first set of previous chain-code symbols, a second average of a second set of previous chain-code symbols, and computing the difference of the first and second averages.

12. The method of claim 1 , further comprising:

detecting a break in the contour of the unknown object;

searching an area of the image for the next chain-code symbol past the break.

13. The method of claim 12 , wherein a size of the area depends at least in part on an average direction of a plurality of previous chain codes or a number of previous chain codes.

14. A system for identifying an object in a digital image, the system comprising:

a computer memory for storing chain-code symbols related to a contour of an unknown object in the digital image;

a processor for traversing the contour by executing instructions for:

i. maintaining a current state if a next chain-code symbol is within a first set of chain-code symbols;

ii. transitioning to a next state if the next chain-code symbol is within a second set of chain-code symbols; and

iii. designating the unknown object as a first type of object if the next chain-code symbol is within neither of the first or second sets of chain-code symbols,

wherein the unknown object is identified as a second type of object if a predetermined number of states are visited.

15. The system of claim 14 , further comprising an image-capture device for capturing the digital image.

16. The system of claim 14 , further comprising a user interface for issuing commands to, or receiving data from, the processor.

17. The system of claim 14 , wherein the system is mounted on a vehicle.

18. The system of claim 14 , wherein the second type of object is a round object and the object is a road sign.

19. A non-transitory computer-readable hardware apparatus having one or more computer-readable programs stored thereon for identifying an object in a digital image stored in a computer memory as an array of pixels, that when executed on a processor configure the processor to perform one or more operations comprising:

traversing the pixels corresponding to a contour of an unknown object in the digital image, wherein traversing comprises:

i. loading a next chain-code symbol in the contour into a computer memory;

ii. maintaining a current state if the next chain-code symbol in the contour is within a first set of chain-code symbols;

iii. transitioning to a next state if the next chain-code symbol in the contour is within a second set of chain-code symbols; and

iv. designating the unknown object as a first type of object if the next chain-code symbol is within neither of the first or second sets of chain-code symbols,

wherein the unknown object is identified as a second type of object if a predetermined number of states are visited.

20. The non-transitory computer-readable hardware apparatus of claim 19 , wherein the first type of object comprises a non-round object and the second type of object comprises a round object.

21. The non-transitory computer-readable hardware apparatus of claim 20 , wherein the round object is a road sign.

22. The non-transitory computer-readable hardware apparatus of claim 19 , further comprising assigning extended chain codes to pixels in the digital image, wherein the extended chain codes comprise a code for an end-of-contour pixel and a code for a multi-contour pixel.

23. The non-transitory computer-readable hardware apparatus of claim 19 , further comprising searching for the contour in the digital image, wherein searching for the contour comprises searching for a chain code in the digital image.

24. The non-transitory computer-readable hardware apparatus of claim 19 , further comprising searching for the contour in the digital image, wherein searching for the contour comprises searching for a first chain code in clockwise objects in the digital image and for a second chain code in counter-clockwise objects in the digital image.

25. The non-transitory computer-readable hardware apparatus of claim 19 , further comprising:

computing a gradient of a plurality of previous chain-code symbols; and

designating the unknown object as a non-round object if the gradient is less than a first threshold or greater than a second threshold.

26. The non-transitory computer-readable hardware apparatus of claim 25 , wherein computing the gradient comprises computing a first average of a first set of previous chain-code symbols, a second average of a second set of previous chain-code symbols, and computing the difference of the first and second averages.

27. The non-transitory computer-readable hardware apparatus of claim 19 , further comprising:

detecting a break in the contour of the unknown object;

searching an area of the image for the next chain-code symbol past the break.

28. An apparatus for identifying an object in a digital image, the apparatus comprising:

means for storing chain-code symbols related to a contour of an unknown object in the digital image;

means for traversing the contour by executing instructions for:

i. maintaining a current state if a next chain-code symbol is within a first set of chain-code symbols;

ii. transitioning to a next state if the next chain-code symbol is within a second set of chain-code symbols; and

iii. designating the unknown object as a first type of object if the next chain-code symbol is within neither of the first or second sets of chain-code symbols,

wherein the unknown object is identified as a second type of object if a predetermined number of states are visited.

29. The apparatus of claim 28 , further comprising means for assigning extended chain codes to pixels in the digital image, wherein the extended chain codes comprise a code for an end-of-contour pixel and a code for a multi-contour pixel.

30. The apparatus of claim 28 , further comprising means for searching for the contour in the digital image, wherein searching for the contour comprises searching for a first chain code in clockwise objects in the digital image and for a second chain code in counter-clockwise objects in the digital image.