Iii региональная научно-практическая студенческая конференция

Список литературы

В настоящее время во многих городах проводится обследование пассажирских потоков на маршрутах государственного пассажирского транспорта с целью выявления оптимальной работы пассажирского транспорта. Юридическим основанием для проведения сплошного обследования пассажирских потоков на маршрутах государственного пассажирского транспорта общего пользования в городском округе – город Камышин, краткое название «СОПП», является договор между Администрацией городского округа – город Камышин и Камышинским технологическим институтом (филиалом) Волгоградского государственного технического университета №02/2009 от 30 января 2009 года.

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

Для реализации модели необходимо собрать и обработать данные. На протяжении 4 дней(13.02, 15.02, 16.02, 18.02) проводилось исследование, в котором принимали участие студенты нашего института (в дальнейшем будем называть их учетчиками). Целью их работы было зафиксировать время и загруженность пассажирского транспорта. Свои наблюдения учетчики заносили в определенные таблицы.

Рис. 1 – Пример таблицы с внесенными данными

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

Рис. 2 – Блок-схема алгоритма обработки первичных данных

Алгоритм обработки первичных данных (рисунок 2) реализован программно на языке VBA в Microsoft Excel, в связи с чем, можно с легкостью собрать данные о конкретном маршруте на отдельный лист.

Рис. 3 – Результат работы данной программы
В дальнейшем планируется доработать этот алгоритм, чтобы при выборе файлов данные о каждом маршруте заносились на отдельный лист. Таким образом, получится книга, листами которой будут номера маршрутов. Также планируется провести анализ пассажиропотока по времени, по маршрутам, по дням, по загруженности транспорта и анализ за 4 дня.

ИССЛЕДОВАНИЕ МЕТОДОВ КОНТУРНОЙ СЕГМЕНТАЦИИ

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

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

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

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

Рис. 1. Примеры прослеживания внешних контуров: а – начальная точка расположена

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

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

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

Рис. 2. Примеры соединения точек перепадов по правилу Робертса

В методе Робертса аналоговые значения градиентов (разности яркостей соседних элементов) анализируются блоками размером 4´4 элемента. Элемент с наибольшим в блоке значением модуля градиента считается пробной контурной точкой, если это значение больше порога. Затем к значениям градиента около этой пробной точки подбираются линии длиной в пять элементов с ориентацией “север”, ”восток”, ”юг”, “запад”. Если отношение наилучшей аппроксимации к наихудшей больше второго порога, то пробная контурная точка объявляется действительной и ей приписывается ориентация, соответствующая наилучшей аппроксимации. Далее к парам контурных точек подбираются прямые линии, если эти точки расположены в смежных блоках размером 4´4 элемента и если направление каждой линии находится в диапазоне ±23^° относительно ориентации контура в каждой контурной точке. Точки, не удовлетворяющие критериям соединения, отбрасываются. Типичная граница, полученная на этом этапе, будет содержать, как видно из рис. 2(а), разрывы и множественные соединения точек. Маленькие треугольники исключаются вычерчиванием наибольшей стороны, а маленькие четырехугольники заменяются их наибольшей диагональю (рис. 2(б)). Короткие выступающие линии также уничтожаются. На этом этапе короткие разрывы заменяются мостиками из прямых линий. Этот вид соединения точек перепада можно использовать для широкого класса детекторов перепада.

Мы считаем, что объединив метод Робертса с алгоритмом прослеживания контуров можно добиться больших результатов, так как рассмотренные методы наиболее просты в реализации и обладают набольшей скоростью работы по сравнению с аналогичными современными методами контурной сегментации.

1. 
   Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений // М.: Высшая школа, 1983. 295 с.
   
2. 
   У. Претт «Цифровая обработка изображений», том 2 // М.: Высшая школа, 1982г.-c.499-500,564-566.
   

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

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

Например, пусть x и y – соответственно оси абсцисс и ординат на гистограмме. Тогда кривая второго порядка

где а, b, c – константы, обеспечивает простую аппроксимацию гистограммы в районе ее «долины».

Минимум гистограммы наблюдается при .

Для определения порога яркости можно использовать оператор Лапласа

Для непрерывного изображения F(x, y) оператор Лапласа дает значения вторых частных производных этой функции по направлениям координатных осей. Рассмотрим область изображения в районе объекта, где яркость увеличивается с уровня низкого «плато» до уровня более высокого «плато», соединенных наклонной поверхностью. На плоских участках лапласиан равен нулю, а вдоль наклонной поверхности – почти нулю. В области перехода от низкого «плато» лапласиан будет иметь большое положительное значение, а при переходе к высокому «плато» – большое отрицательное значение. Гистограмма, построенная с использованием лишь точек исходного изображения, которые соответствуют очень высоким или очень низким значениям лапласиана, оказывается бимодальной с отчетливой «долиной» между пиками. Определению порога яркости могут помочь и другие процедуры выделения перепадов, однако рассмотренные методы являются наиболее приемлемыми в отношении скорости работы и качества подсчета.

Результатами данного исследования стала реализация (рис. 1) и модификация (рис. 2) известного градиентного фильтра выделения границ методом Собела.

Рис 1. Стандартный фильтр Рис 2. Модифицированный фильтр

1. 
   Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений // М.: Высшая школа, 1983. 295 с.
   
2. 
   Сойфер В.А. Компьютерная обработка изображений. Часть 2 Методы и алгоритмы // Соровский образовательный журнал, №3,1996
   

Бинарное пространственное разбиение (Binary Space Partitioning (BSP)) – это разбиение пространства, которое может быть использовано для решения различных геометрических проблем. Оно было первоначально разработано для решения проблемы удаления невидимых поверхностей. BSP имеет два основных варианта в компьютерной графике: выровненное по осям (kd дерево) и выровненное по полигонам.

KD дерево для множества объектов S определяется следующим образом: каждый узел n в kd дереве ассоциируется с выровненной по осям ограничивающей коробкой (axis-aligned bounding box (AABB)) AB(n). Корнем kd дерева является AABB всей сцены S. Каждый внутренний узел дерева n имеет секущую плоскость, которая порождает два дочерних узла.

Каждый листовой узел n может содержать список объектов S(n), которые пересекаются с AABB узла. Если листовой узел содержит хотя бы один объект, то он называется полным листом. Иначе он называется пустым листом.

Во время создания kd-tree сверху вниз должна быть решена проблема сечения AB текущего узла на два новых дочерних узла, а также присвоение объектов родительского узла дочерним узлам. Предполагается, что каждый объект Oi имеет конечный размер, и поэтому имеет конечный AB(Oi ). Из-за того что секущая плоскость в kd-tree перпендикулярна одной из осей, то можно установить по AB объекта, слева или справа от секущей плоскости он расположен. На сегодняшний день самым эффективным способом выбора секущей плоскости является метод оценочной функции, основанный на модели стоимости прохождения луча, через узел.

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

Оценочная функция имеет вид:

(1)

Для выбора оптимального положения делящей плоскости узла, необходимо найти минимальной значение функции стоимости (SAH).

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

Рис. 1. Дискретизация SAH для 10000 попыток

Для ускорения построение дерева необходимо уменьшить количество расчетов SAH без значительной потери точности.

Рис. 2 Дискретизация SAH для 20 значений и нахождение интервала, для детального поиска

Как видно из рисунка 2, дискретизация SAH всего по 20 значениям, позволяет с большой точностью определить интервал, где находиться реальный минимум оценочной функции.

Рис. 3. Повторно дискретизированный участок SAH

1. 
   Благодаря использованию оценочной функции в процессе построения kd-tree структуры, положение делящей плоскости определяется оптимально. Скорость трассировки лучей, с использованием полученной структуры возросла в 1,5-2 раза, в сравнении с обычной kd-tree структурой, где делящая плоскость всегда проходит через середину узла.
   
2. 
   Предложенный метод нахождения значений оценочной функции позволил сократить объем вычислений в сотни раз, при сохранении требуемой точности. Для функции, дискретизированной по 10000 значений, минимум составил -39,42, а для функции, дискретизированной по предложенному методу (дискретизированной по 40 значениям), минимум составил -38,79. Принимая во внимание размеры геометрической сцены по оси Х равные 330,48, погрешность вычислений составила 0,19%, а объем вычислений сократился в 250 раз.