1 00:00:04,070 --> 00:00:07,800 In this video, we're going to have a deeper look at the unscented transform. 2 00:00:07,820 --> 00:00:13,350 We're going to go into how it works and help to explain how it's useful for the common filter. 3 00:00:14,900 --> 00:00:21,530 So the answer to transform is, in a way approximating a nonlinear transformation of a probability distribution 4 00:00:21,560 --> 00:00:23,600 as a Gaussian distribution. 5 00:00:25,050 --> 00:00:30,780 So assume that we have a probability distribution for a random variable vector, so we have a normal 6 00:00:30,780 --> 00:00:38,010 distribution or Gaussian distribution with a main of exper and covariance of our Sigma X. This describes 7 00:00:38,010 --> 00:00:44,430 a random variable vector now given a nonlinear transform that we want to apply to the distribution. 8 00:00:44,670 --> 00:00:50,080 So let's say that we have a function that takes in a X variable and produces a Y variable. 9 00:00:50,940 --> 00:00:56,970 We want to attain the Gaussian approximation of the resulting distribution for y the random variable 10 00:00:57,300 --> 00:01:03,420 that is approximately a normal distribution with mean y bar and covariance sigma y. 11 00:01:04,110 --> 00:01:09,450 So basically we want to approximate how we can transform this random variable vector through this nonlinear 12 00:01:09,450 --> 00:01:13,380 function to approximate this Gaussian distribution over here. 13 00:01:14,670 --> 00:01:19,620 So, for example, we can actually carry out this procedure numerically and we'll go through the steps 14 00:01:19,620 --> 00:01:24,500 now, so one way is that we can generate any samples from the original distribution. 15 00:01:24,510 --> 00:01:29,610 So basically we have this normal distribution for with a current main and covariance and we want to 16 00:01:29,610 --> 00:01:36,780 generate the random samples of the random variable that that X and we're going to do this for I equals 17 00:01:36,780 --> 00:01:38,310 one to end times. 18 00:01:38,310 --> 00:01:43,670 So we're going to come up with any different variables sampled from this distribution over here. 19 00:01:44,580 --> 00:01:50,160 Now, for each of these samples X I, we want to apply the non-linear transform to find the corresponding 20 00:01:50,160 --> 00:01:51,660 Y I value. 21 00:01:51,900 --> 00:01:58,290 So basically we take the output of these random samples, put them into this function F and then we 22 00:01:58,290 --> 00:02:02,820 get a number of we get N outputs of this output function here. 23 00:02:03,690 --> 00:02:11,340 Now we want to fit a Gaussian to the sample data points to obtain a Gaussian approximation of the distribution 24 00:02:11,340 --> 00:02:12,730 of our sample points. 25 00:02:13,140 --> 00:02:16,200 So basically all this is is the calculating machine. 26 00:02:16,230 --> 00:02:22,230 So this is the expectation operator to get Y bar and then we calculate the covariance, basically a 27 00:02:22,230 --> 00:02:28,410 difference of the samples from the main and we calculate the covariance, we get our sigma y and then 28 00:02:28,410 --> 00:02:33,720 these two parameters is a main and the covariance basically gives us the parameters for this normal 29 00:02:33,840 --> 00:02:39,300 distribution that basically approximates this distribution of our Y sample points. 30 00:02:40,920 --> 00:02:43,380 So that's how we would carry out the procedure numerically. 31 00:02:44,310 --> 00:02:47,280 So now let's have a look at a more concrete example. 32 00:02:47,680 --> 00:02:53,760 Let's have a look at a numerical example of a non-linear probability transformation or a common problem 33 00:02:53,760 --> 00:03:00,300 of transforming a range and bearing in system or measurement into a Cartesian coordinate frame. 34 00:03:00,720 --> 00:03:07,320 So let's generate a thousand samples from the Gaussian distribution as shown here with main expert and 35 00:03:07,320 --> 00:03:15,750 covariance Sigma X, where in this case the main vector consists of a range and bearing and it's going 36 00:03:15,750 --> 00:03:22,620 to have a main value of 100 meters for the range and for PI over four, four or forty five degrees for 37 00:03:22,620 --> 00:03:23,220 the bearing. 38 00:03:24,150 --> 00:03:29,520 The covariance matrix can also be set up to be a diagonal matrix, with the uncertainty for the range 39 00:03:29,520 --> 00:03:36,990 being five meters squared for the range variance or PI over seven radians squared for the bearing uncertainty. 40 00:03:37,710 --> 00:03:42,710 So if we put a sample of the thousand points that we generate, we might look something like this. 41 00:03:43,380 --> 00:03:50,040 So we have an ellipse for the unscented distribution for our random variable X that has a normal distribution 42 00:03:50,040 --> 00:03:56,880 or main export and covariance Sigma X, so the center point on the range axis is going to be at 100 43 00:03:56,880 --> 00:04:03,570 meters and the center point for the bearing is going to be at 45, which is what we've set up over here. 44 00:04:03,870 --> 00:04:09,450 And you can see that we've generated a thousand points and they all lie within this ellipse for the 45 00:04:09,450 --> 00:04:10,110 uncertainty. 46 00:04:12,480 --> 00:04:18,810 Now we're going to transform those 1000 points using a transformation function and basically this function 47 00:04:18,810 --> 00:04:20,930 is going to be this equation here. 48 00:04:20,940 --> 00:04:24,360 So we take the range and bearing measurement or one system. 49 00:04:24,360 --> 00:04:30,540 We put it into these two trigonometry equations to calculate the Cartesian coordinates of X and Y. 50 00:04:32,190 --> 00:04:38,790 Once we do that, we want to then fit a Gaussian to the Cartesian coordinate frame, so we apply the 51 00:04:38,790 --> 00:04:45,330 main equation here and we apply the covariance equation here to fit basically a normal distribution 52 00:04:45,330 --> 00:04:47,760 or a Gaussian, the lips to the data. 53 00:04:48,330 --> 00:04:52,590 So if we do that, we'll end up with the several points that look like this. 54 00:04:53,640 --> 00:04:55,610 So here we have the transform sample points. 55 00:04:55,610 --> 00:05:00,240 So all these red crosses correspond to one of the blue crosses in the previous diagram. 56 00:05:00,660 --> 00:05:06,810 And you can see from this diagram here, you can say they're a very nonlinear shape for the range and 57 00:05:06,810 --> 00:05:07,200 bearing. 58 00:05:07,200 --> 00:05:09,390 And this is what we expected to actually happen. 59 00:05:09,390 --> 00:05:15,540 Since we have such a large bearing on certainty, it means that we've got quite a large nonlinear component 60 00:05:15,540 --> 00:05:18,270 due to these nonlinear terms of the sign and cause. 61 00:05:19,230 --> 00:05:23,880 But we can see that once we fit and ellipse to this, so we end up with a normal distribution, with 62 00:05:24,150 --> 00:05:28,020 a main Y bar and Sigma X Y for the covariance. 63 00:05:28,020 --> 00:05:35,010 Based on these equations here, we can see that this is an a linear approximation of these nonlinear 64 00:05:35,010 --> 00:05:35,750 data points. 65 00:05:35,970 --> 00:05:42,900 And you can see in this case we have a main Cartesian coordinate frame or about 63 and 64 meters for 66 00:05:42,900 --> 00:05:44,160 the X and Y components. 67 00:05:44,940 --> 00:05:48,780 So this is basically the idea behind the onset and transform. 68 00:05:49,080 --> 00:05:54,840 But instead of taking a thousand random sample points and then for the galaxy into this, we want to 69 00:05:54,840 --> 00:05:56,470 do this a bit more intelligently. 70 00:05:57,210 --> 00:05:59,490 So this is where the unscented transform comes in. 71 00:06:00,120 --> 00:06:04,460 We can approximate the new distribution by randomly sampling, as we've just done. 72 00:06:06,180 --> 00:06:11,310 However, can we do this in a more intelligent way by selecting a minimum set of key points, a sample 73 00:06:11,340 --> 00:06:14,040 which provide us as much information as possible? 74 00:06:14,850 --> 00:06:20,250 So the unseen and transform is about selecting these key single points to capture the distribution shape 75 00:06:20,430 --> 00:06:22,420 with a minimum number of points used. 76 00:06:22,680 --> 00:06:25,530 So this is where it becomes more computationally efficient. 77 00:06:25,680 --> 00:06:31,410 So rather than taking a thousand points or even more, we can generate just a few minimum points of 78 00:06:31,410 --> 00:06:37,080 similar points and propagate them through the nonlinear model to actually come up with a better estimate 79 00:06:37,200 --> 00:06:40,080 of the final resulting Gaussian distribution. 80 00:06:41,270 --> 00:06:46,280 The signal points are going to be based on the square root of the variance, so this is why they get 81 00:06:46,310 --> 00:06:51,110 given called Sigma, because it's based on the square root of the covariance, which is the standard 82 00:06:51,500 --> 00:06:53,480 deviation, which is normally called sigma. 83 00:06:54,050 --> 00:06:57,230 So the unscented transform is as follows. 84 00:06:58,690 --> 00:07:06,740 We want to let explained by one random variable vector with main exper and covariance P so n here is 85 00:07:06,740 --> 00:07:10,520 the number of states or the dimension of the state vector X. 86 00:07:10,960 --> 00:07:17,080 So if we graph this, this is basically saying we have a normal distribution of X bar and covariance 87 00:07:17,080 --> 00:07:17,770 peso. 88 00:07:17,770 --> 00:07:24,060 X Bar is the center point here and P defines the uncertainty elipse given by over here. 89 00:07:25,540 --> 00:07:31,810 We want to choose to end SGML points where Excite denotes the sigma point and we're going to choose 90 00:07:31,810 --> 00:07:34,410 these single points using the following equation. 91 00:07:34,840 --> 00:07:41,470 We basically want each sigma point to be the main vector plus a delta amount based on the number of 92 00:07:41,470 --> 00:07:41,920 Sigma Point. 93 00:07:41,920 --> 00:07:46,600 It is where I goes from one all the way up to obviously to N. 94 00:07:47,920 --> 00:07:54,550 So for the first and single points, the Delta amount, for the single point, I is just going to be 95 00:07:54,580 --> 00:08:00,320 the eighth column of the square root of the covariance matrix multiplied by the number of days end. 96 00:08:00,730 --> 00:08:06,160 So this means that the Doderer Vector amount for each single point is just the column of the square 97 00:08:06,160 --> 00:08:07,580 root of the covariance matrix. 98 00:08:08,140 --> 00:08:09,970 So you're looking at this example over here. 99 00:08:10,690 --> 00:08:16,810 The square root of this uncertainty ellipse here is going to be basically from the main plus this direction 100 00:08:16,810 --> 00:08:18,520 over here to give us this sigma point. 101 00:08:18,910 --> 00:08:22,390 And for the second single point, because we have it two dimensions. 102 00:08:22,390 --> 00:08:26,560 So it's two states is going to be the main plus this amount over here. 103 00:08:26,830 --> 00:08:31,960 So these are going to give us two positive signal points now for the remaining segments. 104 00:08:31,990 --> 00:08:35,580 So for eye is equal to and plus one all the way up to to end. 105 00:08:35,830 --> 00:08:41,680 So basically each of the Delta amounts is just going to be a negative of this column of the square root 106 00:08:41,680 --> 00:08:42,750 of the covariance matrix. 107 00:08:43,030 --> 00:08:45,970 So that will give us these two sigma points down here. 108 00:08:47,020 --> 00:08:54,220 So as you can see, the Sigma points pretty much define the plus and minus of the different axes majors 109 00:08:54,220 --> 00:08:55,100 of the Ellipse. 110 00:08:55,660 --> 00:09:00,580 So this turns out to be a good approximation of the shape of the uncertainty covariance. 111 00:09:00,580 --> 00:09:05,920 So that way you can use these points to transform it, to get the new uncertainty ellipse from the transform 112 00:09:05,920 --> 00:09:06,580 equations. 113 00:09:07,150 --> 00:09:10,780 So now let's look at how to approximate the main from the sigma points. 114 00:09:11,170 --> 00:09:16,630 So basically, for each of the signal points, we want to put them into the nonlinear transformation 115 00:09:16,630 --> 00:09:17,650 that we want to apply. 116 00:09:18,100 --> 00:09:20,180 So basically, this is the original Sigma Point. 117 00:09:20,350 --> 00:09:25,720 We put it into the nonlinear transformation and we get the Transform Sigma Point up here and we do this 118 00:09:25,720 --> 00:09:27,850 for I equals one all the way up to to end. 119 00:09:28,420 --> 00:09:31,460 So on this diagram here, that will be the same as taking each point. 120 00:09:31,480 --> 00:09:32,890 So let's take this point over here. 121 00:09:33,100 --> 00:09:37,600 We put it into the anomaly and transform and it transforms it up to this point over here. 122 00:09:37,990 --> 00:09:43,390 And we do that for all the other points or the signal points to calculate all the transform sigma points. 123 00:09:44,290 --> 00:09:49,480 So once we've transformed all the sigma points, we can start to estimate the mean of the new probability 124 00:09:49,480 --> 00:09:50,170 distribution. 125 00:09:50,680 --> 00:09:55,270 And to do this, we can look at the weighted mane of the transform data points. 126 00:09:55,760 --> 00:10:01,210 So we're going to have this weighting matrix here, which is going to be one over to N, and we're going 127 00:10:01,210 --> 00:10:05,000 to multiply that by each of the Sigma points and we're going to sum it all up. 128 00:10:05,380 --> 00:10:07,300 So basically you end up with this equation here. 129 00:10:07,540 --> 00:10:12,900 So this equation here is going to calculate the mean all the way to Maine of all the sigma points. 130 00:10:13,420 --> 00:10:19,720 So on this diagram over here, that would produce the main point that looks something like here, the 131 00:10:19,720 --> 00:10:25,330 final step in the transformation process is now to recover the covariance or approximate the covariance 132 00:10:25,330 --> 00:10:26,620 from these weighted samples. 133 00:10:27,010 --> 00:10:30,430 And to do this, we're going to use these equations here. 134 00:10:30,910 --> 00:10:33,540 So all this is basically just a weighted covariance. 135 00:10:33,550 --> 00:10:39,790 We use the same weighting matrix from what we used in the main, and we calculate the covariance and 136 00:10:39,790 --> 00:10:41,920 we end up with this equation here. 137 00:10:42,400 --> 00:10:48,190 So if we evaluate this equation here, it would give us the uncertainty ellipse for this transform distribution. 138 00:10:48,190 --> 00:10:49,410 And it looks something like this. 139 00:10:50,380 --> 00:10:56,500 So the mean and covariance give us a approximation of the normal distribution which would fit to these 140 00:10:56,500 --> 00:10:57,160 data points. 141 00:10:57,190 --> 00:11:01,420 So basically we have the main and the covariance and we assume it's a normal distribution. 142 00:11:02,200 --> 00:11:07,450 So this is how we can take an original probability distribution, generate the single points, transform 143 00:11:07,450 --> 00:11:13,210 them through the nonlinear, transform and then recover an approximation of the Gaussian distribution 144 00:11:13,300 --> 00:11:15,760 that describes the nonlinear transformation. 145 00:11:17,440 --> 00:11:22,700 So the procedure we showed before is for the uncited transform in the space form. 146 00:11:23,260 --> 00:11:26,160 How are these different versions of the unscented and transform? 147 00:11:26,170 --> 00:11:30,070 And we're going to show a more generalized version of the onset and transform. 148 00:11:30,220 --> 00:11:34,780 And this is a version that's usually used inside typical filters. 149 00:11:35,530 --> 00:11:40,600 So the general answer, transform makes a few modifications to the algorithm that we've shown on the 150 00:11:40,600 --> 00:11:41,530 previous slides. 151 00:11:42,800 --> 00:11:49,760 So the basic answer to transform is third order, accurate for the approximation of the main and covariance 152 00:11:49,760 --> 00:11:55,640 of the transformation, it is possible to reduce the higher order errors for the approximation by using 153 00:11:55,640 --> 00:12:01,010 different weightings in the calculations, depending on the type of distribution of the underlying error, 154 00:12:02,090 --> 00:12:07,880 i.e., if the error distribution is Gaussian, then it's possible to reduce the fourth or the error 155 00:12:07,880 --> 00:12:11,180 terms by using an appropriate weighting function. 156 00:12:12,600 --> 00:12:17,440 The general unscented transform allows for different weighting functions to be unemployed. 157 00:12:17,790 --> 00:12:23,430 So this is what actually is typically used inside common filtering that uses the answer to transform. 158 00:12:24,490 --> 00:12:31,960 So the general answer, the transformation is as follows, so we want to generate two and plus one single 159 00:12:31,960 --> 00:12:36,910 points, so instead of just using two and similar points, we're going to add an extra sigma point. 160 00:12:37,030 --> 00:12:39,490 So we're going to use two and plus one single point. 161 00:12:40,000 --> 00:12:45,070 And basically all what we are going to do is that instead of starting asking the points from one, we're 162 00:12:45,070 --> 00:12:50,200 going to start them from zero and at zero, the Delta amount is just going to be zero. 163 00:12:50,560 --> 00:12:58,060 So the Zero Sigma Point is just the main of the distribution and the rest of the calculation is follows. 164 00:12:58,060 --> 00:13:02,410 Pretty similar, except instead of multiplying the covariance matrix before we take the square root 165 00:13:02,410 --> 00:13:05,840 by PN, we're going to multiply it by and plus Kapa. 166 00:13:06,010 --> 00:13:12,100 So this cappa here is a scaling concept that we're going to change to get different effects based on 167 00:13:12,100 --> 00:13:13,540 the underlying distribution. 168 00:13:15,900 --> 00:13:21,450 So with this new definition, we have to change the way we calculate the weights for the weddings inside 169 00:13:21,450 --> 00:13:27,390 the main and the covariance calculations, so the wait for as Earth single point is just going to be 170 00:13:27,390 --> 00:13:29,900 this cappa divided by N plus Kapa. 171 00:13:30,330 --> 00:13:36,390 And for the rest of the sigma points, we're just going to have the waiting to be one over two times 172 00:13:36,390 --> 00:13:37,410 and plus Kapa. 173 00:13:38,670 --> 00:13:43,500 Once we've updated the Sigma Point and the weighting, the rest of the calculation follows exactly the 174 00:13:43,500 --> 00:13:44,030 same. 175 00:13:44,070 --> 00:13:50,370 We basically calculate the mean using our weighted, using our weighted average and we calculate the 176 00:13:50,370 --> 00:13:53,010 covariance using our weighted covariance. 177 00:13:54,970 --> 00:13:59,860 Now, for when we use a Gaussian distribution, the following weights have been shown to improve the 178 00:13:59,860 --> 00:14:04,520 accuracy of the calculation, to reduce the fourth error terms down to zero. 179 00:14:04,750 --> 00:14:11,410 And this is when we set Kapa Eagles' to three minus N, and of course, this only works when N plus 180 00:14:11,410 --> 00:14:12,870 cappa does not equal to zero. 181 00:14:13,960 --> 00:14:18,580 So this is how the general unscented transformation works and this is what they're going to be using 182 00:14:18,580 --> 00:14:20,710 inside or out filtering examples.