Рассылка закрыта
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
Статистика
0 за неделю
Фрактальное сжатие изображений. Введение.
Фрактальное сжатие графикиАвтор: Артём Петров, 02.03.2003
1. Фракталы и история возникновения метода фрактального сжатия Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных, работавших в период 1875-1925
гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.). В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям. 2. Математические основы фрактального сжатияИтак, рассмотрим математическое обоснование возможности фрактального сжатия.
где R – изображение, а di – какие-то (возможно, перекрывающиеся) области изображения D. Каждое преобразование wi переводит di в ri. Таким образом:
Будет логично представить изображение в виде функции двух переменных f (x, y). На множестве всех таких функций введём метрику (расстояние между изображениями), например, таким образом:
Согласно теореме Банаха, существует определённый класс отображений, для которых существует константа c < 1 такая, что для любых изображений f и g выполняется неравенство
Такие отображения называются сжимающими, и для них справедливо следующее утверждение:
то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F0:
Это конечное изображение F называют аттрактором, или неподвижной точкой отображения W. Также известно, что если преобразования wi являются сжимающими, то их объединение W тоже является сжимающим. 3. Типовая схема фрактального сжатияС учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки ri, называемые ранговыми областями. Далее для каждой области ri находят область di и преобразование wi такие, что выполняются следующие условия:
Первые три условия означают, что отображение wi будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия»). Как оказалось, практически все реальные изображения
содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.
Соответственно, для декомпрессии изображения нужно будет:
Пусть дано изображение M x N точек (где M и N кратны 8), 256 градаций серого. Ранговые и доменные области будем брать квадратными. Исходное изображение разобьём на ранговые области размером 8 х 8 точек. Доменные области будем искать размером 16 х 16 точек путём перебора всех возможных положений. Существует всего 8 аффинных преобразований, переводящих квадрат в квадрат (повороты на 0°, 90°, 180°, 270°, зеркальные отражения относительно
центральной горизонтали, центральной вертикали, от главной и побочной диагоналей). Осталось найти только коэффициенты для преобразования цвета. Но значения u и v (контрастности и яркости) можно легко найти аналитически.
Для этого достаточно приравнять частные производные R по u и по v к нулю, и решить уравнение относительно u и v. Получатся такие выражения:
при этом, если
Итак, какие же данные необходимо хранить в результате. Сетка разбиения на ранговые области постоянная для всех изображений, её хранить не надо. Остаётся положение ранговых областей (верхнего левого угла), номер преобразования и коэффициенты яркости и контрастности. 4. Оценка коэффициента сжатия и вычислительных затратРазмер данных для полного определения ранговой области рассчитывается по формуле:
где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости.
где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области. 5. Оптимизация алгоритма компрессииАлгоритм нуждается в оптимизации по нескольким направлениям: по скорости, по качеству получаемого изображения, по степени компрессии.
Для улучшения качества: в случае необнаружения доменной области, удовлетворяющей заданному E, ранговую область можно разбить на 4 подобласти и произвести поиск домена для каждой из них. Это можно делать и дальше рекурсивно, до достижения некоторого минимального размера либо единичного пиксела. Но это увеличит вычислительные затраты и снизит коэффициент сжатия. 6. РеализацияВ данной статье описываеться лишь простейший вариант алгоритма фрактального сжатия. Майкл Барнслн и Алан Слоун нашли метод решения данной задачи, который действует в отношении любого растрового изображения, даже если в нём не заметны очевидные элементы самоподобия. Все подробности этого метода не обнародованы, но то обстоятельство, что пакет Microsoft Encarta использует библиотеку сжатия Барнсли, служит достаточным свидетельством в пользу его эффективности
и обшей применимости к изображениям всех типов. 7. Ссылки http://compression.graphicon.ru/download/fractal.htm Ссылка на статью: http://fic.bos.ru/articles/APetrov_FractalGraphicsCompression.shtml
Фрактальное сжатие графикиАвтор: Артём Петров, 02.03.2003
1. Фракталы и история возникновения метода фрактального сжатия Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных, работавших в период 1875-1925
гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.). В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям. 2. Математические основы фрактального сжатияИтак, рассмотрим математическое обоснование возможности фрактального сжатия.
где R – изображение, а di – какие-то (возможно, перекрывающиеся) области изображения D. Каждое преобразование wi переводит di в ri. Таким образом:
Будет логично представить изображение в виде функции двух переменных f (x, y). На множестве всех таких функций введём метрику (расстояние между изображениями), например, таким образом:
Согласно теореме Банаха, существует определённый класс отображений, для которых существует константа c < 1 такая, что для любых изображений f и g выполняется неравенство
Такие отображения называются сжимающими, и для них справедливо следующее утверждение:
то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F0:
Это конечное изображение F называют аттрактором, или неподвижной точкой отображения W. Также известно, что если преобразования wi являются сжимающими, то их объединение W тоже является сжимающим. 3. Типовая схема фрактального сжатияС учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки ri, называемые ранговыми областями. Далее для каждой области ri находят область di и преобразование wi такие, что выполняются следующие условия:
Первые три условия означают, что отображение wi будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия»). Как оказалось, практически все реальные изображения
содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.
Соответственно, для декомпрессии изображения нужно будет:
Пусть дано изображение M x N точек (где M и N кратны 8), 256 градаций серого. Ранговые и доменные области будем брать квадратными. Исходное изображение разобьём на ранговые области размером 8 х 8 точек. Доменные области будем искать размером 16 х 16 точек путём перебора всех возможных положений. Существует всего 8 аффинных преобразований, переводящих квадрат в квадрат (повороты на 0°, 90°, 180°, 270°, зеркальные отражения относительно
центральной горизонтали, центральной вертикали, от главной и побочной диагоналей). Осталось найти только коэффициенты для преобразования цвета. Но значения u и v (контрастности и яркости) можно легко найти аналитически.
Для этого достаточно приравнять частные производные R по u и по v к нулю, и решить уравнение относительно u и v. Получатся такие выражения:
при этом, если
Итак, какие же данные необходимо хранить в результате. Сетка разбиения на ранговые области постоянная для всех изображений, её хранить не надо. Остаётся положение ранговых областей (верхнего левого угла), номер преобразования и коэффициенты яркости и контрастности. 4. Оценка коэффициента сжатия и вычислительных затратРазмер данных для полного определения ранговой области рассчитывается по формуле:
где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости.
где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области. 5. Оптимизация алгоритма компрессииАлгоритм нуждается в оптимизации по нескольким направлениям: по скорости, по качеству получаемого изображения, по степени компрессии.
Для улучшения качества: в случае необнаружения доменной области, удовлетворяющей заданному E, ранговую область можно разбить на 4 подобласти и произвести поиск домена для каждой из них. Это можно делать и дальше рекурсивно, до достижения некоторого минимального размера либо единичного пиксела. Но это увеличит вычислительные затраты и снизит коэффициент сжатия. 6. РеализацияВ данной статье описываеться лишь простейший вариант алгоритма фрактального сжатия. Майкл Барнслн и Алан Слоун нашли метод решения данной задачи, который действует в отношении любого растрового изображения, даже если в нём не заметны очевидные элементы самоподобия. Все подробности этого метода не обнародованы, но то обстоятельство, что пакет Microsoft Encarta использует библиотеку сжатия Барнсли, служит достаточным свидетельством в пользу его эффективности
и обшей применимости к изображениям всех типов. 7. Ссылки http://compression.graphicon.ru/download/fractal.htm |
В избранное | ||