Python：实现线段聚类，将相邻线段合并为组

一、“相邻线段”

• 这里的相邻可能指的是线段在空间上接近，或者在方向上相似，或者两者都有。
  把位置相近的线段合并成一个组，这样在后续处理中可以当作一个整体来处理，比如找到最右边的组或者进行其他分析。

二、如何衡量线段之间的“相邻”程度

可能的思路包括：

• 1、计算线段之间的距离，或者检查它们的端点是否在一定的阈值范围内。
• 2、使用聚类算法，比如基于距离的聚类，比如DBSCAN或者层次聚类。
• 3、自己设计一种简单的合并策略，比如如果两条线段的端点之间的最小距离小于某个阈值，就将它们合并。

考虑到实现复杂度，可能先采用一个简单的方法，比如基于线段的中点或端点的距离来进行聚类。
比如，计算每条线段的中点，然后根据中点之间的距离进行聚类。
或者，对于线段端点之间的最小距离进行判断

三、如何聚类

• 合并可能意味着将这些线段组合成一个组，或者将它们合并成一条更长的线段。
  如果是后者，可能需要计算这些线段的端点，找到合并后的起点和终点。

• 线段的表示方式
  具体实现时，需要注意线段的表示方式。
  例如，每条线段由两个端点(x1,y1)和(x2,y2)组成。
  可以将每条线段转换成一个特征向量，比如中点坐标，或者两个端点的坐标，或者加上角度等信息。
  比如，每条线段可以表示为中点坐标（(x1+x2)/2, (y1+y2)/2）以及角度（通过atan2(y2-y1, x2-x1)计算）。然后使用这些特征进行聚类。这样，位置相近且方向相似的线段会被聚为一类

• 或者，可以简单地将线段的端点之间的距离作为判断标准。例如，如果两条线段之间的任何端点之间的距离小于某个阈值，就将它们归为同一组。这种方法可能简单但计算量大，因为要比较所有线段对。

• 另外，需要考虑聚类的效率问题。如果线段数量较多，可能需要一个高效的算法。例如，DBSCAN的时间复杂度相对较低，适合处理中等规模的数据集。

四、合并线段

• 对于每个簇，计算所有线段端点中的最小和最大x、y值，或者使用主成分分析找到主要方向，然后生成一条线段。

• 但这里可能需要更简单的方法，比如找到该簇所有端点的最左和最右点，或者上下端点，然后画一条线段连接这些点。
  然后，找到这些点的最小和最大x，或者计算平均位置和方向。
  或者，使用线性回归拟合这些点，得到一条直线，然后找出这条直线上的两个端点。
  或者，取所有点的最左端和最右端作为线段的端点，这可能适用于近似水平的线段。
  具体实现可能需要根据线段的分布情况来选择方法。
  例如，假设簇内的线段大致在同一垂直线上，那么它们的x坐标相近，那么合并后的线段可以取所有线段中最高的点和最低的点，连接起来形成一个垂直线段。
  或者，如果是水平线段，则取最左和最右的点。
  这可能需要判断线段的主要方向。例如，计算簇内线段角度的平均值，如果接近垂直（角度接近90度），则合并为垂直线段；否则合并为水平线段。

• 作为初步实现，可能可以取所有端点中的极值点来形成合并后的线段。
  例如，合并后的线段的起点是（min_x, avg_y），终点是（max_x, avg_y），如果是水平方向；或者起点是（avg_x, min_y），终点是（avg_x, max_y），如果是垂直方向。
  或者，计算所有端点的中心点，以及平均角度，然后根据角度生成一条线段。
  但这样可能更准确，但需要更多的计算。

• 一种合理的合并方式
  假设我们采用简单的方法：对于一个簇内的所有端点，找到最小和最大的x和y，然后根据线段的主要方向决定合并后的线段是水平还是垂直，或者直接连接两个最远的端点。
  或者，计算该簇内所有线段的中点，并找到这些中点的主方向，然后生成一条线段。
  不过，这些都可能需要复杂的计算。可能为了简化，可以取该簇所有端点中的最左、最右、最上、最下点，然后根据这些点生成合并后的线段。

• 如何判断该簇的主要方向
  例如，计算所有线段的角度平均值，假设平均角度接近0度（水平）或90度（垂直）。或者，计算主成分分析的第一主成分方向。
  例如，对于一个簇内的所有端点，组成一个点集，然后计算这些点的协方差矩阵，找到主方向。这可以通过PCA实现。

  • 在Python中，可以使用numpy进行PCA计算。
    例如，对于点集points（N个二维点），计算协方差矩阵的特征向量，最大特征值对应的特征向量就是主方向。
    然后，沿主方向找到这些点的投影的最大和最小值，从而确定合并后的线段的两个端点。
    这可能是一个比较准确的方法。

• 这样，每个簇生成一条新的线段，连接point_min和point_max。
  这将合并簇内的所有线段为一条沿着主方向延伸的线段。
  这样处理后，原来的多个线段被合并成一条代表整个簇的线段。
  不过，这可能更适合于线段大致排列在同一方向的情况。例如，多个接近水平或垂直的线段会被合并成一条长线段。

五、程序

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 26 10:08:50 2025

实现线段聚类，将相邻线段合并为组ds008.py
"""

import cv2
import numpy as np
from sklearn.cluster import DBSCAN

def merge_lines(cluster_lines):
    """ 合并同一簇内的线段 """
    points = []
    for line in cluster_lines:
        x1, y1, x2, y2 = line[0]
        points.append([x1, y1])
        points.append([x2, y2])
    points = np.array(points)
    
    if len(points) < 2:
        return cluster_lines[0]
    
    # PCA计算主方向
    mean = np.mean(points, axis=0)
    centered = points - mean
    cov = np.cov(centered.T)
    
    if np.isnan(cov).any():
        return cluster_lines[0]
    
    eigenvals, eigenvecs = np.linalg.eigh(cov)
    primary_vec = eigenvecs[:, np.argmax(eigenvals)]
    
    # 计算投影极值点
    proj = np.dot(centered, primary_vec)
    min_proj = np.min(proj)
    max_proj = np.max(proj)
    
    # 生成合并后的线段
    point_min = mean + min_proj * primary_vec
    point_max = mean + max_proj * primary_vec
    return np.array([[int(point_min[0]), int(point_min[1]), 
                     int(point_max[0]), int(point_max[1])]])

def find_rightmost_segments(image_path, num_segments=3):
    # 读取图像并检测边缘
    image = cv2.imread(image_path)
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    blurred = cv2.GaussianBlur(gray, (5, 5), 0)
    edges = cv2.Canny(blurred, 50, 150)
    
    # 霍夫变换检测线段
    lines = cv2.HoughLinesP(edges, 1, np.pi/180, threshold=50,
                           minLineLength=50, maxLineGap=10)
    
    rightmost_lines = []
    if lines is not None:
        # 初选最右侧线段
        lines_with_right = []
        for line in lines:
            x1, y1, x2, y2 = line[0]
            right_x = max(x1, x2)
            lines_with_right.append((right_x, line))
        
        lines_with_right.sort(reverse=True, key=lambda x: x[0])
        selected = lines_with_right[:num_segments*2]  # 扩大初选范围
        pre_merge = [line for (_, line) in selected]
        
        # 线段聚类
        features = []
        for line in pre_merge:
            x1, y1, x2, y2 = line[0]
            features.append([(x1+x2)/2, (y1+y2)/2])
        
        features = np.array(features)
        if len(features) > 0:
            # DBSCAN聚类（核心参数：eps控制聚类半径）
            dbscan = DBSCAN(eps=30, min_samples=1)
            clusters = dbscan.fit_predict(features)
            
            # 合并线段
            merged_lines = []
            for cluster_id in np.unique(clusters):
                cluster_lines = [pre_merge[i] for i in np.where(clusters == cluster_id)[0]]
                merged = merge_lines(cluster_lines)
                merged_lines.append(merged)
            
            # 最终筛选最右侧线段
            merged_with_right = []
            for line in merged_lines:
                x1, y1, x2, y2 = line[0]
                merged_with_right.append((max(x1, x2), line))
            
            merged_with_right.sort(reverse=True, key=lambda x: x[0])
            rightmost_lines = [line for (_, line) in merged_with_right[:num_segments]]
    
    # 可视化结果
    result = image.copy()
    colors = [(0,255,0), (0,0,255), (255,0,0)]  # 不同线段用不同颜色
    for idx, line in enumerate(rightmost_lines):
        x1, y1, x2, y2 = line[0]
        cv2.line(result, (x1,y1), (x2,y2), colors[idx%3], 2)
    
    return result

# 使用示例
output_image = find_rightmost_segments("D:/OpenCVpic/p03.jpg", num_segments=5)

# 显示并保存结果
cv2.imshow("Detected Rightmost Lines", output_image)
cv2.waitKey(0)
cv2.destroyAllWindows()
cv2.imwrite("output.jpg", output_image)

六、说明

• 扩大初选范围：首先选择2倍于需求量的线段（num_segments*2），为后续合并保留足够样本

• 特征提取：以线段中点坐标作为聚类特征

• 密度聚类：

  • 使用DBSCAN算法自动发现相邻线段
  • eps=30表示两个线段中点距离小于30像素视为相邻；增大值：合并更多相邻线段；减小值：生成更精细的分组
  • min_samples=1允许独立线段自成一组

• 线段合并：

  • 收集簇内所有端点进行PCA分析
  • 沿主成分方向生成合并线段

• 最终筛选：对合并后的线段再次按右侧位置排序，选择最需要的数量

自动合并相邻线段，消除重复检测；有效处理存在多个相邻线段的情况，特别适合需要识别明显独立结构的场景（如检测多根立柱、多车道线等）。