Faculty of computer science and technology (CST)
Department of automated control systems
Speciality Information systems and technology in engineering and business
The processing of digital images is an extremely important process that has a wide range of applications, ranging from determining the number of the participant's car to the detection of malignant neoplasms in the human body [1].
Segmentation is the process of dividing something into constituent parts, between which there are certain differences. In the case of digital images, segmentation is the process of distributing image pixels to groups within which a certain criterion for the similarity of elements remains. In turn, there is a certain difference between these groups.
Segmentation is one of the most important and difficult tasks in the field of digital image processing. To date, there are a significant number of methods and algorithms for segmentation; each of them has its own strengths and weaknesses. The main principles [2], on which algorithms of image segmentation are built are:
However, despite the diversity, there is no universal approach. Each field of application has its own specifics, because of which the requirements for the segmentation algorithm vary considerably.
The current level of technology development in the field of computer diagnostics makes it possible to provide digitized high-resolution visual information.
Increasing the degree of detail of the image allows you to capture a greater amount of information, which in some areas will have a critical value. Proportional to the volume of information, the volume of images grows. This leads to the fact that existing methods of processing significantly lose efficiency. This situation contributes to the fact that the task of improving the speed and efficiency of image segmentation algorithms is becoming more relevant.
There is a need to find a solution that would provide a significant increase in the productivity of image segmentation methods.
The final qualification work is devoted to solving the problem of increasing the efficiency and productivity of image segmentation algorithms. To find the solution, we propose the use of roving algorithms on the hardware base of modern GPGPUs [3]. As a software platform, the standard of parallel computing OpenCL [4] is chosen, as well as cross-platform object-oriented high level programming language Java [5].
The purpose of the research is to develop tools for the parallel segmentation of three-dimensional images using the methods of swarm intelligence. The main objectives of the research:
Research object: methods for digital images segmentation.
Research subject: parallel image segmentation using swarm algorithms.
As part of the completion of the qualification master's work, receiving theoretical results in the following areas is supposed:
To obtain an experimental evaluation of the theoretical results, it is necessary to develop segmentation tools. The development includes the following steps:
The basis of the method [6] is the representation of the image in the form of a graph in which the vertices are the pixels of the image. The length of edges between vertices is defined by difference between characteristics of two neighboring pixels, on the basis of which segmentation is performed. The value of the edge length is calculated by the formula (1):
The initial stage of the algorithm involves comparing the pixels with 4 (north, south, west, east) or 8 neighbors (intermediate ones are added) . This approach allows you to make a choice in favor of productivity or the quality of the final result. After passing this stage, a large number of disparate segments will be obtained. Further, according to criterion (2), these segments merge:
Fig. 1. Segments merging
In practice, considering program implementation of this algorithm, a more effective approach is to process the array of graph edges, sorted by non-decreasing edge weight. Each edge is checked for the possibility of merging the segments it connects. It should be understood, that at the initial stage, each pixel represents its own segment.
This algorithm is well scalable and allows you to determine the final result, based on current priorities in the direction of improving quality and, as a result, complexity, or in the direction of increasing productivity while maintaining the minimum acceptable quality of the segmentation result.
In addition to the already mentioned possibility of adjusting the number of edges in the graph, there is a method for modifying the calculated formula for the pixels difference (3):
The variables in this formula are determined by the fact that the values of the RGB color model are taken as the estimated pixel characteristics for segmentation. In addition to them, the coordinates of the pixel in three planes (we are talking about three-dimensional images) are added to the formula.
This is just one of the variants of the calculation formula structure. The flexibility of the chosen algorithm provides an opportunity to select the optimal characteristics of pixels that will allow performing high-quality segmentation based on the estimation of the parameters of the original image. Consequently, it is possible to use additional models that will allow an effective evaluation of the original image and on its basis determine the values to be used for segmentation.
At the current stage of the final qualification work implementation it is expected [7] to use the swarm algorithm to efficiently distribute the power of the selected hardware base.
The nature of the bee colony algorithm implies its outstanding level of efficiency when performing the task of distributing available labor resources, which in this case are computing elements of a graphic accelerator capable of performing various tasks in parallel.
Optimization of load distribution using the bee colony algorithm requires a preliminary estimate of the volume and some other criteria for input information.
The basis of the sending approach is the distribution of pixels initial image into a number of blocks on a particular criterion. For each such a block, according to the formula (4), the quantity in the allocated computing elements will be calculated:
Within each block, the allocated elements should be divided into actual working groups, the size of which is determined by the specifications of the chosen software platform of parallelization, as well as the physical structure of the current hardware base.
Key point s image segmentation method described can be schematically represented as follows (Figure 2):
Fig. 2. Segmentation algorithm (Animation: 133 kb, 8 frames, unlim. repeatings number)
It is assumed that the software basis for parallelizing the presented algorithm will be the universal cross-platform standard for parallel computing OpenCL. Among all leading standarts in parallel calculations (CUDA, OpenCL, OpenMP, etc.), the selected one is cross-platform and easily integrated into various systems, the lag in performance from the primary competitor in the face of CUDA is insignificant and with the release of new versions of the standard is becoming even less [8].
To date, a sequential version of the algorithm has been implemented. It is able to segment two-dimensional medical images of MRI, 512 by 512 pixels in size. The program implementation is provided by the Java platform.
During the experiment, image segmentation was carried out by multiple versions of algorithm (using 4-connected and 8-connected graph) for different values of the argument k. The results of time measurements are shown in Table 1.
| № | Connectedness of a graph | k | Time elapsed, sec |
|---|---|---|---|
| 1 | 4 | 300 | 31,188 |
| 2 | 4 | 3000 | 27,438 |
| 3 | 4 | 30000 | 30,971 |
| 4 | 8 | 300 | 35,094 |
| 5 | 8 | 3000 | 34,693 |
| 6 | 8 | 30000 | 35,024 |
The experimental results indicate that, at this stage of the algorithm, the use of 4-connected graph does not give major execution speed advantages. At the same time, from a subjective point of view, the 8-connected graph provides a higher level of quality of the final result. Fig. 3 shows the original image used in the experiment.
Fig. 3 Original image
Figures 4(a) and 4(b) show the results of image segmentation at a value of k = 3000.
Fig. 4. Segmentation results
Final qualifying master’s work is devoted to the research of methods for image segmentation and parallel segmentation tools development, which in the end would reduce the complexity of developing systems, which have medical digital image processing modules as their cores.
At current stage of work performance, the following objectives were achieved:
A further area of research and development will be:
Work is not completed yet. Completion is scheduled for May 2018. The full text and materials on the topic can be obtained from a student or his supervisor only after the specified date.