Патент на изобретение №2212710

(54) СПОСОБ КОДИРОВАНИЯ КООРДИНАТ ПЕРЕМЕЩАЮЩЕГОСЯ НА ЭКРАНЕ МОНИТОРА КОМПЬЮТЕРА ВИДЕОИЗОБРАЖЕНИЯ

(57) Реферат:

Изобретение относится к вычислительной технике и может быть использовано в компьютерных системах активного видео. Технический результат заключается в увеличении производительности и скорости кодирования координат визуального объекта и уменьшении массивов сохраняемых данных. Способ включает разбиение видеокадра на XY ячеек. Присваивают ячейкам визуальных объектов соответствующие им номера и присваивают нули остальным ячейкам. Внутрикадровое кодирование для формирования массива данных карты осуществляют путем выделения рядов, состоящих из ячеек визуального объекта. В массив данных карты вводят модификаторы – указатели разрыва в рядах ячеек, пропуска ряда, повтора ряда. Производят межкадровое кодирование для предыдущего и следующего видеокадров. Получают массив данных А внутрикадрового кодирования и массив данных В разностной матрицы предыдущего и следующего видеокадров, закодированной внутрикадровым кодированием. Если изменяется положение ячеек визуального объекта и его геометрическая форма, то сравнивают размер в байтах массива данных А с массивом данных В по формуле W={[Р(А)-Р(В)]/Р(А)}100%. Если величина W>К, где К – величина заданного порога, то сохраняют массив В в качестве описания следующей карты. Если W<К, то сохраняют массив А в качестве описания следующей карты. Получают соответствующий набор карт с массивами данных закодированных координат. 2 з.п. ф-лы, 12 ил., 1 табл.

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

Известен способ и аппаратура для объединения гиперсвязей с видео, в котором в качестве операции кодирования координат перемещающегося на экране монитора компьютера видеоизображения выводят на экран монитора видеокадр с изображением по меньшей мере одного визуального объекта (ВО), аппроксимируют при помощи разметки визуальный объект простой геометрической фигурой, например кругом, овалом, прямоугольником, с помощью авторского инструментария наносят разметку на отдельные ключевые видеокадры, а области разметки (круг, овал, прямоугольник) линейно интерполируют на оставшиеся промежуточные кадры (Международная заявка РСТ WО 98/44435, G 06 F 17/30, опубл. 1998 г).

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

Известна “Параллельная компьютерная система Активного Видео”, реализующая, в частности, способ кодирования координат перемещающегося на экране монитора компьютера видеоизображения, который является наиболее близким к заявленному (Патент Российской Федерации на изобретение 2173883, G 06 Т 1/20, опубл. 2001 г.).

Способ включает выведение на экран монитора видеокадра с изображением по меньшей мере одного визуального объекта (ВО). Разбивают видеокадр на XY ячеек, где Х и Y – 1, 2, 3, …, имеющих форму элементарных квадратов или прямоугольников. Выделяют ячейки, местоположение которых совпадает и не совпадает на видеокадре с местоположением ВО, присваивая ячейкам, совпадающим с местоположением ячеек ВО, соответствующие им номера, и присваивая нули ячейкам, местоположение которых не совпадает с местоположением ячеек ВО. Производят внутрикадровое кодирование, формируя массив данных карты для ВО данного видеокадра. Если положение ВО в следующих видеокадрах видеофайла постоянно, то для таких видеокадров массив данных карты предыдущего видеокадра принадлежит ему. Если положение ВО в следующем видеокадре изменяется, то формируют новую карту с новым массивом данных для этого ВО. Формируют и запоминают файл, образованный последовательностью карт, в котором каждая карта соответствует по меньшей мере одному видеокадру видеофайла.

Ограничениями этого технического решения являются:
необходимость использования при внутрикадровом кодировании ячеек с нулем, не совпадающих с местоположениями активных объектов, что увеличивает массив данных при создании карт. При идентифицировании и выделении ячеек, местоположение которых совпадает с местоположением активного объекта, необходимо кодирование всех ячеек ВО в координатах X, Y для образования карты ВО, что также резко увеличивает массив данных;
отсутствие межкадрового кодирования, что приводит к избыточности сохраняемых данных.

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

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

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

Для решения поставленной задачи с достижением указанного технического результата в известном способе кодирования координат перемещающегося на экране монитора компьютера видеоизображения, включающем вывод на экран монитора видеокадра с изображением по меньшей мере одного визуального объекта, разделение видеокадра с визуальным объектом на XY ячеек, где Х и Y – 1, 2, 3, …, имеющих форму элементарных квадратов или прямоугольников, выделение ячеек, местоположение которых совпадает и не совпадает на видеокадре с местоположением визуальных объектов, присваивая ячейкам, совпадающим с местоположением ячеек визуальных объектов, соответствующие им номера, и присваивая нули ячейкам, местоположение которых не совпадает с местоположением ячеек визуальных объектов, внутрикадровое кодирование, при котором формируют массив данных карты для всех визуальных объектов данного видеокадра, причем если положение визуальных объектов в следующих видеокадрах видеофайла постоянно, то для таких видеокадров карта предыдущего видеокадра принадлежит им, а если положение визуальных объектов в следующем видеокадре изменяется, то формируют новую карту для этих визуальных объектов, формирование и запоминание файла, образованного последовательностью карт, в которой каждая карта соответствует по меньшей мере одному видеокадру видеофайла, согласно изобретению внутрикадровое кодирование производят путем выделения по одной из координат Х или Y крайнего ряда, состоящего из ячеек визуального объекта, определения координат крайних ячеек этого ряда, определения координат двух крайних ячеек в последующих рядах, при этом если крайний и последующий ряды содержат ячейки, местоположение которых не совпадает с местоположением визуального объекта в этих рядах, то в массив данных карты вводят модификатор разрыва ряда ячеек и запоминают координаты крайних ячеек визуального объекта в месте разрыва ряда, анализируют каждый последующий ряд на предмет отсутствия в ряду ячеек визуальных объектов, и если ряд свободен от ячеек визуальных объектов, то вводят модификатор пропуска ряда, анализируют каждый последующий ряд на предмет идентичности предыдущего и последующих, смежных с ним рядов, если они идентичны, то в массив данных карты вводят модификатор повтора ряда, после внутрикадрового кодирования запоминают карту видеокадра, при изменении геометрической формы и/или положения визуального объекта в следующем видеокадре производят его межкадровое кодирование, при котором, если положение ячеек визуального объекта в следующем видеокадре изменяется, а его геометрическая форма сохраняется, то в массив данных карты следующего видеокадра вводят параметры вектора смещения ячеек визуального объекта, если изменяется положение ячеек визуального объекта и его геометрическая форма, то производят упомянутое внутрикадровое кодирование этого видеокадра, получая массив данных А, далее вводят в массив данных параметры вектора смещения ячеек визуального объекта и вычисляют разность между двумя матрицами массивов данных для визуального объекта на предыдущем и следующем видеокадре, получая разностную матрицу, полученную разностную матрицу кодируют упомянутым внутрикадровым кодированием, получая массив данных В, сравнивают размер в байтах массива данных А с массивом данных В по формуле
W={[Р(А)-Р(В)]/Р(А)}100%,
где W – вычисляемая величина выигрыша, %,
Р(А) – размер массива А;
Р(В) – размер массива В,
и если величина W>К, где К – величина заданного порога, то сохраняют массив В в качестве массива данных следующей карты, и при определении местоположения визуального объекта этого видеокадра используют массив данных А предыдущей карты, а если W<К, то сохраняют массив данных А в качестве массива следующей карты.

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

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

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

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

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

Фиг. 3 – а) предыдущий и б) последующий кадры со смещением ВО при сохранении его геометрической формы.

Фиг. 4 – массив данных с ВО после идентификации ячеек для подачи на кодирование, где а) – К-й кадр с визуальным объектом; б) – (К+1)-й кадр, в котором ВО изменил геометрическую форму; в) – разностная матрица, полученная в результате вычитания массивов данных (К+1)-го и К-го кадра.

Фиг.5 – блок-схема алгоритма внутрикадрового кодирования для заявленного способа.

Фиг.6 – блок-схема алгоритма с учетом межкадрового кодирования.

Фиг.7 – блок-схема способа автоматизированной разметки ВО.

Фиг.8 – блок-схема декодирования карт ВО.

Фиг.9 – блок-схема декодирования ключевой карты.

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

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

При внутрикадровом кодировании производят кодирование областей ВО на данном видеокадре. Внутрикадровое кодирование позволяет сформировать массив данных карты ВО – соответствующую матрицу в системе координат X, Y для ячеек, местоположение которых совпадает на видеокадре с местоположением ВО. Карта – закодированная информация о разметке ВО.

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

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

Процесс внутрикадрового кодирования поясняется с помощью следующего примера.

Пусть процесс внутрикадрового кодирования проводится по горизонтальным рядам ячеек, в которых ячейки с одинаковыми Y координатами принадлежат одной группе и расположены вдоль горизонтальных линий. Группы ячеек (фиг.2) расположены на отрезках линий. При кодировании достаточно запомнить данные о левой и правой координате Х каждого горизонтального ряда. Для уменьшения количества данных карты, необходимых для сохранения и полного описания ВО, вводятся модификаторы трех типов: модификатор разрыва ряда ячеек – отрезка линии, модификатор пропуска ряда для ячеек – пропуска линии для ячеек, модификатор повтора ряда для ячеек – указатель повтора линий для ячеек.

Пусть первоначально запоминают координату Y верхней левой точки ВО, если кодирование производится по горизонтали. Затем определяют начальные и конечные координаты Х отрезков. Отрезки с рядами следуют один за другим, то есть координата Y следующего сохраненного отрезка равна координате Y предыдущего отрезка плюс 1, поэтому сохраняется только одна координата Y крайней точки ВО и начальные и конечные координаты Х отрезков с ячейками.

В случае разрывов линий, пропуска линий (фиг.2) вводятся модификаторы, необходимые для определения только Y координат отрезков. Отрезки линий одинаковые и идентичные для рядов ячеек, т.е. если они имеют равные Х координаты начальной и конечной точек ряда соответственно. Модификатор разрыва ряда ячеек указывает, что отрезки линий с группами ячеек до и после него расположены на одной линии и имеют разрыв, т.е. у них одинаковая Y координата и отсутствует группа ячеек в ряду. Запоминают координаты крайних ячеек в месте разрыва ряда. Модификатор пропуска ряда указывает, что один из горизонтальных рядов ячеек отсутствует, и запоминается Y координата следующего существующего В, т.е. не пустой линии. Модификатор повтора ряда указывает, что линия с ячейками – идентичная смежной, предыдущей (содержит столько же ячеек, как предыдущая, и координаты Х для крайних ячеек линии одинаковые) и повторяется некоторое количество раз. Если в матрице данных отсутствует модификаторы для горизонтального ряда ячеек, то отрезки линий рядов не имеют повторов, разрывов, пропусков. Такие ячейки принадлежат разным, но последовательно идущим сверху вниз линиям: Y_i+1=y_i+1, где i – номер горизонтального ряда ячеек (i=1….k).

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

Схема внутрикадрового кодирования карт в формируемый и запоминаемый файл: