СПОСОБ УПЛОТНЕНИЯ И РАСПАКОВКИ ДАННЫХ ИЗОБРАЖЕНИЯ Российский патент 2006 года по МПК H04N7/24 G06K9/36 

Данное изобретение относится к способу уплотнения и распаковки данных изображения.

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

В основанных на пикселях технологиях на изображение накладывают растр. Каждая точка растра соответствует одному пикселю. Величину пикселя кодируют с помощью одного бита (например, WBMP, что соответствует черно-белому изображению) или нескольких бит (например, BMP, что соответствует реальному цвету). Для уменьшения размера файлов изображения можно применять различные способы уплотнения. Эффективный способ состоит в уменьшении битов на каждый пиксель. Кроме того, можно применять способы, в которых пиксели объединяют в группы. Это, как правило, квадратные зоны, которые затем с помощью DCT (дискретного косинусного преобразования) преобразуют в полосу частот. Возникающими при преобразовании высокочастотными составляющими можно пренебречь без заметного ухудшения качества. Этот способ применяют, например, в изображениях JPEG. При очень большом уплотнении JPEG могут возникать мешающие, прямоугольно перемеживающиеся пятна изображения - так называемые артефакты.

В основанных на векторах способах изображение однозначно описывают с помощью геометрических форм (например, прямоугольников, окружностей). Известным способом является так называемый способ SVG (масштабируемая векторная графика). Этот способ можно прекрасно применять для технических чертежей, поскольку созданные таким образом изображения являются хорошо масштабируемыми. Соответствующие файлы значительно меньше, чем при обычных двоичных растровых форматах. Однако эти способы менее пригодны для сохранения фотоснимков.

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

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

Эта задача решена с помощью признаков пункта 1 формулы изобретения.

Предпочтительные варианты выполнения и модификации изобретения указаны в зависимых пунктах формулы изобретения.

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

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

Для воспроизведения изображения сначала загружают группы пикселей с наивысшими величинами различия пикселей (приоритетами). Из каждых трех лежащих наиболее близко друг к другу групп пикселей образуют соответствующий треугольник. Треугольники можно масштабировать по их величине и тем самым согласовывать с различными разрешениями. Если необходимо воспроизводить определенные зоны изображения особенно точно, то группы пикселей этих зон можно снабдить более высоким приоритетом. Поверхность соответствующих треугольников заполняют с помощью хода изменения цвета, который вычисляют из величин цвета соответствующих трех образующих углы треугольника групп пикселей. При черно-белых изображениях вместо величин цвета рассматривают соответствующую величину яркости пикселей, соответственно групп пикселей, и вычисляют соответствующий ход изменения яркости. Чем больше групп пикселей будет изображено, тем меньше треугольники и тем точнее можно реконструировать изображение.

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

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

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

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

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

фиг.1 - матрица изображения из 20×21 пикселей;

фиг.2 - различные формы групп пикселей;

фиг.3 - вновь генерированная матрица изображения с введенными группами пикселей в углах изображения;

фиг.4 - заполнение поверхностей между уже введенными группами пикселей;

фиг.5 - введение других групп пикселей и заполнение лежащих между ними поверхностей.

Ниже приводится описание уплотнения и распаковки видеосигнала на примере двумерного файла изображения (матрицы изображения).

При этом делаются следующие предположения:

В качестве источника изображения имеется растровое изображение, т.е. матрица изображения. Каждый пиксель матрицы изображения представлен величиной из 32 бит (величина пикселя). 32 бита разделены, например, на 4 величины (прозрачный, красный, зеленый, синий) по 8 бит в каждой.

Показанная в качестве примера матрица изображения является изображением с шириной в 20 пикселей и высотой в 21 пиксель. Позиция пикселя задана целым числом. Матрица кадра пронумерована, как показано на фиг.1, от 0 до 419. Число внутри каждой клетки соответствует положению соответствующего пикселя.

Уплотнение изображения происходит следующим образом:

Считывание матрицы изображения

Изображение считывают в показанную на фиг.1 матрицу изображения размером 20×21 пикселей. Каждый пиксель задан своей позицией (от 0 до 419) и своей величиной пикселя (величиной цвета, соответственно, яркости).

Определение групп пикселей

Сначала задают, какие смежные пиксели образуют группу пикселей. При этом р0 обозначает тот пиксель, который определяет позицию группы пикселей. Относительное положение других пикселей, например р1-р4 группы пикселей, относящихся к опорному пикселю р0, следует из примененного вида (формы) группы пикселей. На фиг.2 показаны в качестве примера некоторые возможные формы групп пикселей. Могут быть образованы как симметричные, так и несимметричные относительно опорного пикселя р0 группы пикселей. Какой вид группы пикселей применяется, зависит среди прочего от вида изображаемого материала и желаемой степени уплотнения. Как правило, достижимый коэффициент уплотнения тем больше, чем больше пикселей содержит одна группа пикселей. Для кодирования и декодирования, т.е. для уплотнения и распаковки изображения, необходимо применять одинаковую форму групп пикселей.

В дальнейшем описании способа применяется форма группы пикселей, обведенная на фиг.2 толстой линией (слева внизу).

Определение величин приоритета

Затем для каждого пикселя р0 группы пикселей вычисляют приоритет относительно этой группы пикселей. При этом каждый пиксель 0-419 изображения становится однажды опорным пикселем р0.

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

Для вычисления приоритета можно использовать различные методы вычислений. В качестве примера в данном случае применяется линейный метод.

Для этого отдельные величины Р0, Р1, Р2, Р3 и Р4 пикселей одной группы раскладывают на составляющие цвета красный, зеленый, синий. Каждую из этих величин цвета представляют 8 битами. Для каждого цвета каждого пикселя Р1-Р4 определяют величину разницы цвета относительно Р0, например, Р0_красный-Р1_красный, Р0_красный-Р2_красный,,,,. Р0_синий-Р4_синий. Абсолютные разностные величины цвета складывают и делят на число цветов и число рассматриваемых пикселей. Результат является величиной приоритета для рассматриваемой группы пикселей. Эта величина приоритета тем больше, чем больше различаются величины цвета отдельных пикселей группы.

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

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

Сортировка величин приоритета

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

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

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

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

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

Сохранение групп пикселей

Сначала сохраняют некоторые характеристики изображения. В качестве примера можно назвать:

- ширина изображения (в пикселях),

- высота изображения (в пикселях),

- примененная форма группы пикселей (нет необходимости, если стандартизована только одна форма),

- 4 группы пикселей углов изображения.

Затем сохраняют отдельные группы пикселей в соответствии с их приоритетом, т.е. сначала сохраняют группы пикселей с высоким приоритетом (а позже также сначала считывают).

Для этого сначала сохраняют величину положения опорного пикселя р0 группы пикселей. Затем сохраняют величины пикселей Р0, Р1, Р2, Р3, Р4.

Пример

Величина Р0 положения, величины пикселей Р0, Р1, Р2, Р3, Р4; следующая величина Р0 положения (с тем же или более низким приоритетом), величины пикселей Р0, Р1, Р2, Р3, Р4,..., следующая величина Р0 положения (с самым низким приоритетом), величины пикселей Р0, Р1, Р2, Р3, Р4.

Сохранение можно оптимировать с помощью различных методов, которые приводятся здесь лишь в качестве примеров. Можно осуществлять кодирование длины прохождения групп пикселей. Например, если в одной зоне изображения нет составляющих красного, то это можно передавать вместо 8 бит (красный) лишь с помощью, например, 2 бит или же можно использовать число направляющих нулей. Кроме того, можно применять широко применяемые методы уплотнения, например формат уплотнения. За счет установки предельного значения для определения приоритета можно обеспечивать определенное качество. Например, можно задать предельное значение для величин различия пикселей, ниже которого соответствующая группа пикселей всегда получает самую низкую величину приоритета.

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

Распаковка изображения

Генерирование новой матрицы изображения

Для генерирования нового изображения сначала считывают и оценивают характеристики изображения. Например, это ширина изображения, высота изображения и форма группы пикселей. Из этих величин затем создают сначала пустую матрицу изображения, аналогичную показанной на фиг.1. Если высота изображения и ширина изображения первоначального изображения не совпадают с желаемым изображением (например, ограниченный дисплей персонального цифрового секретаря или экран с большим разрешением), то необходимо применять соответствующее масштабирование. Для этого сначала определяют коэффициенты пересчета (ширина изображения_оригинал/ширина изображения_дисплей и высота изображения_оригинал/высота изображения_дисплей). Эти коэффициенты пересчета можно использовать для пересчета величины положения первоначального изображения в величину положения нового дисплея.

Ввод угловых групп пикселей

Как показано на фиг.3, затем считывают последовательно группы пикселей в соответствии с их приоритетами. Сначала во вновь генерированную матрицу изображения вводят 4 угловых группы пикселей. Положение опорного пикселя р0 соответствующей группы пикселей задается более темными полями 21, 38, 381, соответственно, 398. Эта величина положения (р0) находится в виде целого числа в сохраненном файле. Затем можно вводить в новую матрицу изображения относящиеся к соответствующей группе пикселей темно-серые величины пикселей (р1-р4). Расположенные между ними светло-серые величины пикселей можно затем вычислить из темно-серых и черных полей. Для вычисления сначала раскладывают известные величины пикселей на их составляющие части - красный, зеленый и синий. Затем вычисляют среднее значение каждого цвета, например, пиксель(22)=(пиксель(2)+пиксель(21)+пиксель(42)/3).

Заполнение поверхностей

Затем имеющиеся группы пикселей соединяют друг с другом линиями. Получаются треугольники, углы которых заданы соответствующими группами пикселей. Ниже это поясняется на примере линии между позицией пикселя 2 и позицией пикселя 17. Изменение цвета на линии вычисляют на основании величин цвета пикселей 2 и 17. Сначала определяют число пикселей между этими двумя позициями, в данном примере их 14. Затем для каждого цвета (красного, зеленого, синего) определяют цветоразность, например, величина цвета в позиции 2=2; величина цвета в позиции 17=30 дает цветоразность 28). Увеличение величины цвета на один пиксель - от пикселя 2 до пикселя 17 вычисляют как цветоразность/число пикселей (в данном примере 28/14=2).

Оставшиеся еще поверхности заполняют проведением горизонтальных линий, например, из позиции 63 в позицию 74, из позиции 82 в позицию 93 и т.д. В этом случае также вычисляют предварительный ход изменения цвета между точками, как указывалось выше.

Как показано на фиг.5, каждая дополнительно введенная группа пикселей образует дополнительные треугольники, которые можно заполнять соответствующим образом. После того как сначала заполнят всю поверхность за счет использования 4 угловых точек (21, 38, 398, 381), можно затем с помощью каждой дополнительной группы пикселей делать разрешение все более тонким. Добавление группы пикселей 87 приводит к 4 треугольникам с опорными точками (21, 38, 87), (21, 87, 381), (381, 87, 398), (398, 87, 38). Если внутри одного такого треугольника, например 87, 381, 398, добавить другую группу пикселей (247), то возникают 3 новых треугольника (247, 381, 398), (247, 87, 381) и (247, 87, 398). Таким образом, каждая новая группа пикселей создает 3 новых треугольника, которые можно заполнять. Чем больше будет введено групп пикселей, т.е. чем больше будет образовано треугольников, тем ближе подходит вычисленный ход изменения цвета к действительному ходу изменения цвета изображения. Поскольку с этого момента возникают лишь новые треугольники, то можно применять для вычисления оптимированные способы. Кроме того, соответствующие 3 вновь возникших треугольника можно вычислять параллельно для увеличения скорости обработки. Дополнительные возможности параллельной обработки возникают, если новые группы пикселей добавлять в разных зонах изображения.

Изобретение относится к способу уплотнения и распаковки данных изображения. Технический результат заключается в обеспечении простого и гибкого согласования с величиной памяти, различными разрешениями изображения и величиной дисплея. Технический результат достигается тем, что уплотнение данных изображения содержит стадии определения величины приоритета для каждого пикселя матрицы посредством задания применяемого пикселя в качестве опорного пикселя (Р0) и вычисления величины различия пикселей на основе соответствующей величины смежных пикселей заранее заданной группы пикселей (Р1-Р4); объединения использованных для вычисления величины приоритета пикселей (Р0-Р4) в одну группу пикселей; сортировки групп пикселей матрицы изображения на основе величины приоритета опорного пикселя (Р0) и сохранения и/или передачи групп пикселей в соответствии с их приоритетом, причем в соответствии с достигаемым коэффициентом сжатия сохраняется и/или передается только часть групп пикселей, начиная с групп с самым высоким приоритетом. 2 н. и 7 з.п. ф-лы, 5 ил.

1. Способ уплотнения данных изображения, которые состоят из матрицы отдельных точек изображения (пикселей), при этом каждый пиксель (0-419) имеет величину пикселя, которая описывает цветную или яркостную информацию пикселя, отличающийся тем, что содержит стадии

a) определения величины приоритета для каждого пикселя матрицы посредством задания применяемого пикселя в качестве опорного пикселя (Р0) и вычисления величины различия пикселей на основе соответствующей величины опорного пикселя относительно величин смежных пикселей заранее заданной группы пикселей (Р1-Р4);

b) объединения использованных для вычисления величины приоритета пикселей (Р0-Р4) в одну группу пикселей;

c) сортировки групп пикселей матрицы изображения на основе величины приоритета опорного пикселя (Р0) и

d) сохранения и/или передачи групп пикселей в соответствии с их приоритетом, причем в соответствии с достигаемым коэффициентом сжатия сохраняется и/или передается только часть групп пикселей, начиная с групп с самым высоким приоритетом.

a) генерирования пустой матрицы изображения из считанных характеристик изображения;

b) считывания угловых групп пикселей и ввод в четырех углах матрицы изображения;

c) образования треугольников за счет соединения соответствующих трех непосредственно смежных групп пикселей по меньшей мере одной линией;

d) заполнения образующих поверхность треугольников пикселей с помощью вычисленного из образующих треугольник групп пикселей хода изменения цвета или яркости;

e) считывания и введения следующей группы пикселей в матрицу изображения;

f) повторения стадий c)-f).