iDocSlide.Com

Free Online Documents. Like!

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Gray-Level Reduction Using Local Spatial Features

Tags

Transcript

Computer Vision and Image Understanding
78,
336–350 (2000)doi:10.1006/cviu.2000.0838, available online at http://www.idealibrary.com on
Gray-Level Reduction Using Local Spatial Features
Nikos Papamarkos
1
and Antonios Atsalakis
Electric Circuits Analysis Laboratory, Department of Electrical and Computer Engineering, DemocritusUniversity of Thrace, 67100 Xanthi, Greece
Received January 26, 2000; accepted February 9, 2000
This paper proposes a new method for reduction of the number of gray-levelsin an image. The proposed approach achieves gray-level reduction using both theimage gray-levels and additional local spatial features. Both gray-level and localfeature values feed a self-organized neural network classiﬁer. After training, theneurons of the output competition layer of the SOFM deﬁne the gray-level classes.The ﬁnal image has not only the dominant image gray-levels, but also has a textureapproaching the image local characteristics used. To split the initial classes further,the proposed technique can be used in an adaptive mode. To speed up the entiremultithresholding algorithm and reduce memory requirements, a fractal scanningsubsamplingtechniqueisadopted.Themethodisapplicabletoanytypeofgray-levelimage and can be easily modiﬁed to accommodate any type of spatial characteristic.Several experimental and comparative results, exhibiting the performance of theproposed technique, are presented.
c
2000 Academic Press
Key Words:
segmentation; multithresholding; neural networks; PCA; SOFM.
1. INTRODUCTION
Reductionofthenumberofgray-levelsinanimageisanimportanttaskforsegmentation,compression, presentation, and transmission of images. In most cases, it is easier to processand understand an image with a limited number of gray-levels. The usual technique forreduction of the number of gray-levels in a digital image is multithresholding. Using onlythe values of the image histogram, multithresholding determines appropriate thresholdvalues that deﬁne the limits of the image gray-level classes. However, the application of multithresholding is based on the assumption that object and background pixels in a digitalimage can be well distinguished by their gray-level values [1]. Therefore, in compleximages,suchasnatural,texture,orpoorlyilluminatedimages,multithresholdingtechniquesdo not give satisfactory results. Also, in multiobject images, there are several difﬁculties
1
To whom correspondence should be addressed. Fax: +30-541-26947. E-mail: papamark@voreas.ee.duth.gr.336
1077-3142/00 $35.00Copyright c
2000 by Academic PressAll rights of reproduction in any form reserved.
GRAY-LEVEL REDUCTION
337for multilevel threshold selection that are associated with gray-level distributions, smallobjects, and object overlapping.Multithresholding techniques can be classiﬁed into three categories. In the ﬁrst cate-gory belong the histogram-based multithresholding techniques [2–6]. These techniquesuse different criteria such as minimum entropy, interclass variance between dark and brightregions, changes of zero-crossing, and curve ﬁtting. The method of Reddi
et al
. [2] is fastand is a version extended to multithresholding, of the global threshold method of Otsu [3],whichisoneofthemostpowerfulmethodsforglobalthresholding[7].Thecriterionusedisthe selection of thresholds so that the interclass variance between dark and bright regions ismaximized. The method of Kapur
et al
. [4] is based on the maximum entropy criterion. Themethod of Carlotto [5] determines thresholds by handling the information derived from thechanges of zero-crossings in the second derivative. The method gives good results only forthe histograms that satisfy the basic hypothesis that the histogram consists only of univari-ate normal distributions. The method of Papamarkos
et al
. [6] is based on a combinationof a hill-clustering algorithm and an appropriate linear programming approximation tech-nique. In the second category belong methods based on edge matching and classiﬁcation[8, 9]. These methods are applicable to images with good edges. As a ﬁrst step, in all thesemethods, the pixels of the initial image are ﬁrst classiﬁed as edge and nonedge pixels byusing an edge extraction algorithm. Consequently, for the extraction of the best thresholds,computationallyexpensiverecursionproceduresareused.Duringeachiteration,thethresh-old values are modiﬁed to satisfy some edge characteristics. Finally, in the third categorybelong all the other techniques, which can be characterized as hybrid. Spann and Wilson[10] propose a hybrid method which is a combination of a quad-tree smoothing technique,a local centroid clustering algorithm, and a boundary estimation approach. This method isapplicable under the condition that the histogram consists only of Gaussian distributions.Other approaches togray-level reduction (GLR) arebased onnearest-gray-level mergingor on gray-level error diffusion. In the nearest-gray-level methods, each pixel in the imagechanges its value to the gray-level in a palette that is the closest match to some typicalneighboring pixel. The error diffusion techniques are based on dithering approaches. The“error” refers to the cumulative difference between the actual values of pixels in the im-age and their “true” values, if all were set to their correct gray-levels. These techniquesare suitable for elimination of uncommon gray-levels in an image but are ineffective forimage analysis and segmentation. It should be noticed that none of the multithresholdingtechniques takes into account the local texture characteristics of an image.This paper proposes a new gray-scale reduction algorithm, which exploits not only thegray-levels of the pixels but also the local spatial characteristics of the image. The pro-posed approach signiﬁcantly improves a previously reported technique [11, 12], whichuses only the gray-level values of the images to perform GLR. According to the proposedtechnique, the gray-level value of each pixel is related to local spatial features extractedin its neighboring region. Thus, the one-dimensional histogram-clustering approach of themultithresholding techniques is now converted to a multidimensional feature-clusteringtechnique. The gray-level value of each pixel is considered the ﬁrst feature. The entire fea-ture set is completed by additional spatial features, which are extracted from neighboringpixels. These features are associated with spatial image characteristics, such as min, max,and entropy values. The feature set feeds a self-organized neural network classiﬁer, whichconsistsofaPCAandaKohonenSOFM[13,14].ThePCAisusedtomanipulatethefeaturecoordinate axes that the data falls on. The new axes are uncorrelated and they represent the
338
PAPAMARKOS AND ATSALAKIS
maximum variability that occurs in the process data. The SOFM is competitively trained,accordingtoKohonen’slearningalgorithm.Aftertraining,theoutputneuronsoftheSOFMdeﬁne the appropriate feature classes. Next, each pixel is classiﬁed into one of these classesand resumes the gray-level of the class. In this way, the srcinal image is converted intoa new one, which has a limited number of gray-levels and whose spatial characteristicsapproximate those deﬁned by the features used. To reduce the storage requirement andcomputation time, the training set can be a representative sample of the image pixels. In ourapproach,thesubsamplingisperformedviaafractalscanningtechnique,basedonHilbert’sspace-ﬁlling curve [15].The use of additional spatial features permits the application of the GLR technique in anadaptive mode. According to this scheme, the GLR technique is initially applied withoutusing spatial features and the gray-levels are classiﬁed into
m
classes. Next, the pixels of the initial image that belong to each one of the
m
classes are further classiﬁed by the GLRalgorithm using additional spatial feature sets. It is obvious that by increasing the featurespace the gray-level classes can be further split. This procedure is repeated level by level.Figure 5 depicts the proposed technique in a binary tree form.The proposed method was tested with a variety of images and the results are comparedwith other multithresholding techniques. In addition, this paper presents characteristic ex-amples for various image local characteristics. The experimental and comparative resultsconﬁrm the effectiveness of the proposed method.
2. DESCRIPTION OF THE METHOD
A digital gray-scaleimage
I
(
i
,
j
)
,
i
=
1
,...,
n
,
j
=
1
,...,
m
,canbeconsidered asetof
n
×
m
pixels, where each pixel is a point in the gray-scale space. Usually, the total numberof gray-levels is restricted to 256; i.e.,
I
(
i
,
j
)
∈
[0
...
255].Let
N
(
i
,
j
) denote the local region neighboring pixel (
i
,
j
). In this approach
N
(
i
,
j
) isconsidered to be a 3
×
3 or a 5
×
5 mask that has as its center the pixel (
i
,
j
). It is assumedthat every pixel (
i
,
j
) belongs to its neighborhood
N
(
i
,
j
). It is obvious that in most cases,the gray-level of each pixel is associated with the gray-levels of the neighboring pixels andthelocaltextureoftheimage.Therefore,thegray-levelofeachpixel(
i
,
j
)canbeassociatedwithlocalimagecharacteristicsextractedfromtheregion
N
(
i
,
j
).Thesecharacteristicscanbe considered local spatial features of the image and can be helpful for the GLR process.That is, using the gray-level values of
N
(
i
,
j
)
,
f
k
,
k
=
2
,
3
,...,
K
+
1, local features canbe deﬁned, which are next considered as image spatial features. As can be observed inFig. 1, each pixel (
i
,
j
) is related to its
I
(
i
,
j
) gray-level value, which is considered theﬁrst spatial feature, and to
K
additional features. This approach transforms the 1-D gray-scale feature space of a standard multithresholding technique to a more advantageous oneof
K
+
1 dimensions. No restrictions on the type of local features are implied. However,the features must represent simple spatial characteristics, such as min, max, entropy, andmedian values of the neighboring masks.According to the above analysis, the gray-scale reduction problem can be consideredthe problem of best transforming the srcinal gray-level image to a new one with only
J
gray-levels as the ﬁnal image, to approximate not only the principal gray-level values butalso the local characteristics used. An effective approach to this problem is to consider it aclustering problem and achieve its solution using a suitable self-organized neural network.
GRAY-LEVEL REDUCTION
339
FIG. 1.
The feature extraction procedure.
In the proposed approach, the topology of the entire neural network has the structure shownin Fig. 2. As can be observed, it consists of a PCA and a SOFM neural network. PCA isusefulbecauseofthemultidimensionalityofthefeaturespace.ThroughthePCAtransform,maximumvarianceintheinputfeaturespaceisachievedandhencethediscriminationabilityof the SOFM is increased. It is well known that the main goal of a SOFM neural network isthe representation of a large set of input vectors with a smaller set of “prototype” vectors,so that a “good” approximation of the srcinal input space can succeed. In other words, aSOFM neural network decreases the input feature space optimally into a smaller one. The
FIG. 2.
The entire neural network.
340
PAPAMARKOS AND ATSALAKIS
resultant feature space can be viewed as a representative of the srcinal feature space andtherefore it approximates the main statistical characteristics of the input space.The PCA has
K
+
1 input and
K
+
1 output neurons. It is used to increase the discrimi-nation of the feature space. The SOFM has
K
+
1 input and
J
output neurons. The entireneural network is fed by the extracted features and after training, the neurons in the outputcompetition layer of the SOFM deﬁne the
J
classes. Using the neural network, each imagepixel is classiﬁed into one of the
J
classes and converts its gray-level to the gray-leveldeﬁned by the class. To speed up the algorithm and minimize its memory requirements, afractal scanning subsampling procedure can be used.
2.1. The PCA Neural Network
As mentioned above, the ﬁrst stage of the neural network is a PCA. After training, thefeature vector is optimally projected to a new set such that the maximum discrimination inthe feature space is obtained. For each pixel, the gray-level and its local features contributeproportionally to the training set. The transformation is designed in such a way that theoriginalfeaturesetisrepresentedbyanumberofeffective“features”andyetretainsmostof theintrinsicinformationcontainedinthedata.Inmultivariatedataanalysis,theKarhumen–Loevetransformation(KLT)[14]iswidelyusedforPCA.Itisaprocedurefortheestimationof the eigenvalues and eigenvectors requiring the computation of a data covariance matrix.Here, a single-layer feedforward neural network is used to perform a PCA. Using thistechnique, there is no need to compute the covariance matrix, since the eigenvectors arederived directly from the data. In our approach, the input vector is the (
K
+
1)-dimensional
I
, and the output is also a (
K
+
1)-dimensional feature vector
y
, which is computed by therelation
y
=
QI
.
(1)The input of the PCA (input features) is the gray-level value of each pixel of the imageand the values of the local features. The output consists of
K
+
1 neurons. Matrix
Q
provides the PCA neural network coefﬁcients. The net is trained by the GHA. This is anunsupervised learning algorithm based on a Hebbian learning rule. The Hebbian rule statesthatiftwoneuronsoneithersideofasynapseareactivatedsimultaneously,thenthestrengthof that synapse is selectively increased; otherwise it is weakened or eliminated. The GHAis implemented in the training stage via the relation
q
ik
=
γ
y
i
I
k
(
A
)
−
y
ii
n
=
0
q
nk
y
n
(
B
)
,
with
i
,
k
=
1
,
2
,
3
,....
(2)Term(A)expressestheHebbianruleandterm(B)imposesalimitonthegrowthofsynapticweights. It should be noticed that after training
Q
approximates with probability one thematrixwhoserowsarethethreeeigenvectorsofthecovariancematrix,formedbydecreasingeigenvalues. Also, for example, the weight coefﬁcients
q
00
,
q
01
, and
q
02
of the ﬁrst neurondetermineaneigenvectorwhichexhibitsthemaximumdiscriminationpowerinitsdirection.Theoutputvalues
y
0
,
y
1
,and
y
2
ofthePCAaretheprojectionsoftheinputvectorontotheseeigenvectors. Thus, the training of SOFM is based on the projections of feature vectors.

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks