找到非常规2D形状的最长全内线的算法？
ggf*_*gfl 1 geometry image-processing shape computer-vision computational-geometry
我最近一直在做一些图像处理,我正在寻找一种算法来确定完全在非规则形状内的最长线段.换句话说,线段应该是在其端点处难以接触形状的最长线段.
形状可以表示为一组(x,y)坐标或二进制数组.最外层的像素(边缘)已经确定.一个简单的例子是椭圆,解决方案是主轴.更复杂的例子是等边三角形,这将导致两个像素之间的线与两个单独的角紧邻.我的大多数形状都是椭圆形或"蠕虫状"(长而波浪状).
最后,我希望将此作为一种方法,将"蠕虫状"形状划分为它们的片段,使用一系列大致垂直于此线的"切割".我希望这条消息形成的线条比回归确定的线条更适合这项任务.应该注意的是,这些形状是高分辨率的,因此可能包含多达1000个边缘像素,这就是为什么我试图避免简单的迭代/强力方法.
谢谢你的任何建议!
以下是一些可视化:
我不确定我的想法是否完全正确,但对我来说这听起来是PCA问题,或者在计算机图形学中是一个面向对象的边界框问题.
例:
该盒子的最长轴将是你最长的线.
有关如何计算此框的在线教程,但步骤非常简单:
- 计算您积分的PCA
- 计算点到第一个主成分的投影
- 获得最大分钟
- 将本征空间中的重新投影(max,0,0)和(min,0,0)重新投影到XYZ
- 在他们之间划一条线
请注意,这仅适用于凸形图形.一个椭球,三角形就可以了,但它会为"L"形几何对象计算一个对角线.如果您知道您的对象将是凸的,那么这是获得"最长内部线"的最快且最简单的方法(因为如果它是凸的,则点之间的所有线都是"内部").如果你的对象是非凸的,那么你需要以某种方式将它们分成凸子部分,例如@imaluengo建议.