图像共享边缘共享像素坐标提取及多边形复杂度计算求助

需求目标 #

实现从图像中提取共享边缘对应的共享像素坐标，最终输出三类结果：

• 标注了共享边缘的可视化图像，可使用红色等任意颜色标注
• 记录所有共享像素坐标的DataFrame
• 自定义复杂度指数，统计每个多边形的共享边数量：示例图中多边形1有1条共享边，多边形2、3各有3条共享边，多边形4有2条共享边，多边形5有1条共享边

当前卡点 #

已经完成轮廓筛选，构建了存储图像轮廓数据的嵌套字典contour_df，记录了图像的所有像素信息。当前核心问题是itertools.permutations会遍历所有像素坐标组合，运行耗时极长，无法推进后续开发。现有实现思路存在问题，需要调整方案。

现有测试代码 #

import numpy as np
import itertools
import math

def complexity_estimator(contour_df):
    adjacency_list = []
    for i in range(0, contour_df.shape[0]):
        if contour_df.iloc[i]["parent_index"] == -1:
            adjacency_list.append(0)
        else:
            # 提取目标轮廓的坐标列表
            contour_coordinate = contour_df.iloc[i]["contour"]
            # 提取所有同级父节点的其他轮廓坐标列表
            contour_coordinate_siblings = contour_df[contour_df["parent_index"] == contour_df.iloc[i]["parent_index"]]['contour'].values
            count = 0
            for sibling_contour in contour_coordinate_siblings:
                # 比对两个轮廓是否相邻
                adjacent = complexity_measure(contour_coordinate,sibling_contour)
                if adjacent:
                    count += 1
            adjacency_list.append(count)
    contour_df['complexity'] = adjacency_list
    return contour_df

def complexity_measure(contour_coordinates1, contour_coordinates2):
    if np.array_equal(contour_coordinates1, contour_coordinates2):
        return False
    else:
        new_pairs =  [list(zip(x,contour_coordinates2)) for x in itertools.permutations(contour_coordinates2,len(contour_coordinates2))]
        print(new_pairs)
        # 原有距离计算逻辑未实现
        # dist = math.hypot(x2 - x1, y2 - y1)
    return True

优化实现方案 #

核心逻辑替换（解决耗时问题） #

完全不需要使用排列组合遍历坐标，直接用集合求交集即可：

1. 把每个轮廓的坐标列表转成tuple组成的集合，每个坐标存为(x,y)格式
2. 两个轮廓坐标集合的交集就是共享像素，只要交集长度≥2（排除单点偶然邻接的情况）就判定为存在共享边，时间复杂度直接从阶乘级降到线性级

全流程实现步骤 #

1. 共享像素提取：遍历所有两两组合的轮廓，求坐标交集，把所有交集中的像素点记录下来，同时标注该像素属于哪两个多边形的共享边
2. 共享边去重聚合：把连续的共享像素归为同一条边，避免同一条边被误统计为多条
3. 结果输出：
   • 可视化：直接在原图上将所有共享像素点染为红色，导出标注后的图像
   • 共享像素DataFrame：列设置为x坐标、y坐标、所属多边形A ID、所属多边形B ID
   • 复杂度统计：每个多边形的复杂度等于该多边形作为主体参与的共享边条数

内容的提问来源于stack exchange，提问作者dalek_fred