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

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

Реферат

 

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

Схема внутрикадрового кодирования карт в формируемый и запоминаемый файл: <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. Таким образом, производится автоматическое выделение и идентификация ячеек ВО.

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