从图像中获取点

Question

我想从给定图像中提取点。图像如下所示..

我想要的点是绿色的上点和红色的点。我尝试逐像素比较，但速度太慢。我需要一个更好的算法。您有什么建议？

Answer 1

如果这些点始终位于距中心已知的半径处，那么您只需检查圆周上的点即可。

Answer 2

逐像素比较将很难被击败。通过使用分而治之的方法，您可以大大提高绿线上的搜索速度。

如果图像宽度为

x

，高度为

y

，则在位于

x={0...x},y={y/4,3*y/4}

的所有像素中搜索绿色像素。如果没有找到，则沿着

x={x/4,3*x/4},y={0...y}

搜索所有像素。一旦在坐标

p

处找到绿色像素

px,py

，就搜索该像素距离图像中心较远的两像素邻域（即，如果

{px,py+1},{px+1,py}

位于右上角，则为

p

，如果

{px,py-1},{px-1,py}

位于左下角，则为

p

；如果

{px,py+1},{px-1,py}

位于左上象限，则为

p

；如果

{px,py-1},{px+1,py}

位于右下象限，则为

p

。将

p

更新为第一个绿色您找到的邻居。迭代直到

p

不再有绿色邻居。最坏情况下，该算法是

~O(2*(x+y)+(1/2)*max(x,y)) ~= O(2.5*max(x,y)) ~= O(x)

，如果您仅检查每对

O(x*y)

的颜色值，则该算法比

{x,y}

好得多。

但是，找到红点的成本将会很高，不会比

O(x*y)

便宜，因为提高搜索单个红色像素成本的唯一方法是对图像进行二次采样 (

O(x*y)

)，然后搜索红色像素的整个图像（现在

O(sqrt(x*y))

）。

不过，我喜欢 par 的想法，如果两个点距图像中心的距离始终相同，那么您只需搜索沿着该半径的圆周的像素即可！