Low-complexity intra prediction for video coding

Technical field The present invention relates to video coding and in particular intra-frame prediction in which a sample block is predicted using previously coded and reproduced pixels from the same video frame.

2. General information [0002] Digital video requires a large amount of data to present each frame of a digital video sequence (e.g. a series of frames) in an uncompressed manner. In most applications, it is not feasible to send uncompressed digital video through a computer network due to bandwidth restrictions. In addition, uncompressed digital video requires large storage space. Digital video is usually encoded in some way to reduce storage space requirements and reduce bandwidth requirements.

[0003] One of the digital video coding techniques is inter-frame prediction, or inter prediction. Interframe prediction uses temporal redundancy among different frames. Temporarily adjacent video frames usually contain pixel blocks that are essentially the same. During the coding process, the motion vector determines the relationship of motion between a block of pixels in one frame and a block of similar pixels in another frame. Accordingly, the system is not required to code the pixel block twice, but rather encodes the pixel block once and provides a motion vector for another pixel block.

[0004] Another digital video coding technique is intra-frame prediction. Intra-frame prediction encodes a frame or part of it without reference to pixels in other frames. Intra-frame prediction uses spatial redundancy among pixel blocks within a frame. Because spatially adjacent pixel blocks generally have similar attributes, the efficiency of the coding process is increased by referring to the spatial mutual correlation between adjacent blocks. This correlation occurs between adjacent blocks. This correlation can be used by target block prediction based on the prediction modes used in adjacent blocks.

Summary of the invention [0005] The present invention provides a video coding method according to claim 1, a video decoding method according to claim 2, a video encoder according to claim 3 and a video decoder according to claim 4.

[0008] In another embodiment, when acquiring at least some of the vertical border pixels, InvAngle is calculated from

N x size angle _, where N is an integer being the power of 2. Then, at least some of the pixels from the vertical border pixels are obtained, using the vertical pixel identifier, which is expressed as [col * InvAngle >> log2N]. The acquired pixels are added to the horizontal pixels at the position specified by the horizontal pixel [col] identifier.

[0007] In another embodiment, InvAngle is obtained from a lookup table that lists InvAngle values ​​in relation to the angle value.

[0008] In another embodiment, the pixel is identified from among the vertical border pixels using the [row] identifier of the vertical pixel, where row is a counter incremented by 1 from 0 to size. The acquired pixel is added to the horizontal border pixels at the position identified by the [int + 1] horizontal pixel identifier, where int is an integer representing the position of the pixel intersecting with the prediction direction.

[0009] The present invention also provides an encoder and decoder that use an intra-frame prediction operation in which at least some of either the horizontal border pixel system or the vertical border pixel system are obtained. Then, the acquired pixels are added to other border pixels to enlarge the pixel arrangement. Intra-frame prediction is performed only based on the expanded border pixel system.

BRIEF DESCRIPTION OF THE FIGURES [0010]

FIG. 1 is a block diagram showing an exemplary hardware architecture on which the present invention may be implemented.

FIG. 2 is a block diagram showing generally a video coding apparatus to which the present invention may be applied.

FIG. 3 is a block diagram showing generally a video decoding device to which the present invention may be applied.

FIG. 4 is a block diagram showing the functional modules of the coding device according to an embodiment of the present invention.

FIG. 5 is a flowchart showing the intra-intra-prediction process carried out by the intra-intra-prediction module according to an embodiment according to the present invention.

FIG. 6 is a block diagram showing the functional modules of a decoding device according to an embodiment of the present invention.

FIG. 7 is a diagram showing directions of prediction illustrating prediction modes

4x4 supported by H.264 / AVC.

FIG. 8 is a diagram showing the prediction directions proposed in document No. JCT-VC A119.

FIG. 9 is a flowchart showing the process, proposed in JCT-VC A119, of generating a block that was predicted according to one of the prediction directions shown in FIG. 7.

FIG. 10 is a flowchart showing a low-complex intra-prediction process carried out according to an embodiment of the present invention.

FIG. 11A is a schematic view showing the prediction block and the horizontal and vertical border pixel systems.

FIG. 11B is a schematic view showing the horizontal border pixel system plus vertical border pixels.

FIG. 12 is a flowchart showing a process of increasing the horizontal border pixel system according to an embodiment of the present invention.

FIG. 13 is a flowchart of another embodiment of enlarging a horizontal border pixel system.

FIG. 14 is a flowchart showing a low-complex intra-prediction process carried out according to another embodiment of the present invention.

DETAILED DESCRIPTION OF THE DRAWING AND PRESENT IMPLEMENTED EMBODIMENTS [0011] FIG. 1 shows an example computer hardware architecture 100 on which the present invention may be implemented. Note that the hardware architecture shown in FIG. 1 may be common to both video coding apparatus and video decoding apparatus that use embodiments of the present invention. The computer 100 includes a processor 101, a memory 102, a storage device 105, and one or more input and / or output (I / O) devices 106 (or peripherals) that are connected in a manner enabling their communication via a local interface 107. Local the interface 105 may be, for example but not limited to, one or more buses or other wired or wireless connections as are known in the art.

[0012] Processor 101 is a hardware device for running software, in particular that stored in memory 102. The processor 101 may be any processor specialized or commercially available, a main processing unit (CPU) or an auxiliary processing unit among the numerous processors associated with the computer 100, a microprocessor based on semiconductor technology (in the form of a chip or a set of system structures), or generally any device for running software instructions.

[0013] Memory 102 consists of a computer-readable medium that may include any memory or combination of volatile memory elements (e.g., random access memory (RAM such as DRAM, SRAM, SDRAM, and the like)) and non-volatile memory elements (for example, ROM, hard disk, tape, CDROM, and the like). Furthermore, memory 102 may use electronic, magnetic, optical and other types of storage media. A computer-readable medium may be any means capable of storing, connecting, broadcasting or transmitting a program for use by, or in conjunction with, an instruction system, component or device. It should be noted that the memory 102 may have a distributed architecture in which the various components are located spaced apart, but which can be accessed by the processor 101.

[0014] The software 103 in the memory 102 may include one or more separate programs, each containing an ordered set of executable instructions for performing the logic functions of the computer 100, as described below. In the example of FIG. 1, the software 103 in memory 102 determines the video coding or video decoding functionality of the computer 100 according to the present invention. In addition, although it is not required, it is possible for memory 102 to contain the operating system (O / S) 104. The operating system 104 primarily controls the execution of computer programs and provides queuing, input control, file and data management, memory management and communication control and related services.

[0015] The storage device 105 of the computer 100 may be one of many types of storage devices, including stationary storage devices or portable storage devices. For example, the storage device 105 may be a magnetic tape, disk, flash memory, volatile memory, or other storage device. In addition, the storage device 105 may be a secure digital memory card, or any other type of removable storage device 105.

[0016] I / O devices 106 may include input devices, for example, but not limited to, a touch screen, keyboard, mouse, scanner, microphone, or other input device. Furthermore, I / O devices 106 may also include output devices, for example, but not limiting the display, or other output devices. The I / O devices 106 may further include devices that connect via both inputs and outputs, for example, but not limited to, a modulator / demodulator (modem: for accessing another device, system or network), a radio frequency transceiver (RF), wireless or other, telephone interface, bridge, router, or other device that plays the role of both input and output.

[0017] As is well known to those skilled in the art, video compression is obtained by removing repetitive information in a video sequence. There are many different video coding standards, examples of which include MPEG-1, MPEG-2, MPEG-4, H.261, H.263, and H.264 / AVC. It should be noted that the present invention is not limited to applications for a particular video coding standard. However, the following description of the present invention is provided using an example of the H.264 / AVC standard. H.264 / AVC is the latest video coding standard and achieves a significant performance improvement over existing coding standards such as MPEG-1, MPEG-2, H.261 and H.263.

[0018] In H.264 / AVC, each frame or video can be separated into several slices. These slices are then divided into 16 * 16 pixel blocks (sizes) called macroblocks, which can then be further divided into 8 * 16, 16 * 8, 8 * 8, 4 * 8, 8 * 4 blocks up to 4 * 4 pixels. H.264 / AVC supports five types of slices. In slices I all macroblocks are encoded using intra-frame prediction. In P slices, macroblocks can be encoded using intra-or inter-frame prediction. P slices allow the use of only one motion compensated prediction (MCP) signal per macroblock. In B slices, macroblocks can be encoded using intra-or inter-frame prediction. Two MCP signals can be used for one prediction. SP slices allow P slices to be effectively switched between different video streams. The SI slice is the exact match for the SP slice for random access, or restoring to an error state when using only intra-frame prediction.

[0019] In FIG. 2 shows the general form of the video encoding apparatus in which the present invention may be applied. The blocks shown in the figure show the functional modules implemented by the processor 101 which executes the program 103 in the memory 102. The image of the video frame 200 is inserted into the video encoding device 201. The video coding device considers the 200 image in 200A macroblock units. Each macroblock contains several pixels of the image 200. A transformation to transformation coefficients is performed on each macroblock, followed by quantization to transformation coefficient levels. In addition, intra-frame or inter-frame prediction is used to not perform coding steps directly on image data, but on their differences to pixel values ​​that have been predicted, thereby obtaining small values ​​that are easier to compress.

[0020] For each slice, the coding apparatus 201 generates several syntax elements that form the encoded version of these macroblocks of the respective slice. All other data components in the syntax elements that are associated with the transformation coefficient coding, such as transformation coefficient levels or materiality map indicating the transform coefficient levels omitted, are called residual syntax elements. In addition to these other data syntax elements, the syntax elements generated by the video encoding device 201 contain control information syntax elements containing control information about how each macro block is to be encoded and how it should be decoded, respectively. In other words, the syntax elements can be divided into two categories. The first category of control information syntax elements contains elements that relate, for example, to the type of macroblock, sub-macroblock type, and information about prediction modes of both spatial and temporal type, as well as control information based on a slice or based on macroblock. In the second category, all elements of the remaining data, such as the significance map indicating the locations of all significant coefficients inside the block of quantized transformation coefficients and those values ​​of the transformation coefficients, which are indicated in units of level corresponding to the quantization stages, are combined and become elements of the syntax of the remaining data.

[0021] The coding apparatus 201 includes an entropy encoder that codes the syntax elements and generates arithmetic code words for each slice. When generating arithmetic code words for a slice, the entropy coder uses statistical relationships between the values ​​of given syntax elements in the bit stream of the video signal. The video encoding device 201 outputs the encoded video signal for the image slice 200 to the video decoding device 301 shown in FIG. 3.

[0022] In FIG. 3 is a pictorial view of a video decoding device in which the present invention may be applied. The blocks shown in the figure show similar function modules implemented by the processor 101 executing the program 103 in the memory 102. The video decoding device 301 receives the encoded signal and first entropy decodes the signal back to the syntax elements. The 301 video decoding device uses syntax elements to play back, macroblock by macroblock followed by slice by slice, 300A image pixel patterns in 300 image.

[0023] In FIG. 4 shows the functional modules of the video coding device 201. These function modules are implemented by the processor 101 executing the program 103 in memory 102. The input video image is a frame or field of a plain (uncompressed) video image determined by sample points representing the components of primary colors, such as chrominance ("chroma") and luminance ("luma" ") (Other components are possible, for example hue, saturation and value). The video input image is divided into 400 macroblocks, each representing a rectangular image area consisting of 16 * 16 pixels of the luma component for the image color. The input image is also divided into macroblocks, each representing 8 * 8 pixels of each of the two chroma components for the color of the image. In the general operation of the coding device, the input macroblocks can be temporarily or spatially predicted using in-frame or inter-frame prediction. However, it has been assumed for the sake of discussion that the 400 macroblocks are all type I macroblocks and are subject only to intra-frame prediction.

[0024] Intra-frame prediction is performed in intra-frame prediction module 401, the operation of which will be discussed in detail below. Intra-frame prediction module 401 generates a prediction block 402 from the horizontal and vertical border pixels of adjacent blocks that have previously been encoded, reproduced and stored in frame memory 403. The remainder 404 of the prediction block 402, which is the difference between the target block 400 and the prediction block 402, is transformed, scaled and quantized by the transformation / quantization module 405, using methods and techniques known to those skilled in the art of video coding. The quantized transform coefficients 406 are then entropy coded in entropy coding module 407 and transmitted (along with other information regarding this intra-frame prediction) as encoded video signal 408.

[0025] The video encoding device 201 includes decoding functionality for performing intra-frame prediction on target blocks. This decoding functionality includes a reverse transformation / quantization module 409 that performs reverse quantization and inverse conversion of quantized transformation coefficients 406 to obtain a decoded residual prediction 410 that is added to prediction block 402. The sum of the decoded residue 410 and prediction block 402 is a reconstructed block 411 that is written to frame memory 403, and will be read from it and used by intra-frame prediction module 401 to create a prediction block 402 to decode another target block 400.

[0026] In FIG. 5 is a flowchart of processes performed by intra-frame prediction module 401. According to the H.264 / AVC Standard, intra-frame prediction uses the prediction of each pixel of the target block 400 in multiple prediction modes, using border pixel interpolation ("reference pixels") of neighboring blocks previously coded and restored. These prediction modes are distinguished by positive integers 0, 1, 2 ... each of which is associated with a different instruction or algorithm for predicting specific pixels in the target block 400. Intra-frame prediction module 401 performs intra-frame prediction with appropriate prediction modes and creates different prediction blocks. With the full search algorithm full search) ("FS"), each of the prediction blocks created is compared to the target block 400 to find the optimal prediction algorithm that minimizes the prediction remainder 404, or creates the smallest prediction remainder 404 among prediction modes. The recognition of the optimal prediction mode is compressed and sent to a decoding device 301 along with other control information syntax elements.

[0027] Each prediction mode can be described by the general direction of the prediction, as described in words (e.g. horizontal up, vertical diagonally down to the left). The direction of the prediction can be described graphically by an angular direction, which is expressed by an arrow diagram such as shown in FIG. 7. In this type of diagram, each arrow can be considered as showing the direction of the prediction or the prediction mode. The angle corresponding to the prediction mode is generally related to the direction from the weighted average position of the reference pixels used to predict the target pixel to the position of the target pixel. Note that the prediction modes include a DC prediction mode that is not associated with any prediction direction and therefore cannot be described graphically in the diagram as opposed to other prediction modes. In DC prediction mode, the prediction block 402 is created in such a way that each pixel in the prediction block 402 is set uniformly relative to the average value of the reference pixels.

[0028] Returning to FIG 5, the prediction mode is started in Step 501. Then, in Step 502, it is determined whether the prediction mode indicates DC prediction. If this is the case, proceed to Step 503, in which the DC prediction block 402 is created with the average value of these reference pixels in Step 503. Unless the prediction mode indicates otherwise, the prediction block 402 is created according to the instruction or algorithm associated with the prediction mode in Step 504, which process will be discussed in detail below. After Step 503 or 504, you go to Step 505, in which it is determined whether prediction blocks are created for all prediction modes. If intra-frame prediction works with all prediction modes, it goes to Step 506. Otherwise, the prediction mode is increased in Step 507 and the operation returns to Step 502. In Step 506, each of the prediction blocks created is compared to the target block 400 to determine the optimal prediction mode that minimizes the remainder of the 404 prediction.

[0029] In FIG. 6 shows the function modules of the 301 video decoding device. These function modules are implemented by the processor 101 executing the program 103 in the memory 102. The encoded video signal from the video encoding device 201 is first received by the entropy decoder 600 and entropy decoded back to quantized transform coefficients 601. The quantized transformation coefficients 601 are inverse quantized and transformed by the inverse quantization / transformation module 602 to form the prediction residue 603. Intra-frame prediction module 604 is notified of the prediction mode selected by the encoding device 201. According to the prediction mode selected, intra-frame prediction module 604 performs an intra-frame prediction process similar to that performed in Steps 502, 503 and 504 of FIG. 5 to create a prediction block 605, using border pixels of adjacent blocks previously restored and stored in the frame memory 606. Prediction block 605 is added to prediction residual 603 to play a decoded video signal block 607. The replayed block 607 is stored in frame memory 606 for use in the prediction of the next block.

[0030] In the following, a detailed description of the process of Step 504 by the intra-frame prediction modules 401 and 604 to form the prediction block will be provided in one of the prediction modes, except for the DC prediction mode.

H.264 / AVC supports Intra 4 4 intra-frame prediction, Intra 8 8 prediction and Intra_16 * 16 prediction. Intra 4 4 prediction is widely used where there is a lot of important detail in the image. Prediction Intra 4 4 separately predicts sixteen luma 4 * 4 blocks within a macroblock. Intra 4 4 prediction is performed using nine prediction modes, including one DC prediction mode. Spatial prediction directions along with the Intra_4 * 4 prediction are implemented as shown in FIG. 7. Prediction Intra_8 * 8 is made with nine prediction modes, including one DC prediction mode. Intra_16 * 16 prediction is performed using four prediction modes, including one DC prediction mode. [0031] Recent studies show that an increase in the number of prediction directions, or an increase in the number of prediction modes, generally improves the efficiency of video compression. See, for example, document No. JCT-VC A119 ("Angular Intra Prediction") and JCT-VC A124 ("Arbitrary Direction Intra") forwarded to the Joint Collaborative Team on Video Coding (JCT-VC), each of which has been included here by reference. The increase in the number of prediction directions leads to an increase in the number of angular divisions of the available prediction directions, and thus to an increase in the number of candidates for the prediction block. The increased number of candidates for the prediction block simply increases the chances of getting a prediction block that is almost the same as the target block to be encoded. In FIG. 8 is a diagram showing the directions of prediction proposed in document No. JCT-VC A119. In FIG. 8, the reference pixels consist of seventeen (17) horizontal pixels and seventeen (17) vertical pixels, where the top-left pixel is common to both the horizontal and vertical border. Therefore, 33 different prediction directions are available to create the prediction pixels in the 8 * 8 block. JCT-VC A124 proposes any targeted intra-frame prediction in which the number of prediction directions is adjusted according to the size of the block to be predicted.

[0032] In FIG. 9 is a flowchart showing the process, proposed in JCT-VC A119, of creating a block along one of the prediction directions shown in FIG. 8. In the following description of this process, some algorithms are simplified to facilitate explanation. In addition, the described process is limited to intra-frame prediction along a direction that is substantially vertical. Intra-frame prediction along a direction that is substantially horizontal can be implemented symmetrically relative to the process of FIG. 9 as shown in the program provided by JCT-VC A119. Although FIG. 8 shows the block 8 * 8 to be predicted, the process shown in FIG. 9 can be extended to various amounts of pixels in various configurations. For example, the block to be predicted may contain 4 * 4 pixels. The prediction block can also contain 8 * 8 pixels, 16 * 16 pixels, or larger pixel systems. Other pixel configurations, including both square and rectangular systems, can also create a prediction block.

[0033] In Step 900 of FIG. 9, reference pixels at the horizontal and vertical borders that lie immediately above and to the left of the target block, respectively, are read from adjacent blocks that have been previously encoded, reproduced and stored in a frame memory, such as memory 403 shown in FIG. 4. Pixels from the horizontal border are saved in the memory space called "refH". Pixels from the vertical border are stored in a memory space called "refV". Returning to FIG. 8, reference pixels are recognized by their coordinates in the coordinate system starting from the top-left position in the 8 * 8 block. Thus, the horizontal border pixels have coordinates expressed by p [x, y] where x = 0, 1 ... 16 ay = 0. The vertical border pixels have coordinates expressed by p [x, y] where x = 0, y = 0 , -1, -2 ...- 16. [0034] It has been assumed that the horizontal border pixels recorded in the memory refH region are recognized by the logical address (x) where x = 0, 1 ... 16, and the horizontal border pixels recorded in the memory refV area are recognized analogically by the logical address ( y) where y = 0, -1, -2 ...- 16, where each pixel is recorded at the address having the number in the coordinate from which it is read. Thus, as the horizontal and vertical pixels are graphically represented in FIG. 8, the refH and refV memory areas can be considered to be linear and perpendicular to each other, and each has a length of 2 * size + 1, where "size" is a parameter representing the size of the target block. It is assumed that size has a value equal to an integer 2, such as 4, 8, 16 ... The low-pass filter as described in chapter 8.3.2.2.1 in H.264 / AVC can be optionally applied to pixels in refH and refV.

[0035] At Step 901, the counter called "row" is set to zero ("0"). The row counter has a value from 0 to size and indicates the location of the prediction pixel row in the prediction block. At Step 902, a parameter called "pos" is calculated as angle * (row + 1). angle is a parameter having a fractional number in a fixed entry. Therefore, the angle consists of an integer part and a fractional part, and the fractional part has a fixed number of binary numbers. angle represents one of the directions of prediction shown in FIG. 8. For example, "angle = -size" identifies the prediction direction that passes through the coordinates [x = 0, y = 0] in FIG. 8. an angle with a positive value identifies the direction of the prediction, which only intersects the horizontal boundary, while an angle with a negative value identifies the direction of the prediction, which intersects both the horizontal and the vertical boundary. angle changes within the range of prediction directions that you want to use. As proposed in JCT-VC A124, the number of prediction directions to be used can be determined according to the size of the block to be predicted. In the following description, it is assumed that the angle occupies a fractional number that varies within the range "-size" to "size". Note that the range limits for angle can be specified by other values. [0036] Like the angle, the pos parameter consists of an integer part and a fractional part, and its fractional part consists of a fixed number of binary digits which is equal to a base-2 logarithm of the range boundary for the angle, which can be expressed by log2_size as appropriate to the above assumption that the range range for angle is set to size. pos equates the intersection between the horizontal boundary and the prediction direction represented by angle. Returning to Step 902, the "pos >> log2_size" action specifies the integer in pos that is written in the "int" parameter, and the "pos & (size - 1)" action specifies the fractional wpos number that is written in the "frac ". The action ">>" invokes the arithmetic right-shift function of binary numbers. Operation "&" invokes the arithmetic function "and".

[0037] In Step 903, it is determined whether the angle is equal to or greater than zero ("0"). If the angle is equal to or greater than zero, it goes to Step 904. Otherwise, it follows Step 913. An angle equal to or greater than zero suggests that you can only rely on reference pixels located on the horizontal border, or saved in refH, to obtaining prediction pixels in the prediction block. On the other hand, an angle less than zero suggests that reference pixels located on the vertical border, or saved in refV, are necessary to obtain the prediction pixels in the prediction block.

[0038] In step 904 it is determined whether frac is not zero. If frac is not zero, it goes to Step 905. If frac is zero, then Step 906 occurs. Frac zero suggests that the prediction pixel in the prediction block can be copied directly from the reference pixel at the horizontal boundary. A non-zero frac suggests that the prediction direction intersects the horizontal boundary at a non-integer location, and more than one reference pixel must be interpolated to obtain the prediction pixels in the prediction block.

[0039] At 905, a counter called "col" is set to zero ("0"). The col counter is used to address the reference pixel in refH. At Step 907, two reference pixels identified by "int + col + 1" and "int + col + 2" are obtained from refH. These two reference pixels are weighted or interpolated at frac to obtain the reference pixel v. In particular, the reference pixel in refH identified by "int + col + 1" is multiplied by "size - frac" and saved in parameter a. The reference pixel in refH identified by "int + col + 2" is multiplied by "frac" and saved in parameter b. Parameters a and b are then added and divided by size, i.e. (size - frac) + frac. Division by size can be replaced by shifting to the right by log2_size. The obtained prediction pixel v is saved in an array of memory areas called "pred", which represents the prediction block for the target block at a specific prediction direction. Each memory area in pred is identified by the row and col parameters. Then col is increased by 1 at Step 908 and compared with size at Step 909. As long as col is smaller than size, Steps 907 and 908 are repeated. When col becomes equal to size, it goes to Step 920.

[0040] If it is determined that frac is zero in Step 904, the col counter is set to zero in Step 906. In Step 910, the prediction pixel v is copied directly from refH (int + col + 1) and then stored in the appropriate area memory in pred. col is then increased by 1 in Step 911 and compared to size in Step 912. As long as col is smaller than size, Steps 910 and 912 are repeated. When col becomes size, then Step 920 occurs.

[0041] Referring to Step 903, an angle less than zero requires reference pixels from refV to obtain the prediction pixels in the prediction block. The col counter is set to zero in Step 913. Then, in Step 914 it is determined whether "int + col + 1" is less than zero. "Int + col + 1" equal to or greater than zero suggests that you can still rely only on reference pixels stored in refH to get the prediction pixels in the prediction block, and then Step 915. The process carried out in Step 915 is similar to that in Step 907, and its description will not be repeated here. col is then increased by 1 in Step 916 and compared with the size in Step 917. As long as col is smaller than size, Steps 914, 915 and 916 are repeated. When col becomes equal in size, Step 920 follows.

[0042] If it is determined that "int + col + 1" is less than zero in Step 914, reference pixels stored in refV are needed to obtain the prediction pixels in the prediction block. At Step 918, the intersection position between the vertical border and the prediction direction is first determined. At step 918, the position is represented by pos2. Note that at Step 902, pos, i.e. the intersection between the horizontal boundary and the prediction direction, is determined by "angle x (row +

1) ". Given that angle expresses the ratio of horizontal and vertical differences, the "angle^-1 x (col + 1) "instead of" angle x (row + 1) "to determine the intersection between the vertical border and the prediction direction. As assumed above, the angle is in the range -size to size (-size <angle <size). Therefore, the ratio a between angle and size is determined by:

angle (-1 <α <1).

size then angle '\ is determined by:

<img file="PL2934009T3_D0001.tif" />

And if so, then pos2 is referred to in Step 918 as the size square multiplied by col + 1 and then divided by the absolute angle value as follows:

size² x (col +1) pos2 = [0043] Like pos, pos2 has a fractional number in the fixed entry, which consists of an integer part and a fractional part. The fractional part consists of the number of binary digits set by log2_size. The integer pos2 is written in the int2 parameter and the fraction pos2 is written in the frac2 parameter. At Step 919, the two reference pixels identified by "int2 + row + 1" and "int2 + row + 2" are obtained from refV. These two reference points are weighted averaged or interpolated with frac2 to obtain the reference pixel v. In particular, the reference pixel from refV (int2 + row + 1) is multiplied by "size - frac2" and stored in parameter a. The reference pixel from refV (int2 + row + 2) is multiplied by "frac2" and stored in parameter b These parameters a and b are then added and divided by size, or are shifted to the right by log2_size. The resulting prediction pixel v is saved in the appropriate "pred" area of ​​the memory. Steps 914, 918 and 919 and 916 are repeated until col becomes equal in Step 917.

[0044] In Step 920, the row is increased by 1. It is then determined in Step 921 whether the row is smaller than size. As long as the row is smaller than size, Steps 902 are repeated to obtain the reference pixel in the prediction block. This operation ends when row becomes equal in size in Step 921.

[0045] As mentioned above, increasing the number of predictor block candidates contributes to improving coding efficiency, while increasing the number of predictor block candidates leads to an increase in computational load. Therefore, in order to increase the number of predictor block candidates to thereby improve coding efficiency, you should review the process of creating a prediction block candidate to achieve further process efficiency. Considering the process shown in FIG. 9, two computational bottlenecks can be seen. The first computational bottleneck is the comparison and branched operations of Step 914, which are repeated in a loop. The second computational bottleneck is the split operation of Step 918, which is also done in a loop.

[0046] Nowadays, Single-Instruction Multiple Data (SIMD) architecture is available for effective calculations. SIMD allows computers with multiple processor components to perform the same operation on multiple data simultaneously. However, typical SIMD architectures do not support looping or joining / branching in the loop and therefore cannot be used to implement the process shown in FIG. 9 due to the fact that it includes looped Steps 914 and 918, although the loops starting from Step 907 and 910 are sufficiently fault tolerant to be implemented by SIMD. Therefore, the object of the present invention is to get rid of computational bottlenecks from the process shown in FIG. 9 and providing low-frame intra-frame prediction, which will allow ordinary SIMD architectures to be used to perform parallel processing for all prediction directions shown in FIG. 8.

[0047] In FIG. 10 is a flowchart showing a low-complex intra-prediction process carried out according to an embodiment of the present invention that is intended to replace the process of FIG. 9 in performing the process at Step 504 of FIG. 5. In FIG. 10, the same steps as were performed in FIG. 9 have the same stage numbers as those in FIG. 9, for example

Stages 900, 901, 902, 904, 905, 906, 907, 908, 909, 910, 911, 912, 920 and 921. The description of these common stages will not be repeated here. Steps 1000 and 1001 are specific steps for the process of FIG. 10. As can be seen from the comparison of the process shown in FIG 9, the process of FIG 10 eliminates the comparison step of Step 903 and all of the branched stages to the left of Step 903, which occurs when the angle is less than zero, thereby eliminating computational bottlenecks from Steps 914 and 918.

[0048] In the steps 1000 and 1001 added, it is determined whether the angle is equal to or greater than -1. When the angle is equal to or greater than -1, reference pixels located on the horizontal border are sufficient to generate a prediction pixel in the prediction block, and reference pixels on the vertical border are not needed. On the other hand, when the angle is less than -1, reference pixels at the vertical border are needed to generate the prediction pixel in the prediction block. At Step 1001, the reference pixels recorded in refH are expanded in the negative direction, using at least some of the pixels stored in refV. In FIG. 11A and 11B are schematic views showing the refH extension performed in Step 1001. In FIG. 11A, reference pixels 1102 recorded in refH are from the horizontal border above target block 1101. Reference pixels 1103 recorded in refV come from the vertical border to the left of target block 1101. As shown in FIG. 11B, after Step 1001 of FIG. 10, some of the reference pixels in refV are copied to refH, and refH has an expanded portion 1104 widening in the negative direction.

[0049] In FIG. 12 is a flowchart showing the details of the process carried out at Step 1001. At Step 1201, the col counter is set to -1. col is used to identify the address of the refH extended part. At Step 1202, the reference pixel in refV to be copied to the refH extended portion is identified by:

size * col angle _.

Division in the above equation is the division of integers, and the result of the equation is an integer. This equation works similar to the process of Step 918 of FIG. 9. At Step 918, the total value of pos2 is calculated by:

(size² x (co / + l)) ^Δ&gt;&gt; log2_size.

angle

Note that shifting to the right by log2_size is tantamount to dividing by size.

[0050] In Step 1203, col is reduced by 1. It is then determined in Step 1204 whether col is equal to an angle. If col is not equal to angle, operation returns to Step 1202. Steps 1202 and 1203 are repeated until col becomes equal to angle. Thus, reference pixels are read from refV in descending order, or from top to bottom of the vertical border, and copied to refH also in descending order, or from right to left of the horizontal border. Also, not all of the reference pixels in refV are copied to refH. Only reference pixels located in the range from the top to the intersection point of the prediction direction are copied from refV to refH.

[0051] Returning to FIG. 10, the process steps beginning with Step 902 are copied from FIG. 9, and include those steps for generating prediction pixels branched to the right of the comparison step of Step 903 of FIG. 9. Note, however, that these steps of FIG. 10 use extended refH (sum of parts 1102 + 1104 of FIG. 11B), while the corresponding steps of FIG. 9 use primary refH (part 1102 of FIG. 10A). Because refH is expanded in the negative direction, no separate in-frame prediction operation specifically designed to use reference pixels stored in refV, such as branched to the left of Step 903 of FIG. 90, is needed regardless of the angle sign. 9.

[0052] In FIG. 13 is a flowchart of another embodiment of refH magnification utilizing reference pixels in refV. The process shown in FIG. 11 and 12 eliminates the bottleneck stages of Steps 914 and 918 shown in FIG. 9, and therefore an increase in the efficiency of the intra-frame prediction process is expected. The process shown in FIG 13 eliminates the splitting operations performed at Step 1202 of FIG 12 from a reference pixel copy loop from refV to refH. By eliminating the split operation from the loop, it is expected that the process shown in FIG 13 will further increase the efficiency of the intra-frame prediction process.

[0053] The process shown in FIG. 13 replaces Step 1202 of FIG. 12 Steps 1301 and 1302. Step 1302 is included in the reference pixel copying loop from refV to refH, while Step 1301 is outside this loop. Step 1301 introduces a new parameter called "InvAngle". InvAngle is appointed by:

256x size angle

Multiplication by 256 is equivalent to a left shift of 8 and ensures that each bit resulting from the "size / angle" operation is included in the calculation of the reference pixel identification in refV. At Step 1302, the reference pixel address in refV to be copied to the refH extended portion is determined by:

col * InvAngle &gt;&gt; 8.

The "col * InvAngle" result is shifted to the right by 8 to reverse the left shift operation performed in Step 1301. Note that the right shift operation from Step 1302 works to round down the "col * InvAngle" result. To round to the nearest whole number, a rounding offset of 128 can be added to the result of "col * InvAngle" before performing a right shift operation. Note that the number "256" is just an example, and Step 1301 can adjust a different offset number, preferably a power integer 2, as long as the number is large enough to keep all bits resulting from the "size / angle" operation . For example, this number may be 64 in Step 1301 instead of 256, and the number of right shift may be 6 in Step 1302 instead of 8. If 64 is used, the rounding offset should be 32.

[0054] The calculations made in Step 1301 can be replaced by a lookup operation to further reduce the computational load. In other words, a lookup table has been created that stores the InvAngle values ​​in relation to the angle value. Table 1 below is an example of the lookup table in Step 1301.

Table 1

<td>angle</td><td> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 5</td><td> 6</td><td> 7</td><td> 8</td>

<td>InvAngle</td><td> 2048</td><td> 1024</td><td> 683</td><td> 512</td><td> 410</td><td> 341</td><td> 293</td><td> 256</td>

In the table above, size is assumed to be 8 and angle is an integer between 4 and 8. Note, however, that size is not limited to 8, and may take a different value, such as 4 and 16. In addition, the angle may be a fractional number in the fixed entry as defined above.

[0055] When the reference pixel is copied from refV to refH in Step 1202 of FIG. 12 or in Step 1302 of FIG. 13, this reference pixel may pass through the low-pass filter to reduce the possible aliasing in the prediction block. The strength of this low pass filter may change according to the angle value. For example, when the angle is equal to -size, a weak low-pass filter may be used, and when the angle is -2, a strong low-pass filter may be used.

[0056] As explained above, not all reference pixels are copied from refV to refH. Because not all of the reference pixels in refV are copied, some information is lost when the pixels are copied. To alleviate this loss of information, the resolution of the reference pixels in refH and refV can be doubled so that refH and refV contain not only pixels from previously coded and reconstructed blocks, but also one pixel between two adjacent reproduced pixels that is generated by interpolating two adjacent pixels. Two adjacent pixels can simply be averaged to generate an interpolation pixel. The interpolation process may be performed when reference pixels are read at Step 900 of FIG. 9. When the pixel resolution is doubled in refH and refV, identification of the reference pixel addresses recorded in refH and refV, such as performed in Steps 907, 910, 915 and 919 of FIG. 9, and Step 1001 of FIG. 10, must be scaled. For example, "int + col + 1" performed in Steps 907, 910 and 915 must be changed to "int + 2 χ col + 2". "Int + col + 2" implemented in Steps 907, 910, 915 should be changed to "int + 2 χ col + 3". "Int2 + row + 1" and "int2 + row + 2" implemented in Step 919 should be changed to "int2 + 2 χ row + 2" and "int2 + 2 χ row + 3", respectively.

[0057] In another embodiment, the process of Step 1202 of FIG. 12 can simply be changed to "" refH \ col \ &lt;refV [-col] "to further simplify the copying process. Despite the deterioration of prediction accuracy, this implementation provides the least complexity for intra-frame prediction operations.

[0058] FIG. 11B shows the extended part 1104 added to refH. The extended part 1104 does not need to be created by reference pixels from refV. The extended portion 1104 may be formed from pixels from an area of ​​a previously restored block that spatially corresponds to the position of the expanded portion 1104. In FIG. 11B, because refH (parts 1102 and 1104) is extended in the negative direction, it is in the range from -size to 2χ size. The extended refH range can be scaled to a range of 0 to 3χ size - 1 by adding the appropriate offset when addressing the reference pixels in the extended refH. The same applies to scaling the refV range.

[0059] In another embodiment, the angle range limitation can be chosen freely. In the above embodiments, angle is assumed to be in the range from -size to size (-size &lt;angle &lt;size). In other words, in the above embodiments, the angle range restrictions are determined by the size of the target block. Note that the angle range restrictions can be specified regardless of the size of the target block, although it is still preferable that the range restriction be specified by an integer 2, so that log2_rangelimit is a positive integer and the equation "rangelimit = 1 &lt;&lt; log2_rangelimit "remained true. By choosing a sufficiently large number as a rangelimit, a large number of directions of prediction can be obtained and represented by angle values ​​in sufficiently wide angular ranges.

[0060] If the angle range restriction is specified regardless of the size of the target block, the size appearing in FIG. 9 and 10 must be replaced by rangelimit, and log2_size must be replaced by log2_rangelimit, except for Steps 909, 912, 917 and 921. The "angle&gt; -1" comparison implemented in Step 1000 of FIG. 10 must also be replaced by "angle χ sizel / rangelimit&gt; -1" or "angle χ size&gt; -rangelimii" In addition, the size appearing in Steps 1202 and 1301 of FIG. 12 and 13 must be replaced by rangelimit, and the comparison "col = angle?" made in Step 1204 must be replaced by "col = angle χ size / rangelimit?" [0061] If rangelimit is introduced as a limit of the angle range, then Table 1 ( presented above) can be replaced as follows:

<td colspan="4">this</td><td colspan="5">bale 2</td>

<td>Angle *</td><td> 2</td><td> 5</td><td> 9</td><td> 13</td><td> 17</td><td> 21</td><td> 26</td><td> 32</td>

<td>InvAngle</td><td> 4096</td><td> 1638</td><td> 910</td><td> 630</td><td> 482</td><td> 390</td><td> 315</td><td> 256</td>

In Table 2, rangelimit is set to 32. Angle * is equal to the integer "rangelimit * tan (π * angle / 8)", where angle = 1, 2, 3, 4, 5, 6, 7 and 8. InvAngle is equal to 256 * rangelimit / angle *. The values ​​in Table 2 are all integers that were obtained by rounding up. Instead of being rounded up, these numbers can be rounded down. In Table 3 below, InvAngle is 32 * rangelimit / angle *. Because "32" is used instead of "256", the accuracy of the prediction is necessarily smaller than the one in Table 2.

<td colspan="4">this</td><td colspan="5">bale 3</td>

<td>Angle *</td><td> 2</td><td> 5</td><td> 9</td><td> 13</td><td> 17</td><td> 21</td><td> 26</td><td> 32</td>

<td>InvAngle</td><td> 512</td><td> 204</td><td> 113</td><td> 78</td><td> 60</td><td> 48</td><td> 39</td><td> 32</td>

[0062] In FIG. 14 is a flowchart showing another embodiment that further simplifies the process shown in FIG. 10. The process shown in FIG. 10 copying reference pixels from refV to refH is done before the process enters the main prediction loop, while the copying process shown in FIG. 14 is performed within the main prediction loop. In addition, the process shown in FIG. 14 eliminates the InvAngle variable. Steps 900, 902 and 921 shown in FIG. 14 are derived from the respective steps of FIG. 10. [0063] In Step 1401, the lastInt counter is initialized with the value -1. lastInt represents the last pixel indicator that was added to refH. At Step 902, pos is calculated by angle * (row + 1). As explained above, pos determines the location of the intersection between the boundaries and the prediction direction represented as angle. In the context of FIG. 9, Step 902 results in a pos that identifies the location of the intersection between the horizontal boundary and the prediction direction determined by the angle. In addition, at Step 902, the integer portion in pos is written in int, and the fractional portion in pos is written in the parameter "frac". At Step 1402, it is determined whether int is less than lastInt. If int is less than lastInt, the reference pixel in refV identified by row is copied to refH to the address identified by "int + 1". Step 1402 consists of Steps 904, 905, 906, 907, 908, 909, 910, 911 and 912 shown in FIG. 9 and 10, the description of which is not repeated here. In Step 1405, int is copied to lastInt. The operation of copying int to lastInt can be performed at Step 1403 instead of at Step 1405.

[0064] The copy operation in Step 1403 copies the same pixel that was copied in Steps 1202 and 1302, where rounding down is used in these steps. Step 1403 can be modified to round to the nearest integer by conditionally using "row + 1" instead of "row" at Step 1403 when the fractional frac location calculated in Step 902 is greater than the offset that is determined by rangelimit + (angle&gt; &gt; 1). Note that the angle is -ve and frac is + ve. Using "row + 1" causes rounding up. To cause a conditional increase of row by 1, the process performed in Step 1403 is changed to refH [int +1] refV [row - ((offset frac) &gt;&gt; 31)], assuming that in 32 bit arithmetic, a shift to the right by " offset frac "gives -1 if frac is greater than offset and gives 0 otherwise. Thus, the address identifier "" row - ((offset - frac) &gt;&gt; 31) "becomes" row + 1 "when frac is larger than offset and becomes" row "otherwise. When offset is set to rangelimit, "Offset - frac" will always be positive, so there will be no rounding.

[0065] Below is a listing of the source code written in the C ++ programming language that implements the process shown in FIG. 14. The source code was modified from the TComPrediction :: xPredIntraAng function in the TcomPrediction.cpp file, which is part of the TMuC 0.7 software developed by JCT-VC, which is available at<a href="http://hevc.kw.bbc.co.uk/svn/jctvc.a124/tags/0.7">http://hevc.kw.bbc.co.uk/svn/jctvc.a124/tags/0.7</a>.

// Function for deriving the simplified angular intra predictions // Function for obtaining simplified Void TComPrediction interframe prediction:: xPredIntraAng (Int * pSrc, Int iSrcStride, Pel * &amp;

rpDst,

Int iDstStride, UInt iWidth, UInt iHeight, UInt uiDirMode, Bool bAbove,

Bool bLeft) {

Int k, 1;

Int deltaInt, deltaFract, refMainIndex;

Int intraPredAngle = 0;

Int absAng = 0;

Int signAng = 0;

Int blkSize = iWidth;

Bool modeDC = false;

Bool modeVer = false;

Bool modeHor = false;

Pel * pDst = rpDst;

// Map the mode index to main prediction direction and angle // Map the mode indicator to the main prediction direction and angle if (uiDirMode == 0) modeDC = true; else if (uiDirMode &lt;18) modeVer = true; else modeHor = true;

intraPredAngle = modeVer? uiDirMode - 9: modeHor? uiDirMode - 25:

0;

absAng = abs (intrapredAngle);

signAng = intraPredAngle &lt;0? -1: 1;

// Set bitshifts and scale the angle parameter to size2 // Set bit offsets and scale the angle parameter to size2 Int iAngTable [9] = {0, 2, 5, 9, 13, 17, 21, 26, 32}; absAng = iAngTable [absAng];

intraPredAngle = signAng * absAng;

// Do the DC prediction // Perform DC prediction if (modeDC) {

Pel dcval = predIntraGetPredValDC (pSrc, iSrcStride, iWidth, iHeight, bAbove, bLeft);

for (k = 0; k &lt;blkSize; k ++) {for (l = 0; l &lt;blkSize; 1 ++) {pDst (k * iDstStride + 1] = dcval;

} }

} // Do angular predictions // Perform angular predictions

<td>else</td><td colspan="3"> {</td>

<td>Pel</td><td>tmp;</td><td></td><td></td>

<td>int</td><td>* pSrcTL = pSrc</td><td>- iSrcStride</td><td> - 1;</td>

<td>int</td><td colspan="2">iStepMain = (modeVer)? 1:</td><td>iSrcStride;</td>

<td>f</td><td>(intraPredAngle</td><td> == 0){</td><td></td>

for (k-0; k &lt;blkSize; k ++) {for (l = 0; 1 &lt;blkSize; 1 ++) {pDst [k * iDstStride + 1] = pSrcTL [(1 + 1) * iStepMain];

^}^} }

else {

Int iStepSide = (modeVer)? iSrcStride 1; int lastDeltaInt = -1;

Int iOffset = 32 + (intraPredAngle &gt;&gt; 1); // enables rounding to nearest side reference // enables rounding to the nearest side reference // Int iOffset = 32; // no rounding. (without rounding)

Pel ref [2 * MAX_CU_SIZE];

Pel * refMain = ref + ((intraPredAngle &lt;0)? BlkSize: 0); if (intraPredAngle&gt; 0) {for (k = 0; k &lt;2 * blkSize; k ++) refMain [k] = pSrcTL [(k + 1) * iStepMain];

} else {for (k = -1; k &lt;blkSize; k ++) // the rest are copied later in step 1403, as and when required // the rest is copied later in step 1403, if required refMain [k] = pSrcTL [(k + 1) * iStepMain];

} for (k = 0; k &lt;blkSize; k ++) {

Int deltaPos = (k + 1) * intraPredAngle; deltalnt = deltaPos &gt;&gt; 5;

deltaFract = deltaPos &amp; (32 - 1);

if (deltalnt &lt;lastDeltalnt) {// step 1402 (step 1402) lastDeltaInt = deltaInt;

refMain [deltaInt] = pSrcTL [(k - ((iOffsetdeltaFract) &gt;&gt; 31)) * iStepSide];

// step 1403 // step 1403 ^} // step 1404 // step 1404 if (deltaFract) {// Do linear filtering // Perform linear filtering for (1 = 0; 1 &lt;blkSize; 1 ++) {refMainIndex = 1 + deltaInt:

pDst [k * iDstStride + 1] = (Pel) (((32-deltaFract) * refMain [refMainIndex] + deltaFract * refMain [refMainlndex + 1] + 16) &gt;&gt; 5);

} }

else {// Just copy the integer samples // Copy integer samples for (1 = 0; 1 &lt;&lt; blkSize; 1 ++) {pDst [k * iDstStride + 1] = refMain [1 + deltaInt];

} }

} }

// Flip the block if this is the horizontal mode // Toggle the block if it is horizontal mode if (modeHor) {for (k = 0; k &lt;blksize-1; k ++) {for (1 = k + 1; 1 &lt; blkSize: 1 ++) {tmp = pDst [k * iDstStride + 1];

pDst (k * iDstStride + 1] = pDst (1 * iDstStride + k];

pDst [1 * iDstStride + k] = tmp;

} }

} ^} [0066] Given that many changes and modifications of the present invention will undoubtedly become apparent to those of ordinary skill in the art after reading the above description, it should be taken into account that each specific embodiment shown and described for clarification does not is in no way considered restrictive. Therefore, references to the details of various embodiments are not intended to limit the scope of the claims, which in themselves discuss only those features considered relevant to the present invention.