# How to detect corners in a binary images with OpenGL?

I have binary 160x120 images such as:

I would like to detect corners of those white blobs. They are previously closed by mathematical morphology so there shouldn't have any inner corners. In this specific case, I would want 16 corners, like:

My first attempt was using some OpenCV functions like goodFeaturesToTrack or FAST but they are particularly slow (plus FAST is very unstable). My idea would be to do such a computation on the GPU, as my source image comes from it. I looked for ideas on the web on how to write such shaders (I'm using OpenGL ES 2.0), but found nothing concrete. Any idea how I could start such an algorithm?

• FAST is slow? :) – endolith Oct 11 '11 at 22:00
• yes, funny right? in fact, it's faster than precedent algorithms like SURF or SIFT, but it's less precise, quite unstable from one image to another and still not fast enough to be done on the CPU – Stéphane Péchard Oct 12 '11 at 7:07
• How important is it to accurately detect these on every frame? How quickly do the rectangles move? Is it OK to detect the corners on most frames and to interpolate them on the frames where the algorithm misses? – justis Dec 19 '11 at 20:14
• @justis well, the way I do it right now (through the use of OpenCV's cvFindContours() and cvApproxPoly() functions) is not very stable over time, so I filter the result with a low-pass filter, introducing lag. Do you think I can get a more stable result with an interpolation? – Stéphane Péchard Dec 20 '11 at 8:44

What size images are you operating on? At what frame rate? On what hardware? FAST is pretty, erm, fast in my experience.

I've also seen FAST used as a ROI detector with goodFeaturesToTrack run on the ROIs identified to provide better stability without running the penalty of gFTT on the whole image.

The "Harris" corner detector is also potentially very quick as it is made up of very simple operations (no sqrt() per pixel for example!) - not as stable as gFTT, but possibly more so than FAST.

(In terms of GPU implementation, Googling gpu corner seems to present quite a lot of links, but I have no idea how suitable they might be - I tend to implement in FPGA.)

• My images are 160x120, supposedly at 30fps, on an iPhone, but of course, the application has a lot more to do :-) I've seen an app implementing FAST quite quickly on such a device, but it was just a demo only doing that... That's why I'm looking towards gpu-based solutions. – Stéphane Péchard Oct 12 '11 at 9:50

I just happened to be implementing something like this on OpenGL ES 2.0 using Harris corner detection, and while I'm not completely finished, I thought I'd share the shader-based implementation I have so far. I've done this as part of an iOS-based open source framework, so you can check out the code if you're curious as to how some particular step works.

To do this, I use the following steps:

• Reduce the image to its luminance values using a dot product of the RGB values with the vector (0.2125, 0.7154, 0.0721).
• Calculate the X and Y derivatives by subtracting the red channel values from the pixels left and right and above and below the current pixel. I then store the x derivative squared in the red channel, the Y derivative squared in the green channel, and the product of X and Y derivatives in the blue channel. The fragment shader for this looks like the following:

precision highp float;

varying vec2 textureCoordinate;
varying vec2 leftTextureCoordinate;
varying vec2 rightTextureCoordinate;

varying vec2 topTextureCoordinate;
varying vec2 bottomTextureCoordinate;

uniform sampler2D inputImageTexture;

void main()
{
float topIntensity = texture2D(inputImageTexture, topTextureCoordinate).r;
float bottomIntensity = texture2D(inputImageTexture, bottomTextureCoordinate).r;
float leftIntensity = texture2D(inputImageTexture, leftTextureCoordinate).r;
float rightIntensity = texture2D(inputImageTexture, rightTextureCoordinate).r;

float verticalDerivative = abs(-topIntensity + bottomIntensity);
float horizontalDerivative = abs(-leftIntensity + rightIntensity);

gl_FragColor = vec4(horizontalDerivative * horizontalDerivative, verticalDerivative * verticalDerivative, verticalDerivative * horizontalDerivative, 1.0);
}


where the varyings are just the offset texture coordinates in each direction. I precalculate these in the vertex shader to eliminate dependent texture reads, which are notoriously slow on these mobile GPUs.

• Apply a Gaussian blur to this derivative image. I used a separated horizontal and vertical blur, and take advantage of hardware texture filtering to do a nine-hit blur with only five texture reads on each pass. I describe this shader in this Stack Overflow answer.

• Run the actual Harris corner detection calculation using the blurred input derivative values. In this case, I'm actually using the calculation described by Alison Noble in her Ph.D. dissertation "Descriptions of Image Surfaces". The shader that handles this looks like the following:

varying highp vec2 textureCoordinate;

uniform sampler2D inputImageTexture;

const mediump float harrisConstant = 0.04;

void main()
{
mediump vec3 derivativeElements = texture2D(inputImageTexture, textureCoordinate).rgb;

mediump float derivativeSum = derivativeElements.x + derivativeElements.y;

// This is the Noble variant on the Harris detector, from
// Alison Noble, "Descriptions of Image Surfaces", PhD thesis, Department of Engineering Science, Oxford University 1989, p45.
mediump float harrisIntensity = (derivativeElements.x * derivativeElements.y - (derivativeElements.z * derivativeElements.z)) / (derivativeSum);

// Original Harris detector
//     highp float harrisIntensity = derivativeElements.x * derivativeElements.y - (derivativeElements.z * derivativeElements.z) - harrisConstant * derivativeSum * derivativeSum;

gl_FragColor = vec4(vec3(harrisIntensity * 10.0), 1.0);
}

• Perform local non-maximum suppression and apply a threshold to highlight the pixels that pass. I use the following fragment shader to sample the eight pixels in the neighborhood of a central pixel and identify whether or not it is the maximum in that grouping:

uniform sampler2D inputImageTexture;

varying highp vec2 textureCoordinate;
varying highp vec2 leftTextureCoordinate;
varying highp vec2 rightTextureCoordinate;

varying highp vec2 topTextureCoordinate;
varying highp vec2 topLeftTextureCoordinate;
varying highp vec2 topRightTextureCoordinate;

varying highp vec2 bottomTextureCoordinate;
varying highp vec2 bottomLeftTextureCoordinate;
varying highp vec2 bottomRightTextureCoordinate;

void main()
{
lowp float bottomColor = texture2D(inputImageTexture, bottomTextureCoordinate).r;
lowp float bottomLeftColor = texture2D(inputImageTexture, bottomLeftTextureCoordinate).r;
lowp float bottomRightColor = texture2D(inputImageTexture, bottomRightTextureCoordinate).r;
lowp vec4 centerColor = texture2D(inputImageTexture, textureCoordinate);
lowp float leftColor = texture2D(inputImageTexture, leftTextureCoordinate).r;
lowp float rightColor = texture2D(inputImageTexture, rightTextureCoordinate).r;
lowp float topColor = texture2D(inputImageTexture, topTextureCoordinate).r;
lowp float topRightColor = texture2D(inputImageTexture, topRightTextureCoordinate).r;
lowp float topLeftColor = texture2D(inputImageTexture, topLeftTextureCoordinate).r;

// Use a tiebreaker for pixels to the left and immediately above this one
lowp float multiplier = 1.0 - step(centerColor.r, topColor);
multiplier = multiplier * 1.0 - step(centerColor.r, topLeftColor);
multiplier = multiplier * 1.0 - step(centerColor.r, leftColor);
multiplier = multiplier * 1.0 - step(centerColor.r, bottomLeftColor);

lowp float maxValue = max(centerColor.r, bottomColor);
maxValue = max(maxValue, bottomRightColor);
maxValue = max(maxValue, rightColor);
maxValue = max(maxValue, topRightColor);

gl_FragColor = vec4((centerColor.rgb * step(maxValue, centerColor.r) * multiplier), 1.0);
}


This process generates a cornerness map from your objects that looks like this:

The following points are identified as corners based on the non-maximum suppression and thresholding:

With proper thresholds set for this filter, it can identify all 16 corners in this image, although it does tend to place the corners a pixel or so inside the actual edges of the object.

On an iPhone 4, this corner detection can be run at 20 FPS on 640x480 frames of video coming from the camera, and an iPhone 4S can easily process video of that size at 60+ FPS. This should be a good deal faster than CPU-bound processing for a task like this, although right now the process of reading back the points is CPU-bound and a little slower than it should be.

If you want to see this in action you can grab the code for my framework and run the FilterShowcase example that comes with it. The Harris corner detection example there runs on live video from the device camera, although as I mentioned the reading back of corner points currently occurs on the CPU, which is really slowing this down. I'm moving to a GPU-based process for this, as well.

• Very nice! I follow your framework on github, it seems really interesting, congrats! – Stéphane Péchard May 2 '12 at 11:45
• Do you have an example somewhere how to get the corner coordinates actually back to the CPU? Is there some smart GPU way or does it require a readback and then looping on the CPU through the returned bitmap looking for marked pixels? – Quasimondo Jan 8 '14 at 16:56
• @Quasimondo - I've been working on using histogram pyramids for point extraction: tevs.eu/files/vmv06.pdf in order to avoid the CPU-bound iteration over pixels for the corner detection. Been a little distracted lately, so haven't quite finished this, but I'd like to soon. – Brad Larson Jan 8 '14 at 17:01
• Hi @BradLarson, I know this is a very old thread and thank you for your answer. I just checked KGPUImageHarrisCornerDetection.m in the GPUImage framework. To extract corner location from image, you have used glReadPixels to read image into buffer and then looped on the buffer to store points with colotByte>0 in an Array. Is there any way to do this all in GPU where we don't have to read image in buffer and loop? – Sahil Bajaj Dec 26 '17 at 10:16
• @SahilBajaj - One technique I've seen (and not yet had the time to implement) is to use histogram pyramids to do fast extraction of points from sparse images like this. That would significantly speed this up. – Brad Larson Dec 27 '17 at 2:32

"Robust" corner detectors like Shi-Tomasi and Moravec are notoriously slow. check them here - http://en.wikipedia.org/wiki/Corner_detection FAST probably is the only good enough lightweight corner detector. You can improve FAST by doing non-maximum suppression - chose FAST output with best "cornerness" score (there are several intuitive way to calculate it, including Shi-Tomasi and Moravec as cornerness score) You also have a choice from several FAST detectors - from FAST-5 to FAST-12 and FAST_ER(last one is probably too huge for mobile) Another way is to get generated FAST - get FAST code generator from author site and train it on the set of likely images. http://www.edwardrosten.com/work/fast.html

Not really GPU-specific, but the SUSAN algorithm by Steve Smith is good for corner detection.

The algorithm is pretty simple, as the source code in C shows.