1、Stockman CSE803 Fall 2008,1,Binary Image Proc: week 2,Getting a binary image Connected components extraction Morphological filtering Extracting numerical features from regions,Stockman CSE803 Fall 2008,2,Quick look at thresholding,Separate objects from background. 2 class or many class problem? How
2、to do it? Discuss methods later.,Stockman CSE803 Fall 2008,3,Cherry image shows 3 regions,Background is black Healthy cherry is bright Bruise is medium dark Histogram shows two cherry regions (black background has been removed),Use this gray value to separate,Stockman CSE803 Fall 2008,4,Choosing a t
3、hreshold,Common to find the deepest valley between two modes of bimodal histogram Or, can level-slice using the intensities values a and b that bracket the mode of the desired objects Can fit two or more Gaussian curves to the histogram Can do optimization on above (Ohta et al),Stockman CSE803 Fall
4、2008,5,Connected components,Assume thresholding obtained binary image Aggregate pixels of each object 2 different program controls Different uses of data structures Related to paint/search algs Compute features from each object region,Stockman CSE803 Fall 2008,6,Notes on Binary Image Proc,Connected
5、Components Algorithms Separate objects from background Aggregate pixels for each object Compute features for each object Different ways of program control Different uses of data structures Related to paint/search algs,Stockman CSE803 Fall 2008,7,Example red blood cell image,Many blood cells are sepa
6、rate objects Many touch bad! Salt and pepper noise from thresholding How useable is this data?,Stockman CSE803 Fall 2008,8,Cleaning up thresholding results,Can delete object pixels on boundary to better separate parts. Can fill small holes Can delete tiny objects (last 2 are “salt-and-pepper” noise)
7、,Stockman CSE803 Fall 2008,9,Removing salt-and-pepper,Change pixels all of whose neighbors are different (coercion!): see hole filled at right Delete objects that are tiny relative to targets: see some islands removed at right,Stockman CSE803 Fall 2008,10,Simple morphological cleanup,Can be done jus
8、t after thresholding- remove salt and pepper Can be done after connected components are extracted- discard regions that are too small or too large to be the target,Stockman CSE803 Fall 2008,11,CC analysis of red blood cells,63 separate objects detected Single cells have area about 50 Noise spots Gob
9、s of cells,Stockman CSE803 Fall 2008,12,More control of imaging,More uniform objects More uniform background Thresholding works Objects actually separated,Stockman CSE803 Fall 2008,13,Results of “pacmen” analysis,15 objects detected Location known Area known 3 distinct clusters of 5 values of area;
10、85, 145, 293,Stockman CSE803 Fall 2008,14,Results of “coloring” objects,Each object is a connected set of pixels Object label is “color” How is this done?,Stockman CSE803 Fall 2008,15,Extracting components: Alg A,Collect connected foreground pixels into separate objects label pixels with same color
11、A) collect by “random access” of pixels using “paint” or “fill” algorithm,Stockman CSE803 Fall 2008,16,paint/fill algorithm,Obj region must be bounded by background Start at any pixel r,c inside obj Recursively color neighbors,Stockman CSE803 Fall 2008,17,Events of paint/fill algorithm,PP denotes “p
12、rocessing point” If PP outside image, return to prior PP If PP already labeled, return to prior PP If PP is backgr. pixel, return to prior PP If PP is unlabeled obj pixel, then1) label PP with current color code2) recursively label neighbors N1, , N8(or N1, , N4),Stockman CSE803 Fall 2008,18,Recursi
13、ve Paint/Fill Alg: 1 region,Color closed boundary with L Choose pixel r,c inside boundary Call FILL,FILL ( I, r, c, L)If r,c is out, returnIf Ir,c = L, returnIr,c L / color itFor all neighbors rn,cnFILL(I, rn, cn, L),Stockman CSE803 Fall 2008,19,Connected components using recursive Paint/Fill,Raster
14、 scan until object pixel found Assign new color for new object Search through all connected neighbors until the entire object is labeled Return to the raster scan to search for another object pixel,Stockman CSE803 Fall 2008,20,Extracting 5 objects,Stockman CSE803 Fall 2008,21,Outside material to cov
15、er,Look at C+ functions for raster scanning and pixel “propagation” Study related fill algorithm Discuss how the recursion works Prove that all pixels connected to the start pixel must be colored the same,Stockman CSE803 Fall 2008,22,Alg B: raster scan control,Visit each image pixel once, going by r
16、ow and then column. Propagate color to neighbors below and to the right. Keep track of merging colors.,Stockman CSE803 Fall 2008,23,Raster scanning control,Stockman CSE803 Fall 2008,24,Events controlled by neighbors,If all Ni background, then PP gets new color code If all Ni same color L, then PP ge
17、ts L If Ni != Nj, then take smallest code and “make” all same See Ch 3.4 of S&S,Stockman CSE803 Fall 2008,25,Merging connecting regions,Detect and record merges while raster scanning. Use equivalence table to recode,Stockman CSE803 Fall 2008,26,alg A versus alg B,Visits pixels more than once Needs f
18、ull image Recursion or stacking slower than B No need to recolor Can compute features on the fly Can quit if search object found (tracking?),“visits” each pixel once Needs only 2 rows of image at a time Need to merge colors and region features when regions merge Typically faster Not suited for heuri
19、stic start pixel,Stockman CSE803 Fall 2008,27,Outside material,More examples of raster scanning Union-find algorithm and parent table Computing features from labeled object region More on recursion and C+,Stockman CSE803 Fall 2008,28,Computing features of regions,Can postprocess results of CC alg. O
20、r, can compute as pixels are aggregated,Stockman CSE803 Fall 2008,29,Area and centroid,Stockman CSE803 Fall 2008,30,Second moments,These are invariant to object location in the image.,Stockman CSE803 Fall 2008,31,Contrast second moments,For the letter I Versus the letter O Versus the underline _,r,c
21、,Stockman CSE803 Fall 2008,32,Perimeter pixels and length,Stockman CSE803 Fall 2008,33,Circularity or elongation,Stockman CSE803 Fall 2008,34,Circularity as variance of “radius”,Stockman CSE803 Fall 2008,35,Radial mass transform,for each radius r, accumulate the mass at distance r from the centroid
22、(rotation and translation invariant)can iterate over bounding box and for each pixel, compute a rounded r and increment histogram of mass Hr,Stockman CSE803 Fall 2008,36,Interest point detection,Centroids of regions can be interesting points for analysis and matching.What do we do if regions are dif
23、ficult to extract?We might transform an image neighborhood into a feature vector, and then classify as “interesting” vs “not”.,Stockman CSE803 Fall 2008,37,Slice of spine MRI and interesting points selected by RMT & SVM,Stockman CSE803 Fall 2008,38,3D microvolumes from Argonne high energy sensor: 1
24、micron voxels,Ram CAT slice of a bee stinger (left) versus segmented slice (right). Each voxel is about 2 microns per side.,Stockman CSE803 Fall 2008,39,Scanning technique used,CCD camera material sample X-raysscintillator,Pin head,rotate,X-rays partly absorbed by sample; excite scintillator produci
25、ng image in the camera; rotate sample a few degrees and produce another image; 3D reconstruction using CT,Stockman CSE803 Fall 2008,40,Different view of stinger,Rendered using ray tracing and pseudo coloring based on the material density clusters that were used to separate object from background. (D
26、ata scanned at Argonne National Labs),Stockman CSE803 Fall 2008,41,Section of interesting points from RMT&SVM,Stockman CSE803 Fall 2008,42,Segmentation of Scutigera,Stockman CSE803 Fall 2008,43,Scutergera: a tiny crustacean,organism is smaller than 1 mmscanned by volume segmented and meshed by Paul
27、Albeeroughly ten million trianglesto represent the surfaceanaglyph created for 3D visualization (view with glasses),Stockman CSE803 Fall 2008,44,Axis of least inertia,gives object oriented coordinate systempasses through centroidaxis of most inertia is perpendicular to itconcept extends to 3D and nD,Stockman CSE803 Fall 2008,45,Derive the formula for best axis,use least squares to derive the tangent angle q of the axis of least inertiaexpress tan 2q in terms of the 3 second momentsinterpret the formula for a circle of pixels and a straight line of pixels,
