сжатие изображения с использованием дискретного косинусного преобразования адаптивно определенного размера блока на основании дисперсии

Формула изобретения

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

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

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

4. Способ по п. 1, в котором упомянутую дисперсию определяют в соответствии со следующим уравнением:

где N - размерность блока;

х_i,j - пиксель в i-й строке, j-м столбце в блоке NxN.

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

6. Система по п.5, в которой упомянутый порог изменяется для каждого уровня подразделения.

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

8. Система по п.5, в которой упомянутое средство преобразования выполняет дискретное косинусное преобразование.

9. Система по п.5, в которой упомянутое средство преобразования выполняет дискретное косинусное преобразование с последующим дифференциальным преобразованием дерева квадрантов.

10. Система по п.5, в которой упомянутое средство преобразования в последовательную форму содержит устройство зигзагообразного сканирования.

11. Система по п.10, в которой упомянутое устройство зигзагообразного сканирования использует размер 8х8 блока для зигзагообразного сканирования.

12. Система по п.5, в которой упомянутое средство кодирования с переменной длиной содержит кодировщик Хаффмана.

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

14. Система по п. 13, в которой имеются три просмотровые таблицы.

15. Система по п.5, в которой упомянутую дисперсию определяют в соответствии со следующим уравнением:

где N - размерность блока;

х_i,j - пиксель в i-й строке, j-м столбце в блоке NxN.

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

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

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

19. Способ по п.16, в котором упомянутое дискретное косинусное преобразование выполняют во время упомянутого этапа преобразования.

20. Способ по п.16, в котором дискретное косинусное преобразование выполняют с последующим дифференциальным преобразованием дерева квадрантов во время упомянутого этапа преобразования.

21. Способ по п.16, в котором зигзагообразное сканирование выполняют во время упомянутого этапа сканирования.

22. Способ по п.21, в котором упомянутое зигзагообразное сканирование выполняют с использованием размера блока 8×8.

23. Способ по п.16, в котором кодирование Хаффмана выполняют во время упомянутого этапа кодирования.

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

25. Способ по п.24, в котором имеются три просмотровые таблицы.

26. Способ по п.16, в котором упомянутую дисперсию определяют в соответствии со следующим уравнением:

где N - размерность блока;

х_i,j - пиксель в i-й строке, j-м столбце в блоке NxN.

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

28. Система по п.27, в которой упомянутый порог изменяется для каждого уровня подразделения.

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

30. Система по п.27, в которой упомянутое средство преобразование использует дискретное косинусное преобразование.

31. Система по п.27, в которой упомянутое средство преобразование использует дискретное косинусное преобразование с последующим дифференциальным преобразованием дерева квадрантов.

32. Система по п.27, в которой упомянутое средство сканирования использует зигзагообразное сканирование.

33. Система по п.27, в которой упомянутое средство кодирования использует кодирование Хаффмана.

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

Описание изобретения к патенту

I. Область изобретения

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

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

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

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

Один способ сжатия, способный предложить значительные уровни сжатия и в то же время сохраняющий желаемый уровень качества для видеосигналов, использует блоки и подблоки адаптивно определенных размеров закодированных данных коэффициентов дискретного косинусного преобразования (ДКП). Этот способ далее будет упоминаться как способ дифференциального косинусного преобразования адаптивного размера блока (ДКПАРБ). Этот способ раскрыт в патенте США №5021891, озаглавленном "Способ и система сжатия изображения адаптивного размера блока", права на который переданы владельцу настоящего изобретения и включенном в настоящее описание в качестве ссылки. Способы ДКП также раскрыты в патенте США №5107345, озаглавленном "Способ и система сжатия изображения адаптивного размера блока", права на который переданы владельцу настоящего изобретения и включенном в настоящее описание в качестве ссылки. Кроме того, использование способа ДКПАРБ в сочетании со способом дифференциального преобразования дерева квадрантов раскрыт в патенте США №5452104, озаглавленном "Способ и система сжатия изображения адаптивного размера блока", права на который также переданы владельцу настоящего изобретения и включенном в настоящее описание в качестве ссылки. Системы, раскрытые в этих патентах, используют, так называемое, "внутрикадровое" кодирование, где каждый кадр данных изображения кодируется, не обращая внимание на содержание любого другого кадра. Используя способ ДКПАРБ, достижимая скорость данных может быть уменьшена приблизительно от 1,5 миллиардов бит в секунду приблизительно до 50 миллионов бит в секунду без заметного ухудшения качества изображения.

Способ ДКПАРБ может использоваться для сжатия либо черно-белого, либо цветного изображения или сигнала, представляющего изображение. Цветной входной сигнал может быть в формате YIQ (яркость/цвет), где Y является выборкой яркости или освещенности, а I и Q являются выборками цветности или цвета для каждого блока 4х4 пиксел. Также могут использоваться другие известные форматы, такие как, форматы YUV и RGB (красный-зеленый-синий). Из-за низкой пространственной чувствительности глаза к цвету большинство исследований показало, что подвыборка составляющих цвета с коэффициентом четыре в горизонтальном и вертикальном направлениях является приемлемой. Таким образом, видеосигнал может быть представлен четырьмя составляющими яркости и двумя составляющими цветности.

Используя ДКПАРБ, видео сигнал будет обычно сегментирован на блоки пиксел для обработки. Для каждого блока составляющие яркости и цветности передаются в блочный перемежитель. Например, блок 16×16 (пиксел) может быть подан в блочный перемежитель, который упорядочивает или организует выборки изображения внутри каждого блока 16×16 для того, чтобы создать блоки и составные подблоки данных для анализа дискретного косинусного преобразования (ДКП). Операция ДКП является одним способом преобразования квантованного по времени сигнала в частотное представление того же самого сигнала. При преобразовании в частотное представление было показано, что способы ДКП дают возможность очень высоких степеней сжатия, так как устройство квантования может быть сконструировано так, чтобы воспользоваться преимуществом характеристик частотного распределения изображения. В предпочтительном осуществлении одно ДКП 16×16 применяется для первого упорядочения, четыре ДКП 8×8 применяются для второго упорядочения, 16 ДКП 4×4 применяются для третьего упорядочения и 64 ДКП 2×2 применяются для четвертого упорядочения.

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

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

Выбранный блок или сочетание подблоков затем соответствующим образом располагаются в последовательности в блок 16×16. Значения коэффициентов ДКП/ДПДК могут затем подвергаться частотному взвешиванию, квантованию и кодированию (такому, как кодирование переменной длины) при подготовке к передаче.

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

Краткое изложение изобретения

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

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

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

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

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

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

фиг.3а, фиг.3b и фиг.3с иллюстрируют пример назначения размера блока, соответствующего декомпозиции дерева квадрантов, и соответствующие данные PQR.

Подробное описание предпочтительных осуществлений

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

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

где и

x(m, n) - местоположение пиксела (m,n) в блоке N×M, и

X(k, l) - соответствующий коэффициент ДКП.

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

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

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

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

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

Дополнительной причиной для использования внутрикадрового кодирования является то, что схема пространственно-временного кодирования является более трудной для стандартизации, когда включены частоты 50 Гц и 60 Гц линии питания. Телевидение в настоящее время передает сигналы либо 50 Гц, либо 60 Гц. Использование внутрикадровой схемы, являющейся цифровым подходом, может адаптироваться к работе как на 50 Гц, так и на 60 Гц или даже к фильмам 24 кадра в секунду с помощью компромисса между частотой кадров относительно пространственного разрешения.

Для целей обработки изображения операция ДКП выполняется относительно данных пикселей, которые разделяются на массив непересекающихся блоков. Заметим, что, несмотря на то, что в настоящем описании обсуждаются размеры блоков, как равные N×N, представляется, что могут использоваться различные размеры блоков. Например, может использоваться размер блока N×M, где как N, так и М - целые, причем М либо больше, либо меньше, чем N. Другим важным аспектом является то, что блок делится, по меньшей мере, на один уровень подблоков, таких как N/i×N/i, N/i×N/j, N/i×M/j и т.д., где i и j - целые. Кроме того, примерный размер блока, как обсуждается в настоящем описании, является блоком 16×16 пикселей с соответствующим блоком и подблоками коэффициентов ДКП. Дополнительно представляется, что могут использоваться различные другие целые, такие как обе четные или нечетные целые величины, например, 9×9.

Теперь ссылаясь на фиг.1, изображена система 100 обработки изображения, которая содержит систему сжатия настоящего изобретения. Система 100 обработки изображения содержит кодировщик 102, который сжимает принятый видеосигнал. Сжатый сигнал передается через канал 104 передачи и принимается декодером 106. Декодер 106 декодирует принятый сигнал в выборки изображения, которые затем могут быть отображены.

Обычно изображение делится на блоки пикселей для обработки. Цветной сигнал может быть преобразован из пространства красный-зеленый-синий (RGB) в пространство YC₁C ₂, где Y является составляющей яркости или освещенности, a C₁ и C₂ являются составляющими цветности или цвета. Из-за низкой пространственной чувствительности глаза к цвету многие системы дополнительно квантуют составляющие C ₁ и C₂ на коэффициент четыре в горизонтальном и вертикальном направлениях. Однако дополнительное квантование необязательно. Изображение с полным разрешением, известное как формат 4:4:4, может быть либо очень полезно, либо необходимо в некоторых приложениях, таких как изображения, упоминаемые как охватывающие "цифровое кино". Двумя возможными представлениями YC₁C₂ являются: представление YIQ и представление YUV, оба из которых хорошо известны в данной области техники. Также возможно использовать вариант представления YUV, известный как YCbCr.

В предпочтительном варианте осуществления каждая из составляющих Y, Cb, и Cr обрабатывается без подквантования. Затем входной сигнал блока 16×16 пикселей подается в кодировщик 102. Кодировщик 102 содержит элемент 108 назначения размера блока, который выполняет назначение размера блока при подготовке к сжатию видеосигнала. Элемент 108 назначения размера блока определяет блочную декомпозицию блока 16×16 на основании воспринимаемых характеристик изображения в блоке. Назначение размера блока подразделяет каждый блок 16×16 на меньшие блоки способом дерева квадрантов в зависимости от активности в блоке 16×16. Элемент 108 назначения размера блока генерирует данные дерева квадрантов, называемые данными PQR, длина которых может быть между 1 и 21 бит. Следовательно, если при назначении размера блока определяют, что блок 16×16 должен быть подразделен, устанавливается бит R данных PQR, за которым следуют четыре дополнительных бита данных Р, соответствующие четырем разделенным блокам 8×8. Если при назначении размера блока определяют, что любой из блоков 8×8 должен быть подразделен, тогда добавляются четыре дополнительных бита данных Q для каждого подразделенного блока 8×8.

Теперь ссылаясь на фиг.2, предоставлена последовательность операций, изображающая подробности работы элемента 108 назначения размера блока. Алгоритм использует дисперсию блока в качестве показателя при решении о подразделении блока. Начиная на шаге 202, блок 16×16 пиксел считывается. На шаге 204 вычисляется дисперсия v16 блока 16×16. Дисперсия вычисляется следующим образом:

где N=16, a x_i,j - пиксел в i-ой строке, j-ом столбце в блоке N×N. На шаге 206 сначала изменяется порог Т16 дисперсии для того, чтобы обеспечить новый порог Т16, если средняя величина блока находится между двумя заранее определенными величинами, затем дисперсия блока сравнивается с новым порогом Т16.

Если дисперсия v16 не больше, чем порог Т16, тогда на шаге 208 записывается начальный адрес блока 16×16 и бит R данных PQR устанавливается в 0 для того, чтобы указать, что блок 16×16 не подразделяется. Затем алгоритм считывает следующий блок 16×16 пикселей. Если дисперсия v16 больше, чем порог Т16, тогда на шаге 210 бит R данных PQR устанавливается в 1 для того, чтобы указать, что блок 16×16 должен быть подразделен на четыре блока 8×8.

Четыре блока 8×8, i=1:4, рассматриваются последовательно для дополнительного подразделения, как изображено на шаге 212. Для каждого блока 8×8 вычисляется дисперсия v8_i на шаге 214. На шаге 216 сначала изменяется порог Т8 дисперсии для того, чтобы обеспечить новый порог Т8, если средняя величина блока находится между двумя заранее определенными величинами, затем дисперсия блока сравнивается с этим новым порогом.

Если дисперсия v8_i не больше, чем порог Т8, тогда на шаге 218 записывается начальный адрес блока 8×8, и соответствующий бит Q, Q_i устанавливается в 0. Затем обрабатывается следующий блок 8×8. Если дисперсия v8 _i больше, чем порог Т8, тогда на шаге 220 соответствующий бит Q, Q_i устанавливается в 1 для того, чтобы указать, что блок 8×8 должен быть подразделен на четыре блока 4×4.

Четыре блока 4×4, j_i=1:4, рассматриваются последовательно для дополнительного подразделения, как изображено на шаге 222. Для каждого блока 4×4 вычисляется дисперсия v4_ij на шаге 224. На шаге 226 сначала изменяется порог Т4 дисперсии для того, чтобы обеспечить новый порог Т4, если средняя величина блока находится между двумя заранее определенными величинами, затем дисперсия блока сравнивается с этим новым порогом.

Если дисперсия v4_ij не больше, чем порог Т4, тогда на шаге 228 записывается начальный адрес блока 4×4, и соответствующий бит Р, P_ij устанавливается в 0. Затем обрабатывается следующий блок 4×4. Если дисперсия v4_ij больше, чем порог Т4, тогда на шаге 230 соответствующий бит Р, P_ij устанавливается в 1 для того, чтобы указать, что блок 4×4 должен быть подразделен на четыре блока 2×2. Кроме того, записываются адреса 4-х блоков 2×2.

Пороги Т16, Т8 и Т4 могут быть заранее определенными константами. Это известно как жесткое решение. Альтернативно может быть реализовано адаптивное или гибкое решение. Гибкое решение изменяет пороги для дисперсий в зависимости от средней величины пикселей блоков 2N×2N, где N может быть 8, 4 или 2. Следовательно, функции средних величин пикселей могут быть использованы в качестве порогов.

С целью иллюстрации рассмотрим следующий пример. Пусть заранее определенные пороги дисперсии для составляющей Y равны 50, 1100 и 880 для блоков 16×16, 8×8 и 4×4, соответственно. Иначе говоря, Т16=50, Т8=1100 и Т16=880. Пусть диапазон средних величин равен 80 и 100. Допустим, что вычисленная дисперсия для блока 16×16 равна 60. Так как 60 и его средняя величина 90 больше, чем Т16, блок 16×16 подразделяется на четыре подблока 8×8. Допустим, что вычисленные дисперсии для блоков 8×8 равны 1180, 935, 980 и 1210. Так как два из блоков 8×8 имеют дисперсии, которые превышают Т8, эти два блока дополнительно подразделяются для того, чтобы создать в итоге восемь подблоков 4×4. Наконец, допустим, что дисперсии восьми блоков 4×4 равны 620, 630, 670, 610, 590, 525, 930 и 690 с соответствующими средними величинами 90, 120, 110, 115. Так как средняя величина первого блока 4×4 попадает в диапазон (80, 100), его порог будет снижен до Т4=200, который меньше, чем 880. Таким образом, этот блок 4×4 будет также подразделен на семь блоков 4×4. Результирующее назначение размера блока изображено на фиг.3а. Соответствующая декомпозиция дерева квадрантов изображена на фиг.3b. Кроме того, данные PQR, сгенерированные с помощью этого назначения размера блока, изображены на фиг.3с.

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

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

Со ссылками на фиг.1 описана остальная часть системы 100 обработки изображения. Данные PQR вместе с адресами выбранных блоков подаются в элемент 110 ДКП. Элемент 110 ДКП использует данные PQR для выполнения дискретного косинусного преобразования соответствующих размеров относительно выбранных блоков. Только выбранные блоки нужно подвергать обработке ДКП.

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

Элемент 112 ДПДК выполняет двумерные ДКП относительно постоянных коэффициентов, беря по одному 2×2. Начиная с блоков 2×2 в блоках 4×4, двумерное ДКП выполняется относительно четырех постоянных коэффициентов. Это ДКП 2×2 называется дифференциальным преобразованием дерева квадрантов, или ДПДК, четырех постоянных коэффициентов. Затем постоянный коэффициент ДПДК вместе с тремя соседними постоянными коэффициентами с блоком 8×8 используются для вычисления ДПДК следующего уровня. Наконец, постоянные коэффициенты четырех блоков 8×8 с блоком 16×16 используются для вычисления ДПДК. Следовательно, в блоке 16×16 имеется один действительный постоянный коэффициент, а остальные являются переменными коэффициентами, соответствующими ДКП и ДПДК.

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

Веса выбираются на основании эмпирических данных. Способ для конструирования взвешивающих масок для коэффициентов 8х8 ДКП раскрыт в стандарте ISO/IEC JTC1 CD 109918 "Цифровое сжатие и кодирование полутоновых неподвижных изображений - часть 1: Требования и руководящие указания". Международная организация стандартов, 1994 г., который включен в настоящее описание в качестве ссылки. Обычно конструируются две ЧВМ, одна для составляющей яркости, а другая для составляющих цветности. Таблицы ЧВМ для размеров 2×2, 4×4 блоков получаются с помощью прореживания, а 16×16 - с помощью интерполяции таблицы для блока 8×8. Масштабный коэффициент управляет качеством и скоростью бит квантованных коэффициентов.

Следовательно, каждый коэффициент ДКП квантуется в соответствии с зависимостью:

где ДКП(i, j) - входной коэффициент ДКП, fwm(i, j) - частотная взвешивающая маска, q - масштабный коэффициент, а ДКПq(i, j) - квантованный коэффициент. Заметим, что в зависимости от знака коэффициента ДКП первый член внутри скобок округляется вверх или вниз. Коэффициенты ДПДК также квантуются с использованием соответствующих взвешивающих масок. Однако может использоваться множество таблиц масок и применяться к каждой из составляющих Y, Cb и Cr.

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

Заметим, что преобразователь 116 в последовательную форму может быть расположен либо перед, либо после устройства 114 квантования. Полученные результаты являются одинаковыми.

В любом случае поток квантованных коэффициентов подается в кодировщик 118 переменной длины. Кодировщик 118 переменной длины может использовать кодирование с переменной длиной нулей с последующим кодированием кодированием Хафмана. Этот способ обсужден подробно в вышеупомянутых патентах США №№5021891, 5107345 и 5452104 и резюмирован в настоящем описании. Кодировщик с переменной длиной выбирает квантованные коэффициенты и выделяет ноль из ненулевых коэффициентов. Нулевые величины называются как значения переменной длины и кодируются способом Хафмана. Ненулевые величины отдельно кодируются способом Хафмана.

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

Коды Хафмана конструируются либо из измеренных или теоретических статистических данных изображения. Было замечено, что наиболее естественные изображения составляются из незаполненных или относительно медленно изменяющихся областей и насыщенных областей, таких как границы объекта и высококонтрастная текстура. Кодировщики Хафмана с частотно-пространственными преобразованиями, такими как ДКП, используют эти особенности при назначении большего количества бит насыщенным областям и меньшего количества бит незаполненным областям. Обычно кодировщики Хафмана используют просмотровые таблицы для кодирования переменной длины и ненулевых величин. Обычно используются множественные таблицы, причем в настоящем изобретении предпочтительны 3 таблицы, несмотря на то, что могут использоваться 1 или 2, когда необходимо.

Сжатый сигнал изображения, сгенерированный кодировщиком 102, передается в декодер 106 через канал 104 передачи. Данные PQR, которые содержат информацию назначения размера блока, также подаются в декодер 106. Декодер 106 содержит декодер 120 переменной длины, который декодирует с переменной длиной величины и ненулевые величины.

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

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

Блок коэффициентов затем подается в элемент 126 ОДПДК (обратного ДПДК), после которого следует элемент 128 ОДКП (обратного ДКП), если было применено дифференциальное преобразование дерева квадрантов. Иначе блок коэффициентов подается непосредственно в элемент 128 ОДКП. Элемент 126 ОДПДК и элемент 128 ОДКП выполняют обратное преобразование коэффициентов для того, чтобы создать блок данных пикселей. Данные пикселей могут быть затем быть интерполированы, преобразованы в форму красный-зеленый-синий, а затем запомнены для будущего отображения.

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

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

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

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