Revisiting the K -nn algorithm for obstetric image segmentation

Abstract

Medical image techniques are used to examine and determine the well-being of the foetus during pregnancy. Digital image processing (DIP) is essential to extract valuable information embedded in most biomedical signals. Afterwords, intelligent segmentation methods, based on classifier algorithms, must be applied to identify structures and relevant features from previous data. The success of both is essential for helping doctors to identify adverse health conditions from the medical images. To obtain easy and reliable DIP methods for foetus images in real-time, at different gestational ages, aware pre-processing needs to be applied to the images. Thence, some data features are extracted that are meant to be used as input to the segmentation algorithms presented in this work. Due to the high dimension of the problems in question, assemblage of the data is also desired. The segmentation of the images is done by revisiting the $K$ -nn algorithm that is a conventional nonparametric classifier. Besides its simplicity, its power to accomplish high classification results in medical applications has been demonstrated. In this work two versions of this algorithm are presented (i) an enhancement of the standard version by aggregating the data apriori and (ii) an iterative version of the same method where the training set (TS) is not static. The procedure is demonstrated in two experiments, where two images of different technologies were selected: a magnetic resonance image and an ultrasound image, respectively. The results were assessed by comparison with the $K$ -means clustering algorithm, a well-known and robust method for this type of task. Both described versions showed results close to 100% matching with the ones obtained by the validation method, although the iterative version displays much higher reliability in the classification.

Keywords

Feature extraction image segmentation K-nn algorithm magnetic resonance image ultrasound image

1. Introduction

Nowadays, images are very important to assist physicians in their decisions since these constitute a non-invasive way to diagnose and map the patient’s anatomy. Different types of images are magnetic resonance images (MRI), computational and digital tomographies and ultrasound images (UI). In obstetrics, having reliable exams is rather relevant since amongst 1000 women 3 have foetus malformations and, for this reason, primary detection and classification of brain abnormalities at widespread gestational ages are important.

MRI technology, patented in 1974 by Raymond Damadian [1], generates good images and is relatively safe. This type of image is relevant in neuroscience and obstetrics and has been used for the first time in pregnancy in 1983 [2, 3, 4, 5]. MRI are difficult to obtain and special care needs to be taken to make sure that their quality is enough for them to be reliably considered for analysis and diagnosis by specialists. It is factual that MRI of foetus may be corrupted by noise or blurred by the movement of the foetus during the examination [6]. However, there are methods of image reconstruction that have been developed to correct fetal movement and permitting to obtain 3D images of the fetal brain [7]. In particular, MRI of the human foetus is emerging as a clinical tool for early detection of brain abnormalities, due to its ability to evaluate morphometric measurements of a brain in development, and promises a range of new quantitative biomarkers to be used in the clinical evaluation of pregnancy [8]. A reliable tool that assesses MRI in real-time would be welcome, although this demands efficiency and speed in the evaluation. As reported in [7], the anatomy of the developing fetal brain is idiosyncratic in terms of both geometric and underlying tissue morphology, as it consists of a mixture of white matter, grey matter, and transitory structures related to brain growth.

As MRI scans are expensive, the reason for which they are used only in special cases, UI technology presents itself as a more economic alternative. Ultrasonography is used to create an image of internal soft body structures, as for instance the foetus in pregnant women or other internal organs, per ultrasound waves and is useful to find a source of a disease or to exclude pathology. Obstetrical sonography dates from 1958, with Ian Donald [9], and is commonly used during pregnancy to check on the development and presentation of the foetus, as it can be seen by the number of specialised journals in the subject, e.g. Ultrasound in Obstetrics and Gynaecology.1 UI remains the standard approach for assessment in obstetrics. It is widely available, cost-effective and allows for a real-time examination of the foetus. However, it may not bestow adequate assessment of a complex case or critical information for antenatal clinical management.

Unfortunately, UI often reveals poor detail of organs and tissues, partly due to the low-level contrast of images. These images are usually strongly degraded by a blurred, distorted shape and high dotted noise (speckle) which are due to the physical limitations of the process of the acquisition system – i.e., the sensor resolution, the limitations of sound waves behaviour and its non-ideal wave propagation conditions inside the body. MRI may overcome these limitations [10]. Presently, both scan methods are complementary in the field of medical diagnose as well as relevant in the clinical evaluation of pregnancy.

In biomedical engineering, the combination of MRI or UI with computational techniques warrants the development of high-interest tools for brain image analysis to assist neurologists and general practitioners in the early diagnosis. Thus, there is a need in the biomedical community to research new methods of processing and analysis, classification and pattern recognition that are robust, effective and general, i.e. applicable to different imaging technologies. In this work, new methods to pre-process the image are presented, followed by a modified $K$ -nn algorithm for segmentation of both kinds of images, in particular of foetus images.

Digital image processing (DIP) refers to the manipulation of digital images through processing methods that are able to make them more clear. Image segmentation (IS) refers to the process of dividing a digital image into multiple regions (sets of points), to simplify its representation in order to facilitate the analysis [11]. As a result, a set of regions or contours is extracted from the image, where every point in the same region has similar characteristics, such as colour, intensity, texture, or continuity.

Foetus segmentation has been extensively studied over the years, with several methods having been described for this type of study. Medical images can easily identify the foetus using segmentation techniques and calculate fetal parameters [12]. The methods of segmentation applied to UI are reviewed in [13]. The advent of 3D ultrasonography has made possible the use of the fetal volume as a biometric measurement to monitor its development and the different required techniques [14]. In [15, 16], the construction of an atlas with 10 isotropic images is proposed as a first method. A second method is the construction of a simple atlas based on a segmentation that aims to find the transformation between the atlas and the target low-resolution images. Following a similar methodology, [17, 18] put labels on the atlas to specify different structures of the brain, since these are usually used as a paradigm for automatic segmentation algorithms. Automatic brain tissue segmentation of MRI using convolutional neural networks is described in [19], since manual segmentation is cumbersome and time-consuming. A review on automatic segmentation of the same kind of images is presented in [17].

In this paper, the fetal brain is segmented through neighbouring characteristics using the $K$ -nearest neighbour algorithm ( $K$ -nn) algorithm [20] to classify every image point into one of the pre-defined regions. Two versions of the $K$ -nn are proposed as the core method for the recognition of different regions of an image. The first one is a refinement of the standard $K$ -nn and the second is an iterative version of the first. Both algorithms use data information in the feature space (FS). The second version complements its decisions with data information in position space (PS). As a result, a clear distinction between different regions is automatically obtained as well as between the different structures that are present in the acquired MR and ultrasound images. In the UI of the case study, these regions are the foetus, the amniotic sac and the uterus. This algorithm has been used before in the segmentation of MRI [21, 22, 23, 24]. Ultrasound obstetric images supplied by Hospital of Braga, Portugal, and MRI downloaded from [25] were used to test the proposed algorithm. Two of these images, one UI and one MRI, were selected as a case study for this work.

In this work, image pre-processing is described in Section 2. In Section 3, a data aggregation procedure is explained, the reference data is discussed and the standard $K$ -nn algorithm is described. The two versions of the $K$ -nn algorithm are explained and distinguished in Section 4. Both versions of the algorithm are demonstrated in two experiments presented in Section 5, which contains also a brief discussion of the results and a comparative appraisal of the proposed $K$ -nn approaches. Section 6 concludes the paper and withdraws some directions for future work.

2. Image pre-processing

The operations used on digital images – at the lowest level of abstraction – whose aim is to improve the representation by suppressing undesired distortions or enhancing some of its properties, relevant for further processing, are designated image pre-processing [26]. Specifically, it is performed in order to remove noise or highlight features such as contours or textures [6], uses redundancy in images and does not increase image information content. Standard processing algorithms used with advantage in many other application domains, such as hard edge or contour detection, frequently fail when applied to the UI processing task [27, 28]. In this section, we pre-process the images of Fig. 1 to prepare for the application of both versions of the $K$ -nn algorithm.

Figure 1.

Selected images used in Experiment-1 and Experiment-2, respectively.

Once an image is uploaded, its pixels are perceived as a matrix of intensities, $I,$ whose indices are point coordinates $p_{k}=(x_{k},y_{k}),k=1,\ldots,n,$ and $n$ is its total number. The first step is to normalise the image to improve the performance of the different pre-processing and segmentation methods to be applied. Normalization is a process that changes the range of point-intensity values by transforming a $n$ -dimensional greyscale image $I:\{{\mathbb{X}}\subseteq{\mathbb{R}}^{n}\}\rightarrow\{\textit{Min},\ldots,% \textit{Max}\}$ with intensity values in the range $[\textit{Min},\textit{Max}]$ , into a new image $I_{N}:\{{\mathbb{X}}\subseteq{\mathbb{R}}^{n}\}\rightarrow\{\textit{newMin},% \ldots,\textit{newMax}\}$ with intensity values in the unit interval $[0,1]$ . Normalisation is commonly used to improve the contrast in an image without distorting relative grey level intensities too significantly.

In the processing of the images of Fig. 1, low-pass filters were used to assess some statistical properties of a local region of the image, since they allow for the smoothing of it. In particular, mean filtering is a method that can reduce image noise without blurring the image contours by reducing the amount of intensity variation between neighbouring pixels. It works by moving through the image, pixel by pixel, replacing each value with the median of the neighbouring pixels, including itself. It is a nonlinear method especially suited for removing impulsive noise, frequently present in limited regions of medical images, and can be applied iteratively [29, 30]. The pattern of neighbours is called the “window”, $W$ , which slides, pixel by pixel, over the entire image. The median is calculated by first sorting all the pixel values of the window into numerical order and replacing the pixel in consideration by its mid-point value.

Contour filters could be used to identify the borders of ROI. Edges are points where the intensity image function changes abruptly. Edge detectors are a collection of local image pre-processing methods used to locate changes in the brightness function. Of the most used techniques of edge filters are Sobel, Canny, Prewitt or the Laplacian of the Gaussian Operator, all of them with good performance when applied to images with low-noise and high-contrast. The Canny filter, for instance, is considered one of the best-defined methods to provide reliable detection [31]. Operators that describe edges are expressed by partial derivatives. A change of the image function is indicated by a gradient that points in the direction of the largest growth of the image function. An edge is a vector variable with two components, magnitude and direction. The edge magnitude, $G$ , is the magnitude of the gradient. The gradient direction, $\theta$ , gives the direction of maximum growth of the function, e.g., from black to white. The edge direction is rotated with respect to the gradient direction by $-\frac{\pi}{2}$ .

Modified median and gradient filters are used to pre-process medical images which show poorly defined structures and are heavily corrupted by noise. Their results are the only features extracted from the image that will be used as input of the classification methods proposed in the next sections to identify regions in the image (ROI). Thus, the image feature vectors have only two components: the median and the gradient of the image. These feature components are sufficient to find the regions of interest (ROI) in the image. This choice is subject to the proposed methods and algorithms being hardly tested in order to determine its performance and robustness. Other components can be added to improve the results of the algorithms whenever more rich and discriminant features are desired.

2.1 Median filter

In this work, an iterative median filter is used on the images. The procedure resembles an iterative restoration of the image, done from the highest degree of similarity to the lowest. Other options for this task could be the median filter, although it has drawbacks such as: (i) one point with a very unrepresented value can significantly affect the mean value of the points in the neighbourhood; (ii) the filter does not work very well when the neighbourhood straddles an edge. Besides, the median filter is a more robust filter.

We start by filtering the original image, $I$ , using a circular window weight mask, $W$ , with radius, $r_{w}$ , to obtain image $I_{M}$ , i.e., $I_{M}^{({0})}=I$ . Next, the median filter is applied iteratively to the pixels of $I_{M}$ whose intensity values (median values) are either below or above certain threshold levels, ${\alpha_{k}}$ and ${\bar{\alpha}_{k}}=1-{\alpha_{k}}$ , respectively. During the iterative process, $k=1,\ldots,n_{\text{iter}}$ , threshold ${\alpha_{k}}=k/(2n_{\text{iter}})$ goes from values close to zero to 0.5 while ${\bar{\alpha}_{k}}$ goes from values close to 1 to 0.5 (i.e., the middle value). At every $k$ th iteration, the set of selected pixels $E=\{{({r,s})\in I_{M}:{{\bar{\alpha}}_{k}}}\leqslant{I_{M}}({r,s})\leqslant{% \alpha_{k}}\}$ is selected for filtering. Thus, the median image, $I_{M}$ , is updated:

$\displaystyle I_{M}^{({k})}(E)\leftarrow I_{M}^{({k-1})}(E)*W,$

where $*$ is the median operator. When $k=n_{\text{iter}}$ , ${\alpha_{k}}={\bar{\alpha}_{k}}=0.5$ , and $I_{M}^{(n_{\text{iter}})}$ is the median image of $I$ .

2.2 Gradient filter

To minimise both the noise effect and the blurred edges, we recalculate the gradient magnitude for each pixel by measuring the alignment between the gradient directions of all the pixels in the circular region ${W_{ij}}=\{{({r,s})\in I:{{(i-r)}^{2}}+{{(j-s)}^{2}}\leqslant r_{w}^{2}}\}$ , centered in the pixel $(i,j)$ and with the direction of pixel $(i,j)$ given by $\theta_{ij}$ and the magnitude:

$\displaystyle G_{W}({i,j})\leftarrow$ $\displaystyle\sqrt{\sum_{({r,s})\in{W_{ij}}}{G({i,j})G({r,s}){{\cos}^{2}}({{% \theta_{ij}}-{\theta_{rs}}})}}.$

This operation improves significantly the coherence of the results of the gradient filter.

Figure 2.

Features used in image segmentation. Left: The median; Right: The gradient.

3. Image segmentation

An image is a set of $n$ points of coordinates $p_{k}=(x_{k},y_{k})$ and intensity $I_{k},k=1,\ldots,n$ . After pre-processing, every point $k$ has associated a feature vector $\chi_{k}\in\mathbb{R}^{d}$ . In our case, $d=2$ and $\chi_{k}=(\textit{Med}_{k},\textit{Grad}_{k}),k=1,\ldots,n$ (see Fig. 2). This means that every point has a representation in both the position space (PS), $p_{k}$ , and in the FS, $\chi_{k}$ .

In order to segment the image, one starts by defining the ROIs. For instance, for the obstetric image on the right of Fig. 1, an interesting segmentation could be the separation of the image into the following ROIs: foetus, amniotic sac and uterus. Every defined ROI corresponds to a class ${\mathcal{C}}_{i},i=1,\ldots,n_{c}$ . TS is the union of the $n_{c}$ classification classes: $\textit{TS}=\cup_{i=1}^{n_{c}}{\mathcal{C}}_{i}$ . Hence, we can view the image as the union of two disjoint sets $\textit{TS}\cup\overline{\textit{TS}}$ , where $\overline{\textit{TS}}$ are the points of the image that do not belong to TS.

To segment the image into $n_{c}$ different regions means that every point of the image should be classified as belonging to one and only one class ${\mathcal{C}}_{i},i=1,\ldots,n_{c}$ . Define $Y$ as a vector that contains the label of the class to which every point pertains to, that is $Y_{k}\in\{0,1,\ldots,n_{c}\},k=1,\ldots,n$ . If $p_{k}\in\textit{TS}$ then the point is already classified and this means that $Y_{k}$ contains the respective class number, i.e., $\exists i,i=1,\ldots,n_{c}:p_{k}\in{\mathcal{C}}_{i}$ and $Y_{k}=i$ . If $p_{k}\in\overline{\textit{TS}}$ then $Y_{k}=0$ . Therefore, we write the trio $(p_{k},\chi_{k},Y_{k}),k=1,\ldots,n$ , for every point of the image.

Often, training classifiers using all image pixels do not lead to a better solution. Large sets of training data cause difficulties to the training process and make it time-consuming. Additionally, the training process can fail, even when in the presence of very similar data groups, which show redundancy and a low level of discrimination, even when the mean absolute error is small. For these large-sample problems, diverse clustering techniques can be used to group the samples in order to have a group represented by a single value. Here, the simple nearest neighbourhood clustering scheme is used as the aggregation method of the data. This method can be seen as a 1-nn algorithm and is described in Subsection 3.1. The $K$ -nn versions developed in this work use the aggregated data instead of the initial TS above defined in Eq. (1).

3.1 Aggregation method

To reduce the dimensionality of the problem, the points may be aggregated in FS as well as in PS. Neighbour groups are constructed in FS and represent regions of pixels that have the same or similar feature values. A group is an ellipsoid region in FS with center $X$ and radius $r$ . Groups may have a different number of points and the number of similar pixels that pertain to the same group is registered in $B$ . To aggregate in PS, we define a 2-neighbourhood whose points have similar intensity and are physically close. A set of aggregated points in PS is called a bubble.

To aggregate in FS, consider set $\{(p_{k},\chi_{k})\}_{k=1,\ldots,n}$ partitioned into two disjoint subsets $\textit{VS}\cup\overline{\textit{VS}}$ , where VS is the set of visited points and $\overline{\textit{VS}}$ its complement. At the beginning all the points belong to $\overline{\textit{VS}}$ . Select any point $(p_{k},\chi_{k})\in\overline{\textit{VS}}$ . $\chi_{k}$ is the center of a new group $X_{1}$ and the associated set ${B_{1}}=1$ (i.e., $B_{1}$ counts the number of elements in group $X_{1}$ ). Select a radius $r$ . At the $k$ th iteration there are $\ell$ groups with centers $X_{1},\ldots,X_{\ell}$ , $\ell\leqslant k$ . Compute the distance of $\chi_{k}$ to every $\ell$ group center $X_{j}$ , i.e., $d_{kj}$ , with $j=1,\ldots,\ell$ and $d_{kj}=|\chi_{k}-X_{j}|$ . Determine the nearest group to $\chi_{k}$ . Let $X_{\ell_{k}}$ be the nearest group, i.e. $\min_{j=1,\ldots,\ell}\|\chi_{k}-X_{j}\|=\|\chi_{k}-X_{\ell_{k}}\|=d_{{k}{\ell% }_{k}}$ . Then:

1.
If $d_{{k}{\ell}_{k}}>r$ , establish $\chi_{k}$ as the center of a new group: ${X_{\ell+1}}=\chi_{k}$ . Also, set $B_{\ell+1}=1$ and $U(k)=\ell+1$ .
2.
If $d_{{k}{\ell}_{k}}\leqslant r$ , increment $B_{\ell_{k}}\leftarrow B_{\ell_{k}}+1$ and $U(k)=\ell_{k}$ . Point $\chi_{k}$ enters group $X_{\ell_{k}}$ .
3.
$\chi_{k}\in\textit{VS}$ .

For every $k,$ $U$ registers the group $X_{j}$ that $\chi_{k}$ belongs to ( $U_{k}=j$ ).

In the end of the procedure, the FS set $\{\chi_{k}\}_{k=1,\ldots,n}$ is transformed into group set $\{X_{j}\}_{j=1,\ldots,\nu}$ and $\nu\ll n$ . This means that a subset of pixel features is aggregated into $X_{j}$ , i.e., $X_{j}=\{\chi_{j_{1}},\ldots,\chi_{j_{k}}\}$ . Also $X_{j}\cap X_{j}^{\prime}=\emptyset$ and we may have $j_{k}\neq j^{\prime}_{k}$ .

Moreover, as $\{(p_{j_{1}},\chi_{j_{1}}),\ldots,(p_{j_{k}},\chi_{j_{k}})\}$ , this means that group $X_{j}\in\mathbb{R}^{d}$ aggregates a feature subvector that has associated a subset of points in PS: $P_{j}=\{p_{j_{1}},\ldots,p_{j_{k}}\}$ . $P_{j}$ may be decomposed in PS into disjoint proximity bubbles using an euclidean distance and a procedure identical to the one used in FS. That is, points $\{p_{j_{1}},\ldots,p_{j_{k}}\}$ form a bubble if they are inside a 2-neighbourhood. Hence, we may have a total of $\ell$ bubbles associated to every $X_{j}$ :

$\displaystyle P_{j1}=\{p_{1},\ldots,p_{j_{k_{1}}}\},$ $\displaystyle P_{j2}=\{p_{1},\ldots,p_{j_{k_{2}}}\},\ldots,$ $\displaystyle P_{j\ell}=\{p_{1},\ldots,p_{j_{k_{\ell}}}\}.$

Also $P_{j}=\cup_{t=1}^{\ell}P_{jt}$ and $P_{jt}\cap P_{jt}^{\prime}=0$ . Thence, in PS $\{p_{k}\}_{k=1,\ldots,n},$ is transformed into

$\displaystyle\{P_{jt},\}_{j=1,\ldots,\nu,t=1,\ldots,\ell},∼{}\ell\leqslant\nu$

and

$\displaystyle\sum_{j=1}^{\nu}\sum_{t=1}^{k_{\ell}}jt\ll n.$

Define $\mu=\sum_{j=1}^{\nu}$ $\sum_{t=1}^{k_{\ell}}jt$ .

Figure 3.
Definition of the ROIs for UI.

3.2 Training set

The TS is constructed according to the defined ROIs. That is, we select a rectangle for every ROI and every ROI should have one rectangle associated. In Fig. 3 we show the selection of ROI for the UI used in Experiment-2 of Section 5. These rectangles are the classes ${\mathcal{C}}_{i},i=1,2,3$ that correspond to the brain, amniotic sac and uterus, respectively. A fourth class ${\mathcal{C}}_{4}$ corresponds to the edges or contours and is defined by the gradient variation, for what is meant that the gradient variation being above a certain threshold is an indication of an edge. Thus, we have a total of $n_{c}=4$ . As TS is defined as the union of these classes of points, i.e., $\textit{TS}=\cup_{i=1}^{4}{\mathcal{C}}_{i}$ , and every class ${\mathcal{C}}_{i},i=1,2,3,4$ , has $n_{c_{i}}$ points, thus TS has $n_{\textit{TS}}=\sum_{i=1}^{n_{c}}n_{c_{i}}$ points. Also, $n=n_{\textit{TS}}+\overline{n_{\textit{TS}}}$ where $n_{\textit{TS}}$ and $\overline{n_{\textit{TS}}}$ are the number of points that belong to TS and $\overline{\textit{TS}}$ , respectively. Hence

$\displaystyle\textit{TS}=\{(p_{k},\chi_{k}),k=1,\ldots,n_{\textit{TS}}\}.$ (1)

Every point in TS is already classified: $(p_{k},\chi_{k},Y_{k})$ , $k=1,\ldots,n_{\textit{TS}},$ and $Y_{k}\neq 0$ . In every class, ${\mathcal{C}}_{i},$ its points $\chi=\{\chi_{k}:k=1,\ldots,n_{c_{i}}\}$ are aggregated into a set of disjoint similarity groups $X=\cup_{j=1}^{\nu_{c_{i}}}X_{j}$ using the Aggregation Method. Hence

$\displaystyle{\mathcal{C}}_{i}=\{X_{i_{j}},j=1,\ldots,\nu_{c_{i}}:\{\chi_{k}\}% _{k=j_{1},\ldots,j_{k}}\in X_{j}\}.$

Consequently, the whole TS defined in Eq. (1) is transformed into:

$\displaystyle\textit{TS}=\cup_{i=1}^{n_{c}}\{X_{i_{j}},j=1,\ldots,\nu_{c_{i}}:% \{\chi_{k}\}_{k=j_{1},\ldots,j_{k}}\in X_{i_{j}}\}=\{X_{i_{j}},j=1,\ldots,\nu_% {c_{i}}:\{\chi_{k}\}_{k=j_{1},\ldots,j_{k}}\in X_{i_{j}}\}_{i=1,\ldots,n_{c}},$ (2)

and features $(\chi_{k},Y_{k}),k=1,\ldots,n_{c_{i}}$ , are transformed into similarity groups $(X_{j},Y_{j}),j=1,\ldots,\nu_{c_{i}}$ , with $\nu_{c_{i}}\ll n_{c_{i}}$ . TS defined in Eq. (2) may be further structured also in PS. Hence:

$\displaystyle\bm{\textit{TS}}=\{(P_{jt},X_{i_{j}},Y_{j}=i)_{t=1,\ldots,\ell_{j% }},:$ $\displaystyle\{\chi_{k}\}_{k=j_{1},\ldots,j_{k}}\in X_{i_{j}},$ $\displaystyle\{p_{k}\}_{k=j_{1},\ldots,j_{k}}\in\cup_{t=1}^{j_{\ell}}P_{j\ell_% {j}}\},$ (3)

with $i=1,\ldots,n_{c},j=1,\ldots,\nu_{c_{i}}$ , and $\ell_{j}\leqslant j_{k}$ . Also $\bm{n_{\textit{TS}}}=\sum_{i=1}^{\nu_{c}}{\nu}_{c_{i}}\ll n_{\textit{TS}}$ .

3.3

K

-nn algorithm

$K$ -nn algorithm is a non-parametric method for classification and regression whose input is, in both cases, a set of training examples in FS: the $K$ -elements. The output of the algorithm depends on whether is used for classification or regression. In the former case, it consists in the association of every element to one or several pre-defined classes, i.e., an object is classified by a plural vote of its $K$ -neighbours and then assigned to the most common class among them. Neighbours are taken from a set of objects for which the class is known. This can be considered the TS, although no explicit training step is required.

The training examples are vectors in a multidimensional FS, each with an assigned class label. The training phase of the algorithm lies in storing the feature vectors of the training samples and the respective class labels. A peculiarity of the $K$ -nn algorithm is its sensitiveness to the local structure of the data. The algorithm approximates the functions locally, and the entire calculation is deferred until the function is evaluated. Since this algorithm depends on the distance used in the classification task, the normalisation of the training data can significantly improve its accuracy. A useful technique is to assign weights to the neighbour contributions, which awards a larger participation of the closest neighbours to the average. $K$ is a user-defined parameter – the number of nearest neighbours. When $K=1$ the algorithm is known as the nearest-neighbour algorithm, and this is the most intuitive version [20].

The aim of the segmentation algorithm is to classify and partition all the points of the image into $n_{c}$ classes. An unlabelled point is classified by assigning to it the label of the most frequent class among its $K$ nearest neighbours belonging to the TS.

Consider some norm $\|\cdot\|$ on ${{\rm I\!R}^{d}}$ – e.g. the Euclidean, Hamming, Manhattan or Minkowski distance – and a non-classified point of index $\ell$ with feature vector ${X_{\ell}}\in$ Unlabelled Set. Calculate the distance of point ${X_{\ell}}$ to every point of TS and order them. Select the $K$ smallest distances. Hence, consider a sequence of the $K$ ordered distances such that $\{{X_{I(k)}}\}_{k\in I}\subset\textit{TS}$ , where $I$ is the list of indices of the $K$ nearest neighbours training points:

$\displaystyle\|{{X_{I(1)}}-{X_{\ell}}}\|\leqslant\|{{X_{I(2)}}-{X_{\ell}}}\|\leqslant$ $\displaystyle\ldots\leqslant\|{{X_{I(K)}}-{X_{\ell}}}\|.$ (4)

The classification of point- ${\ell}$ is done by the majority vote of its $K$ -neighbours, translated into the score value:

$\displaystyle{S_{j{\ell}}}={\displaystyle\frac{\sum_{k=1}^{K}{{u_{j,I(k)}}{w_{% I(k),\ell}}}}{n_{c_{j}}}},j=1,\ldots,n_{c}$ (5)

for the ${\ell}$ -point to the ${j^{\text{th}}}$ class. ${u_{jr}}$ is the membership value of the $r$ training point that belongs to the $j^{\text{th}}$ class (e.g. ${u_{jr}=1}$ if ${Y_{r}}=j$ and ${u_{jr}}=0$ otherwise). ${w_{I(k),\ell}}$ is the weight of every $k^{\text{th}}$ nearest-neighbour for the point- $\ell$ . Finally, the class with most votes is taken as the prediction, i.e., $Y_{i}$ when ${S_{i{\ell}}}>{S_{j{\ell}}},\forall i\neq j$ . The quality of the classification of the unmarked samples, $X_{\ell}$ -point, is better when the result of the vote is concentrated in a certain class, by expressive clear majority voting. For this we define a measure that we call the certainty belief factor (CBF):

$\displaystyle{C_{i{\ell}}}={\displaystyle\frac{S_{i{\ell}}^{\alpha}}{\sum_{j=1% }^{n_{w}}{{S_{j{\ell}}^{\alpha}}}}},$ (6)

where $\alpha$ is a shape parameter. This measure can be seen as a confidence value of the classification process. Values of $C$ close to 1 reveal high level of confidence and express goodness of the classification.

4. Iterative and simple

\bm{K}

-nn algorithms

Two versions of the $K$ -nn algorithm are implemented to segment the image: (i) the first is a modification of the standard version, that we call $K$ -nn; (ii) the second is an iterative version of the first version where the points are classified by an increasing degree of reliability, that we call IK-nn. An image is viewed as a set of $n$ points, $p_{k}=(x_{k},y_{k})$ , that has associated a $d$ -dimensional feature vector, ${\chi_{k}}\in{{\rm I\!R}^{d}}$ , e.g. the mean or the median value, the variance or the gradient (with the last one being strongly correlated to the variance). Some of these points belong to TS, $(p_{k},{\chi_{k}})\in\textit{TS}\subset{{\rm I\!R}^{d}}$ . The image pixel space is transformed into similarity groups that are applied to the FS. Additionally, for the iterative $K$ -nn version of the algorithm, a PS of pixel bubbles may be also defined associated with the classes.

4.1 Version-1: Refinement of the standard $K$ -nn

To apply the algorithm, we start by selecting $K$ , the number of experts who are to decide about the classification. Its value can be either a percentage or an absolute number of points in TS, which can be either equal for all the classes, $K\in\mathbb{R}$ , or a different number for every class, $K\in\mathbb{R}^{n_{c}}$ .

The whole data has been aggregated in FS and, after the aggregation, has size $\nu$ . It is decomposed into two disjoint sets $X=\textit{TS}\cup\overline{\textit{TS}}$ . The respective vector of the classification of the data into classes $Y$ is defined as $Y_{j}\in\{0,1,2,3,4\}$ . If $X_{j}\in\overline{\textit{TS}}$ then $Y_{j}=0$ . The algorithm has as input the structured reference data $\bm{\textit{TS}}=X=\cup_{i=1}^{n_{\textit{TS}}}X_{j}$ . This data is already classified and the information stored in the $\nu$ -vector $Y:Y_{j}=i$ which means that group-sample $X_{j}$ belongs to class- $i,i=1,\ldots,n_{c}$ ; $B_{j}$ is the weight of every group $X_{j}$ ; $C_{j}$ is the degree of trust in the TS data classification. By default, the reference data is assumed to be well classified and $C_{j}=1,\forall j$ with $\textit{dim}(C)=n_{\textit{TS}}$ .

To classify every point $\ell=1,\ldots,\nu$ , the following steps should be followed:

•
If $Y_{\ell}=0$ , determine the distance of point $X_{\ell}$ to every point of TS order them as in Eq. (3.3) and select the $K$ closest ones.
•
Calculate the similarity of point $X_{\ell}$ with every class by using Eq. (5) and

$\displaystyle w_{I(k),\ell}=\log(B_{I(k)})e^{-\alpha|X_{I(k)}-X_{\ell}|}C_{I(k% )},k=1,\ldots,K,$

where $C_{I(k)}$ is the confidence degree on the classification of reference sample $X_{I(k)}$ .
•
Compute the score value $S_{j{\ell}}$ by Eq. (5). Classify point $X_{\ell}$ into class- $i$ : $Y_{\ell}=i$ with ${\cal C}_{i}$ as the class that gets the highest confidence degree calculated in the previous step.
•
Every classified point $X_{\ell}$ has associated a CBF defined in Eq. (6). This is going to define $Cr(\ell,i)=\mathop{\max}\limits_{i}({{C_{i\ell}}})$ when point- $\ell$ has been classified in class- $i$ . $Cc(\ell,i)=S_{i\ell}\in\mathbb{R}^{n_{c}}$ .

In the end of the procedure all the data is classified, therefore: $Y_{j}\in\{{i,\ldots,n_{c}}\}$ .

Figure 4.
MRI of Experiment 1. Left: ROIs; Right: Features.

Figure 5.
Colour codification of the ROI considered for this MRI, the TS: brain (red), remaining body (green), intra-cranial space (blue) and contours (grey green).

Figure 6.
Final result of the segmentation of the MRI into prescribed ROIs.

Figure 7.
Classification reliability per classes. From left to right: brain, remaining body, intra-cranial space and contours.

Figure 8.
Percentage of points classified in every iteration.

4.2 Version-2: Iterative version of version-1

To start the algorithm, one needs to select $K$ as described in Subsection 4.1. Consider niter to be the number of iterations and define $\alpha\in\mathbb{R}^{2}.$ Similarly to what happens for Version-1, the classification procedure has as input the structured $\bm{\textit{TS}}=X=\cup_{i=1}^{\bm{n_{\textit{TS}}}}X_{j}$ , with $Y, B$ and $C$ having the same meaning as before.

All points $p_{k},k=1,\ldots,n,$ could be aggregated also in PS, i.e., $P=\textit{TS}\cup\overline{\textit{TS}}$ is a vector of size $n$ . We recall that $P=\{p_{1},\ldots,p_{j_{k}}\}$ is associated to $X_{j}\in$ FS and $P$ can be reordered and written like $P$ $=$ $\{p_{1},\ldots,p_{j_{k_{1}}},p_{1},\ldots,p_{j_{k_{2}}},\ldots,p_{1},\ldots,p_% {j_{k_{\ell}}}\}$ according to the bubbles in the PS. $P\in\mathbb{R}^{\nu\times 2}$ and contains all the points of the image. $H$ is a structure that contains the aggregation of points in PS.

Figure 9.

Binary classification results obtained with the $K$ -means clustering algorithm.

Figure 10.

Colour codification of the ROI considered for this UI, the TS: foetus (red), uterus (green), amniotic sac (blue) and contours (grey green).

For every iteration ni $=$ 1: niter.

Version-1 is used to classify all the data using the information stored in $X, Y, H, P$ .

A variable threshold is used to eliminate points classified with low reliability to squeeze the confidence interval. Thus, to define the variable, recall the CBF value for the point as in Eq. (6) and calculate $C_{\min}$ and $C_{\max}$ , which are the minimum and maximum value for points in $\overline{\textit{TS}}$ (i.e., the points that just have been classified and correspond to $Y_{\ell}=0$ ). The reliability of the classification of these points lies within the interval $[C_{\min},C_{\max}]$ . Furthermore, define $f_{x}=(C_{\max}-C_{\min})(1-\frac{ni}{\text{niter}})$ and $\textit{treshold}(ni)=C_{\min}+f_{x}$ ; In the last iteration $f_{x}=0$ and all the points are meant to be classified.

Determine the set of points well classified, that is, points whose CBF value $C_{i\ell}$ is above a certain threshold.

The well classified points move to TS. This means that TS grows in every iteration.

The points classified with low reliability remain in $\overline{\textit{TS}}$ and are meant to be classified again.

5. Results

We want to assess the performance of both versions of the $K$ -nn algorithm presented in this work, using two different images: (i) a MRI shown in Fig. 1a that has a very good level of discrimination; (ii) a UI shown in Fig. 1b with a not so good level of discrimination. The results of the classification obtained with both versions are compared between themselves. Besides, the $K$ -means clustering algorithm [32] is used to validate the results obtained with each $K$ -nn algorithm version.

5.1 Experiment 1

Consider the MRI of Fig. 1b that we want to segment into the following ROI: brain, remaining body, intra-cranial space and contours. In this way, we obtain a TS with 4 classes, $\textit{TS}=\sum_{i}^{4}\mathcal{C}_{i}$ that is shown in Fig. 4a. Its respective features are shown in Fig. 4b.

The degree of discrimination between the classes may be judged from the representation of the group centers in FS that belong to every class in Fig. 5a. One may observe that the brain ( $\mathcal{C}_{1}$ ) and the remaining body ( $\mathcal{C}_{2}$ ) are very inter-twinned classes and this may cause some problems to discern between the two. In IK-nn, TS is augmented in every iteration. The final larger TS is shown in Fig. 5b. In Fig. 5c the Voronoy diagram produced by the $K$ -means clustering algorithm is also represented and, as one can observe, there is total affinity with Fig. 5b. As we have realised, from the observation of Fig. 5, that classes $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are highly intertwined, optionally, we can represent the classification reliability with these two classes associated.

Figure 11.

Final result of the segmentation of the UI into prescribed ROIs.

Figure 12.

Classification reliability per classes. From left to right: foetus, amniotic sac, uterus and contours.

The final result of the classification using both versions of the algorithm is shown in Fig. 6. The result of the segmentation done by both versions of the algorithm is quite good although an attentive eye can see the superiority of the results obtained with the iterative version. However, the big gain in using IK-nn is its higher degree of reliability in the classification, as can be observed by the analysis of Fig. 7.

In these images, white represents the highest level of reliability in the classification and black corresponds to zero reliability. Since these are medical images to be used for diagnosis purposes this becomes very relevant.

Both results are compared with the $K$ -means clustering algorithm. The results obtained with Version-1 show 91% of affinity with the former algorithm and 89.9% with Version-2. However, due to the higher degree of reliability shown by the iterative version, we may conclude that its results are superior. The results of IK-nn were obtained in 5 iterations and the percentage of points classified in every iteration, and meant to engross the TS, are represented in Fig. 8. The fuchsia bar represents the initial reference data.

Figure 9 shows the results of the classification obtained with the $K$ -means clustering algorithm.

Figure 13.

Binary classification results obtained with the $K$ -means clustering algorithm.

Figure 14.

Percentage of points classified in every iteration.

5.2 Experiment 2

Consider the UI of Fig. 1a that we want to segment into the prescribed ROI previously defined and shown in Fig. 3: foetus, amniotic sac and uterus. The representation of the features can be seen in in Fig. 2. Observing Fig. 10a, one sees even more inter-twinning between two classes, i.e., the fetus ( $\mathcal{C}_{1}$ ) and the uterus ( $\mathcal{C}_{2}$ ), than in Fig. 5a of Experiment-1. This is not surprising since this type of images typically have less quality and show higher noise levels.

The final result of the classification using both versions of the algorithm is shown in Fig. 11. As it happens in Experiment-1, the segmentation done by both versions of the algorithm is comparable and the big gain lies also in the higher degree of reliability of IK-nn shown in Fig. 12.

Both results are also compared with the $K$ -means clustering algorithm. The results obtained with Version-1 show 83.6 % de affinity with the former algorithm and 86.9 % with Version-2. Also here, due to the higher degree of reliability shown by IK-nn, we may conclude that the results are superior. Figure 13 displays the results of the classification obtained with the $K$ -means clustering algorithm.

The results of of IK-nn were obtained in 5 iterations and the percentagem of points classified in every iteration and that are meant to engross the TS are meant in Fig. 14. The initial fuchsia bar represents the initial reference data.

6. Conclusion and future work

Since the automatic treatment of images towards diagnosis is nowadays paramount, in this work we studied the segmentation of obstetric images. To improve the results, some pre-processing of the data has been done to extract the features necessary to the application of the algorithm and also to agglomerate the data in both FS and PS. The developed algorithms used for the segmentation of the images are based on the $K$ -nn algorithm. We present two versions, where the first one is a simple refinement of the canonical version and the second is an iterative version of the first. The latter shows a notable degree of attested classification, which makes the classification process, and consequent diagnosis, very dependable.

Both algorithms have been demonstrated in two different experiments, using different technologies images. Very good results have been obtained with the MRI. When applied on UI, the results were not as good but they were still satisfactory given the low quality of the image and the degree of discrimination. The methods have been validated against the $K$ -means clustering and the results coincided in 91.4% for the simple version and in 89.9% for the iterative version for the MRI and in 86.9% and in 83.6% for the UI, respectively. However, for both images, the level of reliability of the iterative method is much higher.

$K$ -nn is a standard machine-learning method that has been used as a classifier or a regression model. It is conceptually simple and has the advantage of being non-parametric, even when the variables are categorical. Its merit, as a medium level classifier algorithm, was also demonstrated in this work. We believe that new algorithms can be developed from the proposed $K$ -nn structure. For instance, new methods of characterisation for $K$ samples, through new CBF measure functions, which take into account information in the TS and PS spaces, should be explored. Furthermore, it is expected that the Self Organising maps (SOM) algorithm could also bring benefits in the best choice of the $K$ reference samples.

Footnotes

Online ISSN: 1469–0705.

References

Kauffman

, Nobel prize for MRI imaging denied to taymond V. damadian a decade ago, Chem Educator 19 (2014), 73–90.

Sharkas

M.A.

Attallah

and Gadelkarim

, Fetal brain abnormality classification from MRI images of different gestational age, Brain Sci 9(9) (2019), 231.

Benson

C.B.

and Doubilet

P.M.

, The history of imaging in obstetrics, Radiology 273(2 Suppl) (2014), S92–110. doi: 10.1148/radiol.14140238.

Kay

and Spritzer

, Magnetic resonance imaging in gynecology, in: Welfare of Women Global Health Programme von Dadelszen

, ed., The Global Library of Women’s Medicine’s, (2008). doi: 10.3843/GLOWM.10067.

Scoutt

L.M.

and McCarthy

S.M.

, Applications of magnetic resonance imaging to gynecology, Top Magn Reson Imaging 2(3) (1990), 37–49.

Lucas

C.F.

, Técnicas de Segmentação e Classificação de Imagens em Exames de Ressonância Magnética Nuclear, PhD thesis, Pontifícia Universidade Católica do Rio Grande do Sul, Faculdade de Engenharia e Faculdade de Informática, Porto Alegre, Brasil, (2014).

Habas

et al., Atlas-based segmentation of the germinal matrix from in utero clinical MRI of the fetal brain 11 (2008), 351–358.

Saleem

S.N.

, Fetal MRI: An approach to practice: A review, Journal of Advanced Research 5(5) (2014), 507–523.

Campbell

, A short history of sonography in obstetrics and gynaecology, Facts, Views and Vision, Issues in Obstetrics, Gynaecology and Reproductive Health 5(3) (2013), 213–229.

10.

Patenaude

et al., The use of magnetic resonance imaging in the obstetric patient, SOGC Clinical Practice Guideline 306 (2014), 349–355.

11.

Sridevi

Mageswari

and Mala

, An experimental study and analysis of different image segmentation techniques, Procedia Engineering 64 (2013), 36–45.

12.

Chen

Wang

and Shen

, Fetal abdominal contour extraction and measurement in ultrasound images, Ultrasound in Medicine & Biology 34(2) (2008), 169–182. doi: 10.1016/j.ultrasmedbio.2007.06.026. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0301562907003377.

13.

Jain

Rawat

and Shrimali

, Automated techniques for the interpretation of fetal abnormalities: A review, Appl Bionics Biomech 2018 (2018), 1–11. doi: 10.1155/2018/6452050.

14.

Motta

et al., A semi-automatic technique for fetus segmentation in 3D ultrasound exams, in: ICCPR ’19: Proceedings of the 2019 8th International Conference on Computing and Pattern Recognition, (2019), 179–186. doi: 10.1145/3373509.3373561.

15.

Gholipour

et al., A normative spatiotemporal MRI atlas of the fetal brain for automatic segmentation and analysis of early brain growth, Scientific Reports 7(1) (2017), 476.

16.

Tourbier

et al., Automatic brain extraction in fetal mri using multi-atlas-based segmentation, in: Medical Imaging 2015: Image Processing Ourselin

and Styner

M.A.

, eds, SPIE 9413 (2015), 248–254, International Society for Optics and Photonics.

17.

Counsell

S.J.

A. Makropoulos

and Rueckert

, A review on automatic fetal and neonatal brain MRI segmentation, NeuroImage 170 (2017), 231–248. doi: 10.1016/j.neuroimage.2017.06.074.

18.

Ebner

et al., An automated framework for localization, segmentation and super-resolution reconstruction of fetal brain MRI, Neuroimage 206(116324) (2020), 77–89. doi: 10.1016/j.neuroimage.2019.116324.

19.

Khalili

et al., Automatic brain tissue segmentation in fetal MRI using convolutional neural networks, Magnetic Resonance Imaging 64 (2019), 77–89. doi: 10.1016/j.mri.2019.05.020.

20.

Cover

and Hart

, Nearest Neighbour Pattern Classification, IEEE Transactions of Information Theory IT-13(1) (1967), 21–27.

21.

Rajini

R.H.

and Bhavani

, Classification of MRI brain images using K-nearest neighbor and artificial neural network, in: IEEE International Conference on Recent Trends in Information technology, ICRTIT 2011, (2011), 563–568.

22.

Venkatesh

and Judith

, MRI brain image segmentation and detection using K-nn classification, in: Medical Imaging 2015: Image Processing, Journal of Physics: Conference Series, (1362), IOP Publishing, (2019), International conference on Physics and photonics Processes in Nano.

23.

Zhang

L.H.

Cai

H.M.

Xian

J.B.

Lin

M.F.

Zheng

Xie

H.N.

Wang

and Yang

Y.Z.

, Using deep-learning algorithms to classify fetal brain ultrasound images as normal or abnormal, Ultrasound in Obstetrics and Gynecology 56(4) (2020), 579–587.

24.

Zimmer

and Akselrod

, Image segmentation in obstetrics and gynecology, The Future of Biomedical Ultrasound 26(Supplement 1) (2020), s39–s40.

25.

Levine

et al., Compedium of Fetal MRI @ONLINE, 2002. http://radnet.bidmc.harvard.edu/fetalatlas/atlas.html.

26.

Miljković

, Image pre-processing tool, Kragujevac J Math 32 (2009), 97–107.

27.

Lohitvisate

Rodtook

Kirimasthong

and Makhanov

S.S.

, Automatic initialization of active contours and level set method in ultrasound images of breast abnormalities, Pattern Recognition 79 (2018), 172–182. doi: 10.1016/j.patcog.2018.01.032. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/ article/pii/S0031320318300451.

28.

Keatmanee

Chaumrattanakul

Kotani

and Makhanov

S.S.

, Initialization of active contours for segmentation of breast cancer via fusion of ultrasound, Doppler, and elasticity images, Ultrasonics 94 (2019), 438–453. doi: 10.1016/j.ultras.2017.12.008. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/ article/pii/S0041624X17306832.

29.

Patrocínio

A.C.

Marques da Silva

A.M.

and Schiabel

, Processamento e análise de imagens médicas, Revista Brasileira de Física Médica 13(1) (2019), 34–48.

30.

Salgado

and Azevedo PerdicoÃ°lis

T.-P.

, Segmentation of foetus brain MRI based on K-nn algorithm, a case study, in: Proceedings of the 12th International Conference on Soft Computing and pattern Recognition (SocPaR 2020) 1383, Yukio Ohsawa, ed., Springer, (2021), Springer Nature.

31.

Canny

, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence 8(6) (1986), 679–698.

32.

Askari

, Fuzzy C-Means clustering algorithm for data with unequal cluster sizes and contaminated with noise and outliers: Review and development, Expert Systems with Applications 165 (2011), 113856. doi: 10.1016/j.eswa.2020.113856.