СПОСОБ И УСТРОЙСТВО НАХОЖДЕНИЯ ВЕКТОРА ДВИЖЕНИЯ, ПРОГРАММА И НОСИТЕЛЬ ЗАПИСИ ДЛЯ ХРАНЕНИЯ ПРОГРАММЫ

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

Заявляется приоритет по заявке на патент Японии № 2007-064286, поданной 14 марта 2007 г., содержание которой включено здесь со ссылкой.

УРОВЕНЬ ТЕХНИКИ

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

Соответственно, нахождение вектора движения выполняется с учетом объема сгенерированного кода в качестве непроизводительных затрат. В программном обеспечении в Н.264 по ссылке при выборе режима прогнозирования используется функция затрат «Cost=D+λ·R» (см., например, беспатентный документ 1).

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

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

Объем кода, сгенерированного для вектора движения, изменяется в зависимости от способа кодирования видеосигнала.

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

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

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

В качестве примера использования на втором этапе вектора движения (называемого «исходный вектор движения»), который использовался на первом этапе, на Фиг.8А и 8В показан процесс кодирования видеосигнала с использованием другого способа нахождения вектора движения, а на Фиг.9А и 9В показан процесс перекодирования.

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

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

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

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

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

На Фиг.10 показана блок-схема описанного выше повторного поиска.

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

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

Беспатентный документ 1: адрес в Интернете

Беспатентный документ 2: ISO/IEC-13818-2, “Information technology - Generic coding of moving pictures and associated audio information: Video”, Стр. 77-85, май 1996 г.

Беспатентный документ 3: ITU-T H.264 ITU-T Rec. H.264, “Advanced video coving for generic audiovisual services”, стр. 146-148, март 2005 г.

Патентный документ 1: Нерассмотренная патентная заявка Японии, Первая публикация № 2000-244921.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

ПРОБЛЕМА, РЕШАЕМАЯ ИЗОБРЕТЕНИЕМ

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

На Фиг.11 показан пример вышесказанного. Пример показывает вектор движения с минимальными затратами в области повторного поиска (вблизи от исходного вектора движения) на втором этапе, и другой вектор движения, который расположен вне области повторного поиска и имеет затраты ниже, чем минимальные затраты первого вектора.

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

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

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

СРЕДСТВА ДЛЯ РЕШЕНИЯ ПРОБЛЕМЫ

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

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

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

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

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

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

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

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

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

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

ЭФФЕКТ ИЗОБРЕТЕНИЯ

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг.2А - диаграмма, поясняющая область повторного поиска, ограниченную по настоящему изобретению.

Фиг.2В - также диаграмма, поясняющая область повторного поиска, ограниченную по настоящему изобретению.

Фиг.2С - также диаграмма, поясняющая область повторного поиска, ограниченную по настоящему изобретению.

Фиг.2D - также диаграмма, поясняющая область повторного поиска, ограниченную по настоящему изобретению.

Фиг.3 - диаграмма, показывающая структуру устройства кодирования видеоинформации по настоящему изобретению.

Фиг.4 - диаграмма, показывающая пример внутренней структуры устройства кодирования видео.

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

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

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

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

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

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

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

Фиг.10 - блок-схема алгоритма при обычной технологии обработки.

Фиг.11 - диаграмма, поясняющая проблему обычной технологии.

ОБОЗНАЧЕНИЯ

НАИЛУЧШИЙ СПОСОБ РЕАЛИЗАЦИИ ИЗОБРЕТЕНИЯ

Ниже настоящее изобретение будет объяснено с помощью вариантов осуществления.

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

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

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

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

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

Как показано на блок-схеме, на первом этапе S101 исходный вектор движения, который был получен в первой системе кодирования видеосигнала, вводится в данную систему.

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

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

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

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

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

На следующем этапе S105 с помощью повторного поиска на основе выделенных точек повторного поиска определяется вектор движения.

Далее будет изложен способ ограничения области повторного поиска на основе исходного вектора движения и прогнозируемого вектора.

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

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

(1) Круговая форма

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

(2) Эллиптическая форма

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

(3) Прямоугольная форма

Как показано на Фиг.2С, может быть начерчен прямоугольник, длинные стороны которого соответствуют расстоянию между исходным вектором движения и прогнозируемым вектором, а длина коротких сторон заранее задана как константа, для определения области повторного поиска выделяются поисковые точки, включенные в прямоугольник.

(4) Линейный сегмент

Как показано на Фиг.2D, может быть начерчен линейный сегмент, который соединяет исходный вектор движения и прогнозируемый вектор движения друг с другом таким образом, что для определения области повторного поиска выделяются поисковые точки линейного сегмента.

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

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

Например, если имеют место два размера блока 16×16 и 8×8, вычисление вектора движения, соответствующего минимальным непроизводительным затратам, и определение области повторного поиска проводятся для каждого размера.

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

КОНКРЕТНЫЙ ВАРИАНТ ОСУЩЕСТВЛЕНИЯ

Ниже настоящее изобретение более подробно объясняется для конкретного варианта осуществления.

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

Как показано на Фиг.3, устройство 1 кодирования видеосигнала реализует генерацию прогнозируемого сигнала из целевого видеосигнала, вычисляет разность между видеосигналом и прогнозируемым сигналом и генерирует и выводит закодированный битовый поток с помощью квантования и кодирования разности. Устройство имеет функцию вычисления прогнозированного вектора целевого кодируемого блока на основе вектора движения уже закодированного блока, расположенного в окрестности кодируемого блока, и имеет узел 10 нахождения движения для нахождения вектора движения. Устройство также содержит ограничитель 20 области повторного поиска, в который вводятся исходный вектор движения, полученный в предшествующей системе кодирования видеосигнала, и прогнозируемый вектор, вычисленный узлом 10 нахождения движения. Ограничитель 20 области повторного поиска задает область повторного поиска (регион) целевого вектора движения узлу 10 нахождения движения.

На Фиг.4 показан пример структуры ограничителя 20 области повторного поиска устройства 1 кодирования видеосигнала, так чтобы реализовывать процесс поиска вектора движения по настоящему варианту осуществления.

Как показано на Фиг.4, ограничитель 20 области повторного поиска содержит узел 200 ввода прогнозируемого вектора, узел 201 ввода исходного вектора движения, узел 202 ввода информации о типе фигуры, узел 203 задания области повторного поиска и узел 204 хранения параметра фигуры.

Вычисленный узлом 10 нахождения движения прогнозируемый вектор вводится узлом 200 ввода прогнозируемого вектора в ограничитель 20 области повторного поиска. Исходный вектор движения, полученный в предшествующей системе кодирования видеосигнала, вводится узлом 201 ввода исходного вектора движения в ограничитель 20 области повторного поиска.

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

Узел 203 задания области повторного поиска задает область повторного поиска для вектора движения на основе введенного узлом 200 ввода прогнозированного вектора прогнозируемого вектора, введенного узлом 201 ввода исходного вектора движения вектора движения, и информации о типе фигуры, введенной узлом 202 ввода информации о типе фигуры, и передает установки для области повторного поиска на узел 10 нахождения движения.

Узел 204 хранения параметра фигуры имеет показанную на Фиг.5 структуру данных и хранит информацию о параметрах фигуры, которые используются, когда узел 203 задания области повторного поиска задает область повторного поиска.

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

Далее, как описано при рассмотрении Фиг.2С, для задания области повторного поиска прямоугольная фигура требует задания длины других сторон, сохраняется именно эта установочная информация.

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

Кроме того, прогнозируемый вектор вычисляется с использованием трех блоков возле целевого блока.

Далее, исходный битовый поток уже был декодирован перед кодированием на втором (данном) этапе, и был сохранен соответствующий вектор движения.

Фиг.6 показывает пример блок-схемы алгоритма, реализуемого устройством 1 кодирования видеосигнала, имеющего показанную на Фиг.4 структуру.

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

Как показано на блок-схеме Фиг.6, в устройстве 1 кодирования видеосигнала выполняется ввод заранее определенной информации о типе фигуры для области повторного поиска (см. первый этап S201).

На следующем этапе S202, в узле 204 хранения параметров фигуры находятся параметры, определяемые введенной информацией о типе фигуры.

Если информация о типе фигуры задана для всей последовательности видеосигналов, процесс от этапов S201 до S202 выполняется только один раз для всей последовательности видеосигналов.

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

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

Например, если медиана векторов движения (<MVA>, <MVB>, и <MVC>) трех блоков рядом с целевым кодируемым блоком вычисляется в качестве прогнозируемого вектора, прогнозируемый вектор <PMV> вычисляется по следующим формулам:

PMVx = Median (MVAx, MVBx, MVCx)

PMVy = Median (MVAy, MVBy, MVCy)

где <...> обозначает вектор.

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

Далее с помощью блок-схемы Фиг.7 будет детально описан процесс выполнения этапа S205 блок-схемы Фиг.6 для конкретного примера, в котором типом фигуры для области повторного поиска задается «линейный сегмент».

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

То есть, если в качестве типа фигуры для области повторного поиска задан «линейный сегмент», то в ходе обработки на этапе S205 (см. блок-схему Фиг.7) выполняется инициализация с использованием исходного вектора движения (см. первый этап S301), таким образом, что входной исходный вектор движения <MVO> задается в качестве исходного вектора движения, и в качестве минимальных затрат задаются затраты исходного вектора движения <MVO>.

На следующем этапе S302 рассчитывается линейный сегмент “y=αx+β”, определяемый между исходным вектором движения <MVO> и прогнозируемом вектором <PMV>.

То есть, градиент α и отрезок β вычисляются по следующим формулам:

α=(PMVy-MVOy)/(PMVx-MVOx)

β=MVOy-α·MVOx

где случай “PMVx=MVOx” исключен.

На следующем этапе S303, если абсолютное значение │α│ вычисленного градиента больше или равно 1, вертикальный компонент изменяется на 1. Если абсолютное значение │α│ меньше 1, горизонтальный компонент изменяется на 1. Используя изменение горизонтального или вертикального компонента с помощью соответствующей формулы для линейного сегмента, вычисляется другой компонент, при этом на линейном сегменте “y=αx+β” вычисляется положение поиска. Здесь если “PMVx=MVOx” изменяется только вертикальный компонент.

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

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

На следующем этапе S307 определяется, совпадает ли положение поиска с прогнозированным вектором. Если определяется, что они не совпадают друг с другом, происходит возврат к этапу S303, если определяется, что они совпадают, операция завершается.

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

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

Кроме того, поиск может начинаться с положения с относительно низкими затратами.

Блок-схема Фиг.7 показывает процесс, выполняемый на этапе S205 блок-схемы Фиг.6, где предполагается, что область повторного поиска задана как «линейный сегмент». Однако подобная операция выполняется и когда задается тип фигуры (области повторного поиска), отличный от «линейного сегмента».

То есть в области повторного поиска, ограниченной как показано на Фиг.2А-2С, последовательно выбирается каждое положение поиска и вычисляются необходимые затраты. Если определяется, что вычисленные затраты меньше, чем только что определенные минимальные затраты, минимальные затраты и вектор движения изменяются на основе вычисленных затрат и вектора движения. Путем повторения такой операции находится вектор движения, который дает минимальные затраты.

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

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

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

ПРОМЫШЛЕННАЯ ПРИМЕНИМОСТЬ

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