Parallel flood-fill techniques and architecture

Patent metadata

Field	Value
Publication number	US-9972062-B2
Application number	US-201414550214-A
Country	US
Kind code	B2
Filing date	Nov 21, 2014
Priority date	Oct 15, 2012
Publication date	May 15, 2018
Grant date	May 15, 2018

Abstract

Flood-fill techniques and architecture are disclosed. In accordance with one embodiment, the architecture comprises a hardware primitive with a software interface which collectively allow for both data-based and task-based parallelism in executing a flood-fill process. The hardware primitive is defined to do the flood-fill function and is scalable and may be implemented with a bitwise definition that can be tuned to meet power/performance targets, in some embodiments. In executing a flood-fill operation, and in accordance with an example embodiment, the software interface produces parallel threads and issues them to processing elements, such that each of the threads can run independently until done. Each processing element in turn accesses a flood-fill hardware primitive, each of which is configured to flood a seed inside an N×M image block. In some cases, processing element commands to the flood-fill hardware primitive(s) can be queued and acted upon pursuant to an arbitration scheme.

First claim

What is claimed is:

1. A flood-fill device, comprising:
a flood-fill hardware primitive configured to receive and update an input flood map for a given image block to be flood-fill processed to include final pixel positions to be flooded thereby providing an updated flood map, wherein each of the input flood map and the updated flood map comprises a bit map representing which pixels of the image block are to be flooded and which pixels are not to be flooded, and the flood-fill hardware primitive is implemented with a bitwise definition; and
a processing element configured to execute a flood fill routine in accordance with the updated flood map.

2. The device of claim 1 wherein the processing element is one of multiple processing elements, the device further comprising:
an arbiter operatively coupled between the processing elements and the flood-fill hardware primitive, so that processing element commands to the flood-fill hardware primitive can be acted upon pursuant to an arbitration scheme.

3. The device of claim 2 wherein the device further includes multiple flood-fill hardware primitives which are used in accordance with the arbitration scheme.

4. The device of claim 1 wherein the input flood map further indicates surrounding pixels of the image block which represent connectivity to the image block.

5. The device of claim 1 wherein the device is configured to initially flood-fill an image block that includes a seed node, and to subsequently flood-fill neighbor image blocks of that seed node image block.

6. The device of claim 1 further comprising a software interface configured to at least one of direct the processing element to issue the input flood map, and produce parallel threads and issue each one to one of multiple processing elements such that each thread can run independently until done.

7. The device of claim 1 wherein the bitwise definition is tuned to meet at least one of power and processor cycle performance targets.

8. The device of claim 1 wherein the processing element is configured to early exit the flood fill routine if all connection points of the given image block are reset or if its updated flood map is completely reset.

9. The device of claim 1 wherein the flood-fill hardware primitive is configured to early exit flood map updating if it detects that flooding will make no change.

10. A flood-fill system, comprising:
a plurality of processing elements each configured to execute a flood fill routine in accordance with a corresponding input flood map for a given image block to be flood-fill processed; and
a plurality of flood-fill hardware primitives, each configured to update one of the input flood maps to include final pixel positions to be flooded thereby providing an updated flood map, and to provide the updated flood map back to that processing element;
wherein at least one of the input flood maps and a corresponding one of the updated flood maps each indicates pixels in a corresponding image block that can accept a flooded value and pixels that cannot accept a flooded value, and at least one of the flood-fill hardware primitives is implemented with a bitwise definition.

11. The system of claim 10 further comprising:
an arbiter operatively coupled between the processing elements and the flood-fill hardware primitives, so that processing element commands to the flood-fill hardware primitives can be acted upon pursuant to an arbitration scheme.

12. The system of claim 10 wherein the at least one input flood map and the corresponding updated flood map each further indicates surrounding pixels of that corresponding image block which represent connectivity to that corresponding image block.

13. The system of claim 10 wherein the system is configured to initially flood-fill a given image block that includes a seed node, and to subsequently flood-fill neighbor image blocks of that seed node image block.

14. The system of claim 10 wherein:
at least one of the processing elements is configured to early exit flood-fill processing a given image block if all connection points of that image block are reset or if its updated flood map is completely reset; and
at least one of the flood-fill hardware primitives is configured to early exit flood map updating if it detects that flooding will make no change.

15. A flood-fill method, comprising:
updating, via a flood-fill hardware primitive, an input flood map for a given image block to be flood-fill processed to include final pixel positions to be flooded, thereby providing an updated flood map; and
providing the updated flood map back to a processing element configured to execute a flood fill routine in accordance with the updated flood map;
wherein each of the input flood map and the updated flood map comprises a bit map representing which pixels of the image block are to be flooded and which pixels are not to be flooded, and the flood-fill hardware primitive updates the input flood map in accordance with a bitwise definition.

16. The method of claim 15 further comprising at least one of:
early exiting flood-fill processing the given image block if all connection points of that image block are reset or if its updated flood map is completely reset; and
early exiting the updating if flooding will make no change.

17. A graphics card comprising the device of claim 1 .

18. A media processing system comprising the device of claim 1 .

19. A mobile computing system comprising the device of claim 1 .

Assignees

• Intel Corp

Inventors

• Gluska Alon
• Gupta Niraj
• Hagog Mostafa
• Reif Dror

Classifications

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title