# Context-Based Separation of Cell Clusters for the Automatic Biocompatibility Testing of Implant Materials

Authors: S. Buhl; B. Neumann; S. C. Schäfer
Journal: Journal of Computational Medicine
 (2014)

---

## Abstract

This paper presents a new method to separate cells on microscopic surfaces joined together in cell clusters into individual cells. Important features of this method are that the remaining object geometry is preserved and few contour points are required for finding joints between neighboring cells. There are alternative methods such as morphological operations or the watershed transformation based on the inverse distance transformation but they have certain disadvantages compared to the method presented in this paper. The discussed method contains knowledge-based components in form of a decision function and exchangeable rules to avoid unwanted separations.


---

## Body

## 1. Introduction

In the process of testing implant materials for biocompatibility, it is important to evaluate whether a material is suitable for use in human bodies. An important aspect of biocompatibility is the determination of the exact number of cells which are in contact with the surface of the material being tested. For the specimen preparation process, a suspension with a defined cell concentration reacts for a certain time with the substrate under test and allows the cells to settle on the contact surface. Afterwards, the cells are stained using the May-Grünwald suspension [1] to be easily identifiable amongst each other. Microscopic images (Figure 1) are used to evaluate the results. A major challenge is the separation of single cells in a cluster due to their very variable morphology. The examination of many samples shows that L929 cells often exhibit cell clusters at various positions. This paper is based on providing a method of identifying individual cells within these cell clusters.Figure 1
L929 cells on the substrate steel. Right: a biological cell division process, two joint cells which have a sand glass appearance.Several papers deal with different image processing methods for cell segmentation [2–7]. Depending on the image quality or the dyeing process, different segmentation methods may be the appropriate choice. If, for example, a noisy image has to be analyzed, the use of active contours could be advisable [3, 5–7].The separation of connected cells is still a great challenge. Several papers provide different approaches to separate cells of a specific type [8–11]. Due to the often simple morphology of the analyzed cell types, a separation of clusters with simple rules is possible.An iterative erosion method may create a separation of cells or objects at joining points between cells. After each iteration, it has to be checked whether separated objects have been created. The algorithm is not able to separate the cells without altering the cell contours. Therefore, a reconstruction of the cell area is required. A big disadvantage of this method is that it also removes or separates cell extensions, which is not acceptable in our case. An improved method for separating cells is described in [12] that leaves the cell contour unchanged. This method is known as opening by reconstruction. Compared to the method presented in the next section, this approach partially results in unwanted separation processes and requires about five times more computing time. If the local joining regions are considered to be objects which are being traced, the use of a hit-and-miss transformation [13] or a model-based method [14] is potential solution. But the morphological variation of the cells also leads to a variation of the joining shapes. Thus, a method is required which considers these circumstances.Another common procedure to separate connected cells is the watershed transformation based on the inverse distance transformation [15]. The method works well for cell types with a simple morphology, for example, peripheral blood and bone marrow samples. For biocompatibility testing, often cells of type L929 are used (Figure 1) but they are characterized by a strong varying morphology. Some cells are also creating cell extensions which are not allowed to be separated. These aspects have a negative impact on the segmentation result using the watershed transformation (Figure 12(e)).The method for the separation of connected cells described in [16] turns out to be suitable. This algorithm first detects the nuclei with the Histogram Backprojection method [17]; then the shortest paths between the nuclei are calculated by means of the A
* algorithm [18]. The contact points of connected cells usually have local joints between cells, which are determined by calculating the so-called dominant contour points (DCPs) [19]. With the help of these DCPs, the separation of the cells can be carried out. The disadvantage of the method described in [16] is the high computing time for the separation process due to the high complexity of the algorithm (Table 3). A further disadvantage of the above-mentioned algorithm is the inability to separate cells which are in a biological cell division process (Figure 1) since they contain no visible nucleus regions. The method presented in this paper increases the separation performance and reduces significantly the computing time for the process in [16]. The method is not restricted to cell structures; it can also be applied to general objects which have to be separated.


## 2. Materials and Methods

### 2.1. Cell Segmentation

The images were created by the Olympus XC10 camera, which is installed on an Olympus Bx51 M microscope with 100x magnification. The size of the images is1376
×
1032 pixel. The segmentation of the cell areas is carried out by a standard threshold procedure for all three color channels. The thresholds depend on the used staining method. In the case of the present May-Grünwald staining, the thresholds T
R
=
128, T
G
=
150, and T
B
=
150 are used. To determine suitable thresholds, ​
​an expert draws the contours of 20 different cells in the image. The same cells are also automatically segmented by using the default threshold values ​
​
T
R
=
T
G
=
T
B
=
128. With the help of the Jaccard coefficient, the similarity of the automatically generated cell areas compared to the reference areas can be measured. The automatic cell segmentation with subsequent calculation of the Jaccard coefficient is now iteratively performed with different threshold values. Finally the parameter set with the maximum Jaccard coefficient is used for cell segmentation. Due to a reliable staining process, the chosen parameters are robust for different images of one or more test samples.The resulting three binary imagesB
R, B
G, and B
B are then merged into one image B
Ges
=
B
R
∪
B
G
∪
B
B and a region labeling is performed. Only those segmented regions with a minimum area A
Min
⁡ which depends on the used cell type are further analyzed. To determine the minimum cell area for cells of type L929, the cells in 50 images were automatically segmented and had their respective cell areas calculated. Afterwards, a manual check by an expert was done to determine whether the segmented object is a cell or merely an artifact on the substrate surface. The smallest segmented cell was determined to have an area of C
MIN
=
276 pixel and the biggest segmented artifact was found to have an area of E
Max
⁡
=
102 pixel. A
Min
⁡ is defined as the average of the smallest cell area and the biggest artifact area:
(1)
A
Min
⁡
=
(
C
Min
⁡
+
E
Max
⁡
)
2
=
189
pixel
.
Finally small holes within the regions produced by the segmentation process are filled by the closing algorithm. The complete cell segmentation process is visualized in Figure 2.Figure 2
Cell segmentation process. The steps within the brackets are carried out for the cell region segmentation (Section2.1). The subsequent separation of clusters is described in Section 2.2.Figure2 shows the process of the presented method to segment the cell regions (Section 2.1) and then separating the clusters with help of the context-based separation method (Section 2.2).


### 2.2. Context-Based Separation

The new method presented in this paper is called the context-based separation (CBS). This method performs splitting operations on cells or other objects. This splitting is restricted to narrow joints between cells or objects. In an imagem clusters R
C
1
,
R
C
2
,
…
,
R
C
m are contained. Each cluster consists of several cells which have to be separated for further analysis. The approach of this method is shown by one cluster R
C. For purposes of clarity, R
C is defined as a representative of a cluster. Therefore, the cluster index can be ignored. This method is performed only at narrow joints R
A
n with n
=
1
,
2
,
…
,
x (Figure 5) where a separation process is carried out. For this purpose, the contour of the object R
C is sampled with a circular structural element C
1 with radius r
1 (Figure 3).Figure 3
The contour of the objectR
C is sampled by a circular structural element C
1.For eachnth (step width) contour point it is checked whether the background area B enclosed by C
1 consists of two separated subsets B
1 and B
2. B
1 and B
2 must be separated by the cell area enclosed by C
1 with R
A
n
=
C
1
∩
R
C (Figure 4). This is a necessary condition for a local joining of the object. A join is characterized by a dilatation at the ends. This is determined by creating a circular mask C
2 with radius r
2
=
a
•
r
1 which is generated concentrically around C
1. The parameter a is adjusted to this cell type. In our case a
=
2 is suitable. If values smaller than 1.5 are chosen, not all local joints are found. In contrast, if the value of a is set higher than 2.75, the circular mask gets much bigger than most of the local joints and the failure rate increases (Table 1).Table 1
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert is determined.
a
=
1.25
a
=
1.5
a
=
2.0
a
=
2.5
a
=
3.0
Relative deviation
8.6%
4.6%
2.7%
3.1%
5.4%Figure 4
The backgroundB within C
1 is separated by R
A in two subsets B
1 and B
2.Figure 5
With help ofC
1 and C
R it is checked whether a narrowing is present.With the help ofC
1 and C
2, the circular ring mask C
R is calculated with C
R
=
C
2
∖
C
1 and in the further course of the algorithm R
B
=
C
R
∩
R
C is determined (Figure 5). A join should be present when the decision function f
1
(
x
) assumes the value is true. For the case shown in Figure 5, where the point set R
B consists of 2 nonoverlapping or adjacent point sets R
B
1 and R
B
2, the decision function is defined as
(2)
f
1
(
x
)
=
(
|
R
B
1
|
≥
|
R
A
n
|
·
x
)
∧
(
|
R
B
2
|
≥
|
R
A
n
|
·
x
)
.
The set R
B can also comprise q nonoverlapping or adjacent sets of points (Table 4). The decision function f
1
(
x
) is then given by
(3)
f
1
(
x
)
=
(
|
R
B
1
|
≥
|
R
A
n
|
·
x
)
∧
(
|
R
B
2
|
≥
|
R
A
n
|
·
x
)
∧
⋯
(
|
R
B
q
|
≥
|
R
A
n
|
·
x
)
.
The symbol |
⋯
| denotes the number of pixels of a set. In our case the parameter x is set to x
=
1.5. If the chosen value of x is too high, some local joints are not found. On the other hand if the value of x is a too small, the algorithm provides too many local joints (Table 2).Table 2
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert.
x
=
1.25
x
=
1.5
x
=
2.0
x
=
2.5
x
=
3.0
Relative deviation
5.8%
2.7%
2.9%
3.8%
7.4%Table 3
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert.
y
=
1.5
y
=
2
y
=
3
y
=
4
y
=
5
Relative deviation
26.7%
5.3%
2.7%
4.2%
8.1%Table 4
Schematic illustration of possible object shapes at a cell contact point.
Schema
Description
Case  1
The circular ringC
1 includes the cell region R
A
n that separates the background pixels in two separate sets B
1 and B
2 (Figure 5). The circular ring C
R includes two noncontiguous sets R
B
1 and R
B
2. To allow object separating, f
(
x
,
y
) has to return the value true for
R
B
1 and R
B
2 and the additional conditions 1 and 2 must be met.
Case  2
There are two separated cell regions withinC
1. For further processing only the cell area is selected which contains the center of C
1 in its point set. As a result of this processing, this case is case type 3 from now on.
Case  3
There is a separated cell area withinC
R which does not enter the region of C
1. This cell region will be ignored for further processing. As a result the case is type 1 from this point forward.
Case  4
C
R contains a separated cell area, which is connected to R
A
n, but not with other object areas. For all three subsets contained in R
B, it is checked whether f
(
x
,
y
) returns true and the conditions 1 and 2 are fulfilled. If at least two subsets remain in R
B which fulfill the above-mentioned criteria; the separation takes place at this point. All subsets in R
B, which do not satisfy the above-mentioned criteria, will be added as elements in R
B
D so that the cell regions separated in error can be reunited with the neighboring object.
Case  5
Compared to case  4, there are one or more separate cell areas located withinC
R, which are connected to R
A
n and other parts of R
C in this case. It is determined for all subsets in R
B whether f
(
x
,
y
) returns true and conditions 1 and 2 are met. If at least two subsets in R
B remain which fulfill the above-mentioned criteria, the separation takes place at this point. All subsets in R
B which do not satisfy the above-mentioned criteria are stored as elements in R
B
D similarly to Case  4 so that the cell regions separated in error can be reunited with the neighboring object.Iff
1
(
x
) returns the value true, the object separation is done with the assignment
(4)
R
C
′
=
R
C
∖
R
A
n
,
R
C
∶
=
R
C
′
.
The cell region R
C is overridden to prevent multiple separations of neighboring contour points. R
A
n is added as an element of the set R
A
_
Ges. The mentioned separation process is carried out at the n narrowing joints of the cluster.Applying the region labeling after the separation process of the cluster shown in Figure6 results in 3 cells R
S
1,   R
S
2, and R
S
3. In the context of the 3 separation processes R
A
1,  R
A
2, and R
A
3 are subtracted from R
C and the results are reassigned to R
C afterwards. The object regions stored in R
A
_
Ges are subsets of the original object region R
C
_
Copy and have to be assigned to the neighboring regions. For this purpose, each region R
A
n is separated into two regions using erosion. Each of the two separated regions is then assigned to the closest neighboring cell. Afterwards the assigned regions are enlarged to their original sizes using dilation. The dilation process stops if the two regions collide.Figure 6
The result of the cell separation process. Three new cellsR
S
1, R
S
2, and R
S
3 are created.There may be situations in which object separations do not make sense, for example, at contact points between cell extensions and cell body, even thoughf
1
(
x
) delivers true. For this reason, the decision function f
1
(
x
) has to be expanded for a cell separation. The experience shows that a division should be avoided if one of the two regions R
B
1 or R
B
2 (Figure 7) is y-times greater than the other region. As in the earlier cases, y is a parameter adjusted to the situation. In our case y
=
3 is chosen. If the parameter y is set too high, then cell extensions are partially separated from the cell. For the case that the value of y is set too small, the algorithm partially prevents the separation of connected cells (Table 3).Figure 7
Incorrect separation of a cell extension from its cell.The extended decision function isf
(
x
,
y
)
=
f
1
(
x
)
∧
f
2
(
y
) with
(5)
f
2
(
y
)
=
(
|
R
B
1
|
≤
y
·
|
R
B
2
|
)
∨
(
|
R
B
2
|
≤
y
·
|
R
B
1
|
)
.
Figure 7 illustrates the case |
R
B
2
|
>
3
|
R
B
1
|. Thus f
2
(
3
) = false and therefore f
(
1.5,3
) = false. A separation must not be carried out, because a cell extension which belongs to the cell was recognized. In some cases, the width of an elongated cell extension varies so much that f
(
1.5,3
) has the value true (Figure 8). Again, this is obviously an incorrect decision and must be prevented with additional optional conditions.Figure 8
Incorrect splitting of a cell extension.Condition 1.
All object regions inR
n, generated by the separation process, must have a minimum size A
min
⁡; otherwise they are not separated.Condition 2.
The compactness of all object regions inR
n must be K
≤
a up to a maximum object size A
max
⁡, with a
=
10 in our case.Generally in image processing the compactness is defined as(6)
K
=
(
L
2
4
A
·
π
)
.
L is the contour length of the object and A is the object surface. If an element of R
n has an area >A
max
⁡, it is a narrow elongated single cell and a separation is correct.Figure9 shows a simple flow-diagram of the CBS.Figure 9
Simple flow-diagram of separating objects at the narrow joints.The agglomerateR
C has n different narrowing joints R
A
1
,
R
A
2
,
…
,
R
A
n. These are processed sequentially in a loop with the CBS, shown with a thick border in Figure 9. The separation process of R
C results in r new object regions R
S
1
,
R
S
2
,
…
,
R
S
r from R
C, which are stored as elements of O
List. The mentioned procedure is valid for every segmented cluster. The detailed CBS algorithm is presented in the flow-diagram in Figure 10.Figure 10
Activity diagram of the CBS.Figure10 shows a decision-based structure of the algorithm, with which the possible geometric variations of the objects are processed.After calculation ofR
A
n
=
C
1
∩
R
C with subsequent region labeling R
A
n consists of k sets. For the case k
>
1, only the set is addressed, which includes the center of C
1. If R
A consists only of one set, the calculation of R
B
=
C
R
∩
R
C follows. R
B is region labeled, so l subsets R
B
1
,
R
B
2
,
…
,
R
B
l are created, which form a coherent set when combined with R
A
n. If l
=
2, the decision function f
(
x
,
y
) checks whether the two subsets R
B
1 and R
B
2 represent a join. In the case l
>
2 it is checked whether all subsets fulfill
(7)
(
|
R
B
p
|
≥
x
·
|
R
A
n
|
)
∧
(
|
R
B
p
|
≥
|
R
B
p
|
max
⁡
y
)
with
p
=
1
,
2
,
…
,
l
;
x
=
1.5
;
y
=
3
at which |
R
B
p
|
max
⁡ matches the biggest subset from {
R
B
1
,
R
B
2
,
…
,
R
B
l
}.IfR
B
1
,
R
B
2
,
…
,
R
B
l contain at least two sets, which fulfill the previously mentioned conditions, the separation process is initiated. If q sets exist in {
R
B
1
,
R
B
2
,
…
,
R
B
l
} which do not fulfill the conditions, they are added as elements in R
B
D, R
B
D
=
{
R
B
D
1
,
R
B
D
2
,
…
,
R
B
D
q
}. After the object separation, the undesirably separated object regions are determined with the help of the elements in R
B
D. A separated object region R
S
j with j
=
1
,
2
,
…
,
i is considered to be undesirable if R
U
j
,
t
=
R
S
j
∩
R
B
D
t (with t
=
1,2
,
…
,
q) results in |
R
U
j
,
t
|
>
0. An undesired object region R
S
j is assigned randomly to one of the remaining objects. In this way, an object separation can be done even in cases where several object regions come together but not all of them must be separated (Table 4, case  5). The possible cases that can occur in context of a separation process are listed in Table 4. Figure 11 is used as a legend for Table 4.(a) 2 cells; (b) two connected cells; (c) two connected cells where a left cells region extends intoC
1.
(a)
(b)
(c)(a) Cells of type L929. (b) Cell segmentation result before the separation process. Some cells are connected to each other. (c) Cell separation with the method described in [20]. The arrows indicate wrong separation results. (d) Cell separation with the CBS method. (e) Cell separation with the method described in [15]. The arrows indicate wrong separation results.
(a)
(b)
(c)
(d)
(e)The number of cell areas withinC
1 and C
R can vary but this was not considered in Table 4 for reasons of clarity. Mixed forms of the illustrated cases are also possible, although this would not cause a problem for the algorithm.


## 2.1. Cell Segmentation

The images were created by the Olympus XC10 camera, which is installed on an Olympus Bx51 M microscope with 100x magnification. The size of the images is1376
×
1032 pixel. The segmentation of the cell areas is carried out by a standard threshold procedure for all three color channels. The thresholds depend on the used staining method. In the case of the present May-Grünwald staining, the thresholds T
R
=
128, T
G
=
150, and T
B
=
150 are used. To determine suitable thresholds, ​
​an expert draws the contours of 20 different cells in the image. The same cells are also automatically segmented by using the default threshold values ​
​
T
R
=
T
G
=
T
B
=
128. With the help of the Jaccard coefficient, the similarity of the automatically generated cell areas compared to the reference areas can be measured. The automatic cell segmentation with subsequent calculation of the Jaccard coefficient is now iteratively performed with different threshold values. Finally the parameter set with the maximum Jaccard coefficient is used for cell segmentation. Due to a reliable staining process, the chosen parameters are robust for different images of one or more test samples.The resulting three binary imagesB
R, B
G, and B
B are then merged into one image B
Ges
=
B
R
∪
B
G
∪
B
B and a region labeling is performed. Only those segmented regions with a minimum area A
Min
⁡ which depends on the used cell type are further analyzed. To determine the minimum cell area for cells of type L929, the cells in 50 images were automatically segmented and had their respective cell areas calculated. Afterwards, a manual check by an expert was done to determine whether the segmented object is a cell or merely an artifact on the substrate surface. The smallest segmented cell was determined to have an area of C
MIN
=
276 pixel and the biggest segmented artifact was found to have an area of E
Max
⁡
=
102 pixel. A
Min
⁡ is defined as the average of the smallest cell area and the biggest artifact area:
(1)
A
Min
⁡
=
(
C
Min
⁡
+
E
Max
⁡
)
2
=
189
pixel
.
Finally small holes within the regions produced by the segmentation process are filled by the closing algorithm. The complete cell segmentation process is visualized in Figure 2.Figure 2
Cell segmentation process. The steps within the brackets are carried out for the cell region segmentation (Section2.1). The subsequent separation of clusters is described in Section 2.2.Figure2 shows the process of the presented method to segment the cell regions (Section 2.1) and then separating the clusters with help of the context-based separation method (Section 2.2).


## 2.2. Context-Based Separation

The new method presented in this paper is called the context-based separation (CBS). This method performs splitting operations on cells or other objects. This splitting is restricted to narrow joints between cells or objects. In an imagem clusters R
C
1
,
R
C
2
,
…
,
R
C
m are contained. Each cluster consists of several cells which have to be separated for further analysis. The approach of this method is shown by one cluster R
C. For purposes of clarity, R
C is defined as a representative of a cluster. Therefore, the cluster index can be ignored. This method is performed only at narrow joints R
A
n with n
=
1
,
2
,
…
,
x (Figure 5) where a separation process is carried out. For this purpose, the contour of the object R
C is sampled with a circular structural element C
1 with radius r
1 (Figure 3).Figure 3
The contour of the objectR
C is sampled by a circular structural element C
1.For eachnth (step width) contour point it is checked whether the background area B enclosed by C
1 consists of two separated subsets B
1 and B
2. B
1 and B
2 must be separated by the cell area enclosed by C
1 with R
A
n
=
C
1
∩
R
C (Figure 4). This is a necessary condition for a local joining of the object. A join is characterized by a dilatation at the ends. This is determined by creating a circular mask C
2 with radius r
2
=
a
•
r
1 which is generated concentrically around C
1. The parameter a is adjusted to this cell type. In our case a
=
2 is suitable. If values smaller than 1.5 are chosen, not all local joints are found. In contrast, if the value of a is set higher than 2.75, the circular mask gets much bigger than most of the local joints and the failure rate increases (Table 1).Table 1
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert is determined.
a
=
1.25
a
=
1.5
a
=
2.0
a
=
2.5
a
=
3.0
Relative deviation
8.6%
4.6%
2.7%
3.1%
5.4%Figure 4
The backgroundB within C
1 is separated by R
A in two subsets B
1 and B
2.Figure 5
With help ofC
1 and C
R it is checked whether a narrowing is present.With the help ofC
1 and C
2, the circular ring mask C
R is calculated with C
R
=
C
2
∖
C
1 and in the further course of the algorithm R
B
=
C
R
∩
R
C is determined (Figure 5). A join should be present when the decision function f
1
(
x
) assumes the value is true. For the case shown in Figure 5, where the point set R
B consists of 2 nonoverlapping or adjacent point sets R
B
1 and R
B
2, the decision function is defined as
(2)
f
1
(
x
)
=
(
|
R
B
1
|
≥
|
R
A
n
|
·
x
)
∧
(
|
R
B
2
|
≥
|
R
A
n
|
·
x
)
.
The set R
B can also comprise q nonoverlapping or adjacent sets of points (Table 4). The decision function f
1
(
x
) is then given by
(3)
f
1
(
x
)
=
(
|
R
B
1
|
≥
|
R
A
n
|
·
x
)
∧
(
|
R
B
2
|
≥
|
R
A
n
|
·
x
)
∧
⋯
(
|
R
B
q
|
≥
|
R
A
n
|
·
x
)
.
The symbol |
⋯
| denotes the number of pixels of a set. In our case the parameter x is set to x
=
1.5. If the chosen value of x is too high, some local joints are not found. On the other hand if the value of x is a too small, the algorithm provides too many local joints (Table 2).Table 2
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert.
x
=
1.25
x
=
1.5
x
=
2.0
x
=
2.5
x
=
3.0
Relative deviation
5.8%
2.7%
2.9%
3.8%
7.4%Table 3
Average relative deviation of the automatic cell count (2376 cells) to the reference cell count compiled by an expert.
y
=
1.5
y
=
2
y
=
3
y
=
4
y
=
5
Relative deviation
26.7%
5.3%
2.7%
4.2%
8.1%Table 4
Schematic illustration of possible object shapes at a cell contact point.
Schema
Description
Case  1
The circular ringC
1 includes the cell region R
A
n that separates the background pixels in two separate sets B
1 and B
2 (Figure 5). The circular ring C
R includes two noncontiguous sets R
B
1 and R
B
2. To allow object separating, f
(
x
,
y
) has to return the value true for
R
B
1 and R
B
2 and the additional conditions 1 and 2 must be met.
Case  2
There are two separated cell regions withinC
1. For further processing only the cell area is selected which contains the center of C
1 in its point set. As a result of this processing, this case is case type 3 from now on.
Case  3
There is a separated cell area withinC
R which does not enter the region of C
1. This cell region will be ignored for further processing. As a result the case is type 1 from this point forward.
Case  4
C
R contains a separated cell area, which is connected to R
A
n, but not with other object areas. For all three subsets contained in R
B, it is checked whether f
(
x
,
y
) returns true and the conditions 1 and 2 are fulfilled. If at least two subsets remain in R
B which fulfill the above-mentioned criteria; the separation takes place at this point. All subsets in R
B, which do not satisfy the above-mentioned criteria, will be added as elements in R
B
D so that the cell regions separated in error can be reunited with the neighboring object.
Case  5
Compared to case  4, there are one or more separate cell areas located withinC
R, which are connected to R
A
n and other parts of R
C in this case. It is determined for all subsets in R
B whether f
(
x
,
y
) returns true and conditions 1 and 2 are met. If at least two subsets in R
B remain which fulfill the above-mentioned criteria, the separation takes place at this point. All subsets in R
B which do not satisfy the above-mentioned criteria are stored as elements in R
B
D similarly to Case  4 so that the cell regions separated in error can be reunited with the neighboring object.Iff
1
(
x
) returns the value true, the object separation is done with the assignment
(4)
R
C
′
=
R
C
∖
R
A
n
,
R
C
∶
=
R
C
′
.
The cell region R
C is overridden to prevent multiple separations of neighboring contour points. R
A
n is added as an element of the set R
A
_
Ges. The mentioned separation process is carried out at the n narrowing joints of the cluster.Applying the region labeling after the separation process of the cluster shown in Figure6 results in 3 cells R
S
1,   R
S
2, and R
S
3. In the context of the 3 separation processes R
A
1,  R
A
2, and R
A
3 are subtracted from R
C and the results are reassigned to R
C afterwards. The object regions stored in R
A
_
Ges are subsets of the original object region R
C
_
Copy and have to be assigned to the neighboring regions. For this purpose, each region R
A
n is separated into two regions using erosion. Each of the two separated regions is then assigned to the closest neighboring cell. Afterwards the assigned regions are enlarged to their original sizes using dilation. The dilation process stops if the two regions collide.Figure 6
The result of the cell separation process. Three new cellsR
S
1, R
S
2, and R
S
3 are created.There may be situations in which object separations do not make sense, for example, at contact points between cell extensions and cell body, even thoughf
1
(
x
) delivers true. For this reason, the decision function f
1
(
x
) has to be expanded for a cell separation. The experience shows that a division should be avoided if one of the two regions R
B
1 or R
B
2 (Figure 7) is y-times greater than the other region. As in the earlier cases, y is a parameter adjusted to the situation. In our case y
=
3 is chosen. If the parameter y is set too high, then cell extensions are partially separated from the cell. For the case that the value of y is set too small, the algorithm partially prevents the separation of connected cells (Table 3).Figure 7
Incorrect separation of a cell extension from its cell.The extended decision function isf
(
x
,
y
)
=
f
1
(
x
)
∧
f
2
(
y
) with
(5)
f
2
(
y
)
=
(
|
R
B
1
|
≤
y
·
|
R
B
2
|
)
∨
(
|
R
B
2
|
≤
y
·
|
R
B
1
|
)
.
Figure 7 illustrates the case |
R
B
2
|
>
3
|
R
B
1
|. Thus f
2
(
3
) = false and therefore f
(
1.5,3
) = false. A separation must not be carried out, because a cell extension which belongs to the cell was recognized. In some cases, the width of an elongated cell extension varies so much that f
(
1.5,3
) has the value true (Figure 8). Again, this is obviously an incorrect decision and must be prevented with additional optional conditions.Figure 8
Incorrect splitting of a cell extension.Condition 1.
All object regions inR
n, generated by the separation process, must have a minimum size A
min
⁡; otherwise they are not separated.Condition 2.
The compactness of all object regions inR
n must be K
≤
a up to a maximum object size A
max
⁡, with a
=
10 in our case.Generally in image processing the compactness is defined as(6)
K
=
(
L
2
4
A
·
π
)
.
L is the contour length of the object and A is the object surface. If an element of R
n has an area >A
max
⁡, it is a narrow elongated single cell and a separation is correct.Figure9 shows a simple flow-diagram of the CBS.Figure 9
Simple flow-diagram of separating objects at the narrow joints.The agglomerateR
C has n different narrowing joints R
A
1
,
R
A
2
,
…
,
R
A
n. These are processed sequentially in a loop with the CBS, shown with a thick border in Figure 9. The separation process of R
C results in r new object regions R
S
1
,
R
S
2
,
…
,
R
S
r from R
C, which are stored as elements of O
List. The mentioned procedure is valid for every segmented cluster. The detailed CBS algorithm is presented in the flow-diagram in Figure 10.Figure 10
Activity diagram of the CBS.Figure10 shows a decision-based structure of the algorithm, with which the possible geometric variations of the objects are processed.After calculation ofR
A
n
=
C
1
∩
R
C with subsequent region labeling R
A
n consists of k sets. For the case k
>
1, only the set is addressed, which includes the center of C
1. If R
A consists only of one set, the calculation of R
B
=
C
R
∩
R
C follows. R
B is region labeled, so l subsets R
B
1
,
R
B
2
,
…
,
R
B
l are created, which form a coherent set when combined with R
A
n. If l
=
2, the decision function f
(
x
,
y
) checks whether the two subsets R
B
1 and R
B
2 represent a join. In the case l
>
2 it is checked whether all subsets fulfill
(7)
(
|
R
B
p
|
≥
x
·
|
R
A
n
|
)
∧
(
|
R
B
p
|
≥
|
R
B
p
|
max
⁡
y
)
with
p
=
1
,
2
,
…
,
l
;
x
=
1.5
;
y
=
3
at which |
R
B
p
|
max
⁡ matches the biggest subset from {
R
B
1
,
R
B
2
,
…
,
R
B
l
}.IfR
B
1
,
R
B
2
,
…
,
R
B
l contain at least two sets, which fulfill the previously mentioned conditions, the separation process is initiated. If q sets exist in {
R
B
1
,
R
B
2
,
…
,
R
B
l
} which do not fulfill the conditions, they are added as elements in R
B
D, R
B
D
=
{
R
B
D
1
,
R
B
D
2
,
…
,
R
B
D
q
}. After the object separation, the undesirably separated object regions are determined with the help of the elements in R
B
D. A separated object region R
S
j with j
=
1
,
2
,
…
,
i is considered to be undesirable if R
U
j
,
t
=
R
S
j
∩
R
B
D
t (with t
=
1,2
,
…
,
q) results in |
R
U
j
,
t
|
>
0. An undesired object region R
S
j is assigned randomly to one of the remaining objects. In this way, an object separation can be done even in cases where several object regions come together but not all of them must be separated (Table 4, case  5). The possible cases that can occur in context of a separation process are listed in Table 4. Figure 11 is used as a legend for Table 4.(a) 2 cells; (b) two connected cells; (c) two connected cells where a left cells region extends intoC
1.
(a)
(b)
(c)(a) Cells of type L929. (b) Cell segmentation result before the separation process. Some cells are connected to each other. (c) Cell separation with the method described in [20]. The arrows indicate wrong separation results. (d) Cell separation with the CBS method. (e) Cell separation with the method described in [15]. The arrows indicate wrong separation results.
(a)
(b)
(c)
(d)
(e)The number of cell areas withinC
1 and C
R can vary but this was not considered in Table 4 for reasons of clarity. Mixed forms of the illustrated cases are also possible, although this would not cause a problem for the algorithm.


## 3. Results and Discussion

In the context of biocompatibility testing of implant materials, the determination of the proliferation rate (cell count) and the evaluation of the cell morphology are important features. Therefore, an accurate determination of the cell borders within the clusters is necessary. The cytotoxicity of an implant material is classified in 4 levels depending on the proliferation rate (Table5).Table 5
Assignment of the cell proliferation rate to the four levels of cytotoxicity.
Cytotoxicity level
Proliferation rate (%)
Interpretation
0
100–81
Not cytotoxic
1
80–71
Low cytotoxicity
2
70–61
Moderate cytotoxicity
3
60–0
Strong cytotoxicityTable5 shows that the minimum classification interval of the proliferation rate is 10% (Low cytotoxicity (80%–71%) and Moderate cytotoxicity (70%–61%)). If the automated cell count was to deviate by more than 10% from the reference cell count, it would not be possible to reliably classify the cytotoxicity level of implant materials. Therefore, the automated counting of cells in the field of biocompatibility is only feasible if a counting accuracy of more than 95% is attainable.To evaluate the efficiency of the presented method, first the number of cells for 10 samples (2409 cells) of the cell type L929 on the substrates steel as well as titanium is determined and compared to the number of cells specified by an expert (reference cell count). The part of L929 cells which are connected to clusters is in average 23.3%. Table6 shows the cell counting for the method presented in this paper compared to two other separation methods [15, 20]. The algorithm in [20] is old but cell separation with the help of morphological operations is still a common procedure. The method introduced in [15] is based on the watershed transformation applied to the inverse distance transformation of the segmented cell areas. This is a state-of-the-art procedure to separate connected nuclei or cells in microscopic images.Table 6
Comparison of cell counting using the CBS and the methods presented in [20] and [15].
Sample
ACC
FP
FN
PC
REF
RFP (%)
RFP (%)
ERR (%)
CBS Algorithm
1
234
4
2
230
232
1.7
0.9
0.9
2
350
3
22
347
369
0.8
6.0
5.1
3
240
2
12
238
250
0.8
4.8
4.0
4
193
3
9
190
199
1.5
4.5
3.0
5
232
4
12
228
240
1.7
5.0
3.3
6
205
9
3
196
199
4.5
1.5
3.0
7
217
3
1
214
215
1.4
0.5
0.9
8
208
5
7
203
210
2.4
3.3
1.0
9
220
6
1
214
215
2.8
0.5
2.3
10
270
6
16
264
280
2.1
5.7
3.6
Ø Err
2.0
3.3
2.7
Method described in [20]
1
255
24
1
231
232
10.3
0.4
9.9
2
380
16
5
364
369
4.3
1.4
3.0
3
269
21
2
248
250
8.4
0.8
7.6
4
223
25
1
198
199
12.6
0.5
12.1
5
260
23
3
237
240
9.6
1.3
8.3
6
222
25
2
197
199
12.6
1.0
11.6
7
247
36
4
211
215
16.7
1.9
14.9
8
231
23
2
208
210
11.0
1.0
10.0
9
236
22
1
214
215
10.2
0.5
9.8
10
296
20
4
276
280
7.1
1.4
5.7
Ø Err
10.3
1.0
9.3
Method described in [15]
1
245
14
1
231
232
6.0
0.4
5.6
2
391
25
3
366
369
6.8
0.8
6.0
3
258
8
0
250
250
3.2
0.0
3.2
4
211
14
2
197
199
7.0
1.0
6.0
5
252
13
1
239
240
5.4
0.4
5.0
6
208
10
1
198
199
5.0
0.5
4.5
7
226
13
2
213
215
6.0
0.9
5.1
8
219
10
1
209
210
4.8
0.5
4.3
9
230
16
1
214
215
7.4
0.5
7.0
10
292
14
2
278
280
5.0
0.7
4.3
Ø Err
5.7
0.6
5.1
ACC: automatic cell count; FP: false positive detection; FN: false negative (missed) detection; PC: positive correct detection (ACC − FP); REF: reference cell count; RFP:  relative false positive detection (FP/REF * 100); RFN: relative false negative detection (FN/REF * 100); ERR: relative error (((REF − ACC)/REF) * 100).Separating the cells with the CBS method results in a mean cell count error of 2.7%. In comparison, using the methods described in [15, 20], an average cell count error of 9.3% and 5.1% results. Table 6 shows that the algorithms described in [15, 20] have a high false positive detection rate (10.3% and 5.7%). The main reason is that that these methods are not able to detect the cell extensions as part of the cell and therefore separate them incorrectly. On the other hand, these methods provide a very small false negative detection rate (1.0% and 0.6%) yet due to the high false positive detection rate the overall error is higher in comparison to the CBS algorithm. Thus, the method described in this paper is more suitable for the determination of the L929 cell number as the methods described in [15, 20]. Figure 12 shows the cell separation results for the investigated methods.The used algorithms described in [15, 20] lead to a partial splitting of one cell or cell extensions indicated by the arrows in Figures 12(c) and 12(e). However, these cell extensions are part of the cell and thus they are not allowed to be separated from the rest of the cell area.As mentioned the CBS can be used independently of other procedures or it can be combined with other methods, for example, the algorithm described in [16], to decrease the calculation time (Table 7) and to improve the cell count quality.Table 7
Comparison of calculation time for the separation algorithm described in [16] without CBS and with CBS on a 3.2 GHz Intel Core i7 CPU with parallel processing.
Sample
Calculation time Algorithm excluding CBS (s)
Calculation time Algorithm including CBS (s)
Speed-Up
1
12.4
1.9
6.53
2
5.8
2.1
2.76
3
4.4
0.9
4.89
4
11.8
1.9
6.21
5
2.1
0.6
3.50
6
4.1
1.1
3.73
7
1.1
0.4
2.75
8
2.0
0.5
4.00
9
6.2
0.5
12.40
10
15.1
0.4
37.75
Ø Speed-up
8.45By using the CBS a speed-up factor of about 8 may be achieved, compared to the cell count algorithm without the use of CBS (Table7). The calculation time is varying since the number of clusters is changing from image to image.In comparison, the method described in [9] results in 3.9% deviation from the reference cell count for leukocyte cells. In contrast to type L929, the leukocyte cells morphology does not vary so much. Therefore, it can be assumed that the deviation gets worse for cells with stronger varying morphology than the leucocyte cells.The evaluation of the cell morphology is an important aspect in the context of biocompatibility testing. Therefore, an accurate segmentation of the cell boundaries within the clusters is important in order to obtain a reliable result. To evaluate the methods precision concerning the cell area segmentation, 100 automatically segmented cell regions within clusters were compared with the cell regions evaluated manually by an expert. The Jaccard coefficient is a suitable method to determine the quality of the separation. If two objects are equal in shape and area, the Jaccard coefficient is 1. Table8 shows the Jaccard coefficient of the CBS and four other separation algorithms.Table 8
Calculated Jaccard coefficient based on 100 reference L929 cells within clusters for different cell separation procedures.
CBS
Method described in [16]
Method described in [20]
Method described in [15]
0.84
0.80
0.75
0.76Table8 shows a Jaccard Coefficent of 0.84 for the CBS. In comparison, the other methods [15, 16, 20] provide with 0.76, 0.75 and 0.8 poorer results.The methods [15, 20] partially split cellular extensions or even holes cells (Figures 12(c) and 12(e)). However, with the presented method and the algorithm introduced in [16], no cell extensions are separated and most cells are cut at reasonable places from a biological point of view. The method described in [16] is, in contrast to the CBS, not suitable for the separation of cells which are in a biological division process. Therefore, the Jaccard coefficient is slightly worse in comparison to the presented procedure.The required parameters for the decision functionf
(
x
,
y
) for the cell type L929 were adjusted experimentally. With f
(
1.5,3
), the smallest deviation of the automated cell count compared to the reference value is obtained. The cell-specific rules such as object size and compactness were set up specifically for this application and can, if necessary, be replaced by other rules without changing the method. In this case the method is used as a supplement to the existing separation algorithm [16] to reduce the calculation time and increase the accuracy of cell counting and cell area segmentation within the clusters. It is possible to apply the CBS to object joining situations independently of other algorithms. By doing so, the calculation time needed is milliseconds. The CBS algorithm can also be applied to other types of objects and is therefore suitable for other similar types of problems.


## 4. Conclusion

In this paper, a method for segmenting and separating cells in clusters is presented. The algorithm first segments histological stained cell regions in microscopic images with a standard threshold method applied to each color channel. The separation of connected cells at narrow joints is carried out by sampling the cluster contour with a circular structural element. Within the circular element, the cell geometry is analyzed and the result of a decision function indicates whether a local narrowing exists or not. An extension of the decision function with two exchangeable conditions avoids unwanted separation processes and improves the cell area segmentation. The method can be used to separate any segmented objects which have narrow joints at their contact areas. It has a very fast execution speed since not all contour points have to be processed. The procedure can be combined very well with other separation methods. This leads to better results and reduces the overall calculation time.



---

*Source: 542521-2014-03-20.xml*