STRUCTURED GRIDS AND GRAPH TRAVERSAL FOR IMAGE PROCESSING

• US 20110103712A1
• Filed: 01/13/2010
• Published: 05/05/2011
• Est. Priority Date: 11/03/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: SU, Bor-Yiing, BRUTCH, Tasneem G.
• Granted Patent: US 9,047,674 B2
• Time in Patent Office: Days
• US Class Current: 382/276
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

An image represented by multiple nodes can be processed by determining whether information can be propagated to a node from another node (e.g., source node) of the image, thereby allowing significantly greater parallelism and scalability by taking advantage of multiprocessing or multi-core processors that are prevalent and widely available today. Conceptually, an image can be presented as a “structured grid” of multiple nodes (e.g., a structured grid of pixels of an image). In a “structured grid,” two or more of the nodes can determine whether to propagate information in parallel. In fact, each node of a “structured grid” can perform operations relating to propagation of information in parallel. This means that for an image of N pixels, it is possible to perform N operations in parallel. It is also possible to divide the processing of N operations for N pixels substantially equally between the number processors or processing cores available at a given time.

Claims

1. In a computing system, a computer-implemented method of parallel processing an image represented by multiple nodes, by propagating information between one or more of the nodes, the computer-implemented method comprising:

(a) for each node of the image, determining whether to update the node by propagating information from its neighboring nodes to the node;

(b) for each node of the image, updating the node by propagating the information from one or more of its neighboring nodes when the determining (a) determines to update the node;

(c) determining whether any of the nodes has been updated by the updating (b); and

repeating (a), (b) and (c) wherein at least the determining (a) of whether to update the node and/or the updating (b) of the node are performed in parallel for two or more of the nodes.

2. The computer-implemented method of claim 1, wherein the nodes are effectively represented as a structured grid, wherein each node of the structured grid represents a node of the image, and wherein at least the following operations are performed on behalf or effectively by each one of the nodes in the structured grid in parallel:

the determining (a) of whether to update the node and the updating (b) of the node.

3. The computer-implemented method of claim 1, wherein one or more of the following are performed in parallel for two or more of the nodes:

the determining (a) of whether to update the information, the updating (b) of the information, and the determining (c) of whether the information of any of the nodes has been updated by the updating (b) such that the two or more of the nodes each determine whether their own information has been updated.

4. The computer-implemented method of claim 1, wherein the image is represented by a graph that includes the multiple modes and the processing of the image is for Graph Traversal of the graph.

5. The computer-implemented method of claim 4, wherein the Graph Traversal traverses the graph in accordance with Breadth First Search (BFS) ordering of the nodes.

6. The computer-implemented method of claim 5, wherein the Breadth First Search (BFS) ordering of the nodes is associated with one or more source nodes of the graph that initially have the information that can be propagated to one or more other nodes in accordance with one or more rules and/or when one or more conditions are met.

7. The computer-implemented method of claim 1,

wherein the image can be represented as a graph with multiple nodes, wherein each node of the graph corresponds to a node of a structured grid that are connected in accordance with the edges of the graph that also define neighboring nodes;

and

wherein the determining (a) of whether to update the node and the updating (b) of the information are performed in parallel for two or more of the nodes, by first and second processing cores and/or units, such that;

the first processing core and/or unit determines (a) whether to update the node of the first node by propagating information from each one of the first nodes'"'"' neighboring nodes, updates the information of the first node by propagating the information from one or more of the first nodes'"'"' neighboring nodes if the determining (a) determines to update the node, and

the second processing core and/or unit determines (a) whether to update the node of the second node by propagating information from each one of the second nodes'"'"' neighboring nodes, updates the information of the second node by propagating the information from one or more of the second nodes'"'"' neighboring nodes when the determining (a) determines to update the node.

8. The computer-implemented method of claim 1, wherein the first processing core and/or unit further determines whether information of the first node has been updated, and the second processing core and/or unit further determines whether information of the second node has been updated.

9. The computer-implemented method of claim 1, wherein each node is associated with and/or represents a pixel of the image.

10. The computer-implemented method of claim 1, wherein the information includes a label of a plurality of labels that can be propagated between the nodes.

11. The computer-implemented method of claim 1, wherein the processing of the image is for image recognition.

12. The computer-implemented method of claim 1, wherein the computer-implemented method further comprises:

repeating (a), (b) and (c) until the determining (c) determines that no node has been updated.

13. The computer-implemented method of claim 1, wherein the processing is used for one or more of the following:

edge extraction, filling a region, finding local minimums and/or maximums, boundary detection and/or erosion, distance transformation, and skeletonization.

14. The computer-implemented method of claim 1, wherein propagation of information is done in accordance with Breadth First Search (BFS).

15. The computer-implemented method of claim 1, wherein the determining (a) of whether to update information of the node by propagating information from its neighboring nodes to the node comprises:

(a1) determining whether the node has at least one neighboring node with information; and

(a2) determining, based on or more rules and/or conditions, whether to propagate information from the at least one neighboring node to the node when the determining (a1) determines that node has at least one neighboring node with information.

21. The computer-implemented method of claim 1, wherein the computer-implemented method further comprises one or more of the following:

repeating (a), (b) and (c) until a condition is satisfied; and

repeating (a), (b) and (c) for a predetermined number of iterations.

16. A computing system, wherein the computing system is operable to:

(a) for each node of the image, determining whether to update the node by propagating information from its neighboring nodes to the node;

(b) for each node of the image, updating the node by propagating the information from one or more of its neighboring nodes when the determining (a) determines to update the node;

(c) determining whether any of the nodes has been updated by the updating (b); and

repeating (a), (b) and (c) until the determining (c) determines that no node has been updated.

17. The computing system of claim 16, wherein the computing system is further operable to:

effectively represent the node as a structured grid and, and wherein at least the following operations are performed on behalf or effectively by two or more one of the nodes in the structured grid in parallel;

(a) of whether to update the node and the updating (b) of the node.

18. The computing system of claim 16, wherein the computing system is further operable to perform one or more of the following in parallel:

the determining (a) of whether to update the information, the updating (b) of the information, and the determining (c) of whether the information of any of the nodes has been updated by the updating (b) such that the two or more of the nodes each determine whether their own information has been updated.

19. A computer readable storable medium storing at least computer executable code that when executed causes a computer to perform a computer-implemented method for processing an image represented by multiple nodes, by propagating information between one or more of the nodes, where the computer-implemented method comprising:

(a) for each node of the image, determining whether to update the node by propagating information from its neighboring nodes to the node;

(b) for each node of the image, updating the node by propagating the information from one or more of its neighboring nodes when the determining (a) determines to update the node;

(c) determining whether any of the nodes has been updated by the updating (b); and

repeating (a), (b) and (c) until the determining (c) determines that no node has been updated, wherein at least the determining (a) of whether to update the node and/or the updating (b) of the node are performed in parallel for two or more of the nodes.

20. The computer readable storable medium of claim 19, wherein the computer-implemented method further comprises:

performing at least one or more of the following operations are performed in parallel for two or more of the nodes;

the determining (a) of whether to update the node and the updating (b) of the node.