11institutetext: Departamento de Astronomía y Astrofísica, Universidad de
Valencia, E-46100 Burjassot, Valencia, Spain; 11email<EMAIL_ADDRESS>22institutetext: Observatorio Astronómico, Universidad de Valencia, E-46980
Paterna, Valencia, Spain 33institutetext: Instituto de Astrofísica de
Canarias, Vía Láctea S/N, La Laguna 38200, Tenerife, Spain 44institutetext:
Departamento de Astrofísica, Universidad de la Laguna, La Laguna 38200,
Tenerife 55institutetext: Departamento de Física Teórica y del Cosmos,
Universidad de Granada, Campus de Fuentenueva, 18071 Granada, Spain
66institutetext: Instituto Carlos I de Física Teórica y Computacional,
Universidad de Granada, 18071 Granada, Spain 77institutetext: Instituto de
Física y Astronomía, Universidad de Valparaíso, Avda. Gran Bretaña 1111, Playa
Ancha, Valparaíso 2360102, Chile 88institutetext: Department of Physics,
Faculty of Natural Sciences, University of Haifa, Haifa 3498838, Israel
99institutetext: Haifa Research Center for Theoretical Physics and
Astrophysics, University of Haifa, Haifa 3498838, Israel 1010institutetext:
Institute of Physics (IGAM), University of Graz, Universitätsplatz 5, 8010,
Graz, Austria 1111institutetext: Institute of Cosmology and Gravitation,
University of Portsmouth, Burnaby Rd, Portsmouth PO1 3FX, UK

# Revealing the structure of the lensed quasar Q 0957+561

III. Constraints on the size of the broad-line region

C. Fian 11 J. A. Muñoz 1122 E. Mediavilla 3344 J. Jiménez-Vicente 5566 V.
Motta 77 D. Chelouche 8899 A. Wurzer 1010 A. Hanslmeier 1010 K. Rojas 1111

###### Abstract

Aims. Our aim is to examine the size, kinematics, and geometry of the broad-
line region (BLR) in the double-lensed quasar Q 0957+561 by analyzing the
impact of microlensing on various rest-frame ultraviolet broad-emission lines
(BELs).

Methods. We explore the influence of intrinsic variability and microlensing on
the C IV, C III], and Mg II emission lines through multiple spectroscopic
observations taken between April 1999 and January 2017. By utilizing the line
cores as a reference for no microlensing and correcting for the long time
delay between the images, we estimate the sizes of the regions emitting the
broad-line wings using a Bayesian approach.

Results. Our study of the microlensing amplitudes between the lensed images of
the quasar Q 0957+561 reveals differing sizes of the regions emitting the
three prominent BELs C IV, C III], and Mg II. The strength of the differential
microlensing indicates that the high-ionization line C IV arises from a
compact inner region of the BLR with a half-light radius of $R_{1/2}\gtrsim
16.0$ lt-days, which represents a lower limit on the overall size of the BLR
and is comparable to the size of the region emitting the r-band continuum in
this system. A somewhat larger size of $R_{1/2}\gtrsim 44$ lt-days is obtained
for the semi-forbidden line C III]. Microlensing has a weak impact on the
lower-ionization line Mg II, which is emitted from a region with a half-light
radius of $R_{1/2}\gtrsim 50$ lt-days. These findings suggest that the BEL
regions may have distinct geometries and kinematics, with the more extended
ones being spherically symmetric, and the most compact ones being
nonspherical, with motions likely confined to a plane.

###### Key Words.:

gravitational lensing: strong – gravitational lensing: micro – quasars:
general – quasars: emission lines – quasars: individual (Q 0957+561)

##  1 Introduction

Table 1: Spectroscopic data.

Epoch |  Date |  Observed BEL |  Facility |  Reference
---|---|---|---|---
1a |  15-04-1999 |  C IV, C III], Mg II |  HST |  Goicoechea et al. 2005
1b |  02-06-2000 |  C IV, C III], Mg II |  HST |  Goicoechea et al. 2005
2 |  12-01-2008 |  C IV, C III], Mg II |  MMT |  Motta et al. 2012
3 |  29-01-2009(∗) |  C IV, C III] |  NOT |  GLENDAMA
4 |  03/2010(∗) |  C IV, C III] |  NOT |  GLENDAMA
5 |  10/2010(∗) |  Mg II |  LT |  GLENDAMA
6 |  03/2011(∗) |  Mg II |  LT |  GLENDAMA
7 |  04/2011(∗) |  Mg II |  LT |  GLENDAMA
8 |  12/2011(∗) |  Mg II |  LT |  GLENDAMA
9 |  18-12-2011(∗) |  C IV, C III] |  NOT |  GLENDAMA
10 |  14-03-2013(∗) |  C IV, C III] |  NOT |  GLENDAMA
11 |  05-03-2015 |  C III], Mg II |  LT |  GLENDAMA
12 |  19-11-2015(∗) |  C III], Mg II |  LT |  Gil-Merino et al. 2018
13 |  12-03-2016(∗) |  C IV, C III], Mg II |  WHT |  Fian et al. 2021b
14 |  17-01-2017 |  C III], Mg II |  LT |  Gil-Merino et al. 2018

Notes. (∗)The spectra from multiple observations conducted within a short time
frame (such as several exposures taken on the same night or several
observations within a month) were combined by taking their average.

The twin quasar Q 0957+561 was discovered in 1979 by Dennis Walsh (Walsh et
al. 1979) and was the first gravitational lens system to be identified. The
quasar is lensed into two bright images (with a separation of $\sim$6″) by a
giant elliptical lens galaxy at a redshift of $z_{l}=0.36$, which is part of a
galaxy cluster that also contributes to the lensing (Stockton 1980; Garrett et
al. 1992). The redshift of Q 0957+561 is $z_{s}=1.41$, causing a significant
portion of its ultraviolet (UV) emission to be observed at optical
wavelengths. Multi-wavelength observations of the temporal evolution of
magnification ratios in Q 0957+561 have generated a wealth of monitoring data,
making it an attractive target for studying physical phenomena taking place in
the lens galaxy, such as gravitational microlensing by stars and extinction by
gas and dust clouds (see, e.g., Zuo et al. 1997; Goicoechea et al. 2005; Motta
et al. 2012), as well as physical processes taking place in the background
source itself, such as intrinsic variability of the quasar (see, e.g., Lloyd
1981; Miller et al. 1981; Gondhalekar & Wilson 1982; Planesas et al. 1999;
Hutchings 2003). Optical monitoring of lensed quasars has revealed a diverse
range of intrinsic flux variations, which can be used to determine accurate
time delays between quasar images. In the case of Q 0957+561, image A leads
image B by 417 days (Shalyapin et al. 2008). These time delays can be used to
constrain the Hubble constant (Wong et al. 2020; Millon et al. 2020; Napier et
al. 2023) and lensing mass distributions (Acebron et al. 2022; Forés-Toribio
et al. 2022), and serve as a powerful probe of dark energy (Wang et al. 2022;
Liu et al. 2022). Compact objects (i.e., stars) in galaxies can cause
extrinsic variations in the photometric and spectroscopic observations of
lensed quasars through a phenomenon known as microlensing. This effect can be
used to constrain the sizes of the continuum-emitting sources surrounding the
central supermassive black holes (Fian et al. 2016, 2018b, 2021a; Cornachione
et al. 2020a, b) in order to reveal the structures of the broad-line regions
(BLRs; Rojas et al. 2020; Hutsemékers & Sluse 2021; Fian et al. 2018a, 2021b),
and to estimate the masses of the black holes (Mediavilla et al., 2018, 2019;
Fian et al., 2022).

Our understanding of the geometry and kinematics of BLRs in quasars remains
limited. To investigate the impact of microlensing on broad emission lines
(BELs), it is necessary to compare spectroscopy obtained from multiple
observations. Two decades of observations of Q 0957+561 have facilitated a
comprehensive examination of its temporal evolution. Despite extensive
photometric and spectroscopic monitoring of the quasar components A and B, the
history of their magnification ratios remains a mystery. Goicoechea et al.
(2005) attempted to explain the observed magnification ratios through either a
dust system located between the quasar and the observer (differential
extinction), or a population of microlenses in the deflector. They found that
the flux ratios are consistent with both alternatives, and even a mixed
scenario (extinction + microlensing) is possible. Motta et al. (2012)
calculated the dust-extinction curve using BEL ratios and were able to
differentiate it from microlensing. Thus, microlensing has become the favored
explanation for the anomalous optical continuum ratios, supported by clear
evidence of microlensing in the r-band light curves of the system (see, e.g.,
Fian et al. 2021a; Cornachione et al. 2020a). This concept was initially
proposed by Chang & Refsdal (1979) soon after the discovery of the quasar.

In this study, we undertake a thorough analysis of the time-variable
magnification ratios in the wings of the BELs of C IV, C III, and Mg II. Our
examination of gravitational microlensing and intrinsic variability involves
estimating the magnitude differences between images (after correcting for the
time delay), and the amplitude of variation in a single image over multiple
epochs of observation. The paper is structured as follows. In Section 2, we
present the spectra obtained from the literature. Section 3 outlines the
analysis of extrinsic and intrinsic variability in the BELs. Our method for
constraining the size of the broad-line emitting regions is presented in
Section 4. Finally, in Section 5, we provide conclusions based on our
findings.

Figure 1: Rest-frame emission line profiles of images A (black) and B (red)
for C IV (top), C III] (middle), and Mg II (bottom) displayed in different
epochs, with the continuum subtracted and the line cores matched. The leftmost
panels depict the spectra of image A taken in April 1999 and image B taken 14
months later (corresponding to the time delay in this system) in June 2000.

##  2 Data and observations

In this study, we analyzed rest-frame UV spectra of images A and B in the
lensed quasar Q 0957+561. Our data set consists of 15 epochs of observation
spanning a period of 18 years (1999-2017). The initial spectra of the lens
system were acquired by Goicoechea et al. (2005) using the 2.4m Hubble Space
Telescope (HST). Motta et al. (2012) later conducted observations with the
6.5m Multiple Mirror Telescope (MMT) in 2008. Most of the spectra were
provided by the Gravitational LENses and DArk MAtter
(GLENDAMA111https://grupos.unican.es/glendama/) project of the University of
Cantabria (see Gil-Merino et al. 2018). The GLENDAMA observations were carried
out with the 2.0m Liverpool Telescope (LT) and the 2.6m Nordic Optical
Telescope (NOT). Additionally, we obtained spectra in March 2016 using the
4.2m William Herschel Telescope (WHT) located at the Roque de los Muchachos in
La Palma, Canary Islands. The data from the literature were already fully
reduced. The emission lines for the quasar components A and B are displayed in
Figure 1, with observing information and references listed in Table 1.

##  3 Methods

The estimation of microlensing signals in lensed quasars through the analysis
of BELs can be complicated by the presence of intrinsic variability that is
time-delayed between different images. Intrinsic variability can alter the
shape of the BELs and mimic microlensing, leading to erroneous source-size
estimates. To accurately measure magnitude differences between images, we
select spectra that are separated in time approximately by the time delay
between the images. Time delays in gravitationally lensed quasars are believed
to be unique numbers that can be measured with high precision given good-
quality light curves and models for the contaminating effects of gravitational
microlensing. In the absence of microlensing, the time delay for both the
continuum and broad-line emitting regions should be identical. However, as
demonstrated by Liao (2020), gravitational microlensing can lead to variations
in the time delays measured at different wavelengths. Recent work by Tie &
Kochanek (2018) shows that gravitational microlensing produces changes in the
actual time delays on the order of days. In this study, we account for this
effect by incorporating an additional lag of +/- 20 days, which corresponds to
the scale of the light-crossing time of the accretion disk in this system, as
estimated in Fian et al. (2021a) and Cornachione et al. (2020a). Of the
available spectra, five pairs fulfill this criterion, although not all
emission lines have been observed in all the selected epochs. This results in
two epoch pairs (1a–1b, 3–4) covering the C IV line, three epoch pairs (1a–1b,
3–4, 12–14) including the C III] line, and three epoch pairs (1a–1b, 5–8,
12–14) containing the Mg II line.

The scale of the microlensing pattern caused by stars and compact objects in a
lens galaxy (or cluster) is set by the Einstein radius, $r_{E}$. Significant
microlensing fluctuations occur when the source size, $r_{s}$, is comparable
to or smaller than $r_{E}$. The amplitude of these fluctuations will then be
controlled by $r_{s}/r_{E}$, with smaller ratios leading to larger amplitudes.
If the observational epochs are separated in time by more than the
microlensing event timescale, also known as the Einstein radius crossing time,
$t_{E}$, microlensing measurements are likely to be independent. This
timescale is determined by the effective transverse velocity of the source,
$v$, and $r_{E}$, with $t_{E}=r_{E}/v$ (Paczynski 1986). Mosquera et al.
(2011) report values of $r_{E}=3.25\times 10^{16}\sqrt{M/0.3M_{\odot}}$ cm and
$t_{E}=12.39$ years for the lens system Q 0957+561. The adoption of transverse
peculiar velocity estimates ($\sigma_{pec}\sim 640$ km s-1 for $z_{l}\sim
0.5$) from Mediavilla et al. (2016) results in an approximately 50% reduction
in $t_{E}$. Therefore, the criterion of independence is presumed to be met for
microlensing measurements obtained from the selected pairs of observations.

As an initial step, the continuum for each image and each emission line is
removed by fitting a straight line to the continuum regions adjacent to the
emission line. To account for varying line widths, we use windows of varying
widths to estimate the continuum, avoiding regions of known emission features.
The line cores are believed to be produced by material spread over a large
region (narrow-line region and outer regions of the BLR) and are therefore
thought to be less susceptible to microlensing. Adopting the conclusion from
Fian et al. (2018a) that emission line cores are relatively insensitive to
microlensing by solar mass objects, we establish a baseline of no microlensing
by using the cores as a reference. To investigate whether the same holds true
for the core of the high-ionization line C IV in Q 0957+561, we employed a
method that involves fitting multiple straight lines to the continuum in the
wavelength range between C IV and C III], subtracting them, and subsequently
normalizing the cores of the lower-ionization line C III]. We opted for this
approach since C III] is expected to be less prone to microlensing and
instrumental/calibration issues than C IV, and also to mitigate the larger
extinction effects that may arise from a direct comparison with Mg II. Our
analysis revealed that, on average, the C IV core exhibits minor variations of
$(B/A)_{core}=-0.02\pm 0.08$ mag (68% confidence interval), indicating that
there appears to be little core variability in this system. Therefore, it is
reasonable to conclude that microlensing effects are unlikely to have a
significant impact on the BEL cores, which lends support to the reliability of
the microlensing results presented in this work. To utilize the line cores as
a reference for no microlensing, we defined the flux within a narrow interval
($\pm$ 6Å) centered on the peak of the line and normalized the emission line
cores of images A and B accordingly. Normalizing the line cores by multiplying
the spectrum of image B to match the core flux of image A also effectively
removes the effects of macro magnification and differential extinction (see,
e.g., Guerras et al. 2013). After subtracting the continuum and matching the
line cores, we isolate the line cores from the wings by a buffer of a few
Ångströms to accurately assess variability in the wings. We then estimate the
differential microlensing in the BELs by determining the average wing emission
in velocity intervals of $\sim$5000 km s-1 on either side of the line. In
those cases in which absorption lines affect the emission line wing, a
narrower integration window was chosen (blue wing of C IV) or the estimation
was omitted (blue wing of Mg II) to mitigate their impact. The magnitude
differences (caused by intrinsic variability and/or microlensing variability)
between different observational epochs for a given image can be estimated in a
similar way. The results are listed in Tables 2 and 3.

The analysis of Figure 1 and Tables 2–3 (with special attention being paid to
the scatter) reveals that the red wing of the C IV emission line is affected
by strong intrinsic variability and microlensing (variability), as evidenced
by the temporal changes in the wing. The red wing of C III] is also subject to
substantial intrinsic variability, while both the blue wings of C IV and C
III] display moderate variations. In the blue wings of C IV and C III],
intrinsic variability affects both images to the same extent, while in the red
wings, variability is slightly more pronounced in image B compared to image A,
possibly due to microlensing variability. Mg II exhibits only limited signs of
intrinsic variability and the effects of microlensing on this line are weak.

Table 2: Differential microlensing (B–A) in the BEL wings.

Emission Line | Wing |  $\Delta$m (mag) | Scatter (mag)
---|---|---|---
(1) | (2) | (3) | (4)
C IV | blue | $-0.07$ | $0.00$
red | $-0.33$ | $0.32$
C III] | blue | $\ \ 0.00$ | $0.14$
red | $+0.09$ | $0.33$
Mg II | blue | – | –
red | $-0.09$ | $0.07$

Notes. Col. (1): Emission line core used as a reference for no microlensing.
Col. (2): Emission line wing. Cols. (3)–(4): Average differential microlensing
and scatter between observational epochs.

Table 3: Variability in the BEL wings across different observational epochs.

Emission Line | Wing | Image |  $\Delta$m (mag) | Scatter (mag)
---|---|---|---|---
(1) | (2) | (3) | (4) | (5)
C IV | blue | A | $+0.06$ | $0.23$
B | $+0.05$ | $0.30$
red | A | $-0.05$ | $0.72$
B | $-0.13$ | $0.66$
C III] | blue | A | $+0.02$ | $0.16$
B | $+0.02$ | $0.18$
red | A | $+0.02$ | $0.36$
B | $+0.04$ | $0.47$
Mg II | blue | A | – | –
B | – | –
red | A | $\ \ 0.00$ | $0.09$
B | $-0.01$ | $0.11$

Notes. Col. (1): Emission line core used as a reference for no microlensing.
Col. (2): Emission line wing. Col. (3): Lensed Image. Cols. (4)–(5): Average
magnitude difference and scatter between epoch pairs.

Figure 2: Probability distributions of the half-light radii $R_{1/2}$ for the
regions emitting the C IV (left), C III] (middle), and Mg II line (right). The
vertical dashed lines indicate the expected size of the emission region, while
the gray-shaded regions represent the one-sigma intervals.

##  4 Bayesian size estimates

Based on the differential microlensing estimates between images A and B in the
BEL wings, we can constrain the size of their emission region and provide
insights into the BLR structure of the lensed quasar Q 0957+561. To obtain an
average estimate of the size, we treat each microlensing measurement as a
single-epoch event and compute the joint microlensing probability, $P(r_{s})$,
from all (time-delay-corrected and presumably independent) epochs of
observation. Our procedure closely follows the methodology described in
Guerras et al. (2013).

Our simulations are based on 2000 $\times$ 2000 pixel2 magnification maps,
with a pixel size of approximately 0.3 light-days, covering a total area of
627$\times$627 light-days2 on the source plane. The maps were generated using
the Fast Multipole Method – Inverse Polygon Mapping
algorithm222https://gloton.ugr.es/microlensing/ (FMM–IPM) described by
Jiménez-Vicente & Mediavilla (2022). The local convergence and shear values,
$\kappa$ and $\gamma$, are used to determine the magnification at each image
position. These dimensionless values were obtained by fitting a singular
isothermal sphere with external shear (SIS+$\gamma_{e}$) to the image
coordinates (Mediavilla et al. 2009). Although there are more sophisticated
models available (see Fadely et al. 2010), this simple model was chosen to
maintain consistency with prior publications on this source, including Paper I
and II by Fian et al. (2021a, 2022). A mean stellar mass of $M=0.3M_{\odot}$
was assumed, and the size scale is proportional to the square root of the
microlens mass ($r_{s}\propto\sqrt{M/M_{\odot}}$). The microlensing amplitude
also depends on the local surface mass density fraction in compact objects
(such as stars) compared to that of dark matter at the lensed image location
(see, e.g., Schechter & Wambsganss 2002). In the case of Q 0957+561, the two
lensed images are located at very different radii from the center of the lens
galaxy, with image B appearing close to the center ($\sim$1″), and the light
of component A passing far away ($\sim$5″). As a result, the surface mass
density of the lens galaxy is much lower at the position of component A. In
this study, we adopt the $\alpha$ values reported by Jiménez-Vicente et al.
(2015), with $\alpha\sim 0.3$ at the position of image B and $\alpha\sim 0$
for image A, which is equivalent to not using any magnification map for this
image. To investigate how variations in $\kappa$ and $\gamma$ affect the
simulated magnification distribution of image B, we altered these parameters
by $\pm 0.1$. Our analysis reveals that varying $\kappa$ within this range
does not result in significant changes to the microlensing distribution. When
varying $\gamma$, we observe modest displacements of approximately $0.1$ mag.

To model the impact of extended sources on our simulations, we employ a
Gaussian luminosity profile, $I(r_{s})\propto exp(-R^{2}/2r_{s}^{2})$, to
represent the emission region of the BEL wings. We note that Mortonson et al.
(2005) showed that the microlensing magnification statistics are largely
insensitive to the radial profile of the source (see also Muñoz et al. 2016).
The magnifications experienced by a source of size $r_{s}$ are then obtained
by convolving the magnification maps with 2D Gaussian profiles of sigma
$r_{s}$. The probability of reproducing the observed microlensing is estimated
by randomly placing the Gaussian source on our microlensing magnification
maps. To cover a wide range of source sizes, we employ a linear grid ranging
from $\sim$1 to 150 light-days. These sizes can be converted to half-light
radii with the relation $R_{1/2}=1.18\,r_{s}$.

Using our sample of spectroscopic measurements, we roughly determine the
structure of the BLR in Q 0957+561. Adopting a Bayesian approach, we estimate
the probability of $r_{s}$ given the observed microlensing magnifications. The
resulting joint likelihood functions for the C IV, C III], and Mg II emission
lines are displayed in Figure 2, and allow us to calculate 68% confidence size
estimates. We infer sizes, expressed in $\sqrt{M/0.3M_{\odot}}$, of
$R_{1/2}=16.0_{-6.8}^{+5.3}$, $R_{1/2}=44.3_{-16.0}^{+15.3}$, and
$R_{1/2}=49.9_{-16.4}^{+15.0}$ lt-days for the regions emitting the C IV, C
III], and Mg II lines, respectively. To roughly examine the implications of
covariance on our size estimates, we conducted an additional study for Mg II,
excluding the epoch pair 5–8, which had less temporal separation ($\sim 5$
years) than the other image pairs considered ($\sim$7 to $\sim$11 years). As a
result, the uncertainties in the size estimate increases to $\pm 18.3$ lt-
days, reflecting a 17% increase in the error compared to the initial
measurement.

As mentioning above, the amplitude of microlensing is affected by the relative
density of the local stellar surface mass compared to the dark matter at the
image location, as reported by Schechter & Wambsganss (2002). As a
consequence, the emission region sizes are also sensitive to the stellar mass
fraction present, but the precise value of this latter ($\alpha\sim 0.3$)
remains uncertain. To address this uncertainty, we studied the impact of
$\alpha$ by varying it between 0.2 and 0.4. We recomputed the magnification
maps and repeated the calculations, finding that the estimated sizes of the
BEL emitting regions undergo a change of approximately 22% on average.
Specifically, we observe that larger values of $\alpha$ are associated with
larger source sizes, whereas lower values of $\alpha$ lead to smaller size
estimates. To explore the sensitivity of our size estimates to the width of
the core region, we tested different intervals (1000, 2000, and 3000 km s-1)
to normalize the emission line cores. We then recalculated the sizes and
evaluated the uncertainties introduced by this procedure. Our analysis shows
that the size estimates vary by less than 10%. We note that the separation of
the line emission into two parts can be supported by the idea that the BLR is
formed by a flat inner region (likely related to the accretion disk giving
rise to the line wings), surrounded by a larger three-dimensional structure
that produces the line core (see e.g., Popović et al. 2004). Therefore, the
microlensing-based size estimates for the regions emitting the line wings
should be regarded as approximate lower bounds rather than a precise estimate
of the size of the BEL region. It is important to mention that the blue wing
of the semi-forbidden line C III] is contaminated by several underlying
emission lines (Al III, Si III], and Fe III), which might bias the size
estimates toward smaller sizes. Additionally, the high-velocity ends of the Mg
II line wings may be affected by the pseudo-continuum formed by thousands of
UV Fe II blends, and so caution should be taken when interpreting the results.

##  5 Conclusions

Through optical spectroscopy, we conducted a search for microlensing and
intrinsic variability in 15 epochs of observation of the gravitationally
lensed quasar Q 0957+561. Our analysis of the flux ratios between images A and
B in the three most frequently observed BELs provides insight into the inner
structure of the quasar. Our main findings are as follows:

  1. 1.

Extrinsic and intrinsic variability. The techniques applied in this study
enabled us to separately examine the effects of microlensing between the
lensed quasar images A and B, and intrinsic variability within a single image
across different observational epochs. Our findings indicate that Q 0957+561
is a hybrid case with both moderate microlensing and strong intrinsic
variability present. Consistent with prior studies (Guerras et al. 2013; Fian
et al. 2018a, 2021b), our results show that high- and low-ionization lines are
differently microlensed, with higher magnification seen in the high-ionization
lines, indicating a more compact emission region. The measured microlensing in
the red wing of C IV, averaging around 0.3 mag, is comparable to the
microlensing (approximately 0.35 mag) determined from analyzing the 21year
r-band light curves in this system (as per Fian et al. 2021a). In general,
intrinsic variability affects the same spectral features as microlensing (such
as the red wing of C IV and to some extent the line wings of C III]), with
varying levels of intensity depending on ionization degree. We find the impact
of intrinsic variability or microlensing on the Mg II wings to be weak.

  2. 2.

BLR size. Our analysis of the magnitude differences between the lensed images
A and B suggests emission region sizes of $\gtrsim 44$ and $\gtrsim 50$ lt-
days for C III] and Mg II, respectively, in line with previous studies
(Guerras et al. 2013; Fian et al. 2018a), as well as with findings from
reverberation mapping campaigns (Homayouni et al. 2020). Our inferred size for
the region emitting the C IV line wings ($\gtrsim 16.0$ lt-days) is
comparable, within the errors, to that of the r-band continuum in this system
($\sim 17.6$ lt-days; see Cornachione et al. 2020a; Fian et al. 2021a), and to
that of the UV Fe III blend ($\sim 15$ lt-days; see Fian et al. 2022),
supporting the notion that the line partly originates from the accretion disk.
By varying the stellar mass fraction, the lower limit of the C IV emission
region changes to $14.0$ lt-days ($\alpha=0.2$) and $17.9$ lt-days
($\alpha=0.4$), respectively.

  3. 3.

BLR geometry. The impact of microlensing on the BLR of lensed quasars depends
on the geometry and kinematics of the BLR. Our spectroscopic analysis of the
lensed quasar Q 0957+561 reveals microlensing effects on the broad-line
components in the system. The extent of microlensing varies depending on the
line, appearing in either the blue or red wing, or in both wings with equal
intensity. This observation suggests that the BLR is not generally spherical
in shape, in agreement with previous studies such as Sluse et al. (2012), and
recent findings by Fian et al. (2018a, 2021b) and Hutsemékers & Sluse (2021).
An anisotropic geometry or velocity field is required to produce asymmetrical
deformations in an emission line, as demonstrated by Schneider & Wambsganss
(1990), Abajas et al. (2002), and Lewis & Ibata (2004). These latter authors
showed that microlensing of a spherical BLR (in both geometry and velocity
field) leads to symmetrical variations in the emission lines, while spatially
separated approaching and receding parts of the velocity field in Keplerian
disks can cause asymmetrical microlensing and possible shifts in the line
centroid (as seen in Braibant et al. 2016). The asymmetry observed in the red
wing of C IV might support the idea that this component originates from a
compact region (a few light-days in size) with a nonspherical geometry, most
likely following the motion of the accretion disk.

###### Acknowledgements.

We thank the anonymous referee for the valuable comments and suggestions. We
gratefully thank Luis J. Goicoechea and Vyacheslav N. Shalyapin for kindly
providing most of the spectroscopic data listed in Table 1. This research was
supported by the grants PID2020-118687GB-C31, PID2020-118687GB-C32, and
PID2020-118687GB-C33, financed by the Spanish Ministerio de Ciencia e
Innovación through MCIN/AEI/10.13039/501100011033. J.A.M. is also supported by
the Generalitat Valenciana with the project of excellence Prometeo/2020/085.
J.J.V. is also supported by projects FQM-108, P20_00334, and
A-FQM-510-UGR20/FEDER, financed by Junta de Andalucía. V.M. acknowledges
support from the project ANID FONDECYT Regular grant number 1231418, partial
support from the Centro de Astrofísica de Valparaíso, and from Fortalecimiento
del Sistema de Investigación e Innovación de la Universidad de Valparaíso
(UVA20993). D.C. is financially supported by the DFG grant HA3555-14/1 to Tel
Aviv University and University of Haifa, and by the Israeli Science Foundation
grant no. 2398/19.

## References

  * Abajas et al. (2002) Abajas, C., Mediavilla, E., Muñoz, J. A., Popović, L. Č., & Oscoz, A. 2002, ApJ, 576, 640
  * Acebron et al. (2022) Acebron, A., Grillo, C., Bergamini, P., et al. 2022, A&A, 668, A142
  * Braibant et al. (2016) Braibant, L., Hutsemékers, D., Sluse, D., & Anguita, T. 2016, A&A, 592, A23
  * Chang & Refsdal (1979) Chang, K. & Refsdal, S. 1979, Nature, 282, 561
  * Cornachione et al. (2020a) Cornachione, M. A., Morgan, C. W., Burger, H. R., et al. 2020a, ApJ, 905, 7
  * Cornachione et al. (2020b) Cornachione, M. A., Morgan, C. W., Millon, M., et al. 2020b, ApJ, 895, 125
  * Fadely et al. (2010) Fadely, R., Keeton, C. R., Nakajima, R., & Bernstein, G. M. 2010, ApJ, 711, 246
  * Fian et al. (2018a) Fian, C., Guerras, E., Mediavilla, E., et al. 2018a, ApJ, 859, 50
  * Fian et al. (2016) Fian, C., Mediavilla, E., Hanslmeier, A., et al. 2016, ApJ, 830, 149
  * Fian et al. (2021a) Fian, C., Mediavilla, E., Jiménez-Vicente, J., et al. 2021a, A&A, 654, A70
  * Fian et al. (2022) Fian, C., Mediavilla, E., Jiménez-Vicente, J., et al. 2022, A&A, 667, A67
  * Fian et al. (2018b) Fian, C., Mediavilla, E., Jiménez-Vicente, J., Muñoz, J. A., & Hanslmeier, A. 2018b, ApJ, 869, 132
  * Fian et al. (2021b) Fian, C., Mediavilla, E., Motta, V., et al. 2021b, A&A, 653, A109
  * Forés-Toribio et al. (2022) Forés-Toribio, R., Muñoz, J. A., Kochanek, C. S., & Mediavilla, E. 2022, ApJ, 937, 35
  * Garrett et al. (1992) Garrett, M. A., Walsh, D., & Carswell, R. F. 1992, MNRAS, 254, 27P
  * Gil-Merino et al. (2018) Gil-Merino, R., Goicoechea, L. J., Shalyapin, V. N., & Oscoz, A. 2018, A&A, 616, A118
  * Goicoechea et al. (2005) Goicoechea, L. J., Gil-Merino, R., & Ullán, A. 2005, MNRAS, 360, L60
  * Gondhalekar & Wilson (1982) Gondhalekar, P. M. & Wilson, R. 1982, Nature, 296, 415
  * Guerras et al. (2013) Guerras, E., Mediavilla, E., Jimenez-Vicente, J., et al. 2013, ApJ, 764, 160
  * Homayouni et al. (2020) Homayouni, Y., Trump, J. R., Grier, C. J., et al. 2020, ApJ, 901, 55
  * Hutchings (2003) Hutchings, J. B. 2003, AJ, 126, 24
  * Hutsemékers & Sluse (2021) Hutsemékers, D. & Sluse, D. 2021, A&A, 654, A155
  * Jiménez-Vicente & Mediavilla (2022) Jiménez-Vicente, J. & Mediavilla, E. 2022, ApJ, 941, 80
  * Jiménez-Vicente et al. (2015) Jiménez-Vicente, J., Mediavilla, E., Kochanek, C. S., & Muñoz, J. A. 2015, ApJ, 799, 149
  * Lewis & Ibata (2004) Lewis, G. F. & Ibata, R. A. 2004, MNRAS, 348, 24
  * Liao (2020) Liao, K. 2020, ApJ, 899, L33
  * Liu et al. (2022) Liu, T., Cao, S., Li, X., et al. 2022, A&A, 668, A51
  * Lloyd (1981) Lloyd, C. 1981, Nature, 294, 727
  * Mediavilla et al. (2018) Mediavilla, E., Jiménez-Vicente, J., Fian, C., et al. 2018, ApJ, 862, 104
  * Mediavilla et al. (2019) Mediavilla, E., Jiménez-vicente, J., Mejía-restrepo, J., et al. 2019, ApJ, 880, 96
  * Mediavilla et al. (2016) Mediavilla, E., Jiménez-Vicente, J., Muñoz, J. A., & Battaner, E. 2016, ApJ, 832, 46
  * Mediavilla et al. (2009) Mediavilla, E., Muñoz, J. A., Falco, E., et al. 2009, ApJ, 706, 1451
  * Miller et al. (1981) Miller, J. S., Antonucci, R. R. J., & Keel, W. C. 1981, Nature, 289, 153
  * Millon et al. (2020) Millon, M., Galan, A., Courbin, F., et al. 2020, A&A, 639, A101
  * Mortonson et al. (2005) Mortonson, M. J., Schechter, P. L., & Wambsganss, J. 2005, ApJ, 628, 594
  * Mosquera et al. (2011) Mosquera, A. M., Muñoz, J. A., Mediavilla, E., & Kochanek, C. S. 2011, ApJ, 728, 145
  * Motta et al. (2012) Motta, V., Mediavilla, E., Falco, E., & Muñoz, J. A. 2012, ApJ, 755, 82
  * Muñoz et al. (2016) Muñoz, J. A., Vives-Arias, H., Mosquera, A. M., et al. 2016, ApJ, 817, 155
  * Napier et al. (2023) Napier, K., Sharon, K., Dahle, H., et al. 2023, arXiv e-prints, arXiv:2301.11240
  * Paczynski (1986) Paczynski, B. 1986, ApJ, 304, 1
  * Planesas et al. (1999) Planesas, P., Martin-Pintado, J., Neri, R., & Colina, L. 1999, Science, 286, 2493
  * Popović et al. (2004) Popović, L. Č., Mediavilla, E., Bon, E., & Ilić, D. 2004, A&A, 423, 909
  * Rojas et al. (2020) Rojas, K., Motta, V., Mediavilla, E., et al. 2020, ApJ, 890, 3
  * Schechter & Wambsganss (2002) Schechter, P. L. & Wambsganss, J. 2002, ApJ, 580, 685
  * Schneider & Wambsganss (1990) Schneider, P. & Wambsganss, J. 1990, A&A, 237, 42
  * Shalyapin et al. (2008) Shalyapin, V. N., Goicoechea, L. J., Koptelova, E., Ullán, A., & Gil-Merino, R. 2008, A&A, 492, 401
  * Sluse et al. (2012) Sluse, D., Hutsemékers, D., Courbin, F., Meylan, G., & Wambsganss, J. 2012, A&A, 544, A62
  * Stockton (1980) Stockton, A. 1980, ApJ, 242, L141
  * Tie & Kochanek (2018) Tie, S. S. & Kochanek, C. S. 2018, MNRAS, 473, 80
  * Walsh et al. (1979) Walsh, D., Carswell, R. F., & Weymann, R. J. 1979, Nature, 279, 381
  * Wang et al. (2022) Wang, L.-F., Zhang, J.-H., He, D.-Z., Zhang, J.-F., & Zhang, X. 2022, MNRAS, 514, 1433
  * Wong et al. (2020) Wong, K. C., Suyu, S. H., Chen, G. C. F., et al. 2020, MNRAS[arXiv:1907.04869]
  * Zuo et al. (1997) Zuo, L., Beaver, E. A., Burbidge, E. M., et al. 1997, ApJ, 477, 568


# Neural Artistic Style Transfer with Conditional Adversarial
Networks11footnotemark: 1

Pathirage N. Deelaka22footnotemark: 2 Department of Computer Science and
Engineering, University of Moratuwa, Moratuwa 10400, Sri Lanka

###### Abstract

A neural artistic style transformation (NST) model can modify the appearance
of a simple image by adding the style of a famous image. Even though the
transformed images do not look precisely like artworks by the same artist of
the respective style images, the generated images are appealing. Generally, a
trained NST model specialises in a style, and a single image represents that
style. However, generating an image under a new style is a tedious process,
which includes full model training. In this paper, we present two methods that
step toward the style image independent neural style transfer model. In other
words, the trained model could generate semantically accurate generated image
under any content, style image input pair. Our novel contribution is a
unidirectional-GAN model that ensures the Cyclic consistency by the model
architecture.Furthermore, this leads to much smaller model size and an
efficient training and validation phase.

###### keywords:

###### MSC:

41A05, 41A10, 65D05, 65D17 Neural style transfer, Generative adversarial
network

††journal: Displays

##  1 Introduction

Imposing a style on an image is one of the most laborious tasks in graphic
designing. Most of the time, this process is handled by a skillful graphic
designer, and it will take hours to finish one image with good quality. Using
a neural style transfer (NST) model like [1] is not popular among the computer
graphics community due to several reasons. Since a model is specialized for
the trained style, a simple application that supports several style transfers
would be significant in terms of storage, considering the size of one NST
model. Furthermore, the NST model imposing alias artifacts on the input image
makes the model less reliable. Our first goal in this paper is to develop a
NST model that supports more than one style to transfer. The second goal is to
introduce a reliable NST model that imposes only general features related to a
style.

Fig. 1:  The generated image (c), which is generated for the content image (b)
using the CNN based NST model trained on the style image (a), shows to be
different from the image (d), which represents a Japanese artwork with the
same semantics of the content image (b).

Motivated by the Generative Adversarial Network (GAN) [2, 3, 4] based image-
to-image translation and style transfer literature [5], we upgrade the
convolutional neural network (CNN) based generator architecture into a
conditional generative adversarial network(cGAN) based image synthesis
process. Both proposed models have two independent discriminators to generate
content based adversarial loss and style based adversarial loss. The concept
introduced in the [5] on understanding and controlling latent space to impose
desirable features on generated images lay the fundamental idea to the second
model we introduce in this paper. Using a mapping network introduced in [5]
for matrix learning [6] make the encoder learn style features like in Natural
Language Processing semantic classification model generates feature embedding
for tokenized words.

CNN based NST models introduced so far [1, 7, 5] are models that train
thousands of content images only against a single image which will define the
transform style of the model trained. The objective function of this
supervised training was the weighted sum of content loss and style loss. Style
loss function calculates the norm of correlation matrix between style and
input images. Images generated using the above conventional NST embeds alias
artifacts from the style image and changes the color palette of the generated
image significantly from the content image, as shown in Fig. 1. Since neural
artistic style translation is an unpaired image-to-image translation, by
definition, it makes NST unfitting for the Pix-to-Pix GAN [7] model. Even
though StyleGAN [5] model is designed on an unpaired image-to-image
translation between two pixel spaces, it uses the same set of features to
generate the image from a separate pixel space.

In this paper, we explore GANs in the NST, where just as the StyleGAN model
generates an image with the mixture of both input image features. The proposed
model extracts style features from the style image and object features from
the content image and generates a new image with objects from the content
image painted in the style of the style image. For such a case, we propose a
GAN model that can be used for NST, which can support unpaired image-to-image
translation on independent input pixel spaces. Furthermore, the proposed model
extracts and generates a different latent space on both style and content
image, and the pixel space of the generated image differs from both input
images’ pixel spaces.

We introduce a new GAN architecture with two discriminative headers in the
first approach. In the second approach, we introduce an advancement to the
architecture of the first approach, which makes the training separate
parameter spaces for discriminators disappear. In the revealing network
architecture, the encoder sub-models in the generator work as the
discriminative headers in the training phase. In this model training process,
generator training and discriminator training optimize the same parameter
space.

Conditional adversarial network architecture has been extensively upgraded
over the past few years to support various image synthesis tasks in the
computer vision field. Even though there were improvements in CNN based NST
models such as [7, 5], they were based on CNN supervised learning as in [1].
The major contribution of this paper is to introduce a new cGAN architecture
where the discriminator and encoder sub model of the generator share the same
parameter space in the training time. The generator model has been made more
reliable and consistent in style transferring as in the CycleGAN paper [8]
introduced.

|  Svoboda [9] |  Gao [10] |  Chen [11] |  Gatys [1] |  Zhang [12] |  Appr. 1 |  Appr. 2
---|---|---|---|---|---|---|---
Semi-supervised learning |  $\surd$ |  $\surd$ |  |  |  $\surd$ |  $\surd$ |  $\surd$
does not require paired samples to train |  |  $\surd$ |  |  $\surd$ |  |  |  $\surd$
trained model support more than one style |  |  |  $\surd$ |  |  $\surd$ |  $\surd$ |  $\surd$
preserve original image color |  |  |  $\surd$ |  $\surd$ |  |  |  $\surd$
does not introduce alias artifact in generated image |  $\surd$ |  $\surd$ |  |  |  $\surd$ |  $\surd$ |  $\surd$
Table 1: Table of comparison

##  2 Related Studies

A neural style transfer paper [1] by Leon et al. first introduced the concept
of neural style transformation under image synthesis in the deep learning
based computer vision field in 2015. Since then, it has been prevalent in
research because of its mainstream appeal. In [5], the authors have introduced
an extension to the [1] to make the image synthesis process more efficient and
faster in the NST process. Also, the [7] color histogram matching algorithm
has been used on top of [1] model architecture to preserve the original light
condition in the input image.

In [9, 10, 12] they have used semi-supervised learning (GAN) to achieve more
controllability in the style transferring process, produce clear and detailed
images, and disentangled feature [9] from both content and style feature
spaces. However, as shown in the 1, most research studies in NST have been
conducted under the concept of a model per style.

Use of GAN [2, 13] in image synthesis, image super-resolution, image editing,
and representation learning is very popular. Google pix-to-pix translation [3]
paper has introduced a U-net based image to image translation model that was
trained with GAN. It showed impressive performance in semantic segmentation,
semantic labeling, map translation [aerial photo into graphics], edge and
boundary detection, and in image-to-image translation tasks such as thermal to
color translation. However, the pix-to-pix model could only have a single
input. This restricted the use of the pix-to-pix model for the style transfer
model. Additionally, the model requires to be fed with original and translated
images as a pair. However, it is not practical to generate transferred images
beforehand like in other image synthesis areas in style transfer. For example,
we can manually annotate and pair images in semantic segmentation. Jun-Yan Zhu
et al. [8], has introduced a consistent and well defined method for bijective
validation of image translation between two pixel spaces. In [8], they have
introduced image translation between two domains with unpaired initial
distributions.

In design, the CycleGAN model takes a single image input, making CycleGAN
unsuitable for direct use in style transferring. In 2019, StyleGAN model [5]
paper has introduced an effective model to combine features from two different
input images and generate a new image with features of input images. Since
that paper targeted synthesizing human faces, both images fed into the model
were human images. Therefore, they have proposed only a single encoder model
(Mapping Network) [5] for feature extraction. Furthermore, since features in
human faces were explicitly localized and acceptable network architecture for
global features like texture extraction differ from the Mapping Network
architecture.

The Wavelet Convolutional neural network model [14] has been proposed to
classify images based on texture features in wavelet representation. The input
image was first operated on a multi-resolution image decomposition method
called spectral analysis. However, since the wavelet transformation maps
pixels into a spectral space, it cannot be used for the generator’s
style/texture encoding model In [15, 16]. They have empirically proven that
convolutional models with residual connections can be used for texture
classification tasks. In [15] they have claimed that pre-trained CNN models on
ImageNet [6] dataset have the potential to recognize texture features as well
as the shapes such as clothes in complex images.

As a part of the style transfer process, we have to extract style/texture from
the style image. The style feature of an artwork is represented by different
factors such as the medium used to paint, the surface, and the artist’s
personality. The paper published by Yang Lia et al. [17] introduced the GAN-
based method to control the style ingrained on the aspect of the continuous
flow of color gradient to incorporate with brush stroke patterns in artworks.

##  3 System Model and Implementation

In the first approach, we propose a GAN model where the discriminator has two
parallel headers to independently generate adversarial results on content and
style. In the same approach, we synthesize the training image dataset by using
the NST [5] model to generate paired style transfer images. We advance the
cGAN model architecture and the training process for the model to understand
the class related to the style image and extract core features from the
content model. Then the model imposes general features of the identified style
class to the generated image. Specifically, using the second method, we can
generate images that are not affected by alias feature presence like in Fig.
1.

Since the style encoding submodule is optimized under the metrics learning
objective function for image similarity search, given that the model is
trained under a higher variation of style classes [18], the trained model will
support any art style irrespective of the style presence in the training time.
For the approach one training, we synthesize a dataset in the form of an image
matrix. In the matrix, every column denotes a content image from the Multi-
Salient-Object (MSO) dataset [19]. All other columns contain style transfer
images of content images from MSO related to the row and style related to the
particular column.

###  3.1 Approach #1 : GAN with dual headed discriminator

One of the Foundation work for this approach has been done by the pix-to-pix
paper [3], as a cross domain image transformation model with great qualitative
and qualitative accuracy in the generated images. However, the architecture’s
nature is not directly compatible with the NST for two reasons. The first
reason is that the GAN architecture must support two images as the inputs, and
the second reason is that the NST is an unpaired image to image transformation
in contrast to the pix-to-pix model.

####  3.1.1 Objective of approach #1

the cGANs [6] generator learns a mapping from the input image domain $x$ &
noise vector $z$ to paired image domain $y$, $G:\\{x,z\\}\xrightarrow{}y$, to
produce ”real” images. While the discriminator $D$ learns to distinguish
”real” images from ”fake” images generated by the generator $G$.

The objective of cGAN can be expressed as.

$\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D})=\\\
\mathbb{E}_{x,y}[\log(\mathcal{D}(x,y))]\ +\
\mathbb{E}_{x,y}[\log(1-\mathcal{D}(x,\mathcal{G}(x,z)))]$ (1)

Here, the generator $G$ tries to minimize this objective against the
adversarial discriminator $D$ tries to maximize the adversarial loss.
i.e.
$\mathcal{G}^{*}=\arg\min_{\mathcal{G}}\max_{\mathcal{D}}\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D})$
The proposing model has two distinct discriminators against one generator, and
here onward we use rGAN as the short form for this proposing model. Each
discriminator trains separately. Weighted sum of adversarial loss defines as
the objective of rGAN can express as;

$\mathcal{L}_{rGAN}(\mathcal{G},\mathcal{D}_{s},\mathcal{D}_{c})=\\\
\alpha.\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D}_{s})\ +\
(1-\alpha).\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D}_{c})$ (2)

As stated in the [3] we added $L$1 loss for perceptual clarity of the
generating image. Thus, the final objective is,

$\mathcal{G}^{*}=\arg\min_{\mathcal{G}}\max_{\mathcal{D}_{s}}\max_{\mathcal{D}_{c}}\mathcal{L}_{rGAN}(\mathcal{G},\mathcal{D}_{s},\mathcal{D}_{c})\
+\ \lambda.\mathcal{L}_{l1}(\mathcal{G})$ (3)

A pairwise marginal ranking loss used for the objective function in the
content to assess synthesis image quality [20] of generated images.

####  3.1.2 Network Architecture of approach #1

The skeleton of the GAN model is adopted from the paper [3] with an added
style discriminator header and channels in the encoder to support the style
image. Generator and Content discriminator use standard convolutional modules
[Conv $\xrightarrow{}$ Batchnorm$\xrightarrow{}$ ReLU]. However, the style
discriminator is designed by the wavelet convolution neural network. The
complete training procedure diagrammed in Fig. 2

Fig. 2: The GAN architecture of approach #1.

#####  Generator with skip connection -

The generator model aims to extract object features from the content image and
local-global fused features from the style image. Subsequently, those features
are encoded from the input images’ pixel space into bottleneck layers’ latent
vector space. The decoder model reconstructs the style transferred image up to
the same size as the input. The bottleneck vector size is set to 64 as defined
in [21].

Apart from the two inputs taken by the encoder model, the generator
architecture is a U-Net architecture [22]. Since the U-Net allows information
sharing from low level features of the encoder at the image reconstruction
step, it gives a chance to fuse low level features related to the texture of
the style image. Furthermore, As in the [3] states, U-net residual
architecture supports reducing blurriness in the generated image.

#####  Markovian discriminator [content discriminator] -

The exact discriminator designed in [3] is used due to several reasons. Since
generated images are mixed with style image features, it is crucial to ensure
that local image patches are real. PatchGAN [3] penalizing structure at the
scale of patches ensures the content image is not embedded with alias
artifacts, further allowing the generation of a more semantically accurate
image. The discriminator considers the image a Markov random field with plate
per patch. Therefore, it indirectly supports having original colors in the
generated image because each patch is considered independent from surrounding
patches.

#####  wavelet CNN discriminator [style discriminator] -

Theoretically, the style of an image cannot be successfully captured by a
sequential CNN model because CNN targets capturing local features and
transforming those features until it reaches a complexity that the fully
connected layer will support. As stated in [15, 23], even a CNN model with a
feature fusion like residual CNN [24], the inception model [25] can be used
for texture extraction tasks. The wavelet convolution neural networks begin
with the wavelet transformation layer, which decomposes pixel space into
spectral space in several resolutions using frequency statistics. Then in the
Convolutional Neural Network potion, we down-sample different resolution
results from the wavelet layer with channel-wise adding. In essence, this
model acts as a global-local feature fusion to extract style from the images.

The paper [14] introduced a state-of-the-art texture extraction architecture
based on the wavelet transformation. The style discriminator header is
implemented using wavelet CNN in this approach. Using this model in the
generator as a style encoder header adds unexpected hues into the generated
image and partitions the generated image by light black stripes. We stipulate
that features cause these behaviors in the CNN followed by a wavelet
transformation layer in spectral space.

####  3.1.3 Optimization and inference

As suggested in the original GAN [2] we alternate training between generator
model and discriminator model to get the generator to converge into a point
where loss is minimized, and discriminators damps on equilibrium level.
Instead of feed forwarding real and fake sample sets separately over the
discriminator’s heads, with the motive of achieving a more robust gradient
descent, we concatenate real and fake sample sets and feed them into the
discriminator after a shuffling. More robust gradient descent can be achieved
using this approach because, in the previous method, parameters of Batch
Normalization layers radically changed due to real and fake sample twist
feeding, but in this approach, batch normalization layers will be in a more
stabilized position.

We used a non-reference loss function - L1 norm as the image reconstruction
loss in the generative model, mainly because the L1 loss preserves color &
luminance and equally weights the loss regardless of local structure.
Furthermore, L1-loss does not penalize pixel value difference thoroughly.
Therefore, it gives a chance to add style image color variations and features
on the content image. We have also experimented on a reference loss function
called multi-scale structural similarity index (SSIM) [26], which is sensitive
to local structure. Also experimented using the MixLoss function [27] which is
a weighted combination of SSIM and L1 losses as the reconstruction loss.
However, the generated images in both experiments gave unexpected hues and
noise.

In the content discriminator header, we have used binary cross-entropy loss as
suggested in [3]. We used an instance normalization layer instead of batch
normalization for a more robust and smooth training curve in the style
discriminator header. For the style loss function, we have implemented a
slightly modified version of the pairwise marginal loss function [28] to
support both positive and negative pairs at the same time.

Since the objective of the GAN base of paired image transformation, we have
used it as stated in Method for model training. From that image matrix, we
synthesize the training dataset in the form of triplets; [content image, style
image, style transfer image]. We fed the batched dataset into the model
training pipeline.

###  3.2 Approach #2 : GAN with discriminatory encoder sub models

Fig. 3: The GAN architecture of approach #2.

Approach #1 targeted designing a model that can transfer images into more than
one style. Therefore, to support a new style, we had to train a new CNN-based
NST model such as the fast style transfer [5] model on a chosen set of styles.
The style transfer images from the trained model on content images will be
composed into an image matrix in the approach #1. After that, the GAN in
approach #1 will be trained on the composed image matrix with randomized image
augmentations on the pre-processing pipeline. Therefore, even if the model
generates semantically accurate style transfer images on several styles, the
complicated process of training the model for a new style is a downside of the
approach #1.

Also, in the paper [1] the original image color palette remains consistent
because the model proposed by Approach #1 still learns style from a single
image, and it restricts the color palette of the generated image. As we
discussed, making a style represented by a single image, in reality, is not
accurate and could introduce many unnecessary features into the generated
image. For example, in Fig. 1, (third image) generated image embeds many alias
artifacts such as the presence of waves instead of blurred background in the
reference image (second image) and curly sprinkles like features in bird
feathers. Furthermore, the fourth image in Fig. 1 shows a scene of a bird with
leaves, and that image significantly differs from the generated image (third
image). The generated image has embedded a blueish color palette like in the
style image (first image of Fig. 1) of the model. Both [1] and the proposed
GAN model generates images that show the style image feature in the generated
image.

Besides the ample parameter space in the generative model, a discriminator
model with a large parameter space degrades the gradient flow in the training
phase. As a result of this ample parameter space [order of $10^{5}$], training
the model to get at least moderate results requires a relatively large data
set [order of $10^{4}$]. Also, it is hard to expect to converge the generative
model into an optimal point while the discriminator oscillates over the proper
equilibrium level. Because adversarial loss employs to assess the generated
samples against “real” samples, it is hard to guarantee that the generator
learns for optimal transformation operation without collapsing. Further
defining evaluation metrics on image reconstruction for style transfer is even
more challenging. Also, evaluating model training by a metrics function does
not always guarantee model learning. All the facts above indicate that using
conventional ways to build a model that understands style transfer on unpaired
data is not an accurate and reliable method.

In this approach, we are going to introduce a new model training process as
the solution. The starting point is to drop the concept of training separate
discriminator models. In this approach, the discriminator is not fed with fake
samples as in GAN training. In this approach, we define two separate encoder
models for content feature extraction and style feature extraction. As shown
in Fig. 3, we fed extracted features into the decoder to generate style
transfer images. After that, we use two encoder models in the discriminator to
generate an adversarial loss.

####  3.2.1 Objective of approach #2

Even though we have adopted cGAN in this approach, the training phase will not
be the same as in cGAN training. In this approach both generator and
discriminator trains to minimize the objective, basically because the
discriminator is a part of the generator. The objective function of $rGAN$ can
express as;

$\mathcal{L}_{rGAN}(\mathcal{G},\mathcal{D}_{s},\mathcal{D}_{c})=\\\
\alpha.\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D}_{s})\ +\
(1-\alpha).\mathcal{L}_{cGAN}(\mathcal{G},\mathcal{D}_{c})$ (4)

same as in the Approach #1, but the final Objective 4 is different from 2.

$\mathcal{G}^{*}=\arg\min_{\mathcal{G}}\min_{\mathcal{D}_{s}}\min_{\mathcal{D}_{c}}\mathcal{L}_{rGAN}(\mathcal{G},\mathcal{D}_{s},\mathcal{D}_{c})\
+\ \lambda.\mathcal{L}_{l1}(\mathcal{G})$ (5)

As in [8], the objective is defined to validate that the transformation is
learned by the rGAN. Since here we are using the same encoder models in the
discriminator, it will validate the whole training process. Because, in the
first step, encoder models train as a discriminator model to minimize loss of
feature extraction. Then, in the second step, use those encoder models in the
generator model to adversarial train the decoder with encoders to minimize
adversarial loss. Those two steps repeat over the data set as same as in the
cGAN training.

Especially, in the discriminator training process we do not feed ”fake”
samples as in cGAN training. This is because encoders are supposed to train in
a way they generate optimal latent vectors instead of classification. In this
architecture both discriminator models output encoding vectors as they are
used in the generator. We used the pairwise marginal loss function for the
objective of the content encoder training in the discriminator. Style encoder
trained under metrics learning objective for image similarity search.

$H_{i,k}\ =\ \frac{1}{\gamma}.\sum_{j}xa_{i,j}.xs_{j,k}$ (6)

$\mathcal{L}(xa,xs,ys)\ =\ -\sum_{i}ys_{i}.\log(H_{i})$ (7)

In above equations 6 & 7, $xa$, $xs$ and $ys$ denote anchor sample batch,
style sample batch and style label vector respectively. $\gamma$ used for
regularizing constant in Gram metrics. Use the Gram metrics in 6 for sparse
categorical cross-entropy in 7.

In essence, encoder models are trained to generate optimal features while the
generator model is trained to generate images that minimize weighted sum of
content, style and l1 loss as shown in the equation 5 by using trained
encoders.

####  3.2.2 Network architecture of approach #2

The entire network consists of mainly three parameter spaces called a content
encoder, style encoder, and decoder, as shown in Fig. 3. Content encoder and
style encoder outputs latent vectors of content image and style image,
respectively. The decoder uses those encoded features in the generative model
to generate style transfer images. The discriminative model uses the content
encoder and style encoder to generate adversarial losses to train.

#####  Content encoder -

Content encoders take an image and output an encoded latent vector [of length
32]. An encoder is created by a set of sequential modules in the form of [Conv
$\xrightarrow{}$ Batchnorm$\xrightarrow{}$ ReLU]. The content encoder is
trained on pairwise marginal loss in the training process. As an adoption
model of StyleGAN [5] synthesis network here, we do not directly feed encoded
features over the bottleneck to the decoder model. Instead, we feed features
using skip connections from the content encoding models intermediate CNN
modules to intermediate up-sampling CNN modules in the decoding model.

In the training process, the content encoder is trained in the way a face-
recognition model is being trained [21]. Instead of using triplet loss [28],
here we are using the sum of pairwise marginal loss on the positive sample and
negative sample in each training step. The content discriminator is fed by
random sample pairs in the training process, where positive and negative pairs
are randomly generated in a way each has a 0.5 probability. Also, instead of
using semi-hard ranking loss functions like triplet loss, hard ranking loss
functions, namely the pairwise marginal loss function in the discriminator
make the gradient descent more robust. As stated above, we can guarantee that
the content encoder model is trained to do expected tasks because the same
encoder model is trained on content encoding vector classification by using a
ranking loss function in the discriminator training step. Furthermore, we have
assessed the accuracy of the content discriminator network and objective
function on a separate data set.

Fig. 4: Approach #1 GAN model evaluation image matrix.

#####  Style encoder -

The major concern here is that encoder vectors must show locational proximity
to indicate semantic similarity in the original style when transformed into
UMAP, PCA base encoded vector spaces. For example, the pencil drawing’s
encoder vector position in point cloud must have proximity to a pencil sketch
image rather than an oil painting. In essence, the style encoder is trained to
yield approximately similar encoding vectors for similar style images. The
task appears to be like embedding a vector training process but defining an
objective function to train and using that in an adversarial loss function
causes many issues. Also, the use of classification objective function to
train is not accurate in theory and empirically. As stated in CycleGAN paper
[8] “building $y$, $G:x\xrightarrow{}y$, mapping does not guarantee that an
individual input x and an output y are paired up in a meaningful way- there
are infinitely many mappings $G$”. On the other hand, a design objective as a
dictionary [29] learning is not practically possible due to the complexity of
the parameter space and scale. Because manipulating dictionary metrics in
training and inference stages is computationally costly [30].

The idea is to build an embedding vector training process without explicitly
using an embedding vector. As well as the model architecture must support
proper discriminative loss function to be trained in the adversarial phase.

The concept of metrics learning in deep learning [6] for similarity search is
the optimal way to train Because, in theory, such a model uses sparse
categorical cross-entropy as the objective function. As stated in the
objective section, this objective makes encoding vector distribution estimates
for each class so that their negative log-likelihood is as minimal as
possible. In essence, this makes encoding vectors of the same class drop under
the same distribution and achieve distribution clustering by preserving
proximity.

As stated in Deep-TEN [16] CNN models with residual connection from low level
feature layers to high level feature layers are suitable for tasks like
material and texture extraction. In [16] they have empirically proven this
point by using the ResNet model to classify garments based on texture.
However, the DensNet [31] model is a perfect candidate for this because it
concatenates all features in previous modules, in the current module, and the
transition layer is weighted between different layers to generate more complex
features than features generated by ResNet [24] on a particular resolution.
This makes the model have a much stronger gradient flow. Also, in [31] the
width of the layer being proportional to the growth rate makes the feature
extractor of the style encoder have to have a much smaller parameter space.

#####  Generator -

Generator models are mainly a combination of content encoder, style encoder
and decoder. Here the decoder model is a sequential set of up-sampling CNN
modules like the U-Net with skip connection to content encoder sub-model. The
network architecture is inspired by the StyleGAN [5] synthesis network.
Instead of using a single mapping network [5] to generate features from the
inputs here we implement two separate encoder models as shown in Fig. 3.

The decoder sub-model in the generator starts from the latent vector space
generated only by the style encoder. The generator model is fed by the low-
level feature from the content encoder using skip connection. The targethere
is to make decoder sensitivity style encoded high-level features while using
low-level features to generate content on the image. Therefore, the final
image will not be affected by the exact shapes and colors of the content image
and what objects are present in the style image.

Fig. 5: Approach #2 GAN model evaluation image matrix.

##  4 Model Evaluation

###  4.1 Results of approach #1

Despite having two discriminative models the discriminator in total and
individually tended to converge into an equilibrium point in the training as
we experimented. Furthermore, the generator shows less variety than the CNN-
based NST model in loss, especially l2 loss in experiment results.

The resulting generated images tend to have a much higher resemblance to the
respective art style compared to the CNN-based NST model, as illustrated,
especially in the third and fourth rows of Fig. 4. Especially in generated
images, the presence of content color palette dropping is insignificant.
Furthermore, the introduction of new artifacts to generated images are not
prominent with the new model.

###  4.2 Results of approach #2

For the GAN training process we used two separate datasets for style images
and content images as stated in the method section. The complete adversarial
training process on style discriminator, content discriminator and the
generator converge to an optimal point by minimizing loss function related to
each instead of the discriminative loss oscillating over equilibrium level.
Also, generative loss and content encoder loss happened to have smooth loss
graphs relative to the style encoder. Here in a batch the presence of class is
not uniformly distributed.

Even Though we had adopted the matrix learning to calculate the model loss,
the sample set does not always contain samples from each class in the same
order. Under this method the model overfitting and tendency to model
collapsing reduce significantly than the orders static sampling method.

The generated images have not changed radically like in [9] model inference,
but the generated images are imposed with texture and some color effect from
the style image as illustrated in Fig. 5. As proposed, the model is supposed
to generate an image which will appear as done by the same artist rather than
seeming to have all features from a given style image. Considering the above
mentioned point, the model we introduce does a quite good job in understanding
style image texture and imposing that on the content image without introducing
extrinsic features from style image as artifacts. The slight amount of noise
and blur represented in generated images is due to the downscaling of input
images.

##  5 Discussion

###  5.1 Lessons Learned

In the first approach, we have mainly targeted building a GAN for NST that
supports more than one style. The generating image shows significantly less
content color palette changes than the CNN base NST models because of the
adversarial training. Texture discontinuity and blurriness of the generated
image were significantly affected by the severe downsampling of the images’
pixel space because the downsampling operation could drop interpixel
correlations present in the pixel space.

From the second approach results, we can specify that the style extraction by
using metric learning emphasizes general features for a style class.
Consequently, the generated images have texture and similar semantic
appearance features from the style image. On the other hand, the generated
image will not have striking features such as rapid contract change and sharp
edge as in the reference style image because of style normalization, in a
broader sense.

In this paper we introduce a comprehensive architecture for the GAN which has
two parallel discriminator headers and generators that takes 6 channel tensor
inputs. Because this model has a larger parameter space than the general GAN
model, the training process is slower than average, but the inference time has
not changed significantly. On the other hand, the model proposed in the second
approach has even less parameter space than the general GAN model. However,
training the encoder model parameter set sharing between generator and
discriminator caused an increase in the expected return time. Although, the
inference is much faster than approach #1 due to the smaller model size and
fewer FLOPS.

###  5.2 Open Challenges and Future Research Directions

The model proposed in approach #2 is not capable of clearly introducing
striking features such as outline markings and rapid color gradient patches
into the generated image even though they appear in the style image. Hence,
the proposed model is only fine-tuned on very low-resolution images (128, 128,
3), where the severe downscaling of input images caused edges of the images to
blur and be discontinued. Therefore, input images being in very low resolution
could cause the issue of not introducing striking features.

The target sensor replacement method introduced in [32] paper is trained in
the Eigenspace of the related pixel space. It ensures that the decoder is fed
with essential details about style in the bottleneck layer. Also, we can have
more control over the latent space, implying that we can build a model that
controls the style transfer [12, 33] under rGAN architecture. Building
Multimodal architecture that serves like the model introduced in this paper
and with aleatoric uncertainty of generating image would be like variational
autoencoder [34] among autoencoders [22].

##  6 Conclusion

In this paper, we introduced two novel semi-supervised learning approaches of
neural artistic style transformation. The first approach used a GAN-based
style transfer model capable of transferring images into more than one style.
In the second approach, we introduced neural style transfer that understands
how an actual artist would paint a given image in his style. The adversarial
network and adversarial training process introduced in the second approach
would be applicable to many ambiguous tasks and train on a lower parameter
space than the conventional GAN model.

## Acknowledgment

We thank L.T.N. Wickremasinghe, T.T. Jayasekera and P.G. Amanda for the
support on this project.

## References

  * Gatys et al. [2016] L.A. Gatys, A.S. Ecker, M. Bethge,  Image style transfer using convolutional neural networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2414–2423.
  * Goodfellow et al. [2020] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio,  Generative adversarial networks,  Communications of the ACM 63 (2020) 139–144.
  * Isola et al. [2017] P. Isola, J.Y. Zhu, T. Zhou, A.A. Efros,  Image-to-image translation with conditional adversarial networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 1125–1134.
  * Kang and Park [2020] M. Kang, J. Park,  Contragan: Contrastive learning for conditional image generation,  arXiv preprint arXiv:2006.12681 (2020).
  * Karras et al. [2019] T. Karras, S. Laine, T. Aila,  A style-based generator architecture for generative adversarial networks,  in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 4401–4410.
  * Zhao and Huang [2018] G. Zhao, J. Huang,  Deepsim: deep learning code functional similarity,  in: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2018, pp. 141–151.
  * Gatys et al. [2016] L.A. Gatys, M. Bethge, A. Hertzmann, E. Shechtman,  Preserving color in neural artistic style transfer,  arXiv preprint arXiv:1606.05897 (2016).
  * Zhu et al. [2017] J.Y. Zhu, T. Park, P. Isola, A.A. Efros,  Unpaired image-to-image translation using cycle-consistent adversarial networks,  in: Proceedings of the IEEE international conference on computer vision, 2017, pp. 2223–2232.
  * Svoboda et al. [2020] J. Svoboda, A. Anoosheh, C. Osendorfer, J. Masci,  Two-stage peer-regularized feature recombination for arbitrary image style transfer,  in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 13816–13825.
  * Gao et al. [2020] X. Gao, Y. Tian, Z. Qi,  Rpd-gan: Learning to draw realistic paintings with generative adversarial network,  IEEE Transactions on Image Processing 29 (2020) 8706–8720.
  * Chen and Schmidt [2016] T.Q. Chen, M. Schmidt,  Fast patch-based style transfer of arbitrary style,  arXiv preprint arXiv:1612.04337 (2016).
  * Zhang et al. [2017] L. Zhang, Y. Ji, X. Lin, C. Liu,  Style transfer for anime sketches with enhanced residual u-net and auxiliary classifier gan,  in: 2017 4th IAPR Asian Conference on Pattern Recognition (ACPR), IEEE, 2017, pp. 506–511.
  * Shao and Wang [2021] H. Shao, Y. Wang,  Generative image inpainting with salient prior and relative total variation,  Journal of Visual Communication and Image Representation 79 (2021) 103231\.
  * Liu et al. [2019] P. Liu, H. Zhang, W. Lian, W. Zuo,  Multi-level wavelet convolutional neural networks,  IEEE Access 7 (2019) 74973–74985.
  * Zhang et al. [2020] Y. Zhang, P. Zhang, C. Yuan, Z. Wang,  Texture and shape biased two-stream networks for clothing classification and attribute recognition,  in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 13538–13547.
  * Zhang et al. [2017] H. Zhang, J. Xue, K. Dana,  Deep ten: Texture encoding network,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 708–717.
  * Jing et al. [2018] Y. Jing, Y. Liu, Y. Yang, Z. Feng, Y. Yu, D. Tao, M. Song,  Stroke controllable fast style transfer with adaptive receptive fields,  in: Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 238–254.
  * Lcaro [2021] Lcaro,  Best artworks of all time kaggle dataset ((accessed: 31.07.2021)).
  * Li [2021] J. Li,  Multi-salient-object kaggle dataset ((accessed: 31.07.2021)).
  * Meng et al. [2021] X. Meng, W. Ma, C. Li, Q. Mi,  Siamese cnn-based rank learning for quality assessment of inpainted images,  Journal of Visual Communication and Image Representation 78 (2021) 103176\.
  * Schroff et al. [2015] F. Schroff, D. Kalenichenko, J. Philbin,  Facenet: A unified embedding for face recognition and clustering,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2015, pp. 815–823.
  * Ronneberger et al. [2015] O. Ronneberger, P. Fischer, T. Brox,  U-net: Convolutional networks for biomedical image segmentation,  in: International Conference on Medical image computing and computer-assisted intervention, Springer, 2015, pp. 234–241.
  * Chen et al. [2021] C. Chen, H. Zhao, H. Yang, T. Yu, C. Peng, H. Qin,  Full-reference screen content image quality assessment by fusing multilevel structure similarity 17 (2021).
  * He et al. [2016] K. He, X. Zhang, S. Ren, J. Sun,  Deep residual learning for image recognition,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * Szegedy et al. [2015] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich,  Going deeper with convolutions,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2015, pp. 1–9.
  * Wang et al. [2003] Z. Wang, E.P. Simoncelli, A.C. Bovik,  Multiscale structural similarity for image quality assessment,  in: The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, 2003, volume 2, Ieee, 2003, pp. 1398–1402.
  * Zhao et al. [2016] H. Zhao, O. Gallo, I. Frosio, J. Kautz,  Loss functions for image restoration with neural networks,  IEEE Transactions on computational imaging 3 (2016) 47–57.
  * Wang et al. [2019] X. Wang, Y. Hua, E. Kodirov, G. Hu, R. Garnier, N.M. Robertson,  Ranked list loss for deep metric learning,  in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 5207–5216.
  * Chang et al. [2021] Y. Chang, S. Li, A. Liu, J. Jin,  Quality assessment of screen content images based on multi-stage dictionary learning,  Journal of Visual Communication and Image Representation (2021) 103248.
  * Le Magoarou and Gribonval [2015] L. Le Magoarou, R. Gribonval,  Chasing butterflies: In search of efficient dictionaries,  in: 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2015, pp. 3287–3291.
  * Huang et al. [2017] G. Huang, Z. Liu, L. Van Der Maaten, K.Q. Weinberger,  Densely connected convolutional networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 4700–4708.
  * Brunton et al. [2016] B.W. Brunton, S.L. Brunton, J.L. Proctor, J.N. Kutz,  Sparse sensor placement optimization for classification,  SIAM Journal on Applied Mathematics 76 (2016) 2099–2122.
  * He et al. [2019] Z. He, W. Zuo, M. Kan, S. Shan, X. Chen,  Attgan: Facial attribute editing by only changing what you want,  IEEE Transactions on Image Processing 28 (2019) 5464–5478.
  * Pu et al. [2016] Y. Pu, Z. Gan, R. Henao, X. Yuan, C. Li, A. Stevens, L. Carin,  Variational autoencoder for deep learning of images, labels and captions,  Advances in neural information processing systems 29 (2016) 2352–2360.


# Alternative Proof of the Determinant of Complete Non-Ambiguous Trees

D Chen

###### Abstract.

Complete non-ambiguous trees have been studied in various contexts. Recently,
a conjecture was made about their determinants, and subsequently proved by
Aval. An alternative proof is given here.

##  1\. Introduction

Complete non-ambiguous trees (CNATs) are a combinatorial object of recent
interest [ABBS14]. They may be seen as the proper way to embed a complete
binary tree into a grid (see 2.1). Recently, a study of these objects was
launched in [CO24], in which a conjecture was made that the determinant is
evenly distributed for odd-size CNATs. This was subsequently proved
bijectively in [Ava23].

In this short article, first some self-contained context to the problem is
given by stating the background definitions and conjecture. Then an
alternative proof is given.

##  2\. Definitions

The definition of a (complete) non-ambiguous tree is recalled from [ABBS14] as
follows:

######  Definition 2.1.

A _non-ambiguous tree_ is a filling of a rectangular grid in which each cell
may or may not contain a dot, such that the following constraints are
satisfied:

  * (Existence of a root) The top-left cell (the _root_) is dotted.

  * (Non-ambiguity) For every dotted cell (_vertex_) other than the root, there is another vertex either in the same column and above, or in the same row and to the left, but not both.

  * (Minimality) Every row and column contains at least one vertex.

By connecting each vertex to its unique precursor in the same row or column, a
rooted binary tree is formed, thus motivating the name _non-ambiguous tree_.
If the underlying binary tree is complete, then the object is referred to as a
_complete non-ambiguous tree_ (CNAT).

This implies that a CNAT with $2n-1$ vertices has $n$ leaves and $n-1$
internal vertices. Furthermore, every row and column has exactly one leaf,
thus a CNAT with $2n-1$ vertices is contained in an $n\times n$ grid. We refer
to the CNAT as having size $n$, or dimensions $n\times n$.

Figure 2.1. A 4x4 CNAT with leaf vertices highlighted in blue

######  Definition 2.2 (Leaf Matrices).

A given CNAT, $M$, can be viewed as a square matrix by setting dotted cells to
1 and empty cells to 0. The _leaf matrix_ of $M$ is the matrix obtained when
setting leaf vertices to 1, and all other cells to 0.

Since there is exactly one leaf in every row and column, a leaf matrix is
always a permutation matrix, and thus has determinant $\pm 1$. In fact, it was
proved in Proposition 2.5 of [CO24] that the determinant of any CNAT is equal
to the determinant of its leaf matrix.

##  3\. Statement of the conjecture

Given the preliminary definitions, we may now study the number of CNATs with
determinant 1 and -1. Define these to be $A_{n}$ and $B_{n}$ respectively.
Their sum is the total number of CNATs of a given size, $T_{n}$. Also define
the _defect_ , $D_{n}=A_{n}-B_{n}$.

The numbers $T_{n}$ are well known, and Proposition 9 of [ABBS14] gives a
recurrence for them:

$T_{n}=\sum_{k=1}^{n-1}{n-1\choose k-1}{n-1\choose k}T_{k}T_{n-k}$

Now, we may see the following computed data for $A_{n}$ and $B_{n}$.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
# with det 1, $A_{n}$ | 1 | 0 | 2 | 17 | 228 | 4728 | 137400 | 5321889
# with det -1, $B_{n}$ | 0 | 1 | 2 | 16 | 228 | 4732 | 137400 | 5321856
$T_{n}=A_{n}+B_{n}$ | 1 | 1 | 4 | 33 | 456 | 9460 | 274800 | 10643745
$D_{n}=A_{n}-B_{n}$ | 1 | -1 | 0 | 1 | 0 | -4 | 0 | 33

From the table, the determinant seems to be evenly distributed for odd $n$;
furthermore for even $n$ the defect $D_{n}$ seems to be an alternating version
of $T_{n}$. Indeed, this is the conjecture put forward by [CO24]:

$A_{n}-B_{n}=\begin{cases}1&\text{if }n=1\\\ 0&\text{if }n>1\text{ is odd}\\\
(-1)^{n/2}T_{n/2}&\text{if \begin{math}n\end{math} even}\end{cases}$

In particular, since $A_{n}+B_{n}=T_{n}$ gives two simultaneous equations, it
would imply that number of CNATs with determinants 1 and -1 can be written in
terms of the sequence $T$.

##  4\. Proof

Finally, an inductive proof of the conjecture is given.

######  Definition 4.1.

For convenience, let $e^{n}_{k}$ be the number of $k$-subsets of
$\\{1,\dots,n\\}$ with an even sum. Similarly define $o^{n}_{k}$ for the
number of subsets with odd sum.

######  Proposition 4.2.

$\forall n\geq 2$,

$\begin{split}A_{n}=\sum_{k=1}^{n-1}&\left(A_{k}A_{n-k}+B_{k}B_{n-k})(e^{n-1}_{k-1}e^{n-1}_{k}+o^{n-1}_{k-1}o^{n-1}_{k}\right)\\\
&+\left(A_{k}B_{n-k}+B_{k}A_{n-k})(e^{n-1}_{k-1}o^{n-1}_{k}+o^{n-1}_{k-1}e^{n-1}_{k}\right)\end{split}$

###### Proof.

Proposition 9 of [ABBS14] establishes a recurrence for $T_{n}$, derived by
removing the root node of the CNAT to obtain two smaller CNATs. Let us extend
their proof to formulate recurrences for $A_{n}$ and $B_{n}$.

By removing the root node of a CNAT, we obtain two smaller CNATs after
flattening, whose rows and columns are interweaved together. Also, one
contains all non-root vertices in the top row, and the other contains all non-
root vertices in the leftmost column. Hence to construct a CNAT $T$ of size
$n$ with determinant 1, we need to choose:

  1. (1)

The size of the smaller CNAT, say $M$, that contains the top row. Call this
size $k$ ($1\leq k\leq n-1$). The other smaller CNAT, say $M^{\prime}$,
contains the leftmost column and has size $n-k$.

  2. (2)

The structures of both smaller CNATs. We can choose any combination of the two
determinants, so long as in the next step we interweave the rows and columns
so that the determinant is 1. We consider two cases; if $\det M\det
M^{\prime}=1$ then there are $A_{k}A_{n-k}+B_{k}B_{n-k}$ ways since the
determinants are both even or both odd, and similarly if $\det M\det
M^{\prime}=-1$ then there are $A_{k}B_{n-k}+B_{k}A_{n-k}$ ways.

  3. (3)

A way of interweaving the rows and columns so that the determinant becomes (or
stays) 1. For this, we separately choose the rows of $M$ out of the rows of
$T$, and then the columns. For the rows, since $M$ must contain the top row,
we have $k-1$ out of $n-1$ rows left to pick. For the columns, $M$ cannot
contain the leftmost column because $M^{\prime}$ does, so we have $k$ columns
to pick out of $n-1$.

Now, we must pick the rows and columns so that the determinant is 1. Given a
valid such choice, we may perform a sequence of swaps of adjacent rows or
columns to turn it into a block diagonal matrix whose submatrices are $M$ and
$M^{\prime}$ (so that $M$ is contained in the first $k$ rows and first $k$
columns; $T$ need not still be a CNAT). The determinant of this block diagonal
matrix will be $\det M\det M^{\prime}$. Note that we are only allowed to
perform _adjacent_ swaps because the rows and columns in $M$ and $M^{\prime}$
must stay in the same order. Each of these swaps will flip the sum of chosen
rows and columns mod 2, and will also flip the determinant of $T$. Hence if
$\det M\det M^{\prime}$ is 1 then the valid choices of rows and columns are
precisely those where the sum of the rows and columns is congruent to
$(1+\dots+k)+(1+\dots+k)\equiv 0$ mod 2. Thus there are
$e^{n-1}_{k-1}e^{n-1}_{k}+o^{n-1}_{k-1}o^{n-1}_{k}$ ways, because the sum of
rows and sum of columns must both be odd, or both be even. Similarly if $\det
M\det M^{\prime}$ is -1 then there are
$e^{n-1}_{k-1}o^{n-1}_{k}+o^{n-1}_{k-1}e^{n-1}_{k}$ ways.

Summing the number of ways for each possibility of $\det M\det M^{\prime}$,
then summing over $k$, the result follows. ∎

######  Lemma 4.3.

$\begin{split}D_{n}=\sum_{k=1}^{n-1}&D_{k}D_{n-k}(e^{n-1}_{k-1}-o^{n-1}_{k-1})(e^{n-1}_{k}-o^{n-1}_{k})\end{split}$

###### Proof.

First note that $\forall n\geq 2$, the following formula holds:

$\begin{split}B_{n}=\sum_{k=1}^{n-1}&\left(A_{k}B_{n-k}+B_{k}A_{n-k})(e^{n-1}_{k-1}e^{n-1}_{k}+o^{n-1}_{k-1}o^{n-1}_{k}\right)\\\
&+\left(A_{k}A_{n-k}+B_{k}B_{n-k})(e^{n-1}_{k-1}o^{n-1}_{k}+o^{n-1}_{k-1}e^{n-1}_{k}\right)\end{split}$

This can be seen in an identical way to the proof of 4.2, except in step 3
where we now wish to interweave the rows and columns so that the resulting
determinant is -1.

Now, subtract this expression for $B_{n}$ from the expression for $A_{n}$ in
4.2. The resulting equation factorises, and then occurrences of $A-B$ may be
replaced with $D$. ∎

######  Lemma 4.4.

$\forall n\in\mathbb{N},k\in\mathbb{Z}$ with $0\leq k\leq n-1$:

$e^{2n-1}_{2k}-o^{2n-1}_{2k}=(-1)^{k}{n-1\choose k}$
$e^{2n-1}_{2k+1}-o^{2n-1}_{2k+1}=(-1)^{k+1}{n-1\choose k}$

###### Proof.

Consider the group action of $C_{2}^{k}$ on subsets of ${1,\dots,2n-1}$, with
generators switching $1\leftrightarrow 2,3\leftrightarrow
4,\dots,2n-3\leftrightarrow 2n-2$. If for some pair $(2t-1,2t)$ only one of
them is in a subset, then the orbit of that subset has equally many subsets
with even and odd sum because switching $2t-1\leftrightarrow 2t$ changes the
parity of the sum. The subsets left over are those in which both $2t-1$ and
$2t$ are in the subset, or neither. Note that once we have chosen these pairs,
there is no choice in whether to pick $2n-1$, because we must match the parity
of the total number of items chosen. Thus there are ${n-1\choose k}$ of the
leftover subsets, and their sums all have the same parity. The factor of
$(-1)^{k}$ follows. ∎

######  Theorem 4.5.

$D_{n}=A_{n}-B_{n}=\begin{cases}1&\text{if }n=1\\\ 0&\text{if }n>1\text{ is
odd}\\\ (-1)^{n/2}T_{n/2}&\text{if \begin{math}n\end{math} even}\end{cases}$

###### Proof.

Induction on $n$. Note it is true for $n=1,2$, and true for $n=3$ because
$A_{3}=B_{3}=2$. Now suppose it is true up to $n-1$ where $n>3$; we will show
it for $n$.

If $n$ is odd: for all $2\leq k\leq n-2$, one of $k$ and $n-k$ is odd and
larger than 1, because $n$ is odd. Hence $D_{k}D_{n-k}=0$ by inductive
hypothesis. Thus in the expression given for $D_{n}$ in 4.3, all terms in the
RHS sum vanish except $k=1$ and $k=n-1$. However both of these terms still
contribute zero, because $n$ is odd so $e^{n-1}_{1}=o^{n-1}_{1}$ (and also
$e^{n-1}_{n-2}=o^{n-1}_{n-2}$ by taking the complement of subsets of size 1).
So $D_{n}=0$ as required.

Otherwise, $n$ is even: write $n=2j,j\in\mathbb{N}$. In the expression given
for $D_{n}$ in 4.3, terms in the RHS sum vanish when $k$ is odd because
$D_{k}=D_{2j-k}=0$ by inductive hypothesis. Hence only the even terms
contribute to the sum. Write $k=2r,r\in\mathbb{N}$:

$D_{2j}=\sum_{r=1}^{j-1}D_{2r}D_{2j-2r}(e^{2j-1}_{2r-1}-o^{2j-1}_{2r-1})(e^{2j-1}_{2r}-o^{2j-1}_{2r})$
$=\sum_{r=1}^{j-1}D_{2r}D_{2j-2r}{j-1\choose r-1}{j-1\choose r}\;\text{by
\lx@cref{creftype~refnum}{lem:dets_evenminusodd}}$
$=(-1)^{j}\sum_{r=1}^{j-1}T_{r}T_{j-r}{j-1\choose r-1}{j-1\choose r}\;\text{by
inductive hypothesis}$

The RHS is $(-1)^{j}$ multiplied by the recurrence given in Section 3 for the
number of CNATs of a given size. Hence it equals $(-1)^{j}T_{j}$ as required.

∎

## References

  * [ABBS14] Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, and Matteo Silimbani.  Combinatorics of non-ambiguous trees.  Advances in Applied Mathematics, 56:78–108, 2014.
  * [Ava23] Jean-Christophe Aval.  About the determinant of complete non-ambiguous trees, 2023.
  * [CO24] Daniel Chen and Sebastian Ohlig.  Associated Permutations of Complete Non-Ambiguous Trees.  Discrete Mathematics & Theoretical Computer Science, vol. 25:2 , April 2024.