Retrieval and registration of long-range overlapping frames for scalable mosaicking of in vivo fetoscopy

Each frame of a fetoscopy sequence offers a partial view of the imaged placenta. Under the assumption that the placenta is planar, two arbitrary frames of the sequence are related by a homography transformation. Formally, given a sequence of N frames \(I_1, \ldots , I_N\) where each \(I_i : \varOmega _i \rightarrow \mathbb {R}^3\) is an RGB image defined over a domain \( \varOmega _i \subset \mathbb {R}^2\), there exists for every pair of images \((I_i,I_j)\) a homographic warping \(w_{j,i} : \varOmega _i \rightarrow \varOmega _j\) such that for every \(\mathbf x \in \varOmega _i\), \(I_i(\mathbf x )\) and \(I_j(w_{j,i}(\mathbf x ))\) are visual measurements corresponding to the same location of the placenta. To create and visualise a mosaic, we propose the following approach. First, without loss of generality, the first frame of the sequence is defined as a reference frame located within the central part \(\varOmega _{{\text {abs}}}^1 \subset \varOmega _{{\text {abs}}}\) of a (sufficiently large) mosaic image \(M~:~\varOmega _{{\text {abs}}}~\rightarrow ~\mathbb {R}^3\). The mosaicking task aims at stitching together overlapping images to create a global map of the placenta or, in other words, at warping and placing each frame of the sequence on the corresponding part of the mosaic domain \(\varOmega _{{\text {abs}}}\). For every frame \(I_i\), the corresponding subset \(\varOmega _{{\text {abs}}}^i\) of the absolute mosaic domain \(\varOmega _{{\text {abs}}}\) must be found. Equivalently, we propose to estimate a global homography \(W_i\) such that \(\varOmega _{{\text {abs}}}^i = W_i(\varOmega _{{\text {abs}}}^1)\). Note that \(W_1\) is already defined as the identity via our choice of reference frame. Moreover, global and relative warpings are related via \(W_i \circ W_j^{-1} = w_{i,j}\). To estimate the global warpings, we rely primarily on a series of pairwise registrations of overlapping frames which are directly conducted in the relative image domains \(\varOmega _i\).

A fully sequential approach for mosaicking would register all consecutive frames and, with the obtained relative warpings \(w_{k,k-1}\) for \(2 \le k \le i\), compute the global warping \(W_i\) of the i-th frame as follows:If the estimation of the relative warpings is perfect, the equation above allows in theory a perfect mosaicking. However, in practice, errors in the estimation of each relative warping accumulate so that a clear mismatch can be observed when the fetoscope comes back to a previously visited location. This effect can even degenerate if the presence of occlusions makes the pairwise registration of two consecutive frames unfeasible, thereby breaking the chain of transformations (1). For increased robustness and temporal consistency over a large number of frames, it is therefore desired to register additional overlapping frames that are not necessarily consecutive (for example, the frames obtained when revisiting a portion of the placenta). Overall, if we denote \(\mathcal {R}\) the set of couples of indices (i, j) for which a registration has been performed and for which a resulting (possibly noisy) warping \(\hat{w}_{i,j}\) estimating the true warping \(w_{i,j}\) has thus been computed, and noticing that \(W_i \circ W_j^{-1} = w_{i,j}\), we can look for global warpings \(\hat{W}_1, \ldots , \hat{W}_N\) such thatwhere d is a measure of dissimilarity between two warpings. The formulation (2) is closely related to bundle adjustment and was proposed by Vercauteren et al. in the context of rigid transformations [23]. We define the distance \(d(w_1,w_2)\) between two warpings \(w_1\) and \(w_2\) defined over a rectangular image domain \(\varOmega \) as follows. First, we decide on a discrete set of reference points \(\mathcal {X} = \lbrace \mathbf x _1, \ldots , \mathbf x _m\rbrace \subset \varOmega \), which we choose in our case as a regular grid of step 3 over \(\varOmega \). The distance \(d(w_1,w_2)\) is then defined asThis allows us to obtain an intuitive geometrical interpretation of the distance between warpings as the maximum deviation in terms of Euclidean distance over the set of reference points \(\mathcal {X}\).

After having found estimates of the absolute warpings by solving (2), a final mosaic can be created with blending algorithms [6, 14]. In this paper, we focus on the accurate assessment of the global warpings, i.e. on the correct placement of the frames of the sequence on the mosaic. We used a standard publicly available technique [6] to generate the mosaics shown in this paper (Fig. 4).

To summarise, we identified two crucial components for mosaicking:We propose in this work a strategy to address separately these two challenging problems, respectively, exposed in “Pairwise registration of consecutive frames” and “Ensuring long-range consistency with bag of words” section, which takes into account the visual properties of in vivo sequences.

The traditional image stitiching technique [5] based on the detection and matching of landmarks (e.g. with a combination of SIFT and RANSAC) is prone to failure in in vivo sequences encountered in clinical conditions. The lack of constrast in the acquired images and the cluttered and varying aspect of the observed scene are challenges responsible for these difficulties. In this section, we present a registration method that addresses the pairwise registration of in vivo frames. Given the aforementioned challenges, we propose not to rely on landmarks. Instead, we perform a dense pixelwise alignment of the gradient orientations and propose a variant of the maximisation of the correlation of image gradients introduced by Tzimiropoulos et al. [22], with two main differences exposed in details below. Aligning gradient orientations possesses several advantages: it is for example invariant to local changes of contrast and is suitable for registering accurately linear structures such as vessels, which matches the main clinical objective of mosaicking for TTTS surgery, i.e. the creation of an overview of the topology of the placental vascular network. Moreover, by focusing solely on gradient orientations and not on the gradient norms, each pixel is given the same weight, which naturally improves the robustness of the registration to visual artifacts and partial occlusions.

The registration task consists in estimating the true warping \(w_{j,i}\) such that \(I_i(\mathbf x )\) and \(I_j(w_{j,i}(\mathbf x ))\) correspond to the same location for every \(\mathbf x \in \varOmega _i\). With this formulation, \(I_i\) is called the fixed image and \(I_j\) the moving image. We parametrise the homographic warpings with a vector \(\mathbf p \in \mathbb {R}^8\) corresponding to the 8 coefficients of the canonical homographic representation, i.e. such thatAs discussed above, we propose to look for the registration warping \(\hat{w}_{j,i}\) which aligns best the gradients of \(I_i\) and \(I_j\). Since we explicitly do not want to take into account the strength of the gradients, we first normalise the gradients of the fixed and moving images ensuring a unit gradient norm at every pixel. For a point \(\mathbf x \in \varOmega _i\) of the domain of the fixed image, we denote \(\varDelta \theta (\mathbf x , \mathbf p )\) the angle between the gradient of the fixed image and the gradient of the warped moving image at \(\mathbf x \). We define the final warping \(\hat{w}_{j,i}\), i.e. the output of our registration method, as \(\hat{w}_{j,i} = w(.,\hat{\mathbf{p }})\) whereSince \(\sin ^2t = \frac{1}{2} (1 - \cos 2t)\), the proposed approach can be seen as a variant of the maximisation of the correlation of image gradients [22] defined byWe can identify two main differences between the two formulations. First, our pixelwise costs based on the sine function are minimal for \(\varDelta \theta = 0 \) or \(\varDelta \theta = \pi \), whereas the terms in (6) are minimal for \(\varDelta \theta = 0\) only. Thereby, only the orientation (modulo \(\pi \)) of the gradients is taken into account in our cost function, and not their direction. It appears to be a useful property in practice: as we try to match vessels with an iterative method (see below), optimisation steps must be able to cross areas where gradients are oriented in opposite directions before reaching the optimal vessel alignment. Having written our minimisation problem (5) as a sum of squares, we are also able to use known results on nonlinear least squares, and more precisely the forward additive version of the Lucas Kanade algorithm [2]. This formulation not only leads to simpler theoretical mathematical derivations, but also offers the possibility to use off-the-shelf optimised solvers for nonlinear least squares problem, such as the Ceres solver [17] which includes classical optimisation techniques (the Gauss–Newton, Levenberg–Marquardt or Powell Dog–Leg algorithms, for example).

Solving (5) with the Gauss–Newton algorithm To solve numerically the minimisation problem (5), we use the fact that it is a nonlinear least squares problem to apply the Gauss–Newton algorithm, which, in the context of image registration, can also be seen as the forward additive version of the Lucas–Kanade algorithm [2]. To keep the following derivations as general as possible, we denote \(N = \vert \varOmega _i \vert \) and arbitrarily order the elements of \(\varOmega _i\) so that \(\varOmega _i = \lbrace \mathbf x _1, \ldots , \mathbf x _N \rbrace \), and we denote M the number of parameters encoding the transformation, i.e. the size of the parameter vectors \(\mathbf p \). Applying the Gauss–Newton algorithm, we approximate iteratively the desired minimum with a series of parameters \(\mathbf p ^{(1)}, \mathbf p ^{(2)}, \ldots \) such thatwhere \(\mathbf s (\mathbf p ^{(k)})\) is the \(N \times 1\) column vector \(\left( \sin \varDelta \theta (\mathbf x _i,\right. \left. \mathbf p ^{(k)}) \right) _{1 \le i \le N}\) and \(\mathbf J \) is the \(N \times M\) Jacobian matrix whose coefficients \(J_{ij}\) are defined asWe denote \(\mathbf g _m(\mathbf x _i, \mathbf p ^{(k)}) = \left( g_{m,x}(\mathbf x _i, \mathbf p ^{(k)}), g_{m,y}(\mathbf x _i, \mathbf p ^{(k)})\right) \) the gradient of the warped moving image at the location \(\mathbf x _i\), and \(\theta _m(\mathbf x _i, \mathbf p ^{(k)})\) (respectively, \(\theta _f(\mathbf x _i))\) the angle of the gradient of the moving image (respectively, the fixed image) at the location \(\mathbf x _i\). By definition, we have \(\varDelta \theta (\mathbf x _i, \mathbf p ^{(k)}) = \theta _m(\mathbf x _i, \mathbf p ^{(k)}) - \theta _f(\mathbf x _i)\) andso that the coefficients of the Jacobian given in (8) can be written more explicitly aswhere the dependencies in \(\mathbf x _i\) and \(\mathbf p ^{(k)}\) were omitted for readability. We finally mention that, although the gradients \(\mathbf g _m(\mathbf x _i, \mathbf p ^{(k)})\) could be computed at each iteration by warping the moving image and computing the gradient of the resulting warped image numerically, it is more efficient to precompute once for all the gradient of the (unwarped) moving image and obtain \(\mathbf g _m\) by warping this gradient and multiplying it by the Jacobian of the warping, by application of the chain rule [22]. The partial derivatives of \(g_{m,x}\) and \(g_{m,y}\) are obtained similarly.

As discussed in “Problem statement” section, evaluating the set of global homographies from a series of pairwise registrations of consecutive frames inevitably leads to an accumulation of registration errors. In the most extreme case, the chain of transformations can even be broken if a registration is not feasible at all, for example in the presence of a full occlusion. However, fetoscopy conditions naturally lead to long sequences during which the surgeon follows vessels one by one, resulting in the presence of numerous overlapping areas in the sequence. Therefore, introducing additional constraints from the registration of non-temporally consecutive frames may provide the redundancy to compensate for the drift and the robustness to failed registrations of consecutive frames. If we could have a reliable way to decide from the registration result if the registration was successful (see “Assessing the validity of a registration” section), we could in theory register all image pairs to extract the highest amount of information. However, registering all image pairs is computationally intractable for long sequences and would probably introduce more redundancy than required. Therefore, we need an efficient way to predict, from their visual appearance, the pairs that are worth registering.

Following an idea introduced in computer vision [10], we adopt a strategy based on bags of visual words [7] to efficiently identify frames sharing a similar content without the need to register them first. We sample dense keypoints using the VGG descriptor [19] and perform a K-means clustering over the full video to obtain a vocabulary of K visual words. Each image is then described by a signature vector \(\mathbf v \in \mathbb {N}^K \) encoding the frequency of each visual word in the image. The visual similarity between two images \(I_i\) and \(I_j\) is then computed as the cosine distance between the two associated signature vectors \(\mathbf u \) and \(\mathbf v \), i.eBy computing this similarity measure for every pair of images in the videos, we obtain a similarity matrix on which the revisiting of previous locations is apparent (Fig. 2). The construction of this matrix is more scalable than attempting the registration of all pairs and, in fact, only requires approximate nearest neighbours for which algorithms in linear time (e.g. FLANN) are available. Figure 2 shows an example of similarity matrix. In this example video, the trajectory followed by the clinician is "star-shaped": every vessel is followed until its extremity, before following it back until the last intersection, usually at the coord insertion site. The timepoints and patterns corresponding to these "back and forth" trajectories are apparent on the similarity matrix as lines orthogonal to the diagonal.

To define the set of additional candidate registrations to be included in the bundle adjustment formulation (2), we simply rely on a threshold on the similarity above which the registration of a pair is tried. The choice of this threshold is mainly driven by computational considerations, as it is directly related to the number of attempted registrations which are going to be performed before solving the bundle adjustment problem.

In the previous subsections, we described a robust method to register two images, as well as a way to retrieve pairs of non-consecutive images which share a visual overlap so that a registration of these pairs can be attempted, in addition to the consecutive pairs. Each registration is used as a term in the bundle adjustment formulation (2) and acts as a constraint in the estimation of the global homographies necessary to create the mosaic. However, in practice, the obtained registrations are not always accurate, due for example to the registration optimiser being trapped in a local minimum, to a failure of the retrieval of overlapping frames (leading to the unfeasible registration of two frames for which there is no overlap), or to the presence of a large occlusion in a frame caused for example by foetal limbs. Assessing the correct registrations within the attempted ones is of critical practical importance to filter out these wrong constraints added in the bundle adjustment, which would bias the final estimation of global homographies.

In this work, we declare a registration as successful if it is close enough from the identity (in the sense of the distance d defined in “Problem statement” section), and if the gradient-based cost function which was minimised in (5) is sufficiently small in comparison with the costs obtained with random warpings sampled around the identity. Although this empirical strategy proved to be effective in practice, we plan to investigate as future work more sophisticated methods, such as consistency checks over cycles of frames [8] or learning-based approaches.

We implemented our method in C++ using the OpenCV library. The bundle adjustment minimisation problem (2) was solved numerically using the Levenberg–Marquardt algorithm with the Ceres solver [17]. By restricting the warpings to affine transformations, i.e. homographies where \(p_7 = 0\) and \(p_8 = 0\) with the notations introduced in (4), convergence to a visually sound solution was achieved, even when starting from identity warpings as initialisation. If one desired to work with general homographies instead, closed-form solutions could be used to obtain initialisations close enough from the global optimum [18]. The pairwise registrations using the forward additive Lucas Kanade algorithm were performed in a Gaussian pyramidal fashion with 6 levels (where each level is a blurred and scaled down version of the original image, as implemented in OpenCV), starting by registering the images at a coarse level and refining progressively the warpings by increasing the resolution. In the case where a registration is rejected at a level of the pyramid, it was reinitialised as the identity for the next level. For increased robustness, we performed for each pair both a forward and backward registration (i.e. switched fixed and moving image) and kept the registration leading to the lowest cost. The bags of visual words were computed using the OpenCV implementation, with default parameters in the extraction of the VGG descriptors.

The pairwise registration between two frames takes approximately 1 second. These registrations remain the main bottleneck in practice: on our example video of 600 frames, solving the bundle adjustment problem takes a few minutes, as does the construction of the similarity matrix from the bag of words. Therefore, there is a direct linear relationship between the total computational time and the amount of attempted registrations of retrieved pairs of frames. For a given computational budget, this time can be controlled by registering a predefined amount of pairs with the maximum similarity, as mentioned at the end of “Ensuring long-range consistency with bag of words” section. Given our current implementation and set of parameters, the total mosaicking pipeline took about 3 hours.

Due to the nature of in vivo acquisitions, a ground truth for placenta mosaicking is not available. This makes a quantitative evaluation of our approach very difficult. Nevertheless, we demonstrate first promising visual results with our approach, which we discuss qualitatively in this section. Figure 3 shows, on an example video of 600 frames, the appearance of the mosaic obtained after the estimation of the global homography of each video frame. To facilitate the visual interpretation of the results and relate it more easily to the actual content of our example video, we limit the display of the mosaic to truncated versions of the video at different timepoints (from 1 to 4, chronologically). Each frame of the video is pasted chronologically onto the mosaic according to the global homography obtained after the offline optimisation. Note that the global optimisation has been run once for all on the whole video, and that these chronological timepoints are only introduced for the visualisation of our results. Figure 3 illustrates the global consistency of the mosaic: although an area showing a    -shaped vascular intersection is visited 4 times during the sequence (once at each chosen snapshot), this intersection is correctly placed at the same location in the mosaic over time. This is due to the fact that video frames containing this intersection have been recognised as similar in terms of visual content and successfully registered, adding additional constraints in the global optimisation which lead to improved temporal consistency.

We show in Fig. 4 the resulting mosaics, where frames are merged in a seemless fashion following the method of Burt and Adelson [6] publicly available in the software Enblend,¹ where one frame every 5 frames is used for blending. We show the mosaics obtained when our gradient-based registration method was used, with and without the long-range consistency with the bag-of-word formulation (respectively, Fig. 4a, b). In the purely sequential case (Fig. 4a), the drifting behaviour can be seen via the generally more distorted aspect of the mosaic, as well as clear misalignments (best seen when compared to Fig. 3), for example of the vessels on the top left part and of the membrane of the amniotic sac (linear demarcation on the bottom left part).

In addition to the qualitative results discussed in “Qualitative results” section, we compare our gradient-based registration approach with two baselines. Our first baseline is a classical image stitching technique used in computer vision available in OpenCV which consists in detecting SURF-based keypoints in each image and align the images with RANSAC. SURF features were chosen over SIFT as they performed slightly better empirically, confirming the observations made by Reeff [16] on other placenta images. Our second baseline is obtained by replacing our gradient-based similarity measure by the normalised cross-correlation, keeping the rest of our Gauss–Newton optimisation framework unchanged.

To conduct the comparison, we considered our example video of 600 frames and assessed visually the quality of the 599 sequential pairwise registrations for each baseline. Each registration was manually labelled as either correct, incorrect or doubtful (for ambiguous cases where the correctness of the registration is difficult to assess visually). To remove any subjective bias, the 1797 registrations to be labelled were randomly shuffled so that the annotation was done without knowledge of the approach which was actually evaluated in each case. Table 1 summarises the count of registration belonging to each category for the three methods and confirms the benefit of our approach based on the alignment of gradient orientations.