7 MAR Project Allocated. 11 MAR Initial reading into the field of image processing and image segmentation. 14 MAR Browsed the net for the different segmentation techniques. Tested a few CBIR tools including Blobworld and GIFT. Blobworld appeared to be useful, but the server was down, so extensive testing was not completed. GIFT was hosted on David Squire's website. A basic image query search was performed, and the results and the time the system took to deliver the results were pleasing. 16 MAR First honours meeting. Refer to meeting summary. 20 MAR Read two image segmentation technical papers. The first paper "Unsupervised image segmentation using a simple MRF model with a new implementation scheme", discussed an improved model for image segmentation. The technique used appeared to be effective and efficient. This is a possible technique that could be used for this honours project. The second paper, "Differential Feature Distribution Maps for Image Segmentation and Region Queries in Image Databases" is related to the first paper, but it is more concise. 21 MAR Second honours meeting. Refer to meeting summary. 26 MAR Read the honours thesis paper written by Nadia Trojan on "Improved Feature Extraction for Textures and Differential Structures Specific to Dermatoscopic Images". Although the concepts and algorithms discussed proved to be worthwhile, the discussion of the results and findings in the paper was somewhat unclear. It could be due to my limited understanding of image processing, but the paper had many diagrams showing the results where the textual content surrounding it did not explain clearly what and how the images differ from each other. 27 MAR Read David Squire's notes on the K-means clustering technique. Downloaded and installed the ImageMagick api and software for linux. The c++ implementation of the image magick tool was chosen because it has a good set of documentation, and it was along the lines of the C programming language which was used by the GIFT software. 28 MAR Implemented the K-means clustering algorithm. The results were quite interesting. 29 MAR Extended the K-means clustering algorithm to work with 3D colour space. The program no longer requires the user to specify the dimensions of the image, but they need to specify whether the image given is rgb of g. An improvement made to the algorithm was the use of STL vectors over STL lists. STL lists does not have the constant time nth element access, but the vector container does. The algorithm still works fine for grayscale images, however, it is now running really slow for colour images. Depending on the random k values selected at the start, sometimes the program would just stall and produce nothing, or sometimes when the k values are good, the program would produce the results. Basically, the higher the k value, the longer it will take for the program to complete its job. The no. of colours in an image can affect this too. The problem I encountered was "how do we compare 3d colour pixels?", and "how do we find out which pixel is similar to another", and for sorting, "how is one pixel smaller or larger than the other?". I ended up subtracting the pixel component values from the other and scaling each component to get a unique distance value. Works fine for small k values. 30 MAR Tested the program again, it crashed or stalled on high cluster values. 31 MAR Realised that my k-means clustering program was picking the wrong values for the new cluster mean values. The program was picking the median instead of the mean of each cluster dataset. Honours Meeting #3 I figured out where I was making the mistake in my algorithm. Everytime when I'm calculating the new mean value for each cluster, I would skip the clusters that had no data values. By doing that, the cluster mean for that cluster would not change, but its value is mapped to another cluster's new data set range, therefore, the final image will end up having one colour only. I fixed the problem by resetting the empty dataset cluster mean value back to (0,0,0). 3 APR Started implementing the Mahalanobis Distance function for my K-means cluster algorithm. Studied the maths behind the distance function (vectors, matrices). An initial version was implemented with the ability to support 3 clusters. The function is buggy. 4 APR Honours Meeting #4 Started reading the PHD thesis paper on Image segmentation. Checked out the LAPACK API for maths related functions. The LAPACk maths API was written in Fortran, need to write a C++ wrapper for it. I didn't bother with it because I'm not familiar with the fortran programming language. Instead, I found another maths api called NewMat which was based on the Numerical Recipe maths algorithms. I spent the whole night restructuring my K-means program to use the new API. At around midnight, my new code compiled successfully, but the NewMat's matrix operations were really slow. 5 APR Continued debugging my K-means program. Found a proper manual 3x3 inverse matrix method, and implemented. It was really fast, however, my K-means program still fails for > 3 clusters. I found another bug too. The Mahalanobis distance function should return a positive value rather than both -ve or +ve. 6 APR Started debugging my code again. Realised that when calculating the Covariance matrix, it needs to be normalised to <= 1 so that it will work properly when the other cluster covariance matrix's are set to the identity matrix. The k-means program works for > 3 clusters now, however, due to the random selection of the cluster mean values when the new data set for a cluster is empty, the program will infinitely loop forever. Basically, the program will get to a state where two cluster sets will juggle the remaining unresolve data values. David said: "This shouldn't happen. It is theorectically possible, but it would require a very improbable point being exactly half-way between two clusters - to extremely high precision. Are you sure that this what is going on? Perhaps you could keep track of which points are changing labels at each iteration as a diagnostic, and see what is happening in the end in these situations (print out coordinates of the points, and distances to each cluster centre). " 7 APR I emailed my current progress to David, and he was confused why I was scaling the covariance matrix values. I sent him an example: Okay, here's an example from one of my tests: Cluster 1: Cluster centre: [0.4 0.2 1.0] Covariance matrix of the cluster set, [C1] | 0.108 0.093 0.075 | | 0.093 0.082 0.068 | | 0.075 0.068 0.057 | [C1]' (inverse): | 619.371 -1104.063 489.005 | | -1104.063 2368.270 -1342.971 | | 489.005 -1342.971 958.481 | Cluster 2: This cluster has just been re-initialised and its centre is also at [0.4 0.2 1.0]. Its covariance matrix becomes the identity matrix [C2] | 1 0 0 | | 0 1 0 | | 0 0 1 | [C2]' (inverse) : same result Using Mahalanobis distance to find the distance between the current point CP = |0.5 | |0.16| |0.5 | and the cluster centres. Matrix D1 = abs_value([CP] - [C1 Centre]) Matrix D2 = abs_value([CP] - [C2 Centre]) Cluster 1: [D1]^T[C1]'[D1] = [340.421] Cluster 2: [D2]^T[C2]'[D2] = [0.3716] As you can see, the difference between the two values is far too big, and the cluster distance between the CP and C1 is not even between 0.0 and 1.0. Since cluster 2 uses the identity matrix as its covariance matrix, in the next iteration of the k-means algorithm, most of the data values from cluster set 1 will move to cluster set 2, because the distance values from cluster1 is far too big. As a result of this, cluster 1's data set may become zero again, so its covariance matrix will be reset to the identity matrix...and the same process above will be repeated. If cluster 1's inverse matrix was divided by the largest value in the inverse matrix, 2368.270, then the new C1 matrix would look like | 0.261 -0.466 0.206 | | -0.466 1.00 -0.567 | | 0.206 -0.567 0.405 | and [D1]^T[new C1][D1] = [0.144] The new cluster 1's inverse matrix produces a better distance between the two vectors (0.0->1.0). I also told him that imagemagick reads pixel values as 0.0-1.0, so that is part of the reason why the covariance matrix values are so big. David agreed with my explanation, and suggested that I should reset a data cluster's covariance matrix to the previous one if its new data set is empty. I tried it, but my program still loops forever. He also suggested me to use the CLAPACK maths API instead of the fortran version. David's reply: "You are right the the problem is one of scale - but I think it is the use of the identity matrix for the single point cluster that is the problem. When a covariance matrix is diagonal (as is the identity), each diagonal element is the variance in that direction. Using the identity implies a variance of 1 in each direction, and zero covariance between directions (the off-diagonal elements). Since the maximum difference between points in this data representation is 1, the variance (average squared distance from the mean) has to be less than one. In fact, it's likely to be less that 0.25 (i.e. 0.5^2). A better starting point would be the covariance matrix for the whole data set. You could calculate this once at the start, and then reuse it whenever you need to restart a cluster. I think this should work. " READ * IMAGE SEGMENTATION THESIS * Citations: an and D. Geman. Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images - Gem (ResearchIndex) * http://www.dam.brown.edu/people/geman/index.shtml * Read ColourFAQ * Install CLAPACK 10 APR Spent a few hours researching and compiling the CLAPACK library. It all installs fine, but when you try to compile your own source programs, the compiler will come up with a lot of undefined references to function calls. 11 APR Honours Meeting No.5 Read the GammaFAQ. Half way through the ColourFAQ ( Page 14 ) David suggested: Hi Ji, Here are those questions that I referred to. When writing a research proposal/thesis/paper, you need to address: - What's the problem we're trying to solve? - How do we propose to solve it? - How have others addressed this or similar problems? - How is our approach different? - How will we test it? - What were the results? - What do they mean? - Did it work, how could we move on from here? You need to convey to the reviewer/examiner that you: - are addressing a real and interesting problem - are someone worth listening to - have an interesting solution Cheers, David Implemented the changes required for the K-means program. Q.) It could be used as a benchmark to compare the effectiveness of the proposed project's results with last year's honours project which used the Fast ICA approach to filter/segment dermascology images? "No. Last year's project was about feature extraction. We will compare against Phillipe Schmid's work - and perhaps others. We will have to think about that." "You need to read up on this. See the Schmid thesis." >This could possibly be useful for segmenting >dermascology images where scattered fragments of a skin lesion can be >grouped together. > > Ermmm. No. This is not the sort of problem it addresses. The problem is that points distant from the cluster centre contribute equally to it's centroid location as those close to the centre. This makes it vulnerable to outliers. The fuzzy approach basically says: if this point is unlikely to have been generated by this cluster, then it should not have a great influence on it. 12 APR CLAPACK is finally installed and linked properly to my source code. 14 APR - 15 APR Wrote the draft research proposal. Documents consulted: 1. Bulent Erkol, Randy H. Moss, R. Joe Stanley, William V. Stoecker and Erik Hvatum, Automatic lesion boundary detection in dermoscopy images using gradient vector flow snakes. 2. Guillod Joel, SchmidSaugeon Philippe, Guggisberg David, Cerottini Jean Philippe, Braun Ralph, Krischer Joakim, Saurat JeanHilaire and Kunt Murat, Validation of segmentation techniques for digital dermoscopy. 3. StarSoft Inc., Clustering Analysis, http://www.statsoft.com/textbook/stcluan.html. 21 APR 05 Hi Ji, Sorry I missed you. I hope to be well enough to get to work tomorrow, but I still don't feel good. I could meet you at 4:00pm at Caulfield. I'll let you know if I'm there. BTW, I've heard back from my Swiss collaborators, and we will be able to work on the dermo images. I think you topic could be stated as something like "Lesion segmentation in dermatological images using colour, texture and Markov random fields". We can pitch it as an attempt to improve on Phillipe Schmid's work via the use of MRFs. Regards, David 22 - 23 APR Research Proposal revised. 26 - 30 APR Honours Meeting #6. Updated the research proposal. 2 MAY Honours Meeting #7. Updated the research proposal. 9 MAY Honours Meeting #8. Started the Project Priorities form. 12 MAY Finalised the project priorities form. 15 MAY Read an article: Colour Space Conversions Adrian Ford (ajoec1@wmin.ac.uk ) and Alan Roberts (Alan.Roberts@rd.bbc.co.uk). Summary: It is a comprehensive guide for colour space conversion. A bit difficult to read and understand though. 16 MAY Data Clustering: A Review by A.K. JAIN, M.N. MURTY, and P.J. FLYNN Summary: This is a very good review on the existing clustering methods. It has raised a lot of important points regarding the K-means algorithm. Some of these ideas will be used in my research project implementation. 20 MAY Read an article: Color- and Texture-Based Image Segmentation Using EM and Its Application to Content-Based Image Retrieval Serge Belongie, Chad Carson, Hayit Greenspan, and Jitendra Malik Summary: Talks about a technique to merge the colour descriptors and the texture descriptors using the EM algorithm (with gaussians). This technique is used in the "BlobWorld" CBIR tool. Honours Meeting #9 21 MAY Modified the K-means algorithm program to prevent infinite loops. The maximum iterations is now Clusters (K) * 100. Read an article: k*-means - A Generalized k-means Clustering Algorithm with Unknown Cluster Number Yiu-ming Cheung Summary: An alternative K-means clustering algorithm that takes into account the hyper-ellipsoid clustering (using covariance properties) and uses an automatic cluster number detection algorith to find the optimal number of Ks (an elimination technique). 22 MAY Articles Read: Content-based query of image databases, inspirations from text retrieval: inverted files, frequency-based weights and relevance feedback. David McG. Squire, Wolfgang Muller, Henning Muller, Jilali Raki Summary: Describes the fundamental properties of an image such as its colour, texture, and shape. It introduces the concept of inverted files that stores all possible feature of an image and the images that uses the listed features. These inverted files can improve the CBIR similarity matching process. Towards a computer-aided diagnosis system for pigmented skin lesions Philippe Schmid-Saugeona, Joel Guillodb, Jean-Philippe Thirana. Summary: Discusses the subjective and limited accuracy of the dermatologists when it comes to drawing borders around lesion regions of a dermatological image. It mainly talks about the fuzzy c-means, orientation sensitive fuzzy c-means, and the isotropic diffusion and morphic segmentation technique; and shows how dapplying colour, texture, and shape symmetry maps after image segmentation can improve the separation of Benign and Malignant melanoma lesions. Validation of segmentation techniques for digital dermoscopy Guillod Joel, Schmid-Saugeon Philippe, Guggisberg David, Cerottini Jean Philippe, Braun Ralph, Krischer Joakim, Saurat Jean-Hilaire and Kunt Murat Summary: Discusses the problems of border drawings by the dermatologist experts. Their subjective view of skin lesions are not very consistent. Automatic lesion boundary detection in dermoscopy images using gradient vector flow snakes Bulent Erkol1, Randy H. Moss2, R. Joe Stanley2, William V. Stoecker3 and Erik Hvatum4 Summary: Discusses a border detection method for use in dermatological images. The featured method is called Gradient Vector Flow Snakes where it draws an initial border around a greyscale image and uses the snake like properties to derform the border so that it will conform to the lesion shape. As promising as it sounds, it is still not accurate due the initial blurring of the image to reduce noise since the blurring will remove the weak edges of an image. It also has a higher error rate compared to the manual borders drawn on the lesion images by the dermatology experts. 23 MAY Honours Meeting No. 10 Read: Lecture Note Topics: Expectation-Maximisation (EM) algorithm Vector Quantisation Gaussian Mixture Models Clustering by: Ludwig Schwardt Colour and Texture GZ Yang and DF Gillies 24 MAY Read the Fourier Transform maths notations from the MathWorld website. I understood what the purpose of FTs are but I don't understand the maths behind it all. I implemented the distortion factor for the K-means clustering. If the new centroid values don't differ much from the old centroid value, then the new centroid is considered stable. The distortion factor is 10^-10. Read: A new approach for measuring the validity of the fuzzy c-means algorithm George E. Tsekourasa, Haralambos Sarimveisb Summary: Describes the Fuzzy C-means algorithm and introduces a mathematic concept to validate the clusters generated by the fuzzy c-means algorithm. 25 MAY Read: Hidden Markov Models notes by: Ludwig Schwardt 27-28 MAY Read: Hidden Markov Models http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html Summary: This is an excellent introduction to hidden markov models. It explains and gives examples of how they work and how they can be applied to realistic simulation models. The main algorithms introduced are the Forward, Viberti, and the Forward-Backward model. These are good for evaluation, decoding, and learning respectively. 29 MAY Read: Texture features and Learning Similarity W.Y.Ma and B.S.Manjunath Summary: Discusses the use of Gabor wavelet based texture features together with a hybrid neural network algorithm for learning data from data clusters. The research has shown that the Gabor texture feature can successfully find similar images using an image query via CBIR tools. 31 May - 2 June Read: Clustering-based Colour Image Segmentation Clustering-based Colour Image Segmentation using Inter-cluster distance Determination of Number of Clusters in K-Means Clustering and Application in Colour Image Segmentation Clustering-based Colour Image Segmentation: An evaluation study An application of Clustering in Colour Image Segmentation A new approach to clustering-based colour image segmentation K-means Clustering for Colour Image Segmentation with Automatic detection of K by Sid Ray and Rose H. Turi Summary: Discussion of clustering using the K-means and the fuzzy c-means technique. Introduces the techniques for determining the number of clusters in an image. These automatic cluster determination techniques can be used with the previously mentioned clustering techniques to make the whole process seem automated. 3 June Read: Visualisation of Cluster Changes by Comparing Self-organising Maps by: Denny and David McG. Squire Summary: Discusses the use of SOMs in the field of clustering. It provides a clear and structural way of presenting the changes of clusters in a data set. 4 June Read: Content-Based Image Retrieval at the End of the Early Years by: Arnold W.M. Smeulders, Marcel Worring, Simone Santini, Amarnath Gupta, and Ramesh Jain. Summary: Summarises the main techniques used in CBIR tools such as user interaction, user feedback, similarity measures, data classification, colour and texture pre-processing techniques, shape analysis, image indexes and databases, and image semantics via segmentation. It also discusses the future of CBIR tools and which aspects of it will be exploited in the future. Read: A Tutorial on Clustering Algorithms (Kmeans, Cmeans, Heirarchical, EM) http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/ Summary: A simple and easy to understand tutorial on clustering. 5-6 June: Started the lit review. 13 June Read: ON THE COLOR IMAGE SEGMENTATION ALGORITHM BASED ON THE THRESHOLDING AND THE FUZZY c-MEANS TECHNIQUES Summary: Discusses the various ways researchers have combined the FCM technique with other classification techniques. One of the main technique uses course segmentation by manipulating the histogram of an image by applying a scale-space filter (smooth, first and second derivative) to determine the number of valid classes and threshold values. At this stage, it assigns pixel to the valid classes. Using the data gathered in the course segmentation process, a fine segmentation is performed using the FCM algorithm. This basically assigns all the pixels that have not been assign to anything from the course stage to the most similar class. This process leads to a reduced computational effort. 14 June Honours Meeting #12 Worked on the Literature Review. Read: A Review of Content-Based Image Retrieval Systems in Medical Applications - Clinical Benefits and Future Directions by Henning Muller, Nicolas Michoux, David Bandon and Antoine Geissbuhler Summary: Reviews the current CBIR systems and the techniques used by the systems in the medical domain. It outlines the future directions for the development of CBIR systems, the strengths and weaknesses of the current systems, the importance of CBIR systems in the medical domain, and how these systems can be used for the other fields such as the teaching department. Read: A multiple classifier system for early melanoma diagnosis by Andrea Sboner, Claudio Eccer, Enrico Blanzieri, Paolo Bauer, Mario Cristofolini, Giuseppe Zumiani, Stefano Forti Summary: Describes a dermatology system that uses multiple classifiers to determine whether a skin lesion is a melanoma or a benign lesion. The three different kinds of classifiers used are the linear discriminant analysis (LDA), k-nearest neighbour (k-NN) and a decision tree. Groups of classifiers were also used to classify segmented skin lesions. The statistical measures they used were the specificity and the sensitivity of the image classes. These statistical values were compared with the different classifier's results and against the results produced by the dermatologist experts. The experiment has shown that the combination of the three classifiers were more accurate that the results produced by the dermatologists. 19 June Read: DullRazor: A software approach to hair removal from images Summary: DullRazor is a software utility for preprocessing an image that consists of hairs. It examines the closiness of the hair structure and produces and merges a fixed size masks for each colour component (RGB) to filter out hair from an image. A predefined threshold value is used to determine the hair pixels. Pixel values that lie on a hair are filled up with its neighbouring pixels after the filtering stage. The preprocessing step improves the segmentation process of an image. Read: Blobworld: A System for Region-Based Image Indexing and Retrieval Summary: This content based system uses a tree indexing system to classify images. Images are segmented into objects, blobs (regions) including the colour and texture descriptors which provide a faster and more accurate method for searching similar images compared to the coventional full image similarity criterion. Read: Blobworld: Image Segmentation Using Expectation-Maximization and Its Application to Image Querying Summary: Gives a more detailed discussion of the algorithms and technique used in the Blobworld CBIR system. 20 June Read: A Markov Random Field Image Segmentation Model Using Combined Color and Texture Features Summary: An old MRF segmentation method that uses a combination of CIE-L*u*v* colour features and Gabor filters as texture features to segment colour images. The fundamental model relies on Bayesian estimation associated with combinatorial optimisation to maximise the segments/classes labeled by the use of MRF and multivariate Gaussian distributions. Read: Markov Random Field Models for Unsupervised Segmentation of Textured Color Images Summary: Segmentation of colour images using colour texture and MRF to approximate the maximum liklihood for spatial relationships between texture. The textures found are used in the segmentation stage to determine the region of an image. The segmentation stage involes the use of region splitting/merging. 21 June Honours Meeting No.13 Compiled a list of ideas for each literature review chapter heading. 25-26 June Re-wrote/structured the K-means clustering C++ classes. Researched the Lapack matrix operations. Found that the matrix multiplication method it provides is quite slow. Started coding the Fuzzy Cmeans algorithm. 27-28 Completed the Fuzzy Cmeans C++ implementation. The results generated by this kmenas variant are quite good.