A Novel Video Image Scaling Algorithm Based on
Morphological Edge Interpolation
Zaifeng Shi, Suying Yao, Yingchun Zhao
School of Electronic and Information Engeering, Tianjin University
Tianjin, 300072, China
shizaifeng@tju.edu.cn
ABSTRACT
Traditional image scaling algorithms generally was
based on perfect original images which had not any noise. A
novel video image scaling algorithm based on
morphological edge interpolation was put forward in this
paper. This algorithm filtered noise and smooth images by
morphological opening-closing operation, and it restrained
those faint edges of scaled images obtained by using the
traditional methods because that the original video images
often had been contaminated by noise. Two interpolation
algorithms were used for edge regions and plain regions
respectively. Simulation studies show that the proposed
algorithm is more efficient for image scaling than
conventional image scaling algorithms, and the edges of
result images were less blurring.
Keywords-
image scaling; edge detection;
mathematical morphology;
1.
INTRODUCTION
Image scaling is a very important issue in the video image
post-processing [1-8]. Generally, there are mainly two kinds
of image scaling algorithms. The first is of the non-edge
based image scaling. This kind of image scaling does not
use any information related to image edges and estimates
the pixel values according to each pixel location and its
global invariant relation with its neighborhood pixel values.
The nearest neighbor interpolation [1] ,bi-linear
interpolation [3], bi-cubic interpolation [4], and B-spline
interpolation[5] are all of non-edge based image scaling
algorithms. But these classical image scaling algorithms [6]
have clear disadvantages such as blurring or zigzag edges in
the scaled image. The second type of image scaling
algorithm is that of edge-based scaling algorithms. These
algorithms interpolate the new pixel values according to the
edge information of the original image [2] [7] [8], i.e. these
algorithms depend largely on the edge information. But
these given edge-based scaling methods is only perfect to
the images which are not contaminated by noises, when
there exist noises in the image, the image edge obtained by
the traditional edge detectors may be the faint edge, so the
scaled image according to these edges must exist blurring or
zigzag cases.
In this paper, the proposed scaling algorithm based on
mathematical morphology first detects the image edge.
During the edge detection, considering that the variety of
image edge type and the image may be contaminated by the
noise, we detect the edge direction combined multi-direction
structure elements with a modified anti-noise morphological
edge detector. After that, the boundary pixels interpolate
along edge directions using bi-linear interpolation kernel.
This algorithm can effectively avoid zigzag edges, noises
and can improve image quality validly.
2.
THE PROPOSED SCALING ALGORITHM
Edges include the most important image information,
and can provide the information of the object’s position, so
our algorithm first use the morphological edge detector to
detect the image edge, and then apply different interpolation
to the edge regions and plain region respectively. After
these, the resultant image is our scaled image.
A. Edge Detection Based on Anti-noise multi-direction
Morphological Detector
Mathematical morphology is a tool for analyzing the
digital image. Its basic ideas are to measure the shape of
image and then carry out image processing using structure
element, which has a specific figuration to reach the image
of analyzing and identification. There are 4 basic algorithms
in mathematical morphology: dilation, erosion, opening and
closing algorithm. Based on these basic algorithms or their
combination with the pre-defined structure element, all
kinds of morphological edge detectors can be deduced.
Therefore, the keys of morphological edge detection are the
design of morphological edge detector and the selection of
structure element.
1) Morphological Edge Detector with Noise Restraining
There are several basic edge detectors, as shown in Table
1, they are erosion edge detector, dilation edge detector,
dilation-erosion edge detector respectively, opening edge
detector and closing edge detector. Experiment[9] shows
that the first three edge detectors are better for image edge
by performing the difference between processed image and
original image, but they are worse for noise filtering; The
last two edge detectors are better for filtering, but the result
of processed image is only correlative with the convexity
and concavity of the image edge.
Morphological eroding and opening operating can restrain the
peak (positive impulse) noise, while morphological dilation and
closing operating can restrain the dish (negative impulse) noise.
IEEE Int. Conference Neural Networks & Signal Processing
Zhenjiang, China, June 8~10, 2008
388
Authorized licensed use limited to: National Dong Hwa University. Downloaded on December 11, 2008 at 05:57 from IEEE Xplore. Restrictions apply.
Using the characters above, firstly, we can filter noise by having
opening-closing operation, and then smooth the image by first
closing and then dilation, so the morphological operator of edge
detection with noise restraining. The modified morphological edge
detector is written by:
B
M
B
B
M
F
E
•
−
⊕
•
=
)
(
)
(
(1)
Where
(2)
B
B
F
M
o
)
(
•
=
Table 1 basic edge detectors
Type Operation
Dilation edge detector
F
B
F
−
⊕ )
(
Erosion edge detector
)
(
B
F
F
Θ
−
Dilation-erosion edge detector
)
(
)
(
B
F
B
F
Θ
−
⊕
Opening edge detector
)
(
B
F
F
o
−
Closing edge detector
F
B
F
−
• )
(
Where, F denotes the original image;
B denotes the structure element
2) Selection of Structure Element
The choice of structure element has an important impact to the
morphologic processing of image. Because there may be many
different type of edges and the structure element has the “probing”
effect to the edges type, the final result of detected image edge is
closely associated with the size and shape of structure element[10].
So firstly, it is an important problem about the choice of the
structure element size. The structure element with small window
size has a weaker ability to restrain noise, but can detect smooth
image edge. On the contrary, structure element with larger window
size has a stronger ability to restrain noise, but detects a rough
image edge. Therefore, in order to restrain noise validly and get the
exact image information, we must have a compromise between
them. Generally the window which size is 3-by-3, 5-by-5 or 7-by-7
is the better compromise, while the 3-by-3 window size is the
fastest and the edge detected is the smoothest. Considering the
optimal choice of the size of the structure element is determined by
the cost of encoding boundary zeros versus that of encoding the
positional information of connected components, it is clear that we
choose 3-by-3 structure element size in our algorithm.
Secondly, the choice of the structure element shape is as
important as its size. If a single structure element is chosen, the
processed image only contains the edge information at the same
direction, but those along the other directions will be smoothed. So
in order to gain the edge information along the other direction, we
must adopt multi-structure elements morphological edge detector.
Its basic theory is to construct different structure elements in the
same square window. And these structure elements comprise
almost all the line extending directions in the square window.
Let {
} (
)
,
( y
x
F
Z
y
x
∈
,
) is an original image, and
is its centre, then structure elements in (2N+1)-by-
(2N+1) square window can be denoted by [11]:
)
,
(
0
0
y
x
)
3
(
}
,
|
),
,
(
{
0
0
0
0
N
y
x
N
i
y
y
x
x
F
B
i
i
≤
≤
−
×
=
+
+
=
α
θ
Where
=
and
i
N
N
4
/
180
,
1
4
,
,
1
,
0
0
=
−
α
L
i
θ
is the
direction angle of structure element.
Based on the introduction above, in our algorithm, we choose
the value of
is 1, then the structure element size is 3-by-3, the
direction angles of all structure elements are 0°,90°,45°
and135°. And these structure elements are shown in Figure
1.where the black dot denotes the components of structure element.
N
(a) B1 with 0 °direction (b) B2 with 90 °direction
(c) B2 with 45 °direction (d) B4 with 135° direction
Fig.1. Four different directional structure elements
3) Edge Detection Algorithm of Anti-noise Multi-Structure
Element
Based on the introduction about morphological edge detector
and the structure element above, the steps of anti-noise multi-
structure element morphological edge detection algorithm can be
described as follow:
Step1: Choose the structure elements with the appropriate size
along different directions. There, we choose structure element B1,
B2, B3 and B4 as shown in Figure 1.
Step2: Use structure element B1, B2 and B3 respectively to
detect the edges
(
)
(F
E
i
4
,
3
,
2
,
1
=
i
) of original image by the
formula (1) as follow:
i
i
i
i
i
i
B
M
B
B
M
F
E
•
−
⊕
•
=
)
(
)
(
(4)
Where
i
i
i
B
B
F
M
o
)
(
•
=
(5)
Step3: According to every detected edge E
i
(F)in step2, calculate
the average value to get the final image edge as follow:
4
/
))
(
(
)
(
4
1
∑
=
=
i
i
F
E
F
E
(6)
389
Authorized licensed use limited to: National Dong Hwa University. Downloaded on December 11, 2008 at 05:57 from IEEE Xplore. Restrictions apply.
Where, E(F) is the final image edge gotten by detection of anti-
noise multi-structure element edge detector.
B. Image Interpolation
1) Plain Regions Interpolation
For equally spaced sampled signal, the interpolation process can
be regard as a filtering process. Considering the resource usage and
the quality of image scaling generally, we decide to adopt the bi-
liner interpolation or the bi-cubic interpolation put forward by
Robert G. Keys in [3].
As shown in Fig.2, x0, x1, x2 and x3 are equally spaced
sampled node,
x
is the required node, then the interpolation
formula can be written by:
∑
=
=
3
0
)
(
)
(
)
(
k
k
s
h
x
p
x
p
(7)
Where
and
.
h
x
x
s
/
)
(
1
−
=
)
(
0
1
x
x
h
−
=
Fig. 2 cubic interpolation curve
When
, Keys interpolation kernel is defined as:
1
=
h
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
<
<
<
+
−
+
−
<
<
+
−
=
s
s
s
s
s
s
s
s
s
h
2
0
2
1
2
4
2
5
2
1
1
0
1
2
5
2
3
)
(
2
3
2
3
(8)
Based on the above interpolation algorithm, two-
dimension digital image interpolation can be decomposed
into two one-dimension interpolations. First, the discrete
image signals are interpolated in horizontal direction. Then
we can get four temporary interpolated pixels S0, S1, S2
and
(
), where
stands for
16 neighbors of the original image, the distance between
two neighbors is 1. Second, the horizontal interpolation is
interpolated in vertical direction. In this way, we can get
the interpolated pixel
. Fig. 3 shows the
interpolation algorithm sketching map.
3
S
∑
=
+
Δ
=
3
0
4
)
(
k
i
k
i
x
h
p
S
i
k
p
4
+
∑
=
Δ
×
=
3
0
)
(
i
i
y
S
S
Fig. 3 the interpolation algorithm sketching map
2) Edge Regions Interpolation
According to the detected edge direction, the pixels in the edge
regions can be interpolated along the edge direction. At the same
time considering the computational complexity, we adopt the bi-
linear interpolation in the edge region, so the choice of four
associated pixels depends on the edge direction. For instance, in
Fig. 4, the “s” is the node that will be interpolated into a new pixel,
and p1, p2, p3 and p4 is the neighbors of “s”., and when the
detected edge is along 45
0
direction angle, the four associated
pixels are p3 p4 p6 and p7, then we can have a bi-linear
interpolation to the node “s” in the parallelogram p3p4p6p7. ∆X’
and ∆Y’ is the liner distances.
Fig.4
Edge Region Interpolation
3.
SIMULATION RESULTS AND ANALYSIS
In our experiment, we choose a grid image and a lena
image as the original image. We have our experiment
according to the following steps:
Step1: First adopt the additional image scaling algorithm
such as the bi-linear and bi-cubic interpolation methods to
expand the grid image.
Step2: Second adopt the proposed algorithm to expand
the grid image. Fig.5 is the final scaled image.
(a) Original image (b) Bi-linear
390
Authorized licensed use limited to: National Dong Hwa University. Downloaded on December 11, 2008 at 05:57 from IEEE Xplore. Restrictions apply.
(c) Bi-cubic (d) proposed algorithm
Fig.5 Comparison of image interpolation approaches
(local region of 4x scaled grid image )
The figure 5(b) was the scaled image obtained by bi-
linear interpolation method, which has clearer zigzag
contours; the figure 5(c) was obtained by bi-cubic
interpolation method, which has better image but has
blurred contours; the figure 5(d) was obtained by proposed
algorithm, which has clearer and less zigzag contours
compared with the above two images.
Step3: To show the anti-noise effect of the proposed
algorithm, we first add noise to the lena image, and then
adopt above methods to expand the image respectively.
Fig.6 is the final scaled image.
(a) original image
(b) Bi-linear (c) Bi-cubic
(d) Proposed algorithm
Fig. 6 Comparison of image interpolation approaches
(lena image with noise, 2x scaled)
The figure 6(b) was obtained by using bi-linear
interpolation method, which has many noisy nodes and
blurred contours; the figure 6(c) was obtained using bi-cubic
interpolation method, which has better image but still has
many noisy nodes; the figure 6(d) was obtained by proposed
algorithm, which has clearer contours and less noisy nodes
compared with the above two images.
4.
CONCLUSIONS
In this paper, a novel edge interpolation algorithm based
on mathematic morphology was put forward to expand the
video image. This algorithm detected the image edge region
based on the morphology firstly. And it used the “probing”
effect of the multi-structure elements of morphology to deal
with the variety of edge type. For each structure elements, a
modified anti-noise morphological edge detector was
adopted to detect appropriate image edge. In the end, the
average value of detected results of multi-structure element
was regarded as the final image edge. After detecting the
edge region, two interpolation algorithms are adopted for
edge regions and plain regions respectively. Simulation
results show that the proposed algorithm can restrain the
image noise compared with traditional image interpolation
methods such as bi-linear interpolation and bi-cubic
interpolation algorithm. The final scaled image has less
blurring edge information.
R
EFERENCES
[1] P.Thevenaz,T.Blu &M.”Unser, Interpolation Revisited”. IEEE Trans
Medical Imaging 19(7):739-758,2000
[2] Chun-Ho Kim; Si-Mun Seong; Jin-Aeon Lee; Lee-Sup Kim;”
Winscale: an image-scaling algorithm using an area pixel model”.
IEEE Transactions Circuits and Systems for Video Technology,2003
Page(s):549 - 553
[3] W.K Carey, Chuang & S.S Hemami. “Regularity Preserving Image
Interpolation”. IEEE Trans Image Processing 8(9):1293-1297, 1999
[4] R.G Keys. “Cubic Convolution Interpolation for Digital Image
Processing”.IEEE Transactions on Acoustics, Speech, and Signal
Processing,1981,29(6):1153-1160
[5] Akram Aldroubi &Murray Eden..”Enlargement or Reduction of Digital
Image with Minimum Loss of Information”. IEEE Transactions on
Signal Processing4(3):247-258,1995
[6] J.A.Parker, R.V.Kenyon and D.E.Troxel, “Comparison of Interpolating
Methods for Image Resampling”, IEEE Trans.on Imge
Processing,MI-2, No.1,March 1983
[7] Q.Wand and R.Ward,”A new edge-directed image expansin
scheme”,Proc. IEEE Int. Conf.Image Processing, vol.1,2001,pp.899-
902
[8] Hwasup Lim; Young Ho Lee; Seongjoon Yang; “Image scaling using
vector planes and directional information”. Consumer Electronics,
ICCE. 2005 Page(s):79 - 80
[9] Zhao Yu-qian1, Gui Wei-hua, Chen Zhen-cheng, Tang Jing-tian, Li
Ling-yun1” Medical Images Edge Detection Based on Mathematical
Morphology” Engineering in Medicine and Biology Society, 2005.
IEEE-EMBS 2005. 27th Annual International Conference of the 2005
Page(s):6492 - 6495
[10] Zeng Pingping; Zeng Binyang; “A New Algorithm Based on Multi-
scale Order Morphology for Gray Image Edge Detection”, The Eighth
International Conference on Electronic Measurement and Instruments:
2007 Page(s):2982 - 2985
[11] Yuqian Zhao, Weihua Gui and Zhencheng Chen,” Edge Detection
Based on Multi-Structure Elements Morphology” Proceedings of the
6th World Congress on Intelligent Control and Automation, June 21 -
23, 2006,
391
Authorized licensed use limited to: National Dong Hwa University. Downloaded on December 11, 2008 at 05:57 from IEEE Xplore. Restrictions apply.