# Fast Evaluation of Segmentation Quality with Parallel Computing

Authors: Henry Cruz; Martina Eckert; Juan M. Meneses; J. F. Martínez
Journal: Scientific Programming
 (2017)

---

## Abstract

In digital image processing and computer vision, a fairly frequent task is the performance comparison of different algorithms on enormous image databases. This task is usually time-consuming and tedious, such that any kind of tool to simplify this work is welcome. To achieve an efficient and more practical handling of a normally tedious evaluation, we implemented the automatic detection system, with the help of MATLAB®’s Parallel Computing Toolbox™. The key parts of the system have been parallelized to achieve simultaneous execution and analysis of segmentation algorithms on the one hand and the evaluation of detection accuracy for the nonforested regions, such as a study case, on the other hand. As a positive side effect, CPU usage was reduced and processing time was significantly decreased by 68.54% compared to sequential processing (i.e., executing the system with each algorithm one by one).


---

## Body

## 1. Introduction

Segmentation usage, for the detection and extraction of objects of interest from images, plays a very important role in digital image processing. Over the last 20 years, a large variety of segmentation methods have been developed.When researchers test out a new algorithm, they have to pass it through a very lengthy process. It has to be compared with state-of-the-art methods with all results evaluated for quality. Therefore, different metrics are used to compare the segmentation result with a Ground Truth (GT) [1], which is a segmentation considered to be “perfect” and which has normally been obtained manually by human experts, who classified every pixel into forested and nonforested regions. At the end, a binary image is generated and this image represents a pattern of comparison. However, the GT extraction can be subjective. In order to achieve more precision, it is necessary for more than one expert to participate in the extraction process. Another way to find the GT is through automatic segmentation and based on a precise method, the binary image obtained can be considered a comparison pattern.These metrics are pattern evaluation methods and are based on genetic programming [2], the Variance of Information (VoI), entropy analysis [3], maximum interregion similarity [4], under- and oversegmentation [5], and others [1]. In general, they can be classified as analytical, supervised or unsupervised evaluation methods [3, 4].The process of evaluation by comparison with a GT has to be performed individually. This means that, for each algorithm to be tested, multiple evaluations are carried out, one for each metric. For example, in [6], a comparison of different segmentation methods, against a manually obtained Ground Truth, is used to evaluate the quality of the segmentation in the extraction of vegetation leaves. Furthermore, the process has to be executed over huge datasets, which results in high computer processing costs and is a time-consuming task for the researcher. Our approach aims at enhancing the efficiency of the testing phase. Computer resources and processing times will be reduced by using a multithreaded architecture that avoids repeated sequential processing. We prove greater efficiency by applying the tool to a specific use case: the evaluation and comparison of the performance of five segmentation algorithms as part of an automatic detection method for nonforested areas in tropical forests (see the outline of the general process in Figure 1). As the areas to detect have unpredictable and highly irregular shapes, these kinds of images are very useful for testing the performance of the multithreaded evaluation tool.Figure 1
General workflow for region detection evaluation.The technique of multithreading takes advantage of a multiprocessor architecture and can reduce information losses and latency delays [7]. One of the first works on the implementation of a parallel technique, to evaluate segmentations using multiple metrics, was presented in [8]; here, a coevaluation framework was proposed. The segmentations are continuously evaluated, and the final values are automatically adjusted through machine learning techniques to correct errors. This allows an adaptive improvement of segmentation quality. However, the computational costs are still too high. In [2], segmentations are evaluated by genetic programming in a parallel processing structure. That proposal also demands high computational costs and elevated training time.


### 1.1. Use Case Overview

The parallelization process we present in this work is generic and can be applied to any system that is composed of individual processing steps, where some of them could be exchanged by different algorithms and tested for comparison. Here, all these algorithms would be implemented in parallel, and results could be compared instantly, avoiding the repetitive execution of the whole system.In our case, the system is composed of the following steps, where the highlighted ones are those to be parallelized:(1)
Image acquisition(2)
Image segmentation followed by binarization(3)
Visualization of binarized images(4)
Data load (Ground Truth)(5)
Evaluation of segmentation qualities and detection accuracy with multiple metrics(6)
Visualization and storage of final results.The diagram in Figure 1 shows the general workflow when Superpixel Segmentation is applied in step (2).The selected segmentation algorithms are our own method called NFDI (Nonforest Detection Index) which is currently in the process of being published [9], Chan Vese [10], active contours based region extraction [11], region growing by graph cuts [12], and the Superpixels method [13]. These segmentation methods were chosen as they are usually used in the detection of deforested areas [14] and this enables us to determine which methodology is better. Each method defines its own rules. In addition, these methods were selected for the following reasons:(1)
Chan -Vese: this method uses active contours without edges and identifies the minimum level of energy required to separate nonforested zones from the rest. It adjusts efficiently to irregular contours and also tracks small details.(2)
Region extraction based on active contours: This method is used to obtain the closed boundary and irregular contours of nonforest areas, taking into account energy concentration. It is also able to localize specific regions in heterogeneous images. The processing time is efficient when there is no complexity in the deforested zone.(3)
Region growing by graph cuts: this method generates a cluster of neighbour pixels with the same characteristics. It has the capacity to mark objects with backgrounds precisely and to adjust them exactly to irregular borders in ambiguous images of deforested zones. However, processing time can be very slow, which limits its application in real scenarios due to big amount interactions required to execute segmentations of deforested zones.(4)
The Superpixels method: this is a segmentation method based on analysis of similarity or dissimilarity between regions, taking into account brightness, texture, and low contour energy. This method is especially interesting due to its ability to adhere to deforested area boundaries, speed, and exceptional computing efficiency. It improves segmentation performance and depending on the levels of interaction is most convenient in real-time executions.(5)
The NFDI is a method based on histogram analysis that allows the user to establish chromatic relations and execute algebraic operations in order to separate out relevant objects in the background. This method is able to adjust the deforested zone contours in an exceptional way, avoiding confusions due to shadows, texture similarity, or partial occlusions. Although processing times are slower than the methods described above, it is useful for real-time applications.Image segmentation quality is very important in the evaluation of performance methods, as it is necessary to know which method adjusts to these irregularities with fewer errors, avoiding oversegmentation (excess detail) or undersegmentation (loss of detail), inaccurate outlines, and noncoincidence of areas. To measure segmentation qualities, we selected the following widely used metrics: the Global Consistency Error (GCE), proposed by Martin et al. [15] (see (1)), evaluates over- and undersegmentation; the Object Level Consistency Error (OCE), developed by Polak [5], evaluates oversegmentation where values closer to zero are considered better (see (2)); the Random Index (RI), introduced by Rand [16] in (3), computes a comparison of segmentations (GT against output) by assessing the points of coincidence; the metric values closer to one represent a perfect match; and the analysis of the Variance of Information (VoI), proposed by Meila [3] is shown in (4), where the lower values of VoI represent a better result. The comparative relation of valid information between both segmentations leads to a higher certainty of valid information, to reach greater homogeneity, thus reducing entropy. These measures are performed in step (5). (1)GCE=1nmin⁡∑iESe,Sa,pi,∑iESa,Se,pi,(2)OCESe,Sa=min⁡Ee,a,Ea,e,(3)RISa,Se=nt+nunt+nu+nv+nw.(4)VoISa,Se=HSa+HSe-2·ISa,Se,where Se represent the GT segmentation (by a human expert), Sa the automatic segmentation, pi the total of pixels of interest involved in the interest region, and n the total number of pixels in the image. E represents the local refinement error and Ee,a the refinement error from expert segmentation in relation to the automatic segmentation and Ea,e the reverse. For RI, nt represents the number of pixels coinciding with GT for Sa and Se, nu is the number of pixels differing from GT for Sa and Se, nv is the number of pixels coinciding with GT for Sa but differing for Se, and nw represents the number of pixels differing from GT for Sa but coinciding for Se. In addition, nt+nu represent the coincidences between Sa and Sewhile nv + nw represent the noncoincidence between Sa and Se, and finally for VoI, HSa is the entropy of Sa, H(Se) is the entropy of Se, and ISa,Se is the coinciding information of Sa and Se.In the field of computer vision, the accuracy of detection depends on the quality of the classifier, which is commonly evaluated by a confusion matrix. In the case of deforested areas, true positives (TP) mean correctly detected pixels (deforested); false positives (FP) detect deforestation where it does not exist; true negatives (TN) are correct detection of vegetation and false negatives (FN) are incorrect detection of vegetation. The values obtained through TP, FP, TN, and FN are used to validate detection accuracy by metrics like precision (p), recall (r), false positive rates (FPR), Jaccard Index (JI), Jaccard Distance Index (JDI), and Dice Index (DI) also called F-measure (Fm) or F-score (Fs).In particular, precision or accuracy and “recall” (r) are two fundamental statistical variables that allow us to establish how effective a segmentation or detection algorithm has been. The precision (p) measures proximity between the result of the detection, based on an algorithm, and a standard comparison or the expected result of detection. In general terms, it is the percentage of hits. The relationship describing this parameter is expressed as follows:(5)p=TPTP+FP.On the other hand, the sensitivity allows us to establish the algorithm’s performance level, as the number of effective detection incidents are evaluated against the total number of detection incidents expected. The sensitivity is calculated by the following expression:(6)r=TPTP+FN.The rate of false positives (FPR) is the ratio between errors and hits. When FPR tends to zero, this means that the detection is better with a minimal amount of false positives. The relationship is presented as follows:(7)FPR=FPTP+TN.Another important metric that has been considered is the Jaccard Index (JI), as it is a measure to establish the degree of similarity between the proposed algorithm and the GT. This index describes the relation between correct detection and failures. The closer JI to one, the better the result. It is represented here as follows:(8)JI=TPTP+FP+FN.In contrast to JI, the Jaccard Distance Index (JDI) is a measure of dissimilarity. This measure is obtained by subtracting JI from one (1-JI), such that the best result is obtained when the JDI value approaches zero.The Dice Coefficient or Dice Index (DI) is another metric that measures similarity between a segmentation or detection algorithm and the GT. The DI generally determines the algorithm’s performance by considering both precision and sensitivity in the evaluation. The DI is also known as a precision refinement coefficient (F-measure or F-score) and its expression is shown as follows:(9)Fm=2∗p·rp+r.The Fm establishes the overall accuracy of a system and in this case shows the degree of accuracy of the segmentation or detection; when the value of Fm approaches 1 (100%), there is a greater degree of refinement of a method or algorithm.To avoid the execution of the whole program five times (to test five segmentation algorithms, each time over a huge dataset), the algorithms outlined were implemented in parallel in step(2). In this way, each test image had to be loaded only once, and all five results could be handled in parallel, visually comparing the results and saving the quality metrics into data files. As a logical consequence, the 5th step of metric calculation also had to be parallelized to obtain all metrics for the five results simultaneously.Results show that this method speeds up evaluation and increases computational efficiency. Therefore, it represents a useful strategy for carrying out evaluation tasks. The main contributions of this work are as follows:(i)
The proposal of a multithreaded tool for the simultaneous execution of different segmentation algorithms, followed by the evaluation of detection accuracy and processing times(ii)
An original and helpful strategy to be used in evaluation tasks in the fields of digital image processing and computer vision(iii)
High performance resources in comparison with traditional procedures, due to reduced processing time and computational resources.The rest of the article is organized in the following way: Section 2 shows the methodology used to execute multiple parallel tasks for the evaluation of both image segmentation quality and detection accuracy of deforested areas. In Section 3, we present the experiments that validate the proposed tool together with the main results, while Section 4 describes the main conclusions. To complete the article, we add a tutorial that explains the most important steps needed to create a parallel algorithm, giving our code generated for the presented use case as an example.


## 1.1. Use Case Overview

The parallelization process we present in this work is generic and can be applied to any system that is composed of individual processing steps, where some of them could be exchanged by different algorithms and tested for comparison. Here, all these algorithms would be implemented in parallel, and results could be compared instantly, avoiding the repetitive execution of the whole system.In our case, the system is composed of the following steps, where the highlighted ones are those to be parallelized:(1)
Image acquisition(2)
Image segmentation followed by binarization(3)
Visualization of binarized images(4)
Data load (Ground Truth)(5)
Evaluation of segmentation qualities and detection accuracy with multiple metrics(6)
Visualization and storage of final results.The diagram in Figure 1 shows the general workflow when Superpixel Segmentation is applied in step (2).The selected segmentation algorithms are our own method called NFDI (Nonforest Detection Index) which is currently in the process of being published [9], Chan Vese [10], active contours based region extraction [11], region growing by graph cuts [12], and the Superpixels method [13]. These segmentation methods were chosen as they are usually used in the detection of deforested areas [14] and this enables us to determine which methodology is better. Each method defines its own rules. In addition, these methods were selected for the following reasons:(1)
Chan -Vese: this method uses active contours without edges and identifies the minimum level of energy required to separate nonforested zones from the rest. It adjusts efficiently to irregular contours and also tracks small details.(2)
Region extraction based on active contours: This method is used to obtain the closed boundary and irregular contours of nonforest areas, taking into account energy concentration. It is also able to localize specific regions in heterogeneous images. The processing time is efficient when there is no complexity in the deforested zone.(3)
Region growing by graph cuts: this method generates a cluster of neighbour pixels with the same characteristics. It has the capacity to mark objects with backgrounds precisely and to adjust them exactly to irregular borders in ambiguous images of deforested zones. However, processing time can be very slow, which limits its application in real scenarios due to big amount interactions required to execute segmentations of deforested zones.(4)
The Superpixels method: this is a segmentation method based on analysis of similarity or dissimilarity between regions, taking into account brightness, texture, and low contour energy. This method is especially interesting due to its ability to adhere to deforested area boundaries, speed, and exceptional computing efficiency. It improves segmentation performance and depending on the levels of interaction is most convenient in real-time executions.(5)
The NFDI is a method based on histogram analysis that allows the user to establish chromatic relations and execute algebraic operations in order to separate out relevant objects in the background. This method is able to adjust the deforested zone contours in an exceptional way, avoiding confusions due to shadows, texture similarity, or partial occlusions. Although processing times are slower than the methods described above, it is useful for real-time applications.Image segmentation quality is very important in the evaluation of performance methods, as it is necessary to know which method adjusts to these irregularities with fewer errors, avoiding oversegmentation (excess detail) or undersegmentation (loss of detail), inaccurate outlines, and noncoincidence of areas. To measure segmentation qualities, we selected the following widely used metrics: the Global Consistency Error (GCE), proposed by Martin et al. [15] (see (1)), evaluates over- and undersegmentation; the Object Level Consistency Error (OCE), developed by Polak [5], evaluates oversegmentation where values closer to zero are considered better (see (2)); the Random Index (RI), introduced by Rand [16] in (3), computes a comparison of segmentations (GT against output) by assessing the points of coincidence; the metric values closer to one represent a perfect match; and the analysis of the Variance of Information (VoI), proposed by Meila [3] is shown in (4), where the lower values of VoI represent a better result. The comparative relation of valid information between both segmentations leads to a higher certainty of valid information, to reach greater homogeneity, thus reducing entropy. These measures are performed in step (5). (1)GCE=1nmin⁡∑iESe,Sa,pi,∑iESa,Se,pi,(2)OCESe,Sa=min⁡Ee,a,Ea,e,(3)RISa,Se=nt+nunt+nu+nv+nw.(4)VoISa,Se=HSa+HSe-2·ISa,Se,where Se represent the GT segmentation (by a human expert), Sa the automatic segmentation, pi the total of pixels of interest involved in the interest region, and n the total number of pixels in the image. E represents the local refinement error and Ee,a the refinement error from expert segmentation in relation to the automatic segmentation and Ea,e the reverse. For RI, nt represents the number of pixels coinciding with GT for Sa and Se, nu is the number of pixels differing from GT for Sa and Se, nv is the number of pixels coinciding with GT for Sa but differing for Se, and nw represents the number of pixels differing from GT for Sa but coinciding for Se. In addition, nt+nu represent the coincidences between Sa and Sewhile nv + nw represent the noncoincidence between Sa and Se, and finally for VoI, HSa is the entropy of Sa, H(Se) is the entropy of Se, and ISa,Se is the coinciding information of Sa and Se.In the field of computer vision, the accuracy of detection depends on the quality of the classifier, which is commonly evaluated by a confusion matrix. In the case of deforested areas, true positives (TP) mean correctly detected pixels (deforested); false positives (FP) detect deforestation where it does not exist; true negatives (TN) are correct detection of vegetation and false negatives (FN) are incorrect detection of vegetation. The values obtained through TP, FP, TN, and FN are used to validate detection accuracy by metrics like precision (p), recall (r), false positive rates (FPR), Jaccard Index (JI), Jaccard Distance Index (JDI), and Dice Index (DI) also called F-measure (Fm) or F-score (Fs).In particular, precision or accuracy and “recall” (r) are two fundamental statistical variables that allow us to establish how effective a segmentation or detection algorithm has been. The precision (p) measures proximity between the result of the detection, based on an algorithm, and a standard comparison or the expected result of detection. In general terms, it is the percentage of hits. The relationship describing this parameter is expressed as follows:(5)p=TPTP+FP.On the other hand, the sensitivity allows us to establish the algorithm’s performance level, as the number of effective detection incidents are evaluated against the total number of detection incidents expected. The sensitivity is calculated by the following expression:(6)r=TPTP+FN.The rate of false positives (FPR) is the ratio between errors and hits. When FPR tends to zero, this means that the detection is better with a minimal amount of false positives. The relationship is presented as follows:(7)FPR=FPTP+TN.Another important metric that has been considered is the Jaccard Index (JI), as it is a measure to establish the degree of similarity between the proposed algorithm and the GT. This index describes the relation between correct detection and failures. The closer JI to one, the better the result. It is represented here as follows:(8)JI=TPTP+FP+FN.In contrast to JI, the Jaccard Distance Index (JDI) is a measure of dissimilarity. This measure is obtained by subtracting JI from one (1-JI), such that the best result is obtained when the JDI value approaches zero.The Dice Coefficient or Dice Index (DI) is another metric that measures similarity between a segmentation or detection algorithm and the GT. The DI generally determines the algorithm’s performance by considering both precision and sensitivity in the evaluation. The DI is also known as a precision refinement coefficient (F-measure or F-score) and its expression is shown as follows:(9)Fm=2∗p·rp+r.The Fm establishes the overall accuracy of a system and in this case shows the degree of accuracy of the segmentation or detection; when the value of Fm approaches 1 (100%), there is a greater degree of refinement of a method or algorithm.To avoid the execution of the whole program five times (to test five segmentation algorithms, each time over a huge dataset), the algorithms outlined were implemented in parallel in step(2). In this way, each test image had to be loaded only once, and all five results could be handled in parallel, visually comparing the results and saving the quality metrics into data files. As a logical consequence, the 5th step of metric calculation also had to be parallelized to obtain all metrics for the five results simultaneously.Results show that this method speeds up evaluation and increases computational efficiency. Therefore, it represents a useful strategy for carrying out evaluation tasks. The main contributions of this work are as follows:(i)
The proposal of a multithreaded tool for the simultaneous execution of different segmentation algorithms, followed by the evaluation of detection accuracy and processing times(ii)
An original and helpful strategy to be used in evaluation tasks in the fields of digital image processing and computer vision(iii)
High performance resources in comparison with traditional procedures, due to reduced processing time and computational resources.The rest of the article is organized in the following way: Section 2 shows the methodology used to execute multiple parallel tasks for the evaluation of both image segmentation quality and detection accuracy of deforested areas. In Section 3, we present the experiments that validate the proposed tool together with the main results, while Section 4 describes the main conclusions. To complete the article, we add a tutorial that explains the most important steps needed to create a parallel algorithm, giving our code generated for the presented use case as an example.


## 2. Methodology

The multithreaded application has been developed using the Parallel Computing Toolbox of MATLAB R2015b [17], which provides new procedures to carry out several processes simultaneously (such as multitasking) on multicore platforms. These procedures have been applied in parts of the process whose algorithms we wish to interchange, as explained above. The process contains two main parts which are computationally intensive: image segmentations followed by binarization on the one hand and the evaluation of segmentation qualities and detection accuracy by multiple metrics on the other hand. Only in those parts, tasks have been parallelized; all other steps are still performed sequentially. The data load (step (4)) could be omitted, but as results are stored in memory, it has been included as a possibility of separating the whole process into two parts, which could be performed individually if needed and to add flexibility during substitution of the individual algorithms. Figure 2 shows the resulting process workflow with the parts mentioned implemented as multitasks.Figure 2
Workflow of the parallelized process, where the gray shaded parts are the tasks running on multiple threads. Right: example images and segmentation algorithms for the case study presented here.The system architecture considers two types of parallelism: a parallelism of control and another of data. The control parallelism is executed especially when carrying out processes of segmentation and evaluation of each of the methods, as they are executed simultaneously and with a balanced workload. On the other hand, the data parallelism is presented by sharing matrix information of the original image, the matrix of the GT image, and parameters of the confusion matrix. In Figure3, a graphic diagram of the parallelism architectures used in each of the processes is presented.Figure 3
Parallel architecture used in the evaluation of different methods of segmentation through multithreads.The control parallelism allows us to execute all segmentations at the same time and independent of each of the available processors. In this approach, a first phase of decomposition of the program into tasks or “cases” (T) is performed and a simultaneous execution of the segmentations is defined. Then, the algorithm base of the segmentations, in parallel form in this case, will be composed of five tasks: T1,T2,T3,T4,T5, such that all cases are executed simultaneously, with each task lasting a predetermined time t1,t2,t3,t4,t5, as each segmentation method has a different execution time, as does each metric to be evaluated. The architecture has been designed in such a way that when a processor is free, it immediately assists in the processing of the remaining ones, such that the computational load is distributed in a balanced way. This assures that the processing time required to execute a segmentation in parallel (ts) is equal, regardless of the method chosen. Similarly, the time required by each metric to execute (te) and the total processing time to execute the parallel segmentations (Tpp) will be the sum of the partial times so that Tpp=5ts estimates the total time by parallelism in the same way that it takes all the metrics to execute (Tep).Another advantage of using a parallel architecture is the reduction of communication times (tc) by sharing information of common use and avoiding redundant calculations. Since tc is equal in this case, the total communication time (Tc) will be 3tc. Sharing information through data parallelism ensures computational efficiency, especially considering the matrix structure of the information that MATLAB handles. Exploiting data parallelism comes from the realization that certain applications act on regular data structures (image matrices, data of the confusion matrix), repeating the same calculation on each element of the structure; in this way, the algorithm manipulates regular data structures. The idea is to exploit the regularity of data by performing the same calculation on different data in parallel; for example, if a segmentation is performed under method A, this method will use the same information of the original image matrix as method B or C, and so forth. Moreover, the data obtained from the coordinates of the confusion matrix will be used to apply metrics A, B or C, and so forth, so that in this type of parallelism it associates the data directly with the processors. As calculations are performed in parallel on identical processors, it is possible to centralize control. As the data are similar, the repeat operation takes the same communication time on all processors, and the controller sends the operation to all processors synchronously.This type of parallelism can be explained considering whetherp processors are available and whether a series of T are executed. As Aguilar and Leiss defined, two basic operations are presented in the parallelism of data, it can be expressed such as Φ-notation and ρ-reduction. Φ-notation is described by a function f of dimension m and m vectors of the same size. Φ-notation applies the function f on the set of vectors in parallel. The ρ-reduction operation is a binary function f on a single vector r, such that the function f is applied to the first two elements of v, and then f is applied to the result of the preceding calculation and the next element of vector v [18]. Both Φ and ρ are general enough to express a large number of operations on regular data, such as vectors and matrices, when attempting to exploit data parallelism. In the Φ-notation, for example, the operation r(Φ(+v1,v2)) sums the vectors v1 and v2 to produce the result vector r; this allows the occurrence of data parallelism. In the ρ-reduction, for example, ρ(+,v) computes the sum of all elements of vector v. With certain changes in this operation, to exploit the associative property (of division of tasks), it is possible to generate a parallel execution scheme.


### 2.1. Initialization of the Multitask System

In the first subprocess, the system prepares the assignation of the tasks. Therefore, it defines the sequence of tasks for each algorithm and assigns them to the processors (or cores) using theparpool function provided by the Parallel Toolbox. To achieve optimum performance, the number of threads should be equal to the number of cores (CPUs). If there were more threads than processors available, some cores would have to execute multiple tasks. The result is an increment in the processing time and a lack of uniformity in processing capacity. In this case, evaluating running time would not be valid, as the processing capacity of one CPU had to be divided between two threads.The Parallel Toolbox of MATLAB appliesworker threads and uses the local profile, which is a default setting of the toolbox. After initialization, the work folder and its subfolders are added to the search route of MATLAB. Therefore, it is not necessary to make specifications about where the functions and files are, provided that they are located in one of those subfolders.In our case, five segmentation algorithms will be tested. Therefore, fiveworker threads are defined for calculations and for presenting the resulting information on the screen. In this way, each worker executes the tasks declared in a script that contains all segmentation methods to be evaluated in parallel.


### 2.2. Execution of Segmentations and Presentation of Interim Results

The main purpose of the presented work is the parallel execution of segmentation algorithms included in the process of our use case. The reason is that they consume most computational resources and therefore are the key to achieving lower processing times and reduced total computational costs.To perform multiple segmentations in parallel, the source image is processed by a multitask system which assigns one segmentation method to each thread. For the use case presented here, the five segmentation algorithms outlined above were applied to compare the performances of those methods to find the best one.The segmentation methods are assigned ton case structures, such that there are as many cases as segmentation methods (1 to n being the ID numbers). The instruction smpd obtains the IDs and assigns one “worker” to each segmentation process with the help of the instruction switch case. Each case contains a list of tasks to be performed by the assigned worker (in our cases segmentation, calculation of evaluative parameters, representation of the state of execution on the screen, etc.). Figure 4 shows an example of a process running with five workers in parallel. On the right, the progress status window is shown, which informs us about the state of execution during metrics evaluation (in this case, with OCE).Figure 4
Above: command window during a process with 5 workers. Below-right: progress status window.The variables used by each thread become part of another value of type composite, which is a special kind of array. It has the same number of elements as worker processes exist and is useful to recover data from former segmentations. To avoid problems, in case that other applications are executed at the same time, the Matlab search route, the directories, and the previously created subdirectories should be eliminated to avoid overwriting or confusion.After executing the segmentations, the resulting binary images are saved in a directory named results within a subfolder called Binary_seg. Another interim result is the processing time used by the segmentation algorithm (Tp). All Tp measures are displayed on the screen and saved in MATLAB and Excel files. The sidebar illustrates the process with the help of parts of our code.


### 2.3. Data Load and Comparisons

The data load and comparisons are complementary tasks with no need for parallelization. The data load is executed three times to load the source image, the GT, and the binary images obtained by each segmentation process from a subfolder. Afterwards, the processing timetables stored for each segmentation method are also loaded. The path to the images can be manually introduced or predefined. The loaded images are used for the presentation of interim results and to calculate the evaluation metrics as described in the following section.


### 2.4. Evaluation of Segmentation Quality and Detection Accuracy

The evaluation of segmentation quality and detection accuracy is the second main task developed in this tool. The comparison of all binarized segmentation results with the GT is performed by analyzing the pixel coincidence. Therefore, TP, FP, FN, and TN are calculated first. The segmentation quality is then evaluated by GCE, OCE, RI, and VoI metrics whereas the detection accuracy is measured withp, r, FPR, JI, JDI, DI, and Fs metrics. Therefore, five cases executed in parallel are created in the following manner to distribute the calculation time symmetrically:Case  1: GCECase  2: OCECase  3: RI, VoICase  4:p, r, FPR, JI, JDI, Fs, DICase  5: Data storage, presentation of results.Cases  1, 2, and 3 contain algorithms with high computational complexity, Case  4 joins multiple computations which make use of the formerly obtained values for TP, FP, FN, and TN. Finally, the last case has been defined for complementary tasks as data storage, and so forth. All cases are assigned with the help of the parpool instruction as in the segmentation part.


### 2.5. Final Results and Data Display

We opted to display the results obtained by the multithread process graphically and numerically and store segmentations and automatic detection in  .jpeg format. The results related to time processing, segmentation quality, and accuracy detection are saved in both  .xls and  .mat files, as already shown in Figure 2.In order to present the outcomes in a balanced way, we used a distributed scheme. The segmentation images stored in the subfolder are considered as outcomes. Through new multithreads, the presented software generates the contours in the binary images, which are then overlapped with the source images. This procedure is implemented in parallel for each evaluated segmentation method. The outcomes are stored in specific results folders.The numerical data obtained from automatic evaluation through multithreads (quality rates and the processing time) is also saved in the results folder. In order to obtain  .xls data, it is necessary to carry out a conversion of the data (.mat) to a table (.xls). The stored data is shown in the form of a table on the console. Additionally, a nondestructive system for saving data was implemented to avoid overwriting during each software execution. Figure 5 shows how the results are shown on the console and how they appear in the  .xls file for the example evaluation over a test image.Figure 5
Above: visualization of the working environment as results are shown. Below: simultaneously stored Excel table.


## 2.1. Initialization of the Multitask System

In the first subprocess, the system prepares the assignation of the tasks. Therefore, it defines the sequence of tasks for each algorithm and assigns them to the processors (or cores) using theparpool function provided by the Parallel Toolbox. To achieve optimum performance, the number of threads should be equal to the number of cores (CPUs). If there were more threads than processors available, some cores would have to execute multiple tasks. The result is an increment in the processing time and a lack of uniformity in processing capacity. In this case, evaluating running time would not be valid, as the processing capacity of one CPU had to be divided between two threads.The Parallel Toolbox of MATLAB appliesworker threads and uses the local profile, which is a default setting of the toolbox. After initialization, the work folder and its subfolders are added to the search route of MATLAB. Therefore, it is not necessary to make specifications about where the functions and files are, provided that they are located in one of those subfolders.In our case, five segmentation algorithms will be tested. Therefore, fiveworker threads are defined for calculations and for presenting the resulting information on the screen. In this way, each worker executes the tasks declared in a script that contains all segmentation methods to be evaluated in parallel.


## 2.2. Execution of Segmentations and Presentation of Interim Results

The main purpose of the presented work is the parallel execution of segmentation algorithms included in the process of our use case. The reason is that they consume most computational resources and therefore are the key to achieving lower processing times and reduced total computational costs.To perform multiple segmentations in parallel, the source image is processed by a multitask system which assigns one segmentation method to each thread. For the use case presented here, the five segmentation algorithms outlined above were applied to compare the performances of those methods to find the best one.The segmentation methods are assigned ton case structures, such that there are as many cases as segmentation methods (1 to n being the ID numbers). The instruction smpd obtains the IDs and assigns one “worker” to each segmentation process with the help of the instruction switch case. Each case contains a list of tasks to be performed by the assigned worker (in our cases segmentation, calculation of evaluative parameters, representation of the state of execution on the screen, etc.). Figure 4 shows an example of a process running with five workers in parallel. On the right, the progress status window is shown, which informs us about the state of execution during metrics evaluation (in this case, with OCE).Figure 4
Above: command window during a process with 5 workers. Below-right: progress status window.The variables used by each thread become part of another value of type composite, which is a special kind of array. It has the same number of elements as worker processes exist and is useful to recover data from former segmentations. To avoid problems, in case that other applications are executed at the same time, the Matlab search route, the directories, and the previously created subdirectories should be eliminated to avoid overwriting or confusion.After executing the segmentations, the resulting binary images are saved in a directory named results within a subfolder called Binary_seg. Another interim result is the processing time used by the segmentation algorithm (Tp). All Tp measures are displayed on the screen and saved in MATLAB and Excel files. The sidebar illustrates the process with the help of parts of our code.


## 2.3. Data Load and Comparisons

The data load and comparisons are complementary tasks with no need for parallelization. The data load is executed three times to load the source image, the GT, and the binary images obtained by each segmentation process from a subfolder. Afterwards, the processing timetables stored for each segmentation method are also loaded. The path to the images can be manually introduced or predefined. The loaded images are used for the presentation of interim results and to calculate the evaluation metrics as described in the following section.


## 2.4. Evaluation of Segmentation Quality and Detection Accuracy

The evaluation of segmentation quality and detection accuracy is the second main task developed in this tool. The comparison of all binarized segmentation results with the GT is performed by analyzing the pixel coincidence. Therefore, TP, FP, FN, and TN are calculated first. The segmentation quality is then evaluated by GCE, OCE, RI, and VoI metrics whereas the detection accuracy is measured withp, r, FPR, JI, JDI, DI, and Fs metrics. Therefore, five cases executed in parallel are created in the following manner to distribute the calculation time symmetrically:Case  1: GCECase  2: OCECase  3: RI, VoICase  4:p, r, FPR, JI, JDI, Fs, DICase  5: Data storage, presentation of results.Cases  1, 2, and 3 contain algorithms with high computational complexity, Case  4 joins multiple computations which make use of the formerly obtained values for TP, FP, FN, and TN. Finally, the last case has been defined for complementary tasks as data storage, and so forth. All cases are assigned with the help of the parpool instruction as in the segmentation part.


## 2.5. Final Results and Data Display

We opted to display the results obtained by the multithread process graphically and numerically and store segmentations and automatic detection in  .jpeg format. The results related to time processing, segmentation quality, and accuracy detection are saved in both  .xls and  .mat files, as already shown in Figure 2.In order to present the outcomes in a balanced way, we used a distributed scheme. The segmentation images stored in the subfolder are considered as outcomes. Through new multithreads, the presented software generates the contours in the binary images, which are then overlapped with the source images. This procedure is implemented in parallel for each evaluated segmentation method. The outcomes are stored in specific results folders.The numerical data obtained from automatic evaluation through multithreads (quality rates and the processing time) is also saved in the results folder. In order to obtain  .xls data, it is necessary to carry out a conversion of the data (.mat) to a table (.xls). The stored data is shown in the form of a table on the console. Additionally, a nondestructive system for saving data was implemented to avoid overwriting during each software execution. Figure 5 shows how the results are shown on the console and how they appear in the  .xls file for the example evaluation over a test image.Figure 5
Above: visualization of the working environment as results are shown. Below: simultaneously stored Excel table.


## 3. Validation Tests and Discussion

We carried out numerous experiments to validate a multithreaded system for automatic quality evaluation of multiple image segmentation methods and their usefulness to achieve accurate detection. For this purpose, we used 30 forest images to analyze performance in the detection of nonforested or deforested areas, more specifically, images from the Ecuadorian Air Force Research and Development Centre (CIDFAE) database. The images were recorded with a resolution of 1296 × 864 pixels in JPEG format. The digital treatment of the images for all implemented methods was carried out on MATLAB 2015®, running on an Intel Core i5 @ 3.1 GHz computer. The formerly mentioned five segmentation methods were evaluated by eleven metrics in the following way:(a)
Individual measurement of CPU performance and processing timefor each method(b)
Parallel measurement of CPU performance and processing time for each method(c)
The CPU performance obtained through thewindow management task and the processing time Tp by using the instructions tic and toc.To evaluate the multithread method’s efficiency, we considered the partial processing times required to execute the different tasks under two scenarios: the first using the traditional method and the second via the use of multithreads through parallel computing. For both cases, the execution times of each of the tasks are associated.In the traditional evaluation procedure, the following sequence of tasks is associated with the respective partial processing times. To perform segmentation A, the following processing times are considered: time of loading the image (ta) and time of application of the automatic segmentation algorithm (tb). Each segmentation algorithm has its own execution time, so it is necessary to add a value ε. In the case of segmentation with a shorter time of execution, ε=0. We also take into account the time required to obtain the binary information of the segmentation (td). In this process, we have the following summation of processing times to carry out the segmentation (Tsp1):(10)Tsp1=ta+tb+ϵ+td.To evaluate the quality of segmentation A, the following processing times are considered: loading time GT (tf); time to extract the binarized image (tg); time to load the evaluation metric (th); and time to compare the segmentation against the GT, taking into account the adopted metric (ti). The processing times used to evaluate the segmentation’s quality (Tep1) are computed as follows:(11)Tep1=tf+tg+th+ti.In order to evaluate the detection accuracy of segmentation A, we assessed the time required to load the GT (tf); to extract the binary image (tg); to compare the segmentation against the GT (ti); to establish the coincidence or not of pixels (tj); and to obtain the coordinates of the confusion matrix (tk), as well as the time needed to apply the evaluation metric (tl). In this way, the partial processing time for the detection evaluation (Tdp1) will be(12)Tdp1=tf+tg+ti+tj+tk+tl.The total processing time based on the traditional evaluation procedure (Tpt), considering all the times generated in the segmentation A, will be(13)Tpt1=ta+tb+ϵ+td+2tf+2tg+2ti+tj+tk+tl.In order to perform segmentation B, the processing times in absolute terms would be the same as in A, for the quality evaluation of the segmentation and detection precision; thus, the total processing time of the segmentation method B would be(14)Tpt2=ta+tb1+ϵ1+td+2tf+2tg+2ti+tj+tk+tl.If a third segmentation method C is evaluated, the total processing time (Tpt3) in absolute terms would be equal to Tpt2 and equal to Tpt1. In this way, the total processing time used to execute all loading, segmentation, comparison, and evaluation operations grows linearly and consistently; that is to say, if w methods are evaluated, the processing time ratio will be w∗Tpt1 and the computational cost will grow in equal measure.On the other hand, as described in Section2 and with reference to Figure 3, the use of control parallelism, and data employed in the execution of segmentation, comparison, and evaluation by a specific metric, would generate the following processing times.Executing segmentation A generates atsand using an evaluation metric generates a te. Here, the factor ε is not binding since all the segmentations are executed at the same time as shown in Figure 3. On the other hand, the communication that is generated between the block of data that is stored in the memory data bank creates a tc1 that includes the request and response times for the test image, a tc2 to establish the request and response of the GT, and finally a tc3 to provide the coordinates of the confusion matrix. In this way, the processing times for segmentation method A will be distributed according to the following modules.In the segmentation module, the processing time of the first image, through the use of multithreads and parallel computing(Tpp1), will be(15)Tpp1=ts.In the same way, in the evaluation module, the processing time by parallelism of the metric A (Tep1) will be equal to te. In the memory data bank, the distribution of data is done by blocks where in initial form and in a single event ta, tf, andth will have to be added. In addition, the communication times used in the request and transmission should be considered equal, so that in total there will be 3tc. In this way, the total processing time through parallelism (Tppt) for A is presented as follows:(16)Tppt1=ts+te+ta+tf+th+3tc,and the total processing time by parallelism for the segmentation method B would be(17)Tppt2=ts+te+3tc.Therefore,(18)Tppt2≪Tpt2.In general way,Tppt≪Tpt, where both variables are measured such as time processing (Tp). From segmentation B, the times ta, tf, and th are not computed as this data is generally available for use in both comparisons and evaluations and it is no longer needed to reload or perform computing tasks. The reduction of processing times by parallelism also allows us to improve processor performance, to reduce computational costs, mainly due to the elimination of redundant operations, and to achieve efficiency, as well as a balanced distribution of computational load on the processors.Table1 shows average comparative results, which indicate a better performance and a reduction of processing time through the multithreaded system (Tppt) in comparison with the traditional sequential method (Tpt). To obtain the total amount of computational resources used by each method, the CPU usage and total processing times were measured separately during execution and summed up at the end. In Table 1, the mean processing time Tp is shown for each algorithm.Table 1
Comparative results between one-by-one evaluation and the multithreaded system for the case of deforested areas detection.
Performance One-by-one evaluation (Tpt) Evaluation of all methods in parallel (Tppt) NFDI Region growing Chan Vese Superpixel Region based ∑ Total % CPU usage 30% 35% 43% 54% 57% — 43% T p [s] 14.02 19.73 31.84 44.51 48.97 159.07 50.14The differences in time processing between segmentation methods is due to aspects mainly such as(i)
big amount of regions to analyze in irregular shapes;(ii)
excessive interactions to achieve precision in the detection of nonforested areas;(iii)
the complexity of the texture (no uniformity) in forest scenarios.Particularly, the methods based on gradients, regions, and active contours depend on complex mathematical analysis to achieve a better performance rate (time processing in relation to detection rate) in relation to others that use colour information (NFDI). On the other hand, a minor Tp ensures executions in real time.The comparison of CPU usage and processing times shows a significant advantage for the multithreaded implementation. Here, CPU usage is lower when executing all algorithms in parallel than executing at least two of the tested algorithms individually. Furthermore, total multithreading processing time is not only lower than sequential processing but also more than three times as fast. These results demonstrate that the software is highly efficient and prove the utility of the proposed tool. These results are obtained as resources are shared, which enable evaluation processes to exploit memory and processor times more dynamically. This is reflected in the reduction of computational costs and processing times.


## 4. Conclusions

When scientists complete their work, there is a general desire to obtain results instantly, rather than spending a disproportionate amount of time running tests to compare their method with those of other authors. However, those tests are necessary to prove their concept and in some cases to obtain interim results that enable them to proceed with their work in the right direction.As this paper demonstrates, the MATLAB Parallel Toolbox will be of great help to any scientist who has to get through a similar testing phase. It does not require a deep understanding of parallel programming and makes it easier than ever to deploy parallelism in calculation-intensive parts of a program or, where the performance of different algorithms should be tested inside the same system, as in the case presented case here. The parallelization provides a simple form of program verification, saves time (in this case, 68.54%), and reduces overall effort by 67%. Thus, we hope that scientists and researchers in general will take advantage of this method in their own environments.



---

*Source: 5767521-2017-02-21.xml*