From 2f6c31c9e9b6d202d8ad491ac97207c3b13b9832 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Sun, 16 Nov 2014 17:02:51 +0100 Subject: [PATCH] Figure sprint --- fig/circ_rule.tex | 40 ++++++++++++++++++++ fig/curve_edge.tex | 68 +++++++++++++++++++++++++++++++++ fig/line_disc.tex | 2 + fig/line_midpoint.tex | 75 ++++++++++++++++++++++++++++++++++++ fig/square_cons.tex | 71 ++++++++++++++++++++++++++++++++++ theory.tex | 88 +++++++++++++++++++++++++++++++++++-------- 6 files changed, 329 insertions(+), 15 deletions(-) create mode 100644 fig/circ_rule.tex create mode 100644 fig/curve_edge.tex create mode 100644 fig/line_midpoint.tex create mode 100644 fig/square_cons.tex diff --git a/fig/circ_rule.tex b/fig/circ_rule.tex new file mode 100644 index 0000000..d1ce2bf --- /dev/null +++ b/fig/circ_rule.tex @@ -0,0 +1,40 @@ +\centering +\begin{tikzpicture}[scale=1.0] + + \node[tiny vertex] (o) at (1, 1) {}; + + %\path[dash] (2, 2) -- (5,2); + %\path[dash] (2, 2) -- (5,5); + %\path[dash] (2, 2) -- (2,5.5); + + \draw (1,1) +(0:1.5cm) arc (0:360:1.5cm); + %\path (2,2) ++(22.5:3cm) node {$\phi_{xy}$}; + + \draw[dash] (1,1) +(45:0cm) -- +(45:2.6cm); + \draw[dash] (1,1) +(63.3:0cm) -- +(63.43:2.6cm); + + \draw (1,1) +(45:1.4cm) -- +(45:1.6cm) +(45:1.9cm) + node[font=\small, fill=white, inner sep=0.5pt] {$\phi_k$}; + \draw (1,1) +(63.43:1.4cm) -- +(63.43:1.6cm) +(67.5:1.9cm) + node[font=\small, fill=white, inner sep=0.5pt] {$\phi_{k+1}$}; + %\path (2,2) ++(67.5:3.8cm) node{$\Delta\phi_{xy}$}; + + \draw (1,1) +(45:2.5cm) arc (45:63.43:2.5cm); + \path (1,1) ++(54.215:3cm) node {$\Delta \phi_k$}; + + \foreach \p in {0,90,180,270} { + \draw (1,1) +(\p:1.4cm) -- +(\p:1.6cm); + \draw (1,1) +(\p+45:1.4cm) -- +(\p+45:1.6cm); + \draw (1,1) +(\p+26.57:1.4cm) -- +(\p+26.57:1.6cm); + \draw (1,1) +(\p+90-26.57:1.4cm) -- +(\p+90-26.57:1.6cm); + } + +\end{tikzpicture} +\caption{ + We showed that the angular difference between subsequent angle + parameters goes to zero. The discretization in the $\phi$ dimension + can be viewed as a rectangle approximation rule of the integral, as + the summand is evaluated in one end of the interval $[\phi_k, + \phi_{k+1}]$. +} +\label{fig:circ_rule} diff --git a/fig/curve_edge.tex b/fig/curve_edge.tex new file mode 100644 index 0000000..0ee8711 --- /dev/null +++ b/fig/curve_edge.tex @@ -0,0 +1,68 @@ +\centering +\begin{tikzpicture}[scale=1.2] + \foreach \x in {0,...,5} { + \foreach \y in {0,...,5} { + \node[tiny vertex] (\x\y) at (\x, \y) {}; + } + } + + \clip (0, 0) rectangle (5, 5); + + \path[nedge=4cm] (0,5) -- (2,4); + \path[nedge=4cm] (0,4) -- (2,3); + \path[nedge=4cm] (0,3) -- (2,2); + \path[nedge=4cm] (0,2) -- (2,1); + \path[nedge=4cm] (0,1) -- (2,0); + + \path[nedge=4cm] (-1,1) -- (1,0); + + \path[nedge=4cm] (1,5) -- (3,4); + \path[nedge=4cm] (1,4) -- (3,3); + \path[nedge=4cm] (1,3) -- (3,2); + \path[nedge=4cm] (1,2) -- (3,1); + \path[nedge=4cm] (1,1) -- (3,0); + + \path[nedge=4cm] (2,5) -- (4,4); + \path[nedge=4cm] (3,5) -- (5,4); + \path[nedge=4cm] (4,5) -- (6,4); + + \draw [cyan, xshift=4cm] plot [smooth, tension=2] coordinates { + (1,1) (2,1) (5,5) (3,3)}; + + %\path[dash] (2, 2) -- (5,2); + %\path[dash] (2, 2) -- (5,5); + %\path[dash] (2, 2) -- (2,5.5); + + %\draw (2,2) +(0:2.5cm) arc (0:45:2.5cm); + %\path (2,2) ++(22.5:3cm) node {$\phi_{xy}$}; + + %\draw (2,2) +(45:3.3cm) arc (45:90:3.3cm); + %\path (2,2) ++(67.5:3.8cm) node{$\Delta\phi_{xy}$}; + + %\node[tiny vertex,draw] (a) at (2, 2) {x}; + %\node[tiny vertex,draw] (b) at (2, 3) {}; + %\node[tiny vertex,draw] (c) at (2, 1) {}; + %\node[tiny vertex,draw] (d) at (3, 2) {}; + %\node[tiny vertex,draw] (e) at (1, 2) {}; + %\node[tiny vertex,draw] (f) at (3, 3) {y}; + %\node[tiny vertex,draw] (g) at (1, 1) {}; + %\node[tiny vertex,draw] (h) at (1, 3) {}; + %\node[tiny vertex,draw] (i) at (3, 1) {}; + + %\path[edge] (a) -- (b); + %\path[edge] (a) -- (c); + %\path[edge] (a) -- (d); + %\path[edge] (a) -- (e); + %\path[edge] (a) -- (f); + %\path[edge] (a) -- (g); + %\path[edge] (a) -- (h); + %\path[edge] (a) -- (i); + + \path (4,1) [edge, <->, anchor=center] -- node[anchor=south + east,yshift=-3.5pt] + {$\Delta \rho$} + ($(5,0)!(4,1)!(3,1)$) ; + +\end{tikzpicture} +\caption{One family of lines having the same $\phi$ parameter.} +\label{fig:curve_edge} diff --git a/fig/line_disc.tex b/fig/line_disc.tex index 27a5d31..ec5b865 100644 --- a/fig/line_disc.tex +++ b/fig/line_disc.tex @@ -15,6 +15,7 @@ \node[tiny vertex,draw] (f) at (3, 3) {}; \node[tiny vertex,draw] (g) at (3, 1) {}; \node[tiny vertex,draw] (h) at (2, 1) {}; + \node[tiny vertex,draw] (i) at (2, 0) {}; \path[edge,-] (a) -- (b); \path[edge,-] (a) -- (c); @@ -23,6 +24,7 @@ \path[edge,-] (a) -- (f); \path[edge,-] (a) -- (g); \path[edge,-] (a) -- (h); + \path[edge,-] (a) -- (i); \path[dash] (1, 2) -- +(35.785:4cm); \path[dash] (1, 2) -- +(54.215:4cm); diff --git a/fig/line_midpoint.tex b/fig/line_midpoint.tex new file mode 100644 index 0000000..6472187 --- /dev/null +++ b/fig/line_midpoint.tex @@ -0,0 +1,75 @@ +\centering +\begin{tikzpicture}[scale=1.3] + \foreach \x in {0,...,3} { + \foreach \y in {0,...,2} { + \node[tiny vertex] (\x\y) at (\x, \y) {}; + } + } + + \begin{scope} + \clip (0, 0) rectangle (3, 2); + + \path[nedge=4cm] (0,5) -- (2,4); + \path[nedge=4cm] (0,4) -- (2,3); + \path[nedge=4cm] (0,3) -- (2,2); + \path[nedge=4cm] (0,2) -- (2,1); + \path[nedge=4cm] (0,1) -- (2,0); + + \path[nedge=4cm] (-1,1) -- (1,0); + + \path[nedge=4cm] (1,5) -- (3,4); + \path[nedge=4cm] (1,4) -- (3,3); + \path[nedge=4cm] (1,3) -- (3,2); + \path[nedge=4cm] (1,2) -- (3,1); + \path[nedge=4cm] (1,1) -- (3,0); + + \path[nedge=4cm] (2,5) -- (4,4); + \path[nedge=4cm] (3,5) -- (5,4); + \path[nedge=4cm] (4,5) -- (6,4); + \end{scope} + + \path[dash] (2.5,1.5) -- (3.5,1); + \path[dash] ($(3.5,0.5)!(2.5,1.5)!(1.5,1.5)$) -- ($(4.5,0.0)!(3.5,1.0)!(2.5,1.0)$); + + \path (3.5,1.0) [edge, <->, anchor=center] -- node[anchor=north + west,yshift=+3.0pt,xshift=+1pt, fill=white, font=\small, inner sep=1pt] + {$\Delta \rho$} + ($(4.5,0.0)!(3.5,1.0)!(2.5,1.0)$) ; + + + %\path[dash] (2, 2) -- (5,2); + %\path[dash] (2, 2) -- (5,5); + %\path[dash] (2, 2) -- (2,5.5); + + %\draw (2,2) +(0:2.5cm) arc (0:45:2.5cm); + %\path (2,2) ++(22.5:3cm) node {$\phi_{xy}$}; + + %\draw (2,2) +(45:3.3cm) arc (45:90:3.3cm); + %\path (2,2) ++(67.5:3.8cm) node{$\Delta\phi_{xy}$}; + + %\node[tiny vertex,draw] (a) at (2, 2) {x}; + %\node[tiny vertex,draw] (b) at (2, 3) {}; + %\node[tiny vertex,draw] (c) at (2, 1) {}; + %\node[tiny vertex,draw] (d) at (3, 2) {}; + %\node[tiny vertex,draw] (e) at (1, 2) {}; + %\node[tiny vertex,draw] (f) at (3, 3) {y}; + %\node[tiny vertex,draw] (g) at (1, 1) {}; + %\node[tiny vertex,draw] (h) at (1, 3) {}; + %\node[tiny vertex,draw] (i) at (3, 1) {}; + + %\path[edge] (a) -- (b); + %\path[edge] (a) -- (c); + %\path[edge] (a) -- (d); + %\path[edge] (a) -- (e); + %\path[edge] (a) -- (f); + %\path[edge] (a) -- (g); + %\path[edge] (a) -- (h); + %\path[edge] (a) -- (i); + +\end{tikzpicture} +\caption{ + The discretization in the $\rho$ dimension can be regarded as a + midpoint rule approximation of the integral, since the difference + $\Delta \rho$ the same for all lines in one line family. +} +\label{fig:line_midpoint} diff --git a/fig/square_cons.tex b/fig/square_cons.tex new file mode 100644 index 0000000..979a867 --- /dev/null +++ b/fig/square_cons.tex @@ -0,0 +1,71 @@ +\centering +\begin{tikzpicture}[scale=0.9] + \foreach \x in {0,...,6} { + \foreach \y in {0,...,6} { + \node[tiny vertex] (\x\y) at (\x, \y) {}; + } + } + \node[tiny vertex,draw] (a) at (3, 3) {}; + \node[tiny vertex,draw] (b) at (3, 4) {}; + \node[tiny vertex,draw] (c) at (4, 3) {}; + \node[tiny vertex,draw] (d) at (4, 4) {}; + \node[tiny vertex,draw] (e) at (4, 5) {}; + \node[tiny vertex,draw] (f) at (5, 4) {}; + \node[tiny vertex,draw] (g) at (5, 2) {}; + \node[tiny vertex,draw] (h) at (4, 2) {}; + \node[tiny vertex,draw] (i) at (3, 2) {}; + \node[tiny vertex,draw] (j) at (2, 4) {}; + \node[tiny vertex,draw] (k) at (2, 3) {}; + \node[tiny vertex,draw] (l) at (2, 2) {}; + \node[tiny vertex,draw] (m) at (2, 1) {}; + \node[tiny vertex,draw] (n) at (1, 2) {}; + \node[tiny vertex,draw] (o) at (1, 4) {}; + \node[tiny vertex,draw] (p) at (4, 1) {}; + \node[tiny vertex,draw] (q) at (2, 5) {}; + + \path[edge,-] (a) -- (b); + \path[edge,-] (a) -- (c); + \path[edge,-] (a) -- (d); + \path[edge,-] (a) -- (e); + \path[edge,-] (a) -- (f); + \path[edge,-] (a) -- (g); + \path[edge,-] (a) -- (h); + \path[edge,-] (a) -- (i); + \path[edge,-] (a) -- (j); + \path[edge,-] (a) -- (k); + \path[edge,-] (a) -- (l); + \path[edge,-] (a) -- (m); + \path[edge,-] (a) -- (n); + \path[edge,-] (a) -- (o); + \path[edge,-] (a) -- (p); + \path[edge,-] (a) -- (q); + + \path[dash] (a) -- (5, 5) {}; + \path[dash] (a) -- (3, 5) {}; + \path[dash] (a) -- (3, 1) {}; + \path[dash] (a) -- (1, 3) {}; + \path[dash] (a) -- (5, 3) {}; + \path[dash] (a) -- (5, 1) {}; + \path[dash] (a) -- (1, 5) {}; + \path[dash] (a) -- (1, 1) {}; + + \draw (3,3) +(63.43:1.3cm) arc (63.43:90:1.3cm); + \path (3,3) ++(76.715:1.5cm) node {$a$}; + + \draw (3,3) +(45:1.7cm) arc (45:63.43:1.7cm); + \path (3,3) ++(54.215:1.98cm) node {$b$}; + + \draw (0.7, 0.7) rectangle (5.3, 5.3); + + \path[edge,<->] (0.7, 5.6) -- node[fill=white, font=\small, inner + sep=1.7pt] {$\sqrt{\delta}$} (5.3, 5.6) {}; + +\end{tikzpicture} +\caption{ + To show that we have a consistent discretization of the + Cauchy--Crofton integral formula, we construct a discrete set of + lines $\mathcal{L}_D$ such that the length of the edges $\norm{e}$, + the angle differences $\Delta \phi$ (here $a$ and $b$) and the + distance between lines $\Delta \rho$ goes to zero as $\delta \to 0$. +} +\label{fig:square_cons} diff --git a/theory.tex b/theory.tex index cfd4d1d..58bcf39 100644 --- a/theory.tex +++ b/theory.tex @@ -1122,6 +1122,10 @@ terminals of $e$ lie on each side of the perimeter $C$, and the approximation is exact for zero or one intersection points, but will, as we see in Figure \fixme{ref}, not be entirely correct when we have more. +\begin{figure} + \input{fig/curve_edge} +\end{figure} + \fixme{curve or perimeter here, maybe perimeter because then we know it follows the boundaries of the pixels.} @@ -1213,24 +1217,32 @@ parameter $\beta$, but apart from that, the sum is the midpoint rule approximation of the integral. For the regularization term we will argue that for a differentiable -curve $C$, the discretization of our domain $\Omega$ and set of lines -$\mathcal{L}$ gives a discrete Cauchy--Crofton formula that is +curve $C$, the discretization of our domain $\Omega$ and the set of +lines $\mathcal{L}$ gives a discrete Cauchy--Crofton formula that is consistent with the continuous one. We will show that for an increasingly refined domain $\mathcal{G}$, there exists a choice for $\mathcal{L}_D$ that leads to a consistent Cauchy--Crofton formula. For convenience we will use a neighborhood representation of $\mathcal{L}_D$ similar to the one in Figure \ref{fig:line_neigh}. -Consider a square centered around grid point $x$ with side lengths +\begin{figure} + \input{fig/square_cons} +\end{figure} + +Consider a square centered around a grid point with side lengths $\sqrt{\delta}$. As $\delta$ goes to zero, the size of this square will go to zero. Inside this square we can fit a square of $\lfloor 1 / \sqrt{\delta} \rfloor^2$ grid points. This means that the number of grid points along the outer edge of this square $\lfloor 1 / -\sqrt{\delta} \rfloor$ goes to infinity. For each grid point around at -the boundary of this square, we include a grid point having the same -angle $\phi$ to the $x$-axis as shown in Figure \fixme{ref}. The maximal -$\Delta \phi$ will then be between the horizontal or vertical edge and -its neighbors +\sqrt{\delta} \rfloor$ goes to infinity. For each grid point along +the outer edge of this square, we include in our neighborhood a grid point +having the same angle $\phi$ to the $x$-axis. This means either +including the actual grid point at the outer edge, or one having the +same angle, just closer to the center. This construction can be +seen in Figure \ref{fig:square_cons}. +The maximal $\Delta \phi$ will then be between the +horizontal or vertical edge and its neighbors, shown in Figure +\ref{fig:square_cons} as angle $a$. These angles can be calculated to be \begin{equation} \sup \Delta \phi = \arctan \frac{\delta}{\sfrac{\lfloor \sqrt{\delta} \rfloor}{2}} \leq \arctan \frac{\delta}{\sfrac{\sqrt{\delta}}{2} - @@ -1247,18 +1259,64 @@ we have \sup \Delta \rho \leq \frac{\delta^2}{\delta} = \delta \to 0. \end{equation} -The edge length is bounded from above by $\sqrt{2} \delta$ and will also -go to zero. Thus for a given curve $C$, our simplification of only -counting an intersection between $e$ and $C$ when $C$ crosses $e$ an odd -number of times becomes increasingly correct. +Since all edges are inside our square, the edge length is bounded from +above by $\sqrt{2} \delta$ and will also go to zero. Thus for a given +curve $C$, our simplification of only counting an intersection between +$e$ and $C$ when $C$ crosses $e$ an odd number of times becomes +increasingly correct. Further it is obvious that our tensor approximation in \eqref{eq:tensor_approx} converges to the tensor in the intersection point when the edge length $\norm{e_{ab}}$ goes to zero. -And thus... the perimeter approximation in \eqref{eq:per_approx1} is -consistent with the continuous formulation in Theorem -\ref{thm:riemannian_cauchy_crofton} +To see that this is enough to give a consistent discretization of our +integral, we write the approximation as follows +\begin{equation} + \begin{aligned} + \abs{C}_M &= + \int_\nu \int_\rho \sum_{x \in \ell_{\nu, \rho} \cap C} + \, \frac{\det M(x)}{2\left(\nu^T + \cdot M(x) \cdot \nu\right)^{\sfrac{3}{2}}} \, d\rho \, d\nu \\ + &\approx \sum_\nu \sum_\rho \sum_{e_{\nu, \rho} \cap C} + \, \frac{\det M(e_{\nu, \rho}) \norm{e_{\nu, \rho}}^3}{2\left( + e_{\nu, \rho}^T \cdot M(e_{\nu, \rho}) \cdot e_{\nu, \rho} + \right)^{\sfrac{3}{2}}} \, \Delta \rho \, \Delta \nu. +\end{aligned} +\end{equation} +As $\Delta \rho$ is constant for all lines in one family, we can regard +the discretization in the $\rho$ dimension as a midpoint rule +approximation, as shown in Figure \ref{fig:line_midpoint}. + +\begin{figure} + \input{fig/line_midpoint} +\end{figure} + +For the $\phi$ dimension (or $\nu$ equivalently), we chose to show that +the difference between the angle parameter of one line family and the +next $\Delta \phi$ goes to zero. As shown in Figure \ref{fig:circ_rule}, +the discretization of $\phi$ can also be regarded as a so-called +\emph{rectangle method} approximation of the integral, although not the +midpoint rule. The summand is evaluated in the end point of the angle +interval $[\phi_k, \phi_{k+1}]$, where $\Delta \phi_k = \phi_{k+1} - +\phi_k$. + +\begin{figure} + \input{fig/circ_rule} +\end{figure} + +And thus the approximation has been shown to be equivalent to +well-known, and consistent integral approximations, so the perimeter +approximation in \eqref{eq:per_approx1} is consistent with the +continuous formulation in Theorem \ref{thm:riemannian_cauchy_crofton}. + +Note that as we will work with digital images with fixed resolutions, we +do not really have the chance to refine our discretization. We do +however have to take these things into account when creating our +neighborhood stencil, to make sure that we get a reasonable +approximation of the perimeter lengths. + +\fixme{we did not really state that we have arrived at our final +discretization, and that the rest will be about the solution} \subsubsection{Stability and convergence} -- 2.47.3