Patent Description:
In a block based video coding standard, like H. <NUM>/High Efficiency Video Coding (HEVC) or H. <NUM>/Advanced Video Coding (AVC), a picture is partitioned into blocks. Each block is then predicted by using either intra or inter prediction. While the former prediction method uses only decoded samples within the same picture as a reference, the latter uses displaced blocks of already decoded pictures [<NUM>]. Once the predicted blocks are obtained, they are used to calculate residual blocks which are further processed before encoding. Information related to the tools and techniques applied at the encoder are to be sent to the decoder for reconstruction of the images.

Intra prediction is dealt with the utmost importance in all the video coding standards. <NUM>/AVC has <NUM> intra modes and for the latest H. <NUM>/HEVC there are <NUM> modes. The encoder decides the best intra mode which minimizes the cost function and that mode is signaled in the bitstream to the decoder. The cost function J is defined as: <MAT> where D is the distortion between the original and predicted blocks, R is the number of bits associated with the intra mode and λ is the Lagrange parameter that determines the trade-off between D and R [<NUM>].

<NUM>/HEVC angular prediction provides high-fidelity predictors for objects with directional structures. The additional Planar and DC prediction modes can effectively model smooth image areas [<NUM>]. HEVC has also some advanced processing techniques for improving intra prediction, like filtering of reference samples before actual prediction and post-processing of the predicted samples. There is, however, an ongoing wish to further improve coding efficiency.

Naturally, it would be also be favorable to have a concept at hand which increases the coding efficiency of inter picture prediction where the transmission of the motion information, i.e., the motion field, consumes a considerable amount of the available data rate.

Template matching (TM) is a texture synthesis technique used in digital image processing. This can be applied for intra prediction as well. The known pixels present above and left of the current block is called the template. The method may find the best match for the template in the reconstructed frame by minimizing the sum of squared differences (SSD). Finally, the TM block is copied to the current block which becomes the prediction. The TM intra mode may not require any side information for reconstruction at the decoder. On the other hand, the search algorithm for the template match has to be repeated. This leads to high decoder complexity.

Intra prediction by TM was first proposed in [<NUM>] for H. In [<NUM>] from the same authors, TM with more than one predictor was proposed. Some other proposals related to TM intra prediction can be found in the literature [<NUM>, <NUM>, <NUM>, <NUM>, <NUM>]. All the works mentioned above concentrates more on the coding gain from TM without considering much about the complexity increase.

<NPL>" describes an improvement over H. <NUM>/AVC by use of a template matching method. In particular, this article presents some improvements over a previous proposal of adding a template matching prediction mode to H.

<CIT>) describes a reduced complexity template matching prediction concept for video encoding and decoding, according to which the template matching prediction is selectively constrained using one or more constraining criterion that reduces a complexity of performing the template matching prediction.

Thus, it is an object of the present invention to provide a improved predictive picture coding concept using template matching. For example, it may, for a given computation complexity, result in an increased coding efficiency.

This object is achieved by the subject matter of the independent claims of the present application.

In accordance with a first aspect of the present application, template matching is used for predictive picture coding and the predictive picture coding is made more efficient in terms of computational complexity by sub-dividing the search area within which template matching is performed at the encoder side, into subareas and signaling this subarea within which the selected set of one or more patches are located, in the data stream to the decoder. The decoder in turn, performs template matching using the subarea signaled in the data stream as the search area. Thereby, a good trade-off may be achieved between keeping the signalization overhead low on the one hand and avoiding a too-high computational complexity at the decoder side on the other hand. In other words, the decoder may restrict the computational efforts associated with template matching to the signaled subarea.

In accordance with an embodiment, patch averaging is used as a basis for the predictive coding of the predetermined block, i.e. averaging of more than one patch within the signaled subarea is performed, such as averaging over the p><NUM> best matches. The inventors of the present application found out that, in the case of using patch averaging, the prediction preciseness-loss that comes along with restricting the patches participating in the averaging to the subarea signaled in the data stream, is negligible compared to the advantage of being able to keep the computational complexity at the decoder side low by restricting the template matching process at the decoder side to the signal subarea only.

In accordance with a further aspect of the present application, template-matching-based predictive picture coding is made more efficient when taking rate/distortion coding efficiency into account along with the computational complexity involved therewith, by setting a size of the search area within which template matching is performed, depending on side information in the data stream. For instance, the side information comprises one or more of the group consisting of a picture size parameter indicating a picture size, a tile-subdivision information, indicating a number of independently coded picture tiles, and a picture-content class identifier, distinguishing, for instance, panoramic pictures from non-panoramic pictures. Setting the search area in this manner results in an efficient comprise between computational complexity on the one hand and coding gain using the template matching-based predictive coding on the other hand.

Advantages of the present application are the subject of the dependent claim. Preferred embodiments of the present application are described below with respect to the figures among which:.

The following description of preferred embodiments of the present application starts with a specific embodiment relating to intra picture prediction. In this embodiment, several aspects of the present application are involved. Later on, further embodiments of the present application are described which selectively adopt certain characteristics and features of this initially described embodiment. Insofar, it should be noted that, firstly, the initially described embodiment should not be treated as limiting the embodiments described later on. On the other hand, the features described with respect to the initially described embodiment may individually, in groups or all together, be transferred onto the embodiments described later on in order to result in even alternative embodiments so that the description brought forward with respect to the initially described embodiment should also be treated as a reservoir for explaining possible implementation details with respect to the embodiments described later on.

In accordance with the embodiment described next, the idea of TM is extended for intra picture prediction. This extension might be used, for instance, as a new intra prediction mode in a picture or video codec such as HEVC, H. <NUM> or some other block-based predictive picture/video codec. Later on it will be noted that this extension might be transferred onto inter picture prediction as well.

As mentioned previously, typical TM intra mode results in high decoder complexity even though no side information is being send. This might be unfair towards the decoder. The embodiment described below targets to reduce the complexity despite compromising little on coding efficiency. For the time being, the research was narrowed down to HEVC intra prediction and initial investigation was conducted on different parameters of TM intra mode, like the template size, multiple predictors. Based on this, <NUM> pixel wide rotated-L shaped template and three predictors were decided upon for the mode further described now.

The mode discussed herein operates as follows: consider an N×N block <NUM> to be predicted. As shown in <FIG>, in the reconstructed frame12 , (N+<NUM>)×<NUM> pixels above and <NUM>×N pixels left of the block <NUM> are taken as the template <NUM>. Rather than searching the entire frame <NUM> for the best match, one searches inside a window <NUM>. Based on the frame size of the video sequence, the window size is decided. This window <NUM> is further divided into five regions <NUM> (<FIG> and <FIG>) illustratively with respect to one region <NUM>, namely region no. <NUM>, the three best template matches <NUM> from each region <NUM> are found by minimizing SSD. The average <NUM> of the respective TM blocks <NUM> becomes the prediction <NUM> of the current block <NUM>. Advantage of the rate-distortion optimization algorithm of the HEVC encoder according to (<NUM>) might be taken to decide which region <NUM> gives the best prediction. The information related to the chosen region is signaled in the bitstream. The decoder searches for the best matches only in that signaled region and uses the average of the TM blocks for the final prediction. The aforementioned intra mode may be added to the encoder candidate list of luma samples for all available intra block sizes along with its <NUM> other intra modes.

The HEVC test model reference software (HM version <NUM>) and the common test conditions [<NUM>] have been used for experiments. All tests were restricted to All Intra (AI) main configuration.

<FIG> shows a grayscale histogram of the number of TM blocks with respect to the current block inside a <NUM>×<NUM> window for BasketBallDrill of QP = <NUM>. In order to reduce the complexity of the search algorithm the position of TM blocks <NUM> with respect to the current block <NUM> has been investigated. The study indicates that the TM block is more often present in the neighborhood of the current block as shown in <FIG>. This clearly justifies the use of a window <NUM> for searching in the mode presented here.

As to search window size, an investigation into the effect of the search window size has been carried out. Window sizes M = <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> were considered for this. The general tendency from the research result is that the bigger the window <NUM>, the better the performance as shown in <FIG>. However, there are three main observations to be noted here. First, the gain saturates after a particular value of M and second, this value of M varies with different classes. Third, large window points to high complexity as shown in <FIG>. These remarks led to the idea of an adaptive window for searching where the window size varies with frame characteristics such as the frame size of the sequence.

Further an investigation on the position of second best TM block with respect to first has been performed. In the TM mode introduced with respect to <FIG>, the average of three best TM blocks issued for prediction. For reducing complexity, it was important to understand the position of the second and third best TM blocks with respect to the first one. One wanted to know if the three blocks are spread out or near. The research results show that they are more often close to one another as shown in <FIG> shows a histogram of the number of second best TM blocks (log) with respect to the first block, for BasketBallDrill with QP = <NUM> for <NUM> frames. This observation guided to the division of search window <NUM> into different regions <NUM>. Based on the experimental results, an adaptive search window <NUM> has been assessed where its size is varied depending on the frame size. The window size is M×M where M=n×<NUM> (see <FIG>) and n is calculated as, if N ≥ <NUM>, n = <NUM> × A else: <MAT>.

It should be noted here that the proposed adaptive search window <NUM> is applied only to smaller blocks. The value of A is chosen in such a way that it is a good trade-off between coding efficiency and complexity.

The new TM intra mode will work well for HEVC when there is a good trade-off between performance and complexity. Therefore, the value of A should be chosen carefully. One considers the value of A for Region1 to be A1, for Region2 and <NUM> to be A2 and, for the rest as A3. Similarly, n1 is related to A1, n2 to A2 and n3 to A3. We carried out tests for different combinations of A1, A2 and A3 with A = <NUM> as the lower bound and A = <NUM> as the upper bound. The search window is adapted according to the formula (<NUM>). Our experimental results indicate that further coding efficiency can be achieved by unequal values of A as shown in <FIG>.

The mode discussed above can achieve an average BD-rate gain of -<NUM>% for classes A to E with <NUM>% decoder complexity (Table.

It can be seen that the proposed mode can achieve gain as high as -<NUM>% (for Johnny). According to the tests, an average area of <NUM>% of a frame is predicted by TM mode as shown in <FIG>. The experimental results indicates that TM mode works best for sequences with homogeneous structures.

In the following, embodiments for encoder and decoder are described. These embodiments use certain aspects of the above-presented TM mode and, accordingly, represent a kind of broadening of the specific mode presented above and having formed the basis of the experiments discussed above. In order to ease the understanding as to how the embodiments described below are related to the embodiments described above, the same reference signs are used and the figures relating to the subsequent embodiments.

<FIG> shows an encoder or an apparatus for picture coding, respectively. The apparatus is generally indicated using reference sign <NUM> and comprises, internally, a selector <NUM> and a predictive encoder <NUM>. <FIG> also shows an optional internal configuration of selector <NUM> and predictive encoder <NUM>. These details are described further below.

Generally speaking, apparatus <NUM> is for coding picture <NUM> into a data stream or bitstream <NUM>. Apparatus <NUM> is a block-based coder which codes picture <NUM> into data stream <NUM> in units of these blocks. Block <NUM> is such a block. It should be noted that although block <NUM> is illustrated as being quadratic in <FIG> as well as in the preceding figures, the embodiments of the present application are not restricted to such kinds of blocks. Block <NUM> may be rectangular or of any other shape. According to the block-based nature of the operation of encoder <NUM>, encoder <NUM> may encode each block of picture <NUM> into a data stream <NUM> in a manner described herein, or may choose, for each block, one of several coding modes among which one corresponds to the coding concept described with respect to <FIG>. The one or more other coding modes which encoder <NUM> might support may include other intra picture prediction and/or inter picture prediction modes. A coding order <NUM> may be defined among the blocks into which picture <NUM> is subdivided with this coding order traversing, for instance, picture <NUM> in a row-wise raster scan order from the top of picture <NUM> to the bottom of picture <NUM> as illustrated in <FIG>. "Generally leading in a row-wise raster scan order from top to bottom" shall also include any hierarchical ordering. For instance, the blocks to which block <NUM> belongs, may be leaf blocks of a multi-tree subdivision of tree wood blocks into which picture <NUM> is subdivided regularly in rows and columns of such tree wood blocks. The order <NUM> may traverse the tree wood blocks row-wise from top to bottom wherein, within each tree wood block, the order traverses the leaf blocks of the respective tree wood block in accordance with some predetermined order such as a depth-first traversal order before proceeding to the next tree wood block. Encoder <NUM> may not have to encode picture <NUM> sequentially using order <NUM>, but blocks preceding in accordance with order <NUM> could be regarded as being available at the decoder side and thus, as being available for prediction purposes with respect to a current block such as block <NUM> while blocks succeeding in accordance with order <NUM> could be regarded as being unavailable at the decoder side. In other words, portions of picture <NUM> composed of blocks preceding in accordance with coding order <NUM> are available in already reconstructed form in encoder and decoder at the time of predictively encoding/decoding block <NUM>.

The selector <NUM> selects, out of a search area <NUM> of picture <NUM>, a set <NUM> of one or more patches which match a template area <NUM> which is adjacent to current block <NUM>. As already described above, the template area may cover pixels to the top of, and the left of, current block <NUM>. In the embodiments described above, the template area <NUM> has been a two-pixels-wide L-shaped region bordering the top and left-hand edge of block <NUM>. It should be noted, however, that region <NUM> may also have some other shape, that region <NUM> may be of another width and that region <NUM> may have another spatial relationship with respect to block <NUM>.

The predictive encoder <NUM> is configured to encode predictively block <NUM> into data stream <NUM> based on the set <NUM> of one or more patches. To be more precise, predictive encoder <NUM> construes a predictor <NUM> on the basis of set <NUM> and uses this predictor <NUM> as a prediction of block <NUM>. A residual encoder <NUM> of predictive encoder <NUM> encodes the prediction residual into data stream <NUM>. Residual encoder <NUM> may be a transform-based residual encoder <NUM> which, for instance, spectrally decomposes the prediction residual. Further, residual encoder <NUM> may use entropy coding so as to losslessly encode the quantized residual signal into data stream <NUM>.

As illustrated in <FIG>, the search area <NUM> is spatially subdivided into a plurality of subareas <NUM>. <FIG>, the number S of these subareas <NUM> has illustratively been chosen to be <NUM> whereas the number has been <NUM> in the embodiments of <FIG>, but it should be noted that the number S may be any number greater than <NUM>. Importantly, apparatus <NUM> is configured to signal within data stream <NUM> as to which subarea <NUM> the set <NUM> of one or more patches is located in or belongs to. This information <NUM>, thus, indicates one of the S subareas or regions <NUM> and may be coded into data stream <NUM> by encoder <NUM>, for instance, predictively, such as, for instance, using spatial prediction relative to the same information <NUM> with respect to any other block of picture <NUM> preceding an order <NUM>, and/or using entropy coding such as, for instance, context-adaptive entropy coding.

Thus, in accordance with a coding mode just described, encoder <NUM> encodes into data stream <NUM> for block <NUM> the prediction residual <NUM> for block <NUM> as well as information <NUM>.

Before proceeding with the description of the encoder of <FIG>, reference is made to <FIG> which shows a decoder, or apparatus for picture decoding, fitting to the encoder of <FIG>. The apparatus of <FIG> is generally indicated using reference sign <NUM> and comprises a selector <NUM> and a predictive decoder <NUM>. Generally, apparatus <NUM> of <FIG> is configured to decode picture <NUM> from data stream <NUM>. As described with respect to <FIG>, decoder <NUM> of <FIG> may be a block-based decoder. That is, decoder <NUM> may decode picture <NUM> from data stream <NUM> in units of blocks to which block <NUM> belongs, and may either decode each of these blocks using the mode presented hereinafter, or may select for each block of picture <NUM> one mode out of a set of modes which includes the just-outlined mode in addition to, for instance, one or more intra picture prediction modes and/or one or more intra picture prediction modes. As described with respect to <FIG>, decoder <NUM> may obey some coding order defined among the blocks into which picture <NUM> is subdivided, in decoding the blocks of picture <NUM> from data stream <NUM>.

Selector <NUM> selects, out of a search area <NUM> of picture <NUM>, set <NUM> of one or more patches which match the template area <NUM> of current block <NUM>. Predictive decoder <NUM> predictively decodes current block <NUM> from data stream <NUM> based on the set <NUM> of one or more patches, namely, by forming a prediction signal <NUM> based on the latter and correcting this prediction signal <NUM> using the residual signal <NUM> which a residual decoder <NUM> of predictive decoder <NUM> decodes from data stream <NUM>. Predictive decoder <NUM>, thus, derives a reconstruction or reconstructed signal <NUM> for current block <NUM> which may then be contained in a search area <NUM> used with respect to any other block of picture <NUM> following encoding order <NUM>.

Interestingly, the search areas <NUM> and <NUM>, within which encoder of <FIG> and decoder of <FIG> perform the template matching for current block <NUM>, differ. The encoder <NUM> of <FIG> performs the template matching, or the selection, respectively, by selector <NUM> within all subareas or regions <NUM> the overall search area <NUM> is composed of. As illustrated in <FIG>, however, compared thereto, decoder <NUM> selects its search area <NUM> out of the plurality of subareas <NUM> the overall search area <NUM> associated with block <NUM> is subdivided into, with performing the selection which is illustrated in <FIG> at <NUM>, depending on signalization <NUM>. As set out above, with respect to <FIG>, this concept of providing decoder <NUM> with a hint <NUM> as to which subarea <NUM> of the encoder-sided search area <NUM> the template matching within selector <NUM> of decoder <NUM> should be restricted to, enables a considerable reduction in computational complexity on the side of the decoder, with merely minor penalties in coding efficiency associated with the usage of template matching.

As already described above with respect to the encoder, entropy coding might be used in order to code the prediction residual <NUM> for block <NUM> into data stream <NUM>; accordingly, residual decoder <NUM> may use entropy decoding in order to obtain the prediction residual <NUM> from data stream <NUM>. Additionally, and/or alternatively, the residual signal <NUM> may be conveyed within a data stream in a transform domain such as in the form of a spectral decomposition, and residual decoder <NUM> may be configured to re-transform the residual signal into a spatial domain using, for instance, the inverse of the spectral decomposition used at the encoder-side.

After having described rather generally encoder <NUM> of <FIG> and decoder <NUM> of <FIG>, a more specific description is outlined below. As illustrated in <FIG>, selector <NUM> performs, for each region <NUM>, a best match search or template matching <NUM>, while selector <NUM> of decoder <NUM> performs such best match search or template matching <NUM> merely with respect to the selected region which forms the decoder-side search area <NUM>. <FIG> illustrates how this best match search may look like.

The input for this process is the set <NUM> of patches within the respective search area for which the best match search <NUM> is performed. Again, selector <NUM> of encoder <NUM>, performs such a best match search <NUM> for each region <NUM> area <NUM> is composed of, while selector <NUM> of decoder <NUM>, performs process <NUM> merely for the signaled region <NUM> which, thus, forms the decoder-side search area <NUM>. Set <NUM> may, for instance, include all patches which may be inscribed into region <NUM>. A patch may be deemed to be inscribable into region <NUM> if, for instance, more than half of its pixels lie within region <NUM>, or, alternatively, as long as the upper left pixel of the respective patch or the middle or center pixel thereof lies within region <NUM>, additionally requiring, for instance, that all pixels within each patch of set <NUM> have already been reconstructed. Depending on the size of region <NUM>, set <NUM> may, thus, include a high number of patches, wherein <FIG> illustratively shows merely two patches 70a and 70b of set <NUM>. It should be noted that set <NUM> of patches may not include all possible patches inscribable into, or belonging to, region <NUM>. For instance, patches of set <NUM> may offset relative to each other by a mutual pitch equal to one pixel, or by a mutual pitch which is longer than one pixel. Each patch 70a and 70b of set <NUM> is composed of two portions so that the respective patch is congruent to the combination of template <NUM> and block <NUM>: each patch 70a and 70b comprises a template counterpart area denoted <NUM> in <FIG> and being congruent to template <NUM>, and a portion <NUM> which is congruent to block <NUM> and is located relative to template counterpart area such as the template area <NUM> located relative to block <NUM>.

Let's say, the number of patches 70a and 70b thus forming set <NUM> would be Q. Process <NUM> would then determine for each of these Q patches 70a and 70b a deviation δ<NUM>.

For instance, as denoted above, the sum of square differences (SSD) could be used to this end. That is, δ<NUM> could be determined for each patch i of set <NUM> by overlaying the template counterpart area <NUM> of patch i with the template area <NUM> and summing up the squares of differences between co-located pixels within these areas <NUM> and <NUM>, respectively. Naturally, another matching criterion could be used instead of the SSD. Broadly speaking, a similarity measure, such as the inverse of δ<NUM>. δQ, or a dissimilarity measure, such as δ<NUM>. δQ, is determined for each patch of set <NUM> which measures the similarity/dissimilarity of its respective template counterpart area <NUM> to template area <NUM>. These measures δ<NUM>. δQ or the inverse thereof, are then used as a matching criterion in order to select p patches among set <NUM>; namely, those, which are most similar to template <NUM> in terms of the similarity/dissimilarity measure, i.e. those patches of set <NUM>, for which the deviation measure is smallest or similarity measure is highest.

It should be noted that p had been chosen to be <NUM> in the examples provided above with respect to <FIG> and is illustrated to be <NUM> in <FIG> and <FIG>, but in accordance with alternative embodiments of <FIG> and <FIG>, the number p may be any other number greater than <NUM> with this being true for <FIG> also. With respective to the embodiments of <FIG> and <FIG>, it is even true that p might be <NUM>, in which case the subsequently mentioned averager might be left off.

It should be noted that normal averaging is only one of the many ways of predicting the final samples. Weighted averaging as in eq. (<NUM>) can also be applied. For p = <NUM>, <MAT> where α, β, γ are the weights and p1, p2, p3 are predictor <NUM>, predictor <NUM> and predictor <NUM> respectively, and FINAL is the final predictor.

Experimental results indicate that screen content or screen content like sequences has the best results when p=<NUM>. This can possibly be due to the reason that the effect of smoothing from averaging deteriorates the sharpness in such sequences. In order to effectively model this behavior, without doing much computations, the final prediction can be modified as following: For p = <NUM>,.

Let Err1, Err2 and Err3 be the SSD errors associated with predictor <NUM>, predictor <NUM> and predictor <NUM> respectively. Let Thres be the threshold SSD error whose value depends on Err1 with, for instance, Err1 < Err2 and Err1 < Err3, i. e Err1 being the minimum SSD value. <IMG>
<IMG>.

Thus, the choice of number of predictors for the final prediction of the samples depends on the error value associated with the first predictor. For example, Thres may be set to be α · Err1 with, for example, α being between <NUM> and <NUM> inclusively. The above example may easily transferred onto a number of patch predictors greater than <NUM>, or merely two.

Summarizing the most recent note, averaging might be extended in a way so that the above mentioned averaging of patch predictors in set <NUM> may include a first step of excluding those members of set <NUM> whose match with the template area <NUM> is more than a predetermined threshold worser than the best matching candidate/member of set <NUM> and then skipping any averaging in case of merely the best matching member remaining in set <NUM> and using the latter instead, or restricting the averaging to the remaining subset of members whose match was good enough, or similar enough to the one of the best matching member, wherein, as mentioned above, thresholding with a threshold which is a predetermined multiple of the best matching candidate's difference measure may be used for exclusion or sorting out.

With this, the outcome of best match search process <NUM>, <FIG>, is a set of one or more (namely p) patches from which set <NUM> forms a candidate set <NUM> of patches for the respective region for which the respective best match search <NUM> has been performed, or forms the final set <NUM> of patches directly, such as in the case of decoder where, as explained above, the template matching process <NUM> is merely performed with respect to the signaled region <NUM>.

Accordingly, the selector <NUM> of encoder <NUM>, additionally comprises a region selector <NUM> which selects one of the S candidate sets <NUM>. To this end, region selector <NUM> may already take into account the amount of data needed to convey information <NUM> and <NUM> associated with each of candidate sets <NUM>, thus including the amount of bits associated with coding information <NUM>, or region selector <NUM> may simply select the candidate set <NUM>, the average of which with respect to portion <NUM> results on the lowest deviation from block <NUM> or the like.

Summarizing, region selector <NUM> of selector <NUM> selects one out of candidate sets <NUM> and, accordingly, one of regions <NUM> of search area <NUM>, and signals the selected one of region <NUM> by way of information <NUM> within data stream <NUM>. This signaled region <NUM>, then forms the search area <NUM> for decoder <NUM>.

With respect to <FIG>, it is noted that "match" between the individual patches of set <NUM> on the one hand and template <NUM> on the other hand, may be determined in a manner other than using SSD or the like. Further, patches of set <NUM> and, accordingly, of set <NUM> finally selected by selectors <NUM> and <NUM>, need not be congruent to the composition of template <NUM> and block <NUM>. For example, the patches could be of the same size and congruent to block <NUM> only, with the matching criterion indicating a best match for those patches for which the transition from template <NUM> towards the respective patch in case of replacing block <NUM> by the respective patch, would be smoothest.

In case of the number of patches in sets <NUM> and <NUM>, respectively, i.e., p > <NUM>, the prediction encoder <NUM> of encoder <NUM> and the predictive decoder <NUM> of decoder <NUM> would comprise the optional averagers <NUM> and <NUM>, respectively, shown with dashed lines in <FIG> and <FIG> which would average portions <NUM> of the patches within set <NUM> so as to result in predictor <NUM>. In case of p = <NUM>, the averaging modules <NUM>, <NUM> would be left off and the only patch within set <NUM> would form predictor <NUM>. The averaging process performed by modules <NUM>, <NUM> would, for instance, be a pixel-wise averaging, such as using mean or median, of co-located pixels in case of overlaying the one or more patches of set <NUM>, or, to be more precise, the portion <NUM>. The predictor <NUM> would thus be a block of pixels of the same size as block <NUM> and could form the predictor on the basis of which the residual encoding/decoding is performed. It is noted that the above description of <FIG> revealed that the restriction with respect to predictor preciseness of predictor <NUM>, that comes along with restricting the template matching process <NUM> within decoder <NUM> to one of the subareas <NUM> within the overall search area <NUM>, is less significant than the reduction in computation complexity achieved by this measure at the decoding side owing to the restriction of the amount of template matching tests Q to be performed; namely, towards merely ones for the signaled region rather than for all regions.

It is also noted that a closer inspection of the inspection of the results shown in <FIG> revealed that it is advantageous if the search area <NUM> is subdivided into the plurality of subareas <NUM> such that a first subset of the plurality of subareas are horizontally longitudinal areas neighboring each other vertically, while a second subset of the plurality of subareas are vertically longitudinal areas neighboring each other horizontally. In the case of <FIG>, for instance, such a first subset of subareas has been formed by regions <NUM> and <NUM>, and a second subset of subareas has been formed by regions <NUM> and <NUM>. In the case of <FIG>, horizontally longitudinal areas are regions <NUM>, <NUM> and <NUM>, while the vertically longitudinal areas are regions <NUM>, <NUM> and <NUM>. Taking into account the fact that in case of using an exemplary coding order as shown in the above figures with respect to <NUM>, already reconstructed/already encoded samples generally lie at the top of, and to the left of, current block <NUM>, it might be advantageous if the first subset of subareas and the second subset of subareas, i.e., the horizontal and vertical ones, mutually extend away from each other with the left-hand side of the horizontal regions and the upper side of the vertical regions being nearest to each other.

In accordance with an embodiment of the present application, signalization <NUM> signals the subarea <NUM> which the set <NUM> of one or more patches is located in, in the form of an index which signalizes this subarea <NUM> in a manner where this index points to a one-dimensional list of the subareas <NUM>. That is, information <NUM> does not point to any of regions <NUM> of search area <NUM> two-dimensionally such as in form of a two-dimensional vector having two components, but rather indexes one of these regions <NUM> using a scalar the value of which is mapped onto an ordinary scale of addresses associated with the regions <NUM>. For instance, each region <NUM> of search area <NUM>, has an integer value associated therewith, with the integer values of the regions <NUM> being mutually different and forming an immediately consecutive series of numbers starting, for instance with <NUM> or <NUM> or any other value.

It should be noted with respect to the embodiment just described with respect to <FIG>, that the overall search area <NUM> could be chosen to not vary depending on the size of picture <NUM>. In other words, it could be that the size of area <NUM> could, for blocks of pictures having identical position with respect to, for instance, the upper left corner of the respective picture, the same size irrespective of the size of picture <NUM>. In other words, while encoder and decoder would be able to cope with pictures <NUM> of different size, the search area <NUM> could be chosen to be of the same size irrespective of the size of picture <NUM> which block <NUM> is part of. Furthermore, in accordance with the embodiments described with respect to <FIG> and <FIG>, the search area <NUM> represented a window of a certain size, positioned at a predetermined relative spatial location with respect to current block <NUM> so that for all blocks for which the predictor <NUM> is determined in the manner described with respect to <FIG> and <FIG>, and for which the window forming search area <NUM> does not extend beyond the borders of picture <NUM>, the search area <NUM> is of the same shape and size. The predetermined relative spatial location meant, for instance, that the window <NUM> is separated from block <NUM> by template area <NUM> which adjoins block <NUM>, and extends away from block <NUM> starting at template area <NUM>. Other possible predetermined spatial relationships would be feasible as well such as the window <NUM> being distanced from the boarder of block <NUM> by some predefined distance which might be possibly different from the template area width. However, the size of window <NUM> may also be set in a manner not independent from the location of block <NUM> within the picture (provided window <NUM> fits completely into picture <NUM>). In accordance with alternative embodiments, for instance, the search area <NUM> is defined to be formed by the complete area of already reconstructed pixels of the current picture <NUM> relative to current block <NUM> illustrated by cross-hatching, for instance, in <FIG>. Alternatively, search area <NUM> may cover an area extending until the upper edge of picture <NUM>, and until the left-hand side of picture <NUM> but not extending beyond the right-hand side of block <NUM>. In the latter cases, the number of regions <NUM> of the search area <NUM> may be chosen to be constant or independent from, or chosen to vary with the size of the search area <NUM> which, in turn, depends on the location of block <NUM> within picture <NUM>. For instance, in the former case, the size of regions <NUM> may increase with increasing size of area <NUM> while the number S of regions <NUM> remains constant, and in the latter case, the number S of regions <NUM> may increase with increasing size of area <NUM> while the size of regions <NUM> remains constant. The latter circumstance of not using a fixed-window-size area <NUM> as the search area at the encoder-side would increase the computational complexity of the encoder-side but might still lead to moderate computational complexity at the decoder-side owing to the signalization of the subarea <NUM> to be used as search area <NUM> at the decoder-side.

The latter circumstance that the size of search area <NUM> may, provided that the search area <NUM> does not extend across borders of picture <NUM>, be set by encoder <NUM> and decoder <NUM> dependent on certain characteristics of picture <NUM>, is used in accordance with the embodiment described later on with respect to <FIG> and <FIG>, and is merely optional with respect to the embodiment of <FIG> and <FIG>. This optional circumstance is depicted in <FIG> and <FIG> by way of reference sign <NUM> which indicates optionally present side information within data stream <NUM> dependent on which the size of search area <NUM> may be set. This side information <NUM> may comprise one or more of the group consisting of a picture size parameter indicating a picture size of picture <NUM>, i.e., the size of the picture to which block <NUM> belongs, a tile-subdivision information indicating a number of independently coded picture tiles of the picture <NUM> to which block <NUM> belongs, and a picture content/identifier which semantically distinguishes between different types of scene content in the picture to which the respective block <NUM> belongs. This side information <NUM> may have a greater scope and may be valid, for instance, for a picture sequence of a video which the predetermined picture block <NUM> is part of. For instance, the side information <NUM> may be conveyed within a VPS or SPS, for instance.

In case of area <NUM> being a window spatially positioned relative to block <NUM>, which is of predetermined size - dependent on, or independent from side information <NUM>- it is noted that special measures may be taken at encoder and/or decoder if window <NUM> extends beyond borders of picture <NUM>. Obviously, encoder <NUM> may not perform template matching for regions <NUM> lying outside picture <NUM>, at least for those, completely lying outside picture <NUM>. They are not available. Encoder <NUM> may, however, additionally skip template matching for those regions <NUM>, partially extending outside picture <NUM>. They might be interpreted as not being available, too. For the decoder <NUM>, this restriction might be of no interest, as it is informed on the chosen region <NUM> via signalization <NUM> and performs the template matching within this region <NUM> only. The decoder <NUM> may, however, determine which region <NUM> the encoder <NUM> has subject to template matching and which not, in the same manner, namely by determinind which region <NUM> is outside picture <NUM> or extends beyond the picture borders, and accordingly, is aware of the set of regions <NUM> which the signalization <NUM> may possibly appoint the decoder's search area <NUM> for block <NUM>. This set of available regions <NUM> might be reduced compared to the complete set of regions <NUM> of a template <NUM> completely residing within the picture area. This circumstance might been seen as a reduction of a size of the area <NUM> for which template matching is performed within the encoder. For blocks <NUM> sufficiently distanced from the picture borders, especially the upper and left border, the window <NUM> would be of the same size within the respective picture, or differently speaking, for all picture positions sufficiently distanced from picture borders, blocks <NUM> positioned at such positions have a template <NUM> of the same size associated therewith. The circumstance of a reduced set of "signalable" regions <NUM> might be exploited for reducing the signaling overhead associated with signalization <NUM>. That is, the manner at which signalization <NUM> is coded into, and decoded from data stream <NUM>, may be dependent on the reduction of the "available" set of regions <NUM> relative to the complete set of regions so that the smaller this reduced set is, the smaller the number of bits is which is consumed in the data stream <NUM> for signalization <NUM>. The value set of signalization <NUM> may be reduced accordingly, or the context for entropy coding/decoding signalization <NUM> may be adapted to the size of the "available" region set. Even alternatively, or additionally, as soon as the number of the reduced set of available regions <NUM> is smaller than a predetermined number, then the described template matching mode might be disallowed for block <NUM> at all with a remaining set of coding modes such as other intra picture prediction modes or inter picture prediction modes being available for block <NUM> instead. As done in case of signalization <NUM>, changes might be done in coding/decoding a signalization in data stream <NUM> which, in accordance with an embodiment, is present in data stream for blocks such as block <NUM> so as to signal its coding mode. For example, the cardinality of a set of signalable modes for block <NUM> might be chosen independent from the number of available regions <NUM>, with the template matching mode being part of this set or not depending on the number of available regions <NUM>. Alternatively, a set of signalable modes for block <NUM> might include or not include the template matching mode depending on the number of available regions <NUM> with the cardinality of the set varying accordingly, i.e. being increased by one in case of the number of available regions <NUM> not being smaller than the predetermined number, than compared to the case of the number of available regions <NUM> being smaller than the predetermined number.

In the same manner as just-outlined, situations may be handled, at which the search area <NUM> - might it be a template of predetermined size, positioned spatially relative to block <NUM>, or might it be an area consuming all or, or a part of the already decoded/encoded area traversed prior to block <NUM> - extends beyond borders of a slice which the current block <NUM> is located in, or beyond borders of a tile which the current block <NUM> is located in. Slices and tiles are portions of a picture into which the picture <NUM> may be divided and which are defined as independently decodable portions so that coding inter-dependencies are disallowed.

<FIG> and <FIG> show an encoder <NUM> and a decoder <NUM> in accordance with further embodiments of the present application. Encoder <NUM> and decoder <NUM> of <FIG> and <FIG> fit to each other. The functionality of encoder and decoder of these figures have already been described above with respect to <FIG> and <FIG>, to the description of which, insofar, reference is made. However, in accordance with the embodiments of <FIG> and <FIG>, search area <NUM> may not be subdivided spatially into regions <NUM>, i.e., S of <FIG> may be equal to <NUM>, and accordingly, information <NUM> may not be transmitted in data stream <NUM> and furthermore, the search area used in encoder and decoder might be the same in accordance with the embodiment of <FIG> and <FIG>. The encoder <NUM> and decoder <NUM> of <FIG> and <FIG> are, however, configured to set the size of search area <NUM>, denoted as M in <FIG> and <FIG> for ease of associating these embodiments with the description of <FIG>, depending on the side information <NUM> in data stream <NUM>. Insofar, the description brought forward above with respect to <FIG> is referred to and shall form also a description of <FIG> and <FIG>. Owing to the fact that S may be <NUM> in accordance with <FIG> and <FIG>, the region selector <NUM> might be missing in selector <NUM> and the averagers <NUM> and <NUM> might be missing in the encoder and decoder, respectively. The best match search <NUM> might be performed within selector <NUM> merely once; namely, with respect to search area <NUM> which also forms the search area <NUM> of the decoder. If, however, S > <NUM>, then the description brought forward above with respect to <FIG> to12 applies.

In other words, in accordance with <FIG> and <FIG>, the search area <NUM> and, optionally <NUM>, would be chosen to vary depending on side information <NUM>. This side information <NUM> may comprise one or more of the group consisting of a picture size parameter indicating a picture size W of picture <NUM>, i.e., the size of the picture to which block <NUM> belongs, a tile-subdivision information indicating a number of independently coded picture tiles of the picture <NUM> to which block <NUM> belongs, and a picture content/identifier which semantically distinguishes between different types of scene content in the picture to which the respective block <NUM> belongs. This side information <NUM> may have a greater scope and may be valid, for instance, for a picture sequence of a video which the predetermined picture block <NUM> is part of. For instance, the side information <NUM> may be conveyed within a VPS or SPS, for instance. The size of area <NUM> may, thus, for blocks of pictures <NUM> having identical position <NUM> with respect to, for instance, the upper left corner <NUM> of the respective picture <NUM>, a size M which differs among pictures <NUM> of different size. In other words, encoder and decoder would be able to cope with pictures <NUM> of different size, and the search area <NUM> would be chosen to be of a size M which is set depending on the size M of picture <NUM> which block <NUM> is part of. This dependency could be realized only for blocks <NUM> of a certain size such as for instance, blocks <NUM> below a certain size threshold. Naturally, the same applies for other picture characteristics using which side information <NUM> discriminates between different pictures as well and is not restricted to the picture size W which, as illustrated in <FIG>, may be measured as the picture's width. Within one particular picture <NUM>, the search area <NUM> could by of the same size M for all blocks <NUM> for which the predictor <NUM> is used for predictive coding, and for which the window forming search area <NUM> does not extend beyond the borders of this picture <NUM>. The window <NUM> could be positioned with respect to block <NUM> so that same have a predetermined relative spatial relationship. For instance, window <NUM> is separated from block <NUM> by template area <NUM> which adjoins block <NUM>, and extends away from block <NUM> starting at template area <NUM>. Other possible predetermined spatial relationships would be feasible as well such as the window <NUM> being distanced from the boarder of block <NUM> by some predefined distance which might be possibly different from the template area width.

In a manner similar to the description of <FIG> and <FIG>, the template matching mode for block <NUM> - even when not using subdivision into regions <NUM> in signalization <NUM> - may, in accordance with an embodiment, be forbidden for block <NUM> if the area <NUM>/<NUM> extends more than a predetermined amount beyond the border of the picture, slice and/or tile containing block <NUM>, or if the area <NUM>/<NUM> within the border of the picture, slice and/or tile containing block <NUM> is smaller than a predetermined size.

With respect to <FIG>, it is noted that the above embodiments related to the case where the template area <NUM> and predetermined picture block or current block <NUM> are within the same picture <NUM> with the search area <NUM> or <NUM> also being within this picture <NUM> and spatially neighboring block <NUM>. Insofar, the concepts provided by the embodiments of encoder and decoder of <FIG> formed examples for an intra picture prediction mode of the respective encoder or decoder. It is, however, possible to modify the description brought forward above with respect to <FIG> and with respect to <NUM> and <NUM>, especially, so as to arrive at further embodiments of the present application where the respective concept is used for inter picture prediction. This circumstance is illustrated in <FIG>. Block <NUM> and associated template <NUM> are shown to be part of, or being within, picture <NUM>', i.e., the picture currently encoded/decoded. Another picture <NUM> is, however, also shown in <FIG>. In particular, shown by dotted lines, <FIG> shows a block <NUM>' of picture <NUM>, which is co-located to current block <NUM>. As illustrated in <FIG>, the search area <NUM> mentioned in the aforementioned embodiments, might in fact be a portion of picture <NUM>, i.e., a picture different from the current picture <NUM>'. For instance, picture <NUM> may be a picture of the same video to which picture <NUM>' belongs, or may be a picture of another view but a picture of, for instance, the same instance as picture <NUM>'. Area <NUM> may spatially neighbor block <NUM>' and/or overlay block <NUM>'. Thus, using the alternative shown in <FIG>, all the above-described embodiments may be modified so as to form encoders/decoders supporting a special type of inter picture prediction.

<FIG> shows a modification of <FIG>. Here, area <NUM> is not chosen to have a certain spatial location relative to co-located block <NUM>' within picture <NUM>'. Rather, the search area <NUM> is part of picture <NUM> and is displaced relative to a position <NUM> within picture <NUM> which is co-located to block <NUM> within picture <NUM>' by a vector <NUM> which is conveyed within the data stream <NUM>, i.e., is derived at the decoder side from the data stream, and is signaled within the data stream by the encoder. Imagine, for instance, that vector <NUM> is transmitted in data stream <NUM> more coarsely, then the pitch at which the tested patches of set <NUM> are mutually distanced within area <NUM> and <NUM>, respectively. In this case, the template matching <NUM> would be used to determine a sort of fine tuning of vector <NUM>.

Thus, above embodiments, revealed, inter alias, improved intra prediction techniques. Intra prediction techniques are one of the most important steps in video coding, where spatial redundancy is exploited for coding efficiency. The state-of-the-art H. <NUM>/HEVC has <NUM> intra modes including <NUM> angular, DC and planar modes. However, these methods are still insufficient, especially when there are complex structures involved. This opens the way for searching for new techniques for intra prediction. Template matching has been proposed previously, but an increase in substantial complexity from the search algorithm tended to make it less attractive for further research. The above concepts provide the ability to form a fast template matching intra mode for H. <NUM>/HEVC. The discussed concepts enable to achieve an average BD-rate gain of -<NUM>% for classes A to E with <NUM>% decoder complexity. In other words, fast template matching intra mods were presented with H. <NUM>/HEVC as the possible target reference. The experimental results indicate that the new mode can achieve an average BD-rate gain of -<NUM>% for classes A to E with <NUM>% decoder complexity. On the basis of this study, an adaptive window for carrying out the searching template match may be adapted. The window size may be adapted to the frame size of the video sequence. Further, a gain to -<NUM>% with <NUM>% complexity can be achieved by unequal search region sizes. The research underlines the fact that a good prediction from a local search is a much better trade-off than an optimal prediction from a highly time consuming global search. More complexity reduction could be achieved by terminating the search algorithm after reaching a minimum threshold error value.

The inventive data stream can be stored on a digital storage medium or can be transmitted on a transmission medium such as a wireless transmission medium or a wired transmission medium such as the Internet.

Claim 1:
Apparatus for picture decoding, configured to
select (<NUM>), out of a search area (<NUM>) of a picture (<NUM>), a set (<NUM>) of one or more patches which match a template area (<NUM>) adjacent to a predetermined picture block (<NUM>); and
predictively decode (<NUM>) the predetermined picture block (<NUM>) from a data stream (<NUM>) based on the set (<NUM>) of one or more patches,
wherein the apparatus is configured to select the search area (<NUM>) out of a plurality of subareas (<NUM>) into which an overall search area (<NUM>) associated with the predetermined picture block (<NUM>) is spatially sub-divided, based on a signalization (<NUM>) in the data stream (<NUM>) by deriving an index from the signalization (<NUM>) and applying the index to a one-dimensional list of the plurality of subareas (<NUM>),
wherein the overall search area (<NUM>) is subdivided into the plurality of subareas (<NUM>) such that a first subset of the plurality of subareas (<NUM>) are horizontally longitudinal areas neighboring each other vertically, and a second subset of the plurality of subareas (<NUM>) are vertically longitudinal areas neighboring each other horizontally.