Разработка программы для вычисления скорости движения предмета

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«Ижевский государственный технический университет имени М.Т. Калашникова»
(ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова»)

Факультет «Информатика и вычислительная техника»
Кафедра «Вычислительная техника»

Разработка программы для вычисления скорости движения предмета по видеозаписи

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА
Пояснительная записка


«Утверждаю»
Зав.кафедрой ВТ, д.т.н., профессор

Руководитель
к.т.н., доцент

Н.контроль

Разработал
студент группы 8-78-2


Ижевск 2014
Оглавление
1. Обозначения и сокращения 3
1. Введение 4
2. Обоснование темы и ее актуальности 5
3. Постановка задачи 6
4. Выбор метода решения задачи 7
5. Основные сведения об Android и Android-приложениях 8
5.1. Архитектура Android 8
5.2. Компоненты Android-приложения 14
6. Основные сведения о библиотеке OpenCV 17
7. Разработка программы 23
8. Анализ результатов 24
9. Выводы 25
10. Список использованной литературы 26
11. Приложения 27

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

 
2. Обоснование темы и ее актуальности
Нет сомнений, что измерения скоростей движения предметов на основе применения световых датчиков, датчиков, основанных на эффекте Доплера, либо на других видах датчиков, дают результаты более высокой точности, чем измерения на основе видеосъемки. Это связано с тем, при записи видео большую роль играют освещенность места съемки, разрешение видеозаписывающего устройства. Большие погрешности могут производить другие движущиеся объекты, неоднородность среды, в которой ведется съемка, повышенная влажность воздуха, погрешности при переводе аналоговых сигналов световых потоков в цифровую форму представления, а также другие шумовые факторы .
Но, к сожалению, применение датчиков не всегда возможно, поэтому для определения примерных значений скоростей можно воспользоваться и программой обработки видеосъемки.
В настоящее время большую популярность приобретают смартфоны с камерами высокого разрешения. В связи с этим наиболее актуальным было бы написание программы измерения скорости на операционных системах Android или iOS, наиболее широко распространенных в наше время. Написанная программа служила бы хорошим инструментом для решения задач определения скорости с использованием только лишь смартфона без участия какой-либо сторонней аппаратуры.
Кроме того, до сих пор написано не так уж и много программ, решающих задачу измерения скорости предметов как на ОС Android, так и на ОС iOS. Поэтому написание мобильного приложения заданной тематики имеет в настоящее время большую актуальность.

 
3. Постановка задачи
Необходимо разработать программу, которая на основе видеозаписи движения некоторого предмета определяет скорость его движения.
На вход программы необходимо подавать некоторую привязку к реальным размерам предмета. Данную привязку можно осуществить несколькими способами. Способ привязки определяется программистом, причем, выбранный способ привязки должен быть интуитивно понятен среднему пользователю разрабатываемой программы.
На выходе программа должна выдавать пользователю усредненную величину движения исследуемого предмета.



 
4. Выбор метода решения задачи
Для решения поставленной задачи будем использовать открытую библиотеку OpenCV, представляющую собой мощный инструмент для работы с изображениями и видеопотоками. Описание библиотеки приводится в главе 6 данной пояснительной записки.
Выберем для написания программы ОС Android. Выбор можно обосновать тем, что устройства с данной ОС, как правило, имеют более высокие, по сравнению с ОС iOS, разрешения камер, экранов, довольно удобный интерфейс. Кроме того, в настощее время в России имеют большее распространение мобильные устройства на базе ОС Andriod, нежели на базе ОС iOS. Краткое описание Android приводится в главе 5 данной пояснительной записки.

 
5. Основные сведения об Android и Android-приложениях
5.1. Архитектура Android
Платформа Android представляет собой программный стек для мобильных устройств, который включает операционную систему, программное обеспечение промежуточного слоя (middleware), а также основные пользовательские приложения, входящие в состав мобильного телефона, календарь, карты, браузер, базы данных контактов, сообщений SMS и др. []
Архитектуру Android принято делить на четыре уровня:
• уровень ядра;
• уровень библиотек и среды выполнения;
• уровень каркаса приложений;
• уровень приложений.
Основные компоненты ОС Android и их взаимодействие показаны на рисунке 5.1.1.









Рисунок 5.1.1 – Архитектура системы Android 
Уровень ядра
Ядро является слоем абстракции между оборудованием и остальной частью программного стека. На этом уровне располагаются основные службы типа управления процессами, распределения памяти и управления файловой системой.
Android основан на ядре Linux версии 2.6, но сама система Android не является Linux-системой в чистом виде. Система Android имеет некоторые отличия и содержит дополнительные расширения ядра Linux, специфичные для Android, — свои механизмы распределения памяти, взаимодействие между процессами и др.
Приложения и службы могут работать в защищенных отдельных процессах, которые должны общаться между собой и иметь доступ к общим данным. Платформа Android поддерживает механизм IPC (Inter-process Communication), который является основным механизмом взаимодействия процессов. Драйвер IPC обеспечивает взаимодействие процессов, создание и обработку пулов потоков в процессах, подсчет и отображение ссылок на объекты в других процессах и синхронные запросы между процессами.
Поскольку Android является платформой для мобильных устройств и должна обеспечивать экономный расход аккумуляторной батареи телефона, важную роль выполняет система управления энергопотреблением — Android Power Management. Она разработана на основе стандартного драйвера управления питанием Linux, но оптимизирована для мобильных устройств с учетом их специфических особенностей. Драйвер переводит систему в "спящий режим" с минимальным потреблением мощности процессором, если приложения и службы не используются.

Программный стек Android разработан с учетом необходимой гибкости, включая работу со многими дополнительными компонентами, имеющимися в мобильных устройствах. Эти компоненты в значительной степени полагаются на доступность определенных аппаратных средств на данном устройстве. Они предоставляют дополнительную функциональность для мобильных устройств (сенсорный экран, камера, GPS, акселерометр и т. д.).
На этом уровне также расположен набор драйверов для обеспечения работы с оборудованием мобильного устройства. Набор драйверов может отличаться в зависимости от производителя и модели устройства. Поскольку новое вспомогательное оборудование для мобильных устройств постоянно появляется на рынке, драйверы для них должны быть написаны на уровне ядра Linux для обеспечения поддержки оборудования, так же как и для настольных Linux-систем.
Преимущество использования ядра Linux как основы Android в том, что ядро системы позволяет верхним уровням программного стека оставаться неизменными, несмотря на различия в используемом оборудовании. Конечно, хорошая практика программирования требует, чтобы пользовательские приложения корректно завершали свою работу в случае вызова ресурса, являющегося недоступным, например встроенной видеокамеры или сенсора, не присутствующего в данной модели телефона.

Уровень библиотек
Следующий уровень над ядром Linux включает набор библиотек C/C++, используемых различными компонентами ОС. Библиотеки этого уровня по своему функциональному назначению можно разделить на две группы:

• системная библиотека С;
• функциональные библиотеки С/С++.
Системная библиотека базируется на Berkeley Software Distribution (BSD). Компания Google разработала собственную версию системной библиотеки libc — Bionic специально для мобильных устройств на основе Linux. Это было необходимо для обеспечения быстрой загрузки библиотеки в каждый процесс, и следовательно, библиотека должна была иметь маленький размер. Библиотека Bionic имеет размер около 200 Кбайт, что в два раза меньше размера стандартной библиотеки Linux glibc. Кроме того, необходимо было учитывать ограниченную мощность центрального процессора мобильного устройства. Это означает, что библиотека должна быть оптимизирована для максимального быстродействия. Конечно, сейчас это уже не актуально, современные мобильные устройства практически сравнялись по мощности процессора с нетбуками, но еще несколько лет назад это являлось серьезной проблемой.
Библиотека Bionic имеет встроенную поддержку важных для Android системных служб и регистрацию системных событий, но в то же время она не поддерживает некоторую функциональность, например исключения C++, и несовместима с GNU libc и стандартом POSIX.
Функциональные библиотеки представляют собой набор библиотек C/C++ типа OpenGL, WebKit, FreeType, SSL, базы данных SQLite и библиотек мультимедиа (Media Framework). Для разработчиков доступ к функциям этих библиотек реализован через использование Application Framework — каркаса приложений.

 
Dalvik Virtual Machine
Среда выполнения обеспечивает библиотеки ядра Dalvik Virtual Machine (виртуальная машина Dalvik), которые предоставляют требуемую функциональность для Java-приложений.
Прикладное программное обеспечение, запускаемое на мобильном устройстве, исполняет виртуальная машина Dalvik, которая хоть и является аналогом виртуальной машины Java, существенно от нее отличается. Dalvik относится к классу регистровых машин (регистры процессора используются как первичные модули хранения данных), идеально подходящих для работы на процессорах RISC-архитектуры, к которым относятся и процессоры ARM, применяемые в мобильных устройствах, тогда как стандартная виртуальная машина Java компании Sun Microsystems — стековая. В результате использования регистровой виртуальной машины Google надеется на 30 процентов уменьшить количество команд по сравнению со стековыми машинами.
Виртуальная машина Dalvik, на которой построена вся операционная система Google Android, дает разработчикам удобный механизм для написания приложений, которым не принципиален объем используемой памяти и мощность процессора.

Уровень каркаса приложений
Уровень каркаса приложений находится на вершине системных библиотек, функциональных библиотек и Dalvik VM. На этом уровне находятся основные службы Android для управления жизненным циклом приложений, пакетами, ресурсами и т. д.
Программист имеет полный доступ к тем же API, которые используются основными приложениями. Архитектура этих приложений разработана с целью упрощения многократного использования компонентов. Любое разрабатываемое приложение может использовать возможности базовых приложений и, соответственно, любое другое стороннее приложение может использовать возможности вашего приложения (с учетом установленных разрешений). Этот же самый механизм позволяет многократно использовать уже разработанные компоненты.
Уровень приложений
Мобильное устройство Android поставляется с набором основных приложений, включая почтового клиента, программу для работы с SMS, календарь, навигационные карты, браузер, контакты и др.
Что интересно, платформа Android не делает разницы между основными приложениями, входящими в комплект мобильного телефона и сторонним программным обеспечением — таким образом, ключевые приложения, входящие в стандартный набор программного обеспечения, можно заменить при желании альтернативными приложениями.
При разработке приложений программисты имеют полный доступ ко всей функциональности операционной системы. Архитектура приложений построена так, чтобы было легко использовать основные компоненты, предоставляемые системой. Также есть возможность создавать свои компоненты и предоставлять их в открытое использование.

5.2. Компоненты Android-приложения
Приложения для Android состоят из компонентов, которые система может запускать и управлять так, как ей необходимо.
Всего в Android-приложениях существует четыре типа компонентов:
• Activity;
• Service;
• Broadcast Receiver;
• Content Provider.
Взаимодействие компонентов осуществляется с помощью объектов Intent. Рассмотрим вышеперечисленные компоненты и их взаимодействие.

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

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

Broadcast Receiver
Компонент Broadcast Receiver — компонент для получения внешних событий и реакции на них. Инициализировать передачи могут другие приложения и Service. Приложение может иметь несколько компонентов Broadcast Receiver, чтобы ответить на любые объявления, которые оно считает важными.
Broadcast Receiver не имеют пользовательского интерфейса. Однако они могут запустить Activity или службу, выдать в ответ на информацию, которую они получают, или показать уведомление на экране мобильного устройства, чтобы предупредить пользователя о наступившем событии.

Content Provider
Компонент Content Provider делает определенный набор данных, используемых приложением, доступным для других приложений. Этот компонент является своеобразным посредником между хранилищем данных и клиентским приложением.
Данные в Android могут быть сохранены различными способами: в файловой системе, в базе данных SQLite или любым другим способом. Content Provider для безопасного доступа к данным используют механизм разрешений. Это означает, что вы можете cконфигурировать собственный Content Provider, чтобы разрешить доступ к своим данным из других приложений, а также использовать Content Provider другого приложения для обращения к его хранилищу данных.

Intent
Главная особенность платформы Android состоит в том, что одно приложение может использовать элементы других приложений при условии, что эти приложения разрешают использовать свои компоненты. При этом ваше приложение не включает код другого приложения или ссылки на него, а просто запускает нужный элемент другого приложения.
Поэтому, в отличие от приложений в большинстве других систем, у приложений Android нет единственной точки входа для запуска всего приложения, аналогичной, например, функции main() в C-подобных языках программирования.
Для реализации такого использования компонентов других приложений система должна быть в состоянии запустить процесс для приложения, в котором находится требуемый компонент, и инициализировать нужные ей объекты. 
6. Основные сведения о библиотеке OpenCV

 
7. Некоторые виды преобразований изображений
7.1. Детектор границ Кенни
Детектор границ Кенни является самым популярным методом выделения границ на изображениях.[]
Границы (края) – это такие кривые на изображении, вдоль которых происходит резкое изменение яркости или других видов неоднородностей.
Другими словами, граница — это резкое изменение яркости.
Причины возникновения краёв:
• изменение освещенности;
• изменение цвета;
• изменение глубины сцены (ориентации поверхности).
Получается, что края отражают важные особенности изображения и поэтому, целями преобразования изображения в набор кривых являются:
• выделение существенных характеристик изображения;
• сокращение объема информации для последующего анализа.
Детектор границ Кенни был разработан в 1986 году Джоном Кенни. Кенни изучил с точки зрения математики проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Он показал, что этот фильтр может быть хорошо приближен первой производной Гауссианы. Кенни ввел понятие Non-Maximum Suppression (подавление не-максимумов), которое означает, что пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Хотя его работа была проведена на заре компьютерного зрения, детектор границ Канни до сих пор является одним из лучших детекторов. Кроме особенных частных случаев трудно найти детектор, который бы работал существенно лучше, чем детектор Кенни.[]
Алгоритм детектора является многоступенчатым и включает в себя следующие основные этапы:
• Сглаживание. Размытие изображения для удаления шума. Кенни использует фильтр, который может быть хорошо приближен к первой производной Гауссианы.
• Поиск градиентов. Границы отмечаются там, где градиент изображения приобретает максимальное значение. Они могут иметь различное направление, поэтому алгоритм Кенни использует четыре фильтра для обнаружения горизонтальных, вертикальных и диагональных ребер в размытом изображении.
• Подавление не-максимумов. Только локальные максимумы отмечаются как границы.
• Двойная пороговая фильтрация. Потенциальные границы определяются порогами.
• Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.
 
7.2. Преобразование Хафа
Преобразование Хафа позволяет находить на монохромном изображении линии, круги или другие простые формы. Монохромным изображением считается изображение, состоящее из точек двух типов: фоновых точек и точек интереса (смотрите рисунок 7.2.1). Задача преобразования Хафа состоит в выделении кривых, образованных точками интереса.[]

Рисунок 7.2.1 – Пример монохромного изображения
Идея преобразования Хафа состоит в поиске кривых, которые проходят через достаточное количество точек интереса. Рассмотрим семейство кривых на плоскости, заданное параметрическим уравнением (7.2.1).
F(a1, a2, .., an, x, y) = 0, где (7.2.1)
F – некоторая функция,
a1, a2, .., an – параметры семейства кривых,
x, y – координаты на плоскости.

Параметры семейства кривых образуют фазовое пространство, каждая точка которого соответствует некоторой кривой. Ввиду дискретности машинного представления и входных данных (изображения), требуется перевести непрерывное фазовое пространство в дискретное. Для этого в фазовом пространстве вводится сетка, разбивающая его на ячейки, каждая из которых соответствует набору кривых с близкими значениями параметров. Каждой ячейке фазового пространства можно поставить в соответствие число (счетчик), указывающее количество точек интереса на изображении, принадлежащих хотя бы одной из кривых, соответствующих данной ячейке. Анализ счетчиков ячеек позволяет найти на изображении кривые, на которых лежит наибольшее количество точек интереса.
Рассмотрим пример нахождения прямых линий на изображении.
Формулу прямой линии в полярных координатах можно записать в виде формулы (7.2.2). Графическое представление показано на рисунке 7.2.2.
 = x * cos() + y * sin(),где (7.2.2)
 - длина перпендикуляра, опущенного на прямую из начала координат,
 - угол между перпендикуляром к прямой и горизонтальной осью.

Рисунок 7.2.2 – Графическое представление
прямой в полярных координатах 
Через каждую точку изображения можно провести несколько прямых с разными параметрами  и  (смотрите рисунок 7.2.3), то есть каждой точке (x, y) изображения соответствует набор точек в фазовом пространстве (, θ), образующий синусоиду. В свою очередь каждой точке пространства (, θ) соответствует набор точек (x, y) на изображении, образующий прямую. Каждой точке (0, θ0) пространства (, θ) можно поставить в соответствие счетчик, соответствующий количеству точек (x, y), лежащих на прямой  = x * cos() + y * sin().
Ввиду дискретности машинного представления и входных данных, требуется перевести непрерывное фазовое пространство в дискретное. Введем сетку на пространстве (, θ), одной ячейке которой соответствует набор прямых с близкими значениями  и θ. Теперь счетчик ставится в соответствие каждой ячейке сетки: ячейке [i, i+1]x[θi, θi+1] соответствует число точек, удовлетворяющих уравнению:
 = x * cos() + y * sin(), где θi ≤ θ ≤ θi+1, i ≤  ≤ i+1.
Размер ячеек стоит выбирать, учитывая следующие соображения. Если ячейки будут очень большими, то за "прямую" может приниматься разрозненный набор точек. Если же наоборот, ячейки будут слишком малы, есть вероятность, что ни одной прямой не найдется – все счетчики будут иметь небольшое значение.



 
8. Разработка программы

 
9. Анализ результатов

 
10. Выводы


 
11. Список использованной литературы

 
12. Приложения