KR102801168B1 - Processing Method for Video-based Point Cloud Data and an electronic device supporting the same - Google Patents

Abstract

The present invention discloses a video-based point cloud compression method and an electronic device supporting the same, characterized in that it includes the steps of receiving input point cloud data for a 3D object having three axes, generating tree nodes for converting the input point cloud data into a tree structure, arranging the generated tree nodes to estimate a normal for the input point cloud data in real time, and performing video-based point cloud compression for the input point cloud data based on the estimated normal.

Description

{Processing Method for Video-based Point Cloud Data and an electronic device supporting the same}

The present invention relates to point cloud data processing, and more particularly, to a method for processing video-based point cloud data for real-time Normal Estimation and an electronic device supporting the same.

Point cloud, one type of 3D image data, is attracting attention in various fields due to the remarkable development of media acquisition and processing technology. 3D image data is acquired as points with attribute values (e.g., color, reflectivity, transparency) in 3D space, but in order to supplement the limited graphic data processing speed, a 3D mesh model, which is a method of approximating the acquired points into polygons to reduce the amount of 3D data processed, has been used. However, with the rapidly developing performance of hardware, it has become possible to process all 3D points, and thus point cloud data, which is a cluster of acquired points, has begun to be used as is. In particular, point clouds are being utilized in various fields such as the military, education, medicine, and architecture due to their advantage of being able to precisely acquire 3D data.

Among them, in the autonomous driving field, high-precision, large-capacity data generated based on point clouds are used to obtain dynamic traffic situation information required for autonomous driving. Dynamic traffic situation information can be obtained using sensors such as Lidar, GPS, and cameras, and the point cloud obtained in this way is called a dynamic acquisition point cloud. The dynamic acquisition point cloud is composed of tens or millions of points, and has the characteristics of a wide range of expressions and a large amount of data, so a method for efficiently compressing point cloud data is required to transmit and receive it.

In order to solve the above-described problem, the present invention provides a video-based point cloud data processing method and an electronic device supporting the same, which enables real-time conversion of point cloud data by applying a tree structure to the normal estimation process, which requires the most associations in the compression processing of video-based point cloud data.

Meanwhile, the purpose of the present invention is not limited to the above purpose, and other purposes not mentioned can be clearly understood from the description below.

According to an embodiment of the present invention for achieving the above-described object, an electronic device includes a memory for storing input point cloud data for a 3D object having three axes, a graphics processor for processing compression for the input point cloud data, wherein the graphics processor is configured to generate tree nodes for converting the input point cloud data into a tree structure, arrange the generated tree nodes to estimate a normal for the input point cloud data in real time, and perform video-based point cloud compression for the input point cloud data based on the estimated normal.

Here, the graphic processor includes an offset generation unit that defines a depth value of a subtree according to the depth of the tree structure, and the offset generation unit assigns a specified offset value to a specified subtree when the depth of the tree structure is 0 and 1, and determines a left offset value and a right offset value of the tree structure based on index values for each of the input point cloud data when the depth of the tree structure is 2 or more.

In addition, the graphic processor is characterized by further including a segment alignment unit that aligns the entire list of the input point cloud data by section based on a specific axis among the three axes according to the offset value determined by the offset generation unit.

Here, the segment sorting unit is characterized in that it sorts the entire list by section based on the specific axis, but sorts in different sorting methods depending on the size of the section.

Meanwhile, the graphic processor further includes a reordering unit that reorders the sections sorted by the segment sorting unit, and the reordering unit divides the values sorted by the segment sorting unit and reorganizes the values of the remaining axes other than the specific axis to fit the specific axis, while processing them so that the size of the entire list becomes less than a specified value.

In addition, the graphic processor is characterized by including a segment min-max calculation unit for calculating a bounding box for the input point cloud data, a node generation unit for allocating a tree node to be used in the tree structure based on the values sorted by the reordering unit and the values calculated by the segment min-max calculation unit.

A video-based point cloud compression method according to an embodiment of the present invention is characterized by including the steps of receiving input point cloud data for a 3D object having three axes, generating tree nodes for converting the input point cloud data into a tree structure, arranging the generated tree nodes to estimate a normal for the input point cloud data in real time, and performing video-based point cloud compression for the input point cloud data based on the estimated normal.

Here, the step of generating the tree node is characterized by including a step of assigning a specified offset value to a specified subtree when the depth of the tree structure is 0 and 1, and determining a left offset value and a right offset value of the tree structure based on index values for each of the input point cloud data when the depth of the tree structure is 2 or more.

Additionally, the step of generating the tree node is characterized by including the step of arranging the entire list of the input point cloud data by section based on a specific axis among the three axes according to the determined offset value, while arranging in different sorting methods according to the size of the section, and the step of dividing the sorted values by the segment sorting unit, and reconstructing the values of the remaining axes other than the specific axis to fit the specific axis, while processing them so that the size of the entire list becomes less than a specified value.

In addition, the step of generating the tree node is characterized by including the step of calculating the maximum and minimum values of the bounding box for the input point cloud data, and the step of allocating the tree node to be used in the tree structure based on the values sorted by the reordering unit and the minimum and maximum values.

According to the present invention, the present invention supports reducing the compression time of video-based point cloud data and reducing the amount of data transmitted and received by processing normal calculation of each point more quickly during the compression process of point cloud data.

In addition, various effects other than the effects described above may be directly or implicitly disclosed in the detailed description according to the embodiments of the present invention to be described later.

FIG. 1 is a diagram illustrating an example of an electronic device configuration that supports video-based point cloud data processing according to an embodiment of the present invention.
FIG. 2 is a diagram for explaining a tree generation step during a video-based point cloud compression process according to an embodiment of the present invention.
FIG. 3 is a drawing showing an example of a configuration related to normal vector generation in a video-based point cloud compression method according to an embodiment of the present invention.
FIG. 4 is a diagram illustrating an example of a graphics processor implementation related to tree generation in a video-based point cloud compression method according to an embodiment of the present invention.
FIG. 5 is a diagram showing an example of operator definition related to tree creation according to an embodiment of the present invention.
FIG. 6 is a diagram showing an example of code defining the operation of an offset generation unit according to an embodiment of the present invention.
FIG. 7 is a diagram showing an example of code defining the operation of a segment alignment unit according to an embodiment of the present invention.
FIG. 8 is a diagram showing an example of code defining the operation of a reordering unit according to an embodiment of the present invention.
FIG. 9 is a diagram showing an example of code defining the operation of a segment minimum-maximum calculation unit according to an embodiment of the present invention.
FIG. 10 is a diagram showing an example of code defining the operation of a node creation unit according to an embodiment of the present invention.

In order to make the features and advantages of the problem solving means of the present invention more clear, the present invention will be described in more detail with reference to specific embodiments of the present invention illustrated in the attached drawings.

However, detailed descriptions of well-known functions or configurations that may obscure the gist of the present invention in the following description and attached drawings are omitted. In addition, it should be noted that identical components are indicated with the same drawing reference numerals as much as possible throughout the drawings.

The terms or words used in the following description and drawings should not be interpreted as limited to their conventional or dictionary meanings, but should be interpreted as meanings and concepts that conform to the technical idea of the present invention based on the principle that the inventor can appropriately define the concept of the terms to best describe his or her own invention. Therefore, the embodiments described in this specification and the configurations illustrated in the drawings are merely the most preferred embodiments of the present invention and do not represent all of the technical idea of the present invention. Therefore, it should be understood that there may be various equivalents and modified examples that can replace them at the time of filing this application.

Also, terms including ordinal numbers such as first, second, etc. are used to describe various components, and are only used to distinguish one component from another, and are not used to limit said components. For example, without departing from the scope of the present invention, a second component may be referred to as a first component, and similarly, a first component may also be referred to as a second component.

In addition, the terminology used in this specification is only used to describe specific embodiments and is not intended to limit the present invention. The singular expression includes the plural expression unless the context clearly indicates otherwise. In addition, it should be understood that the terms "comprises" or "has" described in this specification are intended to specify the presence of a feature, number, step, operation, component, part or combination thereof described in the specification, but do not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts or combinations thereof.

In addition, terms such as "unit," "device," and "module" described in the specification mean a unit that processes at least one function or operation, and this can be implemented by hardware, software, or a combination of hardware and software. In addition, "a or an," "one," "the," and similar related words can be used in the context of describing the present invention (especially, in the context of the claims below) to include both singular and plural meanings, unless otherwise indicated in the present specification or clearly contradicted by the context.

In addition to the terms described above, specific terms used in the following description are provided to help understanding of the present invention, and the use of these specific terms may be changed to other forms without departing from the technical spirit of the present invention.

In addition, embodiments within the scope of the present invention include computer-readable media having or carrying computer-executable instructions or data structures stored on a computer-readable medium. Such computer-readable media can be any available media that can be accessed by a general-purpose or special-purpose computer system. By way of example, and not limitation, such computer-readable media can include physical storage media such as RAM, ROM, EPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage, or any other medium that can be used to store or carry certain program code means in the form of computer-executable instructions, computer-readable instructions or data structures and that can be accessed by a general-purpose or special-purpose computer system.

Hereinafter, the system, device, and method constituting the present invention will be described in more detail through each drawing.

FIG. 1 is a diagram illustrating an example of an electronic device configuration that supports video-based point cloud data processing according to an embodiment of the present invention.

Referring to FIG. 1, an electronic device (100) according to an embodiment may include a communication interface (110), a sensor (120), a memory (130), a processor (150), and a graphic processor (160). Meanwhile, although a structure including a processor (150) and a graphic processor (160) has been described for the purpose of explaining the electronic device (100), the electronic device (100) may include only a graphic processor (160) for compression processing of point cloud data, or the processor (160) may replace the operation of the graphic processor (160) for controlling the electronic device (100) and compression processing of point cloud data described below.

The sensor (120) can collect 3D data or original point cloud data for a 3D object or surrounding objects of the electronic device (100). The sensor (120) can include, for example, at least a depth camera. Alternatively, the sensor (120) can include a lidar sensor capable of obtaining object-related depth information. Alternatively, the sensor (120) can collect RGB images (or RGB-D data) for the 3D object or surrounding objects. The sensor (120) of the present invention is not limited to the type of sensor, and can be understood as a configuration that collects original point cloud data and transmits it to the processor (150). Meanwhile, the electronic device (100) of the present invention may not include the configuration of the above-described sensor (120), and may be configured to receive original point cloud data from a separately provided sensor (120) or a device that collects original point cloud data.

The above communication interface (110) may be a configuration that supports a communication function of the electronic device (100). The communication interface (110) may include a broadcast communication circuit for the electronic device (100) to broadcast point cloud data, or may include at least one of a wired communication circuit or a wireless communication circuit for a server that provides the point cloud data to specific terminals. The communication interface (110) may serve as a transmission means that compresses and transmits point cloud data defined in a tree structure according to an embodiment of the present invention.

The above memory (130) can store various data and programs required for operating the electronic device (100). For example, the memory (130) can store original point cloud data received from the sensor (120) or an external electronic device. In addition, the memory (130) can temporarily or semi-permanently store data converted from the received original point cloud data into a tree structure, and compressed data (or compressed point cloud data) compressed from the point cloud data of the tree structure. In addition, the memory (130) can store an algorithm for converting the original point cloud data into a specific tree structure and a compression algorithm.

The processor (150) can perform data transmission and data processing required for the operation of the electronic device (100). For example, the processor (150) can receive original point cloud data and transmit the received data to the graphics processor (160) for tree structure conversion of the received original point cloud data. The processor (150) can output (or transmit) video-based point cloud data compressed by the graphics processor (160) through the communication interface (110).

The graphic processor (160) may perform a compression process on the original point cloud data. In this process, the graphic processor (160) may perform a tree structuring of the original point cloud data and may perform compression of the point cloud data based on the tree structuring. The graphic processor (160) may perform video point cloud compression (VPCC: Video-based points cloud compression) on the tree-structured point cloud data. In this regard, the graphic processor (160) may include a VPCC encoder. The VPCC encoder may perform a role of converting 3D into 2D in order to compress the point cloud with a 2D video codec, and may include a patch generation unit, a packing unit, a geometry image generation unit, a texture image generation unit, smoothing, an image padding unit, a video compression unit, geometry reconstruction, occupancy map compression, Auxiliary patch-info compression, and a multiplexer. The above VPCC encoder divides the input (or original) point cloud into a patch generation unit and converts it into a 2D image. The patch generation unit can perform a tree structure of point cloud data for real-time normal vector processing, and positions the divided patches on a 2D plane and compresses them with a video codec. The geometry image generation unit stores position information of the point cloud, and the texture image generation unit stores color information. In addition, the occupancy map compression unit indicates the presence or absence of a patch in the 2D plane. The compressed geometry video, compressed texture video, compressed occupancy map, and compressed auxiliary patch info are output as a single compressed bitstream through a multiplexer.

FIG. 2 is a diagram for explaining a tree generation step during a video-based point cloud compression process according to an embodiment of the present invention.

Referring to FIG. 2, video-based point cloud compression according to an embodiment of the present invention can be performed through a graphic processor (160). As illustrated, the graphic sensor (120) can align N points corresponding to original (or input) point cloud data for a 3D object with respect to the X-axis, and create a tree node (e.g., create a node of a K-D Tree structure) with a value (N/2) located at the center as a key. The graphic processor (160) can perform an operation of dividing the sorted result in half [0… N/2)[N/2… N), reconstructing the values of the remaining coordinate axes (YZ) to match the sorted X-axis, and aligning each of the divided lists with respect to the Y-axis. The graphic processor (160) can perform sorting in the order of the XYZ axes repeatedly until the size of the divided list becomes 2 for the above-described operations, and create a tree node when the size of the divided list becomes 2, thereby performing video-based point cloud compression. For example, referring to the illustrated drawing, the graphic processor (160) aligns seven points corresponding to a 3D object with respect to the X-axis, uses the central first point (1) as a key, and aligns the second point (2) and the third point (3) with the first branch (or leaf) of the first point (1), and then through repeated alignment, the fourth point (4) and the fifth point (5) are aligned to the second point (2), and the third point (3) and the seventh point (7) are aligned to the third point (3), and again through repeated alignment, the first to seventh points (4, 1, 2, 5, 6, 3, 7) are aligned with the same depth value, thereby generating a tree node.

As described above, the video-based point cloud compression according to the embodiment of the present invention can perform real-time compression operations by operating (or implementing) all processes necessary for compression through the graphics processor (160). The tree structure generated through this method is easy to optimize for the graphics processor (160) because all leaf nodes have the same depth.

FIG. 3 is a drawing showing an example of a configuration related to normal vector generation in a video-based point cloud compression method according to an embodiment of the present invention.

Referring to FIG. 3, the normal vector generation structure may include a tree generator (163), a point cloud tree array unit (165), an input point cloud data provider unit (161), and a normal line estimation unit (167). At least some of the blocks described in the above-described normal vector generation structure may be configured as at least one of a software block or a hardware module.

The above input point cloud data providing unit (161) collects original point cloud data stored in the aforementioned sensor (120) or an external device or memory (130), and transmits it to the tree generator (163), while also transmitting point data to the normal estimation unit (167). The tree generator (163) generates a tree node for the received original point cloud data (or input point cloud data) and transmits it to the point cloud tree arrangement unit (165).

The above point cloud tree array unit (165) receives point coordinates from the normal estimation unit (167) and can process the tree array by receiving tree nodes from the tree generator (163). The above point cloud tree array unit (165) provides tree structure information arranging nodes to the normal estimation unit (167) and can transmit it to the input point cloud data providing unit (161) for reference by index.

FIG. 4 is a diagram illustrating an example of a graphics processor implementation related to tree generation in a video-based point cloud compression method according to an embodiment of the present invention.

Referring to FIG. 4, a graphic processor (160) according to an embodiment of the present invention may include an offset generation unit (61) (Offset Generation), a segment sorting unit (63) (Segmented Sort), a re-sorting unit (65) (Redistribution), a segment min-max calculation unit (67) (Segmented Minmax Calculation), and a node generation unit (69) (Parallel Node Creation). Meanwhile, at least some of the blocks of the above-described graphic processor (160) may be formed as at least one of a software module or a hardware module.

The above offset generation unit (61) can be implemented as a kernel function of the graphic processor (160). The above offset generation unit (61) can generate indexes for sorting the entire list of point cloud data by segment.

The above segment sorting unit (63) can be operated by the kernel-based Radix Sort of the graphic processor (160). The above segment sorting unit (63) can sort the entire list by segment according to the offset. By sorting by comparing from the low digits according to the Radix Sort operation, the operation speed can be improved by not performing a comparison operation.

The above rearrangement unit (65) may be configured as a kernel function of the graphic processor (160). The above rearrangement unit (65) may perform the role of reconstructing the data of the remaining axes so that the data sorted by section according to the offset fits a specific axis.

The above segment minimum-maximum calculation unit (67) may be configured as a kernel function of the graphic processor (160). The above segment minimum-maximum calculation unit (67) can obtain the maximum and minimum values of each section when the entire list of point cloud data is sorted by section.

The node generation unit (69) may be configured with the processor (150) described above in Fig. 1, but high-speed operation is possible by configuring it with the kernel function of the graphic processor (160). The node generation unit (69) may generate a tree node using a reference value. For example, when configuring 100 points into a tree, the node generation unit (69) may generate about 500,000 or more nodes as the number of nodes at the last level of the tree. The node generation unit (69) may allocate a certain space of the memory (130) in advance for node generation.

FIG. 5 is a diagram showing an example of operator definition related to tree creation according to an embodiment of the present invention.

Referring to FIG. 5, a tree generator (163) according to an embodiment of the present invention may allocate, as operator definitions for a TreeNode structure (struct), axis for an axis centerline, isLeaf for defining a branch or leaf, medianValue for defining a median value, medianIndex for defining an index, parentOffset for defining a parent offset in a tree structure, leftOffset for defining a left offset in a tree structure, rightOffset for defining a right offset in a tree structure, and aabb (AABB) for defining a bounding box.

Additionally, the structure AABB can assign minX, minY, minZ, maxX, maxY, and maxZ, which define the minimum and maximum values along the three axes of the bounding box. Additionally, the structure Point can assign the operators x, y, z, r, g, and b, for defining coordinate values and color data.

The above tree generator (163) can convert the XYZ axis values of each point into individual lists and index lists during the data preparation process. For example, the tree generator (163) can perform the conversion Indices[index] = index, Xs[index] = points[index].x, Ys[index] = points[index].y, Zs[index] = points[index].z.

FIG. 6 is a diagram showing an example of code defining the operation of an offset generation unit according to an embodiment of the present invention.

The offset generation unit (61) according to an embodiment of the present invention can generate a tree in a fixed form when the tree depth is 0 and 1. For example, the offset generation unit (61) can generate a tree with Depth 0: {0, N} when the tree depth is 0, and can generate a subtree of 0 with Depth 1: {0, N/2, N} when the tree depth is 1.

Meanwhile, the offset generation unit (61) can define an algorithm as illustrated in FIG. 6 through a kernel function of the graphic processor (160) when the tree depth is 2 or more. For example, the offset generation unit (61) can call or define the OffsetGenerationKernel function, and the variables of the OffsetGenerationKernel function can have in offsets _prev and out offsets _curr . The offset generation unit (61) can define, for each index (0...N-1), a half value of the previous index (e.g., index/2) as index _parent , a half value of the current index (e.g., (index+1)/2) as index _parent+1 , and can define offset _left as an offsets _prev [index _parent ] value, and can define offset _right as an offsets _curr [indexp _arent+1 ] value. Accordingly, if the index _parent+1 value is equal to the index _parent value, the offset _curr [index] value can be the offset _left value, and if the index _parent+1 value is not equal to the index _parent value, the offset _curr [index] value can be the [offset _left + (offset _right - offset _left )/2] value.

FIG. 7 is a diagram showing an example of code defining the operation of a segment alignment unit according to an embodiment of the present invention.

Referring to FIG. 7, the segment sorting unit (63) can apply different algorithms for each number of segments for optimization. In this regard, the segment sorting unit (63) can be defined as a SegmentedSortKernel function that takes in data, in indices, out sortedData, and out sortedIndices as arguments. If the segment size (size _seg ) is greater than 64, the segment sorting unit applies a RadixSort method that takes axis, indices, sortedAxis, and sortedIndices as arguments, and if the segment size (size _seg ) is greater than 2, it applies an InsertionSort method that takes axis, indices, sortedAxis, and sortedIndices as arguments, and otherwise, it can apply a maximum/minimum comparison method. The reference values for the above-described segment sizes can be changed. For example, the radix sort method can be applied when the segment size is greater than 2 and less than or equal to 64, the insertion sort method can be applied when the segment size is less than or equal to 2, and the maximum-minimum comparison method can be applied when the segment size exceeds 64. The segment sorting unit (63) can also sort the index list during the process of sorting by segment size.

FIG. 8 is a diagram showing an example of code defining the operation of a reordering unit according to an embodiment of the present invention.

Referring to Fig. 8, the reordering unit (65) can reorder the remaining axes according to the index of the sorted axes. In this regard, the reordering unit (65) can call the RedistributionKernel function that takes in sortedIndices, in data1, in data2, out data1 _out , and out data2 _out as arguments, or can be defined as the corresponding function. In data1 _out [index], data1[sortedIndices[Index] is written, and in data2 _out [index], data2[sortedIndices[Index] is written.

FIG. 9 is a diagram showing an example of code defining the operation of a segment minimum-maximum calculation unit according to an embodiment of the present invention.

The segment min-max calculation unit (67) can calculate the min and max values for each segment for AABB (Axis Aligned Bounding Box) calculation. In this regard, the segment min-max calculation unit (67) can call a predefined related function, for example, the SegmentedMinMaxKerenl function, which has in data, out min, and out max as arguments, or define the corresponding function. The definition of the above function can be defined as shown in Fig. 9. For example, when the globalIndex value is smaller than the index of the end value of the segment (index _segEnd ), the data function value having dataIndex as an argument can be written to the sharedMin function value having threadIndex as an argument, and the sharedMin function value having threadIndex.x as an argument can be written to the sharedMax function value having threadIndex as an argument. Meanwhile, if the value (dataIndex + blockDim.x) is smaller than the index of the end value of the segment (index _segEnd ), the axis function value that has (dataIndex + blockDim.x) as an argument is written to the v value, the minimum value (min) among sharedMin[threadIndex] and v values can be written to sharedMin[ThreadIndex], and the maximum value (max) among sharedMax[threadIndex] and v values can be written to sharedMax[ThreadIndex].

Meanwhile, if threadIndex is 0, the sharedMin[0] and sharedMax[0] values can be outMin and outMax values, respectively.

FIG. 10 is a diagram showing an example of code defining the operation of a node creation unit according to an embodiment of the present invention.

Referring to FIG. 10, the node creation unit (69) can create a tree node using the sorting result. In this regard, the node creation unit (69) can call or define a predefined ParallelNodeCreationKernel function that takes in startOffset, in offsets, in axis, in indices, in data[3], in min[3], in max[3], in isLeaf, and out nodes as arguments. In the ParallelNodeCreationKernel function, the index _parent value can be defined as an index/2 value, the offset _left value can be defined as an offsets[index]/2 value, and the offset _right value can be defined as an offset[index+1]/2 value. In addition, in the ParallelNodeCreationKernel function, a node can be defined as a nodes[startoffset.current + index] value. node.axis can contain the axis value, node.isLeaf can contain the isLeaf value, node.medianValue can contain the data[axis][offset _median ] value, node.medianIndex can contain the indices[offset _median ] value, and node.parentOffset can contain the value of startOffset.parent minus startOffset.current. node.aabb.minx can contain the min[0][index] value, node.aabb.miny can contain the min[][index] value, node.aabb.minz can contain the min[2][index] value, node.aabb.maxx can contain the max[0][index] value, node.aabb.maxy can contain the max[1][index] value, and node.aabb.maxz can contain the max[2][index] value. For the above-mentioned variable definition values, the node.offset _left value is defined as NodeCount _current if it is not isLeaf, and if it is isLeaf, the node.offset _left value can be defined as the indices[offset _left ] value. The node.offset _right value is defined as NodeCount _current +1 if it is not isLeaf, and if it is isLeaf, the node.offset _right value can be defined as the indices[offset _left -1] value.

While this specification contains details of many specific implementations, these should not be construed as limitations on the scope of any invention or what may be claimed, but rather as descriptions of features that may be unique to particular embodiments of particular inventions.

Also, although operations are depicted in the drawings in a particular order, this should not be understood to imply that the operations must be performed in the particular order illustrated or in any sequential order to achieve a desirable result, or that all of the illustrated operations must be performed. In certain cases, multitasking and parallel processing may be advantageous. Furthermore, the separation of the various system components of the embodiments described above should not be understood to require such separation in all embodiments, and it should be understood that the program components and systems described may generally be integrated together in a single software product or packaged into multiple software products.

The present description has set forth the best mode of the invention and has provided examples to illustrate the invention and to enable those skilled in the art to make and use the invention. The specification, written in this manner, is not intended to limit the invention to the specific terms set forth. Accordingly, although the invention has been described in detail with reference to the examples set forth above, those skilled in the art can make modifications, changes, and variations to the examples without departing from the scope of the invention.

Therefore, the scope of the present invention should not be determined by the described embodiments but by the claims.

100: Electronic devices
110: Communication Interface
120: Sensor
130: Memory
150: Processor
160: Graphics Processor
161: Input Point Cloud Data Provider
163: Tree Generator
165: Point Cloud Tree Array
167: Normal Estimation Section

Claims (10)

Memory for storing input point cloud data for a 3D object with three axes;
A graphics processor for processing compression of the input point cloud data;
The above graphics processor
Generate tree nodes to convert the above input point cloud data into a tree structure,
By arranging the above-generated tree nodes, normal lines are estimated in real time for the input point cloud data,
It is set to perform video-based point cloud compression on the input point cloud data based on the above estimated normal,
The above graphics processor
An offset generation unit defining a depth value of a subtree according to the depth of the above tree structure is included;
The above offset generation part
If the depth of the above tree structure is 0 and 1, assign the specified offset value to the specified subtree,
An electronic device supporting video-based point cloud compression, characterized in that when the depth of the tree structure is 2 or more, the left offset value and the right offset value of the tree structure are determined based on the index values for each of the input point cloud data. delete In the first paragraph,
The above graphics processor
An electronic device supporting video-based point cloud compression, characterized in that it includes a segment alignment unit that aligns the entire list of the input point cloud data by section based on a specific axis among the three axes according to the offset value determined by the offset generation unit. In the third paragraph,
The above segment alignment part
An electronic device supporting video-based point cloud compression, characterized in that the entire list is sorted by section based on the specific axis, and the sorting is performed in different sorting methods depending on the size of the section. In the third paragraph,
The above graphics processor
A reordering unit for reordering the segments sorted by the above segment sorting unit;
The above reordering part
An electronic device supporting video-based point cloud compression, characterized in that it divides the values sorted by the segment sorting unit, and reconstructs the values of the remaining axes excluding the specific axis to fit the specific axis, but processes them so that the size of the entire list is less than a specified value. In paragraph 5,
The above graphics processor
A segment min-max calculation unit for calculating bounding boxes for the above input point cloud data;
An electronic device supporting video-based point cloud compression, characterized in that it includes a node generation unit that allocates a tree node to be used in the tree structure based on the values sorted by the reordering unit and the values calculated by the segment minimum-maximum calculation unit. A step of receiving input point cloud data for a 3D object having three axes;
A step of creating tree nodes for converting the above input point cloud data into a tree structure;
A step of arranging the generated tree nodes to estimate normal lines in real time for the input point cloud data;
A step of performing video-based point cloud compression on the input point cloud data based on the estimated normal;
The steps to create the above tree node are
A video-based point cloud compression method, characterized in that it comprises the steps of: assigning a specified offset value to a specified subtree when the depth of the tree structure is 0 and 1, and determining a left offset value and a right offset value of the tree structure based on index values for each of the input point cloud data when the depth of the tree structure is 2 or more. delete In Article 7,
The steps to create the above tree node are
A step of the segment alignment unit aligning the entire list of the input point cloud data by section based on a specific axis among the three axes according to the determined offset value, and aligning them in different sorting methods according to the size of the section; and
A video-based point cloud compression method, characterized in that it includes a step of: a reordering unit dividing the values sorted by the segment sorting unit, and reconstructing the values of the remaining axes excluding the specific axis to fit the specific axis, while processing them so that the size of the entire list becomes less than a specified value. In Article 9,
The steps to create the above tree node are
A step for calculating the maximum and minimum values of a bounding box for the input point cloud data by a segment min-max calculation unit; and
A video-based point cloud compression method, characterized in that it includes a step of allocating the tree node to be used in the tree structure based on the values sorted by the re-sorting unit and the minimum and maximum values.

Images