Classificação semântica de imagens com k-NN e RN

Um dos maiores desafios tecnológicos no presente é o de se conseguir gerar e manter, de uma maneira eficiente e consistente, uma base de dados de objectos multimédia, em particular, de imagens. A necessidade de desenvolver métodos de pesquisa automáticos baseados no conteúdo semântico das imagens tornou-se de máxima importância. MPEG-7 é um standard que descreve o contudo dos dados multimédia que suportam estes requisitos operacionais. Adiciona um conjunto de descritores audiovisuais de baixo nível. O histograma é a característica mais utilizada para representar as características globais de uma imagem. Neste trabalho é usado o “Edge Histogram Descriptor” (EHD), que resulta numa representação de baixo nível que permite a computação da similaridade entre imagens. Neste trabalho, é obtida uma caracterização semântica da imagem baseada neste descritor usando dois métodos da classificação: o algoritmo k Nearest Neighbors (k-NN) e uma Rede Neuronal (RN) de retro propagação. No algoritmo k-NN é usada a distância Euclidiana entre os descritores de duas imagens para calcular a similaridade entre imagens diferentes. A RN requer um processo de aprendizagem prévia, que inclui responder correctamente às amostras do treino e às amostras de teste. No fim deste trabalho, será apresentado um estudo sobre os resultados dos dois métodos da classificação.

k-NN based On-Line Handwritten Character recognition system

On-line handwriting recognition has been a frontier area of research for the last few decades under the purview of pattern recognition. Word processing turns to be a vexing experience even if it is with the assistance of an alphanumeric keyboard in Indian languages. A natural solution for this problem is offered through online character recognition. There is abundant literature on the handwriting recognition of western, Chinese and Japanese scripts, but there are very few related to the recognition of Indic script such as Malayalam. This paper presents an efficient Online Handwritten character Recognition System for Malayalam Characters (OHR-M) using K-NN algorithm. It would help in recognizing Malayalam text entered using pen-like devices. A novel feature extraction method, a combination of time domain features and dynamic representation of writing direction along with its curvature is used for recognizing Malayalam characters. This writer independent system gives an excellent accuracy of 98.125% with recognition time of 15-30 milliseconds

Hybrid incremental modeling based on least squares and fuzzy K-NN for monitoring tool wear in turning processes

There is now an emerging need for an efficient modeling strategy to develop a new generation of monitoring systems. One method of approaching the modeling of complex processes is to obtain a global model. It should be able to capture the basic or general behavior of the system, by means of a linear or quadratic regression, and then superimpose a local model on it that can capture the localized nonlinearities of the system. In this paper, a novel method based on a hybrid incremental modeling approach is designed and applied for tool wear detection in turning processes. It involves a two-step iterative process that combines a global model with a local model to take advantage of their underlying, complementary capacities. Thus, the first step constructs a global model using a least squares regression. A local model using the fuzzy k-nearest-neighbors smoothing algorithm is obtained in the second step. A comparative study then demonstrates that the hybrid incremental model provides better error-based performance indices for detecting tool wear than a transductive neurofuzzy model and an inductive neurofuzzy model.

Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

An empirical study of Hoelfding Racing for model selction in K-nearest neighbor classification

Racing algorithms have recently been proposed as a general-purpose method for performing model selection in machine teaming algorithms. In this paper, we present an empirical study of the Hoeffding racing algorithm for selecting the k parameter in a simple k-nearest neighbor classifier. Fifteen widely-used classification datasets from UCI are used and experiments conducted across different confidence levels for racing. The results reveal a significant amount of sensitivity of the k-nn classifier to its model parameter value. The Hoeffding racing algorithm also varies widely in its performance, in terms of the computational savings gained over an exhaustive evaluation. While in some cases the savings gained are quite small, the racing algorithm proved to be highly robust to the possibility of erroneously eliminating the optimal models. All results were strongly dependent on the datasets used.

Computer-aided recognition of dental implants in X-ray images

Dental implant recognition in patients without available records is a time-consuming and not straightforward task. The traditional method is a complete user-dependent process, where the expert compares a 2D X-ray image of the dental implant with a generic database. Due to the high number of implants available and the similarity between them, automatic/semi-automatic frameworks to aide implant model detection are essential. In this study, a novel computer-aided framework for dental implant recognition is suggested. The proposed method relies on image processing concepts, namely: (i) a segmentation strategy for semi-automatic implant delineation; and (ii) a machine learning approach for implant model recognition. Although the segmentation technique is the main focus of the current study, preliminary details of the machine learning approach are also reported. Two different scenarios are used to validate the framework: (1) comparison of the semi-automatic contours against implant’s manual contours of 125 X-ray images; and (2) classification of 11 known implants using a large reference database of 601 implants. Regarding experiment 1, 0.97±0.01, 2.24±0.85 pixels and 11.12±6 pixels of dice metric, mean absolute distance and Hausdorff distance were obtained, respectively. In experiment 2, 91% of the implants were successfully recognized while reducing the reference database to 5% of its original size. Overall, the segmentation technique achieved accurate implant contours. Although the preliminary classification results prove the concept of the current work, more features and an extended database should be used in a future work.

ECG biometrics using a dissimilarity space representation

Electrocardiogram (ECG) biometrics are a relatively recent trend in biometric recognition, with at least 13 years of development in peer-reviewed literature. Most of the proposed biometric techniques perform classifi-cation on features extracted from either heartbeats or from ECG based transformed signals. The best representation is yet to be decided. This paper studies an alternative representation, a dissimilarity space, based on the pairwise dissimilarity between templates and subjects' signals. Additionally, this representation can make use of ECG signals sourced from multiple leads. Configurations of three leads will be tested and contrasted with single-lead experiments. Using the same k-NN classifier the results proved superior to those obtained through a similar algorithm which does not employ a dissimilarity representation. The best Authentication EER went as low as 1:53% for a database employing 503 subjects. However, the employment of extra leads did not prove itself advantageous.

Sistema de localização indoor com base no protocolo ZIGBEE

Actualmente, os sistemas de localização são uma área em forte expansão sendo que para espaços exteriores existe uma grande variedade de sistemas de localização enquanto que para espaços interiores as soluções são mais escassas. Este trabalho apresenta o estudo e implementação de um sistema de localização indoor baseado no protocolo ZigBee, utilizando a informação da intensidade de sinal recebido (RSSI - Received Signal Strength Indication). Para a realização deste projecto foi necessário iniciar uma pesquisa mais pormenorizada do protocolo ZigBee. O dispositivo móvel a ser localizado é o módulo XBee Serie 2 que se baseia no mesmo protocolo. Posto isto, foi necessário efectuar um estudo sobre sistemas de localização existentes e analisar as técnicas de localização utilizadas para ambientes interiores. Desta forma utiliza-se neste projecto uma técnica que consiste na análise de fingerprinting, onde é criado um mapa com os valores RSSI para diferentes coordenadas do espaço físico. As intensidades de sinal recebido são relativas a dispositivos XBee instalados em pontos fixos de referência. Para calcular a localização do dispositivo móvel é utilizado o algoritmo K-NN (K- Nearest Neighbors) que permite estimar a posição aproximada do dispositivo móvel. Por último é descrito todo o desenvolvimento do projecto assim como a apresentação e discussão de resultados.

Estudos quimiométricos em amostras de arroz nacional: caracterização do perfil de aminoácidos e sua correlação com o teor de arsénio

O arroz é um dos alimentos básicos mais importantes para a população mundial, sendo um dos cereais mais consumidos em todo o mundo. Possui um alto teor em hidratos de carbono devido à alta concentração de amido, contém ainda proteínas, vitaminas, minerais e poucas gorduras. A quantidade de proteína a ingerir é requisito para uma dieta adequada (0,75g/kg/dia), devido ao desempenho vital que esta tem na saúde humana. O arroz pelo seu papel determinante na alimentação mundial faz com que os aminoácidos, constituintes das proteínas, mereçam o foco deste estudo. Por outro lado, o arroz pelo seu tipo de cultivo é uma das maiores fontes de ingestão de arsénio para o Homem, um importante agente cancerígeno e contaminante da cadeia alimentar. Isto faz com que este elemento seja igualmente merecedor de análise no presente estudo. Neste estudo foram analisadas, ao nível dos diferentes aminoácidos e do arsénio, 39 amostras de diferentes tipos e regiões de arroz nacional que foram remetidas para uma análise multivariada. Foi feita uma caracterização e posterior comparação entre tipos/variedades/região de arroz, que demonstra para ambos os tipos de estatística (ANOVA e Kruskal-Wallis), diferenças entre variedades, arroz integral e arroz branco. Verifica-se que ao analisar pelas várias características do arroz, não existem diferenças ao nível do arsénio e que, através da correlação de Spearman, este se correlaciona positivamente com arroz integral e negativamente com arroz branco. Na análise de clusters, os aminoácidos (variáveis) foram 3 conjuntos: baixa, média e alta concentração. Por sua vez, as amostras dividem-se pela variedade, formando ainda um cluster em que existe uma fusão de variedades. Para classificação de arroz no futuro, com base no perfil de aminoácidos, foi possível a criação de um modelo k-NN cujo erro de classificação fosse nulo.

On the writer identification in old handwritten music scores

Report for the scientific sojourn at the University of Bern, Swiss, from Mars until June 2008. Writer identification consists in determining the writer of a piece of handwriting from a set of writers. Even though an important amount of compositions contains handwritten text in the music scores, the aim of the work is to use only music notation to determine the author. It’s been developed two approaches for writer identification in old handwritten music scores. The methods proposed extract features from every music line, and also features from a texture image of music symbols. First of all, the music sheet is first preprocessed for obtaining a binarized music score without the staff lines. The classification is performed using a k-NN classifier based on Euclidean distance. The proposed method has been tested on a database of old music scores from the 17th to 19th centuries, achieving encouraging identification rates.

Automatic Mapping and Classification of Spatial Environmental Data

The paper deals with the development and application of the generic methodology for automatic processing (mapping and classification) of environmental data. General Regression Neural Network (GRNN) is considered in detail and is proposed as an efficient tool to solve the problem of spatial data mapping (regression). The Probabilistic Neural Network (PNN) is considered as an automatic tool for spatial classifications. The automatic tuning of isotropic and anisotropic GRNN/PNN models using cross-validation procedure is presented. Results are compared with the k-Nearest-Neighbours (k-NN) interpolation algorithm using independent validation data set. Real case studies are based on decision-oriented mapping and classification of radioactively contaminated territories.

Machine learning for geospatial data : algorithms, software tools and case studies

Résumé Cette thèse est consacrée à l'analyse, la modélisation et la visualisation de données environnementales à référence spatiale à l'aide d'algorithmes d'apprentissage automatique (Machine Learning). L'apprentissage automatique peut être considéré au sens large comme une sous-catégorie de l'intelligence artificielle qui concerne particulièrement le développement de techniques et d'algorithmes permettant à une machine d'apprendre à partir de données. Dans cette thèse, les algorithmes d'apprentissage automatique sont adaptés pour être appliqués à des données environnementales et à la prédiction spatiale. Pourquoi l'apprentissage automatique ? Parce que la majorité des algorithmes d'apprentissage automatiques sont universels, adaptatifs, non-linéaires, robustes et efficaces pour la modélisation. Ils peuvent résoudre des problèmes de classification, de régression et de modélisation de densité de probabilités dans des espaces à haute dimension, composés de variables informatives spatialisées (« géo-features ») en plus des coordonnées géographiques. De plus, ils sont idéaux pour être implémentés en tant qu'outils d'aide à la décision pour des questions environnementales allant de la reconnaissance de pattern à la modélisation et la prédiction en passant par la cartographie automatique. Leur efficacité est comparable au modèles géostatistiques dans l'espace des coordonnées géographiques, mais ils sont indispensables pour des données à hautes dimensions incluant des géo-features. Les algorithmes d'apprentissage automatique les plus importants et les plus populaires sont présentés théoriquement et implémentés sous forme de logiciels pour les sciences environnementales. Les principaux algorithmes décrits sont le Perceptron multicouches (MultiLayer Perceptron, MLP) - l'algorithme le plus connu dans l'intelligence artificielle, le réseau de neurones de régression généralisée (General Regression Neural Networks, GRNN), le réseau de neurones probabiliste (Probabilistic Neural Networks, PNN), les cartes auto-organisées (SelfOrganized Maps, SOM), les modèles à mixture Gaussiennes (Gaussian Mixture Models, GMM), les réseaux à fonctions de base radiales (Radial Basis Functions Networks, RBF) et les réseaux à mixture de densité (Mixture Density Networks, MDN). Cette gamme d'algorithmes permet de couvrir des tâches variées telle que la classification, la régression ou l'estimation de densité de probabilité. L'analyse exploratoire des données (Exploratory Data Analysis, EDA) est le premier pas de toute analyse de données. Dans cette thèse les concepts d'analyse exploratoire de données spatiales (Exploratory Spatial Data Analysis, ESDA) sont traités selon l'approche traditionnelle de la géostatistique avec la variographie expérimentale et selon les principes de l'apprentissage automatique. La variographie expérimentale, qui étudie les relations entre pairs de points, est un outil de base pour l'analyse géostatistique de corrélations spatiales anisotropiques qui permet de détecter la présence de patterns spatiaux descriptible par une statistique. L'approche de l'apprentissage automatique pour l'ESDA est présentée à travers l'application de la méthode des k plus proches voisins qui est très simple et possède d'excellentes qualités d'interprétation et de visualisation. Une part importante de la thèse traite de sujets d'actualité comme la cartographie automatique de données spatiales. Le réseau de neurones de régression généralisée est proposé pour résoudre cette tâche efficacement. Les performances du GRNN sont démontrées par des données de Comparaison d'Interpolation Spatiale (SIC) de 2004 pour lesquelles le GRNN bat significativement toutes les autres méthodes, particulièrement lors de situations d'urgence. La thèse est composée de quatre chapitres : théorie, applications, outils logiciels et des exemples guidés. Une partie importante du travail consiste en une collection de logiciels : Machine Learning Office. Cette collection de logiciels a été développée durant les 15 dernières années et a été utilisée pour l'enseignement de nombreux cours, dont des workshops internationaux en Chine, France, Italie, Irlande et Suisse ainsi que dans des projets de recherche fondamentaux et appliqués. Les cas d'études considérés couvrent un vaste spectre de problèmes géoenvironnementaux réels à basse et haute dimensionnalité, tels que la pollution de l'air, du sol et de l'eau par des produits radioactifs et des métaux lourds, la classification de types de sols et d'unités hydrogéologiques, la cartographie des incertitudes pour l'aide à la décision et l'estimation de risques naturels (glissements de terrain, avalanches). Des outils complémentaires pour l'analyse exploratoire des données et la visualisation ont également été développés en prenant soin de créer une interface conviviale et facile à l'utilisation. Machine Learning for geospatial data: algorithms, software tools and case studies Abstract The thesis is devoted to the analysis, modeling and visualisation of spatial environmental data using machine learning algorithms. In a broad sense machine learning can be considered as a subfield of artificial intelligence. It mainly concerns with the development of techniques and algorithms that allow computers to learn from data. In this thesis machine learning algorithms are adapted to learn from spatial environmental data and to make spatial predictions. Why machine learning? In few words most of machine learning algorithms are universal, adaptive, nonlinear, robust and efficient modeling tools. They can find solutions for the classification, regression, and probability density modeling problems in high-dimensional geo-feature spaces, composed of geographical space and additional relevant spatially referenced features. They are well-suited to be implemented as predictive engines in decision support systems, for the purposes of environmental data mining including pattern recognition, modeling and predictions as well as automatic data mapping. They have competitive efficiency to the geostatistical models in low dimensional geographical spaces but are indispensable in high-dimensional geo-feature spaces. The most important and popular machine learning algorithms and models interesting for geo- and environmental sciences are presented in details: from theoretical description of the concepts to the software implementation. The main algorithms and models considered are the following: multi-layer perceptron (a workhorse of machine learning), general regression neural networks, probabilistic neural networks, self-organising (Kohonen) maps, Gaussian mixture models, radial basis functions networks, mixture density networks. This set of models covers machine learning tasks such as classification, regression, and density estimation. Exploratory data analysis (EDA) is initial and very important part of data analysis. In this thesis the concepts of exploratory spatial data analysis (ESDA) is considered using both traditional geostatistical approach such as_experimental variography and machine learning. Experimental variography is a basic tool for geostatistical analysis of anisotropic spatial correlations which helps to understand the presence of spatial patterns, at least described by two-point statistics. A machine learning approach for ESDA is presented by applying the k-nearest neighbors (k-NN) method which is simple and has very good interpretation and visualization properties. Important part of the thesis deals with a hot topic of nowadays, namely, an automatic mapping of geospatial data. General regression neural networks (GRNN) is proposed as efficient model to solve this task. Performance of the GRNN model is demonstrated on Spatial Interpolation Comparison (SIC) 2004 data where GRNN model significantly outperformed all other approaches, especially in case of emergency conditions. The thesis consists of four chapters and has the following structure: theory, applications, software tools, and how-to-do-it examples. An important part of the work is a collection of software tools - Machine Learning Office. Machine Learning Office tools were developed during last 15 years and was used both for many teaching courses, including international workshops in China, France, Italy, Ireland, Switzerland and for realizing fundamental and applied research projects. Case studies considered cover wide spectrum of the real-life low and high-dimensional geo- and environmental problems, such as air, soil and water pollution by radionuclides and heavy metals, soil types and hydro-geological units classification, decision-oriented mapping with uncertainties, natural hazards (landslides, avalanches) assessments and susceptibility mapping. Complementary tools useful for the exploratory data analysis and visualisation were developed as well. The software is user friendly and easy to use.

Análise comparativa de classificadores digitais em imagens do Landsat-8 aplicados ao mapeamento temático

Resumo: O objetivo deste trabalho foi avaliar o desempenho dos classificadores digitais SVM e K-NN para a classificação orientada a objeto em imagens Landsat-8, aplicados ao mapeamento de uso e cobertura do solo da Alta Bacia do Rio Piracicaba-Jaguari, MG. A etapa de pré-processamento contou com a conversão radiométrica e a minimização dos efeitos atmosféricos. Em seguida, foi feita a fusão das bandas multiespectrais (30 m) com a banda pancromática (15 m). Com base em composições RGB e inspeções de campo, definiram-se 15 classes de uso e cobertura do solo. Para a segmentação de bordas, aplicaram-se os limiares 10 e 60 para as configurações de segmentação e união no aplicativo ENVI. A classificação foi feita usando SVM e K-NN. Ambos os classificadores apresentaram elevados valores de índice Kappa (k): 0,92 para SVM e 0,86 para K-NN, significativamente diferentes entre si a 95% de probabilidade. Uma significativa melhoria foi observada para SVM, na classificação correta de diferentes tipologias florestais. A classificação orientada a objetos é amplamente aplicada em imagens de alta resolução espacial; no entanto, os resultados obtidos no presente trabalho mostram a robustez do método também para imagens de média resolução espacial.

Keraamisten laattojen luokittelu väripiirteiden avulla

Vaikka keraamisten laattojen valmistusprosessi onkin täysin automatisoitu, viimeinen vaihe eli laaduntarkistus ja luokittelu tehdään yleensä ihmisvoimin. Automaattinen laaduntarkastus laattojen valmistuksessa voidaan perustella taloudellisuus- ja turvallisuusnäkökohtien avulla. Tämän työn tarkoituksena on kuvata tutkimusprojektia keraamisten laattojen luokittelusta erilaisten väripiirteiden avulla. Oleellisena osana tutkittiin RGB- ja spektrikuvien välistä eroa. Työn teoreettinen osuus käy läpi aiemmin aiheesta tehdyn tutkimuksen sekä antaa taustatietoa konenäöstä, hahmontunnistuksesta, luokittelijoista sekä väriteoriasta. Käytännön osan aineistona oli 25 keraamista laattaa, jotka olivat viidestä eri luokasta. Luokittelussa käytettiin apuna k:n lähimmän naapurin (k-NN) luokittelijaa sekä itseorganisoituvaa karttaa (SOM). Saatuja tuloksia verrattiin myös ihmisten tekemään luokitteluun. Neuraalilaskenta huomattiin tärkeäksi työkaluksi spektrianalyysissä. SOM:n ja spektraalisten piirteiden avulla saadut tulokset olivat lupaavia ja ainoastaan kromatisoidut RGB-piirteet olivat luokittelussa parempia kuin nämä.

KOIVUVIILUN LAATULAJITTELUN KEHITTÄMINEN

Työssä on tutkittu Koskisen Oy:n vaneritehtaan 2. kuivauslinjalla toimivaa viilun laatulajittelujärjestelmää, jonka toiminnan tehostamiseksi haettiin uusia, vaihtoehtoisia ratkaisuja. Lajittelujärjestelmän toiminnan nopeuttamiseen ja toimivuuden kehittämiseksi haettiin ratkaisuja dimensio-, reuna- ja sisävikojen käsittelyyn. Linjan käyttöasteen kasvattamiseksi sen vikadiagnostiikkaan ja toi¬min¬nan seurantaan haettiin myös uusia menetelmiä. Kuvatun arkin reunatietojen avulla pystytään ottamaan huomioon käytönaikaisten asemointivirheiden aiheuttamat mittavirheet. Vika-alueiden harmaatasoarvoista kerättyä tietoa käytetään histogrammipiirteiden irrotuksessa oksien luokittelua parantamiseksi. Neuroluokittelijoiden käyttöönottoa luokittelijoina puoltavat niiden luokittelunopeus itse luokittelussa ja lähes k-NN-luokittimen tasoon yltävä luokittelutarkkuus. Neuroluokittelijoista tutkittiin monikerros-Perceptron- (MLP) ja oppiva vektorikvantisaatio- (LVQ) luokittelijat. Edellä mainittujen muutosten käyttöönoton avulla parantuneen viiluarkin onnistunut laadutus tuo kustannussäästöjä yritykselle sekä viiluarkkien paremman hyväksikäytön että viilun jatkokäsittelyssä säästyvän työmäärän avulla.