Kim* , Kim** , and Lee*: Cell Counting Algorithm Using Radius Variation, Watershed and Distance Transform ## Taehoon Kim* , Donggeun Kim** and Sangjoon Lee* # ** Cell Counting Algorithm Using Radius Variation, Watershed and Distance Transform ** **Abstract:** This study proposed the structure of the cluster's cell counting algorithm for cell analysis. The image required for cell count is taken under a microscope. At present, the cell counting algorithm is reported to have a problem of low accuracy of results due to uneven shape and size clusters. To solve these problems, the proposed algorithm has a feature of calculating the number of cells in a cluster by applying a radius change analysis to the existing distance conversion and watershed algorithm. Later, cell counting algorithms are expected to yield reliable results if applied to the required field. **Keywords:** Cell-Counting , Distance Transform , Radius Variation Analysis , Watershed Algorithm ## 1. Introduction Cell analysis uses images acquired under a microscope and is mainly used in areas such as pathology, biology, and medicine. There are various methods of cell analysis such as cell cycle, cell count, cytotoxicity, etc. [1]. Among them, cell count plays the most basic and essential role. Cell count algorithms have been continuously developed in studies such as classification of cancer cells and normal cells and confirmation of change in cancer cell count [2]. In addition, many algorithms have been developed for automated cell analysis based on machine learning [3]. Among the existing cell-counting algorithms, the method using the distance transform and the watershed algorithm has high accuracy for a single cell, but the accuracy of cluster separation is relatively low [4,5]. Clusters are difficult to count when two or more cells overlap or aggregate. This is less accurate results for cell number change experiments. In this study, we applied radius variation analysis to remedy this problem. The cell images used for counting were obtained by photographing stomach cancer cells with confocal microscope as shown in Fig. 1. The specification of the microscope is as follows. (1) Scan resolution: up to 2048×2048 pixels. (2) Scan rotation: free 360 rotation, variable by increments of 1, free X-Y offset. (3) Detectors: 2-PMT (photo multiplier tube) fluorescence detectors, 1-PMT transmit detector. (4) Lasers: 405 nm (diode laser), 488 nm (solid-state), 561 nm (solid-state), 639 nm (diode laser). (5) Objectives: 10×, 20×, 40×, 63×, 100×. The resolution of the image is 512×512 pixels. Fig. 1. Confocal laser scanning microscope. Stomach cancer cells have an elliptical shape; hence, the cluster shape and size are unbalanced. First, we separated only the clusters by applying Gaussian blur [6], Otsu’s method [7], and a median filter [8] to MKN-28 (stomach cancer cells) images stained with DAPI (4',6-diamidino-2-phenylindol) [9]. The separated clusters were computed by applying the distance transform [10] and the watershed algorithm [11] to calculate the distance between the centerline and the outline. Finally, the number of cells constituting the cluster was calculated by the number of points at which the distance rapidly varies. As a result, the number of cells in the cluster can be calculated, which improves the accuracy of the result. ## 2. Algorithm The proposed algorithm is configured as shown in Fig. 2. First, a preprocessing process for binarization and noise reduction is performed on the cell image. After the preprocessing, group separation is performed as a single cell and as a cluster cell to calculate the number of single cells and the number of cluster cells. Finally, the cell inside the cluster is calculated by the watershed algorithm and the radius change analysis. Then, the total number of cells can be calculated as the sum of the single cell and the cluster internal cells. ##### 2.1 Preprocessing Preprocessing performs the conversion necessary to apply the cell-counting algorithm to image cells. First, the cell image is converted to grayscale, and then the Gaussian filter is applied to reduce noise. The threshold value is set using Otsu’s method. The outer cells are smoothly adjusted with a median filter. Fig. 3 shows the result of the preprocessing step. ##### 2.2 Cell Group Separation As the coefficient algorithms applied to each cell are different, they are divided into different groups. Fig. 4 shows the area distribution according to the number of cells. Based on this, flood fill and labeling are performed. Single cells and clusters are classified by the number of component pixels. Fig. 2. Flow diagram of our proposed cell-counting algorithm. Fig. 3. Result of preprocessing: (a) original cell (MKN-28) image and (b) preprocessed cell (MKN-28) image. Fig. 4. Probability graph by number of cells. ##### 2.3 Distance Transform and Watershed Algorithm Next, we calculate the number of single cells in the cluster. The distance transform is a method that calculates the distance between the internal space and the outline. The watershed algorithm uses the distance to find the center point. Fig. 5 shows clusters of overlapping single cells. Fig. 5(a) is the binarized image obtained from preprocessing. Fig. 5(b) shows that the brightness varies with the overlapped area. Fig. 5(c) shows the center points of the cells. We can observe the center point of a cell in a cluster with high-intensity components but not for other clusters. Fig. 5. Process of marking center point: (a) binarized cluster image, (b) result of distance transform, and (c) image of wrong center points and detected center points. ##### 2.4 Analysis Radius Variation This process computes a cluster whose cells could not be counted in the previous step. First, we measure the distance from the center point to the contour in the clockwise direction, as shown in the Fig. 6. Fig. 6(a) shows the distance between the center point and the outline in Fig. 6(b). The cells overlap at the point where the distance variation changes from a negative number to a positive number. Thus, the number of cells constituting the cluster can be estimated. Fig. 7 shows the step-wise cell-counting process. Fig. 6. Matching points with large distance change: (a) distance change between center point and contour, and (b) location of overlapped cells. Fig. 7. Cell-counting process images: (a) original cluster image, (b) preprocessed cluster image, and (c) distance transformed cluster image, (d) wrong center point cluster image, (e) overlapping detection, and (f) find the center point of each cell. ## 3. Result and Conclusion In this study, we attempt to solve the problem of reliably counting cells inside a cluster during cell counting by applying the distance transform and the watershed method. A change in the distance between the outline of the cluster and the center point results in a large change in the area where single cells overlap. Accordingly, the number of cells in the cluster can be calculated by the number of points at which a large change in the distance occurs. Fig. 8. Result of MKN-28 images used in cell counting experiments: (a) Image-1 and (b) Image-2. Fig. 8 shows the result of applying the proposed algorithm. Table 1 shows the results of cell count using Fig. 8 for each algorithm. In the experiment, 47 images of DAPI stained MKN-28 were used and the proposed method and two algorithms were compared. The watershed algorithm has a single-cell accuracy of about 94%, but the cluster accuracy is low at about 74%. In Otsu’s method, the accuracy of a single cell is about 95% and the accuracy of cluster is about 87%, which is higher than that of watershed algorithm. However, the proposed algorithm shows that the accuracy of a single cell is about 98% and the accuracy of a cluster is about 93%, which is about 6% higher than that of the existing algorithm. Table 1. Cell counting result according to the algorithm | Original | Watershed algorithm | Otsu’s Method | Proposed algorithm | Image-1 | 198 | 179 | 184 | 191 | Image-2 | 233 | 202 | 210 | 221 | ## Acknowledgement This research was financially supported by the Human Resource Training Project for Regional Innovation and Creativity (No. NRF-2014H1C1A1066998). ## Biography ##### Taehoon Kim https://orcid.org/0000-0002-8568-9833 He received B.S. and M.S. degrees from Department of Information and Communication Engineering, Sunmoon University in 2017 and 2019, respectively. He has worked on ILOODA Co. Ltd. as a Research Engineer since 2019. His research areas are embedded system, image processing, and pattern recognition. ## Biography ##### Donggeun Kim https://orcid.org/0000-0002-3824-9907 He received B.S. and M.S. degrees from Department of Information and Communication Engineering, Sunmoon University in 2017 and 2019, respectively. He has worked on ILOODA Co. Ltd. as a Research Engineer since 2019. His research areas are embedded system, image processing, and pattern recognition. He received a B.S. degree from Department of Information and Communication Engineering, Sunmoon University in 2017. He has worked on LIG Nex1 Co. Ltd. as a Research Engineer since 2020. His research areas are embedded system and image processing. ## Biography ##### Sangjoon Lee https://orcid.org/0000-0002-9829-4822 He received B.S. and M.S. degrees from Department of Information and Communication Engineering, Sunmoon University in 2017 and 2019, respectively. He has worked on ILOODA Co. Ltd. as a Research Engineer since 2019. His research areas are embedded system, image processing, and pattern recognition. He received a B.S. degree from Department of Information and Communication Engineering, Sunmoon University in 2017. He has worked on LIG Nex1 Co. Ltd. as a Research Engineer since 2020. His research areas are embedded system and image processing. He received a B.S. degree of measurement and control and a M.S. degree of Electron from the Myoungji University, Korea, in 2011 and 2005, respectively; a Ph.D. degree in Electrical and Electronic Engineering (biomedical engineering) from Yonsei University, Korea in 2011. He worked on Sunmoon University as a professor of Devision of Smart Automotive Engineering (2014-2019). He has worked on ILOODA Co. Ltd. as a Research Director in Institute of Medical Engineering since 2019.His research areas are embedded system, biosignal processing, pattern recognition and biometric system with biosignals. ## References - 1 H. Y. Kwon, M. S. Kim, K. W. Choi, H. J. Kwack, S. H. Yu, "LVQ_Merge clustering algorithm for cell image extraction,"
*Journal of Korea Multimedia Society*, vol. 20, no. 6, pp. 845-852, 2017.custom:[[[-]]] - 2 M. Klinger-Strobel, H. Suesse, D. Fischer, M. W. Pletz, O. Makarewicz, "A novel computerized cell count algorithm for biofilm analysis,"
*PloS One*, vol. 11, no. 5, 2016.custom:[[[-]]] - 3 S. J. Park, S. H. Park, J. G. Lee, S. B. Jang, Y. W. Ko, "Cell bead counting using machine learning scheme," in
*Proceedings of the KIISE*, 2017;vol. 44, no. 2, pp. 933-935. custom:[[[-]]] - 4 M. G. Cho, J. Shim, "Cluster cell separation algorithm for automated cell tracking,"
*Transactions of the Korean Society of Mechanical Engineers B*, vol. 37, no. 3, pp. 259-266, 2013.custom:[[[-]]] - 5 X. Du, S. Dua, "Segmentation of fluorescence microscopy cell images using unsupervised mining,"
*The Open Medical Informatics Journal*, vol. 4, pp. 41-49, 2010.custom:[[[-]]] - 6 X. Zhou, C. Wang, L. Wang, "Blind image quality assessment on Gaussian blur images,"
*Journal of Information Processing Systems*, vol. 13, no. 3, pp. 448-463, 2017.doi:[[[10.3745/JIPS.02.0059]]] - 7 Sarah Hachemi Benziane, Abdelkader Benyettou, "Dorsal Hand Vein Identification Based on Binary Particle Swarm Optimization,"
*Journal of Information Processing Systems*, vol. 13, no. 2, pp. 268-283, 2017.doi:[[[10.3745/JIPS.03.0066]]] - 8 T. Chen, K. K. Ma, L. H. Chen, "Tri-state median filter for image denoising,"
*IEEE Transactions on Image Processing*, vol. 8, no. 12, pp. 1834-1838, 1998.doi:[[[10.1109/83.806630]]] - 9 S. Jeong, Y. M. Lee, S. Lee, "Development of an automatic sorting system for fresh ginsengs by image processing techniques,"
*Human-centric Computing and Information Sciences*, vol. 7, no. 41, 2017.custom:[[[-]]] - 10 H. Talbot, B. C. Appleton, "Elliptical distance transforms and object splitting," in
*Proceedings of the 6th International Symposium on Mathematical Morphology*, Sydney, Australia, 2002;pp. 229-240. custom:[[[-]]] - 11 J. B. Choi, H. M. Kim, H. H. Ko, "Segmentation of colony image using watershed algorithm," in
*Proceedings of IEIE Conference (Fall)*, 2002;vol. 25, no. 2, pp. 853-856. custom:[[[-]]] |