Распознавание изображений. Алгоритм Eigenface

    Введение



    Я продолжаю серию статей посвящённую тематике pattern recognition, computer vision и machine learning. Сегодня я вам представляю обзор алгоритма, который носит название eigenface.



    В основе алгоритма лежит использование фундаментальных статистических характеристик: средних (мат. ожидание) и ковариационной матрицы; использование метода главных компонент. Мы также коснёмся таких понятий линейной алгебры, как собственные значения (eigenvalues) и собственные вектора (eigenvectors) (wiki: ru, eng). И вдобавок, поработаем в многомерном пространстве.
    Как бы страшно всё это не звучало, данный алгоритм, пожалуй, является одним из самых простых рассмотренных мною, его реализация не превышает нескольких десятков строк, в тоже время он показывает неплохие результаты в ряде задач.


    Для меня eigenface интересен поскольку последние 1.5 года я занимаюсь разработкой, в том числе, статистических алгоритмов обработки различных массивов данных, где очень часто приходится иметь дело со всеми вышеописанными «штуками».

    Инструментарий



    По сложившейся, в рамках моего скромного опыта, методике, после обдумывания какого-либо алгоритма, но перед его реализацией на С/С++/С#/Python etc., необходимо быстро (насколько это возможно) создать математическую модель и опробовать её, что-нибудь посчитать. Это позволяет внести необходимые коррективы, исправить ошибки, обнаружить то, что не было учтено при размышлении над алгоритмом. Для этого всего я использую MathCAD. Преимущество MathCAD в том, что наряду с огромным количеством встроенных функций и процедур, в нём используется классическая математическая нотация. Грубо говоря, достаточно знать математику и уметь писать формулы.



    Краткое описание алгоритма



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

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


    Где Фi – центрированное (т.е. за вычетом среднего) i-ое изображение исходной выборки, wj представляют собой веса и uj собственные вектора (eigenvectors или, в рамках данного алгоритма, eigenfaces).



    На рисунке выше мы получаем исходное изображение взвешенным суммированием собственных векторов и прибавлением среднего. Т.е. имея w и u, мы можем восстановить любое исходное изображение.

    Обучающую выборку необходимо спроецировать в новое пространство (причём пространство, как правило, гораздо больше размерности, чем исходное 2х мерное изображение), где каждая размерность будет давать определённый вклад в общее представление. Метод главных компонент позволяет найти базис нового пространство таким образом, чтобы данные в нём располагались, в некотором смысле, оптимально. Чтобы понять, просто представьте, что в новом пространстве некоторые размерности (aka главные компоненты или собственные вектора или eigenfaces) будут «нести» больше общей информации, тогда как другие будут нести только специфичную информацию. Как правило, размерности более высокого порядка (отвечающие меньшим собственным значениям) несут гораздо меньше полезной (в нашем случае под полезной понимается нечто, что даёт обобщённое представление о всей выборке) информации, чем первые размерности, соответствующие наибольшим собственным значениям. Оставляя размерности только с полезной информацией, мы получаем пространство признаков, в котором каждое изображение исходной выборки представлено в обобщённом виде. В этом, очень упрощённо, и состоит идея алгоритма.
    Далее, имея на руках некоторое изображение, мы можем отобразить его на созданное заранее пространство и определить к какому изображению обучающей выборки наш пример расположен ближе всего. Если он находится на относительно большом расстоянии от всех данных, то это изображение с большое вероятностью вообще не принадлежит нашей базе.

    За более подробным описанием я советую обращаться к списку External links википедии.

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

    Создание модели



    Для составления обучающей выборки использовалась Olivetti Research Lab's (ORL) Face Database. Там имеются по 10 фотографий 40 различных людей:


    Для описания реализации алгоритма я буду вставлять сюда скриншоты с функциями и выражениями из MathCAD и комментировать их. Поехали.

    1.



    faceNums задаёт вектор номеров лиц, которые будут использоваться в обучении. varNums задаёт номер варианта (согласно описанию базы у нас 40 директорий в каждой по 10 файлов изображений одного и того же лица). Наша обучающая выборка состоит из 4х изображений.
    Далее мы вызываем функцию ReadData. В ней реализуется последовательное чтение данных и перевод изображения в вектор (функция TwoD2OneD):



    Таким образом на выходе имеем матрицу Г каждый столбец которой является «развёрнутым» в вектор изображением. Такой вектор можно рассматривать как точку в многомерном пространстве, где размерность определяется количеством пикселей. В нашем случае изображения размером 92х112 дают вектор из 10304 элементов или задают точку в 10304-мерном пространстве.



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



    Функция AverageImg считает и возвращает вектор средних. Если мы этот вектор «свернём» в изображение, то увидим «усреднённое лицо»:



    Функция Normalize вычитает вектор средних из каждого изображения и возвращает усреднённую выборку:



    3. Следующий шаг это вычисление собственных векторов (они же eigenfaces) u и весов w для каждого изображения в обучающей выборке. Другими словами, это переход в новое пространство.



    Вычисляем ковариационную матрицу, потом находим главные компоненты (они же собственные вектора) и считаем веса. Те, кто познакомятся с алгоритмом ближе, въедут в математику. Функция возвращает матрицу весов, собственные вектора и собственные значения. Это все необходимые для отображения в новое пространство данные. В нашем случае, мы работаем с 4х мерным пространством, по числу элементов в обучающей выборке, остальные 10304 — 4 = 10300 размерности вырождены, мы их не учитываем.

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



    Собственные значения на самом деле показывают дисперсию по каждой из осей главных компонент (каждой компоненте соответствует одна размерность в пространстве). Посмотрите на правое выражение, сумма данного вектора = 1, а каждый элемент показывает вклад в общую дисперсию данных. Мы видим, что 1 и 3 главные компоненты дают в сумме 0.82. Т.е. 1 и 3 размерности содержат 82% всей информации. 2ая размерность свёрнута, а 4ая несёт 18% информации и нам она не нужна.

    Распознавание



    Модель составлена. Будем тестировать.



    Мы создаём новую выборку из 24 элементов. Первые 4ре элемента те же, что и в обучающей выборке. Остальные это разные варианты изображений из обучающей выборки:



    Далее загружаем данные и передаём в процедуру Recognize. В ней каждое изображение усредняется, отображается в пространство главных компонент, находятся веса w. После того как вектор w известен необходимо определить к какому из существующих объектов он ближе всего расположен. Для этого используется функция dist (вместо классического евклидова расстояния в задачах распознавания образов лучше применять другую метрику: расстояние Махалонобиса). Находится минимальное расстояние и индекс объекта к которому данное изображение расположено ближе всего.

    На выборке из 24 показанных выше объектов эффективность классификатора 100%. Но есть один ньюанс. Если мы подадим на вход изображение, которого нет в исходной базе, то всё равно будет вычислен вектор w и найдено минимальное расстояние. Поэтому вводится критерий O, если минимальное расстояние < O значит изображение принадлежит к классу распознаваемых, если минимальное расстояние > O, то такого изображения в базе нет. Величина данного критерия выбирается эмпирически. Для данной модели я выбрал O = 2.2.

    Давайте составим выборку из лиц, которых нет в обучающей и посмотрим насколько эффективно классификатор отсеет ложные образцы.



    Из 24 образцов имеем 4 ложных срабатывания. Т.е. эффективность составила 83%.

    Заключение



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

    Например, у нас в качестве классификатора применяется простой distance classifier. Однако мы могли бы применить более совершенный алгоритм классификации, например Support Vector Machine (Метод Опорных Векторов) или нейросеть.

    В следующей статьей речь пойдёт о Support Vector Machine (Метод Опорных векторов). Относительно новый и очень интересный алгоритм, во многих задачах может быть использован как альтернатива НС.

    При написании статьи использовались материалы:
    onionesquereality.wordpress.com
    www.cognotics.com

    Материалы:
    Лист расчётов для MathCAD 14

    UPD:
    Я вижу многим непонятна и пугает математика. Тут есть два пути.
    1. Если вы хотите понять весь смысл всех действий алгоритма, то следует начать с понимания базовых вещей: ков. матрицы, метода главных компонент, значение и смысл собственных векторов и значений. Если вы знаете, что это, то всё становится понятно.
    2. Если вы хотите просто реализовать и использовать алгоритм, то берёте качаете лист расчётов для MathCAD'a. Запускаете, смотрите, меняете параметры. Там расчётов на пол экрана и в них нет ничего сложнее умножения матриц (ну если не считать встроенных функций вычисления собственных векторов, но в это вникать не надо). Вот в помощь реализации на python, matlab, C++.

    Поделиться публикацией
    Никаких подозрительных скриптов, только релевантные баннеры. Не релевантные? Пиши на: adv@tmtm.ru с темой «Полундра»

    Зачем оно вам?
    Реклама
    Комментарии 48
    • +42
      Космос.
      • –2
        Интересный пост, спасибо
        • 0
          А есть метОды распознавания образов по там допустим фурье-преобразованию пространственных частот в изображении?
          • +1
            В алгоритме JPEG используются подобные преобразования.

            Что касается распознавания, то данные алгоритм имеет какую-то аналогию с разложением сигнала в тригонометрический ряд. Сигнал представляется как сумма тригонометрических членов, а в нашем случае изображение как сумма базисных элементов.
          • +1
            спасибо, наконец-то встретил понятную статью, а то недавно писали про AdaBoost, сама идея там конечно ясна, но вот как сделать реализацию я так и не понял. а тут и реализация понятная и алгоритм.
            • +1
              Темой статьи был не AdaBoost, поэтому не стал подробно останавливаться. Там есть ссылки на литературу, я сам по ним разбирался.
            • +4
              Плюс за непонятность
              • +2
                Что именно непонятно? Я постараюсь объяснить.
                • 0
                  К несчастью, в универе я не слишком сильно дружил с матаном, поэтому непонятны некоторые детали реализации алгоритма, начиная с пункта 2. Вычисление вектора «средних» — непонятно, что делают 1 и 3 строчки.
                  Далее, в 3 пункте, непонятен механизм вычисления ковариационной матрицы (вики вынесла мозг обилием формул) и собственных векторов (функция eigenvecs()).
                  И еще несколько неясен механизм работы функции dist(). Как я понял, она получает два вектора и вычисляет нормализованную Евклидову дистанцию по формуле:. Я правильно понял?
                  • 0
                    UPD: Имелась в виду вот эта формула: upload.wikimedia.org/math/1/5/f/15ffbc92c56f218d863d04f1091beeb2.png
                    • 0
                      В статье об этом написано: вместо классического евклидова расстояния в задачах распознавания образов лучше применять другую метрику: расстояние Махалонобиса

                      • 0
                        Да, эта формула.
                      • +1
                        > Вычисление вектора «средних» — непонятно, что делают 1 и 3 строчки.

                        1 транспонирует матрицу. В 3ей строке берётся каждый столбец матрицы и вычисляется его среднее. Средние по столбцам и составляют вектор средних (усреднённое изображение).

                        > Далее, в 3 пункте, непонятен механизм вычисления ковариационной матрицы

                        Вобще ковариационная матрица должна вычисляться так:
                        C < — AT * A
                        Где AT — это транспонированная матрица А.
                        Но в этом случае получается матрица размером 10304х10304. Неподъёмный размер. Поэтому мы вычисляет только часть ковариционной матрицы (где количество строк и столбцов равно количеству примеров в обучающей выборке) по немного изменённой формуле:
                        C < — A * AT
                        Этот момент более подробно изложен в любом описании мат. аппарата алгоритма. На русском можно прочесть здесь: library.mephi.ru/data/scientific-sessions/2003/Neuro_2/115.pdf

                        • 0
                          Извиняюсь, формулы для вычисления ков. матрицы перепутал, там наоборот. :) Пишу в дороге с наладонника, неудобно.
                          • 0
                            Спасибо большое, так стало понятнее.
                  • +1
                    Матан =)
                    • +6
                      я бы хотел это понять
                      • +3
                        блин надо было учить математику усерднее
                        • 0
                          Применим ли данный алгоритм для распознавание обьектов, например дигитальных фотоаппаратов? Допустим задача: Есть база с ~300 изображениями (в хорошом качестве / размере) разных д. ф/а. Поступает изображение ф/а который может находиться в базе, а может и нет. Изображение не всегда под тем же углом что и изображение в базе. Стоит отметить, что часто разные ф/а одного производителя похожи друг на друга.

                          Есть ли алгоритмы кототрые более подходят для такой задачи?
                          • 0
                            Если человек глядя на эти фотографии не может отличить какие-нибудь два фотоаппарата, то компьютер точно не сможет.
                            Если только не написать алгоритм классификации фотоаппаратов :)
                          • 0
                            приятно таким заниматься в студенческие годы или в аспирантуре… я бы хотел чтобы мне платили за работу над такими вещами, тогда я вспомнил бы математику и перечитал бы кнута…
                            • +14
                              Хабр тот.
                              • +1
                                После формулы думал, что дальше пойдут нейронные сети. Рад, что ошибся. Понравилась идея с вычитанием среднего.
                                • +1
                                  Я взялся писать эти статьи как раз для того, чтобы показать людям, что в распознавание образов это не только нейросети. :)
                                  • 0
                                    А вообще, как по-вашему, что какое средство эффективнее в распознавании образов: нейросети или какие-то другие алгоритмы?
                                    • 0
                                      Не знаю, я не эксперт в этой области. Единственное, что мне понятно — это то, что эффективнная система для распознавания это комплекс различных алгоритмов. Искусственная нейросеть это далеко не человеческий мозг, поэтому далеко не панацея и чудес не делает.
                                • +3
                                  Действительно очень сильная статья, читал 2 раза вспоминая, что учил на вышке. Вспоминается сложно, но вспоминается, хочется еще подобных статей и побольше, заставляет напрягаться мой мосг :)
                                  • +1
                                    Хм, я бы попробовал получить веса для обучающей выборки, а потом усреднять.

                                    И почему только 4 веса? Имхо надо обрезать по дисперсии.

                                    Я и провильно понимаю что собственные значения нормализовывались только по 4-м значениям? Тогда проценты — всего лишь от вклада этих 4-х. Для оценки эффективности имеет смысл нормализовать по всем исходным размерностям.
                                    • 0
                                      Если не усредняя применять PCA, то области данных изображений в многомерном пространстве будут иметь большую плотность и, возможно, перекрываться.

                                      Максимальное количество весов не превышает размер ков. матрицы по одному из измерений. Т.е. равно объёму выборки.

                                      Это не имеет смысла т.к. все остальные размерности вырождены.
                                    • +3
                                      А хабр-то, ещё торт!
                                      • –3
                                        А есть реализация на .NET?
                                        • 0
                                          Поправьте, пожалуйста, если я что-то упустил: алгоритм Eigenface сводится к
                                          1) уменьшению размерности выборки посредством метода главных компонент (PCA)
                                          2) классификации полученных данных методом ближайшего соседа (Nearest Neighbour).
                                          Так?
                                          • 0
                                            на сколько я понял, как раз да
                                            • +1
                                              нет не так…

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

                                              иными словами аглоритм фишера (или собс. лиц) это на шаг глубже чем РСА
                                              • +2
                                                после нахождения этого пространства — проектируется в него(!)
                                                • +1
                                                  Безусловно, метод Фишера, или линейный дискриминантный анализ (LDA), отличается от PCA (хотя у них и много общего).
                                                  Однако сдаётся мне, Вы говорите о некоей вариации оригинального алгоритма, потому что в нём LDA не использовался, т.е. все лица обучающей выборки обрабатывались без учёта других классов (как и в данном топике).
                                                • 0
                                                  Ну если рассуждать тезисно, то можно и так сказать.
                                                • –3
                                                  Всё понято, только этот ужасный маткад портит всю статью, юзай мэпл или матлаб в крайнем случае. Повторяю, маткад — ужасен. А статья интересная, даже очень.
                                                  • 0
                                                    Да вы просто не поняли прелестей маткада! =)
                                                    Математические формулы «придуманы» как раз чтобы однозначно лаконично сформулировать то, что порой в пару абзацев =)))
                                                    • –2
                                                      Для этого есть Mathematica. А MathCAD все равно ужасен.
                                                  • +1
                                                    УРА! ) в этом году сдавал диплом по этой теме)) налюбился достаточно… но распознает

                                                    в частности интересно что будет если скрестить алгоритм Фишера + нейронные сети
                                                    • 0
                                                      P.N. Belhumeur, J.P. Hespanha, D.J. Kriegman, Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection
                                                    • +2
                                                      Приличная статья по CV на наших Хабрах после продолжительного уныния? Есть путь!
                                                      • 0
                                                        Indalo спасибо за отличную статью…
                                                        • 0
                                                          А я думал матан хорош только в использовании как карательная мера.
                                                          • 0
                                                            Отличная статья, не часто встретишь хорошую статью на русском по CV
                                                            • 0
                                                              В плане развития мат.аппарата у нас специальность близка к «Прикладной математике», так что все такое знакомое:) Плюс не так давно писал простую программу распознавания символов.
                                                              Кстати, статья получилась наглядная и интересная, спасибо.

                                                              Заинтересовал момент с вычислением главных компонент, удобно.
                                                              • 0
                                                                Хорошая статья, спасибо. От себя добавлю ссылку на статью Юрия Чеснокова (eng) с реализацией аналогичного алгоритма на С++

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