%Template for producing IEEE-format articles using LaTeX.
%written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
%use at your own risk.  Complaints to /dev/null.
% make two column with no page numbering, default is 10 point
\documentstyle[twocolumn,xypic]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and paragraph indent
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}


%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex cosiders descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{10pt}\xpt\@xipt
\abovedisplayskip 10pt plus2pt minus 5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt \belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI}

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{1.0ex plus 1ex minus
 .2ex}{.2ex plus .2ex}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{.2ex plus 1ex}
{.2ex plus .2ex}{\subsize\bf}}
\makeatother

\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16pt)
\title{\Large\bf Page Segmentation by Segment Tracing}
\input{psfig}

\author{O. T. Akindele and A. Bela\"{\i}d\\
	\\
	{\sc Crin-Cnrs/Inria-Lorraine},	B\^atiment LORIA,\\
	Campus Scientifique, {\sc B.P.} 239,\\
	54506 Vand{\oe}uvre-l\`es-Nancy Cedex. France.\\
	e-mail~: \{akindele, abelaid\}@loria.fr
	}
\date{}

\bibliographystyle{plain}
%\renewcommand{\baselinestretch}{1}

\maketitle

%I don't know why I have to reset thispagestyle, but otherwise get
%page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
%IEEE allows italicized abstract
{\em
This paper describes a page segmentation method employed in a document
analysis system. This method allows one to cut a document page image
into polygonal blocks as well as into classical rectangular blocks.
The inter-column and inter-paragraph gaps are extracted as horizontal
and vertical lines. The points of intersection between horizontal and
vertical lines are treated as vertices of polygonal blocks. With the
aid of the 4-connected chain code and an intersection table, simple
isothetic polygonal blocks are constructed from these points of
intersection. The straight line joining two points of intersection
corresponding to  two neighboring 1 entries in the intersection table
is treated as a line segment that forms a side of a polygonal block.
This method is tolerant to skewed documents and also robust enough to
be applied to obtain polygonal blocks of any shape and any number of
sides.}\\
{\bf Keywords}\,:\,{\em Block and page segmentation, Document
Analysis, Chain Code, Isothetic Polygons, Polygonal Blocks, Segment
Tracing.}

\section{Introduction}

Block segmentation is the first step of treatment in any automatic
document analysis system. In this step, a document page is subdivided
into blocks or regions of homogeneous data such as text, halftone,
graphics, etc. All other operations involved in document analysis are
based on the results of this step. The importance of this step in
document analysis has lead many researchers to explore various methods
for document segmentation.  A survey of segmentation methods can be
found in~\cite{nad84}. Most of the methods proposed are based on the
rectangular property of blocks of typical document pages.

Wong {\it et al.}~\cite{won82} proposed an algorithm called the {\it
Run-Length Smoothing Algorithm} (RLSA), for segmenting document pages.
This algorithm works on binary images in which any two neighboring
black pixels that are certain thresholds apart are merged together
into a continuous sequence of black pixels. The RLSA is first applied
row-by-row and then column-by-column yielding two distinct bitmaps.
The two resulting bitmaps are then combined by applying a logical AND
operation to each pixel position in the two bitmaps to produce a final
bitmap. A shortcoming of this algorithm is that it can only be used
to extract small blocks. This is due to the manner in which the
smearing process is performed.

Nagy {\it et al.}~\cite{nag86} proposed a method, R-XY-C (Recursive
X-Y Cuts), that decomposes a document page into a hierarchical
structure using recursive cuts in the horizontal and vertical black
pixel projection profiles of the page image. Thus, the page is
represented in the form of a tree of nested rectangular blocks. The
root of the tree represents the entire page. The descendants of a node
are obtained by successive horizontal and vertical cuttings of the
region represented by the node.

These two techniques work well when the page image under treatment is
not skewed. To resolve the segmentation problem posed by skewed page
image, Pavlidis and Zhou~\cite{pav91} proposed a method based on
``white streams''. This method identifies wide white spaces on
adjacent scan-lines and forms white streams (sequences of these
spaces). The skew angle of the page is estimated from these white
streams and blocks are then located as the regions between these white
streams. The isolated blocks are then placed in accordance with the
skew angle.

The use of special text formatting tools allows one to produce
documents whose blocks are of different kinds of shapes, not
necessarily rectangular. Certain office environments contain many
documents of this type. The existing document analysis systems cannot
handle this type of documents due to lack of appropriate block
segmentation method. Yet, they have to be analyzed and understood for
electronic library archival and distribution. In this paper, we
describe a new method for block segmentation that can handle this type
of documents.

With our method, {\it simple isothetic polygonal} blocks (blocks that
have all their edges oriented in two perpendicular directions) can be
obtained. The method starts by converting horizontal and vertical
white gaps into horizontal and vertical lines. Then, a table of
intersections is built from theses lines after the elimination of the
lines that do not intersect with any other line or that intersect with
only one other line. With the aid of this intersection table, simple
isothetic polygonal blocks are extracted using the 4-connected chain
code. This method is described in detail in the sections that follow.

\section{Extraction of Lines}

The horizontal and vertical white gaps in the page image are extracted
as white rectangles by extracting and merging white segments in the
image. A white segment is a set of consecutive white pixels. A white
rectangle is represented with a quadruple ($x_1,y_1,x_2,y_2$) where
$x_1$ and $y_1$ are the coordinates of its top left corner, and $x_2$
and $y_2$ the coordinates of its bottom right corner. To avoid the
use of the white spaces in character images, or those between
characters, words and/or lines, white segments whose lengths or widths
are less than a certain threshold are discarded.

Horizontal white segments are extracted by traversing the image from
top to bottom. A horizontal white segment is represented with a
triplet ($y,x_1,x_2$), where $y$ is its $y$-coordinate, $x_1$ and $x_2$
are the $x$-coordinates of its starting and end points respectively. Any
white segment that satisfies the condition:\[ x_2 - x_1 + 1 <
\epsilon_{1} \] is not taken into consideration. Each of the segments
extracted in the first scan-line is stored as a rectangle
($x_1,y,x_2,y$). A subsequent segment ($y',x'_1, x'_2$) is merged with
a rectangle ($x_1,y_1,x_2,y_2$) if the following condition is
satisfied: \[|x_1-x'_1| < \epsilon_2 \wedge |x_2-x'_2| <
\epsilon_3 \wedge |y_2-y'| < \epsilon_4. \] A segment that cannot be
merged with any rectangle is stored as a new rectangle.

After the extraction of horizontal white rectangles, those whose
heights are less than a certain threshold ($\epsilon_5$) are deleted.
This is to avoid the use of interline white gaps. Horizontal lines
are obtained from the remaining rectangles by taking the straight
lines that pass through the middle of the rectangles. Vertical lines
are obtained in a similar manner.

\section{Construction of Polygonal Blocks}

Having extracted horizontal and vertical lines respectively from the
horizontal and vertical white gaps in the page image, we proceed to
construct polygonal blocks from these lines. To facilitate this
construction, we make use of an intersection table inside which we
walk around with the aid of 4-connected chain codes and a direction
table. This block construction technique is detailed below.

\subsection{Intersection Table ($IT$)}

The extracted horizontal lines are sorted in ascending order of their
$y$-coordinates and the vertical lines are also sorted in ascending
order of their $x$-coordinates. All vertical lines that 
intersect with no or only one horizontal line are deleted from the
list of vertical lines. Also deleted from the list of horizontal lines
are all horizontal lines that intersect with no or only one vertical
line.

A 2-dimensional table, ($IT$), is constructed from the remaining
horizontal and vertical lines. The number of its rows is equal to the
number of horizontal lines, $N_h$, while that of its column is equal
to the number of vertical lines, $N_v$. Each element $IT(i,j)$, $[1
\leq i \leq N_h, 1 \leq j \leq N_v]$, of the table is filled as
follows~:
\[ IT(i,j) =
	\left\{
		\begin{array}{ll}
			1 & \parbox[t]{2.2in}{if horizontal line $i$
intersects with vertical line $j$}\\
\\
			0 & \mbox{otherwise}
		\end{array}
	\right. \]
As the intersection table is constructed, the coordinates of the
points of intersection are noted and stored. The straight line joining
two points of intersection corresponding to two neighboring 1 entries
in the intersection table can be considered as a line segment that
forms a side of a polygonal block.

\subsection{4-Connected Chain Code}

Each vertex of a simple isothetic polygon is directly connected to the
vertex on its right or left and also to the vertex above or below it.
Therefore, to move from one vertex to another, one needs to move to
the right, or to the left, or up, or down. This has lead to the use of
the 4-connected chain code. A chain code is an integer from 0 to 3
that indicates the direction in which to move from the current vertex
to get to the next one as shown in figure~\ref{ccode}. Thus a chain
code of 0 indicates a movement to the right, 1, a movement up, 2, a
movement to the left and 3, a movement down. Figure~\ref{sdir}
illustrates the search directions beginning at a given vertex.

\begin{figure}[hbtp]
$$\diagram
			& \Text{(up)\\ \vspace*{6mm}1}\\
	\Text{(left) 2}	& \bullet \rto \lto \uto \dto & \Text{0 (right)}\\
			& \Text{3\\ \vspace*{6mm}(down)}\\
\enddiagram$$
\caption{\label{ccode} 4-Connected chain codes}
\end{figure}

%\begin{figure}
%\centerline{\psfig{figure=moved.eps}}
%\caption{\label{mdir} Search directions from a given vertex}
%\end{figure}

\subsection{Direction Table ($DT$)}

There are four directions of movement, therefore, the direction table
($DT$) is a $4 \times 4$ 2-dimentional matrix. Each of its elements is
a triplet $(\delta_i, \delta_j, d)$, where ``$d$'' is the chain code
for the direction of movement to follow to get to the next vertex,
$\delta_i$ and $\delta_j$ are respectively the increment steps for the
indices to access the row and column of the intersection matrix. The 
elements of a row in the $DT$ indicate the directions of movement to
be followed, in order, to get to the next vertex. If the current vertex
corresponds to the element $IT(c_i,c_j)$ of the intersection matrix
and that it was obtained by moving in the direction $c_d~(0 \leq c_d
\leq 3)$, the directions given by $(\delta_i, \delta_j, d)$ of
eps$DT(c_d, 0)$, $DT(c_d, 1)$, $DT(c_d, 2)$ and $DT(c_d, 3)$ will be
searched, in order, to get to the next vertex. Table~\ref{dirtab}
shows the direction matrix used in our implementation. The elements in
row 0 show that if the current vertex is obtained by moving in the
direction with code 0, the search for the next vertex will be done
first in the direction ``3'', if there is no success, then in the
direction ``0'' and later in direction ``1'' and  lastly in direction
``2''. The element $DT(0,0),~(1,~0,~3)$, shows that to move in the
direction with code 3, one needs to add 1 to the row index and 0 to
the column index to access the intersection table. In the event of
success, the next direction to be followed is given by the first entry
in row 3 $DT(3,0),~(0, -1, 2)$.

\begin{table}[hbtp]
\centerline{\psfig{figure=tabs.eps}}
\caption{\label{dirtab} Direction matrix}
\end{table}


\subsection{Segment Tracing}

The search for blocks is done by walking through $IT$ row-by-row. The
idea is to start the search from each ``1'' entry in $IT$ and then
walk through the table with the aid of the entries in $DT$ until the
starting point is reached again, noting the direction of movement at
each change of direction. The search for a ``1'' entry in any
direction starts at a given point and continues in the direction until
a ``1'' entry is reached or until the edge of the table as shown in
figure~\ref{sdir}. From the starting point, the first direction of
movement is always ``0'' (i.e. to the right).
\begin{figure}
\centerline{\psfig{figure=search0.eps}}
\caption{\label{sdir} Search for block vertices in $IT$}
\end{figure}

The points of intersection corresponding to the ``1'' entries visited
are stored in a queue as they are obtained. At the end of a search,
the points in the queue are taken as the vertices of a polygonal
block. The search directions and the sequence of vertices searched
during the tracing of a polygon ensure that the trace always follows the
segments of the polygon. The entries of the last row and last column of
$IT$ are never taken as starting points for obvious reasons.

The search for a polygonal block begins at a given ``1'' entry in
$IT$. The $IT$ entry of the starting point is changed to 2 at the
beginning of a search. The first direction of movement always has
chain code 0. Each time a new point is obtained the code of the
direction of movement leading to it is compared with that of the
direction that lead to the immediate previous point. When the two
directions are equal, the last point in the queue is deleted if the
current point is the starting point, or replaced with the current
point otherwise.

If it is not possible to proceed with the trace, {\it i.e.} no vertex
is found in all the directions indicated in the $IT$, the current
search is abandoned. When a search is abandoned, the $IT$ entry of
its starting vertex is changed back to ``1''.

When a ``2'' entry is encountered in $IT$, if it is not the starting
point of the current search, the search is abandoned and a new
search will be started on the next row of $IT$. Otherwise, the points
in the queue are then emptied as the vertices of a new block and a new
searching begins by taking as the starting point, the position of the
second point of the previous search.

\section{Experiments and Results}

The method has been implemented using C codes and on a SUN SPARC
station IPX under SunView environment. It has been tested using a
series of document pages obtained from scientific journals and other
magazines. The pages are scanned with Hewlett Packard Scan Jet IIc
scanner, with a resolution of 300dpi, producing binary images of
dimensions 2550$\times$3500 pixels.

It gives satisfactory results on all tested images and takes about 6
seconds par page. Figure~\ref{res0}(a) shows an example of document
pages we work with, while the results of the application of our method
on the sample page are illustrated in figure~\ref{res0}(b).
%Figures~\ref{res00}(a) is an example of document page images on which
%the ``R-XY-Cuts'' would fail (no complete horizontal or vertical
%passage), while the results of the application of our method are shown
%in figures~\ref{res00}(b).

\begin{figure*}
\centerline{\psfig{figure=sample1.eps,width=18cm}}
\caption{\label{res0} Example of a document page image and its
segmented blocks}
\end{figure*}

%\begin{figure*}
%\centerline{\psfig{figure=sample3.eps}}
%\caption{\label{res00} Example of a page image where R-XY-Cuts would fail}
%\end{figure*}

With this method, it is possible to obtain empty blocks. By an empty
block we mean an image region containing only white pixels. This type
of block must be removed from the list of extracted blocks. This is
done by calculating the density, $\mu$, of each extracted block as
follows~: 
\[ \mu =
\frac{Number~of~Black~Pixels~in~the~Block}{Surface~Area~of~the~Block}
\]
Any block whose density is equal to zero is removed. To eliminate
noise, any block whose density is less than a certain threshold is
also removed.

\section{Discussion}

It is obvious that the use of 4-connected chain code allows one to
extract polygonal blocks with even number of sides. These are usually
the type of blocks encountered in printed documents. However, this
method can be modified to handle polygonal blocks with odd
number of sides as well.

The first thing to be modified is the line extraction module. One will
need a method that can extract lines in any direction. Secondly, the
use of 4-connected chain codes will have to be replaced by Freeman's
chain code (8-connected chain code) and consequently the direction
table too has to be changed accordingly.

\section{Conclusion}

We have presented a method based on segment tracing, for document
page segmentation. This method converts the inter-column and
inter-paragraph gaps into horizontal and vertical lines and builds an
intersection table from the lines. The entries of this table are used
to construct simple isothetic polygonal blocks with the aid of
4-connected chain code and a direction table. The method is robust
enough that it can be applied to obtain polygonal blocks of any shape
and any number of sides.

\begin{thebibliography}{99}
\small{
\bibitem{may87} W. D. May,
{\em 3-D Images from Contour Maps}. Dr. Dobb's Journal, pp. 18--28,
Nov. 1987.

\bibitem{nad84} Morton Nadler,
{\em Document Segmentation and Coding Techniques}, CVGIP 28, pp.
240--262, 1984.

\bibitem{nag84} G. Nagy and S. Seth,
{\em Hierarchical Representation of Optical Scanned Documents}. In
Proceedings of the 7th International Conference on Pattern
Recognition, Montr\'eal, pp. 347--349, 1984.  

\bibitem{nag86} G. Nagy, S. C. Seth and S. D. Stoddard,
{\em Document Analysis with an Expert System}, Pattern Recognition in
Practice II (E. S. Gelsema and C. N. Kanal, Eds) pp. 147--159, 1986.

\bibitem{pzh91} T. Pavlidis and J. Zhou,
{\em Page Segmentation and Classification}. Technical Report No.
TR.91.09.30 Dept. of Computer Science, SUNY at Stony Brook, 1991.

\bibitem{pav91} T. Pavlidis and J. Zhou,
{\em Page Segmentation by White Streams}. In Proceedings of the 1st
International Conference on Document Analysis and Recognition, Vol. 2,
St-Malo, France. pp.945--953, 1991.

\bibitem{wan89} D. Wang and S. N. Srihari,
{\em Classification of Newspaper Image Blocks Using Texture Analysis}.
CVGIP 47, pp. 327--352, 1989.

\bibitem{won82} K. Y. Wong, R. G. Casey and F. M. Wahl,
{\em Document Analysis system}. IBM Journal of Research and
Development 26, pp. 647--655, 1982.
}
\end{thebibliography}

%\onecolumn
%\newpage

%\begin{sidefigure}
%\centerline{\psfig{figure=cnrsdoc.eps}}
%\caption{\label{res0} Example of a document page image and its
%segmented blocks}
%\end{sidefigure}

%\newpage

%\begin{sidefigure}
%\centerline{\psfig{figure=news4.eps}}
%\caption{\label{res1} Another example of a document page image and its
%segmented blocks}
%\end{sidefigure}

%\newpage

%\begin{sidefigure}
%\centerline{\psfig{figure=point.eps}}
%\caption{\label{res00} Example of a page image where R-XY-Cuts would fail}
%\end{sidefigure}

%\newpage

%\begin{sidefigure}
%\centerline{\psfig{figure=newsdoc.eps}}
%\caption{\label{res01} Yet another example of a document page image
%and its segmented blocks}
%\end{sidefigure}

\end{document}
