從圖像中獲得分數

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}的所有像素。只要在座標px,py處發現綠色像素p，就搜索距離圖像中心較遠的那個像素的兩像素鄰域（即，{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的想法，但是，如果兩個點始終與圖像中心的距離相同，那麼您可以只搜索沿該半徑的圓周落下的像素！