The use of digital images of handwritten historical documents has increased in recent years. This has been possible through the Internet, which allows users to access a vast collection of historical documents and makes historical and data research more attainable. However, the insurmountable number of images available in these digital libraries is cumbersome for a single user to read and process. Computers could help read these images through methods known as Optical Character Recognition (OCR), which have had significant success for printed materials but only limited success for handwritten ones. Most of these OCR methods work well only when the images have been preprocessed by getting rid of anything in the image that is not text. This preprocessing step is usually known as binarization. The binarization of images of historical documents that have been affected by degradation and that are of poor image quality is difficult and continues to be a focus of research in the field of image processing. We propose two novel approaches to attempt to solve this problem. One combines recursive Otsu thresholding and selective bilateral filtering to allow automatic binarization and segmentation of handwritten text images. The other adds background normalization and a post-processing step to the algorithm to make it more robust and to work even for images that present bleed-through artifacts. Our results show that these techniques help segment the text in historical documents better than traditional binarization techniques.

In the 1930s, the Carnegie Institute in Washington DC initiated the construction of cosmic ray observation centres around the world. Cosmic ray activity was recorded using the model C cosmic ray ionization chamber which uses a Lindemann electrometer. Seven of these chambers were constructed at seven stations around the world. These chambers recorded cosmic ray data by projecting the shadow of the electrometer needle onto a continuously moving strip of 60 mm photographic paper. Hour markers were recorded by dimming the lamp for three minutes at the start of each hour, while also grounding the ionization chamber. By grounding the ionization chamber the electrometer needle was returned to the zero position. The photographic paper moved about 25 mm an hour. Approximately 114 station-years of data was recorded between 1935 and 1960 (Hardy, 2006). It is important to digitize these recordings in order to preserve the data for further study of cosmic rays from this time period. This digitization process consists of binarizing digital images of the photographic strip to extract the cosmic ray data. By binarizing these images the data is recorded in an easily usable format for future research. This study focuses on extraction of the cosmic ray data using an adaptive binarization method that is able to cope with a wide variety of images, ranging from images that are almost too bright to distinguish the data lines from the background, to images that are too dark to distinguish the data lines at all. This study starts off with a brief explanation of cosmic rays, how these were recorded before the 1950s and how the rays are recorded today. Two research methodologies were used to create a method to adaptively binarize and extract data from the historic cosmic ray recordings. A literature study of image processing techniques was conducted, focusing specifically on popular adaptive document binarization methods. During the experimental phase of this study, these methods or parts thereof were applied to the data to determine which techniques would give the most accurate results. Experimentation is the primary research methodology. The iterative experimental phase is discussed in detail as an algorithm is formed to successfully binarize and extract the historic cosmic ray data as well as the temperature of the electrometer while recording. The study concludes with an interpretation of the results obtained in the experimental phase. The success of the algorithm is measured by comparing the resulting data graph to the original. The conclusion of this study is that an adaptive method can be applied to historical recordings of cosmic ray activity to extract numerical data from a wide variety of images without any additional user input. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2013

In the 1930s, the Carnegie Institute in Washington DC initiated the construction of cosmic ray observation centres around the world. Cosmic ray activity was recorded using the model C cosmic ray ionization chamber which uses a Lindemann electrometer. Seven of these chambers were constructed at seven stations around the world. These chambers recorded cosmic ray data by projecting the shadow of the electrometer needle onto a continuously moving strip of 60 mm photographic paper. Hour markers were recorded by dimming the lamp for three minutes at the start of each hour, while also grounding the ionization chamber. By grounding the ionization chamber the electrometer needle was returned to the zero position. The photographic paper moved about 25 mm an hour. Approximately 114 station-years of data was recorded between 1935 and 1960 (Hardy, 2006). It is important to digitize these recordings in order to preserve the data for further study of cosmic rays from this time period. This digitization process consists of binarizing digital images of the photographic strip to extract the cosmic ray data. By binarizing these images the data is recorded in an easily usable format for future research. This study focuses on extraction of the cosmic ray data using an adaptive binarization method that is able to cope with a wide variety of images, ranging from images that are almost too bright to distinguish the data lines from the background, to images that are too dark to distinguish the data lines at all. This study starts off with a brief explanation of cosmic rays, how these were recorded before the 1950s and how the rays are recorded today. Two research methodologies were used to create a method to adaptively binarize and extract data from the historic cosmic ray recordings. A literature study of image processing techniques was conducted, focusing specifically on popular adaptive document binarization methods. During the experimental phase of this study, these methods or parts thereof were applied to the data to determine which techniques would give the most accurate results. Experimentation is the primary research methodology. The iterative experimental phase is discussed in detail as an algorithm is formed to successfully binarize and extract the historic cosmic ray data as well as the temperature of the electrometer while recording. The study concludes with an interpretation of the results obtained in the experimental phase. The success of the algorithm is measured by comparing the resulting data graph to the original. The conclusion of this study is that an adaptive method can be applied to historical recordings of cosmic ray activity to extract numerical data from a wide variety of images without any additional user input. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2013

Em muitas aplicações de processamento de imagens é desejável converter imagens que estão em escala de cinza para imagens binarias, ou seja, em apenas dois níveis de intensidade. Para realizar essa tarefa de separação entre dois níveis é necessário que se calcule um valor de limiar, pois a partir dele determinamos quais pixels irão pertencer a um nível, normalmente o objeto de interesse, e quais pertencerão ao outro nível, ou ao fundo da imagem. Algumas aplicações exigem que se calcule esse valor de limiar em um tempo muito curto em relação à aquisição de imagem, principalmente quando ocorre uma variação muito alta de luminosidade na aquisição de uma imagem. Para suprir essa dificuldade de velocidade nas aplicações de processamento de imagem, uma alternativa seria o desenvolvimento de uma arquitetura dedicada que realize o cálculo do valor de limiar e binarize a imagem adquirida. O presente trabalho apresenta o desenvolvimento de uma arquitetura que realiza estas tarefas, implementada em circuitos reconfiguráveis do tipo FPGA. A validação da arquitetura foi obtida por meio da comparação dos resultados obtidos com a simulação da mesma na ferramenta Matlab. A arquitetura permite uma frequência máxima de clock de 84,52 MHz, o que permite a utilização da arquitetura em sistemas de tempo real, utilizando como fonte de imagem um vídeo composto ou uma câmera comum. / In many imaging applications it is desirable that images are converted to grayscale images to binary, ie with only two intensity levels. To accomplish this task separation between two levels is necessary to calculate a threshold value as determined from it which pixels will belong to a level generally the object of interest, and which belong to another level, or to the background image . Some applications require you to calculate this threshold value in a very short time in relation to image acquisition, especially when a very high brightness variation in the acquisition of an image. To meet this difficulty in the speed image processing applications, an alternative would be to develop an architecture dedicated to perform the calculation of the value of threshold and binarize the image acquired. This paper proposes the development of an architecture that performs these tasks by implementing reconfigurable circuits like FPGA. Making a comparison of results obtained with algorithms developed in Matlab, thus performing a validation of the proposed architecture. The developed architecture has reached the maximum frequency of 84.52 MHz, and the architecture can be operated in real-time system, using an image as a source of composite video or a regular camera.

Em muitas aplicações de processamento de imagens é desejável converter imagens que estão em escala de cinza para imagens binarias, ou seja, em apenas dois níveis de intensidade. Para realizar essa tarefa de separação entre dois níveis é necessário que se calcule um valor de limiar, pois a partir dele determinamos quais pixels irão pertencer a um nível, normalmente o objeto de interesse, e quais pertencerão ao outro nível, ou ao fundo da imagem. Algumas aplicações exigem que se calcule esse valor de limiar em um tempo muito curto em relação à aquisição de imagem, principalmente quando ocorre uma variação muito alta de luminosidade na aquisição de uma imagem. Para suprir essa dificuldade de velocidade nas aplicações de processamento de imagem, uma alternativa seria o desenvolvimento de uma arquitetura dedicada que realize o cálculo do valor de limiar e binarize a imagem adquirida. O presente trabalho apresenta o desenvolvimento de uma arquitetura que realiza estas tarefas, implementada em circuitos reconfiguráveis do tipo FPGA. A validação da arquitetura foi obtida por meio da comparação dos resultados obtidos com a simulação da mesma na ferramenta Matlab. A arquitetura permite uma frequência máxima de clock de 84,52 MHz, o que permite a utilização da arquitetura em sistemas de tempo real, utilizando como fonte de imagem um vídeo composto ou uma câmera comum. / In many imaging applications it is desirable that images are converted to grayscale images to binary, ie with only two intensity levels. To accomplish this task separation between two levels is necessary to calculate a threshold value as determined from it which pixels will belong to a level generally the object of interest, and which belong to another level, or to the background image . Some applications require you to calculate this threshold value in a very short time in relation to image acquisition, especially when a very high brightness variation in the acquisition of an image. To meet this difficulty in the speed image processing applications, an alternative would be to develop an architecture dedicated to perform the calculation of the value of threshold and binarize the image acquired. This paper proposes the development of an architecture that performs these tasks by implementing reconfigurable circuits like FPGA. Making a comparison of results obtained with algorithms developed in Matlab, thus performing a validation of the proposed architecture. The developed architecture has reached the maximum frequency of 84.52 MHz, and the architecture can be operated in real-time system, using an image as a source of composite video or a regular camera.

We present works on theory and applications for Mixed Integer Quadratically Constrained Quadratic Programs (MIQCQP). We introduce new mixed integer programming (MIP)-based relaxation and approximation schemes for general Quadratically Constrained Quadratic Programs (QCQP's), and also study practical applications of QCQP's and Mixed-integer QCQP's (MIQCQP). We first address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a discrete-time nonconvex MIQCP, then approximate this model as a MILP using a discretization-based approach. We combine a rolling horizon approach with the discretization of individual chemical property specifications to deal with long scheduling horizons, time-varying quality specifications, and multiple suppliers with discrete arrival times. Next, we study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs). These SPs are parallel mechanisms that are stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. The robot will be used in concert with several other types robots to perform complex assembly missions in space. We develop algorithms and optimization models that can efficiently decide on favorable poses and movements that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger workspace and a greater overall payload capacity. In the third work, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions and formulate this approximation using mixed-integer programming (MIP). Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. We computationally demonstrate that our model outperforms existing MIP relaxations, and on hard instances can compete with state-of-the-art solvers. Finally, we study piecewise linear relaxations for solving quadratically constrained quadratic programs (QCQP's). We introduce new relaxation methods based on univariate reformulations of nonconvex variable products, leveraging the relaxation from the third work to model each univariate quadratic term. We also extend the NMDT approach (Castro, 2015) to leverage discretization for both variables in a bilinear term, squaring the resulting precision for the same number of binary variables. We then present various results related to the relative strength of the various formulations. / Doctor of Philosophy / First, we study a challenging long-horizon supply acquisition problem for a chemical plant. For this problem, constraints with products of variables are required to track raw material composition from supply carriers to storage tanks to the production feed. We apply a mixed-integer nonlinear program (MIP) approximation of the problem combined with a rolling planning scheme to obtain good solutions for industry problems within a reasonable time frame. Next, we study optimization methods applied to a robot designed as a stack of Stewart platforms (SPs), which will be used in concert with several other types robots to perform complex space missions. When chaining these SPs together, we obtain a robot that is generally stiffer more precise than a classic robot arm, enabling their potential use for a variety of purposes. Our methods can efficiently decide on favorable poses and movements for the robot that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger usable range of motion and a greater overall payload capacity. Our final two works focus on MIP-based techniques for nonconvex QCQP's. In the first work, we break down the objective into an easy-to-handle term minus some squared terms. We then introduce an elegant new MIP-based approximation to handle these squared terms. We prove that this approximation has strong theoretical guarantees, then demonstrate that it is effective compared to other approximations. In the second, we directly model each variable product term using a MIP relaxation. We introduce two new formulations to do this that build on previous formulations, increasing the accuracy with the same number of integer variables. We then prove a variety of useful properties about the presented formulations, then compare them computationally on two families of problems.

In binary Gaussian process classification the prior class membership probabilities are obtained by transforming a Gaussian process to the unit interval, typically either with the logistic likelihood function or the cumulative Gaussian likelihood function. Multiclass classification problems can be handled by any binary classifier by means of so-called binarization techniques, which reduces the multiclass problem into a number of binary problems. Other than introducing the mathematics behind the theory and methods behind Gaussian process classification, we compare the binarization techniques one-against-all and one-against-one in the context of Gaussian process classification, and we also compare the performance of the logistic likelihood and the cumulative Gaussian likelihood. This is done by means of two experiments: one general experiment where the methods are tested on several publicly available datasets, and one more specific experiment where the methods are compared with respect to class imbalance and class overlap on several artificially generated datasets. The results indicate that there is no significant difference in the choices of binarization technique and likelihood function for typical datasets, although the one-against-one technique showed slightly more consistent performance. However the second experiment revealed some differences in how the methods react to varying degrees of class imbalance and class overlap. Most notably the logistic likelihood was a dominant factor and the one-against-one technique performed better than one-against-all.

The current state-of-the-art, in terms of performance, for solving document image binarization is training artificial neural networks on pre-labelled ground truth data. As such, it faces the same issues as other, more conventional, classification problems; requiring a large amount of training data. However, unlike those conventional classification problems, document image binarization involves having to either manually craft or estimate the binarized ground truth data, which can be error-prone and time-consuming. This is where sample selection, the act of selecting training samples based on some method or metric, might help. By reducing the size of the training dataset in such a way that the binarization performance is not impacted, the required time spent creating the ground truth is also reduced. This thesis proposes a cluster-based sample selection method, based on previous work, that uses image similarity metrics and the relative neighbourhood graph to reduce the underlying redundancy of the dataset. The method is implemented with different clustering methods and similarity metrics for comparison, with the best implementation being based on affinity propagation and the structural similarity index. This implementation manages to reduce the training dataset by 46\% while maintaining a performance that is equal to that of the complete dataset. The performance of this method is shown to not be significantly different from randomly selecting the same number of samples. However, due to limitations in the random method, such as unpredictable performance and uncertainty in how many samples to select, the use of sample selection in document image binarization still shows great promise.

Há uma vasta quantidade de informação nos textos antigos manuscritos e tipografados, e grandes esforços para a digitalização e disponibilização desses documentos têm sido feitos nos últimos anos. No entanto, os sistemas de Reconhecimento Óptico de Caracteres (OCR) não têm grande sucesso nesses documentos por diversas razões, por exemplo, devido a defeitos por envelhecimento do papel, manchas, iluminação desigual, dobras, escrita do verso transparecendo na frente, pouco contraste entre texto e fundo, entre outros. Uma das etapas importantes para o sucesso de um OCR é a boa segmentação da parte escrita e do fundo da imagem (binarização) e essa etapa é particularmente sensível a esses efeitos que são próprios de documentos históricos. Tanto assim que nos últimos oito anos foram realizadas competições de métodos de binarização de documentos históricos que levaram ao avanço do estado da arte na área. Neste trabalho fizemos um estudo comparativo de diversos métodos de segmentação de documentos antigos e propusemos um método baseado em aprendizado de máquina que resgata as vantagens dos métodos heurísticos. Esse estudo abrangeu documentos históricos manuscritos e tipografados e foi comparado com os métodos do estado da arte via métricas usuais e via um sistema de OCR de código aberto. Os resultados obtidos pelo método proposto são comparáveis com os métodos do estado da arte respeito no resultado do OCR, mostrando algumas vantagens em imagens específicas. / There is a vast amount of information in the ancient handwritten and machine-printed texts, and great efforts for the digitization and availability of these documents have been made in recent years. However, Optical Character Recognition (OCR) systems do not have much success in these documents for a variety of reasons, for example, due to paper aging defects, faded ink, stains, uneven lighting, folds, bleed-through, gosthing, poor contrast between text and background, among others. One of the important steps for the success of an OCR system is the good segmentation of the written part and the background of the image (binarization) and this step is particularly sensitive to those defects that are typical of historical documents. So much so that in the last eight years a competition for the binarization methods of historical documents have been held which led to the advance of the state of the art in the area. In this work we have done a comparative study of several methods of segmentation of historical documents and propose a method based on machine learning that rescues the advantages of the heuristic methods. This study covered both handwritten and typography historical documents and was compared to state-of-the-art methods via DIBCO standard metrics and via an open source OCR system. The results obtained by the proposed method are comparable with the methods of the state of the art respect in the OCR result, showing some advantages in specific images.

Performance improvement of a 3-D configuration reconstruction algorithm using a passive secondary target has been focused in this study. In earlier studies, a theoretical development of the 3-D configuration reconstruction algorithm was achieved and it was implemented by a computer program on a system consisting of an optical bench and a digital imaging system. The passive secondary target used was a circle with two internal spots. In order to use this reconstruction algorithm in autonomous systems, an automatic target recognition algorithm has been developed in this study. Starting from a pre-captured and stored 8-bit gray-level image, the algorithm automatically detects the elliptical image of a circular target and determines its contour in the scene. It was shown that the algorithm can also be used for partially captured elliptical images. Another improvement achieved in this study is the determination of internal camera parameters of the vision system.