В моём предыдущем топике я старался показать, как метод Viola Jones работает, с помощью каких технологий и внутренних алгоритмов. В данном посте, дабы не прерывать цепочку, будет также много теории, будет показано за счет чего можно улучшить и до того прекрасный метод. Если здесь описать еще и программную реализацию, то будет огромное полотно, которое читать будет очень неудобно, и смотреться это никак не будет — решено разбить объем информации на два отдельных поста. Ниже — теория, мало картинок, но много полезного.
Человек даже не замечает, как он просто справляется с задачами обнаружения лиц и эмоций при помощи своего зрения. Когда глаз смотрит на окружающие лица людей, предметы, природу, подсознательно не чувствуется, какой объем работы проделывает мозг, чтобы обработать весь поток визуальной информации. Человеку не составит труда найти знакомого человека на фотографии, или отличить ехидную гримассу от улыбки.
Человек пытается воссоздать и построить компьютерную систему обнаружения лиц и эмоций — ему это отчасти удается, но каждый раз приходится сталкиваться с большими проблемами при распознавании. Компьютеры в наше время беспрепятственно могут хранить огромные объемы информации, картинки, видео- и аудио файлы. Но отыскать вычислительным системам с такой же легкостью, к примеру, нужную фотографию с определенной эмоцией нужного человека из собственной личной фотогалереи — сложная задача. Решению такой задачи мешают некоторые факторы:
Список можно продолжать еще долго. Но внимание заострено на самых важных моментах, поэтому перечислять все мешающие параметры нет смысла.
Сравнение качества распознавания разнообразных методов осложнено многими причинами. Одна из них, и самая весомая – это то, что в большинстве случаев опираться можно только на данные испытаний, предоставляемые самими авторами, так как проведение крупномасштабного исследования по реализации большинства известных методов и сравнения их между собой на едином наборе изображений не представляется возможным:
Основные моменты, влияющие на выбор метода решения задачи, и условия критериев выявлены следующие (в процессе разработки интересуют те, которые выделены курсивом, наиболее оптимальные):
• ограничения на лица:
— ограниченный, предопределенный набор людей;
— ограничения на возможную расу людей либо на характерные отличия на лице (к примеру, растительность на лице, очки);
— отсутствие ограничений.
• положение лица на изображении:
— фронтальное;
— наклон под известным углом;
— любой наклон.
• тип изображения:
— цветное;
— черно-белое;
- любое.
• масштаб лица:
— полностью в «основном кадре»;
— локализовано в определенном месте с определенными размерами;
— неважно.
• разрешение и качество изображения:
— плохое/плохое;
— плохое/хорошее;
— только хорошее;
- любое.
• шумы, помехи, муары:
— слабые;
— сильные;
— неважно.
• количество лиц на изображении:
— известно;
— примерно известно;
— неизвестно.
• освещение:
— известно;
— приблизительно известно;
— любое.
• фон:
— фиксированный;
— контрастный однотонный;
— слабоконтрастный зашумленный;
— неизвестный;
— без разницы.
• важность исследования:
— важнее идентифицировать все лица и черты;
— минимизировать ошибки ложных обнаружений путем минимизации обнаружений на изображении.
Метод Виолы-Джонса иногда выдает поразительные ошибки, о чем упоминали некоторые Хабраюзеры. Поэтому, самым логичным решением в данной ситуации было модифицировать алгоритм Виолы-Джонса и улучшить его характеристики распознавания, если это вообще возможно.
Предлагаемый ниже метод предполагает возможное избавление от:
С учетом заявленного выше, данный метод работы должен снизить время определения эмоции.
Схема нового метода представлена на рисунке ниже:
Итак, для повышения возможностей алгоритма и качества нахождения наклоненных черт лица я предлагаю такой вариант новых типов признаков, как на рисунке.
Такие признаки были выбраны не случайно, а в связи с силуэтами искомых черт лица. С помощью данных признаков программа будет искать намного быстрее нос, брови и рот, но при этом на другие черты лица будет тратить чуть больше времени, чем в стандартном алгоритме, но дополнительные признаки стоит внедрить: в-целом, выигрываются миллисекунды распознавания и незначительно, но увеличивается точность.
Описанные алгоритмы, которые использует метод Виолы — Джонса имеют достаточно широкое применение. Сам же метод может удачно взаимодействовать с другими алгоритмами и может быть адаптирован под определенные нужды и требования. Также, он работает не только со статичными изображениями, можно беспрепятственно обрабатывать данные в реальном времени. Однако даже он не обеспечивает идеальное распознавание эмоций. Попробуем еще выше поднять процент распознавания с помощью Виолы-Джонса. Для этого, с целью увеличения производительности принято решение выполнять предварительную обработку изображения.
Для создания быстрого и надежного способа определения вероятных областей лица человека с целью ускорения обработки на дальнейших этапах обнаружения, предлагается алгоритм определения и выделения граничных контуров. Идея данного подхода заключается в том, что можно подчеркнуть те области, в которых с наибольшей вероятностью можно будет найти лицо и его черты. Тем самым достигается не только ускорение работы алгоритма, но и уменьшается вероятность ложных обнаружений лиц. Данные этапы будут проиллюстрированы на исходной картинке:
Для начала нужно перевести изображение в градации серого. Для этого удобно представить изображение в цветовой модели YUV. Для этого выполняется конверсия:
Переведенное полутоновое изображение сглаживается и осуществляется пространственное дифференцирование — вычисляется градиент функции интенсивности в каждой точке изображения. Предполагается, что области соответствуют реальным объектам, или их частям, а границы областей соответствуют границам реальных объектов. Используется обнаружение разрывов яркости с помощью скользящей маски (sliding window). В разных учебниках и статьях ее по разному называют, обычно именуют фильтром или ядром, которое представляет собой квадратную матрицу, соответствующую сопоставленным Y исходного изображения. Схема пространственной фильтрации изображена ниже:
В применяемом методе, использующем специальные ядра, известные как «операторы Собеля», действующие в области изображения размером 3*3 используется весовой коэффициент 2 для средних элементов. Коэффициенты ядра выбраны так, чтобы при его применении одновременно выполнялось сглаживание в одном направлении и вычисление пространственной производной – в другом. Маски, используемые оператором Собеля, отображены ниже:
По ним получаем составляющие градиента Gx и Gy:
Для вычисления величины градиента эти составляющие необходимо использовать совместно:
(1.4)
или
(1.5)
Результат показывает, насколько «резко» или «плавно» меняется яркость изображения в каждой точке, а значит, вероятность нахождения точки на грани, а также ориентацию границы. Результатом работы оператора Собеля в точке области постоянной яркости будет нулевой вектор, а в точке, лежащей на границе областей различной яркости — вектор, пересекающий границу в направлении увеличения яркости. Также, результат работы — перевод фотографии в граничные контуры (это можно видеть на преобразованной картинке):
Далее, то же полутоновое изображение подвергается пороговой классификации (thresholding), или выбору порога по яркости. Смысл такого порога заключается в том, чтобы отделить искомый светлый объект (foreground) и темный фон (background), где объект — это совокупность тех пикселей, яркость которых превышает порог (I > T), а фон — совокупность остальных пикселей, яркость которых ниже порога (I < T). Примерный алгоритм работы с глобальным порогом в автоматическом режиме выглядит так:
Оператор Собеля не может этого сделать, так как дает очень много шумов и помех, поэтому полутоновое изображение необходимо бинаризировать. Существуют десятки методов выбора порога, но выбран именно метод, придуманный японским ученым Нобуюки Отсу (Otsu's Method) в 1979 году [1], т.к. он быстр и эффективен. Значения яркостей пикселей изображения можно рассматривать как случайные величины, а их гистограмму – как оценку плотности распределения вероятностей. Если плотности распределения вероятностей известны, то можно определить оптимальный (в смысле минимума ошибки) порог для сегментации изображения на два класса c0 и c1 (объекты и фон). Гистограмма — это набор бинов (или столбцов), каждый из которых характеризует количество попаданий в него элементов выборки. В случае полутонового изображения — это пиксели различной яркости, которые могут принимать целые значения от 0 до 255. Благодаря гистограмме человеку видны два четко разделяющихся класса. Суть метода Отсу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый из них был как можно более «плотным». Если выражаться математическим языком, то это сводится к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов (т.е. это сумма отклонений от математических ожиданий данных классов):
где σw – внутриклассовая дисперсия, σ1 и σ2 – дисперсии, а w1 и w2 — вероятности первого и второго классов соответственно. В алгоритме Отсу минимизация внутриклассовой дисперсии эквивалентна максимизации межклассовой дисперсии, которая равна:
где σb – межклассовая дисперсия, w1 и w2 — вероятности первого и второго классов соответственно, а μ1 и μ2 — средние арифметические значения для каждого из классов. Совокупная дисперсия выражается формулой
Общая схема быстрого алгоритма такова:
В более точной реализации есть параметры, которые позволяют убыстрить алгоритм, к примеру, проход через гистограмму делается не от 1 до 254, а от min до (max -1) яркости. «Классическая» бинаризация показана на фотографии ниже:
Достоинствами метода Отсу являются:
Итак, исходя из предыдущих шагов обработки изображения, получены края изображения и разбиение порогом в соответствии со значениями яркости. Теперь, чтобы закрепить результат, необходимо применить детектор границ Канни (Canny) для нахождения и окончательного связывания краёв объектов на изображении в контуры. Джон Канни в своих исследованиях [2] добился построения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края.
С помощью алгоритма Канни решаются такие задачи:
В работе Канни применяется такое понятие как подавление «ложных» максимумов (non-maximum suppression), которое означает, что пикселями границ назначаются такие точки, где достигается локальный максимум градиента в направлении найденного вектора градиента. С помощью оператора Собеля получается угол направления вектора границы (следует из формулы 1.4):
где β(x,y) — угол между направлением вектора ∇f в точке (x,y) и осью y, а Gy и Gx — составляющие градиента. Значение направления вектора должно быть кратно 45°. Угол направления вектора границы округляется до одного из четырех углов, представляющих вертикаль, горизонталь и две диагонали (к примеру, 0, 45, 90 и 135 градусов). Затем условиями проверяется, достигает ли величина градиента локального максимума в соответствующем направлении вектора. Ниже разобран пример для маски 3*3:
После подавления локальных неопределенностей, края становятся более точными и тонкими. Таким образом, получается двоичное изображение, содержащее границы (так называемые «тонкие края»). Их можно видеть на преобразованном изображении:
Выделение границ Канни использует два порога фильтрации:
После детектора Канни изображение подвергается морфологической операции дилатации – расширения, утолщения найденных границ за счет того, что по ним пробегается структурообразующее множество.
И, наконец, последним действием является вычитание полученного бинаризованного изображения из оригинала. Примерно должно получиться вот такое изображение на выходе из подготовки хитрого котэ и заплаканного обалдевшего ребенка к распознаванию их эмоций:
Данный подход универсален, расширяем и если обучено достаточное количество каскадов классификаторов, то метод нахождения работает очень быстро и практически безошибочно.
Подытожим:
Есть в наличии подробно рассмотренный механизм работы алгоритма Виолы-Джонса (Viola-Jones) и описаны в данном посте предложенные мной подходы к повышению эффективности решения задачи обнаружения эмоций человека. Естественно, это не единственный вариант модификации метода. Можете попробовать свои. С помощью таких апгрейдов возможно теоретическое улучшение метода.
Теперь должна быть показана состоятельность данного алгоритма и его применимость на практике. О его реализации я расскажу в своем следующем посте и покажу с помощью иллюстраций. Спасибо за внимание! Надеюсь, что Вам было интересно!
1. Otsu, N., «A Threshold Selection Method from Gray-Level Histograms,» IEEE Transactions on Systems, Man, and Cybernetics, Vol. 9, № 1,1979., pp. 62- 66
2. John Canny, « A Computational Approach to Edge Detection», IEEE Transactions on pattern analysis and machine intelligence, Vol.8, № 6, 1986., pp.679 -698
3. Алгоритмы выделения контуров изображений
Возникающие проблемы на этапах распознавания эмоций
Человек даже не замечает, как он просто справляется с задачами обнаружения лиц и эмоций при помощи своего зрения. Когда глаз смотрит на окружающие лица людей, предметы, природу, подсознательно не чувствуется, какой объем работы проделывает мозг, чтобы обработать весь поток визуальной информации. Человеку не составит труда найти знакомого человека на фотографии, или отличить ехидную гримассу от улыбки.
Человек пытается воссоздать и построить компьютерную систему обнаружения лиц и эмоций — ему это отчасти удается, но каждый раз приходится сталкиваться с большими проблемами при распознавании. Компьютеры в наше время беспрепятственно могут хранить огромные объемы информации, картинки, видео- и аудио файлы. Но отыскать вычислительным системам с такой же легкостью, к примеру, нужную фотографию с определенной эмоцией нужного человека из собственной личной фотогалереи — сложная задача. Решению такой задачи мешают некоторые факторы:
- Разный размер искомых объектов, а также масштаб изображений;
- Определяемый объект может находиться где угодно на изображении;
- Совершенно другой объект может быть похож на искомый;
- Предмет, который мы воспринимаем как что-то отдельное, на изображении никак не выделен, и находится на фоне других предметов, сливается с ними;
- Старые и необработанные фотографии — на них всегда присутствуют «отвлекающие» систему царапины, помехи, искажения, а на сканируемых фото нередко появляются разного рода муары;
- Не стоит забывать, что во многих алгоритмах распознавания (также и в Виола-Джонс) работа идет с 2D-пространстве непосредственно. Поэтому поворот искомого объекта и изменение угла обзора относительно заданных координатных осей проекции влияют на его проекцию в 2D. Один и тот же объект может давать совершенно разную картинку, в зависимости от поворота или расстояния до него. Искомое лицо может быть повернуто в плоскости изображения. Даже относительно небольшое изменение ориентации лица относительно камеры влечет за собой серьезное изменение изображения лица и о распознании мимики данного лица уже и речи быть не может;
- Качество изображения или кадра: засветы и неправильный баланс белого, цветокоррекция и другие параметры безусловно влияют на распознавание объекта;
- Расовая принадлежность людей: цвет кожи, расположение и размеры отдельных распознаваемых признаков;
- Сильное изменение выражения лица. Например, чересчур показное действо может сильно оказать влияние на правильное распознавание определенной эмоции;
- Индивидуальные особенности лица человека, такие как усы, борода, очки, морщины, существенно осложняют автоматическое распознавание;
- Часть лица вообще может быть невидима или обрезана;
- Лица может не быть совсем на фотографии, но машина, как ей кажется, правильно определяет другие объекты за лицо и черты лица и детектирует именно их.
Список можно продолжать еще долго. Но внимание заострено на самых важных моментах, поэтому перечислять все мешающие параметры нет смысла.
Критерии выбора метода в задаче распознавания эмоций
Сравнение качества распознавания разнообразных методов осложнено многими причинами. Одна из них, и самая весомая – это то, что в большинстве случаев опираться можно только на данные испытаний, предоставляемые самими авторами, так как проведение крупномасштабного исследования по реализации большинства известных методов и сравнения их между собой на едином наборе изображений не представляется возможным:
- необходима универсальная коллекция тестовых данных;
- должны присутствовать одинаковые наборы данных;
- необходимы вычислительная мощность — ресурсы уровня одной лаборатории для этого малы;
- высокая трудоемкость исследования данных алгоритмов;
- на основе информации, предоставляемой авторами методов, также сложно провести корректное сравнение, поскольку проверка методов часто производится на разных наборах изображений, с разной формулировкой условий успешного и неуспешного обнаружения. К тому же проверка для многих методов первой категории производилась на значительно меньших наборах изображений.
Основные моменты, влияющие на выбор метода решения задачи, и условия критериев выявлены следующие (в процессе разработки интересуют те, которые выделены курсивом, наиболее оптимальные):
• ограничения на лица:
— ограниченный, предопределенный набор людей;
— ограничения на возможную расу людей либо на характерные отличия на лице (к примеру, растительность на лице, очки);
— отсутствие ограничений.
• положение лица на изображении:
— фронтальное;
— наклон под известным углом;
— любой наклон.
• тип изображения:
— цветное;
— черно-белое;
- любое.
• масштаб лица:
— полностью в «основном кадре»;
— локализовано в определенном месте с определенными размерами;
— неважно.
• разрешение и качество изображения:
— плохое/плохое;
— плохое/хорошее;
— только хорошее;
- любое.
• шумы, помехи, муары:
— слабые;
— сильные;
— неважно.
• количество лиц на изображении:
— известно;
— примерно известно;
— неизвестно.
• освещение:
— известно;
— приблизительно известно;
— любое.
• фон:
— фиксированный;
— контрастный однотонный;
— слабоконтрастный зашумленный;
— неизвестный;
— без разницы.
• важность исследования:
— важнее идентифицировать все лица и черты;
— минимизировать ошибки ложных обнаружений путем минимизации обнаружений на изображении.
Предлагаемые улучшения
Метод Виолы-Джонса иногда выдает поразительные ошибки, о чем упоминали некоторые Хабраюзеры. Поэтому, самым логичным решением в данной ситуации было модифицировать алгоритм Виолы-Джонса и улучшить его характеристики распознавания, если это вообще возможно.
Предлагаемый ниже метод предполагает возможное избавление от:
- больших ограничений в виде недостаточной освещенности, существующих помех на изображении и неразличимого объекта на фоне с помощью предварительной обработки изображения;
- проблемы угла наклона лица путем тренировки новых каскадов, специально обученных на нахождение наклоненной головы;
- неточностей обнаружения эмоций на лице человека путем перечисленных выше пунктов, путем введения новых примитивов Хаара, расширяющих стандартный набор, реализуемый в алгоритме Виолы-Джонса и путем обучения большого количества каскадов, специально заточенных под то или иное состояние черты лица определенной эмоции.
С учетом заявленного выше, данный метод работы должен снизить время определения эмоции.
Схема нового метода представлена на рисунке ниже:
Дополнительные примитивы Хаара
Итак, для повышения возможностей алгоритма и качества нахождения наклоненных черт лица я предлагаю такой вариант новых типов признаков, как на рисунке.
Такие признаки были выбраны не случайно, а в связи с силуэтами искомых черт лица. С помощью данных признаков программа будет искать намного быстрее нос, брови и рот, но при этом на другие черты лица будет тратить чуть больше времени, чем в стандартном алгоритме, но дополнительные признаки стоит внедрить: в-целом, выигрываются миллисекунды распознавания и незначительно, но увеличивается точность.Предварительная обработка изображения
Описанные алгоритмы, которые использует метод Виолы — Джонса имеют достаточно широкое применение. Сам же метод может удачно взаимодействовать с другими алгоритмами и может быть адаптирован под определенные нужды и требования. Также, он работает не только со статичными изображениями, можно беспрепятственно обрабатывать данные в реальном времени. Однако даже он не обеспечивает идеальное распознавание эмоций. Попробуем еще выше поднять процент распознавания с помощью Виолы-Джонса. Для этого, с целью увеличения производительности принято решение выполнять предварительную обработку изображения.
Для создания быстрого и надежного способа определения вероятных областей лица человека с целью ускорения обработки на дальнейших этапах обнаружения, предлагается алгоритм определения и выделения граничных контуров. Идея данного подхода заключается в том, что можно подчеркнуть те области, в которых с наибольшей вероятностью можно будет найти лицо и его черты. Тем самым достигается не только ускорение работы алгоритма, но и уменьшается вероятность ложных обнаружений лиц. Данные этапы будут проиллюстрированы на исходной картинке:
Изображение в градациях серого
Для начала нужно перевести изображение в градации серого. Для этого удобно представить изображение в цветовой модели YUV. Для этого выполняется конверсия:
- Y = 0.299 * R + 0.587 * G + 0.114 * B;
- U = -0.14713 * R - 0.28886 * G + 0.436 * B; (1.1)
- V = 0.615 * R - 0.51499 * G - 0.10001 * B;
Пространственная фильтрация
Переведенное полутоновое изображение сглаживается и осуществляется пространственное дифференцирование — вычисляется градиент функции интенсивности в каждой точке изображения. Предполагается, что области соответствуют реальным объектам, или их частям, а границы областей соответствуют границам реальных объектов. Используется обнаружение разрывов яркости с помощью скользящей маски (sliding window). В разных учебниках и статьях ее по разному называют, обычно именуют фильтром или ядром, которое представляет собой квадратную матрицу, соответствующую сопоставленным Y исходного изображения. Схема пространственной фильтрации изображена ниже:
Оператор Собеля
В применяемом методе, использующем специальные ядра, известные как «операторы Собеля», действующие в области изображения размером 3*3 используется весовой коэффициент 2 для средних элементов. Коэффициенты ядра выбраны так, чтобы при его применении одновременно выполнялось сглаживание в одном направлении и вычисление пространственной производной – в другом. Маски, используемые оператором Собеля, отображены ниже:
По ним получаем составляющие градиента Gx и Gy:
Gx = (z7 + 2z8 + z9) – (z1 + 2z2 + z3) (1.2)
и
Gy = (z3 + 2z6 + z9) – (z1 + 2z4 + z7) (1.3)
Для вычисления величины градиента эти составляющие необходимо использовать совместно:
(1.4)или
(1.5) Результат показывает, насколько «резко» или «плавно» меняется яркость изображения в каждой точке, а значит, вероятность нахождения точки на грани, а также ориентацию границы. Результатом работы оператора Собеля в точке области постоянной яркости будет нулевой вектор, а в точке, лежащей на границе областей различной яркости — вектор, пересекающий границу в направлении увеличения яркости. Также, результат работы — перевод фотографии в граничные контуры (это можно видеть на преобразованной картинке):
Пороговая классификация
Далее, то же полутоновое изображение подвергается пороговой классификации (thresholding), или выбору порога по яркости. Смысл такого порога заключается в том, чтобы отделить искомый светлый объект (foreground) и темный фон (background), где объект — это совокупность тех пикселей, яркость которых превышает порог (I > T), а фон — совокупность остальных пикселей, яркость которых ниже порога (I < T). Примерный алгоритм работы с глобальным порогом в автоматическом режиме выглядит так:
- Выбирается начальная оценка порога Т – это может быть средний уровень яркости изображения (полусумма минимальной и максимальной яркости, min+max/2) или любой другой критерий порога;
- Производится некая сегментация изображения с помощью порога Т — в результате образуются две группы пикселей: G1, состоящая из пикселей с яркостью больше T, и G2, состоящая из пикселей с яркостью меньше или равной T;
- Вычисляются средние значения μ1 и μ2 яркостей пикселей по областям G1 и G2;
- Вычисляется новое значение порога T = 0.5 * (μ1 + μ2);
- Повторяются шаги со второго по четвертый до тех пор, пока разница значений порога Т предыдущего и T вычисленного в последней итерации не окажется меньше наперед заданного параметра ε.
Бинаризация методом Отсу
Оператор Собеля не может этого сделать, так как дает очень много шумов и помех, поэтому полутоновое изображение необходимо бинаризировать. Существуют десятки методов выбора порога, но выбран именно метод, придуманный японским ученым Нобуюки Отсу (Otsu's Method) в 1979 году [1], т.к. он быстр и эффективен. Значения яркостей пикселей изображения можно рассматривать как случайные величины, а их гистограмму – как оценку плотности распределения вероятностей. Если плотности распределения вероятностей известны, то можно определить оптимальный (в смысле минимума ошибки) порог для сегментации изображения на два класса c0 и c1 (объекты и фон). Гистограмма — это набор бинов (или столбцов), каждый из которых характеризует количество попаданий в него элементов выборки. В случае полутонового изображения — это пиксели различной яркости, которые могут принимать целые значения от 0 до 255. Благодаря гистограмме человеку видны два четко разделяющихся класса. Суть метода Отсу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый из них был как можно более «плотным». Если выражаться математическим языком, то это сводится к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов (т.е. это сумма отклонений от математических ожиданий данных классов):
σw2 = w1 * σ12 + w2 * σ22, (1.6)где σw – внутриклассовая дисперсия, σ1 и σ2 – дисперсии, а w1 и w2 — вероятности первого и второго классов соответственно. В алгоритме Отсу минимизация внутриклассовой дисперсии эквивалентна максимизации межклассовой дисперсии, которая равна:
σb2 = w1 * w2 (μ1 – μ2)2 , (1.7)где σb – межклассовая дисперсия, w1 и w2 — вероятности первого и второго классов соответственно, а μ1 и μ2 — средние арифметические значения для каждого из классов. Совокупная дисперсия выражается формулой
σT2 = σw2 + σb2. (1.8)Общая схема быстрого алгоритма такова:
- Вычисляем гистограмму (один проход через массив пикселей). Дальше нужна только гистограмма; проходов по всему изображению больше не требуется.
- Начиная с порога t = 1, проходим через всю гистограмму, на каждом шаге пересчитывая дисперсию σb(t). Если на каком-то из шагов дисперсия оказалась больше максимума, то дисперсия обновляется и T = t.
- Искомый порог равен T.
В более точной реализации есть параметры, которые позволяют убыстрить алгоритм, к примеру, проход через гистограмму делается не от 1 до 254, а от min до (max -1) яркости. «Классическая» бинаризация показана на фотографии ниже:
Достоинствами метода Отсу являются:
- Простота реализации;
- Хорошо адаптируем к разным изображениям, выбирая наиболее оптимальный порог;
- Временнáя сложность алгоритма O(N) операций, где N выражается количеством пикселей в изображении.
- Такая пороговая бинаризация очень зависит от равномерной распределенности яркости на изображении. Решение – это использование нескольких локальных порогов вместо одного глобального.
Детектор границ Канни
Итак, исходя из предыдущих шагов обработки изображения, получены края изображения и разбиение порогом в соответствии со значениями яркости. Теперь, чтобы закрепить результат, необходимо применить детектор границ Канни (Canny) для нахождения и окончательного связывания краёв объектов на изображении в контуры. Джон Канни в своих исследованиях [2] добился построения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края.
С помощью алгоритма Канни решаются такие задачи:
- Подавление «ложных» максимумов. Только некоторые из максимумов отмечаются как границы;
- Последующая двойная пороговая фильтрация. Потенциальные границы определяются порогами. Разбиение на тонкие края (edge thinning);
- Подавление всех неоднозначных краёв, не принадлежащих каким-либо границам областей. Связывание краёв в контуры (edge linking).
В работе Канни применяется такое понятие как подавление «ложных» максимумов (non-maximum suppression), которое означает, что пикселями границ назначаются такие точки, где достигается локальный максимум градиента в направлении найденного вектора градиента. С помощью оператора Собеля получается угол направления вектора границы (следует из формулы 1.4):
β(x,y) = arctg(Gx/Gy), (1.9)где β(x,y) — угол между направлением вектора ∇f в точке (x,y) и осью y, а Gy и Gx — составляющие градиента. Значение направления вектора должно быть кратно 45°. Угол направления вектора границы округляется до одного из четырех углов, представляющих вертикаль, горизонталь и две диагонали (к примеру, 0, 45, 90 и 135 градусов). Затем условиями проверяется, достигает ли величина градиента локального максимума в соответствующем направлении вектора. Ниже разобран пример для маски 3*3:
- если угол направления градиента равен нулю, точка будет считаться границей, если её интенсивность больше чем у точки выше и ниже рассматриваемой точки;
- если угол направления градиента равен 90 градусам, точка будет считаться границей, если её интенсивность больше чем у точки слева и справа рассматриваемой точки;
- если угол направления градиента равен 135 градусам, точка будет считаться границей, если её интенсивность больше чем у точек находящихся в верхнем левом и нижнем правом углу от рассматриваемой точки;
- если угол направления градиента равен 45 градусам, точка будет считаться границей, если её интенсивность больше чем у точек находящихся в верхнем правом и нижнем левом углу от рассматриваемой точки.
После подавления локальных неопределенностей, края становятся более точными и тонкими. Таким образом, получается двоичное изображение, содержащее границы (так называемые «тонкие края»). Их можно видеть на преобразованном изображении:
Выделение границ Канни использует два порога фильтрации:
- если значение пикселя выше верхней границы – он принимает максимальное значение и граница считается достоверной, пиксель выделен;
- если ниже – пиксель подавляется;
- точки со значением, попадающим в диапазон между порогами, принимают фиксированное среднее значение;
- затем найденные пиксели со средним фиксированным добавляются к группе, если они соприкасаются с группой по одному из четырех направлений.
Причесывание изображения
После детектора Канни изображение подвергается морфологической операции дилатации – расширения, утолщения найденных границ за счет того, что по ним пробегается структурообразующее множество.
И, наконец, последним действием является вычитание полученного бинаризованного изображения из оригинала. Примерно должно получиться вот такое изображение на выходе из подготовки хитрого котэ и заплаканного обалдевшего ребенка к распознаванию их эмоций:
Выводы
Данный подход универсален, расширяем и если обучено достаточное количество каскадов классификаторов, то метод нахождения работает очень быстро и практически безошибочно.
Подытожим:
Есть в наличии подробно рассмотренный механизм работы алгоритма Виолы-Джонса (Viola-Jones) и описаны в данном посте предложенные мной подходы к повышению эффективности решения задачи обнаружения эмоций человека. Естественно, это не единственный вариант модификации метода. Можете попробовать свои. С помощью таких апгрейдов возможно теоретическое улучшение метода.
Теперь должна быть показана состоятельность данного алгоритма и его применимость на практике. О его реализации я расскажу в своем следующем посте и покажу с помощью иллюстраций. Спасибо за внимание! Надеюсь, что Вам было интересно!
Список литературы
1. Otsu, N., «A Threshold Selection Method from Gray-Level Histograms,» IEEE Transactions on Systems, Man, and Cybernetics, Vol. 9, № 1,1979., pp. 62- 66
2. John Canny, « A Computational Approach to Edge Detection», IEEE Transactions on pattern analysis and machine intelligence, Vol.8, № 6, 1986., pp.679 -698
3. Алгоритмы выделения контуров изображений
