[FIXED] Clustering/supression (NMS) of lines

Issue

Given a list of lines defined as [(x0,y0), (x1,y1)], how can I cluster close lines so I can average them to reduce the number of lines I have? (e.g., lines that are overlapping). I obtained these lines after applying a Hough Transform from opencv in an image.

I have read about DBCluster or K-means cluster, but they are working on dots (as far as I have seen)

Solution

You're correct that traditional clustering algorithms like K-means or DBSCAN are more commonly used for point data rather than line segments. But, you can achieve it by considering the characteristics of line segments.

import numpy as np

def distance(line1, line2):
    # Calculate the distance between the closest points of two lines
    dists = []
    for point1 in line1:
        for point2 in line2:
            dist = np.linalg.norm(np.array(point1) - np.array(point2))
            dists.append(dist)
    return min(dists)

def cluster_lines(lines, threshold):
    clusters = []
    for line in lines:
        # Find an existing cluster to add the line to, if any
        added = False
        for cluster in clusters:
            if any(distance(line, existing_line) < threshold for existing_line in cluster):
                cluster.append(line)
                added = True
                break
        # If no existing cluster fits, create a new cluster
        if not added:
            clusters.append([line])
    return clusters

# Example lines (format: [(x0, y0), (x1, y1)])
lines = [((1, 2), (3, 4)), ((5, 6), (7, 8)), ((2, 3), (4, 5)), ((6, 7), (8, 9))]

# Set the threshold
threshold = 2.0

# Cluster the lines
clustered_lines = cluster_lines(lines, threshold)

# Print the clusters
for idx, cluster in enumerate(clustered_lines):
    print(f"Cluster {idx+1}: {cluster}")

Steps inside code:

1. Distance Calculation: The distance function calculates the distance between the closest points of two lines using the Euclidean distance formula. This will help us decide whether two lines are close enough to be clustered.

2. Clustering Lines: The cluster_lines function takes the lines and a threshold as input. It iterates through each line and tries to add it to an existing cluster. If the current line is close enough to any line in a cluster (within the threshold), it's added to that cluster. If not, a new cluster is created.

3. Threshold Setting: You set the threshold value, which determines how close two lines need to be to be considered for clustering. Adjusting this value will affect the sensitivity of the clustering process.

Answered By - Atzuki