Structured grids and graph traversal for image processing

• US 9,047,674 B2
• Filed: 01/13/2010
• Issued: 06/02/2015
• Est. Priority Date: 11/03/2009
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Su, Bor-Yiing, Brutch, Tasneem G.
• Primary Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US12/687,013
• Publication Number:
  US 20110103712A1
• Time in Patent Office: 1,966 Days
• Field of Search: None
• US Class Current: 1/1
• 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. A method of parallel processing an image comprising a plurality of nodes, the method comprising:

(a) for each node of said image, determining whether to update said node based on propagation information from one or more neighboring nodes, wherein determining whether to update said node comprises verifying whether information can be propagated to said node from said one or more neighboring nodes based on one or more rules relating to balancing work load for a structure grid nodes;

(b) for each node of said image to update, updating said node by determining an order of information propagation, and propagating information from one or more neighboring nodes to said node in said determined order of information propagation;

(c) determining whether any of said plurality of nodes has been updated; and

(d) repeating (a), (b) and (c);

wherein at least one of (a) and (b) is performed in parallel for two or more of said plurality of nodes.

2. The method of claim 1, wherein:

each node repeatedly determines whether to update said node until (c) determines that no node has been updated;

said plurality of nodes are represented as a structured grid of nodes, wherein each node of said structured grid corresponds to a node of said image;

at least one of the following is performed in parallel for each node of said structured grid;

(a) and (b).

3. The method of claim 1, wherein:

at least one of (a), (b) and (c) is performed in parallel for two or more of said plurality of nodes.

4. The method of claim 1, wherein:

said image is represented by a graph that includes said plurality of nodes; and

said processing of said image is for Graph Traversal of said graph.

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

6. The method of claim 5, wherein:

said Breadth First Search (BFS) ordering of said plurality of nodes is associated with one or more source nodes of said graph, wherein each source node has information that is propagated to at least one node based on one or more rules or one or more conditions.

7. The method of claim 1, wherein:

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

(a) and (b) are performed in parallel for a first node and a second node by a first processing core unit and a second processing core unit, respectively, wherein;

said first processing core unit determines whether to update said first node, and updates said first node by propagating information from one or more neighboring nodes to said first node if an update for said first node is determined; and

said second processing core unit determines whether to update said second node, and updates said second node by propagating information from one or more neighboring nodes to said second node if an update for said second node is determined.

8. The method of claim 1, wherein:

said first processing core unit further determines whether information for said first node has been updated; and

said second processing core unit further determines whether information for said second node has been updated.

9. The method of claim 1, wherein each node corresponds to a pixel of said image.

10. The method of claim 1, wherein said information propagating between said plurality of nodes comprises at least one label.

11. The method of claim 1, wherein said processing of said image is for image recognition.

12. The method of claim 1, wherein (a), (b) and (c) are repeated until (c) determines that none of said plurality of nodes has been updated.

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

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

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

15. The method of claim 1, wherein (a) further comprises:

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

(a2) if said node has at least one neighboring node with information, determining, based on one or more rules or conditions, whether to propagate information from said at least one neighboring node to said node.

16. The 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.

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

(a) for each node of an image, determine whether to update said node by based on propagation information from one or more neighboring nodes, wherein determining whether to update said node comprises verifying whether information can be propagated to said node from said one or more neighboring nodes based on one or more rules relating to balancing work load for a structure grid node;

(b) for each node of said image to update, update said node by determining an order of information propagation, and propagating said information from one or more neighboring nodes to said node in said determined order of information propagation;

(c) determine whether any node has been updated; and

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

18. The computing system of claim 17, wherein said computing system is further operable to:

represent said image as a structured grid of nodes, wherein each node of said structured grid corresponds to a node of said image;

wherein at least one of the following is performed in parallel for each node of said structured grid;

(a) and (b); and

wherein each node repeatedly determines whether to update said node until (c) determines that no node has been updated.

19. The computing system of claim 17, wherein said computing system is further operable to perform at least one of (a), (b) and (c) in parallel for two or more of nodes of said image.

20. A non-transitory 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 comprising a plurality of nodes, the computer-implemented method comprising:

(a) for each node of said image, determining whether to update said node based on propagation information from one or more neighboring nodes, wherein determining whether to update said node comprises verifying whether information can be propagated to said node from said one or more neighboring nodes based on one or more rules relating to balancing work load for a structure grid node;

(b) for each node of said image to update, updating said node by determining an order of information propagation, and propagating information from one or more neighboring nodes to said node in said determined order of information propagation;

(c) determining whether any of said plurality of nodes has been updated; and

(d) repeating (a), (b) and (c) until (c) determines that no node has been updated;

wherein at least one of (a) and (b) is performed in parallel for two or more of said plurality of nodes.

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

performing at least one of (a), (b) and (c) in parallel for two or more of said plurality of nodes;

wherein said plurality of nodes are represented as a structured grid of nodes, wherein each node of said structured grid corresponds to a node of said image;

wherein each node repeatedly determines whether to update said node until (c) determines that no node has been updated.