Кодирование встраиваемой графики для изображений с разреженными гистограммами

Кодирование встраиваемой графики для изображений с разреженными гистограммами

Иллюстрации

Показать все

Реферат

Область техники

Настоящее изобретение, в целом, относится к сжатию данных, и, более конкретно, к сжатию данных для изображений с разреженными гистограммами.

Уровень техники

Большинство схем сжатия изображений разработаны для “естественных изображений”, то есть, фотографий, полученных цифровой камерой. В случае естественных изображений существует сильная корреляция между соседними пикселями. Поэтому, большинство схем сжатия изображений используют декорреляцию пикселей посредством прогнозирования/преобразования или оба данных метода. В результате получается разреженная гистограмма из остатков после прогнозирования или коэффициентов преобразования. На фиг.1 показана гистограмма 12 изображения 10 после дискретного косинусного преобразования (DCT) 16 8×8. Как показано на фиг.1, гистограмма 12 имеет единственный максимум 14, расположенный близко к 0. Применяется квантование (если необходимо), и выполняется статистическое кодирование (квантованного) остатков после прогнозирования или коэффициентов преобразования. Статистический кодировщик, в целом, рассчитан для распределения, аналогичного показанному на фиг.1. Другими словами, если распределение имеет существенно отличающуюся форму, производительность кодировщика будет низкой.

Однако достаточно большое количество “неестественных” изображений нуждаются в сжатии. Такие изображения часто содержат графику или текст, которые обычно имеют большой динамический диапазон контраста, резкие углы, текстуры с большим увеличением и разреженную гистограмму. На фиг.2 показан пример такого “неестественного” изображения.

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

Одна из попыток сжатия таких изображений называлась “упаковкой гистограммы”, в ходе которой кодировщик проходил через все изображение, вычислял гистограмму и выполнял нелинейное отображение пиксельных данных перед сжатием изображения. Такое сжатие требует двух проходов, что ведет к увеличению требуемой памяти и большим вычислениям. Поток битов не является масштабируемым, а это означает, что декодеру необходимо все содержание потока битов для декодирования изображения. Частичное восстановление изображения невозможно без полного декодирования.

Раскрытие изобретения

Раскрыты процессы сжатия изображений с разреженными гистограммами. Изображение делят на блоки, и ресурс битов присваивается каждому блоку. Пиксели блока преобразуют и кодируют по битовыми плоскостями, начиная с плоскости самых старших битов (MSB) и заканчивая плоскостью самых младших битов (LSB). Пиксели в блоке расположены группами. Каждая группа содержит пиксели, имеющие одинаковые значения. Группу разбивают на части, если пиксели в группе имеют разные значения в кодируемой битовой плоскости. Обработка производится для каждой битовой плоскости последовательным перемещением от плоскости MSB до плоскости LSB. Кодировщик отправляет значение “0” для группы, если все элементы в группе имеют одинаковое значение битов в текущей обрабатываемой битовой плоскости, за которым следует значение бита. Если элементы группы имеют разные значения, кодировщик разбивает группу и отправляет значение “1”, за которым следуют уточняющие биты для каждого пикселя группы.

Одним объектом настоящего изобретения является способ обработки изображения, содержащий разделение изображения на блоки первым процессором, установку ресурса битов для каждого блока, преобразование пикселей каждого блока в двоичное представление, сканирование и кодирование, начиная с плоскости самых старших битов и заканчивая плоскостью самых младших битов, генерирование файла сжатого изображения с закодированными пикселями и сохранение файла сжатого изображения в памяти, подключенной к первому процессору. Изображение содержит изображение с разреженной гистограммой. Сканирование и кодирование пикселей текущей битовой плоскости содержит обработку всех существующих групп блока, причем для каждой группы, если все пиксели имеют одинаковое значение в текущей битовой плоскости, в поток битов записывают первый бит со значением “0”, а затем записывают значение второго бита, характеризующее значение пикселей в группе, а если значения пикселей не являются одинаковыми, в поток битов записывают значение первого бита, равное “1”, за которым следуют по одному биту для каждого пикселя в текущей группе, характеризующие значение бита для данного пикселя в текущей битовой плоскости, генерируют новую группу и разделяют исходную группу, при этом пиксели со значением “0” оставляют в исходной группе, а пиксели со значением “1” помещают в новую группу. Данный способ дополнительно содержит декодирование сжатого изображения вторым процессором для разуплотнения изображения. Декодирование файла со сжатым изображением содержит обработку каждого блока начиная с MSB и заканчивая LSB, и обработку всех существующих групп для каждой битовой плоскости. Обработка группы текущей битовой плоскости содержит этапы, на которых считывают бит из потока битов, и если бит имеет значение 0, то считывают второй бит из потока битов и устанавливают данное значение в качестве значения бита для всех пикселей в группе текущей битовой плоскости, а если бит имеет значение “1”, то для каждого пикселя группы считывают один бит из потока битов и устанавливают в качестве значения бита для данного пикселя в текущей битовой плоскости, генерируют новую группу и разбивают исходную группу на две, так что пиксели со значением “0” находятся в исходной группе, а пиксели со значением “1” находятся в новой группе. Выделенный ресурс битов для каждого блока совместно используется между блоками. Первый процессор расположен в устройстве, выбранном из группы: персональный компьютер, карманный компьютер, персональный цифровой помощник, портативный персональный компьютер, сотовый/мобильный телефон, интеллектуальное бытовое устройство, игровая консоль, цифровой фотоаппарат, цифровая видеокамера, камерофон, iPod®/iPhone, видеопроигрыватель, устройство воспроизведения/записи DVD, устройство воспроизведения/записи Blu-ray®, телевизор и бытовая аудио-, видео и компьютерная система.

Другим объектом настоящего изобретения является устройство обработки изображения, содержащее первый процессор, выполненный с возможностью обработки пикселей изображения и программный модуль для разбиения изображения на блоки, установки ресурса битов для каждого блока, преобразования пикселей каждого блока в двоичное представление, сканирования и кодирования пикселей, начиная с самой старшей значащей битовой плоскости и заканчивая самой младшей значащей битовой плоскостью, и генерирования файла сжатого изображения с кодированными пикселями. Устройство дополнительно содержит память, соединенную с первым процессором, в которой хранится файл сжатого изображения. Программа выполнена с возможностью последовательного сканирования и кодирования пикселей по битовым плоскостям и для каждой битовой плоскости включает в себя обработку всех существующих групп блока, причем для каждой группы, если все пиксели имеют одинаковое значение в текущей битовой плоскости, в поток битов записывается первый бит со значением 0, а затем записывается значение бита, обозначающее значение всех пикселей в текущей группе, а если значения пикселей не имеют одинаковые значения, в поток битов записывается первый бит со значением 1, за которым следуют биты, по одному для каждого пикселя в текущей группе, обозначающие значение бита для данного пикселя в текущей битовой плоскости, генерирования новой группы и разбиения исходной группы, причем пиксели со значением 0 остаются в исходной группе, а пиксели со значением 1 размещаются в новой группе. Устройство дополнительно содержит второй программный модуль, исполняемый в первом процессоре, или второй процессор и программный модуль, выполненный с возможностью декодирования файла сжатого изображения для разуплотнения изображения. Декодер дополнительно выполнен с возможностью обработки каждого блока, начиная с MSB и заканчивая LSB, и обработки всех имеющихся групп для каждой битовой плоскости. Обработка группы текущей битовой плоскости содержит чтение битов из потока битов, и, если бит имеет значение 0, то считывание второго бита из потока битов и установки данного значения, как значения бита для каждого пикселя группы в текущей битовой плоскости, а если бит имеет значение 1, то считывание для каждого пикселя группы одного бита из потока битов и установки его в качестве значения бита для данного пикселя в текущей битовой плоскости, генерируется новая группа и исходная группа разбивается на две так, что пиксели со значением 0 остаются в исходной группой, а пиксели со значением 1 помещаются в новую группу. Выделенный ресурс битов для каждого блока совместно используется блоками. Данное устройство является одним из группы устройств: персональный компьютер, портативный персональный компьютер, автоматизированное рабочее место, сервер, ЭВМ коллективного пользования, карманный компьютер, персональный цифровой помощник, сотовый/мобильный телефон, игровая приставка, цифровой фотоаппарат, цифровая видеокамера, камерофон, iPod®/iPhone, видеопроигрыватель, устройство воспроизведения/записи DVD, устройство воспроизведения/записи Blu-ray®, телевизор и бытовая аудио-, видео и компьютерная система.

В еще одном объекте настоящего изобретения, устройство обработки изображения с разреженной гистограммой содержит первое средство обработки, выполненное с возможностью обработки пикселей изображения, средство кодирования, исполняемое в первом средстве обработки для разделения изображения на блоки, установки ресурса битов для каждого блока, преобразования пикселей каждого блока в двоичное представление, сканирования и кодирования, начиная с самой старшей значащей битовой плоскости и заканчивая самой младшей битовой плоскостью, и генерации файла сжатого изображения с кодированными пикселями, и средство хранения, соединенное с первым средством обработки, причем файл сжатого изображения хранится в средстве хранения. Средство кодирования выполнено с возможностью сканирования и кодирования пикселей по битовым плоскостям, и для текущей битовой плоскости оно содержит обработку всех существующих групп в блоке, причем для каждой группы, если все пиксели в текущей битовой плоскости имеют одинаковое значение, в поток битов записывается первый бит со значением 0, а затем записывается значение бита, обозначающее значение всех пикселей группы, а если все значения пикселей не имеют одинаковые значения, в поток битов записывается первый бит со значением 1, за которым следуют биты, по одному для каждого пикселя в текущей группе, обозначающие значение бита для данного пикселя в текущей битовой плоскости, генерирование новой группы и разбиение исходной группы, сохранение пикселей со значением 0 в исходной группе и помещение пикселей со значением 1 в новую группу. Устройство дополнительно содержит средство декодирования, выполняемое в первом средстве обработки, или второе средство обработки, соединенное с первым средством обработки, и средство декодирования выполнено с возможностью декодирования файла сжатого изображения для получения несжатого изображения. Средство декодирования содержит декодер, выполненный с возможностью декодирования файла сжатого изображения путем обработки каждого блока, начиная от MSB и заканчивая LSB, и обработки всех существующих групп для каждой битовой плоскости. Обработка группы в текущей битовой плоскости содержит считывание битов из потока битов, если бит имеет значение 0, то считывание второго бита из потока битов и установку данного значения в качестве значения бита для всех пикселей группы в текущей битовой плоскости, если бит имеет значение 1, то для каждого пикселя группы считывание одного бита из потока битов и установки его в качестве значения бита для данного пикселя в текущей битовой плоскости, генерирование новой группы и разбиение исходной группы на две, так что пиксели со значением 0 остаются в исходной группе, а пиксели со значением 1 располагаются в новой группе. Ресурс битов для каждого блока совместно используется блоками. Данное устройство является одним из группы устройств: персональный компьютер, портативный персональный компьютер, автоматизированное рабочее место, сервер, ЭВМ коллективного пользования (суперЭВМ), карманный компьютер, персональный цифровой помощник, сотовый/мобильный телефон, игровая приставка, цифровой фотоаппарат, цифровая видеокамера, камерофон, iPod®/iPhone, видеопроигрыватель, устройство воспроизведения/записи DVD, устройство воспроизведения/записи Blu-ray®, телевизор и бытовая аудио-, видео- и компьютерная система.

В еще одном объекте настоящего изобретения устройство обработки изображения с разреженной гистограммой содержит первый процессор для обработки пикселей изображения, и кодировщик, исполняемый в первом процессоре, для разделения изображения на блоки, установки ресурса битов для каждого блока, преобразования пикселей каждого блока в двоичное представление, сканирования и кодирования пикселей, начиная с самой старшей значащей битовой плоскости и заканчивая самой младшей битовой плоскостью, и генерирования файла сжатого изображения с кодированными пикселями, и запоминающее устройство, соединенное с первым устройством обработки, при этом файл сжатого изображения сохраняется в запоминающем устройстве. Кодировщик выполнен с возможностью сканирования и кодирования пикселей по битовым плоскостям, и для текущей битовой плоскости кодирования содержит обработку всех имеющихся групп в блоке, причем для каждой группы, если все пиксели в текущей битовой плоскости имеют одинаковое значение, в поток битов записывается первый бит со значением 0, а затем записывается значение бита, обозначающего значения всех пикселей группы, а если значения всех пикселей не имеют одинаковые значения, в поток битов записывается первый бит со значением 1, за которым следуют биты, по одному для каждого пикселя в текущей группе, обозначающие значение бита данного пикселя в текущей битовой плоскости, генерирование новой группы и разделение исходной группы на две, сохранение пикселей со значением 0 в исходной группе и помещение пикселей со значением 1 в новую группу. Устройство дополнительно содержит декодер, исполняемый в первом процессоре, или второе средство обработки, соединенное с первым средством обработки, и декодер выполнен с возможностью декодирования файла сжатого изображения для получения несжатого изображения. Декодер выполнен с возможностью декодирования файла сжатого изображения путем обработки каждого блока, начиная с MSB и заканчивая LSB, и обработки всех имеющихся групп для каждой битовой плоскости. Обработка группы в текущей битовой плоскости содержит считывание битов из потока битов, если бит имеет значение 0, считывание второго бита из потока битов и установку данного значения в качестве значения бита для каждого пикселя группы в текущей битовой плоскости, а если бит имеет значение 1, считывание для каждого пикселя группы одного бита из потока битов и установленного в качестве значения бита данного пикселя в текущей битовой плоскости, генерирование новой группы и разбиение исходной группы на две, так что пиксели со значением 0 остаются в исходной группе, а пиксели со значением 1 располагаются в новой группе. Ресурс битов для каждого блока совместно используется блоками. Данное устройство является одним из группы устройств: персональный компьютер, портативный персональный компьютер, автоматизированное рабочее место, сервер, ЭВМ коллективного пользования (суперЭВМ), карманный компьютер, персональный цифровой помощник, сотовый/мобильный телефон, игровая приставка, цифровой фотоаппарат, цифровая видеокамера, камерофон, iPod®/iPhone, видеопроигрыватель, устройство воспроизведения/записи DVD, устройство воспроизведения/записи Blu-ray®, телевизор и бытовая аудио-, видео- и компьютерная система.

Другим объектом настоящего изобретения является сеть устройств, содержащая устройство кодирования изображения, содержащее разделение изображения на блоки, установку ресурса битов для каждого блока, преобразование пикселей каждого блока в двоичное представление, сканирование и кодирование пикселей, начиная с самой старшей значащей битовой плоскости и заканчивая самой младшей значащей битовой плоскостью, и генерирование файла сжатого изображения с кодированными пикселями, и устройство декодирования для декодирования файла сжатого изображения путем обработки от MSB до LSB и обработки всех имеющихся групп для каждой битовой плоскости. Обработка группы текущей битовой плоскости содержит считывание битов из потока битов, и, если бит имеет значение 0, то считывание второго бита из потока битов и установку данного значения в качестве значения бита для каждого пикселя группы в текущей битовой плоскости, а если бит имеет значение 1, то считывание для каждого пикселя группы одного бита из потока битов и установки его в качестве значения бита для данного пикселя в текущей битовой плоскости, генерирование новой группы и разбиение исходной группы на две, так что пиксели со значением 0 остаются в исходной группе, а пиксели со значением 1 помещаются в новой группе. Устройство кодирования выполнено с возможностью сканирования и кодирования пикселей по битовым плоскостям, и кодирование текущей битовой плоскости содержит обработку всех имеющихся групп блока, при этом для каждой группы, если все пиксели в текущей битовой плоскости имеют одинаковое значение, в поток битов записывается первый бит со значением 0, а затем записывается значение бита, обозначающего значения всех пикселей группы, а если значения всех пикселей не имеют одинаковые значения, в поток битов записывается первый бит со значением 1, за которым следуют биты, по одному для каждого пикселя в текущей группе, обозначающие значение бита данного пикселя в текущей битовой плоскости, генерирование новой группы и разделение исходной группы на две, при этом пиксели со значением 0 остаются в исходной группе, а пиксели со значением 1 помещаются в новую группу. Ресурс битов для каждого блока совместно используется блоками.

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

Краткое описание чертежей

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

Фиг.2 иллюстрирует типичное графическое изображение.

Фиг.3 иллюстрирует блок-схему способа кодирования изображения в соответствии с некоторыми вариантами осуществления.

Фиг.4 иллюстрирует блок-схему EGC-кодирования для битовой плоскости в блоке в соответствии с некоторыми вариантами осуществления.

Фиг.5 иллюстрирует блок-схему EGC-кодирования для блока в соответствии с некоторыми вариантами осуществления.

Фиг.6 иллюстрирует блок-схему EGC-кодирования для нескольких блоков, совместно использующих ресурс битов, в соответствии с некоторыми вариантами осуществления.

Фиг.7 иллюстрирует блок-схему EGC-декодирования для битовой плоскости в блоке в соответствии с некоторыми вариантами осуществления.

Фиг.8 иллюстрирует блок-схему EGC-декодирования одного блока в соответствии с некоторыми вариантами осуществления.

Фиг.9 иллюстрирует блок-схему EGC-декодирования для нескольких блоков, совместно использующих ресурс битов, в соответствии с некоторыми вариантами осуществления.

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

Подробное описание предпочтительного варианта осуществления

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

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

Алгоритм, системы и способы используют новый процесс обработки, называемый Embedded Graphics Coding (EGC - Кодирование Встраиваемой Графики), который обеспечивает сжатие с потерями или без потерь, когда даже если декодирование остановится в середине потока битов, декодер сможет создать приемлемый декодированный блок на основе принятых битов. Если был отправлен весь поток битов, изображение может быть восстановлено без потерь.

Алгоритм, системы и способы, описанные здесь, просты и имеют высокую производительность кодирования.

На фиг.3 показана блок-схема процесса 30 кодирования изображения с разреженной гистограммой. Сначала на шаге 32 изображение разделяют на блоки. Затем на шаге 34 устанавливают ресурс битов для каждого блока. Ресурс обычно согласовывается между кодировщиком и декодером. Кодировщик и декодер могут быть выполнены с возможностью динамического изменения ресурса битов, если ширина полосы пропускания меняется со временем. Закодированный поток битов является полностью встроенным, так что ресурс битов может быть изменен произвольно.

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

Затем, на шаге 38, пиксели каждого блока сканируются и кодируются в последовательности расположения битовых плоскостей. Битовая плоскость в цифровом изображении является набором битов, имеющих одинаковую позицию в соответствующем двоичном числе. Например, в случае 8-битового представления данных существует 8 битовых плоскостей. Первая битовая плоскость содержит набор самого старшего значащего бита, а 8-я битовая плоскость содержит самый младший значащий бит.Сначала сканируется и кодируется самая старшая значащая битовая плоскость (MSB), далее процесс переходит к следующей менее значащей битовой плоскости и т.д., пока не будет отсканирована самая младшая значащая битовая плоскость (LSB). Процесс кодирования каждой битовой плоскости подробно описан далее.

На шаге 40 кодирование останавливается. Кодирование останавливается в одном из двух случаев: 1) ресурс битов для текущего блока исчерпан, или 2) если реконструируемый блок достиг конца LSB. В этом случае, декодер также определяет конец блока.

На фиг.4 показана блок-схема кодирования битовой плоскости в блоке согласно некоторым вариантам осуществления. На шаге 50 получают количество (N) существующих групп. На шаге 52 текущая группа устанавливается как группа 1. На шаге 54 алгоритм вычисляет, имеют ли пиксели текущей группы одинаковое значение бита в текущей битовой плоскости.

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

Если пиксели группы не имеют одинакового значения, на шаге 58 в битовый поток записывают значение 1, за которым следуют значения битов каждого пикселя в текущей группе. На шаге 60 генерируется новая группа без увеличения N. На шаге 62 группа разбивается на две, и пиксели со значением 0 остаются в той же группе, а пиксели со значением 1 помещаются в новую группу.

На шаге 64 кодировщик вычисляет, является ли текущая группа группой N. Если текущая группа не является группой N, то на шаге 66 процесс переходит к следующей группе и процесс возобновляется с шага 54. Если текущей группой является группа N, то кодирование текущей битовой плоскости завершается.

На фиг.5 показана блок-схема EGC-кодирования для блока согласно некоторым вариантам осуществления. На шаге 68 все пиксели блока помещаются в группу 1. На шаге 70 текущая битовая плоскость устанавливается как MSB. На шаге 72 текущая битовая плоскость кодируется с использованием способа, приведенного на фиг.4. На шаге 74 определяют, является ли текущая битовая плоскость LSB. Если текущая битовая плоскость не является LSB, то на шаге 76 процесс переходит к следующей битовой плоскости и процесс возобновляется с шага 72. Если текущей битовой плоскостью является LSB, то кодирование текущего блока завершается.

На фиг.6 показана блок-схема EGC-кодирования для нескольких блоков, которые совместно используют ресурс битов, согласно некоторым вариантам осуществления. На шаге 78 пиксели каждого блока располагают в одной и той же группе для каждого блока (пиксели разных блоков располагаются в разных группах). На шаге 80 текущая битовая плоскость устанавливается как MSB. На шаге 82 текущий блок устанавливается как первый блок. На шаге 84 текущая битовая плоскость текущего блока кодируется с использованием способа, показанного на фиг.4. На шаге 86 определяют, является ли текущий блок последним блоком. Если текущий блок не является последним блоком, то на шаге 88 процесс переходит к следующему блоку и процесс возобновляется с шага 84. Если текущий блок является последним блоком, то на шаге 90 определяют, является ли текущая битовая плоскость LSB. Если текущая битовая плоскость не является LSB, то на шаге 92 процесс переходит к следующей битовой плоскости и возобновляется с шага 82.

На фиг.7 показана блок-схема EGC-декодирования битовой плоскости в блоке согласно некоторым вариантам осуществления. На шаге 100 получают число (N) существующих битовых плоскостей. На шаге 102 текущая группа устанавливается как группа 1. На шаге 104 бит считывается из потока битов. На 106 определяют, содержит ли бит значение 0. Если его значение равно 0, то на шаге 108 считывают следующий бит из потока битов и устанавливают его значение в качестве значения всех пикселей в группе для текущей битовой плоскости. Например, если второй считанный бит равен 1, то все биты устанавливаются равными 1. Если значение бита не равно 0, то на шаге 110 биты считываются из потока битов для всех пикселей группы, и данное значение бита устанавливается как значение бита данного пикселя в текущей битовой плоскости. На шаге 112 генерируется новая группа без увеличения N. На шаге 114 группа разбивается, и пиксели со значением 0 остаются в той же группе, а пиксели со значением 1 помещаются в новую группу. На шаге 116 определяют, является ли текущая группа группой N. Если текущая группа не является группой N, то на шаге 118 процесс переходит к следующей группе. Если текущая группа является группой N, то декодирование текущей битовой плоскости завершается.

На фиг, 8 показана блок-схема EGC-декодирования одного блока в соответствии с некоторыми вариантами осуществления. На шаге 120 все пиксели блока располагают в группе 1. На шаге 122 текущая битовая плоскость устанавливается как MSB. На шаге 124 текущая битовая плоскость декодируется с использованием способа, показанного на фиг.7. На шаге 126 определяют, является текущая битовая плоскость LSB. Если текущая битовая плоскость не является LSB, то на шаге 128 процесс переходит к следующей битовой плоскости, и процесс возобновляется с шага 124. Если текущая битовая плоскость является LSB, то декодирование текущего блока завершается.

На фиг.9 показана блок-схема EGC-декодирования нескольких блоков, совместно использующих ресурс битов, согласно некоторым вариантам осуществления. На шаге 130 пиксели каждого блока помещаются в одну группу для каждого блока (пиксели разных блоков помещаются в разные группы). На шаге 132 текущая битовая плоскость устанавливается как MSB. На шаге 134 текущий блок устанавливается как первый блок. На шаге 136 текущая битовая плоскость текущего блока декодируется с использованием способа, показанного на фиг.7. На шаге 138 определяют, является ли текущий блок последним блоком. Если текущий блок не является последним блоком, то на шаге 140 процесс переходит к следующему блоку и возобновляется с шага 136. Если текущий блок является последним блоком, то на шаге 142 определяют, является ли текущая битовая плоскость LSB. Если текущая битовая плоскость является LSB, то декодирование завершается. Если текущая битовая плоскость не является LSB, то на шаге 144 процесс переходит к следующей битовой плоскости и процесс возобновляется с шага 134.

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

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

Например, если первые пять битовых плоскости были декодированы как 10110 и другие 3 битовых плоскости остались неизвестными декодеру, то истинное значение пикселя лежит в диапазоне 10110000~10110111 (в двоичном представлении). В этом случае декодер выбирает для реконструкции среднее значение и устанавливает неизвестные биты в значение 100…0. В вышеприведенном примере реконструированным значением будет 10110100.

На фиг.10 показана примерная система 200 для кодирования и декодирования графического изображения с разреженной гистограммой согласно некоторым вариантам осуществления. Необработанное изображение 202 обрабатывается первым устройством 204, содержащим процессор 206 и кодировщик 208 согласно некоторым вариантам осуществления. Устройства 204 и 214 могут быть персональным компьютером, автоматизированным рабочим местом, сервером, ЭВМ коллективного пользования (суперЭВМ), карманным компьютером, персональным цифровым помощников, сотовым/мобильным телефоном, игровой приставкой, цифровым фотоаппаратом, цифровой видеокамерой, камерофоном, iPod®/iPhone, видеопроигрывателем, устройством воспроизведения/записи DVD, устройством воспроизведения/записи Blu-ray®, телевизором, аудио-, видео и компьютерная системой или другим устройством, содержащим процессор 206 и память или другое средство 209 хранения для хранения модуля 208 кодирования. Необработанное изображение может быть впоследствии закодировано с использованием модуля 208 кодирования, содержащего средство программирования/кодирования (т.е. с помощью алгоритмов/процессов, описанных выше) для формирования файла 210 сжатого изображения. Данный файл может быть отправлен через Интернет 212 или подобную сеть на второе устройство 214. Второе устройство 214 содержит процессор 216, память или устройство 219 хранения и модуль 218 декодирования, который содержит средство программирования/декодирования, выполненные с возможностью чтения данных файла 210 сжатого изображения и его декодирования в соответствии со способами, описанными в данном документе (т.е. алгоритмами/процессами, описанными выше) для генерирования несжатого изображения 220. Необходимо понимать, что оба устройства могут включать в себя модуль 208 кодирования и модуль 218 декодирования, и наоборот, и могут выполнять как операции кодирования,так и декодирования.

Пример 1

В случае типичного 8-битового изображения половина пикселей имеет нулевое значение, а другие пиксели имеют значение 255. Расположение пикселей со значением 0 и 255 является случайным. Теоретически, по меньшей мере, 1 бит на пиксель является необходимым для выполнения сжатия без потерь. Обычные алгоритмы кодирования изображений не могут обеспечить сжатие без потерь, близкое к 1 биту на пиксель (за исключением упаковки гистограмм).

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

Для следующих битовых плоскостей посылается 00 для группы со значением 0 и 01 посылается для группы со значением 255.

Общее количество битов для блока при сжатии без потерь равно

1+n+4×7=n+29

где n соответствует количеству пикселей в блоке.

Средняя скорость передачи битов составляет (1+29/n) битов на пиксель, что близко к теоретическому пределу для рационального размера блока (т.е. когда n=8×8=64).

Алгоритм кодирования также может быть выполнен так, что если группа имеет только 1 или 2 элемента, то 1-битовый сигнал “разделен-или-нет” не отсылается, и биты детализации отсылаются напрямую.

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

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

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

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

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