From 37d557e93a6f9024ab0c365b8cfe4ca10e526eda Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Thu, 3 Apr 2014 19:56:33 +0200 Subject: [PATCH] Some more fixes --- main.tex | 3 + total.tex | 169 ++++++++++++++++++++++++++++++++---------------------- 2 files changed, 102 insertions(+), 70 deletions(-) diff --git a/main.tex b/main.tex index f517b0f..7a81b16 100644 --- a/main.tex +++ b/main.tex @@ -36,8 +36,11 @@ \usepackage{algpseudocode} \tikzstyle{vertex}=[circle,minimum size=20pt,inner sep=0pt,draw] +\tikzstyle{small vertex}=[font=\footnotesize,circle, + minimum size=9pt,inner sep=0pt,fill=gray!40] \tikzstyle{selected vertex} = [vertex, fill=red!24] \tikzstyle{edge} = [draw,thick,->,fill] +\tikzstyle{dash} = [draw,dashed,-] \tikzstyle{bent edge} = [draw,bend left=80,thick,->] \tikzstyle{double edge} = [draw,thick,<->] \tikzstyle{weight} = [font=\small,sloped,fill=white] diff --git a/total.tex b/total.tex index acced19..e6deea5 100644 --- a/total.tex +++ b/total.tex @@ -231,6 +231,7 @@ We denote $S$ for the grid of pixels, and assume that the value of each pixel is taken from the set $\mathcal{L} = \{0, \hdots, L-1\}$. This is a reasonable assumption for grayscale images. +\subsubsection{Regularization term} Chambolle discretizes the total variation as \begin{equation} \TV(u) = \sum_{i,j} \sqrt{ @@ -286,17 +287,24 @@ of a possible one-dimensional image. \centering \begin{subfigure}[b]{0.4\textwidth} \centering - \begin{tikzpicture}[scale=1] - \node[vertex] (x) at (0, 0) {x}; - \node[vertex] (y) at (2, 0) {y}; - \node[vertex] (a) at (0, 2) {}; - \node[vertex] (b) at (0, -2) {}; - \node[vertex] (c) at (-2, 0) {}; - - \path[edge] (x) -- (y); - \path[edge] (x) -- (a); - \path[edge] (x) -- (b); - \path[edge] (x) -- (c); + \begin{tikzpicture}[scale=.7] + \foreach \x in {0,...,4} { + \foreach \y in {0,...,4} { + \node[small vertex] (\x\y) at (\x, \y) {}; + } + } + \node[small vertex,draw] (a) at (2, 2) {}; + \node[small vertex,draw] (b) at (2, 3) {}; + \node[small vertex,draw] (c) at (2, 1) {}; + \node[small vertex,draw] (d) at (3, 2) {}; + \node[small vertex,draw] (e) at (1, 2) {}; + + \path[edge] (a) -- (b); + \path[edge] (a) -- (c); + \path[edge] (a) -- (d); + \path[edge] (a) -- (e); + + \path (00) [edge, <->, anchor=center] -- node[anchor=south] {h} (10) ; \end{tikzpicture} \caption{Size four neighborhood.} \label{fig:c4_grid} @@ -304,63 +312,81 @@ of a possible one-dimensional image. ~ \begin{subfigure}[b]{0.4\textwidth} \centering - \begin{tikzpicture}[scale=1] - - \node[vertex] (1) at (0, 0) {x}; - \node[vertex] (2) at (-2, 0) {}; - \node[vertex] (3) at ( 2, 0) {}; - \node[vertex] (4) at (0, -2) {}; - \node[vertex] (5) at (0, 2) {}; - \node[vertex] (6) at (-2, -2) {}; - \node[vertex] (7) at (-2, 2) {}; - \node[vertex] (8) at ( 2, 2) {y}; - \node[vertex] (9) at ( 2, -2) {}; - - \path[edge] (1) -- (2); - \path[edge] (1) -- (3); - \path[edge] (1) -- (4); - \path[edge] (1) -- (5); - \path[edge] (1) -- (6); - \path[edge] (1) -- (7); - \path[edge] (1) -- (8); - \path[edge] (1) -- (9); - - \draw (0,0) +(0:1cm) arc (0:45:1cm); - \path (0,0) ++(22.5:.75cm) node{$\alpha$}; + \begin{tikzpicture}[scale=.7] + \foreach \x in {0,...,4} { + \foreach \y in {0,...,4} { + \node[small vertex] (\x\y) at (\x, \y) {}; + } + } + + \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[small vertex,draw] (a) at (2, 2) {x}; + \node[small vertex,draw] (b) at (2, 3) {}; + \node[small vertex,draw] (c) at (2, 1) {}; + \node[small vertex,draw] (d) at (3, 2) {}; + \node[small vertex,draw] (e) at (1, 2) {}; + \node[small vertex,draw] (f) at (3, 3) {y}; + \node[small vertex,draw] (g) at (1, 1) {}; + \node[small vertex,draw] (h) at (1, 3) {}; + \node[small 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{Size eight neighborhood.} - \label{fig:c8_grid} + \label{fig:c4_grid} \end{subfigure} \caption{Two common neighborhood stencils.} \label{fig:common_neighborhoods} \end{figure} -Recall that we managed to write the total variation as an integral over -the range of level values in \eqref{eq:coarea_formula}. Here, we + +We also need to introduce the notion of pixel neighborhoods. A pixel in +the image has a neighborhood which consists of the pixels around it, but +not itself. We denote the neighborhood of pixel $x$ by $\mathcal{N}(x)$ +and we will call the line going from pixel $x$ to pixel $y \in +\mathcal{N}(x)$ the \emph{edge} between $x$ and $y$. Two common +neighborhood stencils are shown in Figure +\ref{fig:common_neighborhoods}. + +Recall that we managed to write the total variation as an integral of +the perimeter of the level sets in \eqref{eq:coarea_formula}. We estimate the perimeter of the level set $u^\lambda$ in the discrete setting, such that the total variation can be written as a sum over the -level values. We introduce a neighborhood? - -We estimate the perimeter in the discrete setting to write the total -variation as +level values \begin{equation} \TV(u) = \sum_{\lambda = 0}^{L-2} P(u^\lambda, S) = \sum_{\lambda = 0}^{L-2} \sum_{(x,y)} w_{xy} - \abs{u_x^\lambda - u_y^\lambda}, + \abs{u_x^\lambda - u_y^\lambda}. \label{eq:tv_discrete_int} \end{equation} -where the sum over $(x,y)$ signifies neighborhood relation and the -$w_{xy}$ is the weight of this relation. Intuitively, the perimeter of -the level set $u^\lambda$ is proportional to the number of edges -crossing this perimeter, as $\abs{u^\lambda_x - u^\lambda_y}$ only -contributes to the sum when one node is 0 and the other is 1. -\fixme{Describe what this sum over $(x,y)$ is actually over.} - -The sum only goes up to the level $L-2$ since $u^{L-1}$ is constant -equal to 1 in every pixel of the image. Figure -\ref{fig:common_neighborhoods} shows the two commonly used neighbordhood -stencils, which will be discussed more thorougly in \fixme{Section ??}. +The sum over $(x,y)$ signifies a sum over all pixels $x$ and $y$ that +are in a neighborhood relation, and $w_{xy}$ is a weight parameter. The +sum over $\lambda$ ends at $L-2$ since $u^{L-1}$ is equal to 1 in every +pixel of the image. + +Intuitively, the perimeter of the level set $u^\lambda$ is proportional +to the number of pixels at the boundary of the set. This is again +proportional to the number of neighborhood relations crossing the +boundary, and $\abs{u^\lambda_x - u^\lambda_y}$ only contributes to the +sum when one node is in $u^\lambda$ and the other is not. + Boykov and Kolmogorov argue in \cite{boykov2003computing} that if the weight is chosen as \begin{equation} @@ -368,27 +394,28 @@ weight is chosen as \end{equation} the discrete perimeter in \eqref{eq:tv_discrete_int} converges to the continuous perimeter in \eqref{eq:coarea_formula}. Here, $h$ is the grid -size and $d_{xy}$ is the euclidean distance of the edge. The $\Delta -\phi_{xy}$ is the difference between the angle of this edge and the -next edge, if the edges are sorted by increasing angles. These +size and $d_{xy}$ is the euclidean distance of the edge from $x$ to $y$. +The $\Delta \phi_{xy}$ is the difference between the angle of this edge +and the next edge, if the edges are sorted by increasing angles. These parameters are also shown in Figure \ref{fig:common_neighborhoods}. Boykov and Kolmogorov prove we have convergence when all of $h$, $\Delta -\phi_{xy}$, and $d_{xy}$ go to zero. In other words, if the grid size -decreases and we at the same time increase the density of the -neighborhood. +\phi_{xy}$, and $d_{xy}$ go to zero. -\fixme{BAD TRANSITION} - -For two binary variables $a$ and $b$ we can easily verify that $\abs{a - -b} = a + b - 2 a b$. Using this we rewrite \eqref{eq:tv_discrete_int} to -\begin{equation} - \TV(u) = \sum_{\lambda = 0}^{L-2} \sum_{(x,y)} w_{xy} - \left( - \left(1 - 2 u_y^\lambda \right) u_x^\lambda + u_y^\lambda - \right). - \label{eq:tv_discrete} -\end{equation} +\fixme{IS THIS EVEN NECESSARY? For two binary variables $a$ and $b$ we + can easily verify that $\abs{a - b} = a + b - 2 a b$. Using this we + rewrite \eqref{eq:tv_discrete_int} to + \begin{equation} + \TV(u) = \sum_{\lambda = 0}^{L-2} \sum_{(x,y)} w_{xy} + \left( + \left(1 - 2 u_y^\lambda \right) u_x^\lambda + u_y^\lambda + \right). + \label{eq:tv_discrete} + \end{equation} +} +\subsubsection{Fidelity term} +Now that the total variation is discretized, we need to take care of the +fidelity term. We define the following function for some pixel value $k$ and some pixel position $x$ in the original image $v$, which is the value of the energy if we were to color pixel $u$ with label $k$ @@ -426,6 +453,8 @@ Since $\mathbbm{1}_{\lambda < u_x} = (1 - u^\lambda_x)$ we rewrite \big) (1 - u^\lambda_x) + N_x(0) \end{equation} + +\subsubsection{Total energy} We have now discretized the energy function and decomposed it into a sum over all the levels $\lambda$. Ignoring the constant term $N_x(0)$ we are left with -- 2.47.3