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.
