Problems are inevitable in almost every engineering project, and we had
several. It is fortunate that engineers are problem solvers, or we would
have never created any interesting solutions. Here we have listed some of
the problems we encountered, and how we chose to solve them.
Problem:
Finding the dot product of large matrices is time consuming.
Solution:
Shrink the images to a smaller size, resulting in fewer columns to examine.
Shrinking an image is actually an excellent idea. You trade off the
available detail in an image for the speed at which you examine it. While
this would increase the overall correlation between two images, the end user
would spend less time waiting for the product to work. Unfortunately, this
makes it harder to detect good counterfeit bills.
In Matlab, we used the imresize command to resize the matrices. In
the real world, we would not have such a luxury. Loading every vending
machine with an embedded computer and a "Micro-Matlab" kernel is not
realistic at this point. But, it's fortunate that the laws of physics have
provided us with a much faster if not more elegant solution: a simple lens
and a light bulb. A real world vending machine can resize an image quickly
and cheaply with this innovation, and never even touch a computer.
Problem:
The bill being tested could be shifted or out of alignment compared to our
established samples.
Solution:
Well, there are a couple...
The first solution we considered, and the most intuitive, is to shift the
test image around the samples until we found a match. We figured that there
would exist a set of tolerances for how shifted a bill might be. We would
then perform the same operation over the range of these tolerances.
Unfortunately, this was problematic. Specifically, this would take huge
amounts of time. Let's say that our tolerance was a 20 pixel shift in the
columns and a 10 pixel shift in the rows. That means we would have to
perform 20*10 = 200 different scans to find the right region. The dot product
takes between 1-5 seconds, depending on how much resizing we choose. That
means that we might be waiting anywhere from 200 to 1000 seconds, or 3 to 17
minutes! And that's for just one image. We have to do the same
thing across all 14 images. That leaves a worst case analysis time of
between 42 minutes and 3 hours! If I want a tasty beverage from a
vending machine, I want it now, not in 3 hours.
This brings us to our second idea. Instead of blindly guessing about the
alignment of a bill, we could actually go looking for some kind of notable
feature and use that to line up the samples. Hence, the corner detection
algorithm. This idea is so cool, we have a whole
page devoted to it!
Essentially, we look for the corners of the rectangular image on a bill and
use those to align the test and sample images. This rectangular region
should be the same on all bills, so the alignment should be very good if not
excellent.
Problem:
Finding the corners takes lots of time.
Solution:
Cache the values for the sample images.
Since our sample images are always the same, there is no reason we can't
cache the values of their corners to expedite the search. You can see these
values in our inp2.m file. This way, we only have to
find the corners of the image that we are actually testing, and we only need
to do that once. That means we're only searching from 14 to 70 seconds
(Plus another 2 to 3 for the initial corner detection) in the entire
process. This is certainly a lot better than 3 hours.