A Step-by-Step Introduction to the Basic Object Detection Algorithms (Part 1)
Introduction
Object detection is one of the most exciting and impactful applications of deep learning and computer vision. The ability for computers to locate and identify objects of interest in images and video has opened up a world of possibilities, from self-driving cars that can navigate complex environments, to medical imaging systems that can spot early signs of disease, to smart retail stores that can track inventory in real-time.
At its core, object detection involves both localizing and classifying objects within an image. Given an input image, an object detection model needs to output bounding boxes specifying the location of each object, as well as class labels indicating what type of object is present at each location.
In recent years, deep learning techniques, and specifically convolutional neural networks (CNNs), have become the dominant approach for tackling object detection. By leveraging the hierarchical pattern recognition capabilities of CNNs, it‘s possible to train highly accurate object detectors that can scale to thousands of object categories.
However, applying CNNs to object detection is not as straightforward as it is for image classification tasks. In a typical image classification setup, the input is a fixed-size image (e.g. 224 x 224) and the output is a single class label. Object detection, on the other hand, requires localizing objects of varying sizes and aspect ratios throughout the image. Simply running a classification CNN in a sliding window fashion over an image is computationally infeasible.
In this post, we‘ll take a closer look at some of the foundational object detection algorithms that kicked off the deep learning revolution in this domain. Specifically, we‘ll cover the R-CNN family of detectors, starting with the original R-CNN and building up to the faster and more accurate descendants, Fast R-CNN and Faster R-CNN. In part 2, we‘ll explore more recent single-stage detectors like YOLO and SSD that have pushed object detection to real-time performance.
Let‘s dive in!
The challenge of object detection
To appreciate the innovations behind modern CNN-based object detectors, it‘s helpful to first consider a naïve approach and analyze where it falls short. Given that CNNs have proven highly effective at image classification, a natural first attempt at object detection would be to simply apply a CNN classifier in a sliding window fashion.
We could take our input image and crop out a set of rectangular regions at various scales and aspect ratios. Then we could resize each cropped region to a fixed size (e.g. 224 x 224) and feed it through our pre-trained CNN to obtain a class label. By scanning the CNN across the entire image in a sliding window manner, we could obtain a classification for all possible regions.
While this sliding window approach could work in theory, it quickly becomes computationally intractable in practice. Consider a modestly-sized 500 x 500 pixel image. Even with a coarse sliding window with 50 pixel strides and just 3 scales and 3 aspect ratios, we‘d need to crop and classify over 1000 regions! With a more granular search, the number of windows can easily explode to tens or hundreds of thousands per image.
Not only is this many forward passes through a CNN incredibly slow, but it‘s also extremely inefficient as there is a huge amount of redundant computation being performed on overlapping image regions. Clearly we need a more intelligent approach that can effectively leverage the power of CNNs for object detection.
Region-based CNN (R-CNN)
In 2014, Ross Girshick et al. proposed the Region-based CNN (R-CNN) model which made a major leap in object detection performance. The key insights behind R-CNN were to 1) leverage an external region proposal method to focus feature extraction on a manageable number of regions, and 2) use a CNN to extract a rich set of features from each proposed region for downstream classification and bounding box regression.
Here‘s an overview of the R-CNN algorithm:
- Generate region proposals using selective search
- For each proposal:
- Crop proposal from image
- Resize cropped region to fixed size (e.g. 224 x 224)
- Feed resized region through pre-trained CNN to extract features
- Classify features with SVMs to predict object category
- Refine bounding box with linear regression
- Post-process detections (e.g. non-maximum suppression, thresholding)
Let‘s break this down further:
Region proposals
Instead of a exhaustive sliding window search, R-CNN uses selective search to generate class-agnostic region proposals. Selective search is a fairly sophisticated region proposal method that combines exhaustive search with image segmentation to generate around 2000 region proposals per image. These proposals tend to have high recall (i.e. they cover most of the objects in the image) while significantly reducing the search space compared to sliding windows.
Feature extraction
For each region proposal, R-CNN crops and resizes the image patch to a fixed size (e.g. 224 x 224) and then feeds it through a pre-trained CNN (e.g. AlexNet) to extract a 4096-dimensional feature vector. By using a pre-trained CNN, R-CNN benefits from highly discriminative features learned from large-scale image classification datasets like ImageNet. The fixed-sized feature vectors are then fed into a series of SVMs for classification and a linear regression model for bounding box refinement.
Classification and localization
R-CNN trains a binary SVM for each object category to classify the CNN features and predict the presence or absence of an object within each region. In addition, it trains a linear regression model to refine the bounding box coordinates of the predicted detections.
Limitations of R-CNN
While R-CNN outperformed previous object detection methods by a large margin, it still has a number of significant drawbacks:
- Training is a multi-stage pipeline that involves ConvNets, SVMs, and bounding box regressors, making the process cumbersome and slow.
- Inference (i.e. detecting objects in a new test image) is very slow, taking 40-50 seconds per image due to the need to perform a forward pass of the CNN for each region proposal. With ~2000 proposals per image, this adds up to a huge amount of redundant computation.
- The selective search region proposals are a fixed set of regions that don‘t adapt to the image content and may not align well with object boundaries. Using a fixed set of proposals also limits the recall that can be achieved by the detector.
Despite these limitations, R-CNN demonstrated the potential of CNNs for object detection and set the stage for a series of advances in the following years.
Fast R-CNN
To address some of the shortcomings of R-CNN, Ross Girshick followed up in 2015 with Fast R-CNN. The key insight behind Fast R-CNN was to share computation across the region proposals by first running the input image through the CNN to generate a feature map, and then extracting features for each proposal from this shared feature map.
Here‘s an overview of the Fast R-CNN algorithm:
- Feed input image through CNN to generate feature maps
- Generate ~2000 region proposals with selective search
- For each proposal:
- Extract fixed-length feature vector from feature map using ROI pooling
- Feed feature vector through a sequence of fully connected layers
- Classify object category with softmax classifier
- Refine bounding box with linear regression
- Post-process detections (e.g. non-maximum suppression, thresholding)
The main innovations in Fast R-CNN are:
Shared convolutional features
Instead of feeding each region proposal through the CNN separately, Fast R-CNN first feeds the entire input image through the CNN to generate a shared feature map. This allows the computation to be shared across the ~2000 proposals instead of being repeated for each one. Sharing computation significantly speeds up inference and makes training more efficient.
ROI pooling
Fast R-CNN introduces ROI pooling, a clever way to extract a fixed-size feature vector from the shared feature map for each region proposal. ROI pooling works by dividing the proposal into a grid of sub-windows and then max-pooling the values in each sub-window to generate a fixed-size output (e.g. 7 x 7). This allows Fast R-CNN to efficiently extract features for proposals of varying sizes and aspect ratios.
Streamlined training
Fast R-CNN simplifies the training process by unifying the CNN, classifier, and bounding box regressor into a single model. Instead of training SVMs post-hoc on CNN features, the model is trained end-to-end using a multi-task loss that combines cross-entropy loss for classification and L1 loss for bounding box regression. This makes training more efficient and allows for easier optimization and fine-tuning.
While Fast R-CNN significantly sped up training and inference compared to R-CNN, it still relied on an external region proposal method (i.e. selective search) which became a bottleneck. Selective search is a fixed, non-differentiable function that cannot be optimized during training. Furthermore, by using a pre-defined set of proposals, there is a fundamental limit to the recall that Fast R-CNN can achieve, since it cannot generate new proposals that may better align with the objects.
Faster R-CNN
Faster R-CNN, proposed by Shaoqing Ren et al. in 2015, aimed to address the limitations of Fast R-CNN by introducing a Region Proposal Network (RPN) to generate region proposals directly from the CNN feature maps. This made the entire object detection pipeline differentiable and allowed the region proposals to be learned and optimized during training.
Here‘s an overview of the Faster R-CNN algorithm:
- Feed input image through CNN to generate feature maps
- Run Region Proposal Network on feature maps to generate proposals
- For each proposal:
- Extract fixed-length feature vector from feature map using ROI pooling
- Feed feature vector through a sequence of fully connected layers
- Classify object category with softmax classifier
- Refine bounding box with linear regression
- Post-process detections (e.g. non-maximum suppression, thresholding)
The key component of Faster R-CNN is the Region Proposal Network:
Region Proposal Network (RPN)
The RPN is a small convolutional network that takes the CNN feature maps as input and outputs a set of rectangular object proposals, each with an "objectness" score. To generate proposals, the RPN slides a small window over the feature map and at each location outputs a set of proposal boxes of various scales and aspect ratios (called anchors) along with objectness scores indicating the likelihood of an object being present in each box.
The RPN is trained jointly with the Fast R-CNN detector in an end-to-end manner using a multi-task loss. The loss function combines a binary cross-entropy loss for objectness classification (object vs not object) and a smooth L1 loss for bounding box regression (refining the box coordinates).
By integrating region proposal generation into the CNN feature extraction stage, Faster R-CNN achieved a significant speed up and also improved detection accuracy compared to Fast R-CNN. However, Faster R-CNN still uses a two-stage approach of first generating proposals and then classifying them, which can be computationally expensive and adds some redundancy.
Summary
In this post, we reviewed the evolution of CNN-based object detectors starting with the seminal R-CNN model and its successors, Fast R-CNN and Faster R-CNN. These models made significant advances in detection accuracy and efficiency by leveraging the power of deep convolutional features and streamlining the region proposal and classification process.
Some key takeaways:
-
R-CNN first demonstrated the effectiveness of using deep ConvNet features for object detection, but was slow and inefficient due to the need to separately extract features for each region proposal.
-
Fast R-CNN sped up training and inference by sharing convolutional features across proposals and using a single model for feature extraction, classification, and bounding box regression. However, it still relied on an external region proposal method.
-
Faster R-CNN introduced the Region Proposal Network to generate proposals directly from CNN features, making the entire pipeline differentiable and further improving speed and accuracy.
While the R-CNN family of models have largely been surpassed by more recent single-stage detectors, they laid the groundwork for the rapid progress in object detection over the past few years and are still widely used as benchmarks.
In part 2 of this series, we‘ll take a look at some of these newer models, including YOLO and SSD, which have pushed object detection to real-time performance while maintaining high accuracy. Stay tuned!
){kind=link}