Corner Detection in 2D Vector Data
computer-vision, hierarchical-clustering, image-processing, image-segmentation, matlab
Solution
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.
Problem
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!