24

введите сюда описание изображения

Есть вот такой набор точек, каждая точка представляет собой gps координату автобуса (x,y), у каждой точки есть timestamp. На построенном графике видны явные ошибки измерения. Как их можно убрать? Решение должно быть простым, так как всего координат около 100 тысяч. Интересует идея, но желательно, чтобы ее можно было без особых проблем реализовать средствами Java

Пример исходных данных:

  1447037729  <tab>  3054.619968  <tab>  2409.828279  <tab>  570d8

Первое поле - UNIX-время, второе и третье - (x,y) соответственно, четвертое - идентификатор автобуса (автобусов около 50ти) . Исходные данные : https://drive.google.com/file/d/0B4bA9d5B_O_BcVpPUXpYTmZBUFE/view

15
  • убрать шум можно с помощью OpenCV, threshold. пример тут
    – Stack
    2 янв 2016 в 19:18
  • @Stack изображение просто как иллюстрация того, что происходит. Нужен алгоритм именно на наборе точек (x,y), чтобы после работы этого алгоритма оставался набор относительно точных пар (x,y).
    – Simankov
    2 янв 2016 в 20:01
  • Похожий вопрос: ru.stackoverflow.com/questions/478422/…
    – sercxjo
    2 янв 2016 в 20:16
  • 2
    Посчитать расстояние между точками, максимальная скорость автобуса допустим известна. (Может ли он за секунду переместиться на км?) Выкинуть из входных данных невероятные перемещения.
    – Sergey
    3 янв 2016 в 5:38
  • 2
    Может учесть реальные координаты дорог, по которым может ехать автобус?
    – avp
    3 янв 2016 в 10:39

5 ответов 5

10

Приведённый набор точек - это две зависимости: x(t) и y(t), и по каждой идёт импульсный шум. К таким данным идеально подходит алгоритм медианной обработки в скользящем окне на 7-9 элементов, когда i-тый во времени элемент заменяется на медианное значение элементов с номерами (i-h,i+h) при h=3...4.
Обработку для x(t) и y(t) следует проводить независимо, после чего подменить ими исходные массивы.

Обработка эффективна при высоком уровне импульсной помехи (в тестовом примере искажена третья часть данных). Дополнительный плюс - что сохраняется формат исходных данных. Обработка краёв ведётся на окнах меньшего размера.
Минусы обработки в скользящем окне проявляются при разворотах последовательности, поскольку выступы и провалы шириной меньше h выполаживаются.

В демо-программе представлена рекуррентная сортировка массива в окне. Для этого точки, лежащие между старым (удаляемым) и новым (добавляемым) элементами, сдвигаются в сторону старого элемента, после чего на место крайнего из возникших дубликатов записывается новый элемент. Это резко снижает вычислительные затраты.

Демо-программа (PHP):

function print_a($a, $name){
    print("$name: ");
    foreach($a as $item){
        printf("%2d, ",$item);
    }
}   

function slide_median($h, $a){
    $size = count($a);
    $result = [];
    $slide = [];
    array_push($slide, reset($a));
    array_push($result,$slide[0]);
    print_a($slide, "&emsp;Сортировка в окне");
    print_a($result, "<br>Массив результата");

    for($i=1; $i<=$h; $i++){
        array_push($slide, next($a), next($a));
        sort($slide);
        array_push($result, $slide[$i]);    
        print_a($slide, "&emsp;Сортировка в окне");
        print_a($result, "<br>Массив результата");
    }

    for($i=0; $i < $size-2*$h-1; $i++){
        $old = $a[$i];
        $new = $a[$i+2*$h+1];
        if($old < $new){
            for($key = 0; $key <= 2*$h; $key++){
                if($new < $slide[$key]){
                    break;
                }
                if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key] = $slide[$key+1]; 
            }
            $slide[$key-1] = $new;

        }
        if($old > $new){
            for($key = 2*$h; $key >= 0; $key--){
                if($new > $slide[$key]){
                    break;
                }
                if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key] = $slide[$key-1]; 
            }                   
            $slide[$key+1] = $new;
        }
        array_push($result, $slide[$h]);            
        print("&emsp;old = $old, new =$new");
        print_a($slide, "&emsp;Сортировка в окне");
        print_a($result, "<br>Массив результата");
    }

    for($i = $h-1; $i > 0; $i--){
        $slide = array_slice($a, $size-2*$i-1, 2*$i+1);
        sort($slide);
        array_push($result, $slide[$i]);
        print_a($slide, "&emsp;Сортировка в окне");
        print_a($result, "<br>Массив результата");
    }
    $slide = [$a[$size-1]];
    array_push($result, $slide[0]);
    print_a([end($a)], "&emsp;Сортировка в окне");
    print_a($a, "<br><br>Исходный массив: ");
    print_a($result, "<br>Массив результата");

    return $result;
};

$a = range(20, 40);
foreach($a as &$item){
    $item += 5*mt_rand(-1,1)*(int)(mt_rand(0,199)/100);
}
print_a($a, "Исходный массив: ");
slide_median(3, $a);

Результаты (импульсный шум, амплитуда 5):

Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35,  Сортировка в окне: 20, 
Массив результата: 20,  Сортировка в окне: 20, 21, 22, 
Массив результата: 20, 21,  Сортировка в окне: 19, 20, 21, 22, 23, 
Массив результата: 20, 21, 21,  Сортировка в окне: 19, 20, 20, 21, 21, 22, 23, 
Массив результата: 20, 21, 21, 21,  old = 20, new =27 Сортировка в окне: 19, 20, 21, 21, 22, 23, 27, 
Массив результата: 20, 21, 21, 21, 21,  old = 21, new =28 Сортировка в окне: 19, 20, 21, 22, 23, 27, 28, 
Массив результата: 20, 21, 21, 21, 21, 22,  old = 22, new =29 Сортировка в окне: 19, 20, 21, 23, 27, 28, 29, 
Массив результата: 20, 21, 21, 21, 21, 22, 23,  old = 23, new =30 Сортировка в окне: 19, 20, 21, 27, 28, 29, 30, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27,  old = 19, new =31 Сортировка в окне: 20, 21, 27, 28, 29, 30, 31, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28,  old = 20, new =32 Сортировка в окне: 21, 27, 28, 29, 30, 31, 32, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29,  old = 21, new =28 Сортировка в окне: 27, 28, 28, 29, 30, 31, 32, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29,  old = 27, new =29 Сортировка в окне: 28, 28, 29, 29, 30, 31, 32, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29,  old = 28, new =35 Сортировка в окне: 28, 29, 29, 30, 31, 32, 35, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30,  old = 29, new =36 Сортировка в окне: 28, 29, 30, 31, 32, 35, 36, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31,  old = 30, new =42 Сортировка в окне: 28, 29, 31, 32, 35, 36, 42, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32,  old = 31, new =43 Сортировка в окне: 28, 29, 32, 35, 36, 42, 43, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35,  old = 32, new =39 Сортировка в окне: 28, 29, 35, 36, 39, 42, 43, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36,  old = 28, new =35 Сортировка в окне: 29, 35, 35, 36, 39, 42, 43, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36,  Сортировка в окне: 35, 36, 39, 42, 43, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39,  Сортировка в окне: 35, 39, 43, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39,  Сортировка в окне: 35, 

Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35, 
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39, 35,

Сравнение скользящей медианы и скользящего среднего на интенсивной импульсной помехе проведено с помощью следующей программы:

function print_a($a, $name){
    print("$name: ");
    foreach($a as $item){
        printf("%3d, ",$item);
    }
}   

function slide_median($h, $a){
    $size = count($a);
    $result = [];
    $slide = [];
    array_push($slide, reset($a));
    array_push($result,$slide[0]);

    for($i=1; $i<=$h; $i++){
        array_push($slide, next($a), next($a));
        sort($slide);
        array_push($result, $slide[$i]);    
    }

    for($i=0; $i < $size-2*$h-1; $i++){
        $old = $a[$i];
        $new = $a[$i+2*$h+1];
        if($old < $new){
            for($key = 0; $key <= 2*$h; $key++){
                if($new < $slide[$key]){
                    break;
                }
                if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key] = $slide[$key+1]; 
            }
            $slide[$key-1] = $new;

        }
        if($old > $new){
            for($key = 2*$h; $key >= 0; $key--){
                if($new > $slide[$key]){
                    break;
                }
                if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key] = $slide[$key-1]; 
            }                   
            $slide[$key+1] = $new;
        }
        array_push($result, $slide[$h]);            
    }

    for($i = $h-1; $i > 0; $i--){
        $slide = array_slice($a, $size-2*$i-1, 2*$i+1);
        sort($slide);
        array_push($result, $slide[$i]);
    }
    $slide = [$a[$size-1]];
    array_push($result, $slide[0]);
    print_a($a, "<br><br>Исходный массив ");
    print_a($result, "<br>Массив медиан &emsp;");

    return $result;
};

function slide_average($h, $a){
    $size = count($a);
    $b = array_merge([0], $a);
    $sum = reset($a);
    $result = [$sum];

    for($i=1; $i<=$h; $i++){
        $sum += next($a)+next($a);
        $average = (int)($sum/(2*$i+1)+.5);
        array_push($result, $average);  
    }

    reset($b);
    for($i=0; $i < $size-2*$h-1; $i++){
        $sum += next($a) - next($b);
        $average = (int)($sum/(2*$h+1)+.5);
        array_push($result, $average);
    }

    for($i = $h-1; $i >=0; $i--){
        $sum -= (next($b) + next($b));
        $average = (int)($sum/(2*$i+1)+.5);
        array_push($result, $average);
    }
    print_a($a, "<br><br>Исходный массив ");
    print_a($result, "<br>Массив средних &ensp;");
    return $result;
};

$a = range(200, 240);
foreach($a as &$item){
    $item += 50*mt_rand(-1,1)*(int)(mt_rand(0,149)/100);
}
slide_median(3, $a);
slide_average(3, $a);

Результаты:

Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212, 213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240, 
Массив медиан  : 200, 201, 202, 202, 203, 204, 206, 207, 208, 209, 210, 211, 212, 213, 216, 217, 218, 219, 219, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 229, 230, 231, 232, 234, 235, 236, 238, 239, 239, 240, 

Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212, 213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240, 
Массив средних  : 200, 201, 202, 196, 197, 198, 199, 200, 201, 209, 210, 218, 226, 227, 228, 229, 230, 231, 225, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 223, 224, 225, 226, 234, 235, 236, 244, 248, 239, 240,

Видно, что скользящая медиана лучше сглаживает интенсивные случайные выбросы данных.

Для данных из реального массива (x,y округлялись до целых):



Обработка массива x80c48

Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894, 9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848, 6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825, 
Массив медиан  : 10790, 10728, 10565, 10228, 10148, 9911, 9894, 9894, 9894, 9894, 9907, 9910, 9917, 9917, 9917, 9917, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6868, 6868, 6868, 6868, 6894, 6902, 6903, 6904, 6994, 6994, 6994, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3086, 3086, 3086, 3053, 2977, 2967, 2954, 2834, 2730, 2730, 2611, 2594, 2574, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 825, 825, 

Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894, 9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848, 6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825, 
Массив средних  : 10790, 10694, 10492, 10319, 10189, 10069, 9973, 9927, 9893, 9894, 9904, 9912, 9917, 9918, 9886, 9839, 9772, 9644, 9498, 9323, 9117, 8927, 8749, 8561, 8418, 8274, 8150, 8046, 7923, 7771, 7645, 7520, 7394, 7262, 7136, 7040, 6981, 6927, 6888, 6872, 6871, 6879, 6920, 6950, 6976, 6990, 6987, 6980, 6963, 6907, 6813, 6697, 6575, 6450, 6328, 6167, 6013, 5897, 5767, 5616, 5473, 5286, 5140, 4986, 4800, 4645, 4514, 4389, 4285, 4180, 4066, 3985, 3903, 3819, 3717, 3625, 3508, 3405, 3298, 3198, 3151, 3127, 3113, 3094, 3063, 3008, 2952, 2861, 2786, 2723, 2660, 2597, 2564, 2534, 2496, 2437, 2341, 2254, 2159, 2046, 1885, 1722, 1529, 1346, 1192, 1008, 868, 825, 

Обработка массива y80c48

Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186, 5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279, 
Массив медиан  : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5083, 5081, 5081, 5081, 5083, 5063, 5062, 5042, 5009, 5009, 5007, 4993, 4993, 4993, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3489, 3489, 3489, 3489, 3498, 3542, 3567, 3581, 3586, 3598, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3788, 3788, 3788, 3743, 3710, 3550, 3511, 3511, 3455, 3435, 3406, 3379, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279, 

Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186, 5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279, 
Массив средних  : 7289, 7269, 7230, 7197, 7141, 7071, 6991, 6887, 6775, 6653, 6475, 6305, 6114, 5924, 5729, 5544, 5375, 5260, 5168, 5110, 5083, 5098, 5111, 5087, 5067, 5056, 5051, 5031, 5005, 4980, 4990, 4999, 4998, 4992, 4984, 4977, 4926, 4854, 4735, 4601, 4466, 4330, 4187, 4067, 3956, 3858, 3778, 3699, 3625, 3559, 3522, 3502, 3519, 3536, 3552, 3574, 3596, 3612, 3630, 3651, 3671, 3699, 3719, 3740, 3765, 3785, 3788, 3784, 3751, 3711, 3655, 3591, 3533, 3502, 3465, 3439, 3395, 3363, 3326, 3280, 3140, 3006, 2878, 2756, 2628, 2488, 2347, 2280, 2186, 2090, 1972, 1832, 1700, 1567, 1420, 1276, 1135, 1028, 949, 878, 795, 723, 661, 600, 529, 447, 362, 279,

По сравнению с алгоритмом скользящего среднего, скользящая медиана намного аккуратнее обращается с данными.

Есть перевод статьи на английский язык.

2
  • Не стоит считать координаты независимыми, между ними есть связь - это законы физики и их стоит учитывать. А вот нормальное и тангенциальное ускорения независимы и их можно попробовать сгладить.
    – sercxjo
    3 янв 2016 в 12:58
  • @sercxjo Я говорил только про независимую обработку двух зависимостей. А вот об ускорении при таких шумах придётся забыть. 3 янв 2016 в 17:05
5

Для обработки зашумленных данных стоит подумать о фильтре Калмана. Так как у вас тут автобус - сразу вопрос - этот автобус движется по заранее известному маршруту?

4
  • Нет, маршрут неизвестен, но можно его примерно набросать
    – Simankov
    3 янв 2016 в 11:03
  • Калмановская фильтрация - это рекуррентная реализация метода наименьших квадратов. Скажите, что и как Вы собираетесь оптимизировать. 3 янв 2016 в 12:33
  • @Yuri Negometyanov - хрестоматийный пример использования данного фильтра - как раз получение данных о скорости и положении объекта на основании поступающих зашумленных данных о положении.
    – gbg
    3 янв 2016 в 12:40
  • @gbg В хрестоматиях пишут про нормально распределённую помеху и модель со стабильными параметрами. В данном случае имеются импульсная помеха и высокая динамика движения, что усугубит исходную нестабильность фильтра (визуально - результаты обработки будут уныло тянуться за скачками исходных данных). Поэтому следует подумать о непараметрических методах обработки. 3 янв 2016 в 12:52
3

Если нужно сгладить график - есть алгоритмы фильтрации и аппроксимации. Во первых это метод скользящего среднего, которым можно немного подкорректировать входные данные для их большей гладкости. Далее, можно разбить график на небольшие куски и аппроксимировать их, скажем, параболами с помощью метода наименьших квадратов (о его идее я рассказывал здесь). Ещё можно использовать Фурье преобразование входных данных, убрать оттуда высокие частоты (что и будет шумом), после чего использовать обратное преобразование.

1

На графике видны как явные, так и неявные ошибки. Имеются повороты, плюс на каждом повороте есть сомнительные точки, по которым сразу и не скажешь, ошибка это, или автобус такой загогулиной ехал. То есть простые варианты типа отбрасывания точек для "невероятных" перемещений на участках поворотов вряд ли помогут.

Могу предложить использовать сглаживание методом локальной регрессии, затем построить доверительный интервал (вернее, доверительную область), но не для регрессии, а для значений (см. здесь), и отбрасывать точки за его пределами. 95% интервал может оказаться очень широким, возможно, потребуется взять 90%, 80% и т.д.

Что касается 100 тыс. наблюдений, то никакой бигдаты тут нет, на вполне заурядном компе можно пробовать самые разные методы.

1

Предлагаю два критерия отбрасывания плохих точек.

  1. Зигзаги - два поворота в разные стороны больше 90 градусов подряд. Это на самом деле возможно при откате и пробуксовывании, но если это происходит на одной линии, то не повредит внешний вид графика, а если со смещением, то скорее всего это результат ошибки. Однако при редких точках возможно, что автобус действительно так ехал, здесь критерий мне не ясен. Ещё часто наблюдается ошибочный дрейф во время стоянки. При обнаружении зигзага на маленькой скорости вместо удаления можно скопировать соседнюю точку. Возможно так же считать критерием стоянки постоянную очень маленькую скорость длительное время, но это может быть и движение в пробке.
  2. Слишком большое нормальное ускорение с чередованием знака (автобус не дрова везёт) - тут предлагаю порог 0,4 м/c^2 относительно предыдущего значения.

Программа

#include <stdio.h>
#include <string.h>
#include <math.h>

#define ZZMAXLEN 40
#define MAXDA 0.4

int main(int argn, char **argv) {
    double x[4], y[4]; // кольцевые буферы данных
    int t[4]={0,0,0,0}, n=0, h=0;
    char id[9];
    if(argn!=2) {
        fprintf(stderr, "Usage:\n\t%s bus-ID\n", argv[0]);
        return 1;
    }
    while(scanf("%d %lf %lf %8s", t+h, x+h, y+h, id)==4) {
        if(strcmp(id, argv[1])) continue;
        h= h+1 & 3;
        if(++n < 4) continue;
        int dt1= t[h+1&3]-t[h];
        int dt2= t[h+2&3]-t[h+1&3];
        int dt3= t[h+3&3]-t[h+2&3];
        double dx1= x[h+1&3]-x[h];
        double dy1= y[h+1&3]-y[h];
        double dx2= x[h+2&3]-x[h+1&3];
        double dy2= y[h+2&3]-y[h+1&3];
        double dx3= x[h+3&3]-x[h+2&3];
        double dy3= y[h+3&3]-y[h+2&3];
        int filter=0;
        if(dx1*dx2+dy1*dy2 < 0 && dx2*dx3+dy2*dy3 < 0 && dx1*dx3+dy1*dy3 > 0 && dx2*dx2+dy2*dy2 < ZZMAXLEN*ZZMAXLEN) {
            // разворот на угол более 90 градусов 2 раза подряд
            if((dx2*dx2+dy2*dy2)>0 && (dx2*dx2+dy2*dy2)/(dt2*dt2)<0.05) {
                fprintf(stderr, "D %d\n", n-1); // дрейф
                filter=2;
            } else {
                fprintf(stderr, "Z %d\n", n-2);
                filter=1;
            }
        }
        // скорости
        dx1/=dt1;
        dx2/=dt2;
        dx3/=dt3;
        dy1/=dt1;
        dy2/=dt2;
        dy3/=dt3;
        double vx12= (dx1+dx2)/(dt1+dt2);
        double vy12= (dy1+dy2)/(dt1+dt2);
        double vx23= (dx2+dx3)/(dt2+dt3);
        double vy23= (dy2+dy3)/(dt2+dt3);
        double v12= sqrt(vx12*vx12+vy12*vy12);
        double v23= sqrt(vx23*vx23+vy23*vy23);
        // ускорения
        double ax1= (dx2-dx1)*2/(dt1+dt2);
        double ay1= (dy2-dy1)*2/(dt1+dt2);
        double ax2= (dx3-dx2)*2/(dt2+dt3);
        double ay2= (dy3-dy2)*2/(dt2+dt3);
        // нормальные ускорения
        double an1= v12? (vx12*ay1-vy12*ax1)/v12 : 0;
        double an2= v23? (vx23*ay2-vy23*ax2)/v23 : 0;
        if(fabs(an1-an2) > MAXDA && an1*an2<0) {
            fprintf(stderr, "N %d %f %f\n", n-2, an1, an2); // два резких поворота
            filter=1;
        }
        if(filter) {
            // определяем какую точку удалить
            if(fabs(an1) > fabs(an2))
                if(filter==2) {
                    x[h+1&3]=x[h+2&3];
                    y[h+1&3]=y[h+2&3];
                } else {
                    x[h+1&3]=x[h+2&3];
                    y[h+1&3]=y[h+2&3];
                    t[h+1&3]=t[h+2&3];
                }
            else
                if(filter==2) {
                    x[h+2&3]=x[h+1&3];
                    y[h+2&3]=y[h+1&3];
                } else {
                    x[h+2&3]=x[h+1&3];
                    y[h+2&3]=y[h+1&3];
                    t[h+2&3]=t[h+1&3];
                }
        }
        // тут можно пропустить точки с поворяющимся временем, но я оставил для построения графиков
        printf("%d\t%lf\t%lf\t%s\n", t[h], x[h], y[h], id);
    }
    t[h]=0;
    do { h=h-1&3; } while (t[h-1&3]<t[h] && t[h-1&3]>0);
    do {
        printf("%d\t%lf\t%lf\t%s\n", t[h], x[h], y[h], argv[1]);
        h= h+1&3;
    } while (t[h-1&3]<t[h] && t[h]>0);
    return 0;
}

Результаты работы получаем на стандартном выводе, а в стандартном выводе ошибок список удалённых точек и причина (N - нормальное ускорение, Z - зигзаг, D - зигзаг в дрейфе):

$ ./a.out 80c48 < data.txt > 80c48.txt
N 154 -0.163844 0.490944
D 249
D 252
Z 303
Z 444
Z 567
N 631 0.283293 -0.136238
Z 636
N 727 0.321036 -0.103197
N 984 -0.366378 0.309231
Z 991
N 1082 0.414078 -0.203378
N 1199 -0.020139 0.572870
D 1213
Z 1414
D 1507
D 1515
D 1517
D 1538

И иллюстрация удаления точки 154:

часть результата в графическом виде

Видимо исходные данные уже обработаны каким-то фильтром, так как отсчёты времени неравномерны.

Данный метод вырезает одиночные ошибки, но данные GPS часто могут накапливать ошибки (и фильтр Калмана тоже) , и для борьбы с этим можно предложить притягивать слишком отклонённые точки к сетке дорог, которую можно получить усредняя много траекторий.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.