text:
% Copyright (C) He Guanyuming 2020
% The file is licensed under the MIT license.

\section{Natural Numbers}
\subsection{The Peano Axioms}

\subsection{Addition of Natural Numbers}
\begin{prop}
(Exercise 2.2.1) \label{exercise2.2.1}
The addition of natural numbers is associative. That is, $(a+b)+c=a+(b+c)$.
\end{prop}
\begin{proof}
Use induction: First, $(0+b)+c=b+c=0+(b+c)=b+c$.

Then, assume that $(n+b)+c=n+(b+c)$, thus
\begin{align*}
(S(n)+b)+(c)
&= S(n+b)+c\\
&= S(n+b+c)\\
&= S(n+(b+c)) \tag{By assumption}\\
&= S(n)+(b+c)
\end{align*}
, which closes the induction. \qedhere
\end{proof}

\begin{prop}
(Exercise 2.2.2) \label{exercise2.2.2}
For any positive natural number $n$, there is exactly one natural number $m$ that $S(m) = n$.
\label{prop5}
\end{prop}

\begin{proof}
Use induction: When $n=0$, the statement is vacuously right.

Assume that the statement is true for a natural number $n$, thus
\begin{description}
\item[Existence]
\[
S(S(m)) = S(n)
\]
\item[Uniqueness]
It is obvious according to axiom 3.
\end{description}
\end{proof}

\begin{prop}
(Exercise 2.2.3) \label{exercise2.2.3}
\begin{enumerate}
\item Order is reflective $a \geq a$
\item Order is transitive $a \geq b \wedge b \geq c \Longrightarrow a \geq c$
\item Order is anti-symmetric $a \geq b \wedge b \geq a \Longrightarrow a=b$
\item Addition preserves order $a \geq b \Longrightarrow a+c \geq b+c$
\item $a<b \Longleftrightarrow S(a) \leq b$
\item $a<b$ Iff for positive natural number $c$, $b=a+c$
\end{enumerate}
\end{prop}
\begin{proof}
(1) It is immediately proven by $a=a+0$.

(2)
\begin{align*}
a \geq b &\wedge b \geq c \Longrightarrow \\
a = b+m &\wedge b = c+n \Longrightarrow \\
a = c+n+m &= c+(n+m) \Longrightarrow \\
a &\geq c
\end{align*}

(3)
By definition of order,
\begin{align*}
a \geq b &\wedge b \geq a \Longrightarrow \\
a = b+m &\wedge b = a+n \Longrightarrow \\
a &= a+(n+m) \Longrightarrow \\
n+m&=0 \Longrightarrow \tag{By Lemma \ref{lem3}}\\
n=m&=0 \Longrightarrow \tag{By Corollary \ref{coro1}} \\
b=a+0&=a
\end{align*}

(4)
\begin{align*}
a \geq b &\equiv \\
a = b+n &\equiv \\
a+c=(b+n)+c=b+(n+c)=b+(c+n)=(b+c)+n &\equiv \\
a+c \geq b+c
\end{align*}

(5)
\begin{align*}
a<b &\Longleftrightarrow \\
b=a+p &\Longleftrightarrow \\
b+1=a+p+1=a+1+p=S(a)+p \\
=S(a)+S(n) \tag{By proposition \ref{prop5}, $p$ is always some natural number $n$'s successor}\\
=S(a)+n+1 &\Longleftrightarrow \\
b=S(a)+n &\Longleftrightarrow \tag{By cancellation law} \\
b \geq S(a)
\end{align*} \label{prop.5}

(6)
On one hand, $b=a+c$ immediately gives $a<b$.

On the other hand, according to (5), $a<b$ gives
\begin{align*}
S(a) \leq b  &\Longrightarrow\\
b = S(a) + n& \\
= a+1+n = a+(n+1)&
\end{align*}, where $n+1$ is positive. \label{prop.6}
\end{proof}

\begin{prop}
(Exercise 2.2.4) \label{exercise2.2.4}
For two natural number $m,n$, $m$ either $>$, or $=$, or $<n$.
\end{prop}
\begin{proof}
Tao's book has proven that at most one statement can be true at a time.

Now we are proving the remnant. Use induction: When $m=0$, for any natural number $n$,
$0=n$, or $0 \neq n$. Under the latter case:
\begin{lem}
$n$ is positive $\Longleftrightarrow n>0$
\end{lem}
\begin{proof}
On one hand, $n>0$ immediately gives $n$ is positive.

On the other hand, $n=0+n$ gives $n \geq 0$. And $n$ being positive implies that $n \neq 0$.
So $n > 0$.
\end{proof}

According to the lemma, in this situation, $0<n$. So 0 either $<$ or $=$ $n$.

Assume that we have proven the statement for a natural number $m$, thus when $m<n$, according to
Proposition \ref{prop.5}, $S(m) \leq n$, so $S(m)$ either $<$ or $=n$. When $m=n$,
$S(m)=n+1 \Longrightarrow S(m) > n$ by Proposition \ref{prop.6}. When $m>n$, according to Proposition
\ref{prop.6},
\[
m=n+p \Longrightarrow S(m)=n+(p+1) \Longrightarrow S(m)>n
\]. This closes the induction, implying that at least one of the three statements is true.
\end{proof}

\declareexercise{2.2.5}
\begin{proof}
Let $Q(n)$ be a property of a natural number $n$ such that $Q(n)$ is true iff for all $m_0\leq m'<n$,
$P(m')$ is always true. Use induction: $Q(0)$ is vacuously true.

Assume that $Q(n)$ is true. Here we will be using the proposition we just proved, for because we have
known that there will and only will be one true statement, we can classify the conditions as
following: When $S(n)<m_0$, $Q(S(n))$ is also vacuously true. When $S(n)=m_0$, $Q(S(n))$ is true
because $P(m_0)$ is true. And when $S(n)>m_0$:

First we need to prove that $n$ is the only natural number $\geq m_0$ which satisfies $m_0 \leq n<S(n)$
but doesn't satisfy $m_0 \leq n<n$, so that we only need to prove $P(n)$ is true in the induction,
which is obvious.
\begin{lem}
There is no natural number between $n$ and $S(n)$. That is, there is no such natural number $m$ that
$n<m<S(n)$. \label{lem5}
\end{lem}
\begin{proof}
Presume the negation. Thus, $m=n+p \wedge S(n)=m+q$, where $p,q$ are positive. Substituting $m$
with $n+p$ we have $S(n)=n+p+q$. Let $p=S(a)=a+1$, which is always possible according to Proposition
\ref{prop5}. Thus $n+1=n+1+a+q \Longrightarrow n=n+a+q$, which means $a+q$ has to be 0, and which is
impossible.
\end{proof}

Given a natural number $a$, it either $\geq$ or $<S(n)$, and also either $\geq$ or $<n$. Should it
satisfy $m_0 \leq a<S(n)$ but doesn't satisfy $m_0 \leq a<n$, it then must satisfy $n \leq a<S(n)$,
that is, either $a=n$ or $n<a<S(n)$. The latter, according to the lemma, is impossible. So $n$ is the
only natural number $\geq m_0$ which satisfies $m_0 \leq n<S(n)$ but doesn't satisfy $m_0 \leq n<n$.

Then $Q(S(n)) \Longleftrightarrow Q(n) \wedge P(n)$, which is true. This closes the induction. So $Q(n)$ is
true for all natural number $n \geq m_0$. And this implies that $P(n)$ is true.
\end{proof}

\declareexercise{2.2.6}
\begin{proof}
Use induction: When $n=0$, for all natural number $m\leq 0$, $P(m)$ is true.

Assume that we have proven for a natural number $n$ that if $P(n)$ is true, then for all natural number
$m\leq n$, $P(m)$ is also true. Thus, $P(S(n)) \Longrightarrow P(n) \Longrightarrow \forall m\leq n, P(m)$
is true. According to Lemma \ref{lem5},
$(\forall m\leq n, P(m)) \wedge P(S(n)) \Longleftrightarrow \forall m \leq S(n), P(m)$. This closes the
induction.
\end{proof}

\subsection{Multiplication of Natural Numbers}
\begin{lem}
(Exercise 2.3.1) \label{exercise2.3.1}
Multiplication is commutative. That is, $a \times b = b \times a$.
\end{lem}
\begin{proof} I

Try to imitate the way we prove the commutativity of addition.

\begin{lem}
\[
0 \times a = a \times 0 \label{lem2.3.1}
\]
\end{lem}
\begin{proof}
Use induction: $0 \times 0 = 0$. Assume that $n \times 0 = 0$ is
true. Thus, $S(n) \times 0 = (n \times 0) + 0 = 0$, which closes the induction.
\end{proof}

\begin{lem}
\[
a \times S(b) = a \times b + a \label{lem2.3.2}
\]
\end{lem}
\begin{proof}
Use induction: $0 \times S(b) = 0 = 0 \times b + 0$.

Assume that $a \times S(b) = ab + a$ is true. Thus,
\begin{align*}
S(a)S(b)
&= aS(b) + S(b) \tag{By Def.}\\
&= ab + a + S(b) \tag{By assumption}\\
&= ab+S(a)+b \tag{By addition's properties}\\
&= (ab+b)+S(a) \tag{By addition's properties}\\
&= S(a)b + S(a) \tag{By Def.}
\end{align*}, which closes the induction.
\end{proof}

Now use induction on $a$. First, when $a=0$, by Lemma \ref{lem2.3.1} we have $ab=ba$.

Assume that $ab=ba$ is true. Thus,
\begin{align*}
S(a)b
&=ab+b \\
&=ba+b  \\
&=bS(a) \tag{Lemma \ref{lem2.3.2}}
\end{align*}, which close the induction.

\end{proof}

\begin{proof} II In this proof we will use the distribution law of multiplication.

First, we have Lemma \ref{lem2.3.1}

Before we prove the remnant, we need to prove the distribution law. That
is, $a \times (b+c) = ab + ac$ \label{distriLaw}
\begin{proof}
Use induction: $0 \times (b+c)= 0\times b+0\times c=0$.

Assume that $a \times (b+c) = ab + ac$ is ture. Thus,
\begin{align*}
S(a) \times (b+c)
&= (a(b+c))+(b+c) \\
&= (ab+ac)+(b+c) \tag{By assumption} \\
&= (ab)+b+(ac)+c \\
&= S(a)b+S(a)c
\end{align*}, which closes the induction.
\end{proof}

We still have to prove $n \times 1 = n$ before proceeding. Use induction: $0 \times 1 = 0$. Assume that
$n \times 1 = n$. Thus, $S(n) \times 1 = (n\times 1)+1=n+1=S(n)$.

Now we can proceed the proof. Assume that $a \times b = b \times a$. Thus,
\begin{align*}
S(a)b
&= (ab)+b \\
&= (ba)+b \tag{By assumption} \\
&= b(a+1) \tag{By $b\times 1=b$ and the distribution law}\\
&= b \times S(a)
\end{align*}. This closes the induction.
\end{proof}

\begin{lem} \label{lem2.3.3}
(Exercise 2.3.2) \label{exercise2.3.2}
\[mn \neq 0 \Longleftrightarrow m \neq 0 \wedge n \neq 0\]
\end{lem}

\begin{proof}
On one hand,
let $m=S(a),\ n=S(b)$, where $a,b$ are natural numbers.
\begin{align*}
mn
&= S(a)S(b) \\
&= aS(b) + S(b)
\end{align*}

which, if $a \neq 0$, is the sum of two positive numbers, and is thus positive, and which, if $a = 0$,
is a positive number $S(b)$.

On the other hand, if either of $m,n$ is 0, then $mn$ must be zero. So $mn \neq 0 \Longrightarrow m \neq 0
\wedge n \neq 0$.
\end{proof}

Distribution law has been proved \hyperref[distriLaw]{here}.

\begin{prop}
(Exercise 2.3.3) \label{exercise2.3.3}
\[
(ab)c = a(bc)
\]
\end{prop}
\begin{proof}
Use induction on $a$.
First, $(0b)c=0c=0=0(bc)$.

Assume that $(ab)c = a(bc)$ is true. Thus,
\begin{align*}
(S(a)b)c
&= (ab+b)c \\
&= c(ab+b) \tag{Commutativity} \\
&= c(ab) + cb \tag{Distribution law} \\
&= (ab)c + bc \tag{Commutativity} \\
&= a(bc) + bc \tag{The induction hypothesis} \\
&= S(a)(bc)
\end{align*}. And now we can close the induction.
\end{proof}

\begin{prop}
\label{prop2.3.1}
Multiplication preserves order. That is, if $a>b \wedge c>0$, then $ac > bc$.
\end{prop}
\begin{proof}
\begin{align*}
a>b
&\Longrightarrow \\ a = b + p
&\Longrightarrow \\ ac = bc + pc
\end{align*}
According to Lemma \ref{lem2.3.3}, $pc$ is positive. Therefore, $ac>bc$.
\end{proof}

\begin{coro}
Cancellation law.
\[
ac=bc \wedge c \neq 0 \Longrightarrow a=b
\]
\end{coro}
\begin{proof}
Either $a=b$, or $a<b$, or $a>b$. Suppose that $a \neq b$. Therefore, $ac$ either $<$ or $>bc$, which,
according to Proposition \ref{prop2.3.1}, gives a contradiction. So $a=b$.
\end{proof}

\begin{prop}
(Exercise 2.3.4) \label{exercise2.3.4}
\[
(a+b)^2=a^2+2ab+b^2
\]
(Suppose that we have known $n^2=n \times n$)
\end{prop}
\begin{proof}
\begin{align*}
(a+b)(a+b)
&= (a+b)a+(a+b)b \tag{Distribution law} \\
&= a(a+b) + b(a+b) \tag{Commutativity} \\
&= a^2+ab+ba+b^2 \tag{Distribution law} \\
&= a^2+ab+ab+b^2 \tag{Commutativity}
\end{align*}

Now we prove that $2ab = ab+ab$.
\begin{align*}
2ab
&=S(1)ab \\
&=(1ab)+ab\\
&=(S(0)ab)+ab\\
&=(0ab+ab)+ab\\
&=ab+ab
\end{align*}

The proof is over. \qedhere
\end{proof}

\begin{prop}
(Exercise 2.3.5) \label{exercise2.3.5}
Euclidean algorithm. For any natural number $n$, positive number $p$, there exist natural numbers $m,r$
such that $n=mp+r$.
\end{prop}
\begin{proof}
For any natural number $p$, we induct on $n$. Firstly, $0=0p+0$.

Assume that the statement for $n$ is true. We know that $r<p$. Then $S(r)$ either $=$ or $<p$
(Proposition \ref{prop.5}). On the latter case, simply let $r'=S(r),\ m'=m$, which satisfies the
restriction $0\leq r' <p$

On the former case, let $m'=S(m),\ r'=0$, and we have
\begin{align*}
m'p+r'
&= S(m)p+0\\
&= mp + p\\
&= mp + S(r) \tag{$p=S(r)$}\\
&= S(mp+r)\\
&= S(n)
\end{align*}.
And now we can close the induction.
\end{proof}

max_stars_repo_path: Natural Numbers.tex

max_issues_repo_path: Natural Numbers.tex

max_forks_repo_path: Natural Numbers.tex


text:
\begin{frame}
	\begin{center}
		\Huge Implementation
	\end{center}
\end{frame}

\subsection{Layers in Comparison}
\subsubsection{Traditional}
\begin{frame}[label=overview_traditional_layering]{Overview: Traditional Layering}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{figure}
				\centering
				\includegraphics[height=0.6\textheight]{assets/layers/traditional}
			%	\caption{ \small Traditional: \cite{zfs2003} }
			\end{figure}
		\end{column}
		\pause
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item<5-> System Call: interface to applications
				\item<4-> File System: on-disk data format %only in this sense, a file system is much more, of course, e.g. an organizational abstraction
				\item<3-> Volume Manager: volume abstraction
				\item<2-> Device Driver: hardware abstraction
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Traditional: Example On-Disk Format}
	\begin{figure}
	\centering
	\includegraphics[height=0.75\textheight]{assets/traditional_fs}
	\end{figure}
\end{frame}

\begin{frame}{Traditional: Example \texttt{read}(3) \& \texttt{write}(3)}
	\begin{figure}
		\centering
		\includegraphics[height=0.75\textheight]{assets/traditional_fs}
	\end{figure}
\end{frame}

\againframe<6->{overview_traditional_layering}
\begin{frame}{Comparison: Traditional vs. ZFS}
		\begin{columns}[c]
			\begin{column}{0.4\textwidth}
				\begin{figure}
					\centering
					\includegraphics[height=0.7\textheight]{assets/layers/traditional}
				%	\caption{ \small Traditional: \cite{zfs2003} }
				\end{figure}
			\end{column}
			\begin{column}{0.4\textwidth}
				\begin{figure}
					\centering
					\includegraphics[height=0.7\textheight]{assets/layers/zfs}
				%	\caption{ \small ZFS: \cite{zfs2003} }
				\end{figure}
			\end{column}
		\end{columns}
\end{frame}

\subsubsection{ZFS}
\begin{frame}[label=overview_zfs_stack]{ZFS Layers}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\pause
			\begin{itemize}
				\onslide+<4->
				\item ZFS Posix Layer
				\begin{itemize}
					\item File Systems
				\end{itemize}
				\onslide+<3->
				\item Data Management Unit
					\begin{itemize}
						\item Transactions
						\item Flat Objects
					\end{itemize}
				\onslide+<2->
				\item Storage Pool Allocator
				\begin{itemize}
					\item \small DVA Abstraction % Later
					\item \small Disk Redundancy
					\item \small IO Orchestration
				\end{itemize}
			\end{itemize}
		\end{column}
			\onslide+<0->
			\begin{column}{0.4\textwidth}
				\begin{figure}
					\centering
					\includegraphics[height=0.7\textheight]{assets/layers/zfs_differences}
				\end{figure}
			\end{column}
	\end{columns}
\end{frame}

% Start explaining ZFS implementation by walking up the low-level ZFS layers
\subsection{Basic Concepts}
\begin{frame}{ZFS Basic Concepts}
	\begin{center}
		\Huge ZFS Basic Concepts
	\end{center}
\end{frame}

\begin{frame}<6->[label=impl_tech_overview]
	\frametitle{ZFS Basic Concepts}
	{\Large Key Techniques}\\
	\begin{itemize}
		\item \alert<2>{Block-Pointers}
		\item \alert<3>{Tree-Structure}
		\item \alert<4>{Block-Level Checksumming}
		\item \alert<5>{Copy-on-Write}
	\end{itemize}
\end{frame}

\againframe<2>{impl_tech_overview}
\subsubsection{Block-Pointers}
\begin{frame}{Block-Pointers}
	\begin{figure}
	\centering
	\includegraphics[height=0.75\textheight]{assets/contrib/mckusick/block_pointer}
	\caption{ZFS Block Pointer. Source \cite{introimplzfs}}
	\end{figure}
\end{frame}

\againframe<3>{impl_tech_overview}
\subsubsection{Tree Structure}
\begin{frame}{Tree Structure}
	\begin{figure}
	\centering
	\includegraphics[width=0.6\linewidth]{assets/contrib/zfs2003/tree_structure}
	\caption{Tree Structure. Source \cite{zfs2003}}
	\end{figure}
\end{frame}

\againframe<4>{impl_tech_overview}
\subsubsection{Block-Level Checksumming}
\begin{frame}{Block-Level Checksumming}
	\begin{figure}
		\centering
		\includegraphics[height=0.75\textheight]{assets/contrib/mckusick/block_pointer_checksum_highlighted}
		\caption{ZFS Block Pointer. Source \cite{introimplzfs}}
	\end{figure}
\end{frame}

\againframe<5>{impl_tech_overview}
\subsubsection{Copy-on-Write}
\begin{frame}{Copy-on-Write}
\begin{columns}
	\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item<2-> Modify Data Block \\ $\implies$ Write Copy
				\item<3-> Checksum Changes
				\item<4-> Modify $1^{st}$ level indirect block \\ $\implies$ Write Copy
				\item<5-> Ripple, ripple, ripple...
				\item<6-> Overwrite \alert{Überblock} in-place$^*$
			\end{itemize}
	\end{column}
	\begin{column}{0.6\textwidth}
		\begin{figure}
		\centering
		\only<1>{\includegraphics[width=\linewidth]{assets/contrib/zfs2003/cow/begin}}
		\only<2-3>{\includegraphics[width=\linewidth]{assets/contrib/zfs2003/cow/data_block}}
		\only<4>{\includegraphics[width=\linewidth]{assets/contrib/zfs2003/cow/first_indirect}}
		\only<5>{\includegraphics[width=\linewidth]{assets/contrib/zfs2003/cow/second_indirect}}
		\only<6>{\includegraphics[width=\linewidth]{assets/contrib/zfs2003/cow/uberblock}}
		\caption{ZFS Copy-on-Write. Source \cite{zfs2003}}
	\end{figure}
	\end{column}
\end{columns}
\end{frame}

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

% This is a crippling analogy to legacy filesystems
% Let's look at a more complete picture
\subsection{ZFS Modules}
\begin{frame}{ZFS Modules}
	\begin{center}
		\Huge ZFS Modules
	\end{center}
\end{frame}

\begin{frame}[label=zfs_module_layering]{ZFS Modules}
	\begin{figure}
		\centering
		\includegraphics[height=0.85\textheight]{assets/zfs_modules}
	%	\caption{ \small ZFS module layering. Source \cite{difbsd2nd} }
	\end{figure}
\end{frame}

% We walk bottom up, exploring the functionality each module provides

\subsubsection{VDEVs}
\begin{frame}[fragile]{VDEVs}
	\begin{columns}
		\begin{column}{0.5\linewidth}
				\begin{itemize}
					\item SPA \emph{stripes} root VDEVs
					\item VDEVs implement
					\begin{itemize}
						\item Access to Physical Storage
						\item Disk Redundancy
					\end{itemize}
					\item Building-block approach
					\item Nesting
				\end{itemize}
		\end{column}
		\begin{column}{0.5\linewidth}
			\visible<2->{
				\begin{figure}
				\centering
				\includegraphics[height=0.3\textheight]{assets/zpool_vdev_nesting_own}
				\caption{Nested VDEVs.}
				\end{figure}
			}
		\end{column}
	\end{columns}
	\vspace{20pt}
% Need to keep this to the left or alternatively use spaces
\begin{columns}<3->
\begin{column}{0.4\textwidth}
\centering
\begin{varwidth}{0.4\linewidth}
\begin{semiverbatim}
vdev_\alert{disk}.c
vdev_\alert{geom}.c
vdev_\alert{file}.c
vdev_\alert{cache}.c
vdev_label.c
\end{semiverbatim}
\end{varwidth}
\end{column}
\begin{column}{0.4\textwidth}
\centering
\begin{varwidth}{0.4\linewidth}
\begin{semiverbatim}
vdev_\alert{mirror}.c
vdev_\alert{raidz}.c
vdev_missing.c
vdev_queue.c
vdev_root.c
\end{semiverbatim}
\end{varwidth}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{VDEVs: Disk Redundancy}
\begin{itemize}
	\item Mirroring
	\item RAIDZ-1 $\approx$ RAID-(3|5)ish with logical blocks
	\item RAIDZ-2, RAIDZ-3
	\item Checksumming \\
	$\implies$ Protect Against RAID-5 \emph{Write-Hole}
	\item Fast \emph{resilvering} on moderately filled pools % because can walk tree and only copy indirect blocks (like logical backups, not a dump)
\end{itemize}
\end{frame}

\subsubsection{Storage Pool Allocator (SPA)}
\begin{frame}{Storage Pool Allocator (SPA)}
	Implements \vspace{10pt}
	\begin{itemize}
		\item Checksumming
		\item Compression
		\item Block-level Deduplication
		\item Disk Redundancy (VDEVs)
		\item ZIO: IO Orchestration \& Prioritization %fsyncs need to get to intent-log quickly, while asynchronous txg_groups are lower prio.
	\end{itemize}
	\vspace{10pt}
	Exposes DVA interface $\approx$ \texttt{malloc}(3) \texttt{free}(3)
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{Data Management Unit (DMU)}
\begin{frame}[fragile,allowframebreaks]{Data Management Unit (DMU)}
	\begin{itemize}
	\item Objects with file-like interface \\ \texttt{(objectid, offset)}
	\item Private Namespace (object set / \emph{dataset}) \\ \texttt{(\alert{object set}, objectid, offset)}
	\item Create / Read / Write / Delete objects in Transactions
	\end{itemize}
\pagebreak
\small
\vspace{-2em}
\begin{minted}{c}
/*
 * You must create a transaction, then hold the objects
 * which you will (or might) modify as part of this
 * transaction. Then you must assign the transaction
 * to a transaction group. Once the transaction has
 * been assigned, you can modify buffers which belong to
 * held objects as part of this transaction. [...]
 */
dmu_tx_t *dmu_tx_create(objset_t *os);
void dmu_tx_commit(dmu_tx_t *tx);
void dmu_tx_abort(dmu_tx_t *tx);

void dmu_write(objset_t *os, uint64_t object, uint64_t offset,
               uint64_t size, const void *buf, dmu_tx_t *tx);

void dmu_prealloc(objset_t *os, uint64_t object,
                  uint64_t offset, uint64_t size, dmu_tx_t *tx);
\end{minted}
\centering
\tiny \hfill Lines from \cite{openzfssrc_dmu}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{Dataset- \& Snapshot Layer (DSL)}
\begin{frame}[allowframebreaks]{Dataset- \& Snapshot Layer (DSL) + Meta-Object Set}
	DMU used for different purposes \vspace{10pt}
	\begin{itemize}
		\item POSIX filesystems (ZPL) % with POSIX semantics
		\item ZVOLs (DMU-backed block device)
		\item Snapshots (consistent state of FS / ZVOL)
		\item Clones (rw filesystem starting off snapshot)
		\item \texttt{\$APP} (maybe, someday)
	\end{itemize}  \vspace{10pt}
	$\implies$ Need container for object sets $\implies$ \alert{meta-object set}
	\pagebreak
	\begin{figure}
	\centering
	\includegraphics[height=0.75\textheight]{assets/contrib/mckusick/detailed_with_dsl_structures}
	\caption{On-Disk Structures, including MOS. Source \cite{introimplzfs}}
	\end{figure}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{Adaptive Replacement Cache (ARC) \& L2ARC}
\begin{frame}{Adaptive Replacement Cache (ARC) \& L2ARC}
\begin{itemize}
	% This is why ZFS is performant (at all)
	\item Adaptive Replacement Cache
	\begin{itemize}
		\item Physically Indexed (SPA-)Block-level Cache % Physical = ZFS-Block-Level, i.e. the blocks pointed to by block pointers => Physical saves resources because block is shared between live filesystem and its snapshots & clones, etc.
		\item Scan-resistant LRU eviction strategy % Based on an algorithm from IBM research. Uses combination of MRU and MFU + tracking of eviction + adjustment of MRU/MFU size in response to eviction tracking
		\item Separate from system page cache % result of ZFS's monolithic design. Easier portability, but things like mmap & sendfile waste memory
		\item Will eat up all$^*$ your memory
	\end{itemize}
	\item L2ARC = Level 2 ARC % expand the ARC to secondary storage, e.g. a fast SSD in a HDD-only pool
\end{itemize}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{ZFS POSIX Layer (ZPL)}
\begin{frame}{ZFS POSIX Layer (ZPL)}
	\begin{itemize}
		\item File Systems with POSIX Semantics
		\pause
		\begin{itemize}
			\item Directories
			\item Files
			\item Permissions
			\item ACLs
			\item xattr
			\item ...
		\end{itemize}
		\pause
		\item $\implies$ Leverage DMU + ZAP + ZIL
	\end{itemize}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{ZFS Attribute Processor (ZAP)}
\begin{frame}{ZFS Attribute Processor (ZAP)}
	\begin{itemize}
		\item $\approx$ Key-Value Data Store / dictionary$^*$ % Can have nested structures
		\item Store metadata
		\begin{itemize}
			\item File Attributes (ZPL)
			\item Directories (ZPL)
			\item Dataset Attributes (DSL)
			\item Pool Attributes
			\item ...
		\end{itemize}
	\end{itemize}
\end{frame}

\subsubsection{ZFS Intent Log (ZIL)}
\begin{frame}{ZFS Intent Log (ZIL)}
\begin{itemize}
	\item $\approx$ Journaling for ZPL \& ZVOLs
	\item POSIX Atomic Transactions without DMU checkpoint %remember: DMU cares about on-disk consistency. Does this with checkpoints (transaction groups) that group transactions. Checkpoints are not written frequently enough to use them for fsync(3).
	\item Can designate specific VDEV %mitigate write performance bootleneck / increase write IOPs
\end{itemize}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{ZFS Volume (ZVOL)}
\begin{frame}{ZFS Volume (ZVOL)}
	\begin{itemize}
		\item DMU backed block storage
		\item Export via iSCSI
		\item Local \& Remote VM Storage %With all the goodness of the lower layers
	\end{itemize}
\end{frame}

\againframe{zfs_module_layering}
\subsubsection{/dev/zfs}
\begin{frame}{/dev/zfs}
	\begin{itemize}
		\item \texttt{zpool}(8) \& \texttt{zfs}(8)
		\item \texttt{ioctl}(2) to \texttt{/dev/zfs}
		\item Configure VDEVs
		\item Send \& Receive Snapshot Streams % As introduced earlier: very fast & convenient dataset replication
	\end{itemize}
\end{frame}

\againframe{zfs_module_layering}

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

\subsection{Example}
\begin{frame}{ZFS Modules - Example}
	\begin{center}
		\Huge Example
	\end{center}
\end{frame}

\begin{frame}{\texttt{write}(3)}
\begin{figure}
	\centering
	\includegraphics[height=0.7\textheight]{assets/zfs_modules}
\end{figure}
\end{frame}

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

ext: tex


text:
\chapter{Recognition Software - Screenshots}

\section{Suspect Database}
\begin{center}
\includegraphics[scale=0.5]{screenshots-small/gui1.jpg}
\end{center}

\section{Suspect Matching}
\begin{center}
\includegraphics[scale=0.5]{screenshots-small/gui2.jpg}
\end{center}

\section{Understanding the Hopfield Model}
\begin{center}
\includegraphics[scale=0.5]{screenshots-small/gui3.jpg}
\end{center}

max_stars_repo_name: imperialhopfield/hopfield

max_issues_repo_name: imperialhopfield/hopfield

max_forks_repo_name: imperialhopfield/hopfield


text:
\section*{Conclusion \& Future Work}
In conclusion the project team can be proud of the results of the project. Although we were held up by many data collection and data quality issues we managed to experimentally construct a pipeline from collection tweets to time series of tweet indicators and price data collected online to cleaned an interpolated time series. The neural networks and incorporation of additional data sources did not deliver the predictive power hoped for yet once trained provide very accurate day-to-day predictions without having to be retrained. Due to the many issues we encountered with collecting, setting up the infrastructure and analyzing tweets we were not able to collect enough to data to evaluate the use of twitter indicators. However, since we have successfully set up the infrastructure and filtering of tweets we are positive that this can be done in a follow-up project.\\
In order to refine the prediction models used and to complete the pipeline it might be a good idea to reapply this approach to the \href{http://www.kemendag.go.id/en/economic-profile/prices/national-price-table}{Indonesian national price table} that has recently been published by the Indonesian Ministry of Trade. Twitter statistics very much favor Indonesia with 11.7\% of the population using twitter over India where the percentage only amounts to 1.3\%.\\
Taking the idea of twitter indicators further our map visualization shows that the volume of tweets in India has massively increased in the last few years. By continuing the collection of tweets from India the tweet indicators could be bolstered and compared to price time series. If significant relationships are found the tweet indicators could be used to support real-time prediction of prices when prices monitored by the government are not yet available.\\
Another interesting point would be to take the analysis of the social media content further in order to figure if it is possible to track the patterns of food supply in throughout the country. Such a system could help the highly decentralized Indian government in managing the allocation of resources including food market interventions.

\section*{Closing remarks}
The whole project team would like to sincerely thank Professor Christoph Koch for giving us the possibility to propose this project and implement it despite the uncertainty of its outcome. We would further like to thank our TA Aleksandar Vitorovic for his valuable criticism, advice and motivation.


text:
\section{Appendix}
\label{sec:appendix}

\subsection{Functor}
\label{sec:functor}

Functor is a type class for types, which can be mapped over. Another way to describe functors is that they represent some sort of computational context \cite{yorgey}. Listing \ref{lst:functortypeclass} shows the declaration of the \verb|Functor| type class.
\begin{lstlisting}[caption={Declaration of {\ttfamily Functor} type class},label={lst:functortypeclass}]
class Functor f where
  fmap :: (a -> b) -> f a -> f b
\end{lstlisting}

The \verb|f| in the declaration is a type class constructor. Only type constructors can implement \verb|Functor| (e.g. \verb|Maybe|, \verb|[]|).

\verb|fmap| takes any function \verb|a -> b| and a value of type \verb|f a| (\verb|f| is the container or context, \verb|a| is the type wrapped inside the functor) and returns a value of type \verb|f b|.
If \verb|f a| is of type \verb|Maybe| \verb|Int| and the function of type \verb|Int -> String|, \verb|fmap| returns \verb|Maybe String|.

Examples of \verb|Functor| instances are:

\begin{description}
\item[List] \verb|fmap| applies the function to every element in the list.
\item[Either] \verb|Either e a| is a container. \verb|fmap| applies a function to \verb|a|.
\end{description}

To make a type an instance of \verb|Functor|, it has to define \verb|fmap|. In addition, the instances are expected to obey certain properties. The declaration of the type class doesn't reveal these properties. They are described in the type class documentation \cite{data.functor} \cite{Marlow_2010}. These properties are called the functor laws. All Functor instances in the standard library obey these laws \cite{yorgey} \cite{Lipovaca}.

A \verb|Functor| instance has to satisfy the following laws.

\begin{description}
\item[Law 1] Mapping the identity function over a \verb|Functor| value, will not change the functor value. Formally
\begin{verbatim}
fmap id = id
\end{verbatim}
\item[Law 2] It doesn't matter if we compose two functions and then map them over a functor or if we first map one function over the functor and then map the other function. Formally
\begin{verbatim}
fmap (g . h) = fmap g . fmap h
\end{verbatim}
This is the same as \verb|fmap (g . h) = fmap g (fmap h)|
\end{description}

If we can prove that a type satisfies these laws, we can make assumptions about how the the type will act. We know that \verb|fmap| will not change the structure or the context of the functor.
And we know that \verb|fmap| only maps the function over the functor and nothing else.

\subsection{Applicative Functor}
\label{sec:applicatives}

Applicative functors are abstract characterizations of an applicative style of effectful programming \cite{mcbride} \cite{control.applicative}

The \verb|Applicative| type class encapsulates the following idea. What if we have a function wrapped in a \verb|Functor| (e.g. \verb|Maybe (Int -> Int -> Int)|) and you want to apply the function to another functor (e.g. \verb|Maybe Int|). For example, we want to map \verb|Just (3 *)|, a function encapsulated inside a functor, over \verb|Just 23|, another functor with an encapsulated \verb|Int|. \verb|fmap| doesn't work here, because it expects a function of type \verb|a -> b| as first parameter. That's where the \verb|Applicative| type class comes in.
The \verb|Applicative| type class is defined in listing \ref{lst:applicativetypeclass} \cite{control.applicative}.
\begin{lstlisting}[caption={Declaration of {\ttfamily Applicative} type class},label={lst:applicativetypeclass}]
class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
\end{lstlisting}

Every type that is part of \verb|Applicative| is part of \verb|Functor|. Hence we can use \verb|fmap| with \verb|Applicative| instances.
\verb|Applicatives| are enhanced functors. In addition to \verb|fmap| we can use the \verb|<*>|-operator to chain several \verb|Applicative| values together.

The \verb|pure| function puts a value of type \verb|a| in a default context. If applied with a function \verb|a -> b|,  \verb|pure| returns a functor with a function inside, \verb|f (a -> b)|, hence the first argument of \verb|<*>|.

There are several laws that instances of the \verb|Applicative| type class should satisfy \cite{mcbride} \cite{control.applicative}. We only need to know the following:

\begin{enumerate}
\item \verb|pure id <*> v = v|
\item \verb|fmap g x = pure g <*> x|
\item \verb|pure f <*> pure x = pure (f x)|
\end{enumerate}

The second law states that applying \verb|fmap| over a function \verb|g| over a functor \verb|x| is the same as putting \verb|g| in a default context and mapping the resulting function over \verb|x|.

The third law states that it does not matter if we put the values \verb|f| and \verb|x| in a default context first and then apply \verb|<*>| or if we call \verb|f| on \verb|x| first and then put them in a default context.

\subsection{Monoid}
\label{sec:monoiddefinition}

The \verb|Monoid| type class contains types with an associative binary operation that has an identity
Monoids are described in more detail in section \ref{sec:monoid}. Listing \ref{lst:monoiddefinition} shows the complete definition.
\begin{lstlisting}[label={lst:monoiddefinition}, caption={Definition of type class monoid}]
class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty
\end{lstlisting}

max_stars_repo_name: Hofmaier/robertson

max_issues_repo_name: Hofmaier/robertson

max_forks_repo_name: Hofmaier/robertson


text:
\section{Paper 10}
\subsection{\emph{"Convolutional Neural Networks for Risso’s Dolphins Identification"}}

\begin{frame}{INTRODUCTION}
    Photo identification is a technique that can be used on marine species in
    order to safeguard the environment and the various existing species. The
    marine species on which this study is based are cetaceans, in particular the
    Risso's dolphin species Grampus Griseus (Fig. \ref{fig:Risso}). In order to
    recognize a dolphin, the scars present on their body and on the dorsal fin are
    used, representing the "fingerprints" useful for identifying them. To
    achieve this, a new network model called NNPool is introduced.
    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.5\linewidth]{images/paper10/Risso.png}
        \centering
        \caption{Risso’s dolphins Grampus Griseus}
        \label{fig:Risso}
    \end{figure}
\end{frame}

\begin{frame}{MATERIAL AND METHODS}
    The following work comes from the evolution of two other previously
    created methods that use two different classification algorithms:
    \emph{RUSBoost} \footfullcite{0907875812} and \emph{RUSPool}\footfullcite[]{0907875814}. Each model, including the one proposed, is
    trained on a specific dataset, each of which represents the update of the
    other. The datasets are as follows:
    \begin{enumerate}
        \item $D_R$: consisting of 433 images, used for training RUSBoost method;
        \item $D_V$: consisting of 300 images, used for training RUSPool method;
        \item $D_{NN}$: consisting of 582 images, used for training NNPool method;
    \end{enumerate}
    Each dataset contains more than one image belonging to the single
    dolphin. Each of them is divided into training sets and test sets of
    labeled images.
\end{frame}

\begin{frame}{MATERIAL AND METHODS - RUSBoost}
    \begin{minipage}{\linewidth}
        \centering
        \begin{minipage}{0.47\linewidth}
            RUSBoost consists of two other types of algorithms: Random Under-Sampling
            (RUS) and Adaboost. RUSBoost training takes place by carrying out
            cross-validation, one against all, on each of the 23 dolphins taken into consideration.
            \begin{enumerate}
                \item \emph{Pre-processing}: creation of the black and white image containing the
                extracted fin.
                \item \emph{Features Extraction}: build the 3-dimensional super-SIFT descriptor.
                \item \emph{Classification}: application of the RUSBoost algorithm.
            \end{enumerate}
        \end{minipage}
        \hspace{0.05\linewidth}
        \begin{minipage}{0.45\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width =\linewidth]{images/paper10/RUSBoost model.png}
                \centering
            \end{figure}
        \end{minipage}
    \end{minipage}
\end{frame}

\begin{frame}{MATERIAL AND METHODS - RUSPool}
    The RUSPool algorithm aims to identify known dolphins among all and unknown
    ones. This task is done by using the previous 23 already trained
    RUSBoosts classifiers. Therefore, each image given as input to RUSPool
    will have n super-SIFT descriptors associated with it and this new sample is
    supplied as input to the RUSBoosts classifiers. The result returned by each
    classifier will represent the prediction that a dolphin has been recognized or
    not.In the output vector $R$, if there is an $r_i$ greater than a certain threshold, then the dolphin will be classified as known.
    \begin{minipage}{\linewidth}
        \centering
        \begin{minipage}{0.47\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width =\linewidth]{images/paper10/RUSPool Architecture.png}
                \centering
            \end{figure}
        \end{minipage}
        \hspace{0.05\linewidth}
        \begin{minipage}{0.45\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width = 0.5\linewidth]{images/paper10/ri.png}
                \centering
            \end{figure}
        \end{minipage}
    \end{minipage}

\end{frame}

\begin{frame}{MATERIAL AND METHODS - NNPool}
    The proposed network architecture consists of 28 CNN networks, each of which is trained in recognizing a specific dolphin. If there is a single probability $p_i\in P > 51\%$ in the output vector $P$, then this input dolphin will be classified as known. Each song on the CNN network has the following architecture:
    \begin{minipage}{\linewidth}
        \centering
        \begin{minipage}{0.47\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width = \linewidth]{images/paper10/NNPool Architecture.png}
                \centering
                \caption{CNN Architecture build for each dolphin.}
                \label{fig:CNNDol}
            \end{figure}
        \end{minipage}
        \hspace{0.05\linewidth}
        \begin{minipage}{0.45\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width = 0.5\linewidth]{images/paper10/NNPool output.png}
                \centering
            \end{figure}
        \end{minipage}
    \end{minipage}
\end{frame}

\begin{frame}{EXPERIMENTS AND RESULTS - Metrics}
    The metrics used to evaluate the performance of the proposed model are as follows:
    \begin{enumerate}
        \item \emph{Accuracy}: percentage of correct predictions.
        \item \emph{Sensitivity}: percentage of positive labels considered as positive.
        \item \emph{Specificity}: percentage of negative labels considered as negative.
        \item \emph{PIQE}: determines the type of quality (Excellent, Good, Fair, Poor, Bad) (Low score is better).
    \end{enumerate}
    Images labeled as negative will correspond to unknown classes.
\end{frame}

\begin{frame}{EXPERIMENTS AND RESULTS - RUSPool Vs. NNPool}
    \begin{minipage}{\linewidth}
        \centering
        \begin{minipage}{0.45\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width = \linewidth]{images/paper10/RUSBoost performance.png}
                \centering
                \caption{Performances of every RUSBoost classifiers in RUSPool method.}
                \label{fig: RUSBoostPerf}
            \end{figure}
        \end{minipage}
        \hspace{0.05\linewidth}
        \begin{minipage}{0.45\linewidth}
            \begin{figure}[h!]
                \centering
                \includegraphics[width =\linewidth]{images/paper10/NNPool performance.png}
                \centering
                \caption{Performances of every CNN network in NNPool method.}
                \label{fig: CNNNNPool perfromance}
            \end{figure}
        \end{minipage}
    \end{minipage}
\end{frame}

\begin{frame}{CONCLUSION}
    In conclusion, it can be said that, among all the methods compared, the
    proposed CNN network has better performances and more advantages.
    One of the first is the non-interaction of the user, while following there is
    the factor of the training and classification speed. Even having better
    performance than RUSPool (Tab. \ref{RUSPoolPerf}), NNPool's CNNs networks have the
    problem of the number of images and their quality, in fact by providing a
    low number of images, all with low quality, the proposed algorithm will
    tend to have low performance in terms classification of dolphins. The
    strong point of the CNN network is that it achieves good performance
    both in case there are many low quality images and in case there are few
    high quality images.
    \begin{table}[htbp]
        \centering
        \begin{adjustbox}{width=0.6\textwidth}
        \begin{tabular}{|cccc|}
            \hline
            & Accuracy & Sensitivity & Specificity\\
            \hline
            RUSPool & 0.78 & 0.58 & 0.81\\
            NNPool & 0.87 & 0.70 & 0.90\\
            \hline
        \end{tabular}
        \end{adjustbox}
        \caption{RUSPool and NNPool performance.}
        \label{RUSPoolPerf}
    \end{table}
\end{frame}


text:
\section{Introduction}

\be
\item
Reference to Lua \cite{Lua2011}.

Similar to Tcl/Tk (\cite{Ousterhout2009}), in that the Tcl interpreter
was implemented as a library of C procedures, where applications
built using Tcl could extend the core functionality easily.

\item multi stage programming

Multi-stage programming (MSP) is a variety of metaprogramming in which
compilation is divided into a series of intermediate phases, allowing typesafe
run-time code generation. Statically defined types are used to verify that
dynamically constructed types are valid and do not violate the type system.

Provide forward reference to Operator Polymorphism in
Section~\ref{polymorphism}.

\item

Dealing with null values

\item interpreted versus compiled

{\em  From ``Q for mortals''
  Interpreted Q is interpreted, not compiled. During execution, data and
  functions live in an in-memory workspace. Iterations of the development cycle
  tend to be quick because all run-time information needed to test and debug is
  immediately available in the workspace. Q programs are stored and executed as
  simple text files called scripts. The interpreter's eval and parse routines
  are exposed so that you can dynamically generate code in a controlled manner.

}
\item dyanmic typing

  {\em
  Types Q is a dynamically typed language, in which type checking is mostly
  unobtrusive. Each variable has the type of its currently assigned value and
  type promotion is automatic for most numeric operations. Types are checked on
  operations to homogenous lists.
}

\item in memory

  {\em
  In-Memory Database One can think of kdb+ as an in-memory database with
  persistent backing. Since data manipulation is performed with q, there is no
  separate stored procedure language. In fact, kdb+ comprises serialized q
  column lists written to the file system and then mapped into memory.
}

\item functional language
\ee

max_stars_repo_name: subramon/qlu

max_issues_repo_name: subramon/qlu

max_forks_repo_name: subramon/qlu


text:
%!TEX root = ../main.tex

\chapter{FFTbor2D Appendix}
\label{ch:ffttwoapp}

\lhead{FFTbor\twoD Appendix}

\section{Full recursions for \texorpdfstring{\emZ{i,j}}{}
for the Turner energy model}
\label{sec:ffttwo:turner}

To compute $\emZ{} = \emZ{1,n}$ given input structures \strAB,
we use the recursions

\begin{align}
\label{eq:ffttwoapp:zx}
\emZ{i,j} = \emZ{i,j-1} \cdot x^{\ab{0}} +
\sum_{\mathclap{\substack{(s_k,s_j) \in \bpSet, \\ i \leq k < j}}}\enspace
\Big( \emZ{i,k-1} \cdot \emZB{k,j} \cdot \boltzE{E_d} \cdot
x^{\ab{1}} \Big),
\end{align}

where
$\alpha_0 = 1$ if $j$ is base paired in $\strA_{[i,j]}$ and $0$ otherwise,
$\beta_0 = 1$ if $j$ is base paired in $\strB_{[i,j]}$ and $0$ otherwise,
$\alpha_1 = \dBP{\strA_{[i,j]}}{\strA_{[i,k-1]} \cup \strA_{[k,j]}}$,
$\beta_1 = \dBP{\strB_{[i,j]}}{\strB_{[i,k-1]} \cup \strB_{[k,j]}}$,
and $E_d$ is the energy contribution due to dangling ends (energy
contributions from single bases stacking on adjacent base pairs) and
closing AU base pairs (since a non GC base pair closing a stem has a
destabilizing effect).  The sum is taken over all possible
base pairs $(k,j)$ with $i \leq k < j$.

We compute \emZB{} using the recursion

\begin{align}
\label{eq:ffttwoapp:zbx}
\begin{split}
\emZB{i,j} &= \boltzE{EH(i,j)} \cdot x^{\ab{2}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_l) \in \bpSet, \\ i < k < l < j }}}\enspace
\emZB{k,l} \cdot \boltzE{EI(i,j,k,l)} \cdot x^{\ab{3}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_l) \in \bpSet, \\ i < k < l < j }}}\enspace
\Big( \emZM{i+1,k-1} \cdot \emZB{k,l} \cdot \boltzE{(a+b+c(j-l-1))}
\cdot x^{\ab{4}} \Big)
\end{split}
\end{align}

where
$EH(i,j)$ is the energy of the hairpin loop with closing base pair $(i,j)$,
$\alpha_2 = \dBP{\strA_{[i,j]}}{\{(i,j)\}}$,
$\beta_2 = \dBP{\strB_{[i,j]}}{\{(i,j)\}}$,
$EI(i,j,k,l)$ is the energy of the stack, bulge or
interior loop with the closing base pair $(i,j)$ and the interior
base pair $(k,l)$,
$\alpha_3 = \dBP{\strA_{[i,j]}}{\strA_{[k,l]} \cup \{(i,j)\}}$,
$\beta_3 = \dBP{\strB_{[i,j]}}{\strB_{[k,l]} \cup \{(i,j)\}}$,
$\alpha_4 = \dBP{\strA_{[i,j]}}{\strA_{[i+1,k-1]} \cup
\strA_{[k,l]} \cup\{(i,j)\}}$, and
$\beta_4 = \dBP{\strB_{[i,j]}}{\strB_{[i+1,k-1]} \cup
\strB_{[k,l]} \cup\{(i,j)\}}$.
The first term in the
recursion takes care of the case where $(i,j)$ is the only base pair
in $[i,j]$, i.e. $(i,j)$ closes a hairpin loop. The second term
handles the case where there is an interior loop (or a bulge or a
stack) closed by $(i,j)$ and $(k,l)$. The third term takes care of
all the structures where $(i,j)$ closes a multiloop. To reduce
complexity of the algorithm, the interior and bulge loop size can be
limited to a maximum size of $L$ (taken by default to be $30$),
by requiring that $l>j-L$ in the above recursion.

The final recursion, for computing \emZM{}, is

\begin{align}
\label{eq:ffttwoapp:zmx}
\begin{split}
\emZM{i,j} &= \emZM{i,j-1} \cdot \boltzE{c} \cdot x^{\ab{0}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_j) \in \bpSet, \\ i \leq k < j }}}\enspace
\Big( \emZB{k,j} \cdot \boltzE{(b+c(k-i))} \cdot x^{\ab{5}} \\
&+ \emZM{i,k-1} \cdot \emZB{k,j} \cdot \boltzE{b} \cdot x^{\ab{6}} \Big)
\end{split}
\end{align}

where
$\alpha_5 = \dBP{\strA_{[i,j]}}{\strA_{[k,j]}}$,
$\beta_5 = \dBP{\strB_{[i,j]}}{\strB_{[k,j]}}$,
$\alpha_6 =\dBP{\strA_{[i,j]}}{\strA_{[i,k-1]} \cup \strA_{[k,j]}}$, and
$\beta_6 =\dBP{\strB_{[i,j]}}{\strB_{[i,k-1]} \cup \strB_{[k,j]}}$.
Note that since $\emZM{i,j}$ computes the partition function
contribution under the assumption that $[i,j]$ is part of a
multiloop, there will be exactly one stem-loop structure in this
region (the \emZB{} term) or
more than one (the \emZM{}--\emZB{} term).
Justification of recursions (\ref{eq:ffttwoapp:zx}),
(\ref{eq:ffttwoapp:zbx}), and
(\ref{eq:ffttwoapp:zmx})
follow by induction, as in the proof of Theorem \ref{thm:ffttwo:recursions}.

\section{Proof for Theorem \ref{thm:ffttwo:recursions}}
\label{sec:ffttwo:recursions}

\begin{proof}
Recall that if $F$ is an arbitrary
polynomial [resp. analytic] function, then $[x^{rn+s}]F(x)$
denotes the coefficient of monomial $x^{rn+s}$ in the
Taylor expansion of $F(x)$. For instance, in
\eqnref{ffttwo:pOfX}, $[x^{rn+s}]p(x) = p_{rn+s}$, and in
\eqnref{ffttwo:zOfX}, $[x^{rn+s}]\fullZx = z_{rn+s}$.

By definition, it is clear that $\emZ{i,j}=1$ if $i \leq j \leq i + \theta$,
where we recall that $\theta = 3$ is the minimum number of unpaired bases in
a hairpin loop. For $j > i + \theta$, we have

\begin{align}
\begin{split}
[x^{rn+s}] \emZ{i,j} &= z_{rn+s}(i,j) = \bfZ{rn+s}{i,j} \\
&= \bfZ{(r-\alpha_0)n+(s-\beta_0)}{i,j-1} \\
&+
\sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j}
\cdot \bfZ{u_0 n+v_0}{i,k-1} \cdot \bfZ{u_1 n+v_1}{k+1,j-1} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j} \right. \\
&\left. \cdot \left( [x^{u_0 n+v_0}] \emZ{i,k-1} \right) \cdot
\left( [x^{u_1 n+v_1}] \emZ{k+1,j-1} \right)
\vphantom{\boltzNuss{k,j}} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j} \right. \\
&\left. \cdot [x^{(u_0+u_1)n+(v_0+v_1)}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1} \right)
\vphantom{\boltzNuss{k,j}} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot [x^{(r-\alpha(k))n+(s-\beta(k))}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1}
\right) \right) \\
&= [x^{rn+s}] \left( \emZ{i,j-1} \cdot x^{\ab{0}} \right) \\
&+ \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot [x^{rn+s}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1} \cdot
x^{\alpha(k)n+\beta(k)} \right) \right) \\
&= [x^{rn+s}] \left( \vphantom{\sum_{k=i}^{j-1}} \emZ{i,j-1} \cdot x^{\ab{0}} \right. \\
&\left. + \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot \emZ{i,k-1} \cdot \emZ{k+1,j-1} \cdot
x^{\alpha(k)n+\beta(k)} \right) \right) \\
\end{split}
\end{align}
\end{proof}

\section{Proof for Lemma \ref{lem:ffttwo:lemma3}}
\label{sec:ffttwo:lemma3proof}

\begin{proof}
The lemma states that if the \bpd $d_0$ between reference
structures \strAB is even, then $\emZof{}{-\alpha}=\emZof{}{\alpha}$, while if
the distance is odd, then $\emZof{}{-\alpha}=-\emZof{}{\alpha}$.
Suppose first that $d_0$ is even. By Lemma \ref{lem:ffttwo:lemma1},
$\emZ{} = z_0 + z_2 x^2 + z_4 x^4 + \dots +
z_{M-2} x^{M-2)}$, and so $\emZof{}{-\alpha}=\emZof{}{\alpha}$.
Suppose now that
$d_0$ is odd. By Lemma \ref{lem:ffttwo:lemma1},
$Z(x) = z_1 x^1 + z_3 x^3 + z^5 x^5 \dots +
z_{M-1} x^{M-1}$, and so $\emZof{}{-\alpha}=-\emZof{}{\alpha}$.
\end{proof}

\section{Proof for Lemma \ref{lem:ffttwo:lemma4}}
\label{sec:ffttwo:lemma4proof}

\begin{proof}
Recall Euler's formula in complex analysis:
$\exp(ix) = \cos(x) + i \sin(x)$. As well, recall that
$\sin(\pi)=0$, $\cos(\pi)=-1$, and the trigonometric
addition formulas:

\begin{align}
\begin{split}
\cos(\alpha-\beta) &= \cos(\alpha) \cos(\beta) + \sin(\alpha) \sin(\beta) \\
\sin(\alpha-\beta) &= \sin(\alpha) \cos(\beta) - \sin(\beta) \cos(\alpha).
\end{split}
\end{align}

Then we have

\begin{align}
\begin{split}
\nu^{M_0-k} &= \exp\left(\frac{2 \pi i (M_0-k)}{M}\right) \\
&= \cos\left(\frac{2 \pi (M_0-k)}{M}\right) + i
\sin\left(\frac{2 \pi (M_0-k)}{M}\right) \\
&= \cos\left(\pi - \frac{2 \pi k}{M}\right) + i
\sin\left(\pi - \frac{2 \pi k}{M}\right) \\
&=
\left[
\cos(\pi) \cos\left(\frac{2 \pi k}{M}\right) +
\sin(\pi) \sin\left(\frac{2 \pi k}{M}\right)
\right] \\
&+
i \left[
\sin(\pi) \cos\left(\frac{2 \pi k}{M}\right) -
\sin\left(\frac{2 \pi k}{M}\right) \cos(\pi)
\right] \\
&=
-\cos\left(\frac{2 \pi k}{M}\right) + i
\sin\left(\frac{2 \pi k}{M}\right) \\
&=
-1 \left[ \cos\left(\frac{2 \pi k}{M}\right) - i
\sin\left(\frac{2 \pi k}{M}\right) \right] \\
&=
-1 \cdot \overline{\cos\left(\frac{2 \pi k}{M}\right) + i
\sin\left(\frac{2 \pi k}{M}\right)}  \\
&=
-1 \cdot \overline{\exp\left(\frac{2 \pi i k}{M}\right)} = - \overline{\nu^k} . \\
\end{split}
\end{align}

It follows that
$\nu^{M_0-k} = -\overline{\nu^k}$, so
$\nu^{k} = \overline{- \nu^{(M_0-k)}} = -\overline{\nu^{(M_0-k)}}$.

This completes the proof of the lemma.
\end{proof}

max_stars_repo_name: evansenter/thesis

max_issues_repo_name: evansenter/thesis

max_forks_repo_name: evansenter/thesis


text:
%%% lorem.tex ---
%%
%% Filename: lorem.tex
%% Description:
%% Author: Ola Leifler
%% Maintainer:
%% Created: Wed Nov 10 09:59:23 2010 (CET)
%% Version: $Id$
%% Version:
%% Last-Updated: Wed Nov 10 09:59:47 2010 (CET)
%%           By: Ola Leifler
%%     Update #: 2
%% URL:
%% Keywords:
%% Compatibility:
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%% Commentary:
%%
%%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%% Change log:
%%
%%
%% RCS $Log$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%% Code:

\chapter{Discussion}
\label{cha:discussion}
This chapter discusses and analyzes the results and methods derived from the previous chapters. Additionally, the work will be put in a wider context.

\section{Results}
\label{sec:discussion-results}
Overall the results look promising, with only some minor variations in perspective and rotation (see examples in \textit{Figure \ref{fig:result final} d)}). The biggest reason for any output variations seems to be deviations when finding the compartment edges, essentially due to the extent of bacteria occurring, as well as their positioning. While \textit{Figure \ref{fig:result final} b)} shows nearly identical results,  \textit{Figure \ref{fig:result final} c)} shows slight variations in the positioning and angle of the identified edges. \\

\noindent Using Canny with the additional blur seems to be a promising way to cope with any noise from bacteria growth. Very accurate final results were possible to produce when slightly adjusting the parameters of Dilate, Erosion, Canny, and Gaussian blur individually for each image. However, parameters were set to work with the whole dataset to provide a more generally applicable solution to the thesis problem. \\

\noindent The fact that the agar plate is circular, and not dependent on the background made it much more difficult to identify its orientation.  Usually, some landmark points in corners, shapes, or the background can be found, but here a color segmentation was needed as an addition to defining the rotation. \\

\noindent \textit{Figure \ref{fig:result final}} in each step shows that the criteria in \textit{Section 1.3} are met. Therefore, the thesis problem description is assumed to be solved. How the implementation fulfills the criteria can be shown in \textit{Figure \ref{fig:result final}} as follows:
 \begin{itemize}
     \item \textit{The outer edge of the agar plate shall be identified. The compartment edges shall be identified as well.}
 \end{itemize}
\textit{Figure \ref{fig:result final} b)} shows that Canny, Morphological Closing, Border Following, and RANSAC were successful in providing an elliptical shape around the outer contour of an agar plate. \textit{Figure \ref{fig:result final} c)} shows that the compartment edges can be identified using Canny, Morphological Closing, Skeletonize, and Hough Transform.
  \begin{itemize}
     \item \textit{Pixels outside the agar plate should be masked to remove background noise.}
 \end{itemize}
 As seen in \textit{Figure \ref{fig:result final} c)}, masking proved to be consistent and any relevant noise is masked if, the outer contour of the agar plate is identified correctly.
 \textit{Figure \ref{fig:result final} c)}.
  \begin{itemize}
     \item \textit{Depending on the angle, position, and scale, the image should be adjusted to match a reference image.}
 \end{itemize}
 \textit{Figure \ref{fig:result final} d)} shows the input image in \textit{Figure \ref{fig:result final} a)} is adjusted in scale, position, perspective, and rotation based on a reference image.

\section{Method}
\label{sec:discussion-method}

The method proved to work, thus leading to good results, but could mainly be improved in some aspects. \\

\noindent For example, additional validation of the Canny output in \textit{Figure \ref{fig:compartment edges flowchart}} could be implemented to validate that the compartment edges are identified, as shown in \textit{Figure \ref{fig:compartment masking} b)}. Either the contrast and brightness could be adjusted as during the validation in \textit{Figure \ref{fig:identify and mask flowchart}}; alternatively the Gaussian blur sigma adjusted depending on the situation. If this were to be successful in all cases, the Closing and Skeletonize would not be needed. Instead, the centermost part of the compartment edges could be simply calculated from the four edges identified. \\

\noindent Even though using RANSAC increased the accuracy of identifying the agar plate, it proved to be relatively computationally expensive. The number of RANSAC iterations was a consequence of using parameters suitable enough for the whole dataset and could be lowered if the pre-processing was optimized. However, processing speed may only be of importance when processing larger data sets. In most cases, only a few images will need to be processed per occasion.\\

\noindent For application areas where processing speed is of the essence, the overall processing speed of larger data sets could be decreased using multi-threading, processing multiple images at once. Additionally, CHT alone could be used to replace the whole \texit{Section 5.1.1.}, still producing good-enough results in cases with little to no perspective distortion.\\

\noindent Instead of processing each output multiple times, any perspective distortion could be directly calculated with the major and minor axis of the circular projection of the agar plate. The major and minor axis should then correspond to the compartment edges and the contour found in \texit{Section 4.1.1}. Ideally, this operation would reduce the need to only a single processing iteration. Alternatively, a validation of the compartment edges positioning could be done. If there still was an offset between the compartment edges of the input and the reference model, the second iteration could be initiated. \\

\noindent Lastly, the manual validation using an overlay reference template could be automated by calculating the Hu Moments. A representation of the outer contour, the compartment edges, and the rotation of each output could be constructed. The representation could then be used as a comparison to the reference template. The moment value of each representation could then be validated based on a percentage with a reasonable margin of error.
\newpage
\section{The work in a wider context}
\label{sec:work-wider-context}
Imagining the social and ethical aspects of image processing is difficult. However, using image processing to pre-process images before being used by a bacteria classifier improves the possibility of correctly identifying the right type of bacteria. Therefore, this work could be a base to improve the input used for all types of automated bacteria classifiers using agar plates. Improving the results of automated bacteria classifiers can not only for mastitis, improve the time-consuming and lengthy diagnosis process. \\
%Öppnar upp portar för bakterie klassifierare
%knytt ihop säcken med det som skrevs i börja av introduktionen

%This work could be a base for all types of bacteria classifications. Improving the input images used by bacteria classifiers

%\item The work could be a base for all type of bacteria classification using agar plates. It is not just limited to mastitis.
%Talk about the ethical and social aspects related to the work. Here write about the social and ethical aspects of mastitis and its contribution to the use of antibiotics? (Maybe??)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% lorem.tex ends here

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "demothesis"
%%% End:

max_stars_repo_name: leijonhufvudp/Thesis-Agricam

max_issues_repo_name: leijonhufvudp/Thesis-Agricam

max_forks_repo_name: leijonhufvudp/Thesis-Agricam


text:
\documentclass[a4paper,12pt,oneside,pdflatex,italian,final,twocolumn]{article}

\usepackage[utf8]{inputenc}
\usepackage{parallel}
\usepackage{siunitx}
\usepackage{booktabs}
\usepackage{fancyhdr}

\usepackage[export]{adjustbox}
\usepackage[margin=0.5in]{geometry}
\addtolength{\topmargin}{0in}

\usepackage{libertine}
\renewcommand*\familydefault{\sfdefault}  %% Only if the base font of the document is to be sans serif
\usepackage[T1]{fontenc}

\title{ TCS3472 }
\author{ Nick Felker }
\date{ 2019 }

\begin{document}

\pagestyle{fancy}

\lhead{ Nick Felker }
\chead { 2019 }
\rhead{ TCS3472 v0.1.0 }

\onecolumn

\begin{figure}
\begin{minipage}{0.47\textwidth}

\section{Overview}
    Color Light-to-Digital Converter with IR Filter
    \begin{itemize}
        \item Device address 41
        \item Address type 7-bit
    \end{itemize}

\end{minipage}
\hfill

\end{figure}

\section{Register Description}
\begin{itemize}
\item Blue channel - Blue light as an int. Divide by ambient light to get scaled number.
\item Clear channel - This is the ambient amount of detected light.
\item Enable - Enable specific components of the peripheral
\item Green channel - Green light as an int. Divide by ambient light to get scaled number.
\item Red channel - Red light as an int. Divide by ambient light to get scaled number.
\end{itemize}

\section{Technical specification}
\centering
\begin{tabular}{lcrr}
\toprule
 & Register Name & Register Address & Register Length \\
\midrule
blue & Blue channel & 186 & 16 \\
clear & Clear channel & 180 & 16 \\
enable & Enable & 128 & 8 \\
green & Green channel & 184 & 16 \\
red & Red channel & 182 & 16 \\
\bottomrule
\end{tabular}

\raggedright

\section{Fields}

\raggedright

\subsection{Register enable}
\centering
\begin{tabular}{lcr}
\toprule
  & Field Name & Bits \\
\midrule
init & Setup the device configuration &
7:0
\\
\bottomrule

\end{tabular}

\raggedright

\subsubsection{Field init }

Enable RGBC and Power

\begin{itemize}
\item Power (1) - Power
\item RGBC (2) - Color
\end{itemize}

\raggedright

\section{Functions}

\centering
\begin{tabular}{lc}
\toprule
  & Description \\
\midrule
_lifecycle & Enables features on device \\
\bottomrule
\end{tabular}

\raggedright
\subsection{Function _lifecycle }
Enables features on device \\

\centering
\begin{tabular}{lcr}
\toprule
  & Inputs & Return \\
\midrule
Begin &
&
void
\\
\bottomrule
\end{tabular}

\raggedright

\end{document}

max_stars_repo_name: polfeliu/cyanobyte

max_issues_repo_name: polfeliu/cyanobyte

max_forks_repo_name: polfeliu/cyanobyte


text:
\section{Introduction}

This module provides an interactive command interface to SUGAR
using the Lua language.  It defines little functionality on its
own.

This module provides a Lua interface to the {\tt{}uses} manager
functionality.

Commands to the interface include
\begin{itemize}
  \item {\tt{}use}:
    Read and execute a Lua script file in the current environment
  \item {\tt{}addpath}: Add to the search path
\end{itemize}

Besides these commands, the basic Lua library and the math library
are included.  All the standard Lua syntax is, of course, available.

\section{Interface}

The module provides three functions: one to register the library
functions with the Lua interpreter, and a setter/getter pair to
access the uses manager associated with the interpreter.

\nwfilename{uses-manager-lua.nw}\nwbegincode{1}\sublabel{NWuseJ-useI-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-useI-1}}}\moddef{uses-manager-lua.h~{\nwtagstyle{}\subpageref{NWuseJ-useI-1}}}\endmoddef
#ifndef USES_MANAGER_LUA_H
#define USES_MANAGER_LUA_H

#include "uses-manager.h"

void lua_usesmgrlib(lua_State* L);
void lua_set_usesmgr(lua_State* L, uses_manager_t uses_mgr);
uses_manager_t lua_get_usesmgr(lua_State* L);

#endif /* USES_MANAGER_LUA_H */
\nwnotused{uses-manager-lua.h}\nwendcode{}\nwbegindocs{2}\nwdocspar

\section{Implementation}

\nwenddocs{}\nwbegincode{3}\sublabel{NWuseJ-useI.2-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-useI.2-1}}}\moddef{uses-manager-lua.c~{\nwtagstyle{}\subpageref{NWuseJ-useI.2-1}}}\endmoddef
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <lua.h>
#include <lualib.h>

#include "uses-manager-lua.h"

\LA{}static functions~{\nwtagstyle{}\subpageref{NWuseJ-staG-1}}\RA{}
\LA{}functions~{\nwtagstyle{}\subpageref{NWuseJ-fun9-1}}\RA{}

\nwnotused{uses-manager-lua.c}\nwendcode{}\nwbegindocs{4}\nwdocspar

\subsection{Accessing the uses manager}

The uses manager is stored in the Lua registry table in the entry
keyed by ``SUGAR uses manager''.

\nwenddocs{}\nwbegincode{5}\sublabel{NWuseJ-fun9-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-fun9-1}}}\moddef{functions~{\nwtagstyle{}\subpageref{NWuseJ-fun9-1}}}\endmoddef
void lua_set_usesmgr(lua_State* L, uses_manager_t uses_mgr)
\{
    lua_getregistry(L);
    lua_pushstring(L, "SUGAR uses manager");
    lua_pushuserdata(L, uses_mgr);
    lua_settable(L,-3);
    lua_pop(L,1);
\}

\nwalsodefined{\\{NWuseJ-fun9-2}\\{NWuseJ-fun9-3}}\nwused{\\{NWuseJ-useI.2-1}}\nwendcode{}\nwbegindocs{6}\nwdocspar

\nwenddocs{}\nwbegincode{7}\sublabel{NWuseJ-fun9-2}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-fun9-2}}}\moddef{functions~{\nwtagstyle{}\subpageref{NWuseJ-fun9-1}}}\plusendmoddef
uses_manager_t lua_get_usesmgr(lua_State* L)
\{
    uses_manager_t uses_mgr;

    lua_getregistry(L);
    lua_pushstring(L, "SUGAR uses manager");
    lua_gettable(L,-2);
    if (!lua_isuserdata(L,-1))
        return NULL;
    uses_mgr = (uses_manager_t) lua_touserdata(L,-1);
    lua_pop(L,2);
    return uses_mgr;
\}

\nwendcode{}\nwbegindocs{8}\nwdocspar

\subsection{{\tt{}use} command}

The {\tt{}use} command executes a Lua file in the current environment.

\nwenddocs{}\nwbegincode{9}\sublabel{NWuseJ-staG-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-staG-1}}}\moddef{static functions~{\nwtagstyle{}\subpageref{NWuseJ-staG-1}}}\endmoddef
static int use_lua_file(lua_State* L)
\{
    uses_manager_t uses_manager = lua_get_usesmgr(L);
    int n = lua_gettop(L);
    int i;

    \LA{}Assert presence of uses manager~{\nwtagstyle{}\subpageref{NWuseJ-AssV-1}}\RA{}

    for (i = 1; i <= n; ++i) \{
        char buf[256];
        if (!lua_isstring(L,i))
            lua_error(L, "Invalid argument to 'use'");
        \LA{}Get complete name of file to use~{\nwtagstyle{}\subpageref{NWuseJ-GetW-1}}\RA{}
        \LA{}Use lua file~{\nwtagstyle{}\subpageref{NWuseJ-UseC-1}}\RA{}
    \}
    return 0;
\}

\nwalsodefined{\\{NWuseJ-staG-2}}\nwused{\\{NWuseJ-useI.2-1}}\nwendcode{}\nwbegindocs{10}\nwdocspar

To get the full file name, including path, we consult
the uses manager.  If we find a full name, we store it in {\tt{}buf};
otherwise, we'd better complain.

\nwenddocs{}\nwbegincode{11}\sublabel{NWuseJ-AssV-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-AssV-1}}}\moddef{Assert presence of uses manager~{\nwtagstyle{}\subpageref{NWuseJ-AssV-1}}}\endmoddef
if (uses_manager == NULL)
    lua_error(L, "Uses manager not installed!\\n");
\nwused{\\{NWuseJ-staG-1}\\{NWuseJ-staG-2}}\nwendcode{}\nwbegindocs{12}\nwdocspar

\nwenddocs{}\nwbegincode{13}\sublabel{NWuseJ-GetW-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-GetW-1}}}\moddef{Get complete name of file to use~{\nwtagstyle{}\subpageref{NWuseJ-GetW-1}}}\endmoddef
strncpy(buf, lua_tostring(L,i), sizeof(buf));
if (uses_manager_search(uses_manager, buf, sizeof(buf)) == NULL)
    lua_error(L, "Could not open file");
\nwused{\\{NWuseJ-staG-1}}\nwendcode{}\nwbegindocs{14}\nwdocspar

\nwenddocs{}\nwbegincode{15}\sublabel{NWuseJ-UseC-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-UseC-1}}}\moddef{Use lua file~{\nwtagstyle{}\subpageref{NWuseJ-UseC-1}}}\endmoddef
if (lua_dofile(L, buf) != 0)
    lua_error(L, "Error opening file");
\nwused{\\{NWuseJ-staG-1}}\nwendcode{}\nwbegindocs{16}\nwdocspar

\nwenddocs{}\nwbegincode{17}\sublabel{NWuseJ-regI-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-regI-1}}}\moddef{register functions~{\nwtagstyle{}\subpageref{NWuseJ-regI-1}}}\endmoddef
lua_register(L, "use", use_lua_file);
\nwalsodefined{\\{NWuseJ-regI-2}}\nwused{\\{NWuseJ-fun9-3}}\nwendcode{}\nwbegindocs{18}\nwdocspar

\subsection{{\tt{}addpath} command}

The {\tt{}addpath} command adds to the list of paths to search in
{\tt{}use} commands.  Calls to the {\tt{}uses{\char95}manager{\char95}addpath} command
prepend to the list of available paths.  Note that you \emph{don't}
want to try to add multiple paths in the same string (separated by
a colon as in shell, say).  You can, however, add multiple paths
in different string arguments in a single call to {\tt{}addpath}

\nwenddocs{}\nwbegincode{19}\sublabel{NWuseJ-staG-2}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-staG-2}}}\moddef{static functions~{\nwtagstyle{}\subpageref{NWuseJ-staG-1}}}\plusendmoddef
static int addpath_lua(lua_State* L)
\{
    uses_manager_t uses_manager = lua_get_usesmgr(L);
    int n = lua_gettop(L);
    int i;

    \LA{}Assert presence of uses manager~{\nwtagstyle{}\subpageref{NWuseJ-AssV-1}}\RA{}

    for (i = 1; i <= n; ++i) \{
        if (!lua_isstring(L,i))
            lua_error(L, "Invalid argument to 'use'");
        uses_manager_addpath(uses_manager, lua_tostring(L,i));
    \}
    return 0;
\}

\nwendcode{}\nwbegindocs{20}\nwdocspar

\nwenddocs{}\nwbegincode{21}\sublabel{NWuseJ-regI-2}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-regI-2}}}\moddef{register functions~{\nwtagstyle{}\subpageref{NWuseJ-regI-1}}}\plusendmoddef
lua_register(L, "addpath", addpath_lua);
\nwendcode{}\nwbegindocs{22}\nwdocspar

\subsection{Registration}

\nwenddocs{}\nwbegincode{23}\sublabel{NWuseJ-fun9-3}\nwmargintag{{\nwtagstyle{}\subpageref{NWuseJ-fun9-3}}}\moddef{functions~{\nwtagstyle{}\subpageref{NWuseJ-fun9-1}}}\plusendmoddef
void lua_usesmgrlib(lua_State* L)
\{
    \LA{}register functions~{\nwtagstyle{}\subpageref{NWuseJ-regI-1}}\RA{}
\}

\nwendcode{}

\nwixlogsorted{c}{{Assert presence of uses manager}{NWuseJ-AssV-1}{\nwixu{NWuseJ-staG-1}\nwixd{NWuseJ-AssV-1}\nwixu{NWuseJ-staG-2}}}%
\nwixlogsorted{c}{{Get complete name of file to use}{NWuseJ-GetW-1}{\nwixu{NWuseJ-staG-1}\nwixd{NWuseJ-GetW-1}}}%
\nwixlogsorted{c}{{Use lua file}{NWuseJ-UseC-1}{\nwixu{NWuseJ-staG-1}\nwixd{NWuseJ-UseC-1}}}%
\nwixlogsorted{c}{{functions}{NWuseJ-fun9-1}{\nwixu{NWuseJ-useI.2-1}\nwixd{NWuseJ-fun9-1}\nwixd{NWuseJ-fun9-2}\nwixd{NWuseJ-fun9-3}}}%
\nwixlogsorted{c}{{register functions}{NWuseJ-regI-1}{\nwixd{NWuseJ-regI-1}\nwixd{NWuseJ-regI-2}\nwixu{NWuseJ-fun9-3}}}%
\nwixlogsorted{c}{{static functions}{NWuseJ-staG-1}{\nwixu{NWuseJ-useI.2-1}\nwixd{NWuseJ-staG-1}\nwixd{NWuseJ-staG-2}}}%
\nwixlogsorted{c}{{uses-manager-lua.c}{NWuseJ-useI.2-1}{\nwixd{NWuseJ-useI.2-1}}}%
\nwixlogsorted{c}{{uses-manager-lua.h}{NWuseJ-useI-1}{\nwixd{NWuseJ-useI-1}}}%
\nwbegindocs{24}\nwdocspar

\nwenddocs{}

max_stars_repo_name: davidgarmire/sugar

max_issues_repo_name: davidgarmire/sugar

max_forks_repo_name: davidgarmire/sugar


text:
\chapter{Results} \label{ch:result} During the training sessions, we have recorded five static gestures in 4 different positions in front of the robot. NAO is equipped with Asus Xtion and set in "Stand" posture. Head pitch of NAO is set to -18 degrees to look at the upper body of the user 1800 mm away from the sensor. First 3 positions of training are recorded at 1800 mm distance from the sensor in z axis and + /- 800 mm in x axis. Last training position is recorded at 2200 mm distance. Therefore, training data is recorded for 80 seconds of each gesture.

In this chapter, we present the results of real time hand gesture recognition for Human-robot interaction based on skeletal points tracking using depth camera. Training data for 5 classes with 11918 samples of 6 dimensional vector are trained with Adaptive Naive Bayes Classifier. Min-Max scaling and Null Rejection with coefficient of 2.0 are enabled. Following sections illustrates the results of end-to-end interaction with robot using five gestures named as Walk, Turn Right, Turn Left, Move Right, Move Left gestures which are represented by the class labels 1,2,3,4,5 respectively.

\section{Gesture-To-Motion Results}
Following sections shows that NAO is looking at the user to detect any possible gestures. When it recognized the gesture, Command module commands the robot to execute the appropriate Gesture-To-Motion task. Additionally, results shows the normalized x, y positions of left and right. It is plotted using 60 input samples of the detected gesture. Finally, Control Center displays the prediction results and detected gesture with x,y,z positions of left and right hand in 3D.

\input{chapter/figures/res-walk}
\input{chapter/figures/res-turn-right}
\input{chapter/figures/res-turn-left}
\input{chapter/figures/res-move-right}
\input{chapter/figures/res-move-left}

\clearpage
\section{Gesture-To-Gesture} Figure \ref{res:gg} shows how human hand gestures are translated to robotic hand gestures. When a gesture is detected, the Command module sets the predefined angles to the shoulder and elbow joints of both the hands of NAO to perform Gesture-To-Gesture translation.

\input{chapter/figures/res-gg}

\section{Evaluation} In this section, we present the experiments carried out to evaluate and validate our system to recognize hand gestures using skeletal points. The goal is to demonstrate the effectiveness of the classifier and to evaluate its potential for real time prediction. In the classification phase, input samples are normalized using Min-Max Scaling and Null Rejection is enabled to detect non-gestures. Therefore, the evaluation demonstrates the prediction accuracy of ANBC with various null rejection coefficient and the comparison it with other supervised learning classifier such as Minimum Distance (MinDist).

\input{chapter/tables/ev-mean-sd}

\subsection{Mean and Standard Deviation} During the training phase, first all the input samples are normalized with the range from 0 to 1 and then GRT computes mean $\mu$ and standard deviation $\sigma$ to create a model for each class. During the prediction phase, it basically computes the maximum a posterior probability of an input vector belonging to any of the trained class. Figure \ref{fg:ev:mean} shows the mean positions of left and right hand for every gesture. Table \ref{tb:ev:mean} and \ref{tb:ev:sd} show mean and standard deviations of the labeled training data of all the five classes.

\input{chapter/figures/ev-all-ges-mean}

\subsection{Classification and Prediction} Our gesture recognition pipeline is trained with 11918 input samples of 6 dimensional vector for 5 classes. Classes are labeled as 1,2,3,4,5 and they represent Walk, Turn Right, Turn Left, Move Right, Move Left gestures respectively. Class label 0 is reserved for non-gesture by GRT. We have carried out experiments to evaluate the classification, prediction and post processing efficiency of our system. Figure \ref{ev:test:prediction} show change is positions of left and hand in Cartesian coordinates while test data is recorded and corresponding prediction for every input sample.

Test dataset is a 10\% of training dataset and it is chosen randomly from class. Test dataset is validated against the remaining training dataset, therefore, Precision, Recall, F-Measure and Confusion Matrix are computed. Table \ref{tb:ev:metrics} and \ref{tb:ev:confusion} show the results of prediction using ANBC with null rejection coefficient 2.0. Figure \ref{ev:test:prediction} shows the plot of normalized distances of x,y,z axes of both hands from the test data and their prediction in real time.

\input{chapter/tables/ev-confusion}

\subsection{Prediction Accuracy Vs Null Rejection Accuracy} \label{sec:ev:accuracy} Classifiers of GRT offers various customization that could produce different results for the same test data. Accuracy of a gesture recognition system does not depend only on th precise predictions of trained gestures, but also differentiating them from unintended hand gestures. GRT allows us to set null rejection coefficient for the classifier. Evaluation results are obtained by computing accuracies of 5 trained gestures using ANBC with varying null rejection coefficient from 0 to 10.

Figure \ref{ev:accuracy:anbc} shows that increase in null rejection coefficient causes an increase in the accuracy of trained gestures, however, causes a decrease in the accuracy of non-gesture. Therefore, it is optimal to use a null rejection coefficient of 2.0 with ANBC.

Figure \ref{ev:accuracy:mindist} shows some interesting results of Minimum Distance classifier with 4 clusters. Figure shows that prediction results are unpredictable as there is increase in null rejection coefficient. However, it produces accuracy above 95\% with null rejection coefficient from 2.0 till 4.0. This shows that MinDist could be a better alternative to ANBC.

\input{chapter/figures/ev-test-all}
\input{chapter/figures/ev-accuracy}


text:
\section{MatrixDecomposition: Simultaneous Linear Equations}
There are many, many routines which are useful for systems of
linear equations.  We only catpure some of the common forms here.

\subsection{Tridiagonal Form}
The tridiagonal for can be solved by a forward pass and a backward pass.
It is therefore worth our while to find ways to get matrixrices into that
form.

\subsection*{householder}
This implementation is taken from Naka91, pg 263.

\subsection*{matrix\_to\_arrays}
This is a convenience function, in case you have the full matrix form
(e.g., from householder) and need to convert to the reduced form.

\subsection*{tridiag}
This one took a while to work out.  I started with
the obvious conditions of A=1x1, 2x2, 3x3.  But by stopping
there, I couldn't see the pattern.  Only when I handworked
the 4x4 case, did the recurrence formula stand out.  The
clearest case in the 3rd row in a 4x4.

We solve each row to this form, where ut2 is known and d2*u3
is (obviously) unknown.
     u2=ut2 - d2*u3

Then proceed with row 3:
     a3*u2 + b3*u3 + c3*u4 = r3

     u3 = (r3-a3*u2-c3*u4)/b3
     u3 = (r3-a3(ut2-d2*u3)-c3*u4)/b3
     u3*(1-a3*d2/b3) = u3*(b3-a3*d3)/b3 = (r3-a3*ut2-
     c3*u4)/b3
Multiply both sides by b3, then divide by the left factor,
which we call den for denominator:
     den = (b3-a3*d3)
     u3 = (r3-a3*ut2-c2*u4)/den
Note that part of this is solvable, and part is not, so
split the pieces:
     u3 = (r3-a3*ut2)/den - c3*u4/den
Resolve as far as possible:
     u3 = ut3 - d3*u4
We are now in the same form that we started from u2, and are
ready to proceed with the next row.  This continues until
the last row, at which time there is no c(n)*u(n+1) term,
and we can solve directly.  At that point, we have a vector
of ut's, but have to subtract out the d(n)*u(n+1) terms.
That means a) we have to save the d terms, and we have to
work backwards from u(n) to u(1).

Actually, we can cheat a bit and use the existing u vector
as the ut vector, since we never need both values at once.
So we load up the u vector going forward, and then subtract
out the d*u terms going backwards.