Jaesang Park and James M.Keller, Fellow, IEEE
Перевод с английского
(выполнила магистр ДонНТУ Вовк Е. Л.)
Источник:http://computer.org/publications/dlib
Краткий обзор
В этой статье мы представляем новый подход для обнаружения границы объекта, называемый водяная змейка. Это такой алгоритм змейки, состоящий из двух шагов, при котором энергия функционала минимизируется с помощью динамического метода программирования. В большей степени это трудоемко для случая локального минимума, так как решение находится за счет исследования энергии всей области. Чтобы снизить сложность процесса минимизации используется метод трансформации на так называемом водоразделе, и метод приближения. Этот новый подход сравним со стандартными методами для получения точности комплексных переменных и применим для сегментации изображений белых кровяных клеток костного мозга.
1.Введение
Модели активных контуров, за последние годы привлекли достаточно внимания. Эти модели, также известные как змейки, используются во множестве приложений, особенно для выявления границ объекта. Согласно этим моделям, активные контура – это параметрические кривые. Общая энергия представлена суммой внешней и внутренней энергии контура.
Используется подход вариационных исчислений для минимизации функционала. За счет уравновешивания частей энергии, используя параметры регуляризации, метод змеек может зачастую отлично выявить границы объекта в изображениях с наличием шумов, причем без каких-либо пробелов и фиктивных ответвлений (ложных контуров).
Хотя данный пример модели активных контуров все еще эффективен, найдено много проблем, связанных с минимизацией. Выявлено, что вариационные подходы имеют проблемы касательно оптимальности, численной стабильности, сходимости и применении грубых округлений. Для преодоления этих проблем был предложен альтернативный метод, так называемое дискретное динамическое программирование. Этот метод ищет минимум энергии функционала не за счет средних значений производных, а за счет более эффективной техники исследования. Однако, расчеты намного тяжелее, чем при вариационном подходе.
На самом деле то, что все популярные алгоритмы ищут минимум многократно, в принципе, бесполезно. В основном процессе, все зависит от результата поиска локального минимума, потому что процесс оптимизации прекращается при достижении локального минимума. В данной статье предлагается подход, названный «водные змейки», который совмещает динамическое программирование и перемещения на «водоразделе». Он обеспечивает решение нахождения глобального минимума без многократных итераций, и в то же время сложностью процесса минимизации можно вполне легко контролировать.
2.Змейки на водоразделе
2.1 Проблема локального минимума
Итеративные алгоритмы змеек зачастую имеют трудности, связанные с локальным минимумом, так как гибкость энергии функционала на изображении не гарантирована. Чтобы достигнуть общий минимум, при этом избегая нахождения локального, нужно учесть весь набор возможных кривых, и при этом очень быстро выбрать наиболее подходящую. Однако, как правило, число всех возможных имеющихся кривых для объекта на изображении очень велико для быстрого выбора. Оптимальный выход для того, чтобы ускорить процесс минимизации, это исключить ненужные кривые, не упуская важные для нас. Вполне очевидно, что это маловероятно. Наилучший выход – это устранить больше кривых. Трансформация на водоразделе предлагает эффективный способ определения таких нужных и ненужных кривых.
2.2 Определение границы за счет перемещения на водоразделе
Из-за наличия шумов в изображении, разделение водораздела приводит к чрезмерной сегментации. Однако, линии водораздела включают наиболее важные границы объекта. Во избежание пересегментации, алгоритм был модифицирован. В течении процесса, основной алгоритм всегда отмечает вновь выбранный минимум. Это приводит к чрезмерной пересегментации в шумных изображениях. В модифицированном алгоритме, если вновь выбранная область недостаточно велика, чтобы быть, так сказать отдельным отрывком, точки в данной области не отмечаются, и процесс переходит к следующему этапу. Эта модификация не гарантирует. Что у каждого (выделенного) объекта будет своя собственная область. Однако, объект делится уже на меньшее количество частей. Примерный размер следует ориентировать на средний размер незначительных структур, для того, чтобы найти отдельные области на изображении. Следует отметить, что число отдельных областей значительно уменьшается по мере увеличения размера минимального размера области.
2.3 Зона змейки
В большинстве случаев, изображения содержат больше, чем только один интересующий нас объект. Т. о., нам нужно найти несколько решений путем запуска нескольких змеек в изображение. Змейки могут касаться друг друга, но полное перекрывание нежелательно. Это означает, что каждой змейке необходима своя собственная территория для нахождения решения. Достаточная зона для каждой змейки поможет процессу минимизации и снизит временные затраты на вычисление, т. к. обычно эта зона меньше, чем вся область изображения. Определяем мы зону за счет передвижения каждой точки исходной змейки по оси, которая нормальна к ее касательной. Расстояние, на которое мы сдвигаем, должно быть достаточно велико, чтобы захватить границу объекта в зону змейки.
2.4 «Грубо-точная» стратегия
Точки на водоразделе в зоне змейки – это предполагаемые точки настоящей границы объекта. Однако, число точек поиска для каждой точки змейки все еще достаточно велико, чтобы справиться за один раз, поэтому предлагается «грубо - точная» стратегия для нахождения решения. Для нахождения удачного решения используются два последовательных процесса минимизации.
Предположим, что мы хотим представить границу объекта с помощью n – точек змейки и у нас есть зона змейки, определенная внутренней и внешней кривыми. Рисуем прямую li, которая проходит через точку змейки vi, в направлении перпендикулярной к ее касательной. m точек линии l, которые пересекаются линиями водораздела в зоне змейки – это блуждающие состояния для точки змейки v. Типичное значение количества точек между 6 и 30 в нашем эксперименте. Теперь, грубый процесс минимизации выбирает множество точек среди общего количества блуждающих мест расположения на прямой l, с помощью динамического программирования. Так как мы используем минимальное множество точек в зоне, полученный в результате конечный контур может быть не достаточно четким. Некоторые точки находятся на большем расстоянии друг от друга, чем другие из-за грубого округления. Однако, все точки змейки расположены возле настоящей границы объекта. Просто нам необходимо слегка переставить эти точки, чтобы представить контур более четко. Мы берем более специфичную зону, снова используя результаты предыдущего шага. Определена новая зона змейки. Теперь эта зона разделена на n – эквидистантных частей. Наконец, удачный процесс минимизации посредством динамического программирования выбирает то множество точек змейки среди общего количества блуждающих точек (точек водораздела), в соответствующих эквидистантных частях.
.....
3. Заключение
Был предложен новый подход в определении границ объекта. Наш подход имеет 3 достоинства. 1) хотя и вычисляется вся энергия, вычисления весьма доступны и управляемы за счет трансформации водораздела и «грубо-точного подхода»; 2) можно избежать локального минимума, так как процесс минимизации находит глобальный минимум за счет вычисления общей энергии внутри зоны змейки; 3) точная исходная змейка совсем не обязательна, так как алгоритм рационально обрабатывает все подходящие точки в зоне змейки. Алгоритм был протестирован на комплексных изображениях и изображениях костного мозга. Результаты теста показывают, что метод эффективен и устойчив к проблемам локального минимума.
References