Method and apparatus for determining encoding mode based on temporal and spatial complexity

FIELD

0001The present disclosure relates to an encoding mode decision apparatus and method using temporal and spatial complexities. More particularly, the present invention relates to an apparatus and method for deciding encoding mode by way of a rate-distortion optimization to minimize the calculation of a rate-distortion cost (RD cost).

BACKGROUND

0002The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.

0003Typical video compression schemes of the standards MPEG-1, MPEG-2, MPEG-4 Visual, H.261, H.263, and H.264/MPEG-4 AVC (Advanced Video Coding) compress video data by dividing each frame into a multitude of macroblock units, by which a predicted block is obtained through a prediction process, and then transforming and quantizing the difference between the original video block and the predicted block.

0004An intra prediction and inter prediction are two available prediction methods. The intra prediction performs the current block prediction by utilizing data of blocks that are present surrounding the current frame. The inter prediction generates a predicted block corresponding to the current block from previously encoded one or more video frames by utilizing a block-based motion compensation.

0005Particularly, in the inter prediction event, H.264/MPEG-4 AVC performs the motion prediction not by using a set dimension of block but with seven different block modes of 4×4 to 16×16 varieties.

0006<figref idref="f0001">FIG. 1a</figref> illustrates blocks of various sizes used in the conventional variable block-size motion prediction of H.264/MPEG-4 AVC.

0007As shown, the respective macroblock luminance components (a 16×16 sample) may be divided in four ways. In other words, each macroblock may be a single 16×16 macroblock, two 16×8 partitions thereof, two 8×16 partitions, or four 8×8 partitions to be motion predicted.

0008In addition, if an 8×8 mode were selected, four 8×8 sub-macroblocks of a macroblock may be subdivided into four ways, respectively. Specifically, with the selection of the 8×8 mode each 8×8 block may take one of four shapes comprising a single 8×8 sub-macroblock partition, two divided 8×4 sub-macroblock partitions, two divided 4×8 sub-macroblock partitions, and four divided 4×4 sub-macroblock partitions.

0009Within the respective macroblocks, these partitions and the sub-macroblocks may be related in numerous combinations. This method of dividing macroblocks into different sizes of sub-blocks is called tree structured motion compensation.

0010To decide the best encoding mode for a macroblock, according to the H.264 standard, the rate-distortion optimization is used. Typical rate-distortion optimization equation is as follows: <maths id="math0001" num="Equation 1"><math display="block"><msub><mi>J</mi><mi mathvariant="italic">mode</mi></msub><mo>=</mo><mi>D</mi><mo>+</mo><msub><mi>λ</mi><mi mathvariant="italic">mode</mi></msub><mo>⋅</mo><mi>R</mi></math><img file="EP2242276B1_D0001.tif" /></maths> where J_mode is a rate-distortion cost, λ_mode is Lagrangian multiplier, D is a value of distortion between an original macroblock and a reconstructed macroblock, and R is a coefficient to reflect the number of bits related to mode selection and the quantization value of the macroblock among others. Using Equation 1, the respective macroblocks are preliminarily encoded at the level of the different size-variable block divisions before deciding the mode with the lowest rate-distortion cost as the optimum mode.

0011In other words, the encoder carries out encoding in all the predicted encoding modes and then calculates rate-distortion costs to decide the prediction mode with the lowest rate-distortion cost as the prediction mode for use in the actual encoding process.

0012Although this technique of the rate-distortion optimization may dramatically improve the compression performance of the H.264/AVC encoder value as the optimum mode, the resulting increased complexity is a critical obstacle to the real-time encoding.

0013<figref idref="f0001">FIG.1b</figref> illustrates the calculating complexity by performing the rate-distortion optimization. As illustrated in <figref idref="f0001">FIG.1b</figref>, to perform the rate-distortion optimization increases the calculation complexity to at least seven to eight times greater than otherwise.

0014So, there is a practical need to provide a technology for the encoder to compress videos to minimize the compression speed and dramatically lower the calculation complexity while maintaining the compression performance using the rate-distortion optimization.

0015The document <patcit id="pcit0001" dnum="US5682204A"><text>US5682204</text></patcit> discloses a video encoder which uses intra-coding when an activity level of a current macro-block is smaller than a threshold level.

0016The document <patcit id="pcit0002" dnum="US5832234A"><text>US5832234</text></patcit> discloses a method for encoding images using block-based macroblock-level statistics.

0017The document "<nplcit id="ncit0001" npl-type="b"><text>A hierarchical Framework for fast Macroblock Prediction Mode Decision in H264" of Hend Dong Shen et al.,January 2006, Advances in multimedia information processing - PCM 2006 Lecture notes in Computer science, LNCS, Springer, Berlin, pp827-834</text></nplcit> discloses a hierarchical framework for fast macroblock prediction mode decision in H.264, wherein a classification-based fast mode decision scheme is considered in which temporal and spatial complexity features of a macroblock are assessed against different thresholds so that only a subset of the plurality of modes needs to be evaluated for the macroblock and expensive rate-distortion computations can be saved.

SUMMARY

0018In view of the stated needs to satisfy, the present disclosure seeks to provide an apparatus and method for deciding encoding mode by way of a rate-distortion optimization to minimize the calculation of a rate-distortion cost.

0019One embodiment provides an encoding mode decision apparatus as defined in claim 1.

0020Another embodiment provides an encoding mode decision method as disclosed in claim 5.

0021As described above, according to the disclosure, it is not only possible to provide more accurate calculations of the temporal and spatial complexities of a macroblock but elect the optimal encoding mode using the same resulting in a substantially reduced calculation complexity when using the rate-distortion optimization technique as well as an improved video processing speed.

0022Further areas of applicability will become apparent from the description provided herein. It should be understood that the description and specific examples are intended for purposes of illustration only and are not intended to limit the scope of the present disclosure.

DRAWINGS

0023The drawings described herein are for illustration purposes only and are not intended to limit the scope of the present disclosure in any way. <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1A</figref> illustrates blocks of different sizes used in the size-variable block motion prediction of the conventional H.264/MPEG-4 AVC;</li><li><figref idref="f0001">FIG. 1B</figref> illustrates a calculated complexity following an execution of the rate-distortion optimization;</li><li><figref idref="f0002">FIG. 2</figref> is a block diagram of an electronic configuration of an encoding mode decision apparatus using temporal and spatial complexities according to an embodiment;</li><li><figref idref="f0003">FIG. 3</figref> is a flow diagram for illustrating an encoding mode decision method using temporal and spatial complexities according to an embodiment; and</li><li><figref idref="f0004">FIGs. 4A to 4C</figref> are views for illustrating the steps of calculating the temporal and spatial complexities according to an embodiment.</li></ul>

DETAILED DESCRIPTION

0024Hereinafter, an exemplary embodiment of the present disclosure will be described with reference to the accompanying drawings. In the following description, the same elements will be designated by the same reference numerals although they are shown in different drawings. Further, in the following description of the present disclosure, a detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present disclosure rather unclear.

0025According to the H.264 image compression standard, macroblocks may be classified as in Table 1 and Table 2 below.

0026Table 1 shows the types and classification of the intra-block mode, and Table 2 is those of the inter-block mode. <tables id="tabl0001" num="0001"><table frame="all"><title>[Table 1]</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="51mm" /><colspec colnum="2" colname="col2" colwidth="58mm" /><thead><row><entry align="center" valign="top"><b>Intra-Block Mode</b></entry><entry align="center" valign="top"><b>Classification</b></entry></row></thead><tbody><row><entry align="center">Intra 16×16 Vertical</entry><entry align="center">Large vertical intra-block mode</entry></row><row><entry align="center">Intra 16×16_Horizontal</entry><entry align="center">Large horizontal intra-block mode</entry></row><row><entry align="center">Intra 16×16_DC</entry><entry align="center">Large non-directional intra-block mode</entry></row><row><entry align="center">Intra 16×16_Plane</entry><entry align="center">Large non-directional intra-block mode</entry></row><row><entry align="center">Intra 4×4_Vertical</entry><entry align="center">Small vertical intra-block mode</entry></row><row><entry align="center">Intra 4×4_Horizontal</entry><entry align="center">Small horizontal intra-block mode</entry></row><row><entry align="center">Intra 4×4_DC</entry><entry align="center">Small non-directional intra-block mode</entry></row><row><entry align="center">Intra 4×4_Diagonal Down Left</entry><entry align="center">Small non-directional intra-block mode</entry></row><row><entry align="center">Intra 4×4_Diagonal Down Right</entry><entry align="center">Small non-directional intra-block mode</entry></row><row><entry align="center">Intra 4×4_Vertical Right</entry><entry align="center">Small vertical intra-block mode</entry></row><row><entry align="center">Intra 4×4_Horizontal Down</entry><entry align="center">Small horizontal intra-block mode</entry></row><row><entry align="center">Intra 4×4_Vertical Left</entry><entry align="center">Small vertical intra-block mode</entry></row><row><entry align="center">Intra 4×4_Horizontal Up</entry><entry align="center">Small horizontal intra-block mode</entry></row></tbody></tgroup></table></tables><tables id="tabl0002" num="0002"><table frame="all"><title>[Table 2]</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="32mm" /><colspec colnum="2" colname="col2" colwidth="59mm" /><thead><row><entry align="center" valign="top"><b>Inter-Block Mode</b></entry><entry align="center" valign="top"><b>Classification</b></entry></row></thead><tbody><row><entry align="center">Inter SKIP</entry><entry align="center">Large non-directional inter-block mode</entry></row><row><entry align="center">Inter 16×16</entry><entry align="center">Large non-directional inter-block mode</entry></row><row><entry align="center">Inter 16×8</entry><entry align="center">Large horizontal inter-block mode</entry></row><row><entry align="center">Inter 8×16</entry><entry align="center">Large vertical inter-block mode</entry></row><row><entry align="center">Inter 8×8</entry><entry align="center">Small non-directional inter-block mode</entry></row><row><entry align="center">Inter 8×4</entry><entry align="center">Small horizontal inter-block mode</entry></row><row><entry align="center">Inter 4×8</entry><entry align="center">Small vertical inter-block mode</entry></row><row><entry align="center">Inter 4×4</entry><entry align="center">Small non-directional inter-block mode</entry></row></tbody></tgroup></table></tables>

0027In the present disclosure, block modes may be classified by size into 'large block modes' defining four intra-block modes of an intra 16X16_Vertical, intra 16X16_Horizontal, intra 16X16_DC, and intra 16X16_Plane, and four inter block modes of an inter SKIP, inter 16X16, inter 16X8, and inter 8X16; and 'small block modes' defining nine intra block modes of an intra 4X4_Vertical, intra 4X4_Horizontal, intra 4X4_DC, intra 4X4_Diagonal Down Left, intra 4X4_Diagonal Down Right, intra 4X4_Vertical Right, intra 4X4_Horizontal Down, intra 4X4_Vertical Left, and intra 4X4_Horizontal UP and four inter block modes of inter 8X8, inter 8X4, inter 4X8, and inter 4X4.

0028Additionally, in the present disclosure, block modes may be classified according to directional features into 'vertical block modes' as defined by four vertical intra block modes including an intra 16X16_Vertical, intra 4X4_Vertical, intra 4X4_Vertical Right, and intra 4X4_Vertical Left and two vertical inter block modes having an inter 8X16 and an inter 4X8; 'horizontal block modes' as defined by four horizontal intra block modes including an intra 16X16_Horizontal, intra 4X4_Horizontal, intra 4X4_Horizontal Down, and intra 4X4_Horizontal UP and two horizontal inter block modes of an inter 16X8 and an inter 8X4; and 'non-directional block modes' with neither a vertical nor a horizontal feature as defined by five intra block modes including an intra 16X16_DC, intra 16X16_Plane, intra 4X4_DC, intra 4X4_Diagonal Down Left, and intra 4X4_Diagonal Down Right and four inter block modes of an inter SKIP, inter 16X16, inter 8X8, and inter 4X4.

0029Therefore, the intra block modes or inter block modes shown in Tables 1 and 2 may be classified as in the 'Classification' sections depending on their respective dimensional and directional features. Specifically, for example, the 'intra 16X16_Vertical' is an intra block mode that is sized 16X16 entitled to a 'large block mode' with the vertical feature making the 'vertical block mode'. So, combining these individual features results in the 'large vertical intra-block mode' classified in Table 1. The rest intra and inter block modes are classified in this way.

0030<figref idref="f0002">FIG. 2</figref> is a block diagram of an electronic construction of the encoding mode decision apparatus using temporal and spatial complexities according to an embodiment.

0031The encoding mode decision apparatus of one embodiment may comprise a temporal complexity calculator 210, a spatial complexity calculator 220, and a mode decider 230.

0032The temporal complexity calculator 210 of an embodiment is a data processing means for executing a calculation to generate and store data and it analyzes a macroblock of an image to calculate the temporal complexity of the macroblock.

0033In addition, the temporal complexity calculator 210 of an embodiment calculates a block residual that is a macroblock residual and Hadamard transforms the same to calculate the temporal block complexity, which is then divided by the quantization step size to eventually calculate the temporal complexity. The calculating procedure for the temporal complexity will be described below in detail with reference to <figref idref="f0004">FIG. 4</figref>.

0034The spatial complexity calculator 220 of an embodiment is also a data processing means for performing calculations to generate and store data and it analyzes macroblocks of an image for calculating the spatial complexity of the macroblock.

0035In addition, the spatial complexity calculator 220 according to an embodiment of the present disclosure calculates a vertical complexity by performing vertical filtering of the macroblock and calculates a horizontal complexity by performing horizontal filtering of the macroblock and then divides the vertical plus horizontal complexities to generate a spatial block complexity, which is then divided by the quantization step size in order to calculate the spatial complexity. The calculating procedure for the spatial complexity will be described below in detail with reference to <figref idref="f0004">FIG. 4</figref>.

0036The mode decider 230 of an embodiment of the present disclosure is a data processing means for carrying out calculations to generate and store data and it utilizes the temporal complexity calculated in the temporal complexity calculator 210 and the spatial complexity from the spatial complexity calculator 220 to decide the block mode to apply in encoding.

0037Since a greater temporal complexity is more likely to cause the intra mode of encoding, the mode decider 230 in this embodiment may decide as encoding mode the intra block mode such as the intra 16X16_Vertical, intra 16X16_Horizontal, intra 16X16_DC, intra 16X16_Plane, intra 4X4_Vertical, intra 4X4_Horizontal, intra 4X4_DC, intra 4X4_Diagonal Down Left, and intra 4X4_Diagonal Down Right, intra 4X4_Vertical Right, intra 4X4_Horizontal Down, intra 4X4_Vertical Left, and intra 4X4_Horizontal Up; and since a less temporal complexity is more likely to cause encoding in the inter mode, the encoding mode of choice may be the inter block mode such as the inter SKIP, inter 16X16, inter 16X8, inter 8X16, inter 8X8, inter 8X4, inter 4X8,and inter 4X4.

0038Therefore, the mode decider 230 in this embodiment compares the temporal complexity with a predetermined temporal threshold to see if the temporal complexity exceeds the threshold and if it is true, it selects the intra block mode as the mode of encoding, and if the temporal complexity is less than or equal to the threshold, it selects the inter block mode for encoding.

0039According to the present disclosure, the temporal threshold may be defined as a temporal complexity of a previous macroblock in a previous frame to a current frame with the previous macroblock being equally positioned to a current macroblock contained in the current frame.

0040In addition, since a greater spatial complexity tends to cause a small block mode to be chosen as the encoding mode, the mode decider 230 of an embodiment at the greater spatial complexity may decide as the encoding mode the small block mode such as the intra 4X4_Vertical, intra 4X4_Horizontal, intra 4X4_DC, intra 4X4_Diagonal Down Left, and intra 4X4_Diagonal Down Right, intra 4X4_Vertical Right, intra 4X4_Horizontal Down, intra 4X4_Vertical Left, intra 4X4_Horizontal Up, inter 8X8, inter 8X4, inter 4X8, and inter 4X4; and as a less spatial complexity is more likely to cause an encoding in a large block mode, the encoding modes of choice by the mode decider 230 may be the large block mode such as the intra 16X16_Vertical, intra 16X16_Horizontal, intra 16X16_DC, intra 16X16_Plane, inter SKIP, inter 16X16, inter 16X8, and inter 8X16.

0041Therefore, the mode decider 230 of the embodiment can compare the spatial complexity with the predetermined spatial threshold to set the small block modes as the encoding mode at the comparatively higher spatial complexity or decide the large block encoding modes at the equal or lower spatial complexity.

0042In this disclosure, the spatial threshold means a spatial complexity of a previous macroblock in a previous frame with respect to a current frame with the previous macroblock being equally positioned to a current macroblock in the current frame.

0043Additionally, mode decider 230 of an embodiment of the present disclosure may compare the vertical complexities with the horizontal complexities of the macroblock to see if the vertical complexity is greater than the horizontal complexity where the encoding mode of choice is the vertical block mode such as the intra 16X16_Vertical, intra 4X4_Vertical, intra 4X4_Vertical Right, and intra 4X4_Vertical Left, inter 8X16, and, inter 4X8; if the vertical complexity equals to the horizontal complexity where the decoding mode is decided to be the 'non-directional block mode with no directional feature including the intra 16X16_DC, intra 16X16_Plane, intra 4X4_DC, intra 4X4_Diagonal Down Left, and intra 4X4_Diagonal Down Right, inter SKIP, inter 16X16, inter 8X8, and inter 4X4; and if the vertical complexity is less than the horizontal complexity where the mode decided to apply in encoding is the horizontal block mode such as the intra 16X16_Horizontal, intra 4X4_Horizontal, intra 4X4_Horizontal Down, and intra 4X4_Horizontal UP, inter 16X8, and inter 8X4.

0044In the present disclosure, the temporal complexity calculator 210, spatial complexity calculator 220, and mode decider 230 may be implemented with independent hardware components including memories for storing the respective functional programs and data and microprocessors for executing the stored programs to generate data and storing the same in the memories although the above components may be provided by the corresponding functional program modules, which are stored in the memories until they are executed by the microprocessors.

0045In its decision of the encoding mode, the mode decider 230 is described above as either using the temporal complexity in choosing between the intra and inter block modes, or using the spatial complexity to elect the small or large block mode, or using the vertical and horizontal complexities to elect among the vertical, non-directional, and horizontal block modes, although the respective decision methods may be combined rather than performed selectively.

0046For a specific example, if the temporal and spatial complexities are greater than their respective threshold values and the vertical complexity is greater than the horizontal complexity, the mode decider 230 may select, among the intra block modes, the small and vertical intra block mode (intra 4X4_Vertical, intra 4X4_Vertical Right, and intra 4X4_Vertical Left) as the encoding mode. In this case the calculation amount and the processing time to perform the rate-distortion optimization can be minimized with the encoder incorporating the present embodiment of the encoding mode decision apparatus using temporal and spatial complexities since the apparatus may only calculate the rate-distortion costs in the above three block mode selections before electing the final mode of encoding.

0047The still or video image compressing encoders dissect the images frame by frame before starting the encoding operation where the respective frame's images are divided into macroblocks to encode, when a concurrent decision is made on the encoding mode. In deciding the mode of encoding by the encoders, the rate-distortion optimization has been used in the H.264 video compression standard. However, the used rate-distortion optimization technique in the encoding had to be repeatedly performed in every block mode predicted as the encoding mode (i.e. the intra block modes and inter block modes) to obtain the rate-distortion cost, which exacts complex calculations and increases the burden on the encoder, thereby consuming a substantially longer time to perform the encoding operation.

0048In response, in the present disclosure as described above, the encoding mode may be so determined that the encoder has the minimized number of block modes in which the rate-distortion cost is calculated to cope with the inefficiency of having to deal with every block mode and the repetitive calculations.

0049To this effect, the encoding mode decision apparatus that can be implemented in a hardware or a software module inside an encoder and that employs the temporal and spatial complexities as described with reference to <figref idref="f0002">FIG. 2</figref> is adapted to calculate the temporal complexity and the spatial complexity of a macroblock to determine the least possible number of encoding modes in which the encoder may perform the rate-distortion optimization technique to decide the final encoding mode to apply.

0050Below is a description on the operational process of the encoding mode decision apparatus using temporal and spatial complexities.

0051<figref idref="f0003">FIG. 3</figref> is a flow diagram for illustrating a method for deciding encoding mode by using temporal and spatial complexities according to an embodiment.

0052The apparatus for deciding encoding mode by using temporal and spatial complexities (hereinafter simply called 'encoding mode decision apparatus') of the present disclosure calculates the temporal complexity of the macroblock at S310 and calculates the spatial complexity at S320.

0053Upon calculating the temporal and spatial complexities, the encoding mode decision apparatus checks to see if the temporal complexity is greater than the predetermined temporal threshold through their comparison (S330), and decides the encoding mode as the intra block mode if the temporal complexity is greater (S340) and the inter block mode if the temporal complexity is less than or equal to the temporal threshold (S342).

0054In other words, the encoding mode decision apparatus may rely on the condition that the temporal complexity of the current macroblock in the current frame is greater than that of the previous macroblock in the previous frame in deciding the intra block mode for encoding where the intra block mode is more probable to be the encoding mode regardless of the hassle of the rate distortion cost calculation for the encoding mode decision, and in the opposite condition it picks the inter block mode.

0055In addition, the encoding mode decision apparatus checks to see if the spatial complexity is greater than the predetermined spatial threshold through their comparison (S350), and decides the encoding mode as the small block mode if the spatial complexity is greater (S360) or the large block mode if the spatial complexity is less than or equal to the spatial threshold (S362).

0056In other words, the encoding mode decision apparatus may rely on the condition that the spatial complexity of the current macroblock in the current frame is greater than that of the previous macroblock in the previous frame in deciding the small block mode for encoding where the small block mode is more probable to be the encoding mode regardless of the hassle of the rate distortion cost calculation for the encoding mode decision, or otherwise it picks the large block mode.

0057Further, the encoding mode decision apparatus compares the vertical complexities with horizontal complexities included in the spatial complexity to see if the vertical complexity is greater than the horizontal complexity (S370), and decides the encoding mode as the vertical block mode if the vertical block mode is greater, the non-directional block mode if the vertical and horizontal complexities are same (S374), and the horizontal block mode if the vertical complexity is less than the horizontal complexity (S376).

0058In other words, the encoding mode decision apparatus may rely on the condition that the vertical complexity of the current macroblock in the current frame is greater than the horizontal complexity in deciding the vertical block mode for encoding where the identical vertical block mode is more probable to become the encoding mode regardless of the hassle of the rate distortion cost calculation for the encoding mode decision, and it selects the non-directional block mode if the vertical and horizontal complexities are same or the horizontal block mode if the vertical complexity is less.

0059As above, the encoding mode decision apparatus may operate using the temporal complexity, the spatial complexity, and the vertical and horizontal complexities contained in the spatial complexity.

0060In the meantime, although <figref idref="f0003">FIG. 3</figref> illustrates the encoding mode decision through the procedures of deciding the encoding mode using the temporal complexity (steps S330 thru S342), the spatial complexity (steps S350 thru S362), and both the vertical and horizontal complexities contained in the spatial complexity (steps S360 thru S376), it will be understood by the skilled persons in the art that these procedures may be executed with selected one or two above, or the three procedures altogether in a sequence, which can be arbitrary.

0061Therefore, assuming that, for example, the three procedures of <figref idref="f0003">FIG. 3</figref> were carried out in the illustrated sequence to elect the intra block mode by using the temporal complexity, the small block mode by using the spatial complexity, and the vertical block mode by using the vertical and horizontal complexities, the conclusive block modes may become the classified 'small vertical intra block mode' in Table 1, which are intra 4X4_Vertical, intra 4X4_Vertical Right, and intra 4X4_Vertical Left. That is, it is sufficient for the encoder to calculate the rate-distortion cost in the above three modes to decide the final encoding mode in which the video compression will be made.

0062Additionally, if, for example, it is assumed that the encoding mode decision apparatus proceeded to elect the horizontal block mode along the steps S360 thru S376 using both the vertical and horizontal complexities and then elect the inter block mode along the steps S330 through S342 using the temporal complexity, the final selection for encoding would be 'horizontal inter block modes (i.e. 'large horizontal inter block mode' and 'small horizontal inter block mode'), which are inter 16X8 and inter 8X4. That is, the encoder may calculate the rate-distortion cost only in the above two modes to decide the final encoding mode in which the video compression will be made.

0063<figref idref="f0004">FIGs. 4A, 4B and 4C</figref> illustrate the steps of calculating the temporal and spatial complexities according to an embodiment.

0064<figref idref="f0004">FIG. 4A</figref> shows the Hadamard Transform matrix that is used to calculate the temporal complexity.

0065In order to calculate the temporal complexity of the macroblock, the encoding mode decision apparatus performs a motion compensation on the macroblock to remove any redundancies before it does a calculation for a residual signal matrix of a block residual by which the Hadamard Transform matrix of <figref idref="f0004">FIG. 4A</figref> is multiplied in the Hadamard Transform operation to complete the temporal complexity calculation. Also, the encoding mode decision apparatus calculates the temporal complexity by dividing the temporal block complexity by the quantization step size. Here, the macroblock means the 16X16 matrix having the pixel value thereof. Such a process may be mathematically expressed as Equation 2. <maths id="math0002" num="Equation 2"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Residual</mi><mo>*</mo><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Hadamard</mi></mtd></mtr><mtr><mtd><mrow><mrow><mi mathvariant="italic">Temporal</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mfenced><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mn mathvariant="normal">15</mn></munderover><mrow><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mfenced><mi>i</mi></mfenced></mrow></mstyle></mfenced></mrow><mo>/</mo><mrow><mi>Q</mi><mo>_</mo><mi mathvariant="italic">step</mi></mrow></mrow></mtd></mtr></mtable></math><img file="EP2242276B1_D0002.tif" /></maths>

0066In this disclosure, the motion compensation firstly removes the macroblock redundancy followed by additional Hadamard Transform to remove the redundancy of the residual signals once more, thereby drastically reducing errors in the actual amount of bits generated.

0067In other words, since Hadamard Transformation is capable of decomposing input signals into frequencies, the residual signal after Hadamard Transform may be divided into sixteen frequencies, which approximate the result of the frequency decomposition from a discrete cosine transform (DCT) used to compress signals in the process of an actual encoding operation. Therefore, the encoding mode decision apparatus can predict with a very high accuracy the amount of data that generates the differential signals against the previous frame with a temporal similarity with the use of the decomposed frequencies through Hadamard Transform, whereby calculating the temporal complexity with high accuracy.

0068<figref idref="f0004">FIG. 4B</figref> shows a vertical filter used to calculate the spatial complexity and <figref idref="f0004">FIG. 4C</figref> shows a horizontal filter to calculate the spatial complexity.

0069In order to calculate the spatial complexity, the encoding mode decision apparatus performs a vertical filtering of the macroblock by multiplying the same by the vertical filter shown in <figref idref="f0004">FIG. 4B</figref> to obtain the vertical complexity, and a horizontal filtering of the macroblock by multiplying the same by the horizontal filter shown in <figref idref="f0004">FIG. 4C</figref>. And the encoding mode decision apparatus may divide the sum of the vertical and horizontal complexities by two to obtain the spatial block complexity, which is then divided by the quantization step size to provide the spatial complexity. Here, the macroblock refers to the 16X16 matrix having the pixel value thereof. Such a process may be mathematically expressed as Equation 3. <maths id="math0003" num="Equation 3"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">Vertical</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mi mathvariant="italic">MacroBlock</mi><mo>*</mo><mi mathvariant="italic">Vertical</mi><mo>_</mo><mi mathvariant="italic">Filter</mi></mtd></mtr><mtr><mtd><mi mathvariant="italic">Horizontal</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mi mathvariant="italic">MacroBlock</mi><mo>*</mo><mi mathvariant="italic">Horizontal</mi><mo>_</mo><mi mathvariant="italic">Filter</mi></mtd></mtr><mtr><mtd><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mfenced><mrow><mi mathvariant="italic">Vertical</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>+</mo><mi mathvariant="italic">Horizontal</mi><mo>_</mo><mi mathvariant="italic">Complecity</mi></mrow></mfenced><mo>/</mo><mn>2</mn></mtd></mtr><mtr><mtd><mrow><mrow><mi mathvariant="italic">Spatial</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mo>=</mo><mfenced><mfrac><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mn>255</mn></munderover><mrow><mi mathvariant="italic">Block</mi><mo>_</mo><mi mathvariant="italic">Complexity</mi><mfenced><mi>i</mi></mfenced></mrow></mstyle><mn>16</mn></mfrac></mfenced></mrow><mo>/</mo><mrow><mi>Q</mi><mo>_</mo><mi mathvariant="italic">step</mi></mrow></mrow></mtd></mtr></mtable></math><img file="EP2242276B1_D0003.tif" /></maths>

0070In the present disclosure, 2-dimensional five-tab filters (i.e., vertical filters and horizontal filters) are used to calculate the spatial complexity. Spatial complexity is calculated in order to predict the amount of bit generation with high accuracy in case the intra prediction is used.

0071Typically, in the spatial complexity calculations, differences between the adjacent pixels are obtained in a macroblock, and then the grand total of the differences are simply used to calculate the complexity. In contrast, according to the present disclosure, the 2-dimensioanally constructed high pass filter (i.e., vertical and horizontal filters) are used to perform detections by assigning weights to the significance according to the positions of the pixels in order to find the edge that may present in the input images of the encoder. Since the edge may have various directivities, the filtering is carried out using both the vertical and horizontal filters, and through the sum of the filtered outputs the edge detection is possible for the horizontal and vertical directions as well as the diagonal direction.

0072In addition, the present disclosure uses the quantization step size that is an important factor in the actual encoding process in controlling the bit generation, thereby calculating the spatial complexity in an extra high accuracy. Thanks to the spatial complexity calculated by adding the vertical filtered value and the horizontal filtered value of the macroblock, a dramatic reduction of errors can be achieved in the bit generation amounts and the spatial complexities which can change following the quantization width variation. This approach is used to filter out the most effective one of many prediction directions in the intra predicting, offering an improved accuracy in electing the encoding mode.

0073The scope of the disclosure is not to be limited by the above embodiments but by the appended claims.

INDUSTRIAL APPLICABILITY

0074As described above, the present disclosure is useful in deciding an optimal encoding mode for macroblocks through the rate-distortion optimization technique, and it can be applied to the encoding mode decision method and apparatus to minimize the rate distortion cost calculations in order to calculate the temporal and spatial complexes for the macroblocks with higher accuracy as well as elect the optimal encoding mode using the same resulting in a reduction of the calculation complexity when applying the rate-distortion technique along with an improvement of its processing speed.