Разработка и исследование методов сегментации изображений на основе многомерных цепей Маркова

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

Изображения естественных сцен содержат множество разнообразных объектов. Для конкретных систем важными являются не все объекты, а определенный класс объектов в зависимости от назначения системы. Например, в системах мониторинга земной поверхности объектами исследования могут быть очаги пожаров, области, затопленные в результате наводнения, территории вырубки леса и т. д. Эффективным способом такой интерпретации изображений является сегментация.

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

Большой вклад в развитие методов предварительной обработки изображений внесли российские и зарубежные ученые: Журавлев Ю. И., Бакут П. А.,.

Потапов A.A., Сойфер В. А., Алпатов Б. А., Canny J.F., Pratt W.K., Prewitt J.P., Sobel I.E., Kirche R.A., Roberts L.G. и др. [1−12].

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

Все известные методы сегментации изображений можно условно разделить на методы контурной сегментации [13−35,А1] и методы, основанные на выделении однородных (текстурных) областей [9,13,36−55,А1].

Наиболее распространенные методы контурной сегментации в силу многообразия сцен и неоднородности фона на цифровом полутоновом изображении (ЦПИ) могут приводить к выделению разрывных контуров или пропуску границ объектов. Повышение точности выделения контуров в этих методах требует дополнительных преобразований, операций прослеживания контуров или увеличения размерности и количества масок, что в итоге приводит к большим вычислительным ресурсам.

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

Для разработки методов обработки изображений, являющихся многомерными случайными процессами необходимы математические модели (ММ), наиболее точно отражающие реальные процессы и обладающие наибольшей вычислительной эффективностью. Перспективным в этом смысле решением можно считать использование многомерной ММ, базирующейся на многомерных цепях Маркова с несколькими состояниями и энтропийном подходе к ее реализации [56−59]. Однако, если речь идет об обработке ЦПИ, представленных £-разрядными двоичными числами с числом дискретных значений (уровней яркости), возникает проблема хранения в памяти и оперирования с матрицами вероятностей переходов (МВП) от /' -го состояния к уму (соседнему) размерностью 2ё х2ё. Такая обработка ЦПИ в реальном масштабе времени труднореализуема. Оригинальное решение данной проблемы найдено представлением ЦПИ в виде набора из g разрядных двоичных изображений (РДИ) [60−63], каждое из которых представляет собой двумерную цепь Маркова с двумя равновероятными состояниями МВП размером 2×2 по каждому измерению. Синтезированная в [63] многомерная ММ требует для своей реализации только операций сравнения и послужила основой для разработки методов контурной и текстурной сегментации изображений.

Учитывая, что основные детальные области изображения в наибольшей степени выражены на старших разрядах ЦПИ, для выделения объектов интереса в работе предложено использовать элементы РДИ старших разрядов ЦПИ.

Для выделения контуров объектов интереса с использованием двумерной ММ [64,65,А2-А8], вычисляется величина количество информации в каждом элементе РДИ и сравнивается с порогом. Разработанный метод требует значительно меньших вычислительных затрат, чем известные методы (метод Собела, метод Канни, метод Лапласиана гауссиана).

Улучшение контурных изображений достигается удалением точечных помех, которые обусловлены видом исходного ЦПИ и применяемым методом и проявляются в виде точечных искажений около трехгранных вершин и Т-образных пересечений. В известных работах [1−4,8,10,13] для улучшения контурного изображения применяют усредняющие линейные фильтры с маской 3×3 элемента [3,13,33,34]. В данной работе удаление точечных помех основано на использовании многомерной двоичной цепи Маркова, вычислении количества информации в элементе РДИ относительно четырех соседних элементов и последующим сравнением этой величины с порогом [A3].

Для закрашивания областей интереса (сегментации) предложено использовать построчный алгоритм заполнения с затравкой [66,67], который дает существенный выигрыш в объеме памяти и времени обработки за счет хранения только одного затравочного элемента для каждого заполняемого участка.

В цветовом пространстве RGB каждая из компонент представляет собой gразрядное ЦПИ. Использование цвета при сегментации изображений обусловлено тем, что цвет облегчает выделение и распознавание объектов на изображении. Применяя к каждой из цветовых компонент разработанный метод сегментации ЦПИ и нормирование интенсивности цветовых компонент [14], разработан метод сегментации цветного изображения.

Задача выделения контуров объектов интереса усложняется еще в большей степени, если необходимо оперативно обработать видеосигнал после передачи его по зашумленному радиоканалу. Для оптимизации работы алгоритмов выделения контуров на зашумленных ЦПИ, непосредственно перед их использованием, выполняют сглаживание изображения (методы Лапласиан гаус-сиана, Канни) [4,8,10,13]. Однако, в случае сильно зашумленных ЦПИ (р]х < 1) данные методы будут неприемлемы. Для восстановления изображений, разрушенных шумом, на приемной стороне должны быть применены алгоритмы, наиболее полно реализующие большую статистическую избыточность ЦПИ. Это позволит существенно повысить помехоустойчивость приема изображений. Одним из таких подходов является метод, основанный на теории фильтрации условных марковских процессов и двумерной ММ ЦПИ, продуктивность которого показана в работах [68−71].

В данной работе для выделения контуров на зашумленных БГШ ЦПИ предлагается применить комбинированный метод, состоящий из алгоритма двумерной нелинейной фильтрации и алгоритма выделения контуров, позволяющий выделять контуры объектов интереса на зашумленных ЦПИ с точностью превышающей известные методы (Лапласиан гауссиана, Канни) [А9-А14].

Часто естественные сцены, такие как леса, поля, лишены существенных деталей на больших пространствах и не имеют четко выраженных границ. В этом случае необходимо использовать идентификацию областей изображения на основе анализа их текстуры. Эффективность выделения текстурного признака в значительной мере определяет качество сегментации. Несмотря на широкий выбор методов выделения текстурных областей, многие из них требуют больших вычислительных ресурсов, не точно разделяют признаковое пространство и т. д. В связи с этим разработка методов текстурной сегментации является весьма актуальной. Представление изображений двумерной цепью Маркова, позволило разработать метод текстурной сегментации, базирующийся на вычислении оценки средней вероятности перехода в элементах изображения с использованием скользящего окна. Проведенные в работе исследования показали высокую эффективность выделения текстурных областей [А15-А19].

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

Объектом исследования являются методы контурной и текстурной сегментации цифровых полутоновых и цветных изображений.

Предметом исследования является разработка методов контурной и текстурной сегментации изображений на основе двумерных цепей Маркова.

Для достижения поставленной цели в работе решаются следующие задачи:

1. Анализ характеристик известных методов сегментации изображений, позволяющий оценить эффективность выделения интересующих объектов.

2. Разработка метода сегментации цифровых полутоновых и цветных изображений на основе двумерной цепи Маркова и выделения контуров объектов интереса по вычисленной величине количества информации, реализация которого достигается меньшими вычислительными ресурсами, чем известными алгоритмами.

3. Разработка метода удаления точечных помех, основанного на вычислении количества информации по четырем соседним элементам, позволяющего снизить процент ложных контуров.

4. Разработка комбинированного метода сегментации изображений, за-шумленных БГШ, сочетающего нелинейную фильтрацию ЦПИ на первом этапе и выделение контуров объектов интереса — на втором.

5. Исследование и анализ эффективности разработанного метода выделения контуров на оригинальных и зашумленных ЦПИ.

6. Разработка метода текстурной сегментации цифровых полутоновых и цветных изображений, использующего в качестве текстурного признака оценку средней вероятности перехода в двумерной цепи Маркова и анализ качества его работы.

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

На защиту выносятся следующие основные научные положения:

1. Систематизация и анализ известных методов сегментации изображений позволяет оценить их эффективность.

2. Метод сегментации цифровых полутоновых и цветных изображений на основе двумерных цепей Маркова позволяет точно выделить контуры объектов интереса меньшими вычислительными ресурсами, чем известными методами.

3. Метод удаления точечных помех позволяет удалить 1−2 элемента другой яркости на РДИ и снизить процент ложных контуров.

4. Комбинированный метод сегментации позволяет восстановить за-шумленное изображение нелинейным фильтром и выделить контуры объектов с точностью, превышающей известные методы.

5. Результаты количественного и качественного анализа методов выделения контуров на оригинальных и зашумленных изображениях позволяют оценить эффективность их работы.

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

Научная новизна полученных результатов состоит в следующем:

1. Разработан новый метод сегментации ЦПИ на основе двумерной цепи Маркова, позволяющий выделить контуры объектов интереса с высокой точностью и меньшими вычислительными ресурсами, чем известные методы (Канни, Лапласиан гауссиана, Робертса, Превитта, Собела).

2. Разработан метод удаления точечных помех на основе многомерной цепи Маркова, позволяющий повысить качество сегментации ЦПИ за счет снижения процента ложных контуров.

3. Разработан метод сегментации цветных изображений в системе RGB, позволяющий эффективно выделить объекты заданного цвета и не уступающий по эффективности методу К-средних.

4. Разработан комбинированный метод сегментации ЦПИ, позволяющий выделить контуры объектов интереса на зашумленных ЦПИ при отношениях сигнал/шум на входе приемного устройства до — 9 дБ.

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

Практическая ценность полученных результатов заключается в том, что разработанные методы позволяют эффективно выделить объекты интереса в системах мониторинга и видеонаблюдения, охранного телевидения, медицинских системах за счет точного выделения контуров объектов интереса и текстурных областей, в том числе и в условиях действия БГШ большой интенсивности. Разработанные методы требуют для реализации небольших вычислительных ресурсов, что позволяет обрабатывать изображения в реальном масштабе времени.

Часть результатов, выносимых на защиту, была получена автором в рамках реализации федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009 — 2013 годы (соглашение № 14.В37.21.0628), а также в ходе выполнения НИР по программе стратегического развития ПСР 2.4.1−12 «Разработка программного приложения алгоритмов фильтрации и сегментации изображений в видеоинформационных системах» в ВятГУ.

Для подтверждения достоверности теоретических положений проведено цифровое моделирование, проверена устойчивость полученных алгоритмов к точности априорных данных. Получено свидетельство на программный продукт, зарегистрированное в Реестре программ для ЭВМ [А20].

Результаты работы внедрены: в перспективные разработки программно-аппаратных средств автоматизированных систем обработки видеоинформации (ФГУП «НИИ СВТ») — в состав комплекта прототипа системы обработки и распознавания цифровых изображений (ЗАО НПП «Знак») — в учебный процесс на кафедре радиоэлектронных средств Вятского государственного университета.

Диссертационная работа состоит из четырех глав.

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

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

Во второй главе разработан метод сегментации ЦПИ на основе представления их набором из g РДИ, каждое из которых представляет собой двумерную цепь Маркова. Для выделения контуров вычисляется количество информации в элементе РДИ по двум окрестным элементам. С целью улучшения контурного изображения предложен метод удаления точечных помех, основанный на вычислении количества информации в двоичном элементе изображения относительно четырех окрестных элементов. Проведена сравнительная оценка качества разработанного метода по общепринятым критериям с известными методами сегментации. Определен выигрыш во времени разработанного метода выделения контуров и известных методов контурной сегментации. На основе разработанного метода выделения контуров, предложен метод сегментации цветных изображений в цветовом пространстве RGB, базирующийся на применении разработанного метода к каждой из цветовых компонент. Анализируется качество сегментации цветных изображений на основе качественного сравнения полученных результатов с результатами метода К-средних. Приведены результаты моделирования алгоритмов сегментации, удаления точечных помех, заполнения сегментов, сегментации цветных изображений.

В третьей главе предложен комбинированный метод выделения контуров на зашумленных изображениях. Метод состоит из алгоритма двоичной нелинейной фильтрации, позволяющего восстановить ЦПИ, разрушенное аддитивным БГШ, и алгоритма выделения контуров, позволяющего выделить контуры объектов интереса. Разработанный метод позволяет выполнить сегментацию зашумленных ЦПИ с высокой точностью. Проведено исследование эффективности данного метода в условиях действия БГШ различной интенсивности. Проведена сравнительная оценка качества работы разработанного метода с известными методами при разных отношениях сигнал/шум.

В четвертой главе разработан метод текстурной сегментации изображений, основанный на вычислении статистических характеристик областей. Представление изображения с помощью двумерных цепей Маркова позволяет использовать в качестве текстурного признака оценку средней вероятности перехода, которая вычисляется для каждого элемента изображения и сравнивается с порогом. Проведен анализ эффективности разработанного метода при сегментации искусственных и естественных текстур. Проведено исследование зависимости качества сегментации от размера окна и величины порогового значения при разных вероятностях переходов соседних текстур. Анализируется возможность выбора значения порога по гистограмме изображения текстурного признака. Исследуется возможность текстурной сегментации с помощью разработанного метода цветных изображений.

Основные результаты диссертации опубликованы в 20 работах, в том числе в 7 статьях в журналах из списка ВАК, 12 статьях и тезисах в сборниках трудов научно-технических конференций различных уровней, 1 свидетельстве о государственной регистрации программы для ЭВМ.

Основные результаты диссертации опубликованы в 20 работах, в том числе в 7 статьях в журналах из списка ВАК, 12 статьях и тезисах в сборниках трудов научно-технических конференций различных уровней, 1 свидетельстве о государственной регистрации программы для ЭВМ.

ЗАКЛЮЧЕНИЕ

.

В результате выполнения диссертационной работы разработаны методы сегментации полутоновых и цветных изображений для использования с автоматических системах обработки изображений с целью точного выделения объектов интереса и текстурных областей, в том числе в реальном масштабе времени и в условиях действия БГШ большой интенсивности. Основным итогом диссертации является решение научно-технической задачи разработки и исследования новых методов сегментации изображений, которые обеспечивают высокое качество сегментации и требуют для реализации меньших вычислительных ресурсов, чем известные методы.

Основные научные результаты.

1. Проведена обобщенная систематизация и анализ существующих классических методов сегментации изображений, позволяющий оценить их эффективность.

2. Разработан и исследован метод выделения контуров объектов интереса на ЦПИ на основе многомерной ММ, позволяющий выделить контуры интересующих объектов с высокой точностью при небольших вычислительных затратах.

3. Показано, что для реализации разработанного метода выделения контуров требуется только две операции сравнения с элементами окрестности для принятия решения о принадлежности контуру одного элемента изображения, что обеспечивает выигрыш в скорости обработки по сравнению с известными методами в 5,7−19,7 раз. По качеству сегментации разработанный метод превышает известные методы по критерию FOM на 6−38%, по критерию RMS на 1−3% уступает методам Превитта и Собела. Полученные в результате сегментации контуры всегда являются замкнутыми, в то время как для других методов критерий относительной несвязности составляет 6−33%.

4. Для улучшения контурного изображения предложен метод удаления точечных помех на основе многомерной двоичной цепи Маркова, позволяющей снизить процент ложных контуров по критерию FOM на 11%, а по критерию RMS на 16% при сохранении замкнутости контуров.

5. Разработан метод сегментации полутоновых и цветных изображений, состоящий из алгоритма выделения контуров и построчного алгоритма заполнения с затравкой, требующий небольших вычислительных ресурсов и позволяющий выделить объекты интереса на неоднородном фоне.

6. Разработан и исследован комбинированный метод выделения контуров на зашумленных ЦПИ. Показано, что по помехоустойчивости комбинированный метод сравним с методами Лапласиана гауссиана и Канни, точность выделения контуров на зашумленных ЦПИ разработанным методом превышает известные методы на 33.49% по критерию FOM и на 18.29% по критерию RMS, контуры получаются всегда замкнутыми.

7. Разработан и исследован метод текстурной сегментации, основанный на вычислении оценки средней вероятности перехода в двумерной цепи Маркова для каждого элемента изображения и сравнения вычисленной величины с порогом. Показано, что оптимальным с точки зрения соотношения качество сегментации / время обработки является окно размером 21×21 элемент. Сравнение разработанного метода с методами, основанными на вычислении градиента, показало, что разработанный метод обеспечивает уменьшение ошибки сегментации более чем в 10 раз.

Практические результаты работы.

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

2. Комбинированный метод сегментации позволяет выделить объекты интереса на зашумленных изображениях при отношениях С/Ш на входе приемного устройства до -9 дБ за счет применения алгоритма двумерной нелинейной фильтрации.

3. Разработанная структура устройства комбинированного метода выделения контуров на зашумленных ЦПИ, обладает высокой однородностью и требует для своей реализации малых технических и временных ресурсов.

4. Метод текстурной сегментации позволяет эффективно выделять области различной текстуры в спутниковых системах мониторинга поверхности Земли.

5. Разработано прикладное программное обеспечение для исследования методов сегментации полутоновых и цветных изображений с последующей количественной оценкой качества полученных результатов на основе выбранных критериев.

Разработанные методы внедрены в перспективные разработки программно-аппаратных средств автоматизированных систем обработки видеоинформации (ФГУП «НИИ СВТ») — в состав комплекта прототипа системы обработки и распознавания цифровых изображений (ЗАО НЛП «Знак») — в учебный процесс на кафедре радиоэлектронных средств Вятского государственного университета.