Введение

Данная статья является продолжением серии статей описывающей алгоритмы лежащие в основе
Synet — фреймворка для запуска предварительно обученных нейронных сетей на CPU.

В предыдущей статье я описал методы, основанные на матричном умножении. Эти методы с минимальными усилиями позволяют достичь во многих случаях более 80% от теоретического максимума. Казалось бы, ну куда тут можно еще дальше улучшать? Оказывается можно! Существуют математически методы, которые позволяют сократить число операций, необходимых для свертки. С одним из таких методов — алгоритму свертки по методу Винограда мы и ознакомимся в настоящей статье.


Шмуэль Виноград (Shmuel Winograd) 1936.01.04 — 2019.03.25 — выдающийся израильский и американский ученый в области компьютерных наук, создатель алгоритмов быстрого матричного умножения, свертки и преобразования Фурье.

Введение

Данная статья является продолжением серии статей описывающей алгоритмы лежащие в основе
Synet — фреймворка для запуска предварительно обученных нейронных сетей на CPU.

Если смотреть на распределение процессорного времени, которое тратится на прямое распространение сигнала в нейронных сетях, то окажется что зачастую более 90% всего времени тратится в свёрточных слоях. Поэтому если мы хотим получить быстрый алгоритм для нейронной сети – нам нужен, прежде всего, быстрый алгоритм для свёрточного слоя. В настоящей статье я хочу описать методы оптимизации прямого распространения сигнала в свёрточном слое. Причем начать хочется с наиболее широко распространенных методов, основанных на матричном умножении. Изложение я буду стараться вести в максимально доступной форме, чтобы статья была интересна не только специалистам (они и так про это все знают), но и более широкому кругу читателей. Я не претендую на полноту обзора, так что любые замечания и дополнения только приветствуются.

Введение

Здравствуйте, уважаемые хабровчане!

Последние два года моей работы в компании Synesis были тесно связаны с процессом создания и развития Synet — открытой библиотеки для запуска предварительно обученных сверточных нейронных сетей на CPU. В процессе этой работы мне пришлось столкнуться с рядом интересных моментов, которые касаются вопросов оптимизации алгоритмов прямого распространения сигнала в нейронных сетях. Как мне кажется, описание этих моментов было бы весьма интересным для читателей Хабрахабра. Чему я и хочу посвятить цикл своих статей. Продолжительность цикла будет зависеть от вашего интереса к данной теме ну и конечно же от моей способности побороть лень. Начать цикл хочется с описания самого велосипеда фреймворка. Вопросы алгоритмов, которые лежат в его основе будут раскрыты в последующих статьях:

1. Сверточный слой: методы оптимизации основанные на матричном умножении
2. Сверточный слой: быстрая свертка по методу Шмуэля Винограда

Введение

Умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверточных слоях неронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию. Почему так происходит? Ответ кроется в очень эффективной реализации этого алгоритма для процессоров, графических ускорителей (а в последнее время и специальных ускорителей матричного умножения). Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому не удивительно, что многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.

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

Процесс изложения будет вестись ввиде шагов с примерами по последовательному ускорению алгоритма. Я старался писать максимально упрощая задачу, но не более того. Надеюсь у меня получилось…

В последнее время метод Виолы-Джонса, который долгое время был основным способом детектирования объектов на изображении, отступает под натиском более новых и совершенных алгоритмов. Тем не менее, актуальность этого метода еще сохраняется и в настоящем времени.

Да, каскадный классификатор основанный на признаках Хаара (метод Виолы-Джонса) уступает в скорости работы каскадному LBP классификатору. Он менее точен, чем детектор, основанный на HOG признаках, и тем более детектор, базирующийся на сверточных нейронных сетях. И все же у него есть определенная ниша, когда требуется точность выше, чем у LBP каскада, но скорость работы более точных детекторов недостаточна высока. Не менее важным фактором является то, что для каскадного Хаар классификатора существует большое количество уже обученных каскадов, в том числе в стандартной поставке библиотеки OpenCV. Поэтому скорость работы этого алгоритма весьма важна. Что и побудило автора в свое время занятся его оптимизацией.


Ну и какая статья об детектировании лиц, может обойтись без фотографии Лены?

Введение

Данную статью я решил написать после прочтения статьи «Массивно-параллельная стабилизация изображения», в которой описывается алгоритм для стабилизации изображения с поворотных камер. Дело в том, что в свое время мной был реализован алгоритм для стабилизации изображения со стационарных камер, который используется в IP-видеосервере MagicBox и некоторых других продуктах компании Синезис, в которой я работаю по настоящее время. Алгоритм получился достаточно удачным по своим скоростным характеристикам. В частности, в нем очень эффективно реализован алгоритм поиска смещения текущего изображения относительно фона. Эта эффективность позволила задействовать основные его элементы (конечно с некоторыми модификациями) для сопровождения объектов, а также для проверки их на неподвижность.

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

Рис. 1 Стабилизация изображения иногда очень полезна.

Введение

Ранее во вступительной статье я поднимал список проблем, с которыми придется столкнуться разработчику, если он захочет оптимизировать оптимизацию обработки изображения при помощи SIMD инструкций. Теперь пришло время на конкретном примере показать, как указанные выше проблемы можно решить. Я долго думал, какой алгоритм выбрать для первого примера, и решил остановиться на медианной фильтрации. Медианная фильтрация является эффективным способом подавления шумов, которые неизбежно появляются на цифровых камерах в условиях малого освещения сцены. Алгоритм этот достаточно ресурсоемок – так например, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. Но в тоже время он оперирует только с 8-битными числами и ему для работы требуется сравнительно не много входных данных. Эти обстоятельства делают алгоритм достаточно простым для SIMD оптимизации и в тоже время позволяют получить из нее весьма существенное ускорение.

SIMD и обработка изображений

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

Введение

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



Данный алгоритм был впервые реализован мной во время разработки алгоритмов видеоаналитики для IP-видеосервера MagicBox, которое разрабатывает компания Синезис, в которой я работаю в настоящее время. Как известно, при детектировании движения на видеопоследовательности, условия освещенности не всегда идеальны. И простейший детектор движения, основанный на разности текущего кадра и некого усредненного фона будет реагировать не только на реальные объекты, но также и на виртуальные: подвижные тени и световые зайчики. Что является нежелательным, так как может приводить искажению формы детектируемых предметов а также к ложным срабатываниям детектора движения. Это актуально в солнечную погоду, а особенно в случае переменной облачности. Потому наличие алгоритма по выделению теней, может весьма положительно сказаться на точности всего детектора. Но давайте рассмотрим все по порядку.

Введение

Недавно наткнулся на статью, размещенную на Хабрахабре, посвященную сравнению изображений «Выглядит похоже». Как работает перцептивный хэш. Так как я сам достаточно долго занимался этой тематикой (являюсь автором программы AntiDupl), то мне захотелось поделиться здесь своим опытом по данному вопросу. В статье я приведу два варианта алгоритма сравнения похожих изображений — базовый и улучшенный. Все они были проверены автором на практике в рамках указанного выше проекта. Изложение мое будет вестись без строгих доказательств, сложных формул и специальной математической терминологии. Надеюсь, что читатели простят меня за это.

Базовый Алгоритм

Мера схожести изображений

При сравнении похожих изображений первым встает вопрос: что считать мерой схожести изображений? Очевидно, что это величина имеет значение обратное различию изображений друг от друга. Следственно нужно выбрать некую метрику, характеризующую различие изображений друг от друга. Тогда схожими изображениями будут считаться изображения, отличие между которыми меньше некоторого порога. Для изображений с одинаковыми габаритами, обычно такой мерой различия служит среднеквадратическое отклонение пикселей одного изображения от другого. Хотя конечно, нам ни что не мешает выбрать другую метрику, например усредненную абсолютную разность пикселей изображений друг от друга.