Friday, January 21, 2011

MSER, MSCR detectors

Basic idea - could be overly simplified
A method to detect blobs (Distinguished Regions) by grouping nearby pixels of similar intensity (gray) or color. They try to Maximize the Stable Regions. The region is stable when the area increase very slowly across changes in (color)intensities.

MSER is like Watershed, with focus on finding stable connected-components with the largest possible size. It does so by applying a threshold value from 0 to maximum, one step at a time. Similar to flooding the basins in Watershed-speak. Smaller regions would merge to become larger regions if area remains 'stable'. The region becomes a candidate when the area growth rate reaches a local stationary point.
Rate-of-change = Delta-area/Delta-threshold. 
That's likely where the edge (blob boundary) lies.

MSCR is an color extension of MSER.

MSCR is similar to MSER. It detects blobs by aggregating clusters of pixels. Clusters are formed  by grouping neighborhood pixels having similar color. Comparing to MSER, this 'similarity' is modeled by Chi-Squared Distribution. The 'expected difference in color' of neighboring pixels varies with intensity. That means, the 'distance's are non-uniform across evolutions (iterations). This varying distance at each evolution (iteration) maintains a constant area growth if the intensity increase linearly. Again, the goal is the find the stationary points of area-increase-rate.

Invariance
  • Achieve by using Hu invariant Moments as descriptor?

Code
  • Contributed by Liu Liu - support both single-channel and multi-channel image.
  • OpenCV implements "Linear Time MSER" for grayscale input image and MSCR for 3-channel images. According the abstract of the paper "Linear Time Maximum Stable Extrema Regions", Nister et al proposed a more efficient method in computing the DR than the union-find method.
  • See MSER section of VLFeat website (resources) for description of the parameters (delta, minArea, maxArea, maxVariation and minDiversity).
  • Parameters for MSCR (color)
    • Minimum 'color-difference' (minMargin) for a region - to be adjusted according to degree of edge-smoothing (edgeBlurSize).
    • The blobs are initially returned as contours. Approximated to ellipses. Only the major orientation and center point of the ellipse is saved to KeyPoint. Information about the shape is lost.

Sample 1 (detector_simple)

Comparing the color versus grayscale of the same picture (ABC Test-Pattern.jpg), using default parameters.
  • Total KeyPoints Detected on Gray is fewer than Color ( 344 versus 373 ).
  • Both taken less than 1 second.
  • Gray image has a more complete coverage of Key points on gray tiles pattern.
  • Color image has a more complete coverage of Key points on horizontal strip of black tiles.
    • MSCR is able to identify all 6 color blocks (Yellow, ..., Blue) while MSER sees leftmost 4 as a single one.
    • MSCR is able to identify 5 out of 6 gray scale boxes (above UniSA TV) while MSER identify only one.
  • MSER (falsely?) identify regions at the busy (high-frequency) side of the alternating black-and-white vertical strips.
Performance on large image (Obama Official Portrait), default parameters:
Color - 3312 Keypoints in 12 secs
Gray - 436 Keypoints in 2 secs

Parameters

Most of the parameters are being used in checking whether the current regions are 'stable'.

With Gray Image of "ABC Test-Pattern.jpg":
  • Increase delta to 50 - no more blobs on high-frequency region of B&W vertical strips.
  • Decrease the maxVariations to 0.005 - no more blobs on the high-frequency region of B&W vertical strips. Gray Tiles remains detected. They have clear cut high-contrast and narrow boundaries
  • More overlapping blobs appear after decreasing minDiversity to 0.05.
  • Increase minDiversity to 1 or above - zero blobs detected.
  • Unable to detect the all the separate blocks forming a horizontal gradient across the circle by changing parameters. It could be related to the surrounding textures/geometries because the same program is able to detect those blocks if they are cut out as a standalone image.

With original color image of "ABC Test-Pattern.jpg":
  • maxEvolution divided the Chi table. Fewer evolutions results in larger steps in 'distances' to cover the whole color intensity range, and vice versa.
  • More evolutions increases the number of detected blobs, as seen on more complete coverage of the gray tiles. Unfortunately, this also brings about more overlapping key-points.
  • minDiversity also works for color image.
  • Increase edgeBlurSize naturally remove the blobs from high-frequency area; Disable edgeBlurSize (0) also detect more some gray tiles as blobs.
  • minArea and maxArea also applies to color input
  • Setting minArea to 0 could cause run-time assertion, presumably it is due to the minimum pixels required in Contour functions.
Sample 2 (mser_sample.cpp) [ Added Jan-22 ]
  • Using C API - able to draw the Contours for more complete evaluation of results.
  • Convert input image to Y-Cb-Cr color-space for MSER (in fact MSCR) by default.
  • With puzzles.png, the MCSR detects 100 more contours (164 versus 60) but quite a few are probably owing to the uneven lighting on the big board. It is not trivial to get rid of without visible side-effects, like sacrificing the long board edges. Best parameter I tried is to increase the blurring to aperture size of 11.
  • The MSER is sensitive to shadows posted from the solids. 
Reading
  • RobustWide Baseline Stereo from Maximally Stable Extremal Regions, by Matas et al.
  • Maximally Stable Colour Regions for Recognition and Matching, by  Forseen
  • Linear Time Maximally Stable Extremal Regions, by Nister, Stewenius
Implementations

No comments:

Post a Comment