ГЛОблинНАСС

[VPom]

Lev G. писал(а) Mon, 12 November 2012 23:10

Про программу я уверен, что такую написать возможно, но для конкретных задач. Например, если транспорт велосипед то очевидно, что скорости >100км/ч из области фантастики. В программе можно сделать фильтр по скоростям зачищающий строки в файле от момента включения прибора до точек с такими скоростями если таковые будут.

Увы, но это рассуждения дилетанта. Без обид, просто констатация факта.

Давайте уточним. Для программы нужен четкий критерий для отбора. Иными словами - конкретное число. Больше - плохая точка ("выброс"), меньше - хорошая.

Как мы определим это число? Вот вы говорите, что больше 100км/ч на велосипеде нереально. А 99 реально? Нет. Тогда сколько? 70 нереально? А 69.9? Где точная граница между реальностью и нереальностью?

Но на самом деле все еще сложнее. Вот скорость 40км/ч на велосипеде реальна? Да. А когда в какой-то момент времени скорость равна нулю, через секунду она равна 40км/ч а еще через секунду опять ноль - это реально? Нет. Т.е. одной скорости, получается, недостаточно. Нужно еще и ускорение учитывать. А это еще один точный критерий - какое ускорение считать реальным, а какое нет?

Я не говорю уже о том, что расчет скорости, а тем более, ускорения по координатам-времени дает гигантскую погрешность на малых временных интервалах. Настолько большую, что это теряет всякий смысл. Можно рассчитать с некоторой точностью усредненные значения, скажем, за 10-20-30 секунд, но это мало что даст с точки зрения локализации выбросов.

Куда проще работать с треками, где содержатся дополнительные данные в виде доплеровской скорости и курса. Там можно сравнивать рассчетную скорость и доплеровскую, можно применять фильтр калмана с аппрокимацией следующей точки по координатам-скорости-курсу предыдущей (да еще и HDOP учитывать в качестве "весов" для точек). Но туристические навигаторы такой трек не пишут (в отличие от логгеров, именно поэтому я для записи трека использую логгер, а не навигатор). У магелланов, правда, можно включить NMEA лог, но это делается ручной правкой конфигов (благо, к ним несложно добраться) и в к тому же там не будет разделения по трекам - придется потом все это разгребать руками где "вчера", где "сегодня" и к тому же руками их чистить.

Резюме.

1. Я искал, но не нашел ни одной программы, которая могла бы эффективно фильтровать треки, содержащие только координаты и время.

2. Я пытался сам написать такую программу. Проанализировал куеву хучу треков (ручками, в экселе) в поисках закономерностей и методов их выявления. Результат близкий к нулю. Максимум, что мне удалось, более-менее эффективно выявлять участки "дрифта" (когда стоишь на месте, а трек "гуляет вокруг тебя"). Алгоритм получился отнюдь не простой и ближе к "геометрическому", нежели к математическому. Но что-то ловит.

3. Есть и более сложные ситуации - массовые выбросы. Когда из трека вылетает не одна точка, а несколько. Скажем, движемся по дороге, вдруг трек скачком улетает на 100м в сторону, затем идет ровно, но со смесщением, через несколько секунд (5-10 точек) возвращается обратно. Восстанавливать такое еще сложнее чем выкинуть одну точку, заменив ее интерполяцией. А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

4. Есть пара идей как еще можно попробовать ловить одиночные выбросы, но пока нет времени реализовать и нет уверенности, что это вообще будет работать...

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

[VORON]

VPom писал(а) Fri, 16 November 2012 10:12

А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

Это не функция привязки к дороге шалит?

[VPom]

VORON писал(а) Fri, 16 November 2012 12:27

VPom писал(а) Fri, 16 November 2012 10:12

А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

Это не функция привязки к дороге шалит?

Какая, к чертям, "привязка к дороге" в логгере? В нем ни экрана, ни карты. Он просто протоколирует то, что получает со спутника.

[indi]

VORON писал(а) Fri, 16 November 2012 10:27

VPom писал(а) Fri, 16 November 2012 10:12

А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

Это не функция привязки к дороге шалит?

я встречал такие жалобы часто на старых навигаторах с виндоус мобайл.
ещё у меня был когда-то такой: https://buy.garmin.com/shop/shop.do?pID=220
тоже подобные штуки вытворял. но у него с приёмом сигнала совсем плохо было, стоило въехать в лес, а то и просто небо натянется облаками - ищи свищи эти спутники

[VPom]

indi писал(а) Fri, 16 November 2012 12:37

VORON писал(а) Fri, 16 November 2012 10:27

VPom писал(а) Fri, 16 November 2012 10:12

А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

Это не функция привязки к дороге шалит?

я встречал такие жалобы часто на старых навигаторах с виндоус мобайл.
ещё у меня был когда-то такой: https://buy.garmin.com/shop/shop.do?pID=220
тоже подобные штуки вытворял. но у него с приёмом сигнала совсем плохо было, стоило въехать в лес, а то и просто небо натянется облаками - ищи свищи эти спутники

В моем случае это наблюдалось на старом Garmin eTrex H (чип Bravo-2). Подобное было и на логгере Qstarz BT-Q1000P на чипе МТК3318. Ни тот н другой плохой чувствительностью не страдают. Это чисто системная погрешность - какая-то помеха или сбой.

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

[indi]

VPom писал(а) Fri, 16 November 2012 10:45

В моем случае это наблюдалось на старом Garmin eTrex H (чип Bravo-2).

а в Garmin Legend/Vista HCx такой же чип?

[VPom]

indi писал(а) Fri, 16 November 2012 13:00

VPom писал(а) Fri, 16 November 2012 10:45

В моем случае это наблюдалось на старом Garmin eTrex H (чип Bravo-2).

а в Garmin Legend/Vista HCx такой же чип?

Помнится на эту тему было развернутое обсуждение. Пришли к тому, что eTrex H делались только на B2, а вот Легенды и Висты по разному. Ранние серии выпускались на В2, потом его стали вытеснять приборы на МТК. Вроде бы там это как-то можно было определить (включить питание при каких-то нажатых кнопках и прибор входит в информационно-тестовый режим где написано все, включая тип чипа). Но подробностей не помню уже - давно было.

Существенно разницы в поведении я не заметил, кстати. Был eTrex H на Bravo2, потом параллельно с ему появился логгер на МТК, сейчас вместо етрекса магеллан на sirf-III - в целом там расхождения в реальной обстановке непринципиальные, в мелочах. У всех трех чипов (даже специально как-то писал трек одновремено тремя приборами на разных чипах, просто для сравнения. Где-то больше нравится как МТК работает, где-то как сирф...

[VORON]

VPom писал(а) Fri, 16 November 2012 10:45

Есть еще один способ улучшения качество трека

А практический смысл? На 500-метровке вылетевшую точку даже не увидеть будет. Единственное, что при экспорте в OSM надо наверно все же довести трек до ума.

Эх, помню я времена 10-летней давности, когда навигатор гарантированно терял спутники в кармане куртки или если лес начинал сгущаться... Трек в покатушке получался пунктирным, а о такой мелочи, как выбросы, никто даже не думал.

Особенно весело было тайники искать - на опушке леса определяется примерное направление на тайник, в лесу сигнал скорей всего теряется, дальше искать по фоткам и особым приметам. Собственно, стало неинтересно искать тайники с точными навигаторами.

[VPom]

VORON писал(а) Fri, 16 November 2012 13:13

VPom писал(а) Fri, 16 November 2012 10:45

Есть еще один способ улучшения качество трека

А практический смысл? На 500-метровке вылетевшую точку даже не увидеть будет. Единственное, что при экспорте в OSM надо наверно все же довести трек до ума.

Эх, помню я времена 10-летней давности, когда навигатор гарантированно терял спутники в кармане куртки или если лес начинал сгущаться... Трек в покатушке получался пунктирным, а о такой мелочи, как выбросы, никто даже не думал.

Особенно весело было тайники искать - на опушке леса определяется примерное направление на тайник, в лесу сигнал скорей всего теряется, дальше искать по фоткам и особым приметам. Собственно, стало неинтересно искать тайники с точными навигаторами.

Практический смысл - отдельная тема. кому просто положить трек на карту и примерно посмотреть - тому не надо.

Речь была о том, что фильтрация выбросов только кажется простой, на самом деле это задача очень нетривиальная - глазом выборос виден сразу, а вот математически выявить его ой как непросто.

[indi]

VPom писал(а) Fri, 16 November 2012 10:12

4. Есть пара идей как еще можно попробовать ловить одиночные выбросы, но пока нет времени реализовать и нет уверенности, что это вообще будет работать...

интересно!
а в чём суть этих идей?

[VPom]

indi писал(а) Fri, 16 November 2012 13:38

VPom писал(а) Fri, 16 November 2012 10:12

4. Есть пара идей как еще можно попробовать ловить одиночные выбросы, но пока нет времени реализовать и нет уверенности, что это вообще будет работать...

интересно!
а в чём суть этих идей?

На пальцах сложно объяснять - идеи были в зачаточном состоянии

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

Второе - что-то типа фильтра калмана с применением скоростей и курсов. Но скорость считать не по исходному треку, а усредненную по сглаженому. К примеру, скажем, сглаживаем трек В-сплайном, просчитываем по нему "опорные" точки с интервалом, к примеру, 5-10 секунд, по ним считаем скорость, строим еще один В-сплайн и по нему уже просчитываем скорости в реальных точках трека. Затем уже для каждой последующей точки трека сначала строим аппрокисмацию по предыдущей точке и скорости, а потом смотрим насколько реальная точка отклоняется от аппроксимуемой и делаем на основе этого какие-то выводы.

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

[Bulawka]

VORON писал(а) Fri, 16 November 2012 11:13

VPom писал(а) Fri, 16 November 2012 10:45

Есть еще один способ улучшения качество трека

А практический смысл? На 500-метровке вылетевшую точку даже не увидеть будет.

Ерунда. С вистой (старой, чёрно-белой) вылетевшие точки были видны на километровке, и их было дофига.
И на 10-километровке они ТОЖЕ были бы видны.
Правда, дело было в горах/в лесу, с весьма фиговым прибором.
Могу показать тот вылетательный трек, если надо.

[Lev G.]

VPom писал(а) Fri, 16 November 2012 10:12

Lev G. писал(а) Mon, 12 November 2012 23:10

Про программу я уверен, что такую написать возможно, но для конкретных задач. Например, если транспорт велосипед то очевидно, что скорости >100км/ч из области фантастики. В программе можно сделать фильтр по скоростям зачищающий строки в файле от момента включения прибора до точек с такими скоростями если таковые будут.

Увы, но это рассуждения дилетанта. Без обид, просто констатация факта.

Давайте уточним. Для программы нужен четкий критерий для отбора. Иными словами - конкретное число. Больше - плохая точка ("выброс"), меньше - хорошая.

Как мы определим это число? Вот вы говорите, что больше 100км/ч на велосипеде нереально. А 99 реально? Нет. Тогда сколько? 70 нереально? А 69.9? Где точная граница между реальностью и нереальностью?

Так можно ведь написать такую программу, чтоб пользователь сам задавал в программе это число. Скажем если он знает, что он более 40км/ч не ехал, выставит допустим 45 в фильтре, а если это скоростной даунхилл, то большее число. После этого программа начнет работу.
VPom писал(а) Fri, 16 November 2012 10:12

Но на самом деле все еще сложнее. Вот скорость 40км/ч на велосипеде реальна? Да. А когда в какой-то момент времени скорость равна нулю, через секунду она равна 40км/ч а еще через секунду опять ноль - это реально? Нет. Т.е. одной скорости, получается, недостаточно. Нужно еще и ускорение учитывать. А это еще один точный критерий - какое ускорение считать реальным, а какое нет?

По поводу ускорения все гораздо проще. Ведь у 99% пользователей нет треклогеров, которые бы писали трек с интервалом <1 сек. Для треклога обычного навигатора ускорение просто невозможно вычислить поскольку точки ставятся в лучшем случае через интервал 6-10 сек(метод записи авто - совсем часто). А за такое время разогнать велосипед до 40км/ч думаю будет уже по силам, хотя не проверял Тем не менее мгновенную скорость навигатор определяет с погрешностью во всяком случае не более 1км/ч, сравнивал с велокомпьютером расхождений когда либо замечено не было!
VPom писал(а) Fri, 16 November 2012 10:12

3. Есть и более сложные ситуации - массовые выбросы. Когда из трека вылетает не одна точка, а несколько. Скажем, движемся по дороге, вдруг трек скачком улетает на 100м в сторону, затем идет ровно, но со смесщением, через несколько секунд (5-10 точек) возвращается обратно. Восстанавливать такое еще сложнее чем выкинуть одну точку, заменив ее интерполяцией. А такой уход бывает и плавным - выглядит весьма натурально, как с дороги съехал в лес, проехал по лесу, потом выехал обратно на дорогу. Если не знать что с дороги не съезжал - никаких аномалий не заметишь (был где-то пример и такого трека).

4. Есть пара идей как еще можно попробовать ловить одиночные выбросы, но пока нет времени реализовать и нет уверенности, что это вообще будет работать...

По поводу массовых выбросов первое что приходит в голову это кривость вашей карты, т. е. трек рисуется правильно, а дорога на карте изображена с ошибкой. Или у вас совсем древний прибор. В реальности на современных навигаторах на mtk или sirf такого никогда не наблюдал. Единственное, что бывает, так это когда в глубокий каньон или ущелье залезаешь погрешность падает с 3-4м до 10-15м и трек поэтому гулять начинает, но тут уже ничего не поделаешь. А так даже в самом густом лесу погрешность <10м и никаких выбросов ни массовых ни единичных.

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

Причина такого поведения навигатора в принципе мне ясна, прибор запоминает твое последнее местоположение до потери сигнала и когда ищет спутники(в первую минуту их поиска погрешность еще высока) заложенный в него сложный математический алгоритм учитывает в тот момент в большей степени твое последнее местоположение. И выдает эти координаты в треклог. Затем когда точность сигнала резко увеличивается до привычных +-3м твое прежнее местоположение уже не учитываются и в треклог попадают верные координаты (это только 3 точка в моем примере) Между точками получается большой скачек расстояния и соответственно скорости. На треклогере за это время выставиться не 3-4, а 30-40 точек и этот скачек будет плавным настолько, что его можно и не заметить. Т. е. там не будет таких "нереальных" скоростей будет только неверно начерченный трек.

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

[VPom]

Lev G. писал(а) Sat, 17 November 2012 01:57

Так можно ведь написать такую программу, чтоб пользователь сам задавал в программе это число. Скажем если он знает, что он более 40км/ч не ехал, выставит допустим 45 в фильтре, а если это скоростной даунхилл, то большее число. После этого программа начнет работу.

Хорошо. Значит 44.99 - не выброс, а 45.01 - выброс?
вы сами хоть одну такую программу написали? Думаю что нет. А я несколько лет этим вопросом в свободное время занимаюсь. Не так там все просто как кажется с первого взгляда.

Чтобы стало понятнее могу предложить "домашнее задание". возьмите трек, загрузите его, скажем, в эксель, и попробуйте рассчитать какой-то критерий для каждой точки трека, по которому можно было бы однозначно сказать выброс это или нет. Не видя трек на карте, просто по координатам-времени для каждой точки.

Если удастся, возьмите еще десяток-другой треков и проверьте найденный критерий на них.


Lev G. писал(а) Sat, 17 November 2012 01:57

По поводу ускорения все гораздо проще. Ведь у 99% пользователей нет треклогеров, которые бы писали трек с интервалом <1 сек. Для треклога обычного навигатора ускорение просто невозможно вычислить поскольку точки ставятся в лучшем случае через интервал 6-10 сек(метод записи авто - совсем часто). А за такое время разогнать велосипед до 40км/ч думаю будет уже по силам, хотя не проверял Тем не менее мгновенную скорость навигатор определяет с погрешностью во всяком случае не более 1км/ч, сравнивал с велокомпьютером расхождений когда либо замечено не было!

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

Что касается скорости. Ни на навигаторе, ни на велокомпе мгновенной скорости вы не видите. Тм отображается некая усредненная скорость. Скорее всего, по методу взвешенного скользящего среднего. Что-то типа:

V[i] = a * V + (1 - a) * V[i-1];

где:
V[i] и V[i-1] - отображаемая скорость в текущий и предыдущий моменты времени
V - реально измеренная мгновенная скорость в текущий момент времени
a - коэффициент усреднения (с достаточно большой степенью вероятности могу предположить что он выбирается где-то в интервале 0.6..0.

Кроме того, навигатор берет мгновенное значение скорости не вычисленное по координатам, а измеренное независимо, с использованием доплер-эффекта (по смещению частоты сигнала от каждого из спутников возможно определить скорость относительно спутника, затем, зная расстояние до него и направление на спутник можно вычислить результирующую скорость и направление движения в пространстве как векторную сумму скоростей относительно спутников). Эта скорость (и направление) всегда выдается навигацинным чипом в программу навигатора. Хотя и не записывается в трек (но в NMEA потоке оно присутсвует).

Lev G. писал(а) Sat, 17 November 2012 01:57

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

Garmin eTrex Hа чипе Bravo2. Не менее современный, чем МТК или Сирф-3.



Трек наложен на гуглеснимок в сети (программа работает через GMap API с онлайновыми картами). В одну сторону ухода нет, в другую - есть.

Ни на древность чипа, ни на кривость карты тут не списать. Изменено 19 ноября 2012 г. пользователем Змей Гуревич

[VORON]

Bulawka писал(а) Fri, 16 November 2012 13:16

Правда, дело было в горах/в лесу, с весьма фиговым прибором.
Могу показать тот вылетательный трек, если надо.

То ж именно что фиговый прибор, ему место в музее. У меня была самая первая Виста, для записи треков она не годилась. Современные точнее даже не на порядок - они видят 6 спутников там, где первое поколение видело 1-2.

[Lev G.]

VPom писал(а) Sat, 17 November 2012 11:59

Lev G. писал(а) Sat, 17 November 2012 01:57

Так можно ведь написать такую программу, чтоб пользователь сам задавал в программе это число. Скажем если он знает, что он более 40км/ч не ехал, выставит допустим 45 в фильтре, а если это скоростной даунхилл, то большее число. После этого программа начнет работу.

Хорошо. Значит 44.99 - не выброс, а 45.01 - выброс?
вы сами хоть одну такую программу написали? Думаю что нет. А я несколько лет этим вопросом в свободное время занимаюсь. Не так там все просто как кажется с первого взгляда.

Все равно я не понимаю зачем вам понадобился четкий критерий, ради которого вы готовы потратить так много своего свободного времени? И так же очевидно, что его нет и быть не может. Само определение местоположения носит вероятностный характер. Ухудшился сигнал (почему другой вопрос) и имеем вместо +-3м уже+-15м соответственно велика вероятность что трек может улететь на 15м в сторону и никакая высшая математика вам не поможет. Тем более в ситуации когда дорога имеет изгиб, а сигнал был потерян(или сильно ухудшился) как раз перед входом в этот изгиб, как в вашем примере.

VPom писал(а) Sat, 17 November 2012 11:59

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

Вы поймите, что то что предлагаю я, это не есть четкий критерий 100% отсекающий все выбросы (что по моему мнению нерешаемая задача) это лишь метод позволяющий выявить и избавиться от наиболее грубых выбросов, которые существенно могут исказить данные статистики в сторону увеличения. Например, вместо реальных 600км за велопоход(по велокомпу) по треку будет скажем 630-650км, а по набору высоты вместо 9000м будет 10000м Различия могут быть и более существенными.
Я уже описал для каких случаев предлагается данный метод. Работать этот метод будет только для треков написанных современными приборами, т. е. такими, где при горячем старте потерянный сигнал ищется достаточно быстро за секунды. Тогда "улетевший" трек почти моментально возвращается на дорогу по которой вы едете и в треклог неизбежно попадают "нереальные" скорости. Выявляя их мы тем самым удаляем такие точки. Собственно я не предлагаю ничего нового, только лишь автоматизировать(путем написания программы) то, что мне и так приходилось делать вручную с некоторыми из своих треков.

VPom писал(а) Sat, 17 November 2012 11:59

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

Тут я с вами не согласен. Если те сложные математические алгоритмы, которые вы тут описали, позволяют добиться точности определения мгновенной скорости в +-1км/ч (а это действительно так), то я имею полное право сказать, что глядя в навигатор я знаю(вижу) свою мгновенную скорость (какое для меня имеет значение как именно она там подсчитана, я же не собираюсь процессор в навигаторе разбирать )

VPom писал(а) Sat, 17 November 2012 11:59

Garmin eTrex Hа чипе Bravo2. Не менее современный, чем МТК или Сирф-3.

Трек наложен на гуглеснимок в сети (программа работает через GMap API с онлайновыми картами). В одну сторону ухода нет, в другую - есть.

Ни на древность чипа, ни на кривость карты тут не списать.

И тут я с вами не соглашусь. Нельзя принимать спутниковые снимки Google за эталон. Я тоже раньше так думал, пока не получил пару привязок программой SASPlanet со смещением всей картинки на 50м. Когда я изготовил собственную привязку этого снимка в OZI я понял это. Несовершенны не сами спутниковые снимки, а методы их автоматической привязки в онлайновых или офф-лайновых программах.
Вот и на вашем снимке видно, что весь трек смещен на юг относительно дороги. Т. е. вылет от дороги будет не 50м. а только где-то 30м.
Что касается древности чипа, тут вывод смогу сделать если пришлете мне этот трек в личку с указанием времени, когда проезжали этот участок. Возможно был некий глюк, ваш прибор потерял сигнал, а пока пытался его найти аппроксимировал трек по прямой, а затем по мере повышения точности(горячий старт) трек вернулся к дороге.
Изменено 18 ноября 2012 г. пользователем Lev G.

[VPom]

Lev G. писал(а) Sun, 18 November 2012 22:39

Все равно я не понимаю зачем вам понадобился четкий критерий, ради которого вы готовы потратить так много своего свободного времени? И так же очевидно, что его нет и быть не может.

Напомню - все началось с того, что некоторые (не будем показывать пальцем) утверждали что любой фрилансер за 500р напишет программу, которая легко и просто отсеет все "плохие точки".

Так вот. Для программы нужен четкий и однозначный критерий того, какая это точка. Хорошая или плохая. Программа не умеет мыслить интуитивно, она умеет складывать, вычитать, сравнивать больше-меньше... Т.е. с каждой точкой она может произвести некий набор арифметических действий и потом сравнить результат с каким-то заданным числом. А на основании сравнения сделать вывод удалять току или нет.

Я утверждаю, что скорость, вычисленную по координатам-времени, в качестве такого критерия использовать невозможно. Просто потому что невозможно однозначно определить пороговое ее значение ниже которого все точки будут признаны хорошими, а выше - плохими.

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

Вот еще один пример.



Красный трек - то, что получено с прибора. Синий - обработанный по некоторому специальному алгоритму.

Здесь мы видим классический пример "дрифта". Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора. С такими артефактами научился бороться более-менее эффективно (не на 100%, но в большинстве случаев выявлять их умею). Не так это и просто на самом деле. Визуально-то они сразу в газа бросаются, а вот математически выделить их оказалось достаточно нетривиально.

[indi]

VPom писал(а) Mon, 19 November 2012 09:25

Красный трек - то, что получено с прибора. Синий - обработанный по некоторому специальному алгоритму.

Здесь мы видим классический пример "дрифта". Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора. С такими артефактами научился бороться более-менее эффективно (не на 100%, но в большинстве случаев выявлять их умею). Не так это и просто на самом деле. Визуально-то они сразу в газа бросаются, а вот математически выделить их оказалось достаточно нетривиально.

круто! очень хотелось бы взглянуть на алгоритм.

[indi]

VPom писал(а) Mon, 19 November 2012 09:25

Напомню - все началось с того, что некоторые (не будем показывать пальцем) утверждали что любой фрилансер за 500р напишет программу, которая легко и просто отсеет все "плохие точки".

кто-то где-то говорил, что все точки? Изменено 19 ноября 2012 г. пользователем indi

[VPom]

indi писал(а) Mon, 19 November 2012 11:35

VPom писал(а) Mon, 19 November 2012 09:25

Красный трек - то, что получено с прибора. Синий - обработанный по некоторому специальному алгоритму.

Здесь мы видим классический пример "дрифта". Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора. С такими артефактами научился бороться более-менее эффективно (не на 100%, но в большинстве случаев выявлять их умею). Не так это и просто на самом деле. Визуально-то они сразу в газа бросаются, а вот математически выделить их оказалось достаточно нетривиально.

круто! очень хотелось бы взглянуть на алгоритм.

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

Если в двух словах, то так.

Берем некоторое "окно" из 10-15-20 точек и двигаем его по треку (ну скажем, точки с 1-й по 10-ю, потом со 2-й по 11-ю и т.д). Каждый раз строим прямоугольник, в который попадают все точки окна и анализируем соотношение его сторон - чем оно ближе к 1 (квадрат), тем больше вероятность того, что мы нашли участок "дрифта". Когда такой участок выделен в первом приближении, играемся с размерами окна и точным его положением так, чтобы получить максимально близкое к 1 соотношение сторон. Так удается максимально точно локализовать начало и конец дрифт-участка.

Когда участок локализован уже можно делать с ним что угодно. я обычно заменяю все дрифит-точки на две с одинаковыми координатами (скажем, усредненными по всем дрифт-точкам) и временами начала и конца участка. Т.е. имитирую точное стояние на месте в течении некоторого времени.

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

[VPom]

indi писал(а) Mon, 19 November 2012 11:45

VPom писал(а) Mon, 19 November 2012 09:25

Напомню - все началось с того, что некоторые (не будем показывать пальцем) утверждали что любой фрилансер за 500р напишет программу, которая легко и просто отсеет все "плохие точки".

кто-то где-то говорил, что все точки?

А смысл отсеивать одну две "самых плохих" и оставлять "просто плохие"?

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

Тут много чего можно придумать. Скажем, резкие изменения скорости за короткий промежуток времени. Резкие изменения курса туда-сюда (опять же за короткий промежуток времени)... Большие отклонения отдельных точек от "генеральной линии"... Но все это надо анализировать в комплексе.

[indi]

VPom писал(а) Mon, 19 November 2012 09:47

indi писал(а) Mon, 19 November 2012 11:35

VPom писал(а) Mon, 19 November 2012 09:25

Красный трек - то, что получено с прибора. Синий - обработанный по некоторому специальному алгоритму.

Здесь мы видим классический пример "дрифта". Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора. С такими артефактами научился бороться более-менее эффективно (не на 100%, но в большинстве случаев выявлять их умею). Не так это и просто на самом деле. Визуально-то они сразу в газа бросаются, а вот математически выделить их оказалось достаточно нетривиально.

круто! очень хотелось бы взглянуть на алгоритм.

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

Если в двух словах, то так.

Берем некоторое "окно" из 10-15-20 точек и двигаем его по треку (ну скажем, точки с 1-й по 10-ю, потом со 2-й по 11-ю и т.д). Каждый раз строим прямоугольник, в который попадают все точки окна и анализируем соотношение его сторон - чем оно ближе к 1 (квадрат), тем больше вероятность того, что мы нашли участок "дрифта". Когда такой участок выделен в первом приближении, играемся с размерами окна и точным его положением так, чтобы получить максимально близкое к 1 соотношение сторон. Так удается максимально точно локализовать начало и конец дрифт-участка.

Когда участок локализован уже можно делать с ним что угодно. я обычно заменяю все дрифит-точки на две с одинаковыми координатами (скажем, усредненными по всем дрифт-точкам) и временами начала и конца участка. Т.е. имитирую точное стояние на месте в течении некоторого времени.

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

интересно.
а почему именно прямоугольник? может, проще векторы 10-20 точек складывать, и , чем ближе их сумма к нулю, тем больше шансов, что это дрифт.

[VPom]

indi писал(а) Mon, 19 November 2012 12:00

а почему именно прямоугольник? может, проще векторы 10-20 точек складывать, и , чем ближе их сумма к нулю, тем больше шансов, что это дрифт.

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

А вообще там вся сложность в том, с какого соотношения сторон включать "подозрение на дрифт" и в точном уточнении границ дрифт-участка. Не могу сказать, что у меня получилось на 100% надежно - иногда не получалось выловить. Хотя в большинстве случаев работало.

Но это задача не на 500 рублей. Хотя бы потому что для решения ее приходится обкатывать алгоритм на большом количестве треков чтобы убедиться в его универсальности.

[VORON]

VPom писал(а) Mon, 19 November 2012 09:25

Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора.

А как отличить такой случай от владельца навигатора, который решил погулять туда-сюда, пока кто-то клеит камеру?

[VPom]

VORON писал(а) Mon, 19 November 2012 15:43

VPom писал(а) Mon, 19 November 2012 09:25

Был прокол камеры. Пока клеился, прибор был неподвижен, а записанный им трек "гулял" вокруг прибора.

А как отличить такой случай от владельца навигатора, который решил погулять туда-сюда, пока кто-то клеит камеру?

Вопрос хороший. По существу. Я такой задачи перед собой не ставил т.к. не сталкивался с такой ситуаций.

Подозреваю, что движение владельца навигатора будет все-таки более упорядоченным (ну разве что он в "классики" решит поиграть нежели дрифт. И его можно каким-то образом отфильтровать уже после того, как выделена область, подозреваемая на дрифт.