Алгоритм распознавания образов обучающийся с одного раза (One-Shot learning) +35

Введение


Я хочу представить вам результат своих экспериментов с алгоритмами распознавания образов с обучением с первого раза (так называемый One-Shot Learning). В результате экспериментов выработались определённые подходы к структуризации изображения и в итоге они воплотились в несколько взаимосвязанных алгоритмов и тестовое приложение на Android, которым можно проверить качество и работоспособность алгоритмов.


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


Почему не нейросети?


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


Приведу несколько причин против нейросетей:


  1. Требуются большие датасеты для обучения, которых может просто не быть в распоряжении
  2. Большие мощности для обучения и большое время обучения каждой картинке
  3. Непрозрачность алгоритма, невозможность отладки и прямого влияния на результат. Очень сложно если не сказать невозможно понять логику распределения весов. Это и сила и слабость.

Как это устроено


Основная идея такая: изображение- образец должно быть структурировано, т.е. информация в нем должна быть уменьшена до необходимого минимума, но так чтобы не терялся смысл. Например художники рисуют скетчи – всего в несколько точных линий художник может изобразить лицо человека или какой то предмет и зрителю будет понятно что изображено. Фотография содержит матрицу N*M пикселей каждый пиксель содержит сколько то бит информации о цвете, а если представить это все в виде параметров линий то объем информации резко уменьшается и обработка такой информации гораздо проще. Примерно тоже самое должен делать алгоритм. Он должен выделить главные детали в кадре – то что несет в себе основную информацию и отбросить все лишнее.



Алгоритм находит структуру векторов по границам объектов в образце и такую же структуру в распознаваемом изображении.



Для того чтобы получить вектора изображение проходит несколько стадий обработки:


  • Переводится в монохром по простой формуле (Red+Green+Blue)/3
  • Вычисляется градиент для каждой точки матрицы
  • Находятся наиболее значимые в весовом отношении области градиента
  • Ищутся цепочки векторов, покрывающих эти области
  • Далее происходит зацикливание шагов для получения в итоге минимального количества векторов несущих в себе максимум информации.


В анализируемом алгоритме происходит тоже самое. Далее полученные массивы векторов сравниваются:


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

Таким образом маленькие детальки входят в общую картину и происходит лавинообразное распознавание образа.
Сама классификация построена по принципу поиска наиболее похожего изображения из хранимых. Наиболее похожее – это имеющее наибольшее количество совпадающих векторов с наименьшими отклонениями по отношению к общему объему векторов в образце.


Общая схема работы алгоритмов:



Обучение в несколько этапов


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


Таким образом если вектор входим в состав кластера котрый найден в сохраненном образце и в анализируемом то он получает +1 балл, а если нет то ничего не получит. Спустя несколкьо обучений вектора которые набрали мало баллов удаляются из сохраненного образца и более не используются для анализа.


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


Для чего может применяться


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


Работа тестового приложения



Приложение работает с матрицей 100*100 пикселей, преобразует картинку к монохромной матрице такого размера. Алгоритму не важно под каким углом находится образец и его размеры в некоторых пределах тоже.


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


Можно сохранить несколько образцов. И показывая новое изображение алгоритм найдет наиболее подходящее из них и покажет похожие части.

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (25):

  1. BelerafonL
    /#18787445

    Это похоже на хорошо известное «классическое» компьютерное зрение — гистограмму направленных градиентов, что на пальцах объяснено, скажем, тут youtu.be/riLQCudri7Q?t=46m43s

    Кроме того, нейросети вполне себе демонстрируют One-Shot learning за счет transfer learning (гуглится множество статей).

    • truggvy
      /#18787887

      Ну не стоит так сразу отказывать автору в новаторстве. Вот лично я раньше не встречал примеров использования векторизации для классификации изображений. Упомянутый вами HOG это, всё-таки, не тоже самое, что векторное представление.
      Насколько я понимаю, что бы получить «One-Shot learning за счет transfer learning», вам для начала потребуется подходящая предобученная «родительская» сеть (и большой мешок удачи :). А в данном случае вроде бы не требуется никаких сторонних классификаторов.

      • ProLimit
        /#18788565

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

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

        Сильная идея — это кластеры, т.е. использование фрактального разбиения. Жаль что нет подробностей. И еще нет подробностей, как устраняются инвариантность к базовым преобразованиям картинки: вращениям (в том числе взаимным между кластерами), масштабу, взаимному расстоянию, параллаксу и т.д. Тут нейросети хорошо справляются, но и чисто математические решения, думаю, есть.

    • dv1555
      /#18788603

      Чем то похоже но суть совсем не та. Я не делю изображение на ячейки и не привязываюсь к размеру блока, соответственно нормализация потом идет по другому. Потом, насколько я понимаю этот алгоритм привязан к конкретному положению объекта, т.е. если его развернуть то ничего не получиться? У меня не привязано. К сожалению мне не разрешили опубликовать ссылку на приложение в маркете без этого статья не интересна.

      • BelerafonL
        /#18788637

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

        • dv1555
          /#18788685 / -1

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

      • BelBES
        /#18791013

        Потом, насколько я понимаю этот алгоритм привязан к конкретному положению объекта, т.е. если его развернуть то ничего не получиться?

        Что мешает нормализовать по направлению, как это делают в SIFT, и получить rotated invariant дескриптор региона?

  2. Leoon
    /#18787701

    Идея хорошая, как альтернатива. Один нюанс, на RGB, если разложить на 3 картинки, в каких то случаях соотношения цвета и теней могут быть разные линии, например (могу с цветом ошибаться) на B (из RGB) самая темная картинка из оттенков кожи, т.е. при сильном освещении в области пересвета будет очень четкая картинка в синем спектре.
    Это я о том, что если усложнить алгоритм в 3 раза т.е. делать это все в 3х цветах отдельно, то эффективность при разном освещении разных оттенков цвета вырастет. А далее можно прикрутить комбинирование, замену.

    • truggvy
      /#18787835

      Есть более простое решение: получить градиенты по всем 3-м каналам и взять максимум для каждой точки.

      • Leoon
        /#18787857

        Ну я что такое и имел виду, просто описал сложно. Имелось виду, что использовать все 3 канала вместо серого, который получается при разном освещении разный при (Red+Green+Blue)/3.

  3. Arseny_Info
    /#18788529 / +1

    Для перевода в черно-белый лучше не усреднять каналы, а использовать формулу
    Gray = (Red * 0.299 + Green * 0.587 + Blue * 0.114).

  4. skipidar
    /#18789097 / +1

    А можно на код приложения взглянуть?

    • dv1555
      /#18789433 / -1

      К сожалению нет. Код большой и находится в состоянии перманентной оптимизации и экспериментов. Поэтому плохо читаем

      • Sdima1357
        /#18789713

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

  5. Hedgehogues
    /#18790683

    Автор преподносит свою придумку как нечто совершенно новое. Но есть же SIFT, ORB и другие дескрипторы, которые запечательно делают one-shot-learning путём использования мешка слов и запихивания их в какой-нибудь чёрный ящик типо SVM или случайных лесов (возможно, вместе с PCA или любым аналогом, если того хочется). Чем Ваше решение существенно отличается от указанных методов?

    • Hedgehogues
      /#18790699

      Кстати говоря, вот и они. https://habr.com/post/414459/


      Совершенно случайно был опубликован пост ровно про то, что я сейчас говорил. Практически в один момент с Вами

      • dv1555
        /#18796579

        Прочитал про эти методы, но там же поиск «особых точек», а у меня совершенно не так. У меня все точки одинаково «особые» и покрываются векторами, причем количество векторов стремиться к минимуму. Ну в в принципе можно сказать что у меня «поиск особых векторов». Примерно это можно сформулировать так: вот вам коробок спичек, расположите минимальное количество спичек так чтобы читались основные контуры рисунка и было понятно что нарсовано

        • Sdima1357
          /#18796699

          Почитайте про Radon Transform.( ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A0%D0%B0%D0%B4%D0%BE%D0%BD%D0%B0 )
          Можно использовать более экономный Hough Transform ( ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A5%D0%B0%D1%84%D0%B0 )
          Ваш алгоритм в его первой части реализуется поиском локальных максимумов в пространстве «радона». А вторую часть Вы стесняетесь описывать. Изобретение велосипедов конечно интересное занятие, но не мешает познакомиться с известными алгоритмами обработки изображений.

          • dv1555
            /#18797229

            можно искать прямые алгоритмом Хафа, да. Есть и другие методы. И что? Я знаю что есть множество разных методов, фрейморки и библиотеки типа OpenCV в которых они реализованы. Написать код который проводит линии по градиенту быстрее чем статью в википедии про этот алгоритм. Если бы я сделал только это я бы назвал статью так: «Алгоритм который ищет линии в изображении». Но есть одна проблема — в изображении можно вписать очень много линий и это не имеет смысла — просто вместо точек появится много линий.

            • Sdima1357
              /#18797967

              Еще раз. Есть набор стандартных тестов в OpenCV. Покажите как Ваш код с ними справляется.

              • dv1555
                /#18798091

                Вот ссылка на приложение можно скачать и потестить сколько нужно: play.google.com/store/apps/details?id=ru.travelfood.bitmaps

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

                • Sdima1357
                  /#18798479

                  Оно работает как мне надо

                  Да пожалуйста, вопрос нужно это кому нибудь еще кроме Вас :)
                  Я утверждаю, что на любых картинках из стандартных тестов Ваш алгоритм работать не будет. От слова «совсем».

        • Hedgehogues
          /#18800419

          Могли бы Вы описать алгоритм подробнее? Или дать ссыли на код? Ваше описание очень общее и из него сложно понять, что, действительно, Вы сделали.

          • dv1555
            /#18801167

            Да. Комментарий про алгоритм Хафа, дал мне понять что имеет смысл описать алгоритм подробнее. Я сделаю несколько отдельных постов с ссылкой на этот пост про каждый алгоритм который я использовал: отдельно про выделение главных градиентов, отдельно про расположение векторов и про то как я анализирую связи между векторами