WEBVTT
00:00:04.049 --> 00:00:16.498
Okay so um last time we finished the chapter on optical floor
and image base tracking. And today we want to continue
00:00:16.498 --> 00:00:24.879
with Walt, again tracking. But now we don't want to track
objects inside of an image um representing the position in
00:00:24.879 --> 00:00:33.159
pixel coordinates. But we want to track these objects in the
real world in three D coordinates in the real world.
00:00:33.159 --> 00:00:43.478
And we want to be able to not only say this object that we
see once in one image at that position is now visible at
00:00:43.478 --> 00:00:53.774
another position in the next image. But we also want to be
able to estimate their motion while we want to be able to
00:00:53.774 --> 00:01:01.442
estimate with with velocity or acceleration. Objects are
moving into which direction, and things like that. So now we
00:01:01.442 --> 00:01:09.664
leave this world of two dimensional images, and we enter the
area of three dimensions of the three dimensional world. So
00:01:09.664 --> 00:01:17.759
everything that comes now within this chapter, and also within
Chapternum and refers to three D world courting it.
00:01:17.780 --> 00:01:26.609
So we assume that we have detected objects in the image with
a suitable detection algorithm. We have used a system
00:01:26.609 --> 00:01:33.540
so that we can determine the position of this object in
the three dimensional world. And based on these three
00:01:33.540 --> 00:01:41.178
dimensional coordinates, we want to track these objects. Okay,
literature and references for this chapter? well, we will
00:01:41.178 --> 00:01:51.065
introduce one technique called the filter. Here is a
tutorial that might be useful for you to understand this
00:01:51.065 --> 00:02:00.543
common filter then mhm this paper here is an original
paper introducing something technique that is called the
00:02:00.543 --> 00:02:09.539
unsented Carmen filter. And we touch this technique as well.
So if you want to see the background of this technique.
00:02:09.539 --> 00:02:18.649
Look at that paper, then the robotics book of . And Fox
contains three chapters on these tracking techniques. So
00:02:18.649 --> 00:02:25.719
chapter number two to four. Then there is an older book applied
optimal estimation. It also introduces a common filter.
00:02:25.729 --> 00:02:36.128
So that is the book where I learned about the common filter.
If you were interested, you might look at this book and
00:02:36.128 --> 00:02:47.660
this one here is a larger book about general and topics of
tracking objects. And it contains much more than what we
00:02:47.660 --> 00:02:55.703
introduce in the lecture. So this is more further reading
for those who are more interested in this topic and want to
00:02:55.703 --> 00:03:03.117
get more information about it. However, it, is already
seventeen years old. So @unoise@ % um yeah, @unoise@ okay
00:03:03.117 --> 00:03:13.177
so, let us start with one of the simplest ways to do that.
Yeah, it is often forgotten that this is also an option, but
00:03:13.177 --> 00:03:20.639
we should discuss it because it is not. It is often very
useful, namely emotion, estimation of objects by regression.
00:03:20.650 --> 00:03:27.560
What do we mean with that? so we observe an object at
different points in time. That means, for instance, we have a
00:03:27.560 --> 00:03:33.588
camera image. We detect the object in the camera image, we
calculate its position in the three dimensional world. So
00:03:33.588 --> 00:03:41.301
that means for each point in time at which we have an image
we also have the position of the object and what
00:03:41.301 --> 00:03:49.980
we want is we want to estimate the position and the velocity
of the object. Okay, so simple example we wanted to
00:03:49.980 --> 00:04:00.585
estimate the motion of this car, or the motion profile of
this car. This car is waiting in front of a red traffic
00:04:00.585 --> 00:04:09.373
lights. So it is not moving at all. And uh, within each
image, we somehow segment the scar, and then we determine its
00:04:09.373 --> 00:04:19.399
position. And due to some imposition in the whole image of
processing algorithms and noise, and the camera images and so
00:04:19.399 --> 00:04:27.199
on. The position that we measure in the diaries form image
to image. So it might happen that at the first image, we
00:04:27.199 --> 00:04:34.169
measure a position here in longitudinal direction of minus
upon three meters, and then in the next one, over point one
00:04:34.169 --> 00:04:41.712
metres, and the next one is minus all point four meters. So
we assume that the car is really waiting in front of the
00:04:41.712 --> 00:04:50.496
traffic lights. That means that it is not moving. So we want
to say, okay, what is the real position of the car. These
00:04:50.496 --> 00:04:57.642
are the sense positions, which are somehow affected by
imposition and noise and disturbance disturbances in the whole
00:04:57.642 --> 00:05:07.139
sense of processing chain. So what would you do to get a best
estimate of the position when you have these measurements.
00:05:07.149 --> 00:05:17.701
I resemble everyone would do it. I guess what would you
do? I hope everyone would say some do something like ever
00:05:17.701 --> 00:05:26.022
reaching these positions. They are calculating just the
average of these positions. Now that yields another position
00:05:26.022 --> 00:05:37.474
estimate, say and this is the best position
estimate that we can get if we assume some properties of the
00:05:37.474 --> 00:05:46.095
imposition that occur in this measurement and image
processing process. Now, if we assume that this, this, this
00:05:46.095 --> 00:05:53.332
imposition that occurs follows some statistical properties
@unoise@ then there is a guarantee that this estimate is
00:05:53.332 --> 00:06:03.549
averaging of the positions is the best best thing that
we can do @unoise@ to get an a position value that is, and
00:06:03.549 --> 00:06:12.704
better than any other position estimate that we can get
at least one average. We can also describe under these
00:06:12.704 --> 00:06:22.478
assumptions, how how certain this position is. That means
how much uncertainty exists in this position. And this is
00:06:22.478 --> 00:06:29.985
typically um described either by an interval so called
confidence interval. That says okay, with the probability of,
00:06:29.985 --> 00:06:38.523
say, ninety five per cent, the true position of the car
is within a certain interval that would be a confidence
00:06:38.523 --> 00:06:46.654
interval, or another way to express this uncertainty is to
pride provide the variants of this estimate that is
00:06:46.654 --> 00:06:55.256
provided here could be calculated like that. That is a measure
of, say, imposition. The larger this value is, the more
00:06:55.256 --> 00:07:05.500
imprecise is a position that means the more uncertain it is
@unoise@ okay. So, this is a basic step and is actually a
00:07:05.500 --> 00:07:15.340
simplistic step. And I think for this case, no one would be
surprised if we use this er ever rich as the best estimate.
00:07:15.350 --> 00:07:23.187
Now, let us extend this task a little bit and say," Now we
are observing this Cora, which is moving on a highway with
00:07:23.187 --> 00:07:30.993
more or less constant velocity. So again, we observe it over
time along the road. And we have several points in time at
00:07:30.993 --> 00:07:39.002
which we observe it and say," Now we get these measurements.
So this is a point in time where we have taken a
00:07:39.002 --> 00:07:47.481
measurement. And these are the positions in longitudinal
direction. So now we would say, Ok, What is how can we
00:07:47.481 --> 00:07:57.157
describe the movement of this vehicle, of this object? and
how can we estimate its motion? Hm, okay. The idea is
00:07:57.157 --> 00:08:05.748
actually an extension of the idea that we had before, of course,
now ever reaching these positions does not really help,
00:08:05.748 --> 00:08:14.216
because the vehicle is moving over tile over time. So just
ever, reaching the positions would not help. But instead of
00:08:14.216 --> 00:08:23.161
that, we could go another way. We could say, Ok, we is. We
make an assumption about how this vehicle moves. If you say
00:08:23.161 --> 00:08:31.502
the vehicle moves Wisconsin velocity in the same direction,
then we could argue that we can describe the position of
00:08:31.502 --> 00:08:40.678
this object over time, or X, depending on time, by a certain
image of position, plus the velocity of the vehicle times
00:08:40.678 --> 00:08:51.341
the time now. So this comes from just the basic physical
motion equations for a movement. Wisconsin velocity, the
00:08:51.341 --> 00:09:00.888
measurements that we get here must follow this equation, plus
some additional measurement noise now, which occurs here
00:09:00.888 --> 00:09:10.342
in these measurements. So this is so to say, an assumption
that we might take how this vehicle um moves. Now we could
00:09:10.342 --> 00:09:18.000
enter these numbers here in this equation. So we measured the
position that would be the left inside of this equation.
00:09:18.009 --> 00:09:28.339
And we are given the point in time. That means this value for
tea. % um is something that we could add that means for in
00:09:28.339 --> 00:09:37.459
this case, we would get four equations, and we have total two
unknown variables. X, zero the image position, and
00:09:37.459 --> 00:09:46.950
we the velocity of the of the vehicle so four equations
with two unknown variables in the best case, this system
00:09:46.950 --> 00:09:56.135
of linear equation has a unique solution. In the worst case,
it doesn't have any solution. And the reason another in
00:09:56.135 --> 00:10:04.980
practice, it doesn't have a solution. Why? because there
is this unknown noise term. So it is not exact an exact
00:10:04.980 --> 00:10:13.707
equality here, but it is only an approximate equality. So we
have to deal with this noise. So we could say there is an
00:10:13.707 --> 00:10:23.281
additional noise term in each equation. And now we could
argue for which values of X, Zero and V do these additional
00:10:23.281 --> 00:10:33.818
noise terms become as small as possible @unoise@ so. That means
what we would do is we would isolate the noise term here
00:10:33.818 --> 00:10:45.009
I, for instance, subtracting this term. Xero Plus, we times
tea from both sides of the equation. Then we get X of tea.
00:10:45.019 --> 00:10:54.798
Mine is external. Minor sweetens. Tea is equal to the noise
term. So now we want to minimize the noise in all equations
00:10:54.798 --> 00:11:03.949
in parallel. This can be done by minimizing this queer, the
squared, the sum of the great noise terms. And then we get a
00:11:03.949 --> 00:11:14.853
minimization problem that looks like that. So we want to
minimize this which are equal to the to the noise term in
00:11:14.853 --> 00:11:23.909
each of these equations that we get. And so we want to
minimize the squared noise term, the sum of the square noise
00:11:23.909 --> 00:11:31.480
terms over all the equations that we get from these measurements.
And we want to minimize it with spectacle. It x zero.
00:11:31.490 --> 00:11:41.023
And we now, this is a function that should be minimized % um
to minimize this function, we can go on as we have learned
00:11:41.023 --> 00:11:49.441
it in the last class. Namely, we take the derivatives of this
term here @unoise@ with respect to the unknown variables
00:11:49.441 --> 00:11:57.647
Xero and V, and then zero. These partial derivatives. By
doing that, we get a system of linear equations with two
00:11:57.647 --> 00:12:07.663
equations and two unknown barriers and we now. So this
yields a method that is called linear recreation. So the
00:12:07.663 --> 00:12:18.115
the resulting Linea system of linear equations looks like that.
So on the left inside, we have this matrix that contains
00:12:18.115 --> 00:12:26.138
just the points in time at which the measurements were taken.
And we have this vector here on the right hand side, which
00:12:26.138 --> 00:12:33.212
contains the positions at which the objects have been detected,
and the product of times and objects. And here we have
00:12:33.212 --> 00:12:43.281
the vector of unknown variables. Now, if this matrix is
invertible, so if it has rank to full rank, then we can get a
00:12:43.281 --> 00:12:52.252
unique solution of this system of linear equations. And
this matrix has rank too. As soon as we have at least two
00:12:52.252 --> 00:13:01.374
measurements taken at different points in time. Well, and
that is a good message. So as long as, as soon as we have two
00:13:01.374 --> 00:13:08.155
measurements, we can calculate these terms. They need a
position and the velocity of the vehicle. And based on that, we
00:13:08.155 --> 00:13:16.982
can also make predictions. Where will the vehicle be at a
certain point in future. Now, @unoise@ okay. So, if you are
00:13:16.982 --> 00:13:24.915
interested in the uncertainty so up to now we were on
the providing the system of linear equations, and from which
00:13:24.915 --> 00:13:33.450
we get the best estimate of ex zero. And we @unoise@ under
some assumptions um assumptions about the noisy
00:13:33.450 --> 00:13:42.640
ah in these in these measurement processes @unoise@
um. What we get here is the best estimate of external B.
00:13:42.649 --> 00:13:51.503
However, we might also be interested in the uncertainty so
well. The best estimate, best estimate for the velocity might
00:13:51.503 --> 00:13:59.020
be something like, say, thirty kilometers power. But of course,
it makes a difference whether we are very sure are about
00:13:59.020 --> 00:14:06.041
the velocity and can say, okay, it is definitely between
twenty nine and thirty one kilometer per hours, or whether we
00:14:06.041 --> 00:14:12.410
are very unsure and can only say," Okay, somewhere between
ten kilometer powers and fifty kilometer per hours. That
00:14:12.410 --> 00:14:21.213
makes a difference. So if you are interested again, about
these measures of uncertainty, it is possible to derive also
00:14:21.213 --> 00:14:29.749
and confidence a divorce. For those terms here, if you
like, I don't provide this. The formula here @unoise@ But.
00:14:29.759 --> 00:14:37.923
Ah it, is possible Ah. With a little effort @unoise@ ah,
similar to the case where we ah had a a non moving vehicle
00:14:37.923 --> 00:14:45.331
@unoise@ where we could also derive @unoise@ these variances
for these terms here @unoise@ okay. So, that would be the
00:14:45.331 --> 00:14:53.269
second possibility. We assume the vehicle is moving Wisconsin
velocity that is useful for many in many situations, but
00:14:53.269 --> 00:15:02.602
not in all. So it might also happen like that. So the vehicle
still is waiting at the traffic lights. They go to green,
00:15:02.602 --> 00:15:10.936
and under the vehicle is accelerating. Of course, if we assume
constant velocity, while the vehicle is accelerating like
00:15:10.936 --> 00:15:20.352
that. Our assumptions are not met, and the estimates that we
would get would not be valid. It would not fit to the real
00:15:20.352 --> 00:15:28.329
scenario. So let us discuss how we could model this scenario
of a vehicle that has a considerable acceleration that
00:15:28.329 --> 00:15:36.862
differs from zero okay, what could we do? we could
follow the same way as we are. We are arguing before. But now
00:15:36.862 --> 00:15:45.382
we need another motion model. We need another model that
describes in which way the vehicle moves. And if you go back to
00:15:45.382 --> 00:15:53.360
the basic physical motion equations and assume that the vehicle
is moving with constant acceleration. Then we get this
00:15:53.360 --> 00:16:02.495
equation here from just from the basic physical equations,
or the position of the vehicle at a certain point in time is
00:16:02.495 --> 00:16:10.756
equal to the initial position, plus the individual velocity
times the time, plus a half times Uh acceleration. Times Tea
00:16:10.756 --> 00:16:19.729
Square @unoise@ and. If we can if, we are interested @unoise@
in or if we are modeling not the real position of the
00:16:19.729 --> 00:16:29.115
vehicle @unoise@ um. But the sense position that we have to
consider also the uncertainty and the imposition, the noise
00:16:29.115 --> 00:16:37.881
and distortions and disruptions in the image processing process.
So we have to had some measurement noise here. So based
00:16:37.881 --> 00:16:48.106
on this equation, we can do the same as we did before.
We were arguing @unoise@ Um that um, we get one of these
00:16:48.106 --> 00:16:58.460
equations for each measurement that we made. And we want to
minimize the sum of the squared noise or said
00:16:58.460 --> 00:17:09.980
occur and by doing that, we say we want to minimize this term
here we want to minimize these squared arrows that we make
00:17:09.980 --> 00:17:18.825
in each measurement equation sum up over all the measurement
equations. And we want to minimize this term with suspect
00:17:18.825 --> 00:17:28.235
to the three unknown variables, which are now at zero, B,
zero and A. And again, we can take this term here, calculate
00:17:28.235 --> 00:17:36.446
the respect to the three unknown variables. Zero.
These equations resolve everything, and we get a system of
00:17:36.446 --> 00:17:46.914
linear equations. And based on that, we can determine this.
We are known a variety of so as well we could
00:17:46.914 --> 00:17:55.951
extend this method for any motion model that we can somehow
describe physically. So if you are interested in modeling a
00:17:55.951 --> 00:18:04.265
movement, not just in a one dimensional, a space like we
have did it on the slides before, but in the two dimensional
00:18:04.265 --> 00:18:12.578
space where we were vehicles moving on a plane, and we want
the one to determine the direction into which the vehicle is
00:18:12.578 --> 00:18:21.682
moving. We can go on the same way. So we just have to think
about the question, what is the appropriate an equation that
00:18:21.682 --> 00:18:30.153
describes the motion of this vehicle. If we are assuming that
the vehicle is not just moving straight forward, but that
00:18:30.153 --> 00:18:39.728
it might also steer and um drive on on a curve. We have to
consider the motion model for driving on a curve. Then we
00:18:39.728 --> 00:18:50.026
have some more unknown variables, like the that describes
the amount of turning of the vehicle. And we establish
00:18:50.026 --> 00:18:58.402
this motion model based on that, we determine this optimization
problem where we may want to minimize the sum of the
00:18:58.402 --> 00:19:07.327
scratch square errors that occur in each measurement, and
then we try to minimize it from a certain point on. If the
00:19:07.327 --> 00:19:15.244
Marshall Model becomes too complicated, and there is no
analytical solution for this optimization problem anymore. But
00:19:15.244 --> 00:19:26.583
with numerical , it is still possible to find a solution,
or with um tricks. Okay? and that laughter. Let us now
00:19:26.583 --> 00:19:35.121
summarize these techniques, these regression techniques for
estimating the motion of an object. The advantage is that
00:19:35.121 --> 00:19:44.232
these methods are really simple, are really simple, easy to
use, and the calculations are all efficient. You have to
00:19:44.232 --> 00:19:52.715
solve a system of linear equations, but a pretty small system
of linear equations that does not require much computation
00:19:52.715 --> 00:20:03.246
time. It can be used to estimate straight movements in one,
two or three dimensions. If you like, it is possible to find
00:20:03.246 --> 00:20:13.023
analytic solutions for that. Uh. If it is a uh movement
that is not straight then, uh, you have to solve a non
00:20:13.023 --> 00:20:19.794
linear optimization problem, which requires the numerical
techniques for optimization, but still is possible. So, and my
00:20:19.794 --> 00:20:29.039
suggestion for you is, if you are faced with a problem like
that. Give it a trial with regression. Often it turns out to
00:20:29.039 --> 00:20:37.396
be easier than the techniques that we will introduce next
named the common filter, which looks pretty nice, but in
00:20:37.396 --> 00:20:48.719
practice is a little bit difficult to tune. So give it a
give this a regression, a trial. It is worse trying it the
00:20:48.719 --> 00:20:58.191
shortcomings, while nonlinear methods are necessary for
curved trajectories. That is what I already said than the
00:20:58.191 --> 00:21:07.855
computation effort grows. Okay, let us have a look at an
example of this work that is meanwhile twelve years old, round
00:21:07.855 --> 00:21:17.285
about. At that time, I was creating, together with some
colleagues, a robot soccer team, team of as robots that are
00:21:17.285 --> 00:21:27.125
playing soccer in an automated fashion. So they are not still
operated, but they are fully autonomous. So these are our
00:21:27.125 --> 00:21:35.942
robots, this one here. And these are the robots from
Stuttgart. And there were real competitions in soccer playing
00:21:35.942 --> 00:21:44.061
robots. And yeah, we were one of these teams that were
participating there. Um, of course, if you want to play soccer,
00:21:44.061 --> 00:21:50.442
you need to know where the ball is. And you also need to
know how fast the ball is moving and in which direction,
00:21:50.442 --> 00:21:57.158
otherwise you will not be able to play soccer successfully.
So that is a typical task for motion estimation. Um. And
00:21:57.158 --> 00:22:04.983
actually, in this for this task. I, we were implementing
this kind of regression algorithm quite successfully. Of
00:22:04.983 --> 00:22:14.562
course, we would implementing it took a little bit time to
model all the details. So of course, the ball might roll on
00:22:14.562 --> 00:22:23.268
the field while it is rolling, it is accelerating a little
bit, but it might also be kicked by a robber than it is
00:22:23.268 --> 00:22:30.887
accelerating, or it might collide with a rubber, then it is
somehow reflected at the Robert and changes the direction of
00:22:30.887 --> 00:22:39.137
movement. We might have be faced with chip cakes. Yeah, that
means a ball might leave the ground while it is kicked. And
00:22:39.137 --> 00:22:47.724
we had to deal with all these details. But the basic
method to estimate the motion of the ball was to use um a
00:22:47.724 --> 00:22:54.992
regression model. And that was pretty successful in our case
although, the measurement that we had about the ball
00:22:54.992 --> 00:23:02.626
position were quite limited in accuracy, because the whole
sensor system that was a here you see the camera on top,
00:23:02.626 --> 00:23:11.349
which was looking into a mirror that was above it, and so
that it was looking into the whole environment of the of the.
00:23:11.359 --> 00:23:18.264
So it had a three hundred and sixty degrees around you.
Um. However, the resolution of the camera was quite poor,
00:23:18.264 --> 00:23:26.685
so it was six hundred and forty times four hundred eighty
pixels. If you compare nowadays, consume a camera with
00:23:26.685 --> 00:23:38.045
whatever ten, twelve, eleven, twelve, thirteen million pixels.
Uh, this is pretty, pretty little resolution. And um, so
00:23:38.045 --> 00:23:48.359
that the precision of each measurement of the ball position
was pretty limited in a crucy, but um still, we were able to
00:23:48.359 --> 00:23:57.798
intact with the ball pretty nicely. So how was it done? as
I said so the horizontal for the horizontal movements or
00:23:57.798 --> 00:24:07.442
projected on the ground plane, we were using a constant
velocity model of the ball. And we were always using a time
00:24:07.442 --> 00:24:17.886
frame of the last in between three and fifteen points in
time between the last three and fifteen images from which we
00:24:17.886 --> 00:24:26.301
were taking the ball position. And then we were estimating
the velocity and the position of the ball, based on the
00:24:26.301 --> 00:24:35.587
assumption of constant velocity. So we had a frame rate of
thirty images per second. That means three images means a
00:24:35.587 --> 00:24:45.208
time interval of in total, something like sixty seven
milliseconds and fifteen images means half a second of of
00:24:45.208 --> 00:24:54.760
measurements for the vertical movement. We were assuming an
accelerated motion. We know there is gravity. That means we
00:24:54.760 --> 00:25:04.576
also know the acceleration in vertical direction um. And so
if the ball was we, were assuming uh, that the emotion
00:25:04.576 --> 00:25:12.567
model in vertical direction @unoise@ that is accelerated by
within with an acceleration given by gravity. Of course, we
00:25:12.567 --> 00:25:22.238
had to consider deflections of the ball when the ball bounces
on the ground, it bounces back. And that had to to be
00:25:22.238 --> 00:25:30.135
modeled, eh explicitly, this could not be integrated into
this vertical motion model % um that we were using together
00:25:30.135 --> 00:25:38.336
with linear regression. But this was an additional modeling
step. As I said, we took between three and fifteen
00:25:38.336 --> 00:25:44.777
observations. And while we made it adaptable, that means we
were always checking whether this assumption of a constant
00:25:44.777 --> 00:25:52.779
ball movement was still valid or not. And if we observe that
the new measurements do not fit any more to our our motion
00:25:52.779 --> 00:26:01.011
model than we are saying something happened. The ball might
be kicked, or the ball might be eh deflected at A at an
00:26:01.011 --> 00:26:09.930
obstacle. That means then the motion we as we were assuming
that the motion changed. And that means then we were
00:26:09.930 --> 00:26:18.917
reducing the number of observations that we considered two,
three, and then we added motions. Ah! observations. Ah, in
00:26:18.917 --> 00:26:29.834
our, in our Ah temporal window, up to a maximum number fifty
@unoise@ yeah. That, was the procedure so here is
00:26:29.834 --> 00:26:37.095
some result this was actually an experiment in lap.
What you can see is a soccer field and this is the
00:26:37.095 --> 00:26:45.675
position of the robot so. Here is a front of the Robert.
That is the rear side of the robot. And here is what you
00:26:45.675 --> 00:26:56.978
can see is a bore. So this um the broken circle is the
sense position of the ball. That means that the position
00:26:56.978 --> 00:27:07.312
that the camera sensed and this um light red, solid circle
is the position of the ball that was estimated using the
00:27:07.312 --> 00:27:16.365
linear regression model and the lion here. This red line
indicates the motion direction and the velocity. That means the
00:27:16.365 --> 00:27:26.458
longer this line is, the larger is the estimated velocity,
you know, and when. So this experiment runs in a cycle. So
00:27:26.458 --> 00:27:34.813
when we see observations here, the sequence starts. And now
we have the first two measurements. We saw the first two
00:27:34.813 --> 00:27:42.247
measurements from two measurements. We did not yet estimate
emotion. The motion of the ball but from the third
00:27:42.247 --> 00:27:50.163
observation, we started to estimate the motion of the ball,
you know, and especially for the for the goalkeeper,
00:27:50.163 --> 00:28:00.057
we had a binocular camera set up so that we could also observe
the ball when it is not located on the ground, but when
00:28:00.057 --> 00:28:09.579
it was chip kicked for the other robots. We only had a
Monica arm camera set up so that we can could all only get
00:28:09.579 --> 00:28:17.535
the position of the ball when it was lying on the ground, but
that was sufficient. But for the goalkeeper, it was pretty
00:28:17.535 --> 00:28:26.830
important, of course, to be able to react also on balls that
were chip kicked. Okay, so that is one example where, uh,
00:28:26.830 --> 00:28:37.584
such a linear regression model was very useful to estimate
the motion of objects. Of course, this can also be done if
00:28:37.584 --> 00:28:47.317
you want to track cars in a traffic scenario, or if you want
to track pedestrians, or if you want to track any other
00:28:47.317 --> 00:28:56.319
moving objects @unoise@ okay. So, this was linear regression
with an example for tracking objects. Well, the probability
00:28:56.319 --> 00:29:06.956
theory is something that we already introduced so we can skip
it to day and can go to the next approach, a very generic
00:29:06.956 --> 00:29:15.582
approach. First, for tracking, which does not only apply for
tracking objects in the sense of estimating their emotion,
00:29:15.582 --> 00:29:26.226
but also for checking system states in general. We will see
later on how we can generalize it. But first of all, we need
00:29:26.226 --> 00:29:35.051
to introduce a stochastic model with which we can model these
kind of processes, like the process of a ball that moves,
00:29:35.051 --> 00:29:44.678
or the process of the car that drives, or the process of a
system that evolves and changes over time and these are
00:29:44.678 --> 00:29:54.081
so called hidden Markov models that we want to use. So our
main idea is we observe something and retreat that as a
00:29:54.081 --> 00:30:02.907
system, whatever system means, but as a kind of entity that
can be described by some equations. Physical equations, for
00:30:02.907 --> 00:30:14.045
instance, which describe the motion of of an object or
other equations from other from other sciences. We want to
00:30:14.045 --> 00:30:22.099
describe other systems. So, but for us here, lets us hear.
We want to describe the motion of an object. We treat this
00:30:22.099 --> 00:30:30.855
object in its motion as a system, and we assume that the system
is described by estate. What is a state? a state is just
00:30:30.855 --> 00:30:39.126
a set of variables. So for instance, if you want to model
the movement of a car, you might say the movement is fully
00:30:39.126 --> 00:30:47.122
described. If you know the position of the car. If you know
the velocity of the car, the driving direction may be the
00:30:47.122 --> 00:30:54.712
steering angle. Then this motion is fully described, and
such a set of variables that we need to fully describe the
00:30:54.712 --> 00:31:04.458
behavior of such a system is what we call the system state.
So, and one property of the system state is that we can
00:31:04.458 --> 00:31:13.759
describe the changes of the system over time, only based on
these variables that are contained within the state. If we
00:31:13.759 --> 00:31:22.465
need some other variables, then the state is somehow not
complete that we were using up to now. Now. So one example, let
00:31:22.465 --> 00:31:30.391
us go back to our car accelerates at the traffic lights
scenario. If we don't know the acceleration of the car. We
00:31:30.391 --> 00:31:37.918
cannot make good predictions of its future behavior. But if
we know the acceleration, then we can make good predictions,
00:31:37.918 --> 00:31:46.983
so the acceleration is necessary. So the acceleration must
be part of this state of the of the system moving car. Now
00:31:46.983 --> 00:31:57.244
Okay. So, so here is this example. First of all, this
example without acceleration. So if you want to model a car
00:31:57.244 --> 00:32:05.592
that moves more or less with constant velocity than we might
say. The system is fully described, knowing its current
00:32:05.592 --> 00:32:14.127
position and its current velocity. And if we are interested
in, to the emotion of three D motion. These two parameters
00:32:14.127 --> 00:32:22.829
become vectors. And so the vector valued position of the
vehicle and the vector valued velocity of them. Color
00:32:22.829 --> 00:32:31.610
now. We have based on this system state, we can predict the
changes of the of the system into future. We can say, okay,
00:32:31.610 --> 00:32:40.676
for some point in time, at a future point in time, which is
different from the present point in time tea by a certain
00:32:40.676 --> 00:32:48.740
amount capital delta. And we could argue that um based on
the system description. The future position is the current
00:32:48.740 --> 00:32:58.294
position plus delta times, the current velocity and the future
velocity is equal to the current velocity. Of course, in
00:32:58.294 --> 00:33:08.894
practice, all these systems are not deterministic. There is
always a little bit of imposition in the system. So in this
00:33:08.894 --> 00:33:19.013
case, the car driver might changed the velocity a little bit.
It might let vary it a little bit, or there might be some
00:33:19.013 --> 00:33:27.832
friction or whatever, so that this position here is not
perfectly met this position equation. So therefore we have to
00:33:27.832 --> 00:33:37.302
add some statistics, some random noise in these two equations,
which model this impression in the system, the impression
00:33:37.302 --> 00:33:45.983
in the transitions between different points in time. Now
this is not yet the measurement noise. We didn't talk about
00:33:45.983 --> 00:33:54.584
measurements yet. This is just the the imposition in the
system as such, and the imposition with which we can, which a
00:33:54.584 --> 00:34:03.633
driver can keep its velocity, for instance. So in this case,
we can even rewrite these two equations in term of a matrix
00:34:03.633 --> 00:34:11.912
vector multiplications, or if the state is written here as
a kind of factor of state variables. And we can describe
00:34:11.912 --> 00:34:19.866
these transitions as metrics, vector multiplication. In this
case, the new state is equal to this matrix. One delta zero
00:34:19.866 --> 00:34:29.165
one times the old state, plus noise, where the noise here
is a noise vector. Now that has two components, one for the
00:34:29.165 --> 00:34:37.316
position and one for the velocity @unoise@ okay. So, now
we let us talk about the measurements that we make. So we
00:34:37.316 --> 00:34:46.820
assume we have some sensor that can take measurements from
the system @unoise@ and % um we % um assume that we cannot
00:34:46.820 --> 00:34:54.671
necessarily see the system, measure the system marriages of
state variables, but that we can make some observations that
00:34:54.671 --> 00:35:03.557
are only somehow somehow related to the state variables. And
that means we assume that there is a mapping that describes
00:35:03.557 --> 00:35:13.871
how the censor works, that maps the state, the true state of
the system to a measurement, said the so set is used within
00:35:13.871 --> 00:35:23.021
chapter number five, always for measurements. Who said might
be a single scholar measurement, or it might be a vector of
00:35:23.021 --> 00:35:30.342
measurements. So for instance, furthermore, we assume that
the whole measurement process is not perfect. So there is
00:35:30.342 --> 00:35:38.916
some uncertainty, some random imposition in in the measurement
system as well. That means we have to add some noise here
00:35:38.916 --> 00:35:48.835
as well. So the censor takes the two state of the system and
maps it on to an observation and adds up some imposition,
00:35:48.835 --> 00:35:57.892
some statistical, some random noise. And this indeed is the
measurement noise, the noise that is created by the sensor
00:35:57.892 --> 00:36:07.006
in the sensor evaluation process. So for instance, let us
assume we have this example of Cora that drives its constant
00:36:07.006 --> 00:36:15.681
velocity. The system state is described by these variables.
And now we assume, for instance, that we have a camera, the
00:36:15.681 --> 00:36:23.329
camera can measure the position of of the vehicle, but not
its velocity. Then we could argue that this measurement
00:36:23.329 --> 00:36:30.654
equation looks like that. So said of tea is equal to
directly measure the position of the vehicle, plus some
00:36:30.654 --> 00:36:37.495
additional measurement noise for other sensors, we might
be able to sense the velocity of the vehicle, but not the
00:36:37.495 --> 00:36:46.045
position for other sense, as we might be able to sense both
the position and the velocity um in such a case, set of tea
00:36:46.045 --> 00:36:57.696
would be a vector of two entries. And again, in this case,
we couldn't represent that as well as a matrix times nectar
00:36:57.696 --> 00:37:06.404
multiplication @unoise@ okay. So, what we have to think
about, or what is important to see is that that of tea. These
00:37:06.404 --> 00:37:15.179
are the measurements. That is something that we can observe.
That is something that the sensor provides to us. This S is
00:37:15.179 --> 00:37:26.022
something that we don't know. It is unknown to us. Now. This
is are known to us, and it is also important to see that in
00:37:26.022 --> 00:37:35.243
this case, set of tea is not the same as X of tea. We send
the position of the vehicle, but the measurement that we get
00:37:35.243 --> 00:37:44.266
is not exactly the position, but it is the position plus
some noise on it. And so we must be careful in dealing with
00:37:44.266 --> 00:37:52.501
these equations. Um and always think carefully whether we
talk about the true state, the true position of the vehicle,
00:37:52.501 --> 00:38:01.089
which would be exhausted here, or whether we talk the scent
about the sense, position and the observation that we have.
00:38:01.099 --> 00:38:11.703
They should be related to each other, but they are not the
same @unoise@ okay. So, now let us assume we have modeled the
00:38:11.703 --> 00:38:19.998
system that we are interested in as such a system with a
system state and with some observations, and with a mapping
00:38:19.998 --> 00:38:28.472
from system states at one point in time to future points
in time. And with a modeling that describes which, how the
00:38:28.472 --> 00:38:36.785
observation that the censor provides is related to the state,
then Ah, and if we make some assumptions, we can describe
00:38:36.785 --> 00:38:46.824
that as a so called hidden mark of moral, or for short, h,
m, n, what is it? it is a time discreet. The castic state
00:38:46.824 --> 00:38:54.705
transitioning system, its observation in its successes, they
depend entirely on its present state and do not depend on
00:38:54.705 --> 00:39:02.430
previous states and or observations. Okay, let us go through
this definition step by step. So first of all, it is a
00:39:02.430 --> 00:39:09.247
state transitioning system that is clear. That is what we
already saw. We have some state, and the state is changing
00:39:09.247 --> 00:39:16.297
over time. Now that is a state transition system, then it
is this means there is some randomness in the state
00:39:16.297 --> 00:39:23.150
transition system. Yeah, we always have this noise terms,
these random noise terms. Now it is not deterministic, but
00:39:23.150 --> 00:39:31.152
there is some randomness in then time does treat means we
evaluate the system only at discrete points in time. Now we
00:39:31.152 --> 00:39:40.536
are modeling it, not as a continuous time process. But we
are only focusing on some discrete points in time. For
00:39:40.536 --> 00:39:49.463
instance, only if we often, if we deal with cameras, and
if the cameras are providing whatever, thirty images per
00:39:49.463 --> 00:39:57.802
second. That means one image after thirty, three milliseconds,
then these time intervals that we consider are thirty
00:39:57.802 --> 00:40:06.136
three milliseicants. And we only consider the system stayed
um for these intervals of thirty three Milliseicans. And we
00:40:06.136 --> 00:40:15.464
are not interested what goes on between now. This means a
discrete time um state transitioning system, and therefore we
00:40:15.464 --> 00:40:25.476
can enumerate the States over time with indigers. So point
in time, zero, one, two, three, four, five, et cetera
00:40:25.476 --> 00:40:35.687
@unoise@ so now its observation and its successor state
depend entirely on its present state and do not depend on
00:40:35.687 --> 00:40:45.971
previous states or observations. What does it mean if you
want to predict um. If we know the two state of the system,
00:40:45.971 --> 00:40:56.723
then we can make good predictions for the observation that we
will get and for the next, for the state at the next point
00:40:56.723 --> 00:41:06.763
in time. And if we know what were the previous states and
the previous observations does not help us to get better
00:41:06.763 --> 00:41:14.849
predictions about the future. So all the information that
describes the system is contained in the state variables.
00:41:14.860 --> 00:41:22.099
Knowing the history doesn't help to predict the future, because
all relevant information is already contained in this.
00:41:22.110 --> 00:41:33.696
In the present state, very others. That is the main message
of this. Now, so so sarcastically, this property
00:41:33.696 --> 00:41:49.400
can be defined by these two equations, which are equations
that implement this assumption as a stochastic equation. It
00:41:49.400 --> 00:41:58.716
says the probability for the successor state based on the
knowledge of the present state, the present observation, the
00:41:58.716 --> 00:42:11.524
previous state, previous observation and so on and so on. Up
to the first um state at all is the same as the probability
00:42:11.524 --> 00:42:22.238
of the successor state given the present state, which means
all this history of earlier states and earlier observations
00:42:22.238 --> 00:42:32.600
do not matter. Now, once we are faced with such an equation,
we can simplify with such a probability, we can simplify it
00:42:32.600 --> 00:42:40.079
to that probability. Now, this is an assumption that we make
about the world or about the system. It is not in general.
00:42:40.090 --> 00:42:48.392
Well, it for any system, but it is an assumption that we have
to make if we want to model a system as a hidden mark of
00:42:48.392 --> 00:42:56.886
what. And the same equation is similar to the first one.
It says," If we want to predict the present observation or
00:42:56.886 --> 00:43:05.797
taught us a present observation. What is a probability of the
present observation, given the present state and all the
00:43:05.797 --> 00:43:15.120
previous observations in all previous states. This can be
simplified by assumption in a hidden mark of model to this
00:43:15.120 --> 00:43:23.460
very much simpler probability of the current observation,
given the current state and forgetting about the past. Now,
00:43:23.460 --> 00:43:31.860
hidden Markov model is a system where we can always forget
about what happened in past, because it will not influence
00:43:31.860 --> 00:43:41.471
the future once, at least if we know the present state. Um,
this is not valid for all systems, of course. Eh, for some
00:43:41.471 --> 00:43:50.291
systems, you must know for where you came to be able to
predict into which direction. So to say, you will move in
00:43:50.291 --> 00:43:59.927
future. Then where this, such a system would not be a hidden
mark of moral. Yeah, for the next Ah, we assume that all
00:43:59.927 --> 00:44:09.816
the systems that we model Ah, meet these Ah equations and
these properties, and can therefore be modelled as a hidden
00:44:09.816 --> 00:44:19.646
Markov model @unoise@ so. Now we can ask some questions, namely,
one question would be, let us assume we made an object,
00:44:19.646 --> 00:44:29.585
a sequence of observations. And we want to know in which
state does the system is currently in. What is the present
00:44:29.585 --> 00:44:42.043
state of the system. Once we made a sequence of observations.
So we observed a car several times. And now we want to
00:44:42.043 --> 00:44:50.673
know how fast it is driving. Now, that would be a question
like that. And another question is related to the first
00:44:50.673 --> 00:44:59.724
question. It looks like that. It says," We observe the chorus
of all times. And we want to know where will it be? and
00:44:59.724 --> 00:45:11.212
um, how fast it will. Will it be one time step ahead. So we
want to make a prediction into future. So these are the two
00:45:11.212 --> 00:45:21.792
frequent questions that are relevant for many applications.
So this is what is the present state of the vehicle based on
00:45:21.792 --> 00:45:29.809
the observations that you make. And this is the question
@unoise@ what is the future % uh state of the vehicle, % um.
00:45:29.820 --> 00:45:40.749
Once we made a sequence of observations. Now, let us do that
and and derive Ah! equations for that. Ah! Ah! based on the
00:45:40.749 --> 00:45:49.379
assumptions of a hidden mark of model. First of all, let us
consider this equation here. The probability of the present
00:45:49.379 --> 00:46:00.253
state. Given the observations up to the present point in
time. What can we do? well, first of all, we can use Bayes
00:46:00.253 --> 00:46:10.789
theory to transform this equation. We exchange what do
you know what? yes, we exchange St and set tea in this
00:46:10.789 --> 00:46:20.129
conditioner distribution. And we keep the older observations
here on the right hand side of this conditional um
00:46:20.129 --> 00:46:29.179
probability. Distribution, okay then we get this conditional
probability where the role of Sat at T and S, T has
00:46:29.179 --> 00:46:37.438
changed. And some terms, namely the probability
of S, T given or the previous observations. And in the
00:46:37.438 --> 00:46:47.258
denominator, the probability of the current observation, given
all previous observations. So now we can say to make two
00:46:47.258 --> 00:46:57.014
simplifications. The first simplification is, if we look
at this equation at this probability. Here we see that the
00:46:57.014 --> 00:47:05.330
probability of the current observation, even the current state
and some previous observations. So if we assume that this
00:47:05.330 --> 00:47:12.329
system is a hidden Markov model, then we can simplify this
probability, this condition of probability, because we set
00:47:12.329 --> 00:47:20.885
for a hidden mark of model. The history doesn't matter.
Once we know the present state, all the information that is
00:47:20.885 --> 00:47:29.810
contained in this history of observations. It is also
contained in . Therefore we can omit these previous
00:47:29.810 --> 00:47:42.031
observations in the right hand side part of this conditioner
and probability. Now, then this is simplified, and it
00:47:42.031 --> 00:47:51.481
becomes this probability here. Furthermore, this denominator,
it just contains observations. It doesn't contain any
00:47:51.481 --> 00:47:59.924
states. It does only contains observations. The observations
are what we know. We have measured them. And that means
00:47:59.924 --> 00:48:09.077
this denominator is just a constant that is independent on
the presence of the present state. And therefore we can say
00:48:09.077 --> 00:48:19.299
we could argue that this term is constant, so we hide it
inside of this is proportional to term. Yeah, so this is
00:48:19.299 --> 00:48:28.320
proportional true term here just hides this denominator,
which is just a constant independent of the present state of
00:48:28.320 --> 00:48:39.659
the system. Now Ok So. This is this part now.
Now, let us have a look at this equation. This deals with the
00:48:39.659 --> 00:48:48.979
prediction, predicted probability of the future state of the
system. Given the observations up to now, what can we do
00:48:48.979 --> 00:48:58.120
here? well, we can use again the calculation rules for
probability calculating with probabilities. What we do is we add
00:48:58.120 --> 00:49:07.642
another variable here in this probability the present
state Ah, and to neglect this influence of Sd. Again, we
00:49:07.642 --> 00:49:18.223
summarize over all possible values that this variable este
can take. Now, this is the rule that we introduced in
00:49:18.223 --> 00:49:28.195
the repetition of probability theory now. So this equality
here really holds, because we neglect the influence of this
00:49:28.195 --> 00:49:37.650
added probability, a random variable by summing up over all
possible values @unoise@ okay. So, based on this equation,
00:49:37.650 --> 00:49:45.597
we can split up this equation a little bit again, using the
definition of conditional probabilities we want to push. So
00:49:45.597 --> 00:49:54.264
to save this S T variable to the right inside part of the
conditional distribution, we can do so. And by multiplying it
00:49:54.264 --> 00:50:03.625
with some correction term like that. So the said one to
is always in the condition part in the right and part of
00:50:03.625 --> 00:50:11.016
this of these conditional um distributions, unconditional
probabilities and um. Yeah, the esteem as here we have
00:50:11.016 --> 00:50:19.522
so to say, the joined probability of St plus one. And Este
given these observations. And here we have the conditional
00:50:19.522 --> 00:50:28.682
distribution of St, plus one given St. And all previous
observant and all the observations times the marginal, so to
00:50:28.682 --> 00:50:38.933
say, of St, given always given the observation. So that
is as well just using the definition of a condition of
00:50:38.933 --> 00:50:48.581
probability, this transformation. Now we can simplify this
term. So this term is a probability of a success estate given
00:50:48.581 --> 00:50:57.620
the present state and some observations from past. Again, we
assume we are faced with a hidden Markov model. That means
00:50:57.620 --> 00:51:07.341
all the information from the pass is already contained in
the present state. And that means that we can neglect the
00:51:07.341 --> 00:51:17.584
history and remove these observations here from M, this
conditional probability, and then things simplify. And we get
00:51:17.584 --> 00:51:27.596
these simpler transition probabilities. Okay, so far. Now,
let have a look at these two equations that we get. First of
00:51:27.596 --> 00:51:35.677
all, what is that? well, that is just the symbol state
transition probability that says, if you are in a certain state,
00:51:35.677 --> 00:51:44.608
how likely is it that you enter another state from it. So
that is very simple, and something that we defined in the hit
00:51:44.608 --> 00:51:52.632
mark of model @unoise@ this term here it has formed the
probability of the current state. Given the observations up to
00:51:52.632 --> 00:52:01.792
the current point in time, and that is actually what we get
as result here in the first equation. So this term that
00:52:01.792 --> 00:52:11.995
was calculated as the result of the equation here on the
top of the slide. Ah, though that means once we have this
00:52:11.995 --> 00:52:20.140
result from here, we can enter it here. This is something
that we defined with a hidden mark of model. That means then
00:52:20.140 --> 00:52:31.053
we can evaluate this term, and we get this probability of the
predicted state. Now, let us go to the role here. What is
00:52:31.053 --> 00:52:38.260
this? well, that is just the observation probability. That
is a probability. If you are in a certain state, what is the
00:52:38.260 --> 00:52:45.934
probability to make a certain observation. That is what we
defined within the hidden Markov model. Okay, and what is
00:52:45.934 --> 00:52:55.862
this term while this is the probability of the present state.
Given the observations up to the point in time before, as
00:52:55.862 --> 00:53:05.120
though this is a predicted probably probability that predicts
which state will be in the next point in time. Once we saw
00:53:05.120 --> 00:53:14.084
all the observations up to the previous point in time. Now
also, it has the structure of this probability here. But we
00:53:14.084 --> 00:53:22.900
see that this index here has just been incremented by one.
So here we have S tea, given that one to set tea minus one.
00:53:22.909 --> 00:53:32.068
And here we have S tea plus one given said one to set tea.
So there is one. Just one increment changed in the time. But
00:53:32.068 --> 00:53:39.819
but we see that the structure actually of this probability
is the same as this one. That means, if we want to calculate
00:53:39.819 --> 00:53:47.999
this term, we have to apply this calculation here at the
bottom, but for the point in time before that means, in total,
00:53:47.999 --> 00:53:55.719
we get some recurrent dependence between these two equations.
The result that we calculate here at the bottom enters a
00:53:55.719 --> 00:54:03.774
calculation here. On the right side of the of the calculation.
At the top of the slide. And the result that we get here
00:54:03.774 --> 00:54:13.125
on the top of the slide and has the calculation at the bottom
of the slide. But within such a cycle @unoise@ the, time
00:54:13.125 --> 00:54:25.708
is incremented by one that means the calculations are always
based on the results that we obtained at the point in time
00:54:25.708 --> 00:54:34.457
before. That means we have to start, of course. Still, we
have to start at a certain initial point in time with a
00:54:34.457 --> 00:54:43.455
certain assumption. So an initial assumption about the
distribution or the probabilities of the state variables that
00:54:43.455 --> 00:54:53.900
would be actually something like the probability, whereas
the probability of S, Mhm, um one given no observations at
00:54:53.900 --> 00:55:04.899
all. Now that is something that we have to assume somehow.
Now, if we have that, then we have this term here for as one.
00:55:04.909 --> 00:55:16.636
So where T actually is zero, then we can end that at that
here and go on like that and through time, do all the
00:55:16.636 --> 00:55:26.123
calculations, step by step, all the time. So here
is another scheme that shows this schedule. So we have an
00:55:26.123 --> 00:55:33.537
initial estimate about these predicted state probabilities.
We take it from some background knowledge, or we specify in
00:55:33.537 --> 00:55:41.387
this probability distribution with which we start that we
do not have knowledge about the present state that is also
00:55:41.387 --> 00:55:50.110
possible and then we have these two states with these
two steps. One step that takes these predicted state
00:55:50.110 --> 00:55:58.905
probabilities and um incorporates a new observation. And to
get these state probabilities and then the other step
00:55:58.905 --> 00:56:08.663
that goes from here to here that does a prediction. And these
two steps are called prediction step. Now, once we make
00:56:08.663 --> 00:56:17.512
calculate these predicted state probabilities from those
here. This is the so called prediction step. And this step
00:56:17.512 --> 00:56:29.467
where we add up a new observation is called either the
correction step or the innovation step. And all this of this
00:56:29.467 --> 00:56:42.738
approach @unoise@ yeah um @unoise@ then the whole thing looks
like that. And over time. So we start with this P of S
00:56:42.738 --> 00:56:51.968
one. Ah, then we make an innovation step to get P of as one
given said one. Then we make a prediction step to get this
00:56:51.968 --> 00:57:01.479
peer of as tool given set one. Then we make an innovation
step to get peer of a tool given set to set one. Then we make
00:57:01.479 --> 00:57:11.288
again a prediction step, and so on. And sore huh, we could
start either here or here. That depends very much on the
00:57:11.288 --> 00:57:20.483
problem. Ah, whether it is better to start here, or whether
it is better to start here. Ah, sorry. I ought to start
00:57:20.483 --> 00:57:28.638
here. So that is possible to start with P of a zero, and
then for a first make a prediction step. That is also a
00:57:28.638 --> 00:57:35.180
possible starting point. But that depends very much on the
application, whether it is more reasonable to start here or
00:57:35.180 --> 00:57:48.947
more reasonable to start here. @unoise@ yeah. Um, you so.
This is a very general scheme. And the problem with this
00:57:48.947 --> 00:58:04.778
general scheme of this algorithm is that if you look at the
formula @unoise@ a very general scheme of an algorithm. As
00:58:04.778 --> 00:58:16.091
long as @unoise@ um. The state variables are discrete random
variables, which can only take on values from a finite,
00:58:16.091 --> 00:58:25.183
discreet set of possible values, and the observations are as
well discreet random variables. That means the observations
00:58:25.183 --> 00:58:36.329
are also just discreet numbers, then this algorithm can be
implemented on a computer very efficiently, and um to do the
00:58:36.329 --> 00:58:47.083
prediction. So let us make an example for such a case, and
um to get some better intuitive uh feeling for this
00:58:47.083 --> 00:58:58.178
kind of uh algorithm. So in this case, now we describe this
hidden Markov model in case of a transition diagram in this
00:58:58.178 --> 00:59:06.460
transition diagram. Each of these ellipses refers to one
value that the state variable can take. So we assume one
00:59:06.460 --> 00:59:14.715
discreet random variable estate variable, and it can
take on three different values, A, B and C. And with the
00:59:14.715 --> 00:59:23.754
observation, we assume that we have one discreet, random
variable for the observation, and it can take on two different
00:59:23.754 --> 00:59:31.777
values, either you or the yeah now. We have some
transition probabilities between the different states. And these
00:59:31.777 --> 00:59:40.162
are shown here by these black arrows. So each error models
a possible transition. And the numbers here refer to the
00:59:40.162 --> 00:59:47.369
transition probabilities now. So this point two is a
probability that the system makes a transition from state A
00:59:47.369 --> 00:59:57.546
to state B from one point in time to the subsequent point in
time. And we can also stay in state A with the probability
00:59:57.546 --> 01:00:06.577
of one point eight, for instance, and then these dashed
science lines refer to the observation probabilities. So
01:00:06.577 --> 01:00:15.752
when the numbers here refer to the respective probability.
So this all point eight says the probability to make the
01:00:15.752 --> 01:00:26.170
observation V in state B is eighty percent. Now, and
um of course, since these probabilities must sum up to one.
01:00:26.179 --> 01:00:39.242
And the probability to make the observation you in State
B must then be or point to well @unoise@ ok so this
01:00:39.242 --> 01:00:49.427
is the transition diagram. And for this kind of system,
let us execute this algorithm a little bit. So we want to
01:00:49.427 --> 01:00:56.667
calculate these state probabilities for an observation sequence
you, you will be you. So at first point in time, we get
01:00:56.667 --> 01:01:02.985
an observation you in the second point in time, we get
observation you. And the third point in time we get the
01:01:02.985 --> 01:01:09.288
observation V. And in the fourth point of time, we get
the observation you work at. And we assume as initial
01:01:09.288 --> 01:01:17.788
distribution that the probability to be in A that as a one is
equal to A is equal to all point five. And the probability
01:01:17.788 --> 01:01:27.210
that as one is equal to be is also a point five, and the
probability that as one is equal to C is equal to zero. Now,
01:01:27.210 --> 01:01:40.708
that is our assumption for the initial point of time as one.
So now let us do the calculations. So here is a table that
01:01:40.708 --> 01:01:52.245
contains all the results that we get. So am here at the
bottom. These three lines refer to the predicted state
01:01:52.245 --> 01:02:04.550
probabilities, not the state probability that the predicted
a state is either A or B or C. And the top rose, the sweet
01:02:04.550 --> 01:02:13.317
top rose referred to the estimated state probabilities after
integrating the present observation? well, that means if we
01:02:13.317 --> 01:02:23.381
go from the top rows to the bottom rose, we make a prediction
step. And if we go from the bottom, rose in diagonal
01:02:23.381 --> 01:02:33.003
direction to the right upper neighbor than we make an innovation
step now. So we started here with the predicted states
01:02:33.003 --> 01:02:40.797
state variable estate probabilities. So first of all, we
have to make an innovation step. And the first symbol of the
01:02:40.797 --> 01:02:49.363
first observation that we got was you observation use. So
we may have to make an innovation step. So how did it look
01:02:49.363 --> 01:02:58.344
like? well, what did we have to do? we had to multiply the
respective state probable predicted state probabilities with
01:02:58.344 --> 01:03:06.759
respective observation probabilities, and afterwards
the numbers that we get such that they sum up to one. That
01:03:06.759 --> 01:03:13.689
means we have to find a normalization factor with which we
multiply these values that we get such that afterwards, the
01:03:13.689 --> 01:03:22.086
sum is equal to one. If we do that in this case, what do we
get well, for state A, the probabilities, or point five, the
01:03:22.086 --> 01:03:30.360
probability to make an observation. You is so. We have
all point five times or point six a yields or point three?
01:03:30.369 --> 01:03:40.042
okay, let us remember memorize upon three here, something
like opens we for beam, the probability to be in is a point
01:03:40.042 --> 01:03:49.065
five times observation to make observation. You is open two,
zero point five times or point two is all point two. Five,
01:03:49.065 --> 01:04:03.849
no. Is it no? four point two? five, yes, no or open one. Oh,
what is it all? point one, one point one now so we
01:04:03.849 --> 01:04:11.896
would have zero point three here. And one point one here
foresee the probability to be in a zero the observation
01:04:11.896 --> 01:04:19.246
probability is opened seven or zero times open. Seventy zero
So. Which factor do we have to multiply am to such
01:04:19.246 --> 01:04:28.179
such that the probability sum up to one while we have here,
or point three here, if o point one. So the sum is one at a
01:04:28.179 --> 01:04:36.456
point four. Let us divide the numbers by the sum by o point
four than we get, or point seven, five here and open two,
01:04:36.456 --> 01:04:43.964
five, here and zero here and now we see that these probabilities
sum up to one again now. So this normalization factor,
01:04:43.964 --> 01:04:52.473
in this case, was just the sum of the values that we were
calculating here before normalization. Now we divide all the
01:04:52.473 --> 01:05:02.678
numbers by this sum, and then we get the probabilities.
Okay, then we are here. Can we see that introducing or ink
01:05:02.678 --> 01:05:15.039
introducing this observation helps us to get more certain about
which, within which that we are really in. Ah, so before
01:05:15.039 --> 01:05:23.286
we did not know whether we were in State A or B, could both
could was possible with same probabilities. Now we know that
01:05:23.286 --> 01:05:31.678
it is much likelier to be in state A than to be in state. So
the innovation step helps us to get more information about
01:05:31.678 --> 01:05:42.650
what is a real state. Um, yeah. Now let us start from
here and execute the prediction step in the prediction step.
01:05:42.659 --> 01:05:56.622
What do we have to do if you want to know the probability I
am here too. @unoise@ enter state A. How can we interstate a
01:05:56.622 --> 01:06:07.089
well either we have been in state A before. And when this
way we estate in state A before all we have been in
01:06:07.089 --> 01:06:15.762
state sea and went this way here. Okay, let us calculate the
probabilities for these two possibilities to be in state A
01:06:15.762 --> 01:06:24.272
happens with the probability of oh point seven, five to go
to stay with inside our state A it happens with probability
01:06:24.272 --> 01:06:32.537
of o point eight. So we have opened seven, five times o
point eight. And if you have a pocket card later, you might
01:06:32.537 --> 01:06:39.857
check that this year's or point six. The second possibility
is we could have been in state sea with the probability of
01:06:39.857 --> 01:06:47.760
zero, and made this transition with a probability of
five, which yields in total or point five times zero, y zero.
01:06:47.769 --> 01:06:56.266
That means this possibility does not contribute. That means,
in total, what we have to write here is all point seven,
01:06:56.266 --> 01:07:06.616
five times all point eight plus zero more times or point five.
And this year's @unoise@ state number B what is the
01:07:06.616 --> 01:07:15.404
probability that in the next point in time. We are in state
number B, while there are two possibilities either we have
01:07:15.404 --> 01:07:25.080
been in state A and have went this way, or we have been in
state sea and go this way now. So the first way happens with
01:07:25.080 --> 01:07:32.749
the probability of four point seven, five times zero point
two, and the second path happens with the probability of zero
01:07:32.749 --> 01:07:41.797
times zero point five. And in total, if you sum up these two
possibilities, we get one point one, five here @unoise@
01:07:41.797 --> 01:07:50.294
state see. How likely is it that we are in state. See at the
next point in time. Well, how can it happen? the only way
01:07:50.294 --> 01:08:01.127
that it happens is if we in state be, and we go this way.
We have in total, four point two, five times one yields oh
01:08:01.127 --> 01:08:12.217
point to five. Okay? That is a prediction step. Well,
maybe one further roll a column here to get a better
01:08:12.217 --> 01:08:20.913
understanding next step here. If we make an innovation step
here we make the observation you while for state A. What do
01:08:20.913 --> 01:08:27.820
we have to consider? we have to calculate this probability,
this predicted probability, or point six and multiplied with
01:08:27.820 --> 01:08:37.251
the observation probability. It is as well open six. So we
get all points three, six year, and then for B, we have the
01:08:37.251 --> 01:08:46.379
probability, the predicted probabilities, zero point one, five,
the observation probabilities, zero point two. So we get
01:08:46.379 --> 01:09:04.679
all points < laugh > or point all three. Is it right open
to me? yes, something like that. I, if I'm wrong, just just
01:09:04.679 --> 01:09:14.860
complain. Yeah, um, or? and for Stacy, it is all point two,
five times the observation probability of oh point seven.
01:09:14.869 --> 01:09:22.676
That is something that you might ask your pocket calculator
for, and then you get some numbers here. Ah, you sum up
01:09:22.676 --> 01:09:29.366
these numbers that yields your correction term. You divide
all these numbers by this correction term, and then the
01:09:29.366 --> 01:09:38.191
number that you get is open six, four, a point or five, or
all points we have won okay by doing that you
01:09:38.191 --> 01:09:44.687
get, you execute the innovation step. And now the prediction
step again. Well, now it is a little bit more interesting
01:09:44.687 --> 01:09:52.328
for state A. What are the ways to Interstate A. Either you
have been in State A, and you go this way. This happens with
01:09:52.328 --> 01:09:59.426
probability of all point six, four times or point eight, or
you might have been in state sea, which happened with the
01:09:59.426 --> 01:10:06.568
probability of open three, one. And you went this way with
the probability of one point five, you add up these two
01:10:06.568 --> 01:10:16.149
possibilities, and you get as a result, or point six, seven.
Well, like that, you fill out the oven, the other cells as
01:10:16.149 --> 01:10:31.658
well. Now, @unoise@ mhm. Okay, so that is an example how we
can calculate these probabilities in a hidden Markov model
01:10:31.658 --> 01:10:42.721
with discrete states and discrete discredit state variables
and discreet observations. This is useful for some cases. We
01:10:42.721 --> 01:10:54.312
will go back to this, to these kind of examples later on.
But for many processes, in many estimation tasks, it is not
01:10:54.312 --> 01:11:03.886
yet useful, because many things are not discrete described
by discreet variables by by continuous marijuana. So if
01:11:03.886 --> 01:11:13.950
you want to estimate the velocity of an of a of a a
traffic participant. The velocity is not just drives fast or
01:11:13.950 --> 01:11:25.363
drive slow, or doesn't drive at all from discrete values.
But it is a velocity of thirty five point eight, two
01:11:25.363 --> 01:11:35.608
kilometers power. So I value from a continuous, very album.
And of course, this kind of calculation that we have seen
01:11:35.608 --> 01:11:44.576
here only works for discrete variables. So what is the case
if we are dealing with continuous random barriers. So we
01:11:44.576 --> 01:11:53.052
deal with continuous, random variables, we can do the same
calculations in general that we did. But instead of having
01:11:53.052 --> 01:12:00.806
probabilities, we have to deal with probability density
functions. And instead of some summing up, or what probabilities
01:12:00.806 --> 01:12:09.089
we have to integrate over these terms. That is the only
difference, though, these equations are actually the same that
01:12:09.089 --> 01:12:17.407
we have derived for the discrete case. Now, the first one
describes the innovation step. The second one describes a
01:12:17.407 --> 01:12:29.788
prediction step. But now we just replaced the crisis. Discreet,
random variable probabilities by probability density
01:12:29.788 --> 01:12:39.173
functions. But the disadvantage in this general case is
that well doing these calculations here. Specially these
01:12:39.173 --> 01:12:49.370
integrations often lead to terms that are either hard to solve
analytical, to integrate analytically or even impossible
01:12:49.370 --> 01:12:59.505
to integrate analytically. That is the disadvantage. But the
good message is that for one case, at least for one case,
01:12:59.505 --> 01:13:09.195
it is possible to solve all these analytical these intervals
in analytically. And this is the case in when we are
01:13:09.195 --> 01:13:18.187
dealing with so called linear gaotion models. What are linear
gauge models? while they are linear and they are so
01:13:18.187 --> 01:13:27.198
Gaugeian refers to the noise. The noise should be distributed
according to a Gulf and a normal distribution, and not to
01:13:27.198 --> 01:13:35.236
something else, but only to a caution distribution and the
system dynamics. So the dependence between the future um
01:13:35.236 --> 01:13:42.991
state variables and the present state variables should be
linear, as well as the dependence between the observations and
01:13:42.991 --> 01:13:52.506
the state variables should be linear. So that means such
a system is linear calcium. If we can right this state
01:13:52.506 --> 01:14:04.069
transition equation like that. This future state is to a
matrix times vector modification. So A is a matrix with fixed
01:14:04.069 --> 01:14:14.629
values independent of the current state is a
current state factor then ut is an offset so and it
01:14:14.629 --> 01:14:24.827
doesn't matter how you calculate the offset as long as it is
independent of the state variables. So this offset might be
01:14:24.827 --> 01:14:33.337
just a constant offset. This offset might be determined from
some control input of your system doesn't matter. Just some
01:14:33.337 --> 01:14:45.291
offset that is independent of the present state. You know,
Plus some noise excellent episode on T is a noise term
01:14:45.291 --> 01:14:55.139
that should be taken from the Gaugeian distribution with Sierra
Mean Zero mean caution distribution. And the measurement
01:14:55.139 --> 01:15:03.768
equation must be written like that. So the measurement
vector is equal to a matrix H, T that contains just some
01:15:03.768 --> 01:15:12.137
Constance, which are independent of the state where of the
state were times the state vector plus tell her Ted
01:15:12.137 --> 01:15:22.101
that he also is some noise term may be the sensor noise and
the centre noise must also be taken from a zero mean caution
01:15:22.101 --> 01:15:32.561
distribution. Well, if this is to for your system that
you want to model. And furthermore, okay, that is
01:15:32.561 --> 01:15:42.149
what I already said this is all everything that I already
said. If this is true. And furthermore, you assume that
01:15:42.149 --> 01:15:52.979
your initial state distribution is taken from . Then all
these equations are solvable in an analytical way, and all
01:15:52.979 --> 01:16:01.941
the probability distributions that occur in this calculation
are always caution distributions. Again, that means then
01:16:01.941 --> 01:16:09.309
the calculations that we did the prediction step
takes distributions and yields another caution
01:16:09.309 --> 01:16:17.382
distribution. And the innovation step as well takes a caution
distribution in a measurement and yields another caution
01:16:17.382 --> 01:16:25.479
distribution. It means then the whole process just map
sculpture distributions on two caution distributions So.
01:16:25.489 --> 01:16:35.027
Some remarks here yeah. Eighteen models, the transition from
state to state might vary from time to time. Yeah, that is
01:16:35.027 --> 01:16:45.283
true but it must not depend on the present state. A
beauty might also vary from time to time, might depend on
01:16:45.283 --> 01:16:56.716
whatever, but not on the state variables. Absilty is this
white gauge noise does this zero mean a ocean noise @unoise@
01:16:56.716 --> 01:17:08.137
@unoise@ so a white ocean noise means garage noise with Sierra
Mean. Is the matrix of the transition
01:17:08.137 --> 01:17:20.434
noise that must be given might also depend on the time, but
it must not at all depend on the state variables was Oz, or
01:17:20.434 --> 01:17:30.680
something like that. And then Delta T is the measurement
noise or sense of noise, and it is modeled as well as white.
01:17:30.689 --> 01:17:41.317
That means zero mean gosh noise. Rt is the the
matrix of the so it describes how reliable the sensor
01:17:41.317 --> 01:17:53.173
is. It might vary from time to time, but it must not at all
depend on the state variables, nor on the measurement. So at
01:17:53.173 --> 01:18:00.695
least theoretically, not so what you find in practice is that
it often depends on on the measurement itself, but from a
01:18:00.695 --> 01:18:09.629
theoretical point of view, it is not allowed. So it might
depend on the time, but it must not depend on the measurement
01:18:09.629 --> 01:18:17.953
itself, nor on the state, the current state. You clearly see
this. These are linear equations, therefore linear gauge
01:18:17.953 --> 01:18:29.565
morals. And you see here, we are dealing only with caution
distributions. So yeah low let us make an example
01:18:29.565 --> 01:18:39.203
let us conclude with this example. So again, we assume
Macar that moves Wisconsin velocity. We know that we can
01:18:39.203 --> 01:18:47.618
model the state of this car, knowing the present position X,
t and the present velocity of the car @unoise@ that. Means
01:18:47.618 --> 01:18:57.842
we can model that means we can also make predict the future
position of the car one as x T plus some deltai, which
01:18:57.842 --> 01:19:08.519
is a time interval from now to the next point in time. So if
camera provides thirty images per second, then this delta t
01:19:08.519 --> 01:19:16.746
is thirty three milliseconds. For instance, the time
interval between two measurements times we tea the presence
01:19:16.746 --> 01:19:27.697
velocity times some random noise in the position and Vit the
velocity, the B, T plus one. The next velocity is equal to
01:19:27.697 --> 01:19:37.779
the present velocity, plus some random noise in the velocity
so that means this is a time interval. That is what I
01:19:37.779 --> 01:19:48.149
already said. Okay, that means S, T, F, S, D contains X, T
and V, T than we can rewrite % um this state transition as
01:19:48.149 --> 01:19:57.559
well. This matrix times the state vector times an offset vector
of zero, zero. In this case, times @unoise@ um, a random
01:19:57.559 --> 01:20:07.753
noise term that contains the random noise in the position and
the velocity now. So we see that this has exactly the form
01:20:07.753 --> 01:20:17.185
that we need for such a linear Gulf model @unoise@ Ah law and
the measurement. Well, let us assume we have a binoculars
01:20:17.185 --> 01:20:26.546
system here that is measuring the position of the car. Now,
then we might say the measurement that we get is equal to
01:20:26.546 --> 01:20:35.764
the position plus some random noise or measurement
noise @unoise@ and we can rewrite that in a matrix times the
01:20:35.764 --> 01:20:45.579
state rector multiplication term. So this is a matrix of one
role to column matrix H, T, plastic delta tea. That is the
01:20:45.579 --> 01:20:53.788
noise. That means this measurement equation has exactly the
form that we need for linear system @unoise@ and if he
01:20:53.788 --> 01:21:01.555
assumed that the Delta T distribution is distributed according
to gulsion. And the t is distributed according to
01:21:01.555 --> 01:21:05.949
the @unoise@ we are faced
with a linear Gaugeian model.
01:21:06.210 --> 01:21:16.042
So I think that is a good point um to stop for today. And the
next time we can continue and derive the filter equations
01:21:16.042 --> 01:21:19.089
for these linearc ocean models.