In the previous post, we did not discuss the partial differential equation (PDE) or how to solve it numerically. Specifically, we did not discuss the distance function (time cost) based on which the next data point is selected. In this post we mention it with an example.
We start from a data point whose travel time is frozen i.e. we don't change it again and proceed outwards to the neighboring points from it. We put these neighboring points in a priority queue where the points are sorted based on the minimum travel time. Then the top point in this priority queue is removed which gives the minimum travel time. This point is then frozen. The neighboring points are updated with the Euclidean norm of the gradients. The gradients are along the x,y,z axes and are computed as derivatives (inverse of speed) defined as the difference in the travel time between the new point and the old point on the same axes over a unit distance. We take the maximum of this gradient. The gradients are also taken between the next point and the new point in the normal direction. We take the minimum of this gradient. The Eucledian norm is nothing but a sum of squares just like we measure a hypotenuse. So we take the squares of the maximum and minimum respectively for each of the three axes. This gives us a quadratic in travel time t at the new point and speed v that has a well-defined solution as one of either the travel time at the previous point + (unit-distance / speed) or the next point + (unit-distance/speed). In the fast marching method, we simplify this computation to take forward only direction and at zero-level plane so only x and y co-ordinates.
We repeat this for all other neighboring points around the one we removed from the priority queue.
It might so happen that one or more of the neighboring points are in the active set i.e. in the priority queue. If we take a new point for which we want to compute the travel time as the center, then there are four neighbours around it and one of them is the smallest of all the trial values. Then there are four cases we need to consider. 1) where none of the neighbors are in the active set, 2) one of the neighbors is in the active set 3) two of the neighbors are in the active set and 4) all three of these neighbors are in the active set.
In the case where none of the neighbors are in the active set, the travel time of the new point is the sum of that of A and the inverse speed function f (f is based on the unit-distance).
In the case where one of the neighboring points b is already in the active set, then we know that its travel time is more than the one we just removed and also that the travel time of the new point will be lesser than the sum of the travel time for b and the inverse speed function f.
If two of the neighbors are in the active set and one of them is frozen, then this point is in the forward direction and will be the contributor to the inverse speed function since the frozen value will not be changed and this degenerates to the case 1)
If three of the neighbors are in the active set, the smallest values in each co-ordinate direction is taken and this degenerates to the cases discussed above.
Thus we obtain the travel times of the neighboring points as well and add them to the priority queue
The neighboring points are typically referred to as the narrow band and we locate the grid point with the minimum travel time.
We start from a data point whose travel time is frozen i.e. we don't change it again and proceed outwards to the neighboring points from it. We put these neighboring points in a priority queue where the points are sorted based on the minimum travel time. Then the top point in this priority queue is removed which gives the minimum travel time. This point is then frozen. The neighboring points are updated with the Euclidean norm of the gradients. The gradients are along the x,y,z axes and are computed as derivatives (inverse of speed) defined as the difference in the travel time between the new point and the old point on the same axes over a unit distance. We take the maximum of this gradient. The gradients are also taken between the next point and the new point in the normal direction. We take the minimum of this gradient. The Eucledian norm is nothing but a sum of squares just like we measure a hypotenuse. So we take the squares of the maximum and minimum respectively for each of the three axes. This gives us a quadratic in travel time t at the new point and speed v that has a well-defined solution as one of either the travel time at the previous point + (unit-distance / speed) or the next point + (unit-distance/speed). In the fast marching method, we simplify this computation to take forward only direction and at zero-level plane so only x and y co-ordinates.
We repeat this for all other neighboring points around the one we removed from the priority queue.
It might so happen that one or more of the neighboring points are in the active set i.e. in the priority queue. If we take a new point for which we want to compute the travel time as the center, then there are four neighbours around it and one of them is the smallest of all the trial values. Then there are four cases we need to consider. 1) where none of the neighbors are in the active set, 2) one of the neighbors is in the active set 3) two of the neighbors are in the active set and 4) all three of these neighbors are in the active set.
In the case where none of the neighbors are in the active set, the travel time of the new point is the sum of that of A and the inverse speed function f (f is based on the unit-distance).
In the case where one of the neighboring points b is already in the active set, then we know that its travel time is more than the one we just removed and also that the travel time of the new point will be lesser than the sum of the travel time for b and the inverse speed function f.
If two of the neighbors are in the active set and one of them is frozen, then this point is in the forward direction and will be the contributor to the inverse speed function since the frozen value will not be changed and this degenerates to the case 1)
If three of the neighbors are in the active set, the smallest values in each co-ordinate direction is taken and this degenerates to the cases discussed above.
Thus we obtain the travel times of the neighboring points as well and add them to the priority queue
The neighboring points are typically referred to as the narrow band and we locate the grid point with the minimum travel time.
No comments:
Post a Comment