Signal Processing 75 (1999) 1}10

Repulsive attractive network for baseline extraction on
document images
E. OG ztop, A.Y. MuK layim, V. Atalay, F. Yarman-Vural*
Department of Computer Engineering, Middle East Technical University, TR-06531 Ankara, Turkey
Received 26 July 1996; received in revised form 9 November 1998

Abstract
This paper describes a new framework, called repulsive attractive (RA) network for baseline extraction on document
images. The RA network is an energy minimizing dynamical system, which interacts with the document text image
through the attractive and repulsive forces de"ned over the network components and the document image. Experimental
results indicate that the network can successfully extract the baselines under heavy noise and overlaps between theascending and descending portions of the characters of adjacent lines. The proposed framework is applicable to a wide
range of image processing applications, such as curve "tting, segmentation and thinning.  1999 Elsevier Science B.V.
All rights reserved.
Zusammenfassung
Diese Arbeit beschreibt ein neues Rahmenprogramm, genannt &Repulsive Attractive (RA) network for baseline extraction'
bei Dokument Abbildungen. Das RA Netzwerk ist ein energieminimierendes dynamisches System. Dieses wird mit derAbbildung des Dokumenttextes durch die anziehenden und absto{ende KraK fte, de"niert uK ber Netzwerk-Komponenten,
und dem Dokumentbild in Beziehung gesetzt. Experimentelle Resultate zeigen, da{ das Netzwerk die Grundlinie
zwischen aufsteigenden und absteigenden Buchstabenbereichen unter schwierigen Rauschbedingungen und bei UG berlappung erfolgreich extrahieren kann. Das vorgestellte Programm ist anwendbar auf weite Bereiche der Bildverarbeitung,wie Kurvenanpassung, Segmentierung und AusduK nnung.  1999 Elsevier Science B.V. All rights reserved.
Re2 sume2
Cet article deH crit un nouveau cadre de travail, appeleH re& seau re& pulsif attractif pour l'extraction de la ligne de base sur desimages de documents. Let reH seau reH pulsif attractif est un système dynamique minimisant une eH nergie, qui interagit avec
l'image du texte du document par des forces attractives et reH pulsives deH "nies sur les composantes du reH seau et sur l'image
du document. Des reH sultats expeH rimentaux indiquent que le reH seau peut extraire avec succès les lignes de base sous unbruit important et en preH sence de recouvrements entre les parties ascendantes et descendantes des caractères de deux
lignes adjacentes. Le scheH ma proposeH est applicable à une large gamme d'applications de traitement d'images, telles
l'ajustement de courbes, la segmentation et l'a$nement.  1999 Elsevier Science B.V. All rights reserved.
Keywords: Baseline; Repulsive attractive network; Hough transform; Energy minimization; Active model* Corresponding author. E-mail: vural@ceng. metu.edu.tr
0165-1684/99/$ } see front matter  1999 Elsevier Science B.V. All rights reserved.
PII: S 0 1 6 5 - 1 6 8 4 ( 9 8 ) 0 0 2 2 0 - 5

2

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

1. Introduction

2. Baseline extraction

It is well known that a crucial step in document image analysis is the identi"cation of thebaselines. On a document image, baselines not
only give important information about the layout
structure, but also provide e!ective clues to subsequent steps of document analysis, such as optical character recognition. Baseline extraction
problem becomes complicated in handwritten
documents where the ascending and descending
portions of the characters between adjacent lines
overlap. Additional complexity is introduced when
the characters overlay on a curved or slanted baseline and the documents are contaminated withnoise.
In this study, a new method is presented forextracting the baselines. The method is an application of a framework called repulsive attractive (RA) network [11]. RA Network can
be described as an energy minimizing dynamicalsystem [9] and it is inspired from the universal
law of gravitation where the masses attract eachother according to their weight and distanceamong them. In this particular application inwhich the aim is to extract the baselines ofa document image, the pixels of the image andthe baselines are considered as if they were masses;
each pixel attracts the baselines proportional toits gray value and inversely proportional to thesquare of the distance between them. The baselines,
themselves, repel each other with a magnitude inversely proportional to the square of the distance
between them. The new method is applicable toa wide range of documents and overcomes many
problems faced during the baseline extraction
process, such as thresholding, noise sensitivity, intolerance to font-style variations and skew angles.
Some other possible applications of the RA network in image processing can be thinning andsegmentation.
In the next section, the available techniques forbaseline extraction problem are reviewed. In Section 3, the baseline extraction using RA Network is
described. The network is tested on various text
images in Section 4. Finally, Section 5 concludes
the paper, indicating the direction of the future
work.

In general, a baseline is de"ned to be a curveor line on which the characters overlay on a document image. Standard baseline extraction methods
include Hough transform [5], least-squares
methods [1], horizontal projection pro"les [7],run-length smearing and use of typographical information [8].
Among all, the Hough transform and its variants
are the most widely used methods [10]. In thesemethods, the document image is "rst transformed
to the (o,h) plane. o indicates the length and h indicates the slope of the normal line to a pixel in polar
coordinates. Then, a two-dimensional search is accomplished for detecting the peaks in the transformplane. For a document image having curved baseline and skew angle Hough transform works successfully. However, it has certain drawbacks that
may limit its use. One problem is the quantizationof the input image by extracting the geometricfeatures, such as center of mass of each character.
This process introduces an uncertain amount oferror into the result yielding unsatisfactory solutions for the characters with ascending and descending portions. Secondly, the complexity of thesearch for peaks in the (o,h) plane is a serious
drawback. In addition, it can be di$cult to put
a criterion for identifying the peaks [3,4].
There is a vast amount of variation of the leastsquares methods for "tting lines or curves toa given set of data points [6]. The major limitationof these methods is the sensitivity to the noisecontamination.
The most popular baseline extraction method forprinted text is the use of horizontal projection pro"le which simply obtains the histogram of the image on the y-axis and identi"es the baseline as thepeak points of the histogram [12]. Obviously, it ishighly sensitive to skew angles which requiresa strong preprocessing stage for normalization.
A common baseline extraction method for binary images is to use run length smearing. It isbased on the run length codes which consists ofa start address of each string of 1's, followed by thelength of that string. This method is, also, highly
susceptible to the noise contamination and skew
angle [2].

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

3Finally, use of typographical information forbaseline extraction heavily depends on the skew
angle, font style and size. It is particularly developed for machine printed texts [8].

3. The repulsive attractive (RA) network for baseline
extraction
In this section, the repulsive attractive (RA) network for baseline extraction is described.
A repulsive attractive network is identi"ed by the
triple (Y,g,U) where Y is a vector space, g is a realvalued function de"ned on Y and U is the set ofunits. A unit ; 3U is composed of sub-units, u .
GGHEach sub-unit is associated with a position ora weight vector in Y.
The dynamics of the repulsive attractive network
is determined by the following forces:
E The internal force, f , that exists among the
sub-units belonging to the same unit. This force
gives units the tendency to have certain shape ororientation.
E The repulsive force, f , that exists among the
sub-units of di!erent units.
E The attractive force, f , that is exerted by the
points of Y with a magnitude proportional to thevalue of g at these points.
The repulsive attractive network can be associatedwith the document text image. The baselines, being
curves, are approximated as connected line segments. The triple (Y,g,U) of the RA network
for baseline extraction is speci"ed as follows (seeFig. 1):E Y denotes the document image embedded intoR. More precisely, Y"+(x,y)3R "  twopoints (x ,y ), (x ,y ) on the image such that  x )x)x and y )y)y ,
E U"+; ,; ,2,; , denotes the set of curves
 Lthat approximates the baseline where n is thenumber of baselines, and the sub-units u are theGHconnection points on the curves.
E g : YPZ, where g(p) is the intensity value of theimage at pixel p if p3Z, 0 otherwise.
The internal force of the RA network enforces the
sub-units of the same baseline to lie on a horizontal
line. The forces acting on the document image isde"ned at three levels:

Fig. 1. The forces acting on the sub-unit u (only a sample from
each type of force is shown).

At level 1, the internal, repulsive and attractive
forces among the sub-units and pixels are de"ned
as follows: For each sub-unit u 3; , the receivedGHG
internal force between the sub-units of the same
unit isf (u ,u )GJ GH"u(u ,u )/d(u ,u ), ∀u 3; , jOl,
(1)
GJ GH
GJ GH
GJ
G
the repulsive force between the sub-units of distinct
baselines isf (u ,u )"u(u ,u )/d(u ,u ), ∀u 3; , iOl,
JI GH
JI GH
JI GH
JI
J
(2)
and the attractive force between the image pixels
and sub-unit u isGH
f (p,u )"u(p,u )g(p)/(d(p,u )#g), ∀p3Y. (3)GHGH
GH
In the above equations d is the Euclidean distance function, u(P ,P ) is the unit vector directed from P towards P and g is a real constant.
At level 2, the internal, repulsive and attractive
forces are aggregated to generate net forces
F,#2\ "f (v,u ),
GH
GH
TZIGH

(4)

F,#2\"f (v,u ),
GH
GH
TZRGH

(5)

F,#2\ " f (p,u ),
GH
GH
NZY

(6)

4

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

where
I "+u " kOj, and R "+u " iOl,.
GH
GI
GH
JI
At level 3, the net forces are further aggregated togenerate the total net force
F,#2"aF,#2\ #bF,#2\#cF,#2\ ,
(7)
GH
GH
GH
GH
where a, b, c are real coe$cients.
The RA network framework de"nes the internal,
repulsive and attractive forces among the sub-units
and the pixels in order to extract the baselines ona document. A unit evolves dynamically via the
movements of its sub-units. The displacement of
the sub-units is determined by the forces acting on
it and the total net force is used to update theposition vector associated with each sub-unit. In
this particular application, only the vertical components are taken into account. The vertical component is simply multiplied by a constant scale value to"nd out the amount of change to be performed on
the vertical position of each sub-unit. The energyfunction is de"ned as the integral of the forces. At
a local minimum of the energy function, the subunits do not change their positions. Each baseline isassumed to be a local minimum of the energyfunction. If a unit is su$ciently close to a baseline,
then it will be attracted by the local minimum andthis situation is called as the local convergence. The
global convergence yields the extraction of all thebaselines on a document. In order to guarantee theglobal convergence, a virtual unit is allocated on
top of the document. Also, bottom of the document
is considered to behave as a virtual textline. As soon
as a unit is stuck to the bottom of the image, theglobal convergence is achieved. This indicates that
all of the existing baselines have been extracted.

4. Algorithm for baseline extraction
In order to simulate the system described in thepreceeding section, the following algorithm is used:
1. Choose network parameters: a, b, c.
Initialize o, e and M.
Initialize U"+u ,, u located at the top edge ofthe image.
2. Let d"0

3. For k"1,2,2,M do
1. 3.1. For each sub-unit u of the newly added unitGH
3.1.1. Compute F,#2
GH
3.1.2. Let F be the vertical component of
W
F,#2
GH
3.1.3. Let *y"oF
W
3.1.4. Update the vertical position of subunit u by adding *yGH
3.1.5. Let d"d#*y/M
4. If d'e goto step 2, else continue
5. If the coordinates of the last added unit collapse
with the bottom of the document image then stop.
Else add a new unit to U, located just below
the last added unit.
6. Goto step 2.
At the initial step, parameter values for internal,
repulsive and attractive forces are chosen and theparameters that control the convergence are initialized.
The behavior of the forces in the network aredetermined by the values of the parameters a, b, c.
The internal force, enforces the sub-units of thesame unit to lie on a horizontal line. Therefore,
when the coe$cient of the internal force a, is large
relative to b and c, the RA network looses its ability
to detect curved baselines. On the other hand, if a istaken to be relatively small, then the local properties of the document image dominates the e!ect ofneighboring sub-units, causing zigzags on the baseline. If the coe$cient of repulsive force b, is relatively large, then the in#uence of text pixels on thebaseline decreases. Repulsive force guarantees thatthe distance between the sub-units of di!erent units
on the same column does not come close to 0. On
the other hand, as b gets smaller, multiple units
tend to capture the same baseline. In fact, thisparameter is proportional to the font size. The
amount of attraction that the text pixels exert on
the sub-units is controlled by the parameter for theattractive force, c. If c is taken to be smaller compared to a and b, then the input to the network is
received as an empty page image. If c is large, thenthe attractive force overrides the repulsive force.
This may cause accumulation of more than one
unit on the same line.
o is a constant for controlling the step size of theposition updates. When o gets small, the simulation

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

yields "ner results in terms of the shape of thebaseline. However, it causes slow converge. e isa constant to control the local convergence. It
should be close to 0. The very "rst unit is introduced just below the top of the document image. At thesecond step, coordinates of the sub-units of the
newly introduced unit are updated M times. This isrepeated until the local convergence is reached. The
local convergence criterion checks whether there isany change in the positions of the sub-units. This isevaluated by computing the average square displacements after a set of M updates. The algorithm
terminates when the coordinates of the lastly introduced unit collapse with the bottom of the document as a result of a local convergence. Otherwise,a new unit is added just below the last one.

5. Results
The performance of the RA network as a baseline
extractor is tested on various document images bya simulation program using the C language, under
X Windows environment.
The gray-level images are selected among the
documents from the ancient Ottoman archives(written in Arabic) and from the Latin handwritten
and printed documents. The heavy noise on the
documents are due to the aging, ink smearage andlow quality of the paper. Furthermore, the handwritten documents have high curvature on thebaselines with considerable overlaps on the ascending and descending portions of the characters.
One of the major superiority of the RA networkis that it does not require any preprocessing stage
for noise reduction and binarization. The sample
documents are directly fed to the RA network, forbaseline extraction. In most of the documents, thenoise pixels have relatively light gray values compared to text pixels and the number of the text
pixels exceed the number of the noise pixels. In thiscase, the attractive force of the text pixels dominates the attractive force of the noise pixels. As
a result the RA network becomes insensitive tonoise.
In the RA network for baseline extraction, thesub-units are evenly placed on a unit. The choice ofthe number of sub-units is not a critical parameter.

5

A complex baseline, which does not have a constant curvature, needs relatively more sub-units
than a simple baseline with constant curvature. For
example, a linear baseline can be extracted simply
by two sub-units. The number of sub-units may
initially be chosen large. Then, by checking curvatures locally on the constructed unit, a kind ofpruning algorithm on the sub-units can be applied
until any change is detected on the curvatures. The
network is composed of units and sub-units. Thereexists interactions among all of the sub-units, andalso among all of the sub-units and the pixels of theimage. Therefore, whenever a new unit is introduced, its sub-units a!ect the sub-units of already existing units and vice versa. However, since the existing
units are stuck to the local minima, they do notexhibit important changes. Thus, the update is performed only for the sub-units of a newly introduced
unit. The "rst unit appears just below the top of the
document. It will be repelled by the top and attracted by the "rst textline. As soon as the local convergence is obtained for the "rst unit, second unit isinitialized just below the "rst one. At this moment,
repulsive force from the "rst unit pushes the second
one, so that the second unit is captured by theattractive force of the second textline. More speci"cally, the displacement is determined by the net
force which is composed of internal, attractive andrepulsive forces. Internal forces and attractive forces are almost the same for the units discussed
above. However, since these two units repel eachother, the "rst unit goes up and the second unit
goes down. The "rst unit cannot go further, because
it is also repelled by the top of the document.
In the implementation of the algorithm, M istaken as 10 and e is taken as 0.25 which is decided
experimentally. During the simulations, the valueof g was "xed to 10, which is relatively large compared to other parameters in Eq. (3). If g is chosen
relatively small, then vertical displacements may
become large (particularly when the distance between a sub-unit and a pixel is close to 0) whichyields jumps rather than smooth displacements.
Thus, the unit does not get stuck to a local minimum. The position at which a new unit is added&just below' the previous one depends on the baseline spacing and the resolution of the document
image. However, in the implementation, it is "xed

6

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

to a value of 20 pixels which works "ne for a moderate range of documents. The parameters a, b, cand the number of sub-units will be discussed below in detail.
The evolution of the RA network for a handwritten Ottoman text is presented in Fig. 2. Taking

the parameters a"600, b"550, c"50 alongwith 15 sub-units on each unit enables the network
to capture the high curvature in the baselines. Fig.
2(a) shows the state of the network, when the local
convergence is achieved for the "rst unit. The second unit is introduced just below the "rst one as

Fig. 2. The evolution of the RA network for a handwritten Ottoman text.

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10indicated in Fig. 2(b). Fig. 2(c) and (d) present someintermediate results for the second unit. The baseline extracted by the second unit is shown in Fig.
2(e). Finally, Fig. 2(f ) presents the state when the
global convergence is achieved.
In order to show the experimental convergenceof the system, evolution of the position updates for
an Ottoman text (cf. Fig. 2) is given as a plot in Fig.
3. The y-axis is the average square change in thedisplacement of the sub-units of a unit while thex-axis represents the set of iterations (M;numberof subunits"10;15"150). After the "rst set of
iterations, the average square change drops drastically, which indicates in fact, the local convergence.
In the algorithm, this fact is tested by the comparison to e which is "xed to 0.25. Local convergence isachieved in about 10 ms on a PowerPC processorbased computer.
One may expect that the values of the parameters, particularly those of a, b and c, depend on
the complexity of the document which may be
a!ected by the alphabet in which the document iswritten. The complexity may include: noise level,
curvature, change of curvature, regularity of writing, overlaps on the ascending and descending portions of the characters, etc. However, during the7experimentation it is noted that the RA network is
not sensitive to the changes in the parameters.
A wide range of values of the network parameters is
capable of baseline extraction. For example, thetriple (a"5000, b"550, c"50) with 15 sub-units
successfully extracs baselines of all of the presented
documents.
Fig. 4 shows a handwritten Ottoman text. Notethat the baselines are quite close to each other.
There is a substantial amount of overlap between
the adjacent baselines because of ascending anddescending portions of the characters which is quite
common in handwritten documents. This situation
is highly di$cult to handle with standard baseline
extraction methods.
Fig. 5 shows a handwritten Latin text with heavy
noise and fair amount of overlap between the characters of adjacent lines. The simulated RA network,
however is quite insensitive to such disturbancesand captures the curvatures of the baselines. Fig.
6 shows a printed Latin text. The RA network
easily "nds the baselines with the above indicatedparameter values.
Finally, the result of one of the most popularbaseline extraction method, namely the horizontal
projection pro"les is demonstrated for comparison

Fig. 3. Average square change in the displacement (change in vertical position) of the sub-units of a unit.

8

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

Fig. 4. Extracted baselines by RA network for a handwritten Ottoman text.

Fig. 5. Baseline extraction by RA network for a handwritten Latin text.

Fig. 6. RA network extracts baselines easily for a printed Latin text.

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

Fig. 7. Baseline extraction by using horizontal projectionpro"les.

purpose. In Fig. 7, the Ottoman handwritten document is presented with the extracted baselines bya simple projection method where the image isdivided into vertical strips and a local maximum issought inside the strips. This method requires binarization of the document image. Additionally,
the method depends on many parameters such as
the search for a local maximum value of the projections. It is clear that the curvature of the extracted
baselines do not exhibit a stable behavior on the
document image.
RA network or any of the methods mentioned in
Section 2 can be applied in a straightforward manner to the baseline extraction problem of machine
printed text documents. However, the major problem is the baseline extraction in complex environments, for example, when handwritten text has
irregularities or high skew or even when thereis overlapping of ascending and descending portions of characters of adjacent lines. In this case,algorithms do not provide meaningful results.
Additionally, a quantitative assessment of the performance of the employed method is very di$cult,simply because the identi"cation of the real baseline becomes subjective, depending on the problem
domain.

6. Conclusion
In this study, the RA network for baseline extraction on document images is described. It is based

9on an energy minimization principle. This network
may be incorporated into a complete document
processing system as a part of a page layout extractor or it may be used to provide information toa character recognizer.
There are many advantages of RA network baseline extraction method: RA network completely
eliminates the binarization problem. Moreover,
employing gray-level images improves the performance in contrast to the other methods. One of themost serious problems in many image processing
tasks is noise sensitivity. The existing methods forbaseline extraction also su!ers from this problem.
However, since the attraction of the text pixels
dominate the attraction of the noise pixels on thebaseline, the proposed method is insensitive tonoise. Not only a given set of parameters works "nefor a wide range of documents, but also small
variations in these parameters does not a!ect performance of the method. In the proposed method,
the baselines are not restricted to straight lines
which is the situation for most handwritten documents. Additional di$culty in identi"cation of
baselines is introduced in hand written documents
by the overlapping portions of ascending and descending characters between the baselines. The RA
network baseline extraction method handles the
problem of overlapping elegantly.
Finally, the principles used in the RA network
baseline extraction method can be used to develop
new techniques for various image processing tasks,
such as segmentation and thinning.

References[1] H.K. Aghajan, T. Kailath, SLIDE: subspace-based line
detection, T-PAMI 16 (11) (1994) 1057}1073.
[2] A. Amin, O!-line arabic character recognition: the state of
the art, Pattern Recognition 31 (5) (1998) 517}530.
[3] V. Atalay, M. OG zc7 ilingir, N. Yalabmk, Computer recognition of Ottoman text, in: Proc. ISCIS V, Capadoccia,
Turkey, 1990.
[4] R.O. Duda, P.E. Hart, Use of Hough transform to detect
lines and curves in pictures, Comm. ACM 15 (1) (1972)
11}15.
[5] L.A. Fletcher, R. Kasturi, A robust algorithm for text
string separation from mixed text/graphic images, TPAMI 10 (1988) 910}918.

10

E. O$ ztop et al. / Signal Processing 75 (1999) 1}10

[6] R.M. Haralick, L.G. Shapiro, Computer and Robot Vision,
Addison-Wesley, Reading, MA, 1992, Vol. 1, pp. 602}627.
[7] A.K. Jain, Fundamentals of Digital Image Processing,
Prentice-Hall, Englewood Cli!s, NJ, 1989.
[8] J. Kanai, Text-line extraction using character prototypes,
in: Workshop on Syntactic and Structural Pattern Recognition, Newjersey, 1990, pp. 182}191.
[9] M. Kass, A. Witkin, D. Terzopoulos, Snakes: active contour models, Internat. J. Comput. Vision 1 (1988) 321}331.

[10] V.F. Leavers, Which Hough transform?, CVGIP: Image
Understanding 58 (2) (1993) 250}264.
[11] E. OG ztop, A.Y. MuK laymm, S.S. GuK l, F. Yarman-Vural, V.
Atalay, Repulsive attractive network for baseline extraction, Technical Report TR.95-1, Dept. of Comp. Eng.,
METU, February 1995.
[12] A.A. Atmcm, F.T. Yarman-Vural, A heuristic algorithm forcharacter recognition of Arabic script, Signal Processing
62 (1997) 87}99.