Оценка движения путем трехмерного рекурсивного поиска (3drs) в реальном времени для преобразования частоты кадров (frc)

Оценка движения путем трехмерного рекурсивного поиска (3drs) в реальном времени для преобразования частоты кадров (frc)

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящее изобретение относится к обработке видео, и, более конкретно, к оценке движения для целей преобразования частоты кадров видео.

Уровень техники

Оценка движения является важной частью многих алгоритмов, применяемых при кодировании видео, преобразовании частоты кадров (frame rate conversion, FRC) видео и создании структуры из движущегося изображения (structure from motion, SfM). При этом алгоритмы оценки движения сильно зависят от поставленных задач, поэтому не существует единого, универсального алгоритма, который был бы одинаково приемлемым для любых применений. Например, при реализации оценки движения для FRC для воспроизведения видео в мобильных устройствах существуют некоторые особенности и сложности:

- ограничения по производительности (работа в реальном времени),

- ограничения по энергопотреблению (чтобы избежать значительного уменьшения продолжительности работы батареи),

- зашумленное видео,

- сложное движение,

- артефакты движения,

- «дергающееся» (скачкообразное, не плавное) движение.

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

- устойчивость к шуму,

- высокое быстродействие,

- приближенность к реальному движению,

- многопотоковость,

- мобильность,

- работа в реальном времени,

- низкое энергопотребление.

В свете вышеперечисленных сложностей и требований, хорошие результаты для FRC демонстрирует подход трехмерного рекурсивного поиска (3D recursive search, 3DRS), описанный в патенте US 8,009,174 B2 (30.08.2011, Koninklijke Philips Electronics NV), согласно которому оценка движения 3DRS делается с использованием порядка сканирования (104), называемого «меандровым» в силу сходства траектории сканирования блоков кадра с меандром (Фиг. 1). Результаты поиска помещаются в память кольцевого буфера с блоком управления, адаптированным к меандровому порядку сканирования при приеме вектора движения и растровому порядку сканирования (106) при выдаче вектора движения для блока компенсации движения (MC). Кольцевой буфер поддерживает необходимый объем памяти. Однако, данное решение не обеспечивает повышение производительности в широко используемых в настоящее время многоядерных системах.

В несколько более позднем решении, которое описано в патенте US 8,265,160 B2 (11.09.2012, NXP BV), меандровый порядок сканирования 3DRS-поиска разделен на отдельные части для отдельных потоков обработки, таким образом, что вместе эти части образуют меандр (Фиг. 2). Оценка движения (ME) выполняется для каждой из отдельных частей одновременно. Несколько параллельных потоков повышают производительность вычислений при оценке движения в многоядерных системах. Тем не менее, в данном подходе также существует ряд недостатков. Во-первых, тот факт, что направление сканирования блоков в соседних частях является противоположным, влечет за собой нелокальность доступа к памяти, что приводит к снижению производительности. Во-вторых, движение нечетных и четных линий блоков распространяется с разных направлений, что может вызвать «чересстрочный» эффект на границах объектов. В-третьих, лишь в одном потоке (поток ME1 и блок A на Фиг. 2) основой для оценки движения являются блоки, смежные с текущим блоком, тогда как в остальных потоках (потоки ME2-ME4 и блоки B, C, D на Фиг. 2) вместо некоторых смежных блоков для оценки используются блоки, отстоящие от текущего блока на некоторое расстояние, что неизменно приводит к появлению ошибок. В-четвертых, оценка движения в некоторых потоках (потоки ME2-ME4 на Фиг. 2) происходит на основе оценки, уже сделанной в других потоках, откуда следует необходимость строгой синхронизации потоков между собой и невозможность сделать их обработку полностью независимой, из-за чего производительность также снижается.

Существует также решение, описанное в патенте US 6,996,177 B1 (07.02.2006, Koninklijke Philips Electronics NV), которое несколько иначе подходит к решению поставленных задач и в котором 3DRS оценка движения выполняется с использованием поблочной оценки движения (BME) и оценки глобального движения (GME) (Фиг. 3). GME использует статистику векторов движения из BME и выдает вектора-кандидаты глобального движения для BME. Однако в этом решении для оценки глобального движения используется слишком простая статистика (берутся первый и второй наиболее часто используемые векторы движения, полученные с помощью BME), которой недостаточно, чтобы получать качественный результат. Кроме того, в этом решении результат GME применяется ко всему кадру, тогда как часто бывают случаи, когда один или два вектора глобального движения не подходят для разных частей кадра, вследствие чего возникают артефакты во время преобразования частоты кадров, так как полученные поля движения не соответствуют реальным полям движения.

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

Сущность изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Повышение эффективности достигается за счет трех ключевых факторов:

1) выполнение обработки двойными блоками, то есть сразу по два блока, что позволяет уменьшить вычислительную сложность 3DRS и улучшить шаблон доступа к памяти,

2) выполнение обработки по укрупненному волновому фронту, что позволяет обеспечить сравнительно высокую степень параллелизации (вплоть до десятков потоков), и улучшает шаблон доступа к памяти,

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

Краткое описание чертежей

Фиг. 1-3 - известные из уровня техники решения в области 3DRS оценки движения.

Фиг. 4 - Соседние блоки, содержащие векторы-кандидаты, используемые для формирования набора векторов-кандидатов, для каждого из двух соседних блоков в отдельности (базовый 3DRS)

Фиг. 5 - схема использования ранее оцененных полей движения при оценке очередных полей движения.

Фиг. 6 - блоки, содержащие векторы-кандидаты, рассматриваемые для двойного блока (расширенный 3DRS)

Фиг. 7 - блок-схема варианта осуществления 3DRS-поиска согласно настоящему изобретению.

Фиг. 8 - традиционный 3DRS с полнокадровым меандровым порядком сканирования.

Фиг. 9-3DRS с порядком сканирования, известным как обработка по волновому фронту (или гиперплоскостями).

Фиг. 10-3DRS с порядком сканирования согласно настоящему изобретению.

Фиг. 11 - Пример порядка сканирования с укрупненной единицей из трех двойных блоков.

Фиг. 12 - обратный порядок сканирования кадра.

Фиг. 13 - еще один вариант порядка сканирования кадра.

Фиг. 14-3DRS с использованием дополнительных векторов-кандидатов полуглобального движения.

Фиг. 15A-15C - пример применения полуглобального движения.

Подробное описание

В основе настоящего изобретения лежит алгоритм 3D-рекурсивного поиска (3DRS). Алгоритм ищет блочное поле движения, используя последовательные итерации по паре кадров видеопоследовательности.

Следует понимать, что полем движения называется набор векторов движения, где каждый из векторов движения поставлен в соответствие либо каждому пикселю (dense motion field - плотное поле движения), либо блоку пикселей (обычно квадрат или прямоугольник рядом лежащих пикселей) текущего кадра. В настоящем изобретении используются векторы движения, принадлежащие блокам, и соответственно, используются блочные поля движения.

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

При оценке движения для каждого блока проверяется несколько векторов-кандидатов, то есть возможных векторов, которые могут послужить основой для результирующей оценки. Тот вектор-кандидат, который имеет наилучшую оценку, становится вектором движения для текущего блока. Самый простой набор кандидатов - это все возможные смещения, имеющиеся в кадре, однако такой набор имеет слишком большой размер (если точность вектора движения составляет один пиксель, то полный набор кандидатов будет равен количеству пикселей в кадре). В подходе «3DRS 1993», описанном в статье deHaan G., Biezen P, Huijgen H., Ojo O.A. True-Motion Estimation with 3-D Recursive Search Block Matching. IEEE Transactions on Curcuits and Systems for Video Technology Vol. 3, No. 5 (1993), был предложен такой принцип формирования набора кандидатов, при котором мощность набора обычно не превышает десятка векторов-кандидатов.

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

Традиционный (базовый) подход 3DRS более наглядно изображен на Фиг. 4. Как видно из примера на Фиг. 4, набор векторов-кандидатов формируется для каждого блока отдельно. Например, для блока A (10) пространственные векторы-кандидаты выбираются из блоков 1, 3, 5, 7, 9 в текущем поле движения, а временные векторы-кандидаты выбираются из блоков A (10), B (11), 13, 15 в ранее целиком вычисленном поле движения, то есть в сумме 9 векторов-кандидатов. В свою очередь, для блока B (11) пространственные векторы-кандидаты выбираются из блоков 2, 4, 6, 8, A (10) в текущем поле движения, а временные векторы-кандидаты выбираются из блоков B (11), 12, 14, 16 в ранее целиком вычисленном поле движения, то есть в сумме тоже 9 векторов-кандидатов.

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

1. Форма (шаблон) расположения блоков должен быть таким, чтобы уже оцененное движение поступало в текущий блок с разных направлений, что (при определенных условиях) обеспечивает наиболее быструю сходимость оценки вектора движения к реальному движению. Это основной принцип 3DRS. На данный момент специалистам в данной области известно множество разных шаблонов, удовлетворяющих этому принципу. Для целей настоящего изобретения может быть выбран любой подходящий шаблон.

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

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

Согласно настоящему изобретению, для каждой пары кадров оценивается поле движения вперед (FW) и поле движения назад (BW). Полем движения вперед (FW<N>) является набор векторов движения для текущего кадра N, которые указывают в последующий кадр N+1. Полем движения назад (BW<N-1>) является набор векторов движения для текущего кадра N, которые указывают в предыдущий кадр N-1. При оценке поля движения вперед FW<N> выборка временных кандидатов производится из инвертированного (то есть взятого с обратным знаком) поля движения назад BW<N-1>, оцененного для предыдущей пары кадров (N-1, N). При оценке поля движения назад BW<N> выборка временных кандидатов производится из инвертированного проецированного поля движения вперед FW<N>, оцененного для текущей пары кадров (N, N+1).

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

Для оценки векторов поля движения назад BW<N> в настоящем изобретении используются полуглобальные векторы-кандидаты, оцененные с помощью поля движения вперед FW<N>. Подробнее об этом будет упомянуто в третьем аспекте изобретения.

Первый аспект изобретения

В отличие от традиционного подхода, обрабатываемой единицей в способе согласно настоящему изобретению является двойной блок. Двойной блок представляет собой пару соседних блоков, которые обрабатываются вместе. Только один набор векторов-кандидатов используется для двойного блока, а каждый вектор-кандидат оценивается в одной итерации цикла обхода векторов-кандидатов для обоих блоков пары одновременно, что позволяет уменьшить вычислительные издержки. В частности, в примере на Фиг. 6 блок A и блок B рассматриваются одновременно в рамках двойного блока AB. Для двойного блока AB пространственные векторы-кандидаты выбираются из блоков 1, 3, 5, 7, 9, а временные вектора-кандидаты выбираются из блоков А(10), B (11), 13, 15, то есть в сумме 9 блоков-кандидатов. В сущности, это те самые 9 блоков-кандидатов, которые рассматривались бы в традиционном подходе для одиночного блока A. Таким образом, количество источников пространственных и временных кандидатов в показанном примере в два раза меньше, чем в случае с одиночными блоками, обработка которых показана на Фиг. 4. Как будет пояснено далее, рассмотрение дополнительных кандидатов для второго блока из пары (кандидатов блока B) происходит только в том случае, если значения функций доверия ФД(MVcand, блок) для пары блоков двойного блока соответствуют определенным условиям (при подозрении на границу движения).

Следует также отметить, что в части определения блоков, из которых будут выбираться пространственные векторы-кандидаты, в настоящем изобретении должно выполняться условие невыхода самого правого блока на и за границу фронта волны (так как на фронте волны и за фронтом волны векторы в текущем поле движения еще не оценены).

На Фиг. 7 изображена блок-схема варианта осуществления способа оценки движения на основе 3DRS-поиска согласно настоящему изобретению.

На этапе 100 происходит формирование набора векторов-кандидатов с помощью задания набора правил получения, с тем чтобы в дальнейшем было возможным получение очередного вектора-кандидата для текущей (рассматриваемой) единицы кадра. За исключением некоторых случаев, которые будут пояснены ниже, такой единицей является двойной блок. Например, как было показано на Фиг. 6, для рассматриваемого двойного блока AB сначала выбирают вектор-кандидат из блока 1. Упомянутые правила получения одинаковы для всех единиц кадра и могут быть различны для поля движения назад и поля движения вперед.

Существует много различных вариантов формирования набора правил получения. Примером простого правила получения может быть следующее: взять в качестве вектора-кандидата ранее оцененный вектор из соседнего блока кадра. При этом для точной идентификации соседнего блока необходимо указать сдвиг в блочных координатах относительно текущего блока. Примером более сложного правила может быть следующее: взять в качестве вектора-кандидата случайные смещения в диапазоне [-3..3] по координате x и в диапазоне [-2..2] по координате y.

Более подробно, набор правил может содержать одно или более из следующих правил (подразумевается порядок сканирования слева направо, сверху вниз):

1) Взять оцененный вектор движения из блока предыдущего поля движения, координаты которого равны координатам текущей единицы.

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

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

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

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

6) Взять случайное смещение в диапазоне XY: [-3..3][-2..2]

7) Взять лучший вектор-кандидат из ранее оцененных и прибавить к нему случайное смещение в диапазоне XY: [-3..3][-2..2].

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

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

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

На этапе 101 выполняется формирование очередного вектора-кандидата для текущей единицы кадра из сформированного на этапе 100 набора векторов-кандидатов на основе заданного списка правил получения.

Далее на этапе 102 происходит вычисление ФД(MVcand, блок) для каждого из блоков рассматриваемой единицы (ФД(MVcand,A), ФД(MVcand,B)), если рассматриваемой единицей является двойной блок, или для данного одиночного блока, если рассматриваемой единицей является одиночный блок.

Функция доверия ФД(MVcand, блок)=MAD(MVcand,блок)+f(Prior,MVcand), где

MAD - это средняя абсолютная разность:

f(Prior,MVcand) -штрафная функция, которая использует ранее вычисленную информацию (Prior) и используется для дополнительной регуляризации поля движения. В качестве такой ранее вычисленной информации может служить информация о глобальном или полуглобальном движении.

MVcand - рассматриваемый вектор-кандидат.

(блок) -координаты или позиция блока (текущего блока) в текущем кадре.

Чем больше значение ФД(), тем меньше доверия к данному вектору-кандидату. Меньшее значение ФД() обозначает большее доверие вектору-кандидату в данном блоке.

На этапе 103 вектор-кандидат для каждого блока из двойного блока сохраняется в памяти как лучший, если ФД(MVcand,блок) приняла меньшее значение по сравнению с ранее рассмотренными векторами-кандидатами для текущего блока. При этом, если для рассматриваемой единицы в памяти еще не сохранен наилучший вектор-кандидат, то текущий вектор-кандидат записывается как наилучший. При обработке последующих векторов-кандидатов, когда в памяти уже имеется сохраненный наилучший вектор-кандидат, выполняется сравнение ФД(MVcand,блок) текущего вектора-кандидата и ФД(MVcand,блок) сохраненного наилучшего вектора-кандидата, и в качестве наилучшего вектора-кандидата сохраняется тот вектор-кандидат, у которого значение ФД(MVcand,блок) является меньшим. Например, если в памяти в качестве наилучшего уже сохранен вектор-кандидат 1, а у текущего вектора-кандидата 3 значение ФД(MVcand,блок) является меньшим - тогда наилучший вектор-кандидат в памяти перезаписывается.

На этапе 104 проверяется, был ли полученный вектор-кандидат последним для текущей единицы (то есть последним в заданном наборе векторов-кандидатов). Если нет, то способ возвращается к этапу 101, и на рассмотрение берется следующий вектор-кандидат. Если да, то способ переходит к следующему этапу, 105. В конечном счете, после проверки всех векторов-кандидатов для текущей единицы в памяти остается сохраненным вектор-кандидат с минимальным значением ФД(MVcand,блок).

На этапе 105 выполняется анализ пары значений ФД(MVcand,блок) для каждого из блоков текущего двойного блока. При этом, вычисляется разность d(ВA) между ФД(MVcand best B,B) для второго одиночного блока из текущей единицы и ФД(MVcand best A,A) для первого одиночного блока из текущей единицы. Вычисленная разность d(ВA) сравнивается с предварительно заданным разностным пороговым значением Т_разн. Превышение порога Т_разн показывает, что разница между значениями ФД(MVcand best B,B) и ФД(MVcand best A,A) велика, и это может означать, что блок A и блок B находятся на границе движения (принадлежат объектам с разным движением). Кроме того, на этапе 105 значение ФД(MVcand best B,B) для второго одиночного блока из текущей единицы сравнивается с предварительно заданным абсолютным пороговым значением T_абс, которое показывает, что является ли значение ФД(MVcand best B,B) слишком большим.

Следует отметить, что когда рассматривается конкретный вектор-кандидат, то значение ФД(MVcand,блок) вычисляется для каждого блока пары отдельно. Возможны случаи, когда для одного блока пары это значение ФД(MVcand,блок1) окажется меньше, чем для всех предыдущих векторов-кандидатов, примененных к данному блоку пары (блок1), и тогда текущий вектор-кандидат станет лучшим для этого блока пары, и в тоже время для другого блока пары (блок2) значение ФД(MVcand,блок2) окажется больше, чем значение ФД(MVcand best2,блок2) для какого-то ранее рассмотренного вектора-кандидата MVcand best2. Таким образом, каждый из блоков пары блоков может содержать разные лучшие вектора и значения функции доверия.

На этапе 106 на основе анализа, сделанного на этапе 105, принимается решение, требуется ли рассматривать текущую единицу как два отдельных одиночных блока, или использование двойного блока является приемлемым для текущего применения. В частности, принятие решения о том, что необходимо рассматривать два одиночных блока по отдельности, происходит в случае, когда значение d(ВA) больше, чем значение Т_разн, а также в случае, когда значение ФД(MVcand best B,B) больше, чем значение T_абс. Предварительно задаваемые значения Т_разн и Т_абс позволяют соблюдать компромисс между качеством поля движения (в смысле его близости к реальному полю движения) и скоростью выполнения способа. То есть, если задать относительно высокие значения Т_разн и Т_абс, то рассмотрение дополнительных кандидатов будет происходить реже, и скорость выполнения способа возрастет, но качество поля движения при этом может несколько снизиться, и наоборот, если задать значения Т_разн и Т_абс относительно низкими, то рассмотрение дополнительных кандидатов будет происходить чаще, и скорость выполнения способа упадет, тогда как качество поля движения может улучшиться.

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

Если же на этапе 106 было принято решение, что требуется рассмотрение двух отдельных одиночных блоков, то способ переходит к этапу 107, на котором выполняется формирование набора векторов кандидатов для одиночного блока B, вычисление значений ФД(MVcand B,B) для каждого вектора-кандидата и выбор лучшего из них, то есть того, у которого значение ФД(MVcand B,B) минимально. После этого способ переходит к ранее описанному этапу 108.

В предложенном способе два соседних блока (A и B) на этапах 101-104 используют набор векторов-кандидатов для блока А (это также было показано выше в отношении Фиг. 6). Это уменьшает число векторов-кандидатов и, тем самым, требует меньше вычислений ФД(), что повышает скорость обработки. Кроме того, улучшается шаблон доступа к памяти. Снижение вычислительной сложности и улучшение шаблона доступа к памяти приводит также к снижению энергопотребления.

Второй аспект изобретения

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

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

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