СПОСОБ И УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ/ДЕКОДИРОВАНИЯ ГЕОМЕТРИЧЕСКИХ ДАННЫХ ОБЛАКА ТОЧЕК С ИСПОЛЬЗОВАНИЕМ РЕЖИМА АЗИМУТАЛЬНОГО КОДИРОВАНИЯ Российский патент 2024 года по МПК H04N19/597 H04N19/13 H04N19/167 H04N19/96 

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

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

Предпосылки создания изобретения

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

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

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

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

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

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

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

Облака точек могут формироваться при помощи устройств различных типов, например, массивов камер, датчиков глубины, лазеров (регистрирующих свет и измеряющих расстояние), сканерами, или могут формироваться при помощи компьютера (например, в послесъемочной обработке фильмов). В зависимости от сценария применения, облака точек могут иметь от тысяч до миллиардов точек, в случае применения в картографии. В сыром, «необработанном», виде облака точек требуют очень большого количества битов на каждую точку, по меньшей мере 12 битов на каждую декартову координату х, у и z, и опционально, дополнительные биты для атрибутов, к примеру, три раза по 10 битов для цвета.

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

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

До недавнего времени сжатие облаков точек (point cloud compression, РСС) не было востребовано на массовом потребительском рынке, и соответственно, не было стандартизированного кодека облаков точек. В 2017 году рабочая группа ISO/JCT1/SC29/WG11, также известная под именем «Группа экспертов по движущемуся изображению» (Moving Picture Experts Group, MPEG), инициировала работы по стандартизации сжатия облаков точек. В результате было предложено два стандарта, а именно:

MPEG-I часть 5 (ISO/IEC 23090-5), или сжатие облаков точек на основе видео (Video-based Point Cloud Compression, V-PCC);

MPEG-I часть 9 (ISO/IEC 23090-9), или сжатие облаков точек на основе геометрии (Geometry-based Point Cloud Compression, G-PCC).

Метод кодирования V-PCC сжимает облако точек путем выполнения множества проекций трехмерного объекта с получением двумерных участков (patches), которые упаковывают в изображение (или видео, при работе с движущимися облаками точек). Полученные изображения или видео затем сжимают с помощью существующих кодеков изображений/видео, что позволяет применять уже развернутые решения для работы с изображениями и видео. По своей природе метод V-PCC эффективен только для плотных и непрерывных облаков точек, поскольку кодеки изображений/видео не способны сжимать негладкие участки, которые могут возникать, например, в результате проецирования зарегистрированных лидаром данных с рассеянной геометрией.

Метод G-PCC кодирования имеет две схемы сжатия захваченных данных с рассеянной геометрией.

Первая схема основана на дереве занятости (октадерево), которое может быть представлением геометрии облака точек. Занятые узлы разбивают на подветви до тех пор, пока не будет достигнут заданный размер, при этом занятые листы дерева содержат местоположения точек в трехмерном пространстве. Листовой узел, как правило, представлен некоторым объемом, обычно кубом заданного размера в заданной точке трехмерного пространства. Центр этого объема может определять местоположение одной точки в трехмерном пространстве. Альтернативно, может использоваться режим прямого кодирования с логическим выводом (Inferred Direct Coding Mode, IDCM) для непосредственного кодирования местоположения точки в трехмерном пространстве в листовой узел дерева занятости. Режим прямого кодирования с логическим выводом (IDCM) может давать преимущества в случае рассеянных облаков точек за счет непосредственного кодирования местоположения одной или нескольких точек в узле неминимального размера путем прекращения построения дерева, если в узле присутствуют только изолированные точки.

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

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

Обозначим (x_P, y_P, z_P) координаты текущей точки Р. Когда выбранное азимутальное направление кодирование совпадает с осью х (или соответственно, у), кодирование координат выполняют следующим образом:

- Сначала кодируют биты координаты y_P (или соответственно, x_P),

- Затем кодируют биты координаты x_P (или соответственно y_P) при помощи контекстно-адаптивного двоичного энтропийного кодирования,

- и наконец энтропийно кодируют координату z_P текущей точки Р.

Первое кодирование y_P (или соответственно, x_P) может выполняться при помощи обхода энтропийного кодирования, т.е. биты представления y_P (или соответственно, x_P), просто помещают в битовый поток. Альтернативно, первое кодирование y_P (или соответственно, x_P) может выполняться при помощи контекстно-адаптированного двоичного энтропийного кодирования.

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

Настоящее изобретение не ограничено этим определением азимутального угла, к примеру, могут использоваться альтернативная ось начала угловых координат (ϕ = 0).

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

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

На шаге 101 в текущем (листовом) узле выбирают текущую точку Р с координатами (x_P, y_P, z_P) и выбирают направление азимутального кодирования (в данном случае, вдоль оси х), вдоль которого одна из координат точки (в данном случае, x_P) будет кодирована в битовый поток В при помощи контекстно-адаптивного двоичного энтропийного кодирования.

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

На шаге 103 для текущей точки Р определяют предсказанный азимутальный угол . Предсказанный азимутальный угол получают на основе азимутального угла (ближайшей) уже кодированной точки и множителя n элементарного азимутального шага Δϕ, отражающего сэмплирование при вращении датчика. Целое число n может быть выбрано так, чтобы получить:

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

Соответственно, получаем:

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

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

На шаге 105 интервал х разбивают на два полуинтервала: левый полуинтервал и второй полуинтервал. Определяют два угла Угол соответствует левому полуинтервалу, а угол - правому полуинтервалу.

На шаге 106 выбирают контекст, на основе предсказанного азимутального угла и двух углов:

К примеру, рассмотрим фиг.3, где показан пример точки, местоположение которой на интервале, параллельном оси х (выбранное направление азимутального кодирования), представлено тремя битами b_d (d=1,2,3), дающими одно из 8 возможных представлений точки. Первый бит (b1) равен 0, если кодируемая точка является одной из четырех точек слева, или равен 1, если кодируемая точка является одной из четырех точек справа.

Предсказанный азимутальный угол дает определенную прогнозную информацию о местоположении точки в том смысле, что поскольку предсказанный азимутальный угол указывает на левый полуинтервал, статистически более вероятно, что кодируемая точка принадлежит к левому полуинтервалу (т.е. b_d=0), чем к правому полуинтервалу (т.е. b_d=1). Информация, содержащаяся в предсказанном азимутальном угле может быть использована просто сравнением разностей углов и и затем соответствующим выбором контекста. Например:

- если , для энтропийного кодирования b_d выбирают первый контекст.

- в противном случае для энтропийного кодирования b_d выбирают второй контекст. На шаге 107 при помощи выбранного контекста в битовый поток В кодируют остающийся бит b_d наивысшего порядка для хр. Бит b_d указывает на то, что x_P расположена либо на левом полуинтервале (b_d=0) либо на правом полуинтервале (b_d=1).

На шаге 108 интервал х обновляют, заменяя на полуинтервал, к которому принадлежит x_P (на него указывает кодированный бит b_d). Если кодированный бит равен 0, это означает, что лежит на левом полуинтервале, и интервал х обновляют, заменяя его на левый полуинтервал. Если кодированный бит b_d равен 1, это означает, что x_P лежит на правом полуинтервале, и интервал х обновляют, заменяя его на правый полуинтервал.

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

Если кодирование x_P завершено (т.е., например, если длина интервала х меньше или равна минимальной длине интервала х), на шаге 109 в битовый поток В кодируют остающуюся координату z_P.

Если кодирование x_P не завершено, в цикле возвращаются к шагу 105 для кодирования следующего бита b_d+1 представления хр.

В текущей тестовой модели стандарта G-PCC, на шаге 105, два угла могут быть определены на основе точек представляющих середины (но не обязательно равных им) двух полуинтервалов. Простой способ вычисления этих двух углов с помощью формул арктангенсов показан на фиг.5.

Затраты на вычисление двух функций арктангенса могут быть слишком высокими на некоторых платформах.

Чтобы избежать вычислений двух арктангенсов при кодировании каждого из битов b_d координаты точки вдоль направления азимутального кодирования, в реализации тестовой модели G_PCC используют конкретные местоположения , показанные на фиг.6. А именно, - нижняя (левая) граница интервала х, а - середина интервала х. За счет этого обновленный (полу-) интервал может наследовать один из углов полного интервала х, в результате чего получают обновленный угол

За счет этого на каждой итерации (на каждой глубине d) для вычисления вычисляют только одну функцию арктангенса.

На шаге 106 способа 100 выбирают контексты, на основе предсказанного азимутального угла и двух углов для энтропийного кодирования координатных битов интервала х (или соответственно, интервала у). Предсказанный азимутальный угол дает определенную информацию предсказания о местоположении точки в том смысле, что поскольку предсказанный азимутальный угол указывает на левый полуинтервал, статистически более вероятно, что кодируемая точка принадлежит к левому полуинтервалу (т.е. b_d=0), чем к правому полуинтервалу (т.е. b_d=1).

В стандарте G-PCC определены 8 контекстов: 2 контекста в зависимости от того, одинаковы ли знаки или нет; 2 контекста в зависимости оттого, m > М или нет, и 2 контекста в зависимости оттого, М > 2m или m > 2М, или нет (не выполнено ни М > 2m, ни m > 2М).

На фиг.7 показана процедура выбора контекста G-PCC.

Интервал х показан здесь на глубине d, а углы соответственно, относятся к середине левого полуинтервала х и к середине правого полуинтервала х. Поскольку всего имеются 8 контекстов, каждый контекст может быть представлен тремя битами b₂b₁b₀ при этом каждый бит b_i указывает, выполнено или нет одно из трех приведенных выше условий. В соответствии с иллюстрацией фиг.7 каждый контекст представляет собой диапазон возможных местоположений, которому принадлежит предсказанный азимутальный угол в текущем интервале. Если предсказанный азимутальный угол указывает на первый диапазон местоположений, тогда контекст равен 010 и текущая точка с большей вероятностью будет находиться в левом полуинтервале х на текущей глубине d. Иными словами это означает, что вероятность равенства b_d=1, обозначенная prob(b_d=1), очень мала. Если предсказанный азимутальный угол указывает на самый правый, 8-й диапазон местоположений, тогда контекст равен 011 и текущая точка с большей вероятностью будет находиться в правом полуинтервале х на текущей глубине d. Это означает, что вероятность prob(b_d=1) очень высока.

Для кодирования бита b_d применяют контекстно-адаптивный двоичный энтропийный кодер (например, САВАС). Вероятности кодирования, связанные с каждым из 8 контекстов, естественным образом увеличиваются таким образом, что prob(b_d=1)<0,5 для контекста '010' и prob(b_d=1)>0.5 для контекста '011'.

В качестве общего правила, если принять за р вероятность того, что бит b_d равен 1, затраты на кодирование 1 равны -log2(р), затраты на кодирование 0 равны - log2(1 - р), при этом высокая вероятность адаптивного кодирования бита b_d позволяет сократить затраты на энтропийное кодирование до значения функции энтропии Шеннона для двоичного канала. Если предсказанный азимутальный угол дает хорошее предсказание интервала, которому принадлежит текущая точка (b_d=1 или b_d=0), то затраты на энтропийное кодирование бита b_d могут быть уменьшены.

В стандарте G-PCC предсказанный азимутальный угол используют для выбора контекстов для энтропийного кодирования бита b_d, совместно с углами и . Выбор контекстов, таким образом, зависит от «качества» предсказания, даваемого предсказанным азимутальным углом Качество понимают как способность предсказанного азимутального угла корректно предсказать, какому из полуинтервалов принадлежит текущая точка. То есть, эффективность энтропийного кодирования битов b_d зависит от качества предсказанного азимутального угла

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

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

Для ближнего узла (серый прямоугольник) расстояние г между датчиком и узлом очень мало по сравнению с размером узла. Следовательно, видимый угол ϕ₁, _{соответствующий интервалу х, велик, и получаем ϕ1 >> Δϕ. В этом случае точка внутри узла, потенциально, может быть зарегистрирована в нескольких (даже многих) положениях датчика, и произвольный выбор n в уравнении (1) вряд ли будет достоверно представлять, какое из положений датчика регистрировало текущую точку. При этом малое изменение координаты х текущей точки дает большое изменение азимутального угла ϕ, соответствующего точке, поскольку при малом значении радиуса r. Это означает, что азимутальный угол ϕ будет очень чувствителен к шуму. Предсказанный азимутальный угол в таком случае не обеспечивает стабильного прогнозирования.}

Для дальнего узла (черный прямоугольник) на фиг.8 расстояние г между датчиком и узлом так велико, что ϕ₂ << Δϕ, где ϕ₂ - видимый угол, соответствующий интервалу х.

Следовательно, биты b_d будут давать высокую точность (меньше Δϕ), которую нельзя эффективно прогнозировать при помощи предсказания азимутального угла определяемого с точностью до +/- Δϕ/2.

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

На фиг.9 показаны примеры низкокачественного предсказанного азимутального угла из-за слишком большого (серый прямоугольник) или слишком малого (черный прямоугольник) видимых углов (ϕ₁ или ϕ₂), соответствующих интервалу х для Δϕ. Два узла, показанные на фиг.9, имеют различные размеры (различную длину интервала х). Для большого узла (серый прямоугольник) видимый угол ϕ₁ так велик, что ϕ₁ >> Δϕ, это приводит к тем же проблемам, что и малое расстояние r. Для малого узла (черный прямоугольник) видимый угол ϕ₂ так мал, что ϕ₂ << Δϕ, и это приводит к тем же проблемам, что и большое расстояние r.

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

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

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

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

Если кратко, предложены способы, включающие режим азимутального кодирования, который формирует последовательность битов, для кодирования/декодирования координаты точки облака точек в направлении азимутального кодирования. С целью кодирования/декодирования битов в упомянутой последовательности битов выбирают контексты для зависящего от контекста энтропийного кодирования/декодирования. Выбор контекста основан на видимом угле (AA_d), соответствующем интервалу, параллельному направлению азимутального кодирования, представляющем координату точки облака точек. Видимый угол (AA_d) является оценкой угла интервала при наблюдении из датчика, зарегистрировавшего точку, на конкретной глубине. Выбранные контексты дают более точную статистику для вероятности битов b_d быть равными 0 или 1, за счет чего зависящее от контекста энтропийное кодирование точек в облаке точек может быть улучшено.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.6 проиллюстрирован пример реализации в случае определения двух углов в соответствии с существующим уровнем техники.

На фиг.7 показана процедура выбора контекста G-PCC в соответствии с существующим уровнем техники.

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

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

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

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

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

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

На фиг.14 проиллюстрирован пример реализации в случае вычисления середины интервала.

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

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

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

На фиг.18 показаны примеры трех значений отношения Δϕ/AA_d.

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

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

Описание примеров осуществления изобретения

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

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

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

При этом рассмотренные здесь аспекты настоящего изобретения не ограничены стандартами MPEG, например, частью 5 или частью 9 стандарта MPEG-I, относящегося к сжатию облаков точек, и могут применяться, к примеру, в других стандартах или рекомендациях, как существующих, так и будущих, а также в расширениях любых из подобных стандартов и рекомендаций (включая часть 5 и часть 9 MPEG-I). Если на обратное не указано прямо, или если для этого нет технических препятствий, аспекты, рассмотренные в настоящей заявке, могут применяться как по отдельности, так и совместно.

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

Способ 200 является усовершенствованием способа 100, показанного на фиг.1. Пример текущей точки Р выбирают в текущем (листовом) узле дерева занятости (шаг 101). Позиция точки вдоль выбранного направления азимутального кодирования представлена битами b_d, каждый из которых представляет местоположение x_P на интервале х, параллельном оси х. В приведенном ниже описании выбранное направление азимутального кодирования совпадает с осью х, однако заменой координаты х и оси х на у-координату и ось у, и наоборот, может быть получен альтернативный способ, в котором направление азимутального кодирования совпадает с осью у. Вторую координату точки (в данном случае, y_P) кодируют по противоположному направлению (в данном случае, оси у) (шаг 102). Для точки Р определяют предсказанный азимутальный угол (шаг 103). Инициализируют интервал х, параллельный оси х (шаг 104).

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

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

На шаге 202 интервал х разбивают на два полуинтервала: левый полуинтервал и второй полуинтервал. Интервал х является либо исходным интервалом х, полученным на шаге 104, либо интервалом х, который использовали для кодирования предыдущего бита b_d-1.

На шаге 203 левый угол соответствующий левому полуинтервалу, и правый угол, соответствующий правому полуинтервалу, интерполируют на основе по меньшей мере одного наследованного угла, соответствующего интервалу х.

На шаге 106 выбирают контекст, в соответствии с описанием способа 400 на фиг.16. На шаге 107 при помощи выбранного контекста в битовый поток В кодируют остающийся бит b_d наивысшего порядка для хр. Бит b_d указывает на то, что x_P расположена либо на левом полуинтервале (b_d=0), либо на правом полуинтервале (b_d=1).

В одном из примеров осуществления настоящего изобретения контекстно-адаптивное двоичное энтропийное кодирование является контекстно-адаптивным двоичным арифметическим кодированием (САВАС).

На шаге 108 интервал х обновляют, заменяя на полуинтервал, к которому принадлежит x_P (на него указывает кодированный бит). Если кодированный бит b_d равен 0, это означает, что x_P лежит на левом полуинтервале, и интервал х обновляют, заменяя его на левый полуинтервал. Если кодированный бит b_d равен 1, это означает, что x_P лежит на правом полуинтервале, и интервал х обновляют, заменяя его на правый полуинтервал.

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

Если кодирование x_P не завершено, в цикле возвращаются к шагу 202 для кодирования следующего бита b_d+1 представления x_P.

В одном из примеров осуществления шага 203 левый угол интерполируют, суммируя первый угол (ϕ_1,d) со взвешенной разностью второго угла (ϕ_2,d) и третьего угла (ϕ_3,d), а правый угол интерполируют, суммируя четвертый угол (ϕ_4,d) со взвешенной разностью пятого угла (ϕ_5,d) и шестого угла (ϕ_6,d).

Такая интерполяция может быть определена следующей системой:

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

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

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

В случае кодирования первого бита b_d=1 (первая итерация) наследованным углом будет угол полученный на шаге 201, а наследованный угол , будет соответствовать средней точке исходного интервала х (шаг 104).

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

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

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

где -половина длины исходного интервала х, s₀, (шаг 104), а - значение нижней границы исходного интервала х (шаг 104).

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

где - половина длины S_d-1 родительского интервала, а - значение нижней границы родительского интервала.

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

В еще одном из примеров осуществления шага 203, показанном на фиг.12, все углы в уравнении (2) являются наследованными углами, соответствующими родительскому интервалу. Углы интерполируют при помощи следующих выражений:

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

В случае кодирования первого бита b_d=1 (первая итерация) наследованным углом будет угол полученный на шаге 201, а наследованный угол будет соответствовать верхней границе исходного интервала х.

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

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

где - половина длины исходного интервала х,, (шаг 104), а - значение нижней границы исходного интервала х (шаг 104).

Если b_d-1=0, то левый полуинтервал будет интервалом х для следующей глубины d (следующая итерация), а угол затем вычисляют при помощи вычисления функции арктангенса.

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

где - половина длины исходного интервала х на глубине d-1, а - значение нижней границы интервала х на глубине d-1.

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

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

где - половина длины интервала х на глубине d-1, а - значение нижней границы интервала х на глубине d-1.

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

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

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

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

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

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

где углы являются наследованными углами, соответствующими интервалу х, согласно приведенному выше описанию в отношении фиг.11, 12 и 13.

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

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

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

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

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

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

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

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

Рассмотрим полуинтервал длины потенциальные точки расположены в местоположениях 0, 1, …, s'_d - 1, отсчитывая от нижней границы левого полуинтервала. Среднее положение центра левого полуинтервала, в таком случае определяется выражением:

Затем с помощью формулы арифметической прогрессии получаем:

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

Тот же принцип относится к параметру связанному с правым полуинтервалом.

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

В способах 200 и 300 выполняют несколько операций деления. Например,

- собственно интерполяция как деление на s'_d и s_d

- s_d+1 = s_d/2

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

Уравнение (4) преобразуется следующим образом:

где L_d - log2 длины s_d интервала, соответственно, значения L_d могут рекурсивно вычисляться следующим образом:

Значение вычисляют при помощи следующего выражения:

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

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

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

На шаге 301 координату точки (в данном случае, y_P) декодируют вдоль противоположного направления (в данном случае, оси у).

На шаге 103, предсказание азимутального угла определяют для точки Р. Инициализируют интервал х вдоль оси х (шаг 104). Используют азимутальный угол (ближайшей) уже декодированной точки, и декодер определяет множитель n элементарного азимутального шага. Альтернативно, множитель n может декодироваться из битового потока В.

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

На шаге 201 получают угол текущего узла при помощи уравнения (1).

Координата y_P декодирована из битового потока, a nodepos_x - известный параметр IDCM.

На шаге 202 интервал х разбивают на два полуинтервала: левый полуинтервал и второй полуинтервал. Интервал х является либо исходным интервалом х, инициализированным на шаге 104, либо интервалом х, который использовали для декодирования предыдущего бита b_d-1.

На шаге 203 левый угол соответствующий левому полуинтервалу, и правый угол, соответствующий правому полуинтервалу, интерполируют на основе по меньшей мере одного наследованного угла, соответствующего родительскому интервалу.

На шаге 106 выбирают контекст, в соответствии с описанием способа 400 на фиг.16. На шаге 302 при помощи выбранного контекста из битового потока В декодируют остающийся бит b_d наивысшего порядка для хр. Бит b_d указывает на то, что x_P расположена либо на левом полуинтервале (b_d=0), либо на правом полуинтервале (b_d=1).

В одном из примеров осуществления настоящего изобретения контекстно-адаптивное двоичное энтропийное декодирование представляет собой контекстно-адаптивное двоичное арифметическое кодирование (САВАС, Context-Adaptive Binary Arithmetic Coding).

На шаге 108 интервал х обновляют, заменяя на полуинтервал, к которому принадлежит хР (на него указывает декодированный бит).

Затем в способе выполняют проверку, завершено декодирование координаты x_P или нет.

Если декодирование x_P завершено, на шаге 303 из битового потока В декодируют оставшуюся координату z_P.

Если декодирование x_P не завершено, в цикле возвращаются к шагу 202 для декодирования следующего бита b_d+1 координаты x_P.

Примеры осуществления и вариации способа 200 применимы также к способу 300.

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

На шаге 410 вычисляют видимый угол AA_d, соответствующий интервалу х. Видимый угол AA_d является представлением интервала х при наблюдении из датчика, зарегистрировавшего текущую точку (текущий листовой узел) на конкретной глубине d. Соответственно, видимый угол AA_d уменьшается при обновлении интервала х от глубины d на глубину d+1 (шаг 108).

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

К примеру, угол может быть задан управлением (3), угол может быть получен следующим образом:

где s_d - длина интервала х на глубине d, - значение нижней границы интервала х на глубине d, и угол задан следующим выражением:

В одной и вариаций упомянутого примера осуществления шага 410 видимый угол AA_d вычисляют на основе углов

К примеру, где α - параметр, обеспечивающий пропорциональность угла AA_d разности углов К примеру, значение а может быть равно 1 или 2.

В еще одной из вариаций упомянутого примера осуществления шага 410 видимый угол AA_d вычисляют на основе углов

К примеру, где α - параметр, обеспечивающий пропорциональность угла AA_d разности углов К примеру, значение а может быть равно 1 или 2.

В еще одной из вариаций упомянутого примера осуществления шага 410 видимый угол AA_d вычисляют на основе углов

К примеру, Например, значение а может быть равно 1 или 2.

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

На шаге 420 выбирают контекст на основе относительных величин элементарного азимутального угла Δϕ и видимого угла AA_d.

В одном из примеров осуществления шага 420 относительные величины Δϕ и AA_d оценивают при помощи отношения Δϕ/AA_d.

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

Фактически, отношение Δϕ/AA_d зависит от длины интервала х, расстояния от текущего узла (текущей точки) до датчика, зарегистрировавшего точку, и значения элементарного азимутального угла Δϕ. Если текущий листовой узел сильно удален от датчика, или длина интервала, очень мала, т видимый угол AA_d будет так мал, что отношение Δϕ/AA_d становится много больше 1, и предсказанный азимутальный угол, соответствующий текущей точки, будет иметь низкое качество предсказания. С другой стороны, если текущий листовой узел очень близок к датчику, или длина интервала очень велика, то видимый угол очень велик, отношение Δϕ/AA_d становится много меньше 1, предсказанный азимутальный угол, соответствующий текущей точки, будет иметь низкое качество предсказания. Между этими значениями, когда отношение Δϕ/AA_d близко к 1, качество предсказания азимутального угла, соответствующего текущей точке, максимально.

В одной из вариаций упомянутого примера осуществления шага 420 контексты группируют по меньшей мере в два подмножества контекстов на основе диапазонов конкретных значений отношения Δϕ/AA_d, при этом выбор контекста включает выбор (подшаг 421) подмножества контекстов на основе диапазона конкретных значений отношения Δϕ/AA_d, а также выбор (подшаг 422) контекста из контекстов выбранного подмножества контекстов.

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

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

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

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

К примеру, на основе двух конкретных значений ТН1 и ТН2 отношения Δϕ/D_d могут быть заданы три подмножества С0, С1 и С2 контекстов.

Например, если Δϕ/AA_d < ТН1, то выбирают подмножество С0 контекстов.

то выбирают подмножество С1 контекстов, и если Δϕ/AA_d ≥ 1, выбирают подмножество С2 контекстов.

В одном из примеров, показанном на фиг.18, ТН 1=2/3 и ТН2=1. В случае (а) элементарный азимутальный угол Δϕ значительно меньше, чем видимый угол AA_d, отношение В этом случае может быть выбран первое подмножество контекстов, и это указывает на то, что предсказанный азимутальный угол находится в узком диапазоне внутри текущего узла. В случае (b) элементарный азимутальный угол Δϕ несколько меньше угла AA_d, для отношения выполняется неравенство в этом случае качество предсказания, обеспечиваемое предсказанным азимутальным углом , является наилучшим из всех трех случаев. В случае (с) видимый угол AA_d может быть так мал, что элементарный азимутальный угол Δϕ больше него, т.е. отношение Δϕ/AA_d > 1. В этом случае предсказанный азимутальный угол (полученный на основе элементарного азимутального угла Δϕ) не дает никакой релевантной информации о положении текущей точки в текущем узле.

В другом примере может применяться только одно конкретное значение, ТН1. Например, ТН 1=2/3.

В еще одном из примеров могут использоваться значения ТН1, ТН2 и ТН3. К примеру, ТН 1=1/3, ТН2=2/3 и ТН3=1.

В одном из примеров осуществления подшагов 421 и 422 контекст выбирают из таблицы ctxTable_T контекстов, в качестве первой записи имеющей индекс ctxSetIdx подмножества контекстов, указывающий на выбранное подмножество контекстов, и в качестве второй записи - индекс cxtIdx контекста, указывающий на выбранный контекст в выбранном подмножестве контекстов.

Контекст затем выбирают, выбирая (подшаг 421), сначала, первый индекс ctxSetIdx подмножества контекстов, исходя из диапазона конкретных значений и отношения Δϕ/AA_d, и затем, выбирая индекс cxtIdx контекста, указывающий на выбранный контекст в выбранном подмножестве контекстов.

К примеру, индекс cxtIdx контекста могут выбрать в соответствии с описанием в отношении фиг.7, на основе предсказанного азимутального угла и двух углов и

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

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

Примеры оборудования, которые могут составлять систему 500 в целом, или ее часть, включают персональные компьютеры, портативные компьютеры, смартфоны, планшетные компьютеры, цифровые мультимедийные телеприставки, цифровые телеприемники, персональные системы видеозаписи, подключенные к Интернету бытовые приборы, подключенные к Интернету автомобили и их соответствующие системы обработки данных, устанавливаемые на голове дисплейные устройства или очки с прозрачными дисплеями (head mounted display devices, HMD), проекторы (мультимедийные), среды виртуальной реальности CAVE (системы со множеством дисплеев), серверы, видеокодеры, видеодекодеры, постпроцессоры, обрабатывающие выходные данные видеодекодера, препроцессоры, подающие входные данные в видеокодер, веб-серверы, телеприставки или любые другие устройства для обработки облаков точек, видеоинформации, изображений или иные устройства связи. Элементы системы 500, по отдельности или в комбинации, могут быть реализованы в одной интегральной схеме (integrated circuit, IC), нескольких интегральные схемах и/или на дискретных компонентах. К примеру, по меньшей мере в одном из вариантов осуществления настоящего изобретения элементы обработки данных или кодера/декодера в системе 500 могут быть распределены среди нескольких интегральных схем и/или дискретных компонентов. В различных вариантах осуществления настоящего изобретения система 500 может быть соединена, с возможностью связи, с другими подобными системами или с другими электронными устройствами, например, при помощи шины связи или при помощи специальных портов ввода и/или вывода.

Система 500 может включать по меньшей мере один процессор 510, сконфигурированный для исполнения инструкций, загружаемых в него для реализации, к примеру, различных аспектов, описанных в настоящей заявке. Процессор 510 может иметь встроенную память, интерфейс ввода-вывода и различные иные схемы, известные на существующем уровне техники. Система 500 может включать по меньшей мере одну память 520 (к примеру, энергозависимое запоминающее устройство и/или энергонезависимое запоминающее устройство). Система 500 может включать устройство 540 хранения, которое может включать энергонезависимую память и/или энергозависимую память, включая, без ограничения перечисленным, электрически перепрограммируемую память «только для чтения» (Electrically Erasable Programmable Read-Only Memory, EEPROM), память «только для чтения» (Read-Only Memory, ROM), программируемую память «только для чтения» (Programmable Read-Only Memory, PROM), память с произвольным доступом (Random Access Memory, RAM), динамическую память с произвольным доступом (Dynamic Random-Access Memory, DRAM), статическую память с произвольным доступом (Static Random-Access Memory, SRAM), флэш-память, привод магнитных дисков и/или привод оптических дисков. Устройство 540 хранения в качестве неограничивающих примеров может включать внутреннее устройство хранения, подключаемое устройство хранения и/или доступное по сети устройство хранения.

Система 500 может включать модуль 530 кодера/декодера, сконфигурированный, например, для обработки данных с целью получения кодированных/декодированных геометрических данных облака точек, при этом модуль 530 кодера/декодера может иметь собственные процессор и память. Модуль 530 кодера/декодера может представлять собой модуль (или модули), входящие в состав устройства для выполнения функций кодирования и/или декодирования. Как известно, устройство может содержать модуль кодирования, модуль декодирования или оба модуля одновременно. При этом модуль 530 кодера/декодера 330 может быть реализован в виде отдельного элемента 500 или может быть встроен в процессор 510 в виде комбинации аппаратного и программного обеспечения, что известных специалистам в данной области техники.

Программный код, загружаемый в процессор 510 или кодер/декодер 530 для выполнения различных аспектов, описанных в настоящей заявке, может храниться в устройстве 540 хранения и впоследствии загружаться в память 520 для исполнения процессором 510. В соответствии с различными вариантами осуществления настоящего изобретения одно или более из следующего: процессор 510, память 520, устройство 540 хранения, модуль 530 кодера/декодера могут хранить один или более различных объектов при выполнении процедур, описанных в настоящей заявки. Такие хранимые объекты включают, без ограничения перечисленным, кадр облака точек, геометрию/атрибуты кодируемых/декодируемых видео/изображений или фрагменты геометрии/атрибутов кодируемых/декодируемых видео/изображений, битовый поток, матрицы, переменные и промежуточные или окончательные результаты обработки уравнений, формул, операций и логики выполнения операций.

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

В других вариантах осуществления настоящего изобретения, однако, для одной или более из подобных функций может применяться память, внешняя по отношению к устройству обработки данных (например, таким устройством обработки данных может быть процессор 510 или модуль 530 кодера/декодера). Внешней памятью может быть память 520 и/или устройство 540 хранения, к примеру, динамическая энергозависимая память и/или энергонезависимая флэш-память. В некоторых из вариантов осуществления настоящего изобретения внешняя энергонезависимая флэш-память может использоваться для хранения операционной системы телевизора. По меньшей мере в одном варианте осуществления настоящего изобретения быстрая внешняя динамическая энергозависимая память, например, RAM, может использоваться в качестве рабочей памяти для операций кодирования и декодирования видео, к примеру, для кодирования по стандартам MPEG-2 часть 2 (также называемому Рекомендация Н.262 ITU-T и ISO/IEC 13818-2, также называемому MPEG-2 Video), HEVC (High Efficiency Video coding, «высокоэффективное видеокодирование»), VVC (Versatile Video Coding, «универсальное видеокодирование»), или стандарту MPEG-I часть 5 или 9.

Входные данные в элементы системы 500 могут подаваться при помощи различных устройств ввода, показанных в блоке 590. Такие устройства ввода включают, без ограничения перечисленным: (i) радиочастотный узел, который может принимать радиочастотный сигнал, передаваемый, например, по радиоинтерфейсу передатчиком, (ii) входной терминал композитного интерфейса, (iii) входной терминал USB и/или (iv) входной терминал HDMI.

В различных примерах осуществления настоящего изобретения устройства ввода в блоке 590 могут иметь соответствующие связанные с ними элементы обработки входных данных, известные на существующем уровне техники. К примеру, радиочастотный узел может быть связан с элементами, необходимым для следующего: (i) выбор необходимой частоты (это также называют выделением сигнала, или ограничением полосы частот до заданной полосы), (ii) преобразование выделенного сигнала с понижением частоты, (iii) повторное ограничение полосы частоты до более узкой для выделения (к примеру) полосы частот сигнала, которая может, в некоторых из вариантов осуществления настоящего изобретения, называться каналом, (iv) демодуляция преобразованного с понижением частоты и ограниченного по полосе частот сигнала, (v) выполнение исправления ошибок, и (vi) демультиплексирование для выделения требуемого потока пакетов данных. Радиочастотный узел в различных вариантах осуществления настоящего изобретения может включать один или более элементов для выполнения таких функций, к примеру, селекторы частоты, селекторы сигнала, ограничители полосы частот, селекторы канала, фильтры, понижающие преобразователи, демодуляторы, корректоры ошибок и демультиплексоры. Радиочастотный узел может включать устройство настройки, которое выполняет некоторые из подобных функций, включая, например, понижающее преобразование принятого сигнала до пониженной частоты (к примеру, промежуточной частоты или до близкой к основной полосе частот) или до основной полосы частот.

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

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

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

При этом, упомянутые терминалы USB и/или HDMI могут содержать соответствующие интерфейсные процессоры для соединения системы 500 с другими электронными устройствами по соединениям USB и/или HDMI. Нужно понимать, что различные аспекты обработки входных данных, к примеру, коррекция ошибок с помощью кодов Рида-Соломона, могут быть реализованы при помощи отдельной интегральной схемы обработки ввода или при внутри процессора 510, в зависимости от требований. Аналогично, аспекты обработки интерфейсов USB или HDMI могут быть реализованы в отдельных интерфейсных интегральных схемах или внутри процессора 510 в зависимости от требований. Демодулированный, с исправленными ошибками и демультиплексированный поток может быть подан в различные обрабатывающие элементы, включающие, например, процессор 510 и кодер/декодер 530, функционирующие в сочетании с элементами памяти и хранения, для обработки потока данных, необходимой для отображения на устройстве вывода.

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

Система 500 может включать интерфейс 550 связи, которые обеспечивает возможность связи с другими устройствами по каналу 500 связи. Интерфейс 550 связи может включать, без ограничения перечисленным, приемопередатчик, сконфигурированный для передачи и приема данных по каналу 600 связи. Интерфейс 550 связи может включать, без ограничения перечисленным, модем или сетевую карту, при этом канал 600 связи может быть реализован, например, в проводной и/или беспроводной среде передачи.

Поток данных может передаваться в систему 500, в различных вариантах осуществления настоящего изобретения, с помощью сети Wi-Fi, например, по стандарту IEEE 802.11.Сигнал Wi-Fi в таких вариантах осуществления настоящего изобретения может приниматься по каналу 600 связи и интерфейсу 550 связи, которые приспособлены для связи по стандарту Wi-Fi. Канал 500 связи в таких вариантах осуществления настоящего изобретения, как правило, может быть связан с точкой доступа или маршрутизатором, который представляет доступ к внешним сетям, включая Интернет, давая возможность использовать стриминговые приложения и иную связь, поставляемую поверх сетевых услуг оператора связи (over-the-top, ОТТ).

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

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

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

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

Система 500 может подавать выходной сигнал в различные устройства вывода, включая дисплей 700, динамики 800 и иные периферийные устройства 900. Упомянутые иные периферийные устройства 900 могут включать в различных примерах осуществления настоящего изобретения одно или более из следующего: автономный DVR, проигрыватель дисков, стереосистему, систему освещения, а также другие устройства, выполняющие свои функции на основе выходных данных системы 500.

В различных вариантах осуществления настоящего изобретения между системой 500 и дисплеем 700, динамиками 800 и иными периферийными устройствами 900 могут передаваться сигналы управления при помощи, например, такой сигнализации, как AV Link (Audio/Video Link, «аудио/видео линия»), СЕС (Consumer Electronics Control, «управление бытовой электроникой») или иных протоколов связи, обеспечивающих возможность межустройственного (device-to-device) управления с вмешательством пользователя или без него.

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

Альтернативно, устройства вывода могут быть соединены с системой 500 при помощи канала 600 связи через интерфейс 550 связи. Дисплей 700 и динамики 800 могут быть объединены в одном блоке с остальными компонентами системы 500 в составе электронного устройства, например, телевизора.

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

Дисплей 700 и динамики 800, альтернативном, могут быть отдельными от одного или более других компонентов, к примеру, если радиочастотный узел блок 590 ввода является частью отдельной телеприставки. В тех вариантах осуществления настоящего изобретения, где дисплей 700 и динамики 800 являются внешними компонентами, выходной сигнал может подаваться по специальным выходным включая, к примеру, порты HDMI, порты USB или порты СОМР.

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

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

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

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

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

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

портативная компьютерная дискета, жесткий диск, память "только для чтения" (ROM), перезаписываемая память "только для чтения" (erasable programmable read-only memory, EPROM) или Flash-память, портативная память "только для чтения" на компакт-диске (compact disc read-only memory, CD-ROM), оптическое запоминающее устройство, магнитное запоминающее устройство или любая комбинация перечисленного.

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

Инструкции могут, к примеру, иметь форму аппаратного обеспечения, микропрограммного обеспечения, программного обеспечения или их комбинации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области кодирования и декодирования геометрических данных облака точек. Технический результат заключается в улучшении эффективности основанного на контексте энтропийного кодирования, используемого в режиме азимутального кодирования. Такой результат достигается за счет улучшения выбора контекстов, используемых для энтропийного кодирования битов b_d. Выбор контекста основан на видимом угле (AA_d), соответствующем интервалу вдоль направления азимутального кодирования и представляющем координату точки облака точек. Видимый угол (AA_d) является оценкой угла интервала при наблюдении из датчика, зарегистрировавшего точку, на конкретной глубине. 6 н. и 18 з.п. ф-лы, 19 ил.

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

разбиение (202) интервала, к которому принадлежит координата точки, на левый полуинтервал и правый полуинтервал;

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

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

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

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

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

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

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

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

7. Способ по п. 1, в котором контекст выбирают на основе отношения элементарного азимутального угла () к видимому углу ().

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

выбор (421) подмножества контекстов на основе диапазона конкретных значений упомянутого отношения; и

выбор (422) контекста из выбранного подмножества контекстов.

9. Способ по п. 8, в котором выбор (422) контекста из выбранного подмножества контекстов зависит от предсказанного азимутального угла (, соответствующего точке, левого угла (), соответствующего левому полуинтервалу, и правого угла (), соответствующего правому полуинтервалу.

10. Способ по п. 8 или 9, в котором контекст выбирают из таблицы () контекстов, имеющей в качестве первой записи индекс (ctxSetIdx) подмножества контекстов, указывающий выбранное подмножество контекстов, и в качестве второй записи – индекс контекста (cxtIdx), указывающий выбранный контекст в выбранном подмножестве контекстов.

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

разбиение (202) интервала, к которому принадлежит координата точки, на левый полуинтервал и правый полуинтервал;

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

контекстно-адаптивное двоичное энтропийное декодирование (302) бита (b_d) из битового потока на основе выбранного контекста, при этом декодированный бит (b_d) указывает, какому из двух полуинтервалов принадлежит координата точки,

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

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

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

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

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

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

17. Способ по п. 11, в котором контекст выбирают на основе отношения элементарного азимутального угла () к видимому углу ().

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

выбор (421) подмножества контекстов на основе диапазона конкретных значений упомянутого отношения; и

выбор (422) контекста из выбранного подмножества контекстов.

19. Способ по п. 18, в котором выбор (422) контекста из выбранного подмножества контекстов зависит от предсказанного азимутального угла (, соответствующего точке, левого угла (), соответствующего левому полуинтервалу, и правого угла (), соответствующего правому полуинтервалу.

20. Способ по п. 18 или 19, в котором контекст выбирают из таблицы () контекстов, имеющей в качестве первой записи индекс (ctxSetIdx) подмножества контекстов, указывающий выбранное подмножество контекстов, и в качестве второй записи – индекс контекста (cxtIdx), указывающий выбранный контекст в выбранном подмножестве контекстов.

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

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

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

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

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

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

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

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

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

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

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

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