text:
\documentclass{article}

\usepackage{url}
\newcommand{\refsec}[1]{Section~\ref{sec:#1}}

\title{Artifact Documentation: MonNom}

\author{Fabian Muehlboeck and Ross Tate}

\begin{document}

\maketitle
\section{Getting Started}

\subsection{Prerequisites}

\subsubsection{Virtual Machine Image}
Download the newest Virtual Machine Image (.ova) from \url{https://drive.google.com/drive/folders/1UHlqkndnw3tVGy1xr1uI2nARuopY1pVx?usp=sharing}.

You'll need to install VirtualBox from \url{https://www.virtualbox.org/} - we were using Version 6.1 .
Once you have installed it, start it, and in the VirtualBox Manager, select \texttt{File -> Import Appliance ...}.
Search for the \texttt{.ovf} file you downloaded earlier.

Once the import process is complete, you can start the virtual machine.
You should be automatically logged in, the password (for sudo) is ``monnom''.
On the desktop, there is a link to the \texttt{monnom} directory, which contains all the files for our implementation and experiments.
The rest of this guide assumes you have opened a terminal in that folder.

\subsubsection{Installing from GitHub}
You'll need a Linux distribution with APT as package manager (we tested this on Xubuntu and WSL).
Clone \url{https://github.com/fabianmuehlboeck/monnom}, then run the scripts \texttt{./prerequisites.sh} and \texttt{./build.sh}.

\subsection{Testing whether the benchmarks run}
In the \texttt{monnom} directory, run \texttt{./run-single.sh} (if you are in a non-graphical interface, for example in WSL, run \texttt{./run-single-png.sh} instead; the difference is that at the end, the folder will contain three image files you can copy to somewhere else to look at, while the standard script opens a browser with somewhat interactive reports).
It should run through a single run of all three benchmarks and generate the figures in the paper - either opening a browser window with three tabs, or leaving three \texttt{.png} files in the monnom folder - one for each of the benchmarks: \texttt{float}, \texttt{sort}, and \texttt{sieve}.

\subsection{Updating from GitHub}
Before running the benchmarks, you may want to check whether a newer version of the artifact is available.
Simply run \texttt{git pull} in the \texttt{monnom} directory (you may have to \texttt{git stash} any changes you may have made).
Bigger updates may include an \texttt{./updateN.sh} script to update the prerequisistes; if a new such script is added after updating, please run it, and afterwards re-run \texttt{./build.sh}.

\subsection{Potential Bugs}

\subsubsection{Rebuilding}
Technically, the update scripts include a call to \texttt{./build.sh}.
However, we have noticed in test runs that the re-builds sometimes do not completely run through.
Please run \texttt{./build.sh} anyway after updating, and also try it if you encounter any errors that may hint at build problems.

\subsubsection{Grift Installation}
We noticed that on WSL, Grift may not complete compiling the garbage collector when installed during the prerequisites step.
If Grift fails to run, please try running
\begin{verbatim}
raco pkg remove grift
raco pkg install grift
\end{verbatim}
to reinstall Grift.

\subsubsection{Not All Figures Visible}
In particular in the browser setting, it may happen that a tab does not load the figure it is supposed to.
In this case, please run \texttt{./make\_charts.sh} (or, \texttt{./make\_charts\_png.sh} for the image version) to re-create the figures from the already generated data.

\section{Step-by-Step}

\subsection{Claims}
The artifact is supposed to justify all experimental claims in the paper; all sources for the various experiments that have been run have been included, as well as scripts that regenerate figures in the style of the paper, which---modulo hardware and environment---should produce similar-looking figures overall.

\subsection{Running Experiments}
In the \texttt{monnom} folder, run \texttt{./run-all.sh} (or, if not in a graphical shell, run \texttt{./run-all-png.sh}).
This will run each benchmark program 10 times, average the running times, and produce figures as in the paper based on those running times; either shown directly in a browser, or as \texttt{.png} files to be viewed elsewhere -- either way, there should be one tab/png-file per benchmark: \texttt{float}, \texttt{sort}, and \texttt{sieve}, where the first two are only run for MonNom, while \texttt{sieve} is also run for Racket, Nom, and Grift.
You can adjust the number of runs by editing the \texttt{RUNS} variable in the script you are using.

\subsection{Exploring the Artifact}
After running the experiments, each configuration of each program is available for inspection in some subfolder of the various experiment folders.
You may be particularly interested in the various configurations generated for MonNom; the meanings of the folder names (make sure to look for hidden folders, as the folders are named in the pattern \texttt{.BM\_[configuration]})---and in particular the way we generate the various configurations for our MonNom benchmarks---are explained in \refsec{benchmark-generator}.
In addition to the MonNom source code, you will also find \texttt{.lli} files in each folder after the benchmark has been run; these contain the LLVM IR generated by the MonNom Runtime that was used to generate the actually executed machine code (see also \refsec{runtime} for more details on those files).

You can re-run any individual benchmark configuration right away by (after setting up the environment as in the beginning of \refsec{toolchain} typing \texttt{nom [Float/Sieve/Sort]} in a benchmark configuration folder.
If you also want to recompile the program from source (say because you changed something), you will need to copy the relevant project file from the parent folder (see \refsec{nomproject} for details on project files).

If you want to try out your own program, the next section explains the relevant parts of the MonNom tool chain that you will need to use.
Note, however, that the current state of the standard library is quite barebones; it essentially contains only those classes and their methods that were necessary to make the benchmarks work.
You can look at the source code of the \texttt{NomC}/\texttt{Runtime} projects to look at precisely what standard library classes and interfaces are available.
Much of the design of MonNom is aspirational and irrelevant for the present artifact.
For example, the language contains keywords for member visibilities, such as \texttt{public}, \texttt{private}, \texttt{protected}, etc.; the compiler's type-checking procedures mostly take these into account; however, there is currently no run-time enforcement mechanism for them.

Finally, if you want to look at how a particular feature of the tool chain is implemented, \refsec{sourcecode} gives an overview of the most important parts of the source code.

\subsection{The MonNom Tool Chain}
\label{sec:toolchain}
To use the MonNom Tool Chain manually, first make sure your environment is configured to use the right paths:
\begin{verbatim}
. /opt/intel/oneapi/setvars.sh
. [PATH-TO-MONNOM]/setpath.sh
\end{verbatim}

Note that the toolchain is still very much in development status, and was developed on Windows.
Thus, the implementation is incomplete in many places, and the Linux version created for the Artifact is missing several scripts to make the use of some tools more straightforward.
This section describes the purpose and usage of the various points. \refsec{sourcecode} gives an overview of the most important places in the sources of these tools.

\subsubsection{NomProject}
\label{sec:nomproject}
The MonNom compiler works with project files (\texttt{.mnp}), which are XML files describing the source files (\texttt{.mn}) that should be compiled and any dependencies a project might have.
The dependencies part is not fully implemented, but \texttt{NomProject} can still be used to manage the XML files more easily:

\begin{verbatim}
dotnet "$MONNOMBASE/monnombuild/NomProject/Release/netcoreapp3.1/NomProject.dll" \
  create MyProjectName *.mn
\end{verbatim}

Creates a new MonNom project named \texttt{MyProjectName} and adds all \texttt{.mn} files in the current folder to it.
The latter parameter can be omitted to create an empty project, files can be added later using

\begin{verbatim}
dotnet "$MONNOMBASE/monnombuild/NomProject/Release/netcoreapp3.1/NomProject.dll" \
  addfile MyProjectName File1.mn File2.mn ...
\end{verbatim}

To be executable, a project needs a main class that contains a main method.
The main class can be set with

\begin{verbatim}
dotnet "$MONNOMBASE/monnombuild/NomProject/Release/netcoreapp3.1/NomProject.dll" \
  setmain MyProjectName MyMainClass
\end{verbatim}

To get around the missing implementation of dependencies for the purposes of benchmarking, you can use the following hack: manually edit the project file to contain a list of library files (which will not be inlcuded in the devolution scheme of the benchmark generator, see below).
For example, in the \texttt{float} benchmark, the \texttt{Enumerable} class providing some standard functionality over arbitrary enumerables is specified as a library as follows:
\begin{verbatim}
<libraryfiles><file name="Enumerable.mn" /></libraryfiles>
\end{verbatim}

\subsubsection{NomC}
The MonNom compiler takes a project file, type-checks the program, and generates MonNom Intermediate Language files (\texttt{.mnil}) and a manifest file (\texttt{.manifest}).
Long-term, these are supposed to be enclosed in a singular zip-file, but for now they are just laid out flat in the project folder.
To call the MonNom compiler, run
\begin{verbatim}
dotnet "$MONNOMBASE/monnombuild/NomC/bin/Release/netcoreapp3.1/nomc.dll" \
  -p path/to/my/project --project MyProjectName
\end{verbatim}
The compiler will either output the files mentioned above, display an error message (say for a type error), or crash (it is research code, after all).

\subsubsection{Runtime}
\label{sec:runtime}
The MonNom Runtime executes the intermediate code generated by the MonNom Compiler.
It uses the LLVM JIT libraries to compile the intermediate code to machine code before actually running the program.
You can call it by running

\begin{verbatim}
nom MyProjectName
\end{verbatim}

In from of the project name, you can add a number of optional parameters to control the behavior of the runtime:
\begin{itemize}
\item \texttt{-d[N]}, controls the level of debug output, where \texttt{N} is optionally a number between 0 and 3 (if \texttt{N} is omitted, but \texttt{-d} is present, the default value is 2; without \texttt{-d}, it is 0).
At level three, almost every intermediate value in the LLVM IR is printed, along with location information pointing to the relevant place in the IR.
The runtime always outputs two files in the directory of the program: \texttt{llvmir.lli} and \texttt{llvmirPO.lli}.
The latter is the pre-optimized llvm code that is generated by the code of the runtime, while the former contains the LLVM IR that is actually executed after running through the optimizer and possibly inserting debug print calls.
If debug prints are inserted, look for lines that say \texttt{call void \@RT\_NOM\_STATS\_DebugLine(...)}.
The second parameter to this call is the line reference printed in the program's output, and the fourth parameter the value that is being printed.
\item \texttt{-p path/to/my/project} works like the path argument for the compiler, effectively looking for the project's manifest in that path.
\item \texttt{-v} turns on verbose mode, outputting a more readable form of the MonNom Intermediate Code as it is read in, the various states of LLVM IR, and the actual addresses of various symbols after the code is compiled and before actual program execution starts.
\item \texttt{-o[N]}, controls the optimization level of the compiler, using the groups of optimizations clang uses for the various levels (0-3), default 2.
\item \texttt{-s[N]}, controls the level of statistics collected about running the code (causes lots of overhead).
\texttt{N} is a value between 0 and 4, but 0 or \texttt{s} alone already means that casting and call statistics are collected and displayed when the program finishes.
At higher values, the runtime collects timings between instructions (extremely slow).
\item \texttt{-f[N]}, controls the level of function timings (\texttt{N} between 1 and 3, default 1). At level 3, each LLVM-level function is timed, analogous to a profiler (high overhead; without \texttt{-f}, the level is 0, and no timings are collected)
\item \texttt{-w[N]}, sets number of warmup runs (default 0, with just \texttt{-w}, 1, N within 32 bit integer range).
Runs the program \texttt{N} times, suppressing its output, before running it a final time with output enabled.
Between each run, the garbage collector is forced to collect, and, more importantly, cast and run-time type allocation caches are reset (see discussion in \refsec{sourcecode}).
\item \texttt{--stopatend}: lets the runtime wait for an input line after finishing running the program (mostly for debugging with Visual Studio)
\item \texttt{--version}: displays version information at startup
\end{itemize}

\subsubsection{BenchmarkGenerator}
\label{sec:benchmark-generator}
For the purposes of this Artifact, the benchmark generator is key to understanding how the various configurations for MonNom's benchmarks are created.
While benchmarks for all other languages are created by mixing completely typed and completely untyped versions of various parts of the program, MonNom's benchmark generator starts from a completely typed program and generates various \emph{devolutions}.
Type annotations are still removed on a roughly per-module basis as in the other benchmarks, but the structural-to-nominal transition requires some more complicated changes to the code.
The benchmark generator therefore runs all stages of the compiler except bytecode generation, and uses the type information generated by the type checker to generate source code for the various configurations we want to check.

A fully typed/nominal program consists of just fully typed classes and interfaces.
Each configuration is described by a string describing their state in alphabetical order.
Thus, fully typed/nominal configuration of the \texttt{float} benchmark is called \texttt{ICCC}, indicating that the interface \texttt{IPoint} is a fully typed nominal interface, and the classes \texttt{Main}, \texttt{Point}, and \texttt{PointMapFun} are fully typed classes.
For interfaces, there exist two other states:
\begin{itemize}
\item \texttt{J} indicates an interface whose type annotations have been replaced with dyn.
In this case, any class implementing the interface must adapt the signatures of its methods to match the interface's annotations.
\item \texttt{K} indicates an interface has been removed from the program's source code altogether.
This means that any class or interface implementing or extending it must remove the corresponding entry from its inheritance declarations, and any occurences of the interface in type annotations must be replaced with \texttt{dyn}.
\end{itemize}

For classes, another state \texttt{D} corresponds to the \texttt{J} state of interfaces - it's just the nominal class but without the type annotations.
Furthermore, depending on the shape of the class (in particular, if it contains no static methods), more states may exist:
if it only contains a \texttt{this}-method (in the calculus in the paper, that is a $\lambda$-method), the additional states are \texttt{L} (typed lambda) and \texttt{M} (untyped lambda); otherwise, the additional states are \texttt{S} (typed record) and \texttt{T} (untyped record).
In all cases, the class is removed from the code, and all calls to its constructor are replaced by expressions creating lambdas or records accordingly.

The benchmark generator generates all possible combinations of these stages for all classes or interfaces in the program.
Thus, for example, \texttt{KDTM} is the most untyped/structural configuration of the \texttt{float} benchmark, as the \texttt{IPoint} interface has been removed, the main class contains static methods and thus can neither become a lambda or a record, the \texttt{Point} class becomes an untyped record, and the \texttt{PointMapFun} class becomes an untyped lambda.

To use the benchmark generator, you can use the \texttt{nombench} command with the following possible parameters:
\begin{itemize}
\item \texttt{--project MyProjectName} --- the project from which to generate the benchmark configurations, as for \texttt{NomC}
\item \texttt{-p path/to/my/project} --- the path in which to find the project file, if it is not in the current directory, as for \texttt{NomC}
\item \texttt{-r N} --- how often each configuration should be run. Note that if this parameter is missing, the benchmark generator only generates the various configurations, but runs nothing.
\item \texttt{-o N} --- the optimization level that should be passed to the corresponding runtime flag (default: 3)
\item \texttt{--byfile} --- group classes and interfaces by file for devolution: all classes and interfaces defined in the same file are not varied independently, but devolve together.
This cuts down on the number of configurations, which otherwise can explode quite quickly.
We use this flag in the \texttt{sort} benchmark.
\item \texttt{--priority} --- try to run the actual benchmark runs with the highest process priority.
Typically needs administrator-level permissions (i.e. \texttt{sudo}).
\item \texttt{-w N} --- use warmups for running the benchmark; forwarded to the corresponding runtime parameter (default: 0)
\end{itemize}

For a normal benchmark run, at least the \texttt{--project} and \texttt{-r} parameters are required, as in
\begin{verbatim}
nombench --project MyProjectName -r 1
\end{verbatim}
For examples, see \texttt{run-monnom.sh} in the main folder.

\subsection{The Artifact Scripts}
The artifact comes with a number of scripts in the main folder:
\begin{itemize}
\item \texttt{build.sh}---updates the builds of all parts of the MonNom toolchain, say after pulling an update via \texttt{git}.
If you need a complete re-build, delete all sub-folders of the \texttt{monnombuild} folder (leave at least the \texttt{nombench} script in it), and run \texttt{make clean} in \texttt{sourcecode/Runtime}, then run \texttt{./build.sh} again.
\item \texttt{cleanup-benchmarks.sh}---deletes all intermediate results from running the benchmarks.
This is particularly useful if you want to execute fewer runs than on a previous benchmarking run, as otherwise for some languages the later runs of the earlier benchmarking run would be included in the figures for the new run.
\item \texttt{collekt.rkt/collect.sh path/to/benchmark} --- collects benchmark results for individual configurations of the MonNom and Grift benchmarks and puts them into a \texttt{results.csv} file in the root folder of that benchmark.
\item \texttt{make\_charts.sh}---if all the benchmark data has been generated (i.e. also after running \texttt{collect.sh}), generates the figures from the paper, and displays them in browser tabs
\item \texttt{make\_charts\_png.sh}---like \texttt{make\_charts.sh}, but renders the figures as \texttt{.png} files.
\item \texttt{prerequisites.sh}---installs the necessary programs and libraries needed to run all the benchmarks on a standard Ubuntu distribution
\item \texttt{run-all.sh}---runs all the benchmarks 10 times and generates figures based on the average results
\item \texttt{run-all-png.sh}---like \texttt{run-all.sh}, but figures are output as \texttt{.png} files.
\item \texttt{run-[lang].sh}---runs all benchmarks available for that particular language
\item \texttt{run-monnom-warmup.sh}---like \texttt{run-monnom.sh}, but lets each benchmark use two warmup runs.
\item \texttt{run-single.sh}, \texttt{run-single-png.sh}---like \texttt{run-all.sh} and \texttt{run-all-png.sh}, respectively, but only uses a single run for each benchmark (used to test whether the benchmarks can run successfully)
\item \texttt{setpath.sh}---adds the relevant directories to run the benchmarks to the \texttt{PATH} variable, and exports the root MonNom directory as \texttt{\$MONNOMBASE}.
\end{itemize}

\subsection{Exploring the Source Code}
\label{sec:sourcecode}
To be written

\end{document}

max_stars_repo_name: fabianmuehlboeck/monnom

max_issues_repo_name: fabianmuehlboeck/monnom

max_forks_repo_name: fabianmuehlboeck/monnom


text:
\documentclass[a4paper, 12pt]{article}

\usepackage[utf8]{inputenc}

\usepackage[top=2.5cm, bottom=2.5cm, left=2.25cm, right=2.25cm]{geometry}

\usepackage{mathptmx}
\usepackage[scaled=0.9]{helvet}
\usepackage{courier}
\usepackage[T1]{fontenc}

\begin{document}

\title{Taskstack Documentation\\
\large (Work in progress)}
\author{Julius Krahn}
\maketitle

\tableofcontents

\newpage

\section{Tech Stack}

\subsection{Backend}

\begin{itemize}
	\item Web Server: NGINX
	\item Application Server: uWSGI
	\item Database: MySQL
    \item Application Framework: (Python:) Flask
    \begin{itemize}
        \item SQLAlchemy
        \item Flask-SocketIO
        \item \dots (for all used packages see /taskstack/requirements.txt)
    \end{itemize}
    \item Hosting: AWS EC2 (server), AWS RDS (db), AWS S3 (static and uploaded files)
    \item Email Sending: AWS SES
    \item Docker (+ Docker-Compose)
\end{itemize}

\subsection{Frontend}

\begin{itemize}
    \item Client and Serverside Rendering
	\item No Framework/ big library
	\item socket.io
	\item tippy.js for Tooltips
	\item fontawesome for Icons
	\item he.js for Escaping
	\item anchorme.js for URL to Link
	\item cropper.js for Image Cropping
	\item sortable.js for Drag and Drop + Sort
\end{itemize}

\subsection{Misc}

\begin{itemize}
    \item Domain Name: Namecheap
\end{itemize}

\newpage

\section{Running Taskstack for development}

\subsection{Requirements}

\begin{itemize}
    \item Python 3.7
    \item Python modules: /taskstack/requirements.txt (except uwsgi, gevent, redis)
    \item Local MySQL database
    \item AWS CLI
    \item Port 5000 open
\end{itemize}

\subsection{Run}

\begin{itemize}
    \item set environment variables: /taskstack/.env
    \item run /taskstack/wsgi.py
    \item access the server: http://localhost:5000
\end{itemize}

\section{Deployment}

\subsection{Server Requirements}

\begin{itemize}
    \item OS: Ubuntu
    \item Docker (+ Docker-Compose)
    \item Git
    \item Port 80 and 443 open for all incoming and outgoing connections
\end{itemize}

\subsection{Initial}

\begin{itemize}
    \item Get the code \newline git clone https://github.com/juliuskrahn/taskstack
    \item Set environment variables: /taskstack/.env
    \item Disable THP \newline echo never /sys/kernel/mm/transparent\_hugepage/enabled \newline
    (needs to be done again if the server is shut down)
    \item Build and Start \newline docker-compose build \newline
    docker-compose up -d
    \item Enable https \newline
    docker exec -it nginx bash \newline
    sudo certbot –nginx
\end{itemize}

\subsection{Updating}

\begin{itemize}
    \item Stop affected service (taskstack |nginx |redis) \newline
    docker-compose stop [service]
    \item Get the code \newline
    git pull
    \item Re-build and start affected service (taskstack |nginx |redis) \newline
    docker-compose build [service] \newline
    docker-compose up -d [service] \newline
    (If you need to rebuild the nginx service, make sure to enable https again!)
\end{itemize}

\newpage

\end{document}

ext: tex

max_stars_repo_name: juliuskrahn/Taskstack

max_issues_repo_name: juliuskrahn/Taskstack

max_forks_repo_name: juliuskrahn/Taskstack


text:
\appendix
\section{PatchAPI for Dyninst Programmers}
\label{sec-dyn}

The PatchAPI is a Dyninst component and as such is accessible through
the main Dyninst interface (BPatch objects). However, the PatchAPI
instrumentation and CFG models differ from the Dyninst models in
several critical ways that should be accounted for by users. This
section summarizes those differences and describes how to access
PatchAPI abstractions from the DyninstAPI interface.

\subsection{Differences Between DyninstAPI and PatchAPI}

The DyninstAPI and PatchAPI differ primarily in their CFG
representations and instrumentation point abstractions. In general,
PatchAPI is more powerful and can better represent complex binaries
(e.g., highly optimized code or malware). In order to maintain
backwards compatibility, the DyninstAPI interface has not been
extended to match the PatchAPI. As a result, there are some caveats.

The PatchAPI uses the same CFG model as the ParseAPI. The primary
representation is an interprocedural graph of basic blocks and
edges. Functions are defined on top of this graph as collections of
blocks. \textbf{A block may be contained by more than one function;}
we call this the \emph{shared block} model. Functions are defined to
have a single entry block, and functions may overlap if they contain
the same blocks. Call and return edges exist in the graph, and
therefore traversing the graph may enter different functions. PatchAPI
users may specify instrumenting a particular block within a particular
function (a \emph{block instance}) by specifying both the block and
the function.

The DyninstAPI uses a historic CFG model. The primary representation
is the function. Functions contain a intraprocedural graph of blocks
and edges. As a result, a basic block belongs to only one function,
but two blocks from different functions may be \emph{clones} of each
other. No interprocedural edges are represented in the graph, and thus
traversing the CFG from a particular function is guaranteed to remain
inside that function.

As a result, multiple DyninstAPI blocks may map to the same PatchAPI
block. If instrumenting a particular block instance is desired, the
user should provide both the DyninstAPI basic block and function.

In addition, DyninstAPI uses a \emph{module} abstraction, where
a \texttt{BPatch\_module} represents a collection of functions from a
particular source file (for the executable) or from an entire library
(for all libraries). PatchAPI, like ParseAPI, instead uses
an \emph{object} representation, where a \texttt{PatchObject} object
represents a collection of functions from a file on disk (executable
or libraries).

The instrumentation point (\emph{instPoint}) models also differ
between DyninstAPI and PatchAPI. We classify an instPoint either as
a \emph{behavior} point (e.g., function entry) or \emph{location}
point (e.g., a particular instruction). PatchAPI fully supports both
of these models, with the added extension that a location point
explicitly specifies whether instrumentation will execute before or
after the corresponding location. Dyninst does not support the
behavior model, instead mapping behavior instPoints to a corresponding
instruction. For example, if a user requests a function entry
instPoint they instead receive an instPoint for the first instruction
in the function. These may not always be the
same (see \href{ftp://ftp.cs.wisc.edu/paradyn/papers/Bernat11AWAT.pdf}{Bernat\_AWAT}). In addition, location instPoints represent an
instruction, and the user must later specify whether they wish to
instrument before or after that instruction.

As a result, there are complications for using both DyninstAPI and
PatchAPI. We cannot emphasize enough, though, that users \emph{can
combine DyninstAPI and PatchAPI} with some care. Doing so offers
several benefits:
\begin{itemize}
\item The ability to extend legacy code that is written for
DyninstAPI.
\item The ability to use the DyninstAPI extensions and plugins for
PatchAPI, including snippet-based or dynC-based code generation and
our instrumentation optimizer.
\end{itemize}
We suggest the following best practices to be followed when coding for
PatchAPI via Dyninst:
\begin{itemize}
\item For legacy code, do not attempt to map between DyninstAPI
instPoints and PatchAPI instPoints. Instead, use DyninstAPI CFG
objects to acquire PatchAPI CFG objects, and use a \texttt{PatchMgr} (acquired
through a \texttt{BPatch\_addressSpace}) to look up
PatchAPI instPoints.
\item For new code, acquire a \texttt{PatchMgr} directly from
a \texttt{BPatch\_addressSpace} and use its methods to look up both
CFG objects and instPoints.
\end{itemize}

\subsection{PatchAPI accessor methods in Dyninst}

To access a PatchAPI class from a Dyninst class, use
the \texttt{PatchAPI::convert} function, as in the following example:

\begin{apient}
  BPatch_basicBlock *bp_block = ...;
  PatchAPI::PatchBlock *block = PatchAPI::convert(bp_block);
\end{apient}

We support the following mappings, where all PatchAPI objects
are within the \texttt{Dyninst::PatchAPI} namespace:

\begin{tabular}{|l|l|l|}
\hline
From & To & Comments \\
\hline
\texttt{BPatch\_function} & \texttt{PatchFunction} & \\
\texttt{BPatch\_basicBlock} & \texttt{PatchBlock} & See above. \\
\texttt{BPatch\_edge} & \texttt{PatchEdge} & See above. \\
\texttt{BPatch\_module} & \texttt{PatchObject} & See above. \\
\texttt{BPatch\_image} & \texttt{PatchMgr} & \\
\texttt{BPatch\_addressSpace} & \texttt{PatchMgr} & \\
\texttt{BPatch\_snippet} & \texttt{Snippet} & \\
\hline
\end{tabular}

We do not support a direct mapping between \texttt{BPatch\_point}s
and \texttt{Point}s, as the failure of Dyninst to properly represent
behavior instPoints leads to confusing results. Instead, use
the PatchAPI point lookup methods.


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CS624: Analysis of Algorithms
% Copyright 2015 Pejman Ghorbanzade <pejman@ghorbanzade.com>
% Creative Commons Attribution-ShareAlike 4.0 International License
% More info: https://github.com/ghorbanzade/beacon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Question 4}

Prove that if $T$ is an optimal binary search tree and if $T'$ is any subtree of $T$, then $T'$ is an optimal binary search tree for its nodes.

\subsection*{Solution}

Proof is given by contradiction.
Assume that $T'$ with nodes $n_i$ to $n_j$, is not an optimal binary search tree.
This means nodes $n_i$ and $n_j$ can construct a binary search tree $T''$ whose expected cost is less than that of $T'$.
As the same nodes form a subtree inside $T$, implementing the new binary search tree $T''$ will lead to less expected total tree cost; the later, directly violates our original assumption that $T$ was an optimal binary search tree.
Therefore the initial assumption is false and $T'$ is an optimal binary search tree.

max_stars_repo_name: ghorbanzade/beacon

max_issues_repo_name: ghorbanzade/beacon

max_forks_repo_name: ghorbanzade/beacon


text:
\section*{Results}

In order to demonstrate that our method works, we run it on D-NeRF's synthetic
dataset which contains 8 different rendered scenes. These scenes have ground truth camera positions and viewing directions, as well as timestamps. They capture physically plausible movement, so there are no discontinuities or jumps between frames..

\subsection*{Quantitative Results}

The Bezier spline design is able to slightly outperform D-NeRF on their synthetic dataset. This is likely because D-NeRF can predict non-realistic movement, such as jumping from frame-to-frame, or suddenly accelerating. In practice, D-NeRF learns fairly smooth movement, but quantitatively looks different from our methods movement, which is likely due to variations in velocity and acceleration. Using Bezier spline, we enforce that movement is fluid, and thus can better reproduce missing frames. This leads to a small improvement in PSNR, because the dataset contains relatively simple movement, but we expect that in longer sequences or data with large gaps this difference would be more visible.

\subsection*{Qualitative Results}

The difference between our work and D-NeRF can be observed in the difference of flow between scenes. It's clear from Fig.~\ref{fig:dnerf_cmp} that our method more accurately captures squashing and stretching of movement, as the top of the ball is not moving but the bottom of the ball is falling. In contrast, D-NeRF contains approximately equal flow for the entire ball.

The difference between the two is also more clearly seen in videos of reconstruction. $C^0$-NeRF visibly has the effect of 'tweening between views, slowing into stops, while D-NeRF has more less smooth starts and stops. While it's difficult to characterize the plausibility of this movement, future work can measure smoothness of velocity and acceleration and use that as a way to differentiate between the approaches.

\begin{table*}[t]
    \centering
    \begin{tabular}{|c| c|c | c|c | c|c | c|c |}
    \hline
    \textbf{PSNR$^\uparrow$ $|$ MS-SSIM$^\uparrow$} & \multicolumn{2}{c|}{Bouncing Balls} & \multicolumn{2}{c|}{Hellwarrior} & \multicolumn{2}{c|}{Hook} & \multicolumn{2}{c|}{Jumping Jacks} \\
    \hline
    D-NeRF & \textbf{24.646} & \textbf{0.975}
           & 33.314 & 0.968
           & 27.954 & 0.978
           & 27.610 & \textbf{0.979} \\
    \hline
    $C^0$-NeRF & 24.251 & 0.971
               & \textbf{33.504} & 0.968
               & \textbf{28.104} & \textbf{0.979}
               & 27.610 & 0.978 \\
    \hline
    & \multicolumn{2}{c|}{Lego} & \multicolumn{2}{c|}{Mutant} & \multicolumn{2}{c|}{Standup} & \multicolumn{2}{c|}{T-Rex} \\
    \hline
    D-NeRF & \textbf{23.232} & \textbf{0.940}
           & 28.693 & 0.981
           & 31.218 & 0.989
           & \textbf{25.525} & \textbf{0.975} \\
    \hline
    $C^0$-NeRF & 23.148 & 0.938
               & \textbf{28.967} & \textbf{0.983}
               & \textbf{31.293} & 0.989
               & 25.421 & 0.972 \\
    \hline
    \end{tabular}
    \caption{
        Bezier splines are able to recover movement with slightly improved accuracy in dynamic scenes as compared to D-NeRF~\cite{pumarola2020dnerf}. Despite, or maybe because of, the forced prior of continuous movement, we are able to learn a smooth interpolation through each frame. We randomly samples all frames from the start of training, as opposed to D-NeRF which requires slowly introducing new frames, but we also remove the constraint that at time 0 D-NeRF must have no movement. Here, we parametrize $C^0$-NeRF with 6 control points.
    }
\end{table*}

\begin{figure*}
    \includegraphics[width=\textwidth]{dnerf_compare}
    \caption{
        \label{fig:dnerf_cmp}
        Results comparing movement in D-NeRF~\cite{pumarola2020dnerf} versus Bezier-splines for a small timestep. There is substantial difference in the predicted flow, since D-NeRF cannot guarantee the initial frame has no movement. There is also a significant difference in rigidity, which is not easily explained. We believe it may be significantly easier to model low movement with splines, thus there is less of a need for rigidity.
    }
\end{figure*}


text:
\chapter{Frames}
\label{sec:frames}

\section{The digital world ($\mathbb{Z}$)}

Pixels or voxels are defined over $\mathbb{Z}^2$ or $\mathbb{Z}^3$ and have integer coordinates.

The voxel is a small rectangular cuboid that has a spatial extent. Our conventions are that the voxel coordinates design the center of the voxel. Let $(v_x, v_y, v_z)$ be the voxel size of image $I$, the spatial area of a voxel $M_{\mathbb{R}} = (x,y,z)$ in the real world $\mathbb{R}$ is the cuboid
$[x-v_x/2, x+v_x/2] \times [y-v_y/2, y+v_y/2] \times [z-v_z/2, z+v_z/2]$ (see figure \ref{fig:frame}).

\begin{figure}[ht]
\begin{center}
 \includegraphics[height=5cm]{figures/fig-frame.png}
\end{center}
\caption{\label{fig:frame}Definition of the  field of view with respect to the  \textit{voxel} one. The origin of the \textit{real} frame is at the center of the upper left pixel/voxel, here the one of coordinate $(0,0,\ldots)$ (C/C++ conventions).}
\end{figure}

Let us consider an image that has a voxel size $v_x$ and a number of voxels of $d_x$ along the $X$ direction. From the C/C++ conventions, the $d_x$ voxels have coordinates in $\mathbb{Z}$ from $0$ to $d_x-1$. The length of the field of view (FOV) is obviously $v_x d_x$ and spans the interval $[v_x * 0 -v_x/2 , v_x*(d_x-1)+v_x/2]
= [-v_x/2, v_x d_x - v_x/2]$ in $\mathbb{R}$.

As a consequence, the center of the field of view in $\mathbb{Z}$ is (here in 3D)
\begin{displaymath}
C_{\mathbb{Z}} =
\left(
\begin{array}{c}
\frac{(d_{x}-1)}{2} \\
\frac{(d_{y}-1)}{2} \\
\frac{(d_{z}-1)}{2}
\end{array}
\right)
\end{displaymath}

Converting voxel coordinates into real ones can trivially be done by multiplying by the voxel sizes (see section \ref{sec:frame:conversion}). The voxel with zero's coordinates defines then the origin of the \textit{real} frame.

\section{Image: $\mathbb{R} \leftrightarrow \mathbb{Z}$}
\label{sec:frame:conversion}

An image $I$ is defined over the discrete frame $\mathbb{Z}$ and a point $M$ may be defined either by its 'voxel' coordinates $(i,j,k)$, or by 'real' coordinates $(x,y,z)$ that can be deduced from $(i,j,k)$ thanks to the imaging acquisition information.

Conversion from the voxel frame, denoted $\mathbb{Z}$, to the real one, denoted $\mathbb{R}$, is achieved through conversion matrices that are associated with every image $I$.

Without any other specification, there are diagonal matrices with the voxel sizes (or their inverses) along the diagonal. Let $(v_x, v_y, v_z)$ be the voxel size of image $I$, thus a point $M_{\mathbb{R}} = (x,y,z)$ in the real frame $\mathbb{R}$ correspond to the voxel point $M_{\mathbb{Z}} = (i,j,k)$ in the voxel frame $\mathbb{Z}$ with
$$M_{\mathbb{R}} = \mathbf{H}_{I,\mathbb{R} \leftarrow \mathbb{Z}} M_{\mathbb{Z}}
\quad \mbox{ with } \quad
\mathbf{H}_{I,\mathbb{R} \leftarrow \mathbb{Z}} = \left( \begin{array}{cccc}
v_x & . & . & . \\
. & v_y & . & . \\
. & . & v_z & . \\
. & . & . & 1
\end{array} \right)
$$
Accordingly,
$$M_{\mathbb{Z}} = \mathbf{H}_{I,\mathbb{Z} \leftarrow \mathbb{R}} M_{\mathbb{R}}
\quad \mbox{ with } \quad
\mathbf{H}_{I,\mathbb{Z} \leftarrow \mathbb{R}} = \left( \begin{array}{cccc}
1/v_x & . & . & . \\
. & 1/v_y & . & . \\
. & . & 1/v_z & . \\
. & . & . & 1
\end{array} \right)
$$
Obviously, we have $\mathbf{H}_{I,\mathbb{Z} \leftarrow \mathbb{R}} = \mathbf{H}^{-1}_{I,\mathbb{R} \leftarrow \mathbb{Z}}$. Note that we use homogeneous coordinates (see section \ref{sec:homogeneous}) to define these matrices.

\begin{attention}
With such a default convention, the frame origins in both the real and the voxel frames superimpose. However, the frame origin in the real frame is not the upper left corner of the field of view (see figure \ref{fig:frame}).
\end{attention}

Note that the matrix $\mathbf{H}$ can be any linear matrix. E.g. they can be reorientation matrices that allows to map the voxel array in standard radiology conventions \footnote{Nifti and Inrimage image formats can embed such rigid transformations (the so-called qform matrices in Nifti format). However, such information can be lost when converting to other formats.}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% transformations
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Transformations}

\section{Definitions}

\subsection{Linear transformations}

Classically, linear transformations (i.e. translations, rigid transformations, affine transformations, etc.) are expressed as combinations of a $3 \times 3$ matrix (representing the vectorial part of the transformation) $\mathbf{A}$ and a 3D vector $\mathbf{t}$ (representing the translation). Thus, the transformed point $M'$ of $M$ by the transformation $T=(\mathbf{A},\mathbf{t})$ is expressed by
\begin{displaymath}
M' = T(M) = \mathbf{A} M + \mathbf{t}
\end{displaymath}

Note that linear transformations are mainly expressed in homogeneous coordinates all along this document (see section \ref{sec:homogeneous:linear}), thus we will use the somewhat abusive notation
\begin{displaymath}
M' = \mathbf{T} M
\end{displaymath}
where $\mathbf{T}$ is a $4 \times 4$ matrix.

\subsection{Vector fields}

Vector fields are used to encode non-linear transformations. For a transformation $T$, the vector $\mathbf{v}(M)$ at point $M$ is the displacement of the point $M$, meaning that
\begin{displaymath}
M' = T(M) = M + \mathbf{v}(M)
\end{displaymath}

\section{Homogeneous coordinates}
\label{sec:homogeneous}

4D homogeneous coordinates are implicitly used. However, there are some  with transformations expressed as vector fields.

\subsection{Linear transformations}
\label{sec:homogeneous:linear}

It is more convenient to express the linear transformations as $4 \times 4$ matrices embedding the translation, so combinations of linear transformations can be expressed by multiplications of matrices. Such a $4 \times 4$ matrix $\mathbf{T}$ is designed by
\begin{displaymath}
\mathbf{T} =
\left(
\begin{array}{ccc|c}
& & & \\
& \mathbf{A} & & \mathbf{t} \\
& & & \\ \hline
0 & 0 & 0 & 1
\end{array}
\right)
\end{displaymath}

A point $M$ has then implicitly 4 coordinates, the first three ones being the spatial coordinates $(x,y,z)$ and the last one being 1. We have thus
\begin{displaymath}
M'
= T(M)
=
\left(
\begin{array}{l}
x' \\ y' \\ z' \\ 1
\end{array}
\right)
= \mathbf{T} M
=
\left(
\begin{array}{ccc|c}
& & & \\
& \mathbf{A} & & \mathbf{t} \\
& & & \\ \hline
0 & 0 & 0 & 1
\end{array}
\right)
\left(
\begin{array}{l}
x \\ y \\ z \\ 1
\end{array}
\right)
\end{displaymath}

\subsection{Vector fields}

The transformation with a vector field is encoded by
\begin{displaymath}
M' = M + \mathbf{v}(M)
\end{displaymath}
When composing (at left) with a linear transformation, we have
\begin{eqnarray}
M'' & = & \mathbf{A} M' + \mathbf{t} \nonumber \\
& = & \mathbf{A} M + \mathbf{A} \mathbf{v}(M) + \mathbf{t}
\label{eq:composition:linear:vector}
\end{eqnarray}

If homogeneous coordinates are used, it comes
\begin{eqnarray*}
M'' & = & \mathbf{T} M'
\left( = \mathbf{A} M' + \mathbf{t} \right) \\
& = & \mathbf{T} M + \mathbf{T} \mathbf{v}(M)
\end{eqnarray*}
From equation \ref{eq:composition:linear:vector}, it comes that
\begin{displaymath}
\mathbf{T} \mathbf{v}(M) = \mathbf{A} \mathbf{v}(M)
\end{displaymath}
This is compatible with homogeneous coordinates if the fourth coordinate of $\mathbf{v}$ is $0$, indeed
\begin{displaymath}
\mathbf{T} \mathbf{v}
=
\left(
\begin{array}{ccc|c}
& & & \\
& \mathbf{A} & & \mathbf{t} \\
& & & \\ \hline
0 & 0 & 0 & 1
\end{array}
\right)
\left(
\begin{array}{c}
\mathbf{v}_x \\ \mathbf{v}_y \\ \mathbf{v}_z \\ 0
\end{array}
\right)
=
\left(
\begin{array}{c}
\mathbf{A} \mathbf{v} \\ \hline
0
\end{array}
\right)
\end{displaymath}

\section{'voxel' versus 'real' definitions}

%definitions for discrete images; $\mathbb{R} \leftrightarrow \mathbb{Z}$ conversion}

Recall that an image $I$ is defined over the discrete frame $\mathbb{Z}$. Thus a point $M$ of $I$ can be expressed either in the discrete frame in voxel coordinates (and will be denoted $M_{\mathbb{Z}}$) or in real coordinates (and will be denoted $M_{\mathbb{R}}$). Conversion matrices (see section \ref{sec:frame:conversion}) allow to go from the voxel frame to the real one, and conversely.

A transformation $T_{flo \leftarrow ref}$ from an image $I_{ref}$ towards an image $I_{flo}$ can be then either defined in the voxel frame or in the real one. These transformations are denoted respectively $T_{flo \leftarrow ref,\mathbb{Z}}$ and $T_{flo \leftarrow ref,\mathbb{R}}$:
\begin{displaymath}
\begin{array}{ll}
T_{flo \leftarrow ref,\mathbb{Z}}: &
I_{ref} \rightarrow I_{flo}\\
& M_{ref,\mathbb{Z}} \mapsto M_{flo,\mathbb{Z}}
\end{array}
\end{displaymath}
and
\begin{displaymath}
\begin{array}{ll}
T_{flo \leftarrow ref,\mathbb{R}}: &
I_{ref} \rightarrow I_{flo}\\
& M_{ref,\mathbb{R}} \mapsto M_{flo,\mathbb{R}}
\end{array}
\end{displaymath}

We have then
\begin{eqnarray*}
M_{flo,\mathbb{Z}} & = &
T_{flo \leftarrow ref,\mathbb{Z}}(M_{ref,\mathbb{Z}}) \\
M_{flo,\mathbb{R}} & = &
T_{flo \leftarrow ref,\mathbb{R}}(M_{ref,\mathbb{R}})
\end{eqnarray*}

Transformations in 'voxel' coordinates are required for image resampling, while transformations in 'real' coordinates may be necessary when dealing when some transformation classes (e.g. rigid) or to compute some measurements (e.g. mean displacements) in world units. Thus, conversion of these transformations from the voxel world to the real one, using the image conversion matrices (see section \ref{sec:frame:conversion}), has to be made explicit.

\subsection{Linear transformations}

Linear transformations can be expressed by $4x4$ matrices in homogeneous coordinates (see section \ref{sec:homogeneous:linear}), thus we have
\begin{eqnarray*}
M_{flo,\mathbb{Z}} & = &
T_{flo \leftarrow ref,\mathbb{Z}} M_{ref,\mathbb{Z}}  \\
M_{flo,\mathbb{R}} & = &
T_{flo \leftarrow ref,\mathbb{R}} M_{ref,\mathbb{R}}
\end{eqnarray*}

To convert the transformations from the voxel world to the real one (and conversely), we apply the composition rules that are here simply matrices multiplication:
$$
\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}}
=
\mathbf{H}_{flo,\mathbb{Z} \leftarrow \mathbb{R}} \circ
\mathbf{T}_{flo \leftarrow ref, \mathbb{R}} \circ
\mathbf{H}_{ref,\mathbb{R} \leftarrow \mathbb{Z}}
$$
and
$$
\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}
=
\mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}} \circ
\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}} \circ
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
$$

\subsection{Vector fields}

The difficulty comes from the fact that the non-linear transformation is encoded by a displacement/vector field that is defined over a discrete lattice (i.e. an image). We have then
\begin{eqnarray*}
M_{flo,\mathbb{Z}} & = &
T_{flo \leftarrow ref,\mathbb{Z}}(M_{ref,\mathbb{Z}}) \\
& = &
M_{ref,\mathbb{Z}} +
\mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(M_{ref, \mathbb{Z}}) \\
M_{flo,\mathbb{R}} & = &
T_{flo \leftarrow ref,\mathbb{R}}(M_{ref,\mathbb{R}}) \\
& = &
M_{ref,\mathbb{R}} +
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref, \mathbb{Z}}) \\
& = &
M_{ref,\mathbb{R}} +
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}  M_{ref, \mathbb{R}})
\end{eqnarray*}
where $\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}$ denotes the conversion matrix from the real world $\mathbb{R}$ to the discrete world $\mathbb{Z}$ for image $I_{ref}$.

The vector field $\mathbf{v}$ indicates the displacement at every point. For a transformation from image $I_{ref}$ to image $I_{flo}$, this vector is defined on the same frame than $I_{ref}$. Thus the vector in \textit{real} coordinates $\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}$ at $M_{\mathbb{R}}$ gives the displacement of the point $M_{\mathbb{R}}$.

However, since $\mathbf{v}_{flo \leftarrow ref}$ is defined over a discrete lattice, the vector image stores the vectors $\mathbf{v}_{\mathbb{R}}(M_{\mathbb{Z}})$, thus $\mathbf{v}_{\mathbb{R}}$ at $M_{\mathbb{R}}$ is $\mathbf{v}_{\mathbb{R}}( \mathbf{H}_{\mathbb{Z} \leftarrow \mathbb{R}} M_{\mathbb{R}} )$.

\subsubsection{Vector fields: $\mathbb{R} \rightarrow \mathbb{Z}$}

The transformation $\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}$ from image $I_{ref}$ to image $I_{flo}$ is defined by the vector field $\mathbf{v}_{flo \leftarrow ref,\mathbb{R}}$
\begin{eqnarray*}
M_{flo,\mathbb{R}} & = &
\mathbf{T}(M_{ref,\mathbb{R}}) = M_{ref,\mathbb{R}} + \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( \mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}} M_{ref,\mathbb{R}} )\\
& = &
\mathbf{T}(M_{ref,\mathbb{R}}) = M_{ref,\mathbb{R}} + \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}(M_{ref,\mathbb{Z}} )
\end{eqnarray*}

When expressing this formula in the discrete lattice, it comes
\begin{displaymath}
\mathbf{H}_{flo, \mathbb{R} \leftarrow \mathbb{Z}} M_{flo,\mathbb{Z}}
=
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( M_{ref,\mathbb{Z}} )
\end{displaymath}
\begin{displaymath}
M_{flo,\mathbb{Z}}
=
\mathbf{H}^{-1}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
\circ \mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}}
M_{ref,\mathbb{Z}}
+ \mathbf{H}^{-1}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
\circ \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( M_{ref,\mathbb{Z}} )
\end{displaymath}

The displacement in \textit{voxel} coordinates $\mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}$ (associated to $\mathbf{T}_{flo \leftarrow ref,\mathbb{Z}}$) is then defined by
\begin{eqnarray*}
\lefteqn{\mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} )
 =  M_{flo,\mathbb{Z}} - M_{ref,\mathbb{Z}}} \\
& = &
\left( \mathbf{H}^{-1}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
 \circ \mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} - \mathbf{Id} \right)
 M_{ref,\mathbb{Z}}
 + \mathbf{H}^{-1}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
 \circ \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( M_{ref,\mathbb{Z}} ) \\
 & = &
\left( \mathbf{H}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
 \circ \mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} - \mathbf{Id} \right)
 M_{ref,\mathbb{Z}}
 + \mathbf{H}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
 \circ \mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( M_{ref,\mathbb{Z}} ) \\
\end{eqnarray*}
(where $\mathbf{Id}$ denotes the identity matrix) and may be different from a simple scaling of the vector field defined in \textit{real} coordinates.

\subsubsection{Vector fields: $\mathbb{Z} \rightarrow \mathbb{R}$}

We have
\begin{displaymath}
M_{flo,\mathbb{Z}} = M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} )
\end{displaymath}

When expressing this formula in the real world, it comes
\begin{displaymath}
\mathbf{H}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
M_{flo,\mathbb{R}}
=
\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}
M_{ref,\mathbb{R}}
+ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} ) \\
\end{displaymath}
\begin{displaymath}
M_{flo,\mathbb{R}}
=
\mathbf{H}^{-1}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
\circ
\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}
M_{ref,\mathbb{R}}
+
\mathbf{H}^{-1}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
\circ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} )
\end{displaymath}

The displacement in \textit{real} coordinates $\mathbf{v}_{flo \leftarrow ref,\mathbb{R}}$ is then defined by
\begin{eqnarray*}
\lefteqn{
\mathbf{v}_{flo \leftarrow ref,\mathbb{R}}( M_{ref,\mathbb{Z}} )
= M_{flo,\mathbb{R}} - M_{ref,\mathbb{R}}} \\
& = &
\left(
\mathbf{H}^{-1}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
\circ
\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}
- \mathbf{Id} \right) M_{ref,\mathbb{R}}
+
\mathbf{H}^{-1}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
\circ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} ) \\
& = &
\left(
\mathbf{H}^{-1}_{flo, \mathbb{Z} \leftarrow \mathbb{R}}
\circ
\mathbf{H}_{ref, \mathbb{Z} \leftarrow \mathbb{R}}
- \mathbf{Id} \right)
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}}
M_{ref,\mathbb{Z}}
+
\mathbf{H}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
\circ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} ) \\
& = &
\left(
\mathbf{H}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
-
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}}
\right)
M_{ref,\mathbb{Z}}
+
\mathbf{H}_{flo, \mathbb{R} \leftarrow \mathbb{Z}}
\circ \mathbf{v}_{flo \leftarrow ref,\mathbb{Z}}( M_{ref,\mathbb{Z}} ) \\
\end{eqnarray*}

\section{Transformations: linear $\rightarrow$ vector field}

$\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}$ is a linear transformation in real space. We have then
\begin{displaymath}
M_{flo, \mathbb{R}} =
\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}
M_{ref, \mathbb{R}}
\end{displaymath}
For vector fields, the transformation is expressed by
\begin{displaymath}
M_{flo, \mathbb{R}} =
M_{ref, \mathbb{R}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref, \mathbb{Z}})
\end{displaymath}
We have then
\begin{eqnarray*}
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref, \mathbb{Z}}) & = &
M_{flo, \mathbb{R}} - M_{ref, \mathbb{R}} \\
& = &
\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}
M_{ref, \mathbb{R}} - M_{ref, \mathbb{R}} \\
& = &
\left( \mathbf{T}_{flo \leftarrow ref, \mathbb{R}} - \mathbf{Id} \right) \circ
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} M_{ref, \mathbb{Z}} \\
& = &
\left( \mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}} \circ
\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}} \circ
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}} - \mathbf{Id} \right) \circ
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} M_{ref, \mathbb{Z}} \\
\end{eqnarray*}

Remarks:
\begin{itemize}

\item Estimating the vector field in real/world units $\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}$ from a linear transformation in real/world units $\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}}$ is done with
\begin{displaymath}
\left( \mathbf{T}_{flo \leftarrow ref, \mathbb{R}} - \mathbf{Id} \right) \circ
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} M_{ref, \mathbb{Z}}
\end{displaymath}
Note that the voxel-to-world transformation for the reference image/frame $\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}}$ is also embedded in the non-linear transformation $\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}$.

\item Estimating the vector field in real/world units $\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}$ from a linear transformation in voxel units $\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}}$
\begin{eqnarray*}
\lefteqn{\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref, \mathbb{Z}}) = } \\
& &
\left( \mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}} \circ
\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}} \circ
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}} - \mathbf{Id} \right) \circ
\mathbf{H}_{ref, \mathbb{R} \leftarrow \mathbb{Z}} M_{ref, \mathbb{Z}}
\end{eqnarray*}
requires to have the voxel-to-world transformation for the floating image/frame $\mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}}$ at hand.

\item When $\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}$ is a pure translation $\mathbf{t}_{\mathbb{R}}$, meaning that
$M_{flo, \mathbb{R}} =
\mathbf{Id} M_{ref, \mathbb{R}} + \mathbf{t}_{\mathbb{R}}$, we have then
\begin{displaymath}
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref, \mathbb{Z}}) = \mathbf{t}_{\mathbb{R}}
\end{displaymath}

\end{itemize}

\section{Transformation composition}

We simply use the composition rules to  transformation composition.
\begin{displaymath}
\mathbf{T}_{K \leftarrow I, \mathbb{R}}
=
\mathbf{T}_{K \leftarrow J, \mathbb{R}}
\circ
\mathbf{T}_{J \leftarrow I, \mathbb{R}}
\end{displaymath}
and
\begin{displaymath}
\mathbf{T}_{K \leftarrow I, \mathbb{Z}}
=
\mathbf{T}_{K \leftarrow J, \mathbb{Z}}
\circ
\mathbf{T}_{J \leftarrow I, \mathbb{Z}}
\end{displaymath}

\subsection{Linear $\circ$ linear}

The composition is quite trivial, since it only uses matrices multiplication.

\subsection{Linear $\circ$ vector field in $\mathbb{R}$ }

\begin{eqnarray*}
M_{J, \mathbb{R}} & = &
M_{I, \mathbb{R}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{R}}
(\mathbf{H}_{I, \mathbb{Z} \leftarrow \mathbb{R}}  M_{I, \mathbb{R}}) \\
& = &
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}} M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}) \\
M_{K, \mathbb{R}} & = &
 \mathbf{T}_{K \leftarrow J, \mathbb{R}} M_{J, \mathbb{R}} \\
& = &
\mathbf{T}_{K \leftarrow J, \mathbb{R}}
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}}
M_{I, \mathbb{Z}}
+ \mathbf{T}_{K \leftarrow J, \mathbb{R}}
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{R}} - M_{I, \mathbb{R}} \\
& = &
\left( \mathbf{T}_{K \leftarrow J, \mathbb{R}} - \mathbf{Id} \right)
\circ
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}}
M_{I, \mathbb{Z}}
+ \mathbf{T}_{K \leftarrow J, \mathbb{R}}
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
\end{eqnarray*}

\subsection{Linear $\circ$ vector field in $\mathbb{Z}$ }

\begin{eqnarray*}
M_{J, \mathbb{Z}} & = &
M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}}) \\
M_{K, \mathbb{Z}} & = &
 \mathbf{T}_{K \leftarrow J, \mathbb{Z}} M_{J, \mathbb{Z}} \\
& = &
\mathbf{T}_{K \leftarrow J, \mathbb{Z}}
M_{I, \mathbb{Z}}
+ \mathbf{T}_{K \leftarrow J, \mathbb{Z}}
\mathbf{v}_{J \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{Z}} - M_{I, \mathbb{Z}} \\
& = &
\left( \mathbf{T}_{K \leftarrow J, \mathbb{Z}} - \mathbf{Id} \right)
M_{I, \mathbb{Z}}
+ \mathbf{T}_{K \leftarrow J, \mathbb{Z}}
\mathbf{v}_{J \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
\end{eqnarray*}

\subsection{Vector field $\circ$ linear in $\mathbb{R}$ }

\begin{eqnarray*}
M_{J, \mathbb{R}} & = &
\mathbf{T}_{J \leftarrow I, \mathbb{R}} M_{I, \mathbb{R}}  \\
M_{K, \mathbb{R}} & = &
M_{J, \mathbb{R}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{R}}(\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}  M_{J, \mathbb{R}}) \\
& = &
\mathbf{T}_{J \leftarrow I, \mathbb{R}} M_{I, \mathbb{R}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{R}}(\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}  \mathbf{T}_{J \leftarrow I, \mathbb{R}} M_{I, \mathbb{R}} )
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{R}} - M_{I, \mathbb{R}} \\
& = &
\left( \mathbf{T}_{J \leftarrow I, \mathbb{R}} - \mathbf{Id} \right)
\circ
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}}
M_{I, \mathbb{Z}}  \\
& & {}
+
\mathbf{v}_{K \leftarrow J, \mathbb{R}}
(\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}
\mathbf{T}_{J \leftarrow I, \mathbb{R}}
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}}
M_{I, \mathbb{Z}} )
\end{eqnarray*}

\subsection{Vector field $\circ$ linear in $\mathbb{Z}$ }

\begin{eqnarray*}
M_{J, \mathbb{Z}} &  =  &
\mathbf{T}_{J \leftarrow I, \mathbb{Z}} M_{I, \mathbb{Z}} \\
M_{K, \mathbb{Z}} & = &
M_{J, \mathbb{Z}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{Z}}(M_{J, \mathbb{Z}}) \\
& = &
\mathbf{T}_{J \leftarrow I, \mathbb{Z}} M_{I, \mathbb{Z}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{Z}}(\mathbf{T}_{J \leftarrow I, \mathbb{Z}} M_{I, \mathbb{Z}} )
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{Z}} - M_{I, \mathbb{Z}} \\
& = &
\left( \mathbf{T}_{J \leftarrow I, \mathbb{Z}} - \mathbf{Id} \right)
M_{I, \mathbb{Z}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{Z}}
( \mathbf{T}_{J \leftarrow I, \mathbb{Z}} M_{I, \mathbb{Z}} )
\end{eqnarray*}

\subsection{Vector field $\circ$ vector field in $\mathbb{R}$ }

\begin{eqnarray*}
M_{J, \mathbb{R}} & =  &
M_{I, \mathbb{R}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{R}}(\mathbf{H}_{I, \mathbb{Z} \leftarrow \mathbb{R}}  M_{I, \mathbb{R}}) \\
& = &
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}} M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}) \\
M_{K, \mathbb{R}} & = &
M_{J, \mathbb{R}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{R}}(\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}  M_{J, \mathbb{R}}) \\
& = &
M_{I, \mathbb{R}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}) \\
& & {}
+ \mathbf{v}_{K\leftarrow J, \mathbb{R}}\left(
\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}
\left(
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}} M_{I, \mathbb{Z}}
+
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}
\right)
\right)
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{R}} - M_{I, \mathbb{R}} \\
& = &
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}) \\
& & {}
+ \mathbf{v}_{K \leftarrow J, \mathbb{R}}
\left(
\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}
\left(
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}} M_{I, \mathbb{Z}}
+
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}
\right)
\right) \\
& = &
\mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}}) \\
& & {}
+ \mathbf{v}_{K \leftarrow J, \mathbb{R}}
\left(
\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}
\circ
\mathbf{H}_{I, \mathbb{R} \leftarrow \mathbb{Z}} M_{I, \mathbb{Z}}
+
\mathbf{H}_{J, \mathbb{Z} \leftarrow \mathbb{R}}
\circ \mathbf{v}_{J \leftarrow I, \mathbb{R}}(M_{I, \mathbb{Z}})
\right)
\end{eqnarray*}

\subsection{Vector field $\circ$ vector field in $\mathbb{Z}$ }

\begin{eqnarray*}
M_{J, \mathbb{Z}} & =  &
M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{Z}}( M_{I, \mathbb{Z}}) \\
M_{K, \mathbb{Z}} & = &
M_{J, \mathbb{Z}}
+ \mathbf{v}_{K \leftarrow J, \mathbb{Z}}(M_{J, \mathbb{Z}}) \\
& = &
M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
+ \mathbf{v}_{K\leftarrow J, \mathbb{Z}}\left(
M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{Z}}( M_{I, \mathbb{Z}})
\right)
\end{eqnarray*}

\begin{eqnarray*}
\mathbf{v}_{K \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
& = &
M_{K, \mathbb{Z}} - M_{I, \mathbb{Z}} \\
& = &
\mathbf{v}_{J \leftarrow I, \mathbb{Z}}(M_{I, \mathbb{Z}})
+ \mathbf{v}_{K\leftarrow J, \mathbb{Z}}\left(
M_{I, \mathbb{Z}}
+ \mathbf{v}_{J \leftarrow I, \mathbb{Z}}( M_{I, \mathbb{Z}})
\right)
\end{eqnarray*}

\section{Field of view center alignment}
\label{sec:field:view:center:alignment}

For computational reasons, it may be useful to change the resolution of an image, typically dividing the dimensions by a factor 2 (and then multiplying the voxel sizes by 2). It allows to deal with smaller images while letting the FOV sizes unchanged.

However, because of our conventions where the frame origin is not at the upper left corner of the FOV but at the center of the upper left voxel, the transformation that goes from one frame to the other is a translation (the translation between the two origins).

Let us consider the general case where we want to build the translation that superimposes the FOV centers of two images $I_{ref}$ and $I_{flo}$. Without loss of generality, we only consider the $X$ direction. $I_{ref}$ and $I_{flo}$ have respectively a number of voxels of $d_{ref,x}$ and $d_{flo,x}$. The FOV intervals (in voxels) are respectively
$[-1/2, d_{ref,x} - 1/2]$ and
$[-1/2, d_{flo,x} - 1/2]$ in $\mathbb{Z}$. The FOV centers along the $X$ direction are then respectively $\frac{(d_{ref,x}-1)}{2}$ and $\frac{(d_{fflo,x}-1)}{2}$.

In 3D, the FOV centers of $I_{ref}$ and $I_{flo}$ are respectively
\begin{displaymath}
C_{ref,\mathbb{Z}} =
\left(
\begin{array}{c}
\frac{(d_{r,x}-1)}{2} \\
\frac{(d_{r,y}-1)}{2} \\
\frac{(d_{r,z}-1)}{2}
\end{array}
\right)
\quad \textrm{ and } \quad
C_{flo,\mathbb{Z}} =
\left(
\begin{array}{c}
\frac{(d_{f,x}-1)}{2} \\
\frac{(d_{f,y}-1)}{2} \\
\frac{(d_{f,z}-1)}{2}
\end{array}
\right)
\end{displaymath}

The translation of $\mathbf{T}_{flo \leftarrow ref}$ that aligns the FOV centers in the real space is then
\begin{displaymath}
C_{flo,\mathbb{R}} - C_{ref,\mathbb{R}}
= \mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}} C_{flo,\mathbb{Z}}
- \mathbf{H}_{ref,\mathbb{R} \leftarrow \mathbb{Z}} C_{ref,\mathbb{Z}}
\end{displaymath}

Moreover, such an alignment of the centers of field of view is also the initial transformation (when no initial transformation is given) for the registration through\blockmatching{}.

\section{Transformation inversion}

Knowing the transformation $\mathbf{T}_{flo \leftarrow ref}$, we aim at estimating $\mathbf{T}_{ref \leftarrow flo}$,

\subsection{Linear transformations}

Since linear transformations are represented by $4 \times 4$ matrices, inverting them is trivial and comes to invert the matrices. We have
\begin{displaymath}
\mathbf{T}_{ref \leftarrow flo, \mathbb{Z}} =
\mathbf{T}_{flo \leftarrow ref, \mathbb{Z}}^{-1}
\quad \mbox{ and } \quad
\mathbf{T}_{ref \leftarrow flo, \mathbb{R}} =
\mathbf{T}_{flo \leftarrow ref, \mathbb{R}}^{-1}
\end{displaymath}

\subsection{Vector field in $\mathbb{Z}$}

\subsubsection{Principle}

From the direct transformation, we have
\begin{displaymath}
M_{flo,\mathbb{Z}} =
M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(M_{ref,\mathbb{Z}} )
\end{displaymath}
and the inverse transformation allows to express $M_{ref,\mathbb{Z}}$ from $M_{flo,\mathbb{Z}}$
\begin{eqnarray*}
M_{ref,\mathbb{Z}} & = &
M_{flo,\mathbb{Z}}
+ \mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}} ) \\
& = &
M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(M_{ref,\mathbb{Z}} )
+ \mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}} )
\end{eqnarray*}

Hence we have
\begin{eqnarray*}
0 & = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}} )
+
\mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(M_{ref,\mathbb{Z}} )
\\
& = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}} )
+
\mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(
M_{flo,\mathbb{Z}}
+ \mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}})
)
\end{eqnarray*}

For the sake of simplicity, let us denote
\begin{eqnarray*}
M & = & M_{flo,\mathbb{Z}} \\
\mathbf{v} & = & \mathbf{v}_{flo \leftarrow ref, \mathbb{Z}} \\
\mathbf{v}^{-1} & = & \mathbf{v}_{ref \leftarrow flo, \mathbb{Z}} \\
M' & = & M_{ref,\mathbb{Z}} =
M + \mathbf{v}^{-1}(M) =
M_{flo,\mathbb{Z}} + \mathbf{v}_{ref \leftarrow flo, \mathbb{Z}}(M_{flo,\mathbb{Z}})
\end{eqnarray*}
Computing the inverse transformation, i.e. the vector field $\mathbf{v}_{ref \leftarrow flo, \mathbb{Z}} = \mathbf{v}^{-1}$, aims at minimizing the above expression.
Computing the inverse vector field can be achieved by minimizing
\begin{equation}
\mathbf{v}^{-1}(M) + \mathbf{v}( M' )
= \mathbf{v}^{-1}(M) + \mathbf{v}( M + \mathbf{v}^{-1}(M) )
\label{eq:inverse:vector:z}
\end{equation}

The Newton method aims at estimating iteratively a small variation $\mathbf{\delta}$ of $\mathbf{v}^{-1}(M)$ that make null equation \ref{eq:inverse:vector:z}.

\begin{eqnarray*}
E & = &
\mathbf{v}^{-1}(M) + \mathbf{\delta}
+ \mathbf{v}( M' + \mathbf{\delta} )
\\
& & \mbox{recalling that }
\mathbf{v}(M' + \mathbf{\delta}) \approx
\mathbf{v}( M' ) + (\mathbf{v}.\nabla^t)(M') \mathbf{\delta}
\\
& = &
\mathbf{v}^{-1}(M) + \mathbf{\delta} +
\mathbf{v}( M' )
+ (\mathbf{v}.\nabla^t)( M' ) \mathbf{\delta}
\end{eqnarray*}
Please note that the derivative of
$\mathbf{v} = \mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}$ are computed with respect to $M = M_{ref,\mathbb{Z}}$, i.e. in the voxel frame.
\begin{eqnarray*}
\lefteqn{ E = 0 } \\
& \Leftrightarrow &
\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)( M' )
\right) \mathbf{\delta}
= - \left( \mathbf{v}^{-1}(M) + \mathbf{v}( M' )
\right) \\
& \Leftrightarrow &
\mathbf{\delta}  =
- \left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)( M' )
\right)^{-1}
\left( \mathbf{v}^{-1}(M) + \mathbf{v}( M' )
\right)
\end{eqnarray*}

%   on ajoute une variation delta (d) a I(M) on a
%%   f = I(M) + d + V(M + I(M) + d)
%   V(M'+d) = V(M') + (V.N^t)(M') d avec N l'operateur nabla
%   donc f = I(M) + d + V(M + I(M)) +  (V.N^t)(M + I(M)) d
%   qui s'annule pour
%   d = - ( Id + (V.N^t)(M+I(M)) )^(-1) ( I(M)+v(M+I(M)) )

\subsubsection{Implementation}

$\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)
\right)^{-1}$ are precomputed ($I_{ref}$ frame).

For every point $M = M_{flo,\mathbb{Z}}$, we iterate:
\begin{enumerate}
\itemsep -0.5ex
\item computation of
$M' = M_{ref,\mathbb{Z}} = M + \mathbf{v}^{-1}(M)$
\item computation of
$\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)
\right)^{-1} (M')$ and $\mathbf{v}( M' )$
\item test on
$\| \mathbf{v}^{-1}(M) + \mathbf{v}( M' ) \|$ (ending condition)
\item computation of
$\mathbf{\delta} =
\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)
\right)^{-1} (M')
\left( \mathbf{v}^{-1}(M) + \mathbf{v}( M' ) \right)$
\item update of $\mathbf{v}^{-1}(M)$:
$\mathbf{v}^{-1}(M) \leftarrow \mathbf{v}^{-1}(M) - \alpha \delta$
\end{enumerate}

\subsubsection{Initialization}

From $M' = M_{ref,\mathbb{Z}}$, we compute
\begin{displaymath}
M_{flo,\mathbb{Z}} =
M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{Z}}(M_{ref,\mathbb{Z}} )
\end{displaymath}
Please note that $M_{flo,\mathbb{Z}}$ has real coordinates, though it is a point defined in the discrete frame. $-\mathbf{v}( M' )$ is then distributed to the discrete points around  $M=M_{flo,\mathbb{Z}}$.

\subsection{Vector field in $\mathbb{R}$}

\subsubsection{Principle}

We have
\begin{displaymath}
M_{flo,\mathbb{R}} =
M_{ref,\mathbb{R}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref,\mathbb{Z}} )
\end{displaymath}
and
\begin{eqnarray*}
M_{ref,\mathbb{R}} & = &
M_{flo,\mathbb{R}}
+ \mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} ) \\
& = &
M_{ref,\mathbb{R}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref,\mathbb{Z}} )
+ \mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
\end{eqnarray*}

Hence we have
\begin{eqnarray*}
0 & = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
+
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref,\mathbb{Z}} ) \\
& = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
+
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
M_{ref,\mathbb{R}}
) \\
& = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
 \\
& & \mbox{} +
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
(
M_{flo,\mathbb{R}} +
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
)
) \\
& = &
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
\\
& & \mbox{} +
\mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
\mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}}
M_{flo,\mathbb{Z}}
+
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
)
\end{eqnarray*}

For the sake of simplicity, let us denote
\begin{eqnarray*}
M & = & M_{flo,\mathbb{Z}} \\
\mathbf{v} & = & \mathbf{v}_{flo \leftarrow ref, \mathbb{R}} \\
\mathbf{v}^{-1} & = & \mathbf{v}_{ref \leftarrow flo, \mathbb{R}} \\
\mathbf{H}_r & = & \mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}} \\
\mathbf{H}_f & = & \mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}}  \\
M' & = & M_{ref,\mathbb{Z}} =
\mathbf{H}_r \mathbf{H}_f M + \mathbf{H}_r \mathbf{v}^{-1}(M) \\
& = & \mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
\mathbf{H}_{flo,\mathbb{R} \leftarrow \mathbb{Z}}
M_{flo,\mathbb{Z}}
+
\mathbf{H}_{ref,\mathbb{Z} \leftarrow \mathbb{R}}
\mathbf{v}_{ref \leftarrow flo, \mathbb{R}}(M_{flo,\mathbb{Z}} )
\end{eqnarray*}
Computing the inverse transformation, i.e. the vector field $\mathbf{v}_{ref \leftarrow flo, \mathbb{R}} = \mathbf{v}^{-1}$, aims at minimizing the above expression.
Computing the inverse vector field can be achieved by minimizing
\begin{equation}
\mathbf{v}^{-1}(M) + \mathbf{v}( M' )
= \mathbf{v}^{-1}(M) + \mathbf{v}( \mathbf{H}_r \mathbf{H}_f M + \mathbf{H}_r \mathbf{v}^{-1}(M)  )
\label{eq:inverse:vector:r}
\end{equation}

\begin{eqnarray*}
E & = &
\mathbf{v}^{-1}(M) + \mathbf{\delta}
+ \mathbf{v}( \mathbf{H}_r \mathbf{H}_f M + \mathbf{H}_r (\mathbf{v}^{-1}(M) + \mathbf{\delta} ))
\\
& = &
\mathbf{v}^{-1}(M) + \mathbf{\delta}
+ \mathbf{v}( M' + \mathbf{H}_r  \mathbf{\delta} )
\\
& & \mbox{recalling that }
\mathbf{v}(M' + \mathbf{\delta}) \approx
\mathbf{v}( M' ) + (\mathbf{v}.\nabla^t)(M') \mathbf{\delta}
\\
& = &
\mathbf{v}^{-1}(M) + \mathbf{\delta} +
\mathbf{v}( M' )
+ (\mathbf{v}.\nabla^t)( M' ) \mathbf{H}_r \mathbf{\delta}
\end{eqnarray*}
Please note that the derivative of
$\mathbf{v} = \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}$ are computed with respect to $M = M_{ref,\mathbb{Z}}$, i.e. in the voxel frame.
\begin{eqnarray*}
\lefteqn{ E = 0 } \\
& \Leftrightarrow &
\mathbf{\delta}  =
- \left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)( M' ) \mathbf{H}_r
\right)^{-1}
\left( \mathbf{v}^{-1}(M) + \mathbf{v}( M' )
\right)
\end{eqnarray*}

\subsubsection{Implementation}

$\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t) \mathbf{H}_r
\right)^{-1}$ are precomputed ($I_{ref}$ frame).

For every point $M = M_{flo,\mathbb{Z}}$, we iterate:
\begin{enumerate}
\itemsep -0.5ex
\item computation of
$M' = M_{ref,\mathbb{Z}} =
\mathbf{H}_r \mathbf{H}_f M + \mathbf{H}_r \mathbf{v}^{-1}(M)$
\item computation of
$\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t) \mathbf{H}_r
\right)^{-1} (M')$ and $\mathbf{v}( M' )$
\item test on
$\| \mathbf{v}^{-1}(M) + \mathbf{v}( M' ) \|$ (ending condition)
\item computation of
$\mathbf{\delta} =
\left(
\mathbf{Id} + (\mathbf{v}.\nabla^t)\mathbf{H}_r
\right)^{-1} (M')
\left( \mathbf{v}^{-1}(M) + \mathbf{v}( M' ) \right)$
\item update of $\mathbf{v}^{-1}(M)$:
$\mathbf{v}^{-1}(M) \leftarrow \mathbf{v}^{-1}(M) - \alpha \delta$
\end{enumerate}

\subsubsection{Initialization}

From $M' = M_{ref,\mathbb{Z}}$, we compute
\begin{eqnarray*}
M_{flo,\mathbb{Z}}
& = & \mathbf{H}_{flo,\mathbb{Z} \leftarrow \mathbb{R}}
M_{flo,\mathbb{R}} \\
 & = & \mathbf{H}_{flo,\mathbb{Z} \leftarrow \mathbb{R}}
 \left(
 M_{ref,\mathbb{R}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref,\mathbb{Z}} )
\right) \\
 & = & \mathbf{H}_{flo,\mathbb{Z} \leftarrow \mathbb{R}}
 \left(
 \mathbf{H}_{ref,\mathbb{R} \leftarrow \mathbb{Z}}
 M_{ref,\mathbb{Z}}
+ \mathbf{v}_{flo \leftarrow ref, \mathbb{R}}(M_{ref,\mathbb{Z}} )
\right)
\end{eqnarray*}

Please note that $M_{flo,\mathbb{Z}}$ has real coordinates, though it is a point defined in the discrete frame. $-\mathbf{v}( M' )$ is then distributed to the discrete points around  $M=M_{flo,\mathbb{Z}}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Image interpolation}

\section{Linear transformations}

Let us consider two images $I_0$ and $I_1$, and the transformation $A_{0 \leftarrow 1}$ that allows to resample $I_0$ into $I_1$ frame, ie to compute $I_0 \circ A_{0 \leftarrow 1}$.

To interpolate an image $I_t$ at an intermediary position $t \in [0 \ldots 1]$ from both $I_0$ and $I_1$,
we have to resample both $I_0$ and $I_1$ in $I_t$ frame and then combine them.

We have to estimate both $A_{0\leftarrow t}$ and $A_{1\leftarrow t}$, ie the transformations from $I_t$ towards $I_0$ and $I_1$, that enable to resample $I_0$ and $I_1$ in the frame of $I_t$ by
$I_0 \circ A_{0\leftarrow t}$ and $I_1 \circ A_{1\leftarrow t}$.

Indeed, let us consider $I_0$. To resample this image in $I_t$ frame, we pick every point (voxel) $M_t$ of $I_t$ frame, transform it into $I_0$ and compute (interpolate) its value there: it then requires the transformation from $I_t$ towards $I_0$ that is denoted by $A_{0\leftarrow t}$.

If we assume the "linearity" of the motion from $M_0$ to $M_1$, an intermediary point $M_t$ can be defined
\begin{enumerate}
\item either from $M_0$ and $M_1$ with
\begin{eqnarray*}
M_t & = & (1-t) M_0 + t M_1
=  (1-t) A_{0\leftarrow 1} M_1 + t M_1 \\
& = & \left( t \mathbf{Id} + (1-t) A_{0 \leftarrow 1} \right) M_1
\end{eqnarray*}
\item or from $M_1$ with
\begin{eqnarray*}
M_t & = & M_1 + (1-t) \overrightarrow{M_1 M_0}
= M_1 + (1-t) (M_0 - M_1) \\
& = & M_1 + (1-t) (A_{0\leftarrow 1} M_1 - M_1)
= \left( t \mathbf{Id} + (1-t) A_{0 \leftarrow 1} \right) M_1
\end{eqnarray*}
\end{enumerate}
thus
\begin{displaymath}
A_{t \leftarrow 1} = t \mathbf{Id} + (1-t) A_{0 \leftarrow 1}
\end{displaymath}
and $A_{1 \leftarrow t}$ is computed by inverting the previous matrix
\begin{displaymath}
A_{1 \leftarrow t} = A_{t \leftarrow 1}^{-1}
\end{displaymath}

The computation of $A_{0\leftarrow t}$ can be done
\begin{enumerate}
\item either with a similar calculation to the one of
$A_{1 \leftarrow t}$, i.e.
by first computing $A_{t \leftarrow 0}$ with
\begin{displaymath}
A_{t \leftarrow 0} = (1-t) \mathbf{Id} + t A_{1 \leftarrow 0}
\end{displaymath}
with $A_{1 \leftarrow 0} = A_{0 \leftarrow 1}^{-1}$ and second inverting it, ie $A_{0\leftarrow t} = A_{t \leftarrow 0}^{-1}$,

\item or by observing that
$M_t$ is partway on the "line" joining $M_0$ and $M_1$ and at a "distance" $t$   from $M_1$ and $(1-t)$ from $M_0$.
We have then
\begin{eqnarray*}
M_t =  (1-t) M_0 + t M_1
& \Leftrightarrow &
 M_0 = \frac{1}{1-t} M_t - \frac{t}{1-t} M_1 \\
& \Leftrightarrow &
 M_0
 = \frac{1}{1-t} M_t - \frac{t}{1-t} A_{1\leftarrow t} M_t \\
 & \Leftrightarrow &
 M_0
 = \left( \frac{1}{1-t} \mathbf{Id}
- \frac{t}{1-t} A_{1 \leftarrow t} \right) M_t
\end{eqnarray*}
Thus
\begin{displaymath}
A_{0 \leftarrow t} =  \frac{1}{1-t} \mathbf{Id}
- \frac{t}{1-t} A_{1 \leftarrow t}
\end{displaymath}

\end{enumerate}

Finally, the image $I_t$ can be interpolated from the resampled $I_0$ and $I_1$ into $I_t$ frame, ie $I_0 \circ A_{0 \leftarrow t}$ and $I_1 \circ A_{1 \leftarrow t}$ with
\begin{displaymath}
I_t = (1-t) \times I_0 \circ A_{0 \leftarrow t}
+ t \times I_1 \circ A_{1 \leftarrow t}
\end{displaymath}

\begin{attention}
When dealing with rigid transformations, the above interpolation scheme does not result in a rigidly displaced object/image, since a linear combination of matrices representing rigid displacements does not represent a rigid displacement (in the general case). If one wants to get an interpolation of the rigid displacement, one has to compute intermediary displacements along the geodesic line (in the rigid transformation manifold) from the identity to the final transformation $R_{0 \leftarrow 1}$. Typically, if one rotates a sphere, it may be wanted that each point of the sphere follows a circle arc instead of a straight line.
\end{attention}

\section{Non-linear transformations defined by vector fields}

Let us consider two images $I_0$ and $I_1$, and the transformation $T_{0 \leftarrow 1}$ that allows to resample $I_0$ into $I_1$ frame, ie to compute $I_0 \circ T_{0 \leftarrow 1}$. Please note that $T_{0 \leftarrow 1}$ is a function defined from $I_1$ towards $I_0$.
When dealing with non-linear transformations, $T_{0 \leftarrow 1}$ may be represented by a vector field $\mathbf{u}_{0 \leftarrow 1}$.
\begin{displaymath}
\left\{
\begin{array}{lcl}
T_{0 \leftarrow 1} & = & Id + \mathbf{u}_{0 \leftarrow 1} \\
T_{0 \leftarrow 1}(M) & = & M + \mathbf{u}_{0 \leftarrow 1}(M)
\quad \Longleftrightarrow \quad
M_0 = M_1 + \mathbf{u}_{0 \leftarrow 1}(M_1)
\end{array}
\right.
\end{displaymath}

To interpolate an image $I_t$ at an intermediary position $t \in [0 \ldots 1]$ from both $I_0$ and $I_1$, we have to estimate both $T_{0\leftarrow t}$ and $T_{1\leftarrow t}$, ie the transformations from $I_t$ towards $I_0$ and $I_1$, that enable to resample $I_0$ and $I_1$ in the frame of $I_t$ by
$I_0 \circ T_{0\leftarrow t}$ and $I_1 \circ T_{1\leftarrow t}$.

If we assume the "linearity" of the deformation from $M_1$ to $M_0$, an intermediary point $M_t$ can be defined
\begin{enumerate}
\item either from $M_0$ and $M_1$ with
\begin{eqnarray*}
M_t & = & (1-t) M_0 + t M_1
=  (1-t) \left( M_1 + \mathbf{u}_{0 \leftarrow 1}(M_1) \right) + t M_1 \\
& = &  M_1 + (1-t) \mathbf{u}_{0 \leftarrow 1}(M_1)
\end{eqnarray*}
\item or from $M_1$ with
\begin{eqnarray*}
M_t & = & M_1 + (1-t) \overrightarrow{M_1 M_0}
= M_1 + (1-t) (M_0 - M_1) \\
& = & M_1 + (1-t) \mathbf{u}_{0 \leftarrow 1}(M_1)
\end{eqnarray*}
\end{enumerate}
thus $T_{t \leftarrow 1}$ is defined by the vector field $\mathbf{u}_{t \leftarrow 1} = (1-t) \mathbf{u}_{0 \leftarrow 1}$, and $T_{1 \leftarrow t}$ is then simply obtained by inverting $T_{t \leftarrow 1}$
\begin{displaymath}
T_{1 \leftarrow t} = T^{-1}_{t \leftarrow 1}
\end{displaymath}
Let $\mathbf{u}_{1 \leftarrow t}$ be the vector field representing $T_{1 \leftarrow t}$, and we have
\begin{displaymath}
M_1 = M_t + \mathbf{u}_{1 \leftarrow t}(M_t)
\end{displaymath}

\begin{attention}
$\mathbf{u}_{1 \leftarrow t}$ \textit{is not} $- \mathbf{u}_{t \leftarrow 1} = - (1-t) \mathbf{u}_{0 \leftarrow 1}$.
% Indeed, $\mathbf{u}_{0 \leftarrow 1}$ is a function defined from $I_1$ (and so is $- \mathbf{u}_{t \leftarrow 1}$), while $\mathbf{u}_{1 \leftarrow t}$ is a function defined from $I_t$.
The transformation $T_{t \leftarrow 1}$ allows to compute the point $M_t \in I_t$ that is the transformed point $M_1 \in I_1$ ($M_t$ and $M_1$ have different coordinates as soon as $T_{t \leftarrow 1}$ is different from the identity transformation) by
\begin{equation}
\label{eq:Tt1}
M_t = M_1 + \mathbf{u}_{t \leftarrow 1}(M_1)
\end{equation}
Using the opposite of $\mathbf{u}_{t \leftarrow 1}$ to define the inverse of $T_{t \leftarrow 1}$ comes to state that
\begin{displaymath}
M_1 = M_t - \mathbf{u}_{t \leftarrow 1}(M_t)
\end{displaymath}
However, from Eq. (\ref{eq:Tt1}) we have $M_1 = M_t - \mathbf{u}_{t \leftarrow 1}(M_1)$. Thus,  using the opposite vector field to define the inverse transformation is valid iff
\begin{displaymath}
\mathbf{u}_{t \leftarrow 1}(M_t) = \mathbf{u}_{t \leftarrow 1}(M_1)
\Leftrightarrow
\mathbf{u}_{0 \leftarrow 1}(M_t) = \mathbf{u}_{0 \leftarrow 1}(M_1)
\end{displaymath}
This may be a good estimate in case of small (hence $M_t$ will be close to $M_1$) and slowly varying deformations, but is obviously false in the general case (see Fig. \ref{fig:invert:transformation}).
\end{attention}

\begin{figure}[ht]
\begin{center}
 \includegraphics[height=5cm]{figures/fig-invert-trsf.png}
\end{center}
\caption{\label{fig:invert:transformation}$M_t$ is $M_1$ transformed by $T_{t \leftarrow 1}$, i.e. $M_t = M_1 + \mathbf{u}_{t \leftarrow 1}(M_1) $ where $\mathbf{u}_{t \leftarrow 1}(M_1)$ is the blue vector. $T_{t \leftarrow 1}^{-1}$ at $M_t$ should then by defined by the opposite of this blue vector (so that $M_t$ can project on $M_1$). By building the inverse of $T_{t \leftarrow 1}$ with the opposite of the $\mathbf{u}_{t \leftarrow 1}$ vector field, $T_{t \leftarrow 1}^{-1}$ at $M_t$ would be defined by $- \mathbf{u}_{t \leftarrow 1}(M_t)$, i.e. the dashed red vector (and thus not equal to $- \mathbf{u}_{t \leftarrow 1}(M_1)$, the opposite of the blue vector). This can be an acceptable approximation iff $\mathbf{u}_{t \leftarrow 1}(M_t)$ (the red vector) is sufficiently similar to $\mathbf{u}_{t \leftarrow 1}(M_1)$ (the blue vector).}
\end{figure}

$M_t$ is partway on the "line" joining $M_0$ and $M_1$ and at a "distance" $t$   from $M_1$ and $(1-t)$ from $M_0$.
We have then
\begin{eqnarray*}
M_t =  (1-t) M_0 + t M_1
& \Leftrightarrow &
 M_0 = \frac{1}{1-t} M_t - \frac{t}{1-t} M_1 \\
& \Leftrightarrow &
 M_0
 = \frac{1}{1-t} M_t - \frac{t}{1-t} T_{1\leftarrow t} M_t \\
& \Leftrightarrow &
 M_0
 = \frac{1}{1-t} M_t - \frac{t}{1-t}
 \left( M_t + \mathbf{u}_{1 \leftarrow t}(M_t) \right) \\
 & \Leftrightarrow &
 M_0
 =  M_t - \frac{t}{1-t}
 \mathbf{u}_{1 \leftarrow t}(M_t) \\
\end{eqnarray*}

The transformation $T_{0 \leftarrow t}$ is then represented by the vector field $\left(- \frac{t}{1-t}\mathbf{u}_{1 \leftarrow t}\right)$.

Finally, the image $I_t$ can be interpolated from the resampled $I_0$ and $I_1$ into $I_t$ frame, ie $I_0 \circ T_{0 \leftarrow t}$ and $I_1 \circ T_{1 \leftarrow t}$ with
\begin{displaymath}
I_t = (1-t) \times I_0 \circ T_{0 \leftarrow t}
+ t \times I_1 \circ T_{1 \leftarrow t}
\end{displaymath}

max_stars_repo_name: Xqua/standalone-Mouse

max_issues_repo_name: Xqua/standalone-Mouse

max_forks_repo_name: Xqua/standalone-Mouse


text:
\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=2cm]{geometry}
% \usepackage[parfill]{parskip}
\usepackage{expl3}
\usepackage{float}
\usepackage{listings}
\usepackage{lmodern}
\usepackage{courier}
\usepackage{soul}
\usepackage{xcolor}
\usepackage{url}
\usepackage{hyperref}
\usepackage{filecontents}
\usepackage{classdiagram}

\definecolor{kwd}{RGB}{138, 74, 11}
\definecolor{com}{RGB}{134, 134, 134}
\definecolor{pun}{RGB}{20, 86, 128}
\definecolor{typ}{RGB}{43, 145, 175}

\lstset {
  language=         {[LaTex]TeX},
  basicstyle=       \footnotesize\ttfamily,
%   basicstyle=       \ttfamily,
  frame=            single,
  tabsize=          2,
  commentstyle=     \color{com},
  texcsstyle=        *\color{kwd},
  keywordstyle=      \color{kwd},
  captionpos=        b,
  breaklines=       true,
  abovecaptionskip= 4ex,
  morekeywords=     {},
  moretexcs=        {usetikzlibrary, path, node, relation, attribute, operation, position, abstract},
  literate=
    {\{}{{\textcolor{pun}{\{}}}1
    {\}}{{\textcolor{pun}{\}}}}1
    {[}{{\textcolor{pun}{[}}}1
    {]}{{\textcolor{pun}{]}}}1
    {(}{{\textcolor{pun}{(}}}1
    {)}{{\textcolor{pun}{)}}}1
    {=}{{\textcolor{pun}{=}}}1
    {\$}{{\textcolor{typ}{\$}}}1
    {*}{{\textcolor{kwd}{*}}}1
}

\ExplSyntaxOn

\NewDocumentCommand \code {m}
{
  {\ttfamily #1}
}

\NewDocumentCommand \cmd {mo}
{
  \IfValueTF{#2}
  {
    {\ttfamily\textcolor{kwd}{\char`\\#1}\textcolor{pun}{[}#2\textcolor{pun}{]}}
  }
  {
    {\ttfamily\textcolor{kwd}{\char`\\#1}}
  }
}

\NewDocumentCommand \macro {m}
{
  {\ttfamily\textcolor{kwd}{\char`\\#1}}
}

\NewDocumentCommand \oarg {m}
{
  {\ttfamily\textcolor{pun}{[}#1\textcolor{pun}{]}}
}

\NewDocumentCommand \marg {m}
{
  {\ttfamily\textcolor{pun}{\{}#1\textcolor{pun}{\}}}
}

\NewDocumentCommand \targ {m}
{
  {\ttfamily\textcolor{pun}{<}#1\textcolor{pun}{>}}
}

\NewDocumentCommand \default {m}
{
  \mbox{$\langle$#1$\rangle$}
}

\NewDocumentCommand \listing {m}
{
  \minipage{\linewidth}
  \lstinputlisting{#1}
  \endminipage
}

\ExplSyntaxOff

\title{The {\bfseries \ttfamily classdiagram} package}
\author{Linus Sunde}

\begin{document}
\maketitle

\abstract

The {\ttfamily classdiagram} package allows for creation of UML Class Diagrams. It uses PGF/TikZ to produces the vector graphics. The creation of the package was inspired by the {\ttfamily pgf-umlcd} package, which provides similar functionality. Many thanks to all the patient people at \url{http://tex.stackexchange.com/} who took their time to answer my beginner questions. This package is a work in progress and might never be finished.

\tableofcontents

\section{User Commands}

\subsection{\code{class} and \code{interface}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Class}  % Doesn't allow special characters
    \position{0, 0}
    \attribute[public]{publicAttribute : type}
    \attribute[protected]{packageAttribute : type}
    \attribute[package]{protectedAttribute : type}
    \attribute[private]{privateAttribute : type}
    \operation[public]{publicOperation() : type}
    \operation[protected]{packageOperation() : type}
    \operation[package]{protectedOperation() : type}
    \operation[private]{privateOperation() : type}
  \end{class}

  \begin{interface}{Interface}
    \position[right=0.5cm, anchor=north west]{Class.north east}
    \attribute{attribute : type}
    \operation{operation() : type}
  \end{interface}

  \begin{class}{AbstractClass}
    \position[right=0.5cm, anchor=south west]{Class.south east}
    \abstract
    \attribute*{abstractAttribute : type}
    \operation*{abstractOperation() : type}
  \end{class}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{generalization} (Class Inheritance)}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Person}
    \attribute[private]{name : String}
    \operation[public]{setName(String) : void}
    \operation[public]{getName() : String}
  \end{class}

  \begin{class}{Programmer}
    \position[right=2cm]{Person.east}
    \attribute[private]{linesWritten : type}
    \operation[public]{program() : Code}
    \operation[public]{getLinesWritten() : int}
  \end{class}

  \generalization{Programmer}{Person}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{realization} (Interface Implementation)}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{interface}{Edible}
    \operation[public]{eat() : void}
  \end{interface}

  \begin{class}{Pizza}
    \position[right=2cm]{Edible.east}
    \attribute[private]{toppings : Set<Edible>}
    \operation[public]{addTopping(Edible) : void}
  \end{class}

  \realization{Pizza}{Edible}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{association}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Programmer}
    \attribute[private]{linesWritten : type}
    \operation[public]{program() : Program}
    \operation[public]{getLinesWritten() : int}
  \end{class}

  \begin{class}{Pizza}
    \position[right=3cm]{Programmer.east}
    \attribute[private]{toppings : Set<Edible>}
    \operation[public]{addTopping(Edible) : void}
  \end{class}

  \association{Programmer}[owns][0..*]{Pizza}[owner][1]

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{association}[unidirectional]}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{PizzaBox}
    \attribute[private]{position : Position}
    \attribute[private]{size : Size}
    \operation[public]{open() : Pizza}
  \end{class}

  \begin{class}{Pizza}
    \position[right=3cm]{PizzaBox.east}
    \attribute[private]{toppings : Set<Edible>}
    \operation[public]{addTopping(Edible) : void}
  \end{class}

  \association[unidirectional]{PizzaBox}[contents][1]{Pizza}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{aggregation}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Company}
    \attribute[private]{name : String}
    \operation[public]{hire(Programmer) : void}
    \operation[public]{fire(Programmer) : void}
  \end{class}

  \begin{class}{Programmer}
    \position[right=4cm]{Company.east}
    \attribute[private]{linesWritten : type}
    \operation[public]{program() : Program}
    \operation[public]{getLinesWritten() : int}
  \end{class}

  \aggregation{Company}[employees][0..*]{Programmer}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{composition}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Company}
    \attribute[private]{name : String}
    \operation[public]{hire(Programmer) : void}
    \operation[public]{fire(Programmer) : void}
  \end{class}

  \begin{class}{Founder}
    \position[right=4cm]{Company.east}
    \attribute[private]{balance : int}
    \operation[public]{doNothing() : void}
  \end{class}

  \composition{Company}[founder][1]{Founder}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{nested}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Outer}
  \end{class}

  \begin{class}{Inner}
    \position[right=2cm]{Outer.east}
  \end{class}

  \nested{Outer}{Inner}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{relation}}

All of the above relations uses \cmd{relation} behind the scenes.

\vspace{1em}{\centering\macro{relation}\oarg{options}\marg{from}\oarg{role}\oarg{multiplicity}\marg{to}\oarg{role}\oarg{multiplicity}\targ{via}}\vspace{1em}

The \cmd{association} example demonstrated what all the arguments except \oarg{options} and \targ{via} do. First, \oarg{options} specifiy TikZ options to apply to the relation's ``arrow''. Secondly, \targ{via} allows for specification of a list of intermediary points, via which the ``arrow'' will pass. All of these arguments are available for all relation types, but they do not always make sense to use. The specification of this function is subject to change. It should for example be possible to provide TikZ options for each coordinate in \targ{via}.

\begin{filecontents*}{temp}
\begin{tikzpicture}[show background grid]

  \begin{class}{From}
    \position{0, -2}
  \end{class}

  \begin{class}{To}
    \position{5, 2}
  \end{class}

  \relation[red, out = 90, in = -90, ox-i>]{From}[Role1][Mult1]{To}[Role2][Mult2]<(2,2),(3,-2)>

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{\cmd{package}}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \begin{class}{Person}
    \abstract
    \attribute[private]{name : String}
    \operation[public]{getName() : String}
  \end{class}

  \begin{class}{Parent}
    \position{-2, -3}
  \end{class}

  \begin{class}{Child}
    \position{2, -3}
  \end{class}

  \generalization{Parent}{Person}
  \generalization{Child}{Person}
  \package{Family}{(Person)(Parent)(Child)}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\section{Configuration}

\subsection{Text}
The \code{classdiagram} package defines a number of macros that are used to generate the recurring texts. These can be redefined to change the text and/or style.

\begin{tabular}{ll}
  \macro{textAbstractClass}     & Defines the stereotype used for abstract classes: \textAbstractClass \\
  \macro{textInterface}         & Defines the stereotype used for interfaces: \textInterface \\
\end{tabular}

\begin{tabular}{lll}
  \macro{styleClass}            & sffamily bfseries & {\styleClass Example} \\
  \macro{styleAttribute}        & sffamily small    & {\styleAttribute Example} \\
  \macro{styleOperation}        & sffamily small    & {\styleOperation Example} \\
  \macro{stylePackage}          & sffamily bfseries & {\stylePackage Example} \\
  \macro{styleAbstractClass}    & itshape           & {\styleAbstractClass Example} \\
  \macro{styleAbstractAttribute}& itshape           & {\styleAbstractAttribute Example} \\
  \macro{styleAbstractOperation}& itshape           & {\styleAbstractOperation Example} \\ \\
\end{tabular}

\begin{filecontents*}{temp}
\begin{tikzpicture}

  \renewcommand{\textAbstractClass}{<<abstract>> \\}
  \renewcommand{\styleAbstractClass}{\sffamily \bfseries}
  \renewcommand{\styleAbstractAttribute}{\tiny\ttfamily}
  \renewcommand{\styleAbstractOperation}{\huge\sffamily}

  \begin{class}{AbstractClass}
    \position[right=0.5cm, anchor=south west]{Class.south east}
    \abstract
    \attribute*{abstractAttribute : type}
    \operation*{abstractOperation() : type}
  \end{class}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{Styles}

The \code{classdiagram} package defines a number of TikZ styles that are used to generate the class diagrams, and which can be overridden to change the look and feel.

\begin{tabular}{l}
cd relation \\
cd relation text \\
cd relation role start \\
cd relation role end \\
cd relation multiplicity start \\
cd relation multiplicity end \\
cd nested \\
cd association \\
cd unidirectional \\
cd generalization \\
cd realization \\
cd aggregation \\
cd composition \\
cd package \\
cd package box \\
cd package label \\
\end{tabular}

\begin{filecontents*}{temp}
\begin{tikzpicture}[
  cd common/.append style={
    sharp corners, bottom color=white, top color=white},
  cd package label/.append style={
    sharp corners, fill=white, anchor=north west, outer ysep=0.4pt},
  cd package box/.append style=
    {sharp corners, bottom color=white, top color=white}]

  \begin{class}{Person}
    \abstract
    \attribute[private]{name : String}
    \operation[public]{getName() : String}
  \end{class}

  \begin{class}{Parent}
    \position{-2, -3}
  \end{class}

  \begin{class}{Child}
    \position{2, -3}
  \end{class}

  \generalization{Parent}{Person}
  \generalization{Child}{Person}
  \package{Family}{(Person)(Parent)(Child)}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\subsection{Arrows}

The \code{classdiagram} package defines a number of TikZ arrowheads.

\begin{tabular}{ll}
\code{-a>} & \tikz \draw [-a>] (0,0) -- (1,0); \\
\code{-i>} & \tikz \draw [-i>] (0,0) -- (1,0); \\
\code{ox-} & \tikz \draw [ox-] (0,0) -- (1,0); \\
\code{<>-} & \tikz \draw [<>-] (0,0) -- (1,0); \\
\code{<*>-} & \tikz \draw [<*>-] (0,0) -- (1,0); \\
\end{tabular}

\section{Example}

\begin{filecontents*}{temp}
\begin{tikzpicture}[scale=0.7, every node/.style={transform shape}]

  \begin{class}{Person}
    \abstract
    \attribute[private]{name : String}
    \operation[public]{getName() : String}
  \end{class}

  \begin{class}{Company}
    \position[right=4]{Person}
    \attribute[private]{name : String}
    \operation[public]{hire(Programmer) : void}
    \operation[public]{fire(Programmer) : void}
  \end{class}

  \begin{class}{Founder}
    \position[right=5]{Company}
    \attribute[private]{balance : int}
    \operation[public]{doNothing() : void}
  \end{class}

  \begin{class}{Programmer}
    \position[below=2]{Person}
    \attribute[private]{linesWritten : type}
    \operation[public]{program() : Program}
    \operation[public]{getLinesWritten() : int}
  \end{class}

  \begin{interface}{Edible}
    \position{9, -6}
    \operation[public]{eat() : void}
  \end{interface}

  \begin{class}{Ham}
    \position[below=2]{Edible}
  \end{class}

  \begin{class}{Cheese}
    \position[right=1]{Ham}
  \end{class}

  \begin{class}{Tomato}
    \position[right=1]{Cheese}
  \end{class}

  \begin{class}{Pizza}
    \position[left=1]{Ham}
    \attribute[private]{toppings : Set<Edible>}
    \operation[public]{addTopping(Edible) : void}
  \end{class}

  \begin{class}{PizzaBox}
    \position[left=4.5]{Pizza}
    \attribute[private]{position : Position}
    \attribute[private]{size : Size}
    \operation[public]{open() : Pizza}
  \end{class}

  \aggregation[bend right=90]{Pizza}[has][0..1]{Ham}
  \aggregation[bend right=90]{Pizza}[has][0..1]{Cheese}
  \aggregation[bend right=90]{Pizza}[has][0..1]{Tomato}
  \realization{Ham}{Edible}
  \realization{Cheese}{Edible}
  \realization{Tomato}{Edible}
  \realization{Pizza}{Edible}
  \association[unidirectional]{PizzaBox}[contents][1]{Pizza}
  \association[unidirectional]{Programmer}[owns][0..*]{PizzaBox}
  \aggregation[out=-90, in=0]{Company}[employees][0..*]{Programmer}
  \composition{Company}[founder][1]{Founder}
  \generalization{Programmer}{Person}
  \package{Family}{(Person)(Programmer)}
  \package[bottom color=green!50, top color=green!10]{Organization}{(Company)(Founder)}
  \package[bottom color=red!50, top color=red!10]{Food}{(Pizza)(Ham)(Cheese)(Tomato)(Edible)}

\end{tikzpicture}
\end{filecontents*}

\begin{figure}[H]
  \centering
  \input{temp}
\end{figure}

\listing{temp}

\end{document}

max_stars_repo_name: Lej/classdiagram

max_issues_repo_name: Lej/classdiagram

max_forks_repo_name: Lej/classdiagram


text:
\subsection*{Arrays}

Arrays in Source are created using literal array expressions:
\begin{lstlisting}
let my_array_1 = [];
let my_array_2 = [42, 71, 13];
\end{lstlisting}

max_stars_repo_name: jaesimin/js-slang

max_issues_repo_name: jaesimin/js-slang

max_forks_repo_name: jaesimin/js-slang