Область техники, к которой относится изобретение
Настоящее изобретение относится к области уплотнения и, в частности, к способам и устройствам уплотнения видеоизображения.
Уровень техники
Последовательность изображений может занимать большой объем пространства памяти и требовать очень большой полосы пропускания передачи при представлении в неуплотненной цифровой форме. Двухточечная цифровая видеосвязь стала осуществимой несколько лет назад вслед за прогрессом компьютерных сетей и технологии уплотнения сигналов.
Попытка стандартизации для цифрового видеоуплотнения была предпринята приблизительно в 1988 году. В настоящее время комитет Экспертной группы по кинематографии (ЭГК) (MPEG) при ISO/IEC (Международная организация стандартизации/ Международная электротехническая комиссия) завершила стандарты как MPEG-1, так и MPEG-2; стандарт MPEG-4 также завершен, но все еще принимаются новые предложения. Помимо этого, CCITT (Консультативный комитет по международной телеграфной и телефонной связи) разрабатывал ряд рекомендаций - Н.261, Н.263 и Н.263+, - которые фокусируются на приложениях с низкими битовыми скоростями. Все эти попытки используют при стандартизации двухступенчатую процедуру для уплотнения видеопоследовательности. Первая ступень использует оценку движения и алгоритм компенсации для создания предсказанного видеокадра для текущего видеокадра с помощью предыдущего видеокадра, при этом вычисляется разность между текущим видеокадром и предсказанным видеокадром, которая называется остаточным изображением движения (ОИД) (MRP). Вторая ступень в стандартной процедуре состоит в кодировании ОИД с помощью дискретного косинусного преобразования (ДКП) (DCT). Такие основанные на ДКП системы не имеют хороших эксплуатационных качеств во всех обстоятельствах. При низких битовых скоростях, необходимых для персональной видеосвязи, основанные на ДКП системы вызывают заметные искажения и видимые блоковые артефакты. Для приложений с высоким визуальным качеством, таких как DVD, достигаемый коэффициент уплотнения может быть довольно низким.
Остаточные изображения движения можно кодировать с помощью иных основанных на преобразовании методов. Например, можно также использовать дискретные вейвлетные преобразования (ДВП) (DWT) и сверхполного базисного преобразования. Zakhor и Neff представили в патенте США №5699121 кодирующую систему остаточного движения на основании алгоритма сверхполного базисного преобразования, именуемого поиском согласования. Он был впервые предложен Mallat и Zhang в IEEE Transaction in Signal Processing, vol.41, No.12, Dec. 1993. Видеокодер Zakhor и Neff улучшает и визуальное качество, и С/Ш по мощности (PNSR) по сравнению со стандартными основанными на ДКП видеокодерами. Однако их система является очень медленной и характеристика уплотнения не оптимизирована вследствие приспособленной к конкретному случаю конструкции для согласованного базисного кодирования положения и квантования коэффициентов преобразования. Поэтому имеется необходимость в новом методе видеокодирования на основании сверхполного преобразования, который может обеспечить как скорость, так и эффективность.
Эта информация из уровня техники предоставлена для целей, как полагает заявитель, сделать известную информацию по возможности существенной для настоящего изобретения. Не делается обязательного допущения и не следует истолковывать, что любая из предшествующей информации составляет прототип для настоящего изобретения.
Сущность изобретения
Цель настоящего изобретения состоит в том, чтобы обеспечить способ и устройство покадрового кодирования остаточного движения на основании сверхполного базисного преобразования для видеоуплотнения. В соответствии с объектом настоящего изобретения предлагается способ кодирования остаточного изображения с помощью базисных функций из сверхполной библиотеки, содержащий следующие шаги: получают остаточное изображение, которое имеет размер и энергию; и осуществляют разложение упомянутого остаточного изображения в перечень из одного или нескольких элементов, каждый из которых представляет базисную функцию из сверхполной библиотеки, причем упомянутый шаг разложения упомянутого остаточного изображения включает в себя следующие шаги: (i) идентифицируют область замещения в остаточном изображении для представления элементом с помощью алгоритма сегментации остаточной энергии; (ii) создают поднабор базисных функций из сверхполной библиотеки, причем каждая базисная функция в этом поднаборе согласуется с областью замещения в заранее заданных пределах; (iii) идентифицируют элемент внутри поднабора базисных функций, причем упомянутый элемент служит для представления области замещения и упомянутый элемент имеет параметры; (iv) квантуют упомянутый элемент и модифицируют параметры элемента в форму, пригодную для кодирования; (v) кодируют упомянутый квантованный элемент, вычитают упомянутый элемент из области замещения в остаточном изображении, тем самым понижают энергию остаточного изображения, и используют основанный на дереве квадрантов элементный кодер, чтобы снизить размер остаточного изображения; и (vi) сравнивают сниженный размер остаточного изображения или пониженную энергию остаточного изображения с заранее заданными критериями, и повторяют шаги с (i) по (vi) до тех пор, пока эти заранее заданные критерии не будут достигнуты; посредством этого кодируют упомянутое остаточное изображение и снижают его размер до заранее заданного уровня.
В соответствии с другим объектом настоящего изобретения предлагается устройство для кодирования остаточного изображения с помощью базисных функций из сверхполной библиотеки, содержащее: средство для получения остаточного изображения, причем упомянутое изображение имеет размер и энергию; и средство для разложения упомянутого остаточного изображения в перечень из одного или нескольких элементов, каждый из которых представляет базисную функцию из сверхполной библиотеки, причем упомянутое средство для разложения упомянутого остаточного изображения включает в себя: (i) средство для идентификации области замещения в остаточном изображении для представления элементом с помощью алгоритма сегментации остаточной энергии; (ii) средство для создания поднабора базисных функций из сверхполной библиотеки, причем каждая базисная функция в этом поднаборе согласуется с областью замещения в заранее заданных пределах; (iii) средство для идентификации элемента внутри поднабора базисных функций, причем упомянутый элемент служит для представления области замещения и упомянутый элемент имеет параметры; (iv) средство для квантования упомянутого элемента и для модификации параметров элемента в форму, пригодную для кодирования; (v) средство для кодирования упомянутого квантованного элемента, вычитания упомянутого элемента из области замещения в остаточном изображении, что понижает энергию остаточного изображения, и для использования основанного на дереве квадрантов кодера элемента, чтобы снизить размер остаточного изображения; и (vi) средство для сравнения сниженного размера остаточного изображения или пониженной энергии остаточного изображения с заранее заданными критериями; посредством чего кодируют упомянутое остаточное изображение и снижают его размер до заранее заданного уровня.
В соответствии с другим объектом настоящего изобретения предлагается компьютерный программный продукт, содержащий машиночитаемый носитель с записанной на нем компьютерной программой для выполнения способа кодирования остаточного изображения с помощью базисных функций из сверхполной библиотеки, содержащего следующие шаги: получают остаточное изображение, которое имеет размер и энергию; и осуществляют разложение упомянутого остаточного изображения в перечень из одного или нескольких элементов, каждый из которых представляет базисную функцию из сверхполной библиотеки, причем упомянутый шаг разложения упомянутого остаточного изображения включает в себя следующие шаги: (i) идентифицируют область замещения в остаточном изображении для представления элементом с помощью алгоритма сегментации остаточной энергии; (ii) создают поднабор базисных функций из сверхполной библиотеки, причем каждая базисная функция в этом поднаборе согласуется с областью замещения в заранее заданных пределах; (iii) идентифицируют элемент внутри поднабора базисных функций, причем упомянутый элемент служит для представления области замещения и упомянутый элемент имеет параметры; (iv) квантуют упомянутый элемент и модифицируют параметры элемента в форму, пригодную для кодирования; (v) кодируют упомянутый квантованный элемент, вычитают упомянутый элемент из области замещения в остаточном изображении, тем самым понижают энергию остаточного изображения, и используют основанный на дереве квадрантов элементный кодер, чтобы снизить размер остаточного изображения; и (vi) сравнивают сниженный размер остаточного изображения или пониженную энергию остаточного изображения с заранее заданными критериями, и повторяют шаги с (i) по (vi) до тех пор, пока эти заранее заданные критерии не будут достигнуты; посредством этого кодируют упомянутое остаточное изображение и снижают его размер до заранее заданного уровня.
Краткое описание чертежей
Фиг.1 иллюстрирует общую схему систем видеоуплотнения, которые используют сверхполное базисное преобразование, и связанных способов кодирования согласно одному варианту осуществления настоящего изобретения.
Фиг.2 является примером остаточного изображения движения, обработанного одним вариантом осуществления настоящего изобретения.
Фиг.3 иллюстрирует простой словарь с 16 базами для использования с одним вариантом осуществления настоящего изобретения.
Фиг.4 описывает весь процесс элементного разложения на основании сверхполного базиса согласно одному варианту осуществления настоящего изобретения.
Фиг.5 описывает базисный шаг, выполняемый алгоритмом сегментации остаточной энергии (АСОЭ) (RESA) согласно одному варианту осуществления настоящего изобретения.
Фиг.6 иллюстрирует первый шаг АСОЭ согласно одному варианту осуществления настоящего изобретения.
Фиг.7 иллюстрирует второй шаг АСОЭ: схему роста по горизонтали согласно одному варианту осуществления настоящего изобретения.
Фиг.8 иллюстрирует второй шаг АСОЭ: схему роста по вертикали согласно одному варианту осуществления настоящего изобретения.
Фиг.9 описывает поиск элемента выполнения согласования с помощью алгоритма постепенного удаления (АПУ) (PEA) согласно одному варианту осуществления настоящего изобретения.
Фиг.10 иллюстрирует, как сформировать подсловарь базиса согласования и кандидатов отыскиваемого положения согласно одному варианту осуществления настоящего изобретения.
Фиг.11 иллюстрирует быстрое вычисление энергии области согласно одному варианту осуществления настоящего изобретения.
Фиг.12 иллюстрирует параметры для одного элемента согласно одному варианту осуществления настоящего изобретения.
Фиг.13 является примером карты положения элемента согласно одному варианту осуществления настоящего изобретения.
Фиг.14 является блок-схемой алгоритма, иллюстрирующей процесс кодирования элемента, согласно одному варианту осуществления настоящего изобретения.
Фиг.15 является блок-схемой алгоритма, иллюстрирующей декодирование уплотненного остаточного сигнала согласно одному варианту осуществления настоящего изобретения.
Подробное описание изобретения
Настоящее изобретение представляет собой новый кодер для кодирования остаточного изображения на основании сверхполного преобразования, используемого для систем видеоуплотнения со скомпенсированным движением. Данное изобретение аналогично предыдущим видеокодерам поиска согласования в том, что они разлагают остаточное изображение в перечень элементов, который представляет базисные функции из сверхполного словаря. Процесс нахождения элементов, однако, выполняется с помощью алгоритма сегментации остаточной энергии (АСОЭ) и алгоритма постепенного удаления (АПУ). Базисный словарь может быть очень большим для того, чтобы характеризовать признаки, часто появляющиеся в остаточных изображениях движения. Чтобы найти элемент, АСОЭ идентифицирует приблизительную форму и положение областей с высокой энергией в остаточном изображении движения, так что может быть найдено хорошее согласование путем сравнения с меньшим поднабором баз в словаре. Далее, АПУ последовательно удаляет образы-кандидаты из рассмотрения путем предварительного вычисления энергии поисковых окон, посредством чего снижается время вычислений, необходимое для того, чтобы найти наилучшее согласование. Когда же согласованный элемент найден, остаточное изображение обновляется удалением части, характеризуемой этим элементом. Предшествующие шаги по нахождению элементов и обновлению остаточных изображений повторяются до тех пор, пока не будут достигнуты желательные битовая скорость или качество.
Изобретение вводит новую схему модульного квантования для поиска согласования в сверхполном базисе, что изменяет процедуру нахождения элементов. Коэффициенты, получаемые непосредственно из преобразования, являются непрерывными значениями с плавающей запятой, которые требуется квантовать для оптимального цифрового кодирования при битовых ресурсах. В алгоритме поиска согласования необходимо использовать петлевой квантователь, где каждый найденный элемент сначала квантуется, а затем используется для обновления остаточного изображения. Как таковой, каждый элемент воздействует на выбор последующих элементов. Если квантователь конкретизируется перед тем, как начинается кодирование, как и в предшествующих способах поиска согласования, трудно оптимизировать схему квантования, т.к. оптимальная конструкция квантователя зависит от статистики перечня выбранных элементных модулей. Схема квантования согласно настоящему изобретению выбирает квантователь адаптивно в процессе поиска элементов.
В дополнение к элементному модулю в основанном на сверхполном преобразовании кодере необходимо передавать указатель выбранного базиса и положение элементов. Изобретение включает в себя способ эффективно закодировать информацию элементного положения. Распределение элементных положений образует двумерную карту, где пиксельные значения один или ноль представляют, соответственно, наличие элемента или его отсутствие в каждом положении. Метод, подобный дереву квадрантов, обеспечивает кодирование карты положений. Информация модулей и базисного указателя включается в кодирование положения. Элементы для различных каналов цветного видео (Y, U, V) кодируются независимо.
Параметры элементов передаются после того, как они закодированы в уплотненный вариант остаточных изображений. Для процесса декодирования декодер восстанавливает остаточное изображение через интерпретацию кодированного битового потока назад в параметры элементов и комбинирование информации элементов для образования восстановленного потока остаточных изображений, которые затем комбинируются со скомпенсированным изображением движения, чтобы формировать восстановленный видеопоток.
Настоящее изобретение представляет собой способ кодирования остаточных изображений движения, содержащий следующие шаги: формируют элементное разложение остаточного изображения в пространстве сверхполного базиса с помощью модифицированного алгоритма поиска согласования; выбирают модульный квантователь; кодируют карту положений, модуль, а также указатель для выбранного базиса. Настоящее изобретение далее предлагает способ декодирования остаточных сигналов, которые закодированы с помощью вышеупомянутого способа кодирования.
Фиг.1 иллюстрирует связанную обработку, исполняемую устройством 10 видеоуплотнения, которое использует кодер 20 остаточного изображения, согласно одному варианту осуществления настоящего изобретения. Видеокадр сначала обрабатывается блоком 30 оценки движения, который сравнивает текущий кадр с одним или двумя опорными кадрами. В большинстве случаев, объекты в видеоизображении изменяют свои положения в следующих друг за другом кадрах, тогда как фон остается тем же самым. Поскольку опорные кадры переданы на видеодекодер 12, некоторые области в опорном кадре могут использоваться для построения текущего кадра, блок 30 оценки движения определяет те области в опорных кадрах, которые аналогичны областям в текущем кадре. Компенсатор 32 движения вырабатывает разность между этими аналогичными областями и объединяет их в качестве остаточного изображения движения. Соотношения положений между аналогичными областями представляются в качестве векторов движения, которые обрабатываются кодером 34 вектора движения. Сначала остаточное изображение обрабатывает блок 40 элементного разложения, а затем элементный кодер 42 уплотняет получающиеся элементы. Кодированные векторы движения и элементы объединяются в один битовый поток мультиплексором 22. Уплотненное видеоизображение передается и сохраняется устройством 24, которое может доставлять видеоизображение в уплотненном формате к видеодекодеру 12.
Нижняя часть фиг.1 иллюстрирует декодер 12, в котором демультиплексор 26 разделяет уплотненный видеосигнал, посылая соответствующие биты на декодер 36 вектора движения и декодер 28 остаточного изображения соответственно. Блок 38 восстановления движения формирует кадр предсказания из опорного кадра и вектора движения. Декодер 28 остаточного изображения восстанавливает остаточное изображение. Эти два сигнала, а именно кадр предсказания и остаточный кадр, суммируются для генерирования окончательного восстановленного видеокадра.
Фиг.2 представляет собой примерное остаточное изображение движения для цветового канала Y. Исходное остаточное изображение имеет как отрицательные, так и положительные значения. Для цели отображения остаточного изображения в качестве изображения с 256 уровнями серого пиксельные значения остаточного изображения сдвигаются и масштабируются так, что чистый серый цвет означает ноль, тогда как черный и белый цвета представляют соответственно отрицательные и положительные значения. Например, остаточное изображение содержит несколько высокоэнергетических областей, которые соответствуют движению объектов в видеоизображении.
Большинство методов уплотнения сигналов преобразуют исходные данные в какой-нибудь более компактный формат посредством математических преобразований различных видов. Некоторые математические преобразования, такие как ДКП и ДВП, используют полный базис, который образует матрицу обратимого преобразования. В последнее время значительное внимание привлекли к себе сверхполный базис и связанные с ним алгоритмы преобразования. Число базисов в словаре сверхполного базиса намного больше, нежели размерность исходных данных. Преимущество сверхполного базиса состоит в том, что преобразованные коэффициенты более эффективны в представлении действительных признаков в исходном сигнале. Существует много математических методов для построения базисного словаря для разных сигналов. Для остаточных видеоизображения движения построено несколько словарей и доказано, что они хорошо покрывают признаки в остаточных изображениях. Например, базисный словарь на основе сепарабельных функций Габора описан Neff и Zakhor в «Very Low Bit Rate Video Coding Based on Matching Pursuits», IEEE Transactions on Circuits and Systems for Video Technology, Feb. 1997, 158-171, а базисный словарь на основе функций Хаара описан Vleeschouwer и Macq в «New dictionaries for matching pursuit video coding», Proc. of the 1998 International Conference on Image Processing, vol.1, 764-768. Фиг.3 является простым примерным словарем, содержащим 16 базисов. Любой из вышеуказанных словарей можно использовать с настоящим изобретением. В частности, в отношении вышеупомянутого словаря Габора, имеется 400 двумерных явно упомянутых функций. Однако в действительности он включает в себя намного больше базисных структур неявно, поскольку каждая из этих 400 двумерных функций может быть помещена в любом возможном положении в изображении. Использование размера кадра в 176×144 пиксела предполагает, что словарь в действительности содержит 400×176×144=5,7 миллионов базовых структур, что делает его в высшей степени сверхполным. Преобразование, непосредственно использующее «алгоритм поиска согласования», описанный S.Mallat и Z.Zhang в «Matching Pursuits With Time-Frequency Dictionaries», IEEE Transaction in Signal Processing, vol.41, No.12, Dec. 1993, потребует чрезвычайно большого числа вычислений, чтобы определить коэффициенты преобразования. Поиск согласования для уплотнения видеоизображения, изобретенный Zakhor и Neff в патенте США №5699121, снижает бремя вычислений, однако остается дорогим в вычислительном отношении. Настоящее изобретение предлагает путь преобразования остаточных изображений на основании общих словарей, которое выполняется блоком 40 элементного разложения, и путь кодирования преобразованных коэффициентов, который представляет собой задачу элементного кодера 42.
Работа блока 40 элементного разложения полностью описывается на фиг.4 согласно одному варианту осуществления. Первый шаг (блок 61), исполняемый блоком 40 элементного разложения, состоит в том, чтобы найти начальную область поиска. Этот шаг реализуется алгоритмом сегментации остаточной энергии (АСОЭ), причем один вариант его осуществления показан на фиг.5. АСОЭ основан на идее общего наращивания областей. Сначала он выбирает блок 2×2 в качестве начальной точки для наращивания области (блок 70). Этот шаг требует разделения остаточного изображения на блоки 16×16, как показано на фиг.6. Энергия, которая является суммой квадратов всех пиксельных интенсивностей, вычисляется для каждого блока, и блок с наивысшей энергией определяется, к примеру, в качестве блока 71, показанного на фиг.6. Блок 71 далее разделяется на четыре подблока 8×8, и определяется подблок 72 с наивысшей энергией. В этом подблоке 72 размером 8×8 также определяется подблок 73 размером 2×2 с наивысшей энергией, причем этот блок и будет использоваться в качестве начальной точки для наращивания области.
Следующий шаг АСОЭ (блок 74, показанный на фиг.5), состоит в проверке блока 2×2 слева от текущей области. Фиг.7 иллюстрирует этот шаг АСОЭ. Порог вычисляется динамически как
Т=AE*max(7-AU, 5)/10,
где AU есть число блоков, которые добавлены слева от начального блока, а АЕ есть средняя энергия на блок 2×2 текущей области. Если энергия проверенного блока 2×2 больше, чем текущий порог, проверенный блок 2×2 группируется с текущей областью, образуя вместе новую большую текущую область. В противном случае на этой стороне найдена конечная точка, и мы не группируем блоки вместе. Аналогичным симметричным образом проверяется блок 2×2 справа от текущей области. Продолжаем наращивать сначала левую сторону, а затем правую сторону до тех пор, пока не будут найдены конечные точки на обеих сторонах или пока ширина не достигнет 32 (что бы ни наступило первым). После этого шага образуется горизонтальный ленточный прямоугольник 75, причем размерность ленты составляет 2*2m, 1≤m≤16.
Последний шаг АСОЭ (блок 76 на фиг.5) состоит в наращивании области по вертикали на основе шага 75, как показано на фиг.8. Предположим, что ширина ленты 75 равна W. Рассмотрим ленточный прямоугольник 2*W над текущей областью вместе с порогом:
Т=AEs*max(7-AUs, 5)/10,
где AUs есть число прямоугольников 2*W, которые добавлены над начальной лентой, a AEs есть средняя энергия на прямоугольник 2*W, включенный в текущую область. Если проверенный прямоугольник 2*W имеет энергию, которая больше, чем порог, включаем ее в текущую область. В противном случае на этой стороне найдена конечная точка. Аналогичным симметричным образом проверяется блок 2*W ниже текущей области. Продолжаем наращивать сначала сверху, а затем снизу до тех пор, пока не будут найдены конечные точки на обеих сторонах или пока высота не достигнет 32 (что бы ни наступило первым). В конце концов получим прямоугольник 77, который имеет размерность 2n*2m, 1≤n,m≤16.
Снова ссылаясь на фиг.4, иллюстрируется процесс нахождения ближайшего согласованного базиса из заданного словаря (блок 62). Степень согласования между базисом и остаточным изображением представляется абсолютной величиной (модулем) их скалярного произведения, которое называется элементным модулем, при этом большой модуль подразумевает хорошее согласование. Процесс определения этого модуля требует вычисления нескольких скалярных произведений и выбора одного с наибольшим модулем в качестве текущего элемента. Этот процесс может быть самой медленной частью алгоритма поиска согласования. В классическом алгоритме поиска согласования нужно было бы вычислить скалярное произведение между остаточным изображением и каждым из миллионов элементов в словаре, чтобы определить модуль. К примеру, в прототипе блок 16*16 с наивысшей энергией в остаточном изображении просто выбирается в качестве начальной области поиска: каждая базисная структура центрируется в каждом положении в выбранном блоке и вычисляется скалярное произведение между базисной структурой и соответствующей остаточной областью. Для словаря с 400 базисами этот процесс требует 256×400=102400 вычислений скалярных произведений. Фиг.9 иллюстрирует новый процесс поиска согласования согласно настоящему изобретению.
Результирующий прямоугольник 77 АСОЭ на фиг.8 обеспечивает начальную оценку формы высокоэнергетического признака. Она используется для того, чтобы отфильтровать базисы в словаре, которые имеют форму, слишком отличную от прямоугольника АСОЭ. Затем формируется поднабор базисов согласования (блок 80). Предположим, что ширина и высота прямоугольника равны соответственно w и h, тогда формируется подсловарь, содержащий все базисы с формами, определенными соответственно шириной (width) и высотой (height), которые удовлетворяют условиям:
w-tw1≤ширина≤w+tw2 и h-th1≤высота≤h+th2,
где tw1, trw2, th1 и th2 являются значениями, установленными для ограничения размера базиса. Эти значения могут изменяться и регулироваться согласно структуре словаря. Наибольшие и наименьшие размеры проверенных базисов иллюстрируются как прямоугольники 90 и 91, показанные на фиг.10. Например, блок В 80 является простым примером под словаря, содержащим четыре базиса.
АСОЭ может далее оценивать положение высокоэнергетических признаков в остаточном изображении. Положения-кандидаты для базисов согласования выбираются вокруг центра прямоугольника 77 АСОЭ (блок 81). Фиг.10 показывает малый прямоугольник 92, центр которого тот же самый, что и у прямоугольника 77 АСОЭ. Предполагается, что все пикселы в прямоугольнике 92 будут работать в качестве центра для проверенной остаточной области. Прямоугольник 94 на фиг.10 является примером, центром которого является точка 93, либо левый верхний угол прямоугольника 92. Предполагается, что ширина (ws) и высота (hs) прямоугольника 92 должны быть переменными по отношению к прямоугольнику 77 АСОЭ. Это соотношение таково:
ws=2*min(w/2+1,6) и hs=2*min(h/2+1,6).
Размер прямоугольника 92 может приниматься по иным правилам или просто фиксироваться при воплощении. Идея базисов состоит в том, что хорошее согласование располагается вокруг центра прямоугольника 77 АСОЭ. Далее, любые положения в прямоугольнике 92, которые уже содержат центр элемента, не будут рассматриваться как какие-либо новые элементы. Точка 95 на фиг.10 является примером. Следует отметить, что прототип не ставит такого ограничения. Идея этого типа ограничения в том, что если один элемент обеспечивает хорошее попадание, следует удалить энергию вокруг его центра без введения чересчур большой излишней энергии на его границе. По существу, для алгоритма поиска согласования нежелательно возвращаться к тому же положению, чтобы получить второй элемент. Это ограничение запрета на повторение положения почти не влияет на производительность кодирования и может сделать более простым кодирование информации положения элемента.
Следующий шаг обработки (блок 89 на фиг.9) называется алгоритмом постепенного удаления (АПУ) для поиска остаточного согласования. Он не зависит от способа, используемого для формирования словаря проверочных базисов и набора проверочных положений. Например, АПУ будет работать, если подсловарь является целым словарем, а набор положений-кандидатов является набором координат, содержащим целое остаточное изображение. АПУ представляет собой способ нахождения ближайшего базиса согласования более эффективно путем постепенного удаления кандидатов сравнения из рассмотрения. Это контрастирует с классическим поиском согласования, который сравнивает все базисы-кандидаты на всех возможных положениях. Сначала максимальный модуль устанавливается на нуль (блок 82). Рассматривается следующий базис b(k,l) (блок 83), где k и l представляют ширину и высоту двумерной базисной функции. Формируется область того же размера, центрированная на одном положении-кандидате r(k,l,p) в остаточном изображении (блок 84). Блок 85 сравнивает ||r(k,l,p)||, энергию r(k,l,p) с текущим максимальным модулем (Mm), чтобы решить, имеется ли необходимость вычислять скалярное произведение между r(k,l,p) и b(k,l). Чтобы пояснить эту операцию, вспомним математическое неравенство треугольников:
|<r(k,l,p),b(k,l)>|≤||r(k,l,p)|| ||b(k,l)||.
Цель поиска согласования состоит в нахождении максимума |<r(k,l,p), b(k,l)>|. Предположим, что текущий максимальный модуль равен Mm. Если для базиса b(k,l) в положении р соответствующий остаток r(k,l,p) удовлетворяет ||r(k,l,p)|| ||b(k,l)||≤Mm, то:
|<r(k,l,p), b(k,l)>|≤||r(k,l,p)|| ||b(k,l)||≤Mm.
В этом случае не нужно вычислять скалярное произведение |<r(k,l,p), b(k,l)>|, и область r(k,l,p) перемещается в следующее положение. Норму базиса ||b(k,l)|| можно вычислить заранее (в действительности большинство базисов нормированы, а именно ||b(k,l)||=1, и единственное излишество для этой проверки тогда состоит в вычислении энергии r(k,l,p). Эффективный алгоритм для определения ||r(k,l,p)|| описывается ниже.
Предположим, что имеется n различных размеров базисной высоты {v1, v3,..., vn} и m различных размеров базисной ширины {h1, h2,..., hm}, которые упорядочены по нарастанию. Размерность поискового прямоугольника равна hs*ws, а левая верхняя точка поискового прямоугольника равна р(х,у). Значения энергии hs*ws*n*m можно вычислить посредством следующих четырех шагов:
Шаг 1: Вычислить энергию для s=hm+k столбцов (фиг.11 показывает пример столбцов). Эти столбцы отцентрированы в (x-hm/2+i,у), где i=0, 1,..., s-1. Их высота равна v1. Их энергия представляется как С1,0(0), C1,1(0),...C1,s(0) и вычисляется как:
C1,i(0)=e(x-hm/2+i, у-v1/2)+...+e(x-hm/2+i, у)+...+e(x-hm/2+i, у+v1/2),
где е(х,у) представляет энергию пикселов в положении (х,у).
Энергии для следующих s столбцов с теми же самыми координатами, как и в вышеприведенных полосках, и длиной v2 можно вычислить как:
С2,i(0)=C1,i(0)+Extra(v2-v1) энергия пикселов, i=1, 2,...s.
В общем случае имеем:
Сj,i(0)=Cj-1,i(0)+Extra(vj-v(j-1)) энергия пикселов, i=1, 2,...s; j=1, 2,...n.
Шаг 2: Вычислить энергию столбцов, которые сдвинуты по вертикали от столбцов в шаге 1, с помощью:
Cj,i(a)=Cj,i(a-1)-e(x-hm/2+i, у-v1/2+a-1)+e(x-hm/2+i, у+v1/2+a), а=1..., hs,
где а представляет число сдвига по вертикали, соответствующее у.
Шаг 3: Вычислить энергии областей с высотой vj, (j=1,...,n) и шириной h1, h2,..., hm и центром (х, у+а), (v=0, 1,..., hs), с помощью:
Sj,i(0,a)-Cj,(hm-h1)/2(a)+...-+Cj,hm/2(a)+...+Cj,(hm+h1)/2(a)
Sj,2(0,a)=Sj,i(0,a)+Extra(h2-h1) энергия столбцов.
В общем случае:
Sj,i(0,a)=Sj,i-1(0,a)+Extra(h2-h(i-1)) энергия столбцов, i=1,..., m.
Шаг 4: Вычислить энергии первого набора областей с базовой длиной по вертикали vj(j=1,..., n) и базовой длиной по горизонтали hi(i=1,..., m) и центром (x+b, у+a) (b=1,...ws и a=1,...,hs) с помощью:
Sj,i(b,a)=Sj,i(b-1, a)-Cj,(hm-hi)/2+b-1(a)+Cj,(hm+hi)/2+b(a).
Максимальный модуль может последовательно обновляться в процессе поиска согласования; это может постепенно определить поисковое пространство. Несколько базисов могут иметь одинаковые размеры, тем самым одно вычисление энергии может заменить вычисления нескольких скалярных произведений. Производительность АПУ также относится к тому, как часто находится хорошее согласование (не обязательно наилучшее согласование). Вследствие того, что большие области всегда содержат больше энергии, базисы большей размерности проверяются первыми.
Если ||r(k,l,p)||>Mm, блок 86 исполняется для вычисления скалярного произведения (р) между r(k,l,p) и b(k,l). Блок 87 сравнивает абсолютное значение р с текущим максимальным модулем Mm. Если |р|>Mm, в качестве |р| устанавливается новое Mm и записываются соответствующие указатель и положение базиса. Независимо от этого мы продолжаем возвращаться к блоку 84 до тех пор, пока все положения поиска не будут проверены. Затем блоки 83-88 запускаются повторно до тех пор, пока не будут проверены все базисы-кандидаты. Наконец, получается элемент, который включает в себя три параметра: 1. Указатель базиса в словаре, который дает наилучшее согласование; 2. Местоположение наилучшего согласования в остаточном изображении с координатами (х, у); и 3. Скалярное произведение (р) между базисом и остаточным изображением. Фиг.12 показывает пример элемента на остаточном изображении.
Снова ссылаясь на фиг.4, шаг после нахождения элемента состоит в записи элементных параметров (блок 63). Отметим на этой стадии, что никакого квантования элементного модуля не выполняется. Блок 64 принятия решения будет принимать решение, когда начнется квантование элемента. Его работа зависит от задачи управления скоростью, определенной системой видеоуплотнения. Если коэффициент уплотнения фиксирован, блок 64 будет проверять, доступны ли все еще биты для большего числа элементов. Поскольку еще не сделано никакого действительного кодирования, следует оценить использованные биты для кодирования текущих элементов. Пусть «Bip» представляет среднее число битов для кодирования базисных указателей и положений, «Bm(i)» представляет действительное число битов для i-го элементного модуля без квантования. При выделении одного бита на знак скалярного произведения (р) число использованных битов для n элементов оценивается как:
Использованные биты = n*(Bip+1)+∑(Bm(1)+Bm(2)+...Bm(n)),
где «Bip» инициализируется согласно экспериментальным данным для первого остаточного кадра и устанавливается как действительное значение последнего кадра. Bm(i) может быть известно точно для нескольких модулей. Важно то, что модуль будет квантован позднее и даст меньшее число подлежащих использованию битов, нежели оценено в данный момент. Таким образом, на этой стадии будет как правило меньше элементов, чем то, что можно закодировать. Если видеосистема желает достичь некоторого качества, которое определяется среднеквадратичной ошибкой (СКО) (MSE) закодированного остаточного изображения по сравнению с действительным остаточным изображением, блок 64 будет сравнивать текущую достигнутую СКО с целевой СКО. СКО после введения одного элемента обновляется согласно следующему уравнению:
CKO(n)=CKO(n-1)-p(n)*p(n),
где СКО(n) представляет СКО после использования n элементов, а р(n) представляет скалярное произведение n-го элемента. Сначала СКО, или СКО (0), устанавливается на энергию исходного остаточного изображения. После того, как выполняется квантование, СКО(n), вероятно, возрастет, а потому больше не будет достигаться целевая СКО. В итоге, если биты доступны или задача качества не достигнута, остаточное изображение будет обновляться на основании текущего элемента (блок 65), за чем последует поиск другого элемента, вновь начиная с блока 61. В противном случае, если битовая или качественная цель достигнута, исполняется блок 66 для проектирования квантования. Обновление остаточного изображения - один шаг для стандартного алгоритма поиска согласования - можно математически описать как:
r(k,l,p)=r(k,l,p)-p(n)*b(k,l).
Все области, не охваченные текущим элементом, будут неизменными.
Проект квантователя (блок 66) основан на значении минимального модуля (Minm), найденном на данный момент. Размер шага квантования (ШК) (QS) устанавливается так:
Все элементы, найденные до этого пункта, будут квантованы с помощью вышеуказанного ШК в простой схеме скалярного квантования со считыванием среднего. Вслед за этим остаточное изображение снова обновляется согласно теперь квантованному перечню элементных модулей 67. Предположим, что элементный коэффициент до и после квантования равен, соответственно, p(i) и q(i) (i=1,..., n). Предположим, что соответствующими базисами являются b(i), (i=1,..., n). Остаточное изображение после n неквантованных элементов равно:
Е(n)=(Исходное остаточное)-р(1)b(1)-р(2)b(2)-...-p(n)b(n).
Его энергия ||Е(n)|| также известна. Имеется два пути вычислить остаточную энергию после квантования. Первый путь - это просто вычислить остаточное изображение после квантования как:
EQ(n)=(Исходное остаточное)-q(1)b(1)-q(2)b(2)-...-q(n)b(n).
Другой путь состоит в его рекурсивном обновлении. Предположим, что ошибка квантования для p(i) равна Δp(i). Тогда остаточное изображение, в котором только р(n) проквантованы, есть:
EQ(1)=Е(n)-Δр(n)b(n) и ||EQ(1)||=||Е(n)||+Δр(n)*Δр(n)-2Δр(n)<Е(n),b(n)>.
Остаток с квантованием р(n) и р(n-1) становится:
EQ(2)=EQ(1)-Δp(n-1)g(n-1).
Это соотношение является верным рекурсивно и может быть записано как:
EQ(i)=EQ(i-1)-Δp(n-i+1)g(n-i+1), i=1, 2,...n, EQ(0)=E(n).
Соответствующая энергия равна:
||EQ(i)||=||EQ(i-1)||+Δp(n-i+1)Δp(n-i+1)-2*Δp(n-i+1)<EQ(i-1),g(n-i+1)>.
Наконец, мы возьмем EQ(n) и ||E(n)||, которые являются начальной точкой для дальнейшего нахождения элементов. Важно то, что элементы могут быть в любом порядке для рекурсивного обновления - обновление не нужно проводить в порядке, в котором найдены элементы.
Поскольку модули элементов квантуются, теперь будет необходимо больше элементов для достижения цели управления скоростью или качества. Поэтому блок 68 исполняется для нахождения дополнительных элементов. Процесс тот же самый, что и блоки 61-63. Однако на этой стадии модули элементов будут квантоваться немедленно. Нам теперь нужно иметь дело с элементами, модули которых меньше, чем (ШК-ШК/4), без их отбрасывания путем установки их величины квантования на нуль. Используемая схема дается ниже.
1. Если модуль элемента больше, чем (ШК-ШК/4), то квантователь использует ШК.
2. В противном случае, если модуль элемента больше, чем (ШК/2-ШК/8), он квантуется как значение ШК/2.
3. В противном случае, если модуль элемента больше, чем (ШК/4-ШК/16), он квантуется как значение ШК/4.
4. В противном случае, если модуль элемента больше, чем (ШК/8-ШК/32), он квантуется как значение ШК/8.
На практике, как правило, достаточно трех уровней вниз, хотя можно использовать больше уровней.
После блока 68 исполняется реальный логический блок управления скоростью (блок 69). Поскольку все элементы квантуются на этой стадии в цикле, можно оценить достигнутое качество или число использованных битов. Когда достигается цель уплотнения, система перейдет в элементный кодер 42. В противном случае, остаточное изображение будет обновляться на основании квантованного модуля элемента, и система возвратится к блоку 68, чтобы найти следующий элемент. Для цветного видео остаточное изображение содержит несколько каналов, т.е. каналы Y, U и V. Блок 40 разделения элементов будет использоваться для каждого канала независимо. С этой схемой каждый канал может иметь свой собственный битовый ресурс или желательную цель качества. Имеется несколько способов выделения битов, которые можно использовать для выделения битовых ресурсов для разных каналов.
Все элементы проходят к элементному кодеру 42 для выведения в уплотненном виде. Настоящее изобретение рассматривает распределение элементов для каждого канала как двузначную карту, как показано на фиг.13. Черные пикселы представляют элементы в их соответствующем положении, тогда как белые пикселы представляют отсутствие элементов в этом положении. Для кодирования положений, содержащих элементы, можно использовать метод наподобие дерева квадрантов, хотя, как нетрудно понять, можно использовать и иные методы. Другие параметры каждого элемента могут быть закодированы после информации положений элементов, к примеру, с помощью кодирования с переменной длиной, однако и другие методы кодирования могут использоваться, как известно специалистам в этой области. Процедура кодирования для сигнала параметров элементов иллюстрируется на фиг.14 и более подробно описывается ниже.
Первый шаг кодирования элементов состоит в разложении всей карты элементов, например, как показано на фиг.13, на n*n блоков (блок 101). Значение n может быть либо 16 (для канала Y), либо 8 (для каналов U и V). Для каждого блока n*n, если в блоке нет элементов, выводится нулевой бит; в противном случае выводится единичный бит, и блок обрабатывается дальше для помещения элементов в декодер. Для этого используется процедура разложения дерева квадрантов, и она обобщается в следующих четырех шагах.
Шаг 1. Инициализировать перечень элементных блоков (ПАБ) (LAB) с одним элементом - самим блоком n*n.
Шаг 2. Взять один элемент е из ПАБ. Если размер е равен 1*1, вывести все элементные параметры за исключением положения, а именно, должны быть выведены базисный указатель, модуль и знак скалярного произведения, затем перейти к шагу 4; в противном случае перейти к шагу 3.
Шаг 3. Вывести биты комбинации элементов четырех подблоков из е: а1а2а3а4, где ai (i=1, 2, 3, 4) является единицей, если в соответствующем подблоке имеется элемент, и нулем в противном случае. Поместить все подблоки i со значением аi, равным 1, в конец ПАБ и вернуться к шагу 2.
Шаг 4. Проверить, пуст ли ПАБ. Если он не пуст, вернуться к шагу 2. В противном случае кодирование заканчивается для одного блока n*n.
Указатель базиса и модуль элемента могут быть закодированы с помощью кодера переменной длины для сохранения битов, поскольку эти параметры сигнала могут быть распределены равномерно. Информация положения элемента может кодироваться неявно путем записи процедуры разложения данными 0/1 битов. Способ кодирования переменной длины может использоваться для кодирования битов комбинации элементов четырех подблоков: а1а2а3а4. Имеется 15 видов комбинаций для битов комбинации элементов, а1а2а3а4, причем следует отметить, что 0000 невозможна. Однако некоторые комбинации, такие как 1000, случаются с гораздо более высокой вероятностью, чем остальные комбинации. Вероятность разных комбинаций можно оценить в экспериментах и использовать для создания проекта таблицы переменной длины. Далее, следует отметить, что распределение вероятности может быть переменным для разных каналов и разных плотностей элементов. Поэтому можно использовать множество таблиц, и информация категории блока может кодироваться сначала, так что декодер знает, какую таблицу следует использовать для целей декодирования.
Фиг.15 иллюстрирует элементный декодер 46, который выполняет операции, обратные к тем, что выполнялись элементным кодером 42. Сначала элементный декодер 46 принимает один бит, представляющий состояние для текущего блока n*n. Если значение равно единице, он обрабатывается по процедуре разложения симметричного дерева квадрантов. Сначала блок n*n разделяется на четыре подблока. Биты комбинации элементов для этих четырех подблоков декодируются с помощью обратного кодирования переменной длины (КПД) (VLC). Затем все подблоки со значением 1 помещаются в перечень элементных блоков (ПАБ). ПАБ обновляется динамически путем рекурсивного разложения каждого элемента в ПАБ и получения его битов комбинации элементов. Если элемент из ПАБ является блоком 1*1, указатель и модуль элементного базиса должны декодироваться с помощью таблиц обратного КПД, затем должен считываться бит, представляющий знак скалярного произведения. элементный декодер для одного блока n*n заканчивается, если ПАБ становится пустым.
Декодированный сигнал элементных параметров проходит затем к остаточному восстановителю 48, который формирует один канал остаточного изображения с помощью способа классического поиска согласования. Сначала все пикселы на остаточном изображении устанавливаются в нуль. Затем каждый элемент добавляется один за другим с помощью следующей процедуры. Пусть q(i) и b(i,k,l) представляют соответственно коэффициент i-го элемента и соответствующую двумерную базисную матрицу. Если (x(i), у(i)) представляет местоположение i-го элемента, то матрица q(i)*b(i,k,l) добавляется к остаточному изображению, построенному перед тем в положении (x(i), у(i)), чтобы получить новое текущее остаточное изображение. Процесс этот повторяется до тех пор, пока все элементы не будут добавлены в каналы. Когда же каждый канал разложен, процесс заканчивается, и остаточное изображение восстановлено.
Те, кто знаком с предшествующей техникой видеокодирования, основанного на поиске согласования, увидят несколько преимуществ, связанных с методами согласно настоящему изобретению. Процесс разложения элементов на основании сверхполного базисного пространства ускорен за счет процедуры более точной оценки области энергии и за счет алгоритма постепенного удаления кандидатов. Проект квантователя элементного модуля целиком выбирается схемой элементного разложения, тогда как предшествующие аналоги определяли квантователь перед тем, как начиналось преобразование. Наконец, процесс кодирования элементов более эффективен, потому что в схеме разложения на основании дерева квадрантов применяются пространственные соотношения между элементами. В частности, прототип собирает все элементы в одномерный список, делая его тем самым трудным для их эффективного кодирования, по сравнению с настоящим изобретением.
Варианты осуществления изобретения, описываемые здесь, как очевидно, могут изменяться множеством способов. Такие изменения не должны рассматриваться как отход от сущности и объема изобретения, и все такие модификации, как будет очевидно для специалиста, предназначены для включения в объем нижеследующей формулы изобретения.
Изобретение относится к системам сжатия видеоизображения и предназначено для эффективного кодирования остаточного изображения движения, которое генерируется в процессе оценки и компенсации движения. Техническим результатом является собственно создание простого и эффективного способа и устройства покадрового кодирования остаточного движения на основании сверхполного базисного преобразования для видеоуплотнения. Предложен способ сжатия цифровых движущихся изображений или видеосигналов на основе преобразования сверхполного базиса с помощью модифицированного алгоритма поиска согласования. Алгоритм сегментации остаточной энергии (АСОЭ) используют для получения начальной оценки формы и положения высокоэнергетических областей в остаточном изображении. Алгоритм постепенного удаления (АПУ) используют для снижения числа оценок согласования в процессе поиска согласования. АСОЭ и АПУ увеличивают скорость кодирования для отыскания согласованного базиса из заранее определенного словаря сверхполного базиса. Три параметра согласованной комбинации формируют элемент изображения, что определяет указатель в словарь и положение выбранного базиса, равно как скалярное произведение между выбранной базисной комбинацией и остаточным сигналом. 3 н. и 7 з.п. ф-лы, 15 ил.
| УСТРОЙСТВО ДЛЯ СЖАТИЯ ПРЕДСТАВЛЯЮЩЕГО ИЗОБРАЖЕНИЕ ВИДЕОСИГНАЛА И УСТРОЙСТВО ДЛЯ ФИЛЬТРАЦИИ ШУМА В СИГНАЛЕ | 1996 |
|
RU2189700C2 |
| Способ закрепления слабосцементированных пород | 1980 |
|
SU933943A1 |
| US 5699121 A, 16.12.1997 | |||
| NEFF R and ZAKHOR A, Very Low Bit Rate Video Coding Based on Matching Pursuits, IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, IEEE SERVICE CENTER, US, Vol: 7, No 1, c.158-171. | |||
