From 7ad828118256cf8278781680bc27f78380393110 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 1 Dec 2014 18:35:53 +0100 Subject: [PATCH] Theory, results and figures --- fig/anisotropy_circle.png | Bin 0 -> 924 bytes fig/circle100.pgm | Bin 0 -> 10054 bytes fig/circle100.png | Bin 0 -> 564 bytes fig/circle100n.png | Bin 0 -> 7371 bytes fig/neigh_artifacts.pgm | 4 + fig/neigh_artifacts.png | Bin 0 -> 388 bytes results.tex | 64 ++++++- theory.tex | 344 +++++++++++++++++++------------------- 8 files changed, 238 insertions(+), 174 deletions(-) create mode 100644 fig/anisotropy_circle.png create mode 100644 fig/circle100.pgm create mode 100644 fig/circle100.png create mode 100644 fig/circle100n.png create mode 100644 fig/neigh_artifacts.pgm create mode 100644 fig/neigh_artifacts.png diff --git a/fig/anisotropy_circle.png b/fig/anisotropy_circle.png new file mode 100644 index 0000000000000000000000000000000000000000..24888e369bc57050be0bdbb7a1e7b25e43aabb47 GIT binary patch literal 924 zcmeAS@N?(olHy`uVBq!ia0vp^DIm-NBp5|$GdrZPMD^m1u1al2ebz@ymd5h!QS(rGRA`nQ zZZJtRN@?O*KB=Ov(&&{TT4&YdK20f}CfXmKQF5Xuz3XXwHZ!yJ5;ge;w-;PEpHlX1 zQb4_8==5J-Sr^WH!!42{*vA$7O+b;q^x8GArI!p>Dh1DTe&7)2YwthdvN-U0 zWW3_Z6eBhFz9)9CRFrP5U9F(MIDu8%)Yv{>?vVIexzH(fWjlH19gpXIGnf6vWh=es zu6GVD7l;cxC$U6h@?`H7_sVOQTR&V^wdl6#{ic5(AN3w-*|MS}M`^*0$M@!O2KPO- zxyap8;^K36l_JCZyUS}oP4H3Myoz;J+xl5WzMIA0t~FmRv1-j4kNbP=7WuAyefI23 zUE!lPE|m!qkM`}lwspdUvn5u!R+G%SUhK|W!aFHxBdg5E+9U&x?GD#ozxXa3rf~I0 zw@Zrl-$l2}MOU*NklIwVb5G8ed&N6t${sgnP3d*IBJaH1;AWq^Sa59=XT19BC9fAb zE(toS^fU36!raOC)=Ub|n;7ZRBEr==TkoH?hi1TnvopjZVtBSF{x^A-;$b)6Uxh_6 zn&-x`x4xf0PtoR*R=Uxz;2aWt?(Rpk{f&>OKV7rAld{FjY5NTXDaRLixKX-w!i5?>uGK{y}=eyK{4&wX>I$MRLA; zyywQBhRTw>=~E}ja=&TmId|~p^@dsw$uANyUw(a$dy_izk(nH!1N-w?{0tu8B(q8-u|HF^SgYtv;;H?!b zNNUTrRm$&@sdA{I_mpOmjeEh7o{C&0k-h6%X z>Gjl`PA0tkcsH||2lS8vqyQ;E3XlS%04YEU{AUI7ED8M)V{JNCzO#a{Zi8TKZ2=@`hhQu)1{rrjFg7*>>0}}P zf*F&JSV)crF)3PSlmrm%4nKuY-L$`>L!w-Ib-Wk}vah>RTaam`F-NITA{3E>%3ZS^ zm4(x0Un*;gA@XOxQ2Ca2AAym}!F^lA&Y1P}E&FBqL=ri+Z=2|2gnfO>exW{wX2=;s z1id`u=shES9(n+x_hn+Z(8@*3UCdna;ApiYlD(bpc3cQZdT&}IH=WnFfnBzg5MDngF3C6TB2#K z*zDW^l-Cu?g38)mMoDGxJDHmD6H;rL8^USp;-Z;2v8(B@b*0qK2$c}d_r~dCV30qRA5T;z{@lRsm9=%hC zg0~qwOb%uh5bn`Kj&f@j`n+2F^Iick1a(VXBTACYmy!cvQhGxPHl4D}3+yp;QZ8dX6WQxZ#3t&)pUffR$0 zfuV`6p^>hEVThrHm7$@PiK(`Mp_PGw+}i~vC>nC}Q!>*kacjumAOT7S44$rjF6*2U FngB&P$@TyM literal 0 HcmV?d00001 diff --git a/fig/circle100n.png b/fig/circle100n.png new file mode 100644 index 0000000000000000000000000000000000000000..5f95225344ce3de390fa143b84ee1bfd2c2b0387 GIT binary patch literal 7371 zcmZ{pQ(q+xptY-+jLA**Xq6Q*{UcDC)EZCev&=Q{uQy*n4@Vy)-5 zE}l=YVpNr7&{2p`U|?X-Ux8ckb zWF%oeqLLsz|1D%^SzWjPDEt2-J!U5i14H~KCn=_By``jwY@o9G5}0s9%+d3N-oTz` zd4a}ZzTHv>FyD@}r|poe2c*OcrN`2%$(qU{rBqQ-s!L|3(kje}#~goj9=|vUf4n^T zJ3Zw4UHeV>WE}@=xuq7Q;OJlnQTh$B!>CYi0$}NCrCfIsA~*_m>Fo*j1YK*xk`940 zJjbM4w`*@`Dkq`TJi%AJH8ygs6!tz{6sHgE*5PHmUbk0!pSXMB#7K--WvdauRmHyw z>6~@3vCtlC5U$`QVYHtp(7k{1ub!XnPguX*0`4s}WF8BruB_JZeyjdIJ^`j|{(B~^ z{uJkvQsIS2ZXsT4vM!6;()$kVk#bxgnXQ=&*rCoB_S&7V)Iw#)sFXM1Uph(Kzl9-# z9q|4q_iiaNzRP??K@19h4dCnbB&{R!+hNT?WXFt_##AL0uroPj_4GE%-{CyqKiG=(rR z+3veHi5yto-hu)yoC5I-JdHG7lTLA{`Iu<=mQ~hNGE>eUn|Ac)wbOXLTN}U zubtyqTTNK~r#pp0?>VE43BE4Z>D=8sabXWtvZXUgUVWbriWK;Y_EMqh>kms()bbUS zv@w<6OKeh&26W=a_1RB{BSA-GDJnHefPn5nBpZ{Gd%%B4eZZ#nm~ch@%@*I3-gUb5 zM)tS{utPZL`4@cTNiEce1Bo7*Qny|{q%`YV86PL`di%NS@*QW9K~E^g#zUi8oi{^Q z#n?YM?sXoqs$$CJE-s4hlJ3u7jz?j49O$(I6}<|d}PU)5t3=C>Fg zg+0;xk(Y}r8B+tox;KRFs)&q1CVxY(M`7gsR68qlbs&&*v&C{j7m23Z`yuVrb$`&c z$P2t%ukxX|iJ~1|&{tfy!e%UykNAQu_;8U-t8~_D{sIqe)JlyI; z;OyIA;nl*vY^=<$otPH9j{RO!dkc(Z-7QSh&nj{iLO_F7L=jLT9AlX8f%2*w6@`x` ztcf-KJrrK#M=ss{&l4~Ud7Onj|9O~?CHz3i5*NT7CIa_M>T@)H`rT}*YBb2nFX9{L za4@{J&>xyV;-_4sr@4)qTaIK);m`GkC6k5>w#p1BOxf)1(0}MUI=<^RYp+^H`aspqa}p=2#-IOz)*ChUQss#z8Zyfh7T6V!e^)&VPO5 zl*?i0W*ARyKmT2Mi3Jq*tgjJdbH?Ro(eN4VppIaotVUY+!XC#DJ)McjptoxD;hb3A zHx3%8#I47mij8R%92gsWj*z>pS%upddg1uYHvokDEIH~34o|M|IKNhc^Vr>=-0dgv zEPM^Mni2sRV3Ak=!VeaijNUJ9td%@A{FoSvL(hLFEn7Y3hSL<$lri-?jSI&v1`}FT zkb5;$rl=t8SRW@~XWxld@@=g8F&zCUGf>LTP+jZI+%P`-E|QVG=6NooyZGQ-*mX@Q zhV%Nsw<#09tP6kKNn#em%FsF1y`PzS zbu(*GGvdEg+4N7}Ibx(f!h@(PI)q64Q~LD;nU!4#6Lmj+%D7xlpUkQVkx}G}ON*1u zrkQhMn=9%GW8E;8>Tq1V)gFOEeRWJwNV~6z#Z?B*%6m7mU*_6P zEEom`xF7&9VDYeW{SnhBK1I*_WT!`SEmLAFAp?~f`M=5OcAnWWb7JcZnF3o*_K$S{ z);XmpwL;JI@iq1fuvXx_C{t`oS5%uRHL}lLZA3%}s5coj$*jr03(N7GbySm1OZ4nw z1w`Zp(03vEnLKsj?b%ZIU4o9U)Wu6kXgLx0K^}#Yae8SSZLjtadnEyLr-25? zXNx9MXX>iX{wXO=1^LqZ@P2k(h#2KOFaFki>E0wySx!lRvA5MJ#62&Et_y zAqa3;lGG9}WED@%4`!gU-~!ig(Pr;b37)xAa#b|+0N=qEp$vTOZ;7NdT!zZoDmnU` zh!kSq37>kj=p<=HM9WF>SX7)&A8o(TUQ7$fNJwBX3rAAdsPWJKd2d+iK_sP{0Oo*y zc`HfKAwO-p>!cZSWSs}+e9fs3c^p)pC)3VPKsU?)3;ztKQ{x*>IzqiZUT0Ehzo_*O zpHmuJ7%&R4x*7+t?STJ55SdQML#-saX(zy_qZw! zQ=_Joi_}39aL#I;;*6aeD5533T?mh%y32A*AgH+2IK{klwiDn3z-k<{Y0`J?^$gBB zdnXqbn`7iM`seeb<8(5ij}%>$s*W~uwCF22y1X35QFSQ4DWw!s1L-YGuEXN2p!Pn(C%LLh*D3VTA538oD68{#C7^p z8^VU{OB!j64x#X-#@-3>G;|m%FIwr?A4%BG-5?MWHH!;p#Yh#U^Fy;0HyN<+f7yb^ z_nSSW7^68;Jq3t4JbcCR%j+p{5+bw9tU@4%V%mzOCm2Sj{0Idy^9UA9aMib!e{dG~ zn#rgK8C|m0lyri9a9!{YEeZKE-`+fQ@Ko}->NEJ1P(DJ@jo%C759oil8o z2elj2DpH>hYJg2j(+BUN7(!1th6P3><$)hE&Z_i;eFlQk#M*+X-||hK z{BlZ7^RrXV_crz+)%A?4q^gKji|<+6l-deeh-s68jQRMW3i$qJy;4irx%w1js`a-& z-#NoF*r_r~%+HC6iL+9JlA3+@{MoKmwM-9j5Yj#y{H5M!y`}aaP*0|O5B9}; zAf4rDN0TW$Qaq|-0@`*+5t(r-OyYAsKUi8^X;U47)_H>D84@zD|2!8d(YW5SRkGK@4@$k!SD>D9%|`Z?y;+-9A4aDqV5$P ztXoKO^=hyd!=C~TUl)l39*&xUJ$jIfsW##0KK$z05DqME>HI8)pv2;7*KKwAJDM$=VL*(;=3F-H#s;V8C~5~^HAMJ-E5un zY@I)K5hG>xdZ9#UXeNPMeCq+$&l=bKq(#JRnJ)q}qFraq^m&b8{||$8rzujjyRj0( zONr?n0~HPqb;;3bq-$$lv>hVH`Vgs_x?`TCPjf(sxKotoeeZ1`IWsJN;W`rm_+yyFQ!`EIx6Pw!|*p&f4pF`DcH&pu5N+H)ddlF_{;3olY4+!|tPRZtFpF zI2nEg^}7-hQfI*t!HQ((%E((H+Gwb6JIZImNe$73F?Jm$tGLiJafL75*5cPmBYu`~ zTWiFp6>~`LCC|G-@({N9Rkk9^eaS#fE3s}8D=T#P>=$jEN?~e423-gFEK0i;sG` zxEPoNT+jFw5D$Pq3r!^8zUxp{n)yw!xVP6^X<>-;R~uti8?;1_qn{Bly1akiTu>@5 z^vyN%D#)#xfaT%R%_2Qrtn&`h;Pu;dYHhMJV%vi89gQ5=?GJCVjxJ59!t=vlBQ=4$ z)IJvFLePt3#gopviDye%oO%%{-uHqw-mqC6dUYn+-hKmqfzxqWaKFNr_&!vnm)1-M zA)>3fIqz?eoU#Ysl&1jvl8uffdT5w=_-`d4*@{eiVJUlzWqHcisDy)SQlE-5xQqt$ zL{BDSEAzE>af+T^6)evDf1*0|Xxo&z*CmpGQYRA-$Hsw6Xo{p0XQoIjezwk6%fKE@ z4mqT(kxYA$qw>Y=v$)*!c_!hRIyKmhF}2~ha@(<`46big!3L8<;5%$3hRKRZf!#&n zp^%nl+Mbl&fV4*!DF)LN;QBzqvGD|P4_+o>P-3#zRZkNIVZ%q^%1wO|L$x2|%&C40 z%z>bKb$056I}}AzKR++SQ z0Gl=|BaBF<`JZD}yh?&+_PGO@6$#PCxQa7<$2#!s4 z;LRvVi#Uli(=l+h2*phk7otbTN``35lP&i{3@K2`^UG5x#v?hcObRja!kkG*`)fEM z-5vY0Yyp5>&&q7y5tQ~IeegukIQ$e@y zWw$Y|#i<)N>9RI87OvtV6&-_UG)HNM?bWlte99egb9OBnTLy4cc;DFfoHC~@aDI&{ zmXT@J_k|v(RF5BGwgeIQ5e`fCiC4@AP3TG|S*lk%miPuo1Nu^hz*h$hcli^`vqkL) z5k|JUJ)y_=^NeNWdn|g=JKAUfOhXoO@fVyx{NMk!t@--m>weQo?4j1tlo=mX&j?T8 zEk@=zGk{7Up3=d&E~+Pl?%WLQ#)~c~v}KYu-0v4Obz8p+KtT)+;%?wgm9#3lM!wPh zlu5F&nRFoDl1%1@0SKx_j`PMoE(1-jzGQ9$LFXid&@THcI35y7hNrpy3fo4YIO6uZ zg|%h6N-h;ACE@SPt`K>yAA*O+L{kc4?sI`^_p>l5ALS2M=~8PlTG$*VHmKbs2Mr$6KvcXD$uar?r&1c%WILz49WA56d zsU_{C)|sUVgq-;l#oE{Dc3%cC{~Ot3Wvo$CO~c0kTX4ZQ zK2!es?&1j#s%6E$u{TkFtgomxNk~W9@NA{lNoqavZu@@rT56ZANK)*NRnsPP!Mz9d zE%&onwY`dw2r*~8gocHp2t=ndHsN#>lvAQF@ey5tgahs-FpfVR^pqojB|)}rhxKDoy7&5J9^Co*7OeqvcF65rI}zI(9W*$e zmNOdUwYEK~4cn5XtKz>Q;!o~n>O$>RWIhMx2zCBkf5>g0qJKn_6q?mK!o{3$_~rb8 zVMF=>TSYpPitrkKBl|lgw8Riub~Qp7D5d*g9lAqF{d|Yj17WD^OC>k;l&Q{$3=Ab< z?vvxqJdSrKDmcKV36n-jmFw0<5L4z9wDoA>Ky3DL5p^t$AA;lAjMZVln^{2HG*fomzNEq4e%G6@2!G@I6E;98K;wg}~~^WwN6M z$T)plIu_?K>TV0+X=jrJRK?d|Q;*w@MIrLBp&G#fSMjIKeF*rj;WisE-ZvO*JjR-u z1D17^b}vy0i7Vrjn8APO&REmEhfewL5SoU&4Fs2zGWL8}=Vdodb!EYolKv+&p?Lu$ zP-(-yx9}imq6#WGWbdLEDt*jORFB-Lr6$wky~3-}V9cZo{>+X*<*~DB!n3Tw%5m7? zC1f~(JMYZw7z>lGb2Fe?d-R+rFJi>ksw~lbN|HPTJJB6StGF3TJ%E%>GpAYvpqZEL zV(tgzF33cV>S?c1IX_Xn0mu1+TJzq@mYA=Pe=tg~h}&gIn#W{~cGGw;Y*ixfe0%Pf z8sFse8u_2d25ELR>w5VX5_XK?FU~U>H>T;RPoUz`Jn@S=;UK?8M#?ymL{w@%W)JRV%t%3{UJhV5D-ppY5t*TUkb|V4FfAuC@ zl|~$p3HU>?vjxA2-Nx~kX!ZqHOW3xSf5ra@exH-2rE0}vqh84t)UgZ>qMl$>Iy~8~ zPYxWG?up*^5Yk6zCco@^?(=Es=&g?lX(TFzGuLDZ@fYpFi_={@nR66!*IK08{~&E+ z&Fn_7?rT$4!8_yVzp`b-H=Iu|%0^s<<D$2<2OOV-sjxa^OGqsbQKE@sG{ zt~@pWhV+O7ge!pw90t8N5w;`v9E&`-#SE5Ijs6(?kU^8jk} z@U=@HPQ>Jn3@Ccv`hn6t4wf&Al7Z)#S&IGLXPc&zXahBY6ZtEqtryxkYtUsntT4q^ zM1lV{x%G!o2T$AvO=N7d`l`gyfbi;ukx%I_W&R*>vX& z^$jYej3G>0JxUL8k=Wgf`D-|5gHg@o_B=7ziLHR0vyX+UMIZA@5$Ez3z}v^nY16$a zdfd@i2a<>|-eMxyjblYFdU3H3^6L5`v5_-ZG`rb#!62WCyw-8_xnebBs&a>ksl)r z@(X=ySw}%1SznsTdjW0j*mNaDU25A@{aeQ`jP|@7?~k=v@8rUK3y*KJ9ielgjq%eS z>rN)8cTlB*v0)`W8(GLDVCeRYMXI@4y28mpjSaw$;l%_PQTDs$`vuKaw$?)JtFd=k z(SBtKWd5dgLBEw?6a(jA-I7y0(F$+3R|xM!d711koo!~5rZGMH*7t81fV`zr^KEFB z(aAF~w&}X;pURWS854}ozxXHq{~keFcPSlr3sZMXesfpL{{RDIW9MXH2ePoSYqIn5 uv+?i)`Iy+)`Pta!>+MDVm*C)JVe`Z1{}z5 \lambda \}; \Omega) \, d\lambda \approx \sum_{\lambda = 0}^{L-2} \PerA( \{ u > \lambda \}; \Omega) \, \Delta \lambda. + \label{eq:per_approx1} \end{equation} Note that we will later ignore the $\Delta \lambda$ difference, as we can just absorb it into the $\beta$ parameter of @@ -1156,24 +1162,31 @@ the approximation \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$. - -Since the final goal is to work with digital images, it makes sense to -discretize our domain $\Omega$ as a regular grid $\mathcal{G}$. Our -image is then reduced to a function $u : \mathcal{G} \to \mathcal{L}$. -\fixme{mathcal L is now two things.} Moreover, the level sets $\{ u > -\lambda\}$ will be functions taking the value of 0 or 1 on this grid, as -shown in Figure \fixme{ref}. +\emph{differentiable} curve $C$ in $\Omega$. Being a difference in the +$\rho$ parameter of our line discretization in Figure +\ref{fig:line_param}, the difference $\Delta \rho$ represents the +distance from one line to the next in a line family as shown in Figure +\ref{fig:line_family}. The difference $\Delta \phi$ is taken to be the +average of the distance to the two neighboring line families as shown in +Figure \ref{fig:line_neigh} + +In the discrete setting our domain $\Omega$ is discretized as a regular +grid $\mathcal{G}$. Our image is then reduced to a function $u : +\mathcal{G} \to \mathcal{L}$. \fixme{mathcal L is now two things.} +Moreover, the level sets $\{ u > \lambda\}$ will be functions taking the +value of 0 or 1 on this grid, as shown in Figure \fixme{ref}. The choice of our discrete set of lines $\mathcal{L}_D$ is important, as it will decide the accuracy of our approximation in -\eqref{eq:cauchy_crofton_approx1}. We will only consider lines going -through at least two points in our grid $\mathcal{G}$, and for now we will -consider a discretization which is uniform throughout the domain, -meaning that $\Delta \rho$ is constant for each line family, and that in -each grid point, there is a line from each family. \fixme{moar -explanation.} The -set of lines can then be represented by the neighborhood of a pixel as +\eqref{eq:cauchy_crofton_approx1}. We need some sensible restrictions on +the set $\mathcal{L}_D$ to simplify the further discussion. All lines +intersect at least two grid points, and from the periodicity of our grid +they thus intersect an infinite number of grid points. This puts some +restrictions on the angles we can choose. For each angle, we include all +possible lines of that family, meaning there are no grid points without +a line of that family intersecting it. + +The set of lines can then be represented by the neighborhood of a pixel as shown in Figure \ref{fig:line_neigh}. Extending the edges shown in the figure gives all lines going through the point considered. Figure \ref{fig:line_family} shows all lines of a given family, i.e.\ lines @@ -1195,7 +1208,7 @@ difficulty is finding the intersections $e \cap C$. The exact calculations of these points will not fit into our graph cut framework later, and thus for an edge $e$ we will consider only the question of ``did $e$ cross $C$ or not?'' This amounts to checking whether the -terminals of $e$ lie on each side of the curve $C$, and the +terminals of $e$ lie on different sides of the curve $C$, and the approximation is exact for zero or one intersection points, but will, as we see in Figure \ref{fig:curve_edge}, not be entirely correct when we have more. @@ -1215,19 +1228,21 @@ $x$ somewhere on the edge $e_{ab}$, we approximate the metric tensor by \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 -eigenvalues? sure, a bit, but it won't change consistency..} +edge. Recall that we have already done some spatial smoothing of the +structure tensor in \eqref{eq:s_def} corresponding to the +\emph{integration scale} $\rho$, and thus we expect the tensors $M(a)$ +and $M(b)$ to be similar for edges $e$ of reasonably short length. -\fixme{ - we must define what we mean by a reasonable line family. meaning - each line goes through more than one grid point. and there are no - grid points without a line through it -} +\fixme{really? componentwise? will that not mess up the +eigenvalues? sure, a bit, but it won't change consistency..} \begin{figure} \input{fig/area_proof} \end{figure} +We have now almost arrived at our final curve length approximation, but +we need a way to calculate the inter-line distance $\Delta \rho$ which +will be provided by the following lemma. \begin{lemma} For each family of lines given by an angle parameter $\phi$ in the regular grid of size $\delta$ we have the relation @@ -1254,8 +1269,8 @@ eigenvalues? sure, a bit, but it won't change consistency..} \Delta \rho &= \min_{(p\prime, q\prime)} \left\{ \left\langle \delta [p - p\prime, q - q\prime], \frac{e^\perp}{\norm{e^\perp}} \right\rangle \right\} \\ - &= \min \left\{\delta^2 \cdot \frac{t(p-p\prime) - s(q - - q\prime)}{\norm{e}} \right\}. + &= \min_{(p\prime, q\prime)} \left\{\delta^2 \cdot + \frac{t(p-p\prime) - s(q - q\prime)}{\norm{e}} \right\}. \end{aligned} \end{equation} Since $s$ and $t$ are coprime, there exists $a, b \in \mathbb{Z}$ @@ -1265,25 +1280,29 @@ eigenvalues? sure, a bit, but it won't change consistency..} \Delta \rho = \frac{\delta^2}{\norm{e}}. \end{equation} \end{proof} -Inserting -this \fixme{and the tensor approx} into the curve length approximation -of \fixme{ref} we obtain +Inserting $\Delta \rho = \delta^2 / \norm{e}$ and the tensor +approximation of \eqref{eq:tensor_approx} into the curve length +approximation of \eqref{eq:cauchy_crofton_approx1} we obtain \begin{equation} \abs{C}_M \approx \sum_{e \cap C} \frac{\det M(e) \norm{e}^2 \, \delta^2 \, \Delta\phi}{2 \left(e^T \cdot M(e) \cdot e\right)^{\sfrac{3}{2}}}, + \label{eq:cauchy_crofton_approx2} \end{equation} where the sum is over all edges crossing the curve an odd number of times. -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 + +The curve length we initially wanted to calculate was the perimeter +$\PerA(\{u > \lambda\}; \Omega)$ in \eqref{eq:per_approx1}. As this +curve is closed, we know that every edge intersecting it must have one +terminal in $\{ u > \lambda \}$ and the other outside. Thus we rewrite +the sum over $e \cap C$ such that \begin{equation} - \PerA(\{u > \lambda\}; \mathcal{G}) = \sum_{e_{ab}} \abs{ + \PerA(\{u > \lambda\}; \Omega) \approx \sum_{e_{ab}} \abs{ 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} + \label{eq:per_approx2} \end{equation} 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 @@ -1291,22 +1310,49 @@ 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...} +Thus we have arrived at our final discretization, which takes the form +\begin{gather} + F(u) = \sum_\lambda \sum_x F_x^\lambda(u_x^\lambda) + \beta \sum_\lambda + \sum_{(x, y)} F_{x,y}^\lambda(u_x^\lambda, u_y^\lambda) := + F^\lambda(u^\lambda), \\ + \begin{aligned} + F_x^\lambda(u_x^\lambda) &= \big(N_x(\lambda + 1) - + N_x(\lambda)\big) \cdot u_x^\lambda, \\ + F_{x,y}^\lambda(u_x^\lambda, u_y^\lambda) + &= \abs{u_x^\lambda - u_y^\lambda} \frac{\det M(e_{xy}) + \norm{e_{xy}}^2 \delta^2 \Delta \phi}{2 \left( e_{xy}^T \cdot + M(e_{xy}) \cdot e_{xy} \right)^{\sfrac{3}{2}}}. + \end{aligned} +\end{gather} + +If we minimize $F_\lambda$ to obtain $u^\lambda$ for each level +separately, it is obvious that we will also minimize the sum over all +$F_\lambda$. However, it is not guaranteed that the obtained thresholded +images $u^\lambda$ can be combined to make an output image $u$. They +were defined as $u^\lambda = \idfun_{u > \lambda}$, so we need them to +be monotonically decreasing (?) in increasing level values, i.e.\ +\begin{equation} + u_x^\lambda \geq u_x^\mu, \quad \forall \lambda \leq \mu, \quad + \forall x \in \mathcal{G}. +\end{equation} +Later we will present a graph cut algorithm that find the thresholded +images minimizing each level, \emph{while guaranteeing that they meet +this requirement.} + +\fixme{maybe with a $w_{xy}$ definition} \fixme{edges here are a bit different from edges later} \subsubsection{Consistency} Consistency relates to how well a solution to the continuous problem -fits in the discretized equation, in other words, how well the +fits in the discretized equation, in other words, whether 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 a midpoint rule -approximation of the integral. +\eqref{eq:fidelity_approx_1} is consistent. The sum is a midpoint rule +approximation of the integral. As the grid is refined and $\delta \to 0$ +the sum will converge to the integral. For the regularization term we will argue that for a differentiable curve $C$, the discretization of our domain $\Omega$ and the set of @@ -1317,90 +1363,102 @@ $\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}. -\begin{figure} - \input{fig/square_cons} -\end{figure} - -Consider a square centered around a grid point with side lengths -$\sqrt{\delta}$ as shown in Figure \ref{fig:square_cons}. 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 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 +If we consider the edges $e$ of each family separately, the curve length +approximation in \eqref{eq:cauchy_crofton_approx2} can be written \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. + \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} -\fixme{the flooring here is not right} -Further we know from Lemma \ref{lem:delta_rho} that for each line family -\begin{equation} - \delta^2 = \Delta \rho \norm{e}, -\end{equation} -and since the edge length $\norm{e}$ is bounded from below by $\delta$, -we have -\begin{equation} - \sup \Delta \rho \leq \frac{\delta^2}{\delta} = \delta \to 0. -\end{equation} +As described in the construction of this formula, there are four main +approximations used. Firstly there is the fact that we do not consider +the actual intersection points, but only whether an edge crosses the +curve or not. Secondly we have the tensor which is averaged as in +\eqref{eq:tensor_approx}. And then we have the discretizations of our +two line parameters $\nu$ and $\rho$. -Since all edges are inside our square, -we have $\norm{e} \leq \sqrt{2} \delta \to 0$. 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. +It is intuitive that if $\sup \norm{e} \to 0$, the number of times the +differentiable curve $C$ can cross a given edge decreases. We will not +prove convergence, but rather assume that the special cases where it +might not work, are negligible. -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. +Further, if $\sup \norm{e} \to 0$ it is obvious that the tensor average +in \eqref{eq:tensor_approx} converges to the tensor in the intersection +point. -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}. +For each $\phi$ parameter, our discretization in the $\rho$ dimension +can be regarded as a midpoint rule as shown in Figure +\ref{fig:line_midpoint}. Thus if $\sup \Delta \rho \to 0$, this part of +the discretization is fine. \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$. +The discretization in the $\phi$ dimension can also be regarded as a +version of the \emph{rectangle method}, although not the midpoint rule. +As shown in Figure \ref{fig:circ_rule}, the summand is evaluated on the +endpoint of the partition intervals $[\phi_k, \phi_{k+1}]$ and the +difference is taken to be $\Delta \phi = \phi_{k+1} - \phi_k$. Thus if +$\sup \Delta \phi \to 0$, this discretization is also consistent. \begin{figure} \input{fig/circ_rule} \end{figure} +To show that all these properties can be fulfilled, we look at a +particular neighborhood stencil construction. +Consider a square centered around a grid point with side lengths +$\sqrt{\delta}$ as shown in Figure \ref{fig:square_cons}. As $\delta$ +goes to zero, the size of this square will go to zero. Inside this +square we can fit a square of $n^2 = \lfloor 1 / \sqrt{\delta} \rfloor^2$ grid +points. This means that the number of grid points along the outer edge +of this square $n$ goes to infinity. + +\begin{figure} + \input{fig/square_cons} +\end{figure} + +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} for $n = +5$. 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{1/n}{n/2} = \arctan + \frac{2}{n^2} \to 0. +\end{equation} + +Further we see that the edge length will be bounded by half of the +diagonal of the square such that +\begin{equation} + \norm{e} \leq \sqrt{\delta / 2} \to 0. +\end{equation} +And finally we know from Lemma \ref{lem:delta_rho} that for each line family +$\delta^2 = \Delta \rho \norm{e}$ and the fact that $\norm{e} \geq +\delta$. Thus for the inter-line distance $\Delta \rho$ we have +\begin{equation} + \sup \Delta \rho = \sup \frac{\delta^2}{\norm{e}} \leq + \frac{\delta^2}{\delta} = \delta \to 0. +\end{equation} + 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}. +well-known, and consistent integral approximations, where the +summand converges to the integrand, and the differences $\Delta \phi$ +and $\Delta \rho$ go to zero. Thus 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 @@ -1408,69 +1466,9 @@ 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} -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} - -By combining the discretized fidelity and regularization terms and -ignoring the constant term $N_x(0)$ we obtain an energy function which -is decomposed into a sum over all the levels -\begin{equation} - E_v(u) = - \sum_{\lambda=0}^{L-2} \sum_x E^x_\lambda(u^\lambda_x) - + \beta \sum_{\lambda = 0}^{L-2} \sum_{(x, y)} E^{x,y}(u^\lambda_x, - u^\lambda_y) - =: \sum_{\lambda=0}^{L-2} F_\lambda(u^\lambda) - \label{eq:total_energy} -\end{equation} -\fixme{oops label} -where -\begin{align} - E^x_\lambda(u^\lambda_x) &= - \big( - N_x(\lambda + 1) - - N_x(\lambda) - \big) - \, u^\lambda_x - \label{eq:fidelity_energy} \\ - E^{x,y}(u^\lambda_x, u^\lambda_y) &= - w_{xy} \abs{u_x^\lambda - u_y^\lambda}. - \label{eq:neigh_energy} -\end{align} -If we minimize $F_\lambda$ to obtain $u^\lambda$ for each level -separately, it is obvious that we will also minimize the sum over all -$F_\lambda$. However, it is not guaranteed that the obtained thresholded -images $u^\lambda$ can be combined to make an output image $u$. They -were defined as $u^\lambda = \idfun_{u > \lambda}$, so we need them to -be monotonically decreasing (?) in increasing level values, i.e.\ -\begin{equation} - u_x^\lambda \geq u_x^\mu, \quad \forall \lambda \leq \mu, \quad - \forall x \in \mathcal{G}. -\end{equation} -In the following we will see two graph cut algorithms that find -thresholded images minimizing each level, \emph{while guaranteeing that -they meet this requirement.} +\fixme{Boop.} \section{Graph cut formulation} -- 2.47.3