부드러운 GPS 데이터
GPS 데이터로 작업하고 있으며 매 초마다 값을 가져오고지도에 현재 위치를 표시합니다. 문제는 때때로 (특히 정확도가 낮을 때) 값이 많이 달라져 현재 위치가지도의 먼 지점 사이에서 "점프"하는 것입니다.
이것을 피할 수있는 쉬운 방법이 궁금합니다. 첫 번째 아이디어로 특정 임계 값을 초과하여 정확하게 값을 버리는 것에 대해 생각했지만 더 좋은 방법이 있다고 생각합니다. 프로그램이 이것을 수행하는 일반적인 방법은 무엇입니까?
찾고있는 것을 Kalman Filter 라고합니다 . 탐색 데이터 를 매끄럽게 하는 데 자주 사용됩니다 . 반드시 사소한 것은 아니며 많은 조정이 가능하지만 매우 표준적인 접근 방식이며 잘 작동합니다. 있습니다 KFilter 라이브러리 는 C ++ 구현 가능합니다.
내 다음 폴백은 최소 제곱에 적합 합니다. 칼만 필터는 속도를 고려하여 데이터를 부드럽게하는 반면 최소 자승법은 위치 정보 만 사용합니다. 그럼에도 불구하고 구현하고 이해하는 것이 훨씬 간단합니다. GNU Scientific Library가 이것을 구현 한 것으로 보입니다 .
이 상황에 정확히 사용할 수있는 간단한 칼만 필터가 있습니다. Android 기기에서 수행 한 작업에서 비롯된 것입니다.
일반적인 칼만 필터 이론은 공분산 행렬로 표시되는 추정치의 정확도와 함께 벡터에 대한 추정치에 관한 것입니다. 그러나 Android 기기의 위치를 추정하기 위해 일반적인 이론은 매우 간단한 경우로 줄어 듭니다. Android 위치 제공 업체는 위치를 위도와 경도로 미터 단위로 측정 한 단일 숫자로 지정된 정확도와 함께 제공합니다. 즉, Kalman 필터의 위치가 두 개의 숫자로 측정 되더라도 공분산 행렬 대신 Kalman 필터의 정확도를 단일 숫자로 측정 할 수 있습니다. 또한 위도, 경도 및 미터가 서로 다른 모든 단위라는 사실은 무시할 수 있습니다. 스케일링 계수를 Kalman 필터에 넣어 모두 동일한 단위로 변환하면,
코드는 현재 위치의 최고 추정치가 마지막으로 알려진 위치라고 가정하기 때문에 개선 될 수 있으며, 누군가가 이동하는 경우 Android 센서를 사용하여 더 나은 추정치를 생성 할 수 있어야합니다. 이 코드에는 초당 미터 단위로 표시되는 단일 자유 매개 변수 Q가 있으며, 새로운 위치 추정치가 없을 때 정확도가 얼마나 빨리 저하되는지를 설명합니다. Q 파라미터가 높을수록 정확도가 더 빨리 감쇠합니다. 칼만 필터는 일반적으로 정확도가 예상보다 약간 빨리 쇠퇴 할 때 더 잘 작동하므로 Android 전화로 걸을 때 일반적으로 속도가 느리더라도 도보 당 Q = 3 미터가 잘 작동한다는 것을 알았습니다. 그러나 빠른 자동차로 여행하는 경우 훨씬 더 많은 수를 사용해야합니다.
public class KalmanLatLong {
private final float MinAccuracy = 1;
private float Q_metres_per_second;
private long TimeStamp_milliseconds;
private double lat;
private double lng;
private float variance; // P matrix. Negative means object uninitialised. NB: units irrelevant, as long as same units used throughout
public KalmanLatLong(float Q_metres_per_second) { this.Q_metres_per_second = Q_metres_per_second; variance = -1; }
public long get_TimeStamp() { return TimeStamp_milliseconds; }
public double get_lat() { return lat; }
public double get_lng() { return lng; }
public float get_accuracy() { return (float)Math.sqrt(variance); }
public void SetState(double lat, double lng, float accuracy, long TimeStamp_milliseconds) {
this.lat=lat; this.lng=lng; variance = accuracy * accuracy; this.TimeStamp_milliseconds=TimeStamp_milliseconds;
}
/// <summary>
/// Kalman filter processing for lattitude and longitude
/// </summary>
/// <param name="lat_measurement_degrees">new measurement of lattidude</param>
/// <param name="lng_measurement">new measurement of longitude</param>
/// <param name="accuracy">measurement of 1 standard deviation error in metres</param>
/// <param name="TimeStamp_milliseconds">time of measurement</param>
/// <returns>new state</returns>
public void Process(double lat_measurement, double lng_measurement, float accuracy, long TimeStamp_milliseconds) {
if (accuracy < MinAccuracy) accuracy = MinAccuracy;
if (variance < 0) {
// if variance < 0, object is unitialised, so initialise with current values
this.TimeStamp_milliseconds = TimeStamp_milliseconds;
lat=lat_measurement; lng = lng_measurement; variance = accuracy*accuracy;
} else {
// else apply Kalman filter methodology
long TimeInc_milliseconds = TimeStamp_milliseconds - this.TimeStamp_milliseconds;
if (TimeInc_milliseconds > 0) {
// time has moved on, so the uncertainty in the current position increases
variance += TimeInc_milliseconds * Q_metres_per_second * Q_metres_per_second / 1000;
this.TimeStamp_milliseconds = TimeStamp_milliseconds;
// TO DO: USE VELOCITY INFORMATION HERE TO GET A BETTER ESTIMATE OF CURRENT POSITION
}
// Kalman gain matrix K = Covarariance * Inverse(Covariance + MeasurementVariance)
// NB: because K is dimensionless, it doesn't matter that variance has different units to lat and lng
float K = variance / (variance + accuracy * accuracy);
// apply K
lat += K * (lat_measurement - lat);
lng += K * (lng_measurement - lng);
// new Covarariance matrix is (IdentityMatrix - K) * Covarariance
variance = (1 - K) * variance;
}
}
}
조금 늦을 수도 있습니다 ...
필자는 Android와 KalmanLocationManager 를 작성 했는데 ,이 두 곳은 가장 일반적인 위치 제공 업체 인 네트워크와 GPS를 감싸고 데이터를 필터링하고 LocationListener( '실제'제공 업체와 같은) 업데이트를 제공합니다 .
나는 주로 판독 사이에 "보간"하기 위해 사용합니다-예를 들어 100 밀리 초마다 업데이트 (위치 예측)를 수신합니다 (예 : 최대 gps 속도 대신 1 초). 내 위치를 애니메이션 할 때 더 나은 프레임 속도를 제공합니다.
실제로 각 차원마다 위도, 경도 및 고도의 세 가지 칼만 필터를 사용합니다. 어쨌든 그들은 독립적입니다.
이것은 6x6 상태 전이 행렬을 사용하는 대신 3 개의 다른 2x2 행렬을 사용하여 행렬 수학을 훨씬 쉽게 만듭니다. 실제로 코드에서는 행렬을 전혀 사용하지 않습니다. 모든 방정식을 풀고 모든 값은 프리미티브 (이중)입니다.
소스 코드가 작동하고 있으며 데모 활동이 있습니다. 어떤 곳에서는 javadoc이 없어서 유감입니다.
시간당 위치 변경으로 속도를 계산해서는 안됩니다. GPS의 위치가 정확하지 않을 수 있지만 정확한 속도 (5km / h 이상)가 있습니다. 따라서 GPS 위치 스탬프의 속도를 사용하십시오. 또한 대부분의 경우 작동하지만 물론 그렇게해서는 안됩니다.
배송 된 GPS 위치는 이미 Kalman으로 필터링되었으므로 후 처리 과정에서 일반적으로 GPS 칩과 동일한 정보가없는 경우 개선 할 수 없습니다.
부드럽게 할 수 있지만 오류가 발생합니다.
장치가 정지 상태 일 때 위치를 제거하고 점프 위치를 제거하고 일부 장치 / 구성이 제거되지 않도록하십시오.
나는 보통 가속도계를 사용합니다. 단기간에 갑작스런 위치 변화는 높은 가속도를 의미합니다. 이것이 가속도계 원격 측정에 반영되지 않으면 위치를 계산하는 데 사용되는 "최고의 3 개"위성이 변경 되었기 때문일 것입니다 (GPS 텔레 포팅이라고 함).
GPS 텔레 포팅으로 인해 자산이 정지하고 도약 할 때 중심을 점진적으로 계산하면 더 큰 쉘 세트를 효과적으로 교차하여 정밀도를 향상시킬 수 있습니다.
자산이 정지되어 있지 않을 때이를 수행하려면 속도, 방향 및 선형 및 회전 (자이로가있는 경우) 가속도 데이터를 기반으로 다음 위치와 방향을 추정해야합니다. 이것은 유명한 K 필터의 기능입니다. GPS 모듈을 제외한 모든 것을 포함하는 AHRS와 하나를 연결하는 잭으로 하드웨어에서 약 150 달러에 구입할 수 있습니다. 자체 CPU 및 Kalman 필터링 기능이 탑재되어 있습니다. 결과는 안정적이고 꽤 좋습니다. 관성 가이던스는 지터에 대한 내성이 강하지 만 시간이지나면서 표류합니다. GPS는 지터가 발생하기 쉽지만 시간이 흐르면서 표류하지는 않으며 실제로 서로를 보상하기 위해 만들어졌습니다.
더 적은 수학 / 이론을 사용하는 한 가지 방법은 한 번에 2, 5, 7, 10 개의 데이터 포인트를 샘플링하고 이상치 인 것을 결정하는 것입니다. 칼만 필터보다 특이 치의 덜 정확한 측정 값은 다음 알고리즘 을 사용하여 점 사이의 모든 쌍의 현명한 거리를 취하고 다른 것보다 가장 멀리 떨어진 것을 버리는 것입니다. 일반적으로 이러한 값은 대체하려는 외부 값에 가장 가까운 값으로 바뀝니다.
예를 들어
5 개의 샘플 포인트 A, B, C, D, E에서 스무딩
ATOTAL = 거리의 합 AB AC AD AE
BTOTAL = 거리의 합 AB BC BD BE
CTOTAL = 거리의 합 AC BC CD CE
DTOTAL = 거리의 합 DA DB DC DE
ETOTAL = 거리의 합 EA EB EC DE
BTOTAL이 가장 큰 경우 BD = min {AB, BC, BD, BE} 인 경우 B 지점을 D로 바꿉니다.
This smoothing determines outliers and can be augmented by using the midpoint of BD instead of point D to smooth the positional line. Your mileage may vary and more mathematically rigorous solutions exist.
As for least squares fit, here are a couple other things to experiment with:
Just because it's least squares fit doesn't mean that it has to be linear. You can least-squares-fit a quadratic curve to the data, then this would fit a scenario in which the user is accelerating. (Note that by least squares fit I mean using the coordinates as the dependent variable and time as the independent variable.)
You could also try weighting the data points based on reported accuracy. When the accuracy is low weight those data points lower.
Another thing you might want to try is rather than display a single point, if the accuracy is low display a circle or something indicating the range in which the user could be based on the reported accuracy. (This is what the iPhone's built-in Google Maps application does.)
You can also use a spline. Feed in the values you have and interpolate points between your known points. Linking this with a least-squares fit, moving average or kalman filter (as mentioned in other answers) gives you the ability to calculate the points inbetween your "known" points.
Being able to interpolate the values between your knowns gives you a nice smooth transition and a /reasonable/ approximation of what data would be present if you had a higher-fidelity. http://en.wikipedia.org/wiki/Spline_interpolation
Different splines have different characteristics. The one's I've seen most commonly used are Akima and Cubic splines.
Another algorithm to consider is the Ramer-Douglas-Peucker line simplification algorithm, it is quite commonly used in the simplification of GPS data. (http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm)
Going back to the Kalman Filters ... I found a C implementation for a Kalman filter for GPS data here: http://github.com/lacker/ikalman I haven't tried it out yet, but it seems promising.
Mapped to CoffeeScript if anyones interested. **edit -> sorry using backbone too, but you get the idea.
Modified slightly to accept a beacon with attribs
{latitude: item.lat,longitude: item.lng,date: new Date(item.effective_at),accuracy: item.gps_accuracy}
MIN_ACCURACY = 1
# mapped from http://stackoverflow.com/questions/1134579/smooth-gps-data
class v.Map.BeaconFilter
constructor: ->
_.extend(this, Backbone.Events)
process: (decay,beacon) ->
accuracy = Math.max beacon.accuracy, MIN_ACCURACY
unless @variance?
# if variance nil, inititalise some values
@variance = accuracy * accuracy
@timestamp_ms = beacon.date.getTime();
@lat = beacon.latitude
@lng = beacon.longitude
else
@timestamp_ms = beacon.date.getTime() - @timestamp_ms
if @timestamp_ms > 0
# time has moved on, so the uncertainty in the current position increases
@variance += @timestamp_ms * decay * decay / 1000;
@timestamp_ms = beacon.date.getTime();
# Kalman gain matrix K = Covarariance * Inverse(Covariance + MeasurementVariance)
# NB: because K is dimensionless, it doesn't matter that variance has different units to lat and lng
_k = @variance / (@variance + accuracy * accuracy)
@lat = _k * (beacon.latitude - @lat)
@lng = _k * (beacon.longitude - @lng)
@variance = (1 - _k) * @variance
[@lat,@lng]
I have transformed the Java code from @Stochastically to Kotlin
class KalmanLatLong
{
private val MinAccuracy: Float = 1f
private var Q_metres_per_second: Float = 0f
private var TimeStamp_milliseconds: Long = 0
private var lat: Double = 0.toDouble()
private var lng: Double = 0.toDouble()
private var variance: Float =
0.toFloat() // P matrix. Negative means object uninitialised. NB: units irrelevant, as long as same units used throughout
fun KalmanLatLong(Q_metres_per_second: Float)
{
this.Q_metres_per_second = Q_metres_per_second
variance = -1f
}
fun get_TimeStamp(): Long { return TimeStamp_milliseconds }
fun get_lat(): Double { return lat }
fun get_lng(): Double { return lng }
fun get_accuracy(): Float { return Math.sqrt(variance.toDouble()).toFloat() }
fun SetState(lat: Double, lng: Double, accuracy: Float, TimeStamp_milliseconds: Long)
{
this.lat = lat
this.lng = lng
variance = accuracy * accuracy
this.TimeStamp_milliseconds = TimeStamp_milliseconds
}
/// <summary>
/// Kalman filter processing for lattitude and longitude
/// https://stackoverflow.com/questions/1134579/smooth-gps-data/15657798#15657798
/// </summary>
/// <param name="lat_measurement_degrees">new measurement of lattidude</param>
/// <param name="lng_measurement">new measurement of longitude</param>
/// <param name="accuracy">measurement of 1 standard deviation error in metres</param>
/// <param name="TimeStamp_milliseconds">time of measurement</param>
/// <returns>new state</returns>
fun Process(lat_measurement: Double, lng_measurement: Double, accuracy: Float, TimeStamp_milliseconds: Long)
{
var accuracy = accuracy
if (accuracy < MinAccuracy) accuracy = MinAccuracy
if (variance < 0)
{
// if variance < 0, object is unitialised, so initialise with current values
this.TimeStamp_milliseconds = TimeStamp_milliseconds
lat = lat_measurement
lng = lng_measurement
variance = accuracy * accuracy
}
else
{
// else apply Kalman filter methodology
val TimeInc_milliseconds = TimeStamp_milliseconds - this.TimeStamp_milliseconds
if (TimeInc_milliseconds > 0)
{
// time has moved on, so the uncertainty in the current position increases
variance += TimeInc_milliseconds.toFloat() * Q_metres_per_second * Q_metres_per_second / 1000
this.TimeStamp_milliseconds = TimeStamp_milliseconds
// TO DO: USE VELOCITY INFORMATION HERE TO GET A BETTER ESTIMATE OF CURRENT POSITION
}
// Kalman gain matrix K = Covarariance * Inverse(Covariance + MeasurementVariance)
// NB: because K is dimensionless, it doesn't matter that variance has different units to lat and lng
val K = variance / (variance + accuracy * accuracy)
// apply K
lat += K * (lat_measurement - lat)
lng += K * (lng_measurement - lng)
// new Covarariance matrix is (IdentityMatrix - K) * Covarariance
variance = (1 - K) * variance
}
}
}
참고URL : https://stackoverflow.com/questions/1134579/smooth-gps-data
'Programming' 카테고리의 다른 글
| ASP.NET 임시 파일 정리 (0) | 2020.06.21 |
|---|---|
| Java가 Throwable의 일반 서브 클래스를 허용하지 않는 이유는 무엇입니까? (0) | 2020.06.21 |
| Build.scala, % 및 %% 기호 의미 (0) | 2020.06.21 |
| 너비 우선 검색을 재귀 적으로 수행 (0) | 2020.06.21 |
| HTML 요소없이 ng-repeat를 사용하는 방법 (0) | 2020.06.21 |