Problems and Solutions


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.


Take me home