In the template matching algorithm, a sign template is correlated with a larger image that may or may not include the sign. We used the MATLAB function normxcorr2 to correlate the template and image.  Though template matching works perfectly when a smaller reference image is directly cropped from the larger image, in practice we would not have the cropped image.  Thus, our first task was to choose a general reference image.  After finding a good reference image, our second task was to write a program that would find the correlation for many image:reference ratios which would then allow us to estimate the size of the sign within the larger image. This is necessary because we don't know the size of the stop sign in the larger image and if the template is the wrong size there will not be a high correlation even if the template is in the image.

We implemented the template matching algorithm on stop signs first.  The first template tried for stop signs was stop signs with a black background (fig. 1).  This template yielded results of ~75% stop signs detected.  We saw improved results, ~85% signs detected, if instead of using a template with the entire sign, we used a template that was a rectangular red box with the word “stop” (fig. 2).  This is because the area around the edge of the stop sign in the image was significantly different than the template with a purely black background leading to lower correlation values.  

When a full speed limit sign with a single speed was used for the general template, we lost accuracy because the difference in the speed limits themselves (i.e. 55 vs. 40) reduced the correlation.  The top half of a speed limit sign (fig. 3) proved to be a much better template and we were able to detect a majority of speed limit signs (~85%).  We were also able to successfully implement our code on do not enter and one way signs.

If a template is a different size than the sign within the larger image, the sign will not be detected.  To solve this problem we calculated the correlation of the template and image for many different template/image ratios. We scaled down the image as oppose to scaling up the template to cut down on computation time. When a sign is present and when the template and image have the correct ratio, there is a spike in the correlation values (fig. 4). When no sign that matches the template is present, there is not spike in correlation (fig. 5).  By looking at the scaling of highest correlation we are able to estimate the size of the sign and by looking at the point of highest correlation for this ratio we are able to determine the location of the sign.

In the Edge Detection algorithm, regions of the image are found and then put through another algorithm that determines if they are a part of the sign.  We used the MATLAB function edge to find the boundaries of the objects in the image (fig. 6) and then used the MATLAB function regionprops to find regions within the image.  

We first tried to find the border of the sign.  The outside edge of the sign is a region most of the time, so this was a possibility.  However, there is not a good way of determining which region was the sign.  A first guess was to choose the biggest region, however this did not always work as the sign was not always the biggest object in the picture. We then noticed that the O of stop showed up as two regions, the inner ring and the outer ring.  Since these two regions have approximately the same center (fig. 7), it is possible to find regions that have centers close together and then analyze them to see if they are the sign in question.  For example, if the point is on a stop sign, then the point, the point a bit above it, and the point a bit below it will all be red.  If the point is on a do not enter sign, then the point will be white and the points above and below will be red.  

The points above and below were chosen by using the height of the region found.  By choosing points the height of the region above and below the identified center, the points are on the outside of the letter.  This tells the background of the sign itself.  

This method of finding signs is not the most accurate.  It can be fooled by other signs. For example, a sign for a business that had an O on a red background would be considered a stop sign by this algorithm.  This could be helped by checking more points.  Points immediately around the center should also be red and some points in between the center and the currently checked outer points should be white.  This would improve the accuracy, but it could still be fooled. This algorithm also works best for signs with color.  Signs with white backgrounds such as speed limit signs are hard to find because values that are defined as ‘white’ cover a large range of pale colors and therefore many things not signs are identified as signs.  

Despite these drawbacks, this code is advantageous because it does not require large convolutions like the first method. This means that the method is much faster. To find the sign of the correct size with the first approach, it takes about 30 seconds. To find the sign including the size with the second approach, it takes about .5-1 second.

For our final algorithm we used both template matching and edge detection in an attempt to combine the positive aspects of the two approaches.  The combined algorithm first utilizes edge detection to isolate regions within the image, throwing out all regions of a size below a certain threshold in order not to waste time with extraneous convolutions.  Once the significant regions, usually numbering between twenty and one hundred, have been identified, each is re-sized to a standard small template size and compared to each image in the template library.  Regions with high correlations with a template image are assumed to be the part of the sign that template was created from.

This combined algorithm performed quite well, although it was not error-free.  As was the case with pure template matching, attempting to match pictures of entire signs was prone to error because the background of any given sign can vary, occasionally leading to quite low correlations.  However, we discovered that using this algorithm to match only specific elements of a sign, such as the “S”, “T”, “O”, and “P” in stop (fig. 8), was much more reliable, as the conditions for such sub-sign features are much more consistent than for the overall sign.  In addition, searching for individual sign features and not just the sign itself means that partially obscured signs that would be beyond our first template matching algorithm would present no problems for this modified one. Our template library was expanded so as to contain a number of sub-sign features for both stop signs and speed limit signs, as both of these signs contain changing characteristics (background for the stop sign, speed limit for the speed limit sign) that can thwart conventional template matching.  Again, we found that matching individual letters yielded a high success rate (fig. 9).  Our basic algorithm was also fairly successful in identifying one way signs and do not enter signs, even though no sub-feature library was created for these signs and only the sign itself was used as a template.

This algorithm showed significant success in combining the positive aspects of both tablet matching and edge detection.  In comparison to pure template matching, this method performs correlation calculations on much smaller images and size matching is a non-issue because all regions are re-sized to match the templates.  In comparison to pure edge detection, this method is less prone to false positives and can be much more easily expanded to detect new signs simply by adding to the template library.  Overall, the combination of template matching and edge detection yields a more robust, flexible, and reliable method of sign detection than either algorithm used alone.