Corner Detection in 2D Vector Data

Question

I am trying to detect corners (x/y coordinates) in 2D scatter vectors of data.

The data is from a laser rangefinder and our current platform uses Matlab (though standalone programs/libs are an option, but the Nav/Control code is on Matlab so it must have an interface).

Corner detection is part of a SLAM algorithm and the corners will serve as the landmarks.

I am also looking to achieve something close to 100Hz in terms of speed if possible (I know its Matlab, but my data set is pretty small.)

Sample Data:

[Blue is the raw data, red is what I need to detect. (This view is effectively top down.)]

[Actual vector data from above shots]

Thus far I've tried many different approaches, some more successful than others. I've never formally studied machine vision of any kind.

My first approach was a homebrew least squares line fitter, that would split lines in half resurivly until they met some r^2 value and then try to merge ones with similar slope/intercepts. It would then calculate the intersections of these lines. It wasn't very good, but did work around 70% of the time with decent accuracy, though it had some bad issues with missing certain features completely.

My current approach uses the clusterdata function to segment my data based on mahalanobis distance, and then does basically the same thing (least squares line fitting / merging). It works ok, but I'm assuming there are better methods.

[Source Code to Current Method] [cnrs, dat, ~, ~] = CornerDetect(data, 4, 1) using the above data will produce the locations I am getting.

I do not need to write this from scratch, it just seemed like most of the higher-class methods are meant for 2D images or 3D point clouds, not 2D scatter data. I've read a lot about Hough transforms and all sorts of data clustering methods (k-Means etc). I also tried a few canned line detectors without much success. I tried to play around with Line Segment Detector but it needs a greyscale image as an input and I figured it would be prohibitivly slow to convert my vector into a full 2D image to feed it into something like LSD.

Any help is greatly appreciated!

Fillmore

Answer 1

I'd approach it as a problem of finding extrema of curvature that are stable at multiple scales - and the split-and-merge method you have tried with lines hints at that.

Tinishatinker

Do you have any algorithm recommendations or approaches I should be looking at? (The split and merge was not a textbook copy but merely something I wrote after getting frustrated reading all these whitepapers that only give poor psuedocode.) – Fillmore

Most of the recent work has focused on surfaces. An old but good one in 2D is Andre Lejeune's "curvature consistency". A more recent one is Leontiev's CSS: cs.bgu.ac.il/~icbv061/StudentProjects/ICBV061/… – Tinishatinker

Answer 2

You could use harris corner detector for detecting corners.

Tropophilous

Harris for the above scattered data set? Or for processing the entire depth frame? All the harris implementations I've found only accept greyscale or B/W full frame images. – Fillmore

You could rescale your data (the range of x and y) within a certain range so that the points become continuous , may be perform a bit of dilation, create an image(from this data) and perform Harris. Harris will work for binary images also, it just computes eigenvalues of a matrix which contains gradient magnitudes in orthogonal directions within a window. In most cases it can be made faster using dynamic programming (known as integral images) and the complexity depends on the range (xmax, ymax) of your data – Tropophilous

Nonsense, as the OP correctly points out, his data are not images. – Tinishatinker

If intensities are not present does not mean it cannot be represented as an image, the data is a collection of points, and you could represent those points as 1 and the rest as 0 and create a binary image – Tropophilous

Harris will also give you corner detections (little imprecise due to scaling) for lines but also for the squiggles present in the image, for that you will need to perform HOG over blocks of the image and see if data is present in only 2 bins, the block size should be sufficiently large and would be application dependent. vlFeat can be used for HOG. code: data(:, 1) = data(:, 1) + 1127; data = data/4;data = ceil(data+1);img = zeros(557, 902); for i = 1:620 img(data(i, 1), data(i, 2)) = 1; end imgs = imresize(img, 0.05); C = corner(imgs); imshow(imgs); hold on; plot(C(:,1), C(:,2), 'r*'); – Tropophilous

It would be ok if the squiggles were detected landmarks IFF they are consistently (within reason) detected from different angles. The laserscanner has bad noise as larger distances, and it's hard to differentiate between noise and object curvature at distances over 3 meters. – Fillmore

Using your suggestion, I arrived at [this] which is ok, but it still suffers badly from false positives. What is HOG? I have vl_feat installed from when I was initially searching for a solution. It seems like Harris would be hard to tune for this application or am I wrong? Should I draw lines between each pixel to give smoother/better results? – Fillmore

oh yes, if you could draw lines between pixels which are nearby it should solve the problem – Tropophilous