Факультет компьютерных наук и технологий
Кафедра программного обеспечения систем
Специальность: Программное обеспечения систем
Разработка и анализ алгоритма выделения контура на полутоновом
изображении при условии слабоконтрастных границ объектов
Научный руководитель: к.т.н., доц. Волченко Елена Владимировна
Автоматическая обработка визуальной информации является одним из важнейших направлений в области искусственного интеллекта. Интерес к проблемам компьютерной обработки определяется расширением возможностей как самих компьютерных систем, так и разработкой новых технологий обработки, анализа и идентификации различных видов изображений. При этом для создания эффективных технологий разрабатываемые методы и алгоритмы должны удовлетворять ряду требований по быстродействия и точности. Обычно каждый алгоритм, обладая определенными характеристиками, специализируется
на своем типе изображения. Поэтому в системах технического зрения необходимо сочетание нескольких методов, которые решают одну и ту же задачу различными способами, обеспечивая при этом необходимые показатели по быстродействию и достоверности [1].
Одной из наиболее сложных проблем обработки визуальной информации является выделение контуры объектов, так как контура — это самые информативные структурные элементы объектов. Тем не менее контуры, которые выделяются на слабоконтрастных размытых изображениях известными методами, имеют такие изъяны, как разрывы, отсутствие контурных линий или наличие ошибочных, которые не отвечают исследуемому объекту.
Большинство получаемых изображений являются слабоконтрастными, имеют неравномерный фон, а также содержат различного рода шумы. Поэтому для анализа такой информации необходимо обеспечить высокое визуальное качество и эффективность предварительной обработки исследуемого изображения, которое может быть получено с помощью современных методов выделения контуров и границ. Это позволит улучшить решения большого количества задач [2].
На сегодняшний день существует огромное множество методов выделения контуров. Эти методы эффективны для обработки изображений с низким уровнем шума.
Таким образом, на сегодняшний день остается актуальной разработка методов выделения объектов на слабоконтрастных изображениях.
Выделение контура объекта на изображении является одной из актуальных задач в цифровой обработке сигнала. Психологические исследования выявили, что с точки зрения распознавания и анализа объектов на изображении наиболее информативным является не значение яркости объектов, а характеристики их границ — контуров.
При анализе изображений и распознавании объектов, присутствующих на нем, весомую долю принимают на себя методы и алгоритмы выделения контуров, так как они значительно упрощают работу с изображением и/или цифровым рядом. Но большинство существующих на сегодняшний день алгоритмов не может предоставить достаточно хорошую точность выделения контура объектов, так как всегда присутствуют разрывы и ложные границы. Это в значительной степени усложняет дальнейшую работу над изображением. Данная работа нацелена на разработку алгоритма, позволяющего максимально улучшить выделение границ изображения путем комбинации и модификации существующих методов обработки изображений.
Целью работы является разработка оптимальной комбинации алгоритмов обработки для лучшего выделения контуров.
Ключевой задачей является выделения линий, проходящих на границах однородных областей.
Предметом исследования является разработка алгоритма выделения контура слабоконтрастных объектов на изображении на основании существующих алгоритмов и анализа результатов их работы.
Объектом исследования являются существующие методы обработки и выделения контуров на изображении.
Научной новизной данной работы является разработка алгоритма выделения контуров на слабоконтрастных полутоновых изображениях. Существующие на сегодняшний день алгоритмы выделения контуров плохо справляются с низкой контрастностью объектов и фона, а также крайне чувствительны к шуму на изображении. Разрабатываемый алгоритм будет направлен на максимальное выделение всех границ объектов и на подавление обнаруженных ложных контуров, которые зачастую возникают от присутствия импульсного шума.
Психофизические эксперименты показали, что фотографическое или телевизионное изображение с подчеркнутыми границами оказывается субъективно более приятным, чем фотометрически совершенная репродукция. Повышение резкости изображения может быть достигнуто путем численного дифференцирования. Величина отклика оператора производной в точке изображения пропорционально степени разрыва изображения в данной точке. Таким образом, дифференцирование изображения позволяет усилить перепады яркости и другие разрывы (шумы, помехи) и не подчеркивать области с медленными изменениями яркости [1].
Одной из наиболее сложных прикладных задач, использующих алгоритм выделения контуров, является задача выделения линий на ладони. Сложность данной задачи обусловлена низкой контрастностью линий по отношению к их окружению и обилие помех (шума), разрывы, ложные линии или полное их отсутствие. Для данной задачи является актуальным усиление перепадов яркости.
Для вычисления двумерной второй производной и наложения результата на изображение (высокочастотная фильтрация) используются три маски, представленные в формулах 5.1–5.3:
| (5.1) | ||||||||||
| (5.2) | ||||||||||
| (5.3) |
Одной из задач фильтрации изображения с подъемом высоких частот является случай, когда исходное изображение темнее, чем требуется. В этом случае можно варьировать коэффициент усиления высоких частот U>1 для увеличения общей яркости изображения. Матрицы приведены в формулах 5.4–5.6.
| (5.4) | ||||||||||
| (5.5) | ||||||||||
| (5.6) |
Анализ результатов обработки показывает, что импульсные помехи не могут эффективно подавляться сглаживающими фильтрациями, но полностью удаляются подходящим медианным фильтром. Высокочастотная фильтрация не только улучшает деятельность объектов на изображении, но и подчеркивает высокочастотные шумы [1, 2, 3].
Выделение границ основывается на алгоритмах, которые определяют резкое изменение яркости на изображении. Результатом выполнения алгоритма выделения границ должно быть некоторое количество связанных кривых, которые отображают границы объекта. В большинстве случаев границы на изображениях выражены не столь контрастно, поэтому существующие на данный момент алгоритмы и операторы не дают должного результата. Часто результат обработки варьируется от разрывов контуров и линий (фрагментированность) до полного отсутствия границы.
В общем, алгоритмы выделения контуров изображений основываются на одном из двух базовых свойств сигнала яркости: разрывы и однородность.
В первом случае подход состоит в разбиении изображения на основании резких разрывов яркости, которые являются важными простейшими признаками, поскольку они часто определяют очертания изображенных объектов. Локальные разрывы значений яркости называются яркостными перепадами, или яркостными контурами. Вторая категория методов использует разбиение изображения на области, однородные с точки зрения выбранных критериев [1, 5].
На рисунках 6.1 и 6.2 показаны участки изображения с быстрым изменением яркости от низкого уровня к высокому в одномерном и двумерном случаях. В одномерном случае перепад характеризуется высотой, углом наклона и координатой цента склона. Перепад существует, если его угол наклона и высота больше некоторого заданного порога. Для двумерного случая важна также ориентация перепада по отношению к оси x. Идеальный детектор перепада при обработке областей изображения, представленных на рисунках 6.1 и 6.2, должен указывать на наличие перепада в единственной точке, расположенной в центре склона.
Рисунок 6.1 — Одномерный случай
Рисунок 6.2 — Двумерный случай
Общий подход у обнаружению перепадов на изображении можно сформулировать следующим образом. Исходное изображение представляется цифровой матрицей F с элементами fi, j и подвергается линейной или нелинейной обработке для того, чтобы усилить перепады яркости. В результате образуется массив чисел G с элементами gi, j, описывающий изображение с подчеркнутыми изменениями яркостей. Затем выполняется операция сравнения с порогом и определяется положение элементов изображения с ярко выраженными перепадами. Если gi, j < Ti, jL, то имеет место нисходяще перепад, а при gi, j ≥Ti, jU — восходящий перепад. Величины Ti, jL и Ti, jU представляют собой нижнее и верхнее пороговые значения. Эти значения можно сделать переменными в плоскости изображения для компенсации влияния сильных изменений яркостей на результаты обнаружения перепадов.
Выбор порога является одним из ключевых вопросов выделения перепадов. При слишком высоком уровне порога не будут обнаружены структурные элементы с низким контрастом. Наоборот, слишком низкий уровень порога является причиной того, что шум будет ложно принят за перепад. Для обозначения положения перепадов на изображении часто формируют контурный препарат — массив элементов. Таким образом, перепады яркостей на изображениях являются характеристиками границ областей объектов — контуров. Задача выделения контуров состоит в построении бинарного изображения, содержащего лишь контура.
До выполнения операции порогового обнаружения можно подчеркнуть
перепады с помощью различных способов. Один из наиболее простых способов заключается в вычислении дискретных разностей, что аналогично непрерывному пространственному дифференцированию. Подчеркивание вертикальных перепадов осуществляется горизонтальным (построчным) дискретным дифференцированием (вычислением дискретных производных) [1, 5, 6]. В результате формируется некоторое изображение — массив элементов, представленный в формуле 6.7.
gi, j = fi, j − fi, j+1 | (6.7) |
Аналогично осуществляется подчеркивание горизонтальных перепадов. В результате получается массив элементов, представленный в формуле 6.8.
gi, j = fi, j − fi+1, j | (6.8) |
Диагональное подчеркивание можно получить путем вычисления разностей уровней диагональных пар элементов изображения.
Горизонтальное подчеркивание также можно выполнить вычисляя разности яркостей элементов вдоль строки изображения по формулам 6.9 и 6.10.
gi, j = [fi, j − fi, j-1] − [fi, j+1 − fi+1, j] | (6.9) |
или
gi, j = 2 * fi, j − fi, j-1 − fi, j+1 | (6.10) |
Подобные выражения можно записать для изменения яркости по вертикали и диагонали.
Для обнаружения линий на изображениях можно использовать набор масок, приведенный в (5.5–5.8). Тут (6.10) — горизонтальная, (6.11) — +450, (6.12) — вертикальная и (6.13) — -450. Название масок соответствует их наиболее сильному отклику при скольжении по изображению.
| (6.10) | ||||||||||
| (6.11) | ||||||||||
| (6.12) | ||||||||||
| (6.13) |
Для выделения всех линий заданного направления необходимо применить маску к изображению в целом сравнивая абсолютное значение результата отклика маски с заданным порогом. Таким образом решение о наличии элемента линии на изображении принимается на основе выражения, представленного в формуле 6.14:
|R|≥T | (6.14) |
где R — результат отклика маски, T — заданный порог.
Оставшиеся при этом точки на изображении и соответствуют наибольшим значениям отклика, которые в случае наличия на изображении линий толщиной в один пиксель наиболее близки к направлению, определяемому маской.
Повышение контраста перепадов без учета их ориентации можно получить путем свертки массива изображения с оператором Лапласа, представленным в виде маски 6.15.
| (6.15) |
Операторы Лапласа реагируют на перепады яркости в виде ступенчатого перепада и на крышеобразный
перепад. Они также выделяют изолированные точки, тонкие линии, их концы и острые углы объектов. Линия подчеркивается в два раза ярче, чем ступенчатый перепад, конец линии — в три раза, а точки — в четыре раза ярче. Оператор Лапласа не инвариантен к ориентации перепадов: например, отклик оператора на наклонный перепад в диагональном направлении почти вдвое больше, чем в горизонтальном и вертикальном [8].
В нелинейных системах обнаружения перепадов для контрастирования перед пороговым ограничением используются нелинейные комбинации значений яркости элементов изображения. В большинстве методов ограничиваются обработкой окном размером 2×2 или 3×3. Среди существующих нелинейных методов можно выделить алгоритмы Робертса, Превитта, Собела, Кирша и Уоллеса.
Ряд нелинейных операторов выделения контуров использует вычисление модуля градиента яркости, представленное в формуле 6.16.
∇ = gi, j = √(X2 + Y2) | (6.16) |
где X и Y — частные производные, характеризующие скорость изменения яркости по двум направлениям.
Робертс для вычисления перепадов предложил следующую операцию нахождения величин X и Y, представленную в формуле 6.17 и 6.18:
X = fi, j − fi+1, j+1 | (6.17) |
Y = fi, j+1 − fi+1, j | (6.18) |
При построении оператора Робертса используется тот факт, что для определения перепада яркости можно использовать производные (разности) в любых двух взаимно перпендикулярных направлениях. Отмечая тот из четырех элементов изображения, расположенных около обнаженной точки, который имеет наибольшее значение яркости, можно получить информацию о приблизительной ориентации перепада.
Маски для получения составляющих градиента X и Y с помощью оператора Робертса приведены в 6.19 и 6.20.
| (6.19) | |||||
| (6.20) | |||||
Рисунок 6.3 — Работа алгоритма Робертса с предварительной обработкой (анимация: 4 кадра, 20 циклов повторения, 16,3 килобайт) |
Реализация масок размером 2×2 неудобна, так как у них нет четко выраженного центрального элемента. Метод, при котором используется маски размером 3×3 предложил Превитт [8, 10]. Алгоритм использует модуль вектора градиента и для нахождения величин X и Y используются выражения, приведенные 6.21 и 6.22.
X = (fi-1, j-1 + fi-1, j + fi-1, j+1) - (fi+1, j-1 + fi+1, j + fi+1, j+1) | (6.21) |
Y = (fi-1, j+1 + fi, j+1 + fi+1, j+1) - (fi-1, j-1 + fi, j-1 + fi+1, j-1) | (6.22) |
Маски для получения составляющих градиента X и Y с помощью оператора Превитта приведены в 6.23 и 6.24.
| (6.23) | ||||||||||
| (6.24) |
Собел модифицировал данный алгоритм и предложил использовать весовой коэффициент 2 для средних элементов, что позволяет уменьшить эффект сглаживания за счет придания большего веса средним точкам. Выражения для нахождения X и Y в операторе Собела представлены в 6.25 и 6.26.
X = (fi-1, j-1 + 2 * fi-1, j + fi-1, j+1) - (fi+1, j-1 + 2 * fi+1, j + fi+1, j+1) | (6.25) |
Y = (fi-1, j+1 + 2 * fi, j+1 + fi+1, j+1) - (fi-1, j-1 + 2 * fi, j-1 + fi+1, j-1) | (6.26) |
Маски для получения составляющих градиента X и Y с помощью оператора Собела приведены в 6.27 и 6.28 Для вычисления величины градиента эти составляющие, а соответственно и маски, необходимо использовать совместно.
| (6.27) | ||||||||||
| (6.28) |
Для оператора Робертса приближенные выражения не являются одинаково чувствительными к границам с любой ориентацией. Для строго вертикальных или горизонтальных линий все выражения дают одинаковые результаты, но для линий с наклоном 450 приближенные значения могут отличаться от точного в √2 раз. Для операторов Превитта и Собела вопрос изотропности не возникает, так как сами маски инвариантны лишь для поворотов на углы в 900.
Следует отметить, то операторы Превитта и Собела можно изменить так, чтобы они давали максимальный отклик для контуров, направленный диагонально [1].
Уоллес предложил нелинейный метод обнаружения перепадов, основанной на гомоморфной обработке изображения. Согласно этому методу, точка находится на перепаде, если величина логарифма от яркости в этой точке превосходит среднее значение логарифмов яркостей четырех ближайших соседних элементов на некоторое фиксированное значение. Элемент обработанного изображения определяется формулой 6.29, что эквивалентно 6.30:
gi, j = log(fi, j − ¼ * log(fi-1, j) − ¼ * log(fi, j+1) − ¼ * log(fi+1, j) − ¼ * log(fi, j-1) | (6.29) |
gi, j = ¼ * log{ fi, j4 / (fi-1, j * fi, j+1 * fi+1, j * fi, j-1) | (6.30) |
Рисунок 6.4 — Работа алгоритма Уоллеса с предварительной обработкой (анимация: 4 кадра, 20 циклов повторения, 16,3 килобайт) |
Сравнение gi, j с верхним и нижним пороговым значениями эквивалентно сравнению дроби в скобках выражения с видоизмененным порогом. Поэтому не требуется точно вычислять значения логарифмов. Основное преимущество логарифмического детектора перепадов кроме простоты вычислений состоит в том, что он не чувствителен к мультипликативным изменениям уровня яркости.
На сегодняшний день предложено большое количество алгоритмов выделения контуров [4–18]. Одним из новых и наиболее эффективных из них является алгоритм выделения контуров на малоконтрастных и размытых изображениях на основе фрактальной фильтрации. Фракталы более наглядно выделяют контуры, чем другие операторы, но они ориентированы на обработку малоконтрастных изображений в целом, нежели выделение таковых линий и границ [19].
Алгоритм выделения контуров Лаплассиан Гауссиана был предложен в 1982 году. Данный алгоритм является второй производной, определенной как:
∇2f = d2*f / d*x2 + d2*f / d*y2 | (6.29) |
Рисунок 6.5 — Работа алгоритма Лаплассиан Гауссиана с предварительной обработкой (анимация: 5 кадров, 20 циклов повторения, 18,3 килобайт) |
Он осуществляется в два шага. На первом шаге он сглаживает изображение, а затем вычисляет функцию Лапласса, что приводит к образованию двойных контуров. Определение контуров сводится к нахождению нулей на пересечении двойных границ. Компьютерная реализация функции Лапласса обычно осуществляется через следующие маски:
| (6.30) | ||||||||||
| (6.31) |
Лаплассиан обычно использует нахождение пикселя на темной или светлой стороне границы.
Детектор границ Канни является одной из самых популярных алгоритмов обнаружения контуров. Впервые он был предложен Джоном Канни в магистерской диссертации в 1983 году, и до сих пор является лучше многих алгоритмов, разработанных позднее. Важным шагом в данном алгоритме является устранение шума на контурах, который в значительной мере может повлиять на результат, при этом необходимо максимально сохранить границы [20]. Для этого необходим тщательный подбор порогового значения при обработке данным методом.
Алгоритм:
В отличии от операторов Робертса и Собеля, алгоритм Канни не очень восприимчив к шуму на изображении.
Алгоритм искусственной пчелиной колонии является довольно молодым алгоритмом для нахождения глобальных экстремумов сложных многомерных функций. Идея алгоритма взята, как видно из названия, у пчел, а именно из их поведения при поиске мест, где можно раздобыть как можно больше нектара.
Колония пчел может преодолевать большие расстояния в различных направлениях одновременно в поисках источников питания. Сначала из улья в случайном направлении вылетает какое-то количество пчел-разведчиков, которые пытаются отыскать участки, где есть нектар. По возвращению в улей разведчики сообщают остальным пчелам где и сколько они нашли нектара. После чего на найденные участки отправляются другие пчелы, причем чем больше на данном участке предполагается найти нектара, тем больше пчел летит в этом направлении [21].
В рамках текущей задачи наибольшим количеством нектара будут обладать те точки обработанного изображения, в которых будет самое вероятное нахождение контура или границы, что будет задаваться его фитнесс-функцией. То есть пчелы-работники будут посылаться в те участки, в которых по мнению пчел-разведчиков есть разорванный контур. Пчелы-работники должны провести анализ точек изображения в области нахождения нектара и или выбрать точку для восстановления контурной линии, или же сообщить, что в данном месте нектар отсутствует. Изначально пчелы будут направлены случайным образом в точки вероятного нахождения контурных линий.
Модификацией данного алгоритма является добавление пчелам возможности создавать мертвую зону
. В данном случае это точки изображения, которые с максимальной вероятностью не принадлежат ни к одному из возможных контуров. В таком случае пчела закапывает
данный участок, тем самым удаляя этот участок на изображении.
Идея алгоритма основана на способности муравьев находить кратчайший путь между источником пищи и муравейником без использования визуальной информации [22]. Способность эта обусловлена выделением феромона во время их движения и использованием этого феромона в качестве маркера.
Алгоритм, предложенный в работе [22], реализует процедуру дискретной оптимизации. Переход от непрерывной оптимизации к дискретной осуществляется посредством построения полного ориентированного графа поиска решения, количество вершин в котором определяется точностью нахождения значений параметров. Из каждой вершины выходят дуги с равномерно распределенными значениями нормированных параметров. В вершины графа равномерно распределяются муравьи. Цель муравья — посетить тот список вершин, который вероятнее всего является контуром или границей. Пометки дуг, по которым прошел муравей, будут являться найденным им решением. Общим же решением будет являться максимальный уровень феромона, оставленный множеством муравьев. Количество феромона, наносимого на дуги, пропорционально качеству решения: чем вероятнее наличие контура в районе данной дуги, тем больше феромона наносится на дугу.
На каждой итерации происходит увеличение количества феромона на каждой дуге и его испарение.
Модификацией данного алгоритма для текущей задачи является поэтапное увеличение точности вычисления маршрута муравья. Сначала алгоритм работает c графом, в котором минимальное количество вершин, далее на основании полученных результатов алгоритм запускается на графе большего размера и так до нахождения оптимального результата.
В результате выполнения данной работы были рассмотрены и проанализированы некоторые методы и алгоритмы улучшения качества изображения и выделения контуров объектов на изображении, а именно фильтрация изображений и низкочастотная фильтрация, подчеркивание границ различными методами, такими как Робертс, Превитт, Собел и Уоллес, видоизменение гистограмм для увеличения контрастности изображения, линейные и нелинейные методы обнаружения линий и выделения контуров. Было выявлено, что классические алгоритмы достаточно хорошо справляются с простыми задачами, но они не пригодны для работы с реальными слабоконтрастными изображениями. Результат обработки таких изображений получается зашумленным и перегруженным избыточными лже-контурами. Улучшить выделение границ можно с помощью предварительной обработки изображения определенным набором алгоритмов и операторов, а также алгоритмов, предназначенных для восстановления утерянных фрагментов контуров.
В данной работе предложено два варианта улучшения результатов выделения контура, основанных на алгоритмах пчелиных и муравьиных колоний. Данные варианты могут дать неплохие результаты при обработке изображений, но задача усложняется наличием на реальных изображениях шумов, которые могут привести к возникновению ложных границ и контуров.
При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2015 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.
Мир, 1979. — С. 28–47.
Мир, 1989. — С. 50–61.
Вильямс, 2004. — С. 728–733.
Performance Characterization in Computer Vision: The Role of Statistics in Testing and Design, Chapter in: Imaging and Vision Systems: Theory, Assessment and Applications, Jacques Blanc-Talon and Dan Popescu (Eds.), NOVA Science Books.