\section{Introduction}
\label{sec:intro}

High-cadence astronomy is a relatively new field in observational astronomy.
Advances in hardware and software technology have made it possible to
stream large volumes of observational data over fast links to
clusters of computers that, in general, process the data
in one or more automated pipelines for scientific analysis.
The time available to do real-time analysis
is limited by the cadence of the instrument.
Therefore, additional and complementary scientific data analyses
are forced to shift to non-real time environments.
Here, all data accumulates over time and
the growth may vary in the range of 0.1--100~PB/yr
\citep{Becla}.
These volumes clearly challenge many aspects of contemporary
data management systems, which is also recognised by
\citet{Ivezic}.

Several instruments have shown impressive demonstrations of charting
the sky down to
a timescale of seconds,
e.g.,
the international LOFAR telescope \citep{vHW},
the Murchison Wide-field Array \citep[MWA;][]{Tingay},
the Australian Square Kilometre Array Path\-finder \citep[ASKAP;][]{Murphy}.
High-cadence observations in image-domain astronomy,
where sky regions are revisited many times
in relatively short periods,
produce overwhelmingly large amounts of data.
Optical and radio telescopes planned for the next decade will
generate even larger continuous data streams,
e.g.,
the Large Synoptic Survey Telescope \citep[LSST;][]{Lazio, Juric},
the additional Gound-based Wide Angle optical Camera \citep[GWAC;][]{SVOMGWAC}
of the Space-based multiband astronomical Variable Objects Monitor (SVOM),
BlackGEM \citep{Bloemen},
the Square Kilometre Array \citep[SKA;][]{Broekema}.

Although high-cadence instruments are
specifically designed to carry out their own unique science,
they share similar observational strategies.
The main ones being: high-speed, wide- or all-sky surveys,
searching for transient and variable sources on a variety of time scales
and gradually archiving full-source light-curve catalogues.
In this respect, the archive is considered the new Big Data laboratory,
equipped for making scientific discoveries in complex structured data.
However, such discoveries are only possible when
the infrastructure and software tools allow
continuous and simultaneous data mining,
statistical
modeling, machine learning and ad-hoc querying.

The optical Sloan Digital Sky Survey
\citep[SDSS;][]{York,Alam}
was the first instrument to seriously integrate a database system
into its survey design.
It uses a database-centric computing approach for
their large-scale scientific datasets.
SDSS data are cumulatively released to the
public in roughly annual cycles.
In this respect, SDSS is a low-cadence instrument since the
yearly updates of the full-source catalogue makes
the database essentially static.

On account of Gray's law to ship computations to the data
instead of data to the computations \citep{SzBl}
many algorithms are designed to run \emph{inside} the database engine.
Another design rule includes knowledge of the 50 most frequent and
intensive queries.
Since astronomical pipelines process the data in a structured way,
this allows one to optimise execution plans for known queries.

In the radio regime, the automated Transients Pipeline (TraP) of the international
LOFAR telescope adopted many database techniques
from SDSS \citep{Swinbank}.
The TraP applies source finding and fitting
to calibrated radio images after which,
per image, all image and source properties,
i.e.\ the \emph{source list},
are handed over to the data\-base.
Note that the images themselves are not stored in the database.
The loop of tasks of the TraP database consists in total of about
50
queries which
can be divided into four successive steps, all executed in bulk mode:
\begin{enumerate}
\item{load source list}
\item{cross-match source list with catalogue of known sources}
\item{update catalogue: maintain up-to-date statistical sky model}
\item{find/identify transient and variable sources or
other significant deviations from the sky model}
\end{enumerate}

Typical source lists for LOFAR survey-mode observations do not
exceed $10^3$ entries, whereas averages are less than $10^2$
for cadence modes as high as 10 seconds
\citep{Swinbank}.
The total number of unique sources in the LOFAR radio catalogue
is of the order $10^6$.
Long-term monitoring of the database tasks is essential
to predict pipeline performance
and understand the instrument as a whole.
Queries with poor scaling (e.g.\ exponential)
will eventually jam the processing.
Significant increases of cadence and/or source density
determine the critical limits of the system and
permitted types of observations.
\citet{Swinbank} show that the TraP run times increase linearly
with input size within the LOFAR observation constraints.

Source lists produced by optical instruments are in general much larger,
primarily due to the intrinsic higher resolution in combination with
the
increased
sensitivity.
Also the catalogues that represent the optical sky models
hold orders of magnitude more sources than their radio counterparts.
Therefore, one avoids naive implementations of the TraP
for optical instruments,
since the extrapolation of the source counts into the
optical spectrum will most probably break linear performance
or even in a best-case long-term linear performance scenario,
the processing time will pass the cadence time
at some point.

The planned wide-field optical telescope array BlackGEM
is dedicated to
measure optical emission from pairs of merging neutron stars and black holes
\citep{Bloemen}.
BlackGEM will start with 3 telescopes,
all of which will be located
at ESO La Silla, Chile.
MeerLICHT,\footnote{Check the current status at \url{www.meerlicht.org}}
a single BlackGEM telescope acting as a prototype,
is
coupled to the MeerKAT radio array
\citep[a precursor to SKA;][]{Brederode}
to operate in concert and allowing to study the optical--radio sky simultaneously
as a true multi-wavelength instrument.
Table~\ref{tab:BGMLchar} shows the characteristics
of a single BlackGEM telescope.
From a database--pipeline perspective, the most influential properties
are the source data size,
the source density
and the integration time,
where the latter determines the cadence.

\begin{table}[!t]
\begin{tabular}{ll||c|c}
\hline
\multicolumn{2}{l||}{Mirror diameter} & \multicolumn{2}{c}{65\,cm}  \\
\multicolumn{2}{l||}{FoV} & \multicolumn{2}{c}{2.7\,deg$^2$}  \\
\multicolumn{2}{l||}{CCD size} & \multicolumn{2}{c}{10,536\,$\times$\,10,536} \\
\multicolumn{2}{l||}{Resolution} & \multicolumn{2}{c}{$0.57''$/px}  \\
\multicolumn{2}{l||}{bits per px} & \multicolumn{2}{c}{16}  \\
\multicolumn{2}{l||}{Image size} & \multicolumn{2}{c}{222\,MB}  \\
\multicolumn{2}{l||}{Calib.~images per night} & \multicolumn{2}{c}{2$\times$(10\,bias + 5$\times$5\,flats) = 70}  \\
\multicolumn{2}{l||}{DB source data size} & \multicolumn{2}{c}{402\,B}  \\
\hline
\multicolumn{2}{l||}{Observation mode} & nominal & fast \\
\hline
\multicolumn{2}{l||}{Integration time} & 5\,min & 1\,min \\
\multicolumn{2}{l||}{Sensitivity} & 23\,mag & 21\,mag \\
\multicolumn{2}{l||}{Science images per night} & 120 & 600 \\
\multicolumn{2}{l||}{Data rate per night} & 42\,GB & 148\,GB \\
\hline
\end{tabular}
\caption{Characteristics of the MeerLICHT telescope,
a single BlackGEM prototype telescope.
DB source data size is the storage size that all properties
of single source would need when stored in a database.
We assume observation nights of 10\,hrs.
}
\label{tab:BGMLchar}
\end{table}

In this paper we
use the TraP-like queries as a baseline and
investigate its scalability
to the MeerLICHT environment.
We need to know to what extent the processing of
images with
source densities of 500,000 deg$^{-2}$
or source lists with hundreds of thousands of sources
is still feasible.

The paper is outlined as follows.
Section~\ref{sec:db} gives the rationale
behind the choice of a column-oriented relational database management system
(RDBMS).
Section~\ref{sec:perf} describes the
experimental set up of the performance tests,
the data
and the TraP queries that were adjusted and optimised.
The results are presented in Section~\ref{sec:res}
and concluded in
Section~\ref{sec:concl}.
Although all source codes are publicly available,
the Appendices show the relevant query snippets for readability.
\\

\section{Rationale for MonetDB, a column-oriented
relational database management system
}
\label{sec:db}

Non-relational databases, e.g., key-value and NoSQL stores, lack
solid support for many data manipulations that are required
for this type of astronomical application.
We cannot afford redundant or duplicate storage,
and therefore have to distribute the data over
a minimal set of related tables.
The absence of fast join and cross-match functionality,
schema free storage formats, no transactional support
and own unique query languages
makes non-relational databases
hard to perform on such applications.
Furthermore,
the bulk processing requires fast data aggregation,
ordering and indexing
to avoid large table scans.
All these functionalities are well-known and implemented
in relational database systems.

Relational database storage models
follow either the
row-oriented or column-oriented principles.
The row\hyp{}oriented storage model partitions tabular data horizontally.
Such record layouts consist of rows that store all their columns contiguously,
with the adverse effect that a data block contains multiple data types.
Queries that touch only a few columns of a large table or
joins of tables,
waste both bandwidth and memory space in this model,
because the blocks that the CPU reads and buffers are contaminated
with all the other, unwanted, columns.
\citet{Abadi08} discuss more differences between row and column stores.

The columnar model splits tabular data vertically.
Every column is represented by an array of single data type.
These kinds of array can be manipulated easily and scanned quickly
when sorted.
Its variables of fixed size are densily stored, possibly in compressed format, on disk.
The uniformity of the array fits well to the block-oriented nature
of memory transfers and CPU caches
and exposes good spatial locality
and high cache hit ratios
when queries execute large scans over a subset of columns.
More in-depth details of column-oriented databases can be found
in \citet{Abadi12}.

More research and developments in the field of column-oriented databases
led to the implementation of many related techniques in the open-source
main-memory relational database management system MonetDB \citep{Boncz}.
MonetDB's architecture is geared toward read-optimised data\hyp{}intensive scientific applications
\citep{Marcin}.
It is compliant with the SQL-2008 standard
and has language bindings for \texttt{C}, \texttt{Java}, \texttt{Python},
\texttt{R}
and \texttt{Java\-Script/Node.js}.
The ease of extending its functionality with
user-defined functions (UDFs) written in \texttt{SQL},
\texttt{C}, \texttt{R} and \texttt{Python} are other serious strengths.
MonetDB follows a strict columnar design and takes into
account the underlying computer architecture
\citep{BMK99, Heman}.
The fundamental removal of the expression interpreter
fully eliminates parsing expensive code,
verifying record layouts and checking data types.
Hard-coded semantics makes MonetDB's algebra simple yet
efficient, because all operators work on simple arrays
allowing the compiler to generate CPU-friendly instructions.
Column-at-a-time processing reduces
the number of function calls
and data and control dependencies,
which in turn improve the algorithms and the CPU cache performance,
as opposed to tuple-at-a-time iterators.
Look-up and range queries benefit from
hash-indexes and secondary \emph{imprints} indexes, resp.,
that are automatically built for touched columns
\citep{Lefteris}.
A query optimiser generates and analyses alternative
query plans and executes the plan that minimizes the query cost.
\citet{Stefan} developed cost models that
estimate the query execution time based on I/O and average CPU costs.
\citet{Ivanova13} extended MonetDB's code base
to support SQL management of external data (SQL/MED).
Loading binary columnar catalogue \texttt{FITS} files
in this way
is orders of magnitude faster
than using classical
statements,
since the in-memory binary data exactly matches MonetDB's storage model.

Until now, the largest database archive for a single telescope is
the SDSS SkyServer
tuned to the commercial closed-source row store Microsoft SQL Server.
Full-sized data releases were successfully ported into MonetDB.
\citet{Ivanova} demonstrated that MonetDB is capable of loading
and querying the SDSS SkyServer data.
Initial performance evaluations on a smaller subset indicated that
85\% of the most executed queries
run faster in MonetDB, while the remaining are of competitive speed.
Most of the time scientific queries only touch a few columns,
whereas the tables generally have many hundreds of columns.
This is a strong call for using column-oriented databases

In all our experiments we use the Structured Query Language (SQL)
to interact with the data.
SQL queries access data directly and return aggregated or full result sets,
in contrast to scripts that retrieve data sets and
process tuples iteratively.
(Note that in this context a query is a generic term for any kind of
instruction set(s) that run on database data.)
Query response times are critical in high-cadence pipeline applications.
Because it is more efficient to process data in bulk mode,
the fact that data access is fastest close to the CPU
and that astronomical queries very often work on columns or ranges thereof,
the choice for a main-memory column-oriented database
in astronomical pipelines is obvious.

During database kernel and pipeline query development we
ran comparison tests with main alternative open source RDBMSs regularly.
However, reports of these results are beyond the scope of this paper.

\section{Baseline and alternative high-cadence pipeline benchmarks}
\label{sec:perf}

\subsection{BlackGEM pipeline architectures}
\label{sec:pipearch}

BlackGEM will produce about 1\,TB of data per night
of which 90\% are raw and calibrated images and 10\%
extracted information for the full-source database.
Raw data are calibrated and imaged after which
the source-extraction output product is
a list of all detected sources and their properties
in binary catalog FITS format.

A primary image-differencing pipeline runs in real time
to detect transient and variable events in the data stream
of calibrated images.
For differencing it uses reference images and
parts of the source list for PSF fitting.
The output product is a binary catalog FITS file of
all transient sources, which will be stored in a separate
relatively small transient-source database,
which will not be discussed any further here.

The full-source binary catalog FITS files
serve as input for a secondary
pipeline that runs in an offline mode
and consistently stores all sources into the full-source database for
scientific analysis.
Delays in this mode are acceptable up to the point where
the overall cadence is not being met anymore.
This paper concentrates on the secondary pipeline
and its full-source database.
The high cadence and source densities of BlackGEM and MeerLICHT
force us to carefully monitor the long-term run-time performance
of the pipeline queries,
especially since they run in a dynamically growing database.

The pipeline processes the data in a number of steps described in \S~\ref{sec:intro}.
After the sources have been loaded into the database (step 1),
read, write and delete queries take care of the source association
and sky model maintenance procedures
(steps 2 and 3).

It needs to be noted here that
transactions in MonetDB follow the optimistic concurrency control scheme.
The lack of a locking scheme implies that queries modifying the data
(of which we have many) are serialized at the application level
and run in single-threaded mode.
Explicitly programmed multiple threads with own database connections
can run in parallel easily if the query's write operations
are executed on independent tables, however,
we did not code that in our modules.
On the other hand, queries that only read data
run in parallel multi-threaded mode implicitly.

\subsection{IPHAS data}
\label{sec:iphas}

Before BlackGEM is operational
we process real binary catalogue \texttt{FITS} files
from the Isaac Newton Telescope (INT) Photometric
H$\alpha$ Survey of the Northern Galactic Plane
\citep[IPHAS;][]{Barentsen}.
The $10\sigma$ limit is at magnitude 20 and the field of view is 0.29~deg$^2$.
IPHAS has about 200 observations per night,
where single source lists range between 1,000 and 130,000 entries,
with peaks up to 170,000.

\subsection{The SciLens cluster}

We run our experimentation queries on multiple nodes of the
SciLens\footnote{\url{http://www.scilens.org}}\footnote{For
the current status and overview of the configuration, see
\url{https://www.monetdb.org/wiki/Scilens-configuration-standard}}
cluster located at CWI.
Our queries ran on single cluster nodes,
to which the input files were transfered.
Table~\ref{tab:SciLconfig} gives an excerpt of the specifications
of the nodes that we used.

\begin{table*}[!t]
\centering
\begin{tabular}{ll||c|c|c|c}
\hline
\multicolumn{2}{c||}{}    & \textbf{diamonds} & \textbf{stones} & \textbf{bricks} & \textbf{rocks} \\
\hline
\hline
\textbf{CPU}   & Architecture   & \multicolumn{4}{c}{x86\_64}  \\
\cline{3-6}
 & CPU(s)   & 96 & \multicolumn{2}{c|}{32} & 8 \\
\cline{3-6}
 & Threads per core   & \multicolumn{4}{c}{2}   \\
\cline{3-6}
 & Cores per socket   & 12 & \multicolumn{2}{c|}{8} & 4 \\
\cline{3-6}
 & Socket(s)   & 4 & \multicolumn{2}{c|}{2} & 1 \\
\cline{3-6}
 & Clockspeed & $2.4-2.9$\,GHz & $2.6-3.4$\,GHz & $2.0-2.8$\,GHz & $3.4-3.8$\,GHz\\
\hline
\textbf{RAM} & Size   & 1024\,GB & \multicolumn{2}{c|}{256\,GB} & 16\,GB\\
\hline
\textbf{SSD} & Drives   & \multicolumn{2}{c|}{} & $8\times128$\,GB & \\
\cline{3-6}
             & \texttt{/ssd}   & \multicolumn{2}{c|}{} & 8x HW RAID0    & \\
\hline
\textbf{HDD} & Disks   & $4\times2$\,TB & $3\times3$\,TB & $4\times2$\,TB & $1\times2$\,TB\\
\cline{3-6}
             & \texttt{/scratch} & 7.2\,TB       & \multicolumn{2}{c|}{5.4\,TB} & 1.8\,TB \\
             &                   & ($4\times$\ HW RAID0) & \multicolumn{2}{c|}{(3$\times$\ SW RAID0)} & \\
\cline{3-6}
             & \texttt{/data}   &   & 3$\times$0.9\,TB & 1.8\,TB & \\
\hline
\textbf{Network} & Ethernet   & $2\times10$\,Gb/s & \multicolumn{3}{c}{1\,Gb/s} \\
\cline{3-6}
                 & Infiniband & $4\times40$\,Gb/s & \multicolumn{3}{c}{40\,Gb/s} \\
\hline
\textbf{Software} & OS & \multicolumn{4}{c}{Linux, Fedora 24 4.7.3-200.fc24}    \\
\cline{3-6}
                  & MonetDB & \multicolumn{4}{c}{Jun2016 SP1}    \\
\cline{3-6}
                  & Python & \multicolumn{4}{c}{2.7.12}    \\
\hline
\end{tabular}
\caption[]{Configuration of SciLens cluster nodes}
\label{tab:SciLconfig}
\end{table*}

\subsection{Baseline pipeline and query monitoring}
\label{sec:monitor}

We
used
the May 2007 binary catalogue \texttt{FITS} files as
input for the prototype pipeline.
The series consists of 1893 files, where each \texttt{FITS} file has
four extensions
due to the four CCDs of the telescope.
The \texttt{Python} prototype pipeline script is based on the TraP \citep{Swinbank}
and was modified for the load and
cross-match stages (steps 1 and 2)
before it could serve as the baseline pipeline.

The most significant change in the data loading of step 1 was the replacement
of the classical SQL insert statements with
SQL/MED queries \citep{Ivanova13}.
This technique \emph{attaches} datasets to the database that can be queried
before they are actually loaded.
Larger files, i.e., longer source lists, can be handled, because
the data do not need to be parsed.
In step 2, the variable conical search radius that is being used
for cross-matching radio
sources was set as a constant parameter because of
the more stable quality of optical images
(see \S~\ref{sec:cm} below).

All individual query run times are written to log files
for easy plotting
and identification of CPU and I/O intensive queries.
Sets of queries that belong to a step as described in \S~\ref{sec:intro}
and \S~\ref{sec:pipearch}
are grouped together and prefixed \texttt{I} or \texttt{A}
for loading/inserting or cross-matching/associating, resp.
The modified
TraP, as described in the previous paragraph,
is considered as the baseline
pipeline
to which the query optimisations will be compared.

All source code presented in this paper is publicly and freely
available for download and usage at the CWI
\texttt{git}-repository
site.\footnote{\url{https://scm.cwi.nl/DA/blackgem-code}. The git version
used for this paper was \texttt{3ad947789a19}.}
It also provides instructions to get started.

\subsection{Cross matching and baseline module \texttt{M0}}
\label{sec:cm}

We adopted the set of TraP source association queries,
including the cross-match query,
and modified it slightly
for the processing of optical data.
This then is our baseline module \texttt{M0}.
The source association queries are the most intense and sensitive database operations,
where a source list
is cross-matched with the internal catalogue of known sources.
At the core of this query
is the positional source look-up by a conical search.
From SDSS SkyServer log analyses
\citet{Ivanova} found
that these conical searches
were part of the most frequently executed queries.
Optimising this will minimize CPU time and
compensate processing times for other queries.

The cross-matching method applied here is based on the
TraP source association
described in \S~4 of \citet{Swinbank}.
In that paper it was also shown that the association algorithms scale
reasonbly linear with the number of sources.
Source lists in their performance tests, however,
do not exceed 1200 entries, which is acceptable in
the radio domain of LOFAR, but not
in the optical regimes of MeerLICHT and BlackGEM.
The TraP is untested for source densities
that are orders of magnitude larger,
making it plausible that we cannot
simply extrapolate the TraP test results
to the optical domain.

The resolution and positional uncertainties in the optical IPHAS images are more stable
compared to the LOFAR case, where the image resolutions
fluctuate due to more complex radio-specific calibrations and antenna dependencies.
Therefore, the TraP implements a variable search radius to cross-match sources,
but because the optical image quality is more stable
we can replace it in the query algorithm
by a simpler conical search radius of constant value
that is determined by the telescope's resolution element.

The cross-match baseline query is written out in
\ref{app:q0}.
It joins the sources from the latest appended source list
available in the \texttt{extractedsource} table
with the known catalogued sources stored in \texttt{runningcat\-a\-log}.
If the distance between a found source pair is less than
the search radius the pair is considered as a genuine association
and both \texttt{ID}s and distance are returned.
In fact, however, more properties are returned, but for
illustrative purposes they are omitted here.
It must be noted here that the cross-match query result set
does not contain only unique catalog source--extracted source pairs.
Multiple types of association pairs are possible, falling into
the categories of \emph{no association}, \emph{one-to-one},
\emph{many-to-one}, \emph{one-to-many} and \emph{many-to-many}.
The association module takes care of further processing these topologies,
which are described in detail by \citet{Swinbank}.

The on-sky distance is only calculated for
catalogue counterparts that lie within
the boxes centred at the source positions from the list.
The widths of the boxes are determined by the fixed search radius.
Both tables have an integer \texttt{zone} column of 8-bit data type,
that specifies the declination strip in which the source lies.
The box height gives which neighboring declination strips needs to be searched.
The on-sky search radius is constant, but expressed in RA
it varies depending on declination.
Therefore, the RA-box width increases when moving towards the celestial poles.
The user-defined \texttt{alpha()} function
determines the rate of inflation as given by
\citet{Gray}.

The distance in radians on the sky, $\vartheta$, between a measured source position,
$\mathbf{x}$,
and its candidate counterpart in the running catalogue,
$\mathbf{m}$,
is given by the dot product $\mathbf{x}^T\mathbf{m}=\cos\vartheta$,
where $\mathbf{x}$ and $\mathbf{m}$ are unit vectors.
However, when dealing with small angles the alternative
of using the sine function gives computationally more accurate results.
Therefore we use the arc-angle distance between $\mathbf{x}$ and $\mathbf{m}$
to determine $\vartheta$
\begin{equation}
\sin\tfrac{1}{2}\vartheta = \tfrac{1}{2} ||\mathbf{x} - \mathbf{m}||,
\end{equation}

The above mentioned box size and distance criteria
are declared in the cross-match baseline SQL statement
(see \ref{app:q0}).
Naive SQL execution plans in the case of large source lists
may downgrade the performance to unacceptable levels.
Therefore, we have to carefully design several alternative cross-match queries
that implement different search techniques
and corresponding query optimisations in order to evaluate their
performance under different circumstances.

In the next paragraph we will elaborate on alternative queries,
in a database schema where we
partition and sort the largest tables by declination.

\begin{figure*}[!t]
\centering
\includegraphics[width=0.35\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_accum_I1I2I3I4I5I6I7I8I9_revised}%
\includegraphics[width=0.6\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_bigO_I1I2I3I4I5I6I7I8I9_revised}
\caption{Accumulated (left-column graphs) and
instantaneous (right-column graphs) run times of the loading queries
in the alternative module \texttt{M5}
on the diamonds node in the SciLens cluster
with respect to the image sequence number and
the number of sources appended to the database, resp.
(See Table~\ref{tab:SciLconfig} for the node specifications.)
The thick (red) line in the left-column graphs shows
the growth of the appended number of sources,
which is a measure of the database size.
\texttt{I15--18} is the subset of queries that is responsible
for the database schema clean up.}
\label{fig:i_Q0}
\end{figure*}

\subsubsection{Alternative module \texttt{M5}}
\label{sec:descr_M5}

Data partitioning is a well-known concept in database
designs to control load balancing and performance.
Tables are divided into independent smaller (sub)tables,
which can be accessed at a finer level of granularity.
This functionality allows a table to be defined as a union of its partitions.
One then can query the parent table as if it is an autonomous
table.\footnote{%
More on the internals can be found at
\url{https://www.monetdb.org/Documentation/Cookbooks/SQLrecipes/DataPartitioning}.}
On the other hand, for finer control and better data locality one can query
individual partitions, which are tables,
to avoid access to partitions that are outside the query.
In module \texttt{M5} we investigate the performance of the cross-matching pipeline
where the largest tables are partitioned
horizontally into declination zones of one degree.

We force the
partition tables to be sorted according to declination,
which uses the system cores in parallel.
This means that when table rows need to be updated or appended,
the partition table is rewritten.
This is acceptable as most of the table chuncks are sorted
according to their original format.
Moreover, cross-matching will be
fast and can be done in memory,
since the tables are relatively small and in sorted order.
The partitioning scheme is also prepared to withstand database growth,
since the partition sizes do not exceed the expected number of
sources.
The relevant \texttt{M5} SQL code is shown in \ref{app:M5}.

\section{Presentation of experimental results}
\label{sec:res}

The baseline (\texttt{M0}, \S~\ref{sec:cm}) and alternative (\texttt{M5}, \S~\ref{sec:descr_M5}) modules
both have the same set of SQL/MED loading queries,
but a different set of cross-matching queries.
On the same type of node
the same loading queries compete for memory and CPU
with different sets of cross-matching queries from the respective modules.
Every cross-matching module has its specific methods of memory allocation
and data storage, which produce unequal loading behaviour.
Nevertheless, the variations between modules are small and therefore
\S~\ref{sec:results_loading} only presents
the loading query run times of the
alternative module \texttt{M5}.
In \S~\ref{sec:results_cm} we present the details of different
cross-matching modules
and in \S~\ref{sec:results_overall}
the overall performances.

\subsection{Loading part}
\label{sec:results_loading}

The loading part consists of nine queries
that first attach and load the binary \texttt{FITS} files into temporary tables
that are created on the fly (\texttt{I1}--\texttt{I3}),
then copy the \texttt{FITS} header data
and sources
over into permanent tables (\texttt{I4} and \texttt{I5}, resp.)
and finally clean up the schema (\texttt{I6}--\texttt{I9})
before the next file comes in.
The accumulated run-time performances
of the individual queries
and the growth of the number of sources in the database
with respect to the \texttt{FITS} image sequence
for the alternative module
\texttt{M5} on the diamonds
node are shown
in the left graph of
Fig.~\ref{fig:i_Q0}.
The thick (red) line in
this graph
represents
the number of sources in the database at the moment of query execution and
corresponds to the number of entries in the largest table,
which is a measure for the database size.
Although the number of sources increases irregularly,
the individual query run times accumulate linearly over time,
meaning a query runs equally fast at any moment.

The constant-time complexity $\mathcal{O}(1)$ is clearly visible
in the right
graph of
Fig.~\ref{fig:i_Q0},
where the individual query run times are plotted
versus the number of sources in the database.
Although there is some scatter on the nodes that have limited memory
in combination with the slower HDDs (not plotted here),
these queries run independent of the database size.
It is not possible to make a fair comparison with the loading query set
of the TraP as presented by \citet{Swinbank}, because they
do not separate the loading from the cross-matching in their
performance plots.
However, the flat performance of the SQL/MED queries for the
baseline and alternative modules allow the loading
of source lists that more than 100 times larger.

Queries \texttt{I3}, \texttt{I4} and \texttt{I5}
(spelled out in \ref{app:i3}, \ref{app:i4} and \ref{app:i5}, resp.)
contribute most
to the total load time.
Query \texttt{I3} is an SQL/MED procedure call.
After the \texttt{FITS} data have been attached
to the database by generating a fully queryable temporary table,
this call really loads the data into the database,
effectively making the data-vaults table permanent in the
database schema.
Query \texttt{I4} loads the header data,
common to all sources originating from the same \texttt{FITS} file,
into the \texttt{image} table as a single entry,
whereas \texttt{I5} appends all data from the
data-vaults table to the permanent
\texttt{extractedsource} table.
Such bulk inserts vary, but can be over $10^5$ entries (see \S~\ref{sec:iphas}).
The insertion of only
one entry
into the \texttt{image} table
is an expensive operation,
because all fifteen data types per entry have to be parsed.
Comparison to the other append/insert queries (\texttt{I1}, \texttt{I3} and \texttt{I5})
makes the effect more conspicuous,
where the cost of appending $10^5$ sources is low
since the SQL queries are aware of attaching binary data
and the data types.
However, all load queries run in constant time,
independent of the database
size with the ability to scale up even further.

\subsection{Cross-matching part}
\label{sec:results_cm}

After the sources from a \texttt{FITS} file have been inserted
the cross-matching procedure starts and
runs 15 to 46 queries
depending whether the baseline or alternative module was chosen.
The source list is cross-matched with counterparts
in the catalog of known objects.
As described in \S~\ref{sec:cm} this results in a candidate list that is
further sifted by subsequent queries to
resolve the various association types of source--object pairs that turn up.
\citet{Swinbank} discuss the different types and elaborate on
the devised steps, i.e., queries, to append the new source measurements
to existing or new light curves.
The final step is to update the statistical properties of the known
catalog sources to include the new measurements in the model.
Sources for which no counterparts were found are appended as new
entries in the catalog.

There are many queries involved in this module, but we will focus on
the query that performs the cross-matching.

\subsubsection{The baseline cross-match module \texttt{M0}}
\label{sec:res_M0}

The baseline cross-match module
consists of fifteen queries in total of which
the cross-matching query is labeled \texttt{Q11b}
(see \ref{app:q0}).
The graphs in Fig.~\ref{fig:a_M0} show the performance of
the cross-matching module as a whole (left column),
the \emph{other} queries (middle column)
and the individual cross-matching query \texttt{Q11b} (right column),
while the rows specify the types of node
on which the pipeline ran.

The left-column graphs show the run times summed over
all fifteen queries versus the image sequence number.
During a pipeline run the total run time to process
a single \texttt{FITS} image fluctuates heavily and
depends strongly on the growth rate of the database size.
Larger data input sizes will slow down the pipeline run.

From the right-column graphs it can be seen that the cross-matching query run times
are of the same order as the above mentioned summed query run times,
meaning that the pipeline run time
is determined by \texttt{Q11b}.
We have divided the cross-matching query run times in these graphs into
three consecutive parts according to their image sequence number:
the first 500 images, the middle part of images 500--1500 and
the remaining images starting from sequence number 1500.
This points out that cross matching is not only a function of number of query rows,
but also of database size,
since for the same number of rows
the query run times slow down as
the database fills up with sources.
Searching for counterpart candidates takes longer, since larger tables have to be scanned.

Comparisons of the run times of the cross-matching query to the other queries,
shown in the graphs in the middle column of Fig.~\ref{fig:a_M0},
reveal a difference of more than two orders of magnitude,
making the cross-matching query the most dominant one in module \texttt{M0}.
The middle graphs show that most queries evolve linearly in time
as the database size grows,
while only a few run in constant time independent of the database size.

It all indicates that
the cross-matching query and thus the baseline module scales with database size
in $\mathcal{O}(NM)$ time, where $N$ is the number of sources
in the database and $M$ the number of sources in the resulting candidate list,
which is approximately equal to the number of entries
in the source list originating
from the \texttt{FITS} file.

The pipeline performance on the \texttt{diamonds} and
\texttt{bricks} nodes are similar,
because for the former the RAM size is large enough
and for the latter RAM size is sufficient
in combination with the low latency storage access
of the SSDs.
On the \texttt{stones} and \texttt{bricks} nodes
some of the \emph{other} queries are memory bound.
The fast CPU of the \texttt{rocks} node does not compensate
its small RAM size,
which effect is more prominent
when the database size is larger.
In these cases the operating system starts memory swapping data
from RAM to disk,
a process that impacts the pipeline performance negatively.
The larger storage access latency for HDDs as compared to SSDs
makes the pipeline runs slower and less smooth on a \texttt{stones} node
than on a \texttt{bricks} node, despite its faster CPU.

\begin{figure*}[!p]
\centering
\includegraphics[width=0.29\hsize,valign=t]{diamonds2_q0Y_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{diamonds2_q0Y_iphas_Jun2016_hdd_r025_bigO_Q10Q12-24}%
\includegraphics[width=0.29\hsize,valign=t]{diamonds2_q0Y_iphas_Jun2016_hdd_r025_cm_Q11b}
\includegraphics[width=0.29\hsize,valign=t]{stones07_q0Y_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{stones07_q0Y_iphas_Jun2016_hdd_r025_bigO_Q10Q12-24}%
\includegraphics[width=0.29\hsize,valign=t]{stones07_q0Y_iphas_Jun2016_hdd_r025_cm_Q11b}
\includegraphics[width=0.29\hsize,valign=t]{bricks11_q0Y_iphas_Jun2016_ssd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{bricks11_q0Y_iphas_Jun2016_ssd_r025_bigO_Q10Q12-24}%
\includegraphics[width=0.29\hsize,valign=t]{bricks11_q0Y_iphas_Jun2016_ssd_r025_cm_Q11b}
\includegraphics[width=0.29\hsize,valign=t]{rocks008_q0Y_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{rocks008_q0Y_iphas_Jun2016_hdd_r025_bigO_Q10Q12-24}%
\includegraphics[width=0.29\hsize,valign=t]{rocks008_q0Y_iphas_Jun2016_hdd_r025_cm_Q11b}
\caption{
Query run times for cross-match module \texttt{M0}.
Per row the graphs show the run times for the different types of node
on which the pipelines ran; from top to bottom these are the
\texttt{diamonds}, \texttt{stones}, \texttt{bricks} and \texttt{rocks}
nodes.
(See Table~\ref{tab:SciLconfig} for the node specifications.)
The left-column graphs show the summed run times of all queries
(left vertical axis) of module \texttt{M0} with respect to
the image sequence number (horizontal axis).
The thick (red) line shows the actual accumulated
number of sources stored in the database
(right vertical axis) at the moment of \texttt{FITS} file processing.
The graphs in the middle column show the individual query run times
according to the database size,
which actually is the number of sources stored in the database
at the moment of query execution.
All but the cross-matching queries are shown.
The right-column graphs show the run times of the cross-matching query
with respect to the number of rows in the query result set,
which approximates the number of entries in the source list.
The run times are divided into three parts,
where the image sequences run from start to 500,
500 to 1500, and from 1500 up to the end.
}
\label{fig:a_M0}
\end{figure*}

\begin{figure*}[!p]
\centering
\includegraphics[width=0.29\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_bigO_Q13-23Q25-27Q29-31Q33-37Q40-49}%
\includegraphics[width=0.29\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_cm_Q32}
\includegraphics[width=0.29\hsize,valign=t]{stones10_q5N_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{stones10_q5N_iphas_Jun2016_hdd_r025_bigO_Q13-23Q25-27Q29-31Q33-37Q40-49}%
\includegraphics[width=0.29\hsize,valign=t]{stones10_q5N_iphas_Jun2016_hdd_r025_cm_Q32}
\includegraphics[width=0.29\hsize,valign=t]{bricks07_q5N_iphas_Jun2016_ssd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{bricks07_q5N_iphas_Jun2016_ssd_r025_bigO_Q13-23Q25-27Q29-31Q33-37Q40-49}%
\includegraphics[width=0.29\hsize,valign=t]{bricks07_q5N_iphas_Jun2016_ssd_r025_cm_Q32}
\includegraphics[width=0.29\hsize,valign=t]{rocks010_q5N_iphas_Jun2016_hdd_r025_inst_A-all}%
\includegraphics[width=0.29\hsize,valign=t]{rocks010_q5N_iphas_Jun2016_hdd_r025_bigO_Q13-23Q25-27Q29-31Q33-37Q40-49}%
\includegraphics[width=0.29\hsize,valign=t]{rocks010_q5N_iphas_Jun2016_hdd_r025_cm_Q32}
\caption{%
Query run times for cross-match module \texttt{M5}.
The left-column graphs show the summed run times of all queries
vs.\ the image sequence number.
The graphs in the right column show the cross-matching query
run times with respect to the number of sources in the database
($N$)
and the remaining queries that run in constant time
with respect to $N$
are shown in the middle column.
(See caption of Fig.~\ref{fig:a_M0} for further
descriptions of the graphs.)
The performance of the remaining queries of the module are depicted
in Figs.~\ref{fig:a_M5_max} and \ref{fig:a_M5_lin}.
}
\label{fig:a_M5_const}
\end{figure*}

\subsubsection{The partitioned cross-matching module \texttt{M5}}
\label{sec:res_M5}

In module \texttt{M5} the cataloged sources are distributed
over multiple tables according to their declination zone
as described in \S~\ref{sec:descr_M5}.
The number of rows a query touches
is now limited by the size of the partitioned tables,
which is for zone widths of 1~degree
two orders of magnitude smaller than the
unpartitioned version.
Query run times now only depend either
on the number of rows of partitioned tables or on the size of the result sets
instead of the size of the entire database.
This is nicely demonstrated in
Figs.~\ref{fig:a_M5_const} and \ref{fig:a_M5_lin},
where the run-time performance of all queries in
module \texttt{M5} are shown.

The cross-matching query, labeled \texttt{Q32}
in module \texttt{M5}, is shown in the right-column
graphs of Fig.~\ref{fig:a_M5_const}.
Because the partitioning restricts the number of sources,
the query run times do not depend on the database size anymore.
Therefore, in contrast with the
baseline
module,
the cross-matching run times do not hinge on
the image sequence number,
but are determined by the
number of entries in the result set,
i.e.\ the number of counterpart candidates,
which is approximately equal to the number of entries
in the source list.
This makes the \texttt{M5} cross-matching query to run
stable and faster over time than its counterpart in module
\texttt{M0}.

The summed query run times fluctuate irregularly
over the course of images,
as can be seen in the left column of Fig.~\ref{fig:a_M5_const}.
This originates from query contributions that depend
mainly on the input source-list size,
which varies from image to image,
but the run times never exceed the cadence time.
The middle graphs in Fig.~\ref{fig:a_M5_const} show all queries
that run in constant time.
It can be seen that for the different nodes
the scatter of the run times
increases with decreasing RAM size.
This is caused by queries that run in
linear-time complexity and
compete with all queries for the same memory resources.
Queries that depend on the number of rows need to
allocate a relatively larger percentage of total memory
on the nodes with smaller RAM sizes,
leaving a smaller amount to the remaining queries
which in turn results in longer query run times.

The small group of queries that scales linearly with the number of rows
are displayed in Figs.~\ref{fig:a_M5_max} and \ref{fig:a_M5_lin}.
Fig.~\ref{fig:a_M5_max} shows two queries of which the
run time increases linearly with respect to the database size.
The respective queries select the maximum \texttt{ID} value of the
growing tables of extracted (\texttt{Q12})
and cataloged sources (\texttt{Q19}).
Note that the latter is a \texttt{MERGE} table
of many partitions.
Since the number of unique sources is smaller than
the total number of extracted sources
the slope of query \texttt{Q19} is less steep.
Although it is not noticeable in these experiments,
but if we extrapolate the database size to larger numbers,
the run times will hit the cadence time at some point.
A fairly easy way to correct this part to run in constant time
would be to maintain the values at the application level.
However, a solution where the database itself keeps track of
statistical parameters, e.g., average, minimum, maximum,
standard deviation, is more elegant and is considered in future releases.

The graphs of Fig.~\ref{fig:a_M5_lin} show the
\texttt{M5} query run times that
do not run in constant time.
The areas of the query run times are confined to
certain regions.
Queries \texttt{Q46a} and \texttt{Q28} are working on the light-curve table
and take into account an order of magnitude more entries than
the queries that run over the catalog table with unique sources (\texttt{Q43a} and \texttt{Q24},
where the latter is hidden behind the markers of other query run times).
All four query run times depend on the number of sources
in the partitions, i.e., the source density.
Numbers of new datapoints appended to the light-curve table (\texttt{Q39})
do not exceed $10^6$,
whereas new entries for the extracted source table (\texttt{Q14})
and catalog table (\texttt{Q38})
both do not exceed the number of source list entries.
The graphs show that the performance is controlled and that the queries run at
acceptable speeds.

\begin{figure}
\centering
\includegraphics[width=0.7\hsize]{diamonds1_q5N_iphas_Jun2016_hdd_r025_bigO_Q12Q19}
\caption{%
Run time vs.\ number of sources in the database
of the two queries that call the
SQL \texttt{MAX} function in module \texttt{M5}
on the \texttt{diamonds} node.
}
\label{fig:a_M5_max}
\end{figure}

\begin{figure*}
\centering
\includegraphics[width=0.3\hsize,valign=t]{diamonds1_q5N_iphas_Jun2016_hdd_r025_cm_Q14Q24Q28Q38Q39Q43aQ46a}%
\includegraphics[width=0.3\hsize,valign=t]{stones10_q5N_iphas_Jun2016_hdd_r025_cm_Q14Q24Q28Q38Q39Q43aQ46a}\\
\includegraphics[width=0.3\hsize,valign=t]{bricks07_q5N_iphas_Jun2016_ssd_r025_cm_Q14Q24Q28Q38Q39Q43aQ46a}%
\includegraphics[width=0.3\hsize,valign=t]{rocks010_q5N_iphas_Jun2016_hdd_r025_cm_Q14Q24Q28Q38Q39Q43aQ46a}
\caption{%
Module \texttt{M5} queries that run in linear time.
The plots show the remaining queries that
depend on the number of rows,
which approximates the source list size.
Pipeline runs were on the different cluster nodes.
}
\label{fig:a_M5_lin}
\end{figure*}

\subsection{Overall pipeline runtime}
\label{sec:results_overall}

\begin{table*}[!t]
\centering
\begin{tabular}{cl||S[table-format=3.1]|S[table-format=3.1]|S[table-format=3.1]|S[table-format=3.1]}
\hline
module &  & \textbf{diamonds} & \textbf{stones} & \textbf{bricks} & \textbf{rocks} \\
\hline
\hline
\texttt{M0} & pipeline & 659.0 & 575.1   & 750.6 &  589.4 \\
            & query    & 658.4 & 572.7   & 749.8 &  585.6 \\
\hline
\texttt{M5} & pipeline &   9.6 &  14.8 &  12.0 &   23.2 \\
            & query    &   6.5 &   7.8 &   7.0 &   10.0 \\
\hline
\end{tabular}
\caption[]{Accumulated processing times (in ks) of
the modules for a complete pipeline run,
specified per type of node.
Node rows give the specific node on which the pipeline ran,
pipeline rows specify the total pipeline run time and
query rows report the total run times of all queries summed.
}
\label{tab:overall_ortho}
\end{table*}

Table~\ref{tab:overall_ortho} reports the total time of the pipeline runs and
the summed execution time of all queries, i.e.\ loading and cross-matching, for the
baseline and the alternative module,
specified per cluster node.
It shows that absolute increment of the pipeline overhead is
more prominent in the alternative module \texttt{M5}
than in the baseline module \texttt{M0}.
This is caused by fact that we do not include the query commit times in the
query runtime results.
The larger number of queries and thus commits in the alternative module contribute more
to the total pipeline runtimes.

The scalability of the baseline module \texttt{M0},
which extrapolates LOFAR's TraP pipeline from the radio to the optical domain,
is limited.
Most queries write data,
i.e.\ append or update,
and therefore most of the time
only one CPU core is being used.
The \texttt{M0} cross-matching query is CPU-bound on all nodes and
the full materialisation of the large intermediate results into memory
introduces significant degradations of the performance,
making it unfeasible to process the source lists within
MeerLICHT's cadence time.

Smaller scans over sorted partitioned tables and less complex computations
expose better instruction code locality and reduce intermediates
for the \texttt{M5} cross matching,
from which the overall \texttt{M5} pipeline performance distinctly benefits.
The \texttt{M5} cross-match query is about three orders of magnitude faster
and behaves linearly.
The queries in \texttt{M5} utilise the available resources differently,
since the cross-matching requires less CPU time.
All queries are bound to maximum row numbers and
finish execution within limited amounts of times.
Internal database index structures further speed up the
queries to run sublinear,
giving the pipeline an additional boost of a factor of two.
The partitioned database schema better predicts query behaviour
on the long term, controls the overall pipeline performance and
scales to larger numbers of sources.

\section{Conclusions}
\label{sec:concl}

High-cadence astronomical observatories have the potential
to building up extremely large databases of catalogued sources and
their light curves.
Making scientific discoveries with the use of databases
rely on the ability to efficiently grind the massive amounts of data.
In this work, we matched optimised Big Data storage models
to pipeline query access patterns in a layered
storage system.
The layers present the data in different formats,
going from coarse high-level overviews at the top (all-sky)
to the fine-grained details at the bottom tier (declination strip).

This work describes a scalable solution
for the full-source database
for the MeerLICHT and planned BlackGEM wide-field optical
telescopes.
We adopted the Transients Pipeline (TraP)
database schema and pipeline queries from the
LOFAR Transients Key Science Project
as a baseline
to ingest, process and store
optical data from binary catalog \texttt{FITS} files.
We investigated the database schemas and query modules to
optimise source cross matching and achieve
long-term sublinear run times for all pipeline queries.
We monitored all queries individually to study their long-term behaviour.
Experiments with real data from the IPHAS Survey showed that
the modified TraP baseline cross-match module is not scalable
towards optical source densities.
We developed an alternative cross-match module for
database schema and query optimisations
that improved the pipeline runs significantly.
The column-oriented database schema design
in which the data are partitioned horizontally according to declination strips
allows the data\-base to grow in size and
simultaneously to run all pipeline queries in
constant time,
making this the preferred schema for
processing large source lists at high cadence.

Cross-match algorithms of associating a new source list
with the stored known sources
are highly sensitive to their implementations.
The list of known sources is reduced significantly by
maintaining an up-to-date compact statistical \emph{sky model}.
After operations start,
the model's size settles relatively early and
therefore the cross-matching avoids
large scans over continuously growing tables.
We accelerated the cross-match positional look-ups by three orders of magnitude
with the use of MonetDB's default hash indexes on a single sorted column of declination values.
The overall pipeline speed was increased by two orders of magnitude.
Most queries run in constant time and only a few run in linear time
with known upper limits.

In related tests,
we noticed that the creation of a three-dimensional tree index structure
of the known cataloged sources becomes unbalanced after a while
and that tree rebuilds are expensive,
which slows down the pipeline run.
This makes the $k$d tree, where $k=3$ for the Cartesian co-ordinates,
not the appropriate index structure
in the sky model build-up
phase,
however, in a read-only static database it might well be
the preferred index structure for fast positional look-ups and cross-matching.
In this context, further Bkd tree performance investigations,
especially in the treatment of updating and removing points from the tree,
optimising memory buffer sizes, number of trees in memory and
tuning access to main memory
may demonstrate its usefulness in dynamic, distributed, databases.

Performance results showed that the processing of IPHAS data,
with similar average and peak source densities MeerLICHT
will encounter,
was feasible well within cadence limits of 25 seconds.
Source lists with average densities could be processed at
rates of 5 seconds per image on nodes with
modest CPUs and large RAM.

MeerLICHT's larger field of view implies larger source lists,
but the sublinear-time behaviour and scalability of most queries,
including the cross-matching,
will not affect the performance.
Queries that run in linear time will have similar performance for MeerLICHT,
since the dependence scales with source density and not
source list size for the most intense queries.
The assumption of 12 hours of observation per night and the
offline mode that allows delays due to peaks
will relax the criteria,
meaning that with the alternative database and
partitioning schema MeerLICHT full-source data can be processed
at the one minute cadence.

The BlackGEM array will consist of three telescopes,
where each one will observe a different patch of the sky and
will produce its own data stream, similar to MeerLICHT is doing.
This simplifies parallelisation at an early stage, where
the fields of view can be processed independently
by multiple threads and database connections working
on distinct partitions of the data.
The in-memory column-oriented data storage structures of MonetDB
matches with the data ingestion and pipeline-specific queries.
Independent parallel data streams will make the BlackGEM
full-source pipeline capable of processing
the data within its cadence time of one minute.

Development of the MonetDB database and the MeerLICHT \& BlackGEM
full-source pipeline continues,
where we will address improvements on data-partition querying, multi-dimensional tree indexing
and techniques to visualise data in full-source archives.

\section*{Acknowledgement}
      We would like to thank the referee for the comments and
      suggestions that improved the paper.
      BS and MK acknowledge funding from the
      Dutch National Science Organisation
      NWO under Grant
      \emph{P4164 NWO project Big Bang Big Data (628-002-004)}

\section*{References}


\section{Introduction}\label{ss:intro}
Dense depth estimation of a complex dynamic scene from monocular images is an important and well-studied problem in computer vision \cite{szeliski2010computer}. Recent developments in this area have gained great attention from several industries involved in augmented reality, autonomous driving, movies, robotics \cite{kumar2014markov, kumar2012bayes} \etc. Despite the recent research in solving this problem has provided some promising theory and results, its success depends on the \emph{accurate} estimates of 3D motion parameters \cite{kumar2017monocular, ranftl2016dense, zhou2017unsupervised, godard2018digging}.

\begin{figure}[t]
\begin{center}
\includegraphics[width=1.0\linewidth]{Figures/ambush_5.pdf}
\caption{\small{Given consecutive monocular perspective frame (a), (b) of a complex dynamic scene and the dense optical flow correspondences between them (d). Also, assume an approximate sparse depth prior for the reference frame is provided as input (c), then, our algorithm under the piecewise planar approximation of a dynamic scene gives per-pixel depth estimate for the next frame (f) without solving for any motion parameters. (e) ground-truth depth.} \label{fig:firstPageresult}}
\end{center}
\end{figure}
To our knowledge, almost all the existing \emph{geometric} solutions to this problem have tried to fit the well-established theory of rigid reconstruction in some way to solve per-pixel depth of \emph{dynamic} scenes \cite{noraky2018depth, kumar2017monocular, ranftl2016dense}. Hence, these extensions are intricate to execute and largely depends on per-object or per-superpixel \emph{reliable} motion estimates \cite{noraky2018depth, kumar2017monocular, ranftl2016dense, achanta2012slic}. The main issue with the available geometric frameworks is that, even if the depth for the first/reference frame is known, we must solve for per-superpixel or per-object 3D motion to obtain the depth for the next frame. Consequently, the composition of their objective function fails to utilize the depth knowledge and therefore, does not cascade the prior knowledge well. In this work, we argue that in a dynamic scene, if the depth for the reference frame is known then it's not obligatory to estimate 3D motion parameters to obtain the depth for the next frame. Hence, the rationale behind relative motion estimation as an essential paradigm for obtaining the depth of a complex dynamic scene seems rather {optional} under the prior knowledge about the depth of the reference frame and dense optical flow between frames. To endorse our claim, we propose an \textbf{alternative approach} which is easy to implement and allow us to get rid of the intricacy related to the optimization on $\mathbb{SE}$(3) manifold.

We posit that the recent geometric methods to solve this task have been bounded by their inherent dependence on the 3D motion parameters. Consequently, we present a different method to solve dense depth estimation problem of a dynamic scene. Inspired by the recent work \cite{kumar2017monocular}, we model the dynamic scene as a set of locally planar surfaces and constrain the change in the scene to be as-rigid-as-possible (ARAP). Recent work by Kumar \etal \cite{kumar2017monocular} uses local rigidity graph structure to constrain the movement of each local planar structure based on the homography \cite{malis2007deeper} and its inter-frame relative 3D motion. In contrast, we propose that the global ARAP assumption of a dynamic scene may not need explicit 3D motion parameters, and its definition just based on the 3D Euclidean distance metric is a sufficient regularization to supply the depth for the next frame.
To this point, one may ask ``\emph{Why ARAP assumption for a dynamic scene?}''

Consider a general real-world dynamic scene, the change we observe in the scene between consecutive time frame is not arbitrary, rather it is regular. Hence, if we observe a local transformation closely, it changes rigidly, but the overall transformation that the scene undergoes is non-rigid.  Therefore, to assume that the dynamic scene deforms as rigid as possible seems quite convincing and practically works well for most real-world dynamic scenes.

To realize our intuition, we first decompose the dynamic scene as a collection of moving planes. We consider K-nearest neighbors per superpixel \cite{achanta2012slic} (which is an approximation of a surfel in the projective space) to define our ARAP model. For each superpixel, we choose three points \ie, an anchor point (center of the plane), and two other non-collinear points. Since the depth for the reference frame is assumed to be known (for at least 3 non-collinear points per superpixel), we can estimate per plane normal for the reference frame, but to estimate per plane normal for the next frame, we need depth for at least 3 non-collinear points per plane $\S \ref{ss:pwsm}$. If per-pixel depth for the reference frame is known, then ARAP model can be extended to pixel level without any loss of generality. The only reason for such discrete planar approximation is the computational complexity.

Our ARAP model defined over planes does not take into account the depth continuity along the boundaries of the planes. We address it in the subsequent step by solving a depth continuity constraint optimization problem using the TRW-S algorithm  \cite{kolmogorov2006convergent} (see Fig.~\ref{ss:intro} for a sample result). In this work, we make the following contributions:
\noindent
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
\item We propose an approach to estimate the dense depth map of a complex dynamic scene that circumvents explicit parameterization of the inter-frame 3D motion. We specify as rigid as possible constraint for the depth estimation by expressing length consistency constrain directly on locally neighboring 3D points.
\item  Our algorithm under piece-wise planar and as rigid as possible assumption appropriately encapsulates the behavior of a dynamic scene to estimate per pixel depth.
\item  Although the formulation is shown to work ideally for the classical case of two consecutive frames, its incremental in nature and therefore, it is easy to extend to handle multiple frames without estimating 3D motion parameters. Experimental results over multiple frames show the validity of our claim $\S \ref{ss:experiment}$.
\end{itemize}

\section{Related Work and Our Motivation}
Based on our findings,  Li. H \cite{li2010multi} introduced the first method to directly estimate the 3D structure of a scene without explicitly estimating motion. However, this approach  solves 3D structure of a \textbf{rigid} scene and the formulation can handle few \textbf{sparse} points. Very recently, Ji \etal \cite{ji2017maximizing} extended the Li. H \cite{li2010multi} ``motion-free'' framework to solve \textbf{sparse} 3D structure of a \textbf{single} non-rigidly moving object using multiple frames (M view, N point) \cite{li2010multi}. In contrast, we propose a 3D motion free formulation that provides a \textbf{dense} depth map of the \textbf{entire dynamic scene} over frames by relying on global as-rigid-as-possible assumption. Recently, numerous papers have been published for the dense depth estimation of a dynamic scene from images. However, for brevity, in this paper, we limit our discussion to the recent papers that are motivated \emph{geometrically} to solve this problem, leading to the easy discourse of our contributions.

\begin{figure*}
\centering
\subfigure [\label{fig:concept1}] {\includegraphics[height=0.15\textheight]{Figures/Planeapproximation.pdf}}
~~\subfigure [\label{fig:concept2}] {\includegraphics[height=0.15\textheight]{Figures/ARAPGraph.pdf}}
\caption{\footnotesize{ (a) Piece-wise planar approximation of a dynamic scene. Each superpixel is assumed to be an approximation of a 3D plane in the projective space. The center of the plane is shown with a filled circle (anchor point). (b) Decomposition of the scene into a local graph structure. Locally rigid graph model with its k-nearest neighbor is shown for the reference frame and the next frame. }}
\label{fig:modelexpl}
\end{figure*}

To the best of our knowledge, two major class of work in the recent past has been proposed for dense depth estimation of an entire dynamic scene from two consecutive monocular images \cite{noraky2018depth, kumar2017monocular, ranftl2016dense}. However, all of these methods depends on explicit 3D motion estimation. These methods can broadly be classified as:

\noindent
{\it{(a) Object-level motion segmentation approach:}} Ranftl \etal \cite{ranftl2016dense} proposed a two/three-staged approach to solve dense monocular depth estimation of a dynamic scene. Given the dense optical flow field, the method first performs an object level motion segmentation using epipolar geometry \cite{hartley2003multiple}. Per-object motion segmentation is then used to perform object-level 3D reconstruction using triangulation \cite{hartley2003multiple}. To obtain a scene consistent depth map, ordering constraint and smoothness constraint were employed over Quick-shift superpixel \cite{vedaldi2008quick} graph to deliver the final result.

\noindent
{\it{(b) Object-level motion segmentation free approach:}} Kumar \etal \cite{kumar2017monocular} argued that ``in a general dynamic scene setting, the task of densely segmenting rigidly moving object or parts is not trivial''. They proposed an over-parametrized algorithm to solve this task without using object-specific motion segmentation. The method dubbed as ``Superpixel Soup'' showed that under two mild assumption about the dynamic scene \ie, (a) the deformation of the scene is locally rigid and globally as rigid as possible and (b) the scene can be approximated by piece-wise planar model, scale consistent 3D reconstruction of a dynamic scene can be obtained for both the frames with a higher accuracy. Inspired by locally rigid assumption, recently, Noraky \etal \cite{noraky2018depth} proposed a method that uses optical flow and depth prior to estimate pose and 3D reconstruction of a deformable object.

\noindent
{\bf{Challenges with such geometric approaches:}} Although these methods provide a plausible direction to solve this problem, its usage to real-world applications can be challenging \cite{ranftl2016dense, kumar2017monocular, noraky2018depth}. The major challenge with these approaches is to \textbf{correctly} estimate all conceivable 3D motion parameters from image correspondences. The method proposed by Ranftl \etal \cite{ranftl2016dense} estimates per-object relative rigid motion which is not a sensible choice if the object themselves are deforming. On the other hand method such as \cite{noraky2018depth, kumar2017monocular} estimates per superpixel/region relative rigid motion which is sensitive to the size of the superpixels and distance of the surfel from the camera.

The point we are trying to make is, given the depth for the reference frame of a dynamic scene, \emph{can we correctly estimate the depth for the next frame using the aforementioned approaches?}. Maybe yes, but then, we have to again estimate relative rigid motion for each object or superpixel and so on and so forth. Inspired by the ``as-rigid-as-possible'' (ARAP) intuition \cite{kumar2017monocular}, in this work, we show that if we know the depth for the reference frame and dense optical flow correspondences between the consecutive frames, then estimating relative 3D motion can be avoided. We can successfully estimate the depth for the next frame by exploiting as-rigid-as-possible global constraint. These depth estimate obtained using ARAP can further be refined using boundary depth continuity constraint.

The next concern could be \emph{why we are trying to abort the 3D motion data to solve this problem?} Firstly, as alluded to above, such formulation can help avoid involved optimization on $\mathbb{SE}(3)$ manifold. Secondly, it simplifies the underlying objective function which is relatively neat and easy to solve. Thirdly, it provides a distinct view to think about the behaviour of a dynamic scene which generally pivots around the confusion of structure motion and camera motion and its relative inference from image data. Lastly, it provides the flexibility to solve for depth at a pixel level rather than at an object level or superpixel level which is hard to realize using rotation and translation based approaches \cite{noraky2018depth,kumar2017monocular,ranftl2016dense}. Nevertheless, to reduce the overall computational cost, we stick to optimize our objective function at superpixel level.

\section{Piecewise Planar Scene Model}\label{ss:pwsm}
Inspired by the recent work on dense depth estimation of a general dynamic scene \cite{kumar2017monocular}, our model parameterizes the scene as a collection of piece-wise planar surface, where each local plane is assumed to be moving over frames. The global deformation of the entire scene is assumed to be as rigid as possible. Moreover, we assign the center of each plane (anchor point) to act as a representative for the entire points within that plane (see Fig.\ref{fig:modelexpl}). In addition to the anchor point of each plane, we take two more points from the same plane in such a way that these three points are non-collinear (see Fig.\ref{fig:smoothnessexpl}). This strategy is used to define our as rigid as possible constraint between the reference frame and next frame without using any 3D motion parameters. As the depth for the reference frame and the optical flow between the two successive frames is assumed to be known a priori, each local planar region is described using only four parameters ---normal and depth, instead of nine \cite{kumar2017monocular}.

Our model first assigns each pixel of the reference frame to a superpixel using SLIC algorithm \cite{achanta2012slic} and each of these superpixels then acts as a representative for its 3D plane geometry. Since the global change of the dynamic scene is assumed to be ARAP, the transformation that each plane undergoes from the first frame to the next frame should be as minimum as possible. The solution to global ARAP constraint supply depth for three points per plane in the next frame, which is used to estimate the normal and depth of the plane. The estimated depth and normal of each plane are then used to calculate per pixel depth in the next frame.

Although our algorithm is described for the classical two-frame case, it is easy to extend to the multi-frame case. The energy function we define below is solved in two steps: First, we solve for the depth of each superpixel in the next frame using as rigid as possible constraint. Due to the piece-wise planar approximation of the scene, the overall solution to the depth introduces discontinuity along the boundaries. To remove the blocky artifacts ---due to the discretization of the scene, we smooth the obtained depth along the boundaries of all the estimated 3D plane in the second step using TRWS \cite{kolmogorov2006convergent}. If the ARAP cost function is extended to pixel-level then the boundary continuity constraint can be avoided \cite{hornavcek2014highly}. Nevertheless, over-segmentation of the scene provides a good enough approximation of a dynamic scene and is computationally easy to handle.

\subsection{Model overview}
\noindent
{\bf{Notation:}} We refer two consecutive perspective image $\mathbf{I}$, $\mathbf{I}'$ as the reference frame and next frame respectively. Vectors are represented by bold lowercase letters, for \eg `${\bf{x}}$' and the matrices are represented by bold uppercase letters, for \eg `${\bf{X}}$'. The 1-norm,  2-norm of a vector is denoted as $|.|_1$ and $\|.\|_2$ respectively.

\subsection{As-Rigid-As-Possible (ARAP)}\label{ss:arap}
The idea of ARAP constraint is well known in practice and has been widely used for shape modeling and shape manipulation \cite{igarashi2005rigid}. Recently Kumar \etal \cite{kumar2017monocular} exploited this idea to estimate scale consistent dense 3D structure of a dynamic scene. The motivation to use ARAP constraint in our work is inspired by \cite{kumar2017monocular} idea.

Let ($d_i$, $d_j$) and ($\tilde{d_i}$, $\tilde{d_j}$) be the depth of two neighboring 3D points $i, j$ from the reference coordinate in the consecutive frames. Let $(u_i, v_i, 1)^{T}$, $(u_j, v_j, 1)^{T}$ be its image coordinate in the reference frame and $(\tilde{u_i}, \tilde{v_i}, 1)^{T}$, $(\tilde{u_j}, \tilde{v_j}, 1)^{T}$ be its image coordinate in the next frame. If `$\mathbf{K}$' denotes the intrinsic camera calibration matrix then, ${e_i} = \mathbf{K}^{-1}( u_i, v_i ,1)^{{T}}/\|\mathbf{K}^{-1}( u_i, v_i ,1)^{{T}}\|_2$, ${e_j} = \mathbf{K}^{-1}( u_j, v_j ,1)^{{T}}/\|\mathbf{K}^{-1}( u_j, v_j ,1)^{{T}}\|_2$ is the unit vector in the direction of the $i^{th}, j^{th}$ 3D point respectively for the reference frame. Similarly, the corresponding unit vectors in the next frame is denoted with $\tilde{e_i}, \tilde{e_j}$ (see Fig.~\ref{fig:concept1}). Using these notations, we define the ARAP constraint as:
\begin{equation} \label{eq:1}
\Phi^\textrm{arap} = \sum_{i=1}^{3N} \sum_{j \in \mathcal{N}_i^k} w_{ij}^{(1)} \Big| \underbrace{\|d_i{e_i}- d_j{e_j}\|_2}_\text{reference frame} - \underbrace{\|\tilde{d_i}\tilde{e_i} - \tilde{d_j}\tilde{e_j}\|_2}_\text{next frame}\Big|_1
\end{equation}
Here, $N$ is the total number of planes used to approximate the scene and $\mathcal{N}_i^{k}$ is the `$k$' neighboring planes local to $i^{th}$ superpixel (see Fig.~\ref{fig:concept2}). $ w_{ij}^{(1)}$ is the exponential weight fall off based on the image distance of the points.  $ w_{ij}^{(1)}$ parameter slowly breaks the rigidity constraint if the points are far apart in the image space. This constraint encapsulates our idea that the change in the distance of $i^{th}$ point relative to its local neighbors in the next frame should be as minimum as possible. Note that the summation goes over $3N$ rather than $N$ due the reason discussed in Sec. $\S \ref{ss:intro}$

\begin{figure}[t]
\begin{center}
\includegraphics[width=0.58\linewidth, height=0.42\linewidth]{Figures/depthSmoothness1.pdf}
\caption{\small{Intuition on orientation and shape regularization. Anchor point and two non-collinear points are shown in red and green respectively. Dark red line show the change in the next frame.} \label{fig:smoothnessexpl}}
\end{center}
\end{figure}

\subsection{Orientation and Shape Regularization}\label{ss:osr}
Solving the ARAP constraint provides us the depths for three non-collinear points per-plane for the next frame. We use these three depth estimate per plane to solve for their normals in the next frame. Let the 3D points corresponding to the three depths for $i^{th}$ superpixel in the next frame be denoted as $\tilde{\mathbf{x}}_{i}^{a}$, $\tilde{\mathbf{x}}_{i}^{1}$ and $\tilde{\mathbf{x}}_{i}^{2}$ respectively. We estimate the normals in the next frame as:
\begin{equation}\label{eq:2}
\tilde{\mathbf{n}}_i = \frac{(\tilde{\mathbf{x}}_{i}^{a} - \tilde{\mathbf{x}}_{i}^{1}) \times (\tilde{\mathbf{x}}_{i}^{a} - \tilde{\mathbf{x}}_{i}^{2})}{\|(\tilde{\mathbf{x}}_{i}^{a} - \tilde{\mathbf{x}}_{i}^{1}) \times (\tilde{\mathbf{x}}_{i}^{a} - \tilde{\mathbf{x}}_{i}^{2})\|_2},
\end{equation}
where superscript `$a$' is used intentionally to denote the anchor point, which is assumed to be at the center of each plane (see Fig.~\ref{fig:smoothnessexpl}). Rewriting Eq.~(\ref{eq:2}) in terms of depth
\begin{equation}\label{eq:3}
\tilde{\mathbf{n}}_i = \frac{(\tilde{d}_{i}^{a} \tilde{e}_{i}^a - \tilde{d}_{i}^{1} \tilde{e}_{i}^1) \times (\tilde{d}_{i}^{a} \tilde{e}_{i}^a - \tilde{d}_{i}^{2} \tilde{e}_{i}^2)}{\|(\tilde{d}_{i}^{a} \tilde{e}_{i}^a - \tilde{d}_{i}^{1} \tilde{e}_{i}^1) \times (\tilde{d}_{i}^{a} \tilde{e}_{i}^a - \tilde{d}_{i}^{2} \tilde{e}_{i}^2)\|_2}.
\end{equation}

\noindent
{\bf{(a) Orientation smoothness constraint:}} Once we compute the normal for each plane and 3D coordinates of the anchor point, which lies on the plane, we estimate the depth of the plane as follows
\begin{equation}\label{eq:4}
\tilde{\mathbf{n}}_i^{T}\tilde{\mathbf{x}}_{i}^{a} = \tilde{d}_{i}^{\pi_a}.
\end{equation}
The computed depth of the plane is then used to solve for per-pixel depth in the next frame ---assuming the intrinsic camera matrix is known \cite{kumar2017monocular,hartley2003multiple}.  To encourage the smoothness in the change of angles between each adjacent planes (see Fig.~\ref{fig:smoothnessexpl}), we define the orientation regularization as
\begin{equation}\label{eq:5}
\Phi_{ij}^\textrm{orient} = \lambda_1 \rho_1 \Big(1 - \frac{|\tilde{\mathbf{n}}_{i}^{T}\tilde{\mathbf{n}}_{j}|}{\|\tilde{\mathbf{n}}_{i}\| \|\tilde{\mathbf{n}}_{j}\|}\Big),
\end{equation}
where, $\lambda_1$ is an empirical constant and $\rho_{1}(x)$ = $\min(|x|, \sigma_1)$ is the truncated $l_1$ function with $\sigma_1$ as a scalar parameter.

\noindent
{\bf{(b) Shape smoothness constraint:}} In our representation, the dynamic scene model is approximated by the collection of piecewise planar regions. Hence, the solution to per-pixel depth obtained using Eq.~(\ref{eq:1}) to Eq.~(\ref{eq:4}) may provide discontinuity along the boundaries of the planes in 3D (see Fig.~\ref{fig:smoothnessexpl}). To allow smoothness in the 3D coordinates for each adjacent planes along their region of separation, we define the shape smoothness constraint as
\begin{equation}\label{eq:6}
\begin{aligned}
\Phi^\textrm{shape}=\sum_{(i, j) \in N_{b}} w_{ij}^{(2)}\rho_2(\underbrace{\|d_i{e_i}- d_j{e_j}\|_2^2}_\text{reference frame} + \underbrace{\|\tilde{d_i}\tilde{e_i} - \tilde{d_j}\tilde{e_j}\|_2^2}_\text{next frame}).
\end{aligned}
\end{equation}
\noindent
The symbol `$N_{b}$' denotes the set of boundary pixels of $i^{th}$ superpixel that are shared with the boundary pixel of other superpixels. The weight $w_{ij}^{(2)}$ = $\exp(-\beta \|\mathbf{I}_i - \mathbf{I}_j\|_2)$ takes into account the color consistency of the plane along the boundary points ---weak continuity constraint \cite{blake1987visual}. Since all the pixels within the same plane are assumed to share the same model, smoothness for the pixels within the plane is not essentially required. Similar to orientation regularization, $\rho_{2}(x)$ = $\min(|x|, \sigma_2)$ is the truncated $l_1$ penalty function with $\sigma_2$ as a scalar parameter. The overall optimization steps of our method is provided in {\bf{Algorithm}} ({\bf{\ref{algo:1}}}).

\begin{algorithm}[h!]
\label{Algorithm}
\caption{:~~\small{Dense Depth Estimation without using 3D motion}}
\begin{algorithmic}
{\small
\STATE {\bf{Input:}} ($\mathbf{I}, \mathbf{I}'$), optical\_flow($\mathbf{I}, \mathbf{I}'$), $\mathbf{K}$, depth for reference frame.

\STATE {\bf{Output:}} Dense depth map for the next frame.

\STATE {\fontfamily{cmtt}\selectfont 1:} Over-segment the reference frame into $N$ superpixels \cite{achanta2012slic}.
\STATE {\fontfamily{cmtt}\selectfont 2:} Assign anchor point for each superpixel and two other points in the same plane such that these three points are non-collinear (see Fig.~\ref{fig:smoothnessexpl}).
 \STATE {\fontfamily{cmtt}\selectfont 3:} Use K-NN algorithm over superpixels to get the K-nearest neighbor index set.
 \STATE {\fontfamily{cmtt}\selectfont 4:}  Solve for per-superpixel depth in the next frame $\S \ref{ss:arap}$
 {\fontfamily{cmtt}\selectfont
 \begin{equation}
 \begin{aligned}
 & \displaystyle  ~~\Phi^{\text{arap}} \rightarrow \underset{\tilde{d}_{i}} {\text{minimize}} \\
 & \displaystyle \text{subject to:} ~~\tilde{d}_{i} > 0,  ~~|\tilde{d}_{i} - d_i|< d_{i\sigma} (\textit{optional}) \\
 & \displaystyle \textrm{where,} ~d_{i\sigma} ~\textrm{is the variance in the depth.}\\
 \end{aligned}\label{eq:7}
 \end{equation}
 }
{\small{{{Note:}} The second constraint provides a trust region for the fast and proper convergence of a non-convex problem (Fig.\ref{fig:statsexperiment2}). Can be thought of as max/min restriction  to the scene deformation.}}
\STATE {\fontfamily{cmtt}\selectfont 5:} Estimate the normal of each plane in the next frame Eq.~(\ref{eq:3}).
\STATE {\fontfamily{cmtt}\selectfont 6:} Estimate the depth of each plane Eq.~(\ref{eq:4}).
\STATE {\fontfamily{cmtt}\selectfont 7:} Solve per pixel depth for the next frame using per plane depth $(\tilde{d}_{i}^{\pi_a})$, $\mathbf{K}$, normal of the plane and its image coordinate.
\STATE {\fontfamily{cmtt}\selectfont 8:} Refine the depth of the next frame by minimizing Eq.~(\ref{eq:5}), Eq.~(\ref{eq:6}) with respect to depth and normal \cite{kolmogorov2006convergent} $\S \ref{ss:osr}$.
{\fontfamily{cmtt}\selectfont
\begin{equation}
 \begin{aligned}
 & \displaystyle ~~(\Phi^{\text{orient}} + \Phi^{\text{shape}})\rightarrow \underset{\tilde{d}_{i}, \tilde{\mathbf{n}}_i} {\text{minimize}} \\
 & \displaystyle \text{subject to:} ~~\tilde{d}_{i} > 0, \|\tilde{\mathbf{n}}_i\| = 1.
 \end{aligned}\label{eq:8}
 \end{equation}
 }
\STATE {\fontfamily{cmtt}\selectfont 9:} ({\bf{Optional}}) For generalizing the idea to multi-frame, repeat the above steps by making the next frame as the reference frame and new frame as the next frame.}
\end{algorithmic}\label{algo:1}
\end{algorithm}

\section{Experimental Evaluation}\label{ss:experiment}
We performed the experimental evaluation of our approach on two benchmark datasets, namely MPI Sintel \cite{butler2012naturalistic} and KITTI \cite{geiger2013vision}. These two datasets conveniently provide a complex and realistic environment to test and compare our dense depth estimation algorithm. We compared the accuracy of our approach against two recent state-of-the-art methods \cite{kumar2017monocular,ranftl2016dense} that use geometric approach to solve dynamic scene dense depth estimation from monocular images. These comparisons are performed using three different dense optical flow estimation algorithms, namely PWC-Net \cite{Sun2018PWC-Net}, FlowFields \cite{bailer2015flow} and Full Flow \cite{chen2016full}. All the depth estimation accuracies are reported using mean relative error (MRE) metric. Let $\tilde{d}$ be the estimated depth and $\tilde{d}^{gt}$ be the ground-truth depth, then MRE is defined as
\begin{equation}
\textrm{MRE} = \frac{1}{P} \sum_{i=1}^{P} \frac{|\tilde{d}_{i}-\tilde{d}_{i}^{gt}|}{\tilde{d}_{i}^{gt}},
\end{equation}
where `$P$' denotes the total number of points. The statistical results for DMDE \cite{ranftl2016dense} and Superpixel Soup \cite{kumar2017monocular} are taken from their published work for comparison.

\noindent
\textbf{Implementation Details:} We over-segment the reference frame into 1000-1200 superpixels using SLIC algorithm \cite{achanta2012slic} to approximate the scene.
We use a fixed value of $d_{i\sigma}$ = 1 and $\mathcal{N}_{i}^{k}$ = 20-25 for all the experiments. For computing the dense optical flow correspondences between images we used  PWC-Net \cite{Sun2018PWC-Net}, FlowFields \cite{bailer2015flow} and Full Flow \cite{chen2016full} algorithm. The depth for the reference image is initialized using Mono-Depth \cite{godard2017unsupervised} model on the KITTI dataset and using Superpixel Soup algorithm \cite{kumar2017monocular} on the MPI-Sintel dataset. The proposed optimization is solved in two stages, firstly Eq.~(\ref{eq:7}) is optimized using SQP \cite{powell1978fast} algorithm and Eq.~(\ref{eq:8}) is optimized using TRW-S \cite{kolmogorov2006convergent} algorithm. The choice of the optimizer is purely empirical, and the user may choose different optimization algorithms to solve the same cost function. We implemented it using C++/MATLAB which takes 10-12 minutes on a commodity desktop computer to provide the result.

The implementation is performed under two different experimental settings. In the first setting, given the sparse (\ie for three non-collinear points per superpixel) depth estimate of a dynamic scene for the reference frame, we estimate the per-pixel depth for the next frame. In the second experimental setting, we generalize this idea of two frame depth estimation to multiple frames by computing the depth estimates over frames. For easy understanding, MATLAB codes are provided in the supplementary material showing our idea of ARAP on synthetic examples of a dynamic scene.

\begin{figure}
\begin{center}
\includegraphics[width=1.0\linewidth, height=0.15\textheight]{Figures/TwoFrameDenseResultsMPI.pdf}
\caption{\small{Depth results on the MPI Sintel dataset\cite{butler2012naturalistic} for the next frame under two frame experimental setting. $\mathbf{2^{nd}}$ and $\mathbf{3^{rd}}$ row show ours and ground-truth depth map results respectively.} \label{fig:MPItwoframe}}
\end{center}
\end{figure}

\subsection{MPI Sintel}
This dataset gives an ideal setting to evaluate depth estimation algorithms for complex dynamic scenes. It contains image sequences with intricate motions and severe illumination change. Moreover, the large number of non-planar scenes and non-rigid deformations makes it a suitable choice to test the piece-wise planar assumption. We selected seven set of scenes namely alley\_1, alley\_2, ambush\_5, bandage\_1, bandage\_2, market\_2 and temple\_2 from the clean category of this dataset to test our method.

\begin{table}
\centering
\scriptsize
\begin{tabular}{|>{\columncolor[gray]{0.88}}c|c|c|c|c|}
\hline
{\scriptsize{OF}$\downarrow \slash $ \scriptsize{Methods} $\rightarrow$} & {\scriptsize{DMDE \cite{ranftl2016dense}}}  & {\scriptsize{S. Soup \cite{kumar2017monocular}}} & {\scriptsize{Ours}}\\ \hline
PWC Net \cite{Sun2018PWC-Net}  &  -   &  -   & 0.1848  \\ \hline
Flow Fields \cite{bailer2015flow}  &  0.2970   &  0.1669   & 0.1943  \\ \hline
Full Flow  \cite{chen2016full} &   -   &  0.1933   & 0.2144  \\ \hline
\end{tabular}
\caption{ \small{Comparison of dense depth estimation methods under \emph{two consecutive frame setting} against the state-of-the-art approaches on the {\bf{MPI Sintel dataset}} \cite{butler2012naturalistic}. For consistency, the evaluations are performed using mean relative error metric (MRE).}} \label{tab:MPIResults}
\end{table}

\noindent
{\bf{(a) Two-frame results:}}
While testing our algorithm for the two-frame case, the reference frame depth is initialized using recently proposed superpixel-soup algorithm \cite{kumar2017monocular}. The optical flow between the frames is obtained using methods such as PWC-Net \cite{Sun2018PWC-Net}, Flow Fields \cite{bailer2015flow} and Full Flow \cite{chen2016full}.  Table (\ref{tab:MPIResults}) shows the statistical performance comparison of our method against other geometric approaches. The statistics clearly show that our alternative way performs almost equally well without using any 3D rotation or translation.
Qualitative results within this setting are shown in Fig.~\ref{fig:MPItwoframe}.

\noindent
{\bf{(b) Multi-frame results:}}
In the multi-frame setting, only the depth for the first frame is initialized. The result obtained for the next frame is then used for the upcoming frames to estimate its dense depth map. Since we are dealing with the dynamic scene, the environment changes slowly and therefore, the error starts to accumulate over frames. Fig.~\ref{fig:n1} reflects this propagation of error over frames. Qualitative results over multiple frames are shown in Fig.~\ref{fig:MPImultiframe}.

\begin{figure}
\begin{center}
\includegraphics[width=1.0\linewidth,height=0.15\textheight]{Figures/MultiFrameDenseResultsMPI.pdf}
\caption{\small{Results on MPI Sintel dataset \cite{butler2012naturalistic} under multi-frame experimental setting. (a) Image frame for which the depth is initialized. (b) Depth estimation results using our method over frames.} \label{fig:MPImultiframe}}
\end{center}
\end{figure}

\subsection{KITTI}
The KITTI dataset has emerged as a standard benchmark dataset to evaluate the performance of dense depth estimation algorithms. It contains images of outdoor driving scenes with different lighting conditions and large camera motion. We tested our algorithm on both KITTI raw data and KITTI 2015 benchmark. For KITTI dataset, we used Monodepth method \cite{godard2017unsupervised} to initialize the reference frame depth. Dense optical flow correspondences are obtained using the same aforementioned methods. For consistency, the depth estimation error measurement on KITTI dataset follows the same order of 50 meters as presented in \cite{godard2017unsupervised} work.

\noindent
{\bf{Two-frame results:}}
KITTI 2015 scene flow dataset provides two consecutive frame pair of a dynamic scene to test algorithms. Table (\ref{tab:KITTIResults}) provides the depth estimation statistical result of our algorithm in comparison to other competing methods. Here, our results are a bit better using PWC-Net \cite{Sun2018PWC-Net} optical flow and Monodepth \cite{godard2017unsupervised} depth initialization.
Fig.~\ref{fig:KITTItwoframe} shows the qualitative results using our approach in comparison to the Monodepth \cite{godard2017unsupervised} for the next frame.

\noindent
{\bf{Multi-frame results:}}
To test the performance of our algorithm on multi-frame KITTI dataset, we used KITTI raw dataset specifically from the city, residential and road category. The depth for only the first frame is initialized using Monodepth \cite{godard2017unsupervised} and then we estimate the depth for the upcoming frames. Due to very large displacement in the scene per frame ($>$150) pixels, the rate of change of error accumulation curve for KITTI dataset (Fig.~\ref{fig:n2}) is a bit steeper than MPI Sintel. Fig.~\ref{fig:KITTImultiframe} and Fig.~\ref{fig:n2} show the qualitative results and depth error accumulation over frames on KITTI raw dataset respectively.
\begin{figure}
\begin{center}
\includegraphics[width=1.0\linewidth, height=0.15 \textheight]{Figures/TwoFrameDenseResultsKITTI.pdf}
\caption{\small{Results on KITTI 2015 benchmark dataset under two frame experimental setting. {\bf{$\mathbf{3^{rd}}$ row:}} Monodepth \cite{godard2017unsupervised} results on the same sequence for the next frame for qualitative comparison.} \label{fig:KITTItwoframe}}
\end{center}
\end{figure}

\begin{table}
\centering
\scriptsize
\begin{tabular}{|>{\columncolor[gray]{0.88}}c|c|c|c|c|}
\hline
{\scriptsize{OF}$\downarrow \slash $ \scriptsize{Methods} $\rightarrow$} & {\scriptsize{DMDE \cite{ranftl2016dense}}}  & {\scriptsize{S. Soup \cite{kumar2017monocular}}} & {\scriptsize{Ours}}\\ \hline
PWC Net \cite{Sun2018PWC-Net}  &  -   &  -   & 0.1182  \\ \hline
Flow Fields \cite{bailer2015flow}  &  0.1460   &  0.1268   & 0.1372  \\ \hline
Full Flow  \cite{chen2016full} &   -   &  0.1437   & 0.1665  \\ \hline
\end{tabular}
\caption{ \small{Comparison of dense depth estimation under \emph{two consecutive frame setting} against the state-of-the-art approaches on {\bf{KITTI  dataset}} \cite{butler2012naturalistic}. For consistency, the evaluations are performed using mean relative error metric (MRE). The results are better due to monodepth initialization for the reference frame.}} \label{tab:KITTIResults}
\end{table}

\section{Statistical Analysis}
Besides standard experiments under the aforementioned variable initialization, we conducted other experiments to better understand the behavior of the proposed idea. We conducted experiments on a synthetic example shown in Fig.~\ref{fig:syntheticexample} for easy understanding to the readers. Matlab codes are provided in the supplementary material for reference.

\noindent
{\bf{(a) Effect of the variable $N$}}: The number of superpixels to approximate the dynamic scene can affect the performance of our method. A small number of superpixel can provide poor depth result, whereas a very large number of superpixel can increase the computation time. Fig.~\ref{fig:m1} shows the change in the accuracy of depth estimation with respect to the change in the number of superpixels. The curve suggests that for KITTI and MPI Sintel 1000-1200 superpixel provides a reasonable approximation to the dynamic scenes.

\noindent
{\bf{(b) Effect of the variable $\mathcal{N}_{i}^{k}$}}: The number of K-nearest neighbors to define the local rigidity graph can have a direct effect on the performance of the algorithm. Although $\mathcal{N}_{i}^{k} = 20-25$ works well for the tested benchmarks, it is purely an empirical parameter and can be different for  a distinct dynamic scene. Fig.~\ref{fig:o1} demonstrates the performance of the algorithm with the change in the values of $\mathcal{N}_{i}^{k}$.

\noindent
{\bf{(c) Performance of the algorithm under noisy initialization:}} This experiment is conducted to study the sensitivity of the method to noisy depth initialization. Fig.~\ref{fig:sn1} shows the change in the 3D reconstruction accuracy with the variation in the level of noise from 1\% to 9\%. We introduced the Gaussian noise using randn() MATLAB function and the results are documented for the example shown in Fig.~\ref{fig:syntheticexample} after repeating the experiment for 10 times and taking its average values. We observe that our algorithm can provide arguable results when the noise level gets high.

\begin{figure}
\begin{center}
\includegraphics[width=1.0\linewidth, height=0.15\textheight]{Figures/MultiFrameDenseResultsKITTI.pdf}
\caption{\small{Results on KITTI raw dataset under multi-frame experimental setup. (a) Reference image for which the depth is initialized (b) Dense depth results over frames using our algorithm.} \label{fig:KITTImultiframe}}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
{\includegraphics[width=0.65\linewidth, height=0.14\textheight]{Figures/ConceptDiagram2Objectedit.pdf}}
\caption{\small{Synthetic example to conduct in-depth behavior analysis of the ARAP. Two objects are deforming independently over a rigid background motion. The objects are at a finite separation from the background. For numerical details on this example, kindly go through the supplementary material.} } \label{fig:syntheticexample}
\end{center}
\end{figure}

\begin{figure*}
\centering
\subfigure [\label{fig:n1}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/multiFrameErrorAccumulation.pdf}}
\subfigure [\label{fig:n2}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/multiFrameErrorAccumulationKITTI.pdf}}
\subfigure [\label{fig:m1}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/ErrorVariationWithNs.pdf}}
\subfigure [\label{fig:o1}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/errorwrtKtwoObject1.pdf}}
\caption{\small{(a)-(b) Accumulation of error over frames for MPI and KITTI dataset respectively. (c) Change in the depth estimation accuracy w.r.t number of superpixel. (d) Variation in the depth accuracy as a function of k-nearest neighbor ($\mathcal{N}_{i}^{k}$)}}
\label{fig:statsexperiment1}
\end{figure*}

\begin{figure*}
\centering
\subfigure [\label{fig:sn1}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/NoiseError.png}}
\subfigure [\label{fig:sn2}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/disigma.png}}
\subfigure [\label{fig:sm1}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/conv_curve.png}}
\subfigure [\label{fig:sm2}] {\includegraphics[width=0.23\textwidth, height=0.13\textheight]{Figures/convergence_val_rip.png}}
\caption{\small{(a) Depth results for the next frame with different levels of Gaussian noise in the reference frame coordinate initialization. (b) Variation in the performance with the change in the $d_{i\sigma}$ values for synthetic example. (c) Convergence curve of the ARAP objective function. (d) Quick convergence with similar accuracy on the same example can be achieved by using restricted isometric constraint.}}
\label{fig:statsexperiment2}
\end{figure*}

\noindent
{\bf{(d) Performance of the algorithm under restricted isometry constraint with $\Phi^\textrm{arap}$ objective function:}} While minimizing the ARAP objective function under the $|\tilde{d}_i-d_i|<d_{i\sigma}$ constraint, we restrict the convergence trust region of the optimization. This constraint makes the algorithm works extremely well ---both in timing and accuracy, if an approximate knowledge about the deformation that the scene may undergo is known a priori. Fig.~\ref{fig:sn2} show the 3D reconstruction accuracy as a function of $d_{i\sigma}$ for the example shown in Fig.~\ref{fig:syntheticexample}. Clearly, if we anticipate the scene transformation a priori, we can get high accuracy in less time. See Fig.~\ref{fig:sm2} which show the quick convergence by using this constraint under a suitable range of $d_{i\sigma}$.

\noindent
{\bf{(e) Nature of convergence of the proposed ARAP optimization:}}\\
\noindent
\textbf{1}) \emph{Without restricted isometry constraint}: As rigid as possible minimization $\Phi^\textrm{arap}$ under the constraint $\tilde{d}_i > 0$ is alone a good enough constraint to provide acceptable results. However, it may take a considerable number of iterations to do so. Fig.~\ref{fig:sm1} shows the convergence curve.

\noindent
\textbf{2}) \emph{With restricted isometry constraint}: Employing an approximate bound on the deformation that the scene may undergo in the next time instance can help fast convergence with similar accuracy. Fig.~\ref{fig:sm2} shows that the same accuracy can be achieved in 60-70 iterations.

Note: The per iteration cost without isometry constraint is : 3.6s, whereas with isometry constrain 1.72s when tested on MPI Sintel dataset image \cite{butler2012naturalistic}.

\section{Limitation and Discussion}
\noindent
Even though our method works well for diverse dynamic scenes, there are still a few challenges associated with the formulation. Firstly, very noisy depth initialization for the reference frame can provide unsettling results. Secondly, our method is challenged by the instant arrival or removal of the dynamic subjects in the scene, and in such cases, it may need reinitialization of the depth. Lastly, well-known limitations such as occlusion and temporal consistency, especially around the regions close to the boundary of the images can also affect the accuracy of our algorithm.

\noindent
{\bf{Discussion:}}
In defense, we would like to state that motion based methods to structure from motion is also prone to noisy data \cite{govindu2006robustness, crandall2011discrete}. Algorithms like motion averaging \cite{venu2015motionavg}, M-estimators and random sampling \cite{torr1997development} are quite often used to rectify the solution.

\noindent
(a) \emph{What do we gain or lose by our approach?}\\
Estimating all kinds of conceivable motion in a complex dynamic scene from images is a challenging task, in that respect, our method provides an alternative way to achieve per pixel depth without estimating any 3D motion. However, in achieving this we are allowing the gauge freedom between the frames (temporal relations in 3D over frames).

\noindent
(b) \emph{Depth results has some blocky effects?}
Few blocky artifacts can be observed in the depth results due to discrete piece-wise planar decomposition of the scene. Although we smooth the solution using TRW-S \cite{kolmogorov2006convergent}, the number of particles for each move is taken as 10 to reduce the convergence time, therefore, some artifacts can be observed.

\section{Conclusion}
The problem of estimating per-pixel depth of a dynamic scene, where the complex motions are prevalent is a challenging task to solve. Quite naturally, previous methods rely on standard relative 3D motion estimation techniques to solve this problem, which in fact is a non-trivial task for a non-rigid scene. In contrast, this paper introduces an alternative way to perceive this problem, which essentially trivializes the 3D motion estimation as a compulsory step. Most of the real-world dynamic scenes if observed closely, it can be inferred that it locally transforms rigidly and globally as rigid as possible. Using such acute observation we propose an algorithm to obtain dense depth estimation under the piece-wise planar approximation of a scene without explicitly solving for 3D motion. Results obtained on the benchmark datasets also validate the competence of our idea. We hope that our idea may open up a new direction of research in the development of modern 3D vision system.

\noindent\textbf{Acknowledgement.}{\footnotesize ~This work is funded in part by the ARC Centre of Excellence for Robotic Vision (CE140100016), ARC Discovery project on 3D computer vision for geo-spatial localisation (DP190102261), ARC DECRA project DE140100180 and Natural Science Foundation of China (61420106007, 61871325)}.

{\small
\bibliographystyle{ieee}