Обнаружение пятен

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

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

Учитывая некоторое свойство интереса, выраженное как функция положения на изображении, существует два основных класса детекторов пятен: (i)  дифференциальные методы , которые основаны на производных функции относительно положения, и (ii)  методы, основанные на локальных экстремумах , которые основаны на нахождении локальных максимумов и минимумов функции. С более новой терминологией, используемой в этой области, эти детекторы также могут называться операторами точек интереса или, альтернативно, операторами областей интереса (см. также обнаружение точек интереса и обнаружение углов ).

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

Один из первых и наиболее распространенных детекторов пятен основан на Лапласиане Гаусса ( LoG ). При наличии входного изображения это изображение сворачивается с помощью ядра Гаусса${\displaystyle f(x,y)}$

${\displaystyle g(x,y,t)={\frac {1}{2\pi t}}e^{-{\frac {x^{2}+y^{2}}{2t}}}}$

в определенном масштабе, чтобы дать представление масштабного пространства . Затем, результат применения оператора Лапласа${\displaystyle т}$ ${\displaystyle L(x,y;t)\ =g(x,y,t)*f(x,y)}$

${\displaystyle \nabla ^{2}L=L_{xx}+L_{yy}}$

вычисляется, что обычно приводит к сильным положительным откликам для темных пятен радиуса (для двумерного изображения, для -мерного изображения) и сильным отрицательным откликам для ярких пятен аналогичного размера. Однако основная проблема при применении этого оператора в одном масштабе заключается в том, что отклик оператора сильно зависит от соотношения между размером структур пятен в области изображения и размером гауссовского ядра, используемого для предварительного сглаживания. Для автоматического захвата пятен разного (неизвестного) размера в области изображения необходим многомасштабный подход.${\textstyle r^{2}=2t}$${\textstyle r^{2}=dt}$${\textstyle д}$

Простой способ получить многомасштабный детектор пятен с автоматическим выбором масштаба — рассмотреть нормализованный по масштабу оператор Лапласа

${\displaystyle \nabla _ {\mathrm {norm} }^{2}L=t\,(L_{xx}+L_{yy})}$

и для обнаружения масштабно-пространственных максимумов/минимумов , которые являются точками, которые одновременно являются локальными максимумами/минимумами по отношению как к пространству, так и к масштабу${\displaystyle \nabla _ {\mathrm {норма} }^{2}L}$ (Lindeberg 1994, 1998). Таким образом, учитывая дискретное двумерное входное изображение, вычисляется трехмерный дискретный масштабно-пространственный объем , и точка рассматривается как яркое (темное) пятно, если значение в этой точке больше (меньше), чем значение во всех ее 26 соседях. Таким образом, одновременный выбор точек интереса и масштабов выполняется в соответствии с${\displaystyle f(x,y)}$${\displaystyle L(x,y,t)}$${\displaystyle ({\hat {x}},{\hat {y}})}$${\displaystyle {\шляпа {т}}}$

${\displaystyle ({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argmaxminlocal} _{(x,y;t)}((\nabla _{\mathrm {norm} }^{2}L)(x,y;t))}$.

Обратите внимание, что это понятие блоба дает краткое и математически точное рабочее определение понятия «блоба», что напрямую приводит к эффективному и надежному алгоритму обнаружения блоба. Некоторые основные свойства блоба, определяемые из масштабно-пространственных максимумов нормализованного оператора Лапласа, заключаются в том, что отклики ковариантны с переносами, поворотами и изменениями масштаба в области изображения. Таким образом, если в точке предполагается масштабно-пространственный максимум, то при изменении масштаба изображения на масштабный коэффициент будет наблюдаться масштабно-пространственный максимум в в измененном масштабе изображения (Lindeberg 1998). Это на практике весьма полезное свойство подразумевает, что помимо специфической темы обнаружения пятен Лапласа, локальные максимумы/минимумы масштабно-нормализованного Лапласа также используются для выбора масштаба в других контекстах , например, при обнаружении углов , масштабно-адаптивном отслеживании признаков (Bretzner и Lindeberg, 1998), в масштабно-инвариантном преобразовании признаков (Lowe, 2004), а также в других дескрипторах изображений для сопоставления изображений и распознавания объектов .${\displaystyle (x_{0},y_{0};t_{0})}$${\displaystyle s}$${\displaystyle \left(sx_{0},sy_{0};s^{2}t_{0}\right)}$

Свойства выбора масштаба оператора Лапласа и других детекторов точек интереса в близком масштабном пространстве подробно анализируются в (Lindeberg 2013a). ^[1] В (Lindeberg 2013b, 2015) ^{[2] [3]} показано, что существуют другие детекторы точек интереса в масштабном пространстве, такие как определитель оператора Гессе, которые работают лучше, чем оператор Лапласа или его аппроксимация разностью гауссианов для сопоставления на основе изображений с использованием локальных дескрипторов изображений, подобных SIFT.

Из того факта, что представление масштабного пространства удовлетворяет уравнению диффузии${\displaystyle L(x,y,t)}$

${\displaystyle \partial _{t}L={\frac {1}{2}}\nabla ^{2}L}$

отсюда следует, что Лапласиан гауссовского оператора также может быть вычислен как предельный случай разности между двумя гауссовыми сглаженными изображениями ( представления масштабного пространства )${\displaystyle \nabla ^{2}L(x,y,t)}$

${\displaystyle \nabla _{\mathrm {norm} }^{2}L(x,y;t)\approx {\frac {t}{\Delta t}}\left(L(x,y;t+\Delta t)-L(x,y;t)\right)}$.

В литературе по компьютерному зрению этот подход называется подходом разности гауссианов (DoG). Однако, помимо незначительных технических деталей, этот оператор по сути похож на лапласиан и может рассматриваться как приближение оператора Лапласа. Аналогично детектору пятен Лапласа, пятна могут быть обнаружены из масштабно-пространственных экстремумов разностей гауссианов — см. (Lindeberg 2012, 2015) ^{[3] [4]} для явной связи между оператором разности гауссиан и масштабно-нормализованным оператором Лапласа. Этот подход, например, используется в алгоритме масштабно-инвариантного преобразования признаков (SIFT) — см. Lowe (2004).

Рассматривая нормализованный по масштабу определитель гессиана, также называемый оператором Монжа-Ампера ,

${\displaystyle \det H_{\mathrm {norm} }L=t^{2}\left(L_{xx}L_{yy}-L_{xy}^{2}\right)}$

где обозначает матрицу Гессе масштабно-пространственного представления , а затем, обнаруживая масштабно-пространственные максимумы этого оператора, получаем еще один простой дифференциальный детектор пятен с автоматическим выбором масштаба, который также реагирует на седла (Линдеберг 1994, 1998)${\displaystyle HL}$${\displaystyle L}$

${\displaystyle ({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argmaxlocal} _{(x,y;t)}((\det H_{\mathrm {norm} }L)(x,y;t))}$.

Точки и масштабы пятен также определяются из операционных дифференциальных геометрических определений, что приводит к дескрипторам пятен, которые ковариантны с переносами, поворотами и изменениями масштаба в области изображения. С точки зрения выбора масштаба, пятна, определенные из экстремумов масштабного пространства определителя гессиана (DoH), также имеют немного лучшие свойства выбора масштаба при неевклидовых аффинных преобразованиях, чем более часто используемый оператор Лапласа (Lindeberg 1994, 1998, 2015). ^[3] В упрощенной форме нормализованный по масштабу определитель гессиана, вычисленный из вейвлетов Хаара, используется в качестве базового оператора точки интереса в дескрипторе SURF (Bay et al. 2006) для сопоставления изображений и распознавания объектов.${\displaystyle ({\hat {x}},{\hat {y}})}$${\displaystyle {\hat {t}}}$

Подробный анализ свойств выбора определителя оператора Гессе и других детекторов точек интереса в близком масштабном пространстве приведен в (Lindeberg 2013a) ^[1], показывающий, что определитель оператора Гессе имеет лучшие свойства выбора масштаба при аффинных преобразованиях изображений, чем оператор Лапласа. В (Lindeberg 2013b, 2015) ^{[2] [3]} показано, что определитель оператора Гессе работает значительно лучше, чем оператор Лапласа или его аппроксимация разностью гауссианов, а также лучше, чем операторы Харриса или Харриса-Лапласа, для сопоставления на основе изображений с использованием локальных дескрипторов изображений типа SIFT или SURF, что приводит к более высоким значениям эффективности и более низким оценкам точности 1.

Также был предложен гибридный оператор между лапласианом и определителем гессианских детекторов пятен, где пространственный выбор выполняется определителем гессиана, а выбор масштаба выполняется с помощью масштабно-нормализованного лапласиана (Миколайчик и Шмид, 2004):

${\displaystyle ({\hat {x}},{\hat {y}})=\operatorname {argmaxlocal} _{(x,y)}((\det HL)(x,y;t))}$

${\displaystyle {\hat {t}}=\operatorname {argmaxminlocal} _{t}((\nabla _{\mathrm {norm} }^{2}L)({\hat {x}},{\hat {y}};t))}$

Этот оператор использовался для сопоставления изображений, распознавания объектов, а также анализа текстур.

Дескрипторы пятен, полученные из этих детекторов пятен с автоматическим выбором масштаба, инвариантны к перемещениям, поворотам и равномерному масштабированию в пространственной области. Однако изображения, которые составляют входные данные для системы компьютерного зрения, также подвержены искажениям перспективы. Чтобы получить дескрипторы пятен, которые более устойчивы к преобразованиям перспективы, естественным подходом является разработка детектора пятен, который инвариантен к аффинным преобразованиям . На практике аффинно-инвариантные точки интереса могут быть получены путем применения аффинной адаптации формы к дескриптору пятна, где форма сглаживающего ядра итеративно деформируется для соответствия локальной структуре изображения вокруг пятна, или, что эквивалентно, локальный участок изображения итеративно деформируется, в то время как форма сглаживающего ядра остается вращательно-симметричной (Lindeberg and Garding 1997; Baumberg 2000; Mikolajczyk and Schmid 2004, Lindeberg 2008). Таким образом, мы можем определить аффинно-адаптированные версии оператора Лапласа/разности Гаусса, определителя гессиана и оператора Гессе-Лапласа (см. также Харрисово-аффинный и Гессено-аффинный ).

Определитель оператора Гессе был расширен на совместное пространство-время Виллемсом и др. ^[5] и Линдебергом ^[6], что привело к следующему масштабно-нормализованному дифференциальному выражению:

${\displaystyle \det(H_{(x,y,t),\mathrm {norm} }L)=s^{2\gamma _{s}}\tau ^{\gamma _{\tau }}\left(L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt}^{2}-L_{tt}L_{xy}^{2}\right).}$

В работе Виллемса и др. ^[5] было использовано более простое выражение, соответствующее и . В работе Линдеберга ^[6] было показано, что и подразумевает лучшие свойства выбора масштаба в том смысле, что выбранные уровни масштаба, полученные из пространственно-временного гауссовского пятна с пространственной протяженностью и временной протяженностью, будут идеально соответствовать пространственной протяженности и временной продолжительности пятна, при этом выбор масштаба выполняется путем обнаружения пространственно-временных экстремумов масштабного пространства дифференциального выражения.${\displaystyle \gamma _{s}=1}$${\displaystyle \gamma _{\tau }=1}$${\displaystyle \gamma _{s}=5/4}$${\displaystyle \gamma _{\tau }=5/4}$${\displaystyle s=s_{0}}$${\displaystyle \tau =\tau _{0}}$

Оператор Лапласа был расширен на пространственно-временные видеоданные Линдебергом ^[6], что привело к следующим двум пространственно-временным операторам, которые также представляют собой модели рецептивных полей не запаздывающих и запаздывающих нейронов в LGN:

${\displaystyle \partial _{t,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }/2}(L_{xxt}+L_{yyt}),}$

${\displaystyle \partial _{tt,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }}(L_{xxtt}+L_{yytt}).}$

Для первого оператора свойства выбора шкалы требуют использования и , если мы хотим, чтобы этот оператор принял свое максимальное значение по пространственно-временным шкалам на уровне пространственно-временного масштаба, отражающем пространственную протяженность и временную длительность мигающего гауссова пятна. Для второго оператора свойства выбора шкалы требуют использования и , если мы хотим, чтобы этот оператор принял свое максимальное значение по пространственно-временным шкалам на уровне пространственно-временного масштаба, отражающем пространственную протяженность и временную длительность мигающего гауссова пятна.${\displaystyle \gamma _{s}=1}$${\displaystyle \gamma _{\tau }=1/2}$${\displaystyle \gamma _{s}=1}$${\displaystyle \gamma _{\tau }=3/4}$

Естественный подход к обнаружению пятен заключается в том, чтобы связать яркое (темное) пятно с каждым локальным максимумом (минимумом) в ландшафте интенсивности. Однако основная проблема такого подхода заключается в том, что локальные экстремумы очень чувствительны к шуму. Чтобы решить эту проблему, Линдеберг (1993, 1994) изучил проблему обнаружения локальных максимумов с протяженностью в нескольких масштабах в масштабном пространстве . Регион с пространственной протяженностью, определенной по аналогии с водоразделом, был связан с каждым локальным максимумом, а также локальным контрастом, определенным по так называемой ограничивающей седловой точке. Локальный экстремум с протяженностью, определенной таким образом, назывался серым пятном . Более того, продолжая аналогию с водоразделом за пределами ограничивающей седловой точки, было определено дерево серых пятен для захвата вложенной топологической структуры множеств уровней в ландшафте интенсивности способом, который инвариантен к аффинным деформациям в области изображения и монотонным преобразованиям интенсивности. Изучая, как эти структуры развиваются с увеличением масштабов, было введено понятие пятен масштабного пространства . Помимо локального контраста и протяженности, эти пятна масштабного пространства также измеряли, насколько стабильны структуры изображения в масштабном пространстве, измеряя их время жизни в масштабном пространстве .

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

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

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

1. Если у региона нет соседа выше, то это локальный максимум, и он будет семенем блоба. Установите флаг, который позволяет блобу расти.
2. В противном случае, если у него есть хотя бы один сосед более высокого уровня, который является фоном, то он не может быть частью какого-либо пятна и должен быть фоном.
3. В противном случае, если у него есть более одного соседа вышестоящего уровня и если эти соседи вышестоящего уровня являются частями разных блобов, то он не может быть частью какого-либо блоба и должен быть фоном. Если любому из соседей вышестоящего уровня все еще разрешено расти, снимите с него флаг, который позволяет ему расти.
4. В противном случае у него есть один или несколько более высоких соседей, которые все являются частями одного и того же блоба. Если этому блобу все еще разрешено расти, то текущая область должна быть включена как часть этого блоба. В противном случае область должна быть установлена ​​в фоновом режиме.

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

Этот алгоритм с его приложениями в компьютерном зрении более подробно описан в диссертации Линдеберга ^[7] , а также в монографии по теории масштабного пространства ^[8], частично основанной на этой работе. Более ранние презентации этого алгоритма можно также найти в . ^{[9] [10]} Более подробные описания приложений обнаружения пятен серого уровня и первичного эскиза масштабного пространства для компьютерного зрения и анализа медицинских изображений приведены в . ^{[11] [12] [13]}

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

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

• Извлечение капель
• Обнаружение угла
• Аффинная адаптация формы
• Масштаб пространства
• Обнаружение хребта
• Обнаружение точек интереса
• Обнаружение признаков (компьютерное зрение)
• Детектор аффинной области Харриса
• Детектор аффинной области Гессе
• ПЦБР

• H. Bay; T. Tuytelaars & L. van Gool (2006). "SURF: ускоренные надежные функции". Труды 9-й Европейской конференции по компьютерному зрению, Springer LNCS том 3951, часть 1. стр.  404–417 .
• Л. Бретцнер и Т. Линдеберг (1998). «Отслеживание признаков с автоматическим выбором пространственных масштабов» (страница с аннотацией) . Компьютерное зрение и понимание изображений . 71 (3): 385–392 . doi :10.1006/cviu.1998.0650.
• T. Lindeberg (1993). «Обнаружение заметных пятнообразных структур изображения и их масштабов с помощью первичного эскиза масштабного пространства: метод фокусировки внимания» (страница с аннотацией) . International Journal of Computer Vision . 11 (3): 283– 318. doi :10.1007/BF01469346. S2CID  11998035.
• T. Lindeberg (1994). Теория масштабного пространства в компьютерном зрении. Springer. ISBN 978-0-7923-9418-1.
• T. Lindeberg (1998). "Обнаружение признаков с автоматическим выбором масштаба" (страница с аннотацией) . International Journal of Computer Vision . 30 (2): 77– 116. doi :10.1023/A:1008045108935. S2CID  723210.
• Линдеберг, Т.; Гардинг, Дж. (1997). «Сглаживание, адаптированное к форме, при оценке 3-{D} глубинных сигналов из аффинных искажений локальной 2-{D} структуры». Image and Vision Computing . 15 (6): 415– 434. doi :10.1016/S0262-8856(97)01144-X.
• Линдеберг, Т. (2008). «Масштабное пространство». В Ва, Бенджамин (ред.). Энциклопедия компьютерной науки и техники. Том IV. John Wiley and Sons. стр.  2495–2504 . doi :10.1002/9780470050118.ecse609. ISBN 978-0-470-05011-8.
• DG Lowe (2004). «Отличительные особенности изображения по масштабно-инвариантным ключевым точкам». Международный журнал компьютерного зрения . 60 (2): 91– 110. CiteSeerX  10.1.1.73.2924 . doi :10.1023/B:VISI.0000029664.99615.94. S2CID  221242327.
• J. Matas; O. Chum; M. Urban & T. Pajdla (2002). "Надежное широкое базовое стерео из максимально стабильных экстремальных областей" (PDF) . British Machine Vision Conference . стр.  384–393 .
• K. Mikolajczyk; C. Schmid (2004). "Масштабные и аффинно-инвариантные детекторы точек интереса" (PDF) . International Journal of Computer Vision . 60 (1): 63– 86. doi :10.1023/B:VISI.0000027790.02288.f2. S2CID  1704741.