Efficient Nearest Neighbor Classification Using a Cascade of Approximate Similarity Measures

Nearest neighbor classification using shape context can yield highly accurate results in a number of recognition problems. Unfortunately, the approach can be too slow for practical applications, and thus approximation strategies are needed to make shape context practical. This paper proposes a method for efficient and accurate nearest neighbor classification in non-Euclidean spaces, such as the space induced by the shape context measure. First, a method is introduced for constructing a Euclidean embedding that is optimized for nearest neighbor classification accuracy. Using that embedding, multiple approximations of the underlying non-Euclidean similarity measure are obtained, at different levels of accuracy and efficiency. The approximations are automatically combined to form a cascade classifier, which applies the slower approximations only to the hardest cases. Unlike typical cascade-of-classifiers approaches, that are applied to binary classification problems, our method constructs a cascade for a multiclass problem. Experiments with a standard shape data set indicate that a two-to-three order of magnitude speed up is gained over the standard shape context classifier, with minimal losses in classification accuracy.

Learning Embeddings for Indexing, Retrieval, and Classification, with Applications to Object and Shape Recognition in Image Databases

Nearest neighbor retrieval is the task of identifying, given a database of objects and a query object, the objects in the database that are the most similar to the query. Retrieving nearest neighbors is a necessary component of many practical applications, in fields as diverse as computer vision, pattern recognition, multimedia databases, bioinformatics, and computer networks. At the same time, finding nearest neighbors accurately and efficiently can be challenging, especially when the database contains a large number of objects, and when the underlying distance measure is computationally expensive. This thesis proposes new methods for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed methods are domain-independent, and can be applied in arbitrary spaces, including non-Euclidean and non-metric spaces. In this thesis particular emphasis is given to computer vision applications related to object and shape recognition, where expensive non-Euclidean distance measures are often needed to achieve high accuracy. The first contribution of this thesis is the BoostMap algorithm for embedding arbitrary spaces into a vector space with a computationally efficient distance measure. Using this approach, an approximate set of nearest neighbors can be retrieved efficiently - often orders of magnitude faster than retrieval using the exact distance measure in the original space. The BoostMap algorithm has two key distinguishing features with respect to existing embedding methods. First, embedding construction explicitly maximizes the amount of nearest neighbor information preserved by the embedding. Second, embedding construction is treated as a machine learning problem, in contrast to existing methods that are based on geometric considerations. The second contribution is a method for constructing query-sensitive distance measures for the purposes of nearest neighbor retrieval and classification. In high-dimensional spaces, query-sensitive distance measures allow for automatic selection of the dimensions that are the most informative for each specific query object. It is shown theoretically and experimentally that query-sensitivity increases the modeling power of embeddings, allowing embeddings to capture a larger amount of the nearest neighbor structure of the original space. The third contribution is a method for speeding up nearest neighbor classification by combining multiple embedding-based nearest neighbor classifiers in a cascade. In a cascade, computationally efficient classifiers are used to quickly classify easy cases, and classifiers that are more computationally expensive and also more accurate are only applied to objects that are harder to classify. An interesting property of the proposed cascade method is that, under certain conditions, classification time actually decreases as the size of the database increases, a behavior that is in stark contrast to the behavior of typical nearest neighbor classification systems. The proposed methods are evaluated experimentally in several different applications: hand shape recognition, off-line character recognition, online character recognition, and efficient retrieval of time series. In all datasets, the proposed methods lead to significant improvements in accuracy and efficiency compared to existing state-of-the-art methods. In some datasets, the general-purpose methods introduced in this thesis even outperform domain-specific methods that have been custom-designed for such datasets.

The notion of space in urban housing markets

O mercado imobiliário tem um papel importante nas economias modernas, tanto a nível macro como a nível micro. Ao nível macro, a construção de habitação representa um sector importante e influente na economia, com efeitos multiplicadores significativos sobre a produção e o emprego. Ao nível micro, uma residência representa o activo mais valioso da maioria dos indivíduos e uma parcela muito relevante da riqueza das famílias. Para estas, o custo e a qualidade das suas habitações influencia directa e indirectamente a sua qualidade de vida. A habitação é por isso mesmo um tema, que avaliado nas suas múltiplas dimensões, se caracteriza por ser bastante complexo, mas também ao mesmo tempo desafiante. De modo a delimitar o objecto de análise do trabalho de investigação, esta tese realça os aspectos de localização e distribuição espacial das habitações urbanas. Será desenvolvido um quadro conceptual e respectiva metodologia para a compreender a estrutura espacial da habitação urbana realçando os três aspectos fundamentais da análise espacial: heterogenidade espacial, dependência espacial e escala espacial. A metodologia, aplicada à área urbana de Aveiro e Ílhavo é baseada numa análise hedónica factorial de preços e na noção não geométrica do espaço. Primeiro, é fixada uma escala territorial e são definidos submercados habitacional. Posteriormente, quer a heterogeneidade quer a dependência espaciais são estudados utilizando métodos econométricos, sem considerar qualquer padrão fixo e conhecido de interações espaciais. Em vez disso, são desenvolvidos novos métodos,tendo como base o modelo hedónico factorial, para inferir sobre os potenciais drivers de difusão espacial no valor de uma habitação. Este modelo, foi aplicado a duas diferentes escalas espaciais, para compreender as preferências dos indivíduos em Aveiro ao escolher os seus locais de residencia, e como estas afectam os preços da habitação. O trabalho empírico, utilizando duas bases de dados de habitação distintas, aplicadas ao mercado de habitação de Aveiro mostram: i) em linha com a literatura, a dificuldade de definir submercados e compreender as inter-relações entre esses mercados; ii) a utilidade de uma abordagem híbrida, combinando análise factorial com regressão; iii) a importância fundamental que o efeito escala espacial desempenha no estudo da heterogeneidade e dos spillovers e, finalmente, iv) uma metodologia inovadora para analisar spillovers sem assumir aprioristicamente uma estrutura espacial específica de difusão espacial. Esta metodologia considera a matriz de pesos espaciais (W) desconhecida e estimatima as interações espaciais dentro e entre submercados habitação.

Using self organizing maps on compositional data

Self-organizing maps (Kohonen 1997) is a type of artificial neural network developed to explore patterns in high-dimensional multivariate data. The conventional version of the algorithm involves the use of Euclidean metric in the process of adaptation of the model vectors, thus rendering in theory a whole methodology incompatible with non-Euclidean geometries. In this contribution we explore the two main aspects of the problem: 1. Whether the conventional approach using Euclidean metric can shed valid results with compositional data. 2. If a modification of the conventional approach replacing vectorial sum and scalar multiplication by the canonical operators in the simplex (i.e. perturbation and powering) can converge to an adequate solution. Preliminary tests showed that both methodologies can be used on compositional data. However, the modified version of the algorithm performs poorer than the conventional version, in particular, when the data is pathological. Moreover, the conventional ap- proach converges faster to a solution, when data is \well-behaved". Key words: Self Organizing Map; Artificial Neural networks; Compositional data

Implícits filosòfics del convencionalisme en la geometria espaciotemporal

Treball que té com a objectiu, en primer lloc, establir quina possibilitat té el convencionalisme de ser una alternativa a les concepcions realistes de la geometria relativista; en segon lloc, assenyalar les implicacions epistemològiques que en deriven; en tercer lloc, precisar quin tipus de lectura de la hipòtesi inicial hem de fer donat que hi ha un cert marge per a l’ambigüitat i això ha permès diverses propostes; i en quart i darrer lloc, en cas que hom accepti les restriccions que el convencionalisme imposa al nostre coneixement, hem de veure quines conclusions podem extreure en l’àmbit ontològic i fins a quin punt són significatives per a la discussió sobre la relació entre matemàtica i naturalesa

Integrating control systems defined on the frame bundles of the space forms

This paper considers left-invariant control systems defined on the orthonormal frame bundles of simply connected manifolds of constant sectional curvature, namely the space forms Euclidean space E-3, the sphere S-3 and Hyperboloid H-3 with the corresponding frame bundles equal to the Euclidean group of motions SE(3), the rotation group SO(4) and the Lorentz group SO(1, 3). Orthonormal frame bundles of space forms coincide with their isometry groups and therefore the focus shifts to left-invariant control systems defined on Lie groups. In this paper a method for integrating these systems is given where the controls are time-independent. In the Euclidean case the elements of the Lie algebra se(3) are often referred to as twists. For constant twist motions, the corresponding curves g(t) is an element of SE(3) are known as screw motions, given in closed form by using the well known Rodrigues' formula. However, this formula is only applicable to the Euclidean case. This paper gives a method for computing the non-Euclidean screw motions in closed form. This involves decoupling the system into two lower dimensional systems using the double cover properties of Lie groups, then the lower dimensional systems are solved explicitly in closed form.

Oriented vehicles travelling in spherical space

This paper tackles the path planning problem for oriented vehicles travelling in the non-Euclidean 3-Dimensional space; spherical space S3. For such problem, the orientation of the vehicle is naturally represented by orthonormal frame bundle; the rotation group SO(4). Orthonormal frame bundles of space forms coincide with their isometry groups and therefore the focus shifts to control systems defined on Lie groups. The oriented vehicles, in this case, are constrained to travel at constant speed in a forward direction and their angular velocities directly controlled. In this paper we identify controls that induce steady motions of these oriented vehicles and yield closed form parametric expressions for these motions. The paths these vehicles trace are defined explicitly in terms of the controls and therefore invariant with respect to the coordinate system used to describe the motion.

Optimal steady motions for oriented vehicles

Motivated by the motion planning problem for oriented vehicles travelling in a 3-Dimensional space; Euclidean space E3, the sphere S3 and Hyperboloid H3. For such problems the orientation of the vehicle is naturally represented by an orthonormal frame over a point in the underlying manifold. The orthonormal frame bundles of the space forms R3,S3 and H3 correspond with their isometry groups and are the Euclidean group of motion SE(3), the rotation group SO(4) and the Lorentzian group SO(1; 3) respectively. Orthonormal frame bundles of space forms coincide with their isometry groups and therefore the focus shifts to left-invariant control systems defined on Lie groups. In this paper a method for integrating these systems is given where the controls are time-independent. For constant twist motions or helical motions, the corresponding curves g(t) 2 SE(3) are given in closed form by using the well known Rodrigues’ formula. However, this formula is only applicable to the Euclidean case. This paper gives a method for computing the non-Euclidean screw/helical motions in closed form. This involves decoupling the system into two lower dimensional systems using the double cover properties of Lie groups, then the lower dimensional systems are solved explicitly in closed form.

Treatment of PET and PU polymers by atmospheric pressure plasma generated in dielectric barrier discharge in air

Plasma treatments are frequently employed to modify surface properties of materials such as adhesivity, hydrophobicity, oleophobicity etc. Present work deals with surface modification of common commercial polymers such as polyethylene terephthalate (PET) and polyurethane (PU) by an air dielectric barrier discharge (DBD) at atmospheric pressure. The DBD treatment was performed in a plain reactor in wire-duct geometry (non-uniform field reactor), which was driven by a 60 Hz power supply. Material characterization was carried out by water contact angle measurements, atomic force microscopy (AFM) and X-ray photoelectron spectroscopy (XPS). The plasma-induced modifications are associated with incorporation of polar oxygen and nitrogen containing groups on the polymer surface. The AFM analysis reveals that the plasma treatment roughens the material surface. Due to these structural and morphological changes the surface of DBD-treated polymers becomes more hydrophilic resulting in enhanced adhesion properties. (C) 2010 Elsevier B.V. All rights reserved.

Toward a planning model for the peruvian university system as a competitive strategy.

University education in Peru is based on models of teacher-centered teaching and a conception of knowledge which is closed and static and under the dominance of an information model now overwhelmed by multiple factors hastened by international change. The worlds most prestigious universities have chosen cultural diversity as a sign of quality and are hence interested in the mobility of teachers and students through exchange and cooperation with foreign educational institutions. These universities respond more effectively to pressure from the international business sector, better satisfy training demands, introduce new information and communication technologies into education and research and have improved administration and management structures. While there is progress, the university system in Peru is a planning model defined "as a discipline that seeks to respond to the needs of an organization defined by new cultural and social models" (A. Cazorla, et al 2007).This paper studies the non-Euclidean thinking of planning and development of John Friedmann (2001). Based on the four domains of social practice, it proposes a planning model for Peruvian universities that meets international requirements.

Passive Acoustics: A Multifaceted Tool for Marine Mammal Conservation

Marine mammals exploit the efficiency of sound propagation in the marine environment for essential activities like communication and navigation. For this reason, passive acoustics has particularly high potential for marine mammal studies, especially those aimed at population management and conservation. Despite the rapid realization of this potential through a growing number of studies, much crucial information remains unknown or poorly understood. This research attempts to address two key knowledge gaps, using the well-studied bottlenose dolphin (Tursiops truncatus) as a model species, and underwater acoustic recordings collected on four fixed autonomous sensors deployed at multiple locations in Sarasota Bay, Florida, between September 2012 and August 2013. Underwater noise can hinder dolphin communication. The ability of these animals to overcome this obstacle was examined using recorded noise and dolphin whistles. I found that bottlenose dolphins are able to compensate for increased noise in their environment using a wide range of strategies employed in a singular fashion or in various combinations, depending on the frequency content of the noise, noise source, and time of day. These strategies include modifying whistle frequency characteristics, increasing whistle duration, and increasing whistle redundancy. Recordings were also used to evaluate the performance of six recently developed passive acoustic abundance estimation methods, by comparing their results to the true abundance of animals, obtained via a census conducted within the same area and time period. The methods employed were broadly divided into two categories – those involving direct counts of animals, and those involving counts of cues (signature whistles). The animal-based methods were traditional capture-recapture, spatially explicit capture-recapture (SECR), and an approach that blends the “snapshot” method and mark-recapture distance sampling, referred to here as (SMRDS). The cue-based methods were conventional distance sampling (CDS), an acoustic modeling approach involving the use of the passive sonar equation, and SECR. In the latter approach, detection probability was modelled as a function of sound transmission loss, rather than the Euclidean distance typically used. Of these methods, while SMRDS produced the most accurate estimate, SECR demonstrated the greatest potential for broad applicability to other species and locations, with minimal to no auxiliary data, such as distance from sound source to detector(s), which is often difficult to obtain. This was especially true when this method was compared to traditional capture-recapture results, which greatly underestimated abundance, despite attempts to account for major unmodelled heterogeneity. Furthermore, the incorporation of non-Euclidean distance significantly improved model accuracy. The acoustic modelling approach performed similarly to CDS, but both methods also strongly underestimated abundance. In particular, CDS proved to be inefficient. This approach requires at least 3 sensors for localization at a single point. It was also difficult to obtain accurate distances, and the sample size was greatly reduced by the failure to detect some whistles on all three recorders. As a result, this approach is not recommended for marine mammal abundance estimation when few recorders are available, or in high sound attenuation environments with relatively low sample sizes. It is hoped that these results lead to more informed management decisions, and therefore, more effective species conservation.