Рисунок 5. Манчестерское кодирование
На рисунке 5 показан пример передачи сигнала с помощью Манчестерского кодирования. Стрелками обозначен перепад напряжения.
Для передачи сообщения была создана небольшая веб-страница, которая передает идентификатор с помощью изменения фона страницы с черного на белый в соответствии с Манчестерским кодированием и частотой 5Гц. Частота в 5Гц была выбрана исходя из возможностей камеры мобильного телефона, более подробно об этом будет написано ниже.
3.4.3 Получение сигнала
Сигнал детектируется камерой телефона с помощью стандартных методов Android API. Детектирование и обработка сигнала включает несколько шагов:
1. Включение камеры в режиме видеозаписи.
Режим видеозаписи был выбран ввиду того, что таким образом можно добиться наибольшей частоты кадров в секунду. В режиме съемки фотографии частота получения кадров снижается из-за того, что перед запросом на получение изображения проводится настройка камеры, а после обработка изображения. К тому же, время настройки и обработки не константное, поэтому становится невозможно синхронизоваться с передатчиком.
Видео записывается в минимальном разрешении - 480x360px, так как в используемом алгоритме не требуется хорошее разрешение для детектирования сигнала и таким образом появляется возможность использовать данное приложение на устройствах с плохой камерой.
2. Сохранение видео каждые 2 секунды
Стандартные методы Android API не поддерживают передачу и обработку видео в потоковом режиме, поэтому было принято решение каждые несколько секунд сохранять файл и в отдельном потоке обрабатывать его, пока идёт запись следующего файла.
3. Получение кадров из видео
Так как передача сигнала происходит с частотой в 5Гц, кадры необходимо получать хотя бы с частотой в 10Гц. Но так как частота кадров в секунду в видеозаписи по-прежнему остается не константной, и смена цвета экрана происходит не мгновенно, то становится невозможно определить принадлежность кадра к конкретному такту, если он был получен на границе изменения цвета.
Рисунок 6. Получение фреймов частотой в 10Гц
На схеме выше (Рисунок 6) можно увидеть, что сообщение 111 может быть получено неверно при определенной позиции кадра.
Рисунок 7. Получение фреймов с частотой в 15Гц
Поэтому было принято решение производить считывание кадра частотой в 15Гц, чтобы на каждый такт было выявлено 3 кадра и даже если один из них окажется на границе смены цвета по двум другим можно будет однозначно определить какой бит был передан (Рисунок 7).
Таким образом, из видео запрашиваются кадры по времени, с разницей между двумя кадрами в 67мс (15Гц - смена кадра каждые 1/15 секунды или 67мс).
4. Определение основного цвета кадра
Для каждого кадра вычисляется основной цвет, как среднее между цветом всех пикселей. В качестве оптимизации вместо суммирования всех пикселей, используется только каждый десятый, в итоге обрабатывается только около 2000 пикселей. Это является достаточным для определения среднего цвета, так как в кадре не будет присутствовать мелких деталей, которые повлияли бы на результат.
Так как в данном решении используется только черный и белый цвета, полученный цвет необходимо отнести к одной из этих групп. В процессе тестирования было обнаружено, что черный при различном освещении не сильно изменяется, в отличии от белого. Поэтому было принято решение определять как черный цвет только те кадры, средний цвет которого по каждому каналу RGB (Red, Green, Blue) не больше 80 (число получено в результате проведенных тестов). Все остальные цвета причисляются к белому. Полученный цвет добавляется как единичный или нулевой бит к текущему сообщению.
5. Декодирование сигнала
Процесс продолжается до тех пор, пока не будет получено достаточное количество битов для декодирования сообщения. За количество битов принимается троекратная длина закодированного сообщения с преамбулой. Так как было задано, что на каждый такт выделяется 3 кадра, сначала нужно попытаться разбить текущий код на подпоследовательности по 3 элемента. Каждая подпоследовательность должна удовлетворять одному из условий:
a) Равны только первый или второй бит подпоследовательности
b) Равны только второй и третий бит подпоследовательности
Эти условия следуют из того, что в середине каждого такта обязательно происходит смена цвета. Для каждого разбиения считается ошибка - количество подпоследовательности, которые не удовлетворяют ни одному из условий. Из разбиений выбирается то, у которого наименьшая ошибка. Затем каждые 3 бита в соответствии с Манчестерским кодированием заменяются на один исходный бит. Если в подпоследовательности была ошибка, то анализируются биты слева и справа и выбирается наиболее вероятный исходный бит. В исходных битах сигнала после этого ищется преамбула, чтобы определить начало сообщения и затем сообщение декодируется с помощью кода Хэмминга.
В данном разделе требуется уточнить, что данный алгоритм был создан для тестирования системы и маловероятно применим в настоящем приложении, так как получение сигнала основано на том, что в кадре ничего кроме передатчика нет. Этот алгоритм можно сравнить со сканированием QR-кода, для правильной работы приемник должно находиться в непосредственной близости к передатчику. Данный алгоритм можно улучшить с помощью детектирования передатчиков путем сравнения последовательных кадров и анализирования их положения относительно камеры, но требуется учитывать возможность перемещения приемника, изменение угла обзора и многие другие факторы.
Таким образом, дальнейшее улучшение решение возможно с помощью алгоритмов компьютерного зрения и требует отдельного исследования, основа которого заложена в текущей работе.
Как результат, данная технология имеет множество возможностей для развития и может предоставлять точность в пределах нескольких сантиметров. К тому же эта технология не подразумевает реализацию алгоритмов, основанных на силе сигнала, а значит она менее подвержена различным колебаниям, зависящим от передвижения предметов и многих других факторов.
4.Улучшение точности
Так как данные о местоположении, полученные с помощью вышеописанных методов, могут быть неточны, ввиду различных факторов и нестабильности сигнала, одной из задач было улучшение точности путем использования датчиков телефона и дополнительных алгоритмов.
4.1 Фильтр Калмана
Для сглаживания полученных данных и улучшения точности в определении местоположения был выбран фильтр Калмана, так как он работает в онлайн режиме, и его реализация включает использование информации, поступающей с датчиков телефона. В качестве датчиков был использован акселерометр, показывающий ускорение движения по осям x, y и z и компас, определяющий направление движения.
Фильтр Калмана использует динамическую модель системы (например, физический закон движения), известные управляющие воздействия и множество последовательных измерений для формирования оптимальной оценки состояния. Алгоритм состоит из двух повторяющихся фаз: предсказание и корректировка. На первой рассчитывается предсказание состояния в следующий момент времени (с учетом неточности измерения). На второй - новая информация с датчика корректирует предсказанное значение (также с учетом неточности этой информации). Благодаря пошаговой структуре алгоритма, он может отслеживать состояние объекта в реальном времени, используя только информацию о предыдущем состоянии, текущее состояние системы и ошибку в измерении.
Рисунок 8. Фильтр Калмана
На схеме (Рисунок 8) представлен алгоритм работы фильтра Калмана. Далее будут разобраны все переменные, указанные в формулах с теми значениями, которые применяются в текущем проекте.
Начальными значениями являются: нулевой вектор состояния (X) и единичная матрица P. Матрица P - это апостериорная ковариационная матрица ошибок, задающая оценку точности полученной оценки вектора состояния.
На формуле 1 представлен вектор состояния системы, который включает в себя координаты X и Y на плоскости и проекция скорости на координатные оси.
|
(2) |
Первым шагом этапа предсказания является предсказание текущего состояния системы на основе предыдущей итерации вычисления (Формула 2).
|
(3) |
На формуле 3 представлена матрица эволюции системы. Она воздействует на вектор на каждом шаге предсказания системы. В качестве переменной t, используется время прошедшее, с предыдущего обновления вектора состояния.
|
(4) |
Можно заметить, что если расписать формулу (Формула 4), то на шаге предсказания X и Y изменяются по закону прямолинейного равномерного движения.
|
(5) |
На формуле 5 представлен вектор управляющих воздействий. В текущем решении - это вектор проекции ускорения на оси X и Y.
|
(6) |
Формула 6 отображает матрицу управления, которая воздействует на вектор u (Формула 5).
|
(7) |
Теперь, если вернуться к изначальной формуле (Формула 2), можно заметить, что на первом шаге используется стандартная формула равноускоренного прямолинейного движения (формула 7).
|
(8) |
На втором шаге обновляется матрица P - предсказывается ошибка ковариации (Формула 7).
|
(9) |
На формуле 9 показана используемая ковариационная матрица шума процесса (Q), где acc - это параметр ошибочности данных, полученных с акселерометра, а t - время прошедшее с начала процесса фильтрации. Стоит заметить, что в данном решении было сделано допущение, что ошибка акселерометра по оси X не влияет на ошибку по оси Y.
|
(10) |
На первом шаге этапа корректировки высчитывается коэффициенты усиления (Формула 10), которые отображают степень доверия расчетной и эмпирической величинам. В формуле используется матрица H, связывающая вектор состояния и вектор измерений.
На формуле 11 представлена ковариационная матрица шума измерений. В качестве значений этой матрицы берется точность измерения местоположения с помощью вышеописанных методов.
На следующем шаге обновляется оценка с учетом измерений, поступающих с акселерометра и компаса. Для того, чтобы получить ускорение в системе координат, связанной с Землёй, необходимо умножить инвертированную матрицу поворота, полученную с компаса на вектор ускорения, полученного с акселерометра. Таким образом, в качестве измерений получается ускорение на север и восток или ax и ay.
Последний шаг - это обновление ошибки ковариации (Формула 13). В данной формуле I - единичная матрица. Все остальные параметры были описаны выше.
4.2 Результаты применения
Фильтр Калмана применялся к каждому методу и в результате тестирования было выявлено, что не для всех методов он позволяет улучшить результат.
Алгоритм оказался плохо применим к текущей реализации методов основанных на GSM и Wi-Fi, так как с их помощью местоположение определялось стабильно (то есть не было выявлено признаков большой зашумленности данных), но с плохой точностью. Фильтр Калмана в первую очередь основывается на данных о местоположении и пытается их уточнить, но если признаков шума в исходных данных не обнаруживается, то измерения с датчиков не сильно влияют на итоговый результат. В первую очередь, такое поведение вызвано использованием сторонних сервисов, где вероятно уже происходит сглаживание данных и тем, что сервисы не выдают достаточно точное местоположение. Предположительно, алгоритм с использованием предварительного сканирования мог бы быть уточнен с помощью фильтра Калмана, так как он выдает лучшую точность, но больше подвержен нестабильности сигнала от точек доступа или вышек сотовой связи.
Фильтр Калмана показал хороший результат для BLE Beacons. Так как сила сигнала, полученная непосредственно с Bluetooth датчика, является нестабильной в силу неточности датчика и ряда других факторов, то и итоговые результаты о местоположении будут содержать большое количество шума. Фильтр Калмана помог сгладить нестабильность в получении местоположения и снизил увеличил точность определения местоположения с 3-х метров до одного.
Стоит понимать, что фильтр Калмана напрямую не влияет на определение точности местоположения, он убирает шум и выбросы, которые дают плохую точность, вследствие чего средняя точность определения местоположения увеличивается.
Для технологии VLC фильтр Калмана тоже применялся, но неуспешно на данном этапе реализации этого метода. В данном решении для определения местоположения по VLC необходимо находиться в непосредственной близости от передатчика, а так как для тестирования использовалось ограниченное количество передатчиков, и они располагались с меньшей частотой, чем могли бы располагаться лампы, то данные о местоположении поступали реже, чем в предыдущих методах. Фильтр Калмана, как уже говорилось ранее, в первую очередь использует информацию о местоположении и уточняет её с помощью датчиков.