При обработке изображение зачастую рассматривается не как однородная сцена, а как совокупность объектов переднего плана и фона изображения [4]. Вобщем случае при работе с тем или иным изображением часто возникает необходимость отделить одну, значимую для пользователя часть, которая интересует его в данный момент (объект), от всего остального (фон). Алгоритм интерактивной сегментации, известный также как «волшебная палочка», позволяет это сделать. Его особенностью является то, что пользователь может самостоятельно простыми действиями определить, что является для него целевым объектом, а что относится к фону.
Наибольшее применение данный инструмент нашел в растровых графических редакторах. Тем не менее существует целый класс промышленных программ, использующих в своей основе методы обработки и анализа изображений. Вэтом случае предъявляются повышенные требования как к программной реализации алгоритма – высокая надежность и точность работы, так и к аппаратной платформе, на которой предстоит работать. Так, например, все большее распространение получают мобильные системы контроля и учета.
В частности, в лесной отрасли задача учета круглого леса может быть решена посредством анализа изображений торцов штабелей бревен. Инструмент пользовательского редактирования на основе интерактивной сегментации необходим для оперативной корректировки результатов автоматического выделения. Вданной статье будут рассмотрены особенности реализации данного алгоритма с учетом аппаратных требований к системе учета – мобильные (сенсорные) устройства.
Идея алгоритма
Пользователь указывает точку внутри выделяемого объекта на изображении. Алгоритм определяет цвет выбранного пикселя и анализирует соседние точки на предмет совпадения цветов. По причине воздействия на объект света, теней, а также неоднородной структуры самого объекта его цвет не однороден. Следовательно, необходимо задать максимально допустимое отклонение цвета, при помощи которого и определяется принадлежность пикселя детектируемому объекту.
Реализация алгоритма
Алгоритм определения нужных пикселей является алгоритмом закрашивания замкнутых областей. Основная идея заключается в получении исходной точки (стартовой) и анализе соседних точек из 4-связной области на предмет похожести. Если точка удовлетворяет условию, то сохраняем ее в маске. Псевдокод для этого алгоритма:
В таком виде алгоритм предполагает применение рекурсии. Рекурсия весьма полезный инструмент, но его применение подразумевает использование практически не контролируемого ресурса: стека вызовов. Аучитывая, что параметры картинки (высота и ширина в пикселах), а также площадь выделяемого объекта в пикселах могут быть заранее не известными, то применение рекурсии может с большой вероятностью привести к переполнению стека вызовов или захватить слишком много оперативной памяти. По причине критических требований к надежности работы применение рекурсивного метода в данном случае нежелательно. Альтернативный вариант реализации дает идея волнового алгоритма.
Волновой алгоритм, как правило, используется для поиска кратчайшего пути от одной точки к другой. Суть волнового алгоритма состоит в следующем:
1.Имеется поле размерностью MxN, начальная точка A и конечная точка B. Каждая точка поля имеет свойство проходимости (она может быть проходима или непроходима). Требуется найти кратчайший путь из точки A в точку B.
2.Из начального элемента (точка A) распространяется в 4-хнаправлениях волна [5], как показано на рис.1. Элемент, в который пришла волна, образует фронт волны. На рисунках цифрами обозначены номера фронтов волны. Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор, пока не будет достигнут конечный элемент. Ну, или пока не станет ясно, что его не достигнуть.
3.Строится сама трасса. Её построение осуществляется от конечного элемента к начальному.
В данном случае технология построения трассы (самого кратчайшего пути) рассматриваться не будет ввиду того, что для задачи реализации интерактивной сегментации «волшебная палочка» трасса не нужна.
Так как в текущем случае не нужно искать наименьшее расстояние от начальной точки, до конечной, то нет смысла цифрами с расстоянием помечать точки (пиксели). Вместо этого пиксель отмечается как удовлетворяющий/ неудовлетворяющий критерию вхождения в выделяемую область. Алгоритм останавливается, когда вокруг выделяемого объекта образуется замкнутая рамка из пикселей, не отвечающих установленному критерию.
Рис. 1. Иллюстрация работы волнового алгоритма
Псевдокод алгоритма основной части:
current, next – очереди из точек текущего и следующего уровней соответственно (На рис.1, если в очереди current находятся точки с пометкой1, то в очереди next находятся точки с пометкой2 и так далее). Псевдокод метода проверки соседних точек:
Здесь проверяются 4соседних пикселя (верхний, нижний, левый, правый) на схожесть с текущим пикселем.
Псевдокод метода проверки пикселей на схожесть:
Метод isPixelExists(checkPoint) проверяет не существуют ли пиксели с такими координатами, то есть не произошел ли выход за пределы изображения.
mask – структура, в которую добавляются проверенные пиксели с пометкой вхождения/ не вхождения в результирующую выделяемую область.
Псевдокод метода проверки пикселей на схожесть по цвету:
step – чувствительность алгоритма.
Чтобы получить список пикселей, входящих в результирующую область, нужно из mask выбрать только те пиксели, которые помечены как удовлетворяющие критерию схожести.
Описанный алгоритм был применен в мобильном приложении на базе ОС Android для решения задачи детектирования торцов бревен.
Модификации алгоритма
1.Настройка чувствительности
Величина параметра чувствительность (разница между численными значениями цветовых компонент пикселей) настраивается исходя из особенностей изображений, подаваемых на вход алгоритма. Если картинка содержит детектируемые объекты, являющиеся однородными по цвету, то чувствительность может быть нулевой, это самый простой случай. Если же на вход подается изображение с неоднородным цветом объекта, то чувствительность настраивается исходя из величины его цветового диапазона.
Настройка чувствительности очень тонкий момент, так как при высокой чувствительности алгоритм может не распознать объект целиком, а при малом значении этого параметра могут попасть в выделяемую область пиксели, которые на самом деле не принадлежат объекту. Регулирование этого параметра сильно зависит от предметной области.
В задаче детектирования торцов бревен опытным путем выявлено значение чувствительности равное семи.
2.Аппроксимация
При невозможности определения идеальной чувствительности улучшить показатели точности распознавания алгоритма также может проведение аппроксимации, если заранее известна форма детектируемого объекта. На выходе алгоритма образуется список координат пикселей, вошедших в детектируемый объект, в зависимости от формы детектируемого объекта его можно аппроксимировать в круг, квадрат, треугольник и другие фигуры.
В задаче детектирования торцов бревен выделяемая область аппроксимировалась в эллипс. Диаметры овалов вычислялись по формулам maxX – minX и maxY ? minY, где maxX, maxY – наибольшие координаты по Х и У соответственно; minX, minY – наименьшие координаты по Х и У соответственно.
3.Задание минимального и максимального размеров объекта
Если исходя из условий решаемой задачи возможно оценить минимальный и максимальный размер целевого объекта по отношению к размеру изображения, это позволит значительно оптимизировать работу алгоритма. Вкачестве критериев могут выступать такие метрики, как площадь объекта по отношению к площади изображения в пикселах, соотношение высоты объекта или ширины и изображения и т.д.
В задаче детектирования торцов бревен установлен минимально допустимый диаметр детектируемого объекта – овала, зависящий от размера изображения, и он составляет 1/20часть от среднего арифметического высоты и ширины картинки в пикселях. Также установлена максимально допустимая площадь выделяемого торца бревна, она составляет 1/125часть от площади всего изображения. Значения этих ограничений получены путем анализа набора тестовых изображений.
4.Способ определения схожести
В зависимости от особенностей обрабатываемых изображений можно выбирать различные методы определения попадания пиксела в выделяемую область. Вприведенном примере схожесть определялась исходя из определения максимального отклонения среди трех компонентов цветовой модели RGB и сравнения с заранее установленной чувствительностью. Для сравнения можно использовать другие цветовые модели или сравнивать отклонения не по всем компонентам, а только по одной и т.д.
В задаче детектирования торцов круглых бревен для сравнения использовались все компоненты модели RGB, так как другие цветовые модели не показали лучших результатов.
Результат работы
Рис. 2. Скриншот экрана приложения
На рис.2 представлен скриншот окна мобильного приложения для детектирования торцов бревен [2], на котором продемонстрирован результат работы алгоритма интерактивной сегментации.
Выводы
Модификация «волшебной палочки» с использованием волнового алгоритма позволила устранить рекурсию. Отказ от рекурсии исключил возможность переполнения стека вызовов, а в Android по умолчанию его размер составляет 8Кбайт (около 260вызовов), то есть алгоритм с рекурсией будет способен распознать объект с приближенной площадью не более 260пикселей, что не удовлетворяет условиям задачи выделения торцов бревен на изображении. Таким образом, созданный алгоритм является более предсказуемым и стабильным, нежели рекурсивная «волшебная палочка». Возможности модификации алгоритма с учетом предметной области также повышают точность распознавания.