Note: Descriptions are shown in the official language in which they were submitted.
CA 03078905 2020-04-09
DESCRIPTION
TITLE OF THE INVENTION
MOVING IMAGE ENCODING DEVICE, MOVING IMAGE
ENCODING METHOD, MOVING IMAGE ENCODING COMPUTER
PROGRAM, MOVING IMAGE DECODING DEVICE, MOVING IMAGE
DECODING METHOD, AND MOVING IMAGE DECODING COMPUTER
PROGRAM
TECHNICAL FIELD
The present invention relates to, for
example, a moving image encoding device, a moving
image encoding method, and a moving image encoding
computer program, which encode moving image data,
and a moving image decoding device, a moving image
decoding method, and a moving image decoding
computer program, which decode encoded moving image
data.
BACKGROUND ART
Generally, moving image data has a
significantly large amount of data. Thus, a device
handling moving image data compresses moving image
data by encoding when the device is sending moving
image data to another device or when the device is
storing moving image data in a storage device. As a
representative moving image encoding standard,
Advanced Video Coding (MPEG-4 AVC or ITU-T H.264)
and High Efficiency Video Coding (HEVC or ITU-T
H.265) have been developed (for example, see Non
Patent Document 1).
In such an encoding standard, a picture to
be encoded is partitioned into blocks. For
each
block to be encoded, a prediction block is generated
from another picture already encoded or an area
already encoded in the picture to be encoded, and
1
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
redundancy is removed by encoding a difference
between the block to be encoded and the prediction
block.
For example, each picture included in
moving image data is partitioned at multiple stages
in HEVC. First, partitioning of a picture in HEVC
will be described.
FIG. 1 is a drawing illustrating an
example of partitioning a picture in HEVC. As
illustrated in FIG. 1, a picture 100 is partitioned
by a coding tree unit (CTU) (which is also called a
largest coding unit (LCU)) that is a unit for an
encoding process. Each
CTU 101 is encoded in the
order of raster scanning. The size of the CTU 101
can be selected from 16x16 to 64x64 pixels.
The CTU 101 is further partitioned into
multiple coding units (CUs) 102 using a quadtree
structure. Each
of the CUs 102 in one CTU 101 is
encoded in the z-scan order. The size of the CU 102
is variable and the size is selected from 8x8 to
64x64 pixels of a CU partitioning mode. The CU 102
is a unit for selecting the intra prediction
encoding method or the inter prediction encoding
method, which are encoding modes. The
intra
prediction encoding method is an encoding method
generating a prediction block by referring to an
encoded area of a picture to be encoded. The inter
prediction encoding method is an encoding method
generating a prediction block by referring to a
reference picture (which is also called a locally
decoded picture) obtained by decoding another
picture that is already encoded.
The CUs 102 are individually processed in
a prediction unit (PU) 103 or a transform unit (TU)
104. The
PU 103 is a unit generating a prediction
block on which a prediction is performed in
accordance with the encoding mode. For example, in
2
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
the intra prediction encoding method, the PU 103 is a unit
to which a prediction mode that specifies pixels
referenced when the prediction block is generated and that
specifies a generation method of the prediction block, is
applied. In the inter prediction encoding method, the PU
103 is a unit for performing motion compensation. The
size of the PU 103 can be selected, for example, among
2Nx2N, NxN, 2NxN, Nx2N, 2NxnU, 2NxnD, nRx2N, nLx2N (where
N is CU size / 2) when the inter prediction encoding
method is applied. Additionally, the TU 104 is a unit for
an orthogonal transformation and the orthogonal
transformation is applied to each TU. The size of the TU
104 is selected from 4x4 to 32x32 pixels. The
TU 104 is
partitioned using the quadtree structure and is processed
in the z-scan order.
The CTU is one example of the block obtained by
partitioning a picture. The CU is another example of the
block. Furthermore, the CU is one example of a sub-block
obtained by partitioning the block.
In HEVC, the CTU is partitioned so that the CU
is a square.
However, when the horizontal size or the
vertical size of a picture is not an integral multiple of
the horizontal size or the vertical size of the CTU, the
CTU located at a right side or a bottom side includes an
edge of the picture. In this case, in order to encode the
CTU without including information outside of the picture,
it is preferable to partition the CTU so that a boundary
between the CUs matches the edge of the picture, that is,
so that the edge of the picture is not included in any CU.
However, in order to partition the CTU so that the edge of
the picture is not included in any CU, it may be required
that the size of the CU is decreased and the number of the
CUs included in the CTU is increased. In such a
3
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
case, syntax information included in encoded data of
the CTU may be increased and encoding efficiency may
be reduced.
With respect to the description above, in
order to improve the encoding efficiency, it is
proposed that after partitioning the CTU into
multiple sub-blocks using the quadtree structure,
each CU is determined by further partitioning each
of the sub-blocks using a binary tree structure (for
example, see Non Patent Document 2). In this case,
the CU may be a rectangle.
However, even when the binary tree
structure is applied as described above, sub-blocks
already partitioned in a square shape are not
combined. Thus, with respect to the CTU including
the edge of the picture, the CTU may not be able to
be partitioned so that the size of the CU is large.
Additionally, a technology determining an
edge block that is smaller than the size of a
macroblock is proposed. This technology detects the
size for a higher encoding efficiency from among the
size of a non-square area determined to be the edge
block and the size of multiple non-square areas
obtained by partitioning the edge block either in a
horizontal direction or a vertical direction (for
example, see Patent Document 1).
RELATED-ART DOCUMENT
PATENT DOCUMENT
[Patent Document]
[Patent Document 1] Japanese Laid-Open Patent
Publication No. 2011-223303
[Non Patent Document]
[Non Patent Document 1] Recommendation ITU-T H.265
(ISO/IEC 23008-2), "High Efficiency Video Coding",
April 2013
[Non Patent Document 2] J. An et al, "Block
4
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
partitioning structure for next generation video coding",
ITU-T SG16 Doc. COM 16-C966, September 2015
OVERVIEW OF THE INVENTION
However, even when the edge block is encoded as
a non-square area, a moving image encoding device includes
syntax indicating a partitioning pattern of the edge block
in encoded moving image data.
Thus, when types of a
partitioning pattern of the edge block that is a non-
square area are increased, an encoding amount is increased,
and this reduces the encoding efficiency.
According to one aspect, the present invention
aims to provide a moving image encoding device that can
improve an encoding efficiency even when an edge of a
picture is included in a block that is a unit for an
encoding process.
According to an embodiment, a moving image
encoding device that encodes a picture to be encoded
included in moving image data is provided. The
moving
image encoding device includes a partitioning pattern
determining unit configured to partition a picture edge
block into a plurality of sub-blocks so that none of the
plurality of sub-blocks include an edge of the picture to
be encoded by partitioning the picture edge block into
four in accordance with a quadtree structure or
partitioning the picture edge block into two in a
direction orthogonal to the edge of the picture to be
encoded included in the picture edge block, the picture
edge block being a block including either a horizontal
edge or a vertical edge of the picture to be encoded among
a plurality of blocks obtained by partitioning the picture
to be encoded, a prediction block generator configured to
generate a prediction block by referring to another
encoded picture or an encoded area of the picture to be
encoded for each of the plurality of sub-blocks, an
Date Recue/Received date 2020-04-09
86281021
encoder configured to calculate a prediction error between
a pixel of a given sub-block and a corresponding pixel of
the prediction block corresponding to the given sub-block
for each of the plurality of sub-blocks and encode the
prediction error, and an adding unit configured to add
partitioning information indicating whether the picture
edge block has been partitioned into four or two, to
encoded moving image data.
According to another embodiment, there is
provided a moving image encoding device for encoding a
picture to be encoded included in moving image data, the
moving image encoding device comprising: a partitioning
pattern determining unit configured to partition a picture
edge block into a plurality of sub-blocks so that none of
the plurality of sub-blocks include an edge of the picture
to be encoded by partitioning the picture edge block into
four in accordance with a quadtree structure when the
picture edge block includes both a horizontal edge of the
picture to be encoded and a vertical edge of the picture
to be encoded, by partitioning the picture edge block into
two in a direction orthogonal to the edge included in the
picture edge block when the picture edge block includes
either the horizontal edge of the picture to be encoded or
the vertical edge of the picture to be encoded after a
block including the picture edge block has been
partitioned into two, and by partitioning the picture edge
block into four in accordance with the quadtree structure
or partitioning the picture edge block into two in the
direction orthogonal to the edge included in the picture
edge block when the picture edge block includes either the
horizontal edge of the picture to be encoded or the
vertical edge of the picture to be encoded after the block
including the picture edge block has been partitioned into
four, the picture edge block being a block including at
least either the horizontal edge of the picture to be
6
Date Recue/Date Received 2021-09-20
86281021
encoded or the vertical edge of the picture to be encoded
among a plurality of blocks obtained by partitioning the
picture to be encoded; a prediction block generator
configured to generate a prediction block by referring to
another encoded picture or an encoded area of the picture
to be encoded for each of the plurality of sub-blocks; an
encoder configured to calculate a prediction error between
a pixel of a given sub-block and a corresponding pixel of
the prediction block corresponding to the given sub-block
for each of the plurality of sub-blocks, and encode the
prediction error; and an adding unit configured to add
partitioning information indicating whether the picture
edge block has been partitioned into four or two, to
encoded moving image data.
According to another embodiment, a moving image
decoding device that decodes a picture to be decoded
included in moving image data is provided. The
moving
image decoding device includes a partitioning pattern
determining unit configured to partition a picture edge
block into a plurality of sub-blocks so that none of the
plurality of sub-blocks include an edge of the picture to
be decoded by partitioning the picture edge block into
four in accordance with a quadtree structure or
partitioning the picture edge block into two in a
direction orthogonal to the edge of the picture to be
decoded included in the picture edge block by referring to
partitioning information that is included in the encoded
moving image data and that indicates whether the picture
edge block has been partitioned into four in accordance
with the quadtree structure or has been partitioned into
two, the picture edge block being a block including either
a horizontal edge of the picture to be decoded or a
vertical edge of the picture to be decoded among a
plurality of blocks obtained by partitioning the picture
to be decoded, a prediction block generator configured to
generate a prediction block by referring to another
7
Date Recue/Date Received 2021-09-20
86281021
decoded picture or a decoded area of the picture to be
decoded for each of the plurality of sub-blocks, and a
decoder configured to decode the picture edge block by
adding a prediction error between a pixel of a given
sub-block included in the encoded moving image data and a
corresponding pixel of the prediction block corresponding
to the given sub-block, and a value of the corresponding
pixel of the prediction block, for each of the plurality
of sub-blocks.
According to another embodiment, there is
provided a moving image decoding device for decoding a
picture to be decoded included in encoded moving image
data, the moving image decoding device comprising: a
partitioning pattern determining unit configured to
partition a picture edge block into a plurality of sub-
blocks so that none of the plurality of sub-blocks include
an edge of the picture to be decoded by partitioning the
picture edge block into four in accordance with a quadtree
structure when the picture edge block includes both a
horizontal edge of the picture to be decoded and a
vertical edge of the picture to be decoded, by
partitioning the picture edge block into two in a
direction orthogonal to the edge included in the picture
edge block when the picture edge block includes either the
horizontal edge of the picture to be decoded or the
vertical edge of the picture to be decoded after a block
including the picture edge block has been partitioned into
two, and by partitioning the picture edge block into four
in accordance with the quadtree structure or partitioning
the picture edge block into two in the direction
orthogonal to the edge included in the picture edge block
by referring to partitioning information that is included
in the encoded moving image data and that indicates
whether the picture edge block has been partitioned into
four in accordance with the quadtree structure or has been
partitioned into two when the picture edge block includes
7a
Date Recue/Date Received 2021-09-20
86281021
either the horizontal edge of the picture to be decoded or
the vertical edge of the picture to be decoded after the
block including the picture edge block has been
partitioned into four, the picture edge block being a
block including at least either the horizontal edge of the
picture to be decoded or the vertical edge of the picture
to be decoded among a plurality of blocks obtained by
partitioning the picture to be decoded; a prediction block
generator configured to generate a prediction block by
referring to another decoded picture or a decoded area of
the picture to be decoded for each of the plurality of
sub-blocks; and a decoder configured to decode the picture
edge block by adding a prediction error between a pixel of
a given sub-block included in the encoded moving image
data and a corresponding pixel of the prediction block
corresponding to the given sub-block, and a value of the
corresponding pixel of the prediction block, for each of
the plurality of sub-blocks.
According to another embodiment, there is
provided a moving image encoding method for encoding a
picture to be encoded included in moving image data, the
moving image encoding method comprising: partitioning a
picture edge block into a plurality of sub-blocks so that
none of the plurality of sub-blocks include an edge of the
picture to be encoded by partitioning the picture edge
block into four in accordance with a quadtree structure
when the picture edge block includes both a horizontal
edge of the picture to be encoded and a vertical edge of
the picture to be encoded, by partitioning the picture
edge block into two in a direction orthogonal to the edge
included in the picture edge block when the picture edge
block includes either the horizontal edge of the picture
to be encoded or the vertical edge of the picture to be
encoded after a block including the picture edge block has
been partitioned into two, and by partitioning the picture
edge block into four in accordance with the quadtree
7b
Date Recue/Date Received 2021-09-20
86281021
structure or partitioning the picture edge block into two
in the direction orthogonal to the edge included in the
picture edge block when the picture edge block includes
either the horizontal edge of the picture to be encoded or
the vertical edge of the picture to be encoded after the
block including the picture edge block has been
partitioned into four, the picture edge block being a
block including at least either the horizontal edge of the
picture to be encoded or the vertical edge of the picture
to be encoded among a plurality of blocks obtained by
partitioning the picture to be encoded; generating a
prediction block by referring to another encoded picture
or an encoded area of the picture to be encoded for each
of the plurality of sub-blocks; calculating a prediction
error between a pixel of a given sub-block and a
corresponding pixel of the prediction block corresponding
to the given sub-block for each of the plurality of sub-
blocks, and encoding the prediction error; and adding
partitioning information indicating whether the picture
edge block has been partitioned into four or two, to
encoded moving image data.
According to another embodiment, there is
provided a moving image decoding method for decoding a
picture to be decoded included in encoded moving image
data, the moving image decoding method comprising:
partitioning a picture edge block into a plurality of sub-
blocks so that none of the plurality of sub-blocks include
an edge of the picture to be decoded by partitioning the
picture edge block into four in accordance with a quadtree
structure when the picture edge block includes both a
horizontal edge of the picture to be decoded and a
vertical edge of the picture to be decoded, by
partitioning the picture edge block into two in a
direction orthogonal to the edge included in the picture
edge block when the picture edge block includes either the
horizontal edge of the picture to be decoded or the
7c
Date Recue/Date Received 2021-09-20
86281021
vertical edge of the picture to be decoded after a block
including the picture edge block has been partitioned into
two, and by partitioning the picture edge block into four
in accordance with the quadtree structure or partitioning
the picture edge block into two in the direction
orthogonal to the edge included in the picture edge block
by referring to partitioning information that is included
in the encoded moving image data and that indicates
whether the picture edge block has been partitioned into
four in accordance with the quadtree structure or has been
partitioned into two when the picture edge block includes
either the horizontal edge of the picture to be decoded or
the vertical edge of the picture to be decoded after the
block including the picture edge block has been
partitioned into four, the picture edge block being a
block including at least either the horizontal edge of the
picture to be decoded or the vertical edge of the picture
to be decoded among a plurality of blocks obtained by
partitioning the picture to be decoded; generating a
prediction block by referring to another decoded picture
or a decoded area of the picture to be decoded for each of
the plurality of sub-blocks; and decoding the picture edge
block by adding a prediction error between a pixel of a
given sub-block included in the encoded moving image data
and a corresponding pixel of the prediction block
corresponding to the given sub-block, and a value of the
corresponding pixel of the prediction block, for each of
the plurality of sub-blocks.
According to another embodiment, there is
provided a non-transitory computer readable medium storing
a moving image encoding computer program comprising
executable instructions for encoding a picture to be
encoded included in moving image data and causing a
computer to execute a method, the method comprising:
partitioning a picture edge block into a plurality of sub-
blocks so that none of the plurality of sub-blocks include
7d
Date Recue/Date Received 2021-09-20
86281021
an edge of the picture to be encoded by partitioning the
picture edge block into four in accordance with a quadtree
structure when the picture edge block includes both a
horizontal edge of the picture to be encoded and a
vertical edge of the picture to be encoded, by
partitioning the picture edge block into two in a
direction orthogonal to the edge included in the picture
edge block when the picture edge block includes either the
horizontal edge of the picture to be encoded or the
vertical edge of the picture to be encoded after a block
including the picture edge block has been partitioned into
two, and by partitioning the picture edge block into four
in accordance with the quadtree structure or partitioning
the picture edge block into two in the direction
orthogonal to the edge included in the picture edge block
when the picture edge block includes either the horizontal
edge of the picture to be encoded or the vertical edge of
the picture to be encoded after the block including the
picture edge block has been partitioned into four, the
picture edge block being a block including at least either
the horizontal edge of the picture to be encoded or the
vertical edge of the picture to be encoded among a
plurality of blocks obtained by partitioning the picture
to be encoded; generating a prediction block by referring
to another encoded picture or an encoded area of the
picture to be encoded for each of the plurality of sub-
blocks; calculating a prediction error between a pixel of
a given sub-block and a corresponding pixel of the
prediction block corresponding to the given sub-block for
each of the plurality of sub-blocks, and encoding the
prediction error; and adding partitioning information
indicating whether the picture edge block has been
partitioned into four or two, to encoded moving image data.
According to another embodiment, there is
provided a non-transitory computer readable medium storing
a moving image decoding computer program comprising
7e
Date Recue/Date Received 2021-09-20
86281021
executable instructions for decoding a picture to be
decoded included in encoded moving image data and causing
a computer to execute a method, the method comprising:
partitioning a picture edge block into a plurality of sub-
blocks so that none of the plurality of sub-blocks include
an edge of the picture to be decoded by partitioning the
picture edge block into four in accordance with a quadtree
structure when the picture edge block includes both a
horizontal edge of the picture to be decoded and a
vertical edge of the picture to be decoded, by
partitioning the picture edge block into two in a
direction orthogonal to the edge included in the picture
edge block when the picture edge block includes either the
horizontal edge of the picture to be decoded or the
vertical edge of the picture to be decoded after a block
including the picture edge block has been partitioned into
two, and by partitioning the picture edge block into four
in accordance with the quadtree structure or partitioning
the picture edge block into two in the direction
orthogonal to the edge included in the picture edge block
by referring to partitioning information that is included
in the encoded moving image data and that indicates
whether the picture edge block has been partitioned into
four in accordance with the quadtree structure or has been
partitioned into two when the picture edge block includes
either the horizontal edge of the picture to be decoded or
the vertical edge of the picture to be decoded after the
block including the picture edge block has been
partitioned into four, the picture edge block being a
block including at least either the horizontal edge of the
picture to be decoded or the vertical edge of the picture
to be decoded among a plurality of blocks obtained by
partitioning the picture to be decoded; generating a
prediction block by referring to another decoded picture
or a decoded area of the picture to be decoded for each of
the plurality of sub-blocks; and decoding the picture edge
7f
Date Recue/Date Received 2021-09-20
86281021
block by adding a prediction error between a pixel of a
given sub-block included in the encoded moving image data
and a corresponding pixel of the prediction block
corresponding to the given sub-block, and a value of the
corresponding pixel of the prediction block, for each of
the plurality of sub-blocks.
In one aspect, a moving image encoding device
disclosed in the present specification can improve an
encoding efficiency even when an edge of a picture is
included in a block that is a unit for an encoding process.
BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 is a drawing illustrating an example of
partitioning a picture in HEVC;
FIG. 2 is a drawing illustrating an example of
partitioning a CTU including an edge of a picture;
FIG. 3 is a schematic view of a configuration of
a moving image encoding device according to an embodiment;
FIG. 4 is a drawing illustrating an example of
partitioning the CTU including a bottom edge of a picture;
FIG. 5 is a drawing illustrating an example of
partitioning the CTU including a right edge of a picture;
FIG. 6 is a drawing illustrating an example of
partitioning the CTU including both a bottom edge and a
right edge of a picture;
FIG. 7 is an operation flowchart of a
7g
Date Recue/Date Received 2021-09-20
CA 03078905 2020-04-09
process of determining a partitioning pattern and an
encoding mode by an encoding mode determining unit;
FIG. 8 is an operation flowchart of a
moving image encoding process;
FIG. 9 is a schematic block diagram of a
moving image decoding device;
FIG. 10 is an operation flowchart of a
partitioning pattern determining process performed
by a partitioning pattern determining unit;
FIG. 11 is an operation flowchart of a
moving image decoding process; and
FIG. 12 is a block diagram of a computer
operating as the moving image encoding device or the
moving image decoding device by executing a computer
program that implements a function of each part of
the moving image encoding device or the moving image
decoding device according to the embodiment or a
modified embodiment.
BEST MODE FOR CARRYING OUT THE INVENTION
In the following, a moving image encoding
device will be described with reference to the
drawings. First, partitioning of a CTU including an
edge of a picture will be described.
FIG. 2 is a drawing illustrating an
example of partitioning the CTU including an edge of
a picture. In
this example, since neither the
horizontal size nor the vertical size of a picture
200 is an integral multiple of the CTU size, each of
the right edge and the bottom edge of the picture
200 is included in CTUs at the right side or CTUs at
the bottom side. With
respect to a CTU 201
including the bottom edge of the picture 200 among
these CTUs, as illustrated in a partitioning pattern
210, the CTU 201 is partitioned so that a picture
edge 220 is not included in any of CUs 202. In such
a case, a CU 202 that is one-fourth of the size of
8
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
the CTU 201 is used to partition the CTU 201 using
the quadtree structure so that the picture edge 220
and a boundary between the CUs 202 are matched. As
a result, in this example, the CTU 201 is
partitioned into six CUs 202. Even
if each CU 202
is further partitioned using the binary tree
structure after the CTU 201 is partitioned using the
quadtree structure, the CTU 201 will be partitioned
using more CUs.
With respect to this, when the CTU 201
including the picture edge is divided applying the
binary tree structure from the beginning, the CTU
201 can be divided using non-square CUs 203 as
illustrated in a partitioning pattern 211. However,
by the related art in which the quadtree structure
is applied to divide the CTU into multiple sub-
blocks and then the binary tree structure is applied
to each sub-block, the CTU 201 is first divided into
square sub-blocks. Thus, the CTU 201 is not allowed
to be partitioned as in the partitioning pattern 211.
In an embodiment, the moving image
encoding device divides a block including either the
right edge or the bottom edge of the picture using
sub-blocks that have the lower encoding cost among
sub-blocks of the quadtree structure (i.e., squares)
and sub-blocks of the binary tree structure (i.e.,
rectangles). The moving image encoding device then
adds the syntax indicating whether the quadtree
structure or the binary tree structure has been
applied to the block including the picture edge, to
encoded moving image data.
As illustrated in FIG. 2, when the binary
tree structure is applied to the block including the
bottom edge of the picture to divide the block into
multiple sub-blocks, it is preferable to partition
the block along a direction orthogonal to the
picture edge in order to reduce the number of sub-
9
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
blocks. That
is, the block including the bottom
edge of the picture is preferably partitioned so
that a boundary line between the sub-blocks is
parallel to the picture edge. Thus, it is preferred
that the block including the bottom edge of the
picture is partitioned along the vertical direction
so that the boundary line between the sub-blocks is
horizontal.
Similarly, when the binary tree
structure is applied to a block including the right
edge of the picture, the block is preferably
partitioned along the horizontal direction so that
the boundary line between the sub-blocks is vertical.
Thus, the moving image encoding device is not
required to include a partitioning direction in the
encoded moving image data for the block to which the
binary tree structure is applied. Additionally, the
moving image encoding device applies the quadrant
structure to a block including both the bottom edge
and the right edge of the picture to divide the
block.
The picture may be either a frame or a
field. The
frame is a still image in the moving
image data, while the field is a still image
obtained by retrieving only odd rows or even rows
from the frame.
In the embodiment, the moving image
encoding device divides the picture by a CTU and
encodes the picture by a CTU, as in HEVC. However,
the moving image encoding apparatus may encode the
moving image data in accordance with other encoding
standards which divide the picture into multiple
blocks and encode each block.
FIG. 3 is a schematic view of a
configuration of the moving image encoding device
according to the embodiment. The
moving image
encoding device 1 includes a motion search unit 11,
an encoding mode determining unit 12, a prediction
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
block generator 13, a prediction encoder 14, a
decoder 15, a storage unit 16, and an entropy
encoder 17.
The moving image encoding device 1 encodes
each CTU of a picture to be encoded, in the order of
raster scanning. In the following, each part of the
moving image encoding device 1 will be described as
an example of processing one CTU.
When the picture to be encoded that
includes a CTU to be encoded is a P picture or a B
picture to which the inter prediction encoding
method is applicable, the motion search unit 11
calculates a motion vector for each applicable PU of
the CTU to be encoded. Here, a brightness component
is an example of a first component. A type of the
picture to be encoded is determined based on, for
example, a structure of a group of pictures (GOP)
which a controller (which is not illustrated)
applies to the moving image data to be encoded, and
a position in the GOP of the picture to be encoded.
The motion search unit 11 performs a block
matching operation to compare a PU of interest of
the CTU to be encoded with reference area of at
least one locally decoded picture and determines a
reference block that matches the PU of interest best.
The motion search unit 11 calculates a vector
indicating the amount of movement between the PU of
interest and the reference block as a motion vector.
The motion search unit 11 calculates motion vectors
for both an LO prediction and an Li prediction when
the picture to be encoded is the B picture to which
the bi-directional prediction encoding mode is
applicable. The
motion search unit 11 stores the
motion vector of each PU and information indicating
the locally decoded picture referenced by the motion
vector in the storage unit 16 and notifies the
encoding mode determining unit 12.
11
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
The encoding mode determining unit 12 is an
example of a partitioning pattern determining unit and
determines a partitioning pattern of the CU, the PU, and
the TU in which the CTU to be encoded is partitioned, and
the encoding mode applied to each CU. The
encoding mode
determining unit 12, for example, determines the encoding
mode applicable to the CTU based on information indicating
the type of the picture to be encoded including the CTU to
be encoded that is obtained from the controller (which is
not illustrated). The
encoding mode determining unit 12
selects the encoding mode to be actually applied from
among applicable encoding modes. When
the type of the
picture to be encoded is an I picture to which only the
intra prediction encoding method is applicable, the
encoding mode determining unit 12 selects the intra
prediction encoding method as the encoding mode to be
applied. When the type of the picture to be encoded is a
P picture or a B picture, the encoding mode determining
unit 12, for example, selects either the inter prediction
encoding method or the intra prediction encoding method as
the encoding mode to be applied.
The encoding mode determining unit 12 calculates
the encoding cost, which is an evaluation value of the
amount of encoded data of the CTU to be encoded with
respect to the applicable encoding mode, for each CU. For
example, in the inter prediction encoding method, the
encoding mode determining unit 12 calculates the encoding
cost for each combination of a CU partitioning pattern
that partitions the CTU, a PU partitioning pattern, and a
vector mode that defines a method for generating a
prediction vector of the motion vector. The encoding mode
determining unit 12 can use, for example, either an
advanced motion vector prediction (AMVP) mode or a merge
mode as the vector mode.
12
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
In the intra prediction encoding method,
the encoding mode determining unit 12 calculates the
encoding cost for each combination of the CU
partitioning pattern that partitions the CTU, the PU
partitioning pattern, and the prediction mode that
defines a reference direction in the picture.
In order to calculate the encoding cost,
for example, for the PU of interest, the encoding
mode determining unit 12 calculates a prediction
error, that is, the sum of absolute differences SAD,
in accordance with the following equation:
SAD = ZIOrgPixel-PredPixell
Here, OrgPixel is a value of a pixel included in the
PU of interest, and PredPixel is a value of a pixel
included in the prediction block corresponding to
the block of interest, generated in accordance with
the encoding mode being a calculation object of the
encoding cost.
The encoding mode determining unit 12
calculates the encoding cost of the CU of interest
according to the following equation for example.
Cost = ZSAD + A*B
Here, ZSAD is the sum of SAD calculated for
respective PUs included in the CU of interest. B is
an estimated value of code amount of elements other
than the prediction error, such as the motion vector
and a flag indicating the prediction mode. is
the
Lagrange multiplier.
The encoding mode determining unit 12 may
calculate the sum of absolute transformed
differences SATD of Hadamard coefficients of each
pixel that is obtained after the Hadamard transform
is applied to a differential image between the PU of
interest and the prediction block, instead of the
SAD.
The encoding mode determining unit 12 sets
the CU of interest, for example, in the order from a
13
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
larger size of the possible CU sizes in the CTU to
be encoded. The
encoding mode determining unit 12
selects a prediction mode that minimizes the cost
for each PU partitioning pattern for the CU of
interest with respect to the intra prediction
encoding method.
Additionally, the encoding mode
determining unit 12 selects a vector mode that
minimizes the cost for each PU partitioning pattern
for the CU of interest with respect to the inter
prediction encoding method.
Furthermore, the
encoding mode determining unit 12 selects an
encoding mode having a lower encoding cost from
among the intra prediction encoding method and the
inter prediction encoding method for each CU of the
same size, as the encoding mode to be applied to the
CU.
When the picture edge is not included in
the CU of interest, for each of the four CUs
generated by partitioning the CU of interest in
accordance with the quadtree structure, the encoding
mode determining unit 12 performs a process similar
to the process above as next CU of interest to
calculate the minimum encoding cost. If the sum of
the minimum encoding costs calculated for the
respective partitioned CUs is less than the minimum
encoding cost for the CU of interest, the encoding
mode determining unit 12 partitions the CU of
interest into four in accordance with the quadtree
structure. The
encoding mode determining unit 12
determines the CU partitioning pattern and the PU
partitioning pattern that are applied to the CTU to
be encoded by repeating the above-described process
until each CU is no longer partitioned.
When the CTU of interest or CU of interest
(which will be hereinafter referred to as the block
of interest) includes both the right edge and the
bottom edge of the picture, the encoding mode
14
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
determining unit 12 partitions the block of interest
into four in accordance with the quadtree structure.
This is because when the block of interest includes
both the right edge and the bottom edge of the
picture, it is necessary to partition the block of
interest for both horizontal and vertical directions
so that both the right edge and the bottom edge of
the picture are not included in any CU.
When the block of interest includes the
right edge of the picture and does not include the
bottom edge of the picture, the encoding mode
determining unit 12 partitions the block of interest
into four sub-blocks in accordance with the quadtree
structure.
Furthermore, the encoding mode
determining unit 12 partitions the block of interest
into two sub-blocks in the horizontal direction in
accordance with the binary tree structure.
Similarly, when the block of interest includes the
bottom edge of the picture and does not include the
right edge of the picture, the encoding mode
determining unit 12 partitions the block of interest
into four sub-blocks in accordance with the quadtree
structure and partitions the block of interest into
two sub-blocks in the vertical direction.
When any sub-block obtained by
partitioning the block of interest includes the
picture edge, the encoding mode determining unit 12
further partitions the sub-block including the
picture edge into four or two as described above.
The encoding mode determining unit 12 repeats the
above-described process until the picture edge is
not included in any sub-block.
However, with respect to a block that is
once partitioned along the horizontal direction in
accordance with the binary tree structure, the
encoding mode determining unit 12 partitions a sub-
block including the picture edge among sub-blocks
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
obtained by partitioning the block, also along the
horizontal direction in accordance with the binary
tree structure. Similarly, with respect to a block
that is once partitioned along the vertical
direction in accordance with the binary tree
structure, the encoding mode determining unit 12
partitions a sub-block including the picture edge
among sub-blocks obtained by partitioning the block,
also along the vertical direction in accordance with
the binary tree structure.
The encoding mode determining unit 12
performs a process similar to the process described
above for each combination of the obtained sub-
blocks to calculate the encoding cost. The encoding
mode determining unit 12 may select a combination of
sub-blocks having the minimum encoding cost and may
use sub-blocks included in the selected combination
as one CU.
FIG. 4 is a drawing illustrating an
example of partitioning the CTU including the bottom
edge of the picture. In the example illustrated in
FIG. 4, a CTU 400 includes a bottom picture edge 401.
Thus, the encoding mode determining unit 12 applies
the quadtree structure to the CTU 400 to partition
the CTU 400 into four square CUs 410-1 to 410-4, or
applies the binary tree structure to partition the
CTU 400 into two CUs 420-1 and 420-2 in the vertical
direction. The
encoding mode determining unit 12
may further partition the CU 410-1 and the CU 410-2
into four in accordance with the quadtree structure
because the CU 410-1 and the CU 410-2 do not include
the bottom picture edge 401. The
encoding mode
determining unit 12 may determine whether to
partition the CU 410-1 and the CU 410-2 into four
based on the encoding cost. Since the CU 410-3 and
the CU 410-4 include the bottom picture edge 401,
the encoding mode determining unit 12 partitions the
16
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
CU 410-3 and the CU 410-4 into four in accordance with the
quadtree structure or into two in accordance with the
binary tree structure in the vertical direction.
The encoding mode determining unit 12 may
further partition the CU 420-1, which does not include the
bottom picture edge 401, into two in accordance with the
binary tree structure in the vertical direction. The
encoding mode determining unit 12 may determine whether to
partition the CU 420-1 into two based on the encoding cost.
The encoding mode determining unit 12 further partitions
the CU 420-2, which includes the bottom picture edge 401,
into two CUs, which are the CU 421-1 and the CU 421-2, in
accordance with the binary tree structure in the vertical
direction.
Finally, the sum of the encoding costs of
respective CUs is calculated for each combination of CUs
obtained when all CUs do not include the bottom picture
edge 401, and the CTU 400 is partitioned according to the
combination of CUs that has the minimum sum. For example,
when the sum of the encoding costs for the combination of
the CU 420-1 and the CU 421-1 is minimum, the CTU 400 is
partitioned into the CU 420-1 and the CU 421-1. The
encoding mode determining unit 12 generates the syntax
indicating whether the quadtree structure or the binary
tree structure has been applied to the CTU or the CU at
each time of partitioning the CTU or the CU, and notifies
the entropy encoder 17 of the syntax. The
syntax, which
indicates whether the quadtree structure or the binary
tree structure has been applied, is an example of
partitioning information.
Here, with respect to CUs
obtained applying the binary tree structure, the syntax
indicating whether the quadtree structure or the binary
tree structure has been applied is not
17
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
necessary to be generated because the quadtree
structure is not applied to the CUs even if the CUs
are further partitioned.
FIG. 5 is a drawing illustrating an
example of partitioning the CTU including the right
edge of the picture. In the example illustrated in
FIG. 5, a CTU 500 includes a right picture edge 501.
Thus, the encoding mode determining unit 12 applies
the quadtree structure to the CTU 500 to partition
the CTU 500 into four square CUs 510-1 to 510-4, or
applies the binary tree structure to partition the
CTU 500 into two CUs 520-1 and 520-2 in the
horizontal direction. The encoding mode determining
unit 12 may further partition the CU 510-1 and the
CU 510-3 into four in accordance with the quadtree
structure because the CU 510-1 and the CU 510-3 do
not include the right picture edge 501. The
encoding mode determining unit 12 may determine
whether to partition the CU 510-1 and the CU 510-3
into four based on the encoding cost. Since the CU
510-2 and the CU 510-4 include the right picture
edge 501, the encoding mode determining unit 12
partitions the CU 510-2 and the CU 510-4 into four
in accordance with the quadtree structure or into
two in accordance with the binary tree structure in
the horizontal direction. Additionally, the
encoding mode determining unit 12 partitions the CU
520-2 including the right picture edge 501 into two
CUs, which are CUs 521-1 and 521-2, in the
horizontal direction in accordance with the binary
tree structure.
Finally, the sum of the encoding costs of
respective CUs is calculated for each combination of
CUs obtained when all CUs do not include the right
picture edge 501, and the CTU 500 is partitioned
according to the combination of CUs that has the
minimum sum.
18
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
FIG. 6 is a drawing illustrating an
example of partitioning the CTU including both the
bottom edge and the right edge of the picture. In
the example illustrated in FIG. 6, a CTU 600
includes a right picture edge 601 and a bottom
picture edge 602. Thus,
the encoding mode
determining unit 12 applies the quadtree structure
to the CTU 600 and partitions the CTU 600 into four
squares CUs 610-1 to 610-4. The
encoding mode
determining unit 12 may further partition the CU
610-1 into four in accordance with the quadtree
structure because the CU 610-1 does not include both
the right picture edge 601 and the bottom picture
edge 602. The encoding mode determining unit 12 may
determine whether to partition the CU 610-1 into
four based on the encoding cost.
Additionally,
since the CU 610-3 includes the bottom picture edge
602, the encoding mode determining unit 12 may
repeat partitioning in accordance with the quadtree
structure or the binary tree structure until the
bottom picture edge 602 is not included in the CU in
a manner similar to the CTU 400 illustrated in FIG.
4. Here,
since the CU 610-2 and CU 610-4 do not
include the picture, the CU 610-2 and the CU 610-4
are ignored.
The encoding mode determining unit 12
determines the TU partitioning pattern for each CU
partitioned in accordance with the CU partitioning
pattern determined as described above. At this time,
the encoding mode determining unit 12 calculates a
RD cost according to the following equation for each
applicable TU partitioning pattern.
[Equation (1)]
Cost =E (org(I)- 1decW + 2 bit (1)
19
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
Here, org(i) is a value of a pixel included in the
CU of interest, and ldec(i) indicates a value of a
decoded pixel obtained by encoding the CU using the
TU division pattern of interest and further decoding
the CU. Additionally, bit indicates the code amount
when the CU is encoded using the TU partitioning
pattern of interest. The
first term on the right
hand side of Equation (1) indicates encoding
distortion, and the second term on the right hand
side indicates the coding amount. Thus,
in the TU
division pattern having lowest RD cost, the encoding
distortion is optimally balanced with the code
amount.
The encoding mode determining unit 12 selects the TU
division pattern that minimizes the RD cost.
The encoding mode determining unit 12
notifies the prediction block generator 13 of the
combination of the CU and PU partitioning pattern
and the encoding mode that are selected for the CTU
to be encoded, and notifies the prediction encoder
14 of the TU partitioning pattern. The
encoding
mode determining unit 12 stores the combination of
the CU, PU, and TU partitioning patterns and the
encoding mode that are selected for the CTU to be
encoded, in the storage unit 16. Here,
the
information indicating the partitioning pattern that
partitions the CTU into CUs includes, for example,
information indicating whether each of the sub-
blocks obtained by recursively partitioning the CTU
has been partitioned.
Furthermore, the encoding
mode determining unit 12 generates the syntax
indicating whether the quadtree structure or the
binary tree structure has been applied to the CTU
including the picture edge and the sub-block
including the picture edge among the sub-blocks
obtained by recursively partitioning the CTU. The
encoding mode determining unit 12 passes the syntax
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
to the entropy encoder 17.
FIG. 7 is an operation flowchart of a
process of determining the partitioning pattern and
the encoding mode by the encoding mode determining
unit 12.
In step S101, the encoding mode determining unit 12
determines whether the block of interest includes
the picture edge. The
first block of interest is
the CTU to be encoded.
In step S102, when the block of interest
does not include the picture edge (NO in step S101),
the encoding mode determining unit 12 partitions the
block of interest so as to minimize the encoding
cost. Here, when the coding cost is smaller if the
block of interest is not partitioned, the block of
interest may not be further partitioned. When the
block of interest includes the picture edge (YES in
step S101), in step S103, the encoding mode
determining unit 12 determines whether the block of
interest includes both the right picture edge and
the bottom picture edge.
When the block of interest includes both
the right picture edge and the bottom picture edge
(YES in step S103), in step S104, the encoding mode
determining unit 12 partitions the block of interest
into four in accordance with the quadtree structure.
When the block of interest includes either the right
picture edge or the bottom picture edge (NO in step
S103), in step S105, the encoding mode determining
unit 12 determines whether a block including the
block of interest has been partitioned into two.
When the block including the block of
interest has been partitioned into two (YES in step
S105), in step S106, the encoding mode determining
unit 12 also partitions the block of interest into
two sub¨blocks. At
this time, the encoding mode
determining unit 12 may partition the block of
21
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
interest along the same direction as the
partitioning direction of the block including the
block of interest.
When the block including the block of
interest has not been partitioned into two (NO in
step S105), the encoding mode determining unit 12
partitions the block of interest into four sub-
blocks to generate four square sub-blocks. In step
S107, the encoding mode determining unit 12 further
partitions the block of interest into two sub-blocks
along the direction orthogonal to the picture edge
to generate two rectangular sub-blocks.
In step S108, the encoding mode
determining unit 12 determines whether a sub-block
including the picture edge is present after step
S102, step S104, step S106, or step S107. When the
picture edge is included in any sub-block (YES in
step S108), in step S109, the encoding mode
determining unit 12 sets each sub-block as the block
of interest. The encoding mode determining unit 12
performs the process as of step S101 for the block
of interest.
When the picture edge is not included in
any of the sub-blocks (NO in step S108), the
encoding mode determining unit 12 selects a
combination that minimizes the encoding cost from
the obtained combinations of blocks. In
step S110,
the encoding mode determining unit 12 determines the
CU, PU, and TU partitioning patterns and the
encoding mode to be applied according to the
selected combination. The encoding mode determining
unit 12 ends the process of determining the
partitioning pattern and the encoding mode.
The prediction block generator 13
generates a prediction block for each PU according
to the combination of the CU and PU partitioning
patterns and the encoding mode that are selected for
22
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
the CTU to be encoded.
For example, when the PU of interest is
encoded by the intra prediction encoding method, the
prediction block generator 13 generates the
prediction block based on values of pixels in the
locally decoded block around the PU, which is
referenced in accordance with the prediction mode
selected for the PU. When
the PU of interest is
encoded by the inter prediction encoding method, the
prediction block generator 13 generates the
prediction block by performing the motion
compensation on the locally decoded picture that is
read from the storage unit 16 and that is referenced
by the PU based on the motion vector calculated for
the PU.
The prediction block generator 13 passes
the generated prediction block to the prediction
encoder 14 and the decoder 15.
The prediction encoder 14 performs the
prediction encoding of the CTU to be encoded.
The prediction encoder 14 performs a
differential calculation between each pixel in the
CTU to be encoded and a corresponding pixel in the
prediction block. The prediction encoder 14 uses a
difference value corresponding to each pixel in a TU
obtained by the differential calculation for each TU
in the CTU to be encoded as the prediction error
signal of each pixel of the TU.
The prediction encoder 14 generates a list
of possible prediction vectors of each PU to be
encoded by the inter prediction encoding method
according to the vector mode determined to be
applied by the encoding mode determining unit 12.
The prediction encoder 14 calculates the prediction
error signal between the motion vector of the PU and
each of the possible prediction vectors. The
prediction encoder 14 determines the prediction
23
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
vector from among the possible prediction vectors
for each PU to be encoded by the inter prediction
encoding method, based on the prediction error
signal calculated for each of the possible
prediction vectors. The
prediction encoder 14
passes, for example, information determining the
prediction vector in the list of the possible
prediction vectors for the motion vector of each PU
and the prediction error signal between the motion
vector and the prediction vector, to the entropy
encoder 17.
The prediction encoder 14 obtains
orthogonal transformation coefficients indicating a
horizontal frequency component and a vertical
frequency component of the prediction error signal
by the orthogonal transformation of the prediction
error signal of each TU in the CTU to be encoded.
For example, the prediction encoder 14 performs a
discrete cosine transform (DCT) as an orthogonal
transformation process on the prediction error
signal to obtain a set of DCT coefficients as the
orthogonal transformation coefficients.
The prediction encoder 14 calculates
quantized orthogonal transformation coefficients by
quantizing the orthogonal
transformation
coefficients of each TU in the CTU to be encoded in
accordance with a quantization parameter that
includes a qp value specifying the quantization
width and the like. In the following, the quantized
orthogonal transformation coefficients may be simply
called the quantization coefficients.
The prediction encoder 14 outputs the quantized
orthogonal transformation coefficients to the
decoder 15 and the entropy encoder 17.
The decoder 15 generates the locally
decoded block referenced to encode, for example, the
CU after the TU, from the quantization coefficients
24
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
of each TU in the CTU to be encoded, and stores the
locally decoded block in the storage unit 16.
The decoder 15 restores the orthogonal
transformation coefficients before quantization by
performing the inverse quantization on the
quantization coefficients of each TU. For example,
the decoder 15 performs the inverse orthogonal
transformation on the restored
orthogonal
transformation coefficients for each TU. For
example, when the prediction encoder 14 uses DCT as
the orthogonal transformation, the decoder 15
performs the inverse DCT process as the inverse
orthogonal transformation. By
this, for each TU,
the decoder 15 restores the prediction error signal
having information similar to the prediction error
signal before encoding.
The decoder 15 generates the locally
decoded block by adding the restored prediction
error signal to a value of each pixel of the
prediction block of each TU.
The decoder 15 stores the locally decoded block in
the storage unit 16 every time the locally decoded
block is generated.
The decoder 15 writes the locally decoded
picture obtained by combining the locally decoded
blocks of one picture in accordance with the
encoding order of the CTUs, to the storage unit 16.
The storage unit 16 temporarily stores the
locally decoded block received from the decoder 15.
The storage unit 16 supplies the locally decoded
picture or the locally decoded block to the motion
search unit 11, the encoding mode determining unit
12, and the prediction block generator 13. The
storage unit 16 stores a predetermined number of the
locally decoded pictures that may be referenced by
the picture to be encoded. When the number of the
locally decoded pictures exceeds the predetermined
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
number, the storage unit 16 discards the locally
decoded picture in the order from the older encoding
time.
The storage unit 16 further stores the motion vector
for each of the locally decoded blocks encoded by
the inter prediction encoding method. Additionally,
the storage unit 16 stores the combination of the CU,
PU, and TU partitioning patterns and the encoding
mode selected for each CTU.
The entropy encoder 17 is an example of an
adding unit. The
entropy encoder 17 performs
entropy encoding of, for example, the quantization
coefficients and various syntax of each TU of the
CTU to be encoded. The
entropy encoder 17 also
performs entropy encoding of, for example,
information specifying the prediction vector in a
list of the possible prediction vectors for each PU
to be encoded by the inter prediction encoding
method. The
syntax includes syntax indicating an
applied one of the quadtree structure and the binary
tree structure for the CTU including the picture
edge and each sub-block that is obtained by
recursively partitioning the CTU and that includes
the picture edge.
In the embodiment, the entropy encoder 17
uses an arithmetic encoding process such as context-
based adaptive binary arithmetic coding (CABAC) as
an entropy encoding method. The entropy encoder 17
outputs a bit stream obtained by entropy encoding.
An encoded bit stream including encoded
moving image data is obtained by combining the bit
streams of respective CTUs output from the entropy
encoder 17 in a predetermined order and adding the
header information defined by the HEVC. The moving
image encoding device 1 stores the encoded bit
stream in a storage device (which is not
illustrated) including a magnetic recording medium,
26
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
an optical recording medium, or a semiconductor
memory, or outputs the encoded bit stream to another
device.
FIG. 8 is an operation flowchart of a
moving image encoding process performed by the
moving image encoding device 1. The
moving image
encoding device 1 performs the moving image encoding
process in accordance with the following operation
flowchart for each CTU.
In step S201, the motion search unit 11
calculates the motion vector for each PU in the CTU
to be encoded, to which the inter prediction
encoding method can be applied. The
motion search
unit 11 notifies the encoding mode determining unit
12 of the motion vector of each PU. When
the
picture to be encoded that includes the CTU to be
encoded is the B picture, the motion vector is
calculated for an LO direction and an Li direction.
When the picture to be encoded is the I picture, the
process of step S201 may be omitted.
In sLep 3202, the encoding mode
determining unit 12 determines the CU, PU, and TU
partitioning patterns and the encoding mode to be
applied so as to minimize the encoding cost of the
CTU to be encoded. The
encoding mode determining
unit 12 notifies the prediction block generator 13
of the CU and PU partitioning patterns and the
encoding mode to be applied, and notifies the
prediction encoder 14 of the TU partitioning pattern.
The encoding mode determining unit 12 stores the CU,
PU, and TU partitioning patterns and the encoding
mode to be applied in the storage unit 16.
In step S203, the prediction block
generator 13 generates the prediction block in
accordance with the determined CU and PU
partitioning patterns and the encoding mode to be
applied. The
prediction block generator 13 passes
27
Date Regue/Received date 2020-04-09
CA 03078905 2020-04-09
the generated prediction block to the prediction
encoder 14 and the decoder 15.
In step S204, the prediction encoder 14
calculates the prediction error signal between the
pixel of the CTU to be encoded and the corresponding
pixel of the prediction block. In
step S205, the
prediction encoder 14 calculates the orthogonal
transformation coefficients for each TU by
performing the orthogonal transformation on the
prediction error signal of each pixel for the TU.
In step S206, the prediction encoder 14 calculates
the quantization coefficients by quantizing the
orthogonal transformation coefficients of each TU of
the CTU to be encoded. The
prediction encoder 14
outputs the quantization coefficients of each TU to
the decoder 15 and the entropy encoder 17.
In step S207, the decoder 15 restores the
prediction error signal from the quantization
coefficients of each TU of the CTU to be encoded and
generates the locally decoded block corresponding to
the CTU based on the restored prediction error
signal and the corresponding prediction block. The
decoder 15 stores the locally decoded block in the
storage unit 16.
In step S208, the entropy encoder 17
performs entropy encoding of, for example, the
quantization coefficients and various syntax. The
various syntax includes syntax indicating whether
the quadtree structure or the binary tree structure
has been applied to the CTU or the CU including the
picture edge. The
entropy encoder 17 outputs the
obtained encoded bit stream. The
moving image
encoding device 1 then ends the moving image
encoding process for one CTU.
As described above, the moving image
encoding device partitions the block including
either the right picture edge or the bottom picture
28
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
edge in accordance with a structure with the smaller
encoding cost among the quadtree structure and the
binary tree structure in the direction orthogonal to
the picture edge. Thus,
the moving image encoding
device can apply the binary tree structure to the
block including the picture edge from the beginning,
and this can prevent the block including the picture
edge from being excessively partitioned. The moving
image encoding device adds the syntax indicating the
structure that has been applied to the block
including the picture edge among the quadtree
structure and the binary tree structure, to the
encoded moving image data. With
respect to this,
for the block to which the binary tree structure has
been applied, the syntax indicating the partitioning
direction may not be added to the encoded moving
image data.
Therefore, the moving image encoding
device can reduce the code amount of the information
indicating the partitioning pattern of the block
including the picture edge that is included in the
encoded moving image data. Accordingly, the moving
image encoding device can improve the encoding
efficiency even when the picture edge is included in
the block.
FIG. 9 is a schematic block diagram of a
moving image decoding device that decodes the moving
image data encoded by the moving image encoding
device according to the embodiment described above.
A moving image decoding device 2 includes an entropy
decoder 21, a partitioning pattern determining unit
22, a prediction block generator 23, a decoder 24,
and a storage unit 25.
Each of these parts of the moving image decoding
device 2 is formed as a separate circuit.
Alternatively, each of these parts of the moving
image decoding device 2 may be implemented in the
moving image decoding device 2 as a single
29
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
integrated circuit in which circuits corresponding
to respective parts are integrated.
Additionally,
each of these parts of the moving image decoding
device 2 may be a functional module implemented by a
computer program executed by a processor of the
moving image decoding device 2.
The moving image decoding device 2 obtains
the encoded bit stream including the encoded moving
image data, for example, through a communication
network and an interface circuit for connecting the
moving image decoding device 2 to the communication
network. The moving image decoding device 2 stores
the encoded bit stream in a buffer memory that is
not illustrated. The moving image decoding device 2
reads the encoded data of each CTU from the buffer
memory and inputs data of each CTU to the entropy
decoder 21.
The entropy decoder 21 performs entropy
decoding of the data encoded in each CTU. The
entropy decoder 21 decodes the quantization
coefficients of each TU in the CTU. The
entropy
decoder 21 performs entropy decoding of the
information specifying the motion vector for each PU
included in the CU encoded by the inter prediction
encoding method (for example, the information
indicating the vector mode to be applied and the
prediction vector of the motion vector).
Furthermore, the entropy decoder 21 performs entropy
decoding of the prediction mode for each PU included
in the CU encoded by the intra prediction encoding
method.
Further, the entropy decoder 21 performs
entropy decoding of the various syntax including the
partitioning pattern that has been applied and the
encoding mode. The
entropy decoder 21 passes the
syntax indicating the CU, PU, and TU partitioning
patterns to the partitioning pattern determining
unit 22 and the prediction block generator 23.
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
Further, the entropy decoder 21 passes the syntax
indicating whether the quadtree structure or the
binary tree structure has been applied to the CTU
including the picture edge and each of the sub-
blocks obtained by recursively partitioning the CTU
and including the picture edge, to the partitioning
pattern determining unit 22. The entropy decoder 21
passes other syntax and the like to the prediction
block generator 23. Further, the entropy decoder 21
passes the quantization coefficients to the decoder
24.
The partitioning pattern determining unit
22 partitions the CTU to be decoded into the CUs.
At this time, when the CTU to be decoded does not
include the picture edge, the partitioning pattern
determining unit 22 may partition the CTU to be
decoded into the CUs by referring to the syntax
indicating the partitioning pattern of the CTU to be
decoded, which is decoded by the entropy decoder 21.
With respect to the above, when the CTU to
be decoded includes either the right picture edge or
the bottom picture edge, the partitioning pattern
determining unit 22 partitions the CTU to be decoded
into four or two by referring to the syntax
indicating whether the quadtree structure or the
binary tree structure has been applied. That
is,
when the quadtree structure has been applied to the
CTU to be decoded, the partitioning pattern
determining unit 22 partitions the CTU to be decoded
into four. When the binary tree structure has been
applied to the CTU to be decoded, the partitioning
pattern determining unit 22 partitions the CTU to be
decoded into two. At this time, the partitioning
pattern determining unit 22 may partition the CTU to
be decoded into two along the direction orthogonal
to the picture edge included in the CTU to be
decoded. That
is, when the CTU to be decoded
31
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
includes the right picture edge, the partitioning
pattern determining unit 22 partitions the CTU to be
decoded into two along the horizontal direction.
When the CTU to be decoded includes the bottom
picture edge, the partitioning pattern determining
unit 22 partitions the CTU to be decoded in two
along the vertical direction.
When the CTU to be decoded includes both
the right picture edge and the bottom picture edge,
the partitioning pattern determining unit 22
partitions the CTU to be decoded into four.
The partitioning pattern determining unit
22 may perform a process similar to the process
performed on the CTU to be decoded, on each sub-
block obtained by partitioning the CTU to be decoded.
When a sub-block does not include the picture edge
and the decoded syntax indicates the sub-block is
not further partitioned, the sub-block is one CU.
FIG. 10 is an operation flowchart of a
partitioning pattern determining process performed
by the partitioning pattern determining unit 22.
In step S301, the partitioning pattern determining
unit 22 determines whether the block of interest
includes the picture edge. The
first block of
interest is the CTU to be decoded.
When the block of interest includes the
picture edge (YES in step S301), in step S302, the
partitioning pattern determining unit 22 determines
whether the block of interest includes both the
right picture edge and the bottom picture edge.
When the block of interest includes both
the right picture edge and the bottom picture edge
(YES in step S302), in step S303, the partitioning
pattern determining unit 22 partitions the block of
interest into four in accordance with the quadtree
structure. When
the block of interest includes
either the right picture edge or the bottom picture
32
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
edge (NO in step S302), in step S304, the partitioning
pattern determining unit 22 determines whether a block
including the block of interest has been partitioned into
two.
When the block including the block of interest
has been partitioned into two (YES in step S304), in step
S305, the partitioning pattern determining unit 22
partitions the block of interest into two sub-blocks. At
this time, the partitioning pattern determining unit 22
may partition the block of interest along the same
direction as the partitioning direction of the block
including the block of interest.
When the block including the block of interest
has not been partitioned into two (NO in step S304), in
step S306, the partitioning pattern determining unit 22
partitions the block of interest in accordance with the
structure indicated by the syntax among the quadtree
structure and the binary tree structure.
In step S307, after step S303, S305, or S306,
the partitioning pattern determining unit 22 sets each of
the sub-blocks obtained by partitioning the block of
interest, as the block of interest. The
partitioning
pattern determining unit 22 performs the process as of
step S301 on each block of interest.
In step S301, when the block of interest does
not include the picture edge (NO in step S301), in step
S308, the partitioning pattern determining unit 22
partitions the block of interest into the CUs in
accordance with the partitioning pattern indicated by the
syntax.
When no block includes the picture edge, the
partitioning pattern determining unit 22 ends the
partitioning pattern determining process.
The partitioning pattern determining unit 22
notifies the prediction block generator 23 of the
33
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
information indicating each CU included in the CTU
to be decoded.
For each CU included in the CTU to be
decoded, the prediction block generator 23 generates
the prediction block of each PU included in the CU
by referring to the decoded picture or the decoded
region of the picture to be decoded in accordance
with the encoding mode and the PU partitioning
pattern that have been applied. At this time, the
prediction block generator 23 also decodes the
moving vector from, for example, the information
indicating the vector mode that has been applied and
the prediction error signal of the moving vector.
The prediction block generator 23
generates the prediction block for each PU of the
CTU to be decoded in accordance with the encoding
mode to be applied to the PU in a manner similar to
the prediction block generator 13 of the moving
image encoding device 1. That
is, the prediction
block generator 23 determines an area referenced by
a decoded reference picture or the picture to be
decoded in accordance with the encoded mode decoded
by entropy decoding and generates the prediction
block for each PU based on the determined area. At
this time, when the PU to be decoded is encoded by
the inter prediction encoding method, the prediction
block generator 23 may determine the area referenced
by the decoded reference picture using the motion
vector decoded for the PU. When
the PU to be
decoded is encoded by the intra prediction encoding
method, the prediction block generator 23 may
determine the area referenced by the picture to be
decoded in accordance with the decoded prediction
mode.
The prediction block generator 23 outputs
the generated prediction block to the decoder 24.
The decoder 24 performs the inverse
34
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
quantization by multiplying a predetermined number
corresponding to the quantization width determined
by the quantization parameter obtained from the
decoded header information to the quantization
coefficients of each TU received from the entropy
decoder 21. The
inverse quantization restores the
orthogonal transformation coefficients of each TU.
Subsequently, the decoder 24 performs an inverse
orthogonal transformation process on the orthogonal
transformation coefficients for each TU. By
performing the inverse quantization process and the
inverse orthogonal transformation process on the
quantization coefficients of each TU, the prediction
error signal of each pixel in the whole CTU is
reproduced.
The decoder 24 can decode the PU by adding
a value of each pixel of the prediction block of the
PU and the reproduced prediction error signal
corresponding to the pixel. The decoder 24 decodes
the CTU by combining the decoded PUs in accordance
with the encoding order. The decoder 24 stores the
decoded CTU in the storage unit 25. The decoder 24
decodes the entire picture by combining the decoded
CTUs in accordance with the encoding order. The
decoder 24 stores the decoded picture in the storage
unit 25 and stores the decoded picture in the buffer
memory. Each
decoded picture stored in the buffer
memory is output to a display device (which is not
illustrated) in accordance with a display order by a
controller (which is not illustrated).
The storage unit 25 temporarily stores the
decoded CTU and the decoded picture received from
the decoder 24. The
storage unit 25 supplies the
prediction block generator 23 with the CTU as the
reference area or with the picture as the reference
picture. The storage unit 25 stores a predetermined
number of pictures and discards pictures in the
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
order from the older encoding time when the amount
of the stored data exceeds the amount corresponding
to the predetermined number of pictures.
FIG. 11 is an operation flowchart of a
moving image decoding process performed by the
moving image decoding device 2. The
moving image
decoding device 2 performs the moving image decoding
process illustrated in FIG. 11 for each CTU to be
decoded.
The entropy decoder 21 performs entropy decoding of
the data encoded in each CTU. In
step S401, the
entropy decoder 21 decodes the quantization
coefficients, various syntax of each TU of the CTU
to be decoded, and so on.
In step S402, the partitioning pattern
determining unit 22 determines each CU included in
the CTU to be decoded. At
this time, the
partitioning pattern determining unit 22 may
determine each CU in accordance with the flowchart
illustrated in FIG. 10.
In step S403, the prediction block
generator 23 generates the prediction block for each
CU of the CTU to be decoded by referring to the
encoding mode applied to each PU included in the CU.
The decoder 24 performs the inverse
quantization by multiplying a predetermined number
corresponding to the quantization width determined
by the quantization parameter obtained from the
header information included in the encoding bit
stream to the quantization coefficients received
from the entropy decoder 21. The
decoder 24
reproduces the prediction error signal of each pixel
of the CTU to be decoded by performing the inverse
orthogonal transformation on the orthogonal
transformation signal for each TU. Subsequently, in
step S404, the decoder 24 reproduces the CTU to be
decoded by adding each pixel value of the prediction
36
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
block and the reproduced prediction error signal of
a corresponding pixel. The
decoder 24 stores the
reproduced CTU in the storage unit 25. The moving
image decoding device 2 ends the moving image
decoding process for the CTU to be decoded.
As described above, the moving image
decoding device can decode the encoded moving image
data even if the binary structure is applied to the
block including the picture edge by the moving image
encoding device according to the above-described
embodiment.
According to a modified embodiment, the
encoding mode determining unit 12 of the moving
image encoding device 1 may also generate syntax
indicating the partitioning direction for a block
partitioned into two in accordance with the binary
tree structure. The entropy encoder 17 may add the
syntax indicating the partitioning direction to the
encoded moving image data for each block partitioned
into two in accordance with the binary tree
structure. This
explicitly transmits the
partitioning direction to the moving image decoding
device 2 with respect to the block partitioned into
two in accordance with the binary tree structure.
Therefore, by referring to the syntax indicating the
partitioning direction that is decoded by the
entropy decoder 21, the partitioning pattern
determining unit 22 of the moving image decoding
device 2 may partition a block, to which the syntax
indicating that the binary tree structure has been
applied is added, into two along the partitioning
direction.
According to another modified embodiment,
the prediction block may be generated for each CU.
Alternatively, the orthogonal transformation may be
performed for each CU. In
this case, the encoding
mode determining unit 12 of the moving image
37
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
encoding device 1 does not need to obtain the PU
partitioning pattern or the TU partitioning pattern.
Alternatively, it may not be required to
determine whether the picture edge is included with
respect to the CU. In this case, the encoding mode
determining unit 12 of the moving image encoding
device 1 may determine the partitioning pattern for
the PU including the picture edge in a manner
similar to the CU in the above-described embodiment.
Similarly, the encoding mode determining unit 12 may
determine the partitioning pattern for the TU
including the picture edge in a manner similar to
the CU in the above-described embodiment. In
this
case, the partitioning pattern determining unit 22
of the moving image decoding device 2 may determine
the partitioning pattern in a manner similar to the
above-described embodiment when the CTU to be
decoded is partitioned by the PUs or the TUs.
According to another modified embodiment,
the CTU that does not include the picture edge may
also be recursively partitioned into two in
accordance with the binary tree structure. In this
case, the encoding mode determining unit 12 of the
moving image encoding device 1 may calculate the
encoding cost of the CTU of interest or the
respective sub-blocks obtained by partitioning the
CTU of interest when the CTU is partitioned into
four sub-blocks in accordance with the quadtree
structure and when the CTU is partitioned into two
sub-blocks in accordance with the binary tree
structure. The
encoding mode determining unit 12
may then determine whether the quadtree structure is
to be applied or the binary tree structure is to be
applied so as to minimize the encoding cost. In
this case, the encoding mode determining unit 12
generates the syntax indicating the structure that
has been applied among the quadtree structure and
38
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
the binary tree structure for the CTU of interest or
respective sub-blocks obtained by recursively partitioning
the CTU of interest.
Furthermore, the encoding mode
determining unit 12 generates the syntax indicating the
partitioning direction for the CTU or the sub-blocks to
which the binary tree structure is applied. The
entropy
encoder 17 of the moving image encoding device 1 includes
the syntax indicating the structure that has been applied
and the syntax indicating the partitioning direction in
the encoded moving image data. Further, the partitioning
pattern determining unit 22 of the moving image decoding
device 2 may determine the CU partitioning pattern of the
CTU to be decoded by referring to the syntax indicating
the structure that has been applied and the syntax
indicating the partitioning direction.
FIG. 12 is a block diagram of a computer
operating as the moving image encoding device or the
moving image decoding device by executing a computer
program that implements a function of each part of the
moving image encoding device or the moving image decoding
device according to the above-described embodiment or a
modified embodiment.
A computer 700 includes a user interface 701, a
communication interface 702, a memory 703, a storage
medium access device 704, and a processor 705. The
processor 705 is connected to the user interface 701, the
communication interface 702, the memory 703, and the
storage medium access device 704 through a bus for example.
The user interface 701 includes, for example, an
input device such as a keyboard and a mouse, and a display
device such as a liquid crystal display. Alternatively,
the user interface 701 may include an integrated input and
display device, such as a touch panel display. The
user
interface 701, for example, outputs an operation signal
that selects the moving image data to be encoded or the
moving image data to be decoded to the processor 705 in
39
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
response to the operation of the user. The moving image
data to be encoded or the moving image data to be decoded
may be determined by an application program running on the
processor 705.
The communication interface 702 includes a
communication interface and a control circuit for
connecting to a communication network in accordance with a
communication standard, such as Ethernet (registered
trademark). The communication interface 702 obtains the
moving image data to be encoded from another device
connected to the communication network and passes the
moving image data to be encoded to the processor 705. The
communication interface 702 may also output the encoded
moving image data received from the processor 705 to
another device through the communication network. The
communication interface 702 may also obtain a bit stream
including the encoded moving image data to be decoded from
another device connected to the communication network and
may pass the bit stream to the processor 705.
The memory 703 is an example of a storage unit,
and includes, for example, a readable and writable
semiconductor memory and a read-only semiconductor memory.
The memory 703 stores the computer program for executing
the moving image encoding process or the computer program
for executing the moving image decoding process that is
executed on the processor 705.
Further, the memory 703
stores data generated during or as a result of the moving
image encoding process or the moving image decoding
process.
The storage medium access device 704 is another
example of the storage unit, and is a device that accesses
the storage medium 706, such as a magnetic disk, a
semiconductor memory card, and an optical storage medium.
The storage medium access device 704, for example, reads
the computer program for the moving image encoding process
or the computer program for the moving image decoding
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
process that is executed on the processor 705 and that is
stored in the storage medium 706, and passes the program
to the processor 705.
The processor 705 includes, for example, at
least one of a central processing unit (CPU), a graphics
processing unit (GPU), and a numeric data processor. The
processor 705 encodes the moving image data by executing
the computer program for the moving image encoding process
according to the embodiment or the modified embodiment
described above. The
processor 705 then stores the
encoded moving image data in the memory 703 or outputs the
encoded moving image data to another device through the
communication interface 702. Alternatively, the processor
705 decodes the encoded moving image data by executing the
computer program for the moving image decoding process
according to the embodiment or the modified embodiment
described above. The
processor 705 then causes the
display device of the user interface 701 to display the
decoded picture.
The computer program that can execute the
function of each part of the moving image encoding device
1 on the processor may be provided in a form recorded in a
computer-readable medium. Similarly, the computer program
that can execute the function of each part of the moving
image decoding device 2 on the processor may be provided
in a form recorded in a computer-readable medium. However,
such a recording medium does not include a carrier wave.
All examples and conditional language recited
herein are intended for pedagogical purposes to aid the
reader in understanding the invention and the concepts
contributed by the inventor to furthering the art, and are
to be construed as being without limitation to such
specifically recited examples and conditions, nor does the
organization of such examples in the specification relate
to a showing of the superiority and inferiority of the
invention.
Although the embodiment(s) of the present
41
Date Recue/Received date 2020-04-09
CA 03078905 2020-04-09
86281021
inventions have been described in detail, it should be
understood that the various changes, substitutions, and
alterations could be made hereto without departing from
the spirit and scope of the invention.
EXPLANATION OF REFERENCE NUMERALS
1 moving image coding device
11 motion search unit
12 encoding mode determining unit
13 prediction block generator
14 prediction encoder
15 decoder
16 storage unit
17 entropy encoder
2 moving image decoding device
21 entropy decoder
22 partitioning pattern determining unit
23 prediction block generator
24 decoder
25 storage unit
700 computer
701 user interface
702 communication interface
703 memory
704 storage medium access device
705 processor
706 storage medium
42
Date Recue/Received date 2020-04-09
