0

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:
still frame with two dots

KenL
  • 157
  • 9
  • 1
    What you want is the [Circle Hough Transform](https://en.wikipedia.org/wiki/Circle_Hough_Transform). There is an implementation in [OpenCV](http://docs.opencv.org/2.4/doc/tutorials/imgproc/imgtrans/hough_circle/hough_circle.html). You may also want to see [this tutorial](https://alyssaq.github.io/2014/understanding-hough-transform/). There is lots of other material available on the Circle Hough Transform, if you need it. – Matthew Pope Apr 04 '17 at 17:39
  • 1
    I can't see your image? – Mark Setchell Apr 05 '17 at 07:22
  • 1
    What other information do you know about the circles? Is there always exactly one red one and exactly one yellow one - or could there be more or fewer of either? Can they overlap? Is either constrained to a specific position or part of the image - e.g. with traffic lights we know red is at the top. Any extra constraints can potentially make the processing faster. – Mark Setchell Apr 05 '17 at 12:46
  • Okay, let me clarify. The picture is completely arbitrary. I chose circles of different colors because I thought that would make analysis easy. The big picture is that I want to take a video, break it into individual pictures, then analyze the pictures to find out how the frame is moving. The circles are just one way to determine points within the frame and thereby calculate how the frame is moving. The video camera approaches the circles, so circle size may change. Ideal processing time? I would love to be able to process 10 seconds of video (300 pictures) within a few seconds or less. – KenL Apr 05 '17 at 18:08
  • 1
    btw to find out how the image is moving you can exploit substraction of smoothed consequent frames... constant stuff will be around zero and moving stuff will be non zero ... from that you can create ROI masks ... – Spektre Apr 05 '17 at 20:15
  • Are you planning on providing images? – Mark Setchell Apr 07 '17 at 20:04

2 Answers2

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.

    circle scan

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:

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • This approach sounds interesting. I've clarified a few things above in comments. Run time was 16 seconds and picture was 538 x 544 pixel .jpg on a MacBook. BTW, I can convert to other picture formats if that helps. Will want to use 4K video. Since I'm uber new to Python, I need some clarification on ray casting. How is that done? – KenL Apr 05 '17 at 18:21
  • @KenL I do not use Python but ray casting is simple is like rendering Line but instead writing pixels you read them. In case of H/V rays its is just single for loop through x or y coordinate .... 16 seconds is too much for your resolution that should be around ~15ms on average PC machine. As I mention before my bet is that `iar[row][col]` is your problem try to access your image by scan lines or bitblt operation. see [Display an array of color in C](http://stackoverflow.com/a/21699076/2521214) how I do in VCL you should find python counterpart .... – Spektre Apr 05 '17 at 20:11
0

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.

Original ImageRed circle mask- mask0circle detected using Hough Circle

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

Hope this helps! :)

harshkn
  • 731
  • 6
  • 13
  • I looked up this approach and saw some comment about it requiring a lot of processing. Would it be faster than ray casting or what I'm doing? I've added a a sample picture above. – KenL Apr 12 '17 at 22:32
  • require lot of processing is a vague term,so I cannot help you there unless you provide clear information.You can always take the code and timeit, then you will know the processing time.I have not worked on ray casting, so I do not know about it.I saw the picture and not sure if I am right, but I understand you want to know the motion in a series of pictures, right? If that is the problem in hand, there are many other ways to estimate motion like background subtraction/optical flow etc. So clearly mention the problem and provide couple of frames to understand, else it will be difficult to help – harshkn Apr 13 '17 at 04:42