Title of Invention

DIRECTIONAL INTERPOLATION METHOD AND VIDEO ENCODING/DECODING APPARATUS AND METHOD USING THE DIRECTIONAL INTERPOLATION METHOD

Abstract A directional interpolation method and a video encoding/decoding apparatus and method using the directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for a predetermined-size block based on the characteristics of input image data, performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
Full Text FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(Se section 10, rule 13)
"DIRECTIONAL INTERPOLATION METHOD AND VIDEO
ENCODING/DECODING APPARATUS AND METHOD USING THE
DIRECTIONAL INTERPOLATION METHOD"
SAMSUNG ELECTRONICS CO. LTD., a Korean Corporation of 416, Maetan-dong, Yeongtong-gu, Suwon-si, Gyeonggi-do 442-742, Republic of Korea;
The following specification particularly describes the invention and ascertains the manner in which it is to be performed.
-1-

DIRECTIONAL INTERPOLATION METHOD AND VIDEO
ENCODING/DECODING APPARATUS AND METHOD USING THE
DIRECTIONAL INTERPOLATION METHOD
CROSS-REFERENCE TO RELATED PATENT APPLICATION
[01] This application claims priority from Korean Patent
Application No. 10-2006-0006804, filed on January 23, 2006, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
[02] Methods and apparatuses consistent with the present invention
relate to motion compensation, and more particularly, to a video encoding/decoding using directional interpolation for improving motion compensation accuracy.
2. Description of the Related Art
[03] According to the moving picture experts group (MPEG)-l,
MPEG-2, MPEG-4, and H.264 encoding standards, P-picture encoding, in which the current picture is encoded by referring to a previous picture, and B-picture encoding, in which the current picture is encoded by referring to both a previous picture and a future picture, are adopted, and motion compensation is performed based on P-picture encoding and B-picture encoding. In particular,
2

according to the MPEG-4 or H.264 encoding standard, motion compensation is performed in units of a macroblock or on each of a plurality of blocks obtained by dividing a macroblock. Motion compensation is performed after interpolation for obtaining half pixels, quarter pixels, or one eighth pixels is performed on a block composed of integer pixels to improve the accuracy of data.
[04] FIG. 1 is a reference diagram for explaining half-pixel
interpolation.
[05] Referring to FIG. 1, gray boxes indicate original pixels and
white boxes indicate interpolation pixels. The original pixels mean integer pixels. In FIG. 1, the interpolation pixels 5, 6, 7, 8, and 9 indicate half pixels. Each of the half pixels is obtained based on its vertically or horizontally adjacent integer pixels or half pixels. For example, the half pixel 5 is obtained based on the integer pixels 1 and 2 and the half pixel 8 is obtained based on the integer pixels 3 and 4. The half pixel 6 is obtained based on the integer pixels 1 and 3 and the half pixel 7 is obtained based on the integer pixels 2 and 4. The half pixel 9 is obtained based on the half pixels 5 and 8 or the half pixels 6 and 7. Although the number of integer pixels is limited to 4 for convenience of explanation, the number of pixels used in interpolation may be adjusted properly. For example, the half pixel 5 may be obtained based on not only the integer pixels 1 and 2 but also its horizontally adjacent integer pixels. The interpolation pixels are indicated by integers within the same range as the original pixels. For example, if the original pixels are indicated by integers
3

within a range of 0 - 255, the interpolation pixels also are indicated by integers within a range of 0 - 255.
[06] FIG. 2 is a reference diagram for explaining interpolation used
for quarter pixel interpolation of luminance components in H.264, in which some pixels of a predetermined motion compensation block are illustrated. In FIG. 2, gray boxes indicate integer pixels and white boxes indicate interpolation pixels.
[07] In interpolation of FIG. 2, a plurality of pixels, i.e., 6 pixels, are
used to obtain a single interpolation pixel. In addition, each of the pixels used in interpolation is given a weight. To this end, a 6-tap filter is used. The 6-tap filter has 6 tap values. The tap values mean weights given to the pixels used in interpolation. For example, tap values (1, -5, 20, 20, -5, 1) may be used. Various numbers of pixels may be used in interpolation and various weights, i.e., tap values, may be given thereto.

[08] To obtain the half pixel b, 6 integer pixels E, F, G, H, I, and J
that are horizontally adjacent to the half pixel b are used. If the foregoing 6-tap filter is applied to the integer pixels E, F, G, H, I, and J, a horizontal sum bl is obtained as follows:
bl=(E-5*F + 20*G + 20*H-5*I + J) (1)
[09] Next, 16 is added to the horizontal sum bl, the result of the
addition is divided by 32, the result of the division is made an integer, and
4

range adjustment is performed on the integer, thereby finally obtaining the half
pixel b, as follows:
b = Clipl Y((bl + 16) » 5) (2),
where the result of addition, i.e., bl + 16, is made an integer by
rounding off. I~»5 J indicates dividing the result of the addition by 32 (=25)
and then rounding off the result of the division to the nearest integer. This is because, since the sum of the tap values of the 6-tap filter is 32 (i.e., 32 pixel values are added), the average can be obtained by dividing the result of the addition by 32. CliplY( ) maps the obtained integer, i.e., (bl + 16) » 5, to one within a range of integers indicating the original pixels (integer pixels). For example, when integer pixels are indicated by integers within a range of 0 - 255, if the obtained integer falls outside this range, CliplY( ) maps the obtained integer to a predetermined value within the range.

[10] To obtain the half pixel h, 6 integer pixels A, C, G, M, R, and T
that are vertically adjacent to the half pixel h are used. If the foregoing 6-tap filter is applied to the integer pixels A, C, G, M, R, and T, a vertical sum hi is obtained as follows:
hl=(A-5*C + 20*G + 20*M-5*R + T) (3)
[11] Next, 16 is added to the vertical sum hi, the result of the
addition is divided by 32, an average is obtained by rounding off the result of division, and range adjustment is performed on the average, thereby finally obtaining the half pixel h, as follows:
# 5

h = CliplY((hl + 16) » 5) (4)

[12] The half pixel j can be obtained in a similar manner as the half
pixel h. In other words, the half pixel j is obtained as follows: jl = (cc-5*dd + 20*hl + 20*ml -5*ee + ff) or
jl=(aa-5*bb + 20*bl+20*sl-5*gg + hh) (5)
j = CliplY((jl + 512)»10) (6)

[13] To obtain the quarter pixel a, a horizontal average filter of half
pixels and half pixels that are adjacent to the quarter pixel a is used. For example, the quarter pixel a is obtained as follows:
a = (G + b+l)»l (7),
where (G + b + 1) » 1 indicates adding 1 to (G + b), dividing the result of the addition by 2, and making the result of division an integer by rounding off the result of division to the nearest integer. The remaining quarter pixels c, d, n, f, j, k, and q also are obtained as follows:
c = (H + b+l)»l (8)
d = (G + h+l)»l (9)
n = (M + h+l)»l (10)
f=(b+j + l)»l (11)
i = (h+j + l)»l (12)
k = (j+m+l)»l (13)
q = (j + s+l)»l (14)
6

[14] FIG. 3 is a view for explaining interpolation of chrominance
components in H.264. In interpolation according to H.264, luminance components and chrominance components are processed in different manners. The predictive interpolation value of a chrominance signal is obtained by performing linear interpolation on integer pixels with 1/8-pixel accuracy. The motion vector of a chrominance frame is 1/2 the magnitude of that of a luminance frame. Once the motion vector is determined, a predictive interpolation value v is determined as follows:
v = ((8 - dx)(8 - dy)*A + dx(8 - dy)*B + (8 - dx)*dy*C + dx*dy*D + 32) » 6
05),
where dx and dy are values indicating the motion vector of the chrominance frame.
[15] As can be appreciated from FIGS. 2 and 3, related art sub-pixel
interpolation is performed only horizontally or vertically without considering the characteristics of a video, resulting in degradation of the accuracy of interpolation and motion compensation using the interpolation.
SUMMARY OF THE INVENTION
[16] The present invention provides an interpolation method having
high accuracy and a video encoding/decoding apparatus using the interpolation method.
[17] According to one aspect of the present invention, there is
provided a directional interpolation method including selecting one of a plurality of directional interpolation modes for a predetermined-size block
7

based on characteristics of input video data, performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
[18] The characteristics of the input image data indicate edge
information and the selection of the directional interpolation mode further
comprises calculating a gradient for each of a plurality of directions with
respect to each of respective pixels included in the predetermined-size block.
[19] The selection of the directional interpolation mode may be
performed by selecting a direction having a smallest gradient and selecting a
directional interpolation mode corresponding to the selected direction.
[20] According to another aspect of the present invention, there is
provided a directional interpolation method including selecting one of a
plurality of directional interpolation modes for each pixel based on
characteristics of input video data and performing directional interpolation on
the pixel based on the selected directional interpolation mode.
[21] According to still another aspect of the present invention, there
is provided a directional interpolation method including extracting mode information from a received bitstream, in which the mode information indicates a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data, and performing directional interpolation on a predetermined-size block based on the extracted mode information.
8

[22] According to yet another aspect of the present invention, there
is provided a motion compensation method using a directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data, performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
[23] According to yet another aspect of the present invention, there
is provided a motion compensation method using a directional interpolation
method. The directional interpolation method includes selecting one of a
plurality of directional interpolation modes for each pixel based on
characteristics of input video data and performing directional interpolation on
the pixel based on the selected directional interpolation mode.
[24] According to yet another aspect of the present invention, there
is provided a motion compensation method using a directional interpolation method. The directional interpolation method includes extracting mode information from a received bitstream, in which the mode information indicates a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data, and performing directional interpolation on a predetermined-size block based on the extracted mode information.
9




[25] According to yet another aspect of the present invention, there
is provided a video encoding method using a motion compensation method applying a directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for each of a plurality of predetermined-size blocks based on characteristics of input video data, performing directional interpolation on the predetermined-size blocks based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
[26] According to yet another aspect of the present invention, there
is provided a video encoding method using a motion compensation method applying a directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data and performing directional interpolation on the pixel based on the selected directional interpolation mode.
[27] According to yet another aspect of the present invention, there
is provided a video decoding method using a motion compensation method applying a directional interpolation method. The directional interpolation method includes extracting mode information from a received bitstream, in which the mode information indicates a directional interpolation mode that is selected among a plurality of directional interpolation modes based on

10

characteristics of input video data, and performing directional interpolation on
a predetermined-size block based on the extracted mode information.
[28] According to yet another aspect of the present invention, there
is provided a directional interpolation apparatus including a directional interpolation mode selection unit, a directional interpolation unit, and a mode information generation unit. The directional interpolation mode selection unit selects one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data. The directional interpolation unit performs directional interpolation on the predetermined-size block based on the selected directional interpolation mode. The mode information generation unit generates mode information indicating the selected directional interpolation mode.
[29] According to yet another aspect of the present invention, there
is provided a directional interpolation apparatus including a directional interpolation mode selection unit and a directional interpolation unit. The directional interpolation mode selection unit selects one of a plurality of directional interpolation modes for each of a plurality of pixels based on characteristics of input video data. The directional interpolation unit performs directional interpolation on the pixels based on the selected directional interpolation mode.
[30] According to yet another aspect of the present invention, there
is provided a directional interpolation apparatus including a mode information extraction unit and a directional interpolation unit. The mode information
11

extraction unit extracts mode information from a received bitstream, in which the mode information indicates a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data. The directional interpolation unit performs directional interpolation on a predetermined-size block based on the extracted mode information.
[31] According to yet another aspect of the present invention, there
is provided a computer-readable recording medium having recorded thereon a program for a directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for each of a plurality of predetermined-size blocks based on characteristics of input video data, performing directional interpolation on the predetermined-size blocks based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
[32] According to yet another aspect of the present invention, there
is provided a computer-readable recording medium having recorded thereon a program for a directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data and performing directional interpolation on the pixel based on the selected directional interpolation mode.




12






[33] According to yet another aspect of the present invention, there
is provided a computer-readable recording medium having recorded thereon a program for a directional interpolation method. The directional interpolation method includes extracting mode information from a received bitstream, in which the mode information indicates a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data, and performing directional interpolation on a predetermined-size block based on the extracted mode information.
BRIEF DESCRIPTION OF THE DRAWINGS
[34] The above and other aspects of the present invention will
become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings, in which:
[35] FIG. 1 is a reference diagram for explaining half-pixel
interpolation;
[36] FIG. 2 is a reference diagram for explaining interpolation used
for quarter pixel interpolation of luminance components in H.264;
[37] FIG. 3 is a view for explaining interpolation of chrominance
components in H.264;
[38] FIG. 4 is a block diagram of a video encoder using an
interpolation method according to an exemplary embodiment of the present invention;
[39] FIG. 5 is a view for explaining interpolation according to an
exemplary embodiment of the present invention;
13
[40] FIGS. 6A through 6E are views for explaining interpolation
with respect to a pixel A among pixels illustrated in FIG. 5 according to an
exemplary embodiment of the present invention;
[41] FIG. 7 is a detailed block diagram of an interpolation unit
according to an exemplary embodiment of the present invention;
[42] FIGS. 8A through 8E are views for explaining interpolation
with respect to a pixel B among the pixels illustrated in FIG. 5 according to an
exemplary embodiment of the present invention;
[43] FIGS. 9A through 9C are views for explaining interpolation
with respect to a pixel C among the pixels illustrated in FIG. 5 according to an
exemplary embodiment of the present invention;
[44] FIG. 10 is a flowchart illustrating an interpolation method
implemented by an interpolation unit of the video encoder of FIG. 4 according
to an exemplary embodiment of the present invention;
[45] FIG. 11 is a block diagram of a video decoder using an
interpolation method according to an exemplary embodiment of the present
invention; and
[46] FIG. 12 is a flowchart illustrating an interpolation method
implemented by an interpolation unit of the video decoder of FIG. 11
according to an exemplary embodiment of the present invention.
DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
[47] Hereinafter, exemplary embodiments of the present invention
will be described in detail with reference to the accompanying drawings.
14
[48] FIG. 4 is a block diagram of a video encoder using an
interpolation method according to an exemplary embodiment of the present
invention. The video encoder of FIG. 4 may be an MPEG-2, MPEG-4, or
H.264 encoder.
[49] First, input video data is divided into a plurality of 16*16
macroblocks.
[50] An encoder control unit 410 serves as a bitrate controller to
determine a quantization coefficient for each block so that a desired bitrate for
the entire sequence and a target bit for each picture can be achieved.
[51] A transform/quantization unit 420 transforms the input image
data to remove spatial redundancy of the input image data. The
transform/quantization unit 420 quantizes transform coefficients obtained by
transform encoding using a predetermined quantization step, thereby obtaining
two-dimensional NXM data composed of the quantized transform coefficients.
A discrete cosine transform (DCT) or an integer transform may be used for the
transform. The quantization is performed using a predetermined quantization
step.
[52] An inverse quantization/inverse transform unit 430 inversely
quantizes the image data that is quantized by the transform/quantization unit
420 and inversely transforms the inversely quantized image data using, for
example, an inverse DCT (IDCT).
15

[53] A frame memory 450 stores the image data that is inversely
quantized/inversely transformed by the inverse quantization/inverse transform
unit 430 in frame units.
[54] A motion estimation/motion compensation (ME/MC) unit 470
estimates a motion vector (MV) and a sum of absolute differences (SAD) for
each macroblock using input image data of the current frame and image data
of a previous frame stored in the frame memory 450.
[55] An entropy-encoding unit 480 receives the quantized transform
coefficients from the transform/quantization unit 420, motion vector
information from the ME/MC unit 470, and information required for decoding
such as coding type information and quantization step information from the
encoder control unit 410, performs entropy-encoding, and outputs a final
bitstream.
[56] The video encoder of FIG. 4 may also further include a
deblocking filter 440 and an intraframe prediction unit 460.
[57] The deblocking filter 440 performs filtering to remove a
blocking effect occurring in a motion-compensated image due to quantization
and outputs the result of filtering to the frame memory 450.
[58] The intraframe prediction unit 460 obtains a predictor for each
block or macroblock in a spatial domain of an intra macroblock, obtains a
difference between the obtained predictor and the intra macroblock, and
transmits the difference to the transform/quantization unit 420.




16






[59] The ME/MC unit 470 includes an interpolation unit (not shown)
according to an exemplary embodiment of the present invention. The
interpolation unit performs interpolation to improve the resolution of image
required for the generation of a motion compensation value.
[60] Hereinafter, an interpolation method (interpolation algorithm)
implemented by the interpolation unit will be described with reference to
FIGS. 5 through 10.
[61] In FIG. 5, gray boxes indicate integer pixels and white boxes
indicate interpolation pixels. In the current exemplary embodiment of the
present invention, interpolation with respect to pixels A, B, and C will be
described.
[62] FIGS. 6A through 6E are views for explaining interpolation
with respect to the pixel A among pixels illustrated in FIG. 5. In FIGS. 6A
through 6E, directional interpolation values in 90°, 22.5°, 157.5°, 45°, and
135° directions are illustrated.
[63] In FIG. 6A, a directional interpolation value A_int90 in the 90°
direction with respect to the pixel A is generated by applying an average filter
to integer pixels P13 and P23 that are adjacent to the pixel A as follows. In
the current exemplary embodiment of the present invention, the integer pixels
P13 and P23 are reconstructed integer pixels.
A_int90 = (P13 + P23)/2 (16)





17


[64] In FIG. 6B, a directional interpolation value A_int22.5 in the
22.5° direction with respect to the pixel A is generated by applying an average filter to integer pixels P14 and P22 that are adjacent to the pixel A as follows:
A_int22.5 = (P14 + P22)/2 (17)
[65] In FIG. 6C, a directional interpolation value A_intl57.5 in the
157.5° direction with respect to the pixel A is generated by applying an average filter to integer pixels P12 and P24 that are adjacent to the pixel A as follows:
A_intl57.5 = (P12 + P24)/2 (18)
[66] In FIG. 6D, a directional interpolation value A_int45 in the 45°
direction with respect to the pixel A is generated by applying an average filter to integer pixels PI3, PI4, P22, and P23 that are adjacent to the pixel A as follows:
A_int45 = (P13+P14 + P22 + P23)/4 (19)
[67] In FIG. 6E, a directional interpolation value A_intl35 in the
135° direction with respect to the pixel A is generated by applying an average filter to integer pixels P12, PI3, P23, and P24 that are adjacent to the pixel A as follows:
A_intl35 = (P12 + P13 + P23 + P24)/4 (20)
[68] Directional interpolation may be performed in various other
angle directions in addition to the 90°, 22.5°, 157.5°, 45°, and 135° directions used as examples in FIG. 6.
18

[69] In the current exemplary embodiment of the present invention,
one of a plurality of directions is selected for each pixel, directional
interpolation according to the selected direction is performed on the pixel, and
information about the selected direction is transmitted to a decoding unit.
[70] The interpolation unit of the ME/MC unit 470 according to the
current exemplary embodiment of the present invention selects one of a
plurality of directions based on the characteristics of an image for each sub-
block, performs directional interpolation on pixels of the sub-block according
to the selected direction, generates mode information indicating a directional
interpolation mode according to the selected direction, and transmits the
generated mode information to the entropy-encoding unit 480.
[71] FIG. 7 is a detailed block diagram of the interpolation unit of
the ME/MC unit 470.
[72] A directional interpolation mode selection unit 720 selects a
directional interpolation mode to be applied to a predetermined-size sub-block. The selection is made based on the characteristics of an image corresponding to the sub-block, e.g., edge information of the image. The edge information can be obtained by calculating a gradient for each direction and selecting a final direction using the calculated gradients.
[73] For example, in FIG. 6, when a gradient for the 90° direction is
D_90, D_90 is obtained using (|P12 - P22| + |P13 - P23| + |P14 - P24|)/3. Similarly, a gradient D_22.5 for the 22.5° direction is obtained using (|P13 -P21| + |P14 - P22| + |P15 - P23|)/3. A gradient D_157.5 for the 157.5°


19


direction is obtained using (|P11 - P23| + |P12 - P24| + |P13 - P25|)/3. A gradient D45 for the 45° direction is obtained using (|P13 - P22| + |P14 -P23|)/2. A gradient D_135 for the 135° direction is obtained using (|P12 -P23| + |P13-P24|)/2.
[74] The directional interpolation mode selection unit 720 obtains a
gradient for each of a plurality of directions for pixels of the sub-block and compares the gradients to select the final direction. For example, if the gradient for the 45° direction is smallest, the 45° direction is selected as an interpolation direction.
[75] A directional interpolation unit 740 performs directional
interpolation according to the 45° direction on the pixels of the sub-block.
[76] A mode information generation unit 760 generates mode
information indicating a directional interpolation mode according to the 45° direction and transmits the generated mode information to the entropy-encoding unit 480 of FIG. 4.
[77] A sub-block used in the current exemplary embodiment of the
present invention may be an 8> 20


[78] According to another exemplary embodiment of the present
invention, one of a plurality of directional interpolation modes is selected for
each pixel according to a predetermined criterion and directional interpolation
is performed according to the selected direction. For example, a gradient for
each direction is calculated for each pixel and directional interpolation
selected according to the results of calculation is performed.
[79] For example, in FIG. 6, after the gradient D_90 = (|P12 - P22| +
|P13 - P23| + |P14 - P24|)/3, the gradient D_22.5 = (|P13 - P21| + |P14 - P22| + |P15 - P23|)/3, the gradient D_157.5 = (|P11 - P23| + |P12 - P24| + |P13 -P25|)/3, the gradient D45 = (|P13 - P22| + |P14 - P23|)/2, and the gradient D_135 = (|P12 - P23| + |P13 - P24|)/2 according to the plurality of directions are calculated, the direction having the smallest gradient is selected as the final direction. In the current exemplary embodiment of the present invention, since a directional interpolation mode is selected according to the same criterion in the video encoder and the video decoder, it is not necessary to transmit separate direction information to the decoding unit. Thus, in the current exemplary embodiment of the present invention, the mode information generation unit 760 of FIG. 7 is not required.
[80] FIGS. 8A through 8E are views for explaining interpolation
with respect to the pixel B among the pixels illustrated in FIG. 5. In FIGS. 8A through 8E, directional interpolation values in 0°, 112.5°, 67.5°, 135°, and 45° directions are illustrated.
21

[81] In FIG. 8A, a directional interpolation value B_int0 in the 0°
direction with respect to the pixel B is generated using the average filter of integer pixels P22 and P23 that are adjacent to the pixel B as follows:
B_int0 = (P22 + P23)/2 (21)
[82] In FIG. 8B, a directional interpolation value B_intl12.5 in the
112.5° direction with respect to the pixel B is generated using the average filter of integer pixels P12 and P33 that are adjacent to the pixel B as follows:
B_intll2.5 = (P12 + P33)/2 (22)
[83] In FIG. 8C, a directional interpolation value B_int67.5 in the
67.5° direction with respect to the pixel B is generated using the average filter of integer pixels P13 and P32 that are adjacent to the pixel B as follows:
B_int67.5 = (P13 + P32)/2 (23)
[84] In FIG. 8D, a directional interpolation value B_intl35 in the
135° direction with respect to the pixel B is generated using the average filter of integer pixels Pll, P22, P33, P12, P23, and P34 that are adjacent to the pixel B as follows:
B_intl35 = (PI 1 + P22 + P33 + P12 + P 23 + P34)/6 (24)
[85] In FIG. 8E, a directional interpolation value B_int45 in the 45°
direction with respect to the pixel B is generated using the average filter of integer pixels P13, P22, P31, P14, P23, and P32 that are adjacent to the pixel B as follows:
B_int45=(P13 + P22 + P31 +P14 + P 23+P32)/6 (25)
22.

[86] Directional interpolation may be performed in various-angle
directions in addition to the 0°, 112.5°, 67.5°, 135°, and 45° directions taken
as examples in FIG. 8.
[87] When one of a plurality of directional interpolation modes is
selected for each pixel, a gradient for each direction is calculated and a final
direction is selected in the same manner as for the pixel A.
[88] FIGS. 9A through 9C are views for explaining interpolation
with respect to the pixel C among the pixels illustrated in FIG. 5. In FIGS. 9A
through 9C, directional interpolation values in 0°, 135°, and 45° directions are
illustrated.
[89] In FIG. 9A, a directional interpolation value C_int0 in the 0°
direction with respect to the pixel C is generated using the average filter of
integer pixels P12, P13, P22, and P23 that are adjacent to the pixel C as
follows:
C_int0 = (P12 + P13 + P22 + P23)/4 (26)
[90] In FIG. 9B, a directional interpolation value C_intl35 in the
135° direction with respect to the pixel C is generated using the average filter of integer pixels P12 and P23 that are adjacent to the pixel C as follows:
C_intl35 = (P12 + P23)/2 (27)
[91] In FIG. 9C, a directional interpolation value C_int45 in the 45°
direction with respect to the pixel C is generated using the average filter of integer pixels PI3 and P22 that are adjacent to the pixel B as follows:
C_int45 = (P13 + P22)/2 (28)

23

[92] The directional interpolation mode selection unit 720 of the
interpolation unit may selectively use H.264 interpolation. In other words, an
H.264 interpolation mode or one of a plurality of other directional
interpolation modes may be used. For example, when gradients for a plurality
of directions obtained for a predetermined sub-block exhibit uniform
distribution, H.264 interpolation may be used, instead of selecting one of the
plurality of directions.
[93] Although only pixels that are adjacent to an interpolation pixel
are used in the current exemplary embodiment of the present invention, pixels
in a wider range may be used for H.264 interpolation.
[94] In addition, while half-pixel motion compensation is considered
in the current exemplary embodiment of the present invention, the present
invention can also be applied to quarter-pixel motion compensation.
[95] FIG. 10 is a flowchart illustrating an interpolation method
implemented by the interpolation unit of the video encoder of FIG. 4.
[96] In operation 1020, one of a plurality of directional interpolation
modes is selected based on the characteristics of input image data. For
example, a gradient for each of a plurality of directions is obtained for pixels
of a predetermined-size block and the obtained gradients are compared to
select an interpolation direction. For example, if the gradient for the 45°
direction is smallest, the 45° direction is selected as the final direction.
24

[97] In operation 1040, directional interpolation is performed on
interpolation pixels of the block according to the direction selected in operation 1020, e.g., the 45° direction.
[98] In operation 1060, mode information indicating the selected
direction for the block is generated and is transmitted to the decoding unit.
[99] Alternatively, in operation 1020, when the gradients for the
directions obtained for the block exhibit uniform distribution, H.264 interpolation may be used, instead of selecting one of the plurality of directions. In this case, H.264 interpolation is performed in operation 1040 and mode information indicating H.264 interpolation is generated in operation 1060.
[100] Alternatively, interpolation may be performed according to a
direction selected for each of the pixels of the block based on a predetermined criterion. For example, a gradient for each of the directions is obtained for each of the pixels of the block and interpolation is performed according to a direction selected based on the calculated gradients. In this case, separate mode information is not generated.
[101] FIG. 11 is a block diagram of a video decoder using an
interpolation method according to an exemplary embodiment of the present invention.
[102] Referring to FIG. 11, the video decoder includes an entropy-
decoding unit 1110, an inverse quantization unit 1120, an inverse transform unit 1130, a frame memory 1140, an MC unit 1150, and an addition unit 1160.
25

[103] The entropy-decoding unit 1110 entropy-decodes an input
encoded bitstream to extract image data, motion vector information, and mode
information indicating an interpolation direction. The extracted image data is
input to the inverse quantization unit 1120 and the extracted motion vector
information and mode information are input to the MC unit 1150.
[104] The inverse quantization unit 1120 inversely quantizes the
input extracted video data.
[105] The inverse transform unit 1130 inversely transforms the
inversely quantized video data.
[106] The MC unit 1150 performs motion compensation that is the
same as that performed in a conventional video decoder. For interpolation
pixels, the MC unit 1150 determines an interpolation direction for each
predetermined-size block, e.g., each sub-block, using the input mode
information and performs directional interpolation on interpolation pixels of
the sub-block according to the determined interpolation direction.
[107] The addition unit 1160 adds values output from the inverse
transform unit 1130 and the MC unit 1150 and outputs the result of addition to
a display unit (not shown) and the frame memory 1140.
[108] According to another exemplary embodiment of the present
invention, interpolation is performed using a method of determining an
interpolation direction in the video encoder, instead of using separate mode
information. In this case, since mode information indicating an interpolation
direction is not inserted into an input bitstream, the extraction of the mode
26

information by the entropy-decoding unit 110 and the output of the mode information to the MC unit 1150 are not required.
[109] FIG. 12 is a flowchart illustrating an interpolation method
implemented by the video decoder of FIG. 11.
[110] In operation 1220, an input encoded bitstream is entropy-
decoded to extract mode information indicating a directional interpolation
mode. Here, the directional interpolation mode indicated by the mode
information is selected based on the characteristics of input image data.
[Ill] In operation 1240, an interpolation direction is determined for
each predetermined-size block, e.g., each sub-block, using the extracted mode information.
[112] In operation 1260, interpolation is performed on interpolation
pixels of the predetermined-size block according to the determined interpolation direction.
[113] According to another exemplary embodiment of the present
invention, interpolation is performed using a method of determining an interpolation direction in the video encoder, instead of using separate mode information. For example, a gradient for each direction is calculated for each pixel and directional interpolation is performed according to an interpolation direction selected based on the calculated gradients. In this case, since mode information indicating an interpolation direction is not inserted into an input bitstream, the extraction of the mode information is not required.
27

[114] As described above, according to the exemplary embodiments
of the present invention, directional interpolation is performed adaptively according to the characteristics of input image data during motion compensation, thereby improving motion compensation efficiency and thus encoding efficiency.
[115] Meanwhile, the exemplary embodiments of the present
invention can also be embodied as computer-readable code on a computer-
readable recording medium. The computer-readable recording medium is any
data storage device that can store data which can be thereafter read by a
computer system. Examples of the computer-readable recording medium
include read-only memory (ROM), random-access memory (RAM), CD-
ROMs, magnetic tapes, floppy disks, optical data storage devices, and carrier
waves (e.g., transmission over the Internet). The computer-readable recording
medium can also be distributed over network coupled computer systems so
that the computer-readable code is stored and executed in a distributed fashion.
[116] While the present invention has been particularly shown and
described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims.
28


1. A directional interpolation method comprising:
selecting one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data;
performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode; and
generating mode information indicating the selected directional interpolation mode.
2. The directional interpolation method of claim 1, wherein the characteristics of the input image data indicate edge information, and the selection of the directional interpolation mode further comprises calculating a gradient for each of a plurality of directions with respect to each of respective pixels included in the predetermined-size block.
3. The directional interpolation method of claim 2, wherein the selection of the directional interpolation mode is performed by selecting a direction having a smallest gradient and selecting a directional interpolation mode corresponding to the selected direction.
29

4. The directional interpolation method of claim 2, wherein the plurality of directions comprise at least one angle direction between horizontal and vertical directions.
5. The directional interpolation method of claim 4, wherein the respective pixels comprise at least one of a one-half pixel, a one-quarter pixel and a one-eighth pixel.
6. A directional interpolation method comprising:
selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data; and
performing directional interpolation on the pixel based on the selected directional interpolation mode.
7. The directional interpolation method of claim 6, wherein the characteristics of the input image data indicate edge information and the selection of the directional interpolation mode further comprises calculating a gradient for each of a plurality of directions for the pixel.
8. The directional interpolation method of claim 7, wherein the selection of the directional interpolation mode is performed by selecting a direction having a smallest gradient and selecting a directional interpolation mode corresponding to the selected direction.
30

9. The directional interpolation method of claim 7, wherein the plurality of directions comprise at least one angle direction between horizontal and vertical directions.
10. The directional interpolation method of claim 9, wherein the respective pixels comprise at least one of a one-half pixel, a one-quarter pixel and a one-eighth pixel.
11. A directional interpolation method comprising:
extracting mode information from a received bitstream, the mode information indicating a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data; and
performing directional interpolation on a predetermined-size block based on the extracted mode information.
12. The directional interpolation method of claim 11, wherein the
characteristics of the input image data indicate edge information, and the
selection of the directional interpolation mode is performed based on a
gradient for each of a plurality of directions with respect to each of respective
pixels included in the predetermined-size block.
31
13. A video encoding method using a directional interpolation
method, the directional interpolation method comprising:
selecting one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data;
performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode; and
generating mode information indicating the selected directional interpolation mode.
14. A video encoding method using a directional interpolation
method, the directional interpolation method comprising:
selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data; and
performing directional interpolation on the pixel based on the selected directional interpolation mode.
15. A video decoding method using a directional interpolation
method, the directional interpolation method comprising:
extracting mode information from a received bitstream, the mode information indicating a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data; and
32-

performing directional interpolation on a predetermined-size block based on the extracted mode information.
16. A directional interpolation apparatus comprising:
a directional interpolation mode selection unit which selects one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data;
a directional interpolation unit which performs directional interpolation on the predetermined-size block based on the selected directional interpolation mode; and
a mode information generation unit which generates mode information indicating the selected directional interpolation mode.
17. The directional interpolation apparatus of claim 16, wherein the characteristics of the input image data indicate edge information and the directional interpolation mode selection unit calculates a gradient for each of a plurality of directions with respect to each of respective pixels included in the predetermined-size block.
18. The directional interpolation apparatus of claim 17, wherein the directional interpolation mode selection unit selects a direction having a smallest gradient and selects a directional interpolation mode corresponding to the selected direction.
33

19. The directional interpolation apparatus of claim 17, wherein the plurality of directions comprise at least one angle direction between horizontal and vertical directions.
20. The directional interpolation apparatus of claim 19, wherein the respective pixels comprise at least one of a one-half pixel, a one-quarter pixel and a one-eighth pixel.
21. A directional interpolation apparatus comprising:
a directional interpolation mode selection unit which selects one of a plurality of directional interpolation modes for each of a plurality of pixels based on characteristics of input video data; and
a directional interpolation unit which performs directional interpolation on the pixels based on the selected directional interpolation mode.
22. The directional interpolation apparatus of claim 21, wherein the characteristics of the input image data indicate edge information and the directional interpolation mode selection unit calculates a gradient for each of a plurality of directions for the pixel.
23. The directional interpolation apparatus of claim 22, wherein the directional interpolation mode selection unit selects a direction having a
34

smallest gradient and selects a directional interpolation mode corresponding to the selected direction.
24. The directional interpolation method of claim 22, wherein the plurality of directions comprise at least one angle direction between horizontal and vertical directions.
25. The directional interpolation method of claim 24, wherein the respective pixels comprise at least one of a one-half pixel, a one-quarter pixel and a one-eighth pixel.
26. A directional interpolation apparatus comprising:
a mode information extraction unit which extracts mode information from a received bitstream, the mode information indicating a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data; and
a directional interpolation unit which performs directional interpolation on a predetermined-size block based on the extracted mode information.
27. The directional interpolation apparatus of claim 26, wherein the
characteristics of the input image data indicate edge information and the
selection of the directional interpolation mode is performed based on a
35

gradient for each of a plurality of directions with respect to each of respective pixels included in the predetermined-size block.
28. A video encoder comprising a directional interpolation
apparatus, wherein the directional interpolation apparatus comprises:
a directional interpolation mode selection unit which selects one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data;
a directional interpolation unit which performs directional interpolation on the predetermined-size block based on the selected directional interpolation mode; and
a mode information generation unit which generates mode information indicating the selected directional interpolation mode.
29. A video encoder comprising a directional interpolation
apparatus, wherein the directional interpolation apparatus comprises:
a directional interpolation mode selection unit which selects one of a plurality of directional interpolation modes for each of a plurality of pixels based on characteristics of input video data; and
a directional interpolation unit which performs directional interpolation on the pixels based on the selected directional interpolation mode.
36
30. A video decoder comprising a directional interpolation
apparatus, wherein the directional interpolation apparatus comprises:
a mode information extraction unit which extracts mode information from a received bitstream, the mode information indicating a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data; and
a directional interpolation unit which performs directional interpolation on a predetermined-size block based on the extracted mode information.
31. A computer-readable recording medium having recorded
thereon a program for a directional interpolation method, the directional
interpolation method comprising:
selecting one of a plurality of directional interpolation modes for a predetermined-size block based on characteristics of input video data;
performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode; and
generating mode information indicating the selected directional interpolation mode.
32. A computer-readable recording medium having recorded
thereon a program for a directional interpolation method, the directional
interpolation method comprising:
37
selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data; and
performing directional interpolation on the pixel based on the selected directional interpolation mode.
33. A computer-readable recording medium having recorded
thereon a program for a directional interpolation method, the directional
interpolation method comprising:
extracting mode information from a received bitstream, the mode information indicating a directional interpolation mode that is selected among a plurality of directional interpolation modes based on characteristics of input video data; and
performing directional interpolation on a predetermined-size block based on the extracted mode information.
34. A video decoding method using a directional interpolation
method, the directional interpolation method comprising:
selecting one of a plurality of directional interpolation modes for each pixel based on characteristics of input video data; and
performing directional interpolation on a predetermined-size block based on the selected directional interpolation mode.
Dated this 15* day of December, 2006
G. Deepak Sriniwas
Of K&S Partners
Attorney for the Applicants.
38
ABSTRACT OF THE DISCLOSURE
A directional interpolation method and a video encoding/decoding apparatus and method using the directional interpolation method. The directional interpolation method includes selecting one of a plurality of directional interpolation modes for a predetermined-size block based on the characteristics of input image data, performing directional interpolation on the predetermined-size block based on the selected directional interpolation mode, and generating mode information indicating the selected directional interpolation mode.
39


Documents:

2066-MUM-2006-ABSTRACT(10-3-2010).pdf

2066-MUM-2006-ABSTRACT(18-12-2006).pdf

2066-mum-2006-abstract(granted)-(8-10-2010).pdf

2066-mum-2006-abstract.doc

2066-mum-2006-abstract.pdf

2066-MUM-2006-CANCELLED PAGES(20-9-2010).pdf

2066-MUM-2006-CLAIMS(18-12-2006).pdf

2066-MUM-2006-CLAIMS(AMENDED)-(10-3-2010).pdf

2066-MUM-2006-CLAIMS(AMENDED)-(20-9-2010).pdf

2066-mum-2006-claims(granted)-(8-10-2010).pdf

2066-mum-2006-claims.doc

2066-mum-2006-claims.pdf

2066-mum-2006-correspondance-others.pdf

2066-mum-2006-correspondance-received.pdf

2066-MUM-2006-CORRESPONDENCE(17-1-2007).pdf

2066-MUM-2006-CORRESPONDENCE(IPO)-(8-10-2010).pdf

2066-mum-2006-description (complete).pdf

2066-MUM-2006-DESCRIPTION(COMPLETE)-(18-12-2006).pdf

2066-mum-2006-description(granted)-(8-10-2010).pdf

2066-MUM-2006-DRAWING(10-3-2010).pdf

2066-MUM-2006-DRAWING(18-12-2006).pdf

2066-mum-2006-drawing(granted)-(8-10-2010).pdf

2066-mum-2006-drawings.pdf

2066-MUM-2006-FORM 1(17-1-2007).pdf

2066-MUM-2006-FORM 1(18-12-2006).pdf

2066-MUM-2006-FORM 2(COMPLETE)-(18-12-2006).pdf

2066-mum-2006-form 2(granted)-(8-10-2010).pdf

2066-MUM-2006-FORM 2(TITLE PAGE)-(18-12-2006).pdf

2066-mum-2006-form 2(title page)-(granted)-(8-10-2010).pdf

2066-MUM-2006-FORM 26(10-3-2010).pdf

2066-MUM-2006-FORM 3(10-3-2010).pdf

2066-MUM-2006-FORM 3(10-3-2010).tif

2066-MUM-2006-FORM 3(17-1-2007).pdf

2066-MUM-2006-FORM 3(18-12-2006).pdf

2066-MUM-2006-FORM 3(20-9-2010).pdf

2066-MUM-2006-FORM 5(10-3-2010).pdf

2066-MUM-2006-FORM 5(18-12-2006).pdf

2066-mum-2006-form-1.pdf

2066-mum-2006-form-18.pdf

2066-mum-2006-form-2.doc

2066-mum-2006-form-2.pdf

2066-mum-2006-form-3.pdf

2066-mum-2006-form-5.pdf

2066-MUM-2006-OTHER DOCUMENT(10-3-2010).pdf

2066-MUM-2006-OTHER DOCUMENT(20-9-2010).pdf

2066-MUM-2006-PETITION UNDER RULE 137(10-3-2010).pdf

2066-MUM-2006-REPLY TO EXAMINATION REPORT(10-3-2010).pdf

2066-MUM-2006-REPLY TO EXAMINATION REPORT(20-9-2010).pdf


Patent Number 243375
Indian Patent Application Number 2066/MUM/2006
PG Journal Number 42/2010
Publication Date 15-Oct-2010
Grant Date 08-Oct-2010
Date of Filing 18-Dec-2006
Name of Patentee SAMSUNG ELECTRONICS CO., LTD.
Applicant Address 416, MAETAN-DONG, YEONGTONG-GU, SUWON-SI, GYEONGGI-DO 442-742,
Inventors:
# Inventor's Name Inventor's Address
1 BYUNG-CHEOL SONG 106-1802 Dongsuwon LG Village 1-cha Apt., Mangpo-dong, Yeongtong-gu, Suwon-si, Gyeonggi-do,
PCT International Classification Number H04N7/26
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10-2006-0006804 2006-01-23 Republic of Korea