Synthetic 3D Pap smear nucleus generation

IT 10 217 Examensarbete 15 hp May 2010 Synthetic 3D Pap smear nucleus generation Sandra Gómez Institutionen för informationsteknologi Department of Information Technology ! Teknisknaturvetenskaplig fakultet UTH-enheten Besöksadress: Ångströmlaboratoriet Lägerhyddsvägen 1 Hus 4, Plan 0 Postadress: Box 536 751 21 Uppsala Telefon: 018 – 471 30 03 Telefax: 018 – 471 30 00 Hemsida: http://www.teknat.uu.se/student Abstract Synthetic 3D Pap smear nucleus generation Sandra Gomez In this project we present a 3D Pap smear cell nucleus generator. The shape and the texture are the important features for a realistic synthetic nucleus. For the first one, the shape, a deformed distance transform is used in order to generate deformed spheres. For the second one, the texture, a pseudorandom noise algorithm, Perlin noise, is applied to the shape in order to generate the most realistic texture of a cell. As a result, we obtain synthetic 3D cell nuclei as they appear in Pap smear tests. Tryckt av: Reprocentralen ITC IT 10 021 Examinator: Anders Jansson Ämnesgranskare: Patrik Malm Handledare: Patrik Malm ! 3 Contents 1!Introduction .................................................................................................................................................4! 2!Background..................................................................................................................................................5! 2.1!Preliminary concepts ......................................................................................................................................... 5! 2.1.1!Uniform distribution ............................................................................................................. 5! 2.1.2!Fourier series........................................................................................................................ 5! 2.1.3!Hermite cubic splines............................................................................................................ 6! 2.2!Shape generation................................................................................................................................................. 6! 2.2.1!Parametric model.................................................................................................................. 6! 2.2.2!Layered approach ................................................................................................................. 7! 2.2.3!Distance based model ........................................................................................................... 8! 2.3!Binarization.......................................................................................................................................................... 9! 2.3.1!Bresenham algorithm............................................................................................................ 9! 2.3.2!MidPoint algorithm............................................................................................................. 10! 2.3.3!Seed fill algorithm............................................................................................................... 10! 2.3.4!Scan-line algorithm............................................................................................................. 11! 2.4!Texture generation ............................................................................................................................................12! 2.4.1!Perlin noise ......................................................................................................................... 12! 2.5!Real nuclei images ............................................................................................................................................13! 3!Material and methods............................................................................................................................. 15! 3.1!Development platform.....................................................................................................................................15! 3.2!Shape generation...............................................................................................................................................15! 3.3!Texture generation ............................................................................................................................................15! 3.4!Visualization ......................................................................................................................................................15! 4!Results ........................................................................................................................................................ 17! 4.1!Shape generation method................................................................................................................................17! 4.2!Texture generation method .............................................................................................................................18! 4.3!Final images .......................................................................................................................................................19! 5!Discussion .................................................................................................................................................. 20! 5.1!Shape generation...............................................................................................................................................20! 5.2!Texture generation ............................................................................................................................................21! 6!Acknowledgements.................................................................................................................................. 22! 7!References.................................................................................................................................................. 23! 4 1 INTRODUCTION Computer graphics have many different applications, not only for entertainment, videogames, animation and films but also in the scientific community. Computer graphics is used for data visualization and simulation, which makes analysis of the data easier. Another field is data simulation or synthetic data generation which can be very useful for developing and validating algorithms. While medical image simulation software has been under development since the 1980s, until recently the complexity of the procedures and long computation times have limited the realism and accuracy of artificially generated images. Improvements in computational systems have facilitated simulations that were previously infeasible. Advancements in processor architecture, increases in speed and amount of memory, and development of large storage systems have enabled computers to be used for increasingly complex problems. The use of distributed systems and technologies provide unparalleled computational capabilities [10]. When developing algorithms, one of the most difficult tasks is to know the ground truth of the data. The acquisition of ground truth is a laborious task that usually requires the assistance of several experts and a good amount of time. In addition, this process is often very subjective and different experts may have different views on what could be considered a correct result. The goal of synthetic data generation is to solve this problem. Using synthetic data the ground truth is known a priori. Synthetic data can be created in large numbers, in a short time, with suitable variation of the model parameters, making it possible to draw statistically sound conclusions regarding the relative performance of different methods. Currently, cancer is a big problem in the population. One of the most common cancers, is the cervical cancer which is the second most deadly cancer among women. The Papanicolau test (also called PAP-smear) is a screening test used in gynecology to detect premalignant and malignant (cancerous) processes in the ectocervix. Using a spatula or a brush the area known as the transformation zone of the uterin cervix is scraped in order to obtain endocervical and ectocervical cells. The collected material is then smeared onto a glass slide. The sample is then fixated and stained to enhance the contrast between nucleus and cytoplasm [11,12]. The goal of this project is to mimic cells as they appear in Pap smear. There are many previous studies in two-dimensional synthetic cell image generation, e. g. [1, 2, 3]. They follow the same general process: generate the shape of the cell, then apply different noise algorithms and create a realistic image with a population of cells. This project is an extension of [1] in three dimensions. A three-dimensional model of the nuclei can give us a more realistic representation since the depth in the synthetic image becomes more natural. 5 2 BACKGROUND 2.1 Preliminary concepts 2.1.1 Uniform distribution In probability theory and statistics, the continuous uniform distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution’s support are equally probable [13]. The support is defined by the two parameters, a and b, which are its minimum and maximum values, as seen in Figure 1. The distribution is often abbreviated U(a,b). Fig. 1. Probability density function of the continuous uniform distribution. 2.1.2 Fourier series A Fourier series is an expansion of a periodic function f(x) in terms of an infinite sum of sines and cosines. Fourier series make use of the orthogonality relationships of the sine and cosine functions. The computation and study of Fourier series is known as harmonic analysis and is extremely useful as a way to break up an arbitrary periodic function into a set of simple terms that can be plugged in, solved individually, and then recombined to obtain the solution to the original problem or an approximation to it to whatever accuracy is desired or practical [14]. Using the method for a generalized Fourier series [21], the usual Fourier series involving sines and cosines is obtained by taking f1(x)=cos(x) and f2(x)=sin(x). Since these functions form a complete orthogonal system over [-π, π], the Fourier series of a function is given by: (1) 6 where (2) (3) (4) and n=1,2,3,…Note that the coefficient of the constant term a0 has been written in a special form compared to the form for a generalized Fourier series in order to preserve symmetry with the definitions an and bn. 2.1.3 Hermite cubic splines In the mathematical subfield of numerical analysis, a Hermite spline is a third-degree spline curve where each polynomial of the spline is in Hermite form. The Hermite form consists of two control points and two control tangents for each polynomial [20]. On the unit interval (0,1), given a starting point p0 at t=0 and an ending point p1 with starting tangent m0 at t=0 and ending tangent m1 at t=1, the polynomial can be defined by: (5) where t ∈ [0,1]. 2.2 Shape generation There are several methods to generate spherical shapes. Here three approaches of them are described: parametric model, layered approach and distance based model. 2.2.1 Parametric model The parametric model is the basic representation of a sphere: it calculates the Cartesian coordinates from the spherical coordinates theta (θ) and phi (φ). Figure 2 shows the correspondence with these coordinates and the sphere. 7 Fig. 2. Spherical coordinates of a sphere. The parameterized equation of a sphere, in which the parameters x0, y0, z0 are the center points of the sphere, is given by: (6) (7) (8) where (9) 2.2.2 Layered approach This approximation consists in build a sphere from layers of two-dimensional circles, as seen in Figure 3. It is important to realize that the circles have to be placed equally separate along the size of the radius. To calculate this increment between the circles, the initial point is necessary. Equations 10 and 11 show how to calculate the initial point and the height increment. (10) (11) Once the initial position and the height increment are known, the circles can be generated. 14 Fig. 10. Three examples of different real Pap smear cells. The image 1) shows a nucleus with few internal blobs; 2) shows another nucleus with a different shape, a darker contrast and some internal blobs, and 3) shows several nucleus: a) shows different shapes of the nucleus and b) shows another nucleus with littler blobs. 15 3 MATERIAL AND METHODS 3.1 Development platform This project has been developed using the MATLAB r2009b programming environment and the DIPimage toolbox. 3.2 Shape generation In the previous work on cell generation in two dimensions [1, 2, 3], a cell nucleus is modelled from a basic circle, due to its roundish form. Then, in accordance with this representation, a cell nucleus can be modelled as a sphere in three dimensions. For selecting the appropriate shape method generation, we considered several features. First of all, the method must be able to be parameterized; it means that it can be modified with different parameters values. These parameters allow us to deform the sphere for generating the desired shape. This shape must be continuous and uniform, so the type of the deformation is very important in the model. Furthermore, the method cannot be slow; the generation must be fast in order to obtain synthetic images faster than real images. The point is to avoid slow algorithms for the shape generation, and in this case, these are the binarization algorithms. 3D rasterization algorithms are too slow because they have to fill the volume inside, and it requires many loops. Therefore, the binarization method is critical for the shape generation. 3.3 Texture generation When using an algorithm to generate the texture of the nucleus, it has to be considered the runtime of the algorithm. The computational cost is the critical feature of the texture generation and likeness with real images. 3.4 Visualization For the visualization of the results we used three different methods: the MATLAB command surf and two MATLAB modules for 3D plotting, plot3D and vol3d [22]. An example of each method is shown in Figures 11, 12 and 13, respectively. 16 Fig. 11. An example of using the command surf. Fig. 12. An example of using the command plot3D. Fig. 13. An example of using the command vol3d. 17 4 RESULTS The synthetic image generation presented in this project is a sequential process: first creating a plane model with the desired shape and then adding the features that make it realistic. This method can be divided in two sub processes: shape generation and texture generation, as the flowchart shows in Figure 14. Fig. 14. Flowchart describing the simulation process. 4.1 Shape generation method From the several representation models of a sphere, we used the distance based model (see section 2.2.3), based on the low computational cost, and because it avoids all the problems with the binarization algorithms. Since the sphere can be seen as circles, the deformation can be applied to these circles, forgetting about the third dimension. Therefore, according to the method for creating variance on the shape of a circle in [1], we also used Fourier series to deform the basic form of a circle. As the sphere was not in the parametric model (see section 2.2.1), the results of the Fourier series had been applied in a look-up table, referenced by the angle ϕ of the sphere (from 1 to 360), as seen in Figure 2, hence the deformation was equally applied along the sphere. Figure 15 presents the final shape with the deformation applied to each circle of the sphere. 18 Fig. 15. Representation of deformed spheres using the distance transform model. At the right, the binary 3D model, and at the left the deformation in 2D applied to each circle of the sphere. 4.2 Texture generation method According to the previous work on synthetic Pap smear cells [1], we used the same well-known texture algorithm but in three dimensions: Perlin noise (see section 2.4). In the first place, in order to generate the base model, a Perlin noise smoothed function was applied on each point (x,y,z) of the matrix as follows: (16) where n controls how much the texture smoothes and noise(x,y,z) is the Perlin noise generation function. Figure 16 shows some examples of the variation produced in the texture by changing the value n in the smoothing function. Fig. 16. Different nuclei textures applying a) the noise function without smoothing, b) the smoothed noise function (Eq. 17) where n=4, c) the smoothed noise function where n=6, and d) the smoothed noise function where n=10. Once the textured base model was generated, the chromatin blobs were added to this texture. The position of these blobs was chosen randomly and their shapes generated in the same way. Figure 17 shows few examples of the base texture with the added blobs. 19 Fig. 17. Some examples of textured nuclei with different sizes of the chromatin blobs: (from left to right) size 6x8, size 4x4 and size 3x3. 4.3 Final images As a result of the generation process, we obtain different nuclei models by changing some parameters. Figure 18 shows these final images and some slices of them so we can compare the synthetic images with the real ones. Fig. 18. Final images of synthetic nuclei. At the left, 2D slices from the 3D volume, at the right, the volume rendered with a 50x50x50 resolution: a) radius 25, number of blobs 100 and size of the blobs 7x6, b) radius 36, number of blobs 150 and size of the blobs 5x5, and c) radius 35, number of blobs 100 and size of the blobs 5x5. Fig. 19. Image of a real cell nucleus. 20 5 DISCUSSION 5.1 Shape generation The shape generation process depends on the representation model for the sphere chosen. At the beginning of the project and attending to the previous work in 2D synthetic image generation [1,2, 3], the parametric model was chosen (see section 2.2.1). With this model, the deformation of the sphere was only applying a variation to the radius of the sphere, but it did not produce the expected result, as seen in Figure 20. This modification in the radius was not continuous and made abrupt changes in the sphere model. Fig. 20. Representation of a deformed sphere using the parametric model. Furthermore, the binarization (or rasterization) (see section 2.3) process from this model has a high computational cost. Raster conversion algorithms as Bresenham or MidPoint algorithm work well on images but on volumes, they do not generate a full model, they just convert the boundaries. So, in order to obtain a full volume, a seed fill algorithm (see section 2.3.3) has to be used, and this is what increases the computational cost. There are another algorithms with a low computational cost, for instance, Scan-line algorithm, but due to the problem with the shape and the binarization cost, this model representation was discarded. The next representation model studied was the layered approach (see section 2.2.2). This model, as seen in Figure 3, generated a new problem: create a volume from the layered sphere. This problem was complicated to solve and we found the distance based model, which seemed better for our project. So, this model was also discarded. Finally, we found the solution for all the problems seen above: the distance based model (see section 2.2.3). This model avoids the problem with the binary conversion because, as seen in 2.2.3, just applying a threshold generates the binary matrix. Another problem solved was the variation of the shape, using Fourier series (see section 2.1.2) to generate the desired shape of the sphere in two dimensions. This shape was the perturbation applied to the sphere to deform it. Figure 15 presents two examples of the final shape model and the 2D model generated for deform the sphere. 21 5.2 Texture generation In the texture generation process, Perlin noise function was chosen from the beginning to simulate the nucleus texture, because it is a well-known algorithm for generating textures. As said before, Equation 16 is used to smooth the noise in order to obtain a better approximation to the real nuclei texture. Figure 16 shows four examples of the application of this smoothing function with different settings. As seen, the noise function without smoothing seems very random and not realistic. The last step on the process is to add the chromatin blobs to the textured model. The size and the amount of blobs can be controlled. Figure 17 shows a few examples of the model with different blob sizes. Finally, several images of the final result, the synthetic cell nucleus, are showed in Figure 18. In order to show how the chromatin blobs are distributed into the nucleus, we show some twodimensional slices of the model. Therefore we can compare these images with a real nucleus as seen in Figure 19 and observe the similarity between them. As a future work, the model can be improved by adding different aberrations to the model, adding more realistic features that can help to develop more kind of algorithms. The application can be improved as well by using another algorithms with less computational cost to obtain a faster generator In addition, it could have more parameters to modify in order to generate more variable models 22 6 ACKNOWLEDEGMENTS I am really grateful for the cooperation and interest of Patrik Malm, supervisor of the project. Without his collaboration and his help this project would not be possible. Thanks also to the CBA department from the Uppsala Universitet for providing me a place to work and to help Patrik and me to solve some problems of the project. 23 7 REFERENCES [1] P. Malm, A. Brun and E. Bengtsson, “PAPSYNTH: Simulated bright-field images of cervical smears”. [2] A. Lehmussola, P. Ruusuvuori, J. Selinummi, H. Huttunen, and O. Yli-Harja, “Computational framework for simulating fluorescence microscope images with cell populations”, IEEE Transactions on Medical Imaging, vol. 26, no. 7 pp. 1010-1016, Jul 2007. [3] A. Lehmussola, J. Selinummi, P. Ruusuvuori, A. Niemisto, and O. Yli-Harja, “Simuating fluorescent microscope images of cell populations”, in Proceedings of the 27th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, Piscataway, NJ, USA, 2005. [4] A. Huisman, L. S. Ploeger, H. F. J. Dullens, N. Poulin, W. E. Grizzle and P. J. van Diest, “Development of 3D chromatin texture analysis using confocal laser scanning microscopy”, Cellular Oncology, vol. 27, pp. 335-345, 2005. [5] K. Perlin, “An image synthetizer”, in SIGGRAPH’85: Proceedings of the 12th annual conference on Computer graphics and interactive techniques, New York, NY, USA, Jul 1985, vol. 19, pp. 287-296. [6] K. Perlin, “Improving noise”, In Proceedings of SIGGRAPH 2002, Ed Computer Graphics Proceedings, Annual Conference Series, ACM, 2002, 681–682. [7] K. Perlin, “Making noise”, http://www.noisemachine.com/talk1/, 2000. [8] A. Lagae, S. Lefebvre, R. Cook, T. DeRose, G. Drettakis, D. S. Ebert, J. P. Lewis, K. Perlin and M. Zwicker, “State of the art in procedural noise functions”, in Eurographics STAR program 2010, 2010. [9] D. S. Ebert, F. K. Musgrave, D. Peachey, K. Perlin, and S. Worley, “Texturing & modeling, a procedural approach”, Second Edition, pp. 64-80, July 1998. [10] http://www.cis.rit.edu/research/ultrasound/projects/generationSyntheticMedicalImages.html [11] H.K. Grohs and O.A.N. Husain, Eds., Automated Cervical Cancer Screening, Igaku-Shoin Medical Publishers, Inc., 1994. [12] WHO, Comprehensive cervical cancer control: A guide to essential practice, WHO Press, 2006. [13] http://en.wikipedia.org/wiki/Uniform_distribution_(continuous) [14] http://mathworld.wolfram.com/FourierSeries.html [15] http://sabia.tic.udc.es/gc/teoria/pto_medio_lineas/Inicio.html [16] http://en.wikipedia.org/wiki/Bresenham's_line_algorithm [17] http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html [18] A. Weitzenfeld, “Gráfica: Línea”, http://www.docstoc.com/docs/273281/Graficos-Lineas-Circulos, pp. 7-10. [19] L. Feng, and S. H. Soon, “An effective 3D seed fill algorithm”, Computers and graphics, vol. 22, issue 5, pp. 641-644, Oct, 1998. [20] http://en.wikipedia.org/wiki/Cubic_Hermite_spline [21] http://mathworld.wolfram.com/GeneralizedFourierSeries.html [22] http://www.mathworks.com/matlabcentral/fileexchange/4927-vol3d-m-vol3dtool-m [23] http://en.wikipedia.org/wiki/Rasterisation