Research of Segmentation Algorithms for Overlapping Chromosomes

doi:10.4236/eng.2013.510B082

Paper Menu >>

Journal Menu >>

Engineering, 2013, 5, 404-408

http://dx.doi.org/10.4236/eng.2013.510B082 Published Online October 2013 (http://www.scirp.org/journal/eng)

Research of Segmentation Algorithm s for Overlapping

Chromosomes*

Wenzhong Yan, Lei Bai

Department of Computer, North China Institute of Science and Technology, Beijing, China

Email: [email protected]

Received 2013

ABSTRACT

Chromosome segmentation is the most important step in the automatic chromosome analysis system. Since in almost

every metaphase image partial touching and overlapping of chromosomes are a common phenomenon, how to separate

these chromosomes correctly is a difficult yet vital problem. A number of attempts have been made to deal with this

problem. This paper is focused on these attempts. Some algorithms are investigated. The principle and the realization of

these algorithms are analyzed. Results of these algorithms are compared and discussed.

Keywords: Chromosome; Segmentation; Overlapping; M-FISH

1. Introduction

Human chromosome analysis is an essential task in cy-

togenetics, especially in prenatal screening and genetic

syndrome diagnosis, cancer pathology research and en-

vironmentally induced mutagen dosimetry [1]. A com-

puter-assisted system usually includes four processing

steps: 1) image enhancement, 2) chromosome segmenta-

tion (detection) and alignment, 3) feature computation

and selection and 4) chromosome classification [2]. In

these steps, chromosome segmentation is the most im-

portant one because this step affects the performance of

these systems.

Since in almost every metaphase image partial touch-

ing and overlapping of chromosomes are a common phe-

nomenon (Figure 1 shows an example of overlapping

chromosomes), finding solutions for automated separa-

tion of overlapping chromosomes is difficult yet vital.

Early studies found that a number of automated classifi-

cation systems were somewhat successful in karyotyping

the chromosomes under favorable imaging conditions.

The typical case error rate was approximately 20% [3]. If

the chromosomes were touching, overlapping or deformed,

the classification error rate was substantially increased

[4].

In order to solve the problems above, a number of at-

tempts have been made to deal with segmentation of

overlapping chromosomes. This paper is focused on these

attempts. Some segmentation algorithms are investigated.

The principle and the realization of these algorithms are

analyzed. Results of these algorithms are compared and

discussed.

2. Segmentation Algorithms

A novel recursive searching algorithm was developed

and implemented in an automated karyotyping system

(AKS). The goal of this system is to label the chromo-

somes from a metaphase image with minimal human

intervention. It is unique in that it is designed to auto-

matically process cells containing overlapping chromo-

some. It also has four novel algorithmic features: the use

of cross section sequence graphs, an over-segmentation-

based segmentation strategy, the use of the “pale path”

concept for banded chromosomes and the application of

mathematical programming for cell-level chromosome

classification in cells with overlapping chromosomes.

The algorithm was tested using 29 cells (including 397

chromosomes) and achieved 82% accuracy. Three types

of skeleton errors were found, which were missing frag-

ments in the skeleton, extr a -fragments in the skeleton and

hole information [5].

Figure 1. Example of overlapping chromosomes.

This research is sup ported by the Funda mental Research Fund s for the

Central Universities (2011A010).

W. Z. YAN, L. BAI

405

A new technique to separate overlapping chromosomes

based on computational geometry is developed. This

technique requires the identification of all possible cut

points from the contour line of overlapping chromosomes,

using Voronoi diagrams and Delaunay triangulations to

select the four target cut points and cut overlapping

chromosomes into two chromosomes. This algorithm is

tested on 35 overlapping chromosome images and find

that 28 out of 35 overlapping chromosomes images can

be separated correctly (i.e. 80.0%).Three out of the 35

images are separated incorrectly (i.e. 8.6%) and four out

of 35 images are not separable by our algorithm (i.e.

11.4%). Figure 2 shows some results of the separation

[6].

One research presented an algorithm that is able to

automatically identify chromosomes in metaphase im-

ages. Researchers take care of a first segmentation step

and then of the disentanglement of chromosome clusters

by resolving separately adjacencies and overlaps with a

greedy approach, which ensures that at each step only the

best split of a blob is performed. The performance of this

method is better or comparable to the best of other me-

thods reported in the literature. This method to simulta-

neously tackle segmentation, overlaps and adjacencies

with performance on each task higher than 90%, hence

providing a tool able to automatically analyze an image

and can be handed over wit minimal human intervention

to a classifier for automatic karyotyping [7].

Another research is aimed at designing a classifier that

its input is an image and its output is decision of being

(a) (b)

Figuer 2. Separation overlapping chromosome images. (a)

Original image of two overlapping chromosomes; (b) a

Bounded Voronoi diagram of possible cut points; (c) chro-

mosome 1; and (d) chromosome 2.

mul ti-chromosome or one-chromosome image. Since the

gray-scale level of image has no effect on decision of

human, researchers convert the images to binary. The

output of classifier has two conditions that can be showed

with one bit. Therefore, if the classifier output is “zero”,

the image is one-chromosome and if it is “one”, the im-

age is multi-chromosome image. If one wants to use a

classifier except neural network classifier, he should de-

fine a procedure for feature extraction. But if one uses

neural network classifier, he doesn’t need to define fea-

tures for neural network. When a neural network is learn-

ing, in fact it learns the features. In this condition, deci-

sion space is divided in two regions. Decision boundary

is specified during learning process. The best experiment

result is obtained in second simulation with 73% true

separation. Figure 3 shows that the best result is 73%

and obtained with 8, 16, 20 and 23 neurons in hidden

layer. The specifications of this neural network are: mul-

ti-layer feedforward perceptron (MLP) neural network

with one hidden layer that has 9 neurons in input layer, 8

neurons in hidden layer and one neuron in input layer.

Input vector of neural network includes: surface of image,

surface of chromosome, number of pixels of boundary of

chromosomes, and six momentums [8].

One group proposed a novel approach to image com-

pletion for overlapping chromosomes. In their system,

only given missing regions, the task can be performed

automatically without human intervention. They address

the problem of image completion for overlapping chro-

mosomes in the context of a discrete global optimization

problem. In order to reconstruct the original chromosome

image as faithfully as possible, the objective cost func-

tion of this problem is defined under constraint condi-

tions of band patterns in chromosomes image, and cor-

Figure 3. The results of neural network simulation with 9

features at input. Horizontal axis is the number of neurons

in hidden layer and vertical axis represnts the average per-

centage of true classification.

W. Z. YAN, L. BAI

406

responds to the energy of a discrete Markov random

fields. For efficiently optimizing this MRF, a loopy Be-

lief Propagation algorithm is utilized to perform it. By

using an efficient optimization algorithm, this approach

integrates the high-level knowledge of chromosomes im-

age into image completion process to yield good results

in comparison to conventional methods. Moreover, this

approach can automatically perform without human in-

tervention. Figure 4 shows some results obtained by this

approach to image completion for overlapping chromo-

somes [9].

3. Algorithms for M-FISH

1) Basic Theory

In the mid-1990s, a new technique for staining chro-

mosomes was introduced. It produced an image in which

each chromosome type appeared as a distinct color [10].

This multispectral staining technique is called multiplex

fluorescence in-situ hybridization, or MFISH, which

made analysis of chromosome images easier, not only for

visual inspection of the images by humans, but also for

computer analysis of the images. M-FISH uses five color

dyes that attach to various chromosomes differently to

produce a multispectral image, and a sixth dye that at-

taches to all chromosomes to produce a grayscale image.

(a) (b) (c)

Figure 4. Some results of image completion for overlapping

chromosomes. (a) Images of overlapping chromosomes; (b)

Background chromosome with occluded regions (in green)

after segmentation process; (c) Image completion based on

the approac h.

Thus, it is possible to envision new and improved me-

thods for the location, segmentation and classification of

chromosome images by exploiting the color information

in M-FISH images.

2) Segmentation Algorithms

One study introduces entropy as a criterion for select-

ing cut lines to decompose groups of chromosomes that

touch and overlap each other. This algorithm uses mul-

ti-spectral information in chromosome images for more

accurate segmentation. They locate the chromosome ma-

terial of a sixth dye, DAPI (4,6-diamidino-2-phenylin-

dole nucleic acid stain), which binds to all chromosomes,

and then find the connected components. Next, they label

every connected component as a separate object and cal-

culate its entropy. If its entropy is above a given thre-

shold, then they examine that object for possible cut lines.

They consider only points whose cut line was contained

within the chromosome clusters and had an 8-connected

neighbor whose class differed from theirs. Candidate cut

lines are made by straight line s between all combination s

of candidate cut points. Once all entropy-reducing divi-

sions are made, they recombine objects that may have

been labeled as separate objects due to overlap. Experi-

ment results show that this algorithm is able to decom-

pose clusters of touching and overlapping chromosomes

[11].

An ML method to segment and classify M-FISH chro-

moso me s i ma ge s using multispectr al data was introduced.

This method is developed for automatic chromosome

identification by exploiting the multispectral information

in M-FISH chromosome images and by jointly perform-

ing chromosome segmentation and classification. Re-

searchers develop a maximum-likelihood hypothesis test

that uses multispectral information, together with con-

ventional criteria, to select the best segmentation possi-

bility. Then this likelihood function is used to combine

chromosome segmentation and classification into a ro-

bust chromosome identification system. Experiment re-

sults show that the proposed likelihood function can also

be used as a reliable indicator of errors in segmentation,

errors in classification, and chromosome anomalies, which

can be indicators of radiation damage, cancer, and a wide

variety of inherited diseases. Figure 5 shows that one

single flagged segment can correct a whole cluster [12].

A new decomposition method for overlapping and

touching M-FISH chromosomes is also presented. To

overcome the limited success of previous decomposition

methods that use partial information about a chromosome

cluster, researchers have incorporated more knowledge

about the clusters into a maximum-likelihood frame work.

A cluster was better decomposed by incorporating more

knowledge. Multiple hypotheses were formed based on

color and the geometry defined by the basic elements of

W. Z. YAN, L. BAI

407

a cluster, and then evaluated based on the pixel classifi-

cation results and chromosome sizes. A hypothesis that

has a maximum-likelihood is chosen as the best decom-

position of a given cluster. About 90% of accuracy was

obtained for two or three chromosome clusters, which

consist about 95% of all clusters with two or more chro-

mosomes, and 100% accuracy was obtained for clusters

with a single chromosome. Figure 6 shows some seg-

mentation results [13].

4. Conclusion

Since in almost every metaphase image partial touching

and overlapping of chromosomes are a common phenol-

menon, finding solutions for automated separation of over-

lapped chromosomes is difficult yet vital. In this paper,

some segmentation algorithms for overlapped chromo-

somes are investigated. The principle and the realization

of these algorithms are analyzed. Results of these algo-

rithms are compare d and discus s ed.

(a) (b) (c)

Figure 5. Singl e flagged segment can correct a whole cluster.

(a) M-FISH cluster; (b) Incorrect segmentation and classi-

fication; (c) Correct segmentation and classification.

Figure 6. Segmentation results.

REFERENCES

[1] C. Lundsteen and J. Piper, “Automation of Cytogenetics,”

Springer-Verlag, Berlin, 1989.

http://dx.doi.org/10.1007/978-3-642-74738-0

[2] J. Liang, “Intelligent Splitting in the Chromosome Do-

main,” Pattern Recognition, Vol. 22, No. 5, 1989, pp.

519-532.

http://dx.doi.org/10.1016/0031-3203(89)90021-6

[3] G. Agam and I. Dinstein, “Geometric Separation of Par-

tially Overlapping Nonrigid Objects Applied to Automatic

Chromosome Classification,” IEEE Transactions on Pat-

tern Analysis and Machine Intelligence, Vol. 19, No. 11,

1997, pp. 1212-1222.

http://dx.doi.org/10.1109/34.632981

[4] X. W. Wang, B. Zheng, M. Wood, et al., “Development

and Evaluation of Automated Systems for Detection and

Classification of Handed Chromosomes: Current Status

and Future Perspectives,” Journal of Physics D: Applied

Physics, Vol.38, No.15, 2005, pp. 2536-2542.

http://dx.doi.org/10.1088/0022-3727/38/15/003

[5] M. Popescu, et al., “Automatic Karyotyping of Meta-

phase Cells with Overlapping Chromosomes,” Computers

in Biology and Medicine, Vol.29, 1999, pp. 61-82.

http://dx.doi.org/10.1016/S0010-4825(98)00040-7

[6] S. Wacharapong, J. Krisanadej and J. Mullica, “Segmen-

tation of Overlapping Chromosome Images Using Com-

putational Geometry,” Walailak Journal of Science and

Technology, Vol. 2, No. 3, 2006, pp. 181-194.

[7] E. Grisan, E. Poletti, et al., “Automatic Segmentation of

Chromosomes in Q-Band Images,” Proceedings of the

29th Annual International Conference of the IEEE EMBS,

2007, pp. 5513-5516.

[8] Y. Rahimi, R. Amirfattahi and R. Ghaderi, “Design of a

Neural Network Classifier for Separation of Images with

One Chromosome from Images with Several Chromo-

somes,” 3rd International Conference on Broadband

Communicaitons, Information Technology & Biomedical

Applications, 2008, pp. 186-190.

[9] X. Z. Zhou, Y. Lu and Z. Y. Yan, “Image Completion for

Overlapping Chromosomes,” 2008 IEEE Pacific-Asia

Workshop on Computational Intelligence and Industrial

Application, 2008, pp. 413-417.

http://dx.doi.org/10.1109/PACIIA.2008.271

[10] M. R. Speicher, S. G. Ballard and D. C. Ward, “Karyo-

typing Human Chromosomes by Combinatorial Multi-

Fluor FISH,” Nature Genetics, Vol. 12, 1996, pp. 368-

375. http://dx.doi.org/10.1038/ng0496-368

[11] W. Schwartzkopf, B. L. Evans and A. C. Bovik, “Mini-

mum Entropy Segmentation Applied to Multi-Spectral

Chromosome Images,” 2001 International Conference on

Image Processing, 2001, pp. 865-868.

[12] C. S. Wade, C. B. Alan and L. E. Brian, “Maximum-

Likelihood Techniques for Joint Segmentation-Classifi-

cation of Multispectral Chromosome Images,” IEEE

Transaction on Medical Imaging, Vol. 24, No. 12, 2005,

pp. 1593-1610.

http://dx.doi.org/10.1109/TMI.2005.859207

[13] H. Choi, A. C. Bovik and K. R. Castleman, “Maximum-

W. Z. YAN, L. BAI

408

Likelihood Decomposition of Overlapping and Touching

M-FISH Chromosomes Using Geometry, Size and Color

Information,” Proceedings of the 28th IEEE EMBS An-

nual International Conference, 2006, pp. 3130-3133.