Page 11 -

ix

IV MID-LEVEL VISION 253

9 Segmentation by Clustering 255
9.1 Human Vision: Grouping and Gestalt . . . . . . . . . . . . . . . . . 256
9.2 Important Applications . . . . . . . . . . . . . . . . . . . . . . . . . 261
9.2.1 Background Subtraction . . . . . . . . . . . . . . . . . . . . . 261
9.2.2 Shot Boundary Detection . . . . . . . . . . . . . . . . . . . . 264
9.2.3 Interactive Segmentation .. .. ... .. ... .. .. ... . 265
9.2.4 Forming Image Regions . .. .. ... .. ... .. .. ... . 266
9.3 Image Segmentation by Clustering Pixels .. .. ... .. .. ... . 268
9.3.1 Basic Clustering Methods . . . . . . . . . . . . . . . . . . . . 269
9.3.2 The Watershed Algorithm . . . . . . . . . . . . . . . . . . . . 271
9.3.3 Segmentation Using K-means . . . .. .. ... .. .. ... . 272
9.3.4 Mean Shift: Finding Local Modes in Data . . . . . . . . . . . 273
9.3.5 Clustering and Segmentation with Mean Shift . . . . . . . . . 275
9.4 Segmentation, Clustering, and Graphs . . . . . . . . . . . . . . . . . 277
9.4.1 Terminology and Facts for Graphs .. .. ... .. .. ... . 277
9.4.2 Agglomerative Clustering with a Graph . . . . . . . . . . . . 279
9.4.3 Divisive Clustering with a Graph ... .. ... .. .. ... . 281
9.4.4 Normalized Cuts .. ... .. .. ... .. ... .. .. ... . 284
9.5 Image Segmentation in Practice . . . . . . . . . . . . . . . . . . . . . 285
9.5.1 Evaluating Segmenters .. .. .. ... .. ... .. .. ... . 286
9.6 Notes . . . . . . .. .. .. ... .. .. ... .. ... .. .. ... . 287
10 Grouping and Model Fitting 290
10.1 The Hough Transform . . . . .. .. .. ... .. ... .. .. ... . 290
10.1.1 Fitting Lines with the Hough Transform . ... .. .. ... . 290
10.1.2 Using the Hough Transform . . . . . . . . . . . . . . . . . . . 292
10.2 Fitting Lines and Planes .. ... .. .. ... .. ... .. .. ... . 293
10.2.1 Fitting a Single Line ... .. .. ... .. ... .. .. ... . 294
10.2.2 Fitting Planes . . . . .. .. .. ... .. ... .. .. ... . 295
10.2.3 Fitting Multiple Lines . . . . . . . .. .. ... .. .. ... . 296
10.3 Fitting Curved Structures . ... .. .. ... .. ... .. .. ... . 297
10.4 Robustness . . . .. .. .. ... .. .. ... .. ... .. .. ... . 299
10.4.1 M-Estimators .. .. ... .. .. ... .. ... .. .. ... . 300
10.4.2 RANSAC: Searching for Good Points . . . . . . . . . . . . . 302
10.5 Fitting Using Probabilistic Models . . . . . . . . . . . . . . . . . . . 306
10.5.1 Missing Data Problems . . . . . . . . . . . . . . . . . . . . . 307
10.5.2 Mixture Models and Hidden Variables . . ... .. .. ... . 309
10.5.3 The EM Algorithm for Mixture Models . . . . . . . . . . . . 310
10.5.4 Difficulties with the EM Algorithm . . . . . . . . . . . . . . . 312