## 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. 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. All the code is inside the static class ImageProcessor.

```class Program
{
static void Main(string[] args)
{
ImageProcessor.Process(@&quot;C:\Users\James\Pictures\Blog\sample.jpg&quot;);
}
}
```
```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 &lt; topScore.Length; i++)
{
topScore[i] = 1000;
}

// For each pixel in the image...
Color pixel;
for (var y = 0; y &lt; bitmap.Height; y++)
{
for (var x = 0; x &lt; 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 &lt; 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(&quot;.jpg&quot;, &quot;_output.bmp&quot;);
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 &lt; topScore.Length; i++)
{
if (topScore[i] &lt; 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 &gt; 0; i--)
{
if (topScore[i] &gt; EDGE_THRESHOLD)
{
ball.Left = i;
break;
}
}

// Right edge
for (var i = ball.Center; i &lt; topScore.Length; i++)
{
if (topScore[i] &gt; 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 &gt;= 0)
{
var red = Color.FromArgb(255, 0, 0);

for (var y = 0; y &lt; bitmap.Height; y++)
{
bitmap.SetPixel(ball.Left, y, red);
bitmap.SetPixel(ball.Right, y, red);
}
}

bitmap.Save(outputPath, ImageFormat.Bmp);
}
```
This entry was posted in Projects and tagged , . Bookmark the permalink.