Segmentation of Overlapping Chromosome Images  Using Computational Geometry

Wacharapong SRISANG; Krisanadej JAROENSUTASINEE; Mullica JAROENSUTASINEE

Authors

Wacharapong SRISANG CX-KURUE & Computational Science Graduate Program, School of Science, Walailak University, Nakhon Si Thammarat 80161
Krisanadej JAROENSUTASINEE CX-KURUE & Computational Science Graduate Program, School of Science, Walailak University, Nakhon Si Thammarat 80161
Mullica JAROENSUTASINEE CX-KURUE & Computational Science Graduate Program, School of Science, Walailak University, Nakhon Si Thammarat 80161

Keywords:

Image segmentation, chromosome analysis, overlapping chromosomes, computational geometry

Abstract

Current systems for automatic chromosome classification are interactive and require human intervention for correct separation between touching and overlapping chromosomes. Special separation methods are required to segregate chromosomes because they are non-rigid objects. This study develops a new technique to separate overlapping chromosomes based on computational geometry. 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. We test our algorithm 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 separate incorrectly (i.e. 8.6 %) and four out of 35 images are not separable by our algorithm (i.e. 11.4 %).

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References

A Carothers and J Piper. Computer-aided classification of human chromosomes: A review. Statist. Computing 1994; 4, 161-71.

B Lerner. Toward a completely automatic neural-network-based human chromosome analysis. IEEE Trans. Syst. Man Cybern. B: Cybern. 1998; 28, 544-52.

FCA Groen, TK Kate, AWM Smeulders and IT Young. Human chromosome classification based on local band descriptors. Patt. Recog. Lett. 1989; 9, 211-22.

J Piper, E Granum, D Rutovitz and H Ruttledge. Automation of chromosome analysis. Sig. Proc. 1980; 2, 203-21.

M Moradi and SK Setarehdan. New features for automatic classification of human chromosomes: A feasibility study. Patt. Recog. Lett. 2006; 27, 19-28.

J Liang. Intelligent splitting in the chromosome domain. Patt. Recog. 1989a; 22, 519-32.

J Liang. Decomposition of overlapping chromosomes. In: C Lundsteen and J Piper (ed). Automation of Cytogenetics, Springer, Berlin, 1989b, p. 177-90.

J Liang. Fully automatic chromosome segmentation. Cytometry 1994; 17, 196-208.

G Agam and I Dinstein. Geometric separation of partially overlapping nonrigid objects applied to automatic chromosome classification. IEEE Trans. Patt. Anal. Mach. Intell. 1997; 19, 1212-22.

B Lerner, H Guterman and I Dinstein. A classification-driven partially occluded object segmentation (CPOOS) method with application to chromosome analysis. IEEE Trans. Sig. Proc. 1998; 46, 2841-47.

M Popescu, P Gader, J Keller, C Klein, J Stanley and C Caldwell. Automatic karyotyping of metaphase cells with overlapping chromosomes. Comp. Biol. Med. 1999; 29, 61-82.

GC Charters and J Graham. Trainable grey level models for disentangling overlapping chromosomes. Patt. Recog. 1999; 32, 1335-49.

GC Charters and J Graham. J. Disentangling chromosome overlaps by combining trainable shape models with classification evidence. IEEE Trans. Sig. Proc. 2002; 50, 2080-85.

R Ogniewicz and M Ilg. Voronoi skeletons: Theory and applications. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Illinois. 1992, p. 63-9.

M Styner, G Gerig, J Lieberman, D Jones and D Weinberger. Statistical shape analysis of neuroanatomical structures based on medial models. Med. Image Anal. 2003; 7, 207-20.

CM Boesse, MK Henry, TW Hyde and LS Matthews. Digital imaging and analysis of dusty plasmas. Adv. Space Res. 2004; 34, 2374-78.

PK Sahoo, S Soltani and AKC Wong. A survey of thresholding techniques. Comp. Vis. Graph. Image Proc. 1988; 41, 233-60.

RM Haralick and LG Shapiro. Computer and Robot Vision, Vol. I, Addison-Wesley, Reading, MA, 1992, p. 1-608.

N Otsu. A threshold selection method from gray-level histograms. IEEE Trans. Syst. Man Cybern. 1979; 9, 62-6.

S Wolfram. The Mathematica Book, 5th ed., Book News, Oregon, 2004, p. 1-1200.

H Freeman and LS Davis. A Corner Finding Algorithm for Chain Coded Curves. IEEE Trans. Comp. 1977; 26, 297-303.

T Pavlidis. Algorithms for Shape Analysis of Contours and Waveforms. IEEE Trans. Patt. Anal. Mach. Intell. 1980; 2, 301-12.

A Rosenfeld and AC Kak. Digital Picture Processing. Academic Press, California, 1982, p. 1-349.

W Srisang, K Jaroensutasinee and M Jaroensutasinee. Segmentation of overlapping chromosome images. In: Abstracts of the 30th Congress on Science and Technology of Thailand, Bangkok, Thailand. 2004, p. 40.