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

• US 9,740,947 B2
• Filed: 09/27/2016
• Issued: 08/22/2017
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: Khalifa University Of Science, Technology & Research
• Original Assignee: Khalifa University of Science and Technology
• Inventors: Alyammahi, Sohailah Mohamed Rashed, Salahat, Ehab Najeh, Saleh, Hani Hasan Mustafa, Sluzek, Andrzej Stefan, Elnaggar, Mohammed Ismail
• Primary Examiner(s): Bitar, Nancy
• Application Number:
  US15/277,477
• Publication Number:
  US 20170017853A1
• Time in Patent Office: 329 Days
• Field of Search: None
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/435 Computation of moments
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/752 Contour matching
• CPC Class Codes: G06V 10/955 using specific electronic processors
• CPC Class Codes: G06V 10/96 Management of image or video recognition tasks
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

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₂(M×

N)}}×

M×

N 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₂(M×

N)}}×

M×

N 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).