POINT CLOUDS

FIELD

[001] The disclosed technology concerns compression schemes for voxelized point clouds as may be used in 3D communication systems, such as augmented-reality or virtual-reality systems.

BACKGROUND

[002] With the emergence of inexpensive consumer electronic systems for both 3D capture and 3D rendering, visual communication is on the threshold of advancing beyond traditional 2D video to immersive 3D communication systems. Dynamic 3D scene capture can be implemented using color plus depth (RGBD) cameras, while 3D

visualization can be implemented using stereoscopic monitors or near-eye displays to render the subject within a virtual or augmented reality. The processing for capture and display can be done in real time using powerful graphics processing units (GPUs).

However, representing a complex, dynamic 3D scene generates a large amount of data. Compression is therefore a highly desirable part of enabling these emerging immersive 3D systems for communication.

[003] Further, despite improvements in computer hardware, compression of 3D video is extremely time-consuming and resource-intensive in many encoding scenarios.

Accordingly, improved compression methods that reduce computational complexity (including computational speed and resource usage) while still maintaining acceptable visual quality are highly desirable.

SUMMARY

[004] In summary, the detailed description presents innovations for compressing 3D video data. The innovations described herein can help reduce the bit rate and/or distortion of 3D video encoding by selectively encoding one or more 3D-point-cloud blocks using an inter-frame coding (e.g., motion compensation) technique that allows for previously encoded/decoded frames to be used in predicting current frames being encoded. This reduction in the bit rate required for compression allows an encoder/decoder to more quickly perform compression/decompression of a point cloud frame and also reduces computational resource usage, both of which can be useful in real-time encoding/decoding scenarios. Alternatively, one or more 3D-point-cloud blocks can be encoded using an intra-frame encoding approach. The selection of which encoding mode to use can be based, for example, on a threshold that is evaluated relative to rate-distortion performance for both intra-frame and inter-frame encoding. Still further, embodiments of the disclosed technology can use one or more voxel-distortion-correction filters to correct distortion errors that may occur during voxel compression. Such filters are uniquely adapted for the particular challenges presented when compressing 3D image data. Corresponding decoding techniques are also disclosed herein.

[005] Dynamic point clouds present a new frontier in visual communication systems. Although some advances have been made with respect to compression schemes for point clouds, few (if any) advances have been made with respect to using temporal redundancies as part of an effective point cloud compression scheme. Embodiments of the disclosed technology enable the encoding of dynamic voxelized point clouds at low bit rates. In embodiments of the disclosed technology, an encoder breaks the voxelized point cloud at each frame into 3D blocks (cubes) of voxels (also referred to as "3D-point-cloud blocks"). Each 3D-point-cloud block is either encoded in intra-frame mode or is replaced by a motion-compensated version of a 3D-point-cloud block in the previous frame. The decision can be based (at least in part) on a rate-distortion metric. In this way, both the geometry and the color can be encoded with distortion, allowing for reduced bit-rates. In certain embodiments, in-loop filtering is also employed to reduce (e.g., minimize) compression artifacts caused by distortion in the geometry information. Simulations reveal that embodiments of the disclosed motion compensated coder can efficiently extend the compression range of dynamic voxelized point clouds to rates below what intra-frame coding alone can accommodate, trading rate for geometry accuracy.

[006] The innovations can be implemented as part of a method, as part of a computing device adapted to perform the method or as part of a tangible computer-readable media storing computer-executable instructions for causing a computing device to perform the method. The various innovations can be used in combination or separately.

[007] The foregoing and other objects, features, and advantages of the invention will become more apparent from the following detailed description, which proceeds with reference to the accompanying figures.

BRIEF DESCRIPTION OF THE DRAWINGS

[008] Figure 1 shows six example viewpoints of a voxelized point cloud for an imaged subject. [009] Figure 2 and its subdiagrams are schematic block diagrams illustrating how correspondences can be determined between voxels between two consecutive frames and potential problems therewith.

[010] Figure 3 shows projections from each of the six cube sides (e.g., right, left, front, back, top, bottom) for two 3D images.

[011] Figure 4 is a schematic block diagram of an example coder in accordance with embodiments of the disclosed technology.

[012] Figure 5 is a schematic block diagram illustrating an example motion

compensation scheme.

[013] Figure 6 is a graph showing the rate-distortion performance of different coding modes for a 3D block (cube)

[014] Figure 7 is a graph showing the extremes of a P-frame for completely motion- compensating the whole frame with average RD performance {R _inter ,D _jnter ) or encoding it as an I-frame with average RD performance {R _intrc D _intra ).

[015] Figure 8 is a graph showing RD plots for compressing the 56th frame of sequence "man" as a P-frame using the decompressed 55th frame as an I-frame reference.

[016] Figure 9 shows RD plots for two example sequences using correspondence-based distortion metric.

[017] Figure 10 shows RD plots for two example sequences using projection-based distortion metric.

[018] Figure 11 shows the RD plots for different frames in an example sequence indicating their LCH under a projection-based distortion metric.

[019] Figure 12 show a front projection rendering comparing MCIC against intra-coder (RAHT) for a frame in an example sequence.

[020] Figure 13 shows a similar comparison as in Figure 12 for a frame of an example sequence which was compressed using MCIC (correspondence-based distortion for mode selection) and intra coding.

[021] Figure 14 is a flowchart illustrating an example process for encoding point cloud data for a sequence of frames using aspects of the disclosed technology.

[022] Figure 15 is a flowchart illustrating another example process for encoding point cloud data for a sequence of frames using aspects of the disclosed technology.

[023] Figure 16 is a flowchart illustrating an example process for decoding point cloud data for a sequence of frames using aspects of the disclosed technology. [024] Figure 17 is a diagram of an example computing system in which some described embodiments can be implemented.

[025] Figures 18a and 18b are diagrams of example network environments in which some described embodiments can be implemented.

[026] Figures 19a and 19b are diagrams illustrating example encoders in conjunction with which some described embodiments can be implemented.

[027] Figures 20a and 20b are diagrams illustrating example decoders in conjunction with which some described embodiments can be implemented

DETAILED DESCRIPTION

I. General Considerations

[028] The detailed description presents innovations in the area of encoding 3D video data, such as voxelized point clouds. The innovations described herein can help reduce the bit rate and/or distortion of 3D video encoding by selectively encoding one or more 3D-point-cloud block using an inter-frame coding (e.g., motion compensation) technique that allows for a previously encoded/decoded 3D-point-cloud block to be used in predicting 3D-point-cloud blocks in a current frame being encoded. This reduction in the bit rate required for compression allows an encoder/decoder to more quickly perform compression/decompression of a point cloud frame and also reduces computational resource usage, both of which can be useful in real-time encoding/decoding scenarios. Alternatively, one or more 3D-point-cloud blocks can be encoded using an intra-frame encoding approach. The selection of which encoding mode to use can be based, for example, on a threshold that is evaluated relative to rate-distortion performance for both intra-frame and inter-frame encoding. Still further, embodiments of the disclosed technology can use one or more voxel-distortion-correction filters to correct distortion errors that may occur during voxel compression. Such filters are uniquely adapted for the particular challenges presented when compressing 3D image data. Corresponding decoding techniques are also disclosed herein.

[029] Although operations described herein are in places described as being performed by a video encoder or decoder, in many cases the operations can be performed by another type of media processing tool (e.g., image encoder or decoder).

[030] Various alternatives to the examples described herein are possible. For example, some of the methods described herein can be altered by changing the ordering of the method acts described, by splitting, repeating, or omitting certain method acts, etc. The various aspects of the disclosed technology can be used in combination or separately. Different embodiments use one or more of the described innovations. Some of the innovations described herein address one or more of the problems noted in the

background. Typically, a given technique/tool does not solve all such problems.

[031] As used in this application and in the claims, the singular forms "a," "an," and "the" include the plural forms unless the context clearly dictates otherwise. Additionally, the term "includes" means "comprises." Further, as used herein, the term "and/or" means any one item or combination of any items in the phrase.

II. Example Computing Systems

[032] FIG. 17 illustrates a generalized example of a suitable computer system (1700) in which several of the described innovations may be implemented. The computer system (1700) is not intended to suggest any limitation as to scope of use or functionality, as the innovations may be implemented in diverse general-purpose or special-purpose computer systems.

[033] With reference to FIG. 17, the computer system (1700) includes one or more processing units (1710, 1715) and memory (1720, 1725). The processing units (1710, 1715) execute computer-executable instructions. A processing unit can be a general- purpose central processing unit ("CPU"), processor in an application-specific integrated circuit ("ASIC") or any other type of processor. In a multi-processing system, multiple processing units execute computer-executable instructions to increase processing power. For example, FIG. 17 shows a CPU (1710) as well as a graphics processing unit or coprocessing unit (1715). The tangible memory (1720, 1725) may be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two, accessible by the processing unit(s). The memory (1720, 1725) stores software (1780) implementing one or more of the disclosed innovations for point cloud compression with motion compensation and/or filtering to help correct voxel distortion errors, and corresponding decompression, in the form of computer-executable instructions suitable for execution by the processing unit(s).

[034] A computer system may have additional features. For example, the computer system (1700) includes storage (1740), one or more input devices (1750), one or more output devices (1760), and one or more communication connections (1770). An interconnection mechanism (not shown) such as a bus, controller, or network interconnects the components of the computer system (1700). Typically, operating system software (not shown) provides an operating environment for other software executing in the computer system (1700), and coordinates activities of the components of the computer system (1700).

[035] The tangible storage (1740) may be removable or non-removable, and includes magnetic media such as magnetic disks, magnetic tapes or cassettes, optical media such as CD-ROMs or DVDs, or any other medium which can be used to store information and which can be accessed within the computer system (1700). The storage (1740) stores instructions for the software (1780) implementing one or more of the disclosed

innovations for point cloud compression with motion compensation and/or filtering to help correct voxel distortion errors, and corresponding decompression.

[036] The input device(s) (1750) may be a touch input device such as a keyboard, mouse, pen, or trackball, a voice input device, a scanning device, or another device that provides input to the computer system (1700). For point cloud data, the input device(s) (1750) may be a set of depth cameras or similar devices that capture video input used to derive point cloud data, or a CD-ROM or CD-RW that reads point cloud data into the computer system (1700). The output device(s) (1760) may be a display, printer, speaker, CD-writer, or other device that provides output from the computer system (1700). For rendering of views of reconstructed point cloud data, the output device(s) (1760) may be special glasses or other such near-eye display (e.g., an augmented-reality or virtual-reality headset), a stereoscopic display, or another viewing apparatus, to show the reconstructed point cloud data within a real scene or a synthetic scene.

[037] The communication connection(s) (1770) enable communication over a

communication medium to another computing entity. The communication medium conveys information such as computer-executable instructions, point cloud data input or encoded point could data output, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media can use an electrical, optical, RF, or other carrier.

[038] The innovations can be described in the general context of computer-readable media. Computer-readable media are any available tangible media that can be accessed within a computing environment. By way of example, and not limitation, with the computer system (1700), computer-readable media include memory (1720, 1725), storage (1740), and combinations thereof. Thus, the computer-readable media can be, for example, volatile memory, non-volatile memory, optical media, or magnetic media. As used herein, the term computer-readable media does not include transitory signals or propagating carrier waves.

[039] The innovations can be described in the general context of computer-executable instructions, such as those included in program modules, being executed in a computer system on a target real or virtual processor. Generally, program modules include routines, programs, libraries, objects, classes, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or split between program modules as desired in various embodiments. Computer-executable instructions for program modules may be executed within a local or distributed computer system.

[040] The terms "system" and "device" are used interchangeably herein. Unless the context clearly indicates otherwise, neither term implies any limitation on a type of computer system or computing device. In general, a computer system or computing device can be local or distributed, and can include any combination of special-purpose hardware and/or general-purpose hardware with software implementing the functionality described herein.

[041] The disclosed methods can also be implemented using specialized computing hardware configured to perform any of the disclosed methods. For example, the disclosed methods can be implemented by an integrated circuit (e.g., an ASIC such as an ASIC digital signal processor ("DSP"), a graphics processing unit ("GPU"), or a programmable logic device ("PLD") such as a field programmable gate array ("FPGA")) specially designed or configured to implement any of the disclosed methods.

[042] For the sake of presentation, the detailed description uses terms like "select" and "determine" to describe computer operations in a computer system. These terms are high- level abstractions for operations performed by a computer, and should not be confused with acts performed by a human being. The actual computer operations corresponding to these terms vary depending on implementation.

III. Example Network Environments.

[043] FIGS. 18a and 18b show example network environments (1801, 1802) that include encoders (1820) and decoders (1870). The encoders (1820) and decoders (1870) are connected over a network (1850) using an appropriate communication protocol. The network (1850) can include the Internet or another computer network.

[044] In the network environment (1801) shown in FIG. 18a, each real-time

communication ("RTC") tool (1810) includes both an encoder (1820) and a decoder (1870) for bidirectional communication. A given encoder (1820) can receive 3D image data (e.g., point cloud data) and produce, as output, encoded data compliant with a particular format, with a corresponding decoder (1870) accepting encoded data from the encoder (1820) and decoding it to reconstruct the 3D image data (e.g., point cloud data). The bidirectional communication can be part of a conference or other two-party or multiparty communication scenario. Although the network environment (1801) in FIG. 18a includes two real-time communication tools (1810), the network environment (1801) can instead include three or more real-time communication tools (1810) that participate in multi-party communication.

[045] A real-time communication tool (1810) manages encoding by an encoder (1820). FIGS. 19a and 19b show example encoders (1901, 1902) that can be included in the realtime communication tool (1810). Alternatively, the real-time communication tool (1810) uses another encoder. A real-time communication tool (1810) also manages decoding by a decoder (1870). FIGS. 20a and 20b show example decoders (2001, 2002) that can be included in the real-time communication tool (1810). Alternatively, the real-time communication tool (1810) uses another decoder. A real-time communication tool (1810) can also include one or more encoders and one or more decoders for other media (e.g., audio).

[046] A real-time communication tool (1810) can also include one or more capture components (not shown) that construct point cloud data based in input video received from capture devices (e.g., depth cameras). For example, the capture component(s) generate a series of frames of point cloud data for one or more objects depicted in the input video.

For a given point cloud frame, the capture component(s) process multiple video images from different perspectives of the objects (e.g., 8 video images from different perspectives surrounding the objects) to generate a point cloud in 3D space. For typical frame rates of video capture (such as 15 or 30 frames per second), frames of point cloud data can be generated in real time and provided to the encoder (1820).

[047] A real-time communication tool (1810) can also include one or more rendering components (not shown) that render views of reconstructed point cloud data. For example, the rendering component(s) generate a view of reconstructed point cloud data, from a perspective in the 3D space, for rendering in special glasses, near-eye display, stereoscopic display, or another rendering apparatus. Views of reconstructed point cloud data can be generated in real time as the perspective changes and as new point cloud data is reconstructed. [048] In the network environment (1802) shown in FIG. 18b, an encoding tool (1812) includes an encoder (1820) that receives point cloud data and encodes it for delivery to multiple playback tools (1814), which include decoders (1870). The unidirectional communication can be provided for entertainment, surveillance or monitoring, remote conferencing presentation or sharing, gaming, or other scenario in which point cloud data is encoded and sent from one location to one or more other locations. Although the network environment (1802) in FIG. 18b includes two playback tools (1814), the network environment (1802) can include more or fewer playback tools (1814). In general, a playback tool (1814) communicates with the encoding tool (1812) to determine a stream of point cloud data for the playback tool (1814) to receive. The playback tool (1814) receives the stream, buffers the received encoded data for an appropriate period, and begins decoding and playback.

[049] FIGS. 19a and 19b show example encoders (1901, 1902) that can be included in the encoding tool (1812). Alternatively, the encoding tool (1812) uses another encoder. The encoding tool (1812) can also include server-side controller logic for managing connections with one or more playback tools (1814). An encoding tool (1812) can also include one or more encoders for other media (e.g., audio) and/or capture components (not shown). A playback tool (1814) can include client-side controller logic for managing connections with the encoding tool (1812). FIGS. 20a and 20b show example decoders (2001, 2002) that can be included in the playback tool (1814). Alternatively, the playback tool (1814) uses another decoder. A playback tool (1814) can also include one or more decoders for other media (e.g., audio) and/or rendering components (not shown).

IV. Example Encoders.

[050] FIGS. 19a and 19b show example encoders (1901, 1902) in conjunction with which some described embodiments may be implemented. The encoder (1901) of FIG. 19a is used for intra-frame compression of a 3D-point-cloud block, which exploits spatial redundancy in point cloud data. The encoder (1901) of FIG. 19a can be used iteratively to compress individual 3D-point-cloud blocks from frames of point cloud data in a time series. Or, the encoder (1902) of FIG. 19b can be used for inter-frame compression of a 3D-point-cloud block in a time series of point cloud frames, which also exploits temporal redundancy between the point cloud frames in the time series. Figure 4 shows one example of an encoder in accordance with embodiments of the disclosed technology where intra-frame vs. inter-frame compression schemes are adaptively selected for encoding particular 3D blocks during compression (e.g., during real-time compression). [051] Each of the encoders (1901, 1902) can be part of a general-purpose encoding tool capable of operating in any of multiple encoding modes such as a low-latency encoding mode for real-time communication and a higher-latency encoding mode for producing media for playback from a file or stream, or it can be a special-purpose encoding tool adapted for one such encoding mode. Each of the encoders (1901, 1902) can be implemented as part of an operating system module, as part of an application library, as part of a standalone application, or using special-purpose hardware.

[052] The input buffer (1910) is memory configured to receive and store point cloud data (1905). The input buffer (1910) receives point cloud data (1905) from a source. The source can be one or more capture components that receive input video from a set of cameras (e.g., depth cameras) or other digital video source. The source produces a sequence of frames of point cloud data at a rate of, for example, 30 frames per second. As used herein, the term "frame of point cloud data" or "point cloud frame" (or sometimes just "frame") generally refers to source, coded or reconstructed point cloud data at a given instance of time. A point cloud frame can depict an entire model of objects in a 3D space at a given instance of time. Or, a point cloud frame can depict a single object or region of interest in the 3D space at a given instance of time.

[053] In the input buffer (1910), the point cloud data (1905) includes geometry data (1912) for points as well as attributes (1914) of occupied points. The geometry data (1912) includes indicators of which of the points of the point cloud data (1905) are occupied. For example, for each of the points of the point cloud data (1905), a flag value indicates whether or not the point is occupied. Alternatively, a point of the point cloud can be implicitly flagged as occupied simply by virtue of being included in a list of occupied points. An occupied point has one or more attributes (1914) in the point cloud data (1905). The attributes (1914) associated with occupied points depend on

implementation (e.g., data produced by capture components, data processed by rendering components). For example, the attribute(s) for an occupied point can include: (1) one or more sample values each defining, at least in part, a color associated with the occupied point (e.g., YUV sample values, RGB sample values, or sample values in some other color space); (2) an opacity value defining, at least in part, an opacity associated with the occupied point; (3) a specularity value defining, at least in part, a specularity coefficient associated with the occupied point; (4) one or more surface normal values defining, at least in part, direction of a flat surface associated with the occupied point; (5) a light field defining, at least in part, a set of light rays passing through or reflected from the occupied point; and/or (6) a motion vector defining, at least in part, motion associated with the occupied point. Alternatively, attribute(s) for an occupied point include other and/or additional types of information. During later stages of encoding with the encoder (1902) of FIG. 19b, the transformed value(s) for an occupied point can also include: (7) one or more sample values each defining, at least in part, a residual associated with the occupied point.

[054] An arriving point cloud frame is stored in the input buffer (1910). The input buffer (1910) can include multiple frame storage areas. After one or more of the frames have been stored in input buffer (1910), a selector (not shown) selects an individual point cloud frame to encode as the current point cloud frame. The order in which frames are selected by the selector for input to the encoder (1901, 1902) may differ from the order in which the frames are produced by the capture components, e.g., the encoding of some frames may be delayed in order, so as to allow some later frames to be encoded first and to thus facilitate temporally backward prediction. Before the encoder (1901, 1902), the system can include a pre-processor (not shown) that performs pre-processing (e.g., filtering) of the current point cloud frame before encoding. The pre-processing can include color space conversion into primary (e.g., luma) and secondary (e.g., chroma differences toward red and toward blue) components, resampling, and/or other filtering.

[055] In general, a volumetric element, or voxel, is a set of one or more co-located attributes for a location in 3D space. For purposes of encoding, attributes can be grouped on a voxel-by-voxel basis. Or, to simplify implementation, attributes can be grouped for encoding on an attribute-by-attribute basis (e.g., encoding a first component plane for luma (Y) sample values for points of the frame, then encoding a second component plane for first chroma (U) sample values for points of the frame, then encoding a third component plane for second chroma (V) sample values for points of the frame, and so on). Typically, the geometry data (1912) is the same for all attributes of a point cloud frame - each occupied point has values for the same set of attributes. Alternatively, however, different occupied points can have different sets of attributes.

[056] The encoder (1901, 1902) can include a tiling module (not shown) that partitions a point cloud frame into tiles of the same size or different sizes. For example, the tiling module splits the frame along tile rows, tile columns, etc. that, with frame boundaries, define boundaries of tiles within the frame, where each tile is a rectangular prism region. Tiles can be used to provide options for parallel processing or spatial random access. The content of a frame or tile can be further partitioned into blocks or other sets of points for purposes of encoding and decoding. In general, a "block" of point cloud data (also referred to as a "3D-point-cloud block") is a set of points in an xxyx z rectangular prism. Points of the block may be occupied or not occupied. When attributes are organized in an attribute-by-attribute manner, the values of one attribute for occupied points of a block can be grouped together for processing.

[057] The encoder (1901, 1902) also includes a general encoding control (not shown), which receives the current point cloud frame as well as feedback from various modules of the encoder (1901, 1902). Overall, the general encoding control provides control signals to other modules (such as the intra/inter switch (1938), tiling module, transformer (1940), inverse transformer (1945), quantizer (1950), inverse quantizer (1955), motion estimator (1972), and entropy coder(s) (1980)) to set and change coding parameters during encoding. The general encoding control can evaluate intermediate results during encoding, typically considering bit rate costs and/or distortion costs for different options. In particular, in the encoder (1902) of FIG. 19b, the general encoding control decides whether to use intra-frame compression or inter-frame compression for attributes of occupied points in blocks of the current point cloud frame. For example, any of the compression mode selection techniques described below in Section VI.D can be used. The general encoding control produces general control data that indicates decisions made during encoding, so that a corresponding decoder can make consistent decisions. The general control data is provided to the multiplexer (1990).

[058] With reference to FIG. 19a, the encoder (1901) receives point cloud data (1905) from the input buffer (1910) and produces encoded data (1995) using intra-frame compression, for output to the output buffer (1992). The encoder (1901) includes an octtree coder (1920), a region-adaptive hierarchical transformer (1940), a quantizer (1950), one or more entropy coders (1980), and a multiplexer (1990).

[059] As part of receiving the encoded data (1905), the encoder (1901) receives the geometry data (1912), which is passed to the octtree coder (1920) and region-adaptive hierarchical transformer (1940). The octtree coder (1920) compresses the geometry data (1912). For example, the octtree coder (1920) applies lossless compression to the geometry data (1912). Alternatively, the octtree coder (1920) compresses the geometry data (1912) in some other way (e.g., lossy compression, in which case a reconstructed version of the geometry data (1912) is passed to the region-adaptive hierarchical transformer (1940) instead of the original geometry data (1912)). The octtree coder (1920) passes the compressed geometry data to the multiplexer (1990), which formats the compressed geometry data to be part of the encoded data (1995) for output.

[060] As part of receiving the encoded data (1905), the encoder (1901) also receives the attributes (1914), which are passed to the region-adaptive hierarchical transformer (1940). The region-adaptive hierarchical transformer (1940) uses the received geometry data (1912) when deciding how to apply a RAHT to attributes (1914). For example, the region-adaptive hierarchical transformer (1940) applies a RAHT to the attributes (1914) of occupied points. Alternatively, the region-adaptive hierarchical transformer (1940) applies a RAHT that is region-adaptive (processing attributes for occupied points) and hierarchical (passing coefficients from one level to another level for additional processing) in some other way. The region-adaptive hierarchical transformer (1940) passes the transform coefficients resulting from the RAHT to the quantizer (1950).

[061] The quantizer (1950) quantizes the transform coefficients. For example, the quantizer (1950) applies uniform scalar quantization to the transform coefficients.

Alternatively, the quantizer (1950) applies quantization in some other way. The quantizer (1950) can change the quantization step size on a frame-by-frame basis. Alternatively, the quantizer (1950) can change the quantization step size on a tile-by-tile basis, block-by- block basis, or other basis.

[062] The quantization step size can depend on a quantization parameter ("QP"), whose value is set for a frame, tile, block, and/or other portion of point cloud data. The quantizer (1950) passes the quantized transform coefficients to the one or more entropy coders (1980).

[063] The entropy coder(s) (1980) entropy code the quantized transform coefficients. When entropy coding the quantized transform coefficients, the entropy coder(s) (1980) can use arithmetic coding, run-length Golomb-Rice coding, or some other type of entropy coding (e.g., Exponential-Golomb coding, variable length coding, dictionary coding). Alternatively, the entropy coder(s) (1980) apply some other form of adaptive or non- adaptive entropy coding to the quantized transform coefficients. The entropy coder(s) (1980) can also encode general control data, QP values, and other side information (e.g., mode decisions, parameter choices). For the encoder (1902) of FIG. 19b, the entropy coder(s) (1980) can encode motion data (1978). The entropy coder(s) (1980) can use different coding techniques for different kinds of information, and they can apply multiple techniques in combination. The entropy coder(s) (1980) pass the results of the entropy coding to the multiplexer (1990), which formats the coded transform coefficients and other data to be part of the encoded data (1995) for output. When the entropy coder(s) (1980) use parameters to adapt entropy coding (e.g., estimates of distribution of quantized transform coefficients for buckets), the entropy coder(s) (1980) may also code the parameters and pass them to the multiplexer (1990), which formats the coded parameters to be part of the encoded data (1995).

[064] With reference to FIG. 19b, the encoder (1902) further includes an inverse quantizer (1955), inverse region-adaptive hierarchical transformer (1945), motion compensator (1970), motion estimator (1972), reference frame buffer (1974), and intra/inter switch (1938). The octtree coder (1920) operates as in the encoder (1901) of FIG. 19a. The region-adaptive hierarchical transformer (1940), quantizer (1950), and entropy coder(s) (1980) of the encoder (1902) of FIG. 19b essentially operate as in the encoder (1901) of FIG. 19a, but may process residual values for any of the attributes of occupied points.

[065] When a block of the current point cloud frame is compressed using inter-frame compression, the motion estimator (1972) estimates the motion of attributes of the block with respect to one or more reference frames of point cloud data. The current point cloud frame can be entirely or partially coded using inter-frame compression. The reference frame buffer (1974) buffers one or more reconstructed previously coded/decoded point cloud frames for use as reference frames. When multiple reference frames are used, the multiple reference frames can be from different temporal directions or the same temporal direction. As part of the general control data, the encoder (1902) can include information that indicates how to update the reference frame buffer (1974), e.g., removing a reconstructed point cloud frame, adding a newly reconstructed point cloud frame.

[066] The motion estimator (1972) produces motion data (1978) as side information. The motion data (1978) can include motion vector ("MV") data and reference frame selection data. The motion data (1978) is provided to one of the entropy coder(s) (1980) or the multiplexer (1990) as well as the motion compensator (1970). The motion compensator (1970) applies MV(s) for a block to the reconstructed reference frame(s) from the reference frame buffer (1974). For the block, the motion compensator (1970) produces a motion-compensated prediction, which is a region of attributes in the reference frame(s) that are used to generate motion-compensated prediction values (1976) for the block.

[067] As shown in FIG. 19b, the intra/inter switch (1938) selects whether a given block is compressed using intra-frame compression or inter-frame compression. Intra/inter switch (1938) decisions for blocks of the current point cloud frame can be made using various criteria.

[068] When inter-frame compression is used for a block, the encoder (1902) can determine whether or not to encode and transmit the differences (if any) between prediction values (1976) and corresponding original attributes (1914). The differences (if any) between the prediction values (1976) and corresponding original attributes (1914) provide values of the residual. If encoded/transmitted, the values of the prediction residual are encoded using the region-adaptive hierarchical transformer (1940), quantizer (1950), and entropy coder(s) (1980), as described above, with reference to FIG. 19a. (In practice, calculating the differences between the prediction values (1976) and corresponding original attributes (1914) may be difficult because the number of points in the prediction block and original block may not be the same. In this case, since simple arithmetic differencing is not possible on a point-by-point basis, the original attributes can be subtracted from estimates of corresponding prediction values. Or, to avoid this problem, the prediction residual values are not encoded at all. In this case, paths and components of the encoder (1902) used to determine the prediction residual values and add reconstructed residual values to prediction values (1976) can be omitted. Such paths and components, including the differencing module, switch (1938), and addition module, are shown as optional in FIG. 19b.)

[069] In the encoder (1902) of FIG. 19b, a decoding process emulator implements some of the functionality of a decoder. The decoding process emulator determines whether a given frame needs to be reconstructed and stored for use as a reference frame for inter- frame compression of subsequent frames. For reconstruction, the inverse quantizer (1955) performs inverse quantization on the quantized transform coefficients, inverting whatever quantization was applied by the quantizer (1950). The inverse region-adaptive

hierarchical transformer (1945) performs an inverse RAHT, inverting whatever RAHT was applied by the region-adaptive hierarchical transformer (1940), and thereby producing blocks of reconstructed residual values (if inter-frame compression was used) or reconstructed attributes (if intra-frame compression was used). When inter-frame compression has been used (inter path at switch (1939)), reconstructed residual values, if any, are combined with the prediction values (1976) to produce a reconstruction (1948) of the attributes of occupied points for the current point cloud frame. (If the encoder (1902) does not encode prediction residual values, for reasons explained above, the prediction values (1976) can be directly used as the reconstructed attributes (1948), bypassing the addition component.) When intra-frame compression has been used (intra path at switch (1939)), the encoder (1902) uses the reconstructed attributes (1948) produced by the inverse region-adaptive hierarchical transformer (1945). The reference frame buffer (1974) stores the reconstructed attributes (1948) for use in motion-compensated prediction of attributes of subsequent frames. The reconstructed attributes (1948) can be further filtered by an in-loop post-processing unit (1946) (e.g., one or more voxel -distortion- correction filters, such as any of the filters described in more detail below (for instance, those described in Section VI.D.5), can be applied). A filtering control (not shown) can determine how the in-loop post-processing unit (1946) performs filtering on reconstructed attributes (1948), and one or more filters associated with the in-loop post-processing unit (1946) can perform the filtering. The filtering control can produce filter control data, which is provided to the entropy coder(s) (1980) and multiplexer (1990).

[070] The output buffer (1992) is memory configured to receive and store the encoded data (1995). The encoded data (1995) that is aggregated in the output buffer (1990) can also include metadata relating to the encoded data. The encoded data can be further processed by a channel encoder (not shown), which can implement one or more media system multiplexing protocols or transport protocols. The channel encoder provides output to a channel (not shown), which represents storage, a communications connection, or another channel for the output.

[071] Depending on implementation and the type of compression desired, modules of the encoders (1901, 1902) can be added, omitted, split into multiple modules, combined with other modules, and/or replaced with like modules. In alternative embodiments, encoders with different modules and/or other configurations of modules perform one or more of the described techniques. Specific embodiments of encoders typically use a variation or supplemented version of one of the encoders (1901, 1902). The relationships shown between modules within the encoders (1901, 1902) indicate general flows of information in the respective encoders (1901, 1902); other relationships are not shown for the sake of simplicity. In general, a given module of the encoders (1901, 1902) can be implemented by software executable on a CPU, by software controlling special -purpose hardware (e.g., graphics hardware for video acceleration), or by special-purpose hardware (e.g., in an ASIC).

V. Example Decoders.

[072] FIGS. 20a and 20b show example decoders (2001, 2002) in conjunction with which some described embodiments may be implemented. The decoder (2001) of FIG. 20a is used for intra-frame decompression of a 3D-point-cloud block, and it can be used iteratively to decompress 3D-point-cloud blocks in individual frames of point cloud data in a time series. Or, the decoder (2002) of FIG. 20b can be used for inter-frame decompression of a 3D-point-cloud block in a time series of point cloud frames.

[073] Each of the decoders (2001, 2002) can be a general -purpose decoding tool capable of operating in any of multiple decoding modes such as a low-latency decoding mode for real-time communication and a higher-latency decoding mode for media playback from a file or stream, or it can be a special-purpose decoding tool adapted for one such decoding mode. Each of the decoders (2001, 2002) can be implemented as part of an operating system module, as part of an application library, as part of a standalone application or using special-purpose hardware.

[074] The input buffer (2092) is memory configured to receive and store encoded data (2095). The input buffer (2092) receives the encoded data (2095) from a channel, which can represent storage, a communications connection, or another channel for encoded data as input. The channel produces encoded data (2095) that has been channel coded. A channel decoder (not shown), implementing one or more media system demultiplexing protocols or transport protocols, can process the channel coded data. The encoded data (2095) that is output from the channel decoder is stored in the input buffer (2092) until a sufficient quantity of such data has been received. The encoded data (2095) that is aggregated in the input buffer (2092) can include metadata relating to the encoded data. In general, the input buffer (2092) temporarily stores encoded data (2095) until such encoded data (2095) is used by the decoder (2001, 2002). At that point, encoded data for a coded point cloud frame is transferred from the input buffer (2092) to the decoder (2001, 2002). As decoding continues, new encoded data (2095) is added to the input buffer (2092) and the oldest encoded data (2095) remaining in the input buffer (2092) is transferred to the decoder (2001, 2002).

[075] In the input buffer (2092), the encoded data (2095) includes encoded data for geometry data (2012) as well as encoded data for attributes (2014) of occupied points. The geometry data (2012) includes indicators of which of the points of the reconstructed point cloud data (2005) are occupied (that is, have at least one attribute). For example, for each of the points, a flag value indicates whether or not the point is occupied. An occupied point has one or more attributes (2014) in the reconstructed point cloud data (2005). The attributes (2014) associated with occupied points depend on implementation (e.g., data produced by capture components, data processed by rendering components). For example, the attribute(s) for an occupied point can include: (1) one or more sample values each defining, at least in part, a color associated with the occupied point (e.g., YUV sample values, RGB sample values, or sample values in some other color space); (2) an opacity value defining, at least in part, an opacity associated with the occupied point; (3) a specularity value defining, at least in part, a specularity coefficient associated with the occupied point; (4) one or more surface normal values defining, at least in part, direction of a flat surface associated with the occupied point; (5) a light field defining, at least in part, a set of light rays passing through or reflected from the occupied point; and/or (6) a motion vector defining, at least in part, motion associated with the occupied point.

Alternatively, attribute(s) for an occupied point include other and/or additional types of information. For decoding with the decoder (2002) of FIG. 20b, the transform value(s) for an occupied point can also include: (7) one or more sample values each defining, at least in part, a residual associated with the occupied point.

[076] For purposes of decoding, attributes can be grouped on a voxel-by-voxel basis. Or, to simplify implementation, attributes can be grouped for decoding on an attribute-by- attribute basis (e.g., decoding a first component plane for luma (Y) sample values for points of the frame, then decoding a second component plane for first chroma (U) sample values for points of the frame, then decoding a third component plane for second chroma (V) sample values for points of the frame, and so on). Typically, the geometry data (2012) is the same for all attributes of a point cloud frame - each occupied point has values for the same set of attributes. Alternatively, however, different occupied points can have different sets of attributes.

[077] With reference to FIG. 20a, the decoder (2001) receives encoded data (2095) from the input buffer (2092) and produces reconstructed point cloud data (2005) using intra- frame decompression, for output to the output buffer (2010). The decoder (2001) includes an octtree decoder (2020), an inverse region-adaptive hierarchical transformer (2045), an inverse quantizer (2055), one or more entropy coders (2080), and a demultiplexer (2090). For purposes of decoding, a point cloud frame can be organized into multiple tiles of the same size or different sizes. The content of a point cloud frame or tile can be further organized as blocks or other sets of sample values.

[078] The demultiplexer (2090) receives encoded data (2095) and parses elements of the encoded data (2095) from a bitstream. The demultiplexer (2090) makes the received encoded data (2095) available to one or more entropy decoders (2080) and/or other modules of the decoder (2001). [079] The entropy decoder(s) (2080) entropy decode the quantized transform

coefficients. When entropy decoding the quantized transform coefficients, the entropy decoder(s) (2080) can use arithmetic decoding, run-length Golomb-Rice decoding, or some other type of entropy decoding (e.g., Exponential-Golomb decoding, variable length decoding, dictionary decoding). Alternatively, the entropy decoder(s) (2080) apply some other form of adaptive or non-adaptive entropy decoding to the quantized transform coefficients. The entropy decoder(s) (2080) can also decode general control data, QP values, and other side information (e.g., mode decisions, parameter choices). The entropy decoder(s) (2080) can use different decoding techniques for different kinds of information, and they can apply multiple techniques in combination. When the entropy decoder(s) (2080) use parameters to adapt entropy decoding (e.g., estimates of distribution of quantized transform coefficients for buckets), the entropy decoder(s) (2080) also decode the parameters before decoding the quantized transform coefficients.

[080] The decoder (2001) includes a general decoding control (not shown), which receives general control data from the demultiplexer (2090) and/or entropy decoder(s) (2080). The general decoding control provides control signals (not shown) to other modules (such as the inverse quantizer (2055), inverse region-adaptive hierarchical transformer (2045), and entropy decoder(s) (2080)) to set and change decoding parameters during decoding.

[081] The octtree decoder (2020) receives compressed geometry data from the demultiplexer (2090) or entropy decoder(s) (2080) and decompresses the geometry data (2012). The octtree decoder (2020) passes the geometry data (2012) to the output buffer (2010) and to the inverse region-adaptive hierarchical transformer (2045). For example, the octtree decoder (2020) applies lossless decompression to the compressed geometry data. Alternatively, the octtree decoder (2020) decompresses the geometry data (2012) in some other way (e.g., lossy decompression, in which case a lossy-reconstructed version of the geometry data (2012) is passed to the inverse region-adaptive hierarchical transformer (2045)).

[082] The inverse quantizer (2055) receives quantized transform coefficients from the entropy decoders (2080) and inverse quantizes the transform coefficients. For example, the inverse quantizer (2055) inverts uniform scalar quantization previously applied to the transform coefficients. Alternatively, the inverse quantizer (2055) performs inverse quantization in some other way. Based on QPs that it receives, the inverse quantizer (2055) can change the quantization step size on a frame-by-frame basis. Alternatively, the inverse quantizer (2055) can change the quantization step size on a tile-by-tile basis, block-by-block basis, or other basis. The inverse quantizer (2055) passes the transform coefficients to the inverse region-adaptive hierarchical transformer (2045).

[083] With the geometry data (2012) received from the octtree decoder (2020) and the transform coefficients received from the inverse quantizer (2045), the inverse region- adaptive hierarchical transformer (2045) applies an inverse RAHT to the transform coefficients to reconstruct attributes (2014) of occupied points. The inverse region- adaptive hierarchical transformer (2045) uses the received geometry data (2012) when deciding how to apply the inverse RAHT to reconstruct attributes (2014). For example, the inverse region-adaptive hierarchical transformer (2045) applies an inverse RAHT to reconstruct attributes (2014) of occupied points. Alternatively, the inverse region-adaptive hierarchical transformer (2045) applies an inverse RAHT that is region-adaptive

(processing attributes for occupied points) and hierarchical (passing attributes from one level to another level for additional processing) in some other way. In FIG. 20a, the inverse region-adaptive hierarchical transformer (2045) passes the reconstructed attributes (2014) resulting from the inverse RAHT to the output buffer (2010).

[084] With reference to the decoder (2002) of FIG. 20b, the octtree decoder (2020) operates as in the decoder (2001) of FIG. 20a. The inverse region-adaptive hierarchical transformer (2045), inverse quantizer (2055), and entropy decoder(s) (2080) of the decoder (2002) of FIG. 20b essentially operate as in the decoder (2001) of FIG. 20a, but may process residual values for any of the attributes of occupied points. Also, for the decoder (2002) of FIG. 20b, the entropy decoder(s) (2080) can decode motion data (2078). The decoder (2002) of FIG. 20b further includes an intra/inter switch (2039), a motion compensator (2070), and a reference frame buffer (2074). In addition to other control functions, a general decoding control provides control signals to the intra/inter switch

(2039), motion compensator (2070), and reference frame buffer (2074)) to set and change decoding parameters during decoding.

[085] The decoder (2002) of FIG. 20b determines whether a given point cloud frame needs to be stored for use as a reference frame for inter-frame decompression of subsequent frames. The reference frame buffer (2074) buffers one or more reconstructed previously decoded point cloud frames for use as reference frames. When multiple reference frames are used, the multiple reference frames can be from different temporal directions or the same temporal direction. As part of the general control data, the decoder (2002) can receive information that indicates how to update the reference frame buffer (2074), e.g., removing a reconstructed point cloud frame, adding a newly reconstructed point cloud frame.

[086] As shown in FIG. 20b, the intra/inter switch (2039) selects whether a given block is decompressed using intra-frame decompression or inter-frame decompression.

Intra/inter switch (2039) decisions for blocks of the current point cloud frame can be indicated in syntax elements (or other bitstream elements) of the bitstream, decoded by the decoder, and converted into appropriate control data. The current point cloud frame can be entirely or partially decoded using inter-frame decompression. The inverse region- adaptive hierarchical transformer (2045) can produce blocks of reconstructed residual values (if inter-frame decompression is used) or reconstructed attributes (if intra-frame decompression is used). When inter-frame decompression is used (inter path at switch (2039)), reconstructed residual values, if any, are combined with the prediction values (2076) to produce a reconstruction of the attributes of occupied points for the current point cloud frame. (If the encoder (2002) does not encode prediction residual values, for reasons explained above, then the decoder (2002) does not decode any prediction residual values. In this case, the prediction values (2076) can be directly used as the reconstructed attributes, bypassing the addition component. The path to the addition component, and the addition component, are shown as optional in FIG. 20b.) When intra-frame compression is used (intra path at switch (2039)), the decoder (2002) uses the reconstructed attributes produced by the inverse region-adaptive hierarchical transformer (2045). The reference frame buffer (2074) stores the reconstructed attributes for use in motion-compensated prediction of attributes of subsequent frames. The reconstructed attributes can be further filtered by an in-loop post-processing unit (1946) (e.g., one or more voxel -distortion- correction filters, such as any of the filters described in more detail below (for instance, those described in Section VI. D.5), can be applied). The filtering can be performed based on filter control data, which is provided by the entropy decoder(s) (2080) or demultiplexer (2090).

[087] The motion compensator (2070) receives motion data (2078) from the entropy decoder(s) (2080) or demultiplexer (2090). The motion data (2078) can include MV data and reference frame selection data. The motion compensator (2070) applies MV(s) for a block to the reconstructed reference frame(s) from the reference frame buffer (2074). For the block, the motion compensator (2070) produces a motion-compensated prediction, which is a region of attributes in the reference frame(s) that are used to generate motion- compensated prediction values (2076) for the block. [088] The output buffer (2010) is memory configured to receive and store reconstructed point cloud data (2005). For the reconstructed point cloud data (2005), the decoder (2001, 2002) outputs geometry data (2012) and reconstructed attributes (2014) for occupied points to the output buffer (2010). The output buffer (2010) provides the reconstructed point cloud data (2005) to a sink, e.g., one or more rendering components that generate one or more views of the reconstructed point cloud data (2005). The output buffer (2010) can include multiple frame storage areas. An output sequencer (not shown) can identify when the next point cloud frame to be produced in output order is available in the output buffer (2010). When the next point cloud frame to be produced in output order is available in the output buffer (2010), it is read by the output sequencer and output to the sink. In general, the order in which point cloud frames are output from the output buffer (2010) may differ from the order in which the point cloud frames are decoded by the decoder (2001, 2002) (bitstream order).

[089] Also, after the decoder (2001, 2002), the system can include a post-processor (not shown) that performs post-processing (e.g., filtering) of the current point cloud frame after decoding. For example, the post-processing can include applying any of the voxel- distortion-correction filters described below (e.g., the morphological and/or adaptive filters described below). The post-processing can include color space conversion from primary (e.g., luma) and secondary (e.g., chroma) components to another color space (e.g., RGB), resampling, and/or other filtering. Thus, the decoder (2001, 2002) can include a post-processing filter. Whereas "in-loop" filtering is performed on reconstructed attributes in a motion compensation loop, and hence affects attributes of reference frames, the postprocessing filter is applied to reconstructed attributes outside of the motion compensation loop, before output for rendering.

[090] Depending on implementation and the type of decompression desired, modules of the decoders (2001, 2002) can be added, omitted, split into multiple modules, combined with other modules, and/or replaced with like modules. In alternative embodiments, decoders with different modules and/or other configurations of modules perform one or more of the described techniques. Specific embodiments of decoders typically use a variation or supplemented version of one of the decoders (2001, 2002). The relationships shown between modules within the decoders (2001, 2002) indicate general flows of information in the respective decoders (2001, 2002); other relationships are not shown for the sake of simplicity. In general, a given module of the decoders (2001, 2002) can be implemented by software executable on a CPU, by software controlling special-purpose hardware (e.g., graphics hardware for video acceleration), or by special-purpose hardware (e.g., in an ASIC).

VI. Exemplary Compression Methods for Voxelized Point Clouds

[091] Disclosed below are example methods that can be performed by an encoder to compress 3D video data, and voxelized point clouds in particular. Also disclosed are corresponding decompression methods that can be performed by a decoder to decompress the 3D video data.

A. Introduction and Overview

[092] There are many choices for representing 3D data, and the most appropriate choice depends on the situation. For example, dense voxel arrays may be good for representing dense volumetric medical data, while polygonal meshes may be good for representing surfaces of 3D objects typically found in computer graphics. Point clouds are well-suited to sample real world objects for which the data are volumetrically sparse, especially if the topology is not necessarily a 2D manifold. An alternative to point clouds are sparse voxel arrays, or voxel clouds, which are arbitrary collections of voxels. Unlike points, voxels have a volumetric aspect, which can be highly useful in certain scenarios. Point clouds and sparse voxel arrays obviate some of the common problems that 2D manifolds have, such as dealing with boundary conditions on cut edges, and topological changes over time. Yet another possible representation of 3D data is simply a set of color and depth maps, sometimes called multiview video plus depth (MVD). Such a set is a low-level representation close to the RGBD sensors. Closely related to color and depth maps are elevation maps and multi-level surface maps.

[093] Embodiments of the disclosed technology concern sparse voxel arrays, which are also referred to as "voxelized point clouds" in this disclosure. Such usage should not be construed as limiting, however, as the principles of the disclosed technology can be adapted for other types of 3D representations. Neglecting the volumetric aspect of voxels, voxelized point clouds can be considered simply as point clouds whose points are restricted to lie on a regular 3D grid or lattice. For example, Figure 1 shows six example viewpoints (100, 102, 104, 106, 108, 1 10) of a voxelized point cloud for an imaged subject. In particular, as mentioned above, for the kinds of data expected in 3D scene capture, voxelized point clouds are a more natural fit than dense voxels arrays, and they obviate the kinds of problems that polygonal meshes have with sampled data. Compared to color and depth maps, voxelized point clouds are a higher level representation, in that redundancies and inconsistencies between overlapping sensor maps have already been removed in a multi-camera sensor fusion step. Compared to arbitrary point clouds, voxelized point clouds have implementation advantages and are highly efficient for realtime processing of captured 3D data.

[094] Each type of representation typically employs its own compression technique. For voxelized point cloud representations, some compression schemes are based on an orthogonal graph transform and arithmetic coding of carefully modeled coefficients. The graph transform would appear to be a natural choice for the spatial transform of the color signal due to the irregular domain of definition of the signal. Unfortunately, the graph transform requires repeated eigen-decompositions of many and/or large graph Laplacians, rendering the approach infeasible for real-time processing.

[095] To overcome these drawbacks, an encoder using a region-adaptive hierarchical transform (RAHT) approach can be used to perform intra-frame compression. Such an approach, hereinafter referred to as the "RAHT" approach, can be used with embodiments of the disclosed technology and are described in more detail in U.S. Patent Application No. 15/168,016, filed on May 28, 2016, and entitled "REGION- ADAPTIVE

HIERARCHICAL TRANSFORM AND ENTROPY CODING FOR POINT CLOUD COMPRESSION, AND CORRESPONDING DECOMPRESSION"; U.S. Patent

Application No. 15/168,017, filed on May 28, 2016, and entitled "SCALABLE POINT CLOUD COMPRESSION WITH TRANSFORM, AND CORRESPONDING

DECOMPRESSION"; and in R. L. de Queiroz and P. A. Chou, "Compression of 3D Point Clouds Using a Region-Adaptive Hierarchical Transform," IEEE Transactions on Image Processing (2016). The RAHT approach is specially developed for point clouds and, as noted, is used as a building block for certain example 3D video compression frameworks described herein. The disclosed technology is not limited to the use of RAHT, however, as other intra-frame compression schemes can also be used with any of the disclosed embodiments.

B. Voxelized Point Clouds

[096] The embodiments disclosed below primarily concern voxelized point clouds, but can be adapted for use with other types of 3D data. In the specific embodiments disclosed below, 3D data is represented by voxelized point clouds. A point cloud is a set of points {v} , each point v having a spatial position (x, y, z) and a vector of attributes, such as colors, normals, or curvature. In this disclosure, it is assumed that the attributes are colors represented as (Y,U, V) tuples in YUV color space. A point cloud may be voxelized by quantizing the point positions to a regular lattice (e.g., with the point position

corresponding to a predetermined location within or on the surface or corner of the volume represented by the voxel). A quantization cell, or voxel, is said to be occupied if it contains a point in the point cloud and is unoccupied otherwise. (A polygonal mesh may be likewise voxelized, in which case a voxel is occupied if and only if it contains a point of the surface.) An occupied voxel derives its color from the color(s) of the point(s) within the voxel, possibly by averaging or other technique. Here, it is assumed that each occupied voxel has a color.

[097] Without loss of generality, it can be assumed that the voxels are addressed by positions in the integer lattice l _w , where Z _w = {0, ..., W - 1 } , W = 2° is its width, and D is an integer. Thus, x, y, z can be considered as D -bit unsigned integers. These are analogous to row and column indices in ordinary 2D image processing. Similarly, Y, U, and J ⁷ can be considered to be 8-bit unsigned integers. Thus, for purposes of this disclosure, a voxelized point cloud is a finite set or arbitrarily indexed list of occupied voxels {v in which each voxel:

ν, ^χ,,γ, , ζ, , Υ,,υ,,ν,] (1) comprises a unique integer spatial location (x^ y^ z^ and an integer color vector

(Χ,,υ,,ν,) .

[098] Embodiments of the disclosed technology are specially adapted for live video and dynamic point clouds. Thus, at every discrete time t , a frame F(t) = {v _rt } can be defined as a list of voxels:

[099] Note that different frames may be represented by different lists of voxels, so there is no real relation between v _{i t} and v _{i t+l} , since the indexing of the voxels in the lists is arbitrary. Moreover, different frames may have different numbers of occupied voxels [0100] It can be assumed that each voxel v _{i t+l} ≡ F(t + 1) can be assigned to a corresponding voxel v _]t e F(t) . Intuitively, one expects voxels to be shifted locally from one frame to another, due to more or less rigid translational motion, as illustrated in Figures 2(a) and Figure 2(b). However, since the shifts are not exactly rigid, in general this is a many -to-one mapping from F(t + 1) to F(t) . This mapping may be described by a II F(t + \) 11 x 11 F(t) || matrix S(t) = {¾ } where s _jjt = 1 if the z ^' -th voxel at frame t + l corresponds to the j -th voxel in frame t , and is 0 otherwise. (Here, || F(t) || is the number of occupied voxels in F(t) .) If all the row vectors are stacked with the geometry information G(t) = { [Xj _t , y _Jt , z _jt ]} and the same is done with the colors C(t) = { [Y _jt , U _jt , V _jt ] } , the geometry and color correspondence residues may be written: E _g = G(i + l) - S( G( , (3)

E _c = C(t + l) - S(t)C(t). (4)

[0101] Note that the geometry residues may be considered motion vectors, while the color residues may be considered color prediction errors.

[0102] One way to find an appropriate correspondence S(t) is to minimize (or otherwise reduce) a distortion measure based on these residues, for example by minimizing (or reducing):

S = a _g \\ E _g \\ ² +a _c \\ E _c \\\ (5) where a _g and a _c are multipliers indicating the relative importance of the magnitudes of the color and geometry residues.

[0103] Minimizing (or otherwise reducing) both geometry and color residuals is useful in embodiments of the disclosed compression schemes. However, such schemes are not immune from possible error.

[0104] In this regard, Figure 2 and its subdiagrams are schematic block diagrams (200, 202, 204, 206) illustrating how correspondences can be determined between voxels between two consecutive frames. The diagrams (200, 202, 204, 206) also illustrate particular problems that may arise when determining correspondences. In the diagrams (200, 202, 204, 206), the grey circles illustrate example points (or voxels) in F(t) , while the white circles represent points or voxels in F(t + 1) (the next consecutive frame).

[0105] As illustrated in Figure 2(a) (diagram 200), even for a simple linear motion, a Euclidean-distance criterion may lead to a non-uniform correspondence field, where voxel (201) is found to not have a corresponding voxel in the frame F(t + 1) .

[0106] Figure 2(b) (diagram 202) illustrates voxels in consecutive frames that are misaligned, which can happen often in real-world scenarios.

[0107] Figure 2(c) (diagram 204) shows how a stray voxel, for example created by noise, can act as a "lightning rod" attracting all local correspondence when the "true"

correspondences are from the leftward-most set of voxels in Figure 2(c). In more detail, if only geometry were considered, then the minimization (reduction) of Expression (5) would result in the assignment to each voxel v, _t+l e F(t + 1) the voxel v _]t e F{t) whose position is closest in Euclidean space, often resulting in poor correspondences, including "lightning rods," as illustrated by schematic block diagram (204) in Figure 2(c), where closest voxel (205) is mistakenly assigned as corresponding to the five voxels in the next frame.

[0108] Figure 2(d) (diagram 206) illustrates how correspondence based on color can lead to unpredictable fields, since associations can be made to any voxel far away as long as it has a similar color. (In diagram (206), the voxel (210) is determined to have the color closest to the color of the voxel (212) in the next consecutive frame, despite it being relatively distal to the voxel (212)). More specifically, if only color were considered, then the minimization (reduction) of Expression (5) would result in the assignment to each voxel v, _t+l G F(t + 1) the voxel v _]t e F{t) whose color is closest in color space. In effect, the voxels in F(t + 1) would simply use the voxels in F(t) as colors in a palette, and the correspondences would be chaotic, as illustrated by schematic block diagram (206) in Figure 2(d), where a voxel (210) that is relatively distance from the determined- corresponding voxel (212) is identified for correspondence purposes.

[0109] Smoothness of the corresponding field is another useful feature in determining correspondence (in addition to the magnitudes of the geometry and color residuals).

Hence, a geometry residual smoothness term can be included as part of the

correspondence determination. One example correspondence determination that combines a geometry residual smoothness term along with a color component and a geometry component is:

S = a _c \\ E _e II ² +a _g \\ E _g || ² +a _s tr(E _g ^T L(t + \)E _g ), (6) where L(t + 1) is a Laplacian operator, whose quadratic form is the weighted sum of squared differences between the values at each voxel and its neighbors, and the trace operator simply sums up the separate contributions for x, y , and z components. There is evidence that humans perceive correspondence in terms of smoothed motion; hence the smoothness term is a good way to select correspondences that match human perception.

[0110] Recognizing that there is much existing work on determining correspondence fields for a 3D flow, this disclosure assumes that a suitable motion estimation approach is available and can be applied to the native 3D image data being compressed in order to produce motion estimates for the voxels between consecutive 3D images in a video sequence. Suitable motion estimation approaches that can be used with embodiments of the disclosed technology include, for example, those described in Y. Wang, J. Zhang, Z. Liu, Q. Wu, P. A. Chou, Z. Zhang, and Y. Jia, "Handling occlusion and large

displacement through improved RGB-D scene flow estimation," IEEE Trans. Circuits Syst. Video Techn. (2015); S. Hadfield and R. Bowden, "Scene particles: Unregularized particle based scene flow estimation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 36, no. 3, pp. 564-576 (2014); J.-M. Gottfried, J. Fehr, and C. S. Garbe, "Computing range flow from multi -modal Kinect data," in Advances in Visual Computing, pages 758-767 (Springer, 2011); E. Herbst, X. Ren, and D. Fox, "RGB-D flow: Dense 3- D motion estimation using color and depth," in IEEEInt'l Conf. on Robotics and

Automation (ICRA) (2013); J. Quiroga, F. Devernay, and J. L. Crowley, "Local/global scene flow estimation," in IEEEInt'l Conf. on Image Processing (ICIP) (2013); X.

Zhang, D. Chen, Z. Yuan, and N. Zheng, "Dense scene flow based on depth and multi - channel bilateral filter," in Springer Computer Vision (ACCV), pp. 140-151 (2012); M. Hornacek, A. Fitzgibbon, and R. Carsten, "Sphereflow: 6 DoF scene flow from RGB-D pairs," in IEEE Int 'l Conf. on Computer Vision and Pattern Recognition (CVPR) (2014); J. Quiroga, T. Brox, F. Devernay, and J. Crowley, "Dense semi-rigid scene flow estimation from RGBD images," in Springer Computer Vision (ECCV), pp. 567-582 (2014); Y. Niu, A. Dick, and M. Brooks, "Compass rose: A rotational robust signature for optical flow computation," IEEE Trans. Circuits and Systems for Video Technology, vol. 24, no. 1, pp. 63-73 (Jan 2014); and/or M. Dou, J. Taylor, H. Fuchs, A. W. Fitzgibbon, and S. Izadi, "3D Scanning Deformable Objects with a Single RGBD Sensor," in IEEE Int 'l Conf. on Computer Vision and Pattern Recognition (CVPR) (2015).

[0111] Other motion estimation approaches can, of course, also applied in connection with the disclosed technology. Further, the particular embodiments disclosed below at times assume that the approach of M. Dou, J. Taylor, H. Fuchs, A. W. Fitzgibbon, and S. Izadi, "3D Scanning Deformable Objects with a Single RGBD Sensor," in IEEE Int 'l Conf. on Computer Vision and Pattern Recognition (CVPR) (2015) ("Dou") is applied, though this usage is by way of example only. Specifically, in this disclosure, correspondence fields given by Dou are used as part of the efficient coding techniques described herein.

Moreover, we use the correspondences to measure perceived geometric and color quantization error. C. Distortion Metrics and Residuals

[0112] The focus of certain example embodiments disclosed herein is the encoding and transmitting of the voxelized point clouds of sequences of people and objects (e.g., the encoding of 3D-point-cloud blocks). For the purposes of visual reconstruction, the unoccupied and interior voxels do not need to be encoded, but only the external "shell" of the person or object. The sparsity of these occupied voxels allows efficient still frame or intra-frame compression of the geometry using octtrees. See, e.g., C. Loop, C. Zhang, and Z. Zhang, "Real-time high-resolution sparse voxelization with application to image-based modeling," in High-Performance Graphics Conf. pp. 73-79 (2013); and J. Kammerl, N. Blodow, R. B. Rusu, S. Gedikli, M. Beetz, and E. Steinbach, "Real-time compression of point cloud streams," in IEEE Int. Conf. Robotics and Automation, May 2012. Multiple frame or inter-frame compression of the geometry can also be performed using octtrees. For example, the exclusive-OR (XOR) between sets of occupied voxels in successive frames can be used. See, e.g. D. Thanou, P. A. Chou, and P. Frossard, "Graph-based motion estimation and compensation for dynamic 3D point cloud compression," in IEEE Int. Conf. Image Processing (Sep. 2015); J. Kammerl, N. Blodow, R. B. Rusu, S. Gedikli, M. Beetz, and E. Steinbach, "Real-time compression of point cloud streams," in IEEE Int. Conf. Robotics and Automation (May 2012). However, such methods will increase the data rate when the geometric distance between corresponding voxels are typically more than a unit voxel. Moreover, such methods code the geometry losslessly, and hence are not optimized from a rate-distortion point of view, nor can they achieve low bit rates.

Accordingly, embodiments of the disclosed technology are designed to address these issues by selectively predicting the geometry as well as the color. Further, in some example implementations, the prediction residuals are encoded in a rate-distortion optimized way.

[0113] Specifically, from Expressions (3) and (4), the following can be obtained:

C(i + l) = S( C(0 + E _e , (8) from which one can obtain G(t + \) and C(t + \) by encoding the correspondences S(t) and the residuals Ε _σ and E .

[0114] In order to evaluate the distortion, although objective metrics such as peak signal- to-noise ratio (PSNR) have been very useful in evaluating image coders in most traditional video coding problems, geometry distortion is a complicating factor in the encoding of dynamic point clouds.

[0115] Generally speaking, embodiments of the disclosed technology use one or both of two approaches for computing distortion: an approach based on correspondence or an approach based on projection. Either approach or a combination of both (e.g. , using a weighted sum) can be used.

[0116] In a correspondence-based distortion metric, and in certain example embodiments of the disclosed technology, correspondence is established between the original frame

F(t) and the reconstructed frame F(f) using proximity. For instance, in one example implementation, a voxel in F(t) is associated to its spatially closest voxel in F(t) . Once the association is made, the distortion is computed using a function of E _g or E _c . From these pairing associations {e.g. , all pairing associations for a given voxel), a further value can be computed, such as the mean-squared error (MSE) and, from it, the corresponding peak signal-to-noise ratio (PS R).

[0117] For one particular example of computing distortion using proximity, let there be N _v occupied voxels in the current frame and let E _c compute only the residual of the Y color component. In particular, the MSE of this example implementation is:

½ _+G = ^ (l| E _c || ² +/? || E _g || ² ) (9) where β weights the mixture of geometry and color distortions. From S _Y+G , PS R-Y+G can be computed

[0118] In a projection-based distortion measure, a projection view of the point cloud is rendered. In one particular example implementation, an orthogonal projection of the point cloud is generated over the six sides of a cube at the limits of the voxel space. The observer is assumed far away from the scene so that the rays from it to the voxels are parallel and the background is assumed at a mid-level of gray. An example frontal orthogonal projection within a 9-level test set is a 512x 512 -pixel image, the projections of which are shown in Figure 3. In particular, Figure 3 shows projections from each of the six cube sides (e.g., right, left, front, back, top, bottom) for two 3D images: a 3D image data set (310) labeled "man", and a 3D image data set (312) labeled "Ricardo".

[0119] For the "man" image data set (310), left projection (320), right projection (321), front projection (322), back projection (323), top projection (324), and bottom projection (325) are shown. For the "Ricardo" image data set (312), front projection (330), back projection (331), left projection (332), right projection (333), top projection (334), and bottom projection (335) are shown. Note that for the 3D image data set (3 12) for

"Ricardo", the image data includes (roughly) only the frontal half of the imaged subject in shell form. As a consequence, some of the views do not comprise a volumetric solid shell as with image data set (310), but only a partial shell. For example, the back projection resembles the front projection when depicted in the 2D limitations of a flat page, as it comprises a view through the frontal shell of "Ricardo" from a rear vantage point.

[0120] In one example implementation, the distortion metric in between two point clouds, original and reconstructed, is then the MSE (or PSNR) in between the two corresponding composite images, each with the 6 orthogonal projections of the original or reconstructed Y frames. The corresponding PSNR can then be computed and is referred to herein as the "projection PSNR" or "PSNR-P".

D. The Motion-Compensated Coder

[0121] Embodiments of the disclosed technology comprise a coder for dynamic point clouds. Particular embodiments are specially adapted to perform real-time encoding (e.g. , as may be used in "live" 3D video communication applications, including augmented- reality and virtual-reality implementations). Implementations of the coder are capable of outperforming the use of purely RAHT and octree approaches to compress color and geometry, respectively.

[0122] Embodiments of the disclosed technology use the temporal dimension to remove temporal redundancies. In other words, embodiments of the disclosed technology employ the observation that the geometry and color of a point cloud, in many instances, will not change much from one frame to another. In particular implementations, the coder uses F(t) as a predictor for F(t + 1) . Unlike other approaches, embodiments of the disclosed technology therefore use motion estimation and motion compensation as part of the compression scheme of dynamic point clouds. Embodiments of the disclosed technology have been observed to achieve higher compression ratios (even though, in some cases, lossy coding of the geometry may result).

1. Cube Motion Compensation

[0123] An example coder for 3D-point-cloud blocks is illustrated in schematic block diagram (400) of Figure 4. The coder shown in Figure 4 represents a targeted

simplification of the coder described above with respect to Figures 19a- 19b in order to highlight certain example operations of the disclosed coder. In Figure 4, 3D-point-cloud- blocks of a current frame being encoded (shown as new voxel cubes (410)) are encoded using either intra-frame coding (represented by intra-frame coder (412)) or inter-frame coding using motion compensation as described below (represented by MV coder (414)). The encoding mode selection (shown as being made by mode selector (416)) is based on an evaluation of the rate-distortion performance of each mode. The selected mode can also be encoded as part of the encoded output. In the example shown in Figure 4, the rate- distortion performance data is computed by RD mode decision module (418). To compute the rate-distortion performance of inter-frame encoding, motion compensator (420) provides the inter-frame-related data using motion vectors (422), which are provided by a motion estimator (not shown). If inter-frame compression is selected, the relevant motion vectors (422) can be encoded as part of the output. The coder shown in Figure 4 also includes an in-loop decoding process emulator for reconstructing a frame for use as a reference frame for inter-frame compression of subsequent frames. This process includes a local decoder (430) (which can include an inverse quantization and inverse RAHT operation, as with (1955) and (1945) above) as well as an in-loop post-processor (432) (e.g., an in-loop post processor like processor (1946)) where one or more voxel -distortion- compensation filters as described below can be applied. The reconstructed frame is then stored in frame store (434) (e.g., reference frame buffer (1974)).

[0124] In many 2D video coders, the frame is broken into blocks of NxN pixels. In embodiments of the disclosed 3D video coder, the frame is broken into 3D blocks (cubes) of NxNxN voxels (the voxel space is partitioned into 3D blocks and the list of occupied voxels is likewise partitioned into occupied 3D blocks). Such 3D blocks are also referred to herein as 3D-point-cloud blocks. Further N can be any integer value of 2 or greater. So, the occupied 3D block (cube) at integer position (b _x , b _y , b _z ) is composed of occupied voxels v _u within the block boundaries. Or, more formally, an occupied 3D block (cube) comprises occupied voxels v _u = [x„, y„, z _it , Y _U ,U _U ,V _U ] such that

b _x N≤x _u < b _x N + N,

b _y N≤y _lt < b _y N + N,

b _z N≤z _it < b _z N + N. ₍₁₀₎

Note that each occupied 3D block may have between 1 and N ³ occupied voxels.

[0125] An example of a motion compensation process as can be used in embodiments of the disclosed technology is illustrated by the schematic block diagram (500) of Figure 5. In Figure 5, each occupied 3D block (cube) is associated with a motion vector (MV), whose components (M _x ,M _y ,M _z ) indicate a 3D block (cube) in a reference frame that will be used to predict a current 3D block (cube) being encoded. In Figure 5, an occupied 3D block (520) (e.g., a cube comprising one or more occupied voxels) of a current frame (512) is associated with a motion vector (522) describing motion from an associated occupied 3D block (cube) (524) from the previous frame (510).

[0126] In accordance with one example motion compensation technique as can be used in embodiments of the disclosed technology, let Ω be the set of occupied voxels in a 3D block (block) at position (b _x , b _y , b _z ) in frame F(t) . Then, Ω can be predicted from the set of voxels _t -i, )> _{j t} -i _t -i, Y _j t- U _j ,^ , Υ _{ί t} _i originally in frame F(t - \) such that

b _x N -M _x ≤x _{i t} _ _l < b _x N + N -M _x ,

b _y N -M _y ≤y _iJ _ _l < b _y N + N -M _y ,

b _z N -M _z ≤z _{i t} _ _l < b _z N + N -M _z .

[0127] This set is motion compensated by adding the motion vectors to its coordinates (x _t →x _t +M _X , y _i — > y _i +M _y , and z _t → z _t +M _z ) to obtain the set of voxels

⁺ . Ji,M ^{+ M} y , ^z v-i + ^M ^ ^Y ,, _t - ^U ,, _t - ^V _I , _t - _l · ^{The set} Ω _Ρ ^is used as a predictor of Ω .

[0128] In order to compute a local distortion δ between Ω and Ω^ , and in accordance with example embodiments of the disclosed technology, one or both correspondence- and projection-based metrics can be used.

[0129] For the correspondence-based distortion, as in Expression (5), the correspondences between occupied voxels in Ω and Ω^ can be computed using a process in accordance with the following example pseudocode:

Let Ω have N _a voxels and let Ω have Ν _Ω voxels. If Ν _Ω ≥Ν _Ω , then

^P p p

• Compute all Ν _Ω Ν _Ω Euclidean distances across the sets;

• Set δ = 0

• Find the smallest distance and associate those voxels

• Let their geometric distance be S _g and let their color distance be S _c

• Update δ→ δ + S _g + βδ ₀

• Remove each voxel from its set (from both Ω and Ω^ ) • Repeat the process until all voxels in Ω are gone

Table 1: Pseudocode for Determining Example

Correspondence-Based Distortion Metric

In the example pseudocode, β = oc _c /a _g is a constant used to linearly combine the distortions and maintain their relative importance. If Ν _Ω < Ν _Ω , one may duplicate voxels

P

in before computing δ .

[0130] If, however, the distortion metric is based on projection, the voxels in Ω and Ω^ can be projected onto their six sides and the mean squared error of the Y channel of the individual projections can be computed.

[0131] It should be noted that the sum of the cube-to-cube distortions will not add up to the overall point cloud distortion under either of the two metrics because of the occlusions of the projections and of possible correspondences across cube boundaries. Nevertheless the example local distortion measures serve as strong approximations to the global ones.

[0132] As noted, embodiments of the disclosed technology can be used with a variety of motion estimation schemes. In particular example embodiments, the correspondences that are calculated from any suitable technique are used. For example, for the technique described in M. Dou, J. Taylor, H. Fuchs, A. W. Fitzgibbon, and S. Izadi, "3D Scanning Deformable Objects with a Single RGBD Sensor," m IEEE Int 'l Conf. on Computer Vision and Pattern Recognition (CVPR) (2015), the correspondences that are calculated in the 3D surface reconstruction processes immediately prior to compression are used. In those processes, each voxel may have a correspondence to a voxel in the previous frame, but one MV per occupied block is used. From these correspondences, a voxel-oriented field of MVs can be produced. For instance, in one example embodiment of the disclosed technology, each voxel in Ω is associated with a MV. In order to find one MV for the whole set, and in one example implementation, the existing MV in Ω that is the closest to the average of all MVs in Ω can be used. This "median" MV can then be assigned to the 3D block (cube) containing Ω .

2. Coding mode decision

[0133] Unlike traditional video coding, where the pixel position is known and its color is to be encoded, here, the need to encode the geometry along with the color makes it a distinct problem. In order to increase the compression rate so that the disclosed technology can be used in real-time compression scenarios, certain example embodiments omit one or more encoding steps that might otherwise be used to improve the quality of the predicted 3D image. For example, in certain embodiments, geometry residuals are not encoded. In other examples, however, geometry residuals are encoded and used by the decoder during reconstruction of the 3D image data.

[0134] Example coder embodiments in accordance with the disclosed technology operate in two modes: either (a) a 3D block (cube) comprising multiple voxels is purely motion compensated; or (b) it is entirely encoded in an intra- mode. In such embodiments, and as noted, encoding of geometry residuals is omitted.

[0135] In certain examples, the encoding mode decision is applied on a 3D-block-by-3D- block basis (as referred to as "a cube-by-cube basis" or "3D-point-cloud-block-by-3D- point-cloud-block basis) (e.g., for 3D blocks that include one or occupied voxels), but in other embodiments, the encoding mode decision is applied on a different basis (e.g., a frame-by-frame basis). In certain embodiments, the available encoding modes include an intra-frame encoding mode and an inter-frame encoding mode (e.g., where motion compensation is used). In such examples, frames can be designated as types I (intra-frame coded) or P (predicted), where one or more of the 3D blocks in the frame are inter-frame encoded. For an I-frame, all 3D blocks (cubes) are encoded using an intra-frame coding mode (e.g., using octtree encoding for the geometry and RAHT encoding for the color components). For a P-frame, example embodiments apply an inter-frame coding mode that uses a reference frame stored in the frame store, typically the previous frame but including one or more other previous frames, to predict motion for one or more 3D blocks (cubes) in the P-frame. For a P-frame, and in certain example embodiments, a mode decision for each occupied 3D block (cube) is made: whether it should be inter-frame coded (motion- compensated) or intra-frame coded. In certain embodiments, the decision is based on a test as to whether motion compensation alone produces a good enough approximation of the block. If so, Ω can be replaced by Ω^ ; if not, Ω can be coded independently using octtree and/or RAHT encoding.

[0136] In certain example implementations, the decision can be guided (e.g., optimized) in a rate-distortion (RD) manner. In general, the choice is about representing the 3D block (cube) by Ω (intra) or by Ω^ (inter). Each choice implies rates and distortions for both geometry and color components: (R _g ' ^ntm , R ^a , D _g ' ^ntra , D' ^ra ) and (R _g ' ^nter , R ^er , D _g ' ^nter , and jj ter p _{Qr exam} pi _{e^ m cer} tain embodiments, one or more of the following components can be computed as a guide for determining the intra- vs. inter-coding decision:

r intra . r intra || n rtintra

^K mtra - ^K g + ^K c ~ ^Z - -> 11 ¹ 11 ^+K c Q ₂ )

r) jointer . jointer r>

^inter ^~ g ^~ MV (13)

jointer

^D mter ^{= D} _g +

where is the average rate to encode one MV. In particular embodiments, Lagrangian costs can be computed for each mode, the mode with the smallest cost can be selected. For instance, the intra mode can be selected if and only if:

^ intra ⁺ ^intra ^< ^ inter ⁺ ^inter (1 and, otherwise, on inter mode can be used, for any fixed λ > 0. These example metrics can be applied 3D-block-by-3D-block-basis (cube-by-cube) basis for point cloud data or, more generally, on a frame-by-frame basis (point-cloud-frame-by-point-cloud-frame basis).

[0137] The decision threshold for 3D block (cube) comprising multiple occupied voxels is illustrated in Figure 6. In particular, Figure 6 is a graph (600) showing the rate-distortion performance of different coding modes for a 3D block (cube): (R _mter ,D _mter ) for inter-mode and (R _mtra ,D _mtra ) for intra-mode. Minimizing the Lagrangian cost is equivalent to picking the point supported by the line of slope - λ . Note that a continuum of line slopes may support the same point.

[0138] Graphically, the points (R _mter , D _mter ) and (R _Mer , D _Mer ) are very distinct points in the distortion-rate plane, with (typically) R _Mer < R _mtra and D _mter > D _mtra . Let

— ^ inter ^ intra ^ Q

^R intra ^R inter (17) be the magnitude of the slope of the line connecting the two points. Then, the intra mode criterion (16) reduces to:

λ < Χ. (18)

[0139] That is, a 3D block (cube) of voxels is encoded as intra if and only if its value of X is greater than the globally advertised value of λ , which is fixed across the sequence. One can see that the mode decision for a given block is not excessively sensitive to λ since the choice is between only two RD points and many values of λ may lead to the same mode decision for a given 3D block (cube).

[0140] For a P-frame, there are two extremes: intra-coding the whole frame or motion- compensating the whole frame. By varying 0≤ λ <∞ from one extreme to the other, the frame can be encoded at these extremes or at various points in between. This is illustrated in Figure 7. In particular, Figure 7 is a graph (700) showing the extremes of a P-frame for completely motion-compensating the whole frame with average RD performance

( ter > ^D mter ) ^0Γ encoding it as an I-frame with average RD performance (R _mtra ,D _mtra ). By varying λ , the frame can be encoded at its extremes or at various points in between.

3. Rate or Distortion Control

[0141] For various embodiments disclosed herein, the rates and distortions of the color and motion vectors can be controlled by a quantizer step Q . Like λ , Q is also a means to trade-off rate and distortion. The overall 3D image coder essentially maps Q and λ to an overall rate R and distortion D . In particular embodiments, the 3D image coder desirably operates on the lower convex hull (LCH) of all the RD points produced by spanning all Q and λ combinations. Thus, for certain examples, it is desirable to find the λ and Q points that are mapped into the LCH. In order to speed up the process, it is sometimes useful to derive a relation λ = f _x (Q) that would provide good results across many images. In other words, if the coder is a mapping from (A, Q) to (R,D) , then one can look for the curve defined by f _x in the (A, Q) plane that is to be mapped into the LCH in the RD plane. It is not always feasible to obtain such a function.

[0142] In one example, shown in Figure 8, the 56th frame of the sequence "man" is compressed as a P-frame using the decompressed 55th frame as a reference. The distortion metric is based on correspondence. Both λ and Q are varied. In the figure one can see many RD curves, each for a fixed λ and varying Q . In particular, Figure 8 is a graph (800) showing RD plots for compressing the 56th frame of sequence "man" as a P-frame using the decompressed 55th frame as an I-frame reference. In this example, λ was fixed and Q was varied for various values of λ and Q . The convex hull of all points is also shown, which can model a curve relating λ and Q .

[0143] The LCH of all those curves is also plotted in graph (800) of Figure 8. The loci of all (A, Q) in the LCH curve is empirically approximated by = Λ(β) = β ² /60, (19) which is one relation used in the example coder disclosed herein.

4. Encoded Data

[0144] In example embodiments of the disclosed technology, the compressed frame is locally reconstructed and then post-processed, in a process explained later, before being placed in a frame store where it will be available for motion compensation and prediction of the next frames (see, e.g., the coder diagram of Figure 4).

[0145] The encoded data comprises one or more (e.g., all) of the following:

• Sequence parameters: GOP length, W , N , η , γ (see next subsection);

• Number of occupied 3D blocks (cubes);

• List of occupied 3D blocks (cubes);

• Coding mode per occupied 3D block (cube);

• For intra-frame coded 3D blocks (cubes): occupied voxels encoded using octrees and color data encoded using RAHT and quantizer stepsize Q ; and

• For inter-frame coded 3D blocks (cubes): motion vectors encoded using RAHT and quantizer stepsize Q _mv .

5. In-Loop Processing for Geometry Distortions

[0146] Unlike other coders for dynamic point clouds, certain embodiments of the disclosed technology apply lossy coding of the geometry. Even though a distance metric applied to two sets of point clouds may be useful as an objective measurement of the coding quality, small distortions to the geometry can cause blocking artifacts that are quite annoying.

[0147] In this regard, it should be noted that encoding artifacts (or other image errors) in 3D image data (e.g., point cloud data) are fundamentally different than blocking artifacts in the 2D image context, and thus are more aptly described as voxel-distortion errors. In the 3D image data context, a voxel-distortion error can result in a "gap" or "rip" in the surface of a point cloud representation of a volumetric object. Because point clouds typically represent just the surface, or shell, of such objects, the gap or rip produced by a voxel-motion-compensation error artifact may leave a void in the surface/shell, thus allowing luminance or chrominance values from background objects to penetrate

"through" the point cloud, and thereby degenerating the coherence (and thus the

"realness") of the point cloud representation. By contrast, blocking artifacts in 2D image compression simply result in visually apparent deviations that reveal the "blockiness" of the block-based compression techniques underlying the compression/decompression of an image - not a "gap" or "rip" in the shell of the imaged object itself.

[0148] In some example implementations of the disclosed technology, surfaces of dynamic point clouds are smoothed and gaps (rips) filled using voxel-distortion-correction filters specially adapted for 3D voxels. For instance, an in-loop smoothing filter and/or an in-loop morphological filter specially adapted for 3D voxels can be used.

[0149] In one example technique, the geometry elements are filtered to smooth the surface discontinuities caused by mismatch in the motion compensation process. Without loss of generality, for example, using the first dimension x), the filter is:

where d _y =|| v _j . - v _} \\ is the distance between voxels i and j , and η controls the neighborhood size and the intensity of filtering. Such an operation may cause further holes in the geometry surfaces. Because of that, assuming the discontinuities will be more prominent at the cube boundaries, only voxels that are near the boundaries of a motion- compensated cube are replaced. Furthermore, to avoid creating more holes, we do not allow the voxel position to move away from the border. In effect, if x _t is at the border, x _t is not changed but y _t and z _t are replaced by y _t and z _t , respectively.

[0150] After filtering, and in one example implementation, gaps are closed using morphological operations on the voxel geometry. For instance, in one example process, a dilation process is performed followed by an erosion operation. In particular

implementations, dilation is performed by replicating each existing occupied voxel to its 26 immediate volumetric neighbors (or to n layers of volumetric neighbors, where n is 2 or greater), if such a neighbor is not occupied yet. Further, in this example process, the erosion operation is defined by erasing a given voxel if any of its 26 neighbors in 3D is unoccupied. The dilation can be performed γ times with the same number of erosion operations. The combined process is known as a morphological closing operation. Holes up to 2γ voxels wide may be patched by the process. Other morphological processes are also possible, with greater reach during the dilation and erosion operations {e.g., where the dilation and erosion processes reaches to n layers of volumetric neighbors, where n is 2 or greater). [0151] In particular implementations, the dilution/erosion operations are only applied to inter-frame coded cubes. Processed cubes not only are made available to the decoder and to the display, but can also be placed in the frame store so that the coder can use the frames processed in-loop to perform motion compensation for future frames.

6. Simulation Results

[0152] Simulations were carried out to demonstrate the capabilities of an example embodiment of the disclosed system, referred to in the figures as the motion-compensated intra-frame coder ("MCIC"). Two datasets were used for testing, both with W = 512,200 frames, and captured at a rate of 30 frames per second. One sequence ("man") represents a full body in 3D, while the other sequence ("Ricardo") is intended for video conferencing and thus just a frontal upper body is represented. A GOP length of 8 was used (thus interspersing 7 P-frames between every I-frame). Since P-frames are degraded versions of I-frames (lower rate and higher distortion) and assuming the compression ratio should be similar for every intra-frame coded part in every frame, the rate peaks at every I-frame. Q _mv = 1 was used and Q was varied to obtain the RD curves. Values of Q in the range of

5 through 45 were used for the MCIC, while the purely intra coder used quantizer values ranging from 10 to 50.

[0153] As for the in-loop filtering, after many tests, = 2 and η = 2 were selected.

Nevertheless, this choice of parameters is by way of example only and not limiting, as a variety of other parameter settings and filtering approaches could be used.

[0154] For the correspondence-based distortion metric (PSNR-Y+G), a simple

approximation to f {Q) yields very good results for both sequences tested. The function was derived from one single frame and yet it performs adequately for all other frames under this metric. Using λ = f _A (Q) = Q ² /60 , the RD plots for sequences "man" and "Ricardo" shown in graph 900 in Figure 9 were obtained. In particular, Figure 9 shows RD plots for sequence "man" and "Ricardo" using correspondence-based distortion:

PSNR-Y+G. RD points were obtained by averaging rate or distortion for each frame over the entire sequence. The RD points are averages over all the 200 frames of the sequences. From the figure, one can easily infer the superior performance of the MCIC over purely intra coder under this metric.

[0155] For the projection-based distortion metric (PSNR-P), a curve f _x was found that works well for sequence "man," and the RD curves are presented in graph (1000) of Figure 10. In particular, Figure 10 shows RD plots for sequence "man" and "Ricardo" using a projection-based distortion metric. RD points were averaged for each frame over the entire sequence. The RD points were obtained by averaging the rate or distortion of each frame in the entire sequence. The curve f _x was set from the results of a single frame

3 2

with a simple least-squares fitting in the log domain, f _x {Q) = e" ^{3 +} ° ^{2 +c>1 +a} ° , for a ₀ = -71873 , ¾ = 0.35998 , a ₂ = -7.6525x10 ^"3 , a ₃ = 5.6329x10 ⁵ . Despite the sub - optimality of fitting with least squares instead of a proper RD criterion, the solution yields good results for sequence "man," as depicted in graph 1000 of Figure 10.

[0156] The results are not so simple for sequence "Ricardo" under PS R-P. It is not easy to find a function f _x that works for most frames. Not only it is a rapidly changing sequence, but its noise level and the fact of being front-faced makes the estimation of the global distortion from local cube projections more difficult. The non-stationarity is illustrated in graph 1100 of Figure 11, which shows the RD points and the corresponding LCH for different frames of the sequence. In particular, Figure 11 shows the RD plots for different frames in sequence "Ricardo" indicating their LCH under a projection-based distortion metric. Note how widely the LCH curves vary among frames. It is possible, however, to improve significantly the RD performance of MCIC on this sequence by fixing λ and choosing an optimal value of Q separately for each frame {e.g. , using exhaustive search techniques).

[0157] In general, the choice of distortion metric to use can be a subjective one. As an example, Figure 12 shows a comparison between methods for frame 58 of sequence "man." It shows example zoomed views of the original frame and equivalent views of the frames compressed using MCIC under correspondence- and projection-based metrics, and the intra coder. In particular, the top four images (1210, 1212, 1214, 1216) of Figure 12 show a front projection rendering comparing MCIC against intra-coder (RAHT) for frame 58 in sequence "man". In particular, the top left image (1210) is the original; the top right image (1212) shows MCIC under a correspondence-based distortion metric; the left image (1214) shows MCIC under a projection-based distortion metric; and the right image (1216) shows a result from RAHT. Rates are about 3.7 bpv for all three compression cases. For the bottom images, image (1218) shows a front projection rendering comparing the original frame with its MCIC reconstructed image (1220) after a compression to 4.4 bpv. [0158] The rate is about 3.7 bpv for all cases. The correspondence-based result produces the best color, but with a few speckles of noise caused by geometry shifts. Those artifacts are caused by introducing holes in the object shell, which causes the view to show the background color, which usually contrasts against the foreground shell color. These holes (rips) were not corrected by the two post-processing operators, in this example, indicating that the post-processing steps of the example implementation could be further tuned to mitigate these artifacts.

[0159] Another comparison can be drawn from the bottom of Figure 12, which shows a zoomed view of the original 75th frame of sequence "man" (1218), side-by-side with its decompressed version using MCIC (projection-based distortion for mode selection) (1220) at around 4.4 bpv.

[0160] Figure 13 shows a similar comparison for a frame of sequence "Ricardo," which was compressed using MCIC (correspondence-based distortion for mode selection) (shown in image (1310)) and intra coding (shown in image (1312)), at a rate around 2.6 bpv.

E. General Embodiments

[0161] Disclosed herein are embodiments of a motion-compensation scheme for use with dynamic point clouds. The encoder works on dividing the cloud into 3D blocks of occupied voxels (also referred to as occupied "3D-point-cloud blocks") and deciding for each one if the block should be intra-frame coded or simply motion-compensated from the past frame. The replacement of intra-frame coded data for a slightly distorted (or not) set of voxels saves many bits, but potentially introduces errors not only to the voxel colors, but also to their positions (geometry). In effect, a P-frame may become a degraded I-frame whose extra distortion is found to be "worth it" in an RD sense. With that extra degradation, embodiments of the disclosed technology are able to extend the bit-rate range below where the intra coder can effectively operate and to exceed the performance of the intra coder at any rate under a given objective distortion measure.

[0162] Figure 14 is a flowchart (1400) illustrating an example process for encoding point cloud data for a sequence of frames using aspects of the disclosed technology. In particular, the flowchart (1400) shows a process by which 3D-point-cloud blocks from a current frame being encoded (e.g., a frame comprising voxelized point cloud data) can be encoded according to embodiments of the disclosed technology. The disclosed

embodiment can be performed by a computing device implementing a three-dimensional video encoder, which may be further configured to produce a bitstream. The encoder can be part of an encoder system, which can comprise, for example, a buffer configured to store voxelized point cloud data of a sequence of three-dimensional video frames. The particular embodiment illustrated should not be construed as limiting, as the disclosed method acts can be performed alone, in different orders, or at least partially

simultaneously with one another. Further, any of the disclosed methods or method acts can be performed with any other methods or method acts disclosed herein.

[0163] At (1410), an encoding mode is selected for one or more occupied 3D-point-cloud blocks in a current frame of the sequence. In the illustrated embodiment, the encoding mode is one of a plurality of available encoding modes, the available encoding modes including intra-frame encoding and inter-frame encoding.

[0164] At (1412), the one or more occupied 3D-point-cloud blocks of the current frame of the sequence are encoded according to the selected encoding mode.

[0165] At (1414), a bitstream comprising encoded data for the one or more occupied 3D- point-cloud blocks is output. In accordance with embodiments of the disclosed

technology, the bitstream can include a syntax element or bitstream element signaling the selected encoding mode for the one or more occupied 3D-point-cloud blocks (e.g., on a 3D-point-cloud-block-by-3D-point-cloud-block basis).

[0166] In particular implementations, the inter-frame encoding mode uses motion compensation. In such cases, the motion prediction used for the motion compensation can be block translational, affine, or non-rigid. Further, in some examples, the motion compensation uses block replenishment. For instance, the block replenishment can comprise matching an occupied 3D-point-cloud block from the current frame with a corresponding occupied 3D-point-cloud block from a previous frame using motion vector data; and encoding the motion vector data for the occupied 3D-point-cloud block. In some cases, the block replenishment excludes encoding of geometry residuals (thus increasing the encoding rate, which can be particularly useful in real-time applications such as video conferencing). In other embodiments, however, geometry residuals and/or color residuals are encoded. In embodiments of the disclosed technology, the selecting of the encoding mode is based at least in part on a correspondence-based metric, a projection-based metric, or a combination of both the correspondence-based metric and the projection-based metric. Further, in certain embodiments, the selecting of the encoding mode is based at least in part on a metric that includes both geometry and color components. In some embodiments, the selecting is based on a threshold that relates rate-distortion performance for intra-frame encoding to rate-distortion performance for inter-frame encoding. [0167] Figure 15 is a flowchart (1500) illustrating another example process for encoding point cloud data for a sequence of frames using aspects of the disclosed technology. In particular, the flowchart (1500) shows a process by which 3D-point-cloud blocks from a current frame being encoded (e.g., a frame comprising voxelized point cloud data) can be encoded according to embodiments of the disclosed technology. The disclosed

embodiment can be performed by a computing device implementing a three-dimensional video encoder, which may be further configured to produce a bitstream. The encoder can be part of an encoder system, which can comprise, for example, a buffer configured to store voxelized point cloud data of a sequence of three-dimensional video frames. The particular embodiment illustrated should not be construed as limiting, as the disclosed method acts can be performed alone, in different orders, or at least partially

simultaneously with one another. Further, any of the disclosed methods or method acts can be performed with any other methods or method acts disclosed herein.

[0168] At (1510), three-dimensional image data for a current frame in a sequence of three- dimensional video frames is encoded. In this example, the frame is formed from a plurality of 3D-point-cloud blocks, and the encoding includes encoding occupied ones of the 3D-point-cloud blocks. In some example embodiments, the encoding further comprises applying one or more voxel-distortion-correction filters to the three- dimensional image data for the current frame. In particular implementations, the voxel- distortion-correction filters are applied to one or more 3D-point-cloud blocks that are encoded using an inter-frame encoding technique (e.g., only to inter-frame encoded 3D- point-cloud blocks and not to intra-frame encoded 3D-point-cloud blocks).

[0169] At (1512), a bitstream comprising the encoded three-dimensional image data is output.

[0170] In particular implementations, each 3D-point-cloud block includes a plurality of voxels. Further, in some examples, the voxel-distortion-correction filters are applied in- loop during inter-frame encoding (see, e.g., Figure 4). The voxel-distortion-correction filters applied at (1510) can comprise a morphological process, a smoothing process, or both. For example, a suitable morphological process comprises a dilation phase, and an erosion phase. During the dilation phase, for instance, one or more existing occupied voxels can be replicated volumetrically to volumetric neighbors. Further, the voxel- distortion-correction filter can include an adaptive filtering process (see, e.g., Expression (20)). [0171] During decoding, the reverse operations are performed. For example, during decoding, encoded three-dimensional image data for a current frame in a sequence of three-dimensional video frames is decoded. In this example, the frame is formed from a plurality of 3D-point-cloud blocks, and the decoding includes decoding occupied ones of the 3D-point-cloud blocks. In some example embodiments, the decoding further comprises applying one or more voxel-distortion-correction filters to the three- dimensional image data for the current frame. The filters can be any of the filters disclosed herein. In particular implementations, the voxel-distortion-correction filters are applied to one or more 3D-point-cloud blocks using an inter-frame decoding technique (e.g., the filters are applied only to inter-frame encoded 3D-point-cloud blocks and not to intra-frame encoded 3D-point-cloud blocks). Further, the voxel-distortion-correction filters can be applied in-loop or out-of-loop (e.g., as an out-of-loop post-processing step after reconstruction of the point-cloud frame). Finally, the decoded three-dimensional image data is output (e.g., as voxelized point cloud data that can be rendered on a suitable display device (such as a headset, near-eye display, stereoscopic monitor, flat-screen monitor, or the like).

[0172] Figure 16 is a flowchart (1600) illustrating an example process for decoding point cloud data for a sequence of frames using aspects of the disclosed technology. In particular, the flowchart (1600) shows a process by which 3D-point-cloud blocks for a current frame (e.g., a frame comprising voxelized point cloud data) can be decoded from a bitstream according to embodiments of the disclosed technology. The disclosed embodiment can be performed by a computing device implementing a three-dimensional video decoder, which may be further configured to generate and display a decoded voxelized point cloud (e.g., through use of an augmented-reality or virtual-reality headset, near-eye display, stereoscopic display, flat panel display, or other such display device). The decoder can be part of a decoder system, which can comprise, for example, a buffer configured to receive and temporarily store the bitstream as it is being decoded. The decoder system can also comprise a suitable display device for displaying the reproduced voxelized point cloud data (e.g., via an augmented-reality or virtual-reality headset, flat panel display, near-eye display, stereoscopic display, or other such display device). The particular embodiment illustrated should not be construed as limiting, as the disclosed method acts can be performed alone, in different orders, or at least partially

simultaneously with one another. Further, any of the disclosed methods or method acts can be performed with any other methods or method acts disclosed herein. [0173] At (1610), a bitstream of encoded dynamic point cloud data for a sequence of frames is received. In this example, the bitstream further comprises a syntax value or bitstream element signaling an encoding mode for one or more 3D-point-cloud blocks in a current frame in the sequence (e.g., for each 3D-point-cloud block).

[0174] At (1612), the encoded data for the sequence of frames is decoded. As part of the decoding, the decoding of the one or more 3D-point-cloud blocks of the current frame is performed in accordance with the signaled encoding mode.

[0175] In particular implementations, the signaled encoding mode is one of multiple available encoding modes, which include at least an intra-frame coded mode and an inter- frame coded mode. Further, when the signaled encoding mode indicates inter-frame encoding for the one or more 3D-point-cloud block, the decoding can comprise decoding motion vector data for one or more 3D-point-cloud block of the current frame, the motion vector data indicating three-dimensional translational movement of one or more voxels from a previous frame, and decoding the respective 3D-point-cloud block using the one or more voxels from the previous frame translated according to the motion vector data as predictors of voxels in the one or more 3D-point-cloud block in the current frame being decoded.

[0176] Embodiments of the disclosed techniques have particular application to scenarios in which efficient, fast encoding is desirable, such as real-time encoding situations (e.g., encoding of live events, video conferencing applications, and the like). Thus, the disclosed techniques can be performed when an encoder is operating in a low-latency and/or fast encoding mode (e.g., for real-time (or substantially real-time) encoding, such as during the encoding of live events or video conferencing).

[0177] Further, any of the aspects of the disclosed technology disclosed herein can be used with other embodiments disclosed herein. For instance, any aspect of the embodiments disclosed with respect to Figures 14, 15, and 16 can be used in combination with one another.

VII. Concluding Remarks

[0178] Having described and illustrated the principles of the disclosed technology with reference to the illustrated embodiments, it will be recognized that the illustrated embodiments can be modified in arrangement and detail without departing from such principles.

[0179] For instance, the disclosed technology can be adapted for use with B-frames (bidirectional prediction) as well (e.g., where the GOP is, for example, an IBBPBBP... format). Furthermore, in some embodiments, adaptive 3D block sizes are used rather than a singled-sized 3D block. Further, the adaptive 3D block sizes can be selected using an RD measure. Still further, in some embodiments, both the geometry and the color residues for the predicted (P and B) blocks are encoded. Finally, rather than re-using the correspondences from the surface reconstruction among consecutive frames, other efficient motion estimation methods can be used with the coder.

[0180] Still further, elements of the illustrated embodiments shown in software may be implemented in hardware and vice-versa. Also, the technologies from any example can be combined with the technologies described in any one or more of the other examples. It will be appreciated that procedures and functions such as those described with reference to the illustrated examples can be implemented in a single hardware or software module, or separate modules can be provided. The particular arrangements above are provided for convenient illustration, and other arrangements can be used.

[0181] In view of the many possible embodiments to which the principles of the disclosed invention may be applied, it should be recognized that the illustrated embodiments are only preferred examples of the invention and should not be taken as limiting the scope of the invention. Rather, the scope of the invention is defined by the following claims. We therefore claim as our invention all that comes within the scope and spirit of these claims and their equivalents.