Monday, March 14, 2011

Поиск границ на цветных изображениях

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

Пример реализации этого алгоритма на Java тоже не сложно найти.
Но, у этой реализации есть одна большая проблема. Она состоит в том, что если исходное изображение цветное, то прежде чем детектировать границы приходится тем или иным способом свести его к монохромному. Обычно для этого выделяется яркость изображения. Естественно, что часть информации при таком преобразовании теряется.
Вот, например, для такой картинки стандартный детектор Канни вообще ничего не детектирует (слева исходное изображение, справа границы обнаруженные детектором)




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

Потому и пришлось искать способ модифицировать детектор границ Канни для цветного изображения. И такой способ нашелся

От классической реализации алгоритма Канни этот алгоритм отличается лишь способом определения градиентов, с чего и начнем.

С точки зрения математики цветное изображение это просто некоторое отображение, преобразующее координаты точки (x,y) в набор цветов (r, g, b). Для такого отображения можно написать матрицу Якоби:
| dr/dx  dr/dy |
J = | dg/dx  dg/dy |
    | db/dx  db/dy |
В каждой точке изображения мы хотим определить, в каком направлении изменяются цвета и какова величина этого изменения. Якобиан, будучи обобщением понятия градиента, как раз и дает нам ответ на этот вопрос. Для того, чтобы узнать, в каком направлении изображение претерпевает наибольшее изменение, нам нужно найти собственные векторы матрицы Jt*J. Собственный вектор соответствующий максимальному собственному значению укажет нам это направление. Причем, максимальное собственное значение является квадратом искомой амплитуды изменения.

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

Возьмем исходное изображение




1)На первом шаге производится сглаживание шумов. В моей реализации, для этого применятся Гаусовый фильтр.




2) Производится поиск градиентов на сглаженном изображении. Этот шаг я описал выше.




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




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




Всё. Полную реализацию этого алгоритма на Java я выложил сюда, комментарии welcome.

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



Намного лучше, неправда ли?

7 comments:

  1. Спасибо, очень познавательно!

    ReplyDelete
  2. Пожалуйста! Очень приятно.

    ReplyDelete
  3. Класс! Правда для меня больше интересна вторая часть работы по распознаванию образов

    ReplyDelete
  4. Вау! Это действительно очень круто! Спасибо!

    ReplyDelete
  5. Ооочень круто, а кто-то пытался реализовать распознавание объектов в реальном времени на этой основе? Есть толковы наработки?

    ReplyDelete
  6. Можно взять код в Матлабе?

    ReplyDelete