PROJECT Presentation Medical multimodal Image retrieval
By - Vijayender Singh 105483657
12/11/09
Topic we will cover Why medical industry IRMA Methods of System Categorization Image train labels Bag of words model Pyramid kernel Spatial pyramid scheme SFIT Clustering K means clustering Support Vector Machine
12/11/09
Motivations Huge data base. The IRMA code for unique classification of medical images. Beneficial in necessary times. New topic and Future prospects is good. Part of my master project Topic related to image processing Challenging subject Will be helpful many fields
12/11/09
Why Medical Industry Consist of huge database Needs for content-based image retrieval in medical applications New and challenging field The IRMA code for unique classification of medical images. Research oriented topic Still lot of topics to explore
12/11/09
IRMA Methods of System Categorization First of seven successive analyzing steps extracting content information from medical images. Aims to establish intelligent processing strategies Current image under investigation used in strategies. Valid relations between code and sub-code elements Code must be strictly hierarchical in order to support semantic queries on a database.
12/11/09
Causality is important for grouping of processing strategies. Mono-hierarchical scheme is required Each sub-code element is connected to only one code element. Medical images must cover all aspects Influencing the image content and structure Multi-axial scheme was designed. Presented previously in German
12/11/09
Technical code of IRMA
The IRMA coding system consists of four axes with three to four positions "0" denotes "unspecified" to determine the end of a path along an axis: ◦ ◦ ◦ ◦
T (technical): image modality D (directional): body orientation A (anatomical): body region examined B (biological): biological system examined
Short and unambiguous notation (IRMA: TTTT – DDD – AAA – BBB) T, D, A, and B denotes a coding or sub-coding digit of the technical, directional, anatomical, and biological axis Notation avoids mixtures of one- and two-literal code positions.
12/11/09
Image Train Labels
Needs for content-based image retrieval in medical applications. coding scheme is required to describe
◦ a) the imaging modality including technical parameters. ◦ b) the orientation of the image with respect to the body. ◦ c) the body region examined. ◦ d) the biological system investigated.
Worked on the Body region examined.
12/11/09
Problem To extract the features using spatial pyramid. Multi resolution histograms of local features. Visual Dictionary. IRMA technical code and system categorization. Create new category for body region examined. Support Vector Machine.
12/11/09
Approach used Multi resolution histograms of local features. Spatial pyramid. K means Algorithm. Visual Dictionary. Support Vector machine.
12/11/09
Introduction Image is collection of order less features. Incapable of capturing shape or of segmenting an object from its background. Bag features method. Kernel based recognition method. Repeatedly sub dividing the image. Compute histogram of local features. Global method for object recognition. Identify overall scene. Categorizing images as containing objects.
12/11/09
Previous Work Computing Histograms for image description Mutliresolution histograms Resolutions stays fixed Paper used a Opposite approach Fixing the resolution at which features are computed Varying the spatial resolution at which features are aggregated Preserves more information Kernel used for appropriate geometric matching
12/11/09
Bag of words Model Used for texture recognition Text is represented as an unordered collection of words. Disregards the grammar. Don’t follow the word order ie a good book = good book a.
12/11/09
Representation based on the bag of words model Text can be represented by Ex Harry loves to play soccer. Sam loves to play rugby. Manchester united is a soccer club. Above example can be represented in a dictionary . Dictionary = {1”Harry”, 2 ”loves”, 3 ”to”, 4 ”play”, 5 ”soccer”, 6”Sam”, 7”rugby” , 8”Manchester”, 9”united”, 10”is”, 11”a”, 12”soccer”, 13”club”} Here we have 13 dictionary words.
12/11/09
Representation Based On The Bag Of Words Model contd Using the indexes of the dictionary, each document is represented by a 13-entry vector [1, 2, 2, 2,1,1, 1,0, 0, 0, 0, 0, 0, 0,] [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,] Each entry of the vectors refers to count
12/11/09
Bag of Features Model Same idea of the bag of words model applied in computer vision. Image treated as a document. Represent images collection of order less local features. Features extracted from the image and treated as a word. Works well for image classification.
12/11/09
Outline of Bag of Feature Model Extract features. Create visual vocabulary. Quantize features using visual vocabulary . Represent images by frequencies of visual words.
12/11/09
Spatial Pyramid Matching Kernel based recognition method. Efficient scene recognition in the large datasets. It involves repeatedly sub dividing the images. Compute histogram. Histogram are compared using weighted histogram intersection.
12/11/09
Works by placing the sequence of increasingly coarser grids over the feature space. Two point said to matched if they fall into the same grid
12/11/09
Pyramid Match kernel Pyramid Match Kernels. build pyramid in feature space. discard spatial information X, Y are the two sets of vectors . HlX and HlY denotes the histogram of X and Y. HlX (i) and HlY (i) denotes the number of points from X and Y into the ith cell grid.
12/11/09
Histogram intersection function I(HlX, HlY) Eq : D l l Il = I(Hl , Hl ) = X Y i=1 ∑ min (H X (i) and H Y (i)) . Matches found in level l also found in l+1 level So new matches found at level l will be Il – Il-1 for l = 0…. l-1
12/11/09
Spatial Matching Scheme Perpendicular approach build pyramid in image space quantize feature space Use of traditional clustering technique Calculate all feature vectors into M types Final equation l (X , Y ) Kl (X, Y) = M∑ K m=1 m m
12/11/09
Spatial Matching Scheme contd
12/11/09
Feature Extraction
Two types used ◦ Strong features ◦ Weak features
Features are extracted using SFIT descriptor K Means clustering of random patches Visual vocabulary from training data set
12/11/09
SIFT (Scale Invariant Feature Transformation)
Algorithm in computer vision. Publish by David Lowe in 1999. Widely used in object recognition. Detect and describe local features. Key points are extracted from the image and stored in the data base. Description extracted from the training image can be used on the test image and find the matching features based on the Euclidean distance of the feature vectors. Image size of 500 * 500 pixels can generate about 2000 stable features
12/11/09
Key Point In SIFT Scale Invariant Feature Detection
Transformation of an image into collection of feature vectors Each vector is invariant to image translation, scaling and rotation Key location are defined by the maxima and minima of the difference of Gaussian function Low contrast points and edge response points are rejected Remaining key points are more stable for matching and recognition
12/11/09
Four Stages Of The Algorithm
Scale Space Peak Selection
Key Point Localization
Orientation Assignment
Key Point Descriptor
12/11/09
Scale Space Peak Selection Potential interest points are identified by scanning the image over location. Implemented by constructing a Gaussian pyramid search for local peaks or key points. Done by using difference of Gaussian function.
12/11/09
Key Point Localization Determine location and scale Selection based on stability Unstable key points rejected
12/11/09
Orientation Assignment Identifies the dominant orientation of the each keypoint. Based on local image path. Enable the SIFT to create a canonical view for the keypoint .
12/11/09
Key Point Descriptor Builds the representation of each key points. Based on the pixels in its local neighborhood Significance level of local shape distortion and change in the illumination.
12/11/09
Clustering What is cluster. process of organizing objects into groups who are similar in some way. Two types of clustering 1) Distance based clustering. 2) Conceptual clustering.
12/11/09
Distance Based Clustering
Two or more object belong to the same cluster if they are close according to their geometrical distance Ex below we have 4 clusters
12/11/09
Conceptual Based Clustering Objects are grouped according to their fit to descriptive concepts not according to simple similarity measures. Example
12/11/09
Clustering Algorithm Classification
Classify into four groups Exclusive Clustering ◦ data are grouped in the excusive way so that each cluster to be distinct.
Overlapping Clustering ◦ Data associated with a proper membership value. ◦ uses fuzzy sets to cluster data so that each point may belong to two or more cluster with different degree of membership.
Hierarchical Clustering ◦ Based on union between two nearest cluster.
Probabilistic Clustering ◦ It uses the probabilistic approach.
12/11/09
Clustering Applications
Marketing - finding groups of customers with similar behavior given a large database of customer data containing their properties and past buying records Biology - classification of plants and animals given their features Libraries - book ordering Insurance - identifying groups of motor insurance policy holders with a high average claim cost or identifying frauds City-planning - identifying groups of houses according to their house type, value and geographical location Earthquake studies - clustering observed earthquake epicenters to identify dangerous zones WWW - document classification clustering weblog data to discover groups of similar access patterns
12/11/09
Distance Measure Important concept of clustering algorithm. Distance between two data points. Euclidian distance can some times be misleading .
12/11/09
Requirements Main requirement an clustering algorithm should satisfy Scalability . Dealing with different types of attributes. Discovering clusters with arbitrary shape. Minimal requirements for domain knowledge to determine input parameters. Ability to deal with noise and outliers. Insensitivity to order of input records. High dimensionality. Interpretability and usability.
12/11/09
K Means Clustering Basic idea is to define k centroids one for each cluster. Each centriod give different result. Purpose is to classify the data. Algorithm groups the objects based on features into K number of group. K is positive integer number. The grouping is done by minimizing the sum of squares of distances between data and the corresponding cluster centroid.
12/11/09
K Means Properties There are always K clusters. There is always at least one item in each cluster. The clusters are non-hierarchical and they do not overlap. Every member of a cluster is closer to its cluster than any other cluster.
12/11/09
Simple Flowchart Of K Means
Step 1 – Start Step 2 – Number of cluster Step 3 – Centroid Step 4 – Distance of objects to centroid Step 5 – Grouping based on minimal distance Step 6 – No object move group If yes Step 7 – End If no ( it iterates) repeat Step 3 to step 6
12/11/09
Simple flowchart of K Means
12/11/09
K Means Equation
Equation J = j=1 ∑k
2 ∑ ǀ X µ ǀ nεSj n j
Here we have Clustering of n data points into
K disjoint subset
Sj
Where
Xn = vector representing nth data point µj= geometric centriod of the data points in Sj
12/11/09
Advantages Of Using K Means Can work with a large number of variables K-Means may be computationally faster K-Means may produce tighter clusters than hierarchical clustering
12/11/09
Disadvantages of using K Means Difficulty in comparing quality of the clusters produced Fixed number of clusters create a problem to predict K value Does not work well with non globular clusters. Different initial partitions can result in different final clusters.
12/11/09
Support Vector Machine Goal of SVM modeling is to find the optimal hyperplane that separates clusters of vector One category of the target variable are on one side of the plane and cases with the other category are on the other size of the plane. Performs classification by constructing an Ndimensional hyperplane Optimally separates the data into two categories. SVM models are closely related to neural networks.
12/11/09
SVM model using a sigmoid kernel function is equivalent to a two-layer, perceptron neural network. Models are a close cousin to classical multilayer perceptron neural networks. Kernel function are an alternative training method
◦ Polynomial ◦ radial basis function ◦ multi-layer perceptron classifiers
weights of the network are found by solving a quadratic programming problem with linear constraints
12/11/09
Predictor variable is called an attribute Solving a non-convex, unconstrained minimization problem not used. Transformed attribute that is used to define the hyperplane is called a feature. Choosing the most suitable representation is known as feature selection. Set of features that describes one case (i.e., a row of predictor values) is called a vector. The vectors near the hyperplane are the support vectors. The figure below presents an overview of the SVM process.
12/11/09
Advantages of using SVM Key advantage of SVM is the use of kernels. The absence of local minima the sparseness of the solution. The capacity control obtained by optimizing the margin.
12/11/09
Disadvantages of using SVM The biggest limitation of the support vector approach lies in choice of the kernel A second limitation is speed and size, both in training and testing. Discrete data presents another problem The optimal design for multiclass SVM classifiers is a further area for research.
12/11/09
Experiments Done Took 500 images from the IRMA image folder Spatial pyramid code applied on that images works fine Histograms made Pyramids where applied to SVM SVM works fine shown the promising results
12/11/09
Conclusion Modification of pyramid match kernel shown good result Method uses global approach to find the object in the image Shown the improvement over the order less image representation Use of SVM works fine shown good result Future work is to develop the method that can take full advantage of discriminative information provided by the images
12/11/09
References
http://www.cs.unc.edu/~lazebnik/spring09/lec18_bag_of_features.pdf http://en.wikipedia.org/wiki/Bag_of_words_model http://lear.inrialpes.fr/~verbeek/slides/bof_classification.pdf http://en.wikipedia.org/wiki/Bag_of_words_model_in_computer_vision http://en.wikipedia.org/wiki/Bag_of_words_model http://people.revoledu.com/kardi/tutorial/kMean/NumericalExample.htm http://cs.gmu.edu/cne/modules/dau/stat/clustgalgs/clust5_bdy.html http://www.resample.com/xlminer/help/kMClst/KMClust_intro.htm http://mathworld.wolfram.com/K-MeansClusteringAlgorithm.html http://www.cs.umd.edu/~mount/Projects/KMeans/ http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html http://en.wikipedia.org/wiki/Cluster_analysis http://en.wikipedia.org/wiki/K-means_clustering http://en.wikipedia.org/wiki/Cluster_%28computing%29 http://www.sdcoe.k12.ca.us/score/actbank/tcluster.htm http://books.google.com/books?id=ZIARBoJQxzcC&dq=clustering&prints
12/11/09
http://www-cvr.ai.uiuc.edu/ponce_grp/publication/paper/bmvc04.pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.8899 http://en.wikipedia.org/wiki/Scale-invariant_feature_transform http://graphics.cs.cmu.edu/courses/15-463/2005_fall/www/Papers/BrownLow http://www.cs.cmu.edu/~rahuls/pub/cvpr2004-keypoint-rahuls.pdf http://www.cs.cmu.edu/~yke/pcasift/ http://people.cs.ubc.ca/~lowe/papers/cvpr97.pdf http://citeseerx.ist.psu.edu/legacymapper?did=526611 http://www.dmoz.org/Computers/Artificial_Intelligence/Machine_Learning/So
http://en.wikipedia.org/wiki/Cluster_analysis http://factominer.free.fr/ http://people.revoledu.com/kardi/tutorial/Clustering/index.html http://www.csse.monash.edu.au/~dld/cluster.html http://cran.r-project.org/web/packages/kernlab/index.html http://adios.tau.ac.il/compact/ http://citeseerx.ist.psu.edu/legacymapper?did=526611 http://www.leet.it/home/lale/joomla/component/option,com_wrapper/Itemid, http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
12/11/09
http://www.javaworld.com/javaworld/jw-11-2006/jw-1121-thread.html http://informationandvisualization.de/blog/kmeans-and-voronoi-tesselation-b
http://mathworld.wolfram.com/K-MeansClusteringAlgorithm.html http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/K-Means_C http://www.resample.com/xlminer/help/kMClst/KMClust_intro.htm http://www.ee.columbia.edu/ln/dvmm/publications/08/FKLforSPM_cvpr08.pdf http://www.ifp.illinois.edu/~jyang29/papers/CVPR09-ScSPM.pdf http://wiki.answers.com/Q/FAQ/4128-3 http://www.robots.ox.ac.uk/~vgg/publications/papers/bosch07.pdf http://www.sciweavers.org/publications/linear-spatial-pyramid-matching-usin http://www.citeulike.org/user/apcoates/article/5314764 http://portal.acm.org/citation.cfm?id=1282280.1282340 http://portal.acm.org/citation.cfm?id=1282280.1282340 http://wapedia.mobi/en/Pyramid_(image_processing) Image source WIKI , spatial_pyramid_matching _sceme_1.pdf
12/11/09
Questions
Thank You