Способ сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов
Владельцы патента RU 2541203:
Государственное казенное образовательное учреждение высшего профессионального образования Академия Федеральной службы охраны Российской Федерации (Академия ФСО России) (RU)
Изобретение относится к вычислительной технике. Технический результат заключается в сокращении времени сжатия графического файла фрактальным методом. Способ сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов, в котором графический файл разбивают на ранговые области и домены, и для каждой ранговой области находят домен и соответствующее аффинное преобразование, которое наилучшим образом приближает его к соответствующей ранговой области, и, используя полученные значения параметров доменов, включающие их координаты, коэффициенты аффинных преобразований, значения яркости и контрастности, формируют архив, причем вводят классификацию доменов и ранговых областей, основанную на выделении в них «колец» и расчете математического ожидания интенсивностей пикселей данных «колец», позволяющую сократить сложность этапа соотнесения сегментов и ускорить сжатие. 3 ил.
Изобретение относится к области цифровой обработки графических файлов, а именно к методам сжатия и может быть использовано для обеспечения эффективного хранения или передачи по каналам связи сформированного сжатого файла.
Известен «Способ совместного использования векторного квантования и фрактального кодирования изображений» (патент RU 2316908 C2, МПК H04N 7/26, опубликовано: 10.02.2008), в котором предлагается комбинировать фрактальный способ сжатия с векторным квантованием, за счет использования готовой библиотеки доменов, сформированной заранее.
Недостатком данного способа является резкое повышение сложности выполнения этапа соотнесения ранговая область - домен за счет увеличения размера библиотеки доменов, а также сложность обратной декомпрессии.
Также известен «Способ передачи дополнительной информации при фрактальном кодировании изображения» (патент EP 0742672 A2, МПК G06T 9/00, опубликовано: 13.11.1996), в котором для поиска соответствующего домена используется стратегия дерева поиска.
Недостатком данного способа является то, что за счет использования данной стратегии происходит увеличение времени сжатия графического файла и потеря возможности использования всей библиотеки доменов, что сказывается на качестве сжатия.
Наиболее близким по технической сущности и выполняемым функциям является «Способ повышения скорости кодирования при совместном использовании векторного квантования и фрактального кодирования» (патент RU 2321184 C2, МПК H04N 7/40, G06T 9/00, опубликовано: 27.03.2007), в котором домены, хранящиеся в кодовой книге классифицируются алгоритмом Фишера.
Недостатком этого способа является потеря соответствия между доменами и ранговыми областями при декомпрессии, так как восстановление зависит от исходной точки и расположения доменов, что в случае использования кодовой книги невозможно, также при поиске исключается множество доменов за счет грубой системы классификации.
Задачей изобретения является создание способа сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов, обеспечивающего сокращение времени сжатия графического файла фрактальным методом.
Эта задача решается тем, что в способе сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов, заключающемся в том, что графический файл разбивают на ранговые области и домены, и для каждой ранговой области находят домен и соответствующее аффинное преобразование, которое наилучшим образом приближает его к соответствующей ранговой области, и, используя полученные коэффициенты, формируют архив, вводят кольцевую классификацию доменов и ранговых областей, позволяющую сократить сложность этапа соотнесения сегментов и ускорить сжатие.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественным всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявляемый способ соответствует условию патентоспособности «изобретательский уровень».
«Промышленная применимость» изобретения обусловлена тем, что устройство, реализующее предложенный способ, может быть осуществлено с помощью современной элементной базы, с достижением указанного в изобретении назначения.
Заявленный способ сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов поясняется чертежами, на которых показано:
фиг.1 - разбиение сегмента изображения для реализации кольцевой классификации, где A1, A2 ,..., An - математическое ожидание интенсивностей пикселей соответствующих сегментов;
фиг.2 - алгоритм, описывающий реализацию предложенного способа;
фиг.3 - график, описывающий результаты применения сравниваемых алгоритмов классификации.
Реализация предложенного способа состоит во включении в процесс фрактального сжатия этапа кольцевой классификации сегментов. Общий алгоритм фрактального сжатия первоначально подразумевает ввод параметров сжатия (Уэлстид С. Фракталы и вэйвлеты для сжатия изображений в действии: Учебное пособие. Пер. с англ. - М.: «Издательство Триумф», 2003. - с.78). В качестве параметров сжатия выступают минимальный размер домена, минимальный шаг домена, значение порога среднеквадратического отклонения (СКО), глубина квадродерева.
После ввода параметров сжатия в систему загружается исходное изображение, предназначенное для сжатия. Первым этапом реализуется разбиение изображения на домены (Уэлстид С. Фракталы и вэйвлеты для сжатия изображений в действии: Учебное пособие. Пер. с англ. - М.: «Издательство Триумф», 2003. - с.81). Минимальный размер домена указан в начальных параметрах. Также выделяются домены большего размера, причем для более эффективного расчета, каждые следующие группы доменов больше предыдущих в два раза. Максимально возможный размер домена выбирается в соответствии с размерами исходного изображения.
На следующем этапе происходит выделение ранговых областей, при этом они должны полностью заполнять все изображение и не пересекаться друг с другом. Ранговые области в соответствии с алгоритмом меньше доменов по ширине в два раза.
После формирования библиотеки доменов и определения рангов осуществляется основной этап соотнесения ранговых областей и доменов (Уэлстид С. Фракталы и вэйвлеты для сжатия изображений в действии: Учебное пособие. Пер. с англ. - М.: «Издательство Триумф», 2003. - с.86). Он происходит путем подбора соответствующих рассматриваемому рангу доменов.
Схожесть доменов и рангов определяется по методу наименьших квадратов (МНК). Исследуемый домен подвергается аффинным преобразованиям для обеспечения максимального сходства с рангом, после чего по значению, полученному по МНК, принимается решение о продолжении поиска соответствия. Аффинные преобразования подразумевают под собой такие операции над сегментами изображения, как зеркальное отображение, поворот на углы в 90, 180, 270 градусов (Уэлстид С.Фракталы и вэйвлеты для сжатия изображений в действии: Учебное пособие. Пер. с англ. - М.: «Издательство Триумф», 2003. - с.51). Также возможно применение масштабирования. В параметрах сжатия заранее указывается минимальный порог СКО, получаемый при расчете значения по МНК, чем он ниже, тем качественнее будет сжатое изображение, но увеличивается время компрессии и наоборот. В случае если для ранговой области не будет найден подходящий домен, реализуется метод квадродерева (Уэлстид С. Фракталы и вэйвлеты для сжатия изображений в действии: Учебное пособие. Пер. с англ. - М.: «Издательство Триумф», 2003. - с. 83), при котором ранговая область разбивается на 4 равные части и с ними проводятся аналогичные действия.
После выполнения этапа соотнесения рангов и доменов, формируется архив, состоящий из заголовка, в котором указаны параметры сформированного сжатого файла, и поля данных, содержащего координаты соответствующих доменов, коэффициенты аффинных преобразований и значения яркости и контрастности.
В предлагаемом способе вводится этап классификации сегментов графического файла (фиг.2). Реализация данного этапа происходит следующим образом. Выделенные на первом этапе фрактального сжатия графических файлов домены распределяются в зависимости от их размеров, чаще всего используются степени 2, то есть минимальным доменом является сегмент с шириной 4, так как минимальная ранговая область имеет ширину 2, а домен всегда больше ранговой области. В предлагаемом алгоритме для удобства ранговая область всегда меньше в 2 раза соответствующего домена и все сегменты имеют форму квадрата. Соответственно, формируются массивы доменов с размерами 4, 8, 16 и так далее до максимально возможного значения для исходного графического файла. Для каждого массива доменов проводится классификация с целью сокращения сложности этапа соотнесения ранговая область - домен. В предлагаемом способе классификация осуществляется за счет выделения «колец» в сегментах и расчета их математического ожидания интенсивностей пикселей. Суть метода заключается в выделении «колец» толщиной в один пиксель (фиг.1). Минимальным кольцом для всех сегментов является квадрат шириной 2. Таким образом, в каждом сегменте можно выделить число «колец», равное половине ширины, например для домена размера 8, формируется 4 «кольца». Для выделенных колец значения интенсивностей всех пикселей суммируются и сумма делится на их количество, тем самым для каждого домена формируется вектор значений математических ожиданий интенсивностей пикселей «колец». Аналогичные действия проводятся с ранговыми областями на этапе их выделения. После проведения расчета математического ожидания интенсивностей пикселей «колец» всех сегментов осуществляется формирование возможных пар ранговая область - домен. В способе предлагается использовать интервал, равный 25, что подразумевает под собой формирование классификационных выборок на основе предложенного интервала, причем последний интервал расширен до 30, так как максимальное значение интенсивности пикселя 255. Значение размера интервала подобранно эмпирическим путем и является наиболее приемлемым в плане количества классов и эффективности дальнейшего поиска соответствий. Фактически для каждого возможного размера сегмента формируется пул, с конкретными параметрами, например для домена размера 8 первый класс будет задан через интервалы для первого кольца 0-25, второго 0-25, третьего 0-25 и четвертого 0-25. Следующий класс соответственно имеет значение первого интервала 25-50, остальные не изменяются и так далее для всех возможных сегментов. Таким образом, на этапе соотнесения ранговая область - домен задача поиска соответствий упрощается в сотни раз. Использование разбиения сегментов на «кольца» связано с фрактальным подходом, так как при выполнении аффинных преобразований сегменты подвергаются поворотам и выгоднее использовать классификацию по параметрам, не зависящим от них, иначе приходится подбирать классификационный признак для каждого возможного аффинного преобразования. Также очевидным является то, что подобные сегменты должны быть по значениям интенсивностей пикселей «колец» близки, что объясняется самой природой графических файлов. Предлагаемый способ в данном смысле является универсальным для всех преобразований и позволяет без значительного увеличения сложности сократить время сжатия.
Эффективность функционирования предлагаемого способа по сравнению с прототипом состоит в том, что сокращается время выполнения этапа соотнесения ранговая область-домен, что приводит к снижению длительности общего времени сжатия без заметного изменения качества.
Реализация предложенного способа показала эффективность его применения. На основе сформированной модели, построенной в программном обеспечении MatLab, проведен анализ длительности сжатия одного и того же изображения на основе сравниваемых алгоритмов классификации (фиг.3). На диаграмме видно, что сжатие одного и того же исходного графического файла происходит быстрее при использовании заявленного способа, при этом значение PSNR (инженерный термин, означающий соотношение между максимумом возможного значения сигнала и мощностью шума, искажающего значения сигнала), при прочих равных параметрах сжатия, повысилось. Таким образом, можно сделать вывод, что применение данного способа позволяет сократить длительность сжатия изображения без ухудшения качества.
Способ сжатия графического файла фрактальным методом с использованием кольцевой классификации сегментов, заключающийся в том, что графический файл разбивают на ранговые области и домены, и для каждой ранговой области находят домен и соответствующее аффинное преобразование, которое наилучшим образом приближает его к соответствующей ранговой области, и, используя полученные значения параметров доменов, включающие их координаты, коэффициенты аффинных преобразований, значения яркости и контрастности, формируют архив, отличающийся тем, что вводят классификацию доменов и ранговых областей, основанную на выделении в них «колец» и расчете математического ожидания интенсивностей пикселей данных «колец», позволяющую сократить сложность этапа соотнесения сегментов и ускорить сжатие.
