Archive for June, 2010

Automatic Shape Identification

As a result of our win at the AUVSI competition, the members of ARC were invited to the John Hopkins APL Small UAV Symposium.  During the 5 hour drive back up to Maryland, Alex Ray and I discussed the method that the clever guys over at University of Texas at Austin used for automatic shape identification.  Given that we had some time to kill, we decided to try and implement the method ourselves. Detailed here is my attempt.

Yellow Star photographed by ARC

Yellow Star photographed by ARC

The method begins with a black and white image showing just the shape in question.  For this experiment, black and white images where created as test samples.  Additionally some flight imagery was processed to generate the needed black and white images.  For this example I will process the image below which has been cropped from an image that ARC captured during the competition run.

% Read in the original image
pout = imread(filename);
K = rgb2gray(pout);
% Create a black and white image of the target
K = rgb2gray(pout);
bw = im2bw(K, graythresh(getimage));
bw2 = imfill(bw,'holes');

The above code works effectively on this image to create the needed bw image, however this code will not work on all targets.  Sharp variations in the background and certain target color combinations can ruin the data.  This issue was not further explored because the purpose of this experiment was not finding the targets, but identifying them.  It is assumed that the person using this program would provide a good bw target image.

Using this image an outline of the target is created using the code:

% Find the edge of the object
K = edge(bw2,'sobel');
[K, map] = gray2ind(K,2);

Then the centroid of the object is found using the code:

% Find the centroid
s  = regionprops(bw2, 'centroid');
centroids = cat(1, s.Centroid);

With this data collected it is now possible to generate a signature of the target.  The signature is simply the distance from the centroid of the target to the outer edge.

% Generate the target's signature
dimen = size(K);
counter = 1;
for i=1:dimen(1)
    for k=1:dimen(2)
        if(K(i,k)~=0) % Found an edge point, save the data for this point
                % Distance from centroid
                signature(counter,1) = atan2((centroids(1,2)-i),(centroids(1,1)-k));
                % Angle
                signature(counter,2) = (sqrt((centroids(1,2)-i)^2+(centroids(1,1)-k)^2));
                % Pixel position
                signature(counter,3) = i;
                signature(counter,4) = k;
                counter = counter +1;
% Sort the signature data by angle
signature = sortrows(signature);

From this point on, the challenge it to determine what the signature corresponds to.  For ease of viewing it is easiest to view the signal as plotted in polar coordinates.  The image below shows the signal generated by the preceding script as a blue line.


The method used to process theses images tries to find certain features in the signature; in particular, local maximums and minimums.  Maximums indicate the location of an outside corner.  Minimums indicate inside corners or the midpoints of lines that run past the centroid.  A straight line will appear to get closer and closer to the centroid until it reaches a minimum and then begins to move away.  In the case of the star all minimums are inside corners, but in the rectangle shown below, all minimums are the result of lines passing by the centroid.


To find these points the instantaneous rate of change between each consecutive pair must first be calculated.  This produces the below chart shown in Cartesian coordinates.  Critical points are located at each point where the plot crosses the x axis.  This point can be easily located by checking for a sign change.



Once the critical points have been located it is simply a matter of classifying the target.  Circles are filtered out first by looking for cases where the max and min of the signature are very close together. Next, the classifier discriminates based on the number of critical points.  This will be the final step for ovals and triangles.  For the other shapes a comparison of the  average maximum and minimum points values are compared.  Star like shapes will have a much greater difference than regular shapes.  Quadrilaterals undergo an additional check to compare the values of consecutive maximums.  A large difference will indicate a diamond shape.

When run against a set of seven artificial targets, the method correctly identifies every shape.  Running against the real image set sees excellent results as well.  Moving forward it will be important to expand the data set to include more real images.  There are some enhancements to the current algorithm that may make it more robust.  It would also be interesting to explore the application of a neural net in solving the signature identification.   One final advantage to this algorithm is speed.  When just asked to determine the shape, the star image can be processed in less than half a second.


I’ve made the code available here as a download.  It requires the use of the Mathworks Image Processing Toolbox to work, which I don’t have anymore, so the code is provided as is without testing.


NCSU Aerial Robotics Club 2010 Results

Presented here are the results from NCSU ARC’s competition run at the 2010 AUVSI Student Unmanned Aerial Systems.


Here is the picture we took of the emergent target given during flight.


Every year the targets in the field spell out a message.  This year the message was two part: “Fly safe” and  “Just Joe”.  The second phrase comes from Joe Brannan (The director of the competition) insisting that people just call him Joe instead of Joseph.  The graphic shown above was made using the imagery that we collected at competition with the exception of the “O” target.  The “O” target is provided by Utah State University.

AUVSI SUAS 2010 Results

Overall Results
  1. North Carolina State University
  2. Mississippi State University
  3. Embry Riddle Aeronautical University (Blackbird)
  4. Sherbrooke University (VAMUdes)
  5. University of California at San Diego
Best Flight – North Carolina State University
Best Journal – University of California at San Diego
Best Oral Presentation – Embry-Riddle (Blackbird)
Safety Award – Sherbrooke (VAMUdes)

Prize Barrels
Automatic Target Identification
  • University of Texas at Austin
High Accuracy Target Finding
  • Rutgers University
  • Embry Riddle Aeronautical University (SOAR)
  • Florida International University
Pop-up Target
  • Embry Riddle Aeronautical University (Blackbird)
Actionable Intelligence
  • Utah State University
  • North Carolina State University
Return top