Transcript


00:03
okay right this is going to be our last
00:07
lecture the the date and time for the
00:12
final exam is posted on the website you
00:14
should check it from there and also the
00:17
syllabus for the final is available on
00:19
the website as was the case for the
00:23
other two exams there are sample exams
00:25
there which are exams that have been
00:27
used in the past and once again it's a
00:31
good idea to use those as a test of how
00:35
well prepared you are for the for the
00:37
final exam all right so far we seem to
00:40
be doing pretty well the average scores
00:42
are at least as good as they've been in
00:45
the past
00:47
okay all right today we're going to take
00:51
a look at the last data structure we
00:52
want to study in this course and this
00:54
data structure is called a quadtree
00:58
now as we'll see a quadtree is used to
01:03
represent region data versus point data
01:06
in our last lecture we saw several data
01:09
structures suitable to represent a
01:11
collection of points in multi
01:12
dimensional space and then answer
01:14
different types of queries on that
01:16
collection of points okay so today we
01:18
want to take a look at a quadtree and
01:20
just going to be used to represent
01:22
regions for example you may have a map
01:29
of a country or a state and the map may
01:35
show the location of rivers and roads
01:38
and other continuous items overlaid on a
01:42
partitioning of this country into States
01:44
okay and so we may want to represent
01:46
this map together with the country state
01:50
information Road information River
01:52
information and so on and then you may
01:56
want to answer queries like which rivers
01:58
flow through the state of Florida or
02:03
which roads across the river
02:07
okay so the data that we have is really
02:10
region data it's not a set of discrete
02:13
points you have a map and on the map you
02:16
have drawn roads and rivers and laid out
02:18
the boundaries of different states in
02:20
the country another application for a
02:27
quadtree
02:29
in the representation of region data
02:31
would be to the implementation of
02:35
firewalls for networks so for example a
02:41
firewall and we've seen
02:43
uses of firewalls and data structures
02:46
for these least a couple of times before
02:49
so you have two dimensional rules where
02:55
this particular rule uses the source
03:00
address so you provided a source prefix
03:03
which means you take a source address of
03:05
a packet and see if it's mapped or
03:07
matched by this particular source prefix
03:09
you take a destination address of a
03:11
packet see if it's matched by this
03:13
destination prefix if so this rule
03:15
applies and this action here tells you
03:17
what to do with that packet okay all
03:23
right so you have a collection of two
03:25
dimensional filters abstractly the first
03:30
dimension here is the sauce prefix the
03:32
second dimension is the destination
03:35
prefix so these two together define the
03:37
filter in this third component here
03:39
gives you the action that is to be
03:41
performed so for example the sauce
03:44
prefix may be 0 1 star all source
03:48
addresses that begin with 0 and 1
03:50
all destination addresses that begin
03:52
with 1 1 0
03:53
ok so packet is matching this and that
03:55
are matched by this rule and this tells
03:58
you what to do with that packet you want
04:00
to drop that packet alright so we may
04:05
represent this rule as a region in
04:07
two-dimensional space where the x
04:11
dimension gives you the source address
04:13
and the Y dimension gives you the
04:14
destination even though the addresses
04:17
are discrete we can still view this rule
04:20
as defining
04:22
a rectangle in continuous
04:24
two-dimensional space this rectangle
04:28
here is arrived at making the assumption
04:31
that the addresses that we're dealing
04:33
with a 5-bit addresses so if you look at
04:37
a five bit expansion of this the
04:39
smallest address that would be match
04:41
will be 1 1 0 and then 2 zeros okay so
04:45
that way 24 and then the biggest address
04:47
would be 1 1 0 and then 2 ones and I
04:49
should give you the 27 all right so this
04:52
filter here represented by these two
04:55
prefixes can be represented as a
04:58
rectangular region in two-dimensional
05:00
space similarly you can have another
05:04
rule which is represented by this blue
05:06
rectangular region and then you could
05:11
have tiebreakers which say that in this
05:14
overlap region should you be using the
05:16
blue rule or the orange rule so I could
05:21
take two dimensional filters represent
05:23
them as rectangular regions and then use
05:25
my quadtree to actually represent this
05:28
2d region with these rectangles laid out
05:32
inside a larger 2d region all right so
05:36
another application for quadtrees or
05:38
generally for region data is firewalls
05:43
this example is just two dimensional
05:45
firewalls and generally you could have
05:47
higher dimensions most commonly you may
05:50
go up to about 5 dimensions so then
05:52
you'd be looking at 5 dimensional
05:54
objects
06:01
or another application for quadtrees
06:04
representation of binary images so you
06:09
have black-and-white images the image is
06:16
discretized so you take a two
06:19
dimensional image break it up into cells
06:20
called pixels each pixel is represented
06:23
by a bit either 0 or 1 where a 0 pixel
06:30
would represent 0 would represent a
06:33
black pixel and 1 would represent a
06:35
white pixel right so for example here I
06:41
have a binary image it's a black and
06:45
white image
06:45
you either have black spaces or you have
06:48
white spaces to represent this image I
06:52
will discretize it by superimposing a
06:55
grid okay and then each cell here I will
07:00
call a pixel and then I would have some
07:05
rule to actually go from the colors
07:08
inside this pixel to a zero and one in
07:10
this case it's pretty neat and that the
07:14
whole if you look at any one pixel its
07:17
entirety is either black or it's white
07:19
but in other cases when you discretize
07:23
you may have a little bit of black
07:25
inside here too so you may have some
07:27
thresholding which says that if 50% of
07:30
the pixel is white you're going to call
07:31
it a white pixel all right so I
07:34
discretize it and then I map it into a
07:37
matrix and there I guess these are all
07:40
my ones in the remaining entries which
07:44
are not shown they're zeros so I can
07:49
represent a binary image as a matrix of
07:52
zeros and ones and then I can use a
07:56
quadtree
07:57
to represent this binary image and
07:59
perform various image operations
08:01
efficiently on the quadtree
08:03
representation of the image alright so a
08:08
few applications of quadtrees first
08:10
quadtrees are used to represent region
08:12
data
08:13
the first application I mentioned was to
08:16
the representation of maps so maybe have
08:19
a map of a country with States to
08:21
marketed along with rivers and roads and
08:24
perhaps other entities shown and then he
08:26
want to represent that in in your memory
08:29
using some data structure another
08:33
application we saw was to the
08:35
representation of firewalls
08:37
in a network security application and
08:42
then third one is binary images and
08:44
certainly they're going there are many
08:46
other applications one can talk about
08:48
okay now the balance of the discussion
08:53
we're going to have I'm really going to
08:55
focus the discussion on application of
08:59
quadtrees to binary images so I'm going
09:03
to define some of the operations people
09:05
like to perform on binary binary images
09:07
then I'm going to define what a quadtree
09:09
is and then we'll see how using a
09:12
quadtree you can perform these
09:13
operations but the fundamental quad tree
09:18
structure could just as well be applied
09:20
to the other applications that I
09:22
mentioned now one of the things people
09:27
like to do with images rotation okay and
09:30
typically the rotations you'd like to do
09:34
maybe like 90 degree 180 or 270 so for
09:40
example if you have this image here and
09:43
you perform a 90 degree clockwise
09:45
rotation you'd like to end up with this
09:49
image okay so basically we're then
09:53
looking for a data structure which could
09:55
be used to store the image in a
09:57
discretized form and then if the user
09:59
says perform a 90 degree rotation you'd
10:02
like to obtain the data structure for
10:03
that version
10:07
similarly you talk about a 180 or 270
10:10
rotation or another common operation on
10:16
images is scaling and it's within
10:20
scaling you have expansion and you have
10:23
shrinking
10:24
in an expansion what you do is you look
10:28
at the pixels and so you look at Windows
10:34
in the pixel so 2 to the K by 2 to the K
10:37
well sir you look at each pixel okay if
10:40
a pixel is black you replace it by 2 to
10:44
the K by 2 to the K black pixels so if
10:48
you're doing a expansion say a 2 by 2
10:51
expansion
10:52
each pixel would get replaced by 4
10:54
pixels if you're doing a 4 by 4
10:58
expansion each pixel will get replaced
11:00
by 16 okay and since we're dealing with
11:04
binary images if you have a black pixel
11:07
it gets replaced by the appropriate
11:08
number of black pixels if you're white
11:10
one gets replaced by an appropriate
11:11
number of white pixels the shrinking is
11:17
the reverse where you take a 2 to the K
11:20
by 2 to the K window K is specified by
11:23
the user so if K is 1 you may take a 2
11:25
by 2 window and replace it by a single
11:28
pixel now to replace a 2 by 2 window of
11:34
pixels by a single pixel you need some
11:36
rule that tells you what do you do how
11:40
do you figure out the color of the
11:42
replacement pixel right so for example
11:51
when you're just doing a simple case
11:53
two-by-twos
11:53
ok and it's easy to see that within a 2
11:58
by 2 you got 4 pixels in there so your
12:03
rule may specify that if of the 4 pixels
12:06
in that 2 by 2 window at least 2 are
12:08
white then when you shrink you create a
12:11
white pixel otherwise you create a black
12:15
pixel okay so for example here if you
12:18
have this particular image okay put your
12:22
grid on it okay and I'm gonna do a 2 by
12:25
2 shrinking on this so I superimpose my
12:30
2x2 grid of windows ok and I'm going to
12:36
look in each of these red
12:38
- by 2 windows count the number of white
12:40
pixels if the number of white pixels is
12:43
at least 2 then I'm going to create a
12:45
white pixel in the corresponding shrunk
12:47
image otherwise they're going to create
12:49
a black pixel so this 2 by 2 would
12:57
shrink to this black pixel this 2 by 2
13:01
here would shrink to that black pixel
13:04
this 2 by 2 out here would shrink to
13:08
this white pixel ok and then this 2 by 2
13:12
even though it has one white pixel in it
13:15
it will shrink to a black because our
13:17
thresholding rule said you need at least
13:18
two black pixels ok so you get a black
13:21
one over there ok and that way you kind
13:23
of get all the others ok so when you do
13:26
a 2 by 2 shrinking each dimension of
13:28
your matrix shrinks to half for what it
13:31
was before or any questions about how a
13:36
shrinking works
13:46
but you may do unions and intersections
13:48
of images so for example if you have one
13:52
image which represents all the roads in
13:55
a locality you have another one that
13:58
gives all the rivers in that same
14:00
locality then if you do the Union you'll
14:04
get an image that represents both the
14:06
roads and the rivers if we do an
14:11
intersection you'll find out all the
14:14
places where a road crosses a river so
14:22
another common operation on images is to
14:26
Union two different images or to take
14:28
the intersection of two images
14:33
okay all right so those are some of the
14:35
operations people like to do on images
14:38
and these operations are supported well
14:42
by the use of a quad tree all right so
14:49
as far as our image goes in the natural
14:52
format it looks like a matrix okay
14:56
that's what we've kind of seen you you
14:57
take your picture you superimpose a grid
15:00
you get a matrix out of that and if you
15:05
represent that image in that natural
15:08
matrix form then the amount of space you
15:11
need in your computer you gonna need n
15:13
square bits it's a binary image you got
15:16
zeros at once you can need n square
15:18
space and if you want to perform any of
15:21
these operations
15:22
you also need n square time it'll take
15:26
you n square time just to find out where
15:29
there's a 1 in that image okay where all
15:32
the ones are
15:35
using a quadtree the runtime will change
15:40
from theta n square which means you
15:43
always spend n square time to perform
15:44
rotations or shrinking or expansion and
15:47
so on and you always take n square space
15:49
in the oldest take n square time it will
15:51
shrink to you take at most n square
15:54
space and you take at most n square time
15:57
in fact in the extreme case where you
16:02
maybe have a trivial image where all of
16:04
the pixels are black or all of them are
16:06
white you could perform these operations
16:07
in order one time so you get a range of
16:13
performance depending upon how complex
16:16
the images
16:25
all right let's take a look at what a
16:27
quadtree is and then we'll see how to
16:30
perform these operations or a quadtree
16:36
is a degree four tree where which are
16:39
basically mean that each node can have
16:41
up to four children each node represents
16:46
a sub region of the larger region so it
16:55
represents some portion of the image the
16:59
roots going to represent the entire
17:00
image and we assume that the image is a
17:02
the dimensions are power of two if you
17:09
look at any node in a quad tree and if
17:11
that node represents a window of size 2
17:16
to the Q by 2 to the Q then as children
17:18
it's going to have 4 children or up to 4
17:21
each of those will represent 1/4 of this
17:24
region also each node in a quad tree has
17:32
a color the allowable colors are white
17:38
black and gray a white node means that
17:44
all of the pixels in the region it
17:46
represents a white a black node would
17:49
imply that all of the pixels in its
17:50
region a black and a gray node would
17:55
imply that there's at least one black
17:57
and at least one white pixel okay so
18:00
you've got a mix of colors
18:07
the only nodes that can have children in
18:10
a quadtree are the gray nodes white
18:14
nodes do not have a children right so
18:18
basically the strategy is you start with
18:20
the route that represents the whole
18:21
image if the entire image is black then
18:25
you got a black node for the route
18:28
there's no advantage to be gained by
18:30
looking at the sub regions all of the
18:32
color information is encoded in the
18:33
route similarly if the whole image is
18:35
white you just have a white node route
18:38
which represents the entire image you
18:40
don't need to do a decomposition of the
18:42
image because you know everything about
18:43
it if you have some black and some white
18:47
pixels then the root node is great
18:50
and that doesn't capture the entire
18:52
image information so now you decompose
18:55
the image into four equal sized
18:57
quadrants and recursively apply this
19:00
scheme into the equal sized quadrants
19:04
okay so gray nodes have four children
19:07
okay let's take a look at an example
19:10
right so here's my image this is a 2 4 6
19:16
8 by 8 so the root of my quad tree is
19:19
going to represent this entire 8 by 8
19:21
image the color of the root will be
19:27
black if every pixel is black it'll be
19:31
white if every pixel is white otherwise
19:33
it's going to be great in this case I've
19:35
got a mix of black and white pixels so
19:37
the color of my root will be gray gray
19:43
nodes have children and they're going to
19:46
have exactly 4 children and each of
19:50
those 4 children will represent
19:52
one-fourth of the region represented by
19:55
the node ok so this is an 8 by 8 so I'm
19:59
going to have 4 4 by 4 regions made out
20:03
of this 8 by 8 by cutting it down the
20:07
middle along both the axes so what one
20:12
child was going to represent this region
20:14
called that the northwest region
20:18
another child is going to represent this
20:20
region the Northeast a third child will
20:23
represent this region and the fourth
20:25
child will represent that region all
20:30
right so since this is all black all 16
20:32
pixels are blank the first child
20:34
leftmost child here is going to be a
20:36
black node this node will not have any
20:40
children all of the information for this
20:43
region is captured within this node the
20:48
next child ok is the North East region
20:50
okay so we always start at North West
20:52
and go clockwise hitting these four
20:55
regions so the next child will represent
20:58
the North East region
20:59
you got a mix of black and white so
21:02
you're going to get a grey node then
21:06
we're going to hit this region mix of
21:08
black and whites you also get a gray
21:10
node then you hit this region all black
21:13
so you get a black node all right we're
21:22
going to apply this decomposition scheme
21:24
recursively on the gray nodes okay the
21:26
black nodes don't have children so I
21:27
going to take this node here it's going
21:30
to have four children and then this node
21:32
will have four children okay so looking
21:34
at this node first okay I take its
21:37
region which is this 8 by 8 divide it
21:40
into four equal parts by chopping it
21:43
down the middle ok so I get these four
21:45
regions this is the first or leftmost
21:49
child of that gray node that's going to
21:51
be the next child that's the next child
21:53
and that's the next one okay
21:57
so look at this region here that's a mix
22:02
of black and white alright so this is a
22:11
mix of black and white pixels so you get
22:13
a gray node to represent it that's all
22:15
blacks you get a black node this black
22:17
node won't have any children
22:19
this region is represented by a gray
22:22
node and that one's represented by a
22:24
white
22:29
moving on to this region you chop it up
22:32
into four equal parts down the middle
22:35
the first or leftmost child will
22:37
represent this region it's a black node
22:40
for this one you get a white node for
22:43
this one you get a gray node and for
22:46
this one you get a black node okay red
22:50
black and white nodes have no children
22:52
so we still need to develop the children
22:55
for this gray node that gray node and
22:57
that gray node okay great nodes and
22:59
never leaves of this COIs tree so this
23:03
one here represents this region out here
23:12
so that's going to be a white black
23:15
white white to get a white black white
23:19
white all right and now none of these
23:27
will have children right this node here
23:32
represents this region so that's going
23:36
to be a black white white white
23:44
all right that leaves us with this gray
23:46
node and that represents this region
23:50
here and it's going to be black white
23:53
white black all right so that gives us
24:00
the quadtree for this particular image
24:08
or any questions about what a quadtree
24:10
is is and how you can use it to
24:14
represent a binary image yes why are we
24:23
assuming square images you don't have to
24:25
assume square images it's kind of
24:26
convenient to assume square images you
24:30
could take a non square image and you
24:32
can fill it up with non image rows and
24:37
columns and make it square and a power
24:40
of two or you could stay with your raw
24:42
thing and essentially generalize this
24:44
and say the main concept here is you
24:47
take a region and you chop it up into
24:49
four roughly equal parts and that main
24:52
concept could be applied to any shape
24:54
image but dealing with square power of
25:02
two size images is just a matter of
25:04
convenience okay other questions
25:14
okay all right now in the worst of
25:26
situations this decomposition would
25:29
build you a full tree of degree 4 so
25:34
this gray node would have four gray
25:37
children each grade child would have
25:39
another four great children and so on
25:41
until you go down to nodes that
25:43
represent one by one at that time you
25:46
would be representing pixels that are
25:48
not divisible so you could end up with
25:50
something that's a full tree of degree
25:52
four at the lowest levels you have as
25:55
many nodes as there are pixels here if
25:57
this is n by n you end up with n square
25:59
nodes down here you add up all the
26:02
interior nodes you still end up with
26:03
order of n square nodes so in the worst
26:09
case you would end up taking pharoah of
26:12
n square space of course that tail of n
26:16
square would be bigger than what the
26:17
matrix needs by some constant factor
26:19
because now I've got nodes and nodes
26:21
have pointers whereas in the previous
26:24
case I was using bits in the best of
26:29
circumstances all of the pixels here are
26:32
white you just have a single root node
26:34
which is a white node it doesn't matter
26:36
how big the images you still take one
26:39
unit of space so as far as space goes
26:42
you have a continuum of performance from
26:46
order one space independent of the size
26:49
of the image to order of a third of n
26:52
square space where n by n is the image
26:54
size correspondingly the algorithms that
26:58
perform the functions I mentioned would
27:00
take an amount of time that could vary
27:01
from one to theta n square because as
27:05
we'll see the time required to perform
27:07
operation of the quad tree are really a
27:10
function of how many nodes you have in
27:12
the country
27:17
all right before looking at operations
27:19
on quadtrees let's just we just mention
27:22
an extension of quadtrees to act trees
27:26
so octrees could be used to represent
27:28
three-dimensional objects again for
27:30
convenience assume they're of equal
27:34
dimension so you got a 2 to the K by 2
27:36
to the K by 2 to the K region
27:38
three-dimensional region while you chop
27:40
it up down the middle into 8 equal sized
27:42
parts 2 to the K minus 1 by 2 to the K
27:44
minus 1 by through the K minus 1 so each
27:47
node will now have 8 children if it's a
27:50
gray node if it's a black node has got
27:53
no child if so white note it's got no
27:54
child so that gives you an octree which
27:57
can be used to represent
27:58
three-dimensional regions and that way
28:01
you can extend to four dimensions five
28:03
or what-have-you
28:07
now there are other structures you could
28:10
develop to represent regions than the
28:13
one we have here you could take
28:15
structures based on some of the ideas we
28:18
had last time on point data you could
28:23
take a node and you could first split
28:25
the region down the middle along the
28:27
x-direction okay so if you've got a gray
28:30
node you split it into two a left half
28:33
region and a right half region and color
28:35
those at the next level you chopped it
28:38
along the y-axis and then at the next
28:41
level you chopper get along the x-axis
28:43
again so you could have a binary tree
28:47
that represents a two dimensional region
28:50
at each level you alternately chopped on
28:53
x and y similarly you could represent a
28:57
three dimensional region with a binary
28:58
tree you chopped on X then on wide then
29:00
on Z because you don't have to use this
29:06
systematic scheme which says X Y X Y you
29:11
could say I chopped on X into two
29:12
roughly equal parts if the x dimension
29:15
is bigger than the Y then maybe you chop
29:17
on X again okay so you could have rules
29:21
to decide how you chop at different
29:24
levels but basically all of those
29:26
schemes are slight variations of this
29:30
fundamental quadtree scheme okay
29:39
all right I've said all that so let's so
29:41
let's go back to the quadtree so the
29:48
first thing you'd like to do is be able
29:51
to go back and forth between the
29:54
quadtree representation and the
29:56
representation a human would like to see
29:59
okay so you like to see images as
30:02
pictures as those matrices rather than
30:06
as trees from the tree you can't really
30:07
figure out what the image looks like
30:09
okay so we'd like to have an algorithm
30:12
that starts from an image represented as
30:14
a matrix constructs a quadtree
30:16
similarly one that starts from a
30:18
quadtree and gives you back the images
30:20
of matrix all right the way you go from
30:29
the matrix to the Padres you apply
30:31
divide and conquer all right so let's
30:38
see how you apply do I in conquer here
30:40
suppose we start with a 2 to the K by 2
30:42
to the K matrix K is 0 which means it's
30:47
a one by one then the quadtree for that
30:50
is trivial is just a single note so you
30:56
return a 1 node quadri which is colored
31:01
white if that 1 by 1 pixel was white and
31:05
it's colored black if the pixel is white
31:09
right so that's your recursion stop off
31:12
with this divide and conquer scheme
31:19
if the matrix is bigger than a
31:22
one-by-one
31:23
okay so k is bigger than one then we're
31:26
going to recursively construct the
31:28
quadtrees for the for natural quadrants
31:31
of this matrix so you chop it up into
31:35
four parts recursively build the
31:39
quadtree for these four quadrants okay
31:43
so you do it for the northwest you end
31:47
up with that you do it for the northeast
31:50
you're going to end up with this one you
31:51
do it for the southeast quadrant and
31:54
then you do it for the southwest
31:56
quadrant okay so once you get back
31:59
before quadtrees and then you take a
32:02
look at the color of these roots if all
32:06
four are black then you want to throw
32:10
away these quadtrees and return a single
32:12
node quadtree which is back if all four
32:16
roots are white you want to throw away
32:18
the four white roots and return a single
32:21
white node but if you got at least one
32:25
black and one white or you got some
32:27
Gray's like you have here then you're
32:32
going to put a root out here give these
32:34
four children to it and make that a grey
32:37
node and return that okay okay so if the
32:45
four trees you've constructed from this
32:46
recursive process all have a black root
32:50
or a white root you throw them all away
32:52
return a 1 node quadtree which is black
32:55
or white otherwise okay you're going to
33:00
get a new node here color it gray and
33:02
make these for the show
33:13
or any questions about the algorithm to
33:16
do the construction rifle look at the
33:24
complexity of the algorithm okay for
33:27
divide-and-conquer algorithm you
33:28
typically analyze its complexity by
33:30
setting up a recurrence okay so we let T
33:33
of K represent the time required to
33:35
construct the quadtree for a two to the
33:37
k by 2 to the k image then we know that
33:42
when you're dealing with a 1 by 1 so k
33:44
is 0 the time required is some constant
33:48
you just get a node and you put in the
33:50
appropriate color if K is bigger than 0
33:56
then we're going to make four recursive
33:59
calls to handle two to the K minus 1 by
34:01
K minus ones after that I'm going to
34:04
check the color of the roots of the
34:06
returned trees and possibly create
34:10
another node ok and all of that takes
34:12
some other constant tomorrow time D so I
34:18
get a recurrence this is my base case
34:20
and then this is the recursive case for
34:23
my recurrence and then you solve this
34:27
recurrence using any of a bunch of
34:31
standard techniques to solve recurrence
34:32
equation you end up with something which
34:35
says it takes order of 4 raised to K
34:37
amount of time 4 raised to K is the
34:39
number of pixels in the matrix gets a 2
34:41
to the K by 2 the caves 4 to the K
34:43
pixels right so you take time linear in
34:48
the number of pixels you don't expect to
34:50
do any better than that
34:58
if you want to do the inverse operation
35:01
somebody's constructed a quadtree and
35:04
now you want to get back to matrix
35:05
well you just run the divide and conquer
35:08
algorithm backwards it's basically the
35:13
same as what we had before we're just
35:15
going to do it in the reverse order and
35:19
it's going to take the same amount of
35:20
time to reconstruct the matrix
35:29
now let's look at rotation we've got a
35:35
90 degree rotation here's my sample
35:41
image only rotated clockwise 90 degrees
35:44
so if you rotated clockwise 90 degrees
35:48
we're going to end up with something
35:51
like this in the matrix form so starting
35:55
with this image rotated clockwise 90
35:57
degrees it's going to look like this but
36:00
I'm actually going to be starting with
36:03
its quadtree representation okay so the
36:06
transformation is done once somebody
36:08
starts with the matrix builds this and
36:09
then you perform your rotations you're
36:12
shrinking expansion into suction Union
36:14
what have you on the quadtree and when
36:18
you're done with whatever you want to do
36:19
and then you want to visualize it then
36:21
you transform it back into an image into
36:25
the matrix form okay all right so what
36:30
my input for the clockwise rotation is
36:33
this quadtree and what I want to do is I
36:38
want to create the quadtree
36:39
for this image from this one if you try
36:47
to visualize it what's going on here is
36:50
if you look at the top level okay you've
36:52
really just rotated these regions
36:56
clockwise by one position okay this has
37:00
taken the position of the North East
37:01
region that region takes the position of
37:03
the South East region and this region
37:07
takes the position of the southwest
37:09
region and this one moves up and takes
37:11
the position of the northwest region
37:13
okay so to perform this rotation of
37:16
regions all I really need to do is to
37:18
rotate these children okay I need to
37:21
take this flower here the the rightmost
37:24
child and make it the leftmost child and
37:26
by that way I would have rotated the
37:29
regions of the top level but in addition
37:33
to rotating at the top level if you look
37:35
now inside here into this northeast
37:37
region here okay it's really not this is
37:41
not just an exact
37:43
copy of that you've done the same thing
37:45
here this region is that but you've also
37:47
shifted the four sub regions in the same
37:51
fashion by one okay so I also have to go
37:54
into each of these sub trees and shift
37:56
those children clockwise by one and then
38:00
if you look further down at at lower
38:04
level regions okay so if you come down
38:08
here and you look at these two by twos
38:11
and map them back to let's see this two
38:15
by two came from that two by two
38:17
well it's really not a copy of that it's
38:19
that two by two but you've rotated it's
38:22
four quadrants also clockwise by one
38:24
position so you really have to go into
38:28
each node and rotate it's four children
38:31
clockwise by one to accomplish this 90
38:35
degree rotation alright so you can start
38:39
at the root if it's a gray node it's got
38:43
four children you rotate them clockwise
38:45
by one okay so I take this and when you
38:49
do this rotation the whole subtree comes
38:51
along with it for free okay so I move
38:54
this child to the leftmost position
38:56
since I got black black or gray and then
38:59
you look at the four children it's a
39:00
black node so there's nothing to rotate
39:01
down there so black node nothing to
39:03
rotate you look at this gray node which
39:05
is really this fellow and you rotate
39:07
it's for children clockwise who become
39:09
white gray black gray so said this
39:17
fellow represents that you got to rotate
39:18
it's for children so you end up with the
39:21
white one here so white gray black gray
39:25
okay if you look at this fellow here it
39:28
represents that guy you got to write it
39:31
rotate its four children
39:32
clockwise so it's going to become black
39:34
black white gray then you got to do the
39:40
same thing for the gray nodes down below
39:43
you okay so you look at this fellow here
39:48
which represents that fellow okay you go
39:52
to rotate its foil it's children by one
39:56
so you're going to get
39:57
white black white down here this fellow
40:02
here represents that gray node rotate
40:06
it's children by one so you're going to
40:08
get white black white white then you got
40:12
to do this guy and you're gonna get
40:16
black black white white and there are no
40:19
great children at the next level so
40:21
you're kind of done okay so basically
40:24
you need to perform a traversal of your
40:26
quad tree whenever you see a great node
40:29
rotated children one position clockwise
40:33
and then recursively do it to those gray
40:36
children or any questions about a
40:44
90-degree rotation on the quad tree
40:54
all right so the algorithms if you are
40:56
the leaf you don't do anything if you're
41:00
not at a leaf you have to be at a gray
41:01
node in that case you rotate the
41:05
children of the root one position
41:08
clockwise and then you recursively apply
41:14
this to the children of the node you
41:17
presently act right so it's basically
41:25
just a traversal of the quad tree doing
41:27
order one work at each node so you spend
41:30
time linear in the number of nodes in
41:31
the country
41:42
right the signs the quadtree could
41:44
number of notes could vary from one to
41:47
some constant times N squared the other
41:55
rotations are similar you wanted to 180
41:56
degrees 270 instead of moving by one
41:59
year they got to move by two or by three
42:03
counterclockwise is just the inverse so
42:08
you can do all of the standard rotations
42:09
in time linear in the size of the
42:11
country okay suppose you want to shrink
42:22
okay suppose you want to do a two by two
42:25
shrink with the rule that a 50% or more
42:29
of the pixels in the window a white the
42:32
result is a white pixel otherwise it's a
42:35
black pixel okay in order to do the
42:43
shrinking here I really I really need to
42:46
go and I need to look at these 2 by 2
42:49
regions so the 2 by 2 regions in my quad
42:55
tree are really represented by the nodes
42:57
at this level here these nodes here
43:00
represent one by one regions these are 2
43:03
by 2 these are 4 by 4 and then 8 by 8 so
43:08
I want to look at all of these nodes ok
43:14
if it's a gray node I count how many
43:16
white children it has it's got three so
43:19
this is going to become a white node
43:20
this is a black node is going to remain
43:23
black here it's got three white children
43:26
so it's going to become a white note the
43:28
white node will remain white that'll
43:30
remain black that will remain white this
43:32
one will become white because it's got
43:34
two white children that will become
43:36
black okay and then you may have to do
43:41
some cleanup after that because as a
43:42
result of this it's possible that I end
43:44
up with four white nodes here in which
43:47
case you got to get rid of those and
43:48
change this guy's color to white
43:51
and as a result of this it's possible
43:53
you end up with four white nodes here so
43:55
you may have to throw those away and
43:57
change the color of the parent to white
44:00
but the basic strategy is go down to the
44:02
level which represents the size region
44:04
you're shrinking count the number of
44:06
white children in that subtree and then
44:08
color this node appropriately and then
44:11
do a clean up so that great children or
44:15
gray nodes must have at least one white
44:19
and one black child alright so I want to
44:27
get to that level count the number of
44:32
white children here is three so it's
44:35
going to become a white node the number
44:37
of white children here is three becomes
44:39
a white node here it is three it becomes
44:42
a white node okay then there'd be a
44:47
clean up so you want to look at this
44:48
gray node and make sure it's got at
44:49
least one white and one black if not it
44:52
has to change into either a white or a
44:55
black you look at that fellow make sure
44:58
it's got at least one white and one
44:59
black if not change it to the
45:00
appropriate color throw away the
45:02
children then you have to look at the
45:04
parents at the next level and so on
45:11
all right terms of algorithm what are
45:13
you doing okay if you represent a one by
45:20
one region you don't do anything if
45:22
you're representing a two by two you
45:23
change its color using the rule okay and
45:31
then you need to do a cleanup step which
45:37
says shrink the subtrees if you need to
45:43
all right that I guess you can figure
45:45
out the details of this thing here and
45:49
it's going to run out run also to be
45:53
linear in the number of nodes of the
45:55
quadtree let's take a look at the Union
46:01
algorithm given two images the result of
46:09
the Union you have a rule which says
46:12
Union is you're going to perform
46:14
pairwise unioning on pixels okay so you
46:17
look at the color of this pixel and the
46:19
corresponding pixel if both the colors
46:21
are black the result is black if both
46:23
the colors are white the result is white
46:26
if one is black and one is white the
46:27
color is still white okay so the result
46:33
is white if at least one is white
46:35
otherwise the result is black so here
46:41
this gets replaced by white because you
46:43
got a white out there these get replaced
46:46
by white because you got white out here
46:48
and so on
46:54
so it's pretty much standard definition
46:56
for a pairwise unioning of bits you're
47:00
taking the order of two bits right you
47:07
can describe it recursively you have one
47:11
quadtree call it a you got another
47:12
quadtree call it B you check the roots
47:16
of root of a if the root of a is white
47:20
it doesn't matter what B is the result
47:22
is a white tree okay similarly if the
47:25
root of B is white okay doesn't matter
47:28
what a is the result is white if if this
47:38
root is black then the result is going
47:41
to be B if this is black the result is
47:44
going to be a okay so you take care of
47:47
the case when one of the two roots is
47:49
either white or black that leaves you
47:52
with the case when both roots are great
47:54
so and both have a great root then you
47:58
recursively Union the subtrees of a and
48:01
B pairwise and after you do that you
48:04
look at the colors of the four sub trees
48:07
if all a black your result is black you
48:09
follow white your result is white
48:11
because they can't be black did you want
48:12
to gone down there if they were going to
48:14
be black so you're going to really come
48:15
back with white okay so the possibility
48:18
is that the four returned sub trees have
48:20
a white root in which case you throw
48:21
them away and you color yourself white
48:29
if you get a mix then you cover yourself
48:32
great
48:37
again this is just a synchronized
48:40
traversal and two trees a and B which
48:43
will take you time linear in the size of
48:45
a and B the intersection is very similar
48:56
now you do a pairwise ending of the
48:59
pixels instead of a pairwise oaring so
49:05
if you do a pairwise ending white being
49:07
one and black being zero you're going to
49:09
end up with this as being the
49:11
intersection and you can do this with a
49:19
similar round with them we just says
49:22
first eliminate the cases when one root
49:26
is colored black or white okay that
49:29
leaves you with the case when both are
49:31
gray you work recursively on the four
49:34
sub trees of a and B look at what you
49:38
get back
49:39
if all four are black you throw them
49:42
away and color yourself black otherwise
49:45
you keep them create a root and cover
49:49
that root great runs in the same amount
49:55
of time all right so quad trees are an
49:59
interesting data structure we looked at
50:02
what you might call the simplest form
50:04
used to represent a two-dimensional
50:07
region you can extend it to four
50:10
dimensional regions you can extend it to
50:11
binary versions rather than degree four
50:15
versions the nice thing about them is
50:18
you can represent large regions often
50:20
using a small amount of space
50:23
if the regions have a lot of uniform
50:27
intensity the amount of time it takes to
50:31
perform standard operations is linear in
50:33
the size of the quadtree okay any
50:39
questions
50:43
okay we'll stop here