Hardware architecture for linear-time extraction of maximally stable extremal regions (MSERs)

Abstract

An architecture for linear-time extraction of maximally stable extremal regions (MSERs) having an image memory, heap memory, a pointer array and processing hardware is disclosed. The processing hardware is configured to in real-time analyze image pixels in the image memory using a linear-time algorithm to identify a plurality of components of the image. The processing hardware is also configured to place the image pixels in the heap memory for each of the plurality of components of the image, generate a pointer that points to a location in the heap memory that is associated with a start of flooding for another component and store the pointer in the array of pointers. The processing hardware is also configured to access the plurality of components using the array of pointers and determine MSER ellipses based on the components and MSER criteria.

Claims

1. An architecture for linear-time extraction of maximally stable extremal regions (MSERs) comprising: image memory; heap memory; an array of pointers, wherein a total memory size for the image memory, the heap memory, and the array of pointers is equal to {3.125 +{LOG.sub.2(MN)}}MN where M and N are both finite positive integers; and processing hardware configured to in real-time: analyze image pixels in the image memory using a linear-time algorithm to identify a plurality of components of an image; place the image pixels in the heap memory for each of the plurality of components of the image: generate a pointer that points to a location in the heap memory that is associated with a start of flooding for another component; and store the pointer in the array of pointers; access the plurality of components using the array of pointers; and determine MSER ellipses based on the plurality of components and MSER criteria.

2. The architecture of claim 1 wherein the MSER criteria include a minimum diversity value.

3. The architecture of claim 2 wherein the MSER criteria further include a minimum MSER area, a maximum MSER area, and a maximum variation value for MSER area.

4. The architecture of claim 1 wherein parameters of the MSER ellipses include a center of gravity, a major axis length, a minor axis length, and an angle of the major axis length with respect to a horizontal axis.

5. The architecture of claim 1 wherein the processing hardware includes MSER moments calculator hardware configured to calculate MSER moments.

6. The architecture of claim 5 wherein the processing hardware further includes elliptical fit approximator hardware configured to receive MSER moments from the MSER moments calculator hardware and fit an MSER ellipse to an extremal region based upon the MSER moments.

7. The architecture of claim 1 wherein the processing hardware includes MSER selector hardware configured to automatically select MSERs based upon the MSER criteria.

8. The architecture of claim 1 further including a communications interface configured to receive a data stream containing the image pixels and store the image pixels in the image memory.

9. The architecture of claim 1 wherein the processing hardware is fabricated on a single application specific integrated circuit (ASIC).

10. The architecture of claim 1 wherein the processing hardware is implemented on a single field programmable gate array (FPGA).

11. A method for linear-time extraction of MSERs via processing hardware comprising: analyzing image pixels stored in an image memory using a linear-time algorithm to identify a plurality of components of the image; placing the image pixels in a heap memory for each of the plurality of components of the image: generate a pointer that points to a location in the heap memory that is associated with a start of flooding for another component; and store the pointer in an array of pointers; access the plurality of components using the array of pointers; and determine MSER ellipses based on the plurality of components and MSER criteria, wherein a total memory size for the image memory, the heap memory, and the array of pointers is equal to {3.125 +{LOG.sub.2(MN)}}MN where M and N are both finite positive integers.

12. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the MSER criteria include a minimum diversity value.

13. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the MSER criteria further include a minimum MSER area, a maximum MSER area, and a maximum variation value for MSER area.

14. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein parameters for the MSER ellipses include a center of gravity, a major axis length, a minor axis length, and an angle of the major axis length with respect to a horizontal axis.

15. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the processing hardware includes MSER moments calculator hardware configured to calculate MSER moments.

16. The method for linear-time extraction of MSERs via processing hardware of claim 15 wherein the processing hardware further includes elliptical fit approximator hardware configured to receive MSER moments from the MSER moments calculator hardware and fit an MSER ellipse to an extremal region based upon the MSER moments.

17. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the processing hardware includes MSER selector hardware configured to automatically select MSERs based upon the MSER criteria.

18. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the processing hardware is fabricated on a single application specific integrated circuit (ASIC).

19. The method for linear-time extraction of MSERs via processing hardware of claim 11 wherein the processing hardware is implemented on a single field programmable gate array (FPGA).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings incorporated in and forming a part of this specification illustrate several aspects of the disclosure, and together with the description serve to explain the principles of the disclosure.

(2) FIG. 1 is a block diagram of an architecture for linear-time extraction of maximally stable extremal regions (MSERs) that is in accordance with the present disclosure.

(3) FIG. 2 is a block diagram for an embodiment of the architecture for linear-time extraction of MSERs that provides detail for component creation hardware.

(4) FIG. 3 is a flowchart for a flooding process executed by the component creation hardware and the find new component hardware that communicates with the component creation hardware.

(5) FIG. 4 is memory diagram of a data structure for the heap memory (FIG. 2) and an associated pointer array.

(6) FIG. 5 is an exemplary contour sketch of an irregularly-shaped MSER with a best-fit elliptical approximation.

(7) FIG. 6 is a test image displaying ellipses for MSERs detected and extracted from the test image processed by the architecture for linear-time extraction of MSERs.

DETAILED DESCRIPTION

(8) The embodiments set forth below represent the necessary information to enable those skilled in the art to practice the disclosure and illustrate the best mode of practicing the disclosure. Upon reading the following description in light of the accompanying drawings, those skilled in the art will understand the concepts of the disclosure and will recognize applications of these concepts not particularly addressed herein. It should be understood that these concepts and applications fall within the scope of the disclosure and the accompanying claims.

(9) FIG. 1 is a block diagram of an architecture 10 for linear-time extraction of maximally stable extremal regions (MSERs). The architecture 10 includes a communication interface 12 and MSER linear-time processing hardware 14. In an exemplary embodiment, a cache memory 16 is usable to store data resulting from MSER processing performed by the MSER linear-time processing hardware 14. For the purpose of this disclosure, the architecture 10 combines the required electronic circuits of various hardware implemented functions and memory needed to realize the architecture 10 onto a single integrated chip (IC) as a complete system. The architecture 10 is realized on a (System-on-Chip) SoC, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC) or the like.

(10) The MSER linear-time processing hardware 14 includes intensity image process hardware 18 that receives a data stream of an intensity image via the communications interface 12. The intensity image process hardware 18 includes component creation hardware 20 and find new component hardware 22 that creates, finds, and merges components associated with the intensity image, and then passes the components on MSER process hardware 24.

(11) The MSER process hardware 24 includes MSER selector hardware 26 that receives MSER criteria that uses the components to select MSERs. MSERS that are selected have moments calculated by calculate moments hardware 28. The moments are used by elliptical fit approximator hardware 30 to generate ellipse parameters that are stored in an MSER ellipses parameters memory block 32.

(12) FIG. 2 is a block diagram for an embodiment of the architecture 10 for linear-time extraction of MSERs that provides detail for the component creation hardware 20 and the find new component hardware 22. In order to realize a flood-filling of the linear-time MSERs algorithm, assigned memory locations are employed. A memory location known as a priority queue 20A maintains a priority value that is pixel intensity (i.e., grey level). In at least one embodiment, a highest priority value is 255. Therefore, a priority value less than 256 indicates that the find new component hardware 22 is not finished finding components.

(13) A heap memory 20B has columns equal to the number of grey levels. For an unsigned 8-bit image, there are 256 grey levels (0-255). The first column corresponds to level 0 and the last column to level 255. All pixels that are accessed but not yet flooded are stored in this memory. The first element in each column is used as a pointer to the last element in that column. Initially, the pointer points to the second location in a column. The pointer's value is incremented when a new element is added while its value is decremented when an element is popped out. Feature 22A pushes a new component onto the stack and processes the heap while feature 22B merges components.

(14) A stack memory 22C of the same size as an input image is used to store a sequence of pixels that are flooded. The stack memory can be considered a memory block that stores a water path during flooding.

(15) A binary mask 20D has the same dimension as input image wherein each bit of the binary mask 20D is used to determine the state of a corresponding pixel. The state of the corresponding pixel indicates whether or not the corresponding pixel has been accessed by water or not. Initially, all pixel values are set to be true, indicating that these pixels are accessible. In the exemplary embodiments of this disclosure, a true condition is represented by a logic 1 and a false condition is represented by a logic 0.

(16) FIG. 3 is a flowchart for the flooding process executed by the component creation hardware 20 and the find new component hardware 22 that communicates with the component creation hardware 20. The flooding process comprising the linear-time MSERs algorithm starts by clearing heap memory 20B, a binary mask, and a matrix to store flooding sequence (step 100). Next, a source pixel is set as the current pixel, and a binary mask value of the source pixel is set to 0 along with grey level for the source pixel, which is stored as current grey level (step 102). Then, the neighbors of the current pixel are searched using a process known as 4-connectivity that examines the properties of four pixels that are adjacent to the current pixel. If an index of a neighbor pixel is valid, a binary mask for the neighbor value is set to a logic 1 and marked as accessible (step 104). A grey level of this neighbor pixel is stored as grey level neighbor and is compared with current grey level (step 106). If neighbor grey level is lower than current grey level, the neighbor pixel is selected as the current pixel and the previous current pixel is pushed onto the heap memory 20B and the flooding process returns to step 104 (step 108). However, if neighbor grey level is not lower than current grey level, the neighbor is pushed onto the heap memory 20B and the flooding process returns to step 104 (step 110). If all neighbors are accessed, the binary mask value of the current pixel is set to logic 0, and the current pixel is added to a flooding path stack. At this point, a check is made to determine if the heap memory 20B is empty (step 112). The flooding process comes to a stop if either the heap memory 20B is empty or elements pushed onto the heap memory 20B are equal to the elements popped from the heap memory 20B. If the heap memory 20B is not empty, a pixel of the minimum grey level value is popped from the heap memory 20B and is set as the current pixel (step 114). The flooding process returns to step 104 and continues until the heap memory 20B is empty.

(17) FIG. 4 is a memory diagram of a data structure 34 for the heap memory 20B (FIG. 2) and an associated array of pointers 36. The data structure 34 is relatively very memory efficient as it saves 90% of the memory requirements of the original linear-time MSERs algorithm. As a result, the MSER linear-time processing hardware 14 is suitable for small and mobile devices and fits large-scale image retrieval tasks, and allows a wide spectrum of potential real-time applications to be realized. In particular, the MSER linear-time processing hardware 14 is configured to place image pixels in the heap memory 20B for each of a plurality of components of the image, generate a pointer that points to a location in the heap memory 20B that is associated with a start of flooding for another component and store the pointer in the array of pointers 36. The MSER linear-time processing hardware 14 is also configured to access the plurality of components using the array of pointers and determine MSER ellipses based on the components and MSER criteria.

(18) Returning to FIG. 1, the communication interface 12 receives MSER critera that in at least one embodiment includes a minimum MSER area value MinArea, a maximum MSER area value MaxArea, and a maximum variation value MaxVar. The minimum MSER area is the minimum number of pixels that an MSER can contain. In contrast, the maximum MSER area is the maximum number of pixels that an MSER can contain.

(19) The communication interface 12 passes the MSER criteria to MSER selector hardware 26, which also receives MSERs found via the find new component hardware 22. The MSER selector hardware 26 in turn tests each MSER to ensure that each MSER has an area that fits within the range specified by the minimum MSER area value MinArea and the maximum MSER area value MaxArea.

(20) The maximum variation value MaxVar specifies how stable the detected MSERs must be. The communication interface 12 passes maximum variation value MaxVar to the MSER selector hardware 26, which in turn tests each component found by the find new component hardware 22 to ensure that each component does not exceed the maximum variation value MaxVar.

(21) In one embodiment, the MSER criteria also include a minimum diversity value that is provided to mitigate sensitivity to blur and to mitigate discretization effects that plague traditional MSER extraction software and/or hardware. Since nested MSERs have similar center coordinates, any new MSERs with centers within a range associated with the minimum diversity value compared to previously detected and stored MSERs are excluded automatically. In particular, all detected MSERs satisfy the following conditions:
x.sub.0:.Math.{(10.5)x.sub.i,(1+0.5)x.sub.i},EQ. 1
y.sub.0:.Math.{(10.5)y.sub.i,(1+0.5)y.sub.i},EQ. 2
where x.sub.i and y.sub.i denote all previously stored center values of the detected MSERs. However, comparing centers has a drawback in that unnecessary computations are included while image moments are calculated. In order to predict possible nesting, and hence save unnecessary operations due to comparing centers, an alternative approach is executed by the MSER selector hardware 26 at a relatively far lower computational cost. Specifically, for each region, the MSER selector hardware 26 compares a current growth rate with a previous growth rate, and if an absolute difference is within a range defined by the minimum diversity value , then this region at the current intensity threshold is excluded by the MSER selector hardware from further MSER extraction processing.

(22) FIG. 5 is an exemplary contour sketch of an irregularly shaped MSER 38 with a best-fit elliptical approximation 40. Note that since merging regions will cause the same region sizes to be stored for multiple seeds, multiple detections referring to the same MSER may occur. To avoid this, only the first seed for the merged regions is used by the MSER process hardware 24 during operation, as discussed above. execution time.

(23) MSER calculate moments hardware 28 uses a pixel list to calculate region moments using the following relationship for any particular moment m.sub.pq.
m.sub.pq=.sub.(x,y)Rx.sup.py.sup.q,EQ. 3
x,yR()EQ. 4
where x and y denote the pixel coordinate of the region R() at the current intensity threshold. Subsequently, the region can be approximated by a best-fit ellipse equation that is given by:

(24) $\begin{array}{cc}\frac{{\left(x-x_0+\tan \left(\right)\left(y-y_0\right)\right)}^2}{a^2\left(1+{\tan }^2\left(\right)\right)}+\frac{{\left(y-y_0+\tan \left(\right)\left(x-x_0\right)\right)}^2}{b^2\left(1+{\tan }^2\left(\right)\right)}=1,& \mathrm{EQ}.5\end{array}$
where (x.sub.0, y.sub.0), a, b, and , respectively, are MSER ellipse parameters that represent a center of gravity (center of the MSER ellipse), a major axis length, a minor axis length, and an angle of the major axis with respect to a horizontal axis. In an exemplary embodiment, the MSER ellipse parameters are determinable using region moments m.sub.00, m.sub.10, m.sub.10, m.sub.11, m.sub.02, and m.sub.20 that are calculated by MSER calculate moments hardware 28. Elliptical fit approximator hardware 30 uses the region moments provided by the MSER calculate moments hardware 28 to approximate the MSER ellipse parameters (x.sub.0, y.sub.0), a b, and via the following mathematical relationships.

(25) $\begin{array}{cc}{x}_0=\frac{m_{10}}{m_{00}},& \mathrm{EQ}.6\\ y_0=\frac{m_{01}}{m_{00}},& \mathrm{EQ}.7\\ a=\sqrt{2\left(t_1+t_3+\sqrt{t_2^2+{\left(t_3-t_1\right)}^2}\right)},& \mathrm{EQ}.8\\ b=\sqrt{2\left(t_1+t_3-\sqrt{t_2^2+{\left(t_3-t_1\right)}^2}\right)},& \mathrm{EQ}.9\\ =0.5{\tan }^{-1}\left(\frac{t_2}{t_1-t_3}\right),& \mathrm{EQ}.10\\ \mathrm{where}& \\ t_1=\frac{m_{20}}{m_{00}}-x_0^2,& \mathrm{EQ}.11\\ t_2=2\left(\frac{m_{11}}{m_{00}}-x_0{y}_0\right),& \mathrm{EQ}.12\\ t_3=\frac{m_{02}}{m_{00}}-y_0^2,& \mathrm{EQ}.13\end{array}$
Instead of storing each MSER pixels list, which would require a relatively huge memory, the MSER ellipses parameters memory block 32 is usable to store best-fit ellipses parameters (x.sub.0, y.sub.0), a, b, and , which are provided to external hardware (not shown) for display or monitoring. For example, since the best-fit ellipses parameters (x.sub.0, y.sub.0), a, b, and are readily available through the communication interface 12, they can be used to compute scale invariant feature transform (SIFT) descriptors and speeded up robust features (SURF) descriptors.

(26) The MSER calculate moments hardware 28 calculates the region moments m.sub.00, m.sub.10, m.sub.10, m.sub.11, m.sub.02, and m.sub.20 that are stored in a 51 memory array stored in the cache memory 16 (FIG. 1). Next, the elliptical fit approximation hardware 30 implements calculate ellipses fit parameters that includes best-fit ellipses parameters (x.sub.0, y.sub.0), a, b, and , which are stored in the MSER ellipses parameters memory block 32.

(27) FIG. 6 is a test intensity image displaying a sample of MSERs that were detected by the architecture 10 of the present disclosure. The MSERs are contained or mostly contained within the white ellipses. Note that some of the MSERs are nested and are represented by ellipses within other ellipses. Crosshairs designate the center of each ellipse. Some nested MSERs are represented by concentric ellipses. It is to be understood that the number of ellipses representing MSERs in FIG. 5 are relatively few only for the purpose of simplified illustration. Relatively many more MSERs are typically detectable during operation of the architecture 10.

(28) Those skilled in the art will recognize improvements and modifications to the embodiments of the present disclosure. All such improvements and modifications are considered within the scope of the concepts disclosed herein and the claims that follow.