Реферат по теме выпускной работы
Адаптивный вариант фрактального алгоритма сжатия и его использование к обработке медицинских изображений
Аннотация
Темой данной публикации является тема магистерской работы «Адаптивный вариант фрактального алгоритма сжатия и его использование к обработке медицинских изображений». В данной работе изложены материалы по теме магистерской работы, основные цель и задачи, которые были поставлены и решены, указаны средства и инструменты, которые использовались при работе, описаны схема работы модификаций фрактального алгоритма, произведен анализ результатов их работы, проаназизирована целесообразность использования механизмов выделения значимых областей для обработки медицинских изображений, создано приложение, реализующее первый, подготовительный этап работы адаптивного алгоритма фрактального сжатия изображений — выделение значимой области, а также второй этап — разбиение изображения на блоки. Сделаны выводы по работе алгоритмов, обоснован выбор модификаций для дальнейшего применения к оцифрованным медицинским изображениям.
Содержание
1 Введение
Актуальность
Изображения широко используются в различных сферах, как повседневной жизни человека, так и в конкретных областях науки. Медицинские изображения относятся к классу очень информативных, т.е. изображения такого класса несут большое количество данных, которые очень важны для дальнейшего анализа, которыми нельзя пренебречь. В тоже время такие изображения зачастую имеют большие размеры, что может вызывать сложности при работе с ними. В связи с этим при обработке изображений такого рода следует аккуратно варьировать соотношение степени сжатия и потерь качества изображения.
Одним из вариантов решения этой дилеммы может быть применение алгоритмов выделения значимых областей. Такой подход позволяет разделять все изображения на части и к каждой из частей применять определенный алгоритм сжатия. Для части, представляющей большой интерес, целесообразным является применять алгоритмы сжатия без потерь или задавать параметры, обеспечивающие малую погрешность. А другую часть — исключать из процесса компрессии. Таким образом, в результате обработки такой алгоритм может позволить достичь малого размера файла на выходе и незначительных потерь информации, поэтому разработка адаптивного алгоритма сжатия, который бы обеспечил незначительную погрешность сжатия является актуальной.
Цели и задачи, которые должны решаться
Цель работы состоит в проведении сравнительного анализа существующих методов модификации фрактального алгоритма сжатия, проверить возможность и целесообразность реализации алгоритмов выделения значимых областей медицинских изображений. В качестве критерия для сравнения предлагается анализировать основные характеристики результата работы методов и их этапы работы применительно к медицинским изображениям (время кодированния, декодирования, коэффициент сжатия)
Идея работы — разработка новой модификации метода фрактального алгоритма сжатия с применением алгоритма выделения значимых областей. Для достижения указанной цели в магистерской работе поставлены и решены следующие задачи:
- описать требования и этапы создания программного продукта для обработки медицинских изображений
- подготовить изображения для анализа
- проанализировать особенности функционирования существующих техник выделения значимых областей изображения и целесообразность применения алгоритмов выделения значимых областей для дальнейшего их сжатия с использованием фрактального алгоритма
- составить сравнительный анализ модификаций фрактального алгоритма на этапе подбора домен-ранг
- описать алгоритмы функционирования выбраных модификаций
- разработка соответствующих программных компонент, проведение экспериментов, сравнительные результаты работы
- сделать выводы о целесообразности применения фрактального алгоритма сжатия к медицинским изображениям (акцент сделать на потерю качества)
Предмет исследования — фрактальные алгоритмы сжатия изображений с потерями.
Объект исследования — модификации фрактального алгоритма сжатия изображений.
Методы исследования включают обзор литературных и интернет источников, проведение вычислительных экспериментов, сравнительный анализ результатов, работу предполагается проводить с использованием численных методов.
Предполагаемая научная новизна
Научная новизна уже проведенных и планируемых в работе исследований предполагается в следующем:
- Анализ применимости техник выделения значимых областей изображения.
- Анализ применимости модификаций фрактального алгоритма для подбора пары домен-ранг: FE-алгоритм, алгоритм, использующий значение коэффициента корреляции Пирсона, алгоритм, использующий значение энтропии блоков.
- Анализ применимости нелинейных моделей отображений блоков изображений.
- Анализ механизмов реализации работы выбранных модификаций алгоритма в программном обеспечении.
- Обоснование целесообразности применения перечисленных модификаций для обработки оцифрованных медицинских изображений.
Планируемые практические результаты
Планируется реализовать адаптивный алгоритм фрактального сжатия изображений, обеспечивающий достаточно малую погрешность, которая бы позволила проводить дальнейший анализ специалистом (медицинским работником). Для этого является целесообразным реализовать для пользователя выбор области интереса и просмотр результата.
2 Степень научной разработанности и нерешенные проблемы
В большинстве работ, посвященных теме выделения значимых областей выделяют методы, основанные на особенностях морфологического строения изображения, на цветовых показателях характеристик изображения или вручную путем задания прямоугольной области. Под структурными особенностями понимается неоднородность изображения с точки зрения наличия в нем так называемых областей постоянства, где все пиксели имеют одинаковый или близкий по значению оттенок цвета, и областей с большим количеством мелких деталей, где соседние пиксели существенно отличаются по цвету. Одним из вариантов выделения этих областей является использование статистических характеристик, определяемых по гистограмме яркости. В случае, когда область интереса определяется, исходя из границ объектов, присутствующих в изображении, выделение границ областей изображения может быть выполнено с использованием операций морфологической обработки изображений: дилатации, эрозии, центрального отражения и параллельного переноса [1].
В современных вычислительных пакетах реализованы возможности создания маски изображения. Так, например MatLab предлагает создание маски путем задания полигона. Для этого используется функция poly2mask(x,y,m,n), где x,y — индексы пикселей исходной маски изображения, образующие полигон маски, m,n – матрица изображения.
В первые понятие фрактального сжатия изображений было введено в 1990 году британским математиком Майклом Барнсли [2]. В настоящее время тема ускорения фрактальных алгоритмов сжатия активно изучается. Исследования ведутся в нескольких направлениях.
Условно все существующие модификации можно разделить на классы: характеристические, по особенностям структуры алгоритма.
К первой группе можно отнести следующие алгоритмы: FE-алгоритм, использование коэффициента корреляции Пирсона, классификация блоков (яркостная конфигурация блока).
Ко второй группе: использование обрамляющих доменов, использование пирамидального метода сравнения, квадро-дерево и его модификации.
Кроме того особого внимания заслуживают алгоритмы: с использованием нелинейного отображения, алгоритмы базирующиеся на учете частоты использования доменов, в том числе основанный на значениях энтропии доменных блоков, дискретное преобразование Крестенсона-Леви (ДПКЛ), использование карт Кохонена.
В глобальном масштабе данная тема широко исследуется современными учеными. При анализе литературы по данной тематике было отмечено, что большой интерес для исследователей разных стран составляют алгоритмы с использованием обрамляющих доменов. В работах иностранных авторов часто упоминается метод для уменьшения времени кодирования за счет сокращения размера бассейна доменов на основе стоимости энтропии каждого доменного блока. Экспериментальные результаты на стандартных изображениях показывают, что предложенный метод дает превосходную производительность по сравнению с обычными алгоритмами фрактального кодирования. Этот метод основан на удалении доменного блока с высокой энтропией, применим в ситуациях, когда требуется очень малое время кодировки и допускается ухудшение качества и является весьма сопоставимым с другими методами ускорения[3].
В переделах Украины следует выделить таких исследователей как Ватолин Д.С., Умняшкин С.В., Илюшин С.В., Свет С.Д., Прохоров В.Г. Умняшкин С.В. предлагает относительно новое направление в модернизации фрактальных методов - алгоритмы, основанные на минимизации RD-функции Лагранжа. В качестве начальных данных берется некоторый входной набор данных, которому в результате выполнения процедуры сжатия-восстановления ставится в соответствие выходной набор данных той же природы, Y=F(X,u), где u — набор управляющих параметров алгоритма сжатия F. Можно настраивать алгоритм кодирования F на необходимые характеристики [4]. Прохоров В.Г. описывает целесообразность использования самообучаемых карт Кохонена для ускорения процедуры поиска лучшего домена для ранга [5]. Метод использует следующие положения: алгоритм настроен на поиск наилучшего соответствия доменных и ранговых блоков, на вход поступает цветное изображение размером 256 х 256 пикселов, домены берутся из шаблонного изображения размером 500 х 375 пикселов, общее число ранговых блоков равнялось 4096, доменных – 90528, алгоритм классификации связывает каждый домен с одним из классов. При кодировании алгоритм связывает данный ранговый блок с определенным классом, и после этого доменно-ранговое сопоставление проводится только с доменами, отнесенными к этому классу (и, возможно, с другими подобными классами). Илюшин С.В. предлагает использовать коэффициент корреляции Пирсона для ускорения процесса предлагается в качестве критерия оптимальности использовать коэффициент корреляции Пирсона. Чем лучше реальная зависимость R от D аппроксимируется линейной, тем ближе по модулю к 1 будет их коэффициент корреляции. Использование этого коэффициента позволяет сразу оценить оптимальность текущего домена для данного ранга, без расчета коэффициента преобразования контраста и яркости. Таким образом, эти коэффициенты рассчитываются один раз для каждого ранга [6]. Ватолин Д.С. описывает возможность применения дискретного псевдокосинусного преобразования (ДПКП) [7], на базе которых возможно получать схему компрессии статических изображений (аналогична методу JPEG). Для обработки неподвижных и динамических изображений предлагаются формализующие процедуры анализа и синтеза схем компрессии цифровых изображений на основе дискретных ортогональных преобразований. Оценки вычислительных затрат показывают, что алгоритм на основе ДПКЛ не уступает JPEG в том числе в части, касающейся вычислительной сложности реализации.
Среди работ студентов, аспирантов ДонНТУ следует выделить работы Авлеевой А.Н. [8], которая создала систему создания и обработки фракталов, Бубличенко А. [9], который провел экспериментальный анализ сущействующих методов модификаций фрактального алгоритма, на этапах разбиения изображения на блоки и сравнения пар домен-ранг. Научным руководителем этих магистров является к.т.н., доцент кафедры КСМ, Беловодский Валерий Николаевич.
3 Описание исследований
Предполагается реализовать следующие этапы адаптивного алгоритма:
- Выделение значимой области (прямоугольная, в частном случае квадратная область, задаваемая пользователем)
- Разбиение исходного изображения на домены и ранги с использованием классического алгоритма и алгоритма квадродерево
- Подбор пары домен-ранг путем применения FE-алгоритма, алгоритма, использующего коэффициент корреляции Пирсона, алгоритма, использующего показатель энтропии, алгоритм, основанный на применении нелинейного отображения
- Сжатие изображения
- Декомпрессия
- Оценка погрешности
Выделение значимой области
Для реализации этапа выделения значимой области было создано приложение на языке MatLab. Область интереса задается двумя противоположными точками предполагаемой области прямоугольной формы (верхняя левая и правая нижняя). После этого выбранная область выделяется на исходном изображении линиями синего цвета (по контуру). При нажатии на кнопку “PolyMask” происходит отсечение той части изображения, которая лежит вне выбранной области. Таким образом получили новое изображение, которое непосредственно будет сжиматься (см. Рисунок 1).
Рисунок 1 — Визуализация подготовительного этапа работы алгоритма — Выделение значимой области изображения. Анимация состоит из 4 кадров с задержкой в 80 мс между кадрами; задержка до повторного отображения состоит 400 мс; количество циклов отображения ограничено 10-ю.
Следующим этапом работы алгоритма является разбиение на блоки (домены и ранги). Этот этап являтся одинаковым для всех модификаций алгоритма, принимающих участие в анализе, так как оссобенность их работы проявляется на этапе поиска пары домен-ранг.
Для детального анализа были выбраны 3 модификации, предположительно показывающие наиболее приемлемые результаты. Это:
- FE-алгоритм [9]
- использование коэффициента корреляции Пирсона [6]
- показатель энтропии [3]
- алгоритм, использующий нелинейное отображение [10,11] .
Предложенные модификации применяются на этапе поиска пары домен-ранг.
4 Заключение
Создано приложение, реализующее первый (выделение значимой области) и второй этап (разбиение на блоки). Подготовлены изображения для обработки. Проведен анализ существующих модификаций алгоритма сжатия изображений (этапы работы и возможные результаты работы, характеристики — время кодирования, коэффициент сжатия, погрешность сжатия для изображений в градациях серого с плавными переходами). Были сделаны следующие выводы:
| Название | Время кодирования | Средняя пиксельная ошибка | Коэффициент сжатия |
| FE-алгоритм | ускорение в 8-10 раз | уменьшение на 9% | уменьшается на 12-37% |
| Использование коэффициента корреляции Пирсона | ускорение в 9,35 раза | повышение качества | Увеличение |
| Энтропия | Существенное ускорение по сравнению с методом Фишера | Практически совпадает с оригинальным при декодировании | практически такой же |
| Нелинейное отображение | Уменьшение до 58% | Малы | Может увеличиваться не больше чем на 11% |
5 Литература:
- Самира Эбрахими Кахоу, Адаптивный способ сжатия изображений [Текст] // Вісник Хмельницького національного університету, №2 ’2010. – 295 с.
- Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Methods and apparatus for image compression by iterated function system. United States Patent 4941193, July 10, 1990
- Venkata Rama Prasad VADDELLA, Ramesh Babu INAMPUDI [Электронный ресурс]//Journal of Applied Computer Science & Mathematics, no. 9 (4), 2010, Suceava, http://jacs.usv.ro/getpdf.php?paperid=9_3
- Umnyashkin S. V. Mathematical methods and algorithms for digital image compression using orthogonal transformation, Abstract, 2001 — 569 pp.
- Prokhorov V.G. Using Kohonen maps to accelerate fractal image compression // Applied Software, № 2, 2009 — S. 7.
- Илюшин С.В. Фрактальное сжатие телемедицинских изображений [Электронный ресурс], http://www.elsv.ru/files/actual/130.pdf
- Ватолин Д.С. Использование ДКП для ускорения фрактального сжатия изображений// Журнал «Программирование», №3, 1999, 51—57 с.
- Авлеева А.Н. Фрактальное сжатие изображений. Решение задач сжатия изображений с использованием систем итерированных функций. Магистерская диссертация, ДонНТУ, 2006 [Электронный ресурс] http://masters.donntu.ru/2006/fvti/avleeva/index.htm
- Bublichenko A.V. Algorithms for image compression: a comparative analysis and modification // Qualification Masters work, 2008, 150 pp.
- Кроновер Р.М. Фракталы и хаос в динамических системах // Основы теории. – М.: Постмаркет, 2000
- Гмурман В.Е. Теория вероятностей и математическая статистика // Учеб. пособие для ВУЗов, 10-е изд. стер. — М.: Высшая школа, 2004. — 479 с.