ID recycle mechanism for connected component labeling

• US 10,445,883 B1
• Filed: 05/15/2017
• Issued: 10/15/2019
• Est. Priority Date: 05/15/2017
• Status: Active Grant

• Current Assignee: Ambarella International LP (Ambarella Incorporated)
• Original Assignee: Ambarella Incorporated
• Inventors: Shih, Yen-Hsu, Cheng, Chia-Hung
• Primary Examiner(s): Safaipour, Bobbak
• Application Number:
  US15/594,884
• Time in Patent Office: 883 Days
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle

Abstract

An apparatus includes a processor circuit and an ID recycle circuit. The processor circuit may be configured to generate a component table while performing connected-component labeling on a digital image. The ID recycle circuit is generally in communication with the processor circuit. The ID recycle circuit may be configured to minimize a number of entries in the component table generated by the processor circuit.

Claims

1. An apparatus comprising:

a processor circuit configured to generate a component table while performing a connected component labeling process on a digital image; and

an ID recycle circuit in communication with said processor circuit and configured to minimize a number of entries in said component table generated by said processor circuit, wherein said ID recycle circuit is configured to (i) present a recycled label value as a new ID value for a newly detected object when a label value to be recycled is available and (ii) generate a new unique label value as the new ID value for the newly detected object when no label value to be recycled is available.

2. The apparatus according to claim 1, wherein said ID recycle circuit reuses entries in said component table for different objects in said digital image.

3. The apparatus according to claim 1, wherein said ID recycle circuit is part of a coprocessor circuit associated with said processor circuit.

4. The apparatus according to claim 1, wherein said ID recycle circuit comprises:

an ID generator circuit configured to generate unique label values;

a first-in-first-out memory configured to queue label values to be recycled;

a multiplexer circuit configured to select between an output of said ID generator circuit and an output of said first-in-first-out memory for presentation as said new ID value for said newly detected object; and

a control circuit configured to control said first-in-first-out memory and said multiplexer circuit.

5. The apparatus according to claim 4, wherein said control circuit is configured such that:

when no IDs are queued for recycling, said ID recycle circuit generates a unique ID value for a newly found object; and

when at least one ID is queued for recycling said ID recycle circuit reuses the at least one queued ID for newly found objects.

6. The apparatus according to claim 4, wherein said ID generator circuit comprises:

a register configured to store a current unique label value; and

an adder circuit configured to generate an incremented version of the current unique label value, wherein the current unique label value is replaced by the incremented version of the current unique label value each time the current unique label value is consumed by the connected component labeling process.

7. The apparatus according to claim 1, wherein said ID recycle circuit is implemented solely in hardware.

8. The apparatus according to claim 1, wherein said processor circuit and said ID recycle circuit are implemented as part of an integrated circuit.

9. The apparatus according to claim 1, wherein said processor circuit and said ID recycle circuit are implemented as part of a system on chip (SoC).

10. The apparatus according to claim 1, wherein said processor circuit and said ID recycle circuit are implemented as part of a camera chip.

11. A method of connected component labeling comprising:

generating a component table while performing a connected component labeling process on a digital image; and

minimizing a number of entries in said component table by recycling ID labels no longer associated with objects in said digital image, wherein (i) when a label value to be recycled is available, the label value to be recycled is presented as a new ID value for a newly detected object, and (ii) when no label value to be recycled is available, a newly generated unique label value is presented as the new ID value for the newly detected object.

12. The method according to claim 11, further comprising:

queuing ID label values to be recycled in a first-in-first-out memory.

13. The method according to claim 12, wherein:

generating a unique ID label value for a newly found object when no ID label value to be recycled is queued in said first-in-first-out memory for recycling; and

reusing an ID label value from said first-in-first-out memory for said newly found object when at least one ID label value is queued for recycling.

14. The method according to claim 12, wherein:

said ID label values are queued for recycling when an associated object in said digital image is merged or removed from consideration as a valid object.

15. The method according to claim 14, wherein:

said associated object is removed from consideration as said valid object when said associated object does not meet predefined criteria associated with valid objects.

16. The method according to claim 15, wherein:

said predefined criteria comprise one or more of size, color, or shape.

17. The method according to claim 11, wherein said connected component labeling process and said recycling of ID labels are implemented in a computer vision system.

18. The method according to claim 11, wherein said recycling of ID labels comprises:

receiving a request from said connected component labeling process;

determining whether any ID label values are to be recycled; and

if one or more ID label values are to be recycled, pushing the one or more ID label values into a first-in first-out memory.

19. The method according to claim 18, wherein said recycling of ID labels further comprises:

determining whether a new object ID label value is requested by the connected component labeling process;

when a new object ID label value is requested, determining whether an object ID label value is queued for recycling;

if an object ID label value is queued for recycling, popping the object ID label value from the first-in first-out memory and communicating the popped object ID label value to the connected component labeling process; and

if an object ID label value is not queued for recycling, generating a new unique object ID label value and communicating the newly generated object ID label value to the connected component labeling process.

20. The method according to claim 19, wherein generating the new unique object ID label value comprises incrementing a previously generated unique object ID label value.