Introduction

Percutaneous needle-based procedures such as biopsy, prostate brachytherapy and radio-frequency ablation (RFA) require guidance of the needle to a target location to deliver therapy or to remove tissue samples from a suspicious site for diagnosis. Tracking the needle in real-time through imaging facilitates guiding them inside the soft-tissue and enables automating the needle insertion procedure. Percutaneous needle-based procedures are commonly performed using magnetic resonance imaging (MRI), ultrasound, computed tomography (CT) or fluoroscopy. The success of the image-guided procedures highly depends on the ability to precisely track and guide the needle.

There are many challenges in achieving accurate targeting in needle-based procedures such as needle deflection due to tissue deformation. The targeting errors due to initial alignment of the needle with the target can be reduced with robotic assistance.29,11,22 However, most of the targeting errors occur due to needle deflection when the needle is inside the soft-tissue. Furthermore, some sites are inaccessible using straight-line trajectories due to the anatomical structures that need to be avoided. Targeting errors may lead to false negatives in biopsy procedures, imprecise delivery of radiation therapy in brachytherapy procedures and ablation of healthy tissue in radio-frequency ablation procedures. In our previous work, a multi-degree-of-freedom hollow needle (cannula) was developed to account for the needle placement errors.4 The discretely actuated steerable cannula enables trajectories that are not limited to straight-line trajectories. The cannula is composed of straight segments that are connected by shape memory alloy (SMA) actuators at discrete locations along its length. When the SMA actuators are heated using resistive heating, they transform into an arc thereby generating joint torques. To control the bending angle at each joint and hence the tip of the cannula, two control approaches have been explored. One approach is to measure the bending angle or the tip position directly via the imaging modality. The second approach is an indirect approach where the strain of the SMA actuators is controlled by controlling the temperature of the SMA actuator. The constitutive model of the SMA relates the stress, strain and the temperature of the SMA.25 This work is focused primarily on the detection of the cannula in ultrasound-images for ultrasound-guided steering of the cannula.

Related Work on Ultrasound Imaging

Ultrasound imaging is inexpensive, portable and free of ionizing radiation. Real-time images can be obtained intraoperatively which makes it attractive for instrument guidance in interventional procedures. In clinics, the localization of the needle is done by an experienced physician. When ultrasound is intended to be used as a feedback to automate the needle insertion procedure, the ultrasound image needs to be analyzed to extract quantitative information about the needle shape and configuration.

Image analysis is commonly applied to ultrasound images to reduce noise and extract useful information about the needle position. Extraction of lines, edges and curves is a key step in image analysis. The Radon transform is a well-known tool for detecting parametrized shapes in an image.26 Radon transform was previously used to determine parametrized shapes of a curved needle.23 Hough transform is a special case of the Radon transform and is commonly used to determine line parameters such as slope and intersection points.13 Hough transform has been used to find the needle long-axis which is usually the brightest line in an ultrasound image.33,8 3D ultrasound imaging is advantageous since it enables 3D visualization of the surgical site. Novotny et al. tracked passive markers that were wrapped on a needle using 3D ultrasound to obtain needle position.8 The markers were detected at different positions after imaging for 5 s. Adebar and Okamura attached a piezoelectric actuator to the needle shaft outside the tissue to create vibrations that can be detected in the ultrasound images using 3D Doppler ultrasound.28 An active contour-based detection method was also used to detect a curved instrument and the results were demonstrated in 3D ultrasound images.35 Previous work on 3D ultrasound primarily focused on detection of the instruments in pre-acquired images.28,35 The implementation of the algorithms is computationally intensive, requires a GPU processor,23,21 and only a neighborhood of the region of interest is updated to decrease the computation time.8

Figure 1
figure 1

Needle and ultrasound transducer configurations: (a) out-of-plane tracking, (b) in-plane tracking, (c) out-of-plane tracking with an angle; (d) discretely actuated steerable cannula, (e) schematic of a 3-DOF planar cannula

Full size image

2D ultrasound is the current standard that is used in clinics. The images are obtained in slices as opposed to voxels in 3D ultrasound. Hence, it has high acquisition rate and is advantageous for real-time active tracking. When the long axis of the needle is perpendicular to the plane of the ultrasound beam, imaging occurs out-of-plane (Fig. 1a). In out-of-plane tracking, the detected shape is the cross-section of the needle. This approach is mostly used to locate the needle tip.27,2 This approach is troublesome for active tracking since the geometry of the needle is cylindrical, and each cross-section gives a circle. The shaft of the needle tip can easily be mistaken for the needle tip. The ultrasound transducer is usually placed at an angle with respect to the needle insertion direction to visualize the needle tip31,17 (Fig. 1c). In this case, the detected cross-section can be the needle shaft and the needle tip can be at a greater depth. When the needle long axis and the needle tip lie in the same plane with the ultrasound beam, the imaging takes place in-plane (Fig. 1b). The in-plane tracking makes guidance easier since the entire needle can be seen. In-plane tracking requires finding geometry specific features of the needle. For a rigid needle, the feature to be detected can be a line whereas detection of local or global curvature may be required for a curved needle.

To actively steer the discretely actuated steerable cannula, we need to develop image processing algorithms that extract information about the needle tip and joint angles. The goal of this paper is to develop real-time imaging algorithms that detect the shape of the discretely actuated steerable cannula and achieve accurate localization of its tip. The in-plane tracking gives information about the configuration of the cannula and can be used as feedback to control the motion of the cannula. Out-of-plane tip detection is achieved by rotating the ultrasound transducer until ultrasound beam is perpendicular to the needle long axis and then scanning the cannula tip to detect the exact location of the cannula tip. This way any out-of-plane motion can be easily detected. The out-of-plane tracking method proposed in this paper guarantees that the detected shape is the needle tip.

In ultrasound imaging, artifacts of the needle result in missing boundaries. Even when the boundaries are clearly resolved, extracting the boundaries of the needle is not sufficient for tracking. Independent of which algorithm is used, there still has to be a post-processing step to extract quantitative information on the configuration of the needle. For instance, Hough line transform may work well in situations where there is only a single bright line. Despite the missing boundaries, the line parameters can be obtained when a portion of the line is detected. However, it would fail for the cases where there are multiple links. Since the goal is to find the slope between the links, one cannot specify a desired slope to eliminate the other lines. Hence, for real-time guidance of the needle, the performance of the tracking method used does not only depend on detecting the needle boundaries, but also depends on effectively getting quantitative information that describes the needle configuration. In this work, needle detection and quantitative information are obtained simultaneously.

Contributions

The main contribution of this paper is employing the optical flow algorithm and circular Hough transform to develop image processing algorithms that can detect the cannula and provide quantitative information about its configuration. This is a crucial first step towards automating the cannula insertion and controlling the cannula in a closed-loop using real-time image-feedback. To track the shape of the cannula in-plane, a tracking algorithm based on optical flow was developed. Lucas–Kanade optical flow is a powerful algorithm for motion estimation and feature tracking.1 This algorithm is advantageous since it is computationally efficient, and can run on a CPU. Optical flow algorithm has been previously used for temperature estimation in ultrasound images,6 estimation of muscle thickness during contraction,9 and myocardial strain analysis16 to name a few. While the optical flow algorithm has been applied in other applications, to the best of our knowledge, this is the first time the optical flow algorithm is applied to ultrasound images to track the features of a needle. Optical flow algorithm is based on the brightness smoothness assumption and hence it is sensitive to variation in brightness. Ultrasound imaging suffers from brightness variation. The brightness not only changes in space but also in time. Therefore, applying the optical flow algorithm to the ultrasound images directly gives poor results. We introduce a pre-processing step that enables overcoming the brightness variation problem and enables using the fast and powerful optical flow tracking algorithm on ultrasound images. In this paper, pre-processing refers to the steps before the optical flow algorithm and the circular Hough transform are used. Although the focus of the paper is primarily on tracking the discretely actuated steerable cannula, we show that the algorithms developed in this work can be extended to other generic needles as well. A needle-tip scanning method is also introduced that detects the tip of the cannula using circular Hough transform when the tracking is out-of-plane. The proposed method guarantees that the detected shape is the needle tip and not the needle shaft.

The paper is organized as follows. In Sect. 2, we describe the discretely actuated steerable cannula and the experimental setup used for tracking. We also describe the circular Hough transform along with the optical flow algorithm. In Sect. 3, the effectiveness of the proposed in-plane and out-of-plane tracking methods are demonstrated through experiments inside tissue phantom made of gelatin and ex-vivo experiments in bovine kidney. Finally, in Sect. 4, we make some concluding remarks.

Materials and Methods

Discretely Actuated Steerable Cannula

The cannula is composed of straight segments that are connected by SMA actuators. The SMA actuators are 0.53 mm diameter wires and they were annealed in an arc shape. When the SMA actuator is heated using resistive heating, it deforms into an arc shape thereby generating joint torques. SMA actuators have one-way-shape-memory-effect and antagonistic pair of SMA actuators are needed at each joint to achieve joint motion in a plane.

Figure 1d shows the discretely actuated steerable cannula that has three straight segments and two joints. The straight segments have 1.651 mm inner diameter and 3.175 mm outer diameter. The length of each segment from the base to the tip is 3.8, 2.5 and 2.1 cm, respectively. In our previous work, the straight metal segments were coated with high temperature enamel coating for electrical insulation.12 In this work, the proximal (closest to the base) link is made of metal and coated with high temperature enamel coating and the remaining straight segments are made of polycarbonate. All SMA actuators lie in a plane and the motion of the cannula occurs in a plane. The cannula is covered with non-conductive sheath for heat isolation and electrical insulation of the SMA actuators inside soft-tissue.

The kinematics of the cannula is straightforward. The schematic used for deriving the forward kinematics of the cannula is shown in Fig. 1e. There are 3 degrees-of-freedom (DOF): 1-DOF at each joint and 1 insertion DOF. The configuration of the cannula in a plane can be described using Eq. (1):

$$\begin{aligned} x \,=\,&L_1 + u + L_2 \cos\alpha _1 + L_3 \cos\beta + r_1 \sin\alpha _1 + r_2 ( \sin\alpha _2 \cos\alpha _1 - \sin\alpha _1 ( 1-\cos\alpha _2 ) ) \nonumber \\ y \,=\,&L_2 \sin\alpha _1 + L_3 \sin\beta + r_1 (1-\cos\alpha _1) + r_2 ( \sin\alpha _1 \sin\alpha _2 + \cos\alpha _1 ( 1-\cos\alpha _2 ) ) \nonumber \\ \beta \,=\,&\alpha _1 + \alpha _2 \end{aligned}$$
(1)

where α 1 and α 2 are the joint angles, \(u\) is the insertion distance; \(L_1\), \(L_2\), and \(L_3\) are the lengths of the straight segments from the base to the tip; \((x,y)\) is the position of the cannula tip and \(\beta\) describes the orientation of the distal link (and hence the cannula tip). The radius of curvature of the joints is given by \(r_1\) and \(r_2\). The relation between the arc radius, \(r\), and joint angle, \(\alpha\), is \(r=\ell / \alpha\) where \(\ell\) is the length of the SMA actuator between consecutive links. The three equations representing the geometry of the cannula is solved using a 4th order Runge-Kutta solver.

Experimental Setup

Figure 2
figure 2

Linear rail system used for the ultrasound experiments along with the Philips Sonos 5500 US system

Full size image

The experimental setup used for ultrasound guidance is shown in Fig. 2. Two linear rail systems (Haydon Motion Solutions) are mounted orthogonally to the top frame. The rails consist of a stepper motor (0.015875 mm per step resolution) and has 305 mm travel length. These two rails are used to position the ultrasound transducer in a plane. The cannula is fixed between two plates. The plates are attached to a vertical support, and the vertical support is attached to the sliding element of rail 3. The height of the plates can be adjusted using screws. The vertical position of the ultrasound probe can also be adjusted prior to the experiments to make sure the ultrasound probe is in contact with the tissue sample. The arrows shown with dashed lines show the adjustment direction for the cannula fixture and the ultrasound fixture. There is a DC motor (Model 247858, Maxon Precision Motors, Inc.) attached to the sliding element of rail 2 and its rotation axis is centered along the center of the ultrasound probe. Hence, the ultrasound probe has two translational and one rotational degrees-of-freedom.

There are two PCs that communicate through the serial port. One of the PCs controls the rails and the cannula using Sensoray 626 DAQ. The DAQ sends control signals to the solid state relays (SSRs) that control the current flow to the respective SMA actuators. The rails are controlled via a TTL-compatible micro stepping chopper drive (DCM 8028, Haydon Motion Solutions). The TTL-signals are generated using Arduino UNO board at 500 Hz and this frequency corresponds to 3.9 mm/s travel speed. The DC motor is controlled using a proportional-integral (PI) controller. A constant 2.5 V is supplied until the motor angle is within 10° of the desired angle. Once the error is less than 10° the proportional-integral (PI) controller takes over. Another PC is used to process the ultrasound images. The ultrasound system is a Philips Sonos 5500 ultrasound console with a 3–11 MHz linear array transducer (Model 11-3L). The ultrasound images are acquired in real time at 15 fps using a Matrox Morphis (Matrox Inc.) frame grabber. Matrox Imaging Library (MIL) library is used to grab and process the images in real time.

Lucas–Kanade Optical Flow for In-Plane Tracking

Optical flow is a fast and robust tracking algorithm that can be used to track features or points in an image stream. The Lucas–Kanade optical flow algorithm is briefly described here for completeness, and to shed light on the underlying assumptions which make it hard to apply the algorithm to the ultrasound images directly. By comparing two consecutive images in an image stream, an intensity map can be obtained that describes the change in intensity per pixel. Let the increase in brightness in the first image at a pixel location \(p(x,y)\) along the \(x\) direction be \(I_x\) and \(y\) direction be \(I_y\). After a movement by \(v_x\) pixels in the \(x\) direction and \(v_y\) pixels in the \(y\) direction, the total increase in brightness is equal to the local difference in intensity \(I_{\rm{t}}\) between the two frames. Hence, the optical flow equation is given as:18

$$\begin{aligned} I_x \cdot v_x+I_y \cdot v_y=-I_{\rm{t}} \end{aligned}$$
(2)

where \(v_x\) and \(v_y\) are the unknown optical flow of the pixel in \(x\) and \(y\) direction, respectively. The displacements in \(x\) and \(y\) directions are defined in terms of pixels. In the more general form, the optical flow equation for the ith pixel, \(p_i\), is given as:

$$\begin{aligned} \nabla I(p_i)^{\rm{T}}\cdot[v_x\,v_y ] +I_{\rm{t}}(p_i)=0 \end{aligned}$$
(3)

The first term is the spatial gradient and the second term is the temporal gradient. Since one pixel does not provide enough information for corresponding to another pixel in the next frame, the equations are formulated in a \(k\times k\) sized window around the pixel assuming they all move by \([v_x,v_y]^{\rm{T}}\). A set of \(k^2\) equations can be obtained and represented in the matrix form as:18

$$\left[\begin{array}{cc} I_x(p_1)&\quad I_y(p_1) \\ I_x(p_2)&\quad I_y(p_2) \\ \vdots&\quad \vdots \\ I_x(p_{k^2})&\quad I_y(p_{k^2}) \end{array}\right] \left[ \begin{array}{c} v_x \\ v_y \end{array} \right] = \left[ \begin{array}{c} I_t(p_1) \\ I_t(p_2)\\ \vdots \\ I_t(p_{k^2}) \end{array} \right]$$
(4)

The system of equations is overdetermined and is of the form:

$$\begin{aligned} Ad=b \end{aligned}$$
(5)

The solution to Eq. (5) is formulated as a least-squares minimization of the equation by minimizing \(\left\| Ad -b\right\| ^2\). The solution \(d=[v_x,v_y]^{\rm{T}}\) is found by solving:

$$\begin{aligned} \left( A^{\rm{T}}A\right) d=A^{\rm{T}}b \end{aligned}$$
(6)

\(A^{\rm{T}}A\) is indeed the Hessian matrix and has the second-order derivatives of the image intensities. Eigenvalue analysis of the Hessian matrix contain information about local image structure and reveals edges and corners that can be tracked between images.34 Hence, the detected features are the edges and corners in the \(k\times k\) sized window. Since the algorithm searches only small spatial neighborhood of the pixel of interest, large motions can cause the points to move outside of the local neighborhood and the tracked points can be lost. To overcome this problem, pyramidal Lucas–Kanade algorithm has been developed which starts analyzing the motion flow from the lowest detail to finer detail.19 The pyramidal implementation of the Lucas–Kanade method is a fast and reliable optical flow estimator that can accommodate large motions. We use the OpenCV implementation of the algorithm.7 The mathematical formulation of the optical flow algorithm in pyramids (top to down) is beyond the scope of this work and it is described elsewhere.19

Circular Hough Transform for Tip Detection

The Hough transform is commonly used to find the parametrized shapes in an image. It was originally used for the detection of straight lines14 and has been previously applied for the detection of the needle long-axis in ultrasound images.31,10 It was also used to detect curved needles by connecting the straight segments that are found using Hough transform with a polynomial fit.20 Hough transform can also be used to detect shapes other than lines such as circles and ellipses. Circular Hough transform is a particular example where Hough transform is employed to search a parameter space. A circle with radius \(r_{\rm{c}}\) and its center at \((x_{\rm{c}},y_{\rm{c}})\) is parametrized by the equation:

$$\begin{aligned} (x-x_{\rm{c}})^2+(y-y_{\rm{c}})^2=r_{\rm{c}}^2 \end{aligned}$$
(7)

Hough transform usually employs an edge detector to detect the edges of the circle. An arbitrary edge point \((x_i,y_i)\) transforms into a circular cone in the \((x_{\rm{c}}, y_{\rm{c}}, r_{\rm{c}})\) parameter space.14 Circular Hough transform was previously used for automated localization of retinal optic disk on images captured by a fundus camera,30 measurements of arterial diameter in ultrasound images during the cardiac cycle,24 and segmentation of the left ventricular in 3D echocardiography.5 We use circular Hough transform to detect the needle tip when the tracking is out-of-plane. Since the diameter of the needle is known, the search reduces to two parameters. The algorithm also uses the edge gradient information which determines the direction of the circle with respect to the edge point.32

Experiments and Results

In-Plane Tracking of the Cannula

Figure 3
figure 3

The markers are the tracked features (points). A line was plotted to connect the two points to show the orientation of the cannula tip. (a) Two points were selected (shown on left). The point at the tip shifted across the needle cross-section due to pixels having similar brightness as the cannula was further inserted into the tissue phantom (shown on right-21 frames after). This introduces an error in the angle calculation. This means the pixels that are further down the cross-section had similar brightness with the ones that were originally selected on the top surface. (b) This figure shows another example where the algorithm fails in the beginning when a point on the distal link (the link where tip is located) was selected. When a point on the top surface was clicked with the mouse, the algorithm detected a feature (a brighter edge) that is lower down the cross-section

Full size image

There are two main assumptions of the Lucas–Kanade optical flow algorithm. Firstly, optical flow algorithm is sensitive to brightness variation and it expects brightness smoothness. The objects or features in the image should exhibit intensity levels that change smoothly. The second assumption is the spatial coherence. It is assumed that neighboring points in a region belong to the same surface and move in a similar fashion. These assumptions make it difficult to apply the optical flow algorithm to ultrasound images directly. In ultrasound images the brightness of a region can change both in time and space. The optical flow algorithm was tested on the ultrasound videos of the cannula. Initially, the desired features to be tracked (corner, edge) are selected by clicking on the image with the mouse. To get the cannula configuration, we track a corner (cannula tip) and an edge (a point on the distal link) on the top surface. The coordinates of these two points are enough to determine the tip location and orientation. Figure 3 demonstrates two cases where the algorithm fails to track the desired points in an image stream. To eliminate these problems, smooth brightness should be achieved on the surface from which the points are selected and the brightness variation of the tracked points in time should be minimized. Edge detection algorithms are useful to find the boundaries of the cannula. However, the boundaries of the cannula are not always clearly resolved since the artifacts result in missing boundaries. Pre-processing of the images is necessary to reduce noise, intensity variation, and missing boundaries. Using a fixed threshold value is risky since in ultrasound images the brightness not only varies in space but also in time as the needle is steered inside the soft tissue or the organ. Even when the threshold value is varied between images, there might be anatomical structures having same brightness as the needle and thresholding can destroy some portions of the needle as well. Hence, in this work we avoid using thresholding and only morphological operations are used for processing the images to remove noise and detail.

The image is first processed using downsampling followed by upsampling operation to reduce the amount of noise and detail. Erosion, dilation and blurring operations are also applied recursively to smooth the image and reduce brightness variation. The surface of the cannula facing the transducer has higher brightness in ultrasound images. Sobel operator is applied to the pre-processed image to detect the top surface of the cannula. The edges occur when the gradient is greatest and the Sobel operator finds the edges in the image. The Sobel Operator is a discrete differentiation operator and it computes an approximate image gradient in the \(x\) and \(y\) directions by convolving the image with a pair of \(3\times 3\) kernels. The kernels of the Sobel operator, \(S_x\) and \(S_y\), are defined as:

$$S_x=\left[\begin{array}{lll} -1&\quad 0&\quad 1 \\ -2&\quad 0&\quad 2 \\ -1&\quad 0&\quad 1 \end{array}\right],\quad S_y=\left[\begin{array}{lll} -1&\quad -2&\quad -1 \\ 0&\quad 0&\quad 0 \\ 1&\quad 2&\quad 1 \end{array}\right]$$
(8)

After the top surface of the cannula is detected, a linear blend operator is applied using Eq. (9) to combine the output of the Sobel operator with the original image.

$$\begin{aligned} I=\gamma I+(1-\gamma )I_{\rm{sobel}} \end{aligned}$$
(9)

where \(I\) is the original image, \(I_{\rm{sobel}}\) is the image that is obtained by convolving the output of the morphological operations with the Sobel operators, and \(\gamma\) is the weight of blending that ranges between 0 and 1. The blend operator overlays both images, thus enhancing the brightness of the top surface of the cannula on the original image. The value of \(\gamma\) was chosen as 0.65. This coefficient should be larger than 0.5 so that the output of the Sobel operator (top surface) has a higher weighting. The blend operator not only increases the brightness of the top layer that is detected using the Sobel operator but also reduces the brightness of the other regions since the original image intensities are multiplied by a coefficient that is smaller than 1. The resulting image is used as an input to the optical flow algorithm.

Figure 4
figure 4

(a) The top surface of the cannula was clearly resolved after applying the Sobel operator to the pre-processed images. (b) The shape of the cannula was successfully detected and overlayed on the ultrasound images from the experiment. Since the blend coefficient \(\gamma\) was chosen as 0.3 the image has a tinge of gray. (c) The change in joint variables \(q=[\alpha _1,\alpha _2,u]\), in experiment shown in (b) were calculated in real-time. (d) The various steps of the pre-processing steps in ex-vivo bovine kidney experiment. (e) The shape of the cannula was successfully detected and drawn on the ultrasound images. (f) The change in joint variables in cannula insertion experiment shown in (e)

Full size image

Videos of cannula insertion experiments were recorded to test and optimize the parameters of the tracking algorithm. The videos are 45 s long on average and were recorded at 15fps. The tested parameters were the kernel size of the dilation and erosion (3, 5, 7, 9), the number of recursive morphological operations (between 1 and 10), the blend coefficients (between 0 and 1), and the brightness increase \(\lambda\) (between 1 and 3). Among these, the number of recursive morphological operations determines how much the image will be clear of noise and detail. Five iterations give a clear image for both gelatin and soft-tissue without substantially increasing the computation time. Kernel size of the dilation/erosion does not have a substantial effect on the outcome. \(\lambda\) can be selected between 2 and 3 to increase the brightness of the top surface. \(\lambda =3\) works better for soft-tissue.

In the experiments, the transducer is stationary and the cannula is inserted into the gelatin. The cannula is aligned with the ultrasound beam in-plane. The tracking algorithm starts when the cannula is inserted sufficiently into the medium. Once the cannula is inside the imaging region, the tip of the cannula and one point on the top surface of the distal link are selected. A line is fitted between the two points and the tip orientation is obtained. This configuration is registered as the initial configuration. The motion of the two points are continuously tracked using the pyramidal Lucas–Kanade optical flow algorithm. The optical flow algorithm gives the pixel location of the cannula tip position and orientation. The pixel information is then converted into physical dimensions and the joint variables, \(q = [u, \alpha _1, \alpha _2]\), are solved using inverse kinematics. Finally, the shape of the cannula is drawn on the image in real-time using the kinematic equation given in Sect. 2.1. Full description of the in-plane tracking procedure is given in Algorithm 1.

figure a

Figure 4a shows the original ultrasound image, the pre-processed image and the output of the blend operator which is given as an input to the tracking algorithm. Figures 4b–4c show the results from a tracking experiment in-plane. The cannula trajectory is displayed on the screen and the change of joint variables are recorded in real-time. Any technique can be used to draw the cannula shape on the original image. In this work, the shape of the cannula is drawn in a separate window and overlaid on the original image using a blend operator. The cannula kinematics is overlaid on the image with \(\gamma\) = 0.3 to demonstrate that the cannula shape is accurately detected. The choice of the coefficient for the blend operator is not important as long as the drawing can be seen on the image.

The algorithm was also verified in an ex-vivo experiment. Figure 4d shows various steps of the image processing. Figures 4e–4f show the results of a cannula insertion experiment into a bovine kidney. The soft-tissue has more intensity variations compared to tissue phantom made of gelatin, yet the output of the Sobel edge detector clearly resolves the top surface of the cannula.

Figure 5
figure 5

(a) Needles that are used in ex-vivo bovine experiments, (b) ultrasound image (left) and the pre-processed image (right) of the prostate brachytherapy needle, (c) ultrasound image (left) and the pre-processed image (right) of the coaxial biopsy needle

Full size image

The pre-processing step was tested on two commercially available needles as shown in Fig. 5a inside ex-vivo bovine tissue. One of the needles is a 18 gauge needle used for prostate brachytherapy (Mick Radio Nuclear Instruments, Inc.) and the other one is a 12 gauge high field MRI coaxial biopsy needle (Invivo, Corp.). The goal of this experiment is to demonstrate that the pre-processing step can highlight the top surface of generic metal needles as well. The cannula is currently made of mostly polycarbonate parts. Future prototypes may involve metal parts. Since the pre-processing step uses a gradient operator (Sobel operator), the algorithm looks at the relative intensity difference. Independent of which needle is used; the top surface has higher brightness since the transducer faces the top surface of the needle. Figures 5b and 5c show the original ultrasound images of the prostate brachytherapy and the biopsy needle, and the images after pre-processing. The brightest pixels are on the top surface of the needles and the pre-processing step extracts the top surfaces of the needles.

Image processing algorithms are targeted for visualization or obtaining information about the needle position since the position of the needle is not known. It is difficult to give a quantitative measure of the performance of the algorithm since there is no ground truth that can be used for comparison. We can potentially introduce a magnetic tracker inside the cannula to verify the tip location. However, the error of the magnetic trackers can be up to 2 mm.15 This corresponds to more than half the size of the cannula diameter and is not a reliable way of providing a ground truth. In the tracking algorithm, the tracked features are trapped on the top surface of the cannula. Hence, the locations of the tracked points give an accurate measure of the joint angles. This was manually verified with a digital protractor software.

Out-of-Plane Detection of the Cannula Tip

Figure 6
figure 6

(a) To demonstrate tip detection using circular Hough transform, the ultrasound transducer was slided over the cannula and the images were recorded with 0.127 cm intervals. (b) From left to right: the cannula started to appear—a bright region was observed which corresponds to the upper part of the cross-section (bevel-tip)—the cannula cross-section was detected. The images show: (i) the pre-processed images prior to the application of circular Hough transform, (ii) The original images of the ROI where cannula tip is located. When the circle was detected, it was drawn on the original image. The circular Hough transform gives the center of the detected circle. The center of the circle was marked in blue and the circle, which corresponds to the outer diameter of the cannula , was drawn in yellow on the frame when it was detected. The circle was also drawn on the corresponding pre-processed image of the frame the circle was detected to demonstrate the actual location of the circle. The circular Hough transform operates on the pre-processed image

Full size image

In out-of-plane tracking, the ultrasound transducer is perpendicular to the direction of needle insertion. Hence, the ultrasound image shows cross-sections of the needle-long axis. To demonstrate the tip detection using circular Hough transform, the transducer was positioned away from the cannula tip such that the cannula tip was not visible (Fig. 6a). To increase the computation time, Circular Hough transform searches a circle within a 2.5–3cm (10 times the cannula diameter) window (ROI). The ROI is defined around the initial position of the cannula which is known from the respective position of the rails. The transducer was moved towards the cannula tip with 0.127 mm increments. Downscaling, upscaling, dilation, and erosion operations followed by blurring were applied recursively to obtain a clear image that is free of any noise (see Algorithm 2 for the parameters used). The result is a bright spot at the center of the cannula axis. Figure 6b shows the original ultrasound images and the images after the pre-processing step. A range of pixel values can be specified to detect circles with a desired diameter. The circle radius was specified as 8–10 pixels, which corresponds to 3.074–3.842 mm diameter. The number of recorded frames from the time the tip started to appear to the frame that the circle was detected is 39. This corresponds to 4.953 mm displacement of the transducer. The length of the bevel-tip is 5.5 mm and the algorithm shows great performance in accurate detection of the tip.

figure b

The out-of-plane detection can be used to track the needle-tip in real-time. In our approach, the main tracking takes place in a plane. The cannula is initially aligned with the ultrasound beam in-plane. In the experimental setup, the relative configuration of the rails and the cannula are known. In a clinical scenario, the registration of the ultrasound probe with the cannula axis can be achieved using a camera system such as Micron Tracker (Claron Technologies Inc.) and the needle plane can be detected by jiggling the needle to differentiate its motion from that of the tissues or organs.3 The 3D location of the cannula tip can be obtained by rotating the ultrasound transducer by 90\(^\circ\) around its axis and sliding the transducer over the cannula to obtain the location of the tip using circular Hough transform. Using this approach, any off-plane movement of the cannula due to tissue interaction can be quantified. This method also guarantees the detected shape is the needle tip and not the needle shaft. Full description of the out-of-plane tip detection procedure is given in Algorithm 2.

To demonstrate accurate localization of the cannula tip using combined in-plane and out-of-plane tracking, an experiment was carried out. The cannula is inserted at 0.508 cm intervals and is actively tracked in-plane using the algorithm described in Sect. 3.1. Whenever the cannula tip reaches the center of the ultrasound image, ultrasound transducer is also advanced in the direction of cannula insertion by 0.635 cm to guarantee that the cannula tip does not cross the center of the ultrasound transducer rotation axis. When the user requests 3D information of the tip, the ultrasound probe rotates 90° and the ultrasound transducer is moved towards the cannula to detect the tip. Since the ultrasound transducer always moves ahead of the cannula tip, it is guaranteed that the transducer will be ahead of the cannula tip once it is rotated.

Figure 7
figure 7

(a) Ultrasound images: (i) before the ultrasound transducer rotated (initially the tracking is in-plane), (ii) when ultrasound transducer was rotated, (iii) 90° rotation was achieved and the cannula tip was observed ahead of the ultrasound transducer, (iv) the transducer moved towards the cannula and the circular cross-section was detected. The location of the tip is \([x,y,z]=[56.05,40.30,58.75]\) mm in the imaging plane. (b) Change in ultrasound transducer rotation and position, and the cannula displacement with time

Full size image

The computation time of the in-plane tracking algorithm is 43.4 ms and out-of-plane is 168.4 ms. The reported computation times include the tracking algorithm, drawing the cannula (or the circle) and displaying the original images and the processed images. Figure 7b shows the change in cannula insertion distance, the displacement (rail 2) and the rotation of the ultrasound transducer. The transducer tracked the cannula tip until 22 s. The user requested out-of-plane tip location. The motor rotated 90° and the transducer started moving against the cannula insertion detection and the circular Hough transform was activated. Since the vertical position of the tip in the plane is known prior to the rotation of the transducer, the ROI is automatically defined and the out-of-plane detection algorithm searches for a circle near the neighborhood of the previous location. When the cannula tip was detected, the program stopped. Figure 7a shows the ultrasound images at the locations marked as i, ii, iii and iv in Fig. 7b.

Conclusions

This work describes an in-plane needle tracking method that tracks the needle in 2D and an out-of plane needle-tip detection method that localizes its tip. There are two main results of this work. Firstly, using the pre-processing method described in this work, the top surface of the needles can be highlighted and smooth brightness can be achieved on the needle top surface. This makes it possible to use optical flow algorithm to track the features of the needle in ultrasound images. Secondly, since the cross-section of the needle is a circle, circular Hough transform can be used to localize the needle-tip when the ultrasound beam is perpendicular to the tip of the needle. The in-plane tracking tracks the orientation of the tip and its position at the top-surface of the cannula. Out-of-plane tracking takes advantage of the bevel tip and the circular cross-section to detect the center of the bevel tip.

The effectiveness of the algorithm in extracting the top surface was successfully demonstrated in tissue phantom and in ex-vivo bovine tissue. The algorithms that are presented here show the effectiveness of the algorithms and they form the foundations of our future work on active 3D tracking of the cannula. The relative position of the ultrasound transducer and the cannula base were known since the transducer moves in the Cartesian plane. The algorithms start with the assumption that the cannula is in the imaging plane. In our future work, we are interested in registration and positioning of the ultrasound transducer such that the ultrasound beam is aligned with the cannula plane. We have developed motion planning algorithms that can optimize the path between the entry point to the soft-tissue and the target point based on multiple criteria. The future work will also focus on incorporating the motion planning algorithms into the tracking algorithms to steer the cannula to a desired region using ultrasound guidance.