способ и формат записи для сжатия изображений

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

1. Способ обработки данных фрагмента изображения, содержащий шаги, на которых: предоставляют объект фрагмента изображения;

формируют двоичную битовую карту объекта;

определяют, является ли количество битов, имеющих первое двоичное значение большим, чем количество битов, имеющих второе двоичное значение в двоичной битовой карте;

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

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

2. Способ по п.1, который также содержит шаг, на котором выполняют операцию ИСКЛЮЧАЮЩЕГО ИЛИ между двумя последовательными строками двоичной битовой карты.

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

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

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

6. Способ по п.5, который также содержит шаг, на котором записывают количество (непоследовательных битов, имеющих второе двоичное значение, которые следуют за наиболее значащим битом, в N1 бит, где N1 является наименьшим целым, удовлетворяющим условию n1 2^N1-1.

7. Способ по п.6, который также содержит шаг, на котором записывают участок двоичной битовой карты в первом формате в (N1+2) бит, где наиболее значащий бит первого формата имеет первое двоичное значение, второй наиболее значащий бит первого формата имеет второе двоичное значение, а наименьшие значащие N1 битов имеют значение, равное n1.

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

9. Способ по п.8, который также содержит шаг, на котором записывают количество (n2)последовательных битов, имеющих первое двоичное значение, которые следуют за наиболее значащим битом, в N2 бит, где N2 является наименьшим целым, удовлетворяющим условию n1 2^N2-1.

10. Способ по п.9, который также содержит шаг, на котором записывают участок двоичной битовой карты в первом формате в (N2+2) бит, где наиболее значащий бит второго формата имеет первое двоичное значение, второй наиболее значащий бит второго формата имеет первое двоичное значение, а наименее значащие N2 биты имеют значение, равное n2.

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

12. Способ по п.11, который также содержит этапы, на которых: записывают количество (n3) последовательных битов, имеющих первое двоичное значение, которые следуют за наиболее значащим битом, в N3 бит, где N3 является наименьшим целым, удовлетворяющим условию n1 2^N3-1.

13. Способ по п.12, который также содержит шаг, на котором записывают участок двоичной битовой карты в третьем формате в (N3+2) бит, где наиболее значащий бит третьего формата имеет второе двоичное значение, второй наиболее значащий бит третьего формата имеет первое двоичное значение, а наименее значащие N3 биты имеют значение, равное п3.

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

15. Способ по п.14, который также содержит шаг, на котором записывают количество (n4) последовательных битов, имеющих второе двоичное значение, которые следуют за наиболее значащим битом, в N4 бит, где N4 является наименьшим целым, удовлетворяющим условию n1 2^N4-1.

16. Способ по п.15, который также содержит шаг, на котором записывают участок двоичной битовой карты в четвертом формате в (N4+2) бит, где наиболее значащий бит четвертого формата имеет второе двоичное значение, второй наиболее значащий бит четвертого формата имеет второе двоичное значение, а наименее значащие N4 биты имеют значение, равное n4.

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

18. Способ по п.17, который также содержит шаг, на котором записывают количество (n3) последовательных строк битов, имеющих второе двоичное значение, которые следуют за наиболее значащим битом, в N3 бит, где N3 является наименьшим целым, которое удовлетворяет условию n3 2^N3-1.

19. Способ по п.18, который также содержит шаг, на котором записывают участок двоичной битовой карты в третьем формате в (N3+2) бит, где наиболее значащий бит третьего формата имеет второе двоичное значение, второй наиболее значащий бит третьего формата имеет первое двоичное значение, а наименее значащие N3 биты имеют значение, равное n3.

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

21. Способ по п.20, который также содержит шаг, на котором записывают количество (n4) последовательных битов, которые следуют за наиболее значащим битом в стоке битовой карты, имеющих второе двоичное значение, в N4 бит, если наиболее значащий бит, где N4 является наименьшим целым, удовлетворяющим условию n4 2^N4-1.

22. Способ по п.21, который также содержит шаг, на котором записывают участок двоичной битовой карты в четвертом формате в (N4+2) бит, где наиболее значащий бит первого формата имеет второе двоичное значение, второй наиболее значащий бит первого формата имеет второе двоичное значение, а наименее значащие N4 биты имеют значение, равное n4.

23. Способ обработки данных фрагмента изображения, содержащий шаги, на которых: предоставляют объект фрагмента изображения;

формируют двоичную битовую карту объекта;

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

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

записывают количество (n1) последовательных битов, имеющих второе двоичное значение, которые следуют за наиболее значащим битом, в N1 бит, где N1 является наименьшим целым, удовлетворяющим условию n1 2^N1-1;

сжимают участок во втором формате, если за наиболее значащим битом, имеющим первое двоичное значение следует второй наиболее значащий бит, имеющий первое двоичное значение; и

записывают количество (n2) последовательных битов, имеющих первое двоичное значение, которое следует за наиболее значащим битом в N2 битов, где N2 является наименьшим целым, которое удовлетворяет условию n2 2^N2-1.

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

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

25. Способ по п.24, который также содержит шаги, на которых выполняют операцию ИСКЛЮЧАЮЩЕГО ИЛИ для m-й строки и (m+1)-й строки двоичной битовой карты, m является натуральным числом; и записывают результат операции ИСКЛЮЧАЮЩЕГО ИЛИ в (m+1)-ю строку другой двоичной битовой карты.

26. Способ по п.23, который также содержит шаг, на котором устанавливают в поле формы записи, выполнено ли преобразование двоичной битовой карты.

27. Способ по п.23, который также содержит шаги, на которых сжимают участок в третьем формате, если за наиболее значащим битом, имеющим второе двоичное значение, следует второй наиболее значащий бит, имеющий первое двоичное значение; и записывают количество (n3) последовательных битов, имеющих первое двоичное значение, которое следует за наиболее значащим битом, в N3 битов, где N3 является наименьшим целым, которое удовлетворяет условию n3 2^N3-1.

28. Способ по п.23, который также содержит шаги, на которых сжимают участок в четвертом формате, если за наиболее значащим битом, имеющим второе значение, следует второй наиболее значащий бит, имеющий второе двоичное значение; записывают количество (n4) последовательных битов, имеющих второе двоичное значение, которые следуют за наиболее значащим битом в N4 бит, где N4 является наименьшим целым, удовлетворяющим условию n4 2^N4-1.

29. Способ по п.23, который также содержит шаги, на которых сжимают участок в третьем формате, если за наиболее значащим битом, имеющим второе двоичное значение, следуют последовательные строки битов, имеющие второе двоичное значение; и записывают количество (n3) последовательных битов, имеющих второе двоичное значение, которое следует за наиболее значащим битом, в N3 битов, где N3 является наименьшим целым, которое удовлетворяет условию n3 2^N3-1.

30. Способ по п.23, который также содержит шаги, на которых сжимают участок в четвертом формате, если за наиболее значащим битом, имеющим второе двоичное значение, следуют последовательные биты в строке двоичной битовой карты, имеющие второе двоичное значение; и записывают количество (n4) последовательных битов, которые следуют за наиболее значимым битом в строке двоичной битовой карты, имеющих второе двоичное значение в N4 бит, где N4 является наименьшим целым, которое удовлетворяет условию n4 2^N4-1.

31. Способ сжатия и развертывания фрагмента изображения, содержащий шаги, на которых: определяют объект фрагмента изображения;

формируют двоичную битовую карту объекта;

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

сжимают участок последовательных битов в соответствии с правилом сжатия для формирования сжатого участка; и

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

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

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

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

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

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

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

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

УРОВЕНЬ ТЕХНИКИ

Настоящее изобретение в целом относится к способу обработки данных изображений, а более точно к способу и формату записи для сжатия по длинам серий информации фрагмента изображения. В то время как технология обработки продолжает развиваться, эффективность сжатия аудио- и видеоданных значительно улучшилась в последние годы. Например, форматы сжатия стандартов Экспертной группы по киноизображениям (Motion Picture Experts Group - "MPEG") развились от MPEG 1 до MPEG 4. Тем не менее, эффективность сжатия данных фрагментов изображений, которые играют важную роль в представлении мультимедиа-программ, не была улучшено. Более того, размеры данных фрагментов изображений увеличиваются с увеличением требований от мультимедиа-программ высокого разрешения. Эффективность сжатия, обеспеченная традиционными способами сжатия, может быть неудовлетворительной для обработки мультимедиа-программ высокого разрешения. Пример традиционных способов сжатия включает в себя технологию, описанную в патенте США № 6009202, выданном Кукучи и др., озаглавленном "Система кодирования/декодирования информации изображений". Кукучи раскрывает способ кодирования данных фрагментов изображений, который включает в себя правила сжатия от 1 до 6, со ссылкой на Фиг.5A-5F, и правила сжатия со ссылкой на Фиг.6A-6E. Эти правила сжатия могут требовать больших накладных расходов записи данных, и формат данных не является приспособляемым для лучшей обработки различных особенностей содержимого данных фрагментов чертежей.

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

Другим примером изобретения может быть способ обработки данных фрагмента изображения картинки. Способ может включать в себя предоставление объекта фрагмента изображения, формирование двоичной битовой карты объекта, определение наиболее значащих двух битов участка последовательных битов в двоичной битовой карте, сжатие участка в первом формате, если за наиболее значащим битом, имеющим первое двоичное значение, следует второй наиболее значащий бит, имеющий второе двоичное значение, запись количества (n1) последовательных битов, имеющих второе двоичное значение, которое следует за наиболее значащим битом в N1 битах, где N1 является наименьшим целым, которое удовлетворяет условию n1 2^N1-1, сжатие участка во втором формате, если за наиболее значащим битом, имеющим первое двоичное значение, следует второй наиболее значащий бит, имеющий первое двоичное значение, и запись количества (n2) последовательных битов, имеющих первое двоичное значение, которое следует за наиболее значащим битом в N2 битах, где N2 является наименьшим целым, которое удовлетворяет условию n2 2^N2-1.

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

На чертежах:

Фиг.1А - схематический чертеж изображения, включающего фрагмент изображения;

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

Фиг.2А - схематический чертеж структуры изображения, согласующийся с примером настоящего изобретения;

Фиг.2B - схематический чертеж структуры заголовка изображения, проиллюстрированного на фиг 2A;

Фиг.2С - схематический чертеж структуры объекта, проиллюстрированного на фиг 2A;

Фиг.3A - битовая карта объекта, согласующаяся с примером настоящего изобретения;

Фиг.3B - преобразованная битовая карта объекта, проиллюстрированного на Фиг.3A, согласующаяся с примером настоящего изобретения;

Фиг.3С - преобразованная битовая карта объекта, проиллюстрированного на Фиг.3A, согласующаяся с другим примером настоящего изобретения;

Фиг.4 - блок-схема, иллюстрирующая способ сжатия, согласующийся с примером настоящего изобретения;

Фиг.5A до 5D - блок-схемы, иллюстрирующие способы сжатия, согласующиеся с примерами настоящего изобретения;

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

Фиг.7A до 7Н - схематические чертежи, иллюстрирующие способ сжатия, согласующийся с другим примером настоящего изобретения;

Фиг.8A - схематический чертеж потока битов после сжатия;

Фиг.8В - блок-схема, иллюстрирующая способ распаковки, согласующийся с примером настоящего изобретения;

Фиг.9A - график, иллюстрирующий экспериментальные результаты для английского алфавита.

Фиг.9B - график, иллюстрирующий экспериментальные результаты набора китайских символов; и

Фиг.10 - структурная схема, иллюстрирующая способ сжатия, согласующийся с примером настоящего изобретения.

ПОДРОБНОЕ ОПИСАНИЕ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ

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

Фиг.1А - схематический чертеж изображения, включающего фрагмент изображения 12. Обращаясь к Фиг.1A, изображение 10, которое ссылается на главное изображение фильма, имеет двухмерные размеры X (пикселей) на Y (пикселей). Фрагмент 12 изображения, который ссылается на субтитры или текстовые данные, отображаемые на изображении 10 в фильме, может включать многоязыковые тексты, такие как тексты на английском и китайском. В настоящем примере первая строка фрагмента 12 изображения включает восемь китайских символов и три английских символа, которые являются китайским вариантом "Добро пожаловать в команду FVD" во второй строке. В некоторых примерах фрагмент изображения может включать только одну строку текстов или несколько строк текстов на одном и том же или различных языках.

Фиг.1B и 1C - схематические чертежи объектов фрагмента изображения, согласующихся с примерами настоящего изобретения посредством использования первой строки на Фиг.1A в качестве примера. Фрагмент изображения включает по меньшей мере один объект. Обращаясь к Фиг.1B, символы во фрагменте 12 изображения, проиллюстрированном на Фиг.1A, взяты как целое, как объект 12-1. В результате объект 12-1 имеет тот же размер, что и фрагмент 12 изображения, то есть X₁ на Y₁. Обращаясь к Фиг.1C, каждый из символов во фрагменте 12 изображения взят как объект 12-2. Каждый из объектов 12-2 имеет одинаковый размер X₂ на Y ₂ и включает текстовую часть 121 и фоновую часть 122. Различные размеры объектов могут быть использованы для различных приложений.

Фиг.2А - схематический чертеж структуры изображения, согласующейся с примером настоящего изобретения. Обращаясь к Фиг.2A, структура изображения включает заголовок изображения, за которым следует множество структур объектов. В настоящем примере предоставлено общее количество из "n" объектов, следующих за заголовком изображения. Каждая из структур объектов включает в себя заголовок объекта и блок данных объекта сразу же после заголовка объекта. Параметры и сжатые данные, собранные во время процесса сжатия, хранятся соответственно в заголовке объекта и блоке данных объекта.

Фиг.2B - схематический чертеж структуры заголовка изображения, проиллюстрированного на Фиг.2A. Обращаясь к Фиг.2B, структура заголовка изображения устанавливает размер блока, например один пиксель или четыре пикселя, во флаге блока, размер изображения, размер объекта и количество объектов на изображении.

Фиг.2С - схематический чертеж структуры объекта, проиллюстрированного на фиг 2A. Обращаясь к Фиг.2C, структура объекта включает в себя заголовок объекта, за которым следует блок данных объекта. Заголовок объекта включает в себя флаг исключающего ИЛИ (XOR), поле цвета и поля информации размера объекта. Флаг XOR используется для установления, выполняется ли операция исключающего ИЛИ, которая будет подробно обсуждена далее. Поле цвета используется для установления цветовой информации текстовой части объекта относительно фоновой части. В одном примере, согласующемся с настоящим изобретением, двоичное значение "1" присваивается пикселям текстовой части, в то время как двоичное значение "0" присваивается пикселям фоновой части, когда поле цвета установлено в "1". Заголовок объекта дополнительно включает в себя информацию сжатия в параметрах N1, N2, N3 и N4, которые записывают значения длины данных, хранимых в блоке данных объекта в соответствии с надлежащими правилами сжатия. Правила сжатия и параметры N1, N2, N3 и N4 будут дополнительно подробно обсуждены.

Фиг.3A - битовая карта 31 объекта, согласующаяся с примером настоящего изобретения. Обращаясь к Фиг.3A, сканируется объект, имеющий текстовую часть в виде "H". При задании того, что поле цвета установлено в 1, двоичное значение "1" присваивается пикселям текстовой части, в то время как двоичное значение "0" присваивается пикселям фона. Для облегчения сжатия количество двоичных значений "1" может быть меньше, чем количество двоичных значений "0", когда поле цвета установлено в "1", или наоборот. Более того, для уменьшения количества двоичных значений "1", если двоичные значения "0" численно превышаются, в одном примере, согласующемся с настоящим изобретением, может выполняться операция исключающего ИЛИ (XOR). Операция XOR может быть выполнена строка за строкой от верхней строки (нисходящий XOR) или нижней строки (восходящий XOR), или колонка за колонкой от левой колонки (направленный вправо XOR) или правой колонки (направленный влево XOR). Операция XOR относится к логической операции над двумя операндами, которая приводит к логическому значению "истина", если и только если один из операндов, но не два, имеют значение "истина".

Фиг.3B - преобразованная битовая карта 32 объекта, проиллюстрированного на Фиг.3A, согласующаяся с примером настоящего изобретения. Обращаясь к Фиг.3А и 3B, когда выполняется нисходящий XOR, первая строка битовой карты 31 служит в качестве первой строки преобразованной битовой карты 32. Первая строка и вторая строка битовой карты 31 преобразуются XOR в другую строку, в которой первый элемент первой строки битовой карты 31 подвергается XOR с первым элементом второй строки битовой карты 31, второй элемент первой строки битовой карты 31 подвергается XOR со вторым элементом второй строки битовой карты 31 и так далее. Результат операции XOR может быть записан во вторую строку преобразованной битовой карты 32. В операции нисходящего XOR первая строка битовой карты 31, проиллюстрированная на Фиг.3A, может быть записана в первую строку битовой карты 32, а результат операции XOR по n-ой строке и n+1 строке битовой карты 31 записывается в n+1 строку преобразованной битовой карты 32. После операции XOR количество двоичных значений "1" меньше, чем количество двоичных значений "0" в преобразованной битовой карте 32.

Фиг.3С - преобразованная битовая карта 33 объекта, проиллюстрированного на Фиг.3A, согласующаяся с другим примером настоящего изобретения. Обращаясь к Фиг.3C, битовая карта 33 является результатом операции восходящего XOR, выполняемого над битовой картой 31, проиллюстрированной на Фиг.3A. В операции восходящего XOR первая строка битовой карты 31, проиллюстрированная на Фиг.3A, записывается в первую строку битовой карты 33, а результат операции XOR по n+1-ой строке и n-ой строке битовой карты 31 записывается в n+1 строку преобразованной битовой карты 32. Операции XOR, проиллюстрированные со ссылкой на Фиг.3B и 3С, являются только примерными. Следовательно, другие методы могут быть применены для преобразования битовой карты, имеющей большее количество двоичных "1" в карту, имеющую большее количество двоичных "0". Например, в одном примере может быть выполнена операция инверсии для преобразования двоичной "1" в "0" и наоборот, так что количество двоичных "1" будет меньшим, чем количество двоичных "1" в преобразованной битовой карте.

Фиг.4 - блок-схема, иллюстрирующая способ сжатия, согласующийся с примером настоящего изобретения. Обращаясь к Фиг.4, на шаге 41, предоставлено изображение, включающее фрагмент изображения. Фрагмент изображения включает по меньшей мере один объект. На этапе 42 определяется размер каждого из по меньшей мере одного объекта. Затем на шаге 43 формируется битовая карта для каждого из по меньшей мере одного объекта посредством присвоения первого двоичного значения и второго двоичного значения пикселям текстовой части и фоновой части каждого из по меньшей мере одного объекта соответственно. Затем, на шаге 44, определяется, требуется ли преобразование битовой карты. Если количество двоичных значений "1" больше, чем количество двоичных значений "0", исходя из того что поле цвета установлено в "1", операция XOR выполняется на шаге 45 для получения преобразованной битовой карты. Шаги 44 и 45, однако, являются необязательными. То есть процесс сжатия может продолжаться без выполнения любого преобразования, даже если количество пикселей, имеющих значение "1", больше. Затем определяется, является ли первое, второе, третье или четвертое правило сжатия применимым к головному участку битовой карты.

Как только определено одно из правил сжатия, затем определяется, является ли одно из правил сжатия применимым к головному участку остающейся битовой карты. Такой процесс сжатия продолжается пока битовая карта сжимается в битовый поток. Головной участок может включать в себя непрерывную порцию строк или несколько непрерывных строк битовой карты. Конкретно, на шаге 51, определяется, применимо ли первое правило сжатия к головному участку битовой карты, как преобразованной, так и не преобразованной. Если подтверждено, первое правило применяется на шаге 61, который будет обсужден со ссылкой на Фиг.5A. Если нет, на шаге 52, определяется, применимо ли второе правило сжатия к головному участку. Если подтверждено, второе правило применяется на шаге 62, который будет обсужден со ссылкой к Фиг.5B. Если нет, на шаге 53 определяется, применимо ли третье правило сжатия к участку. Если подтверждено, третье правило применяется на шаге 63, который будет обсужден со ссылкой на Фиг.5С. Если нет, четвертое правило применяется на шаге 54, который будет обсужден со ссылкой на Фиг.5D. Результаты от шагов 61, 62, 63 и 64 собираются в поток битов на шаге 64. Процесс продолжается для определения, является ли применимым первое, второе, третье и четвертое правило сжатия к последующим участкам битовой карты, пока вся битовая карта целиком будет сжата.

Фиг.5A-5D - блок-схемы, иллюстрирующие способы сжатия, согласующиеся с примерами настоящего изобретения. Обращаясь к Фиг.5A, также обращаясь к Фиг.4, на шаге 510 определяется, являются ли первые два бита участка битовой карты "1" и "0", при задании, что флаг цвета является установленным в "1". Если подтверждено, на шаге 611 подсчитывается количество n1 последовательных "0", которые следуют сразу за первым битом "1". Затем, на шаге 612, число n1 записывается в N1 битов в первом формате, проиллюстрированном на Фиг.6A. Число N1 является наименьшим целым, которое удовлетворяет условию n1 2^N1-1. Затем, на шаге 613, число N1 записывается в первое поле заголовка объекта, как проиллюстрировано на Фиг.2С.

Обращаясь к Фиг.5A, также обращаясь к Фиг.4, на шаге 520 определяется, являются ли первые два бита участка битовой карты "1" и "1". Если подтверждено, на шаге 621 считается количество n2 последовательных "1", которые следуют сразу за первым битом "1". Затем, на шаге 622, число записывается n2 в N2 битов во втором формате, проиллюстрированном на Фиг.6B. Число N2 является наименьшим целым, которое удовлетворяет условию n2 2^N2-1. Затем на шаге 623 число N2 записывается во второе поле заголовка объекта, как проиллюстрировано на Фиг.2С.

Обращаясь к Фиг.5С, также обращаясь к Фиг.4, на шаге 530 определяется, являются ли последовательные строки битов в битовой карте имеющими двоичные значения "0". Если подтверждено, на шаге 631 подсчитывается количество (n3) последовательных строк из "0". Затем, на шаге 632, число n3 записывается в N1 битов в третьем формате, проиллюстрированном на Фиг.6A. Число N3 является наименьшим целым, которое удовлетворяет условию n3 2^N3-1. Затем на шаге 633 число N3 записывается в третье поле заголовка объекта, как проиллюстрировано на Фиг.2С.

Обращаясь к Фиг.5D, также обращаясь к Фиг.4, на шаге 541 подсчитывается количество n4 последовательных "0" в строке битовой карты. Затем, на шаге 542, число n4 записывается в N4 битов в четвертом формате, проиллюстрированном на Фиг.6D. Число N4 является наименьшим целым, которое удовлетворяет условию n4 2^N4-1. Затем, на шаге 543, число N4 записывается в четвертое поле заголовка объекта, как проиллюстрировано на Фиг.2С.

Фиг.6A-6D - блок-схемы форматов записи, согласующиеся с примерами настоящего изобретения. Обращаясь к Фиг.6A, первые два бита указывают, что некоторое количество последовательных "0" следует сразу за первым битом "1". Действительное количество последовательных "0" указано в следующих N1 битах. N1+2 битов как целое хранятся в блоке данных объекта и собираются в поток битов. Если более чем один участок удовлетворяет первому правилу и, следовательно, существует более одного n1, только значение N1, соответствующее максимуму n1, записывается в заголовок объекта.

Обращаясь к Фиг.6B, подобным образом, первые два бита указывают, что некоторое количество последовательных "1" следует сразу за первым битом "1". Действительное количество последовательных "1" указано в следующих N2 битах. N2+2 битов хранятся в блоке данных объекта и собираются в потоке битов. Если более чем один участок удовлетворяет второму правилу и, следовательно, существует более одного n2, только значение N2, соответствующее максимуму n2, записывается в заголовок объекта.

Обращаясь к Фиг.6С, первые два бита указывают количество последовательных строк "0". Действительное количество последовательных строк указано в следующих N3 битах. N3+2 битов хранятся в блоке данных объекта и собираются в потоке битов. Если более чем один участок удовлетворяет третьему правилу и, следовательно, существует более одного n3, только значение N3, соответствующее максимуму n3, записывается в заголовок объекта.

Обращаясь к Фиг.6D, первые два бита указывают, что некоторое количество последовательных "0" появляется в строке, но не занимает всю строку. Действительное количество последовательных "0" указано в следующих N4 битах. N4+2 битов хранятся в блоке данных объекта и собираются в потоке битов. Если более чем один участок удовлетворяет второму правилу и, следовательно, существует более одного n4, только значение N4, соответствующее максимуму n4, записывается в заголовок объекта.

Фиг.7A-7Н - схематические чертежи, иллюстрирующие способ сжатия, согласующийся с другим примером настоящего изобретения. Обращаясь к Фиг.7A, представлена битовая карта 70 объекта для сжатия. Обращаясь к Фиг.7B, определяется, что первое правило сжатия применимо к первому участку, который является головным участком битовой карты 70. Более того, определяется, что значение n1 равно 5, потому что пять последовательных "0" следуют за первым "1" на первом участке. Также определяется значение N1, которое равно 3. Значения n1 и N1 соответственно записываются в первом формате в блок данных объекта и первое поле заголовка объекта.

Обращаясь к Фиг.7С, определяется, что второе правило сжатия применимо ко второму участку сразу за первой частью битовой карты 70. Более того, определяется, что значение n2 равно 4, потому что четыре последовательных "1" следуют за первым битом "1" на втором участке. Также определяется значение N2, которое равно 3. Значения n2 и N2 соответственно записываются во втором формате и второе поле заголовка объекта.

Обращаясь к Фиг.7D, определяется, что третье правило сжатия применимо к третьему участку сразу за вторым участком битовой карты 70. Более того, определяется, что значение n3 равно 8, потому что появляется восемь последовательных строк из "0". Также определяется значение N3, которое равно 4. Значения n3 и N3 соответственно записываются в третьем формате и третье поле заголовка объекта.

Обращаясь к Фиг.7E, определяется, что четвертое правило сжатия применимо к четвертому участку сразу за третьим участком битовой карты 70. Более того, определяется, что значение n4 равно 4, потому что четыре последовательных "0" появляются в строке на третьем участке. Также определяется значение N4, которое равно 3. Значения n4 и N4 соответственно записываются в четвертом формате и четвертое поле заголовка объекта.

Обращаясь к Фиг.7F, определяется, что второе правило сжатия применимо к пятому участку сразу за четвертым участком битовой карты 70. Более того, определяется, что значение n2 равно 4, потому что четыре последовательных "1" следуют за первым битом "1" в пятом участке. Однако, поскольку значение n2 со ссылкой на Фиг.7F равняется значению со ссылкой на Фиг.7C, значение n2 для пятого участка записывается в N2 битов во втором формате.

Обращаясь к Фиг.7G, определяется, что четвертое правило сжатия применимо к шестому участку сразу за пятым участком битовой карты 70. Более того, определяется, что значение n4 равно 2, потому что два последовательных "0" появляются в строке на шестом участке. Поскольку значение n4 со ссылкой на Фиг.7G является меньшим, чем значение (n4=4) со ссылкой на Фиг.7E, значение n4 для шестого участка записывается в N4 бита в четвертом формате.

Обращаясь к Фиг.7H, определяется, что третье правило сжатия применимо к седьмому участку сразу за шестым участком битовой карты 70. Более того, определяется, что значение n3 равно 2, потому что появляется две последовательные строки из "0" на седьмом участке. Поскольку значение n3 со ссылкой на Фиг.7H является меньшим, чем значение (n3=8) со ссылкой на Фиг.7D, значение n3 для седьмой части записывается в N3 бита в третьем формате.

Алгоритм сжатия включает четыре правила сжатия, обсужденные со ссылкой на Фиг. c 7A по 7H, которые являются только примерными. В другом примере согласно настоящему изобретению алгоритм сжатия включает правила сжатия, как изложено ниже.

(1) Определяют, являются ли наиболее значащие два бита участка последовательных битов в битовой карте двоичным "1", за которым следует "0". Если подтверждено, вычисляют количество последовательных битов, имеющих двоичное значение "0", которое следует за наиболее значащим битом на участке. Формат записи и сжатые данные, ассоциированные с правилом, являются такими же, как для первого правила сжатия, обсужденного со ссылкой на Фиг. 7A-7H, и не обсуждаются.

(2) Определяют, являются ли наиболее значащие два бита участка последовательных битов в битовой карте двоичным "1", за которым следует двоичная "1". Если подтверждено, подсчитывают количество последовательных битов, имеющих двоичное значение "1", которое следует за наиболее значащим битом на участке. Формат записи и сжатые данные, ассоциированные с правилом, являются такими же, как для второго правила сжатия, обсужденного со ссылкой на Фиг. с 7A по 7H, и не обсуждаются.

(3) Определяют, являются ли наиболее значащие два бита участка последовательных битов в битовой карте двоичным "0", за которым следует двоичная "1". Если подтверждено, подсчитывают количество последовательных битов, имеющих двоичное значение "1", которое следует за наиболее значащим битом на участке. Формат записи и сжатые данные, ассоциированные с правилом, являются такими же, как для первого правила сжатия, обсужденного со ссылкой на Фиг. с 7A по 7H, и не обсуждаются.

(4) Определяют, являются ли наиболее значащие два бита участка последовательных битов в битовой карте двоичным "0", за которым следует двоичный "0". Если подтверждено, вычисляют количество последовательных битов, имеющих двоичное значение "0", которое следует за наиболее значащим битом на участке. Формат записи и сжатые данные, ассоциированные с правилом, являются такими же, как для первого правила сжатия, обсужденного со ссылкой на Фиг. с 7A по 7H, и не обсуждаются.

Фиг.8A - схематический чертеж потока 80 битов после сжатия. Обращаясь к Фиг.8A, поток 80 битов формируется посредством, например, способа, проиллюстрированного на Фиг. с 7A по 7H. Для распаковки потока 80 битов используются значения с n1 по n4 и с N1 по N4, записанные для каждого участка битовой карты 70, проиллюстрированной со ссылкой на Фиг. с 7B по 7H. Поток 80 битов включает в себя 37 битов, если один бит берется в качестве элемента. Коэффициент сжатия, который является отношением количества битов до сжатия к количеству битов после сжатия, вычисляется ниже.

Коэффициент сжатия=(10x12)/(37).

В начале распаковки первым рассматривается головной участок потока 80 битов. Поскольку первые два бита потока 80 битов являются "1" и "0", которые указывают, что первое правило сжатия было применено во время процесса сжатия, определяется, что последующие N1 битов устанавливают количество n1 последовательных "0", следующих за первым битом "1". Более того, поскольку значением N1 является 3 (три), значение n1 вычисляется из двоичного значения трех битов "101", следующих за первыми двумя битами "10", что равно 5 (пяти), имеющее результатом первый участок двоичной битовой карты, то есть 100000. В результате длина первой секции потока 80 битов определяется значением N1+2, и первый участок сам включает в себя информацию касательно правила сжатия битовой карты (доступного посредством первых двух битов) и количество битов, ассоциированных с правилом сжатия (доступного посредством значения последующих N1 битов). В результате поток 80 битов анализируется на участках в соответствии со значениями N1, N2, N3 и N4, записанными во время процесса сжатия.

Фиг.8B - блок-схема, иллюстрирующая способ распаковки, согласующийся с примером настоящего изобретения. Обращаясь к Фиг.8B, поток битов, предназначенных для распаковки, представлен на шаге 81. Поток битов, который должен быть сжат из двоичной битовой карты до распаковки, хранится в блоке данных объекта и является извлекаемым оттуда. Затем, на шаге 82, представлена информация касательно правил сжатия, собранная во время сжатия битовой карты. Информация, включающая N1, N2, N3 и N4, была записана в заголовок объекта и является извлекаемой оттуда. На шаге 83 поток битов анализируется участок за участком от головного участка в соответствии с информацией. На шаге 84 образец битовой карты определяется посредством первых двух битов каждого участка потока битов. Затем на шаге 85 определяется количество битов, ассоциированное с моделью битовой карты. Двоичная битовая карта затем формируется, когда каждый из потока битов распаковывается. Впоследствии декодируется объект, соответствующий битовой карте.

Фиг.9A - график, иллюстрирующий экспериментальные результаты для английского алфавита. Обращаясь к Фиг.9A, посредством осуществления способа, согласующегося с настоящим изобретением, к английскому алфавиту от A до Z, обнаружено, что буква "I" имеет самый большой коэффициент сжатия, приблизительно 180, главным образом, благодаря ее сравнительно высокой симметрии и простоты формы. Символы, такие как "G", "Q" и "S", имеют сравнительно маленький коэффициент сжатия благодаря их низкой симметрии или сложности формы.

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

Фиг.10 - структурная схема, иллюстрирующая способ сжатия, согласующийся с примером настоящего изобретения. Обращаясь к Фиг.10, фрагмент изображения, включающий по меньшей мере один объект, представлен на шаге 101. Затем формируется битовая карта объекта на шаге 102. На шаге 103 содержимое объекта, которое включает в себя двоичные биты "1" и "0", анализируется для определения, может ли преобразование битовой карты облегчить сжатие. В одном примере согласно настоящему изобретению количество двоичных битов "1" является большим, чем количество двоичных битов "0" в битовой карте, на битовой карте выполняется построчно операция исключающего ИЛИ (XOR). В другом примере на битовой карте построчно выполняется операция инвертирования. Преобразование битовой карты посредством операции XOR, операции инвертирования или другой пригодной операции имеет результатом преобразованную битовую карту, включающую в себя большее количество двоичных "0". Если выполняется преобразование, двоичная "1" записывается во флаг преобразования формата 108 записи. Наоборот, если никакого преобразования не выполняется, двоичный "0" записывается во флаг преобразования.

Затем, на шаге 104, выбирается алгоритм для сжатия битовой карты. Выбор пригодного алгоритма может зависеть от содержимого битовой карты. Например, если битовая карта включает в себя несколько строк двоичных "0", для сжатия используется алгоритм, включающий в себя правила сжатия, подобные тем, что описаны со ссылкой на Фиг. с 7A по 7H. В другом примере для сжатия используется алгоритм, включающий правила сжатия, основанные на четырех моделях наиболее значащих двух битов, которые были предварительно обсуждены. Затем выполняется сжатие по длинам серий битовой карты, как преобразованной, так и не преобразованной, в соответствии с алгоритмом сжатия, выбранным на шаге 105. Параметры и сжатые данные, полученные во время сжатия, записываются в формат 108 записи. Впоследствии сжатый поток битов получается на шаге 106 посредством соединения записанных сжатых данных.

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

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

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