# US 12,217,475 B1 · Stream processing-based non-blocking ORB feature extraction accelerator implemented by FPGA

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,217,475 B1
- Document ID: US12217475B1
- Status: Granted
- Kind: B1
- Application number: 18/813,094
- Filed: 2024-08-23
- Granted: 2025-02-04
- Earliest claimed: 2023-11-06
- Assignees: Shanghaitech University
- Applicants: Shanghaitech University
- Inventors: Qixing Zhang; Yajun Ha
- Web page: https://patentgrep.com/patent/US12217475B1

## CPC

- G06V 10/462: {Salient features, e.g. scale invariant feature transforms [SIFT]}
- G06F 5/06: for changing the speed of data flow, i.e. speed regularising {or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor (G06F7/78 takes precedence)}
- G06F 15/78: comprising a single central processing unit
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 1/60: Memory management
- G06V 10/46: Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features (colour feature extraction G06V10/56)
- G06V 10/94: Hardware or software architectures specially adapted for image or video understanding
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

The provided is a stream processing-based non-blocking oriented FAST and rotated BRIEF (ORB) feature extraction accelerator implemented by a field programmable gate array (FPGA), which mainly includes two innovations: A stream processing-based non-blocking hardware architecture and a cache management algorithm are provided. The accelerator precisely controls and buffers each column of an rBRIEF descriptor computation window by using an algorithm, allowing to receive a new input pixel stream while computing a descriptor, thereby achieving non-blocking processing. An efficient hardware sorting design embedded in an accelerator is provided. Based on a count sorting algorithm, minimal resources are used to implement rBRIEF sorting on hardware, and the rBRIEF sorting is embedded in the accelerator. The accelerator ensures quality of a feature point while achieving high-speed feature point extraction, without significantly reducing accuracy of ORB_SLAM and other algorithms.

## Claims

### Claim 1

A stream processing-based non-blocking oriented FAST and rotated BRIEF (ORB) feature extraction accelerator implemented by a field programmable gate array (FPGA), comprising:
a downsampling module configured to adjust an input image to a required size to obtain an original image;
a Gaussian filtering module configured to blur the original image to obtain a blurred image;
a corner detection module configured to determine a position of a feature point in the blurred image and output a mask of the feature point;
a non-maximum suppression (NMS) module configured to perform NMS on the mask of the feature point, wherein the stream processing-based non-blocking ORB feature extraction accelerator further comprises:
a rotated binary robust independent elementary feature (rBRIEF) computation module configured to perform window column selection, rBRIEF computation, and window column First-In First-Out (FIFO) in parallel by using a cache management algorithm, wherein
a working region of a computation module of an rBRIEF descriptor is a 37×37 sliding window, and the 37×37 sliding window is updated in each clock cycle; whenever the 37×37 sliding window is updated, an intermediate pixel of a leftmost column of pixels, namely left pixel, and an intermediate pixel of a rightmost column of pixels, namely right pixel, in the mask of the feature point are detected; when the right pixel is a feature point, an intermediate column of the blurred image is considered as a first column of a window, the intermediate column of the blurred image is written into a window column FIFO queue, a counter is reset, and next 36 intermediate columns are further written into the window column FIFO queue; and when the left pixel is a feature point, the intermediate column of the blurred image is considered as a last column of a window, a label is attached when each intermediate column is written into the window column FIFO queue, to indicate whether the intermediate column is a start column or an end column, and the rBRIEF computation module determines whether to perform the rBRIEF computation based on the label; and
the rBRIEF computation module reads data from the window column FIFO queue and concatenates the read data into another window matrix; a new column is inserted at an end of the window matrix in each clock cycle, and other columns of the window matrix are sequentially shifted leftwards; window concatenation operates at a throughput of one column per cycle until a predetermined column is an end column; the reading of the window column FIFO queue is stopped, and the rBRIEF computation is performed; and when the rBRIEF computation is performed, the original image is configured to compute a direction of a centroid, and a BRIEF coordinate is rotated based on an angle of the direction to compute the rBRIEF descriptor; and
a sorting module configured to perform hardware implemented count sorting.

### Claim 2 (depends on 1)

The stream processing-based non-blocking ORB feature extraction accelerator implemented by the FPGA according to claim 1, wherein the sorting module uses 256 containers internally to cache an index of the feature point, and indexes corresponding to feature points with a same response value are cached in a same container.

### Claim 3 (depends on 1)

The stream processing-based non-blocking ORB feature extraction accelerator implemented by the FPGA according to claim 1, wherein the sorting module is integrated with the rBRIEF computation module; after the rBRIEF descriptor is computed, an index of the rBRIEF descriptor is immediately stored in a container; and after all rBRIEF descriptors are computed, indexes of the rBRIEF descriptors are sequentially outputted in order.