Peak detection in a 2D array | Hacker News Reader

Peak detection in a 2D array

stackoverflow.com

69 pointswheaties8 comments

I don't think there's a good solution to this problem without incorporating some kind of prior distribution, and a statistical model of what paws tend to look like. Heuristics will only take you so far.

edit: come to think of it, something like mean-shift or ICP would probably do very well on this.

Yes mean shift would do it nicely, heck most clustering methods should give good results - but I think they will need a paw model of some sort (even if it's just a basic template) to get up to the 98%+ accuracy levels.

I am not sure this answers the original question, but it seems like you can just look for the n highest peaks that don't have neighbors.

http://gist.github.com/574052

I had a similar problem, but with a QVGA-sized matrix and not just a small array like this guy.

I used some Numerical Recipes formulas to do a linear interpolation on the data and upscale it into a larger grid, then used OpenCV to threshold and then find contours.

It works pretty well, but I wish I could process the data faster. I fear using this Python example with mapping and overlaps would just run way way longer.

I'm pretty sure you can compute a contour from the raw data much more efficiently.

The problem is that I'm working with a sensor set that's way smaller, like 100x smaller. The peaks can be somewhere in the middle and the only way to locate those is by running an Nth order interpolation (or maybe doing something simpler like computing local averages)

Interesting problem. The solution I would try is the following.

1. Apply a low pass filter, such as convolution with a 2D gaussian mask. This will give you a bunch of (probably, but not necessarily floating point) values.

2. Perform a 2D non-maximal suppression using the known approximate radius of each paw pad (or toe).

This should give you the maximal positions without having multiple candidates which are close together. Just to clarify, the radius of the mask in step 1 should also be similar to the radius used in step 2. This radius could be selectable, or the vet could explicitly measure it beforehand (it will vary with age/breed/etc).

Some of the solutions suggested (mean shift, neural nets, and so on) probably will work to some degree, but are overly complicated and probably not ideal.

Convert it to an elevation model for which there are many tools.

Reply on news.ycombinator.com