Je veux détecter et COMPLÈTE de tous les possibles quadrilatère des formes à partir répartis au hasard des segments de ligne!
La photo jointe est un exemple, les lignes peuvent toujours apparaître dans des emplacements très différents.
Toute personne peut signaler à tout bon algorithme pour cela?
La solution est de détecter et prédire le jaune quadrilatère
Dans le cas de 11 segments de ligne, vous avez 330 façons de choisir quatre segments. Vous pouvez déterminer la probabilité de chaque combinaison de faire un quadrilatère, et la teneur de cette façon.
Il est possible d'avoir un Hough transformer détecter des formes autres que les lignes, mais il devient plus difficile de visualiser que l'accumulateur de l'espace auraient besoin de plus de deux dimensions. Les cercles peuvent être trouvés dans les trois dimensions (midX, midY, rayon), des ellipses dans les quatre (je crois). Je ne suis pas sûr exactement comment quelques paramètres que vous auriez besoin de modèle à un quadrilatère, et je crois que le rendement de la transformation de Hough commence à déposer lorsque vous obtenez plus de trois dimensions. L'accumulateur de l'espace devient si grande que le bruit augmente de façon significative.
Voici une question connexe, qui peut avoir quelques réponses intéressantes pour vous.
Laissez-nous savoir comment vous vous y prenez!
J'ai pris un coup de couteau à ce problème aujourd'hui, et téléchargé ma solution pour GitHub. Il y a trop de code pour poster ici.
Voici une capture d'écran montrant la sortie:
La solution que j'ai pris est en gros ce que j'ai décrit ci-dessus avant de cette édition.
L'évaluation se fait par le calcul d'une grossière erreur de score. C'est la somme de deux types d'erreurs:
Le deuxième type d'erreur pourrait être déterminée d'une façon plus robuste. Il était nécessaire de trouver une solution pour votre ensemble de données d'échantillon.
Je n'ai pas expérimenté avec d'autres ensembles de données. Il peut avoir besoin de quelques ajustements pour le rendre plus robuste. J'ai essayé d'éviter d'utiliser trop de paramètres, de sorte qu'il devrait être simple de s'adapter à un environnement particulier. Par exemple, pour le contrôle de la sensibilité à l'occlusion, comme on le voit dans votre image de l'échantillon.
Il trouve la solution dans environ 160ms sur mon ordinateur portable. Cependant, je n'ai pas fait tout d'optimisation des performances. Je m'attends à ce que les méthodes de trouver des combinaisons/combinaisons pourrait être optimisée si vous avez besoin d'une exécution plus proche en temps réel, comme c'est souvent le cas avec la vision par ordinateur expériences.
Sur quatre lignes peuvent être réalisés pour former un quadrilatère si vous n'avez pas imposer des contraintes sur les angles etc.
Image avec potentiellement mauvais pour les quadrilatères:
Probablement vous ne voulez pas inclure les quadrilatères comme le jaune, le montre dans mon exemple. Vous devriez avoir des contraintes sur les angles, minimum/maximum la taille, l'aspect ratio et le degré d'achèvement permis. Si 90 pour cent des lignes doivent être ajoutés dans l'ordre pour former un quadrilatère complet ce ne serait probablement pas un très bon candidat.
Je crains que vous aurez à tester toutes les combinaisons possibles de lignes et d'appliquer une heuristique sur eux pour leur donner des points. Nombre de points pour un angle proche de 90 degrés (si ce que vous voulez sont des rectangles), pour la perfection, pour des rapports d'aspect proche de celle attendue etc.
Mise à JOUR
À l'aide d'un système de points a des avantages sur l'application de règles strictes.
Disons que vous avez une règle stricte (en pseudo-code):
(angles == 90 +/- 10 degrees) && (line_completeness>50%)
Ce serait le travail, peut cependant conduire à des situations comme angles == 90 +/- 1 degree) && (line_completeness == 45%). Selon les règles de ce quadrilatère ne serait pas passer à cause de la mauvaise ligne de l'exhaustivité; toutefois, la qualité de la mesure des angles est exceptionnelle, toujours en train de faire un très bon candidat.
Il est préférable de donner des points. Disons de 20 points pour un angle d'exactement 90 degrés, tombant à 0 points pour un angle de 90 +/-15 degrés, et de 10 points pour l'ensemble des chaînes vers 0 points pour les lignes complètes par seulement 25% par exemple. Cela fait des angles plus important que la ligne de l'exhaustivité et crée également des conditions douces pour un problème qui n'a pas de règles absolues.
Je n'ai pas utiliser le C# de sorte que vous aurez à traduire le code. Le code suivant est en Java. Je l'ai testé avec le test. Je ne sais pas comment ajouter une pièce jointe à stackoverflow, de sorte que je suis y compris le code ici.
Il existe quatre classes (ShapeFinder, Ligne, Point, et Quadrilatère) et une classe de test (ShapeFinderTest):
ShapeFinder classe:
package stackoverflow;
import java.util.ArrayList;
import java.util.List;
public class ShapeFinder {
private List<Line> lines;
private List<Quadrilateral> allQuadrilaterals;
/*
* I am assuming your segments are in a list of arrays:
* [{{x1,y1,},{x2,y2}}, {{x1,y1,},{x2,y2}}, {{x1,y1,},{x2,y2}}]
* You can change this.
*
* So basically you call ShapeFinder with a list of your line segments.
*/
public ShapeFinder(List<Double[][]> allSegments) {
lines = new ArrayList<Line>(allSegments.size());
allQuadrilaterals = new ArrayList<Quadrilateral>();
for (Double[][] segment : allSegments) {
addSlopeInterceptForm(segment);
}
}
/**
* You call this function to compute all possible quadrilaterals for you.
*/
public List<Quadrilateral> completeQuadrilaterals() {
for (int w = 0; w < lines.size(); w++) {
for (int x = w + 1; x < lines.size(); x++) {
for (int y = x + 1; y < lines.size(); y++) {
for (int z = y + 1; z < lines.size(); z++) {
addQuadrilateral(w, x, y, z);
}
}
}
}
return allQuadrilaterals;
}
//assume {{x1,y1,},{x2,y2}}
private void addSlopeInterceptForm(Double[][] s) {
double x1 = s[0][0];
double y1 = s[0][1];
double x2 = s[1][0];
double y2 = s[1][1];
double m = (y1 - y2) / (x1 - x2);
double b = y2 - m * x2;
if (isInfinityOrNaN(m)) {
m = Double.NaN;
b = x1;
}
lines.add(new Line(m, b));
}
/*
* Given four lines, this function creates a quadrilateral if possible
*/
private void addQuadrilateral(int w, int x, int y, int z) {
Point wx = intersect(w, x);
Point wy = intersect(w, y);
Point wz = intersect(w, z);
Point xy = intersect(x, y);
Point xz = intersect(x, z);
Point yz = intersect(y, z);
if (notNull(wx) && notNull(xy) && notNull(yz) && notNull(wz) && isNull(wy) && isNull(xz)) {
allQuadrilaterals.add(new Quadrilateral(wx, xy, yz, wz));
}
}
private Point intersect(int c, int d) {
double m1 = lines.get(c).slope;
double b1 = lines.get(c).intercept;
double m2 = lines.get(d).slope;
double b2 = lines.get(d).intercept;
double xCor, yCor;
if ((isInfinityOrNaN(m1) && !isInfinityOrNaN(m2)) || (!isInfinityOrNaN(m1) && isInfinityOrNaN(m2))) {
xCor = isInfinityOrNaN(m1) ? b1 : b2;
yCor = isInfinityOrNaN(m1) ? m2 * xCor + b2 : m1 * xCor + b1;;
} else {
xCor = (b2 - b1) / (m1 - m2);
yCor = m1 * xCor + b1;
}
if (isInfinityOrNaN(xCor) || isInfinityOrNaN(yCor)) {
return null;
}
return new Point(xCor, yCor);
}
private boolean isInfinityOrNaN(double d){
return Double.isInfinite(d)||Double.isNaN(d);
}
private boolean notNull(Point p) {
return null != p;
}
private boolean isNull(Point p) {
return null == p;
}
}
Ligne de classe:
package stackoverflow;
public class Line {
double slope;
double intercept;
public Line(double slope, double intercept) {
this.slope = slope;
this.intercept = intercept;
}
}
Classe Point:
package stackoverflow;
class Point {
double xCor;
double yCor;
public Point(double xCor, double yCor) {
this.xCor = xCor;
this.yCor = yCor;
}
public String toString(){
return "("+xCor+","+yCor+")";
}
}
Le quadrilatère de la classe:
package stackoverflow;
public class Quadrilateral {
private Point w, x, y, z;
public Quadrilateral(Point w, Point x, Point y, Point z) {
this.w = w;
this.x = x;
this.y = y;
this.z = z;
}
public String toString() {
return "[" + w.toString() + ", " + x.toString() + ", " + y.toString() + ", " + z.toString() + "]";
}
}
UNITÉ DE TEST:
package stackoverflow;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
public class ShapeFinderTest {
@Test
public void testCompleteQuadrilaterals() {
List<Double[][]> lines = new ArrayList<>();
lines.add(new Double[][]{{2., 5.}, {6., 5.}});
lines.add(new Double[][]{{2., 1.}, {2., 5.}});
lines.add(new Double[][]{{2., 1.}, {6., 1.}});
lines.add(new Double[][]{{6., 5.}, {6., 1.}});
lines.add(new Double[][]{{0., 0.}, {5., 1.}});
lines.add(new Double[][]{{5., 5.}, {10., 25.}});
ShapeFinder instance = new ShapeFinder(lines);
List<Quadrilateral> result = instance.completeQuadrilaterals();
for (Quadrilateral q : result) {
System.out.println(q.toString());
}
}
}
À partir de ces exemples, je suppose que la question est plus le long des lignes de Trouver tous les quadrilatères qui ont une ligne de contenu entièrement dans chacun de ses côtés. Ce n'est pas clair du tout dans l'explication fournie.
Ci-dessous quelques raisonnablement facile à mettre en œuvre des pseudo-code. Maintenant, juste pour créer une structure de données pour éviter les O(N^4) de la complexité. Peut-être trier les lignes par poste ou dégradé.
i,j,k,l sont comme suit:
l
|---|
j| |k
|---|
i
extendIntersect est simplement une fonction qui étend les 2 lignes à l'infini (ou selon les limites que vous choisissez) et de revenir au point où ils se croisent, facile à faire mathématiquement.
onLine retourne vrai si un point est sur une ligne.
onSameSide retourne true si les deux points se trouvent sur le même côté de la ligne
for (Line i = lines[0]:lines[lineCount])
for (Line j = lines[1]:lines[lineCount])
Point ijIntersect = extendIntersect(i, j)
if (ijIntersect == NULL || onLine(ijIntersect, i) || onLine(ijIntersect, j))
continue;
for (Line k = lines[2]:lines[lineCount])
Point ikIntersect = extendIntersect(i, k)
if (ikIntersect == NULL || onLine(ikIntersect, i) || onLine(ikIntersect, k) ||
onSameSide(ijIntersect, ikIntersect, i)) continue
for (Line l = lines[3]:lines[lineCount])
Point jlIntersect = extendIntersect(j, l)
Point klIntersect = extendIntersect(k, l)
if (jlIntersect == NULL || onLine(jlIntersect, j) || onLine(jlIntersect, l) ||
klIntersect == NULL || onLine(klIntersect, k) || onLine(klIntersect, l) ||
onSameSide(jlIntersect, ijIntersect, j) ||
onSameSide(klIntersect, ikIntersect, k)) continue
printQuad(ijIntersect, ikIntersect, klIntersect, jlIntersect)
Une sorte de vérification des erreurs comme Drew Noakes a suggéré pourrait également être une bonne idée.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
