The field of computer vision studies the computational tools and methods required for computers to be able to process visual information, for example images and video. Shape descriptors are one of the tools commonly used in image processing applications. Shape descriptors are mathematical functions which are applied to an image and produce numerical values which are representative of a particular characteristic of the image. These numerical values can then be processed in order to provide some information about the image. For example, these values can be fed to a classifier in order to assign a class label to the image. There are a number of shape descriptors already existing in the literature for 2D and 3D images. The aim of this thesis is to develop additional shape descriptors which provide an improvement over (or an alternative to) those already existing in the literature. A large majority of the existing 2D shape descriptors use surface information to produce a measure. However, in some applications surface information is not present and only partially extracted contours are available. In such cases, boundary based shape descriptors must be used. A new boundary based shape descriptor called Linearity is introduced. This measure can be applied to open or closed curve segments. In general the availability of 3D images is comparatively smaller than that of 2D images. As a consequence, the number of existing 3D shape descriptors is also relatively smaller. However, there is an increasing interest in the development of 3D descriptors. In this thesis we present two basic 3D measures which afterwards are modified to produce a range of new shape descriptors. All of these descriptors are similar in their behaviour, however they can be combined and applied in different image processing applications such as image retrieval and classification. This simple fact is demonstrated through several examples.

Slow-servo single-point diamond turning as well as advances in computer controlled small lap polishing enable the fabrication of freeform optics, specifically, optical surfaces for imaging applications that are not rotationally symmetric. Freeform optical elements will have a profound importance in the future of optical technology. Orthogonal polynomials added onto conic sections have been extensively used to describe optical surface shapes. The optical testing industry has chosen to represent the departure of a wavefront under test from a reference sphere in terms of orthogonal φ-polynomials, specifically Zernike polynomials. Various forms of polynomials for describing freeform optical surfaces may be considered, however, both in optical design and in support of fabrication. More recently, radial basis functions were also investigated for optical shape description. In the application of orthogonal φ-polynomials to optical freeform shape description, there are important limitations, such as the number of terms required as well as edge-ringing and ill-conditioning in representing the surface with the accuracy demanded by most stringent optics applications. The first part of this dissertation focuses upon describing freeform optical surfaces with φ-polynomials and shows their limitations when including higher orders together with possible remedies. We show that a possible remedy is to use edge-clusteredfitting grids. Provided different grid types, we furthermore compared the efficacy of using different types of φ-polynomials, namely Zernike and gradient orthogonal Q-polynomials. In the second part of this thesis, a local, efficient and accurate hybrid method is developed in order to greatly reduce the order of polynomial terms required to achieve higher level of accuracy in freeform shape description that were shown to require thousands of terms including many higher order terms under prior art. This comes at the expense of multiple sub-apertures, and as such iv computational methods may leverage parallel processing. This new method combines the assets of both radial basis functions and orthogonal phi-polynomials for freeform shape description and is uniquely applicable across any aperture shape due to its locality and stitching principles. Finally in this thesis, in order to comprehend the possible advantages of parallel computing for optical surface descriptions, the benefits of making an effective use of impressive computational power offered by multi-core platforms for the computation of φ-polynomials are investigated. The φ-polynomials, specifically Zernike and gradient orthogonal Q-polynomials, are implemented with a set of recurrence based parallel algorithms on Graphics Processing Units (GPUs). The results show that more than an order of magnitude speedup is possible in the computation of φ-polynomials over a sequential implementation if the recurrence based parallel algorithms are adopted.

There are currently over 138, 000 known macromolecular structures deposited in the wwPDB (Worldwide Protein Data Bank) database. While all the macromolecular structure files contain information about a particular structure, the collection of these files also allows combining the macromolecular structures to obtain statistical information about macromolecules in general. This fact has been the basis for many structural biology methods including the molecular replacement method used in X-ray crystallography or homologous structure restraints in the refinement methods. With the success of methods based on prior information, it is feasible that novel methods could be developed and current methods improved using further prior information; more specifically, by using the structure density-map shape similarity instead of sequence or model similarity. Therefore, this project introduces a mathematical framework for computing three different measures of macromolecular three-dimensional shape similarity and demonstrates how these descriptors can be applied in symmetry detection and protein-domain clustering. The ability to detect cyclic (C), dihedral (D), tetrahedral (T), octahedral (O) and icosahedral (I) symmetry groups as well as computing all associated symmetry elements has direct applications in map averaging and reducing the storage requirements by storing only the asymmetric information. Moreover, by having the capacity to find structures with similar shape, it was possible to reduce the size of the BALBES protein domain database by more than 18.7% and thus achieve proportional speed-up in the searching parts of its applications. Finally, the development of the method described in this project has many possible applications throughout structural biology. The method could, for example, facilitate matching and fitting of protein domains into the density maps produced by the electron-microscopy techniques, or it could allow for molecular-replacement candidate search using shape instead of sequence similarity. To allow for the development of any further applications, software for applying the methods described here is also presented and released for the community.

We report on initial experiments with an implemented learning system whose inputs are images of two-dimensional shapes. The system first builds semantic network descriptions of shapes based on Brady's smoothed local symmetry representation. It learns shape models form them using a substantially modified version of Winston's ANALOGY program. A generalization of Gray coding enables the representation to be extended and also allows a single operation, called ablation, to achieve the effects of many standard induction heuristics. The program can learn disjunctions, and can learn concepts suing only positive examples. We discuss learnability and the pervasive importance of representational hierarchies.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Sistemas de recuperaÃÃo de imagens baseada em conteÃdo (do termo em inglÃs, Content-Based Image Retrieval - CBIR) que operam em bases com grande volume de dados constituem um problema relevante e desafiador em diferentes Ãreas do conhecimento, a saber, medicina, biologia, computaÃÃo, catalogaÃÃo em geral, etc. A indexaÃÃo das imagens nestas bases pode ser realizada atravÃs de conteÃdo visual como cor, textura e forma, sendo esta Ãltima caracterÃstica a traduÃÃo visual dos objetos em uma cena. Tarefas automatizadas em inspeÃÃo industrial, registro de marca, biometria e descriÃÃo de imagens utilizam atributos da forma, como os cantos, na geraÃÃo de descritores para representaÃÃo, anÃlise e reconhecimento da mesma, possibilitando ainda que estes descritores se adequem ao uso em sistemas de recuperaÃÃo. Esta tese aborda o problema da extraÃÃo de caracterÃsticas de formas planares binÃrias a partir de cantos, na proposta de um detector multiescala de cantos e sua aplicaÃÃo em um sistema CBIR. O mÃtodo de detecÃÃo de cantos proposto combina uma funÃÃo de angulaÃÃo do contorno da forma, a sua decomposiÃÃo nÃo decimada por transformada wavelet ChapÃu Mexicano e a correlaÃÃo espacial entre as escalas do sinal de angulaÃÃo decomposto. A partir dos resultados de detecÃÃo de cantos, foi realizado um experimento com o sistema CBIR proposto, em que informaÃÃes locais e globais extraÃdas dos cantos detectados da forma foram combinadas à tÃcnica DeformaÃÃo Espacial DinÃmica (do termo em inglÃs, Dynamic Space Warping), para fins de anÃlise de similaridade formas com tamanhos distintos. Ainda com este experimento foi traÃada uma estratÃgia de busca e ajuste dos parÃmetros multiescala de detectores de cantos, segundo a maximizaÃÃo de uma funÃÃo de custo. Na avaliaÃÃo de desempenho da metodologia proposta, e outras tÃcnicas de detecÃÃo de cantos, foram empregadas as medidas PrecisÃo e RevocaÃÃo. Estas medidas atestaram o bom desempenho da metodologia proposta na detecÃÃo de cantos verdadeiros das formas, em uma base pÃblica de imagens cujas verdades terrestres estÃo disponÃveis. Para a avaliaÃÃo do experimento de recuperaÃÃo de imagens, utilizamos a taxa Bullâs eye em trÃs bases pÃblicas. Os valores alcanÃados desta taxa mostraram que o experimento proposto foi bem sucedido na descriÃÃo e recuperaÃÃo das formas, dentre os demais mÃtodos avaliados. / Content-based image retrieval (CBIR) applied to large scale datasets is a relevant and challenging problem present in medicine, biology, computer science, general cataloging etc. Image indexing can be done using visual information such as colors, textures and shapes (the visual translation of objects in a scene). Automated tasks in industrial inspection, trademark registration, biostatistics and image description use shape attributes, e.g. corners, to generate descriptors for representation, analysis and recognition; allowing those descriptors to be used in image retrieval systems. This thesis explores the problem of extracting information from binary planar shapes from corners, by proposing a multiscale corner detector and its use in a CBIR system. The proposed corner detection method combines an angulation function of the shape contour, its non-decimated decomposition using the Mexican hat wavelet and the spatial correlation among scales of the decomposed angulation signal. Using the information provided by our corner detection algorithm, we made experiments with the proposed CBIR. Local and global information extracted from the corners detected on shapes was used in a Dynamic Space Warping technique in order to analyze the similarity among shapes of different sizes. We also devised a strategy for searching and refining the multiscale parameters of the corner detector by maximizing an objective function. For performance evaluation of the proposed methodology and other techniques, we employed the Precision and Recall measures. These measures proved the good performance of our method in detecting true corners on shapes from a public image dataset with ground truth information. To assess the image retrieval experiments, we used the Bullâs eye score in three public databases. Our experiments showed our method performed well when compared to the existing approaches in the literature.

A great number of methods based on local features or global appearances have been proposed in the literature for geospatial object detection and recognition from satellite images. However, since these approaches do not have enough discriminative capabilities between object and non-object classes, they produce results with innumerable false positives during their detection process. Moreover, due to the sliding window mechanisms, these algorithms cannot yield exact location information for the detected objects. Therefore, a geospatial object recognition algorithm based on the object shape mask is proposed to minimize the aforementioned imperfections. In order to develop such a robust recognition system, foreground extraction performance of some of popular fully and semi-automatic image segmentation algorithms, such as normalized cut, k-means clustering, mean-shift for fully automatic, and interactive Graph-cut, GrowCut, GrabCut for semi-automatic, are evaluated in terms of their subjective and objective qualities. After this evaluation, the retrieval performance of some shape description techniques, such as ART, Hu moments and Fourier descriptors, are investigated quantitatively. In the proposed system, first of all, some hypothesis points are generated for a given test image. Then, the foreground extraction operation is achieved via GrabCut algorithm after utilizing these hypothesis points as if these are user inputs. Next, the extracted binary object masks are described by means of the integrated versions of shape description techniques. Afterwards, SVM classifier is used to identify the target objects. Finally, elimination of the multiple detections coming from the generation of hypothesis points is performed by some simple post-processing on the resultant masks. Experimental results reveal that the proposed algorithm has promising results in terms of accuracy in recognizing many geospatial objects, such as airplane and ship, from high resolution satellite imagery.

This thesis is concerned with topics related to dense mapping of large scale three-dimensional spaces. In particular, the motivating scenario of this work is one in which a mobile robot with limited computational resources explores an unknown environment using a depth-camera. To this end, low-level topics such as sensor noise, map representation, interpolation, bit-rates, compression are investigated, and their impacts on more complex tasks, such as feature detection and description, camera-tracking, and mapping are evaluated thoroughly. A central idea of this thesis is the use of truncated signed distance fields (TSDF) as a map representation and a comprehensive yet accessible treatise on this subject is the first major contribution of this dissertation. The TSDF is a voxel-based representation of 3D space that enables dense mapping with high surface quality and robustness to sensor noise, making it a good candidate for use in grasping, manipulation and collision avoidance scenarios. The second main contribution of this thesis deals with the way in which information can be efficiently encoded in TSDF maps. The redundant way in which voxels represent continuous surfaces and empty space is one of the main impediments to applying TSDF representations to large-scale mapping. This thesis proposes two algorithms for enabling large-scale 3D tracking and mapping: a fast on-the-fly compression method based on unsupervised learning, and a parallel algorithm for lifting a sparse scene-graph representation from the dense 3D map. The third major contribution of this work consists of thorough evaluations of the impacts of low-level choices on higher-level tasks. Examples of these are the relationships between gradient estimation methods and feature detector repeatability, voxel bit-rate, interpolation strategy and compression ratio on camera tracking performance. Each evaluation thus leads to a better understanding of the trade-offs involved, which translate to direct recommendations for future applications, depending on their particular resource constraints.

The entrainment rate of Ferrosilicone (FeSi) particles was measured in a 140 mm perspex column with air as the fluidising medium. Two different types of FeSi were used, namely atomised FeSi, which is mostly spherical in shape with smooth surfaces, and milled FeSi, which is irregular with rough surfaces. Both the FeSi mixtures had the same solid density and the similar average particle diameters ranging from 38 µm to 50 µm. The size and density of these particles put them on the border between Geldart A and Geldart B powders, similar to the high temperature Fischer-Tropsch catalyst. The atomised FeSi had a slightly higher concentration in fines (8.6% vs 1.8%), but except for the difference in particle shape, the two mixtures had otherwise very similar physical properties. A substantial difference in entrainment rate was measured between the atomised and milled FeSi, where the atomised had an entrainment rate of about six times higher than the milled FeSi throughout the range of superficial velocities tested. It was shown that the higher entrainment rate cannot be attributed only to the higher fines concentration, but that the difference in particle shape had a significant effect on the entrainment rate. Several two dimensional shape characterisation techniques were used in attempt to quantify the difference between the atomised and the milled FeSi. Of these the particle circularity managed to differentiate the best between the two particle mixtures. The circularities of the atomised and the milled FeSi were found to be 0.782 and 0.711 respectively. The measured circularity was used instead of a sphericity to adjust for the effect of particle shape on the terminal velocity of the particles. The adjusted terminal velocity was then used in the elutriation rate constant correlations to see which of the popular correlations in literature predicts the entrainment rate of the FeSi the best. All of the correlations gave a poor performance in predicting the measured entrainment rates. The two correlations that performed the best were that of Choi et al. (1999) (AARE = 72.6%) and Geldart et al. (1979) (AARE = 79%). It was concluded that single particle drag and single particle terminal velocities are not adequate to incorporate the effect of particle shape on entrainment rate. The method i by which shape affects entrainment rate therefore deserves further investigation. Further studies should also be done to develop a three dimensional shape descriptor that predicts bulk behaviour better. / Dissertation (MEng)--University of Pretoria, 2008. / Chemical Engineering / unrestricted

<p>Mathematical models of classes of objects can significantly contribute to the analysis of digital images. A major problem in modelling is to establish suitable descriptions that cover not only a single object but also the variation that is usually present within a class of objects.</p><p>The objective of this thesis is to develop more general modelling strategies than commonly used today. In particular, the impact of the human factor in the model creation process should be minimised. It is presumed that the human ability of abstraction imposes undesired constraints on the description. In comparison, common approaches are discussed from the viewpoint of generality.</p><p>The technique considered introduces <i>appearance space </i>as a common framework to represent both shapes and images. In appearance space, an object is represented by a single point in a high-dimensional vector space. Accordingly, objects subject to variation appear as <i>nonlinear manifolds</i> in appearance space. These manifolds are often characterised by only a few intrinsic dimensions. A model of a class of objects is therefore considered equal to the mathematical description of this manifold.</p><p>The presence of nonlinearity motivates the use of artificial auto-associative neural networks in the modelling process. The network extracts nonlinear modes of variation from a number of training examples. The procedure is evaluated on both synthetic and natural data of shapes and images and shows promising results as a general approach to object modelling.</p>

<p>New methods for global shape description of three-dimensional digital objects are presented. The shape of an object is first represented by a digital surface where the faces are either triangles or quadrilaterals. Techniques for computing a high-quality parameterization of the surface are developed and this parameterization is used to approximate the shape of the object. Spherical harmonics are used as basis functions for approximations of the coordinate functions. Information about the global shape is then captured by the coefficients in the spherical harmonics expansions.</p><p>For a starshaped object it is shown how a parameterization can be computed by a projection from its surface onto the unit sphere. An algorithm for computing the position at which the centre of the sphere should be placed, is presented. This algorithm is suited for digital voxel objects. Most of the work is concerned with digital objects whose surfaces are homeomorphic to the sphere. The standard method for computing parameterizations of such surfaces is shown to fail on many objects. This is due to the large distortions of the geometric properties of the surface that often occur with this method. Algorithms to handle this problem are suggested. Non-linear optimization methods are used to find a mapping between a surface and the sphere that minimizes geometric distortion and is useful as a parameterization of the surface. </p><p>The methods can be applied, for example, in medical imaging for shape recognition, detection of shape deformations and shape comparisons of three-dimensional objects.</p>