Система и способ последовательного преобразования и кодирования цифровых данных

Система и способ последовательного преобразования и кодирования цифровых данных

Иллюстрации

Показать все

Реферат

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

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

Предшествующий уровень техники

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

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

С ростом потребности в управлении, передаче и обработке больших объемов информации также увеличивается потребность в сжатии этих данных. Хотя значительно увеличилась емкость запоминающих устройств, потребность в информации превышает достижения в развитии емкости. Например, несжатое цифровое изображение может потребовать 5 мегабайт свободного пространства, в то время как это изображение может быть сжато без потерь и потребует только 2,5 мегабайт свободного пространства. Следовательно, сжатие данных способствует передаче больших объемов информации. Даже при увеличении скоростей передачи данных, например широкополосные сети, цифровая абонентская линия (ЦАЛ), Интернет, с применением кабелей и модемов, при использовании несжатой информации легко достигаются пределы пропускной способности. Например, передача несжатого изображения через ЦАЛ линию связи может занять десять минут. Однако то же изображение при сжатии может быть передано примерно за одну минуту, следовательно, обеспечивая десятикратный выигрыш в пропускной способности данных.

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

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

Одним из наиболее известных и широко используемых способов сжатия изображения является стандарт сжатия изображения, разработанный объединенной группой экспертов в области фотографии ОГЭФ (JPEG). Стандарт JPEG функционирует путем отображения квадратного блока 8×8 пикселей в частотную область с использованием дискретного косинусного преобразования (ДКП). Коэффициенты, полученные при ДКП, делятся на масштабный коэффициент и округляются до ближайшего целого числа (процесс, известный как квантование) и затем посредством фиксированного зигзагообразного шаблона сканирования отображаются в одномерный вектор. Этот одномерный вектор кодируется с использованием комбинации кодирования Хаффмана и кодирования на основе длин серий.

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

Некоторые из недостатков JPEG смягчены в новом JPEG2000, в котором ДКП заменено на волновые преобразования. Хотя волновые преобразования обеспечивают восстановление сглаженного сигнала без искажений изображения при объединении в блоки, они могут привести к увеличению размывания и к циклическим искажениям изображения. Дополнительно JPEG2000 использует относительно сложные системы кодирования коэффициентов, что приводит к способу сжатия, который может быть в три раза 3× (или большее количество раз) медленнее, чем JPEG.

Сущность изобретения

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

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

Согласно одному конкретному аспекту изобретения обеспечивается система сжатия изображения, имеющая преобразователь цветового пространства, преобразователь с наложением (совмещением) нескольких разрешений, квантователь, развертыватель (растрового изображения в одномерный вектор) и/или статистический кодер. Преобразование с наложением нескольких разрешений выдает коэффициенты преобразования, например первые коэффициенты преобразования и вторые коэффициенты преобразования. Представление с использованием нескольких разрешений может быть получено с использованием вторых коэффициентов преобразования с наложением нескольких разрешений. Преобразователь цветового пространства преобразует входное изображение в представление цветового пространства входного изображения (например, схемы сжатия с разделением информации о яркости и цвете YUV и-или YC_oC_g). Затем представление цветового пространства входного изображения подается на блок преобразования с наложением нескольких разрешений. Квантователь принимает первые коэффициенты преобразования и/или вторые коэффициенты преобразования и выводит квантованные коэффициенты для использования развертывателем (растрового изображения в одномерный вектор) и/или статистическим кодером. Развертыватель (сканер) сканирует квантованные коэффициенты для формирования одномерного вектора, который используется статистическим кодером. Развертыватель может использовать порядок развертывания, подобный пеановскому. Статистический кодер кодирует квантованные коэффициенты, принятые от квантователя и/или развертывателя, что приводит к сжатию данных. Статистический кодер может использовать адаптивный кодер, осуществляющий кодирование на основе длин серий. Согласно другому аспекту настоящего изобретения обеспечивается система сжатия изображения, имеющая преобразователь цветового пространства, преобразование без потерь и статистический кодер. Преобразование без потерь принимает входные значения от преобразователя цветового пространства и использует преобразование без потерь (например, иерархическое преобразование Адамара).

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

Блок обратного преобразования принимает входные значения от статистического декодера и использует обратные преобразования (например, преобразование, обратное иерархическому биортогональному преобразованию с наложением или обратное иерархическому преобразованию Адамара). Блок обратного преобразования выводит выходные значения на обратный преобразователь цветового пространства. Обратный преобразователь цветового пространства преобразует входные значения (например, YUV и/или YC_oC_g) в выходное изображение в палитре «красный, зеленый, синий» КЗС (RGB).

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

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

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

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

На фиг.1 изображена структурная схема системы сжатия изображения, согласно аспекту настоящего изобретения.

На фиг.2 изображена диаграмма биортогонального преобразования с наложением, согласно аспекту настоящего изобретения.

На фиг.3 изображена структурная схема преобразования с наложением с использованием нескольких разрешений, согласно аспекту настоящего изобретения.

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

На фиг.5 изображена структурная схема преобразования с использованием нескольких разрешений, согласно аспекту настоящего изобретения.

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

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

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

На фиг.9 изображена структурная схема системы сжатия изображения, согласно аспекту настоящего изобретения.

На фиг.10 изображена диаграмма преобразования Адамара длиной 4, согласно аспекту настоящего изобретения.

На фиг.11 изображена структурная схема системы восстановления изображения, согласно аспекту настоящего изобретения.

На фиг.12 изображена блок-схема, иллюстрирующая способ кодирования/сжатия данных, согласно аспекту настоящего изобретения.

На фиг.13 изображена блок-схема, иллюстрирующая способ декодирования/восстановления данных, согласно аспекту настоящего изобретения.

На фиг.14 изображена блок-схема, иллюстрирующая способ развертывания порции коэффициентов, согласно аспекту настоящего изобретения.

На фиг.15 изображена диаграмма, иллюстрирующая компонент прямого преобразователя цветового пространства без потерь и компонент реверсивного преобразователя цветового пространства, согласно аспекту настоящего изобретения.

На фиг.16 изображена блок-схема, иллюстрирующая способ отображения цветового пространства, согласно аспекту настоящего изобретения.

На фиг.17 изображена блок-схема, иллюстрирующая способ обратного отображения цветового пространства, согласно аспекту настоящего изобретения.

На фиг.18 изображен возможный вариант операционной среды, в которой может функционировать настоящее изобретение.

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

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

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

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

На фиг.1 изображена система 100 сжатия изображения, согласно аспекту настоящего изобретения. Как отмечено выше, система 100 настоящего изобретения посредством реализации преобразования 120 с наложением (совмещением) нескольких разрешений обеспечивает последовательную визуализацию и уменьшение искажений изображения при объединении в блоки и искажений окантовки изображения по сравнению с многими стандартными системами сжатия. Система 100 сжатия изображения содержит преобразователь 110 цветового пространства, блок 120 преобразования с наложением нескольких разрешений, квантователь 130, развертыватель 140 и статистический кодер 150.

Преобразователь 110 цветового пространства отображает входное изображение в представление цветового пространства входного изображения. Затем представление цветового пространства входного изображения подается на блок 120 преобразования с наложением нескольких разрешений. В одном возможном варианте преобразователь 110 цветового пространства преобразует входное изображение в представление YUV входного изображения КЗС (например, представленное красным, зеленым и синим компонентами). Представление YUV использует компонент яркости, обозначенный Y, цветность красного, обозначенную U, и цветность синего, обозначенную V.

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

Входные компоненты КЗС отображаются в YC_oC_g (например, в качестве альтернативы стандартной схеме YUV, описанной выше) с использованием преобразования:

Следует отметить, что преимущество отображения YC_OC_G цветового пространства состоит в том, что преобразование из КЗС в YC_OC_G, и обратное преобразование из YC₀C_G в КЗС могут быть выполнены с использованием целочисленной арифметики, следовательно, уменьшая вычислительные непроизводительные затраты. Дополнительно, обратное преобразование может быть выполнено без умножения. Представление YC_oC_g цветового пространства может привести к значительно лучшей эффективности сжатия, чем широко используемое представление YUV, так как оно лучше аппроксимирует статистически оптимальные пространства, полученные при анализе основной компоненты на данных усовершенствованного цифрового изображения.

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

Блок 120 преобразования с наложением нескольких разрешений принимает входные значения, например, от преобразователя 110 цветового пространства. Блок 120 преобразования с наложением нескольких разрешений может обеспечить последовательную визуализацию в системе 100 сжатия изображения. Блок 120 преобразования с наложением нескольких разрешений использует иерархические биортогональные преобразования с наложением. При использовании преобразований с наложением могут быть уменьшены блочные искажения изображения, имеющие место в стандартных системах сжатия изображения, использующих дискретное косинусное преобразование (ДКП), например, в JPEG. Дополнительно, использование биортогонального преобразования с наложением уменьшает видимые искажения окантовки изображения по сравнению с стандартными системами сжатия изображения, основанными на ДКП.

Фиг.2 кратко иллюстрирует блок биортогонального преобразования 200 с наложением (БПН), согласно аспекту настоящего изобретения. Блок БПН 200 включает в себя блок 210 первого преобразования, подобного ДКП (например, подобного ДКП, но не идентичное ДКП), имеющее четыре входа x(0), x(1), x(2) и x(3), соответствующие первому блоку данных. Блок 200 БПН также содержит второй блок 220 преобразования, подобный ДКП, имеющий четыре входа x(0), x(1), x(2) и x(3), соответствующих второму блоку данных. Блок 200 БПН имеет четыре выхода 230, Х(0), Х(1), Х(2) и Х(3). Согласно фиг.2 при прямом преобразовании (например, кодирование/сжатие данных) данные обрабатываются слева направо, а при обратном преобразовании (например, декодирование/восстановление данных) данные обрабатываются справа налево. Для прямого (П) и обратного (О) преобразований масштабные коэффициенты могут быть различны.

Для выполнения части преобразования с наложением выход 230 для блока данных, являющихся входными для второго блока 220 преобразования, подобного ДКП, зависит от входа предыдущего блока данных, являющихся входными для первого блока 210 преобразования, подобного ДКП. В возможном варианте, где на входе нет предыдущего блока данных (например, при инициализации и/или в угловой точке (угловых точках) изображения), входные значения первого блока 210 преобразования, подобного ДКП, не будут определены полностью. Конкретно, если первый блок 210 преобразования, подобного ДКП, является первым для строки или столбца, то x(0) и x(1) выходят за пределы границы изображения. В этом случае возможное решение состоит в использовании четного симметрического расширения, устанавливающего x(1)=x(2) и x(0)=x(3). Подобное симметричное отражение применяется в последнем преобразовании 210, подобном ДКП, для строки или столбца изображения. В обоих случаях легко заметить, что первое и последнее преобразование 210, подобное ДКП, для строки или столбца может быть заменено простыми 2x2 операторами (например, два различных входа, два различных выхода).

В одном возможном варианте, по существу, все вычисления в БПН 200 могут быть выполнены с использованием только целочисленной арифметики, без умножений. Например, для заданного значения z новое значение z/2 реализуется числом, полученным при сдвиге вправо: z>>1. Далее, количество 1.25 z может быть реализовано путем сложения с z числа, полученного при двойном сдвиге z вправо (например, z+(z>>2)). Хотя эта реализация может приводить к малым ошибкам отбрасывания, порожденным сдвигами (при соответствующем масштабировании данных), примечательно, что эта реализация, в основном, является независимой от процессора, так как результат, по существу, будет одинаковым, вне зависимости от процессора, используемого для выполнения преобразования. Соответственно, по существу, все реализации систем и способов, предусмотренных настоящим изобретением, могут привести, по существу, к подобным сжатым файлам для одного исходного растрового изображения в отличие от стандартных систем сжатия данных, таких как JPEG, стандарт на сжатие изображений и звука в системах сжатия данных для записи движущегося изображения, разработанный экспертной группой по вопросам движущегося изображения ЭГДИ (MPEG), и других стандартов.

Фиг.3 кратко иллюстрирует блок 300 преобразования с наложением нескольких разрешений, согласно аспекту настоящего изобретения. Блок 300 преобразования с наложением нескольких разрешений включает блоки с первого исходного БПН 310₁ по S-е исходное БПН 310_S, где S - целое число, большее или равное единице. Блоки с первого исходного БПН 310₁ по S-е исходное БПН 310_S, вместе могут быть определены как исходное БПН 310. Блок 300 преобразования с наложением нескольких разрешений также включает блок 320 вторичного БПН. Блок 300 преобразования с наложением нескольких разрешений может использоваться, например, блоком 120 преобразования с наложением нескольких разрешений.

Блок 310 исходного БПН принимает входные значения (например, от преобразователя 110 цветового пространства). Блок 310 исходного БПН обрабатывает входные значения и выводит первые коэффициенты преобразования, основанные, по меньшей мере частично, на биортогональном преобразовании входных значений с наложением (совмещением). Блок 310 первичного исходного БПН может использовать, например, возможный вариант БПН 200, описанный выше.

Блоки с первого исходного БПН 310₁ по S-й блок 310_S первичного БПН обеспечивают первый коэффициент преобразования (первые коэффициенты преобразования) как входные данные для вторичного БПН 320. В одном возможном варианте блок 310 первичного БПН обеспечивает низкочастотный коэффициент (например, DC) для блока 320 вторичного БПН. Блок 320 вторичного БПН обрабатывает первый коэффициент преобразования (первые коэффициенты преобразования) и выводит второй коэффициент преобразования (вторые коэффициенты преобразования), основанные, по меньшей мере частично, на биортогональном преобразовании с наложением входного первого коэффициента преобразования (входных первых коэффициентов преобразования). Блок 320 вторичного БПН может использовать, например, возможный вариант БПН 200, описанный выше.

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

Фиг.4 кратко иллюстрирует преобразование 400 с использованием нескольких разрешений, согласно аспекту настоящего изобретения. Блок 400 преобразования включает в себя первый блок 410₁ первичного БПН, второй блок 410₂ первичного БПН, третй блок 410₃ первичного БПН, четвертый блок 410₄ первичного БПН и блок 420 вторичного БПН. Низкочастотный коэффициент, выведенный первым блоком 410₁ первичного БПН, вторым блоком 410₂ первичного БПН, третьим блоком 410₃ первичного БПН и четвертым блоком 410₄ первичного БПН, подается в качестве входа на вторичный БПН 420. Блок 400 преобразования с наложением нескольких разрешений может использоваться, например, блоком 120 преобразования с наложением нескольких разрешений.

Ниже, согласно фиг.5, поясняется блок 500 преобразования с наложением нескольких разрешений, согласно аспекту настоящего изобретения. Блок 500 преобразования включает в себя первичный блок БПН 510 и вторичный блок БПН 520. Выходные низкочастотные коэффициенты первичного блока БПН 510 последовательно подаются на вторичный блок БПН 520. Если от первичного блока БПН 510 было получено достаточно низкочастотных коэффициентов, то блок вторичного БПН 520 обеспечивает вывод коэффициентов второго уровня. Блок 500 преобразования с наложением нескольких разрешений может использоваться, например, блоком 120 преобразования с наложением нескольких разрешений.

Для обработки изображений используется двумерное преобразование. Для получения двумерного преобразования к строкам и столбцам входных значений (например, каждого из Y, C_o и C_g, принятых от преобразователя 110 цветового пространства) могут быть применены описанные выше преобразования БПН. В одном возможном варианте для уменьшения вычислительных непроизводительных затрат не осуществляется обработка столбцов целиком, так как каждый доступ к столбцу охватывает почти весь массив битовой карты, что потребовало бы доступа к памяти вне кэш-памяти. Вместо этого, согласно настоящему изобретению, может быть использован подход внутреннего "буфера прокрутки", при котором выполняется преобразование части столбца после обработки каждого набора из четырех строк. Таким образом, может быть рассчитано двумерное преобразование только за одно сканирование исходной битовой карты.

Согласно фиг.1 квантователь 130 принимает первые коэффициенты преобразования и/или вторые коэффициенты преобразования и выводит квантованные коэффициенты для использования развертывателем 140 и/или статистическим кодером 150. В основном потери информации в систему 100 сжатия изображения вносит квантователь 130. Потери происходят из-за квантования коэффициента, так как для преобразованного значения Y его квантованная версия обычно задается формулой r=int[(Y+f)/s], где s является размером шага квантователя 130, с модулем f, |f|, в основном равным s/2, и знаком, определяемым формулой sign(f)=sign(Y). Следовательно, при увеличении размера шага s соответствующий динамический диапазон r уменьшается, как и вероятность равенства r нулю. При восстановлении (например, при декодировании) аппроксимация Y обычно восстанавливается согласно формуле Соответственно, чем меньше размер шага s, тем ближе аппроксимация В основном при увеличении размера шага сжатие данных более эффективно, однако вносятся большие потери. В одном возможном варианте для уменьшения вычислительных непроизводительных затрат квантователь 130 использует целочисленную арифметику, например, масштабируя значения целочисленным коэффициентом Z и аппроксимируя Z/s целым числом.

Развертыватель 140 сканирует квантованные коэффициенты для формирования одномерного вектора, который используется статистическим кодером 150. В одном возможном варианте развертыватель 140 использует построчное сканирование (развертывание), в то время как в другом возможном варианте развертыватель использует сканирование по столбцам. В еще одном возможном варианте развертыватель 140 использует зигзагообразный шаблон, такой как в стандартных системах сжатия данных JPEG.

В четвертом возможном варианте квантованные коэффициенты развертываются в другом шаблоне, который остается фиксированным (не зависящим от данных) (например, во избежание случайного доступа к данным). На фиг.6 кратко изображен блок коэффициентов размером четыре на четыре, согласно аспекту настоящего изобретения. Далее, фиг.7 иллюстрирует шаблон развертывания (сканирования), подобный пеановскому, для макроблока данных, размером шестнадцать на шестнадцать (группа L блоков, в этом случае L=4), согласно аспекту настоящего изобретения. На фиг.8 изображен шаблон развертывания для блока коэффициентов второго уровня, размером четыре на четыре (например, сформированных блоками 320, 420 или 520 вторичного преобразования с наложением), согласно аспекту настоящего изобретения.

Для каждого макроблока (например, сформированного иерархическим каскадом из 4×4 преобразований) преобразованное значение считывается в одну из шести групп коэффициентов. Последовательные значения каждой группы считываются из М последовательных макроблоков ("порций"), и шесть групп соединяются в виде одного вектора, длиной 256 M, который передается статистическому кодеру. Следовательно, каждая порция может быть кодирована независимо. Независимое кодирование позволяет независимо декодировать каждую порцию, вследствие этого при необходимости обеспечивая возможность декодирования только части изображения битовой карты.

Шаблон развертывания, иллюстрируемый фиг.7 и 8, является комбинацией упорядоченного по частоте и в пространстве сканирования (развертывания) коэффициентов DC (например, которые прошли два уровня БПН) и пеановского и упорядоченного по частоте и в пространстве сканирования коэффициентов AC (например, которые прошли только первый уровень БПН). Пеановский компонент (шаблон, затененный стрелкой, на фиг.7) используется так, что для каждой группы коэффициентов AC коэффициенты АС, являющиеся соседними в определенной группе, исходят из соседних блоков 4×4.

Следовательно, Группа 0 содержит определенные коэффициенты DC второго уровня каждого макроблока, которые прошли через БПН второго уровня. Затем для каждого макроблока может быть выполнено сканирование групп с Группы 1 по Группу 5, с последующим выполнением сканирования групп с Группы 1 по Группу 5 для следующего макроблока и так далее. Группа 1 для макроблока содержит оставшиеся коэффициенты DC макроблока, прошедшие через БПН второго уровня. Группа 2 содержит иллюстрируемые значения коэффициентов для каждого блока БПН макроблока. Группа 3 содержит иллюстрируемые значения коэффициентов для каждого блока БПН макроблока. Группа 4 содержит иллюстрируемые значения коэффициентов для каждого блока БПН макроблока. Группа 5 содержит иллюстрируемые значения коэффициентов для каждого блока БПН макроблока.

Согласно фиг.1 статистический кодер 150 кодирует квантованные коэффициенты, принятые от квантователя 130 и/или устройства 140. Преобразователь 110 цветового пространства, блок 120 преобразования с наложением нескольких разрешений, квантователь 130 и/или развертыватель 140 преобразовали исходные данные элемента изображения в вектор из целых чисел с уменьшенным динамическим диапазоном и длинными строками из нулей, однако не осуществлено сжатие данных. Статистический кодер 150 кодирует эти квантованные коэффициенты, что приводит к сжатию данных.

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

Таблица: Правило кодирования на основе длин серий для старших битов с параметром k.
Кодовое слово	Входная последовательность битов
0	Выполнить серию 2k нулей
1cO	Неполная серия с <2k нулей, за которыми следует 1, знак коэффициента = ′+′ (с является k-битовым числом)
1cl	Неполная серия <2k нулей, за которыми следует 1, знак коэффициента = ′-′