From 4341eba6d09eccfe555f21017676f1b16fefdd90 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Tue, 11 Nov 2014 15:30:20 +0100 Subject: [PATCH] More on discretization --- theory.tex | 172 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 110 insertions(+), 62 deletions(-) diff --git a/theory.tex b/theory.tex index f14b3bf..adc4239 100644 --- a/theory.tex +++ b/theory.tex @@ -1019,7 +1019,7 @@ taking values $k \in \mathcal{L}$: \begin{aligned} F(k) &= \sum_{\lambda = 0}^{k-1} \big( F(\lambda + 1) - F(\lambda) \big) + F(0) \\ - &= \sum_{\lambda = 0}^{L-2} \big( F(\lambda - 1) - F(\lambda) \big) + &= \sum_{\lambda = 0}^{L-2} \big( F(\lambda + 1) - F(\lambda) \big) I( \lambda < k) + F(0), \end{aligned} \end{equation} @@ -1028,10 +1028,12 @@ true, and 0 if $x$ is false. Since $I(\lambda < u_x) = u_x^\lambda$ we rewrite \eqref{eq:fidelity_approx_1} and obtain \begin{equation} \sum_{x \in \mathcal{G}} \abs{u_x - v_x}^p = - \sum_{x \in \mathcal{G}} N_x(u_x) = \sum_{\lambda = 0}^{L-2} \sum_x + \sum_{x \in \mathcal{G}} N_x(u_x) = \sum_{\lambda = 0}^{L-2} \sum_{x + \in \mathcal{G}} \big( N_x(\lambda + 1) - N_x(\lambda) \big) \, u_x^\lambda + N_x(0). \end{equation} -\fixme{Why stop at $L-2$} +Note that since our image takes values in $\mathcal{L} = \{0, \hdots, +L-1\}$, the thresholded image $u^{L-1}$ is equal to zero everywhere. \subsection{Regularization term} @@ -1042,11 +1044,12 @@ the discrete levels to get \approx \sum_{\lambda = 0}^{L-2} \PerA( \{ u > \lambda \}; \Omega) \, \Delta \lambda. \end{equation} -Note that we do not include any $\Delta \lambda$ difference, as we can +Note that we will later ignore the $\Delta \lambda$ difference, as we can just absorb this into the $\beta$ parameter. The perimeter is then calculated using a discretized version of the Cauchy--Crofton formula -introduced in \fixme{ref}. -\fixme{Why stop at $L-2$} +introduced in Theorem \ref{thm:riemannian_cauchy_crofton}. Again, we +stop the sum at $L-2$ since the level set $\{ u > L - 1\}$ is empty and +has zero perimeter. \subsubsection{Discrete Riemannian Cauchy--Crofton formula} @@ -1055,22 +1058,24 @@ introduced in \fixme{ref}. \end{figure} By approximating the integral in \fixme{REF} by a discrete sum we obtain the approximation -\begin{align} - \abs{C}_M &= \int_\mathcal{L} \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\mathcal{L}(\ell_{\nu, \rho}) \\ - &\approx \sum_{\ell_{\nu, \rho} \in \mathcal{L}_D} - \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}}} \, \Delta\rho \, - \Delta\phi \\ - &\approx \sum_\nu \sum_\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}}} \, \Delta\rho \, - \Delta\phi. - \label{eq:cauchy_crofton_approx1} -\end{align} +\begin{equation} + \begin{aligned} + \abs{C}_M &= \int_\mathcal{L} \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\mathcal{L}(\ell_{\nu, \rho}) \\ + &\approx \sum_{\ell_{\nu, \rho} \in \mathcal{L}_D} + \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}}} \, \Delta\rho \, + \Delta\phi \\ + &= \sum_\nu \sum_\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}}} \, \Delta\rho \, + \Delta\phi. + \label{eq:cauchy_crofton_approx1} + \end{aligned} +\end{equation} The set of lines $\mathcal{L}$ has been discretized to the lines $\mathcal{L}_D$. Note that we are approximating the length of the \emph{differentiable} curve $C$ in $\Omega$. Further we need to @@ -1128,6 +1133,7 @@ tensor in the two endpoints of the edge. Thus for an intersection point $x$ somewhere on the edge $e_{ab}$, we approximate the metric tensor by \begin{equation} M(x) \approx M(e_{ab}) = \frac{M(a) + M(b)}{2}, + \label{eq:tensor_approx} \end{equation} the component-wise average of the tensors in the two end points of the edge. \fixme{really? componentwise? will that not mess up the @@ -1144,65 +1150,107 @@ the distance between lines in a given line family is $\Delta \rho = \, \delta^2 \, \Delta\phi}{2 \left(e^T \cdot M(e) \cdot e\right)^{\sfrac{3}{2}}}. \end{equation} -Going back to the perimeter of the level set $\{ u > \lambda \}$ we get +Going back to the perimeter of the level set $\{ u > \lambda \}$ we can +rewrite the sum to be a sum over all edges that goes from one side of +the set to the other such that \begin{equation} \PerA(\{u > \lambda\}; \mathcal{G}) = \sum_{e_{ab}} \abs{ - u^\lambda(a) - u^\lambda(b)} \frac{\det M(e_{ab}) \norm{e_{ab}}^2 + u^\lambda_a - u^\lambda_b} \frac{\det M(e_{ab}) \norm{e_{ab}}^2 \, \delta^2 \, \Delta\phi}{2 \left(e_{ab}^T \cdot M(e_{ab}) \cdot e_{ab}\right)^{\sfrac{3}{2}}}. + \label{eq:per_approx1} \end{equation} -The absolute value $\abs{u^\lambda(a) - u^\lambda(b)}$ is one if one of +The absolute value $\abs{u^\lambda_a - u^\lambda_b}$ is one if one of $a$ and $b$ lie inside the level set and the other lies outside, and -zero otherwise. In other words if the absolute value is one if $e_{ab}$ +zero otherwise. In other words the absolute value is one if $e_{ab}$ crosses the perimeter of $\{ u > \lambda\}$ an odd number of times, and zero otherwise. \fixme{We now have the problem that $C$ is a curve, but later we want it to be a cut...} -\subsubsection{Consistency, stability and convergence} +\fixme{edges here are a bit different from edges later} + +\subsubsection{Consistency} As for any discretization these are important properties to consider. Consistency relates to how well a solution to the continuous problem -fits in the discretized equation. This would optimally be controlled by -the resolution of the discretization in such a way that if we refine the -discretization, the - -Consider a square centered around grid point $p$ with side lengths -$\sqrt{\delta}$. The size of this square will go to zero, while the -number of points along the outer edge $\lfloor 1 / \delta \rfloor$ of -the square, goes to infinity. Also, the number of points in the square -(and thus the possible number of edges) goes to infinity so the -discretization is finer and finer. So, as $\delta \to 0$, the length of -the edges are bounded by $\sqrt{\delta} \to 0$, and $\Delta \phi \to 0$ -because the number of points around the edge of the square goes to -infinity! \fixme{waving with hands} Also, since the curve is somewhat -regular, when $\norm{e}$ goes to zero, the number of times the curve can -cross $e$ is maximum $1$ so that's great. Also, $M(e) \to M(p)$ -obviously. \fixme{Some figure here aswell. And maybe some consideration -of $\sup \Delta \phi$ etc.} - -\subsubsection{Back to the energy...} - -\fixme{We talk about edges, but it's not really a graph yet...} -The curve $C$ that we are measuring is the perimeter of a level set -$X = \{ u > \lambda \}$. This means that the edges crossing the curve -- -$e \cap C$ -- are exactly those edges with one terminal inside $X$ and -the other terminal outside $X$. \fixme{Terminal?}. This means we can -write the discrete regularization energy term as +fits in the discretized equation, in other words, how well the +discretized equation approximates the continuous one. + +It is obvious that the discretization of the fidelity term in +\eqref{eq:fidelity_approx_1} is consistent. We have left out the pixel +size $\Delta x$ in the sum, and absorbed it into the regularization +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 +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 +$\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 +\begin{equation} + \sup \Delta \phi = \arctan \frac{\delta}{\sfrac{\lfloor \sqrt{\delta} + \rfloor}{2}} \leq \arctan \frac{\delta}{\sfrac{\sqrt{\delta}}{2} - + \delta} = \arctan \frac{1}{\frac{1}{2\sqrt{\delta}} - 1} \to 0. +\end{equation} + +Further we know that for each line family \begin{equation} - \sum_{\lambda = 0}^{L-2} \PerA( \{ u > \lambda \}; \Omega) - \approx \sum_{\lambda = 0}^{L-2} \sum_{e} w_e - \abs{u_{\delta_1(e)}^\lambda - u_{\delta_2(e)}^\lambda} + \delta^2 = \Delta \rho \norm{e}, \end{equation} -where the weight $w_e$ comes directly from the Riemannian -Cauchy--Crofton formula +and since the edge length $\norm{e}$ is bounded from below by $\delta$, +we have \begin{equation} - w_e = \frac{\det M(e) \norm{e}^2 \delta^2 \Delta \phi}{2 (e^T \cdot - M(e) \cdot e)^{\sfrac{3}{2}}}. + \sup \Delta \rho \leq \frac{\delta^2}{\delta} = \delta \to 0. \end{equation} -Now we just have to make sure that this fits well with the -graph-representable function definition and all will be good. + +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} + +\subsubsection{Stability and convergence} + +For a discretization of a problem to be stable, the solution needs to +depend continuously on the input data. So in our case the output image +$u$ should depend continuously on the given input image $f$. We will not +prove stability here, but intuitively there is no reason to believe the +method is unstable though, as small changes in $f$ only gives small +changes to the functional $F$. \fixme{well this is not nearly enough I +guess} \fixme{ref?} + +Convergence is in some nice cases, but not nearly all the time, +equivalent to consistency and stability. It answers the question of +whether a the solutions of the discretized problem converges to the +solution of the continuous problem as the discretization is refined. +This will also not be considered here, but we refer to \fixme{ref}. And +note that even though convergence is important, in practice, we have no +possibility of refining the discretization, as the grid structure is +defined by the digital image which is already composed of discrete +pixels. \subsection{Total energy} -- 2.47.3