Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Visual Vocabulary Constructionfor Mining Biomedical ImagesArnab Bhattacharya, Vebjorn Ljosa, Jia-Yu PanPresented by Li An, CIS, TUIntroduction•Given a large collection of biomedical images of several conditions and treatments, how to describe the important regions in the images , or the differences between different experimental conditions?Figure 1. (a) a normal retina and (b) a retina after 3 days of detachment. The retinas were labeled with antibodies to rhodopsin (red) and glial fibrillary acidic protein (GFAP, green).Introduction•Build a system that will automatically detect and highlight patterns differentiating image classes, after processing hundreds or thousands of pictures.•Problem 1 –Summarize an image automatically.•Problem 2 –Identify patterns that distinguish image classes.•Problem 3 –Highlight interesting regions in an image.Related work•Textual Vocabulary and Visual Vocabulary•Previous work applied transformation on image pixels.–The high dimensionality of pixels limited these methods to small images–Clustering algorithms or transformation-based methods, like K-means, PCA, Wavelet transforms, ICA also have problems with orientation and registration issues–One way to deal with this dimensionality curse is to extract a small number of features from image pixels.Proposed Method•We propose to automatically develop a visual vocabulary by breaking images into n-by-n tiles, and derive key tiles (ViVos) for each image and condition. This method successfully avoids issues such as registration and dimensionality curse. •Tiles–The idea of “tiles” is introduced for visual term generation•ViVos –A novel approach to group tiles into visual terms. We call our automatically extracted visual terms “ViVos.”ViVo Definition•A ViVo is defined by either the positive or the negative direction of an ICA basis vector, and represents a characteristic pattern in image tiles. •The ViVo-vector of a tile ˜ti,j is a vector v(˜ti,j) = f1, . . . , fm], where fi indicates the contibutions of the i-th ViVo in describing the tile. •The ViVo-vector of an image is defined as the sum of the ViVo-vectors of all its tiles.ViVo ConstructingViVo ConstructingViVo Constructing•The first step partitions the images into non-overlapping tiles.–The optimal tile size depends on the nature of the images.–The tiles must be large enough to capture the characteristic textures of the images. –On the other hand, they cannot be too large.–Figure 1(a), we use a tile size of 64-by-64 pixels, so each retinal image has 8×12 tilesViVo Constructing•In the second step, a feature vector is extracted from each tile, representing its image content.–MPEG-7 features •Color structure descriptor (CSD)•Color layout descriptor (CLD) •Homogeneous texture descriptor (HTD)–The vector representing a tile using features of, say CSD, is called a tile-vector of the CSD.ViVo Constructing•The third step derives a set of symbols from the feature vectors of all the tiles of all the images.•We derive a set of symbols by applying ICA or PCA to the feature vectors. Each orthogonal (basis) vector found by ICA or PCA becomes a symbol. We call the symbols ViVos and the set of symbols a visual vocabulary.•Each basis vector defines two ViVos, one along the positive direction of the vector, another along the negative direction.ViVo ConstructingFigure 2. ViVos (ICA vs PCA). Each point corresponds to a tile. Basis vectors (P1,P2, I1, I2, I3) are scaled for visualization.ViVo Constructing•Let T0 be a t-by-d matrix, where t is the number of tiles from all training images, and d is the number of features extracted from each tile. Each row of T0 corresponds to a tile-vector .~ti,j, with the overall mean subtracted.•Suppose we want to generate m ViVos. We first reduce the dimensionality of T0 from d to m’ =m/2, using PCA, yielding a t-by-m’ matrix T. •Next, ICA is applied in order to decompose T into two matrices H[t*m’] and B[m’*m’] such that T = HB. The rows of B are the ICA basis vectors (solid lines in Figure 2). •Considering the positive and negative directions of each basis vector, the m’ ICA basis vectors would dene m = 2m’ ViVos, which are the outputs of the function gen_vv().ViVo Constructing•How do we determine the number of ViVos? We follow the rule of thumb, and make m’ =m/2 be the dimensionality which preserves 95% spread/energy of the distribution.ViVo Constructing•Fourth step, with the ViVos ready, we can use them to represent an image. –Represent each d-dim tile-vector in terms of ViVos by projecting a tile-vector to the m’-dim PCA space and then to the m’-dim ICA space. –The positive and negative projection coefficients are then considered separately, yielding the 2m’-dim ViVo-vector of a tile. –The m = 2m’ coefficients in the ViVo-vector of a tile also indicate the contributions of each of the m ViVos to the tile.ViVo Constructing•Final step, each image is expressed by simply adding up the ViVo-vectors of the tiles in an image.•It is a good description of the entire image because ICA producesViVos that do not “interfere” with each other. ICA makes the columns of H as independent as possibleViVo Visualization•A ViVo is represented by a tile that strongly expresses the characteristics of that ViVo. •The representative tiles of a ViVo vk, T (vk), are then selected from its tile group (essentially the tiles at the “tip” of the tile group).ViVo Tile GroupsVisualizes the tile groups of two ViVos on the 2-D plane defined by the PCA basis vectors (P1;P2). The top 5 representative tiles of the two ViVos are shown in light triangles.Figure 3Quantitative Evaluation•Classification–Classication of Retinal Images–Classication of Subcellular Protein Localization Images•Data Mining Using ViVos–Biological Interpretation of ViVos–Finding Most Discriminative ViVos–Highlighting Interesting Regions by ViVosClassificationBiological Interpretation of ViVosFigure 4Finding Most Discriminative ViVosFigure 5. Pairs of conditions and the corresponding discriminative ViVos. There is an edge in the graph for each pair of conditions that is important from a biological point of view. The numbers on each edge indicate the ViVos that