我希望能够检测并 完整地 从随机位置的线段中找出所有可能的四边形形状！
下方的图片是一个例子，线段可能总是出现在不同的位置上。
是否有人可以指出任何好的算法来实现这个目标？
- 请注意，线段是使用opencv 2.4.2的Hough变换的输出。
解决方案是检测和预测黄色的四边形
四边形形状查找算法
35
- Zaher Joukhadar
10
3你的示例图片中没有完整的四边形。能否提供一个有完整四边形的图片？ - kurast
你能在你的示例中发布一下，期望的输出是什么吗？你是在寻找正方形、矩形、梯形还是任何四边形呢？ - kurast
我已经做了那个，我正在寻找任何四边形。 - Zaher Joukhadar
您需要限制等边形的长宽比吗？换句话说，长而窄的等边形和正方形一样常见吗？ - Drew Noakes
1另外，我认为您可能是指简单或凸四边形。http://en.wikipedia.org/wiki/File:Quadrilateral_hierarchy.png - thang
显示剩余5条评论
5个回答
46
在11条线段的情况下，您有330种选择四条线段的方法。您可以确定每种组合构成四边形的可能性，并按照这种方式进行评分。
霍夫变换可以检测除直线以外的其他形式，但随着累加器空间需要超过两个维度，它变得更难以可视化。圆可以在三维中找到（midX，midY，radius），椭圆可以在四维中找到（我相信）。我不确定您需要多少参数来模拟四边形，我认为当您超过三个维度时，霍夫变换的性能开始下降。累加器空间变得如此之大，以至于噪声比例显著增加。
这里有一个related question，可能对您有一些有趣的答案。
让我们知道您的进展如何！
我没有尝试过其他数据集。它可能需要一些调整才能使其更加强大。我已经尝试避免使用太多参数，以便可以轻松调整到特定环境。例如，控制对遮挡的敏感性，如您的示例图像所示。
它在我的笔记本电脑上大约花费160毫秒找到解决方案。但是我没有进行任何性能优化。如果您需要这个运行更接近实时（通常是计算机视觉实验的情况），我预计找到组合/排列的方法可以显着优化。
霍夫变换可以检测除直线以外的其他形式，但随着累加器空间需要超过两个维度，它变得更难以可视化。圆可以在三维中找到（midX，midY，radius），椭圆可以在四维中找到（我相信）。我不确定您需要多少参数来模拟四边形，我认为当您超过三个维度时，霍夫变换的性能开始下降。累加器空间变得如此之大，以至于噪声比例显著增加。
这里有一个related question，可能对您有一些有趣的答案。
让我们知道您的进展如何！
编辑
我今天尝试解决了这个问题，并将我的解决方案上传到GitHub。有太多的代码无法在此处发布。
这里是一个显示输出结果的屏幕截图:
- 查找四条线的所有组合
- 查找这些四条线的所有排列
- 评估这些四条线形成四边形的可能性
- 选择最佳匹配项
- 每个角度偏离90度的偏差（我使用四个角度上的平方误差之和）
- 当线段在线段内相交时，很可能不是有效的角
我没有尝试过其他数据集。它可能需要一些调整才能使其更加强大。我已经尝试避免使用太多参数，以便可以轻松调整到特定环境。例如，控制对遮挡的敏感性，如您的示例图像所示。
它在我的笔记本电脑上大约花费160毫秒找到解决方案。但是我没有进行任何性能优化。如果您需要这个运行更接近实时（通常是计算机视觉实验的情况），我预计找到组合/排列的方法可以显着优化。
- Drew Noakes
19
如果您不对角度等施加限制，任何四条线都可以组成四边形。
可能存在错误的四边形图片:
您可能不想包括像我例子中显示的黄色四边形那样的四边形。您应该对角度、最小/最大尺寸、长宽比和允许的完整度进行约束。如果必须添加90%的线才能形成完整的四边形，则这可能不是一个很好的选择。
我担心您将不得不测试每种可能的线组合，并对它们应用启发式算法来给它们打分。对于接近90度的角度（如果您想要的是矩形），完整性，接近预期长宽比等，需要给予许多分数。
更新
使用积分系统比仅应用严格规则有优势。
- 积分系统允许您评估四边形的质量，并选择最佳的四边形或完全拒绝一个四边形。
- 一个属性的良好质量可以帮助弥补另一个属性的差质量。
- 它允许您为不同的属性分配不同的权重。
假设您有一个严格的规则（伪代码）：
(angles == 90 +/- 10 degrees) && (line_completeness>50%)
这样做虽然可行，但可能会出现类似于
angles == 90 +/- 1 degree) && (line_completeness == 45%) 的情况。根据规则，这个四边形将因线条完整度不佳而不通过；但是，角度的质量非常好，仍然使它成为一个非常好的候选。最好给出分数。例如，对于恰好为90度的角，给予20分，对于90 +/-15度的角，则降至0分，对于完全的线条，则给予10分，例如只有25%的线条完整性，则得到0分。这使得角度比线条完整性更重要，并且为没有绝对规则的问题创建了更柔和的条件。
- Olivier Jacot-Descombes
5
7是的，我知道这是错误的。这正是问题所在。问题是：为什么？“四边形”只意味着它有四条边，没有更多的含义。如果你说，“我正在寻找任何四边形”，那么即使是带有交叉线的四边形也是被允许的。可能你只想允许与矩形相似的四边形。 - Olivier Jacot-Descombes
考虑到 OP 正在使用霍夫变换，这很可能是一个计算机视觉问题。虽然原始问题陈述并不十分严谨，但我假设他们正在尝试检测矩形物体。无论如何，这只是调整评分函数的问题。 - Drew Noakes
5我的图像旨在展示错误之处，以强调需要限制的必要性。可能之一的限制是非完整线条必须至少占据四边形内的一定百分比。蓝色和绿色线条的未完整下部完全位于四边形外部。算法需要明确的规则，因为它不能像我们人类一样“看到”或“感受”矩形。 - Olivier Jacot-Descombes
我完全同意你的观点。在编写解决方案时，我不得不对暗示的约束条件进行一些假设。实际上，只要没有四条完全平行的线集，那么这个图像中就有330个可能的四边形。你的启发式方法基本上就是我在代码中所做的。这是一个有趣的问题！ - Drew Noakes
2@AgentFire：错误的四边形是有意的。请参见上面的注释。 - Olivier Jacot-Descombes
3
我不使用C#，所以你需要翻译这段代码。以下代码是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;
}
}
Line类：
package stackoverflow;
public class Line {
double slope;
double intercept;
public Line(double slope, double intercept) {
this.slope = slope;
this.intercept = intercept;
}
}
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+")";
}
}
四边形类：
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() + "]";
}
}
单元测试：
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());
}
}
}
- Konsol Labapen
1
1也许如果您发布一些结果图像会更有帮助。 - Rui Marques
2
从这些例子中，我假设问题更多地是关于查找所有四边形，其每条边都包含完全在其中的一条直线。这在提供的解释中并不清楚。
以下是一些相当容易实现的伪代码。现在只需创建一个有效的数据结构来防止O（N ^ 4）复杂度。也许按位置或梯度对线进行排序。
i，j，k，l如下：
l
|---|
j| |k
|---|
i
extendIntersect 是一个将两条直线无限延伸（或延伸到您选择的任意边界）并返回它们相交点的函数，数学上很容易实现。
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)
正如Drew Noakes所建议的那样，进行某种形式的错误检查可能也是个好主意。
- Bernhard Barker
2
解决方案1：
这是一个完整的解决方案，使用OpenCV 2.4和Sympy编写了Python 2.7.x代码。
我使用了D.Noakes的数据（线段），但采取了不同的方法。
问题定义：
对于一组线段，找到所有可能的四边形形状，其中线段适合四边形的边缘内。
方法：
- 将线段分成大致“水平”或“垂直”。
- 将“水平”或“垂直”成对。
- 过滤成对的线段，例如如果它们相互接触或相交。
- 制作两个“水平”和两个“垂直”线段的组合。
- 过滤候选四边形，例如角落在图像外或线段不在四边形上。
结果：
该方法检测到图像中的4个四边形形状
查看动画GIF：https://ibb.co/4Rv9rJW
代码：https://pastiebin.com/5f3836269f7e5
#!/usr/bin/env python
"""
Find Quads:
For a set of line segments, find all the possible
quadrilateral shapes where the segments fit
inside the edges of the quad.
Dependencies:
Sympy is used for geometry primitives.
sudo pip install sympy
"""
import numpy as np
import cv2
import itertools # combinations, product
from sympy import Point, Line, Segment, convex_hull
import sys
input_image = cv2.imread("detected_lines.jpg")
#------------------------------------------------------------------------------#
def checkPointInImage(point, image_width, image_height):
"""
Check if a Sympy Point2D is within the bounds of an OpenCV image.
"""
pt_x = int(round(point.x))
pt_y = int(round(point.y))
if (pt_x >= 0) and (pt_x < image_width) and (pt_y >= 0) and (pt_y < image_height):
return True
# Point is outside the image boundary
return False
def checkPointsInImage(points, image_width, image_height):
"""
Check if a set of Sympy Point2D are all within the bounds of an OpenCV image.
"""
for point in points:
if not checkPointInImage(point, image_width, image_height):
return False
# All points are within the image boundary
return True
def getUniquePairs(segments, image_dims):
"""
Get all the possible pairs of line segments.
(the unique combinations of 2 lines)
Note: this doesn't check for duplicate elements, it works
only on the position in the list.
"""
# Check that a pair of segments are not intersecting
check_segments_dont_intersect = True
# Check that the endpoint of one segment
# does not touch the other segment (within 10 pixels)
check_segment_endpoints = True
endpoint_min_separation = 10
# Project the segments and check if the intersection
# point is within the image
check_projected_segments_dont_intersect = True
pairs = list(itertools.combinations(segments, 2)) # a list of tuple
image_width, image_height = image_dims
filtered_pairs = []
for pair in pairs:
segment1 = pair[0]
segment2 = pair[1]
if check_segments_dont_intersect:
if bool(len(segment1.intersection(segment2))):
# Discard this pair.
# The pair of segments intersect each other.
continue
if check_segment_endpoints or check_projected_segments_dont_intersect:
line1 = Line(segment1)
line2 = Line(segment2)
intersection_points = line1.intersection(line2)
intersects = bool(len(intersection_points))
if intersects:
intersection_point = intersection_points[0]
if check_segment_endpoints:
# Measure the distance from the endpoint of each segment
# to the intersection point.
d1 = float(segment1.points[0].distance(intersection_point))
d2 = float(segment1.points[1].distance(intersection_point))
d3 = float(segment2.points[0].distance(intersection_point))
d4 = float(segment2.points[1].distance(intersection_point))
d = np.array([d1,d2,d3,d4])
if (d < float(endpoint_min_separation)).any():
# Discard this pair.
# One segment is (almost) touching the other.
continue
if check_projected_segments_dont_intersect:
if checkPointInImage(intersection_point, image_width, image_height):
# Discard this pair.
# After projecting the segments as lines,
# they intersect somewhere on the image.
continue
filtered_pairs.append(pair)
return filtered_pairs
def getCombinationsOfTwoLists(list1, list2):
"""
For two sets of Line Segment pairs,
generate all possible combinations.
"""
return list(itertools.product(list1, list2))
def getIntersectionLineSegments(segment1, segment2):
"""
Find the intersection of two line segments,
by extending them into infinite lines.
"""
line1 = Line(segment1)
line2 = Line(segment2)
intersection_points = line1.intersection(line2)
intersects = bool(len(intersection_points))
if intersects:
intersection_point = intersection_points[0]
return intersection_point
# Error, lines do not intersect
print("WARNING: Horizontal and vertical line segments do not intersect.")
print("This should not happen!")
return None
def checkLineSegmentIsAbove(segment1, segment2):
"""
Check if one line segment is above the other.
(this assumes the segments are not intersecting)
"""
# In image coordinates, (+x,+y) is bottom-right corner.
if (segment1.points[0].y > segment2.points[0].y): return False
if (segment1.points[0].y > segment2.points[1].y): return False
if (segment1.points[1].y > segment2.points[0].y): return False
if (segment1.points[1].y > segment2.points[1].y): return False
return True
def checkLineSegmentOnLeft(segment1, segment2):
"""
Check if one line segment is on the left side of the other.
(this assumes the segments are not intersecting)
"""
# In image coordinates, (+x,+y) is bottom-right corner.
if (segment1.points[0].x > segment2.points[0].x): return False
if (segment1.points[0].x > segment2.points[1].x): return False
if (segment1.points[1].x > segment2.points[0].x): return False
if (segment1.points[1].x > segment2.points[1].x): return False
return True
def getConvexIntersectionPoints_method2(horizontal_segment1, horizontal_segment2, vertical_segment1, vertical_segment2):
"""
For two pairs of line segments, treat them as
infinite lines and find the intersection points.
These 4 points are in a clockwise order that
represents a convex quadrilateral.
"""
# Sort the segments in clockwise order
top_segment = None
right_segment = None
bottom_segment = None
left_segment = None
if checkLineSegmentIsAbove(horizontal_segment1, horizontal_segment2):
top_segment = horizontal_segment1
bottom_segment = horizontal_segment2
else:
top_segment = horizontal_segment2
bottom_segment = horizontal_segment1
if checkLineSegmentOnLeft(vertical_segment1, vertical_segment2):
left_segment = vertical_segment1
right_segment = vertical_segment2
else:
left_segment = vertical_segment2
right_segment = vertical_segment1
corner_pt1 = getIntersectionLineSegments(left_segment, top_segment)
corner_pt2 = getIntersectionLineSegments(top_segment, right_segment)
corner_pt3 = getIntersectionLineSegments(right_segment, bottom_segment)
corner_pt4 = getIntersectionLineSegments(bottom_segment, left_segment)
quad_points = [corner_pt1, corner_pt2, corner_pt3, corner_pt4]
sorted_segments = [top_segment, right_segment, bottom_segment, left_segment]
return (quad_points, sorted_segments)
def checkSegmentsOnQuad_method2(sorted_segments, corners):
"""
Check if all 4 line segments are within
the edges of a quadrilateral.
This assumes that the inputs are already matched.
"""
if (len(sorted_segments) != 4) or (len(corners) != 4):
print("ERROR: Expected 4 segments and 4 corners in checkSegmentsOnQuad_method2()")
sys.exit()
# Get the 4 edges
edges = []
for i in range(3):
p1 = corners[i]
p2 = corners[i+1]
edges.append(Segment(p1, p2))
p1 = corners[3]
p2 = corners[0]
edges.append(Segment(p1, p2))
for i in range(4):
if not edges[i].contains(sorted_segments[i]):
return False
return True
def getQuads(sets_of_four_segments, image_dims):
"""
Find quadrilateral shapes.
"""
image_width, image_height = image_dims
quads = []
for i in range(len(sets_of_four_segments)):
# Determine if 4 line segments represent
# a valid quadrilateral shape:
segments = sets_of_four_segments[i]
horizontal_segment1 = segments[0][0]
horizontal_segment2 = segments[0][1]
vertical_segment1 = segments[1][0]
vertical_segment2 = segments[1][1]
quad_points, sorted_segments = getConvexIntersectionPoints_method2(horizontal_segment1, horizontal_segment2, vertical_segment1, vertical_segment2)
if not checkPointsInImage(quad_points, image_width, image_height):
print(" Bad quad, an intersection point (one corner of the quad) is outside image!")
# Save debug image
img = np.copy(input_image)
drawCrosshairs(img, quad_points)
drawQuad(img, quad_points)
suffix = str(i).zfill(2)
cv2.imwrite("candidate_quad_"+suffix+".jpg", img)
# Discard this quad.
# A corner point is outside the image boundary.
continue
# Check if each line segment is within one side of the quad.
# - The segments can not intersect each other.
# - The end of a segment can not extend out past the quad.
# - All segments must be contained within one edge of the shape.
if checkSegmentsOnQuad_method2(sorted_segments, quad_points):
print(" Good")
quads.append(quad_points)
else:
print(" Bad quad, a line segment is not within the quad")
# Save debug image
img = np.copy(input_image)
drawCrosshairs(img, quad_points)
drawQuad(img, quad_points)
suffix = str(i).zfill(2)
cv2.imwrite("candidate_quad_"+suffix+".jpg", img)
#cv2.imshow("Quad corners", img)
#cv2.waitKey()
return quads
#------------------------------------------------------------------------------#
# Drawing functions:
def drawSegment(image, segment, color):
"""
Draw a Sympy Line Segment on an OpenCV image.
"""
thickness = 2
x1 = int(segment.points[0].x) # should already be int
y1 = int(segment.points[0].y)
x2 = int(segment.points[1].x)
y2 = int(segment.points[1].y)
cv2.line(image, (x1,y1), (x2,y2), color, thickness)
def drawSegments(image, segments, color=(0,0,255)):
"""
Draw lines on an OpenCV image.
Default color is red.
"""
for segment in segments:
drawSegment(image, segment, color)
def drawCrosshair(image, point):
"""
Draw a Sympy Point2D on an OpenCV image
with a cross marker.
"""
pt_x = int(round(point.x))
pt_y = int(round(point.y))
length = 5
thickness = 2
color = (255,0,255) # magenta
cv2.line(image, (pt_x, pt_y-length), (pt_x, pt_y+length), color, thickness)
cv2.line(image, (pt_x-length, pt_y), (pt_x+length, pt_y), color, thickness)
def drawCrosshairs(image, points):
"""
Draw marks on an OpenCV image.
"""
for point in points:
drawCrosshair(image, point)
def drawQuad(image, corners, color=(0,255,0)):
"""
Draw a quadrilateral shape.
The 4 corner points are Sympy Point2D.
"""
for i in range(len(corners)-1):
p1 = corners[i]
p2 = corners[i+1]
segment = Segment(p1, p2)
drawSegment(image, segment, color)
# Close the polygon
p1 = corners[len(corners)-1]
p2 = corners[0]
segment = Segment(p1, p2)
drawSegment(image, segment, color)
#------------------------------------------------------------------------------#
if input_image == None:
print("ERROR: Can't find input image")
sys.exit()
#cv2.imshow("input_image", input_image)
#cv2.waitKey()
# Line segments sample data
segment1 = Segment(Point(335,120), Point(517,144))
segment2 = Segment(Point(287, 604), Point(558, 619))
segment3 = Segment(Point(323, 131), Point(275, 587))
segment4 = Segment(Point(589, 473), Point(580, 606))
segment5 = Segment(Point(368, 39), Point(489, 108))
segment6 = Segment(Point(53, 286), Point(293, 406))
segment7 = Segment(Point(299, 347), Point(214, 538))
segment8 = Segment(Point(200, 370), Point(149, 528))
segment9 = Segment(Point(6, 446), Point(68, 449))
segment10 = Segment(Point(66, 444), Point(150, 525))
segment11 = Segment(Point(389, 514), Point(518, 644))
segments = [segment1, segment2, segment3, segment4, segment5, segment6, segment7, segment8, segment9, segment10, segment11]
image_width = input_image.shape[1]
image_height = input_image.shape[0]
image_dims = (image_width, image_height)
input_image_with_segments = np.copy(input_image)
drawSegments(input_image_with_segments, segments)
cv2.imshow("input_image_with_segments", input_image_with_segments)
cv2.waitKey()
# Sort the line segments into 2 groups:
horizontal_segments = []
vertical_segments = []
image_width = input_image.shape[1]
x_axis = Line((0, 0), (image_width, 0))
for segment in segments:
# Compute the angle of each line segment.
# Angle is w.r.t. the top edge of the image
# in a clockwise direction.
angle = float(x_axis.angle_between(segment))
# Check 315 to 360 degrees
if (angle >= 2.0*np.pi-np.pi/4.0) and (angle <= 2.0*np.pi):
horizontal_segments.append(segment)
# Check 0 to 45 degrees
elif (angle >= 0.0) and (angle < np.pi/4.0):
horizontal_segments.append(segment)
# Check 135 to 225 degrees
elif (angle > np.pi-np.pi/4.0) and (angle < np.pi+np.pi/4.0):
horizontal_segments.append(segment)
else:
vertical_segments.append(segment)
# Save debug images
input_image_with_horizontal_segments = np.copy(input_image)
drawSegments(input_image_with_horizontal_segments, horizontal_segments)
cv2.imwrite("segments_horizontal.jpg", input_image_with_horizontal_segments)
input_image_with_vertical_segments = np.copy(input_image)
drawSegments(input_image_with_vertical_segments, vertical_segments)
cv2.imwrite("segments_vertical.jpg", input_image_with_vertical_segments)
# Get all the possible pairs of horizontal line segments:
pairs_of_horizontal_line_segments = getUniquePairs(horizontal_segments, image_dims)
print("Got %d pairs of horizontal line segments" % len(pairs_of_horizontal_line_segments)) # 15 pairs, 10 after filtering
# Get all the pairs of vertical line segments:
pairs_of_vertical_line_segments = getUniquePairs(vertical_segments, image_dims)
print("Got %d pairs of vertical line segments" % len(pairs_of_vertical_line_segments)) # 10 pairs, 6 after filtering
# Save debug images
for i in range(len(pairs_of_horizontal_line_segments)):
pair = pairs_of_horizontal_line_segments[i]
segments = [pair[0], pair[1]]
img = np.copy(input_image)
drawSegments(img, segments)
suffix = str(i).zfill(2)
cv2.imwrite("segment_pairs_horizontal_"+suffix+".jpg", img)
#cv2.imshow("Pair of segments", img)
#cv2.waitKey()
for i in range(len(pairs_of_vertical_line_segments)):
pair = pairs_of_vertical_line_segments[i]
segments = [pair[0], pair[1]]
img = np.copy(input_image)
drawSegments(img, segments)
suffix = str(i).zfill(2)
cv2.imwrite("segment_pairs_vertical_"+suffix+".jpg", img)
#cv2.imshow("Pair of segments", img)
#cv2.waitKey()
# Get all combinations of 4 line segments:
sets_of_four_line_segments = getCombinationsOfTwoLists(pairs_of_horizontal_line_segments, pairs_of_vertical_line_segments)
print("Got %d potential quadrilaterals" % len(sets_of_four_line_segments)) # = 60
# Find the valid quadrilateral shapes:
quads = getQuads(sets_of_four_line_segments, image_dims)
print("Got %d valid quads" % len(quads))
for i in range(len(quads)):
img = np.copy(input_image)
drawQuad(img, quads[i])
# Save result images
suffix = str(i).zfill(2)
cv2.imwrite("quad_"+suffix+".jpg", img)
title = "Candidate Quad " + str(i)
cv2.imshow(title, img)
cv2.waitKey()
- David
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接