Как я писал магистерскую диссертацию по компьютерному зрению

    В этой статье я продолжу тему компьютерного зрения.

    См. предыдущие статьи: Простой алгоритм распознавания движений и алгоритм поиска смещения объектов на изображении. Напомню, что написать эти статьи меня сподвигло то, что когда я начал работать над магистерской диссертацией на тему «Анализ пространственной структуры динамических изображений», то столкнулся с проблемой, что очень трудно найти какие-то готовые примеры алгоритмов распознавания образов и движущихся объектов. Везде, и в литературе, и в Интернете одна только голая теория. С тех пор прошло довольно много времени, я успел успешно защитить диссертацию и получить красный диплом, а теперь пишу, чтобы поделиться опытом.

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

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

    1. Предобработка изображения (удаление шума, улучшение контрастности, масштабирование и так далее).
    2. Нахождение деталей (линии, границы, точки интереса)
    3. Детектирование, сегментация.
    4. Высокоуровневая обработка.

    Ну ок, нарисовал схему программы, которая все это должна делать:

    image

    Короче, получилось, что я должен создать нечто грандиозное уровня Искусственного Интеллекта. Ну ок, попытаюсь создать. Беру Visual Studio и начинаю в C# ваять классы. Точнее, заготовки классов. Чуть позже понял, на что я замахнулся….

    Итак, начинаю отрабатывать первый шаг. Предобработка. Начал с нее, потому что

    1. Это самое простое.
    2. Это первый шаг из списка.

    Стал применять к изображению разные фильтры, смотреть, что получается. Попробовал, например, применить фильтр Собеля:

    image

    Удалить шумы из изображения методом размытия по гауссу:

    image

    Изучил медианную фильтрацию и выделение контуров:

    image

    Во всем этом мне очень помогла лекция о компьютерном зрении с лекториума.

    Итак, знаний стало гораздо больше, но все равно непонятно, как решить задачу. К тому времени тема и задача магистерской диссертации несколько раз пересматривалась, и в итоге была сформулирована так: «Отслеживание траектории БЛА по кадрам аэрофотосъемки». То есть мне нужно было взять ряд фотографий и построить по ним траекторию.

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

    • Классическое выделение контуров Canny из библиотеки OpenCV
    • Разработанный моим научным руководителем улучшенный алгоритм выделения контуров.
    • Выделение контуров путем бинаризации.
    • Выделение контуров путем сегментации. Сегментация проводилась различными способами, в частности, с использованием текстурных признаков.

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

    Ну а дальше научный руководитель подсказал идею: надо использовать особые точки. И даже дал алгоритм, как эти ключевые точки вычислять. Надо сказать, что это был очень нестандартный метод. Это не детектор Харриса, и не BRISK, и не MSER и не AKAZE. Хотя я и их тоже пытался использовать. Но, как оказалось, предложенный научным руководителем детектор работал лучше. И вот принцип его работы. Сначала вычисляем вот по такой формуле контурный препарат:

    image

    image

    Потом находим экстремумы данной функции. Это и есть особые точки. Что характерно, точки могут быть двух типов «Пики» и «ямы». Вот пример этих точек на изображении:

    image

    Далее, из полученных точек отбираются 50 точек с максимальным откликом. По всем этим точкам строятся треугольники, количество треугольников, образованных данными точками, равно:

    image

    где k – количество особых точек, участвующих в расчете. Для каждого треугольника вычисляется специальный индекс от 0 до 16383. Следующий шаг – распределение треугольников по специальному массиву, в котором номер ячейки соответствует индексу треугольника. Каждая ячейка такого массива представляет собой список из треугольников. Такой массив составляется по двум сравниваемым кадрам. Сопоставления производиться путем сопоставления каждой ячейкой массива с соответствующей ячейкой массива другого кадра. Всего нужно сопоставить 16384 групп, что является вполне выполнимой задачей для компьютера за достаточно короткий промежуток времени.

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

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

    image

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 9

      +2
      1 причем тут с#?
      2 Довольно слабенький велосипед. Что вы будете делать с перспективными искажениями на небольшой высоте? На взлете например. И зачем изобретать велосипед? Сегодня методы SLAM неплохо оптимизированы и довольно хороши. Ваш метод лучше хоть чем то? Сначала изучите то, что уже есть, а потом пишите свое.
      Не интересно от слова совсем.
        –3
        «1 причем тут с#?» — при том что прога на C# была написана
          0
          при том что прога на C# была написана

          И как это повлияло на статью?
          — А как еще она была написана? На лаптопе или на десктопе? На Интеле или АМД? На кухне или в ванной? Ну так добавьте соответсвующие метки для полноты картины.
        +1

        Моя вторая магистерская работа была на оооочень схожую тему. По сути — реализация того, что уже сделали в MIT. Только времени и ума не хватило довести до конца.


        Справедливости ради, авторы оригинала (и я в том числе) использовали цепи Маркова для вычисления смещения слоев, аппроксимацию RANSAC для вычисления смещения одного слоя и быстрое преобразование Фурье на упрощенном рисунке (через оконную функцию, Лапласса если правильно помню, считались контуры объектов) для вычисления векторов смещения. И это все дело авторы также считали по пирамидам для каждого изображения.


        То бишь, достаточно сложная работа даже в плане реализации.


        Учитывая что вся эта кутерьма должна была бы гоняться по видео (а это даже на моем старом телефоне 24 кадра в секунду, с кадром ок. 4000 x 2000 пикселей), то чтобы реализовать оптимально нужно было нехило пораскинуть умом (простой параллелизации недостаточно). Я попытался заменить FFT на Optical Flow и RANSAC на что-то еще (уже не помню), что в общем-то не заработало (возможно реализация некорректная была).


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


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

          0
          Особые точки за что-то «цепляются» (угол, например), а у вас они словно распределены случайно. Ощущение, что формируете из экстремумов что-то вроде хеша.
            0
            По сути, они цепляться из экстремумов функции от яркости точек. Форума приведена в статья.
              0
              Картинки результата работы этой функции в статье не хватает. Формула приведена, но не дано никакого описания того, что она делает. Выглядит так, что вам дали «магическую» функцию, и всё, что сделали — отобрали максимумы из результата её вызова. К сожалению, не раскрыто самое интересное.
            –2
            Слушай круто. Возможно мне пригодится. Спасибо.
              0

              С нетерпением ждем результат — определение координат ЛА относительно поверхности земли, изображение которой записано на видео.
              А в перспективе хотелось бы проанализировать архивные видеосъёмки посадки Апполонов на поверхность Луны.

              Only users with full accounts can post comments. Log in, please.