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

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

Иллюстрации

Показать все

Реферат

Область техники

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

Данная заявка притязает на приоритет патентной заявки Японии 2008-275811, поданной 27 октября 2008 г., содержание которой включено сюда в порядке ссылки.

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

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

Согласно такому способу кодирования с прогнозированием, при кодировании целевого пикселя (обозначенного "p"), подлежащего кодированию, прогнозируемое значение p генерируется с использованием того факта, что ранее декодированные периферийные пиксели (например, Inw, In, Ine и Iw на фиг. 14) имеют, в общем случае, высокую корреляцию с p, и, фактически с использованием таких периферийных пикселей. В дальнейшем, прогнозируемое значение p обозначается p'. На следующем этапе ошибка прогнозирования p-p' подвергается энтропийному кодированию.

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

В примере, именуемом "усредненное прогнозирование" в качестве одного из методов в предикторах JPEG, прогнозирование осуществляется путем вычисления среднего значения In и Iw следующим образом:

x'=(In+Iw)/2 Формула (1)

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

x'=In+Iw-Inw плоскостное прогнозирование Формула (2)

x'=In прогнозирование предыдущего значения Формула (3)

x'=Inw+(In-Iw)/2 комплексное прогнозирование Формула (4)

JPEG-LS (см. Непатентный документ 2), имеющий более высокий уровень эффективности, чем JPEG, применяет немного более сложный метод прогнозирования, именуемый "прогнозирование MED", представленный ниже.

if Inw≥max (Iw, In) then

x'=min (Iw, In)

else if Inw≤min (Iw, In) then

x'=max (Iw, In)

else

x'=Iw+In-Inw

где max (x, y) - функция, которая возвращает то из значений x и y, которое больше, и mix (x, y) - функция, которая возвращает то из значений x и y, которое меньше.

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

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

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

Документ уровня техники

Непатентный документ

Непатентный документ 1: ISO/IEC SC29/WG1, ISO/IEC 10918-1 "Digital compression and coding of continuous-tone still images", p. 133, 1993.

Непатентный документ 2: M. Weinberger, G. Seroussi, and G. Sapiro, "The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS", IEEE Trans. Image Processing, Vol. 9, No. 8, pp. 1309-1324, August 2000.

Непатентный документ 3: Ichiro Matsuda, Nau Ozaki, Yuji Umezu, and Susumu Itoh, "Lossless Coding Using Variable Block-Size Adaptive Prediction Optimized for Each Image", Proceedings of 13th European Signal Processing Conference (EUSIPCO 2005), WedAmPO3, Sep. 2005.

Непатентный документ 4: Masaharu Tanaka, Hidenori Sakanashi, Masanobu Mizoguchi and Tetsuya Higuchi, "Bi-level Image Coding for Digital Printing Using Genetic Algorithm", Proceedings of IEICE, D-II, Vol. J83-D-II, No. 5, pp. 1274-1283, May 2000.

Непатентный документ 5: Koh'ichi Takagi, Atsushi Koike, Shuichi Matsumoto, and Hideo Yamamoto, "Moving Picture Coding Based on Region Segmentation Using Genetic Algorithm", Proceedings of IEICE, D-II, Vol. J83-D-II, No. 6, pp. 1437-1445, June 2000.

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

Задача изобретения

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

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

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

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

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

Решение задачи

<1> Структура устройства автоматического формирования процедуры генерации прогнозируемого значения пикселя, отвечающего настоящему изобретению

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

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

(1) первое устройство, которое генерирует родительскую популяцию путем случайного формирования процедур генерации прогнозируемого значения, каждая из которых указана посредством древовидной структуры;

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

(3) третье устройство, которое:

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

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

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

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

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

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

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

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

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

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

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

<2> Структура устройства кодирования изображений и устройства декодирования изображений, согласно настоящему изобретению (первый тип)

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

<2-1> Структура устройства кодирования изображений, отвечающего настоящему изобретению

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

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

(2) второе устройство, которое кодирует процедуру генерации прогнозируемого значения, сформированную первым устройством (с использованием, например, Алгоритма 3, описанного ниже);

(3) третье устройство, которое генерирует прогнозируемое значение каждого пикселя, включенного в целевое изображение кодирования, на основании процедуры генерации прогнозируемого значения, сформированной первым устройством (т.е., с использованием, например, Алгоритма 2, описанного ниже); и

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

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

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

<2-2> Структура устройства декодирования изображений, отвечающего настоящему изобретению

Для декодирования кодированных данных, генерируемых устройством кодирования изображений, отвечающим настоящему изобретению, описанным в вышеприведенном пункте <2-1>, устройство декодирования изображений, в соответствии с настоящим изобретением, имеет структуру, которая включает в себя:

(1) первое устройство, которое декодирует кодированные данные для процедуры генерации прогнозируемого значения, сформированные посредством операции, выполняемой устройством автоматического формирования процедуры генерации прогнозируемого значения пикселя, в соответствии с настоящим изобретением (с использованием, например, Алгоритма 4 описанного ниже), где кодированные данные сгенерированы на кодирующей стороне;

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

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

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

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

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

<3> Структура устройства кодирования изображений и устройства декодирования изображений согласно настоящему изобретению (второй тип)

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

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

<3-1> Структура устройства кодирования изображений, отвечающего настоящему изобретению

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

(1) первое устройство, которое кодирует частичное целевое изображение кодирования, имеющее заранее определенный размер, с использованием существующей процедуры генерации прогнозируемого значения пикселя, сформированной не на основании способа развития древовидной структуры;

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

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

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

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

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

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

<3-2> Структура устройства декодирования изображений, отвечающего настоящему изобретению

Для декодирования кодированных данных, генерируемых устройством кодирования изображений, отвечающим настоящему изобретению, описанным в вышеприведенном пункте <3-1>, устройство декодирования изображений, в соответствии с настоящим изобретением, имеет структуру, которая включает в себя:

(1) первое устройство, которое декодирует кодированные данные для частичного целевого изображения декодирования, которое имеет заранее определенный размер, и закодировано с использованием существующей процедуры генерации прогнозируемого значения пикселя, сформированной не на основании способа развития древовидной структуры, где кодированные данные сгенерированы на кодирующей стороне;

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

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

(4) четвертое устройство, которое декодирует кодированные данные для сигнала остатка прогнозирования, вычисленного с использованием прогнозируемого значения пикселя, сгенерированного на основании процедуры генерации прогнозируемого значения, декодированной вторым устройством, где кодированные данные сгенерированы на кодирующей стороне; и

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

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

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

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

Результат изобретения

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

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

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

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

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

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

Фиг. 2 - схема, поясняющая операцию кроссинговера.

Фиг. 3 - схема, поясняющая операцию мутации.

Фиг. 4 - схема, поясняющая операцию инверсии.

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

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

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

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

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

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

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

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

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

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

Предпочтительные варианты осуществления изобретения

Настоящее изобретение предусматривает использование генетического программирования (ГП) для реализации автоматического компьютерного формирования процедуры прогнозирования, которая надлежащим образом применяется к входному видео или статическому изображению (далее именуемому просто "изображение"), и дополнительного сокращения релевантного объема кода.

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

<1> Представление процедуры прогнозирования посредством древовидной структуры

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

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

Например, в символьном выражении, вышеописанный max (x, y) описывается как (max x y), и вышеописанное прогнозирование MED описывается следующим образом:

(T (sub (Inw) (max (Iw) (In))) (min (Iw) (In)) (T (sub (min (Iw) (In)) (Inw)) (max (Iw) (In)) (add (Iw) (sub (In) (Inw))))),

где каждый перевод строки не имеет конкретного значения.

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

(T A B C)	=B	если A≥0
	=C	если A <0	Формула (5)

где T - первая буква слова "троичный".

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

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

Поскольку такая функция использует аргументы, она оказывается в другой позиции, чем лист релевантного дерева, и, таким образом, часто называется "неконечным узлом". Функцию можно подготавливать заранее, или можно задавать динамически (см. Ссылочный документ 1).

Ссылочный документ 1: J. Koza, "Genetic Programming II, Automatic Discovery of Reusable Programs", The MIT Press, pp. 41, 1998.

Кроме того, численное значение, например, 0,148 или значение периферийного пикселя, например, Iw, In, Ine или Inw (см. фиг. 14) может играть роль конечного узла, который сам имеет значение и назначается листу дерева.

<2> Характеристики конечных узлов в настоящем изобретении

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

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

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

Прогнозируемое значение, выводимое релевантной функцией, может являться прогнозируемым значением на основе наименьших квадратов, значением, полученным плоскостным прогнозированием, прогнозируемым значением для CALIC (см. Ссылочный документ 2 ниже), прогнозируемым значением для JPEG-LS, и прочее.

Ссылочный документ 2: X. Wu and N. Memon: "Context-Based, Adaptive, Lossless Image Coding", IEEE Transactions on Communications, Vol.45, No.4, pp. 437-444, Apr. 1997.

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

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