VII. REFERECNES [1] Nirmala Kalidindi, Audrey Le, Dr. Joe Picone, Dr. Victor A. Rudis, Scenic Beauty Estimation, Research Paper, Mississippi State University, 1996. [2] Nagendra Kumar, Ph.D. Thesis. John Hopkins University, 1996. [3] N. Kumar, A. Andreou, "On Generalizations of Linear Discriminant Analysis." Research Paper, John Hopkins University, 1996. [4] Richard O. Duda, Peter E. Hart, Pattern Classification and Scene Analysis. John Wiley & Sons, Inc., 1973. proposal for Scenic Beauty Estimation using Linear Discriminant Analysis submitted to fulfill the semester project requirement for EE 4773/6773: Digital Signal Processing October 25, 1997 submitted to: Dr. Joseph Picone Department of Electrical and Computer Engineering 413 Simrall, Hardy Rd. Mississippi State University Box 9 571 MS State, MS 39762 submitted by: Suresh Babu Balakrishnama & Robert M. Brown Jr. Scenic Beauty Group Department of Electrical and Computer Engineering Mississippi State University Box 6176 Mississippi State, Mississippi 39762 Tel: 601-325-8335 Fax: 601-325-3149 email: balakris@isip.msstate.edu, rmb6@ra.msstate.edu I. ABSTRACT The main focus of this project is to estimate the scenic beauty of forest images using Linear Discriminant Analysis, a valuable tool for multigroup classification and data reduction. This project originated from the United States Forest Service (USFS) to determine the scenic beauty of forests to preserve recreation and aesthetic resources in forest management. The results of this project would be useful to determine a predefined pattern to cut the trees so as to retain the scenic beauty even after cutting the forest for timber. The algorithm will be initially developed and tested in Matlab and this algorithm would be developed in C++. The software developed will be tested on 638 images available in the database to determine their scenic quality.Every image will be rated on a scale of -200 to 200 and the results obtained will be compared with the ratings from the Scenic Beauty Estimation human subjective ratings through the use of histograms. II. INTRODUCTION Background The database to be used is based on two sets of images taken approximately four years apart. The first set consists of photographs taken during 1990-91. The second set consists of photographs taken during 1994-95. The images included in the database were taken from a study spanning four years in the Ouachita Forest in Arkansas. The photographs were taken under controlled conditions and digitized using extremely high quality scanning process. [1] The areas for study were partitioned into four blocks, with each block subdivided into five plots. The database includes images from each plot during each season of the year. The plots were photographed both in the 1990-91 period and the 1994-95 period. Each plot was photographed from at least four different angles. The total umber of images in the database is 4 blocks x 5 plots x 4 seasons x 4 angles x 2 years = 640. An additional 40 images (20 images from the 1990-91 and 20 images from the 1994-95 period) were added as baseline images. A set of 20 images are also included as warm-up slides. These warm-up slides were used to calibrate human performance during subjective testing. [1] Of the original 700 images that were received were partitioned into a set of 679 images used for development, 20 warm-up slides held out from the database proper, and one anomalous slide that suffered from incomplete documentation. [1] The original images were delivered in a proprietary format developed by Kodak know as the PhotoCD format (PCD), a format for archiving high-quality photographs. Due to the proprietary nature of the PCD format, the images were converted to a Portable Pixel Map image (PPM). The PCD to PPM conversion was done using pcdtoppm version 0.6 on a Unix machine. [1] The PPM images were converted from a 4x PCD resolution to 1536 pixel wide x 1024 pixel high format of PPM. Each image requires about 5 Mbytes of disk space. The PPM P6 formatted image used represents each pixel as a sequence of three bytes. The first byte corresponds to the value of the color red encoded on a linear scale of 0 to 255. The second and third numbers represent the values for green and blue colors. Each file also includes information about the image such as the photographic tray and slide number, a human subjective judgement of 1 to10, a Scenic Beauty Rating (SBE), the Normalized Scenic Beauty Rating (SBEZ), the block number, treatment, plot number, date, angle, and other miscellaneous informations. [1] Linear Discriminant Analysis easily handles the case where the within class frequencies are unequal and their performances has been examined on randomly generated test data. This method maximizes the ratio of overall variance to the within class variance in any data class. [2] The use of Linear Discriminant Analysis will be applied to the existing results of the tests applied to the images in hopes to determine a more accurate overall rating for each image. [2] Why LDA? One method commonly used for data compression by dimension reduction is principal component analysis (PCA). The first principal component of a sample vector is the direction along which there is the largest variance over all samples. This direction corresponds to the eigenvector associated with the largest eigenvalue. The kth principal component is chosen to be the linear combination of the input features that has the largest variance, under the constraint that it is also uncorrelated to the previous k-1 principal components. This approach is well suited for data compression, where the objective is to transmit data with minimal distortion. PCA finds more application in pattern classification, where the consideration is that the direction along which there is maximum variation is also most likely to contain the information about the class discrimination. The method of principal components is dependent of feature scaling. Multiplication of the nth component of the input feature vector by some constant cannot possibly affect the information contained in the nth component, about the class with which the input feature vector is associated. However, as this component begins to point in the direction of the nth feature component, although it may not contain any class-discrimination information. The problem is illustrated in the figure 1, if the task is a two way classification and the within-class distributions are Guassians with equal variance in a two dimensional sample space. The ellipses in the figure represent contours of equal probability density for the two Guassians. The line labeled PCA is in the direction of maximum variance for each of the Guassians. In this example, it is also in the direction of the maximum variance of the mixture of the two Guassians, and hence in the direction of the first principal component. But a projection on this line contains no class discrimination information. One optimum solution for this problem is to use methods of Linear Discriminant Analysis (LDA). The first linear discriminant is shown by the labeled LDA. The direction of LDA clearly demonstrates the discrimination maximally between the classes. [2] Theory The problem of dimensionality reduction through linear projections is described as follows: Let x be an n dimensional feature vector. We seek a linear transformation of the form where is a matrix. Let be a non-singular matrix used to define the linear transformation . Let us partition as (1) where consists of the first p columns of and consists of the remaining columns and is the ith column of . Then, feature dimension reduction can be viewed as a two step procedure. First a non-singular linear transformation is applied to x to obtain . Then, in the second step, only the first p rows of y are retained to give . This notation may seem superfluous at the moment. [3] The objective of LDA is to choose the linear transformation in such a way so as to retain the maximum amount of class discrimination information in the reduced feature space. Let there be a total of J classes, and let indicate the class that is associated with . Let be the set of training examples available. Then (here is a notation used to define the set of all i for which ) is the total number of training examples associated with class j, is the total number of training examples. [2] Let be the sample mean. (2) The total normalized sum of squares and products (SSQP) is defined as (3) The class means , the normalized class SSQP , and the overall pooled and normalized SSQP are defined as: (4) (5) and, (6) The two-class LDA method chooses a single projection that maximizes the ratio of the overall SSQP to the within class SSQP: (7) It has been shown that the solution to the above equation corresponds to that right eigenvector of which has the largest eigenvalue. If the number of classes is more that two, we can find a p dimensional linear transformation (p < n) for classification. To get a p-dimensional transformation, we would maximize the ratio (8) To obtain , we choose those eigenvectors of that correspond to the largest p eigenvalues, and let be a matrix of these eigenvectors. The p dimensional features thus obtained are uncorrelated. [3] III. TESTING The LDA technique will be initially coded in Matlab and tested with the training and testing data consisting of 12 features and results would be obtained by reducing features and the results (error performance) will be compared to the previous test results and human SBE ratings. These tests will provide a new space with reduced features where adequate discrimination information is available. This technique will also be applied on sets of synthetic data with 2 or 3 features. The synthetic data to be used will be data that fits the LDA model of specifically grouped data for training and data point inside and outside of the classes to be tested. By initially developing and testing the LDA algorithm in Matlab, it will be ensured that the algorithm is working properly be for the C++ coding is implemented. This will also allow comparison testing with the Matlab code and the C++ code for debugging and testing the final software. IV. PROJECT SUMMARY The project of Scenic Beauty Estimation using Linear Discriminant Analysis is to provide a more accurate estimation of beauty of images from the data base. This project is a continuation of work done as a part of work done by the Institute for Signal and Information Processing and projects done in EE4773/6773: Digital Signal Processing. Linear Discriminant Analysis will be applied to the results of estimations developed from the pre-existing code. The hopes of this project is techniques of LDA will help in better estimation by grouping and weighting the existing data. V. EVALUATION This project will be evaluated by a comparison of the existing ratings for each image, the Scenic Beauty Rating (SBE) and the Normalized Scenic Beauty Rating (SBEZ), the previous estimations, and the results of applying LDA techniques to the results of the existing estimations. The evaluation of this project will consist of comparing the values of the analysis to those standards mentions above with the use of histograms. With this, it will be possible to determine the error between the human SBE rating and the LDA algorithms and to find the difference between the LDA algorithms and the existing results. VI. PROJECT DEMONSTRATION The demonstration for this project will be an active test of our system on images from the database which are to be chosen from the audience. The data from the evaluations already preformed will be processed using the LDA algorithm. A comparison will be made of the scores obtained form the LDA algorithm ratings for the images using the method of evaluation mentioned above. VII. SCHEDULE WEEK TASK Proposal Research Implementation of Algorithms Training and Testing Final Paper Presentation and Demo Figure 2. Schedule of Completion of Key Tasks. 5 6 7 8 9 2 3 4 1 14 13 12 11 10 Figure 1: Comparison of LDA and PCA.