CN111801703A - Hardware and systems for bounding box generation in image processing pipelines - Google Patents

Abstract

A system for bounding box generation is described. The system operates on images composed of multiple pixels each having a one-bit value. The bounding box is generated around the connected components in the image, which have pixel coordinates and pixel count information. Based on pixel coordinates and pixel count information, a ranking score is generated for each bounding box. Filter bounding boxes based on pixel coordinates and pixel count information to remove bounding boxes that exceed a predetermined size and a predetermined pixel count. The bounding boxes are also filtered to remove bounding boxes below a predetermined ranking score, resulting in the remaining bounding boxes. Finally, the device may be controlled or otherwise operated based on the remaining bounding box.

Description

Hardware and systems for bounding box generation in image processing pipelines

government interest

The present invention is made in a paper entitled "Revolutionary AnalogProbabilistic Inference Devices for Unconventional Processing of Signals for Data Exploitation" (RAPID- UPSIDE) with government support under a U.S. government contract. The government has certain rights in this invention.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation-in-part of US Application No. 15/272,247, filed on September 21, 2016, which is a non-individual continuation of US Provisional Application No. 62/221,550, filed on September 21, 2015 Provisional application, the entire contents of which are incorporated herein by reference.

US Application No. 15/272,247 is a continuation-in-part of US Application No. 15/079,899, filed March 24, 2016, which is US Provisional Application No. 15/079,899, filed March 24, 2015. Non-provisional application 62/137,665, the entire contents of which are incorporated herein by reference. US Application No. 15/079,899 is also a non-provisional application of US Provisional Application No. 62/155,355, filed April 30, 2015, the entire contents of which are incorporated herein by reference.

US Application No. 15/272,247 is also a continuation-in-part of US Application No. 15/043,478, filed February 12, 2016, the entire contents of which are incorporated herein by reference.

US Application No. 15/272,247 is also a continuation-in-part of US Application No. 15/203,596, filed July 6, 2016, which is US Provisional Application No. 15/203,596, filed September 21, 2015. 62/221,550 for non-provisional applications.

This application also claims the benefit of non-provisional patent application US. 62/659,129, filed April 17, 2018, the entire contents of which are incorporated herein by reference.

Background of the Invention

(1) Technical field

The present invention relates to an image processing system, and more particularly, to a system for generating bounding boxes in an image for image processing.

(2) Description of related technologies

Image processing is used in a variety of implementations (including tracking and monitoring applications). In tracking or monitoring, bounding boxes are used to identify an object and, ideally, to track that object across image frames and scenes. A bounding box can be formed by setting boxes for connected components. For example, the work of Walczyk et al. describes performing connected component labeling of binary images (see "Comparative Study on Connected Components Labeling Algorithms for Embedded Video Processing Systems" by Robert Walczyk, Alistair Armitage, and TD Binnie A Comparative Study of Labeling Algorithms)", Proceedings of the 2010 International Congress on Image Processing, Computer Vision and Pattern Recognition (IPCV) (CSREA, 2010, the entire contents of which are hereby incorporated by reference). Although Walczyk et al. disclose performing connected component labeling, this disclosure is only for labeling of images, and fails to further efficiently process boxes or images.

Therefore, there is still a need to generate bounding boxes while efficiently computing bounding box coordinates and bounding box object pixel counts for subsequent sorting and filtering of object boxes for image processing.

SUMMARY OF THE INVENTION

The present disclosure provides a system for bounding box generation. In various aspects, the system includes a memory and one or more processors. The memory has executable instructions such that when the instructions are executed, the one or more processors perform operations, such as receiving an image consisting of a plurality of pixels having a value of one bit per pixel generating a bounding box around the connected components in the image, the connected components having pixel coordinates and pixel count information; based on the pixel coordinates and the pixel count information, generate a ranking score for each bounding box; based on the pixel coordinates and the pixel count information, filtering the bounding boxes to remove bounding boxes exceeding a predetermined size and a predetermined pixel count; and filtering the bounding boxes to remove bounding boxes below a predetermined ranking score, resulting in the remaining bounds box; and control the device based on the remaining bounding box.

In another aspect, the processor is a field programmable gate array (FPGA).

In yet another aspect, generating the bounding box further comprises the operations of: grouping consecutive pixels in the image; and merging connected pixels into connected components, wherein the bounding box is formed by boxes surrounding the connected components .

Additionally, controlling the apparatus includes moving a video stage to maintain at least one remaining bounding box of the remaining bounding boxes within a field of view of the video stage.

Finally, the present invention also includes computer program products and computer-implemented methods. The computer program product includes computer readable instructions stored on a non-transitory computer readable medium, the computer readable instructions being executable by a computer having one or more processors such that when executed, the instructions, The one or more processors perform the operations listed herein. Alternatively, a computer-implemented method includes acts of causing a computer to execute such instructions and perform the resulting operations.

Description of drawings

Objects, features, and advantages of the present invention will become apparent from the following detailed description of various aspects of the invention, taken in conjunction with the accompanying drawings, wherein:

1 is a block diagram illustrating components of a system according to various embodiments of the present invention;

2 is a diagram of a computer program product embodying an aspect of the present invention;

3 is a flowchart illustrating the relationship between variables and arrays during preparation according to various embodiments of the present invention;

4 is a diagram of a search block for finding pixel label values, according to various embodiments of the present invention;

FIG. 5 is a flowchart illustrating a search/marking process according to various embodiments of the present invention;

Figure 6A is a diagram showing a portion of an image and corresponding indicia according to various embodiments of the present invention;

Figure 6B is a diagram showing a partial image and corresponding indicia according to various embodiments of the present invention;

Figure 6C is a diagram of the complete image and corresponding indicia as partially shown in Figures 6A and 6B, according to various embodiments of the present invention;

7 is a flowchart illustrating a merged region according to various embodiments of the present invention;

8 is a flowchart illustrating state transitions according to various embodiments of the present invention;

9A is a flow diagram illustrating State 1 according to various embodiments of the present invention;

9B is an example of a state 2 code according to various embodiments of the present invention;

10 is a flowchart illustrating an incrementer according to various embodiments of the present invention;

FIG. 11 is a flowchart illustrating state 2 according to various embodiments of the present invention;

12 is a diagram of a current tagging module according to various embodiments of the present invention;

Figure 13 is a flowchart illustrating state 3 according to various embodiments of the present invention;

Figure 14 is a flowchart illustrating State 4, State 5, and State 6 according to various embodiments of the present invention;

Figure 15 is a flowchart illustrating state 7 and callback operations according to various embodiments of the present invention;

Figure 16 is a flow diagram illustrating state 7 and sorting operations in accordance with various embodiments of the present invention;

Figure 17 is a flow diagram illustrating state 7 and sorting operations and sorting modules in accordance with various embodiments of the present invention;

18 is a diagram illustrating an example input image with each pixel location having a one-bit value in accordance with various embodiments of the present invention;

FIG. 19 is a diagram showing an image with a resulting bounding box after bounding box processing and filtering in accordance with various embodiments of the present invention; and

FIG. 20 is a block diagram illustrating control of a device according to various embodiments.

Detailed ways

The present invention relates to an image processing system, and more particularly, to a system for generating bounding boxes in an image for image processing. The following description is presented to enable any person of ordinary skill in the art to make and use the invention and to incorporate it in the context of a particular application. Numerous modifications and various uses in different applications will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied in a wide variety of aspects. Thus, the present invention is not intended to be limited to the various aspects presented but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

In the following detailed description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced without being limited to these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order not to obscure the present invention.

The reader is reminded to take note of all files and documents filed concurrently with this specification, which are made available for public inspection with this specification, and the contents of all such files and documents are incorporated herein by reference. All features disclosed in this specification (including any accompanying claims, abstract and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is only one example of a typical series of equivalent or similar features.

Furthermore, no element of a claim that does not expressly recite "means" for performing the specified function or "step" for performing the specified function shall be construed as "means" specified in 35 U.S.C. § 112, subsection 6 ” or “steps” clause. Specifically, the use of "the step of" or "the act of" in the claims herein is not intended to invoke the provisions of 35 U.S.C. § 112, paragraph 6.

Before describing the invention in detail, a description of various major aspects of the invention is first provided. The introductory section then provides the reader with a general understanding of the invention. Finally, specific details of various embodiments of the invention are provided in order to provide an understanding of specific aspects.

(1) Main aspects

Various embodiments of the invention include three "main" aspects. A first aspect is a system for image processing. The system typically takes the form of computer system operating software or in the form of a "hard-coded" instruction set or as a Field Programmable Gate Array (FPGA). The system can be incorporated into a wide variety of devices providing different functions. The second major aspect is a method, usually in the form of software, run using a data processing system (computer). The third major aspect is the computer program product. The computer program product generally represents a computer stored on a non-transitory computer-readable medium such as an optical storage device (eg, a compact disc (CD) or digital versatile disc (DVD)) or a magnetic storage device (eg, a floppy disk or magnetic tape) Readable instructions. Other non-limiting examples of computer readable media include hard disks, read only memory (ROM), and flash-type memory. These aspects will be explained in more detail below.

1 provides a block diagram illustrating an example of a system of the present invention (ie, computer system 100). Computer system 100 is configured to perform calculations, processes, operations and/or functions associated with programs or algorithms. In one aspect, certain processes and steps discussed herein are implemented as a series of instructions (eg, software programs) residing within a computer-readable memory unit and executed by one or more processors of computer system 100 . When executed, these instructions cause computer system 100 to perform particular actions and exhibit particular behaviors, such as described herein.

Computer system 100 may include an address/data bus 102 configured to communicate information. Additionally, one or more data processing units, such as processor 104 (or processors), are coupled with address/data bus 102 . The processor 104 is configured to process information and instructions. In one aspect, the processor 104 is a microprocessor. Alternatively, the processor 104 may be a different type of processor, such as a parallel processor, an application specific integrated circuit (ASIC), a programmable logic array (PLA), a complex programmable logic device (CPLD), or a field programmable gate array ( FPGA) configured to perform the operations described herein.

Computer system 100 is configured to utilize one or more data storage units. Computer system 100 may include a volatile memory unit 106 (eg, random access memory ("RAM"), static RAM, dynamic RAM, etc.) coupled to address/data bus 102, wherein volatile memory unit 106 is configured The components store information and instructions for the processor 104 . Computer system 100 may also include a non-volatile memory unit 108 (eg, read only memory ("ROM"), programmable ROM ("PROM"), erasable programmable ROM ("ROM"), coupled to address/data bus 102. EPROM”), electrically erasable programmable ROM (“EEPROM”), flash memory, etc.), wherein the non-volatile memory unit 108 is configured to store static information and instructions for the processor 104. Alternatively, computer system 100 may execute instructions such as fetched from an online data storage unit in "cloud" computing. In one aspect, computer system 100 may also include one or more interfaces (such as interface 110 ) coupled to address/data bus 102 . The one or more interfaces are configured to enable the computer system 100 to interface with other electronic devices and computer systems. Communication interfaces implemented by the one or more interfaces may include wired communication technologies (eg, serial cables, modems, network adapters, etc.) and/or wireless communication technologies (eg, wireless modems, wireless network adapters, etc.).

In one aspect, computer system 100 may include input device 112 coupled to address/data bus 102 , wherein input device 112 is configured to communicate information and command selections to processor 100 . According to one aspect, input device 112 is an alphanumeric input device (such as a keyboard) that may include alphanumeric keys and/or function keys. Alternatively, input device 112 may be an input device other than an alphanumeric input device. In one aspect, computer system 100 may include cursor control device 114 coupled to address/data bus 102 , wherein cursor control device 114 is configured to communicate user input information and/or command selections to processor 100 . In one aspect, cursor control device 114 is implemented using a device such as a mouse, trackball, trackpad, optical tracking device, or touchscreen. Nonetheless, in one aspect, cursor control device 114 is directed and/or activated via input from input device 112 , such as in response to commands using special keys and key sequences associated with input device 112 . In an alternative aspect, the cursor control device 114 is configured to be guided or guided by voice commands.

In one aspect, computer system 100 may also include one or more optional computer-usable data storage devices (such as storage device 116 ) coupled with address/data bus 102 . Storage device 116 is configured to store information and/or computer-executable instructions. In one aspect, storage device 116 is a storage device such as a magnetic or optical disk drive (eg, hard disk drive ("HDD"), floppy disk, compact disk read only memory ("CD-ROM"), digital versatile disk ("DVD")) equipment. According to one aspect, a display device 118 is coupled to the address/data bus 102, wherein the display device 118 is configured to display video and/or graphics. In one aspect, display device 118 may include a cathode ray tube ("CRT"), a liquid crystal display ("LCD"), a field emission display ("FED"), a plasma display, or suitable for displaying video and/or graphic images and Any other display device with alphanumeric characters recognizable to the user.

The computer system 100 presented herein is an example computing environment according to one aspect. However, the non-limiting example of computer system 100 is not strictly limited to being a computer system. For example, one aspect specifies that computer system 100 represents a data processing analysis that may be used in accordance with various aspects described herein. In addition, other computing systems may also be implemented. Indeed, the spirit and scope of the present technology is not limited to any single data processing environment. Thus, in one aspect, computer-executable instructions, such as program modules, executed by a computer are used to control or implement one or more operations of various aspects of the present technology. In one implementation, such program modules include routines, programs, objects, components, and/or data structures configured to perform particular tasks or implement particular abstract data types. Additionally, one aspect provides for implementing one or more aspects of the technology by utilizing one or more distributed computing environments, such as where tasks are performed by remote processing devices that are linked through a communications network, Alternatively, such as in a distributed computing environment, various program modules are located in both local and remote computer storage media including memory-storage devices.

Figure 2 shows a diagram of a computer program product (ie, a storage device) embodying the present invention. The computer program product is shown as a floppy disk 200 or an optical disk 202 such as a CD or DVD. However, as previously mentioned, a computer program product generally represents computer readable instructions stored on any compatible non-transitory computer readable medium. The term "instructions" as used in connection with the present invention generally refers to a set of operations to be performed on a computer, and may represent a fragment of an entire program or a single separable software module. Non-limiting examples of "instructions" include computer program code (source code or object code) and "hard-coded" electronics (ie, computer operations coded into a computer chip). "Instructions" are stored on any non-transitory computer-readable medium, such as in a computer's memory or on floppy disks, CD-ROMs, and flash drives. In either case, the instructions are encoded on a non-transitory computer-readable medium.

(2) Introduction

The present disclosure provides a system and corresponding hardware implementation for bounding box generation of an image processing pipeline. In various aspects, the system is implemented on a field programmable gate array (FPGA) that receives a binary image, detects object pixels from the binary image, and generates bounding boxes around connected components. The system implements a connected component labeling method for grouping consecutive pixels found throughout an image, and then combining connected pixels to create a unique boxed location. These unique boxes are saved as individual cells that contain bounding box coordinates and counts of contained object pixels. The system also calculates a ranking score based on the height and width of the bounding box and the number of contained object pixels, which is used for subsequent filtering of objects based on size and aspect ratio. The processing is designed to provide this bounding box information while minimizing FPGA resources and achieving sufficient throughput to keep up with the desired input image frame rate (eg, 30 frames per second).

When performing connected component labeling of binary images, the system also simultaneously records bounding box coordinates and the number of object pixels detected for each bounding box. This additional information is used for subsequent sorting and filtering of objects based on size and aspect ratio, and can be collected without significant additional computational time and hardware resources. Additionally, the design of the present invention is optimized to minimize both FPGA utilization and computation time. The advantages allow the present invention to be used as a small size, light weight and low power (SWAP) image processing pipeline (such as in US Application No. 15/272,247) operating at high image frame rates (eg, >30 frames per second). as described in ). The use of the process of the present disclosure will better simplify the image processing pipeline by reducing the necessary computations on the detected specific object over the entire image.

The systems and processes described herein can be implemented as key components of a low SWAP image processing pipeline. Furthermore, the systems and processes can be applied to a variety of implementations including unmanned autonomous vehicles and platforms with severely limited SWAP. By rapidly detecting mission-related targets and obstacles on hardware near the sensor, the present invention can improve mission responsiveness and reduce the amount of raw sensor data that must be transmitted over constrained communication bandwidth. Furthermore, the systems and processes can be used for both active safety and autonomous driving applications. By performing object detection in low-power, low-cost hardware close to the camera, cars can more quickly and robustly detect obstacles on the road, providing more timely warnings to drivers or in autonomous vehicles Faster automatic response to obstacles. Additional details are provided below.

(3) Specific details of each embodiment

(3.1) Introduction to bounding boxes

A bounding box is a method by which the system accepts, as an input image, a matrix of single-bit data, which the system uses as the basis for creating an array of boxes. Each "box" will contain the coordinates of the two x positions, the two y positions, and the effective pixel count. As an example, a set of box data from a bounding box array would contain x-position (Xmin=100, Xmax=150) and y-position (Ymin=80, Ymax=90), where pixel count=70. This would be a "box" 10 pixels high and 50 pixels wide containing 70 effective pixels. Put other sets of pixels into boxes and assign their respective x-position, y-position, and valid pixel count. What separates the boxes is the proximity and separation of valid pixels. This difference is further described below with respect to software implementation and hardware implementation, respectively.

(3.2) Software bounding box design in Matlab

Bounding box processing can be implemented using any suitable software product. As an example, the bounding box is implemented in Matlab. Software-based bounding box design can be defined into 3 different parts: preparation, search/marking, and merge area. The various parts will later be converted to be implemented on the hardware design.

(3.2.1) Preparation

Preparation processing is the simple instantiation and initialization of variables and arrays to their default values. The variables initialized will be the region count, previous y position and current y position. The initialized arrays will be "Image", "Labeled Image", "Merge to Region" and "Bounding Box Data". The area count will be used as the "ticket" value for the found marked pixels. The previous/current Y position is used as a reference to reduce the size of the marker image matrix. The reduced overall marker image size allows digital circuits to use fewer hardware resources when implementing the bounding box method in such circuits. Since the tagging algorithm search mode uses the previous position, the size of the width and height must be increased by 2 by placing extra blank pixels around the image to accommodate the larger image size. The height of the marker image is 2 and the width is set to the image width. Merge into regions is a collection of single-dimensional arrays of length counted for the maximum region, which is a collection limited to how many tokens are distributed at the maximum expected. This limit is to reflect the limited resources used during digital implementation. The Bounding Box Data is two-dimensional and has a width of 5 copies: two x positions, two y positions, and a count of valid pixels. The bounding box data height is set to the maximum area count.

For example, FIG. 3 shows the relationship between various matrices and variables during instantiation of their preparation process. Now that the variable has been created, it must be initialized to the correct starting value. For example, the system initiates an array 316 of a multi-dimensional image (ie, size) plus pixel boundaries (ie, blank pixels that fill multiple dimensions) to form image 318 . All values merged into both the region 300 and the marker image 302 have been initialized to the maximum region count 304 . The marker image 302 continues to change 312 the value so that Y _Previous is set to 0 and Y _Current is set to 1. The minimum x and minimum y values 314 of the bounding box data 306 are sent to the maximum size 308 for image width and image height, respectively. Y was _previously set to 1, and Y _{is currently} set to 2. Therefore, the values in the above matrix are initialized to non-zero values. The last thing initialized is the Region Count 310 which is set to 0. This will keep track of how many tokens are generated and will prevent processing exceeding the maximum array size.

(3.2.2) Search/Mark

After the preparation process, the system continues with the search/mark process, as shown in Figure 5. As the title says, the system will search the image and mark the pixels found (from top to bottom of the image, or any other predetermined order). A pixel is a binary number in the range of 0 or 1, so a "found" pixel is a pixel with a value. Figure 4 shows an example of how the search is performed. Using the current pixel position in the image as (X,Y), the system first checks to see if (X,Y) has a valid pixel. If so, the system proceeds to check whether (X-1,Y-1), (X,Y-1), (X+1,Y-1) and/or (X-1,Y) have been marked. As shown in Figure 5, the process continues until the image has been searched through 500 (eg, to its bottom or top, etc.), at which point the search/marking is complete 502. Alternatively, assume that this is the first pixel found; therefore, there are currently no locations with markers (eg, the image has not been read to its edge 504 and there is a valid pixel 506 at (x,y) and no adjacent Pixels have been marked 508). If this is the case, the pixel should be marked 508 with a region count of 1 and the region count 510 incremented. Using the region count, the system indexes the bounding box data array storing the pixel count to a value of 1, and uses the current x position, current y position to store its min/max values. Since the size of the found box is only one pixel, the maximum and minimum values for the x and y positions will be equal. Now, assume that the next pixel is also valid. This creates conditions where (X-1,Y-1), (X,Y-1), (X+1,Y-1) and/or (X-1,Y) have been flagged. The system then compares the labels of the various neighbors to find the lowest label position and calls it the "Current Label" 512 . To this end, the process uses the previous Y and the current Y to index the label image; however, (X-1), (X), (X+1) are used along another dimension (ie, along the x dimension instead of the y dimension) )move. It comes to mind that, in this example, by making (X-1, Y _current ) a minimum value of "1", the marker image array is loaded with the maximum value for that region. Then, assign the value "1" to the flag for that pixel. After completing the evaluation of a pixel location, the system implements block 526 and increments the "X" index to move closer to the edge of the image. Additionally, after reaching the edge of the image as shown in block 504, the system begins to implement block 524, which will increase the "Y" dimension and swap the Y _current value and the Y _previous value. Remember that Y _current and Y _previous are used to hold small arrays of marker images, so swapping Y _current and Y _previous will hold the data needed for the next evaluation, while opening a new collection that will be overwritten.

The process then continues to determine if the bounding box data has been updated by comparing the new data "(X,Y)" with the stored maximum/minimum X and Y values. If the stored max/min X and Y values are smaller/greater than the new data, the system will update the bounding box data with the new X and Y positions. Using the above example, the system must update 514 some values in the bounding box data by increasing Xmax, because connected pixels will increase the box size by 1 in the x direction, and the pixel count will increase by 1.

After updating the bounding box data, take care to merge invisible pixels later, as processing may not have a chance to relabel these pixels in the current scan. This concept becomes more meaningful in the context of more complex examples, as described below. To record the merge, first consider identifying 516 which neighbors have valid pixels. Any neighbors with valid pixels will be checked against the current marker to merge into the region position 518 to find the smallest marker. Then, the smallest of the two is stored back to its same merged-region location 520 . In this example, the search ends by indexing the merged region with the marker pair of the previous pixel position and then storing the value of the current marker. Finally, if the current pixel is invalid 522, the marker image array is _currently indexed by y, and x is set to the maximum value for region count + 1.

(3.2.3) Merge area

To understand merge region processing, it is helpful to see and understand the more complex "search/mark" example. For example, assume that the system is processing an image as shown in Figure 6C. Assuming the system is scanning the pixel image shown in Figure 6C, the system will gradually "see" the image from Figures 6A to 6B to 6C. Note that in Figures 6A and 6B, the images contain separate components during scanning, so that one would not know that the two separate components are connected. In this case, assume, as an example, that the left side has marker 1 and the right side has marker 2. Only when a pixel is bridged between two sides is it known that the two sides are part of the same image and should be labeled accordingly; however, the system/processing cannot change the information found in label 2 because the components are not known at this point Whether it is connected or not, it is not known how many components are connected. To solve this problem, merge into the region array by setting position 2 with a value of 1. Later, this change will be used to convert all marker positions that will be 2 to marker positions of 1.

In the full image and as shown in Figure 6C, line 600 may be used to cut or otherwise divide the image, showing that in this example, A and C would contain all those components marked as 1s. B will contain all those components that are labeled 2 and are still labeled 2 in this example. D will contain all those components that should have been marked 2 but are now marked 1 instead.

The final step is the merged region processing, as shown in Figure 7. In this step, update reminders found in the Merge into Regions array are set in the appropriate bounding box. Before the section starts, create a new array of 700 that will keep track of valid bounding box data. The valid data array will start with items that are "true" up to the region count and any of the above items that are "false" reaching the maximum region count (having the same length as the bounding box data). The stored bounding box data values can be merged into a central location, invalidating one or more sets of data. Since markers are known to be assigned from decimal to large, the system starts by counting down to 1 in a for loop by tracing back the bounding box data from the current region count (previously used to count how many markers were assigned). A for loop is a process that repeats in a loop until completion. Different types of these loops exist, but usually a for loop performs some action until an end condition is reached. Usually in a loop, either count down or count up to reach a condition that ends processing and exits the loop.

The necessity of an update is determined by looking at the current index of the for loop and comparing it to the merged into area 702 indexed by the same value. If a connection to a different smaller marker is found sometime during the search/mark phase, the merged into region 702 array should be updated 704 to a lower value than the index. If this never happened, then the merge into the region would naturally have a larger number from the original preparation stage. Therefore, if the index of the for loop is greater than the information stored in the merged region with that same index, the system needs to update 706 the bounding box data to include the newly found information. The bounding box data will contain Xmin, Ymin, Xmax, Ymax, and pixel count information; therefore, to update 706, the process continues to look at the bounding box data in both index locations (ie, (1) the bounding box data for the current index and ( 2) Store the bounding box data of the value merged into the region with that same index). Use both positions; compare the min to see which has a smaller value, compare the max to see which has a larger value, and combine the pixel count values. The information is then stored back into the bounding box data indexed by the merge-to-region value indexed by the for loop that will contain the lower marker. Once the array reaches this lower index 708, the bounding box data is fully updated at that location with most of the current information about the minimum count, maximum count, and pixel count. This process is repeated until the region count is one 710, which is the lowest mark, and it is impossible for another location to merge into it. At this point, the merge area process terminates 712 . The output will now be a value stored as bounding box data along with a validation array that identifies which parts of the bounding box data contain boxes with regions that are not merged or have the latest merged information.

(3.3) Hardware bounding box implementation

As mentioned above, the present disclosure also provides a digital hardware implementation for generating bounding boxes. Creating a digital hardware implementation requires reducing the bounding box to some known range of values. For illustration purposes, the implementation is described with respect to an image that is 512 pixels wide and 256 pixels long, where each pixel contains a one-bit value. The design will be controlled from an external module such that the bounding box module will receive the enable signal and needs to allow the necessary image positions to be indexed upon request. To meet other specifications for image processing design, additional filtering is implemented and the provided results are reduced to the top 15 sorted boxes. All bounding boxes are found and stored in memory; however, the module will specifically provide 15 bounding boxes, ordered in a manner discussed in further detail below.

Just like in software design, hardware can be generalized into three phases, namely, prepare, search/mark, and merge regions. However, in this hardware implementation, there is an additional stage called callback and ordering. The translation in hardware also requires the function to complete on a specific clock cycle. In this case, the algorithm has been decomposed into different states. Additionally, to reduce the hardware burden of using many flip-flops, a large bounding box array is stored in block random access memory (BRAM). A flip-flop is a type of register that stores bits. This flip-flop can be found in the construction of the FPGA, and to reduce the amount of data needed to store the creation, the flip-flop can be placed in BRAM (another component in the FPGA). This further requires decomposing the algorithm into multiple states, some of which are used to hide indexes and receive information from BRAM.

(3.3.1) Preparation

The hardware preparation part translates to the instantiation and some initialization of the variables needed in the algorithm. As discussed earlier and shown in Figure 8, hardware limitations dictate the size of the tag variable. This process is illustrated in Figure 8, where some boxes represent arrays 800 and the remaining boxes represent values. The maximum limit is the number of tokens that can be provided. In one example, the number of tokens is reduced to 256, which in turn will set the range of many arrays. As previously described, for input image 801 to include marker image array 802, in this example, input image 801 would have a height of 255 dimensions and a width of 511 (the width of the image) (dimensions). The included data will have a maximum region count of 804 of 255, which means that 8 bits in size can represent these ranges. The width merged into region 806 will be 256, where the value is as large as 255 (which means 8 bits in size). As a rule of thumb, any item for width will be as large as 511 (requires 9 bits) and height will be as large as 255 (requires 8 bits). Pixels rendered for use have a width of 1 bit. Since the size of BRAM 808 is as long as the maximum mark (which is 256), the width of the write and read addresses will be 8 bits. The BRAM will contain all the information 810 from the bounding box BRAM array 808 . As in the software case described above, the included information 810 would be that of Xmax, Ymax, Xmin, Ymin and pixel count. However, in addition to this, the hardware implementation also includes Xsize and Ysize, which are simple (Xmax-Xmin or Ymax-Ymin) calculations.

Just like in software, all variables must be initialized. Variables can be initialized in reset and state 0. In reset, the marker image and all values incorporated into area 806 are set to 255, which will be the maximum value marker, and all other values are set to 0. Since it is not known what is contained in the BRAM, the bounding box BRAM 808 will not be set to any value. Instead, it is desirable to keep track of the position of the write pointer to know which part of the BRAM is valid. In state 0 812, when the start command is given, the Mark Image and Merge to Region values are set to 255, the state is set to 1, Y was _previously set to 0, Y _{is currently} set to 1, and all other values are set is 0. As a reminder, the numeric implementation indexes the first row from 0 instead of 1, which was previously done in the software implementation.

(3.3.2) Search/Mark

Along with the software, the search/tagging part follows. Since the bounding box is in the BRAM, the search/mark function is split to allow the BRAM to be read. Given this constraint, the search/mark software design can be further divided into different state parts to take advantage of clock delays. Therefore, the search/mark is divided into three states by a special incrementer stage.

As shown in Figures 9A and 10, state 1 will contain the conditions for finding a new pixel or no pixel at the current search position. If no hard stop condition 900 exists, and if a currently valid pixel is found 902 , it is desirable to determine whether any of the pixel's neighbors (as shown in FIG. 4 ) have a valid pixel 904 . If none of the neighbors has a valid pixel, the labeled image number and bounding box BRAM are updated 906, and the incrementer 908 is activated 918. A write command to the bounding box BRAM will take one clock cycle, but since the process increments the write address (via incrementer 908) to never rewrite the region in the BRAM, and state 1 does not read the BRAM, the Processing can return to state 1 910 without any problems, thus eliminating the need for unnecessary wait states. For further understanding, the FPGA/hardware consists of processing running in parallel each clock cycle and will acknowledge actions at the end of each clock cycle. It should also be noted that BRAM operates with some clock cycle delay. BRAM is where the system will write and read. Considering that the FPGA acknowledges the action at the end of the clock cycle and there is a delay in the BRAM, it is expected that the BRAM will not be accessed incorrectly until the write operation is complete. In other words, the system does not attempt to read the location that is currently being written to, but should only read that location after the write delay has elapsed. It should also be noted that state 1 does not rewrite the location or does not require a read, it only writes if processing returns to state 1 910. This hides the write clock cycles so that the BRAM is ready and no wait clocks need to be added to this state.

If there is a valid pixel in adjacent pixel 904, move to state 2 912. Unique to the digital implementation is the functionality of the hard stop 900 and incrementer 908. Incrementor 908 will act as a for loop, moving the current pixel and requesting the next set of pixel values. Once the entire image has been read, the incrementer 908 moves the state machine to state 4 914 to begin merging the region portions. However, since there is a chance of overflow given too many marks, state 1 implements a hard stop 900 to see when the process is less than the maximum mark range. If found, there is no need to continue searching for the image, but instead the process proceeds to state 4 916 to begin merging the region portions. If the system does not successfully implement a hard stop and does not find a valid pixel, the 920 marker image must reset the data stored at that pixel location to the maximum area count. This will ensure that when the system compares marker image positions (see Figure 12), the lowest position is up-to-date and only contains valid data pertaining to that part of the image.

In addition, FIG. 10 illustrates incrementer 908 processing, showing the decision to proceed between state 1 910 or state 4 914. After activating the incrementer 908, if the process has not read the edge 1000 of the image, the system increments the "X" index to move closer to the edge 1002 of the image and proceeds to state 1 910. Alternatively, if the process has read to the edge of the image 1000, the "X" index is reset to 1 1004, and it is determined 1006 whether the process is at the end of the image. If not, increment the "Y" index to move closer to the end of the image and swap the values of "Y _current " and "Y _previous " 1008 and proceed to state 1 910. Alternatively, if so, reset "Y _current " and "Y _previous " to their initial values, and lock the active area count to the current value of the area count 1010 and proceed to state 4 914 .

As shown in FIG. 11 , state 2 uses another module called the current tagging module 1100 , which is shown in further detail in FIG. 12 . Here, the clock cycle delay is used to perform the current tag assignment 1112 in preparation for this stage (note the discussion above regarding FPGA clock cycles and BRAM read/write delays). Referring again to Figure 11, since the bounding box BRAM 1102 will take one clock cycle to read, a read signal must be sent along with the current tag 1104 to read the address containing the data to be combined. The BRAM needs a signal as well as an address to indicate that the process is to read. "Current Tag" 1102 will be the read address. Note the note above about the functionality of the Search/Tag section, where the system combines tags here for later merging.

State 2 will only contain the part where the settings are merged into the region. State 2 exists to set the "Merge to Region" 1108 array with data that will be used later during State 3a 1110 and the "Merge Region" phase.

As on the software side, the current marker 1104 is compared 1106 to the content stored in the merged into region to make an update based on the effective neighbors 1114 for which the system will "merge into region" found in the array The value is compared to the lowest tag value. The lower "assignment" token will be the value stored in the "merge into area" array. Because the markers are provided in consecutive order, the lower markers should be the reference used later in the merged region section. See, eg, FIG. 9B , which illustrates the state 2 code, and FIG. 12 , which illustrates the current tagging module 1102 .

State 3 shown in Figure 13 covers the last part of the search/marking phase. In state 3, the bounding box BRAM 1102 is updated. However, since the read was sent in state 2, this data is only valid after one clock cycle. Therefore, state 3 is referred to as two parts. State 3A 1300 will wait one clock cycle for valid data from BRAM 1102, then state 3B 1302 will update bounding box BRAM 1102. Assuming data is received within the second cycle, an update to bounding box BRAM 1102 may be performed. Updating includes combining the data read from the calculated current marker position with the current information. As in software, it is desirable to compare the maximum and minimum values for the x and y positions, and then set the larger and smaller values back into the bounding box BRAM 1102. It is also desirable to increase the pixel count to a larger value for new pixels found. The digital implementation also adds another part to calculate the size in the X and Y directions. This will later be used as a filter against unwanted bounding boxes. Another addition is to filter out unwanted boxes that do not meet a certain range 1308 of pixel sizes. The lower and upper boundary pixel counts are used to validate bounding box BRAM 1102 storage (where pixel counts are within the valid pixel range 1310 designated as valid, and pixel counts outside the valid pixel range are designated as invalid 1312). Therefore, the valid area array is used to determine which information stored in the BRAM should be tested at a later stage by assigning the value "1" to the address containing the valid data set. The array of valid regions will be looped through later to see if the system should read the data stored in BRAM from this address location during the callback and sort phases. Finally, the system activates incrementer 908 and sends process 1304 to state 1 . However, if the incrementer 908 detects that the process is at the last pixel position, it instead sends the process 1306 back to state 4, as shown in FIG. 10 .

As shown in Figure 14, state 4, state 5 and state 6 cover the merged region phase. In state 4, the system searches in the merged area 1402 by starting at the area count 1400 and then counting down to determine if the data needs to be merged. If so, two addresses from the bounding box BRAM 1102 are required (region count 1400 and merge into region [region count] 1402), and the system writes back to the bounding box BRAM 1002 location. If not, the system continues the search in the merged region by decreasing the region count 1422 and decreasing the valid region count 1420 based on the data created during state 6 14261430 and finally implemented through 1418 .

Since the BRAM 1102 reads, the process must return to state 4 to cover the one clock cycle delay of the read and request a different address. For clarity, state 4 is divided into two parts, state 4a 1404, which is used to determine if a merge is required, and state 4b 1406, which includes clock cycle waiting and reading the next address.

State 5 1408 is very simple because BRAM 1102 is known to have valid data from state 4a 1404. Therefore, the data that has arrived at 1410 must be saved so that it can be used later to compare with the address read in state 4b 1406.

State 6 1412 will then compare 1414 to read the two sets of data received from the two bounding box BRAMs 1102 and then store the merge information back into the bounding box BRAM 1102 with the lower address accordingly. Since the write will occur during state 4a1404, the system will have written correctly before activating the read of the next address. Reaching state 6 indicates that the current region count will be merged, so the system invalidates the region for the valid region array and decrements the valid region count by 1424. As described above, a filter can be added to filter out regions (unwanted boxes) that do not meet a specific range 1426 of pixel counts that are within the valid pixel range 1428 designated as valid, and will be outside the valid pixel range The pixel count specified as invalid 1430.

Unique to this implementation is the additional callback and ordering phase carried by state 7 1416. Specifically and as shown in Figures 15 and 16, State 7 focuses on callback operations and sorting operations, respectively. As shown in the recall operation of Figure 15, this stage will recall all valid information from BRAM 1102 until the process has read out all valid areas that have been stored. From the previous state, the process keeps counting how many locations in the bounding box BRAM 1102 are still valid after filtering, and keeps track of the addresses using the valid array. Therefore, in order to recall all valid locations, the valid array is used to check whether the area in BRAM 1102 has valid data, and then decrements the valid data count. When reading, the BRAM has a delay of two clock cycles. The move from state 4a to state 7 is handled by starting a read 1508 from BRAM at the active region 1510 at address zero 1512, and by forcing a one clock cycle wait 1514 before returning to state 71516. The idea is to keep reading addresses from the bounding box BRAM 1102 so that the process is only one clock cycle 1500 later than each read. State 7 1416 will filter based on whether the read from bounding box BRAM 1102 is valid 1502 and satisfies additional filtering. A delay clock cycle is included in 1504 to account for additional filtering delays before returning to state 0 1506. Block 1518 shows the end of the search for the valid region, so the system must be forced to stop continuous reads from the address seen in 1520.

During State 3 and State 6, the pixel count valid range is used as an initial condition for validating bounding box BRAM 1102 data. Now, expect to filter out oddly shaped "boxes" by comparing Xsize(Xmax – Xmin) with Ysize(Ymax – Ymin). These boxes are invalid if Xsize/Ysize or Ysize/Xsize <= 30% (or any other predetermined value). In addition to this, it is desirable to find boxes filled with pixel blobs, thus covering a good area of the found boxes. Therefore, the system also filters by checking to see (pixel count)/Xsize x Ysize <= 30% (or any other predetermined value) and setting these positions to invalid. If the data has passed all filters, it is marked as a valid sort and passed to the "sort" section. Only those boxes that are valid are sorted and saved locally for use in other modules. Due to delays in sequencing, state 7 may complete 8 clock cycles after the last valid data read from BRAM 1102. So, for example, the process waits 8 clock cycles before determining that the bounding box is complete and is currently saved. Since the sorting is partially done in another module, the value will be reset, which is a transition from state 0 to state 1.

As shown in FIG. 16 , the sorting is done in state 7 and further sorting module 1600 . Valid bram reads 1508 and bounding box data 1102 are filtered 1604 to identify valid orderings. In addition, the result of the read and the valid ordering have an added one clock delay 1606, 1608. If the data is found to be in a valid ordering 1602, it is further ordered by the ordering module 1600.

For further understanding, Figure 17 shows a flow diagram of State 7, which focuses on the sorting operations in each individual sorting module. Each ordering module begins by first determining 1700 whether the ordering associated with the bounding box or region is valid or whether a reset ordering has been issued. If the sort is determined to be an invalid sort by a valid sort value of 0, the module will issue a "0" value passing the invalid sort command and associated data. If the ordering is a reset ordering 1704, the system empties 1706 the data stored in the ordering. Flush data 1706 stored in the sort refers to locally stored sort data. This sorted data will later hold the value found from the callback BRAM read, which ends up locally storing the maximum of the pixel count, xmax, xmin, ymax, ymin and (Xsize=xmax-xmin and Ysize=ymax-ymin) . Sorting modules all create sorting numbers by dividing the pixel count by the largest between Xsize and Ysize. This sort number and the valid sort are passed 1708 between the sort modules so that the higher sort numbers remain at the top, while the lower sort numbers drop to open the sort or leave the save area entirely. This is done by first determining 1710 whether the incoming ordering is greater than the higher ordering of the currently stored data. If so, the incoming ordering is set 1712 to the higher ordering of the currently stored data, where the previously stored higher ordering data is then set 1714 to the lower stored data, and removed 1716 from the ordering module. If the incoming ordering is less than the higher ordering of the currently stored data, then it is determined 1718 whether the incoming ordering is greater than the lower ordering of the previously stored data. If not, the incoming sorting data is removed 1722 from the sorting module. Alternatively, if the incoming ordering is greater than the lower ordering of the previously stored data, then the incoming ordering data is set 1720 to the lower ordering storage data and passed out 1716 from the ordering module.

(3.3.3) Hardware Implementation Results

A simulation is performed in which the known image is subjected to the bounding box implementation described above. Following the algorithm requirements and as shown in Figure 18, the known image 1800 is 512x256 pixels in size, with a single bit pixel (ie, one bit value for each pixel location). By passing the image 1800 through the filter, the system identified 220 marker locations, which were then merged into 182 unique bounding boxes. With sorting, the system filters the bounding box to only the top 15 "sorted" positions (as shown in Figure 19). Thus, this demonstrates that the bounding box processing of the present disclosure is effective in identifying objects in an image and generating bounding boxes around such objects. Based on this, the bounding box processing described herein can be implemented on consecutive frames in a video image to function as an efficient and effective motion tracker in any desired setting.

(3.4) Control of equipment.

As shown in Figure 20, a processor 2000 can be used to control a device 2002 (eg, mobile device display, virtual reality display, augmented reality display, computer monitor, motor, machine, drone, camera, etc.) based on bounding box generation . The controls of device 2002 can be used to convert the location of the object into a still image or video representing the object. In other embodiments, device 2002 may be controlled based on authentication and positioning to move the device or otherwise initiate physical action.

In some embodiments, a drone or other autonomous vehicle may be controlled to move to an area where the location of the object is determined based on the imagery. In still other embodiments, the camera may be controlled to track the identified object by maintaining the moving bounding box within the field of view. In other words, actuators or motors are activated to move the camera (or sensor) to keep the bounding box within the field of view so that an operator or other system can identify and track objects. As yet another example, the device may be an autonomous vehicle, such as an unmanned aerial vehicle (UAV), that includes a camera and the bounding box design described herein. In operation and when a bounding box is generated by a system implemented in the UAV, the UAV can be made to manipulate the following object so that the bounding box remains within the UAV's field of view. For example, the rotors and other components of the UAV are actuated to cause the UAV to track and follow objects.

Finally, while the invention has been described in terms of various embodiments, those of ordinary skill in the art will readily recognize that the invention may have other applications in other environments. It should be noted that many implementations and implementations are possible. Additionally, any term "means for" is intended to induce a means-plus-function interpretation of the elements and claims, and any element that does not specifically use the term "means for" should not be read as a means-plus-function element , even if the claim otherwise includes the term "means". Furthermore, although specific method steps have been stated in a specific order, these method steps can be performed in any desired order and are within the scope of the present invention.

Claims (12)

1. A system for bounding box generation, the system comprising: a memory and one or more processors, the memory having executable instructions such that when the instructions are executed, the one or more processors perform the following operations: receiving an image consisting of pixels having a value of one bit per pixel; generating bounding boxes around connected components in the image, the connected components having pixel coordinates and pixel count information; generating a ranking score for each bounding box based on the pixel coordinates and the pixel count information; filtering the bounding box to remove bounding boxes that exceed a predetermined size and a predetermined pixel count based on the pixel coordinates and the pixel count information; and filtering the bounding boxes to remove bounding boxes below a predetermined ranking score, resulting in remaining bounding boxes; and The device is controlled based on the remaining bounding box. 2. The system of claim 1, wherein the processor is a field programmable gate array (FPGA). 3. The system of claim 1, wherein generating the bounding box further comprises the following operations: grouping consecutive pixels in the image; and Connected pixels are merged into connected components, and the bounding box is formed by boxes surrounding the connected components. 4. The system of claim 1, wherein controlling the device comprises moving a video stage to maintain at least one remaining bounding box of the remaining bounding boxes within a field of view of the video stage. 5. A computer program product for bounding box generation, the computer program product comprising: A non-transitory computer-readable medium having executable instructions encoded thereon so that when the instructions are executed by one or more processors, the one or more processors Do the following: receiving an image consisting of pixels having a value of one bit per pixel; generating bounding boxes around connected components in the image, the connected components having pixel coordinates and pixel count information; generating a ranking score for each bounding box based on the pixel coordinates and the pixel count information; filtering the bounding box to remove bounding boxes that exceed a predetermined size and a predetermined pixel count based on the pixel coordinates and the pixel count information; and filtering the bounding boxes to remove bounding boxes below a predetermined ranking score, resulting in remaining bounding boxes; and The device is controlled based on the remaining bounding box. 6. The computer program product of claim 5, wherein the processor is a field programmable gate array (FPGA). 7. The computer program product of claim 5, wherein generating the bounding box further comprises the following operations: grouping consecutive pixels in the image; and Connected pixels are merged into connected components, and the bounding box is formed by boxes surrounding the connected components. 8. The computer program product of claim 5, wherein controlling the apparatus comprises moving a video platform to maintain at least one remaining bounding box of the remaining bounding boxes within a field of view of the video platform . 9. A computer-implemented method for bounding box generation, the method comprising the actions of: Cause one or more processors to execute instructions encoded on a non-transitory computer-readable medium, such that when the instructions are executed, the one or more processors: receiving an image consisting of pixels having a value of one bit per pixel; generating bounding boxes around connected components in the image, the connected components having pixel coordinates and pixel count information; generating a ranking score for each bounding box based on the pixel coordinates and the pixel count information; filtering the bounding box to remove bounding boxes that exceed a predetermined size and a predetermined pixel count based on the pixel coordinates and the pixel count information; and filtering the bounding boxes to remove bounding boxes below a predetermined ranking score, resulting in remaining bounding boxes; and The device is controlled based on the remaining bounding box. 10. The method of claim 9, wherein the processor is a field programmable gate array (FPGA). 11. The method of claim 9, wherein generating the bounding box further comprises the following operations: grouping consecutive pixels in the image; and Connected pixels are merged into connected components, and the bounding box is formed by boxes surrounding the connected components. 12. The method of claim 9, wherein controlling the device comprises moving a video platform to maintain at least one remaining bounding box of the remaining bounding boxes within a field of view of the video platform.

Images