Reconnaître les segments de ligne d'une séquence de points

Question

Étant donné une entrée de points 2D, je voudrais les segmenter dans des lignes.Donc, si vous dessinez une ligne de style zig-zag, chacun des segments doit être reconnu comme une ligne.Habituellement, j'utiliserais d'OpenCV CVhoughlines ou une approche similaire (PCA avec un démaquillant sur valeur), mais dans ce cas, le programme n'est pas autorisé à faire des erreurs "fausses positives".Si l'utilisateur tire une ligne et que ce n'est pas reconnu - c'est bon, mais si l'utilisateur dessine un curcle et qu'il sort comme un carré - ce n'est pas correct.Donc, j'ai une limite supérieure sur l'erreur - mais si c'est une ligne longue et que certains des points ont une plus grande distance de la ligne approximée, c'est de nouveau.Résumé:

Détection -line -Non faux positifs Erreur de réglage de manière dynamique

Oh, et les points sont dessinés en séquence, tout comme le dessin des mains.

au moins il ne doit pas nécessairement être rapide.C'est pour un outil de croquis.Quelqu'un a une idée?

Answer 1

This has the same difficulty as voice and gesture recognition. In other words, you can never be 100% sure that you've found all the corners/junctions, and among those you've found you can never be 100% sure they are correct. The reason you can't be absolutely sure is because of ambiguity. The user might have made a single stroke, intending to create two lines that meet at a right angle. But if they did it quickly, the 'corner' might have been quite round, so it wouldn't be detected.

So you will never be able to avoid false positives. The best you can do is mitigate them by exploring several possible segmentations, and using contextual information to decide which is the most likely.

There are lots of papers on sketch segmentation every year. This seems like a very basic thing to solve, but it is still an open topic. The one I use is out of Texas A&M, called MergeCF. It is nicely summarized in this paper: http://srlweb.cs.tamu.edu/srlng_media/content/objects/object-1246390659-1e1d2af6b25a2ba175670f9cb2e989fe/mergeCF-sbim09-fin.pdf.

Basically, you find the areas that have high curvature (higher than some fraction of the mean curvature) and slow speed (so you need timestamps). Combining curvature and speed improves the initial fit quite a lot. That will give you clusters of points, which you reduce to a single point in some way (e.g. the one closest to the middle of the cluster, or the one with the highest curvature, etc.). This is an 'over fit' of the stroke, however. The next stage of the algorithm is to iteratively pick the smallest segment, and see what would happen if it is merged with one of its neighboring segments. If merging doesn't increase the overall error too much, you remove the point separating the two segments. Rinse, repeat, until you're done.

It has been a while since I've looked at the new segmenters, but I don't think there have been any breakthroughs.

In my implementation I use curvature median rather than mean in my initial threshold, which seems to give me better results. My heavily modified implementation is here, which is definitely not a self-contained thing, but it might give you some insight. http://code.google.com/p/pen-ui/source/browse/trunk/thesis-code/src/org/six11/sf/CornerFinder.java