IP Library › Granted Patent US 12,477,156
Granted Patent B2
US 12,477,156 · App. 18/000,919 · Granted Nov 18, 2025

Method for encoding and decoding, encoder, and decoder

Inventors: Wei Zhang (Shaanxi, CN); Mary-Luc Georges Henry Champel (Beijing, CN)
Assignees: Beijing Xiaomi Mobile Software Co., Ltd.; Xidian University
H04N19/96G06T7/10H04N19/184H04N19/91G06T2207/10028
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,477,156
App. No.
18/000,919
Granted
Nov 18, 2025
Kind
B2
Abstract

A method for encoding a point cloud to generate a bitstream of compressed point cloud data is provided. The point cloud's geometry is represented by an octree-based structure with a plurality of nodes having parent-child relationships by recursively splitting a volumetric space containing the point cloud into sub-volumes each associated with a node of the octree-based structure. The method includes: determining a coding mode, wherein the coding mode includes a planar coding mode and an angular coding mode; obtaining coding context information for a present child node, entropy encoding the present child node based on the obtained coding context information to produce encoded data for the bitstream.

Claims (78)

1 . A method for encoding a point cloud to generate a bitstream of compressed point cloud data, wherein the point cloud's geometry is represented by an octree-based structure with a plurality of nodes having parent-child relationships by recursively splitting a volumetric space containing the point cloud into sub-volumes each associated with a node of the octree-based structure, the method comprising:

determining a coding mode, wherein the coding mode includes a planar coding mode and an angular coding mode;

obtaining coding context information for a present child node, wherein

if the coding mode is the planar coding mode, the coding context information includes planar context information and plane position context information of the present child node, wherein the planar context information is determined according to an occupancy pattern of a present parent node and an occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node, wherein for determining the planar context information and the plane position context information according to the occupancy pattern of at least one neighboring parent node, a present plane position of the present child node relative to the present parent node is determined, wherein the present plane position includes a high plane position and a low plane position, wherein if the present plane position is the low plane position, the planar context information and the plane position context information are determined according to an occupancy of a first group of four child nodes of the neighboring parent node that are directly next to the present parent node and an occupancy of a second group of four child nodes of the present parent node directly opposite the first group; and

if the coding mode is the angular coding mode, the coding context information includes planar information of the present parent node and occupancy of a vertical neighboring parent node adjacent to the present parent node; and

entropy encoding the present child node based on the obtained coding context information to produce encoded data for the bitstream.

2 . The method according to claim 1 , wherein the plane position context information includes one or more of:

a distance d from a closest already coded node at a same coordinate in a respective parent node and a same depth D in the octree-based structure;

a plane position of the closest already coded node at the same coordinate in the respective parent node and the same depth D in the octree-based structure; and

a plane position of the present child node according to the occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node.

3 . The method according to claim 2 , wherein if the closest already coded node at the same coordinate in the respective parent node and the same depth D in the octree-based structure is non-existent, the plane position context information only includes the plane position of the present child node according to the occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node.

4 . The method according to claim 2 , wherein if the coding mode is the angular coding mode and the present child node is not eligible for the angular coding mode, the coding context information includes the plane position context information.

5 . The method according to claim 1 , wherein:

if at least one child node of the first group is occupied and the second group is not occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if the first group is not occupied and at least one child node of the second group is occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if the first group is not occupied and the second group is not occupied, the planar context information includes a likelihood of a plane, wherein the plane position context information includes a likelihood of a low plane, if at least one or more child nodes in the neighboring parent node are occupied which do not belong to the first group; or

if at least one child node of the first group is occupied and at least one child node of the second group is occupied and #FirstGroup>#SecondGroup+1, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if at least one child node of the first group is occupied and at least one child node of the second group is occupied and #FirstGroup<#SecondGroup+1, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position;

wherein #FirstGroup indicates a number of occupied child nodes in the first group and #SecondGroup indicates a number of occupied child nodes in the second group.

6 . The method according to claim 1 , wherein if the present plane position is high, the planar context information and the plane position context information are determined according to an occupancy of the neighboring parent node that is along an axis directly after the present parent node, and an occupancy of a group of four child nodes of the present parent node in a plane directly perpendicular to the axis and next to the present child node.

7 . The method according to claim 6 , wherein:

if at least one child node of the group is occupied and the neighboring parent node is not occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if the group is not occupied and the neighboring parent node is occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if the group is not occupied and the neighboring parent node is not occupied, the planar context information includes a likelihood of a plane, wherein the plane position context information includes a likelihood of a low plane, if one or more child nodes in a neighboring parent node along the axis directly before the present parent node are occupied; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group>2, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group<2, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group=2, the planar context information includes a likelihood of absence of a plane and the plane position is inferred to be unknown;

wherein #Group indicates the number of occupied nodes in the group.

8 . The method according to claim 1 , wherein the neighboring parent node is arranged along one of geometrical axes.

9 . The method according to claim 1 , wherein the coding context information is determined along all three geometrical axes.

10 . A method for decoding a bitstream of compressed point cloud data to generate a reconstructed point cloud, wherein the point cloud's geometry is represented by an octree-based structure with a plurality of nodes having parent-child relationships by recursively splitting a volumetric space containing the point cloud into sub-volumes each associated with a node of the octree-bases structure, the method comprising:

determining a coding mode, wherein the coding mode includes a planar coding mode and an angular coding mode;

obtaining coding context information for a present child node, wherein

if the coding mode is the planar coding mode, the coding context information includes planar context information and plane position context information of the present child node, wherein the planar context information is determined according to an occupancy pattern of a present parent node and an occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node, wherein for determining the planar context information and the plane position context information according to the occupancy pattern of at least one neighboring parent node, a present plane position of the present child node relative to the present parent node is determined, wherein the present plane position includes a high plane position and a low plane position, wherein if the present plane position is the low plane position, the planar context information and the plane position context information are determined according to an occupancy of a first group of four child nodes of the neighboring parent node that are directly next to the present parent node and an occupancy of a second group of four child nodes of the present parent node directly opposite the first group;

if the coding mode is the angular coding mode, the coding context information includes planar information of the present parent node and occupancy of a vertical neighboring parent node adjacent to the present parent node; and

entropy decoding the bitstream based on the obtained coding context information of the present child node to reconstruct the point cloud.

11 . The method according to claim 10 , wherein the plane position context information includes one or more of:

a distance d from a closest already coded node at a same coordinate in a respective parent node and a same depth D in the octree-based structure;

a plane position of the closest already coded node at the same coordinate in the respective parent node and the same depth D in the octree-based structure; and

a plane position of the present child node according to the occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node.

12 . The method according to claim 11 , wherein if the closest already coded node at the same coordinate in the respective parent node and the same depth D in the octree-based structure is non-existent, the plane position context information only includes the plane position of the present child node according to the occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node.

13 . The method according to claim 11 , wherein if the coding mode is the angular coding mode and the present child node is not eligible for the angular coding mode, the coding context information includes the plane position context information.

14 . The method according to claim 10 , wherein:

if at least one child node of the first group is occupied and the second group is not occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if the first group is not occupied and at least one child node of the second group is occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if the first group is not occupied and the second group is not occupied, the planar context information includes a likelihood of a plane, wherein the plane position context information includes a likelihood of a low plane, if at least one or more child nodes in the neighboring parent node are occupied which do not belong to the first group; or

if at least one child node of the first group is occupied and at least one child node of the second group is occupied and #FirstGroup>#SecondGroup+1, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if at least one child node of the first group is occupied and at least one child node of the second group is occupied and #FirstGroup<#SecondGroup+1, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position;

wherein #FirstGroup indicates a number of occupied child nodes in the first group and #SecondGroup indicates a number of occupied child nodes in the second group.

15 . The method according to claim 10 , wherein if the present plane position is high, the planar context information and the plane position context information are determined according to an occupancy of the neighboring parent node that is along an axis directly after the present parent node, and an occupancy of a group of four child nodes of the present parent node in a plane directly perpendicular to the axis and next to the present child node.

16 . The method according to claim 15 , wherein:

if at least one child node of the group is occupied and the neighboring parent node is not occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if the group is not occupied and the neighboring parent node is occupied, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if the group is not occupied and the neighboring parent node is not occupied, the planar context information includes a likelihood of a plane, wherein the plane position context information includes a likelihood of a low plane, if one or more child nodes in a neighboring parent node along the axis directly before the present parent node are occupied; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group>2, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a low plane position; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group<2, the planar context information includes a likelihood of a plane and the plane position context information includes a likelihood of a high plane position; or

if at least one child node of the group is occupied and the neighboring parent node is occupied and #Group=2, the planar context information includes a likelihood of absence of a plane and the plane position is inferred to be unknown;

wherein #Group indicates the number of occupied nodes in the group.

17 . The method according to claim 10 , wherein the neighboring parent node is arranged along one of geometrical axes.

18 . The method according to claim 10 , wherein the coding context information is determined along all three geometrical axes.

19 . An encoder for encoding a point cloud to generate a bitstream of compressed point cloud data, wherein the point cloud's geometry is represented by an octree-based structure with a plurality of nodes having parent-child relationships by recursively splitting a volumetric space containing the point cloud into sub-volumes each associated with a node of the octree-based structure, the encoder comprising:

a processor and

a memory storage device storing instructions executable by the processor,

wherein the processor is configured to:

determine a coding mode, wherein the coding mode includes a planar coding mode and an angular coding mode;

obtain coding context information for a present child node, wherein

if the coding mode is the planar coding mode, the coding context information includes planar context information and plane position context information of the present child node, wherein the planar context information is determined according to an occupancy pattern of a present parent node and an occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node, wherein for determining the planar context information and the plane position context information according to the occupancy pattern of at least one neighboring parent node, a present plane position of the present child node relative to the present parent node is determined, wherein the present plane position includes a high plane position and a low plane position, wherein if the present plane position is the low plane position, the planar context information and the plane position context information are determined according to an occupancy of a first group of four child nodes of the neighboring parent node that are directly next to the present parent node and an occupancy of a second group of four child nodes of the present parent node directly opposite the first group; and

if the coding mode is the angular coding mode, the coding context information includes planar information of the present parent node and occupancy of a vertical neighboring parent node adjacent to the present parent node; and

entropy encoding the present child node based on the obtained coding context information to produce encoded data for the bitstream.

20 . A decoder for decoding a bitstream of compressed point cloud data to generate a reconstructed point cloud, wherein the point cloud's geometry is represented by an octree-based structure with a plurality of nodes having parent-child relationships by recursively splitting a volumetric space containing the point cloud into sub-volumes each associated with a node of the octree-bases structure, the decoder comprising:

a processor and

a memory storage device storing instructions executable by the processor,

wherein the processor is configured to:

determine a coding mode, wherein the coding mode includes a planar coding mode and an angular coding mode;

obtain coding context information for a present child node, wherein

if the coding mode is the planar coding mode, the coding context information includes planar context information and plane position context information of the present child node, wherein the planar context information is determined according to an occupancy pattern of a present parent node and an occupancy pattern of at least one neighboring parent node positioned directly next to the present parent node, wherein for determining the planar context information and the plane position context information according to the occupancy pattern of at least one neighboring parent node, a present plane position of the present child node relative to the present parent node is determined, wherein the present plane position includes a high plane position and a low plane position, wherein if the present plane position is the low plane position, the planar context information and the plane position context information are determined according to an occupancy of a first group of four child nodes of the neighboring parent node that are directly next to the present parent node and an occupancy of a second group of four child nodes of the present parent node directly opposite the first group;

if the coding mode is the angular coding mode, the coding context information includes planar information of the present parent node and occupancy of a vertical neighboring parent node adjacent to the present parent node; and

entropy decoding the bitstream based on the obtained coding context information of the present child node to reconstruct the point cloud.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 7, 2022
From: ZHANG, WEI; CHAMPEL, MARY-LUC GEORGES HENRY
To: BEIJING XIAOMI MOBILE SOFTWARE CO., LTD.; XIDIAN UNIVERSITY
Reel/Frame 062009/0280 →
Continuity (1)
Related Publication 20230224506A1 · Jul 13, 2023
References Cited (94)
US 10223810B2 · Chou et al. · 2019 [cited by applicant]
US 10674165B2 · Panusopone · 2020 [cited by examiner]
US 10693492B1 · Lasserre · 2020 [cited by examiner]
US 10694210B2 · Chou et al. · 2020 [cited by applicant]
US 11483363B2 · Hur et al. · 2022 [cited by applicant]
US 11563984B2 · Zhang et al. · 2023 [cited by applicant]
US 11601488B2 · Hur et al. · 2023 [cited by applicant]
US 11601675B2 · Park et al. · 2023 [cited by applicant]
US 11611775B2 · Gao et al. · 2023 [cited by applicant]
US 11615557B2 · Flynn · 2023 [cited by applicant]
US 11620768B2 · Flynn · 2023 [cited by applicant]
US 11676310B2 · Huang et al. · 2023 [cited by applicant]
US 11711545B2 · Zhang et al. · 2023 [cited by applicant]
US 11736726B2 · Zhang et al. · 2023 [cited by applicant]
US 11750839B2 · Zhang et al. · 2023 [cited by applicant]
US 11843803B2 · Zhang et al. · 2023 [cited by applicant]
US 11895307B2 · Mammou et al. · 2024 [cited by applicant]
US 11936850B2 · Wan et al. · 2024 [cited by applicant]
US 11948336B2 · Zhang et al. · 2024 [cited by applicant]
US 12010341B2 · Oh et al. · 2024 [cited by applicant]
US 12069316B2 · Oh et al. · 2024 [cited by applicant]
US 12087023B2 · Sugio et al. · 2024 [cited by applicant]
US 12113963B2 · Zhu · 2024 [cited by applicant]
US 12149717B2 · Zhang et al. · 2024 [cited by applicant]
US 12165368B2 · Oh et al. · 2024 [cited by applicant]
US 12167032B2 · Sugio et al. · 2024 [cited by applicant]
US 12198392B2 · Iguchi et al. · 2025 [cited by applicant]
US 20140270476A1 · Cameron et al. · 2014 [cited by applicant]
US 20170214943A1 · Cohen et al. · 2017 [cited by applicant]
US 20170347100A1 · Chou et al. · 2017 [cited by applicant]
US 20170347122A1 · Chou et al. · 2017 [cited by applicant]
US 20190394496A1 · Tourapis et al. · 2019 [cited by applicant]
US 20200021844A1 · Yea et al. · 2020 [cited by applicant]
US 20200143568A1 · Lasserre et al. · 2020 [cited by applicant]
US 20200396489A1 · Flynn · 2020 [cited by examiner]
US 20200413080A1 · Lasserre · 2020 [cited by examiner]
US 20210004992A1 · Flynn et al. · 2021 [cited by applicant]
US 20210327099A1 · Van der Auwera · 2021 [cited by examiner]
US 20220351423A1 · Martin-Cocher · 2022 [cited by examiner]
US 20250063196A1 · Sugio et al. · 2025 [cited by applicant]
CA 3096452A1 · 2019 [cited by applicant]
CA 3103454A1 · 2019 [cited by applicant]
CN 106846425A · 2017 [cited by applicant]
CN 110418135A · 2019 [cited by applicant]
CN 110572655A · 2019 [cited by applicant]
CN 110915219A · 2020 [cited by applicant]
CN 111145090A · 2020 [cited by applicant]
CN 111615791A · 2020 [cited by applicant]
CN 111615792A · 2020 [cited by applicant]
CN 111699697A · 2020 [cited by applicant]
CN 114503440A · 2022 [cited by applicant]
EP 3514967A1 · 2019 [cited by applicant]
EP 3595180A1 · 2020 [cited by applicant]
JP 2018101404A · 2018 [cited by applicant]
JP 2021528917A · 2021 [cited by applicant]
JP 2022504344A · 2022 [cited by applicant]
RU 2267161C2 · 2005 [cited by applicant]
WO WO2017209961A1 · 2017 [cited by applicant]
WO WO2019140508A1 · 2019 [cited by applicant]
WO WO2019140510A1 · 2019 [cited by applicant]
WO WO2019195922A1 · 2019 [cited by applicant]
WO 2020055865A1 · 2020 [cited by applicant]
WO WO2020072665A1 · 2020 [cited by applicant]
WO 2020189976A1 · 2020 [cited by applicant]
Intellectual Property India, Office Action Issued in Application No. 202247074337, Apr. 24, 2023, 5 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, Written Opinion of the International Searching Authority Issued in Application No. PCT/CN2020/098267, Nov. 11, 2020, WIPO, 6 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, Written Opinion of the International Searching Authority Issued in Application No. PCT/CN2020/098272, Nov. 11, 2020, WIPO, 6 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, Written Opinion of the International Searching Authority Issued in Application No. PCT/CN2020/119829, Jun. 29, 2021, WIPO, 5 pages. [cited by applicant]
Notice of Reasons for Refusal issued in Japanese Application No. 2022-578799, dated Aug. 10, 2023, 4 pages. [cited by applicant]
Notice about the results of checking the patentability of an invention issued in Russian Application No. 2022133674/28(073328), dated Aug. 8, 2023, 16 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, International Search Report issued in Application No. PCT/CN2020/098272, Nov. 11, 2020, WIPO, 2 pages. [cited by applicant]
State Intellectual Property Office of the People's Republic of China, Office Action and Search Report issued in Application No. 202080003877.X, Nov. 3, 2021, 9 pages. [cited by applicant]
State Intellectual Property Office of the People's Republic of China, Office Action and Search Report issued in Application No. 202080003878.4, Nov. 3, 2021, 14 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, International Search Report issued in Application No. PCT/CN2020/098267, Nov. 11, 2020, WIPO, 4 pages. [cited by applicant]
ISA State Intellectual Property Office of the People's Republic of China, International Search Report issued in Application No. PCT/CN2020/119829, Jun. 29, 2021, WIPO, 5 pages. [cited by applicant]
European Patent Office, Extended European Search Report Issued in Application No. 20196648.8, Mar. 1, 2021, 8 pages. [cited by applicant]
European Patent Office, Extended European Search Report Issued in Application No. 20196653.8, Mar. 1, 2021, 13 pages. [cited by applicant]
Ke Zhang et al., “Hierarchical Segmentation Based Point Cloud Attribute Compression” “2018 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)”, Dec. 31, 2018, 5 pages. [cited by applicant]
Eduardo Pavez et al., “Dynamic Polygon Cloud Compression” “IEEE”, Mar. 5, 2017, 6 pages. [cited by applicant]
Sebastien Lasserre et al., “[GPCC] [CE 13.22 related] An improvement of the planar coding mode”, “128.MPEG meeting No. m50642”, Oct. 11, 2019, 3 pages. [cited by applicant]
Sebastien Lasserre et al., “[GPCC] Planar mode in octree-based geometry coding” “127.MPEG meeting No. m48906”, Jul. 12, 2019, 33 pages. [cited by applicant]
Antoine Dricot et al., “Adaptive Multi-level Triangle Soup for Geometry-based Point Cloud Coding”, “2019 IEE 21st International Workshop on Multimedia Signal Processing (MMSP)”, Dec. 31, 2019, 6 pages. [cited by applicant]
Lasserre (Blackberry)S et al., “On an improvement of RAHT to exploit attribute correlation”, “126.MPEG Meeting; Mar. 25, 2019-Mar. 29, 2019; Geneva; (Motion Picture Expert Group or ISO/IEC JTC1/SC29/WG11), No. m47378, X… [cited by applicant]
3DG, “G-PCC codec description” “128.MPEG Meeting; Oct. 7, 2019-Oct. 11, 2019; Geneva; (Muiuinpicture Expert Group or ISO/IEC JTC1/SC29/WG11), No. n18891, XP030225589” Dec. 18, 2019, 74 pages. [cited by applicant]
Sebastien Lasserre et al., “Entropy coding an octree node occupancy depending on neighbour's child nodes (TM3)”, “124.MPEG Macau, m44753”, Oct. 2018, 29 pages. [cited by applicant]
Khaled Mammou et al., “Adaptive Distance-based Prediction in TMC3”, “Apple Inc., ISO/IEC JTC1/SC29/WG11 MPEG2018/m42642, San Diego, US”, Apr. 2018, 3 pages. [cited by applicant]
European Patent Office, Office Action Issued in Application No. 20196648.8, Jan. 25, 2024, Germany, 5 pages. [cited by applicant]
European Patent Office, Office Action Issued in Application No. 20196653.8, Jan. 26, 2024, Germany, 7 pages. [cited by applicant]
Wei Zhang et al:“[G-PCC] [new proposal] Planar coding improvement”, 130.MPEG Meeting; Apr. 20, 2020-Apr. 24, 2020; XP030287104, No. m53522, Apr. 23, 2020, 5 pages. [cited by applicant]
Japanese Patent Office, Office Action Issued in Application No. 2022-579816, Mar. 5, 2024, 9 pages. (Submitted with Machine Translation). [cited by applicant]
State Intellectual Property Office of the People's Republic of China, Office Action and Search Report Issued in Application No. 2022107881419, Mar. 29, 2024, 16 pages. (Submitted with Machine Translation). [cited by applicant]
The First Office Action issued by the State Intellectual Property Office of People's Republic of China on Jun. 6, 2025, in corresponding Application No. CN 202080017735.9, 8 pages. [cited by applicant]
Office Action issued by the Intellectual Property India on Mar. 27, 2025, in corresponding Application No. IN 202247074338, 7 pages. [cited by applicant]
Notice of Allowance issued by the U.S. Patent and Trademark Office on Mar. 12, 2025, in U.S. Appl. No. 18/001,992, 17 pages. [cited by applicant]