https://doi.org/10.31449/inf.v48i12.6044 Informatica 48 (2024) 15–30 15 Minimum Spanning Tree Image Segmentation Model Based on New Weights Hong Li School of Computer Information Engineering, Shanxi Technology and Business College, Taiyuan 030006, China E-mail: lhsxgs@163.com Keywords: minimum spanning tree, image, segmentation, weight, RGB Received: April 19, 2024 The quality of image segmentation results has a direct impact on subsequent image processing and its application. Therefore, image segmentation represents a pivotal step in image processing and recognition. A minimum spanning tree image segmentation method using new weights is proposed to address the issues of low efficiency and low segmentation accuracy in traditional image segmentation methods. The study initially proposes a minimum spanning tree construction method based on color vector angle distance color difference measurement. This method compensates for the non-uniformity of color space through dynamic weight adjustment, and improves upon the fast multi-spanning tree segmentation algorithm with adaptive threshold. The proposed decomposition method preprocesses the image to reduce the image nodes. The experiment showed that the research method effectively improved color difference measurement accuracy. The segmentation accuracy, over segmentation rate, and under segmentation rate obtained by the research method demonstrated superior performance in terms of average values when compared to other segmentation methods. The average values were 0.984, 0.059, and 0.023, respectively. Compared to other minimum spanning tree segmentation algorithms, the research method improved the average segmentation time by 0.46 seconds, 0.49 seconds, 2.04 seconds, and 3.79 seconds, respectively. The segmentation algorithm studied in this study has good segmentation performance and improves the efficiency of image segmentation, which has certain practical application value in various image segmentation fields. Povzetek: Opisan je nov način / model segmentacije slik z uporabo minimalnega vpetega drevesa z novimi utežmi, kar izboljša točnost ugotavljanja barvnih razlik in učinkovitost segmentacije slik. 1 Introduction Image processing technology involves various fields of computer science, and image segmentation is a prerequisite for studying image processing technology, which has a direct impact on the subsequent processing of images [1]. Image segmentation (IS) is the process of dividing an image into several sub-regions with distinct characteristics, according to a predefined standard. These sub-regions can then be extracted and analyzed for specific purposes [2]. In IS, there is a good one-to-one correspondence between images. Therefore, regarding the conversion of IS, utilizing image theory knowledge for IS not only avoids the errors caused by image discretization, but also optimizes the segmentation steps [3]. In recent years, image theory-based segmentation methods have attracted the attention of researchers. Compared to other methods, this method can better balance the regional and global information of the image, and has good segmentation results for certain specific images [4-5]. At present, the latest technologies in the field of IS mainly include deep learning, such as convolutional neural networks (CNN), and its improved methods. Improved CNN architectures such as U-Net and DeepLab have shown excellent performance in multiple tasks, but they rely more on rich labeled datasets and high-performance computing platforms. Transformer, originally born for text processing, is also suitable for IS after adjustment, despite high data and resource requirements. Weak supervised and semi-supervised learning can reduce dependence on annotated data, but their accuracy is usually lower than that of fully-supervised models, and they also pose implementation challenges. Domain adaptation and transfer learning can facilitate cross domain applications, but performance may be compromised due to differences between domains. To solve such problems, a new weight judgment criterion is studied and combined with the minimum spanning tree (MST) to establish a new MST IS method. The objective of this research is to enhance the precision of IS in the target area, optimize the efficiency of related image processing, and thereby facilitate the advancement of digital image processing technology. The research mainly includes five parts. In the first part, the background and significance of IS are mainly introduced. Part 2 provides a comprehensive overview of IS methods. Part 3 is the research method, mainly divided into two sections. In section 2.1, an MST construction method based on RGB 16 Informatica 48 (2024) 15–30 H. Li vector angle distance color difference measurement is proposed. In section 2.2, an IS method based on a new MST is proposed. Part 4 is about verifying the effectiveness of the research model. Part 5 is a summary of the research methods and an analysis of the experimental results. At the same time, the shortcomings of research methods and future research directions are proposed. 2 Background IS is the process of extracting the parts of an image that people are interested in, which directly affects the subsequent processing of the image and is the most critical step in the image processing process. Wilms and Frintrop proposed a new IS method. This method utilized deep features to enrich the fast MST segmentation algorithm (FH algorithm) that combined MST algorithm with adaptive thresholds for region merging. The experiment verified that the FH algorithm had certain advantages in IS accuracy [6]. Zhou and other scholars proposed a semantic language-oriented attention guided cross modal fusion reference IS method to address the current issue of semantic recognition mainly focusing on English and lacking Chinese semantic recognition. The experiment showed that the research method had good segmentation accuracy [7]. To improve the accuracy of IS, Luo et al. proposed a new method using shape convexity binary and probability model, and solved the model using the Lagrange multiplier method. Research showed that this method outperformed most segmentation algorithms in IS [8]. To improve the speed of IS, researchers such as Yan proposed a hybrid active contour model that combines local pre-fitting image functions based on region features with optimized edge indicator functions based on edge features for fast IS. This model had high efficiency and robustness in segmenting images [9]. IS has also been applied in various fields. Srinitya and other researchers conducted in-depth comparisons on methods for segmentation of synthetic aperture radar images, using the Otsu Threshold Selection Method (OTSU) threshold method to segment images that were not particularly interested in texture parts. Finally, a hybrid algorithm based on CNN was proposed to segment synthetic aperture radar images. Research showed that this hybrid IS method had good IS performance [10]. To improve the segmentation accuracy of the fusion background image captured by the autonomous vehicle on-board sensor, Wu and other scholars proposed a new secondary IS method. This method provided accurate environmental perception information for autonomous vehicles while improving the segmentation effect of fused backgrounds [11]. Zou and other researchers proposed a scanning optimization algorithm using a global cosine fitting energy IS model to improve the speed of solving the evolution equation of mutation IS methods. This algorithm was easily extended to high-dimensional IS and achieved good IS efficiency [12]. Yu et al. proposed a semi-supervised IS method using unlabeled data to reduce over-fitting and improve the accuracy of medical IS. Experiments showed that this method had better performance in medical IS compared to traditional semi supervised learning algorithms [13]. The specific details of the research literature review are shown in Table 1. Table 1: Research literature review Researchers Year Method Advantage Shortcoming Wilms and Frintrop 2021 IS combining MST and FH algorithms Better understanding the content and context of images, improving segmentation efficiency and quality. Requires significant computing resources and poor generalization ability Zhou et al. 2022 Attention guided cross modal fusion reference IS Effectively combining image information from different modalities to improve model generalization ability Possible inability to properly guide the model to focus on the correct features, resulting in reduced segmentation quality Luo et al. 2022 Binary combination based on probability model for IS Probability models have high computational efficiency and are suitable for processing large-scale image data Sensitive to parameter settings and model assumptions, which may lead to poor segmentation performance Yan et al. 2022 Hybrid active contour model for fast IS Can improve the accuracy of complex IS and make these segmentation process more flexible Reduce segmentation speed, parameter tuning may become more complex Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 17 Srinitya et al. 2022 Hybrid IS based on CNN Can improve segmentation accuracy, reliability, and generalization ability The interpretability and adjustability of the model are low, and the training process takes a long time Wu et al. 2022 Secondary IS by fusion of background images Reduce the interference of background noise on segmentation results and improve computational efficiency Poor IS performance when facing dynamic or complex backgrounds Yu et al. 2022 Semi supervised IS using unlabeled data Reduced reliance on large amounts of annotated data and improved segmentation performance Unmarked data contains noise, making model evaluation difficult Zou et al. 2023 Scanning optimization algorithm based on global cosine fitting energy IS model Improve the accuracy of segmentation and enhance the robustness of the segmentation process. High computational resources are required, and improper parameter selection leads to a decrease in segmentation quality Research method / MST IS based on new weights Improved segmentation accuracy, over segmentation rate, under segmentation rate, and increased segmentation efficiency Finding the best parameters may be difficult In summary, due to the uncertainty of images, there is currently no unified IS method or objective segmentation criteria to evaluate them. However, most IS methods have drawbacks such as unsatisfactory segmentation results, slow speed, limited utilization of global information in the image, inability to determine the number of clusters, and severe loss of boundary information. To improve the integrity and efficiency of IS, and considering human eye's sensitivity to changes in RGB values, an MST construction method based on RGB vector angle distance color difference measurement is proposed. At the same time, a new weight standard is adopted and improved on the FH algorithm to form a novel MST-based IS algorithm. 3 Minimum spanning tree IS method using new weights The paper proposes a novel weight judgment standard based on image theory for IS method analysis. Firstly, with the importance of color components, dynamic coefficients are used to adjust the spatial distance and vector angle values between RGB colors, resulting in a novel MST construction method based on RGB vector angle distance color difference measurement. In addition, due to the FH algorithm's ability to preserve the details of changing regions well during the segmentation process, a new weight MST-based IS method is proposed by combining and improving the segmentation algorithm. 3.1 Color Difference methods based on RGB color space distance and angle In graph theory-based IS methods, common weight judgment criteria include RGB Euclidean distance, RGB weighted color difference formula, etc. [14]. However, applying such color difference formulas to the image field will cause errors in subsequent image analysis and processing. There are currently three main types of color difference measurement formulas for two colors in the RGB color space, with coordinates ( ) ,, i i i i x r g b = and ( ) ,, j j j j x r g b = , respectively. The existing RGB color difference measurement formula is shown in equation (1). ( ) ( ) ( ) ( ) 2 2 2 , i j i j i j i j D x x r r g g b b = − + − + − (1) Equation (1) takes the spatial distance between two colors as the color difference value, but the RGB color space is not uniform. Therefore, directly measuring color difference using spatial distance cannot accurately reflect the human eye's perception of color differences. Therefore, the RGB weighted color difference formula is proposed, as shown in equation (2). ( ) ( ) ( ) ( ) 22 2 , r i j g i j ij b i j w r r w g g D x x w b b − + − = +− (2) In equation (2), r w , g w , and b w all represent weighted coefficients. However, since the red, green, and blue components are not independent, the color difference pattern on the three coordinate axes cannot be simply generalized to the entire color space. Furthermore, experiments have demonstrated that various weighted algorithms are not always more effective than unweighted algorithms, and that the degree of improvement is generally limited. Therefore, simple weighting is not a 18 Informatica 48 (2024) 15–30 H. Li universal solution. Andrutsos and other scholars have proposed the RGB angular distance color difference formula, as shown in equation (3). ( ) 1 2 ,1 2 1 cos 1 3 255 ij ij ij ij D x x xx xx xx  − =−    −     −−        (3) The characteristic of equation (3) is that it introduces the consideration of the angle difference between the colors to be compared. The experiment has shown that this equation has a certain improvement on RGB color difference measurement compared to equations (1) and (2), but the effect is not ideal. The method of RGB vector angle distance is more consistent with the human eye's perception of color differences, emphasizing visual contrast by measuring the angle differences between colors, rather than purely numerical differences. This measurement method is not susceptible to alterations in lighting conditions, and even when subjected to varying lighting environments, the direction of colors remains consistent, thereby stabilizing the segmentation effect. In addition, angle calculation can capture subtle color changes in complex images, providing richer information than traditional Euclidean or Manhattan distances, especially with the support of GPU optimized mathematical libraries. This method offers a more accurate reflection of details and may also be more efficient in computation. For this purpose, a measurement method based on the RGB vector-angle distance color difference measurement equation is adopted in the study. This method combines the distance between pixel points and their vector relationships, and effectively overcomes the spatial non-uniformity of the image. The objective function is set as ( ) , G x y = and the pixels as ( ) ,, i i i i x r g b = and ( ) ,, j j j j x r g b = . The calculation expression of this equation is shown in equation (4). ( ) ( ) ( ) ( ) 2 2 2 2 2 2 2 2 255 r r i j g g i j b b i j ratio r g b S W r r S W g g S W b b W S S W W W     − +   − +   − = +   + +  (4) In equation (4), ,, r g b S S S represent the importance of the influence of each component in the RGB space. represent the weight values of each component in RGB space.  represents the normalization of the angles of two-color vectors in RGB space. S  is used to monitor and study the impact of changes in the three components of red, green, and blue, and can be dynamically adjusted according to specific circumstances. The dynamic adjustment coefficient is shown in equation (5). ( ) max , , , , , 255 i j i j i j ratio r r g g b b S = (5) Equation (5) not only improves the color difference measurement accuracy, but also saves calculation time and improves time efficiency. 3.2 MST construction method using RGB vector angle distance color difference measurement The study selects this color difference metric as the weight judgment standard in IS and verifies its practical value in IS. For a connected undirected image ( ) , G V E = , a subset ' E of all fixed points G and edges constitutes a sub-image ( ) '' , G V E = . If any two points in the sub-image are connected without forming a loop, then the sub-image ( ) '' , G V E = is its spanning tree. The calculation expression of the MST value is shown in equation (6). ( ) ( ) ( ) , , u v T W T W u v  =  (6) In equation (6), ( ) , W u v represents the size of the weight value of the edge connecting the fixed point. When a number is the smallest spanning tree, the value of ( ) WT is the smallest. In image theory-based research, there are many algorithms for solving the MST, among which common algorithms include Kruskal algorithm and Prim algorithm [15]. The principles and application scenarios for solving the MST using these two algorithms are different. The Kruskal algorithm is chosen to solve the MST. The construction process of the MST based on the Kruskal algorithm is shown in Figure 1 [16]. Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 19 1 1 1 2 2 2 3 3 3 5 4 5 4 5 4 1 1 2 2 3 4 5 3 4 5 (a) (b) (c) (d) (e) Figure 1: Generation process of MST based on Kruskal algorithm In Figure 1, the Kruskal algorithm obtains the MST by iteratively searching for the edge where the minimum weight value is located in the image. The study considers a weighted connected undirected image ( ) , G V E = with a solution as a forest, where all vertices are independent numbers. The construction process is as follows: First, to select the line (1, 2) with the lowest weight in Figure 1, and then connect (1, 2) together to ensure that nodes 1 and 2 are not in the same tree. The edge with the lowest value (3, 5) is selected, ensuring that nodes 3 and 5 are not in the same tree. Merge 3 and 5. Next, the line with the smallest weight (3, 4) is selected to ensure that they are not in the same tree, and connecting them with the smallest weight edge (3, 4). Due to the points 4 and 5 are all in the same tree, they are discarded. Then the minimum weight edges (2,3) are connected so that the 2 or 3 points are not on the same tree, and then all the points are merged. Connect (2, 5). Due to the nodes are all on the same tree, they are discarded. If the nodes connecting (1, 3) and (1, 4) are all on the same tree, they are discarded, and thus obtaining the final MST. Before segmentation, it is necessary to perform a refinement process on the target image, which is to sharpen the image. On this basis, a gradient-based IS method is proposed. In the field of images, the gradient of an image function ( ) , G x y = at a point ( ) , f x y is a vector with size and direction. On a plane, if a function has a continuous partial derivative term, then for any point ( ) , P x y of the function, its vector is defined as shown in equation (7). __ ff ij xy  +  (7) In mathematics, the vector is defined as the gradient of the function ( ) , z f x y = at a point ( ) , P x y , and its definition expression is shown in equation (8). ( ) __ , ff gradf x y i j xy  =+  (8) Assuming that , Gx Gy are the gradients of point ( ) , f x y in the , xy direction, the calculation expression of this gradient is shown in equation (9). x y f G x f f G y        = =        (9) The amplitude of its gradient vector is shown in equation (10). ( ) 1 22 2 1 2 2 2 xy f mag f G G ff xy   =  = +      =+         (10) Due to the complexity of this operation in the actual image field, the use of absolute values to simplify the calculation of gradient amplitude is studied, and the resulting gradient direction is shown in equation (11). ( ) , arctan ff xy yx    =    (11) In practical applications, it is necessary to set gradient operators in specific pixel domains of the target image to perform gradient calculations. The commonly used gradient operators include Sobel operator, Prewitt operator, Laplace operator, etc. [17-18]. The Sobel operator is an improvement based on the Prewitt operator, with a center coefficient occupancy of 2, which can effectively suppress the influence of noise in subsequent images. The Sobel operator is shown in Figure 2. 20 Informatica 48 (2024) 15–30 H. Li P1 P2 P3 P4 P5 P6 P7 P8 P9 (a) G -1 0 +1 -2 0 +2 -1 0 +1 (b) Gx +1 +2 +1 0 0 0 -1 -2 -1 (c) Gy Figure 2: Sobel operator The Sobel operator is a 3x3 matrix, where G is the original image to be processed and ( ) , xy is its pixels. The grayscale values , Gx Gy of the horizontal and vertical images detected at this point are calculated as shown in equation (12) [19]. 1 0 1 2 0 2 1 0 1 1 0 1 2 0 2 1 0 1 Gx G Gy G  − +   = − +    −+     −+     = − +     −+    (12) The expression for calculating the grayscale value of this point is shown in equation (13). 22 G Gx Gy =+ (13) To improve computational efficiency, its absolute value is often used to facilitate the calculation of gradient amplitude, as expressed in equation (14) [20]. G Gx Gy =+ (14) The calculation expression of gradient direction is shown in equation (15) [21]. arctan Gy Gx   =   (15) 3.3 IS method based on new weight minimum spanning tree The study uses gradient methods to preprocess images, enhance their quality, and obtain the necessary information for image analysis, laying the foundation for further image analysis. This study uses this algorithm and the RGB vector angle distance tolerance formula as the judgment formula for weight standards [22]. The improved weight calculation expression is shown in equation (16). ( ) ( ) ( ) ( ) 2 2 2 2 2 2 255 r r i j g g i j b b i j ratio r g b S W r r S W g g S W b b W S S W W W     − +   − +   − = +   + +  (16) Assuming ( ) , G V E = is simplified as the ( ) , MST C E . The internal difference is the longest edge weight of the edges of all connected points in a region C . The calculation expression of internal difference ( ) Int C is shown in equation (17). ( ) ( ) ( ) , max e MST C E Int C W e  = (17) Assuming that in the region A , the weights of the connecting vertices 1, 2, 3 A A A are 1, 2, 3 w w w respectively. If 1 w is set to the maximum weight value, then ( ) 1 Int A w = . Similarly, in the region B , if the edge with the highest internal weight is set as the edge connecting the vertices 1, 2 BB, then the weight of the edge is 7 w , ( ) 7 Int B w = . The difference between segmented regions is the one that has the smallest weight among the connecting edges between the two regions to be divided. If it is defined as ( ) 1, 2 Dif C C , the calculation expression is shown in equation (18). ( ) ( ) ( ) 12 , , , 1, 2 min , i j i j ij v C V C V V E Dif C C W V V    = (18) If there are no edge connections between the segmented regions, it is defined as ( ) 1, 2 Dif C C = . The segmentation diagram is shown in Figure 3. Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 21 B1 B2 B3 B4 B5 B6 B4 B4 B4 w7 w8 w5 w2 w6 w9 w3 w4 Figure 3: Segmentation diagram In Figure 3, assuming the weight of the minimum edge is 2 w , then ( ),2 Dif A B w = . There is no edge connection between A1 and B5 in Figure 6, therefore ( ) 1, 5 Dif A B =. In the field of IS, there are obvious boundaries between different feature domains, namely segmentation boundaries [23]. The boundaries between regions directly affect the final IS results. The segmentation boundary is determined by the difference ( ) 1, 2 Dif C C between the segmented regions and the magnitude of internal differences ( ) Int C , as shown in equation (19). ( ) ( ) ( ) ( ) ( ) 11 22 , 1, 2 Int C C Dif C C Min Int C C   +    +  (19) If equation (19) holds, it means that the difference between regions C1 and C2 is smaller than the minimum value of the internal difference. If C1 and C2 are merged into one region, it remains unchanged. On this basis, a threshold function  is introduced for divided area's boundaries control. The calculation formula for this function is represented in equation (20). K C  = (20) In equation (20), C is the number of pixels contained in the divided area, which can be ignored for the effect of IS. K is an adjustable parameter, and if it is 0, the pixel is a separate range. If it is 0, the entire image is concentrated, which is a complete region. Therefore, appropriate K values should be selected as the basis for segmentation based on the actual situation. The specific segmentation steps are shown in Figure 4. G=(V, E), sigma, K Preprocessed target image Map the image to be divided as a graph Sort all edges of the graph in ascending order by weight In the initial segmentation, each node is a region According to the construction of s[q-1], the initial edge is selected, whose edge weight is W(r i ,v j ) If vertices vi and vj are located in disjoint regions C1 and C2, the weight W(vi,vj) is compared with the internal difference MInt W(ri,vj)< MInt Area C1 and C2 are merged Yes Stay the same No q=1, 2, 3,…, m Get the final segmentation result S[m] Finish Start Input Figure 4: Specific IS steps 22 Informatica 48 (2024) 15–30 H. Li The IS steps are shown in Figure 4. First, other parameter values such as ( ) , G V E = , sigma , K are input. This algorithm first preprocesses the target image to improve image quality and reduce noise. Firstly, the image to be segmented is imageically processed, and then the edges are arranged in ascending order based on their weights. When performing initial partitioning, each node is a region, and   0 S is the original segmented region. Based on the   1 Sq − construction, the initial edge with a weight of ( ) , ij W v v is selected. If the vertices , ij vv are located in areas 1, 2 CC that do not intersect, the weight ( ) , ij W v v is compared with MInt . If ( ) , ij W v v MInt  , 1, 2 CC are merged. Otherwise, it remains unchanged. The above steps are repeated for   1 Sq − construction, 1,2,3, , qm = . Finally, the segmentation result   Sm is obtained. Figure 5 shows the four segmentation scenarios that occur when the weights are the same. Consider the weight w2 first, and then the weight w1 Consider the weight w1 first, and then the weight w2 Do not influence each other Do not influence each other If w1 can merge regions A and B, w2 cannot merge regions B, and C merges regions A and B If w2 cannot merge regions B and C, and w1 cannot merge regions A and B, the result remains the same If w1 cannot merge regions A and B, and w2 can merge regions B and C, then regions B and C will be merged If w1 merges regions A and B, w2 merges regions B and C; Then, region B is merged first, C is region F, and then F is merged with region A, region A, B, and C are merged. (Int( F)=w2+t>w1) If w1 does not merge regions A and B, and w2 does not merge regions B and C, the result remains the same If w2 cannot merge regions B,C, and w1 can merge regions A and B, regions A and B will merge If w1 can merge regions A and B, and w2 can merge B and C, then region AB is first merged into the vomiting region. Then merge regions D and c, and region ABC completes the merge (Int(D)=w1+τ>w2). w2 can merge B and C, then merge B and C, if w1 cannot merge A and B w1,w2 connect four different regions w1,w2 connect three different regions When the same situation occurs for weights w1 and w2 w1 connects areas A and B. w2 connects to areas B and C Figure 5: Four segmentation cases with the same weight In Figure 5, when ( ) ( ) 1 w Int A A + and ( ) ( ) 1 w Int B B + , , AB connecting the 1 w region merges into the D region. When ( ) ( ) 2 w Int B B + or ( ) ( ) 2 w Int C C + , regions , BC remain unchanged, the final regions are , DC . Regions , DC are connected, then the weight is 2 w . When ( ) ( ) 1 w Int A A + and ( ) ( ) 1 w Int B B + , the regions , AB remain unchanged. If ( ) ( ) 2 w Int B B + and ( ) ( ) 2 w Int C C + , that is, region , BC is merged into region D , then the final regions are , AD . If regions , AD are connected, the weight value is 1 w . When ( ) ( ) 1 w Int A A + and ( ) ( ) 1 w Int B B + , ( ) ( ) 2 w Int B B + and ( ) ( ) 2 w Int C C + , regions , AB can be merged into region D , and when regions , DB are connected, the weight value is 2 w . If the above merger conditions are still met, then region , DC is merged into region F to complete the merger. When ( ) ( ) 1 w Int A A + or ( ) ( ) 1 w Int B B + , the regions , AB remain unchanged. If ( ) ( ) 2 w Int B B + or ( ) ( ) 2 w Int C C + , then regions , BC remain unchanged. The final result is that the region ,, A B C remains unchanged. In the process of constructing image weights, considering the presence of adjacent or non adjacent nodes in the MST, edges' weights are reconstructed [24-25]. If there are many nodes in the image, it is very time-consuming. For this purpose, the study uses the MST decomposition method to segment the original image into several small regions [26-27]. Weighted images are established for each small region and the maximum flow minimum segmentation method is used to complete the region division, thereby reducing the image nodes and saving algorithm time. Figure 6 shows the new weights MST-based IS steps. Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 23 Start Finish Choose an appropriate threshold The image is decomposed according to the decomposition method of minimum spanning tree Map the decomposed image to a weighted graph G=(V,E) The graph is processed with minimum spanning tree Find the weights in the edges Reconstruct the weighted graph G= (V,E) Split using maximum flow/ minimum cut Figure 6: Minimum spanning tree IS steps based on new weights In Figure 6, the steps of the IS method are as follows: First, a suitable threshold is selected, and the image is decomposed using the MST decomposition method. Then, the image is mapped to a weighted image. The weighted image ( ) , G V E = is processed using the MST method to obtain the weight values of the edges. The weighted image ( ) , G V E = is then reconstructed, and the max-flow min-cut algorithm is used for segmentation. In IS, the performance of a segmentation model can be evaluated based on segmentation accuracy and time efficiency. Therefore, the paper evaluates the performance of IS. The calculation formula for segmentation accuracy is shown in equation (21) [28]. 1 ss s RT SA R  −  =−   (21) In equation (21), , s s s T R T − represents the number of correct and incorrect pixels, respectively. s R represents the total number of pixels. The calculation formula for the over segmentation rate is shown in equation (22) [29]. s ss O OR RO = + (22) In equation (22), s O represents that the pixel does not exist in the final segmentation, but exists in reality. The calculation formula for under-segmentation rate is shown in equation (23) [30]. s ss U UR RO = + (23) In equation (23), s U and s O represent opposite meanings. 4 Experimental results analysis of new weights MST-based IS model To solve the problem of incomplete weight criteria based on the most spanning tree algorithm, a new weight calculation method was established based on the RGB vector role difference matrix formula theory. On this basis, a new weight MST-based IS algorithm was proposed by combining it with the FH segmentation algorithm. Through multiple controlled experiments, the proposed algorithm was compared in segmentation accuracy, under segmentation, and over segmentation to verify its effectiveness in IS. Table 2 shows the experimental environment. Table 2: Experimental environment Experimental environment Disposition Experimental parameter Numerical value CPU Inter(R) Core(TM) i5, 3.0GHz K 50 Running memory 8 GB Gaussian filter coefficient sigma 1.2 Operating system windows 10, 64 bit Loss boundary 5 Development environment Matlab, R 201 6a Probability parameter 0.1 To verify the improvement of the proposed algorithm against under segmentation and over segmentation phenomena, the program randomly selected images from the BSDS500 and MATLAB image processing libraries as experimental test subjects. The experiment evaluated the effect of color quantization using the mean square error of CIEDE2000 color difference between pre and post quantization images as the standard. Figure 7 shows the mean and variance of CIEDE2000 color difference mean square error for a total of 12, 24, and 36 images quantified to 64 colors using various color difference formulas. 24 Informatica 48 (2024) 15–30 H. Li (a) 12 basic images (b) 24 basic images (c) 36 basic images 8.358 8.133 7.954 7.325 7.154 0.334 0.373 0.382 0.334 0.328 0.30 0.31 0.32 0.33 0.34 0.35 0.36 0.37 0.38 0.39 0.40 5.00 5.50 6.00 6.50 7.00 7.50 8.00 8.50 9.00 9.50 10.00 RGB RGB(342) RGB Angular distance LUV Research method Mean square error V ariance Mean square error Method Mean square error Mean square error V ariance 9.217 8.889 8.835 8.002 7.919 0.35 0.461 0.46 0.35 0.36 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 6.00 7.00 8.00 9.00 10.00 11.00 12.00 RGB RGB(342) RGB Angular distance LUV Research method Mean square error V ariance Mean square error Method Mean square error Mean square error V ariance 8.923 8.63 8.533 7.77 7.656 0.533 0.562 0.603 0.471 0.503 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 6.00 7.00 8.00 9.00 10.00 11.00 12.00 RGB RGB(342) RGB Angular distance LUV Research method Mean square error V ariance Mean square error Method Mean square error Mean square error V ariance Figure 7: The results of CIEDE2000 color difference quantized to 64 colors for images of different numbers according to the color difference formula In Figure 7 (a), the mean square error and variance of the 64 color CIEDE2000 color difference quantized based on the RGB vector angular distance color difference formula for 12 basic images were smaller than those based on the RGB formula, RGB (342) formula, RGB angular distance formula, and LUV color difference formula. The mean square error and mean square error variance obtained based on the research method were 7.154 and 0.328, respectively. From Figures 7 (a) and (b), the application effect and stability of the studied formula were significantly better, and the CIELUV formula was very close. In summary, the research method effectively improved color difference measurement accuracy in RCB. The segmentation comparison results between the research method and the FH algorithm are shown in Figure 8. Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 25 0 1 2 3 4 5 6 7 0 0.2 0.4 0.6 0.8 1.0 Segmentation accuracy (a) Segmentation accuracy Image number Research method FH 0 1 2 3 4 5 6 7 0 0.04 0.08 0.12 0.16 0.20 Overpartition rate (b) Overpartition rate Image number Research method FH 0 1 2 3 4 5 6 7 0 0.1 0.2 0.3 0.4 05 Underdivision ratio (c) Underdivision ratio Image number Research method FH Figure 8: Objective evaluation indicators comparison of segmentation results In Figure 8 (a), the segmentation accuracy of the research method for images ranged from 0.986 to 0.998, while the average segmentation accuracy based on the FH algorithm was about 0.758. In Figure 8 (b), the over segmentation rate of the research method for images ranged from 0.05 to 0.08, while the average over segmentation rate based on the FH algorithm was approximately 0.175. In Figure 8 (c), the under-segmentation rate of the research method for images ranged from 0.01 to 0.03, while the average segmentation accuracy based on the FH algorithm was about 0.163. In Figure 8 (d), the average under segmentation rate of the research method for images was 5.8 seconds, while the average segmentation accuracy based on the FH algorithm was about 7.6 seconds. In summary, the parameters obtained by the research method and time efficiency were superior to the FH algorithm. To further verify the robustness of the algorithm to image noise, three different types of noise, Gaussian, Poisson, and multiplicative, were randomly added to the dataset images. Results of each segmentation algorithm are shown below. (g) Research method (f) EIMST (e) SLTMST (d) MSFH (c) FH (b) Reference imagesFH (a) The original image Figure 9: IS results of multiple segmentation algorithms In Figure 9, under noise interference, using local extremum as a fusion criterion to measure local extremum in multiple images such as color ball images, swan images, and building images can lead to more severe over-fitting and segmentation deficiencies in images based on the FH algorithm. The EIMST algorithm effectively preserved the integrity and independence of the target, but there were significant issues of under 26 Informatica 48 (2024) 15–30 H. Li segmentation and over segmentation, indicating that the introduction of noise blurred the criteria for region definition. However, the universality of SLTMST algorithm and EIMST algorithm was poor. The overall performance of the research method was consistent with the noise free situation. Through subjective analysis of the experimental results, the research method achieved good segmentation results when noise was introduced into the image. However, other methods were greatly interfered with, indicating that the research method had superior anti-noise capabilities. The comparison results of objective evaluation indicators for various segmentation methods are shown in Figure 10. 0 1 2 3 4 5 0 0.2 0.4 0.6 0.8 1.0 Segmentation accuracy (a) Segmentation accuracy Image number Research method FH MISFH EMST SLTMST 0 1 2 3 4 5 0 0.04 0.08 0.12 0.16 0.20 Overpartition rate (b) Overpartition rate Image number 0 1 2 3 4 5 0 0.1 0.2 0.3 0.4 05 Underdivision ratio (c) Underdivision ratio Image number Research method FH MISFH EMST SLTMST FH MSFH EIMST SLTMST Research method Figure 10: Comparison results of objective evaluation indicators of segmentation results by various methods From Figure 10, the obtained ,, SA OR UR outperformed other segmentation methods in terms of average values, with the average values being 0.984, 0.059, and 0.023, respectively. The segmentation accuracy of the research algorithm remained at a high level and gradually stabilizes. To save time, the method of using MST decomposition was studied, and the maximum flow minimum segmentation method was used to complete the region division. Figure 11 shows the comparison results of the new weights MST-based IS method and traditional methods in terms of segmentation time. 0 1 2 3 4 5 0 4 8 12 16 20 Time efficiency(s) Image number Research method FH MSFH EIMST SLTMS T Figure 11: Comparison between the research method and the traditional method in segmentation time From Figure 11, the research method outperformed other algorithms in segmentation time. The average segmentation time of the new weights MST-based IS method studied was about 4.85 seconds. The research method improved the average segmentation time by 0.46 seconds, 0.49 seconds, 2.04 seconds, and 3.79 seconds Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 27 compared to the FH algorithm, MSFH algorithm, SLTMST algorithm, and EIMST algorithm, respectively. To further verify the IS performance of the research method, the experiment passed a t-test. P<0.05 indicates that the experimental comparison results have statistical significance. The experiment statistically analyzed 1,000 images using different IS methods, and the results are shown in Table 3. Table 3: Performance comparison results of various IS methods Method Segmentation accuracy/% P GPU utilization rate/% P Running time/s P Reference [6] 87.1±0.2 <0.05 83.3±0.1 <0.05 7.2±0.2 <0.05 Reference [9] 86.3±0.2 <0.05 83.6±0.3 <0.05 8.5±0.1 <0.05 Reference [11] 87.3±0.2 <0.05 82.3±0.1 <0.05 7.6±0.2 <0.05 Reference [12] 88.2±0.1 <0.05 80.5±0.3 <0.05 8.2±0.1 <0.05 Research method 95.4±0.2 <0.05 88.2±0.2 <0.05 5.4±0.1 <0.05 According to Table 3, the research method had higher IS accuracy (95.4%) and GPU utilization rate (88.2%) than the methods in references [6], [9], [11], and [12]. The running time of the research method is lower than other methods, at 5.4 seconds. All comparative results of the experiment were statistically significant (P<0.05). 5 Discussion The research method has a higher segmentation accuracy for images than the average segmentation accuracy based on the FH algorithm. The research method has a lower under segmentation rate for images compared to the FH algorithm. The research method outperforms other algorithms in segmentation time, and the average segmentation time of the MST IS method based on new weights studied is about 4.85 seconds. The research results on the FH algorithm are similar to those of Wilms and Frintrop [6]. It is more efficient than the research methods of scholars such as Yan [9]. This is because the FH algorithm requires numerous computations and has high algorithm complexity. The research method based on MST algorithms usually has higher operational efficiency. By defining new weights, the algorithm can optimize for different image features and improve adaptability and segmentation performance in diverse scenarios. The segmentation method studied has the same parameter values as the FH algorithm, and the segmentation results of the research method are more complete than those of scholars such as Wu [11]. The IS quality is better than that of researchers such as Zou [12]. This is because MST ensures that all pixels are interconnected in the image, which helps maintain the coherence of the segmented area. When interactive segmentation or automatic selection of cutting standards, the pixel relationships in the entire image can be fully utilized. 6 Conclusion To solve the inaccurate accuracy in the final segmentation results caused by the defects in the weight judgment criteria selected by the MST-based IS model, a new segmentation algorithm was proposed, which selected a novel weight standard. This model compensated for the non-uniformity of RGB color space through weight adjustment, and obtained a new MST-based IS model. The experiment showed that the mean square error and mean square error variance of image quantization obtained based on the research method were 7.154 and 0.328, respectively. The application effect and stability of the studied formula were significantly better than those based on RGB formula, RGB (342) formula, and RGB angular distance formula, and were very close to CIELUV formula. The research method effectively improved color difference measurement accuracy in RCB. The average obtained by the research method was superior to other segmentation methods, with an average of 0.984, 0.059, and 0.023, respectively. The research method outperformed other algorithms in terms of segmentation time. Compared with FH algorithm, MSFH algorithm, SLTMST algorithm, and EIMST algorithm, the research method improved the average segmentation time by 0.46 seconds, 0.49 seconds, 2.04 seconds, and 3.79 seconds, respectively. In summary, through multiple comparative experiments, the superiority of the proposed method in segmentation performance has been verified, and the efficiency of IS has been improved. The proposed dynamic weight adjustment technology focuses on the importance of visual perception, optimizes the weight of color features in changing environments and lighting conditions, and improves the accuracy and stability of segmentation tasks. This personalized color weight adjustment emphasizes real-time performance and can better adapt to various scenarios compared to traditional static methods. However, the limitations or insufficient performance of this method may affect the accuracy of angle measurement. Furthermore, it may not be sufficient in scenes where color is not a key feature. In addition, the complexity of weight adjustment algorithms may lead to higher computational requirements, affecting speed and application on resource constrained devices. 28 Informatica 48 (2024) 15–30 H. Li 7 Funding The research is supported by Shanxi Province Education Science “14th Five-Year Plan" project "Research and practice of Software Engineering professional practice teaching system construction based on Engineering education certification” (GH-220746). References [1] M. M. Mijwil, A. H. Al-Mistarehi, M. Abotaleb, E. S. M. El-kenawy, A. Ibrahim, A. A. Abdelhamid, and M. M. Eid, “From pixels to diagnoses: deep learning's impact on medical image processing-a survey,” Wasit Journal of Computer and Mathematics Science, vol. 2, no. 3, pp. 9-15, 2023. https://doi.org/10.31185/wjcms.178 [2] S. Mahajan, and A. K. Pandit, “Image segmentation and optimization techniques: a short overview,” Medicon Eng Themes, vol. 2, no. 2, pp. 47-49, 2022. [3] H. Wang, D. Zhang, S. Ding, Z. Gao, J. Feng, and S. Wan, “Rib segmentation algorithm for X-ray image based on unpaired sample augmentation and multi-scale network,” Neural Computing and Applications, vol. 35, no. 16, pp. 11583-11597, 2023. https://doi.org/10.1007/s00521-021-06546-x [4] S. Gite, A. Mishra, and K. Kotecha, “Enhanced lung image segmentation using deep learning,” Neural Computing and Applications, vol. 35, no. 31, pp. 22839-22853, 2023. https://doi.org/10.1007/s00521-021-06719-8 [5] F. F. Liu, S. C. Chu, X. Wang, J. S. Pan, “A collaborative dragonfly algorithm with novel communication strategy and application for multi-thresholding color image segmentation,” Journal of Internet Technology, vol. 23, no. 1, pp. 45-62, 2022. https://doi.org/10.53106/160792642022012301005 [6] C. Wilms, and S. Frintrop, “DeepFH segmentations for superpixel-based object proposal refinement,” Image and Vision Computing, vol. 114, no. Oct., pp. 1-10, 2021. https://doi.org/10.1016/j.imavis.2021.104263 [7] Q. Zhou, R. Wang, H. U. Haimiao, Q. Tan, and W. Zhang, “Referring image segmentation with attention guided cross modal fusion for semantic oriented languages,” Frontiers in Computer Science in China: English, vol. 16, no. 6, pp. 187-189, 2022. https://doi.org/10.1007/s11704-022-1136-3 [8] S. Luo, X. C. Tai, and Y. Wang, “A new binary representation method for shape convexity and application to image segmentation,” Analysis and Applications, vol. 20, no. 3, pp. 465-481, 2022. https://doi.org/10.1142/S0219530521500238 [9] X. Yan, and G. Weng, “Hybrid active contour model driven by optimized local pre-fitting image energy for fast image segmentation,” Applied Mathematical Modelling, vol. 101, pp. 586-599, 2022. https://doi.org/10.1016/j.apm.2021.09.002 [10] G. Srinitya, D. Sharmila, S. Logeswari, and D. M. S. Raja, “Certain investigations on image segmentation algorithms on synthetic aperture radar images and classification using convolution neural network,” Concurrency and Computation: Practice and Experience, vol. 34, no. 10, pp. 1-9, 2022. https://doi.org/10.1002/cpe.6733 [11] C. H. Wu, T. C. Tai, and C. Lai, “Semantic image segmentation in similar fusion background for self-driving vehicles,” Sensors and Materials, vol. 34, no. 2 Pt.1, pp. 467-491, 2022. https://doi.org/10.18494/sam3427 [12] L. Zou, Y. P. Chen, Z. Wu, Q. J, Huang, and X. F. Wang, “A sweeping optimization algorithm for the global cosine fitting energy image segmentation model,” Concurrency and Computation: Practice and Experience, vol. 35, no. 17, pp. 1-13, 2023. https://doi.org/10.1002/cpe.6651 [13] H. Yu, S. Xin, W. Zizhou, and Z. Lei, “Uncertainty-guided voxel-level supervised contrastive learning for semi-supervised medical image segmentation,” International Journal of Neural Systems, vol. 32, no. 4, pp. 1-16, 2022. https://doi.org/10.1142/S0129065722500162 [14] M. Kamiyama, and A. Taguchi, “Color conversion formula with saturation correction from HSI color space to rgb color space,” IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, vol. E104/A, no. 7, pp. 1000-1005, 2021. https://doi.org/10.1587/transfun.2020EAL2087 [15] S. A. S. Almola, N. H. Qasim, and H. A. A. Alasadi, “Robust method for embedding an image inside cover image based on least significant bit steganography,” Informatica, vol. 46, no. 9, 2023. https://doi.org/10.31449/inf.v46i9.4362 [16] Z. Gu, and C. He, “Application of fuzzy decision tree algorithm based on mobile computing in sports fitness member management,” Wireless Communications and Mobile Computing, vol. 2021, no. 6, pp. 1-10, 2021. https://doi.org/10.1155/2021/4632722 [17] S. Nimrah, and S. Saifullah, “Context-free word importance scores for attacking neural networks,” Journal of Computational and Cognitive Engineering, vol. 1, no. 4, pp. 187-192, 2022. https://doi.org/10.47852/bonviewJCCE2202406 [18] Y. Jiang, Q. Luo, and Y. Zhou, “Improved gradient-based optimizer for parameters extraction of photovoltaic models,” IET Renewable Power Generation, vol. 16, no. 8, pp. 1602-1622, 2022. https://doi.org/10.1049/rpg2.12465 [19] J. Yang, Z. Jia, X. Lü, X. Huang, and J. Wang, “Digital image biological detection technology based on the porous silicon periodic crystals film,” Optoelectronics Letters, vol. 17, no. 9, pp.552-557, Minimum Spanning Tree Image Segmentation Model Based on New… Informatica 48 (2024) 15–30 29 2021. https://doi.org/10.1007/s11801-021-0176-5 [20] L. Song, “Canny optimisation of the dynamic image colour automatic segmentation algorithm,” International Journal of Computer Applications in Technology, vol. 69, no. 3, pp. 263-263, 2022. https://doi.org/10.1504/IJCAT.2022.127820 [21] M. R. Luo, Q. Xu, M. Pointer, M. Melgosa, G. Cui, and C. Li, “A comprehensive test of colour-difference formulae and uniform colour spaces using available visual datasets,” Color Research and Application, vol. 48, no. 3, pp. 267-282, 2023.https://doi.org/10.1002/col.22844 [22] C. Su, Z. Li, Z. Wei, N. Xu, and Q. Yuan, “Clarity method of low-illumination and dusty coal mine images based on improved amef,” Informatica, vol. 47, no. 7, 2023. https://doi.org/10.31449/inf. v47i7.4799 [23] H. Yang, M. Qi, G. Zhang, Z. Yang, N. Feng, and Y. Yang, “Investigation on the equi-depth of color depth formulas based on color discrimination threshold and acceptable tolerance,” Color Research and Application, vol. 4, no. 3, pp. 328-336, 2023. https://doi.org/10.1002/col.22854 [24] Y. Ma, H. Lin, Y. Wang, H. Huang, and X. He, “A multi-stage hierarchical clustering algorithm based on centroid of tree and cut edge constraint,” Information Sciences, vol. 557, no. 2, pp. 194-219, 2021. https://doi.org/10.1016/j.ins.2020.12.016 [25] G. Kim, and E. Kim, “Stacked encoder–decoder transformer with boundary smoothing for action segmentation,” Electronics Letters, vol. 58, no. 25, pp. 972-974, 2022. https://doi.org/10.1049/ell2.12678 [26] X. Jin, X. Xi, D. Zhou, X. Ren, J. Yang, and Q. Jiang, “An unsupervised multi‐focus image fusion method based on Transformer and U‐Net,” IET Image Processing, vol. 17, no. 3, pp. 733-746, 2023. https://doi.org/10.1049/ipr2.12668 [27] J. Li, G. Li, T. Xie, and Z. Wu, “MST-UNet: a modified Swin Transformer for water bodies’ mapping using Sentinel-2 images,” Journal of Applied Remote Sensing, vol. 17, no. 2, pp. 26507-26507, 2023. https://doi.org/10.1117/1.JRS.17.026507 [28] S, K. Tripathy, S. Srivastava, and R. Srivastava, “MHAMD-MST-CNN: multiscale head attention guided multiscale density maps fusion for video crowd counting via multi-attention spatial-temporal CNN,” Computer Methods in Biomechanics and Biomedical Engineering: Imaging & Visualization, vol. 11, no. 5, 1777-1790, 2023. https://doi.org/10.1080/21681163.2023.2188971 [29] C. Li, K. He, D. Xu, D. Tao, X. Lin, H. Shi, and W. Yin, “Superpixel-based adaptive salient region analysis for infrared and visible image fusion,” Neural Computing and Applications, vol. 35, no. 30, pp. 22511-22529, 2023. https://doi.org/10.1007/s00521-023-08916-z [30] X. Cai, Y. Huo, Y. Chen, M. Xi, Y. Tu, and C. Sun, “Real-time leaf recognition method based on image segmentation and feature extraction,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 36, no. 1, pp. 1-24, 2022. https://doi.org/10.1142/S0218001421540331 30 Informatica 48 (2024) 15–30 H. Li