7. Constraints Interpreting Line Drawings Video Lecture - Artificial Intelligence

PATRICK WINSTON: Many of you,
maybe most of you, will never
have to work another search
problem by hand in your
natural life.
Others will want to
take another run
at it on the final.
I've been much criticized
for this way of doing
grading in the class.
But the way I look at it is that
the relationship between
students and instructors ought
to be less adversarial than it
used to be in the good old days
when I was a student.
I especially remember an
examination we took--
all of us took-- on Rayleigh
scattering.
That was 803, I think.
And back in the old days, we
had to take four physics
courses, not just two.
And we had to take four math
courses, not just two.
Back in the days when--
well, I was going to
say men were men.
But most of us were
men in those days.
I think we only had 20
women in our class.
Anyway, we had a quiz on
Rayleigh scattering.
And I thought, well, this
is pretty hard.
And then I got my quiz back.
26.
I thought, well, I've
been found out.
I'm going to flunk out.
My father will make me
go to law school.
I'll never attract
anyone to marry.
Horrible things will happen.
Then the instructor announced
the class average was 18.
I was two standard deviations
above that.
They gave us the same exam
two weeks later,
and accounts vary.
Some people say that the class
average went down.
Anyway, today we're going
to study some stuff.
We're going to study some
stuff that will make it
possible for you to understand
how you can do that
computation in just a couple
of seconds, even with the
delays introduced by
the redrawing.
Now this particular program--
I'm not real sure and I don't
have a proof, but I think it
will take more than the lifetime
of the universe to
find a legitimate coloring of
the continental United States.
But by the end of the next
class, you'll see how to do
that lickety-split in just
couple of seconds, even with
the re-display delays.
Now we could, of course,
do this in two ways.
One way is I could start off
by saying, let C be a
constraint satisfaction
problem and just
give you the result.
And anybody can do that.
That's great.
And you needed to learn
some stuff that way.
But there are some things that
you needed to learn, I think,
a different way.
And that different way involves
my telling you the
story of how it all
came to be.
This is a new field, pretty
much, and therefore I know
most of the people in it.
And I know all of the people
who did the work that I'm
going to tell you about today.
I'm going to tell you a little
bit about the struggle for
coming up with the ideas that
led to one of the most
powerful methods you'll learn
about in the subject.
It all has to do, originally,
with an attempt to make a
computer capable of seeing.
And everybody said to
themselves, well, let's start
with seeing simple things,
like children's blocks.
And so Adolfo Guzman, a graduate
student of Marvin
Minsky's, was charged with the
summer project, which led to
his Ph.D. thesis, of writing a
program that could look at a
line drawing and determine
how many objects
are in the line drawing.
So for example, there behind my
outline is a line drawing.
And you believe instantly that
there are two objects there,
even though in some deep
sense, it's ambiguous.
There are all sorts of ways
that you could, through
trickery, arrange something with
even seven objects that
look that way.
But most people would say
there are two objects.
So Guzman set about the
problem of figuring
out how to do that.
And then his work was followed
by Dave Huffman.
And his work was followed
up by Dave Waltz.
And his work was followed up by
Jane [? Froyter ?], who's
not listed there quite yet.
And I want to tell you a little
bit of story how that
all happened.
So Guzman took a lot
of pictures.
He went to Boston Baby, the
precursor to Toys R Us,
purchased a large block set on
a government contract, and
went about the business of
taking a lot of pictures of
them so he'd get a feel
for the domain.
And eventually he decided that
he could build a program that
could determine that there are
two objects here by using the
lines as a quanta of evidence
about which faces belong
together in an object.
So he said, after studying these
for a long time, that
these drawings tend to have a
lot of arrow-type junctions
and a lot of fork-type
junctions.
And when you see an arrow, it's
a little bit of evidence
that the objects on either
side of the shaft are the
same-- the face on either side
of the shaft belong to the
same object.
And over here, the fork-type
junction suggests that
pairwise, three pairs
of faces seem to
belong to the same object.
So with that idea, he could come
back to a drawing like
this and start decorating it
with these so-called links,
these quanta of evidence
that faces
belong to the same object.
And if I've done it right,
you get something
that looks like so.
It's a little hard to
see what's going on
on the drawing itself.
So let me number these.
Now I have an
easier-to-deal-with picture.
There are two links between
1 and 2 and 1 and 3.
One link between 2 and 3.
One between 2 and 4.
Two here.
Two here.
And one each from
all of these.
So Guzman produces this evidence
for how the problem
ought to be solved and then he
begins to think about various
ways of using the evidence.
So he could, and did, decide
that one link is enough to
presume that the faces belong
to the same object.
And you can see that that's
a little bit too liberal.
Because that says
that the whole
thing is just one object.
So Guzman rejected the one-link
theory and went to
the two-link theory.
And the two-link theory says,
oh, well, let's see.
If we insist that two links
should be there before we are
willing to decide that it's the
same object, then these
three faces are pulled together
into one object.
These three are pulled together
into one object.
But alas, 7 doesn't share two
links with anything, so it's
left dangling out there.
So plainly, the two-link theory
is too conservative.
So that as you would soon
discover in any [INAUDIBLE]
project, would lead you to a
third theory, which is two
lengths repeated.
So now that we've formed these
super regions, we can come
back and say we'll merge super
regions if they're connected
together by two or more links.
So nothing new happens
up here.
But this super region
is joined at 7
by two or more links.
So it pulls everything
together like so.
So that worked fine.
Well, it didn't work fine.
There were lots of examples
of situations
where it didn't work--
in situations that were
considered nonsensical by us
humans because it seemed silly,
the kind of conclusions
that it reached.
So when Guzman presented this
work in his Ph.D. thesis
defense, it's said--
and who knows if it's true--
but it's said that Marvin
Minsky thought it was
great work and we
should make him a professor.
It happens that Dave Huffman was
also on the committee and
said that it was ad hoc and the
thesis should be rejected.
So we had two polar opposites
of impressions there.
Dave Huffman, by the way--
you've heard that name
before, I imagine.
It's the guy who invented
Huffman coating as a term
paper in a information theory
course taught by Bob Fano.
He got an A, they say.
So Huffman didn't like it.
He thought it was a little
bit too ad hoc.
It was too heuristic.
It didn't take advantage
of anything we
might know about physics.
And so people began to say,
well, why does it work?
And when does it not work?
And that's just about the best
question you can answer in a
situation like this.
And by playing with some more
of Guzman's pictures and
reflecting on them, it turned
out that it worked because the
world is full of three-face
junctions.
Or let me say three-face
vertexes because they're out
there in the world.
We'll reserve the word junction
for something else.
And three-face vertexes
generally project into either
an arrow or a fork.
So Guzman's whole program worked
on the weak backward
conclusion that if you see one
of those, it probably came
from one of these.
So this is in the drawing.
That's in the world.
So by a process that's neither
deduction or induction, but
rather abduction, you see
one of those guys.
And you say, well, they often
come from three-face vertexes
in the world, so if you see one,
it probably came from a
three-face vertex
in the world.
That's abduction.
So once Huffman saw all that,
being a mathematician, he
began to think about how one
might develop a different and
better theory.
But we have to recognize that
all this work started off with
the efforts of Guzman, who
was an experimentalist.
And Huffman was a
mathematician.
So naturally, they approached
the problem differently.
So Huffman says, I'm not going
to concern myself too much
with the actual problem that
Guzman was trying to solve.
Rather, I'm going to work in a
very simple world, which I can
deal with mathematically.
So he decided that he was going
to work in a world which
had several characteristics.
Characteristic number one was
that the world would be
presented in general position.
That is to say, no
screw cases.
So if you see a cube, it's
going to look like this.
And it's not going to
look like this.
So that's out.
And this is in.
And the idea here is that that's
not general position,
because if you perturb your
point of view a little bit,
you'll change those T junctions
into forks and arrows.
So we know it had to deal
with those kinds of
weird kinds of cases.
So that's presumption
number one.
Presumption number two is that
we're going to be dealing with
a world that's trihedral.
That means all vertexes out
there are going to be formed
from three planes.
So you're going to have the
intersection of three planes.
So how many kinds of junctions
can you see if the world is
composed that way is the
question that Huffman sent
himself upon.
The next assumption was that
there are going to be four
kinds of lines.
See, Guzman only recognized
two kinds of lines-- lines
that have a length and lines
that don't have a link.
And they don't have very much to
do with the physical world.
So Huffman says, I want to get
the constraint out of the
physical world.
So I'm going to deal with
four kinds of lines--
concave, convex, and boundary.
So each of those kinds
of lines is going to
have its own notation.
We'll call the convex lines
plus, the concave lines minus,
and a boundary lines are going
to get an arrow on them,
depending on which side
of the object--
which side you would see the
object if you walk along the
direction of this
little arrow.
STUDENT: Question.
Which is concave and
which is convex?
You said something and you
wrote the opposite.
PATRICK WINSTON: Yeah, sorry.
Thank you.
So concave, convex,
and boundary.
Thank you.
So this down here, that's
a concave line.
And that would get
a minus label.
Oh, I don't know.
These lines you're seeing here,
if there were stuff
behind them instead of
me, then all those
would be convex lines.
Many times you see
a boundary line.
For example, now you don't see
both sides of that line down
here at the bottom.
So that's a boundary line.
And the arrow would point in
that direction, so as to keep
the stuff of the object on the
right as you walk along a kind
of mathematical convention.
So three kinds of lines,
four kinds of labels.
And there's some things
left out.
That's because Huffman wanted
to keep his problem simple,
something he could
manage by hand.
What's left out?
Cracks are left out.
Shadows are left out.
There's a presumption that
there's nothing of interest
here with respect to that.
So let's have a little
vocabulary before I go on.
And I'll try to stick to it.
But there's the stuff out there,
and that consists of
vertexes and edges.
And over here, on the
blackboard, we'll have
junctions and lines.
And I'll try to stick
to that vocabulary.
All right?
Yes, Christopher?
STUDENT: Didn't you say there
were four types of lines?
PATRICK WINSTON: Yeah, there
are four kinds of--
the question is, didn't
I say there were
four kinds of lines?
There are three kinds of lines,
but since we can label
a boundary line in
either direction,
we have four labels.
OK?
It depends on which side of the
object the stuff is on.
And that will be clear,
I think, as
soon as I do an example.
So one, two, three
assumptions.
A little bit of vocabulary.
So we have the possibility of
making a complete catalog.
This is so simple.
We have the possibility of
making a complete catalog of
all the ways that lines can
come together to form a
junction with respect to
these four labels.
Now at first you might say, oh
my god, that will take a
couple of years.
But maybe it won't take
a couple of years.
And in the end, to perhaps your
surprise, you discover
that there are only 18 ways to
arrange the labels around a
junction in this world.
Everything else is excluded.
If you have something that's not
in the set we're going to
produce now, it can't be built
with trihedral vertexes.
So I've listed up there six L's,
five forks, four T's, and
three arrows.
Let's see if I can figure out
why there are those 18 and
nothing else.
Well, if we have three vertexes
coming together, that
means there are eight
octants, right?
And the stuff of the object may
fill 1, 2, 3, 4, 5, 6, 7
or all eight octants.
Now of course, if you
fill all eight
octants, there's no junction.
So we don't consider
that case.
If we don't fill any the
octants, there's no junction.
There's no vertex.
So we don't consider
that case.
But if just one of the eight
octants is filled with stuff,
then we can look at
it from any of the
seven remaining octants.
So right now, you're looking
at it from one of the seven
remaining octants.
And if I'm not mistaken,
you're going to see a
fork-style junction
there, right?
And you're going to see a
fork-style junction in which
all of the edges are convex.
An unfortunate selection of
names, because the linguists
tell me that we index
all of our words
by the first forename.
And those have the same
first forename, so
they're easily confused.
So here's a fork-style
junction.
And we know that one way that's
legitimate for the
lines to come in is
with four pluses.
Now that's not the only
way you can see that.
And here's another way.
There's an L-style
junction, right?
And both of those are
boundary lines.
And we want to draw the boundary
line indicators on
there so that if we walk along
the arrows, the stuff of the
object would be on the right.
So I suppose, to make it easier
to me do my drawing, I
should look at it this way.
And then I would say, well, that
has to be a legitimate
way of labeling a junction.
Are there any more?
Well, there's seven altogether,
but many of them
are the same.
There is one more that's a
little different, though.
I can hold this guy
up like so.
And if I'm holding at the right
angle for you, you see
an arrow-style junction,
right?
Two boundaries, and the
barb is convex.
So in this particular
case, I've got that.
I've got that.
And I've got a plus there.
And that's there happen to be
for the one octant filled with
stuff case.
I happen to be able to
reverse this, though.
And here's the seven octants
filled case.
So that tells us that it's
possible to have a vertex out
there in a space that when
reduced to a junction on the
board deserves three minus
labels, because all of these
that you're seeing
now are concave.
So another fork-style junction
looks like so.
And since there's only one
octant to look at from, that
completes our analysis of the
seven octants filled case.
Now we have a couple of other
possibilities here.
We might have five octants
filled with stuff.
So that means there are three
octants that we can look from.
So let's suppose that
these little chalk
pieces are little people.
And they're looking at this
junction down there, where
this white object is fused
with the table.
I'm fusing it with the table
because I want to consider it
to be one object.
We can view it from the three
objects indicated by those
three little chalk pieces.
And ask ourselves, well, in the
event that we look at it
from those three places,
what do we see?
And if we look at it from the
perspective of the piece of
purple chalk--
I'll have to walk around
and be sure--
looks like an arrow
junction with two
concaves and a convex.
Did I get that right?
So I'm looking at it from
this perspective.
It's an arrow.
This is convex and these two
are concave because I fused
the paper box with the table.
Looking at it from the
perspective of this blue guy--
let me rotate it so you can have
a better understanding of
the blue guy--
it looks like a concave
line and a boundary.
So it's an L. And this
one is a boundary.
And that's concave.
And by a kind of symmetry, we're
also going to get that
one from the other side, the
third of the three octants.
Well, we're off and running.
But we still have an
awful lot to go.
And we could manage to deal with
it by thinking about this
object once again.
But instead of this situation
out here, to turn it around
and look at this vertex.
Think about the junctions
that it can produce.
I think I'll do that for you.
Because you really have to play
with this and move it
around a little bit to see how
things are going to look.
So let me think about how that's
going to work out.
I know that one of the
possibilities is going
to look like so.
I might as well not hide
that from you.
It's going to be what happens
when there's a little man
looking up at the junction.
And this one's going
to be minus.
And now we've got two more
that are just like that.
Look like so.
And you say, oops.
You say, aren't those
just a rotational
variance of each other?
And the answer is sure.
I write them all down, because
if you get a fork-style
junction in space, there are
three different ways it could
be labeled.
Depending on which of
the lines you put
the minus label on.
So that takes care of that.
And then there's one more of
these fork-style junctions.
And that's plus, plus, minus
that derives from this case.
And there appear to
be three more of
these L-style junctions.
And they look like, let's
see, plus, then plus.
I'm having to think this
through as I go.
And then--
and that's it.
Well, what about the T's?
Well, in this world, the only
way you can get a T is if some
object is obscuring
another object.
And if an object is obscuring
a line, it can
be any line at all.
So that's why the four remaining
ones are easy beyond
description to label.
And of course, the cross
pieces of the T are all
boundary lines, with the
obscuring object on the right.
Now let's see.
We've taken care now of the one,
three, five, and seven
octants filled cases.
What about two, four, and six?
Well, it turns out you can have
vertexes that are made
that way too.
But they will have more
than three faces.
They'll have six faces.
They'll be like what happens
when an object comes together
at a point, like so.
Like that.
You can play with it a little
bit and see that if you have
two, four, or six objects filled
with stuff, there are
more than three faces.
So we're going to
ignore those.
So our constraint is going to
be a little more severe than
would be suggested by the
terminology Huffman uses.
They're going to be trihedral
all right, but they're also
going to be three faces.
So we went to a lot
of work there.
But what have we discovered?
We've discovered that in this
world, this is a complete,
100% percent, nothing excluded,
nothing else can be
there, catalog of all possible
ways the junctions can have
line labels arranged
around them.
There's nothing else
in this world.
So that's a very powerful
constraint.
So now let's see what
we can do with it.
This example is usually more fun
when the Red Sox are doing
better, but they're not.
Yet we'll use it any way.
We're going to start
with an object that
looks like home plate.
And I'll ask you the question.
Can you build one of those?
I don't know.
Let's give it a shot.
We're going to assume that
this object is hanging,
floating in space.
So therefore, all of these lines
around the boundary are
boundary lines, like so.
Now that gets us off to a good--
it's just hanging in
space, Christopher, all right?
You look confused.
It's just hanging in space so
that all the lines around the
edges are places where you see
only one side has stuff on it.
So that enables us to just
quickly run around the
periphery and put arrow labels
on all those outside lines.
Now we have a lot
of arrow-style
junctions on the boundary.
That's commonly the case.
So we can run over to our
catalog of all possible
labels, and we see that if we
have an arrow with boundaries
on its barbs, there's
only one of those.
So I know instantly that there
must be a plus on the shaft.
So we can come back here and
take all these arrows here.
And label them with plus
lines on their shafts.
Now a line can't change its
nature along its length.
So if it's a plus line on one
end, it's going to be a plus
line on the other end.
All right?
So what else can we do?
Here deep inside is a
fork-style junction.
It's got convex markers on
both of those two lines.
So we go over to our catalog and
say, what can we say about
it, given that there are pluses
on two of its lines?
Whoop, that means that
the third one has to
be a plus as well.
And now we're done.
We've labeled everything.
Except--
look at this.
What about that guy?
There's an L-style junction
with pluses on
both of its two lines.
Is there one of those
in my catalog?
No.
Therefore, I haven't passed
a necessary condition for
constructability in the
world that I've made.
You can't make it.
You can't construct it.
So Huffman's ideas give us a
way of testing something to
see if it's not possible for
it to be in this world.
If it passes the test, does
that mean it's possible?
No.
It's a necessary but not
sufficient condition.
On this one--
blue-collar occupation--
on this one, maybe it
will help if we
put in another line.
For example, we could
put a line like so.
You feel better about it now?
I don't know.
Let's see.
This has to be a plus for the
same argument we used on
several other arrows before.
That gives us an arrow-style
junction here with a plus on
everything.
Is there such a junction
label?
No.
We lose.
It doesn't help.
You think you can make
it, but you can't.
STUDENT: You could actually
construct it as
a 3-D object, though.
PATRICK WINSTON: He
thinks you can
construct it as a 3-D object.
Let me show you the next
example, Christopher.
Consider this example.
Can you make that?
Your intuition is yes.
So let's label it.
Oh, I've already lost.
We just boost that up a
little bit to make the
situation more clear.
So already, I've got myself in
a situation where I can't
label that.
But you feel like
you can make it.
So what's wrong?
What's wrong is--
what, Elliott?
STUDENT: You have
an obscured--
or, we're presuming that we have
an obscured [INAUDIBLE]
alley from the upper-left corner
to the [INAUDIBLE].
PATRICK WINSTON: Putting a
little interpretation on what
Elliott has said.
If you look at this situation
back here, you get a
four-faced junction there.
So you can make it.
But not with three faces.
So some of these look like
you could make it.
But they can't be labeled
because you need more than
four faces at a junction.
And we can carry that
idea back here.
You can make this OK.
But this junction, you've got
two in the back and two here.
So it has four faces.
Same idea.
So that's Guzman's
contribution.
That's Huffman's contribution.
Huffman was a mathematician.
But we wanted to build robots
back in those days.
And neither one of these guys
solved the problem of dealing
with natural objects with
shadows, with cracks, with
more than trihedral vertexes
in space, and
what to do about that?
Well, that was a problem that
another graduate student,
David Waltz, set
about to solve.
So Waltz decided that he would
not be content unless he added
cracks, shadows, non-trihedral
vertexes.
Uh--
yeah, non-trihedral vertexes.
And light.
These considerations led
Waltz to go from
four labels to 50-plus.
Because he had to pack a lot
of information into each of
the labels he put on a line.
What kind of light
was on the right?
What kind of light
was on the left?
Maybe it's a crack.
Maybe it's a crack that--
all sorts of considerations.
Here we had 18 ways that
lines can come
together around junctions.
That went to thousands of
junctions in Waltz's world.
So here's Guzman.
He writes a program that
sort of works.
Down below, we have Huffman.
Huffman, who has a theory but
solves the wrong problem.
So here comes Waltz, and he's
trying to solve the right
problem with a satisfying
theory that has a
generalizable principle.
So when we get all through
this, we'll talk about
criteria for success.
And we'll conclude that to
have a really successful
thing, you need a problem,
to start with.
You need a method that works.
And you have to show
that it works
because of some principal.
So Guzman had the problem and
something that worked.
Huffman had a method which
worked on the wrong problem.
And it's left to Waltz to
bring it all together.
So Waltz does all this work.
And now he has, instead at 18
labels, he has thousands.
Instead of four-line labels,
he has more than 50.
So naturally, it becomes
difficult to
work these by hand.
We were able to work those
Huffman examples by hand.
We started with labeling
everything on the boundary and
worked our way in.
There's no particular
method there.
It was just easy to work
out the puzzle.
But poor Waltz, he didn't
have that luxury.
So he might have, in a typical
scene, he might have tens or
even hundreds of junctions to
label and no easy way of
dealing with it.
So naturally writes himself a
depth-first search program.
So here is vertex, or rather
junction number 1.
There are many choices for which
label can be used on it.
And for each of those choices,
whatever he's decided junction
number 2 is has its own suite
of possibilities.
And so it becomes a
simple depth-first
search problem, right?
So in actuality, as
soon as Waltz--
he was my office mate
at the time.
I can tell you this
for a fact.
As soon as he wrote this
program, he kept looking over
at the computer--
they were big in those days.
They all had lights.
So you looked over at the
computer to see if the lights
were still blinking.
Because he'd start this
depth-first search program up
and nothing would happen.
He thought the computer
had crashed.
Nothing happened.
Why did nothing happen?
Because the search base is
exponential and much too big
for an ordinary computer,
or maybe
even an ordinary universe.
So Waltz has to do
something else.
He has to come up with a new
method for using all these
labels that he's--
after about a year and a half's
worth of hard work,
with lots of paper on his
desk in little blocks.
After year and a half of hard
work getting all these
junction labels figured out, he
then has to come up with a
method for figuring out
how to use them.
And so we don't know whether
to think his biggest
contribution was that label
set or his method.
And probably both deserve
about equal billing.
Oh, I don't know how to explain
what Waltz did.
Well, one way is to
do an example.
And I think I will hazard
an example.
Let's see.
Let me find some space.
I think I'm reduced to
going over here.
But that will be convenient,
since the
line labels are here.
Here's my example.
And you say, how can I give you
just part of a picture?
Well, you can assume
I'm looking at
this through a window.
So the edge of the window form
boundary lines, and they exert
no constraint whatsoever
on what's behind them.
So this is a legitimate
drawing to
have to think about.
By the way, is this ambiguous?
Or do you get a firm sense
that there's a unique
interpretation of
all those lines?
I think there's a unique
interpretation
of all those lines.
What I'm going to do is I'm
actually going to solve this
problem using Huffman's labels
but Waltz's method.
Because I can't simulate on the
blackboard something with
50 line types and thousands
of line junctions.
So I'm going to use
Huffman's set to
demonstrate Waltz's algorithm.
So Waltz's algorithm involves
starting out by plopping on
some junction all of the
possible labels that the
answer has to be drawn from.
So let me number these in the
order that we're going to
visit them.
Like so.
And so far, I've just put down
the three fork options that
are resident on that
first junction.
And I have to take note of
exactly what they do with the
lines that come out
of the junction.
So let's see.
I'll just copy them down.
One possibility is this one.
Another possibility
is this one.
And another possibility
is plus, plus, minus.
Oops, I've got plus, plus.
No, that's right.
So that right so far?
All I've done is copy
the junction
labelings from my library.
And at this point, Waltz's
algorithm says there's nothing
else to do but go on to
junction number two.
And unfortunately, sadly, there
are lots of labelings
that have to be considered
on junction number 2.
Six of them.
1, 2, 3, 4, 5, 6.
So one of them looks
like that.
Another one looks like that.
One of them is plus
here, arrow in.
Another one is plus
here, arrow out.
Another one is minus
here, arrow down.
And minus here, arrow up.
I think I've copied
those all right.
But now, having copied those
down, Waltz's algorithm looks
around at the neighboring
junctions and says, are any of
the things that I just placed on
junction two disallowed by
what I've already placed on
a neighboring junction?
So it looks over here
in step number two.
And it sees that these three
arrows require the line that
joins junctions 1 and 2 to
be either minus or plus.
So of the six possibilities, I
can only keep the ones that
are likewise content to put
a plus on that line
that joins the two.
So that means that the influence
flowing from
junction 1 eliminates that
one, eliminates that one,
eliminates that one, and
eliminates that one.
So half of them are gone.
All the ones that try to put a
boundary line on that line
between 1 and 2 are
disallowed.
All right?
Now likewise, we could say,
well, of the remaining ones,
do they restrict what I
can do at junction 1?
So let's see.
Here's a minus.
And here's a plus.
So all these possibilities over
here are still alive.
So now, continuing on, we have
to see what we can do at
junction 3.
These are arrow labels again.
So we have to copy exactly
the same labels
set as we had before.
And now we look down at junction
2 and say, well, what
does that tell me about the
three that I've just placed?
If we look up from junction
2 to see what kind of
constraints it puts on here,
we have this one alive and
this one alive.
I guess we've eliminated
four of the six.
So we have these two alive.
And they both but
boundary lines--
I think I must have had this
boundary line wrong, right?
No, that's right.
Oh yes, I see.
Plus.
This one goes--
hang on a second.
You let me do something wrong.
So plus is out.
And that must be
one that goes--
this minus goes up.
Oh, yes.
I'm too hasty and uncertain
about what I was doing.
So let's see.
This guy has a boundary
going down.
And this guy has a boundary
going up.
All of the others have
been eliminated.
So that means that something
that tries to put a concave
line there is gone.
And something that tries to put
a plus line there is gone.
So the influence flowing up in
this direction in the third
step eliminates that guy and
eliminates that guy, leaving
only this guy.
But now, the thing I was worried
about is you have to
also at this point go down to
2 and see if there's any
further constraint on what can
survive down there, based on
what has happened over
here at junction 3.
Now let's see.
This one goes up, which is
compatible with a survivor.
But this one goes down,
which is not
compatible with a survivor.
So when I bring this down in
step three, this guy is
eliminated.
So now I'm down to just one
interpretation for what can be
going on at vertex number 2.
And one interpretation
for vertex number 3.
Now let's see.
This can propagate.
So now that I've made a change
on vertex number 2, I have to
also see if that causes a change
at vertex number 1.
So it's propagating through.
And now I can see that the only
possibility here is a
minus, the label that's coming
down from our survivor.
So that eliminates these two.
Whew!
It's hard to do this by hand,
but I've got three of the four
things labeled.
And even with just three of the
four labeled, I'm down to
a single interpretation for all
of the junctions and the
lines between them.
So there's one left.
We have to deal with
that fork vertex.
We better deal with it, because
for all we know, this
is not a legal drawing
in this world.
We have five fork vertexes
to place.
But you know what?
I don't have to draw much here,
because I know this is
forced to be a plus now.
And this is forced
to be a plus now.
And there's only one fork
vertex with any
pluses on it at all.
So now I can come through and
say, well, the only possible
survivor is this one.
These are gone.
And now I have an
interpretation
for all of the junctions.
And I see that the winners
are this one.
And this one.
And this one.
And this one.
So I've got a unique
interpretation.
This line is convex.
This one is concave.
This is a boundary.
That's a boundary.
And this line is convex,
and that's convex.
Now that's a lot of work.
So I better check and make
sure I got it right.
You'd like to see this
demonstrated to make sure I
haven't made a mistake.
I'm sure of that.
Let's see.
That it?
So each of the places where a
line is obscured has four
possibilities, labeled E. The
arrow junctions are labeled A.
The forks-- there are five of
them-- at the fork junction 5.
So let's just step through here
and see what happens.
Boom.
I've got it.
I did do it right.
So let's try some more.
What do you think will
happen with this one?
Unique solution?
It stopped.
Bug in my program?
Unthinkable.
What's happened?
It is genuinely ambiguous.
It can be something hanging
down from the ceiling.
Or it could be something that
we can think of as a step
going up from left to right.
Let's look at something
more complicated.
You think it'll work?
Not enough constraint for us
to figure that one out.
It's equally ambiguous, but a
little bit larger example.
What about this one?
Yeah, but the stuff is creeping
up from the lower
left up to the upper right.
Yeah, bingo.
It worked.
It's unambiguous.
It's variation on the same
theme we had before.
But let me, just for fun, take
these two lines out.
What do you think
will happen now?
Seems to be doing just fine
until it hits the upper
right-hand corner and discovers
it can't label stuff.
So it propagates back down.
And what looked OK in
the lower left is
no good after all.
So these results are kind of
consistent with what we humans
do when we look at these
kinds of things.
So it's very likely that we,
in our heads, do have some
constraint propagation
apparatus
that we use in vision.
But putting that aside, we can
think about other kinds of
intelligence different from
human, that might use this
kind of mechanism to solve
problems that involve a lot of
constraint in finding
a solution.
So here, we saw the constraint
propagation activity at work
on line drawing analysis.
But next time, what we're going
do is we're going to see
at work in map coloring.
And who cares about
map coloring?
People who do scheduling,
because that turns out to be
the same problem.