Peter Wu Asked: 2025-02-28 13:16:59 +0800 CST2025-02-28 13:16:59 +0800 CST 2025-02-28 13:16:59 +0800 CST 保证一组变化的像素连接的数据结构 772 我正在研究一个优化问题，即找到一个最大化某个目标函数的区域，我使用一组像素坐标来跟踪该区域，并且每一步我都会在边界处添加或删除一个像素，以查看目标函数是否增加。我希望该区域是连通的，是否有任何数据结构可以快速决定删除一个像素是否会使该区域断开连接？这里我们假设一个像素与其四个邻居相连。 还有一个类似的问题：如果我希望该区域始终是单连通的，该怎么办？单连通的意思是没有洞，而添加一个像素可能会产生一个洞。 algorithm 1 个回答 Voted Best Answer Cris Luengo 2025-02-28T14:34:06+08:002025-02-28T14:34:06+08:00 您可以查看移除像素（或添加像素）前后 3x3 邻域的配置，并确定该操作是否会改变其所连接对象的欧拉特征。欧拉特征会告诉您有多少个对象和多少个洞。 如果在 3x3 邻域内（不包括中心像素）有 1 到 7 个固定像素，并且它们只是简单连接，则添加或移除该中心像素不会改变欧拉特征（即不会添加/移除孔洞或添加/移除对象），假设为 8 连通对象（对于 4 连通对象，符合这种情况的配置较少，因此很容易解决）。 通常，我们会有一个表格，其中包含这 8 个像素的 256 种可能配置，您可以将配置作为索引编码到表格中（例如，从左上角的像素开始顺时针旋转，将像素读取为 8 位二进制数）。然后可以非常快速地查找是否可以在给定位置删除（或添加）像素。 寻找骨架化算法或形态细化的标准实现。这两个操作在删除每个像素之前对其执行完全相同的检查，它们都需要保留欧拉特征。例如，请参阅scikit-image 中的此表。
您可以查看移除像素（或添加像素）前后 3x3 邻域的配置，并确定该操作是否会改变其所连接对象的欧拉特征。欧拉特征会告诉您有多少个对象和多少个洞。
如果在 3x3 邻域内（不包括中心像素）有 1 到 7 个固定像素，并且它们只是简单连接，则添加或移除该中心像素不会改变欧拉特征（即不会添加/移除孔洞或添加/移除对象），假设为 8 连通对象（对于 4 连通对象，符合这种情况的配置较少，因此很容易解决）。
通常，我们会有一个表格，其中包含这 8 个像素的 256 种可能配置，您可以将配置作为索引编码到表格中（例如，从左上角的像素开始顺时针旋转，将像素读取为 8 位二进制数）。然后可以非常快速地查找是否可以在给定位置删除（或添加）像素。
寻找骨架化算法或形态细化的标准实现。这两个操作在删除每个像素之前对其执行完全相同的检查，它们都需要保留欧拉特征。例如，请参阅scikit-image 中的此表。