CSS Sprite Sheet Templates

Here are a few templates I’ve created to assist with building CSS sprite sheets. I use them to help space the images at regular intervals which makes the CSS positions easier to calculate. Just right-click to download them.

16 x 16
sprite16

24 x 24
sprite24

32 x 32
sprite32

48 x 48
sprite48

Advertisements
Posted in Reference | Tagged , | Leave a comment

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);
}
Posted in Projects | Tagged , | Leave a comment

Building a Netduino Rover – Part 5

See other posts in this series

Fuzzy Logic

In this post I’ll show you how to build an object avoidance behaviour using Fuzzy Logic.

In contrast with traditional logic [Fuzzy Logic] can have varying values, where binary sets have two-valued logic, true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1.
Wikipedia

Since my own knowledge of fuzzy systems is somewhat limited, I’d recommend you read Fuzzy Logic Obstacle Avoidance by Seshi. This is where I found the equations that this post is based on.

Like my last post, this code is designed to be ‘plugged’ into my Netduino Rover project as a behaviour. The behaviour starts by initializing the weights in the FAMM (fuzzy associative memory matrix), and calculating the total sum of these weights. This will be used later. Since this behaviour should not prevent others from being executed, the Execute method returns false.

using System;
using Microsoft.SPOT;
using NetduinoRover.Outputs;
using NetduinoRover.Sensors;

namespace NetduinoRover.Behaviours
{
    public class FuzzyBehaviour : IBehaviour
    {
        private Motor _leftMotor;
        private Motor _rightMotor;
        private RangeSensor _leftSensor;
        private RangeSensor _rightSensor;

        private int[][] _weights = new int[3][];
        private double _sumOfWeights;

        public FuzzyBehaviour(Motor leftMotor, Motor rightMotor, RangeSensor leftSensor, RangeSensor rightSensor)
        {
            _leftMotor = leftMotor;
            _rightMotor = rightMotor;
            _leftSensor = leftSensor;
            _rightSensor = rightSensor;

            // Define FAMM weights (fuzzy associative memory matrix)
            _weights[0] = new int[3] { 3, 4, 5 };
            _weights[1] = new int[3] { 2, 3, 4 };
            _weights[2] = new int[3] { 1, 2, 3 };

            // Calculate sum of weights
            _sumOfWeights = 0;
            for (int x = 0; x < 3; x++)
            {
                for (int y = 0; y < 3; y++)
                {
                    _sumOfWeights += _weights[x][y];
                }
            }
        }

        public bool Execute()
        {
            // Pass the sensor readings into the fuzzy system
            double delta = GetFuzzyResult(_leftSensor.Read(), _rightSensor.Read());

            // Change the motor speeds based on the value of delta
            ChangeDirection(delta);
            return false;
        }

        // More methods to follow...
    }
}

GetFuzzyResults takes both sensors readings (in cm) and calculates to what degree each reading belongs to each fuzzy set (Near, Far or VeryFar). To get the fuzzy value, multiply each weight in the FAMM by the left and right membership, then divide the total by the sum of all weights in the FAMM. The output should be on the scale 0.07 (turn left) to 0.15 (turn right). 0.11 means go straight ahead.

private double GetFuzzyResult(int leftDistance, int rightDistance)
{
    // Membership function (left sensor)
    double[] leftMembership = new double[3];
    leftMembership[0] = Near(leftDistance);
    leftMembership[1] = Far(leftDistance);
    leftMembership[2] = VeryFar(leftDistance);

    // Membership function (right sensor)
    double[] rightMembership = new double[3];
    rightMembership[0] = Near(rightDistance);
    rightMembership[1] = Far(rightDistance);
    rightMembership[2] = VeryFar(rightDistance);

    // Defuzzifier
    double total = 0;
    for (int x = 0; x < 3; x++)
    {
        for (int y = 0; y < 3; y++)
        {
            total += _weights[x][y] * (leftMembership[x] * rightMembership[y]);
        }
    }
    return total / _sumOfWeights;
}

Each Fuzzy Set function calculates to what degree the distance belongs to the function. This is a core concept in fuzzy logic; the idea that things are not true/false, rather they exist on a scale from 0 to 1. A given distance can be both near and far at the same time, but to different degrees.

private double Near(double distance)
{
    return Bound(-(distance / 50) + 1);
}

private double Far(double distance)
{
    if (distance < 50)
        return Bound(distance / 50);
    else
        return Bound(-(distance / 50) + 2);
}

private double VeryFar(double distance)
{
    return Bound((distance / 50) - 1);
}

The Bound method ensures the supplied value is kept within the range 0 to 1, rounding it up or down as required.

private double Bound(double value)
{
    if (value < 0)
        return 0;
    else if (value > 1)
        return 1;
    else
        return value;
}

Finally, the result of GetFuzzyResults needs to be converted into something the motors can use. Remember, delta will be in the range 0.07 to 0.15 (with 0.11 in the centre). With a little bit of maths, the input is shaped into a percentage of power for each motor.

private void ChangeDirection(double delta)
{
    // The scale is now -0.04 to +0.04
    delta -= 0.11;

    // Convert to the scale -0.40 to +0.40
    delta *= 10;

    double leftSpeed = 0.5;  // 50% power as a starting point
    double rightSpeed = 0.5; // 50% power as a starting point
    leftSpeed -= delta;
    rightSpeed += delta;

    // Send steering to motors
    _leftMotor.SetSpeed(leftSpeed);
    _rightMotor.SetSpeed(rightSpeed);
}

With the behaviour complete, it can be plugged into the behaviour stack (see my last post).

Here’s a video of the finished rover:

Posted in Projects | Tagged , , | Leave a comment

Elite – The Sequal

For those who remember the 1980’s, you might recall the mother of all space trading games; Elite. One of the original authors (David Braben) is raising support to build a modern sequel called Elite: Dangerous, over on Kickstarter.

In just a few short weeks they have raised an astonishing £810,000, but with only 16 days left they need one final push to reach their target of £1,250,000. Can you help make this happen?

David already has the vision, and the team, he just needs to raise the support. Your donation is only taken if they reach their deadline.

Check out their Kickstarter page to make a pledge.

Elite: Dangerous – Teaser Trailer

Posted in Uncategorized | Tagged | Leave a comment

Building a Netduino Rover – Part 4

See other posts in this series

Basic Object Avoidance

I’ve designed this rover to be autonomous rather than remote controlled. The software is designed around the idea of combining many simple behaviours together to produce what appears to be complex behaviour. You can think of the behaviours as being arranged in a stack, with the (important) collision detection at the top, and the (not quite so important) steering behaviours at the bottom. Each behaviour in the stack is executed in turn, starting at the top. Each behaviour can decide to stop further processing of the stack. After a short delay, the process is repeated starting again from the top of the stack.

The example on this post only has two behaviours, ReverseBehaviour which moves the rover backwards when an obstacle is nearby, and ForwardBehaviour which moves the rover forwards. The rover won’t appear very smart with only two behaviours, but more can be added later. This is a scalable design that is easy to maintain.

Here’s the Rover class showing the behaviour stack and the Motor and RangeSensor classes from part 3.

using NetduinoRover.Behaviours;
using NetduinoRover.Outputs;
using NetduinoRover.Sensors;
using SecretLabs.NETMF.Hardware.Netduino;

namespace NetduinoRover
{
    public class Rover
    {
        private Motor _leftMotor;
        private Motor _rightMotor;
        private RangeSensor _leftSensor;
        private RangeSensor _rightSensor;
        private IBehaviour[] _behaviours;
        private int STEER_CORRECTION = 320;
        
        public Rover()
        {
            // Define outputs
            _leftMotor = new Motor(Pins.GPIO_PIN_D6, Pins.GPIO_PIN_D7, STEER_CORRECTION);
            _rightMotor = new Motor(Pins.GPIO_PIN_D5, Pins.GPIO_PIN_D4, STEER_CORRECTION * -1);

            // Define inputs
            _leftSensor = new RangeSensor(Pins.GPIO_PIN_A5);
            _rightSensor = new RangeSensor(Pins.GPIO_PIN_A4);

            // Define the behaviours you want - the order is very important!
            _behaviours = new IBehaviour[2];
            _behaviours[0] = new ReverseBehaviour(_leftMotor, _rightMotor, _leftSensor, _rightSensor);
            _behaviours[1] = new ForwardBehaviour(_leftMotor, _rightMotor);
        }

        public void Move()
        {
            foreach (var behaviour in _behaviours)
            {
                var hasFired = behaviour.Execute();

                // If this behaviour fired, stop processing other behaviours in the array
                if (hasFired)
                    break;
            }
        }
    }
}

By creating an interface for the different behaviours, the Rover class becomes de-coupled from the actual implementations. This makes it easier to work with an array of behaviours – it also makes it easier to add new behaviours in the future. The interface contains a single method Execute which returns a boolean to show if further behaviours should be executed.

namespace NetduinoRover.Behaviours
{
    interface IBehaviour
    {
        bool Execute();
    }
}

As the name suggests, the ForwardBehaviour instructs the Rover to move forward (at 60% speed). The Execute method returns false to allow other behaviours in the stack to execute.

using NetduinoRover.Outputs;

namespace NetduinoRover.Behaviours
{
    public class ForwardBehaviour : IBehaviour
    {
        private Motor _leftMotor;
        private Motor _rightMotor;

        public ForwardBehaviour(Motor leftMotor, Motor rightMotor)
        {
            _leftMotor = leftMotor;
            _rightMotor = rightMotor;
        }

        public bool Execute()
        {
            _leftMotor.SetSpeed(0.6);
            _rightMotor.SetSpeed(0.6);
            return false;
        }
    }
}

The ReverseBehaviour checks to see if either of the range sensors are close to an obstacle. If they are, the motors are set to reverse and true is returned to prevent further behaviours from running. This allows the ReverseBehaviour to take precedence over other behaviours, since avoiding obstacles is more important than always moving forward.

using Microsoft.SPOT;
using NetduinoRover.Outputs;
using NetduinoRover.Sensors;

namespace NetduinoRover.Behaviours
{
    public class ReverseBehaviour : IBehaviour
    {
        private Motor _leftMotor;
        private Motor _rightMotor;
        private RangeSensor _leftSensor;
        private RangeSensor _rightSensor;

        public ReverseBehaviour(Motor leftMotor, Motor rightMotor, RangeSensor leftSensor, RangeSensor rightSensor)
        {
            _leftMotor = leftMotor;
            _rightMotor = rightMotor;
            _leftSensor = leftSensor;
            _rightSensor = rightSensor;
        }

        public bool Execute()
        {
            // Are we going to hit somthing?
            if (_leftSensor.Read() < 10 || _rightSensor.Read() < 10)
            {
                // Slow reverse
                _leftMotor.SetSpeed(-0.8);
                _rightMotor.SetSpeed(-0.8);
                return true;
            }
            return false;
        }
    }
}

The main program simply creates an instance of the Rover class and calls the Move method repeatedly.

using System.Threading;

namespace NetduinoRover
{
    public class Program
    {
        public static void Main()
        {
            var rover = new Rover();
            
            while (true)
            {
                rover.Move();
                Thread.Sleep(100);
            }
        }
    }
}

Here’s a video contrasting this approach with a different approach (Fuzzy Logic).

Posted in Projects | Tagged , , | Leave a comment

Building a Netduino Rover – Part 3

See other posts in this series

Software Basics
If this is your first Netduino project you’ll probably need to install a few things. Everything you need to get started is free, and can be found here on the Netduino website. I’m going to assume you have the environment setup and that you have a basic knowledge of programming.

The first task is to abstract away some of the complexity caused when dealing with hardware. The class below controls a single motor via the SetSpeed method, which takes a value on a scale of -1.0 to 1.0. Passing a negative value automatically sets the motor into reverse.

using Microsoft.SPOT.Hardware;
using SecretLabs.NETMF.Hardware;

namespace NetduinoRover.Outputs
{
    public class Motor
    {
        private PWM _motor;
        private OutputPort _direction;
        private int _correction;

        private const uint PERIOD = 1000 * 50;
        private const int TOP_SPEED = 10000;

        public Motor(Cpu.Pin pwm, Cpu.Pin direction, int correction)
        {
            _motor = new PWM(pwm);
            _direction = new OutputPort(direction, true);
            _correction = correction;
        }

        // Sets the motor speed and direction on a scale of -1 to 1
        public void SetSpeed(double percent)
        {
            // Set direction
            if (percent < 0)
                _direction.Write(false);
            else
                _direction.Write(true);

            // If the percent is negative, make it positive
            if (percent < 0)
                percent = percent * -1;

            // Set pulse width modulation (PWM)
            double duration = percent * TOP_SPEED;
            duration += _correction;
            _motor.SetPulse(PERIOD, (uint)duration);
        }
    }
}

The second task is to create a class to handle the distance sensors. If you read the raw value from the sensors you’ll find that the value increases as the distance decreases. The class below performs a (very crude) conversion of the raw value into a distance in centimetres.

using Microsoft.SPOT.Hardware;
using SecretLabs.NETMF.Hardware;

namespace NetduinoRover.Sensors
{
    public class RangeSensor
    {
        private AnalogInput _analogInput;

        public RangeSensor(Cpu.Pin pin)
        {
            _analogInput = new AnalogInput(pin);
        }

        // Returns approximate distance in cm
        public int Read()
        {
            int sensorReading = _analogInput.Read();

            // Very crude conversion to cm
            double distanceInCm = (1000 - sensorReading) * 0.1;
            
            // Ensure answer is sensible
            if (distanceInCm > 0 && distanceInCm < 100)
                return (int)distanceInCm;
            else
                return 100; // default
        }
    }
}

By using the classes above you should be able to build a simple program to control the rover and detect obstacles. In parts 4 and 5 I’ll show two different ways of implementing this, as well as how to build a behaviour based architecture.

Posted in Projects | Tagged , , | Leave a comment

Building a Netduino Rover

Part 1 – Parts List
Part 2 – Adding a Bumper
Part 3 – Software Basics
Part 4 – Behaviour Based Robotics
Part 5 – Fuzzy Logic

Posted in Projects | Tagged , | Leave a comment