Method and apparatus for encoding and decoding a video
Method and apparatus for encoding and decoding a video. A method and an apparatus for encoding a video are disclosed. Such a method comprises, for at least one block having a size N which is not a power of 2 along at least one dimension: —determining ( 40 ) a predicted block for said at least one block, —obtaining ( 41 ) a residual block from said at least one block and said predicted block, —performing ( 42 ) block transform of said residual block, said residual block having a size N, —encoding ( 43 ) said transformed residual block. Corresponding method and apparatus for decoding a video are also disclosed.
1. A method for encoding a video comprising, for at least one block having a size N which is other than a power of 2 along one dimension:
determining a predicted block for said at least one block;
obtaining a residual block from said at least one block and said predicted block;
performing block transform of said residual block, said residual block having a size N along one dimension,
wherein said block transform involves separate application of one-dimensional (1D) horizontal transform and 1D vertical transform,
wherein said 1D horizontal or vertical transform for said one dimension of said residual block is based on a transform matrix A N represented by:
A
N
=
2
N
(
c
(
k
)
×
cos
(
(
2
×
j
+
1
)
×
k
π
2
×
N
)
)
k
,
j
∈
[
0
,
N
-
1
]
,
with k an integer k≥0,
c
(
k
)
=
{
1
2
if
k
=
0
,
1
if
k
>
0
}
,
wherein performing said 1D transform for said one dimension of said residual block comprises at least performing butterfly operations converting from a spatial domain to a transform domain a sample vector of size 3, said sample vector being based on samples of a row or a column of said residual block,
wherein said butterfly operations are represented by:
E 1 =x 1 +x 3 ,
E 2 =x 1 −x 3 ,
t 1 =( E 1 +x 2 )× A 3 (1,1),
t 2 =E 2 ×A 3 (2,1),
t 3 =E 1 ×A 3 (3,1)− x 2 ,
where
[
x
1
x
2
x
3
]
represents said sample vector of size 3 from said spatial domain,
[
t
1
t
2
t
3
]
represents a resulting sample vector of size 3 from said transform domain, and E 1 and E 2 represent intermediate values for butterfly design used for computing samples from said transform domain; and
encoding said transformed residual block.
2. The method according to claim 1 , wherein N is a multiple of 3.
3. The method for encoding according to claim 2 , wherein said butterfly operations implement a transform matrix of size 3×3, said sample vector comprising:
samples of a row or a column of said residual block along said one dimension in the case where N equals 3, and
linear combinations of samples of a row or a column of said residual block taken along said one dimension in the case where N is higher than 3.
4. The method according to claim 1 , said method further comprising, for N>3:
performing butterfly operations converting from a spatial domain to a transform domain a sample vector of size N/2, wherein said butterfly operations implement a complementary matrix transform X N represented by:
X
N
=
cos
(
(
2
j
+
1
)
×
(
2
k
+
1
)
π
2
N
)
k
,
j
∈
[
0
,
N
/
2
]
.
5. The method according to claim 4 , wherein butterfly operations converting from a spatial domain to a transform domain a sample vector of size 6, comprises at least the following operations:
E 1 =X 6 (1,1)× v 1 +X 6 (3,1)× v 3 ,
E 2 =X 6 (2,1)× v 2 ,
E 3 =X 6 (3,1)× v 1 +X 6 (1,1)× v 3 ,
u 1 =E 1 +E 2
u 2 =E 1 −E 2 −E 3
u 3 =E 2 +E 3
where
[
v
1
v
2
v
3
]
=
[
x
1
-
x
6
x
2
-
x
5
x
3
-
x
4
]
is obtained from said sample vector of size 6 from said spatial domain, E 1 , E 2 and E 3 represent intermediate values for butterfly design further used for computing transformed samples from said transformed residual block, X 6 (k,j) represent corresponding values of the complementary matrix transform and
[
u
1
u
2
u
3
]
is the resulting vector of samples in the transform domain.
6. The method according to claim 1 , wherein, for N>3, a butterfly implementation of said matrix transform A N is based on a matrix P l (A N ) corresponding to a matrix wherein N/2 first lines of P l (A N ) corresponds to odd lines of A N and N/2 last lines of P l (A N ) corresponds to even lines of A N .
7. The method according to claim 4 , wherein said matrix P l (A N ) is represented by:
P
l
(
A
N
)
=
2
N
(
N
/
2
2
×
A
N
/
2
N
/
2
2
×
A
N
/
2
_
X
N
-
X
N
_
)
,
where A N/2 represents a vertically flipped version of the matrix A N/2 , and −X N represents an opposed vertically flipped version of said complementary matrix transform X N .
8. A method for decoding a video comprising, for at least one block having a size N which is other than a power of 2 along one dimension:
decoding a transformed residual block;
performing inverse block transform of said transformed residual block, said residual block having a size N along one dimension,
wherein said inverse block transform involves separate application of one-dimensional (1D) horizontal inverse transforms and 1D vertical inverse transform,
wherein said 1D horizontal or vertical inverse transform for said one dimension is based on a transform matrix S N represented by:
S
N
=
2
N
(
c
(
k
)
×
cos
(
(
2
×
j
+
1
)
×
k
π
2
×
N
)
)
j
,
k
∈
[
0
,
N
-
1
]
,
with k an integer k≥0,
c
(
k
)
=
{
1
2
if
k
=
0
,
1
if
k
>
0
}
.
wherein performing said 1D inverse transform of said transformed residual block comprises at least performing butterfly operations converting from a transform domain to a spatial domain a sample vector of size 3, said sample vector being based on samples of a row or a column of said transformed residual block,
wherein said butterfly operations are represented by:
E 1 =t 1 ×S 3 (1,1),
E 2 =t 2 ×S 3 (1,2),
E 3 =t 3 ×S 3 (1,3),
x 1 =E 1 +E 2 +E 3 ,
x 2 =E 1 −t 3 ,
x 3 =E 1 −E 2 +E 3 ,
where
[
x
1
x
2
x
3
]
represents a resulting sample vector of size 3 from said spatial domain,
[
t
1
t
2
t
3
]
represents said sample vector of size 3 from said transform domain, and E 1 , E 2 and E 3 represent intermediate values for butterfly design used for computing samples from said spatial domain;
determining a predicted block for said at least one block; and
reconstructing said at least one block from said inverse transformed residual block and said predicted block.
9. The method according to claim 8 , wherein N is a multiple of 3.
10. The method according to claim 9 , wherein said butterfly operations implement a transform matrix of size 3×3, said sample vector comprising:
samples of a row or a column of said transformed residual block along said one dimension in the case where N equals 3, and
linear combinations of samples of a row or a column of said transformed residual block taken along said one dimension in the case where N is higher than 3.
11. The method according to claim 8 , said method further comprising, for N>3:
performing butterfly operations converting from a transform domain to a spatial domain a sample vector of size N/2, wherein said butterfly operations implement a complementary matrix transform X N represented by:
X
N
=
cos
(
(
2
j
+
1
)
×
(
2
k
+
1
)
π
2
N
)
k
,
j
ϵ
[
0
,
N
/
2
]
.
12. The method according to claim 11 , wherein butterfly operations converting from a transform domain to a spatial domain a sample vector of size 6, comprises at least the following operations:
E 1 =X 6 (1,1)× u 1 +X 6 (3,1)× u 3 ,
E 2 =X 6 (2,1)× u 2 ,
E 3 =X 6 (3,1)× u 1 +X 6 (1,1)× u 3 ,
v 1 =E 1 +E 2
v 2 =E 1 −E 2 −E 3
v 3 =E 2 +E 3
where
[
u
1
u
2
u
3
]
represents said sample vector of size 3 from said transform domain, E 1 , E 2 and E 3 represent intermediate values for butterfly design further used for computing transformed samples from said transformed residual block, X 6 (k,j) represent corresponding values of the complementary matrix transform and
[
v
1
v
2
v
3
]
is the resulting vector of samples in the spatial domain.
13. The method according to claim 11 , wherein said butterfly operations implementing said matrix transform X N uses linear combinations of columns from said matrix transform X N .
14. The method according to claim 8 , wherein, for N>3, a butterfly implementation of said matrix transform S N is based on a matrix P c (S N ) corresponding to a matrix wherein N/2 first column of P c (S N ) corresponds to even columns of S N and N/2 last columns of (S N ) corresponds to odd columns of S N .
15. A method according to claim 14 , wherein said matrix P c (S N ) is represented by:
P
c
(
S
N
)
=
2
N
(
N
/
2
2
×
S
N
/
2
X
N
N
/
2
2
×
)
,
where represents a horizontally flipped version of the matrix S N/2 , and represents an opposed horizontally flipped version of said complementary matrix transform X N .
16. An apparatus for encoding a video comprising one or more processors, wherein said one or more processors are configured to, for at least one block having a size N which is other than a power of 2 along one dimension:
determine a predicted block for said at least one block;
obtain a residual block from said at least one block and said predicted block;
perform block transform of said residual block, said residual block having a size N along one dimension,
wherein said block transform involves separate application of one-dimensional (1D) horizontal transform and 1D vertical transform,
wherein said 1D horizontal or vertical transform for said one dimension of said residual block is based on a transform matrix A N represented by:
A
N
=
2
N
(
c
(
k
)
×
cos
(
(
2
×
j
+
1
)
×
k
π
2
×
N
)
)
k
,
j
∈
[
0
,
N
-
1
]
,
with k an integer
k
≥
0
,
c
(
k
)
=
{
1
2
if
k
=
0
,
1
if
k
>
0
}
,
wherein said 1D transform for said one dimension of said residual block is performed by using butterfly operations converting from a spatial domain to a transform domain a sample vector of size 3, said sample vector being based on samples of a row or a column of said residual block,
wherein said butterfly operations are represented by:
E 1 =x 1 +x 3 ,
E 2 =x 1 −x 3 ,
t 1 =( E 1 +x 2 )× A 3 (1,1),
t 2 =E 2 ×A 3 (2,1),
t 3 =E 1 ×A 3 (3,1)− x 2 ,
where
[
x
1
x
2
x
3
]
represents said sample vector of size 3 from said spatial domain,
[
t
1
t
2
t
3
]
represents a resulting sample vector of size 3 from said transform domain, and E 1 and E 2 represent intermediate values for butterfly design used for computing samples from said transform domain; and
encode said transformed residual block.
17. An apparatus for decoding a video comprising one or more processors, wherein said one or more processors are configured to, for at least one block having a size N which is other than a power of 2 along one dimension:
decode a transformed residual block;
perform inverse block transform of said transformed residual block, said residual block having a size N along one dimension,
wherein said block transform involves separate application of one-dimensional (1D) horizontal inverse transform and 1D vertical inverse transform,
wherein said 1D horizontal or vertical inverse transform for said one dimension of said transformed residual block is based on a transform matrix S N represented by:
S
N
=
2
N
(
c
(
k
)
×
cos
(
(
2
×
j
+
1
)
×
k
π
2
×
N
)
)
j
,
k
∈
[
0
,
N
-
1
]
,
with k an integer k≥0,
c
(
k
)
=
{
1
2
if
k
=
0
1
if
k
>
0
}
,
wherein said 1D inverse transform of said transformed residual block is performed by using butterfly operations converting from a spatial domain to a transform domain a sample vector of size 3, said sample vector being based on samples of a row or a column of said transformed residual block,
wherein said butterfly operations are represented by:
E 1 =x 1 +x 3 ,
E 2 =x 1 −x 3 ,
t 1 =( E 1 +x 2 )× A 3 (1,1),
t 2 =E 2 ×A 3 (2,1),
t 3 =E 1 ×A 3 (3,1)− x 2 ,
where
[
x
1
x
2
x
3
]
represents said sample vector of size 3 from said spatial domain,
[
t
1
t
2
t
3
]
represents a resulting sample vector of size 3 from said transform domain, E 1 and E 2 represent intermediate values for butterfly design used for computing samples from said transform domain, A 3 (k,j) represent multiplicative factors;
determine a predicted block for said at least one block; and
reconstruct said at least one block from said inverse transformed residual block and said predicted block.
18. The apparatus according to claim 16 , wherein N is a multiple of 3.
19. The apparatus according to claim 18 , wherein said butterfly operations implement a transform matrix of size 3×3, said sample vector comprising:
samples of a row or a column of said residual block along said one dimension in the case where N equals 3, and
linear combinations of samples of a row or a column of said residual block taken along said one dimension in the case where N is higher than 3.
20. The apparatus according to claim 16 , said one or more processors further configured to, for N>3:
perform butterfly operations converting from a spatial domain to a transform domain a sample vector of size N/2, wherein said butterfly operations implement a complementary matrix transform X N represented by:
X
N
=
cos
(
(
2
j
+
1
)
×
(
2
k
+
1
)
π
2
N
)
k
,
j
ϵ
[
0
,
N
/
2
]
.
21. The apparatus according to claim 17 , wherein N is a multiple of 3.
22. The apparatus according to claim 21 , wherein said butterfly operations implement a transform matrix of size 3×3, said sample vector comprising:
samples of a row or a column of said transformed residual block along said at least one dimension in the case where N equals 3, and
linear combinations of samples of a row or a column of said transformed residual block taken along said at least one dimension in the case where N is higher than 3.
23. The apparatus according to claim 17 , wherein said one or more processors are further configured to, for N>3:
perform butterfly operations converting from a transform domain to a spatial domain a sample vector of size N/2, wherein said butterfly operations implement a complementary matrix transform X N represented by:
X
N
=
cos
(
(
2
j
+
1
)
×
(
2
k
+
1
)
π
2
N
)
k
,
j
ϵ
[
0
,
N
/
2
]
.