Lecture Data Structures: Lesson 37 provide students with knowledge about timing with optimization; image segmentation; inclusion criteria for pixels: use pixel intensity, threshold of intensity, threshold for difference in intensity of neighbors, texture; . | Timing with Optimization Theorem A sequence of m union and find operations n of which are find operations can be performed on a disjoint-set forest with union by rank weight or height and path compression in worst case time proportional to m n n is the inverse Ackermann s function which grows extremely slowly. For all practical puposes n 4. Union-find is essentially proportional to m for a sequence of m operations linear in m. Lecture Data Structures Dr. Sohail Aslam Image Segmentation Inclusion criteria for pixels use pixel intensity threshold of intensity threshold for difference in intensity of neighbors texture ie. a pattern of pixel intensities Image Segmentation 0 1 2 3 4 0 0 0 0 4 4 1 2 0 4 4 0 2 4 2 2 4 4 3 4 4 0 4 4 4 0 2 2 4 0 Image Segmentation 0 1 2 3 4 0 1 2 3 4 0 0 0 0 4 4 0 0 0 0 1 1 1 2 0 4 4 0 1 0 0 1 1 0 2 4 2 2 4 4 2 1 0 0 1 1 3 4 4 0 4 4 3 1 1 0 1 1 4 0 2 2 4 0 4 0 0 0 1 0 Threshold 4 Image Segmentation 0 1 2 3 4 0 1 2 3 4 0 0 0 0 4 4 0 0 0 0 1 1 1 2 0 4 4 0 1 1 0 1 1 0 2 4 2 2 4 4 2 1 1 1 1 1 3 4 4 0 4 4 3 1 1 0 1 1 4 0 2 2 4 0 4 0 1 1 1 0 Threshold 2 Maze Generation Maze Generation A random maze generator can use union- find. Consider a 5x5 maze 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Maze Generator Initially 25 cells each isolated by walls from the others. This corresponds to an equivalence relation - two cells are equivalent if they can be reached from each other walls been removed so there is a path from one to the other . Maze Generator To start choose an entrance and an exit. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Maze Generator Randomly remove walls until the entrance and exit cells are in the same set. Removing a wall is the same as doing a union operation. Do not remove a randomly chosen wall if the cells it separates are already in the same set. MakeMaze MakeMaze int size entrance 0 exit size-1 while find entrance find exit cell1 randomly chosen cell cell2 randomly chosen .
