ID recycle mechanism for connected component labeling

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.

The invention claimed is: 
     
       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.