How is segmentation carried out in image processing

Segmentation in medical image processing


1 Segmentation in medical image processing Definition Segmentation 1 is a sub-area of ​​digital image processing and machine vision. It deals with the creation of content-related areas. Pixels and edges are used to identify these regions. In the field of medical image processing, segmentation is used, for example, in CT (computer tomography) to distinguish organs from one another. It is also used in sonography (ultrasound), echocardiography (heart ultrasound), X-rays and in the various areas of endoscopy. Figure 1: Segmentation of the liver in computed tomography Segmentation is the third step in image analysis 2. After the image is captured, the image material is preprocessed, followed by segmentation. A feature extraction and classification can then be made before a statement is made. In the case of a complete segmentation, each pixel is assigned to at least one segment, whereas the segmentation without overlap assigns to each pixel at most one segment. A segmentation is contiguous if each segment forms a contiguous area. 1 Segmentation: see Martin Dugas, Medical Informatics and Bioinformatics. Springer Berlin 2002, S image analysis: see Martin Dugas, Medical Informatics and Bioinformatics. Springer Berlin 2002, p. 126 Vesna Krnjic

2 Procedures There are several procedures for segmentation, whereby the general rule is that automatic procedures are highly susceptible to errors. Therefore, semi-automatic processes are often used. The processes can basically be divided into pixel, edge and region-oriented. In addition, a distinction is made between processes that assume a certain shape of a segment (model-based) and processes that examine the texture of individual segments in order to also take their internal structure into account (texture-based). Most of the methods are very similar and different methods are used in combination to get a better result. Pixel-oriented methods With pixel-oriented methods, it is decided for each pixel whether it belongs to a certain segment or not. This decision can depend on the surroundings of the pixel. Unfortunately, such methods do not bring closed segments, which is why manual or another method reworking is often necessary. One of the most widespread, pixel-oriented methods is the threshold value method 3, in which a one-dimensional value of the pixel is compared with a threshold value and assigned to a segment on the basis of this. As an example of a pixel-oriented method, a segmentation of Dacron vascular prostheses or of cell adhesion molecules in the neointima of these will be shown. Definition: Dacron vessel: blood vessel near the heart. Cell adhesion molecules: Cell adhesion molecules (CAMs: cell adhesion molecule) are a class of proteins that are responsible for the contact between cells in tissue. They are responsible for the cohesion of tissues and the communication of cells with one another. Neointima: scar tissue of cells, which often forms after an angioplasty or stent treatment in the course of the natural healing process. In the following experiment, the area percentage of the cell adhesion molecules or the most frequently occurring actin is to be determined in the course of the healing process. To do this, the user should first define the total area (draw polygons) and then exclude tissue-free islands 4. 3 threshold value methods: see Thomas Wittenberg, Image Processing for Medicine, Algorithms, Systems, Applications. Springer Heidelberg The image numbers correspond to the result numbers of the Vesna Krnjic macro

3 Original image The output graphic after preprocessing. (Image 1) Reduction of the noise with median filtering A group of pixels is combined and the value of the middle pixel is adopted. (Image 2) Real color segmentation: Binary regions are generated for the measurement. With this method, color values ​​can be assigned to individual segments, in this case two (black and white). (Image 3) Deleting regions with 10 or fewer pixels After you received a binary image in the previous step, you can now very easily sort out groups of pixels. In this case, all groups with a size of 10 pixels or smaller will be deleted. (Fig. 5) Binary mask of an island that is to be excluded from the measurement Using the pixels with a binary value for white, one can identify an island that is enclosed by them. This should be excluded from the measurement later. (Figure 7) Linking the inverted mask from Figure 7 and the mask of the total area (white) by bit-wise AND calculation. A bit-wise ANDing of the base with the new mask creates an inverted binary image. (Fig. 6) Inner and outer contours of the measuring surface The segments to be excluded are replaced by contours, which are closing segments (the upper one is closed by the edge) (Fig. 8) Vesna Krnjic

4 Control image: The measurement regions (image 5) within the measurement area (image 6) are displayed. The result of the segmentation after 7 processing steps of the macro. The threshold value method Definition Threshold value methods are algorithms for segmenting digital images; these methods are among the oldest methods of digital image processing. The basis of a threshold value method is an image with numerical values ​​for the included image points (color values). The affiliation to a segment is decided on the basis of a gray value of a pixel. However, it can also be another one-dimensional feature. In this case, the gray value is the pure brightness value of a pixel; further color information is not taken into account here. One of the most famous processes was developed by Otsu 5 Nobuyuki in 1979. Functionality Normally, a threshold value method generates a binary image, which means that there are exactly two segments (mostly organs are separated from surrounding cavities, fatty tissue, etc.). However, by specifying several threshold values, you can also extract several segments. Figure 2: Binary segmentation with a threshold value Figure 3: Segmentation with several threshold values ​​The resulting segments can have a wide variety of sizes, so there can also be individual pixels in a segment or even form a separate segment, because these methods do not always provide connected segments. The size of the segments can vary greatly depending on the threshold value. If only a collection of threshold values ​​is defined for an image, one speaks of a global threshold value method. Since this method is very susceptible to fluctuations in brightness, there are two other options for a threshold value method. One is the local threshold value method, in which different threshold values ​​are defined for different areas of an image 5 Otsu method: see Rüdiger Kramme, Medizintechnik. Procedures systems information processing. 2nd Edition. Springer Berlin 2002, p. 296 Vesna Krnjic

5 become. The most comfortable method is the dynamic one. Here, the threshold value is dynamically defined for each pixel based on its environment. The decisive factor in the threshold value method is therefore the search for a suitable threshold value. A histogram can be used for this task, in which value maxima are well represented. In the ideal case, a bimodal histogram is obtained (there are two maxima that can be easily distinguished from one another). The mean value of these maxima can now be used as the threshold value, or the minimum value between the two maxima. Logically, the latter usually leads to a better result. Figure 4: Bimodal histogram The histogram should therefore ideally be bimodal, because in this case the simplest procedure, the global threshold procedure, functions largely without interference. But if you already have three maxima, for example, it depends on the respective values ​​whether and how well this procedure works. The local method should always work, but it presents the problem that with increasing maxima the subdivision of the image also becomes more and more complex. That is the reason why a dynamic process brings the best results here. The Otsu method In the Otsu method, statistical aids are used for threshold value analysis, primarily with the variance, the spread of the values, whereby it is the gray values. The scattering creates classes from which the threshold value is determined. The spread within these classes should be as small as possible, outside or between the classes (in the free spaces) as large as possible. The mean value is then calculated and a threshold value is obtained which is as far away from both segments as possible. Edge-oriented processes Edge-oriented processes try to detect transitions between individual segments (edges). The border between two homogeneous surfaces in an image is called an edge. However, these algorithms usually do not yet provide closed edges, which is why a rework is necessary here as well. A well-known method for connecting the individual edges is the live wire method. This searches for the optimal path from edge to edge (mostly over the strongest edge pixels). Finding the optimal way is a general problem in computer science and can be solved, for example, using breadth-first search. The watershed transformation in particular is used in medicine for CT. Vesna Krnjic

6 The border between two homogeneous surfaces in an image is called an edge. The sequence of an edge-oriented segmentation is characterized by the following steps: Smoothing of the image, because the original image is usually noisy and disturbances could thus be extracted as edges. The median filter described is suitable for this purpose, for example. Detection of edges or lines. Filters with Sobel operators can be used for this. In most cases, the detection of the edges and lines is not complete with the previous steps. On the one hand, "wrong" edges, which were mistakenly mistaken for edges due to errors, must be removed. On the other hand, "real" edges that have not been fully recognized and have small gaps as a result, must be completed. The curve pieces created in the previous step must be grouped accordingly, continued and connected to one another. This step creates closed lines that can then be assigned to the object boundaries. Watershed transformation With watershed transformation 6 (WST, watershed transformation), the gray value differences are represented as a relief by converting the values ​​into mountains and valleys. This mountainous landscape is gradually flooded with water; dams are simulated at the mountain peaks, i.e. where the water would otherwise spill over. These dams represent the object boundaries, i.e. the edges. 6 watershed transformation: see Rüdiger Kramme, Medizintechnik. Procedures systems information processing. 2nd Edition. Springer Berlin 2002, p. 599 Vesna Krnjic

7 The problem with this process is that the accuracy of the result decreases as the image noise increases. This difficulty is encountered especially with the CT 7. Of course there are a number of filtering methods, but most of them give unsatisfactory results. The result also depends on the initial image, i.e. the part of the body that was examined. An example of a very useful application is skull CT. Figure 5: Segmentation of a skull CT image with a watershed algorithm It can be seen that there are clear edges with large differences in gray values. However, inaccuracies can be recognized even in this case. Some small, darker islands are not perceived as such; surprisingly, this leads to undersegmentation instead of the oversegmentation that is otherwise common with this method. Watershed transformation variants The hierarchical watershed transformation (hereinafter referred to as WST) is an automatic process. The result is shown here as a graph, whereby the relationship with adjacent, neighboring segments (regions) is determined. Based on this principle, this procedure is carried out recursively over and over again. The problem arises that the watersheds are getting wider, which inevitably leads to inaccurate segmentations. With a marker-based WST, not all areas are flooded, but only certain areas provided with markers. These markers can either be set interactively by the user or using morphological operators. In the case of an interactive marker definition, this method is referred to as semi-automatic and, because of this, is one of the segmentation methods that deliver the best results. The interactive WST also belongs to the semiautomatic segmentation method, but here the proportion of interactive work is considerably larger than in the method described above. Here the user can explicitly define areas as relevant or irrelevant (include and exclude points). The user can also use 7 computer tomography: a medical examination similar to an X-ray. Slice images of the patient's body (or parts of it) are made. To do this, the patient moves lying on a stretcher into a cavity (or a bridge) in which a transmitting and receiving unit rotates around the patient and emits rays and captures the residual radiation (after absorption or reflection of these rays) and into an image converts. After each rotation, the patient is pushed a little bit in one direction, which gives a slice image that can even be converted into a 3D image. See Thorsten M. Buzug, Introduction to Computed Tomography. Springer Berlin 2004 Vesna Krnjic

8 build artificial watersheds yourself. This method has the best results due to the high degree of interaction. Median filter 8 With this filter, the gray value is selected from the middle position of the ordered sequence of surrounding pixels. Figure 6: Ordered surrounding pixels Typical properties of the median filter are: Isolated interference is eliminated without any side effects. Edges and linear gray value gradients remain unchanged. Figure 7: unprocessed skull CT image Figure 8: skull CT image with median filter 8 median filter: see Martin Dugas, Medical Informatics and Bioinformatics. Springer Berlin 2002, p. 124 Vesna Krnjic

9 Sobel operator Sobel operator 9 is a simple linear filter for edge detection with the following filter kernel: The operator is used by convolution by placing the filter kernel in the middle of each pixel and then calculating the sum over all 9 pixels, with each pixel value as well is multiplied by the corresponding coefficient from the filter kernel. The Sobel operator supplies minima or maxima at black-white transitions, which are searched for in order to determine the exact location of the edge. Due to the weighted averaging in the vertical direction, the filter is also robust against slight image noise. Region-oriented segmentation In the case of the pixel-oriented method, the separate consideration of each pixel has proven to be a disadvantage. The region-oriented segmentation 10, on the other hand, tries to include the surroundings of a pixel in the classification. In general, the method works in such a way that it sets a starting point (seed point 11). The starting point is usually chosen at random. The algorithm examines the surrounding points. If the neighboring points meet a certain criterion of the class of the starting point, then they are also assigned to this class. This process is repeated until a pixel in the neighborhood no longer fulfills this condition. If this is the case, a new pixel is set as the starting point. When all pixels belong to one class, the process is ended. There are several methods that decide when a pixel is assigned to a class and when not. We will now take a closer look at two decision methods. Gray value difference to the neighbor The value of the pixel of the class is compared with its unclassified neighbors. If the value falls below a certain limit, the pixel is assigned to the class. A problem arises when the color values ​​slowly increase or decrease in one direction, as with a color gradient. Each pixel is gradually assigned to the class. This can result in areas that contain pixels that are not similar. This problem is called chaining. The undesired concatenation only stops when we hit hard, continuous edges. Using color values ​​would bring about an improvement here. 9 Sobel operators: see Thomas Tolxdorff, Image processing for medicine Springer Berlin 2004, S Region-oriented segmentation: see Rüdiger Kramme, Medizintechnik. Procedures systems information processing. 2nd Edition. Springer Berlin 2002, S English for Saatpunkt Vesna Krnjic

10 Figure 9: Region-oriented segmentation Gray value difference to the starting pixel In this procedure we compare the examined pixel with the starting pixel. So we get a noticeable improvement. Every pixel that is in the immediate vicinity is compared with the gray value of the start pixel. If the value falls below a certain value, the class is expanded to include this pixel. The advantage of this technique is that it does not track gradients indefinitely, and it is quick. However, noise in the image can lead to undesirable class boundaries.There is also a risk of oversegmentation if the start pixel does not represent the region well enough. Gray value difference to the mean gray value This method is a middle ground between the two previous methods. After each expansion of the class, an average is calculated over all points in the class. The advantage is that small areas adapt to the environment through the calculated mean value despite the high degree of pixelation (or interference, blurring or noise). The risk of chaining is also prevented with this method, since the threshold value increases, but not so quickly that such large value differences as can be seen in Figure 9 would be taken into account. The only disadvantage is that the computational effort is increased since the mean value has to be recalculated every time. This naturally results in an exponentially increasing value for the time, the larger the image becomes or the more pixels it has. Vesna Krnjic

11 Example: Region-Growing on an Absomen-SONO The SONO abdomen is an abdominal ultrasound. The following images will show the individual cycles of a region growing procedure 12 in which an image of an ultrasound examination on the abdomen is to be segmented. From the starting point (seed point) the algorithm works its way outwards. Thousands of iterative steps are taken. This is a good example that a pixel-oriented method (which is quite similar to the region-oriented method) would not produce a useful result. The texture at the edge (outside of the abdomen) has too many dark spots which, with a pixel-oriented method, could provide the same distance from the threshold value as the abdomen itself. Texture-based methods These methods are extremely useful in the medical field because organs, bones, etc. usually have a texture that is easy to read for this method. Texture-based methods are not about comparing gray values ​​with threshold values ​​and assigning them to a segment on the basis of these. Here you make use of the visual surface, so to speak. This surface is called texture. A texture does not necessarily have to be of a uniform color; it consists of grooves, cracks, special spots with a darker or lighter color. These properties can be compared with a knowledge database and segmented accordingly, with texture-based methods already reaching into the area of ​​classification. Classification is the next step in image processing (or image analysis). Figure 10: 3D segmentation of the knee joint using a texture-based algorithm 12 Region Growing: see Rüdiger Kramme, Medical Technology. Procedures systems information processing. 2nd Edition. Springer Berlin 2002, p. 599 Vesna Krnjic

12 Bibliography Segmentation Lehmann, Th. Et al, Image processing for medicine, Springer Morneburg, H, (Ed.) Imaging systems for medical diagnostics, Publicis MCD Verlag Jähne, B, digital image processing, 5th edition, Springer Wahl, F, Digital image signal processing, Springer Pratt, W, Digital Image Processing, Wiley & Sons Parker, JR, Algorithms for Image Processing and Computer Vision, Wiley & Sons Sonka, M. and Fitzpatrick, JM (Eds.) Handbook of Medical Imaging, Vol. 2 , SPIE Press Martin Dugas Medical Informatics and Bioinformatics, Springer Berlin Thomas Tolxdorff Image processing for medicine 2004, Springer Berlin Pixel-oriented methods (threshold value method) Otsu, N, A threshold selection method from gray level histograms, IEEE Trans. System Man and Cybernetics, Vol. 9, Thomas Wittenberg Image processing for medicine Algorithms, systems, applications Springer Heidelberg Vesna Krnjic

13 Edge-oriented methods (watershed transformation) Cutrona, J. and Bonnet, N, Two methods for semi-automatic image segmentation based on fuzzy connectedness and watersheds, VIIP Tizhoosh, Hamid R, Fuzzy image processing, Springer Region-oriented methods (Region-Growing) Rüdiger Kramme Medical technology. Procedures systems information processing, 2nd edition. Springer Berlin Computed Tomography Thorsten M. Buzug Introduction to Computed Tomography, Springer Berlin Vesna Krnjic