Pixel Vision

Importance of Design

As the project progressed, we as a group realized the importance of design, the from project as a whole, and down to its smallest components.

We had to rework our original design to favour  a more event driven based design, which we thought would be beneficial to implement.  We planned out all aspects of our design in an array of UML diagrams, use cases, a prototype of our GUI, and other documentation, to show our planning, process, progress, and findings to the customer to meet requirements in a timely and organized fashion.  This was done in terms of program implementation and testing of the software to find the bugs and optimal solutions throughout.

This made us appreciate the importance of a quality design.

Graphical User Interface

From the get go our vision was to create a application that would not only satisfy our requirements for our project but also to create a practical application that could be used for real world applications. Our idea behind the GUI was to keep it simple and allows for users to always return to the beginning for multiple images to be processed. Even when switching from the “Vision” tab and “Heat Map” tab, consistency is kept. The application also provides all the interactive tools that all other applications do, like saving an image, printing an image etc. We also provide icons to allow users to associate actions with images so to provide further ease of use.

However, if the user needs a better understanding of how the application works, or what buttons and objects mean, we have provided a “Help” menu for their use. If they would like to know more about our group and the software, they can go to the “About” section located under the “Help” menu which includes a link to this blog.

Heat Map Edges

Work is completed on the heat map for edge and object detection. Based off the found perceived image using offset calculations edges can be isolated by finding pixel influences of neighboring pixels. For each pixel in the the vision image, each can have at most 8 neighbor pixels whereas boundaries will have less depending on if it lies on a straight boundary or a corner.

The algorithm works by taking in to account the amount of influence each neighbor contributes to the current pixel. Because each can have at most 8 pixels, each has an influence of 1/8 or 0.125 as a constant.

The heat intensity is the sum of neighbor pixels red, green and blue values mutliplied by the influence constant. Given that value, it is then mapped to a value in the range [0, 255]. That value is used as lookup in to a palette of heap map colors. This is a gradient image with dimensions 1×256 each with a varying color change which ranges fully through 8-bit color. That lookup color is returned at mapped to the co-ordinate of origin which produces heat signatures of objects in the scene.

The result is seen below as a comparison of the original perceived image and the heat map signature generated by the algorithm.

Heat Wave

Tonight I’m adding on to the core code base some new functionality. In furthering our Pixel Vision suite of software, I’m going to include a heat map edge detection algorithm. The purpose of this is to give the software more means of detecting objects within the scene. This will be based off a heap map of the perceived image. Regions which are “hot” will be areas which are likely edges of objects, “cold” regions will be those in between or non-changing areas such as walls, floors, etc. I think it will if anything bring some nice eye-candy to the stage.

More to follow as the code unravels.

Speed VS. Accuracy

Today I’ve been addressing problems with “Smart” offset calculation. We’ve run in to the problem with our probing methods not reaching the absolute minimal difference. It’s being lost in the recursive search and instead a local minima is found. This is due to the fact that our method attempts to filter as much non-needed information about the image as possible. It uses probe values which represent offsets to calculate the difference and for each iteration, it uses 5 probes. Of those 5, the minimal is found, and the recursion continues using the middle – 1 and middle + 1. This throws away a lot of information, but in the instance where it does it correctly, it does so very quickly.

Alas, it’s not without error. Optimization has already been done in many places such as subsections and data type usage, but this offset needs to be fool proof. So, without further adue, I’ve included another method of offset calculations in the interface. Now the “Smart Distance”, the original quick calculation using 5 probes, is called “Quick Distance” and the new method which uses a simple divide and conquer is called “Smart Distance”. This unit is about to go in to testing, but my initial runs have produced images which appear working consistently and still is much faster than the “Exact Distance” calculation.

Probing Anomalies

As the testing of PixelVision progresses, we discover results not anticipated in our initial plan. This is of course the very purpose of testing in the first place! One of the main focuses of testing PixelVision is verifying that our divide and conquer algorithm works in calculating offsets. Without correct and accurate results, the calculations dependant on offset calculations are destined to fail.

In our application, we have a slider so that the user can select the accuracy to give a better result. As the slider moves from left to right, the accuracy is supposed to increase but with the increase in accuracy comes the increase in time it takes for calculating. Since processing a 3 MegaPixel image to give a meaningful result takes uncomfortably long for an average personal computer, images in the area of 150 000 pixels were tested first.

A simple but effective simulation was written to sequentially calculate the offsets and time elapsed for a range of 5 to 9 probes according to the accuracy slider bar. This result was to be compared with the slow Exact Offset calculations which we have concluded to be correct. Five probes and less than a minute later, we had our first results. The results were not as we anticipated. It seemed that there is no correlation between an increasing amount of probes,  accuracy, and time elapsed. Different images in the same range of sizes were tested as well as a 3MP test image and produced similar results. However, it was noted that the offsets for 5 probes were consistantly within the acceptable accuracy range. There is enough evidence to conclude that the accuracy bar provides only pseudo-accuracy so it has been removed and the number of probes is now statically set to 5.

There still remains many rocks unturned. With testing, we’ll find them.

Recursive Proof

In our initial theory behind processing distances between stereoscopic images, we found that the easiest and most obvious solution, the Naïve approach would give us the most accurate result. This approach involved per pixel subtraction, and works quite well with small (approximately 300×300 pixel) images which yielded several seconds to compute. It then becomes evident that if it takes several seconds to compute a 0.09 Megapixel image, a 3 or 12 Megapixel image would take an eternity to compute.  This became the moment of birth for the Divide and Conquer method.

Once the divide and conquer algorithm was created, the efficency and extent of efficiency must be proved. Also, values used to compute the results must be decided based on time vs. accuracy. A test must be developed  serving the purpose of verifying the accuracy of our new algorithm. Since our algorithm takes a subsection, a ratio used to resize of the original image to omit the “unimportant” areas of the pictures, we must find the ratio that would give us the best efficiency while still remaining accurate. Furthermore, in our algorithm, the images are “dragged” across each other in increments (probes) to then perform the pixel subtraction. From that probe, it recursively performs the same action over again. How many increments yield the best efficiency vs. best accuracy? These questions will be answered in the upcoming tests…

Divide and Conquer

When designing our initial theory behind the stereoscopic image processing we found a method which will linearly find the minimal pixel distance of two images. This is based on per-pixel subtraction of each RGB value. The concept is simple, when two stereoscopic images are taken of a scene there exists a singular point in which the photograph aims to focus on. Each image is hopefully equally offset by both some physical distance between the lenses. This physical offset translates using some trigonometry to produce a pixel distance offset between the images as well.

The linear algorithm we designed at first exhibited an asymptotic order of O(n²). Image processing is destined to work with large datasets, for instance 12MP images and in the future with real-time 30fps video. Obviously a large runtime like that would not suffice. The pseduo code is as follows:

for (delta =  -width to width) {
   foreach (Pixel pL, pR in leftImage and rightImage) {
      sum += pL – pR
   } 

   if (sum < minSum) {
      minSum = sum
      offset = currentDelta
   }
} 

My initial work focused on optimization of this method. Instead of linearly moving the delta across to simulate dragging the left image over the right and performing subtraction on overlapping pixels, I took a different approach.

The optimal method I found works similar to the QuickHull algorithm in computational geometry. It uses a series of probe values which correspond to delta values. It performs complete subtraction of all pixels initially at five locations, 0, 2*Width, Width, Width/2 and (3*Width)/2. Of those probe values, the minimal sum is isolated and new limits are recursed based off the minimal. The surrounding probes are used as the new bounds and the process repeats until the minimal is found. The runtime of this algorithm is O(nlogn) and computes the same offset values much more effeciently.

Actual test results show for images of 300×300 pixels, the time to find the horizontal offset using the linear dragging model was approximately 80 seconds on a 2.4 GHz single core machine. On the same computer, the optimal method takes approximately 4 seconds. A drastic improvement.

new PixelVision();

Follow along our team as we develop our vision project, Pixel Vision. This website will serve as our communication medium to the public about the progress we make. Team members will be blogging about what they’re working on and form a means of discussion about the work.

We look forward to comments and feedback but most importantly making our software available to you to experiment with.