0225
The demo program "moveresize" is able to work with laser. Thresholding of image affects the detection of laser blobs. Lower thresholds makes the laser dot highly visible but introduces more false positives. With higher thresholds, the laser "drops" once in awhile, so I've added loss tolerance for two frames after my program doesnt pick up the laser.
Kevin simplified Lightdraw into three particular areas the team has to look into.
1. Full screen program, probably with transparency overlay. With graffiti, and gestures.
2. Window interaction.
3. Contextual interaction.
0226
Quickly put together an extremely simply gesture recognition for moveresize. Though it is simple, it is extremely reliable as it does corner detection using Douglas-Peucker algorithm with high rate of success.
Increased the effective area of the binarized pointer size to allow a margin of human error when user wants to initiate a pause (It is difficult to keep your hands still and focus the laser on a point).
0227
Went for this Apple talk in the morning that was about role of Apple computing in Science. We were introduced to specialised software available by Apple that is free, such as "stitching" your displays together or desktop sharing.
0228
Read up on Apple window manager programming. I think X11 windowing system would be a good choice as my SuSe development platform uses it natively and the Mac Pro has X11 as well.
I would want to achieve transparent window overlays and control event signals using X11.
0229
Taken OpenCV motion template apart in order to assess how well it can detect a (anti)clockwise motion detection. Even after removing the direction weights on motion history two or more frames ago, I am not able to get a reliable reading from the motion template. Humans cannot draw a perfect circle, and so the direction tangents do not change uniformly. This makes it difficult to determine when the circular motion starts or ends.
Tuesday, February 26, 2008
Friday, February 22, 2008
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!
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.
Thursday, February 21, 2008
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.
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.
Saturday, February 16, 2008
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.
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.
Tuesday, February 5, 2008
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
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!
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.
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!
Subscribe to:
Posts (Atom)