КП (1027375), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Подходы к решению задачи “привязывания” точек рельефа к их высотным отметкам:

1. Итерационный.

Пока количество точек или текстов не равно 0:

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

1. Линейное программирование. Венгерский алгоритм.

Задачу привязывания” точек рельефа к их высотным отметкам можно переформулировать в терминах линейного программирования как задачу о назначении. Основной целью при данном подходе является минимизация сумму расстояний от точек до текстов.

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время. Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари). Временная сложность оригинального алгоритма былаO(n⁴), однако Эдмондс и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O(n³) [13].

1. Машинное обучение. Обучение нейросети с учителем.

В основе данного подхода лежит предположение о том, что плотность распределения точек и текстов на всех чертежах одинаковая. Данное предположение выглядит вполне разумно, так как коридор для проектирования трассы является вырезкой из топоплана (карты) высокой точности. В топоплане (карте) высокой точности должны быть определённые закономерности, так как составлением топопланов (карт) высокой точности занимаются специальные институты (например, ЦНИИГАиК - Государственный Институт Геодезии и Картографии).

1. Для каждой точки определить кротчайшее расстояние до ближайшего текста.

2. Объединить точки в группы, на основании “схожести” расстояний, полученных в 3.1. Получить распределение количества точек данного радиуса от величины радиуса P(N,r) . Данное распределение в какой-то степени характеризует текущий чертеж (см. рис. 4.2.).

Рис. 4.2. Распределение, характеризующее текущий чертеж.

1. Попытаться "сжать" данные о распределении. Ввести параметры математического ожидания и дисперсии подобно нормальному распределению (либо параметр лямбда, аналогично пуассоновскому распределению).

2. Для текущего чертежа получить оптимальный радиус. Большой радиус приведет к сильному "задействованию" пользователя в процессе распознавания и тем самым сократит долю автоматического распознавания. Малый радиус приведет к неточному распознаванию (определенное количество точек вовсе будут не привязаны к текстам).

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

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

1. Искусственный интеллект. Моделирование логики человека при решении данной задачи.

1. Генерируется область поиска вокруг каждой из точек рельефа.

2. В данной области ищутся тексты. Информация о найденных текстах сохраняется.

3. Запускается алгоритм автоматического распознавания для тривиальных случаев. Если не все точки распознаны goto 3., иначе goto 4.

4. Определение высоты точки при помощи пользователя в нетривиальном случае. Если не все точки распознаны goto 3., иначе end

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

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

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

Если R слишком большой, то все случаи будут не тривиальными и пользователю придётся определять значения высот для каждой точки.

Если R будет слишком мал, то точки, скорее всего, будут распознаны неправильно.

В реализованном в программе алгоритме радиус R выбирается следующим образом:

1. Для каждой точки определить кротчайшее расстояние до ближайшего текста.

2. Выбрать максимальное расстояние.

3. Увеличить максимальное расстояние на 1, что гарантирует пересечение текста (а не касание), и принять его за радиус поиска R.

4.1.3. Алгоритмы обработки горизонталей

На этапе распознавания горизонталей предполагается, что завершился этап распознавания точек рельефа и точки рельефа распознаны правильно.

Так как данная задача относится к классу плохоформализуемых задач (см. 2.2.), одним из возможных подходов к её решению является моделирование логики человека при решении данной задачи.

Реализованный в программе алгоритм автоматизированной обработки горизонталей:

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

2. В данной области ищутся точки (“соседние” с текущей)

3. далее последовательно “соединяем” текущую и соседние с ней точки секущей линией.

4. Определяем количество горизонталей пересечённых данной линией.

5. Округляем значение высоты текущей и соседней точек рельефа (с точностью до шага горизонталей (является настройкой)). Получаем их разность и делим на шаг горизонталей. Получаем количество линий в тривиальном случае (тривиальный случай заключается в том, что между 2-мя точками высота горизонталей либо возрастает, либо убывает (сложный случай – между 2-мя точками существуют различные участки, на которых значении горизонталей то возрастают, то убывают.))

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

4.2. Алгоритмы распознавания чертежей профиля

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

Рис. 4.3. Информация, содержащаяся на чертеже профиля, разбитая на логические группы

Реализованный в программе алгоритм автоматизированного распознавания изыскательских чертежей профиля:

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

2. Объединяем тексты в группы, на основании их геометрического расположения (тексты заголовка подвала находятся в одном столбце "подвала" (на одной вертикали))

3. Задаём приоритет группам (на основании количества текстов в группе и расположения на чертеже (приоритет имеют группы текстов находящиеся левее и имеющие больше всего текстов))

4. Заносим группы с приоритетами в дерево возможных решений

5. Выбираем очередную группу и пытаемся продолжить распознавание

6. Проверяем наличие ячеек таблицы вокруг текстов из группы и совпадение правых и левых границ ячеек.

Если проверка вернула отрицательный результат goto 5.

Иначе goto 7.

1. Ищем горизонтальные линии, такие что:

1. находятся правее правой границы заголовка подвала,

2. их координатами Y соответствуют координатам верхних и нижних границ ячеек

1. Объединяем полученные в 7. горизонтальные линии в группы на основании схожести (с определенной точностью (1мм)) их начальных и конечных значений координат X

2. Задаём приоритет группам (На основании количества линий в группе, длины линий, и расположения относительно правой границы подвала)

3. Заносим группы с приоритетами в дерево возможных решений

4. Выбираем очередную группу и пытаемся продолжить распознавание

5. Распознаем строки "Расстояния", "Высотные отметки", "Изыскательский пикетаж"

1. Распознаем Масштаб

2. Определяем координату Y начала линии профиля

1. Распознаем строку "Развернутый план"

2. Определяем расположение ординат

3. Распознаем ординаты

4. Определяем расположение информации о геологии

5. Распознаем геологию

4.2.1. Распознавание подвала

Чертеж продольного профиля по существу состоит из двух частей:

1. подвала - сетки с горизонтальными графами, в которых приведены цифровые данные полевых и проектных работ

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

Подвал в свою очередь можно разделить на 2 части:

1. “Тело” подвала – часть подвала, в которой приведены цифровые данные полевых и проектных работ (см. рис. 4.4.).

Рис. 4.4. “Тело” подвала. Сверху – исходные данные. Снизу – выделены строки, подлежащих обработке. Желтым отмечены строки подвала “Высотные отметки”, “Расстояния” и “Пикетаж”, зеленым - строка подвала “Развёрнутый план”

1. “Заголовок” подвала – часть подвала, содержащая названия горизонтальных граф, в которых приведены цифровые данные полевых и проектных работ (см. рис. 4.5.).

Рис. 4.5.“Заголовок” подвала. Слева – исходные данные. Справа – выделены названия строк, подлежащих обработке. Желтым отмечены названия строк подвала “Высотные отметки”, “Расстояния” и “Пикетаж”, зеленым - строка подвала “Развёрнутый план”

4.2.1.1. Распознавание строк подвала “Высотные отметки”, “Расстояния” и “Пикетаж”

Перед началом распознавания строк подвала “Высотные отметки”, “Расстояния” и “Пикетаж” необходимо определить масштаб и “линейку” высот (см. рис. 4.6.).

Рис. 4.6. Масштаб и “линейка” высот

Реализованный в программе алгоритм автоматизированной обработки строк подвала “Высотные отметки”, “Расстояния” и “Пикетаж” (см. рис.4.7.):

1. Получить строки “Высотные отметки”, “Расстояния” и “Пикетаж”.

2. Создать линию профиля по меткам Пикетажа (по длинным вертикальным линиям в графе "Расстояния")

3. Добавить начальную и конечную точки линии профиля

4. Восстановить значения пикетов (в том случае если пикеты нумеруются от 1 до 9 (после 9-ки следует пустое место))

5. Найти тексты в строке подвала "Расстояния" находящиеся между соответстующимися пикетами

6. Найти тексты в строке подвала "Высотные отметки" находящиеся между соответстующимися пикетами

7. Сопоставить тексты из строки “Расстояния” с текстами из строки “Высотные отметки”.

Рис. 4.7. Строки подвала “ Высотные отметки”, “ Расстояния” и “ Пикетаж”

4.2.1.2. Распознавание строки подвала “Развёрнутый план”

Развернутый план содержит информацию о:

- вершинах углов поворота пути, их обозначениях и номерах, начале и конце кривых, их обозна­чениях и привязке к пикетам;

- числовых значениях элементов кривых: углах поворота, радиусах, тангенсах, суммарных длинах круговых и переходных кривых, длинах переходных кривых;

Характеристики

Список файлов курсовой работы