Способ кодирования координат перемещающегося на экране монитора компьютера видеоизображения

 

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

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

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

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

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

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

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

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

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

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

Для решения поставленной задачи с достижением указанного технического результата в известном способе кодирования координат перемещающегося на экране монитора компьютера видеоизображения, включающем вывод на экран монитора видеокадра с изображением по меньшей мере одного визуального объекта, разделение видеокадра с визуальным объектом на X•Y ячеек, где Х и 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 жирными линиями показан ВО, матрица которого кодируется последовательностью, приведенной в таблице.

Схема внутрикадрового кодирования карт в формируемый и запоминаемый файл:
<object map i>: : = <begin point> <count stretches> <stretches> <begin point>
Начальная точка области разметки объекта, Y координата верхней левой точки отрезка линии верхнего горизонтального ряда ячеек.

<count stretches>
Список элементов разметки. Состоит из координат отрезков линий и модификаторов.

<stretch i>::= <start X> <end X> <start X>
X координата начальной точки отрезка линии.

<end X>
Х координата конечной точки отрезка линии.

<modifier>::=(<line continue>|<pass lines>|<repeat stretch>)
<Iine continue>:=<line continue mod> <stretch i>
Модификатор разрыва линии описывает разрыв текущей линии разметки или, другими словами, продолжительность разметки в текущей линии. Если текущая линия состоит из более чем одного отрезка, модификатор указывает, что следующий отрезок принадлежит той же линии.

<line continue mod>
Модификатор разрыва линии, байт идентификатор модификатора.

<stretch i>
Следующий отрезок в той же линии.

<pass lines>::= <pass lines mod><Y new>
Модификатор пропуска линии описывает линии, которые не содержат разметку объекта. Определяет Y координату следующей линии, в которой встречается разметка.

<pass lines>
Модификатор пропуска линии, байт идентификатор модификатора.

<Y new>
Y координата линии, где разметка появляется.

<repeat stretch>:= <stretches on line> <repeat stretch mod> <count line>
Модификатор повтора линии используется для кодирования повторяющихся отрезков линий или повторяющихся последовательностей отрезков линий.

<stretches on line>
Список отрезков, представляющих повторяющиеся последовательности.

<repeat stretch mod>
Модификатор Повтора, байт идентификатор модификатора.

<count line>
Количество повторяющихся линий.

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

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

Если матрицы не совпадают, то проводят анализ массива данных для каждого ВО (если их несколько).

Возможны следующие варианты:
1. Координаты ВО совпадают.

2. Форма ВО совпадает, но ВО смещен в двухмерном пространстве (фиг.3).

Форма ВО изменена по отношению к форме ВО предыдущего видеокадра, но сам объект не смещен (фиг.4).

4. Форма ВО изменена по отношению к форме ВО предыдущего кадра и объект смещен (совместное действие по фиг.3, 4).

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

Если форма визуальных объектов совпадает, но визуальные объекты смещены в двухмерном пространстве, то производят учет этого смещения при помощи <вектора смещения> (фиг.3). В массив данных карты ВО вводят только координаты вектора смещения - два числа, смещение по оси Х и смещение по оси Y. Карта с данными о смещении - относительная, а карта с первоначальным положением ВО - ключевая. Так, на фиг.3 вектор смещения ВО (К+1)-го кадра относительно К-го кадра характеризуется смещением ВО на 5 ячеек по Х и на 1 ячейку по Y. Поэтому в массив данных карты (К+1)-го кадра вводят только два числа (5, 1), характеризующие координаты вектора смещения. Карта К-го кадра - ключевая, а карта (К+1)-го кадра - относительная, и ее полный массив данных может быть получен при последующем декодировании только с использованием ключевой карты.

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

Величина заданного порога К может быть выбрана в интервале 30-99%. Величина К определяется разработчиком запоминаемого файла. Порог 30% дает большое количество относительных карт ВО, а при 99% практически все карты являются ключевыми. Это сказывается на объеме запоминаемой информации. При использовании на практике только ключевых карт объем сохраняемых данных больше, но и быстрее скорость доступа и соответственно быстрее производится декодирование. При использовании большого количества в файле относительных карт уменьшается быстродействие, но сокращается объем требуемой памяти - доля хранения данных. Поэтому целесообразно величину конкретного порога устанавливать в зависимости от технических характеристик используемого цифрового оборудования. Экспериментально установлено, что для большинства приложений заявленного способа кодирования можно задавать величину порога 40-50%.

Если ВО смещен, а также изменена форма ВО по отношению к его форме на предыдущем видеокадре (т. е. произошла совместная ситуация изменения карты ВО, как это было показано по отдельности на фиг.3 и 4), то сначала производят внутрикадровое кодирование следующего видеокадра, получая массив данных А. Затем определяют вектор смещения (как это было ранее описано для фиг.3). В этом случае за направление и величину вектора смещения принимается вектор, который при смещении на величину этого вектора ВО с предыдущего кадра дает максимальное совпадение ячеек с этим ВО последующего кадра. То есть определяют все совпадающие ячейки предыдущего и следующего кадра и находят для этих ячеек параметры Х и Y вектора смещения, как это было описано ранее. Далее определяют разность между данными координат ячеек матрицы ВО предыдущего кадра и данными координат ячеек матрицы ВО последующего кадра с измененной формой объекта (как это было ранее описано для фиг.4). То есть выявляются те ячейки, который не совпадают на предыдущем и следующем видеокадре. Далее кодируют полученную разностную матрицу методом внутрикадрового кодирования, описанным выше. В результате получают результирующий массив данных В. Если W>К, где К - величина заданного порога, то сохраняется закодированный разностный массив В и параметры вектора смещения, т.е. получают относительную карту. Если W<К, то сохраняют массив А, т.е. ключевую карту, как было описано выше. Величина заданного порога К может быть выбрана в интервале 30-99%.

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

При кодировании последующего видеокадра проверяется предыдущая карта визуального объекта. Определяется, является ли она относительной или ключевой. Если предыдущая карта является относительной, т.е. для нее W>К, то карта визуального объекта на последующем кадре также может быть только относительной по отношению к ранее полученной ключевой карте. То есть ее данные считываются при помощи ключевой карты, минуя массив данных предыдущих относительных карт. Но в случае, если для нее W<К, то она будет сама ключевой для последующих карт визуального объекта. Таким образом, получают последовательность - "цепь" карт ВО, где могут быть несколько относительных карт ВО, следующих за ключевой.

Например, последовательность может выглядеть следующим образом: К R R R R К R R, где К - Ключевая Карта АО, а R - Относительная Карта АО. Процесс формирования карт осуществляется для всех кадров видео, имеющих разметку. Как будет показано далее, такое описание в матричной форме карт требует минимальных затрат памяти и вычислительных ресурсов на их декодирование.

В заявленном техническом решении процесс кодирования включает в себя описанные внутрикадровое и межкадровое и кодирование (фиг.5, 6).

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

Если массив данных координат ВО - первый (блок сравнения 2, фиг.6), то кодируем его в блоке 3 внутрикадровым кодированием. Содержание функциональных элементов блока 3 (фиг.6) изображено на фиг.5. На первом этапе определяют левую верхнюю ординату Y0 для ВО - блок 4 (фиг.5). После ее определения ордината записывается в начальное значение счетчика по рядам - блок 5. Далее в блоке 6 определяют абсциссы начала и конца первого отрезка горизонтальной линии для ячеек и сохраняют их в результирующем массиве в блоке 8. Далее в блоке сравнения 9 проверяется, есть ли следующий отрезок по линии с такой же ординатой: если есть, то применяем модификатор разрыва ряда ячеек по этой горизонтальной линии в блоке 10 и определяем координаты начала и конца следующего отрезка линии с ячейками по горизонтали в блоке 6. Операция разбора горизонтального ряда ячеек вдоль горизонтальной линии происходит до тех пор, пока будет найден последний отрезок исследуемой горизонтальной линии, это условие проверяется в блоке сравнения 7. Если такого отрезка нет, то в блоке 11 выполняется переход на следующий смежный ряд ячеек - на следующую горизонтальную линию (инкремент равен 1). В случае отсутствия на следующей горизонтальной линии ячеек - отрезков ВО эта проверка осуществляется в блоке сравнения 12, указывается модификатор пропуска ряда в блоке 13. В случае обнаружения линии с рядом ячеек в блоке сравнения 14, состоящей из отрезка или отрезков с абсциссами и модификаторами, соответствующими предыдущей линии, в блоке 15 указывается модификатор повтора ряда. Процесс продолжается, начиная с блока 6, до тех пор, пока не будут описаны все отрезки с рядами ячеек, принадлежащие ВО, это условие проверяется в блоке 16. Процесс, начиная с блока 6, повторяется для каждого ВО матрицы данного кадра, это условие проверяется в блоке 17. Результирующий массив запоминается в блоке 18 (фиг. 5). Результирующий массив из блока 3 (фиг.6) запоминается в буфере 19. Если визуальных объектов больше нет, то на вход кодировщика блок 1 (фиг.6) поступает матрица следующего кадра. Эту матрицу сравниваем с матрицей предыдущего кадра в блоке 20 (фиг.6). Если матрицы идентичные, то в блоке 21 относим карту предыдущего кадра к текущему. Если матрицы разные, то в блоке 22 из матрицы выбираются координаты одного ВО и производятся два вычисления. По первому вычислению в блоке 23 координаты первого ВО кодируются методом внутрикадрового кодирования. По второму вычислению в блоке 24 определяется вектор смещения, для этого вычисления матрица координат ВО предыдущего кадра извлекается из блока 25. В блоке 26 определяется разница между матрицами ВО. Блок 27 кодирует полученный после вычислений в блоке 26 разностный массив В внутрикадровым кодированием (фиг.5). В блоке 28 (фиг.6) сравнивается выигрыш W с заданным порогом К.

W={[Р(А)-Р(В)]/Р(А)}•100%,
где W - вычисляемая величина выигрыша, %;
Р(А) - размер массива А;
Р(В) - размер массива В.

После сравнения записывается вычисленный массив А или В в блоке 13. Если величина W>К, где К - величина заданного порога, то сохраняют в блоке 29 массив В и параметры вектора смещения в качестве описания следующей карты, а если W<К, то в блоке 29 сохраняют массив А в качестве другого описания следующей карты визуального объекта. Процесс повторяется для каждого визуального объекта, присутствующего в текущем кадре, что проверяется блоком сравнения 30. Результирующий массив запоминается в блоке 19.

Разметка ячеек ВО может быть произведена ручными способами и автоматически. К ручным способам относится нанесение разметки с помощью известных инструментов:
"Карандаш" - идентификация отдельных ячеек путем выделения ячеек на отображаемом на экране видеокадре с помощью манипулятора (мышь);
"Прямоугольник" - идентификация ячеек в прямоугольной области на кадре, путем растягивания изображения прямоугольника;
"Стирание" - отмена идентификации ячеек объекта;
"Заливка" - идентификация всех ячеек внутри области, ограниченной ранее идентифицированными ячейками;
"Волшебная палочка" - идентификация ячеек, прилежащих к заданной и сходных с ней по цвету (аналогично инструменту "Волшебная палочка" в графических редакторах типа Adobe Photoshop).

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

Автоматизированные способы разметки могут быть выполнены различными способами при их разработке. Один из вариантов автоматизированного способа выполнения разметки описан далее.

В блоке 60 (фиг.7) определяются координаты точек на контуре ВО. Координаты определяются автором, например, автор отмечает с помощью манипулятора точки на видеоизображении ВО. Эти координаты запоминаются в массиве данных. Далее определяется в блоке 61 яркостная составляющая видеоизображения данного кадра по формуле:
Y = α•R+β•G+γ•B,
где α = 0,299, β = 0,587, γ = 0,114, R, G, B - цветовые составляющие видеоизображения в цветовом пространстве RGB, принятом для отображения изображений на компьютерах. В результате получается массив С. Затем определяются в блоке 62 ячейки внутри определенного в блоке 60 контура ВО. Сначала определяются точки внутри контура ВО с использованием одного из известных методов "заливки" фигуры по заданному контуру, например, с использованием стандартной функции API Windows FillRgn. Затем определяются ячейки внутри контура ВО путем аппроксимации ранее найденных точек по сетке. Далее в блоке 63 выполняется запоминание полученных в блоке 62 координат о разметке ВО на данном кадре. Затем в блоке 64 выполняется переход на следующий видеокадр. В блоке 65 далее определяется яркостная составляющая видеоизображения данного кадра по формуле, описанной выше. В результате получается массив D. В блоке 66 выполняется поиск точек, определенных на контуре ВО в видеокадре С, а в блоке 60 - на видеокадре D. Используется метод "Pyramidal Implementation of the Lucas Kanade Feature Tracker", описанный в статье "Pyramidal Implementation of the Lukas Kanade Feature Tracker. Description of the algorithm" Jean-Yves Bouguet. Intel Corporation Microprocessor Research Labs (http: //www. intel.com). В качестве данных используются массивы С, D и массив координат точек на контуре ВО. Далее в блоке сравнения 67 проверяется, найдены ли точки на видеокадре D. Если точки найдены, то в блоке 62 определяются ячейки внутри контура ВО на видеокадре D, заданном этими точками. Далее сохраняется информация о разметке ВО на видеокадре D в блоке 63. В блоке 68 проверяется нужно ли продолжать процесс - автор не прервал процесс? Если процесс нужно продолжать, в блоке 69 массиву С присваивается значение массива D, в качестве массива координат точек принимается массив координат точек, определенных для видеокадра D, и затем процесс повторяется, начиная с блока 64. Процесс продолжается, пока находятся точки контура в блоке 66, условие проверяется в блоке 67, и пока он не прерывается автором, условие проверяется в блоке 68. Таким образом, производится автоматическое выделение и идентификация ячеек ВО.

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

Description::=[...<map i>...]
<map i>: :=<frame number> <count frame> <count map> <count markers> [.. <marker i>..] [... <object map i>...]
<frame number> - номер видеокадра, с которого применяется данная карта
<count frame> - число кадров, к которым применяется данная карта
<count map> - число визуальных объектов, разметка которых описывается данной картой
<count markers> - число маркеров
[...<marker i>...] - список маркеров
<marker i>::=<marker X pos><marker Y pos>
<marker X pos> - X координата в координатах сетки
<marker Y pos> - Y координата в координатах сетки
[...<object map i>...] - список разметок визуальных объектов
<object map i> - разметка одного визуального объекта
<object map i>: := <type + object ID>[<key map number> <motion vector> <type differ-ence>] [<begin point> <circumscribing frame> <count stretches> <stretches>]
<type + object ID> - биты 2-15 - уникальный идентификатор объекта, бит 1 - определяет карта объекта относительная или ключевая (0 - ключевая, 1 - относительная)
[<key map number>] - номер ключевой карты, поле присутствует, если карта относительная.

[<motion vector>] - координаты вектора смещения. Поле присутствует, если карта относительная.

[<type difference>] - определяет тип type относительной карты.

0 - объект смещен, форма не изменилась, разность не записывается.

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

Следующие поля присутствуют, если бит 1 of<type+object ID> равен to 0 или <type difference> не ноль.

[<begin point>] - начальная точка разметки объекта, Y - координата левой верхней точки разметки объекта, если кодирование выполняется по горизонтали, Х - координата нижней правой точки, если кодирование выполняется по вертикали.

[<count stretches>] - количество элементов разметки.

[<stretches>]::=[...(<stretch i>|<modifier>)...] - список элементов разметки
<stretch i>::= <start X/Y> <end X/Y>
<start X/Y> - X/Y координата начальной точки отрезка
<end X/Y>-X/Y координата конечной точки отрезка
Х - горизонтальное кодирование
Y-вертикальное кодирование
<modifier>: : =(<line continue>|<pass lines>|<repeat stretch>) - модификатор
<line continue>::=<lme continue mod> <stretch i> - Описывает разрыв текущей линии разметки или, другими словами, на продолжительность разметки в текущей линии. Если текущая линия состоит из более чем одного отрезка, модификатор обозначает, что следующий отрезок принадлежит той же линии.

<line continue mod> - Модификатор Разрыва Линии, идентификатор модификатора. <stretch i> - следующий отрезок в этой линии
<pass lines>: := <pass lines mod> <Y/X new> Модификатор пропуска линий. Описывает линии, которые не содержат разметку объекта. Определяет Y(горизонтальное кодирование)/X (вертикальное кодирование) координату следующей строки, в которой встречается разметка.

<pass lines mod> - Модификатор Пропуска Линии, идентификатор модификатора.

<Y/X new> - Y (горизонтальное кодирование)/Х(вертикальное кодирование) координата линии, где разметка появляется
<repeat stretch>::= <repeat stretch mod> <count line> <stretches on line> - Модификатор Повтора, используется для кодирования повторяющихся отрезков или повторяющихся последовательностей отрезков
<stretches on line> - [<stretches>] - список отрезков, представляющих повторяющиеся последовательности
<repeat stretch mod> Модификатор Повтора, идентификатор модификатора <count line> - количество повторений линии.

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

<addr of index>.Maps index::=[... <index i>...]
<index i>::== <map number><count frame> <addr of map>
<map number> - номер карты
<count frame> - число видеокадров, к которым применяется данная карта
<addr of map> - смещение от начала файла сценария до этой карты.

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

Декодирование карт из запомненного файла осуществляется следующим образом (фиг.8, 9).

На вход декодировщика (фиг.8) блок 100 поступает массив закодированных координат визуальных объектов - карт. Далее в блоке сравнения 101 проверяется: эта карта ключевая или нет. Карта - ключевая, если все входящие в нее карты для ВО ключевые. Если она ключевая, то в блоке 102 все входящие в данную карту карты ВО декодируются следующим способом. Выбирается карта одного ВО в блоке 120 (фиг.9). Далее в блоке 121 результирующая матрица заполняется нулями. Затем блок 122 осуществляет выбор ординаты YO начальной ячейки ВО, которая определялась на этапе кодирования блок 4 (фиг.5). Далее в блоке 123 (фиг.9) ординате текущей декодируемой линии для ячеек присваивается значение Y0. Затем в блоке 124 извлекается из карты ВО первый отрезок линии разметки ВО, и соответствующие данному отрезку ячейки в матрице (предварительно заполненной нулями в блоке 121) заполняются номером данного ВО. Далее в блоке сравнения 125 проверяется следующая запись в карте - это модификатор разрыва? Если да, то извлекается следующий отрезок с ячейками в блоке 124. Если это не модификатор разрыва, то в блоке сравнения 126 проверяется данная запись - модификатор пропуска? Если это модификатор пропуска, то в блоке 127 присваивается ординате текущей декодируемой линии с рядом ячеек значение, определенное параметром модификатора пропуска. Если это не модификатор пропуска, то в блоке сравнения 128 проверяется текущая запись в карте ВО - модификатор повтора? Если это модификатор повтора линии с ячейками, то в блоке 129 производится копирование координат текущего ряда (строки), вводится копирование координат текущего ряда (строки) результирующей матрицы на следующие смежные ряды, количество которых указано в параметре модификатора. Далее в блоке 130 производится присваивание ординате текущей декодируемой строке ряда ячеек значения ординаты предыдущей декодируемой строки плюс значение параметра модификатора. Если текущая запись в карте ВО - не модификатор повтора, то в блоке 131 увеличивается значение ординаты предыдущего декодируемого ряда ячеек (строки) на единицу. Процесс продолжается, пока будет обнаружен хотя бы один отрезок линии ряда ячеек с текущей ординатой Y. Это условие проверяется в блоке 132. В результате получается матрица (например, как показано на фиг.1), в ячейках которой соответственно координатам ВО хранятся значения номеров ВО, а во всех остальных ячейках - нули. Результат выполнения декодирования блока 102 (фиг.9) запоминается в блоке 104 и в буфере ключевых карт ВО - блоке 103. Блок 103 служит для ускорения процесса декодирования относительных карт ВО. Если результат сравнения блока 101 будет "НЕТ", то значит, что эта карта относительная. Тогда в блоке 105 производится выбор карты одного ВО из буфера ключевых карт блока 103, а если ключевая карта отсутствует в блоке 103, то она выбирается из блока 100 и декодируется блоком 106 (фиг.8), как ранее показано в блоках 120-132 (фиг.9).

Далее в блоке 107 (фиг.8) смещается разметка ВО, определенная на ключевой карте, на параметры вектора смещения, описанные в относительной карте ВО. Затем в блоке 108 декодируется разность между разметкой ВО на ключевой карте и относительной методом, описанным выше в блоках 120-132 (фиг.9). Далее в блоке 109 (фиг.8) прибавляется разность, определенная в блоке 108, к смещенной в блоке 107 на параметры вектора смещения разметки ВО. Процесс продолжается для всех ВО, описанных в этой карте, начиная с блока 105. Это условие проверяется в блоке 110.

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

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

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

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10

NF4A Восстановление действия патента

Дата, с которой действие патента восстановлено: 10.01.2011

Дата публикации: 10.01.2011