A Fast Distance Transform Algorithm Based on Parallel Computing for Digital Rock Image Processing 

A Fast Distance Transform Algorithm Based on Parallel Computing for Digital Rock Image Processing | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A Fast Distance Transform Algorithm Based on Parallel Computing for Digital Rock Image Processing Xiaoting Shi, Tan Mao, Junyan Zha, Qiang Su, Xin Wang, Youliang Cheng This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4457889/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Distance transform (DT) can accurately represent spatial information relationship, and it has been widely used in digital core analysis, such as computer image processing, pattern recognition, and etc. However, for large-resolution 2D/3D images, the existing serial Euclidean distance transform (EDT) algorithm is time-consuming and memory-consuming. This paper proposed a parallel implementation of fast Euclidean distance transform in neighborhood based on data set decomposition, which is called as Parallel Computing EDT (PCEDT). The distance transformation is completed efficiently and accurately by data segmentation, batch calculation, and results combination. Compared with other EDT algorithms, PCEDT algorithm is more efficient and more suitable, especially for 2000 3 Voxels to 4000 3 voxels data amount to deal with when applied in practical applications. Parallel computing Euclidean distance transformation Digital Core Image Processing Skeleton information Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9 Figure 10 Figure 11 Figure 12 Figure 13 Figure 14 Figure 15 Figure 16 Figure 17 Figure 18 Figure 19 Figure 20 Figure 21 Figure 22 Figure 23 Figure 24 Figure 25 Figure 26 1. Introduction The physical properties (permeability, transport capacity) of porous media are strongly related to the spatial structure. Distance transform (DT) can describe the pore distribution and topological structure of porous media. In digital rock image, skeleton or medial axis, is a very important shape descriptor since it can preserve both the topological and geometrical information of the core sample and by using surface skeletons can remove noise from 3D shapes[ 1 ].Typical skeletonization approaches can be categorized into four types: algorithms based on general-field functions [ 2 , 3 ], algorithms based on distance transformation [ 4 , 5 ], thinning and boundary propagation [ 6 , 7 ], and algorithms based on the Voronoi diagram [ 8 , 9 ]. In addition, with the research of neural networks in recent years, although Multi-Scale Bidirectional Fully Convolution Network (MSB-FCN) can also capture and integrate multi-scale advanced context information for object skeleton detection [ 10 ], it still has some defects. The distance transformation is the process of calculating the distance between the space point and the target point, which is a powerful tool in digital image processing, computer vision, pattern recognition, shape analysis, and computational geometry [ 11 ]. Distance transforms are important preprocessing steps in complex image analysis systems. More precise control of the skeleton structure through distance transformation [ 12 ]. At present, it also has important applications in the field of digital core technology, which is used for the microscopic study on the oil/gas reservoirs. The application of digital core technology in the field of petrophysics is divided into two categories: direct analysis based on 3D digital images and numerical simulation of petrophysical properties based on 3D digital cores. The pore structure, mineral composition, grain size distribution and other information can be obtained through image analysis [ 13 ]. By using the digital core technology, the pore space of the reservoir can be finely characterized. Then, the flow and distribution of fluids in pore space can be simulated [ 14 ]. And the physical parameters, such as reservoir permeability, formation factor, and resistivity index, can be obtained. Skeletons provide a simple and compact representation of a 2D/3D shape that preserves many of the topological and size characteristics of the original. The process can be viewed as a transformation to transform the width of a binary pattern into just one single pixel. Essentially, such transformation can be achieved by successively removing points or layers of outline from a binary pattern until all the lines or curves are of unit width. The resulting set of lines or curves is called the skeleton of the pattern. As we know, the purpose of skeletonization is to reduce the amount of redundant data embedded in a binary image and to facilitate the extraction of distinctive features from the binary image thereafter. The aim of the distance transformation is getting distance field with European, chessboard [ 15 ], and the spine of the distance field is taken as the skeleton. Due to the extraction of the spine is difficult, it is not easy to get an accurate spine. Generally, every point is specified by giving its distance to the nearest boundary point. The skeleton is defined as the set of points whose distance to the nearest boundary is locally maximum. Although some techniques have already been presented to realize Euclidean Distance Transformation (EDT), most of them are either inefficient or complex to implement. Furthermore, they require extra time and space demand such as special structure or storages for recording information, especially for the real digital cores which contains large amount of data. Cuisenaire and Macq [ 16 ] proposed a fast EDT by propagation using multiple neighborhoods, but a bucket sorting is required before calculating EDT. Datta and Soundaralakshmi [ 17 ] proposed a constant-time algorithm for achieving EDT, but their algorithm is based on a special hardware structure, the reconfigurable mesh. Saito and Toriwaki [ 18 ] proposed an algorithm for obtaining EDT in an n-dimensional domain, but the time-complexity is high in their algorithm. Wang and Tan [ 19 ] improved this algorithm and proposed an efficient EDT algorithm of a binary image in arbitrary dimensions, which reduced the time complexity effectively. But none of them solved the problem of too much traversal data and too much computation. Previously, the distance from the pore space to the solid particle boundary can be calculated by using algorithms such as random simulation, manual measurement, and parallel calculation, etc. These algorithms lead to data inaccuracy, long calculation periods, and high demand for hardware, etc. Therefore, a new algorithm that can perform distance transformation quickly and effectively is urgently needed. The Euclidean distance transformation (EDT) is realized by calculating the distance between each point and all background points in the image, and then comparing and filtering the minimum value. Thus, the EDT is complicated and time-consuming. For large-scale data, it is not realistic to use the EDT algorithm to obtain the Euclidean distance value quickly and accurately. Therefore, if there is no strict requirement on the calculation precision, the distance transformation is usually accomplished by approximate algorithms, such as Manhattan distance [ 20 ], Chebyshev distance [ 21 ], and chamfer distance [ 22 ]. To ensure the rotation invariance and accuracy of Euclidean distance, a lot of efforts have been made to reduce the complexity of Euclidean distance calculation. Based on the basic theories such as morphology, contour tracing, voronoi diagram, boundary stripped, and several Euclidean distance transform algorithms have been proposed [ 23 – 25 ]. However, most of these algorithms are only applicable for two-dimensional images, and inefficient. Shih et al. proposed a fast scanning algorithm for 2D images by using computational neighborhoods to transfer the relative address between pixels [ 26 ]. This algorithm improved the computing speed and gained widely recognition and application. Also, this algorithm provided some basis for 3D Euclidean distance transformation (CEDT). When the amount of data reaches a certain level, the serial algorithm will cause the problem of the large increase of computing time and the serious shortage of computer memory. Therefore, parallel computing is more effective when the data volume is large. Manduhu and Jones proposed a fully-parallelized work-time optimal algorithm is presented for computing the exact Euclidean Distance Transform (EDT) of a 2D binary image with the size of n × n [ 27 ]. In addition, a new parallel algorithm is proposed for the computation of a Euclidean distance map and Voronoi diagram of a binary image that mixes CUDA multi-thread parallel image processing with a raster propagation of distance information over small fragments of the image [ 28 ]. But they did not consider the boundary value problem. In this paper, a parallel computing algorithm based on CEDT algorithm is proposed (PCEDT). The PCEDT algorithm divides the large data and loads it into the processor sequentially, which increases the CPU utilization to the greatest extent and makes the distance transformation more efficient. 2. Method 2.1 Distance transformation algorithm Traversing all the background points is the main cause of the long computation time. The CEDT algorithm limits the computation to 3×3 neighborhood, so as to reduce the computation times of useless points and transform the global computation to the local computation, thus improving the computation efficiency. As shown in Figure.1, the blue part is a 3×3 two-dimensional distance calculation neighborhood and the center voxel represents the measurement pixel. Neighborhood moves in a single element way and calculate the local Euclidean distance, and scan twice in positive and negative order. In the binary graph, the point with the value '1' represents the pore pixel, and the point with the value of '0' represents the solid pixel. During the calculation, the pore pixels in the neighborhood will be assigned infinity. In the scanning process, when there is a '0' in the neighborhood, the distance transformation is calculated by the following formula: $$L={\left( {x - i} \right)^2}+{\left( {y - j} \right)^2}$$ 1 Where (x,y) stands for the voxel coordinates of the center of the neighborhood and (i, j) stands for the coordinates of each point in the neighborhood starting at the upper-left corner, from left to right, and from top to bottom. With the continuous scanning and the continuous updating of the data volume, there will be the situation that the center voxel of the neighborhood is infinite, and all the neighbor points are not '0'. The formula is as follows: $$L={L_1}+{L_2}+2V\left( {p,q} \right)R{\left( {q,b} \right)^T}$$ 2 Where V(p,q) is the direction vector between the measured point and the neighbor point, and R(q,b) is the direction vector closest to the edge of the neighbor point. The global Euclidean distance transformation can be completed by the iterative calculation in the two scanning processes. 2.2 Algorithm architecture and memory model 2.2.1 Serial calculation Serial computing mode usually has the following characteristics: (1) One problem is decomposed into a series of discrete instructions;(2) These instructions are executed in sequence;(3) All instructions are executed on one processor;(4) At most one instruction can be executed at any time. Serial computing is the basis of parallel computing. According to the flow chart shown in Fig. 2 , the serial computing algorithm can be completed. 2.2.2. Parallel computing structure design Parallel computing uses multiple computing resources simultaneously to solve a computing problem, which has the following characteristics:(1) One problem is decomposed into a series of discrete parts that can be executed concurrently; (2) Each part can be further decomposed into a series of discrete instructions; (3) Instructions from each part can be executed simultaneously on different processors; (4) An overall control mechanism is needed to be responsible for scheduling the execution of different parts. 2.2.3. Memory management scheme design Parallel computing data storage can be divided into two categories: distributed storage and shared memory. Distributed storage means that different processes/instructions process different data and do not interfere with each other; Shared memory requires different processes to modify the same block of data at the same time. In this way, the communication between processes becomes simple, but it is easy to cause data read-write conflict. In the PCEDT algorithm, the data need to be divided into several parts and calculate on different processors respectively, and the results should not interfere with each other. So use distributed storage method to store data. Digital images are stored in memory in the form of two-dimensional (three-dimensional) arrays. Array in the virtual address must be continuous, in the physical address is not necessarily continuous, you need to use the pointer query data storage location. The process of parallel computation queries the data in different heaps by pointer, then loads the data into different process pools sequentially, and returns the data results to memory after the computation. 2.3 Specific calculation process The PCEDT algorithm first divides the data set. To ensure the accuracy of the calculation results, the simplest way is to divide the data into two parts. In the algorithm, the data is added to the calculation in the form of an array. The position of each point in the array is determined by the coordinates. Usually, the first data coordinate in the upper left corner is taken as the origin (0,0). The abscissa increases from left to right and the ordinate increases from top to bottom. Taking a two-dimensional array as an example, the existing 8×8 array A can be divided into two 4×4 arrays B and C according to the vertical coordinates. A [0:4] is taken as array B and A [4:8] as array C, as shown in Fig. 7 . However, due to the variety of porous materials and the ever-changing internal structure, most porous materials have no fixed pore shape. In some cases, the fast average score will lead to wrong calculation results. In CEDT algorithm, there is a step of coordinate transfer, and the calculation process may refer to the background points outside the neighbor domain. If the average fast method is adopted, when the calculated target point is located at the block boundary, the background points required for calculation may be divided into another data set. In the data set as shown in Fig. 8 (a), for the red marked target point with coordinates (3,4), the nearest background point should be the background point directly below it and coordinates (4,4). However, if the average block method is adopted, the background point directly below will be divided into another data set and will not participate in the calculation, and the calculation result is wrong. Therefore, when dividing the data, it is required that the two data sets contain all the data required for their own calculation, as shown in Fig. 8 (b), so that the real background points can be added to the calculation. In the second step of the flowchart, two arrays are loaded into the memory allocated by the two implementations, and the calculation results of the two arrays can be obtained at the same time. The coordinate calculation process is regarded as a function, and the whole process can be described by B '= F (B) and C' = F (C). B 'and C' are the results calculated in different processors, as shown in Fig. 9, in which the red and green boxes show different calculation results of data. At this time, the calculation results can ensure that the data results at the average boundary position are accurate. As shown in Fig. 10, the calculated data sets are extracted according to the average block size to obtain the two data sets to be merged. The two datasets are merged by the x-coordinate, and the result is shown in Fig. 11 . The pseudo code of the whole process is as follows: (1) Import the original data array with the size of k×k×k; (2) The array is partitioned according to the number of processors 'm': {S1=[0: k/m + 2,0: k/m + 2,0: k/m + 2), …, Sm=[ ((m-1)k)/m:k, ((m-1)k)/m:k, ((m-1)k)/m:k) }; (3) Parallel computing: {D1 = Dist (S1), ..., Dm = Dist (Sm)}; (4) Extract dataset:{E1 = Extract (D1,), …, Em = Extract (Dm) }; (5) Merge the results: Result = E1 + E2 +... + Em-1 + Em; 2.4 Deal with the complex boundary In the PCEDT algorithm, all the background points should be included in the data segmentation, but the shape and size of the holes are irregular for most porous materials, it is difficult to tell directly from the human eye the range of data that would require the addition of additional data blocks. Figure 12 (a) is a two-dimensional digital slice from a real limestone digital image. Figure 12 (b) is the result calculated by the CEDT algorithm. Figure 12 (c) is the result of the PCEDT algorithm (take an additional line of data at the boundary position), and you can see that the distance transformation results for the labeled regions differ. In Fig. 12 (c), it can be observed that the lower half of the partitioned data block does not contain the nearest background pixel of the target pixel in the yellow-labeled area ( the data in the green-labeled area of figure (b)). During parallel computation, the green-labeled pixels on the left side of Fig. 12 (c) are considered to be the shortest background pixels added to the computation, resulting in a computational error. Therefore, the reason for the error is that there is a problem in the selection of the block region, and the correct background points cannot be divided into the correct data set, so a query module algorithm is needed, the value of the block region is obtained before parallel computation is performed. In digital cores, structural defects and abrupt changes of pore size often exist at the boundary, so it is necessary to describe the changes of pore size at the boundary. In order to accurately determine the range of the block area, CEDT algorithm can be used at the boundary position. The number of intermediate rows serves as the initial cut-off point, starting with the central two rows and extending the computational range in opposite directions along the x-axis, until there are no longer coordinate results in the outermost data that are larger or smaller than the x axis of the boundary position. At this time, the maximum or minimum value of the x-coordinate of the calculation area is the value additionally divided into the data block. Therefore, through the query module, we can know that the upper half of the dataset does not need to take additional data from the lower half of the dataset, and the lower half of the dataset needs to take two rows of data from the upper half of the dataset, and re-divide the data. The result is shown in Fig. 14 (a). The calculation results of different processors are shown in Fig. 14 (b), and the final calculation results are shown in Fig. 14 (c). After repartition, the distance transformation value of each point can be calculated accurately by parallel computation, which is the same as Fig. 12 (b), indicating that the query module can be used accurately. Using the coincidence query module, the computer can get the correct coincidence area range, rationalize the data division process, and save memory space and CPU use to the greatest extent. The addition of the query module solves to the error-prone problem of the original PCEDT algorithm when the boundary position aperture belongs to a specific structural feature. 3. Results In order to test the calculation speed of the algorithm, a slice taken from the Estaillades limestone sample is shown in Fig. 15 (a). Three algorithms were used to calculate the distance transformation of the slice. The result is shown in Fig. 15 . As shown in Fig. 16 , the EDT algorithm always takes longer than the CEDT algorithm for the same size data set. The time difference between the two algorithms increases with the increase of the size of the data set. For 50×50 dataset, the difference was 164 times, and when the dataset grew to 200×200, the difference was 2,623 times. The huge difference in calculation time caused by different calculation algorithms can prove that compared with the EDT algorithm, the CEDT algorithm is more efficient and can save a lot of time. In Fig. 17 , the PCEDT algorithm takes less time than the CEDT algorithm, and the difference between the two algorithms increases with the increase of the data set. But computing time is not only about size, but also about the content of the data. For small-size data, if the data set contains more measured points, the PCEDT algorithm will take a longer time to compute. In order to prove that the algorithm can also run normally in practical applications. As shown in Fig. 18 , Estaillades Limestone with 5.7 micron resolution, 11.8% porosity was selected as the sample. For a data cube, even a small increase in size can lead to a significant increase in computation. Once the data cube size exceeds the limit size, the EDT algorithm cannot complete the calculation in the specified time. Therefore, only CEDT and PCEDT algorithms are used to calculate the samples, and the results are shown in Fig. 19 . Comparing the pore image with the distance transform image can help to analyze the position of the operation. Compared with the results of the slice data, the two algorithms have a greater difference in calculating limestone samples. With the increasing of sample size, compared with PCEDT algorithm, CEDT algorithm takes more computation time. For a data cube of size 50 3 , the difference was 2 times, and when the data cube size grew to 300 3 , the difference was 3 times which can save about 7 minutes. 4. Discussion 4.1. Result accuracy discussion As shown in Fig. 20 (a), a data set of 16×16 is constructed to demonstrate the accuracy of the PCEDT algorithm. The black blocks represent pores, and the white blocks represent solids. Calculate the sample using the EDT algorithm and the PCEDT algorithm, and the results are as follows: Figure 20 (c) shows that the original data is divided into four parts and then transformed by the PCEDT algorithm. In (b) and (c), the blocks corresponding to the positions have the same color, so the results of the two algorithms are consistent. In addition, the color of the pore center is darker and the color of the edge is lighter, which conforms to the law of distance transformation, proving that the calculation results can be used. Considering that large data cubes are often used in practical applications, a data cube of size 500 3 is selected as a sample and the result is shown in Fig. 21 . In the original image (a), red represents the pore area and purple represents the solid area. In order to observe the pore distribution and the result of distance transformation, the pore is extracted. In contrast (c) and (d), the corresponding positions have the same color and the same change trend. In order to accurately study the distance transformation results of each voxel, a data set with the size of 10×10×10 was extracted from the above samples as shown in Fig. 22 . Comparing (B) and (C) in each pore point, it can be found that the corresponding position has the same color. Therefore, it can be proved that the PCEDT algorithm is also suitable for data cubes, and the result of distance transformation is accurate and reliable. 4.2. CPU utilization and memory usage The time complexity and space complexity of the three algorithms are calculated in parallel as follows: Table 1 Time complexity and space complexity EDT CEDT PCEDT Time complexity O(n 2 ) O(4n) O(4n) Spatial complexity O(1) O(n) O(n) Because the PCEDT algorithm uses more processors, more calculations are done in the same amount of time. In a 3×3×3 neighborhood, the range of n from 0 to 26, and the number of statement executions within the same time are shown in Table 2 . Table 2 The execution time of the algorithm is judged by the number of statement execution Algorithms CEDT PCEDT Number of statements executed 0 ~ 104 0 ~ 416 Querying the CPU utilization and memory occupation of the computer can make an intuitive explanation of the time complexity and space complexity. In the 650 3 limestone samples, 100 3 data sets were selected and processed by the PCEDT algorithm and PDT algorithm, which cost 14705.71s and 7.34s respectively. The processor used in the computer is Intel's Core i5-7300 quad-core processor. The CPU utilization and memory occupancy of the EDT and PCEDT algorithms are shown in Fig. 23 . The CPU utilization and memory usage of the EDT algorithm are shown in Fig. 23 (a). During the whole process, CPU utilization fluctuated from 58–46% based on a 52% baseline, and memory utilization remained stable at 27%. The CPU utilization and memory usage of the PCEDT algorithm are shown in Fig. 23 (b). In the whole process, CPU utilization and memory occupancy are maintained at a high level. The difference in the number of processors used by the two algorithms results in a difference in CPU utilization. The EDT algorithm uses only one processor, while the PCEDT algorithm uses four processors for higher CPU utilization. Therefore, although the time complexity of the algorithm has not changed, the amount of data processed in the same time increases, and the overall computational efficiency is improved. As a result, the computing time has been drastically reduced. The memory usage of the two algorithms is consistent with the theoretical analysis. Compared to the EDT algorithm, the parallel computing algorithm uses more memory because the four processors simultaneously require the system to allocate memory for computation. The experiment divided all data into 6 blocks, if divided into more blocks, can reduce the memory consumption to some extent, but the total memory consumption will still be maintained at a high level. In conclusion, despite the high memory footprint of the parallel computing algorithm, its efficient CPU utilization makes it faster to complete the computation. Therefore, parallel computing has more advantages in practical application. 4.3. Applicability comparison The detailed description of pore space based on the digital image is a new algorithm. Distance transformation, as the basis of dividing pore space, is an important part of the work. In the past, the EDT algorithm was mostly used for distance transformation, and it took a long time to get the final result. In order to prove the superiority of the PCEDT algorithm in the practical application field, a comparative experiment was carried out with a cube size of 50 3 , 100 3 , 200 3 , 3003, 400 3 , 500 3 , 600 3 , 700 3 . As shown in Fig. 24 , when the size is 50 3 , the results can be calculated by all three algorithms. Although the calculation time is quite different, it is still within a reasonable range. When the size is 100 3 , the EDT algorithm takes 4 hours to get the result, while the CEDT and PCEDT algorithms can still complete the calculation faster. In the process of increasing the size to 700 3 , the EDT algorithm cannot get the result in the effective time. Although the CEDT algorithm can get the result, it takes 2 ~ 4 times more time than parallel computation. Only CEDT and PCEDT algorithms are used to calculate data sizes larger than 1000 3 . The results are shown in Fig. 25 . In practice, the data of rock samples is very large. It is often calculated by taking the representative unit at one corner of the rock. The size of the representative unit is from 80 to 300, which is determined by the permeability of the sample. The comparative experiment shows that, when the size exceeds 50 3 , the EDT algorithm is no longer suitable for calculation. The PCEDT algorithm can still get the results in about 3 minutes when the size is 300 3 . Therefore, in the practical application, the PCEDT algorithm has more applicability. 4.4. Comparison of natural data and artificial data In the course of the experiment, artificial data is often used to test because it is difficult to obtain natural data. In order to compare the differences between natural data and man-made data in the calculation process, the following calculations are carried out. The existing man-made data with porosity of 10.8% and natural data with porosity of 11.4% are 500 × 500 × 500. The calculation results are as follows: As can be seen from Fig. 26 , when the data size is 50 3 , the calculation time of natural data is longer than that of artificial data, which is caused by the unclear pore distribution in a small range. With the increase of the data size, when the porosity of the two models is close to each other, the computation time of artificial data is always greater than that of natural data, which is about 1.5 ~ 3 times. According to the calculation principle of the algorithm, it is inferred that the pore distribution of artificial data is relatively concentrated, and the algorithm needs to perform the second scan calculation to obtain the distance transformation result, while the pore distribution of natural data is relatively scattered, and the distance transformation result can often be obtained in the first scan process. Therefore, it can be inferred that the prediction of real model data with the same porosity based on the results of artificial data may result in some error. 5. Conclusions Distance transform is widely used in digital analysis, which is the basis of pore segmentation and pore network modeling, which can help to analyze the structure of porous media and predict the performance of porous media. Aiming at the problems of a large amount of computation and long computation period in the practical application of distance transformation, a parallel implementation of fast Euclidean distance transform in neighborhood based on data set decomposition is proposed in this paper, which can save computation time to a great extent, in order to avoid the waste of computer resources. Finally, three algorithms are used to verify the different size arrays. The results show that the CEDT algorithm is accurate and effective, which greatly reduces the calculation time compared with the EDT algorithm; Compared with the CEDT algorithm, parallel computing can further save time and reduce memory consumption. Declarations Conflicts of Interest The authors declare no conflict of interest. Funding The research was funded by National Key Research and Development Program of China [No.2021YFD1600402], National Natural Science Foundation of China [No. 51704265] (Research on two component gas diffusion-convection model in enhancing shale gas recovery with CO2 injection PI: Dr. Chaohua Guo), Key Research and Development Plan of Shaanxi Province [Grant No. 2020GXLH-Z-031], Key Scientific Research Project of Weinan City [Grant No. 2020ZDYF-GYCX-107], Key Scientific Research Project of Education Department of Shaanxi Province [Grant No. 20JS106], Central Guidance on Local Science and Technology Development Fund of Shaanxi Province [NO.2020-ZYYD-NCC-9], Shaanxi Provincial Department of Education Collaborative Innovation Center Project [20JY052], National Natural Science Foundation of China [NO.52072075], Science and technology planning project of Qindu District, Xianyang City [NO.2021QKJ-001], Outstanding Youth Science Fund of Shaanxi Province [No.2018JC-028]. Project of Postgraduate Education and Teaching Reform Research at North China University of Technology in 2023 [YJS2023JG17]. Author Contribution Conceptualization, investigation, writing – original, X.S.; methodology, review & editing, T.M.; resources, M.L.; review & editing, funding acquisition, X.W, Y.C. All authors have read and agreed to the published version of the manuscript. References Herman R. Schubert, Andrei C. Jalba, Alexandru C. Telea, 2020. Feature preserving noise removal for binary voxel volumes using 3D surface skeletons. Computers and Graphics, 87, 30–42. https://doi.org/10.1016/j.cag.2019.12.003 Tang,Y,Y., You, X., 2003. Skeletonization of ribbon-like shapes based on a new wavelet function. IEEE Transactions on Pattern Analysis & Machine Intelligence, 25(9), 1118–1133. https://doi.org/10.1109/TPAMI.2003.1227987 Bourgeois, F., Emptoz, H., 2007. Skeletonization by Gradient Regularization and Diffusion. International Conference on Document Analysis and Recognition. IEEE, 2, 1118–1122. https://doi.org/10.1109/ICIP.2007.4379239 Saha, P., Borgefors, G., Baja, G., 2016. A survey on skeletonization algorithms and their applications. Pattern Recognition Letters, 76, 3–12. https://doi.org/10.1016/j.patrec.2015.04.006 Zhang, J., Malmberg, F., Sclaroff, S.,2019. A Distance Transform Perspective. Springer, Cham. https://doi.org/10.1007/978-3-030-04831-0_3 Jin, X., Kim, J.,2017. A 3d skeletonization algorithm for 3d mesh models using a partial parallel 3d thinning algorithm and 3d skeleton correcting algorithm. Applied Sciences, 139(7), 1–17. https://doi.org/10.3390/app7020139 Durix, B., Chambon, S., Leonard, K., Mari, JL., Morin, G.,2019. The Propagated Skeleton: A Robust Detail-Preserving Approach. Discrete Geometry for Computer Imagery, 343–354. https://doi.org/10.1007/978-3-030-14085-4_27 Liu, H., Wu, Z., Frank, D., et al.,2012. On the generation and pruning of skeletons using generalized voronoi diagrams. Pattern Recognition Letters, 33(16), 2113–2119. https://doi.org/10.1016/j.patrec.2012.07.014 Burch, M., Lith, J. V., Waterlaat, N., & Winden, J. V. ,2020. Voronoier: From Images to Voronoi Diagrams. Visual Information Communication and Interaction (VINCI). 16, 1–9. https://doi.org/10.1145/3430036.3430043 Yang F, Li X, Shen J,2020. Msb-fcn: multi-scale bidirectional fcn for object skeleton extraction. IEEE Transactions on Image Processing,30,2301–2312. https://doi.org/10.1109/TIP.2020.3038483 Liu, W., Jiang, H., Bai, X., et al.,2013. Distance transform-based skeleton extraction and its applications in sensor networks. IEEE Transactions on Parallel & Distributed Systems, 24(9), 1763–1772. https://doi.org/10.1109/TPDS.2012.300 Denk, M., Rother, K., Paetzold, K, 2021. Fully Automated Subdivision Surface Parametrization for Topology Optimized Structures and Frame Structures Using Euclidean Distance Transformation and Homotopic Thinning. pp 18–27. https://doi.org/10.1007/978-3-662-63143-0_2 ZHAO Jian-peng, CHEN Hui, et al, 2020. Research advance of petrophysical application based on digital core technology,35(3), 1099–1108. https://doi.org/10.6038/pg2020DD0486 Qajar, J., Arns, C.,2016. Characterization of reactive flow-induced evolution of carbonate rocks using digital core analysis- part 1: assessment of pore-scale mineral dissolution and deposition. Journal of Contaminant Hydrology, 192, 60–86. https://doi.org/10.1016/j.jconhyd.2016.06.005 Xia, H., Tucker, P., 2010. Finite volume distance field solution applied to medial axis transform. In: 48th AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition, 1(82), 114–134. https://doi.org/10.2514/6.2010-1082 Cuisenaire, O., Macq, B.,1999. Fast Euclidean distance transformation by propagation using multiple neighborhoods, Computer Vision and Image Understanding, 76(2), 163–172. https://doi.org/10.1006/cviu.1999.0783 Datta, A., Soundaralakshmi, S., 2001. Constant-time algorithm for the euclidean distance transform on reconfigurable meshes. Journal of Parallel & Distributed Computing, 61(10), 1439–1455. https://doi.org/10.1006/jpdc.2000.1684 Saito, T., Toriwaki, J., 1994. New algorithms for Euclidean distance transformation of an n-dimensional digitized picture with applications, Pattern Recognition, 27(11), 1551–1565. https://doi.org/10.1016/0031-3203(94)90133-3 Wang J, Ying T .,2013. Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions. Pattern Recognition, 46(1), 230–242. https://doi.org/10.1016/j.patcog.2012.07.030 Renata M.C.R. de Souza, Francisco de A.T. de Carvalho, 2004. Clustering of interval data based on city–block distances,Pattern Recognition Letters,25(3), 353–365. https://doi.org/10.1016/j.patrec.2003.10.016 Gang Wu, Linmin Xu, 2019. Shape description and recognition by implicit chebyshev moments. Pattern recognition letters, 128, 137–145. https://doi.org/10.1016/j.patrec.2019.08.031 T. A. Al-Shurbaji, K. A. AlKaabneh, I. Alhadid, R. Masa’deh, 2021. An Optimized Scale-Invariant Feature Transform Using Chamfer Distance in Image Matching. 31(2), 971–985. https://doi.org/10.32604/iasc.2022.019654 Lotufo, R., Zampirolli, F.,2000. Fast Euclidean distance transform using a graph-search algorithm. Computer Graphics and Image Processing, 2000. Proceedings XIII Brazilian Symposium. IEEE, 269–275. https://doi.org/10.1109/SIBGRA.2000.883922 Svensson, S., Borgefors, G.,2002. Digital distance transforms in 3D images using information from neighbourhoods up to 5×5×5. Comput Vis Image Und, 88, 24–53. https://doi.org/10.1006/cviu.2002.0976 Maurer, C., Qi, R., Raghavan, V.,2003. A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions. IEEE Trans Pattern Anal Mach Intell, 25, 265–270. https://doi.org/10.1109/TPAMI.2003.1177156 Shih, F., Wu, Y.,2004. Fast Euclidean distance transformation in two scans using a 3×3 neighborhood. Comput Vis Image Und, 93, 195–205. https://doi.org/10.1016/j.cviu.2003.09.004 M. Manduhu, M. W. Jones.,2019. A work efficient parallel algorithm for exact euclidean distance transform. IEEE Transactions on Image Processing, 28(11), 5322–5335. https://doi.org/10.1109/TIP.2019.2916741 Elizondo-Leal JC, Ramirez-Torres JG, Barrón-Zambrano JH, et al.,2020. Parallel Raster Scan for Euclidean Distance Transform. Symmetry. 12(11):1808. https://doi.org/10.3390/sym12111808 Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4457889","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":308998450,"identity":"74e34dac-87b1-47f3-9400-0c5f9e6d80fb","order_by":0,"name":"Xiaoting Shi","email":"","orcid":"","institution":"North China University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Xiaoting","middleName":"","lastName":"Shi","suffix":""},{"id":308998451,"identity":"cefe3600-fe8a-48c7-9fe1-dc11bf8f6e34","order_by":1,"name":"Tan Mao","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAs0lEQVRIiWNgGAWjYFAD9sbGhx+IUcgDZ/AcbjaWIE2LRHqbAA8+pTBgz8Cd+OHjDrvE/ZIP2xgkGOzkdBsI2sK7WXLmmeTEHunEtgcFDMnGZgcIa9kgzdt2AKSl3UCC4UDiNiK0bP4N1iJ5sE2Ch0gt2yC2SDASq+UA7zbLmW3Jxj1nEoGBbECEX9gbeDff+NhmJ9vefvzhww8VdnIEtTDIP0DmGRBSPgpGwSgYBaOAKAAAk7A9YWigEpMAAAAASUVORK5CYII=","orcid":"","institution":"North China University of Technology","correspondingAuthor":true,"prefix":"","firstName":"Tan","middleName":"","lastName":"Mao","suffix":""},{"id":308998452,"identity":"5ca4937f-d393-4305-a4af-8979b665d4c5","order_by":2,"name":"Junyan Zha","email":"","orcid":"","institution":"North China University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Junyan","middleName":"","lastName":"Zha","suffix":""},{"id":308998453,"identity":"0d14e939-274d-4aa5-876f-3c782bb9956e","order_by":3,"name":"Qiang Su","email":"","orcid":"","institution":"North China University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Qiang","middleName":"","lastName":"Su","suffix":""},{"id":308998454,"identity":"85eba2cf-aa29-438c-add9-bff735b82818","order_by":4,"name":"Xin Wang","email":"","orcid":"","institution":"Qingdao University of Science and Technology","correspondingAuthor":false,"prefix":"","firstName":"Xin","middleName":"","lastName":"Wang","suffix":""},{"id":308998455,"identity":"5046b670-f8ef-44ec-990b-8e70af074af9","order_by":5,"name":"Youliang Cheng","email":"","orcid":"","institution":"Xi'an University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Youliang","middleName":"","lastName":"Cheng","suffix":""}],"badges":[],"createdAt":"2024-05-22 03:23:25","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4457889/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4457889/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":57950141,"identity":"8f9c3ac2-5969-40e9-9ff7-057df81fcb22","added_by":"auto","created_at":"2024-06-07 21:08:15","extension":"jpg","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":24926,"visible":true,"origin":"","legend":"\u003cp\u003eSchematic diagram\u003c/p\u003e","description":"","filename":"Fig1.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/5708dc98abbfa58957e158b8.jpg"},{"id":57949441,"identity":"edae87db-170e-4e1e-8739-98590616244a","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":66791,"visible":true,"origin":"","legend":"\u003cp\u003eCalculation Example of Fig.1\u003c/p\u003e","description":"","filename":"Fig2.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/1abe4fd4957461e3f4d6c846.jpg"},{"id":57949444,"identity":"9ec17aae-4e6b-4a82-99d4-787b339f402d","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":23886,"visible":true,"origin":"","legend":"\u003cp\u003eSerial calculation diagram\u003c/p\u003e","description":"","filename":"Fig3.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/19c1b8ebd8dc10c065aa16f4.jpg"},{"id":57949945,"identity":"6295e4aa-757a-4b52-9880-0b8e77c5d8de","added_by":"auto","created_at":"2024-06-07 21:00:15","extension":"jpg","order_by":4,"title":"Figure 4","display":"","copyAsset":false,"role":"figure","size":37539,"visible":true,"origin":"","legend":"\u003cp\u003eParallel computing diagram\u003c/p\u003e","description":"","filename":"Fig4.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/703eaaa27fc58a56ae272369.jpg"},{"id":57950253,"identity":"c1a02943-82c6-4ac4-81fb-1e97a63f378a","added_by":"auto","created_at":"2024-06-07 21:16:15","extension":"jpg","order_by":5,"title":"Figure 5","display":"","copyAsset":false,"role":"figure","size":38351,"visible":true,"origin":"","legend":"\u003cp\u003eTwo memory systems\u003c/p\u003e","description":"","filename":"Fig5.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/aac29f2bfa9100100a51e75d.jpg"},{"id":57949693,"identity":"eb264d7b-1317-480b-b004-f603fe753dac","added_by":"auto","created_at":"2024-06-07 20:52:15","extension":"jpg","order_by":6,"title":"Figure 6","display":"","copyAsset":false,"role":"figure","size":49648,"visible":true,"origin":"","legend":"\u003cp\u003eMemory model of PCEDT algorithm\u003c/p\u003e","description":"","filename":"Fig6.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/f571e645b283c78b5f6511bc.jpg"},{"id":57949948,"identity":"696fdd46-da69-4886-8992-eb7d034b6f3a","added_by":"auto","created_at":"2024-06-07 21:00:15","extension":"jpg","order_by":7,"title":"Figure 7","display":"","copyAsset":false,"role":"figure","size":26010,"visible":true,"origin":"","legend":"\u003cp\u003eConventional blocking\u003c/p\u003e","description":"","filename":"Fig7.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/12794f22dc77223e6d8f0f1f.jpg"},{"id":57949459,"identity":"ec9c1b70-e330-463e-8709-e70794e3a5ea","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"png","order_by":8,"title":"Figure 8","display":"","copyAsset":false,"role":"figure","size":78344,"visible":true,"origin":"","legend":"\u003cp\u003e(a) Average split dataset (b) Unaverage split dataset\u003c/p\u003e","description":"","filename":"Fig8.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/d32dbf400ceab931112d2c93.png"},{"id":57949688,"identity":"b12e7dbf-7359-4b39-af97-770d2d30871d","added_by":"auto","created_at":"2024-06-07 20:52:15","extension":"png","order_by":9,"title":"Figure 9","display":"","copyAsset":false,"role":"figure","size":39878,"visible":true,"origin":"","legend":"\u003cp\u003eParallel computing results B 'and C'\u003c/p\u003e","description":"","filename":"Fig9.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/a1e3e2867a16015cc4221568.png"},{"id":57949457,"identity":"195d398e-b11d-4947-bd0b-3d3b7b9d3d1c","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"png","order_by":10,"title":"Figure 10","display":"","copyAsset":false,"role":"figure","size":22015,"visible":true,"origin":"","legend":"\u003cp\u003eExtract dataset from B 'and C'\u003c/p\u003e","description":"","filename":"Fig10.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/7581d695baed1871732ffeec.png"},{"id":57949450,"identity":"f54aefb2-c14f-407b-a46f-3636d985a5a8","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":11,"title":"Figure 11","display":"","copyAsset":false,"role":"figure","size":15218,"visible":true,"origin":"","legend":"\u003cp\u003eResult of merging operation\u003c/p\u003e","description":"","filename":"Fig11.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/39ec6b6f79719fe083da9ba3.jpg"},{"id":57949696,"identity":"f8187565-df00-4cdd-b162-280c38e8f842","added_by":"auto","created_at":"2024-06-07 20:52:16","extension":"png","order_by":12,"title":"Figure 12","display":"","copyAsset":false,"role":"figure","size":145585,"visible":true,"origin":"","legend":"\u003cp\u003e(a) Initial data; (b) CEDT result; (c) PCEDT result\u003c/p\u003e","description":"","filename":"Fig12.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/c9c34c9ba9e4e06428d43fdb.png"},{"id":57949449,"identity":"e8abbcf9-d068-42db-b333-b9fc073bf4b9","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":13,"title":"Figure 13","display":"","copyAsset":false,"role":"figure","size":21342,"visible":true,"origin":"","legend":"\u003cp\u003eCEDT calculation of boundary position\u003c/p\u003e","description":"","filename":"Fig13.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/71f94341ab742afba1fe65b0.jpg"},{"id":57949455,"identity":"577a7177-ff6b-4c0e-8ff8-222ad553b5f3","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"png","order_by":14,"title":"Figure 14","display":"","copyAsset":false,"role":"figure","size":149360,"visible":true,"origin":"","legend":"\u003cp\u003e(a) Repartition; (b) Processor computing; (c) Results of parallel computation\u003c/p\u003e","description":"","filename":"Fig14.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/f9830d400b90d9d09e530a87.png"},{"id":57949453,"identity":"494189a4-2cf4-4911-8fa3-91ccc25ca029","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"png","order_by":15,"title":"Figure 15","display":"","copyAsset":false,"role":"figure","size":215176,"visible":true,"origin":"","legend":"\u003cp\u003eDT operation on one slice image of Estaillades limestone sample; (a) Original image; (b) Pore image; (c) Result image.\u003c/p\u003e","description":"","filename":"Fig15.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/2d6c90066df1899008caa9da.png"},{"id":57949454,"identity":"0b90cfda-fc25-4ef6-a0be-c0591d28e28e","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":16,"title":"Figure 16","display":"","copyAsset":false,"role":"figure","size":37056,"visible":true,"origin":"","legend":"\u003cp\u003eThe calculation time of EDT algorithm and CEDT algorithm\u003c/p\u003e","description":"","filename":"Fig16.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/cca97972219383ace4822b9e.jpg"},{"id":57949462,"identity":"26817a95-45fd-462c-9e59-6f78134c6069","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"jpg","order_by":17,"title":"Figure 17","display":"","copyAsset":false,"role":"figure","size":36980,"visible":true,"origin":"","legend":"\u003cp\u003eThe calculation time of CEDT algorithm and PCEDT algorithm\u003c/p\u003e","description":"","filename":"Fig17.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/c907fb973c18426861f675ba.jpg"},{"id":57949461,"identity":"aa17188f-b360-49b3-9bea-aedf35ea85d3","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"png","order_by":18,"title":"Figure 18","display":"","copyAsset":false,"role":"figure","size":222348,"visible":true,"origin":"","legend":"\u003cp\u003eDT operation on 3D images of Estaillades limestone sample; (a) Original image; (b) Pore image; (c) Distance transformation image\u003c/p\u003e","description":"","filename":"Fig18.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/2b8dcc58443f9b230a399142.png"},{"id":57949460,"identity":"10b7eb86-a1fb-4ee4-899f-d8ae453d07aa","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"jpg","order_by":19,"title":"Figure 19","display":"","copyAsset":false,"role":"figure","size":31304,"visible":true,"origin":"","legend":"\u003cp\u003eCalculation time of 3D data\u003c/p\u003e","description":"","filename":"Fig19.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/d2c3d15f53221204a953d7b9.jpg"},{"id":57949451,"identity":"027b7e6d-84bb-49ba-aacc-3e27e151b7d3","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"png","order_by":20,"title":"Figure 20","display":"","copyAsset":false,"role":"figure","size":47942,"visible":true,"origin":"","legend":"\u003cp\u003eDT operation on 16×16 dataset sample. (a) Original image; (b)Distance transform image by EDT algorithm; (c) Distance transform image by PCEDT algorithm\u003c/p\u003e","description":"","filename":"Fig20.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/807d3df207317faf94f2650f.png"},{"id":57949950,"identity":"94a71fae-8ddc-469d-99ca-43dc78cc513f","added_by":"auto","created_at":"2024-06-07 21:00:16","extension":"png","order_by":21,"title":"Figure 21","display":"","copyAsset":false,"role":"figure","size":595417,"visible":true,"origin":"","legend":"\u003cp\u003eDT operation on 3D images of data 500\u003csup\u003e3\u003c/sup\u003e (a) Original image; (b) Pore image; (c) EDT algorithm; (d) PCEDT algorithm\u003c/p\u003e","description":"","filename":"Fig21.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/2657bfba0a9420ec497759d3.png"},{"id":57949467,"identity":"396af970-981f-43f2-8e47-deaec1946aff","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"png","order_by":22,"title":"Figure 22","display":"","copyAsset":false,"role":"figure","size":101551,"visible":true,"origin":"","legend":"\u003cp\u003eDetail images of the result visualization with DT operation. (a) Original image; (b)EDT algorithm; (c) PCEDT algorithm\u003c/p\u003e","description":"","filename":"Fig22.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/bbd0449134aa5d4ac2bff201.png"},{"id":57949694,"identity":"310f9abd-9886-4154-ad4f-942e7e4a1e2d","added_by":"auto","created_at":"2024-06-07 20:52:15","extension":"png","order_by":23,"title":"Figure 23","display":"","copyAsset":false,"role":"figure","size":104644,"visible":true,"origin":"","legend":"\u003cp\u003eCPU utilization and memory usage\u003c/p\u003e","description":"","filename":"Fig23.png","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/6f459e23cb4de5ee435cee3f.png"},{"id":57949465,"identity":"18ef2aa7-22d8-48dc-80c1-f24bcb451bf9","added_by":"auto","created_at":"2024-06-07 20:44:16","extension":"jpg","order_by":24,"title":"Figure 24","display":"","copyAsset":false,"role":"figure","size":35204,"visible":true,"origin":"","legend":"\u003cp\u003eComparison of calculation time\u003c/p\u003e","description":"","filename":"Fig24.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/24e85f1ddd4afc37386d4ed8.jpg"},{"id":57949697,"identity":"9c6de6bc-060f-448c-823a-47bd8a1a6fff","added_by":"auto","created_at":"2024-06-07 20:52:16","extension":"jpg","order_by":25,"title":"Figure 25","display":"","copyAsset":false,"role":"figure","size":30881,"visible":true,"origin":"","legend":"\u003cp\u003eComparison of calculation time\u003c/p\u003e","description":"","filename":"Fig25.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/b2e4d3f26dd1ce312030765c.jpg"},{"id":57949456,"identity":"ba282d91-8bce-4bd9-b273-15ca012f5955","added_by":"auto","created_at":"2024-06-07 20:44:15","extension":"jpg","order_by":26,"title":"Figure 26","display":"","copyAsset":false,"role":"figure","size":43166,"visible":true,"origin":"","legend":"\u003cp\u003eComparison of Calculation Time\u003c/p\u003e","description":"","filename":"Fig26.jpg","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/039c49b23cf6d065dcbe4f40.jpg"},{"id":60718661,"identity":"069357b3-2c22-4404-bd76-3a7f8db2a3c9","added_by":"auto","created_at":"2024-07-20 01:31:41","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2553474,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4457889/v1/98280a65-3bbd-4a75-841e-a7100f3fe45f.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A Fast Distance Transform Algorithm Based on Parallel Computing for Digital Rock Image Processing ","fulltext":[{"header":"1. Introduction","content":"\u003cp\u003eThe physical properties (permeability, transport capacity) of porous media are strongly related to the spatial structure. Distance transform (DT) can describe the pore distribution and topological structure of porous media. In digital rock image, skeleton or medial axis, is a very important shape descriptor since it can preserve both the topological and geometrical information of the core sample and by using surface skeletons can remove noise from 3D shapes[\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e].Typical skeletonization approaches can be categorized into four types: algorithms based on general-field functions [\u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2\u003c/span\u003e, \u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e], algorithms based on distance transformation [\u003cspan citationid=\"CR4\" class=\"CitationRef\"\u003e4\u003c/span\u003e, \u003cspan citationid=\"CR5\" class=\"CitationRef\"\u003e5\u003c/span\u003e], thinning and boundary propagation [\u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e6\u003c/span\u003e, \u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e7\u003c/span\u003e], and algorithms based on the Voronoi diagram [\u003cspan citationid=\"CR8\" class=\"CitationRef\"\u003e8\u003c/span\u003e, \u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e9\u003c/span\u003e]. In addition, with the research of neural networks in recent years, although Multi-Scale Bidirectional Fully Convolution Network (MSB-FCN) can also capture and integrate multi-scale advanced context information for object skeleton detection [\u003cspan citationid=\"CR10\" class=\"CitationRef\"\u003e10\u003c/span\u003e], it still has some defects. The distance transformation is the process of calculating the distance between the space point and the target point, which is a powerful tool in digital image processing, computer vision, pattern recognition, shape analysis, and computational geometry [\u003cspan citationid=\"CR11\" class=\"CitationRef\"\u003e11\u003c/span\u003e]. Distance transforms are important preprocessing steps in complex image analysis systems. More precise control of the skeleton structure through distance transformation [\u003cspan citationid=\"CR12\" class=\"CitationRef\"\u003e12\u003c/span\u003e]. At present, it also has important applications in the field of digital core technology, which is used for the microscopic study on the oil/gas reservoirs. The application of digital core technology in the field of petrophysics is divided into two categories: direct analysis based on 3D digital images and numerical simulation of petrophysical properties based on 3D digital cores. The pore structure, mineral composition, grain size distribution and other information can be obtained through image analysis [\u003cspan citationid=\"CR13\" class=\"CitationRef\"\u003e13\u003c/span\u003e]. By using the digital core technology, the pore space of the reservoir can be finely characterized. Then, the flow and distribution of fluids in pore space can be simulated [\u003cspan citationid=\"CR14\" class=\"CitationRef\"\u003e14\u003c/span\u003e]. And the physical parameters, such as reservoir permeability, formation factor, and resistivity index, can be obtained. Skeletons provide a simple and compact representation of a 2D/3D shape that preserves many of the topological and size characteristics of the original. The process can be viewed as a transformation to transform the width of a binary pattern into just one single pixel. Essentially, such transformation can be achieved by successively removing points or layers of outline from a binary pattern until all the lines or curves are of unit width. The resulting set of lines or curves is called the skeleton of the pattern. As we know, the purpose of skeletonization is to reduce the amount of redundant data embedded in a binary image and to facilitate the extraction of distinctive features from the binary image thereafter.\u003c/p\u003e \u003cp\u003eThe aim of the distance transformation is getting distance field with European, chessboard [\u003cspan citationid=\"CR15\" class=\"CitationRef\"\u003e15\u003c/span\u003e], and the spine of the distance field is taken as the skeleton. Due to the extraction of the spine is difficult, it is not easy to get an accurate spine. Generally, every point is specified by giving its distance to the nearest boundary point. The skeleton is defined as the set of points whose distance to the nearest boundary is locally maximum. Although some techniques have already been presented to realize Euclidean Distance Transformation (EDT), most of them are either inefficient or complex to implement. Furthermore, they require extra time and space demand such as special structure or storages for recording information, especially for the real digital cores which contains large amount of data. Cuisenaire and Macq [\u003cspan citationid=\"CR16\" class=\"CitationRef\"\u003e16\u003c/span\u003e] proposed a fast EDT by propagation using multiple neighborhoods, but a bucket sorting is required before calculating EDT. Datta and Soundaralakshmi [\u003cspan citationid=\"CR17\" class=\"CitationRef\"\u003e17\u003c/span\u003e] proposed a constant-time algorithm for achieving EDT, but their algorithm is based on a special hardware structure, the reconfigurable mesh. Saito and Toriwaki [\u003cspan citationid=\"CR18\" class=\"CitationRef\"\u003e18\u003c/span\u003e] proposed an algorithm for obtaining EDT in an n-dimensional domain, but the time-complexity is high in their algorithm. Wang and Tan [\u003cspan citationid=\"CR19\" class=\"CitationRef\"\u003e19\u003c/span\u003e] improved this algorithm and proposed an efficient EDT algorithm of a binary image in arbitrary dimensions, which reduced the time complexity effectively. But none of them solved the problem of too much traversal data and too much computation. Previously, the distance from the pore space to the solid particle boundary can be calculated by using algorithms such as random simulation, manual measurement, and parallel calculation, etc. These algorithms lead to data inaccuracy, long calculation periods, and high demand for hardware, etc. Therefore, a new algorithm that can perform distance transformation quickly and effectively is urgently needed. The Euclidean distance transformation (EDT) is realized by calculating the distance between each point and all background points in the image, and then comparing and filtering the minimum value. Thus, the EDT is complicated and time-consuming. For large-scale data, it is not realistic to use the EDT algorithm to obtain the Euclidean distance value quickly and accurately. Therefore, if there is no strict requirement on the calculation precision, the distance transformation is usually accomplished by approximate algorithms, such as Manhattan distance [\u003cspan citationid=\"CR20\" class=\"CitationRef\"\u003e20\u003c/span\u003e], Chebyshev distance [\u003cspan citationid=\"CR21\" class=\"CitationRef\"\u003e21\u003c/span\u003e], and chamfer distance [\u003cspan citationid=\"CR22\" class=\"CitationRef\"\u003e22\u003c/span\u003e]. To ensure the rotation invariance and accuracy of Euclidean distance, a lot of efforts have been made to reduce the complexity of Euclidean distance calculation. Based on the basic theories such as morphology, contour tracing, voronoi diagram, boundary stripped, and several Euclidean distance transform algorithms have been proposed [\u003cspan additionalcitationids=\"CR24\" citationid=\"CR23\" class=\"CitationRef\"\u003e23\u003c/span\u003e\u0026ndash;\u003cspan citationid=\"CR25\" class=\"CitationRef\"\u003e25\u003c/span\u003e]. However, most of these algorithms are only applicable for two-dimensional images, and inefficient. Shih et al. proposed a fast scanning algorithm for 2D images by using computational neighborhoods to transfer the relative address between pixels [\u003cspan citationid=\"CR26\" class=\"CitationRef\"\u003e26\u003c/span\u003e]. This algorithm improved the computing speed and gained widely recognition and application. Also, this algorithm provided some basis for 3D Euclidean distance transformation (CEDT).\u003c/p\u003e \u003cp\u003eWhen the amount of data reaches a certain level, the serial algorithm will cause the problem of the large increase of computing time and the serious shortage of computer memory. Therefore, parallel computing is more effective when the data volume is large. Manduhu and Jones proposed a fully-parallelized work-time optimal algorithm is presented for computing the exact Euclidean Distance Transform (EDT) of a 2D binary image with the size of n \u0026times; n [\u003cspan citationid=\"CR27\" class=\"CitationRef\"\u003e27\u003c/span\u003e]. In addition, a new parallel algorithm is proposed for the computation of a Euclidean distance map and Voronoi diagram of a binary image that mixes CUDA multi-thread parallel image processing with a raster propagation of distance information over small fragments of the image [\u003cspan citationid=\"CR28\" class=\"CitationRef\"\u003e28\u003c/span\u003e]. But they did not consider the boundary value problem.\u003c/p\u003e \u003cp\u003eIn this paper, a parallel computing algorithm based on CEDT algorithm is proposed (PCEDT). The PCEDT algorithm divides the large data and loads it into the processor sequentially, which increases the CPU utilization to the greatest extent and makes the distance transformation more efficient.\u003c/p\u003e"},{"header":"2.\tMethod ","content":"\u003cdiv id=\"Sec3\" class=\"Section2\"\u003e \u003ch2\u003e2.1 Distance transformation algorithm\u003c/h2\u003e \u003cp\u003eTraversing all the background points is the main cause of the long computation time. The CEDT algorithm limits the computation to 3\u0026times;3 neighborhood, so as to reduce the computation times of useless points and transform the global computation to the local computation, thus improving the computation efficiency. As shown in Figure.1, the blue part is a 3\u0026times;3 two-dimensional distance calculation neighborhood and the center voxel represents the measurement pixel. Neighborhood moves in a single element way and calculate the local Euclidean distance, and scan twice in positive and negative order.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eIn the binary graph, the point with the value '1' represents the pore pixel, and the point with the value of '0' represents the solid pixel. During the calculation, the pore pixels in the neighborhood will be assigned infinity. In the scanning process, when there is a '0' in the neighborhood, the distance transformation is calculated by the following formula:\u003cdiv id=\"Equ1\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equ1\" name=\"EquationSource\"\u003e\n$$L={\\left( {x - i} \\right)^2}+{\\left( {y - j} \\right)^2}$$\u003c/div\u003e\u003cdiv class=\"EquationNumber\"\u003e1\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eWhere (x,y) stands for the voxel coordinates of the center of the neighborhood and (i, j) stands for the coordinates of each point in the neighborhood starting at the upper-left corner, from left to right, and from top to bottom. With the continuous scanning and the continuous updating of the data volume, there will be the situation that the center voxel of the neighborhood is infinite, and all the neighbor points are not '0'. The formula is as follows:\u003cdiv id=\"Equ2\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equ2\" name=\"EquationSource\"\u003e\n$$L={L_1}+{L_2}+2V\\left( {p,q} \\right)R{\\left( {q,b} \\right)^T}$$\u003c/div\u003e\u003cdiv class=\"EquationNumber\"\u003e2\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eWhere V(p,q) is the direction vector between the measured point and the neighbor point, and R(q,b) is the direction vector closest to the edge of the neighbor point. The global Euclidean distance transformation can be completed by the iterative calculation in the two scanning processes.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec4\" class=\"Section2\"\u003e \u003ch2\u003e2.2 Algorithm architecture and memory model\u003c/h2\u003e \u003cdiv id=\"Sec5\" class=\"Section3\"\u003e \u003ch2\u003e2.2.1 Serial calculation\u003c/h2\u003e \u003cp\u003eSerial computing mode usually has the following characteristics: (1) One problem is decomposed into a series of discrete instructions;(2) These instructions are executed in sequence;(3) All instructions are executed on one processor;(4) At most one instruction can be executed at any time.\u003c/p\u003e \u003cp\u003eSerial computing is the basis of parallel computing. According to the flow chart shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig2\" class=\"InternalRef\"\u003e2\u003c/span\u003e, the serial computing algorithm can be completed.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec6\" class=\"Section3\"\u003e \u003ch2\u003e2.2.2. Parallel computing structure design\u003c/h2\u003e \u003cp\u003eParallel computing uses multiple computing resources simultaneously to solve a computing problem, which has the following characteristics:(1) One problem is decomposed into a series of discrete parts that can be executed concurrently; (2) Each part can be further decomposed into a series of discrete instructions; (3) Instructions from each part can be executed simultaneously on different processors; (4) An overall control mechanism is needed to be responsible for scheduling the execution of different parts.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec7\" class=\"Section3\"\u003e \u003ch2\u003e2.2.3. Memory management scheme design\u003c/h2\u003e \u003cp\u003eParallel computing data storage can be divided into two categories: distributed storage and shared memory. Distributed storage means that different processes/instructions process different data and do not interfere with each other; Shared memory requires different processes to modify the same block of data at the same time. In this way, the communication between processes becomes simple, but it is easy to cause data read-write conflict.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eIn the PCEDT algorithm, the data need to be divided into several parts and calculate on different processors respectively, and the results should not interfere with each other. So use distributed storage method to store data. Digital images are stored in memory in the form of two-dimensional (three-dimensional) arrays. Array in the virtual address must be continuous, in the physical address is not necessarily continuous, you need to use the pointer query data storage location. The process of parallel computation queries the data in different heaps by pointer, then loads the data into different process pools sequentially, and returns the data results to memory after the computation.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e \u003c/div\u003e \u003cdiv id=\"Sec8\" class=\"Section2\"\u003e \u003ch2\u003e2.3 Specific calculation process\u003c/h2\u003e \u003cp\u003eThe PCEDT algorithm first divides the data set. To ensure the accuracy of the calculation results, the simplest way is to divide the data into two parts. In the algorithm, the data is added to the calculation in the form of an array. The position of each point in the array is determined by the coordinates. Usually, the first data coordinate in the upper left corner is taken as the origin (0,0). The abscissa increases from left to right and the ordinate increases from top to bottom. Taking a two-dimensional array as an example, the existing 8\u0026times;8 array A can be divided into two 4\u0026times;4 arrays B and C according to the vertical coordinates. A [0:4] is taken as array B and A [4:8] as array C, as shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig7\" class=\"InternalRef\"\u003e7\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eHowever, due to the variety of porous materials and the ever-changing internal structure, most porous materials have no fixed pore shape. In some cases, the fast average score will lead to wrong calculation results. In CEDT algorithm, there is a step of coordinate transfer, and the calculation process may refer to the background points outside the neighbor domain. If the average fast method is adopted, when the calculated target point is located at the block boundary, the background points required for calculation may be divided into another data set. In the data set as shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig8\" class=\"InternalRef\"\u003e8\u003c/span\u003e (a), for the red marked target point with coordinates (3,4), the nearest background point should be the background point directly below it and coordinates (4,4). However, if the average block method is adopted, the background point directly below will be divided into another data set and will not participate in the calculation, and the calculation result is wrong. Therefore, when dividing the data, it is required that the two data sets contain all the data required for their own calculation, as shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig8\" class=\"InternalRef\"\u003e8\u003c/span\u003e (b), so that the real background points can be added to the calculation.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eIn the second step of the flowchart, two arrays are loaded into the memory allocated by the two implementations, and the calculation results of the two arrays can be obtained at the same time. The coordinate calculation process is regarded as a function, and the whole process can be described by B '= F (B) and C' = F (C). B 'and C' are the results calculated in different processors, as shown in Fig.\u0026nbsp;9, in which the red and green boxes show different calculation results of data.\u003c/p\u003e \u003cp\u003eAt this time, the calculation results can ensure that the data results at the average boundary position are accurate. As shown in Fig.\u0026nbsp;10, the calculated data sets are extracted according to the average block size to obtain the two data sets to be merged.\u003c/p\u003e \u003cp\u003eThe two datasets are merged by the x-coordinate, and the result is shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig9\" class=\"InternalRef\"\u003e11\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eThe pseudo code of the whole process is as follows:\u003c/p\u003e \u003cp\u003e(1) Import the original data array with the size of k\u0026times;k\u0026times;k;\u003c/p\u003e \u003cp\u003e(2) The array is partitioned according to the number of processors 'm':\u003c/p\u003e \u003cp\u003e{S1=[0: k/m\u0026thinsp;+\u0026thinsp;2,0: k/m\u0026thinsp;+\u0026thinsp;2,0: k/m\u0026thinsp;+\u0026thinsp;2), \u0026hellip;, Sm=[ ((m-1)k)/m:k, ((m-1)k)/m:k, ((m-1)k)/m:k) };\u003c/p\u003e \u003cp\u003e(3) Parallel computing: {D1\u0026thinsp;=\u0026thinsp;Dist (S1), ..., Dm\u0026thinsp;=\u0026thinsp;Dist (Sm)};\u003c/p\u003e \u003cp\u003e(4) Extract dataset:{E1\u0026thinsp;=\u0026thinsp;Extract (D1,), \u0026hellip;, Em\u0026thinsp;=\u0026thinsp;Extract (Dm) };\u003c/p\u003e \u003cp\u003e(5) Merge the results: Result\u0026thinsp;=\u0026thinsp;E1\u0026thinsp;+\u0026thinsp;E2 +... + Em-1\u0026thinsp;+\u0026thinsp;Em;\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec9\" class=\"Section2\"\u003e \u003ch2\u003e2.4 Deal with the complex boundary\u003c/h2\u003e \u003cp\u003eIn the PCEDT algorithm, all the background points should be included in the data segmentation, but the shape and size of the holes are irregular for most porous materials, it is difficult to tell directly from the human eye the range of data that would require the addition of additional data blocks. Figure\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e(a) is a two-dimensional digital slice from a real limestone digital image. Figure\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e(b) is the result calculated by the CEDT algorithm. Figure\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e(c) is the result of the PCEDT algorithm (take an additional line of data at the boundary position), and you can see that the distance transformation results for the labeled regions differ.\u003c/p\u003e \u003cp\u003eIn Fig.\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e(c), it can be observed that the lower half of the partitioned data block does not contain the nearest background pixel of the target pixel in the yellow-labeled area ( the data in the green-labeled area of figure (b)). During parallel computation, the green-labeled pixels on the left side of Fig.\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e (c) are considered to be the shortest background pixels added to the computation, resulting in a computational error. Therefore, the reason for the error is that there is a problem in the selection of the block region, and the correct background points cannot be divided into the correct data set, so a query module algorithm is needed, the value of the block region is obtained before parallel computation is performed.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eIn digital cores, structural defects and abrupt changes of pore size often exist at the boundary, so it is necessary to describe the changes of pore size at the boundary. In order to accurately determine the range of the block area, CEDT algorithm can be used at the boundary position. The number of intermediate rows serves as the initial cut-off point, starting with the central two rows and extending the computational range in opposite directions along the x-axis, until there are no longer coordinate results in the outermost data that are larger or smaller than the x axis of the boundary position. At this time, the maximum or minimum value of the x-coordinate of the calculation area is the value additionally divided into the data block.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eTherefore, through the query module, we can know that the upper half of the dataset does not need to take additional data from the lower half of the dataset, and the lower half of the dataset needs to take two rows of data from the upper half of the dataset, and re-divide the data. The result is shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig12\" class=\"InternalRef\"\u003e14\u003c/span\u003e (a). The calculation results of different processors are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig12\" class=\"InternalRef\"\u003e14\u003c/span\u003e(b), and the final calculation results are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig12\" class=\"InternalRef\"\u003e14\u003c/span\u003e(c).\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eAfter repartition, the distance transformation value of each point can be calculated accurately by parallel computation, which is the same as Fig.\u0026nbsp;\u003cspan refid=\"Fig10\" class=\"InternalRef\"\u003e12\u003c/span\u003e(b), indicating that the query module can be used accurately. Using the coincidence query module, the computer can get the correct coincidence area range, rationalize the data division process, and save memory space and CPU use to the greatest extent. The addition of the query module solves to the error-prone problem of the original PCEDT algorithm when the boundary position aperture belongs to a specific structural feature.\u003c/p\u003e \u003c/div\u003e"},{"header":"3.\tResults","content":"\u003cp\u003eIn order to test the calculation speed of the algorithm, a slice taken from the Estaillades limestone sample is shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig13\" class=\"InternalRef\"\u003e15\u003c/span\u003e(a). Three algorithms were used to calculate the distance transformation of the slice. The result is shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig13\" class=\"InternalRef\"\u003e15\u003c/span\u003e.\u003c/p\u003e \u003cp\u003eAs shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig14\" class=\"InternalRef\"\u003e16\u003c/span\u003e, the EDT algorithm always takes longer than the CEDT algorithm for the same size data set. The time difference between the two algorithms increases with the increase of the size of the data set. For 50\u0026times;50 dataset, the difference was 164 times, and when the dataset grew to 200\u0026times;200, the difference was 2,623 times. The huge difference in calculation time caused by different calculation algorithms can prove that compared with the EDT algorithm, the CEDT algorithm is more efficient and can save a lot of time.\u003c/p\u003e \u003cp\u003eIn Fig.\u0026nbsp;\u003cspan refid=\"Fig15\" class=\"InternalRef\"\u003e17\u003c/span\u003e, the PCEDT algorithm takes less time than the CEDT algorithm, and the difference between the two algorithms increases with the increase of the data set. But computing time is not only about size, but also about the content of the data. For small-size data, if the data set contains more measured points, the PCEDT algorithm will take a longer time to compute.\u003c/p\u003e \u003cp\u003eIn order to prove that the algorithm can also run normally in practical applications. As shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig16\" class=\"InternalRef\"\u003e18\u003c/span\u003e, Estaillades Limestone with 5.7 micron resolution, 11.8% porosity was selected as the sample. For a data cube, even a small increase in size can lead to a significant increase in computation. Once the data cube size exceeds the limit size, the EDT algorithm cannot complete the calculation in the specified time. Therefore, only CEDT and PCEDT algorithms are used to calculate the samples, and the results are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig17\" class=\"InternalRef\"\u003e19\u003c/span\u003e. Comparing the pore image with the distance transform image can help to analyze the position of the operation.\u003c/p\u003e \u003cp\u003eCompared with the results of the slice data, the two algorithms have a greater difference in calculating limestone samples. With the increasing of sample size, compared with PCEDT algorithm, CEDT algorithm takes more computation time. For a data cube of size 50\u003csup\u003e3\u003c/sup\u003e, the difference was 2 times, and when the data cube size grew to 300\u003csup\u003e3\u003c/sup\u003e, the difference was 3 times which can save about 7 minutes.\u003c/p\u003e"},{"header":"4.\tDiscussion","content":"\u003cdiv id=\"Sec12\" class=\"Section2\"\u003e \u003ch2\u003e4.1. Result accuracy discussion\u003c/h2\u003e \u003cp\u003eAs shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig18\" class=\"InternalRef\"\u003e20\u003c/span\u003e(a), a data set of 16\u0026times;16 is constructed to demonstrate the accuracy of the PCEDT algorithm. The black blocks represent pores, and the white blocks represent solids. Calculate the sample using the EDT algorithm and the PCEDT algorithm, and the results are as follows:\u003c/p\u003e \u003cp\u003eFigure\u0026nbsp;\u003cspan refid=\"Fig18\" class=\"InternalRef\"\u003e20\u003c/span\u003e(c) shows that the original data is divided into four parts and then transformed by the PCEDT algorithm. In (b) and (c), the blocks corresponding to the positions have the same color, so the results of the two algorithms are consistent. In addition, the color of the pore center is darker and the color of the edge is lighter, which conforms to the law of distance transformation, proving that the calculation results can be used.\u003c/p\u003e \u003cp\u003eConsidering that large data cubes are often used in practical applications, a data cube of size 500\u003csup\u003e3\u003c/sup\u003e is selected as a sample and the result is shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig19\" class=\"InternalRef\"\u003e21\u003c/span\u003e. In the original image (a), red represents the pore area and purple represents the solid area. In order to observe the pore distribution and the result of distance transformation, the pore is extracted. In contrast (c) and (d), the corresponding positions have the same color and the same change trend.\u003c/p\u003e \u003cp\u003eIn order to accurately study the distance transformation results of each voxel, a data set with the size of 10\u0026times;10\u0026times;10 was extracted from the above samples as shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig20\" class=\"InternalRef\"\u003e22\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eComparing (B) and (C) in each pore point, it can be found that the corresponding position has the same color. Therefore, it can be proved that the PCEDT algorithm is also suitable for data cubes, and the result of distance transformation is accurate and reliable.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec13\" class=\"Section2\"\u003e \u003ch2\u003e4.2. CPU utilization and memory usage\u003c/h2\u003e \u003cp\u003eThe time complexity and space complexity of the three algorithms are calculated in parallel as follows:\u003c/p\u003e \u003cp\u003e \u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab1\" border=\"1\"\u003e \u003ccaption language=\"En\"\u003e \u003cdiv class=\"CaptionNumber\"\u003eTable 1\u003c/div\u003e \u003cdiv class=\"CaptionContent\"\u003e \u003cp\u003eTime complexity and space complexity\u003c/p\u003e \u003c/div\u003e \u003c/caption\u003e \u003ccolgroup cols=\"4\"\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c3\" colnum=\"3\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c4\" colnum=\"4\"\u003e\u003c/div\u003e \u003cthead\u003e \u003ctr\u003e \u003cth align=\"left\" colname=\"c1\"\u003e\u0026nbsp;\u003c/th\u003e \u003cth align=\"left\" colname=\"c2\"\u003e \u003cp\u003eEDT\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c3\"\u003e \u003cp\u003eCEDT\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c4\"\u003e \u003cp\u003ePCEDT\u003c/p\u003e \u003c/th\u003e \u003c/tr\u003e \u003c/thead\u003e \u003ctbody\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eTime complexity\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003eO(n\u003csup\u003e2\u003c/sup\u003e)\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003eO(4n)\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c4\"\u003e \u003cp\u003eO(4n)\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eSpatial complexity\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003eO(1)\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003eO(n)\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c4\"\u003e \u003cp\u003eO(n)\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003c/tbody\u003e \u003c/colgroup\u003e \u003c/table\u003e\u003c/div\u003e \u003c/p\u003e \u003cp\u003eBecause the PCEDT algorithm uses more processors, more calculations are done in the same amount of time. In a 3\u0026times;3\u0026times;3 neighborhood, the range of n from 0 to 26, and the number of statement executions within the same time are shown in Table\u0026nbsp;\u003cspan refid=\"Tab2\" class=\"InternalRef\"\u003e2\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab2\" border=\"1\"\u003e \u003ccaption language=\"En\"\u003e \u003cdiv class=\"CaptionNumber\"\u003eTable 2\u003c/div\u003e \u003cdiv class=\"CaptionContent\"\u003e \u003cp\u003eThe execution time of the algorithm is judged by the number of statement execution\u003c/p\u003e \u003c/div\u003e \u003c/caption\u003e \u003ccolgroup cols=\"3\"\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c3\" colnum=\"3\"\u003e\u003c/div\u003e \u003cthead\u003e \u003ctr\u003e \u003cth align=\"left\" colname=\"c1\"\u003e \u003cp\u003eAlgorithms\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c2\"\u003e \u003cp\u003eCEDT\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c3\"\u003e \u003cp\u003ePCEDT\u003c/p\u003e \u003c/th\u003e \u003c/tr\u003e \u003c/thead\u003e \u003ctbody\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eNumber of statements executed\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003e0\u0026thinsp;~\u0026thinsp;104\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003e0\u0026thinsp;~\u0026thinsp;416\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003c/tbody\u003e \u003c/colgroup\u003e \u003c/table\u003e\u003c/div\u003e \u003c/p\u003e \u003cp\u003eQuerying the CPU utilization and memory occupation of the computer can make an intuitive explanation of the time complexity and space complexity. In the 650\u003csup\u003e3\u003c/sup\u003e limestone samples, 100\u003csup\u003e3\u003c/sup\u003e data sets were selected and processed by the PCEDT algorithm and PDT algorithm, which cost 14705.71s and 7.34s respectively. The processor used in the computer is Intel's Core i5-7300 quad-core processor. The CPU utilization and memory occupancy of the EDT and PCEDT algorithms are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig21\" class=\"InternalRef\"\u003e23\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eThe CPU utilization and memory usage of the EDT algorithm are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig21\" class=\"InternalRef\"\u003e23\u003c/span\u003e(a). During the whole process, CPU utilization fluctuated from 58\u0026ndash;46% based on a 52% baseline, and memory utilization remained stable at 27%. The CPU utilization and memory usage of the PCEDT algorithm are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig21\" class=\"InternalRef\"\u003e23\u003c/span\u003e(b). In the whole process, CPU utilization and memory occupancy are maintained at a high level.\u003c/p\u003e \u003cp\u003eThe difference in the number of processors used by the two algorithms results in a difference in CPU utilization. The EDT algorithm uses only one processor, while the PCEDT algorithm uses four processors for higher CPU utilization. Therefore, although the time complexity of the algorithm has not changed, the amount of data processed in the same time increases, and the overall computational efficiency is improved. As a result, the computing time has been drastically reduced.\u003c/p\u003e \u003cp\u003eThe memory usage of the two algorithms is consistent with the theoretical analysis. Compared to the EDT algorithm, the parallel computing algorithm uses more memory because the four processors simultaneously require the system to allocate memory for computation. The experiment divided all data into 6 blocks, if divided into more blocks, can reduce the memory consumption to some extent, but the total memory consumption will still be maintained at a high level.\u003c/p\u003e \u003cp\u003eIn conclusion, despite the high memory footprint of the parallel computing algorithm, its efficient CPU utilization makes it faster to complete the computation. Therefore, parallel computing has more advantages in practical application.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec14\" class=\"Section2\"\u003e \u003ch2\u003e4.3. Applicability comparison\u003c/h2\u003e \u003cp\u003eThe detailed description of pore space based on the digital image is a new algorithm. Distance transformation, as the basis of dividing pore space, is an important part of the work. In the past, the EDT algorithm was mostly used for distance transformation, and it took a long time to get the final result. In order to prove the superiority of the PCEDT algorithm in the practical application field, a comparative experiment was carried out with a cube size of 50\u003csup\u003e3\u003c/sup\u003e, 100\u003csup\u003e3\u003c/sup\u003e, 200\u003csup\u003e3\u003c/sup\u003e, 3003, 400\u003csup\u003e3\u003c/sup\u003e, 500\u003csup\u003e3\u003c/sup\u003e, 600\u003csup\u003e3\u003c/sup\u003e, 700\u003csup\u003e3\u003c/sup\u003e.\u003c/p\u003e \u003cp\u003eAs shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig22\" class=\"InternalRef\"\u003e24\u003c/span\u003e, when the size is 50\u003csup\u003e3\u003c/sup\u003e, the results can be calculated by all three algorithms. Although the calculation time is quite different, it is still within a reasonable range. When the size is 100\u003csup\u003e3\u003c/sup\u003e, the EDT algorithm takes 4 hours to get the result, while the CEDT and PCEDT algorithms can still complete the calculation faster. In the process of increasing the size to 700\u003csup\u003e3\u003c/sup\u003e, the EDT algorithm cannot get the result in the effective time. Although the CEDT algorithm can get the result, it takes 2\u0026thinsp;~\u0026thinsp;4 times more time than parallel computation.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eOnly CEDT and PCEDT algorithms are used to calculate data sizes larger than 1000\u003csup\u003e3\u003c/sup\u003e. The results are shown in Fig.\u0026nbsp;\u003cspan refid=\"Fig23\" class=\"InternalRef\"\u003e25\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eIn practice, the data of rock samples is very large. It is often calculated by taking the representative unit at one corner of the rock. The size of the representative unit is from 80 to 300, which is determined by the permeability of the sample. The comparative experiment shows that, when the size exceeds 50\u003csup\u003e3\u003c/sup\u003e, the EDT algorithm is no longer suitable for calculation. The PCEDT algorithm can still get the results in about 3 minutes when the size is 300\u003csup\u003e3\u003c/sup\u003e. Therefore, in the practical application, the PCEDT algorithm has more applicability.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec15\" class=\"Section2\"\u003e \u003ch2\u003e4.4. Comparison of natural data and artificial data\u003c/h2\u003e \u003cp\u003eIn the course of the experiment, artificial data is often used to test because it is difficult to obtain natural data. In order to compare the differences between natural data and man-made data in the calculation process, the following calculations are carried out. The existing man-made data with porosity of 10.8% and natural data with porosity of 11.4% are 500 \u0026times; 500 \u0026times; 500. The calculation results are as follows:\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eAs can be seen from Fig.\u0026nbsp;\u003cspan refid=\"Fig24\" class=\"InternalRef\"\u003e26\u003c/span\u003e, when the data size is 50\u003csup\u003e3\u003c/sup\u003e, the calculation time of natural data is longer than that of artificial data, which is caused by the unclear pore distribution in a small range. With the increase of the data size, when the porosity of the two models is close to each other, the computation time of artificial data is always greater than that of natural data, which is about 1.5\u0026thinsp;~\u0026thinsp;3 times. According to the calculation principle of the algorithm, it is inferred that the pore distribution of artificial data is relatively concentrated, and the algorithm needs to perform the second scan calculation to obtain the distance transformation result, while the pore distribution of natural data is relatively scattered, and the distance transformation result can often be obtained in the first scan process. Therefore, it can be inferred that the prediction of real model data with the same porosity based on the results of artificial data may result in some error.\u003c/p\u003e \u003c/div\u003e"},{"header":" 5. Conclusions","content":"\u003cp\u003eDistance transform is widely used in digital analysis, which is the basis of pore segmentation and pore network modeling, which can help to analyze the structure of porous media and predict the performance of porous media. Aiming at the problems of a large amount of computation and long computation period in the practical application of distance transformation, a parallel implementation of fast Euclidean distance transform in neighborhood based on data set decomposition is proposed in this paper, which can save computation time to a great extent, in order to avoid the waste of computer resources. Finally, three algorithms are used to verify the different size arrays. The results show that the CEDT algorithm is accurate and effective, which greatly reduces the calculation time compared with the EDT algorithm; Compared with the CEDT algorithm, parallel computing can further save time and reduce memory consumption.\u003c/p\u003e"},{"header":"Declarations","content":"\u003cp\u003e \u003ch2\u003e \u003cspan type=\"SmallCaps\" class=\"SmallCaps\" name=\"Emphasis\"\u003eConflicts of Interest\u003c/span\u003e \u003c/h2\u003e \u003cp\u003eThe authors declare no conflict of interest.\u003c/p\u003e \u003c/p\u003e\u003ch2\u003eFunding\u003c/h2\u003e \u003cp\u003eThe research was funded by National Key Research and Development Program of China [No.2021YFD1600402], National Natural Science Foundation of China [No. 51704265] (Research on two component gas diffusion-convection model in enhancing shale gas recovery with CO2 injection PI: Dr. Chaohua Guo), Key Research and Development Plan of Shaanxi Province [Grant No. 2020GXLH-Z-031], Key Scientific Research Project of Weinan City [Grant No. 2020ZDYF-GYCX-107], Key Scientific Research Project of Education Department of Shaanxi Province [Grant No. 20JS106], Central Guidance on Local Science and Technology Development Fund of Shaanxi Province [NO.2020-ZYYD-NCC-9], Shaanxi Provincial Department of Education Collaborative Innovation Center Project [20JY052], National Natural Science Foundation of China [NO.52072075], Science and technology planning project of Qindu District, Xianyang City [NO.2021QKJ-001], Outstanding Youth Science Fund of Shaanxi Province [No.2018JC-028]. Project of Postgraduate Education and Teaching Reform Research at North China University of Technology in 2023 [YJS2023JG17].\u003c/p\u003e\u003ch2\u003eAuthor Contribution\u003c/h2\u003e\u003cp\u003eConceptualization, investigation, writing \u0026ndash; original, X.S.; methodology, review \u0026amp; editing, T.M.; resources, M.L.; review \u0026amp; editing, funding acquisition, X.W, Y.C. All authors have read and agreed to the published version of the manuscript.\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\u003cli\u003e\u003cspan\u003eHerman R. Schubert, Andrei C. Jalba, Alexandru C. Telea, 2020. Feature preserving noise removal for binary voxel volumes using 3D surface skeletons. Computers and Graphics, 87, 30\u0026ndash;42. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.cag.2019.12.003\u003c/span\u003e\u003cspan address=\"10.1016/j.cag.2019.12.003\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eTang,Y,Y., You, X., 2003. Skeletonization of ribbon-like shapes based on a new wavelet function. IEEE Transactions on Pattern Analysis \u0026amp; Machine Intelligence, 25(9), 1118\u0026ndash;1133. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/TPAMI.2003.1227987\u003c/span\u003e\u003cspan address=\"10.1109/TPAMI.2003.1227987\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBourgeois, F., Emptoz, H., 2007. Skeletonization by Gradient Regularization and Diffusion. International Conference on Document Analysis and Recognition. IEEE, 2, 1118\u0026ndash;1122. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/ICIP.2007.4379239\u003c/span\u003e\u003cspan address=\"10.1109/ICIP.2007.4379239\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eSaha, P., Borgefors, G., Baja, G., 2016. A survey on skeletonization algorithms and their applications. Pattern Recognition Letters, 76, 3\u0026ndash;12. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.patrec.2015.04.006\u003c/span\u003e\u003cspan address=\"10.1016/j.patrec.2015.04.006\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eZhang, J., Malmberg, F., Sclaroff, S.,2019. A Distance Transform Perspective. Springer, Cham. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1007/978-3-030-04831-0_3\u003c/span\u003e\u003cspan address=\"10.1007/978-3-030-04831-0_3\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eJin, X., Kim, J.,2017. A 3d skeletonization algorithm for 3d mesh models using a partial parallel 3d thinning algorithm and 3d skeleton correcting algorithm. Applied Sciences, 139(7), 1\u0026ndash;17. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.3390/app7020139\u003c/span\u003e\u003cspan address=\"10.3390/app7020139\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDurix, B., Chambon, S., Leonard, K., Mari, JL., Morin, G.,2019. The Propagated Skeleton: A Robust Detail-Preserving Approach. Discrete Geometry for Computer Imagery, 343\u0026ndash;354. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1007/978-3-030-14085-4_27\u003c/span\u003e\u003cspan address=\"10.1007/978-3-030-14085-4_27\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eLiu, H., Wu, Z., Frank, D., et al.,2012. On the generation and pruning of skeletons using generalized voronoi diagrams. Pattern Recognition Letters, 33(16), 2113\u0026ndash;2119. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.patrec.2012.07.014\u003c/span\u003e\u003cspan address=\"10.1016/j.patrec.2012.07.014\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBurch, M., Lith, J. V., Waterlaat, N., \u0026amp; Winden, J. V. ,2020. Voronoier: From Images to Voronoi Diagrams. Visual Information Communication and Interaction (VINCI). 16, 1\u0026ndash;9. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1145/3430036.3430043\u003c/span\u003e\u003cspan address=\"10.1145/3430036.3430043\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eYang F, Li X, Shen J,2020. Msb-fcn: multi-scale bidirectional fcn for object skeleton extraction. IEEE Transactions on Image Processing,30,2301\u0026ndash;2312. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/TIP.2020.3038483\u003c/span\u003e\u003cspan address=\"10.1109/TIP.2020.3038483\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eLiu, W., Jiang, H., Bai, X., et al.,2013. Distance transform-based skeleton extraction and its applications in sensor networks. IEEE Transactions on Parallel \u0026amp; Distributed Systems, 24(9), 1763\u0026ndash;1772. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/TPDS.2012.300\u003c/span\u003e\u003cspan address=\"10.1109/TPDS.2012.300\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDenk, M., Rother, K., Paetzold, K, 2021. Fully Automated Subdivision Surface Parametrization for Topology Optimized Structures and Frame Structures Using Euclidean Distance Transformation and Homotopic Thinning. pp 18\u0026ndash;27. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1007/978-3-662-63143-0_2\u003c/span\u003e\u003cspan address=\"10.1007/978-3-662-63143-0_2\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eZHAO Jian-peng, CHEN Hui, et al, 2020. Research advance of petrophysical application based on digital core technology,35(3), 1099\u0026ndash;1108. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.6038/pg2020DD0486\u003c/span\u003e\u003cspan address=\"10.6038/pg2020DD0486\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eQajar, J., Arns, C.,2016. Characterization of reactive flow-induced evolution of carbonate rocks using digital core analysis- part 1: assessment of pore-scale mineral dissolution and deposition. Journal of Contaminant Hydrology, 192, 60\u0026ndash;86. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.jconhyd.2016.06.005\u003c/span\u003e\u003cspan address=\"10.1016/j.jconhyd.2016.06.005\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eXia, H., Tucker, P., 2010. Finite volume distance field solution applied to medial axis transform. In: 48th AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition, 1(82), 114\u0026ndash;134. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.2514/6.2010-1082\u003c/span\u003e\u003cspan address=\"10.2514/6.2010-1082\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCuisenaire, O., Macq, B.,1999. Fast Euclidean distance transformation by propagation using multiple neighborhoods, Computer Vision and Image Understanding, 76(2), 163\u0026ndash;172. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1006/cviu.1999.0783\u003c/span\u003e\u003cspan address=\"10.1006/cviu.1999.0783\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDatta, A., Soundaralakshmi, S., 2001. Constant-time algorithm for the euclidean distance transform on reconfigurable meshes. Journal of Parallel \u0026amp; Distributed Computing, 61(10), 1439\u0026ndash;1455. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1006/jpdc.2000.1684\u003c/span\u003e\u003cspan address=\"10.1006/jpdc.2000.1684\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eSaito, T., Toriwaki, J., 1994. New algorithms for Euclidean distance transformation of an n-dimensional digitized picture with applications, Pattern Recognition, 27(11), 1551\u0026ndash;1565. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/0031-3203(94)90133-3\u003c/span\u003e\u003cspan address=\"10.1016/0031-3203(94)90133-3\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eWang J, Ying T .,2013. Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions. Pattern Recognition, 46(1), 230\u0026ndash;242. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.patcog.2012.07.030\u003c/span\u003e\u003cspan address=\"10.1016/j.patcog.2012.07.030\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eRenata M.C.R. de Souza, Francisco de A.T. de Carvalho, 2004. Clustering of interval data based on city\u0026ndash;block distances,Pattern Recognition Letters,25(3), 353\u0026ndash;365.\u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.patrec.2003.10.016\u003c/span\u003e\u003cspan address=\"10.1016/j.patrec.2003.10.016\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eGang Wu, Linmin Xu, 2019. Shape description and recognition by implicit chebyshev moments. Pattern recognition letters, 128, 137\u0026ndash;145. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.patrec.2019.08.031\u003c/span\u003e\u003cspan address=\"10.1016/j.patrec.2019.08.031\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eT. A. Al-Shurbaji, K. A. AlKaabneh, I. Alhadid, R. Masa\u0026rsquo;deh, 2021. An Optimized Scale-Invariant Feature Transform Using Chamfer Distance in Image Matching. 31(2), 971\u0026ndash;985. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.32604/iasc.2022.019654\u003c/span\u003e\u003cspan address=\"10.32604/iasc.2022.019654\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eLotufo, R., Zampirolli, F.,2000. Fast Euclidean distance transform using a graph-search algorithm. Computer Graphics and Image Processing, 2000. Proceedings XIII Brazilian Symposium. IEEE, 269\u0026ndash;275. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/SIBGRA.2000.883922\u003c/span\u003e\u003cspan address=\"10.1109/SIBGRA.2000.883922\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eSvensson, S., Borgefors, G.,2002. Digital distance transforms in 3D images using information from neighbourhoods up to 5\u0026times;5\u0026times;5. Comput Vis Image Und, 88, 24\u0026ndash;53. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1006/cviu.2002.0976\u003c/span\u003e\u003cspan address=\"10.1006/cviu.2002.0976\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMaurer, C., Qi, R., Raghavan, V.,2003. A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions. IEEE Trans Pattern Anal Mach Intell, 25, 265\u0026ndash;270. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/TPAMI.2003.1177156\u003c/span\u003e\u003cspan address=\"10.1109/TPAMI.2003.1177156\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eShih, F., Wu, Y.,2004. Fast Euclidean distance transformation in two scans using a 3\u0026times;3 neighborhood. Comput Vis Image Und, 93, 195\u0026ndash;205. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.cviu.2003.09.004\u003c/span\u003e\u003cspan address=\"10.1016/j.cviu.2003.09.004\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eM. Manduhu, M. W. Jones.,2019. A work efficient parallel algorithm for exact euclidean distance transform. IEEE Transactions on Image Processing, 28(11), 5322\u0026ndash;5335. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1109/TIP.2019.2916741\u003c/span\u003e\u003cspan address=\"10.1109/TIP.2019.2916741\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eElizondo-Leal JC, Ramirez-Torres JG, Barr\u0026oacute;n-Zambrano JH, et al.,2020. Parallel Raster Scan for Euclidean Distance Transform. Symmetry. 12(11):1808. \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.3390/sym12111808\u003c/span\u003e\u003cspan address=\"10.3390/sym12111808\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Parallel computing, Euclidean distance transformation, Digital Core, Image Processing, Skeleton information","lastPublishedDoi":"10.21203/rs.3.rs-4457889/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4457889/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eDistance transform (DT) can accurately represent spatial information relationship, and it has been widely used in digital core analysis, such as computer image processing, pattern recognition, and etc. However, for large-resolution 2D/3D images, the existing serial Euclidean distance transform (EDT) algorithm is time-consuming and memory-consuming. This paper proposed a parallel implementation of fast Euclidean distance transform in neighborhood based on data set decomposition, which is called as Parallel Computing EDT (PCEDT). The distance transformation is completed efficiently and accurately by data segmentation, batch calculation, and results combination. Compared with other EDT algorithms, PCEDT algorithm is more efficient and more suitable, especially for 2000\u003csup\u003e3\u003c/sup\u003e Voxels to 4000\u003csup\u003e3\u003c/sup\u003e voxels data amount to deal with when applied in practical applications.\u003c/p\u003e","manuscriptTitle":"A Fast Distance Transform Algorithm Based on Parallel Computing for Digital Rock Image Processing ","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-06-07 20:44:09","doi":"10.21203/rs.3.rs-4457889/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"3a8f9adc-79c4-48e7-93fb-5dce734115ba","owner":[],"postedDate":"June 7th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-07-20T01:23:31+00:00","versionOfRecord":[],"versionCreatedAt":"2024-06-07 20:44:09","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4457889","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4457889","identity":"rs-4457889","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}