Dave Grossman comments on Blob Analysis Library

This post is meant as an archive, particularly because it is useful and easier to refer to.
Taken from unstable hosting at osdir: http://osdir.com/ml/lib.opencv/2005-11/msg00200.html?rfp=dta

RE: Re: help for CVBLOBSLIB!: msg#00200
Subject:
RE: Re: help for CVBLOBSLIB!

RE: Re: help for CVBLOBSLIB!: msg#00200

Subject: 
RE: Re: help for CVBLOBSLIB!
By now I imagine that rickypetit understands the truth of the old adage that "no
good deed goes unpunished!" He deserves a lot of credit for converting my blob
analysis code into cvblobslib. The result has been many more users, and
therefore many more questions. So, I will try to help him out here by providing
some answers. However, these answers all relate to my original code, which was
deprecated about 2 years ago when cvblobslib was created. And I've never used
cvblobslib. So, my answers are probably somewhat obsolete... 
I don't have any additional documentation on the blob analysis algorithm. I
first saw this algorithm about 33 years ago in a presentation by Gerry Agin at
SRI International (then called Stanford Research Institute). I have been unable
to find it in any journal articles, so I implemented it by memory. The basic
idea is to raster scan, numbering any new regions that are encountered, but also
merging old regions when they prove to be connected on a lower row. The
computations for area, moments, and bounding box are very straightforward. The
computation of perimeter is very complicated. The way I implemented it was in
two passes. The first pass converts to run code. The second pass processes the
run codes for two consecutive rows. It looks at the starting and ending columns
of a region in each row. It also looks at their colors (B or W), whether or not
they were previously encountered, and whether a region is new or old, or a
bridge between two old regions. There are lots of possible states, but I deal
explicitly with the only states that are important. 
The x centroid Xbar is determined by adding the contribution for each row. In
each row, if the pixels of a region are at y1, y2, ..., yn, then just add up all
these values y1+y2+...+yn. (Or equivalently, n[y1+yn]/2.) After finishing all
the rows, you have to divide the accumulated value by the area A. 
The y centroid Ybar is determined as follows: For each row x, let the length of
the run be n. Then just add x*n for all rows. When finished, divide by the area
A. 
Perimeter is really complicated for 2 reasons: 
(1) A region may contain an interior region, so there is an interior perimeter
as well as an exterior perimeter. Since people usually want perimeter to be only
the exterior perimeter, the perimeter of the interior region has to be
subtracted at the end of the computation. 
(2) When analyzing a particular row, you can only compute the perimeter
contribution of the prior row. (This is different from area and centroid, where
the computation is for the current row.) I found the perimeter computation very
complicated, and I no longer remember how it works. The moment computation
accumulates X^2, XY, and Y^2. But you really want (X-Xbar)^2, (X-Xbar)*(Y-Ybar),
and (Y-Ybar)^2. So there is an adjustment at the end of the computation once the
centroid values Xbar and Ybar are known. 
// Case        1       2       3       4       5       6       7       8 
// LastRow |xxx    |xxxxoo |xxxxxxx|xxxxxxx|ooxxxxx|ooxxx  |ooxxxxx|    xxx| 
// ThisRow |    yyy|    yyy|  yyyy |  yyyyy|yyyyyyy|yyyyyyy|yyyy   |yyyy   | 
// Here o is optional 
At each stage, the algorithm is scanning through two consecutive rows, termed
LastRow and ThisRow. During this scan, it sees a region in each row. 
In Cases 1-4, the region in LastRow starts 2 or more columns before the region
in ThisRow. 
In Case 1, the region in LastRow ends one or more columns before the region in
ThisRow starts. Therefore, these regions are NOT connected. In Case 2, the
region in LastRow starts before the region in ThisRow, but the LastRow region
continues at least to the column just before the region in ThisRow starts. Or it
continues further, but it ends before the region in ThisRow ends. Therefore, if
these regions have the same color, then they are connected. 
(Note that I am using 6/2 connectivity, which means that at a corner like this 
01 
10 
the 0's are connected but the 1s are not connected. In other words, the
connectivity of a pixel is given by this mask: 
110 
1X1 
011 
i.e., pixel X is connected to the 6 pixels with a 1 but is not connected to the
2 pixels with a 0. This introduces a slight bias in favor of regions that slope
to the left, but I consider it preferable to using either 4-connectivity or
8-connectivity. 
*** I believe that the rickypetit cvblobslib generalizes this to allow the user
to choose the form of connectivity.) 
In Cases 3 and 4, the region in LastRow starts before the region in ThisRow. 
In Case 3, the region in LastRow continues beyond the region in ThisRow; in Case
4 they end at the same column. In Cases 5, 6, 7, the region in LastRow starts at
or after the column of the region in ThisRow. The distinction among these three
cases is which region ends first. 
In all of Cases 3 - 7, if the colors match then the regions are connected.
Finally, Case 8 has the region in ThisRow end one column before the region in
LastRow. 
These are ALL the possible cases. Depending on the case, the algorithm then
advances to the next region either in LastRow, or ThisRow, or both. When it
exhausts both rows, it then increments the row by one, so LastRow <- ThisRow,
and ThisRow is the next row encountered.      

Week 07 - Blob blog.

0218

I spent the day revising my article for IHPC's newsletter. In my opinion, this is a timely checkpoint for a small self-assessment as well as a short break from development. The article is a brief overview on what Lightdraw is about and why it deserves attention (or not). Writing helps me see how much I've progressed thus far, and serves as a good gauge of how much of my work might actually be important enough to share. Furthermore, having to pen down the methodology in ink means having to explain the rationale of my code (how and when should the code be used). Without explanation code is just a bunch of logic and by itself is not very useful at all.



0219

Finally managed to finish the long overdue Lightdraw video with Peng and JL today.



0220

Favoured Dave Grossman's blob detection over my existing code which used contour detection. The blob detection is much more efficient since it picks up blobs in a single pass. As a result of the tremendous improvement of blob detection algorithm real-time laser tracking is possible.



0221

Studied my code closely, and with some trial and error I found a few pitfalls which reduced the frame rate.
- OpenCV's canny detection reduces frame rate by ~2 fps
- Frame rate is halved after I resized the OpenCV window.
- Morphology operations (i.e dilate, erode) reduces frame rate too. The larger the size of the structuring element used, the greater drop in fps.



0222

Since I'm so intrigued by blob detection efficiency over contour detection, I did some reading on their main differences. Discussion on performance difference between Counter detection and blob analysis and when to use which:
http://tech.groups.yahoo.com/group/OpenCV/messages/38670?threaded=1&m=e&var=1&tidx=1

In a nutshell, BlobsLib is faster for more than 5 blobs. Contour is faster for lesser blobs.
My suggestion is to take the advice with a pinch of salt and do your own benchmarking to see which works best for you.

Week 06 - Integration with Laser Detection

0211

For simplicity's sake, development for the past few weeks was done in an ideal lighting environment. This week my objective is to move my setup to the back projection system.

First thing I needed was to get the camera to see the laser points at the very least. I felt that this is crucial, because even a perfect laser detection program would not be able to function properly if the video input does not reflect the laser point half the time. The best a program can do is to cope with lossy input and perhaps extrapolate a set of points when there are gaps in a stroke. Still, this requires reliable input from the camera at the frontline in order to provide for small loss tolerance levels.

After trying several kinds of configuration again, my conclusion is that placing the camera at the back with the projectors is ideal. Somehow our previous experiment (ref: post 0118) went wrong. Also, setting the exposure settings to lowest on the DVcam allows me to see only the laser dot, which is excellent really, but the bandwidth between the cam and the computer is slow at only ~15fps. [0218, Edit: I found a setting that enables me to jack up shutter speed using the sports mode, under the menu "Program AE". Joy!] An ideal camera would probably be one with manual exposure and manual focus and manual shutter speed settings that achieves >= 30fps easily.



0212

My school's academic supervisor Dr Teo came down for a visit today to learn what Lightdraw is about.

Demonstration went relatively well, except when I had to switch from the front camera to the one at the back. Mental note: For demonstration use only lightdraw account.

So far I am able to give the coordinate of the laser point on an image, detect its colour and trace its motion. Things get trickier when I have two different coloured lasers crossing paths, then I am not able to tell which path belongs to which, for now.



0213

Learned how to install drivers on Mac computers, and got my USB camera to work with the Light the Mac, but only on lightdraw account. Weird huh.

Debugging ensues...



0214

Today was spent cleaning up my code and trying to make it more efficient. Each time a image processing function is called, it makes a few passes (scanning every pixel of image). Furthermore, every loop calls a few of these functions, causing the program not being able keep up with the frame rate.

I found some articles and samples on blob detection mainly for comparison and while these algorithms highlights all kinds of blobs in general, some are really fast and efficient. Since I want to highlight laser points specifically, I could use some of the readily available blob detection methods and combine it with my own filters, then hopefully I would have something that is both efficient and reliable. Here's an interesting article I found on the comparison between blob analysis and edge detection algorithms in practice: http://archive.evaluationengineering.com/archive/articles/0806/0806blob_analysis.asp
Note: I found the article perspective is biased for edge detection algorithm.

OpenCV provides for blob detection, but the OpenCV community attests to its poor reliability.
Currently I am using another slightly different version (just a difference in structuring elements used) of blob detection that works fine for me, as I have cleaned up the image before feeding it to the blob analysis algorithm. The version of blob analysis that I am using is Dave Grossman's, who claimed that he implemented G J Agin's algorithm from memory after attending the latter's presentation. This is because Agin's paper is difficult to find since it is at least 35 years old! (I even tried looking in ACM and IEEE) Dave Grossman tries to explain the algorithm briefly in his post here http://osdir.com/ml/lib.opencv/2005-11/msg00200.html

More details on the algorithm here:
http://opencvlibrary.sourceforge.net/cvBlobsLib



0215

Got part of moveresize to work with laser on back projection screen. I can drag the box around now if I move my pointer around, slowly. Looks like there's more optimizing to be done.

Week 05 - Happy Lunar New Year!

0204

I had to breakdown moveresize.c (a Lightdraw demo, not written by me) into manageable chunks for a few purposes

• It's easier for me to document along the way.
• Refactoring will be much easier after documentation.
• It will be obvious which portion of code goes into the Lightdraw libraries eventually.

Tuesday will be Peng and JL's attachment presentation, and will also be their last day of work in the Cove.



0205

Peng and JL's presentation went pretty well. Luckily Peng spotted a question the night before and asked me about exceptional common-vertex cases for the in-out algorithm (whether a point is inside or outside of a polygon). Of which I just gave the typical solution from the scan-line algorithm that I learned from Computer Graphics last semester.

Dr. Su Yi gave a few pointers for further developments during the discussion on contour processing. The contours could be converted into point sequences for plotting points as the user draws. The contour detection could then be based on a well defined polygon instead of using the current polygon approximation. This has to do geometry processing, something which I will have to look into.

Wonderful farewell lunch for Peng and JL at Au Da Paolo Petite Salut, a French restaurant located near Holland Village. Food was excellent. Best chicken leg I had in a long time, must go back there again! Did not recognise any of the wines they had there. Cost of wine there is rather steep at $16 by the glass.



0206

Half-Day. Laser tracking with screen coordinates on the way.


0207 - 0208
Happy Lunar New Year!

Week 04 - Triggering Events

0128

Went to a local precision optics company to sample the ~532nm bandpass and ~650 longpass filters. The red longpass worked really well and the green laser point was not visible at all despite its high intensity. The laser dots appear as the brightest pixels when the webcamera were fitted with the respective filters.

Back at the Cove, we resumed our UML discussion and added methods to class diagram, mainly to the Lightdraw controller and DisplayManager singletons.



0129

Implemented a feature to detect when the user has the laser point hovering over an area (triggers a hold event). This is done using a separate motion history buffer with a shorter timeout duration.

With this, a user can control when he wants to draw graffiti by triggering the hold event to begin drawing. Drawing ceases when laser point goes out of screen, or when laser is switched off.

Note: Further work can be done to make the detection more accurate. Take the region of pixels the laser point is sitting on, which will have timestamp equal to 0 or some value. Search for the set of immediate pixels with timestamp equal to this value, and empty the complement of this set (i.e setting the timestamp of the rest of the canvas to 0). This will guarantee that only one laser point can trigger the hold event.



0130

Because the UML diagrams have grown so much, Kevin suggested we have the diagrams on the projection screen, and seemed like a much better idea. I had a go with Mac's version of UML diagram software, called OmniGraffle. I felt that it was easy to use, and had all the basic functionalities that I needed. However, I felt that the feature that allows a user to tag notes is quite inflexible. What I wanted was to tag individual methods in a class but it only allowed me to tag the entire class due to some restrictions.

Rebuilt one of the USB infrared pens to a battery operated one instead. The end result works but did not look pretty at all.



0131

Today's UML discussion was mainly on how to handle events. Kevin suggested a signal-slot mechanism, and I got really confused while trying to understand what "slots" were.

So I did some reading up, and these are two of the more informative links I came across.

http://doc.trolltech.com/3.3/signalsandslots.html

http://sigslot.sourceforge.net/sigslot.pdf

The paper has a simple and effective example (using lights and switches) to show how two tightly coupled classes can inherit signal-slot classes to become loosely coupled classes, yet maintain type safety between them. Neat!



0201

Contacted my academic supervisor today to setup a meeting on Tuesday the week after next.

Merging of the programs moveresize and laserMotion still in progress.

Week 03 - Design, design, design!

0121

The Lightdraw team held a meeting to this morning as planned, and will continue to do so every morning this week.

For once, I found myself in a place where design and planning is not brushed away as if it were an unnecessary and time-wasting process. As this blog is not a platform for me to talk about the kind of development horrors or design architectures that will inevitably-collapse-unto-itself that I've previously encountered in past working experiences, I would just like to say that I am so darn glad that things are different here. Hope, is that you?

With help from everyone, the use case diagram was done without too much difficulty. I felt that it was a good reality check for two reasons. Firstly, it was a good chance for the team to clarify doubts, so everyone can be sure to have a common understanding of Lightdraw. Secondly, this forces me to revise my software engineering concepts.

Originally we had planned to use the afternoon to go Sim Lim today to get our supplies. However, the trip got postponed to Tuesday. I carried on with my debugging and managed to get my program to clear the canvas properly. Did so by splitting update_mhi into two parts: one for marking out motion, the other for indexing each pixel of movement with timestamp in a separate image buffer.

I contacted a local company that deals with precision optics, and they claimed to have the optic filters that I am looking for. However, I wasn't able to get a quotation from the lady since the sales department was busy.



0122

Did domain modeling in the morning. Its like a simplified class diagram, so that its easier to separate the different aspects of our program, and group components with similar functionality together.

We went to Sim Lim after lunch. I was able to find the stuff needed for making an IR Wii pen. I bought:

• 4x rechargeable AAA batteries
• 2x IR LED (2-3V)
• 2x 39 Ohm resistor (0.25 Watts)
• 2x Usb connectors
  
• Crocodile clips

The camera shops did not sell the optical filters that we were looking for.



0123

Spent the morning assembling the two IR pens. How do I know it works? Webcams can see infrared light. Hand phone cameras will work too. With my webcam I was able to tell that the infrared LED can be switched on.

Overloaded the minus '-' operator in imageWrapper.h, so that I can subtract pixel values from an image with another. i.e two image buffers A and B

dst[x,y] =
0, if A[x,y] - B[x,y] is less than 0,
A[x,y] - B[x,y] otherwise.

I needed this to kill the dopplegänger effect in motion detection (it renders the motion twice, with delay). This is caused by the way update_mhi (originally) behaves. A motion is defined as a change in light. And light is given a numerical representation using image buffers. update_mhi finds the absolute difference between two frames, so it defines motion as the pixel difference between the old and new image. So it draws the moving object twice: first from the object's previous location (found in the previous frame), second the object's new position.

By Wednesday, we've got a design pattern that's beginning to look like Models View and Controllers (MVC ). We've also agreed on a nifty menu that we can use to interface with applications. Kevin found two more use cases we missed. Given time, all design diagrams will grow into big ugly monsters, and I've got two (unrelated ones) right here:




Flowchart of my school's software engineering project. Chart is so big it had to be cropped into two pictures. I still find these diagrams hilarious.



0124

We've got a good-looking but incomplete class diagram today. CT was able to write a pseudo graffiti program with ease. We noticed that the developer writing the program had to pass a function pointer though. There's still multithreading that we've yet to take into account.

Added a window that is a cross between canny and motion detection, so I get a visual feedback of where my pointer is when I'm drawing an image.

Got the Wii setup up, works well when wiimote is 35degrees from the LCD plane. Calibration was not as easy as it seemed, mainly because the wiimote was not able to see the infrared LED at certain angles.



0125

Experimented using some kind of grey scale and pattern printed on a transparency as a webcam filter as I thought that it may help detect the laser light on a bright background. No dice, I should use a tinted filter to help to reduce intensity instead.

Colour detection much more successful with my new webcam, Z-Star Micro zc0301p.



















Next would be flood fill, pause detection, calibration and some kind of demo.

We're going to visit the precision optics company next Monday.

Week 02 - Laser Detection I

0114

The week began with a question: How do I differentiate the laser dot from its background? The bright green dot could easily be a bullet on a presentation slide, or the desktop background, or the mouse pointer, or ....

I would like to think that I am able to differentiate a laser point from the background via:

1. Color separation
2. Motion tracking
3. Canny edge detection

I decided to use OpenCV libraries to implement these methods, with the aim of finding the capabilities and limitations of what I can do for each of the three. Hopefully, one method would be able to make up for the shortcomings of the others. Then, a combination of methods will give me a better approximate for the location of the laser point.

I began working on the HSV colour model. I know that I will be looking for a green hue of high saturation and brightness. The green hue would be in a extremely small range of approximately 180 degrees. I tried to use OpenCV to convert the image from a RGB to HSV colour model, before extracting the individual H,S and V channels from the resulting image. Getting the full channels is no problem at all, but I am only interested in a certain hue. Unfortunately for me, OpenCV uses a very different scale for HSV.

Usually, H spans from 0 to 360 degrees, and S, V would take on values from either 0 to 1, or 0 to 100. OpenCV did not state explicitly what range of values HSV would take on, but a quick look at the sample code (camshiftdemo) reveals that in OpenCV, H spans from 0 to 180 degrees, and values of S,V spans from 0 to 255. Confusion! I would have to try and error to understand the scale used in OpenCV.

Took a little time off after work to help debug Peng's program and caught two nasty bugs.



0115

By Tuesday, I was still unable to extract the laser hue from the webcam feed. I found out that my webcam sees the red and green laser dots as white instead of their respective colours, mainly because of their intensity. I am able to get the webcam to pick up their colours only on two occassions; when the laser dot is in motion, and when the camera is ridiculously out of focus. A comparison between my webcam and the iSight shows that the Apple iSight is able to pick up the colour of the laser dots better than my Logitech Quickcam IM

As progress was slow with HSV, I had to put a hold on this until I can grab hold of a better webcam or think of a solution. I spent the rest of the day working on motion tracking, mainly with the use of the template included in OpenCV.



0116

Motion tracking is far more successful at detecting the laser dot. By using a relaxed version of the problem, I am able to "draw" on a black background by making the motion persistent. The setup involves a smooth non-glossy black wall approximately 2m away from the quickcam.

Motion tracking is also able to give a rough figure of how intense the dot is. The red laser, being less intense than its green counterpart, gives a much smaller dot. Also, gaps appear when trying to draw a line quickly using red laser. This did not occur with the green laser. Noise can be observed around the trail left by the green laser but the noise is not present the red one.



0117

Added removeNoise, which works by downsampling the image followed by an upsampling, using Gaussian pyramid decomposition. The noise caused by green laser is gone for good!

I proceeded to get the setup to work with a projector screen after having success working with a relaxed environment. I noticed that "Whiteouts" always occur at the beginning (and when I clear the image buffer by pressing 'c'), because the image buffer is initially empty, and the next and also first incoming frame is not, so the resulting difference between the two is picked up as motion.

Note: clock() behaves differently on light and my laptop.



0118

Had our weekly update today. Next week, mornings will be spent on design pattern as the project will be shifting to OOP design. I will have to get the draft UML diagrams ready. We plan to buy parts to make the IR pen, and a 4.5m long firewire cable. Parts of IR pen include: 40-70 Ohm resistor for usb powered, usb power adapter, momentary switch, 1.6v infrared LED. I might want to check out light blocking filters too. (I am looking for a 532nm pass-band filter for the green YAG-medium laser, or 650 longpass filter for the common red Krypton-medium laser.
Ref: http://www.seattlerobotics.org/encoder/200110/vision.htm)

The team tried with various setups of the iSight. Having the camera at the behind the screen is not feasible as there is more interference there. [Edit: see 0211, camera @ back is better] So we ended up placing the iSight in front of projector screen to test how well the iSight is able to see the laser dot. We cheated a little by overlaying terminal transparency on the desktop to improve detection of dot with iSight.