О градиенте изображения

    Аннотация


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

    Введение


    Градиент — векторная величина, показывающая направление наискорейшего возрастания некоторой величины. В нашем случае «некоторая величина» — это двумерная функция яркости изображения, допустим что мы рассматриваем «псевдонепрерывное» изображение, тогда вектор градиента определяется формулой
    image
    где I – это наше изображение.
    На практике, картинка дискретна и в классическом смысле производной не существует, поэтому используют ее разностные аналоги, например в простейшем случае
    image
    — левая разностная производная. Разностных аналогов существует великое множество, и все они обладают различными порядками аппроксимации, подробнее здесь. Увеличение порядка аппроксимации, например как тут в теории должно приводить к увеличению точности расчета производной. Более того, увеличив количество элементов в аппроксимации можно повысить устойчивость к шуму.
    К примеру, будем использовать разностный аналог первой производной, шестого порядка точности аппроксимации по шагу дискретизации:
    image
    А теперь предположим, что I(i,j)независимые случайные величины, распределенные по любому закону распределению, и посмотрим дисперсии:
    1. Для первой аппроксимации получаем: image
    2. Для второй аппроксимации получаемimage

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

    Таким образом, коэффициент усиления шума (1.17), в случае аппроксимации производной разностью более высокого порядка, меньше чем коэффициент (2) в случае аппроксимации производной левой разностью. Логично, что при этом сильно возрастают вычислительные затраты. А теперь рисуночки:

    Рисунок 1Исходное изображение, 2модуль градиента по первой формуле, 3модуль градиента по второй формуле.
    image

    В итоге мы рассчитали градиент, на котором шумовая компонента увеличилась не в 2 раза а всего в 1.17 раз, однако опять же, если на картинке есть шум, то было бы неплохо его диспресию предварительно (до вычисления градиента) уменьшить – например, смазать исходное изображение I, то есть сделать свертку например с гауссовым ядром f. Тогда градиент запишется как:
    image
    однако, из свойств оператора свертки известна формула:
    image

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

    Таким образом, можно построить алгоритм «Смаз — Вычисление градиента»:
    1. Вычисляем разностные аналоги производных по ядру,
    2. Сворачиваем полученные ядра с изображением
    3. В итоге, получим компоненты вектора градиента.

    В вычислительном плане:
    Было: Одна свертка c окном (NxN) для смаза, + две свертки со специфическими окнами (1xN, Nx1) для вычисления производных.
    Стало: Две свертки со специфическими окнами (но уже NxN) для вычисления производных.
    Вычисление градиента смазанного изображения задача, которая очень часто встречается, например, в хитрых детекторах углов и контуров, о которых будет следующая статья.

    Что будет работать быстрее, а главное — устойчивее к шуму? Я предлагаю ответить на этот вопрос в комментариях к статье самим читателям.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 18

      +3
      Класс! Более здоровского описания выделения границ по критерию "(ясность / краткость) * ёмкость" я ещё не читал.
      Может, я делаю невнимательные/поспешные выводы, но мне кажется что тут оченвидно: чем больше порядок аппроксимации, тем больше устойчивость к шуму и тем больше требуется вычислительных мощностей. М?
        +1
        Спасибо. Утверждать не могу точно, хотя можно подумать и над формальных доказательством, дело в сумме квадратов коэффициентов маски с которой делается свертка. Именно это число и есть коэффициент усиления шума. Посмотрите как он высок для оператора Собеля (например из статьи Алгоритмы выделения контуров изображений), но там дело другое — там вторую производную аппроксимируют. Вот там тоже можно повышать порядок аппроксимации второй производной, что приведет к увеличению размеров маски и появлению совершенно нового оператора.
          +2
          Оператор Собеля тоже можно брать не 3x3, а произвольного размера. Он изначально определяется для любого размера ядра.
          0
          Важное наблюдение!
          А если использовать нелинейные фильтры, можно ли получить усиление шума 1.0 или даже его уменьшение? ;)
            0
            Нелинейные фильтры выделения контуров или поиска градиента или производных? — Не знаком с такими.
            Для подавления шума — лучше результаты действительно дают нелинейные фильтры.
              +2
              А какая разница? Возьмите нелинейный локальный фильтр шумоподавления, его суперпозиция с Вашим методом поиска производных даст в результате локальный нелинейный фильтр, который и ищет производные и давит шум.
              В принципе, Вы уже делаете примерно то же самое, только с помощью линейных шумодавов (неявным образом сидящих внутри Ваших длинных формул по вычислении производных). Можно показать, что длинная формула вычисления производных, которую Вы привели, это комбинация линейного low-pass фильтра и короткой формулы вычисления производных — в точности по двум пикселям. Поэтому у Вас и шум меньше получается. Так почему бы сразу не взять нелинейное ядро? Результат намного лучше получится.
                +2
                Я сейчас как будто послушал монолог вов-игрока с характерным лексиконом.
                Мощно!
              +1
              Знаете что мне не нравится? Вот это предложение:
              "Было: Одна свертка c окном (NxN) для смаза, + две свертки со специфическими окнами (1xN, Nx1) для вычисления производных."

              Почему у вас размер гауссова фильтра — N, и размер фильтра производной — тоже N? В общем случае, они же могут быть разными.
                0
                Согласен, косяк, Как правило они разные.
                  +1
                  Теперь второе: мне вот не кажется, что второй алгоритм будет работать быстрее. Если элементарно посчитать количество арифметических действий, то в первом случае будет меньше.
                    0
                    То есть второй алгоритм медленнее будет? — где две свертки с коном NxN?
                      +1
                      Именно так
                        0
                        Как я уже и говорил, эта статья — преамбула к еще одной статье, на этой неделе я ее опубликую и там обязательно отвечу на ваш комментарий. Ответ напишу как и в самой статье так ссылку вам на почту. Спасибо за интерес к статье.
                0
                > то было бы неплохо его диспресию предварительно (до вычисления градиента) уменьшить – например, смазать исходное изображение I, то есть сделать свертку например с гауссовым ядром f

                А медианный фильтр не лучше будет для шумоподавления? Конечно, зависит от характера шума…
                  0
                  Лучше, однако он нелинейный, и не получится факторизовать задачу СМАЗ-ГРАДИЕНТ. А смысл именно в этом. Раз уж речь зашла о нелинейных фильтрах надо бы одно ноухау опубликовать.
                  +2
                  Как то вы очень смело «смешиваете» дисперсию градиента картинки с дисперсией аддитивного шума. Хоть шум и не коррелирует между соседними пикселами, сам градиент очень даже коррелирует.

                  Более того, на вашей проверочной картинке градиент сам по себе шумоподобен (на текстурах где листва). И зачем же его денойзить если он и так хреновый?

                    0
                    Дело в том, что данные выкладки верны когда изображение суть шум — предельный случай, и ориентируясь на него можно как-то сравнивать операторы выделения контуров — на самом деле классическая практика. А картинка была выбрана только по той причине что на ней есть знак — а именно распознаванием дорожных знаков я и занимаюсь сейчас. По поводу листвы — она шумоподобна, согласен, но в этом и суть! Что в одном случае этот шум в 2 раза увеличивается а в другом не так сильно. О корреляции градиента да и вообще о корреляции я не говорил — речь лишь о предположении изотропности шума по картинке.
                      0
                      Пардон, про ковариацию…
                      говорили когда дисперсию суммы разложили на сумму дисперсий :)

                      Дорожные знаки? Любопытно. Напишете про них?

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

                  Самое читаемое