Quadrilateral Shape Finding Algorithm
From the examples, I assume the question is more along the lines of Find all quadrilaterals that have a line contained completely within each of its sides. This is not at all clear from the explanation provided.
Below is some reasonably easy-to-implement pseudo-code. Now just to create an efficient data-structure to prevent the O(N^4) complexity. Maybe sort lines by position or gradient.
i,j,k,l are as follows:
l
|---|
j| |k
|---|
i
extendIntersect is merely a function that extends the 2 lines into infinity (or to whichever bounds you choose) and return the point where they intersect, easy to do mathematically.
onLine returns true if a point lies on a line.
onSameSide returns true if both points lie on the same side of a line
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)
Some sort of error checking as Drew Noakes suggested might also be a good idea.
I don't use C# so you will have to translate the code. The following code is in Java. I tested it with the included test case. I don't know how to add attachment to stackoverflow yet, so I am including the actual code here.
There are four classes (ShapeFinder, Line, Point, and Quadrilateral) and one test class (ShapeFinderTest):
ShapeFinder class:
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;
}
}
Line class:
package stackoverflow;
public class Line {
double slope;
double intercept;
public Line(double slope, double intercept) {
this.slope = slope;
this.intercept = intercept;
}
}
Point class:
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+")";
}
}
Quadrilateral class:
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());
}
}
}
About any four lines can be completed to form a quadrilateral if you don't impose constraints on angles etc.
Image with potentially wrong quadrilaterals:
Probably you don't want to include quadrilaterals like the yellow one shown in my example. You should have constraints on angles, minimum/maximum size, aspect ratio and the degree of completion allowed. If 90 percent of the lines have to be added in order to form a complete quadrilateral this would probably not be a very good candidate.
I fear that you will have to test every possible combination of lines and apply a heuristic on them to give them points. Many points for angles close to 90 degrees (if what you want are rectangles), for completeness, for aspect ratios close to the expected one etc.
UPDATE
Using a point system has advantages over just applying strict rules.
- A point system allows you to evaluate the quality of quadrilaterals and to take the best one or to reject a quadrilateral completely.
- The good quality of one property can help outweigh the poor quality of another one.
- It allows you to give different weights to different properties.
Let's say you have a strict rule (in pseudo code):
(angles == 90 +/- 10 degrees) && (line_completeness>50%)
This would work, can however lead to situations like angles == 90 +/- 1 degree) && (line_completeness == 45%). According to the rules this quadrilateral would not pass because of the poor line completeness; however, the quality of the angles is exceptional, still making it a very good candidate.
It is better to give points. Say 20 points for an angle of exactly 90 degrees, falling to 0 points for an angle of 90 +/-15 degrees and 10 points for complete lines towards 0 points for lines complete by only 25% for instance. This makes angles more important than line completeness and also creates softer conditions for a problem that does not have absolute rules.
In the case of 11 line segments, you have 330 ways of choosing four segments. You could determine the likelihood of each combination making a quadrilateral, and grade that way.
It is possible to have a Hough transform detect forms other than lines, though it becomes harder to visualise as the accumulator space would require more than two dimensions. Circles can be found in three dimensions (midX, midY, radius), ellipses in four (I believe). I'm not sure exactly how few parameters you'd need to model a quadrilateral, and I believe that the performance of the Hough transform starts to drop off when you get higher than three dimensions. The accumulator space becomes so large that the noise ratio increases significantly.
Here's a related question that may have some interesting answers for you.
Let us know how you get on!
EDIT
I took a stab at this problem today, and uploaded my solution to GitHub. There is too much code to post here.
Here's a screenshot showing the output:
The solution I took is basically what I described above before this edit.
- Find all combinations of four lines
- Find all permutations of those four lines
- Evaluate the likelihood that those four lines form a quadrilateral
- Take the best match
The evaluation works by calculating a crude error score. This is the sum of two different types of error:
- The deviation at each corner from 90 degrees (I use the sum of squared errors across all four corners)
- When the line segments intersect within the line segment, it's likely not a valid corner
The second type of error could possibly be determined in a more robust way. It was necessary to find a solution for your sample data set.
I haven't experimented with other data sets. It may need some tweaking to make it more robust. I have tried to avoid using too many parameters so that it should be straightforward to adjust to a particular environment. For example to control sensitivity to occlusion, as seen in your sample image.
It finds the solution in about 160ms on my laptop. However I haven't made any performance optimisations. I expect that the methods of finding combinations/permutations could be significantly optimised if you needed this to run closer to real-time, as is often the case with computer vision experiments.