PATTERN DETECTION ON AN SIMD PROCESSOR

• US 20100232680A1
• Filed: 05/11/2007
• Published: 09/16/2010
• Est. Priority Date: 06/08/2006
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips N.V.
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Kleihorst, Richard Petrus
• Application Number:
  US12/303,581
• Publication Number:
  US 20100232680A1
• Time in Patent Office: Days
• US Class Current: 382/145
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/955 using specific electronic processors
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
• CPC Class Codes: G06V 20/584 of vehicle lights or traffic lights
• CPC Class Codes: G06V 20/625 License plates
• CPC Class Codes: G06V 2201/08 Detecting or categorising vehicles
• CPC Class Codes: G06V 40/28 Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113

Abstract

A method for detecting a pattern in an image comprising a grid of data elements processes each data element in a predetermined order. In processing one of the data elements, the following steps are carried out. It is checked (100) whether a predetermined local feature is present at the data element to generate information about the local feature if it is present. A propagation direction (42) is associated with the generated information, where the propagation direction is chosen such that data elements along the propagation direction still have to be processed. The generated information, as well as the information propagated to the data element, are propagated (110) to respective data elements closest to the data element along the respective propagation directions associated with the respective information. It is checked (104) whether a predetermined pattern is present which includes a plurality of features (32) based on information propagated to the data element about local features established elsewhere in the image, and if found, information about the pattern is outputted (108).

Claims

1. A method for detecting a pattern in an image comprising a grid of data elements, the method comprising:

processing each data element in a predetermined order

checking (100) for a presence of a predetermined local feature (32) at the data element and generating information about the local feature if it is present and associating a propagation direction (42) with the generated information, where the propagation direction is chosen such that data elements along the propagation direction (42) still have to be processed;

propagating (110) the generated information and the information propagated to the data element to respective data elements closest to the data element along the respective propagation directions associated with the respective information;

checking (104) for a presence of a predetermined pattern including a plurality of features (32) based on information propagated to the data element about local features established elsewhere in the image, and

outputting (108) information about the pattern if found.

2. The method according to claim 1, wherein the predetermined order of processing the data elements is such that all data elements of a grid line are processed before proceeding to process data elements of a subsequent neighboring grid line.

3. The method according to claim 1,

further comprising using a plurality of processing elements (12) for processing a plurality of respective data elements in parallel according to the predetermined order;

and

wherein the step of propagating the information comprises making the information available to the processing element (12) that is scheduled to process the respective data element to which the information is propagated.

4. The method according to claim 3, wherein the predetermined order of processing the data elements is such that the plurality of data elements scheduled to be processed in parallel are part of a single grid line, and all data elements of the grid line are processed before proceeding to process data elements of a subsequent neighboring grid line.

5. The method according to claim 1, wherein the step of checking for the presence of the pattern is performed also based on the generated information.

6. The method according to claim 3, wherein the processing elements are processing elements of a single-instruction-multiple-data type of processor.

7. The method according to claim 1, wherein the pattern corresponds to a predefined type of object (30).

8. The method according to claim 3, wherein the step of propagating the information comprises storing the information in a memory (26) accessible by the processing element (24) that is scheduled to process the respective data element to which the information is propagated.

9. The method according to claim 1,

further comprising generating information about the pattern if it is present and associating a propagation direction (67) with the generated information, where the propagation direction is chosen such that data elements along the propagation direction still have to be processed;

and

wherein the step of checking for the presence of the pattern is also based on the information propagated to the data element about patterns established elsewhere in the image.

10. The method according to claim 1, wherein the generated information and the information propagated to the data element is propagated in all directions along the image within a predetermined fan angle.

11. The method according to claim 1, wherein the propagation direction has an angle of 45 degrees or 0 degrees with at least one of the axes of the image.

12. The method according to claim 1, wherein the local feature relates to at least one of:

an edge or gradient in the image;

a spot in the image;

a local entropy of the image;

a local color of the image.

13. The method according to claim 1, further comprising

establishing an existence of an intersection point of a first propagation direction associated with a first local feature for which information was generated and a second propagation direction associated with a second feature for which information was generated, the intersection point being located outside the boundaries of the image;

and

checking for a presence of a pattern including a plurality of features based on the information about the first local feature and information about the second local feature, and outputting information about the pattern if found.

16. A computer program product comprising computer instructions for enabling a processor to execute the method according to claim 1.

14. A system for detecting a pattern in an image comprising a grid of data elements, the system comprising at least one processing element (12) for processing data elements in a predetermined order by 1) checking for a presence of a predetermined local feature at the data element and generating information about the local feature if it is present and associating a propagation direction with the generated information, where the propagation direction is chosen such that data elements along the propagation direction still have to be processed;

2) propagating the generated information and the information propagated to the data element to respective data elements closest to the data element along the respective propagation directions associated with the respective information;

     3) checking for a presence of a predetermined pattern including a plurality of features based on information propagated to the data element about local features established elsewhere in the image, and

     4) outputting information about the pattern if found.

15. The system according to claim 14, further comprising

means (16) for making the information available to the processing element (12) that is scheduled to process the respective data element to which the information is propagated.