Delunay

Data Structures

• CvSubDiv2Edge is a bit tricky.
• CvSubDiv2DEdge: represents a index pair:
      [31:2, 00b]: pointer address to a CvQuadEdge2D structure.
      [1:0] : One of the 4 edges (delunay + reversed,  veronoi + reversed).
• CvQuadEdge2D:  A CvSet 4 pairs of [ edge, associated-vertex ]; see cvSubdiv2DMakeEdge()
• CvSubDiv2D: subdivision header and a graph of CvQuadEdge2Ds

Misc. Notes

• Second argument to cvSubdiv2DRotateEdge() is relative, see how it is used to find the voronoi point in draw_subdiv_facet().
• Some properties from OpenCV Book:
  Each point on the convex hull is connected to at least 2 of the fictitious triangle.

Watershed, Inpainting and Mean-Shift Segmentation

Watershed

• watershed() implements a marker-based method based on "Color Image Segmentation" by F. Meyer
• Some basic idea of Watershed itself (grayscale, marker-based):
  http://cmm.ensmp.fr/~beucher/wtshed.html
  http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/KIM1/Seminars/Watershed/index.htm
  http://en.wikipedia.org/wiki/Watershed_%28image_processing%29#Meyer.27s_flooding_algorithm
• Flood (expand) the catchment-basin from each marker. Watersheds are boundaries at which flooding ends (local maxima). It will never spill over to another basin.
• Implies putting markers at local minima (significant ones) for grayscale images.
• Without markers: solve over-segmentation

Watershed Sample

• The clever part (choosing the markers) is done by human.
• Put markers at different color regions instead-of / in-additional-to local minima of intensity.
• Single marker is meaningless.

Watershed Code

• c_diff() macro hints that the color pixel comparison is based on max of the component differences.
• 4-connected neighbor flooding

Other Techniques: Mixing segment results with original(color) by adding them together with weights of 0.5 each.


Inpainting

• Wikipedia: http://en.wikipedia.org/wiki/Inpainting
• Usage:
• Restore corrupted data or intentionally blur parts of the image (like faces on Google Street View?)
• Remove caption from video/image.

Inpainting Code

• Uses Fast Marching Method (FMM) for both Telea and NS options to inpaint points going inwards from boundary of the omega region.
• Telea method inpaints by calculating the weighted sum of neighboring pixels with regard to direction, distance and level.

Inpainting Sample

• (Observation) Telea introduces less artifacts when the omega region is big comparing to NS, using fruits.jpg as example.

Mean-shift Segmentation
Mean-shift Segmentation Sample

• Spatial Radius slows down processing the most.
• Increasing the Pyramid Level helps remove the white speckles (light reflections) off the orange (fruits.jpg). At the same time blurry strip appear at bottom and right edge. The strip thickness increases with pyramid levels.
• Increasing color radius also helps remove the white speckles, without introducing the edge strips, at the expense of the boundaries between segments (fruits). Those are now more blurry.
• Too big a spatial radius also distorts the segment boundaries.
• Output looks similar to output from a median filter

Background Subtraction and Models

Looked at three background models:

• Codebook
• Learn and keep ranges of values for each pixel. They will be treated as background pixels. Clear stale pixels to remove moving foregrounds from the learning period.
• Foreground objects are detected by subtracting pixels from the ranges (with some allowances).
• Mixture of Gaussians
• The intensity of each pixel is modeled by a few Gaussians. Background values are the most probable ones (highly weighted).
• Model gets continuously updated (adaptive). No separate learning stage.
• Foreground objects are detected by subtracting pixels from the most probable Gaussian.
• Color Co-occurrence:
• Learn and keep a table of color co-occurrences at each pixel location. 
• Input pixel is classified as foreground, background or moving background.
• A reference background image is maintained to compute 'background difference' after binary thresholding.
• Temporal difference from frame to frame will be updated to the co-occurrence tables.
• Foreground/(Static, Moving) Background objects are classified using Bayes decision rule.

Running the Samples with street side video:

• bgfg_codebook (CodeBook method)
• Least CPU demanding.
• Connected objects does not resemble original shape.
• Good result in default parameters.
• segment_objects (Mixture of Gaussians and connected-object refinement)
• More CPU demanding ( 50% CPU on a dual core)
• Lower background-ratio parameter gives a more solid shape of a moving car.
• alpha (learning-rate parameter) is adjusted (decreasing) as time progressed.
• NoiseSigma parameter seems to be used to set the max. variance of each Gaussian component.
• bgfg_segm ( Co-occurrence and Mixture of Gaussians)
• cvCreateGaussianBGModel() is basically using BackgroundSubtractorMOG as model. Detected object refinement left out. segment_objects did processing at the application level.
• FGDModel is the color co-occurrence model.
• Needs double the memory size of MoG. CPU intensive.
• changeDetection() actually finds the best binary threshold on each color component by choosing one that would give the maximum variance. That's probably based on the reasoning that noise pixel color has small variance. Paul Rosin uses the term RelativeVariance in Thresholding for Change Detection . Here the code compare Standard Deviation. Wonder if simply comparing variance is enough, saving the final 'square root' operation.

Tested with more videos

• Golden Gate Bridge: FGDModel shows no ship moving at all. The slowness is making the ship part of the moving background.
• Sea side beach: FGDModel is able to absorb the cloud and wave (slow) movements and into background. MoG can't.
• Single Moving Tree: FGDModel unable to put the center portion of the moving branches  into background. 
• Relaxing Aquarium: 
• Default parameters of FGDModel takes a long time to adapt to the aquarium after fading-in 
• Slow moving fishes quickly becomes the background of FGDModel.
• Increase 'alpha1' parameter of FGDModel makes the slow fishes appear as foreground. But at the same time the oscillating lights on coral turns up as foreground also.
• Codebook seems to be able isolate the big fishes as foreground, eliminating the fluctuating lights on coral. At the same time the smaller fishes are filtered out. Making it looks like the isolation is due to keeping out small foreground objects all together.

Other readings along the way:

• This article from Intel gives an overview of video surveillance system: fg/bg detection and blob tracking.
• Learning patterns of activity using real-time tracking (Stauffer, Grimson)
• Foreground Object Detection in Changing Background Based on Color Co-Occurrences Statistics ( Li, Huang, Qi )
• Thresholding for Change Detection (Rosin)

Other others:

• There is a flag to indicate use of Least Median of Squares (LMedS) methods in findHomography(). Wonder if that could be refactored for thresholding use. 

ConvexityDefects

Added a C++ wrapper for cvConvexityDefects() similar to how ConvexHull() does to cvConvexHull2().

Observations
The defects results makes sense when all the points are of the same contour. Otherwise, the depth_point would be found located at far end of the of hull, ignoring the closer ones.
Come to this conclusion by comparing 3 cases:

• Random points (default example)
• Picture of actual human palm in grayscale. Preprocessed by GaussianBlur and Canny Threshold, resulting in 61 contours. Simplified each contour with approxPolyDP(). Feed all points to ConvexHull() and ConvexityDefects()
• Hand drawn palm in one continuous line, resulting in a single contour - ConvexityDefects() able to discover all the defects area in good accuracy.

Contours samples

Connected Component

• Use of binary thresholding: Make dark objects the foreground (white) when threshold is less than 128 and vice versa.

Fit Ellipse (fitellipse)

• The ellipse drawn by the second of the two consecutive calls to ellipse() mostly overlaps the first one.

Convex Hull - where is ConvexityDefects()?

• ConvexHull() and isContourConvex() are now C++ wrapper function for cvConvexHull2() and cvCheckContourConvexity()respectively.
• There is no C++ wrapper for cvConvexityDefects(). The function requires the hull points be indices to the contour points. This implicitly relates all the hull points to the corresponding contour points. Is this how 'defect' searching works? 
• In some cases the [sklansky82] algorithm have trouble finding convex hull from a polygon, how does that apply to general set of points?
  http://cgm.cs.mcgill.ca/~athens/cs601/

findSquares

• Basic Idea: 
  Approximate the contours with polygon for the straight edges. Criteria of being a 'square': polygon edge count is 4,  area at least 1000 pixels, maximum angle between edges is close to 90.
• Techniques
• Use Law-of-Cosine to determine angle between two edges, with Cartesian origin at the edge joint.
• The closer the angle is to 90 degree, the nearer the cosine value to 0.
• Parameterize epsilon value to approxPolyDP() as a fraction of the contour length.
• Reduce noise of source image with a sequence of downsampling-upsampling with Pyramid function.
• Choose 0 as low-threshold for Canny to combine edges.
• 'Dilate' the post-Canny image to remove 'holes' between edges.
• Discover as many squares in a picture by iterating all color planes, intensity threshold values and

Randomized Hough Transform

Picked this up while looking for fitellipse() from OpenCV discussion group:

http://tech.groups.yahoo.com/group/OpenCV/message/58635

In my current project I use cvFitEllipse to find ellipses. First, I use cvCanny to detect edges. From this egdePixels I randomly draw 6 Pixels and fit an ellipse. Afterwards, I confirm this ellipse by counting the number of edgePixels lying under this ellipse.
The main problem is to choose the right set of edgePixels to draw from, since you need to draw six Points on the Ellipse to have a Chance to find the right ellipse.
This is approach is calles "Randomized Hough Trafo" and works quite well.


This paper proposes this method?
http://www.cs.cuhk.hk/~lxu/papers/journal/xuoprl90.pdf


This article gives an overview of the advances of RHT.
http://www.cse.cuhk.edu.hk/~lxu/papers/RHT08a.pdf

cvAdaptiveskinDetector revisited

Exploring the purpose of histogramHueMotion in cvAdaptiveSkinDetector, noticing that the effect even with a weight value of 0.05 being accounted when being mergeWith() the skinHueHistogram. Tested with a video in 'Office' settings. The outputHueMask is able to cover the human faces more completely, and inevitably covers more areas of similar color tone, like the wall. Perhaps it's the surface of the human faces giving a range of hues that spreads  the adaptive-ranges in findCurveThresholds(), and that in turns pick up more pixels as skin.