Методы определения объектов на изображении

Введение

Компьютерное зрение — это технология создания машин, способных производить обнаружение, отслежи-вание и классификацию объектов. Для обработки данных в ней применяются статистические методы, а также модели, построенные при помощи геометрии, физики и теории обучения. Компьютерное зрение широко применяется в управлении мобильными роботами, в средствах наблюдения, анализе медицинских изображений, а также в интерфейсе взаимодействия «человек — компьютер».

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

Определение объекта с помощью поиска контуров

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

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

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

Одним из самых используемых методов выделения краев — оператор Собеля. Это дискретный дифференциальный оператор, вычисляющий приближенное значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке является вектор градиента яркости или его норма. Оператор Собеля основан на свёртке изображения небольшими целочисленными фильтрами в вертикальном и горизонтальном направлениях [1].

$$G_{x}=\begin{bmatrix} -1 & 0 & 1\\ -2 & 0 & 2\\ -1 & 0 & 1 \end{bmatrix}*A$$ и $$G_{y}=\begin{bmatrix} -1 & -2 & -1\\ 0 & 0 & 0\\ 1 & 2 & 1 \end{bmatrix}*A$$

Формула 1. Определение приближенных производных по горизонтали и вертикали при помощи матриц свертки Собеля, где G и G — изображения, содержащие прибли- жённые производные, А — оригинальное изображение, a* — двумерная операция свертки.

В каждой точке изображения приближённое значение величины градиента можно вычислить путём поэлемент- ного использования полученных приближенных значений производных в формуле 2 [1]

$$G_{i}=\sqrt{G_{yi}^{2}+G_{xi}^{2}}GG]g$$

Формула 2. Определение величины градиента i-го элемента изображения, где G_i — элемент изображения, содержащего величины градиента, а G_xi и G_yi — элементы изображений, содержащих приближённые производные.

Направление вектора градиента вычисляется по формуле 3, применяемой также поэлементно [1].

$$ \theta_{i}=arctan\left(\frac{G_{yi}}{G_{xi}}\right) $$

Формула 3. Определение величины градиента i-го элемента изображения, где θ — элемент изображения, содержащего направление вектора градиента, а G и G — элементы изображений, содержащих приближённые производные.

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

Кроме оператора Собеля, могут использоваться и другие матричные детекторы границ, такие как оператор Прюитта, оператор Шарра и перекрёстный оператор Робертса. Эти методы схожи с оператором Собеля, но используют другие матрицы свертки [1].

$$G_{x}=\begin{bmatrix} -1 & 0 & 1\\ -1 & 0 & 1\\ -1 & 0 & 1 \end{bmatrix}*A$$ и $$G_{y}=\begin{bmatrix} -1 & -1 & -1\\ 0 & 0 & 0\\ 1 & 1 & 1 \end{bmatrix}*A$$

Формула 4. Определение приближенных производных по горизонтали и вертикали при помощи матриц свертки Прюитта, где G и G — изображения, содержащие приближённые производные, А — оригинальное изображение, a* — двумерная операция свертки.

$$G_{x}=\begin{bmatrix} -3 & 0 & 3\\ -10 & 0 & 10\\ -3 & 0 & 3 \end{bmatrix}*A$$ и $$G_{y}=\begin{bmatrix} -3 & -10 & -3\\ 0 & 0 & 0\\ 3 & 10 & 3 \end{bmatrix}*A$$

Формула 5. Определение приближенных производных по горизонтали и вертикали при помощи матриц свертки Шарра, где G и G — изображения, содержащие приближённые производные, А — оригинальное изображение, a* — двумерная операция свертки.

$$G_{x}=\begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}*A$$ и $$G_{y}=\begin{bmatrix} 0 & 1\\ -1 & 0 \end{bmatrix}*A$$

Формула 6. Определение приближенных производных по горизонтали и вертикали при помощи матриц свертки Робертса, где G и G — изображения, содержащие приближённые производные, А — оригинальное изображение, а* — двумерная операция свертки.

Листинг 1. Использование матричных детекторов границ в OpenCV 3.x на примере матрицы Собеля

Mat contour_x, contour_y, kernelMat; //Определение ядра float kernel[KERNEL_SIZE][KERNEL_SIZE] = { {-1.0f, -2.0f, -1.0f}, { 0.0f, 0.0f, 0.0f}, { 1.0f, 2.0f, 1.0f } }; //Загрузка изображения Mat img = imread("lena.jpg"); cvtColor(img, img, CV_BGR2GRAY); kernelMat = Mat(KERNEL_SIZE, KERNEL_SIZE, CV_32F); //Инициализация ядра для поиска приближенной производной по горизонтали for (int i = 0; i < KERNEL_SIZE; i++) { for (int j = 0; j < KERNEL_SIZE; j++) { kernelMat.at<float>(j, i) = kernel[i][j]; } } //Применение горизонтальной матрицы Собеля к изображению filter2D(img, contour_x, -1, kernelMat); //Инициализация ядра для поиска приближенной производной по вертикали for (int i = 0; i < KERNEL_SIZE; i++) { for (int j = 0; j < KERNEL_SIZE; j++) { kernelMat.at<float>(j, i) = kernel[j][i]; } } //Применение вертикальной матрицы Собеля к изображению filter2D(img, contour_y, -1, kernelMat); //Определение величин градиента for (int i = 0; i < img.size().width; i++) { for (int j = 0; j < img.size().height; j++) { img.at<uchar>(j, i) = sqrt(pow(contour_x.at<uchar>(j, i), 2) + pow(contour_y.at<uchar>(j, i), 2)); } }

Более качественным и точным методом является детектор Канни. В 1986 году Джон Канни разработал детектор границ, оптимальный для трех критериев: низкий уровень ошибок, правильная локализация и минимизация откликов на одну границу

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

Алгоритм детектора Канни состоит из 5 шагов. Первый шаг — сглаживание. Оно используется, когда во избежание появления ложных границ требуется уменьшить количество шумов на изображении. Для этого часто используется размытие фильтром Гаусса или каким-либо матричным фильтром размытия [2].

Следующие два шага это нахождение градиентов и подавление не-максимумов. Для начала находятся вся градиенты яркости, для этого можно использовать, например, описанный выше оператор Собеля, но для того чтобы граница была четкой и понятной, она должна быть представлена тонкой линией. Поэтому границей будут являться те пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Допустим, что почти все пиксели в градиенте имеют ориентацию вверх. Тогда значение градиента в них будет сравнено с нижеи вышерасположенными пикселями. Те пиксели, которые имеют наибольшее значение, останутся в результирующем изображении, остальные—будут подавлены [2].

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

В детекторе границ Канни используется два порога: нижний и верхний. Пиксель, значение которого выше верхней границы, принимает максимальное значение, т.е. контур считается достоверным. Если значение пикселя не достигает нижнего порога — пиксель подавляется. Если его значение попадает в диапазон между порогами, то он принимает среднее значение, а решение о том, является ли он точкой границы, будет принято во время трассировки области неоднозначности [2].

Задача трассировки сводится к распределению пикселей, получивших среднее значение. Если такой пиксель соприкасается с достоверным контуром, то его значение приравнивается к максимальному значению и он становится частью границы, в противном случае он подавляется.

В OpenCV 3.x и выше есть встроенная функция для фильтрации Канни — Canny(Mat src, Mat dst, int lowThreshold, int highThreshold, int kernelSize). Где src — входное черно-белое изображение, dst — выходное бинаризованное изображение с найденными границами, lowThreshold и highThreshold — нижний и верхний пороги, kernelSize—размер матрицы Собеля.

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

Примером детектора углов можно взять алгоритм SUSAN (Smallest Univalue Segment Assimilation Nucleus). При использовании данного алгоритма для каждого пикселя изображения рассматривается круговой регион фиксированного радиуса. Центр региона называется ядром, его значение интенсивности запоминается и сравнивается со значениями интенсивности других точек региона. По итогам сравнения пиксели региона разделяются на две категории: интенсивность которых близка к интенсивности ядра (область с пикселями данной категории называют USAN) и интенсивность которых имеет большое отличие от интенсивности ядра [3].

Если регион находится на однородном участке изображения, то схожие точки занимают практически всю область, на ребрах объектов их количество падает примерно до 50%, если их количество резко меньше этого значения, то в данной области находится угол объекта, и можно примерно судить о его величине [3].

На данный момент для расчета USAN используются формулы 7 и 8 [4]:

$$ c\left( \xrightarrow[r]{}, \xrightarrow[r_{0}]{} \right)=e^{-\left(\frac{ I\left(\xrightarrow[r]{}\right)-I\left(\xrightarrow[r_{0}]{}\right) }{t}\right)^{6}} $$

Формула 7. Формула сравнения интенсивности ядра и другой точки региона, где $$ c\left( \xrightarrow[r]{}, \xrightarrow[r_{0}]{} \right) $$ — результат, $$ I\left(\xrightarrow[r_{0}]{}\right) $$ — интенсивность точки, $$ \xrightarrow[r]{} $$ — точка региона, $$ \xrightarrow[r_{0}]{} $$ — ядро, t — пороговое значение.

$$ n\left(\xrightarrow[r_{0}]{}\right)=\sum_{\xrightarrow[r]{}}c\left(\xrightarrow[r]{},\xrightarrow[r_{0}]{}\right) $$

Формула 8. Формула расчета USAN для региона, где $$ n\left(\xrightarrow[r_{0}]{}\right) $$ — результат, $$ \xrightarrow[r]{} $$ — точка региона, $$ \xrightarrow[r_{0}]{} $$ — ядро, $$ c\left(\xrightarrow[r_{0}]{}\right) $$ — результат сравнения интенсивности точки и ядра

После расчета USAN, для получения изображения с найденными углами и контурами требуется пороговая фильтрация. Так как при применении SUSAN нахождение угла в регионе имеет обратную зависимость от значения USAN, то во время пороговой фильтрации сравнивается не сам USAN, а разница между пороговым значением и значением USAN [4].

$$ R\left(\xrightarrow[r_{0}]{}\right)=\begin{cases} g-n\left(\xrightarrow[r_{0}]{}\right),\ if\ b\left(\xrightarrow[r_{0}]{} \right) \lt g \\ 0, \ else \end{cases} $$

Формула 9. Пороговая фильтрация значения USAN, $$ R\left(\xrightarrow[r_{0}]{}\right)$$ — значение отклика края в точке, $$ n\left(\xrightarrow[r_{0}]{}\right)$$ — значение USAN в точке, g — пороговое значение, $$ \xrightarrow[r_{0}]{}$$ — точка на изображении.

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

Листинг 2. Пример расчета USAN и отрисовки результата

Mat calcUSAN(Mat img) { int max = 0; //Расчет USAN на изображении for (int y = 0; y < height - 1; y++) { for (int x = 0; x < width - 1; x++) { //Функция расчета USAN для точки int dot = calcArea(x, y); img.at<uchar>(y, x) = dot; if (imagePlan_angle.at<uchar>(y, x) > max) { max = (int) img.at<uchar>(y, x); } } } //Расчет порога max = max * 0.75; //Если меньше порога, то обозначаем инверсивным цветом, иначе зарисовываем черным for (int y = 0; y < height - 1; y++) { for (int x = 0; x < width - 1; x++) { if (imagePlan_angle.at<uchar>(y, x) < max) { imagePlan_angle.at<uchar>(y, x) = max - imagePlan_angle.at<uchar>(y, x); } else { imagePlan_angle.at<uchar>(y, x) = 0; } } } return img; } //Функция расчета USAN для точки int calcArea(int x, int y) { double res = 0; int th = 128; for (int j = -3; j < 4; j++) { for (int i = -3; i < 4; i++) { if ( i + x > 0 && j + y > 0 && i + x < width && j + y < height ) { res += exp( -pow( double((int)imagePlan_bin.at<uchar>(y + j, x + i) - (int)imagePlan_bin.at<uchar> (y, x)) / th, 6)); } } } return res; }

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

Описание и кодирование контуров

После нахождения контуров или углов объектов на изображении для их хранения и анализа чаще всего требуется перевести их из представления в виде изображения в более удобный для обработки формат.

Самыми простыми способами такого перевода считаются прослеживающие алгоритмы. Одними из наиболее распространённых представителей таких алгоритмов являются цепной код Фримена и метод Жука. Оба метода требуют, чтобы изображение было бинаризовано, а все контура на нем замкнуты

Суть метода Фримена заключается в последовательной записи значения векторов между соседними дискретными участками контура. Значение вектора находится в пределах от 0 до 7. Для начала работы алгоритма Фримена на изображение накладывается сетка (размер ячеек зависит от требований к аппроксимации) и назначается ядром любая ячейка, содержащая участок контура. Следующим шагом является поиск среди смежных ядру ячеек той, что содержит наибольший участок контура. После нахождения такой ячейки вектор между ней и ядром записывается в последовательность, и ядро переносится в найденную ячейку. Затем поиск повторяется, но в этот раз в него не входит предыдущая ячейка.

Когда ядром снова становится начальная ячейка, последовательность замыкается, а новым ядром назначается любая ячейка содержащая участок ещё не описанного контура изображения. Результатом работы цепного кода Фримена является набор числовых последовательностей, каждая из которых описывает замкнутый контур.

Метод Жука заключается в попиксельном обходе замкнутого контура. Изначально Жук ставится на белый пиксель изображений и движется до тех пор, пока не попадет на черный элемент. Как только Жук дойдет до черного пикселя он поворачивает налево и переходит на следующий элемент. Если этот элемент белый, то он поворачивает направо, иначе снова поворачивает налево. Обход контура заканчивается, как только Жук снова дойдет до первого посещенного черного пикселя.

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

Определение объекта при помощи каскадных классификаторов

Каскадные классификаторы

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

Каскадные классификаторы обучаются с несколькими сотнями «положительных» образцов отдельных объектов и произвольными «негативными» изображениями того же размера. После обучения классификатора его можно применить к области изображения и определить объект, о котором идет речь. Для поиска объекта во всем кадре окно поиска перемещается по всему изображению с некоторым нахлестом. Этот процесс чаще всего используется при обработке изображений для обнаружения и отслеживания объектов, в первую очередь для обнаружения и распознавания лиц.

Ансамблевые методы — это набор слабых классификаторов (под слабостью классификатора подразумевается, что его ошибка на обучение выборки менее 50%, но более 0%). Объединяя их предсказания можно достичь более высокой точности классификации объектов из тестовой выборки [5].

Метод Виолы-Джонса

Метод Виолы-Джонса — это алгоритм, позволяющий обнаруживать объекты на изображении. Алгоритм может распознавать различные классы изображений, но основная его задача — обнаружение лиц. В библиотеке OpenCV он реализуется функцией (cvHaarDetectObjects()) [6].

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

Основные принципы:

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

  $$ L\left(x,y\right)=\sum_{i=0, j=0}^{i{\leq}x,j{\leq}y} I\left(i,j\right) $$

  Формула 10. Расчет элемента матрицы интегрального представления изображения, где I(i, j) — яркость пикселя исходного изображения.
• Используются признаки Хаара (признаки Хаара можно определить, как разность сумм пикселей двух смежный областей внутри прямоугольника), спомощью которых происходит поиск объекта. Главным преимуществом признаков Хаара, по сравнению с остальными признаками является скорость. При интегральном представлении изображения, признаки Хаара вычисляется за постоянное время. В стандартном методе Виолы-Джонса используются прямоугольные признаки, они называются примитивами Хаара.

• Использование бустинга (бустинга — это общий метод повышения производительности алгоритмов обучения) для выбора наиболее подходящих признаков для искомого объекта на данной части изображения. В OpenCV используется алгоритм машинного обучения AdaBoost. Алгоритмы бустинга предназначены для обучения T слабых классификаторов. По отдельности эти классификаторы как правило просты. Каждый классификатор Kt (t = {1,2,…T}) ассоциирован с весом at, который применяется при объединении результатов со всех классификаторов. Входной вектор признаков: X = (x1,x2,…xi,…,XM), где i — номер признака, помечается бинарными метками yi = {–1, +1} (в зависимости от используемого алгоритма бустинга диапазон значений может изменяться) [8].

Окончательное уравнение для классификации можно представить в виде формулы 11 [7]:

$$ F(x)=sign\left(\sum_{m=1}^{M} \theta_{m}f_{m}(x)\right) $$

Формула 11. Уравнение для классификации, где f m обозначает слабый классификатор, а θ — соответствующий вес. Это точное взвешивание комбинации слабых классификаторов M.

Листинг 3. Загрузка изображения и каскадов

import numpy as np import cv2 face_cascade = cv2.CascadeClassifier('haarcascade_frontalface_default.xml') eye_cascade = cv2.CascadeClassifier('haarcascade_eye.xml') img = cv2.imread('sachin.jpg') gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

Реализация каскада Хаара с применением технологии OpenCV

OpenCV уже содержит много предварительно подготовленных классификаторов для распознавания лица, сохраненных в виде XML файла. Эти файлы XML расположены в папке opencv / data / haarcascades /. Ниже представлен официальный пример детектора лиц и глаз при помощи OpenCV.

Для начала требуется загрузить нужные классификаторы XML и входное изображение (или видео) в монохромном сером режиме.

Затем происходит поиск лица на изображении с использованием загруженных классификаторов. Если лица найдены, то возвращаются их позиции, представленные объектами Rect (x, y, w, h). После получения данных о расположении лиц, создается ROI для каждого лица, и поиск глаз происходит только в этих ROI, так как в задаче распознавания лиц учитываются только изображения глаз, расположенные на лицах

Листинг 4. Определение объекта при помощи каскадов

faces = face_cascade.detectMultiScale(gray, 1.3, 5) for (x,y,w,h) in faces: cv2.rectangle(img,(x,y),(x+w,y+h),(255,0,0),2) roi_gray = gray[y:y+h, x:x+w] roi_color = img[y:y+h, x:x+w] eyes = eye_cascade.detectMultiScale(roi_gray) for (ex,ey,ew,eh) in eyes: cv2.rectangle(roi_color,(ex,ey),(ex+ew,ey+eh),(0,255,0),2) cv2.imshow('img',img) cv2.waitKey(0) cv2.destroyAllWindows()

Литература:

1. Алгоритмы выделения контуров изображений // Хабрахабр. URL: https://habrahabr.ru/post/114452/
2. Canny Edge Detection // OpenCV. URL: https://docs.opencv.org/3.3.1/da/d22/tutorial_py_canny.html
3. The SUSAN Principle for Feature Detection // Oxford University. Wellcome Centre for Integrative Imaging. URL: https://users.fmrib.ox.ac.uk/~steve/susan/susan/node2.html
4. The SUSAN Edge Detector in Detail // Oxford University. Wellcome Centre for Integrative Imaging. URL: https://users.fmrib.ox.ac.uk/~steve/susan/susan/node6.html#SECTION00042000000000000000
5. Ансамблевый метод машинного обучения, основанный на рекомендации классификаторов // Бесплатная электронная библиотека — электронные матриалы. URL: http://lib.knigi-x.ru/23raznoe/212318–1-v-state-daetsya-kratkoe-vvedenie-ansambli-klassifikatorov-mashinnom-obuchenii-opisivaet.php
6. Метод Виолы—Джонса // Wikipedia. URL: https://ru.wikipedia.org/wiki/Метод_Виолы_—_Джонса
7. Интегральное представление изображений // Studfiles. URL: https://studfiles.net/preview/6234768/page:3/
8. AdaBoost в OpenCV // Recog.ru — Распознавание образов для программистов. URL: http://recog.ru/blog/opencv/page2/