SYSTEMS AND METHODS FOR PROBABILISTIC MESH MOTION ESTIMATION

Disclosed herein are systems, devices and methods for probabilistic mesh motion estimation. The systems, devices and methods can involve an encoder, appliance, or other device for processing the video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model. The encoder can introduce inter-probability in the motion model for appearing areas in the video data in conjunction with using the probabilistic mesh motion estimation. The encoder can introduce a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated. The encoder can use master and slave nodes and over-splitting for mesh continuity preservation. The encoder can use a non fully connected mesh applicable to video coding standards.

CROSS REFERENCE

This application is related, and claims benefit of priority, to European Patent Office Application No. 23305603.5 entitled “Systems and Methods for Probabilistic Mesh Motion Estimation,” filed Apr. 19, 2023, the disclosure of which is incorporated herein by reference in its entirety.

FIELD

This disclosure relates to encoding or processing data, and more particularly relates to encoding or processing live content data or on demand content data.

BACKGROUND

Video coding systems can have encoding or processing devices that use motion estimation and compensation techniques. Motion estimation is the process of determining motion vectors that describe the motion of content data, or the transformation from one image to another image.

For encoding live content data and on-demand content data, several motion estimation operations can be performed by an encoder in the look ahead or in the CODEC itself. For example, a hierarchical block matching process (or variations around it) can be used by the encoder for encoding content data.

Motion vectors can be represented by a translational motion model, for example. Other models can also be used to approximate the motion of content data. For example, more complex motion models (e.g. an affine motion model for VVC) can also be used for motion estimation.

There exists a need for improved processes for motion estimation, or at least alternatives.

SUMMARY

Embodiments described herein relate to systems and methods for mesh motion estimation, and in particular, embodiments described herein relate to systems, methods, and devices for probabilistic mesh motion estimation.

In an aspect, there is provided a computer-implemented system for probabilistic mesh motion estimation. The system has: at least one processor, and memory in communication with the at least one processor. The memory stores software code, which when executed by the at least one processor causes the processor to process video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model. In some embodiments, the system encodes (or compresses) the video data using the estimated motion.

In some embodiments, the system has a transceiver for receiving and transmitting the video data.

In some embodiments, the memory stores the video data.

In some embodiments, the processor is an encoder, the encoder comprising a preprocessor, a look-ahead, and a codec.

In some embodiments, the processor introduces inter-probability in the motion model for appearing areas in the video data in conjunction with using the probabilistic mesh motion estimation.

In some embodiments, the processor introduces a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated.

In some embodiments, the processor uses master and slave nodes and over-splitting for mesh continuity preservation.

In some embodiments, the encoder uses a non fully connected mesh applicable to video coding standards for compression and preprocessing.

In some embodiments, the processor implements dedicated splitting for motion continuity preservation.

In some embodiments, the encoder uses probabilistic mesh motion estimation for compression of the video data.

In some embodiments, the look-ahead implements probabilistic mesh motion estimation.

In some embodiments, the codec implements probabilistic mesh motion estimation.

In some embodiments, the preprocessor implements probabilistic mesh motion estimation.

In another aspect, there is provided a computer-implemented method for probabilistic mesh motion estimation. The method involves: processing the video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model; and transmitting or storing the video data.

In some embodiments, the method involves introducing a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated.

In another aspect, there is provided an appliance device for probabilistic mesh for motion estimation. The device has: at least one processor; memory in communication with the at least one processor; software code stored in the memory, which when executed at the at least one processor causes the device to process the video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model.

In some embodiments, the at least one processor uses master and slave nodes and over-splitting for mesh continuity preservation.

In some embodiments, the at least one processor uses a non fully connected mesh applicable to video coding standards.

In some embodiments, the at least one processor implements dedicated splitting for motion continuity preservation.

These drawings depict exemplary embodiments for illustrative purposes, and variations, alternative configurations, alternative components and modifications may be made to these exemplary embodiments.

DETAILED DESCRIPTION

Embodiments described herein provide computer-implemented systems and methods for probabilistic mesh motion estimation. The systems and methods can involve processing video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model. The systems and methods can involve using the estimated motion in the one or more locations of the video data, such as by encoding (or compressing) the video data using the estimated motion. Encoders or processing devices use motion estimation. For encoding live content data and on-demand content data, several motion estimation operations can be performed by an encoder or processing device in the look ahead (as an example, the preprocessing embeds spatiotemporal filter where the pixels involved in the filtration are obtained by motion estimation) or in the codec itself (in encoders, the estimated motion information is extracted from the sequence and sent to the decoder in such a way the decoder can predict the current image by applying the motion from the previous decoded ones). Standard hierarchical block matching (or variations thereof) may be used by encoder or processing device, for example. The term encoder as used herein can refer to a hardware device that implements motion estimation. Motion estimation is utilized for many purposes as a processing technique for images and video. Examples uses for hardware devices or appliances that implement motion estimation include (but are not limited to): super-resolution (e.g. in television or video display device wherein estimated motion is used to select pixels in previous images in addition to the pixels of the current image to recreate inter-pixel information by interpolation); object tracking (e.g. in simulators such as golf simulators); video shaking removal (e.g. in cameras wherein global motion is estimated and compensated to realign the content image per image); frame rate conversions (e.g. in video system diffusion such as conversion from 25 Hz Phase Alternating Line encoding system to to 29.97 Hz National Television System Committee); human computer interactions, such as hand posture analysis, human posture analysis, gesture controlled gaming, lip movement for user authentication; compression; spatio-temporal filtering (e.g. in pre-processing of encoders); robotics (e.g. robotic heart surgery). Devices that utilize motion estimation can utilize probabilistic mesh motion estimation according to embodiments described herein.

Motion estimation can involve motion vectors that may be represented by a motion model to approximate the motion of content data. For example, a translation motion model may be used for motion estimation. However, compression efficiency may not evolve according to future standards. Motion estimation may involve complex motion models (e.g. affine motion model for VVC). If more complex motion models are not used, then video quality for both special applications and video compression may be blocked at a certain level.

Embodiments described herein relate to systems and methods for probabilistic mesh motion estimation (MME). Embodiments described herein relate to systems and methods for MME implemented in real-time. Embodiments described herein relate to systems and methods that adapt MME to the compression.

Embodiments described herein relate to probabilistic MME that can introduce inter-probability in the motion model (e.g. for appearing areas in the video). Embodiments described herein relate to probabilistic MME that can use a master and slave node concept, and over splitting for mesh continuity preservation. Embodiments described herein relate to probabilistic MME that can use a non-fully connected mesh applicable to versatile video coding (VVC).

Embodiments described herein aim to solve the aperture problem in motion estimation techniques. The aperture problem arises because, given the observed data, only motion along the direction perpendicular to the edge or element can be observed, rather than in the direction of motion itself. The aperture problem may be solved by propagating the motion already known. However, this propagation may generate a lexicographic casual dependency that is not present in MME. Accordingly, embodiments described herein provide an improved solution for the aperture problem.

Known motion estimation technique can block on evolutions. Without mesh motion estimation, motion projection (e.g. deduce future motion from current motion) can be difficult. Super resolution that requires a good motion estimation may be improved according to embodiments described herein. Frame rate change that requires the introduction of a good motion estimation may be improved according to embodiments described herein.

With mesh motion estimation, the compression efficiency can be improved. With mesh motion estimation, the motion field can be smooth and predictable, and motion projection is possible (e.g. tracking, shaking removal). The computational cost should be close to other motion estimation processes, such as a block matching.

There may be a drawback with MME when regions appear in the video. The mesh stretches on these regions and impacts the accuracy of surrounding motion areas. It may be suitable to tear the mesh at some locations. Instead, embodiments described herein propose to identify these regions as “INTRA” according to the compression paradigm. Normally, these regions are identified with a failure in the motion estimation. Instead, embodiments described herein propose to address this dilemma by the introducing the probability of being an INTRA region in the model of the MME which results in probabilistic mesh motion estimation. Accordingly, embodiments described herein relate to systems and methods for probabilistic mesh motion estimation. At the limit, this probability can be replaced by 0 or 1, fixing which area is an INTRA region and which is INTER region.

In another aspect, embodiments described herein relate to systems and methods for probabilistic MME for dedicated splitting for motion continuity preservation.

In a further aspect, embodiments described herein relate to systems and methods for probabilistic MME that can use the non-fully connected mesh for VVC.

Currently MME is not used for video compression. Use of MME for video compression can potentially result in multiple embodiments. In accordance with embodiments described herein, MME can be used for video compression and applied in the look ahead of encoders.

Motion estimation or optical flow is a method of calculating the motion of image intensities. In case of pure optical flow estimation, a motion vector must be computed for each pixel, which is computationally expensive. MME consists of estimating the motion only on some locations, e.g., the motion for pixels surrounded by pixels where the motion is known by being deduced by interpolation. Accordingly, the number of motion vectors to be estimated is lower, making a real time computation possible.

With VVC, the notion of interpolated motion appears with the affine motion compensation where the motion is interpolated from motion vector control points.FIG.1is a diagram of affine motion compensation defined by three control points as an illustrative example. Motion vector mv(x,y) can be obtained from control points M0, M1and M2.

The introduction of the mesh in combination with the optical flow technique can reduce the entropy of the motion vector control points. This can improve the motion vectors compression efficiency. The mesh structure is generally based on a similar concept as partitioning that is used in codecs, e.g., rectangles with various sizes and various connectivity since High Efficiency Video Coding (HEVC).

FIG.2is a diagram of an example of per block motion estimation, or block matching. A motion vector per block (as shown inFIG.2) produces a discontinuous motion vector field. In contrast, a motion mesh produces a smooth motion vector field.

FIG.3is a diagram of an example of mesh-based motion estimation, or MME. Reference areas land into a defined shape (rectangles in this example) by motion compensation. The defined shapes can be referred to finite elements (FEs). The model for the displacement is linked to the landing shape, such as affine for triangles, bilinear for rectangles, and so on.

Historically, MME was done on triangles because most of software libraries for simulations were available with triangles. However, MME can be implemented on various shapes. Rectangles can provide advantages. For example, rectangles are well adapted to video compression block-based standards. Further, the hierarchical approach (to catch big motions) is as simple with rectangles as with triangles. In case of splitting, compared to a triangular partitioning, the number of neighbors is fixed for a regular mesh: one corner (i.e., node) is the connection of four rectangles (i.e., FEs) and bounded to four for non-regular rectangular meshes.

FIG.4is a diagram of an example of triangular variable number neighboring FEs as compared to rectangular maximum of four FEs.

Furthermore, the continuity preservation of the motion field can be addressed mixing rectangles and triangles. In this description, FE can have standing for various shapes, such as rectangles, triangles or other shapes. The case of the “triangles-rectangles” mix is not described in detail for simplicity, and instead the illustrative examples focus only on rectangles. However, there can be a mix of shapes for various embodiments.

The technique for MME mixes FE theory and optical flow equations. The equations suitable for triangles can be extended to rectangles.

FIG.5shows an example diagram and equations for block based optical flow on images. The standard MME process minimizes the mean square error between the original image and the motion compensated image. This leads to equations per node numbered “n” shown inFIG.5. The equations are gathered in a huge sparse matrix which is to be solved.

FIG.6shows a further example diagram and equations for block based optical flow on images. The X vector containing the motion vectors are obtained solving A X=B.

Embodiments described herein relate to systems and methods that (i) introduce inter-probability in the motion model (for appearing areas in the video); (ii) involve master and slave nodes and over splitting for mesh continuity preservation; and/or (iii) apply the non fully connected mesh to video coding standards such as Versatile Video Coding (VVC).

Introduction of INTER Probability

For compression of content data, there is INTRA prediction and INTER prediction. INTER means the rectangle (FE) is predicted via motion, and INTRA means that the rectangle is predicted from surrounding areas. Typically, appearing areas would require to be INTRA-coded. Occlusions would require a non-manifold mesh or at least a discontinuity in the mesh, as connected regions in the image to be predicted are disconnected in the reference image.

Compression algorithms deal with INTRA or INTER concepts, and sometimes a combination of both.

The motion estimation aims to compute the displacement. The INTER vs. INTRA probability can be introduced in the mesh model as a weight to indicate the confidence of being INTER associated to each FE. This concept can be introduced in the model, providing a good estimation for probably-INTER FE and a not-of-interest value for motion of FE with a high INTRA probability. These FE can be further encoded as INTRA. As their weight is low, they have less negative impact on the estimation of INTER FEs. This can globally improve the mesh motion estimation accuracy.

FIG.7is a diagram of example modified equations for optical flow. In the same manner, all the equations are gathered in the huge matrix form and solved to extract the motion vectors.

Mesh Splitting

Embodiments described herein relate to mesh splitting, or over-splitting for motion continuity preservation.

To refine the motion at some location, the mesh can be partitioned. This partitioning generates FEs with different sizes around a node. At the same time, the partitioning of the mesh should be adapted or mapped to the compression technique (depending on the standard, allowed partitions vary).

In this context, the problem to solve is the motion continuity problem. Given a splitting algorithm, the mesh, even if rectangular becomes non-regular, i.e. the number of connected FE to a node can be less than four.

Embodiments described herein can involve slave and master nodes. The following definitions can apply: The master node can be defined as “free to move”. The master nodes have four connected nodes or belongs to the border of the mesh. The slave node can be a constrained node, not to be estimated, but with a motion that can be computed from its two connected master nodes.

Embodiments described herein can involve continuous mesh splitting (e.g. splitting without introducing any discontinuity). Embodiments described herein can involve introducing INTER/INTRA probability in the mesh. Embodiments described herein can involve introducing discontinuities. Setting an INTER probability to zero for a finite element can directly introduce a discontinuity all around the considered finite element.

As an illustrative example, consider the case of a fully-connected mesh, such as a mesh composed of rectangular FEs with four motion vector control points per FE and a bilinear model displacement model.

FIG.8shows an example that can exhibit how discontinuity in the motion field does not match with the rectangle shapes. From three consecutive blocks, the central block can be split horizontally, because the top part of the error at the top of central block is considered as excessive, and we want to refine the motion in this central block. In this example ofFIG.8the level of reconstruction error can decide the splitting.

FIG.9shows the example with vertical discontinuities generated by a horizontal split. To split the central block, at least 2 nodes are introduced. Now, considering the reference picture, blocks where pixels come from, the introduction of two nodes to split horizontally the central block can make the origin of the pixels different on the two sides of the vertical junctions (in dashed lines). Consequently, this produces a vertical motion discontinuity. Indeed, some parts in the original image (e.g. the two triangles ofFIG.9) are unused. This introduces a discontinuity at the reconstruction side due to pixels coming from different locations (disconnected pixels).

To keep motion continuity, a “two-types” of nodes concept can be introduced. This technique can be referred to as “continuous mesh splitting”.FIG.10shows the example with continuous mesh splitting with horizontal splitting without discontinuities. In this example, there are nodes belonging to the optimization problem (in white, where to estimate the motion), and nodes that are slaves (in black). The motion is deduced from connected node motion values.

Forcing motion vectors to the mean of (in this example) the top and the bottom node motion values, motion continuity is conserved. And furthermore, the two new (now) white nodes are free to move.

Continuous quad splitting is implemented with a “two-types node technique”.FIG.11shows an example of the first pass for splitting using the two-types node technique. In this example, for the first pass, black nodes are motion constrained, and white point and border points are free to move.

Different types of splitting horizontal, vertical, quad, ternary trees, have to be over split to keep the continuity of the motion field. Once new (master and slaves) nodes are positioned, a second pass is required on the field to modify the nature of some slave nodes to master nodes. A slave node becomes a master in two cases: (i) the slave node belongs to the border, and (ii) the slave node is connected to four nodes.

FIG.12shows an example of the second pass for splitting using the two-types node technique. In this example, for the second pass, some black nodes (slave nodes) become white (master nodes) and free to move.

The following provides another example splitting rule: if the split generates a connection with a node that already exists, it becomes a master node whatever its initial nature (master or slave). The splitting may be done by discontinuity introduction. To introduce a discontinuity at specific location, the splitting must occur in a more sophisticated manner. Referring back onFIG.8, to introduce the horizontal discontinuity, splitting may be as shown inFIG.12A. Ad hoc splitting can result in the introduction of horizontal discontinuity (shown in dashed lines).

There can be an alternative to discontinuous splitting. For example, the splitting can be in a continuous way and introduce the probability of being INTRA. There is the possibility of not finding a corresponding area in the reference image.

FIG.12Bshows an example diagram of the introduction of INTER probability with the continuous splitting.

The remaining difficulties are the estimation of pethe intra probability, and the objective function to minimize that should not degenerate with manipulations done by pe. A first estimate of pecould be:

Where εINTRAeand εINTEReare reconstruction errors (respectively from some INTRA prediction and INTER prediction).

As noted, there can be INTER probability and INTRA probability introduced in the motion model. It can be shown (see Annex 1) that an additional variable attached to the finite element (FE) is enough to define pethe probability of one element e to be INTER. In that case, the matrixial equation attached to the node n is given by:

It can be rewritten for a better readability as:

The previous equations describe two rows of a wide matrixial system=, where the sub-bloc 2×2

and the sub vector 2×1

Despite the introduction of pevalues,remains symmetric and sparse.

The matrixial system is shown inFIG.24.

Embodiments described herein can handle continuities and discontinuities.

Continuity constraints can be introduced at specific locations to keep the mesh connected. It can be shown that the set of additional continuity constraints can be injected directly in the equation system. This can lead to a complex solution that can be difficult to implement due to enlargement of the dependencies between nodes (see Annex 2).

A simpler solution (see Annex 3) can lead to a simpler implementation. This can result in solving an extended system′′=′:

The set of continuity constraints can be gathered into a Matrix “C” as shown inFIG.13where C describes the set of continuity constraints to apply on slave nodes.

Embodiments described herein can involve constraining deformation to be small.

Introducing, a constraint on motion of the control points to be close to the mean of the control points for all finite elements provides a new shape for the matrix (see Annex 4 for details).

and c is the number of nodes per finite elements. Here it is C=4 control points for the bilinear model. The λ parameter controls the strength of the constraint.

To avoid instabilities in the resolution, constraints can force

TheMatrix remains symmetric and sparse. This deformation constraint can be applied only if of interest.

When using three control points, the previous formulas remain valid. Of course, φ functions must be defined accordingly (e.g. affine instead of bilinear).

If we want to introduce an additional continuity constraint on the free (down right) corner of each finite element (see Annex 5). The constraint to apply per element e is:

Then the system′′=′ can be solve, as described in Annex 3, withdescribing the aforementioned set of constraints.

FIG.13shows an example diagram of the extended system′′=′. In this example,describes the set of continuity constraints to apply on slave nodes. The intermediate λ values can be ignored when extracting thepart of the solution. In the same manner, according to some embodiments, constrained motion vectors (slave nodes) can be readjusted from unconstrained motion vectors (master nodes) for accuracy reasons. It is not mandatory for all embodiments, but can be done for accuracy reasons.

Not-Fully Connected Mesh

Embodiments described herein can relate to non-fully connected mesh. Even if the not-fully connected mesh does not produce a pure smooth motion, it introduces a suitable level of continuity in the motion field. It is applicable if the degree of freedom of the motion model for the elements is lower than the number of nodes. As a first example, a bilinear motion model (4 parameters) with rectangles (4 nodes) can provide a fully connected mesh. As another example, an Affine model (2 or 3 parameters) with rectangles (4 nodes) can provide a non-fully connected mesh. This can be applicable to VVC.

FIG.14is an example diagram of non-fully connected mesh.

In this example, interpolation φ functions are affine (previously bilinear). Compared to the bilinear case, the support S(n) is reduced and the considered vertices k also.

FIG.15is a diagram of example equations for optical flow that are modified to be applicable to versatile video coding (VVC).

Embodiments described herein relate to memory storing machine executable instructions that when executed by a hardware processor implement two parts for probabilistic mesh motion estimation. The first part fills the matrix A. The second part is the resolution of AX=B (whether A is constrained or not).

Embodiments described herein relate to the introduction of the INTER probability in the model (for appearing areas in the video).

Embodiments described herein relate to the use of master and slave nodes and over splitting for mesh continuity preservation.

Embodiments described herein relate to non fully connected mesh: applicable to VVC and other video coding standards. The trend of motion estimation is moving toward more and more complex models, so this may be followed for VVC (the new codec from MPEG). Embodiments described herein provide mesh motion estimation using one or more implementations to solve the problem known as the aperture problem.

Embodiments described herein apply to different use cases of encoder (or transcoder) utilization.

Embodiments described herein relate to encoding live media content.FIG.16is a diagram of an example end to end media system. The media pipe involves content creation and production. A content distributor provides the content to a content aggregator, which in turn provides aggregated content to a broadcaster or network operator. The content is delivered to end devices by broadcast equipment, the Internet, or a managed network.

The media or video content can be delivered using appliances (e.g. software and hardware bundled), cloud native applications (e.g. software for on-premises or public cloud infrastructure), as a service (e.g. cloud native application and public cloud infrastructure and services).

FIG.17is a diagram of an example system100for video distribution over internet mobile and satellite. Components of the system100can utilize probabilistic MME. For example, encoders can implemented motion estimations (including MME). Video distribution systems, such as system100, can include encoders. The system100can involve streaming live media content, or an appliance device for video-on-demand (VOD) media content. An encoder102can encode the live media content. A decoder104can decode the (encoded) media content. In some embodiments, the encoded (live) media content can be integrated or aggregated with VOD content by integrated playout108. An encoder106can encode the integrated content for provision to a multiplexer110and splicer112. There can be a record and package116of the content, and devices to manipulate118the content. In some embodiments, an encode file device122can transform the VOD content into an encoded file and which is then stored in a data store124. The system100can involve different devices for content delivery120such as a content delivery network or broadcasting equipment. There can be different types of end devices for playback of the media content. The system100can deliver content by appliances, cloud applications and/or software as a service infrastructure.

FIG.18is a diagram of an example appliance200where probabilistic mesh motion estimation can be utilized. The appliance200has an SDI router, IP input/output, one or more encoders, and one or more statistical multiplexers that generate single program transport streams (SPTS). The appliance200has a stream processing device to generate a multiple program transport stream from the SPTS. The appliance200has a control system, such as a proportional-integral-derivative (PID) controller to manage content processing by the appliance200.

FIG.19is another diagram of an example appliance200where probabilistic mesh motion estimation can be utilized. The appliance200has one or more encoders for encoding live, and one or more packagers for packaging live. There can backup encoders. The one or more packagers can sync content. The appliance200can have one or more load balancers for output. The appliance200can have a management and control system. This example diagram shows the management flow and data flow for the appliance200.

FIG.20is a diagram of example hardware components for an example appliance200. As shown, Peripheral Component Interconnect (PCI) slots can connect various hardware to the appliance200.

FIG.21is a diagram of a high level ecosystem chain presentation. The diagram shows different encoders or encoding live (EL) components. The diagram shows the “contribution part” of the chain, and what is the “distribution part” of the delivery chain. The encoders can implement probabilistic mesh motion estimation according to embodiments described herein.

Accordingly, embodiments described herein can be implemented as part of one or more encoders or one or more transcoders.

FIG.22is a diagram of an example encoder300that can implement probabilistic mesh motion estimation according to embodiments described herein. The look-ahead is a component in the architecture of an encoder300. For encoding live content data and encoding on-demand content data, several motion estimation operations can be performed in the look-ahead or in the codec of the encoder300. In accordance with embodiments described herein, MME can be used for video compression and applied in the look-ahead of the encoder300. In an encoder300, the look-ahead (also be referred to as video analysis block) stores several frames of video. The look-ahead of the encoder300computes video complexity of images, detects sequence transitions (cuts, fade, dissolves, etc.), and can perform motion estimation to provide vector fields that will be beneficial for various encoding formats including MPEG-2, H.264/MPEG-4 AVC and High Efficiency Video Coding (HEVC). Codecs are compression cores scalable to the number of profiles, resolutions and encoding formats. Further details are provided in “High Efficiency Video Coding (HEVC): replacing or complementing existing compression standards?” by Michael Ropert, et al. 2013 https://www.researchgate.net/publication/261449157_High_efficiency_video_coding_HEVC_Replacing_or_complementing_existing_compression_standards, the entire contents of which is hereby incorporated by reference. The mesh structure for motion estimation is generally based on the same concept as the partitioning that is used in codecs, e.g., rectangles with various sizes and various connectivity since HEVC.

FIG.23shows different example applications for encoding or processing where probabilistic mesh motion estimation can be utilized according to embodiments described herein. Motion is what makes a different between image coding and video coding.

For example, an encoder402can use probabilistic mesh motion estimation in the look-ahead or pre-processing module. As another example, an encoder404can use probabilistic mesh motion estimation in two locations: in the look-ahead and the core codec. As a further example, an encoder406can use probabilistic mesh motion estimation for pre-processing techniques for catching true motion, such as before super resolution operations or spatial-temporal filtering operations. As an additional example, an encoder can use probabilistic mesh motion estimation for temporal interpolation (e.g. 25 hz to 40 Hz, slow motion video creation). As another example, an encoder can use probabilistic mesh motion estimation for object tracking. These are illustrative examples and there are other applications for probabilistic mesh motion estimation according to embodiments described herein.

FIG.25is a high-level schematic diagram of a content system1000with components that can use probabilistic mesh motion estimation. For example, encoder1080can implement probabilistic mesh motion estimation. Content system1000may operate as part of an over-the-top (OTT) media service that delivers content to end users at media playback device1095. The content may include, for example, audio and/or video content.

Content system1000uses encoder1080or appliance1002for processing content using PMME. For example, encoder1080can have a preprocessor1082, a look-ahead1084, and a codec1086. For simplicity only, one encoder1080is shown but system1000may include multiple encoders1080. The encoders1080may be the same or different types of devices. The encoder1080may be connected in various ways including directly coupled, indirectly coupled via a network, and distributed over a wide geographic area and connected via a network.

As shown, content system1000has at least one processor1010and memory1020in communication with the at least one processor1010. For example, the content system100can have an appliance device1002that utilizes PMME. The applicant device1002can have at least one processor1010and memory1020. The memory1020stores software code, which when executed by the at least one processor1010causes the processor1010to process video data to estimate motion in one or more locations of the video data using PMME based on a motion model. In some embodiments, the memory1010stores the video data.

In some embodiments, the processor1010introduces inter-probability in the motion model for appearing areas in the video data in conjunction with using the probabilistic mesh motion estimation. In some embodiments, the processor1010introduces a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated. In some embodiments, the processor1010uses master and slave nodes and over-splitting for mesh continuity preservation. In some embodiments, the processor1010implements dedicated splitting for motion continuity preservation.

As another example, content system1000can have another hardware device that utilizes PMME for different use cases, and that device can have at least one processor and memory. In some embodiments, the content system1000has a transceiver for receiving and transmitting the video data.

As a further example, the content system1000can have an encoder1080that utilizes PMME. The encoder1080can have a preprocessor1082, a look-ahead1084, and a codec1086. In some embodiments, the encoder1080uses probabilistic mesh motion estimation for compression of the video data. In some embodiments, the look-ahead1084implements PMME. In some embodiments, the codec1086implements PMME. In some embodiments, the preprocessor1082implements PMME.

In some embodiments, the encoder1080introduces inter-probability in the motion model for appearing areas in the video data in conjunction with using the PMME. In some embodiments, the encoder1080introduces a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated. In some embodiments, the encoder1080uses master and slave nodes and over-splitting for mesh continuity preservation. In some embodiments, the encoder1080uses a non fully connected mesh applicable to video coding standards for compression and preprocessing. In some embodiments, the encoder1080implements dedicated splitting for motion continuity preservation.

Content system1000provides certain technical advantages using PMME. Content system1000includes a broadcast/distribution system1090for live content and/or on-demand content, content delivery network1070, and a plurality of media playback devices1095. Each media playback device1095is a device operable by an end user to play video content.

Broadcast/distribution system1090may serve as a content origin server for an OTT media service. Content system1000delivers live content and/or on-demand content to media playback devices1095by way of content delivery network1070. Content delivery network1070includes a distributed network of proxy servers and data caches interconnected by way of a communication network.

Content delivery network1070includes a communication network and a distributed plurality of proxy servers and data caches. Communication network may include a packet-switched network portion, a circuit-switched network portion, or a combination thereof. Communication network may include wired links, wireless links such as radio-frequency links or satellite links, or a combination thereof. Communication network may include wired access points and wireless access points. Portions of communication network135could be, for example, an IPv4, IPv6, X.25, IPX or similar network. Portions of communication network could be, for example, a GSM, GPRS, 3G, LTE or similar wireless networks. communication network135may include or be connected to the Internet. When communication network135is a public network such as the public Internet, it may be secured as a virtual private network. Communication network can be adapted for transmission of ABR streams over HTTP.

Broadcast/distribution system1090receives primary content from one or more content sources. Broadcast/distribution system1090receives content segments and transmits content via content delivery network1070. Broadcast/distribution system1090can serve as a multicast server and can include one or more gateways. Broadcast/distribution system1090can broadcast content to gateways that have joined its multicast stream. The multicasting may be by way of a communication network. Although one broadcast/distribution system1090is depicted, in some embodiments, content system1000may include a plurality of broadcast/distribution systems1090. Each broadcast/distribution system1090may be dedicated to particular content, e.g., live content, on demand content, a particular broadcast, channel, or program, or portions of the foregoing.

Broadcast/distribution system1090can have one or more gateways, such as a residential gateway that connects a local area network (LAN) to a wide area network (WAN). In some embodiments, gateway is a residential gateway adapted with custom software code to perform the functions disclosed herein. The custom software may be provided to existing device in the home, e.g., by way of a software update, to perform the functions disclosed herein. In some embodiments, gateway may, for example, be a router, switch, hub, set-top box or other device that provides connection between a LAN and a WAN.

Each media playback devices1095is a device operable by an end user to play streamed content. For example, a media playback device1095may be a digital media player, a set-top box, a video game console, each connected to a display device for playing streamed content. A media playback device1095may also be smart television device or a personal computing device such as a laptop computer, a tablet computer or a smartphone, each having an integrated display screen for playing streamed content. A media playback device1095may be also referred to as a player device herein.

Media playback device1095can begin preparing for playout, e.g., by requesting content. A playout request may be responsive to user control of media playback device1095. The playout request is received at content delivery network1070, which then requests content from the broadcast/distribution system1090.

Broadcast/distribution system1090transmits content data to content delivery network1070, e.g. by way of multicast transmission or unicast transmission. The content delivery network1070transmit the content data to encoder1080or appliance1002for processing. Embodiments have been described herein can use different protocols for communication between a broadcast/distribution system1090and media device1095.

Different example hardware components can be used to implement encoder1080or appliance1002. The hardware components may be used to implement various elements of PMME, in accordance with an embodiment.

In one example, a computing device may be used to implement an encoder1080. In another example, computing device may be used to implement an appliance1002.

As depicted, appliance1002includes at least one processor1010, memory1020, at least one I/O interface1030, and at least one network interface1040.

Each processor1010may be, for example, any type of general-purpose microprocessor or microcontroller, a digital signal processing (DSP) processor, an integrated circuit, a field programmable gate array (FPGA), a reconfigurable processor, a programmable read-only memory (PROM), or any combination thereof.

Each I/O interface1030enables appliance1002to interconnect with one or more input devices, such as a keyboard, mouse, camera, touch screen and a microphone, or with one or more output devices such as a display screen and a speaker.

For simplicity only, one appliance1002is shown but system1000may include multiple appliances1002. The appliance1002may be the same or different types of devices. The appliance1002may be connected in various ways including directly coupled, indirectly coupled via a network, and distributed over a wide geographic area and connected via a network.

FIG.26is a diagram of an example method2000for probabilistic mesh motion estimation.

At2002, an encoder (e.g. encoder1080) or other processing device (e.g. appliance1002) receives video data. For example, the video data can be live content or on-demand content.

At2004, the encoder or other processing device processes the video data to estimate motion in one or more locations of the video data using probabilistic mesh motion estimation based on a motion model. The encoder can have a preprocessor, a look-ahead, and a codec. The encoder can use probabilistic mesh motion estimation for compression of the video data, for example. In some embodiments, the look-ahead implements the probabilistic mesh motion estimation. In some embodiments, the codec implements the probabilistic mesh motion estimation. In some embodiments, the preprocessor implements the probabilistic mesh motion estimation. The encoder can introduce inter-probability in the motion model for appearing areas in the video data. The encoder can introduce a probability that regions in the video data are intra-regions or inter-regions in the motion model as weights to indicate a confidence of finite elements being inter-associated. The encoder can use master and slave nodes and over-splitting for mesh continuity preservation. The encoder can use a non-fully connected mesh applicable to video coding standards. The encoder can implement dedicated splitting for motion continuity preservation.

At2006, the processed video is stored in memory or transmitted to another component or system using a transceiver. In some embodiments, the method2000involves encoding (or compressing) video data using the estimated motion.

It should be understood that steps of one or more of the blocks depicted inFIG.26may be performed in a different sequence or in an interleaved or iterative manner. Further, variations of the steps, omission or substitution of various steps, or additional steps may be considered.

The embodiments described herein are implemented by physical computer hardware, including computing devices, servers, receivers, transmitters, processors, memory, displays, and networks. The embodiments described herein provide useful physical machines and particularly configured computer hardware arrangements.

The total square error over the image is with pe=Prob(e∉INTRA):

Withthe domain defined by the union of all the elements

With V(e) the set of vertices of the finite element e

Solving in matrixial form

A condition for minimizing is given by null derivatives for all motion vector control points components:

In matrixial sense it means ∀n,

The few coming lines uses matrixial derivation.

Defining S(n), the set of finite elements having the node numbered n as vertex

is equivalent to

It can be rewritten for a better readability as:

Rewriting all the problem in a matrixial form:

It is equivalent to solve=

FIG.24shows an equivalent system (note: A is symmetric)where the sub-bloc 2×2

And the sub vector 2×1

Optical Flow: Equation Generalization with Slaves+Intra Probability, with Constraints Directly Introduced

Solving in matrixial form

A condition for minimizing is given by null derivatives for all master motion vector control points components:

In matrixial sense it means ∀n,

The few coming lines uses matrixial derivation. Note that the node n is a master node.

We define:

S(n), the set of finite elements having the node numbered n as vertex

Index of master nodes j are notedj, and index of slave nodes i are notedi. With this notation: S(n)∩(n)Ø,

We can find a combination of motion vectors includingjin(n), such that:

is equivalent to

This can be rewritten as:

Looking at the solution, even if attractive because the dimension of the problem (number of variables) is lower compared to the unconstrained problem it remains very complex in terms of implementation.

Optical Flow: Equation Generalization with Slaves+Intra Probability

Finding the set of optimal nodes

can involve solving.=.

Additional constraints are a set of new equations. For a slave node, two nodes j0(k) and j1(k) (they could be master of slaves) can be used for the computation of the motion Mkare such that:

This can be rewritten as the equation: 2 Mk−Mj0(k)−Mj1(k)=0.

Accounting for all the slave nodes, constraints can be written in a matrixial form: C·M=0, where, as in the unconstrained case, M is composed of the node motion vector coordinates. C is sparse where cijcomposed of 2, −1 and 0 values (or opposite values).

The new problem can be written as:

Using Lagrange description problem minimizing:

The solution of the unconstrained problem in terms of solution is provided inFIG.24, Introducing the constraints, it comes to solve an extended system′′=′ as shown inFIG.13. The new composed matrix A′ is also sparse and symmetric.

The intermediate λ values are just ignored when extracting the M part of the solution. In the same manner, constrained motion vectors (slave nodes) can be readjusted from unconstrained motion vectors (master nodes) for accuracy reasons. This is not mandatory but can be done for accuracy reasons.

As an improvement compared to the Horn-Schunck approach, introducing a motion homogeneity constraint in the Mesh model does not require any user defined smoothing parameter to tune the algorithm behavior.

S=peΣkϵV(e)(Mke−Me)2avoiding too big deformations

As set out in Annex 1:

With C=Card(e)=4

Defining S(n), the set of finite elements having the node numbered n as vertex

is equivalent to

It can be rewritten for a better readability as:

It is a particular case of general equations with slave nodes (see Annex 3): the fourth node (bottom right in each rectangle) can be considered as a slave node.

First: the relation between nodes in the affine model case is:

And the continuity constraint is:

The constraint to apply per element e is:

Then the process solves the system′′=′, as described in Annex 3.