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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание изобретения к патенту

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

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

Данная заявка притязает на приоритет патентной заявки Японии 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.

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

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

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

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

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

Координаты, выводимые такой функцией, могут иметь нормированные значения, например, "x=-1" для каждого пикселя левого конца; "x=1" для каждого пикселя правого конца, "y=-1" для каждого пикселя верхнего конца; "y=1" для каждого пикселя нижнего конца в изображении, или реальные значения координат.

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

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

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

<3> Оценочное значение для процедуры прогнозирования, информационное наполнение (объем информации) дерева, и способ вычисления прогнозируемого значения

<3-1> Оценочное значение для процедуры прогнозирования

При развитии (или эволюции) процедуры прогнозирования, как объяснено ниже, требуется оценочная шкала.

В настоящем изобретении, сумма (X+Y) нижеследующих величин используется в качестве оценочных значений (именуемых "степенью согласия" в генетическом программировании) для каждого индивида, который представляет процедуру прогнозирования:

(i) информационное наполнение X (объем информации) для представления древовидной структуры; и

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

В настоящем изобретении, оценочное значение для индивида (дерево обозначается как "индивид" в генетическом программировании) определяется не только на основании информационного наполнения Y остатка прогнозирования, но и с учетом информационного наполнения X дерева. Одна причина тому состоит в необходимости передавать саму процедуру прогнозирования декодирующей стороне.

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

<3-2> Информационное наполнение X для представления древовидной структуры

Информационное наполнение X для представления древовидной структуры является суммарным информационным наполнением всех узлов дерева.

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

Алгоритм 1

функция tree_info(t)
begin
	if t является численным значением then
		return FUNCINFO + 10
	else begin
		s: = FUNCINFO // часть функции
		foreach (обо всех нижних узлах c соединенных t) begin
			s: = s+tree_info(c)
			end
		return s
	end
end

При этом предполагается, что индивидуальным функциям назначаются порядковые номера от 0 до N-1.

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

FUNCINFO=log ₂ (N+1) Формула (6)

где (N+1) также используется для учета численного значения (например, 2 или 1/4) помимо функций.

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

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

X=tree_info (root) Формула (7)

<3-3> Способ вычисления прогнозируемого значения

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

Алгоритм 2

функция tree_eval(t)

begin

if t является численным значением then

// непосредственное значение

return численное значение

else if t не имеет аргумента then // например, In

return значение функции t

else if t имеет один аргумент then // например, sqrt(A)

return функцию t (tree_eval (первый снизу узел t))

else if t имеет два аргумента then // например, add (A, B)

return функцию t (tree_eval (первый снизу узел t), tree_eval (второй снизу узел t))

else if t имеет три аргумента then // например, троичный оператор T

return функцию t (tree_eval (первый снизу узел t), tree_eval (второй снизу узел t), tree_eval (третий снизу узел t))

end

Хотя вышеприведенный алгоритм предусматривает, что число аргументов ограничено тремя или менее, аналогичные процессы могут осуществляться, даже если верхний предел на количество аргументов установлен равным 4, 5,

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

x'=tree_eval (root) Формула (8)

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

[Формула 1]

В вышеприведенной формуле h_d указывает число появлений (для гистограммы) ошибки прогнозирования d (= x - x') в полном изображении, и W и H, соответственно, указывает количества пикселей в горизонтальном и вертикальном направлениях.

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

<4> Кодирование и декодирование процедуры прогнозирования

<4-1> Кодирование процедуры прогнозирования

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

Алгоритм 3

процедура tree_encode(t)

begin

if t является численным значением then begin

кодировать N (численное значение) с использованием битов FUNCINFO

кодировать численное значение (с фиксированной точкой) с использованием 10-битовой формы

end else begin

кодировать номер функции (0,.. N-1) t с использованием битов FUNCINFO

foreach (обо всех нижних узлах c соединенных t) begin

tree_encode(c)

		end
	end
end

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

<4-2> Декодирование процедуры прогнозирования

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

Алгоритм 4

функция tree_decode()

begin

генерировать пустое дерево T

декодировать биты FUNCINFO для декодирования функции номер n

if n = N then begin // численное значение

декодировать 10 битов для декодирования 10-битвого значения x с фиксированной точкой

T:= x

end else begin

вычислить функцию F, соответствующую функции номер n

T:= F

for i = 1 to "число аргументов, необходимое для F" begin

i-й снизу узел T:= tree_decode()

		end
	end
	return T
end

Вышеуказанное число аргументов, необходимое для F, - это число (известное кодирующей и декодирующей сторонам) значений, используемых для вывода значения из релевантной функции. Если F=add, релевантное число равно 2, и если F=T, релевантное число равно 3.

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

После этого, при выполнении tree_decode(), дерево декодируется посредством релевантного битового потока и затем возвращается.

<5> Автоматическое развитие процедуры прогнозирования с использованием генетического программирования

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

В генетическом программировании, каждое дерево именуется "индивидом". На этом основано нижеследующее объяснение.

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

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

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

4. На основании результатов оценки выбираются выжившие из множества дочерних индивидов (выбор выживших).

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

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

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

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

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

Ссылочный документ 3: Hiroshi Sato, Isao Ono, and Shigenobu Kobayashi, "A New Generation Alternation Model for Genetic Algorithms and Its Assessment", Journal of Japanese Society for Artificial Intelligence, Vol. 12, No. 5, pp. 734-744, 1996.

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

Ссылочный документ 4: Wataru Fujishima and Tomoharu Nagao, "PT-ACTIT; Parameter Tunable-Automatic Construction of Tree-structural Image Transformation", Journal of Institute of Image Information and Television Engineers, Vol. 59, No. 11, pp. 1687-1693, 2005.

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

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

На фиг. 5 показана структура устройства 1 формирования развитого предиктора в качестве варианта осуществления настоящего изобретения.

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

Для реализации автоматического формирования, как показано на фиг. 5, устройство включает в себя блок 10 генерации родительской популяции, блок 11 хранения родительской популяции, блок 12 выбора и дублирования родительского индивида, блок 13 генерации дочерних индивидов, блок 14 хранения мутационной информации, блок 15 расчета оценочного значения, блок 16 определения живучих индивидов, блок 17 определения сходимости, и блок 18 определения развитого предиктора.

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

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

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

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

На основании генетического программирования, блок 13 генерации дочерних индивидов генерирует дочерние индивиды, выбирая родительские индивиды, сгенерированные блоком 12 выбора и дублирования родительского индивида, для кроссинговера, показанного на фиг. 2; мутации, показанной на фиг. 3, с использованием мутационной информации, хранящейся в блоке 14 хранения мутационной информации; инверсии, показанной на фиг. 4; и прочее.

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

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

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

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

На основании оценочных значений, выводимых из блока 15 расчета оценочного значения и прочих, блок 17 определения сходимости определяет, выполнено ли условие сходимости, которое указывает завершение формирования развитого предиктора. Если определено, что условие выполнено, блок 17 определения сходимости предписывает блоку 18 определения развитого предиктора определить развитой предиктор.

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

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

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

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

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

Информационное наполнение X для представления соответствующего дерева вычисляется с использованием вышеописанного алгоритма 1.

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

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

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

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

На следующем этапе S106, M дочерних индивидов генерируются из N дублированных родительских индивидов путем осуществления, например, кроссинговера, показанного на фиг. 2, мутации, показанной на фиг. 3, или инверсии, показанной на фиг. 4, посредством генетического программирования, которое может использовать мутационную информацию, хранящуюся в блоке 14 хранения мутационной информации.

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

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

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

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

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

Используемое условие сходимости может быть таким, при котором скорость уменьшения оценочного значения Z (X+Y) оказывается меньше фиксированного значения (например, 0,1%), или количество итераций для вычисления оценочного значения превышает фиксированное значение (например, 10,000).

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

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

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

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

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

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

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

Устройство 100 кодирования изображений, показанное на фиг. 7, включает в себя блок 101 формирования развитого предиктора, который формирует развитой предиктор, применяемый к целевому изображению кодирования в соответствии с операцией, выполняемой устройством 1 формирования развитого предиктора согласно вышеописанному варианту осуществления, блок 102 кодирования развитого предиктора для кодирования развитого предиктора, сформированного блоком 101 формирования развитого предиктора, блок 103 кодирования изображений для кодирования целевого изображения кодирования с использованием развитого предиктора, сформированного блоком 101 формирования развитого предиктора, и блок 107 передачи кодированных данных, который передает на устройство 200 декодирования изображений (в настоящем варианте осуществления) кодированные данные, генерируемые блоком 102 кодирования развитого предиктора и блоком 103 кодирования изображений.

Вышеописанный блок 103 кодирования изображений включает в себя генератор 104 прогнозируемого значения пикселя, который прогнозирует значение пикселя с использованием развитого предиктора, сформированного блоком 101 формирования развитого предиктора, блок 105 вычисления остатка прогнозирования, который вычисляет остаток прогнозирования на основании значения пикселя, предсказанного генератором 104 прогнозируемого значения пикселя, и кодер 106 остатка прогнозирования для кодирования остатка прогнозирования, вычисленного блоком 105 вычисления остатка прогнозирования.

Устройство 200 декодирования изображений, показанное на фиг. 7, включает в себя блок 201 приема кодированных данных для приема кодированных данных, переданных с устройства 100 кодирования изображений согласно настоящему варианту осуществления, блок 202 декодирования развитого предиктора для декодирования развитого предиктора, сформированного устройством 100 кодирования изображений, путем декодирования кодированных данных развитого предиктора, принятых блоком 201 приема кодированных данных, и блок 203 декодирования изображений для декодирования изображения, закодированного устройством 100 кодирования изображений, на основании развитого предиктора, декодированного блоком 202 декодирования развитого предиктора, и кодированных данных, принятых блоком 201 приема кодированных данных.

Для декодирования изображения, закодированного устройством 100 кодирования изображений, блок 203 декодирования изображений включает в себя генератор 204 прогнозируемого значения пикселя для прогнозирования прогнозируемого значения с использованием развитого предиктора, декодированного блоком 202 декодирования развитого предиктора, декодер 205 остатка прогнозирования для декодирования кодированных данных остатка прогнозирования, принятых блоком 201 приема кодированных данных, и воспроизводитель 206 изображений для воспроизведения изображения, закодированного устройством 100 кодирования изображений, на основании значения пикселя, предсказанного генератором 204 прогнозируемого значения пикселя, и остатка прогнозирования, декодированного декодером 205 остатка прогнозирования.

На фиг. 8 показана логическая блок-схема, выполняемая устройством 100 кодирования изображений, изображенным на фиг. 7, и на фиг. 9 показана логическая блок-схема, выполняемая устройством 200 декодирования изображений, изображенным на фиг. 7.

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

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

Затем, для кодирования целевого изображения кодирования, прогнозируемое значение пикселя (вышеописанное p') генерируется с использованием сформированного развитого предиктора (см. этап S203), и затем остаток прогнозирования (вышеописанная p-p') вычисляется на основании сгенерированного прогнозируемого значения пикселя (см. этап S204).

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

Согласно логической блок-схеме, изображенной на фиг. 9, когда устройство 200 декодирования изображений, имеющее структуру, показанную на фиг. 7, принимает кодированные данные, генерируемые устройством 100 кодирования изображений, устройство 200 декодирования изображений сначала декодирует кодированные данные развитого предиктора на основании вышеописанного алгоритма 4, для декодирования развитого предиктора, сформированного устройством 100 кодирования изображений (см. этап S301).

При дальнейшем декодировании целевого изображения декодирования, на этапе S302, прогнозируемое значение пикселя (вышеописанное p') генерируется с использованием декодированного развитого предиктора, и на следующем этапе S303, кодированные данные остатка прогнозирования декодируются для получения декодированного остатка прогнозирования (т.е. вышеописанной p-p'). На следующем этапе S304, значение пикселя генерируется и выводится на основании ранее сгенерированного прогнозируемого значения пикселя и декодированного остатка прогнозирования.

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

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

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

Таким образом, в соответствии с устройством 100 кодирования изображений и устройством 200 декодирования изображений, которые кодируют и декодируют изображение с использованием развитого предиктора, сформированного устройством 1 формирования развитого предиктора, можно добиться высокого уровня эффективности кодирования.

На фиг. 10 показаны другие варианты осуществления устройства 100 кодирования изображений и устройства 200 декодирования изображений, которые используют вышеописанное устройство 1 формирования развитого предиктора.

Устройство 100 кодирования изображений и устройство 200 декодирования изображений, показанные на фиг. 7, требуют кодирования и передачи развитого предиктора. Однако устройство 100' кодирования изображений и устройство 200' декодирования изображений, показанные на фиг. 10, не осуществляют такого кодирования и передачи развитого предиктора, и развитой предиктор, сформированный кодирующей стороной, может быть сформирован декодирующей стороной с использованием ранее переданных пикселей, благодаря чему кодирующая и декодирующая стороны могут кодировать и декодировать изображение с использованием одного и того же развитого предиктора.

Для реализации вышеозначенной функции, устройство 100' кодирования изображений, показанное на фиг. 10, имеет первый блок 110 кодирования изображений для кодирования частичного изображения, которое принадлежит целевому изображению кодирования и имеет заранее определенный размер, с использованием существующего предиктора; блок 111 формирования развитого предиктора для формирования развитого предиктора, применяемого к декодированному изображению закодированного частичного изображения, где декодированное изображение было получено путем декодирования, выполняемого первым блоком 110 кодирования изображений, для осуществления релевантного кодирования; второй блок кодирования 112 для кодирования оставшегося частичного изображения целевого изображения кодирования с использованием развитого предиктора, сформированного блоком 111 формирования развитого предиктора; и блок 116 передачи кодированных данных, который передает кодированные данные, генерируемые первым блоком кодирования 110 и вторым блоком кодирования 112, на устройство 200' декодирования изображений.

Для кодирования частичного изображения, не закодированного первым блоком кодирования 110, вышеупомянутый второй блок кодирования 112 включает в себя генератор 113 прогнозируемого значения пикселя, который прогнозирует значение пикселя с использованием развитого предиктора, сформированного блоком 111 формирования развитого предиктора, блок 114 вычисления остатка прогнозирования, который вычисляет остаток прогнозирования на основании значения пикселя, предсказанного генератором 113 прогнозируемого значения пикселя, и кодер 115 остатка прогнозирования для кодирования остатка прогнозирования, вычисленного блоком 114 вычисления остатка прогнозирования.

Устройство 200' декодирования изображений, показанное на фиг. 10, имеет блок 210 приема кодированных данных для приема кодированных данных, переданных с устройства 100' кодирования изображений; первый блок 211 декодирования изображений для декодирования кодированных данных, сгенерированных первым блоком 110 кодирования изображений и содержащихся в кодированных данных, принятых блоком 210 приема кодированных данных; блок 212 формирования развитого предиктора для формирования развитого предиктора, применяемого к частичному изображению, декодированному первым блоком 211 декодирования изображений; второй блок 213 декодирования изображений для декодирования частичного изображения, не декодированного первым блоком декодирования изображений 211, на основании развитого предиктора, сформированного блоком 212 формирования развитого предиктора, и кодированных данных, сгенерированных вторым блоком кодирования 112 и содержащихся в кодированных данных, принятых блоком 210 приема кодированных данных; и синтезатор 217 изображения для генерации изображения в качестве цели декодирования путем синтеза изображения, декодированного первым блоком 211 декодирования изображений, и изображения, декодированного вторым блоком 213 декодирования изображений.

Для декодирования частичного изображения, не декодированного первым блоком 211 декодирования изображений, вышеупомянутый второй блок 213 декодирования изображений включает в себя генератор 214 прогнозируемого значения пикселя для прогнозирования прогнозируемого значения с использованием развитого предиктора, сформированного блоком 212 формирования развитого предиктора; декодер 215 остатка прогнозирования для декодирования кодированных данных остатка прогнозирования, принятых блоком 210 приема кодированных данных и назначенных частичному изображению, которое не декодируется первым блоком 211 декодирования изображений; и воспроизводитель 216 изображений для воспроизведения частичного изображения, которое не декодируется первым блоком 211 декодирования изображений, на основании значения пикселя, предсказанного генератором 214 прогнозируемого значения пикселя, и остатка прогнозирования, декодированного декодером 215 остатка прогнозирования.

На фиг. 11 показана логическая блок-схема, выполняемая устройством 100' кодирования изображений, изображенным на фиг. 10, и на фиг. 12 показана логическая блок-схема, выполняемая устройством 200' декодирования изображений, изображенным на фиг. 10.

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

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

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

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

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

Затем, для кодирования оставшегося частичного изображения, которое также принадлежит целевому изображению кодирования, но не закодировано на вышеописанном этапе S401, прогнозируемое значение пикселя (вышеописанное p') генерируется с использованием сформированного развитого предиктора (см. этап S404), и на следующем этапе S405, остаток прогнозирования (вышеописанная p-p') вычисляется на основании сгенерированного прогнозируемого значения пикселя.

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

Согласно логической блок-схеме, изображенной на фиг. 12, когда устройство 200' декодирования изображений принимает кодированные данные, генерируемые устройством 100' кодирования изображений, устройство 200' декодирования изображений начинает с декодирования кодированных данных частичного изображения (имеющего N пикселей в качестве предполагаемого условия), закодированного устройством 100' кодирования изображений с использованием существующего предиктора (см. этап S501). На следующем этапе S502, декодирование продолжается до тех пор, пока не будет подтверждено завершение декодирования для релевантного частичного изображения и, таким образом, декодирование частичного изображения.

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

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

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

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

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

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

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

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

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

Таким образом, в соответствии с устройством 100' кодирования изображений и устройством 200' декодирования изображений, которые кодируют и декодируют изображение с использованием развитого предиктора, сформированного устройством 1 формирования развитого предиктора, можно добиться высокого уровня эффективности кодирования.

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

(add (sub 0.5 (sub (div (Igap) (Ine)) (Igap))) (div (Inw) (Igap))),

где Igap обозначает нелинейно-прогнозируемое значение, полученное с периферии, и Ine и Inw - это значения периферийных пикселей, показанных на фиг. 14.

Полученное оценочное значение X+Y имело размер 1170235 битов, что лучше, чем максимальное значение 1176090 битов, получаемое с использованием доступных в настоящее время существующих предикторов.

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

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

В настоящем эксперименте, сравнительные деревья прогнозирования представляли собой предиктор на основе наименьших квадратов (LS), который осуществляет линейное прогнозирование, предиктор на основе минимальной энтропии (LE), который также осуществляет линейное прогнозирование, предиктор GAP для CALIC, который осуществляет нелинейное прогнозирование (с использованием четырех периферийных пикселей, аналогично настоящему изобретению (см. фиг. 14)), и предиктор MED для JPEG-LS, который также осуществляет нелинейное прогнозирование (с использованием трех периферийных пикселей).

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

На фиг. 13 показано информационное наполнение (X+Y) для остатка каждого изображения (имеющего 512×512 пикселей, 8-битовую градацию и только данные яркости), используемого в эксперименте, где информационное наполнение также учитывает служебную нагрузку (50 для LS и LE, 0 для MED, и биты X для способа, предложенного согласно настоящему изобретению). На фиг. 13 также показано каждое увеличение относительно информационного наполнения предложенного способа для каждого изображения. Кроме того, в нижней строке на фиг. 13 показано информационное наполнение X дерева, отвечающего настоящему изобретению, для каждого изображения. Единицей остаточного информационного наполнения является bpp (ямок на пиксель).

Результаты эксперимента подтвердили, что предиктор, автоматически формируемый в соответствии с настоящим изобретением, имеет наивысший уровень эффективности. Средняя величина информационного наполнения X для дерева предиктора, автоматически формируемого в соответствии с настоящим изобретением, составляет 726 битов, что говорит о небольшом усложнении по сравнению с предикторами GAP и MED (которые, соответственно, имеют 349,5 битов и 116,0 битов, и заданы равными нулю в настоящем эксперименте).

Для изображения "Лена", вычисление развития осуществлялось раздельно без учета информационного наполнения X дерева, чтобы минимизировать только остаточное информационное наполнение Y. По сравнению с результатами, представленными на фиг. 13, результаты раздельного вычисления для предложенного способа, отвечающего настоящему изобретению, показывают, что Y (сама величина Y не показана на фиг. 14) уменьшилась на 0,06%, но X увеличилась примерно в три раза (т.е., X=2795 битов), так что X+Y увеличилась на 0,14%. Хотя разрастание дерева является проблемой, именуемой "раздуванием", вследствие ГП, настоящее изобретение, естественно, позволяет предотвратить ее возникновение благодаря учету X.

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

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

Промышленное применение

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

Перечень условных обозначений

1 устройство формирования развитого предиктора

10 блок генерации родительской популяции

11 блок хранения родительской популяции

12 блок выбора и дублирования родительского индивида

13 блок генерации дочерних индивидов

14 блок хранения мутационной информации

15 блок расчета оценочного значения

16 блок определения живучих индивидов

17 блок определения сходимости

18 блок определения развитого предиктора.