Magnetic localization and orientation of the capsule endoscope based on a random complex algorithm

Introduction

With the development of science and technology, capsule endoscopy is becoming a preferred method for examination of the gastrointestinal tract, especially for the diagnosis of intestinal disease.¹ The movement of the capsule in the gastrointestinal tract of human body depends on gastrointestinal peristalsis, so it is important for the doctor to acquire precise positioning information of the capsule to observe some specific areas of the tissues. Currently, a widely used positioning technique is the magnetic method, which detects the change of the magnetic intensity generated by a magnet attached to the capsule. The magnet signal are changes as a function of the static magnetic field and is not affected by the human body, so this positioning method can obtain high positioning accuracy. Also, it can directly determine the parameters for the position and direction of the capsule, for real-time location tracking. Based on the model of magnetic field positioning, researchers have proposed many positioning methods for the localization and orientation of the magnet.^2–11 For instance, Golden and Silverstein have developed a medical tube that can be positioned in the body of patients. This medical tube can be located by a detection instrument, based on the magnetic intensity generated by the magnets inside the tube. The detection instrument moves around the body until the maximum magnetic intensity is detected, and then, the position of the magnet is calculated. However, this method cannot determine the direction of the magnet and has no real-time tracking system.² Prakash and Spelman proposed a method for localizing a single magnetic dipole has been implemented in vitro using a magnetic marker. This uses an eight fluxgate magnetic sensor to measure the magnetic intensity of the magnetic marker, where the Newton algorithm is applied as the positioning algorithm to calculate the position and direction of the target, but the positioning precision of this method is not very high.³ Yang et al used swarm intelligence algorithms, including genetic algorithms and particle swarm algorithms, to optimize the function of the magnetic positioning model. Their results showed that particle swarm optimization was more accurate to meet the requirement of localization. But for real-time tracking of the magnet, the algorithm is complex, and the speed of the algorithm did not meet the requirement for localization.⁷ Hu et al put forward a new localization algorithm. First, they used an improved linear algorithm to obtain the localization parameters, by finding the eigenvector corresponding to the minimum eigenvalue of the objective matrix. Then, these parameters were used as the initial guess values for the positioning parameters of a nonlinear location algorithm so that the algorithm had better robustness and more precise positioning results.¹⁰

To find a more efficient algorithm, a hybrid algorithm combining different algorithms might be a suitable method to meet the need for high positioning precision and fast speed. Based on the magnetic dipole model, some nonlinear localization methods have been tested, such as Powell’s, Downhill Simplex, DIRECT, multilevel coordinate search, and the Levenberg–Marquardt (LM) algorithm. Hu et al concluded that the LM algorithm is better than other nonlinear algorithms.¹² However, the LM algorithm easily gets into local optimality, so when the positioning range becomes larger, it has insufficient stability and antinoise ability. Therefore, we tested some hybrid methods and obtained better results. In this paper, we put forward a new nonlinear positioning algorithm based on the random complex method. In terms of accuracy and stability, for the three-dimensional position parameters and two-dimensional direction optimization calculation, the random complex algorithm (RCA) is superior to the LM algorithm and other algorithms because of its greater error level of the initial guess of magnet location and “denoising” capacity.

The organization of this paper is as follows: In the following section, we present a magnetic positioning system for the capsule endoscope. After this, we present the nonlinear magnetic positioning algorithm. Then, we present the performance and evaluation, followed by our conclusions.

Magnetic positioning structure of the capsule endoscope

As shown in Figure 1, the capsule endoscope has an enclosed thin, annular magnetic tube that builds the magnetic field and which does not take up very much of the internal space.¹²

Figure 1 Capsule endoscope with magnetic tube. Abbreviation: LED, light-emitting diode.

To detect the capsule endoscope in the body, a magnetic sensor array (Figure 2), which is situated outside of the human body, is designed to measure the magnetic field strength generated by the magnetic tube as the capsule moves inside the human body.

Figure 2 Axially magnetized magnetic sets. Abbreviation: GI, gastrointestinal.

Obviously, the signal received by the magnetic field sensor array is related to the magnet tube position and direction with respect to the sensors. After sampling the sensor data, the position and direction parameters of the tube can be computed by the corresponding algorithm.

Nonlinear magnetic positioning algorithm

Model description

When a capsule moves in the gastrointestinal tract of human body, the position and direction of the capsule change. Therefore, we define a fixed coordinate system (as shown in Figure 3), and under the coordinate system, the magnet’s position is represented by (a,b,c)^T, and the magnet orientation is represented by H₀ = (m,n,p)^T.

Figure 3 Axial circular magnet (magnetic dipole) model. Notes: (a, b, c) is the magnet position; (X1, Y1, Z1) is a spatial point; H0 is the normalized vector; R1 is the distance between the magnet and the spatial point.

Assume that there are N sensors, with lth sensor located at (x_l,y_l,z_l)^T (serial number l, l=1, 2, …, N). We denote three unit coordinate vectors as i, j, and k corresponding to the axes x, y, and z respectively. The magnetic flux density at the lth sensor location can be represented by:

where B_lx, B_ly, and B_lz are the three orthogonal components of B_l; N is the total number of sensors; μ_r is the relative permeability (μ_r ≈ 1 in the air); μ₀ is the vacuum permeability (μ₀ = 4π ×10^–7T · m/A); M_T is the constant (related to the volume and intensity of magnetization) that characterizes the magnetic field intensity of magnets; the vectors P_l connecting the lth sensor and the magnet can be represented by (x_l – a,y_l – b,z_l – c)^T; and R_l is the module of P_l, namely, . The H₀ vector is characterizing the direction of the magnetic field of magnets, and we can add the constraints:

Expanding Equation 1, we have:

If we detect B_lx, B_ly, and B_lz (l ≥ 2), by using Equations 2–5, the location parameter (a,b,c)^T and direction parameter (m,n,p)^T can be determined.

According to the magnetic positioning model, there are five unknown parameters that must be solved, and the number of sensors needs to be N ≥2. But due to the presence of noise, the solution is not unique. We define a target error function (E) as follows:

for which

and

This is a nonlinear least squares problem, so the positioning problem becomes a nonlinear optimization problem. We find (a,b,c)^T and (m,n,p)^T to get the minimum error of the target through the optimization algorithm, namely:

In order to measure the effectiveness of the algorithm, positioning and orientation errors are defined as:

and

where (a_t b_t c_t m_t n_t p_t) and (a_s b_s c_s m_s n_s p_s) represent the setting and calculated parameters of the position and orientation.

Random complex algorithm

For the localization of the capsule endoscope, the accuracy and execution time are very important, and the nonlinear algorithm should be of high speed and precision. There are some widely used nonlinear algorithms, such as Powell’s, downhill, simplex, DIRECT, multilevel coordinate search, and the LM algorithm. We tried these algorithms and found some defects with the efficiency, so a nonlinear optimization algorithm, RCA, is introduced.

RCA was proposed by Andersson on the basis of the complex method.¹³ In this method, the complex is constituted in the constrained space; then the function values of the complex vertices are compared one by one so that the worst vertex will be replaced by a new vertex whose function values are improved and satisfy the constraints. Repeating this process, the result gradually approaches the most accurate one. The step of computing the optimization of RCA is described in Figure 4.

Figure 4 The calculation steps for the random complex algorithm (RCA).

Performance evaluation

In a real system, there will be noise due to the influences of the human body and the environmental factors. So the nonlinear optimization algorithms were tested for their ability to denoise and with the initial setting range of the positioning parameters. In this section, we compare RCA with the LM algorithm in terms of positioning error, direction error, and the execution time of the algorithm. Also, the effects of initial setting errors are used to test the stability of each RCA and LM algorithm.

Although it requires at least five sensors to solve a function for the five unknown positioning and orientation parameters, the greater the number of sensors, the higher is the positioning accuracy. The simulation is based on the layout for 16 three-dimensional magnetic sensors evenly arranged on the 240 × 240 mm square area X-Y plane, as shown in Figure 5.⁹

Figure 5 Arrangement of sensors.

In the simulation, the RCA and the LM algorithms are compared for algorithm characteristics, based on the nonlinear magnetic positioning model.

Tolerance of the initial guess of the parameters and stability of the algorithm

The nonlinear optimization algorithms usually require an initial guess of the parameters, or their bounds, to search for the optimal value. If the initial parameters (or bounds) are chosen with large error, the algorithms may fail to give the correct (global optimization) solution because there might be many local optima. Therefore, the chosen optimization algorithm should have large tolerance for the initial guess of the parameters.

For all the test vectors, the vector Vr = [–0.05, –0.00, 0.97, 0.00, –1.00, 0.00] is the most representative when the error levels of the initial location guess is 100 cm. The simulation results of RCA and the LM algorithm are shown in Figure 6.

Figure 6 Position and orientation errors for the error levels of the initial guess of location. Abbreviation: LM, Levenberg–Marquart.

For Figure 6, we observe that if the location error is 5 mm and direction error is 5%, the LM algorithm lapses when the initial guess of location is 15 cm, and RCA lapses when the initial guess of location is 36 cm.

For all the 32 test vectors, when the initial guess of localization is in the range of 10–100 cm, if the location error is 5 mm and direction error is 5%, the simulation results of the proportion of successful points of the RCA and the LM algorithm are shown in Figure 7.

Figure 7 Proportion of effective points for the different initial errors of position. Abbreviation: RCA, random complex algorithm.

The simulation results show that when the limit for the initial guess of localization is 10 cm for the RCA and the LM algorithm, all test points are successful. But when the limit for the initial guess of localization is extended to 30 cm, 37.5% of test points of the LM algorithm lapse, while the RCA can still successfully and accurately calculate the optimal position and direction. So the tolerance of the initial guess for RCA is higher than that for the LM algorithm. In Figure 9, with the increase in error level of the initial guess for magnet location, the proportion of successful points in the RCA and the LM algorithm will decrease, but the RCA is better than the LM algorithm. Thus, the stability of the RCA is better than that of the LM algorithm.

Denoise capacity

The algorithm and system implementation should be robust with regard to the noise in the sensor data. In a practical system, there is always some noise due to the influences of the human body and the environment. In this section, we present the simulation results for the denoising ability of the LM algorithm and RCA, and the results obtained by a real sensor array system with sixteen three-axis Hall effect sensor.

For all the 32 test vectors, when the initial guess of localization is 10 cm, under different noise levels (0.1–1,000, where 1,000 is approximately 40% full sensing range) of random noises, the average and maximum localization and orientation errors of the LM algorithm and RCA are shown in Table 1.

Table 1 The average and maximum of localization and orientation errors Note: The values with asterisks represent the better values of two algorithms. Abbreviations: RCA, random complex algorithm; LM, Levenberg–Marquart.

According to Table 1, when the noise level is from 0.1 to 1,000, the RCA has smaller fluctuation, and the average value of localization and orientation error of the RCA is smaller than that of the LM algorithm.

For the real vectors Vr1=[0.0853, –0.0956, 0.0520, 0.9183, 0.3958, 0.0000] and Vr2=[–0.815, 0.070, 0.097, 0.2169, 0.9762, 0.0000], when the initial guess of localization is 10 cm and the noise level, dl, is in the range of 0 to 1,000, the simulation results of the RCA and the LM algorithm are shown in Figures 8 and 9.

Figure 8 Position and orientation errors via noise level; vector Vr1. Abbreviation: LM, Levenberg–Marquart.

Figure 9 Position and orientation errors via noise level; vector Vr2. Abbreviation: LM, Levenberg–Marquart.

From the simulation results, the average of the position error for the RCA is 0.76 mm, and the maximum value is 4.60 mm; the mean value of the orientation error is 2.22%, and the maximum value is 12.99%. The average of the position error for the LM algorithm is 592.59 mm, and the maximum value is 4.34×10⁴ mm; the mean value of the orientation error is 9.75%, and the maximum value is 236.93%.

From the simulation results, the average of the position error for RCA is 4.91 mm, and the maximum value is 34.50 mm; the mean value of the orientation error is 7.32%, and the maximum value is 33.74%. The average of the position error for the LM algorithm is 11.82 mm, and the maximum value is 55.92 mm; the mean value of the orientation error is 23.09%, and the maximum value is 168.41%.

From the above figure, when the noise level dl ranges from 0 to 1,000, the condition of failure may occur for the LM algorithm but does not happen for the RCA; comparing with the LM algorithm, the noise immunity of the RCA is stronger.

Real experiment and comparison with testing results

We built an actual experimental system, which consists of magnetic sensors, amplifiers, an analog-to-digital (A/D) converter, and a computer. The 16 magnetic sensors (Figure 7) are made of three-axis Hall sensors. In the system, the magnetic sensors receive the magnetic signals and convert them to electrical signals. The amplifiers amplify (or adjust) the signal magnitude until suitable to the range for A/D conversion. Then, the computer selects the particular signal channel and samples the signal using a 12-bit A/D converter (we tried a 16-channel, ISA bus data acquisition card [PCL-818L; Advantech Co, Ltd, Taipei, Taiwan]). In the experimental process, 32 positions of magnet are selected and the corresponding data of magnetic induction intensities in each position is obtained. Based on the data, the RCA compares with the LM algorithm in terms of the position and direction error, and the execution time of the algorithm, and the result is shown in Figure 10.

Figure 10 Comparison for the position and direction error and execution time of real data. Abbreviations: LMmeanP, the average value of position error of LM algorithm; RCAmeanP, the average value of position error of RCA algorithm; LMmeanO, (the average value of direction error of LM algorithm; RCAmeanO, the average value of direction error of RCA algorithm; LMmeanT, the average value of execution time of LM algorithm; RCAmeanT, the average value of execution time of RCA algorithm; RCA, random complex algorithm.

In Figure 10, in each position among 32 positions, when the algorithms (RCA and LM) were run, we obtained the average values for positioning and direction errors and the running time of the algorithms, with error bars (95% confidence interval) for all of the mean values. The error bars specify the size of the uncertainty of the measurement data. For the LM algorithm, the position error is less than 12.51 mm, and the average value is 4.86 mm; the direction error is less than 10.56%, and the average value is 5.71%; and the execution time of the algorithm is less than 0.24 seconds, and the average value is 0.22 seconds. Alternately, for the RCA, the position error is less than 8.34 mm, and the average value is 3.70 mm; the direction error is less than 10.80%, and the average value is 3.27%; and the execution time of the algorithm is less than 0.21seconds, and the average value is 0.20 seconds. Obviously, for the 32 positions in the actual measured data, the RCA performs better than the LM algorithm for the position, the direction, and the execution time.

Summary

As mentioned above, the positioning and tracking technology of the capsule is the key technology for capsule endoscopy. To realize stable and accurate localization, we must find appropriate algorithms. Based on the magnetic positioning model of the capsule endoscope with an embedded permanent magnet, we propose a new localization algorithm – the RCA. Simulation results show that the RCA is better than the LM algorithm with regard to the stability, the initial guess setting range, and noise immunity. We have tested and compared actual experimental data, based on an actual test system, and find that the RCA is better than the LM algorithm with regard to the position accuracy and the execution time of the algorithm. For the actual localization system, we can design a hybrid algorithm combining the RCA nonlinear algorithm with other algorithms, by first using other algorithms to find a initial position of the capsule and then using the RCA to track it in a real system.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (grant number 61273332) and Ningbo Science and Technology (Innovation Team) plan project (grant number 2014B82015).

Disclosure

The authors report no conflicts of interest in this work.

---

References

1.	Iddan G, Meron G, Glukhovsky A, Swain P. Wireless capsule endoscopy. Nature. 2000;405(6785):417.
2.	Golden RN, Silverstein FE, inventors. Apparatus and method for locating a medical tube in the body of a patient. United States patent US 19975622169. April 22, 1997.
3.	Prakash NM, Spelman FA. Localization of a magnetic marker for GI motility studies: an in vitro feasibility study. Presented at: Engineering in Medicine and Biology Society, 1997: Proceedings of the 19th Annual International Conference of the IEEE; October 30–November 2;1997; Chicago, IL.
4.	Hu C. Localization and Orientation System for Robotic Wireless Capsule Endoscope [dissertation]. Edmonton: University of Alberta; 2006.
5.	Liu L, Liu W, Hu C, Meng MQH. Hybrid magnetic and vision localization technique of capsule endoscope for 3D recovery of pathological tissues. Presented at: IEEE 9th World Congress on Intelligent Control and Automation (WCICA); June 21–25; 2011; Taipei.
6.	Wang K, Yan G, Jiang P, He W, Guo X. [Localization system for electrical capsule based on permanent magnetic field]. Sheng Wu Yi Xue Gong Cheng Xue Za Zhi. 2007;24(5):1148–1151. Chinese.
7.	Yang W, Hu C, Meng MQH, Song S, Dai H. A six-dimensional magnetic localization algorithm for a rectangular magnet objective based on a particle swarm optimizer. IEEE Trans Magn. 2009;45(8):3092–3099.
8.	Popek KM, Mahoney AW, Abbott JJ. Localization method for a magnetic capsule endoscope propelled by a rotating magnetic dipole field. Presented at: IEEE International Conference on Robotics and Automation (ICRA); May 6–10, 2013; Karlsruhe.
9.	Hu C, -H Meng M, Mandal M. Efficient linear algorithm for magnetic localization and orientation in capsule endoscopy. Conf Proc IEEE Eng Med Biol Soc. 2005;7:7143–7146.
10.	Hu C, Yang W, Chen D, Meng MQ, Dai H. An improved magnetic localization and orientation algorithm for wireless capsule endoscope. Conf Proc IEEE Eng Med Biol Soc. 2008;2008:2055–2058.
11.	Hu C, Li M, Meng MH, Song S. A new tracking system for three magnetic objectives. IEEE Trans Magn. 2010;46(12):4023–4029.
12.	Hu C, Meng MH, Mandal M. Efficient magnetic localization and orientation technique for capsule endoscopy. International Journal of Information Acquisition. 2005;2(01):23–36.
13.	Andersson J. Multiobjective Optimization in Engineering Design Applications to Fluid Power Systems [dissertation]. Linköping: Linköping University; 2001.