Поиск параметрических кривых на изображениях Левашов Алексей Евгеньевич Юрин Дмитрий Владимирович Московский Государственный Университет им. Ломоносова Факультет вычислительной математики и кибернетики Лаборатория математических методов обработки изображений

Поиск параметрических кривых на изображениях Алгоритм: Детектор граничных линий Детектор граничных линий Утоньшение линий Утоньшение линий Удаление точек ветвления Удаление точек ветвления Сбор линий в списки (векторизация) Сбор линий в списки (векторизация) Анализ списков Анализ списков Быстрая (рандомизированная) проверка гипотезы Быстрая (рандомизированная) проверка гипотезы Детальная проверка гипотезы и уточнение параметров Детальная проверка гипотезы и уточнение параметров

Детектор граничных линий В работе используется алгоритм Канни для изображений в оттенках серого и Дизензо-Кумани для цветных изображений. В работе используется алгоритм Канни для изображений в оттенках серого и Дизензо-Кумани для цветных изображений. Вычисление производных через свертки с Гауссом и подавление немаксимальных точек с линейной интерполяцией приводят к границам с малым числом разрывов и почти везде единичной ширины Вычисление производных через свертки с Гауссом и подавление немаксимальных точек с линейной интерполяцией приводят к границам с малым числом разрывов и почти везде единичной ширины

Утоньшение граничных линий Для гарантии единичной ширины граничных линий применяется алгоритм (Zhang, Suen, 1984). Для гарантии единичной ширины граничных линий применяется алгоритм (Zhang, Suen, 1984). Это алгоритм математической морфологии подобный морфологическому сжатию, но не съедающий концы линий. Это алгоритм математической морфологии подобный морфологическому сжатию, но не съедающий концы линий. Так как линии почти везде шириной в 1 пиксель, требуется всего несколько итераций Так как линии почти везде шириной в 1 пиксель, требуется всего несколько итераций

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

Сбор граничных линий в списки Граничные точки собираются в виде списка кривых, а кривые – в виде списка точек. Граничные точки собираются в виде списка кривых, а кривые – в виде списка точек. Контейнер представляет собой массив указателей на массивы размером по (=2 16 ) элементов. Контейнер представляет собой массив указателей на массивы размером по (=2 16 ) элементов. В этой единой для задачи структуре данных образуются списки. В этой единой для задачи структуре данных образуются списки. Потом данные переупорядочиваются inplace чтобы обеспечить до них доступ как до абстрактного массива, что удобно на стадии случайных тестов, разбиений на фрагменты, МНК и хи-квадрат. Потом данные переупорядочиваются inplace чтобы обеспечить до них доступ как до абстрактного массива, что удобно на стадии случайных тестов, разбиений на фрагменты, МНК и хи-квадрат.

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

Анализ списков. Быстрая проверка гипотезы В каждой точки границы доступна информация - координаты и направление нормали (градиента яркости). Т.о., кривая определяется минимум N точками: прямая - 1 точкой, окружность – 2, эллипс – 3 и т.д. В каждой точки границы доступна информация - координаты и направление нормали (градиента яркости). Т.о., кривая определяется минимум N точками: прямая - 1 точкой, окружность – 2, эллипс – 3 и т.д. Проверка соответствия фрагмента модели осуществляется по нескольким случайным сбросам из N+1 точек, где дополнительная точка контрольная. Проверка соответствия фрагмента модели осуществляется по нескольким случайным сбросам из N+1 точек, где дополнительная точка контрольная.

Анализ списков Если контрольная точка лежит в пределах параметрической кривой, делается некоторое количество дополнительных случайных сбросов, если и они принадлежат кривой, то по всем точкам кривой параметры модели находятся методом наименьших квадратов с регуляризацией на основе SVD. Достоверность гипотезы определяется на основе критерия χ2. Если контрольная точка лежит в пределах параметрической кривой, делается некоторое количество дополнительных случайных сбросов, если и они принадлежат кривой, то по всем точкам кривой параметры модели находятся методом наименьших квадратов с регуляризацией на основе SVD. Достоверность гипотезы определяется на основе критерия χ2.

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

Примеры работы и вычислительные эксперименты Все эксперименты сделаны на процессоре Intel Core 2 Duo 2.00 MHz. Все эксперименты сделаны на процессоре Intel Core 2 Duo 2.00 MHz. Оперативной памяти 2 Гб. Оперативной памяти 2 Гб.

Результаты 1024 x Edge Detector 710 мс Утоншение 340 мс Анализ 70 мс Всего 1120 мс

Результаты 1024 x Edge Detector 710 мс Утоншение 340 мс Анализ 70 мс Всего 1120 мс

Результаты 381 x 381. Edge Detector 80 мс Утоншение 10 мс Анализ 10 мс Всего 100 мс

Результаты 381 x 381. Edge Detector 80 мс Утоншение 10 мс Анализ 10 мс Всего 100 мс

Результаты 1108x Edge Detector 660 мс Утоншение 330 мс Анализ 70 мс Всего 1060 мс

Результаты 1108x Edge Detector 660 мс Утоншение 330 мс Анализ 70 мс Всего 1060 мс

Результаты 559 x 559. Edge Detector 180 мс Утоншение 80 мс Анализ 20 мс Всего 280 мс

Результаты 1000x 667. Edge Detector 360 мс. Утоншение 160 мс. Анализ 30 мс Всего 550 мс

Результаты 1000x 667. Edge Detector 360 мс. Утоншение 160 мс. Анализ 30 мс Всего 550 мс

Результаты 375x486. Edge Detector 100 мс. Утоншение 40 мс. Анализ 20 мс Всего 160 мс

Результаты 375x486. Edge Detector 100 мс. Утоншение 40 мс. Анализ 20 мс Всего 160 мс

Заключение Разработан алгоритм поиска параметрических кривых на изображениях. Разработан алгоритм поиска параметрических кривых на изображениях. Алгоритм легко настраивается на поиск любых параметрических кривых. Алгоритм легко настраивается на поиск любых параметрических кривых. Особенностью алгоритма является векторизация изображения, быстрый рандомизированный анализ кривых, детальный анализ с помощью регуляризирующих МНК и верификация на основе Хи-квадрат. Особенностью алгоритма является векторизация изображения, быстрый рандомизированный анализ кривых, детальный анализ с помощью регуляризирующих МНК и верификация на основе Хи-квадрат. Эти особенности обеспечивают высокую скорость, точность и надежность алгоритма. Эти особенности обеспечивают высокую скорость, точность и надежность алгоритма.

Спасибо за внимание!