Предыдущий урок: Искусственный интеллект для чайников. Урок 1. Нейросети.
На прошлом уроке я рассказал вам, что такое искусственный интеллект и нейронные сети. Но ИИ – это не только нейронные сети. Существует еще очень много разных методов и подходов. Один из них – это компьютерное зрение. Как вы, наверное, догадались, эта технология применятся для того, чтобы найти на изображении определенные объекты, как то осмыслить его. Задача, на самом деле не тривиальная. Но и не такая уж сложная, как кажется на первый взгляд. Чтобы это доказать, разберем простую задачу: «На чёрном фоне есть несколько белый фигур, прямоугольники и треугольники:
Нужно их распознать. Задача действительно простая, так как тут у нас идеальный случай: нет шумов, картинка абсолютно контрастная, нет искажений фигур. В реальном мире так не бывает, но мы пока только учимся. Более сложны задачи можно разбить на части и свети к простым, решив их по отдельности, примерно, как эту.
И так, как будем решать? Очевидно, нам надо каким-то волшебным образом сосчитать углы. У треугольника их три, у прямоугольника – четыре. Таким образом, мы их различим. Но вся проблема в том, что картинка у нас растровая. Поэтому, сначала нам надо перевести ее в какой-нибудь вид, более удобный для того, чтобы сосчитать у фигур углы.
Хорошую идею предлагает в [1] Гонсалес. Суть этой идеи состоит в том, что у фигуры есть центр масс. А каждая точка фигуры задана в полярных координатах относительно этого центра масс. Напомню, что полярные координаты, в отличи от декартовых – это расстояние от центра и угол поворота радиуса-вектора. Лучше всего это иллюстрирует следующая картинка:
На графиках изображена функция зависимости длины радиуса-вектора от угла поворота. Для круга это будет прямая линия, для прямоугольников и треугольников на графике будут пики, соответствующие углам. Естественно, у треугольника на 360 градусов будет три пика, у прямоугольника – четыре. Вот так их и можно различить. Другой вопрос, как из растра перевести фигуры в такой вот хитрый вид.
Данное изображение у нас бинарное. Оно имеет только два цвета – черный и белый. Если мы возьмем произвольную точку, то мы точно можем знать, относиться ли она к фигуре или к фону. Если эта точка относится к фигуре, мы можем проверить, сколько ее соседей так же имеют белый цвет. Если 8 – то эта точка внутри фигуры, если меньше – то эта точка принадлежит контуру. Зная декартовы координаты точки контура и зная координаты центра масс фигуры, мы можем перевести эти координаты в полярные. Вопрос только в том, как определить центр масс фигуры.
Зная координаты всех точек фигуры, ее центр масс вычислить нетрудно. Для этого можно воспользоваться следующими формулами:
где A– количество пикселей, принадлежащих фигуре; I(x,y) – признак принадлежности точки к фигуре, 1 – если принадлежит, 0 – если не принадлежит; m – ширина изображения, n – высота изображения.
Возможно, кто-то спросит: а где тут искусственный интеллект? Мы решаем какие-то геометрические задачи! На это я отвечу: «ИИ – это не только всякие там нейросети, эвристики, генетические алгоритмы, автоматизация логических рассуждение и прочее тому подобное. Это еще и довольно жесткий матан». Скажу больше, основная часть методов искусственного интеллекта – это и есть жесткий матан. Но не пугайтесь, мы будем разбирать этот «жесткий матан» на простых и доступных примерах. В конец концов, те же нейросети работают с некими признаками, которые еще необходимо как-то получить. Если мы попробуем передать нейросети картинку как есть целиком, то ничего хорошего из этого не выйдет. Поэтому ее еще необходимо будет преобразовать в какой-то другой вид, более удобный для анализа нейросетью. И, решает вот эту геометрическую задачу, мы как раз изучаем, как можно подготовить данные для нейросети или других эвристик.
Но, вернемся, непосредственно, к задаче. Мы знаем, как решить ее, если нам будет известно, какая точка какой фигуре принадлежит. В этом случае мы сможет посчитать ее центр масс, а значит, сможем, в последствии, перевести точки контура фигуры в полярные координаты. Зная координаты всех точек фигуры, мы можем без труда определить и координаты ее точек контура – достаточно посчитать количество соседей у точки. Если меньше 8 – значит, это точка контура.
Осталось определить, какая точка какой фигуре принадлежит. Существует множество методов, как это сделать. Самый простой, хотя и не самый оптимальный – учебный алгоритм рекурсивный заливки, который часто делают студенты на лабах по программированию. Кто умеет пользоваться гуглом, легко найдет его, объяснить подробно не будут, и так уже много букв и пора заканчивать статью. Но, при желании, можно найти и более оптимальные алгоритмы.
Итак, подытожим. Мы можем решить задачу по распознаванию фигур в идеальном случае, проделав следующие шаги:
1. Найти все белые точки и их принадлежность к отдельной фигуре.
2. Найти контру и цент масс каждой фигуры.
3. Посчитать контур в полярных координатах.
4. На развёртке (графике) контура фигура посчитать «всплески» (углы). Как мы знаем, у треугольника их три, у прямоугольника – четыре. Задача решена.
Литература
1. Р Гонсалес, Р. Вудс. Цифровая обработка изображений. Перевод с английского под редакцией П. А. Чочина, Техносфера, Москва, 2005, 1071 с.
