So, welcome back to the lecture on automotive vision.
Yeah, last Monday we started to talk about tracking objects in the
three -dimensional world and determining their movement.
That means their velocity, their direction of movement, etc.
And yeah, we started with a traditional regression approach.
And just to remind you of the last slide that we discussed, that was
actually this one.
We assume that we have a camera or another sensor that is measuring
the position of a vehicle that we observe over time.
So, in this case, we have four different points in time.
For each point in time, we get a measurement where the vehicle is.
Of course, all these measurements are suffering from imprecision and
noise.
So, they are not exactly the true position of the vehicle, but just a
measurement of it.
Then we said, okay, if we assume that the vehicle is moving this
constant velocity along this road here, which is given by a certain
coordinate system, then we can say that the position of the vehicle at
a certain point in time t can be described by means of this linear law
of movement, a certain initial position plus the velocity times time.
And, of course, what we do is we measure the position.
So, the measurement itself is affected by a certain amount of noise
and imprecision that we might add here.
And then we were saying, okay, we do know the sensed position on the
left -hand side for some points in time.
We know the points in time t at which we made the measurements.
And what we do not know is the initial position x zero and the
velocity v.
So, these are the two unknown variables and x of t, the sensed
position at a certain times t, and the point in time t is what we
know.
And now we want to, well, determine the unknown parameters from our
measurement.
And the way we can do so is that we say, okay, for each measurement,
we can enter x of t here on the left-hand side, we can enter t here on
the right-hand side, and we aim for finding x zero and v such that
these equalities that we get for all the measurements are almost
fulfilled.
Now, if we have more than two measurements, then it's very likely that
we don't find any initial position and velocity with which all the
equations are met completely perfectly.
But we will, we aim for a solution that is good for all possible
measurements.
And this can be done by eliminating this, actually the difference.
So, this is the difference of the left-hand side and the right-hand
side of this equation, taking the square of it, and then summing up
this error in this equation, so to say, that we get over all the
measurements, the n measurements that we have.
So, now we have a kind of error measure that describes how good a
certain choice of x zero and v fits to the measurements.
So, the larger the value is here of the sum, the, well, the larger the
sum is, the worse is, the worse is the fit.
That means x zero and v do not fit to the measurements.
If the sum here is very small, if it is close to zero, then we know
that the certain choice of x zero and v fits very well to the
measurements.
That means that we found good choices of x zero and v.
So, how do we determine the best solution?
Well, we take this term, we calculate the partial derivatives with
respect to the unknown variables x zero and v, we zero those partial
derivatives and resolve the system of equations that we get.
And this is shown here.
So, once you do all the calculations, you will see that we end up with
such a system of linear equations.
And as soon as the matrix on the left-hand side has full rank, which
typically is the case as soon as we have at least two measurements,
then we can resolve the system of equations and get the best values
for x zero and v.
If we like, we can also derive in a second step variances, that means
measures of uncertainty that tell us how sure we can be about the
values of x zero and v that we have found.
So, we can even extend our approach.
So, up to now we were assuming the vehicle is moving with constant
velocity.
However, in some situations this is obviously not true.
So, we assume the car is waiting in front of traffic lights and now
the traffic light switches to green and the car accelerates.
Of course, in this such a situation, definitely this assumption that
the vehicle is moving with constant velocity is not met.
So, in this case, we need another motion model that we apply to
estimate the movement of the vehicle.
And for instance, we could assume in this case that the vehicle is
moving with constant acceleration.
And in such a case, we will get a motion model like the one here on
the slide, that x of t can be described by an initial position x zero,
an initial velocity v zero, and a constant acceleration a.
That means all the measurements that we make, we assume that all those
are determined from such a linear... from such a relationship that we
see here.
Yeah, and that the movement of the vehicle can be explained by these
three parameters x zero, v zero, and a.
Now, we can proceed as in the case before.
We make a certain number of measurements, where we measure the
position of the car at each point in time.
Then we create an optimization problem, where we say, okay, what we
want is for each measurement, we want that the left-hand side and the
right -hand side of this equation fits as best as possible.
That should hold for all measurements in parallel.
That means what we do is, we create this difference of the left-hand
side and the right-hand side of this motion equation here.
We sum up the squares of those differences over all measurements, and
then we state, okay, we want to find those parameters which minimize
this term.
Again, we calculate the partial derivatives of this term, zero those,
and resolve the system of equations with respect to the unknown
variables a, v zero, and x zero.
This also yields a system of linear equations, and yeah, if you like,
just derive it at home.
What are the advantages of such an approach, of regression approaches
in general?
Well, so first of all, these approaches are simple.
The calculations that you need to do are rather simple.
It's easy to use, efficient calculations.
The only thing, the most expensive thing that you have to do
computationally is, you have to solve a system of linear equations.
But this small system of linear equations, this still is not really
time -consuming.
So that works easily for all straight movements in a one-dimensional
case.
So if you only consider the position of a vehicle along a road, for
instance, it also works in a two-dimensional case.
If you want to estimate the two-dimensional movement of a vehicle, so
a movement on the plane, so assume a parking lot or something, a large
planar area where a vehicle is moving, and you want to estimate its
velocity, this can also be done with linear regression.
And also in 3D, it would work.
So if you have a spaceship or whatever, and you want to describe the
movement of the spaceship, it would also work.
So my suggestion is, give it a try.
So if you are faced with such a problem, try such a regression
approach, whether it works or not, and before you go to more
complicated approaches to solve the task.
Shortcomings of these methods is, of course, as soon as we are not
faced anymore with straight movements, and we want to create motion
models of not-straight movements, so for instance, for a car that can
turn, so it can drive along a circle on a circular trajectory, then
those approaches become non-linear, so we get non-linear optimization
problems, and so we have to use more complicated numerical solvers to
solve those.
It's still possible, but it's computationally more demanding.
So one example where we were using these kind of regression approaches
is robot soccer.
That's a project that I did many years ago meanwhile, so more than 10
years ago.
So we were operating autonomous robots, these ones here with a pink or
the violet number signs.
They were fully autonomous, yeah, they had a camera on board with
which they could detect the environment and recognize objects in the
environment.
You see, the environment was color-coded in a certain way, so there
was an orange ball so that it is easy to detect it.
All the obstacles are black, the ground was green, there were white
lines, so all these things.
So a color-coded environment so that the perception is not too
complicated, which was quite challenging, still challenging at these
days when the computers were not that powerful as today, and the
computer vision techniques as well were very limited in what they were
able to do.
However, so the task was to let those robots play soccer autonomously,
so not tailor-operated, no one at the sideline that was having a
joystick to operate them, but they had to decide on their own what to
do and how to behave.
And of course, for playing soccer, it is very important to know where
the ball is, and it's also very important to know in which way the
ball is moving.
Yeah, obviously, if you want, for instance, to implement a goalkeeper
and the goalkeeper only knows where the ball is at the point in time
when the last measurement was made, then the goalkeeper will not be
very successful, yeah, because it doesn't know in which direction to
drive and where to expect the ball crossing the goal line.
Okay, so we need the motion of the ball, and also we need our ego
motion.
We, of course, need to know how fast we are moving, in which direction
we are moving.
Yeah, so these were the two things that we were trying to estimate
with regression.
And of course, we would like also to estimate the movement of other
robots, but at that point in time, the recognition of the other robots
was not that stable and not that reliable that we could do it.
Okay, so we're estimating the motion of the ball.
Yeah, we did that with the regression approach.
Just a brief sketch of how we did it.
So, the first starting point of our development was at a point in time
where the other soccer teams could not do chip kicks.
So, they could only kick the ball in a flat way, so the ball was not
leaving the ground.
So, we could assume that the motion of the ball is a two-dimensional
motion on the plane.
And we also were assuming that at least for short periods of time, we
can assume that the ball moves with constant velocity.
So, if the ball is dribbled by another robot, or if the ball was
kicked and now is moving afterwards, we were assuming that at least
for a couple of, no, say for several hundreds of milliseconds, we can
approximate the movement of the ball sufficiently well as a movement
with constant velocity.
Of course, it was not perfectly true, but it was still okay.
For that purpose, what we did was we were estimating the velocity of
the ball based on the last observations.
We took between 3 and 15 observations, the last 3 to 15 observations,
and we had a frame rate of the cameras of 33 milliseconds.
That means, if we have just 3 observations, the time between the first
and the last observation that we were using was roughly 66 to 67
milliseconds.
So, this was a minimal time duration, and with 15 observations, we had
a total observation time of roughly half a second.
So, based on that, we were applying this linear regression approach
that you just saw, assuming constant velocity.
We did that in a two-dimensional manner, so we were estimating the
velocity in x direction and independently in y direction, so that we
get a velocity vector that describes in which way the ball is moving.
Of course, this assumption of constant velocity is sometimes violated,
especially if the ball is kicked by a robot in this moment.
When it is kicked, of course, it is immediately changing its velocity
in a very hard way.
Or, for instance, if the ball collides with a robot or an obstacle,
then its moving direction also changes a lot, so at these points in
time.
And, of course, at that point in time, the assumption of constant
velocity is violated.
To deal with that, we had this adaptive observation length.
That means we always observe whether a new measurement fits to the
motion model that we have so far.
And if we observe that one or two times, the deviation between the
observed position and the expected position using the estimated motion
model deviates very much, then we said, okay, here it seems that
something happened that violates our basic assumption.
So, in these cases, we shrink again the number of observations to our
minimum number of three.
And otherwise, we increase the observation time up to the maximum
observation time.
The more observations we have, in general, if the assumption is not
violated, of course, the better the estimate is, the estimated
movement is.
However, if we observe that our basic assumption is violated, we
shrink the observation interval in order to cope with these changes.
Okay, then later on, some teams, some soccer teams started to kick the
ball not only in a flat way on the ground, on the soccer ground, but
they started to kick the ball in such a way, doing some chip kicks.
That caused a lot of problems for us because we didn't have a stereo
vision system on board of our robots at that time.
So, we were not able to determine the three-dimensional position.
However, we were able to detect that the ball is not on the ground by
doing some plausibility analysis.
Later on, we installed a stereo vision system, a binocular camera
vision on one of the robots, especially on the goalkeeper.
And then the goalkeeper was able to determine the three- dimensional
position of the ball.
And then we were able to model also the vertical movement of the ball.
For that purpose, we were assuming that the movement in vertical
direction is an accelerated movement.
And we already knew the acceleration, namely, that is just the gravity
that accelerates the ball.
That is, we know it.
The only thing is that we also had to consider that once the ball
meets the ground, it's bouncing back and not continuing this motion.
So, again, this kind of model checking be done whether or not the ball
bounces at the ground.
And if it bounces, we're assuming that it again moves upwards
afterwards.
So, in total, what we did is a regression approach plus some model
checking in order to cover situations in which the assumptions of
constant or accelerated vertical motion are violated.
So, some example here.
So, this is a test case that were recorded in our lab and that is now
played in a cycle again and again.
So, we see the soccer ground, obviously.
Then you see this cyan triangle.
Where is it?
The cyan triangle here.
That is actually our robot.
Here you see two circles.
One dark red circle, dark red dashed circle.
That is actually the position of the ball that was sensed with the
camera at that point in time.
And then this solid red circle, that is the estimated position of the
ball after having done the regression.
And then we see this line here that is indicating the movement
direction and the velocity that was estimated.
So, the longer the line, the larger the velocity that we estimated.
So, the motion actually starts here at this point.
The first two cycles that you observe there is only this observed ball
because we do not have enough measurements yet to estimate the
velocity.
And then this solid circle occurs and this indicates that we were able
to estimate the velocity of the ball.
And if we look at the direction of this line that indicates the motion
of the ball, we see that it roughly fits to the real motion of the
ball.
Now, here maybe this direction to the left, the estimated motion is a
little bit too much.
It points to the right, but okay, the precision of this camera system
was not that good and so there were some mistakes.
So, actually the ball was rolling over the field at that point in
time.
So, that also means that the velocity was decreasing slowly over time.
Okay, so that was the ball detection and the ball velocity estimation.
We also use that, as I said, to estimate the motion of the robot.
And for the robot motion, the things were a little bit different.
So, we were not assuming straight movement of the robot, but a
movement with constant jaw rate.
That means a movement on a circular trajectory.
And the measurements that we had, again, were the position of the
robot and also the orientation of the robot that the robot had.
And based on that, we were deriving a technique based on regression
with which we could efficiently estimate also the movement of the
robot.
Okay, so far this excursion to robot soccer and so far the discussion
of regression techniques for estimating velocities of objects in the
world.
And now we want to go to a different technique, which is the technique
of Bayesian filters, including Kalman filters and things like that.
They are very much based on probability theory.
And since I guess that most of you do not had a lecture on probability
theory so far, or maybe it is so long ago that you don't remember the
things, I want to start with a very brief repetition of a probability
theory so that we have the basics again and can start based on these
basic ideas of probability theory.
Okay, so it's actually, I must say, not mathematically completely
correct this presentation, but it's a compromise in order to have it
short and intuitive.
Okay, but let's start.
So, first of all, when we talk about probability theory, we have to
talk about random events, so things that might occur or might not
occur randomly.
And if we have such random event, say A, and behind this A there might
be any event that you can imagine, we might assume a probability for
that.
And the probability, intuitively speaking, is something like a
frequency with which we expect that this event occurs.
So, yeah, and what A might be is up to the problem.
A might be in the context of automated driving.
How likely is it that a vehicle ahead of an ego vehicle turns right at
an intersection?
Yeah, could be such an event.
It could be the event it's raining tomorrow, whether or not it's
raining tomorrow.
It's up to random, we don't know in advance, but however, we can make
a kind of guess how likely it is that it's raining tomorrow.
Okay, so that's the probability.
Then, if we have several events, those events might occur at the same
time or not.
Yeah, let's assume we have two events, A and B, and now we can define
something like a joint probability.
Joint probability means a relative frequency, so to say, with which we
expect that those two events occur at the same time.
So, for instance, in automated driving, if we are facing that again,
and we ask whether a vehicle is turning right at the next
intersection, that would be an event, A.
And another event would be that the vehicle ahead of us is activating
the indicator lights, though, whether it's blinking right or not.
Now, these two events, these are two events, and we can somehow make a
guess how likely it is, how often we expect that a vehicle ahead of us
turns right at an intersection and has its indicator lights activated.
Yeah, we see that already in this example that there is a relationship
between these two events, A and B, but, of course, from A does not
fully follow, completely follows that B also holds and vice versa.
So, sometimes vehicles turn right without activating the indicator
lights, sometimes they do.
There is a stochastic relationship.
There is some probability that if A occurs, B also occurs, but it's
not sure.
Then the third kind of probabilities that we need to introduce are so
-called conditional probabilities, also referring to two events, A and
B.
And they say, more or less, they model how often or how likely it is
that event A occurs if in those cases and only in those cases in which
event B occurred.
Yeah, so if we consider again this example with a car that is
approaching an intersection, might turn right, might have its
indicator lights activated, this probability would mean how often does
it happen that a car turns right at the intersection if it is having
its indicator lights being activated.
This should not be confused with the joint probability of A and B.
The joint probability of A and B means for all cars that are
approaching an intersection, how probable, how likely is it, how often
do we observe that the car turns right and has its indicator lights
being activated.
While the conditional probability says, only in those cases, for those
cars which have their indicator lights being activated, how probable,
how often do we observe that such a car is turning right.
Yeah, so the two probabilities are related to each other, the joint
probability and the conditional probability, but they are not the same
and they cannot be exchanged that easily.
Okay, so these are the three type of probabilities that we have to
consider.
So, besides random events, there is something else in probability
theory that is called random variables.
So, often in probability theory, we do not deal just with kind of
crisp events, something like turns right or not, where we can say
either A or not, whether the event occurs or the event does not occur.
But we are often faced with numbers, with numbers that are somehow
randomly chosen, yeah.
So, and these numbers which are somehow randomly chosen are called
random variables.
So, they are two different cases that we consider to be, or that we
distinguish.
The first one are discrete random variables, so random variables which
only might take on integer numbers.
So, for instance, only positive integer numbers, but just say
integers.
And the continuous variables are those which can take any real values,
just real values.
So, for instance, if we say the velocity of a car that we observe,
that's not just an integer.
The car cannot only drive one kilometer per hour, and two, and three,
and four, and five, but it can also drive 4.3 or 4.8 kilometers per
hour.
And therefore, this is a continuous random variable.
While, for instance, things that we can count, yeah, or that can only
take on some integer numbers, like for instance, the question how many
bicycles are parked in front of this lecture hall, that's an integer.
These are discrete random variables.
And the treatment of this discrete and continuous random variables is
a little bit different, and therefore, we have to make this
distinction.
So, now, these random variables are somehow related to random events.
So, what are typical random events which can be defined for random
variables?
So, for discrete random variables, a typical event that we might be
interested in is something like this one here, the event that this
discrete random variable Y takes on a certain integer, now that Y is
equal to 4.
So, we write it here with these box brackets.
That means inside of these box brackets, that's, so to say, a
condition that describes the event, yeah?
Or another event for discrete variables could be that the random
variable Y is inside of a certain interval of numbers.
That's also a typical event.
And another one would be that we have a certain subset of the integers
and ask how, yeah, and define that as an event, that this variable Y
takes on a value within the subset of the integers, yeah?
For each of those events, again, we can define probabilities, yeah?
We can say what is the probability of the event that Y is equal to 4
or that Y is in the set of 2, 3, 7, and 11.
For continuous variables, things are a little bit different.
So, for theoretical reasons, for axiomatic reasons, it's impossible to
define an event that a continuous random variable takes on a certain
value, that A is exactly equal to 2.3 or something like that.
That is nothing, that is no random event, yeah?
We can, for continuous variables, we can only define random events
based on intervals.
We can ask, we can define a random event, for instance, whether X,
variable X, is within a certain interval, for instance, between 7.1
and 8.3.
And we can also, of course, take union of several intervals and ask
how likely is it that the random variable X is between 4.5 and 8.2 or
between 10.3 and 11.2.
We can have also unbounded intervals, like the interval from 15 on to
infinity, that is also possible.
But the main, the important thing is that for continuous random
variables, we can only define random events based on intervals and not
on individual numbers.
That comes from the theoretical basis of probability theory that we
cannot, we can only define random events for continuous variables
based on intervals.
Okay, so now, now once we define these random, these probabilities and
these random events, we might introduce some rules to calculate these
probabilities.
And the first rule is called a is called the marginalization rule.
It relates a simple probability for a single event with a joint
probability of two events, or one event and a random variable.
And it's defined like that for discrete random variables.
So we assume we have an event A, doesn't matter what it is, just an
arbitrary event A, and we have a discrete random variable Y.
So now we might ask, in which way is this probability of A related to
the joint probability of A, and the event that Y, the random variable
Y, takes on a certain value.
And the solution, or this relationship, is shown here.
So once we know all these joint probabilities of the event A, and the
events that the random variable capital Y takes on a certain value,
then we can derive the probability of A, without considering Y, from
these joint probabilities in this way as it is shown on the slide.
We consider all these joint probabilities of event A, and all possible
values of random variable Y, and sum up over all these possibilities.
And by doing that, we get rid of this second random variable Y.
So we can eliminate the influence of a second random variable, or a
certain random variable, by summing up joint probabilities over all
possible values that this random variable might take.
And by doing that, we can get from joint probabilities to
probabilities of a single event, or vice versa.
Once we have a probability for a single event, and we want to
introduce a second random variable Y, we can relate this probability
of A to the joint probabilities of A, and the random variable Y.
Okay, this rule is known as the marginalization rule, and in this
case, this probability on the left hand side, where the random
variable Y has disappeared, is called the marginal distribution of
this joint distribution.
Yeah, marginal... the word marginal comes from the fact that if we
write down all these joint probabilities in a large table, then... and
we calculate the sums in each row, then we get those marginal
probabilities.
So we write them at the margin of a table, and therefore they are
called marginals.
Then the second calculation rule is this one here.
It relates the conditional probability to the marginal and the joint
probability.
And it says that the joint probability of two events A and B is equal
to the conditional probability of A given B times the marginal
probability of B.
And since the order of these events in the joint probability A and B
doesn't matter, it can be exchanged without any change.
This is also equal to the conditional probability of B given A times
the marginal probability of A.
So this is an important rule to get this relationship between joint
probabilities and conditional probabilities, and describes in which
way they are related to each other.
We can also extend this rule if we are faced with three or more random
events.
For instance, if we have three random events A, B, and C, then we can
group those random events into two groups, and then apply this rule
for those groups of random variables.
So for instance, we could say we group those three random events A, B,
and C into one small group with only event A, and one larger group
with events B and C, and then apply this rule.
And then this means this is equal to the probability of A given B and
C times the joint probability of B and C.
We can also group it in a different way.
We can also say, okay, we group the events A and B in one group and
the events C in another group, and then we get the probability of A
and B given C times the probability of C.
And like that, we can calculate with those probabilities.
And finally, the third important rule that is actually derived from
this rule for conditional probabilities is a so-called Bayesian Bayes
theorem.
That is given here, and it's actually... you can derive it directly
from this row here by dividing this row by probability of B.
Then we get this theorem.
It says that the conditional probability of A given B is equal to the
probability of B given A times the marginal probability of A over the
marginal probability of B.
For which case is that interesting?
So let's go back to our example.
We observe a car at an intersection.
One event A is the car is moving right, turning right at the
intersection.
The probability... the event B is it's blinking right, so its
indicator lights are active.
So then this probability means, how likely is it that a car that is
blinking right, that has its indicator lights active, is really
turning right?
And this probability here means, how likely is it that a car blinks
that wants to turn right?
So these are two different probabilities, but they are related to each
other.
But they are not the same.
They are related by the relationship that is given by Bayes' theory.
And sometimes it's easy to determine one of those conditional
probabilities, but very difficult to determine the other kind of
probability.
So if maybe we might be able to state that if a car wants to turn
right, it is activating its indicator lights with a large probability,
say with 90 percent or so, that might be easy.
It is more difficult to conclude about if the car is blinking right,
how likely is it really turning right?
That is what we want to know when we are following this car and have
to interact with it, and want to calculate its future behavior.
Okay, so that's Bayes' theorem.
Again, we can extend it to more than two variables, and then again we
can group those variables and deal with groups of variables, or we can
keep variables here in this condition part without changing them.
So in this case, for instance, we could keep c always in the condition
part of all the probabilities here, and only exchange the role of a
and b.
That's also possible.
Yeah, if you want to prove that, you just have to apply this
definition here, or in the case of three variables, these definitions
here, and then you can prove that this is also true.
Okay, these are the three major, or the three really important rules
for dealing, calculating these probabilities.
Once you know these rules, then you can actually do the whole
probability theory.
So now, the next concept is the concept of stochastic independence.
What's that?
Well, if we observe these two events, car is blinking and car is
turning at an intersection, we easily see that there is some
relationship between these events.
Yeah, if we observe a car blinking, then it's actually very probable
that it's also turning at the intersection, though there is a strong
connection between these two events.
However, if we consider two different events, say the car ahead of us
is turning right at the intersection, that's event A, and event B
would be the event that it's raining tomorrow, we hardly see any
relationship between these events.
If we know that it's raining tomorrow, this doesn't help us at all to
predict whether the car ahead of us will turn right or not at the
intersection.
So they are not coupled, they are independent of each other.
And this idea of being independent, of not having any influence on
each other, is called stochastic independence.
And it's defined in such a way that two events A and B are said to be
stochastically independent if the conditional probability of B given A
is equal to the marginal probability of B.
That means, if we only consider cases in which A, the event A occurs,
and we ask what happens with event B, is it is it met or not, then
this knowledge of event A doesn't help us at all.
If we ignore this knowledge, we cannot say more or less than if we
know whether A is true or not.
So this is stochastic independence.
And of course, many things are assumed to be stochastically
independent.
What happens on the road here in Europe, of course, seems to be, at
least we can assume, that it is independent of what goes on on the
roads somewhere else on earth, for instance.
Or we might also assume that a
decision of one driver and a decision of another driver that is not
directly in the vicinity of the first driver, that those decisions and
those behaviors are also independent of each other.
So independence is really a nice concept because it simplifies all
calculations.
And that's the important thing.
So actually, the definition is, as I said, the conditional probability
of B given A is equal to B, the probability of B, then those events
are said to be stochastically independent.
And this condition is equivalent to those two conditions that are
given here.
We can use the rules for calculating those probabilities and then you
can easily show that this is actually the same.
So now, let's go on.
For discrete variables, we saw that we can identify events,
probability, random events, where we can say, okay, we are interested
in the probability that this discrete random variable takes on a
certain integer number.
And if you like, we can create a large table with all the integers
which this variable can take on and ask for each of these integer
numbers, how probable is it that this random variable takes on this
value.
So we can represent the probabilities for all individual integers
explicitly and by doing that describe the whole probability
distribution.
For continuous random variables, as I said, this is not that easy
because, well, all these individual numbers, the real numbers, they
are uncountable.
So we cannot make such a table.
It's impossible.
And we have seen or I've said that we can only define probabilities
for intervals, that the variable, the continuous variable, is located
inside of a certain interval between two numbers.
Now the question is, how can we represent these probabilities
efficiently?
So there are, of course, also an uncountable amount of intervals of
the real axis.
So we cannot make a table and for each interval write down its
probability.
So how can we represent that efficiently?
And the solution is to introduce something, a technique that is called
probability density functions or for short PDF functions.
So probability density function.
That's a function that is non-negative for all values so that it can
be zero, it can take on real positive numbers but never negative
numbers.
And we need that the integral from minus infinity to plus infinity of
this probability density function is equal to one.
That comes from the axioms of probability theory.
And with such a probability density function, we can represent the
probability of intervals, so intervals like that, the probability that
the random variable is located between two numbers a and b.
And by this definition, so if we use a probability density function,
we said that the probability of x being located between a and b is
equal to the integral of this probability density function ranging
from a to b.
So we use this representation to represent the probability
distribution, we say probability distribution of such a continuous
random variable.
So Px in this case is the probability density function for random
variable capital X evaluated at a certain position.
So the probability density function is not a probability, so it's not
something that we can directly interpret as probability.
And it can also be larger than one, different than probabilities which
cannot be larger than one.
But this probability density function can become larger than one, it
can become very large.
However, it is somehow, say, somehow proportional to the probability
or approximately proportional to the probability that the random
variable takes on a value in the vicinity of the special value at
which we evaluate the probability density function.
Okay, that's a very important concept.
So for this probability density functions, we can do actually the same
calculations as we did for discrete probabilities, for probabilities
of discrete random variables.
But everywhere where we had probabilities so far, now we have to use
probability density functions.
And everywhere where we had summation, we have to replace it by
integration.
Yeah, that means this marginalization rule that we introduced for
discrete random variables can be rewritten for continuous random
variables in the way that is shown here on the slide.
So we see that here on the right hand side, we have a probability
density function for the joint, for the pair of continuous random
variables X and Y.
This is defined in actually the same way as basic probability density
functions, just for a pair of numbers.
And we can relate this probability density function of this pair of
random variables to the marginal probability density function only for
variable capital X by integrating out the influence of random variable
Y, by taking the integral of the joint probability density function
over the interval from minus infinity to plus infinity.
The next step, the conditional probabilities, the same applies as for
discrete random variables.
We just replace the probability term by the probability density here
and the same, but the same rules actually apply.
And for Bayes' rule, the same applies as well.
We exchange probabilities by probability density functions and still
the theorem holds.
So now, these probability density functions.
Of course, all functions which are non-negative and which, for which
the integral from minus infinity to infinity is equal to one, can be
used as probability density functions.
And of course, which one is suitable to represent the real
distribution of a certain random variable depends on the random
variable, yeah?
So, and there are...
yeah.
However, some choices of probability density functions have become
very successful and very powerful and very useful to represent things
in natural life.
And one of those, and maybe the most popular one, is a so-called
Gaussian or normal distribution.
That's a distribution that is in a certain way very powerful, can be
used in very many circumstances, and has some very nice properties.
So, let's introduce it.
This density... the probability...
this Gaussian distribution is... the density function is given here
for the one-dimensional case of a single random variable.
It's defined like that.
So, actually, oops, it's the exponential function of minus x squared.
And then we have two parameters, mu and sigma, with which we can
control a little bit the shape of this function.
For the basic choice of mu being equal to zero and sigma being equal
to one, the plot of this function, the graph, is given here.
So, symmetric around zero, taking its maximum at zero, being all
positive, and asymptotically tending to zero for very large and very
small values x.
Differentiable, etc.
So, with the parameter mu, we can shift this curve a little bit to the
left or the right.
So, mu is actually the parameter that defines the center of symmetry
of this shape.
So, that means, for the basic choice, mu equal to zero, the center of
symmetry is at the position zero.
If we select mu equal to two, then the whole curve is shifted by two
to the right.
If we choose mu to be minus five, then the whole curve is shifted by
minus five to the left.
And the role of sigma is to control, actually, the width of this bell
-shaped curve.
The larger sigma is, the wider this bell-shaped curve becomes.
The smaller sigma is, the smaller and more narrow this bell-shaped
curve becomes, and the higher the peak in the center becomes.
The larger sigma is, the smaller this peak is, the larger, the smaller
sigma is, the larger this maximum becomes.
We can extend this Gaussian distribution also to the case of several
random variables.
When we have several random variables and we want to describe the
joint density function for several random variables, we can extend
that.
Let's assume that we write those random variables into this vector x
here, and then we can define a probability density function like this
one here.
Yeah, we see that it's actually for the one-dimensional case, so if we
assume that x is a one-dimensional vector, this becomes the same as
this equation here.
Yeah, looks like that.
Again, we have this parameter mu, which controls the center of
symmetry, where it is.
So in the basic case, it's the zero vector, then the center of
symmetry is at zero, but we can shift it to any place that we like.
And yeah, here this graph shows a plot of this function in the two
-dimensional case, so with the center being at zero and this matrix
sigma being the identity matrix.
So what is the role of this matrix sigma?
So because it refers to the small sigma here somehow, it controls how
wide this curve is, whether it's very peaky or very wide, and it
controls...
and this peakiness or this shape can change in different directions.
So this density function might be very peaky in some directions, and
it might be very wide in other directions at the same time.
So we can control a little bit this kind of wideness of this function
in different direction in this space here, in the space.
And this is given with this so-called covariance matrix sigma.
This covariance matrix sigma has to be a matrix that is symmetric and
that is positive-definite, that means all eigenvalues must be larger
than zero, and all those matrices for which these properties hold can
be used as covariance matrices.
And the entries in the diagonal of this matrix, they control the
wideness, so to say, in the different directions of the coordinate
system, and the non-diagonal elements somehow turn this curve a little
bit.
Okay, so, and of course, Gaussian distributions will be the ones that
we need throughout the lecture, and with which we will calculate.
So finally, let's summarize our basic repetition of probability theory
with a little bit of notation stuff.
So if we want to be fully correct in our notation, and we are faced
with a random variable, say a discrete random variable x, and we want
to express the event that x, this random variable x, takes on a
certain value, which is given here with small x, then we would need to
write it like that.
P, capital P, so the probability of the event that the random variable
capital X takes on the value small x.
That's the full correct, mathematically correct notation.
And for a probability density function, so if capital X is a
continuous random variable, then we would say this is the probability
density function of the variable capital X, and we evaluate it at the
position which is given by small x.
This is the full correct notation.
However, if we use this notation, we write formulas that are very,
very long, and therefore many mathematicians prefer to have a short
kind of writing, a shorter notation that looks like that.
Sorry, it looks like that.
P of capital X, and small p of capital X, instead of this and that
notation.
This might be confusing sometimes.
Yeah, this might sometimes be really confusing.
If you are confused by that, rewrite everything in this basic
notation.
Yeah, however, you will easily see that the terms that we get become
very large, and therefore, I will also use the simplified notation if
it's not too confusing.
But if you face such a term, and you think, I don't understand it, I'm
too much confused, first rewrite it to the long form to understand it.
And another thing is this kind of notation.
You might write capital X tilde, and then we get this n script, n of
mu and sigma.
This is a notation to write that we assume that this random variable
capital X is distributed according to a Gaussian distribution.
That means, we say that with this notation, we state that the
probability density function of this random variable X is a Gaussian
probability density function with these parameters mu and sigma, which
are given here.
Yeah, so this is the notation.
So this says, we assume that the random variable X is distributed
according to a Gaussian distribution.
That means, that we have to use this Gaussian probability density
function to describe the probabilities of this random variable.
Okay, so far, the repetition of the very brief and repetition of the
basics of probability theory.
Now, let's use that to develop a model, which is very useful to do
this kind of tracking of objects, estimating motion of objects over
time, integrating measurements in an incremental way.
So the main idea that we need for this is that we want to understand
the world or the part of the world in which we want to model as a
system.
And the system is assumed to have a state.
And we assume that this state contains all information that describe
in which the system behaves.
Yeah, so just knowing the state of a system should be sufficient to
understand or to be able to describe how the system behaves.
Yeah, so... and this means that we can describe the changes of the
system over time by means of describing the changes of its state over
time.
So if we know the state of the system, we know everything.
Yeah, so that's the basic thing, idea behind it.
So let's go back to our standard example, a car that is moving with
constant velocity.
If you want to describe this car that is moving with constant
velocity, it is fully sufficient to know its position and its velocity
at a certain point in time.
If you know its position and the velocity, then these two pieces of
information are completely sufficient to describe the behavior of this
car, to make predictions.
Where will it be in 10 seconds?
If I know where it is at the moment, and if I know how fast it is, I
can easily predict where it will be.
Maybe up to some randomness that still might occur, but in general,
I'm able to do this prediction.
I'm also able to describe where has this vehicle been 10 seconds ago,
something like that.
So the behavior, at least the relevant behavior of this vehicle, is
fully described by these state variables.
If the vehicle is moving with constant velocity, if the vehicle is not
moving with constant velocity, if this assumption is not fulfilled,
then of course knowing just the position and the velocity is
definitely not sufficient to describe the behavior of the vehicle.
Then we are not able to predict where it will be in 10 seconds, if we
don't know in which way it is accelerating.
So that means then maybe we would need in such a case to add the
acceleration of the vehicle as an additional variable to this state
vector, to the state information.
And if the car is not moving on a straight road, but maybe on a curved
road, maybe we also need to know the steering angle of the vehicle or
the draw rate of the vehicle in order to describe in which way it is
turning.
So it depends on the system that we observe, on the assumptions that
we can make in which way it behaves, which pieces of information must
be added to this state information.
But we assume that it is possible to define it.
We assume that it is possible to select a certain number of pieces of
information, a finite number of pieces of information, to add it to a
state vector or to assemble of pieces of information.
And then with this knowledge, we can fully describe the behavior of
the system.
Okay, so based on that, then we can maybe create a transition model
and say, okay, based on these pieces of information, we can predict
where will the vehicle be in a certain number of seconds.
How will it behave?
We go back to that later.
Okay, we also assume that we can observe the system.
For instance, the car that is moving, we observe it with a sensor.
So we also need to describe in a certain abstract way how this
measurement works.
So in this case, we assume that we can make a measurement, we can
measure something, and this measurement depends on the state of the
system.
And we assume that there is a function that explains in which
measurement we can achieve if the system is in a certain state.
So we assume that the measurement, which is now written here
throughout the slides with the letter Z, that it is created by mapping
the state of the system at the present point in time, that is now
denoted with S for state, onto the measurement.
And maybe we have some measurement noise.
That's the second part here that is written.
That means there's just some random influence that is affecting the
measurement.
So we assume there is, first of all, there is a clear, well-defined
relationship that explains how the measurement is related to the
present state of the object of the system.
And there is some additional noise, some additional random influence
that occurs, that is somehow disturbing the measurement.
So that we don't get the real measurement value set, but that we get a
randomly disturbed measurement.
So for a car that we observe with the camera, we might observe, for
instance, the position of the car.
And then we say, okay, Z of t, the measurement that we get is equal to
X of t, one of the state variables, plus some measurement noise, which
we could in this case even rewrite into this matrix form that it is
something like a row vector 1, 0 times this column vector that
contains all the state variables plus some noise.
Okay, important for us is what we can observe, of course, is Z of t.
Z of t is what we can observe, that's what we can measure, that is
what we get.
And of course what we want to determine is the state of the system,
which contains, for instance, the velocity of the car.
This is what we aim to estimate, what we want to get.
We don't assume that we can observe that directly, we don't assume
that we can observe all the state variables.
Maybe that's hidden, so maybe we don't have a sensor that can sense
the velocity of the vehicle.
But of course, based on our measurements, we want to draw conclusions
about the state of the system and estimate the current state of the
system.
So for doing that, let's introduce some stochastic model, a so-called
hidden Markov model.
What is a hidden Markov model?
A hidden Markov model is a time discrete stochastic state transition
system.
Its observation and its successor state depend entirely on its present
state and do not depend on previous states or observations.
Okay, let's go through the definition step by step.
So it's a state transitioning system.
What does it mean?
We assume the system has a certain state at a certain point in time
and then it makes a transition to another state for the next point in
time.
The definition says also that it's a time discrete state transition
system.
That means we are not considering time as a continuum, but we are
considering time only up to a certain discrete sequence of points in
time.
So we assume, for instance, that we consider the state of the system
only for points in time which are spaced by, say, one second.
We're interested in the state of the system now, one second later, two
seconds later, three seconds later, and so on.
But we are not considering what happens between second zero and second
one.
We only consider this integer positions in time.
So that is time discrete.
Then stochastic means, well, there's some randomness in.
So the state transition, the transition from one state to another
state, is not fully deterministic.
It's not fully explained by a transition function, but there is also
some randomness that is affecting this state transition.
That means if we know the state at the present point in time, we
cannot completely determine what will be the successor state, but we
can only determine that up to a probability distribution, because
there is some randomness that is affecting this state transition.
Okay, its observation and its successor state depend entirely on its
present state and do not depend on previous states or observations.
So what does it say?
Okay, so its successor state depends entirely on its present state and
not on its previous state observations.
This means once we know the present state, we know everything that we
need to predict what's going on in future, to explain the behavior of
the system in future.
We can forget about the past.
We do not need to know how, in which way we entered a certain state,
the system entered a certain state, but knowing the state is
sufficient to describe its behavior.
So think of, you want to drive to a certain place, yeah, you're
driving on the road, you arrive at a certain place,
not yet at your final destination, and you ask yourself, how do I get
from this place to my final destination?
Then it's definitely, it doesn't matter at all how you manage to come
to this place, it only depends on where you are to plan your future
path to your goal.
And it doesn't matter whether you went there in a straight manner or
not straight manner, that's completely irrelevant for describing how
you can arrive at your final destination.
So that is meant with, it depends entirely on its present state and
not on the past.
And also the observation that is related to the state only depends on
the present state and not on the past.
That means when we measure the position of a car with a camera, we
assume that this measurement is completely independent of the fact
from where the car came.
Yeah, or whether it was accelerating or decelerating in past, that's
completely irrelevant for this measurement.
Okay, so that is an assumption that we have to make, and if these
assumptions hold, then we are faced with something that is called a
hidden Markov model in probability theory.
Um, this definition is summarized in these two equations here.
Now, these two equations actually describe this independence
assumption.
They state that, well, the probability of a certain successful state,
knowing the present state, knowing the present observation, knowing
the previous state, the previous observation, and so on, up to the
very first state, can be simplified and is equal to just the
probability of the successor state given the present state.
That means if we want to predict what's going on in the future, if we
want to say, okay, what, in which way will the, will the system behave
in future, only we, what we need to know is the present state.
And we can forget all the past states, we can forget all the past
observations, they don't have any influence on the future behavior.
As well for the observation, now the probability to make a certain
observation at a certain, given, knowing the present state of the
system, is completely sufficient.
So, knowing the present state is completely sufficient.
If we know previous observations and previous state, this doesn't help
us to explain better the present observation as long as we know the
present state.
So, again, we can forget about all the past because the past doesn't
have influence on the future, if we know the present state of the
system.
So, the present state contains all the relevant information that is
necessary to describe the behavior of the system and to describe the
measurement process.
So, now, if we assume that we can model a system as a hidden Markov
model, then what we want to get, or what we usually aim for, is that
we want to get an idea of what is the present state of the system.
So, we assume we are observing the system several points in time.
We make several measurements, from point in time 1 to point in time t,
in this case.
So, having observed the whole sequence of observations, set 1 to set
t, we want to know, well, what is the present state of the system.
So, we want to calculate a probability or a probability distribution
of the present state.
So, we want to know, well, we made some observations of the position
of the car, what is its present velocity, what is its present state,
for instance.
A variant of this question is given here.
Namely, we made the certain sequence of observations, and we are not
interested in what is the present state of the system, but we want to
know what is the future state of the system, for the next point in
time.
If we observed up to now what was happening up to now, we want to
know, well, what do we have to expect in future from the system?
How will it behave?
What will be the next state?
Okay, so, let's derive that.
Okay, for that purpose, I present to you these formulas, and we will
go through all these formulas in detail.
Let's start, where do we start?
Here.
Hey, no, let's derive them step by step.
Okay, let's start here.
So, the probability of St given the sequence of observations up to
that point in time, what is it?
We apply first the Bayesian rule, Bayes rule, and we exchange the role
of St and Zt.
Yeah, this is done here.
So, just St and Zt are exchanged, yes, and Z1 up to Zt minus 1 is
preserved in the condition part.
With Bayes rules, this means this is equal to this equation here, to
this term here.
Yeah, okay, and now we simplify things.
We look at the denominator, and we see that the denominator only
contains observations.
The observations from point in time 1 up to the present point in time
t.
We assume that we know those, we have observed them, so they don't
change, they don't vary, they are fixed.
And that means that this denominator is just a constant.
It's independent of St. It's just a constant.
And that means we can say this term here is proportional to its
numerator.
Furthermore, we assume that the system is a hidden Markov model.
And since it is a hidden Markov model, we know that if we know the
present state, we know everything that is necessary to describe the
probability distribution over the observations.
And all the past observations do not help us to make a better
prediction of the observation or to make a better, to know more about
the present observation.
That is actually this independent assumption that comes from the
hidden Markov model.
That means we can simplify this term and leave away those old
observations.
They are not helpful.
We don't need them because we assume that we are in a hidden Markov
model.
So this means this simplifies and becomes this term here.
The second factor here is preserved.
It's just the same.
So that's the first equation.
The second equation starts here.
So that's about this future state that we, about which we want to say
something once we are given the sequence of observations up to point
in time t.
For that purpose, we use the marginalization rule that we've
introduced.
And we add another additional random variable to this probability,
namely the random variable St, which we need as a kind of linking
element to later on simplify these equations.
So we add this additional random variable St here.
And we know if we add it at that point due to the marginalization
rule, we have to sum up over all possible values that this random
variable St might take.
Okay, so that's actually the marginalization rule.
Now we use the rule or the definition of conditional probabilities and
reformulate that.
So actually what we have here is a joint probability that is
conditioned on some other variables.
So now we use the definition of conditional distributions to change
this joint probability into a conditional probability.
By pushing, so to say, this St variable into the condition part.
Now then we get this condition probability and we need the correction
factor, namely the probability of S of t, this marginal, so to say, of
S and t.
However, since we kept all these old observations here in the
condition part, we also have to have it here.
So now we again use the knowledge that we are facing a hidden Markov
model.
And in a hidden Markov model, the state transition from a known state
St to a future state St plus one is independent, as we defined, it is
independent from all the observations.
That means we can leave those observations away and simplify this to
this simpler probability.
Yeah, so no magic inside of these calculations, just applying the
basic calculation rules for probabilities and using the fact that we
are facing a hidden Markov model, that we are assuming that we are
facing a hidden Markov model, in which the present observation only
depends on the present state and not on past states and observations,
and in which the present, the transition from the present state to the
future state only depends on the present state and not on past states
and observations.
Okay, now we can have a look at what we see.
So this is actually just the state transition probability that
describes in which way the states are changing over time.
This term here that we need here is actually something that we get as
a result from this calculation here.
So that's actually the same term that we can see here.
Furthermore, what
we see is that this term here is just the simple probability of an
observation.
It just says how likely is a certain observation if we are in a
certain state.
And we can also see that this probability is something that is
calculated here, but for the previous point in time.
So we see this has the same structure as this term.
And the structure is the same, the probability of the state at a
certain point in time given all the observations up to that point in
time.
And here it's the same kind of probability, but just for one point in
time later.
That means we get some recurrent relationship here.
If we want to calculate the output, if we want to calculate this term
here, we need these state transition probabilities and we need the
result of the calculation of the upper equation here.
So we need, so to say, if we interpret that as a kind of calculation
where we get as a result the left-hand side, we need that result as
input to the equation here.
And if we want to evaluate this term, what we need is the probability
of a certain observation and the result of a calculation which we did
one step before by evaluating the equation at the bottom of the slide.
So we get a kind of recurrent or recursive, better to say, recursive
calculation over time.
And this interpreted as an algorithm looks like that.
So we have two steps.
One is called the prediction step and this prediction step actually
implements this lower equation here.
So it takes as input these two things and it calculates this thing.
Yeah?
What does the sum sign,
this one here?
Well, we sum over all possible values that st can take.
Okay,
this is for the discrete state, for the discrete case.
Yeah?
Let's assume at this point that we're dealing with discrete random
variables.
The same applies for continuous random variables.
Then we replace the sum by the integral and the probabilities by the
probability density functions.
Okay.
But let's first assume that we have discrete random variables.
Yeah?
So we sum up over all possible values of a discrete random variable
st.
Okay, so that's this prediction step.
It calculates the probability distribution over the future states.
So we assume that we observed, we made the measurements up to point in
time t and we want to ask, well, what is the expected state at the
next point in time?
Yeah?
That's a prediction step, therefore called prediction step.
The other step is called innovation or correction step.
That's actually the step that is shown here at the upper equation here
that implements this equation.
And it's calculating, so to say, well, we observed all measurements up
to now and now we want to know for this point in time, what is the
present state of the system?
And what we do, what is the, so to say, the difference, we know also
the present observation.
In this prediction step, we, so to say, the knowledge, the
measurements that we made do not cover the point in time for which we
know the state of the system, but they end up one point in time
before.
For the innovation step, we assume that we made all the observations
up to that point in time.
So that also means that we integrate, so to say, the last observation
in our reasoning.
So, and we execute these two steps one after the other.
Yeah?
Every time we make a new observation, we make one innovation step,
then we get these these kind of probabilities, and then we make a
prediction step to get to guess what will be the future state of the
system one point in time later.
Then we wait for a new measurement.
Once we get the new measurement, we apply this new measurement in the
innovation step.
We go from this side to this side.
Of course, what we also need is some initialization.
So, yeah, at the beginning we need to start at some point, and well,
it depends a little bit on the application whether we want to start
here on the right-hand side or whether we want to start at the left
-hand side.
For some applications, it might be that we know really well the
initial conditions of the system, that we really know very well what
is the initial state.
Then we start here on the left-hand side.
If we don't know very well what is the... yeah, sometimes in other
cases, we might start here on the right-hand side.
That's up to the application.
So, that means the whole process looks like that.
So, we start with an initial guess, say, with an initial guess of for
the first state, an initial probability distribution for the first
state.
Then we do an innovation step to integrate the first measurement.
Then we make a prediction step to guess the probability distribution
for the second point in time, knowing just the first measurement.
Then we integrate the second measurement in an innovation step, and so
on, and so on.
And as I said, we might also start with a prediction step if we like,
if that helps more than starting with an innovation step.
Okay, that's it for today.
Yeah, this is both possible.
That's it for today.
Yeah, we continue next week.