Adaptive interlace-to-progressive scan conversion algorithm
View Patent ↗An interlace-to-progressive scan conversion system comprises: a spatial line averaging prefilter; a motion estimator; a three-stage adaptive recursive filter. The motion estimator comprises: a 3-D recursive search sub-component having a bilinear interpolator; a motion correction sub-component having an error-function including penalties related to the difference between a given candidate vector and a plurality of neighboring vectors; a block erosion sub-component. The motion estimator assumes that motion is constant between fields. The three-stage adaptive recursive filter comprises: a first stage that selects between using static pixels data and moving pixels data from a next field; a second stage that selects a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; a third stage that combines an intra-field interpolation with the more valid set of data selected by the second stage.
1. An interlace-to-progressive scan conversion system, comprising:
a prefilter having a prefiltered signal as an output;
a motion estimator having the prefiltered signal as input and a motion-corrected signal as an output;
an adaptive filter having the prefiltered signal and the motion-corrected signal as inputs; wherein:
the adaptive filter comprises a three-stage adaptive recursive filter, wherein:
a first stage comprises a function that selects between using static pixels data and moving pixels data from a next field;
a second stage comprises a function that selects a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
a third stage comprises a function that combines an intra-field interpolation with the more valid set of data selected by the second stage.
2. The interlace-to-progressive scan conversion system of claim 1 , wherein the prefilter comprises a spatial line average filter.
3. The interlace-to-progressive scan conversion system of claim 1 , wherein the motion estimator comprises a 3-D recursive search sub-component.
4. The interlace-to-progressive scan conversion system of claim 1 , wherein the motion estimator comprises a motion vector correction sub-component.
5. The interlace-to-progressive scan conversion system of claim 1 , wherein the motion estimator comprises a block erosion sub-component.
6. An interlace-to-progressive scan conversion system, comprising:
a spatial line averaging prefilter having a prefiltered signal as an output;
a motion estimator having the prefiltered signal as input and a motion-corrected signal as an output, the motion estimator comprising:
a 3-D recursive search sub-component;
a motion vector correction sub-component;
a block erosion sub-component;
a three-stage adaptive recursive filter, wherein:
a first stage comprises a function that selects between using static pixels data and moving pixels data from a next field;
a second stage comprises a function that selects a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
a third stage comprises a function that combines an intra-field interpolation with the more valid set of data selected by the second stage.
7. The interlace-to-progressive scan conversion system of claim 6 , wherein the 3-D recursive search sub-component resolves motion vectors to at least quarter-pixel accuracy.
8. The interlace-to-progressive scan conversion system of claim 7 , wherein the look-up table consists of:
US
n
=
{
(
0
0
)
,
(
0
1
)
,
(
0
-
1
)
,
(
1
0
)
,
(
-
1
0
)
,
(
0
2
)
,
(
0
-
2
)
,
(
3
0
)
,
(
-
3
0
)
,
(
0
1
4
)
,
(
0
-
1
4
)
,
(
1
4
0
)
,
(
-
1
4
0
)
}
.
9. The interlace-to-progressive scan conversion system of claim 6 , wherein the motion estimator includes a bilinear interpolator.
10. The interlace-to-progressive scan conversion system of claim 9 , wherein a value of a first estimator is set to a value of a second estimator if:
e ( {overscore (MV)} a ,{overscore (X)}−{overscore (SMV)} a ,t )> e ( {overscore (MV)} b ,{overscore (X)}−{overscore (SMV)} b ,t )+ Th
and wherein the value of the second estimator is set to the value of the first estimator if:
e ( {overscore (MV)} b ,{overscore (X)}−{overscore (SMV)} b ,t )> e ( {overscore (MV)} a ,{overscore (X)}−{overscore (SMV)} a ,t )+ Th
where Th is a fixed threshold.
11. The interlace-to-progressive scan conversion system of claim 6 , wherein an error function of the motion estimator includes penalties related to a length of the difference vector between a given candidate vector and a plurality of neighboring vectors.
12. The interlace-to-progressive scan conversion system of claim 11 , wherein the error function is defined by:
e
(
C
_
,
x
,
y
,
t
)
=
∑
x
∈
B
(
x
,
y
,
t
)
F
(
x
,
y
,
t
)
-
F
(
x
-
C
x
,
y
-
C
y
,
t
-
T
)
+
α
·
U
_
(
x
,
y
,
t
)
.
13. The interlace-to-progressive scan conversion system of claim 11 , wherein the motion estimator assumes that a motion vector for an object between a previous field and a current field is the same as a motion vector for the object between the current field and a next field.
14. The interlace-to-progressive scan conversion system of claim 13 , wherein a motion vector error correction function is defined by:
MV
_
(
x
,
y
,
t
)
=
{
(
0
0
)
,
(
e
m
(
x
,
y
,
t
)
≥
e
s
(
x
,
y
,
t
)
)
MV
_
(
x
,
y
,
t
)
,
(
e
m
(
x
,
y
,
t
)
<
e
s
(
x
,
y
,
t
)
)
where:
e
m
(
x
,
y
,
t
)
=
∑
x
∈
X
F
(
X
)
-
F
(
C
)
+
∑
x
∈
X
F
(
X
)
-
F
(
D
)
2
e
s
(
x
,
y
,
t
)
=
∑
x
∈
X
F
(
X
)
-
F
(
A
)
+
∑
x
∈
X
F
(
X
)
-
F
(
B
)
2
and where A, B, C, D, and X are blocks containing ends of candidate motion vectors, X being in the current field, A and C being in the previous field, and B and D being in the next field.
15. The interlace-to-progressive scan conversion system of claim 13 , wherein a motion vector error correction function is defined by:
MV
_
(
x
,
y
,
t
)
=
{
(
0
0
)
,
(
e
m
(
x
,
y
,
t
)
≥
e
s
(
x
,
y
,
t
)
)
MV
_
(
x
,
y
,
t
)
,
(
e
m
(
x
,
y
,
t
)
<
e
s
(
x
,
y
,
t
)
)
where:
e
m
(
x
,
y
,
t
)
=
∑
F
(
C
)
-
F
(
D
)
e
s
(
x
,
y
,
t
)
=
∑
F
(
A
)
-
F
(
B
)
and where A, B, C, D, and X are blocks containing ends of candidate motion vectors, X being in the current field, A and C being in the previous field, and B and D being in the next field.
16. The interlace-to-progressive scan conversion system of claim 6 , wherein a cost function is defined by:
∀F(x,y,t)εB(x,y,t):
D=|F ( x,y,t )− F ( x−MV x, y−MV y ,t− 1)|
TD=TD+D
Diff=D−EstErr
EstErr=EstErr +(δ Diff ));
Dev=Dev +δ(| Diff|−Dev ).
17. The interlace-to-progressive scan conversion system of claim 6 , wherein the block erosion sub-component divides each block according to:
B ( x,y,t )={( x,y )| X x −X /2 ≦x≦X x +X /2 X y −Y /2 ≦y≦X y +Y /2}
wherein a vector {overscore (MV)}(x,y,t) is assigned, into four sub-blocks B i,j (x, y , t)
B
i
,
j
(
x
,
y
,
t
)
=
{
(
x
,
y
)
❘
X
x
-
(
1
-
i
)
·
X
4
≤
x
≤
X
x
+
(
1
+
i
)
·
X
4
⋀
X
y
(
1
-
j
)
·
Y
4
≤
y
≤
X
y
+
(
1
+
j
)
·
Y
4
}
and wherein the variables I and j take the values +1 and −1; wherein a vector MV ij (x,y,t) is assigned to the pixels of each of the sub-blocks B ij (x,y,t):
∀( x,y )ε B i,j ( x,y,t ): {overscore (MV)} i,j ( x,y,t )={overscore (MV)} i,j ( {overscore (X)},t )
wherein:
{overscore (MV)} i,j ( {overscore (X)},t )=med[ {overscore (MV)} ( x+i·X,y,t ), {overscore (MV)} ( {overscore (X)},t ), {overscore (MV)} ( x,y+j·Y,t )]
wherein the median function is a median on the x and y vector components separately; and
wherein a resulting vector is replaced by an original motion vector unless the resulting vector is equal to one of the three input vectors.
18. The interlace-to-progressive scan conversion system of claim 6 , wherein the first stage selection function is given by:
F
n
(
x
,
y
,
t
)
=
{
F
(
x
+
MV
x
(
x
,
y
,
t
)
,
y
+
MV
y
(
x
,
y
,
t
)
,
t
+
1
)
,
(
D
m
<
D
s
)
F
(
x
,
y
,
t
+
1
)
,
(
D
m
≥
D
s
)
where:
D
s
=
∑
k
=
-
2
2
C
v
(
k
)
·
F
(
x
,
y
+
k
,
t
)
-
F
(
x
,
y
+
k
,
t
+
1
)
D
m
=
∑
k
=
-
2
2
C
v
(
k
)
·
F
(
x
,
y
+
k
,
t
)
-
F
(
x
-
MV
x
(
x
,
y
,
t
)
,
y
-
MV
y
(
x
,
y
,
t
)
+
k
,
t
+
1
)
.
(
3.22
)
19. The interlace-to-progressive scan conversion system of claim 6 , wherein the third stage combining function is given by:
F
o
(
x
,
y
,
t
)
=
{
F
(
x
,
y
,
t
)
,
(
y
mod
2
=
t
mod
2
)
(
c
i
·
F
i
(
x
,
y
,
t
)
)
+
(
1
-
c
i
)
(
c
p
·
F
p
(
x
,
y
,
t
)
+
(
1
-
c
p
)
F
n
(
x
,
y
,
t
)
)
,
(
otherwise
)
wherein c i and c p are adaptive coefficients ranging from 0 to 1; F n is given by:
F
n
(
x
,
y
,
t
)
=
{
F
(
x
+
MV
x
(
x
,
y
,
t
)
,
y
+
MV
y
(
x
,
y
,
t
)
,
t
+
1
)
,
(
D
m
<
D
s
)
F
(
x
,
y
,
t
+
1
)
,
(
D
m
≥
D
s
)
wherein intra-field interpolation is given by:
F
i
(
x
,
y
,
t
)
=
F
(
x
,
y
-
1
,
t
)
+
F
(
x
,
y
+
1
,
t
)
2
and wherein backward data prediction is given by:
F p ( x,y,t )= F ( x−MV x ( x,y,t ), y−MV y ( x,y,t ), t− 1).
20. An interlace-to-progressive scan conversion system, comprising:
a spatial line averaging prefilter having a prefiltered signal as an output;
a motion estimator having the prefiltered signal as input and a motion-corrected signal as an output, the motion estimator comprising:
a 3-D recursive search sub-component having a bilinear interpolator;
a motion vector correction sub-component having an error function, the error function including penalties related to a length of the difference vector between a given candidate vector and a plurality of neighboring vectors;
a block erosion sub-component;
wherein the motion estimator assumes that a motion vector for an object between a previous field and a current field is the same as a motion vector for the object between the current field and a next field
a three-stage adaptive recursive filter having the prefiltered output and the motion-corrected output as inputs, the three stages comprising:
a first stage that comprises a function that selects between using static pixels data and moving pixels data from a next field;
a second stage that comprises a function that selects a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
a third stage that comprises a function that combines an intra-field interpolation with the more valid set of data selected by the second stage.
21. An interlace-to-progressive scan conversion system, comprising:
a spatial line averaging prefilter having a prefiltered signal as an output;
a motion estimator having the prefiltered signal as input and a motion-corrected signal as an output, the motion estimator comprising: a 3-D recursive search sub-component; a motion vector correction sub-component; and a block erosion sub-component; wherein:
the 3-D recursive search sub-component includes a bilinear interpolator defined by:
F
(
x
,
y
,
t
)
=
(
yf
·
xf
·
F
(
xi
,
yi
,
t
)
)
+
(
yf
·
(
1
-
xf
)
·
F
(
xi
+
1
,
yi
,
t
)
)
+
(
(
1
-
yf
)
·
xf
·
F
(
xi
,
yi
+
1
,
t
)
)
+
(
(
1
-
yf
)
·
(
1
-
xf
)
·
F
(
xi
+
1
,
yi
+
1
,
t
)
where
:
yf
=
⌊
y
⌋
xf
=
⌊
x
⌋
and
:
yi
=
y
-
⌊
y
⌋
xi
=
x
-
⌊
x
⌋
and wherein a value of a first estimator is set to a value of a second estimator if:
e ( {overscore (MV)} a ,{overscore (X)}−{overscore (SMV)} a ,t )> e ( {overscore (MV)} b ,{overscore (X)}−{overscore (SMV)} b ,t )+ Th
and wherein the value of the second estimator is set to the value of the first estimator if:
e ( {overscore (MV)} b ,{overscore (X)}−{overscore (SMV)} b ,t )> e ( {overscore (MV)} a ,{overscore (X)}−{overscore (SMV)} a ,t )+ Th
where Th is a fixed threshold;
the 3-D recursive search sub-component has a look-up table consisting of:
US
n
=
{
(
0
0
)
,
(
0
1
)
,
(
0
-
1
)
,
(
1
0
)
,
(
-
1
0
)
,
(
0
2
)
,
(
0
-
2
)
,
(
3
0
)
,
(
-
3
0
)
,
(
0
1
4
)
,
(
0
-
1
4
)
,
(
1
4
0
)
,
(
-
1
4
0
)
}
a motion vector correction sub-component having an motion vector error correction function defined by:
MV
_
(
x
,
y
,
t
)
=
{
(
0
0
)
,
(
e
m
(
x
,
y
,
t
)
≥
e
s
(
x
,
y
,
t
)
)
MV
_
(
x
,
y
,
t
)
,
(
e
m
(
x
,
y
,
t
)
<
e
s
(
x
,
y
,
t
)
)
where
:
e
m
(
x
,
y
,
t
)
=
∑
F
(
C
)
-
F
(
D
)
e
s
(
x
,
y
,
t
)
=
∑
F
(
A
)
-
F
(
B
)
and where A, B, C, D, and X are blocks containing ends of candidate motion vectors, X being in the current field, A and C being in the previous field, and B and D being in the next field;
a block erosion sub-component that divides each block according to:
B ( x,y,t )={( x,y )| X x −X /2 ≦x≦X x +X /2 X y −Y /2 ≦y≦X y +Y /2}
wherein a vector {overscore (MV)}(x,y,t) is assigned, into four sub-blocks B i,j (x, y, t)
B
i
,
j
(
x
,
y
,
t
)
=
{
(
x
,
y
)
❘
X
x
-
(
1
-
i
)
·
X
4
≤
x
≤
X
x
+
(
1
+
i
)
·
X
4
⋀
X
y
(
1
-
j
)
·
Y
4
≤
y
≤
X
y
+
(
1
+
j
)
·
Y
4
}
and wherein the variables I and j take the values +1 and −1; wherein a vector MV ij (x,y,t) is assigned to the pixels of each of the sub-blocks B ij (x,y,t):
∀( x,y )ε B i,j ( x,y,t ): {overscore (MV)} i,j ( x,y,t )={overscore (MV)} i,j ( {overscore (X)},t )
wherein:
{overscore (MV)} i,j ( {overscore (X)},t )=med[ {overscore (MV)} ( x+i·X,y,t ), {overscore (MV)}( {overscore (X)},t ), {overscore (MV)} ( x,y+j·Y,t )]
wherein the median function is a median on the x and y vector components separately; and
wherein a resulting vector is replaced by an original motion vector unless the resulting vector is equal to one of the three input vectors;
a three-stage adaptive recursive filter having the prefiltered signal and motion-corrected signals as output, the three stages comprising:
a first stage comprises a function that selects between using static pixels data and moving pixels data from a next field according to the function:
F
n
(
x
,
y
,
t
)
=
{
F
(
x
+
MV
x
(
x
,
y
,
t
)
,
y
+
MV
y
(
x
,
y
,
t
)
,
t
+
1
)
,
(
D
m
<
D
s
)
F
(
x
,
y
,
t
+
1
)
,
(
D
m
≥
D
s
)
where
:
D
s
=
∑
k
=
-
2
2
C
v
(
k
)
·
F
(
x
,
y
+
k
,
t
)
-
F
(
x
,
y
+
k
,
t
+
1
)
D
m
=
∑
k
=
-
2
2
C
v
(
k
)
·
F
(
x
,
y
+
k
,
t
)
-
F
(
x
-
MV
x
(
x
,
y
,
t
)
,
y
-
MV
y
(
x
,
y
,
t
)
+
k
,
t
+
1
)
a second stage comprises a function that selects a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
a third stage comprises a function that combines an intra-field interpolation with the more valid set of data selected by the second stage according to the function:
F
o
(
x
,
y
,
t
)
=
{
F
(
x
,
y
,
t
)
,
(
y
mod
2
=
t
mod
2
)
(
c
i
·
F
i
(
x
,
y
,
t
)
)
+
(
1
-
c
i
)
(
c
p
·
F
p
(
x
,
y
,
t
)
+
(
1
-
c
p
)
F
n
(
x
,
y
,
t
)
)
,
(
otherwise
)
wherein c i and c p are adaptive coefficients ranging from 0 to 1; F n is given by:
F
n
(
x
,
y
,
t
)
=
{
F
(
x
+
MV
x
(
x
,
y
,
t
)
,
y
+
MV
y
(
x
,
y
,
t
)
,
t
+
1
)
,
(
D
m
<
D
s
)
F
(
x
,
y
,
t
+
1
)
,
(
D
m
≥
D
s
)
wherein intra-field interpolation is given by:
F
i
(
x
,
y
,
t
)
=
F
(
x
,
y
-
1
,
t
)
+
F
(
x
,
y
+
1
,
t
)
2
and wherein backward data prediction is given by:
F p ( x,y,t )= F ( x−MV x ( x,y,t ), y−MV y ( x,y,t ), t− 1).
22. A method for converting an interlaced image to a progressive scan image, the method comprising:
providing an input signal corresponding to an image;
prefiltering the input signal with a spatial line averaging prefilter;
estimating motion in the image by:
performing a 3-D recursive search;
performing a motion vector correction;
performing a block erosion to reduce blockiness in the progressive scan image;
filtering the signal in three stages:
in the first stage selecting between using static pixels data and moving pixels data from a next field;
in the second stage selecting a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
in the third stage combining an intra-field interpolation with the more valid set of data selected by the second stage.
23. A method for converting an interlaced image to a progressive scan image, the method comprising:
providing an input signal corresponding to an image;
prefiltering the input signal with a spatial line averaging prefilter;
estimating motion in the image by:
assuming that a motion vector for an object between a previous field and a current field is the same as a motion vector for the object between the current field and a next field;
performing a 3-D recursive search;
performing a motion vector correction in which the error function penalizes a candidate vector based on a length of a difference vector between the candidate vector and a plurality of neighboring vectors;
performing a block erosion to reduce blockiness in the progressive scan image;
filtering the signal in three stages:
in the first stage selecting between using static pixels data and moving pixels data from a next field;
in the second stage selecting a more valid set of data between motion compensated data from a previous field and the pixels selected by the first stage; and
in the third stage combining an intra-field interpolation with the more valid set of data selected by the second stage.