A new-generation video coding standard, named High Efficiency Video Coding (HEVC), has recently been developed by JCT-VC. This new standard provides a significant improvement in picture quality, especially for high-resolution videos. However, one the most important challenges in HEVC is time complexity. A quadtree-based structure is created for the encoding and decoding processes and the rate-distortion (RD) cost is calculated for all possible dimensions of coding units in the quadtree. This provides a high encoding quality, but also causes computational complexity. We focus on a reduction scheme of the computational complexity and propose a new approach that can terminate the quadtree-based structure early, based on the RD costs of the parent and current levels. Our proposed algorithm is compared with HEVC Test Model version 10.0 software and a previously proposed algorithm. Experimental results show that our algorithm provides a significant time reduction for encoding, with only a small loss in video quality. Recently, ISO-IEC/MPEG and ITU-T/VCEG formed the Joint Collaborative Team on Video Coding (JCT-VC), which developed the next-generation video coding standard called High Efficiency Video Coding (HEVC) [1] . The major goal of HEVC was to achieve a significant improvement in coding efficiency, compared to H.264/AVC [2] , especially with high-resolution video content. The video encoding and decoding processes in HEVC are composed of three units: a coding unit (CU) for the root of the transform quadtree, as well as a prediction mode for the INTER/SKIP/INTRA prediction; a prediction unit (PU) for coding the mode decision, including motion estimation and rate-distortion (RD) optimization; and a transform unit (TU) for transform coding and entropy coding. Initially, a frame is divided into a sequence of its largest non-overlapping coding units, called a coding tree unit (CTU). A CTU can be recursively divided into smaller CUs and made flexible using quadtree partitioning, which is called a coding tree block (CTB). A CTU has a block structure size of 64 × 64 pixels, which can be decomposed into four 32 × 32 pixels CUs. Further still, each 32 × 32 pixels CU can be divided into four CUs of 16 × 16 pixels. This decomposition process can continue to CUs of up to 8 × 8 pixels blocks. That means the 8 × 8 pixels block is the smallest possible for a CU. Moreover, for the different combinations of CU structures, different CTBs are generated for a single CTU. For each CTB, RD cost value is calculated. The CTB which has the minimum RD cost value is considered as the best one. The illustration of the CTB structure for a CTU is given in Fig. 1(a) . In Fig. 1 , a 64 × 64 pixels CTU block is shown divided into smaller blocks of CUs. Upon calculating the RD cost for every combination, the CUs which are under the red dotted part of Fig. 1(a) give the minimum RD value. The corresponding CTU partitioning and CTB structure for this particular (best) combination is shown in Fig. 1(b) . The CTB is an efficient representation of variable block sizes so that regions of different sizes can be coded with fewer bits while maintaining the same quality. It is possible to encode stationary or homogeneous regions with a larger block size, resulting in a smaller side-information overhead. On the other hand, the CTB structure dramatically increases the computational complexity. As an example, if a frame has dimensions of 704 × 576 pixels, then it will be decomposed into 99 (11 × 9) CTUs, and a separate CTB will be created for each CTU. For each CTB, 85 calculations are involved for different CU sizes. As a result, 8,415 CU calculations are required for the CTB structure, whereas only 1,584 calculations are needed for a 16 × 16 macroblock, as was used in the previous standard (H.264/AVC). From this analysis, it is clear that the new CTB structure in HEVC greatly increases the computational complexity. From the viewpoint of real-time applications, we need faster video encoders to support real-time video services. Hence, it is important to design a HEVC encoder which can encode a video stream so as to achieve a similar bit rate and quality but also a reduction in encoding time, while comparing with the HEVC Test Model (HM) reference software as a benchmark. Only a few reports have been published regarding reducing the CTB computational complexity. In [3] , a proposed novel early-CU termination algorithm, commonly known as ECU, was integrated into the HM reference software. According to ECU, no further processing of sub-trees is required when the current CU selects SKIP mode as the best prediction mode at the current CU depth. In [4] , it is shown that when the cost of a current CU is lower than the sum of the costs of CUs belonging to the subtrees of the current CU, then no further processing of subtrees is required. In [5] , an early partition decision algorithm is presented that attempts to terminate the mode decision process after checking the INTER mode with each of the PU partition types. Some fast-termination algorithms have been reported to explore other components in HEVC [6] – [9] . In [10] , an early CU size-determination algorithm has been reported. In this work, the authors have exploited two fast approaches — adaptive depth-range determination and early termination of unnecessary motion estimation on small CU sizes. Supervised learning–based algorithms have also been used for estimating the CU size using features specified in [11] , [12] . A Bayesian decision rule has been used in [11] and the supported vector machine was applied in [12] to determine the CU size before the general RD optimization technique in HM reference software. All the above mentioned algorithms are related with INTER prediction. On the other hand, a fair number of works have been reported in fast INTRA-mode decision. In [13] , variance values of coding-mode costs are used to terminate the current CU mode decision as well as TU size selection. A two-stage process has been reported in [14] , where in the first stage texture complexity of different CUs are analyzed, followed by an elimination process for small prediction unit candidates for current blocks in INTRA mode. In [15] , a coarse INTRA-mode decision algorithm is applied by first using the Hadamard transform. Then, a fine refinement is done to reduce the complexity of the INTRA-mode decision. A gradient-based approach has been used in [16] for fast INTRA prediction. Apart from that, TU splitting approaches are also used for fast mode decision. In [17] , a residual quadtree mode decision algorithm has been reported by replacing the original depth-first mode decision process by a merge-and-split process. In this paper, we are focusing on CU partitioning to reduce the computational complexity of the CTB structure. Our main objective is to create an algorithm that decides whether a CU should be decomposed into four lower-dimension CUs or not. The proposed approach should terminate the coding tree earlier than conventional standard reference software. The proposed algorithm is based on the RD costs of the parent and current CUs in a CTB. Motion activity and local statistics of the RD cost value are also considered in this context. As we have previously mentioned, there have already been a number of attempts at this problem. However, our proposed technique is simple to implement and robust in nature. Moreover, it is possible to incorporate the proposed technique into other early-CU termination algorithms. In the next section, our proposed approach is discussed in detail. The experimental results are given in section III and finally conclusions are drawn in section IV. As we have discussed in the last section, the CTB which provides the minimum RD cost is considered to be the best for a HEVC encoder. According to this technique, before calculating the RD values of all possible combinations of CTB, it is impossible to take any decision regarding CTU partitioning. Since the main objective is to select the lowest RD cost among all combinations in [4] , it is shown that no further decomposition is required if the CTB satisfy the condition shown in (1), where the subscript t indicates the current level and t +1 indicates the next level However, at depth t , it is not possible to get any information about depth t +1 without splitting the CU. We can only use information from the prior level (depth t −1). In Fig. 2 , the available information is shown for each level of hierarchy in a CTB. Based on this situation, we use the RD cost values of the current depth t and the previous depth ( t −1) levels and propose a ratio function, which is discussed in detail in the next subsection. Let us consider that CU _t−1 was split and four CUs were created, which means (1) is not satisfied. So, we can consider that the RD cost of CU _t−1 is greater than the costs of its child nodes, as shown in (2) The ratio function for a CU_t ( i ) at depth t can be defined as This parameter is basically a ratio of the RD costs of the current CU and its parent CU. When a CU is split, then it will create four child CUs and for each newly created CU, we can define a value for its ratio function. From (3), it can be inferred that this parameter should have some upper limit, since the sum of the ratio function has an upper bound of 1. It is also observed that when the ratio function of a child is lower than its siblings, then in the next level it has a low chance of splitting. To justify our theoretical approach and to make an upper bound for the ratio function, we have performed an experiment on HM reference software for four sequences of different dimensions. In this experiment, we have checked the ratio functions for all encoded CUs for four quantization parameter (QP) values, which have been split. According to our experimental result, all the split CUs have a ratio function below 0.25, as shown in Fig. 3 . That means if a child has an RD cost that is less than one quarter of its parent, then at the next level it has a low chance of splitting. Moreover, to make this decision, we do not need any information from depth t +1. Therefore, this parameter can be used as a threshold for making the decision to split a current CU in the next level. In our proposed algorithm, we have incorporated the ratio function for different motion activities in a video sequence. The details of the motion activity are discussed in the next subsection. A CU is consisted of two basic units: PU and TU. All prediction-related calculations and algorithms are under the umbrella of PU. There are three kinds of predictions possible in HEVC. These are SKIP, INTRA and INTER mode, predictions. However, in SKIP mode, there is no need to encode a CU at all — it can be predicted directly from the reference frame. Generally, homogeneous and motionless regions are encoded as SKIP mode. According to the ECU algorithm [3] , if a CU is coded as SKIP mode then no further splitting of that CU is required. Motivated by this fact, in this work, we have explored other prediction modes of PU. As shown in Fig. 4 , INTER and INTRA predictions have different kinds of PU modes. In HEVC encoders, SKIP mode is calculated first, followed by INTER and INTRA modes. The RD values for all kinds of modes for both INTER and INTRA (as shown in Fig. 4 ) are calculated in HEVC encoders to get the best PU mode. After the completion of all mode calculations, the CU is divided into four CUs of lower dimensions. PU mode calculations of each child CU are done recursively. Generally, complex motion and rich-texture regions are encoded as low dimension INTER or INTRA PU modes. We have classified all the prediction modes according to motion activity ( Table 1 ). However, to classify the prediction modes into different motion activities is not a new concept. This kind of motion activity was explored to a greater extent in the H.264/AVC-based codec system [18] – [20] . In this work, we have classified the PU modes into four motion activities: motionless region, slow-moving region, moderate motion–based region, and complex motion or texture-based region. In Table 1 , our classified motion activity and the corresponding PU modes are shown. This is basically a labeling of the PU dimension, which incorporates negligible computational complexity of the overall process [21] . However, we have defined a parameter named as PU-mode weighting factor (PU_WF). This parameter simply represents each group of motion activity–based PU modes, as shown in Table 1 . We have assumed that if a region in a video sequence has relatively slow motion activity compared to other regions, then there is a high chance that the slow-moving region will not split in that hierarchy of the CTB. Motivated by this concept, we have performed an experiment to show as a percentage the number of non-splits of a CU at any level of hierarchy in a CTB. In this experiment, we have tested four sequences with different resolutions for four QP values and observed the CUs which are not split for different PU_WFs. The test sequences have a moderate amount of motion throughout the sequence. The first few frames (20 frames) are considered in this experiment. The result of this experiment is shown in Table 2 . In this table, the average of four QP values for each sequence is given. Form this table, it is clear that when PU_WF is 0 (SKIP mode), then there is a very high chance that the CU will not split at the next level. Hence, if PU_WF is 0, then we can directly say that there is no need to split the CU, which is basically the ECU algorithm [3] . On the other hand, if PU_WF is 1 or 2, then there is a significant chance that the CU will not split in the next level. However, the average percentage of non-splitting CUs ranges from 40% to 60%. Hence, it will be not wise to directly make any decision about the splitting of a CU without further investigation. But in this stage, we can at least be confident that a CU with PU_WF of 1 or 2 has a relatively high chance of not splitting at the next level. Finally, for the last group, from this experiment, we can say that it has quite a high chance of splitting at the next level. As we have mentioned in the previous subsection, we need to investigate further CUs that have a PU_WF of 1 or 2. We have calculated a local average of the RD cost values of all encoded CUs. This parameter is not a static value as it takes the values dynamically from the encoded CUs. In this process, after encoding a CU, the final PU mode and the corresponding RD cost values are checked. A running average is calculated for the final RD cost value. The calculation procedure for the local average is shown in Fig. 5 as a flow chart. This parameter is basically a running average of the RD cost values of different dimension of CUs and the corresponding PU_WFs. This average can be calculated using equations (5) and (6) We have performed an experiment to calculate the probability of a non-splitting CU when the RD cost of the CU is less than its local average RD cost. The result is shown in Table 3. It is clear that for PU_WF values of 0, 1 and 2, the probability is within 65% to 75%. In this experiment, we have used four sequences with different resolutions. An absolute motion vector (MV) is also calculated in our algorithm. This is basically an average of the MVs from both List_0 and List_1 in the HM reference software. To simplify the calculation of the absolute MV, we only use the magnitudes of the x- and y-MV direction, as shown in (7) In this context, we have assumed that a CU with low motion should have a high chance of not splitting. Since the MV_abs is directly related to the motion of a CU, we can infer that a CU with a low MV_abs value has a high chance of not splitting in the current hierarchy of the CTB. To justify our assumption, we have performed another experiment in the same environment as discussed in section II, subsection 2. In this experiment, we have checked the percentage of CUs which are not split for different values of MV_abs . The result is shown in Table 4 . From this table, it is clear that for MV_abs = 0, there is quite a high chance that the corresponding CU will not split. For this reason, we have included this condition when checking for the chance of a CU splitting. Since the probability of a non-split is not so high (65% to 75%), we cannot take any straightforward decision regarding features like avg_d^wf or MV_abs (see Tables 3 and 4 ). Hence, we need to combine this with other features in our main algorithm.