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

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

 

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

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

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

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

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

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

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

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

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

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

- определение оператора отмены преобразования согласно упомянутой разложенной сетке; и

- декодирование облака точек посредством применения оператора отмены преобразования к кадру.

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

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

Настоящее раскрытие сущности также относится к способу кодирования двумерного облака точек в потоке битов. Способ содержит:

- формирование разложенной сетки посредством преобразования регулярной сетки согласно оператору плотного преобразования;

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

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

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

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

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

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

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

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

- определять оператор отмены преобразования согласно разложенной сетке; и

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

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

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

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

- формировать разложенную сетку посредством преобразования регулярной сетки согласно оператору плотного преобразования;

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

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

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

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

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

Настоящее раскрытие сущности также относится к потоку, переносящему данные, представляющие двумерное облако точек, при этом данные содержат:

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

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

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

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

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

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

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

Фиг. 3 схематически показывает вычисление оператора упрощенного преобразования (SMO) из оператора плотного преобразования по фиг. 2, согласно настоящим принципам;

Фиг. 4 схематически показывает кодирование облака точек по фиг. 1 в прямоугольном кадре с использованием SMO, как описано на фиг. 3, согласно варианту осуществления;

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

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

Фиг. 7 иллюстрирует способ для кодирования двумерных облаков точек согласно неограничивающему варианту осуществления настоящих принципов;

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

Фиг. 9 показывает примерную архитектуру устройства, которое может быть выполнено с возможностью реализовывать способ, описанный в связи с фиг. 7 и/или 8, согласно варианту осуществления настоящих принципов;

Фиг. 10 иллюстрирует пример передачи кадра и данных по фиг. 3, 4 и 5 между двумя удаленными устройствами по фиг. 9 по сети связи, согласно варианту осуществления настоящих принципов;

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

5. Подробное описание вариантов осуществления

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

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

Двумерное облако точек представляет собой набор двумерных координат, выражаемых в системе отсчета и ассоциированных со значением (например, цвета или глубины). Двумерное облако точек может представлять собой результат проекции на поверхности n-мерного облака точек, причем n больше двух. Двумерное облако точек может кодироваться в растеризированном кадре (т.е. в массиве пикселов), преобразованном в системе отсчета. Каждая точка облака точек преобразуется в один пиксел. Несколько точек могут преобразовываться в один пиксел. Когда две или более точек преобразуются в один пиксел, их ассоциированная информация комбинируется, например, усредняется. Когда, для данного пиксела, точка не преобразуется, этот пиксел задается равным "неиспользуемому" значению. Поскольку пикселы цвета или глубины не предназначены для того, чтобы встраивать "неиспользуемое" значение, обычная практика в данной области техники заключается в том, чтобы создавать дополнительный кадр, в котором пикселы встраивают булево значение ("неиспользуемый"/"используемый"), и значение по умолчанию предоставляется неиспользуемым пикселам. Такой кадр называется "ключевым кадром" (или ключевым изображением). Ключевые кадры используются в качестве маски для того, чтобы различать между значащими пикселами и неиспользуемыми пикселами. Ключевые кадры обычно не сжимаются или сжимаются без потерь, поскольку небольшая ошибка в ключевом изображении может формировать большую ошибку в декодированном изображении. Идентичный ключевой кадр может использоваться для нескольких информационных кадров (например, цветового кадра и кадра глубины). Как информационные кадры, так и ключевой кадр кодируются в потоке и передаются вместе. В разновидности, информационные кадры и ключевой кадр передаются отдельно.

Фиг. 1 иллюстрирует обычный оператор преобразования для кодирования облака точек в растеризированном кадре. Каждая точка облака 10 точек имеет координаты в системе отсчета, ассоциированной с пространством, и встраивает, по меньшей мере, одну информацию, например, глубину или цвет. Оператор 11 преобразования используется для того, чтобы преобразовывать каждую точку в пиксел кадра 12. Кадр 12 имеет ширину (т.е. число столбцов пикселов) и высоту (т.е. число строк пикселов). Оператор 11 тождественного преобразования (IMO) выражает координаты точек облака 10 точек согласно ширине и высоте кадра 12. Оператор 11 тождественного преобразования ассоциируется с точкой, имеющей координаты (u, v), принадлежащие [u_min, u_max] x [v_min, v_max], причем соответствующий пиксел (i, j) принадлежит [0, W-1] x [0, H-1], где W и H, соответственно, означают ширину и высоту кадра 12.

Общая форма для оператора 11 преобразования может задаваться следующим образом:

(уравнение 1) ,

где M₀ представляет собой оператор нормализованного преобразования, который представляет собой тождественную функцию в случае M₀=IMO 11. Такой оператор имеет преимущество простой реализации с помощью прямого и простого в вычислении обратного оператора. Этот оператор не должен обязательно кодироваться в потоке, поскольку он используется в качестве оператора преобразования по умолчанию и отмены преобразования в предшествующем уровне техники. IMO 11 сохраняет информацию точек в пикселах 13 кадра 12. Для плотных частей облака точек, имеется высокая вероятность того, что две или более точек преобразуются в идентичный пиксел. Соответствующие ассоциированные значения затем комбинируются в уникальном (например, усредненном) значении. Большая часть 14 пикселов кадра задается равной "неиспользуемому" значению. Эта область 14 является бесполезной, тогда как она может использоваться для того, чтобы сохранять информацию различных точек, которые комбинируются в идентичный пиксел посредством IMO 11.

Фиг. 2 иллюстрирует оператор 21 плотного преобразования (DMO), который преобразует точки облака 10 точек по фиг. 1 в кадр 22 неортогональным способом. DMO 21 представляет собой оператор, который преобразует точки в кадр по-разному согласно локальной плотности точек в облаке. Такой оператор оптимизирует распределение точек по кадру, чтобы минимизировать число "неиспользуемых" пикселов и максимизировать число информационных пикселов. Этот технический эффект проиллюстрирован на фиг. 2: полезная часть 13 кадра 22 шире полезной части кадра 12 по фиг. 1, в то время как "неиспользуемая" часть 14 кадра 22 меньше "неиспользуемой" части 14 кадра 12. Существуют технологии для того, чтобы вычислять такой оператор 21 плотного преобразования и выполнять адаптивное искривление. Из числа этих технологий, категория алгоритмов на основе формирования сетки (например, как указано в работе "A Practical Guide to Direct Optimization for Planar Grid-Generation", J.E. CASTILLO, J.S. OTTO) имеет преимущество обеспечения некоторых ключевых свойств, которые должен иметь такой оператор. В частности, алгоритм на основе формирования сетки должен выбираться, чтобы формировать раскладываемую проекцию пространства облаков точек в пространстве кадров. Он представляет собой обязательное свойство выбранного оператора плотного преобразования, чтобы обеспечивать возможность вычисления оператора упрощенного преобразования, например, в качестве билинейного кусочного интерполятора.

Оптимизированный оператор 21 плотного преобразования может вычисляться для кадра или последовательности кадров, к примеру, группы изображений (GOP) стандартов сжатия видео. Вычисление такого DMO является длительным и ресурсоемким. Вычисление обратного оператора также является сложным. В некоторых случаях, обратный оператор даже не является математически определимым. В любом случае, кодирование такого алгоритма требует длинного списка параметров, которые должны сжиматься без потерь (или даже вообще не сжиматься). Неэффективно ассоциировать кодирование DMO или кодирование его обратного DMO^-1 с кадром или GOP. Вычисление DMO, оптимизированного для изображения или последовательности изображений, находится за пределами объема настоящего раскрытия сущности. DMO вычисляется как оптимальный для облака точек или группы облаков точек. DMO 21 может отличаться для кодирования различных облаков точек. Преобразование облака 10 точек в кадре 22 соответствует уравнению (уравнение 1), в котором M₀=DMO 21.

Фиг. 3 схематически показывает вычисление оператора 31 упрощенного преобразования из оператора 21 плотного преобразования, согласно настоящим принципам. Во-первых, задается регулярная сетка 30 из K*L точек. На фиг. 3 точки сетки связываются посредством сегментов только для визуальной цели. Сетка представляет собой набор точек, регулярно распределенных по пространству облака точек. Координаты этих точек регулярно распределяются в системе отсчета пространства. Информация, ассоциированная с этими точками, является значением существования (т.е. булевым значением). Это облако 30 регулярных точек (которое дополнительно называется "сеткой") преобразуется в кадр 32 с использованием DMO 21, вычисленного для облака 10 точек (или группы облаков точек) по фиг. 2. Как результат, K*L точек сетки 30 преобразуются в пикселах кадра 32. Кадр 32 имеет размер, идентичный размеру кадра 22. На фиг. 3, точки кадра 32 связываются посредством сегментов только для визуальной цели. Сегменты иллюстрируют ключевой признак раскладывания операторов плотного преобразования, таких как DMO 21: результат проекции посредством DMO 21 сетки 30 представляет собой сетку; т.е. "ни один сегмент преобразованной сетки не пересекает другой сегмент преобразованной сетки". Точки сетки 30 остаются в идентичном структурном порядке после преобразования посредством DMO 21. Две точки A и B сетки 30 могут проецироваться в идентичный пиксел изображения 32. Если DMO 21 приводит к такой ситуации, которая исходит из того факта, что отсутствуют точки в облаке 10 точек (или группе облаков точек) по фиг. 2 между (и/или в близком окружении) координатами точек A и B.

Согласно настоящим принципам, на этом этапе, формируются два объекта. Сначала K*L координат преобразованных точек сетки 30 сохраняются и кодируются в данных 33. Данные 33 кодируются как матрица K*L двумерных координат. В разновидности, данные 33 кодируются как две матрицы K*L целых чисел или чисел с плавающей запятой. В разновидности, K*L координат нормализуются для ширины и высоты изображения и сохраняются в данных 33. Эти матрицы используются для того, чтобы задавать, например, посредством параметризации, обратный оператор. Во-вторых, оператор 31 упрощенного преобразования вычисляется в качестве интерполятора между точками сетки 32. Например, интерполятор может представлять собой билинейный кусочный интерполятор между проецируемыми точками. В разновидности, интерполятор может представлять собой бикубический кусочный интерполятор, как описано, например, в работе Fritsch, F. N. и Carlson, R. E. (1980) "Monotone piecewise cubic interpolation"; SIAM Journal on Numerical Analysis, 17 (2), 238-246. В другой разновидности, интерполятор может представлять собой фильтр Ланцоша, который известен для специалистов в данной области техники.

Билинейная кусочная интерполяция, проиллюстрированная на фиг. 6, представляет собой технологию, известную для специалистов в области обработки изображений. Точка облака 10 точек, преобразованного посредством IMO 11, должна иметь координаты 60a. Эта позиция может быть выражена в системе отсчета прямоугольника, заданного посредством четырех точек 61a, 62a, 63a и 64a регулярной сетки 30. Эта позиция нормализуется в прямоугольнике. Например, координаты 60a имеют значение x, равное процентной доле 65 длины сегмента [61a-62a] (и аналогично для сегмента [64a-63a]) и значение y, равное процентной доле 66 длины сегмента [61a-64a] (и аналогично для сегмента [62a-63a]). Билинейная кусочная интерполяция сохраняет эти процентные доли согласно сегментам, соответствующим преобразованию посредством DMO 21 четырех точек 61a, 62a, 63a и 64a регулярной сетки 30. Координаты 61b, 62b, 63b и 64b (сохраненные в данных 33) представляют собой преобразования посредством DMO 21 соответствующих координат 61a, 62a, 63a и 64a. Билинейная кусочная интерполяция координат 60a затем представляет собой 60b. Процентные значения 65 и 66 сохраняются посредством этого преобразования, соответственно, для сегментов [61b-62b] и [64b-63b] для значения x и для сегментов [61b-64b] и [62b-63b] для значения y в преобразованной системе отсчета. Этот оператор является простым в определении согласно координатам 61b, 62b, 63b и 64b, и его применение к облаку точек очень быстро вычисляется. Обратная функция основана на идентичных принципах и является простой в определении согласно координатам 61b, 62b, 63b и 64b, сохраненным в данных 33, и ее применение к кадру очень быстро вычисляется. Дополнительно, кусочный билинейный интерполятор имеет преимущество возможности полного определения посредством подсписка узловых точек, возможно небольших и простых в передаче и хранении.

Фиг. 4 схематически показывает кодирование облака 10 точек в прямоугольном кадре 42 с использованием SMO 31, как описано на фиг. 3, согласно конкретному варианту осуществления настоящих принципов. Если координаты точки облака 10 точек соответствуют одной из точек сетки 30 по фиг. 3, преобразование этой точки представляет собой соответствующую точку в разложенной сетке 32, сохраненной в данных 33. В других случаях, координаты точки облака 10 точек принадлежат "прямоугольнику" сетки 30; т.е. координаты расположены между четырьмя из точек сетки 30. Преобразование представляет собой билинейную кусочную интерполяцию между соответствующими четырьмя точками проецируемой сетки 32. Проекция облака 10 точек с использованием SMO 21 формирует кадр 42, в котором полезная часть 13 шире полезной части кадра 12 по фиг. 1, в то время как "неиспользуемая" часть 14 меньше "неиспользуемой" части 14 кадра 12. Применение SMO 21 соответствует уравнению (уравнение 1), в котором M₀=SMO 21.

Кадр 42 кодируется и ассоциируется с данными 33. Кадр 42 может сжиматься с использованием стандартного алгоритма сжатия изображений или видео. Алгоритм сжатия может выбираться как "без потерь". В разновидности, ключевая карта может формироваться согласно кадру 42 и ассоциироваться с кадром 42 и данными 33. Ключевая карта представляет собой кадр, содержащий булевы значения (например, 0 или 1), при этом полезные пикселы задаются равными данному значению (например, 1), а неполезные пикселы задаются равными другому значению (например, 0). Обычно ключевые карты не сжимаются или сжимаются без потерь. Ассоциированные кодированные данные передаются в декодер в качестве одного или более потоков. В разновидности, ассоциированные кодированные данные сохраняются в локальном запоминающем устройстве или носителе хранения данных.

Фиг. 5 схематически иллюстрирует декодирование облака 50 точек из кадра 52, ассоциированного с данными 53, надлежащим образом соответствующими кадру 42 по фиг. 4 и данным 33 по фиг. 3. Кадр 52 и данные 53 получаются из источника. В настоящем документе, получение кадра и/или данных должно пониматься как прием данных из источника или считывание данных в источнике. Например, источник принадлежит набору, содержащему:

- локальное запоминающее устройство, например, запоминающее устройство для хранения видеоданных или RAM (или оперативное запоминающее устройство), флэш-память, ROM (или постоянное запоминающее устройство), жесткий диск;

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

- интерфейс связи, например, проводной интерфейс (например, шинный интерфейс, глобальный сетевой интерфейс, локальный сетевой интерфейс) или беспроводной интерфейс (к примеру, IEEE 802.11-интерфейс или Bluetooth®-интерфейс).

В разновидности, данные 53 и кадр 52 получаются из различных источников. Данные 53 соответствуют данным 33, вычисляемым так, как описано со ссылкой на фиг. 3. Сжатие и передача могут немного изменять их. В разновидности, используется способ сжатия без потерь, и обеспечивается безопасная передача, и данные 53 являются точно идентичными данным 33. Данные 53 содержат координаты K*L точек сетки 54. В разновидности, данные 33 нормализованы при кодировании. Согласно этой разновидности, координаты, содержащиеся в данных 53, выражаются в нормализованном пространстве. Оператор 51 обратного упрощенного преобразования (называется SMO^-1 51) вычисляется согласно данным 53 (т.е. согласно соответствующей разложенной сетке 54). Для нормализованных пиксельных координат (a, b), оценка SMO^-1 (a, b) сводится к билинейной кусочной интерполяции между четырьмя соседними значениями:

,,,,

где A=floor(Ka), и B=floor(Lb).

Результат применения SMO^-1 51 представляет собой двумерное облако 50 точек. SMO 31 имеет преимущества DMO 21 без его недостатков. Использование билинейной кусочной интерполяции на основе преобразования посредством DMO 21 регулярной сетки 30 формирует кадр 42, в котором использование пикселов оптимизируется (т.е. число неиспользуемых пикселов минимизируется; число точек облака 10 точек, преобразованных в идентичный пиксел, минимизируется). Различный SMO может быть ассоциирован с каждым облаком точек из последовательности облаков точек (например, видео). В разновидности, оптимизированный SMO может вычисляться для группы облаков точек из последовательности облаков точек. Одновременно, кодирование SMO 21 требует небольшого объема данных 33 в качестве матрицы K*L двумерных координат. На стороне декодирования, вычисление SMO^-1 из данных 53 является прямым, и его применение, билинейная кусочная интерполяция, является очень эффективным, требует ограниченных временных и обрабатывающих ресурсов.

Фиг. 7 иллюстрирует способ 70 для кодирования двумерных облаков точек согласно неограничивающему варианту осуществления настоящих принципов. На этапе 71, облако точек (или последовательность облаков точек) для кодирования получается из источника. Источник, например, может представлять собой локальное запоминающее устройство, интерфейс хранения данных или интерфейс связи. Двумерное облако точек может получаться посредством проекции n-мерного облака точек на поверхности, где n больше 2. В случае последовательности облаков точек, облака точек могут группироваться в качестве изображений, которые группируются в GOP для стандартных способов сжатия видео. Размер кадра (ширина и высота целевых кадров) определяется. Например, определенный размер кадра составляет стандартный размер изображения, такой как 640×480 (VGA) или 1920X1200 (широкоформатное). Определяется оператор плотного преобразования, который оптимизирует использование пикселов кадра определенного размера для облака точек (или группы облаков точек). Определенный DMO минимизирует число неиспользуемых пикселов.

На этапе 72, определенный DMO применяется к регулярной сетке K*L точек. Результат этого вычисления представляет собой разложенную сетку K*L преобразованных двумерных координат, которые сохраняются в матрице K*L пар чисел с плавающей запятой. В разновидности, эти координаты сохраняются в двух матрицах чисел с плавающей запятой. В другой разновидности, эти координаты преобразуются в кадре, и индексы преобразованных пикселов сохраняются в матрице пар целых чисел или в двух матрицах целых чисел. Эти координаты используются для того, чтобы параметризовать оператор упрощенного преобразования, который представляет собой билинейный кусочный интерполятор.

На этапе 73, параметрический SMO применяется к облаку точек (или к каждому из группы облаков точек) для кодирования. Кадр (или группа кадров) с размером, определенным на этапе 71, формируется. На этапе 74, сформированный кадр (или группа кадров) кодируется, например, с использованием стандартного способа сжатия изображений или видео, такого как MPEG 2 или H.264. Данные, представляющие матрицу (или матрицы) преобразованной сетки, вычисленной на этапе 72, кодируются. Кодированный кадр (или группа кадров) и данные ассоциированы в потоке. В разновидности, кодированные кадры и данные кодируются в различных потоках. Поток формируется на этом этапе и отправляется в назначение. Назначение принадлежит набору, содержащему, например:

- локальное запоминающее устройство, например, запоминающее устройство для хранения видеоданных или RAM (или оперативное запоминающее устройство), флэш-память, ROM (или постоянное запоминающее устройство), жесткий диск;

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

- интерфейс связи, например, проводной интерфейс (например, шинный интерфейс, глобальный сетевой интерфейс, локальный сетевой интерфейс) или беспроводной интерфейс (к примеру, IEEE 802.11-интерфейс или Bluetooth®-интерфейс).

Фиг. 8 иллюстрирует способ 80 декодирования двумерного облака точек из потока, содержащего кадр и данные, представляющие разложенную двумерную сетку. На этапе 81, кадр пикселов и ассоциированные данные, представляющие разложенную сетку (т.е. представляющие матрицу двумерных координат), получаются из источника. Источник принадлежит набору, содержащему локальное запоминающее устройство, интерфейс хранения данных и интерфейс связи. Координаты данных представляют разложенную сетку точек. Оператор обратного упрощенного преобразования (SMO^-1) параметризуется согласно координатам данных и размеру (ширине и высоте в пикселах) кадра. SMO^-1 представляет собой билинейный кусочный интерполятор. На этапе 83, параметрический SMO^-1 применяется к кадру, полученному на этапе 81. Эта заявка формирует двумерное облако точек. Идентичные данные могут быть ассоциированы с группой кадров, и идентичный SMO^-1 используется для того, чтобы декодировать кадры из группы кадров. Параметризация и применение такого оператора является простым и быстрым и требует ограниченных временных и обрабатывающих ресурсов для процессора или графической платы.

Фиг. 9 показывает примерную архитектуру устройства 90, которое может быть выполнено с возможностью реализовывать способ, описанный в связи с фиг. 7 и/или 8.

Устройство 90 содержит следующие элементы, которые соединены посредством шины 91 данных и адреса:

- микропроцессор 92 (или CPU), который представляет собой, например, DSP (или процессор цифровых сигналов);

- ROM 93 (или постоянное запоминающее устройство);

- RAM 94 (или оперативное запоминающее устройство);

- интерфейс 95 хранения данных;

- интерфейс 96 ввода-вывода для приема данных, которые следует передавать, из приложения; и

- источник питания, например, аккумулятор.

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

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

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

- локальное запоминающее устройство (93 или 94), например, запоминающее устройство для хранения видеоданных или RAM (или оперативное запоминающее устройство), флэш-память, ROM (или постоянное запоминающее устройство), жесткий диск;

- интерфейс (95) хранения данных, например, интерфейс с устройством хранения данных большой емкости, RAM, флэш-памятью, ROM, оптическим диском или магнитной подложкой;

- интерфейс (96) связи, например, проводной интерфейс (например, шинный интерфейс, глобальный сетевой интерфейс, локальный сетевой интерфейс) или беспроводной интерфейс (к примеру, IEEE 802.11-интерфейс или Bluetooth®- интерфейс); и

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

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

- локальное запоминающее устройство (93 или 94), например, запоминающее устройство для хранения видеоданных или RAM, флэш-память, жесткий диск;

- интерфейс (95) хранения данных, например, интерфейс с устройством хранения данных большой емкости, RAM, флэш-памятью, ROM, оптическим диском или магнитной подложкой; и

- интерфейс (96) связи, например, проводной интерфейс (например, шинный интерфейс (например, USB (или универсальную последовательную шину)), глобальный сетевой интерфейс, локальный сетевой интерфейс, интерфейс HDMI (мультимедийный интерфейс высокой четкости)) или беспроводной интерфейс (к примеру, IEEE 802.11-интерфейс, Wi-Fi®- или Bluetooth®-интерфейс).

В соответствии с примерами кодирования или кодера, поток битов, содержащий кадр и данные, представляющие матрицы двумерных координат, отправляется в назначение. В качестве примера, поток битов сохраняется в локальном или удаленном запоминающем устройстве, например, в запоминающем устройстве (94) для хранения видеоданных или RAM (94), на жестком диске (93). В разновидности, поток битов отправляется в интерфейс (95) хранения данных, например, в интерфейс с устройством хранения данных большой емкости, флэш-памятью, ROM, оптическим диском или магнитной подложкой, и/или передается по интерфейсу (96) связи, например, по интерфейсу с линией связи "точка-точка", шиной связи, линией связи "точка-многоточка" или широковещательной сетью.

В соответствии с примерами декодирования или декодера либо модуля рендеринга, поток битов получается из источника. В качестве примера, поток битов считывается из локального запоминающего устройства, например, запоминающего устройства (94) для хранения видеоданных, RAM (94), ROM (93), флэш-памяти (93) или жесткого диска (93). В разновидности, поток битов принимается из интерфейса (95) хранения данных, например, интерфейса с устройством хранения данных большой емкости, RAM, ROM, флэш-памятью, оптическим диском или магнитной подложкой, и/или принимается из интерфейса (95) связи, например, интерфейса с линией связи "точка-точка", шиной, линией связи "точка-многоточка" или широковещательной сетью.

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

- мобильное устройство;

- устройство связи;

- игровое устройство;

- планшет (или планшетный компьютер);

- переносной компьютер;

- фотокамеру;

- видеокамеру;

- кристалл кодирования;

- сервер (например, широковещательный сервер, сервер "видео по запросу" или веб-сервер).

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

- мобильное устройство;

- устройство связи;

- игровое устройство;

- абонентскую приставку;

- телевизор;

- планшет (или планшетный компьютер);

- переносной компьютер; и

- дисплей (такой как, например, HMD).

В соответствии с примером, проиллюстрированным на фиг. 10, в контексте передачи между двумя удаленными устройствами 101 и 102 (с типом устройства 90) по сети NET 100 связи, устройство 100 содержит средства, которые выполнены с возможностью реализовывать способ для кодирования облаков точек и формирования потока, как описано в связи с фиг. 7, и устройство 102 содержит средства, которые выполнены с возможностью реализовывать способ для декодирования облаков точек, как описано в связи с фиг. 8.

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

Фиг. 11 показывает пример варианта осуществления синтаксиса такого потока, когда данные передаются по протоколу передачи с коммутацией пакетов. Фиг. 11 показывает примерную структуру 110 потока битов. Структура содержит контейнер, который организует поток в независимых синтаксических элементах. Структура может содержать часть 111 заголовка, которая представляет собой набор данных, общий для каждого из синтаксических элементов потока. Например, часть заголовка содержит метаданные относительно синтаксических элементов, описывающие характер и роль каждого из них. Структура может содержать рабочие данные, содержащие синтаксические элементы 112 и 113, причем первый синтаксический элемент 112 задается относительно данных, представляющих разложенные сетки, например, в качестве матриц двумерных координат, и второй синтаксический элемент 113 задается относительно кадров, сформированных посредством оператора упрощенного преобразования. Данные, представляющие разложенную сетку, содержат информацию, ассоциирующую разложенную сетку, по меньшей мере, с одним кадром. Например, кадры идентифицируются посредством номера GOP и номера кадра в GOP. Номер GOP ассоциирован с разложенной сеткой SMO, который формирует кадры этой GOP.

Естественно, настоящее раскрытие сущности не ограничено вышеописанными вариантами осуществления.

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

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

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

Дополнительно, способы могут реализовываться посредством инструкций, выполняемых посредством процессора, и такие инструкции (и/или значения данных, сформированные посредством реализации) могут сохраняться на процессорночитаемом носителе, таком как, например, интегральная схема, программный носитель или другое устройство хранения данных, такое как, например, жесткий диск, компакт-диск (CD), оптический диск (такой как, например, DVD, зачастую называемый "универсальным цифровым диском" или "цифровым видеодиском"), оперативное запоминающее устройство (RAM) или постоянное запоминающее устройство (ROM). Инструкции могут формировать прикладную программу, материально осуществленную на процессорночитаемом носителе. Инструкции, например, могут находиться в аппаратных средствах, микропрограммном обеспечении, программном обеспечении или в комбинации. Инструкции могут содержаться, например, в операционной системе, в отдельном приложении или в комбинации означенного. Следовательно, процессор может характеризоваться, например, в качестве как устройства, выполненного с возможностью осуществлять процесс, так и устройства, которое включает в себя процессорночитаемый носитель (к примеру, устройство хранения данных), имеющий инструкции для выполнения процесса. Дополнительно, процессорночитаемый носитель может сохранять, в дополнение или вместо инструкций, значения данных, сформированные посредством реализации.

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

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

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

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

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

- декодируют облако точек посредством применения упомянутого оператора отмены преобразования к упомянутому кадру.

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

3. Способ кодирования двумерного облака точек в потоке битов, при этом способ содержит этапы, на которых:

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

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

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

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

5. Способ по одному из пп. 3, 4, в котором двумерное облако точек представляет собой проекцию n-мерного облака точек на поверхности, где n больше двух.

6. Устройство, содержащее запоминающее устройство, ассоциированное с по меньшей мере одним процессором, выполненное с возможностью:

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

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

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

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

8. Устройство, содержащее запоминающее устройство, ассоциированное с по меньшей мере одним процессором, выполненное с возможностью:

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

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

- формировать поток битов посредством кодирования упомянутого кадра, ассоциированного с упомянутой матрицей в потоке битов.

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

10. Устройство по одному из пп. 8, 9, в котором двумерное облако точек представляет собой проекцию n-мерного облака точек на поверхности, где n больше двух.

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

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

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

- при этом матрица ассоциирована с упомянутым по меньшей мере одним кадром.