Faster R-CNN : Object Detection

In this blog I will talk about Faster R-CNN algorithm. This is the third blog in the series of R-CNN based object detection. In my previous blogs I talked about R-CNN and Fast R-CNN, for better understanding of Faster R-CNN, first read about R-CNN and Fast R-CNN. Faster R-CNN is one of the state-of-the-art deep learning based object detection network, all the new object detection algorithm is compared with this one, so one must know about this.

Lets recall the previous object detection algorithm of the R-CNN family before starting about Faster R-CNN.

R-CNN (Region based convolutional neural network) have three component, first is region proposal using Selective Search algorithm that generate approx 2000 candidate regions for objects in an image, second part is feature extraction for all these candidate regions by passing them to CNN and third part is region classification using SVM and bounding box (b-box) refinement using b-box regression layer. 

R-CNN Object Detection

Fast R-CNN also have region proposal (Selective Search) same as R-CNN but instead of processing all region proposal through CNN, It first generate feature map of image by processing it by CNN and then extract features for each proposal from the feature map using ROI Pooling Layer.  

And these features are feed into a sequence of fully connected (FC) layers that finally branch into two sibling output layer, one produce softmax probability estimate over K+1 object classes (where K is no. of class, plus one for background) and other layer outputs four real-value number for each of the K classes. 

Fast-RCNN Object Detection

Fast R-CNN if fast and accurate in comparison to R-CNN but still it is not end-to-end trainable and region proposal is still bottelneck in state-of-the-art detection system.

Faster R-CNN introduces novel Region Proposal Networks (RPN) that share convolutional layers with detection networks. By sharing convolutions, the marginal cost for computing proposal reduces to 10ms from 1.5sec for an image. 

Faster R-CNN can be seen as RPN network plus Fast R-CNN detector network.

Let's try to understand RPN Network.

Region Proposal Network 

RPN network is going to generate candidate region for objects in the image, so it must generate proposal for object of different scale and aspect ratio.

To incorporate multiple scales and sizes, we have different scheme like pyramid of images and pyramid of filters. In pyramid of images, features map are calculated over multiple scale of images to detect smaller and larger object. In pyramid of filters, multiple filter with different scales/sizes are applied over feature map to detect smaller and larger object.  

Fig. (a) Pyramid of Image (b) Pyramid of Filters

RPN uses different scheme i.e. pyramid of reference boxes (Anchor). 

Fig. Pyramid of Reference Anchor

Anchor 

Anchor are pre-define bounding box of fixed shape and size. Anchor dimension are define wrt to images. For Anchors, Faster R-CNN uses 3 different scale with box area 128², 256² and 512² and 3 different aspect ration 1:1, 1:2 and 2:1, combination of these will produce 9 anchors.

All 9 anchor at pixel (320,320). Area for blue, green, and red anchors are 128², 256² and 512² respectively.

For a typical input image 1000x600x3 in Faster R-CNN, the dimension of feature map is reduced to 60x40x512 after backbone (VGG-16) network. This feature map is shared between RPN network and Fast R-CNN detection network.

RPN add a mini-convolutional network over backbone/head network to output a set of rectangular object proposal. This mini-network slide multiple 3x3 filter on the last convolutional layer of backbone network, followed by, two sibling 1x1 convolutional layer, a box-regression layer and box-classification layer for object proposal prediction.

At each sliding window (convolution) location it predict 9 proposal (b-box) of different scale and size using Anchors.

Region Proposal Network

The first conv layer of RPN help the RPN network to learn feature for anchors prediction on top of the base network features. The first 1x1 convolution branch of RPN predict whether proposal containing object or no-object. So the number of conv filter required to classify one anchor is 2 and for 9 anchor is 18. 

The Second 1x1 convolution branch of RPN predict proposal bounding box offset. So the number of conv filter required to predict b-box offset for one anchor is 4 (x,y,w,h) and for 9 anchor is 36.

For VGG and ZF head network, network stride is 16 which means after processing image by any of these head network, feature map dimension will be 1/16 of input image dimension. One pixel in feature map have 16x16 receptive field in the input image. So when we say at each point of feature map we try to detect 9 different proposal that means we try to locate object in input image after every 16 pixels.

To understand how RPN learn to predict the object location, see it's loss function. 

RPN Loss function

RPN network is trained in a batch of 256 anchor, with 1:1 ratio of positive anchor and negative anchor. Positive anchor have IoU grater than 0.7 with ground truth and negative anchor have IoU less than 0.3 with ground truth, other anchor are defined as neutral anchor. Note one ground truth can have IoU of 0.7 with multiple anchor.

RPN loss have two component, b-box regression loss to predict the location of object and b-box classification loss to predict positive object and negative object. Regression loss is only calculated for positive anchors.

Multi task loss of RPN

Here, i the index of an anchor in a mini-batch.

First part of above loss is classification loss where p_i is the predicted probability of anchor i being an object and p^*_i is the ground truth of the anchor i, here p^*_i is 1 for positive anchor and 0 for negative anchor. This classification loss L_cls is log loss over two classes (object vs not object).

Second part of loss is regression loss which is multiplied by p^*_i so it's value for negative anchor is zero, here t_i is a vector representing the 4 parameterized co-ordinates of the predicted b-box and t^*_i is that of the ground-truth box associated with a positive anchor.

For Regression loss, L_reg(t_i, t^*_i), it uses smooth L1 loss. To read more about smooth L1 loss go through the loss section of previous blog.

Classification loss is normalized by mini batch size N_cls (256), regression loss is normalized by number of anchor location N_reg (~2400) and regression loss is weighted by lambda which is 10 thus giving approximately equal weighted to both loss.

The regression target t^*_i for a positive anchor is defined as -

Offset of ground truth box and anchor

Here x, y, w and h denotes the box's center coordinates and it's width and height.

Variable x, x_a and x^* are for predicted, anchor and ground truth respectively, likewise for y, w and h.

Predicted bounding box parameter (x, y, w, h) can be calculated by using predicted offset and corresponding anchor.

Offset of predicted box and anchor

RPN loss function force the RPN network to learn to predict the offset (t_x, t_y, t_w and t_h) of bounding box wrt pre-define anchors for object. 

We can see this as a bounding box regression from an anchor box to a nearby ground-truth box.

Training RPN

RPN can be trained end-to-end using backpropogation and SGD. Weights of backbone network is initialized by pre-trained model for ImageNet classification. New layers weight are randomly initialized using zero mean Gaussian distribution with standard deviation of 0.01.

To compute the loss of RPN, random sample of 256 anchor are selected from an image with 1:1 ration of positive and negative anchor. In case of less (<128) positive anchor in an image mini batch is padded with negative anchor.

The Anchor boxes that cross image boundaries were removed from training which reduces the number of anchor from ~20000 (60x40x9) to 6000. Some proposals highly overlap with each other so to reduce redundancy NMS is used with 0.7 IoU threshold, which leaves around 2000 proposal regions per image. After NMS top-N proposal are used for detection.

Faster R-CNN : RPN + Fast R-CNN detector

Faster R-CNN network can be seen as Fast R-CNN network with RPN network for object proposal network instead of Selective Search Algorithm. 

Faster R-CNN Network

Backbone/Head network (VGG-16) feature map is shared between both RPN and detection branch.

Detection network project the object proposal from RPN network to backbone network feature map to get the features for object classification and object bounding box refinement but these feature need to be a fixed size because of fully connected layer in network.

So it uses RoI pooling layer to resize the feature map of each object to a fixed size (7x7x512).

RoI pooling works by dividing the H x W roi region (object proposal) into h x w grid of sub-window of approximate size H/h x W/w and then max-pooling the values in each sub-window into the corresponding output grid cell. Read more about RoI pooling layer in Fast R-CNN blog.

After RoI pooling layer, resized feature for each proposal is passed to fully connected layer and that feature is finally passed to classification layer and bounding box refinement layer.

Classification layer gives C probability values using Softmax function for each proposal where C is number of class including background. 

Predicted box of object proposal is further refined by bounding box regression layer of detection network. This layer gives bounding box offset wrt to each class. That means each class have their own regression with four parameter unlike bounding box regression of RPN.

It uses the same multi-task loss as in Fast R-CNN.

One of the important thing to note about this network is feature sharing between RPN and detection network.

Feature Sharing for RPN and Fast R-CNN

If both RPN and detector network trained independently, both will modify backbone convolutional layer weights in different ways. So author followed a 4-step training procedure to allow the networks to share the weights.

1. First, RPN is trained independently as mentioned above. The network initialized with ImageNet pre-trained model and fine-tuned end-to-end for the region proposal task.
2. In second step, separate detection network is trained by using the proposal generated by step-1 RPN. Again this network is also initialized with ImageNet pre-trained model. Till here networks are not sharing weights.
3. In third step, RPN is again trained but this time network is initialized with the above step-2 detector weights and keeping the common convolutional layer weights between RPN and detector fixed, only layer unique to RPN are fine-tuned. Now here both network are sharing the same wights for backbone network.
4. Finally, keeping the shared convolutional layers fixed of above network, layers unique to detection branch (Faster R-CNN) are fine-tuned. This gives the final Faster R-CNN network which share the convolutional weight and form a unified network.

Result

Faster R-CNN using VGG-16 as backbone network achieves state of the art object detection accuracy on PASCAL VOC 2007, 2012 and MS COCO dataset with only 300 proposal. It perform at 5 fps including all step on a GPU.

• Faster R-CNN takes around 198ms for proposal and detection on one image compared to approx 1.8 sec for Fast R-CNN (avg 1.5 sec for proposal and 320ms for detection).
• Faster R-CNN achieved 3.2% higher mAP compared to Fast R-CNN on the union set of PASCAL VOC 2007 trainval and 2012 trainval dataset.
• Faster R-CNN achieved 2.8% higher mAP@0.5 IoU compared to Fast R-CNN on MS COCO dataset.

That's all for this post, hope you find this blog informative.
Thanks for reading !!

Fast RCNN : Object Detection

In this blog I will cover Fast R-CNN (Fast Region-based Convolutional Neural Network) for object detection algorithm. Fast R-CNN is better than it's base architecture R-CNN in term of detection accuracy, training and testing time. If you don't know about the R-CNN model please read about it in my previous blog.

I will be covering following points from the Fast R-CNN paper.

• Advantage of Fast R-CNN over R-CNN
• Fast R-CNN Architecture
• RoI Pooling Layer
• VGG-16 fine-tuning for Fast-RCNN
• Loss Function
• Main Results
• Miscellaneous

Let's get started with Fast R-CNN. 

Advantage of Fast R-CNN over R-CNN

• Higher detection rate (mAP) than R-CNN. It have 66 % mAP on PASCAL VOC 2012
• Training is single stage for classifying candidate objects and refining their spacial location, using a multi-task loss function
• Fast R-CNN with VGG16 as base network trains 9 times faster then R-CNN and 213 times faster at test time
• No disk storage is required for feature caching

Fast R-CNN Architecture

Let's Recall R-CNN architecture, we saw in my previous blog that R-CNN network have three component, first is region proposal that generate 2000 region proposal, second is feature extraction for each region proposal by passing them to CNN and third is the region classification using SVM & bounding box (b-box) refinement using b-box regression.

Fast R-CNN also have region proposal network same as R-CNN but instead of processing all region proposal through CNN, Fast-RCNN first generate feature map of an image by passing it to CNN and then extract features for each proposals from feature map using ROI Pooling Layer. 

Now these features are feed into a sequence of fully connected (FC) layers that finally branch into two sibling output layers, one produce softmax probability estimate over K+1 object classes (where K is no. of class, plus one is for background) and another layer outputs four real-valued number for each of the K object classes. These four value encodes refined bounding-box positions for one of the K classes.

Fast R-CNN architecture

R-CNN:-  Image + Region Proposal(2K) -> 2K cropped region -> CNN feature for 2K cropped region by passing each region to CNN -> SVM + b-box regression.

Fast-RCNN:- Image + Region Proposal(2K) -> CNN feature for image -> Mapping all region proposal on feature map of image -> Extracting feature of each region proposal using RoI pooling layer -> two separate output layer for classification and b-box refinement 

RoI Pooling Layer

Let's see what is the use of RoI pooling layer.

As we know the fully connected layer always takes fixed length input features. Therefore in R-CNN we wrapped region proposal to fix size (227x227) before passing it to CNN, so that CNN can generate a fixed shape and size of feature map to pass fixed length of input to FC layer.

Here also Faster R-CNN takes input image and region proposal as an input for that image and calculate the features for all proposals of an image simultaneously by calculating the feature map for whole image and projecting all the region proposal onto feature map. 
These features map for each proposal should be of fixed dimension because we have to pass these feature to FC layer for classification and refining the boundary of object. ROI Pooling layer is used to resize the feature map of each proposal to a fixed size.

RoI max pooling works by dividing the H x W roi region (region proposal) into h x w grid of sub-window of approximate size H/h x W/w and then max-pooling the values in each sub-window into the corresponding output grid cell.

Let's understand RoI Pooling with an example where conv feature map size is 8x8 and fixed output RoI size for each proposal is 2x2. Assumimg after applying multiple conv block on input image we get a 8x8xC where C is the depth of feature map or you can say number of channel.

Pooling is applied to each channel independently, for now we will ignore the depth/channel. 

1. 8x8 feature map

2. Now let's say we have one object proposal for an input image and after mapping it to the feature map it cover 6x5 area starting from (3,2) to (8,6) index. 

3. As in this case our RoI pooling output size is 2x2, so we will divide the 6x5  region to get 2x2 cell and apply max pooling. 

4. We will select maximum value (max pooling) from each sub-cell. Now this will be the output by RoI pooling layer. 

** 0.64 instead of 0.60

5. RoI pooling will be applied to all layer of feature map and final output will be 2x2xC size feature map and this will be the input to FC layer.

Importance of RoI Pooling-

Feature sharing: It allow to reuse the feature map for all object proposal hence feature sharing.

Training and testing time: It significantly speed up the training and testing, as it allow to train the network end-to-end. 

VGG-16 fine tuning for Fast R-CNN Network

VGG-16 network undergoes three transformation

• Last Max pooling layer is replaced by RoI Pooling layer.
• Network last fully connected layer and softmax layer are replaced with two sibling layers (a fully connected layer and softmax over K+1 categories and category specific bounding box regressors)
• Network is modified to take two inputs, a list of images and a list of RoI's in those images.

Fast R-CNN Loss Function

As Fast R-CNN have two sibling output layers at the end, it uses multi task loss to train both the layer simultaneously.

The First layer outputs a discrete probability distribution (per ROI) p = (p₀, p₁,...., p_k), over K+1 category. As usual, p is computed by softmax over K+1 outputs of a fully connected layer. This is the normal softmax layer that we use for classification over K object class plus one background class.

The Second layer outputs bounding-box offsets, t^k = (t^k_x, t^k_y, t^k_w, t^k_h), for each of the K object classes, for background class we don't need bounding-box. Here t^k specifies a scale-invarient translation and log-space height/width shift relative to an object proposal.

Each training ROI is labelled with a ground truth class u and bounding-box target v. Multi task loss function is defined as.

where u and v is ground truth, p and t^u is network outputs, L_cls(p,u) = -log p_u is log loss for true class u.

The second loss L_loc, is defined over a tuple of true bounding-box target for class u, v = (u_x, u_y, u_w, u_h) and predicted tuple t^u = (t^u_x, t^u_y, t^u_w, t^u_h), again for each class u. The hyper-parameter lambda is used to balance both the loss.

For bounding-box regression (L_loc) we use,

 where smooth L₁ function is, 

Smooth L₁ loss is less sensitive to the outliers than L₂ loss.

Main Results  

Three main results of this papers is:

• State-of-the-art mAP on VOC 2007, 2010, and 2012
• Fast training and testing compared to R-CNN, SPPnet
• Fine-tuning conv layers in VGG16 improves mAP

Miscellaneous

Fast R-CNN paper also talks about following thing that i haven't covered, if you want to know more please go through the original paper

• Truncated SVD for faster detection
• SVM vs Softmax for classification
• How does number of object proposal affect mAP

That's all for this post, hope you find this blog informative.
Thanks for reading !!

R-CNN : Object Detection

In this blog I will discuss about one of the CNN based Object Detection algorithm, R-CNN (Region based Convolutional Neural Network). Based on R-CNN there are two more object detection algorithm Fast R-CNN and Faster R-CNN. Now day's we use only Faster R-CNN out of these three but it's important to understand the base network first.  

So let's start.

What is object detection and how it is different than classification ?

In classification, given any image we have to predict the class id of the object present in image and in classification problems generally object occupy more than 70-80% region in image and rest is background. See below an example image. 

Example image for classification and it's output should be dog

In object detection problem, an image can have one or multiple object in it. Object detection algorithm have to detect the location (x, y, width and height in pixels) of the objects in the image and also have to correctly classify all the object present.

Example - let's say we have a dog detection model and if we run this model on the above image it should detect the bounding box covering the dog and classify it as dog.

Output of object detection model

If we see pipeline of any object detection algorithm, then it can be divided in three part first one is find the region in image where object can be, second one is if there is an object then which object it is and third one is find the closest bounding box surrounding that object.

Previous Method of Object Detection

Previous to these CNN based object detection network we were using sliding window based algorithms for object detection. In which we slide a window of WxH dimension over the image from top to bottom and crop these window regions from image and classify them with machine learning based algorithm like SVM. 

To detect different shape and size of object, we change the dimension and aspect ration of sliding window and iterate it again over the image.

This method is quite fast but problem is with the accuracy, as it's very difficult to cover the whole object in one sliding window and also classical machine learning algorithm fails to classify correctly if image is exposed to different lighting conditions or if object size is very small or large in image.

Moving forward let's see what is R-CNN.

R-CNN stand for Regions with CNN features. This algorithm was introduced in Rich Feature Hierarchies For Accurate Object Detection and Semantic Segmentation paper. This achieve mean average precision (mAP) of 53.3% on VOC 2012 which is 30% more than the previous best algorithm.

1. Input Image 2. Extracts around 2000 region proposals 3. Computes features for each proposal using a large CNN 4. Classifies each region using class-specific linear SVM

R-CNN object detection model consists of three module.

1. Region Proposal

Conventional object detection algorithm uses Sliding Window approach to search for object in image at each location. This method is very slow if we use CNN for classification at each location and also not accurate for object with different aspect ratio and size.

R-CNN uses Selective Search Algorithm to  generate category-independent region proposals. These proposals defines the set of candidate detection available to the detector. At test time for any given input image it generates 2000 category-independent region proposals.

Region proposal happen only during testing time not training time because during training time we use labelled ground truth as detection candidates. 

10 random region proposal out of 2000

In above image we can see 10 random region proposal of different size and aspect ration out of 2000 region proposals.

2. Feature Extraction

Region proposal gives us detection candidates, after this second step of RCNN is fixed length feature extraction using CNN network for each detection candidates.

Each region proposals bounding box is first dilated (expanded) by p (16) pixels, to get some image context around the original box.  

 

For each region proposals it generates a fixed length (4096) feature vector using CNN. To calculate the features it uses a CNN (AlexNet network) that have five convolutional layers and two fully connected layers and this network takes mean- subtracted input image of size 227X227. In order to compute the features for region proposal, each region should be of size 227x227. So regardless the size and aspect ratio of the different region proposal, it warp all candidate regions in 227x227 region before passing through CNN.

1. Input image with ground truth 2. Example of object wrapping to 227x227 size 3. Feature extraction for each wrapped images using AlexNet network, feature size is 4096

To explain the procedure i have used ground truth labels, in the above image we can see image with ground truth bounding box, it crops the object from image and resize to 227x227, then pass it to AlexNet network which give a 4096 length feature for each cropped ground truth, same happens during testing time with region proposals.

3. Region Classification

The feature vector for each region generated by CNN is scored by SVM that is trained for each class. For an image the feature matrix is typically 2000×4096 (2000 region proposal and 4096 length feature for each proposal) and the SVM weight matrix is 4096×N, where N is the number of classes. SVM will give probability value for each region proposal and depending upon threshold value region proposal will be classify as one of the N class or background.

After region classification non-maximum suppression is applied (for each class independently) to remove overlapping object. 

Bounding-box Regression

To reduce localization error, RCNN fine-tune the bounding box prediction of detected object by class-specific bounding box regressor branch. Input to bounding box regression is set of N training pairs {(P, G)} where P = {Px, Py, Pw, Ph} specifies the pixel coordinates of the center of the proposals (b-box) along with their width and height in pixels. Each ground-truth box G is specified in same way: G = {Gx,Gy,Gw,Gh}. Bounding box regressor inceases mAP by 3-4 point. 

R-CNN with bounding box regressor branch

Conclusion

So let’s wrap it up, R-CNN object detection algorithm is all about generating 2000 object proposal from input image using selective search algorithm then wrapping the each proposal region to fix size i.e. 227x227 to calculate the fixed length (4096) feature vector using CNN (AlexNet) and classify these feature vectors using class specific SVM followed by non-max suppression for each class independently and finally bounding box regression to fine-tune bounding box of predicted objects.

Drawback of R-CNN 

1. Training is a multistage pipeline. R-CNN first fine-tunes a ConvNet (AlexNet) on object proposals using log loss. Then, it fits SVM to ConvNet features. These SVM act as object detectors, replacing the softmax classifier learnt by fine-tuning. In the third training stage, bounding-box regressor are learned. 

2. Training is expensive in space and time. For SVM and bounding-box regressor training, features are extracted from each object proposal from each image and written to disk. These features require lots of storage unit and takes lots of time in training.  

3. Object Detection is slow. At test time, features are extracted from each object proposal in each test image. Detection with VGG16 as base network instead of Alexnet takes 47s per image on a GPU.

That's all for this blog, hope you find this blog informative.
Thanks for reading !!