Выделение границ

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

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

• изменения глубины;
• изменения ориентации поверхностей;
• изменения в свойствах материала;
• различие в освещении сцены.

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

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

Обычной границей может быть, например, граница между блоками красного и жёлтого цвета. С другой стороны, линия может быть набором пикселей отличающегося цвета на постоянном фоне. Поэтому у линии может быть по границе с каждой стороны от неё.

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

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

• Фокусное размытие из-за конечной глубины резкости съемки,
• Размытая полутень от неточечных источников света,
• Затенение гладких объектов,

и поэтому многие исследователи используют ступенчатый край, сглаженный функцией Гаусса (функция ошибки), в качестве простейшего приближения модели идеального края для моделирования размытых границ в прикладных задачах. Таким образом, одномерное изображение ${\displaystyle f}$, которое имеет строго один край в точке ${\displaystyle x=0}$, может быть смоделирована как:

${\displaystyle f(x)={\frac {I_{r}-I_{l}}{2}}\left(\operatorname {erf} \left({\frac {x}{{\sqrt {2}}\sigma }}\right)+1\right)+I_{l}.}$

Здесь

${\displaystyle \operatorname {erf} \,\left(u\right)={\frac {2}{\sqrt {\pi }}}\int \limits _{0}^{u}e^{-t^{2}}\,dt}$.

Слева от границы яркость ${\displaystyle I_{l}=\lim _{x\rightarrow -\infty }f(x)}$, справа — ${\displaystyle I_{r}=\lim _{x\rightarrow \infty }f(x)}$. Параметр ${\displaystyle \sigma }$ называется размером размытия границы.

Чтобы проиллюстрировать, почему выделение границ — нетривиальная задача, рассмотрим задачу выделения границы на следующем одномерном сигнале. Здесь мы можем сразу интуитивно сказать, что граница должна быть между 4-м и 5-м пикселем.

Если бы изменение яркости между 4-м и 5-м пикселем было меньше, а изменение яркости между их соседями было больше, уже не так просто было бы сказать, что граница должна быть именно в этом месте. Кроме того, кто-нибудь мог бы заявить, что здесь вообще должно быть несколько границ.

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

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

Опубликованные методы выделения границ отличаются применяемыми фильтрами сглаживания и способами, как считается сила края. Хотя многие методы выделения границ основываются на вычислении градиента изображения, они отличаются типами фильтров, применяемых для вычисления градиентов в x- и y-направлении.

Джон Кэнни^[англ.] изучил математическую проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Он показал, что искомый фильтр является суммой четырёх экспонент. Он также показал, что этот фильтр может быть хорошо приближен первой производной гауссианы. Кэнни ввел понятие Non-Maximum Suppression (подавление не-максимумов), которое означает, что пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента.

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

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

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

${\displaystyle L_{x}(x,y)=-1/2\cdot L(x-1,y)+0\cdot L(x,y)+1/2\cdot L(x+1,y).}$

${\displaystyle L_{y}(x,y)=-1/2\cdot L(x,y-1)+0\cdot L(x,y)+1/2\cdot L(x,y+1).}$

соответствующие применению следующих фильтров к изображению:

${\displaystyle L_{x}={\begin{bmatrix}-1/2&0&1/2\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{y}={\begin{bmatrix}+1/2\\0\\-1/2\end{bmatrix}}*L}$

Хорошо известный оператор Собеля основывается на следующих фильтрах:

${\displaystyle L_{x}={\begin{bmatrix}-1&0&+1\\-2&0&+2\\-1&0&+1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{y}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}*L}$

Получив такие оценки, мы можем вычислить величину градиента следующим образом:

${\displaystyle |\nabla L|={\sqrt {L_{x}^{2}+L_{y}^{2}}}}$

а направление градиента вычисляется так:

${\displaystyle \theta =\operatorname {atan2} (L_{y},L_{x})}$

Другие операторы для вычисления градиента изображения были предложены Джудит Прюитт (Judith Prewitt) и Лоуренсом Робертсом (Lawrence Roberts) и известны как оператор Прюитт и перекрёстный оператор Робертса, соответственно.

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

Если порог применяется просто к изображению величины градиента, полученные границы будут толстыми и потребуется некоторая постобработка, делающая край тонким и точным. Если же выделить границы с помощью Non-Maximum Suppression, границы будут тонкими по определению и их можно будет соединить в полигоны процедурой соединения краев (прослеживания границы). На дискретной сетке этап подавления немаксимумов может быть реализован с помощью оценки направления градиента, используя первые производные, округление направления на значения с шагом 45 градусов и, наконец, сравнении значений градиента в полученном направлении градиента.

Традиционным подходом к решению проблемы нахождения подходящего порога являются пороги «с запозданием». Метод использует несколько порогов. Мы используем верхний порог, чтобы найти точку начала границы. После того, как мы получили стартовую точку, мы отслеживаем границу, точка за точкой, пока значение силы края выше нижнего порога. Этот алгоритм подразумевает, что границы — это скорее всего непрерывные кривые, и позволяет нам прослеживать слабые участки границ без допущения того, что все шумные точки на изображении будут помечены как края. Однако, все ещё имеет место проблема выбора подходящих значений порогов для этого метода, так как оптимальные параметры могут меняться от изображения к изображению.

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

Плюсы:

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

Существует много популярных методов для решения этой задачи. Один из них описан далее:

1. Выбрать тип связности: 8, 6 или 4
   • Предпочтительна 8-связность, при которой рассматриваются все пиксели, непосредственно окружающие текущий пиксель
2. Удалить точки сверху, снизу, слева и справа от точки
   • Делать это следует в несколько проходов, то есть сначала удалить точки в одном направлении, затем на обработанном изображении удалить точки на другом.
   • Точка удаляется в следующем случае:
     1. У этой точки нет соседей сверху (в случае обработки «верхнего» направления, иначе — в соответствующем направлении)
     2. Эта точка не является концом линии
     3. Удаление этой точки никак не повлияет на связанность её соседей
     4. ИЛИ это изолированная точка
   • Иначе, точка не удаляется
3. Предыдущий шаг можно повторять несколько раз, в зависимости от желаемого уровня «аккуратности» границы.

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

Оператор Марра-Хилдрет основан на вычисления корней оператора Лапласа, примененного к изображению, сглаженному фильтром Гаусса. Однако, было показано, что этот оператор выделяет ложные границы на однородных участках изображения, где градиент имеет локальный минимум. К тому же этот оператор плохо локализовывал скругленные края. Поэтому данный оператор представляет сейчас скорее историческую ценность.

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

Введем в каждой точке изображения локальную систему координат ${\displaystyle (u,v)}$, где ${\displaystyle v}$-направление параллельно градиенту. Предполагая, что изображение было сглажено фильтром Гаусса, и масштабного представление ${\displaystyle L(x,y;t)}$ на масштабе ${\displaystyle t}$ было посчитано, мы можем потребовать, чтобы величина градиента масштабного представления, которое равно первой производной по направлению ${\displaystyle L_{v}}$ в ${\displaystyle v}$-направлении, будет иметь первую производную в ${\displaystyle v}$-направлении, равную нулю

${\displaystyle \partial _{v}(L_{v})=0}$,

в то время как вторая производная в ${\displaystyle v}$-направлении от ${\displaystyle L_{v}}$ должна быть отрицательной, так как на интересуют только максимумы, то есть:

${\displaystyle \partial _{vv}(L_{v})\leq 0}$.

Записанное в качестве явного выражения от локальных частных производных ${\displaystyle L_{x}}$, ${\displaystyle L_{y}}$ … ${\displaystyle L_{yyy}}$, данное определение края может быть выражено в качестве нулевых линий дифференциального инварианта

${\displaystyle L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy}+L_{y}^{2}\,L_{yy}=0,}$

который удовлетворяет следующему условию:

${\displaystyle L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0}$

где ${\displaystyle L_{x}}$, ${\displaystyle L_{y}}$ … ${\displaystyle L_{yyy}}$ обозначают частные производные посчитанные на масштабном представлении ${\displaystyle L}$, полученном с помощью фильтрации исходного изображения фильтром Гаусса.

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

На практике, первые производные могут быть посчитаны так, как описывалось ранее, в то время как вторые производные могут быть вычислены из масштабного представления ${\displaystyle L}$ так:

${\displaystyle L_{xx}(x,y)=L(x-1,y)-2L(x,y)+L(x+1,y).}$

${\displaystyle L_{xy}(x,y)=(L(x-1,y-1)-L(x-1,y+1)-L(x+1,y-1)+L(x+1,y+1))/4,}$

${\displaystyle L_{yy}(x,y)=L(x,y-1)-2L(x,y)+L(x,y+1).}$

соответствуя следующим операторам:

${\displaystyle L_{xx}={\begin{bmatrix}1&-2&1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{xy}={\begin{bmatrix}-1/4&0&1/4\\0&0&0\\1/4&0&-1/4\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{yy}={\begin{bmatrix}1\\-2\\1\end{bmatrix}}*L}$

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

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

• JOHN CANNY, A Computational Approach to Edge Detection
• детектор границ Кенни в OpenCV

• Цифровая обработка изображений
• Компьютерное зрение