大二上学习数据结构lec

1、Quad TreesRegion data vs. point data.Roads and rivers in a country/state.Which rivers flow through Florida?Which roads cross a river?Network firewalls.(source prefix, destination prefix, action)(01*, 110*, drop packet)sourcedest8152427Quad TreesBinary images.Image region is divided into cells called

2、 pixels.Each pixel is either black (0, background) or white (1).Example Binary Image1111111111111Remaining entries are 0.Image OperationsRotation.Rotate 90 degrees clockwise.ScalingExpansion.Each pixel is replaced by a 2k x 2k window of pixels of the same intensity.Shrinking.Each 2k x 2k window is r

3、eplaced by a pixel whose intensity is some function of that of the window pixel intensities.Shrinking Examplek = 1.= 2 white pixels in 21 x 21 window = white pixel.Union & IntersectionImage1 = roads.Image2 = rivers.Union(Image1, Image2) = roads and rivers.Intersection(Image1,Image2) = places where a

4、 road crosses a river = bridge or tunnel.Image Representationn x n matrix.Theta(n2) space.Theta(n2) time for rotation, scaling, union, intersection, and so on.Quad tree.O(n2) space.O(n2) time for rotation, scaling, union, intersection, and so on.For some images, the space and time could be as little

5、 as O(1) (e.g., all white or all black images).Quad TreeDegree 4 tree (each node has up to 4 children).Each node represents a portion of the image.Root node represents entire 2k x 2k image.The children of a node that represents a 2q x 2q region represent its 4 2q-1 x 2q-1 subregions. Quad TreeEach n

6、ode has one of the colors white, black, gray.White (black) = all pixels in nodes region are white (black).Gray = at least one black and at least one white.White and black nodes have no children.Gray nodes have 4 children each.Quad Tree ExampleNWSWNWSWSENENESEQuad Tree ExampleNWSWSENEQuad Tree Exampl

7、eNWSWSENEQuad Tree ExampleNWSWSENEOct TreeExtension of quad tree to the representation of 3-d images.Degree 8 tree (each node has up to 8 children).The children of a node that represents a 2q x 2q x 2q region represent its 8 2q-1 x 2q-1 x 2q-1 subregions. From Matrix To Quad Tree2k x 2k binary matri

8、x.If k = 0, return a single-node quad tree. Root is white if pixel is 1.Root is black if pixel is 0.Divide And ConquerFrom Matrix To Quad TreeIf k 0, recursively construct quad trees for the four quadrants. NWSWSENEFrom Matrix To Quad TreeIf the 4 quad tree roots are all black (white), return a sing

9、le node quad tree with a black (white) root. Otherwise, return a quad tree with a gray root whose subtrees are the quadrant quad trees.NWSWSENEComplexityLet t(k) be the time to construct the quad tree of a 2k x 2k binary image (matrix).t(0) = c, where c is some constant.t(k) = 4t(k1) + d, where d is

10、 some constant and k 1.t(k) = O(4k) = O(#pixels in matrix).From Quad Tree To MatrixRun divide-and-conquer algorithm for matrix to quad tree transformation backwards.t(k) = O(4k) = O(#pixels in matrix).Clockwise Rotation By 90 DegreesNENWNWSWClockwise Rotation By 90 DegreesNENWNWSWRecursive Algorithm

11、If root is a leaf, return.Rotate the children of the root.(NW, NE, SE, SW) (SW, NW, NE, SE)Recursively perform the rotation in the subtrees of the root.Complexity is O(size of quad tree).Quad tree size = # nodes.Quad tree size is usually substantially less than matrix size.Other RotationsClockwise r

12、otations by 180 and 270 degrees are similar.Counterclockwise rotations by 90, 180, and 270 degrees are similar.Rotation by 360 degrees is null.Shrinkingk = 1.= 2 white pixels in 21 x 21 window = white pixel.NWSWSENEShrinkingk = 1.= 2 white pixels in 21 x 21 window = white pixel.NWSWSENEShrinkingk =

13、1.= 2 white pixels in 21 x 21 window = white pixel.NWSWSENEShrinkingk = 1.= 2 white pixels in 21 x 21 window = white pixel.NWSWSENEAlgorithm To Shrink (k = 1)Root represents a 1 x 1 region = return.Root represents a 2 x 2 region.Color the root white if it has = 2 white children.Color the root black

14、if it has 1, region.Shrink subtrees (if any) of root.Recolor root if all subtrees now have same color.Complexity is O(size of quad tree).UnionRules.Do a pairwise union of corresponding pixels in the two images.Union is white iff at least one pixel of the pair is white.+=Recursive Union(A,B)root(A) (

15、root(B) is white = return A (B).root(A) (root(B) is black = return B (A).Both have a gray root.Pairwise union the subtrees of A and B.If all four of the returned subtrees have a white root, return a single node tree with a white root.Otherwise return a tree with a gray root and the four returned sub

16、trees as its subtrees.Complexity is O(|A| + |B|).ABIntersectionRules.Do a pairwise intersection of corresponding pixels in the two images.Intersection is white iff both pixels of the pair are white.+=Recursive Intersection(A,B)root(A) (root(B) is black = return A (B).root(A) (root(B) is white = return B (A).Both have a gray root.Pairwi