% Chapter 4 \chapter{Performance Evaluation of the Body-SLAM} % Main chapter title \label{Chapter4} % For referencing the chapter elsewhere, use \ref{Chapter1} \lhead{Chapter 4. \emph{Performance Evaluation of the Body-SLAM}} % This is for the header on each page - perhaps a shortened title One of the major challenges in localization inside human body is performance evaluation. That's because any experiments inside human body is extremely difficult to operate. After the WCE is swallowed by the patient, we have limited control of the capsule and there is no effective way to verify their positions. Moreover, human subjects are different from one and another, we need a uniform platform for comparative performance evaluation. In this chapter, we talk about the validation of our proposed localization algorithm. Both the empirical results and emulation results are given to verify the performance of our algorithm. \section{Empirical Results of Motion Tracking} We need the motion model of the WCE for the simulation and the analysis of the temporal and spatial variation of the observed signals by body mounted sensors, design of algorithms for localization, and the emulation of the channel characteristics for performance evaluation and visualization of locations of WCEs. Unlike the movement of vehicles on roads or human beings in indoor areas, the movement of WCE inside the human body is very inconsistent and varies with the type of organs. While we cannot develop completely generalized models, we should be able to develop empirical movement models for these movements. Some pre-defined landmarks are detected by image processing techniques or identified by a GI specialist through the video source taken by WCE. These landmarks include entrance and exit of each of the four organs traversed by the endoscopy capsule: esophagus, stomach, small intestine and large intestine as well as tumors and bleeding identified in the tract. Figure~\ref{fig:landmark} shows pictures of landmarks inside the GI tract associated with pictures of duodenum, bleeding, tumor and cecum. \begin{figure}[t!] \centering \includegraphics[width=0.85 \textwidth]{./Figures/landmark.eps} \caption{Some typical landmarks for the WCE} \label{fig:landmark} \end{figure} As introduced in Chapter 3, if we know the motion information of the capsule by processing the endoscopic images, we can integrate this motion information with the RF measurements to enhance the localization accuracy. Conventionally, one simple approach of extracting the speed information of the capsule is to assume the capsule travels at a constant average speed and the approximate position of the capsule is calculated according to the time of travel away from some pre-defined land marks such like pylorus and ileocecal valve. Apparently, when using this approach, the further the capsule moves away from the land marks, the greater the error is. Especially after the video capsule has entered a few centimeters of the small intestine, the localization error will increase dramatically. This is mainly due to the high complicity level of the shape of the small intestine. The distribution of small intestine is like a curled snake with its length varies from 5m to 9m (the average value for human being is 7m) and the tendency of loops is highly indistinguishable. Besides, the intestinal motility is not consistent. Peristalsis may make the wireless capsule sometimes move quickly, sometimes slow or sometimes even stop and then progress with any combination of the movements above. To enhance the localization accuracy, a precise knowledge of how fast the capsule moves is urgently needed. In this section, we apply the speed estimation algorithm introduced in chapter 3 to the clinical endoscopic image database to model the speed of the capsule traveling through the small intestine. \subsection{Speed Estimation using PillCam COLON 2} PillCam COLON 2 is another product of Given Imaging, which specially aims at visualization of the colon mucosa and detecting polyps \cite{schoofs2006pillcam, spada2011pillcam}. After FDA Rejected PillCam Colon application in USA in 2008, Given Imaging developed the second-generation PillCam COLON 2 and received a CE Mark in 2009 and was commercially available in Europe in 2010. The size of PillCam COLON 2 is $11\times31$ mm and equipped with two identical image cameras on both ends as shown in Figure~\ref{fig:pillcolon}. As we mentioned in the previous chapters, performance evaluation of the speed estimation of WCE is extremely difficult. The double camera feature of the PillCam COLON 2 is a perfect tool for statistical validation. Since the images taken from both cameras are almost, after applying the speed estimation algorithm, the speed extracted from both cameras should be close with opposite direction. \begin{figure}[h] \centering \includegraphics[width=0.85 \textwidth]{./Figures/pillcolon.eps} \caption{PillCam COLON 2 with double cameras} \label{fig:pillcolon} \end{figure} The data set we used for this validation is from Umass Hospital. The video clip is consist of 2600 continuous image pairs. After applying the proposed motion tracking algorithms to each image pair, the result of the speed estimation (magnitude) is shown in Figure~\ref{fig:2cam}, where blue line represents the speed estimated from camera 1 and red line represents the speed estimated from camera 2. As we can see, the trend of both line match pretty well which indicate our proposed speed estimation is accurate. The plot shows that the capsule doesn't travel at a constant speed, it sometimes travels fast propelled by the intestinal motility and sometimes moves slowly even stops. This result confirms the assumption that the capsule translates at various speed. We also plotted the PDF and CDF of the speed estimation results from both cameras in Figure~\ref{fig:2camstat}, they also share almost identical distributions. \begin{sidewaysfigure} \includegraphics[width=\textwidth]{./Figures/2cam.eps} \caption{Speed estimation results from PillCam COLON 2 double cameras} \label{fig:2cam} \end{sidewaysfigure} \begin{figure}[h] \centering \includegraphics[width=0.85 \textwidth]{./Figures/2camstat.eps} \caption{Statistics of speed estimation using PillCam COLON 2 double cameras } \label{fig:2camstat} \end{figure} \subsection{Statistical Speed Modeling} \begin{figure}[b!] \begin{center} \begin{tabular}{c} \scalebox{0.8}{\includegraphics[]{./Figures/chap4pdf.eps}} \end{tabular} \caption{PDF of the speed estimation from different individuals} \label{fig:chap4pdf} \end{center} \end{figure} \begin{figure}[b!] \begin{center} \begin{tabular}{c} \scalebox{0.8}{\includegraphics[]{./Figures/chap4cdf.eps}} \end{tabular} \caption{CDF of the speed estimation from different individuals} \label{fig:chap4cdf} \end{center} \end{figure} We also tested our algorithm with the clinical data from different individuals using OMOM \cite{li2008omom} capsule. Figure~\ref{fig:speedexample} shows a sequence of 60 endoscopic frames. After applying our speed estimation algorithm, a plot of the corresponding speed is given underneath. Since we do not have precise control of the capsule, we are not able to perform quantitative evaluation, but we can examine the images manually by naked eye. As shown in Figure~\ref{fig:speedexample}, the whole image sequence can be divided into 4 sections marked by A, B, C, and D. It can be seen that during section A and C, the scene almost stays still which indicates a slow motion of the capsule, while in section B and D, the capsule moves faster. The trend of the corresponding speed estimation plot matches this observation. To further validate our algorithm, we compared the statistical results of clinical data (4 short video clips and 1 long video clip) from 5 different patients. The results are shown in Figure~\ref{fig:chap4pdf} and Figure~\ref{fig:chap4cdf}. It can be seen although the video clips are from different individuals, after applying our speed estimation algorithm, the estimated speed shares very similar distributions in term of probability density function (PDF) and cumulative distribution function (CDF). Some typical speed estimation pattern are shown in Figure~\ref{fig:speed1} and Figure~\ref{fig:speed2}. \begin{sidewaysfigure} \includegraphics[width=\textwidth]{./Figures/speedexample.eps} \caption{Speed estimation results of a sequence of real endoscopic images} \label{fig:speedexample} \end{sidewaysfigure} \begin{figure}[t!] \centering \includegraphics[width=0.80 \textwidth]{./Figures/speed1.eps} \caption{A typical speed pattern of moving fast } \label{fig:speed1} \end{figure} \begin{figure}[t!] \centering \includegraphics[width=0.80 \textwidth]{./Figures/speed2.eps} \caption{A typical speed pattern of moving slow } \label{fig:speed2} \end{figure} \clearpage %---------------------------------------------------------------------------------------- \section{Design of Testbed for Performance Evaluation} %---------------------------------------------------------------------------------------- As we mentioned before, one of the major challenges of implementing any capsule localization algorithms when it comes inside the human body is validation. That's because we have limited control of the capsule after it is swallowed by the patient so we could not verify the performance of the algorithms \cite{pahlavan2012rf, france2005layered}. Besides, carrying out experiments on the real human beings is extremely costly and restricted by law. Thus, the only way to verify the performance of our localization algorithm is to build up an emulation test bed. Similar idea was applied to wireless wide area network (WWAN) and wireless local area network (WLAN) deployments. In WWAN and WLAN, instead of doing real measurements, researchers model the characteristic of the RF signal under a certain scenario by creating emulation testbed. Algorithms and protocols can be imported into the testbed to test and compare their performances. In case of WCE localization, since experiments inside human body is impossible, we need to design a testbed for performance evaluation of the proposed Body-SLAM algorithm. In this section, we describe the details how to establish a testbed for localization inside human body. Since the only two data sources we get from the WCE are images and RF signals used for transmitting these images, the testbed should include two major components: visual component and RF component. The overall flow chart of designing this testbed is illustrated in Figure~\ref{fig:testbed_chart}. \begin{figure}[h] \centering \includegraphics[width=1 \textwidth]{./Figures/testbed_chart.eps} \caption{Design of emulation testbed for quantitative performance evaluation } \label{fig:testbed_chart} \end{figure} \clearpage \subsection{Visual Component} To establish the visual component of the testbed, we need to create a visual environment that is able to produce artificial images that look the same as the real endoscopic images taken by the WCE while we have fully control of the motion status of the camera. \subsubsection{Physical testbed} Our first attempt to emulates the digestive tract is to build a physical hardware. This hardware was created by bending and twisting a 1.5 meter long 3 centimeter diametric Polyvinyl Chloride (PVC) tube. The outer surface of the tube was painted with flesh color to give it a more realistic interior look. A layer of tinfoil paper was covered around the tube to prevent outer light from transmitted into the tube and also preventing the light of camera from escaping outside. To simulate the transition of the endoscopic capsule, we inserted a wired endoscopy camera equipped with four LED lights (as shown in Figure~\ref{fig:physicalbed} (a)) into the tube with a constant step of 0.03 cm and took a picture after each step. In the endoscopic pictures, the tube surface that lied physically closer to the camera had a brighter intensity value. The brightness decreased as the distance increased and finally at the far end of the tube, which was corresponding to the center of the endoscopic pictures, a black hole would form. If the camera was about to tilt, the black hole would move toward to the edge of the endoscopic pictures. Figure~\ref{fig:physicalbed} (c) indicates a test pictures take from inside the physical testbed. We can see that it looks similar with real pictures taken from the small intestine. \begin{figure}[h] \centering \includegraphics[width=1.0 \textwidth]{./Figures/physicalbed.eps} \caption{A physical visual model for the small intestine (a) wired endoscopic camera (b) appearance of the physical model (c) pictures taken from inside the physical model} \label{fig:physicalbed} \end{figure} One big advantage of the physical testbed is that we can put it into water to simulate the liquid environment inside the small intestine. Also we could insert a antenna inside the tube to emulate RF signal emitted by the endoscopic camera. However, there are some fundamental drawbacks with this physical model: \begin{itemize} \item The major drawback of this physical model was the restriction in camera control. After the camera was inserted into the tube, we can only control the speed of the camera by pulling the wire connected to of the camera. However, we don't have full control of other movements of the camera such as tilt and rotation. \item The PVC plastic tube is not soft enough to bend into the complicated shape (especially the sharp turn) of the small intestine. Besides, the endoscopic camera is longer than the actual size of the endoscopic capsule, this would make smooth transition of the camera challeging since it sometimes get stuck somewhere in the tube. \item Adding texture to the interior of the PVC tube is difficult. We meed map the actual texture of inside the digestive tract to the interior to the physical model to make it looks more similar to the real endoscopic images. \end{itemize} Due to the drawbacks stated above, an alternative way to emulate the inside environment of the small intestine was to build a virtual testbed which will be introduced in the upcoming subsection. \subsubsection{Virtual testbed} The major reason why we go for a virtual visual testbed is that it gives full control of the camera's motion. This is critical in validating the performance of our motion tracking algorithm. Besides, we can easily change the shape of the testbed and attach any color and texture to the testbed to make it looks more realistic. To verify the feasibility of the virtual testbed, we compared the images generated from the virtual testbed and physical testbed and make sure they share similar characteristics. The first step is to map the physical model to the virtual 3D space. To do so, we measured the $x$, $y$, and $z$ coordinates of the pipe every 10cm and imported those coordinates into Matlab (as shown in Figure~\ref{fig:mappingphysical}). After linking those 3D points, we got the path of the physical testbed. This path is used for generating a cylinder the same size as the physical pipe as shown in Figure~\ref{fig:3dcylinder}. We attached the texture extracted from the real endoscopic images to the interior of this cylinder to give a realistic look as the small intestine. Using Matlab graphic toolbox, we placed a camera view point and moved it along this path and meanwhile taking pictures. An light source was placed behind the camera view point to simulate the illumination system. Some sample images generated by this virtual environment is shown in Figure~\ref{fig:emulateimage}. As we can see, the images generated from the virtual environment shares the same features of the images from the physical testbed, therefore, it can be used as an alternative for creating the visual component of the testbed. However, the cylinder shown in Figure~\ref{fig:3dcylinder} is too short and too simple to represent the real small intestine. We need a more realistic and complicated virual model of the digestive tract. \begin{figure}[h] \centering \includegraphics[width=0.7 \textwidth]{./Figures/mappingphysical.eps} \caption{Mapping the physical testbed into virtual 3D space} \label{fig:mappingphysical} \end{figure} \clearpage \begin{figure}[h] \centering \includegraphics[width=0.85 \textwidth]{./Figures/3dcylinder.eps} \caption{3D testbed} \label{fig:3dcylinder} \end{figure} \begin{figure}[h] \centering \includegraphics[width=0.9 \textwidth]{./Figures/emulateimage.eps} \caption{Emulated endoscopic images from virtual visual testbed} \label{fig:emulateimage} \end{figure} To create a more realistic scenario, we generated a cylindrical tube with the same size and shape of the small intestine. The actual path of this virtual test bed was extracted from a an anatomical 3D model of the small intestine shown in Figure~\ref{fig:emulation} by using some 3D image processing techniques. For the large intestine, since it already has a very clear pattern which looks like a big hook, we applied 3D skeletonization technique \cite{palagyi19983d} to extract the path of it. As for the small intestine, since the shape of the small intestine is much more complicated (the trend of the small intestine can be hardly recognized by human eyes), we developed an element sliding technique to trace the path. The basic idea behind this technique is to define an element shape (ES) with its radius automatically adjustable to the radius of the small intestine. This ES is propelled forward by a factor associated proportional to the average distance between the vertices within certain range and the physical center of the ES. As the ES goes along the small intestine, the position of its physical center is recorded and this will give us a clear path of the small intestine. The path extracted from the 3D model is shown on the bottom of Figure~\ref{fig:map_generation}. As illustrated on the top of Fig.~\ref{fig:emulation} (c), the virtual test bed shared the same topology with the real small intestine which is intertwined back and forth. To make the interior of the testbed look more realistic, we extracted color and texture from the real endoscopic images and mapped it onto the interior surface of the tube. Similar emulation set up can be found in \cite{france2005layered, seshamani2006real, szczypinski2009model}. \begin{figure}[h] \centering \includegraphics[width=0.6 \textwidth]{./Figures/map_generation.eps} \caption{3D path generation from a 3D GI tract model} \label{fig:map_generation} \end{figure} \clearpage \begin{figure}[h] \centering \includegraphics[width=0.99 \textwidth]{./Figures/emulation.eps} \caption{Emulation testbed set up} \label{fig:emulation} \end{figure} \clearpage \subsection{RF Component} Research in localization inside of the human body has reached a bottleneck due to the difficulty of conducting measurements inside the human body. Two major limitations causing difficulty are the existence of a nonhomogeneous environment and difficulties in antenna implantation inside the human body for experimental purposes. Previously, the efficiency of different simulations around a human body was assessed and theoretically analyzed \cite{liu2013wideband}. Phantoms with emulated tissues were used to validate surface measurements of a human body \cite{swar2012accuracy, chen2013comparison, zhang2013rf}. However, the simulation analysis of the small intestine remains to be done. \subsubsection{RF propagation emulation using FDTD } The RF propagating simulation was carried out using SEMCAD X. SEMCAD X is a full-wave electromagnetic simulation platform based on the Finite Difference Time Domain (FDTD) method. This software provides an abundant library of anatomical non-homogeneous human body models for waveform transmission problems. The models can be used to simulate wave propagation in and around the human body. Additionally, this software runs faster than other electromagnetic simulation platforms due to its algorithm optimization. The FDTD method was first introduced by Yee in 1966. It solves Maxwell curl equations in the time domain. The FDTD method has been proven to be an effective simulation method in terms of the accuracy of obtaining electrical and magnetic field parameters. It has been widely used in indoor localization and microwave simulations \cite{takizawa2008channel, lim2013investigation}. In this section, we present the simulation results of the waveform propagation in both homogeneous and non-homogeneous tissues. By comparing simulation results and empirical measurements, we show that the SEMCAD X platform is a reliable tool for waveform transmission. \begin{figure}[h] \centering \includegraphics[width=0.99 \textwidth]{./Figures/RFemulation.eps} \caption{Emulation testbed set up} \label{fig:RFemulation} \end{figure} \begin{figure}[h] \centering \includegraphics[width=0.99 \textwidth]{./Figures/RFresult.eps} \caption{Emulation testbed set up} \label{fig:RFresult} \end{figure} \subsubsection{RSS vs ToA} To measure the statistics of the temporal and spatial behavior of the signal, we used computational techniques for direct solution of Maxwell's equations for extensive measurements of wide-band characteristics of RF signals inside the human body. We have used these techniques to find the wide-band received signal at body mounted sensors and other WCEs when a waveform is transmitted from a VCE in a specific location inside the GI tract. Then we extracted the RSS, TOA and DOA of the received wide-band signal by other capsules or by body-mounted sensors to model them for use in RF localization algorithm design. For RSS based localization techniques, we need a path-loss model that relates the statistical behavior of the power to the distance to calculate the estimated distance of the capsule from the body-mounted sensors used as the reference point. For TOA-based localization algorithms, we need a model for the multipath arrival and the relationship between distance measurement error and the bandwidth of the system to account for the measurement noise and various biases in distance estimation from TOA measurements. The current body of literature only provides a few path-loss models for implant communication applications. Modeling of the effects of multipath on TOA- and DOA-based localization is at its infancy and new models for these purposes are needed. \section{Performance Evaluation for Body-SLAM} \clearpage \begin{figure}[h] \centering \includegraphics[width=0.99 \textwidth]{./Figures/motionexample.eps} \caption{Typical movements detected by the proposed motion tracking algorithm} \label{fig:motionresult} \end{figure} \clearpage \begin{figure}[h] \centering \includegraphics[width=0.9 \textwidth]{./Figures/Motiontrackingresult.eps} \caption{Result of the motion tracking compared with ground truth} \label{fig:Motiontrackingresult} \end{figure} \begin{figure}[h] \centering \includegraphics[width=0.9 \textwidth]{./Figures/trackingresult.eps} \caption{Result of the motion tracking compared with ground truth} \label{fig:trackingresult} \end{figure} \begin{figure}[h] \centering \subfigure[Localization results of different algorithms]{ \includegraphics[scale =0.65] {./Figures/patha.eps} %\label{fig:Fig2a} } \subfigure[Evolution of localizatoin error as the capsule moves ]{ \includegraphics[scale =0.65] {./Figures/pathb.eps} %\label{fig:Fig2b} } \caption{Localization results of different algorithms and performance evaluation} \label{fig:result} \end{figure} \clearpage Fig.~\ref{fig:motionresult} shows some typical movements that were detected by the proposed motion tracking algorithm. Fig.~\ref{fig:motionresult} (a) shows a scenario that the capsule moves forward. It can be seen that the displacements of FPs are originally pointed to the outer ring in cylindrical image domain while stacked vertically with their orientation pointing upward when mapped into the unrolled image domain. The magnitude of displacements in the unrolled domain reflects the speed of moving of the capsule. Similarly, if the capsule moves backward (shown in Fig.~\ref{fig:motionresult} (b)), motion vectors in the cylindrical image domain are pointed to the center and correspondingly, when mapped into the unrolled image domain, they are vertically pointing downward. Fig.~\ref{fig:motionresult}(c) shows a case when the capsule rotated, motion vectors in the cylindrical image domain formed a circle around the focal axis and the corresponding motion vectors in the unrolled domain were horizontally pointing to the right indicating a clockwise rotation. The magnitude of $\triangle x'$ reveals the rotation angle. Finally in Fig.~\ref{fig:motionresult}(d), the capsule tilted toward $\phi$ during the transition, thus the magnitudes of the motion vectors in this area were smaller than the others. The difference in magnitude indicates the degree that the capsule tilts. The results of motion tracking using images, RF localization and the proposed hybrid localization are given in Fig.~\ref{fig:result}. It can be seen from Fig.~\ref{fig:result} (a) that the results of RF localization (represented in green triangles) are scattered all around the small intestine with relative large error (6.8 cm on average). This is because the RF channel suffers shadow fading and non-homogeneity of the body tissues. However, the good part of RF localization is its independent characteristics. Each measurement is an isolated procedure which cannot be affected by the previous measurements. Therefore, the localization error would not accumulate as the capsule moves along (shown in Fig.~\ref{fig:result}(b)). The result of the camera motion tracking algorithm is shown in gray line in Fig.~\ref{fig:result} (a). It shows that when using this algorithm alone, the estimated positions are continuous and the overall trend of the trajectory matches the ground truth path (shown in black line in Fig.~\ref{fig:result} (a)) of the small intestine. However, as the capsule moves along, the localization error increases. It can be seen from Fig.~\ref{fig:result} (b), after about 15 steps, the localization errors of motion tracking reaches almost the same level of RF localization and it keeps growing until explode (up to 70 cm). This is due to the accumulative characteristic of the motion tracking algorithm. In the motion tracking algorithm, the next motion state is highly dependent on the current motion state plus the current transition information, which is estimated from the displacements of FPs between consecutive image frames. If an error happens during the estimation of this transition matrix, even with very little magnitude, the error would accumulate and the overall error would keep increasing. This is what we call ``drifting effect'' in Robotics. Thus, we cannot judge the performance of a motion tracking algorithm based on the overall accuracy. Instead, we should evaluate the performance of an algorithm by measuring the accuracy of estimation within each step. Statistics in Table I show that our proposed algorithm worked accurately in calculating the transition speed of the capsule and direction angles for each step. The average distance error was 0.04 cm which was way below the unit step size, and the average rotation error was $1.8^o$, which was also very small compared with average rotation angle of $7.8^o$. The estimation of tilt was not as accurate because the differences in motion vectors were not always obvious and the range of smaller motion vectors may cover up to more than 45 degree of $x'$ axis. \begin{table}[h] \renewcommand{\arraystretch}{1.3} \caption{Motion tracking performance for each step} \label{table1} \centering \begin{tabular}{c c c c} \hline\hline \bfseries & average estimates & average errors \\ \hline Transition speed & 0.41 cm/s & 0.04cm/s \\ \hline pitch $\alpha$ & $6.73^o$ & $1.69^o$ \\ \hline yaw $\beta$ & $7.28^o$ & $1.41^o$ \\ \hline roll $\gamma$ & $7.81^o$ & $1.23^o$ \\ \hline\hline \end{tabular} \end{table} Finally we evaluated the performance of the proposed hybrid localization algorithm. The results are shown in purple line in Fig.~\ref{fig:result} (a). It shows after the combination of motion tracking and RF signals, the hybrid localization is able to achieve more continuous position estimation of the capsule and the reconstructed path that the capsule has traveled matches the ground truth path of the small intestine very well. From Fig.~\ref{fig:result} (b) we can see that, compared with the existing RSS based localization system, the localization error of hybrid localization stays stable at a very low level (2.3 cm on average) and the error would not increase as the capsule moves along. The error distribution and CDF plot of the above three algorithms are given in Fig.~\ref{fig:fitting} and Fig.~\ref{fig:CDF}, respectively. From both statistical plots we can see that the localization accuracy of the proposed hybrid localization is much better than the traditional RSS based RF localization. Since the diameter of small intestine is approximately 2.5-3 cm, the localization accuracy that the proposed hybrid localization provides meets the requirement of WCE application. \begin{figure}[h] \begin{center} \begin{tabular}{c} \scalebox{0.6}{\includegraphics[]{./Figures/histgram.eps}} \end{tabular} \caption{Error distributions of different algorithms} \label{fig:fitting} \end{center} \end{figure} \begin{figure}[h] \begin{center} \begin{tabular}{c} \scalebox{0.6}{\includegraphics[]{./Figures/CDF.eps}} \end{tabular} \caption{Performance evaluation by CDF plot of different algorithms} \label{fig:CDF} \end{center} \end{figure} \clearpage