I have many point patterns, and I want to detect those patterns that have points arranged in lines that may be curved, intersected or broken. For example, on the following picture, the upper left pattern is not interesting but other three patterns are those that I want to detect.

enter image description here

Not all points in the interesting patterns are aligned. Some points in those patterns are still random. The lines do not have any parametric form, so I cannot use the Hough transform. I searched some literature on spatial statistics, for example this one and only found metrics for assessing spatial uniformity and detecting clusters such as the index of dispersion. Which metrics exist for detecting the presence of not only clusters but curved lines?

I also need to do the same analysis for three-dimensional points. How to detect those 3D patterns that have points roughly arranged in lines and surfaces that can be wiggly?

  • $\begingroup$ interesting problem! Especially considering the probabilistic model beneath! Out of interest: have you tried throwing PCA at your problem? If that works for the very "linear" distribution in the bottom right, but not for the top right, maybe with locally chosen subsets of your points? $\endgroup$ Feb 14 at 10:48
  • $\begingroup$ I am not an image processing expert but would guess that 2D and 3D correlations would be effective at detecting these as long as offset parameters are swept (such as rotation and gain). Further each reference pixel could be enlarged (with less weight at the perimeters) to allow for robust detection even in the presence of small localized offset variation for each pixels location (displacement noise). $\endgroup$ Feb 14 at 17:05
  • 1
    $\begingroup$ Why don't you make a connected graph of the points by using a greedy algorithm. Just connect points to the nearest neighbor until the whole set of points are connected. (Add the shortest edges in order.) Then you could do some analysis on the graph. One measure would be checking the angles made. When there is a line or a curve, then angle stays similar. $\endgroup$
    – IanJ
    Feb 14 at 20:02
  • $\begingroup$ @MarcusMüller I did PCA after reading your comment. Thanks! Combining with clustering suggested in the answer found more or less flat/straight patterns. $\endgroup$ Mar 24 at 8:26
  • $\begingroup$ @IanJ Applying graph theory. Thanks! As to angles: most of the data are 3D, many patterns with points arranged in curved surfaces. $\endgroup$ Mar 24 at 8:29

Perhaps you could perform blob detection to find the individual dots and then map their location to a 2d space, that preserves their spatial structure, through the use of some measure for example the center of mass of the blob.

Once you have mapped each blob to its coordinates in the 2d space you could perform clustering or fit a regressor since the patterns somewhat resemble piecewise polynomials, you could model them as second or third degree polynomials, and build your algorithm upon RANSAC, it is a probabilistic algorithm that fits a model while discarding the outliers, you could also introduce some extra hyperparameters:

  1. the percent threshold of points that minimize the cost function (you could use the sum of squared errors as a base cost function to build upon) and thus belong in the pattern.
  2. the number of piecewise relations if you opt in the piecewise polynomial approach. Then you could exclude valid points that fit one branch of the piece wise polynomials from next iterations until all such polynomials are found.

Another classic algorithm that can cluster points based on their geodesic structure rather than just the distance would be DBSCAN, choosing a suitable $\epsilon$ for your dataset as the points that belong to the pattern are rather close to each other. A more complex classical machine learning algorithm is ISOMAP, it can also cluster points that based on geodesic properties


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.