Методы обхода плоскости. Обход зигзагом.
Обход массива начинается с одного угла плоскости, заканчивается в противоположном по диагонали. Например, из левого верхнего в правый нижний:
1 |
2 |
6 |
7 |
15 |
16 |
3 |
5 |
8 |
14 |
17 |
24 |
4 |
9 |
13 |
18 |
23 |
25 |
10 |
12 |
19 |
22 |
26 |
29 |
11 |
20 |
21 |
27 |
28 |
30 |
Применяется в алгоритме JPEG для обхода квадрантов (размером 8x8 точек).
Методы обхода плоскости. Квадратная змейка.
Рекурсивный метод для квадратных областей. Если принять левый верхний элемент за первый, то для квадрата 2x2 возможны два варианта обхода без разрывов:
1 |
4 |
2 |
3 |
и |
|
1 |
2 |
4 |
3 |
если нужно выйти к правому (или верхнему) квадрату, то первый шаг - вниз, если к нижнему (или левому), то первый шаг - вправо;
• пройденным путем однозначно задается, к какому квадрату нужно выйти в каждый конкретный момент;
• только в самом начале есть выбор одного из двух вариантов обхода.
•если нужно выйти к правому (или верхнему) квадрату,
то первый шаг - вниз, если к нижнему (или левому), то
первый шаг - вправо;
•пройденным путем однозначно задается, к какому квадрату нужно выйти в каждый конкретный момент;
•только в самом начале есть выбор одного из двух вариантов обхода.
Алгоритмы сжатия изображений без потерь. Rle.
Методы сжатия без потерь разделяют на
две категории:
Методы сжатия источников данных без памяти (т.е. не учитывающих последовательность символов)
Методы сжатия источников с памятью
Сжатие без потерь
Данный алгоритм необычайно прост в реализации. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.
В
данном алгоритме признаком счетчика
(counter) служат единицы в двух верхних
битах считанного файла. Соответственно
оставшиеся 6 бит расходуются на счетчик,
который может принимать значения от 1
до 64. Строку из 64 повторяющихся байтов
мы превращаем в два байта, т.е. сожмем в
32 раза.
RLE –первый вариант.
Алгоритм рассчитан на деловую графику— изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того, чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Данный алгоритм реализован в формате PCX.
RLE –Второй вариант.
В
торой
вариант этого алгоритма имеет большую
максимальную степень сжатия и меньше
увеличивает в размерах исходный файл.
Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта.
Как можно подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта. Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.
К положительным сторонам алгоритма RLE можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает.
Общие характеристики алгоритма RLE:
Коэффициенты компрессии: Первый вариант: 32, 2, 0,5. Второй
вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты)
Класс изображений: Ориентирован алгоритм на изображения с
небольшим количеством цветов: деловую и научную графику.
Симметричность: Примерно единица.