Most efficient way to find center of two circles in a picture

Question

I'm trying to take a picture (.jpg file) and find the exact centers (x/y coords) of two differently colored circles in this picture. I've done this in python 2.7. My program works well, but it takes a long time and I need to drastically reduce the amount of time it takes to do this. I currently check every pixel and test its color, and I know I could greatly improve efficiency by pre-sampling a subset of pixels (e.g. every tenth pixel in both horizontal and vertical directions to find areas of the picture to hone in on). My question is if there are pre-developed functions or ways of finding the x/y coords of objects that are much more efficient than my code. I've already removed function calls within the loop, but that only reduced the run time by a few percent.

Here is my code:

from PIL import Image
import numpy as np

i = Image.open('colors4.jpg')
iar = np.asarray(i)
(numCols,numRows) = i.size
print numCols
print numRows
yellowPixelCount = 0
redPixelCount = 0

yellowWeightedCountRow = 0
yellowWeightedCountCol = 0
redWeightedCountRow = 0
redWeightedCountCol = 0

for row in range(numRows):
    for col in range(numCols):
        pixel = iar[row][col]
        r = pixel[0]
        g = pixel[1]
        b = pixel[2]

        brightEnough = r > 200 and g > 200
        if r > 2*b and g > 2*b and brightEnough: #yellow pixel
            yellowPixelCount = yellowPixelCount + 1
            yellowWeightedCountRow = yellowWeightedCountRow + row
            yellowWeightedCountCol = yellowWeightedCountCol + col

        if r > 2*g and r > 2*b and r > 100:  # red pixel
            redPixelCount = redPixelCount + 1
            redWeightedCountRow = redWeightedCountRow + row
            redWeightedCountCol = redWeightedCountCol + col

print "Yellow circle location"
print yellowWeightedCountRow/yellowPixelCount
print yellowWeightedCountCol/yellowPixelCount
print " "

print "Red circle location"
print redWeightedCountRow/redPixelCount
print redWeightedCountCol/redPixelCount
print " "

Update: As I mentioned below, the picture is somewhat arbitrary, but here is an example of one frame from the video I am using:

Answer 1

First you have to do some clearing:

what do you consider fast enough? where is the sample image so we can see what are you dealing with (resolution, bit per pixel). what platform (especially CPU so we can estimate speed).

As you are dealing with circles (each one encoded with different color) then it should be enough to find bounding box. So find min and max x,y coordinates of the pixels of each color. Then your circle is:

center.x=(xmin+xmax)/2
center.y=(ymin+ymax)/2
radius  =((xmax-xmin)+(ymax-ymin))/4

If coded right even with your approach it should take just few ms. on images around 1024x1024 resolution I estimate 10-100 ms on average machine. You wrote your approach is too slow but you did not specify the time itself (in some cases 1us is slow in other 1min is enough so we can only guess what you need and got). Anyway if you got similar resolution and time is 1-10 sec then you most likelly use some slow pixel access (most likely from GDI) like get/setpixel use bitmap Scanline[] or direct Pixel access with bitblt or use own memory for images.

Your approach can be speeded up by using ray cast to find approximate location of circles.

1. cast horizontal lines

   their distance should be smaller then radius of smallest circle you search for. cast as many rays until you hit each circle with at least 2 rays

2. cast 2 vertical lines

   you can use found intersection points from #1 so no need to cast many rays just 2 ... use the H ray where intersection points are closer together but not too close.

3. compute you circle properties

   so from the 4 intersection points compute center and radius as it is axis aligned rectangle +/- pixel error it should be as easy just find the mid point of any diagonal and radius is also obvious as half of diagonal size.

   

As you did not share any image we can only guess what you got in case you do no have circles or need an idea for different approach see:

• Algorithms: Ellipse matching
• find archery target in image of different perspectives

Answer 2

If you are sure of the colours of the circle, easier method be to filter the colors using a mask and then apply Hough circles as Mathew Pope suggested.

Here is a snippet to get you started quick.

import cv2 as cv2
import numpy as np

fn = '200px-Traffic_lights_dark_red-yellow.svg.png'
# OpenCV reads image with BGR format
img = cv2.imread(fn)
# Convert to HSV format
img_hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)

# lower mask (0-10)
lower_red = np.array([0, 50, 50])
upper_red = np.array([10, 255, 255])
mask = cv2.inRange(img_hsv, lower_red, upper_red)

# Bitwise-AND mask and original image
masked_red = cv2.bitwise_and(img, img, mask=mask)

# Check for circles using HoughCircles on opencv
circles = cv2.HoughCircles(mask, cv2.cv.CV_HOUGH_GRADIENT, 1, 20, param1=30, param2=15, minRadius=0, maxRadius=0)
print 'Radius ' + 'x = ' + str(circles[0][0][0]) + ' y = ' + str(circles[0][0][1])

One example of applying it on image looks like this. First is the original image, followed by the red colour mask obtained and the last is after circle is found using Hough circle function of OpenCV.

Radius found using the above method is Radius x = 97.5 y = 99.5

Hope this helps! :)