Description

The present application is concerned with a predictive coding concept using template matching which would, for instance, be applicable to hybrid video codex such as HEVC or H.264, for instance.

In a block based video coding standard, like H.265/High Efficiency Video Coding (HEVC) or H.264/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 [1]. 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. The H.264/AVC has 9 intra modes and for the latest H.265/HEVC there are 35 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:

J = D + AR, (1 )

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 [1].

H.265/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 [1 ]. HEVC has also some advanced processing techniques for improving intra prediction, like filtering of reference samples before actual prediction and postprocessing 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 [2] for H.264/AVC. In [3] 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 [4, 5, 6, 7, 8]. All the works mentioned above concentrates more on the coding gain from TM without considering much about the complexity increase.

Thus, it is an objection of the present invention to provide a improved predictive picture coding concept using template matching. For example, same 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>1 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:

Fig. 1 shows a schematic diagram illustrating template matching intra prediction;

Fig. 2 shows a schematic diagram illustrating a search area composed of five regions to be used in template matching prediction in accordance with an embodiment;

Fig. 3 shows a schematic diagram illustrating a search area composed averaging which may be used in template matching prediction in accordance with an embodiment;

Fig. 4 shows a histogram of the number of TM blocks (in logarithm gray scale) with respect to the current block inside a 128x128 window for BasketBallDrill of QP = 22;

Fig. 5 shows BD-rate results for different values of M;

Fig. 6 shows complexity results for different values of M;

Fig. 7 shows a histogram of the number of second best TM blocks (log) with respect to the first block, for BasketBallDrill with QP = 22 for 10 frames;

Fig. 8 shows BD-rate Vs Decoder complexity for different combinations of A1 , A2, A3;

Fig. 9 shows average percentage of area in a frame predicted by TM mode for different sequences;

Fig. 10 shows a block diagram of an encoder according to an embodiment of the present application using a search area subdivided into regions and signaling of a selected region to decoder side;

Fig. 1 1 shows a block diagram of a decoder according to an embodiment of the present application fitting to the encoder of Fig. 10;

Fig. 12 shows a schematic diagram illustrating a search for a set of one or more patches as it might be performed at encoder and decoder according to an embodiment;

Fig. 13 shows a block diagram of an encoder according to an embodiment of the present application using a search area the size of which is set according to side information in the data stream;

Fig. 14 shows a block diagram of a decoder according to an embodiment of the present application fitting to the encoder of Fig. 13;

Fig. 15 shows a schematic diagram illustrating a possibility to transfer above intra picture concepts to inter picture prediction; and

Fig. 16 shows a schematic diagram illustrating another possibility to transfer above intra picture concepts to inter picture prediction using a inter picture vector.

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.264 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, 2 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 10 to be predicted. As shown in Fig. 1 , in the reconstructed frame 12 , (N+2)*2 pixels above and 2*N pixels left of the block 10 are taken as the template 14. Rather than searching the entire frame 12 for the best match, one searches inside a window 16. Based on the frame size of the video sequence, the window size is decided. This window 16 is further divided into five regions 18 (Figs.2 and 3) illustratively with respect to one region 18, namely region no. 4, the three best template matches 20 from each region 18 are found by minimizing SSD. The average 22 of the respective TM blocks 24 becomes the prediction 26 of the current block 10. Advantage of the rate-distortion optimization algorithm of the HEVC encoder according to (1 ) might be taken to decide which region 18 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 35 other intra modes.

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

Fig. 4 shows a grayscale histogram of the number of TM blocks with respect to the current block inside a 128*128 window for BasketBallDrill of QP = 22. In order to reduce the complexity of the search algorithm the position of TM blocks 20 with respect to the current block 10 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. 4. This clearly justifies the use of a window 16 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 = 8, 16, 24, 32, 64, 128 were considered for this. The general tendency from the research result is that the bigger the window 16, the better the performance as shown in Fig.5. 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.6. 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 Figs. 1 to 3, 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.7. Fig. 7 shows a histogram of the number of second best TM blocks (log) with respect to the first block, for BasketBallDrill with QP = 22 for 10 frames. This observation guided to the division of search window 16 into different regions 18. Based on the experimental results, an adaptive search window 16 has been assessed where its size is varied depending on the frame size. The window size is M*M where M=n*3 (see Fig.2) and n is calculated as, if N ≥ 16, n = 2 A else:

A if 0 < framewidth < 832,

2 x A if 832 < framewidth < 1280.

n where A = 4

3 x A if 1280 < frame-width < 2560,

4. x A otherwise. (2)

It should be noted here that the proposed adaptive search window 16 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 Regioni to be A1 , for Region2 and 3 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 = 4 as the lower bound and A = 8 as the upper bound. The search window is adapted according to the formula (2). Our experimental results indicate that further coding efficiency can be achieved by unequal values of A as shown in Fig. 8.

The mode discussed above can achieve an average BD-rate gain of -1 .15% for classes A to E with 133% decoder complexity (Table.1 ).
Claims

Apparatus for picture decoding, configured to

select (52), out of a search area (56) of a picture (12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively decode (54) the predetermined picture block (10) from a data stream (36) based on the set (40) of one or more patches,

wherein the apparatus is configured to select the search area (56) out of a plurality of subareas (18) into which an overall search area (16) associated with the predetermined picture block (10) is sub-divided, based on a signalization (46) in the data stream (36).

Apparatus according to claim 1 , wherein the template area (14) and the predetermined picture block (10) are within the picture (12) and the overall search area (16) spatially neighbors the predetermined picture block (10).

Apparatus according to claim 1 , wherein the template area (14) and the predetermined picture block (10) are within a further picture (12') and the overall search area (16) spatially neighbors and/or overlays a block (10') of the picture (12) co-located to the predetermined picture block (10).

Apparatus according to claim 1 , wherein the template area (14) and the predetermined picture block (10) are within a further picture (12') and the overall search area (16) is displaced from a position (100) within the picture (12) collocated to the predetermined picture block (10) by a vector (102), wherein the apparatus is configured to derive the vector (102) from the data stream (36).

Apparatus according to claim 3 or 4, wherein the picture (12) and the further picture (12') are video pictures of a video or pictures of different views.

Apparatus according to any of claims 1 to 5, configured to perform the selection using a predetermined matching criterion such that the set (40) of one or more

patches match best, according to the predetermined matching criterion, the template area (14) among a set (70) of patches within the search area (56).

Apparatus according to claim 6, the predetermined matching criterion measures a difference to the template area (14).

Apparatus according to any of claims 1 to 7, wherein a count of the one or more patches of the set (40) of one or more patches is more than one.

Apparatus according to any of claims 1 to 8, configured to perform the selection (52) by comparing a template counterpart area (72) of each of a set (70) of patches of the search area (56) to the template area (14) and to perform the predictive decoding based on a portion (74) of the set (40) of one or more patches being located relative to the template counter-part area (72) like the template area (14) is located relative to the predetermined picture block (10).

Apparatus according to any of claims 1 to 9, configured to perform the predictive decoding (54) based on an average, such as a normal average, a weighted average, or a combination of both, of the set (40) of one or more patches, or based on an average of a subset out of the set (40) of one or more patches with the subset excluding patches from the set (40) of one or more patches whose match with the template area (14) is more than a predetermined thereshold worser than that for a best matching patch in the set (40) of the one or more patches.

Apparatus according to any of claims 1 to 10, wherein the overall search area (16) is subdivided into the plurality of subareas (18) such that a first subset of the plurality of subareas (18) are horizontally longitudinal areas neighboring each other vertically, and a second subset of the plurality of subareas (18) are vertically longitudinal areas neighboring each other horizontally.

Apparatus according to claim 1 1 , wherein the apparatus uses a horizontal raster scan coding order (38) running from picture top to picture bottom and the overall search area (16) is subdivided into the plurality of subareas (18) such that the horizontally longitudinal areas and the vertically longitudinal areas extend away from each other from an upper end of the vertically longitudinal areas and a left-hand end of the horizontally longitudinal areas, respectively.

Apparatus according to any of claims 1 to 10, configured to use as the overall search area (16) a window spatially positioned relative to the predetermined picture block (10), and having a size independent from which of possible picture positions the predetermined picture block (10) is located at.

Apparatus according to any of claims 1 to 13, configured to select the search area (56) out of the plurality of subareas (18) into which the overall search area (16) associated with the predetermined picture block (10) is sub-divided, based on the signalization (46) in the data stream (36) by deriving an index from the signalization (46) and applying the index to a one-dimensional list of the plurality of subareas (18).

Apparatus according to any of claims 1 to 14, configured to set a size of the overall search area (16) and/or the subareas (18) depending on side information (90) in the data stream (36).

Apparatus according to claim 15, wherein the side information (90) comprises one or more of the group consisting of

a picture size parameter indicating a picture size (W);

a tile-subdivision information indicating a number independently coded picture tiles; and

a picture content class identifier.

Apparatus according to claim 16, the side information (90) is valid for a picture sequence of a video which the predetermined picture block (10) is part of.

Apparatus according to any of claims 15 to 17, configured to set the size of the overall search area (16) and/or the subareas (18) depending on the side information (90) in the data stream (36) if the predetermined picture block (10) is smaller than a predetermined block size, and independent from the side information (90) in the data stream (36) if the predetermined picture block (10) is greater than the predetermined block size.

19. Apparatus according to any of claims 15 to 17, configured to set the size of the overall search area (16) and/or the subareas (18) depending on side information (90) in the data stream (36) such that the size of the overall search area (16) and/or the subareas (18) is larger the larger the picture size of a picture is within which the predetermined picture block resides.

20. Method for picture decoding, comprising

selecting (52), out of a search area (56) of a picture (12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively decoding (54) the predetermined picture block (10) from a data stream (36) based on the set (40) of one or more patches, and

selecting the search area (56) out of a plurality of subareas (18) into which an overall search area (16) associated with the predetermined picture block (10) is sub-divided, based on a signalization (46) in the data stream (36).

21 . Apparatus for picture coding, configured to

select (32), out of a search area (16) of a picture (12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively encode (34) the predetermined picture block (10) into a data stream (36) based on the set (40) of one or more patches,

wherein the search area ( 16) is spatially subdivided into a plurality of subareas (18) and the apparatus is configured to signal within the data stream (36) which subarea the set (40) of one or more patches are located in.

22. Apparatus according to claim 21 , wherein the template area (14) and predetermined picture block (10) are within the picture (12) and the search spatially neighbors the predetermined picture block (10).

23. Apparatus according to claim 21 , wherein the template area (14) and the predetermined picture block (10) are within a further picture (12') and the search area (16) spatially neighbors and/or overlays a block (10') of the picture (12) co- located to the predetermined picture block (10).

24. Apparatus according to claim 21 , wherein the template area (14) and the predetermined picture block (10) are within a further picture (12') and the search area (16) is displaced from a position (100) within the picture (12) collocated to the predetermined picture block (10) by a vector (102), wherein the apparatus is configured to determine the vector (102) and signal the vector (102) in the data stream (36).

25. Apparatus according to claim 23 or 24, wherein the picture (12) and the further picture (12') are video pictures of a video or pictures of different views.

26. Apparatus according to any of claims 21 to 25, configured to perform the selection (32) using a predetermined matching criterion by determining (64), for each subarea (18), a candidate set (78) of one or more patches which match best, according to the predetermined matching criterion, the template area (14) among a set (70) of patches within the respective subarea (18), and selecting (80) the candidate set (78) determined for one of the subareas (18) as the set (40) of one or more patches based on which the predetermined picture block (10) is to be predictively encoded.

27 Apparatus according to claim 26, the predetermined matching criterion measures a difference to the template area (14).

28. Apparatus according to any of claims 21 to 7, wherein a cardinality of the set (40) of one or more patches is more than one.

29, Apparatus according to any of claims 21 to 28, configured to perform the selection (32) by comparing a template counterpart area (72) of each of a set (70) of

patches of the search area (16) to the template area (14) and to perform the predictive encoding (34) based on a portion (74) of the (40) set of one or more patches being located relative to the template counter-part area (72) like the template area (14) is located relative to the predetermined picture block (10).

Apparatus according to any of claims 21 to 29, configured to perform the predictive encoding (34) based on an average of the set (40) of one or more patches, or based on an average of a subset out of the set (40) of one or more patches with the subset excluding patches from the set (40) of one or more patches whose match with the template area (14) is more than a predetermined thereshold worser than that for a best matching patch in the set (40) of the one or more patches.

Apparatus according to any of claims 21 to 30, wherein the search area (16) is subdivided into the plurality of subareas (18) such that a first subset of the plurality of subareas are horizontally longitudinal areas neighboring each other vertically, and a second subset of the plurality of subareas (18) are vertically longitudinal areas neighboring each other horizontally.

Apparatus according to claim 31 , wherein the apparatus uses a horizontal raster scan coding order (38) running from picture top to picture bottom and the search area (16) is subdivided into the plurality of subareas (18) such that the horizontally longitudinal areas and the vertically longitudinal areas extend away from each other from an upper end of the vertically longitudinal areas and a left-hand end of the horizontally longitudinal areas, respectively.

Apparatus according to any of claims 21 to 30, configured to use as the search area (16) a window spatially positioned relative to the predetermined picture block (10), and having a size independent from which of possible picture positions the predetermined picture block (10) is located at.

Apparatus according to any of claims 21 to 33, configured to signal the subarea (18) which the set (40) of one or more patches are located in based on the signalization (46) in the data stream (36) by indicating an index in the signalization (46) which points into a one-dimensional list of the plurality of subareas (18).

Apparatus according to any of claims 21 to 33, configured to set a size (M) of the search area (16) and/or a count of the plurality of subareas (18) depending on side information (90) in the data stream.

Apparatus according to claim 35, wherein the side information (90) comprises one or more of the group consisting of

a picture size parameter indicating a picture size;

a tile-subdivision information indicating a number independently coded picture tiles; and

a picture content class identifier.

Apparatus according to claim 36, wherein the side information (90) is valid for a picture sequence of a video which the predetermined picture block (10) is part of.

Apparatus according to any of claims 35 to 37, configured to set the size of the search area (16) and/or the subareas (18) depending on the side information (90) in the data stream (36) if the predetermined picture block (10) is smaller than a predetermined block size, and independent from the side information (90) in the data stream (36) if the predetermined picture block (10) is greater than the predetermined block size.

Apparatus according to any of claims 35 to 37, configured to set the size of the search area (16) and/or the subareas (18) depending on the side information (90) in the data stream (36) such that the size of the overall search area (16) and/or the subareas (18) is larger the larger the picture size of a picture is within which the predetermined picture block resides.

Method for picture coding, comprising

selecting (32), out of a search area (16) of a picture ( 12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively encoding (34) the predetermined picture block (10) into a data stream (36) based on the set (40) of one or more patches,

wherein the search area (16) is spatially subdivided into a plurality of subareas (18) and the method comprises signalling within the data stream (36) which subarea the set (40) of one or more patches are located in.

Apparatus for picture decoding, configured to

select (52), out of a search area (56) of a picture (12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively decode (54) the predetermined picture block ( 0) from a data stream (36) based on the set (40) of one or more patches,

wherein the apparatus is configured to set a size of the search area (56) depending on side information (90) in the data stream.

Apparatus according to claim 41 , wherein the template area and the predetermined picture block are within the picture and the search area spatially neighbors the predetermined picture block.

Apparatus according to claim 41 , wherein the template area and the predetermined picture block are within a further picture and the search area spatially neighbors or overlays a block of the picture co-located to the predetermined picture block.

Apparatus according to claim 41 , wherein the template area and the predetermined picture block are within a further picture and the search area is displaced from a position within the picture collocated to the predetermined picture block by a vector, wherein the apparatus is configured to determine the vector and signal the vector in the data stream.

Apparatus according to claim 43 or 44, wherein the picture and the further picture are video pictures of a video or pictures of different views.

Apparatus according to any of claims 41 to 45, configured to perform the selection among a set of patches within the search area using a predetermined matching criterion.

Apparatus according to claim 46, the predetermined matching criterion measures a difference to the template area.

Apparatus according to any of claims 41 to 47, wherein a count of the one or more patches is more than one.

Apparatus according to any of claims 41 to 48, configured to perform the selection by comparing a template counterpart area of each of a set of patches of the search area to the template area and to perform the predictive encoding based on a portion of the set of one or more patches being located relative to the template counter-part area like the template area is located relative to the predetermined picture block.

Apparatus according to any of claims 41 to 49, configured to perform the predictive encoding based on an average of the one or more patches, or based on an average of a subset out of the set (40) of one or more patches with the subset excluding patches from the set (40) of one or more patches whose match with the template area (14) is more than a predetermined thereshold worser than that for a best matching patch in the set (40) of the one or more patches.

Apparatus according to any of claims 41 to 50, wherein the side information comprises one or more of the group consisting of

picture size parameter indicating a picture size;

tile-subdivision information indicating a number independently coded picture tiles; and

picture content class identifier

Apparatus according to any of claims 41 to 51 , the side information (90) is valid for a picture sequence of a video which the predetermined picture block (10) is part of.

Apparatus according to any of claims 41 to 52, configured to set the size of the search area (56) depending on the side information (90) in the data stream (36) if the predetermined picture block (10) is smaller than a predetermined block size, and independent from tho side information (90) in the data stream (36) if the predetermined picture block (10) is greater than the predetermined block size.

Apparatus according to any of claims 41 to 53, configured to set the size of the search area (56) depending on side information (90) in the data stream (36) such that the size of the search area (56) is larger the larger the picture size of a picture is within which the predetermined picture block resides.

Method for picture decoding, comprising

selecting (52), out of a search area (56) of a picture (12), a set (40) of one or more patches which match a template area (14) adjacent to a predetermined picture block (10); and

predictively decoding (54) the predetermined picture block (10) from a data stream (36) based on the set (40) of one or more patches, and

setting a size of the search area (56) depending on side information (90) in the data stream.

Apparatus for picture coding, configured to

seiect, out of a search area of a picture, a set of one or more patches which match a template area adjacent to a predetermined picture block; and

predictively encode the predetermined picture block into a data stream based on the set of one or more patches,

wherein the apparatus is configured to set a size of the search area depending on side information in the data stream.

57. Apparatus according to claim 56, wherein the template area and the predetermined picture block are within the picture and the search area spatially neighbors the predetermined picture block.

58. Apparatus according to claim 56, wherein the template area and the predetermined picture block are within a further picture and the search area spatially neighbors a block of the picture co-located to the predetermined picture block.

59. Apparatus according to claim 56, wherein the template area and the predetermined picture block are within a further picture and the search area is displaced from a position within the picture collocated to the predetermined picture block by a vector, wherein the apparatus is configured to determine the vector and signal the vector in the data stream.

60. Apparatus according to claim 58 or 59, wherein the picture and the further picture are video pictures of a video or pictures of different views.

61 . Apparatus according to any of claims 56 to 60, configured to perform the selection among a set of patches within the search area using a predetermined matching criterion.

62. Apparatus according to claim 61 , the predetermined matching criterion measures a difference to the template area.

63. Apparatus according to any of claims 56 to 62, wherein a count of the one or more patches is more than one.

64. Apparatus according to any of claims 56 to 63, configured to perform the selection by comparing a template counterpart area of each of a set of patches of the search area to the template area and to perform the predictive encoding based on a portion of the one or more patches being located relative to the template counterpart area like the template area is located relative to the predetermined picture block.

65, Apparatus according to any of claims 56 to 64, configured to perform the predictive encoding based on an average of the one or more patches, or based on an average of a subset out of the set (40) of one or more patches with the subset excluding patches from the set (40) of one or more patches whose match with the template area (14) is more than a predetermined thereshold worser than that for a best matching patch in the set (40) of the one or more patches.

66. Apparatus according to any of claims 56 to 65, wherein 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 independently coded picture tiles; and

a picture content class identifier.

Apparatus according to any of claims 56 to 66, wherein the side information (90) is valid for a picture sequence of a video which the predetermined picture block (10) is part of.

Apparatus according to any of claims 56 to 67, configured to set the size of the search area (16) depending on the side information (90) in the data stream (36) if the predetermined picture block (10) is smaller than a predetermined block size, and independent from the side information (90) in the data stream (36) if the predetermined picture block (10) is greater than the predetermined block size.

Apparatus according to any of claims 56 to 68, configured to set the size of the search area (16) and depending on the side information (90) in the data stream (36) such that the size of the overall search area (16) is larger the larger the picture size of a picture is within which the predetermined picture block resides.

Method for picture coding, comprising

selecting, out of a search area of a picture, a set of one or more patches which match a template area adjacent to a predetermined picture block; and

predictively encoding the predetermined picture block into a data stream based on the set of one or more patches, and

setting a size of the search area depending on side information in the data stream.

71 . Computer program having a program code for performing, when running on a computer, a method according to one of claims 20, 40, 55 or 70.

72. Data stream generated by a method according to one of claims 40 or 70.