Я хочу обнаружить и ПОЛНЫЙ все возможные четырехугольники из случайно расположенных сегментов линии!
Приведенное изображение является примером, строки могут всегда отображаться в самых разных местах.
Любой может указать на какой-либо хороший алгоритм для этого?
Решение обнаруживает и предсказать желтый четырехугольник
В случае 11 сегментов линии у вас есть 330 способов выбора четырех сегментов. Вы могли бы определить вероятность того, что каждая комбинация сделает четырехугольник, и сравните этот путь.
Возможно, что формы преобразования Хафа обнаруживают другие формы, отличные от строк, хотя становится сложнее визуализировать, так как пространство аккумулятора потребует более двух измерений. Круги можно найти в трех измерениях (midX, midY, radius), эллипсов в четырех (я считаю). Я не уверен точно, как мало параметров вам нужно, чтобы моделировать четырехугольник, и я считаю, что производительность преобразования Hough начинает снижаться, когда вы получаете более трех измерений. Объем аккумулятора становится настолько большим, что отношение шума значительно увеличивается.
Здесь связанный вопрос, который может содержать некоторые интересные ответы для вас.
Сообщите нам, как вы продвигаетесь!
Сегодня я ударил по этой проблеме, а загрузил мое решение в GitHub. Здесь слишком много кода.
Вот скриншот, показывающий результат:
Решение, которое я принял, в основном, было описано выше перед этим редактированием.
Оценка работает, вычисляя грубую оценку ошибки. Это сумма двух разных типов ошибок:
Второй тип ошибки можно определить более надежным способом. Необходимо было найти решение для вашего набора данных образца.
Я не экспериментировал с другими наборами данных. Это может потребовать некоторой настройки, чтобы сделать ее более надежной. Я старался избегать использования слишком большого количества параметров, чтобы было просто настроить их для конкретной среды. Например, чтобы контролировать чувствительность к окклюзии, как видно на вашем образце.
Он находит решение около 160 мс на моем ноутбуке. Однако я не делал оптимизаций производительности. Я ожидаю, что методы поиска комбинаций/перестановок могут быть значительно оптимизированы, если вам нужно, чтобы они приближались к реальному времени, как это часто бывает в экспериментах с компьютерным видением.
О любых четырех строках можно заполнить, чтобы сформировать четырехугольник, если вы не накладываете ограничений на углы и т.д.
Изображение с потенциально неправильными четырехугольными:
Вероятно, вы не хотите включать четырехугольники, такие как желтый, показанный в моем примере. У вас должны быть ограничения на углы, минимальный/максимальный размер, соотношение сторон и степень разрешенного завершения. Если 90 процентов строк необходимо добавить, чтобы сформировать полный четырехугольник, это, вероятно, не очень хороший кандидат.
Я боюсь, что вам придется протестировать каждую возможную комбинацию линий и применить к ним heuristic, чтобы дать им очки. Множество точек для углов, близких к 90 градусам (если вы хотите прямоугольники), для полноты, для пропорций, близких к ожидаемому, и т.д.
UPDATE
Использование точечной системы имеет преимущества перед применением строгих правил.
Скажем, у вас есть строгое правило (в псевдокоде):
(angles == 90 +/- 10 degrees) && (line_completeness>50%)
Это сработает, однако может привести к ситуациям типа angles == 90 +/- 1 degree) && (line_completeness == 45%). Согласно правилам, этот четырехугольник не пройдет из-за плохой завершенности линии; однако качество углов является исключительным, все еще делая его очень хорошим кандидатом.
Лучше дать очки. Скажите 20 баллов за угол ровно на 90 градусов, упав до 0 баллов за угол 90 +/- 15 градусов и 10 очков для полных линий в сторону 0 очков для линий, завершенных всего на 25%, например. Это делает углы более важными, чем линейность, а также создает более мягкие условия для проблемы, которая не имеет абсолютных правил.
Я не использую С#, поэтому вам придется переводить код. Следующий код находится в Java. Я проверил его с включенным тестовым случаем. Я еще не знаю, как добавить вложение в stackoverflow, поэтому я включаю в себя фактический код здесь.
Существует четыре класса (ShapeFinder, Line, Point и Quadrilateral) и один тестовый класс (ShapeFinderTest):
Класс ShapeFinder:
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;
}
}
Класс линии:
package stackoverflow;
public class Line {
double slope;
double intercept;
public Line(double slope, double intercept) {
this.slope = slope;
this.intercept = intercept;
}
}
Класс точки:
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+")";
}
}
Четырехугольный класс:
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 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());
}
}
}
Из примеров, я предполагаю, что вопрос больше соответствует строкам Найти все четырехугольники, которые содержат линию, содержащуюся полностью в каждой из ее сторон. Это не совсем понятно из предоставленного объяснения.
Ниже представлен некоторый разумно простой в использовании псевдокод. Теперь просто создайте эффективную структуру данных, чтобы предотвратить сложность O (N ^ 4). Возможно сортировка строк по положению или градиенту.
i, j, k, l следующие:
l
|---|
j| |k
|---|
i
extendIntersect - это просто функция, которая расширяет 2 линии до бесконечности (или в зависимости от того, какие вы выбираете) и возвращайте точку, где они пересекаются, что легко сделать математически.
onLine возвращает true, если точка лежит на строке.
onSameSide возвращает true, если обе точки лежат на одной стороне строки
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)
Некоторая проверка ошибок, предложенная Дрю Ноукс, также может быть хорошей идеей.