A Simple Ball Finding Algorithm

I’ve recently been playing with a Netduino and I’m considering connecting a camera to my Netduino powered Rover, with the aim of making it follow a ball. The trouble is the Netduino is very limited on RAM (60 KB), so doing any kind of image processing is tricky. I need an algorithm that can locate a ball within the image without needing the whole image in memory…

The example below demonstrates a possible solution – note that although I am loading the image into memory, the image processing algorithm doesn’t require this. It should work just the same by reading the image one byte at a time using a stream, provided the image is a bitmap.

findball

The algorithm works as follows:

  1. For each pixel in the image, calculate the difference in color to the target ball color.
  2. For each X position, store the lowest difference calculated so far in an array.
  3. Move through the array and find the index with the lowest value. This gives the X position for the Center of the ball (It’s not really the center, it’s just a point inside the ball with the best color match).
  4. Starting from the Center, move left and right along the array until the values in the array exceed the Edge Threshold (50). This will give the X position for the Left and Right edges of the ball.

Here’s the target ball color represented by the RGB values 255, 155 and 22.

findball_color

All the code is inside the static class ImageProcessor.

class Program
{
    static void Main(string[] args)
    {
        ImageProcessor.Process(@"C:\Users\James\Pictures\Blog\sample.jpg");
    }
}
public static class ImageProcessor
{
    private static int EDGE_THRESHOLD = 50;

    public static void Process(string fileName)
    {
        var file = new FileInfo(fileName);
        var bitmap = new Bitmap(fileName);

        // Define the array
        var topScore = new int[bitmap.Width];

        // Define the target ball color
        var ballColor = Color.FromArgb(255, 155, 22);

        // Initialize the array to a high value
        for (var i = 0; i < topScore.Length; i++)
        {
            topScore[i] = 1000;
        }

        // For each pixel in the image...
        Color pixel;
        for (var y = 0; y < bitmap.Height; y++)
        {
            for (var x = 0; x < bitmap.Width; x++)
            {
                pixel = bitmap.GetPixel(x, y);

                // Calculate the difference in color between this pixel and the target ball color
                var difference = CompareColor(pixel, ballColor);

                // Store the lowest difference calculated so far
                if (difference < topScore[x])
                    topScore[x] = difference;
            }
        }

        // Find the index with the lowest value
        var ball = FindBall(topScore);

        // Find left and right edges of ball (and therefore distance)
        ball = FindEdges(ball, topScore);

        // Draw lines to show the ball edges
        var outputPath = file.FullName.Replace(".jpg", "_output.bmp");
        DrawLocation(ball, bitmap, outputPath);
    }

    // Other methods to follow...
}

CompareColor calculates the sum of RGB differences between the specified pixel and the ball color.

private static int CompareColor(Color pixel, Color ballColor)
{
    var dR = Math.Abs(pixel.R - ballColor.R);
    var dG = Math.Abs(pixel.G - ballColor.G);
    var dB = Math.Abs(pixel.B - ballColor.B);
    return dR + dG + dB;
}

FindBall finds the index in the array with the lowest value. This gives the X position for the point inside the ball with the best color match.

private static BallPosition FindBall(int[] topScore)
{
    var bestScore = 1000;
    var ball = new BallPosition { Center = -1 };

    for (var i = 0; i < topScore.Length; i++)
    {
        if (topScore[i] < bestScore)
        {
            ball.Center = i;
            bestScore = topScore[i];
        }
    }
    return ball;
}

BallPosition stores the Left, Right and Center positions of the ball relative to the image being processed.

public class BallPosition
{
    public int Center { get; set; }
    public int Left { get; set; }
    public int Right { get; set; }
}

FindEdges calculates the Left and Right edges of the ball by searching the array (outward from the Center) until the values exceed the Edge Threshold (50).

private static BallPosition FindEdges(BallPosition ball, int[] topScore)
{
    // Left edge
    for (var i = ball.Center; i > 0; i--)
    {
        if (topScore[i] > EDGE_THRESHOLD)
        {
            ball.Left = i;
            break;
        }
    }
            
    // Right edge
    for (var i = ball.Center; i < topScore.Length; i++)
    {
        if (topScore[i] > EDGE_THRESHOLD)
        {
            ball.Right = i;
            break;
        }
    }
    return ball;
}

DrawLocation generates the example output image and draws the ball position.

private static void DrawLocation(BallPosition ball, Bitmap bitmap, string outputPath)
{
    if (ball.Center >= 0)
    {
        var red = Color.FromArgb(255, 0, 0);

        for (var y = 0; y < bitmap.Height; y++)
        {
            bitmap.SetPixel(ball.Left, y, red);
            bitmap.SetPixel(ball.Right, y, red);
        }
    }
            
    bitmap.Save(outputPath, ImageFormat.Bmp);
}
Advertisements
This entry was posted in Projects and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s