# Dividing the Ontology Alignment Task
with Semantic Embeddings and Logic-based Modules††Accepted to the 24th
European Conference on Artificial Intelligence (ECAI 2020)

Ernesto Jiménez-Ruiz City, University of London, UK, email: ernesto.jimenez-
<EMAIL_ADDRESS>and Department of Informatics, University of Oslo,
NorwaySection for Artificial Intelligence and Decision Support, Medical
University of Vienna, Vienna, AustriaDepartment of Computer Science,
University of Oxford, UKMiami University, Oxford, OH 45056, United States Asan
Agibetov Section for Artificial Intelligence and Decision Support, Medical
University of Vienna, Vienna, AustriaDepartment of Computer Science,
University of Oxford, UKMiami University, Oxford, OH 45056, United States
Jiaoyan Chen Department of Computer Science, University of Oxford, UKMiami
University, Oxford, OH 45056, United States Matthias Samwald3 Miami
University, Oxford, OH 45056, United States Valerie Cross Miami University,
Oxford, OH 45056, United States

###### Abstract

Large ontologies still pose serious challenges to state-of-the-art ontology
alignment systems. In this paper we present an approach that combines a neural
embedding model and logic-based modules to accurately divide an input ontology
matching task into smaller and more tractable matching (sub)tasks. We have
conducted a comprehensive evaluation using the datasets of the Ontology
Alignment Evaluation Initiative. The results are encouraging and suggest that
the proposed method is adequate in practice and can be integrated within the
workflow of systems unable to cope with very large ontologies.

##  1 Introduction

The problem of (semi-)automatically computing an alignment between
independently developed ontologies has been extensively studied in the last
years. As a result, a number of sophisticated ontology alignment systems
currently exist [44, 15].222Ontology matching surveys and approaches:
http://ontologymatching.org/ The Ontology Alignment Evaluation
Initiative333OAEI evaluation campaigns: http://oaei.ontologymatching.org/
(OAEI) [3, 4] has played a key role in the benchmarking of these systems by
facilitating their comparison on the same basis and the reproducibility of the
results. The OAEI includes different tracks organised by different research
groups. Each track contains one or more matching tasks involving small-size
(e.g., conference), medium-size (e.g., anatomy), large (e.g., phenotype) or
very large (e.g., largebio) ontologies. Some tracks only involve matching at
the terminological level (e.g., concepts and properties) while other tracks
also expect an alignment at the assertional level (i.e., instance data).

Large ontologies still pose serious challenges to ontology alignment systems.
For example, several systems participating in the _largebio track_ were unable
to complete the largest tasks during the latest OAEI campaigns.444Largebio
track: http://www.cs.ox.ac.uk/isg/projects/SEALS/oaei/ These systems typically
use advanced alignment methods and are able to cope with small and medium size
ontologies with competitive results, but fail to complete large tasks in a
given time frame or with the available resources such as memory.

There have been several efforts in the literature to divide the ontology
alignment task (e.g., [20, 22]). These approaches, however, have not been
successfully evaluated with very large ontologies, failing to scale or
producing partitions of the ontologies leading to information loss [42]. In
this paper we propose a novel method to accurately divide the matching task
into several independent, smaller and manageable (sub)tasks, so as to scale
systems that cannot cope with very large ontologies.555A preliminary version
of this work has been published in arXiv [25] and in the Ontology Matching
workshop [26]. Unlike state-of-the-art approaches, our method:  (i) preserves
the coverage of the relevant ontology alignments while keeping manageable
matching subtasks;  (ii) provides a formal notion of matching subtask and
semantic context;  (iii) uses neural embeddings to compute an accurate
division by learning semantic similarities between words and ontology entities
according to the ontology alignment task at hand;  (iv) computes self-
contained (logical) modules to guarantee the inclusion of the (semantically)
relevant information required by an alignment system; and  (v) has been
successfully evaluated with very large ontologies.

##  2 Preliminaries

A _mapping_ (also called match) between entities666In this work we accept any
input ontology in the OWL 2 language [18]. We refer to (OWL 2) concepts,
properties and individuals as entities. of two ontologies $\mathcal{O}_{1}$
and $\mathcal{O}_{2}$ is typically represented as a 4-tuple $\langle
e_{1},\allowbreak e_{2},\allowbreak r,\allowbreak c\rangle$ where $e_{1}$ and
$e_{2}$ are entities of $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$, respectively;
$r$ is a semantic relation, typically one of
$\\{\sqsubseteq,\sqsupseteq,\equiv\\}$; and $c$ is a confidence value,
usually, a real number within the interval $\left(0,1\right]$. For simplicity,
we refer to a mapping as a pair $\langle e_{1},\allowbreak e_{2}\rangle$. An
ontology _alignment_ is a set of mappings $\mathcal{M}$ between two ontologies
$\mathcal{O}_{1}$ and $\mathcal{O}_{2}$.

An ontology _matching task_ $\mathcal{M}\mathcal{T}$ is composed of a pair of
ontologies $\mathcal{O}_{1}$ (typically called source) and $\mathcal{O}_{2}$
(typically called target) and possibly an associated _reference alignment_
$\mathcal{M}^{RA}$. The objective of a matching task is to discover an
overlapping of $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ in the form of an
alignment $\mathcal{M}$. The _size_ or _search space_ of a matching task is
typically bound to the size of the Cartesian product between the entities of
the input ontologies: $\lvert Sig(\mathcal{O}_{1})\rvert\times\lvert
Sig(\mathcal{O}_{2})\rvert$, where $Sig(\mathcal{O})$ denotes the signature
(i.e., entities) of $\mathcal{O}$ and $\lvert\cdot\lvert$ denotes the size of
a set.

An ontology _matching system_ is a program that, given as input a matching
task $\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$,
generates an ontology alignment $\mathcal{M}^{S}$.777Typically automatic,
although there are systems that also allow human interaction [32]. The
standard evaluation measures for an alignment $\mathcal{M}^{S}$ are
_precision_ (P), _recall_ (R) and _f-measure_ (F) computed against a reference
alignment $\mathcal{M}^{RA}$ as follows:

$P=\frac{\lvert\mathcal{M}^{S}\cap\mathcal{M}^{RA}\rvert}{\lvert\mathcal{M}^{S}\rvert},~{}R=\frac{\lvert\mathcal{M}^{S}\cap\mathcal{M}^{RA}\rvert}{\lvert\mathcal{M}^{RA}\rvert},~{}F=2\cdot\frac{P\cdot
R}{P+R}$ (1)

Figure 1: Pipeline to divide a given matching task
$\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$.

###  2.1 Problem definition and quality measures

We denote _division_ of an ontology matching task $\mathcal{M}\mathcal{T}$,
composed by the ontologies $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$, as the
process of finding $n$ matching subtasks
$\mathcal{M}\mathcal{T}_{i}=\langle\mathcal{O}_{1}^{i},\mathcal{O}_{2}^{i}\rangle$
(with $i$=$1$,…,$n$), where $\mathcal{O}_{1}^{i}\subset\mathcal{O}_{1}$ and
$\mathcal{O}_{2}^{i}\subset\mathcal{O}_{2}$.

Size of the division. The size of each matching subtask is smaller than the
original task and thus reduces the search space. Let
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}=\\{\mathcal{M}\mathcal{T}_{1},\ldots,\mathcal{M}\mathcal{T}_{n}\\}$
be the division of a matching task $\mathcal{M}\mathcal{T}$ into $n$ subtasks.
The _size ratio_ of the subtasks $\mathcal{M}\mathcal{T}_{i}$ and
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ with respect to the original
matching task size is computed as follows:

$\mathsf{SizeRatio}(\mathcal{M}\mathcal{T}_{i},\mathcal{M}\mathcal{T})=\frac{\lvert
Sig(\mathcal{O}_{1}^{i})\rvert\times\lvert
Sig(\mathcal{O}_{2}^{i})\rvert}{\lvert Sig(\mathcal{O}_{1})\rvert\times\lvert
Sig(\mathcal{O}_{2})\rvert}$ (2)
$\mathsf{SizeRatio}(\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n},\mathcal{M}\mathcal{T})=\sum_{i=1}^{n}\mathsf{SizeRatio}(\mathcal{M}\mathcal{T}_{i},\mathcal{M}\mathcal{T})$
(3)

The ratio
$\mathsf{SizeRatio}(\mathcal{M}\mathcal{T}_{i},\mathcal{M}\mathcal{T})$ is
less than $1.0$ while the aggregation
$\sum_{i=1}^{n}\mathsf{SizeRatio}(\mathcal{M}\mathcal{T}_{i},\mathcal{M}\mathcal{T})$,
being $n$ the number of matching subtasks, can be greater than $1.0$ as
matching subtasks depend on the division technique and may overlap.

Alignment coverage. The division of the matching task aims at preserving the
target outcomes of the original matching task. The _coverage_ is calculated
with respect to a relevant alignment $\mathcal{M}$, possibly the reference
alignment $\mathcal{M}^{RA}$ of the matching task if it exists, and indicates
whether that alignment can still be (potentially) discovered with the matching
subtasks. The formal notion of coverage is given in Definitions 1 and 2.

######  Definition 1 (Coverage of a matching task)

Let $\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$ be
a matching task and $\mathcal{M}$ an alignment. We say that a mapping
$m=\langle e_{1},\allowbreak e_{2}\rangle\in\mathcal{M}$ is covered by the
matching task if $e_{1}\in Sig(\mathcal{O}_{1})$ and $e_{2}\in
Sig(\mathcal{O}_{2})$. The coverage of $\mathcal{M}\mathcal{T}$ w.r.t.
$\mathcal{M}$ (denoted as
$\mathsf{Coverage}(\mathcal{M}\mathcal{T},\mathcal{M})$) represents the set of
mappings $\mathcal{M}^{\prime}\subseteq\mathcal{M}$ covered by
$\mathcal{M}\mathcal{T}$.

######  Definition 2 (Coverage of the matching task division)

Let
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}=\\{\mathcal{M}\mathcal{T}_{1},\ldots,\mathcal{M}\mathcal{T}_{n}\\}$
be the result of dividing a matching task $\mathcal{M}\mathcal{T}$ and
$\mathcal{M}$ an alignment. We say that a mapping $m\in\mathcal{M}$ is covered
by $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ if $m$ is at least covered by
one of the matching subtask $\mathcal{M}\mathcal{T}_{i}$ (with $i$=$1$,…,$n$)
as in Definition 1. The coverage of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$
w.r.t. $\mathcal{M}$ (denoted as
$\mathsf{Coverage}(\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n},\mathcal{M})$)
represents the set of mappings $\mathcal{M}^{\prime}\subseteq\mathcal{M}$
covered by $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$. The coverage is given
as a ratio with respect to the (covered) alignment:

$\mathsf{CoverageRatio}(\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n},\mathcal{M})=\frac{\lvert\mathsf{Coverage}(\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n},\mathcal{M})\rvert}{\lvert\mathcal{M}\rvert}$
(4)

##  3 Methods

In this section we present our approach to compute a division
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}=\\{\mathcal{M}\mathcal{T}_{1},\ldots,\mathcal{M}\mathcal{T}_{n}\\}$
given a matching task
$\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$ and the
number of target subtasks $n$. We rely on locality ontology modules to extract
self-contained modules of the input ontologies. The module extraction and task
division is tailored to the ontology alignment task at hand by embedding the
contextual semantics of a (combined) inverted index of the ontologies in the
matching task.

Figure 1 shows an overview of our approach. (i) The ontologies
$\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ are indexed using the lexical index
LexI (see Section 3.2); (ii) LexI is divided into clusters based on the
semantic embeddings of its entries (see Section 3.4); (iii) entries in those
clusters derive potential mapping sets (see Section 3.3); and (iv) the context
of these mapping sets lead to matching subtasks (see Sections 3.1 and 3.3).
Next, we elaborate on the methods behind these steps.

###  3.1 Locality modules and context

Logic-based module extraction techniques compute ontology fragments that
capture the meaning of an input signature (e.g., set of entities) with respect
to a given ontology. That is, a module contains the context (i.e., sets of
_semantically related_ entities) of the input signature. In this paper we rely
on bottom-locality modules [13, 29], which will be referred to as locality-
modules or simply as modules. These modules include the ontology axioms
required to describe the entities in the signature. Locality-modules compute
self-contained ontologies and are tailored to tasks that require reusing a
fragment of an ontology. Please refer to [13, 29] for further details.

Locality-modules play an key role in our approach as they provide the context
for the entities in a given mapping or set of mappings as formally presented
in Definition 3.

######  Definition 3 (Context of a mapping and an alignment)

Let $m=\langle e_{1},\allowbreak e_{2}\rangle$ be a mapping between two
ontologies $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$. We define the context of
$m$ (denoted as $\mathsf{Context}(m,\mathcal{O}_{1},\mathcal{O}_{2})$) as a
pair of locality modules $\mathcal{O}_{1}^{\prime}\subseteq\mathcal{O}_{1}$
and $\mathcal{O}_{2}^{\prime}\subseteq\mathcal{O}_{2}$, where
$\mathcal{O}_{1}^{\prime}$ and $\mathcal{O}_{2}^{\prime}$ include the
semantically related entities to $e_{1}$ and $e_{2}$, respectively. Similarly,
the _context_ for an alignment $\mathcal{M}$ between two ontologies
$\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ is denoted as
$\mathsf{Context}(\mathcal{M},\mathcal{O}_{1},\mathcal{O}_{2})=\langle\mathcal{O}_{1}^{\prime},\mathcal{O}_{2}^{\prime}\rangle$,
where $\mathcal{O}_{1}^{\prime}$ and $\mathcal{O}_{2}^{\prime}$ are modules
including the semantically related entities for the entities $e_{1}\in
Sig(\mathcal{O}_{1})$ and $e_{2}\in Sig(\mathcal{O}_{2})$ in each mapping
$m=\langle e_{1},\allowbreak e_{2}\rangle\in\mathcal{M}$.

Intuitively, as the context of an alignment (i.e.,
$\mathsf{Context}(\mathcal{M},\mathcal{O}_{1},\mathcal{O}_{2})=\langle\mathcal{O}_{1}^{\prime},\mathcal{O}_{2}^{\prime}\rangle$)
semantically characterises the entities involved in that alignment, a matching
task $\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$
can be reduced to the task
$\mathcal{M}\mathcal{T}^{\mathcal{M}}_{\mathcal{O}_{1}\text{-}\mathcal{O}_{2}}=\langle\mathcal{O}_{1}^{\prime},\mathcal{O}_{2}^{\prime}\rangle$
without information loss in terms of finding $\mathcal{M}$ (i.e.,
$\mathsf{Coverage}(\mathcal{M}\mathcal{T}^{\mathcal{M}}_{\mathcal{O}_{1}\text{-}\mathcal{O}_{2}},\mathcal{M})=\mathcal{M}$).
For example, in the small OAEI _largebio_ tasks [3, 4] systems are given the
context of the reference alignment as a (reduced) matching task (e.g.,
$\mathcal{M}\mathcal{T}^{RA}_{\text{fma-
nci}}=\mathsf{Context}(\mathcal{M}^{RA}_{\text{fma-nci}},\
\mathcal{O}_{\text{FMA}},\mathcal{O}_{\text{NCI}})=\langle\mathcal{O}_{\text{FMA}}^{\prime},\mathcal{O}_{\text{NCI}}^{\prime}\rangle$),
instead of the whole FMA and NCI ontologies.

Table 1: Inverted lexical index LexI. For readability, index values have been split into elements of $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$. ‘-’ indicates that the ontology does not contain entities for that entry. | # | Index key | Index value
---|---|---
Entities $\mathcal{O}_{1}$ | Entities $\mathcal{O}_{2}$
1 |  $\\{$ disorder $\\}$ |  $\mathcal{O}_{1}$:Disorder_of_pregnancy, $\mathcal{O}_{1}$:Disorder_of_stomach |  $\mathcal{O}_{2}$:Pregnancy_Disorder
2 |  $\\{$ disorder, pregnancy $\\}$ |  $\mathcal{O}_{1}$:Disorder_of_pregnancy |  $\mathcal{O}_{2}$:Pregnancy_Disorder
3 |  $\\{$ carcinoma, basaloid $\\}$ |  $\mathcal{O}_{1}$:Basaloid_carcinoma |  $\mathcal{O}_{2}$:Basaloid_Carcinoma, $\mathcal{O}_{2}$:Basaloid_Lung_Carcinoma
4 |  $\\{$ follicul, thyroid, carcinom $\\}$ |  $\mathcal{O}_{1}$:Follicular_thyroid_carcinoma |  $\mathcal{O}_{2}$:Follicular_Thyroid_carcinoma
5 |  $\\{$ hamate, lunate $\\}$ |  $\mathcal{O}_{1}$:Lunate_facet_of_hamate | -

###  3.2 Indexing the ontology vocabulary

We rely on a semantic inverted index (we will refer to this index as LexI).
This index maps sets of words to the entities where these words appear. LexI
encodes the labels of all entities of the input ontologies $\mathcal{O}_{1}$
and $\mathcal{O}_{2}$, including their lexical variations (e.g., preferred
labels, synonyms), in the form of _key-value_ pairs where the key is a set of
words and the value is a set of entities such that the set of words of the key
appears in (one of) the entity labels. Similar indexes are commonly used in
information retrieval applications [11], Entity Resolution systems [40], and
also exploited in ontology alignment systems (e.g., LogMap [27], ServOMap [14]
and AML [16]) to reduce the search space and enhance the matching process.
Table 1 shows a few example entries of LexI for two input ontologies.

LexI is created as follows.  (i) Each label associated to an ontology entity
is split into a set of words; for example, the label “Lunate facet of hamate”
is split into the set {“lunate”, “facet”, “of”, “hamate”}.  (ii) Stop-words
are removed from the set of words.  (iii) Stemming techniques are applied to
each word (i.e., {“lunat”, “facet”, “hamat”}).  (iv) Combinations of subsets
of words also serve as keys in LexI; for example, {“lunat”, “facet”},
{“hamat”, “lunat”} and so on.888In order to avoid a combinatorial blow-up, the
number of computed subsets of words is limited. (v) Entities leading to the
same (sub)set of words are associated to the same key in LexI, for example
{“disorder”} is associated with three entities. Finally,  (vi) entries in LexI
pointing to entities of only one ontology or associated to a number of
entities larger than $\alpha$ are not considered.999In the experiments we used
$\alpha=60$. Note that a single entity label may lead to several entries in
LexI, and each entry in LexI points to one or more entities.

###  3.3 Covering matching subtasks

Each entry (i.e., a _key-value_ pair) in LexI is a source of candidate
mappings. For instance, the example in Table 1 suggests that there is a
candidate mapping
$m=\langle\mathsf{\mathcal{O}_{1}\negthickspace:\negthickspace
Disorder\\_of\\_stomach},\allowbreak\mathsf{\mathcal{O}_{2}\negthickspace:\negthickspace
Pregnancy\\_disorder}\rangle$ since these entities are associated to the _{
“disorder”}_ entry in LexI. These mappings are not necessarily correct but
will link lexically-related entities, that is, those entities sharing at least
one word among their labels (e.g., “disorder”). Given a subset of entries or
rows of LexI (i.e., $l\subseteq\textsf{LexI}$), the function
$\mathsf{Mappings}(l)=\mathcal{M}^{l}$ provides the set of mappings derived
from $l$. We refer to the set of all (potential) mappings suggested by LexI
(i.e., $\mathsf{Mappings}(\textsf{LexI})$) as $\mathcal{M}^{\textsf{LexI}}$.
$\mathcal{M}^{\textsf{LexI}}$ represents a manageable subset of the Cartesian
product between the entities of the input ontologies. For example, LexI
suggest around $2\times 10^{4}$ potential mappings for the matching task
$\mathcal{M}\mathcal{T}_{\text{fma-
nci}}=\langle\mathcal{O}_{\text{FMA}},\mathcal{O}_{\text{NCI}}\rangle$, while
the Cartesian product between $\mathcal{O}_{\text{FMA}}$ and
$\mathcal{O}_{\text{NCI}}$ involves more than $5\times 10^{9}$ mappings.

Since standard ontology alignment systems rarely discover mappings outside
$\mathcal{M}^{\textsf{LexI}}$, the context of $\mathcal{M}^{\textsf{LexI}}$
(recall Definition 3) can be seen as a reduced matching task
$\mathcal{M}\mathcal{T}^{\textsf{LexI}}=\mathsf{Context}(\mathcal{M}^{\textsf{LexI}},\mathcal{O}_{1},\mathcal{O}_{2})=\langle\mathcal{O}_{1}^{\textsf{LexI}},\mathcal{O}_{2}^{\textsf{LexI}}\rangle$
of the original task
$\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$.
However, the modules $\mathcal{O}_{1}^{\textsf{LexI}}$ and
$\mathcal{O}_{2}^{\textsf{LexI}}$, although smaller than $\mathcal{O}_{1}$ and
$\mathcal{O}_{2}$, can still be challenging for many ontology matching
systems. A solution is to divide or cluster the entries in LexI to lead to
several tasks involving smaller ontology modules.

######  Definition 4 (Matching subtasks from LexI)

Let $\mathcal{M}\mathcal{T}=\langle\mathcal{O}_{1},\mathcal{O}_{2}\rangle$ be
a matching task, _LexI_ the inverted index of the ontologies $\mathcal{O}_{1}$
and $\mathcal{O}_{2}$, and $\\{l_{1},\ldots,l_{n}\\}$ a set of $n$ clusters of
entries in _LexI_. We denote the set of matching subtasks from _LexI_ as
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}=\\{\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{1},\ldots,\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{n}\\}$
where each cluster $l_{i}$ leads to the matching subtask
$\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{i}=\langle\mathcal{O}_{1}^{i},\mathcal{O}_{2}^{i}\rangle$,
such that $\mathsf{Mappings}(l_{i})=\mathcal{M}^{\textsf{LexI}}_{i}$ is the
set of mappings suggested by the _LexI_ entries in $l_{i}$ (i.e., _key-value_
pairs) and $\mathcal{O}_{1}^{i}$ and $\mathcal{O}_{2}^{i}$ represent the
context of $\mathcal{M}^{\textsf{LexI}}_{i}$ w.r.t. $\mathcal{O}_{1}$ and
$\mathcal{O}_{2}$.

Quality of the matching subtasks. The matching subtasks in Definition 4 rely
on LexI and the notion of context, thus it is expected that the tasks in
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ will cover most of the mappings
$\mathcal{M}^{S}$ that a matching system can compute, that is
$\mathsf{CoverageRatio}(\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n},\mathcal{M}^{S})$
will be close to $1.0$. Furthermore, the use of locality modules to compute
the context guarantees the extraction of matching subtasks that are suitable
to ontology alignment systems in terms of preservation of the logical
properties of the given signature.

Intuitively each cluster of LexI will lead to a smaller matching task
$\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{i}$ (with respect to both
$\mathcal{M}\mathcal{T}^{\textsf{LexI}}$ and $\mathcal{M}\mathcal{T}$) in
terms of search space. Hence
$\mathsf{SizeRatio}(\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{i},\mathcal{M}\mathcal{T})$
will be smaller than $1.0$. The overall aggregation of ratios (cf. Equation 3)
depends on the clustering strategy of the entries in LexI and it is also
expected to be smaller than $1.0$.

Reducing the search space in each matching subtask
$\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{i}$ has the potential of enabling the
evaluation of systems that cannot cope with the original matching task
$\mathcal{M}\mathcal{T}$ in a given time-frame or with (limited) computational
resources.

Table 2: Matching tasks. AMA: Adult Mouse Anatomy. DOID: Human Disease Ontology. FMA: Foundational Model of Anatomy. HPO: Human Phenotype Ontology. MP: Mammalian Phenotype. NCI: National Cancer Institute Thesaurus. NCIA: Anatomy fragment of NCI. ORDO: Orphanet Rare Disease Ontology. SNOMED CT: Systematized Nomenclature of Medicine – Clinical Terms. Phenotype ontologies downloaded from BioPortal. For all tracks we use the consensus with vote=3 as system mappings $\mathcal{M}^{S}$. The Phenotype track does not have a gold standard so a consensus alignment with vote=2 is used as reference.  OAEI track | Source of $\mathcal{M}^{RA}$ | Source of $\mathcal{M}^{S}$ | Task | Ontology | Version | Size (classes)
---|---|---|---|---|---|---
Anatomy | Manually created [10] | Consensus (vote=3) | AMA-NCIA | AMA | v.2007 | 2,744
NCIA | v.2007 | 3,304
Largebio | UMLS-Metathesaurus [28] | Consensus (vote=3) | FMA-NCI | FMA | v.2.0 | 78,989
FMA-SNOMED | NCI | v.08.05d | 66,724
SNOMED-NCI |  SNOMED CT | v.2009 | 306,591
Phenotype |  Consensus alignment (vote=2) [21] | Consensus (vote=3) | HPO-MP | HPO |  v.2016 | 11,786
MP | v.2016 | 11,721
DOID-ORDO | DOID | v.2016 | 9,248
ORDO | v.2016 | 12,936

###  3.4 Semantic embeddings

We use a _semantic embedding_ approach to identify, given $n$, a set of
clusters of entries $\\{l_{1},\ldots,l_{n}\\}$ from LexI. As in Definition 4,
these clusters lead to the set of matching subtasks
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}=\\{\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{1},\ldots,\mathcal{M}\mathcal{T}^{\textsf{LexI}}_{n}\\}$.
The _semantic embeddings_ aim at representing into the same (vector) space the
features about the relationships among words and ontology entities that occur
in LexI. Hence, words and entities that belong to similar semantic contexts
will typically have similar vector representations.

Embedding model. Our approach currently relies on the StarSpace
toolkit101010StarSpace: https://github.com/facebookresearch/StarSpace and its
neural embedding model [49] to learn _embeddings_ for the words and ontology
entities in LexI. We adopt the _TagSpace_ [48] training setting of StarSpace.
Applied to our setting, StarSpace learns associations between a set of words
(i.e., keys in LexI) and a set of relevant ontology entities (i.e., values in
LexI). The StarSpace model is trained by assigning a $d$-dimensional vector to
each of the relevant features (e.g., the individual words and the ontology
entities in LexI). Ultimately, the look-up matrix (the matrix of embeddings -
latent vectors) is learned by minimising the loss function in Equation 5.

$\\!\sum_{\begin{subarray}{c}(w,e)\in E^{+},\\\ e^{-}\in
E^{-}\end{subarray}}L^{batch}(sim(\bm{v}_{w},\bm{v}_{e}),sim(\bm{v}_{w},\bm{v}_{e_{1}^{-}}),\ldots,\\\
sim(\bm{v}_{w},\bm{v}_{e_{j}^{-}}))$ (5)

In this loss function we compare positive samples with negative samples. Hence
we need to indicate the generator of positive pairs $(w,e)\in E^{+}$ (in our
setting those are _word-entity_ pairs from LexI) and the generator of negative
entries $e^{-}\in E^{-}$ (in our case we sample from the list of entities in
the values of LexI). StarSpace follows the strategy by Mikolov et al. [36] and
selects a random subset of $j$ negative examples for each batch update. Note
that we tailor the generators to the alignment task by sampling from LexI. The
similarity function $sim$ operates on $d$-dimensional vectors (e.g.,
$\bm{v}_{w}$, $\bm{v}_{e}$ and $\bm{v}_{e}^{-}$), in our case we use the
standard dot product in Euclidean space.

Clustering strategy. The semantic embedding of each entry
$\varepsilon=(K,V)\in$ LexI is calculated by concatenating  (i) the mean
vector representation of the vectors associated to each word in the key $K$,
with  (ii) the mean vector of the vectors of the ontology entities in the
value $V$,  as in Equation 6, where $\oplus$ represents the concatenation of
two vectors, $\bm{v}_{w}$ and $\bm{v}_{e}$ represents $d$-dimensional vector
embeddings learnt by StarSpace, and $\bm{v}_{\varepsilon}$ is a
($2*d$)-dimension vector.

$\bm{v}_{\varepsilon}=\frac{1}{|K|}\sum_{w\in
K}\bm{v}_{w}\oplus\frac{1}{|V|}\sum_{e\in V}\bm{v}_{e}$ (6)

Based on the embeddings $\bm{v}_{\varepsilon}$ we then perform standard
clustering with the K-means algorithm to obtain the clusters of LexI entries
$\\{l_{1},\ldots,l_{n}\\}$. For example, following our approach, in the
example of Table 1 entries in rows $1$ and $2$ (respectively $3$ and $4$)
would belong to the same cluster.

Suitability of the embedding model. Although we could have followed other
embedding strategies, we advocated to learn new entity embeddings with
StarSpace for the following reasons:  (i) ontologies, particularly in the
biomedical domain, may bring specialised vocabulary that is not fully covered
by precomputed word embeddings;  (ii) to embed not only words but also
concepts of both ontologies; and  (iii) to obtain embeddings tailored to the
ontology alignment task (i.e., to learn similarities among words and concepts
dependant on the task).  StarSpace provides the required functionalities to
embed the semantics of LexI and identify accurate clusters. Precise clusters
will lead to smaller matching tasks, and thus, to a reduced global size of the
computed division of the matching task
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ (cf. Equation 3).

##  4 Evaluation

In this section we provide empirical evidence to support the suitability of
the proposed method to divide the ontology alignment task. We rely on the
datasets of the Ontology Alignment Evaluation Initiative (OAEI) [3, 4], more
specifically, on the matching tasks provided in the _anatomy_ , _largebio_ and
_phenotype_ tracks. Table 2 provides an overview of these OAEI tasks and the
related ontologies and mapping sets.

The methods have been implemented in Java111111Java codes:
https://github.com/ernestojimenezruiz/logmap-matcher and Python121212Python
codes: https://github.com/plumdeq/neuro-onto-part (neural embedding strategy),
tested on a Ubuntu Laptop with an Intel Core i9-8950HK<EMAIL_ADDRESS>and
allocating up to $25Gb$ of RAM. Datasets, matching subtasks, computed mappings
and other supporting resources are available in the _Zenodo_ repository [24].
For all of our experiments we used the following StarSpace hyperparameters:
-trainMode 0 -similarity dot --epoch 100 --dim 64.

(a) $\mathsf{CoverageRatio}$ of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$
over $\mathcal{M}^{RA}$

(b) $\mathsf{CoverageRatio}$ of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$
over $\mathcal{M}^{S}$

(c) $\mathsf{SizeRatio}$ of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$

(d) Module sizes of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ for FMA-NCI

Figure 2: Quality measures of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ with
respect to the number of matching subtasks $n$.

###  4.1 Adequacy of the division approach

We have evaluated the adequacy of our division strategy in terms of coverage
(as in Equation 4) and size (as in Equation 3) of the resulting division
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ for each of the matching task in
Table 2.

Coverage ratio. Figures 2(a) and 2(b) shows the coverage of the different
divisions $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ with respect to the
reference alignment and system computed mappings, respectively. As system
mappings we have used the consensus alignment with vote=3, that is, mappings
that have been voted by at least $3$ systems in the last OAEI campaigns. The
overall coverage results are encouraging:  (i) the divisions
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ cover over $94\%$ of the reference
alignments for all tasks, with the exception of the SNOMED-NCI case where
coverage ranges from $0.94$ to $0.90$;  (ii) when considering system mappings,
the coverage for all divisions is over $0.98$ with the exception of AMA-NCIA,
where it ranges from $0.956$ to $0.974$;  (iii) increasing the number of
divisions $n$ tends to slightly decrease the coverage in some of the test
cases, this is an expected behaviour as the computed divisions include
different semantic contexts (i.e., locality modules) and some relevant
entities may fall out the division; finally  (iv) as shown in [42], the
results in terms of coverage of state-of-the-art partitioning methods (e.g.,
[22, 20]) are very low for the OAEI _largebio_ track ($0.76$, $0.59$ and
$0.67$ as the best results for FMA-NCI, FMA-SNOMED and SNOMED-NCI,
respectively), thus, making the obtained results even more valuable.

Size ratio. The results in terms of the size (i.e., search space) of the
selected divisions $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ are presented in
Figure 2(c). The search space is improved with respect to the original
$\mathcal{M}\mathcal{T}$ for all the cases, getting as low as $5\%$ of the
original matching task size for the FMA-NCI and FMA-SNOMED cases. The gain in
the reduction of the search space gets relatively stable after a given
division size; this result is expected since the context provided by locality
modules ensures modules with the necessary semantically related entities. The
scatter plot in Figure 2(d) visualise the size of the source modules against
the size of the target modules for the FMA-NCI matching subtasks with
divisions of size $n\in\\{5,20,50,100\\}$. For instance, the (blue) circles
represent points $\big{(}\lvert Sig(\mathcal{O}_{1}^{i})\rvert,\lvert
Sig(\mathcal{O}_{2}^{i})\rvert\big{)}$ being $\mathcal{O}_{1}^{i}$ and
$\mathcal{O}_{2}^{i}$ the source and target modules (with $i$=$1$,…,$5$) in
the matching subtasks of $\mathcal{D}_{\mathcal{M}\mathcal{T}}^{5}$. It can be
noted that, on average, the size of source and target modules decreases as the
size of the division increases. For example, the largest task in
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{20}$ is represented in point
$(6754,9168)$, while the largest task in
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{100}$ is represented in point
$(2657,11842)$.

Table 3: Evaluation of systems that failed to complete OAEI tasks in the 2015-2018 campaigns. Times reported in seconds (s). Tool | Task | Matching |  Performance measures | Computation times (s)
---|---|---|---|---
subtasks |  P |  R |  F |  Min |  Max |  Total
MAMBA (v.2015) | AMA-NCIA | 5 | 0.870 | 0.624 | 0.727 | 73 | 785 | 1,981
10 |  0.885 |  0.623 |  0.731 | 41 | 379 | 1,608
50 | 0.897 | 0.623 | 0.735 | 8 | 154 |  1,377
FCA-Map (v.2016) | FMA-NCI | 20 | 0.656 | 0.874 | 0.749 | 39 | 340 | 2,934
50 | 0.625 | 0.875 | 0.729 | 19 | 222 | 3,213
FMA-SNOMED | 50 | 0.599 | 0.251 | 0.354 | 6 | 280 | 3,455
100 | 0.569 | 0.253 | 0.350 | 5 | 191 | 3,028
SNOMED-NCI | 150 | 0.704 | 0.629 | 0.664 | 5 | 547 | 16,822
| 200 | 0.696 | 0.630 | 0.661 | 5 | 395 | 16,874
SANOM (v.2017) | FMA-NCI | 20 | 0.475 | 0.720 | 0.572 | 40 | 1,467 | 9,374
50 | 0.466 | 0.726 | 0.568 | 15 | 728 | 7,069
FMA-SNOMED | 100 | 0.145 | 0.210 | 0.172 | 3 | 1,044 | 13,073
150 | 0.143 | 0.209 | 0.170 | 3 | 799 | 10,814
POMap++ (v.2018) | FMA-NCI | 20 | 0.697 | 0.732 | 0.714 | 24 | 850 | 5,448
50 | 0.701 | 0.748 | 0.724 | 11 | 388 | 4,041
FMA-SNOMED | 50 | 0.520 | 0.209 | 0.298 | 4 | 439 | 5,879
100 | 0.522 | 0.209 | 0.298 | 3 | 327 | 4,408
ALOD2vec (v.2018) | FMA-NCI | 20 | 0.697 | 0.813 | 0.751 | 115 | 2,141 | 13,592
50 | 0.698 | 0.813 | 0.751 | 48 | 933 | 12,162
FMA-SNOMED | 100 | 0.702 | 0.183 | 0.29 | 9 | 858 | 12,688
150 | 0.708 | 0.183 | 0.291 | 7 | 581 | 10,449

Computation times. The time to compute the divisions of the matching task is
tied to the number of locality modules to extract, which can be computed in
polynomial time relative to the size of the input ontology [13]. The creation
of LexI does not add an important overhead, while the training of the neural
embedding model ranges from $21s$ in AMA-NCI to $224s$ in SNOMED-NCI. Overall,
for example, the required time to compute the division with $100$ matching
subtasks ranges from $23s$ (AMA-NCIA) to approx. $600s$ (SNOMED-NCI).

###  4.2 Evaluation of OAEI systems

In this section we show that the division of the alignment task enables
systems that, given some computational constraints, were unable to complete an
OAEI task. We have selected the following five systems from the latest OAEI
campaigns, which include novel alignment techniques but failed to scale to
very large matching tasks: MAMBA (v.2015) [35], FCA-Map (v.2016) [52], SANOM
(v.2017) [37], ALOD2vec (v.2018) [43] and POMap++ (v.2018) [30]. MAMBA failed
to complete the anatomy track, while FCA-Map, SANOM, ALOD2vec and POMap++
could not complete the largest tasks in the largebio track. MAMBA and SANOM
threw an out-of-memory exception with $25Gb$, whereas FCA-Map, ALOD2vec and
POMap++ did not complete the tasks within a $6$ hours time-frame. We have used
the SEALS infrastructure to conduct the evaluation [3, 4].

Table 3 shows the obtained results in terms of precision, recall, f-measure,
and computation times (time for the easiest and the hardest task, and total
time for all tasks) over different divisions
$\mathcal{D}_{\mathcal{M}\mathcal{T}}^{n}$ computed using our strategy. For
example, FCA-Map was run over divisions with 20 and 50 matching subtasks
(i.e., $n\in\\{20,50\\}$) in the FMA-NCI case. Note that for each matching
subtask a system generates a partial alignment $\mathcal{M}^{S}_{i}$, the
final alignment for the (original) matching task is computed as the union of
all partial alignments
($\mathcal{M}^{S}=\bigcup_{i=1}^{n}\mathcal{M}^{S}_{i}$). The results are
encouraging and can be summarised as follows:

  1. )

We enabled several systems to produce results even for the largest OAEI test
case (e.g., FCA-Map with SNOMED-NCI).

  2. )

The computation times are also very good falling under the $6$ hours time
frame, specially given that the (independent) matching subtasks have been run
sequentially without parallelization.

  3. )

The size of the divisions, with the exception of FCA-Map, is beneficial in
terms of total computation time.

  4. )

The increase of number of matching subtasks is positive or neutral for MAMBA,
POMap++ and ALOD2vec in terms of f-measure, while it is slightly reduced for
FCA-Map and SANOM.

  5. )

Global f-measure results are lower than top OAEI systems; nevertheless, since
the above systems could not be evaluated without the divisions, these results
are obtained without any fine-tuning of their parameters.

  6. )

The computation times of the hardest tasks, as $n$ increases, is also reduced.
This has a positive impact in the monitoring of alignment systems as the
hardest task is completed in a reasonable time.

##  5 Related work

Partitioning and blocking. Partitioning and modularization techniques have
been extensively used within the Semantic Web to improve the efficiency when
solving the task at hand (e.g., visualization [45, 1], reuse [29], debugging
[47], classification [7]). Partitioning or blocking has also been widely used
to reduce the complexity of the ontology alignment task [16]. In the
literature there are two major categories of partitioning techniques, namely:
_independent_ and _dependent_. Independent techniques typically use only the
structure of the ontologies and are not concerned about the ontology alignment
task when performing the partitioning. Whereas dependent partitioning methods
rely on both the structure of the ontology and the ontology alignment task at
hand. Although our approach does not compute (non-overlapping) partitions of
the ontologies, it can be considered a dependent technique.

Prominent examples of ontology alignment systems including partitioning
techniques are Falcon-AO [22], GOMMA [19], COMA++ [5] and TaxoMap [20].
Falcon-AO, GOMMA and COMA++ perform independent partitioning where the
clusters of the source and target ontologies are independently extracted. Then
pairs of similar clusters (i.e., matching subtasks) are aligned using standard
techniques. TaxoMap [20] implements a dependent technique where the
partitioning is combined with the matching process. TaxoMap proposes two
methods, namely: PAP (partition, anchor, partition) and APP (anchor,
partition, partition). The main difference of these methods is the order of
extraction of (preliminary) anchors to discover pairs of partitions to be
matched (i.e., matching subtasks). SeeCOnt [2] presents a seeding-based
clustering technique to discover independent clusters in the input ontologies.
Their approach has been evaluated with the Falcon-AO system by replacing its
native PBM (Partition-based Block Matching) module [23]. Laadhar et al. [30]
have recently integrated within the system POMap++ a hierarchical
agglomerative clustering algorithm to divide an ontology into a set of
partitions.

The above approaches, although presented interesting ideas, did not provide
guarantees about the size and coverage of the discovered partitions or
divisions. Furthermore, they have not been successfully evaluated on very
large ontologies. On the one hand, as reported by Pereira et al. [42] the
results in terms of coverage of the PBM method of Falcon-OA, and the PAP and
APP methods of TaxoMap are very low for the OAEI largebio track. On the other
hand, as discussed in Section 4, POMap++ fails to scale with the largest
largebio tasks.

Note that the recent work in [31] has borrowed from our workshop paper [26]
the quality measures presented in Section 2.1. They obtain competitive
coverage results for medium size ontologies; however, their approach, as in
POMap++, does not scale for large ontologies.

Blocking techniques are also extensively used in Entity Resolution (see [40]
for a survey). Although related, the problem of blocking in ontologies is
different as the logically related axioms for a seed signature play an
important role when computing the blocks.

Our dependent approach, unlike traditional partitioning and blocking methods,
computes overlapping self-contained modules (i.e., locality modules [13]).
Locality modules guarantee the extraction of all semantically related entities
for a given signature. This capability enhances the coverage results and
enables the inclusion of the (semantically) relevant information required by
an alignment system. It is worth mentioning that the need of self-contained
and covering modules, although not thoroughly studied, was also highlighted in
a preliminary work by Paulheim [41].

Embedding and clustering. Recently, machine learning techniques such as
semantic embedding [12] have been investigated for ontology alignment. They
often first learn vector representations of the entities and then predict the
alignment [9, 51, 46]. However, most of them focus on alignment of ontology
individuals (i.e., ABox) without considering the ontology concepts and axioms
at the terminological level (i.e., TBox). Nkisi-Orji et al. [39] predicts the
alignment between ontology concepts with Random Forest, but incorporates the
embeddings of words alone, without any other semantic components like in our
work. Furthermore, these approaches focus on predicting the alignment, while
our work aims at boosting an existing alignment system. Our framework could
potentially be adopted in systems like in [39] if facing scalability problems
for large ontologies.

Another piece of related work is the clustering of semantic components, using
the canopy clustering algorithm [33] where objects are grouped into canopies
and each object can be a member of multiple canopies. For example, Wu et al.
[50] first extracted canopies (i.e., mentions) from a knowledge base, and then
grouped the entities accordingly so as to finding out the entities with the
same semantics (i.e., canonicalization). As we focus on a totally different
task – ontology alignment, the context that can be used, such as the
embeddings for the words and ontology entities in LexI, is different from
these works, which leads to a different clustering method.

##  6 Conclusions and future work

We have developed a novel framework to split the ontology alignment task into
several matching subtasks based on a semantic inverted index, locality
modules, and a neural embedding model. We have performed a comprehensive
evaluation which suggests that the obtained divisions are suitable in practice
in terms of both coverage and size. The division of the matching task allowed
us to obtain results for five systems which failed to complete these tasks in
the past. We have focused on systems failing to complete a task, but a
suitable adoption and integration of the presented framework within the
pipeline of any ontology alignment system has the potential to improve the
results in terms of computation times.

Opportunities. Reducing the ontology matching task into smaller and more
manageable tasks may also bring opportunities to enhance  (i) user interaction
[32],  (ii) reasoning and repair [34],  (iii) benchmarking and monitoring [3,
4], and  (iv) parallelization.  The computed independent matching subtasks can
potentially be run in parallel in evaluation platforms like the HOBBIT [38].
The current evaluation was conducted sequentially as  (i) the SEALS instance
only allows running one task at a time, and  (ii) the evaluated systems were
not designed to run several tasks in parallel; for instance, we managed to run
MAMBA outside SEALS, but it relies on a MySQL database and raised a concurrent
access exception.

Impact on the f-measure. As shown in Section 4.2, the impact of the number of
divisions on the f-measure depends on the evaluated systems. In the near
future we aim at conducting an extensive evaluation of our framework over OAEI
systems able to deal with the largest tasks in order to obtain more insights
about the impact on the f-measure. In [25] we reported a preliminary
evaluation where YAM-Bio [6] and AML [17] kept similar f-measure values, while
LogMap [27] had a reduction in f-measure, as the number of divisions
increased.

Number of subdivisions. Currently our strategy requires the size of the number
of matching subtasks or divisions as input. The (required) matching subtasks
may be known before hand if, for example, the matching tasks are to be run in
parallel in a number of available CPUs. For the cases where the resources are
limited or where a matching system is known to cope with small ontologies, we
plan to design an algorithm to estimate the number of divisions so that the
size of the matching subtasks in the computed divisions is appropriate to the
system and resource constraints.

Dealing with a limited or large lexicon. The construction of LexI shares a
limitation with state-of-the-art systems when the input ontologies are
lexically disparate or in different languages. In such cases, LexI can be
enriched with general-purpose lexicons (e.g., WordNet), more specialised
background knowledge (e.g., UMLS Metathesaurus) or with translated labels
using online services (e.g., Google). On the other hand, a large lexicon may
also have an important impact in the computation times. Our conducted
evaluation shows, however, that we can cope with very large ontologies with a
rich lexicon (e.g., NCI Thesaurus).

Notion of context. Locality-based modules are typically much smaller than the
whole ontology and they have led to very good results in terms of size and
coverage. We plan, however, to study different notions of _context_ of an
alignment (e.g., the tailored modules proposed in [8]) to further improve the
results in terms of size while keeping the same level of coverage.

This work was supported by the SIRIUS Centre for Scalable Data Access (Norges
forskningsråd), the AIDA project (Alan Turing Institute), Samsung Research UK,
Siemens AG, and the EPSRC projects AnaLOG, OASIS and UK FIRES. We would also
like to thank the anonymous reviewers that helped us improve this work.

## References

  * [1] Asan Agibetov, Giuseppe Patanè, and Michela Spagnuolo, ‘Grontocrawler: Graph-Based Ontology Exploration’, in STAG, (2015).
  * [2] Alsayed Algergawy, Samira Babalou, Mohammad J. Kargar, and S. Hashem Davarpanah, ‘SeeCOnt: A New Seeding-Based Clustering Approach for Ontology Matching’, in ADBIS, (2015).
  * [3] Alsayed Algergawy et al., ‘Results of the Ontology Alignment Evaluation Initiative 2018’, in 13th Int’l Workshop on Ontology Matching, (2018).
  * [4] Alsayed Algergawy et al., ‘Results of the Ontology Alignment Evaluation Initiative 2019’, in Int’l Workshop on Ontology Matching, (2019).
  * [5] Alsayed Algergawy, Sabine Massmann, and Erhard Rahm, ‘A clustering-based approach for large-scale ontology matching’, in ADBIS, pp. 415–428, (2011).
  * [6] Amina Annane, Zohra Bellahsene, Faiçal Azouaou, and Clément Jonquet, ‘YAM-BIO: results for OAEI 2017’, in 12th Int’l Workshop on Ontology Matching, (2017).
  * [7] Ana Armas Romero, Bernardo Cuenca Grau, and Ian Horrocks, ‘MORe: Modular Combination of OWL Reasoners for Ontology Classification’, in Int’l Sem. Web Conf., (2012).
  * [8] Ana Armas Romero, Mark Kaminski, Bernardo Cuenca Grau, and Ian Horrocks, ‘Module Extraction in Expressive Ontology Languages via Datalog Reasoning’, J. Artif. Intell. Res., 55, (2016).
  * [9] Michael Azmy, Peng Shi, Jimmy Lin, and Ihab F Ilyas, ‘Matching entities across different knowledge graphs with graph embeddings’, CoRR, abs/1903.06607, (2019).
  * [10] Olivier Bodenreider, Terry F. Hayamizu, Martin Ringwald, Sherri de Coronado, and Songmao Zhang, ‘Of mice and men: Aligning mouse and human anatomies’, in AMIA Symposium, (2005).
  * [11] Stefan Büttcher, Charles L. A. Clarke, and Gordon V. Cormack, Information Retrieval - Implementing and Evaluating Search Engines, MIT Press, 2010.
  * [12] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang, ‘A comprehensive survey of graph embedding: Problems, techniques, and applications’, IEEE Trans. on Know. and Data Eng., 30(9), (2018).
  * [13] Bernardo Cuenca Grau, Ian Horrocks, Yevgeny Kazakov, and Ulrike Sattler, ‘Modular reuse of ontologies: Theory and practice’, J. Artif. Intell. Res., 31, (2008).
  * [14] Gayo Diallo, ‘An effective method of large scale ontology matching’, J. Biomedical Semantics, 5, 44, (2014).
  * [15] Jérôme Euzenat and Pavel Shvaiko, Ontology Matching, Second Edition, Springer, 2013.
  * [16] Daniel Faria, Catia Pesquita, Isabela Mott, Catarina Martins, Francisco M. Couto, and Isabel F. Cruz, ‘Tackling the challenges of matching biomedical ontologies’, J. Biomedical Semantics, 9(1), (2018).
  * [17] Daniel Faria, Catia Pesquita, Emanuel Santos, Matteo Palmonari, Isabel F. Cruz, and Francisco M. Couto, ‘The AgreementMakerLight Ontology Matching System’, in OTM-ODBASE Conference, (2013).
  * [18] Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter F. Patel-Schneider, and Ulrike Sattler, ‘OWL 2: The next step for OWL’, J. Web Semantics, 6(4), (2008).
  * [19] Anika Groß, Michael Hartung, Toralf Kirsten, and Erhard Rahm, ‘On matching large life science ontologies in parallel’, in Data Integration in the Life Sciences (DILS), (2010).
  * [20] Fayçal Hamdi, Brigitte Safar, Chantal Reynaud, and Haïfa Zargayouna, ‘Alignment-based partitioning of large-scale ontologies’, in Advances in Knowledge Discovery and Management, (2009).
  * [21] Ian Harrow, Ernesto Jiménez-Ruiz, et al., ‘Matching disease and phenotype ontologies in the ontology alignment evaluation initiative’, J. Biomedical Semantics, 8(1), (2017).
  * [22] Wei Hu, Yuzhong Qu, and Gong Cheng, ‘Matching large ontologies: A divide-and-conquer approach’, Data Knowl. Eng., 67, 140–160, (2008).
  * [23] Wei Hu, Yuanyuan Zhao, and Yuzhong Qu, ‘Partition-Based Block Matching of Large Class Hierarchies’, in Asian Sem. Web Conf., (2006).
  * [24] Ernesto Jiménez-Ruiz, Asan Agibetov, Jiaoyan Chen, Matthias Samwald, and Valerie Cross.  Dividing the Ontology Alignment Task [Data set], 2019.  Zenodo. https://doi.org/10.5281/zenodo.3547888.
  * [25] Ernesto Jiménez-Ruiz, Asan Agibetov, Matthias Samwald, and Valerie Cross, ‘Breaking-down the ontology alignment task with a lexical index and neural embeddings’, CoRR, abs/1805.12402, (2018).
  * [26] Ernesto Jiménez-Ruiz, Asan Agibetov, Matthias Samwald, and Valerie Cross, ‘We divide, you conquer: from large-scale ontology alignment to manageable subtasks with a lexical index and neural embeddings’, in 13th Int’l Workshop on Ontology Matching, (2018).
  * [27] Ernesto Jiménez-Ruiz and Bernardo Cuenca Grau, ‘LogMap: Logic-Based and Scalable Ontology Matching’, in Int’l Sem. Web Conf., (2011).
  * [28] Ernesto Jiménez-Ruiz, Bernardo Cuenca Grau, Ian Horrocks, and Rafael Berlanga Llavori, ‘Logic-based assessment of the compatibility of UMLS ontology sources’, J. Biomedical Semantics, 2, (2011).
  * [29] Ernesto Jiménez-Ruiz, Bernardo Cuenca Grau, Ulrike Sattler, Thomas Schneider, and Rafael Berlanga, ‘Safe and Economic Re-Use of Ontologies: A Logic-Based Methodology and Tool Support’, in European Sem. Web Conf., (2008).
  * [30] Amir Laadhar, Faïza Ghozzi, Imen Megdiche, Franck Ravat, Olivier Teste, and Faïez Gargouri, ‘OAEI 2018 results of POMap++’, in 13th Int’l Workshop on Ontology Matching, (2018).
  * [31] Amir Laadhar, Faïza Ghozzi, Imen Megdiche, Franck Ravat, Olivier Teste, and Faïez Gargouri, ‘Partitioning and local matching learning of large biomedical ontologies’, in 34th ACM/SIGAPP Symposium on Applied Computing SAC, (2019).
  * [32] Huanyu Li, Zlatan Dragisic, Daniel Faria, Valentina Ivanova, Ernesto Jiménez-Ruiz, Patrick Lambrix, and Catia Pesquita, ‘User validation in ontology alignment: functional assessment and impact’, The Knowledge Engineering Review, 34, (2019).
  * [33] Andrew McCallum, Kamal Nigam, and Lyle H Ungar, ‘Efficient clustering of high-dimensional data sets with application to reference matching’, in 6th ACM SIGKDD, (2000).
  * [34] Christian Meilicke, Alignment incoherence in ontology matching, Ph.D. dissertation, University of Mannheim, 2011.
  * [35] Christian Meilicke, ‘MAMBA - results for the OAEI 2015’, in 10th Int’l Workshop on Ontology Matching, (2015).
  * [36] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean, ‘Distributed representations of words and phrases and their compositionality’, arXiv, (oct 2013).
  * [37] Majid Mohammadi, Amir Ahooye Atashin, Wout Hofman, and Yao-Hua Tan, ‘SANOM results for OAEI 2017’, in 12th Int’l Workshop on Ontology Matching, (2017).
  * [38] Axel-Cyrille Ngonga Ngomo, Alejandra García-Rojas, and Irini Fundulaki, ‘HOBBIT: holistic benchmarking of big linked data’, ERCIM News, 2016(105), (2016).
  * [39] Ikechukwu Nkisi-Orji, Nirmalie Wiratunga, Stewart Massie, Kit-Ying Hui, and Rachel Heaven, ‘Ontology alignment based on word embedding and random forest classification’, in ECML/PKDD, (2018).
  * [40] George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas, ‘A Survey of Blocking and Filtering Techniques for Entity Resolution’, CoRR, abs/1905.06167, (2019).
  * [41] Heiko Paulheim, ‘On Applying Matching Tools to Large-scale Ontologies’, in 3rd Int’l Workshop on Ontology Matching, (2008).
  * [42] Sunny Pereira, Valerie Cross, and Ernesto Jiménez-Ruiz, ‘On partitioning for ontology alignment’, in Int’l Sem. Web Conf. (Poster), (2017).
  * [43] Jan Portisch and Heiko Paulheim, ‘ALOD2Vec matcher’, in 13th Int’l Workshop on Ontology Matching, (2018).
  * [44] Pavel Shvaiko and Jérôme Euzenat, ‘Ontology matching: State of the art and future challenges’, IEEE Trans. Knowl. Data Eng., 25(1), (2013).
  * [45] Heiner Stuckenschmidt and Anne Schlicht, ‘Structure-based partitioning of large ontologies’, in Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, Springer, (2009).
  * [46] Zequn Sun, Jiacheng Huang, Wei Hu, Muhao Chen, Lingbing Guo, and Yuzhong Qu, ‘TransEdge: Translating Relation-Contextualized Embeddings for Knowledge Graphs’, in Int’l Sem. Web Conf. (ISWC), (2019).
  * [47] Boontawee Suntisrivaraporn, Guilin Qi, Qiu Ji, and Peter Haase, ‘A modularization-based approach to finding all justifications for OWL DL entailments’, in Asian Sem. Web Conf., (2008).
  * [48] Jason Weston, Sumit Chopra, and Keith Adams, ‘#tagspace: Semantic embeddings from hashtags’, in Conference on Empirical Methods in Natural Language Processing (EMNLP), (2014).
  * [49] Ledell Wu, Adam Fisch, Sumit Chopra, Keith Adams, Antoine Bordes, and Jason Weston, ‘StarSpace: Embed All The Things!’, arXiv, (2017).
  * [50] Tien-Hsuan Wu, Zhiyong Wu, Ben Kao, and Pengcheng Yin, ‘Towards practical open knowledge base canonicalization’, in 27th ACM Int’l Conf. on Inf. and Knowledge Management, (2018).
  * [51] Qingheng Zhang, Zequn Sun, Wei Hu, Muhao Chen, Lingbing Guo, and Yuzhong Qu, ‘Multi-view knowledge graph embedding for entity alignment’, in 28th Int’l Joint Conf. on Art. Intell. (IJCAI), (2019).
  * [52] Mengyi Zhao and Songmao Zhang, ‘FCA-Map results for OAEI 2016’, in 11th Int’l Workshop on Ontology Matching, (2016).


# Stochastic super-resolution for Gaussian textures

###### Abstract

Super-resolution (SR) is an ill-posed inverse problem which consists in
proposing high-resolution images consistent with a given low-resolution one.
While most SR algorithms are deterministic, stochastic SR deals with designing
a stochastic sampler generating any realistic SR solution. The goal of this
paper is to show that stochastic SR is a well-posed and solvable problem when
restricting to Gaussian stationary textures. Using Gaussian conditional
sampling and exploiting the stationarity assumption, we propose an efficient
algorithm based on fast Fourier transform. We also demonstrate the practical
relevance of the approach for SR with a reference image. Although limited to
stationary microtextures, our approach compares favorably in terms of speed
and visual quality to some state of the art methods designed for a larger
class of images.

Index Terms—  stochastic super-resolution, Gaussian textures, conditional
simulation, kriging, super-resolution with a reference image

##  1 Introduction

The super resolution (SR) problem consists in generating a high-resolution
(HR) image corresponding to a given low-resolution (LR) input image. This is a
very ill-posed inverse problem that necessitates an image prior model or
additional information to create images having sharp edges and rich texture
details. This is a very important problem for the entertainment industry due
to the increase in resolution of display screens as well as other imaging
industries where resolution is critical, notably satellite imaging and
microscopy.

Different frameworks are considered in the literature: the Single Image SR
(SISR) consists in using only an LR input image and a generic database of HR
images, while SR with a reference image considers an LR input image
accompanied with an HR image that presents similarity with the unknown HR
input. Most contributions in SISR are based on conditional generative neural
networks [1, 2, 3, 4], adversarial [5] or not, and trained using the
“perceptual loss” [6], that is, the distance between pretrained VGG features
[7]. These references tackle zoom factor x4 or even x8. Contrary to a
classical x2 problem that can be seen as an image sharpener problem, for such
high zoom factors new image content must be generated in accordance with the
LR input, and the space of possible images becomes very large. All references
then insist on the importance of generating local textures and avoiding the
“regression to the mean problem”: when favoring PSNR the optimal result
consists in a blurry image close to the mean of plausible sharp images. While
SISR can be seen as local conditional texture synthesis, a close inspection of
the state-of-the-art techniques shows however that texture modeling is absent
from GANs. Indeed, the perception loss does not favor the statistics of the
textures one wishes to reconstruct. In addition, the proposed models are
generally deterministic, which is not desirable for texture generation since
it does not allow checking the statistical consistency of the proposed
solution. More recent models propose generative networks with stochastic
response for SISR: SRFlow [8] use invertible generative flow [9] and [10] use
Denoising Diffusion Probabilistic Models (DDPM) [11], also called score-based
models [12]. They propose practical solutions for stochastic SR, that is
providing a stochastic sampler that outputs any realistic solution to the SISR
problem. In addition, let us note that several recent contributions solely
focus on texture SR, using patch statistics from a reference image [13, 14] or
a prior as spectral content [15].

In this paper, we solve the problem of stochastic SR when restricting to
stationary Gaussian textures [16]. Following a similar approach as for
Gaussian texture inpainting [17, 18], assuming that the LR input is stationary
and Gaussian with a known covariance in HR space, we propose an exact SR
sampler relying on conditional Gaussian simulation. We exploit the
stationarity of both the texture model and the zoom-out operator to obtain an
efficient algorithm based on Fast Fourier Transform (FFT). We further
demonstrate experimentally the interest of the approach in the context of SR
with a reference image.

The plan of the paper is as follows. We present our framework of SR and remind
results about conditional Gaussian simulation. Then, we focus on Gaussian
stationary textures and detail how to implement efficiently the stochastic
simulation for these models. Finally, we extend the approach for SR with a
reference image and compare our results with the state of the art before
concluding.

LR image

HR image

SR Gaussian sample

Kriging component

Innovation component

Fig. 1:  Different components of the Gaussian SR model. Top row: SR with a
factor $\times 16$, the images HR size is $512\times 768$; Bottom row: SR with
a factor $\times 8$, the images HR size is $256\times 256$. The last columns
present respectively a Gaussian SR sample and its associated kriging and
innovation components. Observe the complementarity of the the kriging
component which deblurs the LR input and the innovation component which adds
independent high-frequency details.

##  2 Gaussian conditional simulation for super-resolution

###  2.1 Framework

Notations Let $M,N>2$ be the size of the images. We extend all the images on
$\mathbb{Z}^{2}$ by periodization. We write $[M]=\\{0,\ldots,M-1\\}$ and
${\Omega_{M,N}}=[M]\times[N]$. For
${\mathbf{X}},{\mathbf{Y}}\in\mathbb{R}^{{\Omega_{M,N}}}$,
${\mathbf{X}}\star{\mathbf{Y}}$ designates the discrete and periodic
convolution defined by
$({\mathbf{X}}\star{\mathbf{Y}})({\boldsymbol{x}})=\sum_{{\boldsymbol{y}}\in{\Omega_{M,N}}}{\mathbf{X}}\big{(}{\boldsymbol{x}}-{\boldsymbol{y}}\big{)}{\mathbf{Y}}({\boldsymbol{y}})$,
${\boldsymbol{x}}\in{\Omega_{M,N}}$. For
$\boldsymbol{\lambda}\in\mathbb{R}^{{\Omega_{M,N}}}$, we denote the symmetric
$\widecheck{\boldsymbol{\lambda}}$ such that for
${\boldsymbol{x}}\in{\Omega_{M,N}},\widecheck{\boldsymbol{\lambda}}({\boldsymbol{x}})=\boldsymbol{\lambda}(-{\boldsymbol{x}})$.
For ${\mathbf{X}}\in\mathbb{R}^{{\Omega_{M,N}}}$, we express by
$\mathscr{F}_{2}({\mathbf{X}})$ or $\widehat{{\mathbf{X}}}$ its discrete
Fourier transform defined by
$\widehat{{\mathbf{X}}}({\boldsymbol{x}})=\sum_{{\boldsymbol{y}}\in{\Omega_{M,N}}}{\mathbf{X}}({\boldsymbol{y}})\exp({-\frac{2i\pi
x_{1}y_{1}}{M}})\exp(-\frac{2i\pi x_{2}y_{2}}{N})$,
${\boldsymbol{x}}\in{\Omega_{M,N}}$. Let us recall that $\mathscr{F}_{2}$ is
invertible with $\mathscr{F}^{-1}_{2}=\frac{1}{MN}\overline{\mathscr{F}_{2}}$
and that
$\mathscr{F}_{2}({\mathbf{X}}\star{\mathbf{Y}})=\mathscr{F}_{2}({\mathbf{X}})\odot\mathscr{F}_{2}({\mathbf{Y}})$
where $\odot$ denotes the componentwise product.

Zoom-out operator We denote by $r$ the factor of zoom-out $(=4,8,\ldots)$.
From now on we assume that $M$ and $N$ are multiples of $r$. The loss of
pixels in an image can be caused by multiple operators. We will assume in our
experiments that the degradation is caused by the imresize function of Matlab
which is used in many models [3, 4, 8]. Concretely, this operator reduces the
size of an image by weighting the pixels. Supposing that the image is
periodic, we can split it off in a separable convolution which weights all the
pixels followed by a subsampling with stride $r$ [19]. We denote
${\mathbf{A}}={\mathbf{S}}{\mathbf{C}}$ this linear zoom-out operator, with
${\mathbf{C}}$ the convolution and ${\mathbf{S}}$ the subsampling operator
with stride $r$ such that for
${\mathbf{U}}\in\mathbb{R}^{{\Omega_{M,N}}},{\mathbf{S}}{\mathbf{U}}\in\mathbb{R}^{{\Omega_{M/r,N/r}}}$
and for ${\boldsymbol{x}}\in{\Omega_{M/r,N/r}}$,
$({\mathbf{S}}{\mathbf{U}})({\boldsymbol{x}})={\mathbf{U}}(r{\boldsymbol{x}})$.

###  2.2 Gaussian conditional simulation

Let ${\mathbf{X}}\in\mathbb{R}^{{\Omega_{M,N}}}$ be a stationary Gaussian
process with distribution
$\mathscr{N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ and
${{\mathbf{X}}_{\mathrm{LR}}}={\mathbf{A}}{\mathbf{X}}\in\mathbb{R}^{{\Omega_{M/r,N/r}}}$
be its LR version. ${\mathbf{A}}$ reduces the size of the images and thus is
not invertible. We would like to sample
${\mathbf{X}}|{{\mathbf{X}}_{\mathrm{LR}}}$. In our further assumptions,
${\mathbf{X}}$ is supposed to be Gaussian, consequently we will use the
classical theorem recalled in [18]:

######  Theorem 1 (Gaussian simulation and Gaussian kriging).

Let ${\mathbf{X}}$ be a Gaussian vector, and ${\mathbf{A}}$ be a linear
operator, $\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})$ and
${\mathbf{X}}-\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})$ are
independent. Consequently, if $\tilde{{{\mathbf{X}}}}$ is independent of
${\mathbf{X}}$ with the same distribution, then
$\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})+[\tilde{{{\mathbf{X}}}}-\mathbb{E}(\tilde{{{\mathbf{X}}}}|{\mathbf{A}}\tilde{{{\mathbf{X}}}})]$
has the same distribution as ${\mathbf{X}}$, knowing
${\mathbf{A}}{\mathbf{X}}$. Furthermore, if ${\mathbf{X}}$ is zero-mean, there
exists
$\boldsymbol{\Lambda}\in\mathbb{R}^{{{\Omega_{M/r,N/r}}}\times{{\Omega_{M,N}}}}$
such that
$\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})=\boldsymbol{\Lambda}^{T}{\mathbf{A}}{\mathbf{X}}$
and
$\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})=\boldsymbol{\Lambda}^{T}{\mathbf{A}}{\mathbf{X}}$
if and only if $\boldsymbol{\Lambda}$ verifies the matrix equation:

${\mathbf{A}}{\boldsymbol{\Gamma}}{\mathbf{A}}^{T}\boldsymbol{\Lambda}={\mathbf{A}}{\boldsymbol{\Gamma}}.$
(1)

This theorem is a consequence of the fact that the space of square-integrable
random variables is a Hilbert space. The assumption that ${\mathbf{X}}$
follows a Gaussian law is crucial. As for now, the resolution of our problem
requires the computation of
$\mathbb{E}({\mathbf{X}}|{{\mathbf{X}}_{\mathrm{LR}}})=\mathbb{E}({\mathbf{X}}|{\mathbf{A}}{\mathbf{X}})=\boldsymbol{\Lambda}^{T}{\mathbf{A}}{\mathbf{X}}=\boldsymbol{\Lambda}^{T}{{\mathbf{X}}_{\mathrm{LR}}}$,
where $\boldsymbol{\Lambda}$ is called the kriging matrix.
$\boldsymbol{\Lambda}^{T}{{\mathbf{X}}_{\mathrm{LR}}}$ is called the kriging
component and
$\tilde{{{\mathbf{X}}}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}\tilde{{{\mathbf{X}}}}$
the innovation component. Therefore, stochastic SR for Gaussian textures
corresponds to simulate
$\boldsymbol{\Lambda}^{T}{{\mathbf{X}}_{\mathrm{LR}}}+(\tilde{{{\mathbf{X}}}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}\tilde{{{\mathbf{X}}}})$.
Figure 1 presents the realization of
${\mathbf{X}}|{{\mathbf{X}}_{\mathrm{LR}}}$, titled SR Gaussian sample. This
is the sum of the kriging component which is an attachment to data and the
innovation component that adds stochastic independent high-frequency
variations. For the given LR image ${{\mathbf{X}}_{\mathrm{LR}}}$ and the HR
covariance ${\boldsymbol{\Gamma}}$, it is just necessary to compute
$\boldsymbol{\Lambda}$ to sample HR versions of ${{\mathbf{X}}_{\mathrm{LR}}}$

##  3 An efficient implementation in the stationary case

###  3.1 ADSN model and super-resolution

Our objective is to study the SR of Gaussian stationary textures. We will
focus on textures following the asymptotic discrete spot noise (ADSN) model
[16]. Given a grayscale image ${\mathbf{U}}\in\mathbb{R}^{{\Omega_{M,N}}}$
with mean grayscale $m\in\mathbb{R}$, one defines
$\operatorname{ADSN}({\mathbf{U}})$ as the distribution of
${\mathbf{X}}=\mathbf{t}\star{\mathbf{W}}$ where
$\mathbf{t}=\frac{1}{\sqrt{MN}}({\mathbf{U}}-m)$ is called the texton
associated with ${\mathbf{U}}$. $\operatorname{ADSN}({\mathbf{U}})$ is a
Gaussian distribution with mean zero and covariance matrix
${\boldsymbol{\Gamma}}$ that represents the convolution by the kernel
$\boldsymbol{\gamma}=\mathbf{t}\star\widecheck{\mathbf{t}}$.
${\mathbf{X}}\sim\operatorname{ADSN}({\mathbf{U}})$ is stationary since for
all ${\boldsymbol{x}}\in{\Omega_{M,N}}$ and
${\boldsymbol{y}}\in\mathbb{Z}^{2}$,
${\mathbf{X}}({\boldsymbol{x}}-{\boldsymbol{y}})\overset{\mathscr{L}}{=}{\mathbf{X}}({\boldsymbol{x}})$.

For a given input image ${\mathbf{U}}\in\mathbb{R}^{{\Omega_{M,N}}}$ and its
LR version ${{\mathbf{U}}_{\mathrm{LR}}}={\mathbf{A}}{\mathbf{U}}$, we would
like to sample ${\mathbf{X}}\sim\operatorname{ADSN}({\mathbf{U}})$ conditioned
on ${{\mathbf{X}}_{\mathrm{LR}}}={{\mathbf{U}}_{\mathrm{LR}}}$, that is, by
Theorem 1,

${{\mathbf{X}}_{\mathrm{SR}}}=\boldsymbol{\Lambda}^{T}{{\mathbf{U}}_{\mathrm{LR}}}+(\tilde{{{\mathbf{X}}}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}\tilde{{{\mathbf{X}}}})$

where $\tilde{{{\mathbf{X}}}}\sim\operatorname{ADSN}({\mathbf{U}})$, and
$\boldsymbol{\Lambda}$ is the kriging matrix associated with
$\operatorname{ADSN}({\mathbf{U}})=\mathscr{N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$.
We will explain how to implement it efficiently in the following.

###  3.2 Structure of the problem induced by stationarity

For $k,\ell\in[r]$, let
${\Omega^{k,\ell,r}_{M,N}}=\\{(k+ir,\ell+jr),\leavevmode\nobreak\
i,j\in[M/r]\times[N/r]\\}\subset{\Omega_{M,N}}$ be the subgrid of
${\Omega_{M,N}}$ having stride $r$ and starting at $(k,\ell)$. Note that each
subgrid ${\Omega^{k,\ell,r}_{M,N}}$ has the same number of pixels as the LR
image domain ${\Omega_{M/r,N/r}}$.

######  Proposition 1 (Structure of the kriging matrix).

There exists
$\boldsymbol{\Lambda}\in\mathbb{R}^{{{\Omega_{M/r,N/r}}}\times{{\Omega_{M,N}}}}$
solution of Equation 1 such that
${\mathbf{Y}}\in\mathbb{R}^{{\Omega_{M/r,N/r}}}\mapsto\boldsymbol{\Lambda}^{T}{\mathbf{Y}}\in\mathbb{R}^{{\Omega_{M,N}}}$
corresponds to a convolution on each of the shifted subgrids
${\Omega^{k,\ell,r}_{M,N}}$, $k,\ell\in[r]$. More precisely,
$\boldsymbol{\Lambda}$ is fully determined by its $r^{2}$ first columns
$\boldsymbol{\lambda}(k,\ell)=\boldsymbol{\Lambda}_{{\Omega_{M/r,N/r}}\times(k,\ell)}$,
$k,\ell\in[r]$ and

$\left(\boldsymbol{\Lambda}^{T}{\mathbf{Y}}\right)({\Omega^{k,\ell,r}_{M,N}})=\widecheck{\boldsymbol{\lambda}}(k,\ell)\star{\mathbf{Y}}.$

The proof of Proposition 1 relies on the fact that both ${\mathbf{X}}$ and
${{\mathbf{X}}_{\mathrm{LR}}}={\mathbf{A}}{\mathbf{X}}$ are stationary on
their respective domains. Consequently, it is sufficient to solve the $r^{2}$
equations

${\mathbf{A}}{\boldsymbol{\Gamma}}{\mathbf{A}}^{T}\boldsymbol{\lambda}(k,\ell)={\mathbf{A}}{\boldsymbol{\Gamma}}_{{\Omega_{M,N}}\times(k,\ell)},\quad
k,\ell\in[r]$ (2)

to fully determine the kriging component of
${\mathbf{X}}|{{\mathbf{X}}_{\mathrm{LR}}}$. Remark that the matrix
$\boldsymbol{\Lambda}$ is determined by $MN$ values, the size of the HR image.

###  3.3 Resolution of the systems

To determine the kriging component, it is sufficient to solve the $r^{2}$
systems of Equation (2). We will use the Lemma 1.

######  Lemma 1 (Convolution and subsampling).

If ${\mathbf{B}}$ is a 2D convolution on ${\Omega_{M,N}}$ by the kernel
$\boldsymbol{\beta}\in{\Omega_{M,N}}$,
${\mathbf{S}}{\mathbf{B}}{\mathbf{S}}^{T}$ is a convolution on
${\Omega_{M/r,N/r}}$ by the kernel
${\mathbf{S}}\boldsymbol{\beta}\in{\Omega_{M/r,N/r}}$.

By Lemma 1, ${\mathbf{A}}{\boldsymbol{\Gamma}}{\mathbf{A}}^{T}$ is a
convolution matrix with kernel
${\boldsymbol{\kappa}}={\mathbf{S}}(\mathbf{c}\star\boldsymbol{\gamma}\star\widecheck{\mathbf{c}})$
where $\mathbf{c}$ is the kernel of ${\mathbf{C}}$. The Equations (2) become

${\boldsymbol{\kappa}}\star\boldsymbol{\lambda}(k,\ell)={\mathbf{A}}{\boldsymbol{\Gamma}}_{{\Omega_{M,N}}\times(k,\ell)},\quad
k,\ell\in[r]$ (3)

and we can easily pseudo-invert the convolution by component-wise division in
the Fourier domain.

The full FFT-based procedure is given by Algorithm 1. Note that to avoid
artefacts due to non-periodicity of the images, as classically done, we use
the periodic plus smooth decomposition [20] to make the spectral computations.
To work with non-zero mean images, the mean grayscale of the LR image should
be subtracted at the beginning of the algorithm and added at the end. For RGB
color images, the operations should be led on each channel. Note that the
Gaussian noise ${\mathbf{W}}$ to generate the ADSN textures should be the same
for each channel [16], as done for the results prensented in Figure 1.

1

Input: An image
${{\mathbf{U}}_{\mathrm{LR}}}\in\mathbb{R}^{{\Omega_{M/r,N/r}}}$, $r$ the zoom
factor, $\mathbf{t}$ the convolution kernel of the ADSN model, $\mathbf{c}$
the kernel of the convolution of the zoom-out operator
${\mathbf{A}}={\mathbf{S}}{\mathbf{C}}$

2 Step 1: Computation of kriging matrix $\boldsymbol{\Lambda}$

3Store $\operatorname{\textbf{per}}(\mathbf{t})$ the periodic component of
$\mathbf{t}$;

4

5Store the convolution kernels
$\boldsymbol{\gamma}=\operatorname{\textbf{per}}(\mathbf{t})\star\textbf{p$\widecheck{\textbf{e}}$r}(\mathbf{t})$,
$\mathbf{c}\star\boldsymbol{\gamma}$ and
${\boldsymbol{\kappa}}=\mathbf{c}\star\boldsymbol{\gamma}\star\widecheck{\mathbf{c}}$
(computed in Fourier);

6

7for  _$(k,\ell)\in[r]^{2}$_ do

8
$\widehat{{\mathbf{b}}}=\mathscr{F}_{2}\Big{(}{\mathbf{S}}((\mathbf{c}\star\boldsymbol{\gamma})(\cdot-k,\cdot-\ell))\Big{)}$
;

9

10
$\widehat{\boldsymbol{\lambda}}(k,\ell)\left[\widehat{{\boldsymbol{\kappa}}}\neq
0\right]\leftarrow$
$\frac{\widehat{{\mathbf{b}}}[\widehat{{\boldsymbol{\kappa}}}\neq
0]}{\widehat{{\boldsymbol{\kappa}}}[\widehat{{\boldsymbol{\kappa}}}\neq 0]}$;

11 end for

12

13Step 2: Sampling of one SR version of ${{\mathbf{U}}_{\mathrm{LR}}}$;

14 Generate ${\mathbf{W}}\in\mathbb{R}^{{\Omega_{M,N}}}$ following a Gaussian
standard law;

15 $\tilde{{{\mathbf{X}}}}\leftarrow\mathbf{t}\star{\mathbf{W}}$;

16
${\tilde{{{\mathbf{X}}}}_{\mathrm{LR}}}\leftarrow{\mathbf{A}}\tilde{{{\mathbf{X}}}}$;

17

18for  _each shifted subgrid by $(k,\ell)\in[r]^{2}$_ do

19
${{\mathbf{X}}_{\mathrm{SR}}}({\Omega^{k,\ell,r}_{M,N}})\leftarrow\mathscr{F}_{2}^{-1}\left((\widehat{{\mathbf{U}}}_{\mathrm{LR}}-{\tilde{{{\mathbf{X}}}}_{\mathrm{LR}}})\odot\overline{\widehat{\boldsymbol{\lambda}}(k,\ell)}\right)+\tilde{{{\mathbf{X}}}}({\Omega^{k,\ell,r}_{M,N}})$;

20 end for

21

Output: ${{\mathbf{X}}_{\mathrm{SR}}}$

Algorithm 1 Pseudo-code of the Gaussian simulation for SR. To generate several
samples, only the step 2 should be re-run.

##  4 Super-Resolution with a reference image

LR image | Reference image | HR image | Kriging component | Bicubic |  SRFlow ($\tau=0$)
---|---|---|---|---|---
|  |  |  |  |
Evaluation metrics | Gaussian SR (ours) | WPP |  SRFlow ($\tau=0?9$)
PSNR (dB) $\uparrow$ SSIM $\uparrow$ LPIPS $\downarrow$ TIME (s) Kriging component  28.42 0.56 0.69 Bicubic $\mathbf{30.21}$ $\mathbf{0.65}$ 0.54 $\text{SRFlow}{(\tau=0)}$ $\underline{28.55}$ 0.54 0.63 0.47 (GPU) Gaussian SR (ours) 26.25 $\pm$ 0.05  0.42 $\pm$ 0.00 $\mathbf{0.12\pm 0.01}$ $\mathbf{0.01}$ (CPU) WPP 24.70 0.39 0.22 64.0 (GPU) $\text{SRFlow}{(\tau=0.9)}$ 27.33 $\pm$ 0.34  0.48 $\pm$ 0.02  0.20 $\pm$ 0.03 0.47 (GPU) |  |  |
LR image | Reference image | HR image | Kriging component | Bicubic |  SRFlow ($\tau=0$)
|  |  |  |  |
Evaluation metrics | Gaussian SR (ours) | WPP |  SRFlow ($\tau=0?9$)
PSNR (dB) $\uparrow$ SSIM $\uparrow$ LPIPS $\downarrow$ TIME (s) Kriging component  21.78 0.24 0.87 Bicubic $\mathbf{23.52}$ $\mathbf{0.45}$ 0.70 $\text{SRFlow}{(\tau=0)}$ 21.84 0.24 0.87 0.55 (GPU) Gaussian SR (ours) 18.99 $\pm$ 0.05  0.14 $\pm$ 0.01 $\mathbf{0.25\pm 0.01}$ $\mathbf{0.02}$ (CPU) WPP 21.12 0.21 0.42 77.0 (GPU) $\text{SRFlow}{(\tau=0.9)}$ 18.99 $\pm$ 0.38 0.14 $\pm$ 0.01 0.39 $\pm$ 0.04 0.55 (GPU) |  |  |
Fig. 2:  Gaussian SR with a reference image for a factor $\times 8$ and
comparison with other methods. Top: HR size $208\times 208$. Bottom: HR size
$256\times 256$. For the stochastic methods SR Gaussian and SRFlow, the table
has been realized on 200 samples. Note that our method outperforms in terms of
the perceptual LPIPS metric and execution time, while PSNR and SSIM are
optimal for blurry images, illustrating that these metrics are not relevant
for texture SR. Images from [21].

In the previous theoretical sections we used the ground truth HR version
${\mathbf{U}}$ to estimate the distribution of the Gaussian texture, making
the process impractical. In this section we demonstrate that the approach
extends to the context of SR with a reference image, the reference image being
used in place of the ground truth for modeling the ADSN distribution. Given an
LR texture
${{\mathbf{U}}_{\mathrm{LR}}}={\mathbf{A}}{\mathbf{U}}\in\mathbb{R}^{{\Omega_{M/r,N/r}}}$
and a reference HR texture
${{\mathbf{U}}_{\mathrm{ref}}}\in\mathbb{R}^{{\Omega_{M,N}}}$, we simply
replace the unkown ADSN kernel
$\mathbf{t}=\frac{1}{\sqrt{MN}}({\mathbf{U}}-m)$ by
$\mathbf{t}_{\mathrm{ref}}=\frac{1}{\sqrt{MN}}({{\mathbf{U}}_{\mathrm{ref}}}-m_{\mathrm{ref}})$
in Algorithm 1, assuming that the two microtextures are similar. We sample
${{\mathbf{X}}_{\mathrm{SR}}}=\boldsymbol{\Lambda}^{T}{{\mathbf{U}}_{\mathrm{LR}}}+(\tilde{{{\mathbf{X}}}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}\tilde{{{\mathbf{X}}}})$
where $\tilde{{{\mathbf{X}}}}$ has the distribution
$\operatorname{ADSN}({{\mathbf{U}}_{\mathrm{ref}}})$ and
$\boldsymbol{\Lambda}$ is the kriging matrix associated with
$\operatorname{ADSN}({{\mathbf{U}}_{\mathrm{ref}}})$. Two SR experiments are
given in Figure 2 where we evaluate and compare our results with two
competitive methods: Wasserstein patch prior (WPP) [13] and SRFlow [8].
WPP111https://github.com/johertrich/Wasserstein_Patch_Prior is deterministic
and proposes to use optimal transport in patch space in a variational
formulation for SR. The routine needs a reference image similar to ours.
SRFlow222Code and weights from https://github.com/andreas128/SRFlow is a
normalizing flow for sotchastic SR trained on natural images. The network
transforms a standard Gaussian latent variable into a SR sample given the LR
image. It depends on a temperature hyperparameter $\tau\in[0,1]$ that
modulates the variance of the latent variable. Both methods require GPU and
experiments were conducted using a NVIDIA V100 GPU. Visually, there are some
issues in the borders of the image generated by WPP and the output texture
tends to be blurry. The results of SRFlow with high temperature are too sharp
for the Gaussian texture input, probably a bias induced by the training set of
natural images that are often piecewise regular. The images obtained with SR
Gaussian (ours) have a more granular appearence, due to the innovation
component. However, the texture of details that breaks the stationary
assumptions are not retrieved as in the white spot in the second image. Let us
stress here that both WPP and SRFlow are designed for generic natural images
while our method only works on Gaussian textures.

To evaluate the different methods we report in Figure 2 the metrics Peak
Signal to Noise Ratio (PSNR), Structural SIMilarity (SSIM) and Learned
Perceptual Image Patch Similarity (LPIPS). PSNR is the logarithm of the mean-
squared error (MSE) between two images. SSIM is a metric which quantifies the
similarity of two images studying their luminance, contrast and structure
[22]. LPIPS is the norm between weighted features of a pre-trained
classification network and quantifies the perceptual similarity between two
images [23]. As illustrated by the results of Figure 2, PSNR and SSIM are not
adapted to evaluate the quality of the texture samples in our context. Indeed
the best solutions for this metric are always the most blurry solutions,
namely the bicubic interpolation, SRFlow with temperature $\tau=0$, and the
kriging component. The LPIPS metric is more relevant for SR of textures. For
this metric our Gaussian SR results are the best for both examples. Note also
that our algorithm runs very quickly using only a CPU.

To advocate for the irrelevance of the PSNR for stochastic texture SR, in our
Gaussian framework it can be shown that the MSE is lower for the blurry
kriging component than for the perfect SR samples.

######  Proposition 2 (Kriging component and MSE).

Let ${\mathbf{U}}\in\mathbb{R}^{{\Omega_{M,N}}}$ be a Gaussian texture,
${{\mathbf{U}}_{\mathrm{LR}}}={\mathbf{A}}{\mathbf{U}}$ its LR version,
${{\mathbf{U}}_{\mathrm{ref}}}$ a reference image, ${\boldsymbol{\Gamma}}$
such that
$\operatorname{ADSN}({{\mathbf{U}}_{\mathrm{ref}}})=\mathscr{N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$
and $\boldsymbol{\Lambda}$ associated to ${\boldsymbol{\Gamma}}$. Let
${{\mathbf{X}}_{\mathrm{SR}}}$ be a random image following the distribution of
the SR samples obtained with Algorithm 1, then

$\displaystyle\mathbb{E}_{{{\mathbf{X}}_{\mathrm{SR}}}}\left(\|{\mathbf{U}}-{{\mathbf{X}}_{\mathrm{SR}}}\|^{2}\right)$
$\displaystyle=\|{\mathbf{U}}-\boldsymbol{\Lambda}^{T}{{\mathbf{U}}_{\mathrm{LR}}}\|^{2}+\operatorname{Tr}({\boldsymbol{\Gamma}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}{\boldsymbol{\Gamma}}{\mathbf{A}}^{T}\boldsymbol{\Lambda})$
$\displaystyle\geq\|{\mathbf{U}}-\boldsymbol{\Lambda}^{T}{{\mathbf{U}}_{\mathrm{LR}}}\|^{2}.$

In other words, the kriging component
$\boldsymbol{\Lambda}^{T}{{\mathbf{U}}_{\mathrm{LR}}}$ has a lower MSE in
expectation than the perfect SR samples ${{\mathbf{X}}_{\mathrm{SR}}}$.

The inequality is due to the positiveness of the covariance matrix
${\boldsymbol{\Gamma}}-\boldsymbol{\Lambda}^{T}{\mathbf{A}}{\boldsymbol{\Gamma}}{\mathbf{A}}^{T}\boldsymbol{\Lambda}$
of the innovation component. This property is consistent with the fact that
computing $\mathbb{E}({\mathbf{X}}|{{\mathbf{X}}_{\mathrm{LR}}})$ aims to
minimize the mean squared error. This is a specific illustration of the well-
known regression to the mean problem in SR [24]. The same effect can be
observed for the network SRFlow with temperature $\tau=0$ which solves
deterministically the MSE problem [8].

##  5 Conclusion

This study solves the problem of stochastic SR for stationary Gaussian
textures. Such texture models constitute a base case for stochastic SR for
which all the computations are accessible, leading to an efficient algorithm
for stochastic SR and stochastic SR with a reference image. Our method
outperforms some state of the art methods in terms of execution time and LPIPS
metrics and we have demonstrated experimentally that the PSNR and the SSIM
metrics are not compatible with the evaluation of the perceptual quality of SR
samples for textures. This illustrates the necessity to study further the
performance on microtextures of generic stochastic SR models. Furthermore, the
presented method could be applied for other inverse problems involving non
invertible operators of the form convolution followed by subsampling.

Acknowledgements: The authors acknowledge the support of the project MISTIC
(ANR-19-CE40-005).

## References

  * [1] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A. Efros,  “Image-to-Image Translation with Conditional Adversarial Networks,”  in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 5967–5976.
  * [2] Joan Bruna, Pablo Sprechmann, and Yann LeCun,  “Super-Resolution with Deep Convolutional Sufficient Statistics,”  in 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Yoshua Bengio and Yann LeCun, Eds., 2016.
  * [3] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, and Wenzhe Shi,  “Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network,”  in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 105–114.
  * [4] Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy,  “ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks,”  in Computer Vision – ECCV 2018 Workshops, Laura Leal-Taixé and Stefan Roth, Eds., Cham, 2019, pp. 63–79, Springer International Publishing.
  * [5] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio,  “Generative Adversarial Nets,”  in Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, Eds. 2014, vol. 27, Curran Associates, Inc.
  * [6] Justin Johnson, Alexandre Alahi, and Li Fei-Fei,  “Perceptual losses for real-time style transfer and super-resolution,”  in European Conference on Computer Vision, 2016.
  * [7] Karen Simonyan and Andrew Zisserman,  “Very Deep Convolutional Networks for Large-Scale Image Recognition,”  in 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun, Eds., 2015\.
  * [8] Andreas Lugmayr, Martin Danelljan, Luc Van Gool, and Radu Timofte,  “SRFlow: Learning the Super-Resolution Space with Normalizing Flow,”  in Computer Vision – ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part V, Berlin, Heidelberg, 2020, pp. 715–732, Springer-Verlag,  event-place: Glasgow, United Kingdom.
  * [9] Durk P Kingma and Prafulla Dhariwal,  “Glow: Generative Flow with Invertible 1x1 Convolutions,”  in Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds. 2018, vol. 31, Curran Associates, Inc.
  * [10] Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J. Fleet, and Mohammad Norouzi,  “Image Super-Resolution Via Iterative Refinement,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1–14, 2022.
  * [11] Jonathan Ho, Ajay Jain, and Pieter Abbeel,  “Denoising Diffusion Probabilistic Models,”  in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds. 2020, vol. 33, pp. 6840–6851, Curran Associates, Inc.
  * [12] Yang Song and Stefano Ermon,  “Generative modeling by estimating gradients of the data distribution,”  in Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 11918–11930. Curran Associates Inc., Red Hook, NY, USA, 2019.
  * [13] Johannes Hertrich, Antoine Houdard, and Claudia Redenbach,  “Wasserstein Patch Prior for Image Superresolution,”  IEEE Transactions on Computational Imaging, vol. 8, pp. 693–704, 2022.
  * [14] Johannes Hertrich, Lan Dang Phuong Nguyen, Jean-François Aujol, Dominique Bernard, Yannick Berthoumieu, Abdellatif Saadaldin, and Gabriele Steidl,  “PCA Reduced Gaussian Mixture Models with Applications in Superresolution,”  Inverse Problems and Imaging , vol. 16, no. 2, pp. 341–366, 2022\.
  * [15] Pierrick Chatillon, Yann Gousseau, and Sidonie Lefebvre,  “A statistically constrained internal method for single image super-resolution,”  in 26th International Conference on Pattern Recognition, ICPR 2022, Montreal, QC, Canada, August 21-25, 2022. 2022, pp. 1322–1328, IEEE.
  * [16] Bruno Galerne, Yann Gousseau, and Jean-Michel Morel,  “Random Phase Textures: Theory and Synthesis,”  IEEE Transactions on Image Processing, vol. 20, no. 1, pp. 257–267, 2011.
  * [17] Bruno Galerne, Arthur Leclaire, and Lionel Moisan,  “Microtexture inpainting through Gaussian conditional simulation,”  in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 1204–1208.
  * [18] Bruno Galerne and Arthur Leclaire,  “Texture Inpainting Using Efficient Gaussian Conditional Simulation,”  SIAM Journal on Imaging Sciences, vol. 10, no. 3, pp. 1446–1474, 2017.
  * [19] Yuval Bahat and Tomer Michaeli,  “Explorable super resolution,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 2716–2725.
  * [20] Lionel Moisan,  “Periodic Plus Smooth Image Decomposition,”  Journal of Mathematical Imaging and Vision, vol. 39, no. 2, pp. 161–179, 2011.
  * [21] Bruno Galerne, Yann Gousseau, and Jean-Michel Morel,  “Micro-texture synthesis by phase randomization,”  Image Processing On Line, vol. 1, 2011.
  * [22] Zhou Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli,  “Image quality assessment: from error visibility to structural similarity,”  IEEE Transactions on Image Processing, vol. 13, no. 4, pp. 600–612, 2004.
  * [23] R. Zhang, P. Isola, A. A. Efros, E. Shechtman, and O. Wang,  “The Unreasonable Effectiveness of Deep Features as a Perceptual Metric,”  in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Los Alamitos, CA, USA, June 2018, pp. 586–595, IEEE Computer Society.
  * [24] C. Sønderby, J. Caballero, L. Theis, W. Shi, and F. Huszár,  “Amortised map inference for image super-resolution,”  in International Conference on Learning Representations, 2017.