# Chandra HETG X-ray Spectra and Variability of $\pi\,$Aqr, a $\gamma\,$Cas-
type Be star.

David P. Huenemoerder Kavli Institute for Astrophysics and Space Research,
Massachusetts Institute of Technology , 77 Massachusetts Ave., Cambridge, MA
02139, USA  Pragati Pradhan Embry Riddle Aeronautical University, Department
of Physics & Astronomy, 3700 Willow Creek Road Prescott, AZ 86301, USA  Claude
R. Canizares Kavli Institute for Astrophysics and Space Research,
Massachusetts Institute of Technology , 77 Massachusetts Ave., Cambridge, MA
02139, USA  Sean Gunderson Kavli Institute for Astrophysics and Space
Research, Massachusetts Institute of Technology , 77 Massachusetts Ave.,
Cambridge, MA 02139, USA  Richard Ignace Department of Physics & Astronomy,
East Tennessee State University, Johnson City, TN 37614 USA  Joy S. Nichols
Harvard & Smithsonian Center for Astrophysics, 60 Garden St., Cambridge, MA
02138, USA  A. M. T. Pollock Department of Physics and Astronomy, University
of Sheffield, Hounsfield Road, Sheffield S3 7RH, UK  Norbert S. Schulz  Kavli
Institute for Astrophysics and Space Research, Massachusetts Institute of
Technology , 77 Massachusetts Ave., Cambridge, MA 02139, USA  Dustin K. Swarm
Department of Physics and Astronomy, University of Iowa, Iowa City, IA, USA
José M. Torrejón Instituto Universitario de Física Aplicada a las Ciencias y
las Tecnlogías, Universidad de Alicante, E- 03690 Alicante, Spain

###### Abstract

High-resolution X-ray spectra of $\pi\,$Aqr, a $\gamma\,$Cas-type star,
obtained with the Chandra/HETG grating spectrometer, revealed emission lines
of H-like ions of Mg, Si, S, and Fe, a strong, hard continuum, and a lack of
He-like ions, indicating the presence of very hot thermal plasma. The X-ray
light curve showed significant fluctuations, with coherent variability at
period of about $3400\,$s in one observation. The hardness ratio was
relatively constant except for one observation in which the spectrum was much
harder and more absorbed. We interpret the X-ray emission as arising from
accretion onto the secondary, which is likely a magnetic white dwarf, an
intermediate polar system.

Be stars (142), White dwarf stars (1799), X-ray astronomy (1810), High
resolution spectroscopy (2096), Gamma Cassiopeiae stars (635), Early-type
emission stars (428)

††software: CIAO (Fruscione et al., 2006), ISIS (Houck & Denicola, 2000)

Accepted for publication in ApJL

††thanks<EMAIL_ADDRESS>
##  1 Introduction

$\pi\,$Aqr was recently identified as a $\gamma\,$Cas-type star by Nazé et al.
(2017). The $\gamma\,$Cas-types are O/Be stars which in X-rays have unusually
hard spectra, with characteristic temperatures exceeding $100\,\mathrm{MK}$
($8.6\,\mathrm{keV}$), yet appear to be thermal due to presence of Fe xxv and
Fe xxvi emission lines. Given their thermal spectrum and low X-ray
luminosities, their nature as accreting X-ray binaries containing a neutron
star or a black hole companion is ruled out. Several $\gamma\,$Cas types are
known to be some form of binary including $\pi\,$Aqr (Bjorkman et al., 2002):
it is the nature of the companion which makes them of special interest.
Postnov et al. (2017) proposed a neutron star where direct accretion is
impeded magneto-centrifugally, the so called propeller state. Langer et al.
(2020) gave an account of possible evolutionary states, with preference for
stripped-core companions, either SdO or He-stars. Gies et al. (2023) argued
that SdO companions would be bright enough to see optically, so they prefer a
white dwarf companion hypothesis. Tsujimoto et al. (2018), based on X-ray
spectral modeling of two $\gamma\,$Cas-type stars, also prefer a white dwarf
companion. In XMM-Newton spectra of $\pi\,$Aqr, Nazé et al. (2017) found a
plasma temperature of about $10\,\mathrm{keV}$ ($116\,\mathrm{MK}$) from
isothermal fits of thermal spectra, and found no significant emission line
features in the lower-energy RGS spectral band. In Swift data, Nazé et al.
(2019) had similar results requiring an isothermal plasma with
$kT=15\,\mathrm{keV}$ ($T=174\,\mathrm{MK}$), and local absorption of about
$N_{\mathrm{H}}=0.5\times 10^{22}\,\mathrm{cm^{-2}}$. Tsujimoto et al. (2023)
modeled NuSTAR and XMM-Newton spectra of $\pi\,$Aqr and found a maximum
temperature of $19\,\mathrm{keV}$ ($220\,\mathrm{MK}$) from a cooling flow
model (Pandel et al., 2005), concluding that $\pi\,$Aqr could host either a
magnetic or non-magnetic white dwarf. The interferometric survey of Be stars
by Klement et al. (2024) included several $\gamma\,$Cas-type stars with X-ray
emission. They failed to detect any companions, and excluded SdO and main-
sequence companions for $\pi\,$Aqr, leaving a white dwarf as the most viable
secondary and source of X-ray emission.

Here we present X-ray spectral and temporal properties of $\pi\,$Aqr revealed
by recent Chandra/HETG observations. § 2 details the observations and
reduction of the Chandra HETG data. The spectra are described and interpreted
through spectral modeling in § 3. Finally in § 4 we comment on variability
observed in our dataset, in particular a notable hardening of the spectra
arising from a jump in absorbing column density during the last of our
observational sets.

##  2 Observations and Processing

We obtained Chandra/HETG data for $\pi\,$Aqr in six observations made during
August to October, 2022, for a total exposure of $101\,\mathrm{ks}$. Details
are provided in Table 1.111Data are available at
https://doi.org/10.25574/ObsID, where $ObsID$ is to be replaced with the
values from Table 1. Canizares et al. (2005) gave a description of the
instrument. Data were processed with CIAO (Fruscione et al., 2006) following
standard procedures, except for use of a narrower spatial region defining the
HEG and MEG loci. This removes ambiguity between the two grating types at the
shortest wavelengths, and can improve flux determination below $\sim
1.8\,\mathrm{{\mbox{\AA}}}$ in particular for hard sources where standard
regions overlap. Spectra were analyzed using the ISIS package (Houck &
Denicola, 2000) in conjunction with AtomDB (Foster et al., 2012). For timing
analysis, we used the SITAR ISIS package222For a description of SITAR
routines, see https://space.mit.edu/cxc/analysis/SITAR/., as distributed with
ISISscripts.333The ISISscripts package is available from
http://www.sternwarte.uni-erlangen.de/isis/.

Table 1: $\pi\,$Aqr Observational Information

ObsID | DATE-OBS | Exposure | $\phi_{\mathrm{orb}}$
---|---|---|---
| [Chandra start date] | [$\,\mathrm{ks}$] |
10.25574/26079 (catalog 26079) | 2022-08-23T15:37:02 | 9.93 | 0.40
10.25574/27269 (catalog 27269) | 2022-08-27T04:24:31 | 9.99 | 0.44
10.25574/26080 (catalog 26080) | 2022-09-05T00:58:47 | 29.67 | 0.54
10.25574/26001 (catalog 26001) | 2022-09-13T00:14:35 | 19.80 | 0.64
10.25574/27412 (catalog 27412) | 2022-09-14T06:16:23 | 21.78 | 0.65
10.25574/27325 (catalog 27325) | 2022-10-30T09:44:35 | 9.76 | 0.20

Note. — The orbital phase is defined as $0.0$ for the maximum radial velocity
(redshift) of the secondary, using the error-weighted-mean ephermeris of
Bjorkman et al. (2002): $T_{0}=2450274.84\,\mathrm{JD}$,
$P=84.132\,\mathrm{day}$.

##  3 Spectrum and Modeling

We analyzed the spectrum in two parts because one observation, with about
$10\,\mathrm{ks}$ of the $100\,\mathrm{ks}$ total exposure, had a very
different character in terms of hardness (see § 4 for variability details). We
show the low hardness ratio state HETG spectrum in the left side of Figure 1,
where strong Fe xxv ($1.85\,\mathrm{{\mbox{\AA}}}$) and Fe xxvi
($1.78\,\mathrm{{\mbox{\AA}}}$) emission lines are seen, with a shoulder on
the red side of the He-like line that may be Fe K$\alpha$ fluorescence. The
rest of the spectrum clearly shows the H-Ly$\alpha$-like emission lines from S
xvi ($4.73\,\mathrm{{\mbox{\AA}}}$), Si xiv ($6.18\,\mathrm{{\mbox{\AA}}}$),
and Mg xii ($8.42\,\mathrm{{\mbox{\AA}}}$) on top of a strong continuum. There
may be some Fe xxiv emission lines near Mg xii and between
$10$–$13\,\mathrm{{\mbox{\AA}}}$. The He-Ly$\alpha$-like emission lines from
S, Si, and Mg are conspicuous in their absence. These characteristics point to
very high-temperature plasmas; the H-like lines, except for Fe, are weak
because the plasma is dominated by temperatures well above the peaks of the
emissivity functions, on the long tail of the H-like emissivities and well
beyond the significant region of He-like emissivity. In an isothermal plasma,
to obtain a limit in the Si xiii to Si xiv flux less than the observed ratio
of $<0.10$ requires a temperature greater than $42\,\mathrm{MK}$, and to
obtain the observed ratio of Fe xxvi to Fe xxv requires a temperature of at
least $70\,\mathrm{MK}$.

Figure 1: Left: HETG spectrum of $\pi\,$Aqr in black, which is the merged HEG
and MEG first orders, excluding the high hardness ratio observation (27325).
In red is a model using three APEC components plus a Gaussian for the putative
Fe K fluorescence. On the right, we compare the high hardness ratio state
spectrum (blue) to the rest (black and red).

To characterize the spectrum more systematically, we have fit a few-
temperature model using AtomDB emissivities. For such a hot plasma, the
continuum shape provides limited leverage on the temperature, since above
about $100\,\mathrm{MK}$, the turnover of the thermal bremsstrahlung occurs
below $2\,\mathrm{{\mbox{\AA}}}$, and the shape above that is largely flat and
featureless. We find that three temperatures are sufficient to describe the
spectrum, to which we added a Gaussian for the possible Fe K$\alpha$
fluorescence. Each temperature component shared a common Doppler shift and
“turbulent” broadening term for any Gaussian intrinsic width. Instrumental
broadening is handled by forward-folding through the calibrated responses, and
common elemental abundances, for which Mg, Si, S, and Fe were free to vary.
However, for few-temperature plasmas, abundances are degenerate with
temperature since there are two ways to change a model line flux: vary the
temperature, or vary the abundance. Should the temperature not be accurate,
the abundance will be not be accurate as well. We also include a single
absorption term, however note that the foreground interstellar absorption is
small in this band ($\sim 0.03\times 10^{22}\,\mathrm{cm^{-2}}$, Gudennavar et
al. (2012)).

The fit converges on a very hot component to produce enough Fe xxvi and to
provide the correct shape between $1.7\,\mathrm{{\mbox{\AA}}}$ an
$3\,\mathrm{{\mbox{\AA}}}$. However, the Fe xxvi flux is rather uncertain by
about 40%, so anything over $\sim 200\,\mathrm{MK}$ would be adequate. A
component of about $40\,\mathrm{MK}$ is required to give the observed Fe xxv
flux, some Fe xxvi, and most of the S xvi emission, plus Si xiv, Mg xii, and
Fe xxiv. The third component, at $10\,\mathrm{MK}$ also contributes to the
H-like series, and to the Fe xxiv ionization, but this component has the
lowest normalization. However, if larger, it would contribute to Si xiii,
which is weak or absent. The emission measure, for a distance of
$286\,\mathrm{pc}$ (Gaia Collaboration et al., 2016, 2018) is $1.0\times
10^{55}\,\mathrm{cm^{-3}}$. The absorption required is $N_{\mathrm{H}}\sim
0.4\times 10^{22}$, which has a transmission factor of about $0.3$ at
$13\,\mathrm{{\mbox{\AA}}}$. The absorbed model flux in the
$0.5$–$10\,\mathrm{keV}$ band is $1.5\times
10^{-11}\,\mathrm{erg\,cm^{-2}\,s^{-1}}$, and the X-ray luminosity is
$1.8\times 10^{32}\,\mathrm{erg\,s^{-1}}$. The lines required some broadening
beyond instrumental, with a turbulent velocity term of $\sim
400\,\mathrm{km\,s^{-1}}$, which corresponds to S xvi, Si xiv and Mg xii full-
widths, half-maxima ($FWHM$s) of about $900\,\mathrm{km\,s^{-1}}$ (for
$T=40\,\mathrm{MK}$). The Doppler shift from the global fit was $+64\pm
66\,\mathrm{km\,s^{-1}}$, without correction for the line-of-sight velocities
at these epochs, which is less than $7\,\mathrm{km\,s^{-1}}$. The range is
incommensurate with the Bjorkman et al. (2002) solution for the secondary at
these phases of about $-70\,\mathrm{km\,s^{-1}}$. Plasma model details are
given in Table 2.

We have also fit the few emission lines with intrinsic Gaussian profiles,
folded through the instrument response, in order to determine fluxes, velocity
offsets, and widths. The features with signal-to-noise ratio $>3$ and which
have good resolution are Si xiv and Mg xii. These have $FWHM\sim
800\,\mathrm{km\,s^{-1}}$, consistent with the plasma model determination.
Their Doppler shifts are consistent with $0\,\mathrm{km\,s^{-1}}$. Line fit
details are given in Table 3.

The right panel of Figure 1 shows the high hardness state spectrum compared to
the low hardness state. We see that the high hardness state is brighter below
$4\,\mathrm{{\mbox{\AA}}}$, but much more absorbed. We fit this hard state
spectrum with a two temperature model since less information is available from
emission lines - only Fe xxv, being so heavily absorbed, and having only
$10\,\mathrm{ks}$ exposure. The plasma is much hotter, has higher flux, and
much greater absorption. Details are given in Table 2

Table 2: $\pi\,$Aqr Plasma Model Fit Parameters

Parameter | Value | $\sigma$ | Value | $\sigma$ | Unit
---|---|---|---|---|---
| Normal HR | High HR |
$T_{1}$ | $270$ | $94$ | $>520$ |  | $\,\mathrm{MK}$
$T_{2}$ | $44$ | $11$ | $70$ | $20$ | ”
$T_{3}$ | $13$ | $3$ |  |  | ”
$norm_{1}$ | $7.3$ | $0.8$ | $21.1$ | $3.6$ | $10^{-11}\mathrm{cm^{-5}}$
$norm_{2}$ | $2.7$ | $1.0$ | $6.0$ | $2.8$ | ”
$norm_{3}$ | $0.4$ | $0.3$ |  |  | ”
$v_{\mathrm{turb}}$ | $404$ | $169$ |  |  | $\,\mathrm{km\,s^{-1}}$
$\Delta v$ | $64$ | $66$ |  |  | ”
$A$(Mg) | $1.2$ | $0.3$ |  |  | Relative to Solar
$A$(Si) | $0.7$ | $0.2$ |  |  | ”
$A$(S) | $1.3$ | $0.4$ |  |  | ”
$A$(Fe) | $0.6$ | $0.1$ |  |  | ”
$N_{\mathrm{H}}$ | $0.40$ | $0.05$ | $4.7$ | $0.2$ | $10^{22}\,\mathrm{cm^{-2}}$
$EM$ | $1.0$ | $0.1$ | $2.6$ | $0.4$ | $10^{55}\,\mathrm{cm^{-3}}$
$f_{\mathrm{x}}$ | $1.50$ |  | $2.54$ |  | $10^{-11}\,\mathrm{erg\,cm^{-2}\,s^{-1}}$
$L_{\mathrm{x}}$ | $1.81$ |  | $4.38$ |  | $10^{32}\,\mathrm{erg\,s^{-1}}$

Note. — “Normal HR” refers to all observations except 27325, and “High HR” is
for 27325 in the high hardness-ratio state. Flux is integrated from the model
over the $0.5$–$10\,\mathrm{keV}$ band. The emission measure used a distance
of $D=286\,\mathrm{pc}$, and is related the the normalizations by a factor of
$10^{11}4\pi D^{2}$. Relative abundances are referenced to Anders & Grevesse
(1989). Uncertainties are $1\sigma$.

Table 3: $\pi\,$Aqr Line Fit Parameters

Line | $\lambda_{0}$ | $\Delta v$ | $\sigma$ |  $10^{6}\times$Flux | $\sigma$ | $FWHM$ | $\sigma$
---|---|---|---|---|---|---|---
| [ Å] | [$\,\mathrm{km\,s^{-1}}$] | [$\,\mathrm{phot\,cm^{-2}\,s^{-1}}$] | [$\,\mathrm{km\,s^{-1}}$]
Fe xxvi | $1.7798$ |  $\cdots$ |  $\cdots$ | $8.5$ | $3.4$ | $0.0$ | $1320$
Fe xxv | $1.8554$ | $-48$ | $276$ | $20.7$ | $4.8$ | $2372$ | $1101$
FeK$\alpha$ | $1.94$ | $-950$ | $773$ | $4.5$ | $2.4$ |  $\cdots$ |  $\cdots$
S xvi | $4.7301$ | $-240$ | $630$ | $5.3$ | $2.1$ |  $\cdots$ |  $\cdots$
Si xiv | $6.1831$ | $92$ | $123$ | $6.0$ | $1.5$ | $778$ | $582$
Si xiii(r) | $6.6479$ |  $\cdots$ |  $\cdots$ | $<1.2$ |  $\cdots$ |  $\cdots$ |  $\cdots$
Mg xii | $8.4219$ | $28$ | $71$ | $9.9$ | $1.7$ | $840$ | $280$

Note. — Wavelengths for Fe xxvi and Fe xxv are weighted means over the
components in each group; each was fit with a single Gaussian model. The Fe
xxvi offset from Fe xxv was frozen. The width of FeK$\alpha$ was tied to that
of Fe xxvi. The S xvi width was tied to that of Si xiv, since the former has a
fairly low signal-to-noise ratio. The flux limit on the Si xiii resonance line
was computed with a frozen position and a width frozen at the value for Si
xiv. Uncertainties are for $68\%$ confidence intervals.

##  4 Variability

It is well known that $\gamma\,$Cas-type stars are variable in optical and
X-ray bands (Nazé et al., 2020b, c, a). Optical variability can be highly
periodic and is generally attributed to the B-star’s rotation or pulsations.
X-ray fluctuations can exceed factors of two or three in short times, behavior
often referred to as “flaring” (but not like coronal flares in the Sun and
late-type stars, which have increases in both flux and temperature and are
strongly tied to stellar magnetism).

Figure 2: Left top: The X-ray light curve of $\pi\,$Aqr for all observations
for the $1.7$–$13\,\mathrm{{\mbox{\AA}}}$ band, concatenated in time order.
The vertical dashed lines mark arbitrary length gaps between observations. The
black curve shows the count rate in dispersed first-order events. The red and
orange curves show the results of Bayesian blocks (Scargle et al., 2006, 2013)
and Gregory-Loredo (Gregory & Loredo, 1992) algorithms, confirming the
statistically significant variability. Left bottom: the count-rate hardness
ratio, $(H-S)/(H+S)$, where $H$ is the “hard” rate in the
$1.7$–$5.2\,\mathrm{{\mbox{\AA}}}$ band, and $S$ in
$5.2$–$13\,\mathrm{{\mbox{\AA}}}$ for “soft”. The last observation (27325)
does not stand out in the total rate curve, but does in hardness. Labels at
the top give the observation IDs with orbital phases below them. Right: epoch
folding algorithm (Davies, 1990) “$L$”-statistic for obsid 26080 showing
coherent variability with period near $3400\,$s.

We extracted X-ray light curves of $\pi\,$Aqr from the dispersed first-order
events and found significant variability with about a factor of two amplitude
in count rate. For the longest observation ($\sim 30\,\mathrm{ks}$;
Observation ID 26080) of the six segments, we also found significant cyclic
variability, with a period of about $3400\,$s. In Figure 2 we show light curve
and hardness ratio for all observations, and the epoch-folding period search
for the segment showing the strongest periodic signal. To our knowledge, this
is only the second case of a clear X-ray modulation with an approximately one
hour period in a $\gamma\,$Cas-type star, the first being found by Lopes de
Oliveira et al. (2006) in HD 161103. The other segments, which range from $10$
to $22\,\mathrm{ks}$ exposures, had statistically significant variability, but
not as strong an indication of coherence.

The hardness ratio, defined as $(H-S)/(H+S)$, with $H$ and $S$ defined as
count rates in bands chosen to on average have equal counts
($H:1.7$–$5.2\,\mathrm{{\mbox{\AA}}}$, $S:5.2$–$13\,\mathrm{{\mbox{\AA}}}$),
was relatively constant for most of the time, as we show in the left hand side
of Figure 2, bottom panel. The last observation, however, stands out as
extremely hard, which led us to analyze the spectrum of that state separately.

##  5 Interpretations

The HETG observations presented here strongly support the case that the
$\pi\,$Aqr B-star’s companion is an accreting white dwarf. The emission lines
of H-like ions show that there is thermally emitting plasma, and that the
temperature is high, given the lack of He-like ions for anything but Fe.
Furthermore, the continuum is consistent with Bremsstrahlung for the same
temperature required for the emission lines. Even though the spectral turnover
is below $2\,\mathrm{{\mbox{\AA}}}$, there is some leverage in the spectral
curvature in the observed band. The temperatures we have derived are
consistent with free-fall accretion onto a white dwarf with mass between
$0.5$–$0.8\,M_{\odot}$ (Mukai, 2017; Tsujimoto et al., 2023). This is
consistent with prior XMM-Newton and NuSTAR observations, but since emission
lines are weak, the HETG band and spectral resolving power were required to
detect and characterize them. The best characterized lines, those of Mg xii
and Si xiv, have similar widths and centroid offsets as in early B-star
stellar winds, but they are an order of magnitude more luminous in $\pi\,$Aqr,
and cooler species are missing (Pradhan et al., 2023). Consequently, the
spectrum is incompatible with a superposition of a powerlaw continuum with a
B-star thermal spectrum.

The detection of variability with a period of about $3400\,\mathrm{s}$
suggests that if the companion is a white dwarf, that it is magnetic, such as
in an intermediate polar where accretion is funneled onto the white dwarf by a
moderately strong global magnetic field. The period would then be rotational
modulation. The breadth of the peak obtained through epoch folding is also
reminiscent of the compact object being a white dwarf (see Figure 2 in Hui et
al., 2012) as opposed to a neutron star where narrower peaks are expected
because of the very coherent pulsations. The coherent variability was only
seen in one observation, however. The others show both similar amplitude but
more sporadic fluctuations and also changes in the mean flux level. One would
expect under the hypothesis of an accreting white dwarf, that if the accretion
is steady, and the polar region of a white dwarf always visible, then the
rotational “clock’s” pulsations would be persistent. The variations are
obviously due to something more complicated than a coherent rotationally
modulated accretion spot. We have evidence that very large changes can occur.
In addition to periodic modulation and irregular variations, there was the
state with the high hardness ratio. The absorption increased by an order of
magnitude, while the flux nearly doubled, and the luminosity more than
doubled. We do not know if this is a random episodic or a phase-dependent
event. It occurred near orbital phase $0.2$, when viewing the companion behind
the B-star, through the B-star wind, and perhaps downstream along the
accretion column (see Tab. 1 and Fig. 2). The Swift monitoring by Nazé et al.
(2019) also has their highest absorption near this phase.

There is precedent for complex structure in intermediate polar accretion
disks, with bulges, streams, and veiling which can perturb light curves, such
as has been seen in optical, UV, and X-ray observations of EX Hya (Belle et
al., 2002, 2005). Hiding spin modulation in X-rays with disk instabilities is
very speculative, however, and will require longer term X-ray monitoring to
separate coherent modulation from other variability. One would have to either
hide the accretion hot spot with strong absorption, or mask the rotational
pulsations with other fluctuations. Empirically, we can say that there is
sometimes coherent X-ray modulation, but also more random fluctuations, and
large, persistent changes in spectral hardness. These all suggest complex and
variable X-ray emitting and absorbing structures.

While our evidence is circumstantial, we suggest that the $\pi\,$Aqr
variations indicate that a white dwarf companion is likely, given the episode
of periodic variation. But there is some other source of variability which can
change emission and absorption levels. We cannot determine from our dataset
whether this is stochastic, episodic, or orbitally phase dependent.

Figure 3:  The $\pi\,$Aqr model (red), with absorption removed and
renormalized to the observed mean flux of EX Hya, an intermediate polar
(black). The continuum shapes are similar, but the $\pi\,$Aqr emission lines
are weaker relative to the continuum, and especially the He-like features,
which have a much lower He- to H-like ratios.

EX Hya is a well studied intermediate polar with a white dwarf rotation period
of about $4000\,$s (Warner, 1983; Luna et al., 2015), similar to our detected
period in $\pi\,$Aqr. To compare X-ray spectra, we took our three-temperature
model, removed the absorption and renormalized to the HETG-observed flux of EX
Hya. We found overall qualitative agreement, but with some interesting
differences. Figure 3 shows our unabsorbed model against the observed EX Hya
spectrum, which has little neutral absorption
($N_{\mathrm{H}}<10^{20}\,\mathrm{cm^{-2}}$; Luna et al. (2015)). EX Hya has
emission from the H- and He-like ions of O, Ne, Mg, Si, S, Ar, Ca, and Fe (see
details in Luna et al., 2015). In $\pi\,$Aqr, we only see the H-like lines of
Mg, Si, S, and Fe, as well as He-like Fe; longward of
$13\,\mathrm{{\mbox{\AA}}}$, $\pi\,$Aqr absorption is too strong for detection
at our exposure. The differences seen, however, show that the $\pi\,$Aqr
plasma is substantially hotter than that of EX Hya, since the He-like lines
are extremely weak in $\pi\,$Aqr. Our emission measure distribution for
$\pi\,$Aqr, though with only 3 points, rises steadily from $\log T\approx 7.1$
to $8.5$. This parallels (at about 10 times the amplitude) the simple cooling
flow model of Luna et al. (2015) for EX Hya, which they rejected in favor of
their empirical model which declines steeply above about $7.8\,$dex. Below
$\log T\sim 7.1$, if we extrapolate our emission measure to follow the simple
cooling flow model, we cannot tell if such plasma exists in $\pi\,$Aqr because
the predicted fluxes are below our sensitivity limit; the hot plasma greatly
overwhelms any cooler plasma signature. It could be that the putative white
dwarf in $\pi\,$Aqr is more massive than that in EX Hya. According to Yuasa et
al. (2010), a change of a few tenths of a Solar mass of a white dwarf can
change the shock temperature by a factor of two. Hence, we tentatively
conclude that there is a white dwarf companion in $\pi\,$Aqr with somewhat
more mass than the one in EX Hya, which is estimated by Luna et al. (2015) to
be $0.79\,M_{\odot}$. The emission measure distribution of $\pi\,$Aqr seems
consistent with a cooling flow model, but higher signal-to-noise X-ray spectra
will be required to quantify the contribution of cooler plasma through
detection of He-like ion emission.

Our characterization with a few-temperature, slab-absorbed model is very
rudimentary. We are beginning to apply cooling flow models, in which a
continuous emission measure distribution is weighted inversely by the cooling
time (Mushotzky & Szymkowiak, 1988; Pandel et al., 2005; Böhringer & Werner,
2010). Other refinements were implemented by Tsujimoto et al. (2023), such as
partial covering, and reflection models to explain Fe K fluorescence. The
cooling flow models specify a mass accretion rate through the X-ray luminosity
and temperature extrema. For a simple, slab-absorbed, geometry-independent
(optically thin) cooling-flow model, we obtained mass accretion rates for the
low and high hardness states of $4\times 10^{-11}$ and $7\times
10^{-11}\,M_{\odot}\,\mathrm{yr}^{-1}$. These values are within an order of
magnitude for low-accretion-rate intermediate polars. For the expected
decretion disc densities at the white dwarf orbital separation (Jones et al.,
2008), accretion rates up-to $10^{-8}-10^{-7}\,M_{\odot}\,\mathrm{yr}^{-1}$
can be supported (assuming spherical accretion).

The high-resolution X-ray spectra presented here have further supported the
cases put forward by Tsujimoto et al. (2023) and Klement et al. (2024) that
the dominant X-ray source in $\pi\,$Aqr is a magnetic white dwarf, probably an
intermediate polar. Further observations are warranted, in particular long
observations to monitor coherent variability, and phase-resolved coverage to
separate geometric from stochastic variability.

Support for this work was provided by NASA through the Smithsonian
Astrophysical Observatory (SAO) contract SV3-73016 to MIT for Support of the
Chandra X-Ray Center (CXC) and Science Instruments. CXC is operated by SAO for
and on behalf of NASA under contract NAS8-03060. This research has made use of
ISIS functions (ISISscripts) provided by ECAP/Remeis observatory and MIT
(http://www.sternwarte.uni-erlangen.de/isis/).  CXO (HETG/ACIS)

## References

  * Anders & Grevesse (1989) Anders, E., & Grevesse, N. 1989, Geochim. Cosmochim. Acta, 53, 197
  * Belle et al. (2005) Belle, K. E., Howell, S. B., Mukai, K., et al. 2005, AJ, 129, 1985
  * Belle et al. (2002) Belle, K. E., Howell, S. B., Sirk, M. M., & Huber, M. E. 2002, ApJ, 577, 359
  * Bjorkman et al. (2002) Bjorkman, K. S., Miroshnichenko, A. S., McDavid, D., & Pogrosheva, T. M. 2002, ApJ, 573, 812
  * Böhringer & Werner (2010) Böhringer, H., & Werner, N. 2010, A&A Rev., 18, 127
  * Canizares et al. (2005) Canizares, C. R., Davis, J. E., Dewey, D., et al. 2005, PASP, 117, 1144
  * Davies (1990) Davies, S. R. 1990, MNRAS, 244, 93
  * Foster et al. (2012) Foster, A. R., Ji, L., Smith, R. K., & Brickhouse, N. S. 2012, ApJ, 756, 128
  * Fruscione et al. (2006) Fruscione, A., McDowell, J. C., Allen, G. E., et al. 2006, in Presented at the Society of Photo-Optical Instrumentation Engineers (SPIE) Conference, Vol. 6270, SPIE Conference Series
  * Gaia Collaboration et al. (2016) Gaia Collaboration, Prusti, T., de Bruijne, J. H. J., et al. 2016, A&A, 595, A1
  * Gaia Collaboration et al. (2018) Gaia Collaboration, Brown, A. G. A., Vallenari, A., et al. 2018, A&A, 616, A1
  * Gies et al. (2023) Gies, D. R., Wang, L., & Klement, R. 2023, ApJ, 942, L6
  * Gregory & Loredo (1992) Gregory, P. C., & Loredo, T. J. 1992, ApJ, 398, 146
  * Gudennavar et al. (2012) Gudennavar, S. B., Bubbly, S. G., Preethi, K., & Murthy, J. 2012, ApJS, 199, 8
  * Houck & Denicola (2000) Houck, J. C., & Denicola, L. A. 2000, in Astronomical Society of the Pacific Conference Series, Vol. 216, Astronomical Data Analysis Software and Systems IX, ed. N. Manset, C. Veillet, & D. Crabtree, 591
  * Hui et al. (2012) Hui, C. Y., Seo, K. A., Hu, C. P., Lin, L. C. C., & Chou, Y. 2012, ApJ, 759, 109
  * Jones et al. (2008) Jones, C. E., Sigut, T. A. A., & Porter, J. M. 2008, MNRAS, 386, 1922
  * Klement et al. (2024) Klement, R., Rivinius, T., Gies, D. R., et al. 2024, ApJ, 962, 70
  * Langer et al. (2020) Langer, N., Baade, D., Bodensteiner, J., et al. 2020, A&A, 633, A40
  * Lopes de Oliveira et al. (2006) Lopes de Oliveira, R., Motch, C., Haberl, F., Negueruela, I., & Janot-Pacheco, E. 2006, A&A, 454, 265
  * Luna et al. (2015) Luna, G. J. M., Raymond, J. C., Brickhouse, N. S., Mauche, C. W., & Suleimanov, V. 2015, A&A, 578, A15
  * Mukai (2017) Mukai, K. 2017, PASP, 129, 062001
  * Mushotzky & Szymkowiak (1988) Mushotzky, R. F., & Szymkowiak, A. E. 1988, in NATO Advanced Study Institute (ASI) Series C, Vol. 229, Cooling Flows in Clusters and Galaxies, ed. A. C. Fabian, 53
  * Nazé et al. (2020a) Nazé, Y., Motch, C., Rauw, G., et al. 2020a, MNRAS, 493, 2511
  * Nazé et al. (2020b) Nazé, Y., Pigulski, A., Rauw, G., & Smith, M. A. 2020b, MNRAS, 494, 958
  * Nazé et al. (2017) Nazé, Y., Rauw, G., & Cazorla, C. 2017, A&A, 602, L5
  * Nazé et al. (2020c) Nazé, Y., Rauw, G., & Pigulski, A. 2020c, MNRAS, 498, 3171
  * Nazé et al. (2019) Nazé, Y., Rauw, G., & Smith, M. 2019, A&A, 632, A23
  * Pandel et al. (2005) Pandel, D., Córdova, F. A., Mason, K. O., & Priedhorsky, W. C. 2005, ApJ, 626, 396
  * Postnov et al. (2017) Postnov, K., Oskinova, L., & Torrejón, J. M. 2017, MNRAS, 465, L119
  * Pradhan et al. (2023) Pradhan, P., Huenemoerder, D. P., Ignace, R., Nichols, J. S., & Pollock, A. M. T. 2023, ApJ, 954, 123
  * Scargle et al. (2006) Scargle, J. D., Norris, J., & Jackson, B. 2006, in Studies in Astronomical Time Series Analysis. VI
  * Scargle et al. (2013) Scargle, J. D., Norris, J. P., Jackson, B., & Chiang, J. 2013, ApJ, 764, 167
  * Tsujimoto et al. (2023) Tsujimoto, M., Hayashi, T., Morihana, K., & Moritani, Y. 2023, PASJ, 75, 177
  * Tsujimoto et al. (2018) Tsujimoto, M., Morihana, K., Hayashi, T., & Kitaguchi, T. 2018, PASJ, 70, 109
  * Warner (1983) Warner, B. 1983, in Astrophysics and Space Science Library, Vol. 101, IAU Colloq. 72: Cataclysmic Variables and Related Objects, ed. M. Livio & G. Shaviv, 155–171
  * Yuasa et al. (2010) Yuasa, T., Nakazawa, K., Makishima, K., et al. 2010, A&A, 520, A25


#  General-Purpose OCR Paragraph Identification by Graph Convolutional Neural
Networks

Renshen Wang, Yasuhisa Fujii and Ashok C. Popat R. Wang, Y. Fujii and A. C.
Popat are with Google Research, Mountain View, CA.Manuscript received January
29, 2021.

###### Abstract

Paragraphs are an important class of document entities. We propose a new
approach for paragraph identification by spatial graph convolutional neural
networks (GCN) applied on OCR text boxes. Two steps, namely line splitting and
line clustering, are performed to extract paragraphs from the lines in OCR
results. Each step uses a $\beta$-skeleton graph constructed from bounding
boxes, where the graph edges provide efficient support for graph convolution
operations. With only pure layout input features, the GCN model size is
3$\sim$4 orders of magnitude smaller compared to R-CNN based models, while
achieving comparable or better accuracies on PubLayNet and other datasets.
Furthermore, the GCN models show good generalization from synthetic training
data to real-world images, and good adaptivity for variable document styles.

###### Index Terms:

Optical character recognition, document layout, graph convolutional neural
network.

This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.

##  1 Introduction

Document image understanding is a task to recognize, structure, and understand
the contents of document images, and is a key technology to digitally process
and consume such document images. If we regard any images containing
structured text as document images, they are ubiquitous and can be found in
numerous applications. Document image understanding enables the conversion of
such documents into a digital format with rich structure and semantic
information and makes them available for subsequent information tasks.

A document can be represented by its semantic structure and physical structure
[1]. The task to recover the semantic structure is called logical layout
analysis [2] or semantic structure extraction [3] while the task to recover
the physical structure is called geometric (physical, or structural) layout
analysis [2]. These tasks are critical subproblems of document image
understanding.

A paragraph is a semantic unit of writing consisting of one or more sentences
that usually develops one main idea. Paragraphs are basic constituents of
semantic structure and thus paragraph boundary estimation (or paragraph
estimation, for short) is an important building block of logical layout
analysis. Moreover, paragraphs are often appropriate as processing units for
various downstream tasks such as translation and information extraction
because they are self-contained and have rich semantic information. Therefore,
developing a generic paragraph estimation algorithm is of great interest by
itself.

Figure 1: Examples of paragraphs in printed text. Paragraphs may have complex
shapes when wrapped around figures or other types of document entities.

Paragraphs are usually rendered in a geometric layout structure according to
broadly accepted typographical rules. For example, a paragraph can be rendered
as a series of text lines that

  * •

are placed with uniform vertical spacing between adjacent lines;

  * •

start with a line where one of the following is true:

    1. a.

The line is indented. (An indented paragraph.)

    2. b.

The line starts with a bullet symbol or number, with all the subsequent lines
indented to be left-justified, flush with the first. (A list item.)

    3. c.

The vertical spacing above the first line is significantly larger than the
uniform spacing between subsequent lines. (A block paragraph.)

As such, there are usually clear visual cues to identify paragraphs111A
semantic paragraph can span over multiple text columns or pages. In this
paper, we only look for physical paragraphs where lines of contiguous indices
are always physically proximate. Moreover, we regard stand-alone text spans
such as titles and headings as single-line paragraphs.. Nevertheless, the task
of estimating paragraphs often remains non-trivial as shown in Fig. 1.

Previous studies have attempted to develop a paragraph estimation method by
defining handcrafted rules based on careful observations [4, 5, 6, 7] or by
learning an object detection model to identify the regions of paragraphs from
an image [3, 8]. For the former approaches, it is usually challenging to
define a robust set of heuristics even for a limited domain, and hence
machine-learning-based solutions are generally preferable. The latter
approaches tend to have difficulty dealing with diverse aspect ratios and text
shapes, and the wide range of degradations observed in real-world applications
such as image skews and perspective distortions.

In this paper, we propose to apply graph convolutional neural networks (GCNs)
in a post-processing step of an optical character recognition (OCR) system for
paragraph estimation. Modern OCR engines can detect and recognize texts with a
very high recall for documents in a variety of conditions. Indeed, as will be
shown in the experiments, our generic OCR system can detect and recognize
texts with a higher recall than a specialized image-based paragraph detector,
indicating little risk of missing correct paragraph boundaries by restricting
to the possibilities generated by the OCR engine. That motivates us to employ
the post-processing strategy rather than a pre-processing or an entangled
approach. Recent advancements in graph neural (convolutional) networks [9, 10]
have enabled deep learning on non-Euclidian data. GCNs can learn spatial
relationships among entities combining information from multiple sources and
provide a natural way to learn the non-linear mapping from OCR results to
paragraphs.

More specifically, we design two classifiers based on GCNs — one for line
splitting and one for line clustering. A word graph is constructed for the
first stage and a line graph is constructed for the second stage. Both graphs
are constructed based on the $\beta$-skeleton algorithm [11] that produces a
graph with good connectivity and sparsity.

To fully utilize the models’ capability, it is desirable to have a diverse set
of document styles in the training data. We create synthetic data sets from
web pages where the page styles are randomly modified in the web scraping
engine. By leveraging open web sites like Wikipedia [12] for source material
to render in randomized styles, we have access to practically unlimited
document data.

We evaluate the 2-step models on both the PubLayNet [8] and our own datasets.
We show that GCN based models can be small and efficient by taking OCR
produced bounding boxes as input, and are also capable of generating highly
accurate results. Moreover, with synthesized training data from a browser-
based rendering engine, these models can be a step towards a reverse rendering
engine that recovers comprehensive layout structure from document images.

This paper is organized as follows: Section 2 reviews related work. Section 3
presents our proposed method, where the graph construction method and the
details of each step of the algorithms are described. Section 4 explains
training data generation methods with web scraping. Experimental setups and
results are given in Section 5. Section 6 concludes the paper with suggestions
for future work.

##  2 Related Work

OCR layout analysis (”layout” for short) comprises a large variety of problems
that have been studied from different aspects. There is pre-recognition layout
like [13] to find text lines as the input of recognition, and post-recognition
layout like [14] to find higher level entities based on OCR recognition
results. We list selected studies that are most relevant to our problem in the
following subsections.

###  2.1 Geometric and Rule-based Approaches

Multi-column text, often with small column gaps, needs to be first identified
before paragraphs. Early studies have proposed geometric methods [6, 15] and
rule-based methods [4, 5, 7]. Both categories have algorithms to find column
gaps by searching whitespace [15] or text alignment [7].

Limitations of these approaches include susceptibility to input noise and
false positive column boundaries, especially with monospace font families. Our
production222In current use in products and services at the time of this
writing. layout analyzer has been using a simpler rule-based heuristic
algorithm which splits lines at white spaces that are significantly larger
than others. This simplification gives it a performance (computational and
memory cost) advantage, but also hampers its capability of handling dense text
columns.

Figure 2: Example of multiple short paragraphs densely packed and rotated into
a non axis-aligned direction. The right side shows the region proposal boxes
for object detection models.

###  2.2 Image Based Detection

The PubLayNet paper [8] provides a large dataset for multiple types of
document entities, as well as two object detection models F-RCNN [16] and
M-RCNN [17] trained to detect these entities. Both show good metrics in
evaluations, but also with some disadvantages on detecting paragraphs:

  * •

Cost: Object detection models are typically large in size and expensive in
computation. When used together with an OCR engine to retrieve text
paragraphs, it seems wasteful to bypass the OCR results and attempt to detect
paragraphs independently.

  * •

Quality: Paragraph bounding boxes may have high aspect ratios and are
sometimes tightly packed, making it difficult for Faster R-CNN detection. In
Fig. 2, several short paragraphs are printed with dense text and rotated by 45
degrees. The region proposals required to detect all the paragraphs are highly
overlapped, so some detections will be dropped by non-maximum suppression
(NMS). Rotational R-CNN models [18] can mitigate this issue by inclined NMS,
but further increase the computational cost while still facing a more
difficult task with rotated or warped inputs.

###  2.3 Page Segmentation

Page segmentation models [3, 19, 20] classify every part of the image to
certain types of objects such as text, table, image and background. Sometimes
the shapes of paragraphs can be revealed by the “text” part of the
segmentation. However, when text is dense and paragraphs are indentation based
without variation in line spacings, individual paragraphs cannot be easily
extracted from large connected text regions. On the other hand, when text is
sparse and appears as a lot of separate small components, paragraphs are not
obvious in the segmentation result either.

###  2.4 Graph Neural Network for Table Detection

A graph neural network approach is proposed in [14] to detect tables in
invoice documents. It shows that tabular structures can be detected based
purely on structural information by graph neural networks.

Limitations of this approach include graph construction and graph
representation. First, the visibility graph is built by only connecting pairs
of pre-defined entities that are vertically or horizontally visible, which
requires the input image free of skews and distortions. Second, the adjacency
matrix learned by the GNN is $O(n^{2})$ in size and hence inefficient for
large inputs. A general-purpose post-OCR model will need to overcome these
limitations to accommodate all types of input images and achieve high
computational efficiency.

##  3 Paragraph Estimation with Graph Convolutional Neural Networks

A paragraph consists of a set of text lines, which are usually produced in the
output of OCR systems [21, 13]. If text lines are given by OCR systems, we can
consider a bottom-up approach to cluster text lines into paragraphs for the
paragraph estimation task.

The detected lines provide rudimentary layout information but may not match
the true text lines. For example, in Fig. 3, the lower section of the page
consists of two text columns placed closely to each other. The line detector
might be confused by the tiny spacing and find wrong lines spanning both
columns. These lines need to be split in the middle before being clustered
into paragraphs.

Line splitting and clustering are non-trivial tasks for general-purpose
paragraph estimation – the input images can be skewed or warped, and the
layout styles can vary among different types of documents, e.g. newspapers,
books, signs, web pages, handwritten letters, etc. Even though the concept of
paragraph is mostly consistent across all document categories, the appearance
of a paragraph can differ by many factors such as word spacing, line spacing,
indentation, text flowing around figures, etc. Such variations make it
difficult, if not impossible, to have a straightforward algorithm that
identifies all the paragraphs.

In order to address erroneous line detection and solve the non-trivial split
and clustering problem, we design a paragraph identification method as a
2-step process after the main OCR engine produces line and word bounding
boxes. Both steps use a graph convolutional neural network (GCN) that takes
input features from bounding boxes in the OCR result, together with a
$\beta$-skeleton graph [11] constructed from these boxes. Neither the original
image nor text transcriptions are included in the input, so the models are
small, fast, and entirely focused on the layout structure.

  * •

Step 1: Line splitting. Raw text lines from OCR line detectors may cross
multiple columns, and thus need to be split into shorter lines. A GCN node
classifier predicts splitting points in lines.

  * •

Step 2: Line clustering. After step 1 produces refined lines, they are
clustered into paragraphs. A GCN edge classifier predicts clustering
operations on pairs of neighboring lines.

The following subsections describe these steps in details. In addition, we
discuss the possibility of an alternative one-step process.

Figure 3: Example of a double-column document image and its paragraphs. The
left side shows all the lines found by an OCR text line detector, and the
right side shows the paragraphs formed by clustered text lines within each
column. Figure 4: Comparison among different types of graphs constructed on an
example set of boxes.

###  3.1 $\bm{\beta}$-skeleton on Boxes

A graph is a key part of the GCN model input. We want a graph with high
connectivity for effective message passing in graph convolutions, while also
being sparse for computational efficiency.

Visibility graphs have been used in previous studies [22, 14], where edges are
made by “lines-of-sight”. They are not considered suitable for our models
because the lines may create excessive edges. Fig. 4(a) shows the visibility
graph built on two rows of boxes, where any pairs of boxes on different rows
are connected. This means word connections between text lines may get
$O(n^{2})$ number of edges. If we limit the lines-of-sight to be axis aligned
like Fig. 4(b), then the graph becomes too sparse, even producing disconnected
components in some cases.

By changing “lines-of-sight” into “balls-of-sight”, we get a $\beta$-skeleton
graph [11] with $\beta=1$. In such a graph, two boxes are connected if they
can both touch a circle that does not intersect with any other boxes. It
provides a good balance between connectivity and sparsity. As shown in Fig.
4(c), a $\beta$-skeleton graph does not have too many connections between rows
of boxes. With $\beta=1$, it is a subgraph of a Delaunay triangulation [23]
with number of edges bounded by $O(n)$. Yet, it provides good connectivity
within any local cluster of boxes, and the whole graph is guaranteed to be one
connected component.

Figure 5: Building a $\beta$-skeleton on boxes from $\beta$-skeleton on
points. Left side: intersecting boxes are first connected with edges of length
0. Right side: Non-internal peripheral points are connected with
$\beta$-skeleton edges which are then collapsed into box edges. Edge lengths
are approximate.

The original $\beta$-skeleton graph is constructed on a point set. To apply it
to bounding boxes, we use an algorithm illustrated in Fig. 5 and described in
the following steps, where $n$ used for complexity analysis is the number of
boxes. We assume the length and width of all the input boxes are bounded by a
constant.

  1. 1\.

For each box, pick a set of peripheral points at a pre-set density, and pick a
set of internal points along the longitudinal middle line333The middle line
points are added so that no edges can go through the boxes..

  2. 2\.

Build a Delaunay triangulation graph $G_{D}$ on all the points. (Time
complexity $O(n\log n)$ [23].)

  3. 3\.

Find all the “internal” points that are inside at least one of the boxes.
(Time complexity $O(n)$ by traversing along $G_{D}$’s edges inside each box
starting from any peripheral point. Internal points are marked grey in Fig.
5.)

  4. 4\.

Add an edge of length 0 for each pair of intersecting boxes (containing each
other’s peripheral points).

  5. 5\.

Pick $\beta$-skeleton edges from $G_{D}$ where for each edge
$e=(v_{1},v_{2})$, both its vertices $v_{1}$, $v_{2}$ are non-internal points
and the circle with $v_{1}v_{2}$ as diameter does not cover any other point.

If there is such a point set $V_{c}$ covered by the circle, then the point
$v_{3}\in V_{c}$ closest to $\overline{v_{1}v_{2}}$ must be the neighbor of
either $v_{1}$ or $v_{2}$ (in Delaunay triangulation graphs). Finding such
$v_{3}$ takes $O(\log n)$ time for each edge, since $G_{D}$ produced in step 2
have edges sorted at each point.

  6. 6\.

Keep only the shortest edge for each pair of boxes as the $\beta$-skeleton
edge.

The overall time complexity of this box based $\beta$-skeleton graph
construction is $O(n\log n)$, dominated by Delaunay triangulation. There are
pathological cases where step 4 will need $O(n^{2})$ time, e.g. all the $n$
boxes contain a common overlapping point. But these cases are easily excluded
from OCR results. The total number of edges is bounded by $O(n)$ as in
$G_{D}$, so the graph convolution layers have linear time operations.

Figure 6: Overview of the line splitting model. In the output, line start
nodes are marked green and line end nodes are marked orange. Figure 7:
Overview of the line clustering model. In the output, positive edges are
marked pink.

###  3.2 Message Passing on Graphs

We use spatial-based graph convolutional neural networks (GCNs) [10, 24] for
both tasks of line splitting and line clustering, since both can leverage the
local spatial feature aggregation and combinations across graph edges (more
details in subsections 3.3 and 3.4 below).

Our graph convolutional neural network resembles the message passing neural
network (MPNN) [25] and GraphSage [26]. We use the term “message passing
phase” from [25] to describe the graph level operations in our models. In this
phase, repeated steps of “message passing” are performed based on a message
function $M$ and node update function $U$. At step $t$, a message
$M(h_{v}^{t},h_{w}^{t})$ is passed along every edge $e_{vw}$ in the graph
where $h_{v}^{t}$ and $h_{w}^{t}$ are the hidden states of node $v$ and $w$.
Let $N(v)$ denote the neighbors of node $v$ in the graph, the aggregated
message by average pooling received by $v$ is

$m_{v}^{t+1}=\frac{\sum_{w\in N(v)}M(h_{v}^{t},h_{w}^{t})}{|N(v)|}$ (1)

and the updated hidden state is

$h_{v}^{t+1}=U(h_{v}^{t},m_{v}^{t+1})$ (2)

Alternatively, we can use attention weighted pooling [27] to enhance message
aggregation. Consequently, the model is also called a graph attention network
(GAT), where calculation of $m_{v}^{t+1}$ is replaced by

$m_{v}^{t+1}=\frac{\sum_{w\in
N(v)}\exp(e_{vw}^{t})M(h_{v}^{t},h_{w}^{t})}{\sum_{w\in
N(v)}\exp(e_{vw}^{t})}$ (3)

and $e_{vw}^{t}$ is computed from a shared attention mechanism

$e_{vw}^{t}=a(h_{v}^{t},h_{w}^{t})$ (4)

For $a$, we use the self-attention mechanism introduced in [28].

In our GCN models, the message passing steps are applied on the
$\beta$-skeleton graph constructed on OCR bounding boxes, so that structural
information can be passed around local vicinities along graph edges, and
potentially be combined and extracted into useful signals. Both the line
splitting step and the line clustering step rely on this mechanism to make
predictions on graph nodes or edges.

###  3.3 Splitting Lines

As in [6, 7], if multi-column text blocks are present in a document page,
splitting lines across columns is a necessary first step for finding
paragraphs. Here we have the same objective but a different input with
available OCR bounding boxes for each word and symbol. Image processing can be
skipped to accelerate computations.

Note that the horizontal spacings between words is not a reliable signal for
this task, as when the typography alignment of the text is “justified,” i.e.
the text falls flush with both sides, these word spacings may be stretched to
fill the full column width. In Fig. 3, the bottom left line has word spacings
larger than the column gap. This is common in documents with tightly packed
text such as newspapers.

We use the GCN model shown in Fig. 6 to predict the splitting points, or tab-
stops. Each graph node is a word bounding box. Graph edges are the
$\beta$-skeleton edges built as described in section 3.1. The model output
contains two sets of node classification results – whether each word is a
“line start” and whether it is a “line end”. This model is expected to work
well for difficult cases like dense text columns with “justified” alignment by
aggregating signals from words in multiple lines surrounding the potential
splitting point.

Fig. 8 shows a zoomed-in area of Fig. 3 with a $\beta$-skeleton graph
constructed from the word bounding boxes. Since words are aligned on either
side of the two text columns, a set of words with their left edges all aligned
are likely on the left side of a column, i.e. these words are line starts.
Similarly, a set of words with right edges all aligned are likely on the right
side and are line ends. The $\beta$-skeleton edges are guaranteed to connect
aligned words in neighboring lines, since aligned words have the shortest
distance between the two lines and there is nothing in between to block the
connection. Thus, the alignment signal can be passed around in the message
passing steps and be effectively learned by the GCN model. Moreover, the two
sets of words beside the column gap are also connected with $\beta$-skeleton
edges crossing the two columns, so the signals can be mutually strengthened.

Figure 8: Line splitting signal from word box alignment propagating through
$\beta$-skeleton edges. The resulting predictions are equivalent to tab-stop
detection. Figure 9: Example of paragraph line clustering by indentations.
Light blue edges indicate the $\beta$-skeleton constructed on line bounding
boxes, and pink edges indicate that the connected lines are clustered into
paragraphs.

###  3.4 Clustering Lines

After splitting all the lines into “true” lines, the remaining task is to
cluster them into paragraphs. Again we use a graph convolutional neural
network, but now each graph node is a line bounding box, and the output is
edge classification similar to link prediction in [29, 30]. We define a
positive edge to be one that connects two consecutive lines in the same
paragraph. Note that it is possible to have non-consecutive lines in the same
paragraph being connected by a $\beta$-skeleton edge. Such edges are defined
as negative to make the task easier to learn.

Fig. 7 is an overview of the line clustering model. It looks similar to the
line splitting model in Fig. 6, except the input consists of line bounding
boxes, and the output predictions are on graph edges instead of nodes. An
additional “node-to-edge” step is necessary to enable edge classification with
node-level output from the graph convolution steps. It works in a similar way
as the first half of a graph convolution step, with node aggregation replaced
by edge aggregation:

$m^{\prime}_{e=(v,w)}=\frac{M^{\prime}(h_{v},h_{w})+M^{\prime}(h_{w},h_{v})}{2}$
(5)

The model predicts whether two lines belong to the same paragraph on each pair
of lines connected with a $\beta$-skeleton edge. The predictions are made from
multiple types of context.

  * •

Indentation: For example, in Fig. 9 which is zoomed-in from Fig. 3, each new
paragraph starts with an indented line, so the edge connecting the fourth and
fifth lines in the left column is predicted as non-clustering.

  * •

Vertical spacing: “Block paragraphs” are separated by extra vertical spacing,
which are common in web pages. Line spacing signals are passed around in graph
convolutions to detect vertical space variations.

  * •

List items: The first line of a list item is usually outdented with a bullet
point or a number, and the first word after is flush with the following lines.
So list items can be detected in a similar way as indentation based
paragraphs.

Besides the three common types listed above, we may have other forms of
paragraphs such as mailing addresses, computer source code or other customized
structures. The model can be trained on different types of layout data.

###  3.5 Possibility of Clustering Words

If a 1-step model can cluster the words directly into paragraphs, it will be
preferable to the 2-step GCN models described above. A single model is not
only faster to train and run, but can also avoid cascading errors where the
first step’s mistake propagates to the second.

However, there is significant difficulty for a 1-step GCN model to work on the
paragraph word clustering problem. First, word based GCN models may not have
good signal aggregation for line level features because of the limited number
of graph convolution layers. The oversmoothing effect [31, 32] limits the
depth of the network, i.e. the number of “message passes”. With
$\beta$-skeleton graphs mostly consisting of local connections, the “receptive
field” on each graph node is small and often cannot cover a whole line. For
instance, a word at the end of a line has no information on whether this line
is indented. In a general purpose paragraph model where the input can be noisy
and deformed, this limitation can severely affect model performance.

While it is possible to extend the receptive fields by adding non-local edges
in the graph, or employing residual connections and dilated convolutions [32]
in the model, it is non-trivial to build a scalable and effective solution.
This is an interesting topic for further research, but not the focus of this
paper.

##  4 Synthetic Training Data from Web

A large set of diverse and high quality annotated data is a necessity for
training deep neural networks. Such datasets are not readily available for
paragraphs and layout-related tasks. The PubLayNet dataset [8] is a very large
annotated set, but lacks in style diversity as all the pages are from
publications.

Therefore, we largely rely on automated training data generation [33]. By
taking advantage of high quality and publicly available web documents, as well
as a powerful rendering engine used in modern browsers, we can generate
synthetic training data with a web scraper.

Figure 10: Training data examples from web scraping with randomized style
changes and data augmentation. Green boxes indicate line ground truth labels
and yellow boxes indicate multi-line paragraph ground truth labels. (Yellow
paragraph boxes are for visualization purpose only. Paragraph ground truth
labels are represented by sets of line numbers in order to prevent ambiguity
when there are overlaps between paragraph bounding boxes.)

###  4.1 Scraping Web Pages with Modified Styles

Web pages are a good source of document examples. Wikipedia [12] is well known
to host a great number of high quality articles with free access.

We use a browser-based web scraper to retrieve a list of Wikipedia pages,
where each result includes the image rendered in the browser as well as the
HTML DOM (document object model) tree of that page. The DOM tree contains the
complete document structure and detailed locations of all the rendered
elements, from which we can reconstruct the ground truth line bounding boxes.
Each line bounding box is an axis-aligned rectangle covering a line of text.
For paragraph ground truth, the HTML tag $<$p$>$ conveniently indicates a
paragraph node, and all the text lines under this node belong to the same
paragraph.

TABLE I: Sample web script code for changing paragraph styles. Random combinations of these changes are used in training data synthesis. Style Change | Script Sample
---|---
Single-column to | div.style.columnCount = 2;
double-column |
Vertical spacing to | div.style.textIndent = 30px;
indentation | div.style.marginTop = 0;
| div.style.marginBottom = 0;
Typography alignment | div.style.textAlign = “right”;
Text column width | div.style.width = 50%;
Horizontal text block | div.style.marginLeft = 20%;
position |
Line height/spacing | div.style.lineHeight = 150%;
Font | div.style.fontFamily = “times”;

One issue of using web page data directly for document layout is the lack of
diversity in document styles. Almost all web pages use vertical spacing to
separate paragraphs, and multi-column text is rare. Fortunately, modern web
browsers support extensions that can run script code on web pages to change
their CSS styles. For example, to generate double-column text for a certain
division of a page, we can use “div.style.columnCount = 2.”

Table I lists a few examples of web script code for changing paragraph styles.
Such pieces are randomly picked and combined in our training data pipeline.
Parameters such as column count and alignment type are also randomized. Thus,
the total combinations give a great diversity of styles to simulate various
types of documents to be encountered in the real world.

###  4.2 Data Augmentation

A general-purpose OCR engine must accommodate all types of input images,
including photos of text taken at different camera angles. Our model should be
able to handle the same variations in input, so data augmentation is needed to
transform the rectilinear data scraped from web pages into photo-like data.

To emulate the effect of camera angles on a page, we need two types of
geometric transformation: rotation and perspective projection. Again, we use
randomized parameters in each transformation to diversify our data. Each data
point gets a random projection followed by a random rotation, applied to both
the image and ground truth boxes. Fig. 10 shows two training examples with
data augmentation.

  * •

The left one has Arial font, dense text lines, paragraphs separated by
indentation and the camera placed near the upper-left corner.

  * •

The right one has Monospace font, sparse text lines, paragraphs separated by
vertical spacing and the camera placed near the lower-right corner.

Note that we do not need pixel-level augmentation (imaging noise, illumination
variation, compression artifacts, etc.) for the training of our GCN models,
because these models only take bounding box features from the OCR engine
output, and are decoupled from the input image. Even when real input images
look very different from the training data images, the bounding boxes from a
robust OCR engine can still be consistent. It is assumed that the OCR engine
has been trained to be robust to pixel-level degradation, as is the case in
the present work.

###  4.3 Sequential 2-Step Training by Web Synthetic Data

We train the two GCN models in sequence, where the line clustering input
depends on the line splitting model. For each model, the classification ground
truth labels are computed from matching OCR output to the shapes of ground
truth (GT) lines. The GT lines are denoted by ${L_{1},L_{2},...,L_{n}}$. Each
GT line is a rectangle from the web rendering engine, and is transformed into
a quadrilateral in data augmentation.

In the line splitting model, the graph nodes are the OCR word boxes, and the
output labels are node classifications on whether each node is a “line start”
and whether it is a “line end”. These labels can be computed by the following
two steps.

  * •

For each OCR word $w_{i}$, the word is allocated to the ground truth line with
maximum intersection area with the word bounding box.

  * •

For each GT line $L_{j}$, sort the words allocated to this line along its
longitudinal axis. The word at the left end is a line start, the word at the
right end is a line end, and the remaining words are negative on both.

In the line clustering model, the graph nodes are the line boxes after the
line splitting process, and the output labels are edge classifications on
whether an edge connects two lines that are adjacent lines in the same
paragraph. For each $\beta$-skeleton edge that connects a pair of OCR line
boxes ($l_{i}$, $l_{j}$), we find the corresponding pair of GT line boxes
($L_{i^{\prime}}$, $L_{j^{\prime}}$) by the same maximum intersection area as
the step above. The edge label is positive if $L_{i^{\prime}}$ and
$L_{j^{\prime}}$ belong to the same paragraph and
$\left|i^{\prime}-j^{\prime}\right|=1.$
444$\left|i^{\prime}-j^{\prime}\right|=1$ means no skip-line positive edges,
which makes the task easier to learn. For datasets without line level ground
truth labels, this condition is replaced by “there is no path in the
$\beta$-skeleton graph shorter than edge ($l_{i}$, $l_{j}$)”.

The line clustering model input is generated from line splitting on the OCR
results. While there remains some risk of cascading of errors, line clustering
is able to correct some mistakes in the previous line splitting step.
Specifically,

  * •

For “under-splitting”, i.e. when an OCR line covers multiple GT lines, there
is no way to correct it by clustering, and the training example is discarded.

  * •

For “over-splitting”, i.e. when multiple OCR lines match the same GT line, the
line clustering model can cluster the over-split short lines into the same
paragraph and recover the original lines. See the second picture in Fig. 15 as
an example. The sequential training steps enable this error correction.

It is worth noting that the ground truth labels associated with table elements
are treated as “don’t-care” and assigned with weight 0 in training. The reason
is that tables have very different structures from paragraphed text, and the
two types of entities often produce contradicting labels within the current
GCN framework. Using GCN for table detection like [14] is another interesting
topic but out of the scope of this paper.

##  5 Experiments

We experiment with the 2-step GCN models and evaluate the end-to-end
performance on both the open PubLayNet dataset and our own annotated sets.

In the end-to-end flow, the line splitting model and the line clustering model
work in a sequential order. It takes an OCR result page as input, and produces
a set of paragraphs each containing a set of lines, and every line in the page
belongs to exactly one paragraph.

###  5.1 Setups

We use the OCR engine behind Google Cloud Vision API DOCUMENT_TEXT_DETECTION
555https:$\mathbin{/\mkern-6.0mu/}$cloud.google.com/vision/docs/fulltext-
annotations version 2020 for all the pre-layout detection and recognition
tasks. Setup details are elaborated as follows.

####  5.1.1 Data

We use 3 datasets in our evaluations: PubLayNet from [8], the web synthetic
set as described in section 4, and a human annoatated set with real-world
images.

  * •

PubLayNet contains a large amount of document images with ground truth
annotations: 340K in the training set and 12K in the development/validation
set. The testing set ground truth has not been released at the time of this
writing, so here we use the development set for testing.

  * •

For web synthetic, we scrape 100K Wikipedia [12] pages in English for image
based model training and testing at a 90/10 split. For GCN models, 10K pages
are enough. An additional 10K pages in Chinese, Japanese and Korean are
scraped to train the omni-script GCN models.

  * •

We also use a human annotated set with real-world images – 25K in English for
training and a few hundred for testing in each available language. The images
are collected from books, documents or objects with printed text, and then
sent to a team of raters who draw the ground truth polygons for all the
paragraphs. Example images are shown in Fig. 14, 15 and 16.

####  5.1.2 Models and Hyperparameters

The GCN models are built as in Fig. 6 and Fig. 7, each carrying 8 steps of
graph convolutions with 4-head self-attention weighted pooling [27, 28].

At the models’ input, each graph node’s feature is a vector containing its
bounding box information of the word or the line. The first five values are
width $w$, height $h$, rotation angle $\alpha$, $\cos\alpha$ and $\sin\alpha$.
Then for each of its 4 corners $(x_{p},y_{p})$, we add 6 values $[x_{p},$
$x_{p}\cos\alpha,$ $x_{p}\sin\alpha,$ $y_{p},$ $y_{p}\cos\alpha,$
$y_{p}\sin\alpha]$. For line clustering, an additional $w_{1}$ indicating the
first word’s width is added to each line for better context of line breaks and
list items. These values provide the starting point for feature crossings and
combinations in graph convolutions. This low dimension of model input enables
lightweight and efficient computation.

Model inference latency is very low, under 20 milliseconds for an input graph
of around 1500 nodes (on a 12-core 3.7GHz Xeon CPU), since each GCN model is
less than 130KB in size with 32-bit floating point parameters. In fact, the
computation bottleneck is on the $\beta$-skeleton construction which can take
$\sim$50 milliseconds for the same graph. Compared to the main OCR process,
the overall GCN latency is small, and the $O(n\log n)$ complexity ensures
scalability.

We cannot claim that GCN models have better latency than image based R-CNN
models, because image models can run in parallel with the OCR engine when
resources allow. Instead, the small size of GCN models makes them easy to be
deployed as a lightweight, low cost and energy efficient step of post-OCR
layout analysis.

####  5.1.3 Evaluation Metrics

While classification tasks are evaluated by precision and recall, the end-to-
end performance is measured by IoU based metrics such as the COCO
mAP@IoU[.50:.95] used in [8] so the results are comparable.

The average precision (AP) for mAP is usually calculated on a precision-recall
curve. Since our models produce binary predictions instead of detection boxes,
we have only one output set of paragraph bounding boxes, i.e. only one point
on the precision-recall curve. So $AP=precision\times recall$.

We introduce another metric F1var using variable IoU thresholds, which is more
suitable for paragraph evaluations. In Fig. 11, a single-line paragraph has a
lower IoU even though it is correctly detected, while a 4-line detection (in
red) has a higher IoU with a missed line. This is caused by boundary errors at
character scale rather than at paragraph scale. This error is larger for post-
OCR methods since the OCR engine is not trained to fit paragraph boxes. If we
have line-level ground truth in each paragraph, and adjust IoU thresholds
$T_{iou}$ by

$T_{iou}=\min(1-\frac{1}{1+\\#lines},0.95)$ (6)

the single-line paragraph will have IoU threshold 0.5, the 5-line one will
have IoU threshold 0.833, and both cases in Fig. 11 can be more reasonably
scored.

Figure 11: Paragraph detection example from PubLayNet [8]. Red boxes are
different from ground truth in terms of enclosed words. A single-line correct
detection has lower IoU than a multi-line detection missing a line,
necessitating variable IoU thresholds in evaluations.

Both PubLayNet [8] and our web synthetic set have line level ground truth to
support this metric. For the human annotated set without line annotations, we
fall back to a fixed IoU threshold of 0.5.

####  5.1.4 Baselines

The 2-step GCN models are compared against image based models and the
heuristic algorithm in our production system.

The image models include Faster R-CNN and Mask R-CNN used in [8], which work
on the PubLayNet data with non-augmented images. For broader testing on
augmented datasets, we train a Faster R-CNN model with an additional
quadrilateral output to indicate rotated boxes, denoted by “F-RCNN-Q” in
following subsections. This model uses a ResNet-101 [34] backbone and is
$\sim$200MB in size, smaller than the two models in [8] but still 3 orders of
magnitude larger than the GCN models.

For reference, the baseline heuristic algorithm takes the OCR recognized text
lines as input and generates paragraphs by the following steps.

  1. 1\.

Within each line, find white spaces between words that are significantly wider
than average, and split the line by these spaces into shorter lines.

  2. 2\.

For each line, repeatedly cluster nearby lines into its block by a distance
threshold, until no more proximate lines can be found.

  3. 3\.

Within each block, merge lines that are roughly placed in the same straight
line.

  4. 4\.

Within each block, for each indented line, create a new paragraph.

These rule-based steps were intended to handle multi-column text pages, but
the fixed hand-tuned parameters make it inflexible at style variations.
Replacing them with machine learned GCN models as proposed here can greatly
enhance the algorithm’s performance and adaptivity.

###  5.2 GCN Classification Accuracies

We first check the metrics of the GCN classification tasks on various training
sets. Precision and recall scores of the binary classification tasks are shown
in Table II. The PubLayNet data is not applied with data augmentation because
of the low resolution of its images, while the web synthetic data is tried
with and without data augmentation.

The human annotated training set is added to train the line clustering GCN
model, but not the line splitting model because it lacks dense, multi-column
text pages. Therefore, only the line clustering scores are shown for the
combined set in Table II. The scores on the annotated set are significantly
lower because of the diverse and noisy nature of the data source.

We also compare the $\beta$-skeleton graph with the two types of “line-of-
sight” graphs in Fig. 4. Since the edges are very different among these
graphs, Table III only compares node classification scores trained on the
augmented web synthetic set. When average pooling is used in graph
convolutions, the free “line-of-sight” graph in Fig. 4(a) achieves the best
scores. However, the $O(n^{2})$ size of the graph scales poorly and causes
out-of-memory errors when training with attention weighted pooling within our
environment. In practical use, $\beta$-skeleton graph appears to yield the
best results for our purpose.

###  5.3 PubLayNet Evaluations

The PubLayNet dataset has five types of layout elements: text, title, list,
figure and table. For our task, we take text and title bounding boxes as
paragraph ground truth, and set all other types as “don’t-care” for both
training and testing.

TABLE II: Precision/recall pairs of the two GCN models’ classification tasks during training with different datasets. The $\beta$-skeleton graph is used for all tasks. Dataset | Line start | Line end | Edge clustering
---|---|---|---
PubLayNet | 0.998/0.992 | 0.992/0.990 | 0.994/0.997
Web synthetic | 0.995/0.996 | 0.994/0.997 | 0.978/0.980
Augmented web | 0.988/0.986 | 0.990/0.987 | 0.958/0.966
synthetic |  |  |
Combined set | Augmented web synthetic | 0.949/0.953
| Human annotated | 0.901/0.912
TABLE III: Precision/recall pairs of the line splitting model using different types of graphs on the augmented web synthetic set. Both average pooling and attention weighted pooling are tested for message aggregation in graph convolutions.  Graph type | Pooling method | Line start | Line end
---|---|---|---
$\beta$-skeleton | Average | 0.982/0.978 | 0.981/0.978
| Attention | 0.988/0.986 | 0.990/0.987
Line-of-sight | Average | 0.983/0.985 | 0.984/0.988
| Attention | -/- | -/-
Axis-aligned | Average | 0.972/0.974 | 0.970/0.971
line-of-sight | Attention | 0.973/0.973 | 0.964/0.978

(a) (b) (c) (d)

Figure 12: Representative PubLayNet examples of paragraphs by OCR followed by
GCN line splitting and line clustering.

(a) (b) (c) (d)

Figure 13: Paragraph errors in PubLayNet examples caused by various types of
failures including OCR detection, line splitting and line clustering. (a)
Under splitting. (b) Over splitting. (c) Clustering errors for normal text and
math equations. (d) Clustering error across table boundary line.

Table IV shows that F-RCNN-Q matches the mAP scores in [8]. The GCN models are
worse in this metric because there is only one point in the precision-recall
curve, and the OCR engine is not trained to produce bounding boxes that match
the ground truth. In the bottom row of Table IV, “OCR + Ground Truth” is
computed by clustering OCR words into paragraphs based on ground truth boxes,
which is the upper bound for all post-OCR methods. For mAP scores, even the
upper bound is lower than the scores of image based models. However, if we
measure by F1var scores defined in subsection 5.1.3, OCR + GCNs can match
image based models with a slight advantage.

TABLE IV: Paragraph mAP@IoU[.50:.95] score and F1var comparison on the PubLayNet development set. Numbers in the first 2 rows are from [8]. Model | Training Set | mAP | F1var
---|---|---|---
F-RCNN [8] | PubLayNet training | 0.910 | -
M-RCNN [8] | PubLayNet training | 0.916 | -
F-RCNN-Q | PubLayNet training | 0.914 | 0.945
Tesseract [13] | - | 0.571 | 0.707
OCR + Heuristic | - | 0.302 | 0.364
OCR + GCNs | Augmented web synthetic | 0.748 | 0.867
OCR + GCNs | PubLayNet training | 0.842 | 0.959
OCR + Ground Truth - | 0.892 | 0.997

The high F1var score on “OCR + Ground Truth” also shows that the OCR engine we
use has a very high recall on text detection. The reason it is lower than 1 is
mostly from ground truth variations – a small fraction of single-line
paragraphs have IoU lower than 0.5.

Fig. 12 shows some GCN produced examples where all the paragraphs are
correctly identified. Errors made by the GCN models (or the OCR engine) are
shown in Fig. 13 with four examples:

  1. a.

Under splitting – the top line (marked red) should have been split into two.
This usually causes large IoU drop and cannot be recovered by line clustering.

  2. b.

Over splitting.

  3. c.

Clustering errors among text lines, and also on a math equation together with
detection errors.

  4. d.

A table annotation is clustered with a table cell across a boundary line,
because our models do not take image features and ignore non-text lines.

###  5.4 Synthetic Dataset Evaluations

The synthetic dataset from web scraping can give a more difficult test for
these models by its aggressive style variations.

(a) (b) (c)

Figure 14: Representative examples of real-world images with OCR followed by
GCN line splitting and line clustering. Blue boxes: words; green boxes: lines;
yellow boxes: paragraphs; pink line segments: positive line clustering
predictions.

(a) (b) (c)

Figure 15: Paragraph errors in real-word images. (a) Under splitting. (b) Over
splitting. (c) Over clustering table elements.

In Table V, we can see the F1var score of the image based F-RCNN-Q model
decreases sharply as the task difficulty increases. At the synthetic dataset
where the images are augmented with rotations and projections as in Fig. 10,
detection is essentially broken, not only from non-max suppression drops shown
in Fig. 2, but also from much worse box predictions.

TABLE V: Paragraph F1var score comparison across different types of models and datasets. Model | Training/Testing Set | F1var
---|---|---
F-RCNN-Q | PubLayNet training/dev | 0.945
| Web synthetic | 0.722
| Augmented web synthetic | 0.547
OCR + GCNs | PubLayNet training/dev | 0.959
| Web synthetic | 0.830
| Augmented web synthetic | 0.827

In contrast, the GCN models are much less affected by data augmentations and
layout style variations. Especially between augmented and non-augmented
datasets, the F1var score change is minimal. So GCN models will have greater
advantage when input images are non axis-aligned.

###  5.5 Real-World Dataset Evaluations

The human annotated dataset can potentially show the models’ performance in
real-world applications. Since the annotated set is relatively small, the
F-RCNN-Q model needs to be pre-trained on other paragraph sets, while the GCN
models are small enough that the line clustering model can be trained entirely
on the paragraph annotations. Evaluation metric for this set is F1-score with
a fixed IoU threshold of 0.5.

TABLE VI: Paragraph F1-scores tested on the real-world test set with paragraph annotations. Fixed IoU threshold 0.5 is used since there is no line-level ground truth to support variable thresholds. Model | Training Data |<EMAIL_ADDRESS>
---|---|---
F-RCNN-Q | Augmented web synthetic | 0.030
| Annotated data (pre-trained | 0.607
| on PubLayNet) |
OCR + Heuristic | - | 0.602
OCR + GCNs | Augmented web synthetic | 0.614
| Annotated data | 0.671
| Combined set | 0.671
OCR + Ground Truth | - | 0.960

Table VI shows comparisons across different models and different training
sets. All the models should handle image rotations and perspective
transformations, so we only compare models trained on the augmented web
synthetic set or the human annotated set. First, we can see that Faster R-CNN
trained from synthetic web rendered pages does not work at all for real-world
images, whereas the GCN models can generalize well from synthetic training
data.

Also note that most of the annotated images are nearly axis-aligned, so the
GCN models will yield even greater advantage if the images are rotated or
taken with varied camera angles.

Fig. 14 and Fig. 15 show six examples of OCR + GCNs produced paragraphs. The
successful examples in Fig. 14 are all difficult cases for heuristic and
detection based approaches but are handled well by the GCN models. The image
on the right shows the effectiveness of training with augmented web synthetic
data, as there are no similar images in the annotated set. Error examples
produced by GCN are shown in Fig. 15:

  1. a.

Under splitting: the caption under the top-right picture is not split from the
paragraph on the left, causing downstream errors.

  2. b.

Over splitting: two lines in the middle are mistakenly split, but the short
line segments are then clustered back into the same paragraph, resulting in a
correct final output.

  3. c.

Over clustering table elements: since tables are “don’t-care” regions in the
training data, the GCN models trained with paragraph data may take table
elements as sparse text lines and incorrectly cluster them together. A table
detector may help to filter out these lines for paragraphs.

To verify the robustness of the GCN models for language and script diversity,
we test them on a multi-language evaluation set. The models are trained with
both synthetic and human annotated data in English, and additional synthetic
data from Wikipedia pages in Chinese, Japanese and Korean. No other Latin
language data is needed as the English data is sufficient to represent the
layout styles.

Table VII shows the F1-scores across multiple languages. F-RCNN-Q is not
evaluated for the three Asian languages, because we don’t have suitable
training data, and Table VI indicates that synthetic training data is not
useful for this model. The GCN models produce best results in almost all the
languages tried, once again showing good generalizability.

TABLE VII<EMAIL_ADDRESS>scores tested on the multi-language evaluation set. | OCR + | F-RCNN | OCR + | OCR +
---|---|---|---|---
Language | Heuristic | -Q | GCNs | Ground Truth
English | 0.429 | 0.513 | 0.544 | 0.890
French | 0.438 | 0.557 | 0.553 | 0.885
German | 0.427 | 0.538 | 0.566 | 0.873
Italian | 0.455 | 0.545 | 0.556 | 0.862
Spanish | 0.449 | 0.597 | 0.616 | 0.885
Chinese | 0.370 | - | 0.485 | 0.790
Japanese | 0.398 | - | 0.487 | 0.772
Korean | 0.400 | - | 0.547 | 0.807

The GCN models are also flexible in handling text lines written in vertical
directions, which are common in Japanese and Chinese, and also appear in
Korean. Although we don’t have much training data with vertical lines, the
bounding box structures of lines and symbols in these languages remain the
same when the lines are written vertically, as if they were written
horizontally while the image is rotated clockwise by 90 degrees. Fig. 16 shows
such an example. Since our models are trained to handle all rotation angles,
such paragraphs can be correctly identified.

##  6 Conclusions and Future Work

We demonstrate that GCN models can be powerful and efficient for the task of
paragraph estimation. Provided with a good OCR engine, they can match image
based models with much lower requirement on training data and computation
resources, and significantly beat them on non-axis-aligned inputs with complex
layout styles. The graph convolutions in these models give them unique
advantages in dealing with different levels of page elements and their
relations.

Future work includes model performance improvement through both training data
and model architectures. Training data can be made more realistic by tuning
the web scraping pipeline and adding more complex degradation transformations
such as wrinkling effects on document pages. Also, alternative model
architectures and graph structures mentioned in subsection 3.5 may improve
quality and performance.

Another aspect of the future work is to extend the GCN models’ capability to
identify more types of entities and extract document structural information
such as reading order. Some entities like titles and list items are similar to
paragraphs, while some others like tables and document sections are not
straightforward to handle with our proposed models. Image based CNNs may be
needed with their outputs used as node or edge features in the GCN model, so
that non-text components in the document (e.g. checkboxes, table grid lines)
can be captured. In addition, reading order among entities is a necessary step
if we want to identify semantic paragraphs that span across multiple
columns/pages.

Figure 16: Example of paragraphs from text lines with vertical writing
direction.

## Acknowledgments

The authors would like to thank Chen-Yu Lee, Chun-Liang Li, Michalis Raptis,
Sandeep Tata and Siyang Qin for their helpful reviews and feedback, and to
thank Alessandro Bissacco, Hartwig Adam and Jake Walker for their general
leadership support in the overall project effort.

## References

  * [1] W. Horak, “Office document architecture and office document interchange formats: Current status of international standardization,” _Computer_ , vol. 18, pp. 50–60, October 1985.
  * [2] R. Cattoni, T. Coianiz, S. Messelodi, and C. M. Modena, “Geometric layout analysis techniques for document image understanding: A review,” IRST, Trento, Italy, Tech. Rep. 9703-09, 1998.
  * [3] X. Yang, E. Yumer, P. Asente, M. Kraley, D. Kifer, and C. L. Giles, “Learning to extract semantic structure from documents using multimodal fully convolutional neural networks,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * [4] D. Niyogi and S. N. Srihari, “A rule-based system for document understanding,” in _Proceedings of the Fifth AAAI National Conference on Artificial Intelligence_ , ser. AAAI’86. AAAI Press, 1986, p. 789–793.
  * [5] S. N. Srihari and G. W. Zack, “Document image analysis,” in _Proceedings of the 8th International Conference on Pattern Recognition_. AAAI Press, 1986, p. 434–436.
  * [6] T. M. Breuel, “High performance document layout analysis,” in _Proceedings of the Symposium on Document Image Understanding Technology_ , Greenbelt, MD, 2003, pp. 209–218.
  * [7] R. W. Smith, “Hybrid page layout analysis via tab-stop detection,” in _10th International Conference on Document Analysis and Recognition, ICDAR 2009, Barcelona, Spain, 26-29 July 2009_. IEEE Computer Society, 2009, pp. 241–245. [Online]. Available: https://doi.org/10.1109/ICDAR.2009.257
  * [8] X. Zhong, J. Tang, and A. Jimeno-Yepes, “Publaynet: Largest dataset ever for document layout analysis,” in _2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019_. IEEE, 2019, pp. 1015–1022. [Online]. Available: https://doi.org/10.1109/ICDAR.2019.00166
  * [9] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 1, pp. 61–80, 2009.
  * [10] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–21, 2020.
  * [11] D. G. Kirkpatrick and J. D. Radke, “A framework for computational morphology,” _Machine Intelligence and Pattern Recognition_ , vol. 2, pp. 217–248, 1985. [Online]. Available: https://doi.org/10.1016/B978-0-444-87806-9.50013-X
  * [12] “Wikipedia, the free encyclopedia.” [Online]. Available: https:// en.wikipeida.org
  * [13] R. Smith, “An overview of the Tesseract OCR engine,” in _Proc. 9th IEEE Intl. Conf. on Document Analysis and Recognition (ICDAR)_ , 2007, pp. 629–633.
  * [14] P. Riba, A. Dutta, L. Goldmann, A. Fornés, O. R. Terrades, and J. Lladós, “Table detection in invoice documents by graph neural networks,” in _2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019_. IEEE, 2019, pp. 122–127. [Online]. Available: https://doi.org/10.1109/ICDAR.2019.00028
  * [15] T. M. Breuel, “An algorithm for finding maximal whitespace rectangles at arbitrary orientations for document layout analysis,” in _Seventh International Conference on Document Analysis and Recognition, 2003. Proceedings._ , 2003, pp. 66–70 vol.1.
  * [16] S. Ren, K. He, R. B. Girshick, and J. Sun, “Faster R-CNN: towards real-time object detection with region proposal networks,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 39, no. 6, pp. 1137–1149, 2017. [Online]. Available: https://doi.org/10.1109/TPAMI.2016.2577031
  * [17] K. He, G. Gkioxari, P. Dollár, and R. B. Girshick, “Mask R-CNN,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 42, no. 2, pp. 386–397, 2020. [Online]. Available: https://doi.org/10.1109/TPAMI.2018.2844175
  * [18] Y. Jiang, X. Zhu, X. Wang, S. Yang, W. Li, H. Wang, P. Fu, and Z. Luo, “R2 cnn: Rotational region cnn for arbitrarily-oriented scene text detection,” in _2018 24th International Conference on Pattern Recognition (ICPR)_ , 2018, pp. 3610–3615.
  * [19] J. Lee, H. Hayashi, W. Ohyama, and S. Uchida, “Page segmentation using a convolutional neural network with trainable co-occurrence features,” in _2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019_. IEEE, 2019, pp. 1023–1028. [Online]. Available: https://doi.org/10.1109/ICDAR.2019.00167
  * [20] A. L. L. M. Maia, F. D. Julca-Aguilar, and N. S. T. Hirata, “A machine learning approach for graph-based page segmentation,” in _31st SIBGRAPI Conference on Graphics, Patterns and Images, SIBGRAPI 2018, Paraná, Brazil, October 29 - Nov. 1, 2018_. IEEE Computer Society, 2018, pp. 424–431. [Online]. Available: https://doi.org/10.1109/SIBGRAPI.2018.00061
  * [21] Y. Fujii, K. Driesen, J. Baccash, A. Hurst, and A. C. Popat, “Sequence-to-label script identification for multilingual OCR,” in _14th IAPR International Conference on Document Analysis and Recognition, ICDAR 2017, Kyoto, Japan, November 9-15, 2017_. IEEE, 2017, pp. 161–168. [Online]. Available: https://doi.org/10.1109/ICDAR.2017.35
  * [22] B. L. Davis, B. S. Morse, S. Cohen, B. L. Price, and C. Tensmeyer, “Deep visual template-free form parsing,” in _2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019_. IEEE, 2019, pp. 134–141. [Online]. Available: https://doi.org/10.1109/ICDAR.2019.00030
  * [23] M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars, _Computational Geometry: Algorithms and Applications_ , 3rd ed. Santa Clara, CA, USA: Springer-Verlag TELOS, 2008.
  * [24] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in _Advances in Neural Information Processing Systems_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associates, Inc., 2015, pp. 2224–2232.
  * [25] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ser. ICML’17. JMLR.org, 2017, p. 1263–1272.
  * [26] W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA_ , I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, Eds., 2017, pp. 1024–1034. [Online]. Available: http://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs
  * [27] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018_ , 2018. [Online]. Available: https://openreview.net/forum?id=rJXMpikCZ
  * [28] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” _CoRR_ , vol. abs/1706.03762, 2017. [Online]. Available: http://arxiv.org/abs/1706.03762
  * [29] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” _Journal of the American Society for Information Science and Technology_ , vol. 58, no. 7, p. 1019–1031, May 2007.
  * [30] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” in _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_ , 2018, pp. 5171–5181. [Online]. Available: http://papers.nips.cc/paper/7763-link-prediction-based-on-graph-neural-networks
  * [31] Q. Li, Z. Han, and X. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” in _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , S. A. McIlraith and K. Q. Weinberger, Eds. AAAI Press, 2018, pp. 3538–3545.
  * [32] G. Li, M. Müller, A. K. Thabet, and B. Ghanem, “Deepgcns: Can gcns go as deep as cnns?” in _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019_. IEEE, 2019, pp. 9266–9275. [Online]. Available: https://doi.org/10.1109/ICCV.2019.00936
  * [33] T. Kanungo and R. M. Haralick, “An automatic closed-loop methodology for generating character groundtruth for scanned documents,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 21, no. 2, pp. 179–183, 1999.
  * [34] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 770–778.
  * [35] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [36] C. Clausner, A. Antonacopoulos, and S. Pletschacher, “ICDAR2019 competition on recognition of documents with complex layouts - RDCL2019,” in _2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019_. IEEE, 2019, pp. 1521–1526. [Online]. Available: https://doi.org/10.1109/ICDAR.2019.00245