OpenCV Selective Search for Object Detection

Today, you will learn how to use OpenCV Selective Search for object detection.

Today’s tutorial is Part 2 in our 4-part series on deep learning and object detection:

• Part 1: Turning any deep learning image classifier into an object detector with Keras and TensorFlow
• Part 2: OpenCV Selective Search for Object Detection (today’s tutorial)
• Part 3: Region proposal for object detection with OpenCV, Keras, and TensorFlow (next week’s tutorial)
• Part 4: R-CNN object detection with Keras and TensorFlow (publishing in two weeks)

Selective Search, first introduced by Uijlings et al. in their 2012 paper, Selective Search for Object Recognition, is a critical piece of computer vision, deep learning, and object detection research.

In their work, Uijlings et al. demonstrated:

1. How images can be over-segmented to automatically identify locations in an image that could contain an object
2. That Selective Search is far more computationally efficient than exhaustively computing image pyramids and sliding windows (and without loss of accuracy)
3. And that Selective Search can be swapped in for any object detection framework that utilizes image pyramids and sliding windows

Automatic region proposal algorithms such as Selective Search paved the way for Girshick et al.’s seminal R-CNN paper, which gave rise to highly accurate deep learning-based object detectors.

Furthermore, research with Selective Search and object detection has allowed researchers to create state-of-the-art Region Proposal Network (RPN) components that are even more accurate and more efficient than Selective Search (see Girshick et al.’s follow-up 2015 paper on Faster R-CNNs).

But before we can get into RPNs, we first need to understand how Selective Search works, including how we can leverage Selective Search for object detection with OpenCV.

To learn how to use OpenCV’s Selective Search for object detection, just keep reading.

OpenCV Selective Search for Object Detection

In the first part of this tutorial, we’ll discuss the concept of region proposals via Selective Search and how they can efficiently replace the traditional method of using image pyramids and sliding windows to detect objects in an image.

From there, we’ll review the Selective Search algorithm in detail, including how it over-segments an image via:

1. Color similarity
2. Texture similarity
3. Size similarity
4. Shape similarity
5. A final meta-similarity, which is a linear combination of the above similarity measures

I’ll then show you how to implement Selective Search using OpenCV.

Region proposals versus sliding windows and image pyramids

In last week’s tutorial, you learned how to turn any image classifier into an object detector by applying image pyramids and sliding windows.

As a refresher, image pyramids create a multi-scale representation of an input image, allowing us to detect objects at multiple scales/sizes:

Sliding windows operate on each layer of the image pyramid, sliding from left-to-right and top-to-bottom, thereby allowing us to localize where in an image a given object is:

There are a number of problems with the image pyramid and sliding window approach, but the two primary ones are:

1. It’s painfully slow. Even with an optimized-for-loops approach and multiprocessing, looping over each image pyramid layer and inspecting every location in the image via sliding windows is computationally expensive.
2. They are sensitive to their parameter choices. Different values of your image pyramid scale and sliding window size can lead to dramatically different results in terms of positive detection rate, false-positive detections, and missing detections altogether.

Given these reasons, computer vision researchers have looked into creating automatic region proposal generators that replace sliding windows and image pyramids.

The general idea is that a region proposal algorithm should inspect the image and attempt to find regions of an image that likely contain an object (think of region proposal as a cousin to saliency detection).

The region proposal algorithm should:

1. Be faster and more efficient than sliding windows and image pyramids
2. Accurately detect the regions of an image that could contain an object
3. Pass these “candidate proposals” to a downstream classifier to actually label the regions, thus completing the object detection framework

The question is, what types of region proposal algorithms can we use for object detection?

What is Selective Search and how can Selective Search be used for object detection?

The Selective Search algorithm implemented in OpenCV was first introduced by Uijlings et al. in their 2012 paper, Selective Search for Object Recognition.

Selective Search works by over-segmenting an image using a superpixel algorithm (instead of SLIC, Uijlings et al. use the Felzenszwalb method from Felzenszwalb and Huttenlocher’s 2004 paper, Efficient graph-based image segmentation).

An example of running the Felzenszwalb superpixel algorithm can be seen below:

From there, Selective Search seeks to merge together the superpixels to find regions of an image that could contain an object.

Selective Search merges superpixels in a hierarchical fashion based on five key similarity measures:

1. Color similarity: Computing a 25-bin histogram for each channel of an image, concatenating them together, and obtaining a final descriptor that is 25×3=75-d. Color similarity of any two regions is measured by the histogram intersection distance.
2. Texture similarity: For texture, Selective Search extracts Gaussian derivatives at 8 orientations per channel (assuming a 3-channel image). These orientations are used to compute a 10-bin histogram per channel, generating a final texture descriptor that is 8x10x=240-d. To compute texture similarity between any two regions, histogram intersection is once again used.
3. Size similarity: The size similarity metric that Selective Search uses prefers that smaller regions be grouped earlier rather than later. Anyone who has used Hierarchical Agglomerative Clustering (HAC) algorithms before knows that HACs are prone to clusters reaching a critical mass and then combining everything that they touch. By enforcing smaller regions to merge earlier, we can help prevent a large number of clusters from swallowing up all smaller regions.
4. Shape similarity/compatibility: The idea behind shape similarity in Selective Search is that they should be compatible with each other. Two regions are considered “compatible” if they “fit” into each other (thereby filling gaps in our regional proposal generation). Furthermore, shapes that do not touch should not be merged.
5. A final meta-similarity measure: A final meta-similarity acts as a linear combination of the color similarity, texture similarity, size similarity, and shape similarity/compatibility.

The results of Selective Search applying these hierarchical similarity measures can be seen in the following figure:

On the bottom layer of the pyramid, we can see the original over-segmentation/superpixel generation from the Felzenszwalb method.

In the middle layer, we can see regions being joined together, eventually forming the final set of proposals (top).

If you’re interested in learning more about the underlying theory of Selective Search, I would suggest referring to the following resources:

• Efficient Graph-Based Image Segmentation (Felzenszwalb and Huttenlocher, 2004)
• Selective Search for Object Recognition (Uijlings et al., 2012)
• Selective Search for Object Detection (C++/Python) (Chandel/Mallick, 2017)

Selective Search generates regions, not class labels

A common misconception I see with Selective Search is that readers mistakenly think that Selective Search replaces entire object detection frameworks such as HOG + Linear SVM, R-CNN, etc.

In fact, a couple of weeks ago, PyImageSearch reader Hayden emailed in with that exact same question:

Hi Adrian, I am using Selective Search to detect objects with OpenCV.

However, Selective Search is just returning bounding boxes — I can’t seem to figure out how to get labels associated with these bounding boxes.

So, here’s the deal:

1. Selective Search does generate regions of an image that could contain an object.
2. However, Selective Search does not have any knowledge of what is in that region (think of it as a cousin to saliency detection).
3. Selective Search is meant to replace the computationally expensive, highly inefficient method of exhaustively using image pyramids and sliding windows to examine locations of an image for a potential object.
4. By using Selective Search, we can more efficiently examine regions of an image that likely contain an object and then pass those regions on to a SVM, CNN, etc. for final classification.

If you are using Selective Search, just keep in mind that the Selective Search algorithm will not give you class label predictions — it is assumed that your downstream classifier will do that for you (the topic of next week’s blog post).

But in the meantime, let’s learn how we can use OpenCV Selective Search in our own projects.

Project structure

Be sure to grab the .zip for this tutorial from the “Downloads” section. Once you’ve extracted the files, you may use the tree command to see what’s inside:

$ tree
.
├── dog.jpg
└── selective_search.py

0 directories, 2 files

Our project is quite simple, consisting of a Python script (selective_search.py) and a testing image (dog.jpg).

In the next section, we’ll learn how to implement our Selective Search script with Python and OpenCV.

Implementing Selective Search with OpenCV and Python

We are now ready to implement Selective Search with OpenCV!

Open up a new file, name it selective_search.py, and insert the following code:

# import the necessary packages
import argparse
import random
import time
import cv2

# construct the argument parser and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-i", "--image", required=True,
	help="path to the input image")
ap.add_argument("-m", "--method", type=str, default="fast",
	choices=["fast", "quality"],
	help="selective search method")
args = vars(ap.parse_args())

# load the input image
image = cv2.imread(args["image"])

# initialize OpenCV's selective search implementation and set the
# input image
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()
ss.setBaseImage(image)

# check to see if we are using the *fast* but *less accurate* version
# of selective search
if args["method"] == "fast":
	print("[INFO] using *fast* selective search")
	ss.switchToSelectiveSearchFast()

# otherwise we are using the *slower* but *more accurate* version
else:
	print("[INFO] using *quality* selective search")
	ss.switchToSelectiveSearchQuality()

• The "fast" method: switchToSelectiveSearchFast
• The "quality" method: switchToSelectiveSearchQuality

Generally, the faster method will be suitable; however, depending on your application, you might want to sacrifice speed to achieve better quality results (more on that later).

Let’s go ahead and perform Selective Search with our image:

# run selective search on the input image
start = time.time()
rects = ss.process()
end = time.time()

# show how along selective search took to run along with the total
# number of returned region proposals
print("[INFO] selective search took {:.4f} seconds".format(end - start))
print("[INFO] {} total region proposals".format(len(rects)))

To run Selective Search, we simply call the process method on our ss object (Line 37). We’ve set timestamps around this call, so we can get a feel for how fast the algorithm is; Line 42 reports the Selective Search benchmark to our terminal.

Subsequently, Line 43 tells us the number of region proposals the Selective Search operation found.

Now, what fun would finding our region proposals be if we weren’t going to visualize the result? Zero fun. To wrap up, let’s draw the output on our image:

# loop over the region proposals in chunks (so we can better
# visualize them)
for i in range(0, len(rects), 100):
	# clone the original image so we can draw on it
	output = image.copy()

	# loop over the current subset of region proposals
	for (x, y, w, h) in rects[i:i + 100]:
		# draw the region proposal bounding box on the image
		color = [random.randint(0, 255) for j in range(0, 3)]
		cv2.rectangle(output, (x, y), (x + w, y + h), color, 2)

	# show the output image
	cv2.imshow("Output", output)
	key = cv2.waitKey(0) & 0xFF

	# if the `q` key was pressed, break from the loop
	if key == ord("q"):
		break

OpenCV Selective Search results

We are now ready to apply Selective Search with OpenCV to our own images.

Start by using the “Downloads” section of this blog post to download the source code and example images.

From there, open up a terminal, and execute the following command:

$ python selective_search.py --image dog.jpg 
[INFO] using *fast* selective search
[INFO] selective search took 1.0828 seconds
[INFO] 1219 total region proposals

Here, you can see that OpenCV’s Selective Search “fast mode” took ~1 second to run and generated 1,219 bounding boxes — the visualization in Figure 4 shows us looping over each of the regions generated by Selective Search and visualizing them to our screen.

If you’re confused by this visualization, consider the end goal of Selective Search: to replace traditional computer vision object detection techniques such as sliding windows and image pyramids with a more efficient region proposal generation method.

Thus, Selective Search will not tell you what is in the ROI, but it tells you that the ROI is “interesting enough” to passed on to a downstream classifier (ex., SVM, CNN, etc.) for final classification.

Let’s apply Selective Search to the same image, but this time, use the --method quality mode:

$ python selective_search.py --image dog.jpg --method quality
[INFO] using *quality* selective search
[INFO] selective search took 3.7614 seconds
[INFO] 4712 total region proposals

The “quality” Selective Search method generated 286% more region proposals but also took 247% longer to run.

Whether or not you should use the “fast” or “quality” mode is dependent on your application.

In most cases, the “fast” Selective Search is sufficient, but you may choose to use the “quality” mode:

1. When performing inference and wanting to ensure you generate more quality regions to your downstream classifier (of course, this means that real-time detection is not a concern)
2. When using Selective Search to generate training data, thereby ensuring you generate more positive and negative regions for your classifier to learn from

Where can I learn more about OpenCV’s Selective Search for object detection?

In next week’s tutorial, you’ll learn how to:

1. Use Selective Search to generate object detection proposal regions
2. Take a pre-trained CNN and classify each of the regions (discarding any low confidence/background regions)
3. Apply non-maxima suppression to return our final object detections

And in two weeks, we’ll use Selective Search to generate training data and then fine-tune a CNN to perform object detection via region proposal.

This has been a great series of tutorials so far, and you don’t want to miss the next two!

Summary

In this tutorial, you learned how to perform Selective Search to generate object detection proposal regions with OpenCV.

Selective Search works by over-segmenting an image by combining regions based on five key components:

1. Color similarity
2. Texture similarity
3. Size similarity
4. Shape similarity
5. And a final similarity measure, which is a linear combination of the above four similarity measures

It’s important to note that Selective Search itself does not perform object detection.

Instead, Selective Search returns proposal regions that could contain an object.

The idea here is that we replace our computationally expensive, highly inefficient sliding windows and image pyramids with a less expensive, more efficient Selective Search.

Next week, I’ll show you how to take the proposal regions generated by Selective Search and then run an image classifier on top of them, allowing you to create an ad hoc deep learning-based object detector!

Stay tuned for next week’s tutorial.

To download the source code to this post (and be notified when the next tutorial in this series publishes), simply enter your email address in the form below!