Содержание к диссертации
Введение
1 Введение 6
1.1 Обработка изображений в целом 6
1.2 Распознавание символьных изображений
1.2.1 Современное состояние проблемы распознавания образов 7
1.2.2 Постановка задачи и её практическая значимость 8
1.3 Восстановление изображений, искажённых перспективным преобразо
ванием 9
1.3.1 Реставрация изображений 9
1.3.2 Постановка задачи и её практическая значимость 9
1.4 Разбиение железнодорожного состава на отдельные вагоны 10
1.4.1 Обнаружение движущихся объектов и отслеживание траектории их движения 10
1.4.2 Постановка задачи и её практическая значимость 10
2 Распознавание символьных изображений 12
2.1 Краткий обзор методов 12
2.2 Постановка задачи и общий подход к её решению 17
2.3 Метод, основанный на модификации метрики Хаусдорфа 2.3.1 Определение hm—расстояния 18
2.3.2 Свойства hm—расстояния 19
2.3.3 Описание алгоритма сравнения 19
2.3.4 Оценка трудоёмкости алгоритма сравнения изображений с использованием hm—расстояния 20
2.4 Метод срезов 22
2.4.1 Определение бесконечного вектора и расстояния на множестве бесконечных векторов 23
2.4.2 Определение линейного образа и расстояния на множестве линейных образов 23
2.4.3 Свойства приведённых расстояний 24
2.4.4 Описание алгоритма сравнения 25
2.4.5 Оценка трудоёмкости алгоритма сравнения 25
2.5 Метод радиальных окрестностей 26
2.5.1 Определения 26
2.5.2 Используемые расстояния 27
2.5.3 Свойства приведённых расстояний 27
2.5.4 Описание алгоритма сравнения 29
2.5.5 Оценка трудоёмкости алгоритма сравнения 29
2.6 Описание проведённых экспериментов и результатов работы алгоритмов 30
2.6.1 Эксперимент №1 30
2.6.2 Эксперимент №2 31
2.6.3 Эксперимент №3 32
2.6.4 Результаты работы алгоритмов 32
3 Восстановление изображений 35
3.1 Краткий обзор методов 35
3.2 Обозначения, определения и постановка задачи
3.2.1 Определение перспективного преобразования 37
3.2.2 Постановка задачи 38
3.2.3 Обозначения и определения 38
3.2.4 Формальная постановка задачи 40
3.2.5 Дополнительные ограничения для условия и решения задачи 40
3.3 Решение задачи 41
3.3.1 Необходимые и достаточные свойства Т/г, 41
3.3.2 Вычисление Ть 43
3.4 Применение найденного решения 49
3.4.1 Алгоритм восстановления растровых изображений в оттенках серого 50
3.4.2 Примеры изображений 52
4 Разбиение ж/д состава на отдельные вагоны 54
4.1 Краткий обзор методов решения подобных задач 54
4.2 Входные и выходные данные 59
4.3 Характеристики фильмов 59
4.4 Обозначения и определения 4.4.1 Общие обозначения и определения 60
4.4.2 Пометки, серии, основной поток, основное течение 60
4.4.3 -пометки, краевой поток, краевое течение 4.5 Структура алгоритма разбиения состава 63
4.6 Используемые переменные 64
4.7 Вспомогательные процедуры 4.7.1 Повышение контрастности изображений 66
4.7.2 Общая процедура подготовки кадров 66
4.8 Выделение активной области кадра 67
4.8.1 Накопление суммарной разницы 68
4.8.2 Определение границ активной области 69
4.9 Обработка кадров на начальном этапе движения 70
4.9.1 Основная процедура обработки кадров на этапе начального движения 70
4.9.2 Обнаружение края вагона 71
4.9.3 Отслеживание траектории края вагона 73
4.9.4 Оценка скорости с учётом перспективного искажения кадров 79
4.9.5 Непосредственная оценка скорости 83
4.10 Этап основного движения 83
4.10.1 Процедура обработки кадров на этапе основного движения 83
4.10.2 Оценка текущей скорости ж/д состава 86
4.10.3 Оценка скорости во время выхода ж/д состава из области видимости 88
4.10.4 Обнаружение просветов в кадре 88
4.10.5 Регистрация новой пометки 90
4.11 Обработка накопленных данных на заключительном этапе 94 СОДЕРЖАНИЕ
4.11.1 Основная процедура заключительного этапа 95
4.11.2 Определение условного веса течения 96
4.11.3 Определение веса серии 98
4.11.4 Определение координаты разделяющей вертикали 101
4.12 Описание проведённых экспериментов и результатов работы алгоритма 102
5 Заключение 104
- Современное состояние проблемы распознавания образов
- Метод, основанный на модификации метрики Хаусдорфа 2.3.1 Определение hm—расстояния
- Обозначения, определения и постановка задачи
- Обработка кадров на начальном этапе движения
Введение к работе
Актуальность темы исследования
К настоящему моменту область обработки изображений уже прошла длинный путь развития. Важным шагом на этом пути явилось изобретение фотографии, которая позволила наглядно документировать результаты научных исследований. Следующим шагом послужило появление вычислительных машин, достаточно мощных, чтобы работать с изображениями — это позволило автоматизировать и ускорить их обработку. Сегодня обработка изображений представляет собой активно развивающуюся область знания, методы которой используются во многих естественных науках и технических дисциплинах.
Действительно, изображение является объектом исследования или его результатом в таких областях человеческой деятельности, как космонавтика, астрономия, биология, медицина, физика, геология, криминалистика, дефектоскопия и других. Изображения получают не только в диапазоне частот электромагнитного излучения, отвечающего видимому свету, но и в диапазоне частот акустическом, инфракрасном, ультразвуковом, ультрафиолетовом, рентгеновских и гамма-лучей. Большой объём видеоинформации ведёт к необходимости автоматизации процессов её обработки. Среди направлений исследований в данной области, приведённых в работе [1, стр. 5-6], выделим следующие два.
Восстановление искажённых изображений, а также улучшение их визуального качества заключается в его преобразовании, обратном преобразованию, вызвавшему искажение. Соответствующие алгоритмы восстановления позволяют скомпенсировать искажения, обусловленные рефракцией или турбулентностью атмосферы, недостатками оптических приборов, взаимным расположением устройства съёмки и объектов наблюдения, деформацией фотоматериала, помехами и т. д. Улучшение визуального качества изображений облегчает их восприятие и анализ человеком.
Автоматическое чтение текста, дешифрование аэрокосмических снимков, диагностика заболеваний — примеры задач, относящихся к проблеме распознавания образов. Интерес, проявляемый к её разработке в настоящее время, связан с открывающимися возможностями лучшего понимания процессов обработки информации в живых системах, создания более эффективных систем «человек-машина», а также автоматических систем, позволяющих быстрее, точнее, надёж-
нее или экономичнее человека решать различные задачи обработки визуальной информации.
Выделим отдельно задачу обнаружения на видеопоследовательности движущихся объектов и отслеживание их траектории. Для решения данной задачи (точнее, подзадачи обнаружения) оказываются полезными методы распознавания образов. Алгоритмы, разрабатываемые в процессе решения задачи обнаружения и отслеживания, предназначены для использования во всевозможных системах наблюдения и контроля.
Цели исследования
Целями диссертационной работы являются:
разработка методов распознавания чёрно-белых растровых изображений алфавитно-цифровых символов малого размера;
разработка алгоритма восстановления изображений, искажённых перспективным преобразованием;
разработка алгоритма разбиения железнодорожного состава на отдельные вагоны.
Результаты, выносимые на защиту
Разработаны три метода распознавания чёрно-белых растровых изображений алфавитно-цифровых символов малого размера; произведена оценка их трудоёмкости; изучены некоторые свойства расстояний между изображениями, лежащих в основе предложенных методов; предложено четыре модели искажения чёрно-белых растровых алфавитно-цифровых символов; разработана программная реализация методов; проведён ряд экспериментов для проверки эффективности предложенных методов с использованием искусственно построенных и реальных тестовых изображений, в ходе которых выполнено сравнение данных методов с аналогичным.
Разработан алгоритм восстановления изображений, искажённых перспективным преобразованием; приведено теоретическое обоснование данного алгоритма; разработана программная реализация алгоритма; выполнено тестирование алгоритма с использованием набора изображений.
Разработан алгоритм разбиения железнодорожного состава на отдельные вагоны; разработана программная реализация данного алгоритма; проведено тестирование алгоритма с использованием набора видеопоследовательностей.
Методы исследования
В диссертационной работе использованы методы обработки изображений, распознавания образов (в том числе обнаружения объектов), проективной геометрии, математического анализа.
Научная новизна работы
В проведённых экспериментах с использованием реальных зашум-лённых цифровых символов, а также цифровых символов с искажениями каркаса результаты предложенных методов распознавания оказались близкими к результатам корреляционного алгоритма или лучшими по сравнению с ними.
Преимущество алгоритма восстановления изображений, искажённых перспективным преобразованием, над аналогичными состоит в том, что он не использует каких-либо параметров оптической системы, с помощью которой было получено изображение. В некоторых случаях восстановление изображений может быть полностью автоматизировано.
Преимущества алгоритма разбиения железнодорожного состава на отдельные вагоны по сравнению с аналогичными состоят в том, что он в одном случае является более автоматизированным, а в другом — не требует наличия вспомогательных технических средств.
Практическая значимость работы
Методы и алгоритмы, разработанные в ходе работы над диссертацией, могут быть использованы для создания систем наблюдения за движением автомобильного или железнодорожного транспорта (в том числе для решения задачи идентификации); предложенные методы распознавания могут найти применение также и в системах автоматического чтения текста.
Апробация работы
Основные положения работы докладывались и обсуждались на перечисленных ниже научных конференциях и семинарах.
Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодёжь. Наука. Инновации — 2009», 2009, г. Ярославль.
IV Между народная научно-практическая конференция «Современные информационные технологии и ИТ-образование», 2009, г. Москва.
XLVIII Между народная научная студенческая конференция «Студент и научно-технический прогресс»: Информационные технологии, 2010, г. Новосибирск.
XV Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов, 2010, г. Рязань.
II Международная молодёжная научно-практическая конференция,
2010, г. Елабуга.
5. Шестьдесят четвёртая региональная научно-техническая конферен
ция студентов, магистрантов и аспирантов с международным участием,
2011, г. Ярославль.
Семинар института программных систем им. А.К. Айламазяна РАН, 2011, г. Переславль-Залесский.
Семинар «Моделирование и анализ информационных систем», 2011, г. Ярославль.
Семинар «Нелинейная динамика и синергетика», 2011, г. Ярославль.
Публикации
По теме диссертационной работы опубликовано 15 печатных работ (в том числе 5 публикаций в ведущих рецензируемых научных изданиях, рекомендованных Высшей аттестационной комиссией), а также получено свидетельство о государственной регистрации программы для ЭВМ. Из пяти статей три написаны без соавторов, две — тремя авторами (Малков А.Н., Штерн Г.П., Михайлов И.А.). Все совместные работы написаны в нераздельном соавторстве. Список работ приведён в конце автореферата.
Структура и объём работы
Диссертация состоит из введения, трёх разделов, заключения, списка литературы и приложения. Работа изложена на 112 страницах, содержит 2 таблицы, 6 рисунков, библиография включает 60 наименований.
Современное состояние проблемы распознавания образов
Единой теории распознавания образов, включающей все главные разделы, нет, ибо каждой области применения свойственны ей одной присущие особенности, в расчёте на которые и строится соответствующий подход [1, стр. 7]. Даже в такой, казалось бы, простой задаче распознавания, как автоматическое чтение текста, общих, исчерпывающих и экономических решений не найдено до сих пор [3, стр. 7]. Создание каждого нового приложения в данной области по-прежнему остаётся творческой задачей и требует дополнительных исследований в связи со специфическими требованиями, предъявляемыми к возможному решению [10].
Основная причина такого положения дел в отрасли заключается в том, что многие относящиеся к ней задачи с трудом поддаются формализации или не формализованы вообще. Поэтому вопросы автоматизации обработки изображений не могут быть быстро и легко разрешены на удовлетворительном уровне. Следует указать также и на научную и техническую сложность любой сколько-нибудь серьёзной задачи из данной области (пример — распознавание треков частиц в ядерных исследованиях) [3, стр. 7-8].
Рассматривается задача распознавания чёрно-белых растровых изображений алфавитно-цифровых символов, заданных матрицами из нулей и единиц соответствующего размера. Изображения: как эталоны, так и тесты — могут быть различного размера; для приведения их к одному размеру используется масштабирование. Исходный размер изображений (тестов и эталонов) лежит в пределах от 7 х 12 до 9 х 15 пикселей. Цель состоит в разработке алгоритмов распознавания описанных символьных изображений.
Найденные решения с большим или меньшим успехом можно использовать в таких задачах, как распознавание номеров железнодорожных цистерн [11, 12], распознавание регистрационных номеров автомобилей [13, 22, 21], распознавание печатных [30] и рукописных [29, 18] символов в системах автоматического чтения текста [10]. 1 ВВЕДЕНИЕ
Можно выделить две смежные области в предобработке изображений: улучшение изображений и их реставрацию [4]. Первая из них включает в себя комплекс операций, имеющих цель преобразования изображения в форму, более удобную для визуального или машинного анализа. Реставрацию же можно рассматривать как процесс оценивания: некоторое изображение, полученное в результате наблюдения или измерения, подвергают преобразованию, чтобы найти оценку идеального изображения, которое наблюдалось бы на выходе гипотетической изображающей системы, не вносящей никаких искажений. Методы улучшения и реставрации имеют проблемно-ориентированный характер, так как решаемые ими задачи отличаются специфичностью.
В задаче автоматического распознавания образов (см., например, [13, 11]) исходные изображения, подлежащие анализу, часто оказываются искажены перспективным преобразованием [7, 3]. Это происходит из-за того, что объект наблюдения расположен под некоторым углом к видеокамере или другому аналогичному устройству. В некоторых случаях анализ этих изображений может быть упрощён и лучше автоматизирован, если устранить перспективное искажение до начала основной обработки. Нами рассматривается вопрос восстановления изображений, подверженных перспективному преобразованию. Будем предполагать, что известны искажённое изображение, предпочтительный размер восстановленного изображения, а также коорди 1.4 Разбиение железнодорожного состава на отдельные вагоны наты точек, прообразы которых в исходном изображении лежали на горизонтальных прямых. Цель состоит в разработке соответствующего алгоритма восстановления.
В соответствии с описанной выше классификацией поставленная задача является задачей реставрации изображений, а именно задачей коррекции геометрических искажений, частным случаем которых является перспективное.
Задача, решаемая нами в настоящей работе, — задача разбиения железнодорожного состава на отдельные вагоны. Данную задачу можно отнести к классу задач обнаружения объектов на видеопоследовательности и отслеживания траектории их движения, так как в процессе разбиения определяется наличие вагонов в области видимости, а затем до окончания обработки кадров выполняется оценка скорости ж/д состава, вычисляются длины вагонов и их количество. В настоящее время данная область развивается, примеры систем, реализующих те или иные методы обнаружения и отслеживания, можно найти в работах [12, 11], [38] - [48]. Алгоритмы, разрабатываемые в этой области, обычно предназначаются для различных систем видеонаблюдения, в частности, одно из основных её направлений — наблюдение за движением автотранспорта (примеры можно найти в работах [38] - [43]).
Одна из задач, возникающих при создании автоматизированных систем регистрации железнодорожных составов (см. работы [12, 11]) заключается в разбиении состава на отдельные вагоны. В настоящей работе предлагается алгоритм для решения этой задачи. На вход алгоритму передаётся фильм, полученный с помощью видеокамеры в тот период времени, когда состав двигался в её области видимости; кроме того, передаются параметры, определяющие перспективное искажение изображения вагонов на кадрах фильма. На выходе алгоритм для каждого кадра, на котором виден край некоторого вагона, должен сообщать абсциссу вертикальной линии, отделяющей данный вагон от соседнего вагона (или от фона, если вагон является первым или последним).
Метод, основанный на модификации метрики Хаусдорфа 2.3.1 Определение hm—расстояния
Следствием этого утверждения является тот факт, что сопоставление двух окрестностей может быть выполнено за время O(s), так как длина векторов, из которых состоят окрестности, не может превышать s.
Если использовать для поиска наиболее похожих окрестностей полный перебор, в общей сложности придётся выполнить т2п2 сравнений окрестностей, следовательно, этап сопоставления радиальных образов может быть выполнен за время 0(m2n2s). Как следствие утверждений, приведённых в данном разделе, выпишем окончательную теорему о стоимости сравнения изображений в целом. Теорема 2.5.6 Сравнение изображений с использованием рр-расстояния на множестве радиальных образов мооюет быть выполнено за время 0(m2n2s), где s — коэффициент нормирования. Описание проведённых экспериментов и результатов работы алгоритмов Для оценки эффективности методов было проведено 3 эксперимента. Вначале опишем используемые в каждом из них наборы эталонов и тестов, затем приведём сводные результаты работы алгоритмов.
В первом эксперименте набор эталонов включал в себя 10 изображений символов 0 — 9 высотой 14 пикселей, полученных с помощью шрифта Times New Roman. Данный набор будем обозначать CS.
Тестовые изображения строились посредством искажения изображений из набора CS. Искажения вносились с использованием 4-х моделей. Заметим, что высота построенных тестовых изображений также равнялась 14 пикселям. В конце описания 2 РАСПОЗНАВАНИЕ СИМВОЛЬНЫХ ИЗОБРАЖЕНИЙ каждой модели будем давать обозначение набора тестовых изображений, полученного с её помощью.
Нанесение на изображение-эталон одиночных чёрных пикселей. Расположение каждого пикселя выбиралось случайно. Их количество варьировалось от 1 до 50. Обозначение — NP.
Нанесение на изображение-эталон прямых линий. Направление, длина и толщина линий были случайны; длина колебалась в пределах от 1 до 7 пикселей, толщина — от 1 до 3 пикселей. Цвет половины из них совпадал с цветом фона, поэтому они стирали части контура символа; цвет остальных совпадал с цветом символа. Обозначение — NL.
Алгоритмы искажения каркаса символа, описанные далее, на входе получают последовательность узлов (или цепь), построенную вручную. Узел представляет собой координаты некоторой точки контура. Цепь в среднем содержит 25 узлов, распределённых по всему контуру. В цепь символа-эталона вносились изменения, затем она отображалась в растр.
Сдвиг каждого узла цепи на случайный вектор. При этом координаты изменялись не более, чем на 20% от размеров изображения. Обозначение — SS.
Разбиение каркаса символа на несколько сегментов, поворот каждого сегмента относительно узла, случайно выбранного в данном сегменте. Количество сегментов выбиралось случайно в диапазоне от 2 до б. Угол поворота лежал в пределах от —к/6 до тг/6. Обозначение — ST.
Таким образом, в данном эксперименте использовались четыре различных тестовых набора, каждый из которых включал в себя 5000 изображений (500 для каждого из 10 эталонов).
Эксперимент №2 Во втором эксперименте набор эталонов остался прежним, а в качестве тестов был взят набор изображений цифр, вырезанных с фотографий номеров цистерн после их 2.6 Описание проведённых экспериментов и результатов работы алгоритмов бинаризации. Он содержит изображения всех цифр. Общее количество изображений в наборе — 1614. Средний размер тестов — 8x15 пикселей. Данный набор, некоторые изображения из которого показаны на рис. 1, будем обозначать ЕХР.
В третьем эксперименте в качестве эталонов был взят набор изображений, вырезанных из бинаризованных фотографий цистерн. Этот набор использовался в работе [11] для тестирования. Он включает в себя 55 изображений всех цифр за исключением единицы. Введём обозначение для данного набора — ES. На рис. 2 показаны примеры изображений-эталонов, входящих в его состав. В качестве тестов был взят тот же набор изображений, что и во втором эксперименте, однако все изображения символа Г были удалены из него, так как используемый набор эталонов ES их не содержит.
Прежде чем привести результаты, сделаем несколько замечаний. Частота сечений в алгоритме метода срезов бралась равной 150, в алгоритме метода радиальных окрестностей коэффициент нормирования s брался равным 100, а в алгоритме метода, осно 32 ванного на модификации метрики Хаусдорфа, в качестве расстояния между точками на плоскости использовалась следующая величина: w + h где zx,z x — их абсциссы, zy,zy — ординаты, w,h — ширина и высота изображения соответственно. Из каждого изображения (как эталона, так и теста) перед началом основной обработки удалялись крайние левые (правые) столбцы и крайние верхние (нижние) строки, не содержащие чёрных пикселей, в случае их присутствия.
Для сравнения представим также и результаты работы корреляционного алгоритма, описанного в работе [11]. При описании результатов будем использовать следующие обозначения:
Покажем теперь результаты проведённых экспериментов, представив их в табличной форме: первый столбец содержит обозначения используемых наборов эталонов и тестов соответственно, разделённые косой чертой; в каждой строке приведено соответствующее число верно распознанных тестов для четырёх алгоритмов (в процентах).
Методы распознавания символьных изображений, изложенные в данном разделе, опубликованы в работах [56, 57, 59]. Фрагменты исходного кода программного модуля, реализующего предложенные методы распознавания, приведены в приложении.
Обозначения, определения и постановка задачи
Будем предполагать, что а/ Є (—7г/2,0) U (0,7г/2), фокус С/ лежит внутри угла а/, изображения / и Г полностью лежат на гранях угла а/ (но не на их продолжениях). Пусть х1 с — абсцисса точки пересечения прямых А\А2 и 5 , в координатах изображения. Будем считать, что х с Є (—со,0) U (гі/, +00), где и/ — ширина / . На решение задачи наложим следующие ограничения: схь (—7г/2,0) U (0,7г/2), фокус Сь лежит внутри угла аь, изображения І7 и I" полностью лежат на гранях угла аь. Необходимые и достаточные свойства Т/ь для выполнения условия (1)
В этом разделе показано, какими свойствами должно обладать преобразование Т/ь, чтобы выполнялось условие (1). Пусть {х,у) — некоторая точка в р, {х ,у ) — её проекция в р , построенная с помощью Т/, (х",у") — проекция (х ,у ) в р", построенная с помощью Ть- Используя теорему синусов, можно найти следующие соотношения для преобразования Tf.
Так как нам нужно, чтобы преобразование Т/ь удовлетворяло (1), то естественно потребовать, чтобы горизонтальные прямые плоскости р переходили под воздействием Tfb в горизонтальные прямые р". Воспользуемся этим условием, чтобы выделить искомые свойства Tfb- Для этого зафиксируем с точностью до параметра а некоторую точку А(х + а,у) Є р. Если Tfb: А(х + а,у) — А"{х"а,у"а), то у"а должна быть независима от а. Используя (7), (4) и (5), получаем
Анализируя равенства (8) и (9), можно сделать следующие выводы: горизонтальное смещение изображения относительно фокуса Сь может быть различным, вертикальное должно совпадать со смещением относительно фокуса С/ для сохранения горизонтальности прямых. Воспользовавшись полученными соотношениями, вновь выразим (х", у") через (х, у) с помощью (4), (5), (6) и (7). После приведения получим которое гарантирует отсутствие вертикальной инверсии [ку 0). Чтобы подытожить сказанное в данном разделе, выпишем следующую теорему. Теорема 3.3.1 Для выполнения условия (1) необходимо и достаточно, чтобы выполнялись соотношения (8), (9), гарантирующие сохранение горизонтальности прямых, и соотношение (12), гарантирующее отсутствие вертикальной инверсии.
Условие совпадения знаков а/ и аь является необходимым для выполнения (1). В этом разделе показано, как можно узнать знак af, если известны координаты точек А ъ А 2, В[, Б 2, прообразы которых лежат на горизонтальных прямых.
Пусть А(хі,уі), Аа(хі + а,уі), В(х2,у2), Bb(x2 + b,y2) — точки, лежащие на горизонтальных прямых в плоскости р, А , А а, В , В ь — их образы, полученные с помощью перспективного преобразования 7/ через фокус С/. Используя (4) и (5), найдем уравнения прямых А А а и В В Ь.
С другой стороны, из рис. 4а видно, что для всякой точки Af (х, у) Є р, лежащей правее Mf (х —Ifdgaf), её образ A f(x ,yr) будет располагаться правее Mf (точки, лежащие левее Mf, не рассматриваются в соответствии с ограничениями, описанными в разделе 3.2.5). Следовательно, точка пересечения прямых А А а и В В ь будет располагаться левее всякого преобразованного изображения / (её абсцисса будет иметь отрицательное значение в координатах изображения).
В этом разделе выведены некоторые соотношения между параметрами Ть, необходимые и достаточные для того, чтобы Tfb сохраняло горизонтальность прямых.
Пусть точки iteinS/ii)» А 2(х\2 у\2), В х у ), В 2(х22,уг22) лежат на прямых, прообразы которых горизонтальны. Тогда их образы А {А 2 и В [В2 также должны быть горизонтальны. Так как положение изображения V относительно фокуса
Можно показать, что преобразование Ть при условии (25) переводит прямоугольное изображение / в изображение /", ограниченное трапецией с вертикальными основаниями. Это значит, что ширина из" равна расстоянию между основаниями, а высота h" — расстоянию между самой высокой и самой низкой точками на основаниях. Введём дополнительные обозначения. Пусть
До сих пор под изображением понималось множество точек с вещественными координатами, каждой из которых был сопоставлен некоторый цвет. Однако реальные изображения представляют собой растры — прямоугольные решётки пикселей с целочисленными координатами. В этом разделе приведён алгоритм обратного перспективного преобразования растровых изображений в оттенках серого, разработанный на основе найденного решения.
Обработка кадров на начальном этапе движения
В данном разделе описан вспомогательный алгоритм, выполняемый на подготовительном этапе основного алгоритма. Задача, решаемая вспомогательным алгоритмом, состоит в выделении активной области кадра (что это такое, будет описано несколько позже). Цель его выполнения — повышение эффективности алгоритма вычисления начальной и конечной скоростей ж/д состава и некоторое ускорение обработки кадра в целом. Входными данными для алгоритма служит фильм, выходными — координаты левой и правой границ активной области. Прежде, чем приступить к формальному описанию алгоритма, дадим неформальное определение активной области кадра и представим предположение, лежащее в основе алгоритма её выделения.
Некоторые фильмы из экспериментальной выборки, используемой нами, отличаются следующим свойством: около правой или левой границы каждого кадра можно видеть светлую стену (см. рис. 6). Активная область кадра может быть получена путём отсечения от кадра прямоугольной области высоты Н, примыкающей к левой или правой границе и содержащей изображение стены. Таким образом, активная область задаётся абсциссами своих левой и правой границ. Активная область одинакова для всех кадров заданного фильма.
Предположение, лежащее в основе предлагаемого решения задачи выделения активной области, состоит в том, что часть кадра с изображением стены как совокупность яркостей пикселей мало изменяется на протяжении всего фильма, в то же время часть кадра внутри активной области изменяется значительно, так как здесь можно видеть движение ж/д состава. Разумеется, на кадре могут присутствовать области, расположенные выше или ниже состава, которые также изменяются незначительно, но можно говорить о том, что внутри активной области изменения яркостей пикселей происходят в каждом пиксельном столбце.
На первом из них для каждого к-го кадра фильма вычисляется суммарная по-пиксельная разница между данным кадром и предыдущим считанным; результат вычисления сохраняется (накапливается). На втором этапе на основе высказанного выше предположения и с учётом полученных результатов обработки определяются левая и правая границы активной области.
Предполагается, что объекты Ь0 (предыдущий обработанный кадр), Ь0_а (средние яркости в каждом столбце предыдущего обработанного кадра), ds(x,y) (суммарная попиксельная разница между соседними кадрами) и с/р (счётчик обработанных кадров) сохраняют свои значения между вызовами данной процедуры.
В данном разделе будут описаны процедуры и функции, предназначенные для обработки кадров на начальном этапе движения. Локальная задача, решаемая на данном этапе, — определение начальной скорости ж/д состава. Для решения данной подзадачи предлагается отслеживать движение края первого вагона, а затем, зная пройденный путь и затраченное время, оценить скорость. Для того, чтобы минимизировать погрешности оценки, связанные с неточным определением горизонтальной позиции края вагона, предлагается отслеживать его движение в течение максимально возможного периода времени.
Используемая нами процедура обнаружения края вагона в кадре (описанная в разд. 4.9.2) обладает следующим свойством: вместе с s-пометками, более или менее точно определяющими край вагона, она в большинстве случаев возвращает множество s-пометок, далеко отстоящих от края. Поэтому возникает дополнительная подзадача определения s-пометки, предположительно соответствующей краю, среди всех выделенных на очередном кадре с учётом результатов обработки предыдущих кадров; решение этой подзадачи описано в разд. 4.9.3. Как оценить скорость движения в условиях перспективного искажения кадров, описано в разделах 4.9.4 и 4.9.5. Основная процедура, вызываемая на начальном этапе движения для обработки каждого считанного кадра, описана в разд. 4.9.1.
В данном разделе будет описана процедура обнаружения края первого или последнего вагонов на кадре. Предположение, лежащее в основе данной процедуры, состоит в следующем. Пусть на некотором кадре можно видеть край вагона. Рассмотрим две области на этом кадре: узкую вертикальную полосу рядом с краем, содержащую изображение части вагона, и такую же узкую полосу с другой стороны края, содержащую фоновое изображение. Область с фоном как совокупность яркостей пикселей 4.9 Обработка кадров на начальном этапе движения осталась почти такой же, как и на предыдущем кадре (относительно среднего уровня яркости), в то же время область, содержащая часть изображения вагона, за тот же межкадровый промежуток изменилась значительно в результате движения состава (предполагается, что изображения частей вагона значительно отличаются от фона). Таким образом, если в кадре найти все вертикальные линии, разделяющие области с указанными свойствами, то, по-видимому, одна из них будет соответствовать краю.
