Method and device for intra prediction of video

TECHNICAL FIELD OF THE INVENTION

2The present invention relates to a method of internal video prediction, and more particularly to a method and an internal video prediction apparatus that involves replacing an adjacent pixel not available in a limited internal prediction mode in which the use of an adjacent pixel is limited and using the replaced adjacent pixel as a reference pixel.

BACKGROUND OF THE INVENTION

4In an image compression method, such as the MPEG-1, MPEG-2, MPEG-4, or H.264 / MPEG-4 Advanced Video Encoding (AVC) standard, the video frame is divided into macroblocks for execution encoding the image. Each of the macroblocks is encoded using all coding modes that can be used in external (inter-) prediction or intra-prediction, and then encoded using an encoding mode that is selected according to the data rate used to encode the macroblock , and the degree of distortion between the decoded macroblock and the original macroblock.

5As the hardware for reproducing and storing high-resolution video content or high quality is developed and implemented, there is an increasing need for a video codec capable of efficiently encoding or decoding high-resolution video content or high quality. In the conventional video codec, the video is encoded in macroblock units, each of which has predetermined dimensions.

DETAILED DESCRIPTION OF THE INVENTION

TECHNICAL PROBLEM

8The present invention provides a method for replacing an adjacent pixel not available in a constrained internal prediction mode in which the use of an adjacent pixel used in internal prediction is limited.

TECHNICAL SOLUTION

10The video internal prediction method determines the availability of a predetermined number of adjacent pixels used for internal prediction if there is an inaccessible first adjacent pixel searching for a second adjacent pixel that is accessible by performing a search in a predetermined number of adjacent pixels in a predetermined direction based on the first adjacent pixel , and replaces the pixel value of the first adjacent pixel by the pixel value of the found V the adjacent pixel. For an inaccessible third adjacent pixel, the replacement process is performed by using an adjacent pixel in a predetermined direction.

FAVORABLE EFFECTS

12According to one or more embodiments of the present invention, the complexity of the determination process of the reference pixel used for internal prediction can be reduced by performing a search and replacing an available adjacent pixel, based on a predetermined search direction, by an inaccessible adjacent pixel.

DESCRIPTION OF THE DRAWINGS

14FIG. 1 is a block diagram of a video encoding device according to an embodiment of the present invention;

15FIG. 2 is a block diagram of a video decoding device according to an embodiment of the present invention;

16FIG. 3 is a diagram for describing the concept of the coding units according to an embodiment of the present invention;

17FIG. 4 is a block diagram of an image encoder based on the encoding units according to an embodiment of the present invention;

18FIG. 5 is a block diagram of an image decoder based on the encoding units according to an embodiment of the present invention;

19FIG. 6 is a diagram illustrating deeper coding units in accordance with depths and sections according to an embodiment of the present invention;

20FIG. 7 is a diagram for describing the relationship between a coding unit and conversion units according to an embodiment of the present invention;

21FIG. 8 is a diagram for describing coding information of coding units corresponding to the coded depth according to an embodiment of the present invention;

22FIG. 9 is a diagram of deeper coding units corresponding to depths according to an embodiment of the present invention;

23FIG. 10-12 are diagrams for describing the relationship between coding units, prediction units and conversion units according to an embodiment of the present invention;

24FIG. 13 is a diagram for describing the relationship between a coding unit, a prediction unit or a section, and a conversion unit according to the coding mode information from Table 1;

25FIG. 14 is a table illustrating a number of internal prediction modes in accordance with the size of the prediction unit according to an embodiment of the present invention;

26FIG. 15 illustrates a reference schematic for describing intra-prediction modes having different directions, according to an embodiment of the present invention;

27FIG. 16 is a diagram for describing the relationship between a current pixel and adjacent pixels located on a remote line having a directionality (dx, dy) according to an embodiment of the present invention;

28FIG. 17 and 18 are diagrams depicting directions of an internal prediction mode according to embodiments of the present invention;

29FIG. 19 is a diagram showing directions of an internal prediction mode having a directivity 33 according to an embodiment of the present invention;

30FIG. 20 is a diagram of an adjacent pixel that is not available during the internal prediction of the current block according to the type of the adjacent block, according to an embodiment of the present invention;

31FIG. 21 is a diagram for describing the replacement process of an inaccessible adjacent pixel according to an embodiment of the present invention;

32FIG. 22 is a diagram for describing a process for replacing an inaccessible adjacent pixel according to another embodiment of the present invention;

33FIG. 23 is a diagram for describing a process for replacing an inaccessible adjacent pixel according to another embodiment of the present invention;

34FIG. 24 is a block diagram of an internal prediction device according to an embodiment of the present invention;

35FIG. 25A is a diagram of a filtered adjacent pixel of the current block;

36FIG. 25B illustrates a reference schematic for describing the process of filtering an adjacent pixel of the current block;

37FIG. 26 is a flowchart illustrating an internal video prediction method according to an embodiment of the present invention;

38FIG. 27A illustrates a physical structure of a disc on which a program according to an embodiment of the present invention is stored;

39FIG. 27B illustrates a drive that writes and reads a program by using a disc;

40FIG. 28 illustrates the entire structure of a content delivery system that provides a content distribution service;

41FIG. 29 and 30 illustrate external and internal mobile phone designs to which the video encoding method and video decoding method are applied according to an embodiment of the present invention;

42FIG. 31 illustrates a digital broadcast system using a communication system according to an embodiment of the present invention; and

43FIG. 32 illustrates a network structure of a cloud computing system using a video encoding apparatus and a video decoding apparatus according to an embodiment of the present invention.

BEST MODE FOR CARRYING OUT THE INVENTION

45In accordance with an aspect of the present invention, an internal video prediction method is provided, the method comprising the steps of: determining the availability of a predetermined number of adjacent pixels used for internal prediction of the current block of the number of blocks obtained by dividing the video frame forming the video according to a hierarchical structure; if the first adjacent pixel is not available in a predetermined number of adjacent pixels, a second adjacent pixel is searched for, which is available by performing a search in a predetermined number of adjacent pixels in a predetermined direction based on the first adjacent pixel; replacing the pixel value of the first adjacent pixel with the pixel value of the found second adjacent pixel;

46The availability definition includes the steps of determining adjacent pixels that are included in an adjacent block that is external predicted or that belongs to a slice other than the slice to which the current block belongs as inaccessible.

47The first adjacent pixel may be a pixel in a predetermined position from among a predetermined number of adjacent pixels and the search for the second contiguous pixel may comprise determining an available adjacent pixel that was originally found by performing the search in a predetermined number of adjacent pixels in a predetermined direction based on the first adjacent pixel, as a second adjacent pixel.

48The first adjacent pixel may be an adjacent pixel located at the upper left corner of the current block and the search for the second adjacent pixel may comprise the steps of searching for a second adjacent pixel by searching in adjacent pixels from above and from above to the right of the current block from left to right based on the first adjacent pixel pixel, and if the second adjacent pixel is not available in the adjacent pixels from above and from above to the right of the current block, a search is performed in adjacent pixels on the left and below to the left of the current block from top to bottom on the bases the first adjacent pixel.

49The first adjacent pixel may be an adjacent pixel positioned at the upper left corner of the current block and the search for the second adjacent pixel may comprise the steps of searching for a second adjacent pixel by performing a search in adjacent pixels on the left and bottom to the left of the current block from top to bottom based on the first adjacent pixel, and if the second adjacent pixel is not available in adjacent pixels to the left and below to the left of the current block, a search is performed in adjacent pixels from above and from above to the right of the current block from left to right and based on a first adjacent pixel.

50The first adjacent pixel may be an adjacent pixel located at the upper left corner of the current block and the search for the second adjacent pixel may comprise the steps of determining an available adjacent pixel to the left by performing a search in adjacent pixels to the left and bottom to the left of the current block from top to bottom based on the first and determining an available adjacent pixel from above by performing a search in adjacent pixels from above and top to the right of the current block from left to right based on the first adjacent pixel; and replacing the pixel value of the first adjacent pixel by using the average of the available adjacent pixel on the left and the available adjacent pixel from above.

51The first adjacent pixel may be an adjacent pixel located at the upper left corner of the current block and the search for the second adjacent pixel may comprise the steps of determining an available adjacent pixel to the left by performing a search in adjacent pixels to the left and bottom to the left of the current block from top to bottom based on the first of an adjacent pixel, an available adjacent pixel is determined from above by performing a search in adjacent pixels from above and from above to the right of the current block from left to right based on the first adjacent pixel, an adjacent pixel is located that is closest to the first adjacent pixel from among the found adjacent pixels on the left and from above as a second adjacent pixel.

52The first adjacent pixel may be an adjacent pixel to the left at the very bottom of the number of adjacent pixels on the left and below to the left of the current block, and the search for the second contiguous pixel may comprise the steps of searching for the second contiguous pixel by performing a search in adjacent pixels to the left and bottom to the left of of the current block from the bottom up based on the first adjacent pixel, and if the second adjacent pixel is not available in adjacent pixels on the left and below to the left of the current block, a search is performed in adjacent pixels at the top and top to the right of m from the left to the right.

53The first adjacent pixel may be an adjacent pixel to the far right of the top of the number of adjacent pixels on top and top to the right of the current block, and searching for the second contiguous pixel may comprise searching for a second contiguous pixel by performing searches in adjacent pixels on top and top to the right of the current block from the right to the left based on the first adjacent pixel, and if the second adjacent pixel is not available in the adjacent pixels from above and from above to the right of the current block, then searching in adjacent pixels on the left and lower To the left of the current block, from top to bottom.

54The method may further comprise, in the case of the inaccessibility of at least one third adjacent pixel, the step of replacing the pixel value of said at least one third adjacent pixel with the pixel value of the adjacent pixel found previously based on the predetermined direction.

55The first adjacent pixel may be an adjacent pixel located at the upper left corner of the current block and if said at least one third adjacent pixel is located on top of the current block, the method may further comprise the steps of successively replacing said at least one third adjacent a pixel from the third adjacent pixel of the leftmost adjacent pixel to the left of said at least one third adjacent pixel, and if said at least one third adjacent peak the village is located to the left of the current block, then said at least one third adjacent pixel is successively replaced from the third adjacent pixel of the uppermost by an adjacent pixel above said at least one third adjacent pixel.

56The first adjacent pixel may be an adjacent pixel located at the very bottom-left corner of the current block and if said at least one third adjacent pixel is located to the left of the current block, the method may further comprise the steps of successively replacing said at least one third an adjacent pixel beginning with a third adjacent pixel from the bottom bottom, an adjacent pixel below said at least one third adjacent pixel, and if said at least one third adjacent peak the village is located on top of the current block, then successively replacing said at least one third adjacent pixel from the third adjacent pixel to the leftmost adjacent pixel to the left of said at least one third adjacent pixel.

57The first adjacent pixel may be an adjacent pixel located at the uppermost right corner of the current block and if said at least one third adjacent pixel is located on top of the current block, the method may further comprise the steps of successively replacing said at least one third an adjacent pixel from the third adjacent pixel to the right of the adjacent pixel to the right of the at least one third adjacent pixel, and if at least one third adjacent pixel is located wed to the left of the current block, then successively replacing said at least one third adjacent pixel beginning with the third adjacent pixel from the top by an adjacent pixel above said at least one third adjacent pixel.

58The method may further comprise replacing the pixel value of the first adjacent pixel with a predetermined value if the second adjacent pixel does not exist in a predetermined number of adjacent pixels.

59A predetermined value can be determined based on the bit depth of the pixel.

60According to another aspect of the present invention, there is provided an apparatus for internal video prediction, the device comprises: an accessibility determinator for determining the availability of a predetermined number of adjacent pixels used for internal prediction of the current block of the number of blocks obtained by dividing the video frame forming the video according to a hierarchical structure; a replacement means for performing if the first adjacent pixel is unavailable in a predetermined number of adjacent pixels, searching for a second contiguous pixel that is accessible by searching a predetermined number of adjacent pixels in a predetermined direction based on the first adjacent pixel, and replacing the pixel value of the first adjacent pixel with the pixel value of the found second adjacent pixel; and means for performing an internal prediction for performing an internal prediction with respect to the current block by using a predetermined number of adjacent pixels containing the replaced first adjacent pixel.

DETAILED DESCRIPTION OF THE INVENTION

62Hereinafter, the present invention will be more fully described with reference to the accompanying drawings, which illustrate exemplary embodiments of the invention.

63FIG. 1 is a block diagram of a video encoding device 100 according to an embodiment of the present invention.

64The video encoding device 100 includes a partitioning means 110 for maximum coding units, a coding unit determiner 120, and an output unit 130.

65The partitioning engine 110 for the maximum coding units can split the current video frame based on the maximum coding unit for the current video frame of the image. If the current video frame is larger than the maximum coding unit, then the image data of the current video frame can be divided into at least one maximum coding unit. The maximum coding unit according to an embodiment of the present invention may be a data unit having a size of 32x32, 64x64, 128x128, 256x256, etc., wherein the data unit form is a square having a width and a length in squares 2. The image data may be are output to the encoding determiner 120 in accordance with at least one maximum unit of encoding.

66The encoding unit according to an embodiment of the present invention can be characterized by a maximum size and depth. Depth means the number of times the coding unit is spatially divided from the maximum coding unit, and as the depth increases, deeper coding units in accordance with the depths can be split from the maximum coding unit to the minimum coding unit. The depth of the maximum coding unit is the highest depth, and the depth of the minimum coding unit is the lowest depth. Since the size of the coding unit corresponding to each depth decreases as the depth of the maximum coding unit increases, the coding unit corresponding to the upper depth can include a plurality of coding units,

67As described above, the image data of the current video frame is divided into maximum coding units according to the maximum encoding unit size, and each of the maximum coding units may include deeper coding units that are obtained by partitioning according to the depths. Since the maximum coding unit according to an embodiment of the present invention is decomposed in accordance with the depths, the image data of the spatial region included in the maximum coding unit can be hierarchically classified according to the depths.

68The maximum depth and maximum size of the coding unit that limit the total number of times that the height and width of the maximum coding unit is hierarchically broken can be predefined.

69The coding unit determiner 120 encodes the at least one decomposition region obtained by dividing the region of the maximum coding unit in accordance with the depths and determines the depth for output of the finally encoded image data in accordance with at least one partitioning region. In other words, the encoding unit determiner 120 determines the encoded depth by encoding the image data to deeper coding units, in accordance with the depths, according to the maximum unit of encoding of the current video frame, and selects the depth having the smallest encoding error. A particular encoded depth and encoded image data in accordance with a particular encoded depth are output to the output unit 130.

70The image data in the maximum coding unit is encoded based on deeper coding units corresponding to at least one depth equal to or below the maximum depth, and the results of encoding the image data are compared based on each of the deeper coding units. The depth having the lowest encoding error can be selected after comparing the encoding errors of the deeper coding units. At least one coded depth can be selected for each maximum coding unit.

71The size of the maximum coding unit is broken up as the hierarchical coding unit is decomposed in accordance with the depths and as the number of coding units increases. Moreover, even if the coding units correspond to the same depth in one maximum coding unit, it is determined whether each of the coding units corresponding to the same depth is divided to a lower depth by measuring the coding error of the image data of each coding unit, by isolation. Accordingly, even if the image data is included in one maximum coding unit, the coding errors can vary according to the regions in one maximum coding unit, and therefore the coded depths can vary according to the areas in the image data. FROMAccordingly, one or more of the encoded depths may be defined in one maximum coding unit and the image data of the maximum coding unit may be divided according to the coding units of the at least one coded depth.

72Accordingly, the coding unit determiner 120 can determine the coding units having a tree structure included in the maximum coding unit. "Coding units having a tree structure" according to an embodiment of the present invention include coding units corresponding to the depth defined as the coded depth from among all deeper coding units included in the maximum coding unit. The encoding unit of the encoded depth can be determined hierarchically in accordance with the depths in the same area of ​​the maximum coding unit, and can be determined independently in different areas. Similarly, the encoded depth in the current region can be determined regardless of the encoded depth in another area.

73The maximum depth according to an embodiment of the present invention is an index associated with the number of partitions from the maximum coding unit to the minimum coding unit. The first maximum depth according to an embodiment of the present invention can mean the total number of partitions from the maximum coding unit to the minimum coding unit. The second maximum depth according to an embodiment of the present invention can mean the total number of depth levels from the maximum coding unit to the minimum coding unit. For example, if the depth of the maximum coding unit is 0, then the depth of the coding unit, in which the maximum coding unit is divided once, can be set to 1, and the depth of the coding unit,

74Prediction coding and conversion can be performed in accordance with the maximum unit of encoding. Prediction coding and conversion are also performed based on deeper coding units in accordance with a depth equal to or depths lower than the maximum depth, in accordance with the maximum coding unit.

75Since the number of deeper coding units increases each time the maximum coding unit is partitioned according to the depths, encoding including predictive coding and conversion is performed for all deeper coding units generated as the depth increases. For the convenience of the description, predictive coding and conversion will now be described based on the unit of encoding the current depth in the maximum coding unit.

76The video encoding device 100 can differently select the size or shape of the data unit to encode the image data. To perform encoding of image data, operations such as predictive coding, conversion, and entropy encoding are performed, and at the same time, the same data unit can be used for all operations, or different data units can be used for each operation .

77For example, the video encoding device 100 can select not only the encoding unit to perform the encoding of the image data, but also the data unit other than the coding unit in order to perform prediction coding with respect to the image data in the coding unit.

78To perform predictive coding in the maximum coding unit, prediction coding can be performed based on the coding unit corresponding to the coded depth, i.e., based on the coding unit that is no longer partitioned to coding units corresponding to the lower depth. Further in this document, the coding unit that is no longer partitioned and becomes the basic unit for predictive coding will now be referred to as the "prediction unit". The partition obtained by dividing the prediction unit may include a prediction unit or a data unit obtained by partitioning at least one of the height and width of the prediction unit.

79For example, if the 2Nx2N coding unit (where N is a positive integer) is no longer partitioned and becomes a 2Nx2N prediction unit, the partition size can be 2Nx2N, 2NxN, Nx2N or NxN. Partition type examples include symmetric sections that are obtained by symmetrically dividing the height or width of the prediction unit, sections obtained by asymmetric height division or the width of the prediction unit, such as 1: n or n: 1, the sections that are obtained by means of a geometric partition prediction units, and sections having arbitrary forms.

80The prediction unit prediction mode can be at least one of the internal (intra) mode, the external (inter-) mode, and the skip mode. For example, the internal mode or external mode can be performed for partitions 2Nx2N, 2NxN, Nx2N or NxN. In addition, the skip mode can only be performed with respect to section 2Nx2N. The encoding is performed independently with respect to one prediction unit in the coding unit, thereby selecting a prediction mode having the smallest coding error.

81The video encoding device 100 can also perform conversion with respect to the image data in the coding unit, not only based on the coding unit for encoding the image data, but also on the basis of a data unit that is different from the coding unit.

82To perform the conversion in the coding unit, the conversion may be performed based on a data unit having a size less than or equal to the coding unit. For example, the data unit for the conversion may include a data unit for the internal mode and a data unit for the external mode.

83The unit of data used as the basis for the transformation will now be called the "conversion unit". Like the coding unit, the conversion unit in the coding unit can be recursively divided into smaller areas so that the conversion unit can be determined independently in units of areas. Thus, the residual data in the coding unit can be divided according to a unit of transformation having a tree structure in accordance with the conversion depths.

84The conversion depth indicating the number of partitions to achieve the conversion unit by performing the height division and the width of the coding unit can also be set in the conversion unit. For example, in the current 2Nx2N encoding unit, the conversion depth can be 0 if the conversion unit size is 2Nx2N, can be 1 if, respectively, the conversion unit size is NxN, and can be 2 if, respectively, the conversion unit size is N / 2xN / 2. In other words, a unit of transformation having a tree structure can be set according to the depths of the transformation.

85The encoding information according to the coding units corresponding to the encoded depth requires not only information about the encoded depth, but also information related to prediction and conversion coding. Accordingly, the encoding unit determiner 120 not only determines the encoded depth having the smallest encoding error, but also determines the type of partition in the prediction unit, the prediction mode in accordance with prediction units, and the conversion unit size for performing the conversion.

86Next, with reference to FIG. 3-12, the coding units according to the tree structure in the maximum coding unit and the partition determination method according to embodiments of the present invention will be described in detail.

87The coding unit determiner 120 can measure the coding error of the deeper coding units according to the depths by using the Distortion Optimization, depending on the Transmission Rate, based on Lagrange multipliers.

88The output unit 130 outputs image data of the maximum encoding unit that are encoded based on the at least one encoded depth determined by the encoding unit determiner 120 and the encoding mode information according to the encoded depth in the bitstreams.

89The encoded image data can be obtained by encoding the residual image data.

90The information on the encoding mode in accordance with the encoded depth can include information about the encoded depth, the type of partition in the prediction unit, the prediction mode, and the conversion unit size.

91The encoded depth information can be determined by using the depth-based partitioning information, which indicates whether encoding with respect to the lower-depth encoding units is performed, instead of the current depth. If the current depth of the current encoding unit is the encoded depth, then the image data is encoded and output in the current encoding unit, and thus, the partitioning information can be set so as not to break the current encoding unit to a lower depth. Alternatively, if the current depth of the current coding unit is not the depth coded, the coding is performed with respect to the lower-depth coding unit, and thus, the culling information can be set so that,

92If the current depth is not a depth encoded, then the encoding is performed with respect to the coding unit, which is divided into a coding unit with a lower depth. Since there is at least one lower-depth encoding unit in one current-depth encoding unit, the encoding is repeated with respect to each lower-depth encoding unit, and thus, recursive encoding can be performed for encoding units having the same depth .

93Since coding units having a tree structure are defined for one maximum coding unit and information on at least one coding mode is defined for the coding unit of the encoded depth, information on at least one coding mode can be determined for one maximum coding unit. In addition, the encoded depth of the image data of the maximum coding unit may be different in accordance with the provisions, since the image data is hierarchically partitioned according to the depths, and thus, the encoded depth and coding mode information can be set for the image data.

94Accordingly, the output unit 130 can assign coding information about the corresponding encoding depth and coding mode to at least one of the coding unit, the prediction unit, and the minimum unit included in the maximum coding unit.

95The minimum unit according to an embodiment of the present invention is a unit of square shape data obtained by dividing the minimum coding unit constituting the lowest depth by 4. Alternatively, the minimum unit can be the maximum unit of square shape data that can be included in all units coding, prediction units, unit units and conversion units included in the maximum coding unit.

96For example, the encoding information outputted through the output unit 130 can be classified into coding information according to the coding units and coding information according to the prediction units. The encoding information according to the coding units can include information about the prediction mode and the size of the partitions. The encoding information according to the prediction units can include information about the estimated outer-mode direction, the external-mode reference image index, the motion vector, the internal-mode chrominance component, and the internal mode interpolation method. In addition, information on the maximum encoding unit size specified in accordance with video frames, slices or GOP (video frame groups), and maximum depth information,

97In the video encoding device 100, the deeper coding unit may be a unit of coding obtained by dividing by two heights or the width of a higher-depth coding unit that is one level higher. In other words, if the coding unit's size of the current depth is 2Nx2N, then the coding unit size with the lower depth is NxN. In addition, the current depth coding unit having a size of 2 N × 2 N can include a maximum of 4 coding units with a lower depth.

98Accordingly, the video encoding device 100 can generate coding units having a tree structure by determining the coding units having the optimal shape and the optimal size for each maximum coding unit based on the size of the maximum coding unit and the maximum depth determined according to the characteristics of the current video frame. In addition, since the coding can be performed for each maximum coding unit by using any of various prediction and transformation modes, the optimal coding mode can be determined taking into account the characteristics of a coding unit of different image sizes.

99Thus, if the image has a high resolution or a large amount of data is encoded in a conventional macroblock, then the number of macroblocks in the video frame is excessively increased. Accordingly, the number of pieces of compressed information generated for each macroblock is increased, and thus it is difficult to transmit the compressed information, and the data compression efficiency is reduced. However, by using the video encoding device 100, the image compression efficiency can be increased, since the coding unit is adjusted according to the characteristics of the image, while simultaneously increasing the maximum coding unit size taking into account the image size.

100FIG. 2 is a block diagram of a video decoding device 200 in accordance with an embodiment of the present invention.

101The video decoding apparatus 200 includes a receiver 210, an image data and coding information extracting means 220, and an image data decoder 230. The definitions of various terms such as the coding unit, depth, prediction unit, conversion unit, and information on the different coding modes for the various operations of the video decoding apparatus 200 are identical to those described with reference to FIG. 1 and the video encoding device 100.

102The receiver 210 receives and parses the bit stream of the encoded video. The image data extraction means 220 and the coding information extract the encoded image data for each coding unit from the syntactically analyzed bit stream, the coding units having a tree structure according to each maximum coding unit, and outputs the extracted image data to the image data decoder 230. The image data extraction means 220 and the encoding information can extract the maximum encoding unit size of the current video frame from the title of the current video frame.

103In addition, the image data extraction and coding information extracting means 220 extracts the encoded depth and coding mode information for the coding units having the tree structure in accordance with each maximum coding unit from the syntactically analyzed bitstream. The extracted information on the encoded depth and the encoding mode is output to the image data decoder 230. In other words, the image data in the bitstream is divided into a maximum coding unit such that the image data decoder 230 performs image data decoding for each maximum coding unit.

104The encoded depth and coding mode information in accordance with the maximum coding unit can be set for information on at least one coding unit corresponding to the coded depth and the coding mode information can include information on the type of a section of the corresponding coding unit corresponding to the coded depth , about the prediction mode and the size of the conversion unit. In addition, the partitioning information in accordance with the depths can be extracted as information on the encoded depth.

105The encoded depth and coding mode information according to each maximum coding unit extracted by the image data extracting means 220 and the coding information is the encoded depth and coding mode information determined to generate the minimum coding error when the encoder such as the video coding device 100 , re-encodes with respect to each deeper coding unit in accordance with the depths, according to each maximum unit of ko dication. Accordingly, the video decoding device 200 can reconstruct the image by decoding the image data in accordance with the encoded depth and the encoding mode that generates the minimum encoding error.

106Since the coding information regarding the encoded depth and the coding mode can be assigned to a predetermined data unit from the number of the corresponding coding unit, the prediction unit and the minimum unit, the image data extraction means 220 and the coding information can extract the coded depth and coding mode information according to the predetermined units data. If information about the encoded depth and coding mode of the corresponding maximum coding unit is recorded in accordance with the predetermined data units, then the predetermined data units assigned the same information about the encoded depth and coding mode can be output as data units included in the composition of the same maximum coding unit.

107The image data decoder 230 reconstructs the current video frame by decoding the image data in each maximum coding unit based on the encoded depth information and the coding mode in accordance with the maximum coding units. In other words, the image data decoder 230 can decode the encoded image data based on the extracted section type information, the prediction mode, and the conversion unit for each coding unit from the number of coding units having a tree structure included in each maximum coding unit. The decoding process may include a prediction including internal prediction and motion compensation, and an inverse transformation.

108The image data decoder 230 can perform internal prediction or motion compensation in accordance with the prediction mode and the section of each coding unit based on the type information of the section and the prediction mode of the coding unit prediction unit according to the coded depths.

109In addition, the image data decoder 230 can perform an inverse transform according to each conversion unit in the coding unit based on the unit size information of the coding unit conversion unit according to the coded depths so as to perform the inverse transformation in accordance with the maximum coding units.

110The image data decoder 230 can determine the at least one encoded depth of the current maximum coding unit by using the partition information in accordance with the depths. If the split information indicates that the image data is no longer being decomposed at the current depth, then the current depth is the encoded depth. Accordingly, the image data decoder 230 can decode the encoded data of at least one coding unit corresponding to each coded depth in the current maximum coding unit by using the type information of the prediction unit section, the prediction mode, and the conversion unit size for each coding unit corresponding to the coded depth.

111In other words, data units containing encoding information including the same partitioning information can be collected by examining a set of coding information assigned to a predetermined data unit from the number of the coding unit, the prediction unit and the minimum unit, and the collected data units may be considered as one data unit to be decoded by the image data decoder 230 in the same encoding mode.

112The video decoding apparatus 200 can obtain information about at least one coding unit that generates a minimum coding error when recursive coding is performed for each maximum coding unit and can use the information to decode the current video frame. In other words, the coding units having a tree structure defined as optimal coding units in each maximum coding unit can be decoded.

113Accordingly, even if the image data has a high resolution and a large amount of data, the image data can be efficiently decoded and restored by using a coding unit size and a coding mode that are determined adaptively in accordance with the characteristics of the image data by using the optimal coding mode information received from the encoder.

114Now, with reference to FIG. 3-13, a method for determining coding units having a tree structure, a prediction unit and a conversion unit according to an embodiment of the present invention will be described.

115FIG. 3 is a diagram for describing the concept of the coding units according to an embodiment of the present invention.

116The size of the coding unit can be represented as width x height, and can be 64x64, 32x32, 16x16 and 8x8. The 64x64 coding unit can be divided into 64x64, 64x32, 32x64 or 32x32 sections, and the 32x32 coding unit can be divided into 32x32, 32x16, 16x32 or 16x16 sections, the 16x16 coding unit can be partitioned into 16x16, 16x8, 8x16 or 8x8 sections, and The 8x8 coding unit can be divided into 8x8, 8x4, 4x8 or 4x4 sections.

117In the video data 310, the resolution is 1920x1080, the maximum encoding unit size is 64 and the maximum depth is 2. In the video data 320, the resolution is 1920x1080, the maximum encoding unit size is 64, and the maximum depth is 3. In the video data 330, the resolution is 352x288, the maximum coding unit size is 16, and the maximum depth is 1. The maximum depth shown in FIG. 3, denotes the total number of partitions from the maximum coding unit to the minimum decoding unit.

118If the resolution is high, or the amount of data is large, then the maximum coding unit size may be large in order not only to increase the coding efficiency, but also accurately reflect the characteristics of the image. Accordingly, the maximum encoding unit size of the video data 310 and 320 having a higher resolution than the video data 330 can be 64.

119Since the maximum depth of the video data 310 is 2, the video encoding units 315 of the video data 310 can include a maximum coding unit having a long axis size of 64 and coding units having a long axis dimension of 32 and 16, since the depth is increased by two layers by splitting the maximum coding unit twice. In this case, since the maximum depth of the video data 330 is 1, the coding units 335 of the video data 330 can include a maximum coding unit having a long axis size of 16 and coding units having a long axis size of 8, since the depth is increased by one layer by splitting the maximum coding unit once.

120Since the maximum depth of the video data 320 is 3, the video encoding units 325 of the video data 320 can include a maximum coding unit having a size along the long axis 64 and coding units having a long axis dimension of 32, 16 and 8, since the depths are increased by 3 levels by dividing the maximum coding unit three times. As the depth increases, accurate information can be accurately presented.

121FIG. 4 is a block diagram of an image encoder 400 based on encoding units according to an embodiment of the present invention.

122The image encoder 400 performs the operations of the encoding unit determiner 120 from the video encoding device 100 to perform encoding of the image data. In other words, the internal prediction means 410 performs internal prediction with respect to the intra-coding units from the current frame 405, and the motion estimation means 420 and the motion compensator 425 perform external estimation and motion compensation with respect to the coding units in the external mode from the current frame 405 by using the current frame 405 and the reference frame 495.

123The data output from the intra prediction means 410, the motion estimation means 420, and the motion compensator 425 are output as a quantized transform coefficient through the converter 430 and the quantizer 440. The quantized transform coefficient is reconstructed as data in the spatial domain by the inverse quantizer 460 and the inverse transformer 470, and the recovered data in the spatial domain is output as a reference frame 495 after postprocessing by the deblocking unit 480 and the contour filtering unit 490. The quantized transform coefficient can be output as a bitstream 455 through an entropy encoder 450.

124In order for the image encoder 400 to be applied to the video encoder 100, all the elements of the image encoder 400, i.e., the intra prediction means 410, the motion estimation means 420, the motion compensator 425, the transducer 430, the quantizer 440, the entropy encoder 450, the inverse quantizer 460, the inverse transformer 470 , a deblocking unit 480, and a block filtering unit 490, perform operations based on each coding unit from the number of coding units having a tree structure, taking into account the maximum depth of each maximum unit encoding.

125In particular, the means 410, intra prediction means 420 estimates motion compensator 425 motion determines partitions and a prediction mode of each coding unit from among coding units having a tree structure, with the maximum size and the maximum depth of the current maximum coding unit, and the converter 430 determines the size units of conversion in each unit of coding from the number of coding units having a tree structure.

126FIG. 5 is a block diagram of an image decoder 500 based on the encoding units according to an embodiment of the present invention.

127The parser 510 parses the encoded image data to be decoded and the encoding information necessary for decoding from the bitstream 505. The encoded image data is output as back quantized data through the entropy decoder 520 and the inverse quantizer 530, and the inverse quantized the data is restored to the image data in the spatial domain by the inverse transformer 540.

128The internal prediction performing means 550 performs internal prediction with respect to the intra-coding units for the image data in the spatial domain, and the motion compensator 560 performs motion compensation for the coding units in the outer mode by using the reference frame 585.

129The image data in the spatial domain that have passed through the internal prediction means 550 and the motion compensator 560 can be output as a reconstructed frame 595 after performing their post-processing by the deblocking unit 570 and the contour filtering unit 580. In addition, image data that has been post-processed by the deblocking unit 570 and the contour filtering unit 580 can be output as the reference frame 585.

130In order to decode the image data in the image data decoder 230 of the video decoding apparatus 200, the image decoder 500 can perform operations that are performed after the parser 510.

131In order for the video decoder 500 to be applied to the video decoding apparatus 200, all the elements of the image decoder 500, i.e., the parser 510, the entropy decoder 520, the inverse quantizer 530, the inverse transformer 540, the intra prediction means 550, the motion compensator 560, the deblocking unit 570 and a contour filtering unit 580, performing operations based on the coding units having a tree structure for each maximum coding unit.

132In particular, the internal prediction means 550 and the motion compensator 560 perform partition and prediction operations for each of the coding units having a tree structure, and the inverse transformer 540 performs operations based on the conversion unit size for each coding unit.

133FIG. 6 is a diagram illustrating deeper coding units in accordance with depths and sections according to an embodiment of the present invention.

134The video encoder device 100 and the video decoding device 200 use hierarchical coding units to account for the characteristics of the image. The maximum height, maximum width and maximum depth of the coding units can be determined adaptively according to the characteristics of the image, or can be set differently by the user. The dimensions of the deeper coding units in accordance with the depths can be determined in accordance with a predetermined maximum coding unit size.

135In the hierarchical structure 600 of the coding units, according to the embodiment of the present invention, both the maximum height and the maximum width of the coding units are 64, and the maximum depth is 4. Since the depth increases along the vertical axis of the hierarchical structure 600, each of the height and width of the unit encoding greater depth. In addition, the prediction unit and the sections that are the basis for encoding with the prediction of each greater depth coding unit are shown along the horizontal axis of the hierarchical structure 600.

136In other words, the encoding unit 610 is the maximum coding unit in the hierarchical structure 600 in which the depth is 0, and the size, i.e., the height per width, is 64x64. The depth increases along the vertical axis and there is an encoding unit 620 having a size of 32x32 and a depth of 1, a coding unit 630 having a size of 16x16 and a depth of 2, a coding unit 640 having a size of 8x8 and a depth of 3, and a coding unit 650 having a size of 4x4 and depth 4. The encoding unit 650 having a size of 4x4 and a depth of 4 is the minimum unit of encoding.

137The prediction unit and the coding unit sections are arranged along the horizontal axis according to each depth. In other words, if the coding unit 610 having a size of 64x64 and a depth of 0 is a prediction unit, then the prediction unit may be divided into sections included in the coding unit 610, i.e., a 610 having a size of 64x64, sections 612 having a size of 64x32 , sections 614 having a size of 32x64 or sections 616 having a size of 32x32.

138Similarly, the prediction unit of the coding unit 620 having a size of 32x32 and a depth of 1 can be divided into sections included in the coding unit 620, i.e., a section 620 having a size of 32x32, sections 622 having a size of 32x16, sections 624 having size 16x32, and sections 626 having a size of 16x16.

139Similarly, the prediction unit of the coding unit 630 having a size of 16x16 and a depth of 2 can be divided into sections included in the coding unit 630, i.e., a partition having a size of 16x16 included in the coding unit 630, sections 632 having a size 16x8, sections 634 having a size of 8x16, and sections 636 having a size of 8x8.

140Similarly, the prediction unit of the coding unit 640 having a size of 8 × 8 and a depth of 3 can be divided into sections included in the coding unit 640, that is, a section having a size of 8 × 8 included in the coding unit 640, sections 642 having a size of 8x4, sections 644 having a size of 4x8, and sections 646 having a size of 4x4.

141The encoding unit 650 having a size of 4x4 and a depth of 4 is the minimum unit of encoding and the unit of encoding of the lowest depth. The prediction unit of the encoding unit 650 is assigned only to a section having a size of 4x4.

142To determine the at least one encoding depth of the encoding units constituting the maximum encoding unit 610, the encoding unit determiner 120 of the video encoding device 100 performs encoding for the encoding units corresponding to each depth included in the maximum encoding unit 610.

143The number of deeper coding units in accordance with the depths containing data in the same range and the same size increases as the depth increases. For example, four coding units corresponding to a depth of 2 are required to cover the data that is included in the water coding unit corresponding to depth 1. Accordingly, to compare the coding results of the same data in accordance with the depths, coding of each of the coding unit , corresponding to a depth of 1, and four coding units corresponding to a depth of 2.

144To perform encoding for the current depth from among the depths, the smallest encoding error can be selected for the current depth by performing coding for each prediction unit in coding units corresponding to the current depth along the horizontal axis of the hierarchical structure 600. Alternatively, a minimum coding error by comparing the smallest coding errors in accordance with the depths, by performing coding for each depth as the depth along the vertical axis of the hierarchical structure 600. The depth and the section having the minimum encoding error in the coding unit 610 can be selected as the encoding depth and the type of the section of the coding unit 610.

145FIG. 7 is a diagram for describing the relationship between the encoding unit 710 and the conversion units 720 according to an embodiment of the present invention.

146The video encoding device 100 or the video decoding device 200 performs image encoding or decoding according to coding units having equal or smaller sizes than the maximum coding unit for each maximum coding unit. The sizes of the conversion units for performing the conversion during the encoding process can be selected based on data units that are no larger than the corresponding unit of coding.

147For example, in the video encoding device 100 or the video decoding device 200, if the size of the encoding unit 710 is 64x64, the conversion can be performed by using conversion units 720 having a size of 32x32.

148In addition, the data of the encoding unit 710 having a size of 64x64 can be encoded by performing a conversion with respect to each of the conversion units having a size of 32x32, 16x16, 8x8 and 4x4 that is less than 64x64, and then the conversion unit having the smallest error encoding.

149FIG. 8 is a diagram for describing coding information of coding units corresponding to a coded depth, according to an embodiment of the present invention.

150The output unit 130 of the video encoding device 100 can perform encoding and transmission of the section type information 800, prediction mode information 810, and conversion unit size information 820 for each coding unit corresponding to the encoded depth as coding mode information.

151The information 800 indicates the shape information of the partition obtained by dividing the prediction unit of the current coding unit, the partition being a unit of data for coding with the prediction of the current coding unit. For example, the current encoding unit CU_0 having a size of 2Nx2N can be partitioned into any of the section 802 having a size of 2Nx2N, a section 804 having a size of 2NxN, a section 806 having a size of Nx2N, and a section 808 having a size of NxN. In this case, the partition type information 800 is set to indicate one of the section 804 having a size of 2NxN, a section 806 having a size of Nx2N, and a section 808 having a size of NxN.

152The information 810 indicates the prediction mode of each section. For example, the information 810 may indicate a predictive coding mode performed with respect to the section indicated by the information 800, i.e., the internal mode 812, the external mode 814, or the skip mode 816.

153Information 820 indicates the conversion unit on which it is necessary to be based upon performing the conversion with respect to the current coding unit. For example, the conversion unit may be the first internal conversion unit 822, the second internal conversion unit 824, the first external conversion unit 826, or the second external conversion unit 828.

154The image data extraction means 220 and the encoding information of the video decoding apparatus 200 can extract and use the information 800, 810 and 820 to perform the decoding, according to each deeper unit of encoding.

155FIG. 9 is a diagram of deeper coding units in accordance with the depths according to an embodiment of the present invention.

156The split information can be used to indicate the depth change. The split information indicates whether the current-depth coding unit is divided into lower-depth coding units.

157The prediction unit 910 for encoding with prediction of the encoding unit 900 having a depth of 0 and a size of 2N_0x2N_0 can include sections from the partition type 912 having a size of 2N_0x2N_0, a partition type 914 having a size of 2N_0xN_0, a section type 916 having a size of N_0x2N_0, and type 918 of the section having the size N_0xN_0. FIG. 9 illustrates only the partition types 912-918 that are obtained by symmetrically partitioning the prediction unit 910, but the partition type is not limited thereto, and the sections of the prediction unit 910 can include asymmetric sections, sections having a predetermined shape, and sections having a geometric shape .

158The prediction coding is repeated with respect to one partition having a size of 2N_0x2N_0, two partitions having a size of 2N_0xN_0, two sections having a size of N_0x2N_0, and four sections having a size of N_0xN_0, according to each partition type. Encoding with prediction in the internal mode and external mode can be performed for partitions having the sizes 2N_0x2N_0, N_0x2N_0, 2N_0xN_0, and N_0xN_0. Encoding with prediction in skip mode is performed exclusively with respect to the section having the size 2N_0x2N_0.

159If, in one of the partition types 912-916, the encoding error is the smallest, then the prediction unit 910 may not break up to a lower depth.

160If the encoding error is the smallest in the partition type 918, then the depth varies from 0 to 1 to split the partition type 918 in step 920, and the encoding is repeated with respect to the coding units 930 having a depth of 2 and the size N_0xN_0 to perform the search for the minimum encoding error.

161The prediction unit 910 for encoding with the prediction of the coding unit 930 having a depth of 1 and a size of 2N_1x2N_1 (= N_0xN_0) can include partition sections 942 having a size of 2N_1x2N_1, partition type 944 having a size of 2N_1xN_1, partition type 946 having a size N_1x2N_1, and partition type 948 having the size N_1xN_1.

162If the encoding error is the smallest in the partition type 948, then the depth varies from 1 to 2 to perform partitioning of the partition type 948 in step 950 and the encoding is repeated with respect to the coding units 960 that have a depth of 2 and a size of N_2xN_2 to search for the minimum coding error .

163When the maximum depth is d, the decomposition step in accordance with each depth can be performed until the depth becomes d-1, and the partitioning information can be encoded until the depth is one of 0 to d-2. In other words, if the coding is performed before the time when the depth is d-1 after the coding unit corresponding to the depth d-2 is divided in step 970, the prediction unit 990 for coding prediction of the coding unit 980 having a depth of d-1 and the size 2N_ (d-1) x2N_ (d-1) may include sections of partition type 992 having a size of 2N_ (d-1) x2N_ (d-1), partition type 994 having a size of 2N_ (d-1 ) xN_ (d-1), partition type 996 having the size N_ (d-1) x2N_ (d-1), and partition type 998 having the size N_ (d-1) xN_ (d-1).

164The prediction coding may be re-executed with respect to one partition having a size of 2N_ (d-1) x2N_ (d-1), two partitions having a size of 2N_ (d-1) xN_ (d-1), two partitions having a size N_ (d-1) x2N_ (d-1), four partitions having the size N_ (d-1) xN_ (d-1) of the types of 992-998 partitions, to perform a partition type search having a minimum encoding error.

165Even if the partition type 998 has a minimum encoding error, since the maximum depth is d, the coding unit CU_ (d-1) having a depth of d-1 is no longer divided to a lower depth, and the encoding depth for the coding units constituting the current maximum the encoding unit 900 is defined as d-1, and the partition type of the current maximum encoding unit 900 can be defined as N_ (d-1) xN_ (d-1). In addition, since the maximum depth is d, and the minimum coding unit 980 having the lowest depth d-1 is no longer partitioned to a lower depth, the partitioning information for the minimum coding unit 960 is not specified.

166A data unit 999 may be a "minimum unit" for the current maximum coding unit. The minimum unit according to an embodiment of the present invention can be a square-shaped data unit obtained by dividing the minimum unit 960 of the coding by 4. By re-executing the encoding, the video encoding device 100 can select the depth having the smallest encoding error by comparing the encoding errors in accordance with the depths of the coding unit 900 for determining the encoded depth and setting the corresponding section type and the prediction mode in ka ETS coding mode the encoded depth.

167Also, the minimum coding errors in accordance with the depths are compared at all depths from 1 to d, and the depth having the lowest encoding error can be determined as the encoded depth. The encoded depth, the prediction unit section type, and the prediction mode can be encoded and transmitted as encoding mode information. In addition, since the coding unit is partitioned from depth 0 to the encoded depth, only the coding depth depth information is set to 0, and the depth decomposition information, except for the coded depth, is set to 1.

168The image data extraction means 220 and the encoding information of the video decoding apparatus 200 can extract and use the encoded depth information and the prediction unit unit of the encoding unit 900 for decoding the section 912. The video decoding device 200 can determine the depth at which the partitioning information is 0 as the encoded depth by using the decomposition information in accordance with the depths, and use the information of the encoding mode of the corresponding depth for performing decoding IAOD.

169FIG. 10-12 are diagrams for describing the relationship between the encoding units 1010, prediction units 1060, and conversion units 1070 according to an embodiment of the present invention.

170The encoding units 1010 are coding units having a tree structure corresponding to the coding depths determined by the video encoding device 100 in the maximum coding unit. The prediction units 1060 are sections of the prediction units of each of the encoding units 1010, and the conversion units 1070 are the conversion units of each of the encoding units 1010.

171If the depth of the maximum coding unit is 0 in units of 1010 encoding, then the depths of the coding units 1012 and 1054 are 1, the depths of the 1014, 1016, 1018, 1028, 1050 and 1052 coding units are 2, the depths of 1020, 1022, 1024, 1026, 1030 , 1032 and 1048 are 3, and the depths of the encoding units 1040, 1042, 1044 and 1046 are 4.

172In prediction units 1060, some units 1014, 1016, 1022, 1032, 1048, 1050, 1052 and 1054 are obtained by dividing the coding units in encoding units 1010. In other words, the partition types in the encoding units 1014, 1022, 1050 and 1054 are 2NxN, the partition types in the encoding units 1016, 1048 and 1052 are of the Nx2N size, and the type of the section of the encoding unit 1032 is of the NxN size. The prediction units and sections of the coding units 1010 are less than or equal to each coding unit.

173The conversion or inverse transformation is performed with respect to the image data of the encoding unit 1052 in conversion units 1070 in the data unit that is less than the encoding unit 1050. In addition, the encoding units 1014, 1016, 1022, 1032, 1048, 1050 and 1052 in conversion units 1070 are different from the coding units in the prediction units 1060 based on sizes and shapes. In other words, the video encoding and video decoding apparatuses 100 and 200 can perform internal prediction, motion estimation, motion compensation, conversion and inverse transformation separately for a data unit in the same coding unit.

174Accordingly, encoding is performed recursively for each of the coding units having a hierarchical structure in each region of the maximum coding unit to determine the optimal coding unit, and therefore, coding units having a recursive tree structure can be obtained. The encoding information can include coding partition information, partition type information, prediction mode information, and conversion unit size information. Table 1 shows the encoding information that can be set by the video encoding and decoding apparatuses 100 and 200.

175<tables num="1"><table frame="all"><tgroup rowsep="1" colsep="1" cols="6"><colspec colname="c1" colwidth="30mm" /><colspec colname="c2" colwidth="23mm" /><colspec colname="c3" colwidth="25mm" /><colspec colname="c4" colwidth="29mm" /><colspec colname="c5" colwidth="29mm" /><colspec colname="c6" colwidth="30mm" /><tbody><row><entry namest="c1" nameend="c6" align="right" rowsep="1" colsep="0"><b>Table 1</b></entry></row><row><entry namest="c1" nameend="c5" align="center" rowsep="1" colsep="1">Split information 0 (Encoding with respect to a coding unit having a size of 2N × 2 N and a current depth of d)</entry><entry rowsep="1" colsep="0">Information 1 about the division</entry></row><row><entry align="center" rowsep="1" colsep="1">Prediction mode</entry><entry namest="c2" nameend="c3" align="center" rowsep="1" colsep="1">Section type</entry><entry namest="c4" nameend="c5" align="center" rowsep="1" colsep="1">Conversion unit size</entry><entry morerows="2" rowsep="1" colsep="0">Perform re-encoding of the coding units having a lower depth equal to d + 1</entry></row><row><entry morerows="1" rowsep="1" colsep="1">Internal External Pass (Only 2Nx2N)</entry><entry rowsep="1" colsep="1">Symmetric partition type</entry><entry rowsep="1" colsep="1">Timeless section</entry><entry rowsep="1" colsep="1">Information 0 of the partition of the transformation unit</entry><entry rowsep="1" colsep="0">Information 1 partition transformation unit</entry></row><row><entry rowsep="0" colsep="1">2Nx2N 2NxN Nx2N NxN</entry><entry rowsep="0" colsep="1">2NxnU 2NxnD nLx2N nRx2N</entry><entry rowsep="0" colsep="1">2Nx2N</entry><entry rowsep="0" colsep="0">NxN (symmetric type) N / 2xN / 2 (Unsymmetrical type)</entry></row></tbody></tgroup></table></tables>

176The output unit 130 of the video encoding device 100 can output encoding information about the coding units having the tree structure, and the image data extraction means 220 and the encoding information of the video decoding apparatus 200 can extract encoding information about the coding units having the tree structure from the received bitstream.

177The split information indicates whether the current coding unit is divided into lower-depth coding units. If the decomposition information of the current depth d is 0, then the depth at which the current coding unit is no longer divided to a lower depth is the encoded depth, and thus information on the type of the section, the prediction mode, and the unit size can be determined for the encoded depth transformation. If the current coding unit is further partitioned according to the partitioning information, the coding is performed independently with respect to the four coding units of the lower depth obtained by partitioning.

178The prediction mode can be one of the internal mode, external mode and skip mode. The internal mode and external mode can be defined in all partition types, and the skip mode is defined exclusively in the section type having the size 2Nx2N.

179Partition type information can indicate symmetrical partition types having the sizes 2Nx2N, 2NxN, Nx2N and NxN that are obtained by symmetrically dividing the height or width of the prediction unit and asymmetric partition types having the sizes 2NxnU, 2NxnD, nLx2N and nRx2N that are obtained by an asymmetric height division or width of the prediction unit. Asymmetric partition types having sizes 2NxnU and 2NxnD can be obtained, respectively, by dividing the height of the prediction unit in a ratio of 1: 3 and 3: 1, and asymmetric partition types having sizes nLx2N and nRx2N can be obtained respectively by partitioning width of the prediction unit in a ratio of 1: 3 and 3: 1.

180The conversion unit size can be set as two types in the internal mode and two types in the external mode. In other words, if the partitioning information of the conversion unit is 0, then the conversion unit size can be 2Nx2N, which is the size of the current coding unit. If the partition information of the conversion unit is 1, then the conversion units can be obtained by splitting the current coding unit. In addition, if the partition type of the current encoding unit having a size of 2Nx2N is a symmetric partition type, then the conversion unit size may be NxN, and if the partition type of the current encoding unit is an asymmetric partition type, the conversion unit size may be N / 2xN / 2.

181The coding information about coding units having a tree structure may include at least one of a coding unit corresponding to the coded depth, the prediction unit, and the minimum unit. The encoding unit corresponding to the encoded depth may include at least one of a prediction unit and a minimum unit containing the same encoding information.

182Accordingly, it is determined whether adjacent data units are included in the same coding unit corresponding to the coded depth by comparing the coding information of the adjacent data units. In addition, the corresponding coding unit corresponding to the coded depth is determined by using the data unit coding information, and hence, the distribution of the encoded depths in the maximum coding unit can be determined.

183Accordingly, if the prediction of the current coding unit is based on the coding information of the adjacent data units, a direct reference to the coding information of the data units in the deeper coding units adjacent to the current coding unit and its use can be performed.

184Alternatively, if the prediction of the current coding unit is based on the coding information of the adjacent data units, data units adjacent to the current coding unit are searched using the encoded information of the data units, and a reference to the found adjacent coding units can be performed to perform the prediction of the current unit encoding.

185FIG. 13 is a diagram for describing the relationship between a coding unit, a prediction unit or a section, and a conversion unit, in accordance with coding mode information from Table 1.

186The maximum encoding unit 1300 includes the units 1302, 1304, 1306, 1312, 1314, 1316 and 1318 of the encoded depths. In this case, since the encoding unit 1318 is the encoding unit of the encoded depth, the partitioning information can be set to 0. Information on the type of the section of the encoding unit 1318 having a size of 2Nx2N can be specified as one of the partition type 1322 having a size of 2Nx2N, of the type 1324 of a partition having a size of 2NxN, partition type 1326 having a size of Nx2N, partition type 1328 having a size of NxN, partition type 1332 having a size of 2NxnU, partition type 1334 having a size of 2NxnD, partition type 1336 having a size of nLx2N, and type 1338 section having the size nRx2N.

187If the partition type is set to symmetric, i.e., partition type 1322, 1324, 1326 or 1328, then the conversion unit 1342 having a size of 2Nx2N is set if the partitioning information (TU size flag) of the conversion unit is 0, and the conversion unit 1344 having size NxN, is set if the TU size flag is 1.

188If the partition type is specified as asymmetric, that is, partition type 1332, 1334, 1336 or 1338, then the conversion unit 1352 having the size of 2Nx2N is set if the TU size flag is 0, and the N / 2xN / 2 size conversion unit 1354 is set if the TU size flag is 1.

189Hereinafter, an internal prediction will be described in detail with respect to the prediction unit by the intra prediction means 410 of the video encoding device 100 of FIG. 4 and intra prediction means 550 of the video decoding device 200 of FIG. 5.

190The internal prediction means 410 and 550 perform an internal prediction to obtain the prediction value of the current prediction unit by using adjacent pixels of the current prediction unit. Assuming that the prediction unit has a size equal to or greater than 16x16, the intra prediction means 410 and 550 further perform an internal prediction mode having different directions using the parameter (dx, dy), as well as an internal prediction mode having a limited directionality, according to the prior art. Next, an internal prediction mode having various orientations according to an embodiment of the present invention will be described in detail.

191FIG. 14 illustrates a table showing the number of internal prediction modes in accordance with the size of the prediction unit according to an embodiment of the present invention.

192The internal prediction means 410 and 550 can differently determine the number of internal prediction modes to be applied to the prediction unit according to the size of the prediction unit. For example, with reference to FIG. 14, if the size of the prediction unit to be subjected to the internal prediction is NxN, then the number of internal prediction modes actually performed with respect to the prediction units having the dimensions 2x2, 4x4, 8x8, 16x16, 32x32, 64x64 and 128x128 can be determined, respectively, as equal to 5, 9, 9, 17, 33, 5 and 5 in Example 2. The number of actually performed internal prediction modes differs according to the size of the prediction unit, since the overhead for encoding the prediction mode information is different according to the size of the prediction unit. In other words, even though the portion of the prediction unit occupying the entire image is small, the overhead for transmitting additional information, such as the prediction mode of such a small prediction unit, can be large. Accordingly, if the prediction unit having a small size is encoded in many prediction modes, the number of bits may increase, and hence the compression efficiency may decrease. In addition, since a prediction unit having a larger size, for example, a prediction unit having a size greater than or equal to 64x64, is generally selected as the unit of prediction of the planar image region, may not be sufficient in the context of the compression efficiency for encoding a prediction unit having a large size that is generally selected to perform a flat area coding in many prediction modes. Accordingly, if the size of the prediction unit is too large or too small, compared to a predetermined size, a relatively small number of internal prediction modes can be applied. However, the number of internal prediction modes used in accordance with the prediction unit size is unlimited. FIG. 14, and can vary. The number of internal prediction modes used in accordance with the size of the prediction unit, as depicted in FIG. 14, is just an example, and can vary. Alternatively,

193The internal prediction means 410 and 550 can include, as an internal prediction mode applied to the prediction unit, an internal prediction mode that determines an adjacent reference pixel by using a line having a predetermined angle based on the pixel in the prediction unit and using a certain adjacent prediction the reference pixel as the pixel predictor. The angle of such a line can be set by using the parameter (dx, dy), with each of dx and dy being an integer. For example, if 33 prediction modes are respectively defined as N modes, where N is an integer from 0 to 32, then mode 0 is set as vertical mode, mode 1 is set as horizontal mode, mode 2 is set as DC mode, Mode 3 is set as flat mode, and mode 32 is set as a planar mode. In addition, modes 4-31 can be defined as internal prediction modes defining an adjacent reference pixel by using a line having a tan orientation^-1(dy / dx), using (dx, dy), expressed, respectively, as (1, -1), (1,1), (1,2), (2,1), (1, -2) , (2,1), (1, -2), (2, -1), (2, -11), (5, -7), (10, -7), (11,3), (4 , 3), (1.11), (1, -1), (12, -3), (1, -11), (1, -7), (3, -10), (5, -6 ), (7, -6), (7, -4), (11.1), (6.1), (8.3), (5.3), (5.7), (2.7 ), (5, -7) and (4, -3) from Table 1, and using a certain adjacent reference pixel to perform the internal prediction.

194<tables num="1"><table frame="all"><tgroup rowsep="1" colsep="1" cols="6"><colspec colname="c1" colwidth="32mm" /><colspec colname="c2" colwidth="26mm" /><colspec colname="c3" colwidth="26mm" /><colspec colname="c4" colwidth="32mm" /><colspec colname="c5" colwidth="26mm" /><colspec colname="c6" colwidth="24mm" /><tbody><row><entry namest="c1" nameend="c6" align="right" rowsep="1" colsep="0"><b>table 2</b></entry></row><row><entry rowsep="1" colsep="1">mode#</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">mode#</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="0">dy</entry></row><row><entry rowsep="1" colsep="1">mode 4</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">-1</entry><entry rowsep="1" colsep="1">mode 18</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="0">-eleven</entry></row><row><entry rowsep="1" colsep="1">mode 5</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">mode 19</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="0">-7</entry></row><row><entry rowsep="1" colsep="1">mode 6</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1">mode 20</entry><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="0">-10</entry></row><row><entry rowsep="1" colsep="1">mode 7</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">mode 21</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="0">-6</entry></row><row><entry rowsep="1" colsep="1">mode 8</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">-2</entry><entry rowsep="1" colsep="1">mode 22</entry><entry rowsep="1" colsep="1">7th</entry><entry rowsep="1" colsep="0">-6</entry></row><row><entry rowsep="1" colsep="1">mode 9</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1">-1</entry><entry rowsep="1" colsep="1">mode 23</entry><entry rowsep="1" colsep="1">7th</entry><entry rowsep="1" colsep="0">-4</entry></row><row><entry rowsep="1" colsep="1">mode 10</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1">-eleven</entry><entry rowsep="1" colsep="1">mode 24</entry><entry rowsep="1" colsep="1">eleven</entry><entry rowsep="1" colsep="0">1</entry></row><row><entry rowsep="1" colsep="1">mode 11</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="1">-7</entry><entry rowsep="1" colsep="1">mode 25</entry><entry rowsep="1" colsep="1">6th</entry><entry rowsep="1" colsep="0">1</entry></row><row><entry rowsep="1" colsep="1">mode 12</entry><entry rowsep="1" colsep="1">10</entry><entry rowsep="1" colsep="1">-7</entry><entry rowsep="1" colsep="1">mode 26</entry><entry rowsep="1" colsep="1">8</entry><entry rowsep="1" colsep="0">3</entry></row><row><entry rowsep="1" colsep="1">mode 13</entry><entry rowsep="1" colsep="1">eleven</entry><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1">mode 27</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="0">3</entry></row><row><entry rowsep="1" colsep="1">mode 14</entry><entry rowsep="1" colsep="1">4</entry><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1">mode 28</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="0">7th</entry></row><row><entry rowsep="1" colsep="1">mode 15</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">eleven</entry><entry rowsep="1" colsep="1">mode 29</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="0">7th</entry></row><row><entry rowsep="1" colsep="1">mode 16</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">-1</entry><entry rowsep="1" colsep="1">mode 30</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="0">-7</entry></row><row><entry rowsep="1" colsep="1">mode 17</entry><entry rowsep="1" colsep="1">12</entry><entry rowsep="1" colsep="1">-3</entry><entry rowsep="1" colsep="1">mode 31</entry><entry rowsep="1" colsep="1">4</entry><entry rowsep="1" colsep="0">-3</entry></row><row><entry namest="c1" nameend="c6" rowsep="0" colsep="0">mode 0 is vertical, mode 1 is horizontal, mode 2 is DC, mode 3 is flat, and mode 32 is planar</entry></row></tbody></tgroup></table></tables>

195The number of internal prediction modes used by the intra prediction means 410, 550 is not limited to Table 2, and can vary based on whether the current unit is a prediction of the chrominance component or the luminance signal component, or based on the size of the current prediction unit. In addition, each mode N can designate an internal prediction mode different from the higher one. For example, the number of internal prediction modes can be 36, with mode 0 being the planar mode described below, mode 1 being the DC mode, modes 2-34 are internal prediction modes having 33 directionalities as described below, and mode 35 is an internal prediction mode Intra_FromLuma using a prediction unit in the luminance signal component, corresponding to the prediction unit in the chrominance component. Mode 35, i.e., the internal prediction mode Intra_FromLuma using the prediction unit in the luminance signal component corresponding to the prediction unit in the chrominance component, is applied exclusively to the prediction unit in the chrominance component, and is not used to perform the internal prediction of the prediction unit in the luminance component .

196FIG. 15 illustrates a reference schematic for describing intra-prediction modes having different directions, according to an embodiment of the present invention.

197As described above, intra prediction means 410 and 550 can determine an adjacent reference pixel by using a line having an angle equal to tan^-1(dy / dx), defined by a plurality of parameters (dx, dy), and perform an internal prediction by using a certain adjacent reference pixel.

198With reference to FIG. 15, adjacent pixels A and B located on the extension line 150 having an angle tan^-1(dy / dx) determined according to the value (dx, dy) according to the internal prediction modes of Table 2 based on the current pixel P to be predicted in the current prediction unit can be used as predictors of the current pixel P In this case, the adjacent pixel used as a predictor can be a pixel from the previous prediction unit that is pre-encoded and pre-restored and is located anywhere from the top, left, top right or bottom the left of the current prediction unit. Also, by performing the prediction coding in accordance with the internal prediction modes having different directionalities, the compression can be effectively performed in accordance with the image characteristics.

199Referring to Fig. 15, if the predictor of the current pixel P is generated by using an adjacent pixel located on or adjacent to the extension line 150, the extension line 150, in fact, has a directionality tan^-1(dy / dx), and the division (dy / dx) is required to determine the adjacent pixel using the extension line 150, and therefore the hardware or software can include a decimal point operation, thereby increasing the performance. Accordingly, if the prediction direction for selecting the reference pixel is set by using the parameters (dx, dy), then dx and dy can be set to reduce the performance.

200FIG. 16 is a diagram for describing the relationship between a current pixel and adjacent pixels located on a remote line having a directionality (dx, dy) according to an embodiment of the present invention.

201With reference to FIG. 16, P 1610 denotes the current pixel located in (j, i), and A1611 and B1612, respectively, denote the adjacent pixel from the top and the adjacent pixel on the left located on the extension line having the directivity, i.e., the angle tan^-1(dy / dx) passing through the current pixel P 1610. It is assumed that the size of the prediction unit including the current pixel P 1610 is nSxnS, where nS is a positive integer, the pixel position of the prediction unit is one of (0, 0) (nS-1, nS-1), the position of the adjacent pixel A 1611 from above on the X axis is (m, -1), where m is an integer, and the position of the adjacent pixel B 1612 on the Y axis is (-1, n ), where n is an integer. The position of the adjacent pixel 1611 from above, intersected by a remote line passing through the current pixel P1610, is in (j + i * dx / dy, -1), and the position of the adjacent pixel B 1612 on the left is (-1, i + j * dy / dx). Accordingly, to determine the adjacent pixel A 1611 from above or the adjacent pixel B 1612 on the left to predict the current pixel P1610, a division operation is required, as dx / dy or dy / dx. As described above, since the complexity of the operation for the division operation is high, the speed of the operation in software or hardware may be low. Accordingly, at least one of dx and dy indicating the direction of the prediction mode for determining the adjacent pixel may be a power of two. In other words, if each of n and m is an integer, then dx and dy can be, respectively, 2 ^ n and 2 ^ m.

202If the adjacent pixel B 1612 on the left is used as the predictor of the current pixel P 1610, and dx has a value of 2 ^ n, then the operation j * dy / dx is required to determine (-1, i + j * dy / dx), that is, of the adjacent pixel B 1612 to the left may be (i * dy) / (2 ^ n), and the division operation in which the power of the two is used can be realized by a shift operation such as (i * dy) >> n, thus, the performance is reduced.

203Similarly, if the adjacent pixel A 1611 from above is used as the predictor of the current pixel P 1610, and dy is 2 ^ m, then i * dx / dy is required to determine (j + i * dx / dy, -1), then the position of the adjacent pixel A 1611 from above can be in (i * dx) / (2Am), and the division operation using the power of two can be realized by a shift operation such as (i * dx) >> m.

204FIG. 17 and 18 illustrate a schematic diagram showing directions of an internal prediction mode according to embodiments of the present invention.

205In general, the patterns of straight lines shown in an image or video signal are mainly vertical or horizontal. Therefore, if the internal prediction mode having different directions is determined by using the parameter (dx, dy), then to improve the encoding efficiency of the image, the values ​​of dx and dy can be determined as follows.

206In more detail, if dy has a fixed value of 2 ^ m, then the absolute value of dx can be set such that the interval between prediction directions close to the vertical direction is narrow and the interval between prediction modes increases in the prediction direction close to the horizontal direction . For example, with reference to FIG. 17, if dy is 2 ^ 5, that is, 32, then dx can be set to 2, 5, 9, 13, 17, 21, 26, 32, -2, -5, -9, -13, -17 , -21, -26 and -32 in such a way that the interval between prediction directions close to the vertical direction is relatively narrow, and the interval between prediction modes increases in the prediction direction close to the horizontal direction.

207Similarly, if dx has a fixed value of 2 ^ n, then the absolute value of dy can be set so that the interval between prediction directions close to the horizontal direction is narrow and the interval between prediction modes increases in the prediction direction close to the horizontal direction . For example, with reference to FIG. 18, if dx is equal to 2 ^ 5, that is, 32, then dy can be set to 2, 5, 9, 13, 17, 21, 26, 32, -2, -5, -9, -13, -17 , -21, -26, and -32 in such a way that the interval between prediction directions close to the horizontal direction is relatively narrow, and the interval between prediction modes increases in the prediction direction close to the vertical direction.

208In addition, if one of the values ​​of dx and dy is fixed, another value can be set so that it increases according to the prediction modes. For example, if the value of dy is fixed, then the interval between dx values ​​can be set to increase by a predetermined value. This increment can be set according to the angles separated between the horizontal direction and the vertical direction. For example, if dy is fixed, then dx can be incremented a in a section where the angle with the vertical axis is less than 15 °, increment b in the section where the angle is between 15 ° and 30 °, and the increment c in the section where the angle is above 30 ° .

209For example, prediction modes having tan directionalities^-1(dy / dx) using (dx, dy) can be determined by the parameters (dx, dy) shown in Tables 3-5.

210<tables num="1"><table frame="all"><tgroup align="center" rowsep="1" colsep="1" cols="6"><colspec colname="c1" colwidth="25mm" /><colspec colname="c2" colwidth="28mm" /><colspec colname="c3" colwidth="28mm" /><colspec colname="c4" colwidth="28mm" /><colspec colname="c5" colwidth="28mm" /><colspec colname="c6" colwidth="27mm" /><tbody><row><entry namest="c1" nameend="c6" align="right" rowsep="1" colsep="0"><b>Table 3</b></entry></row><row><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="0">dy</entry></row><row><entry rowsep="1" colsep="1">-32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">21</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">13</entry></row><row><entry rowsep="1" colsep="1">-26</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">26th</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">17th</entry></row><row><entry rowsep="1" colsep="1">-21</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">21</entry></row><row><entry rowsep="1" colsep="1">-17</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-26</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">26th</entry></row><row><entry rowsep="1" colsep="1">-13</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-21</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">32</entry></row><row><entry rowsep="1" colsep="1">-9</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-17</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-5</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-13</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-2</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-9</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-5</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-2</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">9</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">2</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">13</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">5</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="0" colsep="1">17th</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">9</entry><entry rowsep="0" colsep="1" /><entry rowsep="0" colsep="0" /></row></tbody></tgroup></table></tables>

211<tables num="1"><table frame="all"><tgroup rowsep="1" colsep="1" cols="6"><colspec colname="c1" colwidth="26mm" /><colspec colname="c2" colwidth="28mm" /><colspec colname="c3" colwidth="28mm" /><colspec colname="c4" colwidth="28mm" /><colspec colname="c5" colwidth="28mm" /><colspec colname="c6" colwidth="26mm" /><tbody><row><entry namest="c1" nameend="c6" align="right" rowsep="1" colsep="0"><b>Table 4</b></entry></row><row><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="0">dy</entry></row><row><entry rowsep="1" colsep="1">-32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">19</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">10</entry></row><row><entry rowsep="1" colsep="1">-25</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">25</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">14</entry></row><row><entry rowsep="1" colsep="1">-19</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">19</entry></row><row><entry rowsep="1" colsep="1">-14</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-25</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">25</entry></row><row><entry rowsep="1" colsep="1">-10</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-19</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">32</entry></row><row><entry rowsep="1" colsep="1">-6</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-14</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-3</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-10</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-1</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-6</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-3</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-1</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">6th</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">1</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">10</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="0" colsep="1">14</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">6th</entry><entry rowsep="0" colsep="1" /><entry rowsep="0" colsep="0" /></row></tbody></tgroup></table></tables>

212<tables num="1"><table frame="all"><tgroup rowsep="1" colsep="1" cols="6"><colspec colname="c1" colwidth="26mm" /><colspec colname="c2" colwidth="28mm" /><colspec colname="c3" colwidth="28mm" /><colspec colname="c4" colwidth="28mm" /><colspec colname="c5" colwidth="28mm" /><colspec colname="c6" colwidth="26mm" /><tbody><row><entry namest="c1" nameend="c6" align="right" rowsep="1" colsep="0"><b>Table 5</b></entry></row><row><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="1">dy</entry><entry rowsep="1" colsep="1">dx</entry><entry rowsep="1" colsep="0">dy</entry></row><row><entry rowsep="1" colsep="1">-32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">23</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">15</entry></row><row><entry rowsep="1" colsep="1">-27</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">27th</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">19</entry></row><row><entry rowsep="1" colsep="1">-23</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">23</entry></row><row><entry rowsep="1" colsep="1">-19</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-27</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">27th</entry></row><row><entry rowsep="1" colsep="1">-15</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-23</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="0">32</entry></row><row><entry rowsep="1" colsep="1">-eleven</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-19</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-7</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-15</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">-3</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-eleven</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-7</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">-3</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">7th</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">0</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">eleven</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">3</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="1" colsep="1">15</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">32</entry><entry rowsep="1" colsep="1">7th</entry><entry rowsep="1" colsep="1" /><entry rowsep="1" colsep="0" /></row><row><entry rowsep="0" colsep="1">19</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">32</entry><entry rowsep="0" colsep="1">eleven</entry><entry rowsep="0" colsep="1" /><entry rowsep="0" colsep="0" /></row></tbody></tgroup></table></tables>

213As described above, the internal prediction modes using the parameters (dx, dy) use the adjacent pixel (-1, i + j * dy / dx) to the left or the adjacent pixel (j + i * dx / dy, -1) the quality of the pixel predictor located in (j, i). If at least one of dx and dy has a power of two, as shown in Table 2, then the positions of the adjacent pixel (-1, i + j * dy / dx) on the left and the adjacent pixel (j + i * dx / dy, -1 ) from above can be obtained exclusively through multiplication and shift operations without a division operation. If dx is 2 ^ n, that is, 32, at the point (dx, dy), as shown in Table 2, then the division operation using dx can be replaced by a shift operation to the right, and thus the position of the adjacent pixel on the left can be obtained without a division operation on the basis of (i * dy) >> n. Similarly, if dy is 2 ^ m, that is, 32, in (dx, dy),

214FIG. 19 is a diagram showing directions of an internal prediction mode having a directivity 33 according to an embodiment of the present invention.

215The internal prediction means 410 and 550 can determine an adjacent pixel to be used as the predictor of the current pixel in accordance with the intra prediction modes having the directivity patterns 33 shown in FIG. 19. As described above, the directions of the internal prediction modes can be set such that the interval between prediction modes decreases in the direction of the horizontal or vertical direction and increases as you move away from the vertical or horizontal direction.

216In this case, the use of adjacent pixels used as the reference pixels of the current block may be limited in accordance with the intra prediction modes having different directions, as described with reference to FIG. 19. For example, the use of an adjacent pixel included in an external block predicted by an external prediction may be limited in the internal prediction of the current block. Also, the use of an adjacent pixel included in an external block is limited in such a way as to prevent the spread of the error included in the external block. In addition, the use of an adjacent block included in a slice other than that of the current block, which is internally predicted, may be limited in the internal prediction of the current block. The use of an adjacent block included in another slice is limited due to the use of data from the adjacent block included in another slice, may be limited as the reference data of the current block, because image data is encapsulated and independently processed in a slice unit according to the general image processing. Accordingly, the internal prediction means 410 and 550 can determine whether to use the adjacent pixel for internal prediction of the current block based on the prediction mode of the adjacent block including the adjacent pixel or based on whether the slice including the adjacent block is the same, and the slice, which includes the current block. The internal prediction means 410 of the image encoder 400 can set the value of the flag (constrained_intra_pred_flag), indicating whether to use the adjacent pixel included in the outer block for internal prediction of the current block, and then add the constrained_intra_pred_flag to the encoded bit stream in such a way as to signal a restriction on the use of the adjacent pixel included in the outer block. For example, if constrained_intra_pred_flag is 0, then the adjacent pixel is used for internal prediction of the current block, regardless of the prediction mode of the adjacent block. If the constrained_intra_pred_flag value is 1, then the use of the adjacent pixel included in the outer block may be limited during the internal prediction of the current block. Alternatively, the internal prediction means 410 and 550 may limit the pixel of the adjacent block included in the slice,

217Hereinafter, assuming that the value of constrained_intra_pred_flag is 1, i.e., the use of the adjacent block included in the outer block as the reference pixel is limited during the internal prediction of the current block, the process of internal prediction means 410 and 550 replacing the adjacent pixel, having a limited use as a reference pixel, by another adjacent pixel, is described in detail with reference to FIG. 20-26. In addition, it is assumed that the use of the pixel of the adjacent block included in the slice other than the slice of the current block is always limited during the internal prediction of the current block.

218FIG. 24 is a block diagram of an internal prediction device 2400 according to an embodiment of the present invention. The internal prediction device 2400 of FIG. 24 corresponds to internal prediction means 410 and 550 of FIG. 4 and 5.

219With reference to FIG. 24, the intra prediction device 2400 includes an accessibility determiner 2410, a replacement means 2420, and an internal prediction implementer 2430.

220The availability determiner 2410 determines the availability of a predetermined number of adjacent pixels used for internal prediction of the current block. In this case, availability indicates whether an adjacent pixel for internal prediction can be used as the reference pixel of the current block. As described above, since it is assumed that the constrained_intra_pred_flag value is 1, it is determined that the adjacent pixel included in the adjacent block included in the slice other than the slice including the current block or the externally predicted adjacent block is not available. Accordingly, the availability determiner 2410 determines whether the predetermined number of adjacent pixels of the current block includes a neighboring pixel included in the adjacent block included in the slice, different from the slice including the current block, or whether the predetermined number of adjacent pixels of the current block includes a contiguous pixel included in the composition of the externally predicted adjacent block. A predetermined number of adjacent pixels can be determined according to any standard. For example, if the size of the current block is nTxnT, where Nt is an integer, then the availability can be determined with respect to all of the 4nT + 1 contiguous pixels containing 2nT adjacent pixels at the top, top and top to the right of the current block, 2nT adjacent pixels on the left, located to the left and below to the left of the current block, and one adjacent pixel located at the upper left corner of the current block. However, the number and position of adjacent pixels, the availability of which is determined, may vary.

221If it is determined that all adjacent pixels are available, the encoder internal prediction performer 2430 uses the adjacent pixel as the reference pixel so as to generate the prediction block of the current block by performing an internal prediction in accordance with an internal prediction mode having different directions, as depicted in Fig. The decoder internal predictor execution means 2430 generates a prediction block of the current block by performing an internal prediction with respect to the current block by using an adjacent pixel based on the internal prediction mode of the current block extracted from the bitstream.

222If it is determined that all adjacent pixels are unavailable, the replacement means 2420 can replace the pixel value of the inaccessible adjacent pixel with a predetermined value. In this case, the predetermined value may be a value determined based on the bit depth of the pixel. The pixel bit depth is the number of bits used to express the pixel value of one pixel, and can be 8-14 bits. Also, the BitDepth variable bit depth can be represented by the equation: BitDepth = BaseBitDepth + Increased_bit_depth, using the base bit depth of BaseBitDepth and the variable bit depth increase_bit_depth. If the bit depth is in the range of 8 to 14 bits, as described above, the base bit depth of BaseBitDepth is 8, and the increase in the bit depth increased_bit_depth has a value from 0 to 6. If all adjacent pixels are inaccessible, the replacement means 2420 can replace all adjacent pixel values ​​with a value of &lt;&lt; ((BitDepth) -1). For example, if the BitDepth bit depth is 8, then the replacement means 2420 can replace all adjacent pixel values ​​to have a pixel value of 1 &lt;&lt; (8-1), i.e., 128, i.e., 1x2 ^ 7 if all adjacent pixels are inaccessible.

223If it is determined by the access determiner 2410 that not all of the predetermined number of adjacent pixels are unavailable but at least one adjacent pixel is unavailable, the replacement means 2420 searches for an available adjacent pixel by performing a search in a predetermined number of adjacent pixels in a predetermined direction based on an inaccessible adjacent pixel, and replaces the pixel value of the inaccessible adjacent pixel with the pixel value found before foot adjacent pixel. The process of replacing an inaccessible adjacent pixel will be described below with reference to FIG. 20-23.

224If an inaccessible adjacent pixel is replaced by an available adjacent pixel, the internal prediction performing means 2430 performs an internal prediction with respect to the current block by using the replaced adjacent pixel and available adjacent pixels and generates the prediction block of the current block.

225Hereinafter, with reference to FIG. 20-23, the process of replacing an inaccessible adjacent pixel during the internal prediction of the current block will be described in detail.

226FIG. 20 is a diagram of an adjacent pixel that is inaccessible during the internal prediction of the current block 2000 in accordance with the type of the adjacent block, according to an embodiment of the present invention.

227With reference to FIG. 20, if the size of the current block 2000 is nTxnT, then the availability determiner 2410 determines whether adjacent blocks, A, B, C, D and E, include 2nT adjacent pixels at the top, top and top to the right of the current block 2000, external blocks or blocks included in a slice other than a slice including the current block 2000. In addition, the availability determiner 2410 determines whether adjacent blocks G, H, I, J and K are adjacent blocks of 2nT adjacent pixels on the left, located to the left and below to the left of the current block 2000, and the adjacent block F, including one adjacent pixel located at the upper left corner of the current block 2000, by external blocks or blocks included in a slice other than the slice including the current block 2000.

228The availability determiner 2410 determines a contiguous pixel included in an external block or block included in another slice from among adjacent blocks A through K as an inaccessible adjacent pixel. Referring to Fig. 20, because the adjacent blocks A, B, D, E, F, H and I are externally predicted external blocks, the availability determiner 2410 determines adjacent pixels 2011, 2012 and 2013 included in adjacent blocks A, B, D, E, F, H and I, as inaccessible adjacent pixels. As described above, the replacement means 2420 searches for an available adjacent pixel in a predetermined direction based on an inaccessible adjacent pixel, and replaces the pixel value of the inaccessible adjacent pixel with the pixel value of the found adjacent adjacent pixel.

229In more detail, the availability determiner 2410, according to an embodiment, first determines the availability of an adjacent pixel (hereinafter referred to as the first adjacent pixel) at a predetermined position from among the adjacent pixels. If the first adjacent pixel is unavailable, the replacement means 2420 searches for a second contiguous pixel that is available by performing a search for adjacent pixels in a predetermined direction. In addition, the replacement means 2420 replaces the first adjacent pixel with the second adjacent adjacent pixel.

230The remaining inaccessible adjacent pixel (hereinafter referred to as the third adjacent pixel), excluding the first adjacent pixel, is preprocessed and replaced based on a predetermined direction or is replaced by the original available adjacent pixel. Unavailable third adjacent pixels are successively replaced in accordance with the search order used to search for the second adjacent pixel. If the first adjacent pixel is available, then the replacement process of the first adjacent pixel is skipped, and only the replacement process of the third adjacent pixel is performed.

231Hereinafter, it is assumed that the dimensions of the current blocks 2100, 2200 and 2300 of FIG. 21-23 are nTxnT, and the point P (x, y) is the adjacent pixel whose availability is determined for the internal prediction of the current blocks 2100, 2200 and 2300, with x = -1, y = -1, ..., 2nT-1, and x = 0, ..., 2nT-1, y = 1.

232FIG. 21 is a diagram for describing the replacement process of an inaccessible adjacent pixel according to an embodiment of the present invention.

233With reference to FIG. 21, it is assumed that the first adjacent pixel, the availability of which is determined primarily from the number of adjacent pixels, is an adjacent pixel P (-1, -1) 2110 located at the upper left corner of the current block 2100. The availability determiner 2410 first determines the availability of the first adjacent pixel pixel P (-1, -1) 2110. If it is determined that the first adjacent pixel P (-1, -1) 2110 is unavailable, the replacement means 2420 sequentially searches for an available adjacent pixel in adjacent pixels in accordance with a predetermined direction based on a first adjacent pixel P (-1, -1) 2110, and replaces the first adjacent pixel P (-1, -1) 2110 initially found Interconnecting pixel (hereinafter called a second adjacent pixel). For example, the replacement means 2420 searches for adjacent pixels on top and top to the right of the current block 2100 according to the first search direction from left to right, based on the first adjacent pixel P (-1, -1) 2110, and if the second adjacent pixel does not exist in adjacent pixels top and top to the right of the current block 2100, then searches for the second contiguous block by performing a search in adjacent pixels on the left and bottom left of the current block 2100 from top to bottom based on the first adjacent pixel P (-1, -1) 2110. The replacement tool 2420 replaces first adjacent pixel l P (-1, -1) 2110 by the second adjacent pixel, which was originally found in accordance with such a direction and search order. For example, if the adjacent pixel P (nT-2, -1) 2120 is a second adjacent pixel, i.e., initially found in adjacent pixels on top and top to the right of,

234The replacement means 2420 replaces the remaining inaccessible third adjacent pixel, except the first adjacent pixel P (-1, -1) 2110, with an adjacent pixel that has been preprocessed and replaced based on a predetermined search direction, or an initially available adjacent pixel. For example, the replacement means 2420 replaces the first adjacent pixel P (-1, -1) 2110 with a second adjacent pixel P (nT-2, -1) 2120, and then replaces the next inaccessible adjacent pixel P (0, -1) with the first adjacent pixel P (-1, -1) 2110. Since the first adjacent pixel P (-1, -1) 2110 is replaced by the second adjacent pixel P (nT-2, -1) 2120, the adjacent pixel P (0, -1) has the same the most significant value is the same as the second adjacent pixel P (nT-2, -1) 2120. If the first adjacent pixel P (-1, -1) 2110 is initially available, then the process of replacing the first adjacent pixel P (-1, -1) 2110 is skipped, and, therefore,

235This replacement process is repeated for all inaccessible third adjacent pixels. Referring to Fig. 21, the second adjacent pixel P (nT-2, -1) 2120, which is available from among the adjacent pixels from above, is not replaced and retains its original pixel value. Also, the replacement means 2420 replaces the inaccessible adjacent pixel from above with an adjacent pixel that has been previously replaced, or an initially accessible adjacent pixel in accordance with a predetermined search direction. In other words, excluding the first adjacent pixel P (-1, -1) 2110 and the initially available adjacent pixel, the replacement means 2420 replaces the third adjacent pixel by the adjacent pixel directly to the left if the search direction is a left to right direction. Accordingly, if a plurality of third adjacent pixels exist at the top of the current block 2100, then the replacement means 2420 successively replaces the third adjacent pixels from left to right with the corresponding adjacent pixel on the left. In this case, the adjacent pixel on the left, used to replace the third adjacent pixel, can be a pre-replaced or initially available adjacent pixel. Similarly, the replacement means 2420 replaces the third adjacent pixel, which is inaccessible from the number of adjacent pixels to the left and below to the left of the current block by 2100 pixels immediately above. For example, the replacement means 2420 replaces the inaccessible adjacent pixel P (-1.0) by the first adjacent pixel P (-1, -1) 2110. As described above, if the first adjacent pixel P (-1, -1) 2110 is initially the replacement process of the first adjacent pixel P (-1, -1) 2110 is skipped, and therefore, the replacement means 2420 replaces the adjacent pixel P (-1.0) with the first adjacent pixel P (-1, -1) 2110. The pixel value of the adjacent pixel P (-1, 1) is replaced by the pre-processed pixel value of the adjacent pixel P (-1.0 ). As in the above-described third-adjacent pixel replacement process described above, if a plurality of third adjacent pixels exist to the left of the current block 2100, the replacement means 2420 successively replaces the third adjacent pixels from top to bottom with a corresponding adjacent pixel from above. In this case, the adjacent pixel from above, used to replace the third adjacent pixel, may be a pre-replaced or initially available adjacent pixel. 1) is replaced by a pre-processed pixel value of the adjacent pixel P (-1.0). As in the above-described third-adjacent pixel replacement process described above, if a plurality of third adjacent pixels exist to the left of the current block 2100, the replacement means 2420 successively replaces the third adjacent pixels from top to bottom with a corresponding adjacent pixel from above. In this case, the adjacent pixel from above, used to replace the third adjacent pixel, may be a pre-replaced or initially available adjacent pixel. 1) is replaced by a pre-processed pixel value of the adjacent pixel P (-1.0). As in the above-described third-adjacent pixel replacement process described above, if a plurality of third adjacent pixels exist to the left of the current block 2100, the replacement means 2420 successively replaces the third adjacent pixels from top to bottom with a corresponding adjacent pixel from above. In this case, the adjacent pixel from above, used to replace the third adjacent pixel, may be a pre-replaced or initially available adjacent pixel.

236This replacement process is repeated for all third adjacent pixels on the left and bottom left, which are unavailable. The adjacent pixel P (-1, nT + 1) 2130, available from the number of adjacent pixels on the left, is not replaced, but retains its original pixel value. Also, the replacement means 2420 replaces the adjacent pixel on the left, which is inaccessible, pre-replaced, or initially accessible by the adjacent pixel, in accordance with a predetermined search direction. In other words, if the search direction is a top-down direction, the replacement means 2420 replaces the third adjacent pixel with an adjacent pixel directly from above. Alternatively, if all adjacent pixels available to the top and left of the current block 2100 are searched, the replacement means 2420 can replace the first adjacent pixel P (-1, -1) the average value of the found adjacent pixels. For example, in FIG. 21, the pixel value of the first adjacent pixel P (-1, -1) can be replaced by the average value of the second adjacent pixel P (nT-2, -1) 2120 originally found as available from the number of adjacent pixels from above, and the adjacent pixel P (- 1, nT + 1) 2130, originally found as available from the number of adjacent pixels on the left. In other words, if PRA denotes the pixel value of the second adjacent pixel P (nT-2, -1) 2120, and PLB denotes the pixel value of the adjacent pixel P (-1, nT + 1) 2130, then the average PT obtained by the equation: PT = (PRA + PLB + 1) >> 1 can replace the pixel value of the first adjacent pixel P (-1, -1) 2110. -1) can be replaced by the average value of the second adjacent pixel P (nT-2, -1) 2120 originally found as available from the number of adjacent pixels from above, and the adjacent pixel P (-1, nT + 1) 2130 originally found as available from the number of adjacent pixels on the left. In other words, if PRA denotes the pixel value of the second adjacent pixel P (nT-2, -1) 2120, and PLB denotes the pixel value of the adjacent pixel P (-1, nT + 1) 2130, then the average PT obtained by the equation: PT = (PRA + PLB + 1) >> 1 can replace the pixel value of the first adjacent pixel P (-1, -1) 2110. -1) can be replaced by the average value of the second adjacent pixel P (nT-2, -1) 2120 originally found as available from the number of adjacent pixels from above, and the adjacent pixel P (-1, nT + 1) 2130 originally found as available from the number of adjacent pixels on the left. In other words, if PRA denotes the pixel value of the second adjacent pixel P (nT-2, -1) 2120, and PLB denotes the pixel value of the adjacent pixel P (-1, nT + 1) 2130, then the average PT obtained by the equation: PT = (PRA + PLB + 1) >> 1 can replace the pixel value of the first adjacent pixel P (-1, -1) 2110.

237Alternatively, if all adjacent pixels available to the top and left of the current block 2100 are searched, the replacement means 2420 can replace the first adjacent pixel P (-1, -1) 2110 by determining an available adjacent pixel closer to the first adjacent pixel P ( -1, -1) 2110 based on the distance from the first adjacent pixel P (-1, -1) 2110 as the second adjacent pixel, instead of using only the adjacent pixel originally found in accordance with the predetermined search direction. Referring to Fig. 21, since the distance between the first adjacent pixel P (-1, -1) 2110 and the second adjacent pixel P (nT-2, -1) 2120 originally found as accessible from above from the current block 2100 is (nT-2) - (- 1), that is, nT-1, and the distance between the first adjacent pixel P (-1, -1) 2110 and the adjacent pixel P (-1, nT + 1) 2130,

238Alternatively, in order to reduce the complexity of the search process of the second adjacent pixel to replace the first adjacent pixel P (-1, -1) 2110, the replacement means 2420 can perform searches exclusively in pixels P (-1.0) and P (0, -1), directly adjacent to the first adjacent pixel P (-1, -1) 2110, instead of performing a search in all adjacent pixels on the top and left of the current block 2110, and can replace the first adjacent pixel P (-1, -1) 2110 with an accessible adjacent pixel from the number of pixels P (-1,0) and P (0, -1). For example, the replacement means 2420 can perform searches in adjacent pixels in the order of the pixels P (-1.0) and P (0, -1) or vice versa, and replace the first adjacent pixel P (-1, -1) 2110 with a pixel value of the available adjacent pixel that was found first. If an available adjacent pixel is not found in pixels P (-1,0) and P (0, -1), then the replacement means 2420 can replace the first adjacent pixel P (-1, -1) 2110 with a predetermined value based on the bit depth, as described above. If both of the pixels P (-1.0) and P (0, -1) are available, the replacement means 2420 can replace the first adjacent pixel P (-1, -1) 2110 using the average pixel value P (-1, 0) and P (0, -1).

239In this case, the search order and search direction in adjacent pixels on the left and above can be changed. In other words, the replacement means 2420 can first perform a search in adjacent pixels on the left and below to the left of the current block 2100, and if an available adjacent pixel is not found, then it can search in adjacent pixels from above and from above from the right. In addition, instead of performing a search for an available adjacent pixel by performing searches in adjacent pixels on the left and bottom left from top to bottom, the replacement means 2420 can perform searches in adjacent pixels on the left and bottom left from the bottom up. In addition, instead of performing a search for an available adjacent pixel by performing searches on adjacent pixels on top and top right from left to right, the replacement means 2420 can perform searches in adjacent pixels from above and from top right to left.

240Alternatively, the replacement means 2420 can replace the pixel value of the first adjacent pixel P (-1, -1) 2110 by the average value of all available adjacent pixels of the number of adjacent pixels from above, from the top right, left and top to the left of the current block 2100, instead of using the initially found adjacent a pixel accessible from a number of adjacent pixels on the left and from above, to replace the first adjacent pixel P (-1, -1) 2110.

241FIG. 22 is a diagram for describing a process for replacing an inaccessible adjacent pixel according to another embodiment of the present invention.

242With reference to FIG. 22, it is assumed that the first adjacent pixel whose availability is determined by the first of the number of adjacent pixels is an adjacent pixel P (-1,2nT-1) 2210 located at the very bottom left of the current block 2200. In other words, the availability determiner 2410 first determines the availability of the first adjacent pixel P (-1,2nT-1) 2210. If it is determined that the first adjacent pixel P (-1,2nT-1) 2210 is unavailable, the replacement means 2420 sequentially searches for an available adjacent pixel from among the adjacent pixels in accordance with a predetermined order m based on the first adjacent pixel P (-1,2nT-1) 2210, and replaces the first adjacent pixel P (-1,2nT-1) 2210 with an accessible second adjacent pixel that was found initially. For example, the replacement means 2420 searches the adjacent pixels to the left and the bottom of the left of the current block 2200 according to the first upward search direction based on the first adjacent pixel P (-1,2nT-1) 2210, and if the available second contiguous pixel is not found in adjacent pixels on the left and from the bottom left, it searches for an available second adjacent pixel by performing searches of adjacent pixels at the top and top right of the current block 2200 in accordance with the second search direction from left to right. The replacement means 2420 replaces the first adjacent pixel P (-1,2nT-1) 2210 with an accessible second adjacent pixel originally found in accordance with such a search direction and a search order. For example, if the adjacent pixel P (-1, nT-2) 2220 of the number of adjacent pixels on the left is an accessible second adjacent pixel,

243Similar to the embodiment described above, the replacement means 2420 replaces the remaining inaccessible third adjacent pixel, excluding the first adjacent pixel P (-1,2 nT-1) 2210 by a pre-processed and replaced adjacent pixel or an initially available adjacent pixel based on a predetermined search direction. For example, the replacement means 2420 replaces the first adjacent pixel P (-1,2nT-1) 2210 with a second adjacent pixel P (-1, nT-2) 2220, and then replaces the next inaccessible adjacent pixel P (-1, 2nT-2) the adjacent pixel P (-1, 2nT-1) 2210. If the first adjacent pixel P (-1, 2nT-1) 2210 is initially available, then the replacement process of the first adjacent pixel P (-1, 2nT-1) 2210 is skipped, and , thus, the replacement means 2420 replaces the pixel value of the adjacent pixel P (-1,

244This replacement process is repeated for all inaccessible third adjacent pixels. Referring to Fig. 22, the second adjacent pixel P (-1, nT-2) 2220 and the adjacent pixel P (nT + 1, -1) 2230 that are accessible from the number of adjacent pixels on the left and above are not replaced and retain their original pixel values. Accordingly, the replacement means 2420 searches the adjacent pixels to the left and from the top of the current block 2200 from top to bottom and from left to right, respectively, based on the first adjacent pixel P (-1, 2nT-1) 2210, and replaces the third adjacent pixel by the adjacent pixel itself bottom or left. In other words, the replacement means 2420 replaces the inaccessible third adjacent pixels located to the left and below to the left of the current block 2200, excluding the first adjacent pixel P (-1, 2nT-1) 2210 and the initially available adjacent pixel, the corresponding adjacent pixel directly from the bottom, and replaces the inaccessible third adjacent pixels located above and top to the right of the current block 2200 with the corresponding adjacent pixel directly to the left. Therefore, the replacement means 2420, respectively, replaces the plurality of third adjacent pixels located to the left of the current uplink block 2200 with the corresponding lower adjacent pixel, and accordingly replaces the plurality of third adjacent pixels located from the top of the current block 2200 from left to right corresponding adjacent pixel to the left. As described above, the corresponding adjacent pixel on the left and the bottom used for the replacement may be a pre-replaced or initially available adjacent pixel. located top and top to the right of the current block 2200, the corresponding adjacent pixel directly to the left. Therefore, the replacement means 2420, respectively, replaces the plurality of third adjacent pixels located to the left of the current uplink block 2200 with the corresponding lower adjacent pixel, and accordingly replaces the plurality of third adjacent pixels located from the top of the current block 2200 from left to right corresponding adjacent pixel to the left. As described above, the corresponding adjacent pixel on the left and the bottom used for the replacement may be a pre-replaced or initially available adjacent pixel. located top and top to the right of the current block 2200, the corresponding adjacent pixel directly to the left. Therefore, the replacement means 2420, respectively, replaces the plurality of third adjacent pixels located to the left of the current uplink block 2200 with the corresponding lower adjacent pixel, and accordingly replaces the plurality of third adjacent pixels located from the top of the current block 2200 from left to right corresponding adjacent pixel to the left. As described above, the corresponding adjacent pixel on the left and the bottom used for the replacement may be a pre-replaced or initially available adjacent pixel. located to the left of the current uplink block 2200, corresponding to the lower adjacent pixel, and accordingly replaces the plurality of third adjacent pixels located from the top of the current block 2200 from left to right by the corresponding adjacent pixel to the left. As described above, the corresponding adjacent pixel on the left and the bottom used for the replacement may be a pre-replaced or initially available adjacent pixel. located to the left of the current uplink block 2200, corresponding to the lower adjacent pixel, and accordingly replaces the plurality of third adjacent pixels located from the top of the current block 2200 from left to right by the corresponding adjacent pixel to the left. As described above, the corresponding adjacent pixel on the left and the bottom used for the replacement may be a pre-replaced or initially available adjacent pixel.

245As described above, the search order or search direction in adjacent pixels on the left and above can be changed. In other words, the replacement means 2420 can first search in adjacent pixels from above and top to the right of the current block 2200 from right to left, and if the adjacent pixel is unavailable, then it can search in adjacent pixels to the left and bottom left of current block 2200 from top to bottom to search for a second adjacent pixel to replace the first adjacent pixel P (-1,2nT-1) 2210.

246FIG. 23 is a diagram for describing a process for replacing an inaccessible adjacent pixel according to another embodiment of the present invention.

247With reference to FIG. 23, it is assumed that the first adjacent pixel whose availability is determined initially from the number of adjacent pixels is an adjacent pixel P (2nT-1, -1) 2310 located at the top to the right of the current block 2300. In other words, the availability determiner 2410 first determines availability of the first adjacent pixel P (2nT-1, -1) 2310. If the first adjacent pixel P (2nT-1, -1) 2310 is determined to be unavailable, then the replacement means 2420 searches for an available adjacent pixel by sequentially searching for adjacent pixels according to EFINITIONS direction based on a first adjacent pixel P (2nT-1, -1) 2310, and replaces the first adjacent pixel P (2nT-1, -1) 2310 available at the second adjacent pixel is found initially. For example, the replacement means 2420 searches for adjacent pixels on top and top to the right of the current block 2300 in accordance with the first right-to-left search direction based on the first adjacent pixel P (2nT-1, -1) 2310, and if the second adjacent pixel is not available in adjacent pixels from above and top right, then searches for an available second adjacent pixel by performing a search in adjacent pixels on the left and below to the left of the current block 2300 from top to bottom. The replacement means 2420 replaces the first adjacent pixel P (2nT-1, -1) 2310 with an accessible second adjacent pixel found initially in accordance with such a search direction and a search order. For example, if the adjacent pixel P (nT + 1, -1) 2320 from among the adjacent pixels from above is an accessible second adjacent pixel that is detected initially in accordance with the search order,

248In addition, the replacement means 2420 replaces the remaining inaccessible third adjacent pixel, excluding the first adjacent pixel P (2nT-1, -1) 2310, pre-processed and replaced or initially accessible by the adjacent pixel based on the predetermined search direction. For example, the replacement means 2420 replaces the first adjacent pixel P (2nT-1, -1) 2310 with the second adjacent pixel P (nT + 1, -1), and then replaces the next inaccessible adjacent pixel P (2nT-2, -1) pixel P (2nT-1, -1).

249If the first adjacent pixel P (2nT-1, -1) 2310 is available initially, then the replacement process of the first adjacent pixel P (2nT-1, -1) 2310 is skipped, and thus the replacement means 2420 replaces the pixel value of the adjacent pixel P ( 2nT-2, -1) the original pixel value of the first adjacent pixel P (2nT-1, -1) 2310.

250This replacement process is repeated for all inaccessible third adjacent pixels. Referring to Fig. 23, the available second adjacent pixel P (nT + 1, -1) 2320 and the available adjacent pixel P (-1, nT-1) 2330 from the number of adjacent pixels, top and left, are not replaced and retain their original pixel values. Therefore, the replacement means 2420 searches adjacent pixels on the left and top of the current block 2300 from right to left and from top to bottom, respectively, based on the first adjacent pixel P (2nT-1, -1) 2310, and successively replaces the inaccessible third adjacent pixels the corresponding adjacent pixel from the top or left. In other words, the replacement means 2420 successively replaces the inaccessible third adjacent pixels located at the top and top to the right of the current block 2300 with the corresponding adjacent pixel directly to the left,

251As described above, the search order and search direction in adjacent pixels on the left and on top can be changed. In other words, the replacement means 2420 first searches adjacent pixels to the left and bottom left of the current block 2300 from the bottom up, and if the adjacent pixel is unavailable, then searches the adjacent pixels from above and from above to the right of the current block 2300 from left to right, second adjacent pixel to replace the first adjacent pixel P (2nT-1, -1) 2310.

252In this case, if the process of replacing inaccessible adjacent pixels from the number of adjacent pixels is completed, then the process of filtering the adjacent pixels may be performed. The question of using a filtered adjacent pixel can be determined based on the size of the current block. For example, a filtered adjacent pixel can be used only if the size of the current block is 16x16.

253FIG. 25A is a diagram of the filtered adjacent pixels 2510 and 2520 of the current block 2500.

254With reference to FIG. 25A, X of the adjacent pixels 2510 from the top of the current block 2500 and the Y pixels 2520 to the left of the current block 2500 can be filtered at least once, and the filtered adjacent pixel can be used for internal prediction of the current block 2500. In this case, of the block 2500 is nTxnT, then X can be equal to 2nT and Y can be equal to 2nT.

255If ContextOrg [n] denotes X + Y source adjacent pixels to the top and left of current block 2500 having the size nTxnT, where n is an integer from 0 to X + Y-1, then n is 0 in the adjacent pixel at the very bottom of the number of adjacent ones pixels on the left, that is, ContextOrg [0], and n is equal to X + Y-1 in the adjacent rightmost pixel from the number of adjacent pixels from above, that is, ContextOrg [X + Y-1].

256FIG. 25B illustrates a reference schematic for describing the process of filtering an adjacent pixel of the current block.

257With reference to FIG. 25B, if ContextOrg [n] denotes adjacent pixels on the top and left of the current block, where n is an integer from 0 to 4nT-1, adjacent pixels can be filtered by a weighted mean between adjacent pixels. If ContextFiltered1 [n] denotes a once-filtered adjacent pixel, adjacent pixels filtered by applying a three-tap filter to adjacent ContextOrg [n], can be obtained according to the equation: ContextFiltered1 [n] = (ContextOrg [n-1] + 2 * ContextOrg [n] + ContextOrg [n + 1]) / 4. Similarly, a doubly filtered contiguous pixel ContextFiltered2 [n] can be generated by recalculating the weighted average between the once filtered adjacent contiguous pixels of ContextFiltered1 [n]. For example, adjacent pixels filtered by applying a three-tap filter to the filtered adjacent ContextFiltered1 [n] pixels can be generated according to the equation: ContextFiltered2 [n] = (ContextFiltered1 [n-1] + 2 * ContextFiltered1 [n] + ContextFiltered1 [n + 1]) / 4. The filter used for filtering and the number of filterings that can be performed can vary.

258FIG. 26 is a flowchart illustrating an internal video prediction method according to an embodiment of the present invention.

259In step 2610, the availability determiner 2410 determines the availability of a predetermined number of adjacent pixels used for internal prediction of the current block of the number of blocks obtained by dividing the video frame forming the video in a hierarchical structure. As described above, if an adjacent pixel included in an adjacent slice block other than a slice including an externally predicted adjacent block or current block exists from among a predetermined number of adjacent pixels, the availability determiner 2410 determines the corresponding adjacent pixel as inaccessible adjacent pixel.

260In step 2620, if the first adjacent pixel is not available in a predetermined number of adjacent pixels, the replacement means 2420 searches for an available second adjacent pixel by performing a search in a predetermined number of adjacent pixels in a predetermined direction based on the first adjacent pixel. In step 2630, the replacement means 2420 replaces the pixel value of the first adjacent pixel with the pixel value of the second adjacent pixel. If the first adjacent pixel at a predetermined position is available, the first adjacent pixel is used as the reference pixel for performing the internal prediction of the current block, and the replacement process of the first adjacent pixel is skipped. Therefore, if the first adjacent pixel is unavailable and, thus,

261As described above, the replacement means 2420 according to the embodiment determines the availability of the first adjacent pixel located at the uppermost left corner of the current block if the first adjacent pixel is unavailable, searches for an available second adjacent pixel by performing a search in adjacent pixels from above and from above from the right of the left to the right based on the first adjacent pixel, and if the second adjacent pixel is inaccessible in the adjacent pixels from above and from above from the right, it searches for an available second Mezhno pixel by performing a search in the adjacent pixels on the left and bottom left down on the basis of a first adjacent pixel. The replacement means 2420 determines an available adjacent pixel found initially in accordance with such a search direction and the search order as the second adjacent pixel. Then, the replacement means 2420 replaces the pixel value of the first adjacent pixel with the pixel value of the second adjacent pixel. In addition, the replacement means 2420 replaces the inaccessible at least one third adjacent pixel located to the left and below to the left of the current block by an adjacent pixel directly above, excluding the first adjacent pixel and the initially available adjacent pixel, and replacing the inaccessible at least one third adjacent pixel , located at the top and top right of the current block, by an adjacent pixel directly to the left. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions, excluding the first adjacent pixel at a predetermined position, by using the immediately adjacent pixel in a predetermined direction.

262The replacement means 2420 according to another embodiment determines the availability of the first adjacent pixel located at the lowermost portion of the current block, and if the first adjacent pixel is unavailable, then determines the initially found adjacent pixel as the second adjacent pixel by performing a search in adjacent pixels on the left and bottom left from the bottom up based on the first adjacent pixel. If the second adjacent pixel is inaccessible in adjacent pixels to the left and from the bottom to the left of, the replacement means 2420 determines the initially-found available adjacent pixel as the second adjacent pixel by performing searches in adjacent pixels from above and from above right from left to right. Besides, the replacement means 2420 replaces the pixel value of the first adjacent pixel with the pixel value of the second adjacent pixel. In addition, the replacement means 2420 successively replaces the inaccessible third adjacent pixels on the left and the bottom on the left by the corresponding adjacent pixel directly from the bottom, and the inaccessible third adjacent pixels from above and from above to the right by the corresponding adjacent pixel directly to the left, excluding the first adjacent pixel and the initially available adjacent pixel . In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions by an adjacent pixel directly to the left, in a predetermined direction, excluding the first adjacent pixel at a predetermined position. the replacement means 2420 successively replaces the inaccessible third adjacent pixels to the left and the bottom on the left by the corresponding adjacent pixel directly from the bottom, and the inaccessible third adjacent pixels from above and from above to the right by the corresponding adjacent pixel directly to the left, excluding the first adjacent pixel and the initially available adjacent pixel. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions by an adjacent pixel directly to the left, in a predetermined direction, excluding the first adjacent pixel at a predetermined position. the replacement means 2420 successively replaces the inaccessible third adjacent pixels to the left and the bottom on the left by the corresponding adjacent pixel directly from the bottom, and the inaccessible third adjacent pixels from above and from above to the right by the corresponding adjacent pixel directly to the left, excluding the first adjacent pixel and the initially available adjacent pixel. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions by an adjacent pixel directly to the left, in a predetermined direction, excluding the first adjacent pixel at a predetermined position. by the corresponding adjacent pixel directly to the left, excluding the first adjacent pixel and the initially available adjacent pixel. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions by an adjacent pixel directly to the left, in a predetermined direction, excluding the first adjacent pixel at a predetermined position. by the corresponding adjacent pixel directly to the left, excluding the first adjacent pixel and the initially available adjacent pixel. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions by an adjacent pixel directly to the left, in a predetermined direction, excluding the first adjacent pixel at a predetermined position.

263The replacement means 2420 according to another embodiment determines the availability of the first adjacent pixel located at the upper rightmost portion of the current block and if the first adjacent pixel is unavailable, then determines the initially-found available adjacent pixel as the second adjacent pixel, by performing a search of adjacent pixels from above and from top right from right to left based on the first adjacent pixel. If the second adjacent pixel is inaccessible in the adjacent pixels from above and from above from the right, the replacement means 2420 determines the initially-found available adjacent pixel as the second adjacent pixel, by performing a search in adjacent pixels on the left and bottom left from top to bottom. Next, the replacement means 2420 replaces the pixel value of the first adjacent pixel with the pixel value of the second adjacent pixel. In addition, the replacement means 2420 replaces the inaccessible at least one third adjacent pixel located at the top and top to the right of the current block with an adjacent pixel directly to the right and replaces the inaccessible at least one third adjacent pixel located to the left and below to the left of the current block, adjacent pixel directly from above, excluding the first adjacent pixel and the initially available adjacent pixel. In other words, the replacement means 2420 performs the process of replacing the inaccessible third adjacent pixels in other positions, excluding the first adjacent pixel at a predetermined position, directly adjacent the pixel in the predetermined direction. In step 2640,

264As described above, the complexity of the determination process of the reference pixel used for internal prediction can be reduced by performing a search and replacing an available adjacent pixel, based on a predetermined search direction, by an inaccessible adjacent pixel.

265Since the programs for implementing the external prediction method described with reference to FIG. 1-26, are stored on computer-readable media, an independent computer system can easily implement operations (steps) in accordance with programs stored on computer-readable media.

266A computer-readable storage medium storing the program, for example, disk 26000, according to an embodiment of the present invention will now be described in detail.

267FIG. 27A is a physical structure diagram of the disk 26000 on which the program is stored, according to an embodiment of the present invention. The 26000 disk, which is a data medium, can be a hard drive, a compact disk (CD-ROM), a Blu-ray disc, or a digital versatile disk (DVD). The disc 26000 includes a plurality of concentric tracks Tr, each divided into a number of sectors Se in the peripheral direction of the disc 26000. A program that executes the above-described external prediction method can be located and stored in a specific region of the disc 26000.

268Now, with reference to FIG. 27B, a computer system will be described that implements the use of a storage medium that stores a program for executing an internal prediction method, as described above.

269FIG. 27B is a schematic of the drive 26800 for writing and reading a program by using the disk 26000. The computer system 27000 can store a program that executes an internal prediction method according to an embodiment of the present invention on the disk 26000 via the drive 26800. To execute a program stored on the disk 26000 in the computer system 27000, the program can be read from the disk 26000 and transferred to the computer system 26700 by using the drive 27000.

270A program that executes an internal prediction method according to an embodiment of the present invention can be stored not only on the disk 26000 illustrated in FIG. 27A or 27B, but also on a memory card, a ROM cassette or a solid state drive (SSD).

271Hereinafter, a system to which the above-described internal prediction method is applied will be described.

272FIG. 28 is a diagram of a general structure of a content delivery system 11000 for providing a content distribution service. The coverage area of ​​the communication system is divided into cells of predetermined sizes, and wireless base stations 11700, 11800, 11900 and 12000 are respectively installed in these cells.

273The content delivery system 11000 includes a plurality of independent devices. For example, a plurality of independent devices, such as a computer 12100, a PDA 12200, a video camera 12300 and a mobile phone 12500, are connected to the Internet network 11100 via an Internet service provider 12200, a communication network 11400 and base stations 11700, 11800, 11900 and 12,000 wireless connections.

274However, the content delivery system 11000 is not limited to the system illustrated in FIG. 28, and the devices can selectively attach to it. A plurality of independent devices can be directly connected to the communication network 11400, not through the wireless base stations 11700, 11800, 11900 and 12000.

275The camcorder 12300 is an imaging device, for example, a digital video camera that is capable of capturing video images. The 12500 mobile phone can use at least one method of communication from among various protocols, for example, Personal Digital Communications (PDC), Code Division Multiple Access (CDMA), Code Division Multiple Access (W-CDMA), Global System for Mobile Communications (GSM) and the Personal Mobile Phone System (PHS).

276The video camera 12300 can be connected to the streaming server 11300 via the wireless base station 11900 and the communication network 11400. The streaming server 11300 enables streaming of content received from the user through the video camera 12300 via real-time broadcast. The content received from the video camera 12300 can be encoded using a video camera 12300 or a streaming server 11300. The video data captured by the video camera 12300 can be transmitted to the streaming server 11300 via the computer 12100.

277The video data captured by the camera 12600 can also be transmitted to the streaming server 11300 via the computer 12100. The camera 12600 is an image forming device capable of capturing both still images and video images, similarly to a digital camera. The video data captured by the camera 12600 can be encoded using a camera 12600 or computer 12100. Software that performs video encoding and decoding can be stored on a computer-readable storage medium such as a CD-ROM, floppy disk, hard disk, an SSD card, or a memory card that can be accessed by a computer 12100.

278If the video data is captured by the camera built into the mobile phone 12500, the video data can be received from the mobile phone 12500.

279The video data can also be encoded using a large integrated circuit (LSI) system mounted in a video camera 12300, a mobile phone 12500 or a camera 12600.

280The content delivery system 11000 can encode content data recorded by the user using a video camera 12300, a camera 12600, a mobile phone 12500, or other image forming apparatus, for example, content recorded during a concert and transmit the encoded content data to the streaming server 11300. The streaming server 11300 can transmit encoded content data in the streaming content type to other clients that request content data.

281Clients are devices capable of decoding encoded content data, for example, a computer 12100, a PDA 12200, a video camera 12300, or a mobile phone 12500. Therefore, the content delivery system 11000 allows the client to receive and play back encoded content data. In addition, the content delivery system 11000 allows the client to receive encoded content data and decode and reproduce the encoded content data in real time, thereby creating the possibility of personal broadcast transmission.

282The encoding and decoding operations of the plurality of independent devices included in the content delivery system 11000 may be similar to the internal prediction method according to an embodiment of the present invention.

283Now, with reference to FIG. 29 and 30, the mobile phone 12500 included in the content delivery system 11000 according to an embodiment of the present invention will be described in more detail.

284FIG. 29 illustrates the external structure of the mobile phone 12500 to which an internal prediction method is applied according to an embodiment of the present invention. Mobile phone 12500 can be a smartphone, whose functions are unlimited, and a large number of functions can be changed or expanded.

285The mobile phone 12500 includes an internal antenna 12510 through which radio frequency (RF) signals can be exchanged with the wireless base station 12000 of FIG. 21, and includes a display screen 12520 for displaying images captured by the camera 12530 or images that are received via the antenna 12510 and decoded, for example, a liquid crystal display device (LCD) or an OLED display device. The mobile phone 12500 includes a control panel 12540 including a control button and a sensing touch panel. If the display device 12520 is a touch sensing screen, the control panel 12540 further includes a touch sensitive display panel 12520. The 12500 mobile phone includes a speaker 12580 for voice and sound output or another type of sound output unit, and a microphone 12550 for inputting speech and sound or another type of sound input unit. The 12500 mobile phone also includes a 12530 camera, such as a CCD camera, for capturing video and still images. The mobile phone 12500 may further include a data carrier 12570 for storing encoded / decoded data, such as video or still images captured by the camera 12530, received by e-mail, or received on different routes; and a connector 12560 through which the data carrier 12570 is loaded into the mobile phone 12500. The data carrier 12570 can be a flash memory, for example,

286FIG. 30 illustrates an internal structure of a mobile phone 12500 according to an embodiment of the present invention. To systematically manage parts of a mobile phone 12500 including a display screen 12520 and a control panel 12540, a power circuit 12700, an operation input controller 12640, an image encoding unit 12720, a camera interface 12630, a LCD controller 12620, an image decoding unit 12690, a multiplexer / demultiplexer 12680 , a write / read unit 12670, a modulation / demodulation unit 12660, and an audio processor 12650 are connected to the central controller 12710 via a synchronization bus 12730.

287If the user activates the power button and switches it from off to on, the power circuit 12700 supplies power to all parts of the mobile phone 12500 from the battery pack, thereby transferring the mobile phone 12500 into operational mode.

288The central controller 12710 includes a central processing unit (CPU), a ROM (Read Only Memory) and a RAM (random access memory).

289While the mobile phone 12500 transmits communication data externally, a digital signal is generated by the mobile phone 12500 under the control of the central controller 12710. For example, the sound processor 12650 can generate a digital audio signal, the image encoding unit 12720 can generate a digital image signal, and the text message data can be generated by the control panel 12540 and the operation input controller 12640. When the digital signal is transmitted to the modulation / demodulation unit 12660 under the control of the central controller 12710, the modulation / demodulation unit 12660 performs digital signal bandwidth modulation and the communication circuit 12610 performs DAC and frequency conversion with respect to the digital audio signal with a modulated frequency band. The transmission signal,

290For example, if the mobile phone 12500 is in talk mode, the audio signal received through the microphone 12550 is converted to a digital audio signal by the audio processor 12650 under the control of the central controller 12710. The digital audio signal can be converted to a conversion signal by a modulation / demodulation unit 12660 and a communication circuit 12610, and can be transmitted via an antenna 12510.

291If a text message, for example, e-mail, is transmitted in the data transfer mode, the text data of the text message is input through the control panel 12540 and transmitted to the central controller 12610 via the operation input controller 12640. Under the control of the central controller 12610, the text data is converted into a transmission signal via a modulation / demodulation unit 12660 and a communication circuit 12610 and transmitted to the wireless base station 12000 via the antenna 12510.

292In order to transmit image data in a data transmission mode, image data captured by the camera 12530 is provided to the image encoding unit 12720 via the camera interface 12630. The captured image data can be displayed directly on the display screen 12520 via the camera interface 12630 and the LCD controller 12620.

293The structure of the image encoding unit 12720 may correspond to the structure of the video encoding device 100 described above. An image encoding unit 12720 can convert image data received from the camera 12530 into compressed and encoded image data in accordance with a video encoding method used by the video encoding device 100 or the image encoder 400 described above and then output the encoded image data to a multiplexer / demultiplexer 12680 During the operation of recording the camera 12530, the audio signal received by the microphone 12550 of the mobile phone 12500 can be converted to digital audio by the sound processor 12650, and the digital audio data can be transmitted to the multiplexer / demultiplexer 12680.

294The multiplexer / demultiplexer 12680 multiplexes the encoded image data received from the image encoding unit 12720, together with the audio data received from the audio processor 12650. The data multiplexing result can be converted into a transmission signal by the modulation / demodulation unit 12660 and the communication circuit 12610, and then can be transmitted via antenna 12510.

295While the mobile phone 12500 receives the communication data from the outside, a frequency reconstruction and an ADC are performed for the signal received through the antenna 12510 to convert the signal into a digital signal. The modulation / demodulation unit 12660 performs the modulation of the frequency band of the digital signal. The modulated digital bandwidth signal is transmitted to video decoding section 12690, audio processor 12650 or LCD controller 12620 according to the type of digital signal.

296In a talk mode, the mobile phone 12500 amplifies the signal received through the antenna 12510 and receives a digital audio signal by performing a frequency conversion and ADC for the amplified signal. The received digital audio signal is converted into an analog audio signal by the modulation / demodulation unit 12660 and the audio processor 12650, and an analog audio signal is output through the speaker 12580 under the control of the central controller 12710.

297When in the data transmission mode, the video file data that was accessed on the Internet site is received, the signal received from the wireless base station 12000 via the antenna 12510 is output as multiplexed data via the modulation / demodulation unit 12660, and the multiplexed data is transmitted to the multiplexer / demultiplexer 12680.

298To decode the multiplexed data received via the antenna 12510, the multiplexer / demultiplexer 12680 demultiplexes the multiplexed data into a stream of encoded video data and a stream of encoded audio data. Via the synchronization bus 12730, the encoded video data stream and the encoded audio data stream are provided to the video decoding section 12690 and the sound processor 12650, respectively.

299The structure of the image decoding section 12690 may correspond to the structure of the above-described video decoding apparatus 200. The picture decoding section 12690 can decode the encoded video data to obtain the reconstructed video data and provide the reconstructed video data to the display screen 12520 via the LCD controller 12620 in accordance with the video decoding method used by the video decoding device 200 or the image decoder 500 described above.

300Thus, the data of the video file accessed on the website on the Internet can be displayed on the display screen 12520. At the same time, the sound processor 12650 can convert audio data to an analog audio signal and provide an analog audio signal to the speaker 12580. Therefore, audio data contained in a video file accessed on a website on the Internet can also be played through the speaker is 12580.

301The mobile phone 12500 or other type of communication terminal may be a transceiver terminal including both a video encoding device and a video decoding device according to an embodiment of the present invention may be a transceiver terminal including only a video encoding device or may be a transceiver terminal including itself only a video decoding device.

302The communication system according to the present invention is not limited to the communication system described above with reference to FIG. 28. For example, FIG. 31 illustrates a digital broadcast system using a communication system according to an embodiment of the present invention. The digital broadcasting system of FIG. 31 can receive digital broadcasting transmitted via a satellite or terrestrial network by using a video encoding device and a video decoding device according to an embodiment of the present invention.

303In particular, the broadcasting station 12890 transmits the video data stream to a communication satellite or a broadcast satellite 12900 using radio waves. The broadcast satellite 12900 transmits the broadcast signal and the broadcast signal is transmitted to the satellite broadcast receiver via a home antenna 12860. In each house, the encoded video stream can be decoded and played back by a television receiver 12810, a television set-top box 12870, or other device.

304If the video decoding apparatus according to the embodiment of the present invention is implemented as a playback device 12830, the playback device 12830 can parse and decode the encoded video stream recorded on a data carrier 12820, such as a disk or a memory card, to recover digital signals. Thus, the reconstructed video signal can be reproduced, for example, on a monitor 12840.

305In a television set-top box 12870 connected to a satellite / terrestrial antenna 12860 or a cable television (TV) cable 12850, a video decoding device according to an embodiment of the present invention can be installed. The data output from the set-top box 12870 can also be played on the TV monitor 12880.

306As another example, a video decoding apparatus according to an embodiment of the present invention can be installed in a television receiver 12810 in place of a television set-top box 12870.

307A vehicle 12920 that has a corresponding antenna 12910 can receive a signal transmitted from the satellite 12900 or from the wireless base station 11700 of FIG. 21. Decoded video can be played on the display screen of the car navigation system 12930, installed in the car 12920.

308The video signal may be encoded by the video encoding apparatus according to an embodiment of the present invention, and then may be stored on the storage medium. In particular, the image signal can be stored on the DVD disc 12960 via a DVD burner or can be stored on the hard disk by the hard disk recorder 12950. As another example, the video signal can be stored on the SD card 12970. If the HDD recording device 12950 includes a video decoding device according to an embodiment of the present invention, the video signal recorded on the DVD disc 12960, SD card 12970 or other storage medium can be reproduced on the monitor 12880 TV.

309The car navigation system 12930 may not include the camera 12530, the camera interface 12630, and the image encoding unit 12720 of FIG. 30. For example, the computer 12100 and the television receiver 12810 may not be included in the camera 12530, the camera interface 12630, and the image encoding unit 12720 of FIG. thirty.

310FIG. 32 is a diagram illustrating a network structure of a cloud computing system using a video encoding device and a video decoding device according to an embodiment of the present invention.

311The cloud computing system may include a cloud computing server 14000, a user database (DB) 14100, a plurality of computing resources 14200, and a user terminal.

312The cloud computing system provides on demand the outsourcing service of a plurality of computing resources 14200 via a data network, for example, the Internet, in response to a request from the user terminal. Within the cloud computing environment, the service provider provides users with the required services by combining computing resources in data collection and processing centers located at physically different locations through the use of virtualization technology. The user of the service should not install the computing resources, for example, the application, the storage, the operating system (OS), and the security system, to his / her own terminal for their use, but can select and use the required services (services) from the number of services in the virtual space,

313A user terminal of a given service user is connected to a cloud computing server 14000 via a data network including an Internet network and a mobile telecommunications network. For user terminals, cloud computing services, and in particular video playback services, can be provided from a cloud computing server 14000. User terminals can be different types of electronic devices capable of connecting to the Internet, for example, a desktop PC (personal computer) 14300, intelligent TV 14400, a smartphone 14500, a laptop 14600, a portable media player (PMP) 14700, a tablet computer 14800, and t .P..

314The cloud computing server 14000 can combine a plurality of computing resources 14200 distributed in the cloud network and provide a result of the association to the user terminals. The plurality of computing resources 14200 can include various data services, and can include data downloaded from user terminals. As described above, the cloud computing server 14000 can provide the desired services to the user terminals by combining a video database distributed in various areas in accordance with the virtualization technology.

315User information about users who are subscribed to the cloud computing service is stored in the user database 14100 DB. User information may include information about registration, addresses, names and personal information about user credit. The user information may further include video indexes. In this case, the indices may include a list of videos that have already been played, a list of videos that are currently being played, a video pause point that is currently playing, and the like.

316The video information stored in the user database 14100 DB can be shared between user devices. For example, if a video broadcast service is provided for a 14600 laptop in response to a request from a 14600 laptop, the video broadcasting service playback history is stored in the user database 14100 DB. If the request for reproduction of this video broadcasting service is received from the smartphone 14500, the cloud computing server 14000 searches and reproduces this video broadcasting service based on the user database 14100 DB. If the smartphone 14500 receives the video data stream from the cloud computing server 14000, the video playback process by decoding the video data stream is similar to that of the mobile phone 12500 described above with reference to FIG. thirty.

317The cloud computing server 14000 can access the playback history of the desired video broadcast service stored in the user database 14100 DB. For example, the cloud computing server 14000 receives a request for reproducing video stored in the user database 14100 DB from the user terminal. If this video was played, the method for streaming this video, performed by the cloud computing server 14000, may vary according to the request from the user terminal, i.e., according to whether the video will be played from the beginning or from the moment of its suspension. For example, if the user terminal executes the video playback request from its beginning, the cloud computing server 14000 transmits streaming video data starting from its first frame, to the user terminal. If the user terminal executes the video playback request from the moment of its suspension, the cloud computing server 14000 transmits the current video data starting from the frame corresponding to the time of the suspension to the user terminal.

318In this case, the user terminal can include a video decoding device as described above. As another example, the user terminal may include a video encoding device as described above. Alternatively, the user terminal can include both a video decoding device and a video encoding device, as described above.

319Various uses of the video encoding method, video decoding method, video encoding device and video decoding device according to the embodiments described above of the present invention have been described above with reference to FIG. 27A-32. However, video storage methods, a video encoding method and a video decoding method on a storage medium, or methods for implementing a video coding device and a video decoding device in the apparatus, according to various embodiments of the present invention, are not limited to the embodiments described above with reference to FIG. 27A-32.

320According to one or more embodiments of the present invention, the complexity of the determination process of the reference pixel used for internal prediction can be reduced by searching for and replacing an available adjacent pixel based on the predetermined search direction by an inaccessible adjacent pixel.

321While the present invention has been specifically shown and described with reference to exemplary embodiments thereof, it will be understood by those skilled in the art that various changes in form and details can be made therein without departing from the spirit and scope of the present invention as defined by the following claims.