Компания
55,89
рейтинг
16 декабря 2013 в 11:48

Разработка → Классификатор изображений

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

Эта простая с первого взгляда задача встретилась мне на вступительном экзамене в DM Labs.
На первом занятии мы обсудили решение, а преподаватель (Александр Шлемов; он руководил и дальнейшей реализацией) показал, почему для решения лучше использовать машинное обучение.

В процессе дискуссии мы обнаружили, что наше решение производится в два этапа. Первый этап — фильтрация помех, второй этап — вычисление метрики, по которой будет проходить классификация. Здесь возникает проблема определения границ: необходимо знать, какие значения может принимать метрика для каждой фигуры. Можно проложить эти границы вручную “на глазок”, но лучше поручить это дело математически обоснованному алгоритму.
Эта учебная задачка стала для меня введением в Machine Learning, и я хотел бы поделиться с вами этим опытом.

Основная идея


Сначала мы создаем множество случайных изображений кругов, треугольников и четырехугольников. Далее пропускаем картинки через фильтры для ликвидации помех и вычисляем набор метрик, которые будут использованы для классификации фигур. Граничные значения для метрик определим с помощью дерева решений (Decision tree), а точнее с помощью его разновидности CART (подробнее можно прочитать тут). Реализация алгоритма проста и лучше интерпретируется в терминах границ.
Пропустив неизвестное изображение через фильтры и вычислив метрики, по дереву решений мы сможем сказать, к какому классу относится фигура на картинке.

Генерация


Генератор должен не только создавать картинки, но и уметь накладывать помехи на них. При генерации мы должны отбрасывать фигуры с сторонами меньше некой величины (например, 15 пикселей) и с тупыми углами (больше 150 градусов) — даже человеку сложно их классифицировать.
Скрипт заботливо предоставил Виктор Евстратов.
bitbucket.org/rampeer/image-classifier/src/HEAD/picture_generator.py

Фильтры


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

Медианный фильтр: для каждого черного пикселя определяем количество «черных» соседей в окрестности радиуса R. Если это число меньше некого T, то отбрасываем этот пиксель, то есть закрашиваем его в белый цвет. В «оригинальном» медианном фильтре мы отбрасываем пиксель, если у него меньше половины черных соседей, а мы определили свой порог T, так что, на самом деле — это квантильный фильтр.



Я написал медианный фильтр честно и «в лоб», поэтому он работает за O(WHR2), где W и H – размеры картинки. Преподаватель рассказал, что можно ускорить алгоритм, используя преобразование Фурье. Действительно, медианный фильтр можно выразить через свертку, а свертку можно быстро вычислить с помощью быстрого преобразования Фурье.
Получается, что вычислить матрицу с количеством соседей можно как
result = FFT-1 (FFT(data) FFT(window))
Этот алгоритм работает за O(WHlog(W+H)), то есть намного быстрее наивной реализации, и не зависит от размеров окна. Из-за цикличности свертки возникает артефакт на границах: при обработке крайних левых пикселей соседями будут считаться крайние правые. Это можно исправить, добавив рамку из чистых пикселей по краям изображения, а можно оставить так, что я и сделал — всё равно этот эффект не наносит ущерба работоспособности.
bitbucket.org/rampeer/image-classifier/src/HEAD/filter_median.py
Однако, я обнаружил у этого фильтра нехорошее свойство: он скругляет острые углы треугольников. Из-за этого приходится брать радиус окна R довольно маленьким и проходиться по изображению фильтром только несколько (N) раз. Хотя поначалу казалось, что можно применять медианный фильтр до тех пор, пока он удаляет какие-то пиксели.

Бикомпонентный фильтр: берем произвольный черный пиксель, назначаем ему какое-то число Q. Назначаем это же число «черным» соседям этого пикселя в окрестности с радиусом R и повторим для соседей соседей. Будем повторять до тех пор, пока не дойдем до границы изображения (это напоминает действие инструмента «Заливка» в Paint, а красим в цвет Q). Затем увеличим число Q на единицу, выберем очередной «неокрашенный» пиксель и повторим процесс.
После выполнения этого алгоритма получится набор несоприкасающихся островов. Мы можем с высокой достоверностью сказать, что самый большой остров – это и есть фигура, а остальные острова – помехи.


<filter_bicomp.py>
В отличие от предыдущего, этот фильтр не портит изображение. Он может нанести ущерб, только если фигуру пересечет линия из помех шириной больше T, что маловероятно.
У медианного фильтра я обнаружил ещё одно свойство, на этот раз положительное. Он разбивает пространство, заполненное помехами, на “островки”. Значит, применив потом бикомпонентный фильтр, мы получим контур с прилепившимися помехами. После обработки бикомпонентным фильтром стоит ещё раз пройтись медианным, чтобы убрать оставшиеся неровности. Затем нужно построить вокруг оставшихся точек выпуклый контур, заполнить его и вычислять метрики уже для нового изображения.
bitbucket.org/rampeer/image-classifier/src/HEAD/process.py
Работа фильтров:
Исходное изображение Медианный фильтр Медианный, бикомпонентный Медианный, бикомпонентный,
медианный, заливка

Параметры фильтров подбираются исходя из размеров изображений в выборке и их зашумленности. Для хитрого четырехугольника, изображенного выше:
    median.filter(img, 2, 6, 1)
    bicomp.filter(img, 2)
    median.filter(img, 2, 5, 2)

В нашей выборке изображения будут менее зашумлены, и настройки будут более щадящие.

Метрики


В ходе всё той же дискуссии с коллегами мы придумали еще много разных интересных метрик.

Подсчет углов. Это самое первое, что приходит в голову после прочтения задачи. Но из-за помех могут появиться дополнительные углы, близкие к 0 градусам. Я безуспешно пытался бороться с этим, «склеивая» почти коллинеарные вектора и устанавливая пороги. Такие методы тяжело настроить, и они все равно могут дать некорректный результат, так как при фильтрации фигурка сглаживается. Лучше просуммировать квадраты синусов углов, а если углы больше некого порога T – округлять квадрат вверх до единицы. Это дает достаточно хороший результат: острые углы прибавляют к счетчику единичку, а углы, близкие к 0, почти ничего не прибавляют. Кстати, мне показалось забавным, что в таком случае количество углов у треугольника может варьироваться от 2,5 до 4.

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_edges.py

Зеркалирование. Смысл этой метрики – посчитать, насколько фигура будет совпадать с перевернутой копией себя при отражении по горизонтали/вертикали/вдоль обоих осей. То есть эта метрика — своеобразная мера симметрии. Круг, как ни крути, всегда будет полностью совпадать сам с собой. Также, я интуитивно предположил, что квадрат будет больше совпадать сам с собой, чем треугольник.

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_mirror.py

Отношение площади к квадрату периметра. Периметр необходимо возводить в квадрат, чтобы метрика не имела размерности и не зависела от размера изображения. Периметр и площадь будем брать от выпуклого контура. Круг имеет наибольшее значение метрики среди фигур: s/p^2 =(πr^2)/(4π^2 r^2 )=1/4π. Для равностороннего треугольника (у него это соотношение самое большое среди треугольников): s/p^2 =(4√3 a^2)/(3*9a^2 )=(4√3)/27. Для квадрата: s/p^2 =(a^2)/(16*a^2 )=1/16.

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_perimeter.py

Метрики на описывающем прямоугольнике. Предыдущие метрики не очень хорошо разделяли четырех- и треугольник, и я решил придумать новую метрику. Построим ограничивающий прямоугольник вокруг фигуры. Для каждой стороны прямоугольника найдем первое (“минимальное”) и последнее (“максимальное”) пересечение с фигурой. У нас получится “восьмиугольник”, для которого можно вычислять разные метрики.

Например, отношение площади фигуры к площади описывающего квадрата (sbound).
bitbucket.org/rampeer/image-classifier/src/HEAD/feature_sbound.py
Также многообещающей метрикой кажется отношение площади фигуры к площади этого восьмиугольника (sbound2):
bitbucket.org/rampeer/image-classifier/src/HEAD/feature_sbound2.py

Сбор данных


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

Этим случаям я дал большой вес при построении дерева. Дело в том, что вероятность случайной генерации таких картинок мала, а эти случаи являются граничными для некоторых метрик. Следовательно, для корректной классификации надо их добавить в выборку с большим весом.
Процедуру фильтрации изображения и сбора метрик я вынес в отдельный файл, она понадобится для анализа. Кстати, в дереве решений наши метрики называются “входными параметрами” или “фичами” (feature).
bitbucket.org/rampeer/image-classifier/src/HEAD/process.py
bitbucket.org/rampeer/image-classifier/src/HEAD/stats.py
Затем я построил график, чтобы убедиться, что метрики достаточно хорошо различают фигурки. Для этого подойдет график типа “коробки с усиками”:

“Усики” пересекаются, а это означает, что возможны неточности при анализе. Как было написано выше, именно для точности нам нужны несколько метрик, а не одна. Дальше я попробовал убедиться, что «плохие случаи» метрик не пересекаются. Для этого я построил зависимость одной метрики от другой. Если получится, что они монотонно зависят друг от друга, то их “плохие случаи” также совпадут.

*Как мы видим по графикам, “облака” точек сильно пересекаются. Следовательно, при классификации возможна большая ошибка. К тому же, метрики не зависимы монотонно друг от друга.

Анализ


По собранным данным можно построить дерево решений:
bitbucket.org/rampeer/image-classifier/src/HEAD/analyze.py
Я попробовал визуализировать дерево. Получилось вот такая схема:

Из неё следует, что некоторые метрики остались неиспользованными. Мы не могли с самого начала предсказать, какие метрики окажутся “лучше” других.
Точность предсказания составляет примерно 91 процент, что неплохо, учитывая искажения квадратов и помехи в выборке:



Попробуем нарисовать изображения самостоятельно и проанализировать их:

Circle

Rectangle

Triangle

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

Rectangle

Rectangle

Triangle

Rectangle

Вот и всё.
В последнем изображении углы треугольника сильно скруглены, edges не может верно работать, а perimeter дает слишком большую погрешность. Треугольник неудачно повернут: при построении ограничивающего прямоугольника только две вершины будут его касаться, и sbound и sbound2 не выдадут ничего разумного. Только mirror мог бы выдать корректный результат, но он не включен в дерево. Да и если из 5 метрик только одна укажет на треугольник, то можно трактовать этот вывод как ошибочный.

Вывод


Методы машинного обучения позволили построить систему, которая хорошо справляется с поставленной задачей – она достаточно хорошо распознает фигурки на изображении.
Графики были построены в R:
bitbucket.org/rampeer/image-classifier/src/HEAD/charts.R
Автор: @dmstudent
DM Labs
рейтинг 55,89
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Комментарии (28)

  • +5
    А почему для классификации не используется контурный анализ?
    habrahabr.ru/post/118486/
    По-моему он лучше, чем представленные метрики должен работать.
    • 0
      Да, и ещё два вопроса вдогонку.
      Первый: а при обучении по выборке пробовали применять разные алгоритмы? В принципе, как мне подсказывает опыт, иногда лучше SVM, иногда adaboost, а иногда ещё что-то вроде нейросетей. Часто за счёт правильного метода можно эффективность поднять на десятки процентов.

      Второй: Всегда любопытно, когда натыкаешься на какую-нибудь компанию, занимающуюся обработкой изображений или машинным обучением в России. Тут мало кто этими тематиками занимается. Вашу компанию вижу в первый раз, к тому же у вас это похоже у вас первый пост на Хабре. Будут какие-нибудь посты о деятельности компании и тех задачах, что она решает?
      • 0
        Еще хотелось бы порекомендовать попробовать RBM (и DBM, соответственно).
        • 0
          DBM?
          Вы имеете в виду Deep Belief Network, или это чтото новое, также на основе RBM?

          Да, почему бы и нет. Можно копать еще глубже :) К примеру, во всякие deep NCA, говорят они клевые.
          • 0
            Я всегда называл его Deep Boltzmann Machine, но, вроде, это то же самое
        • 0
          Я так понимаю, что DBN предполагается использовать на последнем этапе — для изучения форм по очищенным от шума изображениям? Т.е. входными образцами должны быть просто наборы пикселей, составляющие фигуру? Или вы подразумевали что-то другое?
          • 0
            Да, в конце
    • +1
      Приветствуем. Мы начали нашу деятельность относительно недавно, тем более на Хабре. В ближайшее время планируется вывесить статью о нашей деятельности — чем мы занимаемся помимо обучения студентов. Всегда рады поделиться с общественностью клевыми интересными штуками и продвигать машинное обучение в массы.

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

      Например, как вы заметили, в реальных приложениях можно использовать контурный анализ, или как намекают в комментарии ниже RBM\deep learning. Или еще чтонибудь вроде признаков Хаара и разного рода сверток, но никак не отношение площади к квадрату периметра.

      Насчет других методов — действительно есть смысл поиграться с ними. Хотя, с одной стороны, по графикам видно что на имеющихся признаках 100%-ая точность не достижима. С другой, решающее дерево наглядно для интерпретации.

      Представьте — вас спросят «как отличить квадрат от треугольника?». А вы скажете — «о, все просто — отношение площади к периметру должно быть меньше 0.06». Это прикольнее чем svm, хоть, в данном случае(!), и чуть менее точно :)
    • +8
      Контурный анализ


      • 0
        Ухты, круто!

        Интересно, иконка замочка ему понравилась, а аватарка нет. Это в OpenCV, верно?
        • 0
          У автарки буква b сильно подпортила контур и оно посчитало что это уже не квадрат )

          Это в OpenCV, верно?
          Да, контуры ищутся с помощью OpenCV
  • 0
    а преподаватель (Александр Шлемов; он также руководил дальнейшей реализацией) показал, почему для решения лучше использовать машинное обучение.

    А нам расскажете, почему всё-таки лучше? Из статьи это совсем не следует… Напротив, по моему именно эта задача в конкретной формулировке красивше решается через вычисление характеристик контуров(хотя-бы посчитать центральные или хью моменты)… А ML тут — это как из пушки по воробьям стрелять…
    • 0
      Полагаю что потому что было несколько метрик и ни одна из них не давала хорошей классификации сама по себе

      Тут возникает проблема нахождения границ: необходимо знать, какие значения метрики могут получаться для каждой из фигур. Можно проложить эти границы вручную “на глазок”, но лучше поручить это дело математически обоснованному алгоритму.
      • 0
        Да, вы верно заметили. А также, идея была в том чтобы построить на основе таких признаков чтото простое — дерево решений или логистическую регрессию.

        Это не то, чтобы из пушки по воробьям (хотя если бы речь шла про GBM 1, 2, это было бы правдой), но и не совсем тривиальный подход.

        Плюс, для первичного ознакомления с машинным обучением, Хью моменты и вейвлет-анализ могут быть слишком хардкорны :)
      • 0
        Как-то лихо они сделали такой вывод: взяли несколько плохих метрик, получили ожидаемо плохой результат и тут-же сделали вывод, что ML — спасение человечества)
        • 0
          А сейчас в обработке изображений у многих бытует мнение, что любая задачка сводиться к правильному обучению классификатора:)
          Никто не учитывает, что есть и другие варианты решения проблем:)
          • 0
            Скорей всего эти люди не замниаются продуктизацией такого кода) Когда резко оказывается, что для промышленного применения такой «вроде здорово натренированный» классификатор не подхдоит в связи с плохой точностью:)
            • 0
              Вот, вот в этом и было ключевое недопонимание. Ни о какой продуктизации здесь речи не шло:
              Таким образом эта учебная задачка стала для меня введением в Machine Learning, и я хотел бы поделиться с вами этим опытом.


              Конечно же, для промышленного применения, как неоднократно писали выше, уже есть свои, куда более совершенные инструменты. А также есть готовые коробки, как показанный выше OpenCV — их достаешь и не думаешь о том, кто и как тренировал ее содержимое.
        • 0
          Это конечно клево, что ML ассоциируется со спасением человечества (не надо злить skynet), но таких далеких выводов пока не делалось :) В рамках этого поста, по-крайней мере.

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

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

          А после того как студент справится с заданием, то вытащить тех же вейвлет фич и вместо одного дерева решений обучить тысячу штук — дело техники.
          • 0
            Без обид, но мне ваше решение видится так: давайте возьмем кучу плохих фич, выбирать из них хорошие не будем, ведь заниматься анализом предметной области — это так сложно и скучно, затем возьмем какойнибудь крутой метод машинного обучения и стравим ему получившееся у нас дескрипторы, что-то даже местами отработало(ибо задача достаточно простая, и ML метод кое как справился с убогими фичами) и пофигу что мисматчи вылезли даже на достаточно хороших данных… Вот как-то так. Может я чего-то не понимаю, но хоть с точки зрения компьютерного зренияЮ хоть с точки зрения ML вы показали в статье то, как не надо делать при решении задачи. Если цель была сделать введение в ML, то непонятно где пропал этап feature selection… кучу метрик вы взяли, но их качество не оценили, а на сложных данных это грозит эпичным фэйлом. Если это было введение в компьютерное зрение, то вы опять не «изучили» предметную область… нет никакого анализа качества фич, и попыток решиьт задачу при помощи методов компьютерного зрения… Как-то так…
            • –1
              То что вы говорите это все верно, применительно к настоящим и «сложным» данным, но есть большое но. Вы слишком серьезно подошли именно к учебной задаче, которая не претендовала на чтото серьезное и «настоящее» в производственном плане (прямо в abstract'е к посту). Этот пост был написан учеником о его собственном опыте — первый его подход к снаряду.

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

              Так как критериев больше одного, их можно было как раз использовать в рамках ML, чтобы слепить один большой критерий, без специальных инструментов (надо будет дисклеймер писать в следующий раз). К слову, feature selection как раз был в рамках построения дерева. Но так как в этой статье «куча» метрик перечислима по пальцам одной руки, этот вопрос можно умышленно умолчать :)
  • 0
    На хабре есть блог, ну или теперь уже тег «Обработка изображений», было бы здорово, если бы вы его добавили.
    • 0
      Спасибо за идею, добавили еще пару тегов =)
  • 0
    Кстати, на тимусе есть задачка с ровно таким же условием, так что если кто-то хочет проверить на скорую руку набросанное решение — он может сделать это в системе автоматической проверки: http://acm.timus.ru/problem.aspx?space=1&num=1378
    • 0
      Да, условия задачи почти такие же, только на изображения надо ещё помехи нанести, так она становится интереснее.
      Недавно мы еще решали задачу с распознаванием цифр на kaggle, если кому-то интересно могу скинуть свое решение =)
    • 0
      До чего техника дошла… Мы в одиннадцатом классе просто считали расстояние от центра масс до самой близкой и самой удаленной точки на границе, а потом смотрели на их отношение. Если близко к 1, то круг. Если в районе корня из двух, то квадрат. Если больше, то треугольник. И ничего, AC.
  • 0
    Для фигур, генерируемых bitbucket.org/rampeer/image-classifier/src/HEAD/picture_generator.py, вполне работает такая простая метрика: описываем вокруг фигуры окружность с центром в центре масс фигуры и с радиусом, равным расстоянию от центра масс фигуры до ее наиболее удаленной точки. Далее считаем отношение площади такой окружности к площади самой фигуры.
    Вот что получаем: image
    Код:

  • 0
    Собственно, код:
    https://github.com/atolmachev/figure-classifier/blob/master/metrics.py
    https://github.com/atolmachev/figure-classifier/blob/master/test.py
    Выборка собрана по картинкам размера 30, 60 и 90, по 100 изображений на каждый тип в каждой категории.

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

Самое читаемое Разработка