Accelerating Feature Extraction and Image Stitching Algorithm Using Nvidia CUDA

Introduction

Assuming that you are in a region where natural disasters rampage. Landscape can change, buildings can collapse, and outdated map requires immediate, detailed, and accurate updates. This problem can be addressed by using Unmanned Aerial Vehicle(s) (UAV) to capture images of the area, and then stitch them together using existing computer-vision technologies. The true issue lies in how fast we can do this, as accurate updates mean that multiple high-quality images will be processed, and thus slows down the process due to highly expensive computational processes. One option is multi-core and multi-threads processing. But can we do better? The answer is yes, through the modern architecture behind the Graphic Processing Unit (GPU).

Image stitching requires feature detection algorithms. The first widely-used feature detection algorithm was the Harris Corner Detector, introduced in 1988 by Chris Harris and Mike Stephens. Later on, in 1999, the Scale-invariant feature transform (SIFT) algorithm by David G. and Lowe revolutionized the field of computer vision by providing a reliable method for feature detection and description. It builds upon the Harris Corner Detector but adds many key innovations to improve robustness and functionality. The SIFT algorithm is still widely used today, and most papers regarding new methods in feature detection, either through traditional means, or neural networks, use SIFT as their benchmark.

Although SIFT is a reliable method for such tasks, it is also very computationally expensive. Therefore, many more methods throughout the years have been developed to address that issue, and in 2011, Oriented FAST and Rotated BRIEF (ORB) was introduced. After multiple benchmark tests, ORB has been proven to have better overall performance with quick computing and is demonstrated to be robust to light and rotational shifts.

Project's Objective

This project mainly focuses on images captured by Unmanned Aerial Vehicles (UAV), the image patch is then sent to a central computer with an Nvidia graphic card for image processing. The map generation process involves processing a pair of images, then the algorithm will detect, and match each of the key points from one image to another. The existing work of this project involves an algorithm to process the image patch using multi-core CPUs, which are available on most modern computers.

The original author of the project, my mentor, also addressed the issue of increasing data overhead by employing distributed and shared memory architectures to reduce computation time, or in other words, multi-threading. For this project, we will employ all the previously mentioned techniques, but we will also integrate the Graphic Processing Unit through the use of CUDA. The goal is to generate reliable maps and accelerate image stitching algorithms even further by utilizing multi-core, multi-threads, and GPU computation. Performance is a large emphasis for this project; therefore, C++ will be prioritized instead of Python.

The SIFT and ORB Feature Detectors

Scale-Invariant Feature Transform. SIFT is one of the most well-known and reliable feature detectors in the field of computer vision to extract invariant features from an image. SIFT primarily works based on the Difference of Gaussian (D.o.G), defined as

Since

the D.o.G is a bandpass filter, which means that it only lets selected frequencies through. One characteristic of the bandpass filter is that it lets frequencies greater than $\frac{1}{\sqrt{2}}D_{max}$ through and blocks low frequencies. This means that the frequencies that it passes tend to be the areas of high contrast on the image, which are usually edges (In computer vision, edges are abrupt changes in intensity, discontinuity in image brightness, or contrast).

The algorithm then uses the Gaussian pyramid to compare the respective pixel with its surrounding 26 other neighbor pixels to look for the extrema of the image and improve the accuracy by the Taylor series method. SIFT then uses a straightforward approach for assigning orientations. For each image sample, $L(x,y)$, we compute the gradient magnitude $M(x,y)$ and orientation angle $\theta(x,y)$ using differences of pixels:

and,

The final output is an $n$-dimensional feature vector whose elements are invariant feature descriptors. In 2018, authors Griwodz, Calvet, and Halvorsen proposed a Python library called PopSIFT, which serves as a CUDA implementation of the SIFT algorithm.

Oriented FAST and Rotated BRIEF. FAST, short for “Features from Accelerated Segment Test,” is a widely recognized corner detection algorithm introduced by Edward Rosten and Tom Drumm in their paper “Machine Learning for High-speed Corner Detection.” FAST identifies corners by examining a circular region around a pixel to determine if the pixel qualifies as a corner. The ORB (Oriented FAST and Rotated BRIEF) algorithm uses FAST-9, which uses a circle with a radius of 9 pixels to optimize performance. However, because the original FAST algorithm does not account for orientation, ORB enhances it by assigning an orientation to each detected keypoint (similar to SIFT), thereby making the algorithm rotation-invariant. This orientation is calculated using the intensity centroid method, which leverages the moments of the patch around the keypoint, defined as:

These moments are used to determine the dominant orientation of the keypoint. The centroid can be then computed by

By optimizing the BRIEF (Binary Robust Independent Elementary Features) algorithm, binary descriptors are generated by simple pixel intensity comparison, and Angle invariance is recognized by shifting the descriptors in the main direction.

Overview of General GPU Architecture and Nvidia’s Compute Unified Device Architecture (CUDA)

Unlike a Central Processing Unit (CPU), which typically has only a few physical cores, a Graphics Processing Unit (GPU) can contain thousands or even tens of thousands of cores. Although GPU cores are designed for simple calculations and are less versatile than CPU cores, the GPU's key advantage lies in its ability to perform large-scale parallel computations. Take a look at an image, for instance:

Images are composed of millions of pixels. When processing an image, the GPU cannot handle pixels one by one (it shouldn't!), as doing so would leave many cores idle, leading to a significant waste of resources. Instead, a key principle of GPU operation is parallelism: whichever core is available first takes on the computation, ensuring that all cores are utilized efficiently. All computations are independent of each other, and finally, we only need to combine them to output the final input image.

Let's say we have 100 tasks for a GPU to compute, with each task represented as a thread. GPUs are designed to handle thousands or even millions of threads simultaneously, but they don't assign one thread to each core directly. Instead, GPU cores are organized into groups called "warps," typically consisting of 32 threads that execute the same instruction simultaneously. These warps are managed by units within the GPU called Streaming Multiprocessors (SMs).

If the number of tasks increases to 1 million, the GPU doesn't need 1 million cores to process them. Instead, it groups the threads into blocks, and these blocks are distributed among the SMs. Each SM contains multiple cores that work together to execute the warps of threads. When an SM processes a block, it schedules the warps dynamically, keeping all its cores busy and switching between warps to hide any delays, such as waiting for memory access. For example, with 1,000 cores organized into several SMs, each SM might handle many blocks of threads. Even if a single block contains 1,000 threads, the SM can manage them efficiently by processing them in warps and switching between them as needed. This hierarchical structure allows the GPU to handle a vast number of threads, ensuring that even with millions of tasks, the cores are utilized efficiently to maximize parallel computation.

Message Passing Interfaces (MPI)

What is an MPI? An MPI is a software designed to allow communication between CPU cores. MPI defines the syntax and semantics of library routines that allow programs to communicate data by passing messages between processes. For this research project, we will be using the Microsoft Message Passing Interface (MsMPI).

Open Multi-Processing (OpenMP)

OpenMP is an Application Program Interface (API) that may be used to direct multi-threaded, shared memory parallelism in C/C++, or Fortran programs. Both g++ (available since GCC 4.9) and MSVC compiler have OpenMP available through the header #include<omp.h>. To enable OpenMP in Microsoft Visual Studio, go to Project > Properties > C/C++ > Language > OpenMP support, select yes. For g++, you must add -fopenmp to the compilation of any module that uses OpenMP:

    g++ -c test.cpp -o test.o -fopenmp
    g++ test.o -o test -fopenmp -lpthread    

Image Stitching Workflow

The code base of this project belongs to a private repository, so I will not put the full code on here. It wouldn't make much sense anyway because this whole process spans across thousands of lines code. Instead, I will be summarizing the image stitching process using the flow chart below:

In order to further improve the speed of image processing, the author of the CPU implementation used a distributed memory design to parallelize image processing. Distributed memory designs transfer information between multiple CPU cores through MPI, with each or more CPU cores processing two images as a node. The greater the number of CPU cores, the greater the number of images that can be processed simultaneously in parallel without the need to wait for earlier images in the list to complete processing before processing later images. For example, if one wishes to concatenate four images, one can use two CPU cores for parallel processing.

When the two nodes are finished processing, the results are sent to the new node via MPI to process the two images processed by the previous node. This structure is similar to the tree structure and has been shown to increase the computation speed. However, one needs to note that given an unlimited amount of resources, it does not necessarily mean that the program can speed up infinitely, see Amdahl's law, which states that the potential speedup of a process due to parallelization is limited by the portion of the process that cannot be parallelized, which can be formalized by the equation

where $S$ is the speedup ratio, $P$ is the proportion of the task that can be parallelized, $N$ is the number of processors or cores, and $(1-P)$ is the proportion of the task that must be performed sequentially.

Optimization

The main change from the original paper is to convert the method of image feature extraction using CPU to GPU. We will add a function based on the code of the original paper that can detect image features using the GPU. We changed the finder of feature detection to use cuda::ORB, and based on the open source code of OpenCV CUDA, we used the corresponding CUDA ORB image feature detection algorithm to achieve the same purpose as its regular version. We call this new function

    void computeImageFeatures(Ptr<cuda::ORB> orb, const cuda::GpuMat& img,ImageFeatures& features)    

to compute GPU images. This is an analogous version of the detectAndCompute function when using regular feature detector ORB. The key feature in this function is the computation of descriptors on the GPU. To do this, we must upload the descriptors from the CPU to the GPU, and then download it back to the CPU.

Performance Metrics

Runtime Comparison

As mentioned, I will compare the two runtime of the setup with, and without multi-threading.

I initially ran our code on Setup 1. The original goal of this research is to be able to stitch 64 4K images, but due to the limited resources of the first setup, I had to downscale the image by 75% from their original quality to 540$\times$960 px.

The GPU implementation significantly outperformed the original CPU-based image stitching, reducing the runtime by a factor of three to four. However, as the number of used cores exceeded the available physical cores, the application began to slow down: all components of the system were operating at their limits: the CPU was running at 100%, the RAM was fully utilized at 16GB, and the GPU memory was maxed out at 8GB. This likely due to the context switching that the system had to perform when running out of physical cores.

One interesting thing for the first setup is that the GPU implementation was able to run up to 8 CPU cores, but the original implementation could only run up to 4 cores. One possible reason for this is that the GPU shared the resources with the CPU while performing the algorithm, which put less constraint on the CPU, and hence pushed the number of cores to the limit.

Speedup

Even though the runtime has massively decreased under the usage of CUDA, the speedup ratio does not stand out among the CPU with the OpenMP dataset, but it did, however, speedup in all scenarios of cores against CPU with 1 thread, which is reasonable since our GPU setup also uses only one thread of the CPU (no OpenMP available for GPU).One possible reason why the GPU doesn’t speed up as fast is due to the uploading and downloading of images to the GPU, which costs much more resources due to the high quality of the image patch.

Cost

In parallel computing, resource inefficiency occurs when parts of a process are forced to wait for others to complete, reducing overall performance. As observed, the cost of the GPU implementation is much lower than every other previous CPU implementations. This is not a surprise at all, as GPUs, optimized for massively parallel tasks, often provide significantly better performance for certain applications compared to traditional CPU implementations, resulting in lower operational costs for these specific workloads.

Efficiency

For efficiency, the CUDA-enhanced algorithm is less efficient than the CPU with 1 thread setup, but is overall more efficient than other CPU setups as the number of cores increases. The efficiency of the GPU implementation eventually matches that of the CPU, 1 thread implementation as $p=32$.