СПОСОБ И УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ/ДЕКОДИРОВАНИЯ ГЕОМЕТРИЧЕСКИХ ДАННЫХ ОБЛАКА ТОЧЕК, ЗАХВАЧЕННЫХ ПРИ ПОМОЩИ ВРАЩАЮЩЕЙСЯ ИЗМЕРИТЕЛЬНОЙ ГОЛОВКИ Российский патент 2024 года по МПК G06T9/00 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В одном из вариантов осуществления настоящего изобретения первые данные получают на основе аппроксимации 2π/(r_dec*α*ΔIϕ), где r_dec - декодированный радиус, α - коэффициент масштабирования, больший или равный 1, а ΔIϕ соответствует внутренней точности азимутальных углов.

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

В одном из вариантов осуществления настоящего изобретения аппроксимацию получают путем нахождения, для элементарного шага азимутального угла, наибольшего множителя, представляющего собой степень двойки, который меньше, чем 2π/(r_dec*α*ΔIϕ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг. 7 проиллюстрирован недостаток метода G-PCC в соответствии по меньшей мере с одним из вариантов осуществления.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Облако точек представляет собой множество точек, расположенных в трехмерном (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 имеет две схемы сжатия захваченных геометрических данных.

Первая схема основана на дереве занятости, которое может быть, локально, любым из следующих типов, представляющих геометрию облака точек: октадеревом, квадродеревом или бинарным деревом. Занятые узлы разбивают на подветви до тех пор, пока не будет достигнут заданный размер, и занятые листы дерева содержат местоположения точек в трехмерном пространстве, как правило, в центре этих узлов. Информацию о занятости передают при помощи флагов занятости, сигнализирующих о состоянии занятости каждого из дочерних узлов любого узла. С помощью методов предсказания на основе соседей в случае плотных облаков точек может быть достигнут высокий уровень сжатия флагов занятости. Рассеянные облака точек также могут бытьобработаны, при помощи непосредственного кодирования положения точки в узле с неминимальным размером, и остановки построения дерева, когда в узлах находятся только изолированные точки; такой метод называют методом прямого кодирования (Direct Coding Mode, DCM).

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

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

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

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

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

К примеру, в технологии G-PCC применяют угол возвышения (относительно горизонтальной поверхности земли) для захвата вращающейся измерительной головкой, в соответствии с иллюстрацией фиг. 1 и фиг. 2. Вращающаяся измерительная головка 10 содержит набор датчиков 11 (например, лазеры), причем в данном примере показаны пять датчиков. Вращающаяся измерительная головка 10 может вращаться вокруг вертикальной оси z для захвата геометрических данных физических объектов, т.е. местоположений точек облака точек в трехмерном пространстве. Захваченные вращающейся измерительной головкой геометрические данные затем представляют в сферических координатах (r_3D, ϕ, θ), где r_3D ^_ расстояние от точки Р до центра вращающейся измерительной головки, ϕ - азимутальный угол поворота головки относительно начала координат, а θ - угол возвышения датчика с порядковым номером k во вращающейся измерительной головке относительно опорной горизонтальной плоскости (в данном случае, оси у). Порядковый номер k угла возвышения может быть, например, углом возвышения датчика k, или k-м положением датчика, если единственный датчик последовательно проводит измерения для каждого из последовательных углов возвышения.

На фиг. 3 показано равномерное распределение по азимутальному углу, наблюдаемое в геометрических данных, захваченных вращающейся измерительной головкой. Упомянутая равномерность используется в методе G-PCC для получения квазиодномерного представления облака точек, в котором, с точностью до шума, только радиус r_3D принадлежит непрерывному диапазону значений, тогда как углы ϕ и θ принимают только набор дискретных значений где I - количество азимутальных углов, используемых для захвата точек, and где К - количество датчиков во вращающейся измерительной головке 10. Фактически, в технологии G-PCC рассеянные геометрические данные, захваченные вращающейся измерительной головкой, представляют на двумерной плоскости дискретных углов (ϕ, θ), в соответствии с иллюстрацией фиг. 3, вместе со значением радиуса r_3D для каждой точки.

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

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

В дереве предсказания непосредственно кодируют первую версию местоположения текущей точки Р в сферических координатах (r, ϕ, ), где r проекция радиуса на горизонтальную плоскость ху, показанная на фиг. 4 как r_2D, с использованием квазиодномерного характера этого координатного пространства. Затем сферические координаты (r, ϕ, θ) преобразуют в трехмерные декартовы координаты (x,y,z), и разность (остаток) xyz кодируют для компенсации ошибок при преобразовании координат, аппроксимации угла возвышения и азимутального угла, а также возможного шума.

На фиг. 5 показан кодер облака точек, который аналогичен кодеру G-PCC, основанному на дереве предсказания.

Сначала декартовы координаты (x,y,z) точек в облаке точек преобразуют в сферические координаты (r, ϕ, θ) при помощи (r, ϕ, θ)=C2A(x,y,z).

Функция преобразования частично определена следующим образом:

где round() - операция округления до ближайшего целого, - функция извлечения квадратного корня, и atan2(y,x) - функция арктангенса, взятая от у/х. ΔIr и ΔIϕ - внутренние точности радиусов и азимутальных углов соответственно. Они как правило равны их соответствующим шагам квантования, т.е. ΔIϕ=Δϕ и ΔIr=Δr, где

и

Δr=2^М* элементарный шаг квантования,

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

Кодер может вычислять Δϕ и Δr путем минимизации затрат (например, количества битов) на кодирование представления в сферических координатах и разности xyz в декартовом пространстве.

Для простоты далее будем считать Δϕ=ΔIϕ и Δr=ΔIr.

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

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

Разность сферических координат, (r_res, ϕ_res, θ_res), между сферическими координатами (r, ϕ, θ) и предсказанными сферическими координатами, полученными на основе предсказания PR_n, затем получают следующим образом:

где (r_n, ϕ_n, θ_n) - предсказанный радиус, предсказанный азимутальный угол и предсказанный угол возвышения, полученные на основе предсказания, которое было выбрано из списка кандидатных предсказаний PR₀, PR₁ PR₂ и PR₃, a m- целое количество элементарных шагов азимутального угла, добавляемое к предсказанию азимутального угла.

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

Элементарный шаг азимутального угла, ϕ_step, или количество измерений на каждый оборот головки, NP, кодируют в битовый поток В, например, в наборе параметров геометрии. Альтернативно, NP может быть параметром кодека, который может сигнализируют в битовом потоке, a ϕ_step одинаковым образом вычисляться в кодере и декодере.

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

Разность (r_res, ϕ_res, θ_res) сферических координат может квантоваться (Q), с получением квантованной разности Q(r_res, ϕ_res, θ_res) сферических координат. Квантованная разность Q(r_res, ϕ_res, θ_res) сферических координат может кодироваться в битовый поток В.

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

Индекс n предсказания указывает на предсказание, выбранное из списка кандидатных предсказаний.

Кандидатное предсказание PR₀ может быть равно (r_min, ϕ_0, θ₀), где r_min - минимальное значение радиуса (заданное в наборе параметров геометрии), а ϕ₀ и θ₀ равны 0, если текущий узел (текущая точка Р) не имеет родительского узла, или его азимутальный угол и угол возвышения равны углам точки, соответствующей родительскому узлу.

Второе кандидатное предсказание PR1 может быть равно (r₀, ϕ₀, θ₀), где r₀, ϕ₀ и θ₀, соответственно, радиус, азимутальный угол и угол возвышения точки, соответствующей родительскому узлу для текущего узла.

Еще одно кандидатное предсказание PR2 может быть равно линейному предсказанию радиуса, азимутального угла и угла возвышения с использованием радиуса, азимутального угла и угла возвышения, (r₀, ϕ₀, θ₀), точки, соответствующей родительскомуузлу для текущего узла, и радиуса, азимутального угла и угла возвышения, (r₁, ϕ₁, θ₁), относящегося к прародительскому узлу.

Еще одно кандидатное предсказание PR3 может быть равно линейному предсказанию радиуса, азимутального угла и угла возвышения с использованием радиуса, азимутального угла и угла возвышения, (r₀, ϕ₀, θ₀), точки, соответствующей родительскому узлу для текущего узла, радиуса, азимутального угла и угла возвышения, (r₁, ϕ₁, θ₁, относящегося к прародительскому узлу, и радиуса, азимутального угла и угла возвышения (r₂, ϕ₂, θ₂) точки, относящейся к пра-прародительскому узлу.

Предсказанные декартовы координаты (x_pred, y_pred, z_pred) получают обратным преобразованием восстановленных сферических координат (r_pred, ϕ_pred, θ_pred) следующим образом:

где декодированные сферические координаты (r_dec, ϕ_dec, θ_dec), в случае декодера, могут быть заданы следующим образом:

где (r_res, _dec, ϕ_res, _dec, θ_res, _dec) - декодированная разность сферических координат, в случае декодера.

Декодированная разность сферических координат, (r_res, _dec, ϕ_res, _dec, θ_res, _dec) может быть результатом обратного квантования (IQ) квантованной разности сферических координат, Q(r_res, ϕ_res, θ_res).

В G-PCC не выполняют квантования разности сферических координат, и декодированные сферические координаты (r_res, _dec, ϕ_res, _dec, θ_res, _dec) равны разности (r_res, ϕ_res, θ_res) сферических координат. Декодированные сферические координаты (r_dec, ϕ_dec, θ_dec) в этом случае равны сферическим координатам (r, ϕ, θ).

Обратное преобразование декодированных сферических координат (r_dec, ϕ_dec,θ_dec) может быть определено следующим образом:

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

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

Разность (x_res,y_res,z_res) декартовых координат квантуют (Q), и квантованную разность Q(x_res,y_res,z_res) декартовых координат кодируют в битовый поток.

Разность декартовых координат может кодироваться без потерь, когда шаги квантования x,y,z равны точности исходных точек (как правило, 1), или кодироваться с потерями, когда шаги квантования больше, чем точность исходных точек (как правило, шаги квантования больше 1).

Декодированные декартовы координаты в декодере определяют следующим образом:

- обратно квантованная разность декартовых координат.

Эти декодированные декартовы координаты (x_dec,y_dec,z_dec) могут использоваться в кодере, например, для упорядочивания (декодированных) точек перед кодированием атрибутов.

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

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

Декодированная разность (r_res, _dec, ϕ_res, _dec, θ_res, _dec) сферических координат может быть получена декодированием разности (r_res, ϕ_res, θ_res) сферических координат из битового потока В.

Квантованная разность сферических координат, Q(r_res, ϕ_res, θ_res), может быть декодирована из битового потока В. Квантованную разность Q(r_res, ϕ_res, θ_res) сферических координат обратно квантуют для получения декодированной разности (r_res, _dec, ϕ_res, _dec, θ_res, _dec) сферических координат.

Декодированные сферические координаты (r_res, ϕ_res, θ_res) получают сложением декодированной разности сферических координат (r_res, _dec, ϕ_res, _dec, θ_res, _dec) и предсказанных сферических координат (r_pred, ϕ_pred, θ_pred) в соответствии с уравнением (4).

Предсказанные декартовы координаты (x_pred, y_pred, z_pred) получают обратным преобразованием восстановленных сферических координат (r_dec, ϕ_dec, θ_dec) в соответствии с уравнением (3).

Квантованную разность Q(x_res,y_res,z_res) декартовых координат декодируют из битового потока В и обратно квантуют, получая обратно квантованные декартовы координаты IQ(Q(x_res,y_res,z_res)). Декодированные декартовы координаты (x_dec,y_dec,z_dec) заданы уравнением (5).

В G-PCC уравнения (1) и (4) используют для предсказания азимутального угла ϕ и для получения декодированного азимутального угла ϕ_dec, а уравнение (5) используют для декодирования декартовых координат точки.

При этом, когда радиус достаточно мал (т.е. когда точки достаточно близки к датчику лидара), возможна ситуация, когда использование различных значений ‘m’ в уравнениях (1) и (4) (например, m+1 или m-1) даст результатом одинаковые (квантованные) значения разности декартовых координат.

Этот недостаток G-PCC показан на фиг. 7. В примере на фиг. 7 точка декодируемого облака точек (черный кружок) принадлежит квадрату в декартовом пространстве ху. Квадраты соответствуют равномерному выполнению отсчетов по осям х и у в пространстве декартовых координат. Размер квадратов зависит от точности входного облака точек в случае сжатия без потерь, или частично зависит от шага квантования в случае сжатия с потерями. Угловые секторы размером представляют собой области, проходимые датчиком во вращающейся измерительной головке 10 между двумя захватами. В данном примере точка принадлежит квадрату, рассеченному двумя лазерными лучами b1 и b2, соответствующим двум ориентациям датчика для двух последовательныхизмерений/захватов, выполненных с одним углом возвышения. Соответственно, квадрат перекрыт тремя секторами углов, s₀, s₁ и s₂. В этом случае для вычисления предсказанного азимутального угла (уравнения (1) или (4)) число ‘m’ должно быть выбрано из двух значений, mi (относящегося к лазерному лучу b1) и m₂ (относящегося к лазерному лучу b2). Возможность кодирования нескольких (в данном случае двух, m₁ и m₂) различных значений m для одной точки облака точек может приводить к неоптимальному кодированию количества m (например, m₁), по сравнению с кодированием другого количества т, которое могло бы быть получено, если ϕ_step было бы достаточно велико для того, чтобы квадрат, где лежит точка, пересекал только один лазерный луч. Следовательно, по сравнению с радиусом точки (т.е. расстоянием от датчика), точность угловых измерения, получаемая при использовании элементарного шага ϕ_step азимутального угла, будет слишком велика по сравнению с точностью выходных декартовых координат. Соответственно, возможность кодировать несколько различных количеств означает неоптимальность схемы кодирования, и существует возможность улучшить сжатие.

Для улучшения метода G-PCC необходимо более совершенное кодирование количества m элементарных шагов азимутального угла.

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

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

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

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

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

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

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

На фиг. 8 проиллюстрирована блок-схема алгоритма для способа 100 кодирования облака точек, представляющих физический объект, в соответствии по меньшей мере с одним из вариантов осуществления настоящего изобретения. На шаге 110 элементарный шаг ϕ_step азимутального угла может быть определен при помощи уравнения (2). На шаге 120 декодированный радиус r_dec точки облака точек может быть получен при помощи уравнения (4):

где r_n предсказанный радиус, полученный с использованием предсказания PR_n. На шаге 130 масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла равен первым данным D1, большим, чем элементарный шаг ϕ_step азимутального угла, когда вторые данные D2, зависящие от декодированного радиуса r_dec, строго меньше порога ТН, или, в противном случае, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла равен элементарному шагу ϕ_step азимутального угла.

На шаге 140 количество m_s масштабированных элементарных шагов азимутального угла кодируют в битовый поток В. Количество m_s получают на основе азимутального угла ϕ точки, предсказания азимутального угла ϕ_n и масштабированного элементарного шага S(ϕ_step, r_dec) азимутального угла:

На шаге 150 получают предсказанный азимутальный угол ϕ_pred, на основе масштабированного элементарного шага S(ϕ_step, r_dec) азимутального угла и количества m_s:

На шаге 160 разность ϕ_res азимутального угла кодируют в битовый поток В. Разность ϕ_res азимутального угла может быть вычислена как разность между азимутальным углом ϕ точки и предсказанием ϕ_pred азимутального угла.

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

На шаге 210 из битового потока декодируют элементарный шаг ϕ_step азимутального угла или количество NP измерений на поворот головки, например, из набора параметров геометрии.

На шаге 220 из битового потока декодируют разность r_res, _dec радиуса. Затем может быть получен декодированный радиус при помощи уравнения (6).

На шаге 130 получают масштабированный элементарный шаг (S(ϕ_step, r_dec)) азимутального угла, соответствующий точке облака точек.

На шаге 230 из битового потока декодирует количество m_s масштабированных элементарных шагов азимутального угла.

На шаге 150 с помощью уравнения (7) получают предсказанный азимутальный угол ϕ_pred

На шаге 240 из битового потока декодируют разность (остаток) ϕ_res, _dec азимутального угла.

На шаге 250 получают декодированный азимутальный угол ϕ_dec на основе декодированной разности ϕ_{res dec} азимутального угла и предсказанного азимутального угла ϕ_pred:

В одном из вариантов осуществления настоящее изобретение может применяться в схеме предсказания G-PCC, заданной уравнением (1) или (4), где азимутальные углы ϕ, соответствующие точкам облака точек, адаптивно квантуют в соответствии с описанием заявки ЕР 20306674.

Значение Q(r_res, ϕ_res, θ_res), описанное в связи с фиг.5 и 6, задают равным (r_res, ϕ_res, θ_res), где r_res разность радиуса, Qϕ_res - адаптивно квантованная разность азимутального угла, описанная ниже, a θ_res неквантованная разность угла возвышения (или индекса угла возвышения).

На стороне кодера разность r_res радиуса получают на основе уравнения (1), а декодированный радиус r_dec получают при помощи уравнения (4).

Разность ϕ_гев азимутального угла, полученную с помощью уравнения (1), адаптивно квантуют при помощи следующего выражения:

где Qϕ- адаптивное квантование с использованием шага Δϕ(r_dec) квантования, заданного выражением:

и где Δϕ_ars - шаг квантования дуги.

Если в кодеке применяют арифметику с фиксированной точкой, и внутренняя точность ΔIϕ кодека для представления азимутального угла задана дуговой шаг Δϕ_ars квантования, например, задают равным где, например, х=8.

Обратно квантованная остаточная разность IQϕ_res азимутального угла может быть получена обратным квантованием Qϕ_res следующим образом:

где IQ_ϕ операция обратного адаптивного квантования в зависимости от декодированного радиуса r_dec

Декодированный азимутальный угол ϕ_dec может быть определен следующим образом:

или:

Квантованную разность Qϕ_res азимутального угла кодируют в битовый поток В.

В одном из вариантов осуществления настоящего изобретения кодирование/декодирование разности ϕ_res азимутального угла между азимутальным углом точки облака точек и предсказанным азимутальным углом может быть более эффективным при использовании ограничивающего условия, заданного выражением:

где - абсолютное значение разности ϕ_res азимутального угла, ограниченное

целочисленным значением В, заданным следующим образом:

где

В варианте осуществления шага 130 первые данные D1 зависят от декодированного радиуса r_dec, а вторые данные D2 равны декодированному радиусу r_dec

В этом варианте осуществления, когда декодированный радиус r_dec (D2) строго меньше порога ТН, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угларавен первым данным D1, большим, чем элементарный шаг ϕ_step азимутального угла, а в противном случае масштабированный элементарный шаг S(ϕ_step r_dec) азимутального угла равен элементарному шагу ϕ_step азимутального угла.

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

Например,

Это означает, что масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла больше, чем элементарный шаг ϕ_step азимутального угла, когда декодированный радиус r_dec достаточно мал (т.е. когда r_dec*α меньше количества NP измерений на один оборот, или эквивалентно, r_dec<NP/α). Следовательно, применение излишнего количества элементарных шагов азимутального угла в случае «малых» декодированных радиусов будет сокращено, и затраты на кодирование (т.е. количество битов, необходимых для кодирования) количества m_s будут меньше. Оптимальным порогом для применения может быть TH=NP/α.

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

В одном из вариантов порог ТН может быть равен пороговому значению ТН₀, заданному следующим выражением:

Порог Th₀, когда разность азимутального угла ограничена целочисленной границей В, может быть получен следующим образом: когда В=0, лучше использовать S(ϕ_step,r_dec)=D1, а когда В>0, использовать S(ϕ_step,r_dec)= ϕ_step. Затем, на основе уравнения (15), когда В равно 0, т.е. В строго меньше единицы (В<1), поскольку В равно положительному числу, округленному до целого, когда выполнены следующие эквивалентные неравенства:

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

и получением

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

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

В варианте осуществления шага 130 вторые данные D2 получают путем вычисления монотонной функции m() от декодированного радиуса r_dec, при этом упомянутые вторые данные D2 сравнивают с пороговым значением ТН, полученным вычислением той же самой монотонной функции m() от порогового значения Th₀:

В случае, когда монотонная функция m() монотонно растущая, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла равен элементарному шагу ϕ_step азимутального угла, когда вторые данные D2 больше или равны пороговому значению ТН, и равен первым данным D1, когда вторые данные D2 строго меньше, чем пороговое значение ТН.

Монотонно растущие или убывающие функции могут применяться эквивалентно, при этом в объем настоящего описания входят и монотонно растущие, и монотонно убывающие функции m().

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

В качестве другого примера, если монотонно убывающую функцию m() используют непосредственно, очевидным образом могут быть получены способы, эквивалентные рассмотренным с помощью приложенных чертежей. К примеру, масштабированный элементарный шаг S(ϕ_step, r_dec) может быть равен элементарному шагу ϕ_step азимутального угла, когда вторые данные D2 строго меньше порогового значения ТН, и равен первым данным D1, когда вторые данные D2 больше или равны пороговому значению ТН.

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

В этом случае вторые данные D2 и пороговое значение ТН заданы следующим выражением:

В одном из вариантов, если внутренняя точность ΔIϕ=2π/2^N, разность азимутального угла адаптивно квантуют с помощью уравнения (10), где Δϕ_arc=2^N/Х, и α задан равным х, вторые данные D2 и пороговое значение Th₀ заданы следующим выражением:

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

В этом случае вторые данные D2 и пороговое значение ТН заданы следующим выражением:

В таком варианте, поскольку целочисленная граница В (уравнение 15) равна целому числу, условие В>0 эквивалентном D2>=ТН (т.е. D2>=1), а условие В=0 эквивалентно D2<1. Когда В=0 (D2<1), масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла равен первым данным D1 (уравнения 16 или 17), большим, чем элементарный шаг азимутального угла, а в противном случае масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла равен элементарному шагу ϕ_step азимутального угла.

Если для ограничения кодирования разности ϕ_res азимутального угла используют целочисленную границу В, очевидно более предпочтительным является вариант с использованием уравнения (23), поскольку вторые данные D2 равны целочисленной границе В, уже вычисленной для каждой точки, а пороговое значение ТН всегда равно 1. В противном случае, когда целочисленную границу В не применяют для ограничения разности азимутального угла, более предпочтителен рассмотренный выше первый вариант осуществления настоящего изобретения, или одна из его форм, или уравнения 21-22, поскольку пороговое значение ТН необходимо вычислить один раз для всего облака точек, а вторые данные D2 в уравнении (23) требуют вычисления целочисленного деления для каждой точки облака точек.

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

где результат (а)<<(b) равен побитовому сдвигу влево значения (а) на (b) битов (т.е. значению (а), умноженному на 2^b), а результат (а)>>(b) равен побитовому сдвигу вправо значения (а) на (b) битов (т.е. результату целочисленного деления (а) на 2^b).

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

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

Существует множество способов аппроксимировать целочисленное деление. Например, деление u/v может быть просто аппроксимировано операцией битового сдвига и вправо на количество битов, равное количеству битов NV, занимаемых значением v, (т.е. NV=floor(log₂(v)+l)). В этом случае u/v аппроксимируют делением u/2^NV. Другим способом может быть применение итеративного алгоритма Ньютона Рафсона (https://en.wikipedia.org/wiki/Division algorithm) с ограниченным числом итераций. Или, как это уже реализовано в G-PCC, можно использовать аппроксимацию 1/v с фиксированной точкой в виде таблицы поиска, и умножать и на аппроксимированное значение 1/v, и затем округлять результат с фиксированной точкой до требуемой точности.

По сравнению с истинным целочисленным делением из-за аппроксимации в результатах могут возникать небольшие ошибки, поэтому уравнение (16) приобретает следующий вид:

где divApprox(u, v) - функция аппроксимации целочисленного деления u/v, и+ε(r_dec) ошибка, возникающая из-за аппроксимации деления.

К примеру, где количество битов, занимаемых r_dec*α.

Из-за ошибки ε(r_dec) аппроксимации при использовании D1_app, в отличие от использования D1 (equation 16), при кодировании будут иметься потери. Возможны три различных случая:

1) D1app>D1, т.е. ε(r_dec)>0

В этом случае, поскольку D1_app слишком велико, битрейт будет немного меньшим, так как количество m_s масштабированных элементарных шагов азимутального угла будет меньшим, однако в предсказанных координатах (x_pred, y_pred) будет больше искажений.

2) D1app<D1, т.е. ε(r_dec)<0

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

3) D1_app=D1, в этом случае достигается оптимальная эффективность.

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

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

На фиг. 10 проиллюстрирована блок-схема алгоритма для способа 300 определения аппроксимации масштабированного элементарного шага S(ϕ_step, r_dec) азимутального угла в соответствии по меньшей мере с одним из вариантов осуществления настоящего изобретения.

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

Как было описано выше, когда декодированный радиус r_dec (D2) больше или равен пороговому значению ТН, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла задают равным элементарному шагу ϕ_step азимутального угла. Когда декодированный радиус r_dec (D2) строго меньше порогового значения ТН (или когда целочисленная граница В, вычисленная на основе декодированного радиуса r_dec и элементарного шага ϕ_step азимутального угла, равна 0), на шаге 310 получают первыйэлементарный шаг ϕ_step,₀ азимутального угла с помощью аппроксимации на основе декодированного радиуса r_dec, к примеру:

На шаге 320 первое значение целочисленной границы ВО получают на основе первого элементарного ϕ_step,₀ шага азимутального угла и декодированного радиуса r_dec (уравнение 15). Затем, начиная с индекса i=0, пока целочисленная граница B_j больше 0, индекс i увеличивают на единицу (шаг 340), получают (шаг 350) новый элементарный шаг фйер,1 азимутального угла, уменьшая на единицу предыдущий элементарный шаг ϕ_step,_i-1 азимутального угла: и получают новое значение целочисленной границы B_i (шаг 360) на основе элементарного шага фйер,1 азимутального угла и декодированного радиуса r_dec (уравнение 15).

Когда целочисленная граница B_i равна нулю, разрешают описанный выше первый случай, и масштабированный элементарный шаг S(ϕ_step r_dec) азимутального угла может быть задан равным ϕ_step,_i.

В одном из вариантов, чтобы также разрешить описанный выше второй случай, как это дополнительно показано на фиг. 10, когда целочисленная граница B_j равна нулю, получают (шаг 370) новый элементарный шаг ϕ_step,_i+1 азимутального угла, увеличивая на единицу текущий элементарный шаг азимутального угла:и получают новое значение целочисленной границы B_i+1 (шаг 380) на основе элементарного шага ϕ_step,_i+1 азимутального угла и декодированного радиуса r_dec (уравнение 15).

Если целочисленная граница B_i+1 равна нулю, это значит, что ϕ_step,_i может быть еще увеличен до ϕ_step,_i+1и индекс i увеличивают на единицу (шаг 390).

Затем получают (шаг 370) новый элементарный шаг азимутального угла и новую целочисленную границу (шаг 380).

Эту процедуру повторяют итеративно до тех пор, пока целочисленная граница B_i+1 станет неравной нулю (т.е. станет большей нуля), и в этом случае масштабированный элементарный шаг S(ϕ_step r_dec) азимутального угла задают равным текущему элементарному шагу ϕ_step,_i азимутального угла.

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

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

На фиг. 11 проиллюстрирован еще один пример способа 400 определения масштабированного элементарного шага S(ϕ_step, r_dec) в соответствии по меньшей мере с одним из вариантов осуществления настоящего изобретения.

Как было описано выше, когда декодированный радиус r_dec (D2) больше или равен пороговому значению ТН, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла задают равным элементарному шагу ϕ_step азимутального угла. Когда декодированный радиус r_dec (D2) строго меньше порогового значения ТН (или когда целочисленная граница В, вычисленная на основе декодированного радиуса r_dec и элементарного шага ϕ_step азимутального угла, равна 0), на шаге 410 первый элементарный шаг ϕ_step,₀ азимутального угла задают равным элементарному шагу ϕ_step азимутального угла, а соответствующую длину ϕ_ars,₀ дуги задают равной (шаг 420):

Затем, начиная с индекса i=0, пока длина ϕ_ars,₀ дуги меньше порогового значения Th₁, индекс i увеличивают на 1, а предыдущий элементарный шаг ϕ_step,_i-1 азимутального угла (шаг 430) и предыдущую соответствующую длину ϕ_ars,_i-1 дуги (шаг 440) умножают на два (с помощью операции битового сдвига влево), и получают новый элементарный шаг ϕ_step,_i азимутального угла и новую соответствующую длину ϕ_ars,_i дуги.

Когда длина ϕ_ars,_i дуги становится не меньшей порогового значения Th₁, масштабированный элементарный шаг S(ϕ_step, r_dec) азимутального угла может быть задан равным элементарному шагу ϕ_step,i азимутального угла.

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

В качестве примера, в варианте, показанном на фиг. 11, когда Th₁=π/ΔIϕ всегда получают второй или третий из описанных выше случаев, и в экспериментах, поставленных авторами, сохранялось около 90% эффективности кодирования, по сравнению сприменением истинного деления. Однако если использовать Th₁=π/ΔIϕ, и допустить еще одну итерацию, когда возможен первый случай, при этом снижается абсолютное значение ошибки ε(r_dec) аппроксимации, однако удается сохранить только около 72% эффективности кодирования, даже если ошибка при делении меньше или равна предыдущему варианту. Это доказывает, что первого случая желательно избегать.

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

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

Система 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 связи, которые обеспечивает возможность связи с другими устройствами по каналу 900 связи. Интерфейс 550 связи может включать, без ограничения перечисленным, приемопередатчик, сконфигурированный для передачи и приема данных по каналу 900 связи. Интерфейс 550 связи может включать, без ограничения перечисленным, модем или сетевую карту, при этом канал 900 связи может быть реализован, например, в проводной и/или беспроводной среде передачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники для кодирования/декодирования геометрических данных облака точек, захваченных вращающейся измерительной головкой. Технический результат заключается в снижении задержек при кодировании и декодировании облака точек в битовый поток кодированных данных облака точек. Технический результат достигается за счет этапов, на которых выполняют: получение масштабированного элементарного шага азимутального угла, соответствующего точке облака точек, при этом масштабированный элементарный шаг азимутального угла больше элементарного шага азимутального угла, когда вторые данные строго меньше, чем пороговое значение, а в противном случае равен элементарному шагу азимутального угла; кодирование, в битовый поток, количества масштабированных элементарных шагов азимутального угла, полученного из азимутального угла точки, предсказания азимутального угла и масштабированного элементарного шага азимутального угла; и кодирование, в битовый поток, разности азимутального угла точки между азимутальным углом точки и предсказанным азимутальным углом, вычисленным на основе количества масштабированных элементарных шагов азимутального угла и масштабированного элементарного шага азимутального угла. 6 н. и 8 з.п. ф-лы, 12 ил.

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

- получение (130) масштабированного элементарного шага (S(ϕ_step, r_dec)) азимутального угла, соответствующего точке облака точек, при этом масштабированный элементарный шаг (S(ϕ_step, r_dec)) азимутального угла равен первым данным (D1), большим элементарного шага (ϕ_step) азимутального угла, когда вторые данные (D2) строго меньше, чем пороговое значение, а когда вторые данные (D2) больше или равны пороговому значению, масштабированный элементарный шаг (S(ϕ_step, r_dec)) азимутального угла равен элементарному шагу (ϕ_step) азимутального угла, при этом элементарный шаг (ϕ_step) азимутального угла вычисляют на основе частот и скорости вращения, с которыми вращающаяся измерительная головка захватывала облако точек, при этом вторые данные (D2) зависят от декодированного радиуса (r_dec) точки, полученного путем кодирования и декодирования (120) радиуса, соответствующего упомянутой точке;

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

- кодирование (160), в битовый поток, разности азимутального угла точки между азимутальным углом точки и предсказанным азимутальным углом, вычисленным (150) на основе количества (m_s) масштабированных элементарных шагов азимутального угла и масштабированного элементарного шага (S(ϕ_step, r_dec)) азимутального угла.

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

- декодирование (210) элементарного шага (ϕ_step) азимутального угла из битового потока;

- получение (220) декодированного радиуса (r_dec) точки облака точек на основе декодированной разности (r_res, _dec) радиуса, декодированной из битового потока;

- получение (130) масштабированного элементарного шага (S(ϕ_step, r_dec)) азимутального угла, соответствующего точке облака точек, при этом масштабированный элементарный шаг (S(ϕ_step, r_dec)) азимутального угла равен первым данным (D1), большим элементарного шага (ϕ_step) азимутального угла, когда вторые данные (D2), зависящие от декодированного радиуса (r_dec) точки, строго меньше, чем пороговое значение (ТН), а когда вторые данные (D2), зависящие от декодированного радиуса (r_dec) точки, равны или больше порогового значения (ТН), масштабированный элементарный шаг (S(ϕ_step, r_dec)) азимутального угла равен элементарному шагу (ϕ_step) азимутального угла;

- декодирование (230) количества (m_s) масштабированных элементарных шагов азимутального угла из битового потока;

- декодирование (240) декодированной разности (ϕ_res, _dec) азимутального угла из битового потока; и

- получение (250) декодированного азимутального угла (ϕ_dec) на основе декодированной разности (ϕ_res, _dec) азимутального угла и предсказанного азимутального угла, вычисленного (150) на основе количества (m_s) масштабированных элементарных шагов азимутального угла и масштабированного элементарного шага (S(ϕ_step, r_dec)) азимутального угла.

3. Способ по п. 1 или 2, в котором первые данные (D1) зависят от декодированного радиуса (r_dec).

4. Способ по п. 3, в котором первые данные (D1) обратно пропорциональны произведению декодированного радиуса на масштабирующий коэффициент (α), больший или равный 1.

5. Способ по п. 1 или 2, в котором вторые данные (D2) равны декодированному радиусу (r_dec).

6. Способ по п. 1 или 2, в котором вторые данные (D2) получают путем вычисления монотонной функции от декодированного радиуса (r_dec), при этом вторые данные (D2) сравнивают со вторым пороговым значением (ТН), полученным вычислением той же самой монотонной функции от упомянутого порогового значения.

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

8. Способ по п. 6, в котором первые данные (D1) получают из аппроксимации 2π/(r_dec*α*ΔIϕ), где r_dec - декодированный радиус, α - коэффициент масштабирования, больший или равный 1, а ΔIϕ соответствует внутренней точности азимутальных углов.

9. Способ по п. 8, в котором первые данные (D1) получают путем итеративного уточнения упомянутой аппроксимации.

10. Способ по п. 8, в котором аппроксимацию получают путем нахождения, для элементарного шага азимутального угла, наибольшего множителя, представляющего собой степень двойки, который меньше, чем 2π/(r_dec*α*ΔIϕ).

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

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

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

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